SPEAKER 1: V redu, tako da je to CS50 To je konec petih teden. In opozarjajo, da zadnji čas smo začeli iskati na Ljubitelj podatkov strukture, ki so se začeli reševati Težave, ki so se začeli, da uvede novi problemi, vendar je ključnega pomena, da je to je vrsta navojev, da smo začel delati od vozlišča do vozlišča. Torej, to je seveda za enkrat povezani seznam. In posamezno povezana, Mislim, da je samo ena nit med vsemi temi vozlišč. Izkazalo se je, lahko storite Ljubitelj stvari, kot so dvojno povezanih seznamov s katerim imate puščico gre v obeh smereh, ki lahko pomaga z določenimi učinkovitosti. Toda to rešiti problem? Kaj je problem je to rešiti? Zakaj smo mar v ponedeljek? Zakaj, v teoriji, ni mi mar v ponedeljek? Kaj počne? 

OBČINSTVO: Mi lahko dinamično velikost. 

SPEAKER 1: OK, tako da bomo lahko dinamično velikost. Dobro opravljeno oba. Tako da lahko dinamično spreminjanje velikosti to podatkovna struktura, medtem ko je niz, odpoklic, moraš vedeti priori, koliko prostora želite in če boste potrebovali malo več prostor, da ste nekako od sreče. Boste morali ustvariti povsem novo paleto. Moraš se premakniti vse vaše podatki iz ene v drugo, sčasoma sprostiti staro paleto če lahko, in nato nadaljujte. Ki le počuti zelo drago in zelo neučinkovito, in dejansko je mogoče. Toda to še ni vse dobro. Smo plačali ceno, kar je bil eden bolj očitne cen smo plačilo z uporabo povezani seznam? 

OBČINSTVO: moramo uporabiti dvojni prostor za vsakega od njih. SPEAKER 1: Ja, zato moramo vsaj dvakrat toliko prostora. V bistvu, sem spoznal, ta slika je celo malo zavajajoče, ker na CS50 IDE v veliko moderno računalniki, kazalec ali naslov dejansko ni štirimi zlogi. To je zelo pogosto ti dni osem bajtov, ki pomeni dno najbolj pravokotniki tam v resnici so vrste dvakrat velik kot tisto, kar sem sestavljen, kar pomeni, da ste z uporabo trikrat toliko prostora, kot bi imeli drugače. Sedaj istočasno, da smo Še vedno govorimo bajte, kajne? Mi ni nujno, da govorimo megabajtov ali gigabajtov, če teh podatkov strukture dobil velik. 

In tako smo danes začeli obravnavati kako bi lahko razišče podatke bolj učinkovito, če pri Dejstvo podatki gets večji. Ampak poskusimo kanoniziran operacije prvih ki jih lahko naredite na teh vrste podatkovnih struktur. Torej nekaj podobnega, povezane seznam splošno podpira Operacije želeli izbrisati, vstaviti, in iskati. In kaj mislim s tem? To samo pomeni, da je običajno, če ljudje uporabljajo povezani seznam, sami ali nekdo drug je izvajala Funkcije, kot so brisanje, vstavljanje, in iskanja, tako da boste lahko dejansko nekaj storiti koristno s strukturo podatkov. Torej, kaj je na hitro pogledamo kako lahko izvajamo nekatere kodirajo za povezani seznam, kot sledi. 

Torej, to je le nekaj C kodo, ni niti celoten program da sem res hitro podžigal. To ni na spletu v distribuciji Koda, saj ne bo dejansko vozijo. Ampak opazila sem pravkar s komentar dejal, dot dot dot, da je nekaj tam, dot dot dot, nekaj tam. In kaj je samo pogled na kaj sočno deli. Torej, on-line tri, opozarjajo, da je to zdaj Predlagali smo razglasitvi vozlišče zadnji Čas, eden izmed teh pravokotnih predmetov. Ima int da bomo klic N, vendar bi lahko rekli, da je vse, in takrat imenovana struct vozlišče zvezda naslednjič. In samo zato, da bo jasno, da drugi linija, na vrstnim šestvaljnikom, kaj je to? Kaj je delal za nas? Ker je zagotovo izgleda bolj Grobni od naših običajnih spremenljivk. 

OBČINSTVO: To omogoča, da se premaknete v enem. 

SPEAKER 1: To omogoča, da se premaknete v enem. In če smo natančnejši, bo shranite naslov vozlišča, ki je pomenilo, da je semantično zraven njega, kajne? Tako da je ne bo nujno premakniti ničesar. To je le, da bo shraniti vrednost, ki je bo naslov neke druge vozlišča, in da je, zakaj smo dejal struct vozlišče zvezda, zvezda označuje kazalec ali naslov. OK, tako da zdaj, če predpostavimo, da imamo To N nam na voljo, in ne dovolimo, predpostavimo, da ima nekdo drug vstavi cel kup števil v povezani seznam. In to povezano seznam je poudaril, da ga neki točki spremenljivka imenovan Seznam A, ki je opravil sem kot parameter, Kako naj grem o skladu 14 izvedbenih iskanju? Z drugimi besedami, če sem izvedbenih funkcija, katere namen v življenju je, da int in nato začetek povezanega seznama, da je kazalec na povezani seznam. Tako kot prva, ki mislim, da Davida je bila naša prostovoljka v ponedeljek, je bil obrnjen na celoten povezani seznam, to je, kot da smo mimo David v kot naš argument tukaj. Kako bomo šli o prečkajo ta seznam? No, izkaže se, da čeprav kazalci so relativno nova sedaj za nas, bomo lahko to storili relativno naravnost. 

Grem, da gredo naprej in prijavijo začasno spremenljivko, ki po dogovoru se le, da bo da se imenuje kazalec, ali PTR, ampak jo lahko imenujemo kar hočeš. In bom za inicializacijo je na začetku seznama. Torej si lahko nekako misli o tem Kot mi je učitelj drugi dan, nekako kaže na nekoga med našimi ljudmi kot prostovoljci. Tako da sem začasno spremenljivko, ki je samo kaže na isto stvar da je naš naključno imenovan prostovoljec David je tudi poudaril. Zdaj, ko kazalec ni nič, ker odpoklic da null je nekaj posebnega sentinel vrednost razmejuje konec seznama, Torej, medtem ko jaz ne pokaže na tla kot naš zadnji prostovoljec je, pojdimo naprej in storite naslednje. Če pointer-- in zdaj sem nekako želim da to, kar smo naredili z učencem če structure-- kazalec dot Naslednja equals-- raje, če kazalec dot N enaka enak spremenljivka N, pri Argument, ki je bila sprejeta leta, potem hočem iti naprej in pravijo, vrne true. Ugotovil sem, da številko N notranjost eden od vozlišča moj povezani seznam. Toda pika ni več dela v zvezi s tem, ker je kazalec, PTR, je res kazalec, naslov, smo dejansko lahko čudovito uporabite končno kos sintakse da vrsta znamk intuitiven občutek in dejansko uporabite puščico tukaj, kar pomeni, da gredo od da je naslov za celo tam leta. Torej, to je zelo podobna duh upravljavcu dot, ampak zato, ker kazalec ni kazalec in ne sam po sebi dejansko struct, smo samo uporabo puščico. 

Torej, če je trenutno vozlišče, da sem se začasna spremenljivka, sem gledala ni N, kaj hočem narediti? No, z mojo prostovoljcih da smo imeli tukaj, drugi dan, če je moj prvi človek ni tisti, ki sem želijo, in morda drugi človek ni tista želim, in tretje, sem potreba, da se fizično premikajo. Like kako stopim skozi seznamu? Ko smo imeli paleto vas, pravkar storil, kot sem plus plus. Toda v tem primeru zadostuje, da storiti kazalec, dobi, kazalec, naslednji. Z drugimi besedami, naslednji polje je, kot vse leve roke da naše človeške prostovoljci v ponedeljek so bili z uporabo opozoriti na neko drugo vozlišče. Tisti, ki so bili njihovi naslednji sosedje. 

