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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Joskus, kun rakennus
ohjelma, sinun kannattaa käyttää

3
00:00:10,890 --> 00:00:13,190
tietojen rakenne tunnetaan sanakirja.

4
00:00:13,190 --> 00:00:17,960
Sanakirja kartat avaimet, jotka ovat
yleensä jouset, arvoihin, ints,

5
00:00:17,960 --> 00:00:21,900
merkkiä, osoitin jonkin esineen,
mitä haluamme.

6
00:00:21,900 --> 00:00:26,510
Se on aivan kuin tavallinen sanakirjoja
että kartta sanansa määritelmiä.

7
00:00:26,510 --> 00:00:29,440
>> Sanakirjoja meille
kyky tallentaa tietoja

8
00:00:29,440 --> 00:00:32,750
liittyy jotain
ja etsiä se myöhemmin.

9
00:00:32,750 --> 00:00:36,620
Miten siis käytännössä soveltamaan
sanakirja vaikkapa C-koodia, että voimme

10
00:00:36,620 --> 00:00:38,460
käyttää yksi meidän ohjelmia?

11
00:00:38,460 --> 00:00:41,790
No, on olemassa paljon tapoja, jotka
voisimme toteuttaa sanakirja.

12
00:00:41,790 --> 00:00:45,930
>> Yhden, voisimme käyttää array että me
dynaamisesti uudelleen koko tai voisimme käyttää

13
00:00:45,930 --> 00:00:49,150
linkitetty lista, tiiviste
tai binääripuu.

14
00:00:49,150 --> 00:00:52,250
Mutta mitä me valitsemme, meidän pitäisi
olla tietoinen tehokkuuden ja

15
00:00:52,250 --> 00:00:54,300
suorituskykyä täytäntöönpanoa.

16
00:00:54,300 --> 00:00:57,930
Meidän pitäisi ajatella käytetty algoritmi
lisätä ja etsiä kohteet

17
00:00:57,930 --> 00:00:59,120
meidän tietorakenne.

18
00:00:59,120 --> 00:01:03,060
>> Nyt Oletetaan, että meillä
haluat käyttää merkkijonojen avaimina.

19
00:01:03,060 --> 00:01:07,290
Puhutaanpa yksi mahdollisuus,
data rakennetta kutsutaan triellä.

20
00:01:07,290 --> 00:01:11,210
Joten tässä on visuaalisesti
of trie.

21
00:01:11,210 --> 00:01:14,590
>> Kuten kuvasta voi päätellä, triellä
on puu datarakennetta

22
00:01:14,590 --> 00:01:16,050
solmut liittyvät toisiinsa.

23
00:01:16,050 --> 00:01:19,420
Näemme, että siellä on selvästi root
solmu joitakin yhteyksiä ulottuu

24
00:01:19,420 --> 00:01:20,500
muut solmut.

25
00:01:20,500 --> 00:01:23,040
Mutta mitä kukin solmu koostuu?

26
00:01:23,040 --> 00:01:26,700
Jos oletamme, että olemme tallentaa avaimet
vain kirjaimia ja

27
00:01:26,700 --> 00:01:30,150
emme välitä arvo,
tässä on määritelmä solmu, joka

28
00:01:30,150 --> 00:01:31,100
riittää.

29
00:01:31,100 --> 00:01:34,130
>> Objektin, jonka tyyppi on struct
solmulla on kaksi osaa

30
00:01:34,130 --> 00:01:35,740
nimeltään tietojen ja lapsia.

31
00:01:35,740 --> 00:01:39,200
Olemme jättäneet dataosa kommenttina
korvataan osa

32
00:01:39,200 --> 00:01:43,190
ilmoitusta, jos struct solmu on
sisällytetty C-ohjelma.

33
00:01:43,190 --> 00:01:47,040
Tieto-osa solmu voi olla
Boolean arvo, joka ilmaisee, onko

34
00:01:47,040 --> 00:01:51,160
ei solmu edustaa loppuun
sanakirjan avaimen tai se voi olla

35
00:01:51,160 --> 00:01:54,240
string edustavat määritelmän
sanan sanakirjasta.

36
00:01:54,240 --> 00:01:58,870
>> Käytämme hymiö kasvot osoittamaan
kun data on läsnä solmussa.

