1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Návod - Problém 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
>> Dobrá. Ahoj, všetci, a vitajte na Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 je Pravopisné chyby, v ktorom budeme robiť pravopisu.

6
00:00:17,400 --> 00:00:21,030
Spell-dáma, sú nesmierne dôležité.

7
00:00:21,030 --> 00:00:23,390
Má to niekedy stalo?

8
00:00:23,390 --> 00:00:27,170
Môžete pracovať veľmi, veľmi hromadia na papieri pre stret

9
00:00:27,170 --> 00:00:33,120
a potom ešte nakoniec dostať veľmi žiara Rade ako D alebo D =

10
00:00:33,120 --> 00:00:39,390
a všetci preto, že ste liverwurst spojler v veľrýb širokom slova.

11
00:00:39,390 --> 00:00:44,710
Áno, korektúry vašich papriky je vec, maximálna impotencia.

12
00:00:44,710 --> 00:00:49,140
To je problém, ktorý postihuje mužské, mužné študentov.

13
00:00:49,140 --> 00:00:56,260
Bol som raz povedal môj mučiteľovi stupňa Sith, že by som nikdy dostať do dobrého kolegu.

14
00:00:56,260 --> 00:01:00,250
A to je všetko, čo som kedy chcel, to je všetko, každý chlapec chce v mojom veku,

15
00:01:00,250 --> 00:01:04,569
Len dostať sa do dobrej kolegovi.

16
00:01:04,569 --> 00:01:12,720
A nie len tak hocijaký kolega. Nie Chcel som ísť do Slonoviny Právne kolegovi.

17
00:01:12,720 --> 00:01:18,360
Takže ak som to zlepšenie, by šiel sa moje sny o ísť na Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, alebo Prison - viete, vo väznici, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Tak som si sám sebe pravopisu.

20
00:01:25,170 --> 00:01:29,380
To je trochu výpis z jednej z mojich najobľúbenejších hovorené slovo umelcov, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Každopádne, ako hovorí, že je dôležité mať pravopisu je veľmi dôležité.

22
00:01:34,630 --> 00:01:39,440
>> Takže vitajte na Walkthrough 5, v ktorom sa bude hovoriť o pset5: pravopisné chyby,

23
00:01:39,440 --> 00:01:44,300
, V ktorom budeme robiť naše vlastné pravopisu.

24
00:01:44,300 --> 00:01:50,880
Nástrojov pre tento týždeň, distribúcia kód, bude dôležité, aby sa na

25
00:01:50,880 --> 00:01:54,950
len pochopiť rôzne funkcie, ktoré váš slovník bude mať.

26
00:01:54,950 --> 00:02:01,500
Sme vlastne bude mať viac. C. súborov, ktoré dohromady tvoria našu PSet.

27
00:02:01,500 --> 00:02:05,420
A tak hľadá prostredníctvom rôznych aspektoch, aj keď sme vlastne nie pre editáciu

28
00:02:05,420 --> 00:02:10,770
jeden zo súborov, speller.c, vedel, ako to funguje vo vzťahu k dictionary.c,

29
00:02:10,770 --> 00:02:14,100
ktoré budeme písať, bude dosť dôležité.

30
00:02:14,100 --> 00:02:16,970
Spec Pset tiež obsahuje mnoho užitočných informácií

31
00:02:16,970 --> 00:02:21,360
pokiaľ ide o veci, ktoré môžete predpokladať, pravidlá a podobné veci, ktoré,

32
00:02:21,360 --> 00:02:24,710
tak sa určite prečítajte PSet špec starostlivo tipy.

33
00:02:24,710 --> 00:02:29,310
A v prípade pochybností o pravidlá alebo niečo také, potom sa vždy vzťahujú k PSet spec

34
00:02:29,310 --> 00:02:31,550
alebo Diskutovať.

35
00:02:31,550 --> 00:02:34,060
Tento Pset bude spoliehať na ukazovatele,

36
00:02:34,060 --> 00:02:37,890
tak chceme, aby sa ubezpečil, že sme pochopili rozdiel medzi pridávanie hviezdičiek

37
00:02:37,890 --> 00:02:41,680
v prednej časti je ukazovateľ meno a ampersand, ako sa oslobodiť a atď

38
00:02:41,680 --> 00:02:47,550
Takže byť majstrom ukazovateľov bude veľmi užitočné v tomto probléme sade.

39
00:02:47,550 --> 00:02:50,460
Budeme sa pozrieť do prepojené zoznamy trochu viac,

40
00:02:50,460 --> 00:02:57,790
kde majú prvky, ktorý nazývame uzly, ktoré majú ako hodnotu, rovnako ako ukazovateľ

41
00:02:57,790 --> 00:03:02,520
k nasledujúcemu uzlu, a tak v podstate prepojenie rôznych prvkov jeden po druhom.

42
00:03:02,520 --> 00:03:07,190
Existuje niekoľko rôznych možností na realizáciu svojej skutočnej slovník.

43
00:03:07,190 --> 00:03:13,150
Budeme sa pozrieť do dvoch hlavných metód, ktoré je hashovacie tabuľky a potom sa pokúsi.

44
00:03:13,150 --> 00:03:17,660
V oboch tých, ktoré zahŕňajú nejaký druh pojmu prepojeného zoznamu

45
00:03:17,660 --> 00:03:20,790
kde ste elementy navzájom prepojené.

46
00:03:20,790 --> 00:03:25,640
A tak budeme vyzerať nad tým, ako by ste mali byť schopní pracovať okolo prepojených zoznamov,

47
00:03:25,640 --> 00:03:29,680
vytvoriť, prechádzať z hľadiska ako, napríklad, vložiť uzol do neho

48
00:03:29,680 --> 00:03:32,760
alebo bez všetky uzly rovnako.

49
00:03:32,760 --> 00:03:34,740
Pokiaľ ide o uvoľňovacími uzlov, to je naozaj dôležité

50
00:03:34,740 --> 00:03:37,700
že kedykoľvek sme malloc pamäti, potom sme uvoľniť ju.

51
00:03:37,700 --> 00:03:42,910
Takže chceme, aby sa ubezpečil, že žiadny ukazovateľ ide unfreed, že nemáme žiadne úniky pamäte.

52
00:03:42,910 --> 00:03:48,330
Budeme zaviesť nástroj nazývaný Valgrind, ktorý beží na programe

53
00:03:48,330 --> 00:03:52,260
a kontroluje, či všetky pamäti, že pridelené je potom oslobodený.

54
00:03:52,260 --> 00:03:59,080
Vaša Pset je len dokončiť, keď to funguje, a má plnú funkčnosť,

55
00:03:59,080 --> 00:04:03,990
ale tiež, Valgrind vám povie, že ste nenašli žiadne úniky pamäte.

56
00:04:03,990 --> 00:04:06,690
Napokon, pre tento PSet, naozaj chcem zdôrazniť -

57
00:04:06,690 --> 00:04:11,360
Myslím, ako zvyčajne, ja som rozhodne zástancom použitia pera a papiera pre vaše problémové súbory,

58
00:04:11,360 --> 00:04:14,840
ale pre tento jeden, myslím, že pero a papier bude obzvlášť dôležité

59
00:04:14,840 --> 00:04:19,000
ak chcete, aby sa čerpanie šípky na veci a pochopenie toho, ako veci fungujú.

60
00:04:19,000 --> 00:04:24,440
Takže určite skúste použiť ceruzku a papier k tomu, čo pred vás kódovanie

61
00:04:24,440 --> 00:04:26,970
pretože by to mohlo byť trochu chaotický.

62
00:04:26,970 --> 00:04:30,700
>> Po prvé, poďme do prepojených zoznamov trochu.

63
00:04:30,700 --> 00:04:35,510
Prepojené zoznamy sa skladajú z uzlov, kde každý uzol má hodnotu spojenú s ním,

64
00:04:35,510 --> 00:04:39,810
rovnako ako ukazovateľ na ďalší uzol po ňom.

65
00:04:39,810 --> 00:04:43,680
Pár vecí dôležitých s lineárnymi zoznamy je, že musíme mať na pamäti

66
00:04:43,680 --> 00:04:48,810
kde naša prvá uzol je, a potom raz vieme, kde prvý uzol je,

67
00:04:48,810 --> 00:04:52,990
že spôsob, ako môžeme pristupovať na uzol, ktorý prvý uzol odkazuje na

68
00:04:52,990 --> 00:04:55,850
a potom ešte do a jeden po tom.

69
00:04:55,850 --> 00:05:00,340
A potom posledný prvok vo vašom prepojeného zoznamu je tento uzol je ukazovateľ

70
00:05:00,340 --> 00:05:02,340
je vždy poukázať na NULL.

71
00:05:02,340 --> 00:05:08,230
Keď uzol bodov na hodnotu NULL, potom viete, že ste na konci zoznamu,

72
00:05:08,230 --> 00:05:12,320
že uzol je posledný, že nie je nič po tom.

73
00:05:12,320 --> 00:05:16,970
Tu v tomto schéme, uvidíte, že šípky sú ukazovatele,

74
00:05:16,970 --> 00:05:20,290
a modré sekcia je miesto, kde je uložený hodnota,

75
00:05:20,290 --> 00:05:24,420
a potom červené pole s ukazovateľ na nej je uzol je ukazovateľ

76
00:05:24,420 --> 00:05:27,050
ukazuje na ďalší uzol po ňom.

77
00:05:27,050 --> 00:05:33,730
A tak tu vidíte, by uzol D poukázať na NULL, pretože to je posledný prvok v zozname.

78
00:05:33,730 --> 00:05:38,240
>> Poďme sa pozrieť na to, ako by sme mohli definovať struct pre uzol.

79
00:05:38,240 --> 00:05:40,130
A pretože chceme mať viac uzlov,

80
00:05:40,130 --> 00:05:43,180
to sa stane typedef struct

81
00:05:43,180 --> 00:05:46,870
, V ktorom budeme mať niekoľko rôznych inštancií uzlov.

82
00:05:46,870 --> 00:05:50,850
A tak sme ju definujú ako nový dátový typ.

83
00:05:50,850 --> 00:05:53,630
Tu máme typedef struct uzol.

84
00:05:53,630 --> 00:05:56,160
V tomto príklade, máme čo do činenia s celočíselnými uzlami,

85
00:05:56,160 --> 00:06:00,490
takže máme celočíselnú názvom hodnotu a potom máme ďalšie ukazovateľ,

86
00:06:00,490 --> 00:06:07,390
a v tomto prípade, je to ukazovateľ na uzol, takže máme struct uzol * volal ďalšie.

87
00:06:07,390 --> 00:06:09,520
A potom voláme celú túto vec uzol.

88
00:06:09,520 --> 00:06:11,110
Uistite sa, že budete dodržiavať nasledujúce syntax.

89
00:06:11,110 --> 00:06:17,940
Všimnite si, že uzol je v skutočnosti odkazuje hore rovnako ako dole zložených zátvoriek.

90
00:06:17,940 --> 00:06:23,400
Potom sledovať, kde moja prvá uzol v tomto prepojenom zozname,

91
00:06:23,400 --> 00:06:29,390
potom som si uzol ukazovateľ s názvom hlava, a ja malloc dostatok priestoru pre veľkosť uzla.

92
00:06:29,390 --> 00:06:36,240
Poznámka, však, že hlava je vlastne uzol ukazovateľ na rozdiel od aktuálneho uzla samotného.

93
00:06:36,240 --> 00:06:40,130
Takže hlava skutočne neobsahuje žiadnu hodnotu,

94
00:06:40,130 --> 00:06:45,590
iba poukázať na podľa toho, čo prvý uzol v mojom prepojeného zoznamu je.

95
00:06:55,080 --> 00:06:58,340
>> Ak chcete získať lepšiu predstavu o súvisiacich zoznamov, pretože je to veľmi dôležité,

96
00:06:58,340 --> 00:07:02,220
sledovať uistiť sa, že budete udržiavať reťaz,

97
00:07:02,220 --> 00:07:09,990
Páči sa mi myslieť na to, ako sa ľudia v rade sa drží za ruky,

98
00:07:09,990 --> 00:07:14,330
, Kde každá osoba je drží za ruky s ďalšie.

99
00:07:14,330 --> 00:07:18,350
Nemôžete vidieť v tomto výkresu, ale v podstate sú to ukazuje na ďalšiu osobu

100
00:07:18,350 --> 00:07:23,760
že je v ich reťazci.

101
00:07:23,760 --> 00:07:29,270
A tak ak chcete prejsť prepojené zoznam, kde títo ľudia -

102
00:07:29,270 --> 00:07:32,830
predstaviť všetkých tých ľudí majú hodnoty spojené s nimi

