1
00:00:00,000 --> 00:00:12,350
>> [Музыка гуляе]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN: Прывітанне.

3
00:00:13,050 --> 00:00:13,640
Я Роб.

4
00:00:13,640 --> 00:00:16,210
І давайце гэта рашэнне па-за.

5
00:00:16,210 --> 00:00:20,070
І вось мы збіраемся рэалізаваць
Агульная табліца.

6
00:00:20,070 --> 00:00:24,090
Мы бачым, што структура вузел Нашы
табліца будзе выглядаць наступным чынам.

7
00:00:24,090 --> 00:00:28,710
Так што гэта будзе мець сЬаг слова
Масіў Памер + 1.

8
00:00:28,710 --> 00:00:32,259
Не забывайце, + 1, паколькі максімальная
слова ў слоўніку 45

9
00:00:32,259 --> 00:00:33,130
знакаў.

10
00:00:33,130 --> 00:00:37,070
А потым мы збіраемся трэба адзін дадатковы
сімвал для нуля зваротнай касой.

11
00:00:37,070 --> 00:00:40,870
>> А потым наш хэш ў кожным
вядро збіраецца захоўваць

12
00:00:40,870 --> 00:00:42,320
звязаны спіс вузлоў.

13
00:00:42,320 --> 00:00:44,420
Мы не робім лінейную зандзіравання тут.

14
00:00:44,420 --> 00:00:48,430
І таму для таго, каб звязаць да наступнага
элемент у вядро, мы павінны

15
00:00:48,430 --> 00:00:50,390
структура вузла * наступны.

16
00:00:50,390 --> 00:00:51,110
ОК.

17
00:00:51,110 --> 00:00:53,090
Дык вось што вузел выглядае.

18
00:00:53,090 --> 00:00:56,180
>> Цяпер вось дэкларацыя
нашай хэш-табліцы.

19
00:00:56,180 --> 00:00:59,640
Гэта будзе мець 16834 вёдраў.

20
00:00:59,640 --> 00:01:01,910
Але гэта лік не мае значэння.

21
00:01:01,910 --> 00:01:05,450
І, нарэшце, мы збіраемся мець
глабальная пераменная памер хэш, які

22
00:01:05,450 --> 00:01:07,000
збіраецца пачаць як нуль.

23
00:01:07,000 --> 00:01:10,760
І гэта будзе адсочваць, як
шмат слоў у нашым слоўніку.

24
00:01:10,760 --> 00:01:13,710
>> Так што давайце зірнем на нагрузцы.

25
00:01:13,710 --> 00:01:16,390
Звярніце ўвагу, што нагрузкі, яна вяртае лагічнае значэнне.

26
00:01:16,390 --> 00:01:20,530
Вы вяртаецеся дакладна, калі гэта было паспяхова
загружаныя, і ў адваротным выпадку.

27
00:01:20,530 --> 00:01:23,990
І гэта займае канстантнасцю сімвал * слоўнік,
які з'яўляецца слоўнік

28
00:01:23,990 --> 00:01:25,280
што мы хочам адкрыць.

29
00:01:25,280 --> 00:01:27,170
Дык вось першае, што
мы збіраемся зрабіць.

30
00:01:27,170 --> 00:01:29,500
>> Мы збіраемся адкрыць паток,
слоўнік для чытання.

31
00:01:29,500 --> 00:01:31,680
І мы збіраемся мець, каб зрабіць
упэўнены, што гэта атрымалася.

32
00:01:31,680 --> 00:01:35,920
Так што, калі ён вярнуўся NULL, то мы не зрабілі
паспяхова адкрыць слоўнік.

33
00:01:35,920 --> 00:01:37,440
І мы павінны вярнуцца ілжывым.

34
00:01:37,440 --> 00:01:41,580
Але калі выказаць здагадку, што гэта было паспяхова
адкрыта, то мы хочам, каб прачытаць

35
00:01:41,580 --> 00:01:42,400
слоўнік.

36
00:01:42,400 --> 00:01:46,450
Так што трымаеце цыкл, пакуль не знойдзем некаторыя
Прычына, каб вырвацца з гэтага цыклу,

37
00:01:46,450 --> 00:01:47,570
якія мы ўбачым.

38
00:01:47,570 --> 00:01:48,920
Так што трымаеце цыклу.

39
00:01:48,920 --> 00:01:51,780
>> І зараз мы збіраемся
Malloc адзін вузел.

40
00:01:51,780 --> 00:01:54,020
І, вядома, мы павінны
праветрываць праверце яшчэ раз.

41
00:01:54,020 --> 00:01:58,680
Так што калі mallocing не ўдалося, то
мы хочам, каб разгрузіць любы вузел, які мы

42
00:01:58,680 --> 00:02:02,590
здарылася з Таноса раней, зачыніць
слоўнік і вярнуцца ілжывым.

43
00:02:02,590 --> 00:02:06,830
Але ігнаруючы, што, мяркуючы, што мы
атрымалася, то мы хочам выкарыстоўваць fscanf

44
00:02:06,830 --> 00:02:12,400
чытаць ні аднаго слова з нашага
слоўнік у нашу вузла.

45
00:02:12,400 --> 00:02:17,940
Так што памятаеце, што ўступленне> слова з'яўляецца сімвал
Слова буфер памерам Lenghth + 1

46
00:02:17,940 --> 00:02:20,300
што мы збіраемся захоўваць слова цалі

47
00:02:20,300 --> 00:02:25,070
>> Так fscanf збіраецца вяртаць 1, да тых часоў,
, Як гэта было ў стане паспяхова

