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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Uneori, atunci când construirea unei
Programul, ați putea dori să utilizeze un

3
00:00:10,890 --> 00:00:13,190
structura de date cunoscut ca un dicționar.

4
00:00:13,190 --> 00:00:17,960
A hărți dicționar chei, care sunt
de obicei siruri de caractere, la valori, int,

5
00:00:17,960 --> 00:00:21,900
caractere, un pointer la un obiect,
ceea ce ne dorim.

6
00:00:21,900 --> 00:00:26,510
E la fel ca dicționare obișnuite
că hartă cuvinte prin definiții.

7
00:00:26,510 --> 00:00:29,440
>> Dicționare ne oferi
capacitatea de a stoca informații

8
00:00:29,440 --> 00:00:32,750
asociat cu ceva
și căutați-l mai târziu.

9
00:00:32,750 --> 00:00:36,620
Deci, cum putem implementa de fapt o
dicționar în, să zicem, cod C care putem

10
00:00:36,620 --> 00:00:38,460
utilizarea în unul din programele noastre?

11
00:00:38,460 --> 00:00:41,790
Ei bine, există o mulțime de moduri în care
am putea pune în aplicare un dicționar.

12
00:00:41,790 --> 00:00:45,930
>> Pentru unul, am putea folosi o matrice pe care le
dinamic re-size sau am putea folosi un

13
00:00:45,930 --> 00:00:49,150
Lista legată, tabelul hash
sau un arbore binar.

14
00:00:49,150 --> 00:00:52,250
Dar orice am alege, ar trebui să ne
să fie conștient de eficiența și

15
00:00:52,250 --> 00:00:54,300
performanță de punere în aplicare.

16
00:00:54,300 --> 00:00:57,930
Ar trebui să ne gândim la algoritmul folosit
pentru a introduce și căuta obiecte în

17
00:00:57,930 --> 00:00:59,120
structura noastra de date.

18
00:00:59,120 --> 00:01:03,060
>> Pentru moment, să presupunem că ne-am
doriți să utilizați siruri de caractere ca taste.

19
00:01:03,060 --> 00:01:07,290
Hai sa vorbim despre o posibilitate,
o structură de date numit un trie.

20
00:01:07,290 --> 00:01:11,210
Deci, aici este o reprezentare vizuală
unui trie.

21
00:01:11,210 --> 00:01:14,590
>> După cum sugerează imagine, un trie
este o structură de date arbore cu

22
00:01:14,590 --> 00:01:16,050
noduri legate împreună.

23
00:01:16,050 --> 00:01:19,420
Vedem că există în mod clar o rădăcină
nod cu unele link-uri de extindere a

24
00:01:19,420 --> 00:01:20,500
alte noduri.

25
00:01:20,500 --> 00:01:23,040
Dar ceea ce nu fiecare nod format din?

26
00:01:23,040 --> 00:01:26,700
Dacă presupunem că suntem stocarea cheilor
cu doar caractere alfabetice, și

27
00:01:26,700 --> 00:01:30,150
nu ne pasă de capitalizare,
aici este o definiție a unui nod care

28
00:01:30,150 --> 00:01:31,100
va fi suficient.

29
00:01:31,100 --> 00:01:34,130
>> Un obiect al cărui tip este struct
nod are doua parti

30
00:01:34,130 --> 00:01:35,740
numit de date si copii.

31
00:01:35,740 --> 00:01:39,200
Am plecat de la partea de date ca un comentariu
să fie înlocuită cu o componentă

32
00:01:39,200 --> 00:01:43,190
declarație atunci când nod struct este
încorporate într-un program C.

33
00:01:43,190 --> 00:01:47,040
Partea de date a unui nod poate fi un
Valoare boolean pentru a indica dacă sau

34
00:01:47,040 --> 00:01:51,160
Nu nodul reprezintă finalizarea
de o cheie de dicționar sau ar putea fi o

35
00:01:51,160 --> 00:01:54,240
string reprezentând definiția
de un cuvânt în dicționar.

36
00:01:54,240 --> 00:01:58,870
>> Vom folosi o fata zambitoare pentru a indica
atunci când datele sunt prezente într-un nod.

37
00:01:58,870 --> 00:02:02,310
Există 26 de elemente în nostru
copii matrice, un index

38
00:02:02,310 --> 00:02:03,690
per caracter alfabetic.

39
00:02:03,690 --> 00:02:06,570
Vom vedea semnificația
din această curând.