103
00:07:32,830 --> 00:07:36,590
a tiež poukazujú na ďalšie osoby v súlade -

104
00:07:36,590 --> 00:07:40,810
Ak chcete prejsť prepojeného zoznamu, napríklad, buď upraviť hodnoty

105
00:07:40,810 --> 00:07:42,830
alebo hľadanie hodnote alebo niečo také,

106
00:07:42,830 --> 00:07:48,270
potom budete chcieť mať ukazovateľ na konkrétnu osobu.

107
00:07:48,270 --> 00:07:52,670
Takže budeme mať dátový typ uzla ukazovateľ.

108
00:07:52,670 --> 00:07:55,580
Pre tento Napríklad, povedzme, že kurzor.

109
00:07:55,580 --> 00:07:59,630
Ďalším bežným spôsobom pomenovať to bude Iterator, alebo niečo také

110
00:07:59,630 --> 00:08:05,130
pretože je to iterácie a vlastne dojemná, ktorý uzol to ukazuje.

111
00:08:05,130 --> 00:08:14,410
Toto bude naše kurzor.

112
00:08:14,410 --> 00:08:20,180
Náš kurzor sa najprv poukázať na prvý prvok v našom zozname.

113
00:08:20,180 --> 00:08:26,910
A tak to, čo chceme urobiť, je, že sme sa v podstate bude pokračovať kurzor,

114
00:08:26,910 --> 00:08:29,130
pohybujúce sa zo strany na stranu.

115
00:08:29,130 --> 00:08:33,409
V tomto prípade, chceme presunúť na ďalší prvok v zozname.

116
00:08:33,409 --> 00:08:38,480
S poľom, čo budeme robiť, je by sme len povedať, že sme zvýšiť index 1.

117
00:08:38,480 --> 00:08:46,020
V tomto prípade, čo musíme urobiť, je skutočne zistiť, ktoré osoby tento prúd osoba smerujúce,

118
00:08:46,020 --> 00:08:48,930
a že to bude ďalšiu hodnotu.

119
00:08:48,930 --> 00:08:53,230
Takže ak kurzor je len uzol ukazovateľ, potom to, čo chceme robiť

120
00:08:53,230 --> 00:08:56,320
je, že sa chcú dostať na hodnotu, ktorá je kurzor ukazuje.

121
00:08:56,320 --> 00:09:01,350
Chceme sa dostať do tohto uzla a potom, až budeme v tomto uzle, zistiť, kde to ukazuje.

122
00:09:01,350 --> 00:09:05,820
Ak chcete dostať do aktuálneho uzla, ktorý kurzor ukazuje na,

123
00:09:05,820 --> 00:09:13,160
zvyčajne označujeme ju (* kurzor).

124
00:09:13,160 --> 00:09:19,160
To by vám aktuálne uzol, ktorý kurzor ukazuje.

125
00:09:19,160 --> 00:09:21,730
A potom, čo chceme urobiť, je chceme pristupovať

126
00:09:21,730 --> 00:09:25,680
čo to uzla budúci hodnota.

127
00:09:25,680 --> 00:09:32,820
K tomu, aby sa prístup k hodnoty vnútri struct, máme operátora bodka.

128
00:09:32,820 --> 00:09:39,530
Takže potom by to bolo (* kurzor). Ďalšie.

129
00:09:39,530 --> 00:09:44,840
Ale to je trochu chaotický, pokiaľ ide o to, aby zátvorky okolo * kurzora,

130
00:09:44,840 --> 00:09:56,800
a tak sme sa nahradiť celú túto vyhlásenie s kurzorom->.

131
00:09:56,800 --> 00:10:02,700
To je pomlčka a potom väčšia ako znak, tak aby sa šípkou.

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

133
00:10:05,840 --> 00:10:12,390
To bude skutočne vám uzol, ktorý sa kurzor ukazuje. Táto hodnota je o ďalšie.

134
00:10:12,390 --> 00:10:16,790
Takže namiesto toho, aby na hviezdičku a bodku, budete nahrádzať, že sa šípkou.

135
00:10:16,790 --> 00:10:24,820
Buďte veľmi opatrní, aby sa ubezpečil, že sa pokúsite použiť túto syntax.

136
00:10:33,550 --> 00:10:37,620
>> Teraz, keď máme kurzor, ak chceme, aby prístup k hodnote,

137
00:10:37,620 --> 00:10:40,450
predtým, sme mali kurzor-> next,

138
00:10:40,450 --> 00:10:46,260
ale pre prístup k hodnote na uzla, ktorý kurzor ukazuje na, sme jednoducho povedať

139
00:10:46,260 --> 00:10:48,070
node-> hodnota.

140
00:10:48,070 --> 00:10:53,600
Odtiaľ je to na dátový typ, čo sme definovali hodnoty a uzlov byť.

141
00:10:53,600 --> 00:10:59,620
Ak je to int uzol, potom kurzor-> hodnota je len bude číslo.

142
00:10:59,620 --> 00:11:04,870
Takže môžeme urobiť operácie na to, pozrite sa rovnosťou, priradiť jej rôzne hodnoty, atď

143
00:11:04,870 --> 00:11:11,090
Takže to, čo chcete robiť, keď chcete presunúť kurzor na ďalšiu osobu,

144
00:11:11,090 --> 00:11:15,270
môžete skutočne zmeniť hodnotu kurzora.

145
00:11:15,270 --> 00:11:19,340
Vzhľadom k tomu, kurzor je uzol ukazovateľ, môžete zmeniť aktuálnu adresu ukazovateľ

146
00:11:19,340 --> 00:11:23,890
na adresu ďalšieho uzla v zozname.

147
00:11:23,890 --> 00:11:28,930
To je len nejaký kód, kde by ste mohli iterácii.

148
00:11:28,930 --> 00:11:31,230
Kde mám komentár niečo urobiť,

149
00:11:31,230 --> 00:11:33,850
to, kde ste pravdepodobne bude prístup k hodnote

150
00:11:33,850 --> 00:11:37,850
alebo niečo do činenia s týmto konkrétnym uzla.

151
00:11:37,850 --> 00:11:43,050
Ak chcete začať ho, hovorím, že môj kurzor pôvodne

152
00:11:43,050 --> 00:11:48,430
bude ukazovať na prvý prvok v prepojenom zozname.

153
00:11:48,430 --> 00:11:52,910
A tak sa pred nami, som definoval to ako hlava uzla.

154
00:11:52,910 --> 00:11:57,610
>> Ako som už spomenul skôr, uvoľňovať je naozaj dôležité.

155
00:11:57,610 --> 00:12:02,440
Chcete, aby sa ubezpečil, že ste uvoľniť každý prvok v zozname, akonáhle ste skončil s ním.

156
00:12:02,440 --> 00:12:04,940
Keď nemusíte odkazovať niektoré z týchto ukazovateľov už,

157
00:12:04,940 --> 00:12:10,620
chcete, aby sa ubezpečil, že ste oslobodiť všetky tieto ukazovatele.

158
00:12:10,620 --> 00:12:14,460
Ale vy chcete byť veľmi opatrní v tom, že budete chcieť, aby sa zabránilo pretečeniu pamäte.

159
00:12:14,460 --> 00:12:25,080
Ak si zadarmo jeden človek predčasne, potom všetky ukazovatele, ktoré tento uzol odkazuje na

160
00:12:25,080 --> 00:12:26,900
sa bude stratená.

161
00:12:26,900 --> 00:12:32,070
Vráťme sa späť k osobe príklad, aby bolo trochu viac high stakes,

162
00:12:32,070 --> 00:12:49,600
poďme si týchto ľudí, s výnimkou v tomto prípade, že sa vznášajú nad jazerom s monštrom.

163
00:12:49,600 --> 00:12:53,200
Chceme sa uistiť, že vždy, keď sme uvoľnení, aby sme nestratili

164
00:12:53,200 --> 00:12:58,920
a pustil všetky uzly, ako sme v skutočnosti je oslobodil.

165
00:12:58,920 --> 00:13:05,730
Napríklad, ak ste boli jednoducho volať zadarmo na toho chlapa tu,

166
00:13:05,730 --> 00:13:15,350
potom by bola uvoľnená, ale potom všetky tieto ľudí by potom dôjsť k strate

167
00:13:15,350 --> 00:13:18,450
a oni by zaspať a spadnúť.

168
00:13:18,450 --> 00:13:24,900
Takže chceme, aby sa ubezpečil, že miesto, chceme zachovať odkaz na zvyšok.

169
00:13:37,630 --> 00:13:42,480
Naša hlava ukazovateľ, ktorý ukazuje na prvý prvok v zozname.

170
00:13:42,480 --> 00:13:49,990
Je to niečo ako lano kotevné prvej osobe.

171
00:13:52,870 --> 00:13:57,470
Čo budete chcieť robiť, keď ste uvoľnenie zoznam je mať -

172
00:13:57,470 --> 00:14:04,520
Ak chcete, aby sa uvoľnil prvý prvok prvý, potom môžete mať dočasný ukazovateľ

173
00:14:04,520 --> 00:14:07,370
že poukazuje na akýkoľvek prvý prvok je.

174
00:14:07,370 --> 00:14:11,420
Takže máte váš dočasný ukazovateľ tu.

175
00:14:11,420 --> 00:14:15,840
Tak, máme držať prvého uzla.

176
00:14:15,840 --> 00:14:18,930
A potom, pretože vieme, že prvý uzol bude oslobodený,

177
00:14:18,930 --> 00:14:24,890
potom môžeme presunúť lano, tento kotevné, naše hlavy,

178
00:14:24,890 --> 00:14:31,930
skutočne poukazujú na čokoľvek prvý ukazuje.

179
00:14:31,930 --> 00:14:38,760
Tak toto hlava skutočne odkazuje na druhý prvok teraz.

180
00:14:38,760 --> 00:14:43,980
Teraz sa môžu uvoľniť, čo je uložené v teplote,

181
00:14:43,980 --> 00:14:53,360
a tak sa môže odstrániť, že bez nej ohrozenia všetkých ostatných uzlov v našom zozname.

182
00:14:54,140 --> 00:15:05,020
Ďalším spôsobom, že by ste mohli urobiť to mohlo byť

183
00:15:05,020 --> 00:15:08,650
zakaždým, keď stačí uvoľniť posledný prvok v zozname

184
00:15:08,650 --> 00:15:11,010
pretože oni zaručené, že sa ukázal na čokoľvek.

185
00:15:11,010 --> 00:15:15,570
Takže vy ste mohli len uvoľniť tento, potom voľný tentoraz, potom bez tentoraz.

186
00:15:15,570 --> 00:15:21,900
To určite funguje, ale je trochu pomalší, pretože podľa povahy prepojených zoznamov,

187
00:15:21,900 --> 00:15:24,670
môžeme nielen okamžite skočiť do posledného.

188
00:15:24,670 --> 00:15:28,030
Musíme prejsť každý prvok v pripojenom zozname

189
00:15:28,030 --> 00:15:31,020
a skontrolujte, či že jeden ukazuje na NULL, skontrolujte zakaždým,

190
00:15:31,020 --> 00:15:33,780
a potom ešte raz dôjdeme na koniec, potom zadarmo, ktoré.

191
00:15:33,780 --> 00:15:40,270
Ak by ste mali urobiť tento proces, by si skutočne byť kontrola tu,

192
00:15:40,270 --> 00:15:44,190
kontrola tu, potom kontrola tu, uvoľňovať to,

193
00:15:44,190 --> 00:15:47,470
potom ísť späť, kontrola tu, kontrola tu, uvoľňovať to,

194
00:15:47,470 --> 00:15:49,660
kontrola tu, a potom uvoľňovať to.

195
00:15:49,660 --> 00:15:52,880
To si vyžaduje trochu viac času. Jo.

196
00:15:52,880 --> 00:15:59,060
>> [Študent] Bolo by možné, aby sa spájať zoznam, ktorý ukladá návratový ukazovateľ na koniec?

197
00:15:59,060 --> 00:16:01,320
To by určite bolo možné.

198
00:16:01,320 --> 00:16:08,340
Ak chcete zopakovať otázku, je možné mať prepojenú zoznam štruktúru

199
00:16:08,340 --> 00:16:12,490
tak, že si mať ukazovateľ smerujúce do konca prepojeného zoznamu?

200
00:16:12,490 --> 00:16:18,090
Povedal by som, že je to možné, a zakaždým, keď vložíte niečo do prepojeného zoznamu

201
00:16:18,090 --> 00:16:21,470
budete musieť aktualizovať tento ukazovateľ a podobné veci.

202
00:16:21,470 --> 00:16:26,640
Tie by mali uzla * chvost, napríklad.

203
00:16:26,640 --> 00:16:29,840
Ale keď ste vykonávanie tejto funkcii, musíte myslieť na kompromisov,

