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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Ponekad, kada je zgrada
Program, možda želite koristiti

3
00:00:10,890 --> 00:00:13,190
struktura podataka poznat kao rječniku.

4
00:00:13,190 --> 00:00:17,960
A rječnik zemljovidi tipke, koje su
obično žice, za vrijednostima, Ints,

5
00:00:17,960 --> 00:00:21,900
znakova, kazaljka na nekom objektu,
što god želimo.

6
00:00:21,900 --> 00:00:26,510
To je baš kao i obične rječnika
Ta je karta riječi kroz definicije.

7
00:00:26,510 --> 00:00:29,440
>> Rječnici daju nam
Sposobnost za pohranu podataka

8
00:00:29,440 --> 00:00:32,750
povezana s nečim
i gledati ga kasnije.

9
00:00:32,750 --> 00:00:36,620
Pa kako smo zapravo provesti
rječnik u, recimo, C kod koje možemo

10
00:00:36,620 --> 00:00:38,460
koristiti u jednom od naših programa?

11
00:00:38,460 --> 00:00:41,790
Pa, postoji mnogo načina na koje
bismo mogli provesti rječnika.

12
00:00:41,790 --> 00:00:45,930
>> Za jednu, da bismo mogli koristiti niz koji smo
dinamički re-size ili bismo mogli koristiti

13
00:00:45,930 --> 00:00:49,150
povezani popis, hash tablicu
ili binarno stablo.

14
00:00:49,150 --> 00:00:52,250
No, što god odlučite, trebali bismo
voditi računa o učinkovitosti i

15
00:00:52,250 --> 00:00:54,300
izvedba provedbu.

16
00:00:54,300 --> 00:00:57,930
Trebamo razmišljati o algoritmu koristi
umetnuti i gledati stvari u

17
00:00:57,930 --> 00:00:59,120
Naša struktura podataka.

18
00:00:59,120 --> 00:01:03,060
>> Za sada, neka Pretpostavimo da smo
želite koristiti nizove kao tipke.

19
00:01:03,060 --> 00:01:07,290
Pričajmo o jednom mogućnošću,
struktura podataka naziva trie.

20
00:01:07,290 --> 00:01:11,210
Dakle, ovdje je vizualni prikaz
od trie.

21
00:01:11,210 --> 00:01:14,590
>> Kako slika govori, trie
je stablo struktura podataka s

22
00:01:14,590 --> 00:01:16,050
čvorovi povezani.

23
00:01:16,050 --> 00:01:19,420
Vidimo da postoji jasno korijena
čvor s neke poveznice proteže do

24
00:01:19,420 --> 00:01:20,500
ostali čvorovi.

25
00:01:20,500 --> 00:01:23,040
No, ono što se svaki čvor sastoji?

26
00:01:23,040 --> 00:01:26,700
Ako pretpostavimo da smo pohranu ključeva
sa samo od slova, a

27
00:01:26,700 --> 00:01:30,150
ne brinu o kapitalizaciji,
evo definicija čvor koji

28
00:01:30,150 --> 00:01:31,100
će biti dosta.

29
00:01:31,100 --> 00:01:34,130
>> Objekt čija je tip struct
čvor ima dva dijela

30
00:01:34,130 --> 00:01:35,740
zove podatke i djecu.

31
00:01:35,740 --> 00:01:39,200
Ostavili smo dio podataka kao komentar
biti zamijenjen komponente

32
00:01:39,200 --> 00:01:43,190
Izjava kad struct čvor
uključene u C programu.

33
00:01:43,190 --> 00:01:47,040
Dio podataka od čvora može biti
Boolean vrijednost naznačiti je li ili

34
00:01:47,040 --> 00:01:51,160
Ne čvor predstavlja završetak
riječnika ključem ili bi to moglo biti

35
00:01:51,160 --> 00:01:54,240
string predstavlja definiciju
od riječi u rječniku.

36
00:01:54,240 --> 00:01:58,870
>> Mi ćemo koristiti smješko za označavanje
Kada se podaci prisutan u čvor.

37
00:01:58,870 --> 00:02:02,310
Postoji 26 elementi u našem
djeca polje, jedan index

