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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Néha, amikor az épület a
programot, érdemes kihasználni a

3
00:00:10,890 --> 00:00:13,190
adatstruktúra néven a szótárban.

4
00:00:13,190 --> 00:00:17,960
A szótár térképek gombok, melyek
általában a húrok, értékek, ints,

5
00:00:17,960 --> 00:00:21,900
karakter, a mutató néhány tárgyat,
amit akarunk.

6
00:00:21,900 --> 00:00:26,510
Olyan, mint a hagyományos szótárak
hogy a térkép szavakat a definíciók.

7
00:00:26,510 --> 00:00:29,440
>> Szótárak adja meg nekünk a
képes az adatok tárolására

8
00:00:29,440 --> 00:00:32,750
jár valami
és keresse fel később.

9
00:00:32,750 --> 00:00:36,620
Szóval hogyan lehet ténylegesen alkalmazni a
szótár, mondjuk, a C kód, hogy tudjuk

10
00:00:36,620 --> 00:00:38,460
használja valamelyik program?

11
00:00:38,460 --> 00:00:41,790
Nos, van egy csomó módon, hogy
sikerült végre egy szótárban.

12
00:00:41,790 --> 00:00:45,930
>> Az egyik, hogy jönne egy tömböt, hogy mi
dinamikusan újra méretű vagy mi jönne egy

13
00:00:45,930 --> 00:00:49,150
láncolt lista, hash tábla
vagy egy bináris fa.

14
00:00:49,150 --> 00:00:52,250
De bármit is úgy döntünk, mi kell
szem előtt tartva a hatékonyság és a

15
00:00:52,250 --> 00:00:54,300
teljesítménye a végrehajtás.

16
00:00:54,300 --> 00:00:57,930
Meg kell gondolni a használt algoritmus
beszúrni, és felnéz tételeket

17
00:00:57,930 --> 00:00:59,120
Adataink szerkezetét.

18
00:00:59,120 --> 00:01:03,060
>> Most tegyük fel, hogy mi
használni kívánt karakterláncokat kulcsokat.

19
00:01:03,060 --> 00:01:07,290
Beszéljünk egy lehetőség,
adatstruktúrát trie nevezzük.

20
00:01:07,290 --> 00:01:11,210
Tehát itt egy vizuális ábrázolás
A trie.

21
00:01:11,210 --> 00:01:14,590
>> Ahogy a kép is mutatja, a trie
egy fa adatstruktúra a

22
00:01:14,590 --> 00:01:16,050
csomópontok kapcsolódnak össze.

23
00:01:16,050 --> 00:01:19,420
Látjuk, hogy nincs egyértelműen gyökér
csomópont néhány link kiterjedő

24
00:01:19,420 --> 00:01:20,500
más csomópontok.

25
00:01:20,500 --> 00:01:23,040
De mit jelent az egyes node áll?

26
00:01:23,040 --> 00:01:26,700
Ha feltételezzük, hogy mi tárolására gombok
csak alfabetikus karaktereket,

27
00:01:26,700 --> 00:01:30,150
nem érdekel a nagybetűk,
itt van egy meghatározása a csomópont,

28
00:01:30,150 --> 00:01:31,100
elegendő.

29
00:01:31,100 --> 00:01:34,130
>> Egy objektum, melynek típusa struktúra
node két részből áll

30
00:01:34,130 --> 00:01:35,740
hívott adatok és a gyermekek.

31
00:01:35,740 --> 00:01:39,200
Már elhagyta az adatok egy részét, mint a comment
ki kell cserélni egy összetevő

32
00:01:39,200 --> 00:01:43,190
a nyilatkozatot struct csomópont
építeni egy C program.

33
00:01:43,190 --> 00:01:47,040
Az adatok egy része lehet egy csomópont
Logikai érték, hogy jelezze

34
00:01:47,040 --> 00:01:51,160
nem a csomópont képviseli a befejezése
A szótár gombot, vagy lehet, hogy egy

35
00:01:51,160 --> 00:01:54,240
string meghatározása
egy szó szerepel a szótárban.

36
00:01:54,240 --> 00:01:58,870
>> Majd egy mosolygó arc jelzi
ha az adatok van jelen egy csomópont.

37
00:01:58,870 --> 00:02:02,310
Van 26 eleme a
gyerekek tömb, egy index

38
00:02:02,310 --> 00:02:03,690
egy betű.

