1. Előadó: Rendben, tehát ez CS50 Ez a hét végén öt. És emlékszem, hogy utoljára nekilátott a galambász adatok struktúrák indult, hogy megoldja problémákat, hogy kezdte el bevezetni új problémák, de a legfontosabb, hogy ezt az a fajta threading, hogy mi kezdett hozzá csomópontok. Szóval ez persze egyszeresen láncolt lista. És egyszeres kapcsolódik, Úgy értem, nem csak egy menet között minden egyes ilyen csomópontok. Kiderült, amit tehetünk cifrább dolgok, mint kétszeresen láncolt listák ahol van egy nyíl mindkét irányban, amely segíthet bizonyos hatékonyságot. De ez megoldotta a problémát? Mi a gond viszont ezt megoldani? Miért érdekel hétfőn? Miért, elvileg, nem törődünk hétfőn? Mit csinal? 

Közönség: Mi lehet dinamikusan méretét. 

1. Előadó: OK, így tudjuk dinamikusan méretét. Jól sikerült mind a ketten. Szóval lehet dinamikusan átméretezni ezt adatszerkezet, mivel egy sor, Emlékezzünk, tudnod kell a priori, hogy mennyi helyet szeretne és ha kell még egy kis helyet, te ilyen szerencséje. Létre kell hozni egy teljesen új tömb. Meg kell mozgatni az összes az adatokat az egyik a másikra, végül szabad a régi tömb ha tudsz, majd folytassa. Ami csak úgy érzi, nagyon költséges és nagyon nem hatékony, és valóban az is. De ez még nem minden jó. Mi árat fizetnek, mi volt az egyik a nyilvánvaló árak is fizetni egy láncolt lista? 

Közönség: Meg kell használni dupla helyet mindegyik. 1. Előadó: Igen, így van szükségünk legalább kétszer annyi helyet. Sőt, rájöttem, hogy ez kép még egy kicsit félrevezető, mert a CS50 IDE a sok modern számítógépek, egy mutatót vagy címet valójában nem négy bájt. Nagyon gyakran ezek nap nyolc bájt, amely : a legalsó téglalapok ott a valóságban a fajta kétszer akkora, mint amit én kiállított, ami azt jelenti, amit használ háromszor sok helyet, mint talán van más módon. Most ugyanabban az időben, vagyunk Még mindig beszél bájt, ugye? Mi nem feltétlenül beszél megabájt vagy gigabájt, kivéve, ha ezek az adatok struktúrák kap nagy. 

És így ma elkezdjük vizsgálni hogyan lehet felfedezni adatok hatékonyabban, ha a Valójában az adatok nagyobb lesz. De nézzük meg, hogy canonicalize A műveletek első hogy meg tudod csinálni a következő típusú adatok struktúrákat. Szóval olyasmi, mint egy kapcsolt lista általában támogatja műveletek, mint a törlés, helyezze, és keresni. És mit jelent az, hogy? Ez csak azt jelenti, hogy általában, ha az emberek a láncolt lista, ők vagy valaki más által végrehajtott funkciók, mint a törlés, betét, és a keresés, így Ön valóban tenni valamit hasznos az adatszerkezet. Szóval vessünk egy gyors pillantást meg, hogyan lehet végrehajtani Néhány kódot egy láncolt lista a következőképpen. 

Szóval ez csak néhány a C kód, Nem is egy komplett program hogy igazán gyorsan felkorbácsolta. Ez nem online forgalmazás kódot, mert nem a ténylegesen megtett. De észre Épp most egy megjegyzést mondta, dot dot dot, van valami ott, pont pont pont, ott valami. És nézzük csak nézd meg mi a szaftos részek. Tehát a sorban három, Emlékeztetünk arra, hogy ez most Javasoltuk nyilvánító csomópont utolsó ideje, az egyik ilyen téglalap alakú tárgyat. Meg van egy int, hogy fogjuk hívni N, de nevezhetjük bárminek, majd a struct csomópont csillagos nevezett következő. És csak hogy tisztázzuk, hogy a második vonal, a soros hathengeres, mi ez? Mit tesz nekünk? Mert úgy néz ki több rejtélyes, mint a szokásos változók. 

Közönség: Azt teszi, hogy mozogni több mint egy. 

1. Előadó: Azt teszi, hogy mozogni több mint egy. És pontosabban, akkor tárolja a címét A csomópont, amely azt jelentette, hogy szemantikailag mellette, igaz? Szóval ez nem fog feltétlenül mozognak semmit. Ez csak fog értéket tárolnak, amely lesz a cím néhány más csomópont, és ezért mondtunk struct node csillag, a csillag jelöli egy mutató, vagy egy címet. OK, így most, ha feltételezzük, hogy van Ebben az N elérhető számunkra, és nézzük Feltételezem, hogy valaki másnak beilleszteni egy csomó egészek egy láncolt lista. És hogy kapcsolódik lista Rámutatott, hogy néhány ponton változó nevű lista, amelyet telt itt, mint a paraméter, hogyan megy a vonalon 14 végrehajtási keresés? Más szóval, ha én végrehajtási függvény, amelynek célja az életben az, hogy egy int, majd a elején egy láncolt lista, hogy egy mutató a láncolt lista. Mint az első, aki azt hiszem, David volt önkéntesünk hétfőn, ő mutat Az egész láncolt lista, olyan, mintha mi halad Dávid az érveink itt. Hogyan érjük el áthaladó ez a lista? Nos, kiderült, hogy bár mutatók viszonylag új most nekünk, ezt meg tudjuk tenni, viszonylag egyenesen. 

Megyek megy előre, és Kijelentem, ideiglenes változó, egyezményesen csak megy hogy hívják mutató vagy PTR, de lehet nevezni, amit akarsz. És fogok alaphelyzetbe azt a kezdetét a lista. Szóval lehet egyfajta gondolom, ennek a mint én a tanár a minap, fajta mutatva valaki körében emberek önkéntesként. Szóval egy átmeneti változó, ami Csak mutatva ugyanezt hogy a véletlenül nevezték önkéntes Dávid is rámutatva. Most, miközben mutató nem nulla, mert visszahívás hogy null valamilyen különleges sentinel értéke A behatároló a lista végén, így amíg nem vagyok mutatva földön, mint az utolsó önkéntes volt, menjünk előre és tegye a következőket. Ha pointer-- és most valahogy akarnak hogy amit tettünk a diák structure-- ha a mutató melletti pont equals-- inkább, ha a mutató dot N egyenlő egyenlő az n változó, a érv, hogy a már elfogadott, akkor azt akarom, hogy menjen előre és azt mondják vissza igaz. Találtam száma N belsejét egyik csomópont én láncolt lista. De a dot már nem működik ebben az összefüggésben, mert mutatót, PTR, van Valóban egy mutató, cím, mi valójában is csodálatosan Használja végül egy darab szintaxis ez a fajta gyártmányú ösztönösen érzi, és ténylegesen Használja a nyíl itt, ami azt jelenti, megy ezt a címet az egész, ott. Tehát ez nagyon hasonlít a szellem a dot-üzemeltető, hanem azért, mert a mutató nem egy pointer és nem a tényleges struct magát, csak használja a nyíl. 

Tehát, ha az aktuális csomópont, hogy én, az ideiglenes változó, am mutatva nem N, mit akarok csinálni? Nos, az én emberi önkéntesek hogy mi volt itt a minap, Ha az első emberi nem az általam szeretnénk, és talán a második ember nem Az egyik azt akarom, és a harmadik, én kell tartani fizikai mozgatása. Mint hogyan lépek a listában? Amikor volt egy tömb, csak tettem, mintha én plus plus. De ebben az esetben elegendő, ha nem mutató, kap, mutató, a következő. Más szóval, a következő mező olyan, mint minden a bal kezében hogy emberi önkéntesek hétfőn -a használta, hogy rámutasson néhány más csomóponton. Ezek voltak azok a következő szomszédok. 

Tehát, ha azt akarom, hogy menj végig a listán, Nem tudok csak tudom plus plus többé, Azt kell, hogy mondjam helyett Azt, mutató, folyik hogy egyenlő függetlenül a következő mező, A következő mező, a következő mező, következő mindazoknak bal keze hogy mi volt a színpadon mutatóeszköz Egyes későbbi értékeket. És ha én átjutni hogy egész iterációnál és végül, elütöttem null nem rendelkező megtalált N mégis, én csak vissza hamis. Szóval megint minden, amit mi csinálunk itt, mint egy a kép egy perce kezd mutatva a a lista elején feltehetően. És akkor ellenőrizze, ez az érték Keresem egyenlő kilenc? Ha igen, azt vissza igaz, és kész vagyok. Ha nem, akkor frissítem a kezem, AKA mutatót, hogy pont A következő nyíl helyét, és akkor a következő nyíl helyét, és a következő. Én egyszerűen csak séta ezt a tömböt. 

