>> KEVIN SCHMID: Batzuetan, sortzerakoan bat programa, agian garatu nahi duzun bat
Datu egitura hiztegi bat bezala ezagutzen.
Batek hiztegi mapak giltzak, diren Normalean kateak, balioei, ints,
karakteretan, objektu batzuk erakuslea, edozein dela ere nahi dugu.
Besterik hiztegiak arruntak bezala mapa duten hitzen definizioak bidez.
>> Hiztegiak ematen gurekin batera informazioa gordetzeko gaitasuna
zerbait lotutako eta geroago, itxura gora.
Beraz, nola ez benetan ezartzeko dugu bat , esaten, C kodea hiztegi ahal dugun
gure programa bat erabili?
Beno, ez dira modu asko hiztegi bat martxan izan dugu.
>> Bat, array bat erabili izan dugu dugun dinamikoki berriro tamaina edo bat erabili izan dugu
lotutako zerrenda, hash taula edo zuhaitz bitar bat.
Baina edozein dela ere aukeratu dugu, behar dugu izan eraginkortasuna mindful eta
ezartzeko errendimendua.
Erabilitako algoritmoa buruz pentsatu behar dugu txertatzeko eta begiratu elementuak sartu
Gure datu-egitura.
>> Oraingoz, Demagun dugun kateak teklak bezala erabili nahi.
Dezagun aukera bat egin dezagun, Datu egitura bat trie bat deitu.
Hortaz, hona hemen bisuala ordezkaritza bat trie baten.
>> Irudian dioen bezala, trie zuhaitz datu-egitura bat da,
nodes lotuta elkarrekin.
Ikusten dugu ez dagoela argi erro bat lotura batzuk zabalduz Nodo
beste nodo.
Baina zer datza nodo bakoitzean?
Duten gakoak gordetzeko ari gara bere gain hartzen badugu karaktere alfabetiko bakarra, eta honekin
ez dugu kapitalizazio buruzko zaintzeko, hemen nodo baten definizio hori
nahikoa izango da.
>> Objektu bat bere motako struct da nodo bi zati ditu
datuak eta haurrak deitu.
Datuen zatia utzi dugu iruzkin bat bezala haien tokia osagai batek
deklarazio denean egitura nodo da C programa batean sartu.
Datuak nodo baten zati bat izan liteke Balio boolearrak honakoa adierazten du: edo
ez nodo amaitu adierazten hiztegi gako baten edo bat izango da agian
katea definizioa ordezkari Hiztegian hitz baten.
>> Aurpegi alai bat erabiliko dugu adierazi datuak nodo bat presente dagoenean.
Daude 26 elementu gure haurrak array, indize bat
hizki bakoitzeko.
Ikusiko dugu garrantzia hau laster neurtzen.
>> Gaitezen erroa nodoaren hurbilago itxura bat Diagraman, zein datu ez du
horri lotuta, adierazten duen bezala aurpegieren aurpegia eza
datuen zatia.
Geziak atalen zabalduz haurrek array ez nodo irudikatzeko
beste nodo erakusleak.
Adibidez, gezi zabalduz haurrak bigarren elementua
B gutunean adierazten hiztegi gako bat.
Eta handiago diagrama batean etiketatuko dugu B. batekin
>> Kontuan handiagoa diagrama hori, noiz dugu nodo beste erakuslea bat marraztu, hura
ez du axola non gezi du beste nodo hori betetzen.
Gure lagina hiztegi trie dauka Bi hitz, hori eta zoom.
Goazen adibide baten bidez Datu gora begiratzen gako baten.
>> Suposatzen begiratu nahi izan dugu dagokion balioa gako bainu.
Gure begirada hasiko dugu sortu erroko nodoa.
Ondoren, gure lehenengo letra hartu dugu Giltza, B, eta dagokion jakiteko
gure seme array gelditzea.
Nabarituko daudela zehazki 26 lekuak array, gutuna bakoitzeko bat in
alfabetoa.
Eta izan dugu lekuak ordezkatzen alfabetoaren letrak ordenean.
>> Egingo bigarren indizearen begiratzen dugu, ondoren, indize bat, B. Oro har, eta badugu
zenbait hizki C dugu dagokion lekua zehaztu ezin
haurrak array erabiliz honen antzeko kalkulu bat.
Haurrak handiago bat erabili ahal dugu begirada osatzen eskaini nahi array badugu
karaktere sorta zabalago bat giltzak, esaterako osoan bezala
ASCII karaktere-jokoa.
>> Kasu honetan, erakuslea gure haurrei array
indize bat da, ez da nulua.
Beraz, bila jarraituko dugu Funtsezko bainu sortu.
Inoiz nulua erakuslea topo egin dugu bada haurrak in Leku egokia
array nodoak zeharkatu dugun bitartean, Orduz dugula esan behar dugu
ezin gako horrentzako ezer aurkitu.
>> Orain, bigarren gutunean hartu dugu gure gakoa, A, eta jarraitu ondorengo
modu horretan, erakusleak arte Gure funtsezko amaieran iritsiko.
Gakoa amaieran iritsiko gara gabe bada muturretan hildako edozein sakatuz, null erakusleak,
gertatzen da hemen bezala, orduan guk bakarrik gauza bat gehiago begiratu behar.
Gako hau da, benetan hiztegian?
>> Hala bada, balio bat aurkitu beharko dugu, ongi bat aurpegia smiley gure diagrama ikono non
hitza bukatzen da.
Bada ez beste zerbait gordetzen da Datuak, ondoren, itzuli ahal izango dugu.
Adibidez, funtsezko zoologiko ez da horretan hiztegia, nahiz eta izan dugu
Giltza honen amaieran iritsi inoiz gabe null erakuslea sakatuz, berriz dugu
trie bidez batetik bestera joateko.
>> Funtsezko bainu aurkitu, saiatu ginen bada azken nodoaren array indizea bigarren,
letra H dagokiona, litzateke atxiki null erakuslea.
Beraz, bainu ez dago hiztegian.
Eta beraz trie bat berezia dela gakoak in dira inoiz esplizituki gordeta
Datuen egitura.
Beraz, nola ez zerbait txertatu dugu trie batean?
>> Dezagun txertatzeko gakoa gure trie sartu zoo.
Gogoratu nodo batean aurpegi alai bat duen kode in dagozkio soil batera
Balio boolearrak zoologiko duten adierazteko hiztegian edo izan liteke
Informazio gehiago dagozkion dugu hemen gako zoologiko lotu nahi,
definizioa bezalako hitza edo beste zerbait.
Nolabait, prozesuan sartu trie batean zerbait antzekoa da
trie batean zerbait gora begiratzen.
>> Erroko nodoa hasiko gara berriro, honako erakusleak dagokion
Gure funtsezko hizkiak.
Zorionez, erakusleak jarraitu ahal izan dugu modu guztiak gara iritsi arte
gakoa amaieran.
Geroztik Zoo hitzaren aurrizki bat da zoom, eta horrek kide da
hiztegi, ez dugu behar den edozein nodo berriak esleitzeko.
>> Nodoa aldatu ahal izango dugu, adierazten duten liderra karaktere bidea
gure hiztegian gako bat irudikatzen du.
Orain, saiatu txertatu du Giltza trie sartu BATH.
Egingo erroko nodoa etan hasiko gara eta erakusleak jarraitu berriro.
Baina egoera horretan, hildako bat hit dugu amaitzeko iristeko gai gara aurretik
gakoa amaieran.
Orain, batzuk berriak esleitu behar dugu nodo berri bat esleitu beharko
Gainerako bakoitzeko nodo gure teklaren hizkia.
>> Kasu honetan, behar besterik ez dugu nodo berri bat esleitu.
Gero H indizearen egin behar dugu nodo berri honi erreferentzia.
Berriro ere, nodo aldatzeko dezakegu adierazten duten pertsonaiak bidea
da liderra adierazten batean gure hiztegi gakoa.
Dezagun arrazoia asintotikoak buruzko gure hauentzako prozedurak konplexutasuna
bi eragiketa.
>> Nabarituko dugu bi kasuetan kopuruaren Urratsak gure algoritmoa hartu zuten
kopuruaren proportzionala keyword letrak.
Hori da.
Hitz bat bilatzeko batean nahi baduzu trie besterik bidez batetik bestera joateko behar duzun
letrak banan-banan arte bai Hitz amaieran edo iristeko
hildako amaiera hit trie batean.
>> Eta denean gako bat txertatu nahi duzu balioa bikotea trie batean erabiliz
prozedura aztertu ditugu, kasu txarrenean egingo nodoaren esleitzean duzu
letrak idazteko.
Eta esleipena dela suposatuko dugu denbora etengabeko eragiketa bat da.
Gako luzera dela suposatuko dugu hala bada konstante finkoa, bai mugatzen
txertatzeko eta begiratu etengabeak dira denbora trie baterako eragiketak.
>> Ez badugu egin hipotesi hori gako luzera da finko bat mugatzen
etengabea, eta gero txertatzeko eta begiratu, Kasu txarrenean, ari diren lineal
Gakoaren luzera.
Nabarituko elementu kopurua gordetzen trie batean ez du itxura eraginik sortu
edo txertatzeko denbora.
Honez bakarrik eragin Gakoaren luzera.
>> Aitzitik, sarrerak gehituz, esan, hash taula bat egiteko joera
etorkizunari begiratu motelagoa.
Hau erakargarria soinu bitartean eta lehen, Kontuan hartu behar dugu mantentzeko a
aldeko asintotikoak konplexutasuna ez du esan nahi praktikan datuen
egitura dela nahitaez reproach haratago.
Ere gorde kontuan hartu behar dugu bat trie bat behar dugu, txarrenean hitza
kasuan, nodo kopurua proportzionala hitza bera luzera.
>> Saiatzen ohi espazio asko erabiltzeko.
Duen hash taula bat kontrastea da, non soilik nodo berri bat behar dugu
Zenbait gako-balioa bikotea gordetzeko.
Orain, berriro ere teorian, espazio handi kontsumoak ez du handi bat bezala dirudi
aurre egiteko, are gutxiago, moderno ordenagailuak gigabyte eta
memoria gigabyte.
Baina bihurtzen da hori oraindik ez dugu memoria erabilera eta kezkatu
mesedetan erakundea errendimendua, geroztik ordenagailuak modernoaren
pean bildu diren mekanismoak izan kanpaia azkartzeko memoria sarrera.
>> Baina mekanismo horiek lan onena memoria sarbideak dira trinkoa egin
eskualde edo arloak.
Eta trie baten nodo bizi liteke zeure duen edozein lekutan.
Baina horiek ez dira merkataritza-off duten kontuan hartu behar dugu.
>> Gogoratu, Datuak bat aukeratzerakoan Zeregin jakin baterako egitura, dugu
pentsatu behar da zer motatako eragiketak datuak egitura behar
laguntza eta zenbat errendimendua horietako bakoitzaren
eragiketak gurekin gaietan.
Eragiketa horiek, are gehiago, baliteke besterik haratago hedatzen
oinarrizko look up eta txertatzeko.
Suposatzen moduko bat martxan jartzea nahi izan dugu auto-osoa funtzionaltasuna, askoz
bezalako Google bilatzailea du.
Hau da, itzultzeko tekla guztiak eta balioak potentzialki horrek
aurrizki jakin bat dute.
>> Trie bakarrean erabilgarria da eragiketa honetarako.
Da erraza bidez batetik bestera joateko izaera bakoitzeko trie
aurrizkia.
Just look up eragiketa bat bezala, erakusleak jarraitu ahal izan genuen
pertsonaia by pertsonaia.
Orduan, noiz iritsiko da amaieran dugu aurrizkia, bidez batetik bestera joateko genezake
Gainerako datuak egituraren zati giltzarrietako edozein haratago geroztik
Puntu honetan izan aurrizkia.
>> Halaber Erraza da zerrenda honetan lortzea geroztik ordena alfabetikoan du
haurrak array elementuak alfabetikoki ordenatuta daude.
Beraz, espero dugu kontuan hartu beharko duzu emanez saiatu saiatzen.
Naiz Kevin Schmid, eta hau da CS50.
>> Ah, hau hasiera da gainbehera.
Sentitzen dut.
Barkatu.
>> Greba lau.
Irten naiz.
Barkatu.
Pertsonaren egiteko Barkatu nor editatzeko honetan joan crazy ditu.
>> Barkatu.
Barkatu.
>> HIZLARIA 1: Ongi egina.
Benetan ondo egina zen.