39
00:02:03,690 --> 00:02:06,570
Meglátjuk a jelentősége
Ennek hamarosan.

40
00:02:06,570 --> 00:02:10,759
>> Menjünk egy közelebbi pillantást a gyökér csomópont
a mi diagram, amelynek nincs adat

41
00:02:10,759 --> 00:02:14,740
társított, ahogy azt a
hiányában a mosolygó arc a

42
00:02:14,740 --> 00:02:16,110
adatok részét.

43
00:02:16,110 --> 00:02:19,910
A nyilak a kinyúló részei
A gyerekek array képviselnek non-csomópont

44
00:02:19,910 --> 00:02:21,640
mutatók más csomópontokhoz.

45
00:02:21,640 --> 00:02:25,500
Például, a nyíl kinyúló
A második elem a gyermekek

46
00:02:25,500 --> 00:02:28,400
képviseli a B betű
a szótárban kulcsot.

47
00:02:28,400 --> 00:02:31,920
És a nagyobb diagramon
névvel illetjük is a B.

48
00:02:31,920 --> 00:02:35,810
>> Megjegyezzük, hogy az ábrán a nagyobb, amikor
felhívni a mutatót egy másik csomópont, az

49
00:02:35,810 --> 00:02:39,100
nem számít, ha a nyílhegy
megfelel ennek a másik csomópont.

50
00:02:39,100 --> 00:02:43,850
A minta szótár trie tartalmaz
két szó, hogy és a zoom.

51
00:02:43,850 --> 00:02:47,040
Sétáljunk egy példán keresztül a
keresi fel adatokat a kulcsot.

52
00:02:47,040 --> 00:02:50,800
>> Tegyük fel akartuk nézni a
megfelelő értéket a kulcs fürdő.

53
00:02:50,800 --> 00:02:53,610
Kezdjük a felnéz
A gyökér csomópont.

54
00:02:53,610 --> 00:02:57,870
Akkor tegye meg az első betű a mi
kulcs, B, és megtalálni a megfelelő

55
00:02:57,870 --> 00:03:00,020
észrevenni a gyerekek tömbben.

56
00:03:00,020 --> 00:03:04,490
Figyeljük meg, hogy pontosan 26 foltok
a tömb, egy-egy levelét

57
00:03:04,490 --> 00:03:05,330
az ábécé.

58
00:03:05,330 --> 00:03:08,800
És mi lesz a foltok képviselik
az ábécé sorrendben.

59
00:03:08,800 --> 00:03:13,960
>> Majd nézd meg a második index, akkor,
indexe egy, B. Általában, ha azt

60
00:03:13,960 --> 00:03:17,990
Van néhány betű C is
lehet meghatározni a megfelelő helyen

61
00:03:17,990 --> 00:03:21,520
A gyerekek tömbben
a számítás, mint ez.

62
00:03:21,520 --> 00:03:25,140
Mi lehetett volna használni a nagyobb gyerekek
array, ha azt akartuk, hogy ajánlani felnéz a

63
00:03:25,140 --> 00:03:28,380
kulcsok szélesebb körű karakterekből
mint például az egész

64
00:03:28,380 --> 00:03:29,880
ASCII karakterkészlet.

65
00:03:29,880 --> 00:03:32,630
>> Ebben az esetben a mutató
a gyermekeink array at

66
00:03:32,630 --> 00:03:34,320
index egy nem null.

67
00:03:34,320 --> 00:03:36,600
Tehát fogjuk folytatni kell a munkát
fel a kulcsot fürdő.

68
00:03:36,600 --> 00:03:40,130
Ha valaha is találkozott a null pointer
a megfelelő helyszínen, a gyermekek

69
00:03:40,130 --> 00:03:43,230
array, amíg áthaladt a csomópontok,
akkor meg kell mondani, hogy mi

70
00:03:43,230 --> 00:03:45,630
nem talált semmit a kulcsot.

71
00:03:45,630 --> 00:03:49,370
>> Nos, mi lesz a második levél
kulcsfontosságú, A, és folytassa a következő

72
00:03:49,370 --> 00:03:52,400
mutatók egészen addig, amíg meg
elérjük a végét a gombot.

73
00:03:52,400 --> 00:03:56,530
Ha elérjük a végét, a kulcs nélküli
üti semmilyen zsákutcák, null mutató,

74
00:03:56,530 --> 00:03:59,730
mint a jelen esetben, akkor csak a
kell ellenőrizni, még egy dolog.