Tehát újra, kit érdekel? Mint mi ez az összetevő,? Nos, emlékszem, hogy mi vezetett fogalmának egy halom, amely egy absztrakt adattípus, amennyiben ez nem egy C dolog, hogy ez nem egy CS50 dolog, ez egy elvont elképzelés, ez az ötlet egymásra dolgokat egymás tetejére hogy lehet végrehajtani fürtök különböző módon. És egy út javasoltuk volt egy tömb, vagy egy láncolt lista. És kiderül, hogy kanonikusan, a verem támogatja legalább két művelet. És a buzz szavak push, hogy nyomja valami a verembe, mint egy új tálcát a étkezőben, vagy a pop, ami azt jelenti, hogy távolítsa el a legfelső tálcát a verem az étkezőben hall, majd talán néhány Más műveletek is. Tehát hogyan tudnánk szerkezetét meghatározó hogy mi most hív egy köteg? 

Nos, mindannyian a szükséges szintaxis a rendelkezésünkre a C. mondom, adj egy típus meghatározása Egy struct belsejében egy köteg, Azt fogom mondani egy tömb, egy csomó szám, majd méretét. Más szóval, ha azt akarom, végrehajtani ezt a kódot, hadd menjen, és csak ilyen felhívni, hogy ez mit mond. Tehát ez azt mondja, hogy nekem egy szerkezet, van egy tömbben, és én nem tudom, mi kapacitása, ez nyilván valami állandó, hogy én már máshol definiált, és ez jó. De tegyük fel, hogy csak egy, két, három, négy, öt. Tehát kapacitása 5. Ez az elem belső én struktúrát kell hívott számokat. És akkor kell egy egyéb változó láthatóan nevű méretű, hogy kezdetben megyek kikötni nullára inicializálunk. Ha nincs semmi a verem, mérete nulla, és ez szemét értékeket számokban. Fogalmam sincs, hogy mi van benne, csak még. 

Tehát ha azt szeretné, hogy álljon valamit a verembe, hiszem, hívja a funkciót push, és Mondom tolja 50, mint a 50-, ahol javasolna Én felhívni, hogy ebben a tömbben? Van öt különböző lehetséges válaszok. Hol szeretné, hogy álljon a szám 50? Ha a cél itt, újra, hívja a funkciót push, át egy érvet 50, hová tegyem meg? Öt possible-- 20% -os valószínűséggel találgatás helyesen. Igen? 

Közönség: szélsőjobb. 

1. Előadó: szélsőjobb. Van most egy 25% esélye találgatás helyesen. Tehát, hogy valójában minden rendben lesz. Megegyezés alapján, azt mondom egy sor, mi lenne általában kezdeni a bal, de minden bizonnyal kezdeni a megfelelő. Tehát a spoiler itt lenne vagyok valószínűleg fog rajzolni a bal oldalon, Csak úgy, mint egy normális tömb, ahol Én indulj balról jobbra. De ha a flip számtani, finom. Ez egyszerűen nem hagyományos. OK, azt kell, hogy egy További változás mégis. Most, hogy már tolta valamit a verembe, mi a következő lépés? 

Rendben, azt kell növelni a méretét. Szóval hadd menjen előre, és csak frissíteni ezt, ami nulla volt. És ahelyett, hogy most, megyek hogy hozzanak értéke egy. És most tegyük fel, megnyomom a másik szám a verembe, mint a 51. Nos, azt kell, hogy még egy változás, amely legfeljebb akkora, kettő. És akkor hiszem tolja még egy szám a verembe, mint 61, most kell frissíteni a méret még egy ideje, és kap az érték 3, mint a méret. És most tegyük fel, hívom a pop. Most pop, megállapodás szerint, nem veszi érv. A verem, az egész pont a tálca metafora az, hogy nincs mérlegelési jogköre menni fog, hogy tálcán, minden, amit tehetünk a pop a legfelső egyet a verem, csak azért, mert. Ez az, amit ez az adat struktúrára. 

Tehát, hogy a logika, ha mondjuk pop, mi jön ki? Tehát 61. Szóval mi tényleg a számítógép fog tenni a memóriában? Mit jelent a kódot kell csinálni? Mit javasolna megváltoztatjuk a képernyőn? Mit kell változtatni? Bocsánat? Így megszabadulunk 61. Szóval tudom biztosan csinálni. És tudok megszabadulni a 61. És akkor mi más változás kell történnie? Méret valószínűleg visszamenni kettő. És így ez rendben van. De várj egy percet, méret Egy perccel ezelőtt volt, három. Nézzük csak egy gyors józanság csekket. Honnan tudjuk, hogy akart megszabadulni a 61? Mert mi popping. És így van ez a második ingatlan alapterülete. 

Várj egy percet, én vagyok gondoltam vissza a héten két amikor elkezdtünk beszélni tömbök, ahol ez volt helye nulla, ez volt az egyik helyen, ez volt helye két, ez helyen három, négy, úgy néz ki, mint a közötti kapcsolat méret és az elem, hogy szeretnék eltávolítani A tömb tűnik, hogy csak legyen mit? Méret mínusz egy. És ez az, hogyan, mint az emberek Tudjuk 61 az első. Hogy a számítógép fog tudni? Amikor a kódot, ahol valószínűleg akarok mérete mínusz egy, így három mínusz egy két, és hogy a azt jelenti, hogy szeretne megszabadulni a 61. És akkor valóban frissítheti A méretet úgy, hogy mérete most megy háromról csak két. És csak azért, pedáns, megyek azt javasolni, hogy kész vagyok, ugye? Akkor javasolt ösztönösen helyesen kéne megszabadulni 61. De nincs Valahogy fajta ütött megszabadulni 61? Már elfelejtkeznek hogy ez valóban létezik. És hiszem, vissza PSET4, ha elolvastátok A cikket a kriminalisztika, a PDF- hogy mi volt a srácok olvasni, vagy fogja olvasni ezen a héten PSET4. Emlékezzünk vissza, hogy ez valójában valaminek megfelelő Az egész ötlet a számítógép kriminalisztika. Mi a számítógép általában nem az, ez csak elfelejti, hol valami, de ez nem megy, és hasonlók próbáljuk megkarcolni ki vagy felülírás ezeket a biteket a nullák és egyesek vagy valamilyen más, véletlenszerű mintát hacsak te magad erre tudatosan. Tehát az intuíció volt Rendben, hogy megszabaduljunk a 61. De a valóságban, nem kell bajlódnia. Csak meg kell elfelejteni, hogy hogy ott van megváltoztatásával méretét. 

Most van egy probléma ezzel verem. Ha tovább nyomja a dolgokat a verembe, mi Nyilvánvalóan fog történni mindössze néhány pillanat az időben? Fogunk elfogy a hely. És mit tegyünk? Mi vagyunk a fajta csavarni. Ez a megvalósítás nem hagyja nekünk átméretezni a tömb, mert segítségével ezt a szintaxist, ha gondoljon vissza a heti két, ha egyszer már kijelentette, A tömb méretét, nem láttunk olyan mechanizmust még, ahol meg lehet változtatni a méret a tömb. És valóban C nem ezt a funkciót. Ha azt mondod, hogy nekem öt Nths, hívja őket számokat, Ez minden, amit akarsz kapni. Tehát mi most, mint a hétfő, van a képessége, hogy kifejezze a megoldás Bár, már csak be kell csípés meghatározása a verem hogy nem lehet néhány kódolt tömb, de csak tárolni egy címet. 

Most miért van ez? Most már csak azt kell kényelmes, Az a tény, hogy amikor a program fut, Én valószínűleg fog Meg kell kérdeznem az emberi, hány számot akarsz tárolni? Tehát a bemenő kell jönnie valahonnan. De ha már tudjuk, hogy szám, akkor én is csak Használja milyen funkciót adni nekem egy darab memória? Tudom használni malloc. És elmondhatom, bármennyi bájt akarom vissza ezekre Nths. És azt kell tárolni a számok változó itt belül ez a struktúra kell, hogy mit? Hogy valójában mi megy a szám ebben a forgatókönyvben? Igen, egy mutatót az első byte, hogy darab memória, vagy még pontosabban, a cím Az első ilyen bájt. Nem számít, ha ez az egyik bájt vagy egy milliárd byte-, Csak kell törődnünk az első. Mert amit malloc garanciák és az operációs rendszer garantálja, az, hogy a darab a memória I kap, akkor lesz egybefüggő. Ott nem lesz hiányos. Tehát, ha kértem 50 bájt vagy 1000 byte, ezek mind lesz vissza háttal. És mindaddig, amíg emlékszem, milyen nagy, milyen sokat kértem, csak annyit kell tudni, az első ilyen címet. 

