SPEAKER 1: Dobro, to je CS50 Ovo je kraj tjedna pet. I podsjetiti da je zadnji put smo počeli gleda na ljubitelj podataka strukture koji su se počeli rješavati problemi, koji su se počeli uvoditi novi problemi, ali ključ za to Bila je to threading da smo počeo raditi od čvora do čvora. Dakle, to je, naravno, popis pojedinačno povezani. I pojedinačno povezani, Mislim da postoji samo jedan nit između svaki od tih čvorova. Ispada da možete napraviti ljubitelj stvari kao dvostruko povezane liste gdje imate strelicu ide u oba smjera, što može pomoći s određenim učinkovitosti. Ali to riješilo problem? Koji problem je ovo riješiti? Zašto nam je stalo u ponedjeljak? Zašto, u teoriji, nije mi stalo u ponedjeljak? Što to radi? 

PUBLIKA: Mi dinamički promijeniti veličinu. 

SPEAKER 1: OK, možemo dinamički promijeniti veličinu. Pa učinili oboje. Tako da može dinamički mijenjati veličinu ovog struktura podataka, dok je niz, Podsjetimo, morate znati priori koliko prostora želite a ako je potrebno malo više Prostor, ti si vrsta od sreće. Morate stvoriti cijeli novi niz. Morate premjestiti sve svoje podaci iz jednog u drugi, na kraju oslobodio stari niz ako možete, a zatim nastavite. Koji samo osjeća vrlo skupo i vrlo neučinkovit, i doista može biti. Ali to nije sve dobro. Mi platiti cijenu, što je bio jedan od više očitih cijena mi platiti pomoću popisa povezani? 

PUBLIKA: Moramo iskoristiti dvostruka prostor za svaku od njih. SPEAKER 1: Da, pa trebamo najmanje dva puta toliko prostora. Zapravo, shvatio sam ovu sliku je čak i malo zabludu, jer na CS50 IDE u puno modernog računala, pokazivač ili adresa u stvari nije četiri bajta. Vrlo često ovi dana osam bajtova, koji znači dno najviše pravokutnici tamo u stvarnosti su vrsta dvostruko velika kao što sam izvući, što znači da koristite tri puta puno prostora kao što smo mogli imati drugačije. Sada, u isto vrijeme, mi smo uvijek govori bajtova, zar ne? Mi ne nužno i govori megabajta ili gigabajta, osim tih podataka strukture dobili veliki. 

I tako danas smo započeli u obzir kako bismo mogli istražiti podatke učinkovitije ako u Činjenica podaci dobiva veći. No, pokušajmo canonicalize operacije prvi koje možete učiniti na njih vrste podatkovnih struktura. Dakle, nešto poput povezan Popis općenito podržava Poslovanje željeli izbrisati, umetnite i pretraživanje. A što mislim pod tim? To samo znači da je obično, ako su ljudi povezani pomoću popisa, oni ili netko drugi provodi funkcije kao što izbrisati, umetnuti, i pretraživanje, tako da možete zapravo učiniti nešto korisna sa strukturom podataka. Tako ćemo uzeti brzo pogledati kako bismo mogli provesti neki broj za popis povezane kako slijedi. 

Dakle, ovo je samo neki C kod, ni kompletan program da sam jako brzo tučeno gore. To nije online u distribuciji broj, jer se neće pokrenuti. Ali primijetite Upravo sam sa komentarom rekao, točka točka točkica, nešto Postoji, dot dot dot, nešto postoji. I neka je samo pogledajte što sočan dijelovi. Dakle, na liniji tri, Podsjećamo da je ovo sada mi predložio proglašenje čvor posljednji vrijeme, jedan od onih pravokutnih objekata. To je int kako ćemo nazvati N, ali smo ga mogli nazvati ništa, a zatim struct čvor zvijezda zove sljedeći. I samo da bude jasno, da su drugi linija, na liniji šest, što je to? Što se to radi za nas? Jer to sigurno izgleda više grobni od naših uobičajenih varijabli. 

PUBLIKA: To čini premjestiti na jedan. 

SPEAKER 1: To čini premjestiti na jedan. I da budemo precizniji, to će pohraniti adresu čvora koji je značilo da se semantički pokraj njega, zar ne? Dakle, to neće nužno premjestiti ništa. To samo će pohraniti vrijednost, što je će biti adresa nekog drugog čvora, i to je razlog zašto smo je rekao struct čvor zvijezda, zvijezda označava pokazivač ili adresu. U redu, tako da sada ako pretpostavimo da imamo ova N dostupan za nas, i neka je Pretpostavljam da netko drugi ima umetnuta cijela hrpa brojeva u popisu povezane. I to povezano popis ukazao na neke točke varijabla zove popis koji je donesen ovamo kao parametar, Kako mogu ići o liniji 14 provedbenih pretraživanje? Drugim riječima, ako sam provedbi Funkcija čija je svrha u životu je uzeti int, pa tek onda početak popisa povezane, da je pokazivač na popis povezani. Kao prvo, tko mislim Davida bio naš volonter u ponedjeljak, on pokazujući na cijeli povezani popis, to je kao da smo mi prolaze David je u kao naš argument. Kako ćemo ići oko poprijeko ovaj popis? Pa, ispada da iako pokazivače su relativno novi sad za nas, možemo to učiniti relativno straightforwardly. 

Ja ću ići naprijed i proglasiti privremenu varijablu koja po konvenciji samo ide zvati pokazivač ili PTR, ali možete ga nazvati sve što želite. I ja ću inicijalizirati je na početku liste. Tako možete vrsta misli o ovome Kao što je mene učitelja drugi dan, vrsta pokazujući na nekoga među našim ljudima kao volonteri. Tako sam privremenu varijablu koja je Samo pokazujući na istu stvar da su naši slučajno zove volonter David je također istaknuo. Sada, dok je pokazivač nije null, jer opoziv koji null neka posebna Sentinel vrijednost markira kraj popisa, pa dok nisam pokazujući na tlo poput našeg zadnjeg volonter je, idemo naprijed i učinite sljedeće. Ako pointer-- a sada sam vrsta želim učiniti ono što smo učinili s učenikom structure-- ako pokazivač točka uz equals-- a, ako se pokazivač točka N jednak varijabla jednaka N je Argument koji je donesen u, onda želim ići naprijed i reći povratak istina. Našao sam broj nje unutar jedan od čvorova mom popisu povezane. Ali dot više radi u ovom kontekstu, jer pokazivač, PTR, je doista pokazivač, adresa, možemo zapravo predivno koristiti konačno komad sintakse takav čini intuitivan osjećaj i zapravo koristite strelicu ovdje, što znači ići od da adresa na cijeli broj tamo u. Dakle, to je vrlo slično u Duh operatoru dot, ali zato pokazivač nije pokazivač a ne stvarna sama struct, mi samo koristiti strelicu. 

Dakle, ako je trenutni čvor da sam ja, privremena varijabla, sam pokazujući na nije N, ono što želim učiniti? Pa, sa svojim ljudskim dobrovoljcima da smo imali tu neki dan, ako je moj prvi čovjek nije onaj sam žele, a možda i drugi ljudski nije onaj želim, a treći, ja morate držati fizički kreće. Poput kako sam korak kroz popis? Kad smo imali niz vas, upravo učinio kao ja plus plus. No, u ovom slučaju, dovoljno je napraviti pokazivač, dobiva, pokazivača, sljedeći. Drugim riječima, sljedeći polje je kao i svi napustili rukama da su naši ljudski dobrovoljci u ponedjeljak su pomoću ukazati na nekom drugom čvoru. To su bili njihovi susjedi. 

Dakle, ako želim korak kroz ovaj popis, Ne mogu samo ja radim plus plus više, Ja umjesto toga reći Ja, pokazivač, ide jednaka bez obzira na sljedeći polje, sljedeći polje, sljedeći polje, Sljedeći sve one koji su ostali rukama da smo imali na pozornici usmjerenim nekim kasnijim vrijednosti. A ako ja dobiti preko da cijeli iteracija, i na kraju, udario sam NULL nemaju nađeno N ipak, samo sam return false. Pa opet, sve što radimo ovdje, po slici trenutak prije, počinje od pokazujući na počevši od popisa vjerojatno. A onda sam provjeriti, je vrijednost Tražim jednaka devet? Ako je tako, ja se vratiti istina i ja sam učinio. Ako ne, ja ažurirati svoju ruku, AKA pokazivač, ukazati Na sljedećem strelicama lokaciji, a Onda sljedeći Arrow je mjesto, i sljedeći. Ja sam jednostavno šetnju kroz ovaj niz. 

