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šichni, a vítejte na Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 je Pravopisné chyby, ve kterém budeme dělat pravopisu.

6
00:00:17,400 --> 00:00:21,030
Spell-dáma, jsou nesmírně důležité.

7
00:00:21,030 --> 00:00:23,390
Má to někdy stalo?

8
00:00:23,390 --> 00:00:27,170
Můžete pracovat velmi, velmi hromadí na papíře pro střet

9
00:00:27,170 --> 00:00:33,120
a pak ještě nakonec dostat velmi záře Rade jako D nebo D =

10
00:00:33,120 --> 00:00:39,390
a všichni proto, že jste liverwurst spoiler v velryb širokém slova.

11
00:00:39,390 --> 00:00:44,710
Ano, korektury vašich papriky je věc, maximální impotence.

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

13
00:00:49,140 --> 00:00:56,260
Byl jsem jednou řekl můj mučitel stupně Sith, že bych nikdy dostat do dobrého kolegu.

14
00:00:56,260 --> 00:01:00,250
A to je vše, co jsem kdy chtěl, to je všechno, každý kluk chce v mém věku,

15
00:01:00,250 --> 00:01:04,569
Jen dostat se do dobré kolegovi.

16
00:01:04,569 --> 00:01:12,720
A ne jen tak ledajaký kolega. Ne Chtěl jsem jít do slonoviny Právní kolegovi.

17
00:01:12,720 --> 00:01:18,360
Takže pokud jsem to zlepšení, by šel se mé sny o jít na Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, nebo Prison - víte, ve věznici, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Tak jsem si sám sobě pravopisu.

20
00:01:25,170 --> 00:01:29,380
To je trochu výpis z jedné z mých nejoblíbenějších mluvené slovo umělců, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Každopádně, jak říká, že je důležité mít pravopisu je velmi důležité.

22
00:01:34,630 --> 00:01:39,440
>> Takže vítejte na Walkthrough 5, ve kterém se bude hovořit o pset5: pravopisné chyby,

23
00:01:39,440 --> 00:01:44,300
, ve kterém budeme dělat naše vlastní pravopisu.

24
00:01:44,300 --> 00:01:50,880
Nástrojů pro tento týden, distribuce kód, bude důležité, aby se na

25
00:01:50,880 --> 00:01:54,950
jen pochopit různé funkce, které váš slovník bude mít.

26
00:01:54,950 --> 00:02:01,500
Jsme vlastně bude mít více. C. souborů, které dohromady tvoří naši PSet.

27
00:02:01,500 --> 00:02:05,420
A tak hledá prostřednictvím různých aspektech, i když jsme vlastně ne pro editaci

28
00:02:05,420 --> 00:02:10,770
jeden ze souborů, speller.c, věděl, jak to funguje ve vztahu k dictionary.c,

29
00:02:10,770 --> 00:02:14,100
které budeme psát, bude dost důležité.

30
00:02:14,100 --> 00:02:16,970
Spec Pset také obsahuje mnoho užitečných informací

31
00:02:16,970 --> 00:02:21,360
pokud jde o věci, které můžete předpokládat, pravidla a podobné věci, které,

32
00:02:21,360 --> 00:02:24,710
tak se určitě přečtěte PSet spec pečlivě tipy.

33
00:02:24,710 --> 00:02:29,310
A v případě pochybností o pravidla nebo něco takového, pak se vždy vztahují k PSet spec

34
00:02:29,310 --> 00:02:31,550
nebo Diskutovat.

35
00:02:31,550 --> 00:02:34,060
Tento Pset bude spoléhat na ukazatele,

36
00:02:34,060 --> 00:02:37,890
tak chceme, aby se ujistil, že jsme pochopili rozdíl mezi přidávání hvězdiček

37
00:02:37,890 --> 00:02:41,680
v přední části je ukazatel jméno a ampersand, jak se osvobodit a atd.

38
00:02:41,680 --> 00:02:47,550
Takže být mistrem ukazatelů bude velmi užitečné v tomto problému sadě.

39
00:02:47,550 --> 00:02:50,460
Budeme se podívat do propojené seznamy trochu víc,

40
00:02:50,460 --> 00:02:57,790
kde mají prvky, který nazýváme uzly, které mají jak hodnotu, stejně jako ukazatel

41
00:02:57,790 --> 00:03:02,520
k následujícímu uzlu, a tak v podstatě propojení různých prvků jeden po druhém.

42
00:03:02,520 --> 00:03:07,190
Existuje několik různých možností na realizaci své skutečné slovník.

43
00:03:07,190 --> 00:03:13,150
Budeme se podívat do dvou hlavních metod, které je hashovací tabulky a potom se pokusí.

44
00:03:13,150 --> 00:03:17,660
V obou těch, které zahrnují nějaký druh pojmu propojeného seznamu

45
00:03:17,660 --> 00:03:20,790
kde jste elementy navzájem propojeny.

46
00:03:20,790 --> 00:03:25,640
A tak budeme vypadat nad tím, jak byste měli být schopni pracovat kolem propojených seznamů,

47
00:03:25,640 --> 00:03:29,680
vytvořit, přecházet z hlediska jak, například, vložit uzel do něj

48
00:03:29,680 --> 00:03:32,760
nebo bez všechny uzly stejně.

49
00:03:32,760 --> 00:03:34,740
Pokud jde o uvolňovacími uzlů, to je opravdu důležité

50
00:03:34,740 --> 00:03:37,700
že kdykoli jsme malloc paměti, potom jsme uvolnit ji.

51
00:03:37,700 --> 00:03:42,910
Takže chceme, aby se ujistil, že žádný ukazatel jde unfreed, že nemáme žádné úniky paměti.

52
00:03:42,910 --> 00:03:48,330
Budeme zavést nástroj nazývaný Valgrind, který běží na programu

53
00:03:48,330 --> 00:03:52,260
a kontroluje, zda všechny paměti, že přidělené je pak osvobozený.

54
00:03:52,260 --> 00:03:59,080
Vaše Pset je pouze dokončit, když to funguje, a má plnou funkčnost,

55
00:03:59,080 --> 00:04:03,990
ale také, Valgrind vám řekne, že jste nenašli žádné úniky paměti.

56
00:04:03,990 --> 00:04:06,690
Konečně, pro tento PSet, opravdu chci zdůraznit -

57
00:04:06,690 --> 00:04:11,360
Myslím, jako obvykle, já jsem rozhodně zastáncem použití pera a papíru pro vaše problémové soubory,

58
00:04:11,360 --> 00:04:14,840
ale pro tento jeden, myslím, že pero a papír bude zvláště důležité

59
00:04:14,840 --> 00:04:19,000
pokud chcete, aby se čerpání šipky na věci a pochopení toho, jak věci fungují.

60
00:04:19,000 --> 00:04:24,440
Takže určitě zkuste použít tužku a papír k tomu, co před vás kódování

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

62
00:04:26,970 --> 00:04:30,700
>> Za prvé, pojďme do propojených seznamů trochu.

63
00:04:30,700 --> 00:04:35,510
Propojené seznamy se skládají z uzlů, kde každý uzel má hodnotu spojenou s ním,

64
00:04:35,510 --> 00:04:39,810
stejně jako ukazatel na další uzel po něm.

65
00:04:39,810 --> 00:04:43,680
Pár věcí důležitých s lineárními seznamy je, že musíme mít na paměti

66
00:04:43,680 --> 00:04:48,810
kde naše první uzel je, a pak jednou víme, kde první uzel je,

67
00:04:48,810 --> 00:04:52,990
že způsob, jak můžeme přistupovat na uzel, který první uzel odkazuje na

68
00:04:52,990 --> 00:04:55,850
a pak ještě do a jeden po tom.

69
00:04:55,850 --> 00:05:00,340
A pak poslední prvek ve vašem propojeného seznamu je tento uzel je ukazatel

70
00:05:00,340 --> 00:05:02,340
je vždycky poukázat na NULL.

71
00:05:02,340 --> 00:05:08,230
Když uzel bodů na hodnotu NULL, pak víte, že jste na konci seznamu,

72
00:05:08,230 --> 00:05:12,320
že uzel je poslední, že není nic po tom.

73
00:05:12,320 --> 00:05:16,970
Tady v tomto schématu, uvidíte, že šipky jsou ukazatele,

74
00:05:16,970 --> 00:05:20,290
a modré sekce je místo, kde je uložen hodnota,

75
00:05:20,290 --> 00:05:24,420
a pak červené pole s ukazatel na ní je uzel je ukazatel

76
00:05:24,420 --> 00:05:27,050
ukazuje na další uzel po něm.

77
00:05:27,050 --> 00:05:33,730
A tak zde vidíte, by uzel D poukázat na NULL, protože to je poslední prvek v seznamu.

78
00:05:33,730 --> 00:05:38,240
>> Pojďme se podívat na to, jak bychom mohli definovat struct pro uzel.

79
00:05:38,240 --> 00:05:40,130
A protože chceme mít více uzlů,

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

81
00:05:43,180 --> 00:05:46,870
, ve kterém budeme mít několik různých instancí uzlů.

82
00:05:46,870 --> 00:05:50,850
A tak jsme ji definují jako nový datový typ.

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

84
00:05:53,630 --> 00:05:56,160
V tomto příkladu, máme co do činění s celočíselnými uzly,

85
00:05:56,160 --> 00:06:00,490
takže máme celočíselnou názvem hodnotu a potom máme další ukazatel,

86
00:06:00,490 --> 00:06:07,390
a v tomto případě, je to ukazatel na uzel, takže máme struct uzel * volal další.

87
00:06:07,390 --> 00:06:09,520
A pak voláme celou tuto věc uzel.

88
00:06:09,520 --> 00:06:11,110
Ujistěte se, že budete dodržovat následující syntaxi.

89
00:06:11,110 --> 00:06:17,940
Všimněte si, že uzel je ve skutečnosti odkazováno nahoře stejně jako dole složených závorek.

90
00:06:17,940 --> 00:06:23,400
Pak sledovat, kde moje první uzel v tomto propojeném seznamu,

91
00:06:23,400 --> 00:06:29,390
pak jsem si uzel ukazatel s názvem hlava, a já malloc dostatek prostoru pro velikost uzlu.

92
00:06:29,390 --> 00:06:36,240
Poznámka, nicméně, že hlava je vlastně uzel ukazatel na rozdíl od aktuálního uzlu samotného.

93
00:06:36,240 --> 00:06:40,130
Takže hlava skutečně neobsahuje žádnou hodnotu,

94
00:06:40,130 --> 00:06:45,590
pouze poukázat na podle toho, co první uzel v mém propojeného seznamu je.

95
00:06:55,080 --> 00:06:58,340
>> Chcete-li získat lepší představu o souvisejících seznamů, protože je to velmi důležité,

96
00:06:58,340 --> 00:07:02,220
sledovat ujistit se, že budete udržovat řetěz,

97
00:07:02,220 --> 00:07:09,990
Líbí se mi myslet na to, jak se lidé v řadě se drží za ruce,

98
00:07:09,990 --> 00:07:14,330
, kde každá osoba je drží za ruce s další.

99
00:07:14,330 --> 00:07:18,350
Nemůžete vidět v tomto výkresu, ale v podstatě jsou to ukazuje na další osobu

100
00:07:18,350 --> 00:07:23,760
že je v jejich řetězci.

101
00:07:23,760 --> 00:07:29,270
A tak pokud chcete projít propojené seznam, kde tito lidé -

102
00:07:29,270 --> 00:07:32,830
představit všechny ty lidi mají hodnoty spojené s nimi

103
00:07:32,830 --> 00:07:36,590
a také poukazují na další osoby v souladu -

104
00:07:36,590 --> 00:07:40,810
Chcete-li přejít propojeného seznamu, například, buď upravit hodnoty

