1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Walkthrough - Проблем Постави 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Чан - Универзитетот Харвард]

3
00:00:04,870 --> 00:00:07,190
[Ова е CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Во ред. Здраво на сите, и добредојде да можи 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 е спелувањето грешки, во која ќе се прави магија-Проверка на.

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
а потоа уште завршуваат добивање на многу сјај Раде како D или D =

10
00:00:33,120 --> 00:00:39,390
и сите, бидејќи вие сте liverwurst спојлер во кит широк збор.

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
Јас бев еднаш изјави од страна на моите Sith одделение мачителот дека никогаш нема да влезат во добар колега.

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
Jale, или затвор - знаеш, во затворот, Њу Џерси.

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, во која ќе се зборува за pset5: Грешките во правописот,

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
Ние сме всушност ќе треба да се има повеќе. В датотеки, кои заедно прават нашите pset.

27
00:02:01,500 --> 00:02:05,420
И така гледајќи низ различни аспекти, иако ние, всушност, не уредување

28
00:02:05,420 --> 00:02:10,770
еден од датотеки, speller.c, знаејќи како тоа функционира со однос на dictionary.c,

29
00:02:10,770 --> 00:02:14,100
кои ќе бидат писмено, се случува да биде многу важно.

30
00:02:14,100 --> 00:02:16,970
Спец pset исто така, содржи многу корисни информации

31
00:02:16,970 --> 00:02:21,360
во однос на она што може да се претпостави, правила и работи како што,

32
00:02:21,360 --> 00:02:24,710
па не заборавајте да го прочитате pset спецификации внимателно за совети.

33
00:02:24,710 --> 00:02:29,310
И кога се двоумите на некое правило или нешто слично, тогаш секогаш се однесуваат на pset спецификации

34
00:02:29,310 --> 00:02:31,550
или да дискутирате.

35
00:02:31,550 --> 00:02:34,060
Ова pset се случува да се потпираат на покажувачи,

36
00:02:34,060 --> 00:02:37,890
затоа сакаме да се осигураме дека можеме се разбере разликата помеѓу додавајќи ѕвезди

37
00:02:37,890 --> 00:02:41,680
пред името на покажувачот и ampersands, како да ги ослободи, итн

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
Значи ние сакаме да се осигураме дека нема покажувачот се враќа unfreed, дека ние немаме меморија протекување.

52
00:03:42,910 --> 00:03:48,330
Ние ќе се воведе алатка наречена Valgrind кој работи вашата програма

53
00:03:48,330 --> 00:03:52,260
и проверува дали сите меморија, која ви распределени потоа ослободени.

54
00:03:52,260 --> 00:03:59,080
Вашиот pset е само заврши кога таа работи и има целосна функционалност,

55
00:03:59,080 --> 00:04:03,990
но, исто така, Valgrind ви кажува дека не сум нашол некое меморија протекување.

56
00:04:03,990 --> 00:04:06,690
Конечно, за овој pset, навистина сакам да го истакнам -

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
секогаш ќе се укаже NULL.

71
00:05:02,340 --> 00:05:08,230
Кога еден јазол поени во NULL, тогаш знаете дека сте стигнале до крајот на листата,

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
И за да можете да видите тука, на јазол Д ќе укаже на NULL, бидејќи тоа е последниот елемент во листата.

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
ова ќе стане typedef struct

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
Еве, ние имаме typedef struct јазол.

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
и во овој случај, тоа е покажувач кон еден јазол, па ние имаме struct јазол * наречен следната.

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
Друг заеднички начин да го именува ова ќе биде iterator или нешто слично

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
Да го сторат тоа, за да пристапите на вредности во внатрешноста на struct, имаме точка оператор.

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
Ако тоа е int јазол, тогаш курсорот-> вредноста е само ќе биде цел број.

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
Ова е само дел од кодот каде што можете да iterate.

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
Сега ние се дозволени да се ослободи што се чуваат во Temp,

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
и проверете дали тоа е некој што укажува на NULL, проверете во секое време,

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
како и моите iterator, и работи како што.

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
или iterator.

212
00:17:08,670 --> 00:17:14,640
Ние сме процесирањето додека курсорот е NULL.

213
00:17:14,640 --> 00:17:17,640
Вие не сакате да iterate кога курсорот е NULL

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
да се најде каде што на тековната крајот на поврзани листа е, па без разлика кој јазол е да се покажува на NULL -

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
И така карактеристична за последниот јазол во поврзани листа е тоа што укажува на NULL.

229
00:18:56,080 --> 00:19:09,380
Па тогаш што ќе треба да направите е да поставите покажувачот овој црвено човек да NULL. Таму.

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
Прво ќе забележиме дека имаме оваа Makefile тука,

289
00:24:58,850 --> 00:25:03,040
кои не сме навистина се соочуваат порано.

290
00:25:03,040 --> 00:25:10,090
Ако сте виделе внатрешноста на pset5 папка, ќе забележите дека имате. Ж датотека,

291
00:25:10,090 --> 00:25:12,530
тогаш имаш две. в датотеки.

292
00:25:12,530 --> 00:25:18,920
Што ова Makefile не е порано, ние само би внеси го направи, а потоа името на програмата

293
00:25:18,920 --> 00:25:25,550
и тогаш ќе видите сите овие аргументи и знамињата донесен во на компајлерот.

294
00:25:25,550 --> 00:25:30,580
Што Makefile не е ни овозможува да ги собере неколку датотеки одеднаш

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
Имаме speller.c и dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Вие сте добредојдени да ги уредувате Makefile ако сакате.

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
Таа ги отстранува сите exe фајлови и. O датотеки.

306
00:26:27,900 --> 00:26:30,220
>> Ајде да ги разгледаме во dictionary.h.

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
Ние немаме вистински имплементација, бидејќи тоа е она што ќе се прави за овој pset.

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
Еве ние се провери, кој враќа true ако даден збор е во речникот.

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
>> Ајде да ги разгледаме во dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Ќе видиме дека таа изгледа многу слично на dictionary.h, освен сега тоа само ги има сите овие Todos во неа.

328
00:28:10,490 --> 00:28:16,980
И така тоа е вашата работа. Конечно, ќе се пополнување speller.c со сите на овој код.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, кога работи, не е навистина се случува да се направи нешто,

330
00:28:21,540 --> 00:28:29,590
па ние со нетрпение кон speller.c да се види фактичката имплементација на магија-Проверка на.

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
rusage занимава со време, бидејќи дел од овој pset кои ние ќе се справи со подоцна

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
И така тогаш тоа е каде rusage се случува да дојде внатре

342
00:29:22,040 --> 00:29:28,740
Еве, гледаме првиот повик на еден од нашите dictionary.c датотеки, кој е товарот.

343
00:29:28,740 --> 00:29:34,720
Оптоварување враќа точно или неточно - вистински врз успехот, лажни врз неуспех.

344
00:29:34,720 --> 00:29:41,400
Значи, ако во речникот не е натоварен правилно, тогаш speller.c ќе се врати 1 и се повлече.

345
00:29:41,400 --> 00:29:47,920
Но, ако тоа се вчита правилно, тогаш тоа ќе продолжи.

346
00:29:47,920 --> 00:29:50,740
Ние продолжуваме, и можеме да видиме некои датотека I / O тука,

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
Значи она што speller.c прави токму тука е процесирањето над секој од зборовите во текстуална датотека

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
>> Нашата задача за оваа pset е да се имплементира оптоварување, што ќе внесе речникот

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
Значи speller.c поминува во низа, а потоа мора да се провери дали стрингот

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
но во овој pset, во основа било кој речник донесен во кој било јазик.

378
00:32:53,020 --> 00:32:57,040
Па ние не може само да се претпостави дека зборот на е внатре.

379
00:32:57,040 --> 00:33:03,090
Зборот foobar може да се дефинира во одреден речник што помине внатре

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
и на крајот се зборува за некои општи совети кога сте правење на pset

385
00:33:22,720 --> 00:33:27,870
а исто така и како може да биде во можност да го користите Valgrind да се провери за меморија протекување.

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
Тоа е int хаш табелата.

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
сте ќе сакате она што се нарекува hash функција

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
Така да твојот hash функција ќе се потпрам на тоа да се утврди кои кофа секој клуч оди во

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
Така да твојот hash функција враќа индекс на низата

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
кога hashed, ќе се врати истиот индекс.

458
00:39:46,950 --> 00:39:53,620
Значи, кога ќе се занимаваат со зборови, со еден збор кога hashed

459
00:39:53,620 --> 00:39:57,450
ќе бидат исти hash вредност како друг збор.

460
00:39:57,450 --> 00:40:04,140
Тоа е она што ние го нарекуваме судир, кога имаме еден јазол, кога hashed,

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
Значи, кога сте правење на вашиот pset, обидете се да се позанимавам

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
>> Што оптоварување се случува да направите е да iterate над секој збор во речникот.

477
00:41:09,500 --> 00:41:13,180
Поминува покажувачот на речникот датотека.

478
00:41:13,180 --> 00:41:18,050
Значи сте ќе треба да ги искористат предностите на датотека I / O функции кои ви владее во pset4

479
00:41:18,050 --> 00:41:23,010
и iterate над секој збор во речникот.

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
Еве јас го повикувам мојот јазол покажувачот new_node и јас сум mallocing што? Големината на еден јазол.

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
е во функција fscanf,

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
и вид на излупени слоеви врати на библиотеката CS50,

492
00:42:29,320 --> 00:42:33,430
видовме имплементација на fscanf таму.

493
00:42:33,430 --> 00:42:37,700
Да се ​​вратиме на fscanf, имаме датотека која ние ја читаш од,

494
00:42:37,700 --> 00:42:42,570
ние сме во потрага по низа во таа датотека, а потоа ние тоа ставање во

495
00:42:42,570 --> 00:42:48,340
тука имам new_node-> зборот, бидејќи new_node е еден јазол покажувач,

496
00:42:48,340 --> 00:42:50,380
не е вистински јазол.

497
00:42:50,380 --> 00:42:57,100
Па тогаш сакам да кажам дека new_node, сакам да одам на јазол дека тоа укажува на

498
00:42:57,100 --> 00:43:01,190
а потоа му ја додели таа вредност во Word.

499
00:43:01,190 --> 00:43:08,540
Ние сакаме да тогаш земи тој збор и вметнете ја во хеш табелата.

500
00:43:08,540 --> 00:43:13,750
Сфатат дека ние направивме new_node еден јазол покажувачот

501
00:43:13,750 --> 00:43:18,230
бидејќи ние ќе сакаат да знаат што адресата на тој јазол е

502
00:43:18,230 --> 00:43:23,940
кога ќе го вметнете во затоа структурата на јазли себе, на struct,

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
Таа адреса ќе биде new_node.

506
00:43:34,550 --> 00:43:42,140
Дали тоа има смисла, зошто правиме new_node еден јазол * што е спротивно на јазол?

507
00:43:43,700 --> 00:43:45,700
Во ред.

508
00:43:45,700 --> 00:43:52,840
Имаме збор. Таа вредност е new_node-> зборот.

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
каде што број е индекс каде Hashtable во тој индекс претставува дека кофа.

513
00:44:12,090 --> 00:44:18,260
Ние сакаме да се земе дека индексот, а потоа одат за тоа индексот на хаш табелата

514
00:44:18,260 --> 00:44:26,960
а потоа ја користат таа поврзани листа за да вметнете јазол во new_node.

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
или на почетокот или на крајот, само бидете сигурни дека вашата последна јазол секогаш укажува на NULL

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
а потоа iterate преку секоја поврзани листа во рамките на хаш табелата

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
Значи, ако имате еден збор со апостроф S, тоа е вистински легитимен збор во вашиот речник

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
така што секој единствен збор е секогаш hashed со иста вредност,

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
на вредноста на Hashtable [хаш (зборот)].

558
00:48:06,410 --> 00:48:12,410
Од таму, она што можеме да направиме е имаме помали подмножество на јазли за пребарување за овој збор,

559
00:48:12,410 --> 00:48:16,770
и така ние може да напречни поврзани листа, со користење на пример од почетокот на Walkthrough,

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
>> Сега доаѓаме да се исклучи, каде што сакате да ги ослободи сите на јазли кои имаме malloc'd,

571
00:49:09,530 --> 00:49:14,050
така слободно сите јазли во внатрешноста на нашите хаш табелата.

572
00:49:14,050 --> 00:49:20,270
Ние ќе сакате да iterate во текот на сите поврзани листи и бесплатни на сите јазли во тоа.

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
И јас ќе одам во текот на овој кон крајот на Walkthrough,

576
00:49:37,780 --> 00:49:46,600
но Valgrind е алатка каде што можете да видите дали сте правилно ослободен

577
00:49:46,600 --> 00:49:53,600
секој јазол дека сте malloc'd или нешто друго што сте malloc'd, сите други покажувач.

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
Некои зборови започне со C, но потоа продолжи со A,

586
00:50:40,840 --> 00:50:42,960
но другите продолжуваат со O, на пример.

587
00:50:42,960 --> 00:50:51,090
А Trie е начин на визуелизација на сите можни комбинации на овие зборови.

588
00:50:51,090 --> 00:50:59,070
А Trie се случува да ги пратите на редоследот на буквите кои го сочинуваат зборови,

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
бидејќи ако сте правопис на зборот МАТ, MA јас не мислам дека е валидна збор, но МАТ е.

592
00:51:30,120 --> 00:51:37,820
И така во вашиот Trie, тоа ќе значи дека по МАТ тоа е всушност валидна збор.

593
00:51:41,790 --> 00:51:48,590
Секој јазол во нашата Trie е, всушност, ќе содржи низа на јазол покажувачи,

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
Значи, ако тој јазол е NULL, ако нема ништо после тоа,

598
00:52:14,020 --> 00:52:20,550
тогаш знаеме дека нема повеќе букви во тој збор низа.

599
00:52:20,550 --> 00:52:26,950
Но, ако тој јазол не е NULL, тоа значи дека постојат повеќе букви во тоа писмо секвенца.

600
00:52:26,950 --> 00:52:32,160
А потоа понатаму, секој јазол покажува дали тоа е последниот карактер на зборот или не.

601
00:52:38,110 --> 00:52:43,170
>> Ајде да одиме во еден пример на Trie.

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
првата буква е Б, па ако ми Trie е празна,

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
По, имам писмо R, па потоа А сега укажува на своја комбинација,

612
00:54:08,990 --> 00:54:15,120
а потоа R ќе биде тука.

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
но тие би можеле да бидат NULL.

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
Но, тогаш, наместо тоа, имаме Z следниве.

625
00:55:19,250 --> 00:55:25,490
Па тогаш елемент во нашата низа ќе биде Z,

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
постојат две различни опции во моментов во нашата речник за зборови што почнуваат со B и A.

629
00:55:49,650 --> 00:55:57,460
Велат сакавме да внесете зборот foobar.

630
00:55:57,460 --> 00:56:05,620
Тогаш ние ќе го направи влез во Ф

631
00:56:05,620 --> 00:56:11,320
F е еден јазол што укажува на цела низа.

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
Па тогаш foobar преминува на целиот пат до foobar е точниот збор.

635
00:56:43,570 --> 00:56:52,590
И така тогаш ова ќе биде валидна збор.

636
00:56:52,590 --> 00:57:00,170
Сега велат нашите следниот збор во речникот е всушност зборот foo.

637
00:57:00,170 --> 00:57:03,530
Ние би рекол Ф Она што следува F?

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
Foo е валидна збор во овој речник, па потоа јас ќе одам да укажуваат

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
Но, ако ние продолживме нашата низа од FOO до Б

644
00:57:33,050 --> 00:57:39,750
и само имаше FOOB, FOOB не е збор, а тоа не е означено како валидна.

645
00:57:47,370 --> 00:57:57,600
Во Trie, имате секој јазол означува дали тоа е валидна збор или не,

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
некој начин на знаејќи каде на почетокот на нашата Trie е.

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
до каде нашите Trie е.

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
Во суштина, за секој збор што сте ќе сакате да iterate преку вашиот Trie

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
Толку размислување на целиот пат назад кон Цезар и Vigenere,

662
00:59:11,260 --> 00:59:16,070
знаејќи дека секоја буква можете вид на мапа назад кон индекс азбучен,

663
00:59:16,070 --> 00:59:20,690
дефинитивно преку Z ќе биде прилично лесно да се мапираат со азбучен писмо,

664
00:59:20,690 --> 00:59:25,200
но за жал, апостровите се исто така прифатена карактер со зборови.

665
00:59:25,200 --> 00:59:31,650
Јас не сум сигурен дека дури и она што ASCII вредност е,

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
Па тогаш сте проверка на вредноста на деца [i]

670
00:59:55,300 --> 00:59:58,400
каде што [i] соодветствува на она писмо сте на.

671
00:59:58,400 --> 01:00:04,110
Ако тоа е NULL, што значи дека во моментов не е било можно букви

672
01:00:04,110 --> 01:00:08,150
произлегуваат од таа претходната секвенца, па сте ќе сакате да Примерок

673
01:00:08,150 --> 01:00:13,150
и направи нов јазол и дека имаат деца [i] точка за да ја

674
01:00:13,150 --> 01:00:17,890
така што ќе се создаде - кога вметнува писмо во правоаголникот -

675
01:00:17,890 --> 01:00:23,680
што децата не-NULL и точка во која нов јазол.

676
01:00:23,680 --> 01:00:28,340
Но, ако тоа не е NULL, како во нашата пример на foo

677
01:00:28,340 --> 01:00:34,570
кога ние веќе foobar, ќе продолжиме,

678
01:00:34,570 --> 01:00:44,010
и ние не сме воопшто да прави нов јазол туку само поставување is_word на true

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
а потоа ви се случува да се провери е оваа вредност NULL или не,

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
Ако тоа е NULL, тогаш тоа значи дека зборот е погрешно напишан веднаш.

701
01:02:24,970 --> 01:02:27,110
Но, ако тоа не е NULL, тогаш може да се продолжи,

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
во рамките на вашиот Trie.

708
01:02:59,060 --> 01:03:06,430
Секогаш кога јазол деца во тоа индексни поени во NULL,

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
и ја најдов во мојот Trie, е дека зборот валидни или не?

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
бидејќи сеќавам назад во претходниот случај дека јас привлече каде имавме FOOB,

716
01:03:40,290 --> 01:03:48,410
тоа беше валидна секвенца која најдовме, но не беше вистински валидна самата збор.

717
01:03:50,570 --> 01:03:59,000
>> Слично на тоа, за истовар во обиди дека сакате да го бриши сите јазли во вашиот Trie.

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
Што ви се случува да сакате да направите, ако си работат со Trie

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
Вид на како се занимаваат со долниот слој на Trie првиот

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
Откако ќе ослободи долниот слој на вашиот Trie,

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
Тоа е причината зошто е важно во бриши за Trie да бидете сигурни дека ќе се ослободи дното во прв план.

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
>> Сега дека ние сме поминале над бриши за хаш табелата метод, како и начинот Trie,

748
01:07:22,140 --> 01:07:27,020
ние ќе сакате да се погледне во Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind трчате со следниве команди.

750
01:07:29,640 --> 01:07:32,700
Имате valgrind-V.

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
Значи Valgrind ќе се кандидира на вашиот програма, да ти кажам колку бајти можете распределени,

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
Ако користите Valgrind, тоа ќе ви даде некои пораки

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
>> Дел од оваа pset, тоа е задолжително да се спротивстават на Биг одбор.

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
бидејќи постојат многу помалку зборови што почнуваат со X од почеток со M, на пример.

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
и така за оваа pset ви е дозволено да истражување хаш функциите на интернет

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
Назад кон тоа, може да биде во можност да се види дали некој користи Trie

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
Па можеби ќе го промените вашиот hash функција и потоа сфаќаат дека тоа е всушност многу побрзо

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
>> Користењето на pset е да извршите правопис со изборен речникот

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
во cs50/pset5/dictionaries папка.

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
дека CS50 има направено за вас.

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
На пример, ако сакате да го користите gdb и знаеш специфични вредности

805
01:11:51,140 --> 01:11:53,560
што сакате вашиот хаш табелата да планирам да.

806
01:11:53,560 --> 01:12:00,430
Така што само може да се направи свој текст датотека само со БАР, Баз, foo, а foobar,

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
цртање на стрели, како хеш табелата или како вашиот Trie изгледа,

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
затоа што тогаш јас гарантирам дека ќе работи во помалку покажувачот muddles таму.

826
01:13:24,270 --> 01:13:25,910
>> Во ред.

827
01:13:25,910 --> 01:13:28,780
Сакам да ви посакам многу среќа со овој pset.

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
>> [CS50.TV]