1
00:00:00,000 --> 00:00:12,350
>> [MUSIC PLAYING]

2
00:00:12,350 --> 00:00:13,050
>> ROB Bowden: Hi.

3
00:00:13,050 --> 00:00:13,640
Aku Rob.

4
00:00:13,640 --> 00:00:16,210
Dan mari kita solusi ini.

5
00:00:16,210 --> 00:00:20,070
Jadi di sini kita akan mengimplementasikan
meja umum.

6
00:00:20,070 --> 00:00:24,090
Kita melihat bahwa struct node kami
tabel akan terlihat seperti ini.

7
00:00:24,090 --> 00:00:28,710
Jadi itu akan memiliki kata arang
array ukuran PANJANG + 1.

8
00:00:28,710 --> 00:00:32,259
Jangan lupa + 1, karena maksimum
kata dalam kamus adalah 45

9
00:00:32,259 --> 00:00:33,130
karakter.

10
00:00:33,130 --> 00:00:37,070
Dan kemudian kita akan membutuhkan satu tambahan
karakter untuk nol backslash.

11
00:00:37,070 --> 00:00:40,870
>> Dan kemudian hashtable kami di setiap
ember akan menyimpan

12
00:00:40,870 --> 00:00:42,320
linked list node.

13
00:00:42,320 --> 00:00:44,420
Kami tidak melakukan linear menyelidik sini.

14
00:00:44,420 --> 00:00:48,430
Dan dalam rangka untuk menghubungkan ke depan
elemen dalam ember, kita perlu

15
00:00:48,430 --> 00:00:50,390
struct simpul * berikutnya.

16
00:00:50,390 --> 00:00:51,110
OK.

17
00:00:51,110 --> 00:00:53,090
Jadi itulah yang simpul yang tampak seperti.

18
00:00:53,090 --> 00:00:56,180
>> Sekarang di sini adalah deklarasi
dari hashtable kami.

19
00:00:56,180 --> 00:00:59,640
Ini akan memiliki 16.834 ember.

20
00:00:59,640 --> 00:01:01,910
Namun jumlah itu tidak terlalu penting.

21
00:01:01,910 --> 00:01:05,450
Dan akhirnya, kita akan memiliki
ukuran hashtable variabel global, yang

22
00:01:05,450 --> 00:01:07,000
akan memulai sebagai nol.

23
00:01:07,000 --> 00:01:10,760
Dan itu akan melacak bagaimana
banyak kata yang ada dalam kamus kami.

24
00:01:10,760 --> 00:01:13,710
>> Jadi mari kita lihat pada beban.

25
00:01:13,710 --> 00:01:16,390
Perhatikan beban itu, ia mengembalikan bool.

26
00:01:16,390 --> 00:01:20,530
Anda mengembalikan true jika itu berhasil
dimuat, dan false jika tidak.

27
00:01:20,530 --> 00:01:23,990
Dan dibutuhkan const char * kamus,
yang merupakan kamus

28
00:01:23,990 --> 00:01:25,280
bahwa kita ingin membuka.

29
00:01:25,280 --> 00:01:27,170
Jadi itulah hal pertama
kita akan lakukan.

30
00:01:27,170 --> 00:01:29,500
>> Kita akan fopen yang
kamus untuk membaca.

31
00:01:29,500 --> 00:01:31,680
Dan kita akan harus membuat
yakin bahwa itu berhasil.

32
00:01:31,680 --> 00:01:35,920
Jadi, jika itu kembali NULL, maka kita tidak
berhasil membuka kamus.

33
00:01:35,920 --> 00:01:37,440
Dan kita perlu kembali palsu.

34
00:01:37,440 --> 00:01:41,580
Tetapi dengan asumsi bahwa hal itu berhasil
terbuka, maka kita ingin membaca

35
00:01:41,580 --> 00:01:42,400
kamus.

36
00:01:42,400 --> 00:01:46,450
Jadi terus looping sampai kita menemukan beberapa
alasan untuk keluar dari lingkaran ini,

37
00:01:46,450 --> 00:01:47,570
yang akan kita lihat.

38
00:01:47,570 --> 00:01:48,920
Jadi terus perulangan.

39
00:01:48,920 --> 00:01:51,780
>> Dan sekarang kita akan
malloc node tunggal.

40
00:01:51,780 --> 00:01:54,020
Dan tentu saja kita perlu
untuk udara periksa lagi.

41
00:01:54,020 --> 00:01:58,680
Jadi jika mallocing tidak berhasil, maka
kita ingin membongkar setiap node yang kita

42
00:01:58,680 --> 00:02:02,590
terjadi pada malloc sebelumnya, tutup
kamus dan kembali palsu.

43
00:02:02,590 --> 00:02:06,830
Tetapi mengabaikan itu, dengan asumsi kita
berhasil, maka kita ingin menggunakan fscanf

44
00:02:06,830 --> 00:02:12,400
untuk membaca satu kata dari kami
kamus ke simpul kami.

45
00:02:12,400 --> 00:02:17,940
Jadi ingat bahwa catatan> kata adalah char
penyangga kata ukuran lenghth + 1

46
00:02:17,940 --> 00:02:20,300
bahwa kita akan menyimpan kata masuk

