1
00:00:00,000 --> 00:00:09,700

2
00:00:09,700 --> 00:00:12,140
>> ZAMYLA CHAN: Mari kita membuat
pemeriksa ejaan.

3
00:00:12,140 --> 00:00:16,900
Jika Anda membuka speller.c, maka Anda akan melihat
bahwa sebagian besar fungsi untuk

4
00:00:16,900 --> 00:00:20,810
memeriksa file teks terhadap
kamus sudah dibuat untuk Anda.

5
00:00:20,810 --> 00:00:26,330
. / Ejaan, lewat di teks kamus
mengajukan dan kemudian file teks lain,

6
00:00:26,330 --> 00:00:28,960
akan memeriksa file teks
terhadap kamus.

7
00:00:28,960 --> 00:00:34,160
>> Sekarang, file teks kamus akan berisi
kata-kata yang valid, satu per baris.

8
00:00:34,160 --> 00:00:37,910
Kemudian speller.c akan memanggil Beban
pada file teks kamus.

9
00:00:37,910 --> 00:00:43,650
Ini akan memanggil fungsi yang disebut Memeriksa
setiap kata dalam file teks diinput,

10
00:00:43,650 --> 00:00:46,460
mencetak semua kata yang salah eja.

11
00:00:46,460 --> 00:00:50,030
>> Speller.c juga akan memanggil Ukuran untuk
menentukan jumlah kata dalam

12
00:00:50,030 --> 00:00:53,500
kamus dan memanggil Unload
untuk membebaskan memori.

13
00:00:53,500 --> 00:00:57,600
speller.c juga akan melacak bagaimana
banyak waktu yang digunakan untuk melakukan ini

14
00:00:57,600 --> 00:01:00,560
proses, tapi kita akan
bisa nanti.

15
00:01:00,560 --> 00:01:02,440
>> Jadi apa yang perlu kita lakukan?

16
00:01:02,440 --> 00:01:05,110
Kita perlu mengisi dictionary.c.

17
00:01:05,110 --> 00:01:09,940
Dalam dictionary.c, kita memiliki penolong
fungsi Load, yang memuat

18
00:01:09,940 --> 00:01:10,855
kamus.

19
00:01:10,855 --> 00:01:15,490
Fungsi Periksa, yang memeriksa apakah
kata yang diberikan dalam kamus.

20
00:01:15,490 --> 00:01:19,150
Fungsi Ukuran mengembalikan nomor
kata-kata dalam kamus.

21
00:01:19,150 --> 00:01:24,870
Dan akhirnya, kami telah Membongkar, yang
membebaskan kamus dari memori.

22
00:01:24,870 --> 00:01:27,070
>> Jadi pertama, mari kita menangani beban.

23
00:01:27,070 --> 00:01:32,110
Untuk setiap kata dalam teks kamus
File, Load akan menyimpan kata-kata dalam

24
00:01:32,110 --> 00:01:34,860
struktur data kamus
Anda pilih, baik

25
00:01:34,860 --> 00:01:36,750
hash table atau trie.

26
00:01:36,750 --> 00:01:39,440
Aku akan pergi ke baik di
ini berjalan melalui.

27
00:01:39,440 --> 00:01:43,150
>> Pertama mari kita bicara tentang tabel hash.

28
00:01:43,150 --> 00:01:47,050
Katakanlah Anda memiliki 10 bola bilyar dan
Anda ingin menyimpannya.

29
00:01:47,050 --> 00:01:50,420
Anda mungkin menempatkan mereka semua dalam ember,
dan ketika Anda membutuhkan spesifik

30
00:01:50,420 --> 00:01:54,010
bernomor bola, Anda akan mengambil satu
keluar dari ember pada suatu waktu

31
00:01:54,010 --> 00:01:55,880
mencari bola itu.

32
00:01:55,880 --> 00:01:59,370
Dan dengan hanya 10 bola, Anda harus
mampu menemukan bola dalam waktu yang wajar

33
00:01:59,370 --> 00:02:01,160
jumlah waktu.

34
00:02:01,160 --> 00:02:03,180
>> Tetapi bagaimana jika Anda memiliki 20 bola?

35
00:02:03,180 --> 00:02:05,480
Mungkin butuh waktu lebih lama sekarang.

36
00:02:05,480 --> 00:02:06,180
Bagaimana dengan 100?

37
00:02:06,180 --> 00:02:07,880
1.000?

38
00:02:07,880 --> 00:02:11,590
Sekarang, itu akan jauh lebih mudah jika
Anda memiliki beberapa ember.

39
00:02:11,590 --> 00:02:15,890
Mungkin satu ember untuk bola bernomor nol
melalui sembilan, ember lain untuk

