[Predvajanje glasbe] DAVID J. Malan: Dobro. To je CS50. To je pet teden nadaljuje, in mi dobre novice in slabe novice. Torej, dobra novica je, da CS50 začenja ta petek. Če bi radi, da se nam pridružite, glavo na običajno URL tukaj. Še bolje novica, no predavanje to prihaja ponedeljek 13.. Nekoliko manj boljše novice, Kviz je nič naslednjo sredo. Več podrobnosti lahko najdete na tem URL tukaj. In v naslednjih nekaj dneh bomo lahko izpolnite prazne v zvezi s prostori da bo smo rezerviran. Boljša novica je, da bom je pregled seveda vsej zasedanje tega prihaja Ponedeljek zvečer. Ostanite z nami, da seveda je Spletna stran za kraj in podrobnosti. Profili, čeprav je praznik, se bo sestal tudi kot dobro. Najboljša novica, predavanje naslednji petek. Torej je to tradicija smo imajo, glede na učni načrt. Samo-- se dogaja, da je neverjetno. Boste videli stvari, kot so podatkovne strukture konstanten čas in razpršene tabele in drevesa in se trudi. In se bova pogovorila o problemih rojstni dan. Cel kup stvari čaka naslednji petek. OK. Kakorkoli že. Tako opozarjajo, da smo bili s poudarkom na tej sliki, kar je Notranjost spomin našega računalnika. Torej pomnilnik ali RAM je, če programi obstaja, ko ste jim teče. Če dvakrat kliknete icon teči nekaj programa ali dvokliknite icon odpreti neko datoteko, to je natovorjen s trdega pogon ali pogon SSD v RAM, Random Access Memory, kjer živi do izpada električne energije, pokrov laptop zapre, ali zaprete program. 

Zdaj, spomin, od ki imate verjetno 1 gigabajta te dni, 2 gigabajte ali celo veliko več, je na splošno določeno za določen program V to vrsto pravokotne konceptualni model pri čemer imamo kup na dnu in kup drugih stvari na vrhu. Stvar na samem vrhu smo videli na tej sliki prej, vendar nikoli ni govoril o je tako imenovani besedilo segmenta. Segment besedilo je samo fancy način rekel ničel in enic, ki sestavite vaše dejanske prevedenega programa. 

Torej, ko dvokliknite Microsoft Word na vašem Mac ali PC, ali ko zaženete piko poševnica Mario na Linux računalnik na vašo terminalsko okno, ničle in tisti, ki sestavljajo Beseda ali Mario se začasno shranijo iz računalnika RAM v tako imenovani Besedilo odsek za določen program. Spodaj, da gre inicializiran in neinicializirane podatke. To je stvar, kot so globalne spremenljivke, da smo ne uporablja veliko, ampak včasih smo jih imela globalne spremenljivke ali statično opredeljena strune, ki je težko kodirane besede, kot so "zdravo" da se ne sprejemajo od uporabnika ki so težko kodirane v vaš program. 

Zdaj, navzdol na dnu smo imajo ti dimnika. In stack, tako daleč, da smo bili uporabi za kakšne vrste namene? Kaj je bil sveženj uporablja? Ja? 

Ciljna publika: Funkcije. 

DAVID J. Malan: Za funkcije? V kakšnem smislu za funkcije? 

OBČINSTVO: Ko pokličete funkcijo, Argumenti se kopira na kupu. 

DAVID J. Malan: Točno tako. Ko pokličete funkcijo, njegova Argumenti se kopira na kupu. Torej vse X ali Y ali je ali B je da ste poteka v funkciji začasno dajo na tako imenovani dimnik, tako kot eden od Annenberg jedilnici pladnje, in tudi stvari, kot lokalne spremenljivke. Če je vaš foo funkcija ali vaš swap Funkcija imajo lokalne spremenljivke, kot temp, ta dva končajo na kupu. Zdaj, mi ne bo govoril preveč o njih, vendar te spremenljivke okolja Na dnu smo videli pred časom, ko Sem futzing na tipkovnici en dan in sem začel dostop do stvari kot argv 100 ali argv 1000, Pravkar elements-- sem pozabil numbers-- ampak da ne bi smel biti dostopni zame. Začeli smo videli nekaj funky simboli na zaslonu. Tisti, ki so bili tako imenovani spremenljivke okolja kot globalnih nastavitvah za moj Program ali za računalnikom, ne povezana z nedavno bug, da smo se pogovarjali, Shellshock, da je bilo Mori kar nekaj računalnikov. 

Zdaj nazadnje, v današnjem poudarkom bomo v končni fazi na kup. To je še en kos pomnilnika. In v bistvu vse to Pomnilnik je ista stvar. To je enako strojno opremo. Mi smo nekako zdravljenje različnih skupin bajtov za različne namene. Heap se tudi dogaja, da je tam, kjer spremenljivke in spomin, ki ga zahtevajo od operacijskega sistema začasno shranjeni. 

Vendar pa je nekako problem tukaj, kot kaže slika. Smo nekako še dva ladje okrog, da trčijo. Saj, kot ste uporabili več kupa, in kot vidimo danes dalje, kot ste uporabili več in več heap, zagotovo slabe stvari se lahko zgodi. In res, lahko povzroči, da namerno ali nenamerno. Torej je Cliffhanger zadnji Čas je bil ta program, ki ne služi katera koli funkcionalna namen, razen za dokazovanje kako vam lahko kot slab človek dejansko lahko Prednost hroščev v programu nekoga in prevzeti program ali celo Celoten računalniški sistem ali strežnik. Torej, samo da bi pogled na kratko, ti obvestilo, da je glavna na dnu sprejme v ukazni vrstici trditve, kot na argv. In to je klic funkcije f, v bistvu brez imena funkcijo imenovano f, in to gre v argv [1]. 

Torej, ne glede na besedo uporabnik vnese v na poziv po imenu tega programa, in potem je to samovoljno funkcija up top, f, bo v nizu, AKA char * kot smo začeli, da bi razpravljali, in to samo imenuje "bar". Vendar bi ga lahko imenovali nič. In potem izjavlja, znotraj F, niz znakov imenovano C- 12 takih znakov. 

Zdaj, z zgodbo sem povedal pred nekaj trenutki, kjer je v spomin c je, ali so tisti, ki 12 ožge bo končalo? Samo da bo jasno. Ja? 

OBČINSTVO: Na kupu. 

DAVID J. Malan: Na kupu. Torej je c lokalna spremenljivka. Mi vas prosimo, za 12 znakov ali 12 bajtov. Tisti, ki se bo končalo o tako imenovanem dimnika. Zdaj končno je ta druga funkcija To je pravzaprav zelo koristno, vendar smo v resnici ne uporablja to sami, strncopy. To pomeni niz kopijo, vendar samo črke n, n znakov. Tako bo n znakov biti kopira iz bara v c. In koliko jih je? Dolžina bar. Torej, z drugimi besedami, da ena vrstica, strncopy, gre za kopiranje učinkovito bar se v c. 

Zdaj pa, samo da nekako predvideti Nauk te zgodbe, kar je potencialno problematična tukaj? Čeprav smo preverjanje dolžine droga in njegovo posredovanje v strncopy, kaj je tvoj gut govoriš, da si je še vedno razdeljena glede tega programa? Ja? 

OBČINSTVO: Ne vključuje soba za null značaja. DAVID J. Malan: Ne vključuje soba za null značaja. Potencialno razliko preteklo prakso ne bomo niti Toliko kot plus 1 k sprejme ta null značaj. Ampak to je še slabše kot to. Kaj drugega nam ne bodo storili? Ja? 

