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

2
00:00:05,259 --> 00:00:08,300
DOUG Lloyd: Niin CS50, olemme katettu
paljon erilaisia ​​tietorakenteita,

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

4
00:00:09,180 --> 00:00:11,420
Olemme nähneet paneelit, ja liittyy
luettelot, ja hash taulukot,

5
00:00:11,420 --> 00:00:15,210
ja yrittää, pinot ja jonot.

6
00:00:15,210 --> 00:00:17,579
Otamme myös oppia hieman
puista ja kasoista,

7
00:00:17,579 --> 00:00:20,120
mutta oikeastaan ​​nämä kaikki vain lopettaa
lopulta muunnelmia teemasta.

8
00:00:20,120 --> 00:00:22,840
Ei todellakaan nämä
eräänlainen neljä perusajatuksia

9
00:00:22,840 --> 00:00:25,190
että kaikki muu voi pohjimmiltaan.

10
00:00:25,190 --> 00:00:28,150
Taulukot, jotka liittyvät luettelot,
hash taulukoita, ja yrittää.

11
00:00:28,150 --> 00:00:30,720
Ja kuten sanoin, siellä
ovat muunnelmia niitä,

12
00:00:30,720 --> 00:00:32,720
mutta tämä on melko
paljon menossa yhteenveto

13
00:00:32,720 --> 00:00:38,140
kaikki me aiomme puhua
noin tässä luokassa kannalta C.

14
00:00:38,140 --> 00:00:40,140
>> Mutta miten nämä kaikki toimenpide, eikö?

15
00:00:40,140 --> 00:00:44,265
Olemme puhuneet eduista ja haitoista
Kunkin erillisissä videoita niitä,

16
00:00:44,265 --> 00:00:46,390
mutta siellä on paljon numeroita
saada heittää noin.

17
00:00:46,390 --> 00:00:48,723
Siellä on paljon yleistä
ajatukset saada heittää noin.

18
00:00:48,723 --> 00:00:51,950
Yritetään lujittaa
se vain yhteen paikkaan.

19
00:00:51,950 --> 00:00:55,507
Katsotaanpa punnita hyviä vastaan
haittoja, ja harkita

20
00:00:55,507 --> 00:00:57,340
joka datarakenne
voisi olla oikea tiedot

21
00:00:57,340 --> 00:01:01,440
rakenne teidän tilanteeseen,
Riippumatta siitä, millaista tietoa olet tallentamiseen.

22
00:01:01,440 --> 00:01:06,625
Sinun ei välttämättä aina tarvitse
Käytä huippunopea lisäys, poisto,

23
00:01:06,625 --> 00:01:10,761
ja lookup trie jos todella
eivät välitä lisäämällä ja poistamalla

24
00:01:10,761 --> 00:01:11,260
liian paljon.

25
00:01:11,260 --> 00:01:13,968
Jos tarvitset vain nopeasti satunnainen
yhteys, ehkä array on parempi.

26
00:01:13,968 --> 00:01:15,340
Joten distill että.

27
00:01:15,340 --> 00:01:18,530
Puhutaanpa kunkin neljän
suurta kokonaisuutta tietorakenteiden

28
00:01:18,530 --> 00:01:21,720
että olemme puhuneet, ja
vain nähdä, kun he voisi olla hyvä,

29
00:01:21,720 --> 00:01:23,340
ja kun he ehkä ole niin hyvä.

30
00:01:23,340 --> 00:01:24,610
Joten aloittaa paneelit.

31
00:01:24,610 --> 00:01:27,300
Niin lisäys, että on tavallaan huono.

32
00:01:27,300 --> 00:01:31,350
>> Insertio lopussa array on OK,
jos me rakennamme erilaisia ​​kuin me mennä.

33
00:01:31,350 --> 00:01:33,570
Mutta jos meidän lisätä
elementtejä keskelle,

