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
дзе ў нас ёсць элементы, якiя мы называем вузлы, якія маюць як каштоўнасць, а таксама паказальнік

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
, Каб падарожнічаць на дно і бясплатны мінімальна магчымых вузел 1.

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 1.

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]