1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Kiirtutvustus - Ülesanded 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Harvardi Ülikool]

3
00:00:04,870 --> 00:00:07,190
[See on CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Hea küll. Tere kõigile ja tere tulemast kiirtutvustus 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 on õigekirjavead, mida me teeme õigekirja kontrollija.

6
00:00:17,400 --> 00:00:21,030
Õigekirja-kabe on väga oluline.

7
00:00:21,030 --> 00:00:23,390
Kas see sinuga on juhtunud?

8
00:00:23,390 --> 00:00:27,170
Te töötate väga aare edasi paber kokkupõrge

9
00:00:27,170 --> 00:00:33,120
ja siis veel lõpuks saada väga kuma Rade nagu D või D =

10
00:00:33,120 --> 00:00:39,390
ja kõik, sest oled liverwurst tagaspoiler vaal lai sõna.

11
00:00:39,390 --> 00:00:44,710
Jah, korrektuur oma paprika on küsimus, äärmiselt impotentsus.

12
00:00:44,710 --> 00:00:49,140
See on probleem, mis mõjutab mehine, mehine õpilased.

13
00:00:49,140 --> 00:00:56,260
Kord öeldi mulle minu Sithi klassi piinaja, et ma ei oleks kunagi sattuda hea kolleeg.

14
00:00:56,260 --> 00:01:00,250
Ja see on kõik, mida ma kunagi tahtnud, et kõik on iga laps tahab minu eas,

15
00:01:00,250 --> 00:01:04,569
lihtsalt sattuda hea kolleeg.

16
00:01:04,569 --> 00:01:12,720
Ja mitte iga suvaline kolleeg. No ma tahtsin minna Elevandiluu Õiguslik kolleeg.

17
00:01:12,720 --> 00:01:18,360
Nii et kui ma ei parandada, läinud oleks minu unistused lähevad Harvardi,

18
00:01:18,360 --> 00:01:22,730
Jale või vangla - sa tead, vanglas, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Nii sain endale õigekirja kontrollija.

20
00:01:25,170 --> 00:01:29,380
See on natuke väljavõte üks mu lemmik lausutud sõna kunstnike, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Igatahes, kui ta ütleb, et oluline on õigekirja kontrollija on väga oluline.

22
00:01:34,630 --> 00:01:39,440
>> Nii et tere tulemast kiirtutvustus 5, kus me räägime pset5: õigekirjavead,

23
00:01:39,440 --> 00:01:44,300
kus teeme meie oma õigekirja kontrollija.

24
00:01:44,300 --> 00:01:50,880
Tööriistakasti sel nädalal, jaotus-koodi, saab olema oluline vaadata

25
00:01:50,880 --> 00:01:54,950
lihtsalt mõista erinevaid funktsioone, et teie sõnaraamat läheb on.

26
00:01:54,950 --> 00:02:01,500
Me tegelikult saab olema mitmiktundlike. C failid, mis kokku moodustavad meie pset.

27
00:02:01,500 --> 00:02:05,420
Ja nii vaadates läbi eri aspekte, kuigi me tegelikult ei toimetamine

28
00:02:05,420 --> 00:02:10,770
üks failid, speller.c, teades, kuidas see toimib seoses dictionary.c,

29
00:02:10,770 --> 00:02:14,100
mis me kirjalikult, saab olema päris oluline.

30
00:02:14,100 --> 00:02:16,970
Pset spec sisaldab ka palju kasulikku teavet

31
00:02:16,970 --> 00:02:21,360
seisukohalt asju, mida saate endale reeglid ja asjad niimoodi,

32
00:02:21,360 --> 00:02:24,710
seda kindlasti lugeda pset spec hoolikalt näpunäiteid.

33
00:02:24,710 --> 00:02:29,310
Ja kui kahtled normi või midagi sellist, siis alati viidata pset spec

34
00:02:29,310 --> 00:02:31,550
või arutada.

35
00:02:31,550 --> 00:02:34,060
See pset läheb sõltuvad suuresti suunanäitajaks,

36
00:02:34,060 --> 00:02:37,890
nii et me tahame veenduda, et me mõista erinevust lisades tärni

37
00:02:37,890 --> 00:02:41,680
ees kursor nime ja sümboliga, kuidas vaba neist jne

38
00:02:41,680 --> 00:02:47,550
Nii on kapten viiteid saab olema väga kasulik seda probleemi komplekti.

39
00:02:47,550 --> 00:02:50,460
Me läheme vaatama lingitud nimekirjad natuke rohkem,

40
00:02:50,460 --> 00:02:57,790
kus meil on elemendid, mida me nimetame sõlmed, mis on nii raha kui ka osuti

41
00:02:57,790 --> 00:03:02,520
Järgmise sõlme, ja nii sisuliselt ühendab eri elemente üksteise järel.

42
00:03:02,520 --> 00:03:07,190
Siin on mõned erinevad võimalused rakendada oma tegelikku sõnaraamat.

43
00:03:07,190 --> 00:03:13,150
Me läheme vaatama kahte peamist meetodit, mis on hash tabeleid ning proovib.

44
00:03:13,150 --> 00:03:17,660
Mõlemal neist, nendega kaasneb mingi mõiste seotud nimekirja

45
00:03:17,660 --> 00:03:20,790
kus te olete elemendid omavahel seotud.

46
00:03:20,790 --> 00:03:25,640
Ja nii me lähme vaatame üle kuidas te võite olla võimeline töötama ümber seotud nimekirju,

47
00:03:25,640 --> 00:03:29,680
luua neile, navigeerida osas, kuidas näiteks sisestada sõlme sinna

48
00:03:29,680 --> 00:03:32,760
või tasuta kõik sõlmed samuti.

49
00:03:32,760 --> 00:03:34,740
Seoses vabastades sõlmed, mis on tõesti oluline

50
00:03:34,740 --> 00:03:37,700
et kui me malloc mälu, hiljem me vabastada ta.

51
00:03:37,700 --> 00:03:42,910
Nii et me tahame veenduda, et ükski osuti läheb unfreed, et meil ei ole mingit mälu lekkeid.

52
00:03:42,910 --> 00:03:48,330
Me läheme sisse tööriista nimega Valgrind, mis töötab oma programmi

53
00:03:48,330 --> 00:03:52,260
ja kontrolli kas kõik mälu, et sa eraldatakse seejärel vabastada.

54
00:03:52,260 --> 00:03:59,080
Sinu pset on ainult lõpule viidud, kui see toimib ja see on kõik funktsioonid,

55
00:03:59,080 --> 00:04:03,990
vaid ka Valgrind ütleb, et teil ei ole leidnud ühtegi mälu lekkeid.

56
00:04:03,990 --> 00:04:06,690
Lõpuks, see pset, ma tõesti tahan rõhutada -

57
00:04:06,690 --> 00:04:11,360
Ma mõtlen, et nagu tavaliselt, olen kindlasti toetaja pliiatsi ja paberi jaoks su probleem komplekti,

58
00:04:11,360 --> 00:04:14,840
kuid see üks, ma arvan, et pliiats ja paber saab olema eriti oluline

59
00:04:14,840 --> 00:04:19,000
kui sa tahad olla joonistus nooli asju ja mõista, kuidas asjad töötavad.

60
00:04:19,000 --> 00:04:24,440
Nii et kindlasti proovida kasutada paberit ja pliiatsit teha asju enne kui sa kodeerimine

61
00:04:24,440 --> 00:04:26,970
sest see võib natuke segane.

62
00:04:26,970 --> 00:04:30,700
>> Esiteks, ärgem minna lingitud nimekirjad natuke.

63
00:04:30,700 --> 00:04:35,510
Seotud nimekirjad koosnevad sõlmed, kus iga tipu väärtuse sellega seotud,

64
00:04:35,510 --> 00:04:39,810
samuti kursor järgmisele sõlme pärast seda.

65
00:04:39,810 --> 00:04:43,680
Paar asja tähtis seotud nimekirjad on, et me peame meeles pidama,

66
00:04:43,680 --> 00:04:48,810
kus meie esimene sõlm on, ja siis kui me teame, kus esimese sõlme on,

67
00:04:48,810 --> 00:04:52,990
Nii saame juurde sõlme, et esimese sõlme võrra

68
00:04:52,990 --> 00:04:55,850
ja siis üksteise järel, et ja üks pärast seda.

69
00:04:55,850 --> 00:05:00,340
Ja siis viimase elemendi oma lingitud nimekiri on, et sõlm pointer

70
00:05:00,340 --> 00:05:02,340
alati saab viidata NULL.

71
00:05:02,340 --> 00:05:08,230
Kui sõlme võrra null, siis sa tead, et olete jõudnud nimekirja lõppu,

72
00:05:08,230 --> 00:05:12,320
et sõlm on viimane, et seal on midagi pärast seda.

73
00:05:12,320 --> 00:05:16,970
Siin skeem, näed, et nooled on suunanäitajaks,

74
00:05:16,970 --> 00:05:20,290
ja sinine osa on, kui väärtus on salvestatud,

75
00:05:20,290 --> 00:05:24,420
ja siis punase kasti kursor on sõlm pointer

76
00:05:24,420 --> 00:05:27,050
osutades järgmise sõlme pärast seda.

77
00:05:27,050 --> 00:05:33,730
Ja nii sa näed siin, D sõlme viitaks NULL, sest see on viimase elemendi nimekirja.

78
00:05:33,730 --> 00:05:38,240
>> Vaatame, kuidas me võiksime määratleda struct jaoks sõlme.

79
00:05:38,240 --> 00:05:40,130
Ja kuna me tahame olla mitu tippu,

80
00:05:40,130 --> 00:05:43,180
see saab muutuda typedef struktuure

81
00:05:43,180 --> 00:05:46,870
kus me lähed on mitmeid erinevaid juhtumeid sõlmed.

82
00:05:46,870 --> 00:05:50,850
Ja nii me defineerime seda kui uue andmetüübi.

83
00:05:50,850 --> 00:05:53,630
Siin on meil typedef struktuure sõlme.

84
00:05:53,630 --> 00:05:56,160
Selles näites me tegeleme täisarv tippu,

85
00:05:56,160 --> 00:06:00,490
nii et meil on täisarv nimega väärtus ja siis on meil veel üks pointer,

86
00:06:00,490 --> 00:06:07,390
ja sel juhul on see kursor sõlme, seega on meil struct tipp * nimega kõrval.

87
00:06:07,390 --> 00:06:09,520
Ja siis me nõuame kogu see asi sõlme.

88
00:06:09,520 --> 00:06:11,110
Veenduge, et te järgite seda süntaksit.

89
00:06:11,110 --> 00:06:17,940
Pange tähele, et sõlm on tegelikult viidatud ülevalt kui ka allpool looksulg.

90
00:06:17,940 --> 00:06:23,400
Siis jälgida, kus mu esimene sõlm on selles seotud nimekirja,

91
00:06:23,400 --> 00:06:29,390
siis on mul sõlme osuti nimetatakse pea, ja ma malloc piisavalt ruumi suurust sõlme.

92
00:06:29,390 --> 00:06:36,240
Pane tähele, et pea on tegelikult sõlme osuti mitte tegelik sõlme ise.

93
00:06:36,240 --> 00:06:40,130
Nii pea tegelikult ei sisalda mingit väärtust,

94
00:06:40,130 --> 00:06:45,590
see ainult viitab kumb esimese sõlme minu lingitud nimekiri on.

95
00:06:55,080 --> 00:06:58,340
>> Et saada paremat tunnet seotud nimekirjades, sest see on väga oluline

96
00:06:58,340 --> 00:07:02,220
jälgida ja veenduge, et teil säilitada kett,

97
00:07:02,220 --> 00:07:09,990
Mulle meeldib mõelda sellest kui inimesed liini hoides käed,

98
00:07:09,990 --> 00:07:14,330
kus iga inimene, kellel käed kõrval üks.

99
00:07:14,330 --> 00:07:18,350
Te ei näe selles joonistus, kuid põhimõtteliselt nad osutades järgmisele inimesele

100
00:07:18,350 --> 00:07:23,760
mis on nende kett.

101
00:07:23,760 --> 00:07:29,270
Ja nii et kui soovite läbida seotud nimekirja, kus need inimesed -

102
00:07:29,270 --> 00:07:32,830
kujutan ette, kõik need inimesed on väärtused nendega

103
00:07:32,830 --> 00:07:36,590
ja siinkohal ka järgmisele inimesele rida -

104
00:07:36,590 --> 00:07:40,810
kui soovite läbida seotud nimekirja, näiteks kas muuta väärtused

105
00:07:40,810 --> 00:07:42,830
või leidke väärtus või midagi sellist,

106
00:07:42,830 --> 00:07:48,270
siis sa tahad olla kursor konkreetse isikuga.

107
00:07:48,270 --> 00:07:52,670
Nii et me lähed on andmetüüp sõlme pointer.

108
00:07:52,670 --> 00:07:55,580
Sel juhul olgem kutsuvad seda kursor.

109
00:07:55,580 --> 00:07:59,630
Teine levinud viis nimetada see oleks iteraatori või midagi sellist

110
00:07:59,630 --> 00:08:05,130
sest see on itereerimise üle ja tegelikult liigub, mis sõlme see osutab.

111
00:08:05,130 --> 00:08:14,410
See siin on meie kursor.

112
00:08:14,410 --> 00:08:20,180
Meie kursor Kõigepealt esimene osa meie nimekirjas.

113
00:08:20,180 --> 00:08:26,910
Ja nii me tahame teha, on meil oleks põhimõtteliselt võimalik jätkata kursori

114
00:08:26,910 --> 00:08:29,130
liigutamine küljelt küljele.

115
00:08:29,130 --> 00:08:33,409
Sellisel juhul me tahame liikuda selle järgmisele element nimekirjas.

116
00:08:33,409 --> 00:08:38,480
Massiivid, mida me teeks on me lihtsalt ütleme, et me suurendada indeks 1.

117
00:08:38,480 --> 00:08:46,020
Sel juhul, mida me peame tegema, on tegelikult leida mis inimene see praegune inimene on suunaga,

118
00:08:46,020 --> 00:08:48,930
ja mis saab olema järgmine väärtus.

119
00:08:48,930 --> 00:08:53,230
Nii et kui kursor on lihtsalt sõlme pointer, siis mida me tahame teha

120
00:08:53,230 --> 00:08:56,320
on me tahame saada raha, et kursor osutab.

121
00:08:56,320 --> 00:09:01,350
Me tahame saada selle sõlme ja siis, kui me oleme selle sõlme leida, kui see osutab.

122
00:09:01,350 --> 00:09:05,820
Et saada tegelik sõlme, et kursor on suunaga,

123
00:09:05,820 --> 00:09:13,160
tavaliselt me ​​näitama seda (* kursor).

124
00:09:13,160 --> 00:09:19,160
See annaks sulle tegeliku sõlme, et kursor osutab.

125
00:09:19,160 --> 00:09:21,730
Ja siis pärast seda, mida me tahame teha, on me tahame pääseda

126
00:09:21,730 --> 00:09:25,680
mida iganes see sõlm järgmisel väärtus on.

127
00:09:25,680 --> 00:09:32,820
Selleks, et pääseda väärtused sees struct, meil dot operaator.

128
00:09:32,820 --> 00:09:39,530
Nii et siis oleks (* kursor). Kõrval.

129
00:09:39,530 --> 00:09:44,840
Aga see on natuke räpane mõttes võttes sulgudes ümber * kursori

130
00:09:44,840 --> 00:09:56,800
ja nii me asendada kogu see avaldus koos kursori->.

131
00:09:56,800 --> 00:10:02,700
See on kriips ja siis üle kirjutada, muutes nõnda nool.

132
00:10:02,700 --> 00:10:05,840
kursori-> next.

133
00:10:05,840 --> 00:10:12,390
See tegelikult sulle sõlme, et kursor osutab. See väärtus on järgmine.

134
00:10:12,390 --> 00:10:16,790
Nii et selle asemel, täht-ja täpp, sa oled asendades selle noolega.

135
00:10:16,790 --> 00:10:24,820
Ole väga ettevaatlik veenduda, et sa püüad seda süntaksit kasutada.

136
00:10:33,550 --> 00:10:37,620
>> Nüüd, kui meil on kursor, kui me tahame pääseda väärtus,

137
00:10:37,620 --> 00:10:40,450
enne oli meil kursori-> next,

138
00:10:40,450 --> 00:10:46,260
kuid juurdepääsu väärtus sõlme, et kursor on suunaga, me lihtsalt lihtsalt öelda

139
00:10:46,260 --> 00:10:48,070
sõlm-> väärtus.

140
00:10:48,070 --> 00:10:53,600
Sealt see andmete tüüp iganes oleme määratletud väärtused ja sõlmede olla.

141
00:10:53,600 --> 00:10:59,620
Kui see on int sõlme, siis kursori-> väärtus on lihtsalt saab olema täisarv.

142
00:10:59,620 --> 00:11:04,870
Nii et me saame teha operatsioone, et kontrollida võrdused, määrata selle erinevaid väärtusi jne

143
00:11:04,870 --> 00:11:11,090
Nii siis mida sa teha tahad, kui soovite kursori järgmisele inimesele,

144
00:11:11,090 --> 00:11:15,270
sa tegelikult väärtuse muutmiseks kursor.

145
00:11:15,270 --> 00:11:19,340
Kuna kursor on sõlm pointer, muudad tegelikult osuti aadress

146
00:11:19,340 --> 00:11:23,890
aadressile, järgmise sõlme oma nimekirja.

147
00:11:23,890 --> 00:11:28,930
See on lihtsalt mingi kood, kuhu võiks itereerima.

148
00:11:28,930 --> 00:11:31,230
Kui mul on Kommentaari midagi teha,

149
00:11:31,230 --> 00:11:33,850
see on kui sa oled ilmselt läheb pääseda väärtus

150
00:11:33,850 --> 00:11:37,850
või tegema midagi pistmist selle konkreetse sõlme.

151
00:11:37,850 --> 00:11:43,050
Et alustada selle ära, ma ütlen, et minu kursor esialgu

152
00:11:43,050 --> 00:11:48,430
läheb punkti esimese osa seotud nimekirja.

153
00:11:48,430 --> 00:11:52,910
Ja nii kuni edasi, ma määratletud see juhina sõlme.

154
00:11:52,910 --> 00:11:57,610
>> Nagu ütlesin, vabastades on tõepoolest oluline.

155
00:11:57,610 --> 00:12:02,440
Sa tahad teha kindel, et te vabastama iga element nimekirjas, kui olete sellega lõpetanud.

156
00:12:02,440 --> 00:12:04,940
Kui te ei vaja viidata ühelegi neist osuti enam

157
00:12:04,940 --> 00:12:10,620
sa tahad teha kindel, et sa vabastama kõik need viiteid.

158
00:12:10,620 --> 00:12:14,460
Aga sa tahad olla väga ettevaatlik siin, et sa tahad, et vältida mälu lekkeid.

159
00:12:14,460 --> 00:12:25,080
Kui teil vaba üks inimene enneaegselt, siis on kõik suunanäitajaks, et sõlme võrra

160
00:12:25,080 --> 00:12:26,900
hakkavad kaduma.

161
00:12:26,900 --> 00:12:32,070
Tulles tagasi inimene näiteks selleks, et see natuke rohkem kõrgete panustega,

162
00:12:32,070 --> 00:12:49,600
Olgu meil need inimesed, välja arvatud sel juhul nad varjutavad järve koletis.

163
00:12:49,600 --> 00:12:53,200
Me tahame veenduda, et kui me vabad, me ei kaota

164
00:12:53,200 --> 00:12:58,920
ja lase mõni sõlmede enne oleme tegelikult vabastas neile.

165
00:12:58,920 --> 00:13:05,730
Näiteks, kui sa olid lihtsalt helistada tasuta see kutt siin,

166
00:13:05,730 --> 00:13:15,350
siis ta vabastatakse, kuid siis kõik need kutid oleks siis kadunud

167
00:13:15,350 --> 00:13:18,450
ja nad triiv maha ja kukuks.

168
00:13:18,450 --> 00:13:24,900
Nii et me tahame veenduda, et selle asemel, me tahame säilitada link ülejäänud.

169
00:13:37,630 --> 00:13:42,480
Meie pea osuti, mis näitab, et esimene element nimekirjas.

170
00:13:42,480 --> 00:13:49,990
See on nagu köie siduda esimene inimene.

171
00:13:52,870 --> 00:13:57,470
Mida sa tahad teha, kui sa vabaks nimekiri on -

172
00:13:57,470 --> 00:14:04,520
Kui soovite vabastada esimese osa esimene, siis võib olla ajutine pointer

173
00:14:04,520 --> 00:14:07,370
, mis osutab mis tahes Esimene element on.

174
00:14:07,370 --> 00:14:11,420
Nii et teil on oma ajutise osuti osutab siin.

175
00:14:11,420 --> 00:14:15,840
Nii, meil on kätte esimese sõlme.

176
00:14:15,840 --> 00:14:18,930
Ja siis, kuna me teame, et esimese sõlme läheb vabastatakse,

177
00:14:18,930 --> 00:14:24,890
siis saame edasi liikuda see köis, see ankur, meie pea,

178
00:14:24,890 --> 00:14:31,930
tegelikult osutada ükskõik esimene osutab.

179
00:14:31,930 --> 00:14:38,760
Nii et see pea tegelikult osutab teise elemendi nüüd.

180
00:14:38,760 --> 00:14:43,980
Nüüd on lubatud vabastada iganes on salvestatud temp,

181
00:14:43,980 --> 00:14:53,360
ja nii saame kustutada, et ilma selleta ohtu kõik teised sõlmed meie nimekirjas.

182
00:14:54,140 --> 00:15:05,020
Teine võimalus, et sa võiksid seda teha võiks

183
00:15:05,020 --> 00:15:08,650
iga kord, kui lihtsalt vaba viimane element nimekirja

184
00:15:08,650 --> 00:15:11,010
sest nad ei tohi kindlasti märkida midagi.

185
00:15:11,010 --> 00:15:15,570
Nii et võid lihtsalt vabastada see üks, siis tasuta see üks, siis tasuta seda.

186
00:15:15,570 --> 00:15:21,900
See kindlasti töötab kuid on natuke aeglasem, sest iseloom seotud nimekirju,

187
00:15:21,900 --> 00:15:24,670
me ei saa lihtsalt hüpata kohe viimane.

188
00:15:24,670 --> 00:15:28,030
Meil on läbida iga element seotud nimekirja

189
00:15:28,030 --> 00:15:31,020
ja kas, et üks on suunaga null, kontrollida iga kord,

190
00:15:31,020 --> 00:15:33,780
ja siis kui jõuame lõpuks, siis vaba sellest.

191
00:15:33,780 --> 00:15:40,270
Kui sa olid seda protsessi, siis oleks tegelikult kontrollida siin,

192
00:15:40,270 --> 00:15:44,190
kontroll siin, siis kontrollides siin, vabastades ta,

193
00:15:44,190 --> 00:15:47,470
siis lähen tagasi, kontroll siin, kontroll siin, vabastades ta,

194
00:15:47,470 --> 00:15:49,660
kontroll siin, ja siis vabastades ta.

195
00:15:49,660 --> 00:15:52,880
See võtab natuke rohkem aega. Jah.

196
00:15:52,880 --> 00:15:59,060
>> [Üliõpilane] Kas oleks võimalik siduda nimekiri, mis salvestab väljumise kursor lõpus?

197
00:15:59,060 --> 00:16:01,320
See oleks kindlasti võimalik.

198
00:16:01,320 --> 00:16:08,340
Kordan küsimust, kas on võimalik olla seotud nimekirja struktuur

199
00:16:08,340 --> 00:16:12,490
nii, et teil on osuti osutab lõppu seotud nimekirja?

200
00:16:12,490 --> 00:16:18,090
Ma ütleks, et see on võimalik, ja iga kord, kui sisestad midagi oma seotud nimekirja

201
00:16:18,090 --> 00:16:21,470
siis oleks uuendada, et osuti ja asjad niimoodi.

202
00:16:21,470 --> 00:16:26,640
Sa oleks sõlme * saba, näiteks.

203
00:16:26,640 --> 00:16:29,840
Aga kui sa rakendatakse seda funktsiooni, peate mõtlema kompromisse,

204
00:16:29,840 --> 00:16:32,700
meeldib, kui mitu korda ma seda tuleb itereerimise üle selle,

205
00:16:32,700 --> 00:16:36,100
kui raske see saab olema jälgida saba samuti pea

206
00:16:36,100 --> 00:16:38,400
samuti minu iteraatori ja asjad niimoodi.

207
00:16:40,730 --> 00:16:42,480
Kas see -? >> [Üliõpilane] Jah.

208
00:16:42,480 --> 00:16:48,270
On võimalik, kuid nii disaini otsuseid, sa pead kaaluma võimalusi.

209
00:16:53,850 --> 00:17:01,090
>> Siin on skelett kood, mis võimaldab teil vabastada iga element seotud nimekirja.

210
00:17:01,090 --> 00:17:05,460
Jällegi, kuna ma olen itereerimise üle seotud nimekirja, ma lähen taha olla mingi kursor

211
00:17:05,460 --> 00:17:08,670
või iteraatori.

212
00:17:08,670 --> 00:17:14,640
Meil on itereerimise kuni kursor on NULL.

213
00:17:14,640 --> 00:17:17,640
Sa ei taha kinnitada, kui kursor on NULL

214
00:17:17,640 --> 00:17:20,579
sest see tähendab, et ei ole midagi nimekirjas.

215
00:17:20,579 --> 00:17:25,069
Nii siis siin teen ajutine sõlme *

216
00:17:25,069 --> 00:17:29,610
osutades mida ma arvestades on esimene minu nimekirjas

217
00:17:29,610 --> 00:17:35,340
ja siis ma liikuda mu kursori ees 1 ja seejärel vaba iganes mul oli ajutine ladustamine.

218
00:17:38,460 --> 00:17:43,650
>> Nüüd aga aku asetamist lingitud nimekirjad.

219
00:18:00,200 --> 00:18:09,660
Mul on kolm tippe minu lingitud loendi ja lähme koos lihtsa puhul

220
00:18:09,660 --> 00:18:18,970
kuhu me tahame lisada teise sõlme lõpus meie seotud nimekirja.

221
00:18:18,970 --> 00:18:25,980
Selleks, et kõik me teeks on me läbida

222
00:18:25,980 --> 00:18:32,100
leida, kui praegune lõppu lingitud nimekiri on, nii et kumb sõlme osutades null -

223
00:18:32,100 --> 00:18:33,850
see on see üks -

224
00:18:33,850 --> 00:18:37,260
ja siis öelda, tegelikult ei ole see saab olema viimane sõlm;

225
00:18:37,260 --> 00:18:39,830
me tegelikult läheb on teine.

226
00:18:39,830 --> 00:18:46,260
Nii oleks meil see praegune ühest punktist iganes me sisestamist.

227
00:18:46,260 --> 00:18:50,080
Nii et nüüd see punane inimene siin saab viimase sõlme seotud nimekirja.

228
00:18:50,080 --> 00:18:56,080
Ja nii iseloomulik viimase sõlme seotud nimekirja, et see viitab NULL.

229
00:18:56,080 --> 00:19:09,380
Nii siis mida me peaks tegema, on määrata see punane mees on pointer on NULL. Seal.

230
00:19:09,380 --> 00:19:25,370
>> Aga kui me tahame lisada sõlme vahel teine ​​ja kolmas?

231
00:19:25,370 --> 00:19:28,960
See üks ei ole päris nii lihtne, sest me tahame veenduda

232
00:19:28,960 --> 00:19:34,290
et me ei lase ühtegi sõlme meie seotud nimekirja.

233
00:19:34,290 --> 00:19:43,450
Mida me peame tegema, on veenduge, et me kinnistada end igaüks.

234
00:19:43,450 --> 00:19:49,900
Näiteks olgem nimetame seda teist.

235
00:19:49,900 --> 00:19:54,390
Kui sa ütlesid teine ​​nüüd juhib seda uuega

236
00:19:54,390 --> 00:20:02,520
ja just tehtud pointer seal, siis oleks tulemuseks see kutt on kadunud

237
00:20:02,520 --> 00:20:07,830
sest seal ei ole mingit seost temaga.

238
00:20:07,830 --> 00:20:18,970
Selle asemel - ma joonistan selle uuesti. Vabandage mu kunstiliste võimete.

239
00:20:18,970 --> 00:20:26,570
Me teame, et me ei saa lihtsalt otse ühendada 2 uuega.

240
00:20:26,570 --> 00:20:30,480
Me peame tagama, et me kinni hoida viimane.

241
00:20:30,480 --> 00:20:39,200
Mida me võiksime teha tahad on olla ajutine pointer

242
00:20:39,200 --> 00:20:42,650
element, mis saab olema maatriksi.

243
00:20:42,650 --> 00:20:45,140
Siis on meil ajutine pointer seal.

244
00:20:45,140 --> 00:20:50,780
Kuna me teame, et see kolmas on hoitakse silma peal,

245
00:20:50,780 --> 00:20:53,680
2 saab nüüd link meie uus.

246
00:20:53,680 --> 00:20:57,490
Ja kui see uus punane poiss saab olema vahemikus 2 ja 3,

247
00:20:57,490 --> 00:21:05,550
siis mis on selle kuti osuti läheb osutada? >> [Üliõpilane] Temp.

248
00:21:05,550 --> 00:21:07,490
Temp. Jah.

249
00:21:07,490 --> 00:21:15,430
Nii et siis see punane kuti kõrval väärtus saab olema temp.

250
00:21:26,090 --> 00:21:33,010
Kui olete aku asetamist lingitud nimekirjad nägime, et me võiksime

251
00:21:33,010 --> 00:21:38,260
lihtsalt lisada midagi lõpuni, luues ajutine massiiv,

252
00:21:38,260 --> 00:21:42,850
või kui me tahame midagi lisada keskele meie massiiv,

253
00:21:42,850 --> 00:21:46,810
siis see võtaks natuke rohkem nohinat.

254
00:21:46,810 --> 00:21:50,240
Kui soovite näiteks on järjestatud seotud nimekirja,

255
00:21:50,240 --> 00:21:54,880
siis sa pead mingi kaaluma kulude ja tulude kohta, mis

256
00:21:54,880 --> 00:21:59,720
sest kui sa tahad olla järjestatud hulga, mis tähendab, et iga kord, kui lisada see,

257
00:21:59,720 --> 00:22:01,630
see aega võtab natuke rohkem aega.

258
00:22:01,630 --> 00:22:05,500
Siiski, kui soovite hiljem, kui me leiame me tahame,

259
00:22:05,500 --> 00:22:10,280
otsingu kaudu seotud nimekirja, siis oleks lihtsam, kui tead, et kõik on korras.

260
00:22:10,280 --> 00:22:15,340
Nii et te võiksite kaaluda kulusid ja tulusid nii.

261
00:22:20,150 --> 00:22:27,740
>> Teine võimalus lisada lingitud nimekiri on lisada algusest nimekirja.

262
00:22:27,740 --> 00:22:34,700
Kui me võtame oma ankur siin - see on meie peas -

263
00:22:34,700 --> 00:22:40,960
ja siis on need inimesed sellega seotud,

264
00:22:40,960 --> 00:22:48,460
ja siis on meil uus sõlm, et lisada alguses,

265
00:22:48,460 --> 00:22:52,590
siis milline võiks me tahame teha?

266
00:22:55,220 --> 00:23:03,580
Mis oleks viga lihtsalt ütlen ma tahan siduda punane sinine,

267
00:23:03,580 --> 00:23:05,790
sest see on esimene?

268
00:23:05,790 --> 00:23:08,570
Mis juhtuks siin?

269
00:23:08,570 --> 00:23:12,130
Kõik need kolm oleks eksida.

270
00:23:12,130 --> 00:23:14,140
Nii et me ei taha seda teha.

271
00:23:14,140 --> 00:23:21,430
Jällegi, me oleme õppinud, et me peame olema mingi ajutine kursor.

272
00:23:21,430 --> 00:23:34,470
Valime on ajutine käsk see kutt.

273
00:23:34,470 --> 00:23:39,640
Siis saame sinine ühest punktist ajutine

274
00:23:39,640 --> 00:23:43,240
ja siis punane käsk sinine.

275
00:23:43,240 --> 00:23:47,830
Põhjus, miks ma kasutan inimesed siin on, sest me tõesti tahame visualiseerida

276
00:23:47,830 --> 00:23:53,180
ettevõttest inimesi ning tagada, et meil on link neile

277
00:23:53,180 --> 00:23:57,590
enne kui me lasta minna teise käega või midagi sellist.

278
00:24:05,630 --> 00:24:10,650
>> Nüüd, kui meil on mõttes seotud nimekirjad - kuidas me võiksime luua seotud nimekirja

279
00:24:10,650 --> 00:24:15,090
ning luua struktuurid, mis koosnevad tüüp määratlus sõlme

280
00:24:15,090 --> 00:24:19,060
ja siis veendudes, et meil on viit pea selle lingitud nimekiri -

281
00:24:19,060 --> 00:24:23,210
kui meil on see ja me teame, kuidas läbida kaudu array,

282
00:24:23,210 --> 00:24:28,200
juurdepääs erinevaid elemente, me teame, kuidas sisestada ja me teame, kuidas vaba neist,

283
00:24:28,200 --> 00:24:30,260
siis saame võtta õigekirjavead.

284
00:24:30,260 --> 00:24:38,150
Nagu tavaliselt, on meil osa küsimusi, mis sulle harjunud tegutsema koos lingitud nimekirjad

285
00:24:38,150 --> 00:24:41,750
ja erinevate struktuuride nagu järjekorrad ja korstnad.

286
00:24:41,750 --> 00:24:46,000
Siis saame liikuda õigekirjavead.

287
00:24:46,000 --> 00:24:55,170
>> Õigekirjavead on jaotuse kood paar faili tähtsust.

288
00:24:55,170 --> 00:24:58,850
Esiteks näeme, et meil on see Makefile siin,

289
00:24:58,850 --> 00:25:03,040
mida me ei ole tegelikult varem kohanud.

290
00:25:03,040 --> 00:25:10,090
Kui sa vaatasid sees pset5 kausta soovid teate, et teil on. H faili

291
00:25:10,090 --> 00:25:12,530
siis on sul kaks. c faile.

292
00:25:12,530 --> 00:25:18,920
Mis see Makefile ei ole enne, oleksime lihtsalt kirjuta teha ja siis programmi nimi

293
00:25:18,920 --> 00:25:25,550
ja siis näeme kõik need argumendid ja lipud möödunud aastal, et kompilaator.

294
00:25:25,550 --> 00:25:30,580
Mis Makefile ei ole võimaldab meil koostada mitu faili korraga

295
00:25:30,580 --> 00:25:34,650
ja läbima lipud, et me tahame.

296
00:25:34,650 --> 00:25:41,300
Siin me lihtsalt vaata seal päisefail siin.

297
00:25:41,300 --> 00:25:43,730
Siis tegelikult on kaks allikas faile.

298
00:25:43,730 --> 00:25:47,520
Meil on speller.c ja dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Olete oodatud redigeerida Makefile, kui soovite.

300
00:25:54,560 --> 00:26:03,310
Pange tähele, et siin kui tipite puhas, siis mida ta teeb on tegelikult eemaldab midagi

301
00:26:03,310 --> 00:26:06,340
mis on tuum.

302
00:26:06,340 --> 00:26:09,190
Kui sul killustatust süü, põhimõtteliselt sa saad core dump.

303
00:26:09,190 --> 00:26:13,260
Nii et see kole vähe faili ilmuvad kataloog nimega tuum.

304
00:26:13,260 --> 00:26:16,310
Sa tahad eemaldama, et teha puhtaks.

305
00:26:16,310 --> 00:26:20,940
See eemaldab kõik exe failid ja. O faile.

306
00:26:27,900 --> 00:26:30,220
>> Võtame uurima dictionary.h.

307
00:26:30,220 --> 00:26:34,410
See ütleb, et ta deklareerib sõnaraamat funktsionaalsust.

308
00:26:34,410 --> 00:26:39,530
Meil on maksimaalne pikkus iga sõna sõnastikus.

309
00:26:39,530 --> 00:26:45,130
Me ütleme, et see saab olema pikim võimalik sõna. See on pikkusega 45.

310
00:26:45,130 --> 00:26:48,900
Nii et me ei kavatse olla mis tahes sõna, et ületa pikkus.

311
00:26:48,900 --> 00:26:50,980
Siin me lihtsalt funktsiooni prototüüpe.

312
00:26:50,980 --> 00:26:55,290
Meil ei ole tegelikku rakendamist, sest see on, mida me tegema selle pset.

313
00:26:55,290 --> 00:26:59,940
Aga mida see teeb, on alates me tegeleme suuremate failide siin

314
00:26:59,940 --> 00:27:06,650
ja funktsionaalsus suuremas mastaabis, on kasulik omada. h fail

315
00:27:06,650 --> 00:27:11,290
nii et keegi teine ​​lugemine või kasutades oma koodi saab aru, mis toimub.

316
00:27:11,290 --> 00:27:17,910
Ja võibolla nad soovivad rakendada üritab, kui sa tegid hash tabeleid või vastupidi.

317
00:27:17,910 --> 00:27:21,850
Siis nad ütlevad minu koormus funktsioon,

318
00:27:21,850 --> 00:27:26,950
tegeliku rakendamise läheb erinevad, kuid see prototüüp ei muutu.

319
00:27:26,950 --> 00:27:33,280
Siin me oleme vaadata, mis tagastab true, kui antud sõna on sõnastikus.

320
00:27:33,280 --> 00:27:39,800
Siis oleme koormus, mis põhimõtteliselt võtab sisse sõnastiku faili

321
00:27:39,800 --> 00:27:44,360
ja seejärel laadib see mingi andmestruktuur.

322
00:27:44,360 --> 00:27:47,500
Meil on suurus, mis, kui kutsutakse, tagastab suurust oma sõnaraamat,

323
00:27:47,500 --> 00:27:50,310
kui palju sõnu on salvestatud see,

324
00:27:50,310 --> 00:27:54,390
ja siis maha laadida, mis vabastab kõik mälu, et olete asunud

325
00:27:54,390 --> 00:27:57,900
tehes oma sõnastikku.

326
00:28:01,070 --> 00:28:03,590
>> Võtame pilk dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Me näeme, et see näeb välja väga sarnane dictionary.h, välja arvatud nüüd see lihtsalt on kõik need Todos ta.

328
00:28:10,490 --> 00:28:16,980
Ja nii see on teie töö. Lõpuks saate täites speller.c kogu seda koodi.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, kui joosta, ei ole tõesti midagi teha,

330
00:28:21,540 --> 00:28:29,590
nii et me vaatame suunas speller.c näha tegelikku rakendamist õigekirja kontrollija.

331
00:28:29,590 --> 00:28:32,060
Kuigi te ei kavatse olla redigeerimise tahes käesoleva seadustiku

332
00:28:32,060 --> 00:28:38,050
see on oluline lugeda, mõista kui on koormus nimetatakse, kui ma helistades kontroll,

333
00:28:38,050 --> 00:28:42,350
lihtsalt mõistetav map välja, kuidas toimib.

334
00:28:42,350 --> 00:28:49,860
Me näeme, et see kontrollimine õige kasutamine.

335
00:28:49,860 --> 00:28:55,200
Sisuliselt, kui keegi jookseb speller, näitab see, et see on vabatahtlik

336
00:28:55,200 --> 00:29:00,950
neil läbida sõnastik faili, sest seal saab olla vaikimisi sõnastik faili.

337
00:29:00,950 --> 00:29:05,410
Ja siis nad peavad sooritama tekstis olla õigekirja kontrollida.

338
00:29:05,410 --> 00:29:11,410
rusage tegeleb aega, sest osa sellest pset mis me tegelema hiljem

339
00:29:11,410 --> 00:29:14,790
ei ole ainult saada toimiv õigekirja kontrollija töö

340
00:29:14,790 --> 00:29:17,190
kuid tegelikult saada see olema kiire.

341
00:29:17,190 --> 00:29:22,040
Ja nii siis see on kui rusage on tulemas sisse

342
00:29:22,040 --> 00:29:28,740
Siin näeme esimene kõne ühele meie dictionary.c failid, mis on koormust.

343
00:29:28,740 --> 00:29:34,720
Laadi tagastab true või false - tõsi peale edu, vale jätmise korral.

344
00:29:34,720 --> 00:29:41,400
Nii et kui sõnastik ei laadita korralikult, siis speller.c naaseb 1 ja lõpetan.

345
00:29:41,400 --> 00:29:47,920
Aga kui see ei koorma korralikult, siis see saab jätkuda.

346
00:29:47,920 --> 00:29:50,740
Jätkame, ja me näeme mõnda faili I / O siin,

347
00:29:50,740 --> 00:29:56,210
kus see saab olema tegemist avamist tekstifaili.

348
00:29:56,210 --> 00:30:04,640
Siin Mis see on õigekirja kontrolli iga sõna tekstis.

349
00:30:04,640 --> 00:30:09,270
Mida speller.c teeb siin on itereerimise üle iga sõna tekstifaili

350
00:30:09,270 --> 00:30:12,790
ja siis kontrollida neid sõnaraamat.

351
00:30:24,680 --> 00:30:32,350
Siin on meil Boole'i ​​valesti, et näed, kui kontroll tagastab tõsi või mitte.

352
00:30:32,350 --> 00:30:37,110
Kui sõna on tegelikult sõnastikus, siis kontrolli naaseb tõsi.

353
00:30:37,110 --> 00:30:39,760
See tähendab, et sõna pole valesti kirjutatud.

354
00:30:39,760 --> 00:30:45,330
Nii et valesti oleks vale, ja sellepärast on meil paugu seal märge.

355
00:30:45,330 --> 00:30:56,320
Hoiame läheb, ja siis ta hoiab silma peal, kui palju valesti kirjutatud sõnad

356
00:30:56,320 --> 00:30:58,910
seal on fail.

357
00:30:58,910 --> 00:31:03,870
See jätkub ja sulgeb faili.

358
00:31:03,870 --> 00:31:09,250
Siis siin, esitab ta mitu valesti kirjutatud sõnad, mida oli.

359
00:31:09,250 --> 00:31:12,680
Ta arvutab, kui palju aega kulus laadida sõnastikku

360
00:31:12,680 --> 00:31:15,080
kui palju aega kulus, et seda kontrollida,

361
00:31:15,080 --> 00:31:18,510
kui palju aega kulus, et arvutada suurus,

362
00:31:18,510 --> 00:31:21,260
mis, nagu me lähme, peaks olema väga väike,

363
00:31:21,260 --> 00:31:25,390
ja siis kui palju aega kulus maha laadida sõnaraamat.

364
00:31:25,390 --> 00:31:27,700
Siin kõrgemale näeme kõne maha laadida siit.

365
00:31:27,700 --> 00:31:52,690
Kui me kontrollida suurus siin,

366
00:31:52,690 --> 00:31:59,050
siis näeme, et siin on üleskutse suurus, kus see määrab suuruse sõnaraamat.

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

368
00:32:07,100 --> 00:32:10,920
>> Meie ülesanne selles pset on rakendada koormust, mis laeb sõnaraamat

369
00:32:10,920 --> 00:32:15,480
andmestruktuur - kumb valida, olgu see hash tabelit või proovida -

370
00:32:15,480 --> 00:32:18,810
sõnade sõnaraamatust faili.

371
00:32:18,810 --> 00:32:25,290
Siis on suurus, mis tagastab arvu sõnu sõnastikku.

372
00:32:25,290 --> 00:32:29,860
Ja kui sa rakendada koormust nutikas viis, siis suurus peaks olema üsna lihtne.

373
00:32:29,860 --> 00:32:33,860
Siis on näha, mis kontrollib, kas antud sõna on sõnastikus.

374
00:32:33,860 --> 00:32:38,690
Nii speller.c möödub string, ja siis sa pead kontrollima, kas see string

375
00:32:38,690 --> 00:32:41,610
sisalduvad oma sõnastikku.

376
00:32:41,610 --> 00:32:46,750
Pange tähele, et me üldiselt standard sõnastikud,

377
00:32:46,750 --> 00:32:53,020
kuid selles pset, põhimõtteliselt mis tahes sõnastik möödus mis tahes keeles.

378
00:32:53,020 --> 00:32:57,040
Nii et me ei saa lihtsalt eeldada, et sõna on sees.

379
00:32:57,040 --> 00:33:03,090
Sõna jura võiks määratleda teatud sõnaraamat et võtame sisse

380
00:33:03,090 --> 00:33:07,920
Ja siis on meil maha laadida, mis vabastab sõnaraamat mälust.

381
00:33:07,920 --> 00:33:11,930
>> Esiteks, ma tahaksin minna üle hash tabelit meetod

382
00:33:11,930 --> 00:33:14,630
kuidas me võiksime rakendada kõik need neli funktsiooni,

383
00:33:14,630 --> 00:33:18,650
ja siis ma lähen üle proovib meetod, kuidas me ellu need neli funktsiooni,

384
00:33:18,650 --> 00:33:22,720
ja lõpus rääkida mõned üldised nõuanded, kui sa üritad pset

385
00:33:22,720 --> 00:33:27,870
ja ka seda, kuidas sa võiksid kasutada Valgrind kontrollida mälu lekkeid.

386
00:33:27,870 --> 00:33:30,550
>> Vali nüüd hash tabelit meetod.

387
00:33:30,550 --> 00:33:35,910
Hash tabel koosneb nimekirja ämbrid.

388
00:33:35,910 --> 00:33:43,010
Iga väärtus, iga sõna, läheb minema ühte nendest ämbrid.

389
00:33:43,010 --> 00:33:53,200
Hash tabelit ideaalselt ühtlaselt jaotab kõik need väärtused, mida sa läbides

390
00:33:53,200 --> 00:33:57,160
ja siis asustatakse neid ämber selline, et iga ämber

391
00:33:57,160 --> 00:34:02,000
on umbes sama palju väärtusi ta.

392
00:34:02,000 --> 00:34:09,630
Struktuuri hash tabelit, meil on massiiv seotud nimekirju.

393
00:34:09,630 --> 00:34:17,900
Mida me teeme kui me läbima väärtus, me kontrollime, kui see väärtus peaks kuuluma,

394
00:34:17,900 --> 00:34:23,840
mis ämber see kuulub, ja siis pannakse see seotud nimekirja seostab ämber.

395
00:34:23,840 --> 00:34:28,199
Siin mis mul on räsifunktsiooniga.

396
00:34:28,199 --> 00:34:31,320
See on int hash tabelit.

397
00:34:31,320 --> 00:34:38,540
Nii esimene ämber kõik täisarvud alla 10 läheb esimene ämber.

398
00:34:38,540 --> 00:34:42,190
Iga täisarvu üle 10, kuid alla 20 minna teise,

399
00:34:42,190 --> 00:34:44,179
ja siis nii edasi ja nii edasi.

400
00:34:44,179 --> 00:34:52,370
Minu jaoks on iga ämber esindab neid numbreid.

401
00:34:52,370 --> 00:34:59,850
Kuid öelda, et ma ei liigu 50, näiteks.

402
00:34:59,850 --> 00:35:07,490
Tundub, nagu oleks kolm esimest sisaldama erinevaid kümne numbrid.

403
00:35:07,490 --> 00:35:12,570
Aga ma tahan, et lasta oma hash tabelit võtma mingit täisarvud,

404
00:35:12,570 --> 00:35:19,860
et siis ma oleks välja filtreerida kõik numbrid üle 30 aasta viimases ämber.

405
00:35:19,860 --> 00:35:26,660
Ja nii siis, et tulemuseks oleks selline tasakaalustamata hash tabelit.

406
00:35:31,330 --> 00:35:35,640
Korrata, hash tabel on lihtsalt massiivi ämbrid

407
00:35:35,640 --> 00:35:38,590
kus iga ämber on seotud nimekirja.

408
00:35:38,590 --> 00:35:43,730
Ja nii kindlaks teha, kus iga väärtus läheb, mis ämber see läheb,

409
00:35:43,730 --> 00:35:46,260
sa lähed tahan, mida nimetatakse räsifunktsiooniga

410
00:35:46,260 --> 00:35:55,010
mis võtab väärtuse ja siis ütleb, et see väärtus vastab teatud ämber.

411
00:35:55,010 --> 00:36:00,970
Nii et kuni eespool käesolevas Näiteks minu räsifunktsiooniga võttis iga väärtuse.

412
00:36:00,970 --> 00:36:03,020
See kontrollida, kas see oli vähem kui 10.

413
00:36:03,020 --> 00:36:05,360
Kui ta oli, see paneks see esimene ämber.

414
00:36:05,360 --> 00:36:08,910
Ta kontrollib, kas see on vähem kui 20, paneb see teise, kui tõsi,

415
00:36:08,910 --> 00:36:12,880
kontrolli, kui see on alla 30, siis paneb see kolmas kopp,

416
00:36:12,880 --> 00:36:16,990
ja siis kõik muu lihtsalt langeb neljandas ämber.

417
00:36:16,990 --> 00:36:20,110
Nii et kui teil on raha, oma räsifunktsiooniga

418
00:36:20,110 --> 00:36:25,420
asetab selle väärtuse sobivasse ämbrisse.

419
00:36:25,420 --> 00:36:32,430
Räsifunktsiooniga põhimõtteliselt peab teadma, kui palju kopad olete.

420
00:36:32,430 --> 00:36:37,960
Sinu hash tabelit suurus, arv kopad teil on,

421
00:36:37,960 --> 00:36:41,190
et see saab olema kindel arv, mis on sinust, teie otsustada,

422
00:36:41,190 --> 00:36:43,590
kuid see saab olema kindel arv.

423
00:36:43,590 --> 00:36:51,840
Nii et teie räsifunktsiooniga siis tuginedes, et teha kindlaks, millised ämber iga võti läheb

424
00:36:51,840 --> 00:36:54,450
nii, et see ühtlaselt laiali.

425
00:36:56,150 --> 00:37:03,820
Sarnaselt meie rakendamine seotud nimekirjades, nüüd iga sõlme hash tabelit

426
00:37:03,820 --> 00:37:07,000
tegelikult läheb on tüüpi char.

427
00:37:07,000 --> 00:37:14,340
Nii et meil on char massiiv nimega sõna ja siis teine ​​kursor järgmisele sõlme,

428
00:37:14,340 --> 00:37:19,010
mis mõtet, sest see saab olema seotud nimekirja.

429
00:37:19,010 --> 00:37:24,350
Mäletad, kui me olime seotud nimekirjades, tegin sõlme * nn peaga

430
00:37:24,350 --> 00:37:31,060
mis oli suunatud esimese sõlme seotud nimekirja.

431
00:37:31,060 --> 00:37:34,020
Aga meie hash tabelit, sest meil on mitu seotud nimekirju,

432
00:37:34,020 --> 00:37:37,520
me tahame me tahame, et meie hash tabelis olla nagu, "Mis on ämber?"

433
00:37:37,520 --> 00:37:43,340
Kopp on lihtsalt nimekiri sõlme suunanäitajaks,

434
00:37:43,340 --> 00:37:50,620
ja nii iga element ämber on tegelikult osutab sellele vastava seotud nimekirja.

435
00:37:56,180 --> 00:38:01,520
Tulles tagasi selle skemaatiline, näed, et ämbrid ise on nooled,

436
00:38:01,520 --> 00:38:06,980
mitte päris tippu.

437
00:38:11,680 --> 00:38:16,420
Üks oluline omadus hash funktsioonid on see, et nad on determineeritud.

438
00:38:16,420 --> 00:38:19,440
See tähendab, et kui sa räsi number 2,

439
00:38:19,440 --> 00:38:22,270
see peaks alati tagasi samasse ämbrisse.

440
00:38:22,270 --> 00:38:26,440
Iga üksik väärtus, mis läheb räsifunktsiooniga, kui korrata,

441
00:38:26,440 --> 00:38:29,690
on saada sama indeksit.

442
00:38:29,690 --> 00:38:34,210
Nii et teie räsifunktsiooniga tagastab indeks array

443
00:38:34,210 --> 00:38:38,530
kui see väärtus kuulub.

444
00:38:38,530 --> 00:38:41,790
Nagu ütlesin, mitmed ämbrid on fikseeritud,

445
00:38:41,790 --> 00:38:49,630
ja nii oma pealeht et naasete peab olema väiksem kui arv ämbrid

446
00:38:49,630 --> 00:38:52,680
kuid suurem kui 0.

447
00:38:52,680 --> 00:39:00,780
Põhjus, miks meil on hash funktsioonid, mitte ainult ühe seotud nimekirja

448
00:39:00,780 --> 00:39:09,290
või ühe massiivi on see, et me tahame, et oleks võimalik hüpata teatud osa kõige lihtsam

449
00:39:09,290 --> 00:39:11,720
kui me teame iseloomulik väärtus -

450
00:39:11,720 --> 00:39:14,760
selle asemel et otsida vajalikud kogu sõnaraamat,

451
00:39:14,760 --> 00:39:18,320
on võimalik hüpata teatud osa sellest.

452
00:39:19,880 --> 00:39:24,440
Sinu räsifunktsiooniga tuleks arvesse võtta, et ideaalis

453
00:39:24,440 --> 00:39:28,980
iga ämber on umbes sama palju võtmeid.

454
00:39:28,980 --> 00:39:35,040
Kuna hash tabelis on rida seotud nimekirju,

455
00:39:35,040 --> 00:39:38,480
siis seotud nimekirju ise ei kavatse olla rohkem kui üks sõlm.

456
00:39:38,480 --> 00:39:43,210
Eelmise näiteks kaks erinevat arvu, kuigi nad ei olnud võrdsed,

457
00:39:43,210 --> 00:39:46,950
kui räsitud, tagastab sama indeksit.

458
00:39:46,950 --> 00:39:53,620
Nii et kui teil on tegemist sõnadega, üks sõna, kui räsitud

459
00:39:53,620 --> 00:39:57,450
oleks sama räsi väärtus nagu teine ​​sõna.

460
00:39:57,450 --> 00:40:04,140
See, mida me kutsume kokkupõrge, kui meil on sõlm, et kui räsitud,

461
00:40:04,140 --> 00:40:09,610
seotud nimekirja sel kopp ei ole tühi.

462
00:40:09,610 --> 00:40:14,180
Tehnikat, mida me nimetame on lineaarne katsetamine,

463
00:40:14,180 --> 00:40:22,550
kus te lähete seotud nimekirja ja siis leida, kui soovite lisada, et sõlm

464
00:40:22,550 --> 00:40:25,520
sest sa oled kokkupõrget.

465
00:40:25,520 --> 00:40:28,070
Te näete, et seal võiks olla kompromiss siin, eks?

466
00:40:28,070 --> 00:40:33,760
Kui teil on väga väike hash tabelit, väga väike arv kopad,

467
00:40:33,760 --> 00:40:36,380
siis sa lähed on palju kokkupõrkeid.

468
00:40:36,380 --> 00:40:40,460
Aga siis, kui sa teed väga suur hash tabelit,

469
00:40:40,460 --> 00:40:44,110
sa oled ilmselt läheb vähendada kokkupõrkeid,

470
00:40:44,110 --> 00:40:47,170
kuid see saab olema väga suur andmestruktuur.

471
00:40:47,170 --> 00:40:49,310
Seal saab olema kompromisse sellega.

472
00:40:49,310 --> 00:40:51,310
Nii et kui sa üritad oma pset, proovige mängida

473
00:40:51,310 --> 00:40:54,210
vahel võibolla teha väiksemaid hash tabelit

474
00:40:54,210 --> 00:41:02,100
aga siis teades, et see vőtab natuke kauem läbida erinevad elemendid

475
00:41:02,100 --> 00:41:04,270
Nende lingitud nimekirjad.

476
00:41:04,270 --> 00:41:09,500
>> Mis koormus läheb selleks vaja on itereerima üle iga sõna sõnastikus.

477
00:41:09,500 --> 00:41:13,180
See möödub osuti sõnastikku fail.

478
00:41:13,180 --> 00:41:18,050
Nii et sa lähed ära Faili I / O funktsioone, mida õppinud pset4

479
00:41:18,050 --> 00:41:23,010
ja itereerima üle iga sõna sõnastikus.

480
00:41:23,010 --> 00:41:26,620
Tahad iga sõna sõnastikku saada uus sõlm,

481
00:41:26,620 --> 00:41:32,730
ja sa lähed panna iga üks neist sõlmed oma sõnaraamat andmestruktuur.

482
00:41:32,730 --> 00:41:36,560
Kui sa saad uue sõna, sa tead, et see saab muutuda sõlme.

483
00:41:36,560 --> 00:41:46,590
Nii et võite minna kohe ja malloc sõlme kursor iga uue sõna, mis teil on.

484
00:41:46,590 --> 00:41:52,610
Siin ma helistan minu sõlme osuti new_node ja ma mallocing mida? Suurust sõlme.

485
00:41:52,610 --> 00:41:59,190
Siis lugeda tegeliku stringi faili, sest sõnastik on tegelikult salvestatud

486
00:41:59,190 --> 00:42:03,340
poolt sõna ja siis uus rida, mida me saame ära

487
00:42:03,340 --> 00:42:06,520
on funktsioon fscanf,

488
00:42:06,520 --> 00:42:10,280
mille fail on sõnastiku faili, mida me möödunud aastal,

489
00:42:10,280 --> 00:42:18,900
nii see skaneerib faili stringi ja kohad, mis stringi viimane argument.

490
00:42:18,900 --> 00:42:26,890
Kui te mäletate tagasi üks loenguid, kui me läksime üle

491
00:42:26,890 --> 00:42:29,320
ja selline kooritud kihid tagasi CS50 raamatukogu,

492
00:42:29,320 --> 00:42:33,430
nägime rakendamise fscanf seal.

493
00:42:33,430 --> 00:42:37,700
Et minna tagasi fscanf, meil on fail, mida me lugemine,

494
00:42:37,700 --> 00:42:42,570
me otsime stringi et faili, ja siis me pannes see

495
00:42:42,570 --> 00:42:48,340
siin on mul new_node-> sõna, sest new_node on sõlm pointer,

496
00:42:48,340 --> 00:42:50,380
ei tegelikult sõlme.

497
00:42:50,380 --> 00:42:57,100
Nii siis ma räägin new_node, ma tahan minna sõlme, et see osutab

498
00:42:57,100 --> 00:43:01,190
ja siis määrata, et väärtust sõna.

499
00:43:01,190 --> 00:43:08,540
Soovime siis võta see sõna ja pistke see hash tabelit.

500
00:43:08,540 --> 00:43:13,750
Aru, et tegime new_node sõlme pointer

501
00:43:13,750 --> 00:43:18,230
sest me ei kavatse tahavad teada, mida aadressi, et sõlm on

502
00:43:18,230 --> 00:43:23,940
kui me aseta sest struktuuri sõlmede iseennast, struct,

503
00:43:23,940 --> 00:43:26,380
on see, et neil on kursor uus sõlm.

504
00:43:26,380 --> 00:43:30,820
Nii siis mida on aadress, et sõlme läheb osutada?

505
00:43:30,820 --> 00:43:34,550
See aadress saab olema new_node.

506
00:43:34,550 --> 00:43:42,140
Kas on mõtet, miks me teeme new_node sõlme * mitte sõlme?

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

508
00:43:45,700 --> 00:43:52,840
Meil on sõna. See väärtus on new_node-> sõna.

509
00:43:52,840 --> 00:43:55,970
See sisaldab sõna sõnaraamatust, et me tahame sisend.

510
00:43:55,970 --> 00:44:00,210
Nii et see, mida me tahame teha, on me tahame helistada meie hash funktsiooni, et string

511
00:44:00,210 --> 00:44:03,780
sest meie räsifunktsiooniga võtab on string ja tagastab meile täisarv,

512
00:44:03,780 --> 00:44:12,090
kui see täisarv on indeks, kus Hashtable sel indeks kajastab, et kopp.

513
00:44:12,090 --> 00:44:18,260
Me tahame võtta, et indeks ja seejärel minna, et indeks hash tabelit

514
00:44:18,260 --> 00:44:26,960
ja siis kasutada, et siduda nimekirja lisada sõlme new_node.

515
00:44:26,960 --> 00:44:31,950
Pea meeles, et aga te otsustate sisestada oma sõlme,

516
00:44:31,950 --> 00:44:34,370
kas see on keskel, kui soovite sortida

517
00:44:34,370 --> 00:44:39,650
või alguses või lõpus, veenduge, et teie viimane sõlm osutab alati on NULL

518
00:44:39,650 --> 00:44:46,730
sest see on ainus viis, et me teame, kus viimane element meie lingitud nimekiri on.

519
00:44:50,790 --> 00:44:59,710
>> Kui suurus on täisarv, mis tähistab arvu sõnu sõnastikku,

520
00:44:59,710 --> 00:45:03,060
siis üks viis seda teha on, et kui suurus nimetatakse

521
00:45:03,060 --> 00:45:05,840
me minna läbi iga element meie hash tabelit

522
00:45:05,840 --> 00:45:09,410
ja siis itereerima läbi iga seotud nimekirja jooksul hash tabelit

523
00:45:09,410 --> 00:45:13,770
ja siis arvutada pikkuse, et suurendada meie counter 1 1.

524
00:45:13,770 --> 00:45:16,580
Aga iga kord, suurus nimetatakse, et läheb võtab kaua aega

525
00:45:16,580 --> 00:45:22,120
sest me ei kavatse olla lineaarselt katsetamine iga seotud nimekirja.

526
00:45:22,120 --> 00:45:30,530
Selle asemel, et see saab olema palju lihtsam, kui sa jälgida, kui palju sõnu on möödas sisse

527
00:45:30,530 --> 00:45:36,330
Nii et siis, kui Te counter jooksul oma koormust funktsioon

528
00:45:36,330 --> 00:45:42,430
et uuendused nagu vaja, siis loendur, kui sa määrad selle globaalse muutuja,

529
00:45:42,430 --> 00:45:44,930
saab avada, kui suurus.

530
00:45:44,930 --> 00:45:51,450
Mida suurus võiks lihtsalt teha, on ühes reas, lihtsalt tagasi leti väärtus,

531
00:45:51,450 --> 00:45:55,500
suurust sõnastik, mis sa juba käsitletud koormus.

532
00:45:55,500 --> 00:46:05,190
Seda ma mõtlesin, kui ütlesin, kui sa ellu lasti kasulik viis,

533
00:46:05,190 --> 00:46:08,540
siis suurus saab olema üsna lihtne.

534
00:46:08,540 --> 00:46:11,350
>> Nii et nüüd saame kontrollida.

535
00:46:11,350 --> 00:46:15,960
Nüüd me tegeleme sõnu sisend tekstifail,

536
00:46:15,960 --> 00:46:19,910
ja nii me lähme kontrollima, kas kõik need sisend sõnad

537
00:46:19,910 --> 00:46:22,520
on tegelikult sõnastikus või mitte.

538
00:46:22,520 --> 00:46:26,520
Sarnaselt rüselus, me tahame võimaldada juhul tundetus.

539
00:46:26,520 --> 00:46:32,110
Sa tahad teha kindel, et kõik sõnad vastu võetud, kuigi nad on segatud juhul

540
00:46:32,110 --> 00:46:37,840
kui kutsutakse nööriga Võrdle, on samaväärsed.

541
00:46:37,840 --> 00:46:42,450
Sõnade sõnastik Tekstifailid on tegelikult kõik väiketähed.

542
00:46:42,450 --> 00:46:49,280
Teine asi on see, et võite eeldada, et iga sõna vastu võetud, iga stringi,

543
00:46:49,280 --> 00:46:53,200
saab olema kas tähestikulises järjekorras või sisaldada ülakomad.

544
00:46:53,200 --> 00:46:58,010
Ülakomasid hakkavad kehtima sõnad meie sõnaraamatus.

545
00:46:58,010 --> 00:47:06,470
Nii et kui teil on sõna ülakoma S, see on tegelik õigustatud sõna oma sõnaraamat

546
00:47:06,470 --> 00:47:11,650
et see saab olema üks tippe oma hash tabelit.

547
00:47:13,470 --> 00:47:18,350
Kontrollige töötab, kui sõna on olemas, siis see ju olema meie hash tabelit.

548
00:47:18,350 --> 00:47:22,210
Kui sõna on sõnastikus olemas, siis on kõik sõnad sõnastikus on hash tabelit,

549
00:47:22,210 --> 00:47:26,560
seega vaatame seda sõna hash tabelit.

550
00:47:26,560 --> 00:47:29,250
Me teame, et kuna me ellu meie räsifunktsiooniga

551
00:47:29,250 --> 00:47:38,420
nii et iga unikaalne sõna on alati räsitud sama väärtus,

552
00:47:38,420 --> 00:47:43,340
siis me teame, et selle asemel, et otsida läbi kogu meie kogu hash tabelit,

553
00:47:43,340 --> 00:47:48,310
saame tegelikult leida seotud nimekirja, et see sõna peaks kuuluma.

554
00:47:48,310 --> 00:47:51,850
Kui see oleks sõnastikus, siis oleks selles ämber.

555
00:47:51,850 --> 00:47:57,140
Mida me saame teha, kui sõna on nimi meie string möödunud aastal,

556
00:47:57,140 --> 00:48:01,560
me võime lihtsalt räsi seda sõna ja pilk seotud nimekirja

557
00:48:01,560 --> 00:48:06,410
väärtuse juures Hashtable [räsi (sõna)].

558
00:48:06,410 --> 00:48:12,410
Sealt me ​​teha saame, on meil väiksem alagrupis sõlmede otsida sõna,

559
00:48:12,410 --> 00:48:16,770
ja nii saame läbida seotud nimekirja, kasutades näiteks varem ülevaadet,

560
00:48:16,770 --> 00:48:24,110
ja siis nimetame jada võrrelda peale sõna kus kursor on suunaga,

561
00:48:24,110 --> 00:48:28,430
et sõna ja vaata, kas need võrrelda.

562
00:48:30,280 --> 00:48:35,110
Sõltuvalt nii, et teil korraldada oma räsifunktsiooniga,

563
00:48:35,110 --> 00:48:39,260
kui see on järjestatud, siis võite olla võimeline tagasi false veidi varem,

564
00:48:39,260 --> 00:48:43,440
aga kui see on sorteerimata, siis soovite jätkata liiklevad läbi oma seotud nimekirja

565
00:48:43,440 --> 00:48:46,480
kuni leiad viimane element nimekirja.

566
00:48:46,480 --> 00:48:53,320
Ja kui sa ei ole veel leidnud sõna selleks ajaks olete jõudnud seotud nimekirja,

567
00:48:53,320 --> 00:48:56,890
see tähendab, et teie sõna ei leidu,

568
00:48:56,890 --> 00:48:59,410
ja nii, et sõna on vale,

569
00:48:59,410 --> 00:49:02,730
ja kontroll peaks tagasi false.

570
00:49:02,730 --> 00:49:09,530
>> Nüüd aga maha laadida, kuhu me tahame vabastada kõik sõlmed, et oleme malloc'd,

571
00:49:09,530 --> 00:49:14,050
nii tasuta kõik sõlmed meie hash tabelit.

572
00:49:14,050 --> 00:49:20,270
Me läheme taha itereerime kõik seotud nimekirju ja vaba kõik sõlmed, et.

573
00:49:20,270 --> 00:49:29,350
Kui vaadata eespool liikudes, et näiteks kui me vabastama seotud nimekirja,

574
00:49:29,350 --> 00:49:35,140
siis tahad korrata seda protsessi iga element hash tabelit.

575
00:49:35,140 --> 00:49:37,780
Ja ma lähen üle käesoleva aasta lõpus ülevaadet,

576
00:49:37,780 --> 00:49:46,600
kuid Valgrind on vahend, kus saab näha, kui olete korralikult vabanenud

577
00:49:46,600 --> 00:49:53,600
iga sõlme, et olete malloc'd või midagi muud, et olete malloc'd, muu pointer.

578
00:49:55,140 --> 00:50:00,530
Nii et hash tabeleid, kus meil on hulga kopad

579
00:50:00,530 --> 00:50:09,220
ja räsifunktsiooniga mis võtab väärtuse ja seejärel määrata, et raha teatud ämber.

580
00:50:09,220 --> 00:50:13,340
>> Nüüd aga üritab.

581
00:50:13,340 --> 00:50:18,750
Proovib selline välimus meeldib see, ja ma ka venitama näiteks.

582
00:50:18,750 --> 00:50:25,630
Põhimõtteliselt sul on terve rida võimalikke tähti,

583
00:50:25,630 --> 00:50:29,210
ja siis kui sa ehitamisel sõna,

584
00:50:29,210 --> 00:50:36,490
et kirja võib olla seotud jaoks sõnastiku mitmeid võimalusi.

585
00:50:36,490 --> 00:50:40,840
Mõned sõnad algavad C, kuid seejärel jätkata,

586
00:50:40,840 --> 00:50:42,960
aga teised jätkata O, näiteks.

587
00:50:42,960 --> 00:50:51,090
Trie on viis visualiseerimise kõik võimalikud kombinatsioonid need sõnad.

588
00:50:51,090 --> 00:50:59,070
Trie läheb jälgida rea ​​tähti, mis moodustavad sõna,

589
00:50:59,070 --> 00:51:08,280
hargnevat kui vaja, kui üks täht võib järgneda mitu kirja,

590
00:51:08,280 --> 00:51:16,630
ja lõpus tähistavad igas punktis kas see sõna on kehtiv või mitte

591
00:51:16,630 --> 00:51:30,120
sest kui sa õigekirja sõna MAT, MA Ma ei usu, on kehtiv sõna, kuid MAT on.

592
00:51:30,120 --> 00:51:37,820
Ja nii oma trie, see näitab, et pärast MAT, mis on tegelikult kehtiv sõna.

593
00:51:41,790 --> 00:51:48,590
Iga sõlme meie trie tegelikult toimub sisaldavad hulgaliselt sõlme suunanäitajaks,

594
00:51:48,590 --> 00:51:52,970
ja me lähed on konkreetselt 27 neist sõlme suunanäitajaks,

595
00:51:52,970 --> 00:52:00,550
üks iga tähestiku tähe samuti ülakoma iseloomu.

596
00:52:00,550 --> 00:52:10,450
Iga element selles massiivis on ise saab juhtida teise sõlme.

597
00:52:10,450 --> 00:52:14,020
Nii et kui see sõlm on NULL, kui seal on midagi pärast seda,

598
00:52:14,020 --> 00:52:20,550
siis me teame, et seal ei ole veel tähti selles fraasi.

599
00:52:20,550 --> 00:52:26,950
Aga kui see sõlm ei ole null, mis tähendab, et seal on rohkem tähti, et tähekombinatsiooni.

600
00:52:26,950 --> 00:52:32,160
Ja siis lisaks iga sõlm näitab, kas see on viimane märk, sõna või mitte.

601
00:52:38,110 --> 00:52:43,170
>> Läheme näide trie.

602
00:52:50,500 --> 00:52:58,340
Esiteks on mul toas 27 tippe selle massiivi.

603
00:52:58,340 --> 00:53:03,200
Kui mul on sõna BAR -

604
00:53:13,310 --> 00:53:15,370
Kui mul on sõna baari ja ma tahan lisada, et,

605
00:53:15,370 --> 00:53:22,700
esimene täht on B, nii et kui minu trie on tühi,

606
00:53:22,700 --> 00:53:29,910
B on teine ​​täht, nii et ma lähen valima panna see siin selles indeksis.

607
00:53:29,910 --> 00:53:33,450
Ma lähen on B siin.

608
00:53:33,450 --> 00:53:42,400
B saab olema sõlm, mis viitab teise massiivi kõik võimalikud märgid

609
00:53:42,400 --> 00:53:45,870
et saab jälgida pärast kirja B.

610
00:53:45,870 --> 00:53:57,610
Sel juhul ma tegelen sõna BAR, nii läheb siin.

611
00:54:02,000 --> 00:54:08,990
Pärast Mul on R-täht, nii siis nüüd juhib oma kombinatsioon,

612
00:54:08,990 --> 00:54:15,120
ja siis R on siin.

613
00:54:15,120 --> 00:54:22,470
BAR on täielik sõna, et siis ma lähen on R punktist teise sõlme

614
00:54:22,470 --> 00:54:33,990
mis ütleb, et see sõna on kehtiv.

615
00:54:36,010 --> 00:54:40,970
See sõlm on ka plaanis teha mitmeid erinevaid sõlmi,

616
00:54:40,970 --> 00:54:45,260
kuid need võivad olla NULL.

617
00:54:45,260 --> 00:54:49,080
Aga põhimõtteliselt saab jätkata niimoodi.

618
00:54:49,080 --> 00:54:54,250
See muutub natuke selgem, kui me läheme eri Näiteks

619
00:54:54,250 --> 00:54:56,780
nii lihtsalt karu mind sinna.

620
00:54:56,780 --> 00:55:02,050
Nüüd on meil baari sees meie sõnastikku.

621
00:55:02,050 --> 00:55:05,980
Nüüd ütleme, et meil sõna BAZ.

622
00:55:05,980 --> 00:55:12,630
Alustame B, ja meil on juba B üheks tähed, mis on meie sõnastikku.

623
00:55:12,630 --> 00:55:15,170
See on jälginud A. Meil ​​on juba.

624
00:55:15,170 --> 00:55:19,250
Aga siis selle asemel on meil Z järgmised.

625
00:55:19,250 --> 00:55:25,490
Nii siis osa meie massiivi saab olema Z

626
00:55:25,490 --> 00:55:30,810
ja nii siis, et keegi ei kavatse juhtida teise kehtiva sõna lõppu.

627
00:55:30,810 --> 00:55:36,930
Nii näeme, et kui me jätkame läbi B ja siis,

628
00:55:36,930 --> 00:55:43,480
seal on kaks erinevat võimalust praegu meie sõnastikust sõnu, mis algavad B ja A.

629
00:55:49,650 --> 00:55:57,460
Ütle tahtsime lisada sõna jura.

630
00:55:57,460 --> 00:56:05,620
Siis me oleks sisenemise F.

631
00:56:05,620 --> 00:56:11,320
F on sõlm, mis osutab terve rida.

632
00:56:11,320 --> 00:56:22,790
Soovime leida O, minge O, O siis lingid kogu nimekiri.

633
00:56:22,790 --> 00:56:35,340
Oleksime B ja seejärel jätkake, me tahaks olla ja siis R.

634
00:56:35,340 --> 00:56:43,570
Nii siis foobar läbib kogu tee alla kuni jura on õige sõna.

635
00:56:43,570 --> 00:56:52,590
Ja nii siis see oleks kehtiv sõna.

636
00:56:52,590 --> 00:57:00,170
Nüüd ütlevad meie järgmise sõna sõnastikus on tegelikult sõna foo.

637
00:57:00,170 --> 00:57:03,530
Meil oleks öelda F. Mis järeldub F?

638
00:57:03,530 --> 00:57:06,190
Ma tegelikult juba ruumi O, nii et ma lähen jätkata.

639
00:57:06,190 --> 00:57:09,150
Ma ei pea tegema uue. Jätka.

640
00:57:09,150 --> 00:57:15,500
SUVA on kehtiv sõna selles sõnastik, et siis ma lähen näitama

641
00:57:15,500 --> 00:57:21,660
et see on kehtiv.

642
00:57:21,660 --> 00:57:28,370
Kui ma saan oma järjestuse seal, et oleks õige.

643
00:57:28,370 --> 00:57:33,050
Aga kui me jätkame meie järjestus SUVA alla B

644
00:57:33,050 --> 00:57:39,750
ja lihtsalt pidin FOOB, FOOB ei ole sõna, ja see pole märgitud selle kehtivuse.

645
00:57:47,370 --> 00:57:57,600
Aastal trie, olete iga sõlm näitab, kas tegemist on kehtiv sõna või mitte,

646
00:57:57,600 --> 00:58:05,840
ja siis iga sõlm on ka massiivi 27. sõlme viiteid

647
00:58:05,840 --> 00:58:09,520
et siis käsk sõlmed ise.

648
00:58:09,520 --> 00:58:12,940
>> Siin on viis, kuidas te võiksite määrata see.

649
00:58:12,940 --> 00:58:17,260
Kuid just nagu hash tabelit Näiteks kui meil oli sõlme * pea

650
00:58:17,260 --> 00:58:21,320
näidata algusest meie seotud nimekirja, me ka kavatse tahavad

651
00:58:21,320 --> 00:58:29,150
kuidagi võimalik teada, kus alguses meie trie on.

652
00:58:29,150 --> 00:58:34,110
Mõned inimesed kutsuvad üritab puud, ja see on kui juur pärineb.

653
00:58:34,110 --> 00:58:36,910
Nii et me tahame just meie puu veenduda, et me jääme maandatud

654
00:58:36,910 --> 00:58:39,570
sinna, kus meie trie on.

655
00:58:42,910 --> 00:58:46,300
Meil on juba selline läks üle

656
00:58:46,300 --> 00:58:50,240
kuidas sa võiksid mõelda laadimist iga sõna sõnastikku.

657
00:58:50,240 --> 00:58:54,540
Sisuliselt iga sõna sa lähed tahan kinnitada, läbi oma trie

658
00:58:54,540 --> 00:58:59,590
ja teades, et iga element lapsed - me kutsusime seda last sel juhul -

659
00:58:59,590 --> 00:59:04,290
vastab erinev täht, sa lähed tahan vaadata neid väärtusi

660
00:59:04,290 --> 00:59:08,320
selle konkreetse indeks, mis vastab kirjale.

661
00:59:08,320 --> 00:59:11,260
Nii mõtlesin kogu tee tagasi Caesar ja Vigenere,

662
00:59:11,260 --> 00:59:16,070
teades, et iga täht saad mingi kaardi tagasi tähestikregistris,

663
00:59:16,070 --> 00:59:20,690
kindlasti läbi Z saab olema üsna lihtne map üles tähestikulises kirja,

664
00:59:20,690 --> 00:59:25,200
kuid kahjuks ülakomad on ka tunnustatud tegelane sõnu.

665
00:59:25,200 --> 00:59:31,650
Ma pole isegi kindel, mida ASCII väärtus on

666
00:59:31,650 --> 00:59:39,250
Nii et kui sa tahad leida indeks otsustada, kas sa tahad seda olla esimene

667
00:59:39,250 --> 00:59:44,550
või viimane, sa pead tegema kõva kodeeritud tšeki, et

668
00:59:44,550 --> 00:59:48,930
ja seejärel panna, et indeks 26, näiteks.

669
00:59:48,930 --> 00:59:55,300
Siis te ei kontrolliks raha lastele [i]

670
00:59:55,300 --> 00:59:58,400
kus [i] vastab ükskõik kirja sa oled.

671
00:59:58,400 --> 01:00:04,110
Kui see on NULL, mis tähendab, et ei ole praegu võimaliku tähed

672
01:00:04,110 --> 01:00:08,150
mis selles järjekorras, nii et sa lähed tahan malloc

673
01:00:08,150 --> 01:00:13,150
ja teha uue sõlme ja on, et lapsed [i], et see

674
01:00:13,150 --> 01:00:17,890
nii et loote - kui me sisestatud kirja arvesse ristküliku -

675
01:00:17,890 --> 01:00:23,680
tegemisel laste mitte-null ja punkt arvesse, et uus sõlm.

676
01:00:23,680 --> 01:00:28,340
Aga kui see ei ole null, nagu meie näiteks Foo

677
01:00:28,340 --> 01:00:34,570
kui me juba jura, me jätkame,

678
01:00:34,570 --> 01:00:44,010
ja me ei ole kunagi teha uus sõlm, vaid lihtsalt millega is_word tõeseks

679
01:00:44,010 --> 01:00:47,790
aasta lõpus, et sõna.

680
01:00:50,060 --> 01:00:55,340
>> Siis kui enne, sest siin olete tegelevad iga täht korraga,

681
01:00:55,340 --> 01:01:01,470
see saab olema lihtsam suuruse, selle asemel, et arvutada

682
01:01:01,470 --> 01:01:06,910
ja minna kogu puu ja arvutada, kui palju lapsi on mul

683
01:01:06,910 --> 01:01:10,850
ja siis hargnevat, meenutades, kui palju on vasakul ja paremal küljel

684
01:01:10,850 --> 01:01:12,850
ja asjad niimoodi, et see saab olema palju lihtsam

685
01:01:12,850 --> 01:01:16,220
kui sa lihtsalt jälgida, kui palju sõnu sa lisades

686
01:01:16,220 --> 01:01:18,080
kui olete tegelevad koormus.

687
01:01:18,080 --> 01:01:22,630
Ja nii siis nii suurust saab lihtsalt tagasi globaalse muutuja suurus.

688
01:01:25,320 --> 01:01:28,530
>> Nüüd aga kontrollida.

689
01:01:28,530 --> 01:01:33,920
Samadele standarditele nagu enne, kui me tahame võimaldada juhul tundetus.

690
01:01:33,920 --> 01:01:40,400
Samuti eeldame, et stringid on ainult tähti või ülakomade

691
01:01:40,400 --> 01:01:44,000
sest lapsed on massiiv 27. pikk,

692
01:01:44,000 --> 01:01:48,480
nii et kõik tähestiku tähti pluss ülakoma.

693
01:01:48,480 --> 01:01:53,800
Sest kontrollida, mida sa teha tahad on, mida sa tahad alustada root

694
01:01:53,800 --> 01:01:58,440
sest juur toob välja massiivi, mis sisaldab

695
01:01:58,440 --> 01:02:01,630
kõik võimaliku alustades kirjas sõna.

696
01:02:01,630 --> 01:02:03,680
Sa lähed, et alustada seal,

697
01:02:03,680 --> 01:02:11,590
ja siis sa lähed, et kontrollida kas see väärtus NULL või mitte,

698
01:02:11,590 --> 01:02:16,490
sest kui väärtus on NULL, mis tähendab, et sõnastikku ei ole mingit väärtust

699
01:02:16,490 --> 01:02:21,480
mis sisaldavad selle kirja, et kindlas järjekorras.

700
01:02:21,480 --> 01:02:24,970
Kui see on NULL, siis see tähendab, et sõna valesti kohe.

701
01:02:24,970 --> 01:02:27,110
Aga kui see ei ole null, siis võite jätkata,

702
01:02:27,110 --> 01:02:34,090
öelda, et esimene täht on võimalik esimese tähe sõna,

703
01:02:34,090 --> 01:02:40,630
nii nüüd ma tahan vaadata, kas teine ​​kiri, et jada, jääb minu sõnaraamat.

704
01:02:40,630 --> 01:02:46,540
Nii et sa lähed minema indeks laste esimese sõlme

705
01:02:46,540 --> 01:02:50,720
ja kontrollima, kas see teine ​​täht on olemas.

706
01:02:50,720 --> 01:02:57,440
Siis korrake seda protsessi kontrollida, kas seda jada on kehtiv või mitte

707
01:02:57,440 --> 01:02:59,060
jooksul oma trie.

708
01:02:59,060 --> 01:03:06,430
Kui sõlm lapsi, et indeks viitab null,

709
01:03:06,430 --> 01:03:10,710
sa tead, et see jada ei ole olemas,

710
01:03:10,710 --> 01:03:16,230
aga siis kui jõuad lõpuks sõna, et olete sisestanud,

711
01:03:16,230 --> 01:03:20,070
siis sa tahad vaadata nüüd, et ma olen lõpetanud selle jada

712
01:03:20,070 --> 01:03:27,610
ja leidis selle sees minu trie, on see, et sõna kehtib või mitte?

713
01:03:27,610 --> 01:03:32,480
Ja nii siis sa tahad, et kontrollida, ja just siis, kui olete leidnud, et jada

714
01:03:32,480 --> 01:03:35,120
siis sa tahad, et kontrollida, kas see sõna on kehtiv või mitte

715
01:03:35,120 --> 01:03:40,290
sest mäletan tagasi eelmisel korral, et ma joonistasin, kus meil oli FOOB,

716
01:03:40,290 --> 01:03:48,410
mis oli kehtiv jada, mis me leidsime, kuid ei olnud tegelikult kehtiv sõna ise.

717
01:03:50,570 --> 01:03:59,000
>> Samamoodi lossimisõigusest üritab soovite maha kõik sõlmed oma trie.

718
01:03:59,000 --> 01:04:04,790
Vabandust. Sarnaselt hash tabeleid, kus lossimiseks me vabastas kõik sõlmed,

719
01:04:04,790 --> 01:04:09,740
aastal üritab tahame ka tasuta kõik sõlmed.

720
01:04:09,740 --> 01:04:15,000
Unload tegelikult töötavad lihtsaim alt üles

721
01:04:15,000 --> 01:04:19,290
sest need on peamiselt seotud nimekirju.

722
01:04:19,290 --> 01:04:22,540
Nii et me tahame veenduda, et me kinni hoida kõiki väärtusi

723
01:04:22,540 --> 01:04:25,700
ja tasuta neid kõiki otseselt.

724
01:04:25,700 --> 01:04:28,840
Mis sa lähed tahan teha, kui te töötate trie

725
01:04:28,840 --> 01:04:35,640
on sõita alt ja vaba madalaima võimaliku sõlme 1.

726
01:04:35,640 --> 01:04:39,190
ja siis minna kuni kõik need lapsed ja siis vaba kõigile neile,

727
01:04:39,190 --> 01:04:43,050
tõusevad ja siis vaba jne

728
01:04:43,050 --> 01:04:48,790
Kind of like tegelevad alumine kiht trie 1.

729
01:04:48,790 --> 01:04:51,940
ja siis läksime üles, kui olete vabanenud kõike.

730
01:04:51,940 --> 01:04:56,720
See on hea näide sellest, kus rekursiivne funktsioon võib tulla käepärane.

731
01:04:56,720 --> 01:05:03,830
Kui olete vabanenud alumine kiht oma trie,

732
01:05:03,830 --> 01:05:08,000
siis helistada lossima kohta ülejäänud seda,

733
01:05:08,000 --> 01:05:13,620
veenduge, et teil vabastada iga mini -

734
01:05:13,620 --> 01:05:16,410
Võite liiki visualiseerida seda mini proovib.

735
01:05:23,300 --> 01:05:28,990
Nii et teil on oma juur siin.

736
01:05:30,840 --> 01:05:35,230
Ma lihtsalt lihtsustada see, et ma ei pea koostama 26 neist.

737
01:05:37,250 --> 01:05:43,770
Nii et teil on need, ja siis need esindavad järjestused sõnad

738
01:05:43,770 --> 01:05:54,620
kus kõik need väikesed ringid on kirjad, mis kehtivad tähejadad.

739
01:06:03,040 --> 01:06:07,160
Jätkame lihtsalt natuke rohkem.

740
01:06:15,110 --> 01:06:25,750
Mis sa lähed teha tahad on tasuta alt siin ja siis tasuta see üks

741
01:06:25,750 --> 01:06:31,640
ja siis tasuta see üks allosas, enne kui vaba üks ülemine siin

742
01:06:31,640 --> 01:06:38,180
sest kui sa tasuta midagi teine ​​tase siin,

743
01:06:38,180 --> 01:06:47,230
siis tegelikult kaotaks see väärtus siin.

744
01:06:47,230 --> 01:06:54,780
Sellepärast on oluline ka maha laadima jaoks trie veenduda, et sa vaba alt esimene.

745
01:06:54,780 --> 01:06:59,480
Mida sa tahad teha, on öelda iga sõlme

746
01:06:59,480 --> 01:07:06,430
Ma tahan maha laadida kõik lapsed.

747
01:07:16,060 --> 01:07:22,140
>> Nüüd, kui oleme läinud üle lossimiseks jaoks hash tabelit meetod samuti trie meetod,

748
01:07:22,140 --> 01:07:27,020
me ei kavatse soovite vaadata Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind sa joosta järgmised käsud.

750
01:07:29,640 --> 01:07:32,700
Sul on valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Sa kontrollimine kõik lekked, kui sa jooksed speller antud selle teatud teksti

752
01:07:40,960 --> 01:07:46,980
sest speller peab võtma tekstifaili.

753
01:07:46,980 --> 01:07:52,330
Nii Valgrind kestab oma programmi, ütleb teile, mitu baiti te eraldatud,

754
01:07:52,330 --> 01:07:57,150
kui palju baite olete vabanenud, ja ta ütleb teile, kas te vabanenud lihtsalt piisavalt

755
01:07:57,150 --> 01:07:58,930
või kas sa ei tasuta piisa,

756
01:07:58,930 --> 01:08:02,850
või mõnikord saab isegi üle-vaba, nagu näiteks tasuta sõlme, mis on juba vabastatud

757
01:08:02,850 --> 01:08:05,140
ja nii ta naaseb sa vead.

758
01:08:05,140 --> 01:08:11,600
Kui te kasutate Valgrind, siis annan teile mõned teated

759
01:08:11,600 --> 01:08:15,970
näitab, kas olete vabanenud kas alla piisavalt, lihtsalt piisavalt,

760
01:08:15,970 --> 01:08:19,609
või rohkem kui piisavalt korda.

761
01:08:24,370 --> 01:08:30,410
>> Osa sellest pset, see on vabatahtlik vaidlustada Big juhatus.

762
01:08:30,410 --> 01:08:35,790
Aga kui me tegeleme nende andmete struktuurid

763
01:08:35,790 --> 01:08:40,689
see on selline tore näha, kui kiiresti ja kuidas tõhus oma andmestruktuurid võiks olla.

764
01:08:40,689 --> 01:08:44,490
Kas teie räsifunktsiooniga tulemus palju kokkupõrkeid?

765
01:08:44,490 --> 01:08:46,300
Või on teie andmete suurus tõesti suur?

766
01:08:46,300 --> 01:08:49,420
Kas see võtab palju aega, et läbida?

767
01:08:49,420 --> 01:08:54,800
Aastal logi speller, see väljundid, kui palju aega te kasutate laadida,

768
01:08:54,800 --> 01:08:57,700
et kontrollida, teostada suurus ja maha laadida,

769
01:08:57,700 --> 01:09:00,720
ja nii need on postitatud Big Board,

770
01:09:00,720 --> 01:09:03,600
kus saab võistelda oma klassikaaslastega

771
01:09:03,600 --> 01:09:11,350
ja mõned töötajad, et näha, kes on kõige kiiremini õigekirja kontrollija.

772
01:09:11,350 --> 01:09:14,760
Üks asi, mida ma tahaksin märkida, umbes hash tabeleid

773
01:09:14,760 --> 01:09:20,470
on see, et seal on päris lihtne hash funktsioonid, et me võiksime mõelda.

774
01:09:20,470 --> 01:09:27,240
Näiteks, teil on 26 kopad, ja nii iga ämber

775
01:09:27,240 --> 01:09:30,200
vastab esimene täht sõna,

776
01:09:30,200 --> 01:09:35,229
aga see läheb kaasa päris tasakaalustamata hash tabelit

777
01:09:35,229 --> 01:09:40,979
sest seal on palju vähem sõnu, mis algavad X kui algab M näiteks.

778
01:09:40,979 --> 01:09:47,890
Üks võimalus edasi minna speller on, kui soovite saada kõik muud funktsioonid alla

779
01:09:47,890 --> 01:09:53,240
siis lihtsalt kasutada lihtsaid räsifunktsiooniga oleks võimalik saada oma koodi töötab

780
01:09:53,240 --> 01:09:58,650
ja siis tagasi minna ja muuta suurust oma hash tabelit ja määratlus.

781
01:09:58,650 --> 01:10:03,430
Seal on palju ressursse Internetis hash funktsioonid,

782
01:10:03,430 --> 01:10:08,250
ja nii selle pset teil on lubatud uurida hash funktsioonid Internetis

783
01:10:08,250 --> 01:10:15,560
mõned vihjed ja inspiratsiooni nii kaua, kui te veenduge, et tuua kus sul seda.

784
01:10:15,560 --> 01:10:22,060
Sa oled teretulnud vaatama ja tõlgendama mõned räsifunktsiooniga et sa leiad internetist.

785
01:10:22,060 --> 01:10:27,460
Tagasi, et sa võiksid näha, kui keegi kasutada trie

786
01:10:27,460 --> 01:10:31,700
kas nende rakendamine on kiirem kui teie hash tabelit või mitte.

787
01:10:31,700 --> 01:10:35,290
Võite esitada Big Board mitu korda.

788
01:10:35,290 --> 01:10:37,660
See salvestab oma viimases sissekandes.

789
01:10:37,660 --> 01:10:44,300
Nii et äkki sa muudad oma räsifunktsiooniga ja siis mõistad, et see on tegelikult palju kiiremini

790
01:10:44,300 --> 01:10:46,780
või palju aeglasem kui enne.

791
01:10:46,780 --> 01:10:50,960
See on natuke lõbusalt.

792
01:10:50,960 --> 01:10:57,190
Seal on alati 1 või 2 töötajat, kes püüavad panna aeglaseim võimalik sõnastikku

793
01:10:57,190 --> 01:11:00,210
nii et on alati lõbus vaadata.

794
01:11:00,210 --> 01:11:07,630
>> Kasutamine pset on teil tekib speller koos vabatahtlik sõnaraamat

795
01:11:07,630 --> 01:11:12,840
ja siis kohustuslik tekstifaili.

796
01:11:12,840 --> 01:11:18,380
Vaikimisi, kui sa jooksed speller vaid tekstifaili ja ei täpsusta sõnastik

797
01:11:18,380 --> 01:11:24,410
see saab kasutada sõnastikku tekstifail, suur üks

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

799
01:11:27,920 --> 01:11:32,760
Et üks on üle 100.000 sõnad.

800
01:11:32,760 --> 01:11:37,950
Neil on ka väike sõnastik, mis on tunduvalt vähem sõnu

801
01:11:37,950 --> 01:11:40,730
et CS50 on teinud teile.

802
01:11:40,730 --> 01:11:44,050
Siiski saab väga lihtsalt lihtsalt teeb oma sõnaraamat

803
01:11:44,050 --> 01:11:47,150
kui tahad lihtsalt töötavad väikest näidet -

804
01:11:47,150 --> 01:11:51,140
Näiteks kui soovite kasutada gdb ja sa tead, konkreetsed väärtused

805
01:11:51,140 --> 01:11:53,560
et sa tahad oma hash tabelit kaardistada välja.

806
01:11:53,560 --> 01:12:00,430
Nii saate lihtsalt teha oma teksti faili lihtsalt baariga, BAZ, Foo ja jura,

807
01:12:00,430 --> 01:12:04,860
teha, et tekstifail, eraldage need igaüks 1 rida,

808
01:12:04,860 --> 01:12:12,670
ja siis teha oma tekstifail, sõna otseses mõttes sisaldab ainult võibolla 1 või 2 sõna

809
01:12:12,670 --> 01:12:15,950
nii et sa tead täpselt, mida väljund peaks olema.

810
01:12:15,950 --> 01:12:21,870
Mõned proovi tekstifailid, mis Big Board suorittaessasi väljakutse vaadata

811
01:12:21,870 --> 01:12:25,580
on Sõda ja rahu ja Jane Austeni romaan või midagi sellist.

812
01:12:25,580 --> 01:12:30,450
Nii et kui sa oled hakanud läbi, see on palju lihtsam teha oma tekstifaile

813
01:12:30,450 --> 01:12:34,160
mis sisaldavad ainult paar sõna või võibolla 10

814
01:12:34,160 --> 01:12:38,280
nii et võite aimata, millist tulemus peaks olema

815
01:12:38,280 --> 01:12:42,880
ja siis vaadata seda vastu, et nii mitu kontrollitud näide.

816
01:12:42,880 --> 01:12:45,820
Ja nii kuna me tegeleme ennustavad ja joonistus asju ümber,

817
01:12:45,820 --> 01:12:48,690
jälle ma tahan teid julgustada kasutama pliiatsi ja paberi

818
01:12:48,690 --> 01:12:50,700
sest see on tõesti aitab teil selle ühe -

819
01:12:50,700 --> 01:12:55,620
juhtides nooled, kuidas hash tabelit või kuidas teie trie välja,

820
01:12:55,620 --> 01:12:57,980
kui sa vabastades midagi kus nooled lähevad,

821
01:12:57,980 --> 01:13:01,730
sa hoiad piisavalt, sa näed kõik seosed kaovad

822
01:13:01,730 --> 01:13:05,750
ja langevad kuristikku lekkinud mälu.

823
01:13:05,750 --> 01:13:11,070
Nii et palun, palun proovige juhtida asju isegi enne saate kirjutada koodi alla.

824
01:13:11,070 --> 01:13:14,520
Joonista asju teha nii, et saate aru, kuidas asjad lähevad tööle

825
01:13:14,520 --> 01:13:22,750
sest siis ma garanteerin, sa joosta vähem osuti muddles seal.

826
01:13:24,270 --> 01:13:25,910
>> Hea küll.

827
01:13:25,910 --> 01:13:28,780
Ma tahan soovida teile väga palju õnne, see pset.

828
01:13:28,780 --> 01:13:31,980
See on ilmselt kõige raskema tee.

829
01:13:31,980 --> 01:13:40,360
Nii et proovida alustada varakult, joonistada asju teha, joonistada asju teha, ja õnne.

830
01:13:40,360 --> 01:13:42,980
See oli kiirtutvustus 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]