1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> Кевін Шмід: Часам, пры будаўніцтве
Праграма, вы можаце выкарыстоўваць

3
00:00:10,890 --> 00:00:13,190
Структура дадзеных вядомы як слоўнік.

4
00:00:13,190 --> 00:00:17,960
Слоўнік Карты ключы, якія
звычайна радкі, да значэнняў, Інтс,

5
00:00:17,960 --> 00:00:21,900
сімвалы, паказальнік на нейкі прадмет,
усё, што хочам.

6
00:00:21,900 --> 00:00:26,510
Гэта проста, як звычайныя слоўнікі
што карта словы праз азначэнняў.

7
00:00:26,510 --> 00:00:29,440
>> Слоўнікі даюць нам
Здольнасць захоўваць інфармацыю

8
00:00:29,440 --> 00:00:32,750
асацыюецца з чымсьці
і паглядзець яго пазней.

9
00:00:32,750 --> 00:00:36,620
Так як жа мы на самай справе рэалізаваць
слоўнік, скажам, З-кода, мы можам

10
00:00:36,620 --> 00:00:38,460
выкарыстоўваць у адной з нашых праграм?

11
00:00:38,460 --> 00:00:41,790
Ну, ёсць шмат спосабаў, якімі
мы маглі б рэалізаваць слоўнік.

12
00:00:41,790 --> 00:00:45,930
>> З аднаго боку, мы маглі б выкарыстоўваць масіў, што мы
дынамічна змяняць памеры або мы маглі б выкарыстоўваць

13
00:00:45,930 --> 00:00:49,150
звязаны спіс, хэш-табліцы
або бінарнае дрэва.

14
00:00:49,150 --> 00:00:52,250
Але што б мы ні абралі, мы павінны
памятаць аб эфектыўнасці і

15
00:00:52,250 --> 00:00:54,300
Прадукцыйнасць падсістэмы.

16
00:00:54,300 --> 00:00:57,930
Мы павінны думаць пра алгарытму, які выкарыстоўваецца
ўставіць і паглядзець элементы ў

17
00:00:57,930 --> 00:00:59,120
наша структура дадзеных.

18
00:00:59,120 --> 00:01:03,060
>> А цяпер давайце выкажам здагадку, што мы
хочаце выкарыстоўваць радкі ў якасці ключоў.

19
00:01:03,060 --> 00:01:07,290
Давайце пагаворым аб адной магчымасці,
структура дадзеных называецца сінтаксічнага дрэва.

20
00:01:07,290 --> 00:01:11,210
Такім чынам, вось візуальнае ўяўленне
з выглядзе дрэва.

21
00:01:11,210 --> 00:01:14,590
>> Як карціна мяркуе, выглядзе дрэва
гэта структура дадзеных дрэва з

22
00:01:14,590 --> 00:01:16,050
вузлы звязаныя паміж сабой.

23
00:01:16,050 --> 00:01:19,420
Мы бачым, што ёсць выразна корань
вузел з некалькі спасылак распаўсюджваецца на

24
00:01:19,420 --> 00:01:20,500
іншых вузлоў.

25
00:01:20,500 --> 00:01:23,040
Але тое, што кожны вузел складаецца?

26
00:01:23,040 --> 00:01:26,700
Калі выказаць здагадку, што мы захоўвання ключоў
толькі з літары алфавіту, і

27
00:01:26,700 --> 00:01:30,150
мы не клапоцімся аб капіталізацыі,
вось вызначэнне вузла,

28
00:01:30,150 --> 00:01:31,100
хопіць.

29
00:01:31,100 --> 00:01:34,130
>> Аб'ект, тып якога з'яўляецца структура
вузел складаецца з двух частак

30
00:01:34,130 --> 00:01:35,740
называюцца дадзенымі і дзяцей.

31
00:01:35,740 --> 00:01:39,200
Мы пакінулі частка дадзеных як каментар
павінны быць замененыя складнікам

32
00:01:39,200 --> 00:01:43,190
Дэкларацыя, калі структура вузел
ўключаны ў праграму C.

