1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
Дъг LLOYD: Така че в CS50, ние сме обхванати
много различни структури от данни,

3
00:00:08,300 --> 00:00:09,180
нали?

4
00:00:09,180 --> 00:00:11,420
Виждали сме масиви, и свързана
списъци и хеш таблици,

5
00:00:11,420 --> 00:00:15,210
и се опитва, стекове и опашки.

6
00:00:15,210 --> 00:00:17,579
Ние също така ще научите малко
около дървета и грамади,

7
00:00:17,579 --> 00:00:20,120
но наистина те просто свърши
сметка е вариации по темата.

8
00:00:20,120 --> 00:00:22,840
Там наистина са тези
вид четири основни идеи

9
00:00:22,840 --> 00:00:25,190
че всичко друго може да се свеждат до.

10
00:00:25,190 --> 00:00:28,150
Масиви, свързани списъци,
хеш таблици и опит.

11
00:00:28,150 --> 00:00:30,720
И както казах, има
са вариации на тях,

12
00:00:30,720 --> 00:00:32,720
но това е доста
много ще обобщим

13
00:00:32,720 --> 00:00:38,140
всичко, което ще говорим
около в този клас по отношение на C.

14
00:00:38,140 --> 00:00:40,140
>> Но как всички тези мерки се, нали?

15
00:00:40,140 --> 00:00:44,265
Ние говорихме за плюсовете и минусите
на всеки в отделни клипове на тях,

16
00:00:44,265 --> 00:00:46,390
но има много номера
Първи хвърлен наоколо.

17
00:00:46,390 --> 00:00:48,723
Има много неща, на обща
размисли получаване хвърлени наоколо.

18
00:00:48,723 --> 00:00:51,950
Нека се опитаме и да консолидира
то в само едно място.

19
00:00:51,950 --> 00:00:55,507
Нека да претеглят плюсовете срещу
недостатъците, и да обмислят

20
00:00:55,507 --> 00:00:57,340
които структурата на данните
може да бъде правилният данни

21
00:00:57,340 --> 00:01:01,440
структура за вашия конкретен случай,
без значение какъв вид данни, което приберете.

22
00:01:01,440 --> 00:01:06,625
Не е задължително винаги трябва да
използвате супер бързо вмъкване, изтриване,

23
00:01:06,625 --> 00:01:10,761
и справка за синтактично дърво, ако наистина
не се грижи за вмъкване и изтриване

24
00:01:10,761 --> 00:01:11,260
твърде много.

25
00:01:11,260 --> 00:01:13,968
Ако имате нужда просто бързо случайна
достъп, може би е по-добре масив.

26
00:01:13,968 --> 00:01:15,340
Така че нека да дестилират това.

27
00:01:15,340 --> 00:01:18,530
Нека поговорим за всеки един от четиримата
основните видове структури от данни

28
00:01:18,530 --> 00:01:21,720
че сме говорили за и
Просто вижте, когато те могат да бъдат добри,

29
00:01:21,720 --> 00:01:23,340
и когато не може да бъде толкова добър.

30
00:01:23,340 --> 00:01:24,610
Така че нека да започнем с масиви.

31
00:01:24,610 --> 00:01:27,300
Така вмъкване, че е нещо лошо.

32
00:01:27,300 --> 00:01:31,350
>> Включване в края на масив е ОК,
ако ние строим масив като отидем.

33
00:01:31,350 --> 00:01:33,570
Но ако трябва да поставите
елементи в средата,

34
00:01:33,570 --> 00:01:35,550
мисля, обратно на вмъкване
сортиране, има много

35
00:01:35,550 --> 00:01:37,510
на изместване за да се поберат един елемент там.

36
00:01:37,510 --> 00:01:41,170
И така, ако ще да вмъкнете
навсякъде, но в края на масив,

37
00:01:41,170 --> 00:01:43,590
че вероятно не е толкова голяма.

38
00:01:43,590 --> 00:01:46,710
>> По същия начин, заличаване, освен ако не сме
изтриване от края на масив,

39
00:01:46,710 --> 00:01:49,810
е може би също не е толкова голяма, ако
ние не искаме да оставим празни пропуски,

40
00:01:49,810 --> 00:01:50,790
които обикновено не го правим.

