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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Batzuetan, sortzerakoan bat
programa, agian garatu nahi duzun bat

3
00:00:10,890 --> 00:00:13,190
Datu egitura hiztegi bat bezala ezagutzen.

4
00:00:13,190 --> 00:00:17,960
Batek hiztegi mapak giltzak, diren
Normalean kateak, balioei, ints,

5
00:00:17,960 --> 00:00:21,900
karakteretan, objektu batzuk erakuslea,
edozein dela ere nahi dugu.

6
00:00:21,900 --> 00:00:26,510
Besterik hiztegiak arruntak bezala
mapa duten hitzen definizioak bidez.

7
00:00:26,510 --> 00:00:29,440
>> Hiztegiak ematen gurekin batera
informazioa gordetzeko gaitasuna

8
00:00:29,440 --> 00:00:32,750
zerbait lotutako
eta geroago, itxura gora.

9
00:00:32,750 --> 00:00:36,620
Beraz, nola ez benetan ezartzeko dugu bat
, esaten, C kodea hiztegi ahal dugun

10
00:00:36,620 --> 00:00:38,460
gure programa bat erabili?

11
00:00:38,460 --> 00:00:41,790
Beno, ez dira modu asko
hiztegi bat martxan izan dugu.

12
00:00:41,790 --> 00:00:45,930
>> Bat, array bat erabili izan dugu dugun
dinamikoki berriro tamaina edo bat erabili izan dugu

13
00:00:45,930 --> 00:00:49,150
lotutako zerrenda, hash taula
edo zuhaitz bitar bat.

14
00:00:49,150 --> 00:00:52,250
Baina edozein dela ere aukeratu dugu, behar dugu
izan eraginkortasuna mindful eta

15
00:00:52,250 --> 00:00:54,300
ezartzeko errendimendua.

16
00:00:54,300 --> 00:00:57,930
Erabilitako algoritmoa buruz pentsatu behar dugu
txertatzeko eta begiratu elementuak sartu

17
00:00:57,930 --> 00:00:59,120
Gure datu-egitura.

18
00:00:59,120 --> 00:01:03,060
>> Oraingoz, Demagun dugun
kateak teklak bezala erabili nahi.

19
00:01:03,060 --> 00:01:07,290
Dezagun aukera bat egin dezagun,
Datu egitura bat trie bat deitu.

20
00:01:07,290 --> 00:01:11,210
Hortaz, hona hemen bisuala ordezkaritza bat
trie baten.

21
00:01:11,210 --> 00:01:14,590
>> Irudian dioen bezala, trie
zuhaitz datu-egitura bat da,

22
00:01:14,590 --> 00:01:16,050
nodes lotuta elkarrekin.

23
00:01:16,050 --> 00:01:19,420
Ikusten dugu ez dagoela argi erro bat
lotura batzuk zabalduz Nodo

24
00:01:19,420 --> 00:01:20,500
beste nodo.

25
00:01:20,500 --> 00:01:23,040
Baina zer datza nodo bakoitzean?

26
00:01:23,040 --> 00:01:26,700
Duten gakoak gordetzeko ari gara bere gain hartzen badugu
karaktere alfabetiko bakarra, eta honekin

27
00:01:26,700 --> 00:01:30,150
ez dugu kapitalizazio buruzko zaintzeko,
hemen nodo baten definizio hori

28
00:01:30,150 --> 00:01:31,100
nahikoa izango da.

29
00:01:31,100 --> 00:01:34,130
>> Objektu bat bere motako struct da
nodo bi zati ditu

30
00:01:34,130 --> 00:01:35,740
datuak eta haurrak deitu.

31
00:01:35,740 --> 00:01:39,200
Datuen zatia utzi dugu iruzkin bat bezala
haien tokia osagai batek

32
00:01:39,200 --> 00:01:43,190
deklarazio denean egitura nodo da
C programa batean sartu.

33
00:01:43,190 --> 00:01:47,040
Datuak nodo baten zati bat izan liteke
Balio boolearrak honakoa adierazten du: edo

34
00:01:47,040 --> 00:01:51,160
ez nodo amaitu adierazten
hiztegi gako baten edo bat izango da agian

35
00:01:51,160 --> 00:01:54,240
katea definizioa ordezkari
Hiztegian hitz baten.

36
00:01:54,240 --> 00:01:58,870
>> Aurpegi alai bat erabiliko dugu adierazi
datuak nodo bat presente dagoenean.