33
00:01:43,190 --> 00:01:47,040
Частка дадзеных вузла можа быць
Лагічнае значэнне, каб паказаць, ці з'яўляецца ці

34
00:01:47,040 --> 00:01:51,160
ня вузел, які ўяўляе сабой завяршэнне
з слоўніка ключа ці гэта можа быць

35
00:01:51,160 --> 00:01:54,240
Радок, якая ўяўляе вызначэнне
слова ў слоўніку.

36
00:01:54,240 --> 00:01:58,870
>> Мы будзем выкарыстоўваць смайлік для абазначэння
калі дадзеныя прысутнічаюць у вузле.

37
00:01:58,870 --> 00:02:02,310
Ёсць 26 элементаў у нашай
дзеці масіў, адзін індэкс

38
00:02:02,310 --> 00:02:03,690
за літары.

39
00:02:03,690 --> 00:02:06,570
Мы ўбачым значэнне
гэта ў бліжэйшы час.

40
00:02:06,570 --> 00:02:10,759
>> Давайце больш уважліва паглядзім каранёвага вузла
ў нашай схеме, якая не мае дадзеных

41
00:02:10,759 --> 00:02:14,740
звязаныя з ім, як паказана
адсутнасць смайлік ў

42
00:02:14,740 --> 00:02:16,110
частка дадзеных.

43
00:02:16,110 --> 00:02:19,910
Стрэлкі, якія ідуць ад частак
дзеці масіва прадстаўляюць не-вузел

44
00:02:19,910 --> 00:02:21,640
паказальнікі на іншыя вузлы.

45
00:02:21,640 --> 00:02:25,500
Напрыклад, стрэлка праходзіць ад
другі элемент дзяцей

46
00:02:25,500 --> 00:02:28,400
ўяўляе літару B
у ключы слоўніка.

47
00:02:28,400 --> 00:02:31,920
І ў больш шырокім дыяграме
мы называем яго з В.

48
00:02:31,920 --> 00:02:35,810
>> Адзначым, што ў большай схеме, калі мы
намаляваць паказальнік на іншы вузел, гэта

49
00:02:35,810 --> 00:02:39,100
Не мае значэння, дзе стрэлка
адказвае, што іншы вузел.

50
00:02:39,100 --> 00:02:43,850
Наш слоўнік ўзор сінтаксічнага дрэва ўтрымлівае
два словы, што і зум.

51
00:02:43,850 --> 00:02:47,040
Давайце разгледзім прыклад
гледзячы дадзеныя для ключа.

52
00:02:47,040 --> 00:02:50,800
>> Выкажам здагадку, мы хочам паглядзець
адпаведнае значэнне для ключавога ваннай.

53
00:02:50,800 --> 00:02:53,610
Мы пачнем наш погляд уверх
у каранёвым вузле.

54
00:02:53,610 --> 00:02:57,870
Тады мы будзем прымаць першую літару нашай
Ключ, У і знайсці адпаведны

55
00:02:57,870 --> 00:03:00,020
пляма ў нашай дзіцячай масіва.

56
00:03:00,020 --> 00:03:04,490
Звярніце ўвагу, што існуе роўна 26 месцаў
ў масіве, па адным для кожнай літары

57
00:03:04,490 --> 00:03:05,330
алфавіт.

58
00:03:05,330 --> 00:03:08,800
І мы будзем мець плямы ўяўляюць
літары алфавіту па парадку.

59
00:03:08,800 --> 00:03:13,960
>> Мы разгледзім другі індэкс, то,
Індэкс адзін, для В. Увогуле, калі мы

60
00:03:13,960 --> 00:03:17,990
ёсць алфавітны сімвал з мы
можа вызначыць адпаведную кропку

61
00:03:17,990 --> 00:03:21,520
ў масіве дзяцей з выкарыстаннем
Разлік, як гэта.

62
00:03:21,520 --> 00:03:25,140
Мы маглі б выкарыстоўваць большы дзяцей
Масіў, калі мы хацелі прапанаваць Глядзі вышэй

