[Muziciranja] DAVID J. Malan: U redu. Ovo je CS50. Ovaj je tjedan pet nastavili, a mi imaju neke dobre vijesti i loše vijesti. Dakle, dobra vijest je da je CS50 pokreće ovaj petak. Ako želite da nam se pridružite, glavu na uobičajene URL ovdje. Čak i bolje vijesti, nema predavanja ovaj dolazak ponedjeljak 13.. Nešto manje boljim vijestima, kviz nula je sljedeće srijede. Više informacija može biti naći na ovom URL ovdje. I u narednih nekoliko dana ćemo se ispune praznine s obzirom na sobama da ćemo imati pridržana. Bolja vijest je da ću biti pregled Naravno širom Sjednica ovaj dolazak Ponedjeljak u večernjim satima. Pratite Naravno-a Web stranica za mjesto i detalje. Sekcije, iako je to odmor, također će se sastati kao dobro. Najbolja vijest, predavanje sljedeći petak. Dakle, to je tradicija smo ima, kao i po nastavnom planu. Samo-- to će biti nevjerojatna. Vidjet ćete stvari poput vremenske konstante strukture podataka i hash tablice i drveće i napad. A mi ćemo govoriti o problemima rođendan. Cijela hrpa stvari čeka sljedeći petak. U redu. Bilo kako bilo. Tako se prisjetiti da smo bili fokusirajući se na ovoj slici što je unutar naše memorije računala. Dakle, memorije ili RAM-a je mjesto gdje programi postoje dok ih izvodi. Ako dvaput kliknite Ikona pokrenuti neki program ili dvaput kliknite icon otvoriti neke datoteke, To je učitan s tvrdog pogon ili pogon čvrstog stanja u RAM, RAM, gdje živi sve dok se ne isključi, poklopac laptopa zatvara, ili izađite iz programa. 

Sada kada memorije, od koji vjerojatno imaju 1 gigabajt ovih dana, 2 gigabajta, ili čak i mnogo više, je uglavnom izložena za određenu programa U ovoj vrsti pravokutnim konceptualni model pri čemu imamo hrpu na dnu i hrpa drugih stvari na vrhu. Ono što je na samom vrhu vidjeli smo na ovoj slici prije, ali nikad nije govorio o je tzv teksta segment. Tekst segment je samo fancy način govoreći o nula i jedinica koje sastaviti svoj stvarni sastaviti program. 

Dakle, kada ste dvaput kliknite Microsoft Word na Mac ili PC, ili kada pokrenete točku slash Mario na Linux računalo na prozor terminala, su nule i one koji čine Riječ ili Mario se pohranjuju privremeno u vašem računalu RAM-u tzv Tekst Segment za određeni program. Ispod toga ide inicijaliziranu i nepokrenute podataka. To je stvar kao i globalnih varijabli, da nismo koriste mnogi, ali povremeno mi smo imala globalne varijable ili statički definirana žice koje Teško je kodirana riječi poput "zdravo" da se ne uzimaju u od korisnika da su hard-kodirane u svoj program. 

Sada, dolje na dnu smo imaju tzv stog. I stog, do sada, mi smo bili korištenjem za što vrste svrhe? Što se stog se koristi za? Da? 

Publika: funkcije. 

DAVID J. Malan: Za funkcija? U kojem smislu za funkcije? 

Publika: Kada pozvati funkciju, Argumenti se kopiraju na stog. 

DAVID J. Malan: Točno. Kada pozvati funkciju, njegova Argumenti se kopiraju na stog. Dakle, bilo je X ili Y-a ili-a ili B-a da ste u prolazu u funkciji su privremeno staviti na tzv Stack, kao jedan od Annenberg blagovaonici ladice, a također i stvari poput lokalnih varijabli. Ako vaš Foo funkcija ili da je swap Funkcija imaju lokalne varijable, kao temp, njih dvojica završiti na stog. Sada, nećemo govoriti previše o ih, ali ove varijable okruženja Na dnu smo vidjeli tijekom dana kada Bio sam futzing na tipkovnici jedan dan i ja počeo pristupu stvari kao argv 100 ili argv 1.000, Upravo elements-- zaboravim numbers--, ali da nisu trebale biti pozvane preko mene. Počeli smo vidjeti neke funky simboli na zaslonu. To su bili takozvani varijable okruženja kao i globalnih postavki za moju Program ili za moje računalo, a ne povezana s nedavnom bug koji smo razgovarali, Potres mozga, koji je bio mući dosta računala. 

Sada na kraju, u današnjem fokusu ćemo u konačnici će biti na hrpi. Ovo je još jedan komad memorije. A sve to iz temelja memorije je ista stvar. To je isti hardver. Mi smo samo vrsta liječenje različitih klastera bajtova za različite svrhe. Hrpa također će biti tamo gdje varijable i memorije da zatraže o operacijskom sustavu je privremeno pohranjena. 

No, tu je vrsta problema Ovdje, kao što je slika implicira. Mi smo na neki način ima dva brodovi sukobit. Jer kao što ste koristiti sve više i više stog, a kao što vidimo danas pa nadalje, kao što ste koristiti sve više i više gomila, sigurno loše stvari bi se moglo dogoditi. I doista, možemo izazvati da namjerno ili nenamjerno. Tako je prošle Cliffhanger Vrijeme je ovaj program, koja nije ispunila niti jednu funkcionalnu svrhe osim da pokaže Kako vas kao negativac zapravo može potrajati Prednost bugova u nečijem programu i preuzeti program ili čak cijeli računalni sustav ili poslužitelja. Dakle, samo na prvi pogled kratko, te primijetiti da su glavni na dnu uzima u zapovjednoj liniji argumenti, kao i po argv. I to je poziv funkcije f, u biti bezimeni funkcija zove f, a to je donošenje u argv [1]. 

Dakle, bez obzira riječ je korisnik upiše u redak nakon naziv ovog programa, i onda je to proizvoljna funkcija gore vrhu, F, uzima u nizu, AKA char *, kao što smo počeli razgovarati, i to samo naziva ga "bar." Ali mi ga mogli nazvati ništa. I onda izjavljuje, unutar F, niz znakova zove c-- 12 takvih likova. 

Sada, po priči mi je pripovijedao Trenutak prije, gdje je u memoriji je c, ili su one 12 znakova će završiti? Samo da bude jasno. Da? 

PUBLIKA: Na dimnjaku. 

DAVID J. Malan: Na dimnjaku. Dakle C je lokalna varijabla. Mi tražimo za 12 kao broj znakova ili 12 bajtova. Oni su idući u kraj gore na tzv stog. Sada napokon je ovo druga funkcija to je zapravo prilično korisna, ali mi stvarno nije sam se to mi sami, strncopy. To znači string primjerak, ali samo slova n, n znakova. Dakle, n likovi će biti kopiran iz bara u c. I koliko? Duljina trake. Dakle, drugim riječima, da je jedan redak, strncopy, ide za kopiranje učinkovito bar na c. 

Sada, samo da vrsta predvidjeti Pouka ove priče, ono što je potencijalno problematično ovdje? Iako smo provjerom duljine vodilice i to prolazi u strncopy, ono što je tvoj osjećaj govori što je Još uvijek slomljena o ovom programu? Da? 

PUBLIKA: Ne uključuje soba za nultu karaktera. DAVID J. Malan: Ne uključuje soba za nultu karaktera. Potencijalno, za razliku ranijih iskustava nemamo ni ima toliko toga što je plus 1 do smjestiti tu null karakter. No, to je čak i gore od toga. Što još su nam u nedostatku to učiniti? Da? 

