1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Проходження - Проблема Set 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Гарвардський університет]

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
і все тому, що ви ліверна ковбаса спойлер кита широкий слово.

11
00:00:39,390 --> 00:00:44,710
Так, коректура ваші перці це питання, максимально імпотенції.

12
00:00:44,710 --> 00:00:49,140
Це проблема, яка зачіпає мужній, мужній студентів.

13
00:00:49,140 --> 00:00:56,260
Я був одного разу сказав мій мучитель класу Ситов, що я б ніколи не потрапити в хороший колега.

14
00:00:56,260 --> 00:01:00,250
І це все, що я коли-небудь хотів, це все, що будь-яка дитина хоче в моєму віці,

15
00:01:00,250 --> 00:01:04,569
просто потрапити в хороший колега.

16
00:01:04,569 --> 00:01:12,720
І не просто колеги. Ні, я хотів піти в Кот-правової колега.

17
00:01:12,720 --> 00:01:18,360
Так що, якщо я не поліпшення, пішов би мої мрії їхати в Гарвард,

18
00:01:18,360 --> 00:01:22,730
Жале, або в'язниця - Ви знаєте, у в'язниці, Нью-Джерсі.

19
00:01:22,730 --> 00:01:25,170
Так що я взяв собі для перевірки орфографії.

20
00:01:25,170 --> 00:01:29,380
Це трохи витяг з одного з моїх улюблених художників розмовною словом, Тейлор Малі.

21
00:01:29,380 --> 00:01:34,630
У всякому разі, як він каже, важливість перевірки орфографії дуже важливо.

22
00:01:34,630 --> 00:01:39,440
>> Так що ласкаво просимо Проходження 5, в якому ми будемо говорити про 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
перед ім'ям покажчика і амперсанд, як звільнити їх, і т.д.

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
І ось ви тут бачите, вузол D буде вказувати на 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
це стане ЬурейеЕ структури

81
00:05:43,180 --> 00:05:46,870
, В якій ми збираємося мати кілька різних екземплярів вузлів.

82
00:05:46,870 --> 00:05:50,850
І таким чином, ми визначаємо його як новий тип даних.

83
00:05:50,850 --> 00:05:53,630
Тут ми маємо ЬурейеЕ вузла структури.

84
00:05:53,630 --> 00:05:56,160
У цьому прикладі ми маємо справу з цілими вузлами,

85
00:05:56,160 --> 00:06:00,490
тому ми маємо ціле значення імені, а потім у нас є ще один покажчик,

86
00:06:00,490 --> 00:06:07,390
і в цьому випадку, це покажчик на вузол, тому у нас є структура вузла * називається наступна.

87
00:06:07,390 --> 00:06:09,520
І тоді ми називаємо весь цей вузол річ.

88
00:06:09,520 --> 00:06:11,110
Переконайтеся, що ви будете слідувати цим синтаксисом.

89
00:06:11,110 --> 00:06:17,940
Зверніть увагу, що вузол насправді посилання нагорі, так і внизу фігурні дужки.

90
00:06:17,940 --> 00:06:23,400
Потім, щоб відстежувати, де моїм першим вузлом в цій пов'язаного списку,

91
00:06:23,400 --> 00:06:29,390
то в мене є вузол покажчиків називається головою, і я Танос достатньо місця для розміру вузла.

92
00:06:29,390 --> 00:06:36,240
Зауважимо, однак, що голова насправді є покажчиком вузла, на відміну від самого вузла.

93
00:06:36,240 --> 00:06:40,130
Таким чином, голова насправді не містить ніякого значення,

94
00:06:40,130 --> 00:06:45,590
вона лише вказує на який перший вузол в моєму зв'язаний список.

95
00:06:55,080 --> 00:06:58,340
>> Щоб отримати краще уявлення про пов'язаних списках, тому що це дуже важливо

96
00:06:58,340 --> 00:07:02,220
стежити за переконавшись, що ви підтримуєте ланцюга,

97
00:07:02,220 --> 00:07:09,990
Мені подобається думати про нього, як люди в лінію, тримаючись за руки,

98
00:07:09,990 --> 00:07:14,330
де кожна людина, тримаючись за руки наступного.

99
00:07:14,330 --> 00:07:18,350
Ви не можете бачити на цьому малюнку, але в основному вони вказують на наступний людина