Pa opet, koga briga? Kao što je to sastojak za? Pa, sjećam da smo uveli pojam stog, koji je tip sažetak podataka u mjeri u kojoj je to Nije C stvar, to nije stvar CS50, to je apstraktna ideja, ova ideja slaganje stvari jedan povrh drugog koji se može provesti u nakupine različitih načina. A jedan od načina da predloženo je s niz ili s popisa povezane. I ispada da kanonski, A stog podržava najmanje dvije operacije. I krilaticama su guranje, na gurati nešto na stog, kao novi ladicu u blagovaonica, ili pop, što znači ukloniti najviši ladicu iz dimnjaka u blagovaonicu hodnik, a onda možda neki druge poslove, kao dobro. Pa kako bismo mogli definirati strukturu da smo sada zovete stog? 

Pa, imamo sve traženim Sintaksa na raspolaganju u C. kažem, dajte mi definiciju vrsta struct unutar stog, Idem reći je niz, od a cijela hrpa brojeva, a zatim veličina. Dakle, drugim riječima, ako želim implementirati ovaj u kodu, neka mi ići i samo vrsta privući što to govori. Dakle, ovo je rekao, dajte mi struktura koja ima niz, a ja ne znam što je kapacitet, to je očito neka konstanta koja imam definirani drugdje, i to je u redu. No, pretpostavljam da je to samo jedan, dva, tri, četiri, pet. Dakle, kapacitet je 5. Ovaj element unutar moje struktura će se zvati brojeve. A onda mi je potreban druga varijabla očito zove veličina da najprije idem propisati inicijalizira na nulu. Ako postoji ništa u snop, veličina nula, i to je vrijednosti smeće u brojkama. Nemam pojma što je tamo samo još. 

Dakle, ako želim gurati nešto na stog, Pretpostavljam da zovem funkciju guranje i Kažem gurnuti 50, kao broj 50, gdje bi predložiti Ja ga nacrtati u ovom nizu? Postoji pet različitih mogućih odgovora. Kamo želite gurnuti broj 50? Ako je cilj ovdje, opet, nazovite Funkcija gurati, prolaze u svađi 50, gdje sam ga stavio? Pet possible-- 20% šanse nagađanje ispravno. Da? 

PUBLIKA: Daleko pravo. 

SPEAKER 1: Daleko pravo. Tu je sada 25% šanse nagađanje ispravno. Tako da bi zapravo biti u redu. Po konvenciji, reći ću s nizom, mi općenito bi početi na lijevo, ali smo mogli sigurno početi na desnoj strani. Dakle, spojler ovdje bi se sam Vjerojatno će ga izvući na lijevo, baš kao u normalnom polje gdje Sam početak ide s lijeva na desno. Ali ako možete okrenuti aritmetički, u redu. To jednostavno nije konvencionalno. OK, moram napraviti jedan više promjena ipak. Sad kad sam gurnula nešto na stog, što je sljedeće? 

U redu, moram povećajte veličinu. Pa neka mi ići naprijed i samo ažurirati to, što je nula. I umjesto da sad idem staviti u vrijednosti jedne. A sada pretpostavimo da gurnuti još broj na stog, kao što je 51. Pa, moram napraviti još jedan promjene, što je do veličine dva. A onda pretpostavljam da gurnuti još jedan broj na stog poput 61, Sada moram ažurirati veličinu još jedan vrijeme, i dobiti vrijednost 3 kao veličini. A sada pretpostavimo zovem pop. Sada pop, po konvenciji, ne uzeti argument. Uz stog, cijela točka ladice metafore je da nemate slobodu ići dobiti taj pladanj, sve što možete učiniti je pop najviši jedan od snop, samo zato. To je ono što ova struktura podataka radi. 

Dakle, po toj logici, ako ja reći pop, što dolazi s? Dakle, 61. Dakle, ono što je stvarno računalo učiniti u memoriji? Što je moj broj ima veze? Što biste predložiti mijenjamo na zaslonu? Što treba promijeniti? Žao nam je? Tako smo dobili osloboditi od 61. Tako sam definitivno može učiniti. A ja mogu dobiti osloboditi od 61. I onda ono što drugima Promjena treba dogoditi? Veličina vjerojatno ima vratiti na dva. I tako to je u redu. Ali čekaj malo, veličina trenutak prije bile tri. Ajmo učiniti brzo provjeriti razum. Kako znamo da htio riješiti od 61? Zato smo iskakanje. I tako sam ovu drugu veličinu imovine. 

Čekaj malo, ja sam misleći natrag na tjedan-dva kad smo počeli govoriti o polja, gdje je ovo položaj nula, ovo je položaj jedan, ovo je položaj dva, to je lokacija tri, četiri, izgleda da je odnos između veličine i element koji želim ukloniti iz polja Čini se da samo biti što? Veličina minus jedan. I tako to je kako kao ljudi znamo 61 na prvom mjestu. Kako je računalo će znati? Kada vaš broj, gdje vas vjerojatno želite učiniti veličine minus jedan, pa tri minus jedan je dva, a to znači želimo riješiti 61. A onda smo doista može ažurirati veličina, tako da veličina sada ide od tri do samo dva. I samo da se pedantan, idem predložiti da sam učinio, zar ne? Vi predložio intuitivno točno sam trebao riješiti 61. Ali se nisam vrsta vrsta stečen osloboditi od 61? Ja sam uspješno zaboravila da je to zapravo bilo. I sjetim PSET4, ako ste pročitali članak o forenzici, PDF da smo imali vi pročitali, ili će pročitati ovaj tjedan za PSET4. Sjetite se da je to zapravo tijesnoj se cijela ideja računalne forenzike. Što je računalo obično se je to samo zaboravlja gdje se nešto nalazi, ali to ne ide i slično pokušati ga precrtati ili dotjerivanje ti bitovi s nula i jedinica ili neki drugi slučajni uzorak osim ako ste sami učinili namjerno. Dakle, vaša intuicija je Dobro, neka je riješiti 61. No, u stvarnosti, ne moramo gnjaviti. Mi samo trebate zaboraviti da je da je tamo mijenjajući naše veličine. 

Sada postoji problem s ovom stog. Ako sam gurati stvari na stog, što je Očito će se dogoditi u samo nekoliko trenutaka vremena? Ćemo ponestane prostora. I što nam je činiti? Mi smo vrsta pijan. Ovaj provedba ne dopustite nas veličinu polja, jer pomoću ova sintaksa, ako vas mislim natrag na tjedan-dva, nakon što ste proglasili veličina niza, nismo vidjeli mehanizam još gdje možete promijeniti veličinu polja. I doista C nema tu značajku. Ako kažeš daj mi pet Nths, nazivaju ih brojevi, to je sve što ćeš dobiti. Tako smo sada od ponedjeljka, ima sposobnost izražavanja rješenje ipak, samo trebamo ugađanje definicija našeg dimnjaka ne biti neki hard-kodirane niz, ali samo za pohranu adresu. 

Sad zašto je to? Sada samo moramo biti zadovoljni činjenica da kad je moj program radi, Ja sam vjerojatno idući u moraju pitati čovjeka, koliko brojeva želite spremiti? Tako je ulaz mora doći odnekud. Ali jednom znam da broj, onda ja mogu samo koristiti ono što funkcionira dati mi komad memorije? Mogu koristiti malloc. I ja mogu reći bilo koji broj bajtova Želim natrag za ove Nths. I sve što imam za pohranu u brojkama varijabla ovdje unutar ove STRUCT treba biti što? Što se zapravo ide u brojevi u ovom slučaju? Da, pointer na prvi bajt taj komad memorije, točnije, adresa od prvih tih bajtova. Nije bitno je li to jedan byte ili milijardu bajtova, Samo moram brinuti o prvom mjestu. Jer ono malloc jamstva i moji operativnog sustava jamstva, da je komad memorije I. dobiti, to će biti u dodiru. Tu neće biti praznina. Dakle, ako sam pitao za 50 bajtova ili 1.000 bajtova, svi oni će biti natrag na leđa na leđa. I tako dok se sjećam kako je velika, kako koliko sam tražio, sve što trebate znati je prvi takav adresa. 