OBČINSTVO: [neslišno] DAVID J. Malan: Popolna. Mi smo težko kodirane 12 precej samovoljno. Da ni toliko problem, vendar je dejstvo, da sva sploh ne preverja, če dolžina vrat je manj kot 12, v tem primeru se bo varno, da ga v spomin imenovano c, da smo dodeljen. Dejansko, če je bar je kot 20 znakov, zdi, da ta funkcija za kopiranje 20 znakov iz bara v c, s čimer ob vsaj 8 bajtov da ne bi smelo biti. To je posledice tukaj. 

Torej, na kratko, zdrobljen programa. Ni tak big deal. Morda boste dobili napako segmentacije. Vsi smo imeli napake v programih. Vse, kar bi lahko žuželke v programih, prav zdaj. Toda kaj je posledice? No, tukaj je Povečano-in verzija da je slika spomina mojega računalnika. To je dno mojega dimnika. In res, na samem dnu je tisto, kar je imenovano matično rutinsko stack, fancy način bi rekel, da je glavni. Tako, da kdor se imenuje funkcija f, da govorimo o tem. Torej je to dno kupa. Povratni naslov je nekaj novega. To je bila vedno tam, bila vedno na tej sliki. Mi samo nikoli opozoril na to. Ker se je izkazalo, kako c deluje, je da ko ena funkcija zahteva drugega, ne le argumente, ki Funkcija se potisne na kup, ne le funkcija je lokalna spremenljivke se potisne na kup, nekaj, kar se imenuje povratni naslov dobi tudi dal na kupu. Natančneje, če je glavna zahteva Foo, glavni je lastni naslov v pomnilniku, ox nekaj, dejansko dobi dal na kupu tako da, ko je f narejeno tako izvršitve ne ve, kje naj skoči nazaj v besedilu segment, da bi še naprej izvršitve. 

Torej, če smo tukaj konceptualno, V glavnem, potem dobi f klical. Kako f ve, kdo za nadzor vrniti? No, ta mali Orientacijska v red tukaj, imenuje naslov vrnitev, samo preverjanja, kaj je to povratni naslov? Oh, mi skoči nazaj na glavno tukaj. In to je malo njen pomen, ker ničel in enic za glavno tehnično tu v tech segmentu. Ampak to je ideja. f samo mora vedeti, kaj , kjer nadzor v končni fazi gre nazaj. 

Ampak način računalniki že dolgo določeno stvari kot lokalne spremenljivke in argumentov je, kot je ta. Tako da na vrhu te slike v blue je kup okvir za f, tako da vse pomnilnika, da f še posebej je s pomočjo. Torej zato, opazili, da se bar je na tej sliki. Bar je bil njen argument. In mi je trdil, da so trditve, da Funkcije se potisne na kup. In c, je seveda tudi te slike. 

In samo za namene, simbolov, opazili v zgornjem levem kotu je, kaj bi bilo c nosilec 0 in nato rahlo navzdol v desno je c nosilec 11. Torej, z drugimi besedami, si lahko predstavljate da je grid bajtov tam, od katerih prva je zgoraj levo, katere dno je zadnja od teh 12 bajtov. 

Toda zdaj poskušajo za previjanje naprej. Kaj se bo zgodilo, če se peljemo v godalni vrstici, ki je več kot c? In ne bomo preverjanje, če to je res več kot 12. Kateri del te slike bo se prepiše bajtov 0, 1, 2, 3, dot dot, 11, in nato slab, 12, 13 do 19? Kaj se bo zgodilo tukaj, Če sklepamo iz naročanje da c nosilec 0 je na vrhu in c nosilec 11 je nekako navzdol da ali ne? Ja? 

OBČINSTVO: No, to se dogaja prepisati char * bar. 

DAVID J. Malan: Ja, izgleda, da boš prepisati Char * bar. In še huje, če boste poslali v res dolgo Niz, boste morda celo prepisati kaj? Naslov povratka. Ki je spet, je prav tako kot Orientacijska povedati programu, če , da se vrnete, ko f poteka pozivu. 

Torej, kaj slabi fantje običajno storijo je, če naletijo na programu da so radovedni, ali je izkoriščati, vozičkom tako da je on ali ona lahko Prednost tega hrošča, običajno ne dobijo To pravico je prvič. Pravkar so začeli pošiljati, na primer, naključne nize v svoj program, ali na tipkovnici, ali odkrito verjetno napišite majhen program, da samo samodejno ustvari strune, in začeti razbijati od programa, ki ga pošilja v veliko različnih vhodov na različnih dolžin. 

Takoj, ko je vaš program zruši, To je nekaj neverjetnega. Ker to pomeni, da je ali je bila odkrita kar je verjetno res bug. In potem lahko dobite več pameten in začeti s poudarkom ožje o tem, kako izkoristiti to napako. Še posebej, kar on ali ona morda storiti, je poslati, v najboljšem primeru, zdravo. No big deal. To je niz, ki je dovolj kratko. Kaj pa če je on ali ona pošlje, in jo bomo posploševati kot, napad code-- tako ničel in tisti, ki počnejo stvari kot rm-rf, da odstranite vse iz trdega diska ali pošiljanje neželene elektronske pošte ali nekako napad stroj? 

Torej, če bi vsak od teh Črke samo pomeni, konceptualno, napad, napad, napad, napad, nekateri slabo kodo da je nekdo drug napisal, ampak če je ta oseba dovolj pametna ne samo vključujejo vse teh RM-RFS, ampak tudi imajo njegove zadnjih nekaj bajtov je število, ki ustreza na naslov njegovega ali sama napad koda da je on ali ona opravil v samo tako, da ga na poziv, lahko učinkovito trik računalnik v opazil, ko je f storiti izvršitve, oh, to je čas, da skočite nazaj na rdečo povratni naslov. Ampak zato, ker je on ali ona je nekako prekrivale, da povratni naslov s svojo lastno številko, in oni so dovolj pametni, da je zasnovana tako, da Številka sklicevati, saj vas glej v super top levem kotu tam, dejanski naslov v računalniku Spomin na nekaj svojih napad kodo, slab človek lahko trik računalnik v izvršilni svojo lastno kodo. 

In to kodo, še enkrat, je lahko karkoli. To je na splošno imenovana lupina koda, ki je pravkar način rekel, da to ni na splošno nekaj tako enostavno, kot rm-RF. To je pravzaprav nekaj podobnega Bash, ali dejansko program, ki ga daje ali njen programski nadzor izvajati karkoli drugega, ki to želijo. Torej, na kratko, vse to izhaja iz preprostega dejstva, da ta bug vpleteni ne preverja meje vaše bivanje. In zato, ker je način računalniki delo je, da se uporabite stack od učinkovito, konceptualno, spodaj na gor, potem pa elementi pritisneš na kupu rastejo navzdol top, to je zelo problematično. Zdaj obstajajo načini za delo okoli tega. In odkrito povedano, obstajajo jeziki s katerimi obidete. Java je imunski, na primer, na to vprašanje. Ker se vam ne dajejo napotke. Se vam ne dajejo neposredne naslove spominske. Torej s tem moč, da imamo dotakniti ničesar v spomin Želimo, da prihaja, seveda, veliko tveganje. 

Torej pazi. Če je, odkrito povedano, v prihodnjih mesecih ali let, da pridejo, kadarkoli boste brali o nekem izkoriščanju programa ali strežnika, če ste že kdaj videli namig nečesa kot buffer overflow napadi, ali kup overflow je druga vrsta napada, pisane v duhu, kar navdihuje spletne strani ime, če ga poznate, je vse govoriš samo prepolno velikosti neke značaja matrika ali nekaj matrika bolj na splošno. Vsa vprašanja, nato na to? Ne poskušajte tega doma. 