Torej, če želim stopiti skozi ta seznam, Ne morem storiti jaz plus plus več, Jaz namesto reči I, kazalec, se dogaja da enako ne glede na naslednjo polje, Naslednji polje, naslednji polje, po vseh teh leve roke da smo imeli na odru kazala z nekaterimi poznejšimi vrednosti. In če sem priti skozi da celotna ponovitev, in končno, sem udaril null nimajo Najdenih N še, pravkar sem return false. Torej še enkrat, vse, kar delamo tukaj, kot na sliki pred nekaj trenutki, se začenja z opozorilom Na začetek seznama verjetno. In potem sem preveriti, je vrednost Iščem enaka devet? Če je tako, se vrnem true in sem naredil. Če ne, bom posodobiti svojo roko, AKA kazalec na točko na lokaciji naslednji puščica je, in nato lokacija naslednjega puščica je, in dostavo. Jaz sem preprosto hojo skozi ta niz. 

Torej še enkrat, koga briga? Všeč, kaj je to sestavina za? No, opozarjajo, da smo uvedli pojem dimnika, ki je abstrakten podatkovni tip, kolikor je to ni C stvar, to ni CS50 stvar, to je abstraktna ideja, ta ideja zlaganje stvari na vrhu med seboj ki jih je mogoče izvajati grozde različne načine. In en način, smo predlagali, je bila z niz, ali povezanega seznama. In se izkaže, da je kanonično, A Snop podpira vsaj dve operaciji. In buzz besede potisni, da potisnite nekaj na kupu, kot nov pladenj v jedilnica, ali pop, kar pomeni, da se odstranijo vrhunskih pladenj iz dimnika v jedilnico dvorana, nato pa morda nekaj drugi postopki, kot dobro. Torej, kako lahko definiramo strukturo da smo zdaj kliče kup? 

No, imamo vse zahtevano skladnja so nam na voljo v C. rečem, dajte mi definicijo tipskega struct notranjosti dimnika, Jaz bom rekel, je matrika odsvojila cel kup številk in nato velikosti. Torej, z drugimi besedami, če želim izvajati to v kodi, Naj gredo in šele nekako pripraviti, kaj je to rekel. Torej, to je rekel, daj mi struktura, ki je dobil niz, in ne vem, kaj zmogljivost, to je očitno nekaj konstanta, ki sem jih opredeljena drugje, in da je v redu. Ampak predvidevam, da je samo ena, dva, tri, štiri, pet. Torej zmogljivost je 5. Ta element znotraj my struktura se bo imenoval številke. In potem moram eno druga spremenljivka očitno imenuje velikost, da najprej grem določiti, se ponastavi na nič. Če ni nič v Sveženj, znaša nič, in to je smeti vrednosti v številkah. Nimam pojma, kaj je tam samo še. 

Torej, če želim push nekaj na kupu, Domnevam kličem funkcijo Pritisni in Pravim potiskanje 50, kot številko 50, kjer bi predlagali Sem ga pripravi na tem polju? Obstaja pet različnih možnih odgovorov. Kam želite push številko 50? Če je cilj tukaj, ponovno, pokličite funkcija Push, prenese v argument 50, kje sem ga dal? Pet possible-- 20% možnosti, ugibanja pravilno. Ja? 

OBČINSTVO: Far desno. 

SPEAKER 1: Far desno. Zdaj je 25% možnosti, ugibanja pravilno. Tako da bi dejansko bilo v redu. Po dogovoru, bom rekel, s paleto, mi bi običajno začnejo na levi strani, vendar smo lahko zagotovo začeti na desno. Tako da bi spojler tukaj lahko sem verjetno bo, da ga pripravi na levi strani, Tako kot v normalnem matrika, kjer Začnem na levo proti desni. Ampak, če ste lahko flip aritmetična, v redu. To preprosto ni običajna. OK, moram narediti eno več sprememb, čeprav. Zdaj, ko sem potisnil nekaj na kupu, kaj je naslednje? 

V redu, moram prirastek velikost. Zato mi dovolite, pojdi naprej in le posodablja, ki je enak nič. In namesto da bi zdaj, bom dati v vrednosti enega. In zdaj, da sem potiskanje drugega Številka na kupu, kot 51. No, moram narediti eno bolj Sprememba, ki je do velikosti dveh. In potem, da sem potisnite enega več Številka na kupu, kot 61, Zdaj moram posodobiti velikosti ena čas, in dobili vrednost 3, kot velikosti. In zdaj, da sem poklical pop. Zdaj pop, po dogovoru, ne bo argument. Žetonov, celotno točka pladnja metafore je, da ne boste imeli diskrecijsko pravico iti dobili ta pladenj, vse, kar lahko storite je pop vrhunsko enega iz Sveženj, samo zato, ker. To je tisto, kar ta struktura podatkov počne. 

Torej s to logiko, če sem pravijo, pop, kaj prihaja off? Torej 61. Torej, kaj je res računalnik storili v spomin? Kaj moja koda morate storiti? Kaj bi predlagali spremenimo na zaslonu? Kaj bi spremenili? Žal? Torej bomo znebili 61. Tako sem lahko zagotovo to. In se ne morem znebiti 61. In potem kaj drugega Sprememba se mora zgoditi? Velikost je, da se vrnete na dva verjetno. In tako, da je v redu. Toda počakaj minuto, velikost pred nekaj trenutki je bil tri. Kaj je samo naredil preverjanje hitro prištevnosti. Kako pa vemo, da želel, da se znebite 61? Ker smo živahen. In zato imam to drugo velikost lastnine. 

Čakaj malo, jaz sem razmišljal nazaj na dva tedna ko smo začeli govoriti o polja, kjer je bila ta lokacija nič, to je bila lokacija ena, je bila ta lokacija dva, to je lokacija tri, štiri, Izgleda, da je razmerje med velikostjo in element, da želim, da se odstranijo Iz matrike zdi, da samo se kaj? Velikost minus ena. In da je, kako kot ljudje vemo, 61 na prvem mestu. Kako je računalnik bo vedel? Ko kodo, kjer vas verjetno želite narediti velikost minus ena, tako tri minus ena je dva, in da pomeni, da smo želeli, da se znebite 61. In potem bomo lahko dejansko posodobiti velikost, tako da je velikost zdaj gre iz treh na samo dva. In samo, da je občutljiv, bom predlagati, da sem naredil, kajne? Ste predlagali intuitivno pravilno sem se moral znebiti 61. Ampak še nisem nekako nekako gotten znebite 61? Sem dejansko pozabljena da je dejansko tam. In pomislite na PSET4, če ste prebrali članek o forenziki, PDF da smo imeli vi prebrali, ali ste bo prebral ta teden PSET4. Spomnimo se, da je to pravzaprav germane za celotna ideja računalniške forenzike. Kakšen računalnik splošno pa je to samo pozabi, kje je kaj, vendar ne gredo v in podobno poskusite praska ven ali prekrmiljenje ti bitov z ničel in enic ali kakšno drugo naključno vzorec če ste sami storijo namenoma. Torej, vaša intuicija je bila Dobro, dajmo znebiti 61. Toda v resnici, mi ne bo treba ukvarjati. Vedeti pa je treba, da pozabimo, da da je tam s spremembo velikosti. 

Zdaj pa je problem s tem kupu. Če Držim potiska stvari na kupu, kar je Očitno se bo zgodilo v samo nekaj trenutkov časa? Bomo zmanjkalo prostora. In kaj naj naredimo? Mi smo nekako zajebali. To izvajanje ne pusti nam spremenite velikost array, saj s pomočjo to sintakso, če vas pomislite na dva tedna, ko ste razglašen velikost matrike, nismo videli mehanizem še kje lahko spremenite velikost polja. In res C nima te funkcije. Če rečeš mi daš pet Nths, pravijo številke, da je vse, kar boš dobil. Tako smo zdaj od ponedeljka, imajo sposobnost izražanja rešitev čeprav smo morali poteg opredelitev našega dimnika da ne bodo nekateri težko kodirane-matrika, ampak samo za shranjevanje naslov. 

Zdaj zakaj je to? Zdaj bomo morali biti zadovoljni s dejstvo, da se, ko je moj program teče, Jaz sem verjetno bo morali vprašati človeka, koliko številk ne želite shraniti? Tako da je vhod mora priti od nekje. Toda, ko sem vedel, da številko, potem sem lahko samo uporabite tisto, kar deluje, da bi mi kos pomnilnika? Lahko uporabite malloc. In lahko rečem, poljubno število bajtov hočem nazaj za te Nths. In vse, kar imam za shranjevanje v številkah spremenljivka tu notri te struct bi moralo biti, kaj? Kaj pravzaprav gre v Številke v tem scenariju? Ja, kazalec na prvi bajt ta kos pomnilnika, ali natančneje, naslov prve od teh bajtov. Ni važno, če je to eno Byte ali milijarda bajtov, Moram skrbeti za prvega. Ker kaj malloc jamstva in moje operacijskega sistema jamstva, je, da je kos pomnilniški I razumem, da se dogaja, da se stikata. Tam je ne bo vrzeli. Torej, če sem prosil za 50 bajtov ali 1000 bajtov, oni vse bo back to back to back. In tako dolgo, kot se spomnim, kako velik, kako veliko Prosil sem za, vse, kar morate vedeti je prvi tak naslov. 

