1
00:00:00,000 --> 00:00:00,530

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Mari kita beri
solusi ini mencoba.

3
00:00:03,070 --> 00:00:07,130
Jadi mari kita lihat apa yang kami
Struct node akan terlihat seperti.

4
00:00:07,130 --> 00:00:11,040
Di sini, kita melihat kita akan memiliki
Bool Word dan bintang simpul Struct

5
00:00:11,040 --> 00:00:12,990
Anak-anak braket alfabet.

6
00:00:12,990 --> 00:00:18,720
Sehingga hal pertama yang Anda mungkin bertanya-tanya,
mengapa hash alfabet didefinisikan sebagai 27?

7
00:00:18,720 --> 00:00:22,540
Nah, ingat bahwa kita akan membutuhkan
untuk menangani tanda kutip, sehingga

8
00:00:22,540 --> 00:00:25,610
itu akan menjadi agak khusus
terjadi di seluruh program ini.

9
00:00:25,610 --> 00:00:28,780
>> OK, sekarang, ingat bagaimana
Trie benar-benar bekerja.

10
00:00:28,780 --> 00:00:33,420
Katakanlah kita mengindeks kucing kata,
kemudian dari akar Trie kami,

11
00:00:33,420 --> 00:00:36,670
kita akan melihat Anak
array, dan kita akan melihat

12
00:00:36,670 --> 00:00:42,250
Indeks yang sesuai dengan surat
C. Sehingga akan menjadi indeks kedua.

13
00:00:42,250 --> 00:00:46,400
Jadi mengingat bahwa, yang akan memberi kita
node baru, dan kemudian kita akan

14
00:00:46,400 --> 00:00:47,880
bekerja dari simpul tersebut.

15
00:00:47,880 --> 00:00:51,830
>> Jadi mengingat simpul tersebut, kami sekali lagi
akan melihat Anak array,

16
00:00:51,830 --> 00:00:56,170
dan kita akan melihat indeks nol
untuk sesuai dengan A pada kucing.

17
00:00:56,170 --> 00:01:01,240
Jadi kita akan pergi ke simpul tersebut,
dan mengingat simpul tersebut, kita akan

18
00:01:01,240 --> 00:01:05,170
untuk melihat indeks yang sesuai
T. Dan pindah ke simpul tersebut,

19
00:01:05,170 --> 00:01:09,590
akhirnya, kita telah benar-benar melihat
melalui Cat kata kami, dan sekarang Bool

20
00:01:09,590 --> 00:01:15,020
Kata yang seharusnya untuk menunjukkan apakah
kata ini diberikan sebenarnya kata.

21
00:01:15,020 --> 00:01:17,530
>> Jadi mengapa kita perlu bahwa kasus khusus?

22
00:01:17,530 --> 00:01:21,680
Nah, bagaimana jika kata bencana
adalah dalam kamus kami, tapi

23
00:01:21,680 --> 00:01:24,120
kucing kata tidak?

24
00:01:24,120 --> 00:01:29,030
Jadi dalam mencari untuk melihat apakah kucing kata adalah
dalam kamus kami, kita akan

25
00:01:29,030 --> 00:01:34,880
berhasil melihat melalui indeks
C-A-T dan mencapai node, tapi itu

26
00:01:34,880 --> 00:01:39,760
hanya karena bencana yang terjadi pada
membuat node dalam perjalanan dari C-A-T semua

27
00:01:39,760 --> 00:01:41,250
jalan ke akhir kata.

28
00:01:41,250 --> 00:01:46,520
Jadi Bool Word digunakan mengindikasikan apakah
lokasi tertentu ini benar-benar

29
00:01:46,520 --> 00:01:48,370
menunjukkan sebuah kata.

30
00:01:48,370 --> 00:01:52,920
>> Baiklah, jadi sekarang kita tahu apa
Trie akan terlihat seperti, mari kita lihat

31
00:01:52,920 --> 00:01:54,800
pada fungsi Load.

32
00:01:54,800 --> 00:01:58,670
Jadi beban akan kembali Bool
untuk apakah kita berhasil atau

33
00:01:58,670 --> 00:02:03,020
berhasil dimuat kamus dan
ini akan menjadi kamus

34
00:02:03,020 --> 00:02:04,520
bahwa kita ingin memuat.

35
00:02:04,520 --> 00:02:08,310
Sehingga hal pertama kita akan lakukan adalah membuka
up yang kamus untuk membaca.