V redu. Torej malloc je bila doslej naša nova prijatelj, da bomo lahko dodeliti pomnilnika da ne bomo nujno vedeti napreduje, da želimo, da nimamo trdega kodo v našo število programov, kot so 12. Ko nam uporabniku pove, koliko Podatki on ali ona želi vhod, lahko malloc, da je veliko pomnilnika. 

Torej malloc se izkaže, da Koliko smo se ga uporablja, izrecno zadnji čas, nato pa fantje so ga s pomočjo za getstring nevede za nekaj tednov, vse pomnilnika malloc je prihaja iz tako imenovanega kup. In zato getstring, na primer, mogoče dodeliti pomnilnika dinamično ne da bi vedel, kaj ste dogaja, da tip vnaprej, ti pa vrnejo kazalec na ta spomin, in da je spomin še vedno obdržite, tudi po getstring donose. Ker odpoklic po vsem tem Snop se nenehno dogaja gor in dol, gor in dol. In takoj, ko gre določa, da je katera koli pomnilnika Ta funkcija se uporablja, naj ne bo nihče drug uporablja. To je nerazumljivo vrednote zdaj. 

Ampak kup je tu. In kaj je lepo o malloc je, da ko malloc dodeljuje pomnilnik tu gor, to ni vplivalo na večina del, ki jih je kupu. In tako se lahko vsaka funkcija dostop pomnilnika, ki je bil malloc'd, tudi s funkcijo kot getstring, tudi potem, ko se je vrnil. 

Zdaj, nasprotno od funkcije malloc je brezplačna. In res, ti pravilo morali začeti o sprejetju je vsak, vsak, kadarkoli boste uporabili malloc morate sami uporabljate brezplačno, na koncu, na isti kazalec. Ves ta čas smo bili pisno buggy, buggy kodo, zaradi mnogih razlogov. Vendar pa je eden, ki je uporabo knjižnice CS50, ki sam je namerno buggy, pušča spomin. Vsakič, ko sem poklical getstring v zadnjih nekaj tednih smo asking poslovanja sistem Linux, za spomin. In nikoli, ko ga dal nazaj. In to ni v praksa, dobra stvar. 

In Valgrind, ena orodja, uvedene v pset 4, je vse o vam bomo pomagali Zdaj našli hrošče, kot je ta. Toda na srečo pset 4, vam ni treba uporabiti knjižnico CS50 ali getstring. Torej, vse napake, povezane s spominom so na koncu bo svoje. 

Torej malloc je več kot le primeren za ta namen. Mi lahko dejansko zdaj rešiti bistveno različne težave, in temeljito reševanje problemov več učinkovito kot na obljubo Tedensko ZERO. Doslej je to najbolj seksi podatkovne strukture smo imeli. In podatkovne strukture I pomeni samo način konceptualizaciji pomnilnika na način, ki presega samo rekel, to je int, je to znak. Lahko začnemo kasetnih stvari skupaj. 

Torej matrika videti takole. In kaj je bilo ključnega pomena pri približno Niz je, da vam daje back-to-back kosi spomin, od katerih je vsak se bo istega tipa, int int, int, int ali char, char, char, char. Toda obstaja nekaj slabosti. Ta primer je matrika velikosti šest. Recimo, da se zapolni ta niz s šestimi številke in nato, zaradi kakršnega koli razloga, vaš uporabnik želi, da bi vam sedmi številko. Kje si ga dal? 

Kaj je rešitev, če imate ustvaril niz na sklad, na primer, samo z tedna dva zapisa, da bomo uvedli, kvadratnih oklepajih s številnimi znotraj? No, imaš šest Številke v teh poljih. Kaj bi svojim instinktom bilo? Kje bi si želeli, da bi ga? 

OBČINSTVO: [neslišno] 

DAVID J. Malan: Oprostite? 

OBČINSTVO: Daj ga na koncu. 

DAVID J. Malan: Daj na koncu. Torej nekaj več kot na desni, izven tega prostora. Kar bi bilo lepo, vendar pa Izkazalo se je, da ne morem storiti. Ker če si ne prosi Za ta kos pomnilnika, da bi se lahko po naključju to to se nekatere druge spremenljivke uporablja celoti. Pomisli nazaj teden ali dva, ko smo jih out Zamyla and Davin and Gabe je imen v pomnilniku. Bili so dobesedno back to back to back. Torej, ne moremo nujno Verjamemo, da Karkoli tukaj je na voljo za mene za uporabo. 

Torej, kaj še lahko naredil? No, ko ti zavedali Potrebujemo paleto velikosti sedem, si lahko samo ustvariti array velikosti sedem nato uporabite zanke for ali while zanko, kopirajte v novo paleto, in potem nekako le znebiti Ta matrika ali samo prenehate uporabljati. Ampak to ni posebej učinkovita. Skratka, nizi, ne pustite ti dinamično spreminjanje velikosti. 

Torej, na eni strani dobiš random access, kar je neverjetno. Zato, ker nam omogoča delati stvari kot so deli in vladaj, binarno iskanje, kar smo jih govorili na zaslonu tukaj. Ampak ti si slikal v kotu. Takoj, ko ste zadeli konec tvoje matrike, moraš narediti zelo draga operacija ali pisati cel kup kode Do zdaj se ukvarjajo s tem problemom. 

Pa kaj, če namesto tega smo imeli nekaj, kar se imenuje seznam, ali povezani seznam zlasti? Kaj pa, če namesto da pravokotniki back to back to back, imamo pravokotnike, ki puščajo malo malo Vrckanje prostora med njimi? In čeprav sem to pripraviti slika ali prilagoditi to sliko iz ene od besedil tukaj nazaj na back to back zelo urejeno, v resnici, eden od teh pravokotnikov bi lahko tukaj v spomin. Eden od njih bi lahko tu gor. Eden od njih je lahko tukaj, tukaj, in tako naprej. 

Toda kaj, če smo opozorili, v tem primeru, puščice da nekako povezati ti pravokotnikov skupaj? Dejansko smo videli tehnična inkarnacija puščico. Kaj smo uporabili v nedavnem dni, da se pod pokrovom motorja, je predstavnik puščico? Kazalec, kajne? 

Pa kaj, če namesto Samo shranjevanje številk, kot 9, 17, 22, 26, 34, Kaj pa, če mi ne shranijo Samo število ampak kazalec ob vsakem takem številu? Tako, da je veliko, kot bi navoj iglo skozi cel kup materiala, nekako vezanje stvari skupaj, podobno lahko smo s kazalci, kot so inkarnirali s puščicami tukaj, vrste pletejo Ti posamezni pravokotniki z učinkovito uporabo kazalec poleg vsakega številko, da opozarja na nekaterih naslednjo številko, da poudarja, da v zameno nekaj naslednja številka? Torej, z drugimi besedami, kaj če bi dejansko želeli izvesti kaj takega? No, na žalost, ti pravokotniki, Vsaj ena z 9, 17, 22, in tako naprej, to ni več lepo trgi z ločenima številkami. Dno, pravokotnik pod 9, na primer, predstavlja to, kar bi morala je kazalec, 32 bitov. Zdaj, jaz še nisem seznanjen z nobenimi podatkovni tip v C-ju, ki vam omogoča ne samo int vendar je kazalec v celoti. 

Torej, kaj je rešitev, če želimo izumiti lastne odgovor na to? Ja? 

OBČINSTVO: [neslišno] 

