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

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

3
00:00:04,870 --> 00:00:07,190
[Acest lucru este CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Bine. Bună ziua, tuturor, si bun venit la Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 este Scriere, in care vom face o vraja-checker.

6
00:00:17,400 --> 00:00:21,030
Spell-dame sunt extrem de importante.

7
00:00:21,030 --> 00:00:23,390
Sa această ți sa întâmplat vreodată?

8
00:00:23,390 --> 00:00:27,170
Tu lucrezi foarte, foarte acumulează pe o hârtie de o ciocnire

9
00:00:27,170 --> 00:00:33,120
și apoi ajunge în continuare obținerea unei Rade strălucire foarte ca un D sau o = D

10
00:00:33,120 --> 00:00:39,390
și tot pentru că sunteți leberwurst spoilerul din cuvântul balena larg.

11
00:00:39,390 --> 00:00:44,710
Da, corectura ardei dvs. este o chestiune de, impotenta cea mai mare măsură.

12
00:00:44,710 --> 00:00:49,140
Aceasta este o problemă care afectează elevii masculine, bărbătești.

13
00:00:49,140 --> 00:00:56,260
Am fost o dată spus de către călăul meu clasa sith că n-ar intra într-o bun coleg.

14
00:00:56,260 --> 00:01:00,250
Și asta e tot ce mi-am dorit, asta-i tot orice copil vrea la vârsta mea,

15
00:01:00,250 --> 00:01:04,569
doar pentru a obține într-un bun coleg.

16
00:01:04,569 --> 00:01:12,720
Și nu orice fel de coleg. Nu, am vrut să merg la un coleg juridic de Fildeș.

17
00:01:12,720 --> 00:01:18,360
Așa că, dacă nu am făcut îmbunătățiri, ar fi dus visele mele de a merge la Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, sau Prison - Știi, în închisoare, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Așa că am luat eu o verificatorul ortografic.

20
00:01:25,170 --> 00:01:29,380
Asta e un fragment mic de la unul din artiștii mei favoriți sugerate vorbite, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Oricum, după cum spune el, importanța de a avea o vraja-pul este foarte importantă.

22
00:01:34,630 --> 00:01:39,440
>> Deci, bun venit la Walkthrough 5, în care vom vorbi despre pset5: greșeli de ortografie,

23
00:01:39,440 --> 00:01:44,300
în care vom fi a face propriile noastre foarte verificatorul ortografic.

24
00:01:44,300 --> 00:01:50,880
Setul de instrumente pentru această săptămână, codul de distribuție, va fi important să se uite la

25
00:01:50,880 --> 00:01:54,950
doar pentru a înțelege diferitele funcții pe care dicționarul dvs. este de gând să aibă.

26
00:01:54,950 --> 00:02:01,500
Suntem de fapt de gând să fi având mai multe fișiere. C, care fac împreună PSET nostru.

27
00:02:01,500 --> 00:02:05,420
Și astfel în căutarea prin diferitele aspecte, chiar dacă nu suntem de fapt, editare

28
00:02:05,420 --> 00:02:10,770
unul dintre fișierele, speller.c, știind cum funcționează cu privire la dictionary.c,

29
00:02:10,770 --> 00:02:14,100
care vom fi scris, va fi destul de important.

30
00:02:14,100 --> 00:02:16,970
Spec. PSET conține, de asemenea, o mulțime de informații utile

31
00:02:16,970 --> 00:02:21,360
în ceea ce privește lucrurile pe care le poate asuma, reguli și lucruri de genul asta,

32
00:02:21,360 --> 00:02:24,710
astfel încât să fie sigur de a citi cu atenție spec. PSET pentru sfaturi.

33
00:02:24,710 --> 00:02:29,310
Și când în dubiu de o regula sau ceva de genul asta, atunci se referă întotdeauna la spec. PSET

34
00:02:29,310 --> 00:02:31,550
Discutați sau.

35
00:02:31,550 --> 00:02:34,060
Acest PSET este de gând să se bazeze foarte mult pe indicii,

36
00:02:34,060 --> 00:02:37,890
așa că doriți să vă asigurați că înțelegem diferența dintre stele adăugarea

37
00:02:37,890 --> 00:02:41,680
în fața numelui pointer și ampersand, cum să le elibereze, etc

38
00:02:41,680 --> 00:02:47,550
Deci, fiind un maestru al pointeri va fi de mare ajutor în acest set de probleme.

39
00:02:47,550 --> 00:02:50,460
Ne vom uita în liste legate de un pic mai mult,

40
00:02:50,460 --> 00:02:57,790
în cazul în care avem elemente pe care le numim noduri, care au atât o valoare, precum și un indicator

41
00:02:57,790 --> 00:03:02,520
la nodul următor, și așa mai departe, în esență care leagă diferitele elemente, una după alta.

42
00:03:02,520 --> 00:03:07,190
Există câteva opțiuni diferite de punere în aplicare dicționarul dvs. real.

43
00:03:07,190 --> 00:03:13,150
Ne vom uita în două metode principale, care este tabele de dispersie și apoi încearcă.

44
00:03:13,150 --> 00:03:17,660
În ambele acestea, ele implică un fel de noțiunii de listă legată

45
00:03:17,660 --> 00:03:20,790
în cazul în care v-ați elemente legate una de alta.

46
00:03:20,790 --> 00:03:25,640
Și așa am de gând să se uite peste modul în care ar putea fi în măsură să opereze în jurul valorii de liste legate,

47
00:03:25,640 --> 00:03:29,680
creați-le, navigați în ceea ce privește modul de a, de exemplu, se introduce un nod în ea

48
00:03:29,680 --> 00:03:32,760
sau gratuit, toate nodurile, precum și.

49
00:03:32,760 --> 00:03:34,740
În ceea ce privește noduri furtună, asta e foarte important

50
00:03:34,740 --> 00:03:37,700
că ori de câte ori am de memorie malloc, după care l-am elibera.

51
00:03:37,700 --> 00:03:42,910
Deci, vrem să ne asigurăm că nu merge indicatorul unfreed, că nu avem nici o scurgere de memorie.

52
00:03:42,910 --> 00:03:48,330
Vom introduce un instrument numit Valgrind care execută programul tău

53
00:03:48,330 --> 00:03:52,260
și verifică dacă toate de memorie pe care le alocată este apoi eliberat.

54
00:03:52,260 --> 00:03:59,080
PSET este completă doar atunci când aceasta funcționează și are funcționalitate completă,

55
00:03:59,080 --> 00:04:03,990
dar, de asemenea, Valgrind vă spune că nu ați găsit nici o scurgere de memorie.

56
00:04:03,990 --> 00:04:06,690
În cele din urmă, pentru acest PSET, chiar vreau să subliniez -

57
00:04:06,690 --> 00:04:11,360
Adică, ca de obicei, eu sunt cu siguranta un suporter de a folosi creion și hârtie pentru seturi de problema ta,

58
00:04:11,360 --> 00:04:14,840
dar pentru asta, cred că stilou și hârtie va fi deosebit de important

59
00:04:14,840 --> 00:04:19,000
atunci când doriți să fie desen săgețile pentru a înțelege lucrurile și cum funcționează lucrurile.

60
00:04:19,000 --> 00:04:24,440
Deci, încercați cu siguranta pentru a utiliza un stilou și hârtie pentru a trage lucrurile înainte de a te codificare

61
00:04:24,440 --> 00:04:26,970
deoarece ar putea obține un pic murdar.

62
00:04:26,970 --> 00:04:30,700
>> În primul rând, hai să mergem în liste legate de un pic.

63
00:04:30,700 --> 00:04:35,510
Lista de preturi legate constau din noduri, unde fiecare nod are o valoare asociată cu acesta,

64
00:04:35,510 --> 00:04:39,810
precum și un pointer la nodul următor după el.

65
00:04:39,810 --> 00:04:43,680
Un tânăr de lucruri importante cu listele legate sunt că avem nevoie să ne amintim

66
00:04:43,680 --> 00:04:48,810
în cazul în care primul nostru este nod, și apoi o dată știm unde este primul nod,

67
00:04:48,810 --> 00:04:52,990
în acest fel putem accesa nodul care primele puncte de nod la

68
00:04:52,990 --> 00:04:55,850
și apoi una după care și una după asta.

69
00:04:55,850 --> 00:05:00,340
Si apoi ultimul element din lista dvs. de legat este indicatorul care nodului

70
00:05:00,340 --> 00:05:02,340
este întotdeauna de gând să indice NULL.

71
00:05:02,340 --> 00:05:08,230
Atunci când un nod de puncte la NULL, atunci știi că ai ajuns la sfârșitul listei,

72
00:05:08,230 --> 00:05:12,320
că nodul este ultima, că nu e nimic după aceea.

73
00:05:12,320 --> 00:05:16,970
Aici, în acest schematică, veți vedea că săgețile sunt indicii,

74
00:05:16,970 --> 00:05:20,290
și secțiunea albastră este în cazul în care valoarea este stocată,

75
00:05:20,290 --> 00:05:24,420
și apoi caseta de culoare roșie, cu indicatorul la aceasta este indicatorul nodului

76
00:05:24,420 --> 00:05:27,050
arătând spre nodul următor după el.

77
00:05:27,050 --> 00:05:33,730
Și așa te văd aici, nodul D ar indica NULL, deoarece acesta este ultimul element din listă.

78
00:05:33,730 --> 00:05:38,240
>> Să ne uităm la modul în care am putea defini o struct pentru un nod.

79
00:05:38,240 --> 00:05:40,130
Si din moment ce dorim să avem mai multe noduri,

80
00:05:40,130 --> 00:05:43,180
acest lucru se întâmplă pentru a deveni un typedef struct

81
00:05:43,180 --> 00:05:46,870
în care vom avea mai multe instanțe diferite de noduri.

82
00:05:46,870 --> 00:05:50,850
Și așa l-am defini ca un nou tip de date.

83
00:05:50,850 --> 00:05:53,630
Aici, avem un nod typedef struct.

84
00:05:53,630 --> 00:05:56,160
În acest exemplu, avem de-a face cu noduri întregi,

85
00:05:56,160 --> 00:06:00,490
așa că avem o valoare de tip întreg numit și apoi avem un alt indicator,

86
00:06:00,490 --> 00:06:07,390
și, în acest caz, este un pointer la un nod, așa că avem un nod struct * numit următoare.

87
00:06:07,390 --> 00:06:09,520
Și apoi ne suni acest nod totul.

88
00:06:09,520 --> 00:06:11,110
Asigurați-vă că urmați această sintaxă.

89
00:06:11,110 --> 00:06:17,940
Observați că nodul este de fapt face referire la mai sus, precum și sub acolade.

90
00:06:17,940 --> 00:06:23,400
Apoi, pentru a ține evidența în cazul în care nod prima mea este în această listă legată,

91
00:06:23,400 --> 00:06:29,390
atunci am un pointer nodul numit cap, si am spatiu suficient pentru malloc dimensiunea unui nod.

92
00:06:29,390 --> 00:06:36,240
Comunicarea, cu toate acestea, faptul că șeful este de fapt un pointer nod, spre deosebire de un nod în sine.

93
00:06:36,240 --> 00:06:40,130
Deci, de fapt, capul nu conține nici o valoare,

94
00:06:40,130 --> 00:06:45,590
doar arată spre oricare dintre primul nod din lista mea legată este.

95
00:06:55,080 --> 00:06:58,340
>> Pentru a obține un sentiment mai bună a listelor legate, pentru că e foarte important

96
00:06:58,340 --> 00:07:02,220
pentru a urmări asigurându-vă că vă menține lanțul,

97
00:07:02,220 --> 00:07:09,990
Îmi place să mă gândesc la ea ca oamenii dintr-o linie de tinutul de mana,

98
00:07:09,990 --> 00:07:14,330
în cazul în care fiecare persoană este tinutul de mana cu următoarea.

99
00:07:14,330 --> 00:07:18,350
Nu puteți vedea în acest desen, dar în esență ei indică spre următoarea persoană

100
00:07:18,350 --> 00:07:23,760
care este în lanțul lor.

101
00:07:23,760 --> 00:07:29,270
Și așa că, dacă vrei să traverseze o listă legat în cazul în care acești oameni -

102
00:07:29,270 --> 00:07:32,830
imagina toate aceste persoane au valori asociate cu acestea

103
00:07:32,830 --> 00:07:36,590
și, de asemenea, punctul următoarea persoană în linie -

104
00:07:36,590 --> 00:07:40,810
dacă doriți să traverseze lista de legat, de exemplu, pentru a edita fie valorilor

105
00:07:40,810 --> 00:07:42,830
sau căutați pentru o valoare sau ceva de genul asta,

106
00:07:42,830 --> 00:07:48,270
atunci veți dori să aibă un pointer la anumite persoane.

107
00:07:48,270 --> 00:07:52,670
Deci, vom avea un nod de date pointer de tip.

108
00:07:52,670 --> 00:07:55,580
Pentru acest exemplu, să-i spunem cursorul.

109
00:07:55,580 --> 00:07:59,630
Un alt mod comun pentru a numi acest lucru ar fi iterator sau ceva de genul asta

110
00:07:59,630 --> 00:08:05,130
deoarece este iterarea peste si de fapt se deplasează pe care nodul este îndreptat spre.

111
00:08:05,130 --> 00:08:14,410
Acest lucru va fi aici cursorul noastră.

112
00:08:14,410 --> 00:08:20,180
Cursorul nostru va indica primul primul element din lista noastră.

113
00:08:20,180 --> 00:08:26,910
Și astfel ceea ce dorim să facem este ne-ar fi continuarea practic cursorul,

114
00:08:26,910 --> 00:08:29,130
deplasându-l dintr-o parte în alta.

115
00:08:29,130 --> 00:08:33,409
În acest caz, vrem să-l mutați la următorul element din listă.

116
00:08:33,409 --> 00:08:38,480
Cu matrice, ceea ce ne-ar face este să ne spunem doar că creșterea indicelui de 1.

117
00:08:38,480 --> 00:08:46,020
În acest caz, ceea ce trebuie să facem este să găsească de fapt pe care persoana această persoană curent este îndreptat spre,

118
00:08:46,020 --> 00:08:48,930
și că va fi următoarea valoare.

119
00:08:48,930 --> 00:08:53,230
Deci, în cazul în care cursorul este doar un pointer nod, atunci ceea ce vrem să facem

120
00:08:53,230 --> 00:08:56,320
este vrem să ajungem la valoarea pe care cursorul se indică spre.

121
00:08:56,320 --> 00:09:01,350
Dorim să ajungem la acel nod și apoi, odată ce suntem la acel nod, că în cazul în care este îndreptat spre.

122
00:09:01,350 --> 00:09:05,820
Pentru a ajunge la nodul real pe care cursorul este îndreptat spre,

123
00:09:05,820 --> 00:09:13,160
de obicei, vom indica aceasta prin (* cursor).

124
00:09:13,160 --> 00:09:19,160
Asta ar da nodul real pe care cursorul se indică spre.

125
00:09:19,160 --> 00:09:21,730
Și apoi după aceea, ceea ce vrem sa facem este vrem să acceseze

126
00:09:21,730 --> 00:09:25,680
indiferent de faptul că valoarea nodului urmator este.

127
00:09:25,680 --> 00:09:32,820
Pentru a face acest lucru, pentru a accesa valorile din interiorul struct, avem operator de punct.

128
00:09:32,820 --> 00:09:39,530
Deci, atunci ar fi (* cursor). Următor.

129
00:09:39,530 --> 00:09:44,840
Dar acest lucru este un pic dezordonat din punct de vedere având paranteze în jurul valorii de cursorului *,

130
00:09:44,840 --> 00:09:56,800
și astfel vom înlocui această declarație întregi, cu cursorul->.

131
00:09:56,800 --> 00:10:02,700
Aceasta este o liniuță și apoi un semn mai mare decât, făcând astfel o săgeată.

132
00:10:02,700 --> 00:10:05,840
cursorul-> urmator.

133
00:10:05,840 --> 00:10:12,390
Care va primi de fapt, vă nodul care punctele de la cursorul. Această valoare este de viitor.

134
00:10:12,390 --> 00:10:16,790
Deci, în loc de a avea stele și punct, esti înlocuind asta cu o săgeată.

135
00:10:16,790 --> 00:10:24,820
Fii foarte atent pentru a asigurați-vă că încercați să utilizați această sintaxă.

136
00:10:33,550 --> 00:10:37,620
>> Acum, că avem cursorul noastre, dacă vrem să acceseze valoarea,

137
00:10:37,620 --> 00:10:40,450
înainte, am avut cursorul-> urmator,

138
00:10:40,450 --> 00:10:46,260
dar pentru a accesa valoarea de la nodul care cursorul este orientată spre, ne-am spus pur și simplu

139
00:10:46,260 --> 00:10:48,070
nod-> valoare.

140
00:10:48,070 --> 00:10:53,600
De acolo, e de tipul de date tot ce ne-am definit valorile și noduri de a fi.

141
00:10:53,600 --> 00:10:59,620
Dacă e un nod int, atunci cursorul-> valoare este doar de gând să fie un număr întreg.

142
00:10:59,620 --> 00:11:04,870
Astfel încât să putem face operații pe care, verificați egalități, aloca valori diferite, etc

143
00:11:04,870 --> 00:11:11,090
Deci, atunci ceea ce vrei să faci în cazul în care doriți să mutați cursorul la următoarea persoană,

144
00:11:11,090 --> 00:11:15,270
ai schimba de fapt valoarea cursorului.

145
00:11:15,270 --> 00:11:19,340
Deoarece cursorul este un pointer nod, vă schimbați adresa de indicatorul reală

146
00:11:19,340 --> 00:11:23,890
la adresa nodului următor din lista ta.

147
00:11:23,890 --> 00:11:28,930
Acesta este doar un cod în cazul în care ai putea repeta.

148
00:11:28,930 --> 00:11:31,230
În cazul în care am comentariu facă ceva,

149
00:11:31,230 --> 00:11:33,850
asta e în cazul în care probabil te duci pentru a accesa valoarea

150
00:11:33,850 --> 00:11:37,850
sau de a face ceva de-a face cu acel nod specific.

151
00:11:37,850 --> 00:11:43,050
Pentru a începe, am spune că cursorul meu inițial

152
00:11:43,050 --> 00:11:48,430
se va indica primul element din listă legată.

153
00:11:48,430 --> 00:11:52,910
Și astfel în față, l-am definit ca șef al nodului.

154
00:11:52,910 --> 00:11:57,610
>> Așa cum am menționat mai înainte, eliberând este foarte important.

155
00:11:57,610 --> 00:12:02,440
Doriți să vă asigurați că ați elibera fiecare element în listă, odată ce ați terminat cu ea.

156
00:12:02,440 --> 00:12:04,940
Când nu trebuie să facă referire la oricare dintre aceste indicii mai,

157
00:12:04,940 --> 00:12:10,620
doriți să vă asigurați că vă elibera toate aceste indicii.

158
00:12:10,620 --> 00:12:14,460
Dar vrei să fim foarte atenți aici, în care doriți, pentru a evita orice scurgeri de memorie.

159
00:12:14,460 --> 00:12:25,080
Dacă aveți o singură persoană liber prematur, atunci toate indicii că această punctele de nod la

160
00:12:25,080 --> 00:12:26,900
vor fi pierdute.

161
00:12:26,900 --> 00:12:32,070
Revenind la exemplul persoana pentru a face un pic mai mari mize,

162
00:12:32,070 --> 00:12:49,600
să aibă acești oameni, cu excepția cazului în acest caz, ei sunt deasupra unui lac cu un monstru.

163
00:12:49,600 --> 00:12:53,200
Dorim să vă asigurați că ori de câte ori ne eliberăm, să nu pierdem

164
00:12:53,200 --> 00:12:58,920
și să mergem la orice noduri înainte de a-am de fapt, le-a eliberat.

165
00:12:58,920 --> 00:13:05,730
De exemplu, dacă ați fost de a apela pur și simplu gratuit pe tipul ăsta aici,

166
00:13:05,730 --> 00:13:15,350
atunci el va fi eliberat, dar apoi toate aceste baieti ar fi pierdut

167
00:13:15,350 --> 00:13:18,450
și le-ar adormiți și cad jos.

168
00:13:18,450 --> 00:13:24,900
Deci, vrem să ne asigurăm că, în loc, dorim să mențină o legătură restul.

169
00:13:37,630 --> 00:13:42,480
Indicatorul nostru central, care indică primul element din listă.

170
00:13:42,480 --> 00:13:49,990
E ca un fel de frânghie de ancorare prima persoană.

171
00:13:52,870 --> 00:13:57,470
Ce ar putea să doriți să faceți atunci când vă elibera o listă se avea -

172
00:13:57,470 --> 00:14:04,520
Dacă doriți să eliberați primul element în primul rând, atunci puteți avea un pointer temporar

173
00:14:04,520 --> 00:14:07,370
faptul că punctele de la orice Primul element este.

174
00:14:07,370 --> 00:14:11,420
Deci, aveți indicatorul temporară îndreptat aici.

175
00:14:11,420 --> 00:14:15,840
În acest fel, avem o așteptare de primul nod.

176
00:14:15,840 --> 00:14:18,930
Și apoi, din moment ce știm că primul nod va fi eliberat,

177
00:14:18,930 --> 00:14:24,890
atunci ne putem muta acest frânghie, această ancoră, capul nostru,

178
00:14:24,890 --> 00:14:31,930
pentru a indica de fapt, la orice primul indică spre.

179
00:14:31,930 --> 00:14:38,760
Deci, acest cap de fapt indică al doilea element acum.

180
00:14:38,760 --> 00:14:43,980
Acum ne este permis pentru a elibera tot ceea ce este stocat în temp,

181
00:14:43,980 --> 00:14:53,360
și astfel încât să putem șterge că fără ea pune în pericol toate celelalte noduri din lista noastră.

182
00:14:54,140 --> 00:15:05,020
Un alt mod pe care le-ar putea face acest lucru ar putea fi

183
00:15:05,020 --> 00:15:08,650
de fiecare dată când tocmai elibera ultimul element din listă

184
00:15:08,650 --> 00:15:11,010
deoarece acestea sunt garantate de a nu fi indicat nimic.

185
00:15:11,010 --> 00:15:15,570
Deci, ai putea elibera doar pe asta, atunci gratuită aceasta, atunci fără aceasta.

186
00:15:15,570 --> 00:15:21,900
Asta cu siguranta funcționează, dar este un pic mai lent, deoarece prin natura listelor legate,

187
00:15:21,900 --> 00:15:24,670
nu putem pur și simplu sări imediat la ultima.

188
00:15:24,670 --> 00:15:28,030
Trebuie să traverseze fiecare element din listă legată

189
00:15:28,030 --> 00:15:31,020
și verificați dacă unul este faptul că indică spre NULL, verificați de fiecare dată,

190
00:15:31,020 --> 00:15:33,780
și apoi, odată ce vom ajunge la sfârșitul anului, atunci gratuit care.

191
00:15:33,780 --> 00:15:40,270
Dacă ar fi să faci acest proces, v-ar fi de fapt de verificare aici,

192
00:15:40,270 --> 00:15:44,190
verificarea aici, apoi verificând aici, eliberându-l,

193
00:15:44,190 --> 00:15:47,470
apoi merge înapoi, verificarea aici, verificarea aici, eliberându-l,

194
00:15:47,470 --> 00:15:49,660
verificarea aici, și apoi eliberarea.

195
00:15:49,660 --> 00:15:52,880
Care ia un pic mai mult timp. Da.

196
00:15:52,880 --> 00:15:59,060
>> [Elev] Ar fi posibil să se facă o listă legată care stochează un pointer ieșire la sfârșit?

197
00:15:59,060 --> 00:16:01,320
Asta ar fi cu siguranta posibil.

198
00:16:01,320 --> 00:16:08,340
Pentru a repeta întrebarea, este posibil să aibă o structură listă legată

199
00:16:08,340 --> 00:16:12,490
astfel că aveți un pointer ce indică spre sfârșitul listei legate?

200
00:16:12,490 --> 00:16:18,090
Aș spune că e posibil, și de fiecare dată când introduceți ceva în lista de legat

201
00:16:18,090 --> 00:16:21,470
va trebui să actualizeze că indicatorul și lucruri de genul asta.

202
00:16:21,470 --> 00:16:26,640
Tu ar trebui o coada * nod, de exemplu.

203
00:16:26,640 --> 00:16:29,840
Dar când ești punerea în aplicare a acestei funcții, va trebui să se gândească la compromisuri,

204
00:16:29,840 --> 00:16:32,700
place cum de multe ori am de gând să fie iterarea peste acest lucru,

205
00:16:32,700 --> 00:16:36,100
Cat de greu este de gând să fie de a ține evidența coada, precum și capul

206
00:16:36,100 --> 00:16:38,400
precum și iterator meu, si lucruri de genul asta.

207
00:16:40,730 --> 00:16:42,480
Face asta -? >> [Elev] Da.

208
00:16:42,480 --> 00:16:48,270
E posibil, dar în ceea ce privește deciziile de proiectare, va trebui să cântărească opțiunile.

209
00:16:53,850 --> 00:17:01,090
>> Aici este un schelet de cod care să vă permită să elibereze orice element într-o listă legată.

210
00:17:01,090 --> 00:17:05,460
Din nou, deoarece am iterarea peste o listă legat, am de gând să doriți să aveți un fel de cursorului

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

212
00:17:08,670 --> 00:17:14,640
Suntem iterarea până când cursorul este NULL.

213
00:17:14,640 --> 00:17:17,640
Tu nu vrei să itera atunci când cursorul este NULL

214
00:17:17,640 --> 00:17:20,579
pentru că înseamnă că nu există nimic în listă.

215
00:17:20,579 --> 00:17:25,069
Deci, atunci aici am face un nod * temporar

216
00:17:25,069 --> 00:17:29,610
arătând spre ceea ce eu sunt în considerare este prima lista mea,

217
00:17:29,610 --> 00:17:35,340
si apoi mi-am muta cursorul meu înainte 1 și apoi gratuit orice am avut-o în depozitare temporară.

218
00:17:38,460 --> 00:17:43,650
>> Acum am ajuns la inserarea în liste legate.

219
00:18:00,200 --> 00:18:09,660
Am trei noduri din lista mea de legat, și să mergem cu cazul simplu

220
00:18:09,660 --> 00:18:18,970
în cazul în care dorim să inserați un alt nod la sfârșitul listei noastre legate.

221
00:18:18,970 --> 00:18:25,980
Pentru a face asta, tot ne-ar face este să ne traverseze

222
00:18:25,980 --> 00:18:32,100
pentru a găsi în cazul în care la sfârșitul curentă a listei este legată, atât de oricare nod indică spre NULL -

223
00:18:32,100 --> 00:18:33,850
asta e aceasta -

224
00:18:33,850 --> 00:18:37,260
și apoi spun, de fapt, acesta nu va fi ultimul nod;

225
00:18:37,260 --> 00:18:39,830
de fapt, vom avea o alta.

226
00:18:39,830 --> 00:18:46,260
Deci, am avea acest curent la un punct la tot ce ne introduce.

227
00:18:46,260 --> 00:18:50,080
Deci, acum, această persoană devine roșu aici, ultimul nod în listă legată.

228
00:18:50,080 --> 00:18:56,080
Și astfel caracteristica de ultimul nod în lista de legat este că arată la NULL.

229
00:18:56,080 --> 00:19:09,380
Deci, atunci ce ne-ar trebui să faceți este să setați indicatorul acest tip roșu la NULL. Acolo.

230
00:19:09,380 --> 00:19:25,370
>> Dar dacă ne-am dorit pentru a insera un nod între al doilea și al treilea?

231
00:19:25,370 --> 00:19:28,960
Asta nu este chiar atat de simplu, pentru că vrem să ne asigurăm

232
00:19:28,960 --> 00:19:34,290
că noi nu da drumul la orice nod din lista noastră legată.

233
00:19:34,290 --> 00:19:43,450
Ceea ce ne-ar trebui să faceți este să vă asigurați că ne ancora la fiecare dintre ele.

234
00:19:43,450 --> 00:19:49,900
De exemplu, să numim această doilea.

235
00:19:49,900 --> 00:19:54,390
Dacă ai spus cel de al doilea arată acum la acest nou

236
00:19:54,390 --> 00:20:02,520
și ai făcut doar un pointer acolo, atunci care ar duce la acest tip se pierde

237
00:20:02,520 --> 00:20:07,830
pentru că nu există nici o legătură cu el.

238
00:20:07,830 --> 00:20:18,970
În schimb - Voi desena acest lucru din nou. Scuză-abilitățile mele artistice.

239
00:20:18,970 --> 00:20:26,570
Noi știm că nu putem pur și simplu link direct 2 la unul nou.

240
00:20:26,570 --> 00:20:30,480
Trebuie să ne asigurăm că vom ține pe ultima.

241
00:20:30,480 --> 00:20:39,200
Ce am putea dori să faceți este să aibă un pointer temporar

242
00:20:39,200 --> 00:20:42,650
la elementul care va fi anexată la.

243
00:20:42,650 --> 00:20:45,140
Deci, atunci avem un pointer temporar acolo.

244
00:20:45,140 --> 00:20:50,780
Din moment ce știm că această treime este ținut evidența,

245
00:20:50,780 --> 00:20:53,680
2 poate lega acum la o noua noastră.

246
00:20:53,680 --> 00:20:57,490
Și dacă acest nou tip roșu va fi între 2 și 3,

247
00:20:57,490 --> 00:21:05,550
atunci ceea ce este indicatorul care tipului de gând să indice? >> [Elev] Temp.

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

249
00:21:07,490 --> 00:21:15,430
Deci, atunci valoarea acestui tip de culoare roșie de pe lângă va fi temp.

250
00:21:26,090 --> 00:21:33,010
Când sunteți introducerea în liste legate, am văzut că am putut

251
00:21:33,010 --> 00:21:38,260
adăuga cu ușurință ceva la capăt, prin crearea unei matrice temporară,

252
00:21:38,260 --> 00:21:42,850
sau în cazul în care am vrut să adauge ceva în mijlocul nostru matrice,

253
00:21:42,850 --> 00:21:46,810
atunci ar fi nevoie de un pic mai mult în jurul valorii de amestecare.

254
00:21:46,810 --> 00:21:50,240
Dacă doriți, de exemplu, au o listă sortată legat,

255
00:21:50,240 --> 00:21:54,880
atunci va trebui să cântărească fel de costurile și beneficiile pe care

256
00:21:54,880 --> 00:21:59,720
pentru că, dacă doriți să aveți o matrice sortate, ceea ce înseamnă că de fiecare dată când introduceți în ea,

257
00:21:59,720 --> 00:22:01,630
este de gând să ia un pic mai mult timp.

258
00:22:01,630 --> 00:22:05,500
Cu toate acestea, dacă doriți să mai târziu, după cum vom găsi, vom dori să,

259
00:22:05,500 --> 00:22:10,280
căutare printr-o listă legată, atunci ar putea fi mai ușor dacă știți că totul este în ordine.

260
00:22:10,280 --> 00:22:15,340
Deci, este posibil să doriți să cântărească costurile și beneficiile de care.

261
00:22:20,150 --> 00:22:27,740
>> Un alt mod de a introduce într-o listă legată este de a insera în începutul unei liste.

262
00:22:27,740 --> 00:22:34,700
Dacă tragem ancora noastră aici - acest lucru este capul nostru -

263
00:22:34,700 --> 00:22:40,960
și apoi au acești oameni legate de acesta,

264
00:22:40,960 --> 00:22:48,460
si apoi avem un nou nod care urmează să fie introdus în început,

265
00:22:48,460 --> 00:22:52,590
atunci ceea ce ar putea vrem să facem?

266
00:22:55,220 --> 00:23:03,580
Ce-ar fi greșit cu doar că vreau să legați roșu la albastru,

267
00:23:03,580 --> 00:23:05,790
pentru că e primul?

268
00:23:05,790 --> 00:23:08,570
Ce s-ar întâmpla aici?

269
00:23:08,570 --> 00:23:12,130
Toate acestea trei ar fi pierdut.

270
00:23:12,130 --> 00:23:14,140
Așa că nu vreau să fac asta.

271
00:23:14,140 --> 00:23:21,430
Din nou, am învățat că trebuie să avem un fel de indicator temporar.

272
00:23:21,430 --> 00:23:34,470
Să aleg să aibă un punct de temporar pentru acest tip.

273
00:23:34,470 --> 00:23:39,640
Atunci putem avea un punct albastru spre temporar

274
00:23:39,640 --> 00:23:43,240
și apoi punct rosu la albastru.

275
00:23:43,240 --> 00:23:47,830
Motivul pentru care am Sunt folosind oamenii de aici este pentru că ne dorim cu adevărat să vizualizeze

276
00:23:47,830 --> 00:23:53,180
tinandu-se de oameni și asigurându-vă că avem un link pentru a le

277
00:23:53,180 --> 00:23:57,590
înainte de a ne da drumul de alta parte sau ceva de genul asta.

278
00:24:05,630 --> 00:24:10,650
>> Acum, că avem un sentiment de preturi legate de - cum putem să creați o listă de legat

279
00:24:10,650 --> 00:24:15,090
și de a crea structurile de care constă în definiția de tip pentru un nod

280
00:24:15,090 --> 00:24:19,060
și apoi asigurându-vă că avem un pointer la capul acestei liste legate -

281
00:24:19,060 --> 00:24:23,210
o dată că avem și știm cum să traverseze printr-o matrice,

282
00:24:23,210 --> 00:24:28,200
accesa diverse elemente, știm cum să inserați și știm cum să le elibereze,

283
00:24:28,200 --> 00:24:30,260
atunci putem intra în greșeli de ortografie.

284
00:24:30,260 --> 00:24:38,150
Ca de obicei, avem și o secțiune de întrebări care vor fi folosite pentru a vă operare cu liste legate

285
00:24:38,150 --> 00:24:41,750
și structuri diferite, cum ar fi cozile și stive.

286
00:24:41,750 --> 00:24:46,000
Apoi, ne putem muta în greșeli de ortografie.

287
00:24:46,000 --> 00:24:55,170
>> Greșeli de ortografie are în codul de distribuție o serie de fișiere de importanță.

288
00:24:55,170 --> 00:24:58,850
În primul rând observăm că avem această Makefile aici,

289
00:24:58,850 --> 00:25:03,040
care nu ne-am întâlnit cu adevărat înainte.

290
00:25:03,040 --> 00:25:10,090
Dacă te-ai uitat în interiorul folderul pset5, vei observa că aveți un fișier ore.,

291
00:25:10,090 --> 00:25:12,530
atunci aveți două fișiere. c..

292
00:25:12,530 --> 00:25:18,920
Ce face acest Makefile este înainte, ne-ar face doar de tip și apoi numele programului

293
00:25:18,920 --> 00:25:25,550
și apoi ne-ar vedea toate aceste argumente și steaguri trecut in pentru a compilatorului.

294
00:25:25,550 --> 00:25:30,580
Ce face Makefile este ne permite să compileze mai multe fișiere în același timp

295
00:25:30,580 --> 00:25:34,650
și treci în pavilioanele pe care ne-o dorim.

296
00:25:34,650 --> 00:25:41,300
Aici vom vedea acolo este un fișier header aici.

297
00:25:41,300 --> 00:25:43,730
Apoi, avem de fapt două fișiere sursă.

298
00:25:43,730 --> 00:25:47,520
Avem speller.c și dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Sunteți bineveniți să editați Makefile, dacă doriți.

300
00:25:54,560 --> 00:26:03,310
Observați că aici dacă tastați curat, atunci ceea ce face este de fapt elimină orice

301
00:26:03,310 --> 00:26:06,340
care este nucleul.

302
00:26:06,340 --> 00:26:09,190
Dacă ai o eroare de segmentare, practic veți obține o groapa de bază.

303
00:26:09,190 --> 00:26:13,260
Deci acest fișier mică și urâtă va apărea în directorul dvs. numit miez.

304
00:26:13,260 --> 00:26:16,310
Veți dori să eliminați că pentru a face curat.

305
00:26:16,310 --> 00:26:20,940
Se elimină toate fișierele exe și. Fișiere o.

306
00:26:27,900 --> 00:26:30,220
>> Să aruncăm o privire în dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Aceasta spune că funcționalitatea declară un dicționar.

308
00:26:34,410 --> 00:26:39,530
Avem o lungime maximă pentru orice cuvânt în dicționar.

309
00:26:39,530 --> 00:26:45,130
Noi spunem că acest lucru va fi cel mai lung cuvânt posibil. Este de lungime 45.

310
00:26:45,130 --> 00:26:48,900
Deci, nu vom avea nici cuvintele pe care depășesc această lungime.

311
00:26:48,900 --> 00:26:50,980
Aici avem doar prototipuri funcționale.

312
00:26:50,980 --> 00:26:55,290
Noi nu avem punerea în aplicare efectivă pentru că este ceea ce vom face pentru acest PSET.

313
00:26:55,290 --> 00:26:59,940
Dar ce face asta este de când am de-a face cu fișiere mai mari aici

314
00:26:59,940 --> 00:27:06,650
și funcționalitatea pe o scară mai largă, e util să aveți un fișier h..

315
00:27:06,650 --> 00:27:11,290
astfel că altcineva a citi sau de a folosi codul poate înțelege ce se întâmplă.

316
00:27:11,290 --> 00:27:17,910
Și poate că vor să pună în aplicare încearcă, dacă ai făcut tabele de dispersie sau invers.

317
00:27:17,910 --> 00:27:21,850
Atunci s-ar spune funcția mea de încărcare,

318
00:27:21,850 --> 00:27:26,950
punerea în aplicare efectivă este de gând să difere, dar acest prototip nu se va schimba.

319
00:27:26,950 --> 00:27:33,280
Aici ne-am verifica, care returnează adevărat dacă un cuvânt dat este în dicționar.

320
00:27:33,280 --> 00:27:39,800
Apoi, avem de încărcare, care, practic, ia într-un fișier dicționar

321
00:27:39,800 --> 00:27:44,360
și apoi se încarcă în unele structuri de date.

322
00:27:44,360 --> 00:27:47,500
Avem dimensiune, care, atunci când numit, returnează dimensiunea dicționarul,

323
00:27:47,500 --> 00:27:50,310
câte cuvinte sunt stocate în ea,

324
00:27:50,310 --> 00:27:54,390
și descărcare, apoi, care eliberează toată memoria pe care este posibil să fi preluat

325
00:27:54,390 --> 00:27:57,900
în timp ce face dicționarul.

326
00:28:01,070 --> 00:28:03,590
>> Să aruncăm o privire la dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Vedem că se pare foarte asemănător cu dictionary.h, cu excepția acum are doar toate aceste Todos în ea.

328
00:28:10,490 --> 00:28:16,980
Și așa că e treaba ta. În cele din urmă, veți fi completarea speller.c cu toate acest cod.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, atunci când alerga, nu este cu adevărat de gând să faci nimic,

330
00:28:21,540 --> 00:28:29,590
asa ne uităm spre speller.c pentru a vedea punerea în aplicare efectivă a verificatorul ortografic.

331
00:28:29,590 --> 00:28:32,060
Chiar dacă nu sunteți de gând să fie editarea oricare din acest cod,

332
00:28:32,060 --> 00:28:38,050
este important să citească, să înțeleagă atunci când este chemat de sarcină, când mă apel cec,

333
00:28:38,050 --> 00:28:42,350
doar pentru a intelege, harta l, a se vedea cum funcționează funcția.

334
00:28:42,350 --> 00:28:49,860
Vedem că este de verificare pentru utilizarea corectă.

335
00:28:49,860 --> 00:28:55,200
În esență, atunci când cineva se execută abecedar, acest lucru indică faptul că este opțională

336
00:28:55,200 --> 00:29:00,950
pentru ei să treacă într-un fișier dicționar pentru că nu va fi un dicționar de fișier implicit.

337
00:29:00,950 --> 00:29:05,410
Și atunci ei trebuie să treacă în text pentru a fi vraja verificate.

338
00:29:05,410 --> 00:29:11,410
Oferte rusage cu timp deoarece o parte a acestui PSET pe care ne vom ocupa de mai târziu

339
00:29:11,410 --> 00:29:14,790
este nu numai obtinerea unei funcționări verificatorul ortografic de lucru

340
00:29:14,790 --> 00:29:17,190
dar de fapt, obtinerea-l să fie rapid.

341
00:29:17,190 --> 00:29:22,040
Și astfel, atunci asta e în cazul în care rusage este de gând să vină inch

342
00:29:22,040 --> 00:29:28,740
Aici, vom vedea primul apel la unul din fișierele noastre dictionary.c, care este sarcina.

343
00:29:28,740 --> 00:29:34,720
Încărcați returneaza true sau false - adevarat la succes, fals la eșec.

344
00:29:34,720 --> 00:29:41,400
Deci, dacă dicționarul nu este încărcată în mod corespunzător, atunci se va întoarce speller.c 1 și demisia.

345
00:29:41,400 --> 00:29:47,920
Dar dacă o face în mod corespunzător de sarcină, apoi se va continua.

346
00:29:47,920 --> 00:29:50,740
Vom continua, și vom vedea un fisier I / O aici,

347
00:29:50,740 --> 00:29:56,210
în cazul în care se va face cu deschiderea fișier text.

348
00:29:56,210 --> 00:30:04,640
Aici, ce face asta este vraja locului, fiecare cuvânt în text.

349
00:30:04,640 --> 00:30:09,270
Deci, ce speller.c face chiar aici este iterarea peste fiecare dintre cuvintele din fișierul text

350
00:30:09,270 --> 00:30:12,790
și apoi le verificare în dicționar.

351
00:30:24,680 --> 00:30:32,350
Aici, avem un Boolean scris gresit, care va vedea dacă cecul returneaza true sau nu.

352
00:30:32,350 --> 00:30:37,110
În cazul în care cuvântul este, de fapt, în dicționar, atunci verificarea se va întoarce adevărat.

353
00:30:37,110 --> 00:30:39,760
Asta înseamnă că cuvântul nu este scris greșit.

354
00:30:39,760 --> 00:30:45,330
Deci, ar fi greșit fals, si de aceea avem acolo bang-ului, indicația.

355
00:30:45,330 --> 00:30:56,320
Vom continua să mergi, și apoi ține evidența de cât de multe cuvinte scrise greșit

356
00:30:56,320 --> 00:30:58,910
există în dosar.

357
00:30:58,910 --> 00:31:03,870
Acesta continuă pe și închide fișierul.

358
00:31:03,870 --> 00:31:09,250
Atunci aici, acesta raportează câte cuvinte ortografiate greșit ai avut.

359
00:31:09,250 --> 00:31:12,680
Se calculează cât de mult timp a luat pentru a încărca dicționarul,

360
00:31:12,680 --> 00:31:15,080
cât de mult timp a luat să-l verifice,

361
00:31:15,080 --> 00:31:18,510
cât de mult timp a luat pentru a calcula dimensiunea,

362
00:31:18,510 --> 00:31:21,260
care, așa cum vom merge mai departe, ar trebui să fie foarte mici,

363
00:31:21,260 --> 00:31:25,390
și apoi cât de mult timp a luat pentru a descărca dicționarul.

364
00:31:25,390 --> 00:31:27,700
Aici deasupra vom vedea apelul pentru a descărca aici.

365
00:31:27,700 --> 00:31:52,690
Dacă vom verifica pentru dimensiune aici,

366
00:31:52,690 --> 00:31:59,050
apoi vom vedea că aici este apelul la dimensiunea care determină mărimea dicționarului.

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

368
00:32:07,100 --> 00:32:10,920
>> Sarcina noastră pentru acest PSET este de a pune în aplicare de sarcină, care se va încărca dicționarul

369
00:32:10,920 --> 00:32:15,480
structura de date - Orice variantă ați alege, fie că este vorba un tabel hash sau un try -

370
00:32:15,480 --> 00:32:18,810
cu cuvinte din dicționarul fișierul.

371
00:32:18,810 --> 00:32:25,290
Apoi, aveți dimensiune, care va returna numărul de cuvinte în dicționar.

372
00:32:25,290 --> 00:32:29,860
Și dacă ai pune în aplicare de încărcare într-un mod inteligent, apoi dimensiunea ar trebui sa fie destul de usor.

373
00:32:29,860 --> 00:32:33,860
Atunci ai verifica, care va verifica dacă un anumit cuvânt este în dicționar.

374
00:32:33,860 --> 00:32:38,690
Deci, speller.c trece într-un șir, iar apoi va trebui să verificați dacă această șir

375
00:32:38,690 --> 00:32:41,610
este conținută în dicționarul.

376
00:32:41,610 --> 00:32:46,750
Observați că avem, în general, dicționare standard,

377
00:32:46,750 --> 00:32:53,020
dar în acest PSET, practic orice dicționarul trecut în în orice limbă.

378
00:32:53,020 --> 00:32:57,040
Deci, nu putem presupune doar că cuvântul este în interiorul.

379
00:32:57,040 --> 00:33:03,090
Foobar Cuvântul ar putea fi definită într-un dicționar sigur că vom trece inch

380
00:33:03,090 --> 00:33:07,920
Și atunci ne-am descarce, care eliberează dicționarul din memorie.

381
00:33:07,920 --> 00:33:11,930
>> În primul rând, aș vrea să merg pe metoda de tabel hash

382
00:33:11,930 --> 00:33:14,630
despre cum putem să pună în aplicare toate aceste patru funcții,

383
00:33:14,630 --> 00:33:18,650
si apoi voi trece peste încearcă metoda, cum putem pune în aplicare aceste patru funcții,

384
00:33:18,650 --> 00:33:22,720
iar la sfârșitul vorbesc despre unele sfaturi generale atunci când faci PSET

385
00:33:22,720 --> 00:33:27,870
și, de asemenea, modul în care s-ar putea fi capabil de a utiliza Valgrind pentru a verifica dacă există scurgeri de memorie.

386
00:33:27,870 --> 00:33:30,550
>> Să intrăm în metoda de tabel hash.

387
00:33:30,550 --> 00:33:35,910
Un tabel hash constă dintr-o listă de galeti.

388
00:33:35,910 --> 00:33:43,010
Fiecare valoare, fiecare cuvânt, este de gând să meargă într-una din aceste galeti.

389
00:33:43,010 --> 00:33:53,200
Un tabel hash ideal uniform distribuie toate aceste valori pe care îl trece în

390
00:33:53,200 --> 00:33:57,160
și apoi le populează în găleată, astfel încât fiecare cupă pentru excavat

391
00:33:57,160 --> 00:34:02,000
are aproximativ un număr egal de valori în ea.

392
00:34:02,000 --> 00:34:09,630
Structura pentru un tabel hash, avem o serie de liste legate.

393
00:34:09,630 --> 00:34:17,900
Ceea ce facem este atunci când vom trece într-o valoare, vom verifica în cazul în care valoarea ar trebui să aparțină,

394
00:34:17,900 --> 00:34:23,840
care cupă îi aparține, și apoi puneți-l în lista de legat asociat cu acea cupă.

395
00:34:23,840 --> 00:34:28,199
Aici, ceea ce am este o funcție hash.

396
00:34:28,199 --> 00:34:31,320
E un tabel hash int.

397
00:34:31,320 --> 00:34:38,540
Deci, pentru prima găleată, orice numere naturale mai mici de 10 intra in primul compartiment.

398
00:34:38,540 --> 00:34:42,190
Orice întregi de peste 10, dar sub 20 Du-te în altă parte,

399
00:34:42,190 --> 00:34:44,179
și apoi așa mai departe și așa mai departe.

400
00:34:44,179 --> 00:34:52,370
Pentru mine, fiecare compartiment reprezintă aceste numere.

401
00:34:52,370 --> 00:34:59,850
Cu toate acestea, spun că am fost să treacă în 50, de exemplu.

402
00:34:59,850 --> 00:35:07,490
Se pare ca în cazul în primele trei conțin o serie de zece numere.

403
00:35:07,490 --> 00:35:12,570
Dar eu vreau să permită masa mea hash pentru a lua în orice fel de numere întregi,

404
00:35:12,570 --> 00:35:19,860
da, atunci mi-ar fi de a filtra toate numerele de peste 30 în ultimul compartiment.

405
00:35:19,860 --> 00:35:26,660
Și așa, atunci care ar duce la un fel de tabel hash dezechilibrat.

406
00:35:31,330 --> 00:35:35,640
Pentru a reitera, un tabel hash este doar o serie de cupe

407
00:35:35,640 --> 00:35:38,590
în cazul în care fiecare cupă este o listă legat.

408
00:35:38,590 --> 00:35:43,730
Și astfel pentru a determina în cazul în care fiecare valoare se duce, care merge în cupă,

409
00:35:43,730 --> 00:35:46,260
ai de gând să doriți ceea ce se numește o funcție hash

410
00:35:46,260 --> 00:35:55,010
care ia o valoare și apoi spune această valoare corespunde unei anumite găleată.

411
00:35:55,010 --> 00:36:00,970
Deci, sus, în acest exemplu, funcția mea de distribuire a luat fiecare valoare.

412
00:36:00,970 --> 00:36:03,020
Se verifică dacă aceasta a fost mai mic de 10.

413
00:36:03,020 --> 00:36:05,360
Dacă ar fi fost, l-ar pune în găleată primul.

414
00:36:05,360 --> 00:36:08,910
Se verifică dacă este mai mic de 20, pune-l în două dacă este adevărat,

415
00:36:08,910 --> 00:36:12,880
verifică dacă acesta e mai mic de 30, iar apoi pune în găleată treia,

416
00:36:12,880 --> 00:36:16,990
și apoi toate celelalte doar cade la găleată patra.

417
00:36:16,990 --> 00:36:20,110
Deci, ori de câte ori aveți o valoare, dvs hash funcție

418
00:36:20,110 --> 00:36:25,420
va plasa ca valoarea în găleată corespunzătoare.

419
00:36:25,420 --> 00:36:32,430
Funcția hash practic trebuie să știe cât de multe galeti aveți.

420
00:36:32,430 --> 00:36:37,960
Dimensiunea tabel hash, numărul de compartimente care le aveți,

421
00:36:37,960 --> 00:36:41,190
care va fi un număr fix, care este de până la tine, pentru tine de a decide,

422
00:36:41,190 --> 00:36:43,590
dar o să fie un număr fix.

423
00:36:43,590 --> 00:36:51,840
Deci, funcția de distribuire va fi bazându-se pe faptul că pentru a determina care cupă pentru excavat fiecare tasta merge în

424
00:36:51,840 --> 00:36:54,450
astfel că este uniform distribuită.

425
00:36:56,150 --> 00:37:03,820
Similar cu punerea în aplicare a listelor noastre legate, acum fiecare nod în tabel hash

426
00:37:03,820 --> 00:37:07,000
este, de fapt de gând să aibă un caracter de tip.

427
00:37:07,000 --> 00:37:14,340
Deci, avem un tablou char numit cuvant si apoi un alt pointer la nodul următor,

428
00:37:14,340 --> 00:37:19,010
care are sens, pentru că va fi o listă legată.

429
00:37:19,010 --> 00:37:24,350
Amintiți-vă atunci când ne-am legat de preturi, am facut un nod * cap numit

430
00:37:24,350 --> 00:37:31,060
care a fost îndreptat la primul nod din listă legată.

431
00:37:31,060 --> 00:37:34,020
Dar pentru masa noastră hash, pentru că avem mai multe liste legate,

432
00:37:34,020 --> 00:37:37,520
ceea ce ne dorim este vrem masa noastră de distribuire a fi ca, "Ce este o galeata?"

433
00:37:37,520 --> 00:37:43,340
O galeata este doar o lista de pointeri nod,

434
00:37:43,340 --> 00:37:50,620
și astfel fiecare element în găleată este, de fapt indică sale listă corespunzătoare legate.

435
00:37:56,180 --> 00:38:01,520
Pentru a reveni la acest schematică, veți vedea că ei înșiși sunt gălețile de săgeți,

436
00:38:01,520 --> 00:38:06,980
nu noduri reale.

437
00:38:11,680 --> 00:38:16,420
O proprietate esențială a funcțiilor hash este că acestea sunt deterministe.

438
00:38:16,420 --> 00:38:19,440
Asta înseamnă că ori de câte ori ați hash numărul 2,

439
00:38:19,440 --> 00:38:22,270
ar trebui să revină întotdeauna aceeași găleată.

440
00:38:22,270 --> 00:38:26,440
Fiecare valoare unică, care merge în funcția de hash, dacă se repetă,

441
00:38:26,440 --> 00:38:29,690
are pentru a obține același indice.

442
00:38:29,690 --> 00:38:34,210
Deci, funcția hash returnează indicele de matrice

443
00:38:34,210 --> 00:38:38,530
în cazul în care valoarea aparține.

444
00:38:38,530 --> 00:38:41,790
Așa cum am menționat mai înainte, numărul de compartimente este fix,

445
00:38:41,790 --> 00:38:49,630
și astfel indexul dumneavoastră că vă veți întoarce trebuie să fie mai mică decât numărul de compartimente

446
00:38:49,630 --> 00:38:52,680
dar mai mare decât 0.

447
00:38:52,680 --> 00:39:00,780
Motivul pentru care am avea funcții de dispersie în loc de doar una singură listă legată

448
00:39:00,780 --> 00:39:09,290
sau unul singur array este că ne dorim să fie în măsură pentru a sări la o anumită secțiune cel mai usor

449
00:39:09,290 --> 00:39:11,720
dacă știm caracteristică a unei valori -

450
00:39:11,720 --> 00:39:14,760
în loc de a căuta prin dicționarul întregului,

451
00:39:14,760 --> 00:39:18,320
fiind capabil pentru a sări la o anumită secțiune a acestuia.

452
00:39:19,880 --> 00:39:24,440
Funcția hash ar trebui să țină cont de faptul că în mod ideal,

453
00:39:24,440 --> 00:39:28,980
fiecare compartiment are aproximativ același număr de taste.

454
00:39:28,980 --> 00:39:35,040
Deoarece tabel hash este o serie de liste legate,

455
00:39:35,040 --> 00:39:38,480
apoi listele legate de sine sunt de gând să aibă mai mult de un nod.

456
00:39:38,480 --> 00:39:43,210
În exemplul anterior, două numere de telefon diferite, chiar dacă acestea nu au fost egale,

457
00:39:43,210 --> 00:39:46,950
atunci când trunchiată, se va întoarce același indice.

458
00:39:46,950 --> 00:39:53,620
Deci, atunci când se face cu cuvinte, un cuvânt atunci când trunchiată

459
00:39:53,620 --> 00:39:57,450
ar fi aceeași valoare hash ca un alt cuvânt.

460
00:39:57,450 --> 00:40:04,140
Asta e ceea ce noi numim o coliziune, atunci când avem un nod care, atunci când trunchiată,

461
00:40:04,140 --> 00:40:09,610
lista legat la acea cupă nu este gol.

462
00:40:09,610 --> 00:40:14,180
Tehnica pe care o numim există liniară sondare,

463
00:40:14,180 --> 00:40:22,550
în cazul în care te duci în lista de legat și apoi găsiți în cazul în care doriți să inserați acel nod

464
00:40:22,550 --> 00:40:25,520
pentru că aveți o coliziune.

465
00:40:25,520 --> 00:40:28,070
Puteți vedea că ar putea exista un compromis aici, nu?

466
00:40:28,070 --> 00:40:33,760
Dacă aveți un tabel hash foarte mic, un număr foarte mic de compartimente,

467
00:40:33,760 --> 00:40:36,380
atunci ai de gând să aibă o mulțime de coliziuni.

468
00:40:36,380 --> 00:40:40,460
Dar apoi, dacă faci o masă foarte mare hash,

469
00:40:40,460 --> 00:40:44,110
esti, probabil, de gând să minimizeze coliziunile,

470
00:40:44,110 --> 00:40:47,170
dar o să fie o foarte mare structură de date.

471
00:40:47,170 --> 00:40:49,310
Acolo va fi compromisuri cu asta.

472
00:40:49,310 --> 00:40:51,310
Așa că atunci când faci PSET dumneavoastră, încercați să joace în jurul valorii de

473
00:40:51,310 --> 00:40:54,210
între a face un tabel poate mai mic hash

474
00:40:54,210 --> 00:41:02,100
dar apoi știind că aceasta va dura un pic mai mult pentru a traversa diferitele elemente

475
00:41:02,100 --> 00:41:04,270
din aceste liste legate.

476
00:41:04,270 --> 00:41:09,500
>> Ceea ce sarcina este de gând să faceți este să itera peste fiecare cuvânt în dicționar.

477
00:41:09,500 --> 00:41:13,180
Ea trece într-un pointer la fișierul dicționar.

478
00:41:13,180 --> 00:41:18,050
Deci, ai de gând să profite de fișier I / O, functii pe care le stăpânesc, în pset4

479
00:41:18,050 --> 00:41:23,010
si repeta peste fiecare cuvânt în dicționar.

480
00:41:23,010 --> 00:41:26,620
Vrei fiecare cuvânt în dicționar pentru a deveni un nod nou,

481
00:41:26,620 --> 00:41:32,730
și ai de gând să plaseze fiecare dintre aceste noduri in interiorul tau dicționarul structură de date.

482
00:41:32,730 --> 00:41:36,560
Ori de câte ori veți obține un cuvânt nou, știi că o să devină un nod.

483
00:41:36,560 --> 00:41:46,590
Deci, poti sa te duci imediat și malloc un pointer nod pentru fiecare cuvânt nou pe care aveți.

484
00:41:46,590 --> 00:41:52,610
Aici am sunat new_node mea indicatorul nod și eu mallocing ce? Dimensiunea unui nod.

485
00:41:52,610 --> 00:41:59,190
Apoi, pentru a citi șir real dintr-un fișier, pentru că dicționarul este, de fapt stocate

486
00:41:59,190 --> 00:42:03,340
printr-un cuvânt și apoi o linie nouă, ceea ce putem profita de

487
00:42:03,340 --> 00:42:06,520
este funcția fscanf,

488
00:42:06,520 --> 00:42:10,280
care fisier este fișierul dicționarul că suntem în trecut,

489
00:42:10,280 --> 00:42:18,900
așa că scanează fișierul pentru un șir și locuri care șir în ultimul argument.

490
00:42:18,900 --> 00:42:26,890
Dacă vă reamintesc din nou la una din prelegerile, atunci când ne-am dus peste

491
00:42:26,890 --> 00:42:29,320
și tipul de cojit straturilor înapoi pe biblioteca CS50,

492
00:42:29,320 --> 00:42:33,430
am văzut o punere în aplicare a fscanf acolo.

493
00:42:33,430 --> 00:42:37,700
Pentru a reveni la fscanf, avem fișierul care ne citesc din,

494
00:42:37,700 --> 00:42:42,570
suntem în căutarea pentru un șir de caractere în acel fișier, iar apoi ne-l plasarea în

495
00:42:42,570 --> 00:42:48,340
aici am new_node-> cuvânt, deoarece new_node este un pointer nod,

496
00:42:48,340 --> 00:42:50,380
Nu o reală nod.

497
00:42:50,380 --> 00:42:57,100
Deci, atunci eu spun new_node, vreau să merg la nodul care este îndreptat spre

498
00:42:57,100 --> 00:43:01,190
apoi atribuiți acea valoare la cuvânt.

499
00:43:01,190 --> 00:43:08,540
Dorim să ia apoi acest cuvânt și introduceți-l în tabel hash.

500
00:43:08,540 --> 00:43:13,750
Dau seama că am făcut new_node un pointer nod

501
00:43:13,750 --> 00:43:18,230
pentru că am de gând să vreau să știu ce adresa de acel nod este

502
00:43:18,230 --> 00:43:23,940
atunci când l-am introduce în cauza structura a nodurilor în sine, de struct,

503
00:43:23,940 --> 00:43:26,380
este faptul că acestea au un pointer la un nod nou.

504
00:43:26,380 --> 00:43:30,820
Deci, atunci ce e adresa pe care nod de gând să indice?

505
00:43:30,820 --> 00:43:34,550
Această adresă va fi new_node.

506
00:43:34,550 --> 00:43:42,140
Asta face sens, de ce facem new_node un nod *, spre deosebire de un nod?

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

508
00:43:45,700 --> 00:43:52,840
Avem un cuvânt. Această valoare este new_node-> cuvânt.

509
00:43:52,840 --> 00:43:55,970
Care conține cuvântul din dicționar care ne-o dorim la intrare.

510
00:43:55,970 --> 00:44:00,210
Deci, ceea ce dorim să facem este să vrem numim funcția noastră de distribuire pe care șir

511
00:44:00,210 --> 00:44:03,780
deoarece funcția de distribuire noastră are într-un șir și apoi returnează un întreg ne,

512
00:44:03,780 --> 00:44:12,090
în cazul în care este întreg în cazul în care indicele hashtable la care indicele reprezintă acea cupă.

513
00:44:12,090 --> 00:44:18,260
Dorim să indice faptul că și apoi du-te la faptul că indicele de tabel hash

514
00:44:18,260 --> 00:44:26,960
și de a folosi apoi că lista legat pentru a insera nodul de la new_node.

515
00:44:26,960 --> 00:44:31,950
Amintiți-vă că toate acestea vă decideți să inserați nodul dumneavoastră,

516
00:44:31,950 --> 00:44:34,370
dacă e în mijloc, dacă doriți să-l sortați

517
00:44:34,370 --> 00:44:39,650
sau la începutul sau la sfârșitul, asigurați-vă doar că nod ultima ta întotdeauna arată la NULL

518
00:44:39,650 --> 00:44:46,730
pentru că e singurul mod în care știm unde ultimul element al listei noastre legate este.

519
00:44:50,790 --> 00:44:59,710
>> Dacă dimensiunea este un număr întreg care reprezintă numărul de cuvinte într-un dicționar,

520
00:44:59,710 --> 00:45:03,060
apoi o modalitate de a face acest lucru este faptul că ori de câte ori este chemat dimensiune

521
00:45:03,060 --> 00:45:05,840
trecem prin fiecare element în tabelul nostru de dispersie

522
00:45:05,840 --> 00:45:09,410
si apoi repeta prin fiecare listă legată în tabel hash

523
00:45:09,410 --> 00:45:13,770
și se calculează apoi lungimea de faptul că, creșterea noastră contra 1 cu 1.

524
00:45:13,770 --> 00:45:16,580
Dar de fiecare dată că mărimea este numit, care este de gând să ia o lungă perioadă de timp

525
00:45:16,580 --> 00:45:22,120
pentru că am de gând să fie liniar probeze fiecare listă unică legată.

526
00:45:22,120 --> 00:45:30,530
În schimb, acesta va fi mult mai ușor dacă țineți evidența cât de multe cuvinte sunt transmise inch

527
00:45:30,530 --> 00:45:36,330
Deci dacă includeți un contor în funcție de încărcare dvs.

528
00:45:36,330 --> 00:45:42,430
că actualizările este necesar, apoi contra, dacă l-ați setat la o variabilă globală,

529
00:45:42,430 --> 00:45:44,930
vor putea fi accesate de dimensiunea.

530
00:45:44,930 --> 00:45:51,450
Deci, ce dimensiune ar putea face pur și simplu se află în o singură linie, întoarce doar valoarea contorului,

531
00:45:51,450 --> 00:45:55,500
dimensiunea dicționarului, care deja tratate în sarcină.

532
00:45:55,500 --> 00:46:05,190
Asta e ceea ce am vrut să spun când am spus că, dacă punerea în aplicare a sarcinii într-un mod util,

533
00:46:05,190 --> 00:46:08,540
apoi dimensiunea va fi destul de ușor.

534
00:46:08,540 --> 00:46:11,350
>> Deci, acum ajungem să verifice.

535
00:46:11,350 --> 00:46:15,960
Acum avem de-a face cu cuvinte din fișierul text de intrare,

536
00:46:15,960 --> 00:46:19,910
și astfel vom fi verifica dacă toate aceste cuvinte de intrare

537
00:46:19,910 --> 00:46:22,520
sunt de fapt în dicționarul sau nu.

538
00:46:22,520 --> 00:46:26,520
Similar cu Scramble, dorim pentru a permite insensibilitate caz.

539
00:46:26,520 --> 00:46:32,110
Doriți să vă asigurați că toate cuvintele au trecut în, chiar dacă ele sunt regim mixt,

540
00:46:32,110 --> 00:46:37,840
când este apelat cu șir de comparare, sunt echivalente.

541
00:46:37,840 --> 00:46:42,450
Cuvintele din dicționar fișiere text sunt de fapt toate cu litere mici.

542
00:46:42,450 --> 00:46:49,280
Un alt lucru este că puteți presupune că fiecare cuvânt din trecut, fiecare șir,

543
00:46:49,280 --> 00:46:53,200
este de gând să fie alfabetică sau conțin apostrofuri.

544
00:46:53,200 --> 00:46:58,010
Apostroful vor fi valabile în cuvinte dicționarul nostru.

545
00:46:58,010 --> 00:47:06,470
Deci, dacă aveți un cuvânt cu apostrof S, care este un cuvânt real legitim în dicționarul

546
00:47:06,470 --> 00:47:11,650
care va fi unul dintre nodurile din tabel hash.

547
00:47:13,470 --> 00:47:18,350
Verificați dacă funcționează cu cuvântul există, atunci trebuie sa fie in masa noastră hash.

548
00:47:18,350 --> 00:47:22,210
În cazul în care cuvântul este în dicționar, atunci toate cuvintele din dicționar sunt în tabelul hash,

549
00:47:22,210 --> 00:47:26,560
așa că hai să ne uităm pentru acest cuvânt în tabel hash.

550
00:47:26,560 --> 00:47:29,250
Noi știm că de când am implementat functia noastra de distribuire

551
00:47:29,250 --> 00:47:38,420
astfel încât fiecare cuvânt unic este întotdeauna trunchiată la aceeași valoare,

552
00:47:38,420 --> 00:47:43,340
atunci știm că, în loc de a căuta prin intermediul nostru intreaga întregul tabel hash,

553
00:47:43,340 --> 00:47:48,310
putem găsi de fapt, lista legată că acest cuvânt ar trebui să aparțină.

554
00:47:48,310 --> 00:47:51,850
Dacă ar fi fost în dicționar, atunci acesta ar fi în acea găleată.

555
00:47:51,850 --> 00:47:57,140
Ce putem face, în cazul în care cuvântul este numele nostru a trecut în șir,

556
00:47:57,140 --> 00:48:01,560
putem doar hash acest cuvânt și gasiti lista de legat

557
00:48:01,560 --> 00:48:06,410
la valoarea de Hashtable [hash (cuvânt)].

558
00:48:06,410 --> 00:48:12,410
De acolo, ceea ce putem face este, avem un subset mic de noduri pentru a căuta acest cuvânt,

559
00:48:12,410 --> 00:48:16,770
și astfel încât să putem traversa lista de legat, folosind un exemplu din mai devreme în walkthrough,

560
00:48:16,770 --> 00:48:24,110
și apoi apel șir compara pe cuvântul ori de câte ori este cursorul indică spre,

561
00:48:24,110 --> 00:48:28,430
acest cuvânt, și a vedea dacă cele comparare.

562
00:48:30,280 --> 00:48:35,110
În funcție de modul în care vă organizați funcția hash,

563
00:48:35,110 --> 00:48:39,260
în cazul în care este sortat, ați putea fi în măsură să se întoarcă fals un pic mai devreme,

564
00:48:39,260 --> 00:48:43,440
dar dacă e nesortate, apoi doriți să continuați traversarea prin lista dvs. de legat

565
00:48:43,440 --> 00:48:46,480
până când găsiți ultimul element al listei.

566
00:48:46,480 --> 00:48:53,320
Și dacă încă nu ați găsit cuvântul de timp ați ajuns la sfârșitul listei legate,

567
00:48:53,320 --> 00:48:56,890
ceea ce înseamnă că cuvântul tău nu există în dicționar,

568
00:48:56,890 --> 00:48:59,410
și astfel încât cuvântul este nevalid,

569
00:48:59,410 --> 00:49:02,730
și verificare ar trebui să returneze fals.

570
00:49:02,730 --> 00:49:09,530
>> Acum am ajuns la descărcarea, în cazul în care vrem să eliberăm toate nodurile pe care le-am malloc'd,

571
00:49:09,530 --> 00:49:14,050
atât de liber toate nodurile din interiorul masa noastră hash.

572
00:49:14,050 --> 00:49:20,270
Am de gând să doriți să itera peste toate listele legate și libere toate nodurile din asta.

573
00:49:20,270 --> 00:49:29,350
Daca te uiti mai sus, în pas cu pas pentru exemplul care ne eliberăm o listă legat,

574
00:49:29,350 --> 00:49:35,140
atunci veți dori să repetați acest proces pentru fiecare element în tabelul hash.

575
00:49:35,140 --> 00:49:37,780
Și eu voi trece peste acest spre sfârșitul walkthrough,

576
00:49:37,780 --> 00:49:46,600
dar Valgrind este un instrument în cazul în care puteți vedea dacă ați eliberat în mod corespunzător

577
00:49:46,600 --> 00:49:53,600
fiecare nod pe care le-ați malloc'd sau orice altceva pe care le-ați malloc'd, orice alt indicator.

578
00:49:55,140 --> 00:50:00,530
Deci asta e tabele de dispersie, în cazul în care avem un număr finit de compartimente

579
00:50:00,530 --> 00:50:09,220
și o funcție hash care va avea o valoare și apoi atribui acea valoare într-o găleată anume.

580
00:50:09,220 --> 00:50:13,340
>> Acum am ajuns la incercari.

581
00:50:13,340 --> 00:50:18,750
Incearca un fel de look asa, si eu voi trage de asemenea un exemplu.

582
00:50:18,750 --> 00:50:25,630
Practic, aveți o gamă întreagă de scrisori potențiali,

583
00:50:25,630 --> 00:50:29,210
și apoi ori de câte ori sunteți construirea unui cuvânt,

584
00:50:29,210 --> 00:50:36,490
această scrisoare poate fi legat de un dicționar pentru o gamă largă de posibilități.

585
00:50:36,490 --> 00:50:40,840
Câteva cuvinte încep cu C, dar apoi continua cu A,

586
00:50:40,840 --> 00:50:42,960
dar altele continua cu O, de exemplu.

587
00:50:42,960 --> 00:50:51,090
Un trie este un mod de vizualizare toate combinațiile posibile ale acestor cuvinte.

588
00:50:51,090 --> 00:50:59,070
Un trie este de gând să țină evidența succesiune de litere, care cuprind cuvinte,

589
00:50:59,070 --> 00:51:08,280
ramificatie atunci când este necesar, atunci când o singură literă poate fi urmat de un multiplu de scrisori,

590
00:51:08,280 --> 00:51:16,630
și la sfârșitul indica la fiecare punct, dacă acel cuvânt este valabil sau nu

591
00:51:16,630 --> 00:51:30,120
pentru că dacă sunteți de ortografie cuvântul MAT, MA nu cred că este un cuvânt valid, dar este MAT.

592
00:51:30,120 --> 00:51:37,820
Și astfel, în trie dvs., ar indica faptul că, după MAT, că e de fapt un cuvânt valabil.

593
00:51:41,790 --> 00:51:48,590
Fiecare nod în trie nostru este, de fapt de gând să conțină o serie de indicii nod,

594
00:51:48,590 --> 00:51:52,970
și am de gând să aibă, în mod special, 27 din aceste indicii nod,

595
00:51:52,970 --> 00:52:00,550
unul pentru fiecare literă din alfabet, precum și caracterul apostrof.

596
00:52:00,550 --> 00:52:10,450
Fiecare element din matrice, care este ea însăși va pentru a indica un alt nod.

597
00:52:10,450 --> 00:52:14,020
Deci, în cazul în care nodul este NULL, dacă nu există nimic după aceea,

598
00:52:14,020 --> 00:52:20,550
atunci știm că nu e nici o scrisoare în continuare în această secvență cuvânt.

599
00:52:20,550 --> 00:52:26,950
Dar, în cazul în care nodul nu este NULL, ceea ce înseamnă că există mai multe scrisori în care secvența de scrisoare.

600
00:52:26,950 --> 00:52:32,160
Și apoi în plus, fiecare nod indică dacă este ultimul caracter al unui cuvânt sau nu.

601
00:52:38,110 --> 00:52:43,170
>> Să mergem într-un exemplu de trie.

602
00:52:50,500 --> 00:52:58,340
În primul rând am camera de 27 de noduri în această matrice.

603
00:52:58,340 --> 00:53:03,200
Dacă am BAR cuvântul -

604
00:53:13,310 --> 00:53:15,370
Dacă am BAR cuvântul și vreau să inserați că, în,

605
00:53:15,370 --> 00:53:22,700
prima scrisoare este B, deci, dacă trie meu este gol,

606
00:53:22,700 --> 00:53:29,910
B este a doua literă a alfabetului, așa că am de gând să aleagă pentru a pune asta aici, la acest indice.

607
00:53:29,910 --> 00:53:33,450
Am de gând să aibă B aici.

608
00:53:33,450 --> 00:53:42,400
B va fi un nod care indică un alt tablou al tuturor caracterelor posibile

609
00:53:42,400 --> 00:53:45,870
care poate urma după litera B.

610
00:53:45,870 --> 00:53:57,610
În acest caz, am de-a face cu BAR cuvântul, deci A va merge aici.

611
00:54:02,000 --> 00:54:08,990
După o, am litera R, astfel încât atunci A punctele acum la combinația proprie,

612
00:54:08,990 --> 00:54:15,120
și apoi R va fi aici.

613
00:54:15,120 --> 00:54:22,470
Bar este un cuvânt complet, deci atunci am de gând să aibă R punct la un alt nod

614
00:54:22,470 --> 00:54:33,990
care spune că acest cuvânt este valabil.

615
00:54:36,010 --> 00:54:40,970
Această nod este, de asemenea, va avea o serie de noduri,

616
00:54:40,970 --> 00:54:45,260
dar ar putea fi cele NULL.

617
00:54:45,260 --> 00:54:49,080
Dar în esență, se poate continua așa.

618
00:54:49,080 --> 00:54:54,250
Care va deveni un pic mai clar atunci când vom merge la un alt exemplu,

619
00:54:54,250 --> 00:54:56,780
astfel încât să poarte cu mine acolo.

620
00:54:56,780 --> 00:55:02,050
Acum avem BAR interiorul dicționarul nostru.

621
00:55:02,050 --> 00:55:05,980
Acum spune ca avem BAZ cuvântul.

622
00:55:05,980 --> 00:55:12,630
Vom începe cu B, și avem deja B, ca fiind unul dintre cele scrisori pe care e în dicționarul nostru.

623
00:55:12,630 --> 00:55:15,170
Asta a urmat cu A. Avem o deja.

624
00:55:15,170 --> 00:55:19,250
Dar apoi în schimb, avem Z text.

625
00:55:19,250 --> 00:55:25,490
Deci, atunci un element în gama noastră va fi Z,

626
00:55:25,490 --> 00:55:30,810
și așa mai apoi că unul este de gând să indice către un alt valabilă a cuvântului.

627
00:55:30,810 --> 00:55:36,930
Deci, vom vedea că, atunci când vom continua prin B și apoi A,

628
00:55:36,930 --> 00:55:43,480
există două opțiuni diferite în prezent în dicționarul nostru pentru cuvinte care încep cu B și A.

629
00:55:49,650 --> 00:55:57,460
Spune-am dorit pentru a introduce cuvântul foobar.

630
00:55:57,460 --> 00:56:05,620
Apoi, ne-ar face o intrare la F.

631
00:56:05,620 --> 00:56:11,320
F este un nod care indică o gamă întreagă.

632
00:56:11,320 --> 00:56:22,790
Ne-ar găsi O, du-te la O, O apoi link-uri într-o listă întreagă.

633
00:56:22,790 --> 00:56:35,340
Am avea B și apoi să continue, vom avea A și apoi R.

634
00:56:35,340 --> 00:56:43,570
Deci, atunci traverseaza foobar tot drumul în jos până când foobar este un cuvânt corect.

635
00:56:43,570 --> 00:56:52,590
Și așa, atunci acest lucru ar fi un cuvânt validă.

636
00:56:52,590 --> 00:57:00,170
Acum spune cuvântul nostru următor în dicționarul este de fapt cuvântul FOO.

637
00:57:00,170 --> 00:57:03,530
Ne-ar spune F. Ceea ce urmează F?

638
00:57:03,530 --> 00:57:06,190
De fapt am deja un spațiu pentru O, așa că am de gând să continue.

639
00:57:06,190 --> 00:57:09,150
Nu am nevoie pentru a face unul nou. Continuare.

640
00:57:09,150 --> 00:57:15,500
FOO este un cuvânt valabil în acest dicționar, așa că atunci am de gând să indice

641
00:57:15,500 --> 00:57:21,660
că este validă.

642
00:57:21,660 --> 00:57:28,370
Dacă mă opresc secvența mea acolo, care ar fi corect.

643
00:57:28,370 --> 00:57:33,050
Dar dacă ne-am continuat secvența noastră de la FOO în jos la B

644
00:57:33,050 --> 00:57:39,750
și a avut doar FOOB, FOOB nu este un cuvânt, și că nu este indicat ca unul valid.

645
00:57:47,370 --> 00:57:57,600
Într-un trie, ai fiecare nod indicând dacă este un cuvânt valid sau nu,

646
00:57:57,600 --> 00:58:05,840
și apoi la fiecare nod are, de asemenea, o serie de 27 de noduri pointeri

647
00:58:05,840 --> 00:58:09,520
care apoi indicați spre nodurile ei înșiși.

648
00:58:09,520 --> 00:58:12,940
>> Aici este o modalitate de modul în care ați putea dori să definiți asta.

649
00:58:12,940 --> 00:58:17,260
Cu toate acestea, la fel ca în exemplul de tabel hash, unde am avut un cap * nod

650
00:58:17,260 --> 00:58:21,320
pentru a indica începutul lista noastră legată, de asemenea, suntem de gând să doriți

651
00:58:21,320 --> 00:58:29,150
un mod de a ști unde începutul trie nostru este.

652
00:58:29,150 --> 00:58:34,110
Unii oameni încearcă apel copaci, și că, în cazul în care este rădăcina vine de la.

653
00:58:34,110 --> 00:58:36,910
Deci, vrem rădăcina arborelui nostru pentru a ne asigura că rămâne la pământ

654
00:58:36,910 --> 00:58:39,570
către orice destinație trie nostru este.

655
00:58:42,910 --> 00:58:46,300
Am deja un fel de trecut peste

656
00:58:46,300 --> 00:58:50,240
modul în care ar putea gândi despre încărcarea fiecare cuvânt în dicționar.

657
00:58:50,240 --> 00:58:54,540
În esență, pentru fiecare cuvânt ai de gând să doriți să itera prin trie dvs.

658
00:58:54,540 --> 00:58:59,590
și știind că fiecare element din copiii - am numit-o copiii în acest caz -

659
00:58:59,590 --> 00:59:04,290
corespunde o literă diferită, ai de gând să doriți să verificați aceste valori

660
00:59:04,290 --> 00:59:08,320
la faptul că indicele special, care corespunde literei.

661
00:59:08,320 --> 00:59:11,260
Deci gândesc tot drumul înapoi la Cezar și Vigenere,

662
00:59:11,260 --> 00:59:16,070
știind că fiecare literă poți fel de hartă înapoi la un index alfabetic,

663
00:59:16,070 --> 00:59:20,690
cu siguranta de la A la Z va fi destul de ușor pentru a mapa o scrisoare alfabetică,

664
00:59:20,690 --> 00:59:25,200
dar, din păcate, apostroful, de asemenea, un caracter acceptat în cuvinte.

665
00:59:25,200 --> 00:59:31,650
Nici măcar nu sunt sigur ce valoarea ASCII este,

666
00:59:31,650 --> 00:59:39,250
astfel pentru că, dacă doriți să găsiți un index pentru a decide dacă doriți să fie primul

667
00:59:39,250 --> 00:59:44,550
sau ultima, veți avea de a face o verificare greu codificate pentru că

668
00:59:44,550 --> 00:59:48,930
și a pus apoi că în indexul 26, de exemplu.

669
00:59:48,930 --> 00:59:55,300
Deci, atunci se verifica valoarea la copii [i]

670
00:59:55,300 --> 00:59:58,400
în cazul în care [i] corespunde la orice scrisoare ești.

671
00:59:58,400 --> 01:00:04,110
Dacă e NULL, ceea ce înseamnă că nu există în prezent nici o scrisoare posibile

672
01:00:04,110 --> 01:00:08,150
decurge din faptul că secvența anterioară, astfel încât ai de gând să doriți să malloc

673
01:00:08,150 --> 01:00:13,150
și să facă un nod nou și să aibă copii ca [i] punctul să-l

674
01:00:13,150 --> 01:00:17,890
astfel încât să creați - atunci când am introdus-o scrisoare în dreptunghi -

675
01:00:17,890 --> 01:00:23,680
a face copii non-NULL și cu punctul în care nod nou.

676
01:00:23,680 --> 01:00:28,340
Dar în cazul în care nu este NULL, ca și în cazul nostru de FOO

677
01:00:28,340 --> 01:00:34,570
când am avut deja foobar, vom continua,

678
01:00:34,570 --> 01:00:44,010
iar noi nu facem niciodata un nod nou, ci mai degrabă doar setarea pe true is_word

679
01:00:44,010 --> 01:00:47,790
la sfârșitul acestui cuvânt.

680
01:00:50,060 --> 01:00:55,340
>> Deci la fel ca înainte, pentru că aici ai de a face cu fiecare literă la un moment dat,

681
01:00:55,340 --> 01:01:01,470
că va fi mai ușor pentru tine pentru a dimensiune, in loc de a avea pentru a calcula

682
01:01:01,470 --> 01:01:06,910
și du-te prin copac întreg și calculeze câți copii am eu

683
01:01:06,910 --> 01:01:10,850
și apoi ramificațiile, amintindu-și cum mulți sunt pe partea stângă și pe partea dreaptă

684
01:01:10,850 --> 01:01:12,850
și lucruri de genul asta, o să fie mult mai ușor pentru tine

685
01:01:12,850 --> 01:01:16,220
dacă vă păstrați doar evidența numărului de cuvintele pe care le adăugați în

686
01:01:16,220 --> 01:01:18,080
atunci când ai de a face cu sarcina.

687
01:01:18,080 --> 01:01:22,630
Și astfel, atunci dimensiunea fel se poate returna doar o variabilă globală de mărime.

688
01:01:25,320 --> 01:01:28,530
>> Acum ajungem pentru a verifica.

689
01:01:28,530 --> 01:01:33,920
Aceleași standarde ca și până acum, în cazul în care dorim să permită insensibilitate caz.

690
01:01:33,920 --> 01:01:40,400
De asemenea, vom presupune că șirurile sunt doar caractere alfabetice sau apostrofuri

691
01:01:40,400 --> 01:01:44,000
deoarece copiii este o matrice de 27 lung,

692
01:01:44,000 --> 01:01:48,480
astfel încât toate literele din alfabet, plus apostrof.

693
01:01:48,480 --> 01:01:53,800
Pentru verificați ceea ce veți dori să faceți este să vă veți dori să înceapă de la rădăcină

694
01:01:53,800 --> 01:01:58,440
deoarece radacina va indica o matrice care conține

695
01:01:58,440 --> 01:02:01,630
toate literele posibile minime orientative ale unui cuvânt.

696
01:02:01,630 --> 01:02:03,680
Ai de gând să înceapă acolo,

697
01:02:03,680 --> 01:02:11,590
si apoi ai de gând să verificați este această valoare NULL sau nu,

698
01:02:11,590 --> 01:02:16,490
pentru că dacă valoarea este NULL, ceea ce înseamnă că dicționarul nu are nici o valoare

699
01:02:16,490 --> 01:02:21,480
care conțin această scrisoare, în care o ordine anume.

700
01:02:21,480 --> 01:02:24,970
Dacă e NULL, atunci înseamnă că cuvântul este greșit imediat.

701
01:02:24,970 --> 01:02:27,110
Dar dacă nu e NULL, atunci puteți continua,

702
01:02:27,110 --> 01:02:34,090
spun că prima literă este o scrisoare de prim posibil într-un cuvânt,

703
01:02:34,090 --> 01:02:40,630
asa ca acum vreau pentru a verifica dacă a doua scrisoare, că secvența, este în dicționarul meu.

704
01:02:40,630 --> 01:02:46,540
Deci, ai de gând să mergi la index al copiilor din primul nod

705
01:02:46,540 --> 01:02:50,720
și verificați dacă această scrisoare există două.

706
01:02:50,720 --> 01:02:57,440
Apoi, repetați acest proces pentru a verifica dacă această secvență este valabil sau nu

707
01:02:57,440 --> 01:02:59,060
în cadrul trie dumneavoastră.

708
01:02:59,060 --> 01:03:06,430
Ori de câte ori copiii nodului de la faptul că punctele de index pentru a NULL,

709
01:03:06,430 --> 01:03:10,710
știți că secvența nu există,

710
01:03:10,710 --> 01:03:16,230
dar apoi, dacă ați ajunge la sfârșitul cuvântul pe care le-ați introduse,

711
01:03:16,230 --> 01:03:20,070
apoi doriți să verificați acum că am terminat această secvență

712
01:03:20,070 --> 01:03:27,610
și a găsit în trie mea, este acel cuvânt valabil sau nu?

713
01:03:27,610 --> 01:03:32,480
Și da, atunci vă doriți pentru a verifica dacă, și atunci, dacă ați constatat că secvența,

714
01:03:32,480 --> 01:03:35,120
apoi doriți să verificați dacă acel cuvânt este valabil sau nu

715
01:03:35,120 --> 01:03:40,290
deoarece amintesc înapoi în cazul anterior pe care am desenat în cazul în care am avut FOOB,

716
01:03:40,290 --> 01:03:48,410
că a fost o secvență validă pe care am găsit, dar nu a fost un cuvânt real valabile în sine.

717
01:03:50,570 --> 01:03:59,000
>> În mod similar, pentru descarce în încercări pe care doriți să descărcați toate nodurile din trie ta.

718
01:03:59,000 --> 01:04:04,790
Scuze. Similar cu tabelele de dispersie în cazul în care, în descarca am freed toate nodurile,

719
01:04:04,790 --> 01:04:09,740
în încercările pe care dorim să eliberăm de asemenea, toate nodurile.

720
01:04:09,740 --> 01:04:15,000
Unload va lucra de fapt, cea mai simplă de jos în sus

721
01:04:15,000 --> 01:04:19,290
deoarece acestea sunt în esență de preturi legate.

722
01:04:19,290 --> 01:04:22,540
Așa că vrem să ne asigurăm că țineți pe toate valorile

723
01:04:22,540 --> 01:04:25,700
și fără toate acestea în mod explicit.

724
01:04:25,700 --> 01:04:28,840
Ce ai de gând să doriți să faceți în cazul în care lucrați cu un trie

725
01:04:28,840 --> 01:04:35,640
este de a călători în partea de jos și gratuit nodul cel mai mic posibil primul

726
01:04:35,640 --> 01:04:39,190
și apoi du-te până la toate aceste copii și apoi gratuit tuturor celor,

727
01:04:39,190 --> 01:04:43,050
du-te în sus și apoi liber, etc

728
01:04:43,050 --> 01:04:48,790
Un fel de a face cu stratul de jos al primului trie

729
01:04:48,790 --> 01:04:51,940
si apoi merge până sus, odată ce am eliberat totul.

730
01:04:51,940 --> 01:04:56,720
Acesta este un exemplu bun de unde ar putea veni funcție recursivă la îndemână.

731
01:04:56,720 --> 01:05:03,830
Odată ce v-ați eliberat pe stratul de jos a trie dumneavoastră,

732
01:05:03,830 --> 01:05:08,000
atunci suna descărcați pe restul,

733
01:05:08,000 --> 01:05:13,620
asigurându-vă că vă gratuit în fiecare mini -

734
01:05:13,620 --> 01:05:16,410
Puteți vizualiza un fel de mini-l ca incercari.

735
01:05:23,300 --> 01:05:28,990
Deci, aveți rădăcină aici.

736
01:05:30,840 --> 01:05:35,230
Sunt doar simplificarea așa că nu trebuie să atragă 26 dintre ele.

737
01:05:37,250 --> 01:05:43,770
Deci ai astea, iar apoi acestea reprezintă secvențe de cuvinte

738
01:05:43,770 --> 01:05:54,620
în cazul în care toate aceste cercuri mici sunt litere care sunt valabile secvențe de litere.

739
01:06:03,040 --> 01:06:07,160
Să continuăm doar un pic mai mult.

740
01:06:15,110 --> 01:06:25,750
Ce ai de gând să doriți să faceți este gratuit partea de jos aici și apoi gratuit aceasta

741
01:06:25,750 --> 01:06:31,640
și apoi gratuit o una în partea de jos înainte de a vă elibera cea de sus aici

742
01:06:31,640 --> 01:06:38,180
pentru că dacă ceva gratuită în al doilea nivel aici,

743
01:06:38,180 --> 01:06:47,230
atunci tu de fapt ar pierde această valoare aici.

744
01:06:47,230 --> 01:06:54,780
De aceea e important în descărcarea pentru un trie pentru a vă asigura că vă elibera de jos primul.

745
01:06:54,780 --> 01:06:59,480
Ce ar putea să doriți să faceți este să spunem pentru fiecare nod

746
01:06:59,480 --> 01:07:06,430
Vreau să descarce toți copiii.

747
01:07:16,060 --> 01:07:22,140
>> Acum, că am trecut peste descarce pentru metoda de tabel hash, precum și metoda de trie,

748
01:07:22,140 --> 01:07:27,020
am de gând să doriți să se uite la Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind aveți cu următoarele comenzi.

750
01:07:29,640 --> 01:07:32,700
Ai Valgrind-V.

751
01:07:32,700 --> 01:07:40,960
Ești de verificare pentru toate scurgeri atunci când rulați descifrează dat acest text anumită

752
01:07:40,960 --> 01:07:46,980
deoarece descifrează trebuie să ia într-un fișier text.

753
01:07:46,980 --> 01:07:52,330
Deci, Valgrind va rula programul tău, vă spun cât de multe bytes tine alocat,

754
01:07:52,330 --> 01:07:57,150
cati bytes te-a eliberat, și vă va spune dacă te-a eliberat suficient

755
01:07:57,150 --> 01:07:58,930
sau dacă nu liber suficient,

756
01:07:58,930 --> 01:08:02,850
sau, uneori, puteți chiar peste-free, cum ar fi gratuit un nod care a fost eliberat deja

757
01:08:02,850 --> 01:08:05,140
și așa va veți reveni erori.

758
01:08:05,140 --> 01:08:11,600
Dacă utilizați Valgrind, aceasta vă va da unele mesaje

759
01:08:11,600 --> 01:08:15,970
indicând dacă ați eliberat fie mai mult decât suficient, suficient,

760
01:08:15,970 --> 01:08:19,609
sau mai mult de suficient de multe ori.

761
01:08:24,370 --> 01:08:30,410
>> O parte a acestui PSET, este opțională pentru a contesta Consiliul de mare.

762
01:08:30,410 --> 01:08:35,790
Dar când avem de-a face cu aceste structuri de date

763
01:08:35,790 --> 01:08:40,689
e un fel de distractiv pentru a vedea cât de repede și cât de eficient structurile de date ar putea fi.

764
01:08:40,689 --> 01:08:44,490
Are rezultatul funcției hash într-o mulțime de coliziuni?

765
01:08:44,490 --> 01:08:46,300
Sau este dimensiunea foarte mare de date?

766
01:08:46,300 --> 01:08:49,420
Are ea lua o mulțime de timp pentru a traversa?

767
01:08:49,420 --> 01:08:54,800
În jurnalul de abecedar, să emită cât de mult timp le utilizați pentru a încărca,

768
01:08:54,800 --> 01:08:57,700
pentru a verifica, pentru a efectua dimensiuni, și de a descărca,

769
01:08:57,700 --> 01:09:00,720
și astfel acestea sunt postate în Consiliul de Big,

770
01:09:00,720 --> 01:09:03,600
în cazul în care aveți posibilitatea să concureze cu colegii dvs.

771
01:09:03,600 --> 01:09:11,350
și unii membri ai personalului pentru a vedea cine are cel mai rapid verificatorul ortografic.

772
01:09:11,350 --> 01:09:14,760
Un lucru pe care aș vrea să rețineți despre tabelele de dispersie

773
01:09:14,760 --> 01:09:20,470
este faptul că există unele funcții destul de simple, pe care le-ar putea hash gândi.

774
01:09:20,470 --> 01:09:27,240
De exemplu, aveți 26 găleți, și așa în fiecare cupă

775
01:09:27,240 --> 01:09:30,200
corespunde primei litere într-un cuvânt,

776
01:09:30,200 --> 01:09:35,229
dar asta va duce într-un tabel hash destul de dezechilibrată

777
01:09:35,229 --> 01:09:40,979
pentru că există o mulțime cuvinte care încep cu mai puțin decât X începe cu M, de exemplu.

778
01:09:40,979 --> 01:09:47,890
Un mod de a merge despre abecedar este dacă doriți să obțineți toate alte funcționalități în jos,

779
01:09:47,890 --> 01:09:53,240
apoi utilizați doar o simplă funcție hash pentru a putea pentru a obține codul de alergare

780
01:09:53,240 --> 01:09:58,650
și apoi du-te înapoi și modifica dimensiunea tabelului hash și definiția.

781
01:09:58,650 --> 01:10:03,430
Există o mulțime de resurse de pe Internet pentru funcțiile hash,

782
01:10:03,430 --> 01:10:08,250
și astfel pentru acest PSET vă este permis să cerceteze funcțiile hash pe internet

783
01:10:08,250 --> 01:10:15,560
pentru unele sugestii și inspirație, atâta timp cât vă asigurați-vă pentru a cita în cazul în care l-ați primit de la.

784
01:10:15,560 --> 01:10:22,060
Ești binevenit să te uiți și să interpreteze o funcție de distribuire pe care le găsiți pe Internet.

785
01:10:22,060 --> 01:10:27,460
Înapoi la care, ați putea fi capabil de a vedea dacă cineva a folosit un trie

786
01:10:27,460 --> 01:10:31,700
dacă punerea în aplicare a acestora este mai rapidă decât masa ta hash sau nu.

787
01:10:31,700 --> 01:10:35,290
Puteți să prezinte consiliului Big de mai multe ori.

788
01:10:35,290 --> 01:10:37,660
Acesta va înregistra intrarea cea mai recentă.

789
01:10:37,660 --> 01:10:44,300
Deci, poate că vă schimbați funcția hash și apoi dau seama că este de fapt mult mai repede

790
01:10:44,300 --> 01:10:46,780
sau mult mai lent decât înainte.

791
01:10:46,780 --> 01:10:50,960
Asta e un pic de un mod distractiv.

792
01:10:50,960 --> 01:10:57,190
Nu e întotdeauna 1 sau 2 membri ai personalului care încearcă să facă mai lent dicționarul posibil,

793
01:10:57,190 --> 01:11:00,210
asa ca asta e intotdeauna distractiv sa se uite la.

794
01:11:00,210 --> 01:11:07,630
>> De utilizare pentru PSET este aveți o pronuntie cu un dicționar opțional

795
01:11:07,630 --> 01:11:12,840
și apoi un fișier text obligatoriu.

796
01:11:12,840 --> 01:11:18,380
În mod implicit, atunci când rulați abecedar, cu doar un fișier text și nu specificați un dicționar,

797
01:11:18,380 --> 01:11:24,410
se va folosi fișierul text dicționarul, una mare

798
01:11:24,410 --> 01:11:27,920
în dosarul cs50/pset5/dictionaries.

799
01:11:27,920 --> 01:11:32,760
Pe care o are peste 100.000 de cuvinte.

800
01:11:32,760 --> 01:11:37,950
Ei au, de asemenea, un mic dictionar care are cuvinte considerabil mai puține

801
01:11:37,950 --> 01:11:40,730
că CS50-a făcut pentru tine.

802
01:11:40,730 --> 01:11:44,050
Cu toate acestea, puteți foarte ușor face doar dicționarul ta

803
01:11:44,050 --> 01:11:47,150
dacă doriți doar să fie de lucru în exemple mici -

804
01:11:47,150 --> 01:11:51,140
de exemplu, dacă doriți să utilizați gdb si stii valorile specifice

805
01:11:51,140 --> 01:11:53,560
pe care doriți tabel hash pentru a mapa pentru a.

806
01:11:53,560 --> 01:12:00,430
Deci, tu chiar pot face fișierul text propriul doar cu bar, BAZ, FOO, și foobar,

807
01:12:00,430 --> 01:12:04,860
face că într-un fișier text, fiecare separa pe cei cu 1 linie,

808
01:12:04,860 --> 01:12:12,670
și să facă apoi fișierul text propriu, care conține numai literalmente poate 1 sau 2 cuvinte

809
01:12:12,670 --> 01:12:15,950
astfel încât să știți exact ce ar trebui să fie de ieșire.

810
01:12:15,950 --> 01:12:21,870
Unele dintre fișierele de text eșantion care Consiliul de mare atunci când executați provocare va verifica

811
01:12:21,870 --> 01:12:25,580
sunt Război și pace și o Jane Austen roman sau ceva de genul asta.

812
01:12:25,580 --> 01:12:30,450
Deci, atunci când sunteți la început, e mult mai usor sa-ti faci propriile fișiere de text

813
01:12:30,450 --> 01:12:34,160
care conțin doar câteva cuvinte sau poate 10

814
01:12:34,160 --> 01:12:38,280
astfel încât să puteți anticipa ce rezultatul ar trebui să fie

815
01:12:38,280 --> 01:12:42,880
și apoi verificați-l împotriva acestei, deci mai mult de un exemplu controlat.

816
01:12:42,880 --> 01:12:45,820
Și așa, deoarece avem de a face cu prezicerea și desen lucruri în jurul valorii de,

817
01:12:45,820 --> 01:12:48,690
din nou, vreau să vă încurajez să utilizați stilou și hârtie

818
01:12:48,690 --> 01:12:50,700
pentru că se întâmplă cu adevărat să te ajute cu asta -

819
01:12:50,700 --> 01:12:55,620
desen săgețile, cum tabel hash sau cum va arata trie,

820
01:12:55,620 --> 01:12:57,980
atunci când sunteți eliberarea ceva în cazul în care săgețile merg,

821
01:12:57,980 --> 01:13:01,730
te descurci pe suficient, nu vezi orice link-uri dispariție

822
01:13:01,730 --> 01:13:05,750
și care se încadrează în abisul memoriei scurs.

823
01:13:05,750 --> 01:13:11,070
Asa ca te rog, vă rugăm să încercați pentru a trage lucruri, chiar înainte de a ajunge la scrierea de cod în jos.

824
01:13:11,070 --> 01:13:14,520
Egal lucrurile în așa fel încât să înțelegeți modul în care lucrurile sunt de gând să lucreze

825
01:13:14,520 --> 01:13:22,750
pentru că atunci îți garantez că vei rula în muddles indicatorului mai puțin acolo.

826
01:13:24,270 --> 01:13:25,910
>> Bine.

827
01:13:25,910 --> 01:13:28,780
Vreau să vă urez cele mai bune foarte mult noroc cu acest PSET.

828
01:13:28,780 --> 01:13:31,980
Este, probabil, cel mai dificil.

829
01:13:31,980 --> 01:13:40,360
Deci, încercați să înceapă devreme, trage lucruri, trage lucruri, și mult noroc.

830
01:13:40,360 --> 01:13:42,980
Acest lucru a fost Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]