41
00:01:50,790 --> 00:01:54,700
Искаме да премахнете елемент, и
След това нещо да го плътно отново.

42
00:01:54,700 --> 00:01:57,670
И така изтриване на елементи от
масив, също не е толкова голяма.

43
00:01:57,670 --> 00:01:58,820
>> Търсене, обаче, е страхотно.

44
00:01:58,820 --> 00:02:00,920
Имаме произволен достъп,
константно време за справка.

45
00:02:00,920 --> 00:02:03,800
Ние просто кажем, седем, и да отидем
да масив преместване седем.

46
00:02:03,800 --> 00:02:05,907
Ние казваме, 20, с Отиди на
масив преместване 20.

47
00:02:05,907 --> 00:02:07,240
Ние не трябва да превъртите цяла.

48
00:02:07,240 --> 00:02:08,630
Това е доста добър.

49
00:02:08,630 --> 00:02:11,020
>> Масивите са също сравнително лесно да се справи.

50
00:02:11,020 --> 00:02:14,040
Всеки път, когато говорихме за сортиране
алгоритъм, като избор на сортиране,

51
00:02:14,040 --> 00:02:18,820
сортиране чрез вмъкване, метод на мехурчето, се слеят
сортиране, ние винаги се използва масиви да го направя,

52
00:02:18,820 --> 00:02:21,860
защото масиви са доста лесни за
вид, по отношение на структурите от данни

53
00:02:21,860 --> 00:02:22,970
сме виждали досега.

54
00:02:22,970 --> 00:02:24,320
>> Освен това те са сравнително малко.

55
00:02:24,320 --> 00:02:25,695
Там не е много допълнително пространство.

56
00:02:25,695 --> 00:02:29,210
Ти просто да отмени точно толкова,
колкото е необходимо, за да държат вашите данни,

57
00:02:29,210 --> 00:02:30,320
и това е доста го много.

58
00:02:30,320 --> 00:02:33,180
Така че те са доста малки
и ефективно по този начин.

59
00:02:33,180 --> 00:02:36,000
Но друг недостатък, обаче,
е, че те са фиксирани по размер.

60
00:02:36,000 --> 00:02:38,630
Ние трябва да декларират как точно
голяма искаме нашия масив да бъде,

61
00:02:38,630 --> 00:02:39,940
а ние само се получи един изстрел в него.

62
00:02:39,940 --> 00:02:41,280
Ние не може да расте и да го свие.

63
00:02:41,280 --> 00:02:44,582
>> Ако имаме нужда да расте или да го свие, ние
трябва да декларират изцяло нов масив,

64
00:02:44,582 --> 00:02:47,750
копирате всички елементи на
Първият масив във втория масив.

65
00:02:47,750 --> 00:02:51,410
И ако ние неправилно оцени, че
време, ние трябва да го направя отново.

66
00:02:51,410 --> 00:02:52,760
Не е толкова голяма.

67
00:02:52,760 --> 00:02:58,750
Така масиви не ни дават гъвкавост
да има променлива брой елементи.

68
00:02:58,750 --> 00:03:01,320
>> С свързан списък,
вмъкване е доста лесно.

69
00:03:01,320 --> 00:03:03,290
Ние просто халс върху предната част.

70
00:03:03,290 --> 00:03:04,892
Заличаване също е доста лесно.

71
00:03:04,892 --> 00:03:06,100
Трябва да намерим елементите.

72
00:03:06,100 --> 00:03:07,270
Това включва известно търсене.

73
00:03:07,270 --> 00:03:10,270
>> Но след като веднъж сте открили елемента
което търсите, всичко, което трябва да направите,

74
00:03:10,270 --> 00:03:12,830
е промяна на показалеца,
вероятно две, ако имате

75
00:03:12,830 --> 00:03:15,151
свързан с двойно list--
свързан списък, rather--

76
00:03:15,151 --> 00:03:16,650
и след това може просто да освободи възела.

77
00:03:16,650 --> 00:03:18,399
Вие не трябва да се смени
всичко наоколо.

78
00:03:18,399 --> 00:03:22,090
Можете просто смяна два указатели,
така че това е доста бързо.

79
00:03:22,090 --> 00:03:23,470
>> Търсене е лошо все пак, нали?

80
00:03:23,470 --> 00:03:26,280
За да можем да намерим
елемент в свързан списък,