DAVID J. Malan: Kaj je to? 

OBČINSTVO: Nova struktura. 

DAVID J. Malan: Ja, zakaj ne bomo zgradili novo strukturo, ali C, struct? Videli smo konstruktov prej, če za kratek čas, kjer smo se ukvarjali s strukturo študentov kot je ta, ki je imel ime in hišo. V pset 3 zlom ste uporabili celoten kup structs-- GRect in GOvals da Stanford ustvarjena za cluster informacije skupaj. Pa kaj, če bomo to isto idejo ključne besede "typedef" in "struct," in potem nekaj študent specifične stvari, in razvijajo to v naslednje: typedef struct node-- in vozlišča samo zelo generično računalništvo izraz za nekaj, kar v strukturi podatkov, vsebnik v podatkovno strukturo. Vozlišče Trdim, se dogaja, da imajo int n, povsem enostavna, nato pa malo bolj cryptically, ta druga vrstica struct vozlišče * naslednji. Toda v manj strokovnih izrazov, kaj je to druga vrstica kode notranjosti zavitimi oklepaji? Ja? 

OBČINSTVO: [neslišno] DAVID J. Malan: kazalec na drugo vozlišče. Torej res, skladnje malo skrivnosten. Ampak, če ste prebrali dobesedno, Naslednja je ime spremenljivke. Kakšna je njegova vrsta podatkov? To je malce verbose tokrat, ampak to je tipa struct vozlišče *. Vsakič, ko smo videli nekaj zvezdo, ki pomeni, da je kazalec za to vrsto podatkov. Torej, naslednjič, je očitno kazalec na struct vozlišče. 

Zdaj, kaj je struct vozlišče? No, opazil vidite tiste iste besede v zgornjem desnem kotu. In res, boste videli tudi besedo "Node" tukaj na spodnji levi strani. In to je pravzaprav samo udobje. Opazimo, da v naši definiciji študentski tam je beseda "študent" samo enkrat. In to zato, ker študent objekt ni bil sama nase. Nič ni notri študenta da je treba opozoriti na drug študent, persay. To bi bilo nekako čudno v resničnem svetu. 

Toda s vozlišče v povezan seznam, bomo želeli vozlišče da se referenčni s podobnim ciljem. In tako opazite spremembo tukaj ni samo tisto, kar je znotraj zavitimi oklepaji. Vendar pa smo dodali besedo "node" na vrhu kot tudi dodajanjem na dnu namesto "študenta". In to je samo tehnična podrobnost tako da, še enkrat, vaš struktura podatkov lahko sama nase, tako da vozlišče lahko kažejo na drugo takšno vozlišče. 

Torej, kaj je to na koncu bo to pomenilo za nas? No, ena, te stvari v notranjosti je vsebina našega vozlišča. Ta stvar tu gor, zgoraj desno, samo zato, da da spet lahko govorimo sebi. In potem najbolj oddaljene stvari, čeprav vozlišče je nov izraz morda je še vedno Enako kot študent in kaj je pod pokrovom v SPL. 

Torej, če smo zdaj želeli začeti izvajanje te povezani seznam, kako bi lahko prevedli kaj takega kodo? No, pa sem videl samo Primer programa, ki dejansko uporablja povezani seznam. Med današnjim distribucijskega kodo je program, imenovan Seznam Zero. In če sem teči to sem ustvaril super preprost GUI, grafični uporabniški vmesnik, ampak to je res samo printf. In zdaj sem sam dal nekaj meni options-- Delete, Insert, iskanje, in Traverse. In Končaj. To so le skupne operacije na podatkovna struktura znana kot seznam povezav. 

Zdaj, Delete bo Številko zbrišete s seznama. Vstavi se dogaja, da dodate številka na seznamu. Iskanje se bo izgledalo za številko na seznamu. In premikanja je samo fancy način rekel, sprehod po seznamu, natisnete, ampak to je to. Ne spreminjajo na kakršen koli način. 

Torej poskusimo to. Pojdimo naprej in tip 2. In potem bom vstavite številko, pravijo 9. Enter. In zdaj moj program je le programirana reči, seznam je zdaj 9. Zdaj pa, če grem naprej in pa spet vstavite, naj grem naprej in pomanjšanje in tip v 17. Sedaj je moj seznam, je 9, potem 17. Če bi še enkrat vstaviti, pa preskočite enega. Namesto, da bi 22, kot je na sliki smo jih gledal sem, naj skoči naprej in vstavite 26 naprej. Torej bom tip 26. Seznam je kot pričakujem. Toda zdaj, samo da vidim, če to kodo se bo fleksibilna, pusti me zdaj tip 22, ki je vsaj konceptualno, če smo Ohranitev te razporejene, ki je dejansko bo še en cilj, prav zdaj, bi morala iti v med 17. in 26.. Zato sem zadeti nastopiti. Dejansko, da deluje. In zdaj mi vstavite nazadnje, na sliki, 34. 

V redu. Za zdaj naj določi, da Brisanje in Traverse in iskanje storiti, v resnici deluje. V bistvu, če ne bom teči iskanje, dajva poiščete številko 22, Enter. 22 je mogoče najti. Torej, to je tisto, kar ta Program Seznam Zero počne. 

Toda kaj se dejansko dogaja o, ki izvaja to? No, najprej bi morali, in dejansko Imam, datoteka z imenom list0.h. In nekje je to linija, typedef struct vozlišče, potem imam zavitimi oklepaji, int n, in potem struct-- kaj je definicija? Struct vozlišče naslednji. Zato moramo zvezdo. Sedaj tehnično smo prišli v Navada je risba tukaj. Lahko vidite učbenikov in Spletne reference to storite tam. To je funkcionalno enakovredna. V bistvu, to je malo bolj tipično. Ampak bom biti skladni s kakšnimi sva zadnjič in to. In potem na koncu, bom to naredil. 

Torej v glavi datoteke nekje v list0.h Danes je ta opredelitev struct, in morda nekatere druge stvari. Medtem v list0c tam bo še nekaj stvari. Ampak bomo samo začeti in ne končati to. List0.h je datoteka želim v mojem C datoteko vključiti. In potem na neki točki sem dogaja, da imajo int, glavno, nična. In potem bom imajo nekaj opravkov je tukaj. Jaz sem tudi dogaja, da imajo Prototip, kot nična, iskanje, int, n, katerih namen v življenju je za iskanje elementa. In potem tukaj Trdim v današnja koda, nična, iskanje, int, n, no podpičje vendar odprta zavitimi oklepaji. In zdaj bi rad nekako iskanje za element v tem seznamu. Vendar nimamo dovolj Informacije na zaslonu še. Imam dejansko ni predstavljal seznam sam. Torej en način, da bi lahko izvajala povezani seznam v programu je nekako želijo narediti nekaj kot izjavljam povezani seznam tukaj. Zaradi enostavnosti, bom, da bi ta globalni, čeprav Na splošno ne bi smeli početi to preveč. Vendar bo poenostavil ta primer. Torej, želim, da razglasi povezani seznam tukaj. Zdaj, kako lahko to storim? 

Tukaj je slika povezanega seznama. In jaz res ne vem trenutno kako Jaz grem pa predstavlja Toliko stvari z enim samim spremenljivka v pomnilniku. Vendar pomislite za trenutek. Ves ta čas smo imeli strune, ki smo jih nato je pokazala, da so nizi Znaki, ki jih nato je pokazala, da samo se pointer na prvi znak v niz znakov da je null zaključi. Torej s to logiko, in s tem picture vrsta sejanje svoje misli, kaj potrebujejo smo pravzaprav napisali v našem koda za zastopanje povezani seznam? Koliko te informacije potrebujemo ujeti v C kodo, bi rekli? Ja? 