63
00:03:25,140 --> 00:03:28,380
клавішы з больш шырокім дыяпазонам знакаў,
такіх як усёй

64
00:03:28,380 --> 00:03:29,880
Набор сімвалаў ASCII.

65
00:03:29,880 --> 00:03:32,630
>> У гэтым выпадку паказальнік
ў нашых дзецях масіва ў

66
00:03:32,630 --> 00:03:34,320
Індэкс адзін не з'яўляецца нулявым.

67
00:03:34,320 --> 00:03:36,600
Таму мы будзем працягваць шукаць
да ключавога ваннай.

68
00:03:36,600 --> 00:03:40,130
Калі мы калі-небудзь сутыкаліся нулявы паказальнік
на належным месцы ў дзяцей

69
00:03:40,130 --> 00:03:43,230
Масіў у той час як мы перасеклі вузлы,
то мы павінны будзем сказаць, што мы

70
00:03:43,230 --> 00:03:45,630
не мог знайсці нічога для гэтага ключа.

71
00:03:45,630 --> 00:03:49,370
>> Зараз, мы будзем прымаць другую літару
наш ключ, і працягвайце прытрымлівацца

72
00:03:49,370 --> 00:03:52,400
паказальнікі на гэтым шляху пакуль мы
дойдзе да канца наш ключ.

73
00:03:52,400 --> 00:03:56,530
Калі мы дасягаем канца ключа без
дзівячы любыя тупікоў, нулявых паказальнікаў,

74
00:03:56,530 --> 00:03:59,730
як гэта мае месца тут, то мы толькі
павінны праверыць яшчэ адну рэч.

75
00:03:59,730 --> 00:04:02,110
Гэта ключ на самай справе
ў слоўніку?

76
00:04:02,110 --> 00:04:07,660
>> Калі гэта так, мы павінны знайсці значэнне, а
смайлік значок твар у нашай дыяграме, дзе

77
00:04:07,660 --> 00:04:08,750
слова заканчваецца.

78
00:04:08,750 --> 00:04:12,270
Калі ёсць што-то яшчэ захоўваюцца з
дадзеныя, то мы можам вярнуць яго.

79
00:04:12,270 --> 00:04:16,500
Напрыклад, ключ заапарку не знаходзіцца ў
слоўнік, хоць мы маглі б мець

80
00:04:16,500 --> 00:04:19,810
падышоў да канца гэтага ключа, нават не
патрапіўшы ў пусты паказальнік, у той час як мы

81
00:04:19,810 --> 00:04:21,089
перабору сінтаксічнага дрэва.

82
00:04:21,089 --> 00:04:25,436
>> Калі б мы паспрабавалі паглядзець ключавую ванну,
другі індэкса масіва ў мінулым вузла,

83
00:04:25,436 --> 00:04:28,750
адпаведны літарай H, будзе
правялі нулявы паказальнік.

84
00:04:28,750 --> 00:04:31,120
Так ванна не ў слоўніку.

85
00:04:31,120 --> 00:04:34,800
І так сінтаксічнага дрэва унікальны тым, што ключоў
ніколі не відавочна захоўваецца ў

86
00:04:34,800 --> 00:04:36,650
Структура дадзеных.

87
00:04:36,650 --> 00:04:38,810
Так як жа нам ўставіць нешта
ў выглядзе дрэва?

88
00:04:38,810 --> 00:04:41,780
>> Давайце ўстаўце ключ
заапарк у наш сінтаксічнага дрэва.

89
00:04:41,780 --> 00:04:46,120
Памятаеце, што смайлік ў вузле
можа адпавядаць у кодзе для простай

90
00:04:46,120 --> 00:04:50,170
Лагічнае значэнне, каб паказаць, што заапарк
ёсць у слоўніку, ці гэта мог

91
00:04:50,170 --> 00:04:53,710
адпавядаюць атрымання дадатковай інфармацыі, што мы
хочаце звязаць з ключавым заапарку,

92
00:04:53,710 --> 00:04:56,860
як вызначэнне
слова ці нешта яшчэ.