47
00:02:20,300 --> 00:02:25,070
>> Jadi fscanf akan kembali 1, selama
seperti itu berhasil

48
00:02:25,070 --> 00:02:26,750
membaca sebuah kata dari file tersebut.

49
00:02:26,750 --> 00:02:30,460
Jika terjadi kesalahan yang terjadi, atau kita
mencapai akhir dari file tersebut, ia

50
00:02:30,460 --> 00:02:31,950
tidak akan kembali 1.

51
00:02:31,950 --> 00:02:35,180
Dalam hal ini tidak kembali 1,
kita akhirnya akan keluar dari

52
00:02:35,180 --> 00:02:37,280
ini loop sementara.

53
00:02:37,280 --> 00:02:42,770
Jadi kita melihat bahwa sekali kita telah berhasil
membaca sebuah kata ke dalam

54
00:02:42,770 --> 00:02:48,270
catatan> kata, maka kita akan bahwa
kata menggunakan fungsi hash kami.

55
00:02:48,270 --> 00:02:49,580
>> Mari kita lihat
fungsi hash.

56
00:02:49,580 --> 00:02:52,430

57
00:02:52,430 --> 00:02:55,610
Jadi Anda tidak benar-benar perlu
untuk memahami ini.

58
00:02:55,610 --> 00:02:59,460
Dan sebenarnya kami hanya menarik hash ini
fungsi dari internet.

59
00:02:59,460 --> 00:03:04,010
Satu-satunya hal yang perlu Anda mengenali adalah
bahwa ini mengambil char * const kata.

60
00:03:04,010 --> 00:03:08,960
Jadi itu mengambil string sebagai masukan, dan
kembali sebuah int unsigned sebagai output.

61
00:03:08,960 --> 00:03:12,360
Jadi itu semua fungsi hash adalah, apakah
mengambil dalam masukan dan memberi Anda

62
00:03:12,360 --> 00:03:14,490
indeks ke hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Perhatikan bahwa kita moding oleh NUM_BUCKETS,
sehingga nilai yang dikembalikan

64
00:03:18,530 --> 00:03:21,730
sebenarnya adalah indeks ke hashtable
dan tidak indeks luar

65
00:03:21,730 --> 00:03:24,320
batas-batas array.

66
00:03:24,320 --> 00:03:28,060
Jadi mengingat fungsi itu, kita akan
hash kata yang kita membaca

67
00:03:28,060 --> 00:03:29,390
kamus.

68
00:03:29,390 --> 00:03:31,700
Dan kemudian kita akan menggunakan
bahwa hash untuk memasukkan

69
00:03:31,700 --> 00:03:33,750
masuk ke hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Hash Sekarang hashtable adalah arus
linked list dalam tabel.

71
00:03:38,520 --> 00:03:41,410
Dan itu sangat mungkin
bahwa itu hanya NULL.

72
00:03:41,410 --> 00:03:44,960
Kami ingin memasukkan entri kami di
awal linked list ini.

73
00:03:44,960 --> 00:03:48,600
Dan jadi kita akan memiliki saat kami
entry point untuk apa hashtable

74
00:03:48,600 --> 00:03:50,380
saat ini menunjuk ke.

75
00:03:50,380 --> 00:03:53,310
Dan kemudian kita akan menyimpan,
dalam hashtable di

76
00:03:53,310 --> 00:03:55,350
hash, entry ini.

77
00:03:55,350 --> 00:03:59,320
Jadi dua baris ini berhasil memasukkan
entri pada awal

78
00:03:59,320 --> 00:04:02,260
linked list pada indeks yang
di hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Setelah kami selesai dengan itu, kita tahu
bahwa kita menemukan kata lain dalam

80
00:04:04,900 --> 00:04:07,790
kamus, dan kami kenaikan lagi.

81
00:04:07,790 --> 00:04:13,960
Jadi kita terus melakukan itu sampai fscanf
akhirnya kembali sesuatu yang non-1 di

82
00:04:13,960 --> 00:04:16,950
mana titik ingat bahwa
kita perlu membebaskan entri.

83
00:04:16,950 --> 00:04:19,459
Jadi di sini kita malloced entri.

84
00:04:19,459 --> 00:04:21,329
Dan kami mencoba untuk membaca sesuatu
dari kamus.

85
00:04:21,329 --> 00:04:23,910
Dan kami tidak berhasil membaca
sesuatu dari kamus, dalam

86
00:04:23,910 --> 00:04:26,650
hal ini kita perlu membebaskan entri
bahwa kita tidak pernah benar-benar dimasukkan ke dalam

87
00:04:26,650 --> 00:04:29,140
hashtable, dan akhirnya pecah.

88
00:04:29,140 --> 00:04:32,750
>> Setelah kami keluar kita perlu melihat, baik,
Apakah kita keluar karena ada

89
00:04:32,750 --> 00:04:34,360
adalah kesalahan membaca dari file?

90
00:04:34,360 --> 00:04:37,120
Atau apakah kita keluar karena kita
mencapai akhir file?

91
00:04:37,120 --> 00:04:39,480
Jika ada kesalahan, maka
kita ingin kembali palsu.

92
00:04:39,480 --> 00:04:40,930
Karena beban tidak berhasil.