OBČINSTVO: Potrebujemo kazalec na vozlišče. DAVID J. Malan: kazalec na vozlišče. Še posebej, ki node bi bil vaš instinkt je, da kazalec? 

OBČINSTVO: prvo vozlišče. 

DAVID J. Malan: Ja, Verjetno je samo prvi. In opazil, prvi vozlišče je drugačna oblika. To je samo polovica velikost struct, ker je res samo kazalec. Torej, kaj lahko v resnici storiti, je razglasila povezani seznam, da bi tipa vozlišča *. In kaj je to šele prvi klic in ga inicializirati na nič. Torej null, še enkrat, je prišel v sliko tukaj. Ne samo, da je nična uporablja kot kot posebna vrne vrednost za stvari, kot getstring in malloc, null tudi nič kazalec, pomanjkanje kazalcem, če hočete. To samo pomeni nič, je še tukaj. Zdaj prvič, lahko imam imenujemo to karkoli. Lahko bi ga imenovali "seznam" ali poljubno število drugih stvari. Ampak jaz sem jo kliče "prvi", tako da it uravna s te slike. Torej samo kot niz lahko predstavljal z naslovom prvi bajt, Tako lahko povezani seznam. In bomo videli druge podatke strukture zastopa z enim samim kazalnikom, 32-bit puščica, ki kaže na zelo prvo vozlišče v strukturi. 

Ampak zdaj pa pričakujemo težave. Če sem le spomnimo v mojem programu naslov prvega vozla, prvi pravokotnik, v to strukturo podatkov, Kaj je bolje, da se primer o Izvajanje preostanek svojega seznama? Kaj je ključna podrobnost, ki se dogaja da bi to zagotovili dejansko deluje? In "dejansko deluje" I pomeni, podobno kot niz, upamo, nam gredo od prvega znaka v imenu Davin k drugi, da tretjič, četrtič, do samega konca, Kako vemo, kdaj smo na koncu iz povezanega seznama, ki izgleda takole? Ko je nična. In sem predstavljal te vrste, kot je kot električni inženir moči, z malo ozemljitev simbol, z menoj. Ampak to samo pomeni, null, v tem primeru. Lahko ga izdela poljubno število načinov, vendar je ta avtor se je zgodilo, da uporabite ta simbol tukaj. 

Tako dolgo, dokler bomo zavezovanja vseh teh vozlišč skupaj, Samo spomnimo, kjer Prvi je, tako dolgo kot smo dali poseben simbol na Zelo zadnji vozel v seznamu, in bomo uporabili null, ker je to kar imamo na voljo, da nas, ta seznam je popolna. In tudi, če le ti dam kazalec na Prvi element, ti, programer, zagotovo lahko dostopate še ostalo. Vendar pa naj vaše misli sprehaja malo, če niso že precej wandered-- kaj bo čas teče najti ničesar na tem seznamu? Prekleto, to je velik O n, kar ni slabo, v pravičnosti. Vendar je linearna. Smo dali gor, kaj funkcija nizi, ki jih premika več k te slike dinamično tkani skupaj ali povezana vozlišča? Mi obupal naključni dostop. Niz je lepo, ker matematično vse je back to back to back to back. Čeprav te slike zgleda lepa, in še čeprav izgleda, da teh vozlišč so lepo razmaknjene, v resnici so lahko kjerkoli. OX1, Ox50, Ox123, Ox99, ti vozlišča je lahko kjerkoli. Ker malloc ne dodeliti pomnilnika iz kup, ampak kjerkoli na kup. Saj ni nujno, da veš, da je dogaja, da se vrnem nazaj na hrbet. In zato je ta slika v resnici je ne bo čisto ta lepa. 

Tako da bo trajalo nekaj prizadevala za izvajanje te funkcije. Torej, kaj je sedaj izvaja iskanje. In bomo videli, vrste pameten način za to. Torej, če sem funkcijo iskanja in Jaz sem dal spremenljivo, celo število n iskati, moram vedeti Nova skladnja za iskanje znotraj strukture, ki je poudaril, da bi našli n. Torej, kaj je to. 

Torej, najprej bom šel naprej in razglasi vozlišče *. In bom, da ga pokličete kazalec, samo po dogovoru. In bom inicializacijo najprej. In zdaj lahko to storite na številne načine. Ampak grem, da bi skupen pristop. Čeprav kazalec ni enaka null, in da je veljavna skladnja. In to samo pomeni, da naredite naslednje, da Dokler ti ne kaže na nič. Kaj hočem storiti? 

Če kazalec dot n, mi vrni tistemu, equals-- enaka kaj? Kakšno vrednost iščem? Dejanska n, ki je bil sprejet leta. Torej, tukaj je še ena značilnost o C in številnih jezikih. Čeprav strukture imenujemo vozlišča ima n vrednost, povsem legitimno da ima tudi lokalno argument ali spremenljivo imenuje n. Ker tudi mi z človeške oči, se lahko razlikuje da ta n je verjetno razlikuje od tega n. Ker sintaksa je drugačna. Imaš piko in kazalec, ker tole je nič takšnega. Torej je to v redu. To je v redu, da jih pokličete iste stvari. 

Če bi se vam zdi to, da sem dogaja, da želijo narediti nekaj podobno sporočamo, da smo našli n. In bomo pustite, da kot komentar ali psevdokoda kodo. Drugega, in tukaj je Zanimiv del tega, kar narediti, kar želim storiti, če trenutnim vozliščem ne vsebuje n, da me skrbi? Kako doseči naslednje? Če je moj prst na Trenutek je PTR, in to je kaže na karkoli Prva je gledala, kako premakniti prst na naslednje vozlišče v kodi? No, kaj je Orientacijska smo bo sledila v tem primeru? OBČINSTVO: [neslišno]. DAVID J. Malan: Ja, tako naprej. Torej, če se vrnem na moj Koda tukaj, res, da sem dogaja, da gredo naprej in reči kazalec, ki je le začasna variable-- je čudno ime, ptr, vendar to je tako kot temp-- Grem, da nastavite kazalec enako kakršni koli kazalec je-- in spet, to se bo malo buggy za moment-- piko naslednjo. Z drugimi besedami, bom vzamem prst, ki se kaže v tem vozlišču tu in bom rekel, veste, kaj, si oglejte naslednje polje in premaknite prst karkoli že je obrnjena. In to se dogaja, da ponavljam, ponavljam, ponavljanje. Ampak ko pa moj prst stop počne karkoli? Takoj, ko je kakšna vrstica kode brce v? OBČINSTVO: [neslišno] DAVID J. Malan: Če je točka, ko kazalec ni enaka null. Na neki točki Prst imam dogaja, da se kaže na null in bom za uresničitev da je konec tega seznama. Zdaj, to je malo bela laž zaradi enostavnosti. Izkazalo se je, da kljub temu, da Pravkar se naučili to dot zapis struktur, kazalec ni struct. ptr je kaj? Samo, da se bolj nitpicky. To je kazalec na vozlišče. To ni vozel sama. Če sem imel zvezdo tukaj, kazalec absolutely-- je vozlišče. To je kot en teden Deklaracija spremenljivke, čeprav beseda "vozlišče" je nova. 