40
00:02:15,890 --> 00:02:18,800
bola bernomor 10 melalui
19, dan seterusnya.

41
00:02:18,800 --> 00:02:22,330
>> Sekarang ketika Anda perlu mencari khusus
bola, Anda bisa secara otomatis

42
00:02:22,330 --> 00:02:26,320
pergi ke salah satu ember tertentu dan
mencari melalui ember itu.

43
00:02:26,320 --> 00:02:29,840
Dan jika setiap kotak memiliki sekitar 10
bola, maka Anda bisa dengan mudah mencari

44
00:02:29,840 --> 00:02:31,790
melalui itu.

45
00:02:31,790 --> 00:02:34,960
>> Sekarang, karena kita sedang berhadapan dengan
kamus, satu ember tunggal untuk

46
00:02:34,960 --> 00:02:41,970
semua kata-kata dalam kamus akan
mungkin jauh terlalu sedikit ember.

47
00:02:41,970 --> 00:02:44,370
Jadi mari kita lihat tabel hash.

48
00:02:44,370 --> 00:02:46,940
>> Anggap saja sebagai array ember.

49
00:02:46,940 --> 00:02:50,370
Dan dalam hal ini, ember
adalah daftar link kami.

50
00:02:50,370 --> 00:02:54,770
Dan kita akan mendistribusikan semua kata-kata kita
antara ini beberapa daftar terkait dalam

51
00:02:54,770 --> 00:02:58,940
cara diatur menggunakan fungsi hash,
yang akan memberitahu kami yang

52
00:02:58,940 --> 00:03:03,720
ember kunci yang diberikan, diberikan
kata, milik.

53
00:03:03,720 --> 00:03:05,960
>> Mari kita mewakili ini secara skematik.

54
00:03:05,960 --> 00:03:11,320
Kotak-kotak biru di sini mengandung nilai-nilai dan
kotak merah menunjukkan nilai lain

55
00:03:11,320 --> 00:03:12,280
pair pointer.

56
00:03:12,280 --> 00:03:14,800
Kami akan menelepon pasangan ini node.

57
00:03:14,800 --> 00:03:18,260
Sekarang, setiap kotak, seperti yang saya katakan
sebelumnya, adalah linked list.

58
00:03:18,260 --> 00:03:21,820
Dalam daftar terkait, setiap node memiliki nilai,
serta pointer ke

59
00:03:21,820 --> 00:03:23,170
nilai berikutnya.

60
00:03:23,170 --> 00:03:26,150
>> Sekarang, berurusan dengan daftar terkait,
itu sangat penting bahwa Anda

61
00:03:26,150 --> 00:03:28,120
tidak kehilangan link apapun.

62
00:03:28,120 --> 00:03:32,250
Dan fakta lain yang perlu diingat adalah bahwa
node terakhir, jika tidak menunjuk ke

63
00:03:32,250 --> 00:03:35,120
node lain, menunjuk ke null.

64
00:03:35,120 --> 00:03:37,970
>> Jadi bagaimana kita merepresentasikan ini di C?

65
00:03:37,970 --> 00:03:40,540
Kami mendefinisikan struct kami di sini.

66
00:03:40,540 --> 00:03:44,850
Dan nilai dalam hal ini adalah
array char panjang.

67
00:03:44,850 --> 00:03:48,880
Panjang ditambah 1, di mana panjang adalah
Panjang maksimum setiap kata, ditambah 1 untuk

68
00:03:48,880 --> 00:03:50,380
null terminator.

69
00:03:50,380 --> 00:03:54,210
Dan kemudian kita memiliki pointer ke
simpul lain yang disebut Next.

70
00:03:54,210 --> 00:03:56,730
>> Jadi mari kita membuat daftar link kecil.

71
00:03:56,730 --> 00:04:00,390
Pertama, Anda akan ingin untuk malloc node,
yang menciptakan ruang dalam memori

72
00:04:00,390 --> 00:04:04,010
ukuran tipe node Anda.

73
00:04:04,010 --> 00:04:06,100
Dan membuat node lain,
lagi mallocing.

74
00:04:06,100 --> 00:04:09,370

75
00:04:09,370 --> 00:04:14,340
>> Sekarang jika Anda ingin memberikan nilai pada sebuah
kata, maka kita bisa mengatakan panah node1

76
00:04:14,340 --> 00:04:18,820
kata sama dengan "Hello." Operator panah ini
dereferences pointer dan

77
00:04:18,820 --> 00:04:20,620
mengakses variabel struct itu.

78
00:04:20,620 --> 00:04:24,330
Dengan cara ini, kita tidak perlu menggunakan kedua
titik dan operator bintang.