204
00:16:29,840 --> 00:16:32,700
Páči koľkokrát budem sa iterácia nad tým,

205
00:16:32,700 --> 00:16:36,100
ako ťažké ich bude sledovať z chvosta, rovnako ako hlava

206
00:16:36,100 --> 00:16:38,400
rovnako ako môj Iterator, a podobné veci.

207
00:16:40,730 --> 00:16:42,480
Znamená to, že -? >> [Študent] Jo.

208
00:16:42,480 --> 00:16:48,270
Je to možné, ale pokiaľ ide o návrhu rozhodnutia, budete musieť zvážiť možnosti.

209
00:16:53,850 --> 00:17:01,090
>> Tu je kostra kódu, ktorý by vám umožní uvoľniť každý prvok prepojeného zoznamu.

210
00:17:01,090 --> 00:17:05,460
Opäť, pretože som iterácie previazanom zoznamu, budem chcieť mať nejaký kurzora

211
00:17:05,460 --> 00:17:08,670
alebo Iterator.

212
00:17:08,670 --> 00:17:14,640
Sme iterácií, kým kurzor NULL.

213
00:17:14,640 --> 00:17:17,640
Nechcete, aby iterácii, kedy je kurzor na NULL

214
00:17:17,640 --> 00:17:20,579
pretože to znamená, že nie je nič v zozname.

215
00:17:20,579 --> 00:17:25,069
Takže tu som vytvoriť dočasnú uzla *

216
00:17:25,069 --> 00:17:29,610
poukazuje na to, čo som za zváženie, je prvý z môjho zoznamu,

217
00:17:29,610 --> 00:17:35,340
a potom som pohnúť kurzorom dopredu 1 a potom voľný, čo som mal v režime dočasného uskladnenia.

218
00:17:38,460 --> 00:17:43,650
>> Teraz sa dostávame k vloženiu do prepojených zoznamov.

219
00:18:00,200 --> 00:18:09,660
Mám tri uzly v mojej prepojeného zoznamu, a poďme sa jednoduchom prípade

220
00:18:09,660 --> 00:18:18,970
tam, kde chceme vložiť ďalšie uzol na konci nášho prepojeného zoznamu.

221
00:18:18,970 --> 00:18:25,980
K tomu, všetko, čo bude robiť je, že sme sa prejsť

222
00:18:25,980 --> 00:18:32,100
zistiť, kde prúd koniec prepojeného zoznamu je, tak podľa toho, uzol ukazuje na NULL -

223
00:18:32,100 --> 00:18:33,850
že je to jedno -

224
00:18:33,850 --> 00:18:37,260
a potom povedať, vlastne, toto je nebude posledný uzol;

225
00:18:37,260 --> 00:18:39,830
sme vlastne bude mať inú.

226
00:18:39,830 --> 00:18:46,260
Takže budeme mať tento súčasný jeden bod k tomu, čo sme vkladanie.

227
00:18:46,260 --> 00:18:50,080
Takže teraz to červené osoba tu stáva posledný uzol v prepojenom zozname.

228
00:18:50,080 --> 00:18:56,080
A tak charakteristický posledného uzla v prepojenom zozname je, že sa poukazuje na NULL.

229
00:18:56,080 --> 00:19:09,380
Takže to, čo by sme mali urobiť, je nastaviť túto červenú chlapa ukazovateľ na NULL. Tam.

230
00:19:09,380 --> 00:19:25,370
>> Ale čo keď chceme vložiť uzol medzi druhým a tretím jeden?

231
00:19:25,370 --> 00:19:28,960
To človek nie je tak jednoduché, pretože chceme, aby sa ubezpečil

232
00:19:28,960 --> 00:19:34,290
že nepúšťaj žiadneho uzla v našej prepojeného zoznamu.

233
00:19:34,290 --> 00:19:43,450
Čo by sme mali urobiť, je uistiť, že sme ukotviť, aby sme sa každé z nich.

234
00:19:43,450 --> 00:19:49,900
Napríklad, povedzme túto druhú možnosť.

235
00:19:49,900 --> 00:19:54,390
Ak ste povedal druhý teraz ukazuje na túto novú

236
00:19:54,390 --> 00:20:02,520
a ste práve urobil ukazovateľ tam, potom by to bolo za následok ten chlap strate

237
00:20:02,520 --> 00:20:07,830
pretože tam nie je žiadny odkaz na neho.

238
00:20:07,830 --> 00:20:18,970
Namiesto toho - budem kresliť to znova. Ospravedlňte moje umelecké schopnosti.

239
00:20:18,970 --> 00:20:26,570
Vieme, že nemôžeme len tak priamo pripojiť 2 do nového.

240
00:20:26,570 --> 00:20:30,480
Musíme sa uistiť, že sme sa držať na posledný.

241
00:20:30,480 --> 00:20:39,200
Čo by sme mohli chcieť urobiť, je mať dočasný ukazovateľ

242
00:20:39,200 --> 00:20:42,650
na prvok, ktorý ich bude pripojená na.

243
00:20:42,650 --> 00:20:45,140
Takže máme dočasný ukazovateľ tam.

244
00:20:45,140 --> 00:20:50,780
Pretože vieme, že to tretie je držaný sledovať,

245
00:20:50,780 --> 00:20:53,680
2 môže teraz prepojiť do nášho nového.

246
00:20:53,680 --> 00:20:57,490
A ak táto nová červená chlap bude medzi 2 a 3,

247
00:20:57,490 --> 00:21:05,550
potom to, čo je ten chlap je ukazovateľ bude ukazovať na? >> [Študent] Temp.

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

249
00:21:07,490 --> 00:21:15,430
Takže táto červená chlap ďalšie hodnota bude tepl.

250
00:21:26,090 --> 00:21:33,010
Keď ste vložením do prepojených zoznamov, videli sme, že by sme mohli

251
00:21:33,010 --> 00:21:38,260
ľahko pridať niečo do konca vytvorením dočasnej poľa,

252
00:21:38,260 --> 00:21:42,850
alebo ak sme chceli pridať niečo do stredu nášho poľa,

253
00:21:42,850 --> 00:21:46,810
potom by to trvať trochu viac prešľapuje.

254
00:21:46,810 --> 00:21:50,240
Ak chcete, napríklad, majú zoradená prepojeného zoznamu,

255
00:21:50,240 --> 00:21:54,880
potom sa budete musieť trochu zvažovať náklady a prínosy, ktoré

256
00:21:54,880 --> 00:21:59,720
pretože ak chcete mať zoradené poľa, to znamená, že zakaždým, keď vložíte do neho,

257
00:21:59,720 --> 00:22:01,630
to bude trvať trochu dlhšie.

258
00:22:01,630 --> 00:22:05,500
Avšak, ak chcete, aby neskôr, až nájdeme budeme chcieť,

259
00:22:05,500 --> 00:22:10,280
Hľadanie pomocou prepojeného zoznamu, potom to môže byť jednoduchšie, ak budete vedieť, že je všetko v poriadku.

260
00:22:10,280 --> 00:22:15,340
Takže možno budete chcieť zvážiť náklady a prínosy, ktoré.

261
00:22:20,150 --> 00:22:27,740
>> Ďalším spôsobom, ako vložiť do prepojeného zoznamu je vložiť do začiatku zoznamu.

262
00:22:27,740 --> 00:22:34,700
Ak čerpáme kotvu tu - to je naša hlava -

263
00:22:34,700 --> 00:22:40,960
a potom títo ľudia s ňou súvisí,

264
00:22:40,960 --> 00:22:48,460
a potom máme nový uzol má byť vložená do začiatku,

265
00:22:48,460 --> 00:22:52,590
potom to, čo by sme mohli chcieť urobiť?

266
00:22:55,220 --> 00:23:03,580
Aký by mal byť v poriadku s len hovorím chcem prepojiť červenej k modrej,

267
00:23:03,580 --> 00:23:05,790
pretože to je prvý?

268
00:23:05,790 --> 00:23:08,570
Čo by sa stalo tu?

269
00:23:08,570 --> 00:23:12,130
Všetky z týchto troch by stratiť.

270
00:23:12,130 --> 00:23:14,140
Takže nechceme urobiť.

271
00:23:14,140 --> 00:23:21,430
Opäť sme sa dozvedeli, že musíme mať nejaký druh dočasného ukazovatele.

272
00:23:21,430 --> 00:23:34,470
Poďme si vybrať na dočasnú dobu bod na toho chlapa.

273
00:23:34,470 --> 00:23:39,640
Potom môžeme mať modrú jeden bod k tomu dočasné

274
00:23:39,640 --> 00:23:43,240
a potom červený bod na modrej.

275
00:23:43,240 --> 00:23:47,830
Dôvodom, prečo som využívala ľudí tu je, pretože my naozaj chceme vizualizovať

276
00:23:47,830 --> 00:23:53,180
drží na ľudí a uistiť sa, že máme odkaz na ne

277
00:23:53,180 --> 00:23:57,590
pred pustíme iného ruky alebo niečo také.

278
00:24:05,630 --> 00:24:10,650
>> Teraz, keď máme pocit lineárnymi zoznamy - ako by sme ich mohli vytvoriť odkazovaný zoznam

279
00:24:10,650 --> 00:24:15,090
a vytvoriť štruktúry pre ktoré sa skladá z definície typu pre uzol

280
00:24:15,090 --> 00:24:19,060
a potom uistiť sa, že máme ukazovateľ na hlave toho prepojeného zoznamu -

281
00:24:19,060 --> 00:24:23,210
akonáhle budeme mať to a vieme, ako prejsť cez pole,

282
00:24:23,210 --> 00:24:28,200
prístup k jednotlivým prvkom, vieme, ako vložiť a my vieme, ako sa oslobodiť,

283
00:24:28,200 --> 00:24:30,260
potom sa môžeme dostať do preklepy.

284
00:24:30,260 --> 00:24:38,150
Ako obvykle, máme časť otázok, na ktoré sa vám slúži k prevádzke s prepojenými zoznamy

285
00:24:38,150 --> 00:24:41,750
a rôzne štruktúry ako sú napríklad frontu a komínov.

286
00:24:41,750 --> 00:24:46,000
Potom sa môžeme presunúť do preklepy.

287
00:24:46,000 --> 00:24:55,170
>> Pravopisné chyby sa v distribučnej kóde niekoľko súborov významu.

288
00:24:55,170 --> 00:24:58,850
Najprv sme si všimli, že máme túto Makefile tu,

289
00:24:58,850 --> 00:25:03,040
ktoré sme naozaj nestretol.

290
00:25:03,040 --> 00:25:10,090
Ak ste sa pozreli dovnútra pset5 zložky, tak zistíte, že máte. H súbor,

291
00:25:10,090 --> 00:25:12,530
potom máte dve. C súbory.

292
00:25:12,530 --> 00:25:18,920
Čo to robí, je Makefile predtým, by sme stačí napísať make a potom názov programu

293
00:25:18,920 --> 00:25:25,550
a potom by sme videli všetky tieto argumenty a vlajok odovzdané do kompilátora.

294
00:25:25,550 --> 00:25:30,580
Čo Makefile robí, je nám umožňuje zostaviť niekoľko súborov naraz

295
00:25:30,580 --> 00:25:34,650
a odovzdať vlajok, ktoré chceme.

296
00:25:34,650 --> 00:25:41,300
Tu sme len vidieť, že je súbor hlavičke tu.

297
00:25:41,300 --> 00:25:43,730
Potom sme vlastne dva zdrojové súbory.

298
00:25:43,730 --> 00:25:47,520
Máme speller.c a dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Ste vítaní upraviť Makefile ak si budete priať.

300
00:25:54,560 --> 00:26:03,310
Všimnite si, že tu, ak zadáte čistý, potom to, čo robí, je v skutočnosti odstraňuje niečo

301
00:26:03,310 --> 00:26:06,340
že je jadro.

302
00:26:06,340 --> 00:26:09,190
Ak máš Segmentation fault, v podstate máte core dump.

303
00:26:09,190 --> 00:26:13,260
Tak to škaredý malý súbor sa zobrazí vo vašom adresári s názvom core.

304
00:26:13,260 --> 00:26:16,310
Budete chcieť odobrať, že aby bolo čistenie.

305
00:26:16,310 --> 00:26:20,940
To odstráni všetky spustiteľné súbory a Súbory o

306
00:26:27,900 --> 00:26:30,220
>> Poďme sa pozrieť do dictionary.h.

307
00:26:30,220 --> 00:26:34,410
To hovorí, že to deklaruje slovníka funkčnosť.

308
00:26:34,410 --> 00:26:39,530
Máme maximálnu dĺžku pre ľubovoľné slovo v slovníku.