Toda takoj, ko bomo uvedli zvezda, to je sedaj kazalec na vozlišče. In žal ne morete uporabljati dot zapis za kazalec. Boste morali uporabiti puščico zapis, ki je, presenetljivo, je prvič kateremkoli kos sintakse zgleda intuitivno. To dobesedno videti kot puščica. In tako, da je dobra stvar. In tukaj dobesedno Izgleda kot puščica. Zato mislim, da je la-- ne vem Mislim, da sem pretirano stori tu-- I mislim, da je to zadnja nov kos sintakse bomo videli. In na srečo, to je res Malo bolj intuitivno. 

Zdaj, za tiste, ki ste bi raje staro pot, lahko še vedno uporabljate dot zapis. Vendar pa je na ponedeljek-ih pogovor, smo najprej treba iti tja, pojdi na to obravnavo in dostop do zelenice. Torej, to je tudi pravilno. In odkrito povedano, to je malo bolj občutljiv. Ti si dobesedno rekel, dereference kazalec in tja. Potem zgrabi .N, polje se imenuje n. Vendar odkrito povedano, nihče ne želi tipkati ali brati. In tako svet izumil arrow zapis, ki je enaka, enaki, to je samo skladenjska sladkor. Tako fancy način rekel to izgleda bolje, ali pa je videti preprostejša. 

Torej, zdaj bom naredil še eno stvar. Bom rekel "odmor", ko imam ugotovila, da tudi jaz ne vodijo iskal. Toda to je bistvo za funkcijo iskanja. Ampak to je veliko lažje, v konec, da ne bo sprehod skozi kodo. To je dejansko formalno izvajanje iskanja v današnji distribucije kode. Upam si reči, da vložek ni še posebej zabavno, da sprehod skozi vizualno, niti izbrisati, čeprav čeprav na koncu dneva se omejijo na dokaj preprosti tolči. 

Torej, kaj je to. Če boste humor me tukaj sem prinašajo kup stresnih žogic. Prinesel sem kup številk. In bi lahko dobili le nekaj prostovoljcev da predstavljajo 9, 17, 20, 22, 29, in 34? Torej v bistvu vsak , ki je danes tu. To je ena, dva, tri, štiri, pet, šest ljudi. In sem prosil, da tam-- videli, no eden v hrbet postavlja svoje roke. OK, ena, dva, tri, štiri, five-- mi preračunavanja balance-- šest. OK, ti šest pridi gor. Potrebovali bomo tudi druge ljudi. Smo prinesli dodatne stresne žogice. In če bi lahko, za Samo trenutek, vrstica sami gor samo kot te slike tukaj. 

V redu. Poglejmo, kako ti je ime? 

OBČINSTVO: Andrew. 

DAVID J. Malan: Andrew, ste številka 9. Lepo, da sva se spoznala. Tukaj imaš. OBČINSTVO: Jen. DAVID J. Malan: Jen. David. Številka 17. Ja? 

OBČINSTVO: Jaz sem Julia. 

DAVID J. Malan: Julia, David. Številka 20. OBČINSTVO: Christian. DAVID J. Malan: Christian, David. Številka 22. In? 

OBČINSTVO: JP. DAVID J. Malan: JP. Številka 29. Torej, pojdi naprej in se noter-- Uh oh. Uh oh. Pripravljenosti. 20. Ima kdo marker? OBČINSTVO: Imam Sharpie. DAVID J. Malan: Imaš Sharpie? OK. In ali ima kdo kos papirja? Shranite predavanje. Daj no. OBČINSTVO: Smo jo dobili. DAVID J. Malan: Imamo ga? V redu, hvala. Gremo. Je bilo to pri vas? Pravkar ste rešili dan. Tako 29. V redu. Napačno sem 29, ampak OK. Pojdi naprej. Vredu, dam ti pero nazaj za trenutek. Torej imamo ti ljudje tukaj. Dajva še eno drugo. Gabe, hočeš igrati Prvi element tu? Vam bomo potrebovali točko V teh drobnih ljudi. Torej, 9, 17, 20, 22, sortiranje od 29, in nato 34. Ali smo izgubili nekoga? Imam 34. Kje did-- OK, kdo želi biti 34? OK, pridi gor, 34. V redu, to bo vredno vrhunec. Kako ti je ime? 

OBČINSTVO: Peter. 

DAVID J. Malan: Peter, pridi gor. Vse v redu, tako da tukaj je Cel kup vozlišč. Vsak od vas predstavlja eden od teh pravokotnikov. In Gabe, nekoliko nenavadno človek ven, predstavlja prvi. Torej je njegov kazalec je malo manjši na zaslonu, kot vsi ostali. In v tem primeru se vsak od vaš levi Roke se dogaja, da bodisi točko navzdol, kar predstavlja null, tako le odsotnost kazalcem, ali pa se dogaja, da se kaže na vozlišču poleg sebe. 

Torej, zdaj, če ga krasijo sami, kot na sliki Tukaj, pojdi naprej in točka drug na drugega, z Gabe zlasti kaže na številka 9, ki zastopa seznam. OK, in številko 34, levo roko Morala bi biti obrnjena v tla. 

OK, tako da je to povezano seznam. Torej je ta scenarij v vprašanju. In res, to je reprezentativna za razred problemov da lahko poskusite rešiti s kodo. Hočeš, da na koncu vstaviti nov element v seznamu. V tem primeru bomo poskusite vstaviti številko 55. Vendar pa se dogaja, da se različni primeri, da razmisli. In res, to se dogaja, da je eden od big-picture takeaways tukaj, je, kaj so različni primeri. Kakšne so drugačni, če pogoji, ali veje, ki lahko imajo vaš program? 

No, število, ki ga poskušate Vložek, ki je zdaj vemo, da je 55, ampak, če niste vedeli, vnaprej, upam si reči, spada v vsaj treh možne situacije. Kjer bi lahko nov element je? OBČINSTVO: In konec ali srednje. DAVID J. Malan: Na koncu, v srednji ali na začetku. Torej trdim, da je vsaj tri probleme moramo rešiti. Dajmo izbrati, kaj je mogoče verjetno najpreprostejši ena, kjer je novi element spada na začetku. Torej bom imel kodo precej kot je iskanje, ki sem napisal. In jaz bom imel ptr, ki Jaz bom tu predstavljajo s prstom, kot ponavadi. 

In zapomni si, kakšno vrednost smo inicializacijo ptr za? Zato smo ga inicializiran na začetku null. Ampak potem, kaj smo storili, ko smo so znotraj naše iskalno funkcijo? Mi je pa enaka prvi, ki ne pomeni to. Če sem iz PTR, ki je enaka prvi, kaj naj bi moja roka res gledala? Prav. Torej, če Gabe greva biti enake vrednosti tukaj moramo tako točko na številko 9. 

Tako da je bil to začetek naše zgodbe. In zdaj je to le preprosta, čeprav sintaksa je nova. Konceptualno je to samo linearno iskanje. Je enak 55 do 9? Ali pa, recimo, manj kot 9. Ker skušam ugotoviti, kje postaviti 55. Manj kot 9, manj kot 17 in manj kot 20, manjša od 22, manjša od 29, manj kot 34, št. Torej, zdaj smo v primeru eden od najmanj treh. 

Če želim vstaviti 55 nad tu, kaj vrstic kode potrebi se bodo izvajali? Kako to sliko ljudje morali spremeniti? Kaj naj naredim z mojo levo roko? To bi moralo biti null začetku, zato, ker sem na koncu seznama. In kaj naj bi se zgodilo tukaj s Petrom, je bilo to? Očitno mu je šlo, da kaže na mene. Torej trdim, da je vsaj dve vrstici kode v kodo vzorca in danes da bo za izvajanje tega Scenarij dodal 55 na repu. In lahko dobim nekoga hop in samo predstavljajo 55? V redu, vi ste nov 55. 

