1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN: Hi.

3
00:00:13,050 --> 00:00:16,210
Аз съм Роб, и хашиш нека да
това решение навън.

4
00:00:16,210 --> 00:00:20,070
Така че тук ние ще се приложат
обща таблица за хашиш.

5
00:00:20,070 --> 00:00:24,090
Виждаме, че структурата на възел на нашата хеш
маса ще изглежда по този начин.

6
00:00:24,090 --> 00:00:28,710
Така че няма да има Чар дума
масив от размер дължина плюс един.

7
00:00:28,710 --> 00:00:32,259
Да не забравяме и една от максимално
дума в речника е 45

8
00:00:32,259 --> 00:00:35,110
герои, а след това ние ще
нужда от един допълнителен характер по

9
00:00:35,110 --> 00:00:37,070
наклонена черта 0.

10
00:00:37,070 --> 00:00:40,870
>> И тогава нашата хеш таблица във всяка
кофа ще се съхранява

11
00:00:40,870 --> 00:00:42,320
свързан списък от възли.

12
00:00:42,320 --> 00:00:44,420
Ние не правим линейна сондиране тук.

13
00:00:44,420 --> 00:00:48,430
И така, за да се свърже към следващата
елемент в кофата, ние се нуждаем от

14
00:00:48,430 --> 00:00:51,110
структура възел * следващия.

15
00:00:51,110 --> 00:00:53,090
Така че това е, което възел изглежда.

16
00:00:53,090 --> 00:00:56,180
Сега, тук е декларацията
на нашата хеш таблица.

17
00:00:56,180 --> 00:01:01,910
Тя ще има 16 384 кофи, но
този номер няма значение.

18
00:01:01,910 --> 00:01:05,450
И накрая, ние ще имаме
глобална променлива hashtable_size, които

19
00:01:05,450 --> 00:01:08,640
ще започнем като 0, а това е
Ще следим колко думи

20
00:01:08,640 --> 00:01:10,080
са в нашия речник.

21
00:01:10,080 --> 00:01:10,760
Добре.

22
00:01:10,760 --> 00:01:13,190
>> Така че нека да разгледаме най-натоварване.

23
00:01:13,190 --> 00:01:16,390
Така че забележите, че натоварване,
го връща булев.

24
00:01:16,390 --> 00:01:20,530
Ще се върнете вярно, ако това беше успешно
зареден и лъжа в противен случай.

25
00:01:20,530 --> 00:01:23,990
И това отнема Конст Чар * звезда
речник, който е речника

26
00:01:23,990 --> 00:01:25,280
че искаме да се отвори.

27
00:01:25,280 --> 00:01:27,170
Така че това е първото нещо,
ние ще направим.

28
00:01:27,170 --> 00:01:30,420
Отиваме да Fopen речника за
четене, и ние ще трябва

29
00:01:30,420 --> 00:01:34,700
да се уверите, че тя успя, така че ако
го връща NULL, тогава ние не направихме

30
00:01:34,700 --> 00:01:37,440
успешно отворите речника
и ние трябва да се върне фалшиви.

31
00:01:37,440 --> 00:01:41,580
>> Но ако приемем, че го е направил успешно
отворен, след това ние искаме да прочетете

32
00:01:41,580 --> 00:01:42,400
речник.

33
00:01:42,400 --> 00:01:46,210
Така че продължавайте да примка, докато не се намери някои
причина да се измъкнат от този

34
00:01:46,210 --> 00:01:47,570
цикъл, който ще видим.

35
00:01:47,570 --> 00:01:51,780
Така че продължавайте да примка, а сега отиваме
за изчистване на един възел.

36
00:01:51,780 --> 00:01:56,800
И разбира се, ние трябва да се грешка проверка
отново, така че ако не успее mallocing

37
00:01:56,800 --> 00:02:00,660
и ние искаме да се разтоварят всеки възел, който ние
случило с изчистване преди, затворете

38
00:02:00,660 --> 00:02:02,590
речник и връщане фалшиви.

39
00:02:02,590 --> 00:02:07,440
>> Но пренебрегвайки факта, че, ако се приеме, че
успял, тогава искаме да използваме fscanf

40
00:02:07,440 --> 00:02:12,400
за да прочетете една-единствена дума от нашия
речника в нашия възел.