Tako sada imamo mogućnost u kodu. Iako, to će nas odvesti više vremena za pisanje ovaj gore, mi sada mogli preraspodijeliti tu memoriju Samo spremanje drugu adresu tamo ako želimo veći ili čak manji komad memorije. Dakle, ovdje se trgovina off. Sada smo dobili dinamiku. Imamo još contiguousness sam tvrdi. Budući da će nam dati malloc neprekinut komad memorije. No, to će biti bol u vrat za nas, programer, zapravo kodirati gore. To je samo više posla. Trebamo kôd srodan što sam bio lupanje iz samo trenutak prije. Vrlo izvodljiv, ali dodaje kompleksnost. I tako vrijeme programer, programer Vrijeme je još jedan izvor da bismo je potrebno provesti neko vrijeme da biste dobili nove značajke. I onda naravno postoji red. Nećemo ulaziti u to jedan u više detalja. Ali to je vrlo sličan u duhu. Mogao bih provesti red, i njegove odgovarajuće radnje, Postavi u red ili dequeue, kao što dodati ili ukloniti, to je samo ljubitelj način ga govoreći: ili u red dequeue, kao što slijedi. Ja samo mogu dati ja osobno struct opet ima niz je niz, opet ima veličinu, ali zašto mi sada treba pratiti prednje redu? Nisam morate znati ispred moje stog. Pa, ako sam opet za queue-- neka je samo teško kodirati ga kao vlasništvo kao pet cijeli brojevi u tu potencijalno. Dakle, ovo je nula, jedan, dva, tri, četiri. To će biti ponovno pozvao brojevi. I to će se zvati veličina. 

Zašto je nije dovoljna da imaju samo veličinu? Pa, neka je gurati one iste brojeve na. Tako sam pushed-- enqueued sam, ili guraju. Sad ću u red 50, a zatim 51, a zatim 61, a dot dot dot. Dakle, to je u red. Enqueued sam 50, zatim 51, pa 61. I to izgleda identično na hrpi do sada, osim što trebate napraviti jednu promjenu. Trebam ažurirati ove veličine, pa sam ići od nula do jedan do dva na tri sada. Kako dequeue? Što se događa s dequeue? Tko bi trebao ispasti ovaj popis prvi ako je linija na Apple Store? Dakle, 50. Dakle, to je vrsta trickier ovaj put. Dok zadnji put je bilo super lako samo napraviti veličina minus jedan, Ja bi se na kraju mog niz učinkovito gdje su brojevi, uklanja 61. Ali ja ne želim ukloniti 61. Želim da se 50, koji je bio tamo u 5:00 da se postroje za Novi iPhone i sitnica. I tako riješiti 50, ja ne mogu samo to učiniti, zar ne? Mogu precrtati 50. Ali samo mi smo rekli ne moraju biti tako analni da precrtati ili sakriti podatke. Mi samo možemo zaboraviti gdje je. 

Ali ako promijenim veličinu sada dva, to dovoljno informacija znati što se događa u mom redu? Ne baš. Kao moja veličina je dva, ali gdje se red početak, pogotovo ako još uvijek imam te iste brojeve u memoriji. 50, 51, 61. Dakle, moram se sjetiti Sada, gdje je prednji je. I tako kao što sam predložio gore tamo ćemo upravo nazvao NTH sprijeda, čija je početna vrijednost treba biti što? Nula, tek početak popisa. Ali sada uz decrementing veličina, samo smo povećajte frontu. Sada ovdje je još jedan problem. Dakle, nakon što sam se stalno događa. Smatram to je broj poput 121, 124, a onda, dovraga, Ja sam iz prostora. Ali čekaj malo, ja nisam. Dakle, u ovom trenutku u priči, Pretpostavimo da je veličina je jedan, dva, tri, četiri, pa pretpostavljam da je veličina je četiri, prednji je jedan, pa 51 je na prednjoj strani. Želim staviti ovdje drugi broj, ali, k vragu, ja sam iz prostora. Ali nisam stvarno, zar ne? Gdje bih mogao staviti neke dodatna vrijednost, kao i 171? Da, mogao sam samo vrsta vratite tamo, zar ne? A onda prelaze iz 50, ili samo ga prebrisati sa 171. A ako se pitate zašto naši brojevi dobio tako slučajni, oni se obično uzimaju računalo Znanost tečajevi na Harvardu nakon CS50. Ali to je dobra optimizacija, jer sada nisam gubit prostor. Još uvijek imati na umu koliko je velika ova stvar je ukupno. To je pet ukupno. Jer ja ne želim početak prepisati 51. Dakle, sada sam još uvijek izvan prostora, tako da je isti problem kao i prije. Ali možete vidjeti kako sada u kodu, vjerojatno napisati malo više Složenost da bi se to dogodilo. A u stvari, ono što operater u C vjerojatno omogućuje što magično to kružnost učiniti? Da operator modulo, postotak znak. Dakle, što je vrsta cool o redu, iako smo zadržati crtanje polja kao što su ovi poput ravne linije, ako vas vrsta misli o tome što zakrivljeni okolo kao krug, onda samo Intuitivno je vrsta radova psihički Mislim da je malo više čisto. Ti bi i dalje morati provesti koji mentalni model u kodu. Dakle, ne da je teško, u konačnici, za provedbu, ali još uvijek izgubiti size-- radije, sposobnost za promjenu veličine, osim ako smo to učinili. 

Moramo se riješiti niz, mi zamijenite ga s jednim pokazivačem, a onda negdje u mom kodu imam poziv što funkcionira zapravo stvoriti Niz nazivaju brojeve? Malloc, ili neki sličan funkcija, točno. Bilo kakva pitanja o hrpama ili redova. Da? Dobro pitanje. Što modulo biste koristili ovdje. Dakle općenito, kada koristite mod, što bi to sa veličinom od Cijela struktura podataka. Dakle, nešto poput pet ili sposobnosti, ako to je konstanta, vjerojatno je uključen. Ali samo radi modulo pet Vjerojatno nije dovoljno, jer moramo znati da smo učinili zamotajte ovdje ili ovdje ili ovdje oko. Dakle, vjerojatno ste također će htjeti uključiti veličina stvar, ili prednji varijabla, kao dobro. Dakle, to je samo to relativno Jednostavna matematika izraz, ali modulo će biti ključni sastojak. 

Dakle, kratki film, ako hoćete. Animacija da su neki ljudi na drugom sveučilištu staviti zajedno da smo prilagođena za ovu raspravu. To uključuje Jack učenju činjenice o redovima i statistike. 

FILM: Jednom davno, bio je čovjek po imenu Jack. Kada je došlo do izrade prijatelje, Jack nije imao smisao. Tako je Jack otišao razgovarati s najpopularniji dečko znao. Otišao je Lou i pitao, što da radim? Lou je vidio da je njegov prijatelj je stvarno nevolji. Pa, on je počeo, samo pogledajte kako ste odjeveni. Zar ne imati bilo odjeću s različitim izgled? Da, rekao je Jack. Ja sigurno učiniti. Dođite u moju kuću i Ja ću im pokazati. Tako su otišli Jack. A Jack je pokazao Lou kutiju gdje je zadržao sve svoje košulje, a njegove hlače i čarapama. Lou je rekao, vidim da imate sve svoje odjeće u gomili. Zašto ne nosiš neke drugi jednom u neko vrijeme? 

Jack je rekao, dobro, kada sam izvadite odjeću i čarape, Ja ih oprati i staviti ih daleko u kutiji. Tada dolazi sljedeći jutro, i gore sam hop. Idem kutije i dobiti moja odjeća off vrhu. Lou brzo shvatio problem s Jackom. Držao odjeću, CD-a, a knjige u dimnjaku. Kad je posegnuo za nešto čitati ili nositi, on bi odabrati gornji knjigu ili donje rublje. Onda kada je učinio, on je bi ga stavio natrag. Natrag to će ići, na vrhu dimnjaka. Znam rješenje, rekao pobjednički Loud. Morate naučiti početi koristiti red. Lou je Jackove odjeću i objesio ih u ormaru. I kad je ispraznio okvir, on je samo bacio. 