Tehát most már képes a kódot. Jóllehet, ez fog minket Több időm írni ezt fel, tudnánk teremteni átcsoportosítása, hogy az emlékezet által Csak tárolása eltérő címre van ha azt akarjuk, egy nagyobb, vagy akár egy kisebb darab memória. Tehát itt egy kompromisszum. Most, hogy a dinamizmus. Még mindig van contiguousness Én azt állítva. Mivel malloc ad nekünk egy folytonos darabkája memória. De ez lesz a fájdalom A nyak számunkra, a programozó, hogy ténylegesen kódot fel. Ez csak több munkát. Szükségünk van-kód hasonlít ahhoz, amit én dörömböl ki csak egy pillanattal ezelőtt. Nagyon megvalósítható, de hozzáteszi, komplexitás. És így fejlesztő időt, programozó ideje egy újabb erőforrás hogy mi szüksége lehet tölteni egy kis időt, hogy új funkciókat. És persze van egy sorban. Nem fogunk menni ebbe egy a sok részlet. De ez nagyon hasonlít a szellem. Nem tudtam végrehajtani a sorba, és a megfelelő műveleteket, Enqueue vagy dequeue, mint felvenni vagy eltávolítani, ez csak egy szakértő szóval ez, Enqueue vagy dequeue, az alábbiak szerint. Én is csak adok magamnak egy struct hogy ismét van egy szám tömb, hogy ismét a mérete, De miért most kell nyomon követni az első sorban? Nem kell tudni Az első az én verem. Hát, ha ismét egy queue-- nézzük csak kemény kódolnod, mint amelyek, mint öt Egész számok itt potenciálisan. Tehát ez nulla, egy, kettő, három, négy. Ez lesz hívott számokat újra. És ez lesz az úgynevezett mérete. 

Miért nem elegendő hogy csak méretet? Nos, nézzük nyomja ugyanezen számok. Szóval pushed-- I enqueued, vagy tolt. Most akkor sorba állítását 50, majd 51, majd 61, és pont pont pont. Szóval ez Enqueue. Én enqueued 50, majd 51, majd 61. És hogy néz ki, hogy egy rakás eddig, csak én szükség, hogy egy változás. Azt, hogy frissíteni kell ezt a méretet, így megyek nulláról 1-2, hogy három most. Hogyan dequeue? Mi történik a dequeue? Kinek kell lejönni először a listán ha ez a vonal az Apple Store? Tehát 50. Szóval ez a fajta trükkösebb ebben az időben. Mivel utoljára ez szuper volt egyszerűen csak nem mérete mínusz egy, Azt, hogy a végén az én tömb hatékonyan ahol a számok, hogy eltávolítja 61. De nem akarom, hogy távolítsa el 61. Azt akarom, hogy 50, akik ott volt 05:00 sorban a új iPhone vagy miegymás. És így, hogy megszabaduljon a 50, I Nem csak ezt, ugye? Én is kihúz 50. De mi csak azt mondta, Nem kell, hogy így legyen anális hogy kihúz vagy elrejtheti az adatokat. Mi is csak elfelejteni, hol van. 

De ha tudom megváltoztatni a mérete most Két, ez elegendő információ tudni, hogy mi folyik az én sorban? Nem igazán. Mint a mérete két, hanem hol a sorban kezdődik, különösen, ha még mindig van ugyanezek a számok a memóriában. 50, 51, 61. Szóval kell emlékezni Most, amikor a front. És ahogy javasoltam fel ott vagyunk, már csak úgynevezett N-edik előtt, akinek az első értéket kellett volna, mi? Zero, csak a lista elején. De most amellett, hogy csökkentjük a méret, csak növeljük az első. Most itt van egy másik probléma. Tehát ha én folyamatosan megy. Tegyük fel, ez az a szám, mint 121, 124, majd, a fenébe is, Én vagyok a hely. De várj egy percet, nem vagyok. Tehát ezen a ponton a történet, tegyük fel, hogy a mérete egy, kettő, három, négy, így feltételezzük, hogy a mérete négy, az első az egyik, így 51 elöl. Azt szeretnénk, hogy egy másik számot itt, de a fenébe is, én vagyok a hely. De nem igazán vagyok, ugye? Hol tudnék némi hozzáadott érték, mint a 171? Igen, én is csak ilyen menj vissza oda, ugye? Majd húzza át a 50, vagy Csak írja felül 171. És ha kíváncsi vagy, miért a számok annyira véletlenszerű, Ezek általánosan vett számítógép tudományos képzés, a Harvard után CS50. De ez egy jó optimalizálás, mert most nem vagyok kiesik hely. Még mindig kell emlékezni milyen nagy ez a dolog teljes. Ez összesen öt. Mert nem akarom, hogy felülírását kezdi 51. Szóval most én vagyok még szabad terület, így ugyanaz a probléma, mint korábban. De láthatod, hogy most a kódban, akkor valószínűleg Meg kell írni egy kicsit komplexitás, hogy ez megtörténjen. És valóban, mi üzemeltető C valószínűleg lehetővé teszi, Ön varázslatosan ezt a körkörösség? Ja moduló, A százalékos jel. Szóval mi egyfajta hűvös egy sorban, még akkor is megtartjuk rajz tömbök mivel ezek, mint egyenesek, ha fajta gondolni ezt a kanyargós körül, mint egy kör, akkor csak ösztönösen azt a fajta működik mentálisan Azt hiszem, egy kicsit tisztábban. Azt még meg kell végrehajtani hogy a mentális modell kódot. Szóval nem is olyan nehéz, végül, hogy végre, de még mindig elveszítik a size-- inkább a képes átméretezni, kivéve, ha ezt tesszük. 

Van, hogy megszabaduljon a tömb, akkor helyette egy egységes mutatót, majd valahol a kódomat kaptam Egy hívják, amit úgy működnek, hogy valóban létre A tömb hívott számokat? Malloc, vagy valamilyen hasonló funkciót, pontosan. Bármilyen kérdésre halom, vagy sorokat. Igen? Jó kérdés. Mit modulo kíván használni itt. Tehát általában akkor, ha a mod, akkor csináld a méret a egész adatstruktúra. Szóval valami ilyesmi öt vagy kapacitás, ha ez állandó, valószínűleg részt. De csak ezzel modulo öt Valószínűleg nem elegendő, mert tudnunk kell, hogy mi is kerületi itt vagy itt vagy itt. Szóval akkor valószínűleg azt is akarnak bevonni A méret a dolog, vagy az elülső változó is. Tehát csak ez a viszonylag egyszerű aritmetikai kifejezés, de modulo lenne a legfontosabb összetevő. 

Tehát rövidfilm, ha lesz. Egy animáció, hogy egyes hozzátartozók egy másik egyetemen össze, hogy már adaptált ezt a vitát. Ez magában foglalja a tanulás a Jack tényeket sorok és a statisztikák. 

FILM: Once upon a time, volt egy srác nevű Jack. Amikor eljött a barátkoznak, Jack nem egy trükk. Szóval Jack elment, hogy beszéljen a Népszerű fickó, akit ismert. Elment Lou, és megkérdezte, mit tegyek? Lou látta, hogy a barátja tényleg szomorú. Nos, ő kezdte, csak nézd, milyen úgy nézel ki. Ne bármilyen ruhát egy másik pillantást? Igen, mondta Jack. Én biztos nem. Gyere a házamba, és Majd én megmutatom nektek. Így elmentek Jack. És Jack megmutatta Lou mezőbe hol tartja minden ingek, és a nadrágját, és a zokniját. Lou, látom, hogy van az összes ruhát egy halom. Miért nem viselnek néhány mások egyszer egy kicsit? 

Jack azt mondta, jól, amikor én ruházatot eltávolítani és zokni, Én mosom őket, és tedd őket a dobozba. Aztán jön a következő Reggel, és akár azt hop. Megyek a dobozt, és kap ruhámat a tetején. Lou gyorsan rájött, A probléma Jack. Folyton ruhát, CD-k, és könyvek a veremben. Amikor elérte a valamit olvasni, vagy viselni, Ő dönt, az első könyv, vagy fehérnemű. Aztán amikor végzett, ő mondaná vissza. Vissza menne, a tetején a verem. Tudom, hogy a megoldás, mondta diadalmas Loud. Meg kell tanulni, hogy kezdi el használni a sorban. Lou vette Jack ruháit és lógott a szekrénybe. És mikor kiürítették A doboz, ő csak dobta. 

