DOUG LLOYD: Beraz CS50, Nik estaltzen dugu Datu-egitura desberdinak asko, ezta? Arrayak ikusi dugu, eta lotuta zerrendak eta hash taulak, eta saiatzen da, pilak eta ilarak. Ere, apur bat ikasi dugu zuhaitz eta metak buruz, baina benetan horiek guztiak, besterik gabe amaituko up gai bat aldaketa izanik. Horiek Benetan, oinarrizko lau ideia mota Dena dela, beste irakiten daiteke behera. Arrayak, lotuta zerrendak, hash taulak, eta saiatzen da. Eta antzera, esan nion ez horien gainean aldakuntzak daude, baina hori nahiko Askoz laburbiltzeko joan Dena ari gara hitz joan C. dagokionez class honi buruz Baina nola egin horiek neurri guztiak eman, ezta? Aldekoak eta kontrakoak buruz hitz egin dugu horien gainean bideoak bereiziak bakoitzeko, baina ez zenbakiak asko da ohitu inguruan bota. Ez dago general asko da pentsamenduak ohitu inguruan bota. Dezagun saiatu eta sendotzeko leku bakar bat sartu da. Dezagun pisatzen pros aurka txarrez, eta kontuan hartu zein datu-egitura Eskuineko datuak izan liteke zure egoera bereziki egitura, edozein motatako datuen gordetzeko zaren. Zuk ez dute zertan beti behar den super azkar txertatzeko, ezabatzeko erabili, eta trie bat bilatu nahi izanez gero, benetan ez txertatu eta ezabatu zaintzeko gehiegi. Besterik azkar ausazko behar baduzu sarbidea, agian array bat hobea da. Hargatik destila hori. Hitz egin lau bakoitzari buruz Datu-egitura mota nagusien Horri buruz hitz egin dugu, eta besterik ikusten denean ona izan dute agian, Noiz eta agian ez dute hain ona. Hargatik hilarak en. Beraz txertatzeko, hori da mota txarra. 

Array baten amaieran-sartzeak ondo dago; dugu array bat eraikitzen ari bada joan gara. Baina txertatu behar badugu erdian sartu elementuak, uste back-sartzeak den ordenatu, han asko da elementu bat egokitzeko hor ikusita. Eta ari gara txertatu hala bada joan edonon baina array baten amaiera, Hori ez da, seguruenik, hain handia. 

Era berean, ezabatzeko, ari gara salbu array baten amaiera ezabatu, Era berean, seguruenik ez da hain handia bada ez dugu hutsuneak hutsik utzi nahi, hau da, normalean ez dugu. Elementu bat kendu nahi dugu, eta Orduz Sort egin berriro snug da. Eta orain elementuak ezabatzen sorta bat, gainera, ez da hain handia. 

Bilaketa, ordea, handia da. Ausazko sarbidea izan dugu, denbora etengabe bilatu. Esango dugu besterik zazpi, eta joan ginen array lekualdaketa zazpi. Esango dugu, 20, joan array lekualdaketa 20. Guk ez dugu izan zeharkatuz batetik bestera joateko. Hori nahiko ona. 

Arrayak ordenatzeko nahiko erraza. Aldi bakoitzean hitz egin dugu ordenazio buruz bildu, hala nola aukeraketa sort bezala, txertatzeko ordenatu, burbuila ordenatu, batu ordenatu, beti da egiten baikenuen arrayak, array nahiko erraza delako ordenatu, datuen egitura erlatiboa Orain arte ikusi dugu. 

Halaber, txiki samarra ari dira. Ez zeukan beste tarte asko. Ezarri besterik ez alde batera utzita, zehazki bezainbeste Zure datuak eduki behar duzun bezala, eta hori nahiko askoz da. Beraz, nahiko txikiak ari dira eta horrela eraginkorra. Baina arazotxo bat, nahiz eta, da tamaina dutela finkoak dira. Zehazki deklaratzeko nola egin behar dugu big gure array izan nahi dugu, eta jaurtiketa bat bakarrik lortuko ditugula. Ezin dugu hazten eta txikitu. 

Hazten edo txikitu behar badugu, array erabat berria aldarrikatu behar, kopiatu elementu guztien bigarren array sartu lehen array. Eta kalkulu okerrak dugu badu denbora, berriro egin behar dugu. Ez da hain handia. Beraz, multzo ez eman malgutasuna elementuen zenbakiak aldakorra dute. 

