[MUSIC PLAYING] 

ROB Bowden: Hi. Aku Rob. Dan mari kita solusi ini. Jadi di sini kita akan mengimplementasikan meja umum. Kita melihat bahwa struct node kami tabel akan terlihat seperti ini. Jadi itu akan memiliki kata arang array ukuran PANJANG + 1. Jangan lupa + 1, karena maksimum kata dalam kamus adalah 45 karakter. Dan kemudian kita akan membutuhkan satu tambahan karakter untuk nol backslash. 

Dan kemudian hashtable kami di setiap ember akan menyimpan linked list node. Kami tidak melakukan linear menyelidik sini. Dan dalam rangka untuk menghubungkan ke depan elemen dalam ember, kita perlu struct simpul * berikutnya. OK. Jadi itulah yang simpul yang tampak seperti. 

Sekarang di sini adalah deklarasi dari hashtable kami. Ini akan memiliki 16.834 ember. Namun jumlah itu tidak terlalu penting. Dan akhirnya, kita akan memiliki ukuran hashtable variabel global, yang akan memulai sebagai nol. Dan itu akan melacak bagaimana banyak kata yang ada dalam kamus kami. 

Jadi mari kita lihat pada beban. Perhatikan beban itu, ia mengembalikan bool. Anda mengembalikan true jika itu berhasil dimuat, dan false jika tidak. Dan dibutuhkan const char * kamus, yang merupakan kamus bahwa kita ingin membuka. Jadi itulah hal pertama kita akan lakukan. 

Kita akan fopen yang kamus untuk membaca. Dan kita akan harus membuat yakin bahwa itu berhasil. Jadi, jika itu kembali NULL, maka kita tidak berhasil membuka kamus. Dan kita perlu kembali palsu. Tetapi dengan asumsi bahwa hal itu berhasil terbuka, maka kita ingin membaca kamus. Jadi terus looping sampai kita menemukan beberapa alasan untuk keluar dari lingkaran ini, yang akan kita lihat. Jadi terus perulangan. 

Dan sekarang kita akan malloc node tunggal. Dan tentu saja kita perlu untuk udara periksa lagi. Jadi jika mallocing tidak berhasil, maka kita ingin membongkar setiap node yang kita terjadi pada malloc sebelumnya, tutup kamus dan kembali palsu. Tetapi mengabaikan itu, dengan asumsi kita berhasil, maka kita ingin menggunakan fscanf untuk membaca satu kata dari kami kamus ke simpul kami. Jadi ingat bahwa catatan> kata adalah char penyangga kata ukuran lenghth + 1 bahwa kita akan menyimpan kata masuk 

Jadi fscanf akan kembali 1, selama seperti itu berhasil membaca sebuah kata dari file tersebut. Jika terjadi kesalahan yang terjadi, atau kita mencapai akhir dari file tersebut, ia tidak akan kembali 1. Dalam hal ini tidak kembali 1, kita akhirnya akan keluar dari ini loop sementara. Jadi kita melihat bahwa sekali kita telah berhasil membaca sebuah kata ke dalam catatan> kata, maka kita akan bahwa kata menggunakan fungsi hash kami. 

Mari kita lihat fungsi hash. Jadi Anda tidak benar-benar perlu untuk memahami ini. Dan sebenarnya kami hanya menarik hash ini fungsi dari internet. Satu-satunya hal yang perlu Anda mengenali adalah bahwa ini mengambil char * const kata. Jadi itu mengambil string sebagai masukan, dan kembali sebuah int unsigned sebagai output. Jadi itu semua fungsi hash adalah, apakah mengambil dalam masukan dan memberi Anda indeks ke hashtable. 

Perhatikan bahwa kita moding oleh NUM_BUCKETS, sehingga nilai yang dikembalikan sebenarnya adalah indeks ke hashtable dan tidak indeks luar batas-batas array. Jadi mengingat fungsi itu, kita akan hash kata yang kita membaca kamus. Dan kemudian kita akan menggunakan bahwa hash untuk memasukkan masuk ke hashtable. 

Hash Sekarang hashtable adalah arus linked list dalam tabel. Dan itu sangat mungkin bahwa itu hanya NULL. Kami ingin memasukkan entri kami di awal linked list ini. Dan jadi kita akan memiliki saat kami entry point untuk apa hashtable saat ini menunjuk ke. Dan kemudian kita akan menyimpan, dalam hashtable di hash, entry ini. Jadi dua baris ini berhasil memasukkan entri pada awal linked list pada indeks yang di hashtable. 

