1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Валктхроугх - Проблем Сет 5]

2
00:00:02,740 --> 00:00:04,870
[Замила Цхан - Универзитет Харвард]

3
00:00:04,870 --> 00:00:07,190
[Ово је ЦС50. - ЦС50.ТВ]

4
00:00:07,190 --> 00:00:10,400
>> У реду. Поздрав свима, и добродошли у Валктхроугх 5.

5
00:00:10,400 --> 00:00:17,400
>> Псет5 је Грешке у којој ћемо бити прави за проверу правописа.

6
00:00:17,400 --> 00:00:21,030
Спелл-даме су изузетно важни.

7
00:00:21,030 --> 00:00:23,390
Да се ​​ово икада десило?

8
00:00:23,390 --> 00:00:27,170
Ви сте веома радите, веома оставе на папиру за сукоб

9
00:00:27,170 --> 00:00:33,120
и онда још на крају добија врло сјај Радета као Д или Д =

10
00:00:33,120 --> 00:00:39,390
а све због тога што сте паштета спојлер на китове широком речи.

11
00:00:39,390 --> 00:00:44,710
Да, лектура своје паприке је ствар од, крајње импотенција.

12
00:00:44,710 --> 00:00:49,140
То је проблем који утиче на Манли, Манли студената.

13
00:00:49,140 --> 00:00:56,260
Једном сам рекао мојим Ситх разреда мучитеља да никада не би у добром колеги.

14
00:00:56,260 --> 00:01:00,250
И то је све што сам икада желео, то је све било које дете жели у мојим годинама,

15
00:01:00,250 --> 00:01:04,569
само да уђу у добром колеги.

16
00:01:04,569 --> 00:01:12,720
И то не било какав колега. Не желим да идем на Слоноваче правној колеге.

17
00:01:12,720 --> 00:01:18,360
Дакле, ако нисам побољшање, нестао би моји снови ће да Харварду,

18
00:01:18,360 --> 00:01:22,730
Јале, или затвор - знате, у затвору, Њу Џерси.

19
00:01:22,730 --> 00:01:25,170
Тако сам себи имам провере правописа.

20
00:01:25,170 --> 00:01:29,380
То је мало извод из једног од мојих омиљених уметника изговорена реч, Тејлор Малом.

21
00:01:29,380 --> 00:01:34,630
У сваком случају, како каже, значај има проверу правописа је веома важно.

22
00:01:34,630 --> 00:01:39,440
>> Дакле, добродошли на Валктхроугх 5, у којој ће говорити о псет5: Грешке,

23
00:01:39,440 --> 00:01:44,300
у којој ћемо бити доношење нашу сопствену проверу правописа.

24
00:01:44,300 --> 00:01:50,880
Тоолбок за ову недељу, расподела код, биће важно да погледате

25
00:01:50,880 --> 00:01:54,950
само да разуме различите функције које ваш речник ће имати.

26
00:01:54,950 --> 00:02:01,500
Ми смо заправо ће бити потребе више. Ц датотека које заједно чине наш псет.

27
00:02:01,500 --> 00:02:05,420
И тако гледа кроз различите аспекте, иако заправо не уређивање

28
00:02:05,420 --> 00:02:10,770
један од фајлова, спеллер.ц, знајући како се то ради у односу на дицтионари.ц,

29
00:02:10,770 --> 00:02:14,100
којима ћемо писати, ће бити прилично важно.

30
00:02:14,100 --> 00:02:16,970
Тхе псет спец такође садржи доста корисних информација

31
00:02:16,970 --> 00:02:21,360
у смислу ствари које можете да претпостављају, правила и сличне ствари,

32
00:02:21,360 --> 00:02:24,710
па будите сигурни да прочитате спецификације псет пажљиво савете.

33
00:02:24,710 --> 00:02:29,310
А када су у недоумици по правилу, или нешто слично, онда увек погледајте псет спец

34
00:02:29,310 --> 00:02:31,550
или Разговарајте.

35
00:02:31,550 --> 00:02:34,060
Ова псет ће у великој мери ослањају на показивача,

36
00:02:34,060 --> 00:02:37,890
па смо желели да се уверите да разумемо разлику између додајући звезда

37
00:02:37,890 --> 00:02:41,680
испред имена показивач и амперсандс, како да их ослободе, итд

38
00:02:41,680 --> 00:02:47,550
Тако што мајстор показивача ће бити веома корисно у овом проблематиком сету.

39
00:02:47,550 --> 00:02:50,460
Ми ћемо да погледамо у повезаним листама мало више,

40
00:02:50,460 --> 00:02:57,790
где имамо елементе који зовемо чворове који имају обе вредности, као и показивач

41
00:02:57,790 --> 00:03:02,520
на следећи чвор, и тако суштински повезујући различите елементе један за другим.

42
00:03:02,520 --> 00:03:07,190
Постоји неколико различитих опција спровођења своју стварну речник.

43
00:03:07,190 --> 00:03:13,150
Ми ћемо да погледамо у две главне методе, што је хасх табеле, а затим покушава.

44
00:03:13,150 --> 00:03:17,660
У оба њих, они укључују неку врсту појма повезану листу

45
00:03:17,660 --> 00:03:20,790
где сте елементе повезане једна са другом.

46
00:03:20,790 --> 00:03:25,640
И тако ћемо да погледамо о томе како ћете можда бити у могућности да раде око повезаним листама,

47
00:03:25,640 --> 00:03:29,680
створи их, идите у смислу како да се, на пример, убаците у њега чвор

48
00:03:29,680 --> 00:03:32,760
или бесплатно све чворове као добро.

49
00:03:32,760 --> 00:03:34,740
У смислу ослобадјања чворова, што је заиста важно

50
00:03:34,740 --> 00:03:37,700
да кад год смо маллоц меморије, затим смо га ослободили.

51
00:03:37,700 --> 00:03:42,910
Дакле, желимо да се уверите да нема показивач иде унфреед, да немамо никакве цурење меморије.

52
00:03:42,910 --> 00:03:48,330
Ми ћемо увести алатку која се зове Валгринд који покреће свој програм

53
00:03:48,330 --> 00:03:52,260
и проверава да ли су све меморије коју издваја се затим ослободио.

54
00:03:52,260 --> 00:03:59,080
Ваша псет само заврши када се ради и да има пуну функционалност,

55
00:03:59,080 --> 00:04:03,990
али такође, Валгринд вам говори да нисте нашли никакве меморијске цурења.

56
00:04:03,990 --> 00:04:06,690
Коначно, за ову псет, ја заиста желим да нагласим -

57
00:04:06,690 --> 00:04:11,360
Мислим, као и обично, ја сам дефинитивно поборник коришћења оловку и папир за твој проблем сетовима,

58
00:04:11,360 --> 00:04:14,840
али за овај један, мислим да оловка и папир ће бити посебно важно

59
00:04:14,840 --> 00:04:19,000
када желите да будете цртање стрелице ствари и разумевање како ствари раде.

60
00:04:19,000 --> 00:04:24,440
Дакле, дефинитивно покушајте да користите оловку и папир да скрене ствари пре него што се кодирање

61
00:04:24,440 --> 00:04:26,970
јер она може да добије мало неуредна.

62
00:04:26,970 --> 00:04:30,700
>> Прво идемо у повезаним листама мало.

63
00:04:30,700 --> 00:04:35,510
Повезане листе се састоји од чворова, где сваки чвор има неку вредност у вези са њом,

64
00:04:35,510 --> 00:04:39,810
као и показивач на следећи чвор после њега.

65
00:04:39,810 --> 00:04:43,680
Пар ствари важних са повезаним листама су да треба да запамтите

66
00:04:43,680 --> 00:04:48,810
где је наш први чвор је, а затим једном знамо где је први чвор је,

67
00:04:48,810 --> 00:04:52,990
на тај начин можемо приступити чвор да су први чвор указује на

68
00:04:52,990 --> 00:04:55,850
а затим и један после тога и онај после тога.

69
00:04:55,850 --> 00:05:00,340
А онда последњи елемент у повезаној листи је тог чвора показивач

70
00:05:00,340 --> 00:05:02,340
увек ће да укаже на НУЛЛ.

71
00:05:02,340 --> 00:05:08,230
Када чвор бодова НУЛЛ, онда знате да сте стигли на крај листе,

72
00:05:08,230 --> 00:05:12,320
да је чвор је последњи, да не постоји ништа после тога.

73
00:05:12,320 --> 00:05:16,970
Овде у овој шеми, видећете да су стрелице су показивачи,

74
00:05:16,970 --> 00:05:20,290
а плави одељак где се вредност складишти,

75
00:05:20,290 --> 00:05:24,420
и онда црвени оквир са показивачем То је чвора показивач

76
00:05:24,420 --> 00:05:27,050
указујући на следећи чвор после њега.

77
00:05:27,050 --> 00:05:33,730
И тако ви овде видите, Д чвор би указивао на НУЛЛ, јер је последњи елемент у листи.

78
00:05:33,730 --> 00:05:38,240
>> Хајде да погледамо како бисмо могли да дефинишемо струцт за чвор.

79
00:05:38,240 --> 00:05:40,130
А пошто ми желимо да имамо више чворова,

80
00:05:40,130 --> 00:05:43,180
ово ће постати типедеф струцт

81
00:05:43,180 --> 00:05:46,870
у којој ћемо имати неколико различитих инстанци чворова.

82
00:05:46,870 --> 00:05:50,850
И тако смо га дефинишемо као нови тип података.

83
00:05:50,850 --> 00:05:53,630
Ево, имамо типедеф струцт цвор.

84
00:05:53,630 --> 00:05:56,160
У овом примеру, имамо посла са целим чворова,

85
00:05:56,160 --> 00:06:00,490
тако да имамо целобројну вредност по имену, а онда ћемо имати још једну показивача,

86
00:06:00,490 --> 00:06:07,390
и у овом случају, то је показивач на чвор, тако да имамо струцт цвор * зове следећи.

87
00:06:07,390 --> 00:06:09,520
И онда смо називајући целу ову ствар чвор.

88
00:06:09,520 --> 00:06:11,110
Уверите се да пратите ову синтаксу.

89
00:06:11,110 --> 00:06:17,940
Приметимо да чвор заправо упућује горе, као и испод заграда.

90
00:06:17,940 --> 00:06:23,400
Онда да пратите где је мој први чвор је у овој повезаној листи,

91
00:06:23,400 --> 00:06:29,390
онда имам чвор показивач зове глава, а ја маллоц простора довољно за величине чвора.

92
00:06:29,390 --> 00:06:36,240
Приметите, међутим, да је заправо глава чвор показивач за разлику од стварног саме чвор.

93
00:06:36,240 --> 00:06:40,130
Тако је шеф заправо не садржи никакву вредност,

94
00:06:40,130 --> 00:06:45,590
само указује на први чвор год у мојој листи је повезана.

95
00:06:55,080 --> 00:06:58,340
>> Да бисте добили бољи осећај повезаних листи, јер је то веома важно

96
00:06:58,340 --> 00:07:02,220
да пратите и уверите се да сте одржавају ланац,

97
00:07:02,220 --> 00:07:09,990
Волим да мислим о томе како људи у линији држећи се за руке,

98
00:07:09,990 --> 00:07:14,330
где свака особа држи за руке са следеће.

99
00:07:14,330 --> 00:07:18,350
Ви не можете да видите на овом цртежу, али у суштини они указују на следећу особу

100
00:07:18,350 --> 00:07:23,760
који је у свом ланцу.