93
00:04:56,860 --> 00:05:00,350
У пэўным сэнсе, працэс ўставіць
нешта ў выглядзе дрэва падобная

94
00:05:00,350 --> 00:05:02,060
гледзячы нешта ў выглядзе дрэва.

95
00:05:02,060 --> 00:05:05,720
>> Мы пачнем з каранёвага вузла зноў,
Наступныя паказальнікі, якія адпавядаюць

96
00:05:05,720 --> 00:05:07,990
літары наш ключ.

97
00:05:07,990 --> 00:05:11,310
На шчасце, мы былі ў стане прытрымлівацца паказальнікі
на ўсім шляху, пакуль мы не дасягнулі

98
00:05:11,310 --> 00:05:12,770
канец ключа.

99
00:05:12,770 --> 00:05:16,480
Паколькі заапарк з'яўляецца прэфіксам словы
зум, які з'яўляецца членам

100
00:05:16,480 --> 00:05:19,440
слоўнік, мы не павінны
вылучыць якіх-небудзь новых вузлоў.

101
00:05:19,440 --> 00:05:23,140
>> Мы можам змяніць вузел, каб паказаць, што
шлях персанажаў, якія вядуць да

102
00:05:23,140 --> 00:05:25,360
яна ўяўляе сабой ключ ў нашым слоўніку.

103
00:05:25,360 --> 00:05:28,630
Цяпер, давайце паспрабуем ўстаўкі
Ключ БАНЯ ў сінтаксічнага дрэва.

104
00:05:28,630 --> 00:05:32,260
Мы пачнем ў каранёвым вузле
і вынікайце паказальнікі зноў.

105
00:05:32,260 --> 00:05:35,620
Але ў гэтай сітуацыі, мы патрапілі ў мёртвых
канец да мы ў стане дабрацца да

106
00:05:35,620 --> 00:05:36,940
канец ключа.

107
00:05:36,940 --> 00:05:40,980
Цяпер мы павінны вылучыць некаторыя новыя
вузлы спатрэбіцца вылучыць адзін новы

108
00:05:40,980 --> 00:05:43,660
вузел для кожнага хто застаўся
Ліст нашым ключом.

109
00:05:43,660 --> 00:05:46,740
>> У гэтым выпадку, мы проста павінны
вылучыць адзін новы вузел.

110
00:05:46,740 --> 00:05:50,590
Тады мы павінны будзем зрабіць індэкс H
спасылайцеся на гэты новы вузел.

111
00:05:50,590 --> 00:05:54,070
Яшчэ раз, мы можам змяніць вузел
сведчаць аб тым, што шлях знакаў

112
00:05:54,070 --> 00:05:57,120
вядучая да яго ўяўляе сабой
Ключавым у нашым слоўніку.

113
00:05:57,120 --> 00:06:00,730
Давайце разважаць пра асімптатычнае
Складанасць нашых працэдур для гэтых

114
00:06:00,730 --> 00:06:02,110
дзве аперацыі.

115
00:06:02,110 --> 00:06:06,420
>> Заўважым, што ў абодвух выпадках лік
з крокі наш алгарытм ўзяў было

116
00:06:06,420 --> 00:06:09,470
прапарцыйная колькасці
літары ў ключавое слова.

117
00:06:09,470 --> 00:06:10,220
Гэта дакладна.

118
00:06:10,220 --> 00:06:13,470
Калі вы хочаце шукаць слова ў
сінтаксічнага дрэва трэба проста перабіраць

119
00:06:13,470 --> 00:06:17,100
літары па адным, пакуль вы альбо
дойдзе да канца слова ці

120
00:06:17,100 --> 00:06:19,060
зайшлі ў тупік у сінтаксічнага дрэва.

121
00:06:19,060 --> 00:06:22,470
>> І калі вы хочаце ўставіць ключ
значэнне пары ў выглядзе дрэва з дапамогай

122
00:06:22,470 --> 00:06:26,250
Працэдура мы абмяркоўвалі, у горшым выпадку
будзе ў вас выдзялення новага вузла