Torej, zdaj imamo možnost, v kodi. Čeprav, to se dogaja, da nas bo več časa za to napisati, smo zdaj lahko prerazporedi ta pomnilnik, ki ga Samo shranjevanje drug naslov tam če želimo večji ali celo manjši kos pomnilnika. Torej, tukaj na kompromis. Zdaj smo dobili dinamiko. Še vedno imamo contiguousness sem trdijo. Saj nam bo malloc dal stičen kos pomnilnika. Ampak to se dogaja, da je bolečina v vrat za nas, programer, dejansko kodo gor. To je samo več dela. Potrebujemo kodo, ki spominja na to, kar sem poriva ven pred nekaj trenutki. Zelo izvedljivo, vendar dodaja kompleksnost. In tako, ko razvijalec, programer Čas je še en vir da bomo morda morali porabiti nekaj časa, da bi dobili nove funkcije. In potem seveda ni čakalne vrste. Mi ne bo šel v to eno v veliko podrobnosti. Ampak to je zelo podobno v duhu. Jaz bi izvajati čakalne vrste, in njeni ustrezni postopki, enqueue ali dequeue, kot dodajanje ali odstranjevanje, to je samo Ljubitelj način je rekel, enqueue ali dequeue, kot sledi. Jaz lahko samo dam struct ima ta spet številko na paleto, je, da ponovno velikost, ampak zakaj jaz zdaj potrebujem slediti sprednji čakalne vrste? Nisem vedeti sprednji del mojega dimnika. No, če sem spet za queue-- kaj je samo težko to kodo, da ima kot pet cela v tu potencialno. Torej to je nič, ena, dva, tri, štiri. To se bo imenovane spet številke. In to se bo imenoval velikost. 

Zakaj je ne zadostuje da imajo le velikost? No, pa potisnite te iste številke naprej. Tako sem pushed-- sem enqueued, ali potiska. Zdaj bom enqueue 50, in nato 51, nato 61 in dot dot piko. Tako da je enqueue. Enqueued sem 50, nato 51, nato 61. In da izgleda enako na kup tako daleč, razen mi morali narediti eno spremembo. Moram posodobiti te velikosti, tako da sem šel od nič do enega do dva do tri sedaj. Kako dequeue? Kaj se zgodi z dequeue? Kdo naj sname ta seznam prvič če je to črta na Apple Store? Torej 50. Torej, to je nekako težje tokrat. Ker zadnjem času je bilo super enostavno pač velikost minus ena, Pridem do konca mojega paleto učinkovito kjer so številke, odpravlja 61. Ampak jaz ne želim odstraniti 61. Želim, da bi 50, ki je bil tam ob 5:00 line up za Novi iPhone ali malenkosti. In tako, da se znebite 50, I To preprosto ne more storiti, kajne? Znam prečrtati 50. Vendar smo pravkar rekel, da smo Ne biti tako analni kot praska ven ali skrivanje podatkov. Mi lahko samo pozabil, kje je. 

Ampak, če spremenim velikost zdaj dva, je to dovolj informacij vedeti, kaj se dogaja v moji vrsti? Niti ne. Tako kot moja velikost je dva, ampak kjer se čakalne vrste začne, še posebej, če sem še vedno te iste številke v pomnilniku. 50, 51, 61. Tako da moram zapomniti Sedaj, ko je spredaj. In tako kot sem predlagal gor tam, bomo pravkar poklical N spredaj, katerega začetna vrednost bi morala biti, kaj? Nič, samo začetek seznama. Toda zdaj poleg pomanjšanja velikost, smo pravkar prirastek spredaj. Zdaj tukaj je še en problem. Torej, ko sem se vedno dogaja. Recimo, to je število kot 121, 124 in nato, prekleto, Sem zmanjkalo prostora. Toda počakaj malo, nisem. Tako da na tej točki v zgodbi, Predpostavimo, da je velikost ena, dva, tri, štiri, tako predpostavimo, da je znaša štiri, prednja je on, tako 51 je na sprednji strani. Rad bi dal še eno številko tukaj, ampak, prekleto, da sem ven iz prostora. Ampak jaz nisem res, kajne? Kje bi jaz dal nekaj dodatno vrednost, kot je 171? Ja, jaz bi samo nekako pojdi nazaj tja, kajne? In potem prečrtati 50, ali samo prepisati s 171. In če ste se spraševala, zakaj naše številke dobil tako naključno, ti so pogosto sprejeti računalnik znanost tečaji na Harvardu po CS50. Ampak to je bila dobra optimizacija, ker zdaj ne bom zapravljam prostor. Še vedno moram zapomniti kako velika je ta stvar je skupna. To je pet skupaj. Ker ne želim, da začetek prepisovanju 51. Torej, zdaj sem še vedno zmanjkalo prostora, tako isti problem kot prej. Vendar pa lahko vidite, kako zdaj v kodi, boste verjetno morali napisati malo bolj kompleksnost, da to uresničimo. In v resnici, kaj operater v C verjetno lets si čudežno to krožnost storiti? Ja upravljavec modulo, odstotek znamenje. Torej, kaj je nekako kul o vrsti, čeprav smo ostali risanje nize saj te, kot ravnih črt, če vas nekako razmišljam o tem, kot krivljenje okoli kot kroga, potem samo Intuitivno to nekako deluje duševno Mislim, da je malo bolj čisto. Ti bi še vedno morali izvajati da je duševno model v kodi. Torej ni tako težko, na koncu, izvajanje, vendar smo še vedno izgubili size-- bolje, Sposobnost, da spremenite velikost, če bomo to storili. 

Moramo se znebiti matriki smo ga nadomestiti z enim samim kazalcem, in potem nekje v moji kodi imam klic, kaj deluje, da dejansko ustvarjanje array imenovane številke? Malloc, ali nekaj podobnega funkcija, točno. Vsa vprašanja v zvezi nizov ali čakalne vrste. Ja? Dobro vprašanje. Kaj modulo bi uporabili tukaj. Tako na splošno pri uporabi mod, bi si to naredil z velikostjo od celotno strukturo podatkov. Torej nekaj podobnega kot pet ali sposobnosti, če je konstanta, ki je verjetno vpletena. Ampak samo delaš modulo pet Verjetno ne zadostuje, saj moramo vedeti počnemo ovijte okoli tukaj ali tukaj ali tukaj. Torej, ste verjetno tudi želeli vključiti velikost stvar, ali sprednja spremenljivka tudi. Torej, to je samo to razmeroma preprosta aritmetična izraz, vendar bi modulo ključna sestavina. 

Torej, kratki film, če boste. Animacija, da nekateri ljudje na drugi univerzi skupaj, ki smo jih prilagojen za to razpravo. Gre Jack učenju dejstva o čakalnih vrst in statistiko. 

FILM: Nekoč, tam je bil fant z imenom Jack. Ko je prišel, da bi prijatelji, Jack ni imela smisel. Torej, Jack šel govoriti na Najbolj priljubljen fant vedel. Odšel je Lou in vprašal, kaj naj storim? Lou videl, da je njegov prijatelj je bil res v stiski. No, on je začel, samo poglej, kako ste oblečeni. Nimaš nobenih oblačil z drugačnim videzom? Ja, je dejal Jack. Sem prepričan storiti. Prišel v mojo hišo in Pokazal jim bom za vas. Tako so šli off Jack. In Jack pokazala Lou polje kjer se je ohranil vse njegove srajce, in njegove hlače, in njegove nogavice. Lou je rekel, vidim, da imate vsa vaša oblačila v kupu. Zakaj ne nosiš nekaj drugi enkrat v nekaj časa? 

Jack je rekel, dobro, ko sem odstraniti oblačila in nogavice, Sem jih operemo in dal jim stran v polje. Potem pride naslednji zjutraj, in do sem hop. Grem na polje in dobili moje obleke off vrhu. Lou hitro spoznal problem z Jackom. Je ohranil oblačila, CD-jev, in knjige v dimnika. Ko je prišel za Nekaj ​​za branje ali za nošenje, on bi izbrati top knjigo ali spodnje perilo. Potem ko je bil storil, je bi ga dal nazaj. Nazaj bi šlo, na vrhu kupa. Vem, da je rešitev, dejal zmagoslavno Loud. Moraš se naučiti začeti uporabljati čakalno vrsto. Lou je oblačila Jack in jim visijo v omari. In ko je izpraznil polje, je pravkar ga vrgel. 