101
00:07:23,760 --> 00:07:29,270
И тако, ако желите да пролазе повезану листу где су ти људи -

102
00:07:29,270 --> 00:07:32,830
замислити све од тих људи имају вредности повезане са њима

103
00:07:32,830 --> 00:07:36,590
и указати на следеће особе у линији -

104
00:07:36,590 --> 00:07:40,810
ако желите да пролазе повезану листу, на пример, или уређивање вредности

105
00:07:40,810 --> 00:07:42,830
или потрага за вредност или нешто слично,

106
00:07:42,830 --> 00:07:48,270
онда ћете желети да имате показивач на одређену особу.

107
00:07:48,270 --> 00:07:52,670
Тако ћемо имати податке показивач типа чвора.

108
00:07:52,670 --> 00:07:55,580
За овај пример, назовимо га курсор.

109
00:07:55,580 --> 00:07:59,630
Други уобичајени начин да наведемо ово би итератора или нешто слично

110
00:07:59,630 --> 00:08:05,130
зато што је итератинг изнова и стварно креће којој чвор то је указивање на.

111
00:08:05,130 --> 00:08:14,410
Ово овде ће бити наш курсор.

112
00:08:14,410 --> 00:08:20,180
Наш курсор ће прво указати на први елемент у нашој листи.

113
00:08:20,180 --> 00:08:26,910
И тако оно што ми желимо да урадимо је да смо у основи бити наставак курсор,

114
00:08:26,910 --> 00:08:29,130
премештање са једне на другу страну.

115
00:08:29,130 --> 00:08:33,409
У овом случају, желимо да га преместили на следећи елемент у листи.

116
00:08:33,409 --> 00:08:38,480
Са низовима, шта ћемо урадити јесте да само кажемо повећање индекса од 1.

117
00:08:38,480 --> 00:08:46,020
У том случају, оно што треба да урадимо је заправо наћи које лице ове струје особа указује да,

118
00:08:46,020 --> 00:08:48,930
и то ће бити следећи вредност.

119
00:08:48,930 --> 00:08:53,230
Дакле, ако курсор само чвор показивач, онда оно што желимо да урадимо

120
00:08:53,230 --> 00:08:56,320
је да ми желимо да дођемо до вредности која се курсор указује на.

121
00:08:56,320 --> 00:09:01,350
Желимо да се на тај чвор и онда, кад смо у том чвору, наћи тамо где је указујући на.

122
00:09:01,350 --> 00:09:05,820
Да бисте стигли до самог чвора да курсор указује на,

123
00:09:05,820 --> 00:09:13,160
Обично смо га уписати (* курсор).

124
00:09:13,160 --> 00:09:19,160
То ће вам дати стварну чвор да се курсор упућује на.

125
00:09:19,160 --> 00:09:21,730
А онда, након тога, оно што желимо да урадимо јесте желимо да приступите

126
00:09:21,730 --> 00:09:25,680
шта год да следећа вредност чвора је.

127
00:09:25,680 --> 00:09:32,820
Да би то урадили, да бисте приступили вредности унутар струцт, имамо дот оператера.

128
00:09:32,820 --> 00:09:39,530
Онда би било (* курсор) следећи..

129
00:09:39,530 --> 00:09:44,840
Али ово је мало неуредна у смислу да заграде око * курсора,

130
00:09:44,840 --> 00:09:56,800
и тако смо заменили целу ову изјаву са курсор->.

131
00:09:56,800 --> 00:10:02,700
То је црта, а затим већи него знак, тако што стрелу.

132
00:10:02,700 --> 00:10:05,840
курсор-> следеци.

133
00:10:05,840 --> 00:10:12,390
То ће заиста добити вам чвор који се курсор указује. Та вредност је на следећи.

134
00:10:12,390 --> 00:10:16,790
Дакле, уместо да звезду и тачку, ви мењате то са стрелом.

135
00:10:16,790 --> 00:10:24,820
Будите веома пажљиви да се уверите да покушате да користите ову синтаксу.

136
00:10:33,550 --> 00:10:37,620
>> Сада када имамо курсор, ако желимо да приступимо вредност,

137
00:10:37,620 --> 00:10:40,450
раније, имали смо курсор-> нект,

138
00:10:40,450 --> 00:10:46,260
али да приступите вредност на чвору да се курсор упућује да, ми једноставно само реци

139
00:10:46,260 --> 00:10:48,070
чвор-> вредност.

140
00:10:48,070 --> 00:10:53,600
Одатле, то је врста података год смо дефинисали вредности и чворове да буде.

141
00:10:53,600 --> 00:10:59,620
Ако је инт чвор, а затим курсор-> вредност само ће бити цео број.

142
00:10:59,620 --> 00:11:04,870
Дакле, можемо да урадимо операције на то, проверите једнакости, доделити му различите вредности, итд

143
00:11:04,870 --> 00:11:11,090
Па шта онда желите да урадите уколико желите да померите курсор на следећу особу,

144
00:11:11,090 --> 00:11:15,270
Ви заиста променити вредност курсора.

145
00:11:15,270 --> 00:11:19,340
Пошто курсор је чвор показивач, променили сте стварну показивача адресу

146
00:11:19,340 --> 00:11:23,890
на адресу следећег чвора у листи.

147
00:11:23,890 --> 00:11:28,930
Ово је само неки број где сте могли прелазили.

148
00:11:28,930 --> 00:11:31,230
Где сам коментар нешто уради,

149
00:11:31,230 --> 00:11:33,850
то је место где ћете вероватно ћеш да приступите вредности

150
00:11:33,850 --> 00:11:37,850
или уради нешто са том конкретном чвору.

151
00:11:37,850 --> 00:11:43,050
Да бисте га почетак, ја кажем да је мој почетку курсор

152
00:11:43,050 --> 00:11:48,430
ће да укаже на први елемент у повезаној листи.

153
00:11:48,430 --> 00:11:52,910
И тако напред, ја сам га дефинише као шефа чвора.

154
00:11:52,910 --> 00:11:57,610
>> Као што сам раније поменуо, ослобађајући је заиста важно.

155
00:11:57,610 --> 00:12:02,440
Ви желите да се уверите да сте слободни сваки елемент у листи када завршите са њим.

156
00:12:02,440 --> 00:12:04,940
Када не треба да упућују неки од тих показивача више,

157
00:12:04,940 --> 00:12:10,620
желите да се уверите да сте слободни све те показивача.

158
00:12:10,620 --> 00:12:14,460
Али ти желиш да будеш веома пажљив овде у који желите да избегнете било какво цурење меморије.

159
00:12:14,460 --> 00:12:25,080
Ако прерано сте слободни једна особа, онда сви показивача који тај чвор указује на

160
00:12:25,080 --> 00:12:26,900
ће бити изгубљен.

161
00:12:26,900 --> 00:12:32,070
Враћајући се на лицу пример да би се мало више високих улога,

162
00:12:32,070 --> 00:12:49,600
хајде да те људе, осим у овом случају они су лебди изнад језера са чудовиштем.

163
00:12:49,600 --> 00:12:53,200
Желимо да се уверите да кад год смо ослободили, не губимо

164
00:12:53,200 --> 00:12:58,920
и пустите било чворова пре него што смо смо их ослободили.

165
00:12:58,920 --> 00:13:05,730
На пример, ако сте били да једноставно позовете бесплатно на овог момка овде,

166
00:13:05,730 --> 00:13:15,350
онда би се ослободио, али онда сви ови момци ће онда бити изгубљен

167
00:13:15,350 --> 00:13:18,450
и они би нанос искључен и пасти.

168
00:13:18,450 --> 00:13:24,900
Дакле, желимо да се уверите да уместо тога, желимо да одржимо везу са остатком.

169
00:13:37,630 --> 00:13:42,480
Наше главе показивач, који показује на први елемент у листи.

170
00:13:42,480 --> 00:13:49,990
То је као конопац сидрења прву особу.

171
00:13:52,870 --> 00:13:57,470
Оно што можда желите да урадите када сте слободни листа имају -

172
00:13:57,470 --> 00:14:04,520
Ако желите да се прво ослободи први елемент, онда можете имати привремену показивач

173
00:14:04,520 --> 00:14:07,370
који указује на било први елемент је.

174
00:14:07,370 --> 00:14:11,420
Дакле, имате ваша привремена показивач указује овде.

175
00:14:11,420 --> 00:14:15,840
Тако, имамо држи првог чвора.

176
00:14:15,840 --> 00:14:18,930
А онда, пошто знамо да је први чвор ће бити ослобођен,

177
00:14:18,930 --> 00:14:24,890
онда можемо да пређемо тај конопац, ово сидро, наша глава,

178
00:14:24,890 --> 00:14:31,930
да заправо указују на све што први указује на.

179
00:14:31,930 --> 00:14:38,760
Дакле, ово глава заправо указује на другом елементу сада.

180
00:14:38,760 --> 00:14:43,980
Сада нам је дозвољено да ослободи све што се чува у темп,

181
00:14:43,980 --> 00:14:53,360
и тако можемо избрисати да без тога угрожавања свих осталих чворова у нашој листи.

182
00:14:54,140 --> 00:15:05,020
Други начин да то урадите може да буде

183
00:15:05,020 --> 00:15:08,650
сваки пут када само ослободити последњи елемент у листи

184
00:15:08,650 --> 00:15:11,010
јер они гарантовано неће бити указао на било шта.

185
00:15:11,010 --> 00:15:15,570
Значи само да ослободи ово, онда слободно то један, онда слободно то један.

186
00:15:15,570 --> 00:15:21,900
То дефинитивно ради али је мало спорија, јер по природи повезаних листи,

187
00:15:21,900 --> 00:15:24,670
не можемо одмах прећи на последњој.

188
00:15:24,670 --> 00:15:28,030
Морамо да пролазе сваки елемент у повезаној листи

189
00:15:28,030 --> 00:15:31,020
и проверите да ли је неко указује на НУЛЛ, проверите сваки пут,

190
00:15:31,020 --> 00:15:33,780
и онда када стигнемо до краја, онда без тога.

191
00:15:33,780 --> 00:15:40,270
Ако сте били да се овај процес, ви заправо била ту проверу,

192
00:15:40,270 --> 00:15:44,190
провера овде, онда проверу овде, ослобађајући га,

193
00:15:44,190 --> 00:15:47,470
онда враћам, провера овде, провери овде, ослобађајући га,

194
00:15:47,470 --> 00:15:49,660
провере овде, а затим га ослободе.

195
00:15:49,660 --> 00:15:52,880
То траје мало више времена. Да.

196
00:15:52,880 --> 00:15:59,060
>> [Ученик] Да ли је могуће направити листу која складишти повезане излазну показивач до краја?

197
00:15:59,060 --> 00:16:01,320
То би дефинитивно било могуће.

198
00:16:01,320 --> 00:16:08,340
Да поновим питање, могуће је да имате повезану структуру листе

199
00:16:08,340 --> 00:16:12,490
тако да имате показивач указује на крај повезане листе?

200
00:16:12,490 --> 00:16:18,090
Ја бих рекао да је то могуће, и сваки пут када убаците нешто у своју повезану листу

201
00:16:18,090 --> 00:16:21,470
ти би да ажурирате тај показивач и такве ствари.

202
00:16:21,470 --> 00:16:26,640
Ти би имати чвор реп *, на пример.

203
00:16:26,640 --> 00:16:29,840
Али када сте примене ову функцију, морате да мислите о траде-офф,

204
00:16:29,840 --> 00:16:32,700
волим колико пута ћу бити итератинг због тога,