41
00:02:12,400 --> 00:02:17,310
Така че не забравяйте, че входно-> дума е Чар
Думата буфер на размер дължина плюс

42
00:02:17,310 --> 00:02:20,300
едно, че отиваме в
съхранявате думата инча

43
00:02:20,300 --> 00:02:25,280
Така fscanf ще се върне един толкова дълго,
тъй като тя е в състояние успешно да прочетете

44
00:02:25,280 --> 00:02:26,750
дума от файла.

45
00:02:26,750 --> 00:02:31,030
>> Ако някоя грешка се случва или ще достигне
на края на файла, няма

46
00:02:31,030 --> 00:02:34,950
върнете 1, в който случай, ако това не стане
върнете 1, ние сме най-накрая ще се счупи

47
00:02:34,950 --> 00:02:37,280
от тази линия, докато.

48
00:02:37,280 --> 00:02:42,770
Така ние виждаме, че след като имаме успешно
прочетете една дума в

49
00:02:42,770 --> 00:02:48,270
входно-> дума, след това отиваме в хеш
тази дума с помощта на нашата хеш функция.

50
00:02:48,270 --> 00:02:49,580
Нека да разгледаме най-
функцията за сегментиране.

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

52
00:02:52,430 --> 00:02:55,610
>> Така че наистина не се нуждаят
да се разбере това.

53
00:02:55,610 --> 00:02:59,460
И всъщност, ние просто извади този
хеш функция от интернет.

54
00:02:59,460 --> 00:03:04,010
Единственото нещо, което трябва да се признае, е
че това отнема Конст Чар * дума,

55
00:03:04,010 --> 00:03:08,960
така че това е като низ като вход и
връщане неподписан Int като продукция.

56
00:03:08,960 --> 00:03:12,360
Така че това е всичко, функция за сегментиране се, е, че
се в един вход, той ви дава един

57
00:03:12,360 --> 00:03:14,490
индекс в хеш таблицата.

58
00:03:14,490 --> 00:03:18,530
Забележете, че ние сме модифициране от NUM_BUCKETS
така че стойността на хеш връща

59
00:03:18,530 --> 00:03:21,730
всъщност е индекс в таблицата на хеш
и не индекс на отвъдното

60
00:03:21,730 --> 00:03:24,320
границите на масива.

61
00:03:24,320 --> 00:03:27,855
>> Така че, имайки предвид, че хеш функция, отиваме
за сегментиране на думата, която четем

62
00:03:27,855 --> 00:03:31,700
от речника и след това отиваме
да използвате, че трябва да поставите

63
00:03:31,700 --> 00:03:33,750
влизане в хеш таблицата.

64
00:03:33,750 --> 00:03:38,830
Сега, Hashtable хеш е токът
свързан списък в хеш таблицата, и

65
00:03:38,830 --> 00:03:41,410
това е много възможно, че е само NULL.

66
00:03:41,410 --> 00:03:45,640
Искаме да вмъкнете влизането ни в
началото на този свързан списък, и така

67
00:03:45,640 --> 00:03:48,910
ние ще трябва сегашния ни влизане
точка на това, което хеш таблицата в момента

68
00:03:48,910 --> 00:03:54,030
пункта до и след това отиваме да съхранявате
в хеш таблицата в хеш

69
00:03:54,030 --> 00:03:55,350
текущият запис.

70
00:03:55,350 --> 00:03:59,320
>> Така че тези две линии успешно вмъкват
влизането в началото на

71
00:03:59,320 --> 00:04:02,270
свързан списък в този форум
в хеш таблицата.

72
00:04:02,270 --> 00:04:04,900
След като сте готови с това, ние знаем,
че ние открихме друга дума в

73
00:04:04,900 --> 00:04:07,800
речник и ние увеличаваме отново.

74
00:04:07,800 --> 00:04:13,960
Така че ние продължаваме да правим това, докато fscanf
най-накрая се връща нещо не е едно най-

75
00:04:13,960 --> 00:04:18,560
който момент не забравяйте, че ние трябва да се
безплатен вход, така че тук, ние malloced на

76
00:04:18,560 --> 00:04:21,329
влизане и ние се опитахме да се чете нещо
от речника.

77
00:04:21,329 --> 00:04:24,110
И ние не успешно чете
нещо от речника в която