48
00:02:25,070 --> 00:02:26,750
прачытаць слова з файла.

49
00:02:26,750 --> 00:02:30,460
Калі адзін адбываецца памылка, або мы
дойдзе да канца файла, то

50
00:02:30,460 --> 00:02:31,950
не верне 1.

51
00:02:31,950 --> 00:02:35,180
У гэтым выпадку ён не вяртае 1,
мы, нарэшце, збіраецца вырвацца з

52
00:02:35,180 --> 00:02:37,280
гэта ў той час як пятля.

53
00:02:37,280 --> 00:02:42,770
Такім чынам, мы бачым, што як толькі ў нас ёсць паспяхова
чытаць слова ў

54
00:02:42,770 --> 00:02:48,270
запіс> слова, тое, што мы збіраемся, што
слова з дапамогай нашага хэш-функцыю.

55
00:02:48,270 --> 00:02:49,580
>> Давайце зірнем на
хэш-функцыя.

56
00:02:49,580 --> 00:02:52,430

57
00:02:52,430 --> 00:02:55,610
Такім чынам, вы сапраўды не трэба
каб зразумець гэта.

58
00:02:55,610 --> 00:02:59,460
А на самай справе мы проста выцягнуў гэты хэш
функцыянаваць з Інтэрнэту.

59
00:02:59,460 --> 00:03:04,010
Адзінае, што вы павінны прызнаць гэта
што гэта займае канстантнасцю сімвал * слова.

60
00:03:04,010 --> 00:03:08,960
Дык гэта займае радок у якасці ўваходных дадзеных, і
вяртання без знака Int як выхад.

61
00:03:08,960 --> 00:03:12,360
Так што ўсё хэш-функцыя, гэта
прымае ў якасці ўваходных дадзеных і дае

62
00:03:12,360 --> 00:03:14,490
індэкс ў хэш-табліцы.

63
00:03:14,490 --> 00:03:18,530
>> Звярніце ўвагу, што мы Moding па NUM_BUCKETS,
так што значэнне, вернутае

64
00:03:18,530 --> 00:03:21,730
на самай справе з'яўляецца індэксам ў хэш-табліцы
і ня індэксуе за

65
00:03:21,730 --> 00:03:24,320
Межы масіва.

66
00:03:24,320 --> 00:03:28,060
Таму, улічваючы, што функцыя, мы збіраемся
каб растлумачыць слова, што мы чытаем

67
00:03:28,060 --> 00:03:29,390
слоўнік.

68
00:03:29,390 --> 00:03:31,700
А потым мы збіраемся выкарыстаць
што хэш ўставіць

69
00:03:31,700 --> 00:03:33,750
ўступленне ў хэш-табліцы.

70
00:03:33,750 --> 00:03:38,520
>> Цяпер хэш хэш бягучы
звязана спіс у табліцы.

71
00:03:38,520 --> 00:03:41,410
І вельмі магчыма,
што гэта проста NULL.

72
00:03:41,410 --> 00:03:44,960
Мы хочам, каб ўставіць нашу запіс у
ў пачатку гэтага звязанага спісу.

73
00:03:44,960 --> 00:03:48,600
І такім чынам мы будзем мець нашу ток
Кропка ўваходу да таго, што хэш-табліца

74
00:03:48,600 --> 00:03:50,380
У цяперашні час паказвае.

75
00:03:50,380 --> 00:03:53,310
А потым мы збіраемся захоўваць,
ў хэш-табліцы на

76
00:03:53,310 --> 00:03:55,350
хэш, бягучая запіс.

77
00:03:55,350 --> 00:03:59,320
Такім чынам, гэтыя дзве лініі паспяхова ўставіць
ўступленне ў пачатку

78
00:03:59,320 --> 00:04:02,260
Звязаны спіс па гэтым індэксе
ў хэш-табліцы.

79
00:04:02,260 --> 00:04:04,900
>> Пасля таго, як мы скончым з гэтым, мы ведаем,
што мы знайшлі яшчэ адно слова ў

80
00:04:04,900 --> 00:04:07,790
слоўнік, і мы павялічваем зноў.

81
00:04:07,790 --> 00:04:13,960
Такім чынам, мы працягваць рабіць гэта да fscanf
нарэшце, вярнуўся нешта не-1 на

82
00:04:13,960 --> 00:04:16,950
чаго памятаеце, што
мы павінны на свабодны ўезд.

83
00:04:16,950 --> 00:04:19,459
Так тут мы malloced запіс.

84
00:04:19,459 --> 00:04:21,329
І мы стараліся, каб чытаць тое
з слоўніка.

85
00:04:21,329 --> 00:04:23,910
І мы не паспяхова прачытаныя
нешта з слоўніка, у

86
00:04:23,910 --> 00:04:26,650
гэтым выпадку нам трэба вызваліць запіс
што мы ніколі не ўведзены ў

87
00:04:26,650 --> 00:04:29,140
хэш, і, нарэшце, зламаць.

88
00:04:29,140 --> 00:04:32,750
>> Як толькі мы вырвацца мы павінны бачыць, ну,
ж мы вырвацца, таму што

89
00:04:32,750 --> 00:04:34,360
Адбылася памылка чытання з файла?

90
00:04:34,360 --> 00:04:37,120
Ці мы ламаем, таму што мы
дасягнулі канца файла?

91
00:04:37,120 --> 00:04:39,480
Калі адбылася памылка, то
мы хочам вярнуцца ілжывым.

92
00:04:39,480 --> 00:04:40,930
Таму што нагрузка не ўдалося.