100
00:07:18,350 --> 00:07:23,760
, Що в їх ланцюга.

101
00:07:23,760 --> 00:07:29,270
І тому, якщо ви хочете, щоб пройти зв'язаний список, де ці люди -

102
00:07:29,270 --> 00:07:32,830
Уявіть собі всі ці люди мають значення, пов'язані з ними

103
00:07:32,830 --> 00:07:36,590
, А також вказувати на наступний людина в лінії -

104
00:07:36,590 --> 00:07:40,810
якщо ви хочете, щоб пройти пов'язаного списку, наприклад, або змінити значення

105
00:07:40,810 --> 00:07:42,830
або шукати значення або щось на зразок цього,

106
00:07:42,830 --> 00:07:48,270
то ви хочете мати покажчик на конкретну людину.

107
00:07:48,270 --> 00:07:52,670
Таким чином, ми будемо мати вузол типу даних покажчика.

108
00:07:52,670 --> 00:07:55,580
Для цього, наприклад, назвемо його курсором.

109
00:07:55,580 --> 00:07:59,630
Інший поширений спосіб, щоб назвати це буде ітератор або щось на зразок того

110
00:07:59,630 --> 00:08:05,130
тому що це ітерації та насправді рухається, який вузол він вказує.

111
00:08:05,130 --> 00:08:14,410
Це тут буде наш курсор.

112
00:08:14,410 --> 00:08:20,180
Наш курсор спочатку вказувати на перший елемент в нашому списку.

113
00:08:20,180 --> 00:08:26,910
І тому те, що ми хочемо зробити, це ми хотіли б бути в основному продовжує курсор,

114
00:08:26,910 --> 00:08:29,130
переміщаючи його з боку в бік.

115
00:08:29,130 --> 00:08:33,409
У цьому випадку, ми хочемо, щоб перемістити його на наступний елемент у списку.

116
00:08:33,409 --> 00:08:38,480
З масивами, то, що ми робимо, що ми б просто сказати, що ми збільшенню індексу на 1.

117
00:08:38,480 --> 00:08:46,020
У цьому випадку, те, що ми повинні зробити, це насправді знайти людину який цей струм людина, що вказують на,

118
00:08:46,020 --> 00:08:48,930
і що це буде таке значення.

119
00:08:48,930 --> 00:08:53,230
Так що, якщо курсор знаходиться всього в вузлі покажчик, те, що ми хочемо зробити

120
00:08:53,230 --> 00:08:56,320
що ми хочемо, щоб дістатися до значення, що курсор вказує.

121
00:08:56,320 --> 00:09:01,350
Ми хочемо, щоб дістатися до цього вузла, а потім, коли ми знаходимося в цьому вузлі, дізнатися, де він вказує.

122
00:09:01,350 --> 00:09:05,820
Щоб дістатися до фактичного вузла, що курсор вказує на,

123
00:09:05,820 --> 00:09:13,160
Зазвичай ми вказуємо його (* курсора).

124
00:09:13,160 --> 00:09:19,160
Це дасть вам фактичного вузла, що курсор вказує.

125
00:09:19,160 --> 00:09:21,730
І потім, після того, що ми хочемо зробити, це ми хочемо отримати доступ

126
00:09:21,730 --> 00:09:25,680
все, що таке значення вузла є.

127
00:09:25,680 --> 00:09:32,820
Щоб зробити це, щоб отримати доступ до значень усередині структури, у нас є точка оператора.

128
00:09:32,820 --> 00:09:39,530
Таким чином, то це було б (* курсора). Наступний.

129
00:09:39,530 --> 00:09:44,840
Але це трохи брудний з погляду наявності дужки навколо * курсору,

130
00:09:44,840 --> 00:09:56,800
і тому ми замінити весь цей заяви з курсором>.

131
00:09:56,800 --> 00:10:02,700
Це тире, а потім знак більше, таким чином роблячи стрілки.

132
00:10:02,700 --> 00:10:05,840
Курсор-> далі.

133
00:10:05,840 --> 00:10:12,390
Це буде насправді вам вузол, який курсор миші. Це значення є наступною.

134
00:10:12,390 --> 00:10:16,790
Таким чином, замість того, зірки і крапка, ви замінюєте, що зі стрілкою.

135
00:10:16,790 --> 00:10:24,820
Будьте дуже обережні, щоб переконатися, що ви намагаєтеся використовувати цей синтаксис.

