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

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Universiteti i Harvardit]

3
00:00:04,870 --> 00:00:07,190
[Kjo është CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Dakord. Hello, të gjithë, dhe të mirëpritur të walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 është misspellings, në të cilën ne do të bërë një spell checker-.

6
00:00:17,400 --> 00:00:21,030
Damë spell-janë jashtëzakonisht të rëndësishme.

7
00:00:21,030 --> 00:00:23,390
Kjo ka ndodhur ndonjëherë për ju?

8
00:00:23,390 --> 00:00:27,170
Ju punoni shumë, shumë grumbullojnë në një letër për një përplasje

9
00:00:27,170 --> 00:00:33,120
dhe pastaj ende të përfundojnë duke marrë një Rade shumë shkëlqim si një D ose A = D

10
00:00:33,120 --> 00:00:39,390
dhe të gjithë, sepse ju jeni Spoiler sallam me mëlçi në fjalën balenë gjerë.

11
00:00:39,390 --> 00:00:44,710
Po, proofreading speca tuaja është një çështje e, të impotenca madhe.

12
00:00:44,710 --> 00:00:49,140
Ky është një problem që prek burrëror, studentët burrëror.

13
00:00:49,140 --> 00:00:56,260
Unë u tha një herë nga Sith torturues tim të klasës se unë kurrë nuk do të merrni në një koleg të mirë.

14
00:00:56,260 --> 00:01:00,250
Dhe kjo është e gjitha që kam kërkuar kurrë, që të gjithë çdo fëmijë dëshiron në moshën time,

15
00:01:00,250 --> 00:01:04,569
vetëm për të marrë në një koleg të mirë.

16
00:01:04,569 --> 00:01:12,720
Dhe jo vetëm ndonjë koleg. Nr Unë të kërkuar për të shkuar në një kolegut të Fildishtë Ligjor.

17
00:01:12,720 --> 00:01:18,360
Pra, nëse unë nuk e kam përmirësim, do të jetë zhdukur ëndrrat e mia për të shkuar në Harvard,

18
00:01:18,360 --> 00:01:22,730
Jalë, ose burg - ju e dini, në burg, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Kështu që unë kam veten një spell checker-.

20
00:01:25,170 --> 00:01:29,380
Kjo është një fragment të vogël nga një prej artistëve të mi të preferuar fjalë e thënë, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
Gjithsesi, siç thotë ai, rëndësia e të paturit e një spell checker-është shumë e rëndësishme.

22
00:01:34,630 --> 00:01:39,440
>> Kështu mirëpresim tek walkthrough 5, në të cilën ne do të flasim rreth pset5: misspellings,

23
00:01:39,440 --> 00:01:44,300
në të cilën ne do të jetë bërë shumë vetë tonë spell checker-.

24
00:01:44,300 --> 00:01:50,880
Toolbox për këtë javë, Kodin e Shpërndarjes, do të jetë e rëndësishme të shohim në

25
00:01:50,880 --> 00:01:54,950
vetëm për të kuptuar funksionet e ndryshme që fjalori juaj do të ketë.

26
00:01:54,950 --> 00:02:01,500
Ne jemi të vërtetë do të të ketë të shumta. Fotografi që së bashku bëjnë c pset tonë.

27
00:02:01,500 --> 00:02:05,420
Dhe kështu duke kërkuar nëpër aspekte të ndryshme, edhe pse ne nuk jeni aktualisht redaktimi

28
00:02:05,420 --> 00:02:10,770
një e dosjeve, Shkruaj një fjalë, duke e ditur se si punon me lidhje me dictionary.c,

29
00:02:10,770 --> 00:02:14,100
të cilat ne do të jetë me shkrim, do të jetë shumë e rëndësishme.

30
00:02:14,100 --> 00:02:16,970
Spekulim pset gjithashtu përmban një shumë informacione të dobishme

31
00:02:16,970 --> 00:02:21,360
në aspektin e gjërave që ju mund të supozojmë, rregullat dhe gjëra si kjo,

32
00:02:21,360 --> 00:02:24,710
kështu që të jetë i sigurt për të lexuar spekulim pset kujdes për këshilla.

33
00:02:24,710 --> 00:02:29,310
Dhe kur në dyshim të një rregulli ose diçka të tillë, atëherë gjithmonë i referohen spekulim pset

34
00:02:29,310 --> 00:02:31,550
ose Diskutoni.

35
00:02:31,550 --> 00:02:34,060
Kjo pset do të mbështeten në pointers,

36
00:02:34,060 --> 00:02:37,890
kështu që ne duam të sigurohemi se ne e kuptojmë dallimin midis yje të mundshëm shtuar

37
00:02:37,890 --> 00:02:41,680
në frontin e emrit treguesin së dhe ampersands, si për të liruar ato, etj

38
00:02:41,680 --> 00:02:47,550
Pra, duke qenë një mjeshtër i pointers do të jetë shumë e dobishme në këtë grup problemit.

39
00:02:47,550 --> 00:02:50,460
Ne jemi duke shkuar për të parë në listat e lidhura pak më shumë,

40
00:02:50,460 --> 00:02:57,790
ku ne kemi elemente që ne e quajmë nyjet që kanë edhe një vlerë, si dhe si një tregues

41
00:02:57,790 --> 00:03:02,520
në nyjen e ardhshëm, dhe kështu në thelb lidh elementeve të ndryshme njëra pas tjetrës.

42
00:03:02,520 --> 00:03:07,190
Ka disa opsione të ndryshme të zbatimit fjalorin tuaj aktuale.

43
00:03:07,190 --> 00:03:13,150
Ne do të shikojmë në dy metoda kryesore, e cila është tavolina hash dhe pastaj përpiqet.

44
00:03:13,150 --> 00:03:17,660
Në të dyja këto, ato përfshijnë disa lloj të nocionit të një liste të lidhur

45
00:03:17,660 --> 00:03:20,790
ku keni elemente të lidhura me njëri-tjetrin.

46
00:03:20,790 --> 00:03:25,640
Dhe kështu që ne jemi duke shkuar për të parë mbi se si ju mund të jetë në gjendje të veprojë rreth listave të lidhura,

47
00:03:25,640 --> 00:03:29,680
krijuar ato, për të lundruar në drejtim të asaj se si për të, për shembull, të futur një nyje në të

48
00:03:29,680 --> 00:03:32,760
ose pa të gjitha nyjet si.

49
00:03:32,760 --> 00:03:34,740
Në kushtet e nyjave liruar, se me të vërtetë e rëndësishme

50
00:03:34,740 --> 00:03:37,700
se sa herë që ne memorie malloc, më pas ne e liruar atë.

51
00:03:37,700 --> 00:03:42,910
Pra, ne duam të sigurohemi që asnjë pointer shkon unfreed, se ne nuk kemi ndonjë rrjedhjet e kujtesës.

52
00:03:42,910 --> 00:03:48,330
Ne jemi duke shkuar për të futur një mjet të quajtur Shprehje që shkon programin tuaj

53
00:03:48,330 --> 00:03:52,260
dhe kontrollon nëse të gjitha kujtesës që keni caktuar është liruar më pas.

54
00:03:52,260 --> 00:03:59,080
Pset juaj është vetëm plotësoni kur ajo punon dhe ajo ka funksionalitet të plotë,

55
00:03:59,080 --> 00:04:03,990
por gjithashtu, Shprehje tregon se ju nuk e keni gjetur asnjë rrjedhjet e kujtesës.

56
00:04:03,990 --> 00:04:06,690
Së fundi, për këtë pset, unë me të vërtetë dua të theksoj -

57
00:04:06,690 --> 00:04:11,360
Unë do të thotë, si zakonisht, unë jam padyshim një mbështetës i përdorur stilolaps dhe letër për grupe tuaja problemore,

58
00:04:11,360 --> 00:04:14,840
por për këtë, unë mendoj se stilolaps dhe letër do të jetë veçanërisht e rëndësishme

59
00:04:14,840 --> 00:04:19,000
kur ju doni të tërhequr shigjeta për të gjëra dhe të kuptuarit se si funksionojnë gjërat.

60
00:04:19,000 --> 00:04:24,440
Pra, patjetër të përpiqen të përdorin stilolaps dhe letër për të nxjerrë gjëra para se të merrni coding

61
00:04:24,440 --> 00:04:26,970
për shkak se ajo mund të marrë pak çrregullt.

62
00:04:26,970 --> 00:04:30,700
>> Së pari, le të shkojnë në listat e lidhura pak.

63
00:04:30,700 --> 00:04:35,510
Listat e lidhura përbëhen nga nyjet, ku çdo nyje ka një vlerë të lidhur me të,

64
00:04:35,510 --> 00:04:39,810
si një tregues për nyjen e ardhshme pas saj.

65
00:04:39,810 --> 00:04:43,680
Një disa gjëra të rëndësishme që lidhen me listat janë se ne kemi nevojë për të kujtuar

66
00:04:43,680 --> 00:04:48,810
ku nyja jonë e parë është, dhe pastaj një herë ne e dimë se ku nyja e parë është,

67
00:04:48,810 --> 00:04:52,990
në këtë mënyrë ne mund të hyni në nyjen që pikat e para nyjë në

68
00:04:52,990 --> 00:04:55,850
dhe pastaj njëra pas se dhe ai pas kësaj.

69
00:04:55,850 --> 00:05:00,340
Dhe pastaj elementi i fundit në listën tuaj është e lidhur tregues se Nyja e

70
00:05:00,340 --> 00:05:02,340
është gjithmonë do të theksojnë null.

71
00:05:02,340 --> 00:05:08,230
Kur një pikë nyjë për null, atëherë ju e dini se ju keni arritur fundin e listës,

72
00:05:08,230 --> 00:05:12,320
se kjo është nyja e fundit, se nuk ka asgjë pas kësaj.

73
00:05:12,320 --> 00:05:16,970
Këtu në këtë skematike, ju shihni se shigjetat janë pointers,

74
00:05:16,970 --> 00:05:20,290
dhe seksioni blu është ku vlera është ruajtur,

75
00:05:20,290 --> 00:05:24,420
dhe pastaj kutia e kuqe me treguesin ndaj saj është tregues nyjen e

76
00:05:24,420 --> 00:05:27,050
treguar në nyjen e ardhshëm pas saj.

77
00:05:27,050 --> 00:05:33,730
Dhe kështu që ju shihni këtu, nyja D do të tregojnë për NULL, sepse ajo është elementi i fundit në listë.

78
00:05:33,730 --> 00:05:38,240
>> Le të shohim se si ne mund të përcaktojë një struct për një nyje.

79
00:05:38,240 --> 00:05:40,130
Dhe pasi ne duam që të ketë nyje të shumta,

80
00:05:40,130 --> 00:05:43,180
kjo do të bëhet një struct typedef

81
00:05:43,180 --> 00:05:46,870
në të cilën ne do të kemi disa raste të ndryshme të nyjeve.

82
00:05:46,870 --> 00:05:50,850
Dhe kështu ne define si një lloj të ri të dhënave.

83
00:05:50,850 --> 00:05:53,630
Këtu, ne kemi një nyje typedef struct.

84
00:05:53,630 --> 00:05:56,160
Në këtë shembull, ne jemi që kanë të bëjnë me nyje numër i plotë,

85
00:05:56,160 --> 00:06:00,490
kështu që ne kemi një vlerë integer emrin dhe pastaj ne kemi një tjetër tregues,

86
00:06:00,490 --> 00:06:07,390
dhe në këtë rast, kjo është një tregues për një nyje, kështu që ne kemi një nyje struct * quajtur ardhshëm.

87
00:06:07,390 --> 00:06:09,520
Dhe atëherë ne jemi duke e quajtur këtë gjë nyjen tërë.

88
00:06:09,520 --> 00:06:11,110
Sigurohuni që ju ndiqni këtë sintaksë.

89
00:06:11,110 --> 00:06:17,940
Vini re se nyja është referohet në të vërtetë lart, si më poshtë formatimin e teksteve kaçurrel.

90
00:06:17,940 --> 00:06:23,400
Pastaj të mbajnë gjurmët e ku nyja ime e parë është në këtë listë e lidhur,

91
00:06:23,400 --> 00:06:29,390
atëherë unë kam një tregues nyje quajtur kreu, dhe unë hapësirë ​​malloc mjaftueshme për madhësinë e një nyje.

92
00:06:29,390 --> 00:06:36,240
Njoftim, megjithatë, se kreu në fakt është një tregues nyje në krahasim me një nyje aktuale vetë.

93
00:06:36,240 --> 00:06:40,130
Kështu kreu në fakt nuk përmban ndonjë vlerë,

94
00:06:40,130 --> 00:06:45,590
ajo vetëm tregon cilado nyja e parë në listën time të lidhura është.

95
00:06:55,080 --> 00:06:58,340
>> Për të marrë një kuptim më të mirë të listave të lidhura, sepse kjo është shumë e rëndësishme

96
00:06:58,340 --> 00:07:02,220
të mbajnë gjurmët për të bërë të sigurtë që ju të ruajtur zinxhirin,

97
00:07:02,220 --> 00:07:09,990
Më pëlqen të mendoj për atë si njerëzit në një linjë që mbajnë duart,

98
00:07:09,990 --> 00:07:14,330
ku çdo person është i mbajnë duart me një tjetër.

99
00:07:14,330 --> 00:07:18,350
Ju nuk mund të shihni në këtë vizatim, por në thelb ata janë treguar të personit tjetër

100
00:07:18,350 --> 00:07:23,760
që është në zinxhirin e tyre.

101
00:07:23,760 --> 00:07:29,270
Dhe kështu që nëse ju doni të kaloj nëpër një listë të lidhur ku këta njerëz -

102
00:07:29,270 --> 00:07:32,830
imagjinoni të gjithë ata njerëz kanë vlera të lidhur me to

103
00:07:32,830 --> 00:07:36,590
dhe gjithashtu theksojnë tek personi tjetër në linjë -

104
00:07:36,590 --> 00:07:40,810
në qoftë se ju doni të kaloj nëpër lista të lidhur, për shembull, ose të ndryshoni vlerat

105
00:07:40,810 --> 00:07:42,830
ose kërko për një vlerë apo diçka si kjo,

106
00:07:42,830 --> 00:07:48,270
atëherë ju do të dëshironi që të ketë një tregues për person të veçantë.

107
00:07:48,270 --> 00:07:52,670
Pra, ne do të kemi një nyje të dhënave treguesin lloji.

108
00:07:52,670 --> 00:07:55,580
Për këtë shembull, le të thërrasë atë kursorit.

109
00:07:55,580 --> 00:07:59,630
Një tjetër mënyrë e përbashkët për të përmendur se kjo do të jetë iterator ose diçka si kjo

110
00:07:59,630 --> 00:08:05,130
sepse ajo është iterating gjatë dhe në fakt lëvizin nyjen e cila është e treguar.

111
00:08:05,130 --> 00:08:14,410
Kjo këtu do të jetë kursori tonë.

112
00:08:14,410 --> 00:08:20,180
Kursori tonë së pari do të theksojnë elementin e parë në listën tonë.

113
00:08:20,180 --> 00:08:26,910
Dhe kështu që ajo që ne duam të bëjmë është që ne në thelb do të jetë e vazhdueshme kursorin,

114
00:08:26,910 --> 00:08:29,130
lëvizur atë nga njëra anë në tjetrën.

115
00:08:29,130 --> 00:08:33,409
Në këtë rast, ne duam për të lëvizur atë në elementin tjetër në listë.

116
00:08:33,409 --> 00:08:38,480
Me vargjeve, ajo që ne do të bëjmë është që ne do të themi vetëm ne rritjen e indeksit nga 1.

117
00:08:38,480 --> 00:08:46,020
Në këtë rast, ajo që ne duhet të bëni është të gjeni të vërtetë që personi ky person aktuale është treguar,

118
00:08:46,020 --> 00:08:48,930
dhe kjo do të jetë vlera e ardhshëm.

119
00:08:48,930 --> 00:08:53,230
Pra, nëse kursori është vetëm një tregues nyje, atëherë ajo që ne duam të bëjmë

120
00:08:53,230 --> 00:08:56,320
është që ne duam për të marrë vlerën që kursori është treguar.

121
00:08:56,320 --> 00:09:01,350
Ne duam që të merrni në atë nyje dhe pastaj, pasi ne jemi në atë nyje, të gjetur ku është treguar për të.

122
00:09:01,350 --> 00:09:05,820
Për të marrë në nyjen aktuale që kursori është treguar për të,

123
00:09:05,820 --> 00:09:13,160
Zakonisht ne tregojnë atë me (* kursorin).

124
00:09:13,160 --> 00:09:19,160
Kjo do të ju jap nyjen aktuale që kursori është duke treguar.

125
00:09:19,160 --> 00:09:21,730
Dhe pastaj pas kësaj, ajo që ne duam të bëjmë është që ne duam për të hyrë

126
00:09:21,730 --> 00:09:25,680
çfarëdo që vlera tjetër është nyje.

127
00:09:25,680 --> 00:09:32,820
Për ta bërë këtë, për të hyrë në vlerat brenda e struct, kemi operatorin dot.

128
00:09:32,820 --> 00:09:39,530
Pra, atëherë ajo do të jetë (* kursori). Ardhshëm.

129
00:09:39,530 --> 00:09:44,840
Por kjo është pak e çrregullt në drejtim të pasur kllapa rreth kursorit *,

130
00:09:44,840 --> 00:09:56,800
dhe kështu që ne zëvendësojë këtë deklaratë tërë me kursorin->.

131
00:09:56,800 --> 00:10:02,700
Kjo është një dash dhe pastaj një shenjë e madhe se, kështu duke e bërë një shigjetë.

132
00:10:02,700 --> 00:10:05,840
kursori-> ardhshëm.

133
00:10:05,840 --> 00:10:12,390
Kjo do të vërtetë të merrni ju nyja që pikat kursorin. Kjo vlerë është e ardhshëm.

134
00:10:12,390 --> 00:10:16,790
Pra, në vend që të kesh yll dhe dot, ju jeni duke zëvendësuar atë me një shigjetë.

135
00:10:16,790 --> 00:10:24,820
Jenë shumë të kujdesshëm për të bërë të sigurtë që ju përpiqeni të përdorni këtë sintaksë.

136
00:10:33,550 --> 00:10:37,620
>> Tani që ne kemi kursorin tonë, në qoftë se ne duam të hyrë në vlerë,

137
00:10:37,620 --> 00:10:40,450
më parë, ne kishim kursori-> tjetër,

138
00:10:40,450 --> 00:10:46,260
por për të hyrë në vlerën në nyjen që kursori është duke treguar, ne thjesht themi

139
00:10:46,260 --> 00:10:48,070
nyjen-> vlera.

140
00:10:48,070 --> 00:10:53,600
Nga atje, kjo është e të dhënave të llojit të përcaktuar çdo gjë që ne kemi vlerat dhe nyjet të jetë.

141
00:10:53,600 --> 00:10:59,620
Në qoftë se kjo është një nyje int, atëherë kursori-> vlera është vetëm do të jetë një numër të plotë.

142
00:10:59,620 --> 00:11:04,870
Pra, ne mund të bëjë operacione në atë, kontrolloni barazitë, të caktojë atë vlera të ndryshme, etj

143
00:11:04,870 --> 00:11:11,090
Pra, atëherë çfarë ju doni të bëni nëse ju doni të lëvizni kursorin tek personi tjetër,

144
00:11:11,090 --> 00:11:15,270
ju në të vërtetë të ndryshojë vlerën e kursorit.

145
00:11:15,270 --> 00:11:19,340
Që kursori është një tregues nyje, ju ndryshoni adresën aktuale akrep

146
00:11:19,340 --> 00:11:23,890
në adresën e nyjeve tjetër në listën tuaj.

147
00:11:23,890 --> 00:11:28,930
Kjo është vetëm disa Kodi ZIP ku ju mund të iterate.

148
00:11:28,930 --> 00:11:31,230
Ku kam koment bëjë diçka,

149
00:11:31,230 --> 00:11:33,850
kjo është ajo ku ju jeni me siguri do të ketë qasje në vlerën

150
00:11:33,850 --> 00:11:37,850
ose të bëjë diçka të bëjë me atë nyje të veçantë.

151
00:11:37,850 --> 00:11:43,050
Për të filluar atë, unë them se kursori im fillimisht

152
00:11:43,050 --> 00:11:48,430
do të tregojnë për elementin e parë në listën e lidhur.

153
00:11:48,430 --> 00:11:52,910
Dhe kështu deri përpara, kam definuar atë si kreun e nyjeve.

154
00:11:52,910 --> 00:11:57,610
>> Siç e kam përmendur më parë, duke çliruar është me të vërtetë e rëndësishme.

155
00:11:57,610 --> 00:12:02,440
Ju dëshironi të bëni të sigurtë që ju të liruar çdo element në listë pasi të keni përfunduar me atë.

156
00:12:02,440 --> 00:12:04,940
Kur ju nuk keni nevojë për ndonjë nga ato referencë pointers më,

157
00:12:04,940 --> 00:12:10,620
ju doni të bëni të sigurtë që ju të liruar të gjithë ata pointers.

158
00:12:10,620 --> 00:12:14,460
Por ju doni të jenë shumë të kujdesshëm këtu në atë që ju doni të shmangur çdo rrjedhjet e kujtesës.

159
00:12:14,460 --> 00:12:25,080
Në qoftë se ju pa një person para kohe, atëherë të gjitha pointers se se pikë nyjë të

160
00:12:25,080 --> 00:12:26,900
do të jetë e humbur.

161
00:12:26,900 --> 00:12:32,070
Going back to shembullin e personit për ta bërë atë një pak më të lartë aksionet,

162
00:12:32,070 --> 00:12:49,600
le të kemi këta njerëz, me përjashtim në këtë rast ata janë hovering mbi një liqen me një përbindësh.

163
00:12:49,600 --> 00:12:53,200
Ne duam të sigurohemi që sa herë që ne të lirë, ne nuk do të humbin

164
00:12:53,200 --> 00:12:58,920
dhe le të shkojnë e çdo nyje përpara se ne kemi liruar në fakt ato.

165
00:12:58,920 --> 00:13:05,730
Për shembull, në qoftë se ju do të thjesht të telefononi pa pagesë në këtë djalë këtu,

166
00:13:05,730 --> 00:13:15,350
atëherë ai do të lirohet, por pastaj të gjithë këta njerëz atëherë do të jetë e humbur

167
00:13:15,350 --> 00:13:18,450
dhe ata do të drift off dhe bie poshtë.

168
00:13:18,450 --> 00:13:24,900
Pra, ne duam të sigurohemi se në vend të kësaj, ne duam të mbajnë një lidhje me pjesën tjetër.

169
00:13:37,630 --> 00:13:42,480
Akrep tonë kokë, që tregon për elementin e parë në listë.

170
00:13:42,480 --> 00:13:49,990
Kjo është lloj i si një litar ankorimin personin e parë.

171
00:13:52,870 --> 00:13:57,470
Çfarë ju mund të dëshironi të bëni kur jeni të liruar një listë të ketë -

172
00:13:57,470 --> 00:14:04,520
Nëse ju doni për të liruar elementin e parë e parë, atëherë ju mund të ketë një tregues të përkohshme

173
00:14:04,520 --> 00:14:07,370
se pikë për çfarëdo elementi i parë është.

174
00:14:07,370 --> 00:14:11,420
Pra, ju keni treguesin tuaj të përkohshme treguar këtu.

175
00:14:11,420 --> 00:14:15,840
Në këtë mënyrë, ne kemi një të mbajë nyjen e parë.

176
00:14:15,840 --> 00:14:18,930
Dhe pastaj, pasi ne e dimë se nyja e parë do të lirohen,

177
00:14:18,930 --> 00:14:24,890
atëherë ne mund të lëvizin këtë litar, kjo spirancë, kokën tonë,

178
00:14:24,890 --> 00:14:31,930
që në fakt tregojnë për çfarëdo pari është treguar.

179
00:14:31,930 --> 00:14:38,760
Pra, ky kreu në fakt tregon elementin e dytë tani.

180
00:14:38,760 --> 00:14:43,980
Tani ne jemi të lejuar për të liruar çdo gjë që është ruajtur në temp,

181
00:14:43,980 --> 00:14:53,360
dhe kështu që ne mund të fshihet ajo që pa rrezikuar të gjitha nyjet e tjera në listën tonë.

182
00:14:54,140 --> 00:15:05,020
Një tjetër mënyrë që ju mund të bëni këtë mund të jetë

183
00:15:05,020 --> 00:15:08,650
çdo herë që ju vetëm të liruar elementin e fundit në listën e

184
00:15:08,650 --> 00:15:11,010
sepse ata janë të garantuara për të mos u tregoi asgjë.

185
00:15:11,010 --> 00:15:15,570
Kështu që ju mund vetëm të liruar këtë, atëherë kjo pa një, atëherë pa këtë një të tillë.

186
00:15:15,570 --> 00:15:21,900
Kjo definitivisht punon, por është pak e ngadalshme, sepse nga natyra e listave të lidhura,

187
00:15:21,900 --> 00:15:24,670
ne nuk mund thjesht menjëherë hidhen në një të fundit.

188
00:15:24,670 --> 00:15:28,030
Ne duhet të përshkojë çdo element në listën lidhur

189
00:15:28,030 --> 00:15:31,020
dhe kontrolloni nëse ky dikush është duke treguar NULL, kontrolloni çdo kohë,

190
00:15:31,020 --> 00:15:33,780
dhe pastaj një herë kemi arritur fundin, pastaj të lirë që.

191
00:15:33,780 --> 00:15:40,270
Nëse ju do të bëni këtë proces, ju do të jetë në fakt kontrolluar këtu,

192
00:15:40,270 --> 00:15:44,190
kontrolluar këtu, pastaj duke kontrolluar këtu, liruar atë,

193
00:15:44,190 --> 00:15:47,470
pastaj do të kthehet, duke kontrolluar këtu, duke kontrolluar këtu, liruar atë,

194
00:15:47,470 --> 00:15:49,660
kontrolluar këtu, dhe pastaj liruar atë.

195
00:15:49,660 --> 00:15:52,880
Kjo merr kohë pak më shumë. Po.

196
00:15:52,880 --> 00:15:59,060
>> [Student] A do të jetë e mundur për të bërë një listë e lidhur që ruan një dalje treguesin deri në fund?

197
00:15:59,060 --> 00:16:01,320
Kjo patjetër do të jetë e mundur.

198
00:16:01,320 --> 00:16:08,340
Ta përsërisë pyetjen, a është e mundur që të ketë një strukturë të lidhur listë

199
00:16:08,340 --> 00:16:12,490
të tilla që ju keni një tregues treguar deri në fund të listës të lidhura?

200
00:16:12,490 --> 00:16:18,090
Unë do të them se është e mundur, dhe çdo herë që ju të futur diçka në listën tuaj të lidhur

201
00:16:18,090 --> 00:16:21,470
ju do të keni për të rinovuar atë treguesin dhe gjëra të tilla si kjo.

202
00:16:21,470 --> 00:16:26,640
Ju do të keni një bisht nyje *, për shembull.

203
00:16:26,640 --> 00:16:29,840
Por kur ju jeni duke zbatuar këtë tipar, ju duhet të mendoni të tregtisë të humbura,

204
00:16:29,840 --> 00:16:32,700
si sa herë jam unë do të iterating mbi këtë,

205
00:16:32,700 --> 00:16:36,100
sa e vështirë është ajo do të jetë për të mbajtur gjurmët e bishtit si dhe kreun

206
00:16:36,100 --> 00:16:38,400
si iterator im, dhe gjëra të tilla si kjo.

207
00:16:40,730 --> 00:16:42,480
Bën që -? >> [Student] Yeah.

208
00:16:42,480 --> 00:16:48,270
Është e mundur, por në aspektin e vendimeve të projektimit, ju duhet të peshojnë mundësitë.

209
00:16:53,850 --> 00:17:01,090
>> Këtu është një skelet i kodit që do të ju lejojnë për të liruar çdo element në një listë të lidhura.

210
00:17:01,090 --> 00:17:05,460
Përsëri, pasi që unë jam iterating mbi një listë e lidhur, unë jam do të duan që të ketë një lloj të kursorit

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

212
00:17:08,670 --> 00:17:14,640
Ne jemi iterating derisa kursori është NULL.

213
00:17:14,640 --> 00:17:17,640
Ju nuk doni të iterate kur kursori juaj është NULL

214
00:17:17,640 --> 00:17:20,579
sepse kjo do të thotë se nuk ka asgjë në listë.

215
00:17:20,579 --> 00:17:25,069
Pra, atëherë këtu kam bërë një nyje * përkohshme

216
00:17:25,069 --> 00:17:29,610
duke treguar për atë që unë jam duke marrë parasysh është i pari i listës sime,

217
00:17:29,610 --> 00:17:35,340
dhe pastaj kam lëvizur kursorin tim përpara 1 dhe pastaj të lirë çdo gjë që kam pasur në ruajtje të përkohshme.

218
00:17:38,460 --> 00:17:43,650
>> Tani kemi ardhur për të futur në listat e lidhura.

219
00:18:00,200 --> 00:18:09,660
Unë kam tre nyje në listën time lidhur, dhe le të shkojë me rastin thjeshtë

220
00:18:09,660 --> 00:18:18,970
ku ne duam të futur një tjetër nyje në fund të listës sonë të lidhura.

221
00:18:18,970 --> 00:18:25,980
Për ta bërë këtë, të gjithë ne do të bëjmë është që ne do të kaloj

222
00:18:25,980 --> 00:18:32,100
për të gjetur se ku në fund aktual i listës është i lidhur, kështu që cilado është nyja treguar NULL -

223
00:18:32,100 --> 00:18:33,850
që është kjo -

224
00:18:33,850 --> 00:18:37,260
dhe pastaj thonë, në fakt, kjo nuk do të jetë nyja e fundit;

225
00:18:37,260 --> 00:18:39,830
ne jemi në të vërtetë do të ketë një tjetër.

226
00:18:39,830 --> 00:18:46,260
Pra, ne do të kemi këtë aktuale një pikë për çdo gjë që ne jemi futur.

227
00:18:46,260 --> 00:18:50,080
Deri tani ky person kuqe këtu bëhet nyja e fundit në listën e lidhur.

228
00:18:50,080 --> 00:18:56,080
Dhe kështu karakteristikë e nyjeve të fundit në listën e lidhur është se ajo tregon null.

229
00:18:56,080 --> 00:19:09,380
Pra, atëherë ajo që ne do të duhet të bëni është vendosur treguesin ky djalë kuq për NULL. Atje.

230
00:19:09,380 --> 00:19:25,370
>> Por çfarë nëse ne të kërkuar për të futur një nyje në mes të një të dytë dhe të tretë?

231
00:19:25,370 --> 00:19:28,960
Kjo nuk është fare e thjeshtë, sepse ne duam të sigurohemi

232
00:19:28,960 --> 00:19:34,290
se ne nuk e le të shkojnë e çdo nyje në listën tonë lidhur.

233
00:19:34,290 --> 00:19:43,450
Ajo që ne do të duhet të bëni është të siguroheni se ne anchor veten për secilën prej tyre.

234
00:19:43,450 --> 00:19:49,900
Për shembull, le të quajmë këtë një të dytë.

235
00:19:49,900 --> 00:19:54,390
Nëse ju tha e dyta tani tregon për këtë një të re

236
00:19:54,390 --> 00:20:02,520
dhe ju vetëm e bëri një tregues atje, atëherë kjo do të rezultojë në këtë djalë të humbur

237
00:20:02,520 --> 00:20:07,830
sepse nuk ka ndonjë lidhje të tij.

238
00:20:07,830 --> 00:20:18,970
Në vend të kësaj - unë do të tërheqë këtë përsëri. Falni aftësitë e mia artistike.

239
00:20:18,970 --> 00:20:26,570
Ne e dimë se ne nuk mund thjesht të drejtpërdrejtë lidhur 2 në një të ri.

240
00:20:26,570 --> 00:20:30,480
Ne duhet të sigurohemi që ne të mbajë në të atë të fundit.

241
00:20:30,480 --> 00:20:39,200
Ajo që ne mund të dëshironi të bëni është të ketë një tregues të përkohshme

242
00:20:39,200 --> 00:20:42,650
në elementin që do të jetë bashkëngjitur në.

243
00:20:42,650 --> 00:20:45,140
Pra, atëherë ne kemi një tregues të përkohshëm atje.

244
00:20:45,140 --> 00:20:50,780
Që ne e dimë se kjo një e treta është duke u mbajtur gjurmët e,

245
00:20:50,780 --> 00:20:53,680
2 tani mund të lidhura me një tonë të ri.

246
00:20:53,680 --> 00:20:57,490
Dhe në qoftë se kjo i ri djalë kuqe do të jetë në mes të 2 dhe 3,

247
00:20:57,490 --> 00:21:05,550
atëherë çfarë është tregues se djalë e shkuar për pikë për të? >> [Student] Temp.

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

249
00:21:07,490 --> 00:21:15,430
Pra, atëherë vlera e ardhshëm ky djalë kuq është do të jetë temp.

250
00:21:26,090 --> 00:21:33,010
Kur ju jeni futur në listat e lidhura, ne pamë që ne mund të

251
00:21:33,010 --> 00:21:38,260
lehtësisht të shtoni diçka në fund, duke krijuar një rrjet të përkohshëm,

252
00:21:38,260 --> 00:21:42,850
ose në qoftë se ne të kërkuar për të shtuar diçka në mes të array tonë,

253
00:21:42,850 --> 00:21:46,810
atëherë ajo do të marrë një pak më shumë shuffling rreth.

254
00:21:46,810 --> 00:21:50,240
Nëse ju doni të, për shembull, kanë një listë të renditura të lidhur,

255
00:21:50,240 --> 00:21:54,880
atëherë ju duhet të lloj peshojnë kostot dhe përfitimet e që

256
00:21:54,880 --> 00:21:59,720
sepse në qoftë se ju dëshironi që të ketë një rrjet të renditura, që do të thotë se çdo herë që ju të futur në të,

257
00:21:59,720 --> 00:22:01,630
ajo do të marrë kohë pak më shumë.

258
00:22:01,630 --> 00:22:05,500
Megjithatë, nëse ju doni të më vonë, si ne do të gjeni ne do të duan të,

259
00:22:05,500 --> 00:22:10,280
kërko përmes një listë e lidhur, atëherë ajo mund të jetë më e lehtë në qoftë se ju e dini se çdo gjë është në rregull.

260
00:22:10,280 --> 00:22:15,340
Kështu që ju mund të dëshironi të peshojnë kostot dhe përfitimet e kësaj.

261
00:22:20,150 --> 00:22:27,740
>> Një tjetër mënyrë për të futur në listën e lidhur është futur në fillim të listës.

262
00:22:27,740 --> 00:22:34,700
Nëse ne barazim spirancë tonë këtu - kjo është kreu ynë -

263
00:22:34,700 --> 00:22:40,960
dhe pastaj kanë këta njerëz të lidhur me të,

264
00:22:40,960 --> 00:22:48,460
dhe pastaj ne kemi një nyje të re të futur në fillim,

265
00:22:48,460 --> 00:22:52,590
atëherë çfarë mund të duam të bëjmë?

266
00:22:55,220 --> 00:23:03,580
Çfarë do të jetë i gabuar me vetëm duke thënë se unë dua të lidhë të kuqe në blu,

267
00:23:03,580 --> 00:23:05,790
sepse kjo është e para?

268
00:23:05,790 --> 00:23:08,570
Çfarë do të ndodhë këtu?

269
00:23:08,570 --> 00:23:12,130
Të gjitha këto tre do të merrni humbur.

270
00:23:12,130 --> 00:23:14,140
Pra, ne nuk duam të bëjmë atë.

271
00:23:14,140 --> 00:23:21,430
Përsëri, ne kemi mësuar se ne duhet të kemi disa lloj pointer përkohshëm.

272
00:23:21,430 --> 00:23:34,470
Le të zgjedhin të kenë një pikë të përkohshme për këtë djalë.

273
00:23:34,470 --> 00:23:39,640
Atëherë ne mund të kemi një pikë blu të përkohshme

274
00:23:39,640 --> 00:23:43,240
dhe pastaj pika të kuqe në blu.

275
00:23:43,240 --> 00:23:47,830
Arsyeja pse unë jam duke përdorur njerëzit këtu është, sepse ne të vërtetë duan të kujtoj

276
00:23:47,830 --> 00:23:53,180
mbajtur për njerëzit dhe duke u siguruar se ne kemi një lidhje të tyre

277
00:23:53,180 --> 00:23:57,590
para se të le të shkojë e një dore apo diçka të tillë.

278
00:24:05,630 --> 00:24:10,650
>> Tani që ne kemi një ndjenjë të listave të lidhura - si ne mund të krijojë një listë të lidhur

279
00:24:10,650 --> 00:24:15,090
dhe për të krijuar strukturat për atë përbërë nga përkufizimi tipit për një nyje

280
00:24:15,090 --> 00:24:19,060
dhe pastaj duke e bërë të sigurtë që ne kemi një tregues për kreun e lidhur atë listë -

281
00:24:19,060 --> 00:24:23,210
herë kemi se dhe ne e dimë se si të kaloj përmes një grup,

282
00:24:23,210 --> 00:24:28,200
hyrë elemente të ndryshme, ne e dimë se si për të futur dhe ne e dimë se si për të liruar ato,

283
00:24:28,200 --> 00:24:30,260
atëherë ne mund të merrni në gabim.

284
00:24:30,260 --> 00:24:38,150
Si zakonisht, ne kemi një seksion të pyetjeve që do të merrni ju përdorur për të operuar me listat e lidhura

285
00:24:38,150 --> 00:24:41,750
dhe struktura të ndryshme të tilla si radhët e gjata dhe oxhaqet.

286
00:24:41,750 --> 00:24:46,000
Atëherë ne mund të lëvizin në gabim.

287
00:24:46,000 --> 00:24:55,170
>> Gabim ka në kodin e shpërndarjes një çift të dosjeve të rëndësishme.

288
00:24:55,170 --> 00:24:58,850
Së pari vërejmë se kemi këtë Makefile këtu,

289
00:24:58,850 --> 00:25:03,040
të cilat ne nuk kemi hasur në të vërtetë më parë.

290
00:25:03,040 --> 00:25:10,090
Nëse keni shikuar brenda dosje pset5, ju do të vëreni që ju të keni një skedar. H,

291
00:25:10,090 --> 00:25:12,530
atëherë ju keni dy fotografi. c.

292
00:25:12,530 --> 00:25:18,920
Çfarë kjo nuk është Makefile para, ne vetëm do të bëjë dhe pastaj shtypni emrin programi

293
00:25:18,920 --> 00:25:25,550
dhe pastaj ne do të shohim të gjitha këto argumente dhe flamuj kaluar në të përpiluesit.

294
00:25:25,550 --> 00:25:30,580
Çfarë nuk është Makefile na lejon për të hartuar disa fotografi në të njëjtën kohë

295
00:25:30,580 --> 00:25:34,650
dhe të kalojë në flamujt që ne duam.

296
00:25:34,650 --> 00:25:41,300
Këtu ne shohim vetëm ka një file header këtu.

297
00:25:41,300 --> 00:25:43,730
Pastaj ne fakt kemi dy fotografi burim.

298
00:25:43,730 --> 00:25:47,520
Ne kemi Shkruaj një fjalë dhe dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Ju jeni të mirëpritur për të redaktuar Makefile nëse ju dëshironi.

300
00:25:54,560 --> 00:26:03,310
Vini re se në qoftë se ju shkruani këtu pastër, atëherë ajo që bën është në të vërtetë i heq asgjë

301
00:26:03,310 --> 00:26:06,340
që është bërthamë.

302
00:26:06,340 --> 00:26:09,190
Në qoftë se ju mori një faj segmentimit, në thelb ju merrni një hale thelbësore.

303
00:26:09,190 --> 00:26:13,260
Pra, kjo fotografi e shëmtuar pak do të shfaqet në directory tuaj quajtur thelbësore.

304
00:26:13,260 --> 00:26:16,310
Ju do të dëshironi të hiqni atë për ta bërë atë të pastër.

305
00:26:16,310 --> 00:26:20,940
Ajo heq ndonjë fotografi exe dhe. Fotografi o.

306
00:26:27,900 --> 00:26:30,220
>> Le të marrin një vështrim në dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Kjo thotë se ajo deklaron funksionalitetin e një fjalor të.

308
00:26:34,410 --> 00:26:39,530
Ne kemi një gjatësi maksimale për çdo fjalë në fjalor.

309
00:26:39,530 --> 00:26:45,130
Ne themi se kjo do të jetë fjala më e gjatë të jetë e mundur. Kjo është e gjatësi 45.

310
00:26:45,130 --> 00:26:48,900
Pra, ne nuk do të ketë ndonjë fjalë që tejkalojnë atë gjatësi.

311
00:26:48,900 --> 00:26:50,980
Këtu ne vetëm kemi prototypes funksion.

312
00:26:50,980 --> 00:26:55,290
Ne nuk kemi zbatimin aktual, sepse kjo është ajo që ne do të jetë bërë për këtë pset.

313
00:26:55,290 --> 00:26:59,940
Por ajo që e bën këtë është që ne jemi që kanë të bëjnë me fotografi të mëdha këtu

314
00:26:59,940 --> 00:27:06,650
dhe funksionalitetin në një shkallë më të madhe, është e dobishme që të ketë një skedar. h

315
00:27:06,650 --> 00:27:11,290
kështu që dikush tjetër lexuar ose duke përdorur kodin tuaj mund të kuptojnë se çfarë po ndodh.

316
00:27:11,290 --> 00:27:17,910
Dhe ndoshta ata duan për të zbatuar përpiqet në qoftë se ju e bëri tabelat hash apo anasjelltas.

317
00:27:17,910 --> 00:27:21,850
Atëherë ata do të thonë funksionin tim ngarkesës,

318
00:27:21,850 --> 00:27:26,950
implementimi aktual do të ndryshojnë, por kjo nuk do të ndryshojë prototip.

319
00:27:26,950 --> 00:27:33,280
Këtu kemi të kontrolluar, e cila kthehet e vërtetë në qoftë se një fjalë e dhënë është në fjalor.

320
00:27:33,280 --> 00:27:39,800
Pastaj kemi ngarkesë, e cila në thelb merr në një skedar fjalor

321
00:27:39,800 --> 00:27:44,360
dhe pastaj ngarkesa e saj në disa strukturën e të dhënave.

322
00:27:44,360 --> 00:27:47,500
Ne kemi madhësi, e cila, kur të quhet, kthen madhësinë e fjalorit tuaj,

323
00:27:47,500 --> 00:27:50,310
sa fjalë janë ruajtur në të,

324
00:27:50,310 --> 00:27:54,390
dhe pastaj zbraz, e cila liron të gjithë kujtesës që ju mund të keni marrë

325
00:27:54,390 --> 00:27:57,900
duke bërë fjalorin tuaj.

326
00:28:01,070 --> 00:28:03,590
>> Le të marrin një vështrim në dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Ne shohim se kjo duket shumë e ngjashme me dictionary.h, përveç tani ajo vetëm ka të gjitha këto Shihni Tërë në të.

328
00:28:10,490 --> 00:28:16,980
Dhe kështu kjo është puna juaj. Përfundimisht, ju do të jetë i plotësuar me të gjitha Shkruaj një fjalë të këtij kodi.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, kur ekzekutohet, nuk është me të vërtetë do të bëjë asgjë,

330
00:28:21,540 --> 00:28:29,590
kështu që ne shikojmë drejt Shkruaj një fjalë për të parë zbatimin aktual të spell checker.

331
00:28:29,590 --> 00:28:32,060
Edhe pse ju nuk do të jeni të redaktimi ndonjë të këtij kodi,

332
00:28:32,060 --> 00:28:38,050
është e rëndësishme për të lexuar, të kuptojnë kur është quajtur ngarkesës, kur unë jam duke bërë thirrje kontroll,

333
00:28:38,050 --> 00:28:42,350
vetëm për të kuptuar, hartë atë jashtë, të shohim se si funksion punon.

334
00:28:42,350 --> 00:28:49,860
Ne e shohim se ajo është kontrolluar për përdorimin korrekt.

335
00:28:49,860 --> 00:28:55,200
Në thelb, kur dikush shkon speller, kjo tregon se kjo është fakultative

336
00:28:55,200 --> 00:29:00,950
që ata të kalojnë në një skedar fjalor, sepse nuk do të jetë një fjalor parazgjedhur file.

337
00:29:00,950 --> 00:29:05,410
Dhe pastaj ata duhet të kalojnë në tekst të jetë spell-kontrolluar.

338
00:29:05,410 --> 00:29:11,410
merret rusage me kohë, sepse një pjesë e kësaj pset të cilat ne do të merremi me vone

339
00:29:11,410 --> 00:29:14,790
nuk është vetëm marrjen e një funksionimi spell-checker pune

340
00:29:14,790 --> 00:29:17,190
por në fakt të gjetur atë të jetë i shpejtë.

341
00:29:17,190 --> 00:29:22,040
Dhe kështu, atëherë kjo është ajo ku rusage do të vijnë in

342
00:29:22,040 --> 00:29:28,740
Këtu, ne shih thirrjen e parë për të njërit prej dosjeve tanë dictionary.c, e cila është ngarkesës.

343
00:29:28,740 --> 00:29:34,720
Load kthehet e vërtetë apo e rreme - e vërtetë mbi të suksesit, të rreme mbi dështimit.

344
00:29:34,720 --> 00:29:41,400
Pra, në qoftë se fjalori nuk është i ngarkuar si duhet, atëherë Shkruaj një fjalë do të kthehet 1 dhe u largua.

345
00:29:41,400 --> 00:29:47,920
Por në qoftë se bën ngarkesës siç duhet, atëherë ai do të vazhdojë.

346
00:29:47,920 --> 00:29:50,740
Ne vazhdojmë, dhe ne shohim disa fotografi I / O këtu,

347
00:29:50,740 --> 00:29:56,210
ku ajo do të jetë që kanë të bëjnë me hapjen e file teksti.

348
00:29:56,210 --> 00:30:04,640
Ja, ajo që ky nuk është spell-kontrollon çdo fjalë të vetme në tekst.

349
00:30:04,640 --> 00:30:09,270
Pra, çfarë është duke bërë Shkruaj një fjalë të drejtë këtu është iterating mbi secilën nga fjalët në skedar teksti

350
00:30:09,270 --> 00:30:12,790
dhe pastaj kontrollin e tyre në fjalor.

351
00:30:24,680 --> 00:30:32,350
Këtu, ne kemi një Boolean misspelled që do të shohim nëse kontrolloni kthen vërtetë apo jo.

352
00:30:32,350 --> 00:30:37,110
Nëse fjala është në të vërtetë në fjalor, atëherë kontrolloni do të kthehet vërtetë.

353
00:30:37,110 --> 00:30:39,760
Kjo do të thotë se fjala nuk është misspelled.

354
00:30:39,760 --> 00:30:45,330
Misspelled Pra, do të jenë të rreme, dhe kjo është arsyeja pse ne kemi zhurmë atje, tregues.

355
00:30:45,330 --> 00:30:56,320
Ne mbajmë në vazhdim e sipër, dhe pastaj ajo mban gjurmët e sa fjalë misspelled

356
00:30:56,320 --> 00:30:58,910
nuk janë në dosje.

357
00:30:58,910 --> 00:31:03,870
Ajo vazhdon në dhe mbyllet file.

358
00:31:03,870 --> 00:31:09,250
Atëherë këtu, ajo raporton se shumë fjalë misspelled keni pasur.

359
00:31:09,250 --> 00:31:12,680
Ai llogarit se sa kohë u desh për të ngarkuar fjalor,

360
00:31:12,680 --> 00:31:15,080
se sa kohë u desh për të kontrolluar atë,

361
00:31:15,080 --> 00:31:18,510
se sa kohë u desh për të llogaritur madhësinë,

362
00:31:18,510 --> 00:31:21,260
cila, siç ne do të shkojnë në, duhet të jenë shumë të vogla,

363
00:31:21,260 --> 00:31:25,390
dhe pastaj se sa kohë u desh për të shkarkoj fjalorin.

364
00:31:25,390 --> 00:31:27,700
Këtu ne shohim lart thirrjen për shkarkoj këtu.

365
00:31:27,700 --> 00:31:52,690
Nëse ne kontrolloni për madhësinë këtu,

366
00:31:52,690 --> 00:31:59,050
atëherë shohim se këtu është thirrja në madhësi ku ajo përcakton madhësinë e fjalorit.

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

368
00:32:07,100 --> 00:32:10,920
>> Detyra jonë për këtë pset është për të zbatuar barrën, e cila do të ngarkesës fjalorin

369
00:32:10,920 --> 00:32:15,480
Të dhënat Struktura - cilado që ju zgjidhni, të jetë ajo një tabelë hash apo një provoni -

370
00:32:15,480 --> 00:32:18,810
me fjalë nga file fjalor.

371
00:32:18,810 --> 00:32:25,290
Atëherë ju keni madhësi, e cila do të kthehet në numrin e fjalëve në fjalor.

372
00:32:25,290 --> 00:32:29,860
Dhe në qoftë se ju të zbatojë ngarkesës në një mënyrë të zgjuar, atëherë madhësia duhet të jetë goxha e lehtë.

373
00:32:29,860 --> 00:32:33,860
Atëherë ju keni kontrolluar, e cila do të kontrolloni nëse një fjalë e dhënë është në fjalor.

374
00:32:33,860 --> 00:32:38,690
Pra Shkruaj një fjalë kalon në një varg, dhe pastaj ju duhet të kontrolloni nëse string se

375
00:32:38,690 --> 00:32:41,610
gjendet brenda fjalorit tuaj.

376
00:32:41,610 --> 00:32:46,750
Vini re se ne në përgjithësi kanë fjalorë standarde,

377
00:32:46,750 --> 00:32:53,020
por në këtë pset, në thelb çdo fjalor kaluar në në çdo gjuhë.

378
00:32:53,020 --> 00:32:57,040
Pra, ne nuk mund të supozojmë se fjala është brenda.

379
00:32:57,040 --> 00:33:03,090
Foobar fjalë mund të përcaktohet në një fjalor të caktuar që ne të kalojë in

380
00:33:03,090 --> 00:33:07,920
Dhe pastaj ne kemi zbraz, e cila çliron një fjalor nga memoria.

381
00:33:07,920 --> 00:33:11,930
>> Së pari, unë do të doja të shkoj mbi metodën hash tryezë

382
00:33:11,930 --> 00:33:14,630
rreth asaj se si ne mund të zbatojë të gjitha këto katër funksioneve,

383
00:33:14,630 --> 00:33:18,650
dhe pastaj unë do të shkoj mbi përpiqet metodë, si ne zbatojë ato katër funksionet,

384
00:33:18,650 --> 00:33:22,720
dhe në fund të bisedës në lidhje me disa këshilla të përgjithshme, kur ju jeni bërë pset

385
00:33:22,720 --> 00:33:27,870
dhe gjithashtu se si ju mund të jetë në gjendje të përdorin Shprehje të kontrolloni për rrjedhjet e kujtesës.

386
00:33:27,870 --> 00:33:30,550
>> Le të marrë në tryezë metodë hash.

387
00:33:30,550 --> 00:33:35,910
Një tabelë hash përbëhet nga një listë e kova.

388
00:33:35,910 --> 00:33:43,010
Çdo vlerë, çdo fjalë, do të shkojë në një nga këto kova.

389
00:33:43,010 --> 00:33:53,200
Një tabelë hash në mënyrë ideale të barabartë shpërndan të gjitha këtyre vlerave që ju jeni duke kaluar në

390
00:33:53,200 --> 00:33:57,160
dhe pastaj populates ato në kovë tillë që çdo kovë

391
00:33:57,160 --> 00:34:02,000
ka rreth një numër të barabartë të vlerave në të.

392
00:34:02,000 --> 00:34:09,630
Struktura për një tryezë hash, ne kemi një grup të listave të lidhura.

393
00:34:09,630 --> 00:34:17,900
Çfarë bëjmë ne është kur ne të kalojë në një vlerë, ku ne kontrolloni se vlera duhet të takojnë,

394
00:34:17,900 --> 00:34:23,840
e cila kovë ajo i takon, dhe pastaj vendin e saj në listën e lidhur lidhur me atë kovë.

395
00:34:23,840 --> 00:34:28,199
Ja, ajo që unë kam është një funksion hash.

396
00:34:28,199 --> 00:34:31,320
Kjo është një tabelë hash int.

397
00:34:31,320 --> 00:34:38,540
Pra, për kovë e parë, çdo integers nën 10 shkojnë në kovë e parë.

398
00:34:38,540 --> 00:34:42,190
Çdo integers mbi 10 por nën 20 shkoni në të dytë,

399
00:34:42,190 --> 00:34:44,179
dhe pastaj kështu me radhë e kështu me radhë.

400
00:34:44,179 --> 00:34:52,370
Për mua, çdo kovë është përfaqësuar këto numra.

401
00:34:52,370 --> 00:34:59,850
Megjithatë, thonë se unë do të kalojë në 50, për shembull.

402
00:34:59,850 --> 00:35:07,490
Duket sikur tre e parë përmban një gamë të dhjetë numrave.

403
00:35:07,490 --> 00:35:12,570
Por unë dua që të lejojë tryezën time hash për të marrë në çdo lloj të integers,

404
00:35:12,570 --> 00:35:19,860
kështu atëherë unë do të duhet për të filtruar nga të gjitha numrat e mësipërme 30 në kovë fundit.

405
00:35:19,860 --> 00:35:26,660
Dhe kështu atëherë kjo do të rezultojë në një lloj të tabelës hash çekuilibruar.

406
00:35:31,330 --> 00:35:35,640
Për të përsëritur, një tavolinë hash është vetëm një grup i kova

407
00:35:35,640 --> 00:35:38,590
ku çdo kovë është një listë e lidhur.

408
00:35:38,590 --> 00:35:43,730
Dhe kështu për të përcaktuar ku çdo vlerë shkon, e cila kovë ajo shkon në,

409
00:35:43,730 --> 00:35:46,260
ju jeni do të duan atë që quhet një funksion hash

410
00:35:46,260 --> 00:35:55,010
që merr një vlerë dhe pastaj thotë se kjo vlerë i korrespondon një kovë të caktuar.

411
00:35:55,010 --> 00:36:00,970
Pra, deri lart në këtë shembull, funksioni im mori hash çdo vlerë.

412
00:36:00,970 --> 00:36:03,020
Të kontrolluar nëse ajo ishte më pak se 10.

413
00:36:03,020 --> 00:36:05,360
Në qoftë se kjo ishte, ajo do të vënë atë në kovë e parë.

414
00:36:05,360 --> 00:36:08,910
Ajo kontrollon nëse kjo është më pak se 20, e vë atë në të dytë, nëse vërtetë,

415
00:36:08,910 --> 00:36:12,880
kontrollon nëse ajo është më pak se 30, dhe pastaj e vë atë në kovë e tretë,

416
00:36:12,880 --> 00:36:16,990
dhe pastaj të gjithë të tjerët sapo bie në kovë katërt.

417
00:36:16,990 --> 00:36:20,110
Pra, kur ju keni një vlerë, funksioni juaj hash

418
00:36:20,110 --> 00:36:25,420
do të zhvillohet këtë vlerë në kovë duhur.

419
00:36:25,420 --> 00:36:32,430
Funksioni hash në thelb duhet të dini se sa kova keni.

420
00:36:32,430 --> 00:36:37,960
Madhësia hash tuaj tavolinë, numri i kova keni,

421
00:36:37,960 --> 00:36:41,190
që do të jetë një numër fiks që është deri te ju, për ju që të vendosë,

422
00:36:41,190 --> 00:36:43,590
por ajo do të jetë një numër fiks.

423
00:36:43,590 --> 00:36:51,840
Pra, funksioni juaj do të hash duke u mbështetur në atë të përcaktuar se cila kovë çdo kyç shkon në

424
00:36:51,840 --> 00:36:54,450
tillë që është e shpërndarë në mënyrë të barabartë.

425
00:36:56,150 --> 00:37:03,820
Ngjashëm me implementimin tonë të listave të lidhura, tani çdo nyjë në tabelën hash

426
00:37:03,820 --> 00:37:07,000
është në të vërtetë do të ketë një lloj char.

427
00:37:07,000 --> 00:37:14,340
Pra, ne kemi një rrjet të char quajtur Fjala dhe pastaj një tjetër tregues për nyjen e ardhshëm,

428
00:37:14,340 --> 00:37:19,010
gjë që e bën kuptim sepse kjo do të jetë një listë e lidhur.

429
00:37:19,010 --> 00:37:24,350
Mos harroni kur ne kishim listat e lidhur, kam bërë një nyje * quajtur kreu

430
00:37:24,350 --> 00:37:31,060
që ishte vënë në nyjen e parë në listën e lidhur.

431
00:37:31,060 --> 00:37:34,020
Por, për tryezën tonë hash, sepse ne kemi listat e shumta të lidhura,

432
00:37:34,020 --> 00:37:37,520
ajo që ne duam është që ne duam tabelë hash ynë të jetë si, "Çfarë është një kovë?"

433
00:37:37,520 --> 00:37:43,340
Një kovë është vetëm një listë e pointers nyjeve,

434
00:37:43,340 --> 00:37:50,620
dhe kështu çdo element në kovë në fakt është duke treguar përkatëse listën e saj lidhur.

435
00:37:56,180 --> 00:38:01,520
Që të kthehen në këtë skematike, ju shihni se kova vetë janë shigjeta,

436
00:38:01,520 --> 00:38:06,980
jo nyjet aktuale.

437
00:38:11,680 --> 00:38:16,420
Një nga funksionet thelbësore pronë hash është se ata janë determinist.

438
00:38:16,420 --> 00:38:19,440
Kjo do të thotë se sa herë që ju të hash numri 2,

439
00:38:19,440 --> 00:38:22,270
ajo gjithmonë duhet të kthejë kovë njëjtë.

440
00:38:22,270 --> 00:38:26,440
Çdo vlerë e vetme që shkon në funksion hash, nëse përsëritet,

441
00:38:26,440 --> 00:38:29,690
ka për të marrë indeksin e njëjtë.

442
00:38:29,690 --> 00:38:34,210
Pra, funksioni juaj hash kthen indeksin e vektorit

443
00:38:34,210 --> 00:38:38,530
se ku vlera takon.

444
00:38:38,530 --> 00:38:41,790
Siç e kam përmendur më parë, numri i kova është fikse,

445
00:38:41,790 --> 00:38:49,630
dhe kështu indeksi tuaj që ju të kthehen duhet të jetë më pak se numri i kova

446
00:38:49,630 --> 00:38:52,680
por më e madhe se 0.

447
00:38:52,680 --> 00:39:00,780
Arsyeja pse ne kemi funksionet hash në vend të vetëm një listë të vetme lidhur

448
00:39:00,780 --> 00:39:09,290
ose një grup i vetëm është se ne duam të jetë në gjendje të hidhen në një seksion të caktuar më të lehtë

449
00:39:09,290 --> 00:39:11,720
në qoftë se ne e dimë karakteristikën e një vlerë -

450
00:39:11,720 --> 00:39:14,760
në vend që të kërkoni nëpër tërë fjalor të tërë,

451
00:39:14,760 --> 00:39:18,320
qenë në gjendje të hidhen në një seksion të caktuar të saj.

452
00:39:19,880 --> 00:39:24,440
Funksion hash juaj duhet të marrë parasysh që në mënyrë ideale,

453
00:39:24,440 --> 00:39:28,980
çdo kovë ka përafërsisht numrin e njëjtë të çelësat.

454
00:39:28,980 --> 00:39:35,040
Që nga tabela hash është një seri e listave të lidhura,

455
00:39:35,040 --> 00:39:38,480
atëherë listat lidhura vetë do të ketë më shumë se një nyje.

456
00:39:38,480 --> 00:39:43,210
Në shembullin e mëparshëm, dy numra të ndryshëm, edhe pse ata nuk ishin të barabartë,

457
00:39:43,210 --> 00:39:46,950
kur sheshuar, do të kthehen indeksin e njëjtë.

458
00:39:46,950 --> 00:39:53,620
Pra, kur ju jeni që kanë të bëjnë me fjalë, një fjalë kur sheshuar

459
00:39:53,620 --> 00:39:57,450
do të jetë vlera e hash njëjtë si një tjetër fjalë.

460
00:39:57,450 --> 00:40:04,140
Kjo është ajo që ne e quajmë një përplasje, kur ne kemi një nyje që, kur të sheshuar,

461
00:40:04,140 --> 00:40:09,610
lista e lidhur në atë kovë nuk është bosh.

462
00:40:09,610 --> 00:40:14,180
Teknika që ne e quajmë nuk është lineare probing,

463
00:40:14,180 --> 00:40:22,550
ku ju shkoni në listën e lidhur dhe pastaj të gjeni se ku ju doni të futur atë nyje

464
00:40:22,550 --> 00:40:25,520
sepse ju keni një përplasje.

465
00:40:25,520 --> 00:40:28,070
Ju mund të shihni se nuk mund të jetë një tregti-off këtu, apo jo?

466
00:40:28,070 --> 00:40:33,760
Nëse ju keni një tabelë shumë të vogël hash, një numër shumë i vogël i kova,

467
00:40:33,760 --> 00:40:36,380
atëherë ju jeni do të ketë një shumë e perplasjeve.

468
00:40:36,380 --> 00:40:40,460
Por pastaj, nëse ju bëni një tabelë shumë të madhe hash,

469
00:40:40,460 --> 00:40:44,110
ju jeni me siguri do të minimizuar goditjet,

470
00:40:44,110 --> 00:40:47,170
por ajo do të jetë një shumë të madhe të dhënave struktura.

471
00:40:47,170 --> 00:40:49,310
Nuk do të jetë tregtisë humbura me këtë.

472
00:40:49,310 --> 00:40:51,310
Pra, kur ju jeni duke bërë pset tuaj, do të përpiqen për të luajtur rreth

473
00:40:51,310 --> 00:40:54,210
mes ndoshta bën një tabelë të vogël hash

474
00:40:54,210 --> 00:41:02,100
por pastaj duke e ditur se ajo do të marrë një pak më të gjatë për përshkim të elementeve të ndryshme

475
00:41:02,100 --> 00:41:04,270
e këtyre listave lidhura.

476
00:41:04,270 --> 00:41:09,500
>> Çfarë ngarkesës do të bëni është të iterate mbi çdo fjalë në fjalor.

477
00:41:09,500 --> 00:41:13,180
Ai kalon në një tregues për dosjen e fjalorit.

478
00:41:13,180 --> 00:41:18,050
Pra, ju jeni do të përfitojnë nga file I / O funksionet që ju zotëruar në pset4

479
00:41:18,050 --> 00:41:23,010
dhe iterate mbi çdo fjalë në fjalor.

480
00:41:23,010 --> 00:41:26,620
Ju dëshironi që çdo fjalë në fjalor për t'u bërë një nyje e re,

481
00:41:26,620 --> 00:41:32,730
dhe ju do të jeni në vendin e çdo një prej këtyre nyjeve në brendësi të strukturës së të dhënave tuaj të fjalorit.

482
00:41:32,730 --> 00:41:36,560
Kurdo që ju të merrni një fjalë të re, ju e dini se ajo do të bëhet një nyje.

483
00:41:36,560 --> 00:41:46,590
Kështu që ju mund të shkoni menjëherë dhe malloc një tregues nyje për çdo fjalë të re që ju keni.

484
00:41:46,590 --> 00:41:52,610
Këtu unë jam duke bërë thirrje new_node akrep time nyje dhe unë jam mallocing çfarë? Madhësinë e një nyje.

485
00:41:52,610 --> 00:41:59,190
Pastaj për të lexuar vargun aktual nga një skedar, sepse fjalori është ruajtur në të vërtetë

486
00:41:59,190 --> 00:42:03,340
nga një fjalë dhe pastaj një linjë të re, ajo që ne mund të përfitojnë nga

487
00:42:03,340 --> 00:42:06,520
është fscanf funksion,

488
00:42:06,520 --> 00:42:10,280
ku file është file fjalor që ne jemi duke kaluar në,

489
00:42:10,280 --> 00:42:18,900
kështu që ajo skanon skedarin për një varg dhe vende që string në argumentin e fundit.

490
00:42:18,900 --> 00:42:26,890
Nëse ju kujtohet përsëri në një nga leksionet, kur kemi shkuar mbi

491
00:42:26,890 --> 00:42:29,320
dhe lloji i peeled shtresa përsëri në bibliotekë CS50,

492
00:42:29,320 --> 00:42:33,430
ne pamë një zbatim të fscanf atje.

493
00:42:33,430 --> 00:42:37,700
Të kthehen në fscanf, ne kemi skedar që ne jemi duke lexuar nga,

494
00:42:37,700 --> 00:42:42,570
ne jemi duke kërkuar për një varg në atë dosje, dhe pastaj ne jemi vënë atë në

495
00:42:42,570 --> 00:42:48,340
këtu kam new_node-> fjalë, sepse new_node është një tregues nyje,

496
00:42:48,340 --> 00:42:50,380
jo një nyje e vërtetë.

497
00:42:50,380 --> 00:42:57,100
Pra, atëherë unë jam duke thënë new_node, unë dua të shkoj në nyje se është treguar

498
00:42:57,100 --> 00:43:01,190
dhe pastaj të caktojë atë vlerë të fjalës.

499
00:43:01,190 --> 00:43:08,540
Ne duam që të pastaj të marrë atë fjalë dhe futur atë në tabelën hash.

500
00:43:08,540 --> 00:43:13,750
Kuptojnë se kemi bërë new_node një tregues nyje

501
00:43:13,750 --> 00:43:18,230
sepse ne do të duan të dinë se çfarë adresa e asaj nyje është

502
00:43:18,230 --> 00:43:23,940
kur kemi futur atë në, sepse struktura e nyjeve vetë, e struct,

503
00:43:23,940 --> 00:43:26,380
është se ata kanë një tregues për një nyje të re.

504
00:43:26,380 --> 00:43:30,820
Pra, atëherë çfarë është adresa e kësaj nyje do të vinte për të?

505
00:43:30,820 --> 00:43:34,550
Kjo adresë do të jetë new_node.

506
00:43:34,550 --> 00:43:42,140
Bën që të ketë kuptim, pse ne jemi duke bërë një new_node * nyje në krahasim me një nyje?

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

508
00:43:45,700 --> 00:43:52,840
Ne kemi një fjalë. Kjo vlerë është new_node-> fjalë.

509
00:43:52,840 --> 00:43:55,970
Që përmban një fjalë nga fjalori që ne duam të dhëna.

510
00:43:55,970 --> 00:44:00,210
Kështu që ajo që ne duam të bëjmë është që ne duam të thirrur funksionin hash tonë në atë varg

511
00:44:00,210 --> 00:44:03,780
sepse funksioni ynë hash merr në një varg dhe pastaj kthehet na një numër të plotë,

512
00:44:03,780 --> 00:44:12,090
se ku numër i plotë është indeksi ku hashtable në atë indeks paraqet atë kovë.

513
00:44:12,090 --> 00:44:18,260
Ne duam të marrin atë indeks dhe pastaj të shkoni në atë indeksit të tabelës hash

514
00:44:18,260 --> 00:44:26,960
dhe pastaj të përdorin këtë listë e lidhur për të futur në nyjen new_node.

515
00:44:26,960 --> 00:44:31,950
Mos harroni se megjithatë ju vendosni për të futur nyje tuaj,

516
00:44:31,950 --> 00:44:34,370
nëse kjo është në mes, nëse ju doni të zgjidhur atë

517
00:44:34,370 --> 00:44:39,650
ose në fillim ose në fund të fundit, vetëm sigurohuni që nyja juaj e fundit gjithmonë tregon NULL

518
00:44:39,650 --> 00:44:46,730
sepse kjo është mënyra e vetme që ne e dimë se ku elementi i fundit i listës sonë është e lidhur.

519
00:44:50,790 --> 00:44:59,710
>> Nëse madhësia është një numër të plotë që përfaqëson numrin e fjalëve në një fjalor,

520
00:44:59,710 --> 00:45:03,060
atëherë një mënyrë për të bërë këtë është se sa herë madhësia quhet

521
00:45:03,060 --> 00:45:05,840
ne do të shkojmë nëpër çdo element në tabelën hash tonë

522
00:45:05,840 --> 00:45:09,410
dhe pastaj iterate nëpër çdo listë e lidhur brenda tabelës hash

523
00:45:09,410 --> 00:45:13,770
dhe pastaj të llogaritur gjatësinë e që, duke u rritur me 1 nga 1 counter tonë.

524
00:45:13,770 --> 00:45:16,580
Por çdo herë që madhësia quhet, që do të marrë një kohë të gjatë

525
00:45:16,580 --> 00:45:22,120
sepse ne jemi duke shkuar për jetë linear probing çdo listë të vetme lidhur.

526
00:45:22,120 --> 00:45:30,530
Në vend të kësaj, ajo do të jetë shumë më e lehtë në qoftë se ju mbajnë gjurmët e sa fjalë janë miratuar in

527
00:45:30,530 --> 00:45:36,330
Pra, atëherë në qoftë se ju të përfshijë një counter brenda funksionit tuaj ngarkesës

528
00:45:36,330 --> 00:45:42,430
se si përditësime të nevojshme, atëherë kundër, nëse keni vendosur atë në një ndryshore globale,

529
00:45:42,430 --> 00:45:44,930
do të jetë në gjendje që do të arrihen nga madhësia.

530
00:45:44,930 --> 00:45:51,450
Pra, çfarë madhësia thjesht mund të bëni është në një linjë, vetëm kthejë vlerën kundër,

531
00:45:51,450 --> 00:45:55,500
madhësia e fjalorit, të cilat ju tashmë trajtohen në ngarkesë.

532
00:45:55,500 --> 00:46:05,190
Kjo është ajo që unë do të thotë kur kam thënë në qoftë se ju të zbatuar ngarkesës në një mënyrë të dobishme,

533
00:46:05,190 --> 00:46:08,540
atëherë madhësia do të jetë goxha e lehtë.

534
00:46:08,540 --> 00:46:11,350
>> Kështu që tani ne kemi marrë për të kontrolluar.

535
00:46:11,350 --> 00:46:15,960
Tani ne jemi që kanë të bëjnë me fjalë nga file teksti input,

536
00:46:15,960 --> 00:46:19,910
dhe kështu që ne jemi duke shkuar për të kontrolluar nëse të gjitha ato fjalë hyrëse

537
00:46:19,910 --> 00:46:22,520
janë në fakt në fjalor apo jo.

538
00:46:22,520 --> 00:46:26,520
Ngjashëm me Scramble, ne duam për të lejuar për ftohtësi rast.

539
00:46:26,520 --> 00:46:32,110
Ju dëshironi të bëni të sigurtë që të gjitha fjalët kaluar në, edhe pse ata janë rasti të përziera,

540
00:46:32,110 --> 00:46:37,840
kur thirri me krahasoni string, janë ekuivalente.

541
00:46:37,840 --> 00:46:42,450
Fjalët në fotografi tekst dictionary të vërtetë janë të gjitha të vogla.

542
00:46:42,450 --> 00:46:49,280
Një tjetër gjë është se ju mund të supozojmë se çdo fjalë kaloi në, çdo varg,

543
00:46:49,280 --> 00:46:53,200
do të jetë ose alfabetike ose përmbajnë apostrofat.

544
00:46:53,200 --> 00:46:58,010
Apostrofat do të jenë të vlefshme fjalë në fjalorin tonë.

545
00:46:58,010 --> 00:47:06,470
Pra, nëse ju keni një fjalë me apostrof S, kjo është një fjalë aktual legjitim në fjalorin tuaj

546
00:47:06,470 --> 00:47:11,650
që do të jetë një nga nyjet në tryezën tuaj hash.

547
00:47:13,470 --> 00:47:18,350
Kontrolloni në qoftë se operon me fjalën ekziston, atëherë ai e mori të jetë në tryezën tonë hash.

548
00:47:18,350 --> 00:47:22,210
Nëse fjala është në fjalor, atëherë të gjitha fjalët në fjalor janë në tabelën hash,

549
00:47:22,210 --> 00:47:26,560
kështu që le të shohim për këtë fjalë në tabelën hash.

550
00:47:26,560 --> 00:47:29,250
Ne e dimë se që kemi zbatuar funksionin hash tonë

551
00:47:29,250 --> 00:47:38,420
tillë që çdo fjalë është unik sheshuar gjithmonë të njëjtën vlerë,

552
00:47:38,420 --> 00:47:43,340
atëherë ne e dimë që në vend të kërkimit përmes tabelës tërë tonë të gjithë hash,

553
00:47:43,340 --> 00:47:48,310
ne fakt mund të gjeni listën e të lidhur që kjo fjalë duhet përkasin.

554
00:47:48,310 --> 00:47:51,850
Nëse do të ishte në fjalor, atëherë ajo do të jetë në atë kovë.

555
00:47:51,850 --> 00:47:57,140
Çfarë mund të bëjmë, në qoftë se fjala është emri i vargut jonë kaloi në,

556
00:47:57,140 --> 00:48:01,560
ne vetëm mund të hash se fjala dhe të kërkoni në listën lidhur

557
00:48:01,560 --> 00:48:06,410
në vlerën e hashtable [hash (fjala)].

558
00:48:06,410 --> 00:48:12,410
Nga atje, ajo që ne mund të bëjmë është që ne kemi një mesin e vogël e nyjeve për të kërkuar për këtë fjalë,

559
00:48:12,410 --> 00:48:16,770
dhe kështu që ne mund të kaloj listën e të lidhur, duke përdorur një shembull nga më herët në walkthrough,

560
00:48:16,770 --> 00:48:24,110
dhe pastaj thirrje string krahasohet me fjalën kudo kursori është treguar për të,

561
00:48:24,110 --> 00:48:28,430
se fjala, dhe të shohim nëse ato krahasohen.

562
00:48:30,280 --> 00:48:35,110
Varësi në mënyrë që ju të organizojë funksionin tuaj hash,

563
00:48:35,110 --> 00:48:39,260
në qoftë se ajo është renditur, ju mund të jetë në gjendje të kthehen rreme pak më herët,

564
00:48:39,260 --> 00:48:43,440
por në qoftë se është unsorted, atëherë ju doni të vazhdoni traversing përmes listën tuaj lidhur

565
00:48:43,440 --> 00:48:46,480
derisa ju të gjeni elementin e fundit të listës.

566
00:48:46,480 --> 00:48:53,320
Dhe në qoftë se ju ende nuk kanë gjetur fjalën nga koha që ju keni arritur fundin e listës së lidhur,

567
00:48:53,320 --> 00:48:56,890
që do të thotë se fjala juaj nuk ekziston në fjalor,

568
00:48:56,890 --> 00:48:59,410
dhe kështu se fjala është e pavlefshme,

569
00:48:59,410 --> 00:49:02,730
dhe kontrolloni duhet të kthehen rreme.

570
00:49:02,730 --> 00:49:09,530
>> Tani kemi ardhur për të shkarkoj, ku ne duam të liruar të gjitha nyjet që kemi malloc'd,

571
00:49:09,530 --> 00:49:14,050
në mënyrë të lirë të gjitha nyjet e brenda tryezën tonë hash.

572
00:49:14,050 --> 00:49:20,270
Ne do të duan të iterate mbi të gjitha listave të lidhura dhe të lira të gjitha nyjet në këtë.

573
00:49:20,270 --> 00:49:29,350
Nëse ju shikoni lart në walkthrough për shembull ku kemi liruar një listë të lidhur,

574
00:49:29,350 --> 00:49:35,140
atëherë ju do të dëshironi të përsëritur këtë proces për çdo element në tabelë hash.

575
00:49:35,140 --> 00:49:37,780
Dhe unë do të shkoj për këtë në fund të walkthrough,

576
00:49:37,780 --> 00:49:46,600
por Shprehje është një mjet ku ju mund të shihni nëse ju keni liruar e duhur

577
00:49:46,600 --> 00:49:53,600
çdo nyje që e keni malloc'd ose ndonjë gjë tjetër që ju keni malloc'd, çdo tregues tjetër.

578
00:49:55,140 --> 00:50:00,530
Pra, kjo është tabela hash, ku ne kemi një numër i caktuar i kova

579
00:50:00,530 --> 00:50:09,220
dhe një funksion hash që do të marrë një vlerë dhe pastaj të caktojë se vlera në një kovë të caktuar.

580
00:50:09,220 --> 00:50:13,340
>> Tani kemi ardhur për të përpiqet.

581
00:50:13,340 --> 00:50:18,750
Mundohet lloj të duken si kjo, dhe unë gjithashtu do të tërheqë nga një shembull.

582
00:50:18,750 --> 00:50:25,630
Në thelb, ju keni një koleksion të tërë të letrave të mundshme,

583
00:50:25,630 --> 00:50:29,210
dhe pastaj kur ju jeni ndërtimin e një fjalë,

584
00:50:29,210 --> 00:50:36,490
se letra mund të jetë i lidhur për një fjalor me një gamë të gjerë të mundësive.

585
00:50:36,490 --> 00:50:40,840
Disa fjalë të filluar me C, por pastaj të vazhdojë me A,

586
00:50:40,840 --> 00:50:42,960
por të tjerët vazhdojnë me O, për shembull.

587
00:50:42,960 --> 00:50:51,090
Një trie është një mënyrë për të visualizing të gjitha kombinimet e mundshme të këtyre fjalëve.

588
00:50:51,090 --> 00:50:59,070
Një trie do të mbajnë gjurmët e sekuencën e shkronjave që përbëjnë fjalët,

589
00:50:59,070 --> 00:51:08,280
bronkial jashtë kur është e nevojshme, kur një letër mund të pasohet nga një shumë të letrave,

590
00:51:08,280 --> 00:51:16,630
dhe në fund të tregojë në çdo moment nëse kjo fjalë është e vlefshme apo jo

591
00:51:16,630 --> 00:51:30,120
sepse në qoftë se ju jeni mat drejtshkrimi fjalë, MA unë nuk mendoj se është një fjalë e vlefshme, por MAT është.

592
00:51:30,120 --> 00:51:37,820
Dhe kështu në trie tuaj, ajo do të tregojë se pas MAT që është në fakt një fjalë të vlefshme.

593
00:51:41,790 --> 00:51:48,590
Çdo nyje në trie tonë është në të vërtetë do të përmbajë një sërë pointers nyjeve,

594
00:51:48,590 --> 00:51:52,970
dhe ne do të kemi, në mënyrë specifike, 27 të këtyre pointers nyjeve,

595
00:51:52,970 --> 00:52:00,550
një për çdo letër në alfabetin si dhe karakterin apostrof.

596
00:52:00,550 --> 00:52:10,450
Çdo element në këtë grup është vetë do të tregojnë për një tjetër nyje.

597
00:52:10,450 --> 00:52:14,020
Pra, në qoftë se është nyje NULL, nëse nuk ka asgjë pas kësaj,

598
00:52:14,020 --> 00:52:20,550
atëherë ne e dimë se nuk ka letra të mëtejshme në atë sekuencë fjalë.

599
00:52:20,550 --> 00:52:26,950
Por në qoftë se nuk është nyja NULL, që do të thotë se ka më shumë letra në atë rend letër.

600
00:52:26,950 --> 00:52:32,160
Dhe pastaj më tepër, çdo nyje tregon nëse është personazhi i fundit i një fjalë apo jo.

601
00:52:38,110 --> 00:52:43,170
>> Le të shkojë në një shembull të një trie.

602
00:52:50,500 --> 00:52:58,340
Së pari unë kam hapësirë ​​për 27 nyje në këtë grup.

603
00:52:58,340 --> 00:53:03,200
Nëse kam bar fjalën -

604
00:53:13,310 --> 00:53:15,370
Nëse kam bar fjalën dhe unë dua për të futur atë në,

605
00:53:15,370 --> 00:53:22,700
Letra e parë është B, kështu që nëse trie ime është e zbrazët,

606
00:53:22,700 --> 00:53:29,910
B është letra e dytë e alfabetit, kështu që unë jam duke shkuar për të zgjedhur për të vënë këtë këtu në këtë indeks.

607
00:53:29,910 --> 00:53:33,450
Unë jam duke shkuar të ketë B këtu.

608
00:53:33,450 --> 00:53:42,400
B do të jetë një nyje që tregon për një grup të të gjitha personazhet e mundshme

609
00:53:42,400 --> 00:53:45,870
që mund të ndjekin pas letrës B.

610
00:53:45,870 --> 00:53:57,610
Në këtë rast, unë jam që kanë të bëjnë me BAR fjalë, kështu që një do të shkojnë këtu.

611
00:54:02,000 --> 00:54:08,990
Pas një, unë kam letrën R, kështu që pas një pikë tani në kombinimin e vet,

612
00:54:08,990 --> 00:54:15,120
dhe pastaj R do të jetë këtu.

613
00:54:15,120 --> 00:54:22,470
BAR është një fjalë të plotë, kështu që atëherë unë jam duke shkuar të ketë pikë në një tjetër nyje R

614
00:54:22,470 --> 00:54:33,990
që thotë se kjo fjalë është e vlefshme.

615
00:54:36,010 --> 00:54:40,970
Kjo nyjë është gjithashtu do të ketë një rrjet të nyjeve,

616
00:54:40,970 --> 00:54:45,260
por ato mund të jenë NULL.

617
00:54:45,260 --> 00:54:49,080
Por në thelb, ajo mund të vazhdojë kështu.

618
00:54:49,080 --> 00:54:54,250
Kjo do të bëhet pak më e qartë kur të shkojmë në një shembull tjetër,

619
00:54:54,250 --> 00:54:56,780
kështu që vetëm të kesh durim me mua atje.

620
00:54:56,780 --> 00:55:02,050
Tani ne kemi bar brenda e fjalorit tonë.

621
00:55:02,050 --> 00:55:05,980
Tani thonë se ne kemi Baz fjalë.

622
00:55:05,980 --> 00:55:12,630
Ne fillim me B, dhe ne tashmë kemi B si një nga letrat që në fjalorin tonë.

623
00:55:12,630 --> 00:55:15,170
Kjo është pasuar me A. Ne kemi një tashmë.

624
00:55:15,170 --> 00:55:19,250
Por pastaj në vend të kësaj, ne kemi pas z.

625
00:55:19,250 --> 00:55:25,490
Pra, atëherë një element në grup tonë do të jetë Z,

626
00:55:25,490 --> 00:55:30,810
dhe kështu pastaj se dikush është duke shkuar për pikë në një tjetër në fund të vlefshme të fjalës.

627
00:55:30,810 --> 00:55:36,930
Pra, ne shohim se kur ne vazhdojmë përmes B dhe pastaj A,

628
00:55:36,930 --> 00:55:43,480
ka dy opsione të ndryshme aktualisht në fjalorin tonë për fjalët që fillojnë me B dhe A.

629
00:55:49,650 --> 00:55:57,460
Thonë se ne të kërkuar për të futur Foobar fjalë.

630
00:55:57,460 --> 00:56:05,620
Atëherë ne do të bëjë një hyrje në F.

631
00:56:05,620 --> 00:56:11,320
F është një nyje që tregon për një grup të tërë.

632
00:56:11,320 --> 00:56:22,790
Ne do të gjeni O, shkojnë në O, o pastaj lidh në një listë të tërë.

633
00:56:22,790 --> 00:56:35,340
Ne do të kemi B dhe pastaj të vazhdojë, ne do të kemi një dhe pastaj R.

634
00:56:35,340 --> 00:56:43,570
Pra pastaj përshkon Foobar gjithë rrugën poshtë derisa Foobar është një fjalë e saktë.

635
00:56:43,570 --> 00:56:52,590
Dhe kështu, atëherë kjo do të jetë një fjalë të vlefshme.

636
00:56:52,590 --> 00:57:00,170
Tani thonë se fjala jonë e ardhshme në fjalor është në të vërtetë FOO fjala.

637
00:57:00,170 --> 00:57:03,530
Ne do të thonë F. Çfarë vijon F?

638
00:57:03,530 --> 00:57:06,190
Unë në fakt tashmë kanë një hapësirë ​​për O, kështu që unë jam duke shkuar për të vazhduar.

639
00:57:06,190 --> 00:57:09,150
Unë nuk kam nevojë për të bërë një të ri. Vazhdo.

640
00:57:09,150 --> 00:57:15,500
FOO është një fjalë e vlefshme në këtë fjalor, kështu që atëherë unë jam duke shkuar për të treguar

641
00:57:15,500 --> 00:57:21,660
se kjo është e vlefshme.

642
00:57:21,660 --> 00:57:28,370
Nëse unë ndaluar rend time atje, që do të jetë e saktë.

643
00:57:28,370 --> 00:57:33,050
Por në qoftë se ne kemi vazhduar rend tonë nga foo poshtë për B

644
00:57:33,050 --> 00:57:39,750
dhe vetëm kishte FOOB, FOOB nuk është një fjalë, dhe se nuk është treguar si një të vlefshme.

645
00:57:47,370 --> 00:57:57,600
Në një trie, ju keni çdo nyje treguar nëse kjo është një fjalë të vlefshme ose jo,

646
00:57:57,600 --> 00:58:05,840
dhe pastaj çdo nyje gjithashtu ka një rrjet prej 27 pointers nyjeve

647
00:58:05,840 --> 00:58:09,520
që pastaj pikë në nyjet vetë.

648
00:58:09,520 --> 00:58:12,940
>> Këtu është një mënyrë se si ju mund të dëshironi për të përcaktuar këtë.

649
00:58:12,940 --> 00:58:17,260
Megjithatë, ashtu si në shembullin e tabelës hash, ku kemi pasur një kokë nyje *

650
00:58:17,260 --> 00:58:21,320
për të treguar fillimin e listës sonë të lidhura, ne jemi gjithashtu do të duan

651
00:58:21,320 --> 00:58:29,150
disa mënyrë për të ditur se ku fillimi i trie tonë është.

652
00:58:29,150 --> 00:58:34,110
Disa e quajnë njerëz të përpiqet pemë, dhe kjo është ajo ku vjen nga rrënja.

653
00:58:34,110 --> 00:58:36,910
Pra, ne duam rrënja e pemës tonë për të siguruar që ne të qëndrojnë të bazuara

654
00:58:36,910 --> 00:58:39,570
kudo që trie tonë është.

655
00:58:42,910 --> 00:58:46,300
Ne tashmë lloj i shkoi

656
00:58:46,300 --> 00:58:50,240
në mënyrë që ju mund të mendoni për ngarkimin e çdo fjalë në fjalor.

657
00:58:50,240 --> 00:58:54,540
Në thelb, për çdo fjalë që ju jeni do të duan të iterate përmes trie tuaj

658
00:58:54,540 --> 00:58:59,590
dhe duke e ditur se çdo element në fëmijët - ne e quajti atë fëmijë në këtë rast -

659
00:58:59,590 --> 00:59:04,290
korrespondon me një letër tjetër, ju jeni do të dëshironi të kontrolloni ato vlera

660
00:59:04,290 --> 00:59:08,320
në atë indeks të veçantë që korrespondon me letër.

661
00:59:08,320 --> 00:59:11,260
Pra, duke menduar të gjithë rrugën prapa Cezarit dhe Vigenere,

662
00:59:11,260 --> 00:59:16,070
duke e ditur se çdo letër ju mund të lloj hartë kthehet në një indeks alfabetik,

663
00:59:16,070 --> 00:59:20,690
Një patjetër nëpërmjet Z do të jetë goxha e lehtë për të hartë në një letër alfabetik,

664
00:59:20,690 --> 00:59:25,200
por fatkeqësisht, apostrofat janë gjithashtu një karakter pranuar në fjalë.

665
00:59:25,200 --> 00:59:31,650
Unë nuk jam edhe i sigurt se çfarë është vlera ASCII,

666
00:59:31,650 --> 00:59:39,250
kështu që për se në qoftë se ju doni të gjeni një indeks për të vendosur nëse ju dëshironi që ajo të jetë ose para

667
00:59:39,250 --> 00:59:44,550
apo e fundit, ju do të keni për të bërë një kontroll të vështirë koduar për këtë

668
00:59:44,550 --> 00:59:48,930
dhe të vënë më pas se në indeksin e 26, për shembull.

669
00:59:48,930 --> 00:59:55,300
Pra, atëherë ju jeni duke kontrolluar vlerën në fëmijët [i]

670
00:59:55,300 --> 00:59:58,400
ku [i] korrespondon në çfarëdo letër ju jeni në.

671
00:59:58,400 --> 01:00:04,110
Nëse kjo është NULL, që do të thotë se nuk ka aktualisht asnjë letra e mundshme

672
01:00:04,110 --> 01:00:08,150
që rrjedhin nga ky rend mëparshme, kështu që ju jeni do të duan të malloc

673
01:00:08,150 --> 01:00:13,150
dhe të bëjë një nyje të re dhe të ketë që fëmijët [i] pikë për të

674
01:00:13,150 --> 01:00:17,890
në mënyrë që ju të krijoni - kur futet një letër në drejtkëndësh -

675
01:00:17,890 --> 01:00:23,680
bërë fëmijët jo-NULL pikë dhe në atë nyje të re.

676
01:00:23,680 --> 01:00:28,340
Por në qoftë se nuk është NULL, si në rast tonë të foo

677
01:00:28,340 --> 01:00:34,570
kur ne tashmë kishte Foobar, ne vazhdojmë,

678
01:00:34,570 --> 01:00:44,010
dhe ne nuk jemi kurrë duke bërë një nyje të re, por jo vetëm vendosjen is_word të vërtetë

679
01:00:44,010 --> 01:00:47,790
në fund të kësaj fjale.

680
01:00:50,060 --> 01:00:55,340
>> Prandaj, ashtu si më parë, sepse këtu ju jeni që kanë të bëjnë me çdo letër në një kohë,

681
01:00:55,340 --> 01:01:01,470
ajo do të jetë më e lehtë për ju për të madhësisë, në vend që të llogarisë

682
01:01:01,470 --> 01:01:06,910
dhe kalojnë nëpër pemë gjithë dhe për të llogaritur se sa fëmijë kam

683
01:01:06,910 --> 01:01:10,850
dhe pastaj bronkial jashtë, duke kujtuar se sa shumë janë në anën e majtë dhe në anën e djathtë

684
01:01:10,850 --> 01:01:12,850
dhe gjëra të tilla si se, ajo do të jetë shumë më e lehtë për ju

685
01:01:12,850 --> 01:01:16,220
në qoftë se ju vetëm i mbajnë gjurmët e sa fjalë që ju jeni duke shtuar në

686
01:01:16,220 --> 01:01:18,080
kur ju jeni që kanë të bëjnë me ngarkesën.

687
01:01:18,080 --> 01:01:22,630
Dhe kështu atëherë madhësia mënyrë mund të kthehen vetëm një ndryshore globale të madhësisë.

688
01:01:25,320 --> 01:01:28,530
>> Tani kemi ardhur për të kontrolluar.

689
01:01:28,530 --> 01:01:33,920
Standardet e njëjtë si më parë, ku ne duam të lejuar për ftohtësi rast.

690
01:01:33,920 --> 01:01:40,400
Si edhe, ne supozojmë se vargjet janë karaktere alfabetike vetëm ose apostrofat

691
01:01:40,400 --> 01:01:44,000
sepse fëmijët është një grup i 27 gjatë,

692
01:01:44,000 --> 01:01:48,480
kështu që të gjitha shkronjat e alfabetit plus apostrof.

693
01:01:48,480 --> 01:01:53,800
Për të parë se çfarë ju do të dëshironi të bëni është që ju do të dëshironi të fillojë në rrënjë

694
01:01:53,800 --> 01:01:58,440
sepse rrënja do të tregojë për një grup që përmban

695
01:01:58,440 --> 01:02:01,630
të gjitha letrat e mundshme e fillimit të një fjale.

696
01:02:01,630 --> 01:02:03,680
Ju jeni do të fillojë atje,

697
01:02:03,680 --> 01:02:11,590
dhe pastaj ju do të jeni për të kontrolluar është kjo NULL vlerë apo jo,

698
01:02:11,590 --> 01:02:16,490
sepse nëse vlera është NULL, që do të thotë se fjalori nuk ka asnjë vlera

699
01:02:16,490 --> 01:02:21,480
që përmbajnë atë letër në atë mënyrë të veçantë.

700
01:02:21,480 --> 01:02:24,970
Nëse kjo është NULL, atëherë kjo do të thotë se fjala është misspelled menjëherë.

701
01:02:24,970 --> 01:02:27,110
Por në qoftë se kjo nuk është NULL, atëherë ju mund të vazhdojë,

702
01:02:27,110 --> 01:02:34,090
thonë se letra e parë është një letër e mundur të parë në një fjalë,

703
01:02:34,090 --> 01:02:40,630
kështu që tani unë dua të kontrolloni nëse letra e dytë, që rend, është brenda fjalorit tim.

704
01:02:40,630 --> 01:02:46,540
Pra, ju jeni do të shkojë në indeksin e bijve të nyjen e parë

705
01:02:46,540 --> 01:02:50,720
dhe kontrolloni nëse kjo letër të dytë ekziston.

706
01:02:50,720 --> 01:02:57,440
Pastaj ju përsëris këtë proces për të parë nëse kjo sekuencë është e vlefshme apo jo

707
01:02:57,440 --> 01:02:59,060
brenda trie tuaj.

708
01:02:59,060 --> 01:03:06,430
Kurdo që fëmijët nyjë në atë pikë indeksi në NULL,

709
01:03:06,430 --> 01:03:10,710
ju e dini se kjo sekuencë nuk ekziston,

710
01:03:10,710 --> 01:03:16,230
por pastaj nëse ju arrini në fund të fjalës që ju keni futur,

711
01:03:16,230 --> 01:03:20,070
atëherë ju dëshironi të shikoni tani që unë kam përfunduar këtë rend

712
01:03:20,070 --> 01:03:27,610
dhe e gjeti atë brenda trie tim, është se fjala e vlefshme apo jo?

713
01:03:27,610 --> 01:03:32,480
Dhe kështu atëherë ju dëshironi të shikoni se, dhe kjo është kur në qoftë se ju keni gjetur atë rend,

714
01:03:32,480 --> 01:03:35,120
atëherë ju doni të kontrolloni nëse kjo fjalë është e vlefshme apo jo

715
01:03:35,120 --> 01:03:40,290
sepse kujtohet përsëri në rastin e mëparshëm që unë tërhoqi ku kemi pasur FOOB,

716
01:03:40,290 --> 01:03:48,410
se ishte një sekuencë e vlefshme që kemi gjetur, por nuk ishte një fjalë e vlefshme aktuale vetë.

717
01:03:50,570 --> 01:03:59,000
>> Në mënyrë të ngjashme, për të shkarkoj në mundohet që ju doni të shkarkoj të gjitha nyjet në trie tuaj.

718
01:03:59,000 --> 01:04:04,790
Më vjen keq. Ngjashëm me tabelat hash ku në shkarkoj ne liruar të gjitha nyjet,

719
01:04:04,790 --> 01:04:09,740
në mundohet ne duam gjithashtu të liruar të gjitha nyjet.

720
01:04:09,740 --> 01:04:15,000
Shkarkoj vërtetë do të punojnë lehtë nga fundi në krye

721
01:04:15,000 --> 01:04:19,290
sepse këto janë të lidhura thelb listat.

722
01:04:19,290 --> 01:04:22,540
Pra, ne duam të sigurohemi që ne të mbajë në të gjitha vlerave

723
01:04:22,540 --> 01:04:25,700
dhe të lirë të gjithë ata në mënyrë eksplicite.

724
01:04:25,700 --> 01:04:28,840
Çfarë ju jeni do të dëshironi të bëni, nëse ju jeni duke punuar me një trie

725
01:04:28,840 --> 01:04:35,640
është që të udhëtojë për në fund dhe të lirë nyjen më të ulët të mundshme parë

726
01:04:35,640 --> 01:04:39,190
dhe pastaj të shkojnë deri në të gjithë ata fëmijë dhe pastaj të lirë të gjithë ata,

727
01:04:39,190 --> 01:04:43,050
shkojnë deri dhe pastaj të lirë, etj

728
01:04:43,050 --> 01:04:48,790
Lloj si që kanë të bëjnë me shtresën e poshtme të parë trie

729
01:04:48,790 --> 01:04:51,940
dhe pastaj të shkojnë deri të lartë një herë ju keni liruar gjithçka.

730
01:04:51,940 --> 01:04:56,720
Ky është një shembull i mirë i ku funksion recursive mund të vijnë në volitshëm.

731
01:04:56,720 --> 01:05:03,830
Pasi të keni liruar shtresën e poshtme të trie tuaj,

732
01:05:03,830 --> 01:05:08,000
atëherë ju telefononi shkarkoj në pjesën tjetër të saj,

733
01:05:08,000 --> 01:05:13,620
duke u siguruar që ju të liruar çdo mini -

734
01:05:13,620 --> 01:05:16,410
Ju mund të lloj të parashikoj se si përpiqet mini.

735
01:05:23,300 --> 01:05:28,990
Pra, ju keni rrënjë tuaj këtu.

736
01:05:30,840 --> 01:05:35,230
Unë jam vetëm thjeshtuar atë kështu që unë nuk duhet të tërheqë 26 prej tyre.

737
01:05:37,250 --> 01:05:43,770
Pra, ju keni këto, dhe pastaj këto paraqesin sekuenca të fjalëve

738
01:05:43,770 --> 01:05:54,620
ku të gjitha këto qarqe janë pak letra që janë sekuenca të vlefshme e letrave.

739
01:06:03,040 --> 01:06:07,160
Le të vazhdojnë vetëm një pak më shumë.

740
01:06:15,110 --> 01:06:25,750
Çfarë ju jeni do të dëshironi të bëni është pa fund këtu dhe pastaj të lirë kjo

741
01:06:25,750 --> 01:06:31,640
dhe pastaj pa kjo në fund para se të liruar një të lartë deri këtu

742
01:06:31,640 --> 01:06:38,180
sepse në qoftë se ju diçka të lirë në nivelin e dytë këtu,

743
01:06:38,180 --> 01:06:47,230
atëherë ju në të vërtetë do të humbasë këtë vlerë këtu.

744
01:06:47,230 --> 01:06:54,780
Kjo është arsyeja pse është e rëndësishme në të shkarkoj një trie për të bërë të sigurtë që ju të liruar në fund të parë.

745
01:06:54,780 --> 01:06:59,480
Çfarë ju mund të dëshironi të bëni është të thonë për çdo nyje

746
01:06:59,480 --> 01:07:06,430
Unë dua të shkarkoj gjithë fëmijët.

747
01:07:16,060 --> 01:07:22,140
>> Tani që ne kemi shkuar mbi zbraz për metodën tryezë hash si dhe metodën trie,

748
01:07:22,140 --> 01:07:27,020
ne do të dëshironi të shikoni në Shprehje.

749
01:07:27,020 --> 01:07:29,640
Shprehje me ju drejtuar komandat e mëposhtme.

750
01:07:29,640 --> 01:07:32,700
Ju keni Shprehje-V.

751
01:07:32,700 --> 01:07:40,960
Ju jeni duke kontrolluar për të gjitha rrjedhjet kur ju drejtuar speller dhënë këtë tekst të caktuar

752
01:07:40,960 --> 01:07:46,980
sepse speller nevojë për të marrë në një skedar teksti.

753
01:07:46,980 --> 01:07:52,330
Pra Shprehje do të drejtuar programin tuaj, t'ju them se sa bytes keni ndarë,

754
01:07:52,330 --> 01:07:57,150
sa bytes keni liruar, dhe kjo do të ju tregojnë nëse ju liruan vetëm sa

755
01:07:57,150 --> 01:07:58,930
apo nëse ju nuk e keni të lirë të mjaftueshme,

756
01:07:58,930 --> 01:08:02,850
ose ndonjëherë ju mund edhe të mbi-të lirë, si nyje e lirë një që është tashmë liruar

757
01:08:02,850 --> 01:08:05,140
dhe kështu ajo do të ju kthehen gabime.

758
01:08:05,140 --> 01:08:11,600
Në qoftë se ju përdorni Shprehje, ai do t'ju japë disa mesazhe

759
01:08:11,600 --> 01:08:15,970
treguar nëse ju keni liruar ose më pak se e mjaftueshme, vetëm të mjaftueshme,

760
01:08:15,970 --> 01:08:19,609
ose më shumë se herë të mjaftueshme.

761
01:08:24,370 --> 01:08:30,410
>> Një pjesë e këtij pset, kjo është fakultative për të sfiduar Bordi Big.

762
01:08:30,410 --> 01:08:35,790
Por kur ne jemi që kanë të bëjnë me këto struktura të dhënave

763
01:08:35,790 --> 01:08:40,689
kjo është lloj i argëtim për të parë se sa shpejt dhe sa efikase strukturave të dhënat tuaja mund të jetë.

764
01:08:40,689 --> 01:08:44,490
A rezultat hash juaj funksionojnë në një shumë prej perplasjeve?

765
01:08:44,490 --> 01:08:46,300
Apo është madhësia të dhënat tuaja të vërtetë e madhe?

766
01:08:46,300 --> 01:08:49,420
A do të marrë shumë kohë të kaloj?

767
01:08:49,420 --> 01:08:54,800
Në log të speller, ajo nxjerr sa kohë që ju përdorni për të ngarkuar,

768
01:08:54,800 --> 01:08:57,700
për të kontrolluar, për të kryer madhësinë, dhe të shkarkoj,

769
01:08:57,700 --> 01:09:00,720
dhe kështu ata janë postuar në bordin Big,

770
01:09:00,720 --> 01:09:03,600
ku ju mund të konkurrojnë kundër shokëve tuaj

771
01:09:03,600 --> 01:09:11,350
dhe disa anëtarë të stafit për të parë që e ka më të shpejtë spell checker-.

772
01:09:11,350 --> 01:09:14,760
Një gjë që unë do të doja të theksohet në lidhje me tabelat hash

773
01:09:14,760 --> 01:09:20,470
është se ka disa funksione mjaft të thjeshta hash se ne mund të mendoni.

774
01:09:20,470 --> 01:09:27,240
Për shembull, ju keni 26 kova, dhe kështu çdo kovë

775
01:09:27,240 --> 01:09:30,200
korrespondon tek letrës së parë në një fjale,

776
01:09:30,200 --> 01:09:35,229
por që do të rezultojë në një tryezë mjaft të paekuilibruar hash

777
01:09:35,229 --> 01:09:40,979
sepse nuk janë fjalët e një shumë më pak që fillojnë me X se fillimi me M, për shembull.

778
01:09:40,979 --> 01:09:47,890
Një mënyrë për të shkuar në lidhje speller është në qoftë se ju doni të merrni të gjitha funksionet e tjera poshtë,

779
01:09:47,890 --> 01:09:53,240
vetëm atëherë përdorni një funksion të thjeshtë hash të jetë në gjendje për të marrë kodin tuaj running

780
01:09:53,240 --> 01:09:58,650
dhe pastaj të shkojnë prapa dhe të ndryshojë madhësinë e tabelës suaj hash dhe përkufizim.

781
01:09:58,650 --> 01:10:03,430
Nuk janë një shumë e burimeve në internet për funksione të hash,

782
01:10:03,430 --> 01:10:08,250
dhe kështu për këtë pset ju lejohet të kërkimit funksionet hash në internet

783
01:10:08,250 --> 01:10:15,560
për disa lë të kuptohet dhe frymëzim për aq kohë sa ju të bëni të sigurt për të citojnë se ku e keni marrë atë nga.

784
01:10:15,560 --> 01:10:22,060
Ju jeni të mirëpritur për të parë dhe interpretuar disa funksion hash që ju të gjeni në internet.

785
01:10:22,060 --> 01:10:27,460
Mbrapsht në se, ju mund të jetë në gjendje për të parë nëse dikush përdorur një trie

786
01:10:27,460 --> 01:10:31,700
nëse zbatimi i tyre është më i shpejtë se tavolina juaj hash apo jo.

787
01:10:31,700 --> 01:10:35,290
Ju mund t'i dorëzojë Bordit Big herë të shumta.

788
01:10:35,290 --> 01:10:37,660
Ajo do të regjistrojë hyrjen tuaj më të fundit.

789
01:10:37,660 --> 01:10:44,300
Kështu që ndoshta ju të ndryshojë funksionin hash tuaj dhe pastaj të kuptojë se kjo është në fakt një shumë të shpejtë

790
01:10:44,300 --> 01:10:46,780
ose një shumë më ngadalë se më parë.

791
01:10:46,780 --> 01:10:50,960
Kjo është pak e një mënyrë zbavitëse.

792
01:10:50,960 --> 01:10:57,190
Ka gjithmonë 1 ose 2 anëtarët e stafit të cilët të përpiqet të bëjë fjalor slowest të jetë e mundur,

793
01:10:57,190 --> 01:11:00,210
kështu që është gjithmonë kënaqësi për të parë.

794
01:11:00,210 --> 01:11:07,630
>> Përdorimi për pset është që ju të drejtuar speller me një fjalor opsional

795
01:11:07,630 --> 01:11:12,840
dhe pastaj një file teksti të detyrueshme.

796
01:11:12,840 --> 01:11:18,380
By default, kur ju drejtuar speller me vetëm një skedar një tekst dhe nuk specifikoni një fjalor,

797
01:11:18,380 --> 01:11:24,410
ajo do të përdorin fjalor file teksti, një të madhe

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

799
01:11:27,920 --> 01:11:32,760
Se një ka mbi 100.000 fjalë.

800
01:11:32,760 --> 01:11:37,950
Ata gjithashtu kanë një fjalor të vogël e cila ka fjalë në mënyrë të konsiderueshme më pak

801
01:11:37,950 --> 01:11:40,730
CS50 që ka bërë për ju.

802
01:11:40,730 --> 01:11:44,050
Megjithatë, ju mund shumë lehtë të bëjë vetëm fjalorin tuaj

803
01:11:44,050 --> 01:11:47,150
në qoftë se ju vetëm duan të punojnë në shembuj të vogla -

804
01:11:47,150 --> 01:11:51,140
për shembull, në qoftë se ju dëshironi të përdorni gdb dhe ju e dini vlerat specifike

805
01:11:51,140 --> 01:11:53,560
se ju doni tavolina juaj hash në hartë për të.

806
01:11:53,560 --> 01:12:00,430
Kështu që ju vetëm mund të bëni vetë dosjen tuaj tekst vetëm me bar, Baz, foo, dhe Foobar,

807
01:12:00,430 --> 01:12:04,860
bëjnë që në një skedar teksti, ndajë ata njëri me 1 linjë,

808
01:12:04,860 --> 01:12:12,670
dhe pastaj të bëjë vetë dosjen tuaj tekst që fjalë për fjalë përmban vetëm ndoshta 1 ose 2 fjalë

809
01:12:12,670 --> 01:12:15,950
kështu që ju e dini saktësisht se çfarë duhet të jetë prodhimi.

810
01:12:15,950 --> 01:12:21,870
Disa nga fotografi tekst mostër që Bordi Big, kur ju drejtuar sfidë do të kontrollojë

811
01:12:21,870 --> 01:12:25,580
Lufta dhe Paqja janë dhe një roman Austen Jane ose diçka të tillë.

812
01:12:25,580 --> 01:12:30,450
Pra, kur ju jeni duke filluar nga jashtë, kjo është një shumë e lehtë për të bërë fotografi tuaj tekst

813
01:12:30,450 --> 01:12:34,160
që përmbajnë vetëm disa prej fjalëve apo ndoshta 10

814
01:12:34,160 --> 01:12:38,280
kështu që ju mund të parashikojnë se çfarë rezultati duhet të jetë

815
01:12:38,280 --> 01:12:42,880
dhe pastaj shikoni atë kundër që, aq më shumë të një shembull të kontrolluar.

816
01:12:42,880 --> 01:12:45,820
Dhe kështu që ne jemi që kanë të bëjnë me parashikimin dhe hartimin gjërat rreth,

817
01:12:45,820 --> 01:12:48,690
përsëri unë dua të ju inkurajoj që të përdorni stilolaps dhe letër

818
01:12:48,690 --> 01:12:50,700
sepse ajo është me të vërtetë do të ju ndihmojë me këtë -

819
01:12:50,700 --> 01:12:55,620
vizatim shigjeta, si tabela hash apo si trie tuaj duket,

820
01:12:55,620 --> 01:12:57,980
kur ju jeni liruar diçka ku shigjetat po shkojnë,

821
01:12:57,980 --> 01:13:01,730
po ju mbajnë në të mjaftueshme, ju shihni ndonjë lidhje zhduken

822
01:13:01,730 --> 01:13:05,750
dhe të bjerë në humnerën e kujtesës rrjedhur.

823
01:13:05,750 --> 01:13:11,070
Pra ju lutem, ju lutem provoni për të nxjerrë jashtë gjërat edhe para se të merrni për të shkruar kodin poshtë.

824
01:13:11,070 --> 01:13:14,520
Draw gjëra jashtë në mënyrë që ju të kuptoni se si gjërat janë duke shkuar për të punuar

825
01:13:14,520 --> 01:13:22,750
sepse atëherë unë garantoj ju do të kandidojë në muddles akrep pak atje.

826
01:13:24,270 --> 01:13:25,910
>> Dakord.

827
01:13:25,910 --> 01:13:28,780
Unë dua të ju uroj shumë më të mirë e fat me këtë pset.

828
01:13:28,780 --> 01:13:31,980
Kjo është ndoshta një e vështirë.

829
01:13:31,980 --> 01:13:40,360
Kështu që të përpiqet për të filluar herët, barazim gjërat jashtë, barazim gjërat jashtë, dhe fat të mirë.

830
01:13:40,360 --> 01:13:42,980
Kjo ishte Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]