93
00:04:40,930 --> 00:04:43,890
І ў гэтым працэсе мы хочам, каб разгрузіць
ўсе словы, якія мы чытаем у і

94
00:04:43,890 --> 00:04:45,670
зачыніць файл слоўніка.

95
00:04:45,670 --> 00:04:48,740
>> Выкажам здагадку, што мы атрымалі поспех, то мы проста
яшчэ трэба зачыніць слоўнік

96
00:04:48,740 --> 00:04:53,040
файл, і, нарэшце, вярнуцца дакладна, так як мы
паспяхова загружаны слоўнік.

97
00:04:53,040 --> 00:04:54,420
І гэта ўсё на груз.

98
00:04:54,420 --> 00:04:59,020
Так што цяпер праверыць, улічваючы загружаны хэш,
будзе выглядаць наступным чынам.

99
00:04:59,020 --> 00:05:03,140
Таму праверыць, яна вяртае лагічнае значэнне, якое
збіраецца паказаць, ці з'яўляецца прайшло

100
00:05:03,140 --> 00:05:07,530
ў сімвал * словы, няхай гэта будзе прайшло
у радку знаходзіцца ў нашым слоўніку.

101
00:05:07,530 --> 00:05:09,890
Так што, калі ён знаходзіцца ў слоўніку,
калі ён знаходзіцца ў нашай хэш-табліцы,

102
00:05:09,890 --> 00:05:11,170
мы вернемся праўда.

103
00:05:11,170 --> 00:05:13,380
А калі гэта не так, мы вернемся ілжывым.

104
00:05:13,380 --> 00:05:17,740
>> Улічваючы гэта прайшло ў слове, мы
збіраецца хэш слова.

105
00:05:17,740 --> 00:05:22,110
Зараз галоўнае, каб прызнаць,
што ў нагрузцы мы ведалі, што ўсе

106
00:05:22,110 --> 00:05:23,820
словы, якія мы збіраемся быць у ніжнім рэгістры.

107
00:05:23,820 --> 00:05:25,820
Але тут мы не так ўпэўнены.

108
00:05:25,820 --> 00:05:29,510
Калі мы зірнем на наш хэш-функцыі,
наш хэш-функцыя на самай справе

109
00:05:29,510 --> 00:05:32,700
ніжэй корпуса кожны знак
слова.

110
00:05:32,700 --> 00:05:37,940
Таму, незалежна ад капіталізацыі
Слова, наш хэш-функцыя з'яўляецца вяртанне

111
00:05:37,940 --> 00:05:42,270
аналагічны паказчык па тых ці іншых
капіталізацыя, так як ён павінен быў бы

112
00:05:42,270 --> 00:05:45,280
вярнуліся на зусім ніжнім рэгістры
варыянт слова.

113
00:05:45,280 --> 00:05:46,600
Добра.

114
00:05:46,600 --> 00:05:49,790
Гэта наш індэкс ў
HashTable для гэтага слова.

115
00:05:49,790 --> 00:05:52,940
>> Зараз гэта цыкл збіраецца
перабору звязанага спісу

116
00:05:52,940 --> 00:05:55,000
гэта было па гэтым індэксе.

117
00:05:55,000 --> 00:05:59,610
Так заўважыць мы ініцыялізацыі запіс
паказаць на тое індэкс.

118
00:05:59,610 --> 00:06:02,750
Мы збіраемся працягнуць
у той час як запіс! = NULL.

119
00:06:02,750 --> 00:06:07,770
І памятайце, што абнаўленне паказальнік
у наш звязаны спіс запіс = запіс> наступная.

120
00:06:07,770 --> 00:06:14,400
Так што наш бягучы кропку ўваходу
Наступны пункт у звязаным спісе.

121
00:06:14,400 --> 00:06:19,250
>> Такім чынам, для кожнай запісу ў звязаным спісе,
мы збіраемся выкарыстаць strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Гэта не StrComp.

123
00:06:20,330 --> 00:06:23,780
Таму што ў чарговы раз, мы хочам
зрабіць што-то выпадак нячула.

124
00:06:23,780 --> 00:06:27,870
Таму мы выкарыстоўваем strcasecmp параўнаць
Слова, якое прапускаюць праз гэты

125
00:06:27,870 --> 00:06:31,860
Функцыя супраць слова
гэта значыць у дадзенай запісу.

126
00:06:31,860 --> 00:06:35,570
Калі яна вяртае нуль, гэта азначае, што было
матч, у гэтым выпадку мы хочам

127
00:06:35,570 --> 00:06:36,630
вярнуцца дакладна.

128
00:06:36,630 --> 00:06:39,590
Мы паспяхова знайшлі
Слова ў нашай хэш-табліцы.

129
00:06:39,590 --> 00:06:43,040
>> Калі б не было матчу, то мы
збіраецца цыкле зноў і паглядзець на

130
00:06:43,040 --> 00:06:43,990
Наступны запіс.

131
00:06:43,990 --> 00:06:47,640
І мы будзем працягваць зацыкленне у той час як ёсць
з'яўляюцца запісы ў гэтай звязанага спісу.

132
00:06:47,640 --> 00:06:50,160
Што адбудзецца, калі мы парушаем
з гэтага для цыкла?

133
00:06:50,160 --> 00:06:55,110
Гэта азначае, што мы не знайшлі запіс,
адпавядае гэтае слова, у якім выпадку

134
00:06:55,110 --> 00:07:00,220
мы вярнуцца ілжывым, каб паказаць, што наш
хэш не ўтрымліваюць гэтае слова.

