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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Tehát CS50, már lefedett
egy csomó más adatszerkezetek,

3
00:00:08,300 --> 00:00:09,180
ugye?

4
00:00:09,180 --> 00:00:11,420
Láttuk tömbök, és az ehhez kapcsolódó
listák és hash táblák,

5
00:00:11,420 --> 00:00:15,210
és próbál, halom és a sorban állás.

6
00:00:15,210 --> 00:00:17,579
Majd azt is tanulni egy kicsit
mintegy fák és halmok,

7
00:00:17,579 --> 00:00:20,120
de tényleg ezek mind csak a végén
fel, hogy variációk egy témára.

8
00:00:20,120 --> 00:00:22,840
Valóban vannak ezek a
fajta négy alapvető ötletek

9
00:00:22,840 --> 00:00:25,190
hogy minden mást is szűkülnek le.

10
00:00:25,190 --> 00:00:28,150
Tömbök, láncolt listák,
hash táblák, és próbál.

11
00:00:28,150 --> 00:00:30,720
És mint mondtam,
variációi rájuk,

12
00:00:30,720 --> 00:00:32,720
de ez elég
sokat fog összefoglalni

13
00:00:32,720 --> 00:00:38,140
mindent meg fogunk beszélni
mintegy ebben az osztályban szempontjából C.

14
00:00:38,140 --> 00:00:40,140
>> De hogyan ezek az összes intézkedés, ugye?

15
00:00:40,140 --> 00:00:44,265
Beszéltünk az érvek és ellenérvek
Az egyes különálló videók rájuk,

16
00:00:44,265 --> 00:00:46,390
de van egy csomó számok
egyre dobott körül.

17
00:00:46,390 --> 00:00:48,723
Van egy csomó általános
gondolatok egyre dobott körül.

18
00:00:48,723 --> 00:00:51,950
Próbáljuk megszilárdítása
azt csak egy helyen.

19
00:00:51,950 --> 00:00:55,507
Nézzük mérlegelni előnyeit ellen
Az ellenérvek, és úgy vélik,

20
00:00:55,507 --> 00:00:57,340
mely adatok szerkezete
Lehet, hogy a megfelelő adatokat

21
00:00:57,340 --> 00:01:01,440
struktúra az adott helyzetet,
bármilyen fajta adatok te tárolására.

22
00:01:01,440 --> 00:01:06,625
Nem feltétlenül kell mindig
Használja a szupergyors elvétel,

23
00:01:06,625 --> 00:01:10,761
és keresési egy Trie ha igazán
Nem érdekel beszúrása, törlése

24
00:01:10,761 --> 00:01:11,260
túl sok.

25
00:01:11,260 --> 00:01:13,968
Ha szüksége van csak gyorsan véletlenszerű
hozzáférést, talán egy tömb jobb.

26
00:01:13,968 --> 00:01:15,340
Úgyhogy distill ezt.

27
00:01:15,340 --> 00:01:18,530
Beszéljünk a négy
fő típusú adatok szerkezetek

28
00:01:18,530 --> 00:01:21,720
hogy beszéltünk, és
csak látni, amikor lehet, hogy jó,

29
00:01:21,720 --> 00:01:23,340
és amikor lehet, hogy nem olyan jó.

30
00:01:23,340 --> 00:01:24,610
Szóval kezdjük a tömbök.

31
00:01:24,610 --> 00:01:27,300
Szóval behelyezés, ez a fajta rossz.

32
00:01:27,300 --> 00:01:31,350
>> Insertion végén egy tömb rendben van,
ha építünk egy tömb, ahogy haladunk.

33
00:01:31,350 --> 00:01:33,570
De ha kell beszúrni
elemek középre,

34
00:01:33,570 --> 00:01:35,550
gondoljon vissza a behelyezés
rendezés, van egy csomó

35
00:01:35,550 --> 00:01:37,510
Az áttéréssel illik egy olyan elem is van.

36
00:01:37,510 --> 00:01:41,170
És így ha fogunk beilleszteni
sehol, de a végén egy tömb,

37
00:01:41,170 --> 00:01:43,590
ez talán nem olyan nagy.

38
00:01:43,590 --> 00:01:46,710
>> Hasonlóképpen, törlés, kivéve, ha mi vagyunk
törlése végétől egy tömb,

39
00:01:46,710 --> 00:01:49,810
Feltehetőleg nem olyan nagy, ha
mi nem akarjuk, hogy hagyja üresen hiányosságok,