205
00:16:32,700 --> 00:16:36,100
Колико је тешко ће бити да пратите репа као и главу

206
00:16:36,100 --> 00:16:38,400
као и мој Итератор, и такве ствари.

207
00:16:40,730 --> 00:16:42,480
Да ли то -? >> [Ученик] Да.

208
00:16:42,480 --> 00:16:48,270
То је могуће, али у смислу дизајна одлука, морате да одмери опције.

209
00:16:53,850 --> 00:17:01,090
>> Овде је скелет кода који ће вам омогућити да ослободите сваки елемент у повезану листу.

210
00:17:01,090 --> 00:17:05,460
Опет, пошто сам итератинг преко повезаног листи, ја ћу желети да имају неку врсту курсора

211
00:17:05,460 --> 00:17:08,670
или итератор.

212
00:17:08,670 --> 00:17:14,640
Ми смо итератинг док курсор НУЛЛ.

213
00:17:14,640 --> 00:17:17,640
Ви не желите да вршите итерацију када курсор НУЛЛ

214
00:17:17,640 --> 00:17:20,579
јер то значи да не постоји ништа у листи.

215
00:17:20,579 --> 00:17:25,069
Па онда овде направи привремени чвор *

216
00:17:25,069 --> 00:17:29,610
указујући на оно што сам с обзиром је први мојој листи,

217
00:17:29,610 --> 00:17:35,340
и онда сам померим курсор напред 1 и онда слободно све што сам имао у привременом складишту.

218
00:17:38,460 --> 00:17:43,650
>> Сада долазимо до убацивања у повезаним листама.

219
00:18:00,200 --> 00:18:09,660
Имам три чвора у мом повезаном листи, и идемо са једноставном случају

220
00:18:09,660 --> 00:18:18,970
где желимо да убаците другу чвор на крају нашег повезане листе.

221
00:18:18,970 --> 00:18:25,980
Да бисте то урадили, сви ћемо урадити јесте бисмо прешли

222
00:18:25,980 --> 00:18:32,100
да пронађе где се тренутно крај повезан листи је, како год чвор указује на НУЛЛ -

223
00:18:32,100 --> 00:18:33,850
да је ово један -

224
00:18:33,850 --> 00:18:37,260
и онда кажу, у ствари, ово неће бити последњи чвор;

225
00:18:37,260 --> 00:18:39,830
ми заправо ћемо имати још једну.

226
00:18:39,830 --> 00:18:46,260
Тако бисмо имали ову тренутну један бод год смо убацивање.

227
00:18:46,260 --> 00:18:50,080
Тако сада ова црвена особа овде постаје последњи чвор у повезаној листи.

228
00:18:50,080 --> 00:18:56,080
И тако карактеристична за последње чвора у повезаној листи је да указује на НУЛЛ.

229
00:18:56,080 --> 00:19:09,380
Па шта онда бисмо морали да урадите је да подесите показивач Овај црвени момка на НУЛЛ. Ето.

230
00:19:09,380 --> 00:19:25,370
>> Али шта ако бисмо хтели да убаците чвор између другог и трећег један?

231
00:19:25,370 --> 00:19:28,960
Та није баш тако једноставно, јер желимо да будете сигурни

232
00:19:28,960 --> 00:19:34,290
да не пусти било чвора у нашој повезану листу.

233
00:19:34,290 --> 00:19:43,450
Оно што би требало да урадите је да проверите да смо се усидре на сваког од њих.

234
00:19:43,450 --> 00:19:49,900
На пример, назовимо ово други.

235
00:19:49,900 --> 00:19:54,390
Ако сте рекли други сада показује на овом новом

236
00:19:54,390 --> 00:20:02,520
а ви само тамо направили показивач, онда би за последицу овај момак да се изгуби

237
00:20:02,520 --> 00:20:07,830
јер не постоји веза са њим.

238
00:20:07,830 --> 00:20:18,970
Уместо - Ја ћу извући ово поново. Извините моје уметничке способности.

239
00:20:18,970 --> 00:20:26,570
Ми знамо да не можемо једноставно повезати директно 2 на нови.

240
00:20:26,570 --> 00:20:30,480
Морамо бити сигурни да се држимо до последњег.

241
00:20:30,480 --> 00:20:39,200
Оно што можемо да урадимо је да има привремену показивач

242
00:20:39,200 --> 00:20:42,650
да елемент који ће бити придодат даље.

243
00:20:42,650 --> 00:20:45,140
Онда смо се тамо привремено показивач.

244
00:20:45,140 --> 00:20:50,780
Пошто знамо да је ово трећи се чува евиденцију о,

245
00:20:50,780 --> 00:20:53,680
2 сада може повезати на наш нови.

246
00:20:53,680 --> 00:20:57,490
А ако овај нови црвени момак ће бити између 2 и 3,

247
00:20:57,490 --> 00:21:05,550
онда шта је тај тип је показивач ће указати на? >> [Ученик] темп.

248
00:21:05,550 --> 00:21:07,490
Темп. Да.

249
00:21:07,490 --> 00:21:15,430
Онда следећа вредност овом црвеном лик је ће бити темп.

250
00:21:26,090 --> 00:21:33,010
Када убаците у повезаним листама, видели смо да смо могли

251
00:21:33,010 --> 00:21:38,260
лако додати нешто до краја стварањем привремене низ,

252
00:21:38,260 --> 00:21:42,850
или ако смо хтели да додам нешто у сред нашег низу,

253
00:21:42,850 --> 00:21:46,810
онда ће требати мало више меша около.

254
00:21:46,810 --> 00:21:50,240
Ако желите да, на пример, имају сортирани повезану листу,

255
00:21:50,240 --> 00:21:54,880
онда морате да некако вагати трошкова и користи које

256
00:21:54,880 --> 00:21:59,720
јер ако желите да имате сортирани низ, то значи да сваки пут када убаците у њу,

257
00:21:59,720 --> 00:22:01,630
то ће узети мало више времена.

258
00:22:01,630 --> 00:22:05,500
Међутим, ако желите да касније, као што ћемо наћи ћемо желети да,

259
00:22:05,500 --> 00:22:10,280
Тражи кроз повезану листу, онда то може бити лакше ако знате да је све у реду.

260
00:22:10,280 --> 00:22:15,340
Дакле, можда ћете желети да одмери трошкове и користи од тога.

261
00:22:20,150 --> 00:22:27,740
>> Други начин да се унесе у повезаној листи је да убаците у самом почетку листе.

262
00:22:27,740 --> 00:22:34,700
Ако скрећемо овде сидро - то је наша глава -

263
00:22:34,700 --> 00:22:40,960
и онда су ти људи повезани са њим,

264
00:22:40,960 --> 00:22:48,460
и онда имамо нову чвор да се убаци у почетку,

265
00:22:48,460 --> 00:22:52,590
онда шта бисмо могли да радимо?

266
00:22:55,220 --> 00:23:03,580
Шта би било у реду са само кажем да желим да се повежете црвене до плаве,

267
00:23:03,580 --> 00:23:05,790
јер је то први?

268
00:23:05,790 --> 00:23:08,570
Шта би овде десило?

269
00:23:08,570 --> 00:23:12,130
Све ове три би се изгубила.

270
00:23:12,130 --> 00:23:14,140
Дакле, ми не желимо да то урадим.

271
00:23:14,140 --> 00:23:21,430
Опет смо научили да морамо да имамо неку врсту привременог показивача.

272
00:23:21,430 --> 00:23:34,470
Да одлуче да имају привремену тачку на овог момка.

273
00:23:34,470 --> 00:23:39,640
Тада можемо имати плаву један бод на привремени

274
00:23:39,640 --> 00:23:43,240
и онда црвени показивач на плаво.

275
00:23:43,240 --> 00:23:47,830
Разлог зашто ја користим људе овде, јер ми заиста желимо да визуализује

276
00:23:47,830 --> 00:23:53,180
држећи на људе и да се уверите да имамо везу на њих

277
00:23:53,180 --> 00:23:57,590
Пре него што пусти друге стране, или нешто слично томе.

278
00:24:05,630 --> 00:24:10,650
>> Сада када имамо осећај повезаних листи - како бисмо могли створити повезану листу

279
00:24:10,650 --> 00:24:15,090
и створити структуре за које се састоји од типа дефиниције за чвор

280
00:24:15,090 --> 00:24:19,060
и онда да се уверите да имамо показивач на челу тог повезаних листи -

281
00:24:19,060 --> 00:24:23,210
Једном смо да и ми знамо како да прођу кроз низ,

282
00:24:23,210 --> 00:24:28,200
приступите различите елементе, знамо како да убаците и знамо како да их ослободе,

283
00:24:28,200 --> 00:24:30,260
онда можемо ући у правописних грешака.

284
00:24:30,260 --> 00:24:38,150
Као и обично, ми имамо део питања која ће се сте користили за пословање са повезаним листама

285
00:24:38,150 --> 00:24:41,750
и различите структуре, као што су редове и димњацима.

286
00:24:41,750 --> 00:24:46,000
Онда можемо да идемо у правописних грешака.

287
00:24:46,000 --> 00:24:55,170
>> Грешке има у дистрибутивном код неколико досијеа значаја.

288
00:24:55,170 --> 00:24:58,850
Прво смо приметили да овде имамо ову Макефиле,

289
00:24:58,850 --> 00:25:03,040
које нисмо стварно срели раније.

290
00:25:03,040 --> 00:25:10,090
Ако сте гледали унутар псет5 фасцикле, ти би приметити да имате х фајл.,

291
00:25:10,090 --> 00:25:12,530
онда имате две ц фајлове..

292
00:25:12,530 --> 00:25:18,920
Шта ово ради је Макефиле раније, ми бисмо маке а онда име програма

293
00:25:18,920 --> 00:25:25,550
и онда ћемо видети све ове аргументе и заставе усвојен на компајлера.

294
00:25:25,550 --> 00:25:30,580
Шта ради је Макефиле нам омогућава да састави неколико фајлова одједном

295
00:25:30,580 --> 00:25:34,650
и проћи у заставама које желимо.

296
00:25:34,650 --> 00:25:41,300
Овде видимо овде је заглавље датотеке.

297
00:25:41,300 --> 00:25:43,730
Онда ми заправо имамо две изворне фајлове.

298
00:25:43,730 --> 00:25:47,520
Имамо спеллер.ц и дицтионари.ц.

299
00:25:47,520 --> 00:25:54,560
Ви сте добродошли да уредите Макефиле ако желите.

300
00:25:54,560 --> 00:26:03,310
Приметимо да овде ако откуцате чист, онда оно што ради је заправо уклања све

301
00:26:03,310 --> 00:26:06,340
то је језгро.

302
00:26:06,340 --> 00:26:09,190
Ако имаш грешку сегментације, у суштини добијате депонију језгра.

303
00:26:09,190 --> 00:26:13,260
Дакле, ова ружна мала датотека ће се појавити у вашем именику зове језгро.

304
00:26:13,260 --> 00:26:16,310
Ви ћете желети да уклоните да би га чистим.

305
00:26:16,310 --> 00:26:20,940
Она уклања све еке фајлове и о фајлова..

306
00:26:27,900 --> 00:26:30,220
>> Хајде да погледамо у дицтионари.х.

307
00:26:30,220 --> 00:26:34,410
Овај каже да прогласи функционалност речника је.

308
00:26:34,410 --> 00:26:39,530
Имамо максималну дужину за било речи у речнику.

309
00:26:39,530 --> 00:26:45,130
Ми кажемо да ће ово бити најдужи могући реч. То је дужине 45.