136
00:10:33,550 --> 00:10:37,620
>> Тепер, коли у нас є курсор, якщо ми хочемо отримати доступ до значення,

137
00:10:37,620 --> 00:10:40,450
перш, ми були курсору> наступний,

138
00:10:40,450 --> 00:10:46,260
але для доступу до значення в вузлі, що курсор вказує на, ми просто говорять

139
00:10:46,260 --> 00:10:48,070
вузол-> значення.

140
00:10:48,070 --> 00:10:53,600
Звідти, це тип даних все, що ми визначили значення і вузли, щоб бути.

141
00:10:53,600 --> 00:10:59,620
Якщо це ціле число вузлів, то курсор-> значення тільки збирається бути цілим числом.

142
00:10:59,620 --> 00:11:04,870
Так що ми можемо робити операції на те, що перевірка рівності, присвоїти різні значення, і т.д.

143
00:11:04,870 --> 00:11:11,090
Отже, що ви хочете зробити, якщо ви хочете, щоб перемістити курсор до наступного людині,

144
00:11:11,090 --> 00:11:15,270
Ви дійсно змінити значення курсора.

145
00:11:15,270 --> 00:11:19,340
Так як курсор знаходиться вузол покажчиків, можна змінити фактична адреса покажчика

146
00:11:19,340 --> 00:11:23,890
в адресу наступного вузла в вашому списку.

147
00:11:23,890 --> 00:11:28,930
Це просто якийсь код, де ви могли ітерації.

148
00:11:28,930 --> 00:11:31,230
Там, де у мене є коментар щось робити,

149
00:11:31,230 --> 00:11:33,850
ось де ви, ймовірно, отримати доступ до значення

150
00:11:33,850 --> 00:11:37,850
або зробити щось робити з цим конкретним вузлом.

151
00:11:37,850 --> 00:11:43,050
Щоб почати його, я кажу, що мій курсор спочатку

152
00:11:43,050 --> 00:11:48,430
буде вказувати на перший елемент в зв'язаний список.

153
00:11:48,430 --> 00:11:52,910
І ось попереду, я визначив його як главу вузла.

154
00:11:52,910 --> 00:11:57,610
>> Як я згадував раніше, звільняючи це дуже важливо.

155
00:11:57,610 --> 00:12:02,440
Ви хочете, щоб переконатися, що ви звільнитися кожен елемент у списку, як тільки ви закінчите з ним.

156
00:12:02,440 --> 00:12:04,940
Якщо у вас немає необхідності посилатися на будь-яке з цих покажчиків більше,

157
00:12:04,940 --> 00:12:10,620
Ви хочете, щоб переконатися, що ви звільняєте всі ці покажчики.

158
00:12:10,620 --> 00:12:14,460
Але ви хочете бути дуже обережним у тому, що ви хочете, щоб уникнути витоку пам'яті.

159
00:12:14,460 --> 00:12:25,080
Якщо ви безкоштовних однієї людини передчасно, то всі покажчики, що вузол вказує на

160
00:12:25,080 --> 00:12:26,900
будуть втрачені.

161
00:12:26,900 --> 00:12:32,070
Повертаючись до лиця Наприклад, щоб зробити його трохи більш високі ставки,

162
00:12:32,070 --> 00:12:49,600
давайте цим людям, але в даному випадку вони нависли над озером з монстром.

163
00:12:49,600 --> 00:12:53,200
Ми хочемо, щоб переконатися, що, коли ми вільні, ми не втрачаємо

164
00:12:53,200 --> 00:12:58,920
і відпустити будь-які вузли, перш ніж ми насправді звільнив їх.

165
00:12:58,920 --> 00:13:05,730
Наприклад, якщо б ви просто подзвонити безкоштовно на цього хлопця тут,

166
00:13:05,730 --> 00:13:15,350
Потім він буде звільнений, але потім всі з цих хлопців потім буде втрачений

167
00:13:15,350 --> 00:13:18,450
і вони будуть дрейфувати геть і опадають.

168
00:13:18,450 --> 00:13:24,900
Таким чином, ми хочемо переконатися, що замість цього, ми хочемо підтримувати зв'язок з іншими.

169
00:13:37,630 --> 00:13:42,480
Наш головний покажчик, який вказує на перший елемент у списку.

170
00:13:42,480 --> 00:13:49,990
Це ніби як мотузка якір від першої особи.

