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

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

3
00:00:04,870 --> 00:00:07,190
[Detta är CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Okej. Hej, alla, och välkomna till Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 är felstavningar, där vi kommer att göra en stavningskontroll.

6
00:00:17,400 --> 00:00:21,030
Spell-pjäser är oerhört viktigt.

7
00:00:21,030 --> 00:00:23,390
Har detta någonsin hänt dig?

8
00:00:23,390 --> 00:00:27,170
Du arbetar mycket, mycket hamstra på ett papper för en sammandrabbning

9
00:00:27,170 --> 00:00:33,120
och sedan ändå i slutändan får en mycket glöd Rade som en D-eller D =

10
00:00:33,120 --> 00:00:39,390
och allt eftersom du är den leverkorv spoiler i valen breda ordet.

11
00:00:39,390 --> 00:00:44,710
Ja, korrekturläsning dina paprika är en fråga av den största impotens.

12
00:00:44,710 --> 00:00:49,140
Detta är ett problem som drabbar manliga, manliga studenter.

13
00:00:49,140 --> 00:00:56,260
Jag var en gång höra av min Sith grad torterare att jag aldrig skulle få till en bra kollega.

14
00:00:56,260 --> 00:01:00,250
Och det är allt jag någonsin velat, det är allt någon unge vill i min ålder,

15
00:01:00,250 --> 00:01:04,569
bara för att få till en bra kollega.

16
00:01:04,569 --> 00:01:12,720
Och inte bara någon kollega. Nej, jag ville gå till en Ivory Juridisk kollega.

17
00:01:12,720 --> 00:01:18,360
Så om jag inte bättre, skulle gått vara mina drömmar om att gå till Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, eller fängelse - ni vet, i fängelset, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Så jag fick mig en stavningskontroll.

20
00:01:25,170 --> 00:01:29,380
Det är lite utdrag från en av mina favorit spoken word artister Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Hur som helst, som han säger, är vikten av att ha en stavningskontroll mycket viktigt.

22
00:01:34,630 --> 00:01:39,440
>> Så välkommen till Walkthrough 5, där vi kommer att tala om pset5: felstavningar,

23
00:01:39,440 --> 00:01:44,300
där vi kommer att göra vår egen stavningskontroll.

24
00:01:44,300 --> 00:01:50,880
Verktygslådan för denna vecka, distribution koden, kommer att bli viktigt att titta på

25
00:01:50,880 --> 00:01:54,950
bara för att förstå de olika funktionerna som din ordlista kommer att ha.

26
00:01:54,950 --> 00:02:01,500
Vi är faktiskt kommer att ha flera. C filer som tillsammans utgör vår pset.

27
00:02:01,500 --> 00:02:05,420
Och så tittar genom de olika aspekterna, även om vi faktiskt inte är redigering

28
00:02:05,420 --> 00:02:10,770
en av filerna, speller.c, att veta hur det fungerar i förhållande till dictionary.c,

29
00:02:10,770 --> 00:02:14,100
som vi kommer att skriva, kommer att bli ganska viktigt.

30
00:02:14,100 --> 00:02:16,970
I pset spec innehåller också en hel del användbar information

31
00:02:16,970 --> 00:02:21,360
i form av saker som du kan anta, regler och sånt,

32
00:02:21,360 --> 00:02:24,710
så se till att läsa pset spec noga för tips.

33
00:02:24,710 --> 00:02:29,310
Och om du är osäker på en regel eller något liknande, då alltid hänvisa till pset spec

34
00:02:29,310 --> 00:02:31,550
eller diskutera.

35
00:02:31,550 --> 00:02:34,060
Denna pset kommer att starkt beroende pekare,

36
00:02:34,060 --> 00:02:37,890
så vi vill se till att vi förstår skillnaden mellan att lägga stjärnor

37
00:02:37,890 --> 00:02:41,680
framför pekaren namn och et-tecken, hur man befria dem, osv

38
00:02:41,680 --> 00:02:47,550
Så är en mästare på pekare kommer att vara till stor hjälp i detta problem uppsättning.

39
00:02:47,550 --> 00:02:50,460
Vi kommer att undersöka länkade listor lite mer,

40
00:02:50,460 --> 00:02:57,790
där vi har element som vi kallar noder som har både ett värde och en pekare

41
00:02:57,790 --> 00:03:02,520
till nästa nod, och så i huvudsak koppla olika element efter varandra.

42
00:03:02,520 --> 00:03:07,190
Det finns några olika alternativ att genomföra din faktiska ordbok.

43
00:03:07,190 --> 00:03:13,150
Vi kommer att undersöka två huvudsakliga metoder, vilket är hashtabeller och sedan försöker.

44
00:03:13,150 --> 00:03:17,660
I båda dessa, de innebär någon slags begreppet en länkad lista

45
00:03:17,660 --> 00:03:20,790
där du har element kopplade till varandra.

46
00:03:20,790 --> 00:03:25,640
Och så ska vi se över hur man skulle kunna arbeta runt länkade listor,

47
00:03:25,640 --> 00:03:29,680
skapa dem, navigera i termer av hur till exempel infoga en nod i det

48
00:03:29,680 --> 00:03:32,760
eller fri alla noder samt.

49
00:03:32,760 --> 00:03:34,740
När det gäller att befria noder, det är verkligen viktigt

50
00:03:34,740 --> 00:03:37,700
att när vi malloc minne, efteråt vi befria det.

51
00:03:37,700 --> 00:03:42,910
Så vi vill se till att ingen pekare går unfreed, att vi inte har några minnesläckor.

52
00:03:42,910 --> 00:03:48,330
Vi kommer att införa ett verktyg som heter Valgrind som kör ditt program

53
00:03:48,330 --> 00:03:52,260
och kontrollerar om allt det minne som du tilldelade sedan frigörs.

54
00:03:52,260 --> 00:03:59,080
Din pset är färdig först när den fungerar och det har full funktionalitet,

55
00:03:59,080 --> 00:04:03,990
men också, berättar Valgrind du att du inte har hittat några minnesläckor.

56
00:04:03,990 --> 00:04:06,690
Slutligen, för det här pset, jag vill verkligen understryka -

57
00:04:06,690 --> 00:04:11,360
Jag menar, som vanligt, är jag definitivt en anhängare av att använda penna och papper på ditt problem apparater,

58
00:04:11,360 --> 00:04:14,840
men för detta en, tror jag att penna och papper kommer att bli särskilt viktigt

59
00:04:14,840 --> 00:04:19,000
när du vill vara rita pilar för att saker och förstå hur saker och ting fungerar.

60
00:04:19,000 --> 00:04:24,440
Så definitivt försöka använda papper och penna för att rita saker innan du får kodning

61
00:04:24,440 --> 00:04:26,970
eftersom det kan bli lite rörigt.

62
00:04:26,970 --> 00:04:30,700
>> Först, låt oss gå in i länkade listor lite.

63
00:04:30,700 --> 00:04:35,510
Länkade listor består av noder, där varje nod har ett värde i samband med det,

64
00:04:35,510 --> 00:04:39,810
samt en pekare till nästa nod efter det.

65
00:04:39,810 --> 00:04:43,680
Ett par saker viktiga med de länkade listor är att vi måste komma ihåg

66
00:04:43,680 --> 00:04:48,810
där vår första noden är, och sedan när vi vet var den första noden är,

67
00:04:48,810 --> 00:04:52,990
så vi kan få tillgång till noden att den första noden pekar på

68
00:04:52,990 --> 00:04:55,850
och sedan den ena efter det och ett efter detta.

69
00:04:55,850 --> 00:05:00,340
Och sedan det sista elementet i din länkade listan är att nodens pekare

70
00:05:00,340 --> 00:05:02,340
kommer alltid att peka på NULL.

71
00:05:02,340 --> 00:05:08,230
När en nod pekar till NULL, då vet du att du har nått slutet av listan,

72
00:05:08,230 --> 00:05:12,320
att den noden är den sista, att det finns inget efter det.

73
00:05:12,320 --> 00:05:16,970
Här i denna schematiska ser du att pilarna är pekare,

74
00:05:16,970 --> 00:05:20,290
och den blå delen är där värdet lagras,

75
00:05:20,290 --> 00:05:24,420
och sedan den röda rutan med pekaren till det är nodens pekaren

76
00:05:24,420 --> 00:05:27,050
pekar till nästa nod efter det.

77
00:05:27,050 --> 00:05:33,730
Och så du ser här, skulle D-noden pekar på NULL eftersom det är det sista elementet i listan.

78
00:05:33,730 --> 00:05:38,240
>> Låt oss titta på hur vi kan definiera en struct för en nod.

79
00:05:38,240 --> 00:05:40,130
Och eftersom vi vill ha flera noder,

80
00:05:40,130 --> 00:05:43,180
detta kommer att bli en typedef struct

81
00:05:43,180 --> 00:05:46,870
där vi kommer att ha flera olika instanser av noder.

82
00:05:46,870 --> 00:05:50,850
Och så vi definierar det som en ny datatyp.

83
00:05:50,850 --> 00:05:53,630
Här har vi en typedef struct nod.

84
00:05:53,630 --> 00:05:56,160
I det här exemplet, vi arbetar med heltal noder,

85
00:05:56,160 --> 00:06:00,490
så vi har ett heltal heter värde och sedan har vi en annan pekare,

86
00:06:00,490 --> 00:06:07,390
och i detta fall är det en pekare till en nod, så vi har en struct nod * kallas nästa.

87
00:06:07,390 --> 00:06:09,520
Och vi kallar det hela nod.

88
00:06:09,520 --> 00:06:11,110
Se till att du följer den här syntaxen.

89
00:06:11,110 --> 00:06:17,940
Lägg märke till att noden faktiskt refereras upp ovan samt under klammerparenteser.

90
00:06:17,940 --> 00:06:23,400
Sen att hålla reda på var min första noden är i detta länkad lista,

91
00:06:23,400 --> 00:06:29,390
då har jag en nod pekare kallas huvud, och jag malloc utrymme nog för storleken på en nod.

92
00:06:29,390 --> 00:06:36,240
Observera dock att huvudet faktiskt en nod pekare i stället för en faktisk nod själv.

93
00:06:36,240 --> 00:06:40,130
Så huvudet faktiskt inte innehåller något värde,

94
00:06:40,130 --> 00:06:45,590
den pekar endast beroende den första noden i min länkad lista är.

95
00:06:55,080 --> 00:06:58,340
>> För att få en bättre känsla för länkade listor, eftersom det är mycket viktigt

96
00:06:58,340 --> 00:07:02,220
att hålla reda på att se till att du behåller kedjan,

97
00:07:02,220 --> 00:07:09,990
Jag gillar att tänka på det som människor i en rad håller varandra i handen,

98
00:07:09,990 --> 00:07:14,330
där varje person hålla hand med nästa.

99
00:07:14,330 --> 00:07:18,350
Du kan inte se på denna ritning, men i grunden de är pekar till nästa person

100
00:07:18,350 --> 00:07:23,760
som är i sin kedja.

101
00:07:23,760 --> 00:07:29,270
Och så om du vill passera en länkad lista där dessa människor -

102
00:07:29,270 --> 00:07:32,830
föreställa alla dessa människor har värden associerade med dem

103
00:07:32,830 --> 00:07:36,590
och också peka på nästa person i raden -

104
00:07:36,590 --> 00:07:40,810
om du vill korsa den länkade listan, till exempel att antingen ändra värdena

105
00:07:40,810 --> 00:07:42,830
eller sök efter ett värde eller något liknande,

106
00:07:42,830 --> 00:07:48,270
då du vill ha en pekare till den specifika personen.

107
00:07:48,270 --> 00:07:52,670
Så vi kommer att ha en data pekartyp nod.

108
00:07:52,670 --> 00:07:55,580
För detta fall, låt oss kalla det markören.

109
00:07:55,580 --> 00:07:59,630
Ett annat vanligt sätt att namnge detta skulle vara iterator eller något liknande

110
00:07:59,630 --> 00:08:05,130
eftersom det iteration över och faktiskt flytta vilken nod det pekar på.

111
00:08:05,130 --> 00:08:14,410
Detta här blir vår markören.

112
00:08:14,410 --> 00:08:20,180
Vår markören först peka på det första elementet i vår lista.

113
00:08:20,180 --> 00:08:26,910
Och så vad vi vill göra är att vi skulle i princip att fortsätta markören,

114
00:08:26,910 --> 00:08:29,130
flytta den från sida till sida.

115
00:08:29,130 --> 00:08:33,409
I det här fallet vill vi flytta den till nästa element i listan.

116
00:08:33,409 --> 00:08:38,480
Med arrayer, vad vi skulle göra är att vi bara skulle säga att vi ökar index med 1.

117
00:08:38,480 --> 00:08:46,020
I detta fall är det vi måste göra faktiskt hitta vilken person det aktuella personen pekar på,

118
00:08:46,020 --> 00:08:48,930
och det kommer att bli nästa värde.

119
00:08:48,930 --> 00:08:53,230
Så om markören är bara en nod pekare, vad vi vill göra

120
00:08:53,230 --> 00:08:56,320
är vi vill få till det värde som markören pekar på.

121
00:08:56,320 --> 00:09:01,350
Vi vill komma till den nod och sedan, när vi är på den noden, hitta vart det pekar på.

122
00:09:01,350 --> 00:09:05,820
För att komma till själva noden att markören pekar på,

123
00:09:05,820 --> 00:09:13,160
brukar vi visar det genom (* markör).

124
00:09:13,160 --> 00:09:19,160
Det skulle ge dig den verkliga noden som markören pekar på.

125
00:09:19,160 --> 00:09:21,730
Och sedan efter det, vad vi vill göra är att vi vill ha tillgång till

126
00:09:21,730 --> 00:09:25,680
vad det nod nästa värde.

127
00:09:25,680 --> 00:09:32,820
För att göra det, för att komma till värden inne i struct har vi punktoperatorn.

128
00:09:32,820 --> 00:09:39,530
Så skulle det vara (* markör). Nästa.

129
00:09:39,530 --> 00:09:44,840
Men detta är lite rörigt när det gäller att ha fästena runt * markören,

130
00:09:44,840 --> 00:09:56,800
och så vi byter hela denna uttalande med markör->.

131
00:09:56,800 --> 00:10:02,700
Detta är ett streck och sedan en större än-tecken, så gör en pil.

132
00:10:02,700 --> 00:10:05,840
Markören-> nästa.

133
00:10:05,840 --> 00:10:12,390
Som faktiskt kommer att få dig den nod som markören pekar på. Detta värde är nästa.

134
00:10:12,390 --> 00:10:16,790
Så istället för att ha stjärnan och pricken, du ersätta det med en pil.

135
00:10:16,790 --> 00:10:24,820
Var mycket noga med att se till att du försöker använda den här syntaxen.

136
00:10:33,550 --> 00:10:37,620
>> Nu när vi har vår markör, om vi vill komma åt värdet,

137
00:10:37,620 --> 00:10:40,450
tidigare hade vi markör-> nästa,

138
00:10:40,450 --> 00:10:46,260
utan att komma åt värdet vid noden att markören pekar på, vi bara helt enkelt säga

139
00:10:46,260 --> 00:10:48,070
nod-> värde.

140
00:10:48,070 --> 00:10:53,600
Därifrån är det av datatyp vad vi har definierat de värderingar och noderna att vara.

141
00:10:53,600 --> 00:10:59,620
Om det är en int nod, sedan markören-> värde bara kommer att vara ett heltal.

142
00:10:59,620 --> 00:11:04,870
Så vi kan göra operationer på det, kolla likheter, tilldela den olika värden, etc.

143
00:11:04,870 --> 00:11:11,090
Så vad du vill göra om du vill flytta markören till nästa person,

144
00:11:11,090 --> 00:11:15,270
du ändrar faktiskt värdet av markören.

145
00:11:15,270 --> 00:11:19,340
Eftersom markören är en nod pekare, ändrar du den faktiska pekaradress

146
00:11:19,340 --> 00:11:23,890
till adressen för nästa nod i listan.

147
00:11:23,890 --> 00:11:28,930
Detta är bara lite kod där du kan iterera.

148
00:11:28,930 --> 00:11:31,230
Där jag har kommentaren göra något,

149
00:11:31,230 --> 00:11:33,850
det är där du förmodligen kommer att få tillgång till värdet

150
00:11:33,850 --> 00:11:37,850
eller göra något för att göra med just den noden.

151
00:11:37,850 --> 00:11:43,050
Till att börja den, säger jag att min markör initialt

152
00:11:43,050 --> 00:11:48,430
kommer att peka på det första elementet i den länkade listan.

153
00:11:48,430 --> 00:11:52,910
Och så längre fram, definierade jag det som huvudet av noden.

154
00:11:52,910 --> 00:11:57,610
>> Som jag nämnde tidigare, är att befria verkligen viktigt.

155
00:11:57,610 --> 00:12:02,440
Du vill vara säker på att du gratis varje element i listan när du är klar med det.

156
00:12:02,440 --> 00:12:04,940
När du inte behöver referera någon av dessa pekare längre,

157
00:12:04,940 --> 00:12:10,620
du vill vara säker på att du befriar alla dessa pekare.

158
00:12:10,620 --> 00:12:14,460
Men du vill vara mycket försiktig här att du vill undvika minnesläckor.

159
00:12:14,460 --> 00:12:25,080
Om du fri en person i förtid, då alla de tips som den noden pekar på

160
00:12:25,080 --> 00:12:26,900
kommer att gå förlorade.

161
00:12:26,900 --> 00:12:32,070
Att gå tillbaka till den person exemplet för att göra det lite mer high stakes,

162
00:12:32,070 --> 00:12:49,600
låt oss ha dessa människor, utom i det här fallet de svävar över en sjö med ett monster.

163
00:12:49,600 --> 00:12:53,200
Vi vill se till att när vi befriar vi inte förlorar

164
00:12:53,200 --> 00:12:58,920
och släppa alla noder innan vi har faktiskt befriat dem.

165
00:12:58,920 --> 00:13:05,730
Till exempel, om du skulle helt enkelt ringa gratis på den här killen här,

166
00:13:05,730 --> 00:13:15,350
då skulle han befrias, men då alla dessa killar skulle gå förlorad

167
00:13:15,350 --> 00:13:18,450
och de skulle glida iväg och falla ner.

168
00:13:18,450 --> 00:13:24,900
Så vi vill se till att istället vill vi upprätthålla en länk till resten.

169
00:13:37,630 --> 00:13:42,480
Vår huvud pekare, som pekar på det första elementet i listan.

170
00:13:42,480 --> 00:13:49,990
Det är ungefär som ett rep förankring den första personen.

171
00:13:52,870 --> 00:13:57,470
Vad du kanske vill göra när du befriar en lista har -

172
00:13:57,470 --> 00:14:04,520
Om du vill frigöra det första elementet först, sedan kan du få en tillfällig pekare

173
00:14:04,520 --> 00:14:07,370
som pekar på vad det första elementet är.

174
00:14:07,370 --> 00:14:11,420
Så du har ditt tillfälliga pekaren pekar här.

175
00:14:11,420 --> 00:14:15,840
På så sätt har vi en tag av den första noden.

176
00:14:15,840 --> 00:14:18,930
Och sedan, eftersom vi vet att den första noden kommer att frigöras,

177
00:14:18,930 --> 00:14:24,890
då kan vi flytta rep, detta ankare, huvudet,

178
00:14:24,890 --> 00:14:31,930
att faktiskt peka på vad det första ett pekar på.

179
00:14:31,930 --> 00:14:38,760
Så denna huvud pekar faktiskt det andra elementet nu.

180
00:14:38,760 --> 00:14:43,980
Nu är vi tillåts att frigöra allt lagras i temp,

181
00:14:43,980 --> 00:14:53,360
och så att vi kan radera det utan att det äventyrar alla andra noder i vår lista.

182
00:14:54,140 --> 00:15:05,020
Ett annat sätt att du kan göra detta kan vara

183
00:15:05,020 --> 00:15:08,650
varje gång du frigöra bara det sista elementet i listan

184
00:15:08,650 --> 00:15:11,010
eftersom de är garanterade att inte pekade på någonting.

185
00:15:11,010 --> 00:15:15,570
Så du kan bara befria denna, sedan fri här, sedan fri här.

186
00:15:15,570 --> 00:15:21,900
Som definitivt fungerar men är lite långsammare på grund av arten av de länkade listor,

187
00:15:21,900 --> 00:15:24,670
Vi kan inte bara direkt hoppa till den sista.

188
00:15:24,670 --> 00:15:28,030
Vi måste passera varje element i den länkade listan

189
00:15:28,030 --> 00:15:31,020
och kontrollera om att man pekar på NULL, kontrollera varje gång,

190
00:15:31,020 --> 00:15:33,780
och sedan när vi når slutet, sedan fri att.

191
00:15:33,780 --> 00:15:40,270
Om du skulle göra den här processen, skulle du faktiskt kolla här,

192
00:15:40,270 --> 00:15:44,190
kontroll här, sedan kontrollera här frigör den,

193
00:15:44,190 --> 00:15:47,470
sedan gå tillbaka, kontroll hit, kontroll här, befria det,

194
00:15:47,470 --> 00:15:49,660
kontroll här, och sedan frigöra den.

195
00:15:49,660 --> 00:15:52,880
Det tar lite längre tid. Ja.

196
00:15:52,880 --> 00:15:59,060
>> [Elev] Skulle det vara möjligt att göra en länkad lista som lagrar en utgång pekaren till slutet?

197
00:15:59,060 --> 00:16:01,320
Som definitivt skulle vara möjligt.

198
00:16:01,320 --> 00:16:08,340
För att upprepa frågan, är det möjligt att ha en länkad lista struktur

199
00:16:08,340 --> 00:16:12,490
så att du har en pekare som pekar till slutet av den länkade listan?

200
00:16:12,490 --> 00:16:18,090
Jag skulle säga att det är möjligt, och varje gång du sätter något i din länkade lista

201
00:16:18,090 --> 00:16:21,470
du måste uppdatera pekaren och sånt.

202
00:16:21,470 --> 00:16:26,640
Du skulle ha en nod * svans, till exempel.

203
00:16:26,640 --> 00:16:29,840
Men när du genomföra den här funktionen måste du tänka på avvägningar,

204
00:16:29,840 --> 00:16:32,700
gillar hur många gånger jag kommer att iterera över detta,

205
00:16:32,700 --> 00:16:36,100
Hur svårt är det att vara att hålla reda på svansen och huvudet

206
00:16:36,100 --> 00:16:38,400
liksom min iterator, och sådana saker.

207
00:16:40,730 --> 00:16:42,480
Betyder det -? >> [Elev] Ja.

208
00:16:42,480 --> 00:16:48,270
Det är möjligt, men när det gäller designbeslut, du måste väga alternativen.

209
00:16:53,850 --> 00:17:01,090
>> Här är ett skelett av kod som gör att du kan frigöra varje element i en länkad lista.

210
00:17:01,090 --> 00:17:05,460
Återigen, eftersom jag iteration över en länkad lista, jag kommer att vilja ha någon form av markör

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

212
00:17:08,670 --> 00:17:14,640
Vi iteration tills markören är NULL.

213
00:17:14,640 --> 00:17:17,640
Du vill inte att iterera när markören är NULL

214
00:17:17,640 --> 00:17:20,579
eftersom det innebär att det inte finns något i listan.

215
00:17:20,579 --> 00:17:25,069
Så så här jag gör en tillfällig nod *

216
00:17:25,069 --> 00:17:29,610
pekar på vad jag funderar är den första på min lista,

217
00:17:29,610 --> 00:17:35,340
och då jag flyttar min markör framåt 1 och sedan fri vad jag hade i tillfällig förvaring.

218
00:17:38,460 --> 00:17:43,650
>> Nu kommer vi att infoga i länkade listor.

219
00:18:00,200 --> 00:18:09,660
Jag har tre noder i min länkad lista, och låt oss gå med det enkla fallet

220
00:18:09,660 --> 00:18:18,970
där vi vill infoga en annan nod i slutet av vår länkad lista.

221
00:18:18,970 --> 00:18:25,980
För att göra det, allt vi skulle göra skulle vi passera

222
00:18:25,980 --> 00:18:32,100
att hitta där den nuvarande änden av länkade listan är så beroende nod pekar på NULL -

223
00:18:32,100 --> 00:18:33,850
Det är detta en -

224
00:18:33,850 --> 00:18:37,260
och sedan säga, faktiskt, är detta inte kommer att vara den sista noden;

225
00:18:37,260 --> 00:18:39,830
vi faktiskt kommer att ha en annan.

226
00:18:39,830 --> 00:18:46,260
Så vi skulle ha denna ström en punkt till vad vi sätter.

227
00:18:46,260 --> 00:18:50,080
Så nu denna röda personen blir här den sista noden i den länkade listan.

228
00:18:50,080 --> 00:18:56,080
Och så karakteristiska för den sista noden i den länkade listan är att den pekar till NULL.

229
00:18:56,080 --> 00:19:09,380
Så vad vi skulle behöva göra är att ställa in röd kille pekare till NULL. Där.

230
00:19:09,380 --> 00:19:25,370
>> Men vad händer om vi ville infoga en nod mellan den andra och tredje?

231
00:19:25,370 --> 00:19:28,960
Att man är inte riktigt så enkelt eftersom vi vill se till att

232
00:19:28,960 --> 00:19:34,290
att vi låter inte gå någon nod i vår länkad lista.

233
00:19:34,290 --> 00:19:43,450
Vad vi skulle behöva göra är att se till att vi förankrar oss till var och en.

234
00:19:43,450 --> 00:19:49,900
Till exempel, låt oss kalla det den andra.

235
00:19:49,900 --> 00:19:54,390
Om du sagt det andra en pekar nu på denna nya

236
00:19:54,390 --> 00:20:02,520
och du gjorde bara en pekare där, då skulle resultera i den här killen går förlorade

237
00:20:02,520 --> 00:20:07,830
eftersom det inte finns någon koppling till honom.

238
00:20:07,830 --> 00:20:18,970
Istället - Jag ska göra det här igen. Ursäkta mina konstnärliga förmågor.

239
00:20:18,970 --> 00:20:26,570
Vi vet att vi inte bara kan länka direkt 2 till den nya.

240
00:20:26,570 --> 00:20:30,480
Vi måste se till att vi håller fast vid den sista.

241
00:20:30,480 --> 00:20:39,200
Vad vi kanske vill göra är att ha en tillfällig pekare

242
00:20:39,200 --> 00:20:42,650
till elementet som kommer att läggas på.

243
00:20:42,650 --> 00:20:45,140
Så då har vi en temporär pekare där.

244
00:20:45,140 --> 00:20:50,780
Eftersom vi vet att denna tredje hålls reda på,

245
00:20:50,780 --> 00:20:53,680
2 kan nu länka till vår nya.

246
00:20:53,680 --> 00:20:57,490
Och om detta nya röda killen kommer att vara mellan 2 och 3,

247
00:20:57,490 --> 00:21:05,550
vad är att killen pekare kommer att peka på? >> [Elev] Temp.

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

249
00:21:07,490 --> 00:21:15,430
Så då denna röda killen nästa värde kommer att vara temp.

250
00:21:26,090 --> 00:21:33,010
När du sätter in länkade listor, såg vi att vi kunde

251
00:21:33,010 --> 00:21:38,260
enkelt lägga till något till slutet genom att skapa en tillfällig array,

252
00:21:38,260 --> 00:21:42,850
eller om vi ville lägga till något i mitten av vår grupp,

253
00:21:42,850 --> 00:21:46,810
då det skulle ta lite mer blanda runt.

254
00:21:46,810 --> 00:21:50,240
Om du vill, till exempel, har en sorterad länkad lista,

255
00:21:50,240 --> 00:21:54,880
då måste man typ av väga kostnaderna och fördelarna med det

256
00:21:54,880 --> 00:21:59,720
för om du vill ha en sorterad array, innebär det att varje gång du sätter i den,

257
00:21:59,720 --> 00:22:01,630
det kommer att ta lite längre tid.

258
00:22:01,630 --> 00:22:05,500
Men om du vill senare, när vi hittar vi vill,

259
00:22:05,500 --> 00:22:10,280
söka igenom en länkad lista, kan det vara lättare om du vet att allt är i sin ordning.

260
00:22:10,280 --> 00:22:15,340
Så du kanske vill väga kostnaderna och fördelarna med det.

261
00:22:20,150 --> 00:22:27,740
>> Ett annat sätt att infoga i en länkad lista är att infoga i början av en lista.

262
00:22:27,740 --> 00:22:34,700
Om vi ​​drar vårt ankare här - det är vår huvud -

263
00:22:34,700 --> 00:22:40,960
och sedan har dessa personer knutna till den,

264
00:22:40,960 --> 00:22:48,460
och sedan har vi en ny nod som skall införas i början,

265
00:22:48,460 --> 00:22:52,590
vad kan vi vill göra?

266
00:22:55,220 --> 00:23:03,580
Vad skulle vara fel med att bara säga jag vill länka den röda till blå,

267
00:23:03,580 --> 00:23:05,790
eftersom det är den första?

268
00:23:05,790 --> 00:23:08,570
Vad skulle hända här?

269
00:23:08,570 --> 00:23:12,130
Alla dessa tre skulle gå vilse.

270
00:23:12,130 --> 00:23:14,140
Så vi vill inte göra det.

271
00:23:14,140 --> 00:23:21,430
Återigen har vi lärt oss att vi måste ha någon form av tillfällig pekare.

272
00:23:21,430 --> 00:23:34,470
Låt oss välja att ha en tillfällig punkt till den här killen.

273
00:23:34,470 --> 00:23:39,640
Då kan vi ha den blå en punkt till den tillfälliga

274
00:23:39,640 --> 00:23:43,240
och sedan den röda punkten till blå.

275
00:23:43,240 --> 00:23:47,830
Anledningen till att jag använder folk här är att vi verkligen vill visualisera

276
00:23:47,830 --> 00:23:53,180
hålla fast vid människor och se till att vi har en länk till dem

277
00:23:53,180 --> 00:23:57,590
innan vi släpper en annan hand eller något liknande.

278
00:24:05,630 --> 00:24:10,650
>> Nu när vi har en känsla av länkade listor - hur vi kan skapa en länkad lista

279
00:24:10,650 --> 00:24:15,090
och skapa strukturer för den som består av typen definitionen för en nod

280
00:24:15,090 --> 00:24:19,060
och sedan se till att vi har en pekare till chefen för den länkade listan -

281
00:24:19,060 --> 00:24:23,210
när vi har det och vi vet hur man färdas genom en matris,

282
00:24:23,210 --> 00:24:28,200
få tillgång till olika delar, vet vi hur man sätter i och vi vet hur man befria dem,

283
00:24:28,200 --> 00:24:30,260
då kan vi få in felstavningar.

284
00:24:30,260 --> 00:24:38,150
Som vanligt har vi en del frågor som kommer att få dig brukade arbetar med länkade listor

285
00:24:38,150 --> 00:24:41,750
och olika strukturer som köer och stackar.

286
00:24:41,750 --> 00:24:46,000
Då kan vi flytta in felstavningar.

287
00:24:46,000 --> 00:24:55,170
>> Felstavningar har i distributionen koden ett par filer i vikt.

288
00:24:55,170 --> 00:24:58,850
Först märker vi att vi har denna Makefile här,

289
00:24:58,850 --> 00:25:03,040
som vi inte har riktigt stött på tidigare.

290
00:25:03,040 --> 00:25:10,090
Om du såg innanför pset5 mappen, skulle du märka att du har en. H. fil,

291
00:25:10,090 --> 00:25:12,530
så har du två. C-filer.

292
00:25:12,530 --> 00:25:18,920
Vad detta Makefile gör är tidigare skulle vi skriver bara göra och sedan programnamnet

293
00:25:18,920 --> 00:25:25,550
och då skulle vi se alla dessa argument och flaggor gick in i kompilatorn.

294
00:25:25,550 --> 00:25:30,580
Vad Makefile gör är låter oss att sammanställa flera filer samtidigt

295
00:25:30,580 --> 00:25:34,650
och passerar i flaggorna som vi vill.

296
00:25:34,650 --> 00:25:41,300
Här ser vi bara det finns en huvudfil här.

297
00:25:41,300 --> 00:25:43,730
Sedan har vi faktiskt två källfiler.

298
00:25:43,730 --> 00:25:47,520
Vi har speller.c och dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Du är välkommen att redigera Makefile om du vill.

300
00:25:54,560 --> 00:26:03,310
Observera att här om du skriver ren, vad den gör faktiskt bort allt

301
00:26:03,310 --> 00:26:06,340
som är kärnan.

302
00:26:06,340 --> 00:26:09,190
Om du har en segmenteringsfel, i princip får du en central soptipp.

303
00:26:09,190 --> 00:26:13,260
Så denna fula lilla filen visas i din katalog som heter kärna.

304
00:26:13,260 --> 00:26:16,310
Du vill ta bort det för att göra den ren.

305
00:26:16,310 --> 00:26:20,940
Det tar bort alla exe-filer och. O-filer.

306
00:26:27,900 --> 00:26:30,220
>> Låt oss ta en titt in i dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Det säger att det förklarar en ordbok funktionalitet.

308
00:26:34,410 --> 00:26:39,530
Vi har en maximal längd för alla ord i ordboken.

309
00:26:39,530 --> 00:26:45,130
Vi säger att detta kommer att bli den längsta möjliga ordet. Det är av längd 45.

310
00:26:45,130 --> 00:26:48,900
Så vi inte kommer att ha några ord som överstiger denna längd.

311
00:26:48,900 --> 00:26:50,980
Här har vi bara funktionen prototyper.

312
00:26:50,980 --> 00:26:55,290
Vi har inte det faktiska genomförandet, eftersom det är vad vi kommer att göra detta pset.

313
00:26:55,290 --> 00:26:59,940
Men vad detta innebär är eftersom vi har att göra med större filer här

314
00:26:59,940 --> 00:27:06,650
och funktionalitet i större skala, är det bra att ha en. h. fil

315
00:27:06,650 --> 00:27:11,290
så att någon annan läser eller använda din kod kan förstå vad som händer.

316
00:27:11,290 --> 00:27:17,910
Och kanske de vill genomföra försök om du gjorde hashtabeller eller vice versa.

317
00:27:17,910 --> 00:27:21,850
Då skulle de säga min last funktion,

318
00:27:21,850 --> 00:27:26,950
det faktiska genomförandet kommer att skilja sig, men denna prototyp kommer inte att ändras.

319
00:27:26,950 --> 00:27:33,280
Här har vi kontrollera, vilket returnerar sant om ett givet ord i ordboken.

320
00:27:33,280 --> 00:27:39,800
Sen har vi last, som i princip tar i en ordbok fil

321
00:27:39,800 --> 00:27:44,360
och därefter laddar in det i vissa datastruktur.

322
00:27:44,360 --> 00:27:47,500
Vi har storlek, som när kallas, återvänder storleken på din ordlista,

323
00:27:47,500 --> 00:27:50,310
hur många ord lagras i det,

324
00:27:50,310 --> 00:27:54,390
och sedan lossa, vilket frigör allt minne som du kan ha tagit upp

325
00:27:54,390 --> 00:27:57,900
samtidigt som din ordbok.

326
00:28:01,070 --> 00:28:03,590
>> Låt oss ta en titt på dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Vi ser att det ser mycket lik dictionary.h, förutom nu bara har alla dessa Todos i den.

328
00:28:10,490 --> 00:28:16,980
Och så är ditt jobb. Så småningom kommer du att fylla speller.c med allt i denna kod.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, när det körs, inte verkligen kommer att göra något,

330
00:28:21,540 --> 00:28:29,590
så vi ser till speller.c att se det faktiska genomförandet av stavningskontrollen.

331
00:28:29,590 --> 00:28:32,060
Även om du inte kommer att redigera någon av denna kod,

332
00:28:32,060 --> 00:28:38,050
Det är viktigt att läsa, förstå när är belastningen kallas när jag ringer check,

333
00:28:38,050 --> 00:28:42,350
bara för att förstå, kartlägga det, se hur funktionen fungerar.

334
00:28:42,350 --> 00:28:49,860
Vi ser att det är kontrollen för rätt användning.

335
00:28:49,860 --> 00:28:55,200
Huvudsak när någon kör speller, betyder det att det är frivilligt

336
00:28:55,200 --> 00:29:00,950
för dem att passera i en ordbok fil eftersom det kommer att bli en standard ordlista fil.

337
00:29:00,950 --> 00:29:05,410
Och så måste passera i texten för att vara stavningskontrolleras.

338
00:29:05,410 --> 00:29:11,410
rusage handlar tid eftersom en del av denna pset som vi tar hand om senare

339
00:29:11,410 --> 00:29:14,790
inte bara få en fungerande stavningskontroll fungerar

340
00:29:14,790 --> 00:29:17,190
men faktiskt få det att vara snabb.

341
00:29:17,190 --> 00:29:22,040
Och så då det är där rusage kommer att komma in

342
00:29:22,040 --> 00:29:28,740
Här ser vi det första samtalet till en av våra dictionary.c filer, vilket är last.

343
00:29:28,740 --> 00:29:34,720
Load returnerar sant eller falskt - sant på framgång, falsk vid fel.

344
00:29:34,720 --> 00:29:41,400
Så om ordlistan inte har laddats på rätt sätt, då speller.c kommer tillbaka 1 och sluta.

345
00:29:41,400 --> 00:29:47,920
Men om det gör belastningen på rätt sätt, så det kommer att fortsätta.

346
00:29:47,920 --> 00:29:50,740
Vi fortsätter, och vi se några I / O-här,

347
00:29:50,740 --> 00:29:56,210
där det kommer att ha att göra med att öppna textfilen.

348
00:29:56,210 --> 00:30:04,640
Här, vad detta innebär är spell-kontroller vartenda ord i texten.

349
00:30:04,640 --> 00:30:09,270
Så vad speller.c gör här är iteration över vart och ett av orden i textfilen

350
00:30:09,270 --> 00:30:12,790
och sedan kontrollera dem i ordboken.

351
00:30:24,680 --> 00:30:32,350
Här har vi ett booleskt felstavat som kommer att se om kontrollen returnerar sant eller inte.

352
00:30:32,350 --> 00:30:37,110
Om ordet faktiskt i ordboken, så kolla återkommer sant.

353
00:30:37,110 --> 00:30:39,760
Det innebär att ordet inte är felstavat.

354
00:30:39,760 --> 00:30:45,330
Så felstavade skulle vara falsk, och det är därför vi har smäll där indikationen.

355
00:30:45,330 --> 00:30:56,320
Vi håller på att gå, och då håller reda på hur många felstavade ord

356
00:30:56,320 --> 00:30:58,910
Det finns i filen.

357
00:30:58,910 --> 00:31:03,870
Det fortsätter på och stänger filen.

358
00:31:03,870 --> 00:31:09,250
Då här, rapporterar den hur många felstavade ord du hade.

359
00:31:09,250 --> 00:31:12,680
Den beräknar hur lång tid det tog att ladda ordlistan,

360
00:31:12,680 --> 00:31:15,080
hur mycket tid det tog att kontrollera det,

361
00:31:15,080 --> 00:31:18,510
hur mycket tid det tog att beräkna storleken,

362
00:31:18,510 --> 00:31:21,260
vilket som vi ska gå vidare, bör vara mycket liten,

363
00:31:21,260 --> 00:31:25,390
och sedan hur lång tid det tog att lasta i ordlistan.

364
00:31:25,390 --> 00:31:27,700
Här ovanför ser vi uppmaningen att lasta här.

365
00:31:27,700 --> 00:31:52,690
Om vi ​​kontrollerar för storlek här,

366
00:31:52,690 --> 00:31:59,050
då ser vi att här är uppmaningen att storleken där den bestämmer storleken på ordlistan.

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

368
00:32:07,100 --> 00:32:10,920
>> Vår uppgift här pset är att genomföra belastning, vilket kommer att belasta ordlistan

369
00:32:10,920 --> 00:32:15,480
datastruktur - vilket du väljer, oavsett om det är en hash-tabell eller ett försök -

370
00:32:15,480 --> 00:32:18,810
med ord från ordlistan filen.

371
00:32:18,810 --> 00:32:25,290
Då har du storlek, vilket kommer att returnera antalet ord i ordlistan.

372
00:32:25,290 --> 00:32:29,860
Och om du implementerar belastning på ett smart sätt, så storlek bör vara ganska lätt.

373
00:32:29,860 --> 00:32:33,860
Då har du kontrollera vilket kommer att kontrollera om ett givet ord finns i ordlistan.

374
00:32:33,860 --> 00:32:38,690
Så speller.c passerar i en sträng, och då måste man kontrollera om den strängen

375
00:32:38,690 --> 00:32:41,610
finns i din ordlista.

376
00:32:41,610 --> 00:32:46,750
Observera att vi generellt har standard ordböcker,

377
00:32:46,750 --> 00:32:53,020
men i detta pset, passerade i stort sett någon ordbok på något språk.

378
00:32:53,020 --> 00:32:57,040
Så vi kan inte bara anta att ordet THE är inne.

379
00:32:57,040 --> 00:33:03,090
Ordet Foobar kan definieras i en viss lexikon som vi passerar i.

380
00:33:03,090 --> 00:33:07,920
Och då har vi lasta, vilket frigör ordlistan från minnet.

381
00:33:07,920 --> 00:33:11,930
>> Först vill jag gå över hashtabellen metoden

382
00:33:11,930 --> 00:33:14,630
om hur vi kan genomföra alla dessa fyra funktioner,

383
00:33:14,630 --> 00:33:18,650
och sedan ska jag gå över försöker metoden, hur vi genomför dessa fyra funktioner,

384
00:33:18,650 --> 00:33:22,720
och i slutet tala om några allmänna tips när du gör pset

385
00:33:22,720 --> 00:33:27,870
och även hur du skulle kunna använda Valgrind för att kontrollera minnesläckor.

386
00:33:27,870 --> 00:33:30,550
>> Låt oss komma in i hash-tabellen metoden.

387
00:33:30,550 --> 00:33:35,910
En hash-tabell består av en lista av skopor.

388
00:33:35,910 --> 00:33:43,010
Varje värde varje ord, kommer att gå in i en av dessa hinkar.

389
00:33:43,010 --> 00:33:53,200
En hashtabell helst jämnt distribuerar alla dessa värden som du passerar i

390
00:33:53,200 --> 00:33:57,160
och sedan fyller dem i hinken så att varje skopa

391
00:33:57,160 --> 00:34:02,000
har ungefär lika många värden i den.

392
00:34:02,000 --> 00:34:09,630
Strukturen för en hashtabell, har vi en matris med länkade listor.

393
00:34:09,630 --> 00:34:17,900
Vad vi gör är när vi passerar ett värde kontrollerar vi om detta värde ska tillhöra,

394
00:34:17,900 --> 00:34:23,840
vilket hink den tillhör, och sedan placera det i den länkade listan i samband med den skopa.

395
00:34:23,840 --> 00:34:28,199
Här, vad jag har är en hashfunktion.

396
00:34:28,199 --> 00:34:31,320
Det är en int hashtabell.

397
00:34:31,320 --> 00:34:38,540
Så för första skopan, alla heltal under 10 går in i den första hinken.

398
00:34:38,540 --> 00:34:42,190
Alla heltal över 10 men under 20 Gå in i andra,

399
00:34:42,190 --> 00:34:44,179
och sedan så vidare och så vidare.

400
00:34:44,179 --> 00:34:52,370
För mig är varje hink representerar dessa nummer.

401
00:34:52,370 --> 00:34:59,850
Men säger jag skulle passera i 50, till exempel.

402
00:34:59,850 --> 00:35:07,490
Det verkar som om de första tre innehåller en rad tio nummer.

403
00:35:07,490 --> 00:35:12,570
Men jag vill låta min hashtabell att ta i någon form av heltal,

404
00:35:12,570 --> 00:35:19,860
så då skulle jag behöva filtrera bort alla nummer över 30 i den sista skopan.

405
00:35:19,860 --> 00:35:26,660
Och så då skulle resultera i en slags obalanserad hashtabell.

406
00:35:31,330 --> 00:35:35,640
För att upprepa, är en hash tabell bara en rad av skopor

407
00:35:35,640 --> 00:35:38,590
där varje hink är en länkad lista.

408
00:35:38,590 --> 00:35:43,730
Och så för att avgöra var varje värde går, vilket hink den går in i,

409
00:35:43,730 --> 00:35:46,260
du kommer att vilja vad som kallas en hashfunktion

410
00:35:46,260 --> 00:35:55,010
som tar ett värde och sedan säger detta värde motsvarar en viss hink.

411
00:35:55,010 --> 00:36:00,970
Så upp ovan i detta exempel, tog min hashfunktion varje värde.

412
00:36:00,970 --> 00:36:03,020
Det kontrolleras huruvida det var mindre än 10.

413
00:36:03,020 --> 00:36:05,360
Om det var, skulle det sätta den i den första hinken.

414
00:36:05,360 --> 00:36:08,910
Den kontrollerar om det är mindre än 20, sätter det i det andra om sant,

415
00:36:08,910 --> 00:36:12,880
kontrollerar om det är mindre än 30, och sedan sätter det i den tredje skopan,

416
00:36:12,880 --> 00:36:16,990
och sedan allt annat faller bara den fjärde hinken.

417
00:36:16,990 --> 00:36:20,110
Så när du har ett värde, din hashfunktion

418
00:36:20,110 --> 00:36:25,420
kommer att placera detta värde i lämplig hinken.

419
00:36:25,420 --> 00:36:32,430
Hashfunktionen behöver i princip veta hur många skopor du har.

420
00:36:32,430 --> 00:36:37,960
Din hash-tabell storlek, antalet skopor du har,

421
00:36:37,960 --> 00:36:41,190
det kommer att bli ett fast antal som är upp till dig, för dig att bestämma,

422
00:36:41,190 --> 00:36:43,590
men det kommer att bli ett fast antal.

423
00:36:43,590 --> 00:36:51,840
Så din hashfunktion kommer att förlita sig på att för att avgöra vilken hink varje nyckel går till

424
00:36:51,840 --> 00:36:54,450
så att den jämnt spridda.

425
00:36:56,150 --> 00:37:03,820
Liknar vårt genomförande av länkade listor, nu varje nod i hashtabellen

426
00:37:03,820 --> 00:37:07,000
faktiskt kommer att ha en typ röding.

427
00:37:07,000 --> 00:37:14,340
Så vi har en char array som heter ord och sedan en annan pekare till nästa nod,

428
00:37:14,340 --> 00:37:19,010
vilket är rimligt eftersom det kommer att bli en länkad lista.

429
00:37:19,010 --> 00:37:24,350
Kommer du ihåg när vi hade kopplat listor, jag gjorde en nod * kallas huvud

430
00:37:24,350 --> 00:37:31,060
som pekar till den första noden i den länkade listan.

431
00:37:31,060 --> 00:37:34,020
Men för vår hashtabell, eftersom vi har flera länkade listor,

432
00:37:34,020 --> 00:37:37,520
vad vi vill är att vi vill att vår hashtabell att vara som, "Vad är en hink?"

433
00:37:37,520 --> 00:37:43,340
En hink är bara en lista över pekare nod,

434
00:37:43,340 --> 00:37:50,620
och så varje element i skopan faktiskt pekar på dess motsvarande länkad lista.

435
00:37:56,180 --> 00:38:01,520
För att gå tillbaka till denna schematiska, ser du att skoporna själva är pilarna,

436
00:38:01,520 --> 00:38:06,980
inte faktiska noder.

437
00:38:11,680 --> 00:38:16,420
En viktig egenskap hos hash funktioner är att de är deterministiska.

438
00:38:16,420 --> 00:38:19,440
Det innebär att när du hash numret 2,

439
00:38:19,440 --> 00:38:22,270
Det ska alltid returnera samma hink.

440
00:38:22,270 --> 00:38:26,440
Varje enskilt värde som går in i hashfunktion, om de upprepas,

441
00:38:26,440 --> 00:38:29,690
måste få samma index.

442
00:38:29,690 --> 00:38:34,210
Så din hashfunktion returnerar index för matrisen

443
00:38:34,210 --> 00:38:38,530
där detta värde tillhör.

444
00:38:38,530 --> 00:38:41,790
Som jag nämnde tidigare, är antalet skopor fast,

445
00:38:41,790 --> 00:38:49,630
och så din index som du återvänder måste vara mindre än antalet segment

446
00:38:49,630 --> 00:38:52,680
men större än 0.

447
00:38:52,680 --> 00:39:00,780
Anledningen till att vi har hashfunktioner istället för bara en länkad enda lista

448
00:39:00,780 --> 00:39:09,290
eller en enda array är att vi vill kunna hoppa till ett visst avsnitt lättast

449
00:39:09,290 --> 00:39:11,720
om vi vet det karakteristiska för ett värde -

450
00:39:11,720 --> 00:39:14,760
istället för att behöva söka igenom hela hela ordboken,

451
00:39:14,760 --> 00:39:18,320
att kunna hoppa till en viss del av det.

452
00:39:19,880 --> 00:39:24,440
Din hashfunktion bör ta hänsyn till att idealt,

453
00:39:24,440 --> 00:39:28,980
varje hink har ungefär samma antal tangenter.

454
00:39:28,980 --> 00:39:35,040
Eftersom den hash-tabell är en serie av länkade listor,

455
00:39:35,040 --> 00:39:38,480
då länkade listor själva kommer att ha mer än en nod.

456
00:39:38,480 --> 00:39:43,210
I föregående exempel, två olika nummer, även om de inte var lika,

457
00:39:43,210 --> 00:39:46,950
när hashas, ​​skulle återvända samma index.

458
00:39:46,950 --> 00:39:53,620
Så när du arbetar med ord, ett ord när hashas

459
00:39:53,620 --> 00:39:57,450
skulle vara samma hashvärde som ett annat ord.

460
00:39:57,450 --> 00:40:04,140
Det är vad vi kallar en kollision, när vi har en nod som när hashas,

461
00:40:04,140 --> 00:40:09,610
den länkade listan att skopan inte är tom.

462
00:40:09,610 --> 00:40:14,180
Den teknik som vi kallar det är linjär sondering,

463
00:40:14,180 --> 00:40:22,550
där man går in den länkade listan och sedan hitta där du vill infoga den noden

464
00:40:22,550 --> 00:40:25,520
eftersom du har en kollision.

465
00:40:25,520 --> 00:40:28,070
Du kan se att det kan finnas en avvägning här, eller hur?

466
00:40:28,070 --> 00:40:33,760
Om du har en mycket liten hashtabell, ett mycket litet antal skopor,

467
00:40:33,760 --> 00:40:36,380
då du kommer att ha en massa kollisioner.

468
00:40:36,380 --> 00:40:40,460
Men om du gör en mycket stor hash-tabell,

469
00:40:40,460 --> 00:40:44,110
du förmodligen kommer att minimera kollisioner,

470
00:40:44,110 --> 00:40:47,170
men det kommer att bli en mycket stor datastruktur.

471
00:40:47,170 --> 00:40:49,310
Det kommer att bli kompromisser med det.

472
00:40:49,310 --> 00:40:51,310
Så när du gör din pset, försök att leka

473
00:40:51,310 --> 00:40:54,210
mellan kanske gör en mindre hash-tabell

474
00:40:54,210 --> 00:41:02,100
men sedan vet att det kommer att ta lite längre tid att passera de olika delarna

475
00:41:02,100 --> 00:41:04,270
av dessa länkade listor.

476
00:41:04,270 --> 00:41:09,500
>> Vilken belastning kommer att göra är att iterera över varje ord i ordlistan.

477
00:41:09,500 --> 00:41:13,180
Det passerar i en pekare till ordlistan filen.

478
00:41:13,180 --> 00:41:18,050
Så du kommer att dra nytta av den fil I / O funktioner som du behärskar i pset4

479
00:41:18,050 --> 00:41:23,010
och iterera över varje ord i ordlistan.

480
00:41:23,010 --> 00:41:26,620
Du vill att varje ord i ordlistan för att bli en ny nod,

481
00:41:26,620 --> 00:41:32,730
och du kommer att placera var och en av dessa noder insidan av din ordlista datastruktur.

482
00:41:32,730 --> 00:41:36,560
När du får ett nytt ord, vet du att det kommer att bli en nod.

483
00:41:36,560 --> 00:41:46,590
Så du kan gå genast och malloc en nod pekare för varje nytt ord som du har.

484
00:41:46,590 --> 00:41:52,610
Här ringer jag min new_node nod pekare och jag mallocing vad? Storleken på en nod.

485
00:41:52,610 --> 00:41:59,190
Sedan att läsa själva strängen från en fil, eftersom ordboken faktiskt lagras

486
00:41:59,190 --> 00:42:03,340
av ett ord och sedan en ny linje, vad vi kan dra nytta av

487
00:42:03,340 --> 00:42:06,520
är funktionen fscanf,

488
00:42:06,520 --> 00:42:10,280
varigenom filen är ordlistan fil som vi är passerat i,

489
00:42:10,280 --> 00:42:18,900
så det skannar filen för en sträng och platser som sträng i den sista argumentet.

490
00:42:18,900 --> 00:42:26,890
Om ni minns tillbaka till en av föreläsningarna, när vi gick över

491
00:42:26,890 --> 00:42:29,320
och typ av skalade lagren tillbaka på CS50 biblioteket,

492
00:42:29,320 --> 00:42:33,430
vi såg en implementering av fscanf där.

493
00:42:33,430 --> 00:42:37,700
För att gå tillbaka till fscanf har vi fil som vi läser från,

494
00:42:37,700 --> 00:42:42,570
Vi letar efter en sträng i filen, och sedan vi placera den i

495
00:42:42,570 --> 00:42:48,340
Här har jag new_node-> ord eftersom new_node är en nod pekare,

496
00:42:48,340 --> 00:42:50,380
inte en verklig nod.

497
00:42:50,380 --> 00:42:57,100
Så då jag säger new_node, jag vill gå till den nod som det pekar på

498
00:42:57,100 --> 00:43:01,190
och sedan tilldela det värdet till ordet.

499
00:43:01,190 --> 00:43:08,540
Vi vill sedan ta det ordet och för in den i hash-tabellen.

500
00:43:08,540 --> 00:43:13,750
Inse att vi gjort new_node en nod pekare

501
00:43:13,750 --> 00:43:18,230
eftersom vi kommer att vilja veta vad adressen till den nod är

502
00:43:18,230 --> 00:43:23,940
när vi sätter det eftersom strukturen av noderna själva, av struct,

503
00:43:23,940 --> 00:43:26,380
är att de har en pekare till en ny nod.

504
00:43:26,380 --> 00:43:30,820
Så vad är adressen till den nod kommer att peka på?

505
00:43:30,820 --> 00:43:34,550
Det adress kommer att bli new_node.

506
00:43:34,550 --> 00:43:42,140
Betyder det vettigt, varför vi gör new_node en nod * i motsats till en nod?

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

508
00:43:45,700 --> 00:43:52,840
Vi har ett ord. Detta värde är new_node-> ord.

509
00:43:52,840 --> 00:43:55,970
Som innehåller ord från ordlistan som vi vill mata in.

510
00:43:55,970 --> 00:44:00,210
Så vad vi vill göra är att vi vill kalla vårt hashfunktion på den strängen

511
00:44:00,210 --> 00:44:03,780
eftersom vår hashfunktionen tar in en sträng och returnerar sedan oss ett heltal,

512
00:44:03,780 --> 00:44:12,090
när denna heltal är index där Hashtable vid detta index representerar den hink.

513
00:44:12,090 --> 00:44:18,260
Vi vill ta detta index och sedan gå till detta index i hashtabellen

514
00:44:18,260 --> 00:44:26,960
och sedan använda den länkade listan för att sätta noden i new_node.

515
00:44:26,960 --> 00:44:31,950
Kom ihåg att hur du väljer att sätta in nod,

516
00:44:31,950 --> 00:44:34,370
oavsett om det är i mitten om du vill sortera

517
00:44:34,370 --> 00:44:39,650
eller i början eller i slutet, bara se till att din sista nod pekar alltid till NULL

518
00:44:39,650 --> 00:44:46,730
eftersom det är det enda sättet som vi vet var det sista elementet i vår länkad lista är.

519
00:44:50,790 --> 00:44:59,710
>> Om storleken är ett heltal som representerar antalet ord i ett lexikon,

520
00:44:59,710 --> 00:45:03,060
därefter ett sätt att göra detta är att när storleken kallas

521
00:45:03,060 --> 00:45:05,840
Vi går igenom varje element i vår hashtabell

522
00:45:05,840 --> 00:45:09,410
och sedan iterera igenom varje länkad lista i hash-tabellen

523
00:45:09,410 --> 00:45:13,770
och sedan beräkna längden på det, öka vår disk 1 av 1.

524
00:45:13,770 --> 00:45:16,580
Men varje gång som storleken heter, det är kommer att ta lång tid

525
00:45:16,580 --> 00:45:22,120
eftersom vi kommer att vara linjärt sondering varenda länkad lista.

526
00:45:22,120 --> 00:45:30,530
Istället kommer det att bli mycket enklare om du håller koll på hur många ord förs in

527
00:45:30,530 --> 00:45:36,330
Så då om du har en räknare i din last funktion

528
00:45:36,330 --> 00:45:42,430
att uppdateringar som behövs, sedan disk, om du ställer den till en global variabel,

529
00:45:42,430 --> 00:45:44,930
kommer att kunna nås av storlek.

530
00:45:44,930 --> 00:45:51,450
Så vilken storlek skulle helt enkelt göra är en linje, bara returnera räknarvärdet,

531
00:45:51,450 --> 00:45:55,500
storleken på ordlistan som du redan behandlats i lasten.

532
00:45:55,500 --> 00:46:05,190
Det är vad jag menade när jag sa att om du implementerar last i ett användbart sätt,

533
00:46:05,190 --> 00:46:08,540
då storleken kommer att bli ganska lätt.

534
00:46:08,540 --> 00:46:11,350
>> Så nu får vi se.

535
00:46:11,350 --> 00:46:15,960
Nu är vi har att göra med ord från den ingående textfil,

536
00:46:15,960 --> 00:46:19,910
och så vi kommer att kontrollera om alla dessa ingångsord

537
00:46:19,910 --> 00:46:22,520
är faktiskt i ordlistan eller inte.

538
00:46:22,520 --> 00:46:26,520
I likhet med Scramble vill vi möjliggöra för fall okänslighet.

539
00:46:26,520 --> 00:46:32,110
Du vill vara säker på att alla ord gick in, trots att de är gemener,

540
00:46:32,110 --> 00:46:37,840
när kallas med snöre jämföra, är likvärdiga.

541
00:46:37,840 --> 00:46:42,450
Orden i filerna ordbok texten är faktiskt gemener.

542
00:46:42,450 --> 00:46:49,280
En annan sak är att du kan räkna med att varje ord passerade, varje sträng,

543
00:46:49,280 --> 00:46:53,200
kommer att vara antingen alfabetisk eller innehålla apostrofer.

544
00:46:53,200 --> 00:46:58,010
Apostrofer kommer att vara giltiga ord i vår ordlista.

545
00:46:58,010 --> 00:47:06,470
Så om du har ett ord med apostrof S, det är en verklig legitim ord i din ordlista

546
00:47:06,470 --> 00:47:11,650
det kommer att bli en av noderna i ditt hashtabell.

547
00:47:13,470 --> 00:47:18,350
Kontrollera arbetar med om ordet finns, så det måste vara i vår hashtabell.

548
00:47:18,350 --> 00:47:22,210
Om ordet är i ordlistan, då alla ord i ordboken är i hash-tabellen,

549
00:47:22,210 --> 00:47:26,560
så låt oss titta på detta ord i hashtabellen.

550
00:47:26,560 --> 00:47:29,250
Vi vet att eftersom vi genomfört vår hashfunktion

551
00:47:29,250 --> 00:47:38,420
så att varje unikt ord alltid hashas till samma värde,

552
00:47:38,420 --> 00:47:43,340
då vet vi att i stället för att söka igenom hela vår hela hashtabell,

553
00:47:43,340 --> 00:47:48,310
Vi kan faktiskt hitta den länkade lista som det ordet skulle tillhöra.

554
00:47:48,310 --> 00:47:51,850
Om det var i ordlistan så skulle det vara i den hink.

555
00:47:51,850 --> 00:47:57,140
Vad vi kan göra, om ordet är namnet på vår sträng som skickas in,

556
00:47:57,140 --> 00:48:01,560
Vi kan bara hash att ord och titta på den länkade listan

557
00:48:01,560 --> 00:48:06,410
på värdet av Hashtable [hash (ord)].

558
00:48:06,410 --> 00:48:12,410
Därifrån, vad vi kan göra är att vi har en mindre delmängd av noder för att söka efter detta ord,

559
00:48:12,410 --> 00:48:16,770
och så att vi kan gå igenom den länkade listan, med hjälp av ett exempel från tidigare i genomgången,

560
00:48:16,770 --> 00:48:24,110
och sedan ringa sträng jämföra på ordet där markören pekar på,

561
00:48:24,110 --> 00:48:28,430
det ordet, och se om de jämföra.

562
00:48:30,280 --> 00:48:35,110
Beroende på hur du organiserar din hashfunktion,

563
00:48:35,110 --> 00:48:39,260
om det är sorterade, kanske du kan returnera false lite tidigare,

564
00:48:39,260 --> 00:48:43,440
men om det är osorterat, då du vill fortsätta gå igenom igenom länkad lista

565
00:48:43,440 --> 00:48:46,480
tills du hittar den sista delen av listan.

566
00:48:46,480 --> 00:48:53,320
Och om du fortfarande inte har hittat ordet med den tid du har nått slutet av den länkade listan,

567
00:48:53,320 --> 00:48:56,890
som innebär att dina ord inte finns i ordlistan,

568
00:48:56,890 --> 00:48:59,410
och så att ordet är ogiltig,

569
00:48:59,410 --> 00:49:02,730
och kontroll ska returnera false.

570
00:49:02,730 --> 00:49:09,530
>> Nu kommer vi till lasta, där vi vill befria alla de noder som vi har malloc'd,

571
00:49:09,530 --> 00:49:14,050
så fri alla noder inom vår hashtabell.

572
00:49:14,050 --> 00:49:20,270
Vi kommer att vilja iterera över alla länkade listor och fria alla noder i det.

573
00:49:20,270 --> 00:49:29,350
Om du tittar ovan i genomgången till exempel där vi frigöra en länkad lista,

574
00:49:29,350 --> 00:49:35,140
då du kommer att vilja upprepa denna process för varje element i hash tabellen.

575
00:49:35,140 --> 00:49:37,780
Och jag ska gå över detta i slutet av genomgång,

576
00:49:37,780 --> 00:49:46,600
men Valgrind är ett verktyg där du kan se om du har rätt befriat

577
00:49:46,600 --> 00:49:53,600
Varje nod som du har malloc'd eller något annat som du har malloc'd, någon annan pekare.

578
00:49:55,140 --> 00:50:00,530
Så det är hashtabeller, där vi har ett begränsat antal skopor

579
00:50:00,530 --> 00:50:09,220
och en hashfunktion som tar ett värde och sedan tilldela det värdet till en viss hink.

580
00:50:09,220 --> 00:50:13,340
>> Nu kommer vi till försök.

581
00:50:13,340 --> 00:50:18,750
Försöker typ av ser ut så här, och jag kommer även dra ut ett exempel.

582
00:50:18,750 --> 00:50:25,630
I grunden har du en hel rad potentiella bokstäver,

583
00:50:25,630 --> 00:50:29,210
och sedan när du bygger ett ord,

584
00:50:29,210 --> 00:50:36,490
skrivelsen kan kopplas till en ordlista till ett brett utbud av möjligheter.

585
00:50:36,490 --> 00:50:40,840
Några ord börjar med C men sedan fortsätta med,

586
00:50:40,840 --> 00:50:42,960
men andra fortsätter med O, till exempel.

587
00:50:42,960 --> 00:50:51,090
En trie är ett sätt att visualisera alla de möjliga kombinationer av dessa ord.

588
00:50:51,090 --> 00:50:59,070
En trie kommer att hålla reda på den sekvens av bokstäver som utgör ord,

589
00:50:59,070 --> 00:51:08,280
förgreningar vid behov, när en bokstav kan följas av en multipel av bokstäver,

590
00:51:08,280 --> 00:51:16,630
och vid slutet visar vid varje punkt om det ordet är giltigt eller inte

591
00:51:16,630 --> 00:51:30,120
för om du stava ordet MAT, MA Jag tror inte ett giltigt ord, men mattan.

592
00:51:30,120 --> 00:51:37,820
Och så i trie, skulle det tyda på att efter MAT det är faktiskt ett giltigt ord.

593
00:51:41,790 --> 00:51:48,590
Varje nod i vår trie faktiskt kommer att innehålla en rad noder pekare,

594
00:51:48,590 --> 00:51:52,970
och vi kommer att ha, särskilt 27 av dessa noder pekare,

595
00:51:52,970 --> 00:52:00,550
en för varje bokstav i alfabetet samt apostrof tecken.

596
00:52:00,550 --> 00:52:10,450
Varje element i matrisen är själv kommer att peka till en annan nod.

597
00:52:10,450 --> 00:52:14,020
Så om den noden är NULL, om det inte finns något efter det,

598
00:52:14,020 --> 00:52:20,550
då vet vi att det inte finns några ytterligare bokstäver i det ordet sekvens.

599
00:52:20,550 --> 00:52:26,950
Men om den noden inte är NULL, innebär det att det finns fler bokstäver i detta brev sekvens.

600
00:52:26,950 --> 00:52:32,160
Och sedan vidare indikerar varje nod om det är det sista tecknet i ett ord eller inte.

601
00:52:38,110 --> 00:52:43,170
>> Låt oss gå in ett exempel på en trie.

602
00:52:50,500 --> 00:52:58,340
Först har jag plats för 27 noder i denna array.

603
00:52:58,340 --> 00:53:03,200
Om jag har ordet BAR -

604
00:53:13,310 --> 00:53:15,370
Om jag har ordet bar och jag vill infoga det i,

605
00:53:15,370 --> 00:53:22,700
den första bokstaven är B, så om min trie är tom,

606
00:53:22,700 --> 00:53:29,910
B är den andra bokstaven i alfabetet, så jag ska välja att sätta detta här på detta index.

607
00:53:29,910 --> 00:53:33,450
Jag ska ha B här.

608
00:53:33,450 --> 00:53:42,400
B kommer att vara en nod som pekar på en annan uppsättning av alla möjliga tecken

609
00:53:42,400 --> 00:53:45,870
som kan följa efter bokstaven B.

610
00:53:45,870 --> 00:53:57,610
I det här fallet, jag arbetar med ordet bar, så en kommer att gå hit.

611
00:54:02,000 --> 00:54:08,990
Efter en, jag har bokstaven R, så då en nu pekar på sin egen kombination,

612
00:54:08,990 --> 00:54:15,120
och då R kommer att vara här.

613
00:54:15,120 --> 00:54:22,470
BAR är en komplett ord, så då kommer jag att ha R-punkten till en annan nod

614
00:54:22,470 --> 00:54:33,990
som säger att detta ord är giltig.

615
00:54:36,010 --> 00:54:40,970
Denna nod kommer även att ha en mängd noder,

616
00:54:40,970 --> 00:54:45,260
men de kan vara NULL.

617
00:54:45,260 --> 00:54:49,080
Men i grunden kan det fortsätta så.

618
00:54:49,080 --> 00:54:54,250
Det kommer att bli lite tydligare när vi går till en annan exempel,

619
00:54:54,250 --> 00:54:56,780
så bara bära med mig där.

620
00:54:56,780 --> 00:55:02,050
Nu har vi BAR inne i vår ordlista.

621
00:55:02,050 --> 00:55:05,980
Nu säger vi ordet BAZ.

622
00:55:05,980 --> 00:55:12,630
Vi börjar med B, och vi har redan B som en av de bokstäver som finns i vår ordlista.

623
00:55:12,630 --> 00:55:15,170
Det är följt med A. Vi har en redan.

624
00:55:15,170 --> 00:55:19,250
Men då istället har vi Z-följande.

625
00:55:19,250 --> 00:55:25,490
Så då ett element i vår array kommer att bli Z,

626
00:55:25,490 --> 00:55:30,810
och så att då man kommer att peka på en annan giltig slutet av ordet.

627
00:55:30,810 --> 00:55:36,930
Så vi ser att när vi fortsätter till B och sedan A,

628
00:55:36,930 --> 00:55:43,480
Det finns två olika alternativ för närvarande i vår ordlista för ord som börjar med B och A.

629
00:55:49,650 --> 00:55:57,460
Säg att vi ville infoga ordet Foobar.

630
00:55:57,460 --> 00:56:05,620
Då skulle vi göra en post på F.

631
00:56:05,620 --> 00:56:11,320
F är en nod som pekar till en hel rad.

632
00:56:11,320 --> 00:56:22,790
Vi skulle hitta O, gå till O, länkar O sedan till en hel lista.

633
00:56:22,790 --> 00:56:35,340
Vi skulle ha B och sedan fortsätta, skulle vi ha A och sedan R.

634
00:56:35,340 --> 00:56:43,570
Så då Foobar korsar hela vägen ner tills foobar är en korrekt ord.

635
00:56:43,570 --> 00:56:52,590
Och så skulle detta vara ett giltigt ord.

636
00:56:52,590 --> 00:57:00,170
Nu säger vår nästa ord i ordlistan är faktiskt ordet FOO.

637
00:57:00,170 --> 00:57:03,530
Vi skulle säga F. Vad följer F?

638
00:57:03,530 --> 00:57:06,190
Jag har faktiskt redan har en plats för O, så jag kommer att fortsätta.

639
00:57:06,190 --> 00:57:09,150
Jag behöver inte göra en ny. Fortsätt.

640
00:57:09,150 --> 00:57:15,500
FOO är ett giltigt ord i ordlistan, så då kommer jag att visa

641
00:57:15,500 --> 00:57:21,660
att det är giltigt.

642
00:57:21,660 --> 00:57:28,370
Om jag slutar min sekvens där, det skulle vara korrekt.

643
00:57:28,370 --> 00:57:33,050
Men om vi fortsatte vår sekvens från FOO ner till B

644
00:57:33,050 --> 00:57:39,750
och bara hade FOOB är FOOB inte ett ord, och det är inte anges som en giltig.

645
00:57:47,370 --> 00:57:57,600
I en trie har du varje nod anger om det är ett giltigt ord eller inte,

646
00:57:57,600 --> 00:58:05,840
och sedan varje nod har också en rad 27 noder pekare

647
00:58:05,840 --> 00:58:09,520
att peka på noder själva.

648
00:58:09,520 --> 00:58:12,940
>> Här är ett sätt på hur du kan vill definiera detta.

649
00:58:12,940 --> 00:58:17,260
Men precis som i hash tabellen exempel, där vi hade en nod * huvud

650
00:58:17,260 --> 00:58:21,320
för att indikera början av vår länkad lista, vi kommer också att vilja

651
00:58:21,320 --> 00:58:29,150
något sätt att veta var i början av vår Trie är.

652
00:58:29,150 --> 00:58:34,110
En del kallar försöker träd, och det är där roten kommer ifrån.

653
00:58:34,110 --> 00:58:36,910
Så vi vill roten av vårt träd att se till att vi håller oss jordade

654
00:58:36,910 --> 00:58:39,570
dit vår Trie är.

655
00:58:42,910 --> 00:58:46,300
Vi har redan typ av gick över

656
00:58:46,300 --> 00:58:50,240
hur du kan tänka om hur du fyller varje ord i ordlistan.

657
00:58:50,240 --> 00:58:54,540
Huvudsak för varje ord du kommer att vilja iterera igenom Trie

658
00:58:54,540 --> 00:58:59,590
och att veta att varje element i barnen - vi kallade det barn i detta fall -

659
00:58:59,590 --> 00:59:04,290
motsvarar en annan bokstav, du kommer att vilja kontrollera de värden

660
00:59:04,290 --> 00:59:08,320
vid det visst index som motsvarar bokstaven.

661
00:59:08,320 --> 00:59:11,260
Så tänker hela vägen tillbaka till Caesar och Vigenère,

662
00:59:11,260 --> 00:59:16,070
att veta att varje bokstav du typ av karta tillbaka till ett kartotek,

663
00:59:16,070 --> 00:59:20,690
definitivt A till Z kommer att bli ganska lätt att mappa till ett alfabetiskt brev,

664
00:59:20,690 --> 00:59:25,200
men tyvärr apostrofer också en accepterad karaktär i ord.

665
00:59:25,200 --> 00:59:31,650
Jag är inte ens säker på vad det ASCII-värdet är,

666
00:59:31,650 --> 00:59:39,250
så för att om du vill hitta ett index för att avgöra om du vill att det ska vara antingen den första

667
00:59:39,250 --> 00:59:44,550
eller den sista, måste du göra en hård kodad kontroll för att

668
00:59:44,550 --> 00:59:48,930
och sedan lägga det i index 26, till exempel.

669
00:59:48,930 --> 00:59:55,300
Så då du checkar värdet till barn [i]

670
00:59:55,300 --> 00:59:58,400
där [i] motsvarar vad bokstav du är på.

671
00:59:58,400 --> 01:00:04,110
Om det är NULL, innebär att det för närvarande inte eventuella bokstäver

672
01:00:04,110 --> 01:00:08,150
härrör från den tidigare sekvens, så du kommer att vilja malloc

673
01:00:08,150 --> 01:00:13,150
och gör en ny nod och har som barn [i] pekar på det

674
01:00:13,150 --> 01:00:17,890
så att du skapar - när vi in ​​ett brev i rektangeln -

675
01:00:17,890 --> 01:00:23,680
göra barn utan NULL och peka in i den nya noden.

676
01:00:23,680 --> 01:00:28,340
Men om det inte är NULL, som i vår instans av FOO

677
01:00:28,340 --> 01:00:34,570
när vi redan hade foobar fortsätter vi,

678
01:00:34,570 --> 01:00:44,010
och vi inte någonsin göra en ny nod utan bara sätta is_word till true

679
01:00:44,010 --> 01:00:47,790
vid slutet av detta ord.

680
01:00:50,060 --> 01:00:55,340
>> Alltså som tidigare, för här har att göra med varje bokstav i taget,

681
01:00:55,340 --> 01:01:01,470
det kommer att bli lättare för dig för storlek, i stället för att beräkna

682
01:01:01,470 --> 01:01:06,910
och gå igenom hela trädet och beräkna hur många barn har jag

683
01:01:06,910 --> 01:01:10,850
och därefter förgreningar, komma ihåg hur många är på vänster sida och på höger sida

684
01:01:10,850 --> 01:01:12,850
och sådana saker, det kommer att bli mycket lättare för dig

685
01:01:12,850 --> 01:01:16,220
Om du bara hålla reda på hur många ord du lägger i

686
01:01:16,220 --> 01:01:18,080
När du arbetar med belastning.

687
01:01:18,080 --> 01:01:22,630
Och så då det sättet storlek kan bara returnera en global variabel storlek.

688
01:01:25,320 --> 01:01:28,530
>> Nu kommer vi att kontrollera.

689
01:01:28,530 --> 01:01:33,920
Samma normer som tidigare, där vi vill att möjliggöra fall okänslighet.

690
01:01:33,920 --> 01:01:40,400
Liksom, antar vi att strängarna är endast alfabetiska tecken eller apostrofer

691
01:01:40,400 --> 01:01:44,000
eftersom barn är en array med 27 lång,

692
01:01:44,000 --> 01:01:48,480
så alla bokstäver i alfabetet plus apostrof.

693
01:01:48,480 --> 01:01:53,800
För kolla vad du vill göra är att du vill starta vid roten

694
01:01:53,800 --> 01:01:58,440
eftersom roten pekar på en array som innehåller

695
01:01:58,440 --> 01:02:01,630
alla möjliga start bokstäverna i ett ord.

696
01:02:01,630 --> 01:02:03,680
Du kommer att börja där,

697
01:02:03,680 --> 01:02:11,590
och då du kommer att kontrollera är detta värde NULL eller inte,

698
01:02:11,590 --> 01:02:16,490
eftersom om värdet är NULL, innebär detta att ordboken inte har några värden

699
01:02:16,490 --> 01:02:21,480
som innehåller den bokstaven i den aktuella ordningen.

700
01:02:21,480 --> 01:02:24,970
Om det är NULL, då det innebär att ordet är felstavat direkt.

701
01:02:24,970 --> 01:02:27,110
Men om det inte är NULL, då kan du fortsätta

702
01:02:27,110 --> 01:02:34,090
säga att första bokstaven är en möjlig första bokstaven i ett ord,

703
01:02:34,090 --> 01:02:40,630
så nu vill jag kolla om den andra bokstaven, den sekvensen, är inom min ordbok.

704
01:02:40,630 --> 01:02:46,540
Så du kommer att gå till indexet för barnen i den första noden

705
01:02:46,540 --> 01:02:50,720
och kontrollera om den andra bokstaven finns.

706
01:02:50,720 --> 01:02:57,440
Då du upprepa denna process för att kontrollera om den sekvensen är giltigt eller inte

707
01:02:57,440 --> 01:02:59,060
i din Trie.

708
01:02:59,060 --> 01:03:06,430
När noden barn på att indexpunkter till NULL,

709
01:03:06,430 --> 01:03:10,710
du vet att den sekvensen inte finns,

710
01:03:10,710 --> 01:03:16,230
men om du når slutet av ordet som du har matas in,

711
01:03:16,230 --> 01:03:20,070
då du vill kontrollera nu när jag har slutfört denna sekvens

712
01:03:20,070 --> 01:03:27,610
och fann det i min trie är detta ord giltigt eller inte?

713
01:03:27,610 --> 01:03:32,480
Och så då du vill kontrollera det, och det är då om du har hittat den sekvensen,

714
01:03:32,480 --> 01:03:35,120
då du vill kontrollera om det ordet är giltigt eller inte

715
01:03:35,120 --> 01:03:40,290
eftersom minns tillbaka i det tidigare fallet som jag drog där vi hade FOOB,

716
01:03:40,290 --> 01:03:48,410
Det var ett giltigt sekvens som vi hittat, men var inte en verklig giltigt ord i sig.

717
01:03:50,570 --> 01:03:59,000
>> Likaså för lasta i försök som du vill lasta alla noder i Trie.

718
01:03:59,000 --> 01:04:04,790
Ursäkta. I likhet med hashtabeller var i lasta vi frigjort alla noder,

719
01:04:04,790 --> 01:04:09,740
i försök vi vill också frigöra alla noder.

720
01:04:09,740 --> 01:04:15,000
Lasta faktiskt kommer att arbeta lättast från botten till toppen

721
01:04:15,000 --> 01:04:19,290
eftersom dessa är i huvudsak länkade listor.

722
01:04:19,290 --> 01:04:22,540
Så vi vill se till att vi håller fast vid alla värden

723
01:04:22,540 --> 01:04:25,700
och fri dem alla explicit.

724
01:04:25,700 --> 01:04:28,840
Vad du kommer att vilja göra om du arbetar med en trie

725
01:04:28,840 --> 01:04:35,640
är att resa till botten och fri lägsta möjliga noden 1.

726
01:04:35,640 --> 01:04:39,190
och sedan gå upp till alla dessa barn och sedan fri alla dem,

727
01:04:39,190 --> 01:04:43,050
gå upp och sedan fri etc.

728
01:04:43,050 --> 01:04:48,790
Ungefär som att hantera bottenskiktet av trie 1.

729
01:04:48,790 --> 01:04:51,940
och sedan gå upp topp när du har befriat allt.

730
01:04:51,940 --> 01:04:56,720
Detta är ett bra exempel på när rekursiv funktion kan komma till hands.

731
01:04:56,720 --> 01:05:03,830
När du har frigjort den nedre lagret av Trie,

732
01:05:03,830 --> 01:05:08,000
då du ringer lasta på resten av det,

733
01:05:08,000 --> 01:05:13,620
se till att du gratis varje mini -

734
01:05:13,620 --> 01:05:16,410
Du kan slags visualisera det som mini försök.

735
01:05:23,300 --> 01:05:28,990
Så du har din rot här.

736
01:05:30,840 --> 01:05:35,230
Jag bara förenkla det så jag inte behöver dra 26 av dem.

737
01:05:37,250 --> 01:05:43,770
Så du har dessa, och då dessa representerar sekvenser av ord

738
01:05:43,770 --> 01:05:54,620
där alla dessa små cirklar är bokstäver som är giltiga sekvenser av bokstäver.

739
01:06:03,040 --> 01:06:07,160
Låt oss fortsätta bara lite mer.

740
01:06:15,110 --> 01:06:25,750
Vad du kommer att vilja göra är gratis botten här och sedan fri detta en

741
01:06:25,750 --> 01:06:31,640
och sedan fritt här i botten innan du frigör den övre upp här

742
01:06:31,640 --> 01:06:38,180
för om du fri något i den andra nivån här,

743
01:06:38,180 --> 01:06:47,230
då du faktiskt skulle förlora detta värde här.

744
01:06:47,230 --> 01:06:54,780
Det är därför det är viktigt i lasta en trie att se till att du frigöra botten först.

745
01:06:54,780 --> 01:06:59,480
Vad du kanske vill göra är att säga för varje nod

746
01:06:59,480 --> 01:07:06,430
Jag vill lasta alla barn.

747
01:07:16,060 --> 01:07:22,140
>> Nu när vi har gått över lasta för hashtabellen metoden samt trie metoden,

748
01:07:22,140 --> 01:07:27,020
vi kommer att vilja titta på Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind kör du med följande kommandon.

750
01:07:29,640 --> 01:07:32,700
Du har Valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Du kollar på alla läckor när du kör speller gett denna viss text

752
01:07:40,960 --> 01:07:46,980
eftersom speller måste ta i en textfil.

753
01:07:46,980 --> 01:07:52,330
Så Valgrind kommer att köra ditt program, berätta hur många byte man tilldelats,

754
01:07:52,330 --> 01:07:57,150
hur många byte man befriade, och det kommer att berätta om du befriad lagom

755
01:07:57,150 --> 01:07:58,930
eller om du inte tillräckligt fri,

756
01:07:58,930 --> 01:08:02,850
eller ibland kan du även över-fri, liksom gratis en nod som redan har befriats

757
01:08:02,850 --> 01:08:05,140
och så kommer du tillbaka fel.

758
01:08:05,140 --> 01:08:11,600
Om du använder Valgrind, kommer det att ge dig några meddelanden

759
01:08:11,600 --> 01:08:15,970
anger om du har befriat antingen mindre än tillräckligt, bara tillräckligt,

760
01:08:15,970 --> 01:08:19,609
eller mer än tillräckligt många gånger.

761
01:08:24,370 --> 01:08:30,410
>> En del av denna pset är det frivilligt att utmana de stora styrelsen.

762
01:08:30,410 --> 01:08:35,790
Men när vi har att göra med dessa datastrukturer

763
01:08:35,790 --> 01:08:40,689
Det är ganska kul att se hur snabbt och hur effektivt dina datastrukturer skulle kunna vara.

764
01:08:40,689 --> 01:08:44,490
Har din hashfunktion resulterar i en massa kollisioner?

765
01:08:44,490 --> 01:08:46,300
Eller är din datastorlek riktigt stora?

766
01:08:46,300 --> 01:08:49,420
Tar det mycket tid att korsa?

767
01:08:49,420 --> 01:08:54,800
I loggen för stavningskontroll matar det hur mycket tid du använder för att ladda,

768
01:08:54,800 --> 01:08:57,700
att kontrollera, att genomföra storlek och att lasta,

769
01:08:57,700 --> 01:09:00,720
och så de är postade i The Big Board,

770
01:09:00,720 --> 01:09:03,600
där du kan tävla mot dina klasskamrater

771
01:09:03,600 --> 01:09:11,350
och vissa anställda att se vem som har den snabbaste stavningskontrollen.

772
01:09:11,350 --> 01:09:14,760
En sak som jag skulle vilja att notera om hashtabeller

773
01:09:14,760 --> 01:09:20,470
är att det finns några ganska enkla hash funktioner som vi kan tänka på.

774
01:09:20,470 --> 01:09:27,240
Till exempel, du har 26 hinkar och så varje skopa

775
01:09:27,240 --> 01:09:30,200
motsvarar den första bokstaven i ett ord,

776
01:09:30,200 --> 01:09:35,229
men det kommer att resultera i en ganska obalanserad hash-tabell

777
01:09:35,229 --> 01:09:40,979
eftersom det är mycket mindre ord som börjar med X än start med M, till exempel.

778
01:09:40,979 --> 01:09:47,890
Ett sätt att gå speller är om du vill få alla andra funktioner nedåt,

779
01:09:47,890 --> 01:09:53,240
sedan bara använda en enkel hashfunktion för att kunna få din kod körs

780
01:09:53,240 --> 01:09:58,650
och sedan gå tillbaka och ändra storleken på din hashtabell och definitionen.

781
01:09:58,650 --> 01:10:03,430
Det finns en hel del resurser på Internet för hash funktioner,

782
01:10:03,430 --> 01:10:08,250
och så för denna pset du får forska hashfunktioner på Internet

783
01:10:08,250 --> 01:10:15,560
för några tips och inspiration så länge du uppge var du fick det ifrån.

784
01:10:15,560 --> 01:10:22,060
Du är välkommen att titta och tolka några hashfunktion som du hittar på Internet.

785
01:10:22,060 --> 01:10:27,460
Tillbaka till det, kanske du kan se om någon använt en trie

786
01:10:27,460 --> 01:10:31,700
om deras genomförande är snabbare än din hashtabell eller inte.

787
01:10:31,700 --> 01:10:35,290
Du kan skicka till The Big Board flera gånger.

788
01:10:35,290 --> 01:10:37,660
Det kommer att spela din senaste inmatning.

789
01:10:37,660 --> 01:10:44,300
Så kanske du ändrar din hashfunktion och sedan inser att det faktiskt är mycket snabbare

790
01:10:44,300 --> 01:10:46,780
eller mycket långsammare än tidigare.

791
01:10:46,780 --> 01:10:50,960
Det är lite av ett roligt sätt.

792
01:10:50,960 --> 01:10:57,190
Det finns alltid 1 eller 2 anställda som försöker göra den långsammaste möjliga ordlistan

793
01:10:57,190 --> 01:11:00,210
så det är alltid kul att titta på.

794
01:11:00,210 --> 01:11:07,630
>> Användningen för pset är du köra speller med en valfri ordbok

795
01:11:07,630 --> 01:11:12,840
och sedan en obligatorisk textfil.

796
01:11:12,840 --> 01:11:18,380
Som standard när du kör speller med bara en textfil och inte anger en ordbok,

797
01:11:18,380 --> 01:11:24,410
det kommer att använda filen ordlistan texten, den stora en

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

799
01:11:27,920 --> 01:11:32,760
Att man har över 100.000 ord.

800
01:11:32,760 --> 01:11:37,950
De har också en liten ordlista som har betydligt mindre ord

801
01:11:37,950 --> 01:11:40,730
som CS50 har gjort för dig.

802
01:11:40,730 --> 01:11:44,050
Du kan dock enkelt bara göra din egen ordlista

803
01:11:44,050 --> 01:11:47,150
Om du bara vill att arbeta i små exempel -

804
01:11:47,150 --> 01:11:51,140
till exempel om du vill använda gdb och du vet de specifika värden

805
01:11:51,140 --> 01:11:53,560
att du vill att din hashtabell att kartlägga till.

806
01:11:53,560 --> 01:12:00,430
Så du bara kan göra din egen textfil bara med bar, BAZ, FOO och Foobar,

807
01:12:00,430 --> 01:12:04,860
göra det i en textfil, separera dem med vardera 1 rad,

808
01:12:04,860 --> 01:12:12,670
och sedan göra en egen textfil som bokstavligen bara innehåller kanske 1 eller 2 ord

809
01:12:12,670 --> 01:12:15,950
så att du vet exakt vad utgången ska vara.

810
01:12:15,950 --> 01:12:21,870
Några av filerna prov text som The Big Board när du kör utmaning kommer att kontrollera

811
01:12:21,870 --> 01:12:25,580
är Krig och fred och en Jane Austen roman eller något liknande.

812
01:12:25,580 --> 01:12:30,450
Så när du har börjat, är det mycket lättare att göra dina egna textfiler

813
01:12:30,450 --> 01:12:34,160
som innehåller bara ett par ord eller kanske 10

814
01:12:34,160 --> 01:12:38,280
så att du kan förutsäga vad resultatet ska

815
01:12:38,280 --> 01:12:42,880
och sedan kontrollera den mot det, så mer av en kontrollerad exempel.

816
01:12:42,880 --> 01:12:45,820
Och så eftersom vi har att göra med att förutse och rita saker runt,

817
01:12:45,820 --> 01:12:48,690
igen jag vill uppmuntra dig att använda penna och papper

818
01:12:48,690 --> 01:12:50,700
eftersom det verkligen kommer att hjälpa dig med detta -

819
01:12:50,700 --> 01:12:55,620
dra pilarna, hur hash tabellen eller hur Trie ser ut,

820
01:12:55,620 --> 01:12:57,980
när du frigöra något där pilarna är på väg,

821
01:12:57,980 --> 01:13:01,730
håller du på att tillräckligt, ser du några länkar försvinner

822
01:13:01,730 --> 01:13:05,750
och faller ner i avgrunden av läckt minne.

823
01:13:05,750 --> 01:13:11,070
Så snälla, försök att dra ut saker redan innan du kommer att skriva kod ner.

824
01:13:11,070 --> 01:13:14,520
Rita saker så att du förstår hur det går att arbeta

825
01:13:14,520 --> 01:13:22,750
för då jag garanterar att du kommer stöta på mindre pekaren dramatiska förändringar där.

826
01:13:24,270 --> 01:13:25,910
>> Okej.

827
01:13:25,910 --> 01:13:28,780
Jag vill önska er lycka till med detta pset.

828
01:13:28,780 --> 01:13:31,980
Det är nog den svåraste en.

829
01:13:31,980 --> 01:13:40,360
Så försök att börja tidigt, dra ut saker, dra ut saker, och lycka till.

830
01:13:40,360 --> 01:13:42,980
Detta var Genomgång 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]