93
00:04:40,930 --> 00:04:43,890
Dan dalam proses kita ingin membongkar
semua kata-kata yang kita baca dalam, dan

94
00:04:43,890 --> 00:04:45,670
menutup file kamus.

95
00:04:45,670 --> 00:04:48,740
>> Dengan asumsi kita tidak berhasil, maka kita hanya
masih perlu menutup kamus

96
00:04:48,740 --> 00:04:53,040
mengajukan, dan akhirnya kembali benar karena kita
berhasil dimuat kamus.

97
00:04:53,040 --> 00:04:54,420
Dan itu saja untuk beban.

98
00:04:54,420 --> 00:04:59,020
Jadi sekarang memeriksa, diberi hashtable dimuat,
akan terlihat seperti ini.

99
00:04:59,020 --> 00:05:03,140
Jadi periksa, ia mengembalikan bool, yang
akan menunjukkan apakah lulus

100
00:05:03,140 --> 00:05:07,530
di char * kata, apakah lulus
dalam string adalah dalam kamus kami.

101
00:05:07,530 --> 00:05:09,890
Jadi jika berada dalam kamus,
jika berada dalam hashtable kami,

102
00:05:09,890 --> 00:05:11,170
kami akan kembali benar.

103
00:05:11,170 --> 00:05:13,380
Dan jika tidak, kami akan kembali palsu.

104
00:05:13,380 --> 00:05:17,740
>> Mengingat ini berlalu dalam kata, kami
akan hash kata.

105
00:05:17,740 --> 00:05:22,110
Sekarang hal yang penting untuk mengenali adalah
bahwa beban kita tahu bahwa semua

106
00:05:22,110 --> 00:05:23,820
kata-kata kita akan menjadi huruf kecil.

107
00:05:23,820 --> 00:05:25,820
Tapi di sini kita tidak begitu yakin.

108
00:05:25,820 --> 00:05:29,510
Jika kita melihat pada fungsi hash kami,
Fungsi hash kami benar-benar

109
00:05:29,510 --> 00:05:32,700
adalah casing yang lebih rendah masing-masing karakter
kata.

110
00:05:32,700 --> 00:05:37,940
Jadi terlepas dari kapitalisasi
kata, fungsi hash kami adalah kembalinya

111
00:05:37,940 --> 00:05:42,270
indeks yang sama untuk apa pun
kapitalisasi adalah, karena akan memiliki

112
00:05:42,270 --> 00:05:45,280
kembali untuk benar-benar huruf kecil
versi kata.

113
00:05:45,280 --> 00:05:46,600
Baiklah.

114
00:05:46,600 --> 00:05:49,790
Itu indeks kami adalah ke
Hashtable untuk kata ini.

115
00:05:49,790 --> 00:05:52,940
>> Sekarang ini untuk loop akan
iterate atas daftar link

116
00:05:52,940 --> 00:05:55,000
yang pada indeks itu.

117
00:05:55,000 --> 00:05:59,610
Jadi perhatikan kita menginisialisasi entri
untuk menunjuk ke indeks.

118
00:05:59,610 --> 00:06:02,750
Kami akan terus
sementara masuk! = NULL.

119
00:06:02,750 --> 00:06:07,770
Dan ingat bahwa memperbarui pointer
dalam daftar kami masuk linked = entry> berikutnya.

120
00:06:07,770 --> 00:06:14,400
Jadi kami memiliki titik masuk saat ini untuk
item berikutnya dalam linked list.

121
00:06:14,400 --> 00:06:19,250
>> Jadi untuk setiap entri dalam linked list,
kita akan menggunakan strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Ini bukan StrComp.

123
00:06:20,330 --> 00:06:23,780
Karena sekali lagi, kita ingin
melakukan hal-hal kasus insensitively.

124
00:06:23,780 --> 00:06:27,870
Jadi kita menggunakan strcasecmp untuk membandingkan
kata yang melewati ini

125
00:06:27,870 --> 00:06:31,860
fungsi terhadap kata
yang ada di entri ini.

126
00:06:31,860 --> 00:06:35,570
Jika kembali nol, yang berarti ada
pertandingan, dalam hal ini kita ingin

127
00:06:35,570 --> 00:06:36,630
kembali benar.

128
00:06:36,630 --> 00:06:39,590
Kami berhasil menemukan
kata dalam hashtable kami.

129
00:06:39,590 --> 00:06:43,040
>> Jika tidak ada pertandingan, maka kita
akan loop lagi dan melihat

130
00:06:43,040 --> 00:06:43,990
entri berikutnya.

131
00:06:43,990 --> 00:06:47,640
Dan kami akan terus looping sementara ada
entri dalam daftar link ini.

132
00:06:47,640 --> 00:06:50,160
Apa yang terjadi jika kita istirahat
keluar dari ini untuk loop?

133
00:06:50,160 --> 00:06:55,110
Itu berarti kita tidak menemukan entri yang
cocok kata ini, dalam hal ini

134
00:06:55,110 --> 00:07:00,220
kita kembali palsu untuk menunjukkan bahwa kami
hashtable tidak mengandung kata ini.

135
00:07:00,220 --> 00:07:02,540
Dan itu cek.

136
00:07:02,540 --> 00:07:04,790
>> Jadi mari kita lihat ukuran.