309
00:26:39,530 --> 00:26:45,130
Povieme, že je to bude najdlhšia slovo. Je to dĺžky 45.

310
00:26:45,130 --> 00:26:48,900
Takže my nebudeme mať žiadne slovo, ktoré presahujú túto dĺžku.

311
00:26:48,900 --> 00:26:50,980
Tu musíme len funkčné prototypy.

312
00:26:50,980 --> 00:26:55,290
Nemáme vlastnú realizáciu, pretože to je to, čo budeme robiť v tomto PSet.

313
00:26:55,290 --> 00:26:59,940
Ale čo to robí, je, pretože máme čo do činenia s väčšími súbormi tu

314
00:26:59,940 --> 00:27:06,650
a funkčnosť vo väčšom meradle, je užitočné mať. h súbor

315
00:27:06,650 --> 00:27:11,290
tak, že niekto iný čítať, alebo pomocou kódu nemôže pochopiť, čo sa deje.

316
00:27:11,290 --> 00:27:17,910
A možno, že chcú zaviesť pokúsi, ak ste hash tabuľky alebo naopak.

317
00:27:17,910 --> 00:27:21,850
Potom by povedali mi zaťaženie funkcie,

318
00:27:21,850 --> 00:27:26,950
Vlastná realizácia bude líšiť, ale tento prototyp nebude meniť.

319
00:27:26,950 --> 00:27:33,280
Tu sme zistiť, ktorá vracia true, ak dané slovo v slovníku.

320
00:27:33,280 --> 00:27:39,800
Potom máme zaťaženia, ktorá v podstate trvá do slovníka súboru

321
00:27:39,800 --> 00:27:44,360
a potom načíta do nejakej dátovej štruktúry.

322
00:27:44,360 --> 00:27:47,500
Máme veľkosť, ktorá, ak je volaná, vracia veľkosť vášho slovníka,

323
00:27:47,500 --> 00:27:50,310
koľko slov sú uložené v nej,

324
00:27:50,310 --> 00:27:54,390
a potom uvoľnite, ktoré uvoľní všetku pamäť, ktorú možno vziať do

325
00:27:54,390 --> 00:27:57,900
a pritom svoj slovník.

326
00:28:01,070 --> 00:28:03,590
>> Poďme sa pozrieť na dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Je vidieť, že to vyzerá veľmi podobne ako dictionary.h, s výnimkou teraz to jednoducho má všetky tieto todos v ňom.

328
00:28:10,490 --> 00:28:16,980
A tak to je vaša práca. Nakoniec, budete vyplňovať speller.c so všetkými tohto kódu.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, pri spustení, nie je naozaj nič robiť,

330
00:28:21,540 --> 00:28:29,590
takže sa pozrieme na speller.c vidieť skutočné vykonávanie kontroly pravopisu.

331
00:28:29,590 --> 00:28:32,060
Aj keď nie ste bude editovať žiadnu z tohto kódu,

332
00:28:32,060 --> 00:28:38,050
je dôležité prečítať, pochopiť, keď je zaťaženie nazýva, keď som volať kontrolu,

333
00:28:38,050 --> 00:28:42,350
len pochopiť, zmapovať to, ako funkcia pracuje.

334
00:28:42,350 --> 00:28:49,860
Vidíme, že je to kontrola správne použitie.

335
00:28:49,860 --> 00:28:55,200
V podstate, keď niekto beží pravopisu, znamená to, že je to voliteľný

336
00:28:55,200 --> 00:29:00,950
pre ne prejsť do slovníka súboru, pretože tam to bude predvolený slovník súboru.

337
00:29:00,950 --> 00:29:05,410
A potom sa musí prejsť v texte byť spell-skontrolovať.

338
00:29:05,410 --> 00:29:11,410
rusage zaoberá času, pretože časť tohto PSet ktoré budeme zaoberať neskôr

339
00:29:11,410 --> 00:29:14,790
nie je len dostať fungujúci spell-checker pracovné

340
00:29:14,790 --> 00:29:17,190
ale v skutočnosti dostať, aby to bolo rýchlo.

341
00:29:17,190 --> 00:29:22,040
A tak potom to je miesto, kde rusage sa príde dovnútra

342
00:29:22,040 --> 00:29:28,740
Tu vidíme prvý hovor s jedným z našich dictionary.c súborov, ktorý je zaťaženie.

343
00:29:28,740 --> 00:29:34,720
Load vracia true alebo false - true na úspech, false pri výpadku.

344
00:29:34,720 --> 00:29:41,400
Takže ak slovníka nie je vložený správne, potom speller.c vráti 1 a ukončite.

345
00:29:41,400 --> 00:29:47,920
Ale ak to robí záťaž správne, potom to bude pokračovať.

346
00:29:47,920 --> 00:29:50,740
Budeme pokračovať, a my vidíme nejaký súbor I / O tu,

347
00:29:50,740 --> 00:29:56,210
kde to bude rokovaní s otvorením textového súboru.

348
00:29:56,210 --> 00:30:04,640
Tu, čo to robí, je kúzlo-kontroluje každé slovo v texte.

349
00:30:04,640 --> 00:30:09,270
Takže to, čo speller.c robí tu je iterácie každého slova v textovom súbore

350
00:30:09,270 --> 00:30:12,790
a potom kontrola je v slovníku.

351
00:30:24,680 --> 00:30:32,350
Tu máme logickú chybne, že uvidíme, či kontrola vráti pravda alebo nie.

352
00:30:32,350 --> 00:30:37,110
Ak slovo je vlastne v slovníku, potom kontrola vráti true.

353
00:30:37,110 --> 00:30:39,760
To znamená, že slovo nie je chybne.

354
00:30:39,760 --> 00:30:45,330
Takže chybne by bolo falošné, a to je dôvod, prečo máme bang tam, indikácie.

355
00:30:45,330 --> 00:30:56,320
Držíme ďalej, a potom to sleduje, koľko slov s chybným pravopisom

356
00:30:56,320 --> 00:30:58,910
sú v súbore.

357
00:30:58,910 --> 00:31:03,870
To pokračuje ďalej a zavrie súbor.

358
00:31:03,870 --> 00:31:09,250
Potom tu, hlási, koľko chybne napísané slová, ktoré mal.

359
00:31:09,250 --> 00:31:12,680
To počíta, ako dlho to trvalo načítať slovník,

360
00:31:12,680 --> 00:31:15,080
Ako dlho to trvalo pozrieť sa na to,

361
00:31:15,080 --> 00:31:18,510
Ako dlho to trvalo vypočítať veľkosť,

362
00:31:18,510 --> 00:31:21,260
ktorá, ako budeme pokračovať, by malo byť veľmi malé,

363
00:31:21,260 --> 00:31:25,390
a potom ako dlho to trvalo vyložiť slovník.

364
00:31:25,390 --> 00:31:27,700
Tu hore vidíme výzvu, aby ste si vyložili tu.

365
00:31:27,700 --> 00:31:52,690
Ak by sme skontrolovať veľkosť tu,

366
00:31:52,690 --> 00:31:59,050
potom vidíme, že je tu výzva k veľkosti, kde sa určuje veľkosť slovníka.

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

368
00:32:07,100 --> 00:32:10,920
>> Našou úlohou pre túto PSet je implementovať zaťaženie, ktoré načíta slovník

369
00:32:10,920 --> 00:32:15,480
Dátová štruktúra - podľa toho, čo si vyberiete, či už je to hash tabuľka alebo skúsiť -

370
00:32:15,480 --> 00:32:18,810
so slovami zo slovníka súboru.

371
00:32:18,810 --> 00:32:25,290
Potom máte veľkosť, ktorá vráti počet slov v slovníku.

372
00:32:25,290 --> 00:32:29,860
A ak sa rozhodnete zaťaženie v inteligentným spôsobom, potom veľkosť by mala byť celkom jednoduché.

373
00:32:29,860 --> 00:32:33,860
Potom ste zistiť, ktorý bude či dané slovo v slovníku.

374
00:32:33,860 --> 00:32:38,690
Takže speller.c prechádza v reťazci, a potom sa budete musieť skontrolovať, či reťazec

375
00:32:38,690 --> 00:32:41,610
je obsiahnutý vo vašej slovníku.

376
00:32:41,610 --> 00:32:46,750
Všimnite si, že vo všeobecnosti majú štandardné slovníky,

377
00:32:46,750 --> 00:32:53,020
ale v tomto Pset, v podstate akékoľvek slovník prešiel v ktoromkoľvek jazyku.

378
00:32:53,020 --> 00:32:57,040
Takže nemôžeme len predpokladať, že slovo je vnútri.

379
00:32:57,040 --> 00:33:03,090
Slovo foobar mohla byť definovaná v istom slovníku, ktorý míňame dovnútra

380
00:33:03,090 --> 00:33:07,920
A potom sme vyložiť, ktorá oslobodzuje slovník z pamäte.

381
00:33:07,920 --> 00:33:11,930
>> Najprv by som chcel ísť cez hash tabuľky metódy

382
00:33:11,930 --> 00:33:14,630
o tom, ako by sme mohli implementovať všetky z týchto štyroch funkcií,

383
00:33:14,630 --> 00:33:18,650
a potom pôjdem cez snaží metódy, ako vykonávať tieto štyri funkcie,

384
00:33:18,650 --> 00:33:22,720
a na konci rozhovoru o niektorých všeobecných tipov, keď ste robiť PSet

385
00:33:22,720 --> 00:33:27,870
a tiež, ako by ste mali byť schopní používať Valgrind pre kontrolu únikov pamäte.

386
00:33:27,870 --> 00:33:30,550
>> Poďme do hash tabuľky metódou.

387
00:33:30,550 --> 00:33:35,910
Hash tabuľka obsahuje zoznam segmentov.

388
00:33:35,910 --> 00:33:43,010
Každá hodnota, každé slovo, je ísť do jedného z týchto segmentov.

389
00:33:43,010 --> 00:33:53,200
Hash table ideálne rovnomerne distribuuje všetky tieto hodnoty, ktoré ste mimochodom v

390
00:33:53,200 --> 00:33:57,160
a potom vyplní ich do vedra tak, že každá lopata

391
00:33:57,160 --> 00:34:02,000
má asi rovnaký počet hodnôt v ňom.

392
00:34:02,000 --> 00:34:09,630
Štruktúra tabuľky hash, máme rad prepojených zoznamov.

393
00:34:09,630 --> 00:34:17,900
Čo máme urobiť, je, keď sme sa prejsť v hodnote, môžeme skontrolovať, kde táto hodnota by mala patriť,

394
00:34:17,900 --> 00:34:23,840
ktoré vedro patrí, a umiestnite ho do prepojeného zoznamu spojené s týmto lopatou.

395
00:34:23,840 --> 00:34:28,199
Tu, čo mám, je hash funkcie.

396
00:34:28,199 --> 00:34:31,320
Je to int hash tabuľky.

397
00:34:31,320 --> 00:34:38,540
Takže pre prvého segmentu, všetky celé čísla pod 10 ísť do prvého segmentu.

398
00:34:38,540 --> 00:34:42,190
Akékoľvek celé čísla nad 10, ale nižšia ako 20 zaobchádzajú do druhej,

399
00:34:42,190 --> 00:34:44,179
a potom sa tak ďalej a tak ďalej.

400
00:34:44,179 --> 00:34:52,370
Pre mňa, každý vedro zastupuje tieto čísla.

401
00:34:52,370 --> 00:34:59,850
Avšak, povedať, že som bol prejsť v 50, napríklad.

402
00:34:59,850 --> 00:35:07,490
Zdá sa, že prvé tri obsahujú rad desiatich čísel.

403
00:35:07,490 --> 00:35:12,570
Ale ja chcem, aby moje hash tabuľky, aby sa v nejakom druhu celých čísel,

404
00:35:12,570 --> 00:35:19,860
tak potom budem musieť odfiltrovať všetky čísla nad 30 do posledného segmentu.

405
00:35:19,860 --> 00:35:26,660
A tak potom by to mať za následok akési nevyvážené hash tabuľky.

406
00:35:31,330 --> 00:35:35,640
Ak chcete zopakovať, hash tabuľka je len rad lopát

407
00:35:35,640 --> 00:35:38,590
kde každý vedro je previazaný zoznam.

408
00:35:38,590 --> 00:35:43,730
A tak sa určiť, kde každá hodnota ide, čo vedro to ide do,

409
00:35:43,730 --> 00:35:46,260
budete chcieť, čo sa nazýva hash funkcie

410
00:35:46,260 --> 00:35:55,010
že vezme hodnotu a potom hovorí táto hodnota zodpovedá určitej nádoby.

411
00:35:55,010 --> 00:36:00,970
Takže hore v tomto príklade, moja hashovacie funkcie sa každú hodnotu.