75
00:03:59,730 --> 00:04:02,110
Ez kulcsfontosságú valójában
a szótárban?

76
00:04:02,110 --> 00:04:07,660
>> Ha igen, akkor kell találni egy értéket, illetve a
mosolygó arc ikon a diagram, ahol a

77
00:04:07,660 --> 00:04:08,750
a szó véget ér.

78
00:04:08,750 --> 00:04:12,270
Ha van valami tárolt
az adatokat, akkor is vissza.

79
00:04:12,270 --> 00:04:16,500
Például, a kulcs állatkert nincs a
szótár, még akkor is lehetett volna

80
00:04:16,500 --> 00:04:19,810
elérte a végén ez a kulcs, anélkül, hogy
ütő egy null pointer, míg mi

81
00:04:19,810 --> 00:04:21,089
halad végig a trie.

82
00:04:21,089 --> 00:04:25,436
>> Ha megpróbáltuk felnéz a kulcsot fürdő, a
a második az utolsó csomópont tömb index,

83
00:04:25,436 --> 00:04:28,750
megfelel a H betű, akkor
tartottak null mutató.

84
00:04:28,750 --> 00:04:31,120
Tehát fürdő nem szerepel a szótárban.

85
00:04:31,120 --> 00:04:34,800
És így a trie egyedülálló abban, hogy a kulcsokat
soha nem explicit módon tárolja

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

87
00:04:36,650 --> 00:04:38,810
Szóval hogyan lehet beszúrni valamit
egy trie?

88
00:04:38,810 --> 00:04:41,780
>> Menjünk be a kulcsot
állatkert a mi trie.

89
00:04:41,780 --> 00:04:46,120
Ne feledje, hogy a mosolygó arc egy csomópont
lehet levelezési kódot egy egyszerű

90
00:04:46,120 --> 00:04:50,170
Logikai érték, amely jelzi, hogy állatkertben
van a szótárban, vagy lehetett

91
00:04:50,170 --> 00:04:53,710
felel meg több információt, hogy mi
kívánja társítani a kulcs állatkert,

92
00:04:53,710 --> 00:04:56,860
mint a meghatározása a
szó, vagy valami más.

93
00:04:56,860 --> 00:05:00,350
Bizonyos szempontból, a folyamat be
valamit a trie hasonló

94
00:05:00,350 --> 00:05:02,060
keres valamit a trie.

95
00:05:02,060 --> 00:05:05,720
>> Kezdjük a gyökér csomópont ismét
következő mutatókat megfelelő

96
00:05:05,720 --> 00:05:07,990
A leveleket a gombot.

97
00:05:07,990 --> 00:05:11,310
Szerencsére meg tudtuk követni mutatók
egészen addig, amíg elértük

98
00:05:11,310 --> 00:05:12,770
a végén a gombot.

99
00:05:12,770 --> 00:05:16,480
Mivel az állatkert a prefix szó
zoom, amely tagja a

100
00:05:16,480 --> 00:05:19,440
szótár, nem kell, hogy
osztják az új csomópontokat.

101
00:05:19,440 --> 00:05:23,140
>> Mi lehet módosítani a csomópontot, hogy jelezze, hogy a
útját karakter vezető

102
00:05:23,140 --> 00:05:25,360
ez jelenti a kulcsot a szótár.

103
00:05:25,360 --> 00:05:28,630
Most próbáljuk behelyezése
kulcsot BATH a trie.

104
00:05:28,630 --> 00:05:32,260
Kezdjük a gyökér csomópontot
és kövesse mutatók újra.

105
00:05:32,260 --> 00:05:35,620
De ebben a helyzetben, elérünk egy halott
vége előtt képesek vagyunk, hogy a

106
00:05:35,620 --> 00:05:36,940
vége a kulcs.

107
00:05:36,940 --> 00:05:40,980
Most akkor kell kiosztani néhány új
csomópontok kell hozzá egy új

108
00:05:40,980 --> 00:05:43,660
node minden fennmaradó
levél a gombot.

109
00:05:43,660 --> 00:05:46,740
>> Ebben az esetben, már csak be kell
kiosztani egy új csomópontot.

110
00:05:46,740 --> 00:05:50,590
Akkor kell, hogy a H-index
referencia az új csomópontot.

111
00:05:50,590 --> 00:05:54,070
Ismét lehet módosítani a csomópont
azt jelzi, hogy az út a karakter