38
00:02:02,310 --> 00:02:03,690
po abecedi.

39
00:02:03,690 --> 00:02:06,570
Vidjet ćemo značaj
to uskoro.

40
00:02:06,570 --> 00:02:10,759
>> Uzmimo bliži pogled korijenskog čvora
u našem dijagramu, koja nema podataka

41
00:02:10,759 --> 00:02:14,740
povezane s njim, na što ukazuje
Izostanak smješko u

42
00:02:14,740 --> 00:02:16,110
predio za podatke.

43
00:02:16,110 --> 00:02:19,910
Strelice koje se protežu od dijela
djeca Polje predstavljaju ne-čvor

44
00:02:19,910 --> 00:02:21,640
upućivanje na druge čvorove.

45
00:02:21,640 --> 00:02:25,500
Na primjer, koji se proteže od strelica
Drugi element djece

46
00:02:25,500 --> 00:02:28,400
predstavlja slovo B
u rječniku ključu.

47
00:02:28,400 --> 00:02:31,920
I u većoj slici
smo ga označiti s B.

48
00:02:31,920 --> 00:02:35,810
>> Imajte na umu da se u većoj slici, kad smo
povući pokazivač na drugi čvor, to

49
00:02:35,810 --> 00:02:39,100
Nije važno gdje strijele
zadovoljava taj drugi čvor.

50
00:02:39,100 --> 00:02:43,850
Naš uzorak rječnik trie sadrži
dvije riječi, da je i zoom.

51
00:02:43,850 --> 00:02:47,040
Idemo prošetati kroz primjer
uvidom u podatke za neku tipku.

52
00:02:47,040 --> 00:02:50,800
>> Pretpostavimo da smo htjeli pogledati
odgovara vrijednosti za ključ kupku.

53
00:02:50,800 --> 00:02:53,610
Počet ćemo naš pogled prema gore
na root čvor.

54
00:02:53,610 --> 00:02:57,870
Onda ćemo uzeti prvo slovo od naših
Ključ, B, i pronaći odgovarajuća

55
00:02:57,870 --> 00:03:00,020
uočiti u našu djecu niz.

56
00:03:00,020 --> 00:03:04,490
Uočite da postoje točno 26 mjesta
u nizu, jedan za svako slovo

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

58
00:03:05,330 --> 00:03:08,800
I mi ćemo imati spotova predstavljaju
slova abecede u redu.

59
00:03:08,800 --> 00:03:13,960
>> Mi ćemo gledati na drugom indeksa tada,
index je jedan, za B. U principu, ako smo

60
00:03:13,960 --> 00:03:17,990
imaju neke slovo abecede C mi
može odrediti odgovarajuće mjesto

61
00:03:17,990 --> 00:03:21,520
u djece niz pomoću
Izračun ovako.

62
00:03:21,520 --> 00:03:25,140
Dobro bi nam veće djece
Niz ako smo htjeli ponuditi Potraži

63
00:03:25,140 --> 00:03:28,380
tipke sa širim rasponom likova,
kao cjelokupnog

64
00:03:28,380 --> 00:03:29,880
ASCII skup znakova.

65
00:03:29,880 --> 00:03:32,630
>> U tom slučaju, pokazivač
u našu djecu niz na

66
00:03:32,630 --> 00:03:34,320
index netko nije null.

67
00:03:34,320 --> 00:03:36,600
Tako ćemo i dalje u potrazi
do ključnog kupki.

68
00:03:36,600 --> 00:03:40,130
Ako smo ikada naišli na null pokazivač
na odgovarajuće mjesto u djece

69
00:03:40,130 --> 00:03:43,230
Niz dok smo prelazili preko čvorova,
onda ćemo morati reći da smo

70
00:03:43,230 --> 00:03:45,630
nije mogao pronaći ništa za taj ključ.

71
00:03:45,630 --> 00:03:49,370
>> Sada, mi ćemo poduzeti drugi pismo
naš ključ, i nastavite slijediti

72
00:03:49,370 --> 00:03:52,400
upućuje se na taj način sve dok ne
do kraja našeg ključu.

73
00:03:52,400 --> 00:03:56,530
Ako ćemo do kraja ključ bez
udarca bilo slijepe ulice, null naputke,