37
00:01:58,870 --> 00:02:02,310
Daude 26 elementu gure
haurrak array, indize bat

38
00:02:02,310 --> 00:02:03,690
hizki bakoitzeko.

39
00:02:03,690 --> 00:02:06,570
Ikusiko dugu garrantzia
hau laster neurtzen.

40
00:02:06,570 --> 00:02:10,759
>> Gaitezen erroa nodoaren hurbilago itxura bat
Diagraman, zein datu ez du

41
00:02:10,759 --> 00:02:14,740
horri lotuta, adierazten duen bezala
aurpegieren aurpegia eza

42
00:02:14,740 --> 00:02:16,110
datuen zatia.

43
00:02:16,110 --> 00:02:19,910
Geziak atalen zabalduz
haurrek array ez nodo irudikatzeko

44
00:02:19,910 --> 00:02:21,640
beste nodo erakusleak.

45
00:02:21,640 --> 00:02:25,500
Adibidez, gezi zabalduz
haurrak bigarren elementua

46
00:02:25,500 --> 00:02:28,400
B gutunean adierazten
hiztegi gako bat.

47
00:02:28,400 --> 00:02:31,920
Eta handiago diagrama batean
etiketatuko dugu B. batekin

48
00:02:31,920 --> 00:02:35,810
>> Kontuan handiagoa diagrama hori, noiz dugu
nodo beste erakuslea bat marraztu, hura

49
00:02:35,810 --> 00:02:39,100
ez du axola non gezi du
beste nodo hori betetzen.

50
00:02:39,100 --> 00:02:43,850
Gure lagina hiztegi trie dauka
Bi hitz, hori eta zoom.

51
00:02:43,850 --> 00:02:47,040
Goazen adibide baten bidez
Datu gora begiratzen gako baten.

52
00:02:47,040 --> 00:02:50,800
>> Suposatzen begiratu nahi izan dugu
dagokion balioa gako bainu.

53
00:02:50,800 --> 00:02:53,610
Gure begirada hasiko dugu sortu
erroko nodoa.

54
00:02:53,610 --> 00:02:57,870
Ondoren, gure lehenengo letra hartu dugu
Giltza, B, eta dagokion jakiteko

55
00:02:57,870 --> 00:03:00,020
gure seme array gelditzea.

56
00:03:00,020 --> 00:03:04,490
Nabarituko daudela zehazki 26 lekuak
array, gutuna bakoitzeko bat in

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

58
00:03:05,330 --> 00:03:08,800
Eta izan dugu lekuak ordezkatzen
alfabetoaren letrak ordenean.

59
00:03:08,800 --> 00:03:13,960
>> Egingo bigarren indizearen begiratzen dugu, ondoren,
indize bat, B. Oro har, eta badugu

60
00:03:13,960 --> 00:03:17,990
zenbait hizki C dugu
dagokion lekua zehaztu ezin

61
00:03:17,990 --> 00:03:21,520
haurrak array erabiliz
honen antzeko kalkulu bat.

62
00:03:21,520 --> 00:03:25,140
Haurrak handiago bat erabili ahal dugu
begirada osatzen eskaini nahi array badugu

63
00:03:25,140 --> 00:03:28,380
karaktere sorta zabalago bat giltzak,
esaterako osoan bezala

64
00:03:28,380 --> 00:03:29,880
ASCII karaktere-jokoa.

65
00:03:29,880 --> 00:03:32,630
>> Kasu honetan, erakuslea
gure haurrei array

66
00:03:32,630 --> 00:03:34,320
indize bat da, ez da nulua.

67
00:03:34,320 --> 00:03:36,600
Beraz, bila jarraituko dugu
Funtsezko bainu sortu.

68
00:03:36,600 --> 00:03:40,130
Inoiz nulua erakuslea topo egin dugu bada
haurrak in Leku egokia

69
00:03:40,130 --> 00:03:43,230
array nodoak zeharkatu dugun bitartean,
Orduz dugula esan behar dugu

70
00:03:43,230 --> 00:03:45,630
ezin gako horrentzako ezer aurkitu.

71
00:03:45,630 --> 00:03:49,370
>> Orain, bigarren gutunean hartu dugu
gure gakoa, A, eta jarraitu ondorengo

72
00:03:49,370 --> 00:03:52,400
modu horretan, erakusleak arte
Gure funtsezko amaieran iritsiko.