40
00:02:06,570 --> 00:02:10,759
>> Să ne o privire mai atentă a nodului rădăcină
în diagrama noastră, care nu are date

41
00:02:10,759 --> 00:02:14,740
asociate cu acesta, după cum este indicat de către
lipsa de fața zâmbitoare în

42
00:02:14,740 --> 00:02:16,110
porțiune de date.

43
00:02:16,110 --> 00:02:19,910
Săgețile se extind din părțile
matrice copiii reprezintă non-nod

44
00:02:19,910 --> 00:02:21,640
indicii la alte noduri.

45
00:02:21,640 --> 00:02:25,500
De exemplu, săgeata extinsă de la
al doilea element de copii

46
00:02:25,500 --> 00:02:28,400
reprezintă litera B
într-o cheie dicționar.

47
00:02:28,400 --> 00:02:31,920
Și în diagrama de mai mare
am o eticheta cu un B.

48
00:02:31,920 --> 00:02:35,810
>> Rețineți că în diagrama mai mare, atunci când ne
trage un pointer la un alt nod, ea

49
00:02:35,810 --> 00:02:39,100
nu contează în cazul în care pe vârful săgeții
întâlnește celălalt nod.

50
00:02:39,100 --> 00:02:43,850
Nostru trie dicționar eșantion conține
două cuvinte, care și zoom.

51
00:02:43,850 --> 00:02:47,040
Să mergem printr-un exemplu de
uita în sus de date pentru o cheie.

52
00:02:47,040 --> 00:02:50,800
>> Să presupunem că am vrut să se uite în sus
valoare corespunzătoare pentru baie cheie.

53
00:02:50,800 --> 00:02:53,610
Vom începe uite noastre în sus
la nodul rădăcină.

54
00:02:53,610 --> 00:02:57,870
Apoi vom lua prima literă a noastră
cheie, B, și pentru a găsi corespunzătoare

55
00:02:57,870 --> 00:03:00,020
la fața locului în copii nostru matrice.

56
00:03:00,020 --> 00:03:04,490
Observați că există exact 26 pete
în matrice, una pentru fiecare literă a

57
00:03:04,490 --> 00:03:05,330
alfabetul.

58
00:03:05,330 --> 00:03:08,800
Și vom avea pete reprezintă
litere ale alfabetului, în ordine.

59
00:03:08,800 --> 00:03:13,960
>> Ne vom uita la cea de a doua index, apoi,
indicele unul, pentru B. In general, dacă

60
00:03:13,960 --> 00:03:17,990
au un caracter alfabetic C noi
ar putea determina locul corespunzător

61
00:03:17,990 --> 00:03:21,520
în copii matrice folosind
un calcul de genul asta.

62
00:03:21,520 --> 00:03:25,140
Am fi putut folosi pentru copii mai mari
matrice dacă ne-am dorit să oferim aspect din

63
00:03:25,140 --> 00:03:28,380
chei, cu o gamă mai largă de personaje,
cum ar fi întreaga

64
00:03:28,380 --> 00:03:29,880
De caractere ASCII.

65
00:03:29,880 --> 00:03:32,630
>> În acest caz, indicatorul
la copiii nostru matrice la

66
00:03:32,630 --> 00:03:34,320
indicele unul nu este nulă.

67
00:03:34,320 --> 00:03:36,600
Asa ca vom continua căutarea
up baia cheie.

68
00:03:36,600 --> 00:03:40,130
Dacă am întâlnit vreodată un pointer nul
la fața locului adecvat în copiii

69
00:03:40,130 --> 00:03:43,230
matrice în timp ce ne-am traversat nodurile,
atunci va trebui să spunem că ne-am

70
00:03:43,230 --> 00:03:45,630
nu a putut găsi nimic pentru acea cheie.

71
00:03:45,630 --> 00:03:49,370
>> Acum, vom avea de-a doua scrisoare de
cheia noastră, A, și să continue în urma

72
00:03:49,370 --> 00:03:52,400
indicii în acest fel până când vom
ajunge la sfârșitul cheia noastră.

73
00:03:52,400 --> 00:03:56,530
Dacă vom ajunge la capătul cheii fără
a lovit nici unghiuri moarte, indicii nule,

74
00:03:56,530 --> 00:03:59,730
cum este cazul aici, atunci numai noi
Trebuie să verific un singur lucru.

