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. Barkatu. Barkatu. 

Greba lau. Irten naiz. Barkatu. Barkatu. Barkatu. Pertsonaren egiteko Barkatu nor editatzeko honetan joan crazy ditu. 

Barkatu. Barkatu. Barkatu. Barkatu. 

HIZLARIA 1: Ongi egina. Benetan ondo egina zen.