137
00:07:04,790 --> 00:07:06,970
Ukuran Sekarang akan menjadi sangat sederhana.

138
00:07:06,970 --> 00:07:11,080
Sejak ingat beban, untuk setiap kata
kami menemukan, kami bertambah global

139
00:07:11,080 --> 00:07:12,880
ukuran hashtable variabel.

140
00:07:12,880 --> 00:07:16,480
Jadi fungsi ukuran hanya akan
untuk kembali variabel global.

141
00:07:16,480 --> 00:07:18,150
Dan itu saja.

142
00:07:18,150 --> 00:07:22,300
>> Sekarang akhirnya, kita perlu membongkar
kamus setelah semuanya selesai.

143
00:07:22,300 --> 00:07:25,340
Jadi bagaimana yang akan kita melakukan itu?

144
00:07:25,340 --> 00:07:30,440
Di sini kita mengulang terus
semua ember meja kami.

145
00:07:30,440 --> 00:07:33,240
Jadi ada NUM_BUCKETS ember.

146
00:07:33,240 --> 00:07:37,410
Dan untuk setiap linked list di kami
hashtable, kita akan loop atas

147
00:07:37,410 --> 00:07:41,070
keseluruhan dari linked list,
membebaskan setiap elemen.

148
00:07:41,070 --> 00:07:42,900
>> Sekarang kita perlu berhati-hati.

149
00:07:42,900 --> 00:07:47,910
Jadi di sini kita memiliki variabel sementara
yang menyimpan pointer ke depan

150
00:07:47,910 --> 00:07:49,730
elemen dalam linked list.

151
00:07:49,730 --> 00:07:52,140
Dan kemudian kita akan bebas
elemen saat ini.

152
00:07:52,140 --> 00:07:55,990
Kita perlu memastikan bahwa kita melakukan ini karena kita
tidak bisa hanya membebaskan elemen saat ini

153
00:07:55,990 --> 00:07:59,180
dan kemudian mencoba untuk mengakses pointer berikutnya,
karena sekali kita sudah dibebaskan itu,

154
00:07:59,180 --> 00:08:00,870
memori menjadi tidak valid.

155
00:08:00,870 --> 00:08:04,990
>> Jadi kita perlu menjaga sekitar pointer ke
elemen berikutnya, maka kita dapat membebaskan

156
00:08:04,990 --> 00:08:08,360
elemen saat ini, dan kemudian kita dapat memperbarui
elemen kami saat ini untuk menunjuk ke

157
00:08:08,360 --> 00:08:09,550
elemen berikutnya.

158
00:08:09,550 --> 00:08:12,800
Kami akan loop sementara ada unsur
dalam linked list ini.

159
00:08:12,800 --> 00:08:15,620
Kami akan melakukannya untuk semua terkait
daftar di hashtable.

160
00:08:15,620 --> 00:08:19,460
Dan setelah kami selesai dengan itu, kita sudah
benar-benar dibongkar hashtable, dan

161
00:08:19,460 --> 00:08:20,190
kita sudah selesai.

162
00:08:20,190 --> 00:08:23,200
Jadi tidak mungkin untuk membongkar
pernah kembali palsu.

163
00:08:23,200 --> 00:08:26,470
Dan ketika kita sudah selesai, kita
hanya kembali benar.

164
00:08:26,470 --> 00:08:29,000
>> Mari kita beri solusi ini mencoba.

165
00:08:29,000 --> 00:08:33,070
Jadi mari kita lihat apa yang kami
struct node akan terlihat seperti.

166
00:08:33,070 --> 00:08:36,220
Di sini kita melihat kita akan memiliki bool
kata dan struct simpul * anak

167
00:08:36,220 --> 00:08:37,470
braket ALPHABET.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
Jadi hal pertama yang Anda mungkin
tanya, mengapa ALPHABET

170
00:08:42,020 --> 00:08:44,660
ed didefinisikan sebagai 27?

171
00:08:44,660 --> 00:08:47,900
Nah, ingat bahwa kita akan membutuhkan
untuk menangani tanda kutip.

172
00:08:47,900 --> 00:08:51,910
Sehingga akan menjadi sedikit dari
kasus khusus seluruh program ini.

173
00:08:51,910 --> 00:08:54,710
>> Sekarang ingat bagaimana trie
benar-benar bekerja.

174
00:08:54,710 --> 00:08:59,380
Katakanlah kita pengindeksan kata
"Kucing." Kemudian dari akar trie,

175
00:08:59,380 --> 00:09:02,610
kita akan melihat anak-anak
array, dan kita akan melihat

176
00:09:02,610 --> 00:09:08,090
Indeks yang sesuai dengan surat
C. Sehingga akan diindeks 2.

177
00:09:08,090 --> 00:09:11,530
Jadi mengingat bahwa, kehendak yang
memberi kita sebuah node baru.

178
00:09:11,530 --> 00:09:13,820
Dan kemudian kita akan bekerja dari simpul tersebut.

179
00:09:13,820 --> 00:09:17,770
>> Jadi mengingat simpul tersebut, kami sekali lagi
akan melihat anak-anak array.

180
00:09:17,770 --> 00:09:22,110
Dan kita akan melihat indeks nol
untuk sesuai dengan A pada kucing.

