1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Walkthrough - Masalah Set 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Universiti Harvard]

3
00:00:04,870 --> 00:00:07,190
[Ini adalah CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Semua hak. Hello, semua orang, dan mengalu-alukan ke 5 Walkthrough.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 adalah salah ejaan, di mana kita akan membuat pemeriksa ejaan.

6
00:00:17,400 --> 00:00:21,030
Ejaan dam adalah amat penting.

7
00:00:21,030 --> 00:00:23,390
Adakah ini pernah berlaku kepada anda?

8
00:00:23,390 --> 00:00:27,170
Anda bekerja sangat, sangat simpan pada kertas untuk pertembungan

9
00:00:27,170 --> 00:00:33,120
dan kemudian masih akhirnya mendapat rade cahaya sangat seperti D atau D =

10
00:00:33,120 --> 00:00:39,390
dan semua kerana anda adalah spoiler sosis yg mengandung cincangan dalam perkataan paus luas.

11
00:00:39,390 --> 00:00:44,710
Ya, proofreading lada anda adalah satu perkara, mati pucuk penuh.

12
00:00:44,710 --> 00:00:49,140
Ini adalah masalah yang menjejaskan waras, pelajar waras.

13
00:00:49,140 --> 00:00:56,260
Saya pernah diberitahu oleh penyiksa gred sith saya bahawa saya tidak akan masuk ke dalam rakan sekerja yang baik.

14
00:00:56,260 --> 00:01:00,250
Dan itu semua yang pernah saya mahu, itu semua mana-mana kanak-kanak mahu pada usia saya,

15
00:01:00,250 --> 00:01:04,569
hanya untuk masuk ke dalam rakan sekerja yang baik.

16
00:01:04,569 --> 00:01:12,720
Dan bukan sahaja mana-mana rakan sekerja. Saya mahu pergi kepada rakan sekerja Ivory satu undang-undang.

17
00:01:12,720 --> 00:01:18,360
Jadi jika saya tidak penambahbaikan, pergi akan menjadi impian saya pergi ke Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, atau Penjara - anda tahu, di Penjara New Jersey.

19
00:01:22,730 --> 00:01:25,170
Jadi saya mendapat diri saya pemeriksa ejaan.

20
00:01:25,170 --> 00:01:29,380
Itulah petikan sedikit dari salah satu artis perkataan kegemaran saya bercakap, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Bagaimanapun, seperti katanya, kepentingan mempunyai ejaan pemeriksa adalah sangat penting.

22
00:01:34,630 --> 00:01:39,440
>> Jadi dialu-alukan untuk 5 Walkthrough, di mana kita akan bercakap tentang pset5: salah ejaan,

23
00:01:39,440 --> 00:01:44,300
di mana kita akan membuat kita sendiri ejaan pemeriksa.

24
00:01:44,300 --> 00:01:50,880
Toolbox untuk minggu ini, kod pengedaran, akan menjadi penting untuk melihat

25
00:01:50,880 --> 00:01:54,950
hanya untuk memahami fungsi yang berbeza yang kamus anda akan mempunyai.

26
00:01:54,950 --> 00:02:01,500
Kami sebenarnya akan mempunyai pelbagai c fail yang bersama-sama membuat pset kami.

27
00:02:01,500 --> 00:02:05,420
Dan sebagainya mencari melalui aspek-aspek yang berbeza, walaupun kita sebenarnya tidak menyunting

28
00:02:05,420 --> 00:02:10,770
salah satu fail, speller.c, mengetahui bagaimana ia berfungsi dengan berhubung dengan dictionary.c,

29
00:02:10,770 --> 00:02:14,100
yang kita akan menulis, akan menjadi cukup penting.

30
00:02:14,100 --> 00:02:16,970
Spec pset juga mengandungi banyak maklumat yang berguna

31
00:02:16,970 --> 00:02:21,360
dari segi perkara yang anda boleh menganggap, peraturan dan perkara-perkara seperti itu,

32
00:02:21,360 --> 00:02:24,710
jadi pastikan untuk membaca spec pset teliti bagi tips.

33
00:02:24,710 --> 00:02:29,310
Dan apabila keraguan peraturan atau sesuatu seperti itu, maka sentiasa merujuk kepada spesifikasi pset

34
00:02:29,310 --> 00:02:31,550
atau Bincangkan.

35
00:02:31,550 --> 00:02:34,060
Pset ini akan banyak bergantung pada petunjuk,

36
00:02:34,060 --> 00:02:37,890
jadi kami mahu memastikan bahawa kita memahami perbezaan antara bintang menambah

37
00:02:37,890 --> 00:02:41,680
di hadapan nama dan penunjuk ampersands, bagaimana untuk membebaskan mereka, dan lain-lain

38
00:02:41,680 --> 00:02:47,550
Jadi, menjadi tuan petunjuk akan menjadi sangat membantu dalam set masalah ini.

39
00:02:47,550 --> 00:02:50,460
Kami akan meneliti senarai berkaitan sedikit lebih,

40
00:02:50,460 --> 00:02:57,790
di mana kita mempunyai unsur-unsur yang kita panggil nod yang mempunyai kedua-dua nilai serta penunjuk

41
00:02:57,790 --> 00:03:02,520
ke nod seterusnya, dan sebagainya dasarnya menghubungkan unsur-unsur yang berbeza salah satu selepas yang lain.

42
00:03:02,520 --> 00:03:07,190
Terdapat beberapa pilihan yang berbeza melaksanakan kamus sebenar anda.

43
00:03:07,190 --> 00:03:13,150
Kami akan melihat kepada dua kaedah utama, yang adalah jadual hash dan kemudian cuba.

44
00:03:13,150 --> 00:03:17,660
Dalam kedua-dua mereka, mereka melibatkan beberapa jenis tanggapan senarai berkaitan

45
00:03:17,660 --> 00:03:20,790
di mana anda telah elemen dikaitkan antara satu sama lain.

46
00:03:20,790 --> 00:03:25,640
Dan jadi kita akan melihat bagaimana anda mungkin tidak dapat beroperasi di sekitar senarai dikaitkan,

47
00:03:25,640 --> 00:03:29,680
mencipta mereka, mengemudi dari segi bagaimana untuk, misalnya, memasukkan nod ke dalamnya

48
00:03:29,680 --> 00:03:32,760
atau percuma di nod serta.

49
00:03:32,760 --> 00:03:34,740
Dari segi nod membebaskan, yang benar-benar penting

50
00:03:34,740 --> 00:03:37,700
bahawa apabila kita malloc ingatan, selepas itu kita membebaskannya.

51
00:03:37,700 --> 00:03:42,910
Jadi kita mahu pastikan bahawa penunjuk tidak pergi unfreed, bahawa kita tidak mempunyai sebarang kebocoran memori.

52
00:03:42,910 --> 00:03:48,330
Kami akan memperkenalkan alat dipanggil Valgrind yang menjalankan program anda

53
00:03:48,330 --> 00:03:52,260
dan cek sama ada semua memori yang anda memperuntukkan kemudian dibebaskan.

54
00:03:52,260 --> 00:03:59,080
Pset anda hanya melengkapkan apabila ia berfungsi dan ia mempunyai kefungsian penuh,

55
00:03:59,080 --> 00:04:03,990
tetapi juga, Valgrind memberitahu anda bahawa anda tidak menemui sebarang kebocoran memori.

56
00:04:03,990 --> 00:04:06,690
Akhirnya, bagi pset ini, saya benar-benar ingin tekankan -

57
00:04:06,690 --> 00:04:11,360
Maksud saya, seperti biasa, saya pasti penyokong menggunakan pen dan kertas untuk set masalah anda,

58
00:04:11,360 --> 00:04:14,840
tetapi untuk yang satu ini, saya berfikir bahawa pen dan kertas akan menjadi penting terutamanya

59
00:04:14,840 --> 00:04:19,000
apabila anda mahu lukisan anak panah untuk perkara dan memahami bagaimana ia berfungsi.

60
00:04:19,000 --> 00:04:24,440
Jadi pasti cuba untuk menggunakan pen dan kertas untuk menarik perkara-perkara yang keluar sebelum anda mendapat kod

61
00:04:24,440 --> 00:04:26,970
kerana ia boleh mendapatkan sedikit kotor.

62
00:04:26,970 --> 00:04:30,700
>> Pertama, mari kita pergi ke senarai berkaitan sedikit.

63
00:04:30,700 --> 00:04:35,510
Berkaitan senarai terdiri daripada nod, di mana setiap nod mempunyai nilai yang dikaitkan dengannya,

64
00:04:35,510 --> 00:04:39,810
serta penunjuk kepada nod berikutnya selepas ia.

65
00:04:39,810 --> 00:04:43,680
Beberapa perkara penting dengan senarai yang dikaitkan adalah bahawa kita perlu ingat

66
00:04:43,680 --> 00:04:48,810
mana nod pertama kami adalah, dan kemudian apabila kita tahu di mana nod pertama adalah,

67
00:04:48,810 --> 00:04:52,990
yang cara kita boleh mengakses nod nod mata pertama untuk

68
00:04:52,990 --> 00:04:55,850
dan kemudian selepas itu dan satu selepas itu.

69
00:04:55,850 --> 00:05:00,340
Dan kemudian elemen terakhir dalam senarai dikaitkan anda adalah penunjuk bahawa nod

70
00:05:00,340 --> 00:05:02,340
sentiasa akan menunjukkan kepada NULL.

71
00:05:02,340 --> 00:05:08,230
Apabila titik nod batal, maka anda tahu bahawa anda telah sampai ke penghujung senarai,

72
00:05:08,230 --> 00:05:12,320
bahawa nod tersebut adalah yang terakhir, bahawa tiada apa-apa selepas itu.

73
00:05:12,320 --> 00:05:16,970
Sini dalam skema ini, anda melihat bahawa anak panah adalah petunjuk,

74
00:05:16,970 --> 00:05:20,290
dan seksyen biru di mana nilai disimpan,

75
00:05:20,290 --> 00:05:24,420
dan kemudian kotak merah dengan penunjuk ia adalah penunjuk nod

76
00:05:24,420 --> 00:05:27,050
menunjuk kepada nod berikutnya selepas ia.

77
00:05:27,050 --> 00:05:33,730
Dan sebagainya yang anda lihat di sini, nod D akan menunjukkan NULL kerana ia adalah elemen terakhir dalam senarai.

78
00:05:33,730 --> 00:05:38,240
>> Mari kita melihat bagaimana kita boleh menentukan struct nod.

79
00:05:38,240 --> 00:05:40,130
Dan kerana kita mahu mempunyai pelbagai nod,

80
00:05:40,130 --> 00:05:43,180
ini akan menjadi struct typedef

81
00:05:43,180 --> 00:05:46,870
di mana kita akan mempunyai keadaan yang berbeza beberapa nod.

82
00:05:46,870 --> 00:05:50,850
Dan supaya kita menentukan ia sebagai jenis data baru.

83
00:05:50,850 --> 00:05:53,630
Di sini, kita mempunyai nod struct typedef.

84
00:05:53,630 --> 00:05:56,160
Dalam contoh ini, kita sedang berurusan dengan nod integer,

85
00:05:56,160 --> 00:06:00,490
jadi kita mempunyai nilai integer yang dinamakan dan kemudian kita mempunyai penunjuk lain,

86
00:06:00,490 --> 00:06:07,390
dan dalam kes ini, ia adalah penunjuk kepada nod, jadi kita mempunyai nod struct * dipanggil seterusnya.

87
00:06:07,390 --> 00:06:09,520
Dan kemudian kita memanggil ini nod segala-galanya.

88
00:06:09,520 --> 00:06:11,110
Pastikan bahawa anda mengikuti sintaks ini.

89
00:06:11,110 --> 00:06:17,940
Perhatikan bahawa nod sebenarnya dirujuk atas serta bawah pendakap kerinting.

90
00:06:17,940 --> 00:06:23,400
Kemudian untuk menjejaki di mana nod pertama saya adalah dalam senarai ini dipautkan,

91
00:06:23,400 --> 00:06:29,390
maka saya mempunyai penunjuk nod dipanggil kepala, dan saya malloc ruang cukup untuk saiz nod.

92
00:06:29,390 --> 00:06:36,240
Notis, bagaimanapun, ketua yang sebenarnya adalah penunjuk nod berbanding kepada nod sebenar itu sendiri.

93
00:06:36,240 --> 00:06:40,130
Jadi kepala sebenarnya tidak mengandungi sebarang nilai,

94
00:06:40,130 --> 00:06:45,590
ia hanya mata kepada mana-mana nod pertama dalam senarai saya dikaitkan.

95
00:06:55,080 --> 00:06:58,340
>> Untuk mendapatkan rasa yang lebih baik senarai yang dipautkan, kerana ia amat penting

96
00:06:58,340 --> 00:07:02,220
untuk menjejaki memastikan bahawa anda mengekalkan rantaian,

97
00:07:02,220 --> 00:07:09,990
Saya suka untuk memikirkan ia sebagai rakyat dalam satu barisan berpegangan tangan,

98
00:07:09,990 --> 00:07:14,330
di mana setiap orang berpegangan tangan dengan satu depan.

99
00:07:14,330 --> 00:07:18,350
Anda tidak boleh melihat dalam lukisan ini, tetapi pada dasarnya mereka menunjuk kepada orang yang seterusnya

100
00:07:18,350 --> 00:07:23,760
yang dalam rantaian mereka.

101
00:07:23,760 --> 00:07:29,270
Dan jadi jika anda mahu merentasi senarai berpaut di mana orang-orang ini -

102
00:07:29,270 --> 00:07:32,830
bayangkan semua orang mempunyai nilai-nilai yang dikaitkan dengan mereka

103
00:07:32,830 --> 00:07:36,590
dan juga menunjukkan kepada orang yang seterusnya dalam baris -

104
00:07:36,590 --> 00:07:40,810
jika anda mahu melintasi senarai berkaitan, misalnya, sama ada untuk mengedit nilai

105
00:07:40,810 --> 00:07:42,830
atau mencari nilai atau sesuatu seperti itu,

106
00:07:42,830 --> 00:07:48,270
maka anda akan mahu mempunyai penunjuk kepada orang yang tertentu.

107
00:07:48,270 --> 00:07:52,670
Jadi, kita akan mempunyai jenis data penunjuk nod.

108
00:07:52,670 --> 00:07:55,580
Sebagai contoh ini, mari kita memanggilnya kursor.

109
00:07:55,580 --> 00:07:59,630
Satu lagi cara yang biasa untuk menamakan ini akan iterator atau sesuatu seperti itu

110
00:07:59,630 --> 00:08:05,130
kerana ia iterating alih dan sebenarnya bergerak nod yang ia menunjuk ke.

111
00:08:05,130 --> 00:08:14,410
Ini di sini akan kursor kami.

112
00:08:14,410 --> 00:08:20,180
Kursor pertama kami akan menunjukkan kepada elemen pertama dalam senarai kami.

113
00:08:20,180 --> 00:08:26,910
Dan jadi apa yang kita mahu lakukan ialah kita pada dasarnya akan meneruskan kursor,

114
00:08:26,910 --> 00:08:29,130
bergerak dari sisi ke sisi.

115
00:08:29,130 --> 00:08:33,409
Dalam kes ini, kita mahu memindahkannya ke elemen seterusnya dalam senarai.

116
00:08:33,409 --> 00:08:38,480
Dengan tatasusunan, apa yang kita akan lakukan ialah kita hanya akan mengatakan bahawa kita meningkatkan indeks oleh 1.

117
00:08:38,480 --> 00:08:46,020
Dalam kes ini, apa yang perlu kita lakukan adalah sebenarnya mencari yang orang orang ini semasa menunjuk ke,

118
00:08:46,020 --> 00:08:48,930
dan yang akan menjadi nilai seterusnya.

119
00:08:48,930 --> 00:08:53,230
Jadi jika kursor hanya penunjuk nod, maka apa yang kita mahu lakukan

120
00:08:53,230 --> 00:08:56,320
ialah kita mahu mendapatkan nilai yang kursor menunjuk ke.

121
00:08:56,320 --> 00:09:01,350
Kita mahu mendapatkan nod tersebut dan kemudian, apabila kita berada di nod tersebut, mencari di mana ia menunjuk ke.

122
00:09:01,350 --> 00:09:05,820
Untuk mendapatkan ke nod sebenar bahawa kursor menunjuk ke,

123
00:09:05,820 --> 00:09:13,160
biasanya kita menunjukkan bahawa ia oleh (* kursor).

124
00:09:13,160 --> 00:09:19,160
Yang akan memberi anda nod sebenar bahawa kursor menunjuk ke.

125
00:09:19,160 --> 00:09:21,730
Dan kemudian selepas itu, apa yang kita mahu lakukan ialah kita mahu untuk mengakses

126
00:09:21,730 --> 00:09:25,680
apa yang nilai nod seterusnya.

127
00:09:25,680 --> 00:09:32,820
Untuk berbuat demikian, untuk mengakses nilai dalam struct itu, kita mempunyai pengendali dot.

128
00:09:32,820 --> 00:09:39,530
Jadi maka ia akan menjadi (* kursor). Seterusnya.

129
00:09:39,530 --> 00:09:44,840
Tetapi ini adalah sedikit kotor dari segi mempunyai kurungan sekitar kursor *,

130
00:09:44,840 --> 00:09:56,800
dan sebagainya kita menggantikan keseluruhan kenyataan ini dengan kursor->.

131
00:09:56,800 --> 00:10:02,700
Ini adalah melontarkan dan kemudian satu tanda yang lebih besar daripada, jadi membuat anak panah.

132
00:10:02,700 --> 00:10:05,840
kursor-> seterusnya.

133
00:10:05,840 --> 00:10:12,390
Yang sebenarnya akan mendapatkan anda nod bahawa mata kursor untuk. Bahawa nilai seterusnya.

134
00:10:12,390 --> 00:10:16,790
Jadi bukannya mempunyai bintang dan titik, anda menggantikan bahawa dengan anak panah.

135
00:10:16,790 --> 00:10:24,820
Berhati-hati untuk memastikan bahawa anda cuba untuk menggunakan sintaks ini.

136
00:10:33,550 --> 00:10:37,620
>> Sekarang kita mempunyai kursor kita, jika kita mahu untuk mengakses nilai,

137
00:10:37,620 --> 00:10:40,450
sebelum ini, kita terpaksa kursor-> seterusnya,

138
00:10:40,450 --> 00:10:46,260
tetapi untuk mengakses nilai pada nod bahawa kursor menunjuk ke, kita hanya sekadar mengatakan

139
00:10:46,260 --> 00:10:48,070
nod-> nilai.

140
00:10:48,070 --> 00:10:53,600
Dari situ, ia adalah jenis data apa yang kita telah ditakrifkan nilai-nilai dan nodus menjadi.

141
00:10:53,600 --> 00:10:59,620
Jika ia nod int, maka kursor-> nilai hanya akan menjadi integer.

142
00:10:59,620 --> 00:11:04,870
Jadi, kita boleh melakukan operasi pada itu, periksa equalities, menyerahhakkan nilai-nilai yang berbeza, dan lain-lain

143
00:11:04,870 --> 00:11:11,090
Jadi maka apa yang anda mahu lakukan jika anda mahu menggerakkan kursor anda kepada orang yang seterusnya,

144
00:11:11,090 --> 00:11:15,270
anda sebenarnya menukar nilai kursor.

145
00:11:15,270 --> 00:11:19,340
Sejak kursor penunjuk nod, anda menukar alamat penunjuk sebenar

146
00:11:19,340 --> 00:11:23,890
alamat nod seterusnya dalam senarai anda.

147
00:11:23,890 --> 00:11:28,930
Ini adalah hanya beberapa kod di mana anda boleh melelar.

148
00:11:28,930 --> 00:11:31,230
Di mana saya mempunyai komen melakukan sesuatu,

149
00:11:31,230 --> 00:11:33,850
itulah di mana anda mungkin akan mengakses nilai

150
00:11:33,850 --> 00:11:37,850
atau melakukan sesuatu untuk dilakukan dengan nod yang tertentu.

151
00:11:37,850 --> 00:11:43,050
Untuk memulakan ia dimatikan, saya mengatakan bahawa kursor saya pada mulanya

152
00:11:43,050 --> 00:11:48,430
akan untuk menunjukkan elemen yang pertama dalam senarai berkaitan.

153
00:11:48,430 --> 00:11:52,910
Dan sebagainya sehingga ke hadapan, saya ditakrifkan sebagai ketua nod.

154
00:11:52,910 --> 00:11:57,610
>> Seperti yang saya nyatakan sebelum ini, membebaskan adalah benar-benar penting.

155
00:11:57,610 --> 00:12:02,440
Anda ingin memastikan bahawa anda membebaskan setiap elemen dalam senarai sebaik sahaja anda selesai dengan ia.

156
00:12:02,440 --> 00:12:04,940
Apabila anda tidak perlu untuk rujukan mana-mana mereka petunjuk lagi,

157
00:12:04,940 --> 00:12:10,620
anda ingin memastikan bahawa anda membebaskan semua mereka petunjuk.

158
00:12:10,620 --> 00:12:14,460
Tetapi anda ingin menjadi sangat berhati-hati di sini kerana anda mahu mengelakkan sebarang kebocoran memori.

159
00:12:14,460 --> 00:12:25,080
Jika anda bebas seseorang pramatang, maka semua petunjuk bahawa titik nod

160
00:12:25,080 --> 00:12:26,900
akan hilang.

161
00:12:26,900 --> 00:12:32,070
Melangkah kembali ke contoh orang yang membuat ia sedikit kepentingan lebih tinggi,

162
00:12:32,070 --> 00:12:49,600
mari kita mempunyai orang-orang ini, kecuali dalam kes ini mereka berlegar di atas tasik dengan raksasa.

163
00:12:49,600 --> 00:12:53,200
Kami mahu memastikan bahawa apabila kita bebas, kita tidak kehilangan

164
00:12:53,200 --> 00:12:58,920
dan membiarkan pergi mana-mana nod sebelum kita telah benar-benar dibebaskan mereka.

165
00:12:58,920 --> 00:13:05,730
Sebagai contoh, jika anda adalah untuk hanya memanggil percuma pada lelaki ini di sini,

166
00:13:05,730 --> 00:13:15,350
maka dia akan dibebaskan, tetapi kemudian semua ini lelaki maka akan hilang

167
00:13:15,350 --> 00:13:18,450
dan mereka akan hanyut dan jatuh.

168
00:13:18,450 --> 00:13:24,900
Jadi, kita mahu pastikan bahawa sebaliknya, kita mahu mengekalkan pautan ke seluruh.

169
00:13:37,630 --> 00:13:42,480
Penunjuk kepala kita, yang mata kepada unsur yang pertama dalam senarai.

170
00:13:42,480 --> 00:13:49,990
Ia adalah jenis seperti tali sauh orang pertama.

171
00:13:52,870 --> 00:13:57,470
Apa yang anda mungkin mahu lakukan apabila anda membebaskan senarai -

172
00:13:57,470 --> 00:14:04,520
Jika anda ingin membebaskan elemen pertama yang pertama, maka anda boleh mempunyai penunjuk sementara

173
00:14:04,520 --> 00:14:07,370
bahawa mata kepada apa jua elemen pertama.

174
00:14:07,370 --> 00:14:11,420
Jadi anda mempunyai penunjuk sementara anda menunjuk sini.

175
00:14:11,420 --> 00:14:15,840
Dengan cara itu, kita perlu memegang nod pertama.

176
00:14:15,840 --> 00:14:18,930
Dan kemudian, kerana kita tahu bahawa nod pertama akan dibebaskan,

177
00:14:18,930 --> 00:14:24,890
maka kita boleh bergerak ini tali, sauh ini, kepala kita,

178
00:14:24,890 --> 00:14:31,930
untuk benar-benar menunjukkan apa yang pertama menunjuk ke.

179
00:14:31,930 --> 00:14:38,760
Jadi kepala ini sebenarnya menunjukkan kepada elemen kedua sekarang.

180
00:14:38,760 --> 00:14:43,980
Sekarang kita dibenarkan untuk membebaskan apa yang disimpan dalam menggoda,

181
00:14:43,980 --> 00:14:53,360
dan sebagainya kita boleh memadam bahawa tanpa ia membahayakan semua nod lain dalam senarai kami.

182
00:14:54,140 --> 00:15:05,020
Satu lagi cara yang anda boleh lakukan ini boleh menjadi

183
00:15:05,020 --> 00:15:08,650
setiap kali anda hanya membebaskan elemen terakhir dalam senarai

184
00:15:08,650 --> 00:15:11,010
kerana mereka dijamin tidak akan menunjukkan apa-apa.

185
00:15:11,010 --> 00:15:15,570
Jadi, anda hanya boleh membebaskan satu ini, maka yang satu ini, maka percuma satu ini.

186
00:15:15,570 --> 00:15:21,900
Yang pasti kerja-kerja tetapi adalah agak perlahan kerana oleh sifat senarai yang dikaitkan,

187
00:15:21,900 --> 00:15:24,670
kita tidak boleh hanya segera melompat kepada yang terakhir.

188
00:15:24,670 --> 00:15:28,030
Kita perlu merentasi setiap elemen dalam senarai berkaitan

189
00:15:28,030 --> 00:15:31,020
dan memeriksa sama ada salah satu yang menunjuk ke NULL, memeriksa setiap masa,

190
00:15:31,020 --> 00:15:33,780
dan kemudian apabila kita sampai akhir, maka percuma yang.

191
00:15:33,780 --> 00:15:40,270
Jika anda untuk melakukan proses ini, anda sebenarnya akan memeriksa di sini,

192
00:15:40,270 --> 00:15:44,190
memeriksa di sini, kemudian memeriksa di sini, membebaskan,

193
00:15:44,190 --> 00:15:47,470
kemudian akan kembali, memeriksa sini, memeriksa sini, membebaskan,

194
00:15:47,470 --> 00:15:49,660
memeriksa di sini, dan kemudian membebaskan ia.

195
00:15:49,660 --> 00:15:52,880
Yang mengambil masa sedikit lebih. Yeah.

196
00:15:52,880 --> 00:15:59,060
>> [Pelajar] Adakah ia mungkin untuk membuat senarai yang dikaitkan yang menyimpan penunjuk keluar ke akhir?

197
00:15:59,060 --> 00:16:01,320
Yang pasti akan berlaku.

198
00:16:01,320 --> 00:16:08,340
Untuk mengulangi soalan, ia mungkin untuk mempunyai senarai struktur yang dikaitkan

199
00:16:08,340 --> 00:16:12,490
seperti yang anda mempunyai penunjuk yang menunjuk ke akhir senarai dikaitkan?

200
00:16:12,490 --> 00:16:18,090
Saya mengatakan bahawa mungkin, dan setiap kali anda memasukkan sesuatu ke dalam senarai dikaitkan anda

201
00:16:18,090 --> 00:16:21,470
anda akan mempunyai untuk mengemaskinikan bahawa penunjuk dan perkara-perkara seperti itu.

202
00:16:21,470 --> 00:16:26,640
Anda akan mempunyai ekor * nod, misalnya.

203
00:16:26,640 --> 00:16:29,840
Tetapi apabila anda melaksanakan ciri ini, anda perlu berfikir off perdagangan,

204
00:16:29,840 --> 00:16:32,700
suka berapa kali saya akan iterating lebih ini,

205
00:16:32,700 --> 00:16:36,100
bagaimana sukar ia akan menjadi menjejaki ekor serta kepala

206
00:16:36,100 --> 00:16:38,400
serta iterator saya, dan hal-hal seperti itu.

207
00:16:40,730 --> 00:16:42,480
Adakah itu? >> [Pelajar] Yeah.

208
00:16:42,480 --> 00:16:48,270
Ia mungkin, tetapi dari segi keputusan reka bentuk, anda perlu menimbang pilihan.

209
00:16:53,850 --> 00:17:01,090
>> Berikut adalah rangka kod yang akan membolehkan anda untuk membebaskan setiap elemen dalam senarai berkaitan.

210
00:17:01,090 --> 00:17:05,460
Sekali lagi, kerana saya iterating atas senarai berkaitan, saya akan mahu mempunyai beberapa jenis kursor

211
00:17:05,460 --> 00:17:08,670
atau iterator.

212
00:17:08,670 --> 00:17:14,640
Kami iterating sehingga kursor NULL.

213
00:17:14,640 --> 00:17:17,640
Anda tidak mahu untuk melelar apabila kursor anda adalah NULL

214
00:17:17,640 --> 00:17:20,579
kerana itu bermakna bahawa tidak ada apa-apa dalam senarai.

215
00:17:20,579 --> 00:17:25,069
Jadi maka di sini saya membuat * nod sementara

216
00:17:25,069 --> 00:17:29,610
menunjuk kepada apa yang saya mempertimbangkan pertama senarai saya,

217
00:17:29,610 --> 00:17:35,340
dan kemudian saya menggerakkan kursor saya menjelang 1 dan kemudiannya bebas apa yang saya ada dalam simpanan sementara.

218
00:17:38,460 --> 00:17:43,650
>> Sekarang kita datang untuk memasukkan ke dalam senarai berkaitan.

219
00:18:00,200 --> 00:18:09,660
Saya mempunyai tiga nod dalam senarai berpaut saya, dan mari kita pergi dengan kes mudah

220
00:18:09,660 --> 00:18:18,970
di mana kita mahu memasukkan nod yang lain pada akhir senarai dikaitkan kami.

221
00:18:18,970 --> 00:18:25,980
Untuk berbuat demikian, kita akan lakukan ialah kita akan merentasi

222
00:18:25,980 --> 00:18:32,100
untuk mencari di mana akhir semasa senarai berkaitan, jadi mana-mana nod menunjuk ke Nol -

223
00:18:32,100 --> 00:18:33,850
yang satu ini -

224
00:18:33,850 --> 00:18:37,260
dan kemudian berkata, sebenarnya, yang satu ini tidak akan menjadi nod terakhir;

225
00:18:37,260 --> 00:18:39,830
kita sebenarnya akan mempunyai satu sama lain.

226
00:18:39,830 --> 00:18:46,260
Jadi, kita akan mempunyai ini semasa satu titik untuk apa sahaja yang kita memasukkan.

227
00:18:46,260 --> 00:18:50,080
Jadi sekarang ini orang merah di sini menjadi nod terakhir dalam senarai berkaitan.

228
00:18:50,080 --> 00:18:56,080
Dan sebagainya ciri nod terakhir dalam senarai berkaitan adalah bahawa ia menjurus kepada NULL.

229
00:18:56,080 --> 00:19:09,380
Demikian maka apa yang kita perlu lakukan ialah menetapkan penunjuk lelaki ini merah untuk null. Di sana.

230
00:19:09,380 --> 00:19:25,370
>> Tetapi bagaimana jika kita mahu memasukkan nod di antara satu kedua dan ketiga?

231
00:19:25,370 --> 00:19:28,960
Bahawa seseorang itu tidak cukup sebagai mudah kerana kita mahu memastikan

232
00:19:28,960 --> 00:19:34,290
bahawa kita tidak melepaskan mana-mana nod dalam senarai dikaitkan kami.

233
00:19:34,290 --> 00:19:43,450
Apa yang kita perlu lakukan adalah pastikan bahawa kita menambat diri kita untuk setiap satu.

234
00:19:43,450 --> 00:19:49,900
Sebagai contoh, mari kita memanggil ini yang kedua.

235
00:19:49,900 --> 00:19:54,390
Jika anda berkata yang kedua sekarang menunjukkan kepada yang satu ini baru

236
00:19:54,390 --> 00:20:02,520
dan anda hanya dibuat penunjuk sana, kemudian yang akan mengakibatkan lelaki ini hilang

237
00:20:02,520 --> 00:20:07,830
kerana tidak ada mana-mana pautan kepadanya.

238
00:20:07,830 --> 00:20:18,970
Sebaliknya - Saya akan menarik ini lagi. Maafkan kebolehan artistik saya.

239
00:20:18,970 --> 00:20:26,570
Kita tahu bahawa kita tidak boleh hanya terus menghubungkan 2 yang baru.

240
00:20:26,570 --> 00:20:30,480
Kita perlu pastikan bahawa kita berpegang kepada yang terakhir.

241
00:20:30,480 --> 00:20:39,200
Apa yang kita mungkin mahu lakukan adalah mempunyai penunjuk sementara

242
00:20:39,200 --> 00:20:42,650
kepada elemen yang akan dilampirkan.

243
00:20:42,650 --> 00:20:45,140
Jadi maka kita mempunyai penunjuk sementara di sana.

244
00:20:45,140 --> 00:20:50,780
Sejak kita tahu bahawa ini satu ketiga sedang disimpan mengesan,

245
00:20:50,780 --> 00:20:53,680
2 kini boleh menghubungkan kepada satu baru kami.

246
00:20:53,680 --> 00:20:57,490
Dan jika ini lelaki merah baru akan menjadi di antara 2 dan 3,

247
00:20:57,490 --> 00:21:05,550
maka apa yang penunjuk bahawa lelaki akan untuk menunjukkan? >> [Pelajar] Temp.

248
00:21:05,550 --> 00:21:07,490
Suhu. Yeah.

249
00:21:07,490 --> 00:21:15,430
Jadi maka nilai seterusnya ini lelaki merah akan menjadi temp.

250
00:21:26,090 --> 00:21:33,010
Apabila anda memasukkan ke dalam senarai yang berkaitan, kita melihat bahawa kita boleh

251
00:21:33,010 --> 00:21:38,260
mudah menambah sesuatu ke akhir dengan mewujudkan pelbagai sementara,

252
00:21:38,260 --> 00:21:42,850
atau jika kita mahu menambah sesuatu ke tengah-tengah pelbagai kami,

253
00:21:42,850 --> 00:21:46,810
maka ia akan mengambil sedikit lebih shuffling sekitar.

254
00:21:46,810 --> 00:21:50,240
Jika anda mahu, misalnya, mempunyai senarai berpaut disusun,

255
00:21:50,240 --> 00:21:54,880
maka anda perlu jenis berat kos dan faedah itu

256
00:21:54,880 --> 00:21:59,720
kerana jika anda mahu mempunyai pelbagai disusun, ini bermakna bahawa setiap kali yang anda masukkan ke dalam,

257
00:21:59,720 --> 00:22:01,630
ia akan mengambil masa sedikit lebih.

258
00:22:01,630 --> 00:22:05,500
Walau bagaimanapun, jika anda mahu kemudian, seperti yang kita akan dapati kita akan mahu,

259
00:22:05,500 --> 00:22:10,280
carian melalui senarai berkaitan, maka ia mungkin lebih mudah jika anda tahu bahawa segala-galanya teratur.

260
00:22:10,280 --> 00:22:15,340
Jadi anda mungkin mahu untuk menimbang kos dan faedah itu.

261
00:22:20,150 --> 00:22:27,740
>> Satu lagi cara untuk memasukkan ke dalam senarai berkaitan adalah untuk memasukkan ke awal sangat senarai.

262
00:22:27,740 --> 00:22:34,700
Jika kita menarik sauh kami di sini - ini adalah kepala kita -

263
00:22:34,700 --> 00:22:40,960
dan kemudian telah orang-orang ini dikaitkan dengan,

264
00:22:40,960 --> 00:22:48,460
dan kemudian kita mempunyai nod baru akan dimasukkan ke dalam permulaan,

265
00:22:48,460 --> 00:22:52,590
maka apa yang kita mungkin mahu lakukan?

266
00:22:55,220 --> 00:23:03,580
Apa yang akan menjadi salah dengan hanya mengatakan saya mahu untuk menghubungkan merah kepada biru,

267
00:23:03,580 --> 00:23:05,790
kerana itulah yang pertama?

268
00:23:05,790 --> 00:23:08,570
Apa yang akan berlaku di sini?

269
00:23:08,570 --> 00:23:12,130
Semua ketiga-tiga akan tersesat.

270
00:23:12,130 --> 00:23:14,140
Jadi kita tidak mahu berbuat demikian.

271
00:23:14,140 --> 00:23:21,430
Sekali lagi, kita telah belajar bahawa kita perlu mempunyai beberapa jenis penunjuk sementara.

272
00:23:21,430 --> 00:23:34,470
Mari kita memilih untuk mempunyai satu titik sementara kepada lelaki ini.

273
00:23:34,470 --> 00:23:39,640
Kemudian kita boleh mempunyai satu titik biru untuk sementara

274
00:23:39,640 --> 00:23:43,240
dan kemudian titik merah kepada biru.

275
00:23:43,240 --> 00:23:47,830
Sebab mengapa saya menggunakan orang di sini adalah kerana kita benar-benar mahu untuk menggambarkan

276
00:23:47,830 --> 00:23:53,180
berpegang kepada rakyat dan memastikan bahawa kita mempunyai pautan kepada mereka

277
00:23:53,180 --> 00:23:57,590
sebelum kita melepaskan tangan lain atau sesuatu seperti itu.

278
00:24:05,630 --> 00:24:10,650
>> Sekarang kita mempunyai rasa senarai yang dipautkan - bagaimana kita boleh mewujudkan senarai berpaut

279
00:24:10,650 --> 00:24:15,090
dan mewujudkan struktur bagi yang terdiri daripada definisi jenis untuk nod

280
00:24:15,090 --> 00:24:19,060
dan kemudian memastikan bahawa kita mempunyai penunjuk kepada kepala senarai yang dikaitkan -

281
00:24:19,060 --> 00:24:23,210
sekali kita perlu dan kita tahu bagaimana untuk merentasi melalui array,

282
00:24:23,210 --> 00:24:28,200
mengakses pelbagai elemen, kita tahu bagaimana untuk memasukkan dan kita tahu bagaimana untuk membebaskan mereka,

283
00:24:28,200 --> 00:24:30,260
maka kita boleh masuk ke dalam ejaan.

284
00:24:30,260 --> 00:24:38,150
Seperti biasa, kita mempunyai seksyen soalan-soalan yang akan mendapatkan anda digunakan untuk operasi dengan senarai berkaitan

285
00:24:38,150 --> 00:24:41,750
dan struktur yang berbeza seperti barisan dan susunan.

286
00:24:41,750 --> 00:24:46,000
Kemudian kita boleh bergerak ke dalam ejaan.

287
00:24:46,000 --> 00:24:55,170
>> Ejaan mempunyai kod pengagihan beberapa fail penting.

288
00:24:55,170 --> 00:24:58,850
Mula-mula kita dapati bahawa kita mempunyai Makefile ini di sini,

289
00:24:58,850 --> 00:25:03,040
yang kita tidak benar-benar yang dihadapi sebelum ini.

290
00:25:03,040 --> 00:25:10,090
Jika anda melihat di dalam folder pset5, anda akan melihat bahawa anda mempunyai fail h,

291
00:25:10,090 --> 00:25:12,530
maka anda mempunyai dua c fail.

292
00:25:12,530 --> 00:25:18,920
Apa Makefile ini tidak sebelum ini, kita hanya akan menaip membuat dan maka nama program

293
00:25:18,920 --> 00:25:25,550
dan kemudian kita akan melihat semua ini hujah dan bendera lulus ke pengkompil.

294
00:25:25,550 --> 00:25:30,580
Apa Makefile tidak membolehkan kita untuk menyusun beberapa fail sekaligus

295
00:25:30,580 --> 00:25:34,650
dan lulus dalam bendera yang kita mahu.

296
00:25:34,650 --> 00:25:41,300
Di sini kita hanya melihat ada fail pengepala di sini.

297
00:25:41,300 --> 00:25:43,730
Kemudian kita sebenarnya mempunyai dua fail sumber.

298
00:25:43,730 --> 00:25:47,520
Kami mempunyai speller.c dan dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Anda dialu-alukan untuk mengedit Makefile jika anda mahu.

300
00:25:54,560 --> 00:26:03,310
Perhatikan bahawa di sini jika anda menaip bersih, maka apa yang ia adalah sebenarnya membuang apa-apa

301
00:26:03,310 --> 00:26:06,340
yang adalah teras.

302
00:26:06,340 --> 00:26:09,190
Jika anda mendapat suatu kesalahan segmentasi, pada dasarnya anda mendapat tempat pembuangan teras.

303
00:26:09,190 --> 00:26:13,260
Jadi fail ini sedikit hodoh akan muncul dalam direktori yang dipanggil teras anda.

304
00:26:13,260 --> 00:26:16,310
Anda akan mahu untuk menghapuskan bahawa untuk membuat ia bersih.

305
00:26:16,310 --> 00:26:20,940
Ia membuang mana-mana fail exe dan fail o.

306
00:26:27,900 --> 00:26:30,220
>> Mari kita lihat ke dalam dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Ini mengatakan bahawa ia mengisytiharkan fungsi kamus.

308
00:26:34,410 --> 00:26:39,530
Kami mempunyai panjang maksimum bagi mana-mana perkataan di dalam kamus.

309
00:26:39,530 --> 00:26:45,130
Kami mengatakan bahawa ini akan menjadi perkataan yang mungkin terpanjang. Ia adalah sebanyak 45 panjang.

310
00:26:45,130 --> 00:26:48,900
Jadi kita tidak akan mempunyai apa-apa perkataan yang melebihi panjang yang.

311
00:26:48,900 --> 00:26:50,980
Di sini kita hanya mempunyai prototaip fungsi.

312
00:26:50,980 --> 00:26:55,290
Kami tidak mempunyai pelaksanaan sebenar kerana itulah apa yang kita akan lakukan untuk pset ini.

313
00:26:55,290 --> 00:26:59,940
Tetapi apa yang ini tidak adalah kerana kita sedang berurusan dengan fail yang lebih besar di sini

314
00:26:59,940 --> 00:27:06,650
dan fungsi pada skala yang lebih besar, ia berguna untuk mempunyai fail h

315
00:27:06,650 --> 00:27:11,290
supaya orang lain membaca atau menggunakan kod anda boleh memahami apa yang berlaku.

316
00:27:11,290 --> 00:27:17,910
Dan mungkin mereka mahu untuk melaksanakan cuba jika anda lakukan jadual hash atau sebaliknya.

317
00:27:17,910 --> 00:27:21,850
Kemudian mereka akan mengatakan fungsi beban saya,

318
00:27:21,850 --> 00:27:26,950
pelaksanaan sebenar akan berbeza, tetapi prototaip ini tidak akan berubah.

319
00:27:26,950 --> 00:27:33,280
Di sini kita telah memeriksa, yang mengembalikan benar jika perkataan yang diberikan di dalam kamus.

320
00:27:33,280 --> 00:27:39,800
Kemudian kita mempunyai beban, yang pada dasarnya mengambil dalam fail kamus

321
00:27:39,800 --> 00:27:44,360
dan kemudian memuatkan ke dalam beberapa struktur data.

322
00:27:44,360 --> 00:27:47,500
Kami mempunyai saiz, yang, apabila dipanggil, mengembalikan saiz kamus anda,

323
00:27:47,500 --> 00:27:50,310
berapa banyak kata-kata yang disimpan di dalamnya,

324
00:27:50,310 --> 00:27:54,390
dan kemudian memunggah, yang membebaskan memori semua yang anda mungkin telah diambil

325
00:27:54,390 --> 00:27:57,900
semasa membuat kamus anda.

326
00:28:01,070 --> 00:28:03,590
>> Mari kita lihat pada dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Kita lihat bahawa ia kelihatan sangat serupa ke dictionary.h, kecuali kini ia hanya mempunyai semua ini Todos di dalamnya.

328
00:28:10,490 --> 00:28:16,980
Dan supaya kerja anda. Akhirnya, anda akan mengisi speller.c dengan semua kod ini.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, apabila berjalan, tidak benar-benar akan melakukan apa-apa,

330
00:28:21,540 --> 00:28:29,590
jadi kita melihat ke arah speller.c untuk melihat pelaksanaan sebenar pemeriksa ejaan.

331
00:28:29,590 --> 00:28:32,060
Walaupun anda tidak akan menyunting mana-mana kod ini,

332
00:28:32,060 --> 00:28:38,050
ia adalah penting untuk membaca, memahami apabila beban dipanggil, apabila saya memanggil cek,

333
00:28:38,050 --> 00:28:42,350
hanya untuk memahami, memetakan ia keluar, melihat bagaimana fungsi berfungsi.

334
00:28:42,350 --> 00:28:49,860
Kita lihat bahawa ia memeriksa penggunaan yang betul.

335
00:28:49,860 --> 00:28:55,200
Pada asasnya, apabila seseorang berjalan pengeja, ini menunjukkan bahawa ia adalah pilihan

336
00:28:55,200 --> 00:29:00,950
bagi mereka untuk lulus dalam fail kamus kerana ada akan menjadi fail lalai kamus.

337
00:29:00,950 --> 00:29:05,410
Dan kemudian mereka perlu lulus dalam teks untuk menjadi eja.

338
00:29:05,410 --> 00:29:11,410
tawaran rusage dengan masa kerana sebahagian pset ini yang kita akan berurusan dengan kemudian

339
00:29:11,410 --> 00:29:14,790
bukan sahaja mendapat berfungsi ejaan pemeriksa bekerja

340
00:29:14,790 --> 00:29:17,190
tetapi sebenarnya mendapat ia menjadi cepat.

341
00:29:17,190 --> 00:29:22,040
Dan demikian maka yang mana rusage akan datang masuk

342
00:29:22,040 --> 00:29:28,740
Di sini, kita lihat panggilan pertama salah fail dictionary.c kami, yang merupakan beban.

343
00:29:28,740 --> 00:29:34,720
Beban mengembalikan benar atau palsu - benar apabila kejayaan, palsu atas kegagalan.

344
00:29:34,720 --> 00:29:41,400
Jadi jika kamus tidak dimuatkan dengan betul, maka speller.c itu akan kembali 1 dan berhenti.

345
00:29:41,400 --> 00:29:47,920
Tetapi jika ia tidak beban yang betul, maka ia akan terus.

346
00:29:47,920 --> 00:29:50,740
Kami terus, dan kita lihat beberapa fail I / O di sini,

347
00:29:50,740 --> 00:29:56,210
di mana ia akan berurusan dengan membuka fail teks.

348
00:29:56,210 --> 00:30:04,640
Di sini, apa ini tidak adalah ejaan memeriksa setiap perkataan tunggal dalam teks.

349
00:30:04,640 --> 00:30:09,270
Jadi apa speller.c melakukan di sini iterating setiap perkataan dalam fail teks

350
00:30:09,270 --> 00:30:12,790
dan kemudian memeriksa mereka di dalam kamus.

351
00:30:24,680 --> 00:30:32,350
Di sini, kita mempunyai Boolean silap eja yang akan melihat jika cek mengembalikan benar atau tidak.

352
00:30:32,350 --> 00:30:37,110
Jika perkataan itu sebenarnya adalah di dalam kamus, maka cek akan kembali benar.

353
00:30:37,110 --> 00:30:39,760
Ini bermakna bahawa perkataan itu tidak silap eja.

354
00:30:39,760 --> 00:30:45,330
Jadi silap eja akan menjadi palsu, dan itulah sebabnya kami mempunyai letupan di sana, petunjuk.

355
00:30:45,330 --> 00:30:56,320
Kami terus pergi, dan kemudian ia menjejaki berapa banyak kata yang salah Mengeja

356
00:30:56,320 --> 00:30:58,910
terdapat dalam fail.

357
00:30:58,910 --> 00:31:03,870
Ia terus dan menutup fail.

358
00:31:03,870 --> 00:31:09,250
Maka di sini, ia melaporkan berapa banyak kata yang salah Mengeja anda mempunyai.

359
00:31:09,250 --> 00:31:12,680
Ia mengira berapa banyak masa ia mengambil masa untuk memuatkan kamus,

360
00:31:12,680 --> 00:31:15,080
berapa banyak masa ia mengambil masa untuk memeriksa,

361
00:31:15,080 --> 00:31:18,510
berapa banyak masa ia mengambil masa untuk mengira saiz,

362
00:31:18,510 --> 00:31:21,260
yang, seperti yang kita akan pergi, harus sangat kecil,

363
00:31:21,260 --> 00:31:25,390
dan kemudian berapa banyak masa ia mengambil masa untuk memunggah kamus.

364
00:31:25,390 --> 00:31:27,700
Di sini sehingga di atas kita lihat panggilan untuk memunggah di sini.

365
00:31:27,700 --> 00:31:52,690
Jika kita memeriksa saiz di sini,

366
00:31:52,690 --> 00:31:59,050
maka kita melihat bahawa di sini adalah panggilan untuk saiz di mana ia menentukan saiz kamus.

367
00:32:05,730 --> 00:32:07,100
Menggerunkan.

368
00:32:07,100 --> 00:32:10,920
>> Tugas kita untuk pset ini adalah untuk melaksanakan beban, yang akan memuatkan kamus

369
00:32:10,920 --> 00:32:15,480
struktur data - yang mana anda memilih, sama ada jadual hash atau cuba -

370
00:32:15,480 --> 00:32:18,810
dengan perkataan dari fail kamus.

371
00:32:18,810 --> 00:32:25,290
Kemudian anda mempunyai saiz, yang akan mengembalikan bilangan perkataan dalam kamus.

372
00:32:25,290 --> 00:32:29,860
Dan jika anda melaksanakan beban dalam cara yang bijak, maka saiz harus agak mudah.

373
00:32:29,860 --> 00:32:33,860
Maka anda telah mendaftar, yang akan memeriksa jika satu perkataan yang diberikan di dalam kamus.

374
00:32:33,860 --> 00:32:38,690
Jadi speller.c pas dalam rentetan, dan kemudian anda perlu untuk memeriksa sama ada rentetan itu

375
00:32:38,690 --> 00:32:41,610
yang terkandung dalam kamus anda.

376
00:32:41,610 --> 00:32:46,750
Notis bahawa kita umumnya mempunyai kamus standard,

377
00:32:46,750 --> 00:32:53,020
tetapi dalam pset ini, pada dasarnya mana-mana kamus diluluskan di dalam mana-mana bahasa.

378
00:32:53,020 --> 00:32:57,040
Jadi kita tidak boleh hanya menganggap bahawa perkataan THE berada di dalam.

379
00:32:57,040 --> 00:33:03,090
Foobar perkataan boleh ditakrifkan dalam kamus tertentu yang kita lulus.

380
00:33:03,090 --> 00:33:07,920
Dan maka kita telah memunggah, yang membebaskan kamus dari ingatan.

381
00:33:07,920 --> 00:33:11,930
>> Pertama, saya ingin untuk pergi ke atas kaedah jadual hash

382
00:33:11,930 --> 00:33:14,630
tentang bagaimana kita boleh melaksanakan semua daripada mereka empat fungsi,

383
00:33:14,630 --> 00:33:18,650
dan kemudian saya akan pergi lebih cuba kaedah, bagaimana kita melaksanakan mereka empat fungsi,

384
00:33:18,650 --> 00:33:22,720
dan pada akhir bercakap mengenai beberapa tip umum apabila anda membuat pset yang

385
00:33:22,720 --> 00:33:27,870
dan juga bagaimana anda mungkin boleh menggunakan Valgrind untuk memeriksa kebocoran memori.

386
00:33:27,870 --> 00:33:30,550
>> Mari kita masuk ke dalam kaedah jadual hash.

387
00:33:30,550 --> 00:33:35,910
Satu jadual hash terdiri daripada senarai baldi.

388
00:33:35,910 --> 00:33:43,010
Setiap nilai, setiap perkataan, akan pergi ke dalam salah satu daripada baldi ini.

389
00:33:43,010 --> 00:33:53,200
Satu jadual hash ideal sama rata mengedarkan semua nilai-nilai yang anda lulus dalam

390
00:33:53,200 --> 00:33:57,160
dan kemudian populates mereka dalam baldi itu bahawa setiap baldi

391
00:33:57,160 --> 00:34:02,000
mempunyai kira-kira nombor yang sama nilai di dalamnya.

392
00:34:02,000 --> 00:34:09,630
Struktur untuk jadual hash, kita mempunyai pelbagai senarai yang dipautkan.

393
00:34:09,630 --> 00:34:17,900
Apa yang kita lakukan adalah apabila kita lulus dalam nilai, kita memeriksa mana nilai yang perlu dimiliki,

394
00:34:17,900 --> 00:34:23,840
baldi yang ia milik, dan kemudian meletakkannya ke dalam senarai berkaitan dikaitkan dengan baldi itu.

395
00:34:23,840 --> 00:34:28,199
Di sini, apa yang saya ada adalah fungsi hash.

396
00:34:28,199 --> 00:34:31,320
Ia adalah jadual hash int.

397
00:34:31,320 --> 00:34:38,540
Jadi untuk baldi pertama, sebarang integer bawah 10 pergi ke dalam baldi yang pertama.

398
00:34:38,540 --> 00:34:42,190
Mana-mana integer melebihi 10 tetapi di bawah 20 pergi ke kedua,

399
00:34:42,190 --> 00:34:44,179
dan kemudian sebagainya dan sebagainya.

400
00:34:44,179 --> 00:34:52,370
Bagi saya, baldi setiap mewakili nombor-nombor ini.

401
00:34:52,370 --> 00:34:59,850
Walau bagaimanapun, katakan saya adalah untuk lulus dalam 50, misalnya.

402
00:34:59,850 --> 00:35:07,490
Nampaknya seolah-olah tiga pertama mengandungi pelbagai sepuluh nombor.

403
00:35:07,490 --> 00:35:12,570
Tetapi saya mahu membenarkan jadual hash saya untuk mengambil apa-apa jenis integer,

404
00:35:12,570 --> 00:35:19,860
begitu maka saya akan perlu untuk menapis semua nombor di atas 30 ke dalam baldi lalu.

405
00:35:19,860 --> 00:35:26,660
Dan demikian maka yang akan menyebabkan sejenis jadual hash tidak seimbang.

406
00:35:31,330 --> 00:35:35,640
Mengulangi, jadual hash hanya pelbagai baldi

407
00:35:35,640 --> 00:35:38,590
di mana setiap baldi adalah senarai yang berkaitan.

408
00:35:38,590 --> 00:35:43,730
Dan sebagainya untuk menentukan di mana nilai setiap pergi, yang baldi ia masuk ke dalam,

409
00:35:43,730 --> 00:35:46,260
anda akan mahu apa yang dipanggil fungsi hash

410
00:35:46,260 --> 00:35:55,010
yang mengambil nilai dan kemudian mengatakan nilai ini sepadan dengan baldi tertentu.

411
00:35:55,010 --> 00:36:00,970
Jadi sehingga di atas dalam contoh ini, fungsi hash saya mengambil setiap nilai.

412
00:36:00,970 --> 00:36:03,020
Ia diperiksa sama ada ia adalah kurang daripada 10.

413
00:36:03,020 --> 00:36:05,360
Jika ia adalah, ia akan meletakkan ia ke dalam baldi yang pertama.

414
00:36:05,360 --> 00:36:08,910
Ia memeriksa sama ada ia adalah kurang daripada 20, meletakkan ia ke dalam kedua jika benar,

415
00:36:08,910 --> 00:36:12,880
cek jika ia adalah kurang daripada 30, dan kemudian meletakkan ia ke dalam baldi ketiga,

416
00:36:12,880 --> 00:36:16,990
dan kemudian segala-galanya hanya jatuh ke baldi keempat.

417
00:36:16,990 --> 00:36:20,110
Jadi apabila anda mempunyai nilai, fungsi hash anda

418
00:36:20,110 --> 00:36:25,420
akan meletakkan nilai itu ke dalam baldi sesuai.

419
00:36:25,420 --> 00:36:32,430
Fungsi hash pada dasarnya perlu tahu berapa banyak baldi anda mempunyai.

420
00:36:32,430 --> 00:36:37,960
Jadual hash saiz anda, bilangan baldi anda mempunyai,

421
00:36:37,960 --> 00:36:41,190
yang akan menjadi nombor tetap yang terpulang kepada anda, bagi anda untuk membuat keputusan,

422
00:36:41,190 --> 00:36:43,590
tetapi ia akan menjadi nombor tetap.

423
00:36:43,590 --> 00:36:51,840
Jadi fungsi hash anda akan bergantung kepada bahawa untuk menentukan baldi kunci yang masuk ke dalam setiap

424
00:36:51,840 --> 00:36:54,450
itu bahawa ia sama rata.

425
00:36:56,150 --> 00:37:03,820
Serupa dengan pelaksanaan senarai yang dipautkan kami, kini setiap nod dalam jadual hash

426
00:37:03,820 --> 00:37:07,000
sebenarnya akan mempunyai char jenis.

427
00:37:07,000 --> 00:37:14,340
Jadi kita mempunyai pelbagai char dipanggil perkataan dan kemudian satu lagi penunjuk kepada nod seterusnya,

428
00:37:14,340 --> 00:37:19,010
yang masuk akal kerana ia akan menjadi senarai yang dipautkan.

429
00:37:19,010 --> 00:37:24,350
Ingat apabila kita telah dikaitkan senarai, saya membuat kepala * nod yang dipanggil

430
00:37:24,350 --> 00:37:31,060
yang menunjuk kepada nod pertama dalam senarai berkaitan.

431
00:37:31,060 --> 00:37:34,020
Tetapi bagi jadual hash kita, kerana kita mempunyai pelbagai dikaitkan senarai,

432
00:37:34,020 --> 00:37:37,520
apa yang kita mahu ialah kita mahu jadual hash kami untuk menjadi seperti, "Apakah baldi?"

433
00:37:37,520 --> 00:37:43,340
Baldi adalah hanya senarai penunjuk nod,

434
00:37:43,340 --> 00:37:50,620
dan sebagainya setiap unsur dalam baldi sebenarnya menunjuk kepada senarai yang sama berkaitan.

435
00:37:56,180 --> 00:38:01,520
Untuk kembali ke skematik ini, anda akan melihat bahawa baldi sendiri adalah anak panah,

436
00:38:01,520 --> 00:38:06,980
tidak nod sebenar.

437
00:38:11,680 --> 00:38:16,420
Salah satu harta penting fungsi hash adalah bahawa mereka berada berketentuan.

438
00:38:16,420 --> 00:38:19,440
Ini bermakna bahawa apabila anda hash nombor 2,

439
00:38:19,440 --> 00:38:22,270
ia perlu sentiasa kembali baldi yang sama.

440
00:38:22,270 --> 00:38:26,440
Setiap nilai tunggal yang masuk ke dalam fungsi hash, jika berulang,

441
00:38:26,440 --> 00:38:29,690
untuk mendapatkan indeks yang sama.

442
00:38:29,690 --> 00:38:34,210
Jadi fungsi hash anda mengembalikan indeks array

443
00:38:34,210 --> 00:38:38,530
di mana nilai yang dimiliki.

444
00:38:38,530 --> 00:38:41,790
Seperti yang saya nyatakan sebelum ini, bilangan baldi ditetapkan,

445
00:38:41,790 --> 00:38:49,630
dan sebagainya telunjuk anda bahawa anda kembali mempunyai kurang daripada bilangan baldi

446
00:38:49,630 --> 00:38:52,680
tetapi lebih besar daripada 0.

447
00:38:52,680 --> 00:39:00,780
Sebab mengapa kita mempunyai fungsi hash dan bukannya hanya satu senarai tunggal dikaitkan

448
00:39:00,780 --> 00:39:09,290
atau satu array tunggal adalah bahawa kita mahu menjadi dapat untuk melompat ke bahagian tertentu yang paling mudah

449
00:39:09,290 --> 00:39:11,720
jika kita tahu ciri-ciri nilai -

450
00:39:11,720 --> 00:39:14,760
bukannya terpaksa mencari melalui kamus keseluruhan keseluruhan,

451
00:39:14,760 --> 00:39:18,320
dapat untuk melompat ke seksyen tertentu.

452
00:39:19,880 --> 00:39:24,440
Fungsi hash anda harus mengambil kira bahawa ideal,

453
00:39:24,440 --> 00:39:28,980
baldi masing-masing mempunyai kira-kira jumlah yang sama kunci.

454
00:39:28,980 --> 00:39:35,040
Sejak jadual hash adalah satu siri senarai yang dipautkan,

455
00:39:35,040 --> 00:39:38,480
maka senarai yang dikaitkan sendiri akan mempunyai lebih daripada satu nod.

456
00:39:38,480 --> 00:39:43,210
Dalam contoh sebelum ini, dua nombor yang berbeza, walaupun mereka tidak sama,

457
00:39:43,210 --> 00:39:46,950
apabila dicincang, akan mengembalikan indeks yang sama.

458
00:39:46,950 --> 00:39:53,620
Jadi, apabila anda berurusan dengan kata-kata, satu perkataan apabila dicincang

459
00:39:53,620 --> 00:39:57,450
akan menjadi nilai yang sama hash sebagai perkataan lain.

460
00:39:57,450 --> 00:40:04,140
Itulah apa yang kita panggil perlanggaran, apabila kita mempunyai nod bahawa, apabila dicincang,

461
00:40:04,140 --> 00:40:09,610
senarai dikaitkan di baldi yang tidak kosong.

462
00:40:09,610 --> 00:40:14,180
Teknik yang kita panggil di sana adalah linear menyelesaikan sesuatu,

463
00:40:14,180 --> 00:40:22,550
di mana anda pergi ke senarai berkaitan dan kemudian mencari di mana anda mahu untuk memasukkan bahawa nod

464
00:40:22,550 --> 00:40:25,520
kerana anda mempunyai perlanggaran.

465
00:40:25,520 --> 00:40:28,070
Anda boleh lihat bahawa mungkin ada trade-off di sini, betul-betul?

466
00:40:28,070 --> 00:40:33,760
Jika anda mempunyai jadual hash yang sangat kecil, jumlah yang sangat kecil baldi,

467
00:40:33,760 --> 00:40:36,380
maka anda akan mempunyai banyak perlanggaran.

468
00:40:36,380 --> 00:40:40,460
Tetapi kemudian jika anda membuat jadual hash yang sangat besar,

469
00:40:40,460 --> 00:40:44,110
anda mungkin akan mengurangkan perlanggaran,

470
00:40:44,110 --> 00:40:47,170
tetapi ia akan menjadi struktur data yang sangat besar.

471
00:40:47,170 --> 00:40:49,310
Ada akan menjadi keseimbangan dengan itu.

472
00:40:49,310 --> 00:40:51,310
Jadi, apabila anda membuat pset anda, cuba untuk bermain-main

473
00:40:51,310 --> 00:40:54,210
antara mungkin membuat jadual hash yang lebih kecil

474
00:40:54,210 --> 00:41:02,100
tetapi kemudian mengetahui bahawa ia akan mengambil masa yang lama untuk merentasi elemen-elemen yang berbeza

475
00:41:02,100 --> 00:41:04,270
mereka senarai yang dipautkan.

476
00:41:04,270 --> 00:41:09,500
>> Apa beban akan lakukan adalah melelar lebih setiap perkataan dalam kamus.

477
00:41:09,500 --> 00:41:13,180
Ia pas penunjuk kepada fail kamus.

478
00:41:13,180 --> 00:41:18,050
Jadi, anda akan mengambil kesempatan fail I / O fungsi yang anda menguasai dalam pset4

479
00:41:18,050 --> 00:41:23,010
dan melelar lebih setiap perkataan dalam kamus.

480
00:41:23,010 --> 00:41:26,620
Anda mahu setiap perkataan dalam kamus untuk menjadi nod baru,

481
00:41:26,620 --> 00:41:32,730
dan anda akan meletakkan setiap satu daripada nod-nod di dalam struktur data kamus anda.

482
00:41:32,730 --> 00:41:36,560
Apabila anda mendapat satu perkataan baru, anda tahu bahawa ia akan menjadi nod.

483
00:41:36,560 --> 00:41:46,590
Jadi, anda boleh pergi merta dan malloc penunjuk nod bagi setiap perkataan baru yang anda mempunyai.

484
00:41:46,590 --> 00:41:52,610
Di sini saya memanggil penunjuk nod new_node saya dan saya mallocing apa? Saiz nod.

485
00:41:52,610 --> 00:41:59,190
Kemudian membaca rentetan sebenar dari fail, kerana kamus sebenarnya disimpan

486
00:41:59,190 --> 00:42:03,340
oleh perkataan dan kemudian barisan baru, apa yang kita boleh mengambil kesempatan daripada

487
00:42:03,340 --> 00:42:06,520
adalah fscanf fungsi,

488
00:42:06,520 --> 00:42:10,280
mana fail fail kamus bahawa kita lulus,

489
00:42:10,280 --> 00:42:18,900
jadi ia mengimbas fail untuk rentetan dan tempat-tempat yang tali ke dalam hujah terakhir.

490
00:42:18,900 --> 00:42:26,890
Jika anda ingat kembali kepada salah satu kuliah, apabila kita pergi ke

491
00:42:26,890 --> 00:42:29,320
dan jenis dikupas lapisan kembali di perpustakaan CS50,

492
00:42:29,320 --> 00:42:33,430
kita menyaksikan pelaksanaan fscanf sana.

493
00:42:33,430 --> 00:42:37,700
Untuk kembali ke fscanf, kita mempunyai fail yang kita sedang membaca dari,

494
00:42:37,700 --> 00:42:42,570
kita sedang mencari string dalam fail itu, dan kemudian kita meletakkan ia ke dalam

495
00:42:42,570 --> 00:42:48,340
di sini saya mempunyai new_node-> perkataan kerana new_node adalah penunjuk nod,

496
00:42:48,340 --> 00:42:50,380
bukan nod sebenar.

497
00:42:50,380 --> 00:42:57,100
Jadi maka saya cakapkan new_node, saya mahu pergi ke nod yang ia menunjuk ke

498
00:42:57,100 --> 00:43:01,190
dan kemudian memberikan nilai itu kepada perkataan.

499
00:43:01,190 --> 00:43:08,540
Kami mahu kemudian mengambil perkataan itu dan memasukkannya ke dalam jadual hash.

500
00:43:08,540 --> 00:43:13,750
Sedar bahawa kita dibuat new_node penunjuk nod

501
00:43:13,750 --> 00:43:18,230
kerana kita akan mahu tahu apa alamat nod tersebut adalah

502
00:43:18,230 --> 00:43:23,940
apabila kita memasukkan ia masuk kerana struktur nod sendiri, struct itu,

503
00:43:23,940 --> 00:43:26,380
adalah bahawa mereka mempunyai penunjuk kepada nod baru.

504
00:43:26,380 --> 00:43:30,820
Jadi maka apa alamat nod yang pergi untuk menunjukkan?

505
00:43:30,820 --> 00:43:34,550
Alamat akan menjadi new_node.

506
00:43:34,550 --> 00:43:42,140
Adakah yang masuk akal, mengapa kita membuat new_node * nod sebagai bertentangan dengan nod?

507
00:43:43,700 --> 00:43:45,700
Okay.

508
00:43:45,700 --> 00:43:52,840
Kami mempunyai perkataan. Itu nilai new_node-> perkataan.

509
00:43:52,840 --> 00:43:55,970
Yang mengandungi perkataan daripada kamus yang kita mahu untuk input.

510
00:43:55,970 --> 00:44:00,210
Jadi apa yang kita mahu lakukan ialah kita mahu untuk memanggil fungsi hash kami pada tali itu

511
00:44:00,210 --> 00:44:03,780
kerana fungsi hash kita mengambil dalam rentetan dan kemudian kembali kita integer,

512
00:44:03,780 --> 00:44:12,090
mana integer bahawa indeks mana hashtable pada indeks yang mewakili baldi yang.

513
00:44:12,090 --> 00:44:18,260
Kami mahu mengambil indeks itu dan kemudian pergi kepada indeks yang jadual hash

514
00:44:18,260 --> 00:44:26,960
dan kemudian gunakan bahawa senarai yang dipautkan untuk memasukkan nod pada new_node.

515
00:44:26,960 --> 00:44:31,950
Ingatlah bahawa bagaimanapun anda memutuskan untuk memasukkan nod anda,

516
00:44:31,950 --> 00:44:34,370
sama ada ia adalah di tengah-tengah jika anda mahu untuk menyusun

517
00:44:34,370 --> 00:44:39,650
atau pada awal atau di akhir, pastikan bahawa nod terakhir anda sentiasa mata kepada NULL

518
00:44:39,650 --> 00:44:46,730
kerana itulah satu-satunya cara yang kita tahu di mana elemen terakhir senarai dikaitkan kami.

519
00:44:50,790 --> 00:44:59,710
>> Jika saiz adalah integer yang mewakili bilangan perkataan dalam kamus,

520
00:44:59,710 --> 00:45:03,060
maka salah satu cara untuk melakukan ini adalah bahawa apabila saiz dipanggil

521
00:45:03,060 --> 00:45:05,840
kita pergi melalui setiap elemen dalam jadual hash kami

522
00:45:05,840 --> 00:45:09,410
dan kemudian melelar melalui senarai setiap dikaitkan dalam jadual hash

523
00:45:09,410 --> 00:45:13,770
dan kemudian mengira panjang itu, meningkat 1 kaunter kami dengan 1.

524
00:45:13,770 --> 00:45:16,580
Tetapi setiap kali bahawa saiz dipanggil, yang akan mengambil masa yang lama

525
00:45:16,580 --> 00:45:22,120
kerana kita akan menjadi linear menyelesaikan sesuatu setiap senarai tunggal yang berkaitan.

526
00:45:22,120 --> 00:45:30,530
Sebaliknya, ia akan menjadi lebih mudah jika anda menjejaki berapa banyak kata-kata yang diluluskan.

527
00:45:30,530 --> 00:45:36,330
Jadi, maka jika anda termasuk kaunter dalam fungsi beban anda

528
00:45:36,330 --> 00:45:42,430
update seperti yang diperlukan, maka kaunter, jika anda menetapkan pembolehubah global,

529
00:45:42,430 --> 00:45:44,930
akan dapat diakses oleh saiz.

530
00:45:44,930 --> 00:45:51,450
Jadi apa saiz hanya boleh lakukan dalam satu baris, hanya memulangkan nilai kaunter,

531
00:45:51,450 --> 00:45:55,500
saiz kamus yang anda sudah diuruskan dengan beban.

532
00:45:55,500 --> 00:46:05,190
Itulah apa yang saya maksudkan apabila saya berkata jika anda melaksanakan beban dalam cara membantu,

533
00:46:05,190 --> 00:46:08,540
maka saiz akan menjadi agak mudah.

534
00:46:08,540 --> 00:46:11,350
>> Jadi sekarang kita mendapatkan untuk memeriksa.

535
00:46:11,350 --> 00:46:15,960
Sekarang kita sedang berurusan dengan perkataan dari fail input teks,

536
00:46:15,960 --> 00:46:19,910
dan sebagainya kita akan memeriksa sama ada semua kata-kata input

537
00:46:19,910 --> 00:46:22,520
sebenarnya dalam kamus atau tidak.

538
00:46:22,520 --> 00:46:26,520
Similar Kacau, kita mahu untuk membolehkan tidak sensitif huruf.

539
00:46:26,520 --> 00:46:32,110
Anda ingin memastikan bahawa semua perkataan lulus dalam, walaupun mereka berada kes bercampur,

540
00:46:32,110 --> 00:46:37,840
apabila dipanggil dengan Bandingkan tali, adalah bersamaan.

541
00:46:37,840 --> 00:46:42,450
Perkataan dalam fail teks kamus sebenarnya semua huruf kecil.

542
00:46:42,450 --> 00:46:49,280
Satu lagi perkara adalah bahawa anda boleh mengandaikan bahawa setiap perkataan meninggal dalam setiap, tali,

543
00:46:49,280 --> 00:46:53,200
akan sama ada abjad atau mengandungi koma.

544
00:46:53,200 --> 00:46:58,010
Apostrofi akan menjadi perkataan yang sah di dalam kamus kami.

545
00:46:58,010 --> 00:47:06,470
Jadi jika anda mempunyai satu perkataan dengan apostrofi S, itulah perkataan sebenar yang sah dalam kamus anda

546
00:47:06,470 --> 00:47:11,650
yang akan menjadi salah satu daripada nod dalam jadual hash anda.

547
00:47:13,470 --> 00:47:18,350
Semak beroperasi dengan jika perkataan itu wujud, maka ia mendapat menjadi dalam jadual hash kami.

548
00:47:18,350 --> 00:47:22,210
Sekiranya perkataan ada di dalam kamus, maka semua perkataan di dalam kamus dalam jadual hash,

549
00:47:22,210 --> 00:47:26,560
jadi mari kita lihat perkataan ini dalam jadual hash.

550
00:47:26,560 --> 00:47:29,250
Kita tahu bahawa sejak kita melaksanakan fungsi hash kami

551
00:47:29,250 --> 00:47:38,420
seperti bahawa setiap perkataan yang unik sentiasa dicincang kepada nilai yang sama,

552
00:47:38,420 --> 00:47:43,340
maka kita tahu bahawa bukannya mencari melalui jadual hash keseluruhan keseluruhan kami,

553
00:47:43,340 --> 00:47:48,310
kita sebenarnya boleh mencari senarai berpaut bahawa perkataan itu seharusnya tergolong.

554
00:47:48,310 --> 00:47:51,850
Jika ia berada di dalam kamus, maka ia akan menjadi dalam baldi itu.

555
00:47:51,850 --> 00:47:57,140
Apa yang boleh kita lakukan, jika perkataan adalah nama rentetan diluluskan pada kami,

556
00:47:57,140 --> 00:48:01,560
kita hanya boleh hash bahawa perkataan dan melihat senarai berkaitan

557
00:48:01,560 --> 00:48:06,410
pada nilai hashtable [hash (perkataan)].

558
00:48:06,410 --> 00:48:12,410
Dari situ, apa yang boleh kita lakukan ialah kita mempunyai subset yang lebih kecil nod untuk mencari perkataan ini,

559
00:48:12,410 --> 00:48:16,770
dan supaya kita boleh merentasi senarai berpaut, dengan menggunakan contoh dari awal Walkthrough,

560
00:48:16,770 --> 00:48:24,110
dan kemudian memanggil rentetan bandingkan apabila perkataan mana-mana kursor menunjuk ke,

561
00:48:24,110 --> 00:48:28,430
bahawa perkataan, dan lihat sama ada mereka istimewa.

562
00:48:30,280 --> 00:48:35,110
Bergantung kepada cara yang anda mengatur fungsi hash anda,

563
00:48:35,110 --> 00:48:39,260
jika ia disusun, anda mungkin tidak dapat untuk kembali palsu sedikit lebih awal,

564
00:48:39,260 --> 00:48:43,440
tetapi jika ia Unsorted, maka anda mahu terus menyeberangi melalui senarai dikaitkan anda

565
00:48:43,440 --> 00:48:46,480
sehingga anda menjumpai elemen terakhir senarai.

566
00:48:46,480 --> 00:48:53,320
Dan jika anda masih tidak dijumpai perkataan oleh masa yang anda telah sampai ke penghujung senarai berkaitan,

567
00:48:53,320 --> 00:48:56,890
yang bermaksud bahawa perkataan anda tidak wujud di dalam kamus,

568
00:48:56,890 --> 00:48:59,410
dan sebagainya perkataan itu adalah tidak sah,

569
00:48:59,410 --> 00:49:02,730
dan cek perlu kembali palsu.

570
00:49:02,730 --> 00:49:09,530
>> Sekarang kita sampai kepada memunggah, di mana kita mahu untuk membebaskan semua nod yang kita telah malloc'd,

571
00:49:09,530 --> 00:49:14,050
begitu bebas semua nod dalam jadual hash kami.

572
00:49:14,050 --> 00:49:20,270
Kami akan mahu untuk melelar semua senarai dikaitkan dan bebas semua nod dalam itu.

573
00:49:20,270 --> 00:49:29,350
Jika anda melihat ke atas dalam Walkthrough contoh di mana kita membebaskan senarai berpaut,

574
00:49:29,350 --> 00:49:35,140
maka anda akan mahu mengulangi proses itu bagi setiap elemen dalam jadual hash.

575
00:49:35,140 --> 00:49:37,780
Dan saya akan pergi ke ini ke arah akhir Walkthrough,

576
00:49:37,780 --> 00:49:46,600
tetapi Valgrind adalah alat yang mana anda boleh melihat jika anda telah dibebaskan

577
00:49:46,600 --> 00:49:53,600
setiap nod yang anda telah malloc'd atau apa-apa lain yang anda telah malloc'd, apa-apa penunjuk lain.

578
00:49:55,140 --> 00:50:00,530
Jadi itulah jadual hash, di mana kita mempunyai nombor terhingga baldi

579
00:50:00,530 --> 00:50:09,220
dan fungsi hash yang akan mengambil nilai dan kemudian menetapkan nilai yang baldi tertentu.

580
00:50:09,220 --> 00:50:13,340
>> Sekarang kita datang kepada cuba.

581
00:50:13,340 --> 00:50:18,750
Cuba jenis kelihatan seperti ini, dan saya juga akan menarik keluar contoh.

582
00:50:18,750 --> 00:50:25,630
Pada asasnya, anda mempunyai pelbagai keseluruhan surat yang berpotensi,

583
00:50:25,630 --> 00:50:29,210
dan kemudian apabila anda membina perkataan,

584
00:50:29,210 --> 00:50:36,490
surat yang boleh dikaitkan untuk kamus kepada pelbagai kemungkinan.

585
00:50:36,490 --> 00:50:40,840
Sesetengah perkataan bermula dengan C tetapi kemudian terus dengan A,

586
00:50:40,840 --> 00:50:42,960
tetapi yang lain terus dengan O, sebagai contoh.

587
00:50:42,960 --> 00:50:51,090
Indone adalah cara yang menggambarkan semua kemungkinan kombinasi kata-kata.

588
00:50:51,090 --> 00:50:59,070
Indone A akan menjejaki urutan huruf yang terdiri daripada perkataan,

589
00:50:59,070 --> 00:51:08,280
Sisihan apabila perlu, apabila satu huruf boleh diikuti oleh pelbagai surat,

590
00:51:08,280 --> 00:51:16,630
dan pada akhir menunjukkan pada setiap titik sama ada perkataan itu adalah sah atau tidak

591
00:51:16,630 --> 00:51:30,120
kerana jika anda sedang ejaan MAT perkataan, MA Saya tidak fikir adalah perkataan yang sah, tetapi MAT adalah.

592
00:51:30,120 --> 00:51:37,820
Dan supaya di indone anda, ia akan menunjukkan bahawa selepas MAT itulah sebenarnya satu perkataan yang sah.

593
00:51:41,790 --> 00:51:48,590
Setiap nod dalam indone kita sebenarnya akan mengandungi pelbagai petunjuk nod,

594
00:51:48,590 --> 00:51:52,970
dan kita akan mempunyai, khususnya, 27 orang penunjuk nod,

595
00:51:52,970 --> 00:52:00,550
salah bagi setiap huruf dalam abjad serta watak apostrofe.

596
00:52:00,550 --> 00:52:10,450
Setiap elemen dalam array bahawa dirinya akan menuding kepada nod yang lain.

597
00:52:10,450 --> 00:52:14,020
Jadi, jika nod tersebut adalah NULL, jika tiada apa-apa selepas itu,

598
00:52:14,020 --> 00:52:20,550
maka kita tahu bahawa tidak ada surat lagi dalam urutan perkataan itu.

599
00:52:20,550 --> 00:52:26,950
Tetapi jika nod tersebut tidak NULL, ini bermakna bahawa terdapat lebih huruf dalam urutan surat itu.

600
00:52:26,950 --> 00:52:32,160
Dan kemudian tambahan pula, setiap nod menunjukkan sama ada ia adalah aksara terakhir perkataan atau tidak.

601
00:52:38,110 --> 00:52:43,170
>> Mari pergi ke contoh indone satu.

602
00:52:50,500 --> 00:52:58,340
Pertama Saya mempunyai bilik untuk 27 nod dalam pelbagai ini.

603
00:52:58,340 --> 00:53:03,200
Jika saya mempunyai BAR perkataan -

604
00:53:13,310 --> 00:53:15,370
Jika saya mempunyai BAR perkataan dan saya mahu untuk memasukkan bahawa dalam,

605
00:53:15,370 --> 00:53:22,700
huruf pertama ialah B, jadi jika indone saya adalah kosong,

606
00:53:22,700 --> 00:53:29,910
B adalah huruf kedua abjad, jadi saya akan memilih untuk meletakkan ini di sini pada indeks ini.

607
00:53:29,910 --> 00:53:33,450
Saya akan mempunyai B di sini.

608
00:53:33,450 --> 00:53:42,400
B akan menjadi nod yang mata kepada pelbagai lain semua watak-watak yang mungkin

609
00:53:42,400 --> 00:53:45,870
yang boleh mengikuti selepas huruf B.

610
00:53:45,870 --> 00:53:57,610
Dalam kes ini, saya berurusan dengan BAR perkataan, jadi A akan pergi di sini.

611
00:54:02,000 --> 00:54:08,990
Selepas A, saya mempunyai huruf R, maka A mata sekarang gabungan sendiri,

612
00:54:08,990 --> 00:54:15,120
dan kemudian R akan berada di sini.

613
00:54:15,120 --> 00:54:22,470
BAR adalah satu perkataan yang lengkap, demikian maka saya akan mempunyai titik R ke nod yang lain

614
00:54:22,470 --> 00:54:33,990
yang mengatakan bahawa perkataan itu adalah sah.

615
00:54:36,010 --> 00:54:40,970
Nod juga akan mempunyai pelbagai nod,

616
00:54:40,970 --> 00:54:45,260
tetapi mereka mungkin NULL.

617
00:54:45,260 --> 00:54:49,080
Tetapi pada dasarnya, ia boleh terus seperti itu.

618
00:54:49,080 --> 00:54:54,250
Itu akan menjadi sedikit lebih jelas apabila kita pergi ke contoh yang berbeza,

619
00:54:54,250 --> 00:54:56,780
jadi hanya menanggung dengan saya di sana.

620
00:54:56,780 --> 00:55:02,050
Sekarang kita mempunyai BAR di dalam kamus kami.

621
00:55:02,050 --> 00:55:05,980
Sekarang katakan kita mempunyai perkataan Baz.

622
00:55:05,980 --> 00:55:12,630
Kita mulakan dengan B, dan kita sudah mempunyai B sebagai salah satu huruf yang di dalam kamus kami.

623
00:55:12,630 --> 00:55:15,170
Itu diikuti dengan A. Kami mempunyai A sudah.

624
00:55:15,170 --> 00:55:19,250
Tetapi kemudian sebaliknya, kita mempunyai Z berikut.

625
00:55:19,250 --> 00:55:25,490
Jadi maka elemen dalam array kami akan menjadi Z,

626
00:55:25,490 --> 00:55:30,810
dan demikian maka seseorang itu akan ke titik akhir lain sah perkataan.

627
00:55:30,810 --> 00:55:36,930
Jadi kita lihat bahawa apabila kita terus melalui B dan kemudian,

628
00:55:36,930 --> 00:55:43,480
terdapat dua pilihan yang berbeza kini dalam kamus kita untuk perkataan yang bermula dengan B dan A.

629
00:55:49,650 --> 00:55:57,460
Katakanlah kita mahu memasukkan foobar perkataan.

630
00:55:57,460 --> 00:56:05,620
Kemudian kita akan membuat kemasukan di F.

631
00:56:05,620 --> 00:56:11,320
F adalah nod yang mata kepada pelbagai keseluruhan.

632
00:56:11,320 --> 00:56:22,790
Kita akan mendapati O, pergi ke O, O kemudian menghubungkan ke senarai keseluruhan.

633
00:56:22,790 --> 00:56:35,340
Kita akan mempunyai B dan kemudian terus, kita akan mempunyai A dan kemudian R.

634
00:56:35,340 --> 00:56:43,570
Jadi kemudian merentasi foobar semua jalan ke bawah sehingga foobar adalah perkataan yang betul.

635
00:56:43,570 --> 00:56:52,590
Dan sebagainya maka ini akan menjadi satu perkataan yang sah.

636
00:56:52,590 --> 00:57:00,170
Sekarang mengatakan perkataan seterusnya kami dalam kamus adalah sebenarnya perkataan FOO.

637
00:57:00,170 --> 00:57:03,530
Kita akan mengatakan F. Apa berikut F?

638
00:57:03,530 --> 00:57:06,190
Saya sebenarnya sudah mempunyai ruang untuk O, jadi saya akan terus.

639
00:57:06,190 --> 00:57:09,150
Saya tidak perlu untuk membuat satu yang baru. Teruskan.

640
00:57:09,150 --> 00:57:15,500
FOO adalah perkataan yang sah dalam kamus ini, maka saya akan menunjukkan

641
00:57:15,500 --> 00:57:21,660
bahawa adalah sah.

642
00:57:21,660 --> 00:57:28,370
Jika saya berhenti urutan saya di sana, yang akan menjadi betul.

643
00:57:28,370 --> 00:57:33,050
Tetapi jika kita terus turutan kami dari FOO turun kepada B

644
00:57:33,050 --> 00:57:39,750
dan hanya mempunyai FOOB, FOOB tidak adalah perkataan, dan yang tidak dinyatakan sebagai satu yang sah.

645
00:57:47,370 --> 00:57:57,600
Dalam indone, anda telah setiap nod menunjukkan sama ada ia adalah satu perkataan yang sah atau tidak,

646
00:57:57,600 --> 00:58:05,840
dan kemudian setiap nod juga mempunyai pelbagai 27 penunjuk nod

647
00:58:05,840 --> 00:58:09,520
yang kemudian titik ke nodus diri.

648
00:58:09,520 --> 00:58:12,940
>> Berikut adalah cara bagaimana anda mungkin mahu untuk menentukan ini.

649
00:58:12,940 --> 00:58:17,260
Walau bagaimanapun, seperti dalam contoh jadual hash, di mana kita mempunyai kepala * nod

650
00:58:17,260 --> 00:58:21,320
untuk menunjukkan permulaan senarai dihubungkan kami, kami juga akan mahu

651
00:58:21,320 --> 00:58:29,150
beberapa cara mengetahui mana permulaan indone kami adalah.

652
00:58:29,150 --> 00:58:34,110
Beberapa panggilan orang cuba pokok-pokok, dan itulah di mana akar datang dari.

653
00:58:34,110 --> 00:58:36,910
Jadi kita mahu akar pokok kita untuk memastikan bahawa kita tinggal dibumikan

654
00:58:36,910 --> 00:58:39,570
ke mana sahaja indone kami.

655
00:58:42,910 --> 00:58:46,300
Kita sudah jenis pergi

656
00:58:46,300 --> 00:58:50,240
cara anda boleh berfikir tentang memuatkan setiap perkataan dalam kamus.

657
00:58:50,240 --> 00:58:54,540
Pada asasnya, bagi setiap perkataan, anda akan mahu untuk melelar melalui indone anda

658
00:58:54,540 --> 00:58:59,590
dan mengetahui bahawa setiap unsur dalam kanak-kanak - kita dipanggil kanak-kanak dalam kes ini -

659
00:58:59,590 --> 00:59:04,290
sepadan dengan surat yang berbeza, anda akan mahu untuk memeriksa nilai-nilai

660
00:59:04,290 --> 00:59:08,320
pada indeks yang tertentu yang sepadan dengan huruf.

661
00:59:08,320 --> 00:59:11,260
Jadi berfikir sepanjang jalan kembali ke Caesar dan Vigenere,

662
00:59:11,260 --> 00:59:16,070
mengetahui bahawa setiap huruf yang anda boleh jenis peta kembali kepada indeks abjad,

663
00:59:16,070 --> 00:59:20,690
pasti A melalui Z akan menjadi agak mudah untuk memetakan huruf abjad,

664
00:59:20,690 --> 00:59:25,200
tetapi malangnya, koma juga merupakan watak yang diterima dalam perkataan.

665
00:59:25,200 --> 00:59:31,650
Saya tidak pasti apa nilai ASCII,

666
00:59:31,650 --> 00:59:39,250
jadi untuk itu jika anda mahu untuk mencari indeks untuk memutuskan sama ada anda mahu ia menjadi sama ada yang pertama

667
00:59:39,250 --> 00:59:44,550
atau yang terakhir, anda akan perlu membuat cek keras berkod untuk itu

668
00:59:44,550 --> 00:59:48,930
dan kemudian meletakkan bahawa dalam indeks 26, misalnya.

669
00:59:48,930 --> 00:59:55,300
Jadi maka anda memeriksa nilai pada kanak-kanak [i]

670
00:59:55,300 --> 00:59:58,400
mana [i] sepadan dengan apa-apa huruf yang anda berada di.

671
00:59:58,400 --> 01:00:04,110
Jika itulah NULL, yang bermaksud bahawa tidak ada apa-apa surat yang mungkin

672
01:00:04,110 --> 01:00:08,150
berpunca daripada urutan yang sebelumnya, supaya anda akan mahu malloc

673
01:00:08,150 --> 01:00:13,150
dan membuat nod baru dan mempunyai bahawa kanak-kanak [i] titik ke

674
01:00:13,150 --> 01:00:17,890
supaya anda mencipta - apabila kita memasukkan surat ke dalam segi empat tepat -

675
01:00:17,890 --> 01:00:23,680
membuat kanak-kanak bukan NULL dan titik ke nod yang baru.

676
01:00:23,680 --> 01:00:28,340
Tetapi jika yang tidak NULL, seperti dalam contoh kami FOO

677
01:00:28,340 --> 01:00:34,570
apabila kita sudah mempunyai foobar, kita terus,

678
01:00:34,570 --> 01:00:44,010
dan kita tidak pernah membuat nod baru tetapi hanya menetapkan is_word kepada true

679
01:00:44,010 --> 01:00:47,790
pada akhir perkataan itu.

680
01:00:50,060 --> 01:00:55,340
>> Jadi kemudian seperti sebelum ini, kerana di sini anda berurusan dengan setiap huruf pada satu masa,

681
01:00:55,340 --> 01:01:01,470
ia akan menjadi lebih mudah untuk anda untuk saiz, bukannya mempunyai untuk mengira

682
01:01:01,470 --> 01:01:06,910
dan pergi melalui seluruh pokok dan mengira berapa ramai anak-anak saya mempunyai

683
01:01:06,910 --> 01:01:10,850
dan kemudian bercabang, mengingat berapa banyak pada sebelah kiri dan di sebelah kanan

684
01:01:10,850 --> 01:01:12,850
dan perkara-perkara seperti itu, ia akan menjadi lebih mudah untuk anda

685
01:01:12,850 --> 01:01:16,220
jika anda hanya menjejaki berapa banyak kata-kata anda menambah dalam

686
01:01:16,220 --> 01:01:18,080
apabila anda berurusan dengan beban.

687
01:01:18,080 --> 01:01:22,630
Dan demikian maka cara bahawa saiz hanya boleh kembali pembolehubah global saiz.

688
01:01:25,320 --> 01:01:28,530
>> Sekarang kita datang untuk memeriksa.

689
01:01:28,530 --> 01:01:33,920
Piawaian yang sama seperti sebelum ini, di mana kita mahu untuk membolehkan tidak sensitif huruf.

690
01:01:33,920 --> 01:01:40,400
Juga, kita menganggap bahawa rentetan adalah hanya aksara abjad atau koma

691
01:01:40,400 --> 01:01:44,000
kerana kanak-kanak adalah pelbagai sebanyak 27 lama,

692
01:01:44,000 --> 01:01:48,480
jadi semua huruf abjad ditambah apostrofe.

693
01:01:48,480 --> 01:01:53,800
Untuk memeriksa apa yang anda akan mahu lakukan adalah anda akan mahu bermula di akar

694
01:01:53,800 --> 01:01:58,440
kerana akar akan menunjukkan kepada pelbagai yang mengandungi

695
01:01:58,440 --> 01:02:01,630
semua huruf permulaan mungkin perkataan.

696
01:02:01,630 --> 01:02:03,680
Anda akan bermula di sana,

697
01:02:03,680 --> 01:02:11,590
dan kemudian anda pergi untuk memeriksa ini NULL nilai atau tidak,

698
01:02:11,590 --> 01:02:16,490
kerana jika nilai NULL, ini bermakna bahawa kamus tidak mempunyai apa-apa nilai

699
01:02:16,490 --> 01:02:21,480
yang mengandungi surat itu dalam susunan yang tertentu.

700
01:02:21,480 --> 01:02:24,970
Jika ia NULL, maka ini bermakna bahawa perkataan silap eja segera.

701
01:02:24,970 --> 01:02:27,110
Tetapi jika ia tidak NULL, maka anda boleh terus,

702
01:02:27,110 --> 01:02:34,090
mengatakan bahawa surat pertama adalah surat yang mungkin pertama dalam perkataan,

703
01:02:34,090 --> 01:02:40,630
jadi sekarang saya mahu untuk memeriksa jika surat kedua, urutan itu, adalah dalam kamus saya.

704
01:02:40,630 --> 01:02:46,540
Jadi, anda akan pergi kepada indeks kanak-kanak nod pertama

705
01:02:46,540 --> 01:02:50,720
dan memeriksa sama bahawa surat kedua wujud.

706
01:02:50,720 --> 01:02:57,440
Kemudian anda mengulangi proses itu untuk memeriksa sama ada urutan yang sah atau tidak

707
01:02:57,440 --> 01:02:59,060
dalam indone anda.

708
01:02:59,060 --> 01:03:06,430
Apabila kanak-kanak nod di bahawa mata indeks untuk NULL,

709
01:03:06,430 --> 01:03:10,710
anda tahu bahawa rentetan yang tidak wujud,

710
01:03:10,710 --> 01:03:16,230
tetapi kemudian jika anda sampai akhir perkataan yang anda telah dimasukkan,

711
01:03:16,230 --> 01:03:20,070
maka anda mahu untuk memeriksa sekarang bahawa saya telah selesai urutan ini

712
01:03:20,070 --> 01:03:27,610
dan mendapati ia dalam indone saya, adalah bahawa perkataan sah atau tidak?

713
01:03:27,610 --> 01:03:32,480
Dan demikian maka anda mahu untuk memeriksa bahawa, dan itulah apabila jika anda telah mendapati bahawa urutan,

714
01:03:32,480 --> 01:03:35,120
maka anda mahu untuk memeriksa sama ada perkataan itu adalah sah atau tidak

715
01:03:35,120 --> 01:03:40,290
kerana ingat kembali dalam kes sebelumnya yang saya menarik di mana kita terpaksa FOOB,

716
01:03:40,290 --> 01:03:48,410
yang merupakan urutan sah bahawa kita mendapati tetapi tidak adalah perkataan sebenar yang sah itu sendiri.

717
01:03:50,570 --> 01:03:59,000
>> Begitu juga, bagi memunggah di cuba anda mahu untuk memunggah semua nod dalam indone anda.

718
01:03:59,000 --> 01:04:04,790
Maaf. Seperti jadual hash di mana dalam memunggah kita membebaskan semua nod,

719
01:04:04,790 --> 01:04:09,740
cuba kita mahu juga membebaskan semua nod.

720
01:04:09,740 --> 01:04:15,000
Memunggah sebenarnya akan bekerja paling mudah dari bawah ke atas

721
01:04:15,000 --> 01:04:19,290
kerana ini adalah asasnya dikaitkan senarai.

722
01:04:19,290 --> 01:04:22,540
Jadi, kami ingin memastikan bahawa kita memegang kepada semua nilai-nilai

723
01:04:22,540 --> 01:04:25,700
dan bebas kesemua mereka jelas.

724
01:04:25,700 --> 01:04:28,840
Apa yang anda akan mahu lakukan jika anda sedang bekerja dengan indone

725
01:04:28,840 --> 01:04:35,640
adalah untuk pergi ke bawah dan bebas nod terendah mungkin pertama

726
01:04:35,640 --> 01:04:39,190
dan kemudian pergi sehingga kepada semua orang-orang kanak-kanak dan kemudian bebas semua orang,

727
01:04:39,190 --> 01:04:43,050
naik dan kemudian bebas, dan lain-lain

728
01:04:43,050 --> 01:04:48,790
Jenis seperti berurusan dengan lapisan bawah yang pertama indone

729
01:04:48,790 --> 01:04:51,940
dan kemudian naik atas sebaik sahaja anda telah dibebaskan segala-galanya.

730
01:04:51,940 --> 01:04:56,720
Ini adalah satu contoh yang baik di mana fungsi rekursi mungkin datang dalam berguna.

731
01:04:56,720 --> 01:05:03,830
Sebaik sahaja anda telah dibebaskan lapisan bawah indone anda,

732
01:05:03,830 --> 01:05:08,000
maka anda memanggil memunggah di seluruh ia,

733
01:05:08,000 --> 01:05:13,620
memastikan bahawa anda membebaskan setiap mini -

734
01:05:13,620 --> 01:05:16,410
Anda jenis boleh menggambarkan ia sebagai cuba mini.

735
01:05:23,300 --> 01:05:28,990
Jadi anda mempunyai akar anda di sini.

736
01:05:30,840 --> 01:05:35,230
Saya hanya memudahkan ia jadi saya tidak perlu untuk menarik 26 daripada mereka.

737
01:05:37,250 --> 01:05:43,770
Jadi anda mempunyai ini, dan kemudian ini mewakili urutan perkataan

738
01:05:43,770 --> 01:05:54,620
di mana semua ini bulatan kecil adalah surat yang urutan yang sah surat.

739
01:06:03,040 --> 01:06:07,160
Mari kita terus hanya sedikit lebih.

740
01:06:15,110 --> 01:06:25,750
Apa yang anda akan mahu lakukan adalah percuma bawah di sini dan kemudian bebas yang satu ini

741
01:06:25,750 --> 01:06:31,640
dan kemudian percuma satu ini di bawah sebelum anda membebaskan satu atas di sini

742
01:06:31,640 --> 01:06:38,180
kerana jika anda sesuatu yang percuma di peringkat kedua di sini,

743
01:06:38,180 --> 01:06:47,230
maka anda sebenarnya akan kehilangan nilai ini di sini.

744
01:06:47,230 --> 01:06:54,780
Itulah sebabnya ia adalah penting dalam memunggah indone untuk memastikan bahawa anda membebaskan bahagian bawah dahulu.

745
01:06:54,780 --> 01:06:59,480
Apa yang anda mungkin mahu lakukan adalah katakan untuk setiap nod

746
01:06:59,480 --> 01:07:06,430
Saya mahu untuk memunggah semua kanak-kanak.

747
01:07:16,060 --> 01:07:22,140
>> Sekarang kita telah pergi lebih memunggah untuk kaedah jadual hash serta kaedah indone,

748
01:07:22,140 --> 01:07:27,020
kita akan untuk mahu melihat Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind anda berlari dengan arahan berikut.

750
01:07:29,640 --> 01:07:32,700
Anda mempunyai valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Anda sedang memeriksa semua kebocoran apabila anda menjalankan pengeja memandangkan teks ini tertentu

752
01:07:40,960 --> 01:07:46,980
kerana pengeja perlu mengambil fail teks.

753
01:07:46,980 --> 01:07:52,330
Jadi Valgrind akan menjalankan program anda, memberitahu anda berapa banyak bait anda memperuntukkan,

754
01:07:52,330 --> 01:07:57,150
berapa banyak bait anda dibebaskan, dan ia akan memberitahu anda sama ada anda dibebaskan hanya cukup

755
01:07:57,150 --> 01:07:58,930
atau sama ada anda tidak bebas cukup,

756
01:07:58,930 --> 01:08:02,850
atau kadang-kadang anda boleh juga lebih bebas, seperti nod bebas yang sudah dibebaskan

757
01:08:02,850 --> 01:08:05,140
dan sebagainya ia akan kembali anda kesilapan.

758
01:08:05,140 --> 01:08:11,600
Jika anda menggunakan Valgrind, ia akan memberikan anda beberapa mesej

759
01:08:11,600 --> 01:08:15,970
menunjukkan sama ada anda telah dibebaskan sama ada kurang daripada cukup, cukup,

760
01:08:15,970 --> 01:08:19,609
atau lebih daripada masa yang cukup.

761
01:08:24,370 --> 01:08:30,410
>> Satu sebahagian daripada pset ini, ia adalah pilihan untuk mencabar Lembaga Besar.

762
01:08:30,410 --> 01:08:35,790
Tetapi apabila kita sedang berurusan dengan struktur data

763
01:08:35,790 --> 01:08:40,689
ia adalah jenis menyeronokkan untuk melihat bagaimana cepat dan bagaimana cekap struktur data anda boleh.

764
01:08:40,689 --> 01:08:44,490
Adakah hasil fungsi hash anda dalam banyak perlanggaran?

765
01:08:44,490 --> 01:08:46,300
Atau adalah saiz data anda benar-benar besar?

766
01:08:46,300 --> 01:08:49,420
Adakah ia mengambil banyak masa untuk merentasi?

767
01:08:49,420 --> 01:08:54,800
Dalam log pengeja, ia output berapa banyak masa yang anda gunakan untuk beban,

768
01:08:54,800 --> 01:08:57,700
untuk memeriksa, untuk menjalankan saiz, dan memunggah,

769
01:08:57,700 --> 01:09:00,720
dan sebagainya yang disiarkan di Lembaga Besar,

770
01:09:00,720 --> 01:09:03,600
di mana anda boleh bersaing dengan rakan sekelas anda

771
01:09:03,600 --> 01:09:11,350
dan beberapa kakitangan untuk melihat siapa yang mempunyai terpantas ejaan pemeriksa.

772
01:09:11,350 --> 01:09:14,760
Satu perkara yang saya ingin untuk perhatian tentang jadual hash

773
01:09:14,760 --> 01:09:20,470
adalah bahawa terdapat beberapa fungsi yang agak mudah hash yang kita boleh fikirkan.

774
01:09:20,470 --> 01:09:27,240
Sebagai contoh, anda mempunyai 26 baldi, dan jadi baldi setiap

775
01:09:27,240 --> 01:09:30,200
sepadan dengan huruf pertama dalam perkataan,

776
01:09:30,200 --> 01:09:35,229
tetapi yang akan mengakibatkan dalam jadual hash yang cukup tidak seimbang

777
01:09:35,229 --> 01:09:40,979
kerana terdapat banyak kurang perkataan yang bermula dengan X daripada bermula dengan M, misalnya.

778
01:09:40,979 --> 01:09:47,890
Salah satu cara untuk pergi tentang pengeja adalah jika anda ingin mendapatkan semua fungsi lain,

779
01:09:47,890 --> 01:09:53,240
kemudian hanya menggunakan fungsi hash mudah dapat untuk mendapatkan kod anda berjalan

780
01:09:53,240 --> 01:09:58,650
dan kemudian kembali dan mengubah saiz jadual hash anda dan definisi.

781
01:09:58,650 --> 01:10:03,430
Terdapat banyak sumber di Internet untuk fungsi hash,

782
01:10:03,430 --> 01:10:08,250
dan demikian bagi pset ini anda dibenarkan untuk penyelidikan fungsi hash di Internet

783
01:10:08,250 --> 01:10:15,560
untuk beberapa petunjuk dan inspirasi selagi anda pastikan untuk memetik mana anda mendapat dari.

784
01:10:15,560 --> 01:10:22,060
Anda dialu-alukan untuk melihat dan mentafsir beberapa fungsi hash yang anda mencari di Internet.

785
01:10:22,060 --> 01:10:27,460
Kembali ke itu, anda mungkin dapat melihat jika seseorang menggunakan indone

786
01:10:27,460 --> 01:10:31,700
sama ada pelaksanaan mereka adalah lebih cepat daripada jadual hash anda atau tidak.

787
01:10:31,700 --> 01:10:35,290
Anda boleh mengemukakan kepada Lembaga The Big beberapa kali.

788
01:10:35,290 --> 01:10:37,660
Ia akan merekodkan penyertaan anda paling terkini.

789
01:10:37,660 --> 01:10:44,300
Jadi mungkin anda menukar fungsi hash anda dan kemudian menyedari bahawa ia sebenarnya banyak yang lebih cepat

790
01:10:44,300 --> 01:10:46,780
atau banyak perlahan daripada sebelumnya.

791
01:10:46,780 --> 01:10:50,960
Itulah sedikit cara yang menyeronokkan.

792
01:10:50,960 --> 01:10:57,190
Selalu ada 1 atau 2 ahli kakitangan yang cuba untuk membuat kamus perlahan mungkin,

793
01:10:57,190 --> 01:11:00,210
supaya sentiasa menyeronokkan untuk melihat.

794
01:11:00,210 --> 01:11:07,630
>> Penggunaan untuk pset yang anda menjalankan pengeja dengan kamus pilihan

795
01:11:07,630 --> 01:11:12,840
dan kemudian fail teks mandatori.

796
01:11:12,840 --> 01:11:18,380
Secara lalai apabila anda menjalankan pengeja dengan hanya fail teks dan tidak menentukan kamus,

797
01:11:18,380 --> 01:11:24,410
ia akan menggunakan fail kamus teks, satu besar

798
01:11:24,410 --> 01:11:27,920
dalam folder cs50/pset5/dictionaries.

799
01:11:27,920 --> 01:11:32,760
Satu yang mempunyai lebih 100,000 patah perkataan.

800
01:11:32,760 --> 01:11:37,950
Mereka juga mempunyai kamus kecil yang mempunyai agak kurang perkataan

801
01:11:37,950 --> 01:11:40,730
CS50 yang telah dibuat untuk anda.

802
01:11:40,730 --> 01:11:44,050
Walau bagaimanapun, anda boleh sangat mudah hanya membuat kamus anda sendiri

803
01:11:44,050 --> 01:11:47,150
jika anda hanya mahu bekerja dalam contoh-contoh kecil -

804
01:11:47,150 --> 01:11:51,140
sebagai contoh, jika anda mahu menggunakan Pra-Pemasangan dan anda tahu nilai tertentu

805
01:11:51,140 --> 01:11:53,560
yang anda mahu jadual hash anda untuk merancang.

806
01:11:53,560 --> 01:12:00,430
Jadi, anda hanya boleh membuat fail teks anda sendiri hanya dengan BAR, Baz, FOO, dan foobar,

807
01:12:00,430 --> 01:12:04,860
membuat bahawa dalam fail teks, memisahkan mereka masing-masing dengan baris 1,

808
01:12:04,860 --> 01:12:12,670
dan kemudian membuat fail teks anda sendiri yang benar-benar hanya mengandungi mungkin 1 atau 2 perkataan

809
01:12:12,670 --> 01:12:15,950
supaya anda tahu apa yang output harus.

810
01:12:15,950 --> 01:12:21,870
Sebahagian daripada fail teks sampel bahawa Lembaga Besar apabila anda menghadapi cabaran akan memeriksa

811
01:12:21,870 --> 01:12:25,580
Perang dan Keamanan dan novel Jane Austen atau sesuatu seperti itu.

812
01:12:25,580 --> 01:12:30,450
Jadi apabila anda bermula, ia adalah lebih mudah untuk membuat fail teks anda sendiri

813
01:12:30,450 --> 01:12:34,160
yang mengandungi hanya beberapa perkataan atau mungkin 10

814
01:12:34,160 --> 01:12:38,280
supaya anda boleh meramalkan apa keputusan harus

815
01:12:38,280 --> 01:12:42,880
dan kemudian memeriksa terhadap itu, jadi lebih contoh terkawal.

816
01:12:42,880 --> 01:12:45,820
Dan sebagainya kerana kita sedang berurusan dengan meramalkan dan lukisan perkara-perkara di sekeliling,

817
01:12:45,820 --> 01:12:48,690
sekali lagi saya ingin menggalakkan anda untuk menggunakan pen dan kertas

818
01:12:48,690 --> 01:12:50,700
kerana ia benar-benar akan membantu anda dengan yang satu ini -

819
01:12:50,700 --> 01:12:55,620
lukisan anak panah, bagaimana jadual hash atau bagaimana indone anda kelihatan,

820
01:12:55,620 --> 01:12:57,980
apabila anda membebaskan sesuatu di mana anak panah akan,

821
01:12:57,980 --> 01:13:01,730
anda memegang kepada cukup, adakah anda melihat link hilang

822
01:13:01,730 --> 01:13:05,750
dan jatuh ke jurang memori bocor.

823
01:13:05,750 --> 01:13:11,070
Jadi sila, sila cuba untuk menarik perkara-perkara yang keluar walaupun sebelum anda mendapat untuk menulis kod turun.

824
01:13:11,070 --> 01:13:14,520
Lukiskan perkara supaya anda memahami bagaimana perkara akan bekerja

825
01:13:14,520 --> 01:13:22,750
kerana saya jamin anda akan berjalan ke muddles penunjuk kurang di sana.

826
01:13:24,270 --> 01:13:25,910
>> Semua hak.

827
01:13:25,910 --> 01:13:28,780
Saya mahu ingin anda yang terbaik nasib dengan pset ini.

828
01:13:28,780 --> 01:13:31,980
Ia mungkin salah satu yang paling sukar.

829
01:13:31,980 --> 01:13:40,360
Oleh itu, cuba untuk memulakan awal, lukiskan perkara keluar, lukiskan perkara keluar, dan nasib baik.

830
01:13:40,360 --> 01:13:42,980
Ini adalah Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]