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

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: Deci, în CS50, am acoperit
o mulțime de diferite structuri de date,

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

4
00:00:09,180 --> 00:00:11,420
Am văzut tablouri, și legat
liste și tabele de dispersie,

5
00:00:11,420 --> 00:00:15,210
și încearcă, stive și cozi.

6
00:00:15,210 --> 00:00:17,579
Vom afla, de asemenea un pic
despre copaci și grămezi,

7
00:00:17,579 --> 00:00:20,120
dar de fapt toate aceste doar termina
a fi variații pe o temă.

8
00:00:20,120 --> 00:00:22,840
Există într-adevăr sunt acestea
un fel de patru idei de bază

9
00:00:22,840 --> 00:00:25,190
că totul se poate fierbe în jos pentru a.

10
00:00:25,190 --> 00:00:28,150
Tablouri, liste legate,
tabele de dispersie, și încearcă.

11
00:00:28,150 --> 00:00:30,720
Și cum am spus, nu
variații pe ele,

12
00:00:30,720 --> 00:00:32,720
dar acest lucru este destul de
mult va rezuma

13
00:00:32,720 --> 00:00:38,140
tot ceea ce vom vorbi
despre în această clasă în ceea ce privește C.

14
00:00:38,140 --> 00:00:40,140
>> Dar cum toate aceste măsuri, nu?

15
00:00:40,140 --> 00:00:44,265
Am vorbit despre argumente pro și contra
de fiecare în clipuri video separate pe ei,

16
00:00:44,265 --> 00:00:46,390
dar există o mulțime de numere
obtinerea aruncat în jurul.

17
00:00:46,390 --> 00:00:48,723
Există o mulțime de generală
gânduri obtinerea aruncat în jurul.

18
00:00:48,723 --> 00:00:51,950
Să încercăm și consolida
l în doar un singur loc.

19
00:00:51,950 --> 00:00:55,507
Să cântărească avantajele împotriva
contra, și ia în considerare

20
00:00:55,507 --> 00:00:57,340
care structură de date
ar putea fi date drept

21
00:00:57,340 --> 00:01:01,440
structura pentru situatia dumneavoastra particulara,
orice fel de date ce stocarea.

22
00:01:01,440 --> 00:01:06,625
Tu nu neapărat nevoie întotdeauna să
utilizați super rapid de inserare, ștergere,

23
00:01:06,625 --> 00:01:10,761
și căutare a unui trie dacă într-adevăr
Nu-mi pasă inserarea și ștergerea

24
00:01:10,761 --> 00:01:11,260
prea mult.

25
00:01:11,260 --> 00:01:13,968
Dacă aveți nevoie doar de repede aleatoare
acces, poate un tablou este mai bine.

26
00:01:13,968 --> 00:01:15,340
Deci, haideți să distila asta.

27
00:01:15,340 --> 00:01:18,530
Hai sa vorbim despre fiecare dintre cele patru
tipuri majore de structuri de date

28
00:01:18,530 --> 00:01:21,720
pe care le-am vorbit despre, și
doar vedea cand acestea ar putea fi bun,

29
00:01:21,720 --> 00:01:23,340
și atunci când acestea s-ar putea să nu fie atât de bun.

30
00:01:23,340 --> 00:01:24,610
Așa că haideți să începem cu tablouri.

31
00:01:24,610 --> 00:01:27,300
Deci inserție, asta e un fel de rău.

32
00:01:27,300 --> 00:01:31,350
>> Inserție, la sfârșitul unei matrice este OK,
dacă ne construim un tablou ca mergem.

33
00:01:31,350 --> 00:01:33,570
Dar dacă avem nevoie pentru a introduce
elemente în centru,

34
00:01:33,570 --> 00:01:35,550
cred că înapoi la inserție
sortare, există o mulțime

35
00:01:35,550 --> 00:01:37,510
de trecerea pentru a se potrivi un element acolo.

36
00:01:37,510 --> 00:01:41,170
Și așa, dacă vom introduce
oriunde, dar la sfârșitul anului o matrice,

37
00:01:41,170 --> 00:01:43,590
care, probabil, nu e atât de mare.

38
00:01:43,590 --> 00:01:46,710
>> În mod similar, ștergere, cu excepția cazului în suntem
ștergerea din sfârșitul unei matrice,

39
00:01:46,710 --> 00:01:49,810
este, probabil, de asemenea, nu atât de mare dacă
nu vrem să plece lacune goale,

40
00:01:49,810 --> 00:01:50,790
care de obicei nu avem.