Aztán azt mondta, most már Jack, a végén A nap ruháit a bal ha fel őket. Akkor holnap reggel, amikor lásd a napsütés, hogy a ruhák a jobb oldalon, a sor végére. Hát nem látod? mondta Lou. Ez lesz olyan szép. Majd viselni mindent egyszerre Mielőtt viselni valamit kétszer. És mindent sorba a szekrényében, és polc, Jack kezdte érezni egészen biztos magában. Minden köszönhetően Lou és ő csodálatos sorban. 1. Előadó: Rendben, ez imádnivaló. Szóval mi már tényleg lesz A a motorháztető alatt most? Hogy van mutatók, hogy van malloc, hogy megvan a képessége, hogy hozzon létre darabokat a memória magunkat dinamikusan. Tehát ez egy kép, amit megpillantotta csak a minap. Nem igazán él rajta, de ez a kép már folyik alatta A motorháztető hete. És így ez azt jelenti, csak egy téglalapot, amit rajzolt, a számítógép memóriáját. És talán a számítógép, illetve CS50 ID, egy gigabájt memória vagy RAM vagy két gigabájt vagy négy. Ez nem igazán számít. Az operációs rendszer Windows vagy Mac OS vagy Linux, lényegében lehetővé teszi a programot gondolni, hogy hozzá tud hogy a teljes egészében a számítógép memóriájában, még akkor is lehet, hogy fut több program egyszerre. Így a valóságban, hogy nem igazán működik. De ez a fajta illúzió fordítani az összes programot. Tehát, ha két giga RAM, ez a az, hogy a számítógép lehet, hogy belegondolok. 

Most véletlenül, az egyik ilyen dolgok, az egyik ilyen szegmensek memória, nevezzük verem. És valóban bármikor Eddig írásban kódot hogy felhívta a funkciót, például a fő. Emlékezzünk vissza, hogy minden alkalommal, amikor már húzott számítógép memóriája, Én mindig felhívni a fajta felében egy téglalap itt és nem zavarja, beszél mi van fent. Mert amikor fő hívják, azt állítják, hogy ezt kapod szelet memória hogy megy le itt. És ha fő nevezett funkció mint a swap, illetve a swap megy itt. És kiderül, hogy ez ahol ez kiöntött. On egy úgynevezett verem belsejében a számítógép memóriáját. Most a végén a nap, ez csak címek. Ez olyan, mint byte nulla, byte hosszú, byte 2 milliárd. De ha belegondolunk mivel ez téglalap alakú tárgyat, Az összes csinálunk minden alkalommal hívunk funkció rétegződés új szelet memória. Adunk, hogy a funkció egy szelet saját memóriával dolgozni. 

És emlékszem most, hogy ez fontos. Mert ha van olyasmi, mint a swap és két helyi változók, mint az A és B megváltoztatjuk ezeket az értékeket egy és két két és egy, visszahívás hogy amikor a swap visszatér, olyan, mintha ez a szelet A memória csak elmentek. A valóságban ez még mindig ott forensically. És valami még valóban ott. De fogalmilag, ez olyan mintha ez teljesen eltűnt. És így fő nem ismer a munka hogy azért került sor, hogy a swap, kivéve, ha ez valóban telt azokban érvek mutató által vagy utalásokkal. Most, az alapvető megoldás hogy ezt a problémát a swap- Múlik a dolgokat a címet. De kiderült, túl, mi óta tart fent az a része, A téglalap egész idő alatt Még van több memóriát odafent. És ha dinamikusan memóriát foglalni, legyen szó belsejében getString, amely mi már ennek az Ön számára a CS50 könyvtár, vagy ha a fiúk hívja malloc és kérje Az operációs rendszer egy darab memória, ez nem jön a veremből. Jön egy másik helyre a számítógép memóriájában hogy hívják a kupac. És ez még nem minden más. Ez ugyanaz a RAM. Ez ugyanaz a memória. Ez csak a RAM, ami akár ott, hanem itt lent. 

És ez mit jelent? Nos, ha a számítógép véges mennyiségű memória és a verem nő fel, így beszélni, és a kupac szerint hogy ezt a nyilat, növekszik le. Más szavakkal, minden alkalommal, amikor hívást malloc, te is kap egy szelet memória felülről, akkor talán egy kicsit alacsonyabb, majd egy kicsit alacsonyabb, minden alkalommal, amikor hívást malloc, A kupac, ez a használat, a fajta nő, egyre közelebb és közelebb, mi? A verem. Így jelent ez úgy tűnik, mint egy jó ötlet? Úgy értem, ahol ez nem igazán világos, mi mást tehet, ha csak Van egy véges mennyiségű memóriát. De ez biztosan rossz. Ez a két nyíl a gyorstalpaló egymásért. 

És kiderül, hogy a rosszfiú, emberek, akik különösen jó a programozás, és akarja feltörni a számítógépeket, lehet kihasználni ezt a valóságot. Tény, hogy nézzük meg egy kis részlet. Szóval ez egy példa lehet olvasni mintegy részletesebben a Wikipedia. Majd pont akkor a cikket, ha kíváncsi. De van egy támadás általában néven puffer túlcsordulás, hogy létezett ameddig emberekben volt képes manipulálni számítógép memóriájában, különösen a C. Tehát ez egy nagyon önkényes programot, de most olvasni alulról felfelé. Fő be argC char csillagos argv. Szóval ez egy program, mely parancssori paramétereket. És a legfontosabb jelent látszólag hívás függvényében, nevezzük az egyszerűség kedvéért F. És ez megy, mi? Argv egy. Így bejut F bármi a szó, hogy a felhasználói gépelt A prompt után Szak neve egyáltalán. Annyira, mint Caesar vagy Vigenère, amely talán felidézni csinál argv. 

Tehát mi F? F vesz egy húr mint a kizárólagos érvet, AKA egy char csillag, ugyanazon dolog, mint egy húr. És ezt hívják önkényesen Bár ebben a példában. És akkor char c 12, Csak a laikus szempontból, mi char c konzol 12 csinál nekünk? Mi csinál? Memórialefoglalás, konkrétan 12 byte 12 karakter. Pontosan. És akkor az utolsó sort, majd kevergetve másolatot, akkor már valószínűleg nem látta. Ez egy szöveg másolata függvény, amelynek célja az életben az, hogy másolja a második érv be az első érv, de csak egy bizonyos számú bájt. Így a harmadik érv azt mondja, hány bájtot kell másolni? A hossza bár, amit a felhasználó beírt. És a tartalmát bár, hogy a húr, amelyek bemásolja a memóriában mutatott a C. 

Szóval ez úgy tűnik, elég hülyén, és ez. Ez egy kitalált példa, de ez képviselője egy osztály a támadási, módon támadó egy programot. Minden rendben van, és jó, ha a felhasználó típusok egy szó, ami 11 karakter vagy kevesebb, plusz a backslash nulla. Mi van, ha a felhasználó beírja a több mint 11 vagy 12 vagy 20 vagy 50 karakter? Mi ez a program fog csinálni? Potenciálisan seg hiba. Működik hogy vakon másolni mindent bar a hosszával, amely a Szó szerint mindent bár, a címet mutatott C. De C csak megelőző jellegű adják 12 bájt. De nincs külön ellenőrizni. Nincs ha a körülmények. Nincs hibaellenőrzési itt. 

És akkor mi ez a program eredménye, hogy vakon másolni egy dolog, hogy a többi. És így, ha felhívjuk ezt képként, itt Csak egy szeletkét a memóriát. Tehát észre az alján, mi Van egy helyi változó bárban. Szóval ez a mutató, hogy fog store-- inkább az, hogy a helyi érv, hogy ez fog tárolni a húr bárban. És akkor észre csak fölötte egy verem, mert minden alkalommal, amikor kérni A memória a veremben, megy egy kicsit fölötte képileg, észre, hogy megvan a 12 byte van. A bal felső az egyik C konzol nulla és ki a jobb alsót C konzol 11. Ez csak, hogy a számítógépek majd feküdt ki. Tehát csak ösztönösen, ha bár több mint 12 karakter összesen, beleértve a A backslash nulla, hol van a 12 vagy a C konzol 12 fog menni? Vagy inkább, ahol a 12- karakter vagy a 13. karaktert, A századik karaktert fog hogy a végén a képen? Alatt vagy felett? 