73
00:03:52,400 --> 00:03:56,530
Gakoa amaieran iritsiko gara gabe bada
muturretan hildako edozein sakatuz, null erakusleak,

74
00:03:56,530 --> 00:03:59,730
gertatzen da hemen bezala, orduan guk bakarrik
gauza bat gehiago begiratu behar.

75
00:03:59,730 --> 00:04:02,110
Gako hau da, benetan
hiztegian?

76
00:04:02,110 --> 00:04:07,660
>> Hala bada, balio bat aurkitu beharko dugu, ongi bat
aurpegia smiley gure diagrama ikono non

77
00:04:07,660 --> 00:04:08,750
hitza bukatzen da.

78
00:04:08,750 --> 00:04:12,270
Bada ez beste zerbait gordetzen da
Datuak, ondoren, itzuli ahal izango dugu.

79
00:04:12,270 --> 00:04:16,500
Adibidez, funtsezko zoologiko ez da horretan
hiztegia, nahiz eta izan dugu

80
00:04:16,500 --> 00:04:19,810
Giltza honen amaieran iritsi inoiz gabe
null erakuslea sakatuz, berriz dugu

81
00:04:19,810 --> 00:04:21,089
trie bidez batetik bestera joateko.

82
00:04:21,089 --> 00:04:25,436
>> Funtsezko bainu aurkitu, saiatu ginen bada
azken nodoaren array indizea bigarren,

83
00:04:25,436 --> 00:04:28,750
letra H dagokiona, litzateke
atxiki null erakuslea.

84
00:04:28,750 --> 00:04:31,120
Beraz, bainu ez dago hiztegian.

85
00:04:31,120 --> 00:04:34,800
Eta beraz trie bat berezia dela gakoak in
dira inoiz esplizituki gordeta

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

87
00:04:36,650 --> 00:04:38,810
Beraz, nola ez zerbait txertatu dugu
trie batean?

88
00:04:38,810 --> 00:04:41,780
>> Dezagun txertatzeko gakoa
gure trie sartu zoo.

89
00:04:41,780 --> 00:04:46,120
Gogoratu nodo batean aurpegi alai bat
duen kode in dagozkio soil batera

90
00:04:46,120 --> 00:04:50,170
Balio boolearrak zoologiko duten adierazteko
hiztegian edo izan liteke

91
00:04:50,170 --> 00:04:53,710
Informazio gehiago dagozkion dugu
hemen gako zoologiko lotu nahi,

92
00:04:53,710 --> 00:04:56,860
definizioa bezalako
hitza edo beste zerbait.

93
00:04:56,860 --> 00:05:00,350
Nolabait, prozesuan sartu
trie batean zerbait antzekoa da

94
00:05:00,350 --> 00:05:02,060
trie batean zerbait gora begiratzen.

95
00:05:02,060 --> 00:05:05,720
>> Erroko nodoa hasiko gara berriro,
honako erakusleak dagokion

96
00:05:05,720 --> 00:05:07,990
Gure funtsezko hizkiak.

97
00:05:07,990 --> 00:05:11,310
Zorionez, erakusleak jarraitu ahal izan dugu
modu guztiak gara iritsi arte

98
00:05:11,310 --> 00:05:12,770
gakoa amaieran.

99
00:05:12,770 --> 00:05:16,480
Geroztik Zoo hitzaren aurrizki bat da
zoom, eta horrek kide da

100
00:05:16,480 --> 00:05:19,440
hiztegi, ez dugu behar den
edozein nodo berriak esleitzeko.

101
00:05:19,440 --> 00:05:23,140
>> Nodoa aldatu ahal izango dugu, adierazten duten
liderra karaktere bidea

102
00:05:23,140 --> 00:05:25,360
gure hiztegian gako bat irudikatzen du.

103
00:05:25,360 --> 00:05:28,630
Orain, saiatu txertatu du
Giltza trie sartu BATH.

104
00:05:28,630 --> 00:05:32,260
Egingo erroko nodoa etan hasiko gara
eta erakusleak jarraitu berriro.

105
00:05:32,260 --> 00:05:35,620
Baina egoera horretan, hildako bat hit dugu
amaitzeko iristeko gai gara aurretik

106
00:05:35,620 --> 00:05:36,940
gakoa amaieran.

107
00:05:36,940 --> 00:05:40,980
Orain, batzuk berriak esleitu behar dugu
nodo berri bat esleitu beharko

108
00:05:40,980 --> 00:05:43,660
Gainerako bakoitzeko nodo
gure teklaren hizkia.