412
00:36:00,970 --> 00:36:03,020
Je kontrolované, či to bolo menej ako 10.

413
00:36:03,020 --> 00:36:05,360
Ak to bolo, to by dať do prvého segmentu.

414
00:36:05,360 --> 00:36:08,910
Skontroluje, či je to menej ako 20, dá to do druhého, ak platí,

415
00:36:08,910 --> 00:36:12,880
kontroluje, či je to menej ako 30, a potom ju umiestni do tretieho vedra,

416
00:36:12,880 --> 00:36:16,990
a potom všetci ostatní len patrí do štvrtej vedra.

417
00:36:16,990 --> 00:36:20,110
Takže zakaždým, keď majú hodnotu, vaše hashovacie funkcie

418
00:36:20,110 --> 00:36:25,420
bude klásť túto hodnotu do príslušného vedra.

419
00:36:25,420 --> 00:36:32,430
Hashovacie funkcie v podstate potrebuje vedieť, koľko vedierka máte.

420
00:36:32,430 --> 00:36:37,960
Vaša veľkosť hash tabuľky, počet segmentov, ktoré máte,

421
00:36:37,960 --> 00:36:41,190
že to bude pevné číslo, ktoré je na vás, pre vás sa rozhodnúť,

422
00:36:41,190 --> 00:36:43,590
ale to bude stanovený počet.

423
00:36:43,590 --> 00:36:51,840
Takže vaše hash funkcie bude spoliehať na to určiť, ktorý lyžice každý kľúč ide do

424
00:36:51,840 --> 00:36:54,450
také, že je to rovnomerne.

425
00:36:56,150 --> 00:37:03,820
Podobne ako naše vykonávanie súvisiacich zoznamov, teraz každý uzol v hash tabuľke

426
00:37:03,820 --> 00:37:07,000
bude skutočne mať typu char.

427
00:37:07,000 --> 00:37:14,340
Takže máme char pole s názvom Slovo a potom ešte ukazovateľ na ďalší uzol,

428
00:37:14,340 --> 00:37:19,010
čo dáva zmysel, pretože to bude spájať zoznam.

429
00:37:19,010 --> 00:37:24,350
Pamätáš, keď sme sa spojil zoznamy, urobil som uzla * s názvom hlava

430
00:37:24,350 --> 00:37:31,060
ktorý bol s poukazom na prvom uzla v prepojenom zozname.

431
00:37:31,060 --> 00:37:34,020
Ale pre naše hash tabuľky, pretože máme niekoľko prepojených zoznamov,

432
00:37:34,020 --> 00:37:37,520
to, čo chceme, je chceme, aby náš hash table byť ako, "Čo je to vedro?"

433
00:37:37,520 --> 00:37:43,340
Lopata je len zoznam uzlov ukazovateľov,

434
00:37:43,340 --> 00:37:50,620
a tak každý prvok v segmente je vlastne ukazuje na jeho zodpovedajúce prepojeného zoznamu.

435
00:37:56,180 --> 00:38:01,520
Ak sa chcete vrátiť k tomuto schémy, uvidíte, že vedierka samotné sú šípky,

436
00:38:01,520 --> 00:38:06,980
nie skutočné uzly.

437
00:38:11,680 --> 00:38:16,420
Jednou zo základných vlastností hašovacia funkcia je, že sú deterministické.

438
00:38:16,420 --> 00:38:19,440
To znamená, že ak ste hash číslo 2,

439
00:38:19,440 --> 00:38:22,270
by mal vždy vrátiť rovnaký vedro.

440
00:38:22,270 --> 00:38:26,440
Každý hodnota, ktorá ide do hash funkcie, ak by sa opakovali,

441
00:38:26,440 --> 00:38:29,690
musí dostať rovnaký index.

442
00:38:29,690 --> 00:38:34,210
Takže vaše hash funkcia vracia index poľa

443
00:38:34,210 --> 00:38:38,530
kde táto hodnota patrí.

444
00:38:38,530 --> 00:38:41,790
Ako som už spomenul predtým, je stanovená počet segmentov,

445
00:38:41,790 --> 00:38:49,630
a tak si index, ktorý sa vrátiť musí byť menšia, než je počet segmentov

446
00:38:49,630 --> 00:38:52,680
ale väčšie ako 0.

447
00:38:52,680 --> 00:39:00,780
Dôvodom, prečo sme hašovacia funkcia miesto len jednej prepojeného zoznamu

448
00:39:00,780 --> 00:39:09,290
alebo jeden jediný pole je to, že chceme byť schopný skočiť do určitej časti najľahšie

449
00:39:09,290 --> 00:39:11,720
ak poznáme charakteristiku hodnoty -

450
00:39:11,720 --> 00:39:14,760
namiesto toho, aby museli prehľadávať celého slovníka,

451
00:39:14,760 --> 00:39:18,320
budú môcť prejsť na určité časti nej.

452
00:39:19,880 --> 00:39:24,440
Váš hash funkcia by mala brať do úvahy, že v ideálnom prípade,

453
00:39:24,440 --> 00:39:28,980
Každý vedro má približne rovnaký počet kľúčov.

454
00:39:28,980 --> 00:39:35,040
Vzhľadom k tomu, hash tabuľka je séria spojených zoznamov,

455
00:39:35,040 --> 00:39:38,480
potom spojené zoznamy sami budú mať viac ako jeden uzol.

456
00:39:38,480 --> 00:39:43,210
V predchádzajúcom príklade, dve rôzne čísla, aj keď neboli rovnaké,

457
00:39:43,210 --> 00:39:46,950
keď rozhádzané, vráti rovnaký index.

458
00:39:46,950 --> 00:39:53,620
Takže keď máte čo do činenia so slovami, jedno slovo, keď klasifikácii

459
00:39:53,620 --> 00:39:57,450
by byť rovnaká hodnota mriežky ako iné slovo.

460
00:39:57,450 --> 00:40:04,140
To je to, čo nazývame kolízii, keď máme uzol, ktorý, keď rozhádzané,

461
00:40:04,140 --> 00:40:09,610
spájať zoznam v tomto segmente nie je prázdny.

462
00:40:09,610 --> 00:40:14,180
Technika, ktorá nazývame je lineárne snímanie,

463
00:40:14,180 --> 00:40:22,550
kde idete do prepojeného zoznamu a potom nájsť miesto, kde chcete vložiť tento uzol

464
00:40:22,550 --> 00:40:25,520
pretože máte kolízii.

465
00:40:25,520 --> 00:40:28,070
Môžete vidieť, že tam by mohlo byť trade-off, že jo?

466
00:40:28,070 --> 00:40:33,760
Ak máte veľmi malú hash tabuľky, veľmi malý počet segmentov,

467
00:40:33,760 --> 00:40:36,380
potom budete mať veľa kolízií.

468
00:40:36,380 --> 00:40:40,460
Ale potom, ak urobíte veľkú hash tabuľky,

469
00:40:40,460 --> 00:40:44,110
budete pravdepodobne k minimalizácii kolízií,

470
00:40:44,110 --> 00:40:47,170
ale to bude veľmi veľké dátové štruktúry.

471
00:40:47,170 --> 00:40:49,310
Tam to bude kompromisy s tým.

472
00:40:49,310 --> 00:40:51,310
Takže keď ste vykonali PSet, skúste sa pohrať

473
00:40:51,310 --> 00:40:54,210
medzi možná robiť menšie hash tabuľky

474
00:40:54,210 --> 00:41:02,100
ale potom s vedomím, že to bude trvať trochu dlhšie prechádzať jednotlivé prvky

475
00:41:02,100 --> 00:41:04,270
z týchto prepojených zoznamov.

476
00:41:04,270 --> 00:41:09,500
>> Čo zaťaženie sa chystá urobiť, je iterácii každé slovo v slovníku.

477
00:41:09,500 --> 00:41:13,180
To prejde ukazovateľ na súbor slovníka.

478
00:41:13,180 --> 00:41:18,050
Takže budete využívať súboru I / O funkcií, ktoré ovládajú v pset4

479
00:41:18,050 --> 00:41:23,010
a iteráciu každé slovo v slovníku.

480
00:41:23,010 --> 00:41:26,620
Ak každé slovo v slovníku, aby sa stal nový uzol,

481
00:41:26,620 --> 00:41:32,730
a budete umiestniť každý z týchto uzlov vnútri vášho slovníka dátové štruktúry.

482
00:41:32,730 --> 00:41:36,560
Kedykoľvek dostanete nové slovo, viete, že to bude stáť uzol.

483
00:41:36,560 --> 00:41:46,590
Takže môžete ísť hneď a malloc uzla ukazovateľ pre každú novú slovo, ktoré ste.

484
00:41:46,590 --> 00:41:52,610
Tu som volá moje uzla ukazovateľ new_node a ja mallocing čo? Veľkosť uzla.

485
00:41:52,610 --> 00:41:59,190
Potom si prečítať aktuálne reťazec zo súboru, pretože slovník je v skutočnosti uložená

486
00:41:59,190 --> 00:42:03,340
slovom a potom nový riadok, čo môžeme využiť

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

488
00:42:06,520 --> 00:42:10,280
pričom súbor je slovník súbor, ktorý sme prešiel v roku,

489
00:42:10,280 --> 00:42:18,900
tak to skenuje súbor pre reťazce a miesta, ktoré reťazec do posledného argumentu.

490
00:42:18,900 --> 00:42:26,890
Ak si spomeniete, späť k jednému z prednášok, keď sme išli cez

491
00:42:26,890 --> 00:42:29,320
a druh lúpané vrstvy späť na knižnici CS50,

492
00:42:29,320 --> 00:42:33,430
Videli sme implementáciu fscanf tam.

493
00:42:33,430 --> 00:42:37,700
Ak sa chcete vrátiť do fscanf, máme súbor, ktorý sme čítanie z,

494
00:42:37,700 --> 00:42:42,570
hľadáme pre reťazec v tomto súbore, a potom sme uvedení do

495
00:42:42,570 --> 00:42:48,340
tu mám new_node-> slovo, pretože new_node je uzol ukazovateľ,

496
00:42:48,340 --> 00:42:50,380
nie je aktuálny uzol.

497
00:42:50,380 --> 00:42:57,100
Takže hovorím new_node, chcem ísť do uzla, že to ukazuje na

498
00:42:57,100 --> 00:43:01,190
a potom priradiť túto hodnotu na slovo.

499
00:43:01,190 --> 00:43:08,540
Chceme, aby potom toto slovo a vložte ho do hash tabuľky.

500
00:43:08,540 --> 00:43:13,750
Uvedomte si, že sme urobili new_node uzla ukazovateľ

501
00:43:13,750 --> 00:43:18,230
pretože budeme chcieť vedieť, čo adresa tohto uzla je

502
00:43:18,230 --> 00:43:23,940
keď sa vložiť do preto, že štruktúra uzlov samotných, v struct,

503
00:43:23,940 --> 00:43:26,380
je to, že majú ukazovateľ na nový uzol.

504
00:43:26,380 --> 00:43:30,820
Takže to, čo je adresa tohto uzla ísť poukázať na?

505
00:43:30,820 --> 00:43:34,550
Táto adresa bude new_node.

506
00:43:34,550 --> 00:43:42,140
Dáva to zmysel, prečo robíme new_node uzla * na rozdiel od uzla?

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

508
00:43:45,700 --> 00:43:52,840
Máme slovo. Táto hodnota je new_node-> slovo.

509
00:43:52,840 --> 00:43:55,970
, Ktorý obsahuje slovo zo slovníka, ktoré chceme na vstup.

510
00:43:55,970 --> 00:44:00,210
Takže to, čo chceme urobiť, je chceme nazývať našu hash funkcie na tomto reťazci

511
00:44:00,210 --> 00:44:03,780
pretože naše hash funkcie má v reťazci a vráti nám celé číslo,

512
00:44:03,780 --> 00:44:12,090
kde, že číslo je index, kde Hashtable v tomto indexe predstavuje tento vedro.

513
00:44:12,090 --> 00:44:18,260
Chceme, aby sa tento index a potom ísť do toho indexu hash tabuľky

514
00:44:18,260 --> 00:44:26,960
a potom použiť tento spájať zoznam pre vloženie uzla na new_node.

515
00:44:26,960 --> 00:44:31,950
Pamätajte si, že sa však sa rozhodnete vložiť svoje uzol,

516
00:44:31,950 --> 00:44:34,370
či už je to v stredu, ak chcete radiť ho

517
00:44:34,370 --> 00:44:39,650
alebo na začiatku alebo na konci, len sa uistite, že vaša posledná uzol vždy ukazuje na NULL

518
00:44:39,650 --> 00:44:46,730
pretože to je jediný spôsob, ako vieme, kde posledný prvok nášho prepojeného zoznamu je.

