[Powered by Google Translate] [Aste 6, Continúa] [David J. Malan] [Harvardeko Unibertsitateko] [Hau da CS50.] [CS50.TV] Hau CS50 da eta 6 aste bukaera honetan. Beraz CS50x, Harvard lehen kurtsoak parte hartzen, edX ekimen bat hain zuzen ere, estreinatu iraganeko astelehenean. Besteek ohi bat lortzeko Interneten nahi baduzu batera jarraituz, x.cs50.net dezakezu buru. Leku egokia edx.org redirect egingo duzun, non MIT eta Berkeley beste ikastaro hau eta gaur egun bizi izan zen. Saioa hasi kontu bat duzu; materiala aurkitu da, neurri handi batean, bera duzu duzun izan seihileko honetan, aste batzuk atzeratu egin bada ere, lortuko dugu dena prest. Baina zer gertatzen da CS50x ikasle egingo da orain ikusi nahiko honetan bezala interfaze bat da. Honek, esate baterako, Zamyla arazo multzo 0 Bisita gidatua buru da. To edx.org saioa hasi ondoren, ikaslearen CS50x bat ikusten gauza mota espero ikastaro batean ikusten duzu: astelehenetik hitzaldia, Asteazkena, hainbat film laburrak, arazo multzo, walkthroughs, PDFak hitzaldia. Horrez gain, ikusten duzu hemen, makina itzulpenak Txinako, Japoniako, Espainiako, Italian sartu transkripzioak English, eta beste hizkuntza batzuetan sorta osoa zalantzarik izan Inperfektua roll diegu bezala programazioaren zerbait izeneko API bat erabiliz, edo aplikazio programazio interfazea da, Google aukera ematen duen beste hizkuntza horiek bihurtu English digu. Baina ehun-plus boluntario batzuk espiritua wonderful esker, ausazko Interneten atsegin handiz eskaintzen duten pertsonen parte hartzea Proiektu honetan, pixkanaka-pixkanaka dugu itzulpen horien kalitatea hobetzeko gizakiak gure ordenagailuak egin dituzten akatsak zuzendu beharrik. 

Beraz, ikasle gehiago batzuk out genuen erakusten sortu Astelehena, hasieran uste genuena baino espero bihurtzen da. Izan ere, gaur egun CS50x 100.000 pertsona batera etxean. Beraz, parte konturatzen dira Ikastaro hau egiteko informatika klase inaugurazio honetan hezkuntza gehiago, oro har, oro har, erabilgarri. Eta errealitatea da gaur egun, online ikastaroak masiboa horiek batzuk batera, zenbaki horiek oso altua dute hasteko, badirudi hemen egin dugun bezala. Baina helburua, azken finean, CS50x da benetan hainbat pertsona line akabera ahalik eta. Diseinua, CS50x da hau iragan astelehenean eskainiko April 15, 2013 bidez, beraz, eskola konpromisoak folks duten beste nonbait, lana, familia, beste gatazka eta bezala, pixka bat gehiago malgutasuna Ikastaro honetan murgiltzea duten, izan ere, nahikoa esan nahi du, nahiko ambitiously egin bada bakarrik seihilekoan zehar ohiko hiru hilabete osoan zehar. Hala ere, ikasle horiek aurre arazo multzo berean, eduki bera begiratzen, bera bezala, film labur eta sarbidea izatea. Beraz, konturatzen garela denak elkarrekin hau benetan. Eta CS50x azken helburu bat ez da bakarrik hainbat Folks helmugan eta emateko informatika ulertzeko newfound hau eta programazioa, baina baita esperientzia hori partekatua izatea. One campusean 50 ezaugarriak definitzeko, espero dugu, esperientzia komunetan sort hau da, batzuetan, onerako zein txarrerako, baina pertsona horiek ezkerrera eta eskuinera biratu beharrik, eta bulego ordu eta hackathon eta azoka. Pixka bat zailagoa da horretarako folks online pertsona, baina CS50x apirilean amaituko inoiz lehen CS50 Expo arrazoizko gure ideia egokitzapena online bat izango da non milaka ikasle horiek guztiak gonbidatu 1 aurkeztu - 2 minutuko bideoa, bai bere proiektua behin betiko edo bideo Screencast kaixo agurtzen eta bere proiektua buruz hitz egiten du eta demoing zure aurrekoek bezala askoz hemen egin campus arrazoizko beraz, seihilekoa amaitu, esperantza global erakusketa bat izan da ikasle CS50x 'azken proiektuak, askoz zure zain dago abenduaren Hemen campusean. Beraz, datozen hilabeteetan. 

Hala ere, 100.000 ikasle gehiago batzuk CAk beharra dator. Kontuan hartuta duzu guys pista ondo moldatuko hemen eta CS50 hartu Material hau edX on folks-oharra aldez aurretik hainbat aste, konturatzen love genuke gure ikasle propioa ahalik eta ekimen honetan parte hartzea, bai seihilekoan, baita neguan zehar eta udaberri honetan. Beraz, nahi CS50x parte hartzen duten nahi duzun, eztabaidatzeko CS50x, CS50 eztabaidatzeko bertsio edX bereziki parte hartu, asko dira campus erabiliz, online iragarki-oholean, mesedez egin URL burua, nor zaren ezagutzen laguntzen digu, ikasle eta langile talde bat sortu eta fakultateko alike love litzaidake delako campusean dira, besterik gabe, batera jolasten eta laguntzen. Die ezaguna da galdera bat ikusten dute, ikasle bat bug batzuk berri nonbait ez dago herrialde batzuetan Interneten entzuten baduzu, eta eraztunak hori kanpai baten ere gai hori bera izan delako d-aretoa aspaldi, zorionez gero chime dezakezu eta zure esperientzia. Beraz, mesedez ez nahi duzu partake. 

Harvard Informatika ikastaroak tradizio bat apur bat, Horien artean CS50, jantziak batzuk, arropa batzuk, higadura harro dezakezu seihilekoa amaitu aurretik, nahiko harro esaten amaitu duzula CS50 eta hartu CS50 eta antzekoak, eta beti saiatu gara ikasle inplikatzeko prozesu hau ahalik eta gehien, beraz dugu gonbidatu, seihilekoan garai honen inguruan, ikasleek diseinuak aurkeztu Photoshop erabiliz, edo edozein tresna aukeratu erabili nahi duzun Oraindik diseinatzaile bat izanez gero, kamisetak eta izerditakoak diseinu aurkeztu eta aterkiak eta bandanas little txakurrak izan dugu eta. Eta dena, ondoren, irabazleak urte bakoitzeko ondoren ikusgai ikastaroa store.cs50.net web orrian. Dena kostua han saltzen, baina web bera exekutatzen eta pertsona nahi duten kolore eta diseinuak aukeratzeko aukera ematen du. Beraz, besterik ez genuke partekatzeko iaz diseinu batzuk pentsatu nuen web honetan hemen, gainera, horrek urteko tradizio bat da. "Every Day Faultn naiz seg" bidalketa bat izan zen iaz, hau da, oraindik ez dago erabilgarri ikasle ohientzat. Ko hau izan genuen, "CS50, sortu zen 1989." Gure Bowdens bat, Rob, oso ospetsua izan zen iaz. "Team Bowden" jaio zen, diseinu hau aurkeztu, top saltzaileen artean. As bat izan zen hau hemen. Jende askok izan "Bowden Fever" Salmenta egunkariak arabera. Konturatzen hori, eta ezin izango zure diseinua dago, Interneten. Honi buruzko xehetasun gehiago hurrengo arazoa etorri ezarri du. 

One tresna gehiago: esposizio batzuk izan duzun, eta, zorionez, gaur egun GDB esperientzia eskuak-on batzuk, hau da, jakina, araztailea eta, horri esker manipulatzeko duzu nahiko maila baxua programa, zer mota gauzak egiten? Zer esan nahi du GDB utzi egin nahi duzu? Bai? Give me zerbait. [Ikasleentzako erantzuna, ulertezina] Good. Funtzioa sartu urratsa, eta, beraz, ez duzu besterik ez exekutatu idatzi eta bere osotasunean programaren bidez kolpe, inprimatzeko gauzak irteera estandarrean. Honako beharrean, hari line bidez dezakezu urratsa line, bai hurrengo idazten urratsa funtzio bat murgiltzea, normalean bat idatzi lerro bat edo lerro lerro joan. Zer gehiago ez GDB utzi egin nahi duzu? Bai? [Ikasleentzako erantzuna, ulertezina] Inprimatu variables. Beraz, bada Historia II txiki bat egin nahi duzun zure programaren barruan printf adierazpenak leku osoko idatziz jo beharrik gabe, bakarrik inprima dezakezu aldagai edo aldagai bat erakutsi. Zer gehiago egin dezaket GDB bezala araztaileak duzu? [Ikasleentzako erantzuna, ulertezina] Hain zuzen ere. Eten - puntu ezar dezakezu; break exekuzioa esan daiteke nagusia funtzioa edo foo funtzioa. Break line 123 exekuzioa esan daiteke. Eta teknika oso indartsu bat eten - puntu zentzu orokor bat behar duzu, non zure arazoa delako ziurrenik da, ez duzu denbora alferrik programa osotasunean bidez hurrats. Funtsean jauzi egin ahal izango duzu bertan, eta gero hasi idazten bidez, hurrengo urratsa edo edo antzeko hurrats. Baina GDB antzeko zerbait harrapatzen da laguntzen dela, giza zure arazoak aurkitu eta zure bugs aurkitu. Ez du zertan bilatu hainbeste. 