41
00:01:50,790 --> 00:01:54,700
Vrem să eliminați un element, și
apoi un fel de a face confortabil din nou.

42
00:01:54,700 --> 00:01:57,670
Și astfel ștergerea elemente din
o matrice, de asemenea, nu atât de mare.

43
00:01:57,670 --> 00:01:58,820
>> Căutare, deși, este mare.

44
00:01:58,820 --> 00:02:00,920
Noi avem acces aleator,
căutare constantă de timp.

45
00:02:00,920 --> 00:02:03,800
Noi spunem doar șapte, și vom merge
pentru matrice relocare șapte.

46
00:02:03,800 --> 00:02:05,907
Noi spunem 20, cu Du-te la
matrice relocare 20.

47
00:02:05,907 --> 00:02:07,240
Noi nu trebuie să itera peste.

48
00:02:07,240 --> 00:02:08,630
Asta e destul de bun.

49
00:02:08,630 --> 00:02:11,020
>> Arrays sunt, de asemenea, relativ ușor pentru a sorta.

50
00:02:11,020 --> 00:02:14,040
De fiecare dată când am vorbit despre o sortare
algoritm, cum ar fi de selecție fel,

51
00:02:14,040 --> 00:02:18,820
fel de introducere, cu bule de sortare, îmbinare
fel, am întotdeauna folosit matrice a face acest lucru,

52
00:02:18,820 --> 00:02:21,860
deoarece matrice sunt destul de ușor de
sortare, în raport cu structurile de date

53
00:02:21,860 --> 00:02:22,970
am văzut până acum.

54
00:02:22,970 --> 00:02:24,320
>> Sunt, de asemenea, relativ mică.

55
00:02:24,320 --> 00:02:25,695
Nu este o mulțime de spațiu suplimentar.

56
00:02:25,695 --> 00:02:29,210
Trebuie doar anularea exact la fel de mult
ca ai nevoie de a organiza datele tale,

57
00:02:29,210 --> 00:02:30,320
și asta e destul de mult.

58
00:02:30,320 --> 00:02:33,180
Astfel încât acestea sunt destul de mici
și eficient în acest mod.

59
00:02:33,180 --> 00:02:36,000
Dar un alt dezavantaj, deși,
este că acestea sunt stabilite în mărime.

60
00:02:36,000 --> 00:02:38,630
Trebuie să declare exact cum
mare dorim oferta noastră să fie,

61
00:02:38,630 --> 00:02:39,940
si ajungem o singura lovitura la ea.

62
00:02:39,940 --> 00:02:41,280
Nu putem crește și reduce o.

63
00:02:41,280 --> 00:02:44,582
>> Dacă avem nevoie să crească sau micsora aceasta, ne-am
Trebuie să declare o serie complet nouă,

64
00:02:44,582 --> 00:02:47,750
copia toate elementele
prima matrice în a doua matrice.

65
00:02:47,750 --> 00:02:51,410
Și dacă ne-am calculat greșit că
timp, trebuie să o facem din nou.

66
00:02:51,410 --> 00:02:52,760
Nu atât de mare.

67
00:02:52,760 --> 00:02:58,750
Deci, tablouri, nu ne dau flexibilitatea
de a avea un număr variabil de elemente.

68
00:02:58,750 --> 00:03:01,320
>> Cu o listă legată,
inserare este destul de ușor.

69
00:03:01,320 --> 00:03:03,290
Tocmai am tac pe față.

70
00:03:03,290 --> 00:03:04,892
Eliminarea este, de asemenea, destul de ușor.

71
00:03:04,892 --> 00:03:06,100
Trebuie să găsim elemente.

72
00:03:06,100 --> 00:03:07,270
Care implică unele căutarea.

73
00:03:07,270 --> 00:03:10,270
>> Dar, odată ce ați găsit elementul
sunteți în căutarea pentru, tot ce trebuie să faci

74
00:03:10,270 --> 00:03:12,830
este schimba un pointer,
eventual două dacă aveți

75
00:03:12,830 --> 00:03:15,151
un legat list-- un dublu
Lista legate, rather--

76
00:03:15,151 --> 00:03:16,650
și apoi puteți elibera doar nodul.

77
00:03:16,650 --> 00:03:18,399
Nu trebuie să transfere
totul în jur.

78
00:03:18,399 --> 00:03:22,090
Doar vă schimbați doi pointeri,
așa că e destul de rapid.

79
00:03:22,090 --> 00:03:23,470
>> Căutare este rău, nu?

