DAVID MALAN: Eskubidea guztiak. Ongi etorri atzera CS50. 8 aste honetan hasiera da. Eta gogoratzen duten arazo multzo 5 amaitu erronka bat pixka batekin. Beraz, zure guztiak berreskuratu duzu suposatuz irakaskuntza Fellows eta CA-ren argazkiak card.raw fitxategian, eskubidea zaude Orain aurkituko pertsona horiek guztiak, eta ko zortea irabazlea etxera oinez egingo batekin Gauza horiek, jauzi mugimendua Gailu ditzakezun final erabili proiektuak, adibidez. Hau, urtero, eta oina creepiness pixka bat. Eta, beraz, zer egin nuela pentsatu nuen share zurekin ohar duten zenbait desagertu atzera eta aurrera baino gehiago berandu zerrenda langileek. Adibidez, besterik gabe, bart, aurrekontua egiteko unquote, langile bat kideak, "izan dut ikaslea erronda bat nire atean nirekin argazki bat ateratzeko. Stal, esango dut ". Hasi nahiko deskriptiboa eta, ondoren, mugitu dugu on, ordu bat edo, beraz, geroago, "bat izan nuen ikaslea niretzat atala ondoren eta gure izenak eta argazki guztiak izan zuen paper-orri batzuk. "Ondo da. Beraz, antolatzen, baina ez duten guztiak creepy oraindik. Ondoren, "out izan dut herri asteburu honetan, eta noiz itzuli dut, ez dago bat izan zen, nire logelak. "[barreak] DAVID MALAN: langile aurrekontua Hurrengoa kide, "ikasle bat etorri zen nire etxea at 4 Somerville goizean AM. "Hurrengoa langileak, "lortu nire San hotel dut Francisco eta ikaslea izan zen zain hiru DSLRs dituzten lobby hartan dit. " Kamera-mota. "Ez nago nahiz langileek seihileko honetan, baina, ikasle bat nire etxean sartu honetan goiz eta grabatutako gauza osoa Google Glass-ekin. "Eta, azkenik, "Gutxienez 12 pertsona izan ziren irrikitan niretzat noiz dut nire zain Limo, eta, ondoren, I esnatu. "Ondo da. Beraz, argazkien artean, maiatzaren gisa dituzu gogoratzen dira, ikaskide hau hemen, nor zaren baliteke Milo Banana, bizi gisa ezagutzen Lauren Carvalho, gure burua Fellow irakasten. Milo, Milo, zatoz hona mutil. Milo. Milo. Axola, Google-Glass zuen jantzita, eta beraz, erakusten dizkizugu hori guztia egin ondoren. Beraz, hau da, Milo nahi baduzu argazki bat hartu berarekin ondoren. Kanpora begiratu nahi baduzu ikusleek ez zuten. Ados. Hori ona metrajea. Beno, Milo Banana. Oh, ez da hori egiteko. [Barreak] Ados. Hitz bat eta ondoren zer datza aurretik, beraz, trantsizio dugu hasten delako, aste honetan, zehazki, bat C-tik Komando-lerroa PHP eta ingurumena Ikusteko Javascript-a eta SQL eta HTML eta CSS web ingurune bat, izan dugu duzun ekipamendu guztiekin gehiago ezagutza potentzial amaierako proiektuak. Horretarako norabidean, jakina dauka mintegiak edukitzearen tradizioa gaiak tangentzialak dira ikastaroan. Oso programazio eta zerikusia app garapena eta abar, baina ez nahitaez aztertu arabera Ikastaroaren berezko ikasketa plana. Beraz, bada bat interesa izan dezakezu edo aurtengo mintegiak gehiago, cs50.net/seminar erregistratu. Badira adineko mintegiak cs50.net/seminars at. Zerrendan, eta, beraz, aurten buruzko Amazing dira Ruby Web Apps on batekin Rails, zein alternatiba bat da PHP hizkuntzan. Linguistika konputazionala. To IOS, hau da, sarrera plataforma en iPhone erabiltzen eta iPad garatzeko. Ikusteko Javascript-a Web Apps, estali egingo dugu hori, baina, mintegi honetan, joan ahal izango duzu Xehetasun gehiago sartu. Jauzi Mugimenduan, beraz, benetan dugu zenbait gure jauzi Mugimenduan etorritako lagunak, enpresan bertan, gurekin. Bihar, hain zuzen ere, ematen eskuak-on bat mintegia, bada zure interesekoak. Meteor.js, teknika alternatibo bat egiteko Ikusteko Javascript-a erabiliz, ez da nabigatzaile bat da, baina zerbitzari batean. Node.js, hau da, oso Ildo horretan, bai. Sleek Android diseinua. Android oso ezaguna alternatiboa izateaz to iOS eta Windows Telefonoa eta beste plataforma mugikorrak. Web eta segurtasuna defentsa aktiboa. Beraz, hain zuzen ere, nahi duzu bada honetan parte hartzeko, let me Egiteko honen oharra. Oso pozik dagoela esan gara gure jauzi lagunekin Mugimenduan, zein startup bat da - gailu hau benetan bakarrik etorri duela hilabete batzuk out - graciously dohaintzan eman ditu, besteak beste, 30 gailu du ikasle askok bezala, klase, bada like hardware maileguan zinela seihilekoaren bukaera aldera, eta erabili benetako azken proiektua. Hainbat hizkuntzatan onartzen dira. Horietako bat ere ez C, horietako inor PHP, beraz, konturatzen bat edo gehiago mintegi horien baliteke interes frogatzeko. Eta horiek guztiak behar diren filmatu gertaera ez zarela gai pertsona hasi dira. Ordutegia izango iragarri bidez email solidoa dugu gela gisa. Eta, azkenik, nahi baduzu projects.cs.50.net, hau da, web urtero gonbidatzen ditugu mantentzen dugu batetik, komunitatean, fakultatean, lagunok, sailetan, langileak, eta biak CS50 Kanpo batean proposatzen proiektuaren ideia. Interesgarriak diren gauzak, ikasle taldeak. De sailaren interes gauzak. Beraz, ez dago buelta egiten ari zaren borrokan ari bada zer duzun bezala ziurgabetasun batekin nahi aurre zeuk litzateke. Beraz, azken denbora bat sartu dugu, dudarik gabe, konplexuagoa datuak egitura genuke baino iragan aste ikusi. Dira genuke array erabiliz nahiko zorionez gisa erabilgarria bada sinplista datuak egitura. Ondoren, hauek sartu ditugu, eta horrek jakina lotuta daude zerrendak. Eta zer motibazio nagusietako bat izan zen Datuen egitura hau aurkezten? Bai? Zer da hori? Ikusleak: dinamikoa tamaina. DAVID MALAN: dinamikoa tamaina. Beraz, array, berriz, behar duzu bere jakin, aldez aurretik, neurri berau esleitu duzu. Zerrenda lotuta ere, ez duzu izan duten jakin ahal izateko. Besterik malloc, edo, oro har, ahal baduzu, esleitu gehigarri bat nodoa, nolabait esateko, edonoiz duzu nahi datu gehiago txertatzeko. Nodo eta ez du aldez aurretik esanahia. Besterik ez da deskribatzeko termino generiko zenbait edukiontzi mota ari gara Gure datu-egitura gordetzeko erabiltzen interes-elementu batzuk, honetan duen Kasu gertatuko osokoak izan. Baina ez da beti bat denerako. Beraz, datuen tamaina dinamikoa lortuko dugu egitura, baina zer egiten dugu prezio ordaindu? Zer zerrendak lotutako arazotxo da? Bai? Ikusleak: memoria gehiago behar du. DAVID MALAN: gehiago behar da memoria, zer? Ikusleak: [INAUDIBLE]. DAVID MALAN: Horixe. Beraz, orain erakusleak ditugu hartuz osagarriak memoria dugu aldez aurretik duten ez zuen behar, izan ere, abantaila array bat, noski, hau da, Alboko dena da, atzera ra itzuli itzuli, eta horrek ematen dizu ausazko sarbidea. Besterik kortxetea erabiliz delako idazkera, edo gehiago, teknikoki erakuslea aritmetika, oso erraza da, gainera, edozein sartu duzu denbora etengabeko elementuak. Eta, hain zuzen ere, horretan laguntza mota da prezio beste garela bat ordainduz lotuta zerrenda. Zer exekutatzen denbora gertatzen Search antzeko zerbait, nahi dut, nahi izanez gero, balio batzuk aurkitu eta barruan lotuta zerrenda? Zer gertatzen da nire denborak ez du bihurtu? Big n O. Gainera nahi izanez gero ordenatuko? Zer datuak egitura ordenatuko da bada? Ezin big baino hobeto egin dut N O bilatzeko? Ez, izan ere, kasu horretan, txarrena izan daiteke Oso ondo ordenatuta, baina kopurua handia izan daiteke bilatzen ari zaren. 100 zenbakia da, eta hori izan liteke guztiak izango dira gerta amaieran bidea. Eta ezin duzu bakarrik sartzeko lotuta ezartzeko honetan zerrendaren arabera nodoa bere lehenengo bidea, zauden oraindik nolako zorte daudelarik. Gauza osoa zeharkatzeko behar duzu lehen ordena aurkituko iraungo 100 bezalako balio handia duten. Edo ez bada zehazteko ere ez dago. Beraz, ezin dugu zer datuak batean algoritmoa egitura itxura hau? Ezin dugu bilaketa bitarra delako, bilaketa bitarra eskatzen genuen ausazko sarbidea. Besterik ezin izan dugu kokapen batetik jauzi jarraitu beharrik gabe kokapena inprimakia ogi apurrak hauek erakusleak horiek guztiak. Orain, nola hau ezartzeko dugu? Beno, pantaila galtzen dugu hemen, bada azkar dezakegu reimplement datuak honetan egitura - nire idazkera ez da guztia handia da hemen, baina saiatu gara. Beraz typedef struct, eta zer egin nuen nahi gauza hori deitzeko hemen? Nodoa. Beraz, gurekin hasi naiz. Eta orain, zer egin behar du barruan izan banaka duten egitura datuak lotuta dago zerrendan? Zenbat eremuetan? Beraz, bi. Nahiko erraza da bat. Beraz, int n. Eta n ezer dugu deitu nahi izan dugu, baina int bat izan beharko litzateke Oraindik badugu ints zerrenda lotuta ezartzeko. Eta orain, zer da bigarrena Eremu izatea? Egitura nodo *. Beraz, bada, egitura nodo *, eta gero, ez dut nik honek deitu ere edozein dela ere nahi dut, baina argi deitu dut , hurrengo dugun bezala egiten. Eta, ondoren, nire kizkur giltza itxi dut. Eta orain, azken gisa, Nodo behera jarri dut hemen. Baina nago, hau bada bat bezala geratuko da Nodo, zergatik beraz izateaz kezkatu dut Luze hemen egitura geratuko nodo * ondoan, aurrean besterik nodo * hurrengoa? Bai? Ikusleak: [INAUDIBLE]. DAVID MALAN: Horixe. Zehazki. C benetan hartzen duzulako, eta hitzez hitz soilik nodo definizioa ikusten Hemen modu behera, ezin duzu da erreferentzia hemen. Beraz preemptive moduko hau dugu adierazpena hemen, hau da, Admittedly more verbose. Egitura nodoa, horrek esan nahi du Orain, ezin dugu sartu datu-egituraren barruan. Eta alde batera bezala, honetan ere pixka bat gehiago subjektiboa bilakatu da gaur egun, izarra teknikoki joan daiteke hemen, hemen joan ahal izango da, eta, ahal nahiz eta erdian joan. Hartutako dugu, gida estilo en Ikastaroan, jarri batzarra izarra eskubidea datuak hurrengo mota bat, kasu honetan, eta, egitura nodoa izango litzateke. Testu-liburuak, baina askotan konturatzen eta online erreferentziak, hain zuzen ere, dezakezu ikusten da beste aldetik. Baina konturatzen bai benetan lan egin eta, besterik gabe, behar duzu koherentea. Guztiak eskubidea. Beraz, hori izan da gure adierazpena egitura nodoaren. Baina gero gehiago egiten hasi ginen sofistikatua gauzak. Adibidez, sartzea erabaki genuen hash taula bat bezalako zerbait. Beraz, hemen tamaina n hash taula bat da, 0 indexatutako n utzi gainean ken behean utzi 1. Hau egiaztapen bat izan liteke ezer taula. Baina, zer gauza mota genuen hitz hash taula bat erabiliz buruz? Gordetzeko, zer? Izenak. Izenak egin izan dugun bezala, azken aldiz egin dugu. Eta benetan, ezer gorde ahal izango duzu. Eta hau ikusiko dugu berriro PHP eta Javascript-en. Hash taula bat Suitzako moduko polita da Army labana hori gordetzeko aukera ematen dizu nahiko askoz edozein dela ere barruan nahi duzu balioak dituzten gakoak by lotzen ditu. Balioak dituzten gakoak. Azken hau simple kasuan, gure gakoak dira zenbakiak. Egiaztapen bat ari gara ezartzeko array gisa taula. Eta, beraz, gakoak 0 dira, 1, 2, eta abar. Eta, beraz, gizakiak bezala, gu, azken erabaki aste hori, zer, Oraindik badugu badakizu denda izenak joan, dezagun, besterik gabe, edonola, baina nahiko arrazoiz, Alice bere gain, A-izen bat dela, soilik sartu behar dira 0 ordenatuta. Eta Bob, B, izena, indexatu egingo da 1, eta abar. Beraz, sarrera arteko mapping bat izan genuen, horrek kateak dira, eta hash balioa kokapenak, diren zenbakiak. Beraz, prozesu hori, oro har, ezagutzen hash funtzio bat, eta benetan dezakezu ezartzea da kodean. Nahi nuen hash funtzio bat ezarri nahi baduzu horrela, ez dugu zehatz-mehatz zer besterik gabe, azken aldiz, deskribatzen, I might deklaratzeko funtzio bat hartzen du, baita Adibidez, sarrera - eta egin dezagun honetan hemen pantaila. Nahi nuen egiaztapen bat ezarri nahi baduzu funtzioa, esan liteke I honen antzeko zerbait. Int bat itzuli behar da joan. Deitu behar hash da joan, eta bere argumentu bat onartzen joan katea, edo gehiago, egokia dugu, gaur egun, eta esan char *, deitu s gara. Eta, ondoren, funtzio hori guztia egiteko, azken finean, int bat itzuli da. Orain, nola egiten du hori gerta ez dira hain argi. Hau ezartzeko gabe noa error egiaztatzea osatzeko oraintxe. Besterik ez dut esan blindly joan, bueltatu edozein dela ere s tarte 0 da, ken, esan dezagun, kapital eta koma. Erabat hautsi. Ez da perfektua delako ko, zer da s null bada? Gauza txarrak dira gertatuko. Bi, zer galtzen honetan gutun lehen izena ez da maiuskulaz? Hori ez da piztu joan ondo bai. Minuskulaz gutun bat izan liteke edo ez, gutun bat. Beraz, erabat hobetu da hemen, baina honen oinarrizko ideia da. Zer azken astean deskribatu dugu hitzez gisa besterik Alice mapak egiteko prozesu bat 0 eta Bob eta 1 adieraz daiteke zalantzarik gabe, gehiago formulaically C gisa funtziona hemen. Izeneko berriro fidatu, kate bat bezala hartzen du sarrera, eta, ondoren, nolabait egiten du zerbait sarrera duten irteera bat sortzeko asmoz. Ez gure kutxa beltzak ez bezala deskribapena dugun luzea egin. Ez dakit nola egongo den jakiteko kanpaia azpian lanean. Arazo multzo 6, erronka bat da, zeuk erabakitzen duzu zer egingo al hash funtzioa izan daiteke? Zer beltz horren barruan izango da kutxa, eta, ustez, bat izango duzue gehixeago hau interesgarria baino, eta behin betiko gehiago akats joera jakin hori baino egiaztapena ezartzeko. Baina arazoak, sor daiteke, ezta? Dugu horrelako egitura bat izanez gero, datuak ko, zer arazo bat da exekutatu ahal duzun denbora baino gehiago sartu duzun gero eta gehiago sartu izenak hash taula? Talkak lortu duzu, ezta? Zer behar duzu Alice eta Aaron bada, bi pertsona beren izenak gertatu A-rekin hasi? Duten galdera segurutzat jotzen dute, non jarri du, hala nola, bigarren izena? Beno, naively baliteke besterik jarri non Bob da, baina, ondoren, Bob da mota screwed saiatu izanez gero sartu haren izena, eta hurrengo ez zion gela ez da. Beraz, Bob non Charlie da jarri dezakezu, eta imajinatu hau oso azkar dezakezu nahaspila bat pixka bat sartu devolving. Zerbait lineal, azkenean, non besterik ez dute gauza osoa bilatu Alice edo Bob bila edo Aaron edo Charlie. Beraz, horren ordez, proposatu dugun ordez, besterik linealki espazio irekita probak eta izenak plopping ez dugu proposatu fancier hurbilketa bat. Inplementatu oraindik duen hash taula bat indize array, baina datu-mota indizeak horiek orain erakusleak izan ziren. Zer esan? Lotuta zerrendak erakusleak. Abisuaren lotuta zerrenda bat delako Benetan, besterik gabe, nodo bat erakusle eta nodo bat hurrengo eremuan, eta nodo dituen hurrengo eremu bat du, eta abar. Beraz, orain dezakezu array honetan, uste hash taula bat jo du ezkerreko eskua lotuta zerrenda bat lortzeko. Duen abantaila da lortu baduzu Alice eta Aaron arteko talka, zer egin nahi duzu bigarren, besteak beste, pertsona? Erantsi besterik ez duzu bera du amaieran, edo are gehiago, hasieran lotzen zerrenda. Eta egia esan, dezagun, besterik fideodun bidez besterik gabe, bigarren bat. Non gehien zentzu luke? Txertatzen Alice bada, eta sortu zuen eta ondorioz lehen kokalekua, eta gero saiatzen naiz sartu Aaron izena, eta ez da jakina, talka bat, behar dut jarri zion hasieran lotuta zerrenda? Duten lehenengo kokapenean da, edo amaieran? Ikusleak: [INAUDIBLE]. DAVID MALAN: OK. Hasieratik entzun nuen. Zergatik hasieran? Ikusleak: [INAUDIBLE]. DAVID MALAN: OK. Alfabetikoa da, eta hori da hain polita. Jabetza hori ona da. Gorde me izango da denbora batzuk potentzialki. Ez da utzi bitar bilaketa egin dit, baina ez dut baliteke gutxienez gai izan hausteko begizta baten konturatzen badut, ongi, modu naiz iragan ziren Aaron litzateke hau izango da ordenatuko lotutako zerrenda. Ez dut nire denbora alferrik bilatzen amaiera modu guztiak. Beraz, hori da arrazoizkoa. Zergatik, bestela, agian sartu nahi duzun bertan izena talka egiten du zerrendaren hasiera-hasieratik? Zer da hori? Ikusleak: [INAUDIBLE]. DAVID MALAN: denbora luze bat hartu izan da, zerrendari amaiera lortzeko. Eta, hain zuzen ere, gero eta mantsoago. Gehiago izenak sartu duzun hori A, orduan eta horrekin hasteko katean dago, lortu dugu. Luzeagoa lotuta dagoela zerrenda bat lortu dugu. Beraz, benetan ari zaren zure denbora alferrik galtzen. Agian hobea zarela off mantenduz etengabeko txertatzeko denbora, big 1 O, beti talka izena jarriz lotuta zerrendaren hasiera-hasieratik, eta ez askoz kezkagarria ordenatzeko buruz. Zer onena erantzuna? Unclear da. Mota araberakoa da on zer banaketa da, zer eredua da izen txertatzen ari zara. Ez da, nahitaez, bistako erantzuna. Baina, hemen, berriz, ez da diseinu-aukera bat da. Beraz, gauza hau eta gero begiratu dugu, eta horrek Benetan beste aukera handi p-multzo 6. Eta konturatzen, ez baduzu dagoeneko, Zamyla horiek sartu murgilaldiak, hash mahai eta saiatzen da, zehatz-mehatz. Eta bideo gidatua da p-set spec barneratua. Hau trie bat izan zen - T-R-I-E. Eta zer izan zen interesgarri buruz hau dela exekutatzen denbora izan zen izen bat bilatzeko, Maxwell bezala azken aldiz, big O zer izan zen? Zer da hori? Ikusleak: hizki-kopurua. DAVID MALAN: letren kopurua. Bi gauza entzun nuen. Letrak eta etengabeko denbora kopurua. Hargatik lehen joan. Letra kopuruak. Beno, hau datu egitura, gogoratzen da, gustatzen zuhaitz bat, familia zuhaitz bat, bakoitzaren zeinen nodo osatzen array du. Eta multzo horiek erakusten dira beste nodo, edo beste, hala nola, Zuhaitza array. Beraz, bada, ondoren, zehaztu nahi izan dugu Maxwell ala ez, hemen da, joan liteke I , lehen array, oso goian at zuhaitza, llamado erroa, goiko trie, eta gero jarraitu m erakusleak, ondoren, erakuslea eta, ondoren, x, w, e, l, l. Eta orduan, berezia ikur batzuk ikusi ditut, adierazten da hemen triangelu baten ondorioz. Kodea ikusi dugu proposatu beharko duzu duzula boolearra gisa inplementatu, besterik gabe, bai esaten edo ez, hitz bat gelditzen da hemen. Beno, behin M-A-X-W-E-L-L dugu joan zazpi bezala sentitzen, agian zortzi joan behar dugu iragan bat, zortzi bada urrats Maxwell aurkitzeko. Edo dezagun deitzen K. Baina azken gogoratzen denbora, bada, hori ez da argudiatu dut errealistan baten luzera gehienez hitza, 40-batzuk-bakoitiak pertsonaien antzera, gehienezko luzera dakar etengabeko balio bat. Beraz, benetan, bai, teknikoki big O da 8 edo 7 edo benetan big K. O Baina ez dago zer txano finitu bat bada K izan, konstante bat da. Eta, beraz, big 1 O da at egunaren amaieran. Ez mundu errealean. Ez denean hasiko da, benetan, zuri begira zure programaren entzierroa gisa erlojua. Erabat da pixka bat izango da benetan etengabeko baino motelagoa urrats bat denbora. Zazpi edo zortzi urrats izango da joan, baina, oraindik ere, hori da askoz hobea big n O horrelako algoritmo bat baino zer en tamainaren araberakoa Datuen egitura. Iragarki goitik hemen da sartu ahal izango dugu milioi bat gehiago sartu izenak Datuen egitura, baina zenbat urrats va gurekin eraman aurkitu Kasu horretan Maxwell? Bat ere ez. Eraginik izan zuen. Eta orain arte, ez dut uste ikusi dugu datu egitura bat edo adibide bat algoritmoa izan zen erabat kanpoko eraginik horrelako jokabideak. Baina hau ez da izango harrigarria. Hau ezin da irtenbide bakarra izan P-ezarri Eta ez da. Hau ez da, datuak derrigorrez egitura behar duzu gravitate, taulak hash bezala, denerako delako. Zer prezioa ordaindu Hemen duzu? Memoria. Esan nahi dut, hau da atrocious memoria kopurua. Eta ezin nahiko ikusten duelako hemen Argazki hau egileari jakina trunkatuta array guztiak, eta ez gara A horrek asko ikusten da eta B-ren eta C-ren eta Q-ren eta Y-ren eta Z array hauetan horrek. Baina ez dira. Nodo horietako bakoitzak osotasunean array bat da batzuk 26 edo gehiago byte, bakoitzaren duen gutun bat adierazten du. Gure kasuan 27, beraz, onartzen dugu arazo multzo apostrophes. Datu egitura hori da benetan, beraz, Benetan trinko eta zabala. Eta hori bakarrik, azkenean, baliteke motelduz gauzak behera, edo, gutxienez, balio bat duzu Asko leku gehiago. Baina, berriro, marraztu ahal izango dugu konparazioak hemen. Gogoratzen, berriz, bat atzera, askoz ere lortu dugu gehiago zirraragarria lasterketak ordenatzeko denbora denean merge ordenatu, baina prezioa erabiltzen dugu n lortzeko saioa merge for n ordaintzen dugu sort eskatzen gastatzen dugun zer baliabide gehiago? Leku gehiago. Mailako bigarren array bat behar dugu kopiatzeko pertsonak, sartu bezala hemen egin dugu eszenatokian. Beraz, berriro ere, ez dago argi irabazleak, baina subjektiboa diseinua erabakiak hartu egin behar da. Guztiak eskubidea. Beraz, nola horri buruz? Edonork ezagutzen den D-Hall? Ados. Beraz, gurekin hiru egin. Mather Etxea. Beraz, hau Mather en jangela da. Apostu jantokiak guztiek dut hau bezalako erretiluak pila. Eta hau da, benetan, ordezkari zerbait dugu de jakina ikusten dagoeneko. Izeneko dugu, literalki, pila bat. Eta pila, zure aldetik ordenagailuaren memoria, non datuak doa funtzioak ari diren bitartean deitu. Esate baterako, zer motatako gauzak joan to aldean pilan memoria diseinua eztabaidatu dugu aste iragan? Zer da hori? Ikusleak: funtzio deiak. DAVID MALAN: Sentitzen dut. Ikusleak: funtzio deiak. DAVID MALAN: funtzio deiak, baina zehazki, zer bakoitzaren barruan da markoak horiek? Zer gauza mota? Bai. Beraz, aldagai lokalak. Edonoiz biltegi lokala batzuk behar ditugu, argumentu bezala, edo int dut, edo int aldi baterako, edo edozein tokiko aldagaia da, izan gara duten jarriz pilan. Eta hori pila bat deitu dugu, zeren layering ideia hori. Just partiduak mota sortu errealitatearekin, kontzeptu horiek. Baina bihurtzen da pila bat ere duten izango da datu-egitura bat bezala ikusten da, array alternatiba, alternatiba lotuta zerrenda. Zerbait kontzeptualki interesgarriagoa duten oraindik inplementatu erabiliz gero, horien gauzak, baina beste motako da Datuen egitura, laguntzeko, benetan, soilik bi eragiketak. Baina fancier dezakezu gehitzeko Ezaugarri horiek baino. Baina horiek oinarrizkoak dira - bultza eta pop. Eta pila bat ideia bada dudala dute hemen, edo Annenberg gabe ezagutu, ate datorren erretiluan kopurua 9 gainean ere. Beraz, int bat. Eta hau bultza datuak gainean nahi dut egitura, gaur egun hutsik dago. Demagun hau pilaren behean. Zenbaki hau 9 bultza nuke gainean pilatu, eta orain bertan da. Baina pila bat gauza interesgarri hau da, orain, nik nahi izanez gero, bultza batzuen balioa, 17 bezala, eta nik bultza pila gainean, hau da, egin dut bakarrik gauza intuitiboa da, besterik ez naiz jarri nahi dugun lekuan gizakiak makurturiko izango litzateke jarri, gainean. Baina zer da interesgarria orain da, nola lortu 9 dut? Badakizu, ez dut ahalegin batzuk gabe. Beraz, zer da interesgarria buruz pila bat duen diseinua da, bat LIFO datuak egitura da. Deskribatzeko modua Silly azken batean, lehen izarrekin. Azken zenbakia, beraz, Garai honetan izan zen, 17. Beraz, bada zerbait, pop off nahi dut pilaren, baino ezin izango da 17. Beraz, ez dago derrigorrezko ordena da eragiketak hemen, non azken elementua duen lehena izango da. Hori dela eta akronimoa, LIFO. Beraz, zergatik ez litzateke baliagarria? Beren testuinguru dira bertan, nahi duzuna nahi hau bezalako egitura datuak bat? Beno, oso baliagarria izan da, zalantzarik gabe, ordenagailu baten barruan. Beraz, argi eta garbi, sistema hau erabili datuak pilak egitura mota. Era berean, ikusiko dugu ideia bera denean, web orriak dator. Aste honetan eta datorren astean, beraz, eta haratago, eta hasteko duzun web ezartzeko jo hizkuntza batean izeneko HTML orrialdeak, dezakezu benetan erabiltzen den datu-egitura bezala hau zehazteko orriaren bada da behar bezala formateatu. Ikusiko dugu delako web orri guztiak jarraitu bat hierarkia ordenatu, koska bat egingo dela, egunaren amaieran, izan Zuhaitz kanpaia azpian egitura. Beraz, hori on gehiago pixka bat. Baina oraingoz, goazen bat proposatuko Oraingoz, nola buruz joan gara zer pila bat ordezkari? Let me ezartzea proposatzen dugu honelako-kodea pila bat. Beraz, pila bat dago, horren barruan izan joan bi gauza, array bat, deitu, erretiluak, besterik demo koherentea izateko. Eta array duten elementu bakoitzaren da int mota bat izango da. Eta ahalmena ez da zentzuzkoa zer? Nik ez delako idatzi Definizio osoa hemen. Seguruenik, gehienez array tamaina. Eta hori da, ziurrenik, zorrotz bat izendatu fitxategia goialdean definitzeko, zenbait etengabeko mota gisa inplizituki arabera hutsa kapitalizazio. Beraz, nonbait ahalmena definitzen ahalik eta tamaina maximoa gisa. Bien bitartean, barruan datu egitura pila bat bezala ezagutzen da egongo bakarrik ezagutzen da zenbaki oso bat izan tamaina gisa, besterik gabe. Beraz, bada, hau irudikatzeko izan dut orain pictorially, dezagun hori osoa kutxa beltza nire pila adierazten du. Horren barruan bi aldagai da. Beraz marraztu dut tamaina bat lehenengo. Eta bigarrena joan naiz array bat bezala marraztuko. Baina gauza ordenatua mantendu, normalean array bat marraztu nahi dut honek, baina horrek polita mota dator dugun errealitatea bada, edo dator adimen-eredua. Hargatik marraztu ordez me array bertikalean, hau da, besterik gabe, berriro ere, artistaren interpretazio. Ez da benetan axola zer kanpaia azpian dago. Eta hori esan dugu, berez, edukiera, hiru izango dira. Beraz, hau kokapena 0, hau izango da kokapena 1, hau izango da kokapena 2 izango da. Estresa, baloi bat dut bribe izanez gero, ez litzateke izango gustuko norbait etorri eta exekutatu taula Hemen, besterik gabe, une batez? OK, ikusi zure lehen eskuko. Goazen gora. Guztiak eskubidea. Beraz, Steven da uste dut. Goazen gora. Guztiak eskubidea. Baina demagun orain atzeratzean hasierako dugu munduaren egoera, non I deklaratu dute, besterik gabe, pila bat, eta hori da gaitasunaren hiru izango da. Baina tamaina ez da oraindik zehaztu. Erretiluak oraindik ez da zehazten. Galdera pare bat, beraz, lehen aldiz. Eta utzi ematen dit mic ahal duzu, beraz, partake gehiago aktiboki honetan. Beraz, zer tamaina barruan dago une honetan denbora guztia egin dut bada deklaratu pila batekin ko kodea lerroa? Steven: Ez asko. DAVID MALAN: OK, ez asko. Zer tamaina barruan da jakin dugu, zer da barrutik ezagutzen dugun array hau hemen? Steven: Just ausazko kodea da, ezta? Just - DAVID MALAN: Bai, nahi dut deitu kodea, baina ausazko - Steven: gauzak. DAVID MALAN: ausazko bezala gauzak Steven: Bits. DAVID MALAN: Bits, ezta? Zabor balioak beraz, ezta? Beraz, 0 eta 1-en permutazioak. Erabilera aurreko aztarnarik memoria honetan. Eta ez dugu jakingo benetan zer balioak dira, eta, beraz, normalean marrazteko ditugu galdera-marka gisa. Beraz, lehenengo gauza zentzuzkoa gara hemen egin nahi joan - eta utzi eremu hori ematen dit barruan erretiluak - ez dago izen bat. Zer egin behar du abiarazi zentzuzkoa dugu tamaina nahi dugu, nahi izanez gero, hasteko pila hau erabiliz? Steven: erretilua da sailkatuta 3. DAVID MALAN: Beraz, OK. Argi izan, gaitasun izendatu edonon hiru. Eta hori da erabiltzen dut array esleitu. Tamaina da erreferentzia joan zenbat erretiluak Une pilan. Steven: Zero. DAVID MALAN: Beraz, zero izan beharko luke. Beraz, aurrera, eta hatz edozein, marraztu tamaina zero da. Guztiak eskubidea. Beraz, orain, zer honen barruan da Hemen, ez dakigu. Hauek dira benetan besterik zabor balio. Beraz, galdera ikurrak marraztu izan dugu, baina taula garbi mantentzen dezagun orain ez baitu axola zer ez. Ez dugu behar array hasieratzean ezer, ezagutzen dugu hori delako pila tamaina zero da, bai, ez dugu ez litzateke ezer at bila array hau hala ere at Puntu honetan denbora. Orain, demagun bultzatzen duten I kopurua 9 pila gainean. Nola datu egitura eguneratu dugu hau beltza kutxa barruan? Zer behar balioak aldatzeko? Steven: barruan - tamaina? DAVID MALAN: OK. Tamaina zer izan behar du? Steven: Tamaina bat izango litzateke. DAVID MALAN: OK. Beraz tamaina bat bihurtu behar da. Beraz, egin dezakezu, pare modu batean. Dizute ematen dit, orain zure hatz borragoma bat da. Guztiak eskubidea. Gero, orain hatza eskuila bat da. Guztiak eskubidea. Eta orain, zer gehiago behar du aldatzeko, jakina, datu egitura? Steven: batetik gara behetik gora 9. DAVID MALAN: 9. Ados, Ona. Beraz, oraindik ez du axola zer at kokapena bat edo bi Oraindik dutelako zabor balio, baina ezin dugu traba ez bila tamaina delako gurekin kontatzea soilik lehen elementu hori benetan da legitimoa. Beraz, orain 17 bultza dut zerrenda gainean. Zer gertatzen da argazki hau? Steven: Beraz tamaina bi joan. DAVID MALAN: OK. Borragoma zara - trabatzen. Borragoma bat zara. Steven: Eraser. DAVID MALAN: eskuila bat zara. Steven: Brush. DAVID MALAN: OK. Eta zer gehiago? Steven: Eta gero dugu - DAVID MALAN: 17 bultzatu dugu. Steven: 17 itsatsiko ditugu gainean, eta, beraz - DAVID MALAN: OK, ona. Steven: - jaregin behera. DAVID MALAN: Eskubidea guztiak. Oso erraza da lortzean. Ez dut lagundu nahi baduzu, une honetan joan. Push 22. Steven: Done. Borragoma bat bilakatu da. Eskuila bat naiz bihurtuz. Eta, ondoren, 22 naiz jarriz. DAVID MALAN: 22. Bikain. Beraz, denbora gehiago. Orain naiz bultza joan pila 26 gainean. Steven: Ooh. Oh Gosh. Harrapatu duzula guardia me off. DAVID MALAN: Ez duzu ikus datozen? Steven: ez dut ikusi hau datozen. Ezin dugu berriro hasierako ahalmena? DAVID MALAN: Hori ona galdera bat da. Beraz, mota horretako dugu geure burua margotu txoko bat hemen. Benetan, ez da Steven izarrekin ona dugu egotzitako delako array honetan estatikoki, eta, beraz, hitz egiteko barruan datu egitura. Eta, funtsean, gogor egin dugu kodetuta tamaina hiru behar da. Beraz, ezin dugu benetan reallocate da. Dugu, ezin dugu atzera joan bada ere, dugu definitu erretiluak erakuslea bat izateko erabili dugu esku memoria malloc. Lortu dugu memoria galtzen delako malloc bidez zeure gara Orduan askatzea da. Uzten, baina aurretik, esan dezakegu reallocate memoria zatia handiagoa da, eguneratu erakusleak, eta abar. Baina, oraingoz, hau da, benetan onena egin ahal izango dugu. Push eta pop dira ustez joan Errore batzuk seinalea dute. Beraz, adibidez, gure ezartzeko Push boolearra itzuli ezin den Aurretik itzuli egia da, egia da, egia da. Baina, laugarren aldiz, behar da joan faltsua itzultzeko, adibidez. Guztiak eskubidea. Oso ondo egin. Zorionak. Irabazi duzun zure estresa baloia gaur. [Txaloak] Steven: Eskerrik asko. DAVID MALAN: Eskerrik asko. OK, beraz, ez dirudi askoz ere izango dira aurrerapauso bat da, ezta? Datuen egitura honetan deskribatu dugu. Oso sinesgarria izan, ezta? Sistema eragile gustatzen. Antza denez, web honen erabilera egin ahal izango dituzte, eta beste aplikazio oraindik. Baina, zer gertatuko mugarik ergelak Oraindik dugu ordenatu aste bi mugak kopiak non konpondu dugu tamaina array. Beraz, ez dira hain zuzen ere, pare bat modu hau konpondu ahal izan genuen. Dinamikoki izan dugu esleitu array, ez da zaila bidez kodetzea dut nik egiten da hemen, baina horren ordez berriro deklaratzen hau, besterik gabe, argi izan behar da, honen antzeko zerbait. Int * erretiluak, ez erabakitzeko edukiera oraindik. Baina pila adierazi dut beste nonbait nire kodea, orduan izan nuen deitu malloc, lortu pusketa baten helbidea memoria, eta esleitu ezin izan dut to erretiluak helbidea. Eta, ondoren, delako besterik pusketa bat memoria, jarraitu plaza erabili behar nuen parentesi ohiko modu idazkera. Berriro ere, ez delako hau moduko da funtzional multzo baliokidea eta memoria zatiak datozen atzera malloc from. Ko tratatu ahal izango dugu beste gisa erakuslea aritmetika erabiliz edo kortxetea idazkera. Beraz, hurbilketa bat da. Baina, nola liteke, bestela, hau ezartzeko dugu berean datu-egitura, potentzialki? Eskuin? Besterik ez dugu hau konpondu bezala sentitzen naiz Duela aste bat bezala arazoa. Zein izan da arazo honen konponbidea Steven horretan ran? Beraz lotuta zerrendak, eskuinera. Arazoa da ari garen pintura bada izkinan geure buruari esleitzeko arabera aldez memoria gutxi dugu hori Ondoren, nolabait aurre, ondo, zergatik ez, besterik gabe, hori saihesteko igorriko guztiz? Zergatik ez besterik deklaratzeko erretilu bat izan nahi nodo bat, ERGO lotuta zerrenda bat erakuslea, eta, gero, besterik gabe, berria esleitu nodo aldi bakoitzean Steven beharrezko bat egokitzeko Datuen egitura sartzen kopurua. Beraz, argazkia aldatu beharko lukete. Ez da garbi gisa, eta, izango hiru ints sorta bat bezain sinplea. Orain bat erakuslea bat izango da joan egitura, eta egitura hori joan izan int bat eta hurrengo erakuslea. Eramaten da joan erakuslea duten bidez hala nola, beste egitura hala nola, egitura bat. Beraz, irudi litzateke benetan Messier pixka bat. Dituzte eta geziak genuke tying dena elkarrekin. Baina hori fina, eskuinera, delako ikusi dugu hau nola egin. Eta behin erosoa lortu duzu ezartzeko lotutako baten antzeko zerbait zerrenda, horiek egin beharko duzu ez baduzu aukeratu hash taula bat ezarri nahi dituzten p-set 6 kateatzea bereiziak, dezakezu erabiltzen da eraikina bloke, edo bat bezala osagai edo Scratch hitz egiten da, prozedura, zerbait ipini duzun sortu zeure puzzle ahal izango dituzu, gero berrerabiltzeko. Beraz tradeoffs, baina, balizko irtenbideak dugun benetan, ikusi baino lehen. Beraz, sarritan, hori ikusten duzun bakoitzean urtean edo bi denean Apple oharrak zerbait berria, eta jendea ero guztiak line sortu Apple kanpo gorde beren marjinala erosi hardwarearen berritzea. Hau diot, OK da, izan ere, Pertsona horietako bat naiz. Beraz, zer nolako datuak egitura Errealitate hori irudikatzeko, agian? Beno, goazen deitu ilara bat, lerro bat. Beraz, British normalean deitu litzateke ilaran, hala ere, beraz, izen polita da. Eta bi eragiketak ilara enqueue bat deitu dugu onartzen izango funtzionamendu eta eragiketa bat adierazten du, diren antzeko espiritua eta bultza aterako. Besterik desberdinak sailkatu da konbentzio, zer ari gara horiek deituz. Baina zerbait esan nahi enqueue gehitu edo jarri da datu-egitura. To adierazten du esan nahi kentzeko. Baina pila bat LIFO datu bat izan zen, berriz, egitura, ilara lehen bat da, lehen datu-egitura da. Zara lerro lehen pertsonan bada, lehen pertsona heldu izango duzu lerro eta zure gailu berria erosteko. Imajinatu nola gelditu pertsona horiek izango Apple bada ordez erabiltzen pila bat egiteko, Adibidez, picking ezartzeko zure jostailu berriak sortu. Beraz, ilarak zentzurik, zalantzarik gabe, eta mota guztietako ahal izango dugula uste aplikazioak, ustez, ilarak, batez ere, zuzentasuna nahi duzun. Beraz, nola liteke hauek gauzatu ditugu datu egitura bat bezala? Beno, agian dugun proposatzen dut behar egiteko modu honetan. Beraz, orain zenbakiak noa. Beraz eduki eta erraza da, ez dugu nahitaez erretiluak dagokionez hitz egin. Just zenbakiak duten pertsona ahaztuak. Ahalmena da, joan, berriz ere, konpondu da pertsonak izan daitezke kopuru osoaren lerro honetan, hiru edo beste edozein balio. Baina, behar dut segimendua egiteko proposatzen dut ez bakarrik tamaina ilara, zenbat gauza dira bertan. Beraz, tamaina uneko tamaina, edukiera da gehienezko tamaina. Besterik gabe, berriro ere, nomenklatura konbentzio arabera. Zergatik gehigarri bat int barruan behar dut ilara pista mantentzeko nor en la line aurrean? Zergatik egin behar dela eta kasu honetan behar dut? Beno, nola irudi hau aldatu da? Ziurrenik ezin dut gehien berrerabiltzea argazki hau. Dezagun aurrera ni eta ezabatuko zer da hemen. Hau eman beharko dugu apur bat beste izen hemen. Gaitezen 17 kentzeko, gaitezen kentzeko 9 de, gaitezen 3 kentzeko. Eta dezagun gehi beste gauza bat da. Behar dut pista mantentzeko proposatzen dut zerrendaren aurrean, hau da, besterik gabe, int bat izan nahi du, bai eta joan. Eta erraza mantendu nahi dugu. Oraingoz zerrenda lotuta ez. Onartzen ari garen joan beharko dugu erliebe sortu muga horren aurka. Baina zer ikusi nahi dut gertatuko da denbora honetan? Beraz, demagun Aurrera joan nintzen eta lehenengo Pertsona ateratzen line, eta kopurua 9 da. Estresa pilotak izan dugu. Dezakezu, adibidez, lapurtzen dut bi edo hiru pertsona? Bat, bi, hiru? Goazen gora. Eskuin aurrean, eta, delako Egiteko hau azkar dugu. Duzun bakoitzean dago orain izango da line mutil Apple fan bat. Ez zaizu Apple hardware jasotzeko nahiz eta honen amaieran. Guztiak eskubidea. Oraindik duzun kopurua 9 Beraz, zauden zenbakia 17 zenbakia 22. Hauek arbitrarioak zenbakiak dira, adibidez, ikaslea identifikazioak edo whatnot. Eta besterik gabe, une batean, utzi hasiko gauzak gehituz hasteko. Eta taula exekutatu dut hemen une honetan. Beraz, kasu honetan, hasieratu dut aurrean behar diren - Egia esan, ez dut ez benetan axola zer aurrean dago, tamaina zero da delako. Beraz, hori baita, besterik gabe, galdera-marka bat izango da. Hauek dira galdera ikurrak dira. Beraz, orain hasiko da, benetan ikusi dugu zenbait pertsona sortu Hornigaia dendan. Beraz, zenbaki 9 bada, lehenengoa bazara han 5 etan, aurrera eta lerro sortu, edo gauean aurretik. Ados. Beraz, orain 9 da hemen. Beraz, 9 zerrenda aurrean dago. Beraz, aurrera eta eguneratu dut hau uneko datuak tamaina egitura ez da 0 izango dut, baina 1 izan behar. 9 jartzea at noa zerrendaren aurrean. Dezagun aurrera ni eta pantailan ezkutatu beraz, gurekin iragan ikus dezakegu hemen. Eta orain, zer nahi dut aurrean jarri? Segimendua noa dela ilara aurrean oraintxe kokapena 0 da. Zer da hurrengoa delako gertatuko? Beno, suposatzen dut enqueue 17 baita. Beraz, lerro han hop. Eta berriro, atearen sailkatu du denda da, hemen izango. Beraz, orain gehitu dut 17. Eta nahiz eta mutil hauek dira blokeatzea pantailan, hori OK, bertan ikus daitezke hemen. Sentitzen dut. Ikusleak: mugitu ahal izango dugu - DAVID MALAN: Ez, hori ongi. Han sortu erraldoia da. Beraz, gaur egun, 17 barruan ilara. Horrek eguneratu behar dut eremuak, nahiz eta gaur egun? Ados, zalantzarik tamaina. Eta nola aurrean zer? Ados, ez. Aurrean behar ez aldatzeko, izan ere, pila bat bezala, dugu nahi zuzentasuna mantentzeko. Beraz, bada, lehenengo 9 zen, 9 nahi dugu lerroa kanpo lehen izan da eta dendan sartu. Izan ere, ikus dezagun hori. Sartu dugu 22 baino lehen, dezagun aurrera eta adierazten du 9. Zein da zure izena berriro? Ikusleak: Jake. DAVID MALAN: Jake da joan dequeued behar da orain. Beraz, dendan sartu oinez duzu. Eta nahi duten denda han da. Beraz, orain zer - dit-dit-dit! Zer gertatuko da orain? Diseinua erabakia. Beraz, ez da txarra sena, baina - Zein da zure izena berriro? Ikusleak: David. DAVID MALAN: David. Beraz, zer egin zuen David? Konpondu datuak ordenatzeko izan zen saiatzen egitura eta mugimendua, bere kokapen Jake-en kokapen ohia da. Eta hori da fin gaude prest bada hori onartu behar bezala ezartzeko xehetasun. Baina lehen, dezagun eguneratzeko datuak egitura egin dugu aurretik. Dut ez delako guztiak ideia gustuko pertsona Ildo honetan ikusita. Big deal ez da David egiten bada urrats bat, baina berriro ere, uste itzuli denean izan dugu zortzi buruzko boluntario etapa eta txertatzeko atsegin dugu egin ordenatu, non hasi behar izan genuen guztiontzat inguruan mugitzen. Hori lortu garestia da, ezta? Horregatik, cringe big O buruz n, big n O karratu berriro. Ez da bezala sentitu Emaitza ezin hobea. Hargatik, besterik eguneratu. Ilara tamaina, beraz, Jada ez da 2. Gaur egun, ez da, besterik gabe, 1. Baina orain ezin dut eguneratu zerbait Nik ez dut eguneratu aurretik, zerrendaren aurrean. Besterik ezin dut esan, kokapena duten 1 da? Beraz, orain zabor balioa dugu hemen, zabor balioa hemen, eta David zabor honen erdialdera. Baina datu-egitura da, oraindik ere, oso-osorik. Eta, hain zuzen ere, ez dakit, nahiz eta behar aldatu Jake en lehengo zenbakia 9, nork zaintzen duelako. Nahikoa informazio izan dut gaur egun dauden tamaina jakin dut horrek pertsona bat hasi ilara honetan. Eta badakit, pertsona hori kokapena 1, ez da 0. Ez dut kontatuta. 1, beraz, bai. Beraz, datu egitura oraindik Ados. Beno, zer gertatzen da gero? Dezagun enqueue - Zein da zure izena? Ikusleak: Callen. DAVID MALAN: Callen. Dezagun enqueue Callen bat, eta 22 da orain ilaran. Beraz, orain zer egiten du hemen aldatzeko? Aurrean, ez da joan aldatu, jakina. Tamaina 2 izango da, berriz ere aldatuko. Eta 22an amaituko da hemen, eta 9, oraindik ere presente baina modu eraginkorrean bat da zabor balioa orain. Besterik ez da Jake iraganeko aztarna bat. Beraz, orain zer gertatzen bada David adierazten du dut? One azken eragiketa, adierazten du David. Mugitzeko, baina ezin izan dugu dezagun proposatzen dut ahalik eta lan gutxi egin. Orain nire datuak egitura doa tamaina atzera 2 eta 1. Baina ilara aurrean Gaur egun, 2 bilakatzen da. Ez dut behar zenbaki horiek aldatzeko besterik gabe, delako Oraindik besterik zabor balio. Baina orain zer gertatzen da? Demagun enqueue dut neure burua, 26? Sartzen ditut hemen bezala sentitzen dut. Beraz, naiz ari enqueued. Sartzen dira, beraz, mota horretako dut hemen. Eta nahiz eta ez nahiko egin duzu eskertzen honetan ikusmen agertokian, dugu gela ugari duelako, behar dut ez da hemen zutik, zergatik? Ikusleak: out zara mugetatik kanpo. DAVID MALAN: Right. Nago mugetatik kanpo. Haratago Nik indexatutako multzo honen mugetatik kanpo. Behar dut bat izango da hiru kokapenak. Orain, non da gehien natural joan? Dugu leveraged proposatzen dut aste bat trikimailu. The mod eragilea, portzentajea. Dut teknikoki delako delarik kokapena 3, baina ez dut beste 3 mod edukiera, 3, ehuneko ikurra, beraz, 3 - edukiera 3 da. Zer da hori? Zer gainerako orduan 3 zatitzen 3 duzu? 0. Beraz jartzen dit ziren Jake zen, hau da, benetan ona. Beraz, orain ezartzeko gauza hori egin ahal izateko joan buruhauste bat pixka bat izango da. Benetan, besterik gabe, lerro bat buruko min, kodea da. Baina, gutxienez, gaur egun, ez da zaborra balio du, baina ez da bi legitimoa ints hemen. Eta orain, hori egin dugu aldarrikatzen dut zehazki zer hain luze jo egin behar dugu Jake horrek zer aldatu dugu balioa izan zen, 26 izango dira. Gaur egun, oraindik ere, nahikoa informazioa osotasuna mantentzeko Datuen egitura hau. Oraindik dugu nolako kanpo zorte dugunean nahi edo lau gehiago, guztira txertatzeko elementuak, baina, gutxienez, ezin dut egin nahiko konstante erabilera eraginkorra denbora, hain zuzen ere. Ez dut nahi ikusita kezkatu guztiontzat, David en joera izan zen. Pilak buruzko edozein galdera, edo ilara hau? Ikusleak: horregatik tamaina jakin behar duzu, beraz, non pertsona bat izatea? DAVID MALAN: Horixe. Array tamaina jakin behar dut behar dut zehazki nola jakin behar delako balio horiek asko dira zilegi, eta, beraz, non ipini dut aurkitu ahal hurrengo pertsona. Zehazki. Tamaina da - egia esan, ez dugu eguneratu gabe. Gehitu dut neure burua 26. Tamaina da, gaur egun, ez da 1, baina 2. Beraz, orain hau, hain zuzen ere laguntzen aurkituko me zerrenda-burua, eta hori ez da 0, ez 1, baina 2. Zerrendaren aurrean da, hain zuzen ere, 22. Lehen zuen delako, eta, beraz, behar zuen egon dendan sartu onartzen nik baino lehen, nahiz eta ikusmen zutik dut denda hurbilago. Guztiak eskubidea? A txalo Kopako mutil hauek egiteko eta utzi egingo dugu bertan. [Txaloak] DAVID MALAN: utzi izan dut erretiluan dizu. Ikusi zer gertatzen bada genezake , nahi duzun, baina agian ez. Guztiak eskubidea. Beraz, orain ez duela utziko digu? Beno, utzi niri ez dagoela proposatzen da bat gutxi beste datu egiturak genezake hasteko gure tresna kit izango gehituz benetan izan nahiko, oso garrantzitsutzat jo murgiltze web stuff sartu dugu. Zein da berriro, konexio mota batzuk ditu inprimaki honen zuhaitzak zerbait izeneko DOM, dokumentu objektu eredua. Baina gehiago ikusiko dugu luze baino lehen. Let me definitionally proposatzen dugu deitu zuhaitz orain zer badakizu, baliteke familia zuhaitz bat, non gehiago izan hartan arbaso batzuk zuhaitzaren sustraiak. A patriarkal edo matriarch at oso Zuhaitzaren goiko. Bere ezkontidea izan gabe, kasu honetan. Baina orain, zer deitu dugu seme-alabak dira, nodo zintzilikatzeko Umearen ezkerreko edo eskuineko umea off, geziak irudikatu hemen. Alegia, zuhaitz bat datuak egitura batean ordenagailuan, zuhaitz bat du zero edo gehiago nodoak. Gutxienez bat nodoa dauka bada, deitzen duten erro. Gauzak ikusmen hori da marraztu goialdean dugu. Eta nodo hori, beste edozein nodo bezala, ahal dute, zero, bat, edo bi, edo hiru, o Hala ere, askok seme-alabak Datuen egitura onartzen. Kasu honetan, erroa, gordetzeko balio bat, bi seme-alaba ditu, 2 eta 3, beraz, deitu dugu, oro har, 2 Ezkerraldean haur eta 3 seme-alaba izateko eskubidea. Eta orduan, behera iritsi gara, 5, 6, eta 7, 6 deitu daiteke, erdiko umea. Duzu, lau seme-alaba bada, nahasgarria xelebrea. Beraz, mota horretako erabiltzeari utzi dugu laster-hitzez du. Baina benetan familiako zuhaitz bat. Eta hostoak hemen nodoak direla seme-alabek ez dute beren burua. Off zintzilikatu dute zuhaitz behealdean. Beraz, nola liteke zuhaitz bat ezartzen dugu du besterik Gehienez bi seme-alaba? Deitu bitar zuhaitz bat dugu. Bi berriro bi esanahia honetan kasuan, bitar bezala. Eta, beraz, zero, bat izan daiteke, edo Gehienez bi seme-alaba. Ezartzea proposatzen dugu nodo dut int n bat egitura dela-eta, eta, ondoren, bi erakusleak, bat deitzen ezkerrera, eskuinera izeneko bat. Baina besterik ez dira polita konbentzio arbitrarioa. Eta zer polita da gaur egun, batez ere baduzu mota borrokatu kontzeptualki batera errekurtsibitate, edo pentsatu ez zela benetan ezer irtenbide bat, bereziki, ezin izan bada agortu memoria. Orain dela datuak buruz ari gara hitz egiten egiturak eta algoritmoak aukera ematen duten zeharkatuko dugu manipulatzeko, bihurtzen errekurtsio datorren itzuli askoz sinesgarria ez bada modu ederra. Hau proposatzen dut ezartzeko da, beraz, Search Funtzio bat. Emandako bi sarrera - beraz, uste kutxa beltz bat bezala. Emandako bi sarrera, n, int, eta bat zuhaitz baten erakusle baten erakuslea nodoa, edo benetan zuhaitz baten erroa, I erreklamazioa funtzio honek dezake itzultzeko egia edo gezurra, balio n Zuhaitz hau da barrutik. Zer da hau kutxa beltza barrutik da? Beno, lau adarretan. Lehen besterik ez egiaztatzen du. Zuhaitz null bada, faltsua besterik ez itzultzeko. Han nodo ez bada, ez dago n ez da, han-zenbakia ez da, besterik gabe itzultzeko faltsua. Arren, n, balio badu bilatzen ari zaren , ez da zuhaitz gezi-n baino txikiagoa da, eta besterik gabe, argi eta garbi izan behar du, zer esan nahi denean Zuhaitz eta, ondoren, gezi idazten dut idazkera, n? Zehazki. Dereference esan nahi duten erakuslea izeneko zuhaitza. Hara joan, eta, ondoren, horren barruan lortu nodo eta bere eremuan izeneko n. Eta gero, konparatu benetako n zela aurka Search pasa. Beraz, bada, n, n balioa baino txikiagoa Zuhaitz nodo berez, bai, Zer esan nahi du? Horrek esan nahi du ezer ez, lehen begiratuan. Eskuin? Just like denean array bat izatea balioak, nahi bitar aplikatzen dezakezu arraila moduan bilatu eta konkistatzeko. Baina, zer bereganatzeak ez zuen egin behar dugu binary bilaketa guztietan lan egiteko telefono-liburua eta lehenago adibideak? Nola ordenatuko da. Hargatik zehatzagoak zuhaitz definizioa Hemen ez da, besterik gabe, zuhaitz bat, ezin izango da dute seme-alaben kopurua edozein. Ez bakarrik bitar zuhaitz bat, eta horrek dute 0, 1, 2 edo Gehienez. Baina bilaketa zuhaitz bitarra, edo udako ordutegian gisa, hau da, besterik gabe, esaten modu dotore bat hala nola, zuhaitz bitar nodo guztien duten Ezkerraldean haurra, baldin badago, ez da nodo baino gutxiago. Eta nodo bakoitzean eskubidea haurra, badaude, handiagoa da nodo bera baino. Beraz, hitz beste, izan ziren baduzu marraztu Zuhaitz dira, zenbaki guztiak dira arretaz hau atsegin orekatua beraz, gero 55 izan duzu erro gisa, 33 joan bere ezker dela 55 baino gutxiago delako. 77 dezake bere eskubidea delako joan 55 baino handiagoa da. Baina orain konturatzen, beraren definizioa, errekurtsiboaren definizio bat da, ahoz, ditu 33 eskatzeko. 33 en ezker umea baino gutxiago izan behar du, eta 33 seme-alabak eskubidea, 44, behar izan hura baino handiagoa da. Beraz, hau bilaketa zuhaitz bitarra da, eta , Proposatzen dut pixka bat erabiliz errekurtsibitate, orain aurkituko ditugu n. Hala bada n balio n hori baino gutxiago egungo nodoa, joan naiz Animatu eta punt, eta, beraz, hitz egiteko, eta, besterik gabe, itzultzeko, edozein dela erantzun da n bilatzen du Zuhaitz horrek ezkerreko umea. Iragarki berriro, funtzio honetan bakarrik nodo bat izar bat espero du nodo bat erakuslea. Beraz, ziur asko, besterik ezin dut egin zuhaitz ezkerrera gezi, eta ekar Niri nodo bat. Baina zer nodo hori? Beno, eta deklarazio honen arabera, ezkerretara erakuslea besterik ez da, beraz, besterik ez da esan nahi du, bilaketa-funtzioa dut igaro desberdinak erakuslea, hain zuzen bat dagoela adierazten du nire ezker haurraren zuhaitz. Beraz, kasu honetan, erakuslea 33, bada hau gure lagina sarrera Bitartean, bada n da n balioa baino handiagoa Zuhaitz nodo oraingoa, orduan naiz Animatu eta punt joan beste joan norabidea, eta besterik esan, ez dut ezagutzen balioa n zuhaitza bada, baina bada ezagutu dut, behera da nire eskuineko adarraren, nolabait esateko. Hargatik errekurtsiboki Call me bilatzeko, n bat pasa eta berriro, baina bat igaro nire eskuineko umea erakuslea. Bestela esanda, gaur egun, naiz bada 55 99 eta bila nabil, badakit hori 99 da 55 baino handiagoa da, eta, beraz, besterik gabe, atsegin dut Tore telefono-liburua duela eta gu joan eskubidea, era berean gaude hemen joan behar. Eta ez dakit nire eskubidea zuen bada haurra, eta ez da, 77 hor dago, baina Da norabide horretan jakin nuen. Beraz, bilaketa deitu dut nire seme-alaba eskuinean, 77, eta utzi bilaketa zifra kanpotik ez arbitrarioa honetan 99 bada Adibidez, ez da benetan. Bestela, azken kasuan zer da? Zuhaitz bada null bat kasua da. N da nodoa oraingoa baino txikiagoa bada balioa kasu bat da. N da, oraingoa baino handiagoa bada nodo balio hirugarren kasu bat da. Zer Laugarren eta azken kasua da? Ari gara kasu, uste dut, ezta? N izan dela da behar egungo nodo duten nago. Beraz, bada, 55 dut puntu honetan bilatzen Ipuinean, adar hori Zuhaitz egia itzuliko litzateke. Beraz, zer da interesgarria hemen dugu benetan, iragan asteetan ez bezala, ez dugu mota dute bi oinarri kasu. Eta ez dute nahi guztiak izango dira goialdean. Goiko oinarri-kasu bat da, baldin eta delako Zuhaitz nulua da, ez da ezer egin behar da. Just itzultzeko gogor bat kodetuak faltsua balioa. Behean adarra den moduko da lehenetsia, beraz dugu bada hautatuta nulua, hautatuta dugu eta izan beharko bada utzi, baina ez luke izan behar, dugu hautatuta eskubidea duela behar bada, baina ez du izan behar, argi izan behar ditu eskubidea non gauden. Duten oinarri-kasu bat da. Beraz, ez da bi kasuetan recursive sandwiched ez erdian. Baina idatzi nuen Hori edozein. Pentsatu dut sentitu mota da naturala lehenengo posible akats egiaztatzeko, hautatu utzi eta, ondoren, eskuinera begiratu, eta gero bere gain nodo batean zaudela benetan ari zaren bila. Beraz, zergatik ez litzateke baliagarria? Beraz bihurtzen da - eta utzi egin beharko aurkezpenik niretzat hemen web da. Ez da erabiltzen hasteko goaz programatzeko lehen hizkuntza, baina markaketa hizkuntza. Ko hori izateaz markaketa hizkuntza programazio espiritua antzekoak hizkuntza, baina ez du ematen dizu gaitasuna zeure burua adierazteko logikoki. Bakarrik ematen dizu gaitasuna adierazteko zeuk egituraz. Non zerbait jarri nahi duzun orrian, web orria? Zer kolorea ez da egin nahi duzu? Zer da letra-tamaina utzi egin nahi duzu? Zer hitz egiten duzu benetan web orrian nahi? Beraz, markaketa hizkuntza bat da. Baina, gero, oso azkar egingo dugu aurkezten Ikusteko Javascript-a, hau da, osoko fledged Hizkuntza programazioa. Argazkiak, sintaktikoki oso antzekoak C, baina ahal izango da polita, ahaltsuagoa gehiago lagungarri ezaugarri. Eta frustrazio bat honetan seihilekoan puntua da hori egiten zaitugu laster ezartzea speller urrun gutxiago kode lerro beste hizkuntza erabiliz C bera baino aukera ematen du, baina arrazoi-en laster ikusiko dugu ulertzen. Lehenengo, hala nola, web orrian egongo dira. Erabat underwhelming izango da, lehenengoa dugu. Izango da, besterik gabe, esan, Kaixo mundua. Baina nik inoiz ez baduzu ikusi baino lehen, hau da, HTML, Hipertestua Markatzeko lengoaia. Jakin bat menuko aukera bazoaz en gehien Edozein nabigatzailean, web orrian edozein an Internet, HTML ikusi ahal izango dituzu pertsona batzuek idatzi zuen Sortu web orri hori. Eta, seguruenik, ez da ez itxura labur edo hau neat. Baina horien eredua jarraitu egingo du parentesi irekiak eta barrak eta letrak eta zenbakiak izan daitezkeen. Emango dizu nuke esaldi bat pentsatu nuen zer egin ahal izango dute egin dituzun CS50 hartu ondoren. Demagun joan cs.harvard.edu / rob me, gure Rob Bowden en orri nagusia. Hau egin zuen guretzat. Beraz, laster ahal izango duzu horretarako. Eta, era berean, zer entzun Gaur goizean - zer goizean entzun duzu - [Hamster Dance Music] - You'll gai izan hau egiteko. Duten zain gurekin asteazkenean. Duzu ikusten dugu gero. [Hamster Dance Music] DAVID MALAN: hurrengo CS50 At -