Beraz, beste egun style50 sartu dugu, komando-lerroko tresna labur bat da saiatuko da zure kodea estilizatzeko apur bat gehiago garbian zu baino, giza, egin izan dezake. Baina hori ere, benetan, gauza bat besterik ez estetikoa. Baina deitzen Valgrind beste tresna hori da apur bat gehiago arcane erabili out bihurtzen da. Lehen begiratuan atrociously críptica Bere irteera da. Baina wonderfully erabilgarria da, batez ere, gaur egun, epe parte garela Oraindik non malloc eta dinamikoa memoria esleitzeko erabiltzen ari zaren hasita. Gauzak benetan, benetan gaizki joan daiteke azkar. Ahaztu duzu zure memoria libratzeko nahi izanez gero, edo NULL erakuslea batzuk dereference delako, edo zabor erakuslea batzuk dereference duzu, zer da normalean sintoma emaitzarik? Errua seg. Eta kilobyteko edo megabyte kopuru batzuk fitxategia-core hau lortuko duzu zure programa memorian egoera adierazten denean huts egin du, baina, azken finean, zure programa matxurak seg, segmentaziuo hutsegitea horrek esan nahi du zerbait txarra gertatu zen ia beti lotutako memoria-akatsa egin duzula nonbait. Beraz Valgrind laguntzen hau bezalako gauzak aurkituko dituzu. Exekutatzen duzun tresna bat da, GDB duzun bezala, zure programa konpilatu ondoren, baina baino gehiago exekutatu programa zuzenean, Valgrind exekutatzen duzun eta gainditu behar duzu zure programa, bezala egin GDB duzu. Orain, erabilera, irteera mota onena lortzeko, apur bat luzea da, eta, beraz, bertan pantailaren gainean Valgrind-v ikusiko duzu. "-V" ia unibertsalena esan nahi du verbose programak erabiltzen ari zaren ordenagailuan Linux. Beraz, txu default dezakezu datuen baino gehiago esan nahi du. "- Leak-check = full." Hau besterik ez da memoria ahalik eta filtrazioen check esaten, akatsak egiten dut dezake. Hau ere, programak Linux paradigma komun bat da. Oro har, komando-lerroko argumentu "" aldatu da, ustezko programaren portaera aldatzeko, eta letra bakar bat da, da-v, baina hori aldatu egin da, besterik ez programatzailea diseinua, hitza edo hitz zenbait osoa da, komando-lerroko argumentu bat hasten da. Hauek besterik ez dira giza konbentzioak, baina gero eta gehiago ikusiko duzu. Eta gero, azkenik, "a.out" hau adibide jakin programaren izena arbitrarioa da. Eta hemen zenbait ordezkari irteera. 

Zer esan liteke esan nahi dugu aurretik, utzi baino gehiago joan me kodea snippet hemen. Eta hau mugitu me bidea utzi, coming soon, eta dezagun memory.c, adibide labur hau hemen begirada bat. Beraz, programa honetan, utzi gerturatzeko me funtzioak eta galderak. Funtzio nagusia funtzio bat deitzen ditugu, f, eta, ondoren, zer f aurrera jarraitzeko, ingelesa pixka bat teknikoa? Zer esan nahi du f jarraitu egin? How about line 20 dut hasteko, eta izarraren kokapena ez du axola, baina besterik ez dut koherentea hemen azken hitzaldia. Zer da line 20 ez Gurekin? Ezkerraldeko On. Apurtu dugu behera gehiago. Int * x: zer ari da hori egiten? Ongi da. Erakuslea geratuko da, eta, gaur egun, dezagun are gehiago teknikoak. Zer esan nahi du, batez bestekoa oso zehazki, erakuslea deklaratzeko? Beste norbaitek? Bai? [Ikasleentzako erantzuna, ulertezina] urrunegi. Beraz, berdin ikurra eskuinaldean irakurtzen ari zaren. Dezagun fokua ezkerretara, int * x. Honek ez du "aldarrikatu" erakuslea bat, baina orain dezagun definizio hori sakonago artelan. Zer esan nahi du zehazki, teknikoki esan nahi du? Bai? [Ikasleentzako erantzuna, ulertezina] Ongi da. Helbide bat gordetzeko memoria prestatzen ari da. Good. Eta dezagun urrats bat gehiago nahi izanez gero, aldagai bat, x, 32 bits da deklaratzen. Eta 32 bits delako ezagutzen dut? Ez da int bat delako, baina kasu honetan erakuslea delako. Kasualitatea dela bat eta bera int batekin, baina ez dagoela izarra esan nahi du, hau da erakuslea da eta aparatuaren, ordenagailu askotan gertatzen den bezala, baina ez guztiak, erakusleak 32 bit dira. MACS azken, azken ordenagailu bezala moderno hardware On gehiago, 64-bit erakusle izan dezakezu, baina aparatuaren, gauza horiek 32 bit dira. Beraz, normalizatzeko dugu. Zehazki, ipuin honela doa: "Aldarrikatu" erakuslea; zer esan nahi du horrek? Memoria-helbide bat gorde prestatzen ditugu. Zer esan nahi du horrek? X aldagaia deitzen hartzen duen 32 bits sortu dugu laster izango da zenbaki oso bat gorde helbidea. Eta hori da ziurrenik bezala zehatzak gara. Fina da mundua sinplifikatzeko aurrera, eta bakarrik esan deklaratzeko x izeneko erakuslea. Deklaratu erakuslea, baina konturatzen eta ulertzen zer benetan gertatzen ari nahiz eta batzuk besterik ez duten pertsonaiak. 

Orain, hau da, ia pixka bat errazagoa da, nahiz eta adierazpen bat luzeagoa da. Beraz, zer da hau, egiten ari den nabarmenduta, gaur egun: "malloc (10 * sizeof (int));" Bai? [Ikasleentzako erantzuna, ulertezina] Good. Eta han hartuko dut. Zatia memoria esleitzean hamar zenbaki osoen da. Eta orain apur bat sakonago murgiltze; zatia hamar zenbaki osoen memoria esleitzean da. Zer da malloc gero itzuli? Zatia horren helbidea, edo, zehazkiago, zatia horren lehenengo byte helbidea. Nola ondoren am I, programatzailea, jakin non zatia memoria amaitzen da hori? Dela Alboko ezagutzen dut. Malloc, definizioz, duzu emango zatia memoria alboko bat. Hutsuneak No. Zatia horretan byte guztietan sarbidea behar duzu, itzuli Itzuli, baina nola ez non zatia memoria honen amaiera izango da ezagutzen dut? Malloc erabili nahi duzun? [Ikasleentzako erantzuna, ulertezina] Good. Ez duzu. Gogoratu behar duzu. Nituen 10 balioa gogoratu behar dut, eta ez dut, nahiz eta badirudi egin hemen. Baina onus me on da oso-osorik. Strlen, bihurtu dugu apur bat mende on kateak, hitzarmen hau \ 0 izatea delako soilik funtzionatzen edo NULUAK pertsonaia berezi hau, NULUAK, kate baten amaieran. Horrek ez du memoria zatiak arbitrarioak mantendu. Sortu da. Line 20 Beraz, ondoren, memoria zatia esleitzen hamar zenbaki osoak gordetzeko, eta lehen bytea helbidea gordetzen da zatia izeneko aldagaia x memoria hori. Ergo, erakuslea da. Linea 21 Beraz, zoritxarrez, akats bat izan zen. Baina, lehenik eta behin, zer egiten da? Denda da esaten kokapena 10, 0 indexed x balioa 0 izeneko memoria zatia. 

Beraz, gauza pare bat ari da nabarituko. Nahiz eta x erakuslea da, duela pare aste gogoratzen array-style kortxetea notazioa oraindik ere erabili ahal izango dituzu. Hori benetan labur-eskuko erakuslea críptica begira aritmetika idazkera. non honen antzeko zerbait egin genuke: Hartu helbidea x, mugitu 10 lekuak baino gehiago, ondoren, bertan agertutako edozein izanda ere helbidea da kokaleku horretan gordetzen da. Baina, Egia, hau besterik ez da atrocious irakurri eta eroso. Beraz, mundu karratu normalean erabiltzen baizik askoz gehiago giza-friendly irakurri da parentesi artean. Baina zer benetan kanpaia azpian; x helbide bat, ez da array bat, per se. Beraz, hau da, 0 gordetzeko kokapena 10 x. Zergatik da txarra? Bai? [Ikasleentzako erantzuna, ulertezina] Zehazki. Esleitu hamar ints bakarrik, baina 0-tik C programazioa, 0 1 2 3 4 5 6 7 8 9, baina ez 10 sartzeko aukera izango duzu. Beraz, bai programa seg errua joan edo ez da. Hala ere, ez dugu benetan ezagutzeko; portaera nondeterministic sort da. Lortuko dugu zortea ala ez benetan araberakoa da. Bihurtzen da sistema eragilearen ez dela axola erabiltzen dut extra byte hori bada, nahiz eta ez du ematen dit, nire programa agian ez du huts egin. Gordinak da, buggy da, baina agian ez duzu sintoma hori ikus edo pixka bat behin bakarrik ikusi ahal izango duzu. Baina errealitatea da bug hau da, hain zuzen ere, ez dago. Eta benetan problematikoa da zuzena izan nahi duzun programa bat idatzi duzun, programa saltzen duzula pertsona bakoitzak behin pixka bat kraskatzen erabiliz zeren, noski, hori ez da ona. Izan ere, Android telefono bat edo iPhone bat behar duzu bada eta apps download duzu egun hauetan, duzun, inoiz izan bada, aplikazio bat besterik ez irten, Bat-batean desagertzen da, ia beti memoria-lotutako arazo batzuen ondorioz, Horren bidez, programatzailea izorratu sortu eta dereferenced erakuslea zuen edo ez izan behar zuen, eta iOS edo Android ondorioz hil programa guztiz baizik eta undefined arrisku portaera edo segurtasun konpromiso mota batzuk baino. 

Programa honetan beste bug hau gain. Zer gehiago izorratu nuen programa hau? Ez dut praktikatzen zer Predicada dut. Bai? [Ikasleentzako erantzuna, ulertezina] Good. Ez dut askatuko memoria. Thumb araua Beraz, malloc anytime deitu, deitu free behar duzu zaudenean egin memoria hori erabiliz. Orain, memoria hau libre nahi dut? Beharbada, lehen lerro hau zuzena zen suposatuz, hemen egin nahi nuke. Izan dut ez duelako, esate baterako, egin du behera hemen. Zergatik? Just out esparrua. Beraz, nahiz eta erakusleak buruz ari gara hitz egiten, aste honetan 2 edo 3 gai, non x giltza kizkur izendatu zuten barruan esparrua da bakarrik. Ahal izateko behin betiko duzu ez askatzea han. Nire aukera bakarra libre gutxi gorabehera line 21 ondoren. Hau nahiko simple programa bat da, nahiko erraza izan da mota bilduta behin your mind zer inguruko programa egiten da, non akatsak izan ziren. Eta nahiz eta ez ikusiko duzu lehen, zorionez, apur bat begi-bistakoa da gaur egun akats horiek nahiko erraz konpondu eta erraz egin. Baina programa bat da, 12 lerro baino gehiago, 50 lerro 100 lerro, Zure kodea line bidez lerro oinez, pentsatzen bidez logikoki, posible da, baina ez bereziki dibertigarria da, etengabe bugs bila, eta, gainera, oso zaila egin, eta horregatik Valgrind bezalako tresna bat badago. Dezagun aurrera eta hau egin: nire terminal-leihoa ireki me utzi, eta ez me exekutatu memoria, memoria dirudi fina izan delako. Zortea dut. Array amaieran osagarriak byte hori Going ez dirudi ere arazoak izan. Baina me, hala ere, ez behatu check, besterik gabe esan nahi du egiaztatu ala ez, hau da, benetan zuzena. 

