[MUZIK Bermain] 

ROB Bowden: Hi. Saya Rob. Dan mari kita penyelesaian ini keluar. Jadi di sini kita akan melaksanakan jadual umum. Kita lihat bahawa nod struct yang kami jadual akan kelihatan seperti ini. Jadi ia akan mempunyai perkataan char pelbagai saiz PANJANG + 1. Jangan lupa + 1, sejak maksimum perkataan dalam kamus ialah 45 aksara. Dan kemudian kita akan memerlukan satu tambahan watak untuk sifar garis sendeng terbalik itu. 

Dan kemudian hashtable kita dalam setiap baldi akan menyimpan senarai bersambung nod. Kami tidak melakukan linear menyelesaikan sesuatu di sini. Dan sebagainya untuk pautan ke seterusnya elemen dalam baldi, kita memerlukan nod struct * seterusnya. OK. Jadi itulah yang nod kelihatan seperti. 

Sekarang di sini adalah pengakuan yang daripada hashtable kami. Ia akan mempunyai 16.834 baldi. Tetapi jumlah itu tidak benar-benar perkara itu. Dan akhirnya, kita akan mempunyai saiz hashtable pembolehubah global, yang akan bermula sebagai sifar. Dan ia akan menjejaki bagaimana banyak perkataan dalam kamus kami. 

Jadi mari kita lihat beban. Notis beban itu, ia mengembalikan bool a. Anda kembali benar jika ia berjaya dimuatkan, dan palsu sebaliknya. Dan ia mengambil char malar * kamus, yang merupakan kamus yang kita mahu buka. Jadi itu perkara pertama kita akan lakukan. 

Kami akan fopen yang kamus untuk membaca. Dan kita akan perlu membuat memastikan bahawa ia berjaya. Jadi, jika ia kembali NULL, maka kita tidak berjaya membuka kamus. Dan kita perlu kembali palsu. Tetapi menganggap bahawa ia tidak berjaya terbuka, maka kita mahu membaca kamus. Jadi menyimpan menggelung sehingga kita menemui beberapa sebab untuk keluar daripada gelung ini, yang kita akan melihat. Jadi menyimpan menggelung. 

Dan sekarang kita akan malloc nod tunggal. Dan sudah tentu kita perlu untuk memeriksa udara lagi. Jadi jika mallocing tidak berjaya, maka kita mahu memunggah mana-mana nod yang kita berlaku kepada malloc sebelum, tutup kamus dan pulangan palsu. Tetapi mengabaikan itu, kami menganggap berjaya, maka kita mahu menggunakan fscanf untuk membaca satu perkataan pun dari kami kamus ke dalam nod kami. Jadi ingat bahawa kemasukan> perkataan char penampan perkataan saiz LENGHTH + 1 yang kita akan menyimpan perkataan masuk 

Jadi fscanf akan kembali 1, selagi kerana ia mampu berjaya membaca perkataan dari fail. Jika sama ada kesilapan berlaku, atau kita sampai ke akhir fail tersebut, ia tidak akan kembali 1. Di mana ia tidak kembali 1, kita akhirnya akan keluar daripada ini gelung sementara. Jadi kita lihat bahawa sebaik sahaja kami telah berjaya membaca perkataan ke dalam kemasukan> perkataan, maka kita akan dengan perkataan menggunakan fungsi hash kami. 

Mari kita lihat fungsi hash. Jadi anda tidak benar-benar memerlukan untuk memahami perkara ini. Dan sebenarnya kita hanya ditarik hash ini berfungsi dari internet. Satu-satunya perkara yang anda perlu menyedari adalah bahawa ini mengambil char malar * perkataan. Jadi ia mengambil rentetan sebagai input, dan kembali satu int tidak ditandatangani sebagai output. Jadi itu sahaja fungsi hash adalah, adakah ia mengambil masa dalam input dan memberi anda indeks ke hashtable itu. 