36
00:02:08,310 --> 00:02:12,060
Kita harus memastikan bahwa kita tidak gagal,
jadi jika kamus itu tidak

37
00:02:12,060 --> 00:02:15,280
berhasil dibuka, maka akan kembali
Tidak, dalam hal ini kita akan

38
00:02:15,280 --> 00:02:16,340
kembali False.

39
00:02:16,340 --> 00:02:21,290
Tetapi dengan asumsi bahwa hal itu berhasil
dibuka, maka kita benar-benar bisa membaca

40
00:02:21,290 --> 00:02:22,310
melalui kamus.

41
00:02:22,310 --> 00:02:24,940
>> Sehingga hal pertama kita akan
ingin lakukan adalah kita memiliki ini

42
00:02:24,940 --> 00:02:26,560
akar variabel global.

43
00:02:26,560 --> 00:02:30,250
Sekarang, akar akan menjadi bintang simpul.

44
00:02:30,250 --> 00:02:33,830
Ini adalah puncak Trie kami bahwa kita
akan iterasi melalui.

45
00:02:33,830 --> 00:02:38,200
Sehingga hal pertama kita akan ingin
lakukan adalah mengalokasikan memori untuk akar kami.

46
00:02:38,200 --> 00:02:42,040
>> Perhatikan bahwa kita menggunakan calloc
fungsi, yang pada dasarnya adalah sama

47
00:02:42,040 --> 00:02:45,560
sebagai fungsi malloc, kecuali itu
dijamin untuk kembali sesuatu yang

48
00:02:45,560 --> 00:02:47,240
benar-benar memusatkan perhatian keluar.

49
00:02:47,240 --> 00:02:51,350
Jadi jika kita menggunakan malloc, kita perlu
pergi melalui semua pointer di kami

50
00:02:51,350 --> 00:02:54,220
simpul dan pastikan bahwa
mereka semua null.

51
00:02:54,220 --> 00:02:56,780
Jadi calloc akan melakukannya untuk kita.

52
00:02:56,780 --> 00:03:00,390
>> Sekarang, seperti malloc, kita perlu membuat
memastikan bahwa alokasi sebenarnya

53
00:03:00,390 --> 00:03:01,580
sukses.

54
00:03:01,580 --> 00:03:04,060
Jika hal ini kembali null, maka kita
harus menutup kamus kami

55
00:03:04,060 --> 00:03:06,170
mengajukan dan kembali False.

56
00:03:06,170 --> 00:03:11,040
Jadi dengan asumsi alokasi itu
sukses, kita akan menggunakan node

57
00:03:11,040 --> 00:03:14,340
membintangi kursor iterate
melalui Trie kami.

58
00:03:14,340 --> 00:03:17,950
Jadi akar kami tidak akan pernah berubah,
tapi kita akan menggunakan kursor ke

59
00:03:17,950 --> 00:03:20,770
benar-benar pergi dari node ke node.

60
00:03:20,770 --> 00:03:25,000
>> Baiklah, jadi dalam hal ini Untuk lingkaran, kita
membaca file kamus,

61
00:03:25,000 --> 00:03:26,965
dan kita gunakan di fgetc.

62
00:03:26,965 --> 00:03:30,360
Jadi fgetc akan ambil satu
karakter dari file tersebut.

63
00:03:30,360 --> 00:03:33,430
Kami akan terus meraih
karakter sementara kita tidak mencapai

64
00:03:33,430 --> 00:03:37,540
akhir file, jadi ada
dua kasus yang kita butuhkan untuk menangani.

65
00:03:37,540 --> 00:03:41,640
Yang pertama, jika karakter bukan
baris baru, jadi kita tahu apakah itu baru

66
00:03:41,640 --> 00:03:44,480
line, maka kita akan
pindah ke sebuah kata baru.

67
00:03:44,480 --> 00:03:49,300
Tapi asumsi itu bukan baris baru, kemudian
di sini, kami ingin mengetahui

68
00:03:49,300 --> 00:03:52,440
indeks kita akan indeks ke
Anak-anak di array

69
00:03:52,440 --> 00:03:53,890
kami melihat sebelumnya.

70
00:03:53,890 --> 00:03:57,950
>> Jadi seperti saya katakan sebelumnya, kita perlu
kasus khusus tanda kutip.

71
00:03:57,950 --> 00:04:01,040
Perhatikan kita sedang menggunakan operator terner
di sini, jadi kita akan membaca