310
00:26:45,130 --> 00:26:48,900
Дакле, ми нећемо имати никакве речи које премашују ту дужину.

311
00:26:48,900 --> 00:26:50,980
Овде имамо само функцијских прототипова.

312
00:26:50,980 --> 00:26:55,290
Ми немамо конкретну реализацију, јер то је оно што ћемо радити за ову псет.

313
00:26:55,290 --> 00:26:59,940
Али, шта то ради је јер смо се баве већим фајловима овде

314
00:26:59,940 --> 00:27:06,650
и функционалност у већем обиму, то је корисно имати х фајл.

315
00:27:06,650 --> 00:27:11,290
тако да неко други чита или коришћењем кода може да разуме шта се дешава.

316
00:27:11,290 --> 00:27:17,910
А можда желе да спроведу покушава ако јеси хеш табеле или обрнуто.

317
00:27:17,910 --> 00:27:21,850
Онда бих моју функцију учитавања

318
00:27:21,850 --> 00:27:26,950
стварна реализација ће да се разликују, али то прототип неће променити.

319
00:27:26,950 --> 00:27:33,280
Овде смо проверили, које враћа труе ако дати реч у речнику.

320
00:27:33,280 --> 00:27:39,800
Онда имамо оптерећења, што у основи узима у датотеци речника

321
00:27:39,800 --> 00:27:44,360
и онда га учитава у неку структуру података.

322
00:27:44,360 --> 00:27:47,500
Имамо величину, који, када се зове, враћа величину речника,

323
00:27:47,500 --> 00:27:50,310
колико речи се чувају у њему,

324
00:27:50,310 --> 00:27:54,390
и онда истовара, који ослобађа меморију све које сте преузели

325
00:27:54,390 --> 00:27:57,900
правећи свој речник.

326
00:28:01,070 --> 00:28:03,590
>> Хајде да погледамо дицтионари.ц.

327
00:28:03,590 --> 00:28:10,490
Видимо да то изгледа врло слично дицтионари.х, осим сада има само све ове тодос у њему.

328
00:28:10,490 --> 00:28:16,980
И то је твој посао. На крају, бићете попуњавањем спеллер.ц са свим овим кодом.

329
00:28:16,980 --> 00:28:21,540
Дицтионари.ц, када покренете, није стварно да уради ништа,

330
00:28:21,540 --> 00:28:29,590
па гледамо према спеллер.ц да види стварну примену правописа.

331
00:28:29,590 --> 00:28:32,060
Чак и ако не идеш да се уређивање било овог законика,

332
00:28:32,060 --> 00:28:38,050
важно је да чита, разуме када је оптерећење зове, када сам зове чек,

333
00:28:38,050 --> 00:28:42,350
само да разуме, мапирати га, види како функционише.

334
00:28:42,350 --> 00:28:49,860
Ми видимо да се то провери за правилно коришћење.

335
00:28:49,860 --> 00:28:55,200
У суштини, када неко ради Спеллер, то указује да је опционо

336
00:28:55,200 --> 00:29:00,950
за њих да прође у речнику датотеци јер ће бити подразумевани речник фајл.

337
00:29:00,950 --> 00:29:05,410
И онда они морају да прођу у тексту да се правописа проверава.

338
00:29:05,410 --> 00:29:11,410
русаге бави време, јер део овог псет којима ћемо се бавити касније

339
00:29:11,410 --> 00:29:14,790
није само добијање функционисање спелл-Цхецкер ради

340
00:29:14,790 --> 00:29:17,190
али заправо све да буде брз.

341
00:29:17,190 --> 00:29:22,040
И тако онда то је где русаге ће да уђу

342
00:29:22,040 --> 00:29:28,740
Овде видимо први позив на један од наших дицтионари.ц фајлова, што је оптерећење.

343
00:29:28,740 --> 00:29:34,720
Оптерећење враћа труе или фалсе - тачно на успех, лажни након неуспеха.

344
00:29:34,720 --> 00:29:41,400
Дакле, ако речник није учитан исправно, онда ће се вратити спеллер.ц 1 и отказ.

345
00:29:41,400 --> 00:29:47,920
Али ако се то деси оптерећење правилно, онда ће то наставити.

346
00:29:47,920 --> 00:29:50,740
Настављамо и видимо овде неки фајл И / О,

347
00:29:50,740 --> 00:29:56,210
где ће се суочити са отварањем текстуалну датотеку.

348
00:29:56,210 --> 00:30:04,640
Ево, шта је ово ради је правописа проверава сваку реч у тексту.

349
00:30:04,640 --> 00:30:09,270
Па шта спеллер.ц ради овде се итератинг преко сваке речи у текстуалној датотеци

350
00:30:09,270 --> 00:30:12,790
а затим их провере у речнику.

351
00:30:24,680 --> 00:30:32,350
Ево, имамо Боолеан погрешно написану која ће видети да ли чек врати истина или не.

352
00:30:32,350 --> 00:30:37,110
Ако реч је заправо у речнику, онда провера ће се вратити истина.

353
00:30:37,110 --> 00:30:39,760
То значи да реч није погрешно.

354
00:30:39,760 --> 00:30:45,330
Дакле, погрешно би било погрешно, и то је разлог зашто смо тамо прасак, индикација.

355
00:30:45,330 --> 00:30:56,320
Настављамо да иде, и онда води евиденцију о томе колико погрешно написане речи

356
00:30:56,320 --> 00:30:58,910
постоје у датотеци.

357
00:30:58,910 --> 00:31:03,870
Она се наставља и затвара фајл.

358
00:31:03,870 --> 00:31:09,250
Онда овде, извештава колико погрешно написане речи сте имали.

359
00:31:09,250 --> 00:31:12,680
Она израчунава колико времена је било потребно да се учита речник,

360
00:31:12,680 --> 00:31:15,080
колико времена је било потребно да се провери,

361
00:31:15,080 --> 00:31:18,510
колико времена је било потребно да израчуна величину,

362
00:31:18,510 --> 00:31:21,260
који је, како ћемо ићи даље, треба бити веома мали,

363
00:31:21,260 --> 00:31:25,390
па колико времена је требало да истовари речник.

364
00:31:25,390 --> 00:31:27,700
Овде горе видимо позив да овде истоваре.

365
00:31:27,700 --> 00:31:52,690
Ако бисмо проверили за величину овде,

366
00:31:52,690 --> 00:31:59,050
онда видимо да је овде позив на величину где одређује величину речника.

367
00:32:05,730 --> 00:32:07,100
Страва.

368
00:32:07,100 --> 00:32:10,920
>> Наш задатак за ову псет је да спроведе оптерећења, што ће учитати речник

369
00:32:10,920 --> 00:32:15,480
Структура података - шта год да изаберете, било да је хеш табела или пробајте -

370
00:32:15,480 --> 00:32:18,810
са речима из речника датотеке.

371
00:32:18,810 --> 00:32:25,290
Онда имате величину, која ће вратити број речи у речнику.

372
00:32:25,290 --> 00:32:29,860
А ако спроведе оптерећење у паметан начин, онда величине треба да буде прилично лако.

373
00:32:29,860 --> 00:32:33,860
Онда сте проверили, који ће проверити да ли дата реч налази у речнику.

374
00:32:33,860 --> 00:32:38,690
Тако спеллер.ц пролази у низу, а онда морате да проверите да ли је стринг

375
00:32:38,690 --> 00:32:41,610
садржан у вашем речнику.

376
00:32:41,610 --> 00:32:46,750
Приметите да смо генерално имају стандардне речнике,

377
00:32:46,750 --> 00:32:53,020
али у овом псет, у основи било речник донет на било ком језику.

378
00:32:53,020 --> 00:32:57,040
Дакле, ми не можемо само претпоставити да је Реч је унутра.

379
00:32:57,040 --> 00:33:03,090
Реч Фообар може дефинисати у одређеном речнику који пролазимо ин

380
00:33:03,090 --> 00:33:07,920
А онда смо истовара, који ослобађа речник из меморије.

381
00:33:07,920 --> 00:33:11,930
>> Прво, желео бих да идем у хеш метод табеле

382
00:33:11,930 --> 00:33:14,630
о томе како бисмо могли спровести све те четири функције,

383
00:33:14,630 --> 00:33:18,650
и онда идем преко покушава метод, како можемо имплементирати ове четири функције,

384
00:33:18,650 --> 00:33:22,720
и на крају приче о неким општим савете када правите псет

385
00:33:22,720 --> 00:33:27,870
и како ћете можда бити у могућности да користите Валгринд да проверите за меморијске цурења.

386
00:33:27,870 --> 00:33:30,550
>> Идемо у хеш табеле методом.

387
00:33:30,550 --> 00:33:35,910
Хасх табела се састоји од листе корпи.

388
00:33:35,910 --> 00:33:43,010
Свака вредност, свака реч, је да идем у једну од ових сегмената.

389
00:33:43,010 --> 00:33:53,200
Хасх табела идеално равномерно распоређује свим овим вредностима које сте пролазу у

390
00:33:53,200 --> 00:33:57,160
а затим их попуњава у кофи том што свака кашика

391
00:33:57,160 --> 00:34:02,000
има око једнаким бројем вредности у њему.

392
00:34:02,000 --> 00:34:09,630
Структура за хеш табели, имамо низ повезаних листи.

393
00:34:09,630 --> 00:34:17,900
Шта радимо када прођемо у вредности, ми смо проверили где је вредност треба да припадају,

394
00:34:17,900 --> 00:34:23,840
која кашика припада, а затим га ставите у повезаној листи повезан са том кашиком.

395
00:34:23,840 --> 00:34:28,199
Ево, шта ја имам је хеш функција.

396
00:34:28,199 --> 00:34:31,320
То је инт хасх табели.

397
00:34:31,320 --> 00:34:38,540
Дакле, за прву кофу, сви цели бројеви испод 10 иде у прву кофу.

398
00:34:38,540 --> 00:34:42,190
Било целих изнад 10, али испод 20 иду у други,

399
00:34:42,190 --> 00:34:44,179
и онда тако даље и тако даље.

400
00:34:44,179 --> 00:34:52,370
За мене, свака кашика заступа ове бројеве.

401
00:34:52,370 --> 00:34:59,850
Ипак, кажу да је требало да прође у 50, на пример.

402
00:34:59,850 --> 00:35:07,490
Изгледа као да је прва три садржи низ од десет бројева.

403
00:35:07,490 --> 00:35:12,570
Али ја желим да дозволите ми хеш табела да се у било којој врсти целих бројева,

404
00:35:12,570 --> 00:35:19,860
па онда би морао да филтрира све бројеве изнад 30 у последњој кофу.

405
00:35:19,860 --> 00:35:26,660
И тако онда би резултирати неком врстом неуравнотеженом хеш табеле.

406
00:35:31,330 --> 00:35:35,640
Да подсетимо, хеш табела је само низ сегмената

407
00:35:35,640 --> 00:35:38,590
где је сваки кофа повезана листа.

408
00:35:38,590 --> 00:35:43,730
И тако би се утврдило где свака вредност иде, која кашика иде у,

409
00:35:43,730 --> 00:35:46,260
ћеш да желим оно што се зове хеш функција

410
00:35:46,260 --> 00:35:55,010
који узима вредност и онда каже ова вредност одговара одређеном корпе.

411
00:35:55,010 --> 00:36:00,970
Дакле, горе у овом примеру, мој хасх функција је сваку вредност.

412
00:36:00,970 --> 00:36:03,020
Она проверава да ли је било мање од 10 година.

