>> SPEAKER 1: 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 Word dan bintang simpul Struct
Anak-anak braket alfabet.
Sehingga hal pertama yang Anda mungkin bertanya-tanya, mengapa hash alfabet didefinisikan sebagai 27?
Nah, ingat bahwa kita akan membutuhkan untuk menangani tanda kutip, sehingga
itu akan menjadi agak khusus terjadi di seluruh program ini.
>> OK, sekarang, ingat bagaimana Trie benar-benar bekerja.
Katakanlah kita mengindeks kucing kata, kemudian dari akar Trie kami,
kita akan melihat Anak array, dan kita akan melihat
Indeks yang sesuai dengan surat C. Sehingga akan menjadi indeks kedua.
Jadi mengingat bahwa, yang akan memberi kita node baru, dan kemudian kita akan
bekerja dari simpul tersebut.
>> Jadi mengingat simpul tersebut, kami sekali lagi akan melihat Anak array,
dan kita akan melihat indeks nol untuk sesuai dengan A pada kucing.
Jadi kita akan pergi ke simpul tersebut, dan mengingat simpul tersebut, kita akan
untuk melihat indeks yang sesuai T. Dan pindah ke simpul tersebut,
akhirnya, kita telah benar-benar melihat melalui Cat kata kami, dan sekarang Bool
Kata yang seharusnya untuk menunjukkan apakah kata ini diberikan sebenarnya kata.
>> Jadi mengapa kita perlu bahwa kasus khusus?
Nah, bagaimana jika kata bencana adalah dalam kamus kami, tapi
kucing kata tidak?
Jadi dalam mencari untuk melihat apakah kucing kata adalah dalam kamus kami, kita akan
berhasil melihat melalui indeks C-A-T dan mencapai node, tapi itu
hanya karena bencana yang terjadi pada membuat node dalam perjalanan dari C-A-T semua
jalan ke akhir kata.
Jadi Bool Word digunakan mengindikasikan apakah lokasi tertentu ini benar-benar
menunjukkan sebuah kata.
>> Baiklah, jadi sekarang kita tahu apa Trie akan terlihat seperti, mari kita lihat
pada fungsi Load.
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 akan lakukan adalah membuka up yang kamus untuk membaca.
Kita harus memastikan bahwa kita tidak gagal, jadi jika kamus itu tidak
berhasil dibuka, maka akan kembali Tidak, dalam hal ini kita akan
kembali False.
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 bintang simpul.
Ini adalah puncak Trie kami bahwa kita akan iterasi melalui.
Sehingga hal pertama kita akan ingin lakukan adalah mengalokasikan memori untuk akar kami.
>> Perhatikan bahwa kita menggunakan calloc 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
simpul dan pastikan bahwa mereka semua null.
Jadi calloc akan melakukannya untuk kita.
>> Sekarang, seperti malloc, kita perlu membuat memastikan bahwa alokasi sebenarnya
sukses.
Jika hal ini kembali null, maka kita harus menutup kamus kami
mengajukan dan kembali False.
Jadi dengan asumsi alokasi itu sukses, kita akan menggunakan node
membintangi kursor iterate melalui Trie kami.
Jadi akar kami tidak akan pernah berubah, tapi kita akan menggunakan kursor ke
benar-benar pergi dari node ke node.
>> Baiklah, jadi dalam hal ini Untuk lingkaran, kita membaca file kamus,
dan kita gunakan di fgetc.
Jadi fgetc akan ambil satu karakter dari file tersebut.
Kami akan terus meraih karakter sementara kita tidak mencapai
akhir file, jadi ada dua kasus yang kita butuhkan untuk menangani.
Yang pertama, jika karakter bukan baris baru, jadi kita tahu apakah itu baru
line, maka kita akan pindah ke sebuah kata baru.
Tapi asumsi itu bukan baris baru, kemudian di sini, kami ingin mengetahui
indeks kita akan indeks ke Anak-anak di array
kami melihat sebelumnya.
>> Jadi seperti saya katakan sebelumnya, kita perlu kasus khusus tanda kutip.
Perhatikan kita sedang menggunakan operator terner di sini, jadi kita akan membaca
ini seolah-olah karakter yang kita baca dalam adalah apostrof, maka kita akan
Set index sama dengan alfabet dikurangi 1, yang akan menjadi indeks 26.
Lain, jika bukan apostrof, maka kita akan mengatur indeks
sama dengan c minus.
Jadi ingat kembali dari p set sebelumnya, c minus akan memberi kita
Posisi abjad dari c, jadi jika c adalah huruf A, ini akan
memberi kita indeks nol.
Untuk huruf B, itu akan memberikan kami indeks 1, dan seterusnya.
>> Jadi ini memberi kita indeks ke dalam Anak-anak Array yang kita inginkan.
Sekarang, jika indeks ini saat ini nol di Anak array, yang berarti bahwa
node saat ini tidak ada dari jalan itu, jadi kita perlu mengalokasikan
simpul untuk jalan itu.
Itulah yang kami lakukan di sini.
Jadi kita akan, sekali lagi, gunakan calloc fungsi sehingga kita tidak memiliki
untuk nol semua pointer, dan kami, lagi, perlu memeriksa calloc yang
tidak gagal.
Jika calloc tidak gagal, maka kita perlu untuk membongkar semuanya, tutup kami
kamus, dan kembali False.
>> 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 untuk mengalokasikan kucing kata, dan
itu berarti ketika kita pergi untuk mengalokasikan bencana, kita tidak perlu membuat
node untuk C-A-T lagi.
Mereka sudah ada.
>> OK, jadi apa Lagi ini?
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 ingin kita lakukan ketika kita berhasil menyelesaikan sebuah kata?
Kita akan menggunakan kolom kata ini dalam simpul Struct 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 untuk awal Trie lagi.
Dan akhirnya, kenaikan kamus kami ukuran karena kita menemukan kata lain.
>> Baiklah, jadi kita akan terus melakukan itu, membaca karakter dengan
karakter, membangun node baru Trie kami dan untuk setiap kata dalam
kamus, sampai kami akhirnya mencapai c sama dengan EOF, dalam hal ini, kita istirahat
dari file.
Sekarang, ada dua kasus di bawah yang kita mungkin telah memukul EOF.
Yang pertama adalah jika ada kesalahan membaca dari file tersebut, jadi jika ada
kesalahan, yang perlu kita lakukan khas membongkar semuanya, tutup file,
kembali False.
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
berhasil dimuat kamus Trie ke kami.
>> Baiklah, jadi sekarang mari kita memeriksa tarif.
Melihat fungsi Periksa, kita melihat Periksa bahwa akan mengembalikan Bool.
Ia mengembalikan Benar jika kata ini bahwa itu yang lulus di Trie kami.
Ia mengembalikan False sebaliknya.
>> Jadi bagaimana kita akan menentukan apakah kata ini adalah di 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 berlalu, kita akan menentukan
indeks ke dalam array Anak-anak sesuai dengan kata braket i.
Jadi ini akan terlihat persis seperti Load, di mana jika kata braket i adalah
apostrof, maka kita ingin menggunakan indeks alfabet dikurangi 1 karena kita ditentukan
itu adalah di mana kita akan untuk menyimpan apostrof.
>> Lain kita akan menggunakan tolower kata braket i.
Jadi ingat kata yang dapat memiliki sewenang-wenang kapitalisasi, dan jadi kita
ingin memastikan bahwa kita menggunakan versi huruf kecil hal.
Dan kemudian kurangi dari huruf kecil yang untuk, sekali lagi, memberi kita
Posisi abjad karakter itu.
Sehingga akan menjadi indeks kami Anak-anak ke dalam array.
>> Dan sekarang, jika indeks ke 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
yang, itu berarti akan ada path ke kata itu, dan Anda akan
pernah mengalami null.
Jadi menghadapi null, kita kembali False.
Kata tersebut tidak ada dalam kamus.
Jika bukan nol, maka kita akan terus iterasi, jadi kita akan
untuk memperbarui kursor untuk menunjuk ke node tertentu pada indeks itu.
>> Jadi kita terus melakukan itu sepanjang seluruh kata.
Dengan asumsi kita tidak pernah memukul null, artinya kami mampu melewati seluruh yang
dunia dan menemukan simpul di Trie kami, tapi kami tidak cukup dilakukan belum.
Kami tidak ingin hanya kembali Benar.
Kami ingin kembali kursor kata kesalahan karena, ingat lagi, jika kucing tidak
dalam kamus dan bencana kita, maka kita akan berhasil melewati
kucing kata, tapi kata kursor 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 periksa Size.
Jadi Ukuran akan menjadi cukup mudah karena, ingat di Load, kami
incrementing ukuran kamus untuk setiap kata yang kita hadapi.
Jadi Ukuran hanya akan kembali ukuran kamus, dan hanya itu.
>> Baiklah, jadi yang terakhir, kita memiliki Unload.
Jadi Membongkar, kita akan menggunakan fungsi rekursif untuk benar-benar melakukan semua
pekerjaan bagi kita, jadi fungsi kita akan disebut Unloader.
Apa yang Unloader lakukan?
Kita lihat di sini Unloader yang akan iterate atas semua anak-anak di
simpul tertentu, dan jika anak node tidak null, maka kita akan
membongkar node anak.
>> Jadi ini akan secara rekursif membongkar semua anak-anak kita.
Setelah kami yakin bahwa semua anak-anak kita telah dibongkar, maka kita
dapat membebaskan diri, sehingga membongkar diri.
Jadi ini secara rekursif akan membongkar seluruh Trie, dan kemudian sekali itu
dilakukan, 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 [Tak terdengar].