72
00:04:01,040 --> 00:04:05,500
ini seolah-olah karakter yang kita baca dalam adalah
apostrof, maka kita akan

73
00:04:05,500 --> 00:04:11,740
Set index sama dengan alfabet dikurangi
1, yang akan menjadi indeks 26.

74
00:04:11,740 --> 00:04:15,190
Lain, jika bukan apostrof,
maka kita akan mengatur indeks

75
00:04:15,190 --> 00:04:17,820
sama dengan c minus.

76
00:04:17,820 --> 00:04:23,090
Jadi ingat kembali dari p set sebelumnya,
c minus akan memberi kita

77
00:04:23,090 --> 00:04:27,470
Posisi abjad dari c, jadi jika
c adalah huruf A, ini akan

78
00:04:27,470 --> 00:04:28,770
memberi kita indeks nol.

79
00:04:28,770 --> 00:04:32,180
Untuk huruf B, itu akan memberikan
kami indeks 1, dan seterusnya.

80
00:04:32,180 --> 00:04:37,070
>> Jadi ini memberi kita indeks ke dalam
Anak-anak Array yang kita inginkan.

81
00:04:37,070 --> 00:04:42,540
Sekarang, jika indeks ini saat ini nol di
Anak array, yang berarti bahwa

82
00:04:42,540 --> 00:04:47,470
node saat ini tidak ada dari
jalan itu, jadi kita perlu mengalokasikan

83
00:04:47,470 --> 00:04:49,220
simpul untuk jalan itu.

84
00:04:49,220 --> 00:04:50,610
Itulah yang kami lakukan di sini.

85
00:04:50,610 --> 00:04:54,650
Jadi kita akan, sekali lagi, gunakan calloc
fungsi sehingga kita tidak memiliki

86
00:04:54,650 --> 00:05:00,130
untuk nol semua pointer, dan kami,
lagi, perlu memeriksa calloc yang

87
00:05:00,130 --> 00:05:01,300
tidak gagal.

88
00:05:01,300 --> 00:05:04,760
Jika calloc tidak gagal, maka kita perlu
untuk membongkar semuanya, tutup kami

89
00:05:04,760 --> 00:05:06,880
kamus, dan kembali False.

90
00:05:06,880 --> 00:05:14,110
>> Jadi dengan asumsi bahwa itu tidak gagal, maka
ini akan membuat anak yang baru bagi kita,

91
00:05:14,110 --> 00:05:16,000
dan kemudian kami akan pergi ke anak itu.

92
00:05:16,000 --> 00:05:19,030
Kursor kita akan iterate
turun ke anak itu.

93
00:05:19,030 --> 00:05:23,390
Sekarang, jika ini tidak nol untuk memulai dengan,
maka kursor hanya dapat iterate

94
00:05:23,390 --> 00:05:26,650
turun ke anak itu tanpa benar-benar
harus mengalokasikan apa-apa.

95
00:05:26,650 --> 00:05:30,790
Ini adalah kasus di mana kami pertama kali terjadi
untuk mengalokasikan kucing kata, dan

96
00:05:30,790 --> 00:05:34,390
itu berarti ketika kita pergi untuk mengalokasikan
bencana, kita tidak perlu membuat

97
00:05:34,390 --> 00:05:35,720
node untuk C-A-T lagi.

98
00:05:35,720 --> 00:05:37,620
Mereka sudah ada.

99
00:05:37,620 --> 00:05:40,140
>> OK, jadi apa Lagi ini?

100
00:05:40,140 --> 00:05:44,600
Ini adalah kondisi di mana c adalah
backslash n, di mana c adalah baris baru.

101
00:05:44,600 --> 00:05:47,780
Ini berarti bahwa kita telah berhasil
menyelesaikan kata.

102
00:05:47,780 --> 00:05:51,020
Sekarang, apa yang ingin kita lakukan ketika kita
berhasil menyelesaikan sebuah kata?

103
00:05:51,020 --> 00:05:55,250
Kita akan menggunakan kolom kata ini
dalam simpul Struct kami.

104
00:05:55,250 --> 00:06:00,570
>> Kami ingin menetapkan bahwa untuk Benar, sehingga
menunjukkan bahwa node ini menunjukkan

105
00:06:00,570 --> 00:06:03,320
sukses kata kata yang sebenarnya.

106
00:06:03,320 --> 00:06:05,050
Sekarang, menetapkan bahwa untuk Benar.

107
00:06:05,050 --> 00:06:09,210
Kami ingin me-reset kursor kita ke titik
untuk awal Trie lagi.