171
00:13:52,870 --> 00:13:57,470
Що ви можете зробити, коли ви звільнити списку є -

172
00:13:57,470 --> 00:14:04,520
Якщо ви хочете, щоб звільнити перший елемент перший, то ви можете мати тимчасовий покажчик

173
00:14:04,520 --> 00:14:07,370
, Який вказує на все, що перший елемент.

174
00:14:07,370 --> 00:14:11,420
Так що у вас є тимчасовий покажчик, який вказує тут.

175
00:14:11,420 --> 00:14:15,840
Таким чином, ми маємо в руки першого вузла.

176
00:14:15,840 --> 00:14:18,930
А потім, оскільки ми знаємо, що перший вузол буде звільнений,

177
00:14:18,930 --> 00:14:24,890
Потім ми можемо перейти цю мотузку, цей якір, наша голова,

178
00:14:24,890 --> 00:14:31,930
насправді вказують на все, що перше вказує.

179
00:14:31,930 --> 00:14:38,760
Таким чином, ця голова насправді вказує на другий елемент зараз.

180
00:14:38,760 --> 00:14:43,980
Зараз ми дозволили, щоб звільнити все, що зберігається в темп,

181
00:14:43,980 --> 00:14:53,360
і тому ми можемо стерти, що без нього загрозу всі інші вузли в нашому списку.

182
00:14:54,140 --> 00:15:05,020
Ще один спосіб, що ви можете зробити, це може бути

183
00:15:05,020 --> 00:15:08,650
кожен раз, коли ви просто звільнити останній елемент у списку

184
00:15:08,650 --> 00:15:11,010
тому що вони гарантовано не вказав ні до чого.

185
00:15:11,010 --> 00:15:15,570
Таким чином, можна просто звільнити цю одну, то безкоштовно це одне, то безкоштовно це.

186
00:15:15,570 --> 00:15:21,900
Це безперечно працює, але трохи повільніше, тому що за характером пов'язаних списків,

187
00:15:21,900 --> 00:15:24,670
Ми не можемо просто відразу перейти до останнього.

188
00:15:24,670 --> 00:15:28,030
Ми повинні пройти кожен елемент в зв'язаний список

189
00:15:28,030 --> 00:15:31,020
і переконайтеся в тому, що одне вказує на 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
а також мої ітератор, тощо.

207
00:16:40,730 --> 00:16:42,480
Чи означає це -? >> [Студент] Так.

208
00:16:42,480 --> 00:16:48,270
Це можливо, але з точки зору дизайнерських рішень, ви повинні зважити всі варіанти.

209
00:16:53,850 --> 00:17:01,090
>> Ось скелет коду, який дозволить вам звільнитися кожного елемента в зв'язаному списку.

210
00:17:01,090 --> 00:17:05,460
Знову ж таки, так як я ітерації пов'язаного списку, я збираюся хочуть мати якийсь курсор

211
00:17:05,460 --> 00:17:08,670
або ітераторів.

212
00:17:08,670 --> 00:17:14,640
Ми ітерації, поки курсор не NULL.

213
00:17:14,640 --> 00:17:17,640
Ви ж не хочете, щоб ітерації, коли курсор знаходиться 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 і. Про файлах.

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
Тут ми перевірка, яка повертає істину, якщо дане слово в словник.

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, тільки тепер він просто всі ці незробленого в цьому.

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
Ми як і раніше, і ми бачимо деякий файловий ввід / вивід тут,

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
Awesome.

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
Це ціле число хеш-таблиці.

397
00:34:31,320 --> 00:34:38,540
Таким чином, для першого відра, будь-які цілі нижче 10 вдаватися в першому відрі.

398
00:34:38,540 --> 00:34:42,190
Будь-які цілі вище 10, але нижче 20 Перейти в секунду,

399
00:34:42,190 --> 00:34:44,179
і так далі, і так далі.

400
00:34:44,179 --> 00:34:52,370
Для мене кожне відро, що представляють ці цифри.

401
00:34:52,370 --> 00:34:59,850
Тим не менш, сказати, що я була пройти в 50, наприклад.

402
00:34:59,850 --> 00:35:07,490
Здається, ніби перші три містять ряд з десяти цифр.

403
00:35:07,490 --> 00:35:12,570
Але я хочу, щоб мої хеш-таблиці, щоб приймати в будь-якому вигляді цілих чисел,