74
00:03:56,530 --> 00:03:59,730
kao što je ovdje slučaj, onda smo samo
Moram provjeriti još jednu stvar.

75
00:03:59,730 --> 00:04:02,110
Je li to ključ zapravo
u rječniku?

76
00:04:02,110 --> 00:04:07,660
>> Ako je tako, trebali bismo se naći vrijednost, te
smiley ikona lice u našoj shemi gdje

77
00:04:07,660 --> 00:04:08,750
Riječ završava.

78
00:04:08,750 --> 00:04:12,270
Ako postoji nešto drugo spremaju s
podatke, a zatim ga možemo vratiti.

79
00:04:12,270 --> 00:04:16,500
Primjerice, ključ zoo nije
rječnik, iako smo mogli imati

80
00:04:16,500 --> 00:04:19,810
došli do kraja ovog ključa bez ikada
udarajući null pointer, dok smo

81
00:04:19,810 --> 00:04:21,089
ponoviti kroz trie.

82
00:04:21,089 --> 00:04:25,436
>> Ako smo pokušali potražiti ključnu kupku,
predzadnji čvora indeksa polja,

83
00:04:25,436 --> 00:04:28,750
odgovara slova H, bi
održali su null pokazivač.

84
00:04:28,750 --> 00:04:31,120
Dakle kupka je nema u rječniku.

85
00:04:31,120 --> 00:04:34,800
I tako trie je jedinstvena po tome što ključeva
se nikada nije izričito pohranjene u

86
00:04:34,800 --> 00:04:36,650
Struktura podataka.

87
00:04:36,650 --> 00:04:38,810
Pa kako ćemo umetnuti nešto
u trie?

88
00:04:38,810 --> 00:04:41,780
>> Idemo umetnite ključ
Zoološki vrt u naš trie.

89
00:04:41,780 --> 00:04:46,120
Ne zaboravite da je smješko na čvoru
može odgovarati u kodu za jednostavne

90
00:04:46,120 --> 00:04:50,170
Boolean vrijednost naznačiti da zoološki vrt
je u rječniku ili je mogao

91
00:04:50,170 --> 00:04:53,710
odgovaraju dodatne informacije koje smo
žele povezati s ključnim zoološkom vrtu,

92
00:04:53,710 --> 00:04:56,860
kao definicija
Riječ ili nešto drugo.

93
00:04:56,860 --> 00:05:00,350
Na neki način, postupak za umetanje
nešto u trie je sličan

94
00:05:00,350 --> 00:05:02,060
gleda se nešto u trie.

95
00:05:02,060 --> 00:05:05,720
>> Počet ćemo s root čvor opet,
Sljedeće naputke odgovara

96
00:05:05,720 --> 00:05:07,990
slova od naših ključnih.

97
00:05:07,990 --> 00:05:11,310
Srećom, bili smo u mogućnosti pratiti naputke
sve dok nismo stigli do

98
00:05:11,310 --> 00:05:12,770
kraj ključa.

99
00:05:12,770 --> 00:05:16,480
Budući da je zoološki vrt je prefiks riječi
zoom, koji je član

100
00:05:16,480 --> 00:05:19,440
rječnik, mi ne trebaju
izdvojiti neke nove čvorove.

101
00:05:19,440 --> 00:05:23,140
>> Možemo mijenjati čvor ukazuje da
Put od likova koji vode do

102
00:05:23,140 --> 00:05:25,360
predstavlja ključ u našem rječniku.

103
00:05:25,360 --> 00:05:28,630
Sada, pokušajmo umetanja
Ključ KUPKA u trie.

104
00:05:28,630 --> 00:05:32,260
Počet ćemo na root čvor
i opet slijediti naputke.

105
00:05:32,260 --> 00:05:35,620
No, u ovoj situaciji, udario mi mrtav
završiti prije nego što smo mogli dobiti

106
00:05:35,620 --> 00:05:36,940
kraj ključa.

107
00:05:36,940 --> 00:05:40,980
Sada ćemo morati izdvojiti neke nove
čvorovi će trebati izdvojiti jedan novi