79
00:04:24,330 --> 00:04:30,100
>> Jadi saya memiliki kata panah node2 sama
"Dunia." Dan di sana, nilai-nilai yang

80
00:04:30,100 --> 00:04:33,110
dihuni pada kelenjar saya.

81
00:04:33,110 --> 00:04:38,780
Untuk membuat link, saya akan lulus dalam node1
panah di sebelah, bahwa bintang mengakses node,

82
00:04:38,780 --> 00:04:44,160
bahwa node pointer, sama node2,
menunjuk node1 untuk Node2 dua.

83
00:04:44,160 --> 00:04:46,360
Dan di sana kita memiliki sebuah linked list.

84
00:04:46,360 --> 00:04:51,480
>> Jadi itu hanya satu linked list, tetapi
tabel hash adalah seluruh array

85
00:04:51,480 --> 00:04:52,520
terkait daftar.

86
00:04:52,520 --> 00:04:55,920
Nah, kita akan memiliki node yang sama
struktur seperti sebelumnya.

87
00:04:55,920 --> 00:05:00,140
Tetapi jika kita ingin tabel hash yang sebenarnya,
maka kita hanya bisa membuat pointer simpul

88
00:05:00,140 --> 00:05:01,330
Array di sini.

89
00:05:01,330 --> 00:05:04,940
Sebagai contoh, ukuran 500.

90
00:05:04,940 --> 00:05:08,910
>> Sekarang pemberitahuan, ada akan menjadi perdagangan
off antara ukuran Anda

91
00:05:08,910 --> 00:05:11,280
tabel hash dan ukuran
daftar Anda terhubung.

92
00:05:11,280 --> 00:05:15,640
Jika Anda memiliki jumlah yang sangat tinggi dari
ember, membayangkan harus menjalankan kembali

93
00:05:15,640 --> 00:05:18,230
dan sebagainya dalam antrean untuk
menemukan ember Anda.

94
00:05:18,230 --> 00:05:21,530
Tapi Anda juga tidak ingin sejumlah kecil
ember, karena dengan begitu kita kembali ke

95
00:05:21,530 --> 00:05:26,850
masalah asli dari bagaimana memiliki
terlalu banyak bola di ember kami.

96
00:05:26,850 --> 00:05:30,480
>> OK, tapi mana bola kami pergi?

97
00:05:30,480 --> 00:05:33,150
Yah, pertama-tama kita perlu
memiliki bola, kan?

98
00:05:33,150 --> 00:05:39,130
Jadi mari kita malloc node untuk setiap
kata baru yang kita miliki.

99
00:05:39,130 --> 00:05:42,900
simpul * new_node equals
malloc (sizeof (node)).

100
00:05:42,900 --> 00:05:46,760
>> Sekarang bahwa kita memiliki struktur ini, kita
dapat memindai, menggunakan fungsi

101
00:05:46,760 --> 00:05:51,850
fscanf, string dari file kami, jika
itu adalah file kamus, ke

102
00:05:51,850 --> 00:05:55,780
new_node panah kata, di mana new_node
Kata panah adalah kami

103
00:05:55,780 --> 00:05:58,110
tujuan dari kata itu.

104
00:05:58,110 --> 00:06:01,900
>> Selanjutnya, kita akan ingin hash yang
kata dengan menggunakan fungsi hash.

105
00:06:01,900 --> 00:06:05,860
Sebuah fungsi hash mengambil string
dan mengembalikan indeks.

106
00:06:05,860 --> 00:06:09,760
Dalam hal ini, indeks harus
kurang dari jumlah

107
00:06:09,760 --> 00:06:11,440
ember yang Anda miliki.

108
00:06:11,440 --> 00:06:14,600
>> Sekarang, fungsi hash, ketika Anda mencoba
untuk menemukan satu dan menciptakan salah satu

109
00:06:14,600 --> 00:06:17,890
Anda sendiri, ingatlah bahwa mereka
harus deterministik.

110
00:06:17,890 --> 00:06:22,420
Itu berarti bahwa nilai yang sama perlu
memetakan ke ember yang sama setiap kali

111
00:06:22,420 --> 00:06:23,800
bahwa Anda hash itu.

112
00:06:23,800 --> 00:06:25,300
>> Ini semacam seperti perpustakaan.

113
00:06:25,300 --> 00:06:28,560
Ketika Anda mengambil sebuah buku, yang didasarkan pada
Penulis, Anda tahu mana rak seharusnya

114
00:06:28,560 --> 00:06:31,890
terus, apakah itu nomor rak
satu, dua, atau tiga.

115
00:06:31,890 --> 00:06:36,280
Dan buku yang akan selalu menjadi milik pada
salah satu rak, dua, atau tiga.