413
00:36:03,020 --> 00:36:05,360
Ако јесте, то би га ставио у први кофу.

414
00:36:05,360 --> 00:36:08,910
Она проверава да ли је мање од 20, ставља га у други ако је то тачно,

415
00:36:08,910 --> 00:36:12,880
проверава да ли је мање од 30 година, а затим га ставља у трећем кофу,

416
00:36:12,880 --> 00:36:16,990
и онда све остало само пада на четврту корпе.

417
00:36:16,990 --> 00:36:20,110
Дакле, кад год имате неку вредност, ваш хеш функција

418
00:36:20,110 --> 00:36:25,420
ће ставити ту вредност у одговарајуће корпе.

419
00:36:25,420 --> 00:36:32,430
Хеш функција у основи треба да зна колико кашике имате.

420
00:36:32,430 --> 00:36:37,960
Ваша хасх табела величине, број корпи имате,

421
00:36:37,960 --> 00:36:41,190
то ће бити фиксни број који је до вас, за вас да одлучите,

422
00:36:41,190 --> 00:36:43,590
али то ће бити фиксни број.

423
00:36:43,590 --> 00:36:51,840
Дакле, ваша хасх функција ће се ослањати на то да се утврди које кашика сваки тастер иде у

424
00:36:51,840 --> 00:36:54,450
таква да је равномерно распоређена.

425
00:36:56,150 --> 00:37:03,820
Слично нашем имплементацију повезаних листи, сада сваки чвор у хеш табели

426
00:37:03,820 --> 00:37:07,000
заправо ће имати знак типа.

427
00:37:07,000 --> 00:37:14,340
Дакле, имамо низ цхар називом реч, а затим још један показивач на следећи чвор,

428
00:37:14,340 --> 00:37:19,010
што има смисла, јер ће то бити повезана листа.

429
00:37:19,010 --> 00:37:24,350
Сећаш ли се када смо повезани листе, направио сам чвор * зове глава

430
00:37:24,350 --> 00:37:31,060
који је указујући на први чвор у повезаној листи.

431
00:37:31,060 --> 00:37:34,020
Али за наше хеш табеле, јер имамо више повезаних листи,

432
00:37:34,020 --> 00:37:37,520
оно што ми желимо је да желимо наш хеш табела бити као, "Шта је канта?"

433
00:37:37,520 --> 00:37:43,340
Кашика је само списак чвора показивача,

434
00:37:43,340 --> 00:37:50,620
и тако сваки елемент у кофи заправо указује на одговарајућој повезаних листи.

435
00:37:56,180 --> 00:38:01,520
Да се ​​вратимо на ову шему, видећете да су сами кашике су стрелице,

436
00:38:01,520 --> 00:38:06,980
не стварни чворова.

437
00:38:11,680 --> 00:38:16,420
Један од суштинског значаја имовина хеш функција је да су детерминистичка.

438
00:38:16,420 --> 00:38:19,440
То значи да кад год хеш број 2,

439
00:38:19,440 --> 00:38:22,270
увек треба да врати исту канту.

440
00:38:22,270 --> 00:38:26,440
Свака појединачна вредност која иде у хеш функцију, ако се понови,

441
00:38:26,440 --> 00:38:29,690
има да добије исти индекс.

442
00:38:29,690 --> 00:38:34,210
Дакле, ваш хасх функција враћа индекс низа

443
00:38:34,210 --> 00:38:38,530
где је вредност припада.

444
00:38:38,530 --> 00:38:41,790
Као што сам раније поменуо, број корпи је фиксна,

445
00:38:41,790 --> 00:38:49,630
и тако ваш индекс који се вратите мора да буде мањи од броја сегмената

446
00:38:49,630 --> 00:38:52,680
али већи од 0.

447
00:38:52,680 --> 00:39:00,780
Разлог зашто смо хеш функције уместо само једним повезану листу

448
00:39:00,780 --> 00:39:09,290
или једна низ је да ми желимо да будемо у стању да скочи на одређени одељак најлакше

449
00:39:09,290 --> 00:39:11,720
ако знамо својство вредности -

450
00:39:11,720 --> 00:39:14,760
уместо да тражи кроз цео цео речник,

451
00:39:14,760 --> 00:39:18,320
бити у стању да пређете на одређеном делу њега.

452
00:39:19,880 --> 00:39:24,440
Ваша хеш функција треба да узме у обзир да у идеалном случају,

453
00:39:24,440 --> 00:39:28,980
свака кашика има приближно исти број тастера.

454
00:39:28,980 --> 00:39:35,040
Пошто је хасх табела низ повезаних листи,

455
00:39:35,040 --> 00:39:38,480
онда повезани сами спискови ће имати више од једног чвора.

456
00:39:38,480 --> 00:39:43,210
У претходном примеру, две различите бројеве, чак иако они нису били једнаки,

457
00:39:43,210 --> 00:39:46,950
када хеширају, враћали исти индекс.

458
00:39:46,950 --> 00:39:53,620
Дакле, када се баве речима, једну реч када хеширају

459
00:39:53,620 --> 00:39:57,450
ће бити исти хеш вредност као друге речи.

460
00:39:57,450 --> 00:40:04,140
То је оно што ми зовемо судара, када имамо чвор који, када хеширане,

461
00:40:04,140 --> 00:40:09,610
повезана листа у том кофи није празан.

462
00:40:09,610 --> 00:40:14,180
Техника коју зовемо постоји линеарна прескок,

463
00:40:14,180 --> 00:40:22,550
где идете на повезану листу, а затим пронађите где желите да убаците тај чвор

464
00:40:22,550 --> 00:40:25,520
јер имате судар.

465
00:40:25,520 --> 00:40:28,070
Можете видети да можда постоји траде-офф овде, зар не?

466
00:40:28,070 --> 00:40:33,760
Ако имате веома мали хеш табелу, веома мали број корпи,

467
00:40:33,760 --> 00:40:36,380
онда ћеш имати много судара.

468
00:40:36,380 --> 00:40:40,460
Али онда ако направите веома велики хеш табелу,

469
00:40:40,460 --> 00:40:44,110
вероватно ћеш да минимизира судара,

470
00:40:44,110 --> 00:40:47,170
али то ће бити веома велика структура података.

471
00:40:47,170 --> 00:40:49,310
Ту ће бити компромиси са тим.

472
00:40:49,310 --> 00:40:51,310
Дакле, када правите свој псет, покушајте да играте

473
00:40:51,310 --> 00:40:54,210
између можда што мањи хеш табелу

474
00:40:54,210 --> 00:41:02,100
али онда знајући да ће то узети мало више времена да прођу различите елементе

475
00:41:02,100 --> 00:41:04,270
тих повезаних листи.

476
00:41:04,270 --> 00:41:09,500
>> Шта оптерећење ће да уради јесте прелазили преко сваке речи у речнику.

477
00:41:09,500 --> 00:41:13,180
Она пролази у показивач на речника фајл.

478
00:41:13,180 --> 00:41:18,050
Тако ћеш да искористе датотеке И / О функције које сте усавршили у псет4

479
00:41:18,050 --> 00:41:23,010
и прелазили преко сваку реч у речнику.

480
00:41:23,010 --> 00:41:26,620
Хоћеш сваку реч у речнику да постане нови чвор,

481
00:41:26,620 --> 00:41:32,730
и ти ћеш ставити сваки од ових чворова унутар структуре вашег речника података.

482
00:41:32,730 --> 00:41:36,560
Кад год добијете нову реч, ви знате да ће то постати чвор.

483
00:41:36,560 --> 00:41:46,590
Дакле, можете одмах отићи и маллоц показивач чвор за сваку нову реч коју имате.

484
00:41:46,590 --> 00:41:52,610
Ево зовем моју чвор показивача нев_ноде и ја маллоцинг шта? Величина чвора.

485
00:41:52,610 --> 00:41:59,190
Онда да прочитате стварни стринг из фајла, јер је речник заправо чувају

486
00:41:59,190 --> 00:42:03,340
од речи и онда нови ред, шта можемо искористити

487
00:42:03,340 --> 00:42:06,520
је функција фсцанф,

488
00:42:06,520 --> 00:42:10,280
при чему фајл је речник фајл који смо прошли у,

489
00:42:10,280 --> 00:42:18,900
тако да скенира фајл за ниску и места која стринг у последњи аргумент.

490
00:42:18,900 --> 00:42:26,890
Ако се вратите сећате једног од предавања, када смо отишли ​​у

491
00:42:26,890 --> 00:42:29,320
и врста ољуштен слојеве назад на ЦС50 библиотеке,

492
00:42:29,320 --> 00:42:33,430
Видели смо да је спровођење фсцанф.

493
00:42:33,430 --> 00:42:37,700
Да се ​​вратимо на фсцанф, имамо датотеку да читате,

494
00:42:37,700 --> 00:42:42,570
тражимо ниску у том фајлу, и онда смо га ставља у

495
00:42:42,570 --> 00:42:48,340
Овде имам нев_ноде-> рец, јер нев_ноде је чвор показивач,

496
00:42:48,340 --> 00:42:50,380
Није стварна чвор.

497
00:42:50,380 --> 00:42:57,100
Онда ја кажем нев_ноде, желим да идем у чвор да се то указује на

498
00:42:57,100 --> 00:43:01,190
и онда доделите ту вредност речи.

499
00:43:01,190 --> 00:43:08,540
Желимо да онда узети ту реч и убаците га у хеш табелу.

500
00:43:08,540 --> 00:43:13,750
Схватите да смо направили нев_ноде чвор показивач

501
00:43:13,750 --> 00:43:18,230
јер ћемо желети да знају шта адресу тог чвора је

502
00:43:18,230 --> 00:43:23,940
када смо га убацили у, јер је структура самих чворова, од струцт,

503
00:43:23,940 --> 00:43:26,380
је да они имају показивач на нови чвор.

504
00:43:26,380 --> 00:43:30,820
Па у чему је онда адреса тог чвора ће указати на?

505
00:43:30,820 --> 00:43:34,550
Та адреса ће бити нев_ноде.

506
00:43:34,550 --> 00:43:42,140
Да ли то има смисла, зашто чинимо нев_ноде а * чвор насупрот чвор?

507
00:43:43,700 --> 00:43:45,700
Ок.

508
00:43:45,700 --> 00:43:52,840
Имамо реч. Та вредност је нев_ноде-> рец.

509
00:43:52,840 --> 00:43:55,970
Који садржи реч из речника који желимо да улаз.

510
00:43:55,970 --> 00:44:00,210
Дакле, оно што ми желимо да урадимо јесте желимо да позовете наш хеш функцију у том низу

511
00:44:00,210 --> 00:44:03,780
јер је наш хасх функција узима у низу, а онда се враћа нам цео број,

512
00:44:03,780 --> 00:44:12,090
где је цео је индекс где Хасхтабле на том индексу представља ту канту.

513
00:44:12,090 --> 00:44:18,260
Желимо да тај индекс, а затим идите на том индексу хеш табеле

514
00:44:18,260 --> 00:44:26,960
и онда користите ту повезану листу да убаците чвор на нев_ноде.

515
00:44:26,960 --> 00:44:31,950
Запамтите да ипак одлучите да убаците чвор,

516
00:44:31,950 --> 00:44:34,370
да ли је у средини ако желите да га сортирате

517
00:44:34,370 --> 00:44:39,650
или на почетку или на крају, само проверите да ли ваш последњи чвор увек указује на НУЛЛ