135
00:07:00,220 --> 00:07:02,540
І гэта праверка.

136
00:07:02,540 --> 00:07:04,790
>> Так што давайце зірнем на памер.

137
00:07:04,790 --> 00:07:06,970
Цяпер памер будзе даволі проста.

138
00:07:06,970 --> 00:07:11,080
Так памятаеце нагрузкі, для кожнага слова
мы знайшлі, мы павялічваецца глабальная

139
00:07:11,080 --> 00:07:12,880
пераменны памер хэш.

140
00:07:12,880 --> 00:07:16,480
Такім чынам, функцыя памер толькі збіраецца
вярнуцца глабальнай зменнай.

141
00:07:16,480 --> 00:07:18,150
І гэта ўсё.

142
00:07:18,150 --> 00:07:22,300
>> Цяпер, нарэшце, мы павінны выгрузіць
слоўнік, як толькі ўсё будзе зроблена.

143
00:07:22,300 --> 00:07:25,340
Так як мы збіраемся гэта зрабіць?

144
00:07:25,340 --> 00:07:30,440
Прама тут мы прабягаем па
ўсе вядра нашым стале.

145
00:07:30,440 --> 00:07:33,240
Такім чынам, ёсць NUM_BUCKETS вядра.

146
00:07:33,240 --> 00:07:37,410
І для кожнага звязанага спісу ў нашым
хэш, мы збіраемся цыкла па

147
00:07:37,410 --> 00:07:41,070
паўната звязанага спісу,
вызваляючы кожны элемент.

148
00:07:41,070 --> 00:07:42,900
>> Цяпер мы павінны быць асцярожныя.

149
00:07:42,900 --> 00:07:47,910
Так вось у нас часовую зменную
які захоўвання паказальнік на наступны

150
00:07:47,910 --> 00:07:49,730
элемент у звязаным спісе.

151
00:07:49,730 --> 00:07:52,140
А потым мы збіраемся бясплатна
бягучы элемент.

152
00:07:52,140 --> 00:07:55,990
Мы павінны быць упэўнены, што мы робім гэта, так як мы
не магу проста вызваліць бягучы элемент

153
00:07:55,990 --> 00:07:59,180
, А затым паспрабаваць пераходу да наступнай паказальнік,
так як толькі мы вызвалілі яго,

154
00:07:59,180 --> 00:08:00,870
памяць становіцца несапраўдным.

155
00:08:00,870 --> 00:08:04,990
>> Так што мы павінны трымаць вакол паказальнік на
на наступны элемент, то мы можам вызваліць

156
00:08:04,990 --> 00:08:08,360
бягучы элемент, і тады мы зможам абнавіць
наш бягучы элемент, каб паказаць на

157
00:08:08,360 --> 00:08:09,550
наступны элемент.

158
00:08:09,550 --> 00:08:12,800
Мы будзем цыкл у той час як ёсць элементы
у гэтым звязаным спісе.

159
00:08:12,800 --> 00:08:15,620
Мы зробім гэта для ўсіх звязаны
Спісы ў хэш-табліцы.

160
00:08:15,620 --> 00:08:19,460
І як толькі мы скончым з гэтым, мы
цалкам разгрузілі хэш-табліцу, і

161
00:08:19,460 --> 00:08:20,190
мы скончылі.

162
00:08:20,190 --> 00:08:23,200
Так што гэта немагчыма для выгрузкі
каб калі-небудзь вярнуцца ілжывым.

163
00:08:23,200 --> 00:08:26,470
А калі мы скончым, мы
проста вярнуць дакладна.

164
00:08:26,470 --> 00:08:29,000
>> Давайце гэта рашэнне паспрабаваць.

165
00:08:29,000 --> 00:08:33,070
Такім чынам, давайце паглядзім, што наш
структура вузел будзе выглядаць.

166
00:08:33,070 --> 00:08:36,220
Тут мы бачым, што мы збіраемся мець лагічнае значэнне
слова і структура вузла * дзеці

167
00:08:36,220 --> 00:08:37,470
Кранштэйны алфавіт.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
Таму першае, што вы маглі б быць
цікава, чаму алфавіт

170
00:08:42,020 --> 00:08:44,660
рэд вызначаецца як 27?

171
00:08:44,660 --> 00:08:47,900
Ну, памятаеце, што мы збіраемся трэба
быць апрацоўкі апостраф.

172
00:08:47,900 --> 00:08:51,910
Так што гэта будзе свайго роду
Асаблівы выпадак ўсёй гэтай праграмы.

173
00:08:51,910 --> 00:08:54,710
>> Цяпер успомніце, як сінтаксічнага дрэва
на самай справе працуе.

174
00:08:54,710 --> 00:08:59,380
Скажам мы індэксацыі слова
"Кошкі". Тады з кораня сінтаксічнага дрэва,

175
00:08:59,380 --> 00:09:02,610
мы будзем глядзець на дзяцей
Масіў, і мы будзем глядзець на

176
00:09:02,610 --> 00:09:08,090
індэкс, які адпавядае літары
С. Так што будзе індэксавацца 2.

177
00:09:08,090 --> 00:09:11,530
Таму, улічваючы, што, што воля
даць нам новы вузел.

178
00:09:11,530 --> 00:09:13,820
І тады мы будзем працаваць з гэтым вузлом.

179
00:09:13,820 --> 00:09:17,770
>> Таму, улічваючы, што вузел, мы ў чарговы раз
будзем глядзець на масіве дзяцей.

180
00:09:17,770 --> 00:09:22,110
І мы будзем глядзець на нулявы індэкс
каб адпавядаць А ў кот.