78
00:04:24,110 --> 00:04:27,440
случай ние трябва да се освободим записа, който ние
всъщност никога не се пуска в хеш таблицата

79
00:04:27,440 --> 00:04:29,110
и най-накрая счупи.

80
00:04:29,110 --> 00:04:32,750
>> След като избухне, ние трябва да видим, добре,
не сме се измъкнат, защото има

81
00:04:32,750 --> 00:04:35,840
четеше грешка от файла, или
не сме се измъкнат, защото стигнахме

82
00:04:35,840 --> 00:04:37,120
на края на файла?

83
00:04:37,120 --> 00:04:40,150
Ако има грешка, то ние искаме да
връщане фалшиви, защото натоварването не е направил

84
00:04:40,150 --> 00:04:43,260
успеят, и в този процес, ние искаме да
разтоварят всички думи, които четем

85
00:04:43,260 --> 00:04:45,670
в и затворете файла речник.

86
00:04:45,670 --> 00:04:48,740
Ако приемем, че ние успяхме, тогава ние просто
Все още трябва да се затвори речника

87
00:04:48,740 --> 00:04:51,970
Файл, а най-накрая се върнете вярно, тъй като
ние успешно заредена

88
00:04:51,970 --> 00:04:53,040
речник.

89
00:04:53,040 --> 00:04:54,420
И това е за натоварване.

90
00:04:54,420 --> 00:04:59,020
>> Така че сега се провери, като се има зареден хеш таблица,
ще изглежда по този начин.

91
00:04:59,020 --> 00:05:02,690
Така че проверете, тя връща булев, което
ще посочват дали

92
00:05:02,690 --> 00:05:07,530
прехвърлена в Чар * дума, дали
прехвърлена в низ е в нашия речник.

93
00:05:07,530 --> 00:05:10,530
Така че, ако това е в речника, ако е
в нашата хеш таблица, ние ще се върне

94
00:05:10,530 --> 00:05:13,380
вярно, и ако не е,
ние ще се върне фалшиви.

95
00:05:13,380 --> 00:05:17,770
Като се има предвид това премина в дума, ние сме
ще сегментиране на думата.

96
00:05:17,770 --> 00:05:22,020
>> Сега, важно нещо е да се признае,
че при натоварване, ние знаехме, че всички

97
00:05:22,020 --> 00:05:25,820
думите щяха да бъдат по-ниски случай,
но ето, че не сме толкова сигурни.

98
00:05:25,820 --> 00:05:29,510
Ако можем да погледнем в нашата хеш функция,
нашата хеш функция всъщност

99
00:05:29,510 --> 00:05:32,700
е с умалени букви всеки знак
на думата.

100
00:05:32,700 --> 00:05:37,580
Така че независимо от капитализацията на
дума, нашата хеш функция ще

101
00:05:37,580 --> 00:05:42,270
върнете същия индекс за каквато и да е
капитализация е така, както би трябвало

102
00:05:42,270 --> 00:05:45,280
върнато за съвсем малки букви
версия на думата.

103
00:05:45,280 --> 00:05:45,950
Добре.

104
00:05:45,950 --> 00:05:47,410
>> Така че това е нашия форум.

105
00:05:47,410 --> 00:05:49,790
Това е хеш таблицата за тази дума.

106
00:05:49,790 --> 00:05:52,940
Сега, това за линия ще
до над свързан списък

107
00:05:52,940 --> 00:05:55,000
, което бе в този индекс.

108
00:05:55,000 --> 00:05:59,630
Така че забележите ние сме инициализиране влизане
да сочи към този индекс.

109
00:05:59,630 --> 00:06:03,480
Отиваме да продължи, докато влизането прави
не е равно NULL, и не забравяйте, че

110
00:06:03,480 --> 00:06:08,350
актуализиране на показалеца в нашата свързан списък
влизане равнява на входно-> следващия, така че да има

111
00:06:08,350 --> 00:06:13,840
сегашната ни входна точка към
следващия елемент в свързан списък.

112
00:06:13,840 --> 00:06:14,400
Добре.

113
00:06:14,400 --> 00:06:19,150
>> Така че за всяко влизане в свързан списък,
ние ще използваме strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Това не е strcmp защото отново, ние
искам да правя неща случай безчувствено.

115
00:06:23,780 --> 00:06:28,830
Така че ние използваме strcasecmp за сравнение на думата
че се предава тази функция