518
00:44:39,650 --> 00:44:46,730
јер то је једини начин на који знамо где је последњи елемент нашег повезаних листи је.

519
00:44:50,790 --> 00:44:59,710
>> Ако је величина цео број који представља број речи у речнику,

520
00:44:59,710 --> 00:45:03,060
онда један од начина да то урадите је да кад год се зове величина

521
00:45:03,060 --> 00:45:05,840
идемо кроз сваки елемент у нашој хасх табеле

522
00:45:05,840 --> 00:45:09,410
а онда прелазили преко сваког повезаног листе у року од хеш табели

523
00:45:09,410 --> 00:45:13,770
и онда израчунати дужину да повећава нашу противтужбу 1 од 1.

524
00:45:13,770 --> 00:45:16,580
Али сваки пут када се зове величина, који ће трајати дуго времена

525
00:45:16,580 --> 00:45:22,120
јер ћемо бити линеарно сондирање сваку повезану листу.

526
00:45:22,120 --> 00:45:30,530
Уместо тога, то ће бити много лакше ако пратите колико речи су прошли ин

527
00:45:30,530 --> 00:45:36,330
Дакле, ако сте укључити бројач унутар ваше оптерећења функцији

528
00:45:36,330 --> 00:45:42,430
која се ажурира по потреби, онда контра, ако га поставите на глобална променљива,

529
00:45:42,430 --> 00:45:44,930
ће моћи да се приступи по величини.

530
00:45:44,930 --> 00:45:51,450
Дакле, шта величине може једноставно урадити у једној линији, само вратите контра вредност,

531
00:45:51,450 --> 00:45:55,500
на величину речника, коју већ бавили у оптерећењем.

532
00:45:55,500 --> 00:46:05,190
То је оно што сам мислио када сам рекао ако спроведе оптерећење на користан начин,

533
00:46:05,190 --> 00:46:08,540
онда величина ће бити прилично лако.

534
00:46:08,540 --> 00:46:11,350
>> Дакле, сада смо добили да проверите.

535
00:46:11,350 --> 00:46:15,960
Сада имамо посла са речима из датотеке унос текста,

536
00:46:15,960 --> 00:46:19,910
па ћемо да провере да ли је све те речи улазних

537
00:46:19,910 --> 00:46:22,520
су заправо у речнику или не.

538
00:46:22,520 --> 00:46:26,520
Слично сцрамбле, желимо да омогући случај неосетљивости.

539
00:46:26,520 --> 00:46:32,110
Ви желите да се уверите да све речи донет, иако су мешовити случај,

540
00:46:32,110 --> 00:46:37,840
када се позове са гудачким упоредите су еквивалентна.

541
00:46:37,840 --> 00:46:42,450
Речи у датотекама речника текстуалних су заправо сви малим словима.

542
00:46:42,450 --> 00:46:49,280
Друга ствар је да можете претпоставити да је свака реч донет, сваки стринг,

543
00:46:49,280 --> 00:46:53,200
ће бити или алфабетски или садрже апострофа.

544
00:46:53,200 --> 00:46:58,010
Апострофа ће бити валидне речи у нашем речнику.

545
00:46:58,010 --> 00:47:06,470
Дакле, ако имате реч са апострофом С, то је стварна легитимна реч у вашем речнику

546
00:47:06,470 --> 00:47:11,650
то ће бити један од чворова у вашем хеш табели.

547
00:47:13,470 --> 00:47:18,350
Проверите да ли послује са реч постоји, онда то мора да буде у нашем хеш табели.

548
00:47:18,350 --> 00:47:22,210
Ако је реч у речнику, онда све речи у речнику су у хеш табели,

549
00:47:22,210 --> 00:47:26,560
па хајде да погледамо овај речи у хеш табели.

550
00:47:26,560 --> 00:47:29,250
Ми знамо да пошто смо имплементирали наше хеш функцију

551
00:47:29,250 --> 00:47:38,420
таква да је свака јединствена реч увек хеширају истом вредношћу,

552
00:47:38,420 --> 00:47:43,340
онда знамо да уместо трагања кроз читаву нашу целу хеш табели,

553
00:47:43,340 --> 00:47:48,310
ми заправо можемо да нађемо повезану листу да та реч припада.

554
00:47:48,310 --> 00:47:51,850
Ако је то у речнику, онда би у том канту.

555
00:47:51,850 --> 00:47:57,140
Оно што можемо да урадимо, ако је реч име наше ниске усвојен у,

556
00:47:57,140 --> 00:48:01,560
можемо само да хасх реч и поглед на повезану листу

557
00:48:01,560 --> 00:48:06,410
у вредности од Хасхтабле [хеш (реч)].

558
00:48:06,410 --> 00:48:12,410
Одатле, шта можемо да урадимо је да имамо мањи подскуп чворова за претрагу за ову реч,

559
00:48:12,410 --> 00:48:16,770
па можемо прећи повезану листу, користећи пример из раније у објашњења,

560
00:48:16,770 --> 00:48:24,110
а затим позива стринг упореди по реч где год курсор указује да,

561
00:48:24,110 --> 00:48:28,430
та реч, и видети да ли они поредити.

562
00:48:30,280 --> 00:48:35,110
У зависности од начина да организујете своје хеш функцију,

563
00:48:35,110 --> 00:48:39,260
ако је сортиран, можда ћете моћи да се врати лажно мало раније,

564
00:48:39,260 --> 00:48:43,440
али ако је то некласификовани, онда желите да наставите попречно кроз повезану листу

565
00:48:43,440 --> 00:48:46,480
док вам је последњи елемент листе.

566
00:48:46,480 --> 00:48:53,320
А ако још увек нисте нашли реч време које сте постигли крај повезану листу,

567
00:48:53,320 --> 00:48:56,890
то значи да твоја реч не постоји у речнику,

568
00:48:56,890 --> 00:48:59,410
па та реч је неважећа,

569
00:48:59,410 --> 00:49:02,730
и провера треба да се врате лажна.

570
00:49:02,730 --> 00:49:09,530
>> Сада долазимо до истовара, где желимо да ослободимо свих тачака које смо маллоц'д,

571
00:49:09,530 --> 00:49:14,050
па без свих тачака унутар нашег хеш табели.

572
00:49:14,050 --> 00:49:20,270
Ми ћемо желети да вршите итерацију над свим повезаним листама и без свих чворова у то.

573
00:49:20,270 --> 00:49:29,350
Ако погледате горе у објашњења за пример где смо ослободили повезану листу,

574
00:49:29,350 --> 00:49:35,140
онда ћете желети да понови тај процес за сваки елемент у хеш табели.

575
00:49:35,140 --> 00:49:37,780
А ја ћу због овога на крају објашњења,

576
00:49:37,780 --> 00:49:46,600
али Валгринд је алат где можете видети да ли сте правилно ослободио

577
00:49:46,600 --> 00:49:53,600
сваки чвор који сте маллоц'д или било шта друго што сте маллоц'д, свака друга показивач.

578
00:49:55,140 --> 00:50:00,530
Дакле, то је хеш табеле, где имамо ограничен број сегмената

579
00:50:00,530 --> 00:50:09,220
и хасх функција која ће се вредност, а затим доделите ту вредност на одређени корпе.

580
00:50:09,220 --> 00:50:13,340
>> Сада долазимо до покушаја.

581
00:50:13,340 --> 00:50:18,750
Покушава врсте изгледа овако, и ја ћу извући пример.

582
00:50:18,750 --> 00:50:25,630
У суштини, имате читав низ потенцијалних писама,

583
00:50:25,630 --> 00:50:29,210
и онда кад ти изградње реч,

584
00:50:29,210 --> 00:50:36,490
то писмо може бити повезан на речнику на широк спектар могућности.

585
00:50:36,490 --> 00:50:40,840
Неке речи почињу са Ц, али онда настави са,

586
00:50:40,840 --> 00:50:42,960
али други настављају са О, на пример.

587
00:50:42,960 --> 00:50:51,090
Трие је начин визуелно свих могућих комбинација тих речи.

588
00:50:51,090 --> 00:50:59,070
Трие ће пратити низа писама које чине речи,

589
00:50:59,070 --> 00:51:08,280
Гранање се када је то потребно, када се једно слово бити праћено умножак писама,

590
00:51:08,280 --> 00:51:16,630
и на крају показују у сваком тренутку да ли је реч важи или не

591
00:51:16,630 --> 00:51:30,120
јер ако сте правопис реч МАТ МА ја не мислим да је важећа реч, али је МАТ.

592
00:51:30,120 --> 00:51:37,820
И тако у трие, то би значило да након МАТ то је заправо важи реч.

593
00:51:41,790 --> 00:51:48,590
Сваки чвор у нашем трие се заправо дешава да садржи низ показивача чвора,

594
00:51:48,590 --> 00:51:52,970
и ми ћемо морати, конкретно, 27 тих чвора показивача,

595
00:51:52,970 --> 00:52:00,550
један за свако писмо у писму, као и апостроф карактера.

596
00:52:00,550 --> 00:52:10,450
Сваки елемент у том низу је и сама ће да укаже на други чвор.

597
00:52:10,450 --> 00:52:14,020
Дакле, ако је чвор је НУЛЛ, ако нема ништа после тога,

598
00:52:14,020 --> 00:52:20,550
онда знамо да нема никаквих даљих слова у тој речи низу.

599
00:52:20,550 --> 00:52:26,950
Али ако тај чвор није НУЛЛ, то значи да постоји више слова у том писму низу.

600
00:52:26,950 --> 00:52:32,160
А онда даље, сваки чвор означава да ли је то последњи знак речи или не.

601
00:52:38,110 --> 00:52:43,170
>> Идемо у један пример трие.

602
00:52:50,500 --> 00:52:58,340
Прво морам собу за 27 чворова у овом низу.

603
00:52:58,340 --> 00:53:03,200
Ако имам реч Бар -

604
00:53:13,310 --> 00:53:15,370
Ако имам реч БАР и желим да убаците да,

605
00:53:15,370 --> 00:53:22,700
прво слово Б, па ако ми трие је празна,

606
00:53:22,700 --> 00:53:29,910
Б је друго слово азбуке, тако да ћу изабрати да ставим овде на овом индексу.

607
00:53:29,910 --> 00:53:33,450
Ја ћу морати Б овде.

608
00:53:33,450 --> 00:53:42,400
Б ће бити чвор који указује на неки други низ свих могућих ликова

609
00:53:42,400 --> 00:53:45,870
да прати након писма Б.

610
00:53:45,870 --> 00:53:57,610
У овом случају, ја сам се баве речи БАР, па ће овде иде.

611
00:54:02,000 --> 00:54:08,990
После, имам писмо Р, па онда се сада показује на свом комбинацији,

612
00:54:08,990 --> 00:54:15,120
и онда Р ће бити овде.

613
00:54:15,120 --> 00:54:22,470
БАР је комплетна реч, па онда ћу морати Р тачку на другом чвору

614
00:54:22,470 --> 00:54:33,990
која каже да је реч је важећи.

615
00:54:36,010 --> 00:54:40,970
Тај чвор је такође ће имати низ чворова,

616
00:54:40,970 --> 00:54:45,260
али они могу бити НУЛЛ.

617
00:54:45,260 --> 00:54:49,080
Али у суштини, она може да настави овако.

618
00:54:49,080 --> 00:54:54,250
То ће постати мало јасније кад одемо у другу пример,

619
00:54:54,250 --> 00:54:56,780
па само носе са мном тамо.

620
00:54:56,780 --> 00:55:02,050
Сада имамо БАР унутар наше речнику.