Beraz, egin dezagun valgrind-v - leak-check = full, eta, ondoren, kasu honetan programaren memoria, ez a.out da. Beraz, aurrera eta hau egin. Sakatu Sartu. Dear God. Honek bere irteera da, hau da, zer aipatu lehenago dut. Baina, ikasten zentzugabekeria guztiak, irakurri hemen, honen diagnostiko-irteera ez da interesgarria da. Zein da zure begiak benetan nahi dira bilatzen, edozein akats edo baliogabea aipamen da. Hitz dituzten arazoak. Eta, hain zuzen ere, zer oker joan behera hemen-en. Nolabaiteko laburpena, behar dut "erabiltzen irtetean: 40 byte 1 blokeak" Egia esan, ez nago ziur zer bloke bat da oraindik, baina 40 byte benetan sentitzen dut irudikatu bezala, non den datozen. 40 byte. Zergatik dira 40 byte irtetean erabiltzen? Eta, zehazki, joan gara behera hemen, zergatik 40 byte behin betiko galdu dut? Bai? [Ikasleentzako erantzuna, ulertezina] Perfect. Bai, hain zuzen. Baziren hamar zenbaki osoen, eta horietako bakoitzean 4 edo 32 bit tamaina da, beraz, galdu dut hain zuzen ere, 40 byte izan ere, zuk proposatu bezala, ez dut deitu free. Hau bug bat da, eta, gaur egun, utzi behera begiratu apur bat gehiago nahi izanez gero, ikusi eta ondoan, "Baliogabea tamaina 4 idazteko." Zer da hau? Helbide hau adierazten zer oinarri notazioa, itxuraz? Hau hamaseitarra da, eta edozein momentutan zenbaki bat 0x ekin hasten diren ikusiko duzu, hamaseitarra esan nahi du, eta horrek, nire ustez, pset 0 galderak atalean egin dugu, besterik ez zen warmup ariketa bat egin ahal izateko, hex hamartar bihurtzeko bitar eta abar. Hamaseitar, konbentzio giza, ohi da erakusleak irudikatzeko erabiltzen edo, oro har, helbideak. Konbentzio bat besterik ez da, da apur bat errazagoa delako irakurri, pixka bat hamartar antzeko zerbait baino gehiago trinkoa da, eta bitarra Ezertarako da, izan ere, gehienak gizakiak erabili. Beraz, gaur egun, zer esan nahi du horrek? Beno, ez dago baliogabea idazteko itxura on line 21 memory.c tamaina 4. Hargatik itzuli linea 21, eta hain zuzen ere, hemen idazteko baliogabea dela. Beraz Valgrind ez dago guztiz ezazu nire eskua eta esango fix zer da, baina naiz idazteko I baliogabe bat egiten ari den detektatzeko. 4 bytes dut ukitu behar ez izatea, eta, itxuraz, hori delako, adierazi du, eta horren ordez [9] [10] Gehienez egiten ari naiz edo [0] edo arteko zerbait. Valgrind, konturatzen programa bat idazten ari zaren edozein unetan erabiltzen dituen erakusleak eta memoria erabiltzen ditu, eta malloc zehatzago esanda, behin betiko luze hau abiarazi ohitura sartu baina oso erraz kopiatu eta itsatsi Valgrind komandoa ez da hor akatsak batzuk ikusteko. Eta erabatekoa izan da, eta aldi bakoitzean jarriko irteera ikusten duzu, baina ikusmen irteeraren bidez analizatu eta ikusten baduzu akatsak aipatzen edo abisu edo baliogabea edo galdu. Edozein hitz izorratu sortu soinua duzun bezala nonbait. Beraz, konturatzen zure toolkit tresna berri bat da. 

Orain Astelehena, folks sorta osoa izan genuen etorri hemen eta lotuta zerrenda nozioa. Eta zer arazo irtenbide bat bezala zerrenda lotuta sartu dugu? Bai? [Ikasleentzako erantzuna, ulertezina] Good. Arrayak ezin izan memoria gehitu. Esleitu tamaina 10 array, hori da duzun guztia lortu bada. Idazketa bezalako funtzio bat dei dezakezu hasieran bada malloc izeneko eta hori array hazten saiatu Lekurik bada amaiera aldera inork ez bestela hori erabiliz, eta dago ez bada, aski izango da aurkituko dituzu handiagoa zatia beste nonbait. Baina orduan byte horiek guztiak kopiatu berria array. Oso zuzena irtenbide bat bezala soinuak. Zergatik da hau unattractive? Esan nahi dut, funtzionatzen duen, gizakiak arazo hau konpondu. Zergatik Astelehena zerrendak lotuta ebatzi behar dugu? Bai? [Ikasleentzako erantzuna, ulertezina] denbora luzea har lezake. Izan ere, edozein unetan malloc edo idazketa edo calloc, hau da, oraindik beste bat deitzen ari zaren edozein unetan, programa, sistema eragilearen hitz egiten ari, programa motela behera joera duzu. Eta zaren loops gauza mota horiek egiten bada, benetan ari zaren gauza geldotzen behera. Ez duzu nabarituko "kaixo mundua" motako programak errazena, baina programa askoz handiagoa, sistema eragilearen eskatuz behin eta berriro memoria edo emanez behin eta berriro ez da gauza ona izan ohi da. Plus, besterik ez da intelektualki moduko denbora galtzea oso bat da. Zergatik esleitu gero eta memoria gehiago, arrisku dena kopiatzea berria array, ematen alternatiba askoz memoria esleitu benetan behar baduzu? Beraz, ez da hemen pluses eta minuses. Pluses, gaur egun dugun dinamismoa. Ez du axola non memoria zatiak dira, doakoak dira, Bakarrik ezin dut sortu ordenatzeko ogi apurrak horiek erakusleak bidez nire lotuta zerrenda osoa elkarrekin katea. Baina, gutxienez, prezioa ordaindu dut. 

Zer lotuta zerrendak lortzeko eman behar dut? Bai? [Ikasleentzako erantzuna, ulertezina] Good. Memoria gehiago behar duzu. Erakusleak horiek espazio behar dut orain, eta erraz hau super lotuta zerrenda kasuan hori bakarrik zenbaki osoko, 4 byte gordetzeko saiatzen, esaten mantendu dugu ondo, erakusle 4 byte da, beraz, gaur egun, literalki Nik bikoiztu memoria zerrenda honetan gorde behar dut. Baina, berriro ere, konstante bat da hau informatikako denerako denboran eta espazioan eta garapena, ahalegina eta beste baliabide batzuen artean. Zer da lotuta zerrenda bat erabiliz beste arazotxo bat? Bai? [Ikasleentzako erantzuna, ulertezina] Good. Ez baita erraza sartzeko. No longer ahal izango dugu leverage astea: 0 printzipio bezala zatitzeko eta konkistatzeko. Eta, zehazki, bilaketa bitarra. Dugulako, nahiz eta gizakiak gutxi gorabehera ikus daitezke, non zerrenda honen erdian da, ordenagailua bakarrik daki lotuta zerrenda hori helbidea izeneko lehen hasten da. Eta hori 0x123 edo horrelako zerbait. Eta modu bakarra programa erdiko elementu aurki daitezke zerrenda osoa da benetan bilatzeko. Eta orduan ere, literalki du zerrenda osoa bilatu behin ere erdiko elementu iristeko erakusleak jarraituz, , programa, ez daki zenbat denbora Zerrenda hau da, potentzialki, hit duzu amaiera arte, eta nola programazioaren badakizu lotuta zerrenda baten amaieran zaudela? NULL erakuslea berezi bat dago, eta, beraz, berriro ere, hitzarmen bat da. Baino gehiago erabili erakuslea honetan, ez behin betiko ez dugun nahi izan zabor balioa eta zenbait etapa off seinalatuz nonbait; eskua nahi dugu behera, NULL, beraz, Terminus dugu datu-egitura honen dakigu non eta ondorioz, beraz. 

Zer nahi badugu, hau manipulatzeko? Gehienak ikusmen hau egin dugu, eta gizakiak, baina zer txertatzeko bat egin nahi badugu? Beraz, jatorrizko zerrenda 9, 17, 20, 22, 29, 34 izan zen. Zer gertatzen da malloc espazioa, ondoren, 55, nodo nahi dugu, eta, ondoren, 55 zerrendan sartu behar bezala egin Astelehena nahi dugu? Nola egiten dugu hori? Beno, Anita izan zen, eta funtsean ibili zen zerrendan. Lehen elementu hasi zen eta, ondoren, hurrengo, hurrengoa, hurrengoa, hurrengoa, hurrengoa. Azkenik, sakatu ezkerreko guztiak behera eta konturatu oh, hau da NULL. Beraz, zer erakuslea manipulazioa egin behar dira? Pertsona amaieran izan zen, 34 zenbakia, bere ezkerreko behar planteatu 55 puntu, 55 bere ezker besoan behera seinalatuz NULL amaierako berri izan behar. Eginda. Pretty erraza 55 txertatzeko ordenatuko zerrenda. Eta nola liteke hau bilatzeko? 