Zerrenda bat lotuta, Txertatze nahiko erraza da. Aurrean kalera Tack besterik ez dugu. Ezabaketa ere nahiko erraza da. Elementu aurkitu behar dugu. Hori bilatzeko batzuk inplikatzeko. 

Baina behin elementua aurkitu duzu duzu, egin behar duzun guztia zabiltzala da erakuslea aldatu, seguru bi baldin baduzu bi aldiz bat list-- lotuta Zerrenda lotuta, rather-- eta, ondoren, besterik libre dezakezu nodoa. Ez daukazu filmea dena inguruan. Bi erakusleak aldatu besterik ez duzu, beraz, nahiko azkarra da. 

Bilaketa txarra bada ere, ezta? Bat aurkitu guretzat ordenan lotuta zerrenda batean elementu, ala banaka edo bi aldiz lotuta, bilatu lineala behar dugu. To hasieran hasiko ditugu, eta mugitu amaieran, bai bukaerako mugimendua hasten hasieran. Guk ez dugu izan ausazko sarbidea jada. Beraz, bat egiten ari gara, Bilatzen asko, agian, lotutako zerrenda bat, ez da hain ona da guretzat. 

Oraindik ere oso ordenatzeko zaila da, ezta? Ahal duzun Modu bakarra lotutako zerrenda bat benetan ordenatzeko dela ordenatzeko Eraikitzeko duzun bezala. Baina egiten duzun bezala ordenatzen badituzu eraikitzen da, Oraindik ez dago jada sarrerak azkar jada egiteko. Oraindik ez duzu besterik tacking Gauzak aurrean kalera. Aurkitu behar duzu eskuineko spot jarri, eta, ondoren, zure txertatze- bihurtzen besterik buruz bezain txarra array batean txertatzeak bezala. Beraz, zerrendak lotuta ez dauden hain handia datuak ordenatzeko. 

Oraindik ere nahiko txikiak, tamaina-wise. Bi aldiz lotuta zerrenda zertxobait banaka lotuta zerrendak baino handiagoak, diren zertxobait handiagoa array baino, baina ez da alferrik galtzen espazioa kopuru handi bat. Beraz, bada, espazio prima bat da, baina Ez prima benetan bizia, hau da joan eskuineko bidea izan liteke. 

Hash taulak. Hash taula bat sartzen lagunduz nahiko erraza da. Bi-prozesuan urrats bat da. Lehen bitartez gure datuak exekutatu behar dugu hash funtzio bat hash kodea lortzeko, eta, ondoren, sartu elementua txertatu dugu Hash kodea kokapena hartan mahai hash. 

Deletion, lotuta zerrenda antzekoak, erraza da behin elementu aurkituko dituzu. Da lehen aurkitu behar duzu, baina, orduan, ezabatzeko duzu, besterik truke behar duzu erakusleak pare bat, bereizi kateatzea erabiliz gero. Kraterrak erabiltzen ari bazara, edo ez bazaude batere kateatzea erabiliz hash taula batean, ezabatzeko benetan oso erraza da. Guztiak egin behar duzun da hash datuak, eta, ondoren, kokapena joango dira. Eta suposatuz ez duzu talkak dute, Oso azkar ezabatu ahal izango duzu. 

Orain, bilatu non gauza da pixka bat zailagoa da. Batez besteko hobea on It lotutako zerrendak baino. Kateatzea erabiltzen ari bazara, oraindik lotuta zerrenda bat duzu, horrek esan nahi du, oraindik ere, behar duzun bilaketa lotuta zerrenda kaltetan. Baina zuk hartzen ari delako zure lotuta Zerrenda eta splitting 100 edo 1.000 edo n zure hash taula elementu, zaren lotuta zerrendak tamaina Ngarren bat dira. Guztiak nabarmenki txikiagoa Oraindik dute. Izan n lotuta Zerrendak ordez lotuta tamaina n zerrenda bat. 

