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.