Dezagun aurrera eta ireki kodea hemen adibide batzuk. Ireki dut gedit, eta utzi ireki me lehen bi fitxategiak. List1.h bat da, eta utzi gogorarazteko besterik ez zidan hau zela kode zatia nodo bat irudikatzeko erabiltzen dugun. Nodo bat bai int izeneko n eta erakuslea besterik ez duten puntu zerrendako hurrengo gauza ondoan izeneko du. Hori da gaur egun. H fitxategi batean. Zergatik? Hitzarmen hau da, eta ez dugu abantaila hartu hau kopuru handi bat geure burua, baina nork idatzi printf eta beste funtzioak munduko opari gisa eman funtzio horiek guztiak deitu stdio.h fitxategi bat idazten. Eta gero, ez da string.h, eta, ondoren, ez da map.h, eta ez da h fitxategi horien guztien ikusi duzu agian edo beste pertsonekin idatzitako indarrean dagoen bitartean erabiltzen. Normalean horien h fitxategiak typedefs bezalako gauzak bakarrik edo mota pertsonalizatuak edo konstanteak adierazpenak deklarazioak. Ez duzu jarri funtzioak 'goiburu fitxategiak inplementazio. , Sartu ordez, beren prototipoak. Partekatu nahi duzun gauza jarri duzu zer behar dute munduaren beren kodea biltzeko. Beraz, ohitura hau, gauza bera egitea erabaki dugu. Ez dago askoz list1.h baina jarri dugu zerbait interesgarriak izan daitezkeen pertsonek munduko lotutako gure zerrenda ezartzeko erabili nahi duten. Orain, list1.c, ezin izango dut gauza honetan guztian bidez joan da apur bat luzea delako, programa hau, baina dezagun exekutatu benetako azkar gonbitan. Let Zerrenda1 konpilatu me, utzi ondoren, exekutatu me Zerrenda1, eta zer ikusiko duzu simulatutako simple programa txiki bat dugu hemen hori gehitu eta me kendu zenbakiak zerrenda bat egin ahal izateko. Beraz, aurrera eta 3 idatzi menu aukera 3. Zenbakia txertatu nahi dut - egin dezagun lehen zenbakia, hain zuzen, 9, eta orain dut kontatu zerrenda da gaur egun 9. Dezagun aurrera eta beste egin txertatzeko, beraz, menu aukera 3 hit dut. Zein zenbaki sartu nahi dut? 17. Sartu. Eta beste bat gehiago egin dut. 22 zenbakia sartu me. Beraz, zerrenda lotuta diapositiba inprimaki dugun une bat izan duela hasieratik dugu. Nola txertatzeko hau benetan gertatzen ari da? Izan ere, 22 da zerrendaren amaieran. Istorioa Beraz, esan etapa astelehena eta recapped oraintxe kodea behar benetan gertatzen ari dena. Ikus dezagun begirada bat. Demagun behera joan me fitxategi honetan. Gloss dugu funtzio batzuk, baina jaisten dugu, esan, txertatze-funtzioa. 

Dezagun nola joan lotuta zerrenda hori nodo berri bat sartu dugu ikus-en. Non izendatu zerrendan? Beno, utzi mugitu modu guztiak goialdean, eta konturatu nire lotuta zerrenda hori, funtsean, hasiera batean NULL erakuslea bakar bat izendatu. Beraz, aldagai global bat naiz Hemen, eta, oro har, Predicada dugu aurka egiten du zure kodea delako little messy bat mantentzeko, alferrak, normalean sort da, baina ez da alferrak eta ez da okerra eta ez da txarra zure programa bizitzan helburu bakarra lotutako zerrenda bat simulatu nahi izanez gero. Zein da, zehatz-mehatz zer egiten ari gara. Beraz, baino deklaratzeko nagusia eta, ondoren, funtzio guztietan pasatzen programa hau idatzi dugu, konturatzen gara ordez oh, dezagun egin da global Programa honen helburua osoa da bat eta bakarra lotuta zerrenda erakusteko delako. Beraz, ongi sentitzen. Hona hemen nire prototipoak, eta ez dugu horien guztien bidez, baina delete funtzio bat, aurkituko funtzio bat, txertatze-funtzio bat, eta traverse funtzio bat idatzi nuen. Baina dezagun atzera jo txertatze-funtzioa ikusi eta nola funtzionatzen du hemen. Txertatu on line da, hemen goaz. Txertatu. Beraz, ez du argumenturik hartzen ari gara, eskatu delako erabiltzaileen kopurua sartu nahi duten funtzio honen barruan. Baina, lehenik eta behin, emateko lekua prestatu dugu. Kopia eta itsatsi beste adibide moduko bat da. Kasu horretan, int bat ginen esleitzean; Une honetan nodo bat ari gara esleitzean. Ez dut gogoratzen zenbat byte nodo bat da, baina hori da isuna. Sizeof hori irudikatu ahal izango niretzat. Eta zergatik am egiaztapena line 120 NULL dut? Zer line 119 oker joan liteke? Bai? [Ikasleentzako erantzuna, ulertezina] Good. Badaezpada dudan memoria gehiegi eskatu izan liteke edo zerbait oker eta sistema eragilea ez da nahikoa bytes niri emateko, beraz, askoz ere seinaleak NULL itzuli, eta ez bada ez dut hori egiaztatzeko eta jarraitu besterik ez blindly helbidea itzuli erabili, NULL da. Balio ezezagun batzuk izan daiteke, ez da gauza ona dut ezean - Egia esan, ez du balio ezezagun bat izango da. Izan NULL izan daiteke, beraz, ez dut nahi gehiegi eta arriskua da dereferencing. Horrela gertatzen bada, itzuli besterik ez dut, eta ez nuen bezala itzuli memoria edozein asmoa dugu. 

Bestela, erabiltzaileari eman dit zenbaki bat sartu esango dut, gure lagun zaharra GetInt deitzen diot nik, eta, ondoren, astelehena, sintaxia sartu dugu. 'Newptr-> n' esan nahi du, helbidea zirela malloc emandako lehen nodo berria objektu byte adierazten du. eta, ondoren, n izeneko eremuan. Un poco de bitxikeriak galdera: zer gehiago críptica kodea line baliokidea da? Nola bestela ezin idatzi dut hau? Stab bat hartu nahi duzu? [Ikasleentzako erantzuna, ulertezina] Good. N bidez, baina ez da nahiko bezain erraza. Zer egin behar dut, lehen ez? [Ikasleentzako erantzuna, ulertezina] Good. * Newptr.n egin behar dut. Beraz, hau da erakuslea da, jakina, helbide bat esanez. Zergatik? Izan da malloc itzuli delako. * Newptr esaten "Hara joan," eta, ondoren, bertan behin eta, ondoren, gehiago ezagutzen. n erabili ahal izango duzu, baina hori itxura pixka bat itsusi, batez ere badugu gizakiak dira joan marraztu duten erakusleak geziak denbora guztian; munduko normalizatua gezi-izendapen hori, zehazki gauza bera egiten du. Beraz, soilik erabili -> notazioa ezker gauza erakuslea da. Bestela, uneko eta egitura bat izanez gero, erabili. N. Eta gero hau: Zergatik newptr-> hurrengo hasieratu I NULL? Ez dugu nahi zintzilik ezkerreko off etapa amaieran. Seinalatuz zuzen behera nahi dugu, eta horrek esan nahi du zerrenda honen amaieran potentzialki nodo honetan izango da, beraz, hobe dugu ziurtatu NULL da. Eta, oro har, zure aldagai edo zure datuak kide eta structs hasieratzean zerbait, praktika onak besterik ez da. Just zabor existitzen eta, oro har, existitzen jarraitzen uztea lortzen Arazoak ahaztu zerbait egin ondoren. 

Hona hemen batzuk kasu. Honek, berriro ere, txertatze-funtzioa da, eta egiaztatu nuen lehenengo gauza da, aldagai izeneko lehen bada, global aldagaia NULL da, horrek esan nahi du dago lotuta zerrenda ez da. Ez sartu ditugu zenbakiak, eta, beraz, hutsala da uneko zenbaki hau sartu zerrendan sartu, besterik ez delako zerrendaren hasiera dagokio. Honetan, beraz, noiz Anita besterik ez zuten zutik hemen bakarrik, itxurak inork ez bestela zen hemen etapa nodo bat esleitu arte, ondoren, bere eskua altxatzeko izan zuen lehen aldiz, Besteek iritsia zen agertokian bere ondoren astelehena. Orain hemen, non esan behar dut pixka bat check berria nodo n balioa n balioa lehen uneko nodoaren <, horrek esan nahi du ez da estekatutako zerrenda hasi da. Gutxienez zerrendan nodo, baina lasaia hau berria dagokio, beraz, aurretik gauzak lekuz aldatzeko behar dugu. Beste era batera esanda, zerrenda hasi besterik ez bada, demagun, kopurua 17, benetan, hau egin ahal izango dugu, argi eta garbi. Hasten bada, gure istorioa erakuslea hemen izeneko lehen, eta hasiera batean NULL da, eta 9 zenbakia sartu dugu, kopurua 9 argi eta garbi zerrendaren hasiera dagokio. Hargatik asmoa malloced besterik ez dugu helbidea edo telefono zenbaki 9 eta jarri hemen. Lehenengoa da lehenetsi 9 bada, lehenengo eszenatokia dugu eztabaidatu let guy hau esan nahi du hemen, utzi hau NULL; kopurua 9 ditugu. Sartu nahi dugu hurrengo zenbakia 17 da. 17 pertenece baino gehiago hemen, beraz, hurrats batzuk logikoa honen bidez egin nahi izan dugu. Hargatik ordez, egiten dugu, dezagun asmoa kopurua 8 txertatu nahi dugun aurretik. 

Beraz, besterik gabe, erosotasuna-en mesedetan, hemen marraztu dut. Baina gogoan, malloc jarri gehien edozein lekutan. Baina marrazki-en mesedetan jarri dut hemen. Beraz, asmoa besterik ez dut esleitutako kopurua 8 nodo bat; hau da lehenespenez NULL. Orain zer gertatuko? Gauza pare bat. Akatsa egin dugu etapa on Astelehena non erakuslea hau atsegin eguneratu dugu, ondoren egin hau, eta, ondoren, erreklamatutako - Besteek eszenatokian umezurtz dugu. Can't duzulako - eragiketa hemen ordena garrantzitsua da, Orain delako galdu dugu hau nodo 9 espazioan flotatzen sort besterik ez dela. Beraz, hori ez zen Astelehena ikuspegi eskubidea. Lehen beste zerbait egin behar dugu. Munduko egoera honen itxura. Hasieran, 8 izan dira. Zer da 8 txertatu modu hobea izango litzateke? Horren ordez erakuslea hau eguneratzen lehen, hau hemen eguneratu ordez. Beraz, kode lerro bat den NULL karaktere hau aktiba behar dugu erakusle bat benetako nodo 9 seinalatuz, eta, ondoren, segurtasunez aldatzeko lehen guy honetan seinalatu hemen. Orain zerrenda bat, zerrenda bat lotuta, bi elementu ditugu. Eta zer esan nahi du honek benetan hemen itxura? Kodea begiratuz gero, konturatu egin ditudan zehazki hori. Esan dut newptr, eta istorio hau, newptr guy hau seinalatuz. 