109
00:05:43,660 --> 00:05:46,740
>> Kasu honetan, behar besterik ez dugu
nodo berri bat esleitu.

110
00:05:46,740 --> 00:05:50,590
Gero H indizearen egin behar dugu
nodo berri honi erreferentzia.

111
00:05:50,590 --> 00:05:54,070
Berriro ere, nodo aldatzeko dezakegu
adierazten duten pertsonaiak bidea

112
00:05:54,070 --> 00:05:57,120
da liderra adierazten batean
gure hiztegi gakoa.

113
00:05:57,120 --> 00:06:00,730
Dezagun arrazoia asintotikoak buruzko
gure hauentzako prozedurak konplexutasuna

114
00:06:00,730 --> 00:06:02,110
bi eragiketa.

115
00:06:02,110 --> 00:06:06,420
>> Nabarituko dugu bi kasuetan kopuruaren
Urratsak gure algoritmoa hartu zuten

116
00:06:06,420 --> 00:06:09,470
kopuruaren proportzionala
keyword letrak.

117
00:06:09,470 --> 00:06:10,220
Hori da.

118
00:06:10,220 --> 00:06:13,470
Hitz bat bilatzeko batean nahi baduzu
trie besterik bidez batetik bestera joateko behar duzun

119
00:06:13,470 --> 00:06:17,100
letrak banan-banan arte bai
Hitz amaieran edo iristeko

120
00:06:17,100 --> 00:06:19,060
hildako amaiera hit trie batean.

121
00:06:19,060 --> 00:06:22,470
>> Eta denean gako bat txertatu nahi duzu
balioa bikotea trie batean erabiliz

122
00:06:22,470 --> 00:06:26,250
prozedura aztertu ditugu, kasu txarrenean
egingo nodoaren esleitzean duzu

123
00:06:26,250 --> 00:06:27,550
letrak idazteko.

124
00:06:27,550 --> 00:06:31,290
Eta esleipena dela suposatuko dugu
denbora etengabeko eragiketa bat da.

125
00:06:31,290 --> 00:06:35,850
Gako luzera dela suposatuko dugu hala bada
konstante finkoa, bai mugatzen

126
00:06:35,850 --> 00:06:39,400
txertatzeko eta begiratu etengabeak dira
denbora trie baterako eragiketak.

127
00:06:39,400 --> 00:06:42,930
>> Ez badugu egin hipotesi hori
gako luzera da finko bat mugatzen

128
00:06:42,930 --> 00:06:46,650
etengabea, eta gero txertatzeko eta begiratu,
Kasu txarrenean, ari diren lineal

129
00:06:46,650 --> 00:06:48,240
Gakoaren luzera.

130
00:06:48,240 --> 00:06:51,800
Nabarituko elementu kopurua gordetzen
trie batean ez du itxura eraginik sortu

131
00:06:51,800 --> 00:06:52,820
edo txertatzeko denbora.

132
00:06:52,820 --> 00:06:55,360
Honez bakarrik eragin
Gakoaren luzera.

133
00:06:55,360 --> 00:06:59,300
>> Aitzitik, sarrerak gehituz, esan,
hash taula bat egiteko joera

134
00:06:59,300 --> 00:07:01,250
etorkizunari begiratu motelagoa.

135
00:07:01,250 --> 00:07:04,520
Hau erakargarria soinu bitartean eta lehen,
Kontuan hartu behar dugu mantentzeko a

136
00:07:04,520 --> 00:07:08,740
aldeko asintotikoak konplexutasuna ez du
esan nahi praktikan datuen

137
00:07:08,740 --> 00:07:11,410
egitura dela nahitaez
reproach haratago.

138
00:07:11,410 --> 00:07:15,860
Ere gorde kontuan hartu behar dugu bat
trie bat behar dugu, txarrenean hitza

139
00:07:15,860 --> 00:07:19,700
kasuan, nodo kopurua proportzionala
hitza bera luzera.

140
00:07:19,700 --> 00:07:21,880
>> Saiatzen ohi espazio asko erabiltzeko.

141
00:07:21,880 --> 00:07:25,620
Duen hash taula bat kontrastea da,
non soilik nodo berri bat behar dugu

142
00:07:25,620 --> 00:07:27,940
Zenbait gako-balioa bikotea gordetzeko.

143
00:07:27,940 --> 00:07:31,370
Orain, berriro ere teorian, espazio handi
kontsumoak ez du handi bat bezala dirudi