40
00:01:49,810 --> 00:01:50,790
ami általában nem.

41
00:01:50,790 --> 00:01:54,700
Azt akarjuk, hogy távolítsa el az elemet, és
akkor egyfajta teszik otthonos újra.

42
00:01:54,700 --> 00:01:57,670
És így törlését elemek
tömb, nem is olyan nagy.

43
00:01:57,670 --> 00:01:58,820
>> Keresése, mégis, ez nagyszerű.

44
00:01:58,820 --> 00:02:00,920
Van véletlenszerű hozzáférés,
konstans időben keresést.

45
00:02:00,920 --> 00:02:03,800
Mi csak annyit hét, és megyünk
a tömb áthelyezés hét.

46
00:02:03,800 --> 00:02:05,907
Azt mondjuk 20, a go, hogy
tömb áthelyezés 20.

47
00:02:05,907 --> 00:02:07,240
Nem kell iterációkhoz szerte.

48
00:02:07,240 --> 00:02:08,630
Ez elég jó.

49
00:02:08,630 --> 00:02:11,020
>> A tömbök is viszonylag könnyen rendezni.

50
00:02:11,020 --> 00:02:14,040
Minden alkalommal beszélgettünk szelektáló
algoritmus, mint például a kiválasztás sort,

51
00:02:14,040 --> 00:02:18,820
beillesztés sort, buborékos rendezést, merge
rendezés, mi mindig tömböket kell csinálni,

52
00:02:18,820 --> 00:02:21,860
mert tömbök elég könnyű
Rendezés képest a adatstruktúrák

53
00:02:21,860 --> 00:02:22,970
láttunk eddig.

54
00:02:22,970 --> 00:02:24,320
>> Ők is viszonylag kicsi.

55
00:02:24,320 --> 00:02:25,695
Ott nem sok extra helyet.

56
00:02:25,695 --> 00:02:29,210
Te csak félre pontosan annyi
ahogy kell tartani az adatokat,

57
00:02:29,210 --> 00:02:30,320
és ez nagyjából azt.

58
00:02:30,320 --> 00:02:33,180
Tehát ők nagyon kicsi
és hatékony az említett módon.

59
00:02:33,180 --> 00:02:36,000
De egy másik hátránya azonban,
az, hogy ezek fix méretű.

60
00:02:36,000 --> 00:02:38,630
Van, hogy állapítsa meg, hogy pontosan hogyan
big azt akarjuk tömb lenni,

61
00:02:38,630 --> 00:02:39,940
és mi csak kap egy lövés is.

62
00:02:39,940 --> 00:02:41,280
Nem tudunk növekedni és csökken ez.

63
00:02:41,280 --> 00:02:44,582
>> Ha kell, hogy növekszik vagy csökken, mi
kell bejelenteni egy teljesen új tömb,

64
00:02:44,582 --> 00:02:47,750
másolja az összes elem a
első tömb a második tömb.

65
00:02:47,750 --> 00:02:51,410
És ha elszámította magát, hogy
idő, meg kell csinálni újra.

66
00:02:51,410 --> 00:02:52,760
Nem olyan nagy.

67
00:02:52,760 --> 00:02:58,750
Tehát tömbök nem ad számunkra a rugalmasságot,
hogy változó számú elemekkel.

68
00:02:58,750 --> 00:03:01,320
>> A láncolt lista,
behelyezés elég könnyű.

69
00:03:01,320 --> 00:03:03,290
Mi csak a host-ra az első.

70
00:03:03,290 --> 00:03:04,892
Törlés is nagyon egyszerű.

71
00:03:04,892 --> 00:03:06,100
Meg kell találnunk az elemeket.

72
00:03:06,100 --> 00:03:07,270
Mely magában némi keresgélés.

73
00:03:07,270 --> 00:03:10,270
>> De ha megtalálta az elem
keres, csak annyit kell tennie,

74
00:03:10,270 --> 00:03:12,830
a változás egy mutató,
talán két ha

75
00:03:12,830 --> 00:03:15,151
Csatolt list-- kétszeresen
láncolt lista, rather--

76
00:03:15,151 --> 00:03:16,650
és akkor is csak kiszabadítani a csomópontot.

77
00:03:16,650 --> 00:03:18,399
Nem kell váltani
mindent körül.

78
00:03:18,399 --> 00:03:22,090
Te csak megváltoztatni a két mutató,
úgy, hogy elég gyors.

79
00:03:22,090 --> 00:03:23,470
>> Keresési van rossz, ugye?