Tada je rekao, sada je Jack, na kraju dan, stavite odjeću na lijevoj kada ih otpustiti. Sutra ujutro kad vas vidjeti sunce, dobiti svoju odjeću na desnoj strani, od kraja linije. Zar ne vidite? reče Lou. To će biti tako lijepo. Vi ćete nositi sve odjednom Prije nego što nosite nešto dvaput. I sa svime u redovima u svom ormaru i polica, Jack je počeo osjećati sasvim sigurni u sebe. Sve zahvaljujući Lou i njegova prekrasna red. SPEAKER 1: Dobro, to je divan. Dakle, ono što je stvarno događa na ispod haube sada? Da imamo upućuje, da imamo malloc, da imamo mogućnost stvaranja komadi memorije za sebe dinamički. Dakle, ovo je slika nas nazire baš neki dan. Mi stvarno ne prebiva na njemu, ali ova slika ima se događa ispod napa već tjednima. I tako to predstavlja, samo pravokutnik koji smo izvući, memorije računala. A možda je računalo, ili CS50 ID, ima gigabajt memorije ili RAM ili dva gigabajta ili četiri. To zapravo ne smeta. Vaš operativni sustav Windows ili Mac OS ili Linux, suštini omogućuje svoj program da mislim da ima pristup na cjelinu memorije računala, iako možda biti pokrenut više programa odjednom. Tako je u stvarnosti, to zapravo ne rade. No, to je vrsta iluzije s obzirom na sve svoje programe. Dakle, ako ste imali dva nastupa RAM, ovaj je kako se računalo može misliti o tome. 

Sada je slučajno, jedan od tih stvari, jedna od tih segmenata memorije, naziva stog. I doista bilo koje vrijeme Do sada je u pisanje koda da ste naziva funkcija, primjerice Main. Sjetite se da je bilo vrijeme imam memorije nacrtana računala, Uvijek sam crtati vrsta polovica pravokutnika ovdje i ne smetaju govori o tome što je ranije. Jer kada glavni zove, tvrdim da ste dobili ovu luč memorije da ide ovdje dolje. I ako glavna naziva funkcija kao zamjene, te zamjena ide ovdje. I ispada da je gdje je završio. Na nešto što se zove snop unutar memorije računala. Sada je na kraju dan, ovo je samo bavi. To je kao byte nula, bajt jedan, bajt 2 milijarde. Ali ako mislite o tome što je ovaj pravokutni objekt, svi mi radimo svaki Vrijeme mi zovemo funkcija raslojavanje novi komad memorije. Mi smo davanje tu funkciju kriška vlastite memorije raditi. 

A sjećam se sada da je to važno. Jer ako mi nemamo nešto poput zamjene i dvije lokalne varijable kao što su A i B i možemo promijeniti te vrijednosti od jednog i dva za dva i jedan, opoziv da kad zamjena vraća, to je kao da je ovaj kriška memorije je samo otišao. U stvarnosti, to je još uvijek Postoji forenzički. I nešto još zapravo tamo. No konceptualno, to je kao iako je potpuno nestala. I tako glavna ne zna bilo koji dio posla koje je učinjeno u tom swapu funkciji, osim ako to je zapravo prošlo u onima Argumenti po karti ili referenca. Sada, temeljno rješenje za taj problem s swapa prolazi stvari u koju adresu. No, ispostavilo se, također, ono što je događa iznad tog dijela pravokutnika sve ovo vrijeme Još ima više memorije tamo. A kada dinamički alocirati memoriju, da li je unutar GetString, koji smo radili za vas u CS50 knjižnica, ili ako vi nazvati i pitati malloc operativni sustav za komad memorije, to ne dolazi iz dimnjaka. Ona dolazi s drugog mjesta u memoriju računala kako se zove gomila. I to nije bilo drugačije. To je isti RAM. To je isti memorije. To je samo RAM-to je gore tamo umjesto ovamo. 

I tako, što to znači? Pa, ako vaše računalo ima konačan iznos memorije i stog raste, tako govoriti, a gomila, prema ovom strijelom, raste prema dolje. Drugim riječima, svaki Vrijeme nazovete malloc, ti si se dao krišku memorije odozgo, onda možda malo niža, a zatim malo niže, svaki put kad poziv malloc, hrpu, to je običaj, je vrsta raste, raste bliže i bliže što? Stog. Dakle, to se čini kao dobra ideja? Mislim, gdje je zapravo nije jasno Što još možete učiniti ako samo imaju ograničen količinu memorije. No, to je sigurno loše. Te dvije strelice ste na sudar naravno jedni za druge. 

I ispada da negativca, ljudi koji posebno su dobri s programiranjem, i pokušava provaliti u računala, mogu iskoristiti ovu stvarnost. U stvari, neka je uzeti u obzir malo isječak. Dakle, ovo je primjer možete pročitati O detaljnije na Wikipediji. Mi ćemo Vam ukazati na Članak ako znatiželjni. No, tu je napad općenito poznat kao buffer overflow koji postoji koliko god ljudi imali sposobnost da manipulira memorije računala, a posebno u C. Dakle, ovo je vrlo proizvoljna programa, ali neka je čitati od dna prema gore. Glavni u argC char zvjezdica argv. Dakle, to je program koji traje argumente naredbenog retka. I svi glavni očito nema je poziv funkcija, nazivaju ga F za jednostavnošću. I to prolazi u što? Argv jednog. Dakle, to prelazi u F god Riječ je da korisnik upisali u retku nakon što je Ime programa je na sve. Toliko poput Cezara ili Vigenere koji možda sjetiti radiš sa argv. 

Dakle, što je F? F uzima u nizu kao jedini argument, AKA ugljen zvijezda, isto stvar, kao string. I to se zove proizvoljno bar u ovom primjeru. A onda char c 12, Samo u laik uvjete, Što je char c nosač 12 radi za nas? Što je to? Dodjela memorije, posebno 12 bajta za 12 znakova. Točno. I onda posljednja linija, promiješati i kopija, vjerojatno ste ne vidi. To je niz kopija Funkcija čija je svrha u životu je da kopirate svoju drugu tvrdnju u svom prvom argumentu, ali samo do određeni broj bajtova. Dakle, treći argument kaže, koliko bajtova trebate kopirati? Duljina trake, sve što korisnik upisali u. A sadržaj bar, taj string, su kopirati u memoriju ukazao na na C 

Tako to izgleda nekako glupo, i to je to. To je neprirodan primjer, ali to je predstavnik klase napada vektora, način napadaju program. Sve je u redu i dobro ako korisnik vrste u riječ koja je 11 znakova ili manje, plus backslash nula. Što ako korisnik upiše u više od 11 ili 12 ili 20 ili 50 znakova? Što je ovaj program će učiniti? Potencijalno SEG kriv. Ide slijepo kopirati sve što je u baru do svoje dužine, koji je doslovno sve u baru, u adresi ukazao na C. No C je samo preventivno dati kao 12 bajtova. Ali nema dodatnih provjera. Nema li uvjete. Nema provjere ovdje pogreške. 

I tako ono što ovaj program učiniti je samo slijepo kopirati jednu stvar na drugu. I tako, ako ćemo izvući ovu kao slika, evo samo komadić od memorijskog prostora. Tako obavijest na dnu smo imaju lokalnu varijablu bar. Tako da pokazivač da će store-- umjesto da lokalne argument koji je će pohraniti string bar. A onda primijetiti samo iznad njega u snopu, jer svaki put kad pitam za sjećanje na dimnjaku, to ide malo iznad njega slikovito, Obavijest da imamo 12 bajtova tamo. Gornja lijeva jedna je C nosač nula i donji desni je C nosač 11. To je samo način na koji računala će ga nokautirati. Dakle, samo intuitivno, ako bar ima više od 12 znakova ukupno, uključujući obrnute kose crte nula, gdje je 12 ili C nosač 12 ići? Ili, bolje rečeno, gdje je 12. lik ili 13. znak, stoti lik ide završiti na slici? Iznad ili ispod? 