181
00:09:22,110 --> 00:09:27,170
Такім чынам, мы збіраемся пайсці на гэты вузел,
і ўлічваючы, што вузел мы збіраемся

182
00:09:27,170 --> 00:09:31,090
шукаць у канцы гэта адпавядае
Т. і перайсці да гэтага вузла,

183
00:09:31,090 --> 00:09:35,530
нарэшце, мы цалкам паглядзеў
праз наша слова "кот". А цяпер Ьоо

184
00:09:35,530 --> 00:09:40,960
слова мяркуецца паказаць, ці з'яўляецца
гэта дадзенае слова на самой справе слова.

185
00:09:40,960 --> 00:09:43,470
>> Дык чаму ж мы павінны, што прыватны выпадак?

186
00:09:43,470 --> 00:09:47,700
Ну тое, што словы «катастрофа»
знаходзіцца ў нашым слоўніку, але

187
00:09:47,700 --> 00:09:50,150
Слова "кот" не з'яўляецца?

188
00:09:50,150 --> 00:09:54,580
Так і глядзеў, калі слова "кот"
знаходзіцца ў нашым слоўніку, мы

189
00:09:54,580 --> 00:09:59,970
збіраецца паспяхова праглядаць
індэксы С-А-Т ў галіне вузла.

190
00:09:59,970 --> 00:10:04,290
Але гэта толькі таму, што катастрофа
адбылося стварыць вузлы на шляху

191
00:10:04,290 --> 00:10:07,190
ад З-А-Т, аж да
канец слова.

192
00:10:07,190 --> 00:10:12,020
Так BOOL слова выкарыстоўваецца, каб паказаць,
гэта асаблівая размяшчэнне

193
00:10:12,020 --> 00:10:14,310
на самай справе паказвае на слова.

194
00:10:14,310 --> 00:10:15,140
>> Добра.

195
00:10:15,140 --> 00:10:19,310
Так што цяпер мы ведаем, што гэта сінтаксічнага дрэва з'яўляецца
будзе выглядаць, давайце паглядзім на

196
00:10:19,310 --> 00:10:20,730
загрузіць функцыю.

197
00:10:20,730 --> 00:10:24,610
Так нагрузка будзе вяртаць лагічнае значэнне
для таго мы паспяхова або

198
00:10:24,610 --> 00:10:26,720
беспаспяхова загружалася слоўнік.

199
00:10:26,720 --> 00:10:30,460
І гэта будзе слоўнік
што мы хочам загрузіць.

200
00:10:30,460 --> 00:10:33,930
>> Так першае, што мы хочам зрабіць, гэта адкрыць
да гэтага слоўніка для чытання.

201
00:10:33,930 --> 00:10:36,160
І мы павінны пераканацца,
мы не праваліўся.

202
00:10:36,160 --> 00:10:39,580
Так, калі ў слоўніку не было
паспяхова адкрыты, то ён верне

203
00:10:39,580 --> 00:10:42,400
нуль, у якім выпадку мы
збіраецца вярнуцца ілжывым.

204
00:10:42,400 --> 00:10:47,230
Але калі выказаць здагадку, што ён паспяхова
адкрыў, то мы можам на самай справе чытаць

205
00:10:47,230 --> 00:10:48,220
праз слоўніку.

206
00:10:48,220 --> 00:10:50,880
>> Так першае, што мы збіраемся
хачу зрабіць, гэта ў нас ёсць гэта

207
00:10:50,880 --> 00:10:52,500
глабальная пераменная корань.

208
00:10:52,500 --> 00:10:56,190
Цяпер корань будзе вузел *.

209
00:10:56,190 --> 00:10:59,760
Гэта вяршыня нашага сінтаксічнага дрэва, што мы
будзе ітэрацыі.

210
00:10:59,760 --> 00:11:02,660
Такім чынам, першае, што мы збіраемся
хочуць зрабіць, гэта вылучыць

211
00:11:02,660 --> 00:11:04,140
памяць для нашага кораня.

212
00:11:04,140 --> 00:11:07,980
Звярніце ўвагу, што мы выкарыстоўваем calloc
Функцыя, якая ў асноўным тое ж самае

213
00:11:07,980 --> 00:11:11,500
як функцыя Таноса, за выключэннем, што гэта
гарантавана вярнуць тое, што з'яўляецца

214
00:11:11,500 --> 00:11:13,180
цалкам абнуляецца.

215
00:11:13,180 --> 00:11:17,290
Так што, калі мы выкарыстоўвалі Таноса, мы павінны былі б
прайсці праз усе ўказальнікі ў нашай

216
00:11:17,290 --> 00:11:20,160
вузел, і пераканайцеся, што
яны ўсё нуль.

217
00:11:20,160 --> 00:11:22,710
Так calloc зробіць гэта за нас.

218
00:11:22,710 --> 00:11:26,330
>> Цяпер жа, як Таноса, мы павінны зрабіць
упэўнены, што размеркаванне было на самай справе

219
00:11:26,330 --> 00:11:27,520
паспяховым.

220
00:11:27,520 --> 00:11:29,990
Калі гэта вяртаецца нуль, то
трэба зачыніць ці слоўнік

221
00:11:29,990 --> 00:11:32,100
файл і вярнуцца ілжывым.

222
00:11:32,100 --> 00:11:36,835
Так, мяркуючы, што размеркаванне было
паспяхова, мы збіраемся выкарыстаць вузел *

223
00:11:36,835 --> 00:11:40,270
курсор для перабору нашага сінтаксічнага дрэва.