80
00:03:23,470 --> 00:03:26,280
Pentru ca noi să găsească o
element dintr-o listă legată,

81
00:03:26,280 --> 00:03:29,154
dacă individual sau de două ori legate,
trebuie să-l căuta liniară.

82
00:03:29,154 --> 00:03:32,320
Trebuie să începem de la început și
muta la sfârșitul, sau de a începe de la capăt în mișcare

83
00:03:32,320 --> 00:03:33,860
la început.

84
00:03:33,860 --> 00:03:35,474
Noi nu avem acces aleator mai.

85
00:03:35,474 --> 00:03:37,265
Deci, dacă facem o
mulțime de cautare, poate

86
00:03:37,265 --> 00:03:39,830
o listă de legat nu este
chiar atât de bine pentru noi.

87
00:03:39,830 --> 00:03:43,750
>> Sunt de asemenea, foarte
greu pentru a sorta, nu?

88
00:03:43,750 --> 00:03:45,666
Singurul mod în care poți
sorta într-adevăr o listă legată

89
00:03:45,666 --> 00:03:47,870
este să-l sorta cum îl construiască.

90
00:03:47,870 --> 00:03:50,497
Dar, dacă-l rezolve în timp ce
construi o, nu mai ești

91
00:03:50,497 --> 00:03:51,830
face inserții rapide mai.

92
00:03:51,830 --> 00:03:53,746
Nu ești doar tacking
lucrurile pe față.

93
00:03:53,746 --> 00:03:55,710
Trebuie să găsiți cele mai
locul potrivit să-l puneți,

94
00:03:55,710 --> 00:03:57,820
și apoi inserarea dvs.
devine aproape la fel de rău

95
00:03:57,820 --> 00:03:59,390
ca introducerea într-o matrice.

96
00:03:59,390 --> 00:04:03,130
Deci, listele nu sunt legate de
atât de mare pentru sortarea datelor.

97
00:04:03,130 --> 00:04:05,830
>> Sunt, de asemenea, destul de mici, de dimensiuni înțelept.

98
00:04:05,830 --> 00:04:08,496
Lista legate de două ori ușor
mai mare decât liste individual legate,

99
00:04:08,496 --> 00:04:10,620
care sunt puțin mai mari
decât tablouri, dar nu este

100
00:04:10,620 --> 00:04:13,330
o cantitate mare de spațiu irosit.

101
00:04:13,330 --> 00:04:18,730
Deci, dacă spațiul este la o primă, dar
Nu o primă foarte intens,

102
00:04:18,730 --> 00:04:22,180
aceasta ar putea fi modul corect de a merge.

103
00:04:22,180 --> 00:04:23,330
>> Tabele de dispersie.

104
00:04:23,330 --> 00:04:25,850
Inserare într-un tabel hash
este destul de simplu.

105
00:04:25,850 --> 00:04:26,980
Este un proces în două etape.

106
00:04:26,980 --> 00:04:30,700
În primul rând avem nevoie pentru a rula datele noastre prin
o funcție hash pentru a obține un cod hash,

107
00:04:30,700 --> 00:04:37,550
și apoi ne-am introduce elementul în
Tabelul hash la codul hash locație.

108
00:04:37,550 --> 00:04:40,879
>> Eliminarea, similar cu lista legate,
este ușor odată ce ați găsit elementul.

109
00:04:40,879 --> 00:04:43,170
Trebuie să-l găsiți în primul rând,
dar atunci când îl ștergeți,

110
00:04:43,170 --> 00:04:45,128
trebuie doar să facă schimb de
un cuplu de indicii,

111
00:04:45,128 --> 00:04:47,250
dacă utilizați înlănțuirea separată.

112
00:04:47,250 --> 00:04:49,942
Dacă utilizați sondare,
sau dacă nu sunteți

113
00:04:49,942 --> 00:04:51,650
folosind înlănțuirea la toate
în tabelul hash,

114
00:04:51,650 --> 00:04:53,040
ștergere este de fapt foarte simplu.

115
00:04:53,040 --> 00:04:57,134
Tot ce trebuie să faceți este să hash
date, și apoi du-te la acea locație.

116
00:04:57,134 --> 00:04:58,925
Și presupunând că nu
nici coliziuni,

117
00:04:58,925 --> 00:05:01,650
vei putea să ștergeți foarte repede.

118
00:05:01,650 --> 00:05:04,930
>> Acum, căutare este în cazul în care lucrurile
obține un pic mai complicat.