75
00:03:59,730 --> 00:04:02,110
Este această cheie de fapt
în dicționar?

76
00:04:02,110 --> 00:04:07,660
>> Dacă este așa, ar trebui să găsim o valoare, precum și o
icon fata zambitoare în diagrama noastră, unde

77
00:04:07,660 --> 00:04:08,750
cuvântul se termină.

78
00:04:08,750 --> 00:04:12,270
Dacă există ceva stocate cu
datele, atunci putem întoarce.

79
00:04:12,270 --> 00:04:16,500
De exemplu, grădina zoologică cheie nu este în
dicționar, chiar dacă am putea avea

80
00:04:16,500 --> 00:04:19,810
a ajuns la sfârșitul acestei taste, fără vreodată
lovind un pointer nul, în timp ce noi

81
00:04:19,810 --> 00:04:21,089
itera prin trie.

82
00:04:21,089 --> 00:04:25,436
>> Dacă am încercat să te uiți în sus baia cheie,
în al doilea rând să indice matrice ultimul nod,

83
00:04:25,436 --> 00:04:28,750
corespunzătoare literei H, ar
au organizat un pointer nul.

84
00:04:28,750 --> 00:04:31,120
Deci, baie, nu se află în dicționar.

85
00:04:31,120 --> 00:04:34,800
Și astfel un trie este unic în faptul că tastele
nu sunt niciodată stocate în mod explicit în

86
00:04:34,800 --> 00:04:36,650
structura de date.

87
00:04:36,650 --> 00:04:38,810
Deci, cum putem introduce ceva
într-un trie?

88
00:04:38,810 --> 00:04:41,780
>> Să introduceți cheia
grădină zoologică în trie nostru.

89
00:04:41,780 --> 00:04:46,120
Amintiți-vă că o fata zambitoare la un nod
ar putea corespunde cu cod la un simplu

90
00:04:46,120 --> 00:04:50,170
Valoare Boolean pentru a indica faptul că zoo
este în dicționar sau ar putea

91
00:04:50,170 --> 00:04:53,710
corespund la mai multe informații pe care le
doresc să se asocieze cu gradina zoologica cheie,

92
00:04:53,710 --> 00:04:56,860
cum ar fi definiția
cuvânt sau altceva.

93
00:04:56,860 --> 00:05:00,350
În unele privințe, procesul de a insera
ceva într-un trie este similar cu

94
00:05:00,350 --> 00:05:02,060
căutând ceva într-un trie.

95
00:05:02,060 --> 00:05:05,720
>> Vom începe cu nodul rădăcină nou,
Următoarele indicii corespunzătoare

96
00:05:05,720 --> 00:05:07,990
scrisorile de cheia noastră.

97
00:05:07,990 --> 00:05:11,310
Din fericire, noi am fost capabil să urmeze indicii
tot drumul până când am ajuns la

98
00:05:11,310 --> 00:05:12,770
capătul cheii.

99
00:05:12,770 --> 00:05:16,480
Deoarece grădină zoologică este un prefix al cuvântului
zoom-ul, care este un membru al

100
00:05:16,480 --> 00:05:19,440
dicționar, nu avem nevoie să
aloca noi noduri.

101
00:05:19,440 --> 00:05:23,140
>> Putem modifica nodul pentru a indica faptul că
calea de caractere care duc la

102
00:05:23,140 --> 00:05:25,360
reprezintă o cheie în dicționarul nostru.

103
00:05:25,360 --> 00:05:28,630
Acum, haideți să încercați să introduceți
BATH cheie în trie.

104
00:05:28,630 --> 00:05:32,260
Vom începe de la nodul rădăcină
și să urmeze din nou indicii.

105
00:05:32,260 --> 00:05:35,620
Dar, în această situație, am lovit un mort
se încheie înainte de suntem capabili de a ajunge la

106
00:05:35,620 --> 00:05:36,940
capăt al cheii.

107
00:05:36,940 --> 00:05:40,980
Acum, va trebui să aloce unor noi
noduri va trebui să aloce un nou

108
00:05:40,980 --> 00:05:43,660
nod pentru fiecare rămasă
scrisoarea de cheia noastră.

109
00:05:43,660 --> 00:05:46,740
>> În acest caz, avem nevoie doar de
de a aloca un nod nou.

110
00:05:46,740 --> 00:05:50,590
Atunci vom avea nevoie pentru a face indicele H
referire la acest nou nod.