Točno, jer iako sama stog raste prema gore, nakon što ste stavili stvari u da, to za dizajn razloga, stavlja memoriju od vrha do dna. Dakle, ako imate više od 12 bajtova, da ćeš početi prepisati bar. A da je bug, ali to je zapravo i nije velika stvar. Ali, to je velika stvar, jer je više stvari događa u memoriji. Pa evo kako smo mogli stavi Pozdrav, da bude jasno. Ako sam upisali u Hello na redak. H-E-L-L-O backslash nula, završava unutar ti 12 bajtova, a mi smo super sigurno. Sve je dobro. Ali ako upišete nešto više, potencijalno je će se uvlače u razmaknice. Ali još gore, ispada sve ovo vrijeme, iako nikad nismo razgovarali o je, snop se koristi za druge stvari. To je ne samo lokalne varijable. 

C je vrlo niska razina jezika. I to vrsta potajno koristi snop također zapamtiti kada Funkcija se zove, ono je adresa od prethodne funkcije, tako da može skočiti natrag na tu funkciju. Dakle, kada glavni pozivi zamijeniti, među stvari gurnula na stog nisu samo swaps lokalne varijable, ili njegovi argumenti, također potajno gurnula na stog kao što je prikazano crveni kriška ovdje je adresa glavni fizički u memoriji računala, tako da kad zamjena je učinio, računalo zna Moram se vratiti u glavni i završiti izvršavanju glavnu funkciju. Dakle, to je opasno i sada, jer ako korisnik upisuje u i više od hello, kao da korisnikov unos clobbers ili prebrisati taj crveni dio, logično ako je računalo je Samo će slijepo pretpostaviti da bajtova u tom crvenom kriška su adresa na koju se treba vratiti, što ako protivnik je dovoljno pametan ili dovoljno sretan da stavi niz bajtova tamo izgleda kao adresu, ali to je adresa koda da on ili ona želi računalo izvršiti umjesto glavni? 

Drugim riječima, ako je ono što je Korisnik piše na upit, nije samo nešto bezazleno kao zdravo, ali to je zapravo kod koji je ekvivalent izbrisati sve ove korisnikovih datoteka? Ili e-mail lozinke za mene? Ili početi prijavom njihova tipke, zar ne? Postoji način, neka je propisano i danas, da bi mogli upisati ne samo pozdravi Svijet i njihovo ime, su mogli bitno proći kod, nula i one, da računalo grešaka za oba koda i adrese. Dakle, iako pomalo apstraktno, ako je korisnik upiše u dovoljno kontradiktornosti kod da ćemo generalizirati ovdje A. je napad ili protivnici. Dakle, samo loše stvari. Mi ne briga o brojeva ili nula ili one danas, tako da ćete završiti prepisati taj crveni dio, primijetiti da je slijed bajtova. O 835 C nula osam nula. I sada kao Wikipedia članak je ovdje predlaže, ako se sada zapravo početi označavanje bajtova u vašem računalu memorije, što je Wikipedia članak je predlaganje je da, što ako je adresa tog gornjem lijevom bajta je 80 ° C 0 3508. 

Drugim riječima, ako je negativac je dovoljno pametan sa svojim kodom zapravo staviti ovdje broj koji odgovara na adresu koda on ili ona ubrizgava u računalo, može izigrati računalo u radi ništa. Uklanjanje datoteka, slanje e stvari, njuškanje prometa, doslovno ništa mogao biti ubrizgava u računalo. I tako buffer overflow Napad u svojoj srži samo je glupo, glupo Najvažniji od niza koji nisu imali njegove granice provjeriti. I to je ono što je super opasan i istovremeno super moćan u C je da smo doista nemamo pristup bilo gdje u memoriji. To je do nas, programeri, koji pišu izvorni kod provjeriti duljinu darn bilo polja koje smo manipulira. Dakle, da bude jasno, što je popravak? Ako smo vratiti na ovo kod, ne samo treba promijenili duljinu trake, što inače bih se provjera? Što još trebam raditi na spriječilo ovaj napad u potpunosti? Ne želim da samo slijepo reći koje bi trebali kopirati što više bajtova kao što je dužina trake. Želim reći, kopirati kao mnogi bajtova što su u baru do dodijeljeni memorije, ili 12 maksimalno. Dakle, trebam nekakav ako stanje koji radi provjeriti duljinu trake, ali ako prelazi 12, samo tvrdi kôd 12 što u najvećoj mogućoj udaljenosti. Inače tzv pufer overflow napad može dogoditi. Na dnu tih slajdova, Ako ste znatiželjan to opširnije je stvarni izvorni članak Ako želite pogledati. 

Ali sada, među cijene plaćeni ovdje bio neučinkovitosti. Tako da je brz niska razina pogled na ono što problemi mogu nastati sada da smo imati pristup memoriji računala. No, još jedan problem smo Već je posrnuo u ponedjeljak je samo neučinkovitost popisa povezane. Mi smo natrag u linearnom vremenu. Mi više ne imati granični niz. Nemamo slučajni pristup. Ne možemo koristiti uglata zagrada zapis. Mi smo doslovno morati koristiti while petlja poput onoga što sam napisao maloprije. No, u ponedjeljak, tvrdili smo da možemo puzanje natrag u carstvo učinkovitosti postizanje nešto što je logaritamska možda, ili najbolje još, možda čak i nešto što je Takozvani konstanta vrijeme. Pa kako možemo učiniti da pomoću ove nove alati, ove adrese, ove naputke, i navoja stvari vlastitih? Pa, pretpostavimo da ovdje su hrpa brojeva koje želite pohraniti u Struktura i traženje podataka učinkovito. Mi apsolutno može premotati u tjedan dva, baciti ih u polje, te ih pretraživati ​​pomoću binarnog pretraživanja. Podijeli pa vladaj. A u stvari si napisao binarno pretraživanje u PSET3, gdje se provodi za traženje programa. Ali znate što. Postoji vrsta više pametan način za to. To je malo više sofisticiran i to možda omogućuje nam da vidimo zašto je binarni traži toliko puno brže. Prvo, neka je uvesti pojam stabla. Koji iako u stvarnost drveće vrsta rastu ovako, u svijetu računala znanost se vrsta raste prema dolje poput stabla, gdje imate Vaši djedovi ili bake i djedovi velik ili sitnica na vrhu, patrijarha i matriarch obitelji, samo jedan Takozvani korijen, čvor, ispod koji su njegovi sinovi, ispod kojeg su njegovi sinovi, ili njegovi potomci općenito. A tko visi dno obitelji stabla, osim što je najmlađi u obitelji, može biti samo generički zove lišće stabla. 

Dakle, ovo je samo hrpa riječi i definicija za nešto što se zove stablo u računalu znanost, baš kao obiteljsko stablo. No, tu je ljubitelj inkarnacija stabala, od kojih je jedan se zove pretraživanje po binarnom stablu. A možete vrsta zafrkavati Osim što je ova stvar radi. Pa, to je binarna u kojem smislu? Odakle binarni dolazi odavde? Žao nam je? To nije toliko bilo ili. To je još da svaki od čvorova nema više od dvoje djece, kao što smo vidjeli ovdje. Općenito, tree-- i tvoji roditelji i djedovi može imati onoliko djece ili grandkids što oni zapravo žele, pa primjerice tu imamo tri djeca gola koja desnoj čvor, ali u binarnom stablu, čvor ima nula, jedan ili dvoje djece najvi. I to je lijepo svojstvo, jer ako se to poklopi s dva, ćemo moći dobiti malo log bazu dva akcija događa ovdje u konačnici. Dakle, imamo nešto logaritamske. No, više o tome u ovom trenutku. Traži stablo znači da su brojevi postavljeni tako da lijevi djeteta vrijednost je veća od korijena. A svoje pravo dijete veći od korijena. Drugim riječima, ako se bilo što od čvorovi, krugovi u ovoj slici, i izgleda na svojoj lijevoj Dijete i njegova pravo djeteta, prvi bi trebao biti manji od, drugi bi trebao biti veći od. Dakle, razum provjeriti 55. To je napustio dijete je 33. To je manje od. 55, svoje pravo dijete 77. To je veći od. I to je rekurzivna definicija. Možemo provjeriti svaki od tih čvorovi i isti uzorak bi držati. 