181
00:09:22,110 --> 00:09:27,170
Jadi kita akan pergi ke simpul tersebut,
dan mengingat simpul bahwa kita akan

182
00:09:27,170 --> 00:09:31,090
untuk melihat akhir itu berkorespondensi
T. Dan pindah ke simpul tersebut,

183
00:09:31,090 --> 00:09:35,530
akhirnya, kita telah benar-benar melihat
melalui kata kita "kucing." Dan sekarang bool

184
00:09:35,530 --> 00:09:40,960
kata yang seharusnya untuk menunjukkan apakah
kata ini diberikan sebenarnya kata.

185
00:09:40,960 --> 00:09:43,470
>> Jadi mengapa kita perlu bahwa kasus khusus?

186
00:09:43,470 --> 00:09:47,700
Nah apa kata "bencana"
adalah dalam kamus kami, tetapi

187
00:09:47,700 --> 00:09:50,150
Kata "kucing" yang tidak?

188
00:09:50,150 --> 00:09:54,580
Jadi dan mencari untuk melihat apakah kata "kucing"
adalah dalam kamus kami, kami

189
00:09:54,580 --> 00:09:59,970
akan berhasil melihat melalui
indeks C-A-T di wilayah simpul.

190
00:09:59,970 --> 00:10:04,290
Tapi itu hanya karena bencana
terjadi untuk membuat node di jalan

191
00:10:04,290 --> 00:10:07,190
dari C-A-T, semua cara untuk
akhir kata.

192
00:10:07,190 --> 00:10:12,020
Jadi kata bool digunakan untuk mengindikasikan apakah
lokasi tertentu ini

193
00:10:12,020 --> 00:10:14,310
benar-benar menunjukkan sebuah kata.

194
00:10:14,310 --> 00:10:15,140
>> Baik.

195
00:10:15,140 --> 00:10:19,310
Jadi sekarang kita tahu apa itu trie adalah
akan terlihat seperti, mari kita lihat pada

196
00:10:19,310 --> 00:10:20,730
memuat fungsi.

197
00:10:20,730 --> 00:10:24,610
Jadi beban akan kembali bool
untuk apakah kita berhasil atau

198
00:10:24,610 --> 00:10:26,720
berhasil dimuat kamus.

199
00:10:26,720 --> 00:10:30,460
Dan ini akan menjadi kamus
bahwa kita ingin memuat.

200
00:10:30,460 --> 00:10:33,930
>> Sehingga hal pertama kita lakukan adalah membuka
up yang kamus untuk membaca.

201
00:10:33,930 --> 00:10:36,160
Dan kami harus memastikan
kami tidak gagal.

202
00:10:36,160 --> 00:10:39,580
Jadi jika kamus itu tidak
berhasil dibuka, maka akan kembali

203
00:10:39,580 --> 00:10:42,400
null, dalam hal ini kita
akan kembali palsu.

204
00:10:42,400 --> 00:10:47,230
Tetapi dengan asumsi bahwa hal itu berhasil
dibuka, maka kita benar-benar bisa membaca

205
00:10:47,230 --> 00:10:48,220
melalui kamus.

206
00:10:48,220 --> 00:10:50,880
>> Sehingga hal pertama kita akan
ingin lakukan adalah kita memiliki ini

207
00:10:50,880 --> 00:10:52,500
akar variabel global.

208
00:10:52,500 --> 00:10:56,190
Sekarang akar akan menjadi node *.

209
00:10:56,190 --> 00:10:59,760
Ini adalah atas trie kami bahwa kita
akan iterasi melalui.

210
00:10:59,760 --> 00:11:02,660
Jadi hal pertama yang kita akan
ingin lakukan adalah mengalokasikan

211
00:11:02,660 --> 00:11:04,140
memori untuk akar kami.

212
00:11:04,140 --> 00:11:07,980
Perhatikan bahwa kita menggunakan calloc yang
fungsi, yang pada dasarnya adalah sama

213
00:11:07,980 --> 00:11:11,500
sebagai fungsi malloc, kecuali itu
dijamin untuk kembali sesuatu yang

214
00:11:11,500 --> 00:11:13,180
benar-benar memusatkan perhatian keluar.

215
00:11:13,180 --> 00:11:17,290
Jadi jika kita menggunakan malloc, kita perlu
pergi melalui semua pointer di kami

216
00:11:17,290 --> 00:11:20,160
node, dan pastikan bahwa
mereka semua null.

217
00:11:20,160 --> 00:11:22,710
Jadi calloc akan melakukannya untuk kita.

218
00:11:22,710 --> 00:11:26,330
>> Sekarang seperti malloc, kita perlu membuat
memastikan bahwa alokasi itu sebenarnya

219
00:11:26,330 --> 00:11:27,520
sukses.

220
00:11:27,520 --> 00:11:29,990
Jika hal ini kembali null, maka kita
harus menutup atau kamus

221
00:11:29,990 --> 00:11:32,100
mengajukan dan kembali palsu.

222
00:11:32,100 --> 00:11:36,835
Jadi dengan asumsi alokasi yang
sukses, kita akan menggunakan node *

223
00:11:36,835 --> 00:11:40,270
kursor untuk iterate melalui trie kami.