Hargatik marraztu me gauza bat gehiago, eta gela hau apur bat gehiago utzi behar dut. Beraz barkatzen minuskula txikia marrazkia. Guy newptr deritzo. Aldagai lerro gutxitan lehenago deklaratu dugu, line - 25 gainetik. Eta 8 seinalatuz. Beraz newptr-> hurrengo diot, eta horrek esan nahi du egitura joan ari diren adierazi at newptr, eta, beraz, hemen gaude, Hara joan. Orduan gezi hurrengo eremuan, eta, ondoren, = jartzen da zein balio han esaten? Balioa lehen zen; zer balioa lehen zen? Lehenengoa zen nodo honetan, seinalatuz beraz, horrek esan nahi du nodo honetan seinalatu behar. Beste era batera esanda, nire idazkera barregarria nahastea, nahiz eta itxura, geziak horiek mugitzen inguruko ideia sinple bat kodea itzuli with bakarrarekin forrua honetan. Biltegiratu lehen hurrengo eremuan, eta, ondoren, eguneratu zer lehen benetan. Dezagun aurrera eta Aurreratu honen bidez, eta begiratu bakarrik buztana txertatzeko honetan oraingoz. Demagun iritsi, non nodo batzuen eremuan hurrengo NULL dela iruditzen zait puntu dut. Eta istorioa, xehetasun puntu honetan naiz duten I glossing erakuslea beste sartu dudan hemen, aurrekoak erakuslea line 142. Funtsean, istorioa Puntu honetan, behin zerrendan lortzen luze, Behar mota bi behatzak oinez joaten naiz urrunegi delako, bakar-zerrenda luze bat gogoratu, ezin duzu atzeraka joatea. Beraz, predptr ideia hau nire ezkerreko hatz da, eta newptr - ez newptr. Erakuslea beste hemen nire beste hatz da,, eta zerrenda oinez mota naiz. Horregatik existitzen dela. Baina bakarra kontuan hartu kasu errazagoa hemen bat. Erakuslea eremu hori hurrengo NULL bada, logikoa inplikazioa? Zerrenda honetan bada traversing eta NULL erakuslea bat hit duzu? Oraindik zerrendaren amaieran, eta, beraz, kodea, ondoren, osagarriak elementu bat eransteko intuitiboa, sort honen hurrengo erakuslea da NULL nodo hori hartuko du, beraz, hau da gaur egun NULL, eta aldatu, nahiz eta, nodoaren berri helbidea izan. Beraz, ari gara kodea gezi marraztean etapa marraztu dugun norbaiten ezkerreko handituz. 

Eta kasu eskuak I olatuen egingo oraingoz at, besterik ez delako erraza da galdu egiten dugu, ingurumena moduko honetan uste dut, zerrenda erdian txertatzeko egiaztapena da. Baina senez, zer gertatu behar da nahi duzun irudikatu nahi izanez gero non zenbaki batzuk erdian pertenece daukazu oinez hatz bat baino gehiago, bat baino gehiago erakuslea, irudikatu non pertenece egiaztapena elementu <unekoa, > Unekoa, eta behin leku horretan aurkituko dituzu, ondoren, non erakusleak kontu handiz mugitu inguruan shell joko moduko Horretarako behar duzu. Eta erantzuna, dituzu, arrazoi nahi izanez gero, honen bidez, zeure etxean, irakin, besterik gabe, bi kode lerro horiek behera, baina lerro horien ordena da super garrantzitsua da. Jaregitean norbaiten eskua bada, eta goratzeko beste norbaitek ordena okerra delako, berriro hasi behar duzu. izan zerrendan orphaning. Kontzeptualki laburbiltzea, buztana txertatzeko nahiko erraza da. Burua txertatzeko ere nahiko erraza da, baina erakusle bat gehiago une honetan eguneratu behar duzu multzoko 5 ederki zerrendan Hemen eta, ondoren, erdian txertatzeko are gehiago ahalegina eskatzen du, kontu handiz sartu 20 zenbakia bere kokapena zuzena, 17 eta 22 artekoa da. Beraz, behar duzun zerbait egin berri dute nodo 20 puntu eta 22 bezala, eta, ondoren, zein nodo en erakuslea eguneratu egin behar da azken? 17 da, benetan sartu da. Beraz, berriro ere, jakin ezartzeko benetako kodea atzeratu dut. 

Lehen begiratuan, pixka bat jasanezinak da, baina benetan begizta infinitu bat besterik ez da den, begizta begizta batean, begizta batean, begizta batean, eta ahalik eta azkarren hausteko hit NULL erakuslea gisa, eta amaitzen da baldintza txertatzeko egin dezakezu. Honek, beraz, ordezkaritza lotuta zerrenda txertatzeko kodea da. Mota asko izan zen, eta konpondu atsegin dugu arazo bat sentitzen da, baina oso bat sartu dugu beste bat. Egia, gastatu dugu denbora hori guztia big O eta Ω eta iraupena, arazoak konpontzeko azkarrago nahian, eta hemen beste urrats bat handira atzeraka ari garela, sentitzen. Eta, hala ere, lortu nahi da, datuak gorde nahi izanez gero, Holy Grail bezala sentitzen da, astelehena, esan bezala, benetan gauzak gordetzeko berehala. 

Izan ere, demagun ez dugu une batez alde batera utzita lotuta jarri zerrenda eta ordez sartu dugu mahai baten ideia. Eta dezagun taula bat besterik ez dela uste array gisa une bat. Array hau eta kasu honetan hemen 26 elementuak, 0 25 bidez, eta demagun behar duzun zatia biltegiratze batzuen izenak: Alice eta Bob eta Charlie eta antzekoak. Eta datu-egitura bat behar duzu, izen horiek gordetzeko. Beno, lotuta zerrenda antzeko zerbait erabili ahal izango duzu eta Alice txertatu zerrenda oinez Bob eta Charlie Bob ondoren aurretik, eta abar. Eta, hain zuzen ere, horrelako bat alde batera utzita kodea ikusteko nahi duzun bada, jakin list2.h, zehatz-mehatz egiten dugu. Kode honen bidez ez dugu, baina hau lehen adibide aldaera bat da struct beste bat ikasleak izenekoa aurretik ikusi dugu sartzen, eta orduan zer lotutako zerrenda gordetzen da benetan, ikaslea egitura baten erakuslea da sinple bat baino apur osokoa, n. Beraz, konturatzen kodea ez da bertan lan egiten duten benetako kateak, baina esku helburua benetan bada eraginkortasun arazoari aurre egiteko, ez litzateke polita izango da gaude Alice izeneko objektu bat ematen bazaio, bere datuak egitura batean eskuineko kokapena jarri nahi dugu, benetan polita da gustatuko litzaidake jarri Alice sentitzen da, cuyo nombre A batekin hasten da, lehen kokalekua. Eta Bob, bere izena B batekin hasten da, bigarren kokapena. Array bat, edo dezagun hasteko deituz mahai bat, hartan hash taula bat, zehazki hori egin ahal izango dugu. Gaude Alice bezalako izen bat ematen bazaio, Alice bezalako kate bat, non A-l-i-c-e jarri al duzu? Hueristic bat behar dugu. Alice bezala sarrera batzuk hartzeko funtzio bat behar dugu eta erantzun bat itzultzeko, "Jarri Alice kokaleku horretan." Eta, kutxa beltza, funtzio hau deitu behar hash funtzio bat. 

Zerbait sarrera bat hartzen duen bezala, "Alice" hash funtzio bat da, duzu, normalean, kokapena zenbakizko datuak egitura batzuetan non Alice dagokio. Kasu honetan, gure hash funtzioa nahiko erraza izan beharko luke. Gure hash funtzioa, esan behar baduzu, emandako "Alice", zein karaktere izan behar dut arduratu dira? Lehena. Beraz, itxura [0], eta, ondoren, [0] pertsonaia da A bada, itzultzeko kopurua 0 diot. Da B bada, itzuli 1. Da C bada, itzultzeko 2, eta abar. Guztiak 0 indizea, eta Alice eta, ondoren, Bob eta, ondoren, Charlie sartu me ahalbidetuko luke, eta abar datu egitura honetan sartu. Baina arazo bat da. Zer dator Anita batera berriro? Nora egin Anita jarri dugu? Bere izena, ere bai, gutun-A batekin hasten da, dugu arazo hau nahastea, are handiagoa egin bezala sentitzen da. Dugu berehalako txertatzeko, etengabeko denbora txertatzeko, datu egitura bat baizik eta okerrago-kasu baino lineal, baina, zer egin dezaket Anita dugu kasu honetan? Zer dira bi aukerak, benetan? Bai? [Ikasleentzako erantzuna, ulertezina] Ongi da, eta, beraz, beste dimentsio bat izan dugu. Hori ona da. Beraz, gauzak eraiki ahal izango dugu hitz egin bezala 3D dugu hitzez Astelehena. Sarbide bat gehitu izan dugu hemen, baina demagun ez dela, hau simple mantentzeko saiatzen ari naiz. Osoa helburua hemen da etengabe-time berehalako sarbidea dute, beraz, gehiegi konplexutasuna gehituz. Zer dira beste aukerak Anita txertatzeko datu egitura honetan sartu nahian? Bai? [Ikasleentzako erantzuna, ulertezina] Good. Beraz, gainontzeko behera mugitu ahal izan genuen, Charlie behera nudges Bob eta Alice, eta, ondoren, atsegin Anita jarri dugu non nahi benetan zuen. 

Noski, gaur egun, ez dago albo efektu bat da. Datu-egitura hau da, ziur aski erabilgarria ez delako behin pertsona sartu nahi dugu baina nahi dugu Oraindik ere, badago geroago ikusteko duelako datu-egitura izen guztiak inprimatu nahi badugu. Datu honekin zerbait egin behar azkenean goaz. Beraz, gaur egun mota Alice, jada ez zuen behar baino gehiago izorratu dugu. Nor da Bob, ez da Charlie. Beraz, agian, ez da ideia ona, hala nola. Baina, hain zuzen ere, aukera bat da. Denek filmea izan dugu behera, edo heck, Anita berandu iritsi zen joko, zergatik ez jarri besterik ez dugu Anita hemen ez, hemen ez, hemen ez, dezagun jarri bere zerrendan pixka bat txikiagoa. Baina gero, arazo hau berriro devolve hasten. Alice aurkitu ahal izango duzu agian, berehala, bere lehen izen oinarritzen da. Eta Bob berehala, eta Charlie. Baina orduan begiratzen Anita, , eta ikusiko duzu, hmm, Alice bidea da. Beno, utzi egiaztatu Alice azpian me. Bob ez da Anita. Charlie ez da Anita. Oh, ez dago Anita. Eta logika jarraitzen duzu tren hori bada, modu guztiak, kasurik txarrenaren exekutatzen edo aurkitzeko Anita txertatu datu berriak egitura zer da? O (n) da, ezta? Kasu txarrena dela eta, ez da Alice, Bob, Charlie. . . utzi behera norbait izeneko "Y", guztiak, beraz, ez dago Leku bakarra da. Zorionez, "Z" izeneko bat ez dugu, beraz, Anita oso behean jarri genituen. 