Potem je rekel, zdaj Jack, na koncu dan, dal svojo obleko na levi strani ko jih dal proč. Potem jutri zjutraj, ko vas glej sonce, dobili vaših oblačil na desni, od konca vrstice. Ali ne vidiš? je rekel Lou. To bo tako lepo. Boste nositi vse, enkrat preden kaj nositi dvakrat. In z vsem v čakalnih vrst v svoji omari in police Jack začel počutiti povsem prepričani o sebi. Vse zahvaljujoč Lou in Njegov čudovit čakalne vrste. SPEAKER 1: V redu, to je čudovit. Torej, kaj je bilo v resnici dogaja na pod pokrovom zdaj? Da imamo kazalce, da imamo malloc, da imamo možnost, da ustvarijo kose pomnilnika za nas dinamično. Torej je to slika smo zagledali šele drugi dan. Mi ni res živijo na njej, vendar pa je ta slika bil je dogajalo pod napa tednov zdaj. In tako to pomeni, samo pravokotnik, ki smo pripravljeni, pomnilnik vašega računalnika. In morda vaš računalnik ali CS50 ID, ima gigabajt pomnilnika ali RAM ali dva gigabajta ali štiri. To sploh ni pomembno. Vaš operacijski sistem Windows ali Mac OS ali Linux, v bistvu omogoča vaš program misliti, da ima dostop za celoto računalnika spomin, čeprav vas bo morda teče več programov naenkrat. Torej, v resnici, da v resnici ne deluje. Ampak to je neke vrste iluzija dati vse svoje programe. Torej, če ste imeli dve nastopov RAM-a, to je, kako lahko računalnik si o njej mislijo. 

Zdaj pa po naključju, je eden od teh stvari, eden izmed teh segmentov pomnilnika, se imenuje kup. In res kadarkoli doslej v pisanje kode ki ste jih imenuje funkcija, na primer vod. Spomnimo se, da vsak čas sem imel Drawn računalnika spomin, Vedno rišem nekako polovica pravokotnika tukaj in ne trudim govoriti o tem, kaj je zgoraj. Ker, ko je glavna imenuje, Trdim da dobiš to žarek spomina da gre tukaj dol. In če glavna imenuje funkcija kot so zamenjave, ter swap gre tukaj. In se je izkazalo, da je kam to konča. Na nekaj imenujemo kup znotraj pomnilnika računalnika. Sedaj na koncu dneva, to je samo obravnava. To je kot bajt ničlo, bajt ena, bajt 2 milijardi. Ampak, če mislite, da o tem kot to pravokotnega predmeta, Vse počneva vsak Čas pravimo funkcija je plastenjem nov rezino pomnilnika. Mi daje to funkcijo rezina lastnega pomnilnika delati. 

In spomni se zdaj, da je to pomembno. Ker če ne bomo imeli nekaj podobnega zamenjave in dva lokalne spremenljivke, kot so A in B, bomo spremenili te vrednote iz ene in dva za dva in enega, odpoklica da ko swap vrne, to je, kot da ta rezina spomina je pravkar šla. V resnici pa je še vedno tam forensically. In kar je še vedno tam dejansko. Vendar konceptualno, to je kot čeprav je to popolnoma izginila. In tako glavni ne pozna nobenega dela, ki je bilo storjeno v tej funkciji swap, razen če je to dejansko prenesejo na tiste, Argumenti, ki jih kazalcem ali s sklicevanjem. Zdaj, temeljna rešitev na ta problem z zamenjavo je mimo stvari po naslovu. Ampak se je izkazalo tudi, kaj je se dogaja na zgoraj navedenem delu pravokotnika je ves ta čas še tam je več pomnilnika tam gor. In ko boste dinamično dodeliti pomnilnika, ali je to znotraj GetString, ki smo počeli za vas v CS50 knjižnica, ali če se vidva klic malloc in vprašati operacijski sistem za kos spomin, da ne prihaja iz dimnika. To izhaja iz drugega kraja v pomnilniku računalnika da se imenuje kup. In to ni nič drugače. To je isti RAM. To je isti spomin. To je samo RAM, ki je do tam namesto dol. 

In tako, kaj to pomeni? No, če ima vaš računalnik končna količina pomnilnika in kup odrašča, zato govoriti, in kup, po te puščice, raste dol. Z drugimi besedami, vsak Čas pokličete malloc, Bili ste dali rezino pomnilnika od zgoraj, potem pa malo nižje, nato pa malo nižje, vsakič, ko klic malloc, kup, da je navada, je vrsta raste, raste bližje in bližje, kaj? Sveženj. Torej se to zdi dobra ideja? Mislim, če je to v resnici ni jasno, kaj še lahko storite, če ste le imajo končno količino pomnilnika. Ampak to je zagotovo slabo. Ti dve puščici določijo na Crash Course drug za drugega. 

In se je izkazalo, da je slab fant, ljudje, ki so še posebej dobro s programiranjem, in poskuša vdreti v računalnike, lahko izkoriščajo to realnost. V resnici pa menijo malo odrezek. Torej, to je primer, si lahko preberete podrobneje na Wikipediji o v. Vam bomo kazali na članek, če radoveden. Ampak tam je napad na splošno znan kot varovalni preliva da obstaja že tako dolgo kot ljudje so imeli možnost, da manipulirajo računalnika spomin, še posebej v C. Torej je to zelo poljubna program ampak dajmo brati od spodaj navzgor. Main v argc char zvezdic argv. Torej, to je program, ki traja argumenti v ukazni vrstici. In vsi glavni pa očitno je klic funkcijo, jo pokličite F za preprostost. In prehaja v kaj? Argv enega. Tako da prehaja v F karkoli Beseda je, da Vtipkali na poziv po vrstnem Ime programa sploh. Toliko kot Cezarja ali Vigenere, ki boste morda odpoklic delaš z argv. 

Torej, kaj je F? F je v nizu kot edini argument, AKA char zvezda, enako stvar, kot niz. In se imenuje samovoljno bar v tem primeru. In potem char c 12, samo v smislu navadnega je, kaj je char c nosilec 12 delaš za nas? Kaj pa je naredil? Dodeljevanje pomnilnika, še posebej 12 bajte za 12 znakov. Točno tako. In potem je zadnja vrstica, premešamo in Kopija, ki ste jih verjetno ni videl. To je niz kopija funkcija, katere namen v življenju je, da kopirate svojo drugo trditev v svoji prvi argument, vendar le do Določeno število bajtov. Torej tretji argument pravi, koliko bajtov morate kopirati? Dolžina vrat, kar uporabnik vtipka. In vsebina bar, ta niz, so kopirati v pomnilnik opozoril na na C. 

Torej, to se zdi nekako neumno, in je. To je izmišljeno primer, ampak to je reprezentativen iz razreda napadom vektorjev, način napadajo program. Vse je lepo in prav, če uporabnik vrste v eno besedo, ki je 11 znakov ali manj, plus poševnica nazaj nič. Kaj pa, če uporabnik vnese v več kot 11 ali 12 ali 20 ali 50 znakov? Kaj je to program, boš naredil? Potencialno seg krivda. To se dogaja slepo kopirati vse v baru navzgor njegovi dolžini, ki je dobesedno vse, kar je v barih, v naslovu opozoril na C. But C je le preemptively podana kot 12 bajtov. Vendar ni dodatno preverjanje. Če pogojev ni. Ni preverjanje tu napake. 

In kaj je ta program tekoč storiti, je le slepo kopirate eno stvar za drugo. In tako, če potegnemo to kot sliko, tukaj je samo žarek pomnilniški prostor. Tako obvestilo na dnu, smo imajo lokalne variabilne bar. Tako da je kazalec, da se dogaja, da store-- namesto te lokalne trditev, da je dogaja, da shranite niz bar. In potem opazili samo nad njo v kup, ker vsakič, ko si vprašal Za spomin na kupu, gre malo nad njo slikovno, Obvestilo, da imamo 12 bajtov tja. Zgoraj levo je ena C nosilec nič in V spodnjem desnem kotu je ena C nosilec 11. To je samo, kako so računalniki dogaja, da ga položite ven. Torej samo intuitivno, če ima bar več kot 12 znakov v celoti, vključno z Nagibnica nič, kjer je 12 ali C nosilec 12 šli? Oziroma, če je 12. značaj ali 13. značaj, stoti znak dogaja končajo na sliki? Zgoraj ali spodaj? 