81
00:03:26,280 --> 00:03:29,154
независимо дали поотделно или двойно свързан,
ние трябва да линеен го търси.

82
00:03:29,154 --> 00:03:32,320
Ние трябва да започнем от самото начало и
преместете края, или да започне в края на ход

83
00:03:32,320 --> 00:03:33,860
в началото.

84
00:03:33,860 --> 00:03:35,474
Ние не разполагаме с произволен достъп вече.

85
00:03:35,474 --> 00:03:37,265
Така че, ако ние сме прави
Много от търсенето, може би

86
00:03:37,265 --> 00:03:39,830
свързан списък не е
чак толкова добро за нас.

87
00:03:39,830 --> 00:03:43,750
>> Освен това те са наистина
трудно да се справи, нали?

88
00:03:43,750 --> 00:03:45,666
Единственият начин можете
Наистина сортирате свързан списък

89
00:03:45,666 --> 00:03:47,870
е да го оправи, докато го построи.

90
00:03:47,870 --> 00:03:50,497
Но ако го оправи, колкото
го изгради, вече не сте

91
00:03:50,497 --> 00:03:51,830
правене на бързи вмъквания вече.

92
00:03:51,830 --> 00:03:53,746
Вие не сте просто лепнали
неща, върху предната част.

93
00:03:53,746 --> 00:03:55,710
Трябва да се намери на
точното място, за да го сложи,

94
00:03:55,710 --> 00:03:57,820
и след това си вмъкване
става въпрос само за толкова зле,

95
00:03:57,820 --> 00:03:59,390
като вкарате в масив.

96
00:03:59,390 --> 00:04:03,130
Така свързани списъци не са
толкова голямо, за сортиране на данни.

97
00:04:03,130 --> 00:04:05,830
>> Освен това те са доста малки, размер-мъдър.

98
00:04:05,830 --> 00:04:08,496
Двойно свързан списък леко
по-голям от поединично свързани списъци,

99
00:04:08,496 --> 00:04:10,620
които са малко по-голям
от масиви, но това не е

100
00:04:10,620 --> 00:04:13,330
огромно количество губи пространство.

101
00:04:13,330 --> 00:04:18,730
Така че, ако пространството е ограничено, но
Не наистина интензивна премия,

102
00:04:18,730 --> 00:04:22,180
това може да е правилният начин да отида.

103
00:04:22,180 --> 00:04:23,330
>> Hash маси.

104
00:04:23,330 --> 00:04:25,850
Включване в хеш таблица
е сравнително лесно.

105
00:04:25,850 --> 00:04:26,980
Това е процес на два етапа.

106
00:04:26,980 --> 00:04:30,700
Първо трябва да се изпълнява нашите данни през
хеш функция, за да получите кода, хашиш,

107
00:04:30,700 --> 00:04:37,550
и тогава поставете елемент в
хеш таблица в този хеш код населено място.

108
00:04:37,550 --> 00:04:40,879
>> Заличаване, подобен на свързан списък,
е лесно, след като се намери елемента.

109
00:04:40,879 --> 00:04:43,170
Трябва да го намеря на първо място,
но тогава, когато не го изтриете,

110
00:04:43,170 --> 00:04:45,128
просто трябва да се обменят
Няколко указатели,

111
00:04:45,128 --> 00:04:47,250
ако използвате отделна верижното.

112
00:04:47,250 --> 00:04:49,942
Ако използвате сондиране,
или ако не сте

113
00:04:49,942 --> 00:04:51,650
използване на верижното изобщо
в хеш таблица,

114
00:04:51,650 --> 00:04:53,040
заличаване всъщност е много лесно.

115
00:04:53,040 --> 00:04:57,134
Всичко, което трябва да направите, е хеш на
данни, и след това отидете на това място.

116
00:04:57,134 --> 00:04:58,925
И ако приемем, че не правим
имате някакви сблъсъци,

117
00:04:58,925 --> 00:05:01,650
ще можете да изтриете много бързо.

118
00:05:01,650 --> 00:05:04,930
>> Сега, за справка е мястото, където нещата
да се получи малко по-сложно.

119
00:05:04,930 --> 00:05:06,910
Това е средно по-добре
от свързани списъци.

120
00:05:06,910 --> 00:05:09,560
Ако използвате верижното,
вие все още имате свързан списък,