112
00:05:54,070 --> 00:05:57,120
ami azt jelenti
kulcs a szótár.

113
00:05:57,120 --> 00:06:00,730
Nézzük oka az aszimptotikus
komplexitását eljárások ezen

114
00:06:00,730 --> 00:06:02,110
két művelet.

115
00:06:02,110 --> 00:06:06,420
>> Megjegyezzük, hogy mindkét esetben a számot
lépések algoritmus kellett hozzá

116
00:06:06,420 --> 00:06:09,470
arányos a számát
betűk a kulcsszó.

117
00:06:09,470 --> 00:06:10,220
Ez így van.

118
00:06:10,220 --> 00:06:13,470
Ha azt szeretné, hogy néz ki egy szót a
trie akkor csak meg kell halad végig

119
00:06:13,470 --> 00:06:17,100
a betűk egyenként, amíg nem vagy
eléri a végén a szó vagy

120
00:06:17,100 --> 00:06:19,060
zsákutcába a trie.

121
00:06:19,060 --> 00:06:22,470
>> És ha be szeretne szúrni egy kulcsot
érték pár egy trie a

122
00:06:22,470 --> 00:06:26,250
eljárás beszéltünk, a legrosszabb esetben
lesz akkor kiosztása egy új csomópont

123
00:06:26,250 --> 00:06:27,550
minden betű.

124
00:06:27,550 --> 00:06:31,290
És tegyük fel, hogy a kiosztás
állandó idő működését.

125
00:06:31,290 --> 00:06:35,850
Tehát, ha azt feltételezzük, hogy a kulcs hossza
által határolt fix konstans, mind

126
00:06:35,850 --> 00:06:39,400
behelyezése és felnéz állandó
üzemeltetését a trie.

127
00:06:39,400 --> 00:06:42,930
>> Ha nem teszik ezt a feltételezést, hogy az
a kulcs hosszát határolt fix

128
00:06:42,930 --> 00:06:46,650
állandó, akkor behelyezése és felnéz,
a legrosszabb esetben is lineáris a

129
00:06:46,650 --> 00:06:48,240
a kulcs hossza.

130
00:06:48,240 --> 00:06:51,800
Figyeljük meg, hogy a tételek száma a tárolt
A trie nem befolyásolja a megjelenés fel

131
00:06:51,800 --> 00:06:52,820
vagy behelyezésének időpontjával.

132
00:06:52,820 --> 00:06:55,360
Ez csak érintette a
a kulcs hossza.

133
00:06:55,360 --> 00:06:59,300
>> Ezzel szemben, a bejegyzések hozzáadását, mondjuk,
a hash tábla hajlamos arra, hogy

134
00:06:59,300 --> 00:07:01,250
jövő felnéz lassabb.

135
00:07:01,250 --> 00:07:04,520
Bár ez hangzik vonzó az első,
azt kell szem előtt tartani, hogy a

136
00:07:04,520 --> 00:07:08,740
kedvező aszimptotikus komplexitás nem
a gyakorlatban azt jelenti, hogy az adatok

137
00:07:08,740 --> 00:07:11,410
struktúra szükségszerűen
feddhetetlen.

138
00:07:11,410 --> 00:07:15,860
Azt is figyelembe kell venni, hogy az, hogy tárolja a
szó a trie amire szükségünk van, a legrosszabb

139
00:07:15,860 --> 00:07:19,700
esetben a csomópontok száma arányos
hogy a hossza a szó maga.

140
00:07:19,700 --> 00:07:21,880
>> Megpróbálja hajlanak arra, hogy a sok helyet.

141
00:07:21,880 --> 00:07:25,620
Ez ellentétben a hash tábla,
ahol csak szükség van egy új csomópont

142
00:07:25,620 --> 00:07:27,940
tárolni néhány kulcs-érték párt.

143
00:07:27,940 --> 00:07:31,370
Most ismét elméletben, nagy tér
fogyasztás nem tűnik, mint egy nagy

144
00:07:31,370 --> 00:07:34,620
foglalkoznak, különös tekintettel arra, hogy a modern
számítógépek gigabájt és

145
00:07:34,620 --> 00:07:36,180
gigabájt memória.

146
00:07:36,180 --> 00:07:39,200
De kiderül, hogy még mindig
aggódni a memória használat és

147
00:07:39,200 --> 00:07:42,540
szervezet kedvéért
teljesítmény, mivel a modern számítógépek