Prav, ker čeprav Sveženj sama raste navzgor, ko ste dal stvari v to je za oblikovalskih razlogov, postavlja pomnilnik od vrha do dna. Torej, če imaš več kot 12 bajtov, boš začeti prepisati bar. Zdaj, ko je napako, vendar je ni res big deal. Ampak to je velik posel, saj je več stvari dogaja v pomnilniku. Torej, tukaj je, kako bi lahko dal zdravo, da bo jasno. Če sem tipkal v pozdrav na poziv. H-E-L-L-O Nagibnica nič, konča znotraj ti 12 bajtov, in smo super varna. Vse je dobro. Ampak, če sem kaj natipkali več, morda je dogaja, da lezenje v bar prostor. Ampak še huje, se izkaže ven vsem tem času, čeprav se nikoli nismo pogovarjali o to je kup uporablja za druge stvari. To ni le lokalne spremenljivke. 

C je jezik zelo nizko raven. In to je nekako na skrivaj uporablja stack tudi da se spomniš, ko Funkcija se imenuje, kaj naslov je prejšnji funkciji tako da lahko skoči nazaj na to funkcijo. Torej, ko glavni klici zamenjali, med stvari potisniti na kupu niso samo zamenjav lokalnih spremenljivk, ali njeni argumenti, tudi na skrivaj porinil na kupu, kot je predstavljena z rdečim rezine tod je naslov glavne fizično v spominu računalnika, tako da, ko je zamenjava opravljeno, računalnik ve, da moram iti nazaj na glavno in konča izvedbo glavno funkcijo. Torej je to nevarno sedaj, ker če uporabnik vnese v dobro več kot zdravo, tako da vhod uporabnikova clobbers ali prepiše ta rdeči del, logično, če računalnika le, da bo slepo prevzame da so bajtov tem rdeče rezine naslov, na katerega bi se moral vrniti, Kaj pa, če nasprotnik je dovolj pameten, ali dovolj srečni, da bi dal zaporedje bajtov tam, da izgleda kot naslov, ampak to je naslov kode da je on ali ona želi računalnik izvršiti namesto glavnega? 

Z drugimi besedami, če je kaj na Uporabnik je tipkanje na poziv, ni samo nekaj, neškodljive kot zdravo, ampak to je dejansko kodo, ki je enakovreden izbrisati vse datoteke Ta uporabnik je? Ali email svoje geslo z mano? Ali začeti prijavite svoje tipkanja, kajne? Obstaja način, dajmo določajo danes, da bi jih tip v ne samo zdravo svet ali njihovo ime, so lahko v bistvu prenese v kodo, ničle in tisti, ki računalnik napake tako za kodo in naslov. Torej, čeprav je nekoliko abstraktno, če uporabnik vnese v dovolj kontradiktornosti kodo da bomo posplošiti tukaj A. A je napad ali nasprotniki. Tako da samo slabe stvari. Mi ne skrbi številke ali ničle ali tisti, danes, tako da boste na koncu prepisovanju ta rdeči del, opazili, da je zaporedje bajtov. O 835 Cnič osem nič. In zdaj, ko Wikipedije članek tukaj je predlagal, če boste zdaj dejansko začeli označevanje bajtov v vašem računalniku spomin, kaj je članek Wikipedija predlagateljica je to, kaj pa če je naslov navedene zgornjem levem bajt 80 C 0 3508. 

Z drugimi besedami, če je slab fant je dovolj pameten s svojo kodo dejansko dal številko tukaj, da ustreza naslovu oznake on ali ona vbrizga v računalniku, lahko trik računalnik v delaš karkoli. Odstranjevanje datotek, pošiljanje e-pošte Stvari, nahod svojega prometa, dobesedno vse, kar bi lahko vbrizga v računalniku. In tako buffer overflow napad v svojem jedru je samo neumna, neumna prevlada od matrike, ki niso imeli preveriti njene meje. In to je tisto, kar je super nevarno in hkrati super močan v C je, da smo zares imeli dostop do kjerkoli v pomnilniku. To je odvisno od nas, programerji, ki pišejo izvirno kodo preveriti dolžino darn kateregakoli nizi, da smo manipuliranja. Torej, da bo jasno, kaj je fix? Če smo roll nazaj na to koda, jaz ne bi samo spremeniti dolžino vrat, kar sicer bi moral biti preverjanje? Kaj drugega naj se delaš, da popolnoma preprečiti ta napad? Nočem, da bi le slepo reči da bi morali kopirati toliko bajtov kot je dolžina vrat. Hočem reči, kopirate veliko bajti, kot so v barih do dodeljena spomin, ali 12 maksimalno. Torej rabim nekakšen če pogoj da ne preveri dolžino vrat, če pa preseže 12, samo trdo kodo 12, kot je v največji možni razdalji. V nasprotnem primeru se ti buffer overflow napad lahko zgodi. Na dnu teh stekelc, Če ste radovedni, da preberete več je dejanska izvirni članek če želite, da pogled. 

Toda zdaj, med cenami plačan tukaj je neučinkovitosti. Tako da je to lahko hitro nizka pogled raven, na kaj Težave se lahko pojavijo zdaj, da smo imajo dostop do pomnilnika računalnika. Ampak en problem smo že naletel na ponedeljek je samo neučinkovitost iz povezani seznam. Mi smo nazaj v linearnem času. Nimamo več sosednji paleto. Nimamo naključni dostop. Ne moremo uporabiti oglati oklepaj zapis. Mi dobesedno morali uporabiti while zanko kot tisti, ki sem napisal pred nekaj trenutki. Ampak v ponedeljek, smo trdili, da smo lahko lezenje nazaj v sfero učinkovitosti doseči nekaj, kar je logaritemsko morda, ali še najbolje, morda celo nekaj, kar je ti konstantna čas. Torej, kako lahko naredimo, da z uporabo teh novih orodja, ti naslovi, ti kazalci, in navojev stvari sami? No, recimo, da je tukaj, to so kup številk, ki jih želimo shranite v Struktura podatkov in iskanje učinkovito. Mi lahko povsem nazaj do tedna dva, vrgel ti v array, in jih iskati v dvojiškem iskanje. Deli in vladaj. In v resnici si napisal binarno iskanje v PSET3, kjer se izvaja program najde. Ampak veš kaj. Tam je nekako bolj pameten način za to. To je malo bolj prefinjen in ga morda nam omogoča, da vidite, zakaj binarni Iskanje je toliko hitrejši. Najprej, kaj je uvesti pojem drevesa. Ki je, čeprav v realnost drevesa vrste rastejo, kot je ta, v svetu računalniku znanost so vrsta raste navzdol kot družinsko drevo, kjer imate vaši stari starši ali stari starši veliko ali malenkosti na vrhu, patriarha in Matriarchs družine, le eno ti koren, vozlišče, spodaj ki so njegovi otroci, pod katero so njeni otroci, ali njegovi potomci bolj na splošno. In kdo visi off dno družine drevo, poleg tega pri čemer je najmlajši v družini, Lahko tudi samo biti splošno imenovani listi drevesa. 

Torej je to samo kup besed in definicij za nekaj, kar se imenuje drevo v računalniku znanost, podobno kot družinsko drevo. Ampak tam je Ljubitelj inkarnacije dreves, od katerih je eden imenujemo binarno iskalno drevo. In lahko nekako tease narazen, kaj ta stvar počne. No, to je binarni, v kakšnem smislu? Kje binarni prihaja od tukaj? Žal? To ni toliko bodisi ali. To je več, da ima vsaka izmed vozlišč ne več kot dva otroka, kot smo videli tukaj. Na splošno je tree-- in vaši starši in stari starši imajo lahko toliko otrok ali vnuki, kot so dejansko želijo, in tako na primer tam imamo tri otroci izven te desnem vozlišču, temveč v binarnem drevesu vozlišče ima nič, ena ali dva otroka najvišja. In to je lepa lastnost, ker če je to omejena z dvema, bomo mogli dobili malo dnevnika baze dva dejanje dogaja na koncu. Torej, imamo nekaj logaritemsko. Ampak več o tem v tem trenutku. Iskanje drevo pomeni, da so številke razporejena tako, da je leva otroka je vrednost večja od korena. In njegova pravica otrok večja od korena. Z drugimi besedami, če jemljete katero koli izmed vozlišča, krogi v tej sliki, in gleda na levi Otrok in njegova pravica otrok, prva mora biti manjša Drugi mora biti večja od. Torej sanity check 55. To je zapustila otroka, je 33. To je manj kot. 55, njena pravica otrok je 77. To je večje od. In to je rekurzivna definicija. Mi lahko preveri vsak eno izmed tistih, vozlišča in isti vzorec bi imel. 