37
00:01:58,870 --> 00:02:02,310
On 26 elementtejä meidän
lasten joukko, yksi indeksi

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

39
00:02:03,690 --> 00:02:06,570
Näemme merkitystä
tämän pian.

40
00:02:06,570 --> 00:02:10,759
>> Mennään lähemmin juurisolmun
meidän kaaviossa, joka ei ole tietoja

41
00:02:10,759 --> 00:02:14,740
liittyy siihen, kuten on esitetty
Koska hymiö kasvot

42
00:02:14,740 --> 00:02:16,110
tieto-osan.

43
00:02:16,110 --> 00:02:19,910
Nuolet, jotka ulottuvat osista
lapset array edustavat ei-solmun

44
00:02:19,910 --> 00:02:21,640
viitteitä muihin solmuihin.

45
00:02:21,640 --> 00:02:25,500
Esimerkiksi nuoli ulottuu
toinen elementti lasten

46
00:02:25,500 --> 00:02:28,400
edustaa kirjain B
sanakirjasta näppäintä.

47
00:02:28,400 --> 00:02:31,920
Ja suurempi kaaviossa
merkitsemme sen B.

48
00:02:31,920 --> 00:02:35,810
>> Huomaa, että suurempi kaaviossa, kun
piirtää osoittimen toiseen solmuun, se

49
00:02:35,810 --> 00:02:39,100
ei ole väliä missä nuolenkärki
täyttää, että muut solmu.

50
00:02:39,100 --> 00:02:43,850
Meidän näyte sanakirja triestä sisältää
kaksi sanaa, jotka ja zoom.

51
00:02:43,850 --> 00:02:47,040
Käydään läpi esimerkki
etsii tietoja avaimen.

52
00:02:47,040 --> 00:02:50,800
>> Oletetaan halusimme etsiä
vastaava arvo avaimen kylpy.

53
00:02:50,800 --> 00:02:53,610
Aloitamme meidän look up
juurisolmusta.

54
00:02:53,610 --> 00:02:57,870
Sitten otamme ensimmäisen kirjaimen meidän
näppäintä, B, ja löytää vastaava

55
00:02:57,870 --> 00:03:00,020
Spot lapsemme array.

56
00:03:00,020 --> 00:03:04,490
Huomaa, että on olemassa täsmälleen 26 paikkoja
array, yksi kutakin kirjeellä

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

58
00:03:05,330 --> 00:03:08,800
Ja meillä on paikkoja edustavat
aakkosten järjestyksessä.

59
00:03:08,800 --> 00:03:13,960
>> Me tarkastelemme toisen indeksin sitten
indeksi yhdestä, B. Yleensä, jos me

60
00:03:13,960 --> 00:03:17,990
on joitakin kirjain C me
voisi määrittää vastaavan paikalla

61
00:03:17,990 --> 00:03:21,520
lapsissa array
laskelma näin.

62
00:03:21,520 --> 00:03:25,140
Olisimme voineet käyttää isommille lapsille
array jos halusimme tarjota look up

63
00:03:25,140 --> 00:03:28,380
näppäimet, joilla on laajempi valikoima merkkejä,
kuten koko

64
00:03:28,380 --> 00:03:29,880
ASCII-merkistön.

65
00:03:29,880 --> 00:03:32,630
>> Tässä tapauksessa osoitin
lapsemme array at

66
00:03:32,630 --> 00:03:34,320
indeksi yksi ei ole nolla.

67
00:03:34,320 --> 00:03:36,600
Niin me etsimme edelleen
ylös-näppäintä kylpyamme.

68
00:03:36,600 --> 00:03:40,130
Jos me koskaan kohdannut nollaosoittimen
oikeassa paikalla lapsia

69
00:03:40,130 --> 00:03:43,230
array kun me kulki solmut,
Sitten meidän täytyy sanoa, että me

70
00:03:43,230 --> 00:03:45,630
ei löytänyt mitään, että avain.

71
00:03:45,630 --> 00:03:49,370
>> Nyt otamme toisen kirjeellä
keskeisiä, ja jatka noudattaen

72
00:03:49,370 --> 00:03:52,400
viitteitä tällä tavoin, kunnes me
päähän keskeisiä.

73
00:03:52,400 --> 00:03:56,530
Jos me päähän avaimen ilman
lyödä mitään umpikujia, null osoittimia,