105
00:07:40,810 --> 00:07:42,830
nebo hledání hodnotě nebo něco takového,

106
00:07:42,830 --> 00:07:48,270
pak budete chtít mít ukazatel na konkrétní osobu.

107
00:07:48,270 --> 00:07:52,670
Takže budeme mít datový typ uzlu ukazatel.

108
00:07:52,670 --> 00:07:55,580
Pro tento Například, řekněme, že kurzor.

109
00:07:55,580 --> 00:07:59,630
Dalším běžným způsobem pojmenovat to bude iterátor, nebo něco takového

110
00:07:59,630 --> 00:08:05,130
protože je to iterace a vlastně dojemná, který uzel to ukazuje.

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

112
00:08:14,410 --> 00:08:20,180
Náš kurzor se nejprve poukázat na první prvek v našem seznamu.

113
00:08:20,180 --> 00:08:26,910
A tak to, co chceme udělat, je, že jsme se v podstatě bude pokračovat kurzor,

114
00:08:26,910 --> 00:08:29,130
pohybující se ze strany na stranu.

115
00:08:29,130 --> 00:08:33,409
V tomto případě, chceme přesunout na další prvek v seznamu.

116
00:08:33,409 --> 00:08:38,480
S polem, co budeme dělat, je bychom jen říci, že jsme zvýšit index 1.

117
00:08:38,480 --> 00:08:46,020
V tomto případě, co musíme udělat, je skutečně zjistit, které osoby tento proud osoba směřující,

118
00:08:46,020 --> 00:08:48,930
a že to bude další hodnotu.

119
00:08:48,930 --> 00:08:53,230
Takže pokud kurzor je jen uzel ukazatel, pak to, co chceme dělat

120
00:08:53,230 --> 00:08:56,320
je, že se chtějí dostat na hodnotu, která je kurzor ukazuje.

121
00:08:56,320 --> 00:09:01,350
Chceme se dostat do tohoto uzlu a pak, až budeme v tomto uzlu, zjistit, kde to ukazuje.

122
00:09:01,350 --> 00:09:05,820
Chcete-li získat skutečné uzlu, který kurzor ukazuje na,

123
00:09:05,820 --> 00:09:13,160
obvykle označujeme ji (* kurzor).

124
00:09:13,160 --> 00:09:19,160
To by vám aktuální uzel, který kurzor ukazuje.

125
00:09:19,160 --> 00:09:21,730
A potom, co chceme udělat, je chceme přistupovat

126
00:09:21,730 --> 00:09:25,680
co to uzlu příští hodnota.

127
00:09:25,680 --> 00:09:32,820
K tomu, aby přístup k hodnoty uvnitř struct, máme operátoru tečka.

128
00:09:32,820 --> 00:09:39,530
Takže pak by to bylo (* kurzor). Další.

129
00:09:39,530 --> 00:09:44,840
Ale to je trochu chaotický, pokud jde o to, aby závorky kolem * kurzoru,

130
00:09:44,840 --> 00:09:56,800
a tak jsme se nahradit celou tuto prohlášení s kurzorem->.

131
00:09:56,800 --> 00:10:02,700
To je pomlčka a pak větší než znak, tak aby se šipkou.

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

133
00:10:05,840 --> 00:10:12,390
To bude skutečně vám uzel, který se kurzor ukazuje. Tato hodnota je o další.

134
00:10:12,390 --> 00:10:16,790
Takže místo toho, aby na hvězdičku a tečku, budete nahrazovat, že se šipkou.

135
00:10:16,790 --> 00:10:24,820
Buďte velmi opatrní, aby se ujistil, že se pokusíte použít tuto syntaxi.

136
00:10:33,550 --> 00:10:37,620
>> Nyní, když máme kurzor, pokud chceme, aby přístup k hodnotě,

137
00:10:37,620 --> 00:10:40,450
předtím, jsme měli kurzor-> next,

138
00:10:40,450 --> 00:10:46,260
ale pro přístup k hodnotě na uzlu, který kurzor ukazuje na, jsme prostě říct

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

140
00:10:48,070 --> 00:10:53,600
Odtud je to na datový typ, co jsme definovali hodnoty a uzlů být.

141
00:10:53,600 --> 00:10:59,620
Pokud je to int uzel, pak kurzor-> hodnota je jen bude číslo.

142
00:10:59,620 --> 00:11:04,870
Takže můžeme udělat operace na to, podívejte se rovností, přiřadit jí různé hodnoty, atd.

143
00:11:04,870 --> 00:11:11,090
Takže to, co chcete dělat, když chcete přesunout kurzor na další osobu,

144
00:11:11,090 --> 00:11:15,270
můžete skutečně změnit hodnotu kurzoru.

145
00:11:15,270 --> 00:11:19,340
Vzhledem k tomu, kurzor je uzel ukazatel, můžete změnit aktuální adresu ukazatel

146
00:11:19,340 --> 00:11:23,890
na adresu dalšího uzlu v seznamu.

147
00:11:23,890 --> 00:11:28,930
To je jen nějaký kód, kde byste mohli iteraci.

148
00:11:28,930 --> 00:11:31,230
Kde mám komentář něco udělat,

149
00:11:31,230 --> 00:11:33,850
to, kde jste pravděpodobně bude přístup k hodnotě

150
00:11:33,850 --> 00:11:37,850
nebo něco do činění s tímto konkrétním uzlu.

151
00:11:37,850 --> 00:11:43,050
Chcete-li začít ho, říkám, že můj kurzor původně

152
00:11:43,050 --> 00:11:48,430
bude ukazovat na první prvek v propojeném seznamu.

153
00:11:48,430 --> 00:11:52,910
A tak se před námi, jsem definoval to jako hlava uzlu.

154
00:11:52,910 --> 00:11:57,610
>> Jak jsem již zmínil dříve, uvolňovat je opravdu důležité.

155
00:11:57,610 --> 00:12:02,440
Chcete, aby se ujistil, že jste uvolnit každý prvek v seznamu, jakmile jste skončil s ním.

156
00:12:02,440 --> 00:12:04,940
Když nemusíte odkazovat některé z těchto ukazatelů už,

157
00:12:04,940 --> 00:12:10,620
chcete, aby se ujistil, že jste osvobodit všechny tyto ukazatele.

158
00:12:10,620 --> 00:12:14,460
Ale vy chcete být velmi opatrní v tom, že budete chtít, aby se zabránilo nevracení paměti.

159
00:12:14,460 --> 00:12:25,080
Pokud si zdarma jeden člověk předčasně, pak všechny ukazatele, které tento uzel odkazuje na

160
00:12:25,080 --> 00:12:26,900
se bude ztracena.

161
00:12:26,900 --> 00:12:32,070
Vraťme se zpět k osobě příklad, aby bylo trochu víc high stakes,

162
00:12:32,070 --> 00:12:49,600
pojďme si tyto lidi, s výjimkou v tomto případě, že se vznášejí nad jezerem s monstrem.

163
00:12:49,600 --> 00:12:53,200
Chceme se ujistit, že vždy, když jsme uvolnění, abychom neztratili

164
00:12:53,200 --> 00:12:58,920
a pustil všechny uzly, než jsme ve skutečnosti je osvobodil.

165
00:12:58,920 --> 00:13:05,730
Například, pokud jste byli jednoduše volat zdarma na toho chlapa tady,

166
00:13:05,730 --> 00:13:15,350
pak by byla uvolněna, ale pak všechny tyto lidi by pak dojít ke ztrátě

167
00:13:15,350 --> 00:13:18,450
a oni by usnout a spadnout.

168
00:13:18,450 --> 00:13:24,900
Takže chceme, aby se ujistil, že místo, chceme zachovat odkaz na zbytek.

169
00:13:37,630 --> 00:13:42,480
Naše hlava ukazatel, který ukazuje na první prvek v seznamu.

170
00:13:42,480 --> 00:13:49,990
Je to něco jako lano kotevní první osobě.

171
00:13:52,870 --> 00:13:57,470
Co byste mohli chtít dělat, když jste uvolnění seznam je mít -

172
00:13:57,470 --> 00:14:04,520
Pokud chcete, aby se uvolnil první prvek první, pak můžete mít dočasný ukazatel

173
00:14:04,520 --> 00:14:07,370
že poukazuje na jakýkoliv první prvek je.

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

175
00:14:11,420 --> 00:14:15,840
Tak, máme držet prvního uzlu.

176
00:14:15,840 --> 00:14:18,930
A pak, protože víme, že první uzel bude osvobozen,

177
00:14:18,930 --> 00:14:24,890
pak můžeme přesunout lano, tento kotevní, naše hlavy,

178
00:14:24,890 --> 00:14:31,930
skutečně poukazují na cokoliv první ukazuje.

179
00:14:31,930 --> 00:14:38,760
Tak tohle hlava skutečně odkazuje na druhý prvek nyní.

180
00:14:38,760 --> 00:14:43,980
Nyní se mohou uvolnit, co je uloženo v teplotě,

181
00:14:43,980 --> 00:14:53,360
a tak se může odstranit, že bez ní ohrožení všech ostatních uzlů v našem seznamu.

182
00:14:54,140 --> 00:15:05,020
Dalším způsobem, že byste mohli udělat to mohlo být

183
00:15:05,020 --> 00:15:08,650
pokaždé, když stačí uvolnit poslední prvek v seznamu

184
00:15:08,650 --> 00:15:11,010
protože oni zaručeno, že se ukázal na cokoliv.

185
00:15:11,010 --> 00:15:15,570
Takže vy jste mohli jen uvolnit tenhle, pak volný tentokrát, pak bez tentokrát.

186
00:15:15,570 --> 00:15:21,900
To určitě funguje, ale je trochu pomalejší, protože podle povahy propojených seznamů,

187
00:15:21,900 --> 00:15:24,670
můžeme nejen okamžitě skočit do posledního.

188
00:15:24,670 --> 00:15:28,030
Musíme projít každý prvek v připojeném seznamu

189
00:15:28,030 --> 00:15:31,020
a zkontrolujte, zda že jeden ukazuje na NULL, zkontrolujte pokaždé,

190
00:15:31,020 --> 00:15:33,780
a pak ještě jednou dojdeme na konec, pak zdarma, které.

191
00:15:33,780 --> 00:15:40,270
Pokud byste měli udělat tento proces, by si skutečně být kontrola zde,

192
00:15:40,270 --> 00:15:44,190
kontrola tady, pak kontrola tady, uvolňovat to,

193
00:15:44,190 --> 00:15:47,470
pak jít zpět, kontrola tady, kontrola tady, uvolňovat to,

194
00:15:47,470 --> 00:15:49,660
kontrola tady, a pak uvolňovat to.

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

196
00:15:52,880 --> 00:15:59,060
>> [Student] Bylo by možné, aby se spojový seznam, který ukládá návratový ukazatel na konec?

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

198
00:16:01,320 --> 00:16:08,340
Chcete-li zopakovat otázku, je možné mít propojenou seznam strukturu

199
00:16:08,340 --> 00:16:12,490
tak, že si mít ukazatel směřující do konce propojeného seznamu?

200
00:16:12,490 --> 00:16:18,090
Řekl bych, že je to možné, a pokaždé, když vložíte něco do propojeného seznamu

201
00:16:18,090 --> 00:16:21,470
budete muset aktualizovat tento ukazatel a podobné věci.

202
00:16:21,470 --> 00:16:26,640
Ty by měly uzlu * ocas, například.

203
00:16:26,640 --> 00:16:29,840
Ale když jste provádění této funkci, musíte myslet na kompromisů,

204
00:16:29,840 --> 00:16:32,700
Líbí kolikrát budu se iterace nad tím,

205
00:16:32,700 --> 00:16:36,100
jak těžké je bude sledovat z ocasu, stejně jako hlava