111
00:05:50,590 --> 00:05:54,070
Încă o dată, putem modifica nodul la
indică faptul că drumul de caractere

112
00:05:54,070 --> 00:05:57,120
care duce la aceasta reprezintă o
cheie în dicționarul nostru.

113
00:05:57,120 --> 00:06:00,730
Să rationa despre asimptotice
complexitatea procedurilor noastre pentru aceste

114
00:06:00,730 --> 00:06:02,110
două operațiuni.

115
00:06:02,110 --> 00:06:06,420
>> Se observă că în ambele cazuri numărul
de pașii algoritmului nostru a fost luat

116
00:06:06,420 --> 00:06:09,470
proporțională cu numărul de
litere din cuvântul cheie.

117
00:06:09,470 --> 00:06:10,220
Asta-i drept.

118
00:06:10,220 --> 00:06:13,470
Când doriți să căutați un cuvânt într-o
trie trebuie doar să itera prin

119
00:06:13,470 --> 00:06:17,100
literele una câte una, până când, fie
ajunge la sfârșitul cuvântului sau

120
00:06:17,100 --> 00:06:19,060
a lovit-o fundătură în trie.

121
00:06:19,060 --> 00:06:22,470
>> Și atunci când doriți să introduceți o cheie
Valoarea pereche într-un trie, utilizând

122
00:06:22,470 --> 00:06:26,250
Procedura am discutat, cel mai rău caz
va avea tu alocarea un nou nod

123
00:06:26,250 --> 00:06:27,550
pentru fiecare literă.

124
00:06:27,550 --> 00:06:31,290
Și vom presupune că alocarea
este o operațiune de timp constant.

125
00:06:31,290 --> 00:06:35,850
Deci, dacă am presupune că lungimea cheii este
delimitate de o constantă fixă, ambele

126
00:06:35,850 --> 00:06:39,400
inserare și privi în sus sunt constante
operațiunilor de timp pentru un trie.

127
00:06:39,400 --> 00:06:42,930
>> Dacă nu facem această presupunere că
lungimea cheii este delimitată de un fix

128
00:06:42,930 --> 00:06:46,650
constant, apoi inserare și privi în sus,
în cel mai rău caz, sunt liniare în

129
00:06:46,650 --> 00:06:48,240
lungimea codului.

130
00:06:48,240 --> 00:06:51,800
Observați că numărul de elemente stocate
în trie nu afectează aspectul în sus

131
00:06:51,800 --> 00:06:52,820
sau timp de inserare.

132
00:06:52,820 --> 00:06:55,360
Este afectat doar de către
lungimea codului.

133
00:06:55,360 --> 00:06:59,300
>> Prin contrast, adaugand intrări la, să zicem,
un tabel hash tinde să facă

134
00:06:59,300 --> 00:07:01,250
viitor căuta mai lent.

135
00:07:01,250 --> 00:07:04,520
În timp ce acest lucru poate suna atragatoare la început,
noi ar trebui să țină cont de faptul că o

136
00:07:04,520 --> 00:07:08,740
complexitate asimptotică favorabil nu
înseamnă că, în practică, datele

137
00:07:08,740 --> 00:07:11,410
Structura este în mod necesar
dincolo de reproș.

138
00:07:11,410 --> 00:07:15,860
Noi trebuie să ia în considerare, de asemenea, că pentru a stoca o
cuvânt într-un trie avem nevoie, în cel mai rău

139
00:07:15,860 --> 00:07:19,700
caz, un număr de noduri proporțional
cu lungimea cuvântului în sine.

140
00:07:19,700 --> 00:07:21,880
>> Încearcă tendința de a folosi o mulțime de spațiu.

141
00:07:21,880 --> 00:07:25,620
Aceasta este în contrast cu un tabel hash,
unde avem nevoie doar de un nou nod de

142
00:07:25,620 --> 00:07:27,940
stoca unele pereche valoare-cheie.

143
00:07:27,940 --> 00:07:31,370
Acum, din nou, în teorie, spațiu mare
consum nu pare ca o mare

144
00:07:31,370 --> 00:07:34,620
a face, mai ales având în vedere că moderne
computerele au gigabytes și

145
00:07:34,620 --> 00:07:36,180
GB de memorie.

146
00:07:36,180 --> 00:07:39,200
Dar se pare că mai avem încă
să vă faceți griji cu privire la utilizarea de memorie și