Ez dugu benetan konpondu arazo hori. Beraz, agian, hirugarren dimentsio hori aurkeztu beharko dugu ez. Eta bihurtzen da, hirugarren dimentsio hori aurkeztu ezean, ezin dugu primeran, baina Holy Grail da lortzean joan konstante-time-munduratze eta, beraz, dinamikoa insertions ez dugu hard-tamaina 26 kodea array bat. Dezakegu izen asko gisa sartu nahi dugu, baina dezagun gure 5 minutuko break hartzeko hemen eta, ondoren, behar bezala dela. Guztiak eskubidea. Istorioa dut nahiko artifizialki dago Alice eta gero, Bob eta, ondoren, Charlie eta, ondoren, Anita aukeratzerakoan, dauka, eta izen zen, jakina, Alice talka. Baina galdera da, astelehena, amaitu dugu nola litekeena da mota horiek talka duzula? Beste era batera esanda, hasten gara tabularrean egitura hau erabili nahi izanez gero, hau da, benetan array bat besterik ez da, 26 kokalekuen kasu honetan, gure input badira ordez uniformeki banatzen? Ez da artifizialki Alice eta Bob eta Charlie eta David eta abarren arabera alfabetikoki Z. bidez du uniformeki A banatuta 

Agian besterik ez dugu lortu zortea eta ez ari gara bi bat edo bi B dute probabilitatea oso altua, baina norbait duenez, dugu orokortu eta arazo hau ez bada egin 0 eta 25 baina, adibidez, 0 bidez 364 edo 65, askotan ohiko urtean, egun kopurua eta galdera, "Zer da gurekin bi gela honetan bera duten urtebetetzea probabilitatea?" Jarri beste modu bat, zer probabilitate gurekin bi izen bat dute A-rekin hasten da? Galdera-sort berbera da, baina helbide-espazio hau, bilaketa-espazioa hau, urtebetetzeak kasuan handiagoa da, dugulako hainbeste urtean egun alfabetoaren letra baino. Zer da talka baten probabilitatea? Beno, hau ezin dugu uste kalkulatzen math kontrako bidea. Zer da talkak ez probabilitatea? Beno, adierazpen hau hemen dio zer probabilitatea gela honetan pertsona bakar bat, berezia urtebetetzea dutela bada? % 100 da. Gela pertsona bakarra delako, bere urtebetetzea 365 egun edozein izan daiteke urteko daudelarik. Beraz, 365/365 aukera ematen dit balio bat 1. Beraz, une honetan galdera probabilitatea 1 da. Baina gela bigarren pertsona bat izanez gero, zer probabilitate bere urtebetetzea desberdina da? Ez bakarrik ahalik eta 364 egun, ez ikusi egingo zaio, bisurteetan, bere urtebetetzea ez beste pertsona batekin talka. Beraz, 364/365. Hirugarren pertsona bat badator, 363/365, eta abar. Beraz, elkarrekin biderkatuz frakzio horiek mantendu dira, txikiagoak eta txikiagoa lortzean, out irudikatu zer guztiok berezia urtebetetzeak probabilitatea? Baina orduan, ezin dugu, jakina, besterik gabe, erantzuna hartu eta irauli inguruan eta zer 1 ken guztiak, adierazpen bat azkenean dugu gogoratzen duzu zure math liburuak itzuli bada, honen antzeko zerbait pixka bat ikusten da, askoz ere erraz interpretatu grafikoki. Eta grafiko hau hemen x ardatza urtebetetzeak kopurua, edo urtebetetzeak duten pertsonak, eta y ardatzean kopurua partida probabilitatea da. Eta zer da hori esaten baldin baduzu, demagun, nahiz eta, aukeratu dezagun 22, 23 antzeko zerbait. Ez da 22 edo 23 pertsona gelan bada, probabilitatea, bi horiek oso jende gutxik urtebetetzea izan bera super altua da, benetan, combinatorially. % 50 odds 22 pertsona, mintegi bat, ia-ia klase batean, Pertsonen 2 urtebetetzea izan bera. Ez delako hainbeste modu berean urtebetetzea izan dezakezu. Nahiz eta okerragoa, diagramaren eskuinaldean begiratzen baduzu, denbora klase bat duzula, 58 ikasle, 2 pertsonek urtebetetzea bat izateko probabilitatea super, super altua da, ia% 100. Orain, bizitza errealean buruzko fun Izan ere, sort. 

Baina inplikazio, gaur egun, datuen egitura eta gordetzeko informazioa esan nahi du, besterik gabe, polit bat, garbi, datu-banaketa uniformea ​​suposatuz eta gauza mordo bat egokitzeko array handi bat nahikoa duzu ez du esan nahi pertsona kokapenak berezia lortzeko ari zaren. Talkak ari zara. Egiaztapena nozioa honetan, beraz, deitzen, bezalako "Alice" sarrera bat hartu eta nolabait massaging eta, ondoren, 0 edo 1 edo 2 bezala erantzun bat. Atzera eskuratzen funtzio hori irteera batzuk talka probabilitatea hau beteta. Beraz, nola egin dezaket talkak horiek kudeatzeko dugu? Beno, kasu batean, ideia izan zen iradoki hartu ahal izango dugu. Besterik dugu guztiontzat, mugitu behera, edo agian, apur bat gehiago, besterik gabe, mugimendua Besteek ordez, utzi besterik ez mugitu Anita eskuragarri Leku beheko aldean. Beraz, bada Alice 0 da, Bob 1 da, Charlie 2 da, besterik ez dugu jarri Anita kokapena 3. Eta hori izeneko datu egitura lineal artesiak teknika bat da. Lineala delako ari zaren lerro hau oinez, eta artesiak moduko Oraindik duzu datu egitura lekuak eskuragarri. Jakina, O (n) sartu devolves. Datu-egitura oso beteta badago, ez da 25 pertsona dagoeneko eta, ondoren, Anita batera dator, eta ondorioz bere kokapena Z izango litzateke, eta hori da isuna. Egokitzen jarraitzen zuen, eta geroago bere aurki ditzakegu. 

Baina gauzak bizkortzeko sortu helburua aurkakoa izan zen. Beraz, zer bada ordez sartu dugu hirugarren dimentsio hori? Teknika da, oro har, aparteko kateatzea deitzen zaio, edo kateak izatea. Eta zer hash taula bat da, egitura hau tabularrean zure taula erakusleak array bat besterik ez da. Baina zer gertatzen da erakusle ere seinalatu asmatzeko zer da? Lotuta zerrenda. Beraz, zer bi munduen onena hartuko dugu? Array erabiltzen dugu hasierako indizeak datuak egitura sartu berehala [0] [1], [30] edo abarren joan ahal izango dugu, baina dugun malgutasun batzuk eta Anita eta Alice eta Adam doi dezakegu eta beste edozein izen bat, utzi ordez, beste ardatza hazten arbitrarioki. Eta, azkenik, astelehenetik, zerrenda lotutako gaitasun espresibo hori. Arbitrarioki, datu-egitura bat hazten dugu. Bestela, 2 dimentsioko array handi bat egin izan dugu, dimentsioko array bat 2-ilara bat baina hori awful egoera bat izan nahi izanez gero ez da nahikoa pertsona osagarriak bere izen gertatzen A. batekin hasten Jainkoa forbid 2 dimentsioko egitura handi bat reallocate behar dugu besterik ez dagoelako hainbeste izeneko A batez ere, ez da hain gutxi Z zerbait izeneko pertsona. Besterik ez da, datuak oso sakabanatuak egitura izango. Beraz, ez da edozein bitarteko ezin hobea da, baina orain, gutxienez gaitasuna berehala aurkituko non Alice edo Anita da, gutxienez ardatz bertikala dagokionez, eta, ondoren, besterik ez dugu non Anita edo Alice jarri lotuta zerrenda hori erabakitzeko. Gauzak ordenatzeko buruzko zaintzeko ez badugu, nola azkar izan Alice sartu dugu hau atsegin egitura batean? Etengabeko denbora da. Indizea [0] ditugu, eta inork ez badago, Alice lotzen zerrenda Irteeran doa. Baina hori ez da aurre erraldoia. Zeren Anita ondoren dator zehar urrats batzuk beranduago, non ez Anita sartzen zara? Beno, [0]. Objektuei Begirako Programazio. Alice da dagoeneko lotzen zerrendan. 

Baina ez badugu izen horiek ordenatzeko buruzko zaintzeko, Alice baino gehiago, Anita txertatzea besterik ez mugitu ahal izango dugu, baina nahiz eta denbora konstante da. Nahiz eta Alice eta Adam eta beste izen horiek guztiak A, ez da benetan aldatzearen fisikoki. Zergatik? Besterik ez dugu egin delako hemen zerrenda lotuta, nork daki ziren nodo horiek dira, hala ere? Guztiak egin behar duzun da mugitu ogi apurrak. Mugitu geziak inguruan, ez duzu edozein datu fisikoki mugitu inguruan. Beraz, Anita sartu ahal izango dugu, kasu horretan, berehala. Constant denbora. Beraz, konstante-time lookup, eta etengabe-time Anita bezalako norbait txertatzeko dugu. Baina mota munduko oversimplifying. Zer geroago Alice aurkitu nahi badugu? Zer geroago Alice aurkitu nahi badugu? Zenbat urrats hori hartu? [Ikasleentzako erantzuna, ulertezina] Hain zuzen ere. Alice aurretik lotuta zerrendan pertsona kopurua. Beraz, ez da nahiko perfektua, gure datu-egitura, berriz, delako, bertikala sarbidea du eta, ondoren, zintzilik lotutako zerrendak hauek ditu: - benetan, ez marraztu da array bat utzi. Lotuta, zerrenda horiek off zintzilik honen antzeko zerbait apur bat itxura. Baina arazoa da, Alice eta Adam eta beste izen horiek guztiak A azkenean, gero eta gehiago, han, norbait amaitzeko urratsen sorta bat hartu izan aurkitzeko, bcause lotutako zerrenda zeharkatzeko behar duzu, eragiketa bat lineala da. Beraz, benetan, eta gero, txertatzeko denbora, azken finean, O (n), non n zerrendako elementu kopurua da. Sailkatuak, dezagun arbitrarioki deitu m, non m zerrendak lotutako kopurua da ardatz bertikala honetan dugun. Beste era batera esanda, benetan bere gain hartzen dugu izenak banaketa uniformea ​​bada, erabat unrealistic. Ez da, jakina, letra batzuk besteak baino gehiago. 