119
00:05:04,930 --> 00:05:06,910
E, în medie, mai bine
decât liste legate.

120
00:05:06,910 --> 00:05:09,560
Dacă utilizați inlantuire,
aveți în continuare o listă legată,

121
00:05:09,560 --> 00:05:13,170
ceea ce înseamnă că încă au
căutare detrimentul o listă legată.

122
00:05:13,170 --> 00:05:18,390
Dar pentru că sunteți luați legat dvs.
Lista și divizarea peste 100 sau 1000

123
00:05:18,390 --> 00:05:25,380
sau n elemente în tabelul hash, ești
Listele sunt legate una n-lea dimensiunea.

124
00:05:25,380 --> 00:05:27,650
Sunt toți în mod substanțial mai mici.

125
00:05:27,650 --> 00:05:32,080
Ați legate n liste loc
de o listă legată de dimensiune n.

126
00:05:32,080 --> 00:05:34,960
>> Și așa această lume reală constantă
factor, care noi, în general

127
00:05:34,960 --> 00:05:39,730
nu vorbesc despre în complexitate timp ea,
de fapt, nu face o diferență aici.

128
00:05:39,730 --> 00:05:43,020
Deci căutare este încă liniară
căutare dacă utilizați inlantuire,

129
00:05:43,020 --> 00:05:46,780
dar lungimea listei
vă căutați prin

130
00:05:46,780 --> 00:05:50,080
este foarte, foarte scurt prin comparație.

131
00:05:50,080 --> 00:05:52,995
Din nou, în cazul în care sortarea este dvs.
Scopul aici, hash masă a

132
00:05:52,995 --> 00:05:54,370
probabil, nu modul corect de a merge.

133
00:05:54,370 --> 00:05:56,830
Doar folosi un array dacă sortare
este foarte important pentru tine.

134
00:05:56,830 --> 00:05:58,590
>> Și ei pot rula gama de dimensiuni.

135
00:05:58,590 --> 00:06:01,640
E greu de spus dacă o
tabel hash este mic sau mare,

136
00:06:01,640 --> 00:06:04,110
pentru că într-adevăr depinde de
cât de mare masa ta hash este.

137
00:06:04,110 --> 00:06:07,340
Dacă sunteți doar de gând să fie stocarea
cinci elemente din tabelul hash,

138
00:06:07,340 --> 00:06:10,620
și aveți un tabel hash
cu 10.000 de elemente în ea,

139
00:06:10,620 --> 00:06:12,614
esti, probabil, pierde o mulțime de spațiu.

140
00:06:12,614 --> 00:06:15,030
Contrast ești poate, de asemenea
au tabele de dispersie foarte compacte,

141
00:06:15,030 --> 00:06:18,720
dar mai mici masa ta hash devine,
cu atât mai mult fiecare dintre aceste liste legate

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

143
00:06:19,220 --> 00:06:22,607
Și deci nu este într-adevăr nici o modalitate de a defini
exact, ca dimensiune a unui tabel hash,

144
00:06:22,607 --> 00:06:24,440
dar este, probabil, în condiții de siguranță
să spun este, în general

145
00:06:24,440 --> 00:06:27,990
va fi mai mare decât un legat
Lista stocarea aceleași date,

146
00:06:27,990 --> 00:06:30,400
dar mai mică decât un trie.

147
00:06:30,400 --> 00:06:32,720
>> Și încearcă sunt a patra
dintre aceste structuri

148
00:06:32,720 --> 00:06:34,070
care am vorbit despre.

149
00:06:34,070 --> 00:06:36,450
Introducerea într-un trie este complex.

150
00:06:36,450 --> 00:06:38,400
Există o mulțime de dinamică
alocare de memorie,

151
00:06:38,400 --> 00:06:40,780
mai ales la început,
cum începi să construiască.

152
00:06:40,780 --> 00:06:43,700
Dar e timpul constant.

153
00:06:43,700 --> 00:06:47,690
E doar elementul uman
aici care face dificil.

154
00:06:47,690 --> 00:06:53,250
Având de a întâlni pointer null, malloc
spațiu, du-te acolo, spațiu posibil malloc

155
00:06:53,250 --> 00:06:54,490
de acolo din nou.

156
00:06:54,490 --> 00:06:58,880
Un fel de factor de intimidare
indicii în alocare de memorie dinamică

157
00:06:58,880 --> 00:07:00,130
este obstacol pentru a șterge.

158
00:07:00,130 --> 00:07:04,550
Dar, odată ce ați a reușit să respingă, inserție
de fapt, vine destul de simplu,