In kaj zdaj, če je naslednji Scenarij prihaja skupaj, in želimo, da vstavite na začnejo ali vodja tega seznama? In kako ti je ime, številka 55? 

OBČINSTVO: Jack. 

DAVID J. Malan: Jack? OK, lepo, da sva se spoznala. Dobrodošli na krovu. Torej, zdaj bomo vstavite, recimo, število 5. Tukaj je drugi primer trije smo prišli do prej. Torej, če 5 spada na začetku, Poglejmo, kako se to ugotovi. I inicializacijo moje ptr kazalec na številko 9 znova. In sem spoznal, oh, 5 je manj kot 9. Torej popraviti to sliko za nas. Katerih roke, Gabe ali David je ali-- kaj je številka 9 je ime? 

OBČINSTVO: Jen. 

DAVID J. Malan: Jen hands-- kateri od naših rokah morali spremeniti? OK, tako da Gabe opozarja na kaj pa zdaj? Vame. Sem nova vozlišča. Torej bom nekako premakniti tukaj videti vizualno. In medtem kaj moram poudariti, da je? Še vedno, ko sem obrnjena. Torej, to je to. Torej, samo res ena vrstica kode popravkov to posebno vprašanje, se zdi. V redu, to je dobro. In lahko nekdo ograda za 5? Pridi gor. Vam bom naslednjič. 

V redu, tako sedaj-- in Naj omenim, da imeni Jaz ne bi izrecno omenja pravice Zdaj, PRED kazalec, predhodnik pointer in nov kazalec, da je saj le imena v kodeksu vzorca na kazalcev ali moje roke, ki je nekako obrnjena naokoli. Kako ti je ime? 

OBČINSTVO: Christine. 

DAVID J. Malan: Christine. Dobrodošli na krovu. V redu, kaj menijo, da je sedaj nekoliko bolj siten scenarij, pri čemer želim vstaviti nekaj podobnega kot 26. v to. 20? Kaj? To si-- dobra stvar imamo to pisalo. V redu, 20. Če bi nekdo dobil en kos papir pripravljen, samo v case-- vse v redu. Oh, zanimivo. No to je primer predavanja hrošča. OK kaj je že ime? OBČINSTVO: Julia. DAVID J. Malan: Julia, se lahko pop ven in se pretvarjati, da si nikoli ni tam? OK, to se ni nikoli zgodilo. Hvala. Torej domnevam, želimo vstaviti Julia v tem povezanega seznama. Ona je številka 20. In seveda, da je dogaja, da sodijo v begin-- ne kažejo na kaj še. Torej tvoja roka lahko nekako biti navzdol null ali nekaj smeti vrednost. Povejmo hitro zgodbo. Jaz sem gledala številko 5 tokrat. Potem sem preveriti, 9. Potem sem preveriti 17. Potem sem preveriti 22. In se zavedam, ooh, Julia mora iti pred 22. Torej, kaj se mora zgoditi? Čigar roke je treba spremeniti? Julia, rudnik, ali-- kaj je že ime? 

OBČINSTVO: Christian. 

DAVID J. Malan: Christian ali? 

OBČINSTVO: Andy. 

DAVID J. Malan: Andy. Christian ali Andy? Andy je treba opozoriti na? Julia. V redu. Torej, Andy, hočeš opozoriti na Julia? Toda počakaj malo. V doslej zgodbe Jaz sem nekako ene zadolžen, v tem smislu, da kazalec je stvar, ki je premikanje po seznamu. Morda bomo imeli ime Andy, vendar ni spremenljivka se imenuje Andy. Edina druga spremenljivka imamo, je Prvi, ki je zastopal Gabe. 

Torej, to je pravzaprav, zakaj tako daleč smo ni to potrebno. Toda zdaj na zaslonu je omeniš of PRED kazalca. Torej, kaj mi je bolj jasno. Če je to kazalec, da je bolje, malo bolj inteligenten o mojem ponovitev. Če vas ne moti, moj gre tu skozi spet kaže tu, kaže tukaj. Ampak naj imajo PRED kazalec, Predhodnik kazalec, da je nekako kaže na element Ravnokar sem bil. Torej, ko sem šel tu, zdaj Moja leva posodobitve ročno. Ko sem šel tu moja leva posodobitve roko. In zdaj imam ne samo kazalec element, ki gre po Juliji, Še vedno imam kazalec Andy, element prej. Tako imate dostop, v bistvu, drobtine, če hočete, do vseh potrebnih kazalcev. 

Torej, če sem gledala Andy in jaz sem tudi obrnjena na krščanske, katere roke Sedaj je treba poudariti drugje? Torej, Andy lahko sedaj opozarjajo na Julijo. Julia zdaj lahko kazali na krščansko. Ker je mogoče kopirati moj Desna roka je kazalec. In da je dejansko vas postavi nazaj v ta kraj tu. Torej, na kratko, čeprav je to se nam pri tem nekako večno dejansko posodobiti povezani seznam, zavedati da poslovanje relativno enostavno. To je eden, dva, tri vrstic kode na koncu. Ampak ovije okrog tistih, vrstic kode predvidoma je malo logike, ki učinkovito zastavlja vprašanje, kje smo? Smo na začetku, srednji ali konec? 

Zdaj, gotovo obstajajo nekatere druge Operacije mi lahko izvajajo. In te slike tukaj samo opisujejo kaj sva naredila z ljudmi. Kaj pa odstranitev? Če želim, da, na primer, odstraniti številko 34 ali 55, Jaz bi imela enake kode, ampak bom potreboval enega ali dva koraka. Ker, kaj je novega? Če sem odstraniti nekoga na koncu, kot številko 55 in nato 34, kaj spremeniti tudi, kot sem to storil? Moram ne evict-- kaj je že ime? 

OBČINSTVO: Jack. 

DAVID J. Malan: Jack. Moram le evict-- brezplačno Jack, tako dobesedno pokličite brezplačno Jack, ali vsaj kazalec tam, ampak zdaj kaj je treba spremeniti s Petrom? Njegova roka je bolje začeti navzdol. Zato, ker takoj, ko sem poklical brezplačno Jack, če Peter je še vedno gledala Jack in zato vodi prečkajo seznam in dostop kazalec this, da je, ko naš stari prijatelj segmentacija Napaka bi lahko dejansko brcnil. Ker smo zaradi spomin nazaj k Jacku. 

Lahko ostaneš tam nerodno le za trenutek. Ker imamo le nekaj končni postopki, da razmisli. Odstranjevanje glav seznama, ali beginning-- in ta je malo siten. Ker moramo vedeti, da Gabe je nekako poseben v tem programu. Saj res, on ima svoj kazalec. On ni samo pa opozoril na, kot je že skoraj vsi ostali tukaj. 

Torej, ko je glava seznama odstraniti, katerih roke je treba zdaj spremeniti? Kaj je že ime? 

OBČINSTVO: Christine. 