224
00:11:40,270 --> 00:11:43,890
Такім чынам, нашы карані ніколі не збіраецца мяняць,
але мы збіраемся выкарыстоўваць курсор

225
00:11:43,890 --> 00:11:47,875
на самай справе ісці ад вузла да вузла.

226
00:11:47,875 --> 00:11:50,940
>> Так што ў гэтым цыкле мы чытаем
праз файл слоўніка.

227
00:11:50,940 --> 00:11:53,670
І мы выкарыстоўваем fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc збіраецца захапіць адзін
персанаж з файла.

229
00:11:56,290 --> 00:11:59,370
Мы збіраемся працягнуць захоп
знакаў у той час як мы не даходзяць

230
00:11:59,370 --> 00:12:01,570
канец файла.

231
00:12:01,570 --> 00:12:03,480
>> Ёсць два выпадкі, якія мы павінны справіцца.

232
00:12:03,480 --> 00:12:06,610
Першы, калі знак
ня новая лінія.

233
00:12:06,610 --> 00:12:10,450
Такім чынам, мы ведаем, ці было гэта новая лінія, то
мы збіраемся перайсці да новых словам.

234
00:12:10,450 --> 00:12:15,240
Але калі выказаць здагадку, што гэта не было новай лініі, то
тут мы хочам высветліць,

235
00:12:15,240 --> 00:12:18,380
Індэкс мы збіраемся індэкса ў
ў масіве дзяцей, што

236
00:12:18,380 --> 00:12:19,810
мы глядзелі на перад.

237
00:12:19,810 --> 00:12:23,880
>> Так што, як я ўжо казаў, мы павінны
Асаблівы выпадак апостраф.

238
00:12:23,880 --> 00:12:26,220
Звярніце ўвагу, што мы выкарыстоўваем патройных
аператар тут.

239
00:12:26,220 --> 00:12:29,580
Так што мы збіраемся, каб прачытаць гэта як, калі
характар ​​мы чытаем, быў

240
00:12:29,580 --> 00:12:35,330
апостраф, то мы збіраемся ўсталяваць
індэкс = "алфавіт" -1, які будзе

241
00:12:35,330 --> 00:12:37,680
быць індэкс 26.

242
00:12:37,680 --> 00:12:41,130
>> У адваротным выпадку, калі гэта не было апостраф, ёсць
мы збіраемся ўсталяваць індэкс

243
00:12:41,130 --> 00:12:43,760
роўная с -.

244
00:12:43,760 --> 00:12:49,030
Так што памятаеце параўнанні з раней р-набораў,
с - а будзе даваць нам

245
00:12:49,030 --> 00:12:53,410
алфавітны пазіцыя С. Так што калі
З літара А, гэта будзе

246
00:12:53,410 --> 00:12:54,700
даць нам нулявы індэкс.

247
00:12:54,700 --> 00:12:58,120
Для лісты B, гэта дасць
нам індэкс 1, і гэтак далей.

248
00:12:58,120 --> 00:13:03,010
>> Так што гэта дае нам індэкс ў
дзеці масіў, які мы хочам.

249
00:13:03,010 --> 00:13:08,890
Цяпер, калі гэты паказчык у цяперашні час нулявы ў
дзеці, гэта азначае, што вузел

250
00:13:08,890 --> 00:13:11,830
у цяперашні час не існуе
з гэтага шляху.

251
00:13:11,830 --> 00:13:15,160
Так што мы павінны вылучыць
вузел для гэтага шляху.

252
00:13:15,160 --> 00:13:16,550
Гэта тое, што мы будзем рабіць тут.

253
00:13:16,550 --> 00:13:20,690
>> Так што мы збіраемся зноў выкарыстоўваць calloc
Функцыя, так што мы не павінны

254
00:13:20,690 --> 00:13:22,880
абнуліць усе паказальнікі.

255
00:13:22,880 --> 00:13:27,240
І мы зноў павінны праверыць
што calloc не праваліўся.

256
00:13:27,240 --> 00:13:30,700
Калі calloc нічога не атрымаецца, то мы павінны
выгрузіць усё, закрываем

257
00:13:30,700 --> 00:13:32,820
слоўнік, і вярнуцца ілжывым.

258
00:13:32,820 --> 00:13:40,050
Так мяркуючы, што ён не прамінуў, то
гэта створыць новага дзіцяці для нас.

259
00:13:40,050 --> 00:13:41,930
А потым мы пойдзем у гэтага дзіцяці.

260
00:13:41,930 --> 00:13:44,960
Наша курсор ітэрацыі
да гэтага дзіцяці.

261
00:13:44,960 --> 00:13:49,330
>> Цяпер, калі гэта не было пустой для пачатку,
то курсор можна проста перабраць

262
00:13:49,330 --> 00:13:52,590
да гэтага дзіцяці, фактычна не
таго, каб вылучыць нічога.

263
00:13:52,590 --> 00:13:56,730
Гэта той выпадак, калі мы ўпершыню адбылося
вылучыць слова «кот». І

264
00:13:56,730 --> 00:14:00,330
гэта азначае, што, калі мы ідзем вылучыць
"Катастрофа", нам не трэба ствараць

265
00:14:00,330 --> 00:14:01,680
вузлы для C-A-T зноў.

266
00:14:01,680 --> 00:14:04,830
Яны ўжо існуюць.

267
00:14:04,830 --> 00:14:06,080
>> Што гэта яшчэ?

268
00:14:06,080 --> 00:14:10,480
Гэта стан, пры якім кандыцыянер быў
касая рыса п, дзе кандыцыянер быў новая лінія.