Setelah kami selesai dengan itu, kita tahu bahwa kita menemukan kata lain dalam kamus, dan kami kenaikan lagi. Jadi kita terus melakukan itu sampai fscanf akhirnya kembali sesuatu yang non-1 di mana titik ingat bahwa kita perlu membebaskan entri. Jadi di sini kita malloced entri. Dan kami mencoba untuk membaca sesuatu dari kamus. Dan kami tidak berhasil membaca sesuatu dari kamus, dalam hal ini kita perlu membebaskan entri bahwa kita tidak pernah benar-benar dimasukkan ke dalam hashtable, dan akhirnya pecah. 

Setelah kami keluar kita perlu melihat, baik, Apakah kita keluar karena ada adalah kesalahan membaca dari file? Atau apakah kita keluar karena kita mencapai akhir file? Jika ada kesalahan, maka kita ingin kembali palsu. Karena beban tidak berhasil. Dan dalam proses kita ingin membongkar semua kata-kata yang kita baca dalam, dan menutup file kamus. 

Dengan asumsi kita tidak berhasil, maka kita hanya masih perlu menutup kamus mengajukan, dan akhirnya kembali benar karena kita berhasil dimuat kamus. Dan itu saja untuk beban. Jadi sekarang memeriksa, diberi hashtable dimuat, akan terlihat seperti ini. Jadi periksa, ia mengembalikan bool, yang akan menunjukkan apakah lulus di char * kata, apakah lulus dalam string adalah dalam kamus kami. Jadi jika berada dalam kamus, jika berada dalam hashtable kami, kami akan kembali benar. Dan jika tidak, kami akan kembali palsu. 

Mengingat ini berlalu dalam kata, kami akan hash kata. Sekarang hal yang penting untuk mengenali adalah bahwa beban kita tahu bahwa semua kata-kata kita akan menjadi huruf kecil. Tapi di sini kita tidak begitu yakin. Jika kita melihat pada fungsi hash kami, Fungsi hash kami benar-benar adalah casing yang lebih rendah masing-masing karakter kata. Jadi terlepas dari kapitalisasi kata, fungsi hash kami adalah kembalinya indeks yang sama untuk apa pun kapitalisasi adalah, karena akan memiliki kembali untuk benar-benar huruf kecil versi kata. Baiklah. Itu indeks kami adalah ke Hashtable untuk kata ini. 

Sekarang ini untuk loop akan iterate atas daftar link yang pada indeks itu. Jadi perhatikan kita menginisialisasi entri untuk menunjuk ke indeks. Kami akan terus sementara masuk! = NULL. Dan ingat bahwa memperbarui pointer dalam daftar kami masuk linked = entry> berikutnya. Jadi kami memiliki titik masuk saat ini untuk item berikutnya dalam linked list. 

Jadi untuk setiap entri dalam linked list, kita akan menggunakan strcasecmp. Ini bukan StrComp. Karena sekali lagi, kita ingin melakukan hal-hal kasus insensitively. Jadi kita menggunakan strcasecmp untuk membandingkan kata yang melewati ini fungsi terhadap kata yang ada di entri ini. Jika kembali nol, yang berarti ada pertandingan, dalam hal ini kita ingin kembali benar. Kami berhasil menemukan kata dalam hashtable kami. 

Jika tidak ada pertandingan, maka kita akan loop lagi dan melihat entri berikutnya. Dan kami akan terus looping sementara ada entri dalam daftar link ini. Apa yang terjadi jika kita istirahat keluar dari ini untuk loop? Itu berarti kita tidak menemukan entri yang cocok kata ini, dalam hal ini kita kembali palsu untuk menunjukkan bahwa kami hashtable tidak mengandung kata ini. Dan itu cek. 

Jadi mari kita lihat ukuran. Ukuran Sekarang akan menjadi sangat sederhana. Sejak ingat beban, untuk setiap kata kami menemukan, kami bertambah global ukuran hashtable variabel. Jadi fungsi ukuran hanya akan untuk kembali variabel global. Dan itu saja. 

Sekarang akhirnya, kita perlu membongkar kamus setelah semuanya selesai. Jadi bagaimana yang akan kita melakukan itu? Di sini kita mengulang terus semua ember meja kami. Jadi ada NUM_BUCKETS ember. Dan untuk setiap linked list di kami hashtable, kita akan loop atas keseluruhan dari linked list, membebaskan setiap elemen. 