74
00:03:56,530 --> 00:03:59,730
kuten tässä tapauksessa, niin me vain
täytyy tarkistaa yksi asia.

75
00:03:59,730 --> 00:04:02,110
Onko tämä avain todella
sanakirjassa?

76
00:04:02,110 --> 00:04:07,660
>> Jos näin on, meidän pitäisi löytää arvo, hyvin
hymiö ilme meidän kaavio, jossa

77
00:04:07,660 --> 00:04:08,750
sana päättyy.

78
00:04:08,750 --> 00:04:12,270
Jos on jotain muuta tallennetaan
tietoa, niin voimme palauttaa sen.

79
00:04:12,270 --> 00:04:16,500
Esimerkiksi avain eläintarha ei ole
sanakirja, vaikka olisimme voineet

80
00:04:16,500 --> 00:04:19,810
lopussa tämän keskeisen ilman koskaan
lyömällä nollaosoittimen, kun me

81
00:04:19,810 --> 00:04:21,089
kerrata trien läpi.

82
00:04:21,089 --> 00:04:25,436
>> Jos yritimme etsiä avain kylpyamme,
toiseksi viimeinen solmun taulukkoindeksin,

83
00:04:25,436 --> 00:04:28,750
vastaava kirjain H, olisi
ovat pitäneet nollaosoittimen.

84
00:04:28,750 --> 00:04:31,120
Joten kylpy ei ole sanakirjassa.

85
00:04:31,120 --> 00:04:34,800
Ja niin trien on ainutlaatuinen siinä, että avaimet
ei koskaan nimenomaisesti tallennetaan

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

87
00:04:36,650 --> 00:04:38,810
Miten siis lisätä jotain
osaksi triestä?

88
00:04:38,810 --> 00:04:41,780
>> Katsotaanpa aseta avain
Eläintarha meidän triellä.

89
00:04:41,780 --> 00:04:46,120
Muista, että hymiö kasvot solmussa
voisi vastaavat koodin yksinkertainen

90
00:04:46,120 --> 00:04:50,170
Boolean joka osoittaa, että eläintarha
löytyy sanakirjasta tai se voi

91
00:04:50,170 --> 00:04:53,710
vastaavat enemmän tietoa, joka meillä
haluavat yhdistää avaimen eläintarha,

92
00:04:53,710 --> 00:04:56,860
kuten määritelmä
sana tai jotain muuta.

93
00:04:56,860 --> 00:05:00,350
Jollain tavalla, prosessi lisätä
jotain osaksi trien on samanlainen kuin

94
00:05:00,350 --> 00:05:02,060
etsii jotain triellä.

95
00:05:02,060 --> 00:05:05,720
>> Aloitamme juurisolmu uudelleen,
seuraavia viitteitä vastaa

96
00:05:05,720 --> 00:05:07,990
kirjaimet keskeisiä.

97
00:05:07,990 --> 00:05:11,310
Onneksi pystyimme seuraamaan viitteitä
aina kunnes saavuimme

98
00:05:11,310 --> 00:05:12,770
avaimen päätä.

99
00:05:12,770 --> 00:05:16,480
Koska eläintarha on etuliite sanan
zoom, joka on jäsenenä

100
00:05:16,480 --> 00:05:19,440
sanakirja, meidän ei tarvitse
jakaa uusia solmuja.

101
00:05:19,440 --> 00:05:23,140
>> Sitä voidaan muokata solmu osoittaa, että
polku merkkiä, joka johtaa

102
00:05:23,140 --> 00:05:25,360
se on keskeinen meidän sanakirja.

103
00:05:25,360 --> 00:05:28,630
Nyt, kokeile asettaa
avain kylvystä triessä.

104
00:05:28,630 --> 00:05:32,260
Aloitamme klo juurisolmu
ja seuraa viitteitä uudelleen.

105
00:05:32,260 --> 00:05:35,620
Mutta tässä tilanteessa, osuimme kuollut
päättyä ennen pystymme päästä

106
00:05:35,620 --> 00:05:36,940
avaimen päätä.

107
00:05:36,940 --> 00:05:40,980
Nyt meidän täytyy jakaa joitakin uusia
solmut tarvitse varata yhden uuden

108
00:05:40,980 --> 00:05:43,660
solmu jokaisen jäljellä
kirjeellä keskeisiä.