144
00:07:31,370 --> 00:07:34,620
aurre egiteko, are gutxiago, moderno
ordenagailuak gigabyte eta

145
00:07:34,620 --> 00:07:36,180
memoria gigabyte.

146
00:07:36,180 --> 00:07:39,200
Baina bihurtzen da hori oraindik ez dugu
memoria erabilera eta kezkatu

147
00:07:39,200 --> 00:07:42,540
mesedetan erakundea
errendimendua, geroztik ordenagailuak modernoaren

148
00:07:42,540 --> 00:07:46,960
pean bildu diren mekanismoak izan
kanpaia azkartzeko memoria sarrera.

149
00:07:46,960 --> 00:07:51,180
>> Baina mekanismo horiek lan onena
memoria sarbideak dira trinkoa egin

150
00:07:51,180 --> 00:07:52,810
eskualde edo arloak.

151
00:07:52,810 --> 00:07:55,910
Eta trie baten nodo bizi liteke
zeure duen edozein lekutan.

152
00:07:55,910 --> 00:07:58,390
Baina horiek ez dira merkataritza-off
duten kontuan hartu behar dugu.

153
00:07:58,390 --> 00:08:01,440
>> Gogoratu, Datuak bat aukeratzerakoan
Zeregin jakin baterako egitura, dugu

154
00:08:01,440 --> 00:08:04,420
pentsatu behar da zer motatako
eragiketak datuak egitura behar

155
00:08:04,420 --> 00:08:07,140
laguntza eta zenbat errendimendua
horietako bakoitzaren

156
00:08:07,140 --> 00:08:09,080
eragiketak gurekin gaietan.

157
00:08:09,080 --> 00:08:11,300
Eragiketa horiek, are gehiago, baliteke
besterik haratago hedatzen

158
00:08:11,300 --> 00:08:13,430
oinarrizko look up eta txertatzeko.

159
00:08:13,430 --> 00:08:17,010
Suposatzen moduko bat martxan jartzea nahi izan dugu
auto-osoa funtzionaltasuna, askoz

160
00:08:17,010 --> 00:08:18,890
bezalako Google bilatzailea du.

161
00:08:18,890 --> 00:08:22,210
Hau da, itzultzeko tekla guztiak eta
balioak potentzialki horrek

162
00:08:22,210 --> 00:08:24,130
aurrizki jakin bat dute.

163
00:08:24,130 --> 00:08:27,050
>> Trie bakarrean erabilgarria da
eragiketa honetarako.

164
00:08:27,050 --> 00:08:29,890
Da erraza bidez batetik bestera joateko
izaera bakoitzeko trie

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

166
00:08:30,950 --> 00:08:33,559
Just look up eragiketa bat bezala,
erakusleak jarraitu ahal izan genuen

167
00:08:33,559 --> 00:08:35,400
pertsonaia by pertsonaia.

168
00:08:35,400 --> 00:08:38,659
Orduan, noiz iritsiko da amaieran dugu
aurrizkia, bidez batetik bestera joateko genezake

169
00:08:38,659 --> 00:08:42,049
Gainerako datuak egituraren zati
giltzarrietako edozein haratago geroztik

170
00:08:42,049 --> 00:08:43,980
Puntu honetan izan aurrizkia.

171
00:08:43,980 --> 00:08:47,670
>> Halaber Erraza da zerrenda honetan lortzea
geroztik ordena alfabetikoan du

172
00:08:47,670 --> 00:08:50,970
haurrak array elementuak
alfabetikoki ordenatuta daude.

173
00:08:50,970 --> 00:08:54,420
Beraz, espero dugu kontuan hartu beharko duzu
emanez saiatu saiatzen.

174
00:08:54,420 --> 00:08:56,085
Naiz Kevin Schmid, eta hau da CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, hau hasiera da
gainbehera.

177
00:09:00,790 --> 00:09:01,350
Sentitzen dut.

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

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

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

181
00:09:03,130 --> 00:09:03,950
>> Greba lau.

182
00:09:03,950 --> 00:09:04,360
Irten naiz.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Pertsonaren egiteko Barkatu nor
editatzeko honetan joan crazy ditu.

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

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

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

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

191
00:09:15,680 --> 00:09:16,280
>> HIZLARIA 1: Ongi egina.

192
00:09:16,280 --> 00:09:17,530
Benetan ondo egina zen.

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