108
00:05:40,980 --> 00:05:43,660
čvor za svaki preostali
Pismo našeg ključa.

109
00:05:43,660 --> 00:05:46,740
>> U ovom slučaju, samo trebamo
izdvojiti jedan novi čvor.

110
00:05:46,740 --> 00:05:50,590
Onda ćemo morati napraviti indeks H
Ovaj se novi čvor.

111
00:05:50,590 --> 00:05:54,070
Još jednom, možemo mijenjati čvor na
pokazuju da je put od likova

112
00:05:54,070 --> 00:05:57,120
što je dovelo do njega predstavlja
Ključ u našem rječniku.

113
00:05:57,120 --> 00:06:00,730
Neka je razlog zbog asymptotic
složenost naših postupaka za njih

114
00:06:00,730 --> 00:06:02,110
dvije operacije.

115
00:06:02,110 --> 00:06:06,420
>> Primjećujemo da je u oba slučaja broj
koraka naš algoritam uzeo je

116
00:06:06,420 --> 00:06:09,470
proporcionalna broju
slova u ključnoj riječi.

117
00:06:09,470 --> 00:06:10,220
To je točno.

118
00:06:10,220 --> 00:06:13,470
Kada želite potražiti riječi u
trie trebate samo ponoviti kroz

119
00:06:13,470 --> 00:06:17,100
slova jedan po jedan sve dok ili ne
do kraja riječi ili

120
00:06:17,100 --> 00:06:19,060
pogodak ćorsokak u trie.

121
00:06:19,060 --> 00:06:22,470
>> A kad želite umetnuti ključ
Vrijednost par u trie pomoću

122
00:06:22,470 --> 00:06:26,250
Postupak smo razgovarali, u najgorem slučaju
imat ćete dodjele novi čvor

123
00:06:26,250 --> 00:06:27,550
za svako slovo.

124
00:06:27,550 --> 00:06:31,290
A mi ćemo pretpostaviti da raspodjelu
je konstantna vrijeme operacije.

125
00:06:31,290 --> 00:06:35,850
Dakle, ako pretpostavimo da je duljina ključa
omeđen fiksnom konstanta, kako

126
00:06:35,850 --> 00:06:39,400
umetanje i pogledati konstantne
Vrijeme radnje za trie.

127
00:06:39,400 --> 00:06:42,930
>> Ako mi ne bi tu pretpostavku da
Dužina ključa je omeđen fiksna

128
00:06:42,930 --> 00:06:46,650
konstantna, a zatim umetanje i pogledati,
u najgorem slučaju, su linearna u

129
00:06:46,650 --> 00:06:48,240
Duljina ključa.

130
00:06:48,240 --> 00:06:51,800
Uočite da je broj predmeta pohranjena
u trie ne utječe na pogled prema gore

131
00:06:51,800 --> 00:06:52,820
ili umetanje vrijeme.

132
00:06:52,820 --> 00:06:55,360
To je samo utjecali
Duljina ključa.

133
00:06:55,360 --> 00:06:59,300
>> Za razliku od toga, dodao unose se, recimo,
hash tablica ima tendenciju da se

134
00:06:59,300 --> 00:07:01,250
Budućnost pogledati sporije.

135
00:07:01,250 --> 00:07:04,520
Iako ovo može zvučati privlačno na prvi pogled,
treba imati na umu da

136
00:07:04,520 --> 00:07:08,740
povoljni asimptotičnu složenost ne
znači da je u praksi podataka

137
00:07:08,740 --> 00:07:11,410
Struktura je nužno
besprijekorno.

138
00:07:11,410 --> 00:07:15,860
Također, moramo uzeti u obzir da je za pohranu
Riječ u trie trebamo, u najgorem

139
00:07:15,860 --> 00:07:19,700
slučaju, broj čvorova proporcionalna
duljini same riječi.

140
00:07:19,700 --> 00:07:21,880
>> Pokušava imaju tendenciju da koriste puno prostora.

141
00:07:21,880 --> 00:07:25,620
To je u suprotnosti s hash tablici,
gdje smo samo jedan novi čvor na

142
00:07:25,620 --> 00:07:27,940
pohraniti neke ključne vrijednosti par.