116
00:06:36,280 --> 00:06:39,460

117
00:06:39,460 --> 00:06:43,810
>> Jadi, jika new_node panah kata memiliki
kata dari kamus Anda, maka

118
00:06:43,810 --> 00:06:47,770
hashing new_node panah kata akan
memberi kita indeks dari

119
00:06:47,770 --> 00:06:49,370
ember tabel hash.

120
00:06:49,370 --> 00:06:54,040
Dan kemudian kita akan memasukkan itu ke dalam
linked list tertentu ditunjukkan oleh

121
00:06:54,040 --> 00:06:56,060
nilai fungsi hash kami kembali.

122
00:06:56,060 --> 00:06:59,070
>> Mari kita lihat contoh
memasukkan node ke dalam

123
00:06:59,070 --> 00:07:01,750
mulai dari linked list.

124
00:07:01,750 --> 00:07:06,930
Jika kepala adalah pointer node yang menunjukkan
awal terkait

125
00:07:06,930 --> 00:07:12,420
daftar, dan new_node menunjukkan baru
node yang ingin Anda masuk, hanya

126
00:07:12,420 --> 00:07:17,340
menugaskan kepala ke new_node akan kehilangan
link ke seluruh daftar.

127
00:07:17,340 --> 00:07:19,330
Jadi kita tidak ingin melakukan ini.

128
00:07:19,330 --> 00:07:22,160
>> Sebaliknya, kita ingin memastikan
bahwa kita berpegang pada setiap

129
00:07:22,160 --> 00:07:23,550
node tunggal dalam program kami.

130
00:07:23,550 --> 00:07:29,560
Jadi berjalan new_node panah equals berikutnya
kepala dan kemudian kepala sama new_node

131
00:07:29,560 --> 00:07:34,470
akan mempertahankan semua
link dan tidak kehilangan apapun.

132
00:07:34,470 --> 00:07:39,330
>> Tetapi bagaimana jika Anda ingin daftar menjadi
diurutkan, karena memiliki sebuah diurutkan terkait

133
00:07:39,330 --> 00:07:42,910
Daftar mungkin lebih mudah untuk
mencari nanti?

134
00:07:42,910 --> 00:07:46,020
Nah, untuk itu, Anda harus tahu
bagaimana untuk melintasi daftar terkait.

135
00:07:46,020 --> 00:07:51,210
>> Untuk melintasi sebuah linked list, mari kita
pointer node, node *, untuk bertindak sebagai

136
00:07:51,210 --> 00:07:54,120
kursor Anda, yang menunjukkan
Anda berada di simpul, mulai

137
00:07:54,120 --> 00:07:55,460
pada elemen pertama.

138
00:07:55,460 --> 00:08:01,070
Looping hingga kursor adalah null, kita bisa
melakukan proses tertentu dan kemudian

139
00:08:01,070 --> 00:08:04,330
memajukan kursor ketika kita perlu
menggunakan kursor nilai panah.

140
00:08:04,330 --> 00:08:08,820
>> Ingat, ini adalah hal yang sama seperti
mengatakan star kursor, dereferencing

141
00:08:08,820 --> 00:08:13,480
kursor, kemudian menggunakan
Nilai dot operator.

142
00:08:13,480 --> 00:08:19,000
Jadi memperbarui kursor dengan menetapkan
kursor ke kursor panah berikutnya.

143
00:08:19,000 --> 00:08:24,960
>> Katakanlah Anda menentukan bahwa D menjadi di
antara C dan E. Untuk menyisipkan node,

144
00:08:24,960 --> 00:08:30,030
memiliki titik D new_node ke
simpul E, yang merupakan kursor berikutnya.

145
00:08:30,030 --> 00:08:36,409
Dan kemudian C, kursor, kemudian arahkan
D. Dengan begitu, Anda mempertahankan daftar.

146
00:08:36,409 --> 00:08:41,080
Berhati-hatilah untuk tidak kehilangan link Anda dengan
memindahkan kursor panah di samping D

147
00:08:41,080 --> 00:08:43,929
segera.

148
00:08:43,929 --> 00:08:44,620
>> Baik.

149
00:08:44,620 --> 00:08:48,920
Jadi itulah bagaimana Anda dapat menyisipkan node,
beban mereka dalam, kata-kata beban ke mereka

150
00:08:48,920 --> 00:08:51,600
node, dan memasukkan mereka
ke dalam tabel hash Anda.

151
00:08:51,600 --> 00:08:53,580
Jadi sekarang mari kita lihat mencoba.

152
00:08:53,580 --> 00:08:58,540
>> Dalam trie, setiap node akan mengandung
array dari pointer node, satu untuk setiap