108
00:06:09,210 --> 00:06:13,510
Dan akhirnya, kenaikan kamus kami
ukuran karena kita menemukan kata lain.

109
00:06:13,510 --> 00:06:16,450
>> Baiklah, jadi kita akan terus melakukan
itu, membaca karakter dengan

110
00:06:16,450 --> 00:06:21,960
karakter, membangun node baru
Trie kami dan untuk setiap kata dalam

111
00:06:21,960 --> 00:06:26,810
kamus, sampai kami akhirnya mencapai c
sama dengan EOF, dalam hal ini, kita istirahat

112
00:06:26,810 --> 00:06:28,100
dari file.

113
00:06:28,100 --> 00:06:31,110
Sekarang, ada dua kasus di bawah
yang kita mungkin telah memukul EOF.

114
00:06:31,110 --> 00:06:35,680
Yang pertama adalah jika ada kesalahan
membaca dari file tersebut, jadi jika ada

115
00:06:35,680 --> 00:06:39,280
kesalahan, yang perlu kita lakukan khas
membongkar semuanya, tutup file,

116
00:06:39,280 --> 00:06:40,520
kembali False.

117
00:06:40,520 --> 00:06:43,870
Dengan asumsi tidak ada kesalahan, yang
hanya berarti kita benar-benar memukul akhir

118
00:06:43,870 --> 00:06:47,820
file, dalam hal ini, kita menutup
mengajukan dan kembali Benar karena kita

119
00:06:47,820 --> 00:06:51,010
berhasil dimuat kamus
Trie ke kami.

120
00:06:51,010 --> 00:06:54,240
>> Baiklah, jadi sekarang mari kita
memeriksa tarif.

121
00:06:54,240 --> 00:06:58,780
Melihat fungsi Periksa, kita melihat
Periksa bahwa akan mengembalikan Bool.

122
00:06:58,780 --> 00:07:03,740
Ia mengembalikan Benar jika kata ini bahwa itu
yang lulus di Trie kami.

123
00:07:03,740 --> 00:07:06,170
Ia mengembalikan False sebaliknya.

124
00:07:06,170 --> 00:07:10,110
>> Jadi bagaimana kita akan menentukan apakah
kata ini adalah di Trie kita?

125
00:07:10,110 --> 00:07:14,270
Kita lihat di sini bahwa, sama seperti sebelumnya,
kita akan menggunakan kursor untuk iterate

126
00:07:14,270 --> 00:07:16,010
melalui Trie kami.

127
00:07:16,010 --> 00:07:20,650
Sekarang, di sini, kita akan iterate
atas seluruh kata kita.

128
00:07:20,650 --> 00:07:24,680
Jadi iterasi kata kita
berlalu, kita akan menentukan

129
00:07:24,680 --> 00:07:29,280
indeks ke dalam array Anak-anak
sesuai dengan kata braket i.

130
00:07:29,280 --> 00:07:34,150
Jadi ini akan terlihat persis seperti
Load, di mana jika kata braket i adalah

131
00:07:34,150 --> 00:07:38,110
apostrof, maka kita ingin menggunakan indeks
alfabet dikurangi 1 karena kita ditentukan

132
00:07:38,110 --> 00:07:41,160
itu adalah di mana kita akan
untuk menyimpan apostrof.

133
00:07:41,160 --> 00:07:44,440
>> Lain kita akan menggunakan tolower
kata braket i.

134
00:07:44,440 --> 00:07:48,270
Jadi ingat kata yang dapat memiliki sewenang-wenang
kapitalisasi, dan jadi kita

135
00:07:48,270 --> 00:07:51,590
ingin memastikan bahwa kita menggunakan
versi huruf kecil hal.

136
00:07:51,590 --> 00:07:55,300
Dan kemudian kurangi dari huruf kecil yang
untuk, sekali lagi, memberi kita

137
00:07:55,300 --> 00:07:57,940
Posisi abjad
karakter itu.

138
00:07:57,940 --> 00:08:01,740
Sehingga akan menjadi indeks kami
Anak-anak ke dalam array.

139
00:08:01,740 --> 00:08:06,480
>> Dan sekarang, jika indeks ke Anak
array nol, itu berarti kita

140
00:08:06,480 --> 00:08:09,050
tidak bisa lagi melanjutkan iterasi
Trie bawah kami.

141
00:08:09,050 --> 00:08:13,320
Jika itu yang terjadi, kata ini tidak bisa
mungkin berada dalam Trie kami, karena jika