159
00:07:04,550 --> 00:07:06,810
și cu siguranță este constanta de timp.

160
00:07:06,810 --> 00:07:07,680
>> Ștergerea este ușor.

161
00:07:07,680 --> 00:07:11,330
Tot ce trebuie să faceți este să mergeți în jos un
câteva indicii și gratuit nodul,

162
00:07:11,330 --> 00:07:12,420
așa că e destul de bun.

163
00:07:12,420 --> 00:07:13,930
Căutare este, de asemenea, destul de rapid.

164
00:07:13,930 --> 00:07:16,780
Este numai pe baza
lungime de datele.

165
00:07:16,780 --> 00:07:19,924
Deci, dacă toate datele dumneavoastră este
cinci șiruri de caractere,

166
00:07:19,924 --> 00:07:22,590
de exemplu, te stocarea cinci
șiruri de caractere în trie-ul,

167
00:07:22,590 --> 00:07:25,439
este nevoie de doar cinci pași pentru
găsi ceea ce căutați pentru.

168
00:07:25,439 --> 00:07:28,480
Cinci este doar un factor constant, astfel încât
din nou, inserare, ștergere, și căutare

169
00:07:28,480 --> 00:07:31,670
aici sunt toate constantă de timp, în mod eficient.

170
00:07:31,670 --> 00:07:34,880
>> Un alt lucru este că trie este
de fapt, un fel de deja sortate, nu?

171
00:07:34,880 --> 00:07:36,800
În virtutea cum suntem
Elemente inserarea,

172
00:07:36,800 --> 00:07:40,060
mergând scrisoare prin scrisoarea
cheie, sau cifră cu cifră a cheii,

173
00:07:40,060 --> 00:07:45,084
de obicei, trie-ul sfârșește prin a fi
un fel de sortate ca se va construi.

174
00:07:45,084 --> 00:07:47,250
Ea nu face cu adevărat
sens să se gândească la sortarea

175
00:07:47,250 --> 00:07:49,874
în același mod în care ne gândim
cu tablouri, sau liste legate,

176
00:07:49,874 --> 00:07:51,070
sau tabele de dispersie.

177
00:07:51,070 --> 00:07:54,780
Dar într-un fel, dumneavoastră
trie este sortate ca te duci.

178
00:07:54,780 --> 00:07:58,630
>> Dezavantajul, desigur, este că
un trie devine rapid foarte mare.

179
00:07:58,630 --> 00:08:02,970
Din fiecare punct de joncțiune, s-ar putea
have-- dacă cheia este format din cifre,

180
00:08:02,970 --> 00:08:04,880
aveți 10 alte
locuri poti sa te duci, care

181
00:08:04,880 --> 00:08:07,490
înseamnă că fiecare nod
conține informații

182
00:08:07,490 --> 00:08:11,440
despre datele pe care doriți să stocați
la acel nod, plus 10 indicii.

183
00:08:11,440 --> 00:08:14,430
Care, pe IDE CS50, este de 80 bytes.

184
00:08:14,430 --> 00:08:17,220
Deci, este de cel puțin 80 de bytes pentru
fiecare nod pe care le creați,

185
00:08:17,220 --> 00:08:19,240
Și asta nu e chiar de numărare a datelor.

186
00:08:19,240 --> 00:08:24,950
Și dacă nodurile tale sunt
litere în loc de cifre,

187
00:08:24,950 --> 00:08:27,825
acum ai 26 de indicii
din orice locație.

188
00:08:27,825 --> 00:08:32,007
Și de 26 de ori 8 este, probabil, 200
bytes, sau ceva de genul asta.

189
00:08:32,007 --> 00:08:33,840
Și aveți de capital
și vă puteți lowercase--

190
00:08:33,840 --> 00:08:35,381
vezi unde am de gând cu asta, nu?

191
00:08:35,381 --> 00:08:37,500
Nodulii poate obține cu adevărat
mare, și astfel trie

192
00:08:37,500 --> 00:08:40,470
în sine, în general, poate
obține cu adevărat mare, prea.

193
00:08:40,470 --> 00:08:42,630
Deci, dacă spațiul este o mare
premium pe sistemul dvs.,

194
00:08:42,630 --> 00:08:45,830
un trie nu ar putea fi modul corect de a
du-te, chiar dacă alte beneficiile sale

195
00:08:45,830 --> 00:08:47,780
intra in joc.

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

197
00:08:48,710 --> 00:08:50,740
Acest lucru este CS50.

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