224
00:11:40,270 --> 00:11:43,890
Jadi akar kita tidak akan pernah berubah,
tapi kita akan menggunakan kursor ke

225
00:11:43,890 --> 00:11:47,875
benar-benar pergi dari node ke node.

226
00:11:47,875 --> 00:11:50,940
>> Jadi dalam hal ini untuk loop kita membaca
melalui file kamus.

227
00:11:50,940 --> 00:11:53,670
Dan kita menggunakan fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc akan ambil satu
karakter dari file tersebut.

229
00:11:56,290 --> 00:11:59,370
Kami akan terus meraih
karakter sementara kita tidak mencapai

230
00:11:59,370 --> 00:12:01,570
akhir file.

231
00:12:01,570 --> 00:12:03,480
>> Ada dua kasus yang kita butuhkan untuk menangani.

232
00:12:03,480 --> 00:12:06,610
Yang pertama, jika karakter
bukan baris baru.

233
00:12:06,610 --> 00:12:10,450
Jadi kita tahu apakah itu baris baru, kemudian
kami akan pindah ke sebuah kata baru.

234
00:12:10,450 --> 00:12:15,240
Tapi asumsi itu bukan baris baru, kemudian
di sini kita ingin mengetahui

235
00:12:15,240 --> 00:12:18,380
indeks kita akan indeks ke
pada anak-anak array

236
00:12:18,380 --> 00:12:19,810
kami melihat sebelumnya.

237
00:12:19,810 --> 00:12:23,880
>> Jadi, seperti saya katakan sebelumnya, kita perlu
kasus khusus tanda kutip.

238
00:12:23,880 --> 00:12:26,220
Perhatikan kita sedang menggunakan terner tersebut
Operator di sini.

239
00:12:26,220 --> 00:12:29,580
Jadi kita akan membaca ini sebagai, jika
karakter yang kita baca dalam adalah

240
00:12:29,580 --> 00:12:35,330
apostrof, maka kita akan mengatur
index = "ALPHABET" -1, yang akan

241
00:12:35,330 --> 00:12:37,680
menjadi indeks 26.

242
00:12:37,680 --> 00:12:41,130
>> Lain, jika bukan apostrof, ada
kita akan mengatur indeks

243
00:12:41,130 --> 00:12:43,760
sama dengan c - a.

244
00:12:43,760 --> 00:12:49,030
Jadi ingat kembali dari sebelumnya p-set,
c - a akan memberi kita

245
00:12:49,030 --> 00:12:53,410
Posisi abjad dari C. Jadi jika
C adalah huruf A, ini akan

246
00:12:53,410 --> 00:12:54,700
memberi kita indeks nol.

247
00:12:54,700 --> 00:12:58,120
Untuk huruf B, akan memberikan
kami indeks 1, dan seterusnya.

248
00:12:58,120 --> 00:13:03,010
>> Jadi ini memberi kita indeks ke dalam
anak Array yang kita inginkan.

249
00:13:03,010 --> 00:13:08,890
Sekarang jika indeks ini saat ini nol di
anak-anak, itu berarti bahwa node

250
00:13:08,890 --> 00:13:11,830
saat ini tidak ada
dari jalan itu.

251
00:13:11,830 --> 00:13:15,160
Jadi kita perlu mengalokasikan
node untuk jalan itu.

252
00:13:15,160 --> 00:13:16,550
Itulah yang akan kita lakukan di sini.

253
00:13:16,550 --> 00:13:20,690
>> Jadi kita akan lagi menggunakan calloc yang
fungsi, sehingga kita tidak perlu

254
00:13:20,690 --> 00:13:22,880
nol semua pointer.

255
00:13:22,880 --> 00:13:27,240
Dan kita lagi perlu memeriksa
calloc yang tidak gagal.

256
00:13:27,240 --> 00:13:30,700
Jika calloc tidak gagal, maka kita perlu
untuk membongkar semuanya, tutup kami

257
00:13:30,700 --> 00:13:32,820
kamus, dan kembali palsu.

258
00:13:32,820 --> 00:13:40,050
Jadi dengan asumsi bahwa itu tidak gagal, maka
ini akan membuat anak yang baru bagi kita.

259
00:13:40,050 --> 00:13:41,930
Dan kemudian kami akan pergi ke anak itu.

260
00:13:41,930 --> 00:13:44,960
Kursor kita akan iterate
turun ke anak itu.

261
00:13:44,960 --> 00:13:49,330
>> Sekarang jika ini tidak nol untuk memulai dengan,
maka kursor hanya dapat iterate

262
00:13:49,330 --> 00:13:52,590
turun ke anak itu tanpa benar-benar
harus mengalokasikan apa-apa.

263
00:13:52,590 --> 00:13:56,730
Ini adalah kasus di mana kami pertama kali terjadi
mengalokasikan kata "kucing." Dan

264
00:13:56,730 --> 00:14:00,330
itu berarti ketika kita pergi untuk mengalokasikan
"Bencana," kita tidak perlu membuat

265
00:14:00,330 --> 00:14:01,680
node untuk C-A-T lagi.

266
00:14:01,680 --> 00:14:04,830
Mereka sudah ada.

267
00:14:04,830 --> 00:14:06,080
>> Apa ini lagi?