34
00:01:33,570 --> 00:01:35,550
muistelen lisäys
lajitella, siellä on paljon

35
00:01:35,550 --> 00:01:37,510
vaihtuvien sopivaksi elementti siellä.

36
00:01:37,510 --> 00:01:41,170
Joten jos aiomme lisätä
missä tahansa mutta lopussa array,

37
00:01:41,170 --> 00:01:43,590
se luultavasti ei ole niin suuri.

38
00:01:43,590 --> 00:01:46,710
>> Samoin poistetaan, ellei olemme
poistamalla lopusta array,

39
00:01:46,710 --> 00:01:49,810
ei luultavasti myös ei ole niin suuri, jos
emme halua lähteä tyhjä aukkoja,

40
00:01:49,810 --> 00:01:50,790
joka yleensä emme.

41
00:01:50,790 --> 00:01:54,700
Haluamme poistaa elementin, ja
sitten tavallaan tekevät siitä kireällä uudelleen.

42
00:01:54,700 --> 00:01:57,670
Ja niin poistamalla elementtejä
array, myös ei niin suuri.

43
00:01:57,670 --> 00:01:58,820
>> Lookup on kuitenkin suuri.

44
00:01:58,820 --> 00:02:00,920
Meillä on random access,
vakioaikaisia ​​haku.

45
00:02:00,920 --> 00:02:03,800
Me vain sanoa seitsemän, ja menemme
array siirtäminen seitsemän.

46
00:02:03,800 --> 00:02:05,907
Sanomme 20, kanssa mennä
array siirtäminen 20.

47
00:02:05,907 --> 00:02:07,240
Meillä ei tarvitse kerrata poikki.

48
00:02:07,240 --> 00:02:08,630
Se on aika hyvä.

49
00:02:08,630 --> 00:02:11,020
>> Taulukot ovat myös suhteellisen helppo lajitella.

50
00:02:11,020 --> 00:02:14,040
Joka kerta puhuimme lajittelu
algoritmi, kuten valinta lajitella,

51
00:02:14,040 --> 00:02:18,820
lisäyslajittelun, kuplalajittelu, yhdistää
lajitella, me aina käytetty taulukot tehdä sitä,

52
00:02:18,820 --> 00:02:21,860
koska taulukot ovat melko helppo
lajitella, suhteessa tietorakenteiden

53
00:02:21,860 --> 00:02:22,970
olemme nähneet tähän mennessä.

54
00:02:22,970 --> 00:02:24,320
>> Ne ovat myös suhteellisen pieni.

55
00:02:24,320 --> 00:02:25,695
Siellä ei ole paljon ylimääräistä tilaa.

56
00:02:25,695 --> 00:02:29,210
Sinä vain varattu täsmälleen yhtä paljon
niin sinun täytyy pitää tietosi,

57
00:02:29,210 --> 00:02:30,320
ja se on aika paljon se.

58
00:02:30,320 --> 00:02:33,180
Joten ne ovat melko pieniä
ja tehokas näin.

59
00:02:33,180 --> 00:02:36,000
Mutta toinen haittapuoli, vaikka,
on, että ne ovat kiinteitä koko.

60
00:02:36,000 --> 00:02:38,630
Meidän on julistaa kuinka
iso haluamme array olla,

61
00:02:38,630 --> 00:02:39,940
ja me vain saada yksi laukaus sitä.

62
00:02:39,940 --> 00:02:41,280
Emme voi kasvaa ja kutista se.

63
00:02:41,280 --> 00:02:44,582
>> Jos meidän täytyy kasvattaa tai pienentää sitä, me
tarvitse ilmoittaa kokonaan uusi joukko,

64
00:02:44,582 --> 00:02:47,750
kopioida kaikki elementit
ensimmäinen array toiseen array.

65
00:02:47,750 --> 00:02:51,410
Ja jos me virheellisesti, että
aika, meidän täytyy tehdä se uudelleen.