PUBLIKA: [nečujan] DAVID J. Malan: Savršen. Mi smo naporno kodirana 12 prilično proizvoljno. To nije toliko problem, ali činjenica da nismo ni provjere da li Duljina trake je manji od 12, u kojem slučaju to će biti siguran da ga staviti u memoriju zove c da smo dodijeljeni. Doista, ako je bar je kao 20 znakova, ova funkcija Čini se da je kopiranje 20 znakova iz bara u C, čime se uzimanje najmanje 8 bajta da ne bi trebalo biti. To implicira ovdje. 

Tako je u kratkom, slomljena programa. Nije tako velika stvar. Možda ste dobili grešku segmentacije. Mi smo svi imali bugove u programima. Svi smo mogli imati bugova u programima upravo sada. No, ono što je dublji smisao? Pa, ovdje je zumirana-u verzija da slika sjećanja mog računala. Ovo je dno moje stog. I doista, na samom dnu je ono što je zove roditelj rutinu stog, fancy način kaže da je glavna. Tako da onaj tko zove funkcija f da pričamo o tome. Dakle, ovo je dno dimnjaka. Povratak adresa je nešto novo. On je uvijek bio tu, uvijek je bio na toj slici. Mi jednostavno nikada nije pozvao pozornost na njega. Zbog ispada način c radi je da kad se poziva funkcija drugoga Ne samo da argumente na koje Funkcija se guraju na dimnjaku, Ne samo da je funkcija lokalne varijable se guraju na dimnjaku, nešto što se zove povratna adresa također dobiva staviti na stog. Točnije, ako je glavni pozivi Foo, glavni je vlastitu adresu u memoriji, nešto vola, učinkovito dobiva staviti na stog tako da, kada se radi f njezina izvršenja zna gdje bi skočiti natrag u tekstu segmenta kako bi nastavili izvršenja. 

Dakle, ako smo ovdje konceptualno, U glavnom, onda f dobiva zove. Kako ž zna tko za kontrolu ruku natrag? Pa, ovaj mali Put kroz web lokaciju u crvenom ovdje, zove povratna adresa, to samo provjere, što je to povratna adresa? Oh, neka mi skočiti natrag u glavni ovdje. I to je malo od pojednostavljivanje, jer je nula i jedinica za glavni tehnički ovdje u tech segmentu. No, to je ideja. f Samo treba znati što na kojima je kontrola u konačnici ide natrag. 

No, način na koji računala odavno iznio stvari poput lokalnih varijabli i Argumenti je ovako. Tako je u vrhu ove slike u plava je stog okvir za devizama, tako da sve memorije koja f posebno je korištenjem. Dakle, u skladu s tim, primijetiti da bar je na ovoj slici. Bar je bio njezin argument. I mi smo tvrdili da argumenti za Funkcije se guraju na stog. I C, naravno, i na ovoj slici. 

I samo za znakovlja koje svrhe, primijetiti u gornjem lijevom kutu je ono što će biti C nosač 0 i onda malo dolje desno je C nosač 11. Dakle, drugim riječima, možete zamisliti da postoji mreža bajtova Postoji, od kojih je prva gore lijevo, od kojih je donja je posljednji od tih 12 bajtova. 

Ali sada pokušati premotavanje prema naprijed. Što će se dogoditi ako prođemo u nizu bar koji je duže od c? A ovdje se ne provjere da li to je doista duže od 12 godina. Koji dio ove slike će se se zamjenjuje bajtova 0, 1, 2, 3, točka točka točka, 11, i loše, 12, 13 do 19? Što će se dogoditi ovdje, ako zaključiti iz naručivanje da c nosač 0 se nalazi na vrhu i c nosač 11 je vrsta prema dolje da u pravu? Da? 

PUBLIKA: Pa, to se događa prebrišite char * bar. 

DAVID J. Malan: Da, to izgleda idete prebrisati char * bar. I još gore, ako pošaljete u jako dugo niz, možda čak i prepisati što? Adresa povratak. Koji opet, baš kao i Put kroz web lokaciju reći program gdje da se vrati kad f vrši se zove. 

Dakle, ono što negativci obično učiniti je da su naišli na programu koji su znatiželjni hoće li se iskoristiv, kolicima tako da on ili ona može poduzeti Prednost tog buga, uglavnom ne dobiju to pravo prvi put. Oni samo početi slati, primjerice, slučajni nizovi u svom programu, bilo na tipkovnici, ili iskreno oni vjerojatno napisati mali program da se samo automatski generirati žice, i početi lupati po svom programu slanje u mnogo različitih inputa na različitim dužinama. 

Čim je vaš program ruši, to je nevjerojatna stvar. Jer to znači da ili ona je otkrila što je vjerojatno istina bug. I onda oni mogu dobiti više pametan i početi s naglaskom uže o tome kako iskoristiti tu grešku. Konkretno, ono što on ili ona može učiniti je poslati, u najboljem slučaju, zdravo. Nije velika stvar. To je niz koji je dovoljno kratko. Ali što ako on ili ona šalje, , a mi ćemo ga generalizirati kako, Napad code-- tako nula i one koje to stvari kao što su rm-RF, da ukloni sve s tvrdog diska ili slanje spama ili nekako napasti stroj? 

Dakle, ako je svaki od tih slova samo predstavlja, Konceptualno, napad, napad, napad, napad, neke loše kod da je netko drugi napisao, ali ako ta osoba je dovoljno pametna ne samo da su sve od onih RM-RFS, ali i imaju svoje posljednjih nekoliko bajtova biti broj koji odgovara na adresu njegovog ili njezin vlastiti napad kod da je on ili ona prošla u samo tako da ga pružajući na brz, učinkovito možete prevariti računalo u primjećivati ​​kada ž obavlja izvršenje, Oh, da je vrijeme za mene da skočiti natrag na crvenom povratnu adresu. Ali, jer on ili ona ima nekako preklapanju tu povratnu adresu s vlastitim brojem, i oni su dovoljno pametni da je konfiguriran da broj se odnosi, kao i vi pogledajte u super vrhu lijevom kutu postoji, stvarna adresa na računalu Sjećanje na neke od njihovih napada koda, negativac može izigrati računalo u izvršavanju svoj vlastiti kod. 

I to kod, opet, može biti bilo što. To je obično zove Shell kod države, što je samo način da se kaže da to nije općenito nešto tako jednostavno kao rm-RF. To je zapravo nešto poput Bash, ili stvarni program koji ga daje ili njezina programska kontrola izvršiti sve ostalo što oni žele. Dakle, ukratko, sve ovo proizlazi iz jednostavne činjenice da je ovaj bug koji su uključeni ne provjere granice vaše polje. I zato putu Računala rade je da oni koristiti papire iz učinkovito, konceptualno, Dno na gore, ali onda su elementi vas gurnuti na stog raste odozgo prema dolje, ovo je nevjerojatno problematično. Sada, postoje načini da se zaobišli. I iskreno, postoje jezici s kojima bi zaobišli ovo. Java je imun, primjerice, na ovom pitanju. Jer oni ne vam dati naputke. Oni ne daju vam izravne memorije adrese. Dakle, s ovom moći koju imamo kako bi dirali u memoriji Želimo u pitanju, doduše, veliki rizik. 

Dakle pripaze. Ako je, iskreno, u mjesecima ili godine koje dolaze, u bilo koje vrijeme čitate o nekim eksploatacije programa ili poslužitelja, Ako ste ikada vidjeli nagovještaj nečega kao buffer overflow napada, ili Stack Overflow je drugi tip napada, slični u duhu, koliko nadahnjuje web-a ime, ako ga znate, to sve govori o samo prepun veličinu nekog lika Niz ili neki niz općenito. Bilo kakva pitanja, dakle, o tome? Ne pokušavajte ovo kod kuće. 