519
00:44:50,790 --> 00:44:59,710
>> Ak je veľkosť celé číslo, ktoré predstavuje počet slov v slovníku,

520
00:44:59,710 --> 00:45:03,060
potom jeden spôsob, ako to urobiť, je to, že vždy, keď sa nazýva veľkosť

521
00:45:03,060 --> 00:45:05,840
prejdeme každý prvok v našej hašovacia tabuľke

522
00:45:05,840 --> 00:45:09,410
a potom určiť iteráciou každého prepojeného zoznamu v hash tabuľke

523
00:45:09,410 --> 00:45:13,770
a potom vypočítať dĺžku, že zvýšenie našej čítač 1 do 1.

524
00:45:13,770 --> 00:45:16,580
Ale zakaždým, keď veľkosť sa nazýva, že to bude trvať dlho

525
00:45:16,580 --> 00:45:22,120
pretože budeme mať lineárne snímanie každý spájať zoznam.

526
00:45:22,120 --> 00:45:30,530
Namiesto toho, to bude oveľa jednoduchšie, ak budete mať prehľad o tom, koľko slov sú odovzdávané palcov

527
00:45:30,530 --> 00:45:36,330
Takže ak ste napríklad počítadlo priamo vo Vašom zaťaženie funkcie

528
00:45:36,330 --> 00:45:42,430
to, že aktualizácia je to potrebné, potom čítač, ak ju nastaviť na globálne premenné,

529
00:45:42,430 --> 00:45:44,930
budú môcť byť prístupné veľkosti.

530
00:45:44,930 --> 00:45:51,450
Takže to, čo veľkosť by jednoducho urobiť, je v jednej línii, stačí sa vrátiť hodnotu čítača,

531
00:45:51,450 --> 00:45:55,500
veľkosť slovníka, ktorý ste už zaoberal v zaťažení.

532
00:45:55,500 --> 00:46:05,190
To je to, čo som mal na mysli, keď som hovoril, že keď sa rozhodnete zaťaženie v užitočné spôsobom,

533
00:46:05,190 --> 00:46:08,540
potom veľkosť bude celkom jednoduché.

534
00:46:08,540 --> 00:46:11,350
>> Takže teraz sme si to overiť.

535
00:46:11,350 --> 00:46:15,960
Teraz máme čo do činenia so slovami zo súboru vstupného textu,

536
00:46:15,960 --> 00:46:19,910
a tak budeme mali overovať, či všetky tie vstupných slov

537
00:46:19,910 --> 00:46:22,520
sú vlastne v slovníku, alebo nie.

538
00:46:22,520 --> 00:46:26,520
Podobne ako Scramble, chceme, aby pre prípad necitlivosti.

539
00:46:26,520 --> 00:46:32,110
Chcete, aby sa ubezpečil, že všetky slová prešiel v roku, aj keď sú zmiešaný prípad,

540
00:46:32,110 --> 00:46:37,840
pri volaní sa sláčikovým porovnanie, sú rovnocenné.

541
00:46:37,840 --> 00:46:42,450
Slová v súboroch slovníka textového sú vlastne všetci malá.

542
00:46:42,450 --> 00:46:49,280
Ďalšia vec je, že môžete predpokladať, že každé slovo prešiel v roku, každý reťazec,

543
00:46:49,280 --> 00:46:53,200
sa bude buď v abecednom alebo obsahujú apostrofy.

544
00:46:53,200 --> 00:46:58,010
Apostrofy sa bude platné slová v našom slovníku.

545
00:46:58,010 --> 00:47:06,470
Takže ak máte slovo s apostrof S, to je skutočný legitímny slovo vo vašom slovníku

546
00:47:06,470 --> 00:47:11,650
že to bude jeden z uzlov vo vašom tabuľky hash.

547
00:47:13,470 --> 00:47:18,350
Kontrola pracuje s ak slovo existuje, potom to musí byť v našej hašovacia tabuľke.

548
00:47:18,350 --> 00:47:22,210
Ak je slovo v slovníku, potom všetky slová v slovníku, sú v hash tabuľke,

549
00:47:22,210 --> 00:47:26,560
tak sa poďme pozrieť na tohto slova v hash tabuľke.

550
00:47:26,560 --> 00:47:29,250
Vieme, že od tej doby sme realizovali náš hash funkcie

551
00:47:29,250 --> 00:47:38,420
tak, že každá jedinečná slovo vždy klasifikované na rovnakú hodnotu,

552
00:47:38,420 --> 00:47:43,340
potom vieme, že miesto prehľadávanie nášho celého hash tabuľky,

553
00:47:43,340 --> 00:47:48,310
môžeme skutočne nájsť prepojený zoznam, ktorý toto slovo by malo patriť k

554
00:47:48,310 --> 00:47:51,850
Ak to bolo v slovníku, potom by to bolo v tomto bloku.

555
00:47:51,850 --> 00:47:57,140
Čo môžeme robiť, keď slovo je názov nášho reťazca prešiel v,

556
00:47:57,140 --> 00:48:01,560
môžeme len hash, že slovo a pohľad na prepojenom zoznamu

557
00:48:01,560 --> 00:48:06,410
pri hodnote Hashtable [hash (slovo)].

558
00:48:06,410 --> 00:48:12,410
Odtiaľ, čo môžeme urobiť, je, že sme menší podmnožinu uzlov pre vyhľadávanie tohto slova,

559
00:48:12,410 --> 00:48:16,770
a tak môžeme prejsť prepojeného zoznamu, na príklade z predtým v návode,

560
00:48:16,770 --> 00:48:24,110
a potom volať reťazec nákupný na slovo všade tam, kde je kurzor ukazuje na,

561
00:48:24,110 --> 00:48:28,430
to slovo, a zistiť, či sú tieto.

562
00:48:30,280 --> 00:48:35,110
V závislosti na spôsobe, akým ste organizovať svoj hash funkcie,

563
00:48:35,110 --> 00:48:39,260
ak je to zoradená, mali by ste byť schopní vrátiť false niečo skôr,

564
00:48:39,260 --> 00:48:43,440
ale ak je to netriedený, potom budete chcieť pokračovať kríženia cez prepojeného zoznamu

565
00:48:43,440 --> 00:48:46,480
kým nenájdete posledný prvok zoznamu.

566
00:48:46,480 --> 00:48:53,320
A ak ste ešte nenašli slovo v čase, keď ste dosiahli konca prepojeného zoznamu,

567
00:48:53,320 --> 00:48:56,890
to znamená, že vaše slovo neexistuje v slovníku,

568
00:48:56,890 --> 00:48:59,410
a tak to slovo je neplatný,

569
00:48:59,410 --> 00:49:02,730
a kontrola by mal vrátiť false.

570
00:49:02,730 --> 00:49:09,530
>> Teraz sa dostávame k uvoľneniu, kde chceme oslobodiť všetky uzly, ktoré sme malloc'd,

571
00:49:09,530 --> 00:49:14,050
tak bez všetkých uzlov vnútri nášho stola mriežky.

572
00:49:14,050 --> 00:49:20,270
Budeme chcieť, aby iteráciu cez všetky prepojených zoznamov a zdarma všetky uzly v tom.

573
00:49:20,270 --> 00:49:29,350
Ak sa pozriete vyššie v návode na príklade, kde sme uvoľniť prepojeného zoznamu,

574
00:49:29,350 --> 00:49:35,140
potom budete chcieť zopakovať tento proces pre každý prvok v hash tabuľke.

575
00:49:35,140 --> 00:49:37,780
A ja budem ísť cez tento na konci návodu,

576
00:49:37,780 --> 00:49:46,600
ale Valgrind je nástroj, kde môžete vidieť, ak ste správne oslobodil

577
00:49:46,600 --> 00:49:53,600
každý uzol, ktorý ste malloc'd alebo čokoľvek iné, čo ste malloc'd, iné ukazovateľ.

578
00:49:55,140 --> 00:50:00,530
Tak to je hashovacie tabuľky, kde máme konečný počet segmentov

579
00:50:00,530 --> 00:50:09,220
a hash funkcie, ktorá bude mať hodnotu a potom priradiť túto hodnotu do určitej vedra.

580
00:50:09,220 --> 00:50:13,340
>> Teraz sa dostávame k pokusoch.

581
00:50:13,340 --> 00:50:18,750
Pokúsi druh vyzerajú takto, a ja tiež čerpať z príkladu.

582
00:50:18,750 --> 00:50:25,630
V podstate, máte celý rad potenciálnych listov,

583
00:50:25,630 --> 00:50:29,210
a potom kedykoľvek budete budovať slovo,

584
00:50:29,210 --> 00:50:36,490
že list môže byť spojené za slovníku na širokú škálu možností.

585
00:50:36,490 --> 00:50:40,840
Niektoré slová začať s C, ale potom pokračovať s,

586
00:50:40,840 --> 00:50:42,960
ale iní pokračujú s O, napríklad.

587
00:50:42,960 --> 00:50:51,090
Trie je spôsob vizualizácie všetkých možných kombinácií týchto slov.

588
00:50:51,090 --> 00:50:59,070
Trie sa bude sledovať sledu písmen, ktoré tvoria slová,

589
00:50:59,070 --> 00:51:08,280
odbočenie ak je to potrebné, keď je jedno písmeno nasledovať násobok písmen,

590
00:51:08,280 --> 00:51:16,630
a na konci uviesť v každom bode, či tento výraz je platná alebo nie

591
00:51:16,630 --> 00:51:30,120
pretože ak ste hláskovať slovo MAT, MA nemyslím si, že je platný slovo, ale MAT je.

592
00:51:30,120 --> 00:51:37,820
A tak v trie, by to znamenať, že po MAT, že je to vlastne platné slovo.

593
00:51:41,790 --> 00:51:48,590
Každý uzol v našom trie je vlastne bude obsahovať množstvo uzlov ukazovateľov,

594
00:51:48,590 --> 00:51:52,970
a budeme mať, konkrétne 27 z týchto uzlov ukazovateľov,

595
00:51:52,970 --> 00:52:00,550
jeden pre každé písmeno v abecede, rovnako ako Apostrof.

596
00:52:00,550 --> 00:52:10,450
Každý prvok v tomto poli je samo o sebe bude ukazovať do iného uzla.

597
00:52:10,450 --> 00:52:14,020
Takže, ak tento uzol je NULL, v prípade, že je to nič po tom,

598
00:52:14,020 --> 00:52:20,550
potom vieme, že tam žiadne ďalšie písmená v tomto slove poradí.

599
00:52:20,550 --> 00:52:26,950
Ale ak tento uzol nie je NULL, znamená to, že existuje viac písmen v tomto liste poradí.

600
00:52:26,950 --> 00:52:32,160
A potom ďalej, každý uzol označuje, či je to posledný znak slova, alebo nie.

601
00:52:38,110 --> 00:52:43,170
>> Poďme do príklade trie.

602
00:52:50,500 --> 00:52:58,340
Najprv som mať priestor pre 27 uzlov v tomto poli.

603
00:52:58,340 --> 00:53:03,200
Ak mám slovo BAR -

604
00:53:13,310 --> 00:53:15,370
Ak mám slovo BAR a chcem vložiť, že v,

605
00:53:15,370 --> 00:53:22,700
prvé písmeno je B, takže ak má trie je prázdny,

606
00:53:22,700 --> 00:53:29,910
B je druhé písmeno v abecede, takže budem voliť, aby to tu v tomto indexe.

607
00:53:29,910 --> 00:53:33,450
Budem mať B tu.

608
00:53:33,450 --> 00:53:42,400
B bude uzol, ktorý ukazuje na iného pole všetkých možných znakov

609
00:53:42,400 --> 00:53:45,870
že môže nasledovať po písmenom B.

610
00:53:45,870 --> 00:53:57,610
V tomto prípade, sa zaoberám slovom BAR, takže pôjdu sem.

611
00:54:02,000 --> 00:54:08,990
Po, mám list R, tak potom teraz ukazuje na vlastnú kombináciu,

612
00:54:08,990 --> 00:54:15,120
a potom R bude tu.

613
00:54:15,120 --> 00:54:22,470
BAR je úplné slovo, takže potom budem mať R bod do iného uzla

614
00:54:22,470 --> 00:54:33,990
, Ktorý hovorí, že toto slovo je platné.

615
00:54:36,010 --> 00:54:40,970
To je uzol tiež bude mať rad uzlov,

616
00:54:40,970 --> 00:54:45,260
ale tie by mohli byť NULL.

617
00:54:45,260 --> 00:54:49,080
Ale v podstate, môže pokračovať takhle.

618
00:54:49,080 --> 00:54:54,250
To bude trochu jasnejší, keď sme išli do iného príkladu,