142
00:08:13,320 --> 00:08:18,000
yang, itu berarti akan ada
path ke kata itu, dan Anda akan

143
00:08:18,000 --> 00:08:19,350
pernah mengalami null.

144
00:08:19,350 --> 00:08:21,910
Jadi menghadapi null, kita kembali False.

145
00:08:21,910 --> 00:08:23,810
Kata tersebut tidak ada dalam kamus.

146
00:08:23,810 --> 00:08:28,200
Jika bukan nol, maka kita akan
terus iterasi, jadi kita akan

147
00:08:28,200 --> 00:08:33,150
untuk memperbarui kursor untuk menunjuk ke
node tertentu pada indeks itu.

148
00:08:33,150 --> 00:08:36,659
>> Jadi kita terus melakukan itu sepanjang
seluruh kata.

149
00:08:36,659 --> 00:08:40,630
Dengan asumsi kita tidak pernah memukul null, artinya
kami mampu melewati seluruh yang

150
00:08:40,630 --> 00:08:44,840
dunia dan menemukan simpul di Trie kami,
tapi kami tidak cukup dilakukan belum.

151
00:08:44,840 --> 00:08:46,350
Kami tidak ingin hanya kembali Benar.

152
00:08:46,350 --> 00:08:51,400
Kami ingin kembali kursor kata kesalahan
karena, ingat lagi, jika kucing tidak

153
00:08:51,400 --> 00:08:55,140
dalam kamus dan bencana kita,
maka kita akan berhasil melewati

154
00:08:55,140 --> 00:08:59,810
kucing kata, tapi kata kursor
akan Palsu dan tidak benar.

155
00:08:59,810 --> 00:09:04,990
Jadi kita kembali kata kursor untuk menunjukkan
apakah simpul ini sebenarnya sebuah kata,

156
00:09:04,990 --> 00:09:06,530
dan itu saja untuk cek.

157
00:09:06,530 --> 00:09:08,310
>> Jadi mari kita periksa Size.

158
00:09:08,310 --> 00:09:11,410
Jadi Ukuran akan menjadi cukup mudah
karena, ingat di Load, kami

159
00:09:11,410 --> 00:09:15,480
incrementing ukuran kamus untuk
setiap kata yang kita hadapi.

160
00:09:15,480 --> 00:09:20,820
Jadi Ukuran hanya akan kembali
ukuran kamus, dan hanya itu.

161
00:09:20,820 --> 00:09:24,650
>> Baiklah, jadi yang terakhir, kita memiliki Unload.

162
00:09:24,650 --> 00:09:29,050
Jadi Membongkar, kita akan menggunakan
fungsi rekursif untuk benar-benar melakukan semua

163
00:09:29,050 --> 00:09:33,390
pekerjaan bagi kita, jadi fungsi kita
akan disebut Unloader.

164
00:09:33,390 --> 00:09:35,830
Apa yang Unloader lakukan?

165
00:09:35,830 --> 00:09:40,640
Kita lihat di sini Unloader yang akan
iterate atas semua anak-anak di

166
00:09:40,640 --> 00:09:45,810
simpul tertentu, dan jika anak
node tidak null, maka kita akan

167
00:09:45,810 --> 00:09:47,760
membongkar node anak.

168
00:09:47,760 --> 00:09:52,070
>> Jadi ini akan secara rekursif
membongkar semua anak-anak kita.

169
00:09:52,070 --> 00:09:55,140
Setelah kami yakin bahwa semua anak-anak kita
telah dibongkar, maka kita

170
00:09:55,140 --> 00:09:58,830
dapat membebaskan diri, sehingga membongkar diri.

171
00:09:58,830 --> 00:10:04,550
Jadi ini secara rekursif akan membongkar
seluruh Trie, dan kemudian sekali itu

172
00:10:04,550 --> 00:10:06,910
dilakukan, kita hanya bisa kembali Benar.

173
00:10:06,910 --> 00:10:09,770
Membongkar tidak bisa gagal, kami
hanya membebaskan hal.

174
00:10:09,770 --> 00:10:12,985
Jadi setelah kami selesai membebaskan
semuanya, kembali Benar.

175
00:10:12,985 --> 00:10:14,380
Dan itu saja.

176
00:10:14,380 --> 00:10:16,792
Nama saya Rob, dan ini
adalah [Tak terdengar].

177
00:10:16,792 --> 00:10:21,888