Perhatikan bahawa kita moding oleh NUM_BUCKETS, jadi nilai yang dikembalikan sebenarnya ialah indeks ke hashtable yang dan tidak indeks di luar batas array. Jadi diberikan fungsi itu, kita akan untuk hash perkataan yang kita membaca kamus. Dan kemudian kita akan menggunakan bahawa hash untuk memasukkan masuk ke hashtable itu. 

Hash Sekarang hashtable adalah semasa senarai dikaitkan dalam jadual. Dan ia sangat mungkin bahawa ia hanya NULL. Kami mahu memasukkan kemasukan kami di permulaan senarai ini dikaitkan. Dan dengan itu kita akan perlu semasa kami pintu masuk kepada apa yang hashtable kini menunjuk ke. Dan kemudian kita akan menyimpan, dalam hashtable di hash, masuk semasa. Jadi kedua-dua baris berjaya memasukkan penyertaan di permulaan senarai bersambung pada indeks yang dalam hashtable itu. 

Setelah kami selesai dengan itu, kita tahu yang kami dapati perkataan lain dalam kamus, dan kami kenaikan lagi. Oleh itu, kita terus melakukan sehingga fscanf akhirnya kembali sesuatu bukan 1 pada mana titik ingat bahawa kita perlu untuk membebaskan masuk. Jadi di sini kita malloced entri. Dan kami cuba untuk membaca sesuatu daripada kamus. Dan kita tidak berjaya membaca sesuatu daripada kamus, dalam mana kita perlu untuk membebaskan masuk yang kita tidak benar-benar meletakkan ke dalam hashtable, dan akhirnya pecah. 

Apabila kita keluar kita perlu melihat, baik, yang kita keluar kerana ada telah kesilapan membaca dari fail? Atau adakah kita keluar kerana kita sampai ke penghujung fail? Jika terdapat kesilapan, kita mahu kembali palsu. Kerana beban tidak berjaya. Dan dalam proses itu kita mahu memunggah semua perkataan yang kita baca dalam, dan menutup fail kamus. 

Andai kata kita tidak berjaya, maka kita hanya masih perlu menutup kamus fail, dan akhirnya kembali benar kerana kita berjaya dimuatkan kamus. Dan itu sahaja untuk beban. Jadi sekarang cek, diberi hashtable dimuatkan, akan kelihatan seperti ini. Jadi lihat, ia kembali bool, yang merupakan akan menunjukkan sama ada diluluskan dalam char * perkataan, sama ada diluluskan dalam rentetan di dalam kamus kami. Jadi, jika ia ada di dalam kamus, jika ia di hashtable kami, kita akan kembali benar. Dan jika tidak, kita akan kembali palsu. 

Memandangkan ini diluluskan pada perkataan, kita akan hash perkataan. Sekarang satu perkara yang penting untuk menyedari adalah bahawa dalam beban kami tahu bahawa semua kata-kata kita akan menjadi kes yang lebih rendah. Tetapi di sini kita tidak begitu pasti. Jika kita lihat fungsi hash kami, fungsi hash kita sebenarnya adalah selongsong yang lebih rendah setiap aksara perkataan. Jadi, tanpa mengira permodalan perkataan, fungsi hash kami adalah kembali indeks yang sama untuk apa jua permodalan adalah, kerana ia akan kembali untuk yang sama sekali huruf kecil versi perkataan. Baiklah. Itulah indeks kami adalah ke dalam hashtable untuk perkataan ini. 

Sekarang ini untuk gelung akan melelar ke senarai dikaitkan yang pada indeks itu. Jadi notis kita Memulakan masuk untuk menunjukkan kepada indeks itu. Kami akan terus manakala kemasukan! = NULL. Dan ingat bahawa mengemaskini penuding dalam kemasukan kami dikaitkan senarai = entry> seterusnya. Jadi mempunyai pintu masuk semasa kami untuk item seterusnya dalam senarai yang dipautkan. 