404
00:35:12,570 --> 00:35:19,860
так, то я мав би відфільтрувати всі числа більше 30, в останні відро.

405
00:35:19,860 --> 00:35:26,660
І таким чином, який призведе до свого роду незбалансоване хеш-таблиці.

406
00:35:31,330 --> 00:35:35,640
Повторюся, хеш-таблиця просто масив відра

407
00:35:35,640 --> 00:35:38,590
де кожне відро пов'язаного списку.

408
00:35:38,590 --> 00:35:43,730
І ось щоб визначити, де кожне значення виходить, що відро він переходить в,

409
00:35:43,730 --> 00:35:46,260
Ви будете хотіти те, що називається хеш-функції

410
00:35:46,260 --> 00:35:55,010
, Яка приймає значення, а потім говорить, що це значення відповідає певний відро.

411
00:35:55,010 --> 00:36:00,970
Так що нагорі в цьому прикладі, мій хеш-функції взяв кожного значення.

412
00:36:00,970 --> 00:36:03,020
Він перевірив, чи було це менше, ніж 10.

413
00:36:03,020 --> 00:36:05,360
Якби це було, це було б покласти його в першому відрі.

414
00:36:05,360 --> 00:36:08,910
Він перевіряє, чи є це менше 20, ставить його в другу якщо це правда,

415
00:36:08,910 --> 00:36:12,880
перевіряє, чи є це менше, ніж 30, а потім кладе його в третю відро,

416
00:36:12,880 --> 00:36:16,990
а потім все інше просто падає на четвертий відро.

417
00:36:16,990 --> 00:36:20,110
Тому, коли у вас є значення, ваш хеш-функції

418
00:36:20,110 --> 00:36:25,420
Покладіть це значення у відповідне відро.

419
00:36:25,420 --> 00:36:32,430
Хеш-функція в основному потрібно знати, скільки у вас є відра.

420
00:36:32,430 --> 00:36:37,960
Ваш розмір хеш-таблиці, кількість сегментів у вас є,

421
00:36:37,960 --> 00:36:41,190
що це буде фіксоване число це до вас, для вас, щоб вирішити,

422
00:36:41,190 --> 00:36:43,590
але це буде фіксоване число.

423
00:36:43,590 --> 00:36:51,840
Так що ваш хеш-функція буде покладатися на те, щоб визначити, до якої кожен ключ переходить у

424
00:36:51,840 --> 00:36:54,450
такий, що він рівномірно розподілений.

425
00:36:56,150 --> 00:37:03,820
Як і в нашій реалізації пов'язаних списків, тепер кожен вузол в хеш-таблиці

426
00:37:03,820 --> 00:37:07,000
насправді матиме тип символу.

427
00:37:07,000 --> 00:37:14,340
Тому у нас є масив символів називаються слова, а потім ще один покажчик на наступний вузол,

428
00:37:14,340 --> 00:37:19,010
який має сенс, тому що це буде пов'язаний список.

429
00:37:19,010 --> 00:37:24,350
Пам'ятаєте, коли ми були зв'язані списки, я зробив вузол * називається головою

430
00:37:24,350 --> 00:37:31,060
, Що вказувало на перший вузол у зв'язаному списку.

431
00:37:31,060 --> 00:37:34,020
Але для нашої хеш-таблицю, тому що у нас є декілька пов'язаних списків,

432
00:37:34,020 --> 00:37:37,520
те, що ми хочемо, ми хочемо, щоб наша хеш-таблиці, щоб бути, як: "Що таке відро?"

433
00:37:37,520 --> 00:37:43,340
Ківш являє собою список вузлів покажчиків,

434
00:37:43,340 --> 00:37:50,620
і так кожен елемент у відрі насправді вказує на відповідний зв'язаний список.

435
00:37:56,180 --> 00:38:01,520
Щоб повернутися до цієї схеми, ви бачите, що відра самі стрілки,

436
00:38:01,520 --> 00:38:06,980
не актуально вузлів.

437
00:38:11,680 --> 00:38:16,420
Одним з найважливіших властивостей хеш-функцій є те, що вони детерміновані.

438
00:38:16,420 --> 00:38:19,440
Це означає, що всякий раз, коли ви хеш № 2,

439
00:38:19,440 --> 00:38:22,270
вона завжди повинна повертати той же відро.