Dakle, ono što je lijepo u pretraživanje po binarnom stablu, je da jedan, možemo ga provesti s STRUCT, baš kao i ova. I iako smo bacanje puno objekata na svoje, oni su nešto Sada intuitivno nadamo. Sintaksa je uvijek Arcane sigurno, ali sadržaj čvor u ovoj context-- i držimo koristim riječ čvor, da li je pravokutnik na zaslonu ili krug, to je samo neki generički kontejner, u ovom slučaju drvo, kao što je onaj Vidjeli smo, moramo cijeli broj u svakoj od čvorova a onda moram dva ptičara koji upućuju na lijevoj djeteta i pravo djeteta, respektivno. Dakle, to je kako bismo mogli provesti kako u Struct. A kako bi moglo da ga provede u kodu? Pa, neka je uzme brz pogledajte ovaj mali primjer. To nije funkcionalna, ali sam kopirati i zalijepiti tu strukturu. I ako moj funkcija za binarnom traži stablo zove pretraživanje, i to traje dva argumenta, cijeli broj N i pokazivač u čvor, pa pokazivač na stablu ili pokazivač na korijen stabla, Kako mogu ići o potrazi za N? Pa, prvo, zato što sam bave pokazivače, Ja ću učiniti ček razum. Ako stabla jednaka jednaka null, N u ovom stablu ili ne u ovom stablu? To ne može biti, zar ne? Ako sam pokraj null, nema ničega. Ja možda i samo slijepo reći return false. Ako mi ne daju ništa, ja sigurno ne mogu pronaći bilo koji broj N. Pa što drugi možda sam provjeri sada? Ja ću reći i drugo, ako je N manje nego ono što je na stablu čvor da sam bio predao N vrijednosti. Drugim riječima, ako je broj sam tražite, N, manji od čvora da gledam. A čvor tražim na se zove stablo, i sjećam iz prethodnog primjera dobiti na vrijednosti u pokazivač, Koristim strelicom zapis. Dakle, ako je N manji od stabla strelice N, želim konceptualno ide lijevo. Kako izražavam potrazi otišao? Da bude jasno, ako je to slika u pitanju, i ja sam prošao taj najviši strelica koja se pokazuje prema dolje. To je moje drvo pokazivač. Ja sam pokazujući na korijen stabla. I tražim recimo, za broj 44, proizvoljno. Je li 44 ili manje od veći od 55 očito? Tako da je manje od. I tako to, ako uvjet vrijedi. Pa koncepcijski, ono što želim Pretražite Sljedeći ako tražim 44? Da? 

Točno, želim Pretražite lijevu dijete, ili ulijevo pod-stablo ovu sliku. A u stvari, pustite me da prođem slika ovdje samo na trenutak, jer Ne mogu ispočetka ovo. Ako počnem ovdje u 55, i Znam da je vrijednost 44 Tražim je da lijeva, to je vrsta poput suzenje telefonski imenik u pola ili suzenje stabla na pola. Ja više ne moraju brinuti o Cijeli ovaj pola stabla. A ipak, začudo u smislu Struktura, ova stvar ovdje da počinje s 33, koji sebi je pretraživanje po binarnom stablu. Rekao sam da je riječ rekurzivna prije, jer Doista to je struktura podataka koji po definiciji je rekurzivna. Možda ste stablo koje je ovo velika, ali svaki od njegovih djece predstavlja stablo samo malo manji. Umjesto toga se djeda ili baka, sada je samo mama or-- Ne mogu ne say-- mama ili tata, koji će biti čudno. Umjesto dvoje djece tamo bi bilo kao brata i sestru. Nova generacija obiteljskog stabla. Ali strukturno, to je ista ideja. I ispada da imam funkciju s kojima mogu potražiti binarnu pretragu stablo. To se zove pretraživanja. Tražim N u stablo strelice lijevo inače ako je n veći od vrijednosti da sam trenutno. 55 u priči trenutak prije. Imam funkciju pod nazivom traži da ja mogu jednostavno prođe N ovo i rekurzivno pretragu pod-stablo i samo povratak što god da je odgovor. Inače imam neku konačnu bazu slučaj ovdje. 

Što je konačni slučaj? Stablo je bilo nula. Vrijednost sam bilo tražite manji od njega, ili veći od onog ili jednak tome. I moglo bi se reći jednaka jednaka, ali logično je ekvivalent za samo govoreći ostalo ovdje. Dakle, istina je kako sam naći nešto. Dakle, nadam se da je to još uvjerljiv primjer nego glupog funkciji sigma smo nekoliko predavanja natrag, gdje je jednako lako koristiti petlju brojati sve brojeve iz jednog N. ovdje sa strukturom podataka koja je sama po sebi rekurzivno definirati i rekurzivno nacrtana, sada smo imaju sposobnost da se izrazim u kodu koji je sam po sebi rekurzivna. Dakle, to je isti broj ovdje. 

Dakle, ono što drugi problemi mogu se riješiti? Tako brz korak od Stabla za samo trenutak. Evo, recimo, njemački zastavu. I tu je jasno Uzorak ovom zastavom. A tu je puno zastave u svijetu koji kao jednostavan kao ovaj u smislu njihovih boja i uzoraka. Ali pretpostavljam da je to čuvati kao .GIF Ili JPEG ili Bitmap ili ping, bilo grafički format datoteke s kojima ste upoznati, od kojih smo igranje s u PSET4. To se ne čini vrijedno pohraniti crna piksela, crne piksela, crne piksela, točka, točka, točka, cijela hrpa crni pikseli za prvi scanline, ili red, onda cijela hrpa isti, onda cijela hrpa istog, a zatim cijela hrpa crvenih piksela, crvena piksela, crvene piksela, onda cijeli gomila žutih piksela, žuta, zar ne? 

Postoji takva neučinkovitost ovdje. Kako biste intuitivno stisnuti njemačku zastavu ako ga provodi kao datoteku? Kao što informacije ne možemo gnjaviti spremanje na disk kako smanjiti našu veličinu iz poput megabajt u kilobajt, nešto manja? U kojoj leži zalihost Ovdje se jasno? Što možete učiniti? Da? Točno. Zašto se ne sjećam, a ne boja svakog piksela prokleto baš kao što radite u PSET4 s formatom bitmap datoteke, zašto jednostavno ne predstavljaju krajnjem lijevom stupcu piksela, primjerice hrpa crnih piksela, gomila crvene i hrpa žute, i onda samo nekako kodiraju Ideja Ponovite ovaj 100 puta ili ponovite 1000 puta? Gdje 100 ili 1000 je samo cijeli broj, pa vas može dobiti daleko sa samo jednim brojem umjesto stotina ili tisuća dodatnih piksela. I doista, to je kako smo mogao stisnuti njemačku zastavu. I A što je s francuskom zastavom? I malo neka vrsta mentalne vježbe, koja zastava može se sažeti više na disku? Njemačka zastava ili francuski zastava, ako uzmemo da je pristup? Njemačka zastava, jer je više horizontalna zalihost. I po dizajnu, mnogi grafički datotečni formati doista rade linije kao skeniranje vodoravno. Mogli su raditi vertikalno, samo čovječanstvo Prije odlučili godina da ćemo općenito mislim da stvari zaredom po red umjesto stupca strane stupca. Dakle, doista, ako ste bili pogledati datoteke Veličina njemačkom zastavom i francuski zastava, tako dugo dok je razlučivost isti, iste širine i visina, to je jedan Ovdje će biti veći, jer vas moraju sami ponoviti tri puta. Morate navesti plave, ponavljanje sebe, bijela, ponavljam se, crvena, Ponavljam se. Vi ne možete samo ići sve put u desno. I usput, da bi jasno kompresije je svugdje, ako su Četiri okviri iz video-- ste možda podsjetiti da je film ili video općenito kao i 29 ili 30 sličica u sekundi. To je kao malo flip knjigu u kojoj vas samo vidjeti slike, slike, slike, slike, Slika samo super brzo, tako da izgleda kao glumci na zaslonu se kreće. Evo bumbar na vrh hrpa cvijeća. I iako bi to moglo biti vrsta teško je vidjeti na prvi pogled, jedino što se kreće u ovaj film je pčela. 