80
00:03:23,470 --> 00:03:26,280
Annak érdekében, hogy megtaláljuk a
eleme egy láncolt lista,

81
00:03:26,280 --> 00:03:29,154
akár magukban, vagy kétszeresen kötött,
van, hogy lineáris keresés rá.

82
00:03:29,154 --> 00:03:32,320
Meg kell kezdeni az elején és
mozgatni a végén, vagy végén kezdődik mozgásban

83
00:03:32,320 --> 00:03:33,860
az elején.

84
00:03:33,860 --> 00:03:35,474
Nincs véletlen hozzáférésű többé.

85
00:03:35,474 --> 00:03:37,265
Tehát, ha csinálunk egy
Sok keresés, talán

86
00:03:37,265 --> 00:03:39,830
A csatolt lista nem
annyira jó nekünk.

87
00:03:39,830 --> 00:03:43,750
>> Ők is nagyon
nehéz rendezni, ugye?

88
00:03:43,750 --> 00:03:45,666
Az egyetlen mód, akkor
Tényleg rendezni egy láncolt lista

89
00:03:45,666 --> 00:03:47,870
az, hogy rendezni úgy, mint a kivitelezést.

90
00:03:47,870 --> 00:03:50,497
De ha rendezni úgy, mint
kivitelezést, te már nem

91
00:03:50,497 --> 00:03:51,830
hogy gyors betoldások többé.

92
00:03:51,830 --> 00:03:53,746
Te nem csak tacking
dolgokat rá az első.

93
00:03:53,746 --> 00:03:55,710
Meg kell találni a
megfelelő helyre tedd,

94
00:03:55,710 --> 00:03:57,820
majd a beszúrás
válik majdnem olyan rossz

95
00:03:57,820 --> 00:03:59,390
mint behelyezése egy tömbbe.

96
00:03:59,390 --> 00:04:03,130
Így kapcsolódik listák nem
olyan nagy válogatás adatok.

97
00:04:03,130 --> 00:04:05,830
>> Ők is elég kicsi, méret-bölcs.

98
00:04:05,830 --> 00:04:08,496
Kétszeresen láncolt lista enyhén
nagyobb, mint külön-külön láncolt listák,

99
00:04:08,496 --> 00:04:10,620
amelyek kissé nagyobb
mint tömbök, de ez nem

100
00:04:10,620 --> 00:04:13,330
rengeteg elvesztegetett hely.

101
00:04:13,330 --> 00:04:18,730
Tehát ha a hely egy prémium, de
Nem egy igazán erős prémium,

102
00:04:18,730 --> 00:04:22,180
ez lehet a helyes út.

103
00:04:22,180 --> 00:04:23,330
>> Hash táblák.

104
00:04:23,330 --> 00:04:25,850
Beszúrás hasító táblázat
meglehetősen egyszerű.

105
00:04:25,850 --> 00:04:26,980
Ez egy kétlépcsős folyamat.

106
00:04:26,980 --> 00:04:30,700
Először is meg kell futtatni adataink segítségével
a hash függvény, hogy egy hash kódot,

107
00:04:30,700 --> 00:04:37,550
majd betesszük az elem az
hash tábla, hogy hash kódot helyét.

108
00:04:37,550 --> 00:04:40,879
>> Törlés, hasonló láncolt lista,
könnyű, ha megtaláljuk a elemet.

109
00:04:40,879 --> 00:04:43,170
Meg kell találni azt az első,
de aztán amikor törli azt,

110
00:04:43,170 --> 00:04:45,128
akkor csak meg kell cserélni
Pár mutatók,

111
00:04:45,128 --> 00:04:47,250
ha használja külön láncolás.

112
00:04:47,250 --> 00:04:49,942
Ha használja szondázás,
vagy ha nem

113
00:04:49,942 --> 00:04:51,650
segítségével láncolt egyáltalán
a hash tábla,

114
00:04:51,650 --> 00:04:53,040
törlés valójában nagyon egyszerű.

115
00:04:53,040 --> 00:04:57,134
Mindössze annyit kell tennie, hogy a hash
adatokat, és akkor megy arra a helyre.

116
00:04:57,134 --> 00:04:58,925
És feltételezve, hogy nem
bármilyen ütközések,

117
00:04:58,925 --> 00:05:01,650
Ön képes lesz arra, hogy törölje nagyon gyorsan.

118
00:05:01,650 --> 00:05:04,930
>> Most, keresési van, ahol a dolgok
egy kicsit bonyolultabb.