269
00:14:10,480 --> 00:14:13,710
Гэта азначае, што мы паспяхова
завяршыла слова.

270
00:14:13,710 --> 00:14:16,860
Цяпер тое, што мы хочам зрабіць, калі мы
паспяхова завяршыла слова?

271
00:14:16,860 --> 00:14:21,100
Мы збіраемся выкарыстоўваць гэта поле слова
ўнутры нашага структуры вузла.

272
00:14:21,100 --> 00:14:23,390
Мы хочам, каб усталяваць, што да ісціны.

273
00:14:23,390 --> 00:14:27,150
Так што паказвае, што гэты вузел
паказвае паспяховым

274
00:14:27,150 --> 00:14:29,250
Слова, фактычны слова.

275
00:14:29,250 --> 00:14:30,940
>> Зараз усталюеце, што да ісціны.

276
00:14:30,940 --> 00:14:35,150
Мы хочам, каб скінуць нашу курсор да кропкі
ў пачатку сінтаксічнага дрэва зноў.

277
00:14:35,150 --> 00:14:40,160
І, нарэшце, павялічыць наш слоўнік
памер, так як мы знайшлі іншай працы.

278
00:14:40,160 --> 00:14:43,230
Так што мы збіраемся працягваць рабіць гэта,
чытанне ў посимвольно,

279
00:14:43,230 --> 00:14:49,150
пабудовы новых вузлоў у нашай сінтаксічнага дрэва і
для кожнага слова ў слоўніку, да

280
00:14:49,150 --> 00:14:54,020
мы, нарэшце, дасягнуць C! = EOF, у якім
выпадку мы вырвацца з файла.

281
00:14:54,020 --> 00:14:57,050
>> Зараз ёсць два выпадкі пад
якія мы маглі б патрапіць EOF.

282
00:14:57,050 --> 00:15:00,980
Першы, калі адбылася памылка
чытанне з файла.

283
00:15:00,980 --> 00:15:03,470
Так што, калі адбылася памылка, мы
трэба зрабіць тыповы.

284
00:15:03,470 --> 00:15:06,460
Выгрузка ўсё, блізка
файл, вяртанне ілжывым.

285
00:15:06,460 --> 00:15:09,810
Мяркуючы, што не было памылак, якія
проста азначае, што мы на самай справе патрапіў у канцы

286
00:15:09,810 --> 00:15:13,750
файл, у якім выпадку, мы закрываем
файл і вярнуцца дакладна, так як мы

287
00:15:13,750 --> 00:15:17,330
паспяхова загружаны слоўнік
ў нашай сінтаксічнага дрэва.

288
00:15:17,330 --> 00:15:20,170
>> Так што цяпер давайце праверым чэк.

289
00:15:20,170 --> 00:15:25,156
Гледзячы на ​​функцыі праверкі, мы бачым,
, Што рэгістрацыя будзе вяртаць лагічнае значэнне.

290
00:15:25,156 --> 00:15:29,680
Гэта вяртае ісціну, калі гэта слова, што гэта
перадаецца ў нашай сінтаксічнага дрэва.

291
00:15:29,680 --> 00:15:32,110
Гэта вяртае хлусня ў адваротным выпадку.

292
00:15:32,110 --> 00:15:36,050
Так як жа вызначыць, ці з'яўляецца
гэтае слова ў нашым сінтаксічнага дрэва?

293
00:15:36,050 --> 00:15:40,190
>> Мы бачым тут, што, як і раней,
мы збіраемся выкарыстоўваць курсор для перабору

294
00:15:40,190 --> 00:15:41,970
праз нашу сінтаксічнага дрэва.

295
00:15:41,970 --> 00:15:46,600
Цяпер вось мы збіраемся ітэрацыі
над усім нашым словам.

296
00:15:46,600 --> 00:15:50,620
Так ітэрацыі словы мы мінулае,
мы збіраемся вызначыць

297
00:15:50,620 --> 00:15:56,400
індэкс ў масіве дзяцей, што
адпавядае слова кранштэйна I. Такім чынам, гэта

298
00:15:56,400 --> 00:15:59,670
будзе выглядаць гэтак жа, як
нагрузка, дзе, калі слова [я]

299
00:15:59,670 --> 00:16:03,310
з'яўляецца апостраф, то мы хочам
выкарыстоўваць індэкс «алфавіт» - 1.

300
00:16:03,310 --> 00:16:05,350
Таму мы вырашылі, што, што
Тут мы збіраемся захоўваць

301
00:16:05,350 --> 00:16:07,100
апострафа.

302
00:16:07,100 --> 00:16:11,780
>> Астатняе мы збіраемся выкарыстаць два ніжніх слова
Кранштэйны І. Так што памятаеце, што слова можа

303
00:16:11,780 --> 00:16:13,920
мець адвольную капіталізацыі.

304
00:16:13,920 --> 00:16:17,540
І таму мы хочам, каб пераканацца, што мы
выкарыстоўваючы маленькую версію рэчаў.

305
00:16:17,540 --> 00:16:21,920
А потым адняць ад "а" да аднаго разу
зноў даць нам алфавітным

306
00:16:21,920 --> 00:16:23,880
Становішча гэтага знака.

307
00:16:23,880 --> 00:16:27,680
Так што гэта будзе наш індэкс
ў масіве дзяцей.

308
00:16:27,680 --> 00:16:32,420
>> А цяпер, калі гэта індэкс ў дзяцей
Масіў з'яўляецца пустым, што азначае, што мы