Što je nijem o spremanju Video komprimirana? To je vrsta otpada za pohranu videa kao četiri gotovo identične slike koje razlikuju samo utoliko što, gdje pčela je. Možete baciti većinu tih informacija i zapamtiti samo na primjer, prvi okvir i posljednji kadar, Ključni okviri, ako ste ikada čuli tu riječ, i samo pohraniti u Srednji gdje pčela je. A vi ne morate pohraniti sve ružičastoj, i plava, a zelene vrijednosti kao dobro. Dakle, ovo je samo reći da Kompresija je posvuda. To je tehnika često se koriste ili uzeti zdravo za gotovo ovih dana. 

Ali kako stisnuti tekst? Kako idete o sažimanje teksta? Pa, svaki od likova u Ascii je jedan bajt ili osam bitova. I to je vrsta glupo, zar ne? Jer vjerojatno tip A i E i ja i O i U mnogo češće nego poput W ili P ili Z, ovisno o jeziku na kojem pišete sigurno. I zašto smo koristeći osam bitova za svaku riječ, uključujući najmanje Popularni slova, zar ne? Zašto ne koristiti manje bitova za super popularne slova, kao i E, ono što pretpostavljam prvi u Wheel of Fortune, i koristiti više bitova za manje popularne slova? Zašto? Jer samo ćemo se koristiti ih rjeđe. 

Pa, ispada da tamo ima bili pokušaji napravljeni da to učinite. A ako se sjećate iz razreda školu ili srednju školu, Morseov kod. Morseov kod ima točkice i crtice koje mogu biti prenosi duž žice kao zvukova ili signali neke vrste. No, Morseov kod je super čist. To je vrsta binarnog sustava da imate točkice ili crtice. Ali ako vidite, na primjer, dvije točkice. Ili ako mislite natrag operatera koji ide ovako bip bip, bip,, zvučni signal, udaranje malo okidač koji prenosi signal, Ako vi kao primatelj prima dvije točkice, koju poruku ste dobili? Potpuno proizvoljna. 

Ja? Ja? Ili što about-- ili ne? Možda je to samo dvije e je u pravu? Tako je ovaj problem od decodability s Morse kod, pri čemu osim ako Osoba slanja poruke zapravo zaustavlja tako da možete sortirati od vidjeti ili čuti razlike između pojedinih slova, to nije dovoljno samo pošalji strujom nula i jedinica, ili točkice i crtice, jer ima nejasnoća. E je jedna točka, pa ako vas vidjeti dvije točkice ili čuti dvije točkice, možda je dva E-a ili je to možda jedan I. Dakle, trebamo sustav koji je malo pametniji od toga. Dakle, čovjek po imenu Huffman godina Prije smislio upravo to. Dakle, samo ćemo uzeti brz pogled kako su stabla tijesnoj na to. Smatram da je to neki glupo poruku koju želite poslati, sastavljen od samo A, B, C je D's i E-a, ali ima puno redundancije ovdje. To nije značilo da se engleski. To nije šifrirana. To je samo glupa poruka s mnogo ponavljanja. Dakle, ako ste zapravo računati iz svih A-a, B-a, C-a, D's, i E je, ovdje je frekvencija. 20% od slova A je, 45% od slova su E, a tri druge frekvencije. Računali smo tamo ručno i upravo učinio math. 

Tako ispada da je Huffman, prije nekog vremena, shvatio da, znate ono, ako sam početi graditi drvo ili šumu stabala, ako hoćete, kao što slijedi, ja mogu učiniti sljedeće. Idem dati čvor na svakoj od pisama koje mi je stalo i ja ću za pohranu unutar tog čvora frekvencije kao pomičnim zarezom vrijednost, ili možete koristiti N, također, ali ćemo samo koristiti plovak ovdje. A algoritam koji predložio je da se iskoristiti ovu šumu jednog čvora stabla, tako super kratke stabala, i početi ih povezuje s nove skupine, novi roditelji, ako će. A vi to učiniti odabirom Dva najmanja frekvencija u isto vrijeme. Zato sam uzeo 10% i 10%. Ja stvoriti novi čvor. I ja nazivam novi čvor 20%. 

Koje dvije čvorovi sam kombinirati sljedeće? To je malo nejasan. Dakle, postoji neki kutak slučajeve uzeti u obzir, ali da bi stvari lijepe, Idem odabrati 20% - Sada ignorirati djecu. Idem izabrati 20% i 15% i nacrtati dvije nove rubove. I sad su dva čvora ja logično kombinirati? Zanemari sve djece, sve unuci, samo pogledajte korijenima Sada. Koje dvije čvorovi mogu povezati? Točka dva i 0,35. Pa neka mi nacrtati dvije nove rubove. A onda sam dobio samo jedan lijevo. Dakle, ovdje je drvo. I to je bio nacrtan namjerno gledati vrsta lijepa, ali primijetiti da rubovi moraju Također su označeni nula i jedan. Dakle, svi su napustili rubova su nula proizvoljno, ali dosljedno. Sve desni rub su one. 

I tako ono što Hoffman predložio je, Ako želite predstavlja B, umjesto predstavlja broj 66 kao ascii što je osam cijeli bita, Znaš što, samo dućan uzorak nula, nula, nula, nula, jer to je put iz mog stabla, gospodina Huffman je stablo, na list iz korijena. Ako želite pohraniti E, s druge strane, ne pošalji osam bitova koji predstavljaju E. Umjesto toga, pošaljite što uzorak bitova? Jedna. A što je lijepo o tome da e je najpopularniji pismo, i da ste korištenjem Najkraći kod za to. Sljedeći najpopularniji Pismo izgleda kao da je A. I tako koliko bitova je on predlaže pomoću za to? Nula, jedan. 

I zato što je proveden kao ovog drveta, za sada neka mi propisuje postoji nema dvosmislenosti kao u Morse broj, jer je sve od slova stalo su na kraju tih rubova. Dakle, to je samo jedan Primjena stabla. Ovaj is-- a ja ću mahati moja ruka na to kako vas Možda provesti ovo kao C strukture. Mi samo trebate kombinirati simbol, poput char, a učestalost u lijevo i desno. Ali pogledajmo dva Konačni primjeri koje ćete dobiti prilično upoznat s poslije Kviz nula u problemu postaviti pet. 

Tako da je struktura podataka poznat kao hash tablicu. I hash tablica je vrsta hladiti da se posude. I pretpostavimo da postoji četiri kante Ovdje, samo četiri razmaci. Evo špilom karata, a ovdje se klub, Spade, klub, dijamanti, klub, dijamanti, klub, dijamanti, clubs-- pa to je slučajan. Srca, hearts-- pa sam bucketizing sve ulaza ovdje. I šifriran tablice potrebe gledati na svoj ulaz, a zatim ga staviti u neki staviti na temelju onoga što vidite. To je algoritam. I ja sam bio koristeći super Jednostavan vizualni algoritam. Najteži dio koji je bio prisjećajući se što su slike bile. A tu je i četiri ukupno stvari. 

Sada hrpe su rasle, što je namjerno dizajn stvar ovdje. Ali, što drugo bi moglo da radim? Tako zapravo ovdje imamo hrpa starih škola ispita knjigama. Pretpostavimo da je hrpa studenti su imena ovdje. Evo veći hash tablicu. Umjesto četiri kante, Ja sam, recimo 26. I nismo htjeli ići posuditi 26 stvari iz vanjskog [? Annenberg?], Tako da evo pet koje predstavljaju A do Z. I ako ja vidi student čije ime počinje sa A, Idem s njegovim kviz stavio tamo. Ako netko počne s C, tamo, A- zapravo, nije htio učiniti. B ide ovamo. Tako sam dobio A i B i C. A Sada ovdje je još jedan student. No, ako je to hash tablica provode s nizom, Ja sam vrsta pijan u ovom trenutku, zar ne? Ja vrsta morati staviti ovaj negdje. 

Tako je jedan od načina da se riješi ovo je sve pravo, zauzet, B je zauzet, C je zauzet. Ja ću ga staviti u D. Dakle, na Prvo, imam slučajnim brz pristup da svaki od kante za studente. Ali sada je to vrsta devolved u nešto linearno, jer ako želim tražiti nekoga čije ime počinje sa A, sam provjeriti ovdje. No, ako to nije A Student Tražim, Ja vrsta početi provjeru su kante, jer ono što sam učinio je vrsta linearno istražiti strukturu podataka. Glupi način govoreći samo pogledajte prvi dostupnih otvaranja, i staviti kao plan B, da se tako izrazim, ili plan D, u ovom slučaju, vrijednost na tom mjestu umjesto. To je samo tako da ako ste dobio 26 mjesta i bez studente s imenom Q ili Z, ili nešto slično da, barem da koristite prostor. 