DAVID J. Malan: Jaz sem grozna na imena, očitno. Torej, Christine in Gabe, čigar roke je treba spremeniti ko smo poskušali odstraniti Christine, številka 5, iz slike? OK, tako da naredimo Gabe. Gabe se dogaja s točko, domnevno, na številki 9. Toda kaj naj bi se zgodilo naslednjič? OBČINSTVO: Christine smeli je ničen [neslišno]. DAVID J. Malan: OK, če bi mi verjetno make-- sem slišal "null" nekje. OBČINSTVO: Null in brez nje. DAVID J. Malan: NULL kaj? OBČINSTVO: Null in brez nje. DAVID J. Malan: Null in brez nje. Torej, to je zelo enostavno. In je kot nalašč, da si zdaj nekako ki stoji tam, ne pripada. Zato, ker ste bili ločena od seznama. Učinkovito ste bili sirota iz seznama. In tako smo poklicali brezplačno zdaj Christine, da bi ta spomin nazaj. V nasprotnem primeru vsakič, ko odstrani vozlišče iz seznama bomo lahko izdelavo seznama krajši, vendar dejansko ne zmanjšuje velikost v pomnilniku. In tako, če se držimo dodajanje in dodajanje, dodajanje stvari na seznamu, moj računalnik morda dobili počasnejši in počasneje in počasneje, ker sem zmanjkuje spomin, čeprav v resnici nisem uporabo Christine je bajta spomina več. 

Torej, na koncu pa se drugi scenariji, iz course-- odstranitev v sredini, odstranjevanje na koncu, kot smo videli. Ampak bolj zanimivo Zdaj je izziv bo natančno preuči kaj čas teče, je. Torej ne samo, da lahko obdržite vaše Lističe, če Gabe, vas ne bi motilo, dajanje vsi stres žogo. Najlepša hvala za naše povezani seznam prostovoljcev tukaj, če bi lahko. 

[APLAVZ] 

DAVID J. Malan: Dobro. Torej nekaj analitično vprašanja, nato pa, če sem lahko. Videli smo ta zapis pred, big O in omega, zgornje meje in spodnja meja za čas nekaj algoritem teče. Torej, kaj menijo, da samo nekaj vprašanj. 

One, in mi je rekel, pred tem, kaj je tek čas iskanja Seznam v smislu velikega O? Kaj je zgornja meja za vožnjo Čas iskanjem povezani seznam kot naši prostovoljci izvajajo tu? To je velik O n, linearna. Ker v najslabšem primeru, elementa, kot so 55, bomo lahko iskali morda kje Jack je bilo vse tako na koncu. In na žalost, za razliko od matrike ne moremo dobiti fancy tokrat. Čeprav so bile vse naše ljudi razporejene od majhnih elementov, 5, vse tja do večjega elementa 55, to je navadno dobra stvar. Ampak kaj to domnevo ne nam omogočajo, da naredim? OBČINSTVO: [neslišno] DAVID J. Malan: Ponovi? OBČINSTVO: Random dostop. DAVID J. Malan: Random dostop. In posledično to pomeni, da ne moremo več uporabljati šibek ničel intuicijo, in očitnost dvojiškem iskanje in razdeli in vladaj. Ker čeprav smo Ljudje bi očitno vidim, da so Andy ali Christian približno na sredini seznama, vemo le, da je, kot je Računalnik s posnemanjem s seznama od samega začetka. Tako da smo obupali, da naključni dostop. 

Tako velik O n zdaj je zgornja vezan na naše iskalno času. Kaj pa omega naše iskanje? Kaj je spodnja meja za iskanje za nekaj več na tem seznamu? OBČINSTVO: [neslišno] DAVID J. Malan: Ponovi? OBČINSTVO: One. DAVID J. Malan: One. Tako konstanten čas. V najboljšem primeru, Christine je dejansko na začetku seznama. In iščemo številka 5, tako da smo jo našli. Torej ni nič takega. Ampak ona ima, da je na začetek seznama v tem primeru. Kaj pa nekaj takega kot Delete? Kaj pa, če želite izbrisati element? Kaj je zgornja meja in spodnja meja o izbrisu nekaj iz povezane seznam? OBČINSTVO: [neslišno] DAVID J. Malan: Ponovi? OBČINSTVO: n. DAVID J. Malan: n res zgornja meja. Ker v najslabšem primeru bomo poskušali izbrisati Jack, kot smo pravkar storil. On je vse tako na koncu. Nas traja večno, ali n korakov, da bi ga našli. Tako, da je zgornja meja. To je linearna, seveda. In najboljši primer čas teče, ali spodnje meje v najboljšem primeru bi bil konstanten čas. Mogoče zato, ker smo poskušali izbrisati Christine, in smo samo srečo ona je na začetku. Počakajte malo. Gabe je tudi na začetku, in smo tudi imeli za posodobitev Gabe. Tako, da ni bil le en korak. Torej je res konstantna čas, v najboljšem primeru, odstraniti najmanjši element? To je, čeprav bi bilo morda dva, tri ali celo 100 vrstic kode, Če je enako število linije, ne v neki zanki, in neodvisna od velikosti seznama, absolutno. Brisanje elementa na začetek seznama tudi če imamo opraviti z Gabe, je še vedno čas konstantna. 

Torej, to se zdi, kot ogromen korak nazaj. In kaj zapravljanje časa če je, v enem tednu in teden zero smo imeli ne samo psevdokoda code ampak dejanska koda izvesti nekaj, kar je dnevnik baza n, ali se prijavite, ne, n, baza 2, v smislu svojega časa teče. Torej, zakaj bi vraga želimo začeti uporabo nekaj podobnega povezanega seznama? Ja. 

OBČINSTVO: Torej, lahko dodate elementi v matriki. DAVID J. Malan: Torej lahko dodate elemente matrike. In tudi to je tematsko. In bomo še videli to je to trade-off, kar je precej kot smo videli trade-off z zlivanjem. Mi bi res lahko pospeši iskanje in sortiranje, ne, če bomo porabili malo več prostora in imajo dodatno kos pomnilnika ali niz za urejanje z zlivanjem. Vendar smo porabili več prostor, vendar smo prihranili čas. V tem primeru smo obupal čas, vendar smo pridobivanje fleksibilnost, dinamičnost, če hočete, ki je nedvomno pozitivna lastnost. 

Mi smo tudi porabo prostora. V kakšnem smislu je povezano seznam dražji v prostorskem smislu, kot array? Kjer je dodaten prostor, ki prihaja iz? Ja? 

OBČINSTVO: [neslišno] kazalec. 

DAVID J. Malan: Ja, tudi kazalec. Torej je to minorly nadležno s tem, da ni več am I shranjevanje le int za zastopanje int. Jaz shranjevanje int in A kazalec, ki je prav tako 32 bitov. Tako da sem dobesedno podvojili Količina prostora je izbral. Torej, to je trade-off, vendar da je v primeru notr. Predvidevam, da niste shranjevanje int, ampak domnevam, vsaka od teh pravokotnikov ali vsak od teh ljudi je predstavlja beseda, angleška beseda, ki morda pet znakov, 10 znakov, morda celo več. Nato dodal le 32 več bitov morda manj velik posel. 

Kaj pa, če je vsak od učencev pri predstavitvi dobesedno študentske konstruktov, ki imajo imena in hiše in morda telefonske številke in Twitter ročaji in podobno. Torej vsa polja smo začeli Govorimo o drugi dan, mnogo manj velik posel kot naša vozlišča dobili bolj zanimivo in velika, da preživijo, eh, dodatna kazalec samo, da jih povezati. Ampak res, to je trade-off. In res, koda bolj zapletena, kot boste glej s posnemanjem s da posamezen primer. Toda kaj, če ne bi bilo nekateri sveti gral tukaj. Kaj pa, če ne bomo naredili korak nazaj, ampak ogromen korak naprej in izvajati podatkov Struktura po katerem mogoče najti elemente, kot so Jack ali Christine ali katere koli druge elemente v tem polju v pravem času konstantno? Iskanje je konstantna. Izbriši konstantna. Vstavi se konstantna. Vse te operacije so stalnica. Da bi naš sveti gral. In to je, če smo bo dvignil naslednjič. Se vidiva potem.