619
00:54:54,250 --> 00:54:56,780
takže stačí mať so sebou tam.

620
00:54:56,780 --> 00:55:02,050
Teraz máme BAR vnútri nášho slovníka.

621
00:55:02,050 --> 00:55:05,980
Teraz, že máme slovo Baz.

622
00:55:05,980 --> 00:55:12,630
Začneme s B, a už máme B ako jeden z listov, ktoré v našom cenníku.

623
00:55:12,630 --> 00:55:15,170
To je nasledoval s A. Máme už.

624
00:55:15,170 --> 00:55:19,250
Ale potom miesto, máme Z nasledujúcej.

625
00:55:19,250 --> 00:55:25,490
Takže prvkom v našom poli sa bude Z,

626
00:55:25,490 --> 00:55:30,810
a tak, že jeden potom bude poukázať na inú platnú koniec slova.

627
00:55:30,810 --> 00:55:36,930
Takže vidíme, že keď budeme pokračovať cez B a potom,

628
00:55:36,930 --> 00:55:43,480
existujú dve rôzne možnosti v súčasnej dobe v našom slovníku pre slová, ktoré začínajú B a A.

629
00:55:49,650 --> 00:55:57,460
Povedzme, že by sme chceli vložiť slovo foobar.

630
00:55:57,460 --> 00:56:05,620
Potom by sme urobiť vstup na F.

631
00:56:05,620 --> 00:56:11,320
F je uzol, ktorý ukazuje na celú radu.

632
00:56:11,320 --> 00:56:22,790
Radi by sme vás O, choďte na O, O a potom spája do celého zoznamu.

633
00:56:22,790 --> 00:56:35,340
Mali by sme B a potom pokračovať, mali by sme a potom R.

634
00:56:35,340 --> 00:56:43,570
Takže foobar prechádza celú cestu dole, kým foobar je správne slovo.

635
00:56:43,570 --> 00:56:52,590
A tak potom by to bolo platné slovo.

636
00:56:52,590 --> 00:57:00,170
Teraz hovoria, naše ďalšie slovo v slovníku je vlastne slovo FOO.

637
00:57:00,170 --> 00:57:03,530
Mali by sme povedať, F. Čo bude nasledovať, F?

638
00:57:03,530 --> 00:57:06,190
Vlastne som už priestor pre O, takže budem pokračovať.

639
00:57:06,190 --> 00:57:09,150
Nepotrebujem, aby sa nový. Pokračovať.

640
00:57:09,150 --> 00:57:15,500
FOO je platná slovo v tomto slovníku, tak potom budem uvádzať

641
00:57:15,500 --> 00:57:21,660
že je platná.

642
00:57:21,660 --> 00:57:28,370
Keby som prestala som sekvenciu tam, to by bolo správne.

643
00:57:28,370 --> 00:57:33,050
Ale ak sme pokračovali v poradí od FOO až B

644
00:57:33,050 --> 00:57:39,750
a proste musel FOOB, FOOB nie je slovo, a to nie je uvedené ako platnú.

645
00:57:47,370 --> 00:57:57,600
V trie, ste každý uzol označujúci, či je to platné slovo, alebo nie,

646
00:57:57,600 --> 00:58:05,840
a potom každý uzol má aj rad 27 uzla ukazovateľov

647
00:58:05,840 --> 00:58:09,520
, Ktoré potom prejdite na uzly samotných.

648
00:58:09,520 --> 00:58:12,940
>> Tu je spôsob, ako na to, ako budete chcieť definovať to.

649
00:58:12,940 --> 00:58:17,260
Avšak, rovnako ako v hash tabuľke príklade, kde sme mali uzla * hlavu

650
00:58:17,260 --> 00:58:21,320
na označenie začiatku nášho prepojeného zoznamu, budeme tiež chcieť

651
00:58:21,320 --> 00:58:29,150
nejaký spôsob, ako vedieť, kde je počiatok nášho trie je.

652
00:58:29,150 --> 00:58:34,110
Niektorí ľudia hovoria, sa snaží stromy, a to je miesto, kde koreň pochádza.

653
00:58:34,110 --> 00:58:36,910
Takže chceme koreň nášho stromu, aby sa ubezpečil, že sme zostať uzemnený

654
00:58:36,910 --> 00:58:39,570
tam, kam naše trie je.

655
00:58:42,910 --> 00:58:46,300
Už sme trochu prešiel

656
00:58:46,300 --> 00:58:50,240
ako by ste mohli premýšľať o nakladaní každé slovo do slovníka.

657
00:58:50,240 --> 00:58:54,540
V podstate, pre každé slovo budete chcieť určiť iteráciou svojho trie

658
00:58:54,540 --> 00:58:59,590
a vedel, že každý prvok u detí - hovorili sme, že deti v tomto prípade -

659
00:58:59,590 --> 00:59:04,290
zodpovedá iným písmenom, budete chcieť skontrolovať tieto hodnoty

660
00:59:04,290 --> 00:59:08,320
v tomto konkrétnom indexe, ktorý zodpovedá písmeno.

661
00:59:08,320 --> 00:59:11,260
Takže myslieť celú cestu späť k Caesarovi a Vigenère,

662
00:59:11,260 --> 00:59:16,070
s vedomím, že každý list si môžete druh mapy späť na index abecedy,

663
00:59:16,070 --> 00:59:20,690
Rozhodne až Z bude celkom jednoduché mapovať abecedný list,

664
00:59:20,690 --> 00:59:25,200
ale bohužiaľ, apostrofy sú tiež prijímaný znak v slovách.

665
00:59:25,200 --> 00:59:31,650
Nie som si ani istý, čo ASCII hodnota je,

666
00:59:31,650 --> 00:59:39,250
tak na to, ak chcete nájsť index rozhodnúť, či chcete, aby to bolo buď prvý

667
00:59:39,250 --> 00:59:44,550
alebo posledný, budete musieť pevný kódované šek na ktoré

668
00:59:44,550 --> 00:59:48,930
a potom dať, že v indexe 26, napríklad.

669
00:59:48,930 --> 00:59:55,300
Takže potom ste kontrolou hodnoty u detí [i]

670
00:59:55,300 --> 00:59:58,400
kde [i] odpovedá na čokoľvek písmeno ste na.

671
00:59:58,400 --> 01:00:04,110
Ak je to NULL, to znamená, že nie je v súčasnej dobe prípadné listy

672
01:00:04,110 --> 01:00:08,150
vyplývajúce z predchádzajúceho sekvencie, takže budete chcieť malloc

673
01:00:08,150 --> 01:00:13,150
a vytvoriť nový uzol a mať deti, že [i] prejdite na ňu

674
01:00:13,150 --> 01:00:17,890
takže môžete vytvoriť - keď sme vložili list do obdĺžnika -

675
01:00:17,890 --> 01:00:23,680
Vďaka deťom non-NULL a bod do tohto nového uzla.

676
01:00:23,680 --> 01:00:28,340
Ale ak to nie je NULL, ako v našom prípade z FOO

677
01:00:28,340 --> 01:00:34,570
keď už sme mali foobar, budeme pokračovať,

678
01:00:34,570 --> 01:00:44,010
a my sa nikdy robiť nový uzol, ale len nastaviť is_word na hodnotu true

679
01:00:44,010 --> 01:00:47,790
Na konci tohto slova.

680
01:00:50,060 --> 01:00:55,340
>> Takže rovnako ako predtým, pretože tu máte čo do činenia s každým listom v čase,

681
01:00:55,340 --> 01:01:01,470
to bude pre vás jednoduchšie pre veľkosť, namiesto toho, aby výpočet

682
01:01:01,470 --> 01:01:06,910
a prejsť celý strom a vypočítať, koľko detí mám

683
01:01:06,910 --> 01:01:10,850
a potom odbočenie, spomenul koľko sú na ľavej strane a na pravej strane

684
01:01:10,850 --> 01:01:12,850
a podobné veci, to bude oveľa jednoduchšie pre vás

685
01:01:12,850 --> 01:01:16,220
ak ste práve sledovať, koľko slov ste tým, že do

686
01:01:16,220 --> 01:01:18,080
keď máte čo do činenia s nákladom.

687
01:01:18,080 --> 01:01:22,630
A potom sa to tak veľkosť môže len návrat globálne premenné veľkosti.

688
01:01:25,320 --> 01:01:28,530
>> Teraz sa dostávame k skontrolovať.

689
01:01:28,530 --> 01:01:33,920
Rovnakých štandardov ako predtým, kde chceme, aby pre prípad necitlivosti.

690
01:01:33,920 --> 01:01:40,400
Rovnako, my predpokladáme, že reťazce sú len abecedné znaky alebo apostrofy

691
01:01:40,400 --> 01:01:44,000
pretože deti je pole 27 dlhé,

692
01:01:44,000 --> 01:01:48,480
takže všetky písmená abecedy plus apostrof.

693
01:01:48,480 --> 01:01:53,800
Pre kontrolu toho, čo budete chcieť urobiť, je, že budete chcieť začať pri koreni

694
01:01:53,800 --> 01:01:58,440
pretože koreň bude ukazovať na pole, ktoré obsahuje

695
01:01:58,440 --> 01:02:01,630
všetkých možných východiskových písmen slova.

696
01:02:01,630 --> 01:02:03,680
Budeš začať tam,

697
01:02:03,680 --> 01:02:11,590
a potom budete kontrolovať, je táto hodnota NULL alebo nie,

698
01:02:11,590 --> 01:02:16,490
pretože ak je hodnota NULL, to znamená, že v slovníku nemá žiadne hodnoty

699
01:02:16,490 --> 01:02:21,480
ktoré obsahujú ten list v tomto konkrétnom poradí.

700
01:02:21,480 --> 01:02:24,970
Ak je to NULL, potom to znamená, že toto slovo je chybne hneď.

701
01:02:24,970 --> 01:02:27,110
Ale ak to nie je NULL, potom môžete pokračovať,

702
01:02:27,110 --> 01:02:34,090
povedať, že prvé písmeno je možné prvé písmeno v slove,

703
01:02:34,090 --> 01:02:40,630
tak teraz chcem skontrolovať, či druhý list, že sekvencie, je v mojom slovníku.

704
01:02:40,630 --> 01:02:46,540
Takže sa chystáte ísť do indexu deti na prvom uzle

705
01:02:46,540 --> 01:02:50,720
a skontrolujte, či druhý list existuje.

706
01:02:50,720 --> 01:02:57,440
Potom si opakovať, že proces skontrolovať, či postupnosť je platná alebo nie

707
01:02:57,440 --> 01:02:59,060
vo vašej trie.

708
01:02:59,060 --> 01:03:06,430
Kedykoľvek uzol deti na to, že indexových bodov na hodnotu NULL,

709
01:03:06,430 --> 01:03:10,710
Viete, že postupnosť neexistuje,

710
01:03:10,710 --> 01:03:16,230
ale potom, keď sa dostanete na koniec slova, ktoré ste vložili,

711
01:03:16,230 --> 01:03:20,070
potom chcete skontrolovať teraz, že som dokončil túto sekvenciu

712
01:03:20,070 --> 01:03:27,610
a zistil, že je v mojom trie, je to, že slovo platí, alebo nie?

713
01:03:27,610 --> 01:03:32,480
A potom sa budete chcieť skontrolovať, či, a to je, keď, ak ste zistili, že postupnosť,

714
01:03:32,480 --> 01:03:35,120
potom chcete skontrolovať, či slovo je platná alebo nie

715
01:03:35,120 --> 01:03:40,290
pretože Spomínam si v predchádzajúcom prípade, že som nakreslil, kde sme mali FOOB,

716
01:03:40,290 --> 01:03:48,410
, Ktorý bol platný sekvencie, ktoré sme našli, ale nebola skutočná platné slovo samo o sebe.

717
01:03:50,570 --> 01:03:59,000
>> Podobne, pre vyložiť v pokusoch, ktoré chcete uvoľniť všetky uzly vo vašom trie.

718
01:03:59,000 --> 01:04:04,790
Prepáčte. Podobne ako hash tabuľky, kde v vyložiť sme oslobodil všetky uzly,

719
01:04:04,790 --> 01:04:09,740
v pokusoch, ktoré chceme tiež uvoľniť všetky uzly.

720
01:04:09,740 --> 01:04:15,000
Uvoľniť bude skutočne fungovať najjednoduchšie zdola nahor

721
01:04:15,000 --> 01:04:19,290
pretože tieto sú v podstate spojené zoznamy.

722
01:04:19,290 --> 01:04:22,540
Takže chceme sa uistiť, že máme na všetky hodnoty

723
01:04:22,540 --> 01:04:25,700
a bez všetky z nich výslovne.