119
00:05:04,930 --> 00:05:06,910
Ez jobb az átlagos
mint láncolt listák.

120
00:05:06,910 --> 00:05:09,560
Ha használja láncolás,
még mindig van egy láncolt lista,

121
00:05:09,560 --> 00:05:13,170
ami azt jelenti, még a
keresés kárára egy láncolt lista.

122
00:05:13,170 --> 00:05:18,390
Hanem azért, mert ön tölti kapcsolódik
listát, és ketté ez több mint 100 vagy 1000

123
00:05:18,390 --> 00:05:25,380
vagy n eleme a hash tábla, akkor
láncolt listák mindnyájan egy n-edik méretét.

124
00:05:25,380 --> 00:05:27,650
Mind lényegesen kisebb.

125
00:05:27,650 --> 00:05:32,080
Még n láncolt listák helyett
Egy láncolt lista n méretű.

126
00:05:32,080 --> 00:05:34,960
>> És így ez a valós állandó
tényező, amit általában

127
00:05:34,960 --> 00:05:39,730
Nem beszélnek a futási ideje, hogy
valójában csinál egy különbség van.

128
00:05:39,730 --> 00:05:43,020
Tehát keresési van még lineáris
keresés használata esetén láncolás,

129
00:05:43,020 --> 00:05:46,780
de a hossza a lista
Ön keres keresztül

130
00:05:46,780 --> 00:05:50,080
Nagyon, nagyon rövid képest.

131
00:05:50,080 --> 00:05:52,995
Ismét, ha válogatás az Ön
cél itt, hash tábla

132
00:05:52,995 --> 00:05:54,370
valószínűleg nem a helyes út.

133
00:05:54,370 --> 00:05:56,830
Csak használ egy tömböt, ha válogatás
nagyon fontos neked.

134
00:05:56,830 --> 00:05:58,590
>> És akkor végig nem járják a mérete.

135
00:05:58,590 --> 00:06:01,640
Nehéz megmondani, hogy a
hash tábla kicsi vagy nagy,

136
00:06:01,640 --> 00:06:04,110
mert valójában attól függ,
milyen nagy a hash tábla.

137
00:06:04,110 --> 00:06:07,340
Ha csak lesz tárolására
öt elem a hash tábla,

138
00:06:07,340 --> 00:06:10,620
és van egy hash tábla
10.000 elemek is,

139
00:06:10,620 --> 00:06:12,614
akkor valószínűleg pazarlás sok helyet.

140
00:06:12,614 --> 00:06:15,030
Kontraszt, hogy akkor is
nagyon kompakt hash táblák,

141
00:06:15,030 --> 00:06:18,720
de a kisebb a hash tábla lesz,
Hosszabb minden egyes ilyen láncolt listák

142
00:06:18,720 --> 00:06:19,220
jelentkeznek.

143
00:06:19,220 --> 00:06:22,607
És így már tényleg nem lehet meghatározni
Pontosan akkora, mint egy hash tábla,

144
00:06:22,607 --> 00:06:24,440
de ez valószínűleg biztonságos
mondani, hogy az általánosan

145
00:06:24,440 --> 00:06:27,990
nagyobb lesz, mint a kapcsolt
listán tárolja ugyanazokat az adatokat,

146
00:06:27,990 --> 00:06:30,400
de kisebb, mint egy Trie.

147
00:06:30,400 --> 00:06:32,720
>> És megpróbálja a negyedik
E struktúrák

148
00:06:32,720 --> 00:06:34,070
hogy mi már beszélünk.

149
00:06:34,070 --> 00:06:36,450
Behe- egy Trie összetett.

150
00:06:36,450 --> 00:06:38,400
Van egy csomó dinamikus
memóriafoglalási,

151
00:06:38,400 --> 00:06:40,780
főleg az elején,
mint kezded építeni.

152
00:06:40,780 --> 00:06:43,700
De ez az állandó idő.

153
00:06:43,700 --> 00:06:47,690
Ez csak az emberi tényező
itt teszi, hogy trükkös.

154
00:06:47,690 --> 00:06:53,250
Miután a találkozás null pointer, malloc
helyet, ott, esetleg malloc tér

155
00:06:53,250 --> 00:06:54,490
onnan újra.

156
00:06:54,490 --> 00:06:58,880
Az a fajta megfélemlítés tényezője
mutatókat memória dinamikus

157
00:06:58,880 --> 00:07:00,130
az akadályt, hogy egyértelmű.