66
00:02:51,410 --> 00:02:52,760
Ole niin suuri.

67
00:02:52,760 --> 00:02:58,750
Joten paneelit eivät anna meille joustavuutta
on vaihteleva määrä elementtejä.

68
00:02:58,750 --> 00:03:01,320
>> Kanssa linkitetty lista,
Lisäys on melko helppoa.

69
00:03:01,320 --> 00:03:03,290
Me vain tack päälle edessä.

70
00:03:03,290 --> 00:03:04,892
Poisto on myös melko helppoa.

71
00:03:04,892 --> 00:03:06,100
Meidän täytyy löytää elementtejä.

72
00:03:06,100 --> 00:03:07,270
Että mukana vähän tutkimustyötä.

73
00:03:07,270 --> 00:03:10,270
>> Mutta kun olet löytänyt elementti
etsit, sinun ei tarvitse tehdä

74
00:03:10,270 --> 00:03:12,830
on muuttaa osoitin,
mahdollisesti kaksi jos sinulla on

75
00:03:12,830 --> 00:03:15,151
linkitetty list-- kaksinkertaisesti
linkitetty lista, rather--

76
00:03:15,151 --> 00:03:16,650
ja sitten voit vain vapauttaa solmu.

77
00:03:16,650 --> 00:03:18,399
Sinun ei tarvitse siirtää
kaikki ympärillä.

78
00:03:18,399 --> 00:03:22,090
Sinä vain vaihtaa kaksi osoitinta,
niin se on melko nopeasti.

79
00:03:22,090 --> 00:03:23,470
>> Lookup on huono, vaikka, eikö?

80
00:03:23,470 --> 00:03:26,280
Jotta voimme löytää
elementti linkitetty lista,

81
00:03:26,280 --> 00:03:29,154
onko yksittäin tai kaksinkertaisesti sidottu,
meidän on lineaarinen etsiä sitä.

82
00:03:29,154 --> 00:03:32,320
Meidän on aloitettava alusta ja
Siirrä loppuun, tai aloittaa lopussa liikkeellä

83
00:03:32,320 --> 00:03:33,860
alkuun.

84
00:03:33,860 --> 00:03:35,474
Meillä ei ole random access enää.

85
00:03:35,474 --> 00:03:37,265
Joten jos teemme
Kovan etsimisen, ehkä

86
00:03:37,265 --> 00:03:39,830
linkitetty lista ei ole
aivan niin hyvä meille.

87
00:03:39,830 --> 00:03:43,750
>> Ne ovat myös todella
vaikea lajitella, eikö?

88
00:03:43,750 --> 00:03:45,666
Vain siten voit
todella lajitella linkitetty lista

89
00:03:45,666 --> 00:03:47,870
on lajitella se, kun rakentaa sitä.

90
00:03:47,870 --> 00:03:50,497
Mutta jos lajitella kun
rakentaa se, et enää

91
00:03:50,497 --> 00:03:51,830
joten nopea insertioita enää.

92
00:03:51,830 --> 00:03:53,746
Et vain tacking
asioita päälle edessä.

93
00:03:53,746 --> 00:03:55,710
Sinun täytyy löytää
oikea paikka laittaa se,

94
00:03:55,710 --> 00:03:57,820
ja sitten lisäys
tulee lähes yhtä huono

95
00:03:57,820 --> 00:03:59,390
kuten lisäämällä taulukkoon.

96
00:03:59,390 --> 00:04:03,130
Joten liity luettelot eivät ole
niin suuri tietojen lajittelussa.

97
00:04:03,130 --> 00:04:05,830
>> Ne ovat myös melko pieni, koko-viisasta.

98
00:04:05,830 --> 00:04:08,496
Kaksin verroin linkitetty lista hieman
suurempi kuin yksittäin liittyvät luettelot,

99
00:04:08,496 --> 00:04:10,620
jotka ovat hieman suurempia
kuin paneelit, mutta se ei ole