206
00:16:36,100 --> 00:16:38,400
stejně jako můj iterátor, a podobné věci.

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

208
00:16:42,480 --> 00:16:48,270
Je to možné, ale pokud jde o návrhu rozhodnutí, budete muset zvážit možnosti.

209
00:16:53,850 --> 00:17:01,090
>> Zde je kostra kódu, který by vám umožní uvolnit každý prvek propojeného seznamu.

210
00:17:01,090 --> 00:17:05,460
Opět, protože jsem iterace provázaném seznamu, budu chtít mít nějaký kurzoru

211
00:17:05,460 --> 00:17:08,670
nebo iterátor.

212
00:17:08,670 --> 00:17:14,640
Jsme iterací, dokud kurzor NULL.

213
00:17:14,640 --> 00:17:17,640
Nechcete, aby iteraci, kdy je kurzor na NULL

214
00:17:17,640 --> 00:17:20,579
protože to znamená, že není nic v seznamu.

215
00:17:20,579 --> 00:17:25,069
Takže tady jsem vytvořit dočasnou uzlu *

216
00:17:25,069 --> 00:17:29,610
poukazuje na to, co jsem za zvážení, je první z mého seznamu,

217
00:17:29,610 --> 00:17:35,340
a pak jsem pohnout kurzorem dopředu 1 a pak volný, co jsem měl v režimu dočasného uskladnění.

218
00:17:38,460 --> 00:17:43,650
>> Nyní se dostáváme k vložení do propojených seznamů.

219
00:18:00,200 --> 00:18:09,660
Mám tři uzly v mé propojeného seznamu, a pojďme se jednoduchém případě

220
00:18:09,660 --> 00:18:18,970
tam, kde chceme vložit další uzel na konci našeho propojeného seznamu.

221
00:18:18,970 --> 00:18:25,980
K tomu, vše, co bude dělat je, že jsme se projít

222
00:18:25,980 --> 00:18:32,100
zjistit, kde proud konec propojeného seznamu je, tak podle toho, uzel 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 pak říci, vlastně, tohle je nebude poslední uzel;

225
00:18:37,260 --> 00:18:39,830
jsme vlastně bude mít jinou.

226
00:18:39,830 --> 00:18:46,260
Takže budeme mít tento současný jeden bod k tomu, co jsme vkládání.

227
00:18:46,260 --> 00:18:50,080
Takže teď to červené osoba zde stává poslední uzel v propojeném seznamu.

228
00:18:50,080 --> 00:18:56,080
A tak charakteristický posledního uzlu v propojeném seznamu je, že se poukazuje na NULL.

229
00:18:56,080 --> 00:19:09,380
Takže to, co bychom měli udělat, je nastavit tuto červenou chlapa ukazatel na NULL. Tam.

230
00:19:09,380 --> 00:19:25,370
>> Ale co když chceme vložit uzel mezi druhým a třetím jeden?

231
00:19:25,370 --> 00:19:28,960
To člověk není tak jednoduché, protože chceme, aby se ujistil

232
00:19:28,960 --> 00:19:34,290
že nepouštěj žádného uzlu v naší propojeného seznamu.

233
00:19:34,290 --> 00:19:43,450
Co bychom měli udělat, je ujistit, že jsme ukotvit, abychom se každé z nich.

234
00:19:43,450 --> 00:19:49,900
Například, řekněme tuto druhou možnost.

235
00:19:49,900 --> 00:19:54,390
Pokud jste řekl druhý nyní ukazuje na tuto novou

236
00:19:54,390 --> 00:20:02,520
a jste právě udělal ukazatel tam, pak by to bylo za následek ten chlap ztrátě

237
00:20:02,520 --> 00:20:07,830
protože tam není žádný odkaz na něj.

238
00:20:07,830 --> 00:20:18,970
Místo toho - budu kreslit to znovu. Omluvte mé umělecké schopnosti.

239
00:20:18,970 --> 00:20:26,570
Víme, že nemůžeme jen tak přímo připojit 2 do nového.

240
00:20:26,570 --> 00:20:30,480
Musíme se ujistit, že jsme se držet na poslední.

241
00:20:30,480 --> 00:20:39,200
Co bychom mohli chtít udělat, je mít dočasný ukazatel

242
00:20:39,200 --> 00:20:42,650
na prvek, který je bude připojena na.

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

244
00:20:45,140 --> 00:20:50,780
Protože víme, že to třetí je držen sledovat,

245
00:20:50,780 --> 00:20:53,680
2 může nyní propojit do našeho nového.

246
00:20:53,680 --> 00:20:57,490
A pokud tato nová červená chlap bude mezi 2 a 3,

247
00:20:57,490 --> 00:21:05,550
pak to, co je ten chlap je ukazatel bude ukazovat na? >> [Student] Temp.

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

249
00:21:07,490 --> 00:21:15,430
Takže tahle červená chlap další hodnota bude tepl.

250
00:21:26,090 --> 00:21:33,010
Když jste vložením do propojených seznamů, viděli jsme, že bychom mohli

251
00:21:33,010 --> 00:21:38,260
snadno přidat něco do konce vytvořením dočasné pole,

252
00:21:38,260 --> 00:21:42,850
nebo pokud jsme chtěli přidat něco do středu našeho pole,

253
00:21:42,850 --> 00:21:46,810
pak by to trvat trochu více přešlapuje.

254
00:21:46,810 --> 00:21:50,240
Pokud chcete, například, mají seřazena propojeného seznamu,

255
00:21:50,240 --> 00:21:54,880
pak se budete muset trochu zvažovat náklady a přínosy, které

256
00:21:54,880 --> 00:21:59,720
protože pokud chcete mít seřazena pole, to znamená, že pokaždé, když vložíte do něj,

257
00:21:59,720 --> 00:22:01,630
to bude trvat trochu déle.

258
00:22:01,630 --> 00:22:05,500
Nicméně, pokud chcete, aby později, až najdeme budeme chtít,

259
00:22:05,500 --> 00:22:10,280
Hledání pomocí propojeného seznamu, pak to může být snadnější, pokud budete vědět, že je vše v pořádku.

260
00:22:10,280 --> 00:22:15,340
Takže možná budete chtít zvážit náklady a přínosy, které.

261
00:22:20,150 --> 00:22:27,740
>> Dalším způsobem, jak vložit do propojeného seznamu je vložit do začátku seznamu.

262
00:22:27,740 --> 00:22:34,700
Pokud čerpáme kotvu zde - to je naše hlava -

263
00:22:34,700 --> 00:22:40,960
a pak tito lidé s ní souvisí,

264
00:22:40,960 --> 00:22:48,460
a pak máme nový uzel má být vložena do začátku,

265
00:22:48,460 --> 00:22:52,590
pak to, co bychom mohli chtít udělat?

266
00:22:55,220 --> 00:23:03,580
Jaký by měl být v pořádku s jen říkám chci propojit červené k modré,

267
00:23:03,580 --> 00:23:05,790
protože to je první?

268
00:23:05,790 --> 00:23:08,570
Co by se stalo tady?

269
00:23:08,570 --> 00:23:12,130
Všechny z těchto tří by ztratit.

270
00:23:12,130 --> 00:23:14,140
Takže nechceme udělat.

271
00:23:14,140 --> 00:23:21,430
Opět jsme se dozvěděli, že musíme mít nějaký druh dočasného ukazatele.

272
00:23:21,430 --> 00:23:34,470
Pojďme si vybrat na dočasnou dobu bod na toho chlapa.

273
00:23:34,470 --> 00:23:39,640
Pak můžeme mít modrou jeden bod k tomu dočasné

274
00:23:39,640 --> 00:23:43,240
a pak červený bod na modré.

275
00:23:43,240 --> 00:23:47,830
Důvodem, proč jsem využívala lidi tady je, protože my opravdu chceme vizualizovat

276
00:23:47,830 --> 00:23:53,180
drží na lidi a ujistit se, že máme odkaz na ně

277
00:23:53,180 --> 00:23:57,590
před pustíme jiného ruky nebo něco takového.

278
00:24:05,630 --> 00:24:10,650
>> Nyní, když máme pocit lineárními seznamy - jak bychom je mohli vytvořit odkazovaný seznam

279
00:24:10,650 --> 00:24:15,090
a vytvořit struktury pro které se skládá z definice typu pro uzel

280
00:24:15,090 --> 00:24:19,060
a pak ujistit se, že máme ukazatel na hlavě toho propojeného seznamu -

281
00:24:19,060 --> 00:24:23,210
jakmile budeme mít to a víme, jak přejít přes pole,

282
00:24:23,210 --> 00:24:28,200
přístup k jednotlivým prvkům, víme, jak vložit a my víme, jak se osvobodit,

283
00:24:28,200 --> 00:24:30,260
pak se můžeme dostat do překlepy.

284
00:24:30,260 --> 00:24:38,150
Jako obvykle, máme část otázek, na které se vám slouží k provozu s propojenými seznamy

285
00:24:38,150 --> 00:24:41,750
a různé struktury jako jsou například fronty a komínů.

286
00:24:41,750 --> 00:24:46,000
Pak se můžeme přesunout do překlepy.

287
00:24:46,000 --> 00:24:55,170
>> Pravopisné chyby se v distribuční kódu několik souborů významu.

288
00:24:55,170 --> 00:24:58,850
Nejprve jsme si všimli, že máme tuto Makefile tady,

289
00:24:58,850 --> 00:25:03,040
které jsme opravdu nesetkal.

290
00:25:03,040 --> 00:25:10,090
Pokud jste se podívali dovnitř pset5 složky, tak zjistíte, že máte. H soubor,

291
00:25:10,090 --> 00:25:12,530
pak máte dvě. C soubory.

292
00:25:12,530 --> 00:25:18,920
Co to dělá, je Makefile předtím, bychom stačí napsat make a pak název programu

293
00:25:18,920 --> 00:25:25,550
a pak bychom viděli všechny tyto argumenty a vlajek předány do kompilátoru.

294
00:25:25,550 --> 00:25:30,580
Co Makefile dělá, je nám umožňuje sestavit několik souborů najednou

295
00:25:30,580 --> 00:25:34,650
a předat vlajek, které chceme.

296
00:25:34,650 --> 00:25:41,300
Tady jsme jen vidět, že je soubor záhlaví zde.

297
00:25:41,300 --> 00:25:43,730
Pak jsme vlastně dva zdrojové soubory.

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
Jste vítáni upravit Makefile pokud si budete přát.

300
00:25:54,560 --> 00:26:03,310
Všimněte si, že zde, pokud zadáte čistý, pak to, co dělá, je ve skutečnosti odstraňuje něco

301
00:26:03,310 --> 00:26:06,340
že je jádro.

302
00:26:06,340 --> 00:26:09,190
Pokud máš segmentation fault, v podstatě máte core dump.

303
00:26:09,190 --> 00:26:13,260
Tak to ošklivý malý soubor se zobrazí ve vašem adresáři s názvem core.

304
00:26:13,260 --> 00:26:16,310
Budete chtít odebrat, že aby bylo čištění.

305
00:26:16,310 --> 00:26:20,940
To odstraní všechny spustitelné soubory a. Soubory o.

306
00:26:27,900 --> 00:26:30,220
>> Pojďme se podívat do dictionary.h.

307
00:26:30,220 --> 00:26:34,410
To říká, že to deklaruje slovníku funkčnost.

308
00:26:34,410 --> 00:26:39,530
Máme maximální délku pro libovolné slovo ve slovníku.

309
00:26:39,530 --> 00:26:45,130
Řekneme, že je to bude nejdelší slovo. Je to délky 45.

310
00:26:45,130 --> 00:26:48,900
Takže my nebudeme mít žádné slovo, které přesahují tuto délku.