147
00:07:39,200 --> 00:07:42,540
organizare de dragul de
performanță, deoarece calculatoare moderne

148
00:07:42,540 --> 00:07:46,960
au mecanisme în loc sub
capota pentru a accelera de acces la memorie.

149
00:07:46,960 --> 00:07:51,180
>> Dar aceste mecanisme funcționează cel mai bine atunci când
accese de memorie sunt făcute în compact

150
00:07:51,180 --> 00:07:52,810
regiuni sau zone.

151
00:07:52,810 --> 00:07:55,910
Și nodurile de un trie ar putea locui
oriunde în grămadă.

152
00:07:55,910 --> 00:07:58,390
Dar acestea sunt compromisuri
că trebuie să ne gândim.

153
00:07:58,390 --> 00:08:01,440
>> Amintiți-vă că, atunci când aleg un date
structura pentru o anumită sarcină, ne-am

154
00:08:01,440 --> 00:08:04,420
ar trebui să se gândească la ce fel de
operațiunile de structura de date trebuie să

155
00:08:04,420 --> 00:08:07,140
suport și cât de mult a performanței
fiecăruia dintre aceste

156
00:08:07,140 --> 00:08:09,080
Operațiuni contează pentru noi.

157
00:08:09,080 --> 00:08:11,300
Aceste operațiuni pot chiar
se extind dincolo de doar

158
00:08:11,300 --> 00:08:13,430
aspect de bază în sus și inserare.

159
00:08:13,430 --> 00:08:17,010
Să presupunem că ne-am dorit să pună în aplicare un fel
de funcționalitate auto-complete, mult

160
00:08:17,010 --> 00:08:18,890
cum ar fi motorul de căutare Google nu.

161
00:08:18,890 --> 00:08:22,210
Asta este, se întoarcă toate cheile și
potențial valori care

162
00:08:22,210 --> 00:08:24,130
au un anumit prefix.

163
00:08:24,130 --> 00:08:27,050
>> Un trie este unic util
pentru această operație.

164
00:08:27,050 --> 00:08:29,890
Este simplu pentru a itera prin
trie pentru fiecare caracter de

165
00:08:29,890 --> 00:08:30,950
prefixul.

166
00:08:30,950 --> 00:08:33,559
La fel ca o operațiune privi în sus,
am putea urmări indicii

167
00:08:33,559 --> 00:08:35,400
caracter cu caracter.

168
00:08:35,400 --> 00:08:38,659
Apoi, când am ajuns la sfârșitul perioadei de
prefix, am putea repeta prin

169
00:08:38,659 --> 00:08:42,049
restul porțiune a structurii de date
deoarece oricare dintre tastele dincolo

170
00:08:42,049 --> 00:08:43,980
acest punct au prefixul.

171
00:08:43,980 --> 00:08:47,670
>> Este, de asemenea, ușor pentru a obține această listare
în ordine alfabetică de la

172
00:08:47,670 --> 00:08:50,970
elemente de matrice copii
sunt ordonate alfabetic.

173
00:08:50,970 --> 00:08:54,420
Deci sperăm că veți lua în considerare
da încearcă un try.

174
00:08:54,420 --> 00:08:56,085
Sunt Kevin Schmid, iar acest lucru este CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, aceasta este începutul
a declinului.

177
00:09:00,790 --> 00:09:01,350
Îmi pare rău.

178
00:09:01,350 --> 00:09:01,870
Scuze.

179
00:09:01,870 --> 00:09:02,480
Scuze.

180
00:09:02,480 --> 00:09:03,130
Scuze.

181
00:09:03,130 --> 00:09:03,950
>> Strike patru.

182
00:09:03,950 --> 00:09:04,360
Am plecat.

183
00:09:04,360 --> 00:09:05,280
Scuze.

184
00:09:05,280 --> 00:09:06,500
Scuze.

185
00:09:06,500 --> 00:09:07,490
Scuze.

186
00:09:07,490 --> 00:09:12,352
Ne pare rău pentru a face persoana care
are pentru a edita acest razna.

187
00:09:12,352 --> 00:09:13,280
>> Scuze.

188
00:09:13,280 --> 00:09:13,880
Scuze.

189
00:09:13,880 --> 00:09:15,080
Scuze.

190
00:09:15,080 --> 00:09:15,680
Scuze.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Foarte bine.

192
00:09:16,280 --> 00:09:17,530
, Care a fost foarte bine facut.

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