Jadi bagi setiap penyertaan dalam senarai yang dihubungkan, kita akan menggunakan strcasecmp. Ia bukan strcomp. Kerana sekali lagi, kita mahu melakukan perkara-perkara kes insensitively. Oleh itu, kita menggunakan strcasecmp untuk membandingkan perkataan yang telah diluluskan melalui ini fungsi terhadap perkataan yang ada di entri ini. Jika ia kembali sifar, ini bermakna terdapat perlawanan, di mana kita mahu kembali benar. Kami berjaya menemui perkataan dalam hashtable kami. 

Jika tidak ada perlawanan, maka kami akan gelung lagi dan melihat kemasukan yang berikutnya. Dan kami akan terus gelung sementara ada entri di senarai ini dikaitkan. Apakah yang akan berlaku jika kita memecahkan daripada ini untuk gelung? Ini bermakna kita tidak mencari penyertaan yang dipadankan perkataan ini, di mana kita kembali palsu untuk menunjukkan bahawa kami hashtable tidak mengandungi perkataan ini. Dan itu cek. 

Jadi mari kita lihat pada saiz. Saiz sekarang akan menjadi agak mudah. Sejak ingat dalam beban bagi setiap perkataan kami dapati, kita incremented global saiz hashtable berubah-ubah. Jadi fungsi saiz hanya akan untuk kembali berubah-ubah global. Dan itu sahaja. 

Kini akhirnya, kita perlu memunggah kamus sekali semuanya dilakukan. Jadi bagaimana kita boleh berbuat demikian? Di sini kami menggelung lebih semua baldi meja kami. Jadi, terdapat NUM_BUCKETS baldi. Dan bagi setiap senarai dikaitkan dalam kami hashtable, kita akan lebih gelung keseluruhan daripada senarai yang dihubungkan, membebaskan setiap elemen. 

Sekarang kita perlu berhati-hati. Jadi di sini kita mempunyai pembolehubah sementara yang yang menyimpan penunjuk ke depan elemen dalam senarai berkaitan. Dan kemudian kita akan bebas elemen semasa. Kita perlu pastikan kita melakukan ini kerana kita tidak boleh hanya membebaskan elemen semasa dan kemudian cuba untuk mengakses penunjuk akan datang, sejak setelah kami dibebaskan ia, memori menjadi tidak sah. 

Oleh itu, kita perlu menjaga seluruh penunjuk kepada elemen yang akan datang, maka kita boleh membebaskan elemen semasa, dan kemudian kita boleh mengemas kini elemen semasa kami untuk menunjukkan elemen seterusnya. Kami akan gelung manakala terdapat unsur-unsur dalam senarai ini dikaitkan. Kami akan melakukannya untuk semua berkait senarai di hashtable itu. Dan sebaik sahaja kami selesai dengan itu, kita kena sepenuhnya dipunggah hashtable, dan kita selesai. Jadi ia adalah mustahil untuk memunggah yang pernah pulangan palsu. Dan apabila kita selesai, kita hanya kembali benar. 

Mari kita memberi penyelesaian ini cuba. Jadi mari kita lihat apa yang kami nod struct akan kelihatan seperti. Di sini kita lihat kita akan mempunyai satu bool perkataan dan nod struct * kanak-kanak kurungan abjad. Jadi perkara pertama yang anda mungkin tertanya-tanya, mengapa abjad ed ditakrifkan sebagai 27? Nah, ingat bahawa kita akan perlu yang akan mengendalikan koma atas itu. Supaya akan menjadi sebahagian dari kes khas sepanjang program ini. 

Sekarang ingat bagaimana indone yang sebenarnya berfungsi. Katakan kita mengindeks perkataan "Kucing." Kemudian dari akar indone, kita akan melihat anak-anak pelbagai, dan kita akan melihat indeks yang sepadan dengan huruf C. Jadi yang akan diindeks 2. Jadi memandangkan, kehendak yang memberi kita nod baru. Dan kemudian kita akan bekerja dari nod itu. 