121
00:05:09,560 --> 00:05:13,170
което означава, че все още имат
Търсене в ущърб свързан списък.

122
00:05:13,170 --> 00:05:18,390
Но тъй като сте като вашия свързана
списък и го разделя над 100 или 1000

123
00:05:18,390 --> 00:05:25,380
или п елементи в хеш таблица, вие сте
свързани списъци са един тото размера.

124
00:05:25,380 --> 00:05:27,650
Всички те са значително по-малък.

125
00:05:27,650 --> 00:05:32,080
Вие сте п свързани списъци, вместо
на един свързан списък на размера п.

126
00:05:32,080 --> 00:05:34,960
>> И така, това в реалния свят постоянно
фактор, който ние по принцип

127
00:05:34,960 --> 00:05:39,730
не говоря за в сложността време, то
всъщност не правят разлика тук.

128
00:05:39,730 --> 00:05:43,020
Така че все още е линейна за справка
търсите, ако използвате верижното,

129
00:05:43,020 --> 00:05:46,780
но дължината на списъка
можете да започнете да търсите чрез

130
00:05:46,780 --> 00:05:50,080
е много, много кратък в сравнение.

131
00:05:50,080 --> 00:05:52,995
Отново, ако сортиране е вашият
цел тук, хеш-таблица на

132
00:05:52,995 --> 00:05:54,370
Вероятно не е правилният начин да отида.

133
00:05:54,370 --> 00:05:56,830
Просто използвайте масив ако сортиране
е наистина важно за вас.

134
00:05:56,830 --> 00:05:58,590
>> И те могат да стартирате гама от размери.

135
00:05:58,590 --> 00:06:01,640
Трудно е да се каже дали един
хеш таблица е малка или голяма,

136
00:06:01,640 --> 00:06:04,110
защото това наистина зависи от
колко голям си хеш таблица е.

137
00:06:04,110 --> 00:06:07,340
Ако сте само ще трябва да се съхраняват
пет метални елементи в хеш таблица,

138
00:06:07,340 --> 00:06:10,620
и имате хеш таблица
с 10,000 елементи в него,

139
00:06:10,620 --> 00:06:12,614
вие вероятно губите много място.

140
00:06:12,614 --> 00:06:15,030
Контраст, че си също може да
има много компактни хеш таблици,

141
00:06:15,030 --> 00:06:18,720
но по-малкия си хеш таблицата получава,
колкото по-дълго всеки от тези свързани списъци

142
00:06:18,720 --> 00:06:19,220
получава.

143
00:06:19,220 --> 00:06:22,607
И така, там наистина няма начин да се определи
точно с размерите на хеш таблица,

144
00:06:22,607 --> 00:06:24,440
но това е може би безопасна
да се каже, че е по принцип

145
00:06:24,440 --> 00:06:27,990
щеше да бъде по-голям от една свързана
списък съхраняване на едни и същи данни,

146
00:06:27,990 --> 00:06:30,400
но по-малка от Trie.

147
00:06:30,400 --> 00:06:32,720
>> И се опитва са четвъртият
на тези структури

148
00:06:32,720 --> 00:06:34,070
че ние сме били говориш.

149
00:06:34,070 --> 00:06:36,450
Поставяне в синтактично дърво е сложна.

150
00:06:36,450 --> 00:06:38,400
Има една много динамична
заделяне на памет,

151
00:06:38,400 --> 00:06:40,780
особено в началото,
като сте се започне да се строи.

152
00:06:40,780 --> 00:06:43,700
Но това е константно време.

153
00:06:43,700 --> 00:06:47,690
Това е само човешкия елемент
ето, че го прави труден.

154
00:06:47,690 --> 00:06:53,250
Като взе да срещнете нулев указател, изчистване
пространство, отидете там, евентуално изчистване пространство

155
00:06:53,250 --> 00:06:54,490
от там отново.

156
00:06:54,490 --> 00:06:58,880
Сортът за сплашване фактор
указатели в динамично разпределение на паметта

157
00:06:58,880 --> 00:07:00,130
е препятствие, за да изчистите.

158
00:07:00,130 --> 00:07:04,550
Но след като веднъж сте го прочисти, вмъкване
всъщност идва съвсем проста,

159
00:07:04,550 --> 00:07:06,810
и то със сигурност е константно време.