Jobb, mert bár A verem magát növekszik felfelé, ha egyszer már fel cuccot , ez a dizájn miatt helyezi a memória felülről lefelé. Tehát, ha már van több mint 12 bájt, fogsz kezdeni, hogy felülírja bárban. Most, hogy egy hiba, de ez Nem igazán nagy dolog. De ez egy nagy dolog, mert van Több dolog történik a memóriában. Tehát itt, hogy hogyan tudnánk tedd hello, hogy egyértelmű legyen. Ha beírtam helló a billentyűket. H-E-L-L-O backslash nulla, végül belül a 12 byte, és mi szuper biztonságos. Minden rendben. De ha én írja valamit hosszabb, esetleg ez fog szivárogni a bárban helyet. De ami még rosszabb, kiderül az összes ebben az időben, még akkor is, soha nem beszéltünk ez a verem használják egyéb dolgokat. Ez nem csak a helyi változókat. 

C egy nagyon alacsony szintű nyelven. És ez a fajta titokban használja a verem is emlékezni, amikor egy funkciót nevezik, mi A cím az előző funkciót, így ugrik vissza, hogy a funkció. Tehát amikor a fő hívások cserélni között A dolgok a verembe nem csak felcseréli a helyi változókat, vagy érveit, szintén titokban tolta a verembe képviselt A piros szelet itt, a címe fő fizikailag a számítógép memóriájában, úgy, hogy amikor a swap történik, a számítógép tudja, hogy vissza kell mennie a fő és befejezni a végrehajtó a fő funkciója. Szóval ez veszélyes most, mert ha a felhasználó által is több mint hello, úgy, hogy a felhasználó által megadott clobbers vagy felülírja, hogy piros pont, logikusan, ha a számítógép csak fog vakon vállalnak hogy a bájtok a piros szelet is a címet, amelyre ad vissza, mi van, ha az ellenség elég okos ahhoz, vagy szerencsés, hogy egy bájtsorozatok van, hogy néz ki, mint egy cím, de ez a címe kód hogy ő akarja a számítógép hogy végre ahelyett fő? 

Más szóval, ha az, amit az felhasználó beírja a parancssorba nem csak valami ártalmatlan, mint a Hello, de ez valójában kódot, ami egyenértékű törölni mindezt a felhasználó fájljai? Vagy e-mailben a jelszót, hogy nekem? Vagy indul naplózása billentyűleütéseket, ugye? Van egy módja, hadd kikötik ma, hogy tudtak írja nemcsak helló világ, vagy a nevüket, tudtak lényegében át a kódot, és nullák is, hogy a számítógép hibák mindkét kódot, és egy címet. Így bár kissé absztrakt, ha a felhasználó beír elég ellenséges kódot hogy mi lesz általánosítani itt A. A jelentése támadás vagy ellenfelek. Tehát csak rossz dolgokat. Nem érdekel a számát vagy a nullát vagy egyest ma, mint, amit a végén felülírását, hogy piros pont, észre, hogy bájtsorozatok. O 835 C nulla nyolc nulla. És most, ahogy a Wikipedia cikket itt azt javasolta, ha már tényleg kezd címkézéshez bájtok számítógép memória, amit a Wikipedia cikket javaslattevő, hogy mi van, ha a cím Az, hogy a bal felső bájt 80 C 0 3508. 

Más szóval, ha a rosszfiú elég okos a saját kódját hogy egyszerűen egy számmal, hogy itt megfelel a címet a kódot ő injektált a számítógépbe, akkor trükk a számítógép csinál semmit. Eltávolítja a fájlokat, e-mailezés dolgokat, szippantás a forgalom, Szó szerint bármi lehet fecskendeznek a számítógép. És így a puffer túlcsordulás támadást középpontban ez csak egy hülye, hülye nyomós tömb, hogy Nem volt annak határait ellenőrizni. És ez az, ami szuper veszélyes és ezzel egyidejűleg szuper erős C-ben az, hogy valóban van hozzáférést biztosít bárhol a memóriában. Rajtunk múlik, hogy velünk, a programozók, akik írni az eredeti kódot hogy ellenőrizze a rohadt hosszú bármely tömbök, hogy mi manipulálni. Tehát, hogy világos legyen, mi a fix? Ha visszaállíthatja erre kódot, amit nem kellene csak megváltoztatni a hossza bár, mit mást kéne megnézni? Mit kell még csinálni, hogy ennek kivédésére teljesen? Nem akarom, hogy csak vakon mondani hogy meg kell másolni annyi bájt mint a hossza bar. Azt akarom mondani, másolni, mint hány bájt, mint a bar akár a kiosztott memória, vagy 12 maximálisan. Szóval kell valami, ha állapota hogy nem ellenőrzi a hossza bár, de ha az meghaladja a 12, csak kemény kódot 12, mint a lehető legnagyobb távolságot. Ellenkező esetben az úgynevezett puffer túlcsordulás támadás megtörténhet. Alján a tárgylemezeket, Ha kíváncsi vagy, hogy tovább a tényleges eredeti cikk Ha azt szeretné, hogy vessen egy pillantást. 

De most, többek között az árak fordítani volt hiányosságok. Szóval ez volt a gyors alacsony nézd meg, mi problémák merülhetnek fel most, hogy férhetnek hozzá számítógép memóriájában. De egy másik probléma is Már megbotlott hétfőn csak az eredménytelenség A láncolt lista. Mi vissza a lineáris időt. Már nincs egy összefüggő tömbben. Nincs véletlen hozzáférésű. Nem tudjuk használni szögletes zárójel jelöléssel. Szó van, hogy egy while ciklus amilyet én írtam az imént. De hétfőn azt állította, hogy tudjuk kúsznak vissza a birodalmába hatékonyság elérése valamit, ami logaritmikus vagy talán eddigi legjobb, talán még valamit, ami úgynevezett konstans idő. Szóval hogyan lehet csinálni, hogy segítségével ezek az új szerszámok, ezeket a címeket, ezeket a mutatókat, és threading dolgokat a saját? Nos, tegyük fel, hogy Itt, ezek egy csomó A számok, hogy szeretnénk tárolni egy adatok szerkezete és keresés hatékonyan. Mi lehet teljesen visszatekerni a héten két, dobja ezeket egy tömbben, és keresni őket bináris kereséssel. Oszd meg és uralkodj. És valóban írtál bináris keresés PSET3, ahol végre a find programot. De tudod, mit. Van egyfajta többet okos módja ennek. Ez egy kicsit kifinomult és ez talán lehetővé teszi számunkra, hogy miért bináris Keresés annyira sokkal gyorsabb. Először is, hadd vezessen be a fogalom a fán. Mely, bár a valóság fák fajta nőnek, mint ez, a világ számítógép a tudomány azt a fajta nő lefelé mint egy családfát, ahol van, a nagyszülők vagy a dédszüleim vagy miegymás tetején, a pátriárka és A családfő anya a család, csak egy úgynevezett gyökér, csomópont, az alábbiakban amelyek a gyermekek, alatt, amelyek a gyermekek, illetve leszármazottai általában. És bárki lógott le az alján a család fa, amellett, hogy a legfiatalabb a családban, is csak legyen általánosan az úgynevezett levelek a fa. 

Tehát ez csak egy csomó A szavak és kifejezések valami úgynevezett fa számítógép a tudomány, mint egy családfát. De van cifrább inkarnációja a fák, amelyek közül az egyik az úgynevezett bináris kereső fa. És akkor milyen kötekedik eltekintve mi ez a dolog nem. Nos, ez a bináris milyen értelemben? Amennyiben ez a bináris származik itt? Bocsánat? Ez nem is annyira sem vagy. Ez több, hogy az egyes csomópontok nem rendelkezik Több mint két gyerek, mint látjuk itt. Általában egy tree-- és a szülők és nagyszülők Egyszerre annyi gyerek, vagy unoka, mert valójában akar, és így például ott van három a gyerekek ki, hogy jobb csomópont, de egy bináris fa, egy csomópont nulla, egy vagy két gyermek maximálisan. És ez egy jó tulajdonság, mert ha ez a két kupakkal, fogunk tudni egy kicsit napló bázis két akció folyik itt végül. Tehát van valami logaritmikus. De még az, hogy egy pillanat alatt. Keresés fa azt jelenti, hogy a számok elrendezve, hogy a bal oldali gyermek érték nagyobb, mint a gyökér. És a jobb fia nagyobb, mint a gyökér. Más szóval, ha Ön bármely csomópontok, a körök ezt a képet, és megnézi a bal gyermek és jobb fia, az első legyen kisebb, mint, a második nagyobbnak kell lennie, mint. Így a józanság ellenőrizheti 55. Ez maradt gyermek 33. Ez kevesebb, mint. 55, a jobb fia 77. Ez nagyobb, mint. És ez egy rekurzív definíció. Mi lehetett ellenőrizni minden egyike azoknak csomópontok és ugyanazt a mintát tartana. 