153
00:08:58,540 --> 00:09:02,260
huruf dalam alfabet
ditambah apostrof.

154
00:09:02,260 --> 00:09:06,150
Dan setiap elemen dalam array
akan menunjuk ke node lain.

155
00:09:06,150 --> 00:09:10,130
Jika node yang adalah null, maka surat itu
tidak akan menjadi huruf berikutnya

156
00:09:10,130 --> 00:09:15,690
setiap kata secara berurutan, karena setiap
kata menunjukkan apakah itu yang terakhir

157
00:09:15,690 --> 00:09:18,160
karakter dari sebuah kata atau tidak.

158
00:09:18,160 --> 00:09:19,750
>> Mari kita lihat diagram.

159
00:09:19,750 --> 00:09:22,260
Mudah-mudahan hal-hal yang akan
menjadi sedikit lebih jelas.

160
00:09:22,260 --> 00:09:27,210
Dalam diagram ini, kita melihat bahwa hanya
huruf tertentu dan substring tertentu

161
00:09:27,210 --> 00:09:28,190
sedang terdaftar keluar.

162
00:09:28,190 --> 00:09:32,500
Jadi, Anda dapat mengikuti jalur tertentu, dan
semua orang jalan akan membawa Anda ke

163
00:09:32,500 --> 00:09:34,020
kata yang berbeda.

164
00:09:34,020 --> 00:09:37,630
>> Jadi bagaimana kita merepresentasikan ini di C?

165
00:09:37,630 --> 00:09:41,910
Nah, setiap simpul sekarang akan memiliki
nilai Boolean yang menunjukkan apakah

166
00:09:41,910 --> 00:09:46,580
simpul itu adalah akhir dari
kata yang diberikan atau tidak.

167
00:09:46,580 --> 00:09:50,690
Dan kemudian juga akan memiliki sebuah array
simpul pointer disebut anak-anak, dan

168
00:09:50,690 --> 00:09:53,440
ada akan menjadi 27 dari mereka.

169
00:09:53,440 --> 00:09:56,510
Dan ingat, Anda juga akan ingin
melacak simpul pertama Anda.

170
00:09:56,510 --> 00:09:59,830
Kita akan memanggil akar itu.

171
00:09:59,830 --> 00:10:01,690
>> Jadi itulah struktur trie.

172
00:10:01,690 --> 00:10:05,630
Bagaimana kami mewakili ini
sebagai kamus?

173
00:10:05,630 --> 00:10:09,890
Nah, untuk memuat kata-kata dalam, untuk setiap
kata kamus, Anda akan ingin

174
00:10:09,890 --> 00:10:11,960
iterate melalui trie.

175
00:10:11,960 --> 00:10:16,170
Dan setiap elemen pada anak
sesuai dengan huruf yang berbeda.

176
00:10:16,170 --> 00:10:21,660
>> Jadi memeriksa nilai pada anak-anak
Indeks i, di mana saya mewakili

177
00:10:21,660 --> 00:10:24,840
Indeks spesifik surat yang
Anda mencoba untuk memasukkan.

178
00:10:24,840 --> 00:10:28,980
Nah, jika itu nol, maka Anda akan ingin
malloc node baru dan memiliki anak

179
00:10:28,980 --> 00:10:31,110
i menunjuk ke simpul tersebut.

180
00:10:31,110 --> 00:10:35,630
>> Jika tidak null, maka itu berarti bahwa
cabang yang diberikan, yang diberikan

181
00:10:35,630 --> 00:10:37,350
substring, sudah ada.

182
00:10:37,350 --> 00:10:40,160
Jadi Anda hanya akan pindah ke yang
node baru dan melanjutkan.

183
00:10:40,160 --> 00:10:43,220
Jika Anda berada di akhir kata yang
Anda mencoba untuk memuat dalam

184
00:10:43,220 --> 00:10:48,120
kamus, maka Anda dapat mengatur bahwa
node saat ini bahwa Anda berada di true.

185
00:10:48,120 --> 00:10:51,550
>> Jadi mari kita lihat contoh memasukkan
kata "fox" ke kami

186
00:10:51,550 --> 00:10:53,070
kamus.

187
00:10:53,070 --> 00:10:56,110
Berpura-pura kita mulai dengan
kamus kosong.

188
00:10:56,110 --> 00:11:01,610
Surat pertama, F, akan berlokasi
indeks anak lima dari akar

189
00:11:01,610 --> 00:11:03,700
anak array.

190
00:11:03,700 --> 00:11:05,430
Jadi kita memasukkan yang masuk