311
00:26:48,900 --> 00:26:50,980
Zde musíme jen funkční prototypy.

312
00:26:50,980 --> 00:26:55,290
Nemáme vlastní realizaci, protože to je to, co budeme dělat v tomto PSet.

313
00:26:55,290 --> 00:26:59,940
Ale co to dělá, je, protože máme co do činění s většími soubory zde

314
00:26:59,940 --> 00:27:06,650
a funkčnost ve větším měřítku, je užitečné mít. h soubor

315
00:27:06,650 --> 00:27:11,290
tak, že někdo jiný číst, nebo pomocí kódu nemůže pochopit, co se děje.

316
00:27:11,290 --> 00:27:17,910
A možná, že chtějí zavést pokusí, pokud jste hash tabulky nebo naopak.

317
00:27:17,910 --> 00:27:21,850
Pak by řekli mi zatížení funkce,

318
00:27:21,850 --> 00:27:26,950
Vlastní realizace bude lišit, ale tento prototyp nebude měnit.

319
00:27:26,950 --> 00:27:33,280
Zde jsme zjistit, která vrací true, pokud dané slovo ve slovníku.

320
00:27:33,280 --> 00:27:39,800
Pak máme zátěž, která v podstatě trvá do slovníku souboru

321
00:27:39,800 --> 00:27:44,360
a potom načte do nějaké datové struktury.

322
00:27:44,360 --> 00:27:47,500
Máme velikost, která, je-li volána, vrací velikost vašeho slovníku,

323
00:27:47,500 --> 00:27:50,310
kolik slov jsou uloženy v ní,

324
00:27:50,310 --> 00:27:54,390
a potom uvolněte, které uvolní veškerou paměť, kterou lze vzít do

325
00:27:54,390 --> 00:27:57,900
a přitom svůj slovník.

326
00:28:01,070 --> 00:28:03,590
>> Pojďme se podívat na dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Je vidět, že to vypadá velmi podobně jako dictionary.h, s výjimkou nyní to prostě má všechny tyto todos v něm.

328
00:28:10,490 --> 00:28:16,980
A tak to je vaše práce. Nakonec, budete vyplňovat speller.c se všemi tohoto kódu.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, při spuštění, není opravdu nic dělat,

330
00:28:21,540 --> 00:28:29,590
takže se podíváme na speller.c vidět skutečné provádění kontroly pravopisu.

331
00:28:29,590 --> 00:28:32,060
I když nejste bude editovat žádnou z tohoto kódu,

332
00:28:32,060 --> 00:28:38,050
je důležité přečíst, pochopit, když je zatížení nazývá, když jsem volat kontrolu,

333
00:28:38,050 --> 00:28:42,350
jen pochopit, zmapovat to, jak funkce pracuje.

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

335
00:28:49,860 --> 00:28:55,200
V podstatě, když někdo běží pravopisu, znamená to, že je to volitelný

336
00:28:55,200 --> 00:29:00,950
pro ně projít do slovníku souboru, protože tam to bude výchozí slovník souboru.

337
00:29:00,950 --> 00:29:05,410
A pak se musí projít v textu být spell-zkontrolovat.

338
00:29:05,410 --> 00:29:11,410
rusage zabývá času, protože část tohoto PSet které budeme zabývat později

339
00:29:11,410 --> 00:29:14,790
není jen dostat fungující spell-checker pracovní

340
00:29:14,790 --> 00:29:17,190
ale ve skutečnosti dostat, aby to bylo rychle.

341
00:29:17,190 --> 00:29:22,040
A tak pak to je místo, kde rusage se přijde dovnitř

342
00:29:22,040 --> 00:29:28,740
Zde vidíme první hovor s jedním z našich dictionary.c souborů, který je zatížení.

343
00:29:28,740 --> 00:29:34,720
Load vrací true nebo false - true na úspěch, false při výpadku.

344
00:29:34,720 --> 00:29:41,400
Takže pokud slovníku není vložen správně, pak speller.c vrátí 1 a ukončete.

345
00:29:41,400 --> 00:29:47,920
Ale pokud to dělá zátěž správně, pak to bude pokračovat.

346
00:29:47,920 --> 00:29:50,740
Budeme pokračovat, a my vidíme nějaký soubor I / O zde,

347
00:29:50,740 --> 00:29:56,210
kde to bude jednání s otevřením textového souboru.

348
00:29:56,210 --> 00:30:04,640
Zde, co to dělá, je kouzlo-kontroluje každé slovo v textu.

349
00:30:04,640 --> 00:30:09,270
Takže to, co speller.c dělá tady je iterace každého slova v textovém souboru

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

351
00:30:24,680 --> 00:30:32,350
Zde máme logickou chybně, že uvidíme, jestli kontrola vrátí pravda nebo ne.

352
00:30:32,350 --> 00:30:37,110
Pokud slovo je vlastně ve slovníku, pak kontrola vrátí true.

353
00:30:37,110 --> 00:30:39,760
To znamená, že slovo není chybně.

354
00:30:39,760 --> 00:30:45,330
Takže chybně by bylo falešné, a to je důvod, proč máme bang tam, indikace.

355
00:30:45,330 --> 00:30:56,320
Držíme dál, a pak to sleduje, kolik slov s chybným pravopisem

356
00:30:56,320 --> 00:30:58,910
jsou v souboru.

357
00:30:58,910 --> 00:31:03,870
To pokračuje dál a zavře soubor.

358
00:31:03,870 --> 00:31:09,250
Pak tady, hlásí, kolik chybně napsaná slova, která měl.

359
00:31:09,250 --> 00:31:12,680
To počítá, jak dlouho to trvalo načíst slovník,

360
00:31:12,680 --> 00:31:15,080
Jak dlouho to trvalo podívat se na to,

361
00:31:15,080 --> 00:31:18,510
Jak dlouho to trvalo vypočítat velikost,

362
00:31:18,510 --> 00:31:21,260
která, jak budeme pokračovat, by mělo být velmi malé,

363
00:31:21,260 --> 00:31:25,390
a pak jak dlouho to trvalo vyložit slovník.

364
00:31:25,390 --> 00:31:27,700
Zde nahoře vidíme výzvu, abyste si vyložili zde.

365
00:31:27,700 --> 00:31:52,690
Pokud bychom zkontrolovat velikost zde,

366
00:31:52,690 --> 00:31:59,050
pak vidíme, že je zde výzva k velikosti, kde se určuje velikost slovníku.

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

368
00:32:07,100 --> 00:32:10,920
>> Naším úkolem pro tuto PSet je implementovat zátěž, která načte slovník

369
00:32:10,920 --> 00:32:15,480
Datová struktura - podle toho, co si vyberete, ať už je to hash tabulka nebo zkusit -

370
00:32:15,480 --> 00:32:18,810
se slovy ze slovníku souboru.

371
00:32:18,810 --> 00:32:25,290
Pak máte velikost, která vrátí počet slov ve slovníku.

372
00:32:25,290 --> 00:32:29,860
A pokud se rozhodnete zatížení v inteligentním způsobem, pak velikost by měla být docela snadné.

373
00:32:29,860 --> 00:32:33,860
Pak jste zjistit, který bude zda dané slovo ve slovníku.

374
00:32:33,860 --> 00:32:38,690
Takže speller.c přechází v řetězci, a pak se budete muset zkontrolovat, zda řetězec

375
00:32:38,690 --> 00:32:41,610
je obsažen ve vaší slovníku.

376
00:32:41,610 --> 00:32:46,750
Všimněte si, že obecně mají standardní slovníky,

377
00:32:46,750 --> 00:32:53,020
ale v tomto Pset, v podstatě jakékoliv slovník prošel v kterémkoliv jazyce.

378
00:32:53,020 --> 00:32:57,040
Takže nemůžeme jen předpokládat, že slovo je uvnitř.

379
00:32:57,040 --> 00:33:03,090
Slovo foobar mohla být definována v jistém slovníku, který míjíme dovnitř

380
00:33:03,090 --> 00:33:07,920
A pak jsme vyložit, která osvobozuje slovník z paměti.

381
00:33:07,920 --> 00:33:11,930
>> Nejprve bych chtěl jít přes hash tabulky metody

382
00:33:11,930 --> 00:33:14,630
o tom, jak bychom mohli implementovat všechny z těchto čtyř funkcí,

383
00:33:14,630 --> 00:33:18,650
a pak půjdu přes snaží metody, jak provádět tyto čtyři funkce,

384
00:33:18,650 --> 00:33:22,720
a na konci rozhovoru o některých obecných tipů, když jste dělat PSet

385
00:33:22,720 --> 00:33:27,870
a také, jak byste měli být schopni používat Valgrind pro kontrolu úniků paměti.

386
00:33:27,870 --> 00:33:30,550
>> Pojďme do hash tabulky metodou.

387
00:33:30,550 --> 00:33:35,910
Hash tabulka se skládá ze seznamu segmentů.

388
00:33:35,910 --> 00:33:43,010
Každá hodnota, každé slovo, je jít do jednoho z těchto segmentů.

389
00:33:43,010 --> 00:33:53,200
Hash table ideálně rovnoměrně distribuuje všechny tyto hodnoty, které jste mimochodem v

390
00:33:53,200 --> 00:33:57,160
a pak vyplní je do kbelíku tak, že každá lopata

391
00:33:57,160 --> 00:34:02,000
má asi stejný počet hodnot v něm.

392
00:34:02,000 --> 00:34:09,630
Struktura tabulky hash, máme řadu propojených seznamů.

393
00:34:09,630 --> 00:34:17,900
Co máme udělat, je, když jsme se projít v hodnotě, můžeme zkontrolovat, kde tato hodnota by měla patřit,

394
00:34:17,900 --> 00:34:23,840
které vědro patří, a umístěte jej do propojeného seznamu spojené s tímto lopatou.

395
00:34:23,840 --> 00:34:28,199
Tady, co mám, je hash funkce.

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

397
00:34:31,320 --> 00:34:38,540
Takže pro prvního segmentu, všechny celá čísla pod 10 jít do prvního segmentu.

398
00:34:38,540 --> 00:34:42,190
Jakékoliv celá čísla nad 10, ale nižší než 20 zacházejí do druhé,

399
00:34:42,190 --> 00:34:44,179
a pak se tak dále a tak dále.

400
00:34:44,179 --> 00:34:52,370
Pro mě, každý kbelík zastupuje tato čísla.

401
00:34:52,370 --> 00:34:59,850
Nicméně, říct, že jsem byl projít v 50, například.

402
00:34:59,850 --> 00:35:07,490
Zdá se, že první tři obsahují řadu deseti čísel.

403
00:35:07,490 --> 00:35:12,570
Ale já chci, aby moje hash tabulky, aby se v nějakém druhu celých čísel,

404
00:35:12,570 --> 00:35:19,860
tak pak budu muset odfiltrovat všechny čísla nad 30 do posledního segmentu.

405
00:35:19,860 --> 00:35:26,660
A tak pak by to mít za následek jakési nevyvážené hash tabulky.

406
00:35:31,330 --> 00:35:35,640
Chcete-li zopakovat, hash tabulka je jen řada lopat

407
00:35:35,640 --> 00:35:38,590
kde každý kbelík je provázaný seznam.

408
00:35:38,590 --> 00:35:43,730
A tak se určit, kde každá hodnota jde, což vědro to jde do,

409
00:35:43,730 --> 00:35:46,260
budete chtít, co se nazývá hash funkce

410
00:35:46,260 --> 00:35:55,010
že vezme hodnotu a pak říká tato hodnota odpovídá určité nádoby.

411
00:35:55,010 --> 00:36:00,970
Takže nahoře v tomto příkladu, moje hashovací funkce se každou hodnotu.

412
00:36:00,970 --> 00:36:03,020
Je kontrolováno, zda to bylo méně než 10.