U redu. Dakle malloc do sada je naša nova Prijatelj u koje možemo dodijeliti memoriju da ne mora nužno znati u unaprijed da želimo, tako da nemamo na tvrdom koda u naše Program brojevi poput 12. Nakon što nam govori koliko je korisnika Podaci on ili ona želi da se ulaz, možemo malloc toliko memorije. 

Dakle malloc ispada, da Koliko smo ga koriste, izričito posljednji put, a zatim ti dečki su ga pomoću za getstring znajući za nekoliko tjedana, svi malloc memoriju dolazi iz tzv hrpi. I to je razlog zašto getstring, primjerice, može alocirati memoriju dinamički ne znajući što ste će se upisati unaprijed, uručiti vam vratiti kazaljke na tu memoriju, i da je memorija je još uvijek tvoje zadržati, čak i nakon getstring vraća. Budući da podsjetimo, nakon svega što stog stalno ide gore i dolje, gore i dolje. I čim to ide prema dolje, to znači da je bilo memorije Ova funkcija koristi trebale ne može koristiti nitko drugi. To je vrijednosti za smeće sada. 

No hrpa je ovdje gore. A ono što je lijepo o malloc je da kada malloc alocira memoriju ovdje, to nije utjecalo, za Najveći dio, po dimnjaku. I tako je bilo funkcija može pristupiti memorije koja je malloc'd, čak i funkcije kao što getstring, čak i nakon što se vratio. 

Sada, obrnuto od malloc je slobodan. I doista, ti pravilo trebaju početi s usvajanjem je bilo, bilo, svaki put kad koristite malloc moraš se koristiti besplatno, na kraju, na toj istoj karti. Sve ovo vrijeme bili smo pisanje lud, lud koda, iz više razloga. No, jedna od kojih je bila pomoću CS50 knjižnicu, koja Sama je namjerno buggy, curi memorije. Svaki put kada sam zvao getstring tijekom posljednjih nekoliko tjedana tražimo pogonski sustav, Linux, za memoriju. A ti nikada jednom ga dobiti natrag. I to nije, u praksa, dobra stvar. 

I Valgrind, jedan od alata uveo u pset 4, je sve o tome ćemo vam pomoći Sada pronaći greške kao što je to. No, srećom za pset 4 ne morate upotrijebite CS50 knjižnicu ili getstring. Dakle, sve bugove vezane za memoriju su u konačnici će biti sami. 

Dakle malloc je više nego samo pogodan za ovu svrhu. Mi zapravo sada može riješiti bitno različiti problemi, i temeljno rješavanje problema više učinkovito kao tjedno Zero obećanja. Do sada je ovo najseksi struktura podataka što smo imali. I po strukturi podataka sam samo znači način gledanja memorije na način koji nadilazi samo govoreći, ovo je int, ovo je char. Možemo početi klastera stvari zajedno. 

Tako niz izgledao ovako. I ono što je ključno u oko Niz je da vam daje back-to-back komadi memorija, od kojih svaka će biti istog tipa, int, int, int, int ili char, char, char, char. No, postoji nekoliko nedostataka. To, na primjer, nalazi Niz veličine šest. Recimo da ispunite ovaj niz sa šest brojevi i onda, iz bilo kojeg razloga, Vaš korisnički želi dati što sedamtine broj. Gdje ste ga stavili? 

Što je rješenje ako imate stvorio niz na dimnjaku, Na primjer, samo u tjednu dvije oznake koje smo uveli, od uglate zagrade s brojnim unutarnjim? Pa, imaš šest Brojevi u tim okvirima. Što bi vaši instinkti biti? Gdje bi htjela da ga stavi? 

PUBLIKA: [nečujan] 

DAVID J. Malan: Molim? 

PUBLIKA: Stavite ga na kraju. 

DAVID J. Malan: Stavite ga na kraju. Dakle, nešto više udesno, izvan tog okvira. Koji bi bilo lijepo, ali to Ispada da ne može to učiniti. Jer ako ne ste pitali za ovaj komad memorije, to bi moglo biti slučajno da to se koristi od strane neke druge varijable uopce. Sjetite se tjedan dana, kada smo položili iz Zamyla and Davin and Gabe imenima u memoriji. Oni su doslovno natrag na leđa na leđa. Dakle, ne možemo nužno vjeruju da sve što je ovamo je dostupan za mene koristiti. 

Pa što još možda ćete učiniti? Pa, nakon što shvaćajući potreban niz veličine sedam, ti samo mogao stvoriti Niz veličine sedam zatim pomoću za petlje ili while petlji ga kopirati u novi niz, a onda nekako samo riješiti to polje ili samo prestati koristiti. Ali to nije posebno učinkovita. Ukratko, nizovi ne dopustite dinamički mijenjati veličinu. 

Dakle, s jedne strane, te dobiti izravnim pristupom, što je nevjerojatna. Zato što nam omogućuje da radimo stvari kao i podijeli pa vladaj, binarno traženje, a svi mi smo govorio o na zaslonu ovdje. No, što se bojite u kut. Čim hit kraj tvoje polje, što morate učiniti vrlo skupa operacija ili napisati cijela hrpa koda do sada nositi s tim problemom. 

Pa što ako umjesto smo imali nešto što se zove popis, ili povezani popis posebno? Što ako, umjesto da pravokutnici natrag na leđa na leđa, imamo pravokutnike koje ostavljaju malo malo wiggle room između njih? I iako sam nacrtana ova slika ili prilagoditi ovu sliku iz jednog od tekstova ovdje da će se vratiti na natrag na leđa vrlo uredan, u stvarnosti, jedan od tih pravokutnika mogao biti ovdje u memoriji. Jedan od njih mogao biti ovdje. Jedan od njih mogao biti ovdje, ovamo, i tako dalje. 

No, što ako mi je nacrtao, u ovom slučaju, strelice da nekako povezati to pravokutnici zajedno? Doista, vidjeli smo tehnički inkarnacija strelicom. Što smo korišten u novijim dana da, ispod haube, prikazuje strelicom? Pokazivač, zar ne? 

Pa što ako se, umjesto da Upravo spremanje brojeva, poput 9, 17, 22, 26, 34, što ako mi se ne pohranjuju samo broj, ali se kazaljka uz svaki takav broj? Tako da je slično kao što bi konac iglu kroz cijela hrpa tkanine, nekako vezanje stvari zajedno, na sličan način mogu smo s pokazivača, što utjelovio strelicama ovdje, vrsta tkati zajedno ti pojedinačni pravokutnici učinkovito korištenje pokazivač pored svakog broja koji ukazuje na neki sljedeći broj, koji ukazuje na, pak neki Iduća? Dakle, drugim riječima, ono što ako mi zapravo htjeli provesti nešto ovako? Pa nažalost, ti pravokutnici, Barem je jedan s 9, 17, 22, i tako dalje, te se više ne lijepi trgovi s pojedinačnim brojevima. Dno, pravokutnik ispod 9, na primjer, predstavlja ono što bi trebala pointer, 32 bita. Sada, ja sam još uvijek nije svjestan bilo koje vrste podataka u C koji vam daje ne samo int ali kazaljka uopce. 

Dakle, ono što je rješenje ako želimo izmisliti vlastiti odgovor na ovo? Da? 

PUBLIKA: [nečujan] 

DAVID J. Malan: Što je to? 

PUBLIKA: Nova struktura. 