No, već smo vidjeli više pametan rješenja ovdje, zar ne? Što biste učinili umjesto Ako imate sudar? Ako dvije osobe imaju naziv A, što bi bio pametniji ili više intuitivno rješenje nego samo Stavljanje gdje je D trebao biti? Zašto ne bih jednostavno otići izvan [? Annenberg?] poput malloc, drugi čvor, stavi ga ovdje, a zatim staviti da student ovdje. Tako da sam u biti ima neka niza, ili možda i više elegantno kao da smo počinju vidjeti popis povezane. 

I tako hash tablicu je struktura koji bi mogao izgledati upravo ovako, ali više pametno, te nešto što se zove odvojeni ulančavanje, pri čemu hash tablicu jednostavno je niz, svaki od čije elemente nije broj, je sam popis povezani. Tako da dobijete super brzo pristupa odlučivanja gdje hash svoju vrijednost na. Slično kao s kartice, primjerice, Napravio sam super brze odluke. Hearts ide ovdje, dijamanti ide ovdje. Isto ovdje, A ide ovdje, D ide ovdje, B ide ovdje. Dakle, super brzo izgled-up, a ako vam se dogoditi da se izvoditi u slučaju gdje Imaš sudari, dva ljudi s istim imenom, ali onda vi samo početi povezuje ih zajedno. A možda bi ih razvrstani abecednom redu, možda ne. Ali barem sada imamo dinamiku. Dakle, s jedne strane imamo super brzi vremenska konstanta, a vrsta linearnog vremena uključena, ako ovim povezanim popisima početi da se malo dugo. 

Dakle, ova vrsta glup, štreberski vic godina. Na CS50 hack-a-Thon, kada učenici check in, Neki TF ili CA svake godine misli da je smiješno da se stavi znak kao što je ovaj, gdje je samo znači ako je vaše ime počinje sa A, ići na ovaj način. Ako vaše ime počinje s B, idite this-- redu, to je smiješno možda kasnije u semestru. No, tu je još jedan način za to, previše. Vratite se na to. 

Tako je ova struktura. A ovo je naša posljednja Struktura za danas, što je nešto što se zove Trie. T-R-I-e, koji je iz nekog razloga je kratka za dohvat, ali to se zove Trie. Tako Trie je još jedan zanimljiv amalgam puno tih ideja. To je stablo, koje smo vidjeli. Nije pretraživanje po binarnom stablu. To je stablo s bilo kojim brojem djece, ali svaki od djece u Trie je niz. Niz veličine, kažu, 26 ili možda 27 Ako želite podržati crticu imena ili apostrofe u ljudi imena. 

I tako je to struktura podataka. A ako pogledate odozgo do dna, kao i ako pogledajte gornjem čvoru tamo, M, je ukazujući na krajnjem lijevom stvar postoji, koji se zatim su A, X, W, E, L, L. To je samo struktura podataka koja samovoljno je spremanje imena ljudi. I Maxwell se pohranjuje samo nakon put od polja do polja na polje. No, ono što je nevjerojatna o Trie je da, dok je popis povezanih, pa čak i niz, najbolji smo ikada stečen je linearno vrijeme ili logaritamska vremena u potrazi netko gore. U ovom struktura podataka, ako Trie moja struktura podataka ima jedno ime u njemu i ja sam u potrazi za Maxwell, ja sam će ga pronaći prilično brzo. Upravo sam u potrazi za M-A-X-W-E-L-L. Ukoliko ova struktura podataka, za razliku od, ako je N milijun, ako postoji Milijun imena u ovoj strukturi podataka, Maxwell i dalje će biti otkriti nakon samo M-A-X-W-E-L-L koraka. A David-- D-A-V-I-D koraka. Drugim riječima, gradeći struktura podataka koji je nema a svi od ovih polja, sve uzdržavati slučajni pristup, Mogu početi gleda gore Narodne ime koristite količinu vremena koja je proporcionalna ne po broju stvari u strukturi podataka, Poput milijuna postojećih imena. Iznos od vrijeme koje je potrebno mi je naći M-A-X-W-E-L-L u ovoj strukturi podataka je proporcionalna ne na Veličina strukture podataka, ali na duljinu imena. A realno imena što smo se gleda se nikada ne će biti ludi dugo. Možda netko ima 10 karaktera ime, ime 20 znakova. To je svakako konačni, zar ne? Tu je čovjek na Zemlji, koji ima najdulji mogući naziv, ali to ime je konstanta Duljina vrijednost, zar ne? To ne razlikuju u bilo kojem smislu. Dakle, na ovaj način, mi smo postigla strukturu podataka da je vremenska konstanta pregledna. To ne uzeti broj koraka ovisno o dužini unosa, ali ne i broj imena u podatkovnoj strukturi. Dakle, ako ćemo udvostručiti broj imena sljedeće godine od milijardu do dvije milijarde, Nalaz Maxwell će potrajati točno isti broj sedam koraka ga naći. I tako mi se čini da su postigli naš sveti gral trčanje vremena. 

Dakle, par brzih najave. Kviz nula dolazi. Više o tome na stranicama tijeku je u narednih nekoliko dana. Ponedjeljak lecture-- to je odmor ovdje na Harvardu u ponedjeljak. To nije u New Havenu, tako da smo uzimajući klase New Haven za predavanje u ponedjeljak. Sve će biti sniman i streamed uživo, kao i obično, ali neka je danas završava s druge isječak 30 pod nazivom "Deep misli" po Daven Farnham, koji je inspiriran prošle godine u subotu Night Live-a "Deep misli" Jack pri ruci, što Sada bi trebalo smisla. 

FILM: A sada, "Deep Misli "od Daven Farnham. Hash tablica. 

SPEAKER 1: Dobro, to je to za sada. Vidimo se sljedeći tjedan. 

Doug: Da biste ga vidjeli u akciji. Tako ćemo pogledati kako upravo sada. Dakle ovdje imamo nesortiranog niz. 

IAN: Doug, možete ići naprijed i ponovno pokretanje to za samo jednu sekundu, molim. U redu, kamere su valjanje, pa akcija kad god ste spremni, Doug, u redu? Doug: U redu, tako da ono što smo imamo ovdje je Nesortirano polje. I ja sam boji sve elemente crveno što znači da je, u stvari, nesortiran. Tako podsjetiti da je prva stvar koju radimo je smo sortirali utakmice polovicu polja. Onda smo sortirali pravo polovica polja. A ya-da, ya-da, ya-da, možemo ih spojiti zajedno. I imamo potpuno sortirani niz. Dakle, to je kako spojiti vrsta radova. 

IAN: Joj, joj, joj, cut, cut, cut, cut. Doug, ne možeš samo ya-da, ya-da, ya-da, svoj put kroz spajanje vrste. 

Doug: Upravo sam učinio. U redu je. Mi si dobar to ići. Ajmo zadržati valjanje. Pa ipak, 

IAN: Morate objasniti što potpunije od toga. To jednostavno nije dovoljno. Doug: Ian, mi ne morate se vratiti na jedan. U redu je. Pa ipak, ako nastavimo s merge-- Ian, mi smo usred snimanja. 

IAN: Znam. A mi ne možemo samo ya-da, ya-da, ya-da, kroz cijeli proces. Morate objasniti kako Dvije strane se spojene zajedno. 

Doug: Ali mi smo već objasnio kako dvije sides-- 

IAN: Upravo ste prikazano ih spajanje polje. Doug: Znaju proces. Oni su u redu. Mi smo otišli preko njega deset puta. 

IAN: Vi samo preskočila pravo nad njom. Vraćamo se na jednu, što Ne možeš ya-da, ya-da preko njega. Dobro, natrag u jedan. 

Doug: Moram se vratiti kroz sve slajdove? O moj Bože. To je kao šesti put, Ian. U redu je. 

IAN: U redu. Spreman? Veliki. Akcija.