123
00:06:26,250 --> 00:06:27,550
для кожнай літары.

124
00:06:27,550 --> 00:06:31,290
І мы будзем лічыць, што размеркаванне
пастаянная работа час.

125
00:06:31,290 --> 00:06:35,850
Так што, калі мы мяркуем, што даўжыня ключа
абмежаваны фіксаванай канстантай, як

126
00:06:35,850 --> 00:06:39,400
устаўка і паглядзець сталыя
Час аперацыі для выглядзе дрэва.

127
00:06:39,400 --> 00:06:42,930
>> Калі мы не будзем рабіць гэта здагадка, што
даўжыня ключа абмежаваная фіксаваным

128
00:06:42,930 --> 00:06:46,650
пастаянная, то ўстаўка і паглядзіце уверх,
у горшым выпадку, лінейных па

129
00:06:46,650 --> 00:06:48,240
Даўжыня ключа.

130
00:06:48,240 --> 00:06:51,800
Звярніце ўвагу, што колькасць элементаў захоўваюцца
у сінтаксічнага дрэва не ўплывае на знешні выгляд да

131
00:06:51,800 --> 00:06:52,820
або час ўстаўкі.

132
00:06:52,820 --> 00:06:55,360
Гэта толькі ўплыў
Даўжыня ключа.

133
00:06:55,360 --> 00:06:59,300
>> З іншага боку, даданне элементаў, скажам,
хэш-табліцу прыводзіць да таго,

134
00:06:59,300 --> 00:07:01,250
Будучыня паглядзець больш павольна.

135
00:07:01,250 --> 00:07:04,520
Хоць гэта можа здацца прывабным у першую чаргу,
мы павінны мець на ўвазе, што

136
00:07:04,520 --> 00:07:08,740
спрыяльная асімптатычнай складанасці не
азначае, што на практыцы дадзеныя

137
00:07:08,740 --> 00:07:11,410
Структура абавязкова
бездакорным.

138
00:07:11,410 --> 00:07:15,860
Мы таксама павінны ўлічваць, што для захоўвання
слова ў выглядзе дрэва, мы павінны, у горшым

139
00:07:15,860 --> 00:07:19,700
так, лік вузлоў прапарцыйная
даўжыні самога слова.

140
00:07:19,700 --> 00:07:21,880
>> Спрабуе як правіла, выкарыстоўваюць шмат месца.

141
00:07:21,880 --> 00:07:25,620
Гэта ў адрозненне ад хэш-табліцы,
дзе нам патрэбен толькі адзін новы вузел да

142
00:07:25,620 --> 00:07:27,940
захоўваць некаторыя ключавыя каштоўнасці пару.

143
00:07:27,940 --> 00:07:31,370
Цяпер зноў у тэорыі, вялікая прастора
Выдатак не здаецца, што вялікая

144
00:07:31,370 --> 00:07:34,620
справа, асабліва ўлічваючы, што сучасныя
кампутары маюць гігабайт і

145
00:07:34,620 --> 00:07:36,180
гігабайт памяці.

146
00:07:36,180 --> 00:07:39,200
Але аказваецца, што ў нас яшчэ ёсць
турбавацца аб выкарыстанні памяці і

147
00:07:39,200 --> 00:07:42,540
арганізацыя дзеля
прадукцыйнасць, так як сучасныя кампутары

148
00:07:42,540 --> 00:07:46,960
укараніць механізмы пад
капот, каб паскорыць доступ да памяці.

149
00:07:46,960 --> 00:07:51,180
>> Але гэтыя механізмы працуюць лепш, калі
доступ да памяці выкананы ў кампактнай

150
00:07:51,180 --> 00:07:52,810
рэгіёны або раёны.

151
00:07:52,810 --> 00:07:55,910
І вузлы выглядзе дрэва можа знаходзіцца
у любым месцы ў гэтай кучы.

152
00:07:55,910 --> 00:07:58,390
Але гэта кампрамісы
што мы павінны разгледзець.

153
00:07:58,390 --> 00:08:01,440
>> Памятаеце, што пры выбары дадзеных
Структура для пэўнай задачы, мы