109
00:05:43,660 --> 00:05:46,740
>> Tässä tapauksessa meidän täytyy vain
jakaa yhden uuden solmun.

110
00:05:46,740 --> 00:05:50,590
Sitten meidän täytyy tehdä H-indeksi
viite tähän uuteen solmuun.

111
00:05:50,590 --> 00:05:54,070
Jälleen kerran voimme muuttaa solmun
osoittavat, että polku merkkiä

112
00:05:54,070 --> 00:05:57,120
mikä se edustaa
avain meidän sanakirja.

113
00:05:57,120 --> 00:06:00,730
Katsotaanpa päättelemään asymptoottinen
monimutkaisuus meidän menettelyt näitä

114
00:06:00,730 --> 00:06:02,110
kaksi operaatiota.

115
00:06:02,110 --> 00:06:06,420
>> Huomaamme, että molemmissa tapauksissa numero
vaiheiden algoritmimme kesti oli

116
00:06:06,420 --> 00:06:09,470
verrannollinen määrä
kirjaimet avainsanan.

117
00:06:09,470 --> 00:06:10,220
Aivan oikein.

118
00:06:10,220 --> 00:06:13,470
Kun haluat etsiä sanan
triestä sinun tarvitsee vain kerrata kautta

119
00:06:13,470 --> 00:06:17,100
kirjaimet yksitellen, kunnes joko
päähän sanan tai

120
00:06:17,100 --> 00:06:19,060
jemmassa triessä.

121
00:06:19,060 --> 00:06:22,470
>> Ja kun haluat lisätä avaimen
arvopari osaksi trie käyttäen

122
00:06:22,470 --> 00:06:26,250
menettelyn keskustelimme, pahimmassa tapauksessa
on sinulle jaettaessa uusi solmu

123
00:06:26,250 --> 00:06:27,550
jokaista kirjainta.

124
00:06:27,550 --> 00:06:31,290
Ja oletamme, että jako
on jatkuvasti ajan toimintaa.

125
00:06:31,290 --> 00:06:35,850
Jos siis oletetaan, että avaimen pituus on
jota rajoittaa kiinteä vakio, sekä

126
00:06:35,850 --> 00:06:39,400
sijoittelua ja etsiä ovat vakioita
aika operaatioita triellä.

127
00:06:39,400 --> 00:06:42,930
>> Jos emme tee tätä oletusta, että
avaimen pituus rajoittuu kiinteään

128
00:06:42,930 --> 00:06:46,650
vakio, niin sijoittelua ja etsiä,
pahimmassa tapauksessa, on lineaarinen

129
00:06:46,650 --> 00:06:48,240
avaimen pituus.

130
00:06:48,240 --> 00:06:51,800
Huomaa, että kohteiden määrää tallennettu
triessä ei vaikuta look up

131
00:06:51,800 --> 00:06:52,820
tai asetettiin paikoilleen.

132
00:06:52,820 --> 00:06:55,360
Se on vain vaikutti
avaimen pituus.

133
00:06:55,360 --> 00:06:59,300
>> Sen sijaan lisätään merkintöjä, vaikkapa
hash table taipumus tehdä

134
00:06:59,300 --> 00:07:01,250
tulevaisuudessa etsiä hitaammin.

135
00:07:01,250 --> 00:07:04,520
Vaikka tämä saattaa kuulostaa houkuttelevalta aluksi,
meidän pitäisi pitää mielessä, että

136
00:07:04,520 --> 00:07:08,740
suotuisa asymptoottinen monimutkaisuus ei
tarkoittaa, että käytännössä data

137
00:07:08,740 --> 00:07:11,410
rakenne on välttämättä
arvostelun yläpuolella.

138
00:07:11,410 --> 00:07:15,860
Meidän on myös otettava huomioon, että tallentaa
sana triestä tarvitsemme pahimmassa

139
00:07:15,860 --> 00:07:19,700
Tällöin solmujen verrannollinen
pituuden sana itse.

140
00:07:19,700 --> 00:07:21,880
>> Yrittää taipumus käyttää paljon tilaa.

141
00:07:21,880 --> 00:07:25,620
Se on toisin kuin hash-taulukko,
missä meidän tarvitsee vain yhden uuden solmun

142
00:07:25,620 --> 00:07:27,940
tallentaa joitakin keskeisiä arvopari.