724
01:04:25,700 --> 01:04:28,840
Čo budete chcieť robiť, keď pracujete s trie

725
01:04:28,840 --> 01:04:35,640
je cestovať až na dno a voľný najnižšiu možnú uzol prvý

726
01:04:35,640 --> 01:04:39,190
a potom sa do všetkých týchto detí a potom bez všetkých tých,

727
01:04:39,190 --> 01:04:43,050
hore a potom zadarmo, atď

728
01:04:43,050 --> 01:04:48,790
Niečo ako zaoberajúca sa spodnou vrstvou trie prvý

729
01:04:48,790 --> 01:04:51,940
a potom ísť až hore, akonáhle ste oslobodil všetko.

730
01:04:51,940 --> 01:04:56,720
Toto je dobrý príklad, kde rekurzívne funkcie môže hodiť.

731
01:04:56,720 --> 01:05:03,830
Akonáhle oslobodil spodnú vrstvu vášho trie,

732
01:05:03,830 --> 01:05:08,000
potom volať vyložiť na to ostatné,

733
01:05:08,000 --> 01:05:13,620
Uistite sa, že ste uvoľniť každý mini -

734
01:05:13,620 --> 01:05:16,410
Môžete trochu predstaviť, že ako mini pokusov.

735
01:05:23,300 --> 01:05:28,990
Takže máte koreň tu.

736
01:05:30,840 --> 01:05:35,230
Ja len zjednodušiť tak, nemám k tomu 26 z nich.

737
01:05:37,250 --> 01:05:43,770
Takže budete mať tieto, a potom títo reprezentujú sekvencie slov

738
01:05:43,770 --> 01:05:54,620
kde všetky tieto malé kruhy sú listy, ktoré sú platné postupnosti písmen.

739
01:06:03,040 --> 01:06:07,160
Poďme pokračovať len trochu viac.

740
01:06:15,110 --> 01:06:25,750
Čo budete chcieť urobiť, je zadarmo spodnej tu a potom zadarmo tento

741
01:06:25,750 --> 01:06:31,640
a potom zadarmo to jeden na dne pred uvoľniť hornej jeden až sem

742
01:06:31,640 --> 01:06:38,180
pretože ak vás úplne zadarmo, niečo, čo v druhej úrovni tu,

743
01:06:38,180 --> 01:06:47,230
potom skutočne prídu túto hodnotu tu.

744
01:06:47,230 --> 01:06:54,780
To je dôvod, prečo je to dôležité v uvoľnenie pre trie, aby sa ubezpečil, že ste uvoľniť dno ako prvý.

745
01:06:54,780 --> 01:06:59,480
Čo budete chcieť urobiť, je povedať, pre každý uzol

746
01:06:59,480 --> 01:07:06,430
Chcem vyložiť všetky deti.

747
01:07:16,060 --> 01:07:22,140
>> Teraz, keď sme preč cez vyložiť na hash tabuľky metódy, ako aj spôsobu trie,

748
01:07:22,140 --> 01:07:27,020
budeme chcieť pozrieť na Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind spustiť s nasledujúcimi príkazmi.

750
01:07:29,640 --> 01:07:32,700
Máte Valgrind-V.

751
01:07:32,700 --> 01:07:40,960
Ste kontrola všetkých netesností pri spustení pravopisu, rovnako to určitý text

752
01:07:40,960 --> 01:07:46,980
pretože Speller potrebné, aby v textovom súbore.

753
01:07:46,980 --> 01:07:52,330
Takže Valgrind bude spustite program, povedať, koľko bytov si pridelené,

754
01:07:52,330 --> 01:07:57,150
koľko bytov si oslobodený, a to vám povie, či ste oslobodený len dosť

755
01:07:57,150 --> 01:07:58,930
alebo či ste to už dosť,

756
01:07:58,930 --> 01:08:02,850
alebo niekedy dokonca môžete cez-free, ako je voľný uzol, ktorý už bol oslobodený

757
01:08:02,850 --> 01:08:05,140
a tak sa vrátite chyby.

758
01:08:05,140 --> 01:08:11,600
Ak používate Valgrind, bude vám niektoré správy

759
01:08:11,600 --> 01:08:15,970
uvedie, či ste oslobodení buď menej než dosť, len dosť,

760
01:08:15,970 --> 01:08:19,609
alebo viac než dosť časov.

761
01:08:24,370 --> 01:08:30,410
>> Súčasťou tejto PSet, je to voliteľná napadnúť veľkú tabuľu.

762
01:08:30,410 --> 01:08:35,790
Ale keď máme čo do činenia s týmito dátovými štruktúrami

763
01:08:35,790 --> 01:08:40,689
je to celkom zábavné vidieť, ako rýchlo a ako efektívne vaše dátové štruktúry môže byť.

764
01:08:40,689 --> 01:08:44,490
Má vaše hash funkcie majú za následok veľa kolízií?

765
01:08:44,490 --> 01:08:46,300
Alebo je vaša veľkosť dát naozaj veľký?

766
01:08:46,300 --> 01:08:49,420
Má to trvať veľa času prejsť?

767
01:08:49,420 --> 01:08:54,800
V protokole o Speller, že výstupy, koľko času budete používať pre načítanie,

768
01:08:54,800 --> 01:08:57,700
kontrolovať, vykonávať veľkosti, a vyložiť,

769
01:08:57,700 --> 01:09:00,720
a tak tie sú uložené v The Big rade,

770
01:09:00,720 --> 01:09:03,600
kde môžete súťažiť proti svojim spolužiakom

771
01:09:03,600 --> 01:09:11,350
a niektorí zamestnanci sa vidieť, kto má najrýchlejší pravopisu.

772
01:09:11,350 --> 01:09:14,760
Jedna vec, že ​​by som chcel poznamenať, o hash tabuľky

773
01:09:14,760 --> 01:09:20,470
je to, že tam sú niektoré docela jednoduché hashovacie funkcie, ktoré by sme mohli myslieť.

774
01:09:20,470 --> 01:09:27,240
Napríklad, máte 26 vedrá, a tak každý vedro

775
01:09:27,240 --> 01:09:30,200
zodpovedá prvé písmeno v slove,

776
01:09:30,200 --> 01:09:35,229
ale že to bude mať za následok docela nevyvážené hash tabuľky

777
01:09:35,229 --> 01:09:40,979
pretože tam sú veľa menej slov, ktoré začínajú s X než štarte sa M, napríklad.

778
01:09:40,979 --> 01:09:47,890
Jeden spôsob, ako ísť o Speller je, ak chcete získať všetky ostatné funkcie dole,

779
01:09:47,890 --> 01:09:53,240
potom stačí použiť jednoduchý hash funkcie, aby mohli dostať váš kód beží

780
01:09:53,240 --> 01:09:58,650
a potom sa vrátiť späť a zmeniť veľkosť vašej hash tabuľky a definície.

781
01:09:58,650 --> 01:10:03,430
Existuje veľa zdrojov na internete pre hašovacia funkcia,

782
01:10:03,430 --> 01:10:08,250
a tak pre tento PSet je povolené výskum hash funkcie na internete

783
01:10:08,250 --> 01:10:15,560
o nejaké rady a inšpiráciu tak dlho, ako sa uistiť, citovať, kde ste získali.

784
01:10:15,560 --> 01:10:22,060
Rado sa stalo sa pozrieť a interpretovať niektoré hash funkcie, ktoré nájdete na internete.

785
01:10:22,060 --> 01:10:27,460
Späť na to, že môžete byť schopní zistiť, či niekto použil trie

786
01:10:27,460 --> 01:10:31,700
či je ich realizácia je rýchlejší ako váš hašovacia tabuľky alebo nie.

787
01:10:31,700 --> 01:10:35,290
Môžete predložiť veľkú tabuľu viackrát.

788
01:10:35,290 --> 01:10:37,660
To bude zaznamenávať vaše poslednú položku.

789
01:10:37,660 --> 01:10:44,300
Takže možno zmeníte funkciu hash a potom si uvedomí, že je to vlastne oveľa rýchlejšie

790
01:10:44,300 --> 01:10:46,780
alebo oveľa pomalší ako predtým.

791
01:10:46,780 --> 01:10:50,960
To je trochu zábavnou formou.

792
01:10:50,960 --> 01:10:57,190
Tam je vždy 1 alebo 2 zamestnanci, ktorí sa snažia, aby sa najpomalší možnú slovník,

793
01:10:57,190 --> 01:11:00,210
tak to je vždy zábavné sa pozerať na.

794
01:11:00,210 --> 01:11:07,630
>> Použitie pre PSet je spustiť pravopisu s voliteľným slovníka

795
01:11:07,630 --> 01:11:12,840
a potom povinný textový súbor.

796
01:11:12,840 --> 01:11:18,380
V predvolenom nastavení pri spustení pravopisu sa len textového súboru a neuvediete slovník,

797
01:11:18,380 --> 01:11:24,410
to bude používať slovník textový súbor, toho veľkého

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

799
01:11:27,920 --> 01:11:32,760
Že jeden má viac ako 100.000 slov.

800
01:11:32,760 --> 01:11:37,950
Majú tiež malý slovník, ktorý má podstatne menej slov

801
01:11:37,950 --> 01:11:40,730
že CS50 urobil pre vás.

802
01:11:40,730 --> 01:11:44,050
Avšak, môžete veľmi ľahko stačí si len vlastný slovník

803
01:11:44,050 --> 01:11:47,150
ak si len chcete pracovať v malých príkladoch -

804
01:11:47,150 --> 01:11:51,140
Napríklad, ak chcete použiť gdb a viete, že konkrétne hodnoty

805
01:11:51,140 --> 01:11:53,560
že chcete, aby vaše hash tabuľka mapuje na.

806
01:11:53,560 --> 01:12:00,430
Takže stačí vytvoriť svoj vlastný textový súbor len s barom, bázou, foo, a foobar,

807
01:12:00,430 --> 01:12:04,860
aby to v textovom súbore, oddeliť tie, každý s 1 riadok,

808
01:12:04,860 --> 01:12:12,670
a potom vytvoriť svoj vlastný textový súbor, ktorý doslova obsahuje len možno 1 alebo 2 slová

809
01:12:12,670 --> 01:12:15,950
takže presne viete, čo výstup by mal byť.

810
01:12:15,950 --> 01:12:21,870
Niektoré z ukážkových súborov textových, že Big Board pri spustení úlohy bude kontrolovať

811
01:12:21,870 --> 01:12:25,580
sú Vojna a mier a Jane Austen román alebo niečo také.

812
01:12:25,580 --> 01:12:30,450
Takže, keď ste začínal, je to oveľa jednoduchšie, aby vaše vlastné textové súbory

813
01:12:30,450 --> 01:12:34,160
ktoré obsahujú len pár slov alebo možno 10

814
01:12:34,160 --> 01:12:38,280
takže môžete predvídať, čo výsledok by mal byť

815
01:12:38,280 --> 01:12:42,880
a overiť si to proti tomu, aby viac kontrolovanej príklad.

816
01:12:42,880 --> 01:12:45,820
A tak od tej doby máme čo do činenia s predpovedanie a kreslenie veci okolo,

817
01:12:45,820 --> 01:12:48,690
raz chcem povzbudiť, aby ste sa používať ceruzku a papier

818
01:12:48,690 --> 01:12:50,700
pretože je to naozaj ti pomôže s týmto -

819
01:12:50,700 --> 01:12:55,620
kreslenie šípok, ako hash tabuľka alebo ako sa vaše trie vyzerá,

820
01:12:55,620 --> 01:12:57,980
keď ste uvoľnenie niečo, kde sa šípky idete,

821
01:12:57,980 --> 01:13:01,730
sa držíš na dosť, vidíte nejaké odkazy mizne

822
01:13:01,730 --> 01:13:05,750
a pádu do priepasti unikli pamäte.

823
01:13:05,750 --> 01:13:11,070
Takže, prosím, skúste nakresliť veci ešte predtým, než sa dostanete na písanie kódu dole.

824
01:13:11,070 --> 01:13:14,520
Nakreslite veci tak, že ste pochopili, ako sa veci chodiť do práce

825
01:13:14,520 --> 01:13:22,750
pretože potom som zaručiť, že budete spúšťať do menej ukazovateľ muddles tam.

826
01:13:24,270 --> 01:13:25,910
>> Dobrá.

827
01:13:25,910 --> 01:13:28,780
Chcem vám popriať veľa šťastia s týmto PSet.

828
01:13:28,780 --> 01:13:31,980
Je to asi najťažšia.

829
01:13:31,980 --> 01:13:40,360
Tak skúste začať čoskoro, kresliť veci, kresliť veci, a veľa šťastia.

830
01:13:40,360 --> 01:13:42,980
To bolo Návod 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]