DAVID J. Malan: Da, pa zašto ne bismo stvorili novu strukturu, ili C, a STRUCT? Vidjeli smo tvorevina i prije, ako je kratko, gdje smo se bavili sa studentskom strukture kao što je ovaj, koji je imao ime i kuću. U pset 3 Bijeg ste koristili cijeli Hrpa structs-- GRect i GOvals da Stanford stvorio se Klaster informacije zajedno. Pa što ako uzmemo tu istu ideju ključne riječi "typedef" i "struct", i onda neki student-specifične stvari, i razvijati to u sljedeće: typedef struct node-- i čvor samo vrlo općenito računalnih znanosti Izraz za nešto u strukture podataka, Spremnik u strukturu podataka. Čvor Tvrdim će imati int n, sasvim jednostavan, i onda malo više skriveno, Ova druga linija, struct čvor * sljedeći. No, u manjim tehničkim uvjetima, što je to druga linija koda unutar vitičastih zagrada? Da? 

PUBLIKA: [nečujan] DAVID J. Malan: pokazivač na drugi čvor. Dakle, doduše, sintaksa pomalo zagonetan. Ali ako ga se uzima doslovno, Sljedeći je ime varijable. Koji je njegov tip podataka? To je malo preopširan ovaj put, ali to je tipa struct čvor *. Svaki put kad smo vidjeli nešto zvijezdu, koja znači da je kazaljka na tu vrstu podataka. Dakle, sljedeći je očito pointer na struct čvor. 

Sada, ono što je struct čvor? Pa, primijetit ćete vidjeti one Iste riječi u gornjem desnom kutu. I doista, što se također vidi riječ "Čvor" ovdje u donjem lijevom kutu. A to je zapravo samo praktičnost. Uočite da u našem studentskom definiciji Tu je riječ "učenik" samo jednom. A to je zato što je student Cilj nije bio samo-referencijalni. Nema ništa unutar student da treba ukazati na drugog učenika, persay. To bi bila neka vrsta čudno u stvarnom svijetu. 

No, s čvora u povezana Popis, mi želimo čvor da bude referentna na sličan objekt. I tako primijetiti promjene ovdje nije samo ono što je unutar vitičastih zagrada. Ali smo dodali riječ "čvor" na vrhu, kao i dodavanjem na dnu u zamjenu za "student". A to je samo tehnički detalji tako da, opet, tvoja struktura podataka može biti samo-referencijalni, tako da čvor može ukazati na neki drugi takav čvor. 

Pa što je to u konačnici će značiti za nas? Pa, jedan, ove stvari unutar je sadržaj naše čvor. To je stvar ovdje, gore desno, samo tako da, opet, možemo se odnose na sebe. A onda najudaljeniji stvari, iako čvor je novi pojam, možda, to je još uvijek Isto kao student i što bio je ispod haube u SPL. 

Dakle, ako mi sada htjeli početi provedbe ovog popisa povezane, Kako bismo mogli prevesti nešto ovako to kod? Pa, pogledajmo Primjer programa koji zapravo koristi popis povezane. Među današnjem distribucije koda je program pod nazivom Lista Zero. A ako sam pokrenuti ovaj sam stvorio super Jednostavan GUI, grafičko korisničko sučelje, ali to je stvarno samo printf. I sada sam sebi dao nekoliko izbornik options-- Delete, Insert, pretrage, i poprijeko. I Quit. To su samo zajedničke operacije na struktura podataka poznat kao popisa linkova. 

Sada, Delete će Brisanje broja iz popisa. Umetnite će dodati broj na popisu. Pretraživanje će izgledati za broj na popisu. I poprijeko je samo fancy način govoreći, prošetati kroz popis, print it out, ali to je to. Nemojte ga mijenjati na bilo koji način. 

Tako ćemo probati ovo. Idemo naprijed i tip 2. A onda ću umetnuti broj, kažu 9. Unesite. A sada moj program je samo programirani da kažu, popis je sada 9. Sada, ako sam ići naprijed i Uložite li opet, neka mi ići naprijed i smanjivanje i upisati 17. Sada je moj popis je 9, a zatim 17. Ako ja umetnuti opet, ajmo preskočiti jedan. Umjesto 22, kao i po slici mi smo je gledao ovdje, neka mi skok naprijed i umetnite 26 naprijed. Tako da ću upisati 26. Popis je što ja očekujem. Ali sada, samo da vidi je li ovaj kod će biti fleksibilan, neka me sada tipa 22, koji je barem konceptualno, ako smo Imajući to riješeno, što je doista će biti još jedan cilj upravo sada, trebao ići u između 17 i 26 godina. Tako sam udario Enter. Doista, koji radi. I tako sada neka mi umetnite Posljednji, po slici, 34. 

U redu. Dakle, za sada neka mi odrediti da Brisanje i Traverse i pretrage napraviti, u stvari, radi. U stvari, ako ja ne odvijaju Search, ajmo potražite na broju 22, Enter. Utvrdio 22. Dakle, to je ono što ova Program Lista Zero radi. 

Ali što se zapravo događa na koji implementira ovo? Pa, prvo bih mogao imati, i doista Ja nemam, datoteka pod nazivom list0.h. A negdje tamo je to linije, typedef, struct čvor, onda ja imam svoje vitičastim zagradama, int n, i onda struct-- što je definicija? Struct čvor naprijed. Dakle, trebamo zvijezdu. Sada tehnički smo dobili u navika crtež ovdje. Možda ćete vidjeti udžbenike i online reference to učiniti tamo. To je funkcionalno ekvivalentni. U stvari, to je malo više tipičan. Ali ja ću biti u skladu s onim što smo učinili prošli put i to učiniti. I onda na kraju, ja ću to učiniti. 

Dakle, u zaglavlju datoteke Negdje, u list0.h Danas je ova definicija struct, a možda i neke druge stvari. U međuvremenu je u list0c postoji će biti nekoliko stvari. Ali ćemo samo početak, a ne završiti ovo. List0.h je datoteka želim uključiti u mom C datoteci. A onda u nekom trenutku sam će imati int, glavni, poništiti. A onda ću imaju neke to-do ovdje. Ja sam također će imati Prototip, kao praznina, pretraživanje, int, n, čija je svrha u životu je u potrazi za element. I onda ovdje tvrdim u današnji broj, nevažeće, pretraživanje, int n, nema zarez, ali otvorene vitičastim zagradama. A sada želim na neki način traži za element u ovom popisu. Ali nemamo dovoljno Informacije na zaslonu još. Nisam zapravo predstavljao samu popis. Tako je jedan način na koji smo mogli ostvariti Popis povezani u programu je nekako želite učiniti nešto kao proglasiti povezani popis ovdje. Radi jednostavnosti, ja ću napraviti Ovaj globalni, iako općenito mi Ne treba to učiniti previše. No, to će pojednostaviti ovaj primjer. Dakle, želim izjaviti Popis povezano ovdje. Sada, kako bih mogao to učiniti? 

Evo slika popisu povezane. A ja stvarno ne znati u ovom trenutku koliko Ja ću ići oko zastupanje toliko mnogo stvari samo s jednim varijabla u sjećanju. Ali mislim vratiti trenutak. Sve ovo vrijeme koje smo imali žice, koje smo tada otkrila je da su nizovi likovi, koje smo tada otkrila je da samo biti pokazivač na prvi znak u niz znakova da null je prekinut. Dakle, po toj logici, i uz to Slika vrsta sijanje svoje misli, Što nam zapravo pisati u našim Kod za zastupanje popis povezana? Koliko od ovih informacija ne trebamo uhvatiti u C kodu, biste rekli? Da? 