Jadi diberikan nod itu, kami sekali lagi akan melihat pelbagai kanak-kanak itu. Dan kita akan melihat indeks sifar untuk sesuai dengan A dalam kucing. Demikian maka kita akan pergi dengan node itu, dan diberikan nod bahawa kita akan untuk melihat akhirnya ia adalah sepadan T. Dan beralih dengan node itu, akhirnya, kita telah benar-benar kelihatan melalui perkataan kita "kucing." Dan kini bool perkataan sepatutnya untuk menunjukkan sama ada perkataan ini diberikan sebenarnya perkataan. 

Jadi mengapa kita perlu bahawa kes khas? Akan apa perkataan "bencana" di dalam kamus kita, tetapi perkataan "kucing" tidak? Jadi dan ingin melihat jika perkataan "kucing" adalah di dalam kamus kita, kita akan berjaya melihat melalui indeks C-A-T dalam nod wilayah. Tetapi itu hanya kerana malapetaka berlaku untuk mewujudkan nod dalam perjalanan daripada C-A-T, sepanjang jalan ke akhir perkataan. Jadi perkataan bool digunakan untuk menunjukkan sama ada lokasi ini tertentu sebenarnya menunjukkan perkataan. 

Baiklah. Jadi sekarang kita tahu apa yang indone adalah akan kelihatan seperti, mari kita lihat di memuatkan fungsi. Jadi beban akan kembali bool yang untuk sama ada kita berjaya atau tidak berjaya dimuatkan kamus. Dan ini akan menjadi kamus yang kita mahu untuk beban. 

Perkara oleh itu kita lakukan adalah terbuka up yang kamus untuk membaca. Dan kita perlu memastikan kami tidak gagal. Jadi jika kamus itu tidak berjaya dibuka, ia akan kembali batal, di mana kami akan kembali palsu. Tetapi menganggap bahawa ia berjaya dibuka, maka kita sebenarnya boleh membaca melalui kamus. 

Perkara itu kita akan mahu lakukan adalah kita mempunyai ini akar ubah global. Sekarang akar akan menjadi nod *. Ia bahagian atas indone kita bahawa kita akan iterating melalui. Jadi perkara pertama yang kita akan mahu lakukan adalah memperuntukkan memori untuk akar kami. Perhatikan bahawa kita menggunakan calloc yang fungsi, yang pada dasarnya yang sama sebagai fungsi malloc, kecuali ia dijamin untuk kembali sesuatu yang sepenuhnya menumpukan perhatian di luar. Jadi, jika kita digunakan malloc, kita perlu pergi melalui semua petunjuk dalam kita nod, dan memastikan bahawa mereka semua null. Jadi calloc akan melakukannya untuk kita. 

Sekarang seperti malloc, kita perlu membuat memastikan bahawa peruntukan itu sebenarnya berjaya. Jika ini kembali batal, maka kita perlu untuk menutup atau kamus memfailkan dan pulangan palsu. Jadi menganggap peruntukan yang berjaya, kita akan menggunakan nod * kursor untuk melelar melalui indone kami. Jadi akar kita tidak pernah akan berubah, tetapi kita akan menggunakan kursor untuk sebenarnya pergi dari nod ke nod. 

Jadi dalam ini untuk gelung kita membaca melalui fail kamus. Dan kita menggunakan fgetc. Fgetc akan merebut satu watak dari fail. Kami akan terus meraih aksara manakala kita tidak sampai ke akhir fail. 

Terdapat dua kes kita perlu untuk mengendalikan. Yang pertama, jika watak bukan satu barisan baru. Oleh itu, kita tahu jika ia adalah barisan baru, maka kita kira-kira untuk bergerak ke satu perkataan baru. Tetapi menganggap ia bukan satu talian baru, maka di sini kita mahu memikirkan indeks kita akan indeks ke dalam dalam pelbagai kanak-kanak yang kita melihat sebelum ini. 