309
00:16:32,420 --> 00:16:34,990
больш не можа працягваць ітэрацыі
ўніз нашага сінтаксічнага дрэва.

310
00:16:34,990 --> 00:16:38,870
Калі гэта так, то гэта слова не можа
магчыма, будзе ў нашым сінтаксічнага дрэва.

311
00:16:38,870 --> 00:16:42,340
Паколькі калі б гэта было, што б
азначае, што будзе шлях

312
00:16:42,340 --> 00:16:43,510
да гэтага слова.

313
00:16:43,510 --> 00:16:45,290
І вы ніколі не сутыкнецеся з нуль.

314
00:16:45,290 --> 00:16:47,850
Так сустракаючы нуль, мы вярнуцца ілжывым.

315
00:16:47,850 --> 00:16:49,840
Слова адсутнічае ў слоўніку.

316
00:16:49,840 --> 00:16:53,660
Калі б не нуль, то мы
збіраецца працягнуць ітэрацыі.

317
00:16:53,660 --> 00:16:57,220
>> Так што мы збіраемся там курсор
, Каб паказаць, што асабліва

318
00:16:57,220 --> 00:16:59,760
вузел па гэтым індэксе.

319
00:16:59,760 --> 00:17:03,150
Мы працягваем рабіць гэта на працягу
усё слова, мяркуючы,

320
00:17:03,150 --> 00:17:03,950
мы ніколі не ўдарыў нуль.

321
00:17:03,950 --> 00:17:07,220
Гэта азначае, што мы змаглі прайсці праз
усё слова і знайсці

322
00:17:07,220 --> 00:17:08,920
вузел у нашай спробы.

323
00:17:08,920 --> 00:17:10,770
Але мы яшчэ не скончылі яшчэ.

324
00:17:10,770 --> 00:17:12,290
>> Мы не хочам, каб проста вярнуць дакладна.

325
00:17:12,290 --> 00:17:14,770
Мы хочам вярнуцца курсора> слова.

326
00:17:14,770 --> 00:17:18,980
Так памятаеце зноў жа, "кошка" ня
ў нашым слоўніку, і «катастрофа»

327
00:17:18,980 --> 00:17:22,935
будзе, то мы будзем паспяхова мы атрымліваем
праз слова "кот". Але курсора

328
00:17:22,935 --> 00:17:25,760
Слова будзе ілжывым, а не праўда.

329
00:17:25,760 --> 00:17:30,930
Так мы вяртаемся курсора слова для абазначэння
Ці гэты вузел на самой справе слова.

330
00:17:30,930 --> 00:17:32,470
І гэта ўсё для праверкі.

331
00:17:32,470 --> 00:17:34,250
>> Дык давайце праверым памер.

332
00:17:34,250 --> 00:17:37,350
Так памер будзе даволі лёгка
так, памятаеце, у нагрузцы, мы

333
00:17:37,350 --> 00:17:41,430
павялічваючы памер слоўніка для
кожнае слова, што мы сутыкаемся з.

334
00:17:41,430 --> 00:17:45,350
Так памер толькі збіраецца
вярнуцца памер слоўніка.

335
00:17:45,350 --> 00:17:47,390
І гэта ўсё.

336
00:17:47,390 --> 00:17:50,590
>> Так, нарэшце, мы выгрузіць.

337
00:17:50,590 --> 00:17:55,100
Так выгрузіць, мы збіраемся выкарыстаць
рэкурсіўная функцыя на самай справе рабіць усё

338
00:17:55,100 --> 00:17:56,530
частка працы за нас.

339
00:17:56,530 --> 00:17:59,340
Такім чынам, наша функцыя будзе
быць выкліканы разгрузкі.

340
00:17:59,340 --> 00:18:01,650
Што разгрузачныя збіраецеся рабіць?

341
00:18:01,650 --> 00:18:06,580
Мы бачым тут, што разгружальная збіраецца
перабору ўсіх дзяцей у

342
00:18:06,580 --> 00:18:08,410
менавіта гэты вузел.

343
00:18:08,410 --> 00:18:11,750
А калі дзіця вузел ня
нуля, то мы збіраемся

344
00:18:11,750 --> 00:18:13,730
выгрузіць даччыны вузел.

345
00:18:13,730 --> 00:18:18,010
>> Так што гэта вы рэкурсіўна выгрузіць
ўсіх нашых дзяцей.

346
00:18:18,010 --> 00:18:21,080
Пасля таго, як мы ўпэўненыя, што ўсе нашы дзеці
былі выгружаны, то мы

347
00:18:21,080 --> 00:18:25,210
можа вызваліцца, так
выгрузіць сябе.

348
00:18:25,210 --> 00:18:29,460
Гэта будзе працаваць рэкурсіўна
выгрузіць ўвесь сінтаксічнага дрэва.

349
00:18:29,460 --> 00:18:32,850
А потым, як толькі гэта будзе зроблена,
мы можам проста вярнуць дакладна.

350
00:18:32,850 --> 00:18:34,210
Выгрузка не можа падвесці.

351
00:18:34,210 --> 00:18:35,710
Мы проста вызваляючы рэчы.

352
00:18:35,710 --> 00:18:38,870
Таму, як толькі мы скончым вызваляючы
ўсё, вярнуцца дакладна.

353
00:18:38,870 --> 00:18:40,320
І гэта ўсё.

354
00:18:40,320 --> 00:18:41,080
Мяне клічуць Боб.

355
00:18:41,080 --> 00:18:42,426
І гэта было правапісу.

356
00:18:42,426 --> 00:18:47,830
>> [Музыка гуляе]