413
00:36:03,020 --> 00:36:05,360
Pokud to bylo, to by dát do prvního segmentu.

414
00:36:05,360 --> 00:36:08,910
Zkontroluje, zda je to méně než 20, dá to do druhého, pokud platí,

415
00:36:08,910 --> 00:36:12,880
kontroluje, zda je to méně než 30, a potom ji umístí do třetího kbelíku,

416
00:36:12,880 --> 00:36:16,990
a pak všichni ostatní jen spadá do čtvrté kbelíku.

417
00:36:16,990 --> 00:36:20,110
Takže pokaždé, když mají hodnotu, vaše hashovací funkce

418
00:36:20,110 --> 00:36:25,420
bude klást tuto hodnotu do příslušného kbelíku.

419
00:36:25,420 --> 00:36:32,430
Hashovací funkce v podstatě potřebuje vědět, kolik kbelíky máte.

420
00:36:32,430 --> 00:36:37,960
Vaše velikost hash tabulky, počet segmentů, které máte,

421
00:36:37,960 --> 00:36:41,190
že to bude pevné číslo, které je na vás, pro vás se rozhodnout,

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 funkce bude spoléhat na to určit, který lžíce každý klíč jde do

424
00:36:51,840 --> 00:36:54,450
takové, že je to rovnoměrně.

425
00:36:56,150 --> 00:37:03,820
Podobně jako naše provádění souvisejících seznamů, nyní každý uzel v hash tabulce

426
00:37:03,820 --> 00:37:07,000
bude skutečně mít typu char.

427
00:37:07,000 --> 00:37:14,340
Takže máme char pole s názvem Slovo a pak ještě ukazatel na další uzel,

428
00:37:14,340 --> 00:37:19,010
což dává smysl, protože to bude spojový seznam.

429
00:37:19,010 --> 00:37:24,350
Pamatuješ, když jsme se spojil seznamy, udělal jsem uzlu * s názvem hlava

430
00:37:24,350 --> 00:37:31,060
, který byl s poukazem na prvním uzlu v propojeném seznamu.

431
00:37:31,060 --> 00:37:34,020
Ale pro naše hash tabulky, protože máme několik propojených seznamů,

432
00:37:34,020 --> 00:37:37,520
to, co chceme, je chceme, aby náš hash table být jako, "Co je to kbelík?"

433
00:37:37,520 --> 00:37:43,340
Lopata je jen seznam uzlů ukazatelů,

434
00:37:43,340 --> 00:37:50,620
a tak každý prvek v segmentu je vlastně ukazuje na jeho odpovídající propojeného seznamu.

435
00:37:56,180 --> 00:38:01,520
Chcete-li se vrátit k tomuto schématu, uvidíte, že kbelíky samotné jsou šipky,

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

437
00:38:11,680 --> 00:38:16,420
Jednou ze základních vlastností hašovacích funkcí je, že jsou deterministické.

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

439
00:38:19,440 --> 00:38:22,270
by měl vždy vrátit stejný kbelík.

440
00:38:22,270 --> 00:38:26,440
Každý hodnota, která jde do hash funkce, pokud by se opakovaly,

441
00:38:26,440 --> 00:38:29,690
musí dostat stejný index.

442
00:38:29,690 --> 00:38:34,210
Takže vaše hash funkce vrací index pole

443
00:38:34,210 --> 00:38:38,530
kde tato hodnota patří.

444
00:38:38,530 --> 00:38:41,790
Jak jsem již zmínil dříve, je stanovena počet segmentů,

445
00:38:41,790 --> 00:38:49,630
a tak si index, který se vrátit musí být menší, než je počet segmentů

446
00:38:49,630 --> 00:38:52,680
ale větší než 0.

447
00:38:52,680 --> 00:39:00,780
Důvodem, proč jsme hašovacích funkcí místo jen jedné propojeného seznamu

448
00:39:00,780 --> 00:39:09,290
nebo jeden jediný pole je to, že chceme být schopen skočit do určité části nejsnadněji

449
00:39:09,290 --> 00:39:11,720
pokud známe charakteristiku hodnoty -

450
00:39:11,720 --> 00:39:14,760
místo toho, aby museli prohledávat celého slovníku,

451
00:39:14,760 --> 00:39:18,320
budou moci přejít na určité části ní.

452
00:39:19,880 --> 00:39:24,440
Váš hash funkce by měla brát v úvahu, že v ideálním případě,

453
00:39:24,440 --> 00:39:28,980
Každý kbelík má přibližně stejný počet klíčů.

454
00:39:28,980 --> 00:39:35,040
Vzhledem k tomu, hash tabulka je série spojených seznamů,

455
00:39:35,040 --> 00:39:38,480
pak spojené seznamy sami budou mít více než jeden uzel.

456
00:39:38,480 --> 00:39:43,210
V předchozím příkladu, dvě různá čísla, i když nebyly stejné,

457
00:39:43,210 --> 00:39:46,950
když rozházeny, vrátí stejný index.

458
00:39:46,950 --> 00:39:53,620
Takže když máte co do činění se slovy, jedno slovo, když zatříděna

459
00:39:53,620 --> 00:39:57,450
by být stejná hodnota mřížky jako jiné slovo.

460
00:39:57,450 --> 00:40:04,140
To je to, co nazýváme kolizi, když máme uzel, který, když rozházeny,

461
00:40:04,140 --> 00:40:09,610
spojový seznam v tomto segmentu není prázdný.

462
00:40:09,610 --> 00:40:14,180
Technika, která nazýváme je lineární snímání,

463
00:40:14,180 --> 00:40:22,550
kde jdete do propojeného seznamu a pak najít místo, kde chcete vložit tento uzel

464
00:40:22,550 --> 00:40:25,520
protože máte kolizi.

465
00:40:25,520 --> 00:40:28,070
Můžete vidět, že tam by mohlo být trade-off, že jo?

466
00:40:28,070 --> 00:40:33,760
Pokud máte velmi malou hash tabulky, velmi malý počet segmentů,

467
00:40:33,760 --> 00:40:36,380
pak budete mít spoustu kolizí.

468
00:40:36,380 --> 00:40:40,460
Ale pak, pokud uděláte velkou hash tabulky,

469
00:40:40,460 --> 00:40:44,110
budete pravděpodobně k minimalizaci kolizí,

470
00:40:44,110 --> 00:40:47,170
ale to bude velmi velké datové struktury.

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 když jste provedli PSet, zkuste si pohrát

473
00:40:51,310 --> 00:40:54,210
mezi možná dělat menší hash tabulky

474
00:40:54,210 --> 00:41:02,100
ale pak s vědomím, že to bude trvat trochu déle procházet jednotlivé prvky

475
00:41:02,100 --> 00:41:04,270
z těchto propojených seznamů.

476
00:41:04,270 --> 00:41:09,500
>> Co zatížení se chystá udělat, je iteraci každé slovo ve slovníku.

477
00:41:09,500 --> 00:41:13,180
To projde ukazatel na soubor slovníku.

478
00:41:13,180 --> 00:41:18,050
Takže budete využívat souboru I / O funkcí, které ovládají v pset4

479
00:41:18,050 --> 00:41:23,010
a iteraci každé slovo ve slovníku.

480
00:41:23,010 --> 00:41:26,620
Chcete-každé slovo ve slovníku, aby se stal nový uzel,

481
00:41:26,620 --> 00:41:32,730
a budete umístit každý z těchto uzlů uvnitř vašeho slovníku datové struktury.

482
00:41:32,730 --> 00:41:36,560
Kdykoliv dostanete nové slovo, víte, že to bude stát uzel.

483
00:41:36,560 --> 00:41:46,590
Takže můžete jít hned a malloc uzlu ukazatel pro každou novou slovo, které jste.

484
00:41:46,590 --> 00:41:52,610
Tady jsem volá mé uzlu ukazatel new_node a já mallocing co? Velikost uzlu.

485
00:41:52,610 --> 00:41:59,190
Pak si přečíst aktuální řetězec ze souboru, protože slovník je ve skutečnosti uložena

486
00:41:59,190 --> 00:42:03,340
slovem a pak nový řádek, co můžeme využít

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

488
00:42:06,520 --> 00:42:10,280
přičemž soubor je slovník soubor, který jsme prošel v roce,

489
00:42:10,280 --> 00:42:18,900
tak to skenuje soubor pro řetězce a místa, která řetězec do posledního argumentu.

490
00:42:18,900 --> 00:42:26,890
Pokud si vzpomenete, zpět k jednomu z přednášek, když jsme šli přes

491
00:42:26,890 --> 00:42:29,320
a druh loupané vrstvy zpět na knihovně CS50,

492
00:42:29,320 --> 00:42:33,430
Viděli jsme implementaci fscanf tam.

493
00:42:33,430 --> 00:42:37,700
Chcete-li se vrátit do fscanf, máme soubor, který jsme čtení z,

494
00:42:37,700 --> 00:42:42,570
hledáme pro řetězec v tomto souboru, a pak jsme uvedení do

495
00:42:42,570 --> 00:42:48,340
tady mám new_node-> slovo, protože new_node je uzel ukazatel,

496
00:42:48,340 --> 00:42:50,380
není aktuální uzel.

497
00:42:50,380 --> 00:42:57,100
Takže říkám new_node, chci jít do uzlu, že to ukazuje na

498
00:42:57,100 --> 00:43:01,190
a pak přiřadit tuto hodnotu na slovo.

499
00:43:01,190 --> 00:43:08,540
Chceme, aby pak toto slovo a vložte jej do hash tabulky.

500
00:43:08,540 --> 00:43:13,750
Uvědomte si, že jsme udělali new_node uzlu ukazatel

501
00:43:13,750 --> 00:43:18,230
protože budeme chtít vědět, co adresa tohoto uzlu je

502
00:43:18,230 --> 00:43:23,940
když se vložit do proto, že struktura uzlů samotných, v struct,

503
00:43:23,940 --> 00:43:26,380
je to, že mají ukazatel na nový uzel.

504
00:43:26,380 --> 00:43:30,820
Takže to, co je adresa tohoto uzlu jít poukázat na?

505
00:43:30,820 --> 00:43:34,550
Tato adresa bude new_node.

506
00:43:34,550 --> 00:43:42,140
Dává to smysl, proč děláme new_node uzlu * na rozdíl od uzlu?

507
00:43:43,700 --> 00:43:45,700
Dobře.

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

509
00:43:52,840 --> 00:43:55,970
, Který obsahuje slovo ze slovníku, které chceme na vstup.

510
00:43:55,970 --> 00:44:00,210
Takže to, co chceme udělat, je chceme nazývat naši hash funkce na tomto řetězci

511
00:44:00,210 --> 00:44:03,780
protože naše hash funkce má v řetězci a vrátí nám celé číslo,

512
00:44:03,780 --> 00:44:12,090
kde, že číslo je index, kde Hashtable v tomto indexu představuje tento kbelík.

513
00:44:12,090 --> 00:44:18,260
Chceme, aby se tento index a pak jít do toho indexu hash tabulky

514
00:44:18,260 --> 00:44:26,960
a pak použít tento spojový seznam pro vložení uzlu na new_node.

515
00:44:26,960 --> 00:44:31,950
Pamatujte si, že se však se rozhodnete vložit své uzel,

516
00:44:31,950 --> 00:44:34,370
ať už je to ve středu, pokud chcete řadit jej

517
00:44:34,370 --> 00:44:39,650
nebo na začátku nebo na konci, jen se ujistěte, že vaše poslední uzel vždy ukazuje na NULL

518
00:44:39,650 --> 00:44:46,730
protože to je jediný způsob, jak víme, kde poslední prvek našeho propojeného seznamu je.

519
00:44:50,790 --> 00:44:59,710
>> Pokud je velikost celé číslo, které představuje počet slov ve slovníku,