Szóval mi szép egy bináris kereső fa, az hogy az egyik, akkor végrehajtja egy struct, mint ez. És bár mi dobott Sok struktúrák a, ők valamelyest intuitív most remélhetőleg. A szintaxis mindig misztikus biztos, de a tartalmát egy csomópont ebben context-- és mi folyamatosan szó használata a csomópont, hogy ez egy téglalap a képernyőn, vagy egy kör, ez csak néhány általános tároló, Ebben az esetben egy fa, mint az egyik láttuk, szükségünk van egy egész szám az egyes csomópontok és aztán kell két mutató mutató balra a gyermek és a megfelelő gyermek, volt. Szóval így talán végre, hogy egy struktúra. És hogyan lehet azt megvalósítani, hogy a kódot? Nos, vessünk egy gyors nézd meg ezt a kis példát. Ez nem működőképes, de már vágólapra másolni, hogy a struktúra. És ha én a funkció egy bináris keresési fa az úgynevezett kereső, és ez a két paramétert, n egész és egy mutatót A csomóponthoz, így egy mutatót a fán vagy egy mutatót a fa gyökerét, hogyan megy körülbelül keresi N? Nos, először is, mert én vagyok foglalkozó mutatók, Azt fogom tenni a józanság csekket. Ha fa egyenlők egyenlő null, N a fán vagy nem a fán? Nem lehet, nem? Ha én vagyok már null, nincs ott semmi. Én akár azt is csak vakon mondják vissza hamis. Ha adsz nekem semmi, én biztosan nem találtunk száma N. Szóval mi mást én ellenőrizd most? Azt fogom mondani jól mást, ha N kevesebb, mint amit az a facsomópont hogy én már átadta N értéket. Más szóval, ha a szám én keres, az N, kevesebb, mint a csomópont hogy nézem. És a csomópont keresem A nevezik fa, és emlékszem az előző példában eljutni az értéket egy mutatót, Én a nyíl jelöléssel. Tehát, ha az N-nél kisebb fa nyíl N, azt akarom, hogy koncepcionálisan menni balra. Hogyan kifejezetten keresi maradt? Ahhoz, hogy tiszta, ha ez a kép a szóban forgó, és én már át, hogy a legfelső nyíl, ami lefelé mutat. Ez az én fa mutató. Én mutatott a gyökér a fa. És keresem mondjuk, száma 44, önkényesen. 44-nél kisebb, vagy nagyobb, mint 55 nyilvánvalóan? Szóval ez kevesebb, mint. És így ez, ha a feltétel. Tehát elméletileg, mit akarok keresés jövő, ha keresem 44? Igen? 

Pontosan, szeretnék keresés a bal gyermek, vagy a bal oldali részfa kép. És valóban, hadd keresztül A képet itt lent csak egy pillanatra, hiszen Nem tudom karcolja meg ezt. Ha elkezdek itt a 55., és a Tudom, hogy az érték 44 Keresem az, hogy A bal, ez a fajta hasonló tépte a telefonkönyvből fél- vagy könnyezés a fa felét. Én már nem kell törődnünk ezt az egész fele a fa. És mégis, kíváncsian szempontjából a szerkezete, ez a dolog itt, hogy kezdődik a 33., hogy maga egy bináris kereső fa. Azt mondta, a szó rekurzív előtt, mert Valóban ez egy adatstruktúrát, amely definíció rekurzív. Lehet, hogy egy fát, hogy ez nagy, de minden embernél a gyerekeknek jelent egy fa, csak egy kicsit kisebb. Ahelyett hogy a nagypapa vagy a nagymama, most már csak anya or-- nem tudok say-- nem anya vagy apa, hogy furcsa lenne. Ehelyett a két gyerek van lenne, mint testvére és a testvér. Az új generációs családfáját. De szerkezetileg, ez ugyanaz a gondolat. És kiderül, van egy funkció amellyel tudok keresni egy bináris keresés fa. Úgy hívják keresést. Én keresni N fa nyíl balra mást ha n értéke nagyobb, mint az érték hogy én vagyok jelenleg. 55 A történet egy perce. Van olyan függvény is kereső, amely tudok csak át N ezt, és rekurzív keresés Az al-fát, és csak vissza akármit is választ. Mást kaptam néhány végső alapeset itt. 

Mi a végső esetben? Fa vagy null. Az érték Engem sem keres kevesebb, mint ez, vagy nagyobb, mint a vagy egyenlő vele. És azt is mondhatnám egyenlő egyenlő, de logikusan ez egyenértékű csak azt mondom, itt még. Tehát igaz az, hogy hogyan találok valamit. Így remélhetőleg ez egy még vonzóbb például mint a hülye szigma funkció csináltunk egy pár előadásra vissza, ahol éppen olyan könnyen használható a hurok számoljon el a számokat az egyik N. Itt egy adatstruktúrát hogy maga rekurzív meghatározott és rekurzív húzott, most megvan a képessége, hogy kifejezze magunkat A kód, amely önmagában rekurzív. Tehát ez pontosan ugyanazt a kódot itt. 

Tehát mi más problémák tudjuk megoldani? Tehát egy gyors lépésre fák csak egy pillanatra. Itt van, mondjuk, a német zászló. És ott egyértelműen a minta ez a zászló. És van sok zászlók a világ, hogy olyan egyszerű, mint ez szempontjából a színek és minták. De tegyük fel, hogy ez tárolja a GIF, vagy JPEG, vagy bitmap, vagy egy ping, egy grafikus fájlformátum amellyel még nem ismeri, amelyek közül néhány vagyunk játszik a PSET4. Ez nem tűnik érdemes tárolni fekete pixel, fekete pixel, fekete pixel, dot, pont, pont, egy csomó fekete képpont az első soronkénti, vagy sor, akkor egy csomó ugyanaz, akkor egy csomó az azonos, majd egy csomó piros pixel, piros pixel, piros pixel, majd egy egész csokor sárga képpont, sárga, ugye? 

Van egy ilyen eredménytelenség itt. Hogyan írnád intuitívan tömöríteni a német zászló Ha azt végrehajtó fájlként? Például mit információt nem tudunk zavarja tárolása a lemezen érdekében csökkenti a fájl mérete, mint a egy megabyte egy kilobyte, valami kisebb? Ahol rejlik a redundancia Itt tisztázni kell? Mit tehetett volna? Igen? Pontosan. Miért nem inkább emlékezni a színe minden rohadt pixel mint te csinálsz itt PSET4 A bitmap file formátum, miért nem csak képviseli a bal szélső oszlopában pixel, például Egy csomó fekete képpontok, egy csomó vörös, és egy csomó sárga, és aztán csak valahogy kódolják ötlete ismételje ezt 100-szor vagy ismételje meg ezt a 1000-szer? Amennyiben 100 vagy 1000 van Csak egy egész szám, így lehet megúszni csak egy számot helyett száz vagy több ezer további pixel. És valóban, mi így lehet tömöríteni a német zászlót. És Most mi a helyzet a francia zászló? És egy kicsit valamiféle mentális gyakorlat, amely zászló lehet tömörített több lemezen? A német zászló, vagy a francia zászló, ha vesszük ezt a megközelítést? A német zászló, mert van több vízszintes redundancia. És a programok kialakítása, sok grafikus fájl formátumok valóban működik nevén képsorok vízszintesen. Tudtak dolgozni függőlegesen, csak az emberiség úgy döntött évvel ezelőtt, hogy mi lesz általában gondolni a dolgokat sorban által, hanem egymás oszlopról oszlopra. Tehát valóban, ha volt hogy nézd meg a fájl akkora, mint egy német és egy francia zászló zászló, mindaddig, amíg a felbontás az azonos, azonos szélességű és a magasság, ez az egy Itt lesz nagyobb, mert meg kell ismételni magát háromszor. Meg kell adnia a kék, ismételje magad, fehér, ismételje meg magad, piros, ismételje magát. Nem lehet csak úgy megy minden Az utat a jobb oldalon. És mint félre, hogy törölje a kompressziós mindenütt jelen van, ha ezek négy kép egy video-- akkor Lehet emlékeztetnek arra, hogy egy film vagy video általában mint 29 vagy 30 képkocka másodpercenként. Ez olyan, mint egy kis flip könyv, ahol csak lásd kép, kép, kép, képek, A kép csak szuper gyors, így néz ki A szereplők a képernyőn mozog. Itt egy poszméh a tetején egy csokor virágot. És bár lehet, hogy egyfajta nehéz belátni, hogy az első pillantásra, Az egyetlen dolog, mozgó ez a film a méhek. 