Sekarang kita perlu berhati-hati. Jadi di sini kita memiliki variabel sementara yang menyimpan pointer ke depan elemen dalam linked list. Dan kemudian kita akan bebas elemen saat ini. Kita perlu memastikan bahwa kita melakukan ini karena kita tidak bisa hanya membebaskan elemen saat ini dan kemudian mencoba untuk mengakses pointer berikutnya, karena sekali kita sudah dibebaskan itu, memori menjadi tidak valid. 

Jadi kita perlu menjaga sekitar pointer ke elemen berikutnya, maka kita dapat membebaskan elemen saat ini, dan kemudian kita dapat memperbarui elemen kami saat ini untuk menunjuk ke elemen berikutnya. Kami akan loop sementara ada unsur dalam linked list ini. Kami akan melakukannya untuk semua terkait daftar di hashtable. Dan setelah kami selesai dengan itu, kita sudah benar-benar dibongkar hashtable, dan kita sudah selesai. Jadi tidak mungkin untuk membongkar pernah kembali palsu. Dan ketika kita sudah selesai, kita hanya kembali benar. 

Mari kita beri solusi ini mencoba. Jadi mari kita lihat apa yang kami struct node akan terlihat seperti. Di sini kita melihat kita akan memiliki bool kata dan struct simpul * anak braket ALPHABET. Jadi hal pertama yang Anda mungkin tanya, mengapa ALPHABET ed didefinisikan sebagai 27? Nah, ingat bahwa kita akan membutuhkan untuk menangani tanda kutip. Sehingga akan menjadi sedikit dari kasus khusus seluruh program ini. 

Sekarang ingat bagaimana trie benar-benar bekerja. Katakanlah kita pengindeksan kata "Kucing." Kemudian dari akar trie, kita akan melihat anak-anak array, dan kita akan melihat Indeks yang sesuai dengan surat C. Sehingga akan diindeks 2. Jadi mengingat bahwa, kehendak yang memberi kita sebuah node baru. Dan kemudian kita akan bekerja dari simpul tersebut. 

Jadi mengingat simpul tersebut, kami sekali lagi akan melihat anak-anak array. Dan kita akan melihat indeks nol untuk sesuai dengan A pada kucing. Jadi kita akan pergi ke simpul tersebut, dan mengingat simpul bahwa kita akan untuk melihat akhir itu berkorespondensi T. Dan pindah ke simpul tersebut, akhirnya, kita telah benar-benar melihat melalui kata kita "kucing." Dan sekarang bool kata yang seharusnya untuk menunjukkan apakah kata ini diberikan sebenarnya kata. 

Jadi mengapa kita perlu bahwa kasus khusus? Nah apa kata "bencana" adalah dalam kamus kami, tetapi Kata "kucing" yang tidak? Jadi dan mencari untuk melihat apakah kata "kucing" adalah dalam kamus kami, kami akan berhasil melihat melalui indeks C-A-T di wilayah simpul. Tapi itu hanya karena bencana terjadi untuk membuat node di jalan dari C-A-T, semua cara untuk akhir kata. Jadi kata bool digunakan untuk mengindikasikan apakah lokasi tertentu ini benar-benar menunjukkan sebuah kata. 

Baik. Jadi sekarang kita tahu apa itu trie adalah akan terlihat seperti, mari kita lihat pada memuat fungsi. Jadi beban akan kembali bool untuk apakah kita berhasil atau berhasil dimuat kamus. Dan ini akan menjadi kamus bahwa kita ingin memuat. 

Sehingga hal pertama kita lakukan adalah membuka up yang kamus untuk membaca. Dan kami harus memastikan kami tidak gagal. Jadi jika kamus itu tidak berhasil dibuka, maka akan kembali null, dalam hal ini kita akan kembali palsu. Tetapi dengan asumsi bahwa hal itu berhasil dibuka, maka kita benar-benar bisa membaca melalui kamus. 

Sehingga hal pertama kita akan ingin lakukan adalah kita memiliki ini akar variabel global. Sekarang akar akan menjadi node *. Ini adalah atas trie kami bahwa kita akan iterasi melalui. Jadi hal pertama yang kita akan ingin lakukan adalah mengalokasikan memori untuk akar kami. Perhatikan bahwa kita menggunakan calloc yang fungsi, yang pada dasarnya adalah sama sebagai fungsi malloc, kecuali itu dijamin untuk kembali sesuatu yang benar-benar memusatkan perhatian keluar. Jadi jika kita menggunakan malloc, kita perlu pergi melalui semua pointer di kami node, dan pastikan bahwa mereka semua null. Jadi calloc akan melakukannya untuk kita. 