Baina une uniformea ​​banaketa bere gain hartzen bada, eta pertsona guztira, eta guztira m kateak dugu n aukera ematen digu, eta gero kateak horietako bakoitzaren iraupena nahiko besterik ez da, guztira, n kateak kopuruaren arabera banatzen da izango. N / m Beraz. Baina hemen non matematikoki clever ahal izango dugu. m konstante bat da, ez dago horien kopuru finko bat delako. Array deklaratzen ari zara hasieran, Oraindik ez dugu tamainaz aldatu ardatz bertikala. Definizioz, egonaldi konpondu. Bakarrik da ardatz horizontala, eta, beraz, hitz hori aldatzen. Beraz, teknikoki, konstante bat da. Beraz, gaur egun, txertatzeko denbora pretty askoz O (n) da. Beraz, ez da askoz hobeto sentitzen. Baina egia da hemen? Beno, denbora honetan guztian, asteak, dira esaten dugu O (n ²). O (n), 2 x n ², - n, 2 arabera banatzen da. . . ech. N ² besterik ez da. Baina orain, seihilekoan zati honetan, mundu errealean buruz berriro hitz egiten hasi ahal izango dugu. Eta n / m da erabat, besterik ez bakarrik n baino azkarrago. Mila izen bat bada, eta horiek apurtu kuboak hainbat beraz, bakarrik hamar kateak horietako bakoitzak izen duzu, hamar gauzak erabat bilatzen mila gauza bat baino azkarrago izango da. Eta, beraz, arazo datozen multzo bat da erronka zehazki dela pentsatu arren, bai, asymptotically eta matematikoki, hau da, oraindik ere, lineala, eta, oro har, sucks gauzak aurkitu nahian. Egia esan, hori baino azkarragoa izan da delako zatitzaile hau. Eta beraz, ez da berriro merkataritza-off honetan izango da eta teoria eta errealitatearen arteko gatazka honetan, eta gasaren puntu honetan seihilekoan inflexio hasiko da errealitate bat baino gehiago sort semster amaitu bezala prestatzeko, aurkezten dugun web programazioaren munduan, non benetan, errendimendua zenbatu zure erabiltzaile delako hasi eta sentitzen eskertzen pobrea diseinua erabakiak. 

Beraz, nola joaten lotutako ezartzeko - 31 elementu hash taula bat? Eta aurreko adibidea arbitrarioki urtebetetzeak buruz. Norbaitek urtarrilaren 1a edo February 1 urtebetetzea badu, jarri dugu ontzi hau. Da urtarrilaren 2, otsailak 2, March 2 izanez gero, jarri dugu ontzi hau. Hori dela eta, 31 izan zen. Nola hash taula bat aldarrikatu duzu? Pretty simple daiteke, nodoak * taula nire izena, arbitrarioak [31]. Honek ematen dit, 31 erakusle, nodo eta aukera ematen duen 31 lotuta zerrendak erakusle izan me nahiz eta kateak dira hasiera batean NULL. Zer jarri nahi dut nahi dut gorde nahi izanez gero "Alice", "Bob", "Charlie"? Beno, gauza horiek biltzeko egitura bat behar dugu. behar ditugu, Alice eta Bob seinalatu, Charlie seinalatu, eta abar. Ezin dugu besterik ez izenak bakarrik, eta, beraz, deitzen nodo, hemen egitura berri bat sortu izan dut. 

Zer da benetako nodo bat da? Zer da hau loturiko zerrenda berri nodo bat da? Lehenik eta behin, deitu hitza, pertsona izena da. LENGTH, ustez, giza izena gehienezko luzera, edozein dela ere, 20, 30, 40 izkinan crazy kasu pertsonaiak, eta +1 zer da? Besterik ez da aparteko NULL karaktere, \ 0. Beraz, nodo honen barruan bere burua "zerbait" itzulbiratzeko, baina adierazten ere izeneko hurrengo erakuslea beraz, kate Alice Bob Charlie ahal izango dugu, eta abar. NULL izan daiteke, baina ez du zertan izan. Hash taulak horiek edozein galdera? Bai? [Student galdera galdetzen, ulertezina] array bat - galdera ona. Zergatik hitz array bat baino besterik ez char * karaktere hau da? Hau zertxobait arbitrarioa Adibidez, ez dut jo nahi izan jatorrizko izenak bakoitzean malloc. Katea memoria gehienezko zenbatekoa bat aldarrikatu nahi dut beraz, egitura izan dut kopiatu Alice \ 0 eta ez malloc eta doakoa da eta bezala aurre egiteko. Baina hori egin izan dut nahi nuen espazioaren erabilera kontziente izan nahi izanez gero. Ona galdera. Beraz, utzi kanpoan orokortu hau saiatu bere eta fokua datuen egitura, oro har, gaur egungo gainerako eta oinarriak berdinak erabiltzen duten beste arazo batzuk konpondu ahal izango dugu. nahiz eta datu-egitura nahiz eta bere berezitasunak ezberdindu dezake bere burua. 

Beraz, izarrekin bihurtzen da ordenagailua zientzia, zuhaitzak oso arruntak dira. Eta zuhaitz sort dezakezu uste familia zuhaitz bat bezala, han sustraiak, matriarch batzuk edo patriarka, amona edo aitona edo lehenago itzuli horien azpian daude, ama eta aita edo hainbat anai-arrebak, edo antzekoak. Beraz, zuhaitz egitura du nodo eta seme-alaba ditu, normalean 0 nodo bakoitzeko seme-alaba edo gehiago. Eta jargon, batzuk hemen Argazki hau ikusten duzun ertzak kids gutxi edo grandkids edozein duten geziak ez da irteten, duten deiturikoak hostoak, eta barrutik edonork barne-nodo bat da; ezer lerro horiek batera deitu dezakezu. Baina egitura hori nahiko ohikoa da. Hau da, apur bat arbitrarioa. Seme-alabaren bat behar dugu ezkerretara, hiru seme-alabak eskubidea dugu, behean bi seme-alabak utzi. Beraz, tamaina ezberdineko zuhaitzak izan dezakegu, baina gauzak normalizatzeko hasten badugu, eta hau gogoratzen dezakezu Patrick en bideo labur bat aurreko bilaketa bitarra online, bilaketa bitarra ez da array bat abian edo paper-pieza arbel bat. Demagun nahi duzun zure zenbakiak gordetzeko datu-egitura sofistikatuagoa. Hau atsegin zuhaitz bat sor dezakezu. C deklaratu nodo bat izan duzu, eta nodo horren barruan, gutxienez bi elementu izan ditzake. Gorde nahi duzun zenbaki bat da, eta bestea ondo, beste bat gehiago behar dugu. Bestea, bere seme-alaba da. Hortaz, hona hemen datu-egitura bat da. Oraingo honetan, nodo bat bezala definitzen da zenbaki bat gordetzeko n eta, ondoren, bi erakusleak; ezker seme-alaba eta seme-alabak eskubidea. Eta ez dira arbitrarioak. Zer da Zuhaitz honi buruz interesgarria? 

Zer nola ezarritako dugu hau edo nola Patrick ezarri du bere bideo eredua? Mota da bistako Ordenatzeko batzuk hemen, baina zer simple araua? Bai? [Ikasleentzako erantzuna, ulertezina] Perfect. Honetan, labur-labur bada, ezkerreko zenbakiak txiki ikusten duzu, big ezkerreko zenbakiak, baina hori egia nodo bakoitzeko. Nodo bakoitzean, haren ezkerreko seme baino gutxiago, eta bere eskubidea seme-alaba baino handiagoa. Zer da hau esan nahi du, gaur egun, datu-egitura hau bilatu nahi dut, adibidez, 44 zenbakia, Erro hasi behar dut, baita horiek datuak egitura konplexuagoa guztiak erakuslea besterik ez dugu gauza bat, hasiera-hasieratik. Eta, kasu honetan, hasiera-hasieratik root da. Ez da ezker amaieran, Egitura hau root da. Beraz, ikusten dut hemen 55 eta 44 bila nabil. Zein norabidean joan nahi dut? Beno, ezkerrera joan nahi dut, jakina, eskubidea delako handiegia izango. Beraz nabarituko hemen, kontzeptualki erdia zuhaitz Tajadura moduko Oraindik ari zaren zeren eta ez baitira inoiz eskuinaldean behera egingo. Beraz, gaur egun, 55-tik 33-I. Too txiki zenbaki bat da. 44 naiz bila, baina, gaur egun, 44 Zuhaitz hau bada, joan ahal izateko, jakina, I eskubidea ezagutzen dut. Beraz, berriro ere, erdia zuhaitz inausketa naiz. Pretty askoz ere berdin-berdina, eta kontzeptualki telefono-liburua da. Berdina da, zer egin dugu arbelean paperak, baina benetan guri aukera ematen duen egitura bat sofistikatuagoa da algoritmoaren diseinua hau zatitzeko eta konkistatzeko eta hain zuzen ere, egitura hau atsegin traversing - whoops. - Bezalako egitura bat Traversing, non da "Joan Modu horretan edo bide horretatik joan," kodea duten tolestuta your mind lehenengo atalean aplikatzeko guztiak esan nahi du edo haren bidez etxean oinez, bilaketa bitarra, errekurtsio edo iterazio erabiliz, lepoan mina da. Aurkitu erdiko elementua, eta ondoren, egin zure biribiltze gora edo behera. 

Ez dago edertasun bat da hau erabili ahal izango dugu orain delako errekurtsio berriz, baina askoz ere garbian. Izan ere, 55 zenbakia baduzu eta 44 aurkitu nahi baduzu, kasu honetan, ezkerrera joan gero, zer egin nahi duzu? Zehatza berean algoritmoa exekutatu nahiko duzu. Nodoaren balioa egiaztatu, ondoren, ezkerrera edo eskuinera joan beharko duzu. Ondoren, nodo balioa egiaztatzeko, joan ezkerrera edo eskuinera. Hori ederki errekurtsio egokitzen. Beraz, nahiz eta iraganean egin dugun errekurtsio inplikatuz adibide batzuk nahiko arbitrarioa ez zuela behar errekurtsiboa da, datuak stuctures batez ere, zuhaitz, arazo bat hartzeko ideia honen aplikazio ezin hobea da, shrinking, eta, ondoren, mota bereko, baina txikiagoa, programa konpontzeko. 