116
00:06:28,830 --> 00:06:31,860
срещу думата, която
е в този пост.

117
00:06:31,860 --> 00:06:35,570
Ако връща 0, това означава, че не е
един мач, в който случай ние искаме да

118
00:06:35,570 --> 00:06:36,630
връщане вярно.

119
00:06:36,630 --> 00:06:39,590
Ние успешно намери
дума в нашата хеш таблица.

120
00:06:39,590 --> 00:06:43,040
>> Ако там не беше мач, а след това ние сме
Ще цикъл отново и погледнете в

121
00:06:43,040 --> 00:06:43,990
следващия запис.

122
00:06:43,990 --> 00:06:47,640
И ние ще продължим примка, докато има
са вписвания в тази свързан списък.

123
00:06:47,640 --> 00:06:50,160
Какво ще стане, ако се прекъсне
от това за цикъл?

124
00:06:50,160 --> 00:06:55,110
Това означава, че ние не се намери запис, който
съвпадащи тази дума, в който случай

125
00:06:55,110 --> 00:07:00,220
ние връщане фалшиви да покаже, че нашата
хеш таблица не съдържа тази дума.

126
00:07:00,220 --> 00:07:01,910
И това е за проверка.

127
00:07:01,910 --> 00:07:02,540
Добре.

128
00:07:02,540 --> 00:07:04,790
>> Така че нека да разгледаме най-размер.

129
00:07:04,790 --> 00:07:09,280
Сега, размер ще бъде доста проста
откакто се помни в натоварване, за всяка дума

130
00:07:09,280 --> 00:07:12,880
ние открихме, ние увеличава в световен
променлива hashtable_size.

131
00:07:12,880 --> 00:07:15,830
Така функцията размер е просто
ще се върне, че глобалното

132
00:07:15,830 --> 00:07:18,150
променлива, и това е всичко.

133
00:07:18,150 --> 00:07:22,300
>> Сега най-накрая, ние трябва да се разтоварим
речник След като всичко е готово.

134
00:07:22,300 --> 00:07:25,340
Така че как ще го направиш?

135
00:07:25,340 --> 00:07:30,440
Точно тук, ние сме примка над всички
кофи с нашата хеш таблица.

136
00:07:30,440 --> 00:07:33,240
Така че има NUM_BUCKETS кофи.

137
00:07:33,240 --> 00:07:37,490
И за всеки свързан списък в нашата хеш
маса, отиваме да отскача над река

138
00:07:37,490 --> 00:07:41,070
цялост на свързан списък
освобождавайки всеки елемент.

139
00:07:41,070 --> 00:07:46,070
Сега, ние трябва да бъдем внимателни, така че тук ние
имат временен променлива, която е

140
00:07:46,070 --> 00:07:49,740
съхраняване на показалеца към следващата
елемент в свързан списък.

141
00:07:49,740 --> 00:07:52,140
И след това отиваме на свободно
текущия елемент.

142
00:07:52,140 --> 00:07:55,990
>> Ние трябва да бъдем сигурни, че правим това, тъй като ние
Не може просто да освободи текущия елемент

143
00:07:55,990 --> 00:07:59,260
и след това се опитайте да влезете в следващия показалеца
тъй като след като сме го освободили

144
00:07:59,260 --> 00:08:00,870
паметта става невалиден.

145
00:08:00,870 --> 00:08:04,990
Така че ние трябва да се запази около указател към
следващия елемент, тогава можем да се освободи

146
00:08:04,990 --> 00:08:08,360
текущия елемент, а след това можем да се актуализира
сегашната ни елемент да сочи към

147
00:08:08,360 --> 00:08:09,590
на следващия елемент.

148
00:08:09,590 --> 00:08:12,770
>> Ще контур докато има елементи
в този свързан списък.

149
00:08:12,770 --> 00:08:16,450
Ние ще направим това за всички свързани списъци в
хеш таблицата, и след като сме готови

150
00:08:16,450 --> 00:08:20,180
с това, ние сме напълно разтоварени
хеш таблицата, и сме готови.

151
00:08:20,180 --> 00:08:24,050
Така че това е невъзможно за разтоварвания на все
връщане фалшиви, и когато сме готови, ние

152
00:08:24,050 --> 00:08:25,320
просто връщане вярно.

153
00:08:25,320 --> 00:08:27,563