Eta beraz, real-mundu honetan konstante faktorea, oro har, zein dugu ez hitz egin, denbora konplexutasuna, hura du benetan egin diferentzia hemen. Beraz bilatu lineala oraindik bilatu kateatzea erabiliz gero, baina zerrenda luzera bilatzean zu da, oso, oso labur alderatuz. Berriz ere, ordenazio zure badago Helburua hemen, hash taula seguruenik ez da eskuineko bidea joan. Just matrizea erabiliko dira ordenatzeko bada da benetan garrantzia. 

Eta tamaina gamaren exekutatu ahal izango dute. Zaila da bat esatea Hash taula txiki edo handi, Egiatan araberakoa delako nola handi hash taula da. Gordetzeko bakarrik bazoaz bost elementu hash taula batean, eta hash taula bat behar duzu 10.000 bertan elementuekin, Ziurrenik ari espazio asko alferrik galtzen duzu. Kontrastatu duzu ere ari daiteke hash oso trinkoa mahaiak dute, baina txikiagoa hash taula lortzen, luzeagoak loturiko zerrendak horietako bakoitza lortzen. Eta, beraz, ez da benetan den definitzen du inola zehazki hash taula baten tamaina, baina seguruenik seguru esateko oro har, a lotuta baino handiagoa izango da Zerrenda bera datuak gordetzeko, baina trie bat baino txikiagoa. 

Eta saiatzen laugarrena dira Egitura horiek Hori egin dugu buruz hitz egiten. Trie bat sartu txertatzeak konplexua da. Ez dago dinamikoa asko da memoria esleipena, batez ere, hasieran, eraikitzeko hasten zaren bezala. Baina etengabeko denbora da. Giza elementu bakarra da, Hemen egiten duen delikatua. Null erakuslea topo beharrik, malloc espazioa, han joan, espazio seguru malloc hortik berriro. Larderia faktore moduko memoria dinamikoa esleipena erakusleak oztopoa den argi dago. Baina behin garbitu egiten, txertatzeko Egia esan, nahiko erraz dator, eta, zalantzarik gabe, etengabeko denbora da. 

Ezabaketa erraza da. Guztiak egin behar duzun da nabigatu behera erakusleak eta doan nodoa pare, beraz, nahiko ona. Bilatu ere nahiko azkarra da. Honez bakarrik oinarritutako Zure datuak luzera. Beraz, zure datu guztiak badago bost pertsonaia kateak, adibidez, bost gordetzeko zaren Pertsonaia zure trie kateak, bost urrats bakarrik hartzen du da zer bilatzen ari zaren aurkitzeko. Etengabeko faktore bat besterik Bost dago, beraz, Berriro, txertatzeko, ezabatzeko, eta bilatu Hemen zaude etengabeko denbora guztian, eraginkortasunez. 

Beste gauza bat da zure trie dela benetan mota dagoeneko horrela, ezta? Nola ari garen indarrez elementu sartuko, Gutun joan letra by arabera gakoa, edo gakoaren digituko arabera digituko, normalean, zure trie bukatzen ari motatako ordenatuko eratzen duzun bezala. Ez du benetan egiten Zentzu ordenatzeko pentsatzen modu berean pentsatzen dugu da multzo dute, edo zerrendak lotuta, edo hash taulak. Baina nolabait, zure trie ordenatuko da joan ahala. 

Arazotxo, jakina, hori da trie bat azkar handi bihurtzen da. Bidegurutzera puntu guztietatik, baliteke have-- zure gako digituak osatzen bada, duzu 10 bestelako lekuak joan ahal izango duzu, eta horrek nodo bakoitzean esan nahi du informazioa du datuei buruz gorde nahi duzu nodo hori, plus 10 erakusle dira. Zein, CS50 IDE, 80 byte da. Beraz, gutxienez 80 byte da zuk sortutako nodo bakoitzean, eta hori ez da datu are kontatuta. Eta zure nodo badira letren ordez digituen, orain 26 erakusle duzu kokapena guztietatik. Eta 26 aldiz 8 da seguruenik 200 byte, edo horrelako zerbait. Eta kapital duzu eta minuskulaz dezakezu Begira non honekin noa, ezta? Zure nodo benetan lortu ahal big, eta beraz, trie bera, oro har, ezin benetan big, gehiegi. Beraz, bada espazio altua da premium zure sisteman, trie bat agian ez du modu eskubidea izan joan, nahiz eta bere beste prestazioak arren jokoan sartzen dira. Naiz Doug Lloyd. Hau CS50 da.