520
00:44:59,710 --> 00:45:03,060
pak jeden způsob, jak to udělat, je to, že vždy, když se nazývá velikost

521
00:45:03,060 --> 00:45:05,840
projdeme každý prvek v naší hašovací tabulce

522
00:45:05,840 --> 00:45:09,410
a pak iterovat každého propojeného seznamu v hash tabulce

523
00:45:09,410 --> 00:45:13,770
a potom vypočítat délku, že zvýšení naší čítač 1 do 1.

524
00:45:13,770 --> 00:45:16,580
Ale pokaždé, když velikost se nazývá, že to bude trvat dlouho

525
00:45:16,580 --> 00:45:22,120
protože budeme mít lineárně snímání každý spojový seznam.

526
00:45:22,120 --> 00:45:30,530
Místo toho, to bude mnohem jednodušší, pokud budete mít přehled o tom, kolik slov jsou předávány palců

527
00:45:30,530 --> 00:45:36,330
Takže pokud jste například počítadlo přímo ve Vašem zatížení funkce

528
00:45:36,330 --> 00:45:42,430
to, že aktualizace je to nutné, pak čítač, pokud ji nastavit na globální proměnné,

529
00:45:42,430 --> 00:45:44,930
budou moci být přístupné velikosti.

530
00:45:44,930 --> 00:45:51,450
Takže to, co velikost by prostě udělat, je v jedné linii, stačí se vrátit hodnotu čítače,

531
00:45:51,450 --> 00:45:55,500
velikost slovníku, který jste již zabýval v zatížení.

532
00:45:55,500 --> 00:46:05,190
To je to, co jsem měl na mysli, když jsem říkal, že když se rozhodnete zatížení v užitečné způsobem,

533
00:46:05,190 --> 00:46:08,540
pak velikost bude docela snadné.

534
00:46:08,540 --> 00:46:11,350
>> Takže teď jsme si to ověřit.

535
00:46:11,350 --> 00:46:15,960
Nyní máme co do činění se slovy ze souboru vstupního textu,

536
00:46:15,960 --> 00:46:19,910
a tak budeme měly ověřovat, zda všechny ty vstupních slov

537
00:46:19,910 --> 00:46:22,520
jsou vlastně ve slovníku, nebo ne.

538
00:46:22,520 --> 00:46:26,520
Podobně jako Scramble, chceme, aby pro případ necitlivosti.

539
00:46:26,520 --> 00:46:32,110
Chcete, aby se ujistil, že všechna slova prošel v roce, i když jsou smíšený případ,

540
00:46:32,110 --> 00:46:37,840
při volání se smyčcovým porovnání, jsou rovnocenné.

541
00:46:37,840 --> 00:46:42,450
Slova v souborech slovníku textového jsou vlastně všichni malá.

542
00:46:42,450 --> 00:46:49,280
Další věc je, že můžete předpokládat, že každé slovo prošel v roce, každý řetězec,

543
00:46:49,280 --> 00:46:53,200
se bude buď v abecedním nebo obsahují apostrofy.

544
00:46:53,200 --> 00:46:58,010
Apostrofy se bude platné slova v našem slovníku.

545
00:46:58,010 --> 00:47:06,470
Takže pokud máte slovo s apostrof S, to je skutečný legitimní slovo ve vašem slovníku

546
00:47:06,470 --> 00:47:11,650
že to bude jeden z uzlů ve vašem tabulky hash.

547
00:47:13,470 --> 00:47:18,350
Kontrola pracuje s pokud slovo existuje, pak to musí být v naší hašovací tabulce.

548
00:47:18,350 --> 00:47:22,210
Je-li slovo ve slovníku, pak všechna slova ve slovníku, jsou v hash tabulce,

549
00:47:22,210 --> 00:47:26,560
tak se pojďme podívat na tohoto slova v hash tabulce.

550
00:47:26,560 --> 00:47:29,250
Víme, že od té doby jsme realizovali náš hash funkce

551
00:47:29,250 --> 00:47:38,420
tak, že každá jedinečná slovo vždy zatříděna na stejnou hodnotu,

552
00:47:38,420 --> 00:47:43,340
pak víme, že místo prohledávání našeho celého hash tabulky,

553
00:47:43,340 --> 00:47:48,310
můžeme skutečně najít propojený seznam, který toto slovo by mělo patřit k.

554
00:47:48,310 --> 00:47:51,850
Pokud to bylo ve slovníku, pak by to bylo v tomto bloku.

555
00:47:51,850 --> 00:47:57,140
Co můžeme dělat, když slovo je název našeho řetězce prošel v,

556
00:47:57,140 --> 00:48:01,560
můžeme jen hash, že slovo a pohled na propojeném seznamu

557
00:48:01,560 --> 00:48:06,410
při hodnotě Hashtable [hash (slovo)].

558
00:48:06,410 --> 00:48:12,410
Odtud, co můžeme udělat, je, že jsme menší podmnožinu uzlů pro vyhledávání tohoto slova,

559
00:48:12,410 --> 00:48:16,770
a tak můžeme přejít propojeného seznamu, na příkladu z dříve v návodu,

560
00:48:16,770 --> 00:48:24,110
a pak volat řetězec porovnání na slovo všude tam, kde je kurzor ukazuje na,

561
00:48:24,110 --> 00:48:28,430
to slovo, a zjistit, zda jsou tyto.

562
00:48:30,280 --> 00:48:35,110
V závislosti na způsobu, jakým jste organizovat svůj hash funkce,

563
00:48:35,110 --> 00:48:39,260
pokud je to seřazena, měli byste být schopni vrátit false něco dříve,

564
00:48:39,260 --> 00:48:43,440
ale pokud je to netříděný, pak budete chtít pokračovat křížení přes propojeného seznamu

565
00:48:43,440 --> 00:48:46,480
dokud nenajdete poslední prvek seznamu.

566
00:48:46,480 --> 00:48:53,320
A pokud jste ještě nenašli slovo v době, kdy jste dosáhli konce propojeného seznamu,

567
00:48:53,320 --> 00:48:56,890
to znamená, že vaše slovo neexistuje ve 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 měl vrátit false.

570
00:49:02,730 --> 00:49:09,530
>> Nyní se dostáváme k uvolnění, kde chceme osvobodit všechny uzly, které jsme malloc'd,

571
00:49:09,530 --> 00:49:14,050
tak bez všech uzlů uvnitř našeho stolu mřížky.

572
00:49:14,050 --> 00:49:20,270
Budeme chtít, aby iteraci přes všechny propojených seznamů a zdarma všechny uzly v tom.

573
00:49:20,270 --> 00:49:29,350
Podíváte-li se výše v návodu k příkladu, kde jsme uvolnit propojeného seznamu,

574
00:49:29,350 --> 00:49:35,140
pak budete chtít zopakovat tento proces pro každý prvek v hash tabulce.

575
00:49:35,140 --> 00:49:37,780
A já budu jít přes tento na konci návodu,

576
00:49:37,780 --> 00:49:46,600
ale Valgrind je nástroj, kde můžete vidět, pokud jste správně osvobodil

577
00:49:46,600 --> 00:49:53,600
každý uzel, který jste malloc'd nebo cokoliv jiného, ​​co jste malloc'd, jiné ukazatel.

578
00:49:55,140 --> 00:50:00,530
Tak to je hashovací tabulky, kde máme konečný počet segmentů

579
00:50:00,530 --> 00:50:09,220
a hash funkce, která bude mít hodnotu a pak přiřadit tuto hodnotu do určité kbelíku.

580
00:50:09,220 --> 00:50:13,340
>> Nyní se dostáváme k pokusech.

581
00:50:13,340 --> 00:50:18,750
Pokusí druh vypadají takto, a já také čerpat z příkladu.

582
00:50:18,750 --> 00:50:25,630
V podstatě, máte celou řadu potenciálních dopisů,

583
00:50:25,630 --> 00:50:29,210
a pak kdykoli budete budovat slovo,

584
00:50:29,210 --> 00:50:36,490
že dopis může být spojeno za slovníku na širokou škálu možností.

585
00:50:36,490 --> 00:50:40,840
Některá slova začít s C, ale pak pokračovat s,

586
00:50:40,840 --> 00:50:42,960
ale jiní pokračují s O, například.

587
00:50:42,960 --> 00:50:51,090
Trie je způsob vizualizace všech možných kombinací těchto slov.

588
00:50:51,090 --> 00:50:59,070
Trie se bude sledovat sledu písmen, které tvoří slova,

589
00:50:59,070 --> 00:51:08,280
odbočení pokud je to nutné, když je jedno písmeno následovat násobek písmen,

590
00:51:08,280 --> 00:51:16,630
a na konci uvést v každém bodě, zda tento výraz je platná nebo ne

591
00:51:16,630 --> 00:51:30,120
protože pokud jste hláskovat 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 znamenat, že po MAT, že je to vlastně platné slovo.

593
00:51:41,790 --> 00:51:48,590
Každý uzel v našem trie je vlastně bude obsahovat řadu uzlů ukazatelů,

594
00:51:48,590 --> 00:51:52,970
a budeme mít, konkrétně 27 z těchto uzlů ukazatelů,

595
00:51:52,970 --> 00:52:00,550
jeden pro každé písmeno v abecedě, stejně jako Apostrof.

596
00:52:00,550 --> 00:52:10,450
Každý prvek v tomto poli je samo o sobě bude ukazovat do jiného uzlu.

597
00:52:10,450 --> 00:52:14,020
Takže, pokud tento uzel je NULL, v případě, že je to nic po tom,

598
00:52:14,020 --> 00:52:20,550
pak víme, že tam žádné další písmena v tomto slově pořadí.

599
00:52:20,550 --> 00:52:26,950
Ale pokud tento uzel není NULL, znamená to, že existuje více písmen v tomto dopise pořadí.

600
00:52:26,950 --> 00:52:32,160
A pak dále, každý uzel označuje, zda je to poslední znak slova, nebo ne.

601
00:52:38,110 --> 00:52:43,170
>> Pojďme do příkladu trie.

602
00:52:50,500 --> 00:52:58,340
Nejprve jsem mít prostor pro 27 uzlů v tomto poli.

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

604
00:53:13,310 --> 00:53:15,370
Mám-li slovo BAR a chci vložit, že v,

605
00:53:15,370 --> 00:53:22,700
první písmeno je B, takže pokud má trie je prázdný,

606
00:53:22,700 --> 00:53:29,910
B je druhé písmeno v abecedě, takže budu volit, aby to tady v tomto indexu.

607
00:53:29,910 --> 00:53:33,450
Budu mít B zde.

608
00:53:33,450 --> 00:53:42,400
B bude uzel, který ukazuje na jiného pole všech možných znaků

609
00:53:42,400 --> 00:53:45,870
že může následovat po písmenem B.

610
00:53:45,870 --> 00:53:57,610
V tomto případě, se zabývám slovem BAR, takže půjdou sem.

611
00:54:02,000 --> 00:54:08,990
Po, mám dopis R, tak pak nyní ukazuje na vlastní kombinaci,

612
00:54:08,990 --> 00:54:15,120
a pak R bude tady.

613
00:54:15,120 --> 00:54:22,470
BAR je úplné slovo, takže pak budu mít R bod do jiného uzlu

614
00:54:22,470 --> 00:54:33,990
, který říká, že toto slovo je platné.

615
00:54:36,010 --> 00:54:40,970
To je uzel také bude mít řadu uzlů,

616
00:54:40,970 --> 00:54:45,260
ale ty by mohly být NULL.

617
00:54:45,260 --> 00:54:49,080
Ale v podstatě, může pokračovat takhle.

618
00:54:49,080 --> 00:54:54,250
To bude trochu jasnější, když jsme šli do jiného příkladu,