Beraz, ez dago beste datuak aurkeztu ahal izango dugu, egitura. Hau da Lehen begiratuan críptica bilatzeko diseinatu da, baina hau ez da harrigarria. Beraz, trie, trie den hitza berreskuratz heredatu izeneko datu-egitura bat da, eta hori ez da ahoskatzen berriro saiatu-val, baina horrek zer deiak munduko gauza horiek. Saiatuko da. T-r-i-e. Nolabaiteko egitura zuhaitz bat da, baina trie batean nodo bakoitzean agertzen da zer izan nahi du? Eta hau da, pixka bat engainagarria da abbreviated mota baita. Baina trie honetan nodo bakoitzean bezalakoa da benetan array bat dirudi. Eta nahiz eta diagrama honen egileak ez du erakusten, kasu honetan, trie hau datu egitura horren helburua bizitza hitz gordetzeko A-l-i-c-e edo B-o-b bezala. Eta modu hau azalera datuak Alice eta Bob eta Charlie eta Anita eta abar array bat erabiltzen du horren bidez Alice trie batean gordetzeko, array bat itxura erro-nodoa hasiko dugu, eta azkarra notazioan idatzita dago. Egileak zehazten ez abcdefg ez duten izenak ez delako. M eta P eta T erakutsi dute, baina kasu honetan, dezagun Alice eta Bob eta Charlie urruntzen diren izen batzuk hemen. Maxwell diagrama hau da, benetan. Beraz, nola egin egilearen dendan M-a-x-w-e-l-l? Zuen erroko nodoa hasi zen, eta joan [M], beraz, gutxi gorabehera 13, array kokapena 13an. Gero, hortik aurrera, ez da erakuslea da. Erakuslea A array beste liderra. Hortik aurrera egileak array horretan indexatuta kokapena A, honelako han goiko ezkerreko eta, ondoren, bere ondoren erakuslea duten array beste, eta erakuslea kokapena X. joan Ondoren, array hurrengo kokapena W, E, L, L, eta abar, eta, azkenik, dezagun benetan saiatu irudi bat jarri behar da hau. Zer da kode itxura nodo bat? Nodo bat trie bat gehiago nodo erakusleak array bat dauka. Baina ez da balio boolearra mota batzuk ere lortu izan da, gutxienez ezartzeko. Deitu du is_word gertatuko dut. Zergatik? Maxwell ari txertatu, ez delako ari zaren txertatu datu egitura honetan sartu ezer. Ez ari zara M. idazten ari zara X. idazten Guztiak egiten ari zaren erakusleak jarraituz. M, ondoren adierazten A erakuslea adierazten duen erakuslea, ondoren erakuslea X, W, E, L, L adierazten duen, baina zer amaieran egin behar duzun sort joan, egiaztatu da, kokaleku honetan iritsi naiz. Ez zen hitz bat eta ondorioz hemen datuak egitura. 

Beraz, zer trie bat da, benetan betetako eta egileak aukeratu irudikatzeko triangelu txiki terminuses horiek. Hau, besterik gabe esan nahi du, hain zuzen, triangelu hau da hemen, egia balio boolearra honetan esan nahi du, joan atzeraka zuhaitza izeneko Maxwell honetan hitz bat esan nahi du. Baina hitza foo, esate baterako, ez da, erroko nodoa dut hemen goian delako, zuhaitza Ez dago f erakuslea, o erakuslea ez, o erakuslea ez da. Foo hiztegi hau ez da izen bat. Baina, aitzitik, Turing, t-u-r-i-n-g. Berriz ere, ez nuen gorde t edo u edo r edo i edo n edo g. Baina denda nuen datuak egitura honetan modu egia behera hemen nodo honetan balio bat zuhaitza balio boolearra hori is_word ezartzen egia. Beraz, trie mota hau meta egitura oso interesgarria da, non ez zaren benetan hitzak gordetzeko beraiek hiztegi mota hau. Argi izan, besterik ez zaren bai edo ez gordetzeko, ez dago bueltarik, hemen hitz bat da. 

Orain zer inplikazioa? 150.000 hitz memorian gorde nahian ari zaren bada, hiztegi bat zerbait lotuta zerrenda bezala erabiliz, zure zerrenda lotutako 150.000 nodoen zoazen. Eta hitz horietako bat aurkitzeko alfabetikoki O (n) denbora har dezake. Lineala denbora. Baina kasu hemen trie bat, zer hitz bat aurkitzeko denbora da? Bihurtzen da hemen, edertasuna da, nahiz eta 149.999 dagoeneko hiztegi hau hitz, datu-egitura hau ezarri zenbat denbora ez aurkitzeko edo gehiago pertsona bat sartu horretan, Alice bezala, Alice hartu? Beno, 5 baino ez da, agian 6 amaierako karaktere urratsak. Egitura izenak beste presense delako Alice txertatu modu ez iritsi. Gainera, Alice aurkitzeko daude 150.000 hitz behin hiztegia ez zure Alice aurkitzeko modu guztietan, Alice dagoelako. . . . . Hemen, boolear bat aurkitu dudalako. Eta ez da boolearra egia, orduan Alice ez bada hitz datu-egitura honetan. Beste era batera esanda, gauzak aurkitzeko eta sartzean gauza berri honetan sartzeko denbora datuak trie O egitura - ez da n. Alice on 150.000 pertsona presense ez du eraginik izango denez, badirudi. Hargatik k, non k ingelesez hitz baten gehienezko luzera hau da, normalean ez da gehiago 20-zerbait karaktere baino. Beraz, k konstante bat da. Holy Grail Beraz, orain badirudi da, trie txertatzen denbora etengabeko bilaketak, ezabaketen. Dagoeneko egituran gauzak kopurua delako, horiek ez dira, nahiz eta fisikoki ez dago. Berriz ere, ari dira ordenatzeko hautatuta off, bai ala ez, eragina ez du bere etorkizuneko denbora exekutatzen ari. 

Baina ez da harrapaketa bat eskuratu, bestela genuke ez alferrik galtzen hainbeste denbora horiek beste datu guztiak egitura, azkenik, sekretu bat amazing. Beraz, zer prezio ordaindu dira handitasuna hau lortu nahi dugu hemen? Space. Gauza hau da masiboak. Eta arrazoia, egilearen ez aurkeztu hemen, konturatu array itxura gauza horiek guztiak, ez zuen marraztu zuhaitzaren gainerako, trie-gainerako Oraindik ez dute besterik ez delako Istorioa garrantzitsua. Baina nodo horiek guztiak dira super zabal, eta zuhaitza nodo guztietan hartzen du 26 edo, benetan, 27 karaktere izan daiteke, kasu honetan apostrophe, espazio dudalako barne beraz, apostrophized hitz ezin izan dugu. Kasu honetan, zabala array dira. Beraz, nahiz eta ez ari picutured hau RAM zenbatekoa masiboa bat hartzen du. Zein fina izan daiteke, especilly hardware modernoan, baina hori denerako. Denbora gutxiago dugu, leku gehiago gastatu. Beraz, non da hori guztia? Beno, egin dezagun utzi hemen ikus-en. Egin dezagun salto bat lasaia hau hemen. 

Sinetsi edo ez, askoz ere fun C gisa denbora pixka bat izan da, gaur egun, seihilekoan bertan gauza gehiago moderno trantsizio time puntu iristen ari gara. Buruzko goi mailako Things. Eta nahiz eta hurrengo bi aste, nahiz eta oraindik ere jarraituko dugu geure burua, erakusleak eta memoria kudeaketa munduan murgiltzeko horrek batera eraiki ahal izango dugu, orduan on erosotasuna lortzeko, azken jokoa da, azken finean, aurkeztu ironikoki, ez da hizkuntza hau. Gastatzen dugu, 10 minutu HTML buruz hitz egin bezala. HTML da markaketa dauka hizkuntza bat da, eta zer da markup language parentesi artean irekia eta itxia parentesi artean esan 'hau bold' serie horiek 'Letra etzanez honetan' egin zentratua hau '. Ez da hori intelektualki interesgarria,, baina super erabilgarria da. Eta, zalantzarik gabe da nonahiko egun hauetan. Baina zer HTML munduko buruz indartsua, eta web programazioa, oro har, gauza dinamikoa eraikitzeko; Python edo PHP edo Ruby edo Java edo C # bezalako hizkuntzetan kodea idatziz. Benetan, edozein zuk aukeratutako hizkuntzan da, eta HTML dinamikoki sortzeko. Zerbait izeneko CSS dinamikoki sortzen. Kaskadako estilo-orriak, hau da, estetika buruz ere. Eta, beraz, nahiz eta, gaur egun, ezagutzen Google.com bezalako web batzuk I joan bada, ikusteko eta, developer, ikusi, agian egin duzun aurretik joan I, baina iturri bat ikusteko joan, stuff hau seguruenik itxura polita críptica. Baina hau azpiko kodea duten Google.com inplementatzen da. Frontend On. Eta benetan hori guztia Fluffy estetika stuff da. Hau CSS da hemen. Mantentzeko I scrolling badu behera, kolore-kodetua stuff batzuk lortuko dugu. Hau da, HTML. Google-ren kodea gaizki baten itxura du, baina benetan I ireki beste leiho bat. egitura batzuk ikus ahal izango dugu hau. Ireki dut hau bada, konturatu hemen, apur bat gehiago irakurgarria da. Etiketa honek luzea aurretik goaz, [hitza] tag bat da, HTML, burua, gorputza, div, gidoia, testu-eremuan, span, zentratua, div. Eta hori ere críptica begira ordenatzeko Lehen begiratuan, baina nahaspila hau guztia, zenbait ereduak, eta eredu Errepikagarria beraz, behin oinarriak lortuko dugu behera, hau atsegin kodea idatzi ahal izango duzu eta, ondoren, manipulatu, oraindik beste hizkuntza bat erabiliz, deitzen JavaScript kodea. Eta Ikusteko Javascript-a nabigatzaile baten barruan doan hizkuntza gaur egun Harvard ikastaroak, erabiltzen dugun ikastaroaren merkataritza-tresna Google maps erabiltzen duen dinamismo sorta osoa emateko, Facebook da egoera-eguneratzeak berehalako erakusteko, Twitter erabiltzen erakusteko tweets berehala. Hori guztia hasiko dugu geure burua murgildu sartu egingo Baina iritsi, Internet buruzko zerbait pixka bat ulertu behar dugu. Clip hau hemen Minutu bat besterik ez da, eta gaur egun, hau da, hain zuzen ere bere gain hartzen dezagun, Internet zer etorri teaser gisa lan egiten du. Ematen dizut "Sare Warriors". 

[♫ Slow koru musika ♫] [Gizonezkoa narratzailea] zen mezu bat zuen. Protokolo bat bere guztiak. [♫ Faster musika elektronikoa ♫] , Suebakien cool mundu bat etorri zen, routers uncaring eta arriskuak urrun heriotza baino okerragoa. Azkarra da. Indartsua da. TCP / IP zuen, eta berak zure helbidea lortu. Sarean Warriors. [Malan] Datorren astean, orduan. Internet. Web programazioa. Hau CS50 da. [CS50.TV]