191
00:11:05,430 --> 00:11:14,610
>> Huruf O kemudian akan pada anak-anak
Indeks 15, setelah itu F. Dan kemudian X

192
00:11:14,610 --> 00:11:20,180
akan lebih di bawah itu, bercabang
off dari anak-anak O.

193
00:11:20,180 --> 00:11:24,120
Dan kemudian karena X adalah huruf terakhir
dari kata "rubah," maka aku akan

194
00:11:24,120 --> 00:11:27,210
warna hijau yang menunjukkan bahwa
itu adalah akhir kata.

195
00:11:27,210 --> 00:11:32,880
Dalam C, yang akan menetapkan Is
Kata Boolean dengan nilai sebenarnya.

196
00:11:32,880 --> 00:11:36,780
>> Sekarang bagaimana jika kata berikutnya yang Anda
loading di adalah kata "foo"?

197
00:11:36,780 --> 00:11:41,490
Nah, Anda tidak perlu malloc lagi
ruang untuk F atau O, karena

198
00:11:41,490 --> 00:11:42,990
yang sudah ada.

199
00:11:42,990 --> 00:11:45,910
Tapi O terakhir di foo?

200
00:11:45,910 --> 00:11:47,320
Yang satu itu, Anda harus malloc.

201
00:11:47,320 --> 00:11:52,390
Membuat node baru untuk itu, pengaturan
Is Firman Boolean true.

202
00:11:52,390 --> 00:11:57,340
>> Jadi sekarang mari kita masukkan "anjing." Anjing akan
mulai dengan indeks tiga dari akar

203
00:11:57,340 --> 00:12:00,520
anak-anak, karena D belum
telah dibuat.

204
00:12:00,520 --> 00:12:04,990
Dan kami akan mengikuti proses yang sama seperti
sebelumnya, menciptakan anjing substring,

205
00:12:04,990 --> 00:12:10,400
mana yang G berwarna hijau karena
itulah akhir dari sebuah kata.

206
00:12:10,400 --> 00:12:13,160
>> Sekarang, bagaimana jika kita ingin memasukkan "melakukan"?

207
00:12:13,160 --> 00:12:17,150
Nah, ini adalah substring dari anjing, sehingga
kita tidak perlu malloc lagi.

208
00:12:17,150 --> 00:12:20,800
Tapi kita perlu untuk menunjukkan di mana kita sudah
mencapai akhir dari kata itu.

209
00:12:20,800 --> 00:12:24,020
Jadi O akan berwarna hijau.

210
00:12:24,020 --> 00:12:27,810
Melanjutkan proses bahwa untuk setiap satu
kata dalam kamus Anda, Anda sudah

211
00:12:27,810 --> 00:12:32,120
dimuat dalam menjadi baik Anda
hash table atau trie Anda.

212
00:12:32,120 --> 00:12:37,530
>> speller.c akan lulus dalam string untuk
dictionary.c untuk memeriksa mereka.

213
00:12:37,530 --> 00:12:41,140
Sekarang, fungsi Periksa harus beroperasi
di bawah kasus ketidakpekaan.

214
00:12:41,140 --> 00:12:45,980
Itu berarti bahwa huruf kapital dan
huruf kecil dan campuran keduanya

215
00:12:45,980 --> 00:12:50,670
semua harus sama dengan benar jika ada
kombinasi yang ada di

216
00:12:50,670 --> 00:12:51,880
kamus.

217
00:12:51,880 --> 00:12:55,580
Anda juga dapat mengasumsikan bahwa string adalah
hanya akan berisi abjad

218
00:12:55,580 --> 00:12:58,200
karakter atau apostrof.

219
00:12:58,200 --> 00:13:02,490
>> Jadi mari kita lihat bagaimana Anda dapat memeriksa
dengan struktur tabel hash.

220
00:13:02,490 --> 00:13:07,330
Nah, jika kata itu ada, maka
dapat ditemukan dalam tabel hash.

221
00:13:07,330 --> 00:13:12,240
Jadi maka Anda dapat mencoba untuk menemukan bahwa
kata dalam ember yang relevan.

222
00:13:12,240 --> 00:13:14,480
>> Jadi yang akan ember kata yang berada di?

223
00:13:14,480 --> 00:13:20,060
Nah, Anda akan mendapatkan nomor, indeks yang
ember, dengan hashing kata itu

224
00:13:20,060 --> 00:13:23,690
dan kemudian mencari dalam linked list,
melintasi melalui seluruh yang

225
00:13:23,690 --> 00:13:28,060
linked list, menggunakan String
Bandingkan fungsi.

226
00:13:28,060 --> 00:13:31,940
>> Jika akhir linked list adalah
tercapai, yang berarti bahwa kursor Anda