268
00:14:06,080 --> 00:14:10,480
Ini adalah kondisi di mana c adalah
backslash n, di mana c adalah baris baru.

269
00:14:10,480 --> 00:14:13,710
Ini berarti bahwa kita telah berhasil
menyelesaikan kata.

270
00:14:13,710 --> 00:14:16,860
Sekarang apa yang kita ingin lakukan ketika kita
berhasil menyelesaikan sebuah kata?

271
00:14:16,860 --> 00:14:21,100
Kita akan menggunakan kolom kata ini
dalam struct simpul kami.

272
00:14:21,100 --> 00:14:23,390
Kami ingin menetapkan bahwa untuk benar.

273
00:14:23,390 --> 00:14:27,150
Sehingga menunjukkan bahwa node ini
menunjukkan sukses

274
00:14:27,150 --> 00:14:29,250
kata, kata yang sebenarnya.

275
00:14:29,250 --> 00:14:30,940
>> Sekarang menetapkan bahwa untuk benar.

276
00:14:30,940 --> 00:14:35,150
Kami ingin me-reset kursor kita ke titik
ke awal trie lagi.

277
00:14:35,150 --> 00:14:40,160
Dan akhirnya, kenaikan kamus kami
ukuran, karena kita menemukan pekerjaan lain.

278
00:14:40,160 --> 00:14:43,230
Jadi kita akan terus melakukan itu,
membaca karakter demi karakter,

279
00:14:43,230 --> 00:14:49,150
membangun node baru dalam trie kami dan
untuk setiap kata dalam kamus, sampai

280
00:14:49,150 --> 00:14:54,020
kami akhirnya mencapai C! = EOF, di mana
jika kita keluar dari file.

281
00:14:54,020 --> 00:14:57,050
>> Sekarang ada dua kasus di bawah
yang kita mungkin telah memukul EOF.

282
00:14:57,050 --> 00:15:00,980
Yang pertama adalah jika ada kesalahan
membaca dari file.

283
00:15:00,980 --> 00:15:03,470
Jadi, jika ada kesalahan, kami
perlu melakukan khas.

284
00:15:03,470 --> 00:15:06,460
Membongkar segala sesuatu, dekat
file, kembali palsu.

285
00:15:06,460 --> 00:15:09,810
Dengan asumsi tidak ada kesalahan, yang
hanya berarti kita benar-benar memukul akhir

286
00:15:09,810 --> 00:15:13,750
file, dalam hal ini, kita menutup
mengajukan dan kembali benar karena kita

287
00:15:13,750 --> 00:15:17,330
kamus berhasil dimuat
trie ke kami.

288
00:15:17,330 --> 00:15:20,170
>> Jadi sekarang mari kita periksa cek.

289
00:15:20,170 --> 00:15:25,156
Melihat fungsi cek, kita melihat
bahwa cek akan kembali bool.

290
00:15:25,156 --> 00:15:29,680
Ia mengembalikan true jika kata ini bahwa itu
yang lulus dalam trie kami.

291
00:15:29,680 --> 00:15:32,110
Ia mengembalikan false jika tidak.

292
00:15:32,110 --> 00:15:36,050
Jadi bagaimana Anda menentukan apakah
kata ini dalam trie kita?

293
00:15:36,050 --> 00:15:40,190
>> Kita lihat di sini bahwa, sama seperti sebelumnya,
kita akan menggunakan kursor untuk iterate

294
00:15:40,190 --> 00:15:41,970
melalui trie kami.

295
00:15:41,970 --> 00:15:46,600
Sekarang di sini kita akan iterate
atas seluruh kata kita.

296
00:15:46,600 --> 00:15:50,620
Jadi iterasi kata kita di masa lalu,
kita akan menentukan

297
00:15:50,620 --> 00:15:56,400
indeks ke anak-anak array
sesuai dengan kata braket I. Jadi ini

298
00:15:56,400 --> 00:15:59,670
akan terlihat persis seperti
beban, di mana jika kata [i]

299
00:15:59,670 --> 00:16:03,310
adalah apostrof, maka kita ingin
menggunakan indeks "ALPHABET" - 1.

300
00:16:03,310 --> 00:16:05,350
Karena kita menetapkan bahwa yang
adalah di mana kita akan menyimpan

301
00:16:05,350 --> 00:16:07,100
apostrof.

302
00:16:07,100 --> 00:16:11,780
>> Lain kita akan menggunakan dua kata yang lebih rendah
braket I. Jadi ingat kata yang dapat

303
00:16:11,780 --> 00:16:13,920
memiliki kapitalisasi sewenang-wenang.

304
00:16:13,920 --> 00:16:17,540
Dan jadi kami ingin memastikan bahwa kita
menggunakan versi huruf kecil hal.

305
00:16:17,540 --> 00:16:21,920
Dan kemudian kurangi dari yang 'a' untuk sekali
lagi memberi kita abjad yang

306
00:16:21,920 --> 00:16:23,880
posisi karakter itu.

307
00:16:23,880 --> 00:16:27,680
Sehingga akan menjadi indeks kami
ke anak array.

308
00:16:27,680 --> 00:16:32,420
>> Dan jika itu indeks ke anak-anak
array nol, itu berarti kita

