>> ZAMYLA CHAN: Mari kita membuat pemeriksa ejaan.
Jika Anda membuka speller.c, maka Anda akan melihat bahwa sebagian besar fungsi untuk
memeriksa file teks terhadap kamus sudah dibuat untuk Anda.
. / Ejaan, lewat di teks kamus mengajukan dan kemudian file teks lain,
akan memeriksa file teks terhadap kamus.
>> Sekarang, file teks kamus akan berisi kata-kata yang valid, satu per baris.
Kemudian speller.c akan memanggil Beban pada file teks kamus.
Ini akan memanggil fungsi yang disebut Memeriksa setiap kata dalam file teks diinput,
mencetak semua kata yang salah eja.
>> Speller.c juga akan memanggil Ukuran untuk menentukan jumlah kata dalam
kamus dan memanggil Unload untuk membebaskan memori.
speller.c juga akan melacak bagaimana banyak waktu yang digunakan untuk melakukan ini
proses, tapi kita akan bisa nanti.
>> Jadi apa yang perlu kita lakukan?
Kita perlu mengisi dictionary.c.
Dalam dictionary.c, kita memiliki penolong fungsi Load, yang memuat
kamus.
Fungsi Periksa, yang memeriksa apakah kata yang diberikan dalam kamus.
Fungsi Ukuran mengembalikan nomor kata-kata dalam kamus.
Dan akhirnya, kami telah Membongkar, yang membebaskan kamus dari memori.
>> Jadi pertama, mari kita menangani beban.
Untuk setiap kata dalam teks kamus File, Load akan menyimpan kata-kata dalam
struktur data kamus Anda pilih, baik
hash table atau trie.
Aku akan pergi ke baik di ini berjalan melalui.
>> Pertama mari kita bicara tentang tabel hash.
Katakanlah Anda memiliki 10 bola bilyar dan Anda ingin menyimpannya.
Anda mungkin menempatkan mereka semua dalam ember, dan ketika Anda membutuhkan spesifik
bernomor bola, Anda akan mengambil satu keluar dari ember pada suatu waktu
mencari bola itu.
Dan dengan hanya 10 bola, Anda harus mampu menemukan bola dalam waktu yang wajar
jumlah waktu.
>> Tetapi bagaimana jika Anda memiliki 20 bola?
Mungkin butuh waktu lebih lama sekarang.
Bagaimana dengan 100?
1.000?
Sekarang, itu akan jauh lebih mudah jika Anda memiliki beberapa ember.
Mungkin satu ember untuk bola bernomor nol melalui sembilan, ember lain untuk
bola bernomor 10 melalui 19, dan seterusnya.
>> Sekarang ketika Anda perlu mencari khusus bola, Anda bisa secara otomatis
pergi ke salah satu ember tertentu dan mencari melalui ember itu.
Dan jika setiap kotak memiliki sekitar 10 bola, maka Anda bisa dengan mudah mencari
melalui itu.
>> Sekarang, karena kita sedang berhadapan dengan kamus, satu ember tunggal untuk
semua kata-kata dalam kamus akan mungkin jauh terlalu sedikit ember.
Jadi mari kita lihat tabel hash.
>> Anggap saja sebagai array ember.
Dan dalam hal ini, ember adalah daftar link kami.
Dan kita akan mendistribusikan semua kata-kata kita antara ini beberapa daftar terkait dalam
cara diatur menggunakan fungsi hash, yang akan memberitahu kami yang
ember kunci yang diberikan, diberikan kata, milik.
>> Mari kita mewakili ini secara skematik.
Kotak-kotak biru di sini mengandung nilai-nilai dan kotak merah menunjukkan nilai lain
pair pointer.
Kami akan menelepon pasangan ini node.
Sekarang, setiap kotak, seperti yang saya katakan sebelumnya, adalah linked list.
Dalam daftar terkait, setiap node memiliki nilai, serta pointer ke
nilai berikutnya.
>> Sekarang, berurusan dengan daftar terkait, itu sangat penting bahwa Anda
tidak kehilangan link apapun.
Dan fakta lain yang perlu diingat adalah bahwa node terakhir, jika tidak menunjuk ke
node lain, menunjuk ke null.
>> Jadi bagaimana kita merepresentasikan ini di C?
Kami mendefinisikan struct kami di sini.
Dan nilai dalam hal ini adalah array char panjang.
Panjang ditambah 1, di mana panjang adalah Panjang maksimum setiap kata, ditambah 1 untuk
null terminator.
Dan kemudian kita memiliki pointer ke simpul lain yang disebut Next.
>> Jadi mari kita membuat daftar link kecil.
Pertama, Anda akan ingin untuk malloc node, yang menciptakan ruang dalam memori
ukuran tipe node Anda.
Dan membuat node lain, lagi mallocing.
>> Sekarang jika Anda ingin memberikan nilai pada sebuah kata, maka kita bisa mengatakan panah node1
kata sama dengan "Hello." Operator panah ini dereferences pointer dan
mengakses variabel struct itu.
Dengan cara ini, kita tidak perlu menggunakan kedua titik dan operator bintang.
>> Jadi saya memiliki kata panah node2 sama "Dunia." Dan di sana, nilai-nilai yang
dihuni pada kelenjar saya.
Untuk membuat link, saya akan lulus dalam node1 panah di sebelah, bahwa bintang mengakses node,
bahwa node pointer, sama node2, menunjuk node1 untuk Node2 dua.
Dan di sana kita memiliki sebuah linked list.
>> Jadi itu hanya satu linked list, tetapi tabel hash adalah seluruh array
terkait daftar.
Nah, kita akan memiliki node yang sama struktur seperti sebelumnya.
Tetapi jika kita ingin tabel hash yang sebenarnya, maka kita hanya bisa membuat pointer simpul
Array di sini.
Sebagai contoh, ukuran 500.
>> Sekarang pemberitahuan, ada akan menjadi perdagangan off antara ukuran Anda
tabel hash dan ukuran daftar Anda terhubung.
Jika Anda memiliki jumlah yang sangat tinggi dari ember, membayangkan harus menjalankan kembali
dan sebagainya dalam antrean untuk menemukan ember Anda.
Tapi Anda juga tidak ingin sejumlah kecil ember, karena dengan begitu kita kembali ke
masalah asli dari bagaimana memiliki terlalu banyak bola di ember kami.
>> OK, tapi mana bola kami pergi?
Yah, pertama-tama kita perlu memiliki bola, kan?
Jadi mari kita malloc node untuk setiap kata baru yang kita miliki.
simpul * new_node equals malloc (sizeof (node)).
>> Sekarang bahwa kita memiliki struktur ini, kita dapat memindai, menggunakan fungsi
fscanf, string dari file kami, jika itu adalah file kamus, ke
new_node panah kata, di mana new_node Kata panah adalah kami
tujuan dari kata itu.
>> Selanjutnya, kita akan ingin hash yang kata dengan menggunakan fungsi hash.
Sebuah fungsi hash mengambil string dan mengembalikan indeks.
Dalam hal ini, indeks harus kurang dari jumlah
ember yang Anda miliki.
>> Sekarang, fungsi hash, ketika Anda mencoba untuk menemukan satu dan menciptakan salah satu
Anda sendiri, ingatlah bahwa mereka harus deterministik.
Itu berarti bahwa nilai yang sama perlu memetakan ke ember yang sama setiap kali
bahwa Anda hash itu.
>> Ini semacam seperti perpustakaan.
Ketika Anda mengambil sebuah buku, yang didasarkan pada Penulis, Anda tahu mana rak seharusnya
terus, apakah itu nomor rak satu, dua, atau tiga.
Dan buku yang akan selalu menjadi milik pada salah satu rak, dua, atau tiga.
>> Jadi, jika new_node panah kata memiliki kata dari kamus Anda, maka
hashing new_node panah kata akan memberi kita indeks dari
ember tabel hash.
Dan kemudian kita akan memasukkan itu ke dalam linked list tertentu ditunjukkan oleh
nilai fungsi hash kami kembali.
>> Mari kita lihat contoh memasukkan node ke dalam
mulai dari linked list.
Jika kepala adalah pointer node yang menunjukkan awal terkait
daftar, dan new_node menunjukkan baru node yang ingin Anda masuk, hanya
menugaskan kepala ke new_node akan kehilangan link ke seluruh daftar.
Jadi kita tidak ingin melakukan ini.
>> Sebaliknya, kita ingin memastikan bahwa kita berpegang pada setiap
node tunggal dalam program kami.
Jadi berjalan new_node panah equals berikutnya kepala dan kemudian kepala sama new_node
akan mempertahankan semua link dan tidak kehilangan apapun.
>> Tetapi bagaimana jika Anda ingin daftar menjadi diurutkan, karena memiliki sebuah diurutkan terkait
Daftar mungkin lebih mudah untuk mencari nanti?
Nah, untuk itu, Anda harus tahu bagaimana untuk melintasi daftar terkait.
>> Untuk melintasi sebuah linked list, mari kita pointer node, node *, untuk bertindak sebagai
kursor Anda, yang menunjukkan Anda berada di simpul, mulai
pada elemen pertama.
Looping hingga kursor adalah null, kita bisa melakukan proses tertentu dan kemudian
memajukan kursor ketika kita perlu menggunakan kursor nilai panah.
>> Ingat, ini adalah hal yang sama seperti mengatakan star kursor, dereferencing
kursor, kemudian menggunakan Nilai dot operator.
Jadi memperbarui kursor dengan menetapkan kursor ke kursor panah berikutnya.
>> Katakanlah Anda menentukan bahwa D menjadi di antara C dan E. Untuk menyisipkan node,
memiliki titik D new_node ke simpul E, yang merupakan kursor berikutnya.
Dan kemudian C, kursor, kemudian arahkan D. Dengan begitu, Anda mempertahankan daftar.
Berhati-hatilah untuk tidak kehilangan link Anda dengan memindahkan kursor panah di samping D
segera.
>> Baik.
Jadi itulah bagaimana Anda dapat menyisipkan node, beban mereka dalam, kata-kata beban ke mereka
node, dan memasukkan mereka ke dalam tabel hash Anda.
Jadi sekarang mari kita lihat mencoba.
>> Dalam trie, setiap node akan mengandung array dari pointer node, satu untuk setiap
huruf dalam alfabet ditambah apostrof.
Dan setiap elemen dalam array akan menunjuk ke node lain.
Jika node yang adalah null, maka surat itu tidak akan menjadi huruf berikutnya
setiap kata secara berurutan, karena setiap kata menunjukkan apakah itu yang terakhir
karakter dari sebuah kata atau tidak.
>> Mari kita lihat diagram.
Mudah-mudahan hal-hal yang akan menjadi sedikit lebih jelas.
Dalam diagram ini, kita melihat bahwa hanya huruf tertentu dan substring tertentu
sedang terdaftar keluar.
Jadi, Anda dapat mengikuti jalur tertentu, dan semua orang jalan akan membawa Anda ke
kata yang berbeda.
>> Jadi bagaimana kita merepresentasikan ini di C?
Nah, setiap simpul sekarang akan memiliki nilai Boolean yang menunjukkan apakah
simpul itu adalah akhir dari kata yang diberikan atau tidak.
Dan kemudian juga akan memiliki sebuah array simpul pointer disebut anak-anak, dan
ada akan menjadi 27 dari mereka.
Dan ingat, Anda juga akan ingin melacak simpul pertama Anda.
Kita akan memanggil akar itu.
>> Jadi itulah struktur trie.
Bagaimana kami mewakili ini sebagai kamus?
Nah, untuk memuat kata-kata dalam, untuk setiap kata kamus, Anda akan ingin
iterate melalui trie.
Dan setiap elemen pada anak sesuai dengan huruf yang berbeda.
>> Jadi memeriksa nilai pada anak-anak Indeks i, di mana saya mewakili
Indeks spesifik surat yang Anda mencoba untuk memasukkan.
Nah, jika itu nol, maka Anda akan ingin malloc node baru dan memiliki anak
i menunjuk ke simpul tersebut.
>> Jika tidak null, maka itu berarti bahwa cabang yang diberikan, yang diberikan
substring, sudah ada.
Jadi Anda hanya akan pindah ke yang node baru dan melanjutkan.
Jika Anda berada di akhir kata yang Anda mencoba untuk memuat dalam
kamus, maka Anda dapat mengatur bahwa node saat ini bahwa Anda berada di true.
>> Jadi mari kita lihat contoh memasukkan kata "fox" ke kami
kamus.
Berpura-pura kita mulai dengan kamus kosong.
Surat pertama, F, akan berlokasi indeks anak lima dari akar
anak array.
Jadi kita memasukkan yang masuk
>> Huruf O kemudian akan pada anak-anak Indeks 15, setelah itu F. Dan kemudian X
akan lebih di bawah itu, bercabang off dari anak-anak O.
Dan kemudian karena X adalah huruf terakhir dari kata "rubah," maka aku akan
warna hijau yang menunjukkan bahwa itu adalah akhir kata.
Dalam C, yang akan menetapkan Is Kata Boolean dengan nilai sebenarnya.
>> Sekarang bagaimana jika kata berikutnya yang Anda loading di adalah kata "foo"?
Nah, Anda tidak perlu malloc lagi ruang untuk F atau O, karena
yang sudah ada.
Tapi O terakhir di foo?
Yang satu itu, Anda harus malloc.
Membuat node baru untuk itu, pengaturan Is Firman Boolean true.
>> Jadi sekarang mari kita masukkan "anjing." Anjing akan mulai dengan indeks tiga dari akar
anak-anak, karena D belum telah dibuat.
Dan kami akan mengikuti proses yang sama seperti sebelumnya, menciptakan anjing substring,
mana yang G berwarna hijau karena itulah akhir dari sebuah kata.
>> Sekarang, bagaimana jika kita ingin memasukkan "melakukan"?
Nah, ini adalah substring dari anjing, sehingga kita tidak perlu malloc lagi.
Tapi kita perlu untuk menunjukkan di mana kita sudah mencapai akhir dari kata itu.
Jadi O akan berwarna hijau.
Melanjutkan proses bahwa untuk setiap satu kata dalam kamus Anda, Anda sudah
dimuat dalam menjadi baik Anda hash table atau trie Anda.
>> speller.c akan lulus dalam string untuk dictionary.c untuk memeriksa mereka.
Sekarang, fungsi Periksa harus beroperasi di bawah kasus ketidakpekaan.
Itu berarti bahwa huruf kapital dan huruf kecil dan campuran keduanya
semua harus sama dengan benar jika ada kombinasi yang ada di
kamus.
Anda juga dapat mengasumsikan bahwa string adalah hanya akan berisi abjad
karakter atau apostrof.
>> Jadi mari kita lihat bagaimana Anda dapat memeriksa dengan struktur tabel hash.
Nah, jika kata itu ada, maka dapat ditemukan dalam tabel hash.
Jadi maka Anda dapat mencoba untuk menemukan bahwa kata dalam ember yang relevan.
>> Jadi yang akan ember kata yang berada di?
Nah, Anda akan mendapatkan nomor, indeks yang ember, dengan hashing kata itu
dan kemudian mencari dalam linked list, melintasi melalui seluruh yang
linked list, menggunakan String Bandingkan fungsi.
>> Jika akhir linked list adalah tercapai, yang berarti bahwa kursor Anda
mencapai nol, maka kata tersebut tidak dapat ditemukan dalam kamus.
Ini tidak akan dalam ember lain.
Jadi di sini, Anda mungkin akan melihat bagaimana mungkin ada menjadi trade-off antara memiliki baik
diurutkan daftar terkait atau yang tidak dipisahkan.
Entah akan mengambil lebih banyak waktu selama memuat atau lebih waktu selama check.
>> Bagaimana mungkin Anda check-in struktur trie?
Kita akan melakukan perjalanan ke bawah dalam trie.
Untuk setiap huruf dalam kata diinput bahwa kita sedang memeriksa, kita akan pergi ke yang
sesuai elemen dalam anak-anak.
>> Jika unsur yang null, maka berarti bahwa bahwa tidak ada substring
mengandung kata masukan kami, jadi kata salah eja.
Jika tidak null, kita bisa pindah ke huruf berikutnya dari kata yang kita
memeriksa dan melanjutkan proses ini sampai kita mencapai akhir
kata input.
Dan kemudian kita dapat memeriksa Apakah jika Firman adalah benar.
Jika ya, maka besar.
Kata benar.
Tapi jika tidak, meskipun substring yang ada dalam trie, kata tersebut
salah eja.
>> Ketika fungsi Ukuran disebut, ukuran harus mengembalikan jumlah kata yang
dalam kamus Anda diberikan struktur data.
Jadi jika Anda menggunakan tabel hash, Anda dapat pergi melalui setiap satu
linked list dalam setiap satu ember menghitung jumlah
kata-kata yang ada.
Jika Anda menggunakan trie, Anda dapat pergi melalui setiap non nol
jalan di trie Anda.
Atau saat Anda sedang memuat kamus dalam, mungkin Anda dapat melacak bagaimana
banyak kata-kata Anda memuat masuk
>> Setelah selesai memeriksa speller.c file teks terhadap kamus, maka
itu dilakukan dan sehingga panggilan Membongkar, di mana tugas Anda adalah untuk membebaskan sesuatu
bahwa Anda telah malloced.
Jadi, jika Anda menggunakan tabel hash, maka Anda harus berhati-hati untuk menghindari
kebocoran memori dengan tidak membebaskan apa-apa prematur dan memegang setiap
link tunggal sebelum Anda gratis.
>> Jadi untuk setiap elemen dalam tabel hash dan untuk setiap node dalam linked list,
Anda akan ingin untuk membebaskan simpul tersebut.
Bagaimana Anda pergi tentang membebaskan linked list?
Mengatur node pointer kursor ke kepala, untuk awal
linked list, maka saat kursor Anda tidak null, Anda dapat mengatur sementara
simpul pointer kursor Anda.
Kemudian memajukan kursor.
Dan kemudian Anda dapat bebas yang sementara nilai sementara masih berpegangan pada
semuanya setelah itu.
>> Bagaimana jika Anda menggunakan trie?
Maka cara terbaik untuk melakukan hal ini adalah untuk membongkar dari sangat
bawah ke atas.
Dengan bepergian ke serendah mungkin node, Anda dapat membebaskan semua pointer di
bahwa anak-anak dan kemudian mundur ke atas, membebaskan semua elemen dalam semua
anak-anak array, sampai anda menekan simpul akar utama Anda.
Di sinilah Rekursi akan berguna.
>> Untuk memastikan bahwa Anda mungkin pernah dibebaskan segala sesuatu yang telah Anda malloced,
Anda dapat menggunakan Valgrind.
Menjalankan Valgrind akan menjalankan program Anda menghitung berapa banyak byte memori
Anda menggunakan dan memastikan bahwa Anda telah membebaskan mereka semua, memberitahu Anda
di mana Anda mungkin memiliki lupa gratis.
Jadi menjalankan itu dan sekali Valgrind memberitahu Anda dan memberi Anda pergi ke depan, kemudian
Anda telah selesai membongkar.
>> Sekarang, beberapa tips sebelum Anda pergi off dan mulai menerapkan Anda
kamus.
Saya akan merekomendasikan untuk lulus dalam lebih kecil kamus ketika Anda mencoba untuk menguji
hal-hal dan debugging dengan GDP.
Penggunaan ejaan adalah. / Ejaan, sebuah kamus opsional, dan kemudian teks.
>> Secara default, itu beban di kamus besar.
Jadi, Anda mungkin ingin lulus dalam kecil kamus, atau mungkin bahkan membuat Anda
sendiri, menyesuaikan kamus Anda dan file teks Anda.
>> Dan akhirnya, saya akan juga merekomendasikan untuk mengambil pena dan kertas dan menarik
hal-hal sebelum, selama, dan setelah Anda telah menulis semua kode Anda.
Pastikan bahwa Anda punya mereka pointer tepat.
>> Saya berharap yang terbaik keberuntungan.
Dan setelah Anda selesai, jika Anda ingin untuk menantang papan besar dan
melihat seberapa cepat program Anda dibandingkan dengan teman sekelas Anda, maka saya mendorong
Anda memeriksa yang keluar.
>> Dengan itu, Anda telah selesai yang PSet ejaan.
Nama saya adalah Zamyla, dan ini adalah CS50.