Sekarang seperti malloc, kita perlu membuat memastikan bahwa alokasi itu sebenarnya sukses. Jika hal ini kembali null, maka kita harus menutup atau kamus mengajukan dan kembali palsu. Jadi dengan asumsi alokasi yang sukses, kita akan menggunakan node * kursor untuk iterate melalui trie kami. Jadi akar kita tidak akan pernah berubah, tapi kita akan menggunakan kursor ke benar-benar pergi dari node ke node. 

Jadi dalam hal ini untuk loop kita membaca melalui file kamus. Dan kita menggunakan fgetc. Fgetc akan ambil satu karakter dari file tersebut. Kami akan terus meraih karakter sementara kita tidak mencapai akhir file. 

Ada dua kasus yang kita butuhkan untuk menangani. Yang pertama, jika karakter bukan baris baru. Jadi kita tahu apakah itu baris baru, kemudian kami akan pindah ke sebuah kata baru. Tapi asumsi itu bukan baris baru, kemudian di sini kita ingin mengetahui indeks kita akan indeks ke pada anak-anak array kami melihat sebelumnya. 

Jadi, seperti saya katakan sebelumnya, kita perlu kasus khusus tanda kutip. Perhatikan kita sedang menggunakan terner tersebut Operator di sini. Jadi kita akan membaca ini sebagai, jika karakter yang kita baca dalam adalah apostrof, maka kita akan mengatur index = "ALPHABET" -1, yang akan menjadi indeks 26. 

Lain, jika bukan apostrof, ada kita akan mengatur indeks sama dengan c - a. Jadi ingat kembali dari sebelumnya p-set, c - a akan memberi kita Posisi abjad dari C. Jadi jika C adalah huruf A, ini akan memberi kita indeks nol. Untuk huruf B, akan memberikan kami indeks 1, dan seterusnya. 

Jadi ini memberi kita indeks ke dalam anak Array yang kita inginkan. Sekarang jika indeks ini saat ini nol di anak-anak, itu berarti bahwa node saat ini tidak ada dari jalan itu. Jadi kita perlu mengalokasikan node untuk jalan itu. Itulah yang akan kita lakukan di sini. 

Jadi kita akan lagi menggunakan calloc yang fungsi, sehingga kita tidak perlu nol semua pointer. Dan kita lagi perlu memeriksa calloc yang tidak gagal. Jika calloc tidak gagal, maka kita perlu untuk membongkar semuanya, tutup kami kamus, dan kembali palsu. Jadi dengan asumsi bahwa itu tidak gagal, maka ini akan membuat anak yang baru bagi kita. Dan kemudian kami akan pergi ke anak itu. Kursor kita akan iterate turun ke anak itu. 

Sekarang jika ini tidak nol untuk memulai dengan, maka kursor hanya dapat iterate turun ke anak itu tanpa benar-benar harus mengalokasikan apa-apa. Ini adalah kasus di mana kami pertama kali terjadi mengalokasikan kata "kucing." Dan itu berarti ketika kita pergi untuk mengalokasikan "Bencana," kita tidak perlu membuat node untuk C-A-T lagi. Mereka sudah ada. 

Apa ini lagi? Ini adalah kondisi di mana c adalah backslash n, di mana c adalah baris baru. Ini berarti bahwa kita telah berhasil menyelesaikan kata. Sekarang apa yang kita ingin lakukan ketika kita berhasil menyelesaikan sebuah kata? Kita akan menggunakan kolom kata ini dalam struct simpul kami. Kami ingin menetapkan bahwa untuk benar. Sehingga menunjukkan bahwa node ini menunjukkan sukses kata, kata yang sebenarnya. 

Sekarang menetapkan bahwa untuk benar. Kami ingin me-reset kursor kita ke titik ke awal trie lagi. Dan akhirnya, kenaikan kamus kami ukuran, karena kita menemukan pekerjaan lain. Jadi kita akan terus melakukan itu, membaca karakter demi karakter, membangun node baru dalam trie kami dan untuk setiap kata dalam kamus, sampai kami akhirnya mencapai C! = EOF, di mana jika kita keluar dari file. 