440
00:38:22,270 --> 00:38:26,440
Кожне значення, яке входить в хеш-функцію, якщо повторюється,

441
00:38:26,440 --> 00:38:29,690
повинен отримати той же індекс.

442
00:38:29,690 --> 00:38:34,210
Так що ваш хеш-функція повертає індекс масиву

443
00:38:34,210 --> 00:38:38,530
де це значення належить.

444
00:38:38,530 --> 00:38:41,790
Як я згадував раніше, кількість сегментів фіксоване,

445
00:38:41,790 --> 00:38:49,630
і тому ваш індекс, що ви повернетеся повинна бути менше, ніж кількість ковшів

446
00:38:49,630 --> 00:38:52,680
але більше 0.

447
00:38:52,680 --> 00:39:00,780
Причина, чому ми маємо хеш-функції, а не тільки одного пов'язаного списку

448
00:39:00,780 --> 00:39:09,290
або одного масиву є те, що ми хочемо, щоб мати можливість перейти до певної частини найбільш легко

449
00:39:09,290 --> 00:39:11,720
якщо ми знаємо, характерні значення -

450
00:39:11,720 --> 00:39:14,760
замість того, щоб шукати через весь весь словник,

451
00:39:14,760 --> 00:39:18,320
можливість переходу до певної її частини.

452
00:39:19,880 --> 00:39:24,440
Ваш хеш-функція повинна брати до уваги, що в ідеалі,

453
00:39:24,440 --> 00:39:28,980
кожного сегмента має приблизно таку ж кількість ключів.

454
00:39:28,980 --> 00:39:35,040
Так як хеш-таблиці являє собою серію пов'язаних списків,

455
00:39:35,040 --> 00:39:38,480
Потім пов'язаних списків самі будете мати більше, ніж одного вузла.

456
00:39:38,480 --> 00:39:43,210
У попередньому прикладі, два різних номери, хоча вони були не рівні,

457
00:39:43,210 --> 00:39:46,950
При хешіруется, повернеться тим же індексом.

458
00:39:46,950 --> 00:39:53,620
Так що, коли ви маєте справу зі словами, одним словом, коли хешіруется

459
00:39:53,620 --> 00:39:57,450
буде такою ж хеш-значення, як іншим словом.

460
00:39:57,450 --> 00:40:04,140
Це те, що ми називаємо зіткнення, коли у нас є вузол, який, коли хешіруется

461
00:40:04,140 --> 00:40:09,610
Зв'язаний список у цьому відрі не порожній.

462
00:40:09,610 --> 00:40:14,180
Техніка, яку ми називаємо є лінійне зондування,

463
00:40:14,180 --> 00:40:22,550
куди ви йдете в зв'язаному списку, а потім знайти, де ви хочете вставити цей вузол

464
00:40:22,550 --> 00:40:25,520
тому що у вас зіткнення.

465
00:40:25,520 --> 00:40:28,070
Ви можете бачити, що там може бути компроміс тут, чи не так?

466
00:40:28,070 --> 00:40:33,760
Якщо у вас є дуже маленький хеш-таблиці, дуже невелика кількість сегментів,

467
00:40:33,760 --> 00:40:36,380
то ви будете мати багато зіткнень.

468
00:40:36,380 --> 00:40:40,460
Але тоді, якщо ви робите дуже велику хеш-таблиці,

469
00:40:40,460 --> 00:40:44,110
ви, ймовірно, щоб звести до мінімуму зіткнення,

470
00:40:44,110 --> 00:40:47,170
але це буде дуже великою структури даних.

471
00:40:47,170 --> 00:40:49,310
Там збирається бути компроміси з цим.

472
00:40:49,310 --> 00:40:51,310
Тому, коли ви робите вашу 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
>> Які навантаження збираюся зробити, це перебір кожне слово в словнику.

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
і перебирати кожне слово в словнику.

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
, А потім привласнити це значення слова.

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
коли ми вставляємо його в тому, що структура вузлів собі, про структуру,

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
де це число є індексом, де хеш-таблиці за цим індексом уявляє, що відро.

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
а потім повторювати через кожні зв'язаний список у хеш-таблиці

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
Подібний Scramble, ми хочемо, щоб забезпечити нечутливість до регістру.

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
такі, що кожен унікальний слово завжди хешіруется те ж значення,