619
00:54:54,250 --> 00:54:56,780
takže stačí mít s sebou tam.

620
00:54:56,780 --> 00:55:02,050
Nyní máme BAR uvnitř našeho slovníku.

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

622
00:55:05,980 --> 00:55:12,630
Začneme s B, a už máme B jako jeden z dopisů, které v našem ceníku.

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

624
00:55:15,170 --> 00:55:19,250
Ale pak místo, máme Z následující.

625
00:55:19,250 --> 00:55:25,490
Takže prvkem v našem poli se bude Z,

626
00:55:25,490 --> 00:55:30,810
a tak, že jeden pak bude poukázat na jinou platnou konec slova.

627
00:55:30,810 --> 00:55:36,930
Takže vidíme, že když budeme pokračovat přes B a pak,

628
00:55:36,930 --> 00:55:43,480
existují dvě různé možnosti v současné době v našem slovníku pro slova, která začínají B a A.

629
00:55:49,650 --> 00:55:57,460
Řekněme, že bychom chtěli vložit slovo foobar.

630
00:55:57,460 --> 00:56:05,620
Pak bychom udělat vstup na F.

631
00:56:05,620 --> 00:56:11,320
F je uzel, který ukazuje na celou řadu.

632
00:56:11,320 --> 00:56:22,790
Rádi bychom vás O, jděte na O, O a pak spojuje do celého seznamu.

633
00:56:22,790 --> 00:56:35,340
Měli bychom B a pak pokračovat, měli bychom a pak R.

634
00:56:35,340 --> 00:56:43,570
Takže foobar prochází celou cestu dolů, dokud foobar je správné slovo.

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

636
00:56:52,590 --> 00:57:00,170
Teď říkají, naše další slovo ve slovníku je vlastně slovo FOO.

637
00:57:00,170 --> 00:57:03,530
Měli bychom říci, F. Co bude následovat, F?

638
00:57:03,530 --> 00:57:06,190
Vlastně jsem již prostor pro O, takže budu pokračovat.

639
00:57:06,190 --> 00:57:09,150
Nepotřebuju, aby se nový. Pokračovat.

640
00:57:09,150 --> 00:57:15,500
FOO je platná slovo v tomto slovníku, tak pak budu uvádět

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

642
00:57:21,660 --> 00:57:28,370
Kdybych přestala jsem sekvenci tam, to by bylo správné.

643
00:57:28,370 --> 00:57:33,050
Ale pokud jsme pokračovali v pořadí od FOO až B

644
00:57:33,050 --> 00:57:39,750
a prostě musel FOOB, FOOB není slovo, a to není uvedeno jako platnou.

645
00:57:47,370 --> 00:57:57,600
V trie, jste každý uzel označující, zda je to platné slovo, nebo ne,

646
00:57:57,600 --> 00:58:05,840
a pak každý uzel má také řadu 27 uzlu ukazatelů

647
00:58:05,840 --> 00:58:09,520
, které pak přejděte na uzly samotných.

648
00:58:09,520 --> 00:58:12,940
>> Zde je způsob, jak na to, jak budete chtít definovat to.

649
00:58:12,940 --> 00:58:17,260
Nicméně, stejně jako v hash tabulce příkladu, kde jsme měli uzlu * hlavu

650
00:58:17,260 --> 00:58:21,320
k označení začátku našeho propojeného seznamu, budeme také chtít

651
00:58:21,320 --> 00:58:29,150
nějaký způsob, jak vědět, kde je počátek našeho trie je.

652
00:58:29,150 --> 00:58:34,110
Někteří lidé říkají, se snaží stromy, a to je místo, kde kořen pochází.

653
00:58:34,110 --> 00:58:36,910
Takže chceme kořen našeho stromu, aby se ujistil, že jsme zůstat uzemněný

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ž jsme trochu přešel

656
00:58:46,300 --> 00:58:50,240
jak byste mohli přemýšlet o nakládání každé slovo do slovníku.

657
00:58:50,240 --> 00:58:54,540
V podstatě, pro každé slovo budete chtít iterovat svého trie

658
00:58:54,540 --> 00:58:59,590
a věděl, že každý prvek u dětí - říkali jsme, že děti v tomto případě -

659
00:58:59,590 --> 00:59:04,290
odpovídá jiným písmenem, budete chtít zkontrolovat tyto hodnoty

660
00:59:04,290 --> 00:59:08,320
v tomto konkrétním indexu, který odpovídá písmeno.

661
00:59:08,320 --> 00:59:11,260
Takže myslet celou cestu zpátky k Caesarovi a Vigenère,

662
00:59:11,260 --> 00:59:16,070
s vědomím, že každý dopis si můžete druh mapy zpět na index abecedy,

663
00:59:16,070 --> 00:59:20,690
Rozhodně až Z bude docela snadné mapovat abecední dopis,

664
00:59:20,690 --> 00:59:25,200
ale bohužel, apostrofy jsou také přijímaný znak ve slovech.

665
00:59:25,200 --> 00:59:31,650
Nejsem si ani jistý, co ASCII hodnota je,

666
00:59:31,650 --> 00:59:39,250
tak na to, pokud chcete najít index rozhodnout, zda chcete, aby to bylo buď první

667
00:59:39,250 --> 00:59:44,550
nebo poslední, budete muset pevný kódované šek na které

668
00:59:44,550 --> 00:59:48,930
a pak dát, že v indexu 26, například.

669
00:59:48,930 --> 00:59:55,300
Takže pak jste kontrolou hodnoty u dětí [i]

670
00:59:55,300 --> 00:59:58,400
kde [i] odpovídá na cokoliv písmeno jste na.

671
00:59:58,400 --> 01:00:04,110
Pokud je to NULL, to znamená, že není v současné době případné dopisy

672
01:00:04,110 --> 01:00:08,150
vyplývající z předchozího sekvence, takže budete chtít malloc

673
01:00:08,150 --> 01:00:13,150
a vytvořit nový uzel a mít děti, že [i] přejděte na ni

674
01:00:13,150 --> 01:00:17,890
takže můžete vytvořit - když jsme vložili dopis do obdélníku -

675
01:00:17,890 --> 01:00:23,680
Díky dětem non-NULL a bod do tohoto nového uzlu.

676
01:00:23,680 --> 01:00:28,340
Ale pokud to není NULL, jako v našem případě z FOO

677
01:00:28,340 --> 01:00:34,570
když už jsme měli foobar, budeme pokračovat,

678
01:00:34,570 --> 01:00:44,010
a my se nikdy dělat nový uzel, ale jen nastavit is_word na hodnotu true

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

680
01:00:50,060 --> 01:00:55,340
>> Takže stejně jako předtím, protože zde máte co do činění s každým dopisem v době,

681
01:00:55,340 --> 01:01:01,470
to bude pro vás jednodušší pro velikost, místo toho, aby výpočet

682
01:01:01,470 --> 01:01:06,910
a projít celý strom a vypočítat, kolik dětí mám

683
01:01:06,910 --> 01:01:10,850
a pak odbočení, vzpomněl kolik jsou na levé straně a na pravé straně

684
01:01:10,850 --> 01:01:12,850
a podobné věci, to bude mnohem jednodušší pro vás

685
01:01:12,850 --> 01:01:16,220
pokud jste právě sledovat, kolik slov jste tím, že do

686
01:01:16,220 --> 01:01:18,080
když máte co do činění s nákladem.

687
01:01:18,080 --> 01:01:22,630
A pak se to tak velikost může jen návrat globální proměnné velikosti.

688
01:01:25,320 --> 01:01:28,530
>> Nyní se dostáváme k zkontrolovat.

689
01:01:28,530 --> 01:01:33,920
Stejných standardů jako dříve, kde chceme, aby pro případ necitlivosti.

690
01:01:33,920 --> 01:01:40,400
Stejně, my předpokládáme, že řetězce jsou jen abecední znaky nebo apostrofy

691
01:01:40,400 --> 01:01:44,000
protože děti je pole 27 dlouhé,

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

693
01:01:48,480 --> 01:01:53,800
Pro kontrolu toho, co budete chtít udělat, je, že budete chtít začít u kořene

694
01:01:53,800 --> 01:01:58,440
protože kořen bude ukazovat na pole, které obsahuje

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

696
01:02:01,630 --> 01:02:03,680
Budeš začít tam,

697
01:02:03,680 --> 01:02:11,590
a pak budete kontrolovat, je tato hodnota NULL nebo ne,

698
01:02:11,590 --> 01:02:16,490
protože pokud je hodnota NULL, to znamená, že ve slovníku nemá žádné hodnoty

699
01:02:16,490 --> 01:02:21,480
které obsahují ten dopis v tomto konkrétním pořadí.

700
01:02:21,480 --> 01:02:24,970
Pokud je to NULL, pak to znamená, že toto slovo je chybně hned.

701
01:02:24,970 --> 01:02:27,110
Ale pokud to není NULL, pak můžete pokračovat,

702
01:02:27,110 --> 01:02:34,090
říci, že první písmeno je možné první písmeno ve slově,

703
01:02:34,090 --> 01:02:40,630
tak teď chci zkontrolovat, zda druhý dopis, že sekvence, je v mém slovníku.

704
01:02:40,630 --> 01:02:46,540
Takže se chystáte jít do indexu děti na prvním uzlu

705
01:02:46,540 --> 01:02:50,720
a zkontrolujte, zda druhý dopis existuje.

706
01:02:50,720 --> 01:02:57,440
Pak si opakovat, že proces zkontrolovat, zda posloupnost je platná nebo ne

707
01:02:57,440 --> 01:02:59,060
ve vaší trie.

708
01:02:59,060 --> 01:03:06,430
Kdykoliv uzel děti na to, že indexových bodů na hodnotu NULL,

709
01:03:06,430 --> 01:03:10,710
Víte, že posloupnost neexistuje,

710
01:03:10,710 --> 01:03:16,230
ale pak, když se dostanete na konec slova, které jste vloženy,

711
01:03:16,230 --> 01:03:20,070
pak chcete zkontrolovat teď, že jsem dokončil tuto sekvenci

712
01:03:20,070 --> 01:03:27,610
a zjistil, že je v mém trie, je to, že slovo platí, nebo ne?

713
01:03:27,610 --> 01:03:32,480
A pak se budete chtít zkontrolovat, zda, a to je, když, pokud jste zjistili, že posloupnost,

714
01:03:32,480 --> 01:03:35,120
pak chcete zkontrolovat, zda slovo je platná nebo ne

715
01:03:35,120 --> 01:03:40,290
protože Vzpomínám si v předchozím případě, že jsem nakreslil, kde jsme měli FOOB,

716
01:03:40,290 --> 01:03:48,410
, který byl platný sekvence, které jsme našli, ale nebyla skutečná platné slovo samo o sobě.

717
01:03:50,570 --> 01:03:59,000
>> Podobně, pro vyložit v pokusech, které chcete uvolnit všechny uzly ve vašem trie.

718
01:03:59,000 --> 01:04:04,790
Promiňte. Podobně jako hash tabulky, kde v vyložit jsme osvobodil všechny uzly,

719
01:04:04,790 --> 01:04:09,740
v pokusech, které chceme také uvolnit všechny uzly.

720
01:04:09,740 --> 01:04:15,000
Uvolnit bude skutečně fungovat nejjednodušší zdola nahoru

721
01:04:15,000 --> 01:04:19,290
protože tyto jsou v podstatě spojené seznamy.

722
01:04:19,290 --> 01:04:22,540
Takže chceme se ujistit, že máme na všechny hodnoty

723
01:04:22,540 --> 01:04:25,700
a bez všechny z nich výslovně.

724
01:04:25,700 --> 01:04:28,840
Co budete chtít dělat, když pracujete s trie