100
00:04:10,620 --> 00:04:13,330
valtavasti hukkaan tilaa.

101
00:04:13,330 --> 00:04:18,730
Joten jos tilaa on niukasti, mutta
ei todella voimakas palkkio,

102
00:04:18,730 --> 00:04:22,180
tämä voisi olla oikea tapa edetä.

103
00:04:22,180 --> 00:04:23,330
>> Hash taulukoita.

104
00:04:23,330 --> 00:04:25,850
Liittämistä osaksi hajautustaulun
on melko yksinkertainen.

105
00:04:25,850 --> 00:04:26,980
Se on kaksivaiheinen prosessi.

106
00:04:26,980 --> 00:04:30,700
Ensin täytyy ajaa meidän dataa
hajautusfunktio saada hash,

107
00:04:30,700 --> 00:04:37,550
ja sitten me aseta elementin
hash pöytä että hash koodi sijainti.

108
00:04:37,550 --> 00:04:40,879
>> Poisto, samanlainen linkitetty lista,
on helppoa kun löydät elementti.

109
00:04:40,879 --> 00:04:43,170
Sinun täytyy löytää se ensin,
mutta sitten kun se poistetaan,

110
00:04:43,170 --> 00:04:45,128
sinun tarvitsee vain vaihtaa
pari viitteitä,

111
00:04:45,128 --> 00:04:47,250
jos käytät erillistä ketjutusta.

112
00:04:47,250 --> 00:04:49,942
Jos käytät hyvää,
tai jos et ole

113
00:04:49,942 --> 00:04:51,650
käyttäen ketjuttamalla ollenkaan
teidän tiiviste,

114
00:04:51,650 --> 00:04:53,040
poisto on todella helppoa.

115
00:04:53,040 --> 00:04:57,134
Kaikki sinun tarvitsee vain hash
data, ja sitten mennä kyseiseen sijaintiin.

116
00:04:57,134 --> 00:04:58,925
Ja olettaen et
mitään törmäyksiä,

117
00:04:58,925 --> 00:05:01,650
voit poistaa hyvin nopeasti.

118
00:05:01,650 --> 00:05:04,930
>> Nyt haku on, jos asiat
saada hieman monimutkaisempi.

119
00:05:04,930 --> 00:05:06,910
Se on keskimäärin parempi
kuin liittyvät luettelot.

120
00:05:06,910 --> 00:05:09,560
Jos käytät ketjuttamalla,
sinulla on vielä linkitetty lista,

121
00:05:09,560 --> 00:05:13,170
mikä tarkoittaa sinulla on vielä
haku vahinkoon linkitetty lista.

122
00:05:13,170 --> 00:05:18,390
Mutta koska olet ottaen teidän sidoksissa
lista ja jakamalla se yli 100 tai 1000

123
00:05:18,390 --> 00:05:25,380
tai n elementtejä teidän tiiviste, olet
liittyvät luettelot ovat kaikki yhtä nnen kokoa.

124
00:05:25,380 --> 00:05:27,650
He ovat kaikki olennaisesti pienempi.

125
00:05:27,650 --> 00:05:32,080
Olet n linkitettyjen listojen sijasta
yhden linkitetyn listan koko on n.

126
00:05:32,080 --> 00:05:34,960
>> Ja niin tämä reaalimaailman vakio
tekijä, joka me yleensä

127
00:05:34,960 --> 00:05:39,730
älä puhu ajoissa monimutkaisuus, se
ei todella tehdä ero tässä.

128
00:05:39,730 --> 00:05:43,020
Joten haku on edelleen lineaarinen
etsi jos käytät ketjuttamalla,

129
00:05:43,020 --> 00:05:46,780
mutta pituus luettelon
etsit kautta

130
00:05:46,780 --> 00:05:50,080
on hyvin, hyvin lyhyt verrattuna.