Jadi, seperti yang saya katakan sebelum ini, kita perlu kes khas koma atas itu. Notis yang kita gunakan pertigaan yang operator di sini. Jadi, kita akan membaca ini kerana, jika watak kita baca dalam merupakan koma atas, maka kita akan menetapkan index = "abjad" -1, yang akan menjadi indeks 26. 

Lagi, jika ia tidak apostrofe, terdapat kami akan menetapkan indeks sama dengan c - a. Jadi ingat kembali dari sebelum ini p-set, c - a akan memberi kita kedudukan abjad C. Jadi, jika C adalah huruf A, ini akan memberikan kita indeks sifar. Untuk surat B, ia akan memberikan kami indeks 1, dan sebagainya. 

Jadi ini memberikan kita indeks ke dalam kanak-kanak array yang kita mahu. Sekarang jika indeks ini kini null dalam kanak-kanak, ini bermakna bahawa nod buat masa ini tidak wujud dari jalan itu. Oleh itu, kita perlu memperuntukkan nod untuk jalan itu. Itulah apa yang kita akan lakukan di sini. 

Jadi, kita akan sekali lagi menggunakan calloc yang fungsi, supaya kita tidak perlu sifar segala petunjuk. Dan kami sekali lagi perlu menyemak calloc yang tidak gagal. Jika calloc tidak gagal, maka kita perlu untuk memunggah segala-galanya, kita menutup kamus, dan pulangan palsu. Jadi menganggap bahawa ia tidak gagal, maka ini akan mewujudkan anak yang baru untuk kita. Dan kemudian kita akan pergi kepada anak itu. Kursor kami akan melelar turun kepada anak itu. 

Sekarang jika ini tidak batal untuk memulakan dengan, maka kursor hanya boleh melelar ke kanak-kanak yang tanpa sebenarnya perlu memperuntukkan apa-apa. Ini adalah kes di mana kita mula-mula berlaku memperuntukkan perkataan "kucing." Dan ini bermakna apabila kita pergi untuk memperuntukkan "Bencana," kita tidak perlu membuat nod untuk C-A-T lagi. Mereka sudah wujud. 

Apakah ini yang berlainan? Ini adalah keadaan di mana c adalah garis sendeng terbalik n, di mana c adalah barisan baru. Ini bermakna bahawa kita telah berjaya selesai satu perkataan. Sekarang apa yang kita mahu lakukan apabila kita berjaya menamatkan satu perkataan? Kami akan menggunakan bidang perkataan ini di dalam nod struct kami. Kami mahu menetapkan bahawa untuk benar. Jadi yang menunjukkan bahawa nod ini menunjukkan yang berjaya perkataan, perkataan yang sebenar. 

Kini bersedia untuk yang benar. Kami mahu menetapkan semula kursor menjelaskan fakta ke permulaan indone lagi. Dan akhirnya, kenaikan kamus kami saiz, kerana kita mendapati kerja lain. Jadi, kita akan terus melakukan itu, membaca dalam watak oleh watak, membina nod baru di indone dan bagi setiap perkataan dalam kamus, sehingga kami akhirnya mencapai C! = EOF, di mana kes kita keluar daripada fail. 

Sekarang terdapat dua kes di bawah yang kita mungkin telah melanda EOF. Yang pertama adalah jika terdapat ralat membaca dari fail. Jadi, jika ada ralat, kami perlu melakukan perkara yang biasa. Memunggah segala-galanya, berhampiran fail, pulangan palsu. Dengan menganggap tidak ada kesilapan, yang hanya bermakna kita sebenarnya melanda akhir fail, di mana, kita menutup memfailkan dan kembali benar kerana kita kamus berjaya dimuatkan ke indone kami. 

Jadi sekarang mari kita lihat cek. Melihat fungsi cek, kita lihat cek yang akan kembali bool a. Ia akan kembali benar jika perkataan ini bahawa itu yang diluluskan adalah di indone kami. Ia akan kembali palsu sebaliknya. Jadi bagaimana anda menentukan sama ada perkataan ini adalah di indone kita? 