143
00:07:27,940 --> 00:07:31,370
Nyt, jälleen teoriassa, suuri tila
kulutus ei tunnu iso

144
00:07:31,370 --> 00:07:34,620
käsitellä, varsinkin kun nykyaikaisen
tietokoneissa on gigatavua ja

145
00:07:34,620 --> 00:07:36,180
gigatavua muistia.

146
00:07:36,180 --> 00:07:39,200
Mutta näyttää siltä, ​​että meillä on vielä
murehtia muistin käyttöä ja

147
00:07:39,200 --> 00:07:42,540
organisaatio vuoksi
suorituskykyä, koska nykyiset tietokoneet

148
00:07:42,540 --> 00:07:46,960
käytössä järjestelyjä alle
huppu nopeuttaa muistin käyttöön.

149
00:07:46,960 --> 00:07:51,180
>> Mutta nämä mekanismit toimivat parhaiten, kun
muistin vierailuja tehdään kompakti

150
00:07:51,180 --> 00:07:52,810
alueita tai vyöhykkeitä.

151
00:07:52,810 --> 00:07:55,910
Ja solmut trien voisi sijaita
missä tahansa, että kasaan.

152
00:07:55,910 --> 00:07:58,390
Mutta nämä ovat kompromisseja
että meidän on pohdittava.

153
00:07:58,390 --> 00:08:01,440
>> Muista, että valitessaan tiedot
rakenne tiettyjä tehtäviä varten, me

154
00:08:01,440 --> 00:08:04,420
pitäisi ajatella siitä, millaisia
toiminnan tietorakenne on

155
00:08:04,420 --> 00:08:07,140
tukea ja kuinka paljon suorituskykyä
kunkin tällaisen

156
00:08:07,140 --> 00:08:09,080
toiminnot asioita meille.

157
00:08:09,080 --> 00:08:11,300
Nämä toiminnot voivat jopa
ulottua vain

158
00:08:11,300 --> 00:08:13,430
perus ilme ja paikoilleen.

159
00:08:13,430 --> 00:08:17,010
Oletetaan halusimme toteuttaa eräänlainen
Auto-kaikki toiminnot, paljon

160
00:08:17,010 --> 00:08:18,890
kuten Google-hakukone tekee.

161
00:08:18,890 --> 00:08:22,210
Eli palauttaa kaikki avaimet ja
mahdollisesti arvot, jotka

162
00:08:22,210 --> 00:08:24,130
on annettu etuliite.

163
00:08:24,130 --> 00:08:27,050
>> Triestä on ainutlaatuisen käyttökelpoinen
tähän operaatioon.

164
00:08:27,050 --> 00:08:29,890
Se on yksinkertaista iteroitava
triestä kunkin merkin

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

166
00:08:30,950 --> 00:08:33,559
Aivan kuten etsiä toimintaa,
voisimme seurata viitteitä

167
00:08:33,559 --> 00:08:35,400
merkki kerrallaan.

168
00:08:35,400 --> 00:08:38,659
Sitten, kun tulemme lopussa
etuliite, voisimme kerrata läpi

169
00:08:38,659 --> 00:08:42,049
jäljellä oleva osa datarakenteen
koska kaikki avaimet yli

170
00:08:42,049 --> 00:08:43,980
Tässä vaiheessa on etuliite.

171
00:08:43,980 --> 00:08:47,670
>> Se on myös helppo saada tietoja
aakkosjärjestyksessä vuodesta

172
00:08:47,670 --> 00:08:50,970
osia lasten array
ovat aakkosjärjestyksessä.

173
00:08:50,970 --> 00:08:54,420
Joten toivottavasti sinun harkita
antaminen yrittää yrittää.

174
00:08:54,420 --> 00:08:56,085
Olen Kevin Schmid, ja tämä on CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, tämä on alku
lasku.

177
00:09:00,790 --> 00:09:01,350
Olen pahoillani.

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

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

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

181
00:09:03,130 --> 00:09:03,950
>> Lakko neljä.

182
00:09:03,950 --> 00:09:04,360
Minä häivyn.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Sorry tehdä henkilö, joka
on muokata tätä hulluksi.

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

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

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

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

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Hyvin tehty.

192
00:09:16,280 --> 00:09:17,530
Se oli todella hyvin tehty.

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