PUBLIKA: Trebamo pokazivač na čvor. DAVID J. Malan: pointer na čvoru. Konkretno, što bi čvor CTR instinkti će zadržati pokazivač? 

PUBLIKA: Prvi čvor. 

DAVID J. Malan: Da, Vjerojatno je samo prva. I primijetiti, prvi Čvor je različit oblik. To je samo pola veličine STRUCT, jer to je doista samo pokazivač. Dakle, ono što se doista može učiniti jest proglasiti Popis povezan s biti tipa čvora *. I neka je samo to prvi poziv i inicijalizirati ga na nulu. Dakle null, opet, dolazi u sliku ovdje. Ne samo da se koristi kao nula kao poseban Povratak vrijednost za stvari kao što su getstring i malloc, nulta je i nula pokazivač, nedostatak pokazivač, ako hoćete. To samo znači da se ništa još ovdje. Sada prvi put, mogao sam nazvao to ništa. Mogao sam ga nazvao "Popis" ili bilo koji od drugih stvari. Ali ja zovem ga "prvi", tako da IT linije s tom slikom. Dakle, baš kao i niza može biti zastupljena s adresom u svom prvom bajtu, tako da mogu Popis povezani. A vidjet ćemo i druge podatke strukture biti predstavljeni sa samo jednim pokazivačem 32-bitni strelica, pokazujući na prvi čvor u strukturi. 

Ali sada idemo predvidjeti problem. Ako sam samo sjećanja u mom programu adrese prvog čvora, prvi pravokutnik u ovoj strukturi podataka, ono što je bolje biti slučaj o Provedba ostatka mom popisu? Što je ključan detalj koji se događa kako bi se osiguralo to zapravo radi? I tako "zapravo radi" sam znači, baš kao i niza, omogućuje nam ide od prvog karaktera u Davin ime na sekundu, za trećinu, na Četvrto, do samog kraja, Kako možemo znati kada smo na kraju od popisa povezan koja izgleda ovako? Kada je nula. I ja sam zastupao ovu vrstu kao kao inženjer elektrotehnike snagom, s malo uzemljenje Simbol, od sorti. No, to samo znači nula u ovom slučaju. Vi ga možete izvući bilo koji broj načina, ali ovaj autor dogodilo da koriste ovaj simbol ovdje. 

Tako dugo dok mi nizanje sve od tih čvorova zajedno samo sjećanja gdje Prvi je, tako dugo kao što smo stavili poseban simbol na posljednji čvor na popisu, a mi ćemo koristiti null, jer to je ono što imamo na raspolaganju nama, ovaj popis završi. A čak i ako je samo dajem vam kazaljke na Prvi element, što, programer, svakako može pristupiti ostatak njemu. Ali neka neka vaš um lutati malo, ako oni nisu već dosta wandered-- što je će biti vrijeme rada pronalaženje ništa u tom popisu? Kvragu, to je veliki O n, što nije loše, u pravednosti. Ali, to je linearan. Mi smo odustali od onoga što je značajka matrica pomicanjem više prema ovoj slici dinamički tkani zajedno ili povezani čvorovi? Odustali smo slučajni pristup. Niz je lijepo, jer matematički je sve je natrag na leđa na leđa uz leđa. Iako ove slike izgleda lijepo, pa čak i iako to izgleda tih čvorova lijepo razmaknute, u stvarnosti bi mogli biti bilo gdje. Ox1, Ox50, Ox123, Ox99, to čvorovi mogu biti bilo gdje. Zbog malloc ne dodijeliti memoriju iz hrpe, ali nigdje u hrpi. Ne nužno znati da je će se vratiti natrag na leđa. I tako je ta slika u realnosti ne će biti dosta ova lijepa. 

Dakle, to će potrajati malo raditi za provedbu ove funkcije. Tako ćemo provesti pretragu. I vidjet ćemo kakve pametan način za to. Dakle, ako sam tražilici i Ja sam dao varijablu, broj N tražiti, moram znati Novi sintaksa za gleda unutar strukture koja je ukazao na, kako bi pronašli n. Tako ćemo to učiniti. 

Dakle, prvo ću otići naprijed i proglasiti čvor *. A ja ću ga nazvati pointer, samo po konvenciji. A ja ću ga inicijalizirati na prvom mjestu. I sad ja to mogu na više načina. Ali ja ću se zajednički pristup. Dok se kazaljka nije jednako null, a to je valjan sintakse. I to samo znači učiniti sljedeće, pa Sve dok niste usmjerene prema ničemu. Što želim učiniti? 

Ako se kazaljka točka n, dopustite mi da se vratim da da, equals-- jednako što? Ono vrijednost tražim? Stvarni n koji je donesen u. Dakle, ovdje je još jedna značajka od C i mnoge jezike. Iako se struktura naziva čvora ima vrijednost n, potpuno legitiman da imaju lokalnu argument ili promjenjiva zove n. Zato i mi, s ljudske oči, može razlikovati da je ovaj n vjerojatno razlikuje od ove n. Zato sintaksa je drugačija. Imaš točku i pokazivač, dok je ovaj jedan nema takvu stvar. Dakle, to je u redu. To je u redu da ih zovu iste stvari. 

Ako sam ti naći to, ja sam će htjeti nešto učiniti kao što je objaviti da smo pronašli n. A mi ćemo ostaviti da se kao komentirati ili pseudocode koda. Inače, i ovdje je Zanimljiv dio, što želim učiniti ako trenutnog čvora ne sadrži n da mi je stalo? Kako bi se postigla sljedeće? Ako moj prst na Trenutak je PTR, a to je pokazujući na ono što Prva je ukazujući na, Kako sam premjestiti moj prst na sljedeći čvor u kodu? Pa, ono što je kroz web lokaciju smo će slijediti u ovom slučaju? PUBLIKA: [nečujan]. DAVID J. Malan: Da, tako naprijed. Dakle, ako sam se vratiti u svoj Kod ovdje, dapače, ja sam ići dalje i reći pokazivač, koji je samo privremena variable-- je čudno ime, PTR, ali to je isto kao temp-- Ja ću postaviti pokazivač jednaka bez obzira na kazaljke je-- i opet, to će biti malo lud za moment-- točka uz. Drugim riječima, ja ću uzeti moj prst koji je pokazujući na tom čvoru ovdje, a ja ću reći, znaš ono, pogledajte na sljedećem polju i pomaknite prst na bez obzira na to je pokazujući na. A to će se Ponavljam, ponavljam, ponoviti. No, kada se moj prst prestati raditi bilo što? Čim ono linija koda udaraca u? PUBLIKA: [nečujan] DAVID J. Malan: Ako je točka, a Pokazivač nije jednak nuli. U jednom trenutku mi je prst-ih će biti pokazujući na null i ja ću ostvariti to je kraj ovog popisa. Sada, to je malo bijela laž zbog jednostavnosti. Ispada da, iako smo upravo naučili ovu dot zapis za konstrukcije, kazaljka nije struct. PTR je što? Samo da se više nitpicky. To je pointer na čvoru. To nije samo po sebi čvor. Ako sam imao zvijezdu ovdje, pokazivač absolutely-- je čvor. To je kao jedan tjedan izjava o varijabli, iako riječ "čvor" je nova. 

No, čim smo uvesti zvijezda, to je sada pokazivač na čvor. I na žalost, ne možete koristiti dot zapis za pokazivača. Morate koristiti strelicu zapis, koji je, nevjerojatno, je prvi put bilo koji komad sintakse izgleda intuitivno. To je doslovno izgleda kao strijela. I to je dobra stvar. I ovdje je doslovno Izgleda poput strijele. Dakle, mislim da je la-- ne znam Mislim da sam više-počinjenje ovdje-- sam mislim da je to zadnji put novi komad sintakse ćemo vidjeti. I srećom, to je doista malo više intuitivno. 