621
00:55:02,050 --> 00:55:05,980
Сада кажу да имамо реч Баз.

622
00:55:05,980 --> 00:55:12,630
Почињемо са Б, а ми већ имамо Б као једном од писама које је у нашем речнику.

623
00:55:12,630 --> 00:55:15,170
То је праћено А. Имамо већ.

624
00:55:15,170 --> 00:55:19,250
Али онда уместо тога, имамо З следеће.

625
00:55:19,250 --> 00:55:25,490
Дакле елемент у нашој низу ће бити З

626
00:55:25,490 --> 00:55:30,810
па онда да је један ће указати на другу важећу крају речи.

627
00:55:30,810 --> 00:55:36,930
Дакле, видимо да, када ћемо наставити кроз Б, а затим,

628
00:55:36,930 --> 00:55:43,480
постоје две различите опције тренутно у нашем речнику за речи које почињу са Б и А.

629
00:55:49,650 --> 00:55:57,460
Реци ми смо желели да убаците Фообар реч.

630
00:55:57,460 --> 00:56:05,620
Тада ћемо направити унос у Ф.

631
00:56:05,620 --> 00:56:11,320
Ф је чвор који указује на читав низ.

632
00:56:11,320 --> 00:56:22,790
Ми бисмо пронашли О, идите на О, о онда повезује на целу листу.

633
00:56:22,790 --> 00:56:35,340
Имали бисмо Б и онда наставите, имали бисмо и онда Р.

634
00:56:35,340 --> 00:56:43,570
Дакле Фообар прелази скроз доле док Фообар је исправна реч.

635
00:56:43,570 --> 00:56:52,590
И тако онда ће то бити валидан реч.

636
00:56:52,590 --> 00:57:00,170
Сада кажу да наш следећи реч у речнику је заправо реч ФОО.

637
00:57:00,170 --> 00:57:03,530
Ми бисмо рекли Ф. Оно што следи Ф?

638
00:57:03,530 --> 00:57:06,190
Ја заправо већ имам простора за О, па ћу наставити.

639
00:57:06,190 --> 00:57:09,150
Не треба да се направи нови. Настави.

640
00:57:09,150 --> 00:57:15,500
ФОО је важећа реч у овом речнику, па онда ћу да укаже

641
00:57:15,500 --> 00:57:21,660
да је то исправан.

642
00:57:21,660 --> 00:57:28,370
Ако сам зауставити свој редослед, то би било тачно.

643
00:57:28,370 --> 00:57:33,050
Али, ако смо наставили наш секвенцу од Фоо до Б

644
00:57:33,050 --> 00:57:39,750
и само је ФООБ, ФООБ није реч, а то није наведено као важећег.

645
00:57:47,370 --> 00:57:57,600
У трие, ви сте сваки чвор указује да ли је валидна реч или не,

646
00:57:57,600 --> 00:58:05,840
и онда сваки чвор има низ од 27 чвора показивачи

647
00:58:05,840 --> 00:58:09,520
да онда указују на чворове самих.

648
00:58:09,520 --> 00:58:12,940
>> Овде је начин како ћете можда желети да дефинишете.

649
00:58:12,940 --> 00:58:17,260
Међутим, баш као у хеш табели пример, где смо имали чвор * главу

650
00:58:17,260 --> 00:58:21,320
да укаже на почетак нашег повезану листу, такође ћемо желети

651
00:58:21,320 --> 00:58:29,150
неки начин знајући где почетак нашег трие је.

652
00:58:29,150 --> 00:58:34,110
Неки људи позив покушава дрвеће, а то је место где корен долази.

653
00:58:34,110 --> 00:58:36,910
Дакле, ми желимо корен нашег стабла до уверите се да ћемо остати утемељено

654
00:58:36,910 --> 00:58:39,570
где год је наш трие је.

655
00:58:42,910 --> 00:58:46,300
Ми смо већ некако прешли

656
00:58:46,300 --> 00:58:50,240
начин можете да размислите о утовар сваку реч у речнику.

657
00:58:50,240 --> 00:58:54,540
У суштини, за сваку реч коју ћеш желети да вршите итерацију кроз трие

658
00:58:54,540 --> 00:58:59,590
и знајући да је сваки елемент у деце - звали смо га деца у овом случају -

659
00:58:59,590 --> 00:59:04,290
одговара другом писму, ти ћеш желети да провери те вредности

660
00:59:04,290 --> 00:59:08,320
у том индексу који одговара на писмо.

661
00:59:08,320 --> 00:59:11,260
Тако размишља скроз назад на Цезара и Вигенере,

662
00:59:11,260 --> 00:59:16,070
знајући да је свако слово можете некако мапи назад на азбучном индекс,

663
00:59:16,070 --> 00:59:20,690
Дефинитивно до З ће бити прилично лако мапирати на азбучном писму,

664
00:59:20,690 --> 00:59:25,200
али, нажалост, апострофа су прихваћена лик у речима.

665
00:59:25,200 --> 00:59:31,650
Нисам чак ни сигуран шта је АСЦИИ вредност је,

666
00:59:31,650 --> 00:59:39,250
па за то ако желите да пронађете индекс да одлучи да ли желите да буде или први

667
00:59:39,250 --> 00:59:44,550
или последњи, мораћете да направите фиксирана чек за то

668
00:59:44,550 --> 00:59:48,930
и онда стави да је у индексу 26, на пример.

669
00:59:48,930 --> 00:59:55,300
Па онда се проверава вредност код деце [и]

670
00:59:55,300 --> 00:59:58,400
где [и] одговара на било писмо сте.

671
00:59:58,400 --> 01:00:04,110
Ако је то НУЛЛ, то значи да не постоји тренутно евентуалне слова

672
01:00:04,110 --> 01:00:08,150
проистичу из тог претходног низу, тако да ћете желети да маллоц

673
01:00:08,150 --> 01:00:13,150
и направити нови чвор и има да деца [и] указују на то

674
01:00:13,150 --> 01:00:17,890
тако да стварају - када смо убаци писмо у правоугаоник -

675
01:00:17,890 --> 01:00:23,680
прављење деце нису НУЛЛ и тачка у том новом чвору.

676
01:00:23,680 --> 01:00:28,340
Али, ако то није НУЛЛ, као у нашем инстанци Фоо

677
01:00:28,340 --> 01:00:34,570
кад смо већ имали Фообар, настављамо,

678
01:00:34,570 --> 01:00:44,010
а ми не никада израду новог чвор већ само постављањем ис_ворд на истина

679
01:00:44,010 --> 01:00:47,790
на крају те речи.

680
01:00:50,060 --> 01:00:55,340
>> Дакле, тада као и раније, јер овде имате посла са сваким словом у једном тренутку,

681
01:00:55,340 --> 01:01:01,470
то ће бити лакше за вас величини, уместо да се израчуна

682
01:01:01,470 --> 01:01:06,910
и пролазе кроз целу дрвета и израчунати колико деце имам

683
01:01:06,910 --> 01:01:10,850
и онда гранања искључен, сећајући се колико су на левој страни и на десној страни

684
01:01:10,850 --> 01:01:12,850
и такве ствари, то ће бити много лакше за вас

685
01:01:12,850 --> 01:01:16,220
ако само пратите колико речи коју додајете у

686
01:01:16,220 --> 01:01:18,080
када имате посла са оптерећењем.

687
01:01:18,080 --> 01:01:22,630
И тако онда тај начин величина може само врати глобалну променљиву величину.

688
01:01:25,320 --> 01:01:28,530
>> Сада долазимо да проверите.

689
01:01:28,530 --> 01:01:33,920
Исти стандарди као пре, где желимо да омогући случај неосетљивости.

690
01:01:33,920 --> 01:01:40,400
Као, ми претпостављамо да су жице су само по азбучном карактера или су апострофа

691
01:01:40,400 --> 01:01:44,000
јер деца је низ од 27 дуго,

692
01:01:44,000 --> 01:01:48,480
па све слова алфабета плус апостроф.

693
01:01:48,480 --> 01:01:53,800
За проверите шта ћете желети да урадите је да ћете желети да почне у корену

694
01:01:53,800 --> 01:01:58,440
јер корен ће указати на низ који садржи

695
01:01:58,440 --> 01:02:01,630
свим могућим почетних слова речи.

696
01:02:01,630 --> 01:02:03,680
Идеш тамо почети,

697
01:02:03,680 --> 01:02:11,590
и онда ћеш да проверите је ова вредност НУЛЛ или не,

698
01:02:11,590 --> 01:02:16,490
јер ако је вредност НУЛЛ, то значи да се речник нема никакве вредности

699
01:02:16,490 --> 01:02:21,480
који садрже то слово у том редоследу.

700
01:02:21,480 --> 01:02:24,970
Ако је НУЛЛ, онда то значи да је реч погрешно одмах.

701
01:02:24,970 --> 01:02:27,110
Али ако то није НУЛЛ, онда можете да наставите,

702
01:02:27,110 --> 01:02:34,090
кажу да је прво слово могуће прво слово у речи,

703
01:02:34,090 --> 01:02:40,630
па сада желим да проверим да ли друго писмо, да је секвенца, је у мом речнику.

704
01:02:40,630 --> 01:02:46,540
Тако ћеш да идеш на индекс деце из првог чвора

705
01:02:46,540 --> 01:02:50,720
и проверите да ли је друго писмо постоји.

706
01:02:50,720 --> 01:02:57,440
Затим поновите тај поступак да провери да ли је редослед важи или не

707
01:02:57,440 --> 01:02:59,060
у вашој трие.

708
01:02:59,060 --> 01:03:06,430
Кад год чворова деца у том индексних поена на НУЛЛ,

709
01:03:06,430 --> 01:03:10,710
знате да редослед не постоји,

710
01:03:10,710 --> 01:03:16,230
али онда ако дођете на крај речи које сте инпуттед,

711
01:03:16,230 --> 01:03:20,070
онда желите да проверите да ли сада сам завршио ову секвенцу

712
01:03:20,070 --> 01:03:27,610
и да га нашао у мојој трие, да је реч важи или не?

713
01:03:27,610 --> 01:03:32,480
И тако онда желите да проверите да ли и тада, ако сте нашли да је редослед,

714
01:03:32,480 --> 01:03:35,120
онда желите да проверите да ли је реч важи или не

715
01:03:35,120 --> 01:03:40,290
јер сетите назад у претходном случају који сам нацртао, где смо имали ФООБ,

716
01:03:40,290 --> 01:03:48,410
који је био валидан секвенца коју смо нашли, али није стварна важи сама реч.

717
01:03:50,570 --> 01:03:59,000
>> Слично томе, за истовар у покушаја желите да истовари све чворова у вашем трие.

718
01:03:59,000 --> 01:04:04,790
Извините. Слично хеш табеле где истоваре смо ослобођени свих чворова,

719
01:04:04,790 --> 01:04:09,740
у покушаја желимо да се ослободимо свих чворова.

720
01:04:09,740 --> 01:04:15,000
Истовар ће заправо радити најлакше од дна до врха

721
01:04:15,000 --> 01:04:19,290
јер су у суштини повезане листе.

722
01:04:19,290 --> 01:04:22,540
Дакле, желимо да се уверите да се држимо све вредности

723
01:04:22,540 --> 01:04:25,700
и без свих њих експлицитно.

724
01:04:25,700 --> 01:04:28,840
Шта ћеш желети да урадите ако радите са трие

725
01:04:28,840 --> 01:04:35,640
је да путује до дна и слободног најнижи могући НОДЕ први