148
00:07:42,540 --> 00:07:46,960
van mechanizmusok meglétét a
Hood, hogy gyorsítsák fel memóriát.

149
00:07:46,960 --> 00:07:51,180
>> De ezek a mechanizmusok működnek a legjobban, ha
memória hozzáférések készülnek kompakt

150
00:07:51,180 --> 00:07:52,810
régiók és területek.

151
00:07:52,810 --> 00:07:55,910
És a csomópontok egy trie is laknak
bárhol, hogy a halom.

152
00:07:55,910 --> 00:07:58,390
De ezek a kompromisszumok
hogy figyelembe kell venni.

153
00:07:58,390 --> 00:08:01,440
>> Ne feledje, hogy, amikor kiválasztják egy adat
struktúra egy bizonyos feladat, mi

154
00:08:01,440 --> 00:08:04,420
meg kell gondolni, milyen
műveleteket az adatstruktúra kell

155
00:08:04,420 --> 00:08:07,140
támogatás és mennyi a teljesítménye
e, az egyes

156
00:08:07,140 --> 00:08:09,080
műveletek kérdésekben nekünk.

157
00:08:09,080 --> 00:08:11,300
Ezek a műveletek még
túlmutat csak

158
00:08:11,300 --> 00:08:13,430
alapvető felnéz és beillesztés.

159
00:08:13,430 --> 00:08:17,010
Tegyük fel, hogy volna végre egy kedves
Az automatikus teljes funkcionalitás, nagy

160
00:08:17,010 --> 00:08:18,890
mint a Google kereső nem.

161
00:08:18,890 --> 00:08:22,210
Ez azt jelenti, vissza a kulcsokat, és
potenciálisan értékek

162
00:08:22,210 --> 00:08:24,130
egy adott előtagot.

163
00:08:24,130 --> 00:08:27,050
>> A trie egyedülállóan hasznos
ehhez a művelethez.

164
00:08:27,050 --> 00:08:29,890
Ez egyszerűen halad végig
A trie minden karakterét

165
00:08:29,890 --> 00:08:30,950
előtag.

166
00:08:30,950 --> 00:08:33,559
Csakúgy, mint egy felnézni működés,
tudtuk követni mutatók

167
00:08:33,559 --> 00:08:35,400
karakterenként.

168
00:08:35,400 --> 00:08:38,659
Ezután, amikor megérkezik a végén a
prefix, tudtuk halad végig a

169
00:08:38,659 --> 00:08:42,049
fennmaradó részét az adatstruktúra
mivel bármely, a gombok túl

170
00:08:42,049 --> 00:08:43,980
Ezen a ponton van az előtag.

171
00:08:43,980 --> 00:08:47,670
>> Ez is könnyű megszerezni ezt a hirdetést
betűrendben, mivel a

172
00:08:47,670 --> 00:08:50,970
elemeit a gyerekek tömb
sorrendben betűrendben.

173
00:08:50,970 --> 00:08:54,420
Így remélhetőleg akkor figyelembe
adakozás próbál egy próbát.

174
00:08:54,420 --> 00:08:56,085
Schmid Kevin vagyok, és ez a CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, ez a kezdet
a csökkenés.

177
00:09:00,790 --> 00:09:01,350
Sajnálom.

178
00:09:01,350 --> 00:09:01,870
Bocsánat.

179
00:09:01,870 --> 00:09:02,480
Bocsánat.

180
00:09:02,480 --> 00:09:03,130
Bocsánat.

181
00:09:03,130 --> 00:09:03,950
>> Strike négy.

182
00:09:03,950 --> 00:09:04,360
Kint vagyok.

183
00:09:04,360 --> 00:09:05,280
Bocsánat.

184
00:09:05,280 --> 00:09:06,500
Bocsánat.

185
00:09:06,500 --> 00:09:07,490
Bocsánat.

186
00:09:07,490 --> 00:09:12,352
Elnézést, hogy a személy, aki
kell szerkeszteni ezt megbolondul.

187
00:09:12,352 --> 00:09:13,280
>> Bocsánat.

188
00:09:13,280 --> 00:09:13,880
Bocsánat.

189
00:09:13,880 --> 00:09:15,080
Bocsánat.

190
00:09:15,080 --> 00:09:15,680
Bocsánat.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Szép munka.

192
00:09:16,280 --> 00:09:17,530
Ez nagyon jól sikerült.

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