Sada, za one od vas koji možda radije na stari način, još uvijek možete koristiti dot zapis. No, kao i po u ponedjeljak razgovor, prvo treba ići tamo, idite na to adresu, a zatim pristupiti polje. Dakle, to je također točno. I iskreno, ovo je Malo više pedantan. Vi ste doslovno govoreći, dereference pokazivač i otići tamo. Zatim uzmite .n, polje zove n. Ali, iskreno, nitko ne želi upisati ili pročitati. I tako je svijet izmislio strelica zapis, koji se je ekvivalent, identična, to je samo sintaktička šećera. Dakle fancy način govoreći to izgleda bolje, ili izgleda jednostavnije. 

Dakle, sad ću napraviti jednu drugu stvar. Ja ću reći "break", jednom sam pronašao je tako da ne bi u potrazi za njega. No, to je suština od funkciju pretraživanja. No, to je puno lakše, u kraj, a ne šetati koda. To je doista formalna provedba potrage u današnjem distribucije koda. Usuđujem se reći da umetak nije Posebno je zabavno šetati vizualno, niti izbrisati, čak i da je na kraju dan oni svode se na relativno jednostavna heuristika. 

Tako ćemo to učiniti. Ako ćete humora me ovdje, jesam donijeti hrpu stresa lopti. Donio sam hrpu brojeva. A mogli smo dobiti samo nekoliko volontera predstavljaju 9, 17, 20, 22, 29 i 34? Dakle, u biti svatko tko je ovdje danas. To je bio jedan, dva, tri, četiri, pet, šest ljudi. I ja sam bio zamoljen da go-- vidjeti, nema jedan u leđima podiže svoje ruke. OK, jedan, dva, tri, četiri, five-- neka mi učitati balance-- šest. OK, šest dođi. Trebamo druge ljude. Donijeli smo dodatni stres loptice. A ako bi, za Samo trenutak, linija i sami se samo poput ove slike ovdje. 

U redu. Da vidimo, kako se ti zoveš? 

PUBLIKA: Andrew. 

DAVID J. Malan: Andrija, ti si broj 9. Drago mi je. Izvoli. PUBLIKA: Jen. DAVID J. Malan: Jen. David. Broj 17. Da? 

PUBLIKA: Ja sam Julia. 

DAVID J. Malan: Julia, David. Broj 20. PUBLIKA: Christian. DAVID J. Malan: Christian David. Broj 22. I? 

PUBLIKA: JP. DAVID J. Malan: JP. Broj 29. Dakle, ići naprijed i dobiti in-- Uh. Uh. Stanje pripravnosti. 20. Ima li tko marker? PUBLIKA: Imam Sharpie. DAVID J. Malan: Imaš Sharpie? U redu. I bilo tko imati komad papira? Spremite predavanje. Hajde. PUBLIKA: Mi smo ga dobili. DAVID J. Malan: Uspjeli smo? U redu, hvala na pitanju. Ovdje ćemo ići. Je li ovo od vas? Upravo si spasio dan. Tako 29. U redu. Pogrešno sam 29, ali u redu. Samo naprijed. U redu, ja ću vam dati vaša olovka natrag na trenutak. Dakle, imamo ove ljude ovdje. Idemo na jedan drugi. Gabe, hoćeš igrati Prvi element ovdje? Mi ćemo vam treba istaknuti kod tih sitnih ljudi. Dakle, 9, 17, 20, 22, svojevrsni od 29, a zatim 34. Jesmo li izgubili nekoga? Imam 34. Gdje mu treba redu, tko želi biti 34? U redu, dođi, 34. U redu, to će biti dobro vrijedi vrhunac. Koje je tvoje ime? 

PUBLIKA: Petar. 

DAVID J. Malan: Petar, dođi gore. U redu, pa evo cijela hrpa čvorova. Svaki od vas predstavlja jedan od tih pravokutnika. I Gabe, pomalo čudno čovjek iz, predstavlja prvi. Tako je njegov pokazivač je malo manji Na zaslonu se od svih ostalih. I u ovom slučaju, svaki od vaše lijeve strane Ruke će bilo ukazati dolje, čime predstavlja null, tako Upravo nepostojanje pokazivača, ili će to biti okrenuta na čvoru pored vas. 

Dakle, upravo sada, ako ste krasiti sebe kao na slici ovdje, ići naprijed i točka jedni na druge, s Gabea posebice pokazujući na broj 9 za zastupanje popis. U redu, i broj 34, lijevu ruku samo treba biti okrenuta prema podu. 

U redu, tako da je ovo popis povezani. Dakle, ovo je scenarij u pitanju. I doista, to je predstavnik klase problema da možda pokušati riješiti s kodom. Želite li u konačnici umetanje novi element u popisu. U ovom slučaju, idemo na pokušajte umetnuti broj 55. No, tu će biti različita slučaja uzeti u obzir. I doista, ovo će biti jedan od big-picture takeaways ovdje, je, Koji su različiti slučajevi. Koje su različite, ako uvjetima ili grane koje vaš program može dobiti? 

Pa, broj pokušavate umetak, koji sada znamo da se 55, ali ako niste znali unaprijed, usuđujem se reći spada u najmanje tri moguće situacije. Gdje bi mogao biti novi element? PUBLIKA: I kraj ili srednji. DAVID J. Malan: Na kraju, u sredini ili na početku. Dakle, ja tvrdim ima najmanje tri problema moramo riješiti. Idemo izabrati ono što je možda nedvojbeno najjednostavniji jedan, gdje je nova elementa pripada na početku. Tako da ću imati dosta kôd kao što traži, što sam upravo napisao. I ja ću imati PTR, koji Ja ću ovdje predstavljam s mojim prstom, kao i obično. 

I zapamtite, što vrijednost smo početne ptr se? Tako smo ga inicijalizirati na nulu u početku. Ali onda što smo radili kada smo mi bili su unutar našeg funkciju pretraživanja? Mi ga postaviti jednaka prva, što ne znači to. Ako sam postaviti PTR jednak prvo, što treba mi ruka zaista biti usmjerene prema? Točno. Dakle, ako Gabe i ja idemo biti jednake vrijednosti ovdje, moramo obje točke na broju 9. 

Dakle, to je bio početak naše priče. A sada ovo je samo jednostavan, iako sintaksa je nova. Koncepcijski to je samo linearno pretraživanje. Je li 55 jednaka do 9? Odnosno, recimo manje od 9. Jer ja pokušavam shvatiti gdje staviti 55. Manji od 9, manje od 17, manje od 20, najmanje 22, najmanje 29, manje od 34, br. Dakle, sada smo u slučaju jedna od najmanje tri. 

Ako želim da ubacite 55 ovamo, što linija koda je potrebno da se pogubili? Kako ovo sliku ljudi trebaju promijeniti? Što da radim s moje lijeve strane? To bi trebao biti nula u početku, jer sam na kraju popisa. A što bi se trebalo dogoditi Ovdje s Petrom, bio je to? Očito će ukazati na mene. Dakle, ja tvrdim ima najmanje dvije linije koda u primjeru koda od danas koji će se provesti ovo scenarij dodao 55 na repu. A mogao sam imati nekoga hop i predstavlja samo 55? U redu, vi ste novi 55. 

I što sad, ako sljedeći Scenarij dolazi zajedno, i želimo umetnuti u s početkom ili voditelj ovog popisa? A kako se ti zoveš, broj 55? 