Sekarang ada dua kasus di bawah yang kita mungkin telah memukul EOF. Yang pertama adalah jika ada kesalahan membaca dari file. Jadi, jika ada kesalahan, kami perlu melakukan khas. Membongkar segala sesuatu, dekat file, kembali palsu. Dengan asumsi tidak ada kesalahan, yang hanya berarti kita benar-benar memukul akhir file, dalam hal ini, kita menutup mengajukan dan kembali benar karena kita kamus berhasil dimuat trie ke kami. 

Jadi sekarang mari kita periksa cek. Melihat fungsi cek, kita melihat bahwa cek akan kembali bool. Ia mengembalikan true jika kata ini bahwa itu yang lulus dalam trie kami. Ia mengembalikan false jika tidak. Jadi bagaimana Anda menentukan apakah kata ini dalam trie kita? 

Kita lihat di sini bahwa, sama seperti sebelumnya, kita akan menggunakan kursor untuk iterate melalui trie kami. Sekarang di sini kita akan iterate atas seluruh kata kita. Jadi iterasi kata kita di masa lalu, kita akan menentukan indeks ke anak-anak array sesuai dengan kata braket I. Jadi ini akan terlihat persis seperti beban, di mana jika kata [i] adalah apostrof, maka kita ingin menggunakan indeks "ALPHABET" - 1. Karena kita menetapkan bahwa yang adalah di mana kita akan menyimpan apostrof. 

Lain kita akan menggunakan dua kata yang lebih rendah braket I. Jadi ingat kata yang dapat memiliki kapitalisasi sewenang-wenang. Dan jadi kami ingin memastikan bahwa kita menggunakan versi huruf kecil hal. Dan kemudian kurangi dari yang 'a' untuk sekali lagi memberi kita abjad yang posisi karakter itu. Sehingga akan menjadi indeks kami ke anak array. 

Dan jika itu indeks ke anak-anak array nol, itu berarti kita tidak bisa lagi melanjutkan iterasi trie bawah kami. Jika itu yang terjadi, kata ini tidak bisa mungkin berada dalam trie kami. Karena jika itu, yang akan berarti akan ada jalan ke kata itu. Dan Anda tidak akan menemukan nol. Jadi menghadapi null, kita kembali palsu. Kata tersebut tidak ada dalam kamus. Jika bukan nol, maka kita akan terus iterasi. 

Jadi kita akan luar sana kursor untuk menunjuk ke yang khusus simpul pada indeks itu. Kami terus melakukan itu sepanjang seluruh kata, dengan asumsi kita tidak pernah memukul null. Itu berarti kami mampu melewati seluruh kata dan menemukan node dalam try kami. Tapi kami tidak cukup dilakukan belum. 

Kami tidak ingin hanya kembali benar. Kami ingin kembali kursor> kata. Sejak ingat lagi, adalah "kucing" tidak dalam kamus kami, dan "bencana" adalah, maka kita akan berhasil kita mendapatkan melalui kata "kucing." Tapi kursor kata akan palsu dan tidak benar. Jadi kita kembali kata kursor untuk menunjukkan apakah simpul ini sebenarnya sebuah kata. Dan itu saja untuk cek. 

Jadi mari kita memeriksa ukuran. Jadi ukuran akan menjadi cukup mudah karena, mengingat beban, kami incrementing ukuran kamus untuk setiap kata yang kita hadapi. Jadi ukuran hanya akan kembali ukuran kamus. Dan itu saja. 

Jadi akhirnya kami telah membongkar. Jadi membongkar, kita akan menggunakan fungsi rekursif untuk benar-benar melakukan semua pekerjaan bagi kita. Jadi fungsi kita akan dipanggil unloader. Apa yang unloader akan lakukan? Kita lihat di sini unloader yang akan iterate atas semua anak-anak di simpul tertentu. Dan jika node anak tidak null, maka kita akan membongkar node anak. 

Jadi ini adalah Anda rekursif membongkar semua anak-anak kita. Setelah kami yakin bahwa semua anak-anak kita telah dibongkar, maka kita dapat membebaskan diri, sehingga membongkar diri kita sendiri. Ini akan bekerja secara rekursif membongkar seluruh trie. Dan kemudian setelah itu selesai, kita hanya bisa kembali benar. Membongkar tidak bisa gagal. Kami hanya membebaskan hal. Jadi setelah kami selesai membebaskan semuanya, kembali benar. Dan itu saja. Nama saya Rob. Dan ini adalah ejaan. 

[MUSIC PLAYING]