131
00:05:50,080 --> 00:05:52,995
Jälleen, jos lajittelu on sinun
Tavoitteena tässä, tiiviste: n

132
00:05:52,995 --> 00:05:54,370
luultavasti ole oikea tapa edetä.

133
00:05:54,370 --> 00:05:56,830
Vain käyttää array jos lajittelu
on todella tärkeää sinulle.

134
00:05:56,830 --> 00:05:58,590
>> Ja ne voivat juosta kirjo koko.

135
00:05:58,590 --> 00:06:01,640
On vaikea sanoa, onko
tiiviste on pieni tai iso,

136
00:06:01,640 --> 00:06:04,110
koska se todella riippuu
kuinka suuri tiiviste on.

137
00:06:04,110 --> 00:06:07,340
Jos olet vain olemaan tallentamiseen
viisi elementtiä teidän tiiviste,

138
00:06:07,340 --> 00:06:10,620
ja sinulla on tiiviste
10000 elementtejä se,

139
00:06:10,620 --> 00:06:12,614
olet todennäköisesti tuhlaa paljon tilaa.

140
00:06:12,614 --> 00:06:15,030
Kontrasti on voit myös
on erittäin kompakti hash taulukoita,

141
00:06:15,030 --> 00:06:18,720
mutta pienempi teidän tiiviste saa,
kauemmin jokainen näistä liittyvät luettelot

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

143
00:06:19,220 --> 00:06:22,607
Ja joten ei todellakaan ole tapa määritellä
täsmälleen koko hash-taulukon,

144
00:06:22,607 --> 00:06:24,440
mutta se on todennäköisesti turvallista
sanoa se on yleensä

145
00:06:24,440 --> 00:06:27,990
tulee olla suurempi kuin linkitetty
lista tallennettu samat tiedot,,

146
00:06:27,990 --> 00:06:30,400
mutta pienempi kuin trie.

147
00:06:30,400 --> 00:06:32,720
>> Ja yrittää ovat neljäs
Näiden rakenteiden

148
00:06:32,720 --> 00:06:34,070
että olemme puhuneet.

149
00:06:34,070 --> 00:06:36,450
Insertoimalla trie on monimutkainen.

150
00:06:36,450 --> 00:06:38,400
Siellä on paljon dynaamisia
muistin jakamista,

151
00:06:38,400 --> 00:06:40,780
varsinkin alussa,
kun olet alkanut rakentaa.

152
00:06:40,780 --> 00:06:43,700
Mutta se on vakiona aika.

153
00:06:43,700 --> 00:06:47,690
Se on vain inhimillinen tekijä
täällä, joka tekee siitä hankala.

154
00:06:47,690 --> 00:06:53,250
Ottavat kohdata nollaosoittimen, malloc
tila, mennä sinne, mahdollisesti malloc tilaa

155
00:06:53,250 --> 00:06:54,490
sieltä taas.

156
00:06:54,490 --> 00:06:58,880
Tavallaan pelottelu tekijä
osoittimet dynaamisen muistin jakamista

157
00:06:58,880 --> 00:07:00,130
on este poistaa.

158
00:07:00,130 --> 00:07:04,550
Mutta kun olet tyhjentänyt sen, lisäys
tulee itse asiassa melko yksinkertainen,

159
00:07:04,550 --> 00:07:06,810
ja se varmasti on vakio ajan.

160
00:07:06,810 --> 00:07:07,680
>> Poisto on helppoa.

161
00:07:07,680 --> 00:07:11,330
Kaikki mitä sinun tarvitsee tehdä on navigoida alas
pari viitteitä ja vapaa solmu,

162
00:07:11,330 --> 00:07:12,420
niin se on aika hyvä.

163
00:07:12,420 --> 00:07:13,930
Haku on myös melko nopeasti.

164
00:07:13,930 --> 00:07:16,780
Se on vain perustuu
pituus tietosi.