PUBLIKA: Jack. 

DAVID J. Malan: Jack? U redu, lijepo da zadovolji vas. Dobro došli na brodu. Dakle, sada ćemo umetanje, recimo, broj 5. Evo drugi slučaj trojica smo došli prije. Dakle, ako 5 spada na početku, da vidimo kako ćemo to saznati. Ja formatirati moj PTR kazaljka na broju 9 opet. I shvatio sam, o, 5 je manje od 9. Dakle, popraviti tu sliku za nas. Čije ruke, Gabe-a ili Davida ili-- što je broj 9 je ime? 

PUBLIKA: Jen. 

DAVID J. Malan: Jen je hands-- koji je od naših ruku je potrebno promijeniti? U redu, tako da je Gabe ukazuje na ono što je sada? Na mene. Ja sam novi čvor. Pa ću samo vrsta pokretu Ovdje ga vidimo vizualno. A u međuvremenu što sam naglasiti da? Ipak, gdje sam pokazivao. Dakle, to je to. Dakle, samo stvarno jedna linija koda popravci ovaj problem, čini se. U redu, tako da je dobra. A netko može biti rezervirano za 5? Dođi gore. Mi ćemo vam se sljedeći put. 

U redu, tako da now-- i Kao na stranu, naziva Ja sam ne čineći eksplicitno se navode prava Sada, Pred pokazivač, pokazivač prethodnik i novi pokazivač, to je samo imena dano u uzorak koda na pokazivače ili moje ruke koja je vrsta upućuju okolo. Koje je tvoje ime? 

PUBLIKA: Christine. 

DAVID J. Malan: Christine. Dobro došli na brodu. U redu, tako da razmotrimo sada malo neugodno scenarij, gdje želim ubaciti nešto kao 26. u to. 20? Što? To are-- dobra stvar imamo ovu olovku. U redu, 20. Ako je netko mogao dobiti još jedan komad papir spreman, samo u case-- redu. Oh, interesantno. Pa ovo je primjer od predavanja bug. U redu, tako ono zoveš? PUBLIKA: Julia. DAVID J. Malan: Julia, možete pop se i pretvarati se da nikada nisu bili tamo? U redu, to se nije dogodilo. Hvala vam. Dakle, pretpostavimo da želimo umetnuti Julia je u ovom popisu povezane. Ona je broj 20. I naravno da je ona će pripadati na begin-- ne ukazuju na bilo još. Dakle, tvoja ruka može biti neka vrsta niz nula ili neki smeća vrijednost. Ajmo reći brzi priču. Ja sam pokazujući na broju 5. ovoga puta. Tada sam provjeriti 9. Tada sam provjeriti 17. Tada sam provjeriti 22. I shvaćam, Ooh, Julia treba ići prije 22. Dakle, ono što treba da se desi? Čije ruke je potrebno promijeniti? Julia je, moja, ili-- ono zoveš? 

PUBLIKA: Christian. 

DAVID J. Malan: kršćanin ili? 

PUBLIKA: Andy. 

DAVID J. Malan: Andy. Kršćanin ili Andy? Andy treba ukazati na? Julia. U redu. Dakle, Andy, želiš ukazati na Juliju? Ali čekaj malo. U priči do sada, Ja sam na neki način jedan zadužena, u smislu da Pokazivač je stvar koja je kreće kroz popis. Mogli bi imati ime za Andy, ali nema varijabla zove Andy. Jedina druga varijabla imamo je Prvi, koji je zastupao Gabe. 

Dakle, to je zapravo razlog zašto tako daleko nismo potrebno ovo. Ali sada na zaslonu je spominjem opet od Pred pokazivača. Pa neka mi bude jasniji. Ako je ovo pokazivač, morao sam bolje dobili malo više inteligentni o mom iteracije. Ako vam ne smeta moja ide ovuda opet, pokazujući ovdje, pokazujući ovdje. No, dopustite mi da imaju Pred pokazivač, prethodnik pokazivač, to je vrsta pokazujući na Element bio sam samo na. Dakle, kad idem ovdje, sada moje lijeve strane ažuriranja. Kad idem ovdje moje lijeve strane ažuriranja. I sada imam ne samo kazaljke na element koji ide nakon Julia, Još uvijek imam kazaljke na Andy, prije elementa. Dakle, imate pristup, u biti, krušne mrvice, ako hoćete, svim potrebnim pokazivače. 

Dakle, ako sam pokazujući na Andy i ja sam također upućuju na kršćanina, čije ruke Sada treba istaknuti negdje drugdje? Dakle, Andy sada mogu ukazati na Juliju. Julia sada mogu ukazati na kršćanina. Budući da ona može kopirati moj Desna ruka je kazaljka. I to učinkovito vas stavlja natrag na ovo mjesto ovdje. Dakle, ukratko, iako to nas vodi vrsta zauvijek zapravo ažurirati povezani popis, shvatite da je operacija su relativno jednostavna. To je jedan, dva, tri linija koda u konačnici. No, omotan oko onih linija koda, pretpostavlja je malo logike da učinkovito postavlja pitanje, gdje smo mi? Jesmo li na početku, sredini ili na kraju? 

Sada, svakako postoje i neki drugi Poslovanje bismo mogli provesti. A ove slike ovdje samo prikazuju ono što smo upravo učinili s ljudima. Što je uklanjanje? Ako želim da se, primjerice, ukloniti broj 34 ili 55, Možda imam istu vrstu koda, ali ja ću morati jedan ili dva koraka. Jer ono što je novo? Ako sam nekoga izvadite na kraju, kao broj 55, a zatim 34, što se mora mijenjati kako sam to učinio? Moram se ne evict-- ono zoveš? 

PUBLIKA: Jack. 

DAVID J. Malan: Jack. Moram ne samo evict-- besplatno Jack, tako doslovno nazvati besplatan Jacka, ili barem pokazivač tamo, ali sada ono što treba promijeniti s Petrom? Ruka mu je bolje početi pokazuje prema dolje. Jer čim sam nazvati besplatno Jack, ako je Petar još uvijek pokazujući na Jacka Zato sam se držati poprijeko Popis i pristup to pokazivač, to je kad je naš stari prijatelj segmentacija greška zapravo može udariti u. Zato smo ostavili memorije natrag na Jacka. 

Možete ostati tamo nespretno samo na trenutak. Budući da imamo samo par završne operacije razmotriti. Uklanjanje glavu na popisu, ili beginning-- i ova je malo neugodno. Jer moramo znati da je Gabe je vrsta posebna u ovom programu. Jer doista, on ima svoj pokazivač. On ne samo što je ukazao na, kao gotovo svi ostali ovdje. 

Dakle, kada je glava na popisu je uklonjena, čije ruke je potrebno promijeniti sada? Koje je tvoje ime? 

PUBLIKA: Christine. 

DAVID J. Malan: Ja sam grozna po imenima, očito. Dakle, Christine i Gabe, čije ruke je potrebno promijeniti kad smo pokušati ukloniti Christine, broj 5, sa slike? U redu, tako da ćemo učiniti Gabea. Gabe će se ukazati, vjerojatno, na broju 9. No, što bi se trebalo dogoditi sljedeći? PUBLIKA: Christine trebao biti null [nečujan]. DAVID J. Malan: U redu, trebali bismo vjerojatno make-- Čuo sam "null" negdje. PUBLIKA: Null i slobodno ju. DAVID J. Malan: null što? PUBLIKA: Null i slobodno ju. DAVID J. Malan: Null i slobodno ju. Dakle, to je vrlo jednostavno. I to je idealno da si sada neka vrsta stoji tamo ne pripadaju. Budući da ste bili odvojen od popisa. Vi ste bili učinkovito siroče s popisa. I tako mi je bolje nazvati besplatno sada Christine dati tu memoriju natrag. Inače svaki put mi brisanje čvor s popisa bismo mogli biti stvaranje popisa kraći, ali zapravo ne smanjuje Veličina u memoriji. I tako, ako ćemo držati dodajući i dodavanja, dodajući stvari na popisu, moje računalo može doći sporije i sporiji i sporiji, jer sam ponestaje memorije, čak i ako nisam zapravo korištenjem Christineinom bajtova memorije više. 