Torej, kaj je lepo v binarno iskalno drevo, je da je eden, ga lahko izvajajo s struct, tako kot to. In čeprav smo metali veliko objektov na vaši, oni nekoliko intuitivno zdaj upajmo. Sintaksa je še vedno Skrivnosten za prepričani, vendar pa je vsebina vozlišča v tem context-- in hranimo z besedo vozlišče, ali je pravokotnik na zaslonu ali kroga, to je samo nekaj generično posoda, V tem primeru drevesa, podobnega tistemu smo videli, moramo celo v vsakem od vozlišč in potem moram dva kazalca, ki kaže na levo otroka in desni otroka, oz. Torej, to je, kako bomo morda sredstva, ki je v struct. In kako bi jaz to izvesti v kodo? No, vzemimo hitro poglej ta majhen primer. To ne deluje, vendar sem kopirali in prilepili to strukturo. In če je moja funkcija za binarne Iskanje drevo se imenuje iskanje, in to traja dva argumenta, celo število N in kazalec na vozlišča, tako da kazalec na drevesu ali kazalec do korena drevesa, kako iti o iskanju za N? No, najprej, ker sem ki se ukvarjajo s kazalci, Bom naredil pregled prištevnosti. Če drevo Ene enak null, je N v tem drevo ali ni v tem drevesu? To ne more biti, kajne? Če sem mimo null, tam ni ničesar. Jaz lahko tudi samo slepo pravijo vrne false. Če mi daš nič, jaz zagotovo ne morem najti številko N. Torej kaj bi jaz preveriti zdaj? Jaz bom rekel, tudi drugje, če je N manj kot vse, kar je na drevo vozlišče da sem bil izročil N vrednost. Z drugimi besedami, če je število sem išče, N, je manjša od vozlišča da gledam. In vozlišče Iščem pri imenujemo drevo, in odpoklic iz prejšnjega primera da se pri vrednosti v kazalca I uporabite puščico zapis. Torej, če je N manj kot drevo puščico N, želim konceptualno iti levo. Kako ekspres iskanje po levi? Da bo jasno, če je to slika v vprašanju, in sem bil sprejet, da je vrhunska arrow ki je obrnjena navzdol. To je moje drevo kazalec. Jaz sem gledala v korenu drevesa. In iščem recimo, za številka 44, poljubno. Je 44 manj kot ali večja od 55 očitno? Torej, to je manj kot. In tako je to, če velja pogoj. Torej konceptualno, kaj hočem iskanje zraven, če iščem 44? Ja? 

Točno, želim iskanje po levi otroka, ali levo sub-tree te slike. In v resnici, pustite me skozi slika tukaj za trenutek, saj Tega ne morem opraskati ven. Če začnem tukaj na 55, in Vem, da je vrednost 44 Iščem je levo, to je neke vrste podobnega solzenje imenika v polovico ali solzenje drevo na pol. Nimam več skrbeti ta cela polovica drevesa. In vendar, radovedno v odnosu na struktura, ta stvar tukaj, ki se začne z 33, ki sama po sebi je dvojiško iskalno drevo. Rekel sem, beseda rekurzivna prej, ker dejansko je to podatkovna struktura, ki po definiciji je rekurzivna. Morda imate drevo, ki je to velik, vendar vsak od njenih otrok predstavlja drevo le malo manjši. Namesto njega pa dedek ali babica, zdaj pa je samo mama or-- ne morem say-- ni mama ali oče, da bi bilo čudno. Namesto tega dva otroka tam bi bilo, kot brat in brat. Nova generacija družinskega drevesa. Ampak strukturno, to je ista ideja. In se je izkazalo, da imam funkcijo s katero sem lahko poiščete binarno iskanje drevo. To se imenuje iskanje. Iščem za N v drevo puščico levo drugega, če je n večji od vrednosti da sem trenutno. 55 v zgodbi trenutek nazaj. Imam funkcijo imenovano iskanje, da sem lahko samo mimo N to in rekurzivno iskanje sub-tree in samo donos karkoli že to odgovor. Else Imam nekaj končno bazo primera tukaj. 

Kaj je končna primer? Drevo je bodisi nična. Vrednost bom niti iskal je manjši od njega ali višja kot tista ali enako njej. In lahko rečem enako enaka, vendar pa je logično, da je enakovredna samo rekel še tukaj. Torej, res je, kako sem našel nekaj. Zato upajmo, da je to Še bolj prepričljiv primer kot neumnega funkcijo sigma smo naredili nekaj predavanj nazaj, kjer je bilo prav tako enostaven za uporabo zanko za štetje gor vse številke iz enega v N. tukaj s podatkovno strukturo da sama rekurzivno opredeljena in rekurzivno pripravljeni, zdaj smo imeti možnost, da sami izrazijo V kodeksu je rekurzivni, da je sama. Torej, to je točno isto kodo tukaj. 

Torej, kaj druge težave lahko rešimo? Torej, hiter korak stran od drevesa za trenutek. Tukaj je, pravijo, nemško zastavo. In tam je jasno Vzorec te zastave. In tam je veliko Zastave na svetu, ki so tako enostavno, kot je to v smislu njihovih barv in vzorcev. Recimo, da je ta shranjena kot GIF ali JPEG, ali bitmap ali ping, katerikoli grafični format datotek s katerim ste seznanjeni, nekateri, ki smo igranje z v PSET4. To se ne zdi vredno, da shranite črna pixel, črna pixel, črna pixel, dot, dot, dot, cel kup črnih pik za prvi scanline, ali vrstica, nato pa cel kup enaka, potem cel kup iste, nato pa cel kup rdečih pik, rdečih pik, rdeče pik, potem celota šopek rumenih pik, rumena, kajne? 

Tam je kot neučinkovitost tukaj. Kako bi si intuitivno stisniti nemško zastavo če ga izvajajo kot datoteko? Všeč, kaj informacij ne moremo trudim shranjevanje na disku, da bi zmanjšati našo velikost datoteke iz podobnih megabajt do kilobyte, nekaj manjši? V čem je redundanca Tukaj mora biti jasno? Kaj lahko naredim? Ja? Točno tako. Zakaj ne bi namesto spomnim barva vsake darn piksla tako kot počnete v PSET4 z obliko bitmap datoteke, zakaj ne samo predstavljajo Skrajno levi stolpec slikovnih pik, na primer kup črnih pik, kup rdeče, in kup rumena, in potem nekako kodiranje Zamisel o ponovite ta 100-krat ali ponovite 1000-krat? Kjer je 100 ali 1000 je samo celo število, zato vas lahko izmaže samo eno številko namesto da bi več sto ali tisoč dodatnih pik. In res, to je, kako smo lahko stisne nemško zastavo. In Zdaj kaj francosko zastavo? In malo nekakšna mentalna vaja, ki zastava je mogoče stisniti več na disku? Nemška zastava ali francoščina zastava, če vzamemo, da je pristop? Nemška zastava, ker tam je bolj horizontalno odveč. In z zasnovo, mnogi grafična datoteka Oblike zares delujejo kot skeniranja linije vodoravno. Da bi lahko delali navpično, samo človeštvo Pred odločili let, da bomo običajno razmišljati o stvari zapored z vrstico namesto kolono s kolone. Torej res, če ste bili pogledati datoteko Velikost nemško zastavo in francoščini zastave, tako dolgo, kot je ločljivost enako, enako širino ter višine, tale tukaj se bo večji, ker vas morali sami ponovite trikrat. Morate navesti modro, ponovitev sami, bela, ponovite sami, rdeča, ponovite sami. Ne moreš kar iti vse pot v desno. In kot prahi, da bi počistite stiskanje je povsod, če so ti štirje okvirji iz video-- vas Morda se spomni, da je film ali video je na splošno kot 29 ali 30 sličic na sekundo. To je kot malo flip knjigo, kjer vas le glej slike, slike, slike, slike, slika samo super hitro, tako da izgleda kot akterji na zaslonu se gibljejo. Tukaj je čmrljev na vrh kup cvetja. In čeprav bi bilo nekako težko videti na prvi pogled, edina stvar gibljejo Ta film je čebela. 