227
00:13:31,940 --> 00:13:36,030
mencapai nol, maka kata tersebut tidak
dapat ditemukan dalam kamus.

228
00:13:36,030 --> 00:13:39,090
Ini tidak akan dalam ember lain.

229
00:13:39,090 --> 00:13:43,020
Jadi di sini, Anda mungkin akan melihat bagaimana mungkin ada
menjadi trade-off antara memiliki baik

230
00:13:43,020 --> 00:13:46,280
diurutkan daftar terkait atau yang tidak dipisahkan.

231
00:13:46,280 --> 00:13:51,180
Entah akan mengambil lebih banyak waktu selama
memuat atau lebih waktu selama check.

232
00:13:51,180 --> 00:13:53,560
>> Bagaimana mungkin Anda check-in
struktur trie?

233
00:13:53,560 --> 00:13:56,370
Kita akan melakukan perjalanan ke bawah
dalam trie.

234
00:13:56,370 --> 00:14:00,390
Untuk setiap huruf dalam kata diinput
bahwa kita sedang memeriksa, kita akan pergi ke yang

235
00:14:00,390 --> 00:14:03,280
sesuai elemen dalam anak-anak.

236
00:14:03,280 --> 00:14:07,770
>> Jika unsur yang null, maka berarti bahwa
bahwa tidak ada substring

237
00:14:07,770 --> 00:14:11,110
mengandung kata masukan kami, jadi
kata salah eja.

238
00:14:11,110 --> 00:14:15,140
Jika tidak null, kita bisa pindah ke
huruf berikutnya dari kata yang kita

239
00:14:15,140 --> 00:14:18,850
memeriksa dan melanjutkan proses ini
sampai kita mencapai akhir

240
00:14:18,850 --> 00:14:20,350
kata input.

241
00:14:20,350 --> 00:14:23,330
Dan kemudian kita dapat memeriksa
Apakah jika Firman adalah benar.

242
00:14:23,330 --> 00:14:24,610
Jika ya, maka besar.

243
00:14:24,610 --> 00:14:25,590
Kata benar.

244
00:14:25,590 --> 00:14:30,890
Tapi jika tidak, meskipun substring yang
ada dalam trie, kata tersebut

245
00:14:30,890 --> 00:14:32,250
salah eja.

246
00:14:32,250 --> 00:14:36,590
>> Ketika fungsi Ukuran disebut, ukuran
harus mengembalikan jumlah kata yang

247
00:14:36,590 --> 00:14:39,110
dalam kamus Anda diberikan
struktur data.

248
00:14:39,110 --> 00:14:42,780
Jadi jika Anda menggunakan tabel hash, Anda
dapat pergi melalui setiap satu

249
00:14:42,780 --> 00:14:45,860
linked list dalam setiap satu
ember menghitung jumlah

250
00:14:45,860 --> 00:14:47,130
kata-kata yang ada.

251
00:14:47,130 --> 00:14:49,940
Jika Anda menggunakan trie, Anda dapat
pergi melalui setiap non nol

252
00:14:49,940 --> 00:14:52,030
jalan di trie Anda.

253
00:14:52,030 --> 00:14:56,420
Atau saat Anda sedang memuat kamus
dalam, mungkin Anda dapat melacak bagaimana

254
00:14:56,420 --> 00:14:58,760
banyak kata-kata Anda memuat masuk

255
00:14:58,760 --> 00:15:03,180
>> Setelah selesai memeriksa speller.c
file teks terhadap kamus, maka

256
00:15:03,180 --> 00:15:08,010
itu dilakukan dan sehingga panggilan Membongkar, di mana
tugas Anda adalah untuk membebaskan sesuatu

257
00:15:08,010 --> 00:15:09,500
bahwa Anda telah malloced.

258
00:15:09,500 --> 00:15:14,420
Jadi, jika Anda menggunakan tabel hash, maka Anda
harus berhati-hati untuk menghindari

259
00:15:14,420 --> 00:15:18,830
kebocoran memori dengan tidak membebaskan apa-apa
prematur dan memegang setiap

260
00:15:18,830 --> 00:15:20,780
link tunggal sebelum Anda gratis.

261
00:15:20,780 --> 00:15:24,680

262
00:15:24,680 --> 00:15:30,100
>> Jadi untuk setiap elemen dalam tabel hash
dan untuk setiap node dalam linked list,

263
00:15:30,100 --> 00:15:32,370
Anda akan ingin untuk membebaskan simpul tersebut.

264
00:15:32,370 --> 00:15:34,970
Bagaimana Anda pergi tentang membebaskan
linked list?

265
00:15:34,970 --> 00:15:38,570
Mengatur node pointer kursor ke
kepala, untuk awal