Tako je na kraju tu su i drugi scenarija, od course-- uklanjanje u sredini, uklanjanje Na kraju, kao što smo vidjeli. No, zanimljivije Izazov je će biti uzeti u obzir upravo ono što je trčanje vremena. Dakle, ne samo da možete zadržati svoje komada papira, ako, Gabe, ti ne bi smetalo davanje Svatko stres loptica. Hvala vam puno na našem popisu povezan volontera ovdje, ako može. 

[Pljesak] 

DAVID J. Malan: U redu. Dakle par analitičko Pitanje tada, ako je moguće. Vidjeli smo ovaj zapis prije, Veliki O i Omega, gornje granice i donja granica na trajanju od nekog algoritma. Tako ćemo razmotriti samo par pitanja. 

Jedan, i to smo rekli Prije nego što je trčanje Vrijeme traženja Popis u smislu velikom O? Koja je gornja granica na trčanje Vrijeme traženja popis povezan kako je implementiran od strane naših volontera ovdje? To je veliki O n, linearno. Budući da je u najgorem slučaju, element, kao što je 55, bismo mogli biti u potrazi za može biti gdje Jack je, skroz na kraju. I na žalost, za razliku od niza ne možemo dobiti fancy ovaj put. Iako svi naši ljudi bili razvrstani iz malih elemenata, 5, pa sve do većeg elementa, 55, to je obično dobra stvar. No, što to pretpostavka više ne dopušta nam da radim? PUBLIKA: [nečujan] DAVID J. Malan: Molim? PUBLIKA: izravnim pristupom. DAVID J. Malan: izravnim pristupom. A s druge strane to znači da ne možemo više koristiti slabu nule, intuiciju, i očiglednost korištenja binarni Pretražite i podijeli pa vladaj. Jer iako smo ljudi bi očito vidim da je Andy ili kršćanski su otprilike u sredini popisa Mi samo znamo da je kao Računalo koje skimming popis od samog početka. Tako smo odustali od tog slučajni pristup. 

Tako veliki O n sada je gornja vezan na naše vrijeme pretraživanja. Što je omega našega traženja? Koja je donja granica na traženje za neki broj u ovom popisu? PUBLIKA: [nečujan] DAVID J. Malan: Molim? PUBLIKA: Jedan. DAVID J. Malan: Jedan. Dakle, konstanta vrijeme. U najboljem slučaju, Christine je doista na početku popisa. I mi tražimo broj 5, pa smo je pronašli. Dakle, nije velika stvar. Ali ona mora biti na početku popisa u ovom slučaju. Što je s nečim kao što je brisanje? Što ako želite izbrisati element? Koja je gornja granica i donja granica o brisanju iz nešto povezano popis? PUBLIKA: [nečujan] DAVID J. Malan: Molim? PUBLIKA: n. DAVID J. Malan: n Doista gornju granicu. Budući da je u najgorem slučaju ćemo pokušati izbrisati Jacka, kao što smo upravo učinili. On je skroz na kraju. Vodi nas zauvijek, ili n koraka kako bi ga pronašli. Dakle, to je gornja granica. To je linearno, sigurno. I najbolji slučaj pokrenut vremena, ili donja granica u najboljem slučaju će biti konstantna vrijeme. Jer možda ćemo pokušati izbrisati Christine, a mi samo se posreći Ona je na početku. Samo malo. Gabe je bio i na početku, a imali smo i ažurirati Gabea. Dakle, to nije bio samo jedan korak. Tako je to doista konstantna vrijeme, u najboljem slučaju, ukloniti najmanji element? To je, iako bi to moglo biti dva, tri, ili čak 100 linija koda, ako je isti broj linije, a ne u nekoj petlji, i neovisno o veličini popisa, apsolutno. Brisanje element u početak popisa čak i ako se moramo nositi s Gabe, još uvijek je konstanta vrijeme. 

Dakle, ovo izgleda kao ogromni korak unatrag. A što gubljenje vremena ako je, u tjednu i jednom tjedno nuli smo imali ne samo pseudocode koda, ali stvarni broj provesti nešto što je zapisnik Baza n, odnosno prijavite, a, n, baza 2, u smislu njegovog vremena rada. Pa zašto bi dovraga želimo početi korištenjem nešto poput popisa povezane? Da. 

PUBLIKE: Dakle, možete dodati elementi niza. DAVID J. Malan: Dakle, možete dodati elemente niza. I ovo je tematska. I dalje ćemo vidjeti ovo, ovo kompromis, mnogo kao što smo vidjeli trade-off s udruživanjem vrste. Mi stvarno mogao ubrzati Traženje ili sortiranje, bolje rečeno, ako ćemo potrošiti malo više prostora i imati dodatni komad sjećanja ili niz udruži- vrste. No, trošimo više prostor, ali mi uštedjeti vrijeme. U ovom slučaju, mi smo odustajanje vremena, ali smo dobivanjem fleksibilnost, dinamika, ako hoćete, koji je nedvojbeno pozitivna osobina. 

Mi smo također trošiti prostor. U kojem smislu je povezan popis skuplji u pogledu prostora nego niz? Gdje se dodatni prostor dolazi? Da? 

PUBLIKA: [nečujan] pokazivač. 

DAVID J. Malan: Da, mi također imaju pokazivač. Dakle, ovo je minorly neugodno u da više ne ja Ja spremanje samo int zastupati int. Ja spremanje int i A pokazivač, što je također 32 bita. Dakle, ja sam doslovno udvostručuje Količina prostora koji su uključeni. Dakle, to je kompromis, ali to je u slučaju int. Pretpostavimo da niste spremanje int, ali pretpostavljam da je svaki od tih pravokutnika i svaki od tih ljudi je predstavlja Riječ, engleska riječ koja može biti pet znakova, 10 likovi, možda čak i više. Zatim dodavanjem samo 32 više bitova bi moglo biti manje od velikog posla. 

Što ako svaki od studenata u demonstracijama bili su doslovno studentske tvorevina koja imaju imena i kuće, a možda telefonski brojevi i Twitter ručke i slično. Dakle sva polja smo počeli Riječ je o drugom danu, mnogo manje od velika stvar kao što je naši čvorovi dobili još zanimljivije i veliki potrošiti, eh, dodatni Pokazivač samo da ih povezivati. Ali doista, to je kompromis. I doista, kod složenije, kao što ćete vidim po skimming kroz da određeni primjer. Ali što ako je bilo neki sveti gral ovdje. Što ako mi ne uzeti jedan korak unatrag, ali ogromni korak naprijed i provesti podataka struktura preko koje smo pronaći elemente poput Jacka ili Christine ili bilo koje druge elemente u ovom nizu u pravog stalnom vrijeme? Pretraživanje je konstantan. Brisanje je konstantan. Insert je konstanta. Sve ove aktivnosti su konstanta. To će biti naš sveti gral. I to je mjesto gdje smo će pokupiti sljedeći put. Vidimo se onda.