Milyen buta tárolásával kapcsolatban videó tömörítés nélkül? Elég egy hulladék tárolására videó négy, közel azonos képek különböznek csak annyiban, amennyiben a méh. Akkor dobja el a legtöbb Ezen információk és emlékszem csak, például, Az első keret és az utolsó képkocka, fő kereteket, ha már Hallottál már a szó, és csak tárolja az közepén, ahol a méh. És akkor nem kell tárolja az összes a rózsaszín, és a kék, és a zöld értékeket is. Tehát ez csak azt jelenti, hogy tömörítés mindenhol. Ez egy technika, gyakran használja vagy magától értetődőnek ezekben a napokban. 

De hogyan tömöríteni szöveget? Hogyan megy körülbelül tömörítése szöveget? Nos, mind a karakterek Az ASCII egy bájt, illetve nyolc bit. És ez a fajta buta, ugye? Mert akkor valószínűleg típusú és E I és O, U sokat gyakrabban, mint, mint a W vagy Q vagy Z, attól függően, hogy milyen nyelven írsz biztosan. És így miért is használ nyolc bit minden levelet, köztük a legkevésbé népszerű leveleket, ugye? Miért nem használ kevesebb bitet A szuper népszerű betűk, mint az E, a dolgok akkor hiszem, első Szerencsekerék, és több bitet A kevésbé népszerű leveleket? Miért? Mert mi csak fog használja őket ritkábban. 

Nos, kiderült, hogy ott van Történtek próbálkozások erre. És ha visszahívja évfolyam iskolában vagy középiskolában, morze. Morse kód pontok és gondolatjelek, hogy lehet adódik át egy vezetéket, mint hangok vagy jelek néhány sort. De morze egy szuper tiszta. Elég egy bináris rendszer hogy van a pontok vagy gondolatjelek. De ha úgy látja, hogy például két pont. Vagy ha úgy gondolja, vissza a kezelő aki megy, mint sípszó sípszó, sípszó, sípolás, ütő egy kicsit ravaszt hogy egy jelet, ha a címzett, kap két pöttyök, milyen üzenetet kaptál? Teljesen önkényes. 

Én? Én? Vagy mi about-- vagy én? Lehet, hogy csak két E jogát? Szóval van ez a probléma A decodability Morse kódot, amellyel kivéve, ha a küldője akkor az üzenet valóban szünetel, így egyfajta lát vagy hall a rések között levelek, ez nem elegendő csupán Levél egy patak nullák, vagy pontok és vonalak, mert ott van a kétértelműség. E egyetlen pont, így ha hogy két pont, vagy hallani két pont, talán két E által vagy talán ez az egyik I. Tehát szükségünk van egy olyan rendszer, amely egy kicsit okosabb annál. Tehát egy ember nevű Huffman év ezelőtt jött össze pontosan ezt. Szóval csak úgy hogy egy gyors pillantást hogy milyen fák illenek ehhez. Tegyük fel, hogy ez az egyes hülye üzenetet küldeni szeretné, tagjai: csak A, B, C a D és az E-k, de van egy csomó redundancia itt. Ez nem azt jelentette, hogy az angol. Ez nem titkosított. Ez csak egy hülye üzenetet sok az ismétlés. Tehát, ha valóban számít ki az összes A., B., C-, D és E a, itt van A frekvencia. 20% -a a betűk A., 45% -a a betűk az E-k, és három másik frekvencián. Mi számít ott kézzel és csak nem a matek. 

Így kiderül, hogy a Huffman, néhány évvel ezelőtt, rájött, hogy, tudod, mit, ha elkezdek épület egy fa, vagy erdei fák, ha úgy tetszik, az alábbiak szerint, meg tudom csinálni a következő. Megyek, hogy egy csomópont minden A betűk érdekel és megyek tárolni belsejében a csomóponton A frekvenciák lebegőpontos értéket, vagy ha lehet használni egy N is de majd csak használ egy úszó van. És az algoritmus, hogy azt javasolta, hogy meg ezt erdő egyes csomópont fák, így szuper rövid fák, és elkezd összekötő őket Új csoportok, új szülők, ha úgy tetszik. És akkor ezt választotta a két legkisebb frekvencia egy időben. Szóval vettem 10% és 10%. Én hozzon létre egy új csomópontot. És hívom az új csomópont 20%. 

Melyik két csomópont egyszerre többféle jövő? Ez egy kicsit félreérthető. Szóval egy kis sarok ügyek fontolja meg, de a dolgokat elég, Megyek választhat 20% - Én most figyelmen kívül hagyja a gyerekeket. Megyek választhat 20% és 15% és felhívni két új élek. És most, amely két csomópontot tudom logikailag összekapcsolják? Figyelmen kívül hagyja a gyerekek, mind a unokái, csak nézd meg a gyökereket Most. Melyik két csomópont tudom köti össze? Pont két és 0,35. Szóval hadd hívjam két új élek. És akkor már csak egy maradt. Tehát itt egy fa. És ez már kiállított szándékosan nézni milyen szép, de észrevettem, hogy a széleken is is jelzett nulla és egy. Tehát mind a bal szélétől nulla önkényesen, de következetesen. Minden a megfelelő élek is. 

És akkor mi van Hoffman javasolt, Ha azt szeretnénk, hogy képviselje a B, ahelyett képviseli a szám 66, mint ASCII amely nyolc teljes bit, tudod mit, csak boltba A minta nulla, nulla, nulla, nulla, mert ez az út az én fa, Mr. Huffman fája, A levél a gyökér. Ha szeretnéd tárolni E ezzel szemben nem Levél nyolc bit, hogy képviselje az E. Ehelyett küldeni, milyen mintát bitek? Egy. És mi a szép ez, hogy az E a legnépszerűbb írni, valamint ha a legrövidebb kódot hozzá. A következő legnépszerűbb levél néz ki, hogy volt A. És így hány bitet mondott javaslatot használ ez? Nulla, egy. 

És mert ez végre mivel ez a fa, most hadd kikötik van egyértelműen meg a Morse- kódot, mert az összes betűk törődsz vannak végén ezeket élek. Szóval ez csak egy alkalmazása egy fa. Ez is-- és én hullám kezem ebben hogyan Lehet végrehajtani ezt a C szerkezetet. Csak meg kell kombinálni egy szimbólum, mint egy char, és a frekvencia balra és jobbra. De nézzük meg a két utolsó példa, hogy akkor kap elég ismerős után kvíz nulla probléma meg öt. 

Tehát van az adatstruktúra néven hash tábla. És egy hash tábla fajta király, mivel úgy rendelkezik vödrök. És tegyük fel, van négy vödör itt van, csak négy üres helyeket. Itt egy pakli kártyát, és itt van klub, ásó, klub, gyémánt, klub, gyémánt, klub, gyémánt, clubs-- így ez a véletlen. Szívek, hearts-- úgyhogy bucketizing az összes bemenet van. És egy hash table-nek hogy nézd meg a bemeneti, majd betette egy bizonyos helyezze az alapján, amit látsz. Ez egy algoritmust. És én is használtam egy szuper egyszerű vizuális algoritmus. A legnehezebb része az volt, eszébe jutott, amit a képek voltak. És akkor ott van négy teljes dolgokat. 

Most a halom nőttek, ami egy tudatos tervezés dolog itt. De mi mást tehetek? Szóval tényleg itt van egy csomó régi iskolai vizsga könyveket. Tegyük fel, hogy egy csomó hallgatók nevek itt. Itt egy nagyobb hash tábla. Négy helyett vödrök, Én, mondjuk 26. És nem akartunk menni kölcsönkérni 26 dolgokat kívülről [? Annenberg?], Így Itt van öt képviselő A-tól Z És ha én hogy egy diák, akinek a neve kezdődik, Megyek tegye saját kvíz ott. Ha valaki kezdődik C, ott, Egy-- valójában, nem akartam ezt tenni. B megy át ide. Így kaptam az A és B és C és Most itt egy másik diák. De ha ez a hash tábla végre egy sor, Én ilyen csavarni Ezen a ponton, igaz? Valahogy meg kell tenni ennek valahol. 