Kaj je neumna o shranjevanju video nestisnjena? To je neke vrste odpadkov, za shranjevanje videa kot štiri skoraj enakih podob, ki razlikujejo le toliko, kolikor kje je čebela. Lahko mečejo najbolj te informacije in zapomni samo, na primer, prvi okvir in zadnji okvir, Ključne okvirji Če ste kdaj slišal besedo, in samo shranite v sredina, kjer je čebela. In ti ne bi bilo treba shranjevanje vseh roza, in modro, ter zelene vrednosti, kot dobro. Torej, to se pravi, da le Stiskanje je povsod. To je tehnika, smo pogosto uporabljajo ali jemljemo za samoumevno v teh dneh. 

Ampak kako si stisniti besedilo? Kako greste o stiskanjem besedilo? No, vsaka od znakov ASCII je en bajt, ali osem bitov. In to je nekako neumno, kajne? Ker ste verjetno tip A in E in I in O in U veliko največkrat kot W ali Q ali Z, odvisno od jezika, v katerem pišete zagotovo. In zakaj smo se s pomočjo osem bitov za vsako pismu, vključno z najmanj zanimiva pisma, kajne? Zakaj ne bi uporabili manj bitov za super priljubljena pisma, kot E, stvari, ki jih ugibati najprej v Wheel of Fortune, in uporabite več bitov za manj zanimiva pisma? Zakaj? Ker smo le, da bo jih uporabljajo manj pogosto. 

No, izkaže se, da je imela bil napore, da to storijo. In če se spomnite iz razreda šoli ali srednji šoli, Morse code. Morse code ima pike in črtice, ki se lahko prenaša vzdolž žice kot sliši ali signali neke vrste. Ampak Morse code je super čist. To je nekako binarnega sistema da imate pike ali črtice. Ampak, če ste videli, na primer, dve piki. Ali pa, če mislite, da nazaj na izvajalca ki gre takole pisk, pisk, pisk pisk, hitting malo sprožilec ki oddaja signal, če vas, prejemnik prejme dva pike, kakšno sporočilo ste prejeli? Popolnoma samovoljno. 

JAZ? JAZ? Ali kaj about-- ali jaz? Mogoče je bilo samo dva prava E je? Tako da je ta problem od decodability z Morse kode, pri čemer razen če Oseba, ki vam pošilja sporočilo dejansko premori, tako da lahko nekako videli ali slišali vrzeli med črkami, to ni dovolj, samo, da pošljete tok ničel in enic, ali pike in črtice, zato, ker je dvoumnost. E je ena pika, tako da, če vas glej dve piki ali slišali dve piki, morda je dva E ali morda je ena I. Zato moramo sistem, ki je malo bolj pameten kot to. Torej človek, imenovan Huffman let Pred prišel s točno to. Tako da smo šele tekoč vzeti hiter pogled kako so drevesa germane za to. Recimo, da je to nekaj neumen sporočilo, ki ga želite poslati, sestavljajo samo A, B, C v D-jev, in E je, ampak tam je veliko redundance tukaj. To ni mišljeno, da bo angleščina. To ni šifrirana. To je samo neumno sporočilo z veliko ponavljanja. Torej, če ste dejansko izločiš vse Je A, B je, C-ih, D's, in E je, tu je frekvenca. 20% črk Je, 45% črk so E-jev, in tri druge frekvence. Smo prešteti tam ročno in samo naredil matematike. 

Tako se izkaže, da Huffman, nekaj časa nazaj, spoznal, da veste kaj, če začnem stavbo drevo ali gozd dreves, če hočete, takole, jaz lahko storite naslednje. Bom dal vozlišče za vsako pisem, ki mi je mar in bom za shranjevanje Notranjost vozlišča frekvence kot plavajočo vejico vrednost, ali pa bi ga uporabili N, preveč, vendar bomo šele raba plovec tukaj. In algoritem, ki je predlagal je, da si to gozd samega vozlišča drevesa, tako super kratke drevesa, in začnete jih povezujejo s nove skupine, nove starše, če hočete. In to storite z izbiro dve najmanjši frekvenci hkrati. Zato sem vzel 10% in 10%. Sem ustvariti novo vozlišče. In kličem novo vozlišče 20%. 

Kateri dve vozlišči kombiniram zraven? To je malo dvoumno. Torej je nekaj kotiček primerov na menijo, ampak da se stvari precej, Grem, da izberejo 20% - Zdaj prezreti otroke. Grem, da izberejo 20% in 15% in sestaviti dva nova robove. In sedaj katera dva vozlišča jaz logično združiti? Ignoriraj vse otroke, vsa vnuki, samo poglej na koreninah zdaj. Kateri dve vozlišči moram kravato skupaj? Točka dva in 0,35. Torej mi pripravi dva nova robove. In potem imam samo eno levo. Torej, tukaj je drevo. In to je bil sestavljen namerno pogledati nekako lepo, vendar opazili, da imajo robovi Prav tako je bilo označeno nič in ena. Torej vse levimi robovi so nič samovoljno, ampak dosledno. Vse desni robovi so tisti. 

In kaj Hoffman je predlagana, če želite, da predstavljajo B, namesto predstavljajo število 66 kot ASCII, ki je osem celotno bitov, Veš kaj, samo trgovina vzorec nič, nič, nič, nič, ker je to pot iz mojega drevesa, gospoda Huffman je drevo, na krilo od korena. Če želite shraniti E, nasprotno, ne poslati osem bitov, ki predstavljajo E. Namesto, pošljete kakšen vzorec bitov? Ena. In tisto, kar je lepo, o tem je da E je najbolj priljubljena pismo, in ste z uporabo Najkrajša koda za njo. Naslednja najbolj priljubljen Pismo je videti, kot da je A. In tako, koliko bitov pa je predlagala uporabo za to? Nič, ena. 

In zato, ker je izvajala kot je to drevo, za zdaj Naj določi, da je nejasnosti kot v Morse Koda, ker vse črke, ki jih skrbijo so na koncu teh robov. Torej, to je samo ena Uporaba drevesa. To is-- in bom val moja roka na to, kako vas to lahko izvede kot struktura C. Vedeti pa je treba združiti simbol, kot char, in frekvenca v levo in desno. Toda poglejmo na dveh Končni primeri, da boste dobili precej seznanjeni s po kviz nič na problem nastaviti pet. 

Tako da je struktura podatkov znan kot hash tabele. In hash tabela je nekako ohladi s tem, da ima žlice. In Recimo, da je štiri žlice tu, le štiri presledke. Tukaj je kart, in tu se klub, lopato, klub, diamanti, klub, diamanti, klub, diamanti, clubs-- tako da je to naključno. Hearts, hearts-- tako da sem bucketizing vse vhode tukaj. In hash table potrebe pogled na vaš prispevek, in ga nato dal v neka postavite na osnovi tega, kar vidite. To je algoritem. In sem bil z uporabo super enostavna vizualna algoritem. Najtežji del je bil spomnimo, kaj so bile slike. In potem je tu še štiri skupne stvari. 

Zdaj nizov so bile narašča, kar je premišljena zasnova stvar tukaj. Ampak, kaj še lahko storim? Torej, dejansko tukaj imamo kup starih šola izpit knjig. Denimo, da je kup Imena študentov so tukaj. Tukaj je večji hash tabele. Namesto štiri segmente, Sem, recimo, 26. In nismo želeli iti izposoditi 26 Stvari od zunaj [? Annenberg?], Zato tukaj je pet, ki predstavljajo A do Z. In če sem glej študenta, čigar ime se začne z A, Jaz grem k svoji kviz dal tja. Če nekdo začne s C, tam, A-- dejansko, ni želel, da to storim. B gre tukaj. Torej imam A in B in C. In tukaj je še en študent. Ampak, če je to hash tabela izvaja z vrsto, Jaz sem nekako zajebali na tej točki, kajne? Sem nekako morali dati to nekje. 