154
00:08:01,440 --> 00:08:04,420
павінны думаць пра тое, якія з
аперацыі структура дадзеных павінна

155
00:08:04,420 --> 00:08:07,140
падтрымка і колькі прадукцыйнасць
кожнага з тых,

156
00:08:07,140 --> 00:08:09,080
аперацыі мае значэнне для нас.

157
00:08:09,080 --> 00:08:11,300
Гэтыя аперацыі могуць нават
выходзяць за рамкі проста

158
00:08:11,300 --> 00:08:13,430
асноўны выгляд і ўстаўкі.

159
00:08:13,430 --> 00:08:17,010
Выкажам здагадку, мы хочам рэалізаваць свайго роду
з аўтазапаўнення функцыянальнасць, нашмат

160
00:08:17,010 --> 00:08:18,890
як пошукавая сістэма Google робіць.

161
00:08:18,890 --> 00:08:22,210
Гэта значыць, вярнуць усе ключы і
патэнцыйна каштоўнасці, якія

162
00:08:22,210 --> 00:08:24,130
ёсць зададзенага прэфікса.

163
00:08:24,130 --> 00:08:27,050
>> Сінтаксічнага дрэва адназначна карысна
Для выканання гэтай аперацыі.

164
00:08:27,050 --> 00:08:29,890
Ён проста перабраць
сінтаксічнага дрэва для кожнага знака

165
00:08:29,890 --> 00:08:30,950
прэфікс.

166
00:08:30,950 --> 00:08:33,559
Гэтак жа, як глядзець уверх аперацыі,
мы маглі прытрымлівацца паказальнікі

167
00:08:33,559 --> 00:08:35,400
посимвольно.

168
00:08:35,400 --> 00:08:38,659
Потым, калі мы прыходзім у канцы
прэфікс, мы маглі перабору

169
00:08:38,659 --> 00:08:42,049
Астатняя частка структуры дадзеных
так як любы з ключоў за

170
00:08:42,049 --> 00:08:43,980
гэты пункт маюць прэфікс.

171
00:08:43,980 --> 00:08:47,670
>> Гэта таксама лёгка атрымаць гэты лістынг
ў алфавітным парадку, так як

172
00:08:47,670 --> 00:08:50,970
Элементы масіва дзяцей
размяшчаюцца ў алфавітным парадку.

173
00:08:50,970 --> 00:08:54,420
Так, спадзяюся, вы разгледзець
прадастаўленне спрабуе паспрабаваць.

174
00:08:54,420 --> 00:08:56,085
Я Кевін Шмід, і гэта CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ах, гэта пачатак
заняпаду.

177
00:09:00,790 --> 00:09:01,350
Мне вельмі шкада.

178
00:09:01,350 --> 00:09:01,870
Выбачайце.

179
00:09:01,870 --> 00:09:02,480
Выбачайце.

180
00:09:02,480 --> 00:09:03,130
Выбачайце.

181
00:09:03,130 --> 00:09:03,950
>> Удар чатыры.

182
00:09:03,950 --> 00:09:04,360
Я сыходжу.

183
00:09:04,360 --> 00:09:05,280
Выбачайце.

184
00:09:05,280 --> 00:09:06,500
Выбачайце.

185
00:09:06,500 --> 00:09:07,490
Выбачайце.

186
00:09:07,490 --> 00:09:12,352
Выбачайце за чалавека, які
павінен змяніць гэтую сысці з розуму.

187
00:09:12,352 --> 00:09:13,280
>> Выбачайце.

188
00:09:13,280 --> 00:09:13,880
Выбачайце.

189
00:09:13,880 --> 00:09:15,080
Выбачайце.

190
00:09:15,080 --> 00:09:15,680
Выбачайце.

191
00:09:15,680 --> 00:09:16,280
>> Выступоўца 1: Малайцы.

192
00:09:16,280 --> 00:09:17,530
Гэта было сапраўды добра зроблена.

193
00:09:17,530 --> 00:09:18,430