266
00:15:38,570 --> 00:15:43,100
linked list, maka saat kursor Anda
tidak null, Anda dapat mengatur sementara

267
00:15:43,100 --> 00:15:45,610
simpul pointer kursor Anda.

268
00:15:45,610 --> 00:15:48,370
Kemudian memajukan kursor.

269
00:15:48,370 --> 00:15:52,950
Dan kemudian Anda dapat bebas yang sementara
nilai sementara masih berpegangan pada

270
00:15:52,950 --> 00:15:55,650
semuanya setelah itu.

271
00:15:55,650 --> 00:15:57,800
>> Bagaimana jika Anda menggunakan trie?

272
00:15:57,800 --> 00:16:00,410
Maka cara terbaik untuk melakukan hal ini
adalah untuk membongkar dari sangat

273
00:16:00,410 --> 00:16:02,290
bawah ke atas.

274
00:16:02,290 --> 00:16:06,920
Dengan bepergian ke serendah mungkin
node, Anda dapat membebaskan semua pointer di

275
00:16:06,920 --> 00:16:11,430
bahwa anak-anak dan kemudian mundur
ke atas, membebaskan semua elemen dalam semua

276
00:16:11,430 --> 00:16:15,610
anak-anak array, sampai
anda menekan simpul akar utama Anda.

277
00:16:15,610 --> 00:16:18,920
Di sinilah Rekursi
akan berguna.

278
00:16:18,920 --> 00:16:22,780
>> Untuk memastikan bahwa Anda mungkin pernah dibebaskan
segala sesuatu yang telah Anda malloced,

279
00:16:22,780 --> 00:16:24,400
Anda dapat menggunakan Valgrind.

280
00:16:24,400 --> 00:16:28,640
Menjalankan Valgrind akan menjalankan program Anda
menghitung berapa banyak byte memori

281
00:16:28,640 --> 00:16:32,440
Anda menggunakan dan memastikan bahwa Anda telah
membebaskan mereka semua, memberitahu Anda

282
00:16:32,440 --> 00:16:34,530
di mana Anda mungkin memiliki
lupa gratis.

283
00:16:34,530 --> 00:16:38,390
Jadi menjalankan itu dan sekali Valgrind memberitahu Anda
dan memberi Anda pergi ke depan, kemudian

284
00:16:38,390 --> 00:16:41,160
Anda telah selesai membongkar.

285
00:16:41,160 --> 00:16:44,420
>> Sekarang, beberapa tips sebelum Anda pergi
off dan mulai menerapkan Anda

286
00:16:44,420 --> 00:16:46,260
kamus.

287
00:16:46,260 --> 00:16:49,650
Saya akan merekomendasikan untuk lulus dalam lebih kecil
kamus ketika Anda mencoba untuk menguji

288
00:16:49,650 --> 00:16:52,620
hal-hal dan debugging dengan GDP.

289
00:16:52,620 --> 00:16:58,550
Penggunaan ejaan adalah. / Ejaan, sebuah
kamus opsional, dan kemudian teks.

290
00:16:58,550 --> 00:17:01,550
>> Secara default, itu beban di
kamus besar.

291
00:17:01,550 --> 00:17:06,670
Jadi, Anda mungkin ingin lulus dalam kecil
kamus, atau mungkin bahkan membuat Anda

292
00:17:06,670 --> 00:17:11,819
sendiri, menyesuaikan kamus Anda
dan file teks Anda.

293
00:17:11,819 --> 00:17:15,950
>> Dan akhirnya, saya akan juga merekomendasikan
untuk mengambil pena dan kertas dan menarik

294
00:17:15,950 --> 00:17:20,490
hal-hal sebelum, selama, dan setelah
Anda telah menulis semua kode Anda.

295
00:17:20,490 --> 00:17:24,170
Pastikan bahwa Anda punya
mereka pointer tepat.

296
00:17:24,170 --> 00:17:26,480
>> Saya berharap yang terbaik keberuntungan.

297
00:17:26,480 --> 00:17:29,690
Dan setelah Anda selesai, jika Anda ingin
untuk menantang papan besar dan

298
00:17:29,690 --> 00:17:34,390
melihat seberapa cepat program Anda dibandingkan dengan
teman sekelas Anda, maka saya mendorong

299
00:17:34,390 --> 00:17:35,960
Anda memeriksa yang keluar.

300
00:17:35,960 --> 00:17:39,220
>> Dengan itu, Anda telah selesai
yang PSet ejaan.

301
00:17:39,220 --> 00:17:41,800
Nama saya adalah Zamyla, dan ini adalah CS50.

302
00:17:41,800 --> 00:17:49,504