Tehát az egyik mód arra, hogy megoldja ezt, minden Jobbra egy forgalmas, B foglalt, C foglalt. Megyek, hogy őt D. Tehát Először is, én véletlen azonnali hozzáférést az egyes kanalak a diákok számára. De most ez a fajta decentralizált valami lineáris, mert ha akarok keresni valakit akinek a neve kezdődik, megnézem itt. De ha ez nem az A hallgató keresem, Valahogy el kell kezdeni ellenőrzése A vödrök, mert amit tettem afféle lineárisan szonda adatok szerkezetét. Egy hülye szóval csak nézz az első rendelkezésre álló nyitó, és tedd egy B terv, hogy úgy mondjam, vagy terv D ebben az esetben az értéket e helyett. Ez csak úgy, hogy ha már Van 26 helyszínen, és nem a diákok A név Q vagy Z, vagy valami ilyesmi hogy legalábbis, amit használ a teret. 

De már látott több Okos megoldás itt van, ugye? Mit tennél helyett ha van egy ütközés? Ha két ember A megnevezés, mi lenne már egy okosabb vagy több intuitív megoldás, mint Elhelyezés egy D helyére kéne lennie? Miért nem csak megy kívül [? Annenberg?], mint a malloc, egy másik csomópont, tedd itt, és aztán, hogy egy diák itt. Szóval, hogy én alapvetően van valamiféle tömb, vagy talán elegánsabb, mint mi vagyunk kezdik látni a láncolt lista. 

És így a hash tábla egy olyan szerkezet amelyek úgy néznek ki, mint ez, de ügyesen, akkor egy úgynevezett Külön láncolás, ahol egy hash tábla egészen egyszerűen egy tömb, egyenként melynek elemei nem szám, maga a láncolt lista. Úgy, hogy Önnek szuper gyors hozzáférést döntés, hogy hol hash meg értéket. Hasonlóan a kártyák például Csináltam szuper gyors döntéseket. Szívek megy itt, gyémánt megy itt. Ugyanez itt, egy megy itt, D megy itt, a B megy itt. Szóval szuper gyors pillantást-up, és ha akkor megtörténhet, hogy befut egy esetben ahol van ütközés, két az emberek az azonos nevű, majd jól csak elkezd őket összekapcsolni. És talán nem tartjuk őket válogatni betűrendben, talán nem. De legalább most már a dinamizmus. Tehát az egyik oldalon ott van szupergyors konstans időt, és egyfajta lineáris idő szó, ha ezek a láncolt listák kezdenek egy kicsit hosszú. 

Tehát ez a fajta egy buta, geeky vicc évvel ezelőtt. A CS50 hack-a-Thon, amikor a diákok ellenőrzi, Néhány TF vagy CA évente hiszi, hogy vicces, hogy tegye fel jele, mint ez, ahol csak azt jelenti, ha a neve kezdődik egy A, erre kell menni. Ha a neve kezdődik a B, menjen this-- OK, ez vicces, talán később a félévben. De van egy másik módja ennek is. Gyere vissza, hogy a. 

Szóval van ez a szerkezet. És ez az utolsó struktúra ma, amely egy úgynevezett Trie. A T-R-I-E, amely valamilyen okból rövid visszakeresés, de ezt hívják Trie. Tehát egy Trie egy másik érdekes amalgám sok ilyen ötletek. Ez egy fa, amit eddig láttam. Ez nem egy bináris kereső fa. Ez egy fa, minden gyermekek száma, de minden a gyerekek egy Trie egy tömb. Egy sor mérete, mondjuk, 26 vagy talán 27 Ha szeretnéd támogatni kötőjeles neveket vagy aposztróf az emberek neveit. 

És így ez egy adatstruktúra. És ha megnézzük felülről A végére, mint ha Nézd meg a felső csomópont van, M, az rámutatva, hogy a bal szélső dolog van, amelyet ezután A, X, W, E, L, L. Ez csak egy adatstruktúra, hogy önkényesen a tároló emberek neveit. És Maxwell tárolja csak a következő az utat a tömb tömb tömb. De mi Elképesztő egy Trie van hogy míg a láncolt lista, és még tömb, a legjobb, amit valaha kaptál van lineáris idő vagy logaritmikus ideje keres valakit. Ebben adatstruktúra egy Trie, ha én adatszerkezet egy név benne és keresem Maxwell, én vagyok fog találni elég gyorsan. Én csak keresni M-A-X-W-E-L-L. Ha ez az adat struktúra, ezzel szemben, ha N egy millió, ha van egy millió nevek ezen adatok szerkezete, Maxwell még lesz felderíthető után csak az M-A-X-W-E-L-L lépéseket. És David-- D-A-V-I-D lépésben. Más szóval, az épület adatstruktúrát, ami kapott összes ilyen tömbök, amelyek mindegyike magukat támogatják véletlenszerű hozzáférés, Kezdhetem keresi fel az emberek nevet egy ideig, ez arányos Nem száma a dolgok az adatok szerkezete, mint egy millió nevekkel. Az időt vesz igénybe, hogy megtaláljam M-A-X-W-E-L-L ezen adat struktúra arányos nem a mérete az adatok szerkezete, de, hogy a hossza a név. És reálisan nevek keresünk fel soha nem lesz őrült hosszú. Lehet, hogy valaki egy 10 karakter Íme, 20 karakter neve. Ez természetesen véges, nem igaz? Van egy ember a Földön, aki a leghosszabb lehetséges nevet, bár ez az elnevezés állandó érték hossza, ugye? Ez nem változik semmi értelme. Tehát ily módon, most már elérni egy adatstruktúra hogy állandó idő look-up. Ez nem fog egy több lépésből attól függően, hogy a hossza a bemenet, de nem a több név az adatszerkezet. Tehát, ha megduplázza a nevek száma jövőre egy milliárd kétmilliárd, megállapítás Maxwell fog tartani pontosan ugyanannyi hét lépésben hogy megtalálja őt. És így úgy tűnik, hogy elérték a szent grál a futási idő. 

Tehát néhány gyors bejelentések. Kvíz nulla jön ki. Több az, hogy a pályán honlapján Az elkövetkező pár nap. A hétfői lecture-- ez egy ünnep Itt a Harvardon hétfőn. Ez nem New Haven, így elvisszük az osztály New Haven Tantermi hétfőn. Minden forgatják és élőben, mint rendesen, de most véget ma egy 30 másodperces klip az úgynevezett "mély gondolatokat" által Daven Farnham, amely ihlette tavaly a szombat Night Live "mély gondolatok" Jack Handy, amely Most már semmi értelme. 

FILM: És most, "Deep Gondolatok "a Daven Farnham. Hash tábla. 

1. Előadó: Rendben, ennyi egyelőre. Találkozunk a jövő héten. 

DOUG: Hogy látni működés közben. Szóval vessünk egy pillantást, hogy most. Tehát itt, van egy rendezetlen tömb. 

Ian: Doug, akkor megy előre, és indítsa újra ez csak egy második, kérem. Rendben, kamera gördülő, így fellépés, amikor csak akarja, Doug, OK? DOUG: Rendben, akkor mi vagyunk Van itt egy rendezetlen tömb. És én már színes valamennyi elemét piros, jelezve, hogy ez, sőt, szétválogatás nélkül. Így emlékeztetni arra, hogy az első dolog, amit Mi vagyunk rendezni a bal fele a tömbben. Aztán rendezni a jobb a fele a tömb. És ya-da, da ya-, ya-da, mi egyesítése őket. És van egy teljesen rendezett tömbben. Szóval így egyesíti a fajta működik. 

Ian: Hé, hé, hé, vág, vág, vág, vág. Doug, akkor nem csak ya-da, da ya-, ya-da, végig merge sort. 

DOUG: én csináltam. Rendben van. Mi még jól jöhet. Nézzük csak tartsa gördülési. Mindegy, 

Ian: Meg kell magyarázni ez jobban, mint ezt. Ez egyszerűen nem elég. DOUG: Ian, mi nem kell, hogy menjen vissza az egyik. Rendben van. Mindegy, ha továbbra is a merge-- Ian, mi vagyunk a közepén forgatás. 

Ian: Tudom. És nem csak a ya-da, da ya-, ya-da, az egész folyamatot. Meg kell magyarázni, hogy a két fél kap összefűzve. 

DOUG: De már elmagyarázta, hogy a két sides-- 

Ian: épp most látható nekik egy merge tömb. DOUG: Ismerik a folyamatot. Jól vannak. Mentünk rajta tízszer. 

Ian: Csak kimarad jobb rajta. Megyünk vissza az egyik, akkor nem tudsz ya-da, da ya-felette. Rendben, vissza az egyik. 

DOUG: mennem kell vissza végig a csúszda? Istenem. Ez olyan, mint a hatodik alkalommal, Ian. Rendben van. 

Ian: Rendben. Készen állsz? Nagy. Akció.