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 - Harvard University]

3
00:00:04,870 --> 00:00:07,190
[To je CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> V redu. Pozdravljeni, vsi, in dobrodošli Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 je napačno črkovane besede, v kateri bomo izdelavo črkovalnik.

6
00:00:17,400 --> 00:00:21,030
Črkovanje dama zelo pomembna.

7
00:00:21,030 --> 00:00:23,390
Se je to že kdaj zgodilo?

8
00:00:23,390 --> 00:00:27,170
Delaš zelo, zelo depoju na papir za spopad

9
00:00:27,170 --> 00:00:33,120
in potem še na koncu dobili zelo svetijo Rade kot D ali D =

10
00:00:33,120 --> 00:00:39,390
in zato, ker ste liverwurst spojler na kita široko besedo.

11
00:00:39,390 --> 00:00:44,710
Ja, lektoriranje vaše paprike je stvar, izredno impotenca.

12
00:00:44,710 --> 00:00:49,140
To je problem, ki vpliva na Manly, Manly študentov.

13
00:00:49,140 --> 00:00:56,260
Bil sem nekoč povedal moj mučitelja razreda Sith, da ne bi prišli v dobri kolega.

14
00:00:56,260 --> 00:01:00,250
In to je vse, kar sem si želela, da je vse, vsak otrok želi v moji starosti,

15
00:01:00,250 --> 00:01:04,569
samo da bi prišel v dobri kolega.

16
00:01:04,569 --> 00:01:12,720
In ne samo kakršne koli kolega. Ne želim iti v pravni kolega Slonokoščena.

17
00:01:12,720 --> 00:01:18,360
Torej, če nisem izboljšanja, bi šel lahko moje sanje gre na Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, ali zapor - saj veste, v zaporu, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Tako sem dobil sam črkovalnik.

20
00:01:25,170 --> 00:01:29,380
To je malo odlomek iz enega od mojih najljubših umetnikov govorjene besede, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Kakorkoli že, kot pravi, treba imeti črkovalnika je zelo pomembno.

22
00:01:34,630 --> 00:01:39,440
>> Torej, dobrodošli na Walkthrough 5, v kateri bomo govorili o pset5: zatipkanih besed,

23
00:01:39,440 --> 00:01:44,300
v katerem bomo lahko kar samega črkovalnika.

24
00:01:44,300 --> 00:01:50,880
Toolbox za ta teden, distribucija kodo, se bo treba pogledati

25
00:01:50,880 --> 00:01:54,950
Samo razumeti različne funkcije, ki jih vaš slovar bo imel.

26
00:01:54,950 --> 00:02:01,500
Mi smo dejansko dogaja, da se ob več. Files C, ki skupaj tvorijo naše pset.

27
00:02:01,500 --> 00:02:05,420
In tako je videti skozi različne vidike, čeprav smo dejansko ne urejanje

28
00:02:05,420 --> 00:02:10,770
eno od datotek, speller.c, ne vedo, kako se dela z zvezi z dictionary.c,

29
00:02:10,770 --> 00:02:14,100
kar bomo pisali, se bo zelo pomemben.

30
00:02:14,100 --> 00:02:16,970
Spec pset vsebuje tudi veliko koristnih informacij

31
00:02:16,970 --> 00:02:21,360
glede stvari, ki jih lahko predvidevamo, pravila in stvari, kot je ta,

32
00:02:21,360 --> 00:02:24,710
zato se prepričajte, da se glasi pset spec skrbno za nasvete.

33
00:02:24,710 --> 00:02:29,310
In ko ste v dvomih norme ali kaj podobnega, potem pa se vedno sklicujejo na pset spec

34
00:02:29,310 --> 00:02:31,550
ali Razprava.

35
00:02:31,550 --> 00:02:34,060
Ta pset bo zelo odvisna od kazalcev,

36
00:02:34,060 --> 00:02:37,890
zato želimo zagotoviti, da bomo razumeli razliko med dodajanjem zvezdic

37
00:02:37,890 --> 00:02:41,680
pred imenom kazalca in ampersands, kako jih osvoboditi, itd

38
00:02:41,680 --> 00:02:47,550
Torej bi kapitan kazalcev se bo zelo koristno za ta problem nizu.

39
00:02:47,550 --> 00:02:50,460
Gremo pogledati v povezanih seznamih malo več,

40
00:02:50,460 --> 00:02:57,790
kjer imamo elemente, ki ji pravimo vozlišča, ki imajo tako vrednost kot tudi kazalec

41
00:02:57,790 --> 00:03:02,520
na naslednje vozlišče, in tako v bistvu povezuje različne elemente, enega za drugim.

42
00:03:02,520 --> 00:03:07,190
Obstaja nekaj različnih možnosti izvajanja vašo dejansko slovar.

43
00:03:07,190 --> 00:03:13,150
Gremo pogledati v dveh glavnih metod, ki so razpršene tabele, nato pa poskuša.

44
00:03:13,150 --> 00:03:17,660
V obeh tistih, gre za neke vrste pojmom povezani seznam

45
00:03:17,660 --> 00:03:20,790
kjer ste elemente povezane med seboj.

46
00:03:20,790 --> 00:03:25,640
In tako bomo pogled nad tem, kako bi lahko bili sposobni delovati okoli povezanih seznamov,

47
00:03:25,640 --> 00:03:29,680
jih ustvarjajo, upravljajo v smislu, kako se, na primer, vstavite vanj vozlišče

48
00:03:29,680 --> 00:03:32,760
ali brez vseh vozliščih, kot tudi.

49
00:03:32,760 --> 00:03:34,740
V smislu sprostitve vozlišč, da je zelo pomembno

50
00:03:34,740 --> 00:03:37,700
da ko smo malloc pomnilnika, potem smo ga rešil.

51
00:03:37,700 --> 00:03:42,910
Zato želimo zagotoviti, da poteka noben kazalec unfreed, da nimamo nobenih spomin razpoka.

52
00:03:42,910 --> 00:03:48,330
Bomo uvesti orodje, imenovano Valgrind, ki teče svoj program

53
00:03:48,330 --> 00:03:52,260
in preveri, ali vse pomnilnika, ki ga dodeli nato osvobodil.

54
00:03:52,260 --> 00:03:59,080
Vaš pset le končana, ko deluje in ima polno funkcionalnost,

55
00:03:59,080 --> 00:04:03,990
ampak Valgrind vam pove, da niste našli nobenih spomin razpoka.

56
00:04:03,990 --> 00:04:06,690
Končno, pri tem pset, želim poudariti -

57
00:04:06,690 --> 00:04:11,360
Mislim, kot ponavadi, sem definitivno zagovornik uporabe svinčnik in papir za tvoj problem sklopov,

58
00:04:11,360 --> 00:04:14,840
ampak za tole, mislim, da je pero in papir, se bo še posebej pomembno,

59
00:04:14,840 --> 00:04:19,000
če želite, da se pripravi puščice, da stvari, in razumeti, kako stvari delujejo.

60
00:04:19,000 --> 00:04:24,440
Torej vsekakor poskušali uporabiti svinčnik in papir, da pripravi stvari, preden boste dobili kodiranje

61
00:04:24,440 --> 00:04:26,970
saj bi lahko dobil malo grdo.

62
00:04:26,970 --> 00:04:30,700
>> Najprej gremo v povezanih seznamih malo.

63
00:04:30,700 --> 00:04:35,510
Povezani seznami so sestavljeni iz vozlišč, kjer je vsako vozlišče ima vrednost, povezano z njim,

64
00:04:35,510 --> 00:04:39,810
kot tudi kazalec na naslednji vozel po njej.

65
00:04:39,810 --> 00:04:43,680
Nekaj ​​stvari pomembnih povezanih s seznamov, da moramo zapomniti

66
00:04:43,680 --> 00:04:48,810
kjer je naša prva vozlišče, nato pa, ko bomo vedeli, kje je prvi vozlišče,

67
00:04:48,810 --> 00:04:52,990
na ta način lahko dostopate do vozlišča, ki so prvi vozlišče kaže na

68
00:04:52,990 --> 00:04:55,850
in potem eno za to in tisto po tem.

69
00:04:55,850 --> 00:05:00,340
In potem zadnji element v vašem seznamu je povezana vozlišča na kazalec

70
00:05:00,340 --> 00:05:02,340
je vedno tekoč, da kaže na NULL.

71
00:05:02,340 --> 00:05:08,230
Ko vozlišče točk na NULL, potem veste, da ste prišli do konca seznama,

72
00:05:08,230 --> 00:05:12,320
vozlišče, da je zadnja, da ni nič po tem.

73
00:05:12,320 --> 00:05:16,970
Tu v tem shematično, boste videli, da so puščice so kazalci,

74
00:05:16,970 --> 00:05:20,290
in modri del, kjer je shranjena vrednost,

75
00:05:20,290 --> 00:05:24,420
nato pa rdeče polje s kazalcem, to je vozlišče je kazalec

76
00:05:24,420 --> 00:05:27,050
kaže na naslednje vozlišče po njej.

77
00:05:27,050 --> 00:05:33,730
In tako si lahko ogledate tukaj, bi vozlišče D kaže na NULL, ker je zadnji element na seznamu.

78
00:05:33,730 --> 00:05:38,240
>> Oglejmo si, kako lahko definiramo struct za vozlišče.

79
00:05:38,240 --> 00:05:40,130
In ker želimo imeti več vozlišč,

80
00:05:40,130 --> 00:05:43,180
to se dogaja, da postane typedef struct

81
00:05:43,180 --> 00:05:46,870
v katerem bomo imeli več različnih primerkov vozlišč.

82
00:05:46,870 --> 00:05:50,850
In tako smo jo opredeljuje kot novo vrsto podatkov.

83
00:05:50,850 --> 00:05:53,630
Tu imamo typedef struct vozlišče.

84
00:05:53,630 --> 00:05:56,160
V tem primeru imamo opravka s celo število vozlišč,

85
00:05:56,160 --> 00:06:00,490
tako da imamo celoštevilsko vrednost imenom in potem imamo še kazalec,

86
00:06:00,490 --> 00:06:07,390
in v tem primeru, je kazalec na vozlišče, tako da imamo struct * vozlišče, imenovano drugo.

87
00:06:07,390 --> 00:06:09,520
In potem kličeš ta stvar vozlišče.

88
00:06:09,520 --> 00:06:11,110
Poskrbite, da boste sledili tem sintakso.

89
00:06:11,110 --> 00:06:17,940
Obvestilo, da vozlišče je pravzaprav navaja tam zgoraj, kot tudi pod zavitih oklepajih.

90
00:06:17,940 --> 00:06:23,400
Potem, da bi spremljali, kje moj prvi vozlišče je v tem povezanega seznama,

91
00:06:23,400 --> 00:06:29,390
potem imam vozlišče, imenovano kazalec glava in sem malloc prostora dovolj za velikost vozlišča.

92
00:06:29,390 --> 00:06:36,240
Obvestilo pa je, da je vodja dejansko vozlišče kazalec v nasprotju z dejanskim vozlišču sama.

93
00:06:36,240 --> 00:06:40,130
Torej glava dejansko ne vsebuje nobene vrednosti,

94
00:06:40,130 --> 00:06:45,590
samo kar kaže na prvi vozel v mojem seznamu je povezano.

95
00:06:55,080 --> 00:06:58,340
>> Da bi dobili boljšo predstavo o povezanih seznamov, saj je zelo pomembno,

96
00:06:58,340 --> 00:07:02,220
slediti pazite, da boste ohranili verige,

97
00:07:02,220 --> 00:07:09,990
Rad pomislim, da je ljudi v skladu držala za roke,

98
00:07:09,990 --> 00:07:14,330
kjer je vsaka oseba, ki se držijo za roke z naslednjo.

99
00:07:14,330 --> 00:07:18,350
Ne morete videti v tej risbi, ampak v bistvu oni kažejo na naslednjo osebo

100
00:07:18,350 --> 00:07:23,760
, ki je v svoji verigi.

101
00:07:23,760 --> 00:07:29,270
In tako, če želite, da prečkanje povezan seznam, kjer so ti ljudje -

102
00:07:29,270 --> 00:07:32,830
predstavljate vse te ljudi, ki so vrednote, povezane z njimi

103
00:07:32,830 --> 00:07:36,590
in opozarjajo tudi na naslednjo osebo v liniji -

104
00:07:36,590 --> 00:07:40,810
Če želite prečkanje povezani seznam, na primer, bodisi urediti vrednosti

105
00:07:40,810 --> 00:07:42,830
ali poiščite vrednosti ali kaj podobnega,

106
00:07:42,830 --> 00:07:48,270
potem boste želeli, da kazalec na določeno osebo.

107
00:07:48,270 --> 00:07:52,670
Torej bomo imeli podatkov kazalec tipa vozlišča.

108
00:07:52,670 --> 00:07:55,580
Za ta primer, recimo, da kazalec.

109
00:07:55,580 --> 00:07:59,630
Drug pogost način poimenovati to bi iterator ali kaj podobnega

110
00:07:59,630 --> 00:08:05,130
ker je ponavljanjem več in dejansko premika, ki vozlišče, da je obrnjena k.

111
00:08:05,130 --> 00:08:14,410
To bo tukaj naš kazalec.

112
00:08:14,410 --> 00:08:20,180
Our kazalec se bo najprej opozoriti, da prvi element v našem seznamu.

113
00:08:20,180 --> 00:08:26,910
In kaj želimo storiti, je, da bomo v bistvu se nadaljuje kazalec,

114
00:08:26,910 --> 00:08:29,130
se gibljejo od strani do strani.

115
00:08:29,130 --> 00:08:33,409
V tem primeru želimo, da se premaknete na naslednji element v seznamu.

116
00:08:33,409 --> 00:08:38,480
Z nizi, kaj bi naredil, je, da bomo samo rekli, da smo povečali z indeksom 1.

117
00:08:38,480 --> 00:08:46,020
V tem primeru, kaj moramo storiti, je dejansko bil oseba, ki je to trenutno kaže, da je oseba,

118
00:08:46,020 --> 00:08:48,930
in da se bo naslednja vrednost.

119
00:08:48,930 --> 00:08:53,230
Torej, če je kazalec le kazalec vozlišče, potem tisto, kar želimo narediti

120
00:08:53,230 --> 00:08:56,320
je, da smo želeli, da bi dobili na vrednost, ki je kazalec kaže na.

121
00:08:56,320 --> 00:09:01,350
Želimo, da pridete do te vozlišče in potem, ko smo že pri tem vozlišču, kjer je bil, da je obrnjena k.

122
00:09:01,350 --> 00:09:05,820
Da bi prišli do dejanske vozlišču, da je kazalec kaže na,

123
00:09:05,820 --> 00:09:13,160
Ponavadi jo kažejo z (* kazalec).

124
00:09:13,160 --> 00:09:19,160
To bi vam dejansko vozlišče, ki je kazalec, ki kaže na.

125
00:09:19,160 --> 00:09:21,730
In potem po tem, kaj želimo storiti, je, da smo želeli dostop

126
00:09:21,730 --> 00:09:25,680
karkoli že to vozlišče prihodnjo vrednost.

127
00:09:25,680 --> 00:09:32,820
To storite tako, da omogočajo dostop do vrednosti notranjost struct, imamo dot operaterja.

128
00:09:32,820 --> 00:09:39,530
Torej bi bilo (* kazalec). Naslednjo.

129
00:09:39,530 --> 00:09:44,840
Ampak to je malo grdo, v smislu, da imajo nosilce okoli * kazalec,

130
00:09:44,840 --> 00:09:56,800
in tako smo zamenjati vso to izjavo z kazalec->.

131
00:09:56,800 --> 00:10:02,700
To je pomišljaj in nato več kot znak, da postanejo puščico.

132
00:10:02,700 --> 00:10:05,840
Kazalec-> naslednji.

133
00:10:05,840 --> 00:10:12,390
To bo dejansko dobili vozlišče, da se kazalec kaže. Ta vrednost je naslednje.

134
00:10:12,390 --> 00:10:16,790
Torej, namesto da bi zvezdo in piko, ti nadomešča s puščico.

135
00:10:16,790 --> 00:10:24,820
Bodite zelo previdni, da se prepričajte, da ste poskušali uporabiti to sintakso.

136
00:10:33,550 --> 00:10:37,620
>> Zdaj, ko imamo kazalec, če želimo dostopati do vrednosti,

137
00:10:37,620 --> 00:10:40,450
preden smo imeli kazalec-> naslednji,

138
00:10:40,450 --> 00:10:46,260
ampak za dostop do vrednosti na vozlišču, da je kazalec, ki kaže, da smo samo preprosto reči,

139
00:10:46,260 --> 00:10:48,070
vozlišče-> vrednost.

140
00:10:48,070 --> 00:10:53,600
Od tam je tipa podatkov Karkoli smo opredelili vrednote in vozlišč biti.

141
00:10:53,600 --> 00:10:59,620
Če je int vozlišče, nato pa kazalec-> vrednost je le, da bo treba število.

142
00:10:59,620 --> 00:11:04,870
Tako lahko naredimo delovati, da preverite equalities, mu dodelite različne vrednosti, itd

143
00:11:04,870 --> 00:11:11,090
Torej, kaj želite storiti, če želite premakniti kazalec na naslednjo osebo,

144
00:11:11,090 --> 00:11:15,270
ste dejansko spremembo vrednosti kazalca.

145
00:11:15,270 --> 00:11:19,340
Ker je kazalec kazalec vozlišče, spremenite dejansko kazalec naslov

146
00:11:19,340 --> 00:11:23,890
na naslov naslednjega vozlišča na vašem seznamu.

147
00:11:23,890 --> 00:11:28,930
To je samo del kode, kjer lahko izbirate.

148
00:11:28,930 --> 00:11:31,230
Če imam komentar nekaj storiti,

149
00:11:31,230 --> 00:11:33,850
to je, če ste verjetno, da bo za dostop do vrednosti

150
00:11:33,850 --> 00:11:37,850
ali pa kaj opraviti s tem posebnem vozlišču.

151
00:11:37,850 --> 00:11:43,050
Če ga začnete, lahko rečem, da je moj kazalec na začetku

152
00:11:43,050 --> 00:11:48,430
se dogaja, da kaže na prvi element v povezanem seznamu.

153
00:11:48,430 --> 00:11:52,910
In tako se naprej, mi je opredeljeno kot vodja vozlišča.

154
00:11:52,910 --> 00:11:57,610
>> Kot sem že omenil, sprostitev, je zelo pomembno.

155
00:11:57,610 --> 00:12:02,440
Hočeš, da poskrbite, da boste sprostili vsak element na seznamu, ko ste končali z njo.

156
00:12:02,440 --> 00:12:04,940
Ko vam ni treba, da sklicevanje koli od teh kazalcev več,

157
00:12:04,940 --> 00:12:10,620
želite poskrbite, da boste sprostili vseh teh kazalcev.

158
00:12:10,620 --> 00:12:14,460
Ampak hočeš biti zelo previdni tukaj, da želite izogniti spomin razpoka.

159
00:12:14,460 --> 00:12:25,080
Če ste brez ena oseba predčasno, potem vse napotke, ki kaže na vozlišče, da se

160
00:12:25,080 --> 00:12:26,900
se bodo izgubljeni.

161
00:12:26,900 --> 00:12:32,070
Če se vrnemo k osebi, na primer, da bi bilo malo bolj high stakes,

162
00:12:32,070 --> 00:12:49,600
imejmo teh ljudi, razen v tem primeru so lebdi nad jezerom s pošastjo.

163
00:12:49,600 --> 00:12:53,200
Želimo zagotoviti, da ko smo sprostili, ne bomo izgubili

164
00:12:53,200 --> 00:12:58,920
in spustite vseh vozlišč, preden smo jih dejansko osvobodil.

165
00:12:58,920 --> 00:13:05,730
Na primer, če ste bili, da preprosto pokličite brezplačno na tega tipa tukaj,

166
00:13:05,730 --> 00:13:15,350
potem bi ga osvobodili, potem pa bi bili vsi ti ljudje potem lahko izgubijo

167
00:13:15,350 --> 00:13:18,450
in bi odtavaš in padel na tla.

168
00:13:18,450 --> 00:13:24,900
Zato želimo zagotoviti, da namesto tega, da želimo ohraniti povezavo do ostalih.

169
00:13:37,630 --> 00:13:42,480
Naš glavni kazalec, ki kaže na prvi element na seznamu.

170
00:13:42,480 --> 00:13:49,990
To je nekako kot vrv, sidranje prvo osebo.

171
00:13:52,870 --> 00:13:57,470
Kaj boste morda želeli storiti, ko sprostite seznam so se -

172
00:13:57,470 --> 00:14:04,520
Če želite sprostiti prvi del, potem imate lahko začasno kazalec

173
00:14:04,520 --> 00:14:07,370
, ki kaže, da ne glede na prvi element je.

174
00:14:07,370 --> 00:14:11,420
Torej imate vaše začasno kazalec kaže tukaj.

175
00:14:11,420 --> 00:14:15,840
Na ta način imamo drži prvo vozlišče.

176
00:14:15,840 --> 00:14:18,930
In potem, saj vemo, da je prvi vozel se bo sprostil,

177
00:14:18,930 --> 00:14:24,890
potem lahko gremo to vrv, to sidro, naše glave,

178
00:14:24,890 --> 00:14:31,930
dejansko kažejo, da ne glede na prvi kaže, da.

179
00:14:31,930 --> 00:14:38,760
Torej je to dejansko glava opozarja na drugem elementu zdaj.

180
00:14:38,760 --> 00:14:43,980
Zdaj smo lahko osvobodi vse, kar je shranjeno v temp,

181
00:14:43,980 --> 00:14:53,360
in da bomo lahko izbriše, da ne da bi ogrožali vseh drugih vozlišč v našem seznamu.

182
00:14:54,140 --> 00:15:05,020
Drug način, da bi vam to lahko

183
00:15:05,020 --> 00:15:08,650
vsakič, ko se le sprostiti zadnji element na seznamu

184
00:15:08,650 --> 00:15:11,010
ker si zagotoviti, da ne bi opozoril na karkoli.

185
00:15:11,010 --> 00:15:15,570
Torej bi lahko samo sprostiti tole, potem prosta 1, nato pa brez tega.

186
00:15:15,570 --> 00:15:21,900
To vsekakor deluje, vendar je nekoliko počasneje, ker ga je narava povezanih seznamov,

187
00:15:21,900 --> 00:15:24,670
ne moremo kar takoj skočiti na zadnji.

188
00:15:24,670 --> 00:15:28,030
Moramo prečkati vsak element v povezanem seznamu

189
00:15:28,030 --> 00:15:31,020
in preverite, ali da ena kaže na NULL, preverite vsakič,

190
00:15:31,020 --> 00:15:33,780
in potem, ko pridemo do konca, nato pa brez tega.

191
00:15:33,780 --> 00:15:40,270
Če ste bili do tega procesa, bi dejansko lahko tukaj preverjanje,

192
00:15:40,270 --> 00:15:44,190
preverjanje, potem pa se preveri tukaj, je osvoboditev,

193
00:15:44,190 --> 00:15:47,470
potem grem nazaj, preverjanje tukaj, preverjanje tukaj, je osvoboditev,

194
00:15:47,470 --> 00:15:49,660
preverjanje tukaj, in ga nato sprostiti.

195
00:15:49,660 --> 00:15:52,880
To traja malo več časa. Ja.

196
00:15:52,880 --> 00:15:59,060
>> [Študent] Bi bilo možno, da bi povezani seznam, ki shranjuje izhodne kazalec do konca?

197
00:15:59,060 --> 00:16:01,320
To bi vsekakor bilo mogoče.

198
00:16:01,320 --> 00:16:08,340
Če želite ponoviti vprašanje, ali je mogoče, da so povezanega strukturo seznam

199
00:16:08,340 --> 00:16:12,490
tako da imate kazalec, ki kaže na konec seznama, povezano?

200
00:16:12,490 --> 00:16:18,090
Jaz bi rekel, da je to možno, in vsakič, ko nekaj vstavili v svojo povezano seznam

201
00:16:18,090 --> 00:16:21,470
bi morali posodobiti, da kazalec in podobno.

202
00:16:21,470 --> 00:16:26,640
Ti bi morali vozlišče * rep, na primer.

203
00:16:26,640 --> 00:16:29,840
Toda, ko ste izvajanju te funkcije, boste morali razmišljati o kompromisov,

204
00:16:29,840 --> 00:16:32,700
všeč, kolikokrat bom se ponavljanjem nad tem,

205
00:16:32,700 --> 00:16:36,100
kako težko se bo slediti repa kot tudi glavo

206
00:16:36,100 --> 00:16:38,400
kot tudi moja iterator, in stvari, kot je ta.

207
00:16:40,730 --> 00:16:42,480
Ali to -? >> [Študent] Ja.

208
00:16:42,480 --> 00:16:48,270
Možno je, ampak v smislu oblikovanja sklepov, morate pretehtati možnosti.

209
00:16:53,850 --> 00:17:01,090
>> Tukaj je okostje kodo, da bi vam omogočajo, da osvobodi vse elemente v povezanem seznamu.

210
00:17:01,090 --> 00:17:05,460
Še enkrat, ker sem ponavljanjem v povezanem seznamu, bom želijo imeti neke vrste kazalca

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

212
00:17:08,670 --> 00:17:14,640
Mi smo ponavljanjem, dokler kazalec NULL.

213
00:17:14,640 --> 00:17:17,640
Vi ne želite, da izbirate, ko je kazalec NULL

214
00:17:17,640 --> 00:17:20,579
ker to pomeni, da ni nič na seznamu.

215
00:17:20,579 --> 00:17:25,069
Torej tukaj sem, da začasno vozlišče *

216
00:17:25,069 --> 00:17:29,610
kaže na to, kar Razmišljam je prvi mojem seznamu,

217
00:17:29,610 --> 00:17:35,340
in potem sem premakniti kazalko pred 1 in nato brezplačno, kar sem imela v začasnem skladišču.

218
00:17:38,460 --> 00:17:43,650
>> Zdaj smo prišli do vstavite v povezanih seznamih.

219
00:18:00,200 --> 00:18:09,660
Imam tri vozlišča v mojem povezanem seznamu in pojdimo z preprostem primeru

220
00:18:09,660 --> 00:18:18,970
kjer želimo vstaviti drugo vozlišče ob koncu našega povezani seznam.

221
00:18:18,970 --> 00:18:25,980
Da bi to dosegli, vse kar bi naredil, je pa bi prečkala

222
00:18:25,980 --> 00:18:32,100
najti, kje trenutno konec povezanega seznama je, da kar vozlišče kaže na NULL -

223
00:18:32,100 --> 00:18:33,850
da je to ena -

224
00:18:33,850 --> 00:18:37,260
in potem pravijo, pravzaprav, ta ne bo zadnji vozel;

225
00:18:37,260 --> 00:18:39,830
smo dejansko dogaja, da imajo še enega.

226
00:18:39,830 --> 00:18:46,260
Tako bi imeli to trenutno eno točko za karkoli smo vstavljanje.

227
00:18:46,260 --> 00:18:50,080
Torej, zdaj je to rdeča oseba, tukaj postane zadnji vozel v povezanem seznamu.

228
00:18:50,080 --> 00:18:56,080
In tako je značilnost zadnjega vozlišča v povezanem seznamu je, da opozarja na NULL.

229
00:18:56,080 --> 00:19:09,380
Torej kaj bi morali storiti, je nastaviti ta rdeča tip je kazalec NULL. Tukaj.

230
00:19:09,380 --> 00:19:25,370
>> Toda kaj, če želimo vstaviti v vozlišče med drugim in tretjim enega?

231
00:19:25,370 --> 00:19:28,960
Ta je ni tako preprosto, saj želimo zagotoviti,

232
00:19:28,960 --> 00:19:34,290
da ne opustite vse vozlišča v našem povezani seznam.

233
00:19:34,290 --> 00:19:43,450
Kaj bi morali storiti, je zagotoviti, da bomo zasidrali na vsakega.

234
00:19:43,450 --> 00:19:49,900
Na primer, recimo to, da drugega.

235
00:19:49,900 --> 00:19:54,390
Če si rekel, druga pa zdaj trdi, da to novo

236
00:19:54,390 --> 00:20:02,520
in si je kazalec tam, da bi povzročila ta človek izgublja

237
00:20:02,520 --> 00:20:07,830
ker ni nobene povezave z njim.

238
00:20:07,830 --> 00:20:18,970
Namesto tega - bom pripraviti še enkrat. Oprostite mi umetniške sposobnosti.

239
00:20:18,970 --> 00:20:26,570
Vemo, da ne moremo kar neposredno povezavo 2 na novo.

240
00:20:26,570 --> 00:20:30,480
Moramo zagotoviti, da imamo na zadnjega.

241
00:20:30,480 --> 00:20:39,200
Kaj lahko storite, je, da imajo začasni kazalec

242
00:20:39,200 --> 00:20:42,650
elementu, ki se dogaja, da se doda naprej.

243
00:20:42,650 --> 00:20:45,140
Torej imamo začasno kazalec tam.

244
00:20:45,140 --> 00:20:50,780
Ker vemo, da je to tretji pa se hranijo spremljali,

245
00:20:50,780 --> 00:20:53,680
2 Zdaj lahko povežete na našo novo.

246
00:20:53,680 --> 00:20:57,490
In če ta novi rdeči fant se bo v času med 2 in 3,

247
00:20:57,490 --> 00:21:05,550
potem kaj je ta tip je kazalec gre izpostaviti? >> [Študent] Temp.

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

249
00:21:07,490 --> 00:21:15,430
Torej ta rdeča tip je naslednja vrednost se bo temp.

250
00:21:26,090 --> 00:21:33,010
Ko ste vstavite v povezanih seznamih, smo videli, da bi se

251
00:21:33,010 --> 00:21:38,260
preprosto dodate nekaj do konca z ustvarjanjem začasno niz,

252
00:21:38,260 --> 00:21:42,850
ali če bi želel dodati nekaj v sredini našega niza,

253
00:21:42,850 --> 00:21:46,810
potem bi lahko malo bolj shuffling okoli.

254
00:21:46,810 --> 00:21:50,240
Če želite, na primer, imajo urejen povezani seznam,

255
00:21:50,240 --> 00:21:54,880
potem moraš nekako pretehtati stroške in koristi, ki

256
00:21:54,880 --> 00:21:59,720
ker če želimo imeti urejen niz, to pomeni, da vsakič, ko vstavite vanj,

257
00:21:59,720 --> 00:22:01,630
to bo trajalo malo več časa.

258
00:22:01,630 --> 00:22:05,500
Vendar, če želite kasneje, kot bomo našli bomo želeli,

259
00:22:05,500 --> 00:22:10,280
iskanje prek povezanega seznama, potem bi bilo lažje, če veš, da je vse v redu.

260
00:22:10,280 --> 00:22:15,340
Torej boste morda želeli primerjati stroške in koristi tega.

261
00:22:20,150 --> 00:22:27,740
>> Drug način, da vstavite v povezan seznam je vstaviti v samem začetku seznama.

262
00:22:27,740 --> 00:22:34,700
Če potegnemo našo sidro tukaj - to je naša glava -

263
00:22:34,700 --> 00:22:40,960
in potem so ti ljudje povezani z njim,

264
00:22:40,960 --> 00:22:48,460
in potem imamo novo vozlišče, ki se vstavi v začetku,

265
00:22:48,460 --> 00:22:52,590
potem, kaj bi radi, da naredim?

266
00:22:55,220 --> 00:23:03,580
Kaj bi bilo narobe s samo povedati hočem povezati rdečo modro,

267
00:23:03,580 --> 00:23:05,790
ker je to prva?

268
00:23:05,790 --> 00:23:08,570
Kaj bi se zgodilo tukaj?

269
00:23:08,570 --> 00:23:12,130
Vse od teh treh se bo izgubil.

270
00:23:12,130 --> 00:23:14,140
Zato ne želimo storiti.

271
00:23:14,140 --> 00:23:21,430
Spet smo se naučili, da moramo imeti neke vrste začasno kazalca.

272
00:23:21,430 --> 00:23:34,470
Naj odločijo za začasno točko do tega tipa.

273
00:23:34,470 --> 00:23:39,640
Potem lahko imamo modro eno točko za začasno

274
00:23:39,640 --> 00:23:43,240
in nato rdeča točka za modro.

275
00:23:43,240 --> 00:23:47,830
Razlog, zakaj sem s pomočjo ljudi tukaj, ker smo prepričani, da želite vizualizirati

276
00:23:47,830 --> 00:23:53,180
zadrževanje ljudi in zagotoviti, da imajo povezavo do njih

277
00:23:53,180 --> 00:23:57,590
preden se znebimo drugo roko ali kaj podobnega.

278
00:24:05,630 --> 00:24:10,650
>> Zdaj, ko imamo občutek, povezanih seznamov - kako bi lahko ustvarili povezano seznam

279
00:24:10,650 --> 00:24:15,090
in oblikovanje struktur za to je sestavljena iz vrste opredelitve za vozlišče

280
00:24:15,090 --> 00:24:19,060
nato pa se prepričajte, da imamo kazalec na čelu te povezane seznam -

281
00:24:19,060 --> 00:24:23,210
ko bomo imeli to in vemo, kako za prečkanje pričajo,

282
00:24:23,210 --> 00:24:28,200
dostop do različnih elementov, vemo, kako vstaviti, in vemo, kako se osvoboditi,

283
00:24:28,200 --> 00:24:30,260
potem bomo lahko v pravopisne napake.

284
00:24:30,260 --> 00:24:38,150
Kot ponavadi, smo del vprašanj, ki se boste uporabili za poslovanje s povezanimi seznami

285
00:24:38,150 --> 00:24:41,750
in različne strukture, kot so čakalne vrste in lonce.

286
00:24:41,750 --> 00:24:46,000
Potem lahko gremo v napačno zapisanih.

287
00:24:46,000 --> 00:24:55,170
>> Pravopisnih je v distribucijski oznako nekaj datotek pomena.

288
00:24:55,170 --> 00:24:58,850
Najprej opazimo, da imamo to Makefile tukaj,

289
00:24:58,850 --> 00:25:03,040
ki nismo zares prišlo prej.

290
00:25:03,040 --> 00:25:10,090
Če bi pogledali v notranjost pset5 mapo, ki ste jo opazili, da imate datoteko. H,

291
00:25:10,090 --> 00:25:12,530
potem imate dve c datoteke..

292
00:25:12,530 --> 00:25:18,920
Kaj to Makefile pa je prej, bi lahko samo tip in nato ime programa

293
00:25:18,920 --> 00:25:25,550
in potem bomo videli vse te trditve in zastav sprejet v prevajalnik.

294
00:25:25,550 --> 00:25:30,580
Kaj Makefile pa je, nam omogoča, da zbere več datotek hkrati

295
00:25:30,580 --> 00:25:34,650
in prenesti v zastavami, ki jih želimo.

296
00:25:34,650 --> 00:25:41,300
Tukaj smo videli tam glavo datoteke tukaj.

297
00:25:41,300 --> 00:25:43,730
Potem smo dejansko imajo dva izvornih datotek.

298
00:25:43,730 --> 00:25:47,520
Imamo speller.c in dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Vabimo vas, da uredite Makefile, če želite.

300
00:25:54,560 --> 00:26:03,310
Obvestilo, da tukaj, če vnesete čisto, kaj potem počne, je dejansko odstrani ničesar

301
00:26:03,310 --> 00:26:06,340
da je jedro.

302
00:26:06,340 --> 00:26:09,190
Če imaš Napaka pri razčlenjenosti, v bistvu si dobil njegove posmrtne ostanke.

303
00:26:09,190 --> 00:26:13,260
Tako bo ta grdi mali datoteka se pojavi v vašem imeniku, imenovano jedro.

304
00:26:13,260 --> 00:26:16,310
Boste želeli odstraniti, da bi bilo čisto.

305
00:26:16,310 --> 00:26:20,940
To odstrani vse exe datoteke in. O datoteke.

306
00:26:27,900 --> 00:26:30,220
>> Oglejmo si v dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Ta pravi, da razglasi zbirko funkcionalnost.

308
00:26:34,410 --> 00:26:39,530
Imamo največjo dolžino za vsako besedo v slovarju.

309
00:26:39,530 --> 00:26:45,130
Pravimo, da se bo najdaljša možna beseda. To je dolžine 45.

310
00:26:45,130 --> 00:26:48,900
Torej mi ne bo imela nobenih besed, ki presegajo to dolžino.

311
00:26:48,900 --> 00:26:50,980
Tukaj imamo samo funkcijskih prototipov.

312
00:26:50,980 --> 00:26:55,290
Nimamo dejansko izvajanje, ker to je tisto, kar bomo lahko delaš za to pset.

313
00:26:55,290 --> 00:26:59,940
Toda kaj to počne, je, ker imamo opravka z večjimi datotekami tukaj

314
00:26:59,940 --> 00:27:06,650
funkcionalnost in v večjem obsegu, je koristno imeti h datoteko.

315
00:27:06,650 --> 00:27:11,290
tako da se lahko nekdo bere ali z uporabo kode razumeti, kaj se dogaja.

316
00:27:11,290 --> 00:27:17,910
In morda želijo izvajati poskusi, če si hash tabele ali obratno.

317
00:27:17,910 --> 00:27:21,850
Potem bi rekel moj obremenitve funkcijo,

318
00:27:21,850 --> 00:27:26,950
dejansko izvajanje bo razlikujejo, vendar to prototip ne bo spremenila.

319
00:27:26,950 --> 00:27:33,280
Tukaj smo preveriti, ki vrne true, če je dana beseda v slovarju.

320
00:27:33,280 --> 00:27:39,800
Potem imamo tovor, ki v bistvu traja v slovarju datoteke

321
00:27:39,800 --> 00:27:44,360
in ga naloži v neko strukturo podatkov.

322
00:27:44,360 --> 00:27:47,500
Imamo velikosti, ki je, ko je poklical, vrne velikost slovar

323
00:27:47,500 --> 00:27:50,310
koliko besed so shranjene v njej,

324
00:27:50,310 --> 00:27:54,390
in potem razkladanje, ki sprosti vse pomnilnika, ki ste jih prevzeli

325
00:27:54,390 --> 00:27:57,900
pri tem pa svoj slovar.

326
00:28:01,070 --> 00:28:03,590
>> Oglejmo si dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Vidimo, da je videti zelo podobna dictionary.h, razen zdaj pa le ima vse te todos v njej.

328
00:28:10,490 --> 00:28:16,980
In da je tvoje delo. Sčasoma boste izpolnite speller.c z vso to kodo.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, ko se izvaja, v resnici ni storila ničesar,

330
00:28:21,540 --> 00:28:29,590
tako da se ozremo speller.c za prikaz dejanskega izvajanja črkovalnik.

331
00:28:29,590 --> 00:28:32,060
Čeprav vam ne bo treba urejati vse te oznake,

332
00:28:32,060 --> 00:28:38,050
je pomembno, da brati, razumeti, ko je obremenitev poklicala, ko kličem pregled,

333
00:28:38,050 --> 00:28:42,350
samo da bi razumeli, ga načrtovati, kako funkcija deluje.

334
00:28:42,350 --> 00:28:49,860
Vidimo, da je preverjanje za pravilno uporabo.

335
00:28:49,860 --> 00:28:55,200
V bistvu, ko nekdo teče speller, to pomeni, da je to neobvezno

336
00:28:55,200 --> 00:29:00,950
za njih, da preide v slovarju datoteke, ker se bo v privzeti slovar datoteko.

337
00:29:00,950 --> 00:29:05,410
In potem je treba iti v besedilu, da je črkovanja preveriti.

338
00:29:05,410 --> 00:29:11,410
rusage se ukvarja s časom, saj je del tega pset ki ukvarjali se bomo s kasneje

339
00:29:11,410 --> 00:29:14,790
ne samo pridobivanje delovanje črkovalnika delo

340
00:29:14,790 --> 00:29:17,190
ampak dejansko dobili, da bi bilo hitro.

341
00:29:17,190 --> 00:29:22,040
In tako je to, če rusage se dogaja, da pridejo noter

342
00:29:22,040 --> 00:29:28,740
Tukaj smo videli prvi klic na enega od naših dictionary.c datoteke, ki je tovor.

343
00:29:28,740 --> 00:29:34,720
Obremenitev vrne resnična ali neresnična - res odvisna od uspeha, lažnih ob izpadu.

344
00:29:34,720 --> 00:29:41,400
Torej, če je slovar ni pravilno vstavljen, se bo vrnil speller.c 1 in zaprete.

345
00:29:41,400 --> 00:29:47,920
Toda, če ne obremenitve pravilno, nato pa se bo nadaljevalo.

346
00:29:47,920 --> 00:29:50,740
Še naprej in vidimo nekaj datoteko I / O tukaj,

347
00:29:50,740 --> 00:29:56,210
kjer se dogaja, da se ukvarjajo z odpiranjem besedilno datoteko.

348
00:29:56,210 --> 00:30:04,640
Tukaj je, kaj to počne, je črkovanja preveri vsako posamezno besedo v besedilu.

349
00:30:04,640 --> 00:30:09,270
Torej, kaj speller.c počne tukaj je nad vsakim ponavljanjem besed v besedilno datoteko

350
00:30:09,270 --> 00:30:12,790
in jih nato preveri v slovarju.

351
00:30:24,680 --> 00:30:32,350
Tu imamo logičnim napačno črkovano, da bodo videli, če prijava vrne resnična ali ne.

352
00:30:32,350 --> 00:30:37,110
Če je beseda dejansko v slovarju, potem se bo prijava return true.

353
00:30:37,110 --> 00:30:39,760
To pomeni, da beseda ni napačno črkovana.

354
00:30:39,760 --> 00:30:45,330
Zato bi bilo napačno zapisano napačno, in zato imamo pok, navedba.

355
00:30:45,330 --> 00:30:56,320
Mi naprej dogaja, potem pa beleži, koliko napačno črkovane besede

356
00:30:56,320 --> 00:30:58,910
obstajajo v datoteki.

357
00:30:58,910 --> 00:31:03,870
Še naprej je na in arhivira.

358
00:31:03,870 --> 00:31:09,250
Potem sem pa poroča, koliko napačno črkovane besede, ki jih je imela.

359
00:31:09,250 --> 00:31:12,680
Komisija je izračunala, koliko časa je trajalo, da naložiti slovar,

360
00:31:12,680 --> 00:31:15,080
koliko časa je trajalo, da preveri,

361
00:31:15,080 --> 00:31:18,510
koliko časa je trajalo, da izračun velikosti,

362
00:31:18,510 --> 00:31:21,260
ki morajo biti, bomo šli naprej, je zelo majhna,

363
00:31:21,260 --> 00:31:25,390
in nato, koliko časa je trajalo, da raztovarjanje slovar.

364
00:31:25,390 --> 00:31:27,700
Tukaj gor nad vidimo poziv tukaj raztovoriti.

365
00:31:27,700 --> 00:31:52,690
Če želimo preveriti velikost tukaj,

366
00:31:52,690 --> 00:31:59,050
potem vidimo, da je tukaj poziv velikosti, kjer se določa velikost slovarja.

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

368
00:32:07,100 --> 00:32:10,920
>> Naša naloga za to pset je izvajanje obremenitev, ki bo nalaganje slovar

369
00:32:10,920 --> 00:32:15,480
Struktura podatkov - kar boste izbrali, bo to razpršena tabela ali poskusiti -

370
00:32:15,480 --> 00:32:18,810
z besedami iz slovarja datoteke.

371
00:32:18,810 --> 00:32:25,290
Potem imate velikosti, ki vrne število besed v slovarju.

372
00:32:25,290 --> 00:32:29,860
In če se izvaja tovor v pameten način, potem bi morali biti velikost precej enostavno.

373
00:32:29,860 --> 00:32:33,860
Potem ste preverjanje, ki bo preveril, če je dana beseda v slovarju.

374
00:32:33,860 --> 00:32:38,690
Torej speller.c prehaja v nizu, nato pa boste morali preveriti, ali je ta niz

375
00:32:38,690 --> 00:32:41,610
se nahaja v vašem slovarju.

376
00:32:41,610 --> 00:32:46,750
Opazimo, da smo na splošno imajo standardne slovarjev,

377
00:32:46,750 --> 00:32:53,020
vendar v tem pset, v bistvu vse slovar sprejet v katerem koli jeziku.

378
00:32:53,020 --> 00:32:57,040
Torej ne moremo preprosto sklepati, da beseda je notri.

379
00:32:57,040 --> 00:33:03,090
Beseda foobar je lahko opredeljen v določenem slovarju, ki se peljemo noter

380
00:33:03,090 --> 00:33:07,920
In potem smo raztovoriti, ki osvobaja zbirko iz spomina.

381
00:33:07,920 --> 00:33:11,930
>> Prvič, rad bi šel čez haše metodo tabele

382
00:33:11,930 --> 00:33:14,630
o tem, kako bi morali izvajati vseh teh štirih funkcij,

383
00:33:14,630 --> 00:33:18,650
in potem bom šel čez poskuša način, kako se izvajajo te štiri funkcije,

384
00:33:18,650 --> 00:33:22,720
in na koncu govori o nekaj splošnih nasvetov, če ste izdelavo pset

385
00:33:22,720 --> 00:33:27,870
in tudi, kako bi lahko bili lahko uporabila Valgrind za preverjanje pomnilnika pušča.

386
00:33:27,870 --> 00:33:30,550
>> Pojdimo v razpršitve metodo tabele.

387
00:33:30,550 --> 00:33:35,910
Razpršena tabela zajema seznam segmentov.

388
00:33:35,910 --> 00:33:43,010
Vsaka vrednost, vsako besedo, da bo šel v eno od teh segmentov.

389
00:33:43,010 --> 00:33:53,200
Razpršena tabela idealno enakomerno porazdeli vse te vrednosti, da ste potujejo

390
00:33:53,200 --> 00:33:57,160
in jih nato napolni v vedro, kot da vsak žlica

391
00:33:57,160 --> 00:34:02,000
ima približno enako število vrednosti v njem.

392
00:34:02,000 --> 00:34:09,630
Struktura za hash tabelo, imamo niz povezanih seznamov.

393
00:34:09,630 --> 00:34:17,900
Kaj moramo storiti, je, ko se peljemo v vrednosti, potrebno preveriti, če je ta vrednost pripada,

394
00:34:17,900 --> 00:34:23,840
ki žlica pripada, nato pa jo postavite v povezano seznamu povezano s tem vedro.

395
00:34:23,840 --> 00:34:28,199
Tukaj, kar imam, je hash funkcija.

396
00:34:28,199 --> 00:34:31,320
To je int razpršena tabela.

397
00:34:31,320 --> 00:34:38,540
Torej, za prvega segmenta, vse cela pod 10 šel v prvo vedro.

398
00:34:38,540 --> 00:34:42,190
Vse cela nad 10, vendar pod 20 šel v drugo,

399
00:34:42,190 --> 00:34:44,179
in potem tako naprej in tako naprej.

400
00:34:44,179 --> 00:34:52,370
Zame je vsaka žlica zastopa te številke.

401
00:34:52,370 --> 00:34:59,850
Vendar pa je rekel, da je bilo treba iti 50, na primer.

402
00:34:59,850 --> 00:35:07,490
Zdi se, kot da prvi trije vsebuje vrsto 10 številk.

403
00:35:07,490 --> 00:35:12,570
Ampak jaz želim, da bi moja razpršena tabela, da se v kakršnikoli cela števila,

404
00:35:12,570 --> 00:35:19,860
tako da bi potem morala tudi, da izločijo vse številke nad 30 v zadnjem vedro.

405
00:35:19,860 --> 00:35:26,660
In tako potem bi to imelo za posledico neke vrste neuravnovešenega hash tabele.

406
00:35:31,330 --> 00:35:35,640
Če ponovimo, razpršena tabela je le niz žlic

407
00:35:35,640 --> 00:35:38,590
kjer je vsak žlica povezani seznam.

408
00:35:38,590 --> 00:35:43,730
In tako ugotoviti, kje vsako vrednost gre, kar gre v vedro,

409
00:35:43,730 --> 00:35:46,260
boste želeli, kar se imenuje funkcijo razpršitve

410
00:35:46,260 --> 00:35:55,010
da se vrednost, nato pa pravi, da je ta vrednost ustreza določenemu vedro.

411
00:35:55,010 --> 00:36:00,970
Torej, tam zgoraj, v tem primeru moj hash funkcija je vsako vrednost.

412
00:36:00,970 --> 00:36:03,020
Zato je preverila, ali je bilo manj kot 10.

413
00:36:03,020 --> 00:36:05,360
Če bi bil, bi ga dal v prvo vedro.

414
00:36:05,360 --> 00:36:08,910
Preveri, ali je manj kot 20, ga spravlja v 2. če je to res,

415
00:36:08,910 --> 00:36:12,880
preveri, če je manj kot 30 let, nato pa ga spravlja v tretjem vedro,

416
00:36:12,880 --> 00:36:16,990
in potem vse ostalo samo pade na četrto vedro.

417
00:36:16,990 --> 00:36:20,110
Torej, ko ste vrednost, vaša funkcijo razpršitve

418
00:36:20,110 --> 00:36:25,420
bo potekala to vrednost v ustrezno vedro.

419
00:36:25,420 --> 00:36:32,430
Razpršilna funkcija v bistvu mora vedeti, koliko žlic imate.

420
00:36:32,430 --> 00:36:37,960
Vaš razpršena tabela velikost, število segmentov, ki jih imate,

421
00:36:37,960 --> 00:36:41,190
da se bo določeno število, ki je odvisno od vas, da se odločite,

422
00:36:41,190 --> 00:36:43,590
vendar pa se dogaja, da se določeno število.

423
00:36:43,590 --> 00:36:51,840
Torej vaš razpršilna funkcija se bo zanašal na to, da določi, katere žlica vsak ključ gre v

424
00:36:51,840 --> 00:36:54,450
tako, da je ni enakomerno porazdeljeno.

425
00:36:56,150 --> 00:37:03,820
Podobno kot pri našem izvajanju povezanih seznamov, zdaj vsako vozlišče v hash tabelo

426
00:37:03,820 --> 00:37:07,000
se dejansko dogaja, da ima tip sloj.

427
00:37:07,000 --> 00:37:14,340
Torej imamo char niz imenovano besedo in nato še kazalec na naslednje vozlišče,

428
00:37:14,340 --> 00:37:19,010
kar je smiselno, saj bo v povezani seznam.

429
00:37:19,010 --> 00:37:24,350
Se spomniš, ko smo povezani seznami, naredil sem vozlišče * imenovano glavo

430
00:37:24,350 --> 00:37:31,060
, ki je kazal na prvo vozlišča v povezanem seznamu.

431
00:37:31,060 --> 00:37:34,020
Toda za naš hash tabele, saj imamo več povezanih seznamov,

432
00:37:34,020 --> 00:37:37,520
hočemo želimo naša razpršena tabela, da bi izgledal "Kaj je vedro?"

433
00:37:37,520 --> 00:37:43,340
Žlica je samo seznam vozlišč kazalcev,

434
00:37:43,340 --> 00:37:50,620
in zato je vsak element v vedru je dejansko kaže na njeno ustrezno povezani seznam.

435
00:37:56,180 --> 00:38:01,520
Če se želite vrniti na to shematično, boste videli, da so same žlice puščice,

436
00:38:01,520 --> 00:38:06,980
ne dejanska vozlišča.

437
00:38:11,680 --> 00:38:16,420
Ena od bistvenih last hash funkcij, ki si jih deterministična.

438
00:38:16,420 --> 00:38:19,440
To pomeni, da vsakič, ko hash številka 2,

439
00:38:19,440 --> 00:38:22,270
mora vedno vrne isto vedro.

440
00:38:22,270 --> 00:38:26,440
Vsak znesek, ki gre v hash funkcijo, če bi se ponovil,

441
00:38:26,440 --> 00:38:29,690
je, da se isti indeks.

442
00:38:29,690 --> 00:38:34,210
Torej vaš hash funkcija vrne indeks niz

443
00:38:34,210 --> 00:38:38,530
kadar ta vrednost pripada.

444
00:38:38,530 --> 00:38:41,790
Kot sem že omenil, se določi število veder,

445
00:38:41,790 --> 00:38:49,630
in tako bo indeks, da se vrnete mora biti manjše od števila segmentov

446
00:38:49,630 --> 00:38:52,680
vendar večji od 0.

447
00:38:52,680 --> 00:39:00,780
Razlog, zakaj imamo hash funkcijo, namesto da samo z enim samim povezan seznam

448
00:39:00,780 --> 00:39:09,290
ali en sam niz je, da želimo, da bi lahko skočil do določene točke najlažje

449
00:39:09,290 --> 00:39:11,720
če vemo, značilne vrednosti -

450
00:39:11,720 --> 00:39:14,760
namesto da bi morali iskati po celotnega slovar

451
00:39:14,760 --> 00:39:18,320
da lahko skoči na določen del tega.

452
00:39:19,880 --> 00:39:24,440
Vaš hash funkcijo je treba upoštevati, da je idealno,

453
00:39:24,440 --> 00:39:28,980
vsaka žlica ima približno enako število tipk.

454
00:39:28,980 --> 00:39:35,040
Ker je razpršena tabela je serija povezanih seznamov,

455
00:39:35,040 --> 00:39:38,480
potem povezani seznam sami pa bodo morali več kot eno vozlišče.

456
00:39:38,480 --> 00:39:43,210
V prejšnjem primeru dveh različnih številk, čeprav niso bili enaki,

457
00:39:43,210 --> 00:39:46,950
ko je zgoščen bi vrnili isti indeks.

458
00:39:46,950 --> 00:39:53,620
Torej, če ste se ukvarjajo z besedami, eno besedo, ko zgoščen

459
00:39:53,620 --> 00:39:57,450
bi bila enaka vrednost razpršitve, kot drugo besedo.

460
00:39:57,450 --> 00:40:04,140
To je tisto, čemur pravimo trčenja, ko imamo vozlišče, da se pri zgoščene,

461
00:40:04,140 --> 00:40:09,610
povezani seznam v tem vedru ni prazna.

462
00:40:09,610 --> 00:40:14,180
Tehnika, ki jo imenujemo ni linearna sondiranje,

463
00:40:14,180 --> 00:40:22,550
če greš v povezanem seznamu in poiščite mesto, kamor želite vstaviti, da je vozlišče

464
00:40:22,550 --> 00:40:25,520
ker imaš trčenje.

465
00:40:25,520 --> 00:40:28,070
Vidite lahko, da bi lahko prišlo do kompromisa, kajne?

466
00:40:28,070 --> 00:40:33,760
Če imate zelo malo razpršene tabele, zelo majhno število veder,

467
00:40:33,760 --> 00:40:36,380
potem boste imeli veliko trčenj.

468
00:40:36,380 --> 00:40:40,460
Ampak potem, če ste se zelo veliko razpršene tabele,

469
00:40:40,460 --> 00:40:44,110
ste verjetno, da bo zmanjšanje trkov,

470
00:40:44,110 --> 00:40:47,170
vendar bo še zelo velika struktura podatkov.

471
00:40:47,170 --> 00:40:49,310
Prišlo bo kompromisi s tem.

472
00:40:49,310 --> 00:40:51,310
Torej, ko delaš svoje pset, poskusite igral

473
00:40:51,310 --> 00:40:54,210
Mogoče bi med manjše razpršene tabele

474
00:40:54,210 --> 00:41:02,100
potem pa se zavedamo, da bo trajalo nekoliko dlje, da prečkanje različne elemente

475
00:41:02,100 --> 00:41:04,270
od teh povezanih seznamov.

476
00:41:04,270 --> 00:41:09,500
>> Kaj obremenitev bo naredil, je ponovitev čez vsako besedo v slovarju.

477
00:41:09,500 --> 00:41:13,180
Poteka v kazalec na datoteko slovarju.

478
00:41:13,180 --> 00:41:18,050
Torej boš izkoristil spisa I / O funkcije, ki jih obvlada v pset4

479
00:41:18,050 --> 00:41:23,010
Ponovil in nad vsako besedo v slovarju.

480
00:41:23,010 --> 00:41:26,620
Hočeš vsako besedo iz slovarja, da postane novo vozlišče,

481
00:41:26,620 --> 00:41:32,730
in ti boš, da se vsak od teh vozlišč znotraj vašega strukture slovarju podatkov.

482
00:41:32,730 --> 00:41:36,560
Vsakič, ko dobite novo besedo, veste, da se dogaja, da postane vozlišče.

483
00:41:36,560 --> 00:41:46,590
Torej, lahko greš takoj in malloc vozlišče kazalec za vsako novo besedo, ki jo imate.

484
00:41:46,590 --> 00:41:52,610
Tukaj bom poklical mojo new_node vozlišča kazalca in sem mallocing kaj? Velikost vozlišče.

485
00:41:52,610 --> 00:41:59,190
Nato se glasi dejansko niz iz datoteke, ker je dejansko skladiščena slovar

486
00:41:59,190 --> 00:42:03,340
z besedo in nato novo linijo, kar lahko izkoristimo

487
00:42:03,340 --> 00:42:06,520
je funkcija fscanf,

488
00:42:06,520 --> 00:42:10,280
pri čemer je datoteka slovar datoteka, ki smo opravili v,

489
00:42:10,280 --> 00:42:18,900
tako da skenira datoteko za niz in kraji, ki vrvice v zadnji argument.

490
00:42:18,900 --> 00:42:26,890
Če se spomnim nazaj na enem od predavanj, ko smo se odpravili v

491
00:42:26,890 --> 00:42:29,320
in vrsta olupljen plasti nazaj v knjižnico CS50,

492
00:42:29,320 --> 00:42:33,430
smo videli izvajanje fscanf tam.

493
00:42:33,430 --> 00:42:37,700
Če se želite vrniti fscanf, imamo datoteko, ki smo branje iz,

494
00:42:37,700 --> 00:42:42,570
iščemo niz v tej datoteki, nato pa smo, da ga postavite v

495
00:42:42,570 --> 00:42:48,340
Tukaj imam new_node-> besedo, ker new_node je vozlišče kazalec,

496
00:42:48,340 --> 00:42:50,380
Ne dejansko vozlišče.

497
00:42:50,380 --> 00:42:57,100
Potem sem rekel new_node, želim iti na vozlišče, da se kaže, da

498
00:42:57,100 --> 00:43:01,190
in nato določite, da vrednost besedo.

499
00:43:01,190 --> 00:43:08,540
Želimo, da bi potem to besedo in jo vstavite v hash tabelo.

500
00:43:08,540 --> 00:43:13,750
Zavedam se, da smo new_node vozlišče kazalec

501
00:43:13,750 --> 00:43:18,230
ker bomo želeli vedeti, kaj je naslov tega vozlišča je

502
00:43:18,230 --> 00:43:23,940
ko ga vstavite v ker je struktura vozlišč samih, o struct,

503
00:43:23,940 --> 00:43:26,380
je, da imajo kazalec na novo vozlišče.

504
00:43:26,380 --> 00:43:30,820
Torej, kaj je naslov tega vozlišča dogaja izpostaviti?

505
00:43:30,820 --> 00:43:34,550
Ta naslov se bo new_node.

506
00:43:34,550 --> 00:43:42,140
Ali ima to smisel, zakaj delamo new_node vozlišče * za razliko od vozlišča?

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

508
00:43:45,700 --> 00:43:52,840
Imamo besedo. Ta vrednost je new_node-> beseda.

509
00:43:52,840 --> 00:43:55,970
, Ki vsebuje besedo iz slovarja, ki ga želite vhodu.

510
00:43:55,970 --> 00:44:00,210
Torej, kaj želimo narediti, je, da smo želeli poklicati svojo funkcijo razpršitve na tem nizu

511
00:44:00,210 --> 00:44:03,780
saj je naš hash funkcija se v nizu in se nato vrne nam celo število,

512
00:44:03,780 --> 00:44:12,090
če to celo, če je indeks Hashtable na ta indeks predstavlja, da vedro.

513
00:44:12,090 --> 00:44:18,260
Želimo, da to kazalo, nato pa pojdite na to indeksu hash tabele

514
00:44:18,260 --> 00:44:26,960
in nato uporabite, da povezani seznam dodati vozlišče v new_node.

515
00:44:26,960 --> 00:44:31,950
Ne pozabite, da pa se odločite, da vstavite vaše vozlišče,

516
00:44:31,950 --> 00:44:34,370
ali je v sredini, če želite, da ga rešiti

517
00:44:34,370 --> 00:44:39,650
ali na začetku ali na koncu, le poskrbite, da vaše zadnje vozlišče vedno obrnjen na NULL

518
00:44:39,650 --> 00:44:46,730
ker je to edini način, da bomo vedeli, kje je zadnji element našega seznama je povezano.

519
00:44:50,790 --> 00:44:59,710
>> Če je velikost, ki predstavlja celo število besed v slovarju,

520
00:44:59,710 --> 00:45:03,060
Nato eden od načinov za to je, da kadar se imenuje velikost

521
00:45:03,060 --> 00:45:05,840
gremo skozi vsak element v našem hash tabele

522
00:45:05,840 --> 00:45:09,410
in potem Ponovil skozi vse povezano seznam v tabeli razpršitve

523
00:45:09,410 --> 00:45:13,770
in nato izračunati, koliko, da povečuje našo števec 1 do 1.

524
00:45:13,770 --> 00:45:16,580
Ampak vsakič, ko se imenuje velikost, da se bo to trajalo dlje časa

525
00:45:16,580 --> 00:45:22,120
saj bomo linearno biti sondiranje vsak povezani seznam.

526
00:45:22,120 --> 00:45:30,530
Namesto tega se bo veliko lažje, če bi spremljali, koliko besed so opravili noter

527
00:45:30,530 --> 00:45:36,330
Torej, če ste tudi števec v vašem obremenitve funkcijo

528
00:45:36,330 --> 00:45:42,430
da posodobitve, kot je potrebno, potem števec, če jo nastavite na globalne spremenljivke,

529
00:45:42,430 --> 00:45:44,930
bodo mogli dostopati po velikosti.

530
00:45:44,930 --> 00:45:51,450
Torej, kaj lahko naredite enostavno velikost je v eni vrstici, le vrne protivrednost,

531
00:45:51,450 --> 00:45:55,500
velikost slovarja, ki ste jih že obravnava v breme.

532
00:45:55,500 --> 00:46:05,190
To je tisto, kar sem mislil, ko sem rekel, če izvajajo obremenitev na koristen način,

533
00:46:05,190 --> 00:46:08,540
potem velikost se bo zelo enostavno.

534
00:46:08,540 --> 00:46:11,350
>> Torej, zdaj smo dobili pregled.

535
00:46:11,350 --> 00:46:15,960
Zdaj imamo opravka z besedami iz vhodne datoteke z besedilom,

536
00:46:15,960 --> 00:46:19,910
in tako bomo lahko preverili, ali vse te besede vhodnih

537
00:46:19,910 --> 00:46:22,520
dejansko v slovarju ali ne.

538
00:46:22,520 --> 00:46:26,520
Podobno Scramble, želimo, da se omogoči neobčutljivosti primera.

539
00:46:26,520 --> 00:46:32,110
Hočeš, da poskrbite, da po vseh besedah ​​sprejet, čeprav si malimi črkami,

540
00:46:32,110 --> 00:46:37,840
ko je klical z primerjanje nizov, sta enakovredna.

541
00:46:37,840 --> 00:46:42,450
Besede v slovarju besedilne datoteke so dejansko vse male črke.

542
00:46:42,450 --> 00:46:49,280
Druga stvar je, da lahko predpostavimo, da je vsaka beseda izrečena, vsak niz,

543
00:46:49,280 --> 00:46:53,200
se bo bodisi po abecedi ali vsebujejo opuščaje.

544
00:46:53,200 --> 00:46:58,010
Opuščaje se bodo veljavni besede v našem slovarju.

545
00:46:58,010 --> 00:47:06,470
Torej, če govorim z opuščajem S, ki je dejansko legitimno beseda v vašem slovarju

546
00:47:06,470 --> 00:47:11,650
da se dogaja, da je eden od vozlišč v vašem hash tabele.

547
00:47:13,470 --> 00:47:18,350
Preverite, če deluje z besedo ne obstaja, potem je dobil, da je v naši hash tabele.

548
00:47:18,350 --> 00:47:22,210
Če je beseda v slovarju, potem pa vse besede v slovarju so v hash tabele,

549
00:47:22,210 --> 00:47:26,560
tako da je pogled na te besede v hash tabelo.

550
00:47:26,560 --> 00:47:29,250
Vemo, da je, odkar smo izvajali svojo funkcijo razpršitve

551
00:47:29,250 --> 00:47:38,420
tako, da je vsak edinstven beseda vedno zgoščen na enako vrednost,

552
00:47:38,420 --> 00:47:43,340
potem vemo, da namesto da bi iskali s pomočjo našega celotnega hash tabele,

553
00:47:43,340 --> 00:47:48,310
lahko dejansko našli povezan seznam, da bi ta beseda pripada.

554
00:47:48,310 --> 00:47:51,850
Če bi bilo v slovarju, potem bi bilo v tem vedru.

555
00:47:51,850 --> 00:47:57,140
Kaj lahko storimo, če je beseda ime našega niza, sprejeto leta,

556
00:47:57,140 --> 00:48:01,560
smo lahko le hašiš, da beseda in pogled na povezanem seznamu

557
00:48:01,560 --> 00:48:06,410
na vrednost Hashtable [razpršitve (beseda)].

558
00:48:06,410 --> 00:48:12,410
Od tam, kaj lahko storimo je, da imamo manjše podmnožice vozlišč za iskanje te besede,

559
00:48:12,410 --> 00:48:16,770
in da bomo lahko prečkala povezanega seznama z uporabo primera iz prej v walkthrough,

560
00:48:16,770 --> 00:48:24,110
nato pa klic niz primerjati na besedo, kjer je kazalec kaže na,

561
00:48:24,110 --> 00:48:28,430
ta beseda, in videli, ali so primerjati.

562
00:48:30,280 --> 00:48:35,110
Glede na način, ki ga organizira svojo funkcijo razpršitve,

563
00:48:35,110 --> 00:48:39,260
če je to razporejene, bi morali imeti možnost, da vrne false nekoliko prej,

564
00:48:39,260 --> 00:48:43,440
če pa je neurejeno, potem pa želite še naprej vozijo prek povezanega seznama

565
00:48:43,440 --> 00:48:46,480
dokler ne boste našli zadnji element seznama.

566
00:48:46,480 --> 00:48:53,320
In če še vedno niste našli besedo, ko ste zaključili povezanem seznamu

567
00:48:53,320 --> 00:48:56,890
To pomeni, da vaša beseda ne obstaja v slovarju,

568
00:48:56,890 --> 00:48:59,410
in da beseda ni pravilna,

569
00:48:59,410 --> 00:49:02,730
in bi morala prijava vrne false.

570
00:49:02,730 --> 00:49:09,530
>> Zdaj smo prišli do raztovoriti, če želimo, da osvobodi vse vozlišča, ki smo malloc'd,

571
00:49:09,530 --> 00:49:14,050
tako brez vseh vozlišč znotraj našega hash tabele.

572
00:49:14,050 --> 00:49:20,270
Bomo želeli ponoviti čez vse, povezanih seznamov in brez vseh vozlišč v to.

573
00:49:20,270 --> 00:49:29,350
Če pogledaš zgoraj v walkthrough na primer takrat, ko smo sprostili povezan seznam,

574
00:49:29,350 --> 00:49:35,140
potem boste želeli ponoviti ta postopek za vsak element v hash tabelo.

575
00:49:35,140 --> 00:49:37,780
In jaz bom šel čez to proti koncu walkthrough,

576
00:49:37,780 --> 00:49:46,600
ampak Valgrind je orodje, kjer lahko vidite, če ste pravilno osvobodili

577
00:49:46,600 --> 00:49:53,600
vsako vozlišče, ki ste jih malloc'd ali karkoli drugega, ki ste jih malloc'd, katero koli drugo kazalec.

578
00:49:55,140 --> 00:50:00,530
Torej, to je razpršene tabele, kjer imamo končno število segmentov

579
00:50:00,530 --> 00:50:09,220
in razpršilna funkcija, ki bo vrednost in nato določite, da vrednost določenega segmenta.

580
00:50:09,220 --> 00:50:13,340
>> Zdaj smo prišli do poskusa.

581
00:50:13,340 --> 00:50:18,750
Poskuša vrste zgleda takole, jaz pa bom tudi potegnili zgled.

582
00:50:18,750 --> 00:50:25,630
V bistvu, imate celo paleto možnih črk,

583
00:50:25,630 --> 00:50:29,210
in potem, ko ste izgradnjo besedo,

584
00:50:29,210 --> 00:50:36,490
ta dopis je mogoče povezati v slovarju za široko paleto možnosti.

585
00:50:36,490 --> 00:50:40,840
Nekaj ​​besed začeti s C, nato pa še z,

586
00:50:40,840 --> 00:50:42,960
drugi pa še z O, na primer.

587
00:50:42,960 --> 00:50:51,090
Trie je način za ponazoritev vse možne kombinacije teh besed.

588
00:50:51,090 --> 00:50:59,070
Trie bo slediti zaporedja črk, ki sestavljajo besede,

589
00:50:59,070 --> 00:51:08,280
odcepil, če je to potrebno, če se lahko ena črka sledi večkratnik pisem,

590
00:51:08,280 --> 00:51:16,630
in na koncu kažejo na vsaki točki, ali je ta beseda veljavna ali ne,

591
00:51:16,630 --> 00:51:30,120
ker če ste črkovanje besedo MAT, MA Ne verjamem, da je veljavna beseda, ampak MAT.

592
00:51:30,120 --> 00:51:37,820
In tako v vašem Trie, bi bilo navedeno, da po tem, ko MAT, da je dejansko veljavna beseda.

593
00:51:41,790 --> 00:51:48,590
Vsako vozlišče v naši Trie se dejansko dogaja, da vsebuje niz vozlišč kazalcev,

594
00:51:48,590 --> 00:51:52,970
in bomo imeli, še posebej, 27 od teh vozlišč kazalcev,

595
00:51:52,970 --> 00:52:00,550
ena za vsako črko v abecedi, kot tudi Opuščaj značaja.

596
00:52:00,550 --> 00:52:10,450
Vsak element v tem polju se bo sama, da kaže na drugo vozlišče.

597
00:52:10,450 --> 00:52:14,020
Torej, če je vozlišče NULL, če ni nič po tem,

598
00:52:14,020 --> 00:52:20,550
potem vemo, da ni nobenih nadaljnjih pisem v ta besedna zveza.

599
00:52:20,550 --> 00:52:26,950
Ampak če je vozlišče ni NULL, kar pomeni, da obstaja več črk v tem dopisu zaporedju.

600
00:52:26,950 --> 00:52:32,160
In potem prav, vsak vozel označuje, ali je to zadnji znak v besedi ali ne.

601
00:52:38,110 --> 00:52:43,170
>> Pojdimo v primer za Trie.

602
00:52:50,500 --> 00:52:58,340
Najprej moram prostor za 27 vozlišč v tem polju.

603
00:52:58,340 --> 00:53:03,200
Če imam besedo BAR -

604
00:53:13,310 --> 00:53:15,370
Če imam besedo BAR in želim dodati, da,

605
00:53:15,370 --> 00:53:22,700
prva črka je B, tako da če mi Trie je prazna,

606
00:53:22,700 --> 00:53:29,910
B je druga črka v abecedi, zato bom odločite, da to tukaj na tem indeksu.

607
00:53:29,910 --> 00:53:33,450
Jaz bom imel B tukaj.

608
00:53:33,450 --> 00:53:42,400
B se bo vozlišče, ki kaže na drugo paleto vseh mogočih likov

609
00:53:42,400 --> 00:53:45,870
, ki lahko sledijo po pisnem B.

610
00:53:45,870 --> 00:53:57,610
V tem primeru, sem se ukvarjajo z napisom BAR, tako da bo tukaj gre.

611
00:54:02,000 --> 00:54:08,990
Ko imam pismo R, potem je zdaj točke za svojo kombinacijo,

612
00:54:08,990 --> 00:54:15,120
in potem bo R tukaj.

613
00:54:15,120 --> 00:54:22,470
BAR je popolna beseda, zato pa bom, da imajo raziskave kažejo na drugo vozlišče

614
00:54:22,470 --> 00:54:33,990
, ki pravi, da je ta beseda velja.

615
00:54:36,010 --> 00:54:40,970
To vozlišče se tudi dogaja, da imajo niz vozlišč,

616
00:54:40,970 --> 00:54:45,260
vendar pa bi bilo tistih NULL.

617
00:54:45,260 --> 00:54:49,080
Ampak v bistvu, lahko še naprej tako.

618
00:54:49,080 --> 00:54:54,250
To bo malo bolj jasno, ko bomo šli v drug primer,

619
00:54:54,250 --> 00:54:56,780
tako da samo tam nosijo s seboj.

620
00:54:56,780 --> 00:55:02,050
Zdaj imamo BAR znotraj našega slovarja.

621
00:55:02,050 --> 00:55:05,980
Zdaj pravijo, da imamo besedo BAZ.

622
00:55:05,980 --> 00:55:12,630
Začeli smo z B, in že imamo B, kot eno izmed pisem, ki jih je v našem slovarju.

623
00:55:12,630 --> 00:55:15,170
To je sledila z A. Imamo že.

624
00:55:15,170 --> 00:55:19,250
Potem pa namesto tega imamo Z naslednjo.

625
00:55:19,250 --> 00:55:25,490
Torej element v našem polju se bo Z,

626
00:55:25,490 --> 00:55:30,810
in tako potem bo nihče izpostaviti drugo veljavno koncu besede.

627
00:55:30,810 --> 00:55:36,930
Tako vidimo, da ko bomo nadaljevali z B, nato pa,

628
00:55:36,930 --> 00:55:43,480
obstajata dve različni možnosti trenutno v našem slovarju za besede, ki se začnejo s črko B in A.

629
00:55:49,650 --> 00:55:57,460
Povejte smo želeli vstaviti besedo foobar.

630
00:55:57,460 --> 00:56:05,620
Potem bi naredimo vstop na F.

631
00:56:05,620 --> 00:56:11,320
F je vozlišče, ki opozarja na celo vrsto.

632
00:56:11,320 --> 00:56:22,790
Radi bi našli O, pojdite na O, O, nato povezave do celotnega seznama.

633
00:56:22,790 --> 00:56:35,340
Mi bi morali B in nato nadaljujte, bi imeli, nato pa R.

634
00:56:35,340 --> 00:56:43,570
Torej foobar prehaja vso pot navzdol, dokler ne foobar ni prava beseda.

635
00:56:43,570 --> 00:56:52,590
In tako potem bi to bila veljavna beseda.

636
00:56:52,590 --> 00:57:00,170
Zdaj pravijo, naša naslednja beseda v slovarju, je pravzaprav beseda FOO.

637
00:57:00,170 --> 00:57:03,530
Mi bi rekli, F. Kaj sledi F?

638
00:57:03,530 --> 00:57:06,190
Pravzaprav sem že prostor za O, tako da bom še naprej.

639
00:57:06,190 --> 00:57:09,150
Ne rabim, da bi novo. Nadaljuj.

640
00:57:09,150 --> 00:57:15,500
FOO je veljavna beseda v tem slovarju, tako da potem bom navesti

641
00:57:15,500 --> 00:57:21,660
, da je veljavna.

642
00:57:21,660 --> 00:57:28,370
Če se ustavim svoj zaporedje tam, bi bilo to pravilno.

643
00:57:28,370 --> 00:57:33,050
Ampak, če bomo nadaljevali zaporedje od Foo do B

644
00:57:33,050 --> 00:57:39,750
in prav je FOOB, FOOB ni beseda, ki je ni navedena kot veljaven.

645
00:57:47,370 --> 00:57:57,600
V Trie, ki ste jih vsako vozlišče pove, ali je beseda velja ali ne,

646
00:57:57,600 --> 00:58:05,840
in nato vsak vozel ima tudi niz 27 vozlov kazalcev

647
00:58:05,840 --> 00:58:09,520
ki pokažite na vozlišč sami.

648
00:58:09,520 --> 00:58:12,940
>> Tukaj je način, kako bi želeli določiti to.

649
00:58:12,940 --> 00:58:17,260
Vendar pa, tako kot v primeru hash tabele, kjer smo imeli vozlišče * glavo

650
00:58:17,260 --> 00:58:21,320
, ki označuje začetek naše povezan seznam, bomo tudi dogaja, da želijo

651
00:58:21,320 --> 00:58:29,150
nek način vedeli, kje začetek našega Trie je.

652
00:58:29,150 --> 00:58:34,110
Nekateri ljudje pravijo poskuša drevesa, in to je, če prihaja od korena.

653
00:58:34,110 --> 00:58:36,910
Zato želimo naše korenine drevesa, se prepričajte, da bomo ostali ozemljeni

654
00:58:36,910 --> 00:58:39,570
povsod, kjer smo Trie je.

655
00:58:42,910 --> 00:58:46,300
Smo že nekako šla čez

656
00:58:46,300 --> 00:58:50,240
Tako boste lahko mislil nakladanje vsako besedo v slovar.

657
00:58:50,240 --> 00:58:54,540
V bistvu, za vsako besedo, ki jo boste želeli ponoviti skozi Trie

658
00:58:54,540 --> 00:58:59,590
in vemo, da vsak element pri otrocih - smo poklicani, da otroci v tem primeru -

659
00:58:59,590 --> 00:59:04,290
ustreza drugo pismo, boste želeli preveriti te vrednote

660
00:59:04,290 --> 00:59:08,320
v tistem indeksa, ki ustreza dopisu.

661
00:59:08,320 --> 00:59:11,260
Tako razmišljanje vso pot nazaj k cesarju in Vigenere,

662
00:59:11,260 --> 00:59:16,070
vedoč, da ima vsaka črka, ki jo lahko nekako zemljevidu nazaj na indeks abecednem,

663
00:59:16,070 --> 00:59:20,690
Zagotovo A do Z se bo zelo enostavno preslikati v abecednem pismu,

664
00:59:20,690 --> 00:59:25,200
ampak na žalost, opuščaje tudi sprejet znak v besedi.

665
00:59:25,200 --> 00:59:31,650
Nisem prepričan, kaj ASCII vrednost,

666
00:59:31,650 --> 00:59:39,250
tako da za to, če želite, da bi našli kazalo, da odloči, ali želite, da je bodisi prvi

667
00:59:39,250 --> 00:59:44,550
ali zadnja, boste morali, da bi težko kodirane ček, ki

668
00:59:44,550 --> 00:59:48,930
, nato pa, da je v indeksu 26, na primer.

669
00:59:48,930 --> 00:59:55,300
Torej ste preverjanje vrednosti otroke [i]

670
00:59:55,300 --> 00:59:58,400
kjer je [i], kar ustreza črka ste.

671
00:59:58,400 --> 01:00:04,110
Če je to NULL, kar pomeni, da trenutno ni na morebitne črke

672
01:00:04,110 --> 01:00:08,150
izhajajo iz tega zaporedja prejšnjega, tako da boste želeli, da malloc

673
01:00:08,150 --> 01:00:13,150
in narediti novo vozlišče in imate, da otroci [i] opozarjajo na to

674
01:00:13,150 --> 01:00:17,890
tako da boste ustvarili - ko smo vstavili pismo v pravokotniku -

675
01:00:17,890 --> 01:00:23,680
ki otrokom ne NULL in točka v tej novi vozlišče.

676
01:00:23,680 --> 01:00:28,340
Ampak, če to ni NULL, kot v našem primeru foo

677
01:00:28,340 --> 01:00:34,570
ko smo že foobar, bomo še naprej,

678
01:00:34,570 --> 01:00:44,010
in smo se nikoli ne bi novo vozlišče, ampak le določa, da res is_word

679
01:00:44,010 --> 01:00:47,790
Na koncu te besede.

680
01:00:50,060 --> 01:00:55,340
>> Torej tako kot prej, saj tu imate opravka z vsakim pismom, v času,

681
01:00:55,340 --> 01:01:01,470
to bo lažje za vas, za velikost, namesto da bi izračun

682
01:01:01,470 --> 01:01:06,910
in iti skozi celotno drevo in izračunajte, koliko otrok imam

683
01:01:06,910 --> 01:01:10,850
in potem odcepil, se spomnimo, koliko so na levi in ​​na desni strani

684
01:01:10,850 --> 01:01:12,850
in take stvari, to se dogaja, da je veliko lažje za vas

685
01:01:12,850 --> 01:01:16,220
če ste le slediti, koliko besed ste ga dodali v

686
01:01:16,220 --> 01:01:18,080
ko imate opravka s tovorom.

687
01:01:18,080 --> 01:01:22,630
In tako potem lahko na ta način velikost samo vrnitev globalno spremenljivko velikosti.

688
01:01:25,320 --> 01:01:28,530
>> Zdaj smo prišli preveriti.

689
01:01:28,530 --> 01:01:33,920
Enakimi standardi, kot prej, ko želimo omogočiti neobčutljivosti primera.

690
01:01:33,920 --> 01:01:40,400
Kot je dobro, predpostavimo, da so strune le črki ali opuščaje

691
01:01:40,400 --> 01:01:44,000
ker otrok je niz 27 dolgo,

692
01:01:44,000 --> 01:01:48,480
tako da vse črke abecede plus Opuščaj.

693
01:01:48,480 --> 01:01:53,800
Za preverite, kaj boste želeli storiti, je, da boste želeli, da začnete pri korenu

694
01:01:53,800 --> 01:01:58,440
ker bo koren kažejo na matriko, ki vsebuje

695
01:01:58,440 --> 01:02:01,630
vseh možnih začetnih črk besede.

696
01:02:01,630 --> 01:02:03,680
Boš tam začeti,

697
01:02:03,680 --> 01:02:11,590
in potem boš preverite to vrednost NULL ali ne,

698
01:02:11,590 --> 01:02:16,490
ker če je vrednost NULL, kar pomeni, da je slovar nima vrednosti

699
01:02:16,490 --> 01:02:21,480
, ki vsebujejo ta dopis, v tem posebnem vrstnem redu.

700
01:02:21,480 --> 01:02:24,970
Če je NULL, potem to pomeni, da je beseda napačno črkovana takoj.

701
01:02:24,970 --> 01:02:27,110
Ampak, če to ni NULL, potem pa lahko nadaljujete,

702
01:02:27,110 --> 01:02:34,090
pravijo, da je prva črka je možna prva črka v besedi,

703
01:02:34,090 --> 01:02:40,630
tako da zdaj hočem, da preverite, če je druga črka, da zaporedje, je v mojem slovarju.

704
01:02:40,630 --> 01:02:46,540
Torej boš šel z indeksom otrok prvega vozla

705
01:02:46,540 --> 01:02:50,720
in preverite, ali je to drugo pismo obstaja.

706
01:02:50,720 --> 01:02:57,440
Nato ponovite ta postopek za preverjanje, ali je to zaporedje veljavna ali ne,

707
01:02:57,440 --> 01:02:59,060
v vašem Trie.

708
01:02:59,060 --> 01:03:06,430
Kadar so otroci v vozlišče, ki indeksnih točkah na NULL,

709
01:03:06,430 --> 01:03:10,710
veš, da zaporedje ne obstaja,

710
01:03:10,710 --> 01:03:16,230
potem pa, če pridete do konca besede, ki ste jih vnesejo,

711
01:03:16,230 --> 01:03:20,070
potem boste želeli preveriti, zdaj sem končal to zaporedje

712
01:03:20,070 --> 01:03:27,610
in ugotovil, da je v moji Trie je, da beseda velja ali ne?

713
01:03:27,610 --> 01:03:32,480
In tako potem želite preveriti, in takrat, če ste ugotovili, da je zaporedje

714
01:03:32,480 --> 01:03:35,120
potem boste želeli preveriti, ali je ta beseda veljavna ali ne,

715
01:03:35,120 --> 01:03:40,290
saj se spomnite nazaj v prejšnjem primeru, ki sem narisal, kjer smo imeli FOOB,

716
01:03:40,290 --> 01:03:48,410
da je veljavna zaporedna ki smo jo našli, vendar ni bila dejansko veljavna beseda sama.

717
01:03:50,570 --> 01:03:59,000
>> Podobno velja za raztovarjanje v poskusih, ki jih želite razkladanje vseh vozlišč v vašem Trie.

718
01:03:59,000 --> 01:04:04,790
Žal mi je. Podobno kot hash tabele kjer raztovarjanje smo osvobojeni vseh vozlišč,

719
01:04:04,790 --> 01:04:09,740
V poskusih, ki jih želimo tudi osvobodi vse vozlišč.

720
01:04:09,740 --> 01:04:15,000
Razbremenite se bo dejansko delajo najlažji od spodaj navzgor

721
01:04:15,000 --> 01:04:19,290
ker so v bistvu povezani seznam.

722
01:04:19,290 --> 01:04:22,540
Zato želimo zagotoviti, da imamo na vseh vrednot

723
01:04:22,540 --> 01:04:25,700
in brez vseh njih eksplicitno.

724
01:04:25,700 --> 01:04:28,840
Kaj boste želeli storiti, če delate z Trie

725
01:04:28,840 --> 01:04:35,640
je, da potujejo na dnu in prosti najnižjo možno vozlišče 1.

726
01:04:35,640 --> 01:04:39,190
in nato šel na vse tiste otroke, nato pa brez vseh tistih,

727
01:04:39,190 --> 01:04:43,050
pojdi gor in nato brezplačno, itd

728
01:04:43,050 --> 01:04:48,790
Nekako tako kot se ukvarjajo s spodnjim plasti Trie 1.

729
01:04:48,790 --> 01:04:51,940
nato pa bo do vrha, ko ste osvobodili vse.

730
01:04:51,940 --> 01:04:56,720
To je dober primer, kjer bi lahko rekurzivna funkcija prišla prav.

731
01:04:56,720 --> 01:05:03,830
Ko ste osvobodili spodnja plast vašega Trie,

732
01:05:03,830 --> 01:05:08,000
potem pokličete na razkladanje ostalega območja,

733
01:05:08,000 --> 01:05:13,620
pazite, da boste sprostili vsak mini -

734
01:05:13,620 --> 01:05:16,410
Lahko nekako vizualiziramo, da kot mini poskusih.

735
01:05:23,300 --> 01:05:28,990
Torej imate korenine tukaj.

736
01:05:30,840 --> 01:05:35,230
Jaz sem samo to poenostavi tako da mi ni bilo treba poseči 26 izmed njih.

737
01:05:37,250 --> 01:05:43,770
Torej imate to, potem ti predstavljajo zaporedja besed

738
01:05:43,770 --> 01:05:54,620
če vse te majhnih krogih so črke, ki so veljavni zaporedja črk.

739
01:06:03,040 --> 01:06:07,160
Naj še samo malo več.

740
01:06:15,110 --> 01:06:25,750
Kaj boste želeli storiti, je brezplačna dno tukaj in nato prosta 1

741
01:06:25,750 --> 01:06:31,640
in nato brezplačno ta na dnu, preden si brezplačno vrhnjo 1 tukaj

742
01:06:31,640 --> 01:06:38,180
ker če vas brezplačno nekaj v drugem nivoju tukaj,

743
01:06:38,180 --> 01:06:47,230
potem bi dejansko izgubil to vrednost tukaj.

744
01:06:47,230 --> 01:06:54,780
To je razlog, zakaj je pomembno za razkladanje Trie in se prepričajte, da boste sprostili na dnu prve.

745
01:06:54,780 --> 01:06:59,480
Kaj boste morda želeli storiti, je rekel za vsako vozlišče

746
01:06:59,480 --> 01:07:06,430
Želim razložiti vse otroke.

747
01:07:16,060 --> 01:07:22,140
>> Zdaj, ko smo šli čez raztovoriti za hash metodo mizo, kot tudi način Trie,

748
01:07:22,140 --> 01:07:27,020
bomo želeli videti na Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind zaženete z naslednjimi ukazi.

750
01:07:29,640 --> 01:07:32,700
Imate valgrind-V.

751
01:07:32,700 --> 01:07:40,960
Saj kontrolo za vse puščanja pri zagonu speller saj je to določeno besedilo

752
01:07:40,960 --> 01:07:46,980
ker speller potrebuje v besedilno datoteko.

753
01:07:46,980 --> 01:07:52,330
Tako bo Valgrind zaženete program, vam povedati, koliko bajtov se dodelijo,

754
01:07:52,330 --> 01:07:57,150
koliko bajtov se sprosti, in to vam bo povedal, ali ste osvobodili ravno dovolj

755
01:07:57,150 --> 01:07:58,930
ali pa nisi dovolj prosto,

756
01:07:58,930 --> 01:08:02,850
včasih lahko celo preveč svobodno, kot je brezplačen vozlišče, ki je že osvobojena

757
01:08:02,850 --> 01:08:05,140
in tako se bo vrnil vam napake.

758
01:08:05,140 --> 01:08:11,600
Če uporabljate Valgrind, se vam bo nekaj sporočil

759
01:08:11,600 --> 01:08:15,970
navedbo, ali ste osvobojeni ali manj kot dovolj, ravno dovolj,

760
01:08:15,970 --> 01:08:19,609
ali več kot dovolj časa.

761
01:08:24,370 --> 01:08:30,410
>> Del tega pset, je opcija za izpodbijanje veliko tablo.

762
01:08:30,410 --> 01:08:35,790
Toda, ko imamo opravka s temi podatkovnih struktur

763
01:08:35,790 --> 01:08:40,689
to je zabavno videti, kako hitro in kako učinkovito bi bilo vaše podatkovne strukture.

764
01:08:40,689 --> 01:08:44,490
Ali vaš hash funkcija za posledico veliko trčenj?

765
01:08:44,490 --> 01:08:46,300
Ali je vaš obseg podatkov zelo velika?

766
01:08:46,300 --> 01:08:49,420
Ali je potrebno veliko časa za prečkanje?

767
01:08:49,420 --> 01:08:54,800
V dnevniku speller, za pisanje, koliko časa boste uporabili za nalaganje,

768
01:08:54,800 --> 01:08:57,700
Za preverjanje, vodenje velikosti in razkladanje,

769
01:08:57,700 --> 01:09:00,720
in tako so tisti, objavljene v velikem svetu,

770
01:09:00,720 --> 01:09:03,600
kjer lahko tekmujejo sošolci

771
01:09:03,600 --> 01:09:11,350
in nekateri uslužbenci bi videli, kdo je najhitrejši črkovalnik.

772
01:09:11,350 --> 01:09:14,760
Ena stvar, ki bi rad vedite o hash tabele

773
01:09:14,760 --> 01:09:20,470
je, da obstaja nekaj zelo preprostih zgostitvene funkcije, ki bi lahko mislimo.

774
01:09:20,470 --> 01:09:27,240
Na primer, da imate 26 veder, in zato je vsaka žlica

775
01:09:27,240 --> 01:09:30,200
ustreza prvo črko v besedi,

776
01:09:30,200 --> 01:09:35,229
ampak da se bo to povzročilo precej neuravnotežen hash tabele

777
01:09:35,229 --> 01:09:40,979
ker obstaja veliko manj besed, ki se začnejo z X od začetka z M, na primer.

778
01:09:40,979 --> 01:09:47,890
Eden od načinov, da gredo o speller je, če želite, da bi dobili vse druge funkcionalnosti navzdol

779
01:09:47,890 --> 01:09:53,240
potem pa uporabite preprosto funkcijo razpršitve, da bi lahko dobili kodo teče

780
01:09:53,240 --> 01:09:58,650
nato pa pojdite nazaj in spremeni velikost razpršilne tabele in opredelitev.

781
01:09:58,650 --> 01:10:03,430
Obstaja veliko virov na spletu za hash funkcij,

782
01:10:03,430 --> 01:10:08,250
in tako za to pset si dovoliti, da raziskave hash funkcije na internetu

783
01:10:08,250 --> 01:10:15,560
Za nekaj namigov in navdih, dokler ste prepričani, da navedejo kje ste jo dobili od.

784
01:10:15,560 --> 01:10:22,060
Vabljeni, da si razlagajo in nekaj funkcijo razpršitve, ki ga najdete na internetu.

785
01:10:22,060 --> 01:10:27,460
Nazaj, da boste morda lahko videli, če je nekdo uporabil Trie

786
01:10:27,460 --> 01:10:31,700
ali je njihovo izvajanje hitreje kot vaš hash tabelo ali ne.

787
01:10:31,700 --> 01:10:35,290
Lahko pošljete na veliko tablo večkrat.

788
01:10:35,290 --> 01:10:37,660
To bo posneti zadnji vnos.

789
01:10:37,660 --> 01:10:44,300
Mogoče ste spremenili funkcijo razpršitve in nato ugotovili, da je dejansko veliko hitreje

790
01:10:44,300 --> 01:10:46,780
ali veliko počasneje kot prej.

791
01:10:46,780 --> 01:10:50,960
To je malo na zabaven način.

792
01:10:50,960 --> 01:10:57,190
Vedno je 1 ali 2 uslužbenci, ki poskušajo narediti čim najpočasneje zbirko,

793
01:10:57,190 --> 01:11:00,210
tako da je vedno zabavno gledati.

794
01:11:00,210 --> 01:11:07,630
>> Uporaba za pset je naletite speller z dodatnim slovarju

795
01:11:07,630 --> 01:11:12,840
in potem obvezno besedilna datoteka.

796
01:11:12,840 --> 01:11:18,380
Privzeto, ko zaženete speller s samo besedilne datoteke in ne določajo zbirko,

797
01:11:18,380 --> 01:11:24,410
to se dogaja, da uporabite datoteko slovarja besedila, velik 1

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

799
01:11:27,920 --> 01:11:32,760
To je ena je več kot 100.000 besed.

800
01:11:32,760 --> 01:11:37,950
Imajo tudi majhno zbirko, ki ima precej manj besed

801
01:11:37,950 --> 01:11:40,730
da CS50 je za vas.

802
01:11:40,730 --> 01:11:44,050
Vendar pa je lahko zelo enostavno samo, da svojo zbirko

803
01:11:44,050 --> 01:11:47,150
Če si želite, da bodo delali v manjših primerov -

804
01:11:47,150 --> 01:11:51,140
na primer, če želite uporabljati gdb in veš posebne vrednosti

805
01:11:51,140 --> 01:11:53,560
, ki želite, da vaš razpršena tabela začrtati k.

806
01:11:53,560 --> 01:12:00,430
Tako si lahko naredite svojo besedilno datoteko samo z barom, Baz, Foo, in foobar,

807
01:12:00,430 --> 01:12:04,860
da to v besedilno datoteko, ločiti tiste, vsak z 1 linijo,

808
01:12:04,860 --> 01:12:12,670
in nato naredite svojo besedilno datoteko, ki vsebuje le dobesedno morda 1 ali 2 besedi

809
01:12:12,670 --> 01:12:15,950
tako da boste točno vedeli, kaj bi bilo izhod.

810
01:12:15,950 --> 01:12:21,870
Nekatere besedilne datoteke vzorcev, da bo Veliki svet je ob zagonu preverite izziv

811
01:12:21,870 --> 01:12:25,580
so Vojna in mir ter roman Jane Austen ali nekaj takega.

812
01:12:25,580 --> 01:12:30,450
Torej, če ste začeli ven, je to veliko lažje narediti svoje besedilne datoteke

813
01:12:30,450 --> 01:12:34,160
ki vsebujejo le nekaj besed ali morda 10

814
01:12:34,160 --> 01:12:38,280
tako da lahko napovedati, kaj bi rezultat

815
01:12:38,280 --> 01:12:42,880
nato pa preverite pred, da je to bolj nadzorovano primer.

816
01:12:42,880 --> 01:12:45,820
In zato, ker imamo opravka z predvidevanje in risanje stvari okoli,

817
01:12:45,820 --> 01:12:48,690
Ponovno bi rad, da uporabite svinčnik in papir

818
01:12:48,690 --> 01:12:50,700
ker se v resnici dogaja, da vam pomaga s tem 1 -

819
01:12:50,700 --> 01:12:55,620
risanje puščic, kako hash tabele ali kako Trie izgleda,

820
01:12:55,620 --> 01:12:57,980
ko boš sprostila nekaj, kjer puščice se dogaja,

821
01:12:57,980 --> 01:13:01,730
se držiš na dovolj, vidiš vse povezave izginjajo

822
01:13:01,730 --> 01:13:05,750
in ki spadajo v brezno ušli spominu.

823
01:13:05,750 --> 01:13:11,070
Zato vas prosimo, poskusite pripraviti stvari, še preden prideš do pisanja kode navzdol.

824
01:13:11,070 --> 01:13:14,520
Risanje stvari, tako da boste razumeli, kako stvari gredo na delo

825
01:13:14,520 --> 01:13:22,750
ker potem vam zagotavljam, da boste naleteli na manj pokvari kazalec tam.

826
01:13:24,270 --> 01:13:25,910
>> V redu.

827
01:13:25,910 --> 01:13:28,780
Želim vam želim veliko sreče s tem pset.

828
01:13:28,780 --> 01:13:31,980
To je verjetno najtežje.

829
01:13:31,980 --> 01:13:40,360
Torej, poskusite začeti zgodaj, pripravi stvari, pripravi stvari, in veliko sreče.

830
01:13:40,360 --> 01:13:42,980
To je bilo Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]