158
00:07:00,130 --> 00:07:04,550
De ha egyszer már tisztázta, beillesztés
valóban jön nagyon egyszerű,

159
00:07:04,550 --> 00:07:06,810
és ez minden bizonnyal nem változik az időben.

160
00:07:06,810 --> 00:07:07,680
>> Törlés könnyű.

161
00:07:07,680 --> 00:07:11,330
Mindössze annyit kell tennie, hogy navigálni le
Pár mutatók és ingyenes a csomópont,

162
00:07:11,330 --> 00:07:12,420
szóval ez elég jó.

163
00:07:12,420 --> 00:07:13,930
Keresés is elég gyors.

164
00:07:13,930 --> 00:07:16,780
Ez csak alapul a
hossza az adatokat.

165
00:07:16,780 --> 00:07:19,924
Tehát, ha az összes adat van
Öt karakterláncok,

166
00:07:19,924 --> 00:07:22,590
Például te tárolására öt
karaktersorainak a Trie,

167
00:07:22,590 --> 00:07:25,439
csak úgy öt lépésben
megtalálja, amit keres.

168
00:07:25,439 --> 00:07:28,480
Öt mindössze egy állandó tényezőt, így
ismét, inszerciójával, deléciójával, és keresési

169
00:07:28,480 --> 00:07:31,670
Itt megtalálja az összes állandó időben, hatékonyan.

170
00:07:31,670 --> 00:07:34,880
>> A másik dolog az, hogy a Trie van
valójában milyen már válogatni, ugye?

171
00:07:34,880 --> 00:07:36,800
Azáltal, hogy hogyan vagyunk
behelyezése elemek,

172
00:07:36,800 --> 00:07:40,060
megy levélre a
gombot, vagy számjegyenként a legfontosabb,

173
00:07:40,060 --> 00:07:45,084
Jellemzően a Trie végül is
fajta válogatni, mint építeni.

174
00:07:45,084 --> 00:07:47,250
Ez nem igazán tesz
értelme gondolkodni válogatás

175
00:07:47,250 --> 00:07:49,874
ugyanúgy gondolkodunk
azt tömbök, vagy kapcsolt listák,

176
00:07:49,874 --> 00:07:51,070
vagy hash táblák.

177
00:07:51,070 --> 00:07:54,780
De bizonyos értelemben, a
Trie van rendezve, ahogy megy.

178
00:07:54,780 --> 00:07:58,630
>> A hátránya, természetesen az, hogy
Egy Trie gyorsan válik hatalmas.

179
00:07:58,630 --> 00:08:02,970
Minden csatlakozási pontja, lehet,
have-- ha a kulcs áll számjegy,

180
00:08:02,970 --> 00:08:04,880
Ön 10 egyéb
helyen érhetők el, amelyek

181
00:08:04,880 --> 00:08:07,490
azt jelenti, hogy minden csomópont
információkat tartalmaz

182
00:08:07,490 --> 00:08:11,440
a kívánt adatokat tárolni
abban csomópontot, plusz 10 mutató.

183
00:08:11,440 --> 00:08:14,430
Melyik, a CS50 IDE, 80 bájt.

184
00:08:14,430 --> 00:08:17,220
Tehát legalább 80 byte
minden csomópont hogy hozzon létre,

185
00:08:17,220 --> 00:08:19,240
és ez nem is számít adatokat.

186
00:08:19,240 --> 00:08:24,950
És ha a csomópontok
betűk helyett számok,

187
00:08:24,950 --> 00:08:27,825
most már 26 mutató
minden helyen.

188
00:08:27,825 --> 00:08:32,007
És 26-szer 8 valószínűleg 200
bájt, vagy valami ilyesmi.

189
00:08:32,007 --> 00:08:33,840
És van fővárosban
és lowercase-- lehet

190
00:08:33,840 --> 00:08:35,381
lásd, hova megyek ezzel, nem igaz?

191
00:08:35,381 --> 00:08:37,500
Az Ön csomópontok tud igazán
nagy, és így a Trie

192
00:08:37,500 --> 00:08:40,470
Maga összességében is
igazán nagy, túl.

193
00:08:40,470 --> 00:08:42,630
Tehát, ha kevés a hely magas
prémium a rendszer,

194
00:08:42,630 --> 00:08:45,830
Egy Trie lehet, hogy nem a helyes út
megy, annak ellenére, hogy más előnyök

195
00:08:45,830 --> 00:08:47,780
jöhet számításba.

196
00:08:47,780 --> 00:08:48,710
Én Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Ez CS50.

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