309
00:16:32,420 --> 00:16:34,990
tidak bisa lagi melanjutkan iterasi
trie bawah kami.

310
00:16:34,990 --> 00:16:38,870
Jika itu yang terjadi, kata ini tidak bisa
mungkin berada dalam trie kami.

311
00:16:38,870 --> 00:16:42,340
Karena jika itu, yang akan
berarti akan ada jalan

312
00:16:42,340 --> 00:16:43,510
ke kata itu.

313
00:16:43,510 --> 00:16:45,290
Dan Anda tidak akan menemukan nol.

314
00:16:45,290 --> 00:16:47,850
Jadi menghadapi null, kita kembali palsu.

315
00:16:47,850 --> 00:16:49,840
Kata tersebut tidak ada dalam kamus.

316
00:16:49,840 --> 00:16:53,660
Jika bukan nol, maka kita
akan terus iterasi.

317
00:16:53,660 --> 00:16:57,220
>> Jadi kita akan luar sana kursor
untuk menunjuk ke yang khusus

318
00:16:57,220 --> 00:16:59,760
simpul pada indeks itu.

319
00:16:59,760 --> 00:17:03,150
Kami terus melakukan itu sepanjang
seluruh kata, dengan asumsi

320
00:17:03,150 --> 00:17:03,950
kita tidak pernah memukul null.

321
00:17:03,950 --> 00:17:07,220
Itu berarti kami mampu melewati
seluruh kata dan menemukan

322
00:17:07,220 --> 00:17:08,920
node dalam try kami.

323
00:17:08,920 --> 00:17:10,770
Tapi kami tidak cukup dilakukan belum.

324
00:17:10,770 --> 00:17:12,290
>> Kami tidak ingin hanya kembali benar.

325
00:17:12,290 --> 00:17:14,770
Kami ingin kembali kursor> kata.

326
00:17:14,770 --> 00:17:18,980
Sejak ingat lagi, adalah "kucing" tidak
dalam kamus kami, dan "bencana"

327
00:17:18,980 --> 00:17:22,935
adalah, maka kita akan berhasil kita mendapatkan
melalui kata "kucing." Tapi kursor

328
00:17:22,935 --> 00:17:25,760
kata akan palsu dan tidak benar.

329
00:17:25,760 --> 00:17:30,930
Jadi kita kembali kata kursor untuk menunjukkan
apakah simpul ini sebenarnya sebuah kata.

330
00:17:30,930 --> 00:17:32,470
Dan itu saja untuk cek.

331
00:17:32,470 --> 00:17:34,250
>> Jadi mari kita memeriksa ukuran.

332
00:17:34,250 --> 00:17:37,350
Jadi ukuran akan menjadi cukup mudah
karena, mengingat beban, kami

333
00:17:37,350 --> 00:17:41,430
incrementing ukuran kamus untuk
setiap kata yang kita hadapi.

334
00:17:41,430 --> 00:17:45,350
Jadi ukuran hanya akan
kembali ukuran kamus.

335
00:17:45,350 --> 00:17:47,390
Dan itu saja.

336
00:17:47,390 --> 00:17:50,590
>> Jadi akhirnya kami telah membongkar.

337
00:17:50,590 --> 00:17:55,100
Jadi membongkar, kita akan menggunakan
fungsi rekursif untuk benar-benar melakukan semua

338
00:17:55,100 --> 00:17:56,530
pekerjaan bagi kita.

339
00:17:56,530 --> 00:17:59,340
Jadi fungsi kita akan
dipanggil unloader.

340
00:17:59,340 --> 00:18:01,650
Apa yang unloader akan lakukan?

341
00:18:01,650 --> 00:18:06,580
Kita lihat di sini unloader yang akan
iterate atas semua anak-anak di

342
00:18:06,580 --> 00:18:08,410
simpul tertentu.

343
00:18:08,410 --> 00:18:11,750
Dan jika node anak tidak
null, maka kita akan

344
00:18:11,750 --> 00:18:13,730
membongkar node anak.

345
00:18:13,730 --> 00:18:18,010
>> Jadi ini adalah Anda rekursif membongkar
semua anak-anak kita.

346
00:18:18,010 --> 00:18:21,080
Setelah kami yakin bahwa semua anak-anak kita
telah dibongkar, maka kita

347
00:18:21,080 --> 00:18:25,210
dapat membebaskan diri, sehingga
membongkar diri kita sendiri.

348
00:18:25,210 --> 00:18:29,460
Ini akan bekerja secara rekursif
membongkar seluruh trie.

349
00:18:29,460 --> 00:18:32,850
Dan kemudian setelah itu selesai,
kita hanya bisa kembali benar.

350
00:18:32,850 --> 00:18:34,210
Membongkar tidak bisa gagal.

351
00:18:34,210 --> 00:18:35,710
Kami hanya membebaskan hal.

352
00:18:35,710 --> 00:18:38,870
Jadi setelah kami selesai membebaskan
semuanya, kembali benar.

353
00:18:38,870 --> 00:18:40,320
Dan itu saja.

354
00:18:40,320 --> 00:18:41,080
Nama saya Rob.

355
00:18:41,080 --> 00:18:42,426
Dan ini adalah ejaan.

356
00:18:42,426 --> 00:18:47,830
>> [MUSIC PLAYING]