726
01:04:35,640 --> 01:04:39,190
и онда иде до свих тих деце, а затим без свих оних,

727
01:04:39,190 --> 01:04:43,050
иди горе и онда бесплатно, итд

728
01:04:43,050 --> 01:04:48,790
Нешто попут бави доњем слоју трие прво

729
01:04:48,790 --> 01:04:51,940
и онда иде до врха када сте ослобођени све.

730
01:04:51,940 --> 01:04:56,720
Ово је добар пример где рекурзивна функција би могла да дође у руци.

731
01:04:56,720 --> 01:05:03,830
Када ослободио доњи слој вашег трие,

732
01:05:03,830 --> 01:05:08,000
онда зовете истоваре на остатак ње,

733
01:05:08,000 --> 01:05:13,620
пазећи да ослободи сваке мини -

734
01:05:13,620 --> 01:05:16,410
Можете да замислите врста је као мини покушаја.

735
01:05:23,300 --> 01:05:28,990
Дакле, имате овде свој корен.

736
01:05:30,840 --> 01:05:35,230
Само сам га поједностављујући тако да не морам да скренем 26 од њих.

737
01:05:37,250 --> 01:05:43,770
Дакле, имате ово, а онда они представљају низове речи

738
01:05:43,770 --> 01:05:54,620
где су сви од ових малих кругова су писма која важе низови слова.

739
01:06:03,040 --> 01:06:07,160
Идемо даље само мало више.

740
01:06:15,110 --> 01:06:25,750
Шта ћеш желети да урадите је слободан доњи овде и онда слободно ово

741
01:06:25,750 --> 01:06:31,640
и онда слободно ово на дну пре него што се ослободи горњу један овде

742
01:06:31,640 --> 01:06:38,180
јер ако вас нешто бесплатно у другом нивоу овде,

743
01:06:38,180 --> 01:06:47,230
онда би заиста овде губи ову вредност.

744
01:06:47,230 --> 01:06:54,780
Зато је важно у истовари за трие како би били сигурни да сте слободни прво дно.

745
01:06:54,780 --> 01:06:59,480
Оно што можда желите да урадите је рећи за сваки чвор

746
01:06:59,480 --> 01:07:06,430
Желим да истовари све деце.

747
01:07:16,060 --> 01:07:22,140
>> Сада када смо прошли током истовара за хеш табеле методу као и трие метод,

748
01:07:22,140 --> 01:07:27,020
ћемо желети да погледате Валгринд.

749
01:07:27,020 --> 01:07:29,640
Валгринд наиђете са следећим командама.

750
01:07:29,640 --> 01:07:32,700
Имате Валгринд-В.

751
01:07:32,700 --> 01:07:40,960
Ти провера за све цури када покренете Спеллер дао овај текст сигурно

752
01:07:40,960 --> 01:07:46,980
јер буквар треба да узме у текстуалној датотеци.

753
01:07:46,980 --> 01:07:52,330
Тако Валгринд ће покренути ваш програм, да вам кажем колико бајтова си издвојила,

754
01:07:52,330 --> 01:07:57,150
колико бајтова си ослобођен, а он ће вам рећи да ли сте довољно ослобођен

755
01:07:57,150 --> 01:07:58,930
или да нисте слободни довољно,

756
01:07:58,930 --> 01:08:02,850
или понекад можете чак превише слободно, као слободан чвор који је већ ослобођен

757
01:08:02,850 --> 01:08:05,140
и тако ће вам вратити грешке.

758
01:08:05,140 --> 01:08:11,600
Ако користите Валгринд, то ће вам дати неке поруке

759
01:08:11,600 --> 01:08:15,970
указујући да ли сте или ослобођен мање него довољно, сасвим довољно,

760
01:08:15,970 --> 01:08:19,609
или више него довољно времена.

761
01:08:24,370 --> 01:08:30,410
>> Део овог псет, то је опционо да оспори Тхе Биг одбор.

762
01:08:30,410 --> 01:08:35,790
Али када се бавимо овим структурама података

763
01:08:35,790 --> 01:08:40,689
то је некако забавно да види колико брзо и колико ефикасно да ваше структуре података бити.

764
01:08:40,689 --> 01:08:44,490
Да ли ваш хасх функција резултат у много судара?

765
01:08:44,490 --> 01:08:46,300
Или је ваша величина подаци стварно велика?

766
01:08:46,300 --> 01:08:49,420
Да ли је потребно доста времена да прођу?

767
01:08:49,420 --> 01:08:54,800
У дневнику Спеллер, она излази колико времена се користи за учитавање,

768
01:08:54,800 --> 01:08:57,700
да проверите да спроведе величину, и да истовари,

769
01:08:57,700 --> 01:09:00,720
па они су послали у Тхе Биг одбора,

770
01:09:00,720 --> 01:09:03,600
где можете такмичити против својих другара

771
01:09:03,600 --> 01:09:11,350
и неки чланови особља да видимо ко има најбржи провере правописа.

772
01:09:11,350 --> 01:09:14,760
Једна ствар коју бих желео да напоменути о хеш табеле

773
01:09:14,760 --> 01:09:20,470
је да постоје неке прилично једноставне хеш функције које смо могли замислити.

774
01:09:20,470 --> 01:09:27,240
На пример, имате 26 канте, па сваки кашика

775
01:09:27,240 --> 01:09:30,200
одговара првом слову у речи,

776
01:09:30,200 --> 01:09:35,229
али да ће то довести у прилично неуравнотеженог хеш табели

777
01:09:35,229 --> 01:09:40,979
јер постоји много мање речи које почињу са Кс од почетка са М, на пример.

778
01:09:40,979 --> 01:09:47,890
Један од начина да се о Спеллер је ако желите да добијете све друге функционалности доле,

779
01:09:47,890 --> 01:09:53,240
онда само користити једноставне хеш функцију да бисте могли да добијете ваш код ради

780
01:09:53,240 --> 01:09:58,650
и онда се вратите и мењају величину хеш табеле и дефинисање.

781
01:09:58,650 --> 01:10:03,430
Постоји много ресурса на интернету за хеш функције,

782
01:10:03,430 --> 01:10:08,250
па за ову псет вам је дозвољено да истражују хеш функције на Интернету

783
01:10:08,250 --> 01:10:15,560
за неке савете и инспирацију све док се уверите да наведу где сте га добили од.

784
01:10:15,560 --> 01:10:22,060
Ви сте добродошли да погледате и интерпретира неке хасх функцију коју ћете наћи на Интернету.

785
01:10:22,060 --> 01:10:27,460
Назад на то, можда ћете моћи да видите да ли је неко користио трие

786
01:10:27,460 --> 01:10:31,700
да ли је њихово спровођење је брже од хасх табеле или не.

787
01:10:31,700 --> 01:10:35,290
Можете да поднесе Тхе Биг одбор више пута.

788
01:10:35,290 --> 01:10:37,660
Она ће снимити свој најновији унос.

789
01:10:37,660 --> 01:10:44,300
Дакле, можда сте променили своје хеш функцију и онда схвате да је то заправо много брже

790
01:10:44,300 --> 01:10:46,780
или много спорије него раније.

791
01:10:46,780 --> 01:10:50,960
То је помало забаван начин.

792
01:10:50,960 --> 01:10:57,190
Увек има 1 или 2 члана особља који покушавају да направе најспорији могући речник,

793
01:10:57,190 --> 01:11:00,210
тако да је увек забавно гледати.

794
01:11:00,210 --> 01:11:07,630
>> Употреба за псет је да покренете Спеллер са опционим речника

795
01:11:07,630 --> 01:11:12,840
и онда обавезно текст фајл.

796
01:11:12,840 --> 01:11:18,380
Уобичајено је да када покренете Спеллер са само текст фајла, а не одредите речник,

797
01:11:18,380 --> 01:11:24,410
то ће користити датотеку речника текста, велики један

798
01:11:24,410 --> 01:11:27,920
у цс50/псет5/дицтионариес фасцикли.

799
01:11:27,920 --> 01:11:32,760
Тај има преко 100.000 речи.

800
01:11:32,760 --> 01:11:37,950
Они такође имају малу речник који има знатно мање речи

801
01:11:37,950 --> 01:11:40,730
да ЦС50 је направио за тебе.

802
01:11:40,730 --> 01:11:44,050
Међутим, можете врло лако само да свој речник

803
01:11:44,050 --> 01:11:47,150
Ако желите само да се ради у малим примерима -

804
01:11:47,150 --> 01:11:51,140
На пример, ако желите да користите ГДБ и знате конкретне вредности

805
01:11:51,140 --> 01:11:53,560
да желите да се ваш хеш табела мапирати на.

806
01:11:53,560 --> 01:12:00,430
Дакле, можете само да направите сопствену текстуални фајл само са БАР, Баз, Фоо и Фообар,

807
01:12:00,430 --> 01:12:04,860
чине да се у текстуалној датотеци, одвојите оне свака са 1 линијом,

808
01:12:04,860 --> 01:12:12,670
и онда направите сопствену текстуални фајл који садржи буквално само мозда 1 или 2 речи

809
01:12:12,670 --> 01:12:15,950
тако да знате тачно шта излаз треба да буде.

810
01:12:15,950 --> 01:12:21,870
Неке од датотека узорак текста који ће Биг одбор када покренете изазов проверите

811
01:12:21,870 --> 01:12:25,580
Рат и мир су и роман Џејн Остин, или нешто слично томе.

812
01:12:25,580 --> 01:12:30,450
Дакле, када сте почетник, то је много лакше направити сопствене текстуалне датотеке

813
01:12:30,450 --> 01:12:34,160
који садржи само неколико речи, или можда 10

814
01:12:34,160 --> 01:12:38,280
тако да можете предвидети шта исход би требало да буде

815
01:12:38,280 --> 01:12:42,880
и онда провери против тога, тако да више од контролисаног пример.

816
01:12:42,880 --> 01:12:45,820
И тако, јер се бавимо предвиђању и цртање ствари око себе,

817
01:12:45,820 --> 01:12:48,690
Поново желим да вас охрабри да користите оловку и папир

818
01:12:48,690 --> 01:12:50,700
јер заиста ће ти помоћи са овим -

819
01:12:50,700 --> 01:12:55,620
цртање стрелице, како хеш табела или како ваша трие изгледа,

820
01:12:55,620 --> 01:12:57,980
када сте ослобађање нешто где стрелице се дешава,

821
01:12:57,980 --> 01:13:01,730
ви држите на довољно, да ли видите неке везе нестају

822
01:13:01,730 --> 01:13:05,750
и пада у амбис процурио меморије.

823
01:13:05,750 --> 01:13:11,070
Зато вас молим, покушајте да се скрене ствари чак и пре него што дођете до писања кода доле.

824
01:13:11,070 --> 01:13:14,520
Жреб ствари, тако да сте схватили како ствари иду на посао

825
01:13:14,520 --> 01:13:22,750
јер онда ја гарантујем да ћете налетети на мање показивач муддлес тамо.

826
01:13:24,270 --> 01:13:25,910
>> У реду.

827
01:13:25,910 --> 01:13:28,780
Желим да вам пожелим много среће са овом псет.

828
01:13:28,780 --> 01:13:31,980
То је вероватно најтежи један.

829
01:13:31,980 --> 01:13:40,360
Дакле, покушајте да покренете рано, цртање ствари, цртају ствари, и добре среће.

830
01:13:40,360 --> 01:13:42,980
Ово је Валктхроугх 5.

831
01:13:45,160 --> 01:13:47,000
>> [ЦС50.ТВ]