160
00:07:06,810 --> 00:07:07,680
>> Заличаване е лесно.

161
00:07:07,680 --> 00:07:11,330
Всичко, което трябва да направите е да се движите надолу по
Няколко указатели и безплатно възела,

162
00:07:11,330 --> 00:07:12,420
така че това е доста добър.

163
00:07:12,420 --> 00:07:13,930
Търсене също е доста бърз.

164
00:07:13,930 --> 00:07:16,780
Тя се основава само на
Дължина на вашите данни.

165
00:07:16,780 --> 00:07:19,924
Така че, ако всички от данните ви е
пет буквени поредици,

166
00:07:19,924 --> 00:07:22,590
Например, можете да започнете съхраняване пет
символни низове в твоята синтактично дърво,

167
00:07:22,590 --> 00:07:25,439
отнема само пет стъпки към
намерите това, което търсите.

168
00:07:25,439 --> 00:07:28,480
Five е само на постоянен фактор, така че
отново, вмъкване, изтриване, и за справка

169
00:07:28,480 --> 00:07:31,670
тук всички са константно време, ефективно.

170
00:07:31,670 --> 00:07:34,880
>> Друго нещо е, че си е синтактично дърво
всъщност вид вече подредени, нали?

171
00:07:34,880 --> 00:07:36,800
По силата на това как сме
вмъкване на елементи,

172
00:07:36,800 --> 00:07:40,060
като отидете буква по буква на
ключ, или цифра по цифра на ключа,

173
00:07:40,060 --> 00:07:45,084
Обикновено, вашият Trie озовава
вид, сортирани като сте го построили.

174
00:07:45,084 --> 00:07:47,250
Тя не наистина прави
смисъл да се мисли за сортиране

175
00:07:47,250 --> 00:07:49,874
по същия начин, по който мислим за
то с масиви или свързани списъци,

176
00:07:49,874 --> 00:07:51,070
или хеш таблици.

177
00:07:51,070 --> 00:07:54,780
Но в известен смисъл, си
Trie се сортират като отидеш.

178
00:07:54,780 --> 00:07:58,630
>> Недостатъкът, разбира се, е, че
синтактично дърво бързо се превръща в огромен.

179
00:07:58,630 --> 00:08:02,970
От всяко кръстовище точка, може да се
have-- ако вашият ключ се състои от цифри,

180
00:08:02,970 --> 00:08:04,880
имате 10 други
места можете да отидете, които

181
00:08:04,880 --> 00:08:07,490
означава, че всеки възел
съдържа информация

182
00:08:07,490 --> 00:08:11,440
за данните, които искате да съхранявате
в този възел, плюс 10 указатели.

183
00:08:11,440 --> 00:08:14,430
Което, на CS50 IDE, е 80 байта.

184
00:08:14,430 --> 00:08:17,220
Така че това е най-малко 80 байта за
всеки възел, който създавате,

185
00:08:17,220 --> 00:08:19,240
И това не е дори да броим данни.

186
00:08:19,240 --> 00:08:24,950
И ако ви възли са
букви вместо цифри,

187
00:08:24,950 --> 00:08:27,825
Сега имате 26 показалки
от всяко населено място.

188
00:08:27,825 --> 00:08:32,007
И 26 пъти 8 е може би 200
байта, или нещо подобно.

189
00:08:32,007 --> 00:08:33,840
И вие имате капитал
и вие може да lowercase--

190
00:08:33,840 --> 00:08:35,381
виж къде отивам с това, нали?

191
00:08:35,381 --> 00:08:37,500
Вашите възли, може да получите наистина
голям, така и на Trie

192
00:08:37,500 --> 00:08:40,470
себе си, като цяло, може да
получите наистина голям, прекалено.

193
00:08:40,470 --> 00:08:42,630
Така че, ако пространството е висока
премия на вашата система,

194
00:08:42,630 --> 00:08:45,830
синтактично дърво може да не е правилният начин да се
отида, въпреки че други ползи

195
00:08:45,830 --> 00:08:47,780
да влезе в игра.

196
00:08:47,780 --> 00:08:48,710
Аз съм Дъг Лойд.

197
00:08:48,710 --> 00:08:50,740
Това е CS50.

198
00:08:50,740 --> 00:08:52,316