Torej en način sem lahko reši to je vse desno, A je zaseden, B je zaposlen, C je zaseden. Bom ga dal v D. Torej na Najprej sem imela naključno takojšen dostop za vsakega od vedra za študente. Ampak zdaj je vrsta preneseno v nekaj linearnega, ker če želim iskati nekoga katerih ime se začne z A, I preverite tukaj. Toda, če to ni A študent Iščem, Nekako sem moral začeti preverjanje Vedra, ker tisto, kar sem storil je nekako linearno sonda podatkovne strukture. Neumen način rekel samo poglej za prvo razpoložljivo odprtino, in dal kot Plan B, tako rekoč, ali plan D, v tem primeru vrednost na tem mestu namesto. To je samo zato, da, če ste dobil 26 lokacij in študenti z imenom Q ali Z, ali kaj podobnega da, vsaj boste uporabljali prostor. 

Ampak smo že videli več pametne rešitve tukaj, kajne? Kaj bi ti naredil namesto če imate trčenje? Če imata dve osebi ime A, kaj bi so bili pametnejši ali bolj intuitivno rešitev, kot le Prenos kjer je D naj bi bila? Zakaj ne samo pojdi izven [? Annenberg?] kot knjižnične funkcije malloc, drugo vozlišče, ga tukaj, in potem dal, da študent tukaj. Tako, da sem v bistvu še nekakšen array, ali morda še bolj elegantno, kot smo začenja videti povezani seznam. 

In zato je hash tabela je struktura da bi lahko videti kot to, ampak bolj spretno, si nekaj, kar se imenuje ločen veriženje, s katerim hash tabela preprosto je matrika, vsaka katere elementi ni številka, je sama povezani seznam. Torej, da dobiš super hitri dostop odločanju, kje izbrskali svojo vrednost. Podobno kot s primerom kartice, Naredil sem super hitre odločitve. Hearts gre tukaj, diamanti gre tukaj. Enako tukaj, A gre tu, D gre tukaj, B gre tukaj. Torej super hitro look-ups, in če se zgodi, da delujejo v primeru kjer imaš trkov, dve ljudje z istim imenom, in nato ste šele začeli ju povezuje. In morda boste obdržali jih razporejene po abecednem redu, morda ne. Ampak zdaj vsaj imamo dinamičnost. Torej na eni strani imamo zelo hitro stalen čas in vrsta linearnem času vključeni, če teh povezanih seznamov začetek, da bi dobili malo dolgo. 

Tako da je ta vrsta neumno, pred geeky potegavščine let. Na CS50 hack-a-thon, ko so študenti prijavijo, nekateri TF ali CA vsako leto misli, da je smešno, da dajo znak, kot je ta, če je le pomeni, da če vaše ime se začne z A, gredo v to smer. Če je vaše ime se začne z B, pojdite this-- OK, to je smešno, morda kasneje v semestru. Toda obstaja še ena načinov za to, preveč. Vrnite se k temu. 

Torej je ta struktura. In to je naša zadnja struktura za danes, ki je nekaj, kar se imenuje trie. T-R-I-E, ki je iz neznanega razloga je kratka za iskanje, vendar je pozval trie. Torej trie je še ena zanimiva amalgam veliko teh idej. To je drevo, ki smo ga videli prej. To ni binarno iskalno drevo. To je drevo s poljubnim številom otrok, ampak vsak otrok v Trie je niz. Niz velikosti, recimo, 26 ali morda 27 Če želite podpreti sklopljenih imena ali opuščaj v imenih ljudi. 

In tako je to struktura podatkov. In če pogledaš od zgoraj do dna, kot če vas poglej zgornjem vozlišču tam, M, je kaže na skrajni levi stvar tam, ki ga nato A, X, W, E, L, L. Gre le struktura podatkov, ki samovoljno je shranjevanje imen ljudi. In Maxwell shranijo samo po pot od polja do polja do polja. Toda kaj je neverjetno približno trie je da, ker je povezana seznama in še matrika, najbolje kar smo jih kdaj gotten je linearni čas ali logaritemsko čas iščejo nekdo gor. V tej strukturi podatkov za trie, če moj podatkovna struktura ima eno ime v njej in iščem Maxwell, sem dogaja, da ga precej hitro našli. Pravkar sem si za M-A-X-W-E-L-L. Če ta struktura podatkov, nasprotno, če N je milijon, če obstaja milijon imen v tej strukturi podatkov, Maxwell je še vedno dogaja, da se odkriti po samo M-A-X-W-E-L-L koraki. In koraki David-- D-A-V-I-D. Z drugimi besedami, z oblikovanjem podatkovna struktura, ki je nimajo od katerih so vsi ti nizi, vse sami podpirajo naključni dostop, Lahko začnete iskati up ljudske ime uporabljate količino časa, ki je sorazmerna ne številom stvari v strukturi podatkov, kot milijon obstoječa imena. Količina časa, da me popelje najti M-A-X-W-E-L-L v tej strukturi podatkov je sorazmerna ne do velikost strukture podatkov, vendar dolžini imenom. In stvarno Imena iščemo up se nikoli ne bo noro dolgo. Mogoče kdo ima 10 značaja ime, 20 ime znakov. To je gotovo omejen, kajne? Tam je človek na Zemlji, ki ima najdaljšo možno ime, ampak to ime je konstanta Dolžina vrednost, kajne? To ne spreminja v nobenem smislu. Torej, na ta način, ki smo jih doseženi podatkovne strukture da je stalen čas look-up. To ne bo več korakov odvisno od dolžine vnosa, vendar ne število imenom v podatkovno strukturo. Torej, če bomo podvojili število imen Naslednje leto od milijarde do dveh milijard evrov, Ugotovitev Maxwell se dogaja, da sprejmejo natančno enako število sedmih korakih da bi ga našli. In tako se zdi, da smo dosegli naš sveti gral čas teče. 

Torej Nekaj ​​hitrih objav. Kviz nič prihaja. Več o tem na spletni strani predmeta je v naslednjih nekaj dneh. Ponedeljek je lecture-- To je praznik tukaj na Harvardu v ponedeljek. To ni v New Haven, tako da smo vzeli razred New Haven za predavanje v ponedeljek. Vse bo posnet in predvajale v živo, kot ponavadi, ampak kaj je na koncu danes z drugo sponko 30 imenovane "Deep Thoughts" ga Daven Farnham, ki je je navdihnila lani do sobote Night Live je "Deep Thoughts" Jack Handy, ki bi se morali zdaj smisla. 

FILM: In zdaj, "Deep Misli "po Daven Farnham. Hash tabela. 

SPEAKER 1: V redu, to je to za zdaj. Se vidimo naslednji teden. 

Doug: Da bi ga videli v akciji. Torej, kaj je si oglejte, da je prav zdaj. Torej, tukaj imamo neurejen paleto. 

IAN: Doug, lahko greš naprej in ponovni zagon to za eno samo sekundo, prosim. Vredu, kamere so valjanje, tako Akcijski ko boste pripravljeni, Doug, OK? Doug: V redu, tako da tisto, kar smo imamo tukaj je razvrščen niz. In sem obarvani vse elemente rdeče, kar pomeni, da je v resnici razvrščeni. Tako opozarjajo, da je prva stvar, ki jo storite je levi polovici matrike smo razvrstiti. Potem smo razvrstiti pravico polovica matriki. In ya-da, ya-da, ya-da, smo jih združiti skupaj. In imamo popolnoma urejen niz. Torej, to je, kako združiti nekako deluje. 

IAN: Vau, vau, vau, cut, cut, cut, cut. Doug, ne moreš samo ya-da, ya-da, ya-da, svojo pot skozi zlivanjem. 

Doug: sem pravkar storil. V redu je. Mi smo na dobri poti. Recimo samo, da valjanje. Tako nekako, 

IAN: Moraš razložiti bolj polno, kot da. To preprosto ni dovolj. Doug: Ian, ne bomo morali iti nazaj v enem. V redu je. Torej nekako, če bomo nadaljevali s merge-- Ian, smo sredi snemanja. 

IAN: Vem. In ne moremo samo ya-da, ya-da, ya-da, skozi celoten proces. Moraš pojasniti, kako je Obe strani sta se združili skupaj. 

Doug: Ampak smo že pojasnil, kako sta sides-- 

IAN: Pravkar ste prikazani jim omogoča spajanje nizov. Doug: Poznajo postopek. Oni so v redu. Šli smo nad njim desetkrat. 

IAN: Pravkar si preskočila prav nad njim. Gremo nazaj v eno, Ne morem vam ya-da, ya-da nad njim. V redu, nazaj v enem. 

Doug: Moram iti nazaj skozi vse diapozitivov? Moj Bog. To je, kot že šestič, Ian. V redu je. 

IAN: V redu. Ste pripravljeni? Great. Ukrepanje.