725
01:04:28,840 --> 01:04:35,640
je cestovat až na dno a volný nejnižší možnou uzel první

726
01:04:35,640 --> 01:04:39,190
a pak se do všech těchto dětí a pak bez všech těch,

727
01:04:39,190 --> 01:04:43,050
nahoru a pak zdarma, atd.

728
01:04:43,050 --> 01:04:48,790
Něco jako zabývající se spodní vrstvou trie první

729
01:04:48,790 --> 01:04:51,940
a pak jít až nahoru, jakmile jste osvobodil všechno.

730
01:04:51,940 --> 01:04:56,720
Toto je dobrý příklad, kde rekurzivní funkce může hodit.

731
01:04:56,720 --> 01:05:03,830
Jakmile osvobodil spodní vrstvu vašeho trie,

732
01:05:03,830 --> 01:05:08,000
pak volat vyložit na to ostatní,

733
01:05:08,000 --> 01:05:13,620
Ujistěte se, že jste uvolnit každý mini -

734
01:05:13,620 --> 01:05:16,410
Můžete trochu představit, že jako mini pokusů.

735
01:05:23,300 --> 01:05:28,990
Takže máte kořen zde.

736
01:05:30,840 --> 01:05:35,230
Já jen zjednodušit tak, nemám k tomu 26 z nich.

737
01:05:37,250 --> 01:05:43,770
Takže budete mít tyto, a pak tito reprezentují sekvence slov

738
01:05:43,770 --> 01:05:54,620
kde všechny tyto malé kruhy jsou dopisy, které jsou platné posloupnosti písmen.

739
01:06:03,040 --> 01:06:07,160
Pojďme pokračovat jen trochu víc.

740
01:06:15,110 --> 01:06:25,750
Co budete chtít udělat, je zdarma spodní tady a pak zdarma tento

741
01:06:25,750 --> 01:06:31,640
a pak zdarma to jeden na dně před uvolnit horní jeden až sem

742
01:06:31,640 --> 01:06:38,180
protože pokud vás zcela zdarma, něco, co v druhé úrovni zde,

743
01:06:38,180 --> 01:06:47,230
pak skutečně přijdou tuto hodnotu zde.

744
01:06:47,230 --> 01:06:54,780
To je důvod, proč je to důležité v uvolnění pro trie, aby se ujistil, že jste uvolnit dno jako první.

745
01:06:54,780 --> 01:06:59,480
Co budete chtít udělat, je říct, pro každý uzel

746
01:06:59,480 --> 01:07:06,430
Chci vyložit všechny děti.

747
01:07:16,060 --> 01:07:22,140
>> Teď, když jsme pryč přes vyložit na hash tabulky metody, jakož i způsobu trie,

748
01:07:22,140 --> 01:07:27,020
budeme chtít podívat na Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind spustit s následujícími příkazy.

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

751
01:07:32,700 --> 01:07:40,960
Jste kontrola všech netěsností při spuštění pravopisu, stejně to určitý text

752
01:07:40,960 --> 01:07:46,980
protože speller třeba, aby v textovém souboru.

753
01:07:46,980 --> 01:07:52,330
Takže Valgrind bude spusťte program, říct, kolik bytů si přiděleno,

754
01:07:52,330 --> 01:07:57,150
kolik bytů si osvobozen, a to vám řekne, zda jste osvobozen jen dost

755
01:07:57,150 --> 01:07:58,930
nebo zda jste to již dost,

756
01:07:58,930 --> 01:08:02,850
nebo někdy dokonce můžete přes-free, jako je volný uzel, který již byl osvobozen

757
01:08:02,850 --> 01:08:05,140
a tak se vrátíte chyby.

758
01:08:05,140 --> 01:08:11,600
Pokud používáte Valgrind, bude vám některé zprávy

759
01:08:11,600 --> 01:08:15,970
uvede, zda jste osvobozeni buď méně než dost, jen dost,

760
01:08:15,970 --> 01:08:19,609
nebo více než dost časů.

761
01:08:24,370 --> 01:08:30,410
>> Součástí této PSet, je to volitelná napadnout velkou tabuli.

762
01:08:30,410 --> 01:08:35,790
Ale když máme co do činění s těmito datovými strukturami

763
01:08:35,790 --> 01:08:40,689
je to docela zábavné vidět, jak rychle a jak efektivní vaše datové struktury může být.

764
01:08:40,689 --> 01:08:44,490
Má vaše hash funkce mají za následek hodně kolizí?

765
01:08:44,490 --> 01:08:46,300
Nebo je vaše velikost dat opravdu velký?

766
01:08:46,300 --> 01:08:49,420
Má to trvat hodně času projít?

767
01:08:49,420 --> 01:08:54,800
V protokolu o speller, že výstupy, kolik času budete používat pro načtení,

768
01:08:54,800 --> 01:08:57,700
kontrolovat, provádět velikosti, a vyložit,

769
01:08:57,700 --> 01:09:00,720
a tak ty jsou uloženy v The Big radě,

770
01:09:00,720 --> 01:09:03,600
kde můžete soutěžit proti svým spolužákům

771
01:09:03,600 --> 01:09:11,350
a někteří zaměstnanci se vidět, kdo má nejrychlejší pravopisu.

772
01:09:11,350 --> 01:09:14,760
Jedna věc, že ​​bych chtěl poznamenat, o hash tabulky

773
01:09:14,760 --> 01:09:20,470
je to, že tam jsou některé docela jednoduché hashovací funkce, které bychom mohli myslet.

774
01:09:20,470 --> 01:09:27,240
Například, máte 26 vědra, a tak každý kbelík

775
01:09:27,240 --> 01:09:30,200
odpovídá na první písmeno ve slově,

776
01:09:30,200 --> 01:09:35,229
ale že to bude mít za následek docela nevyvážené hash tabulky

777
01:09:35,229 --> 01:09:40,979
protože tam jsou hodně méně slov, které začínají s X než startu se M, například.

778
01:09:40,979 --> 01:09:47,890
Jeden způsob, jak jít o speller je, pokud chcete získat všechny ostatní funkce dolů,

779
01:09:47,890 --> 01:09:53,240
pak stačí použít jednoduchý hash funkce, aby mohli dostat váš kód běží

780
01:09:53,240 --> 01:09:58,650
a pak se vrátit zpět a změnit velikost vaší hash tabulky a definice.

781
01:09:58,650 --> 01:10:03,430
Existuje mnoho zdrojů na internetu pro hašovacích funkcí,

782
01:10:03,430 --> 01:10:08,250
a tak pro tento PSet je povoleno výzkum hash funkce na internetu

783
01:10:08,250 --> 01:10:15,560
o nějaké rady a inspiraci tak dlouho, jak se ujistit, citovat, kde jste získali.

784
01:10:15,560 --> 01:10:22,060
Rádo se stalo se podívat a interpretovat některé hash funkce, které najdete na internetu.

785
01:10:22,060 --> 01:10:27,460
Zpět na to, že můžete být schopni zjistit, jestli někdo použil trie

786
01:10:27,460 --> 01:10:31,700
zda je jejich realizace je rychlejší než váš hašovací tabulky nebo ne.

787
01:10:31,700 --> 01:10:35,290
Můžete odeslat The Big radě vícekrát.

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

789
01:10:37,660 --> 01:10:44,300
Takže možná změníte funkci hash a pak si uvědomí, že je to vlastně mnohem rychleji

790
01:10:44,300 --> 01:10:46,780
nebo mnohem pomalejší než dříve.

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 nebo 2 zaměstnanci, kteří se snaží, aby se nejpomalejší možnou slovník,

793
01:10:57,190 --> 01:11:00,210
tak to je vždycky zábavné se dívat na.

794
01:11:00,210 --> 01:11:07,630
>> Použití pro PSet je spustit pravopisu s volitelným slovníku

795
01:11:07,630 --> 01:11:12,840
a pak povinný textový soubor.

796
01:11:12,840 --> 01:11:18,380
Ve výchozím nastavení při spuštění pravopisu se jen textového souboru a neurčíte slovník,

797
01:11:18,380 --> 01:11:24,410
to bude používat slovník textový soubor, toho velkého

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

799
01:11:27,920 --> 01:11:32,760
Že jeden má více než 100.000 slov.

800
01:11:32,760 --> 01:11:37,950
Mají také malý slovník, který má podstatně méně slov

801
01:11:37,950 --> 01:11:40,730
že CS50 učinil pro vás.

802
01:11:40,730 --> 01:11:44,050
Nicméně, můžete velmi snadno stačí si jen vlastní slovník

803
01:11:44,050 --> 01:11:47,150
pokud si jen chcete pracovat v malých příkladech -

804
01:11:47,150 --> 01:11:51,140
Například, pokud chcete použít gdb a víte, že konkrétní hodnoty

805
01:11:51,140 --> 01:11:53,560
že chcete, aby vaše hash tabulka mapuje na.

806
01:11:53,560 --> 01:12:00,430
Takže stačí vytvořit svůj vlastní textový soubor jen s barem, Bazi, foo, a foobar,

807
01:12:00,430 --> 01:12:04,860
aby to v textovém souboru, oddělit ty, každý s 1 řádek,

808
01:12:04,860 --> 01:12:12,670
a pak vytvořit svůj vlastní textový soubor, který doslova obsahuje pouze možná 1 nebo 2 slova

809
01:12:12,670 --> 01:12:15,950
takže přesně víte, co výstup by měl být.

810
01:12:15,950 --> 01:12:21,870
Některé z ukázkových souborů textových, že Big Board při spuštění úkolu bude kontrolovat

811
01:12:21,870 --> 01:12:25,580
jsou Válka a mír a Jane Austen román nebo něco takového.

812
01:12:25,580 --> 01:12:30,450
Takže, když jste začínal, je to mnohem jednodušší, aby vaše vlastní textové soubory

813
01:12:30,450 --> 01:12:34,160
které obsahují jen pár slov nebo možná 10

814
01:12:34,160 --> 01:12:38,280
takže můžete předvídat, co výsledek by měl být

815
01:12:38,280 --> 01:12:42,880
a ověřit si to proti tomu, aby více kontrolované příklad.

816
01:12:42,880 --> 01:12:45,820
A tak od té doby máme co do činění s předpovídání a kreslení věci kolem,

817
01:12:45,820 --> 01:12:48,690
jednou chci povzbudit, abyste se používat tužku a papír

818
01:12:48,690 --> 01:12:50,700
protože je to opravdu ti pomůže s tímhle -

819
01:12:50,700 --> 01:12:55,620
kreslení šipek, jak hash tabulka nebo jak se vaše trie vypadá,

820
01:12:55,620 --> 01:12:57,980
když jste uvolnění něco, kde se šipky jedete,

821
01:12:57,980 --> 01:13:01,730
se držíš na dost, vidíte nějaké odkazy mizí

822
01:13:01,730 --> 01:13:05,750
a pádu do propasti unikly paměti.

823
01:13:05,750 --> 01:13:11,070
Takže, prosím, zkuste nakreslit věci ještě předtím, než se dostanete k psaní kódu dolů.

824
01:13:11,070 --> 01:13:14,520
Nakreslete věci tak, že jste pochopili, jak se věci chodit do práce

825
01:13:14,520 --> 01:13:22,750
protože pak jsem zaručit, že budete spouštět do méně ukazatel muddles tam.

826
01:13:24,270 --> 01:13:25,910
>> Dobrá.

827
01:13:25,910 --> 01:13:28,780
Chci vám popřát hodně štěstí s tímto PSet.

828
01:13:28,780 --> 01:13:31,980
Je to asi nejtěžší.

829
01:13:31,980 --> 01:13:40,360
Tak zkuste začít brzy, kreslit věci, kreslit věci, a hodně štěstí.

830
01:13:40,360 --> 01:13:42,980
To bylo Návod 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]