Kita lihat di sini bahawa, sama seperti sebelum ini, kita akan menggunakan kursor untuk melelar melalui indone kami. Sekarang di sini kita akan melelar atas seluruh perkataan kami. Jadi iterating lebih perkataan kami yang lepas, kita akan menentukan indeks ke dalam pelbagai kanak-kanak yang sepadan dengan kurungan perkataan I. Jadi ini akan kelihatan betul-betul seperti beban, di mana jika perkataan [i] adalah apostrofe, maka kita mahu menggunakan index "abjad" - 1. Kerana kita menetapkan bahawa yang adalah di mana kita akan menyimpan apostrofi. 

Yang lain kita akan menggunakan dua perkataan yang lebih rendah kurungan I. Jadi ingat perkataan yang boleh mempunyai permodalan sewenang-wenangnya. Dan jadi kita ingin memastikan bahawa kita menggunakan versi huruf kecil perkara. Dan kemudian tolak dari yang 'a' untuk sekali sekali lagi memberi kita abjad yang kedudukan watak itu. Supaya akan menjadi indeks kami ke dalam pelbagai kanak-kanak itu. 

Dan kini jika indeks itu ke dalam kanak-kanak array adalah batal, ini bermakna kita tidak lagi boleh terus iterating turun indone kami. Jika itu berlaku, perkataan ini tidak boleh mungkin berada dalam indone kami. Kerana jika ia, yang akan bermakna akan ada jalan yang ke perkataan itu. Dan anda tidak akan menghadapi null. Jadi menghadapi batal, kita kembali palsu. Perkataan itu tidak ada di dalam kamus. Jika tidak batal, maka kami akan terus iterating. 

Jadi, kita akan di luar sana kursor untuk menunjukkan bahawa tertentu nod di indeks itu. Kami terus melakukan bahawa sepanjang perkataan keseluruhan, dengan andaian kita tidak pernah memukul null. Ini bermakna kita dapat melalui perkataan keseluruhan dan mencari nod dalam cuba kami. Tetapi kita tidak cukup dilakukan lagi. 

Kami tidak mahu hanya kembali benar. Kami mahu kembali kursor> perkataan. Sejak ingat lagi, adalah "kucing" tidak di dalam kamus kita, dan "bencana" adalah, maka kita akan berjaya kita melalui perkataan "kucing." Tetapi kursor perkataan akan menjadi palsu dan tidak benar. Oleh itu, kita kembali perkataan kursor untuk menunjukkan sama ada nod ini sebenarnya perkataan. Dan itu sahaja untuk cek. 

Jadi mari kita lihat saiz. Jadi saiz akan menjadi agak mudah sejak, ingat dalam beban, kami menokok saiz kamus untuk setiap perkataan yang kita hadapi. Jadi saiz hanya akan kembali saiz kamus. Dan itu sahaja. 

Jadi akhir sekali kita telah memunggah. Jadi memunggah, kita akan menggunakan fungsi rekursi untuk benar-benar melakukan semua kerja untuk kita. Jadi fungsi kita akan dipanggil pada-beban. Apa yang pengurang beban akan lakukan? Kita lihat di sini-beban yang akan melelar atas semua kanak-kanak di ini nod tertentu. Dan jika nod kanak-kanak tidak batal, maka kita akan memunggah nod kanak-kanak. 

Jadi ini adalah anda secara rekursif memunggah semua anak-anak kita. Apabila kita pasti bahawa semua anak-anak kita telah dipunggah, maka kita boleh membebaskan diri kita, jadi memunggah diri kita sendiri. Ini akan bekerja secara rekursif memunggah keseluruhan indone itu. Dan kemudian sekali itu dilakukan, kita hanya boleh kembali benar. Memunggah tidak boleh gagal. Kami hanya membebaskan sesuatu. Jadi sebaik sahaja kami selesai membebaskan segala-galanya, kembali benar. Dan itu sahaja. Nama saya Rob. Dan ini adalah buku ejaan. 

[MUZIK Bermain]