143
00:07:27,940 --> 00:07:31,370
Sada, ponovno je u teoriji, veliki prostor
Potrošnja ne čini kao veliki

144
00:07:31,370 --> 00:07:34,620
nositi, pogotovo s obzirom da je moderni
računala imaju gigabajta i

145
00:07:34,620 --> 00:07:36,180
gigabajta memorije.

146
00:07:36,180 --> 00:07:39,200
No, ispostavilo se da još uvijek imamo
brinuti o korištenju memorije i

147
00:07:39,200 --> 00:07:42,540
Organizacija za dobrobit
performanse, jer suvremeni računala

148
00:07:42,540 --> 00:07:46,960
imaju mehanizme pod
Sjenilo za ubrzanje pristupa memorije.

149
00:07:46,960 --> 00:07:51,180
>> No, ti mehanizmi rade najbolje kada
memorije pristupi su izrađene u kompaktni

150
00:07:51,180 --> 00:07:52,810
regije ili područja.

151
00:07:52,810 --> 00:07:55,910
A čvorovi trie mogao nalaziti
bilo gdje u toj gomili.

152
00:07:55,910 --> 00:07:58,390
No, to su kompromisi
koje moramo uzeti u obzir.

153
00:07:58,390 --> 00:08:01,440
>> Zapamtite da, pri odabiru podatke
Struktura za određeni zadatak, mi

154
00:08:01,440 --> 00:08:04,420
trebali razmišljati o tome što vrste
Operacije struktura podataka treba

155
00:08:04,420 --> 00:08:07,140
Podrška i koliko performanse
svakog od tih

156
00:08:07,140 --> 00:08:09,080
operacije je stalo do nas.

157
00:08:09,080 --> 00:08:11,300
Ove operacije može čak
proširiti dalje od pukog

158
00:08:11,300 --> 00:08:13,430
Osnovni izgled i umetanje.

159
00:08:13,430 --> 00:08:17,010
Pretpostavimo da smo htjeli provesti neku vrstu
auto-kompletna funkcionalnost, mnogo

160
00:08:17,010 --> 00:08:18,890
kao što je Google tražilica radi.

161
00:08:18,890 --> 00:08:22,210
To jest, vratiti sve tipke i
potencijalno vrijednosti koje

162
00:08:22,210 --> 00:08:24,130
imaju određeni prefiks.

163
00:08:24,130 --> 00:08:27,050
>> Trie je jedinstveno korisne
Za ovaj postupak.

164
00:08:27,050 --> 00:08:29,890
To je jednostavan za ponoviti kroz
trie za svaki karakter

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

166
00:08:30,950 --> 00:08:33,559
Baš kao i pogled do operacije,
možemo pratiti naputke

167
00:08:33,559 --> 00:08:35,400
slovo po slovo.

168
00:08:35,400 --> 00:08:38,659
Zatim, kada dolazimo do kraja
prefiks, mogli bismo ponoviti kroz

169
00:08:38,659 --> 00:08:42,049
Preostali dio strukture podataka
budući da je svaka od ključeva izvan

170
00:08:42,049 --> 00:08:43,980
ova točka ima prefiks.

171
00:08:43,980 --> 00:08:47,670
>> To je također lako dobiti ovaj oglas
abecednim redom od

172
00:08:47,670 --> 00:08:50,970
dijelovi dje niz
su poredani po abecedi.

173
00:08:50,970 --> 00:08:54,420
Dakle, nadamo se da ćete uzeti u obzir
Davanje pokušava probati.

174
00:08:54,420 --> 00:08:56,085
Ja sam Kevin Schmid, a to je CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, ovo je početak
od pada.

177
00:09:00,790 --> 00:09:01,350
Žao mi je.

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

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

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

181
00:09:03,130 --> 00:09:03,950
>> Štrajk četiri.

182
00:09:03,950 --> 00:09:04,360
Ja sam vani.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Žao mi je za izradu osobu koja
mora urediti polude.

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

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

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

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

191
00:09:15,680 --> 00:09:16,280
>> ZVUČNIK 1: Bravo.

192
00:09:16,280 --> 00:09:17,530
To je jako dobro napravljena.

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