165
00:07:16,780 --> 00:07:19,924
Joten jos kaikki tiedot on
viisi merkkijonojen,

166
00:07:19,924 --> 00:07:22,590
esimerkiksi olet tallennuskapasiteetti on viisi
merkkijonoja teidän trien,

167
00:07:22,590 --> 00:07:25,439
se kestää vain viisi askelta
löytää mitä etsit.

168
00:07:25,439 --> 00:07:28,480
Viisi on vain vakio tekijä, joten
jälleen, insertio, deleetio, ja haku

169
00:07:28,480 --> 00:07:31,670
Tässä ovat kaikki vakio aikaa, tehokkaasti.

170
00:07:31,670 --> 00:07:34,880
>> Toinen asia on, että trien on
oikeastaan ​​eräänlainen jo järjestetty, eikö?

171
00:07:34,880 --> 00:07:36,800
Nojalla, miten olemme
lisäämällä elementtejä,

172
00:07:36,800 --> 00:07:40,060
menemällä kirjeellä kirjeellä
näppäintä tai numero kerrallaan avaimen,

173
00:07:40,060 --> 00:07:45,084
tyypillisesti, sinun trie päätyy
Tällainen lajitella rakentaa sitä.

174
00:07:45,084 --> 00:07:47,250
Se ei oikeastaan ​​tekee
järkevää ajatella lajittelu

175
00:07:47,250 --> 00:07:49,874
samalla tavoin ajattelemme
sen paneelit, tai linkitettyjen listojen,

176
00:07:49,874 --> 00:07:51,070
tai hash taulukoita.

177
00:07:51,070 --> 00:07:54,780
Mutta jossain mielessä, teidän
trie lajitellaan kuten mennä.

178
00:07:54,780 --> 00:07:58,630
>> Huonona puolena on tietenkin se, että
trie tulee nopeasti valtava.

179
00:07:58,630 --> 00:08:02,970
Jokaisesta liitoskohta, saatat
have-- jos avain koostuu numeroa,

180
00:08:02,970 --> 00:08:04,880
sinulla on 10 muuta
paikkoja voit mennä, joka

181
00:08:04,880 --> 00:08:07,490
tarkoittaa, että jokainen solmu
sisältää tietoa

182
00:08:07,490 --> 00:08:11,440
noin tiedot haluat tallentaa
klo että solmu, lisättynä 10 osoittimia.

183
00:08:11,440 --> 00:08:14,430
, Jotka olivat CS50 IDE, on 80 tavua.

184
00:08:14,430 --> 00:08:17,220
Joten se on vähintään 80 tavua
jokainen solmu että luot,

185
00:08:17,220 --> 00:08:19,240
ja että ei edes lasketa tietoja.

186
00:08:19,240 --> 00:08:24,950
Ja jos solmut ovat
kirjeet sijasta numeroa,

187
00:08:24,950 --> 00:08:27,825
nyt sinulla on 26 osoittimet
alkaen kaikissa paikoissa.

188
00:08:27,825 --> 00:08:32,007
Ja 26 kertaa 8 on todennäköisesti 200
tavua, tai jotain sellaista.

189
00:08:32,007 --> 00:08:33,840
Ja sinulla on pääomaa
ja lowercase-- voit

190
00:08:33,840 --> 00:08:35,381
katso minne olen menossa tämän, eikö?

191
00:08:35,381 --> 00:08:37,500
Solmut voi saada todella
iso, ja niin trie

192
00:08:37,500 --> 00:08:40,470
itse, yleinen, voi
saada todella suuri, liian.

193
00:08:40,470 --> 00:08:42,630
Joten jos tilaa on korkea
Premium järjestelmään,

194
00:08:42,630 --> 00:08:45,830
trie ehkä ole oikea tapa
mennä, vaikka sen muut edut

195
00:08:45,830 --> 00:08:47,780
kuvaan.

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

197
00:08:48,710 --> 00:08:50,740
Tämä on CS50.

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