552
00:47:38,420 --> 00:47:43,340
Потім ми знаємо, що замість пошуку через всю нашу всій хеш-таблиці,

553
00:47:43,340 --> 00:47:48,310
ми дійсно можемо знайти пов'язаного списку, що це слово має належати.

554
00:47:48,310 --> 00:47:51,850
Якби це було в словнику, то це було б в цьому відрі.

555
00:47:51,850 --> 00:47:57,140
Що ми можемо зробити, якщо слово це ім'я нашої рядки передається,

556
00:47:57,140 --> 00:48:01,560
Ми можемо тільки хеш, що слово і погляд на зв'язаний список

557
00:48:01,560 --> 00:48:06,410
на значення хеш-таблиці [хеша (слово)].

558
00:48:06,410 --> 00:48:12,410
Звідти, що ми можемо зробити, це у нас є менша підмножина вузлів для пошуку цього слова,

559
00:48:12,410 --> 00:48:16,770
і тому ми можемо пройти через зв'язаний список, використовуючи приклад із раніше в керівництві

560
00:48:16,770 --> 00:48:24,110
, А потім викликати порівняння рядків на слово там, де курсор вказує на,

561
00:48:24,110 --> 00:48:28,430
це слово, і подивитися, чи є ці порівняння.

562
00:48:30,280 --> 00:48:35,110
Залежно від способу, що Вам організувати свій хеш-функції,

563
00:48:35,110 --> 00:48:39,260
якщо вона сортується, ви могли б повернутися помилковим трохи раніше,

564
00:48:39,260 --> 00:48:43,440
але якщо це несортоване, то ви хочете, щоб продовжити обхід через зв'язаний список

565
00:48:43,440 --> 00:48:46,480
поки ви не знайдете останній елемент списку.

566
00:48:46,480 --> 00:48:53,320
І якщо ви все ще не знайшли слів до того часу, як ви дійшли до кінця пов'язаного списку,

567
00:48:53,320 --> 00:48:56,890
це означає, що ваші слова не існує в словнику,

568
00:48:56,890 --> 00:48:59,410
і так, що слово є недійсним,

569
00:48:59,410 --> 00:49:02,730
і чек повинен повернутися помилковим.

570
00:49:02,730 --> 00:49:09,530
>> Тепер ми підійшли до вивантаження, де ми хочемо, щоб звільнити всіх вузлів, які ми malloc'd,

571
00:49:09,530 --> 00:49:14,050
так вільно всі вузли усередині нашої хеш-таблиці.

572
00:49:14,050 --> 00:49:20,270
Ми збираємося хочете перебрати всі зв'язані списки і безкоштовно всі вузли в цьому.

573
00:49:20,270 --> 00:49:29,350
Якщо ви подивитеся вище в керівництві наприклад, де ми звільнитися пов'язаного списку,

574
00:49:29,350 --> 00:49:35,140
то ви хочете, щоб повторити цей процес для кожного елемента в хеш-таблиці.

575
00:49:35,140 --> 00:49:37,780
І я піду на це до кінця проходження гри,

576
00:49:37,780 --> 00:49:46,600
але 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, а потім продовжити,

586
00:50:40,840 --> 00:50:42,960
але інші продовжують з ущільнювальним, наприклад.

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
тому що якщо ви правопис слова MAT, MA Я не думаю, що це дійсно слово, але мат.

592
00:51:30,120 --> 00:51:37,820
І тому у вашому Trie, це буде означати, що після MAT, що насправді це дійсно слово.

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
>> Підемо в приклад вигляді дерева.

602
00:52:50,500 --> 00:52:58,340
Перший у мене є кімната на 27 вузлах в цьому масиві.

603
00:52:58,340 --> 00:53:03,200
Якщо у мене є слово BAR -

604
00:53:13,310 --> 00:53:15,370
Якщо у мене є слово BAR, і я хочу, щоб вставити, що,

605
00:53:15,370 --> 00:53:22,700
перша буква B, так що якщо моя Trie порожній,

606
00:53:22,700 --> 00:53:29,910
B є другою букви алфавіту, так що я збираюся вибрати, щоб поставити це тут, на цьому індексі.

607
00:53:29,910 --> 00:53:33,450
Я хочу, щоб мати B тут.

608
00:53:33,450 --> 00:53:42,400
B буде вузол, який вказує на інший масив всіх можливих символів

609
00:53:42,400 --> 00:53:45,870
, Які можуть слідувати за буквою B.

610
00:53:45,870 --> 00:53:57,610
В даному випадку я маю справу зі словом BAR, так буде йти тут.

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
BAR повне слово, і тоді я буду мати точку R на інший вузол

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
Почнемо з B, і ми вже маємо B якості однієї з букв, яка в нашому словнику.

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
Отже, ми бачимо, що, коли ми як і раніше через B, а потім,

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
Тоді ми хотіли б зробити запис в F.

631
00:56:05,620 --> 00:56:11,320
F це вузол, який вказує на весь масив.

632
00:56:11,320 --> 00:56:22,790
Ми хотіли б знайти O, перейдіть на O, O, то посилання на весь список.

633
00:56:22,790 --> 00:56:35,340
Ми б B, а потім продовжити, ми б і R.

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. 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 до B

644
00:57:33,050 --> 00:57:39,750
і тільки що FOOB, FOOB ні слова, і це не зазначено в якості допустимим.

645
00:57:47,370 --> 00:57:57,600
У вигляді дерева, ви кожен вузол вказує, чи є це дійсно слово чи ні,

646
00:57:57,600 --> 00:58:05,840
, А потім кожен вузол також має масив з 27 вузлів покажчики

647
00:58:05,840 --> 00:58:09,520
що потім виберіть вузли самі.

648
00:58:09,520 --> 00:58:12,940
>> Ось спосіб, як ви можете визначити це.

649
00:58:12,940 --> 00:58:17,260
Однак, як і в хеш-таблицю-приклад, де у нас було головному вузлі *

650
00:58:17,260 --> 00:58:21,320
для позначення початку нашої зв'язаний список, ми також захочуть

651
00:58:21,320 --> 00:58:29,150
якимось чином знаючи, де початок нашої 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
По суті, за кожне слово ви збираєтеся хочете перебрати ваші 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
Так думають всі шляхи назад на Цезаря і Віженер,

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
І тоді ви перевіряєте значення у дітей [я]

670
00:59:55,300 --> 00:59:58,400
де [я] відповідає будь букві знаходимося.

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
і зробити новий вузол і є, що діти [я] вказують на це

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 до істинного

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
тому що, якщо значення NULL, що означає, що словник не має значення

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
і знайшов його в моїй синтаксичного дерева, в тому, що слово дійсно чи ні?

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
Ось чому так важливо для вивантаження у вигляді дерева, щоб переконатися, що ви звільнити нижню першим.

745
01:06:54,780 --> 01:06:59,480
Що ви можете зробити, це сказати для кожного вузла

746
01:06:59,480 --> 01:07:06,430
Я хочу, щоб вивантажити все про дітей.

747
01:07:16,060 --> 01:07:22,140
>> Тепер, коли ми перейшли вивантаження для хеш-таблиці методів, а також методу синтаксичного дерева,

748
01:07:22,140 --> 01:07:27,020
ми збираємося хочете подивитися на 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, це необов'язково, щоб кинути виклик Big Board.

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
Повернутися до цього, ви могли б побачити, якщо хтось використовував вигляді дерева

786
01:10:27,460 --> 01:10:31,700
Чи їх реалізація швидше, ніж ваш хеш-таблиці чи ні.

787
01:10:31,700 --> 01:10:35,290
Ви можете уявити Big Board кілька разів.

788
01:10:35,290 --> 01:10:37,660
Вона буде записувати самі останні записи.

789
01:10:37,660 --> 01:10:44,300
Тому, можливо, ви зміните своє хеш-функції, а потім зрозуміли, що це насправді набагато швидше

790
01:10:44,300 --> 01:10:46,780
або багато повільніше, ніж раніше.

791
01:10:46,780 --> 01:10:50,960
Це трохи кумедним способом.

792
01:10:50,960 --> 01:10:57,190
Там завжди 1 або 2 співробітників, які намагаються зробити мінімально можливий словник,

793
01:10:57,190 --> 01:11:00,210
так що це завжди цікаво дивитися.

794
01:11:00,210 --> 01:11:07,630
>> Використання для 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
Це одна має більш 100000 слів.

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
Так що ви просто можете зробити свій власний текстовий файл тільки з BAR, BAZ, 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
тому що тоді я гарантую, що ви будете працювати в меншій плутанини покажчик там.

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]