[Zenelejátszás] David J. MALAN: Rendben. Ez CS50. Ez a hét öt folytatódott, és mi Van egy jó hír és egy rossz hír. Így jó hír, hogy CS50 indít pénteken. Ha szeretnél csatlakozni hozzánk, irány a szokásos URL itt. Még jobb hír, nincs előadás a jövő hétfő 13. Valamivel kevesebb jobb hír, kvíz nulla jövő szerdán. További részletek található ezen az URL-t ide. És az elkövetkező pár napra fogunk kitöltésével az üres tekintettel a szobában hogy mi lesz fenntartva. Jobb hír, hogy lesz majd egy kurzus kiterjedő felülvizsgálat ülés a jövő Hétfő este. Maradjanak velünk, hogy a tanfolyam honlap hely és a részleteket. Szakaszok, bár ez egy ünnep, akkor is eleget is. A legjobb hír, előadás jövő pénteken. Tehát ez egy hagyomány van, mint egy a tananyag. Hogy-- lesz csodálatos. Látni fogja a dolgokat, mint állandó idő adatszerkezetek és hash táblák és fák és próbál. És fogunk beszélni születésnapját problémákat. Egy csomó dolgot várja jövő pénteken. OK. Egyébként. Úgy emlékszem, hogy már összpontosítva ezt a képet, hogy mi van belsejében a számítógép memóriájában. Tehát a memória vagy RAM ahol programok létezik, miközben futsz őket. Ha duplán rákattint egy ikon futtatni néhány programot vagy kattintson duplán egy icon nyitni néhány fájlt, meg van töltve a merevlemez meghajtó vagy szilárdtest-meghajtó a RAM-ba, Random Access Memory, ahol él, amíg a készülék ki nem kapcsol, A laptop fedél bezárul, vagy kilép a programból. 

Most, hogy a memória, a amit valószínűleg 1 gigabájt ezekben a napokban, 2 gigabyte, vagy akár sokkal több, általában lefektetett Ha egy adott programhoz ebben a fajta négyszögletes fogalmi modell amelynek megvan a halom alján és egy csomó más dolog a tetején. A dolog a legtetején láttunk ezen a képen előtt, de soha nem beszélt az úgynevezett szöveges szegmensben. Szöveg szegmens csak egy divatos mondván a nullák és egyesek, hogy össze a tényleges lefordított program. 

Tehát, ha dupla kattintás Microsoft Word a Mac vagy PC, vagy ha fut pont perjel Mario egy Linux számítógép a terminál ablak, A nullák és egyesek alkotó Szó vagy Mario ideiglenesen tárolja a számítógép RAM az úgynevezett szöveg szegmens egy adott programot. Alatta megy inicializált és inicializált adat. Ez a cucc, mint a globális változók, hogy már nem használják sokan, de időnként mi már volt globális változók vagy statikusan definiált vonósok hogy Nehéz kódolt szavak, mint a "hello" hogy nem születnek meg a felhasználó amelyek kódolva a programba. 

Most le az alul van az úgynevezett stack. És a verem, eddig, voltunk használ, milyen célból? Mi ez a halom használt? Igen? 

Közönség: funkciók. 

David J. MALAN: A funkciók? Milyen értelemben funkciókhoz? 

Közönség: ha hívja a funkció, a érveket másolja a verembe. 

David J. MALAN: Pontosan. Ha hívja a funkció, a érveket másolja a verembe. Így minden X vagy Y vagy A vagy B hogy te halad egy funkció átmenetileg fel az úgynevezett stack, mint az egyik Annenberg étkező tálcák, és a dolgok, mint lokális változók. Ha a foo függvény vagy a csere funkció van lokális változók, mint temp, a két végén a verem. Most nem fogunk túl sokat beszélni őket, de ezek a környezeti változók alul láttunk egy darabig ezelőtt, amikor Én futzing a billentyűzet egy nap és elkezdtem hozzáférés dolgok mint argv 100 vagy argv 1000, csak elements-- elfelejtem a numbers-- de nem kellene hozzáférni engem. Elkezdtük látni néhány funky szimbólumok a képernyőn. Ezek voltak az úgynevezett környezeti változók mint globális beállításait a program vagy a számítógéphez, nem független a közelmúltban hiba, hogy megbeszéltük, Shellshock, hogy a már sújtó jó néhány számítógép. 

Most végül, a mai fókusz mi lesz végül a kupac. Ez egy másik darabja a memóriát. És alapvetően mindez memória ugyanazokat a dolgokat. Ez ugyanaz a hardver. Mi csak egyfajta kezelésére különböző klaszterek bájtok különböző célokra. A halom is lesz, ahol a változók és a memória, amit kér Az operációs rendszer ideiglenes tárolására használnak. 

De van olyan probléma Itt is, mint a kép is jelzi. Mi a fajta két hajó hamarosan összeütközik. Mert ahogy te és egyre A verem, és mint látjuk ma től, mint használ egyre több a halom, biztosan rossz dolgok történnek. És valóban, mi válthat ki, hogy szándékosan vagy akaratlanul. Így a filmsorozat utolsó Mikor volt ez a program, amely nem szolgál semmilyen funkcionális más célja, mint annak bizonyítására, hogyan, mint egy rossz ember ténylegesen venni előnye hibákat valaki programban és átveszi a programot, vagy akár a teljes számítógépes rendszer vagy szerver. Tehát csak a pillanat röviden, te észre, hogy legfontosabb az alján vesz parancssorban érvek, mint egy ARGV. És van egy hívást egy f, lényegében egy névtelen nevezett funkció f, és ez halad argv [1]. 

Tehát bármi szó a felhasználó által a A prompt után a program nevét, és akkor ez önkényes funkció fel top, f, vesz egy string, AKA char * ahogy már elkezdték megvitatni, és ez csak kéri, hogy "bar". De nevezhetjük bárminek. És akkor azt mondja, belül f, egy sor karakter hívott C-- 12 ilyen karaktereket. 

Most, a történet, amit mesélt Egy perce, amikor a memóriában c jelentése, vagy azok 12 karakter lesz a vége? Csak hogy világos legyen. Igen? 

Közönség: A verem. 

David J. MALAN: A verem. Így c egy lokális változó. Kérünk 12 karakter vagy 12 bájt. Azok fognak a végén az úgynevezett stack. Most végre van egy másik funkciója ez valóban nagyon hasznos, de már nem igazán használható magunk, strncopy. Ez azt jelenti, húr példány, de csak az N betű, n karaktereket. Így n karakter lesz másolt rudat c. És hány? A hossza a bárban. Tehát más szavakkal, hogy a egy vonal, strncopy, fogja másolni hatékonyan bár a c. 

Most, csak azért, hogy milyen előre A történet tanulsága, ami potenciálisan problematikus itt? Annak ellenére, hogy mi ellenőrzése hosszát A bár és halad azt strncopy, mi a bél mondom az még mindig sérült erről a programról? Igen? 

KÖZÖNSÉG: nem tartalmazza hely a null karakter. David J. MALAN: nem tartalmazza hely a null karakter. Potenciálisan, ellentétben korábbi gyakorlat még csak nem is annyi, mint a plusz 1-től befogadására, hogy null karakter. De ez még annál is rosszabb. Mi mást is mivel nem kell csinálni? Igen? 

KÖZÖNSÉG: [nem hallható] David J. MALAN: Tökéletes. Már bedrótozott 12 szép önkényesen. Ez nem annyira a probléma, hanem az a tény, hogy még csak nem is ellenőrizhető, hogy bár a hossza kisebb, mint 12, ebben az esetben lesz nyugodtan tedd be a memóriába c néven, hogy már kiosztott. Valóban, ha bár mint 20 karakter hosszú, Ez a funkció úgy tűnik, hogy a másolás 20 karakter a rudat c, ezáltal figyelembe legalább 8 bájt hogy ne legyen. Ez a gondolat itt. 

Tehát röviden, hibás program. Nem olyan nagy ügy. Lehet, hogy kap egy szegmentációs hiba. Mindannyian hibásak a programokban. Mindannyian volna hibát programok most. De mi a következménye? Nos, itt van egy felnagyított változata hogy kép a számítógép memóriájában. Ez az alsó az én verem. És valóban, a legalján az, ami nevezett szülő rutin verem, divatos módja mondván, hogy ez fontosabb. Úgy, hogy aki nevezett funkció f hogy beszélünk. Szóval ez a köteg alján. Visszatérési cím van valami új. Ez mindig is ott volt, mindig is azt a képet. Csak soha nem hívta rá a figyelmet. Mert kiderül, ahogy a C működik hogy ha egy függvény meghívja a másik, nem csak az érvek, hogy a funkció kap a verembe, nem csak a függvény helyi változó kap a verembe, egy úgynevezett visszatérési cím is kap tesz a verembe. Pontosabban, ha a fő hívások ize Main saját címét a memóriában, ökör valami, hatékonyan kerül fel a verembe hogy amikor f történik futtatása tudja, hogy hol ugrik vissza a szöveg szegmens annak érdekében, hogy továbbra is a végrehajtó. 

Tehát, ha itt vagyunk fogalmilag, A legfontosabb, akkor f hívódik. Hogyan f, hogy ki a kézi vezérlés vissza? Nos, ez a kis morzsa piros itt, az úgynevezett visszatérési címet, csak ellenőrzés, mi az, hogy a feladó címét? Ó, hadd ugorjon vissza a ide. És ez egy kicsit egy leegyszerűsítés, mert a nullák és egyesek A fő technikailag itt a tech szegmensben. De ez az ötlet. f csak azt tudni, hogy mi hogy ahol a szabályozás végül visszamegy. 

De ahogy a számítógépek már régen lefektetett dolgok mint lokális változók és érvek, mint ez. Tehát az első kép a kék a verem keret f, így minden a memória, hogy f különösen az használ. Tehát ennek megfelelően, észreveheti, hogy bár ezen a képen. Bár volt az érv. És azt állította, hogy érvek funkciókat kap a verembe. És c, természetesen, is ezt a képet. 

És csak a jelölési célokra, észre a bal felső sarokban mi kerülne c tartó 0 és majd enyhén jobbra le a c konzol 11. Más szóval, el lehet képzelni hogy van egy rács bájtok ott, amelynek első bal felső, alsó, amely az utolsó a 12 bájt. 

De most megpróbál a gyors előre. Mi fog történni, ha át egy karakterlánc bárban, ami hosszabb, mint c? És mi nem ellenőrizhető, hogy ez valóban több, mint 12. Melyik része ez a kép fog kap felülírja byte 0, 1, 2, 3, dot dot dot, 11, majd a rossz, 12, 13 19 keresztül? Mi fog történni itt, ha arra következtetnek a rendelési hogy c konzol a 0 a legjobb és c konzol 11 fajta lefelé a jobb? Igen? 

Közönség: Nos, ez lesz felülírja a char * bár. 

David J. MALAN: Igen, úgy néz ki, mint fogsz felülírni char * bár. És ami még rosszabb, ha küld egy nagyon hosszú húr, akkor talán még felülírja mi? A feladó címét. Ami megint, olyan, mint egy morzsa, hogy elmondja a program, ahol hogy menjen vissza, amikor f történik, hogy hívják. 

Szóval, mi a rossz fiúk általában nem , ha azok találkoznak a programot hogy ők kíváncsiak, hogy az kihasználható, buggy úgy hogy ő tehet előnye, hogy a hiba, általában nem kap ez jobb az első alkalommal. Csak megkezdéséhez, például, véletlenszerű húrok a programba, akár a billentyűzet, vagy őszintén valószínűleg írni egy kis programot, hogy csak automatikusan generál vonósok, és meg kell kezdeni dörömböl a program küldés sok különböző bemenetek A különböző hosszúságú. 

Amint a program lefagy, ez egy csodálatos dolog. Mert ez azt jelenti, hogy vagy ő fedezte fel ami talán valóban egy hiba. És akkor lehet, hogy több okos és meg kell kezdeni összpontosítva szűkebben hogyan kell kihasználni a bogarat. Különösen, amit ő talán tennie, hogy küld, a legjobb esetben, helló. Nem nagy ügy. Ez egy sor, ami elég rövid. De mi van, ha ő küld, és mi általánosítani azt, támadás code-- így nulla és is, hogy a dolgok mint rm-rf, hogy távolítsa el minden A merevlemez vagy kéretlen levelek küldésére vagy valamilyen módon megtámadják a gép? 

Tehát, ha minden ilyen betűk csak képviseli, fogalmilag, támadás, támadás, támadás, támadás, egy rossz kód hogy valaki más írta, de ha ez a személy elég okos ahhoz, hogy nem csak a minden RM-e RFS, hanem már ő az utolsó néhány byte egy szám, amely megfelel A cím az ő vagy a saját támadó kódot hogy ő át mindössze azáltal, hogy a gyors, akkor hatékonyan becsapni a számítógép figyelembe vette észre, amikor az f kész végrehajtása, Ó, itt az ideje, hogy ugrik vissza a piros feladó címét. Hanem azért, mert ő is valahogy átfedésben hogy visszatérési cím saját szám, és ők elég okosak volna kialakítani, hogy szám hivatkozni, mint te lásd a szuper felső bal sarokban, az aktuális cím a számítógép emlékét azok egyes támadó kódot, rossz ember lehet becsapni a számítógép a végrehajtó a saját kódját. 

És a kódot, megint, bármi lehet. Ez általában az úgynevezett shell kód, ami csak oly módon, mondván, hogy ez nem általában valami olyan egyszerű, mint a rm-rf. Ez valójában olyasmi, mint Bash, vagy a tényleges program, amely őt vagy a programozott ellenőrzés végrehajtását mást, hogy akarnak. Tehát röviden, ez az egész abból az egyszerű tény, hogy ez a hiba szó nem ellenőrzés a határait a tömb. És mivel az út számítógépek az, hogy a munka használja az oszlopot hatékonyan, fogalmilag, akár alulról, de aztán az elemek tolja a verembe nő felülről lefelé, Ez hihetetlenül problematikus. Nos, vannak olyan módon, hogy a munka körül ezt. És őszintén szólva, vannak nyelvek amellyel a munka körül ezt. Java immunrendszer, például, hogy az adott kérdés. Mert nem kapsz mutatókat. Nem kapsz közvetlen memória címeket. Tehát ez az erő, hogy mi nyúljon semmihez a memóriában azt akarjuk, jön, igaz, nagy a kockázata. 

Így tartsa a szemét. Ha őszintén szólva, a következő hónapokban vagy az elkövetkező években, bármikor olvastam néhány kizsákmányolás a program vagy a szerveren, Ha valaha is látni egy csipetnyi valami mint a buffer overflow támadás, vagy stack túlcsordulás egy másik típusa A támadás, hasonló szellemben, mint inspirálja a honlap neve, ha tudod, ez mind beszél, csak tele a mérete néhány karakter array vagy néhány tömb általában. Bármilyen kérdése van, akkor ezen? Ne próbáld ki otthon. 

Rendben. Tehát malloc eddig volt új barátom, hogy tudjuk lefoglalni memóriát hogy nem feltétlenül tudja, hogy a előre, hogy mi szeretnénk, így nem kell kemény kód a mi programok száma, mint a 12. Ha a felhasználó azt mondja, hogy mennyi adatokat, vagy akar bemenet, akkor malloc, hogy sok memóriát. 

Így malloc kiderül, hogy a mennyiben már nem, pedig, kifejezetten utoljára, majd a srácok már használja A getString tudatlanul az Néhány hét minden malloc memória származik az úgynevezett kupac. És ez az, amiért getString, például, lehet lefoglalni memóriát dinamikusan anélkül, hogy tudnánk, mit te majd írja előre, adja vissza a mutatót, hogy az emlékezet, és hogy az emlékezet még mindig a tiéd, hogy, után is getString visszatér. Mivel a visszahívás után is, hogy a verem folyamatosan megy fel és le, felfelé és lefelé. És amint megy le, hogy minden olyan memória ezt a funkciót használni kellene nem használhatja bárki más. Ez szemét értékeket most. 

De a rakás itt. És mi a szép a malloc, hogy ha malloc memóriát itt, ez nem befolyásolja, a legnagyobb részben a verem. És így minden funkció eléréséhez memória, amelyet malloc segítségével lefoglalt, még egy funkció, mint a getstring, után is vissza. 

Most az ellenkezője a malloc ingyenes. És valóban, a szabály akkor kell kezdeni elfogadása minden olyan, minden, minden alkalommal, amikor használja malloc akkor magad használni szabad, végül, ugyanezen mutató. Egész idő alatt mi is írásban hibás, hibás kód, több okból. De az egyik, amely már a CS50 könyvtár, amely Maga szándékosan buggy, azt memóriavesztést. Minden alkalommal, amikor már hívott getstring Az elmúlt néhány hét alatt kérünk az üzemeltetési rendszer, a Linux, a memória. És még egyszer sem adott vissza. És ez nem, a gyakorlat, egy jó dolog. 

És Valgrind egyik eszközök bevezetett Pset 4, szól segít most meg a hibákat, mint ezt. De szerencsére az Pset 4 nem szükséges használja a CS50 könyvtár vagy getstring. Tehát bármilyen hibát kapcsolatos emlékezet végül lesz saját. 

Tehát malloc több, mint kényelmes erre a célra. Mi is valójában már megoldani alapvetően eltérő problémákkal, és alapvetően megoldja a felmerült problémákat hatékonyan hetente nulla ígérete. Eddig ez a legszexisebb adatstruktúra már volt. És adatstruktúra Úgy értem egy módja fogalomalkotó memória oly módon, hogy túlmutat csak azt mondom, ez egy int, ez egy char. Elkezdhetjük klaszter dolgokat. 

Tehát egy sor így nézett ki. És mi volt a kulcs, körülbelül egy tömb, hogy ad back-to-back darabok memória, amelyek mindegyike lesz az azonos típusú, int, int, int, int vagy char, char, char, char. De van egy rossz oldala is. Ez például, tömb mérete hat. Tegyük fel, hogy töltse ki ezt a tömböt hat számokat, majd bármilyen okból, a felhasználó akarja adni Ön egy hetedik számot. Hová tetted? 

Mi a megoldás, ha létrehozott egy tömböt a verem, például, csak a hét két jelölés, hogy mi vezetett, A szögletes zárójelben egy szám benne? Nos, van hat számok ezekben a dobozokban. Mi lenne az ösztönök is? Hol akarod, hogy ez? 

KÖZÖNSÉG: [nem hallható] 

David J. MALAN: Tessék? 

Közönség: Tedd a végén. 

David J. MALAN: Tedd a végén. Így alig több mint a jobb, kívül ezt a dobozt. Ami jó lenne, de azt Kiderül, hogy nem tehetem meg. Mert ha már nem kérte e darab memória, ez lehet véletlen, hogy ez a által használt más változó összesen. Gondolj vissza egy hét múlva, amikor meghatározott ki Zamyla és Davin és Gabe nevét a memóriában. Ezek szó szerint vissza háttal. Tehát nem feltétlenül bízom benne, hogy bármi a itt áll rendelkezésre, hogy használjam. 

Szóval, mit lehet tenni? Nos, amint rájött, hogy szüksége van egy sor méret hét, akkor csak létre tömb mérete hét majd a for ciklus vagy egy while ciklus, másold be az új tömb, és aztán valahogy csak megszabadulni ezt a tömböt, vagy éppen ne használja azt. De ez nem különösebben hatékony. Röviden, a tömbök ne engedd dinamikusan átméretezi. 

Így egyrészt kapsz véletlen elérésű, ami elképesztő. Mert ez lehetővé teszi számunkra, hogy a dolgokat mint oszd meg és uralkodj, bináris keresés, mind amit már beszélt a képernyőn itt. De festeni magad a sarokba. Amint eléred a végén a tömb, meg kell csinálni egy nagyon drága működés vagy írjon egy csomó kód most kezelni ezt a problémát. 

Szóval, mi lenne, ha inkább volt egy úgynevezett listán, vagy a kapcsolt lista különösen? Mi van, ha ahelyett, hogy téglalapok vissza, hogy háttal, van téglalapok hagy egy kis kis kígyózik szoba között? És bár én készült ez kép vagy alkalmassá ezt a képet az egyik a szövegek itt, hogy újra háttal nagyon rendezett, a valóságban, az egyik ilyen téglalap Lehet itt a memóriában. Egyikük lehet itt. Egyikük lehet itt, ide, és így tovább. 

De mi van, ha rajzolt, Ebben az esetben, nyilak hogy valahogy össze ezt a téglalapok együtt? Sőt, láttunk egy technikai megtestesülése egy nyíl. Mit használtunk az elmúlt nap, hogy a motorháztető alatt, reprezentatív nyíl? A mutató, igaz? 

Mi van, ha ahelyett, hogy csak tárolja a számokat, mint a 9., 17., 22., 26., 34., Mi van, ha a tárolt nem csak egy telefonszámot, de a mutató mellett minden ilyen szám? Annak érdekében, hogy ugyanúgy, mint akkor menet a tűt egy csomó szövet, valahogy árukapcsolás dolgok együtt, mint szintén mi a mutatók, mint inkarnálódott nyilak itt, fajta szövik együtt ezek az egyes téglalapok által ténylegesen egy mutató mellett minden szám rámutat néhány a következő számot, hogy mutat, viszont, néhány a következő szám? Más szóval, mi ha valóban akarta végrehajtása ilyesmit? Hát sajnos, ezek a téglalap, legalább az egyik a 9., 17., 22., és így tovább, ezek már nem szép terek egyetlen számokat. Az alsó, téglalap 9 alatti, például, képviseli azt, amit kellene egy mutató, 32 bit. Nos, én nem vagyok még tisztában bármilyen adattípus C-ben, hogy ad nem csak egy int de a mutató teljesen. 

Szóval, mi a megoldás, ha azt akarjuk kitalálni a saját válasza erre? Igen? 

KÖZÖNSÉG: [nem hallható] 

David J. MALAN: Mi ez? 

Közönség: új struktúrát. 

David J. MALAN: Igen, miért nem hozunk létre egy új struktúra, vagy C, a struktúra? Láttuk Struktúrák korábban, ha röviden, ahol foglalkozott a diák szerkezet mint ez, akinek a neve és a házat. A Pset 3 kitörési használt egész csomó structs-- GRect és GOvals hogy Stanford létrehozott fürtinformációit együtt. Szóval, mi lenne, ha ezt azonos ötlet a kulcsszavak "typedef" és "struct" majd néhány diák-specifikus dolog, és fejlődik ez a következő: typedef struct node-- és csomópont csak egy nagyon általános számítógép-tudomány kifejezés valamit egy adat struktúra, egy tartályt egy adatszerkezetet. A csomópont Állítom megy, hogy egy int n, teljesen egyértelmű, , majd egy kicsit rejtélyesen, A második vonal, struct csomópont * mellett. De kevesebb technikai értelemben, mi az, hogy a második sor kód belsejében a kapcsos zárójelek? Igen? 

KÖZÖNSÉG: [nem hallható] David J. MALAN: A Mutató a másik csomópont. Tehát igaz, mondattani kissé rejtélyes. De ha olvasod a szó szoros értelmében, következő a neve a változó. Mi a adattípus? Ez egy kicsit bőbeszédű ebben az időben, de ez a típus struct csomópont *. Minden alkalommal láttunk valami csillag, hogy azt jelenti, hogy egy mutatót, amely az adatok típusát. Így a következő látszólag a pointert a struct csomópont. 

Nos, mi a struct csomópont? Nos, észre látod azokat ugyanazokat a szavakat a jobb felső sarokban. És valóban, akkor is látni a szó "Node" itt a bal alsó sarokban. És ez valójában csak a kényelem. Figyeljük meg, hogy a mi hallgatói definíció ott van a "diák" csak egyszer. És ez azért van, mert egy diák objektum nem önreferenciálisak. Nincs benne semmi a diák hogy kell, hogy pont a másik diák, persay. Ez lenne a fajta furcsa a valós világban. 

De egy csomópont a kapcsolt lista, mi szeretnénk egy csomópont hogy referenciális egy hasonló objektumot. És így a változást itt nem csak mi van benne a kapcsos zárójeleket. De hozzá a "csomópont" a tetején, valamint hozzátéve, hogy az alsó helyett "tanuló". És ez csak egy technikai részlet úgy, hogy ismét az adatok szerkezete lehet saját referenciális, úgy, hogy a csomópont is pont egy ilyen csomópont. 

Szóval mi ez a végső soron fog jelenteni számunkra? Nos, az egyik, ez a cucc benne a tartalma a csomópontot. Ez a dolog itt, jobb felső, csak annyira hogy ismét tudunk hivatkozni magunkat. És akkor a legtávolabbi dolog, noha csomópont egy új kifejezés, talán még mindig a ugyanaz, mint a diák, és milyen volt a motorháztető alatt az SPL. 

Tehát, ha most akartam kezdeni végrehajtásáért láncolt lista, hogyan tudnánk fordítani valami ilyesmit kell a kódot? Nos, nézzük meg egy Például, hogy a program valójában használ láncolt lista. Napjaink eloszlás kód egy program neve List Zero. És ha én vezetem ezt hoztam létre egy szuper egyszerű GUI, grafikus felhasználói felület, de ez tényleg csak printf. És most adtam magamnak néhány menüt options-- Törlés, Beszúrás, Keresés, és Traverse. És kilép. Ezek csak a közös műveleteket a adatstruktúra ismert, mint egy link listát. 

Most, Törlés fog Szám törlése a listából. Insert fog hozzá egy számot a listához. Keresés fog nézni A szám a listán. És áthalad csak egy divatos módon mondván, séta a listán, nyomtassa ki, de ennyi. Ne változtassa meg semmilyen módon. 

Szóval próbáld ki ezt. Menjünk előre, és 2-es típusú. És akkor fogok helyezze be a számot, mondjuk 9. Az Enter billentyűt. És most a program csak programozva, hogy mondjam, a lista már 9. Most, ha jól megy előre, és Ne helyezze be újra, legyen menjek előre, és kicsinyítés és írja 17. Most a lista 9, majd 17. Ha megteszem helyezze újra, ugorjunk egyet. Ahelyett, hogy 22, mint egy kép mi már már néztem itt, hadd ugrik előre és helyezze 26 Következő. Így fogok 26-os típus. Íme, a lista gondolom. De most, csak azért, hogy ha ez a kód lesz rugalmas, hadd most 22 típusú, amelyek közül legalább fogalmilag, ha vagyunk Tartsa ezt válogatni, ami valóban lesz egy másik cél most, kell menni a 17 és 26. Szóval az Enter leütése. Sőt, ami működik. És most hadd tegye be a Végül, egy a kép, 34. 

Rendben. Tehát most hadd előírják, hogy Törlés és Traverse és Search csinálni, sőt, a munka. Sőt, ha én futni Search, nézzük megkeresi a szám 22, Enter. Úgy ítélte meg, 22. Szóval, ez az, amit ez a programok listája Zero nem. 

De mi is történt valójában az, hogy megvalósítja ezt? Nos, először talán van, sőt Nekem van egy nevű fájlt list0.h. És valahol itt van ez a vonal, typedef struct csomópont, akkor ott van a kapcsos zárójelek, int n, és akkor struct-- mi volt a meghatározás? Struct csomópont mellett. Tehát szükségünk van a csillag. Most technikailag belemennénk a szokás rajz itt. Lehet látni a tankönyvek és Online referenciák csinálni ott. Ez funkcionálisan egyenértékű. Tény, hogy ez egy kicsit több jellemző. De én leszek, ami megfelel mi a múltkor, és nem ezt. És akkor végül, fogom csinálni. 

Tehát egy header fájlban valahol, a list0.h ma ez a struktúra definíció, és talán néhány egyéb dolog. Eközben list0c van lesz egy pár dolgot. De megyünk csak kezdeni és nem befejezni ezt. List0.h egy fájl akarok tartalmazza az én C fájlban. Aztán egy bizonyos ponton vagyok lesz int, a fő, semmis. És akkor fogok néhány to-do itt. Én is megyek, hogy egy prototípus, mint üres, keresés, int, n, amelynek célja az életben keresni egy elem. És akkor itt azt állítják, A mai kód, érvénytelen, keresés, int, n, nincs pontosvessző, de nyitott kapcsos zárójeleket. És most szeretném valahogy keresni Egy elem a listában. De nem elég információ a képernyőn még. Én valójában nem képviselte a lista is. Tehát az egyik módja, hogy végre A láncolt lista egy programban A Valahogy akarok valamit mint kinyilváníthatja láncolt lista itt. Az egyszerűség kedvéért, én csinálok ez a globális, bár általában mi nem kell ezt túl sokat. De ez egyszerűsíti ezt a példát. Szóval azt akarom, hogy állapítsa láncolt lista itt. Nos, hogyan lehet ilyet? 

Itt van a kép egy láncolt lista. És én nem igazán tudják, abban a pillanatban, hogy Én megyek a képviselő Olyan sok dolog csak egy változó a memóriában. De gondolj vissza egy pillanatra. Egész idő alatt is megvolt vonósok, amit aztán kiderült, hogy a tömbök karakter, amit aztán kiderült, hogy csak egy mutató Az első karakter egy sor karakter ez null megszűnik. Tehát a logika, és ezzel kép a fajta vetés a gondolatait, mit kell valójában írni mi kód, hogy képviselje a láncolt lista? Mennyi ezen információk nem is kell hogy rögzítse a C kód, mit mondana? Igen? 

Közönség: Szükségünk van egy mutató egy csomópont. David J. MALAN: A mutató egy csomópont. Különösen, ami csomópont lenne az ösztönök lehet tartani a mutatót? 

KÖZÖNSÉG: Az első csomópont. 

David J. MALAN: Igen, talán csak az első. , És vegyük észre, az első csomópont egy másik formája. Ez csak feleakkora a struct, mert ez tényleg csak egy mutató. Szóval, mit lehet valóban tenni is kijelentik A láncolt lista, hogy típusú csomópont *. És hívjuk csak először és inicializálása null. Tehát null ismét jön a kép itt. Nem csak a null használják, mint a speciális visszatérési érték a dolgok, mint getstring és malloc, null is a nulla mutató, nincs meg az a mutató, ha úgy tetszik. Ez csak azt jelenti, semmi még itt. Most először, nem tudtam volna hívják ezt a valamit. Tudtam volna nevezte "lista" vagy számos más dolog. De én hívom, hogy "első", hogy a egy vonalba ezzel a képpel. Tehát, mint egy húr is képviselteti magát A cím az első byte, így lehet a láncolt lista. És majd meglátjuk egyéb adatok szerkezetek képviseli csak egy mutató, 32 bites arrow, rámutatva a nagyon első csomópont a szerkezetben. 

De most nézzük előre a probléma. Ha én csak emlékezni a programom a cím Az első csomópont, az első téglalap adatstruktúrát, mi volt jobb a helyzet a végrehajtása a többi az én lista? Mi az a legfontosabb részlet, hogy fog Ennek biztosítása tényleg működik? És a "tényleg működik" I jelent, mint egy húr, lehetővé teszi számunkra, megy az első karakter A Davin nevét a második, A harmadik, hogy a negyedik, hogy a legvégén, honnan tudjuk, hogy mikor vagyunk a végén A láncolt lista, amely úgy néz ki, mint ez? Mikor ez null. És már képviselte ezt a fajta, mint mint villamosmérnök hatalom, A kis földelés szimbólum, a fajta. De ez csak azt jelenti, null ebben az esetben. Tudod felhívni minden olyan szám módon, de ez a szerző történt, hogy ezt a szimbólumot itt. 

Mindaddig, amíg mi drót mindezen csomópontok együtt, csak elfelejtette, hogy hová Az első az, amíg mint mi, hogy egy speciális szimbólum az utolsó csomópont a listán, és fogjuk használni null, mert az mi van elérhető számunkra, ez a lista teljes. És még ha csak kapsz egy mutatót az első elem, te, a programozó, biztosan tudja elérni a többi. De hagyjuk, a fejében vándorolni egy kicsit, ha ők még nem egészen wandered-- mi lesz a menetideje találni valami ebben a listában? A fenébe is, ez nagy O n ami nem rossz, a méltányosság. De ez lineáris. Adtunk fel, amit a szolgáltatás A tömbök mozgatásával több felé ezt a képet dinamikusan szőtt együtt vagy kapcsolt csomópont? Már feladta véletlen hozzáférésű. Egy tömb szép, mert matematikailag minden vissza vissza a háttal. Annak ellenére, hogy ezt a képet úgy néz ki, szép, és még de úgy néz ki, mint ezek a csomópontok szépen egymástól távol, a valóságban akkor bárhol lehet. OX1, Ox50, Ox123, Ox99, ezeket csomópontok bárhol lehet. Mivel a malloc nem lefoglalni memóriát a kupac, de bárhol a kupac. Nem feltétlenül tudják, hogy ez lesz vissza háttal. És ezt a képet a valóság Nem lesz elég a szép. 

Szóval ez fog tartani egy kis dolgozni, hogy végrehajtja-e ezt a funkciót. Szóval végre a Keresés gombra. És majd meglátjuk, egyfajta okos módja ennek. Tehát, ha én vagyok a kereső funkció és Kapok egy változó, egész n keresni, azt kell tudni, hogy a új szintaxis keresett belül A szerkezet, ami rámutatott arra, hogy ahhoz, hogy megtaláld n. Így csináljuk. 

Tehát először fogok menni előre, és állapítsa meg a csomópont *. És én fogom nevezni mutató, csak a konvenció. És én fogom inicializálása először. És most én is ezt számos módon. De én, hogy egy közös megközelítés. Bár a mutató nem egyenlő null, és ez érvényes szintaxis. És ez csak azt jelenti, nem a következő, így Amíg te nem mutatott semmit. Mit akarok? 

Ha a mutató pont n, hadd jöjjön vissza az, hogy equals-- egyenlő mi? Milyen értéket keressek? A tényleges n, amit átadott. Tehát itt van egy másik funkció C és több nyelven. Annak ellenére, hogy a szerkezet az úgynevezett csomópont értéke n, teljesen jogos hogy is van egy helyi érv vagy változó hívott n. Mert még mi, a az emberi szem képes megkülönböztetni n értéke, hogy ez feltehetően ettől eltérő n. Mivel a szintaxis más. Van egy pont, és a mutató, mivel ez egy nem ilyen dolog. Tehát ez rendben van. Ez rendben van, hogy hívja őket ugyanazokat a dolgokat. 

Ha találsz ezt, én vagyok szeretne majd csinálni valamit mint bejelenteni, hogy megtaláltuk az n. És mi hagyjuk, hogy a megjegyzést vagy pszeudokódja kódot. Else, és itt van a érdekes rész, amit nem akarok, ha a jelenlegi csomópont nem tartalmaz n, hogy érdekel? Hogyan elérni a következő? Ha az ujját a pillanat PTR, és ez mutatva bármilyen először mutat meg, hogyan mozog az ujjam A következő csomópont kódot? Nos, mi a morzsa vagyunk fogja követni ebben az esetben? KÖZÖNSÉG: [nem hallható]. David J. MALAN: Igen, így a következő. Tehát, ha megyek vissza a kód van, sőt, én vagyok menni előre, és azt mondják, mutató, amely csak egy átmeneti változó-- ez a furcsa nevet, PTR, de ez olyan, mint temp-- Megyek be mutató egyenlő bármi mutató fektettünk-- és újra, ez lesz a kicsit bugos a moment-- pont található. Más szóval, fogom vinni a ujj mutatna ezen a csomóponton itt fogom mondani, tudod mi, vessen egy pillantást a következő mező és mozgassa az ujját bármi is mutatna. És ez fog ismétlés, ismétlés, ismétlés. De ha nem az ujjam abba egyáltalán? Amint milyen kódsort beindul? KÖZÖNSÉG: [nem hallható] David J. MALAN: Ha pont, míg mutató nem egyenlő null. Egy bizonyos ponton az ujjam a lesz mutatva null és fogok megvalósítani itt a vége ennek a listának. Nos, ez egy kicsit fehér hazugság az egyszerűség kedvéért. Kiderült, hogy még akkor is, csak tanultam ezt pont jelölés szerkezetekhez, mutató nem egy struktúra. ptr mi? Csak, hogy több nitpicky. Ez egy mutató, hogy a csomópont. Ez nem egy csomópont is. Ha nem volt csillag itt, mutató absolutely-- ez a csomópont. Ez olyan, mint a héten egy nyilatkozat a változó, még akkor is, ha a "csomópont" új. 

De amint bemutatjuk a csillag, ez most a mutatót egy csomóponthoz. És sajnos nem tudja használni A pont jelölése a mutató. Ki kell használni a nyíl jelölést, ami feltűnően, az első alkalommal egy darab A szintaxis néz intuitív. Ez a szó szerint úgy néz ki, mint a nyíl. És ez egy jó dolog. És itt szó szerint úgy néz ki, mint egy nyíl. Szóval úgy gondolom, hogy ez a la-- én nem hiszem, túl elkötelezi itt-- I gondolom, hogy ez az utolsó új darab A szintaxis fogunk látni. És szerencsére, ez valóban egy kicsit intuitív. 

Nos, azok számára, akik talán inkább a régi módon, továbbra is használhatja a pont jelölést. De ahogy egy hétfői beszélgetés, először kell menni oda, megy, hogy címét, majd lépjen be a területen. Szóval ez is helyes. És őszintén szólva, ez a kicsit pedáns. Te szó szerint azt mondja, dereference a mutató és ott. Ezután fogd .N, a terület az úgynevezett n. De őszintén szólva, senki sem akar írja vagy olvassa el ezt. És így a világ kitalált A nyíl jelölés, amely egyenértékű, azonos, ez csak szintaktikai cukor. Így divatos szóval ezt jobban néz ki, vagy úgy néz ki, egyszerűbb. 

Szóval most fogok csinálni egy másik dolog. Fogom mondani, hogy "szünet", ha én már találtam, így nem tartja keresi. De ez a lényeg a kereső funkció. De ez sokkal könnyebb, a end, nem a séta a kódot. Valóban ez a formális végrehajtását A keresés a mai eloszlás kódot. Merem állítani, hogy betét nem különösen szórakoztató a séta vizuálisan, sem törölni, még bár a végén a nap úgy szűkülnek le, hogy meglehetősen egyszerű heurisztika. 

Így csináljuk. Ha lesz humor ide, tettem hogy egy csomó stressz labda. Hoztam egy csomó számot. És tudnánk, hogy csak néhány önkéntesek hogy képviselje 9., 17., 20., 22., 29., és 34.? Tehát lényegében mindenki ki van itt ma. Ez volt az egyik, kettő, három, négy, öt, hat ember. És én már kérte van-- látni, nem az egyik a hátsó emeli a kezét. OK, egy, kettő, három, négy, five-- hadd töltse balance-- hat. OK, akkor hat gyere fel. Szükségünk lesz a többi ember. Hoztunk extra stressz labda. És ha, a Csak egy pillanat, vonal magatokat csak szeret ezt a képet itt. 

Rendben. Lássuk, mi a neve? 

Közönség: Andrew. 

David J. MALAN: Andrew, Ön szám 9. Örülök, hogy találkoztunk. Itt van. Közönség: Jen. David J. MALAN: Jen. David. Number 17. Igen? 

Közönség: Én vagyok Julia. 

David J. MALAN: Julia, David. 20. számú. Közönség: Christian. David J. MALAN: Christian, David. A 22. És? 

Közönség: JP. David J. MALAN: JP. A 29. Így megy előre, és kap in-- Uh oh. Uh oh. Készenlét. 20.. Van valakinek egy marker? Közönség: Van egy Sharpie. David J. MALAN: Van egy Sharpie? OK. És van valakinek egy darab papírt? Mentse el az előadás. Gyerünk. Közönség: Van rá. David J. MALAN: Megvan? Rendben, köszönöm. Itt vagyunk. Vajon ez tőled? Épp most mentette meg a napot. Így 29. Rendben. Én elgépelt 29, de az OK gombra. Rajta. Rendben, adok a toll vissza egy pillanatra. Tehát ezek az emberek itt. Nézzük meg egy másik. Gabe, mit szeretne játszani az első elem itt? Szükségünk lesz, hogy pont ezeken a szép emberek. Tehát 9., 17., 20., 22., sort 29, majd 34. Vajon elveszíteni valakit? Van egy 34. Ahol did-- OK, aki azt akarja, hogy 34? OK, gyere fel, 34. Rendben, ez lesz megéri a csúcspontja. Mi a neve? 

Közönség: Peter. 

David J. MALAN: Peter, gyere fel. Rendben, itt egy csomó csomópontok. Minden srácok jelent az egyik ilyen téglalapok. Gabe, a kissé furcsa ember, ki képviseli az első. Így a mutató egy kicsit kisebb a képernyőn, mint mindenki más. És ebben az esetben mindegyik a bal kezet fog vagy pont le, ezáltal képviselő null, így hanem a hiánya egy mutatót, vagy ez lesz mutatva egy csomópont melletted. 

Tehát most, ha szépít magatokat, mint a képen itt, megy előre, és pont minden más, a Gabe különösen mutatva 9-es szám, hogy képviselje a listán. OK, és 34-a bal kezét kéne mutasson a padlóra. 

OK, így ez a láncolt lista. Tehát ez a forgatókönyv a kérdéses. És valóban, ez a reprezentatív egy osztály a problémák hogy lehet, megpróbálják megoldani a kódot. Azt akarod, hogy végül beilleszteni egy új elemet a lista. Ebben az esetben, mi lesz próbálja meg behelyezni a szám 55. De lesz különböző esetek, hogy fontolja meg. És valóban, ez lesz az egyik A nagy kép elvitelre itt, az, Melyek a különböző eseteket. Melyek a ha a körülmények vagy ágak, hogy a program esetleg? 

Nos, a szám akarsz betét, amely most már tudjuk, hogy 55, de ha nem tudja, előre, merem állítani beleesik legalább három lehetséges helyzetek. Ahol lehet, hogy egy új elem az? Közönség: És a végén, vagy középen. David J. MALAN: A végén, a a középső, vagy az elején. Tehát azt állítom, van legalább három problémát meg kell oldani. Nézzük választani, mi van talán vitathatatlanul a legegyszerűbb egyik, ahol az új elem tartozik az elején. Szóval lesz kód meglehetősen mint keresni, amit csak írtam. És én megyek is PTR, amely Én képviselek az ujjam, mint mindig. 

És ne feledd, milyen értéket jutottunk inicializálni PTR? Így inicializáltuk NULL kezdetben. De akkor mit tegyünk, ha már volt benne keresési funkció? Mi meg azt egyenlő az első, ami nem jelenti ezt. Ha én meg PTR egyenlő az első, amit meg a kezem tényleg mutat? Jobb. Tehát, ha Gabe és én hogy egyenlő értékek itt, kell mindkét pont a szám 9. 

Tehát ez volt a kezdete a történet. És most ez csak egyszerű, bár a szintaxis új. Fogalmi ez csak lineáris keresést. 55 egyenlő 9? Vagy inkább, mondjuk kevesebb, mint 9. Mert próbálok kitalálni, hová tegye 55. Kevesebb, mint 9, kevesebb, mint 17, kevesebb mint 20, kevesebb, mint 22, kevesebb, mint 29, kevesebb, mint 34, no. Tehát most vagyunk abban az esetben, egyike legalább három. 

Ha a beszúrni kívánt 55 ide, mit sornyi kódot kell, hogy végre? Hogyan működik ez a kép az emberek meg kell változtatni? Mit csináljak a bal kezemmel? Ez legyen null kezdetben, mert én vagyok az a lista végén. És mi történik itt Peter, ugye? Ő lehet a baj, hogy pont nekem. Tehát azt állítom, van legalább két sor A kód a minta kódját a mai hogy fogja végrehajtani ezt forgatókönyv, hozzátéve 55 a farok. És tudtam, hogy valaki hop és csak képvisel 55? Rendben, te vagy az új 55. 

Így most mi van, ha a következő forgatókönyv jön, és szeretnénk beszúrni a elején vagy a fejét ez a lista? És mi a neve, száma 55? 

Közönség: Jack. 

David J. MALAN: Jack? OK, örülök, hogy találkoztunk. Üdvözöljük a fedélzeten. Tehát most megyünk helyezze, mondjuk, az 5-ös szám. Itt a második esetben a három kitaláltunk előtt. Tehát, ha 5 tartozik az elején, nézzük meg, hogyan látjuk, hogy ki. Én inicializálni a ptr mutató a 9-es szám újra. És rájöttem, ó, 5 kevesebb, mint 9. Csináld ezt a képet nekünk. Kinek a keze, Gabe és Dávid vagy-- mi 9-es szám neve? 

Közönség: Jen. 

David J. MALAN: Jen hands-- amely a kezünkből kell változtatni? OK, így Gabe rámutat, hogy mi most? Rám. Én vagyok az új csomópontot. Úgyhogy csak ilyen lépés ide meg vizuálisan. És közben mit pont ezt? Mégis hol vagyok mutatva. Szóval ennyi. Szóval tényleg egy sor kód javítások ez a bizonyos kérdés, úgy tűnik. Rendben, ez jó. És valaki egy helykitöltő 5? Gyere fel. Kapsz legközelebb. 

Rendben, now-- és Mellesleg, a neveket Nem én kifejezett említést jog Most, pred mutató, elődje mutató és az új mutató, az csak a neveket adott a minta kódot a mutatók vagy a kezem, hogy ez a fajta mutat körül. Mi a neve? 

Közönség: Christine. 

David J. MALAN: Christine. Üdvözöljük a fedélzeten. Rendben, nézzük meg most némileg bosszantó forgatókönyv, amelynek szeretnék beilleszteni valami hasonló 26 ebbe. 20? Mi az? Ezek a are-- jó dolog, amit meg ezt a tollat. Rendben, 20. Ha valaki tudna még egy darab papír kész, csak case-- minden rendben. Oh, érdekes. Hát ez egy példa Egy előadás bug. OK, így mi is a neved? Közönség: Julia. David J. MALAN: Julia, tudsz pop , és tégy úgy, mintha soha ott? OK, ez soha nem történt meg. Köszönöm. Tegyük fel, hogy szeretnénk beilleszteni Julia ebbe láncolt lista. Ő a 20. számú. És persze ő fog tartozni a begin-- nem mutatnak meg semmit. Hogy a keze is olyan lehet le null vagy valami szemetet értéket. Mondjuk el a rövid történetet. Én mutatva 5. szám ebben az időben. Aztán nézd 9. Aztán nézd 17. Aztán nézd 22. És rájöttem, ó, Julia kell menni, mielőtt 22. Tehát mi kell történnie? Kinek a kezében kell változtatni? Julia, az enyém, vagy-- mi a neved? 

Közönség: Christian. 

David J. MALAN: keresztény vagy? 

Közönség: Andy. 

David J. MALAN: Andy. Keresztény vagy Andy? Andy kell mutatni? Julia. Rendben. Szóval Andy, akarsz rámutatni Julia? De várjunk csak egy percet. A történet eddig, Én vagyok az a fajta egy felelős, abban az értelemben, hogy a mutató az a dolog, ami halad át a listát. Lehet, hogy egy nevet Andy, de nincs változó nevű Andy. Az egyetlen változó van az Először is, aki képviseli Gabe. 

Tehát ez valójában miért így messzire nem szükséges ezt. De most a képernyőn van beszélve ismét a Pred mutató. Szóval hadd legyek egyértelmű. Ha ez a mutató, már jobb egy kicsit intelligensebb az én iteráció. Ha nem baj, hogy megy át itt megint mutatott itt, rámutatva itt. De hadd van Pred mutató, elődje mutató, az fajta mutatott a elem most voltam. Tehát, ha elmegyek itt, most a bal oldali frissítéseket. Mikor megy itt a bal oldali frissítéseket. És most már nem csak egy mutató, az elem, hogy megy után Julia, Még mindig van egy mutatót Andy, az elem előtt. Így van hozzáférése, lényegében, zsemlemorzsa, ha úgy tetszik, hogy az összes szükséges mutatók. 

Tehát, ha én mutatott Andy és én is mutat A keresztény, akiknek a kezén most meg kell mutatni máshol? Így Andy már mutatni Julia. Julia most mutatni Christian. Mert lehet másolni a jobb keze mutató. És hogy hatékonyan hozza meg vissza erre a helyre itt. Tehát röviden, bár ez a elvisz minket a fajta örökre hogy valóban frissítéséhez láncolt lista, észre hogy a műveletek viszonylag egyszerű. Ez az egy, kettő, három sornyi kódot végül. De köré azokat sornyi kódot feltehetően egy kis logika, amely hatékonyan felteszi a kérdést, hol vagyunk? Vagyunk az elején, a középső, vagy a végén? 

Nos, biztosan vannak más művelet talán végre. És ezek a képek itt csak ábrázol amit most tett az emberekkel. Mi a eltávolítása? Ha azt akarom, hogy, például, távolítsa el a számot 34 vagy 55, Talán van ugyanolyan kód, de fogok kell egy vagy két lépésben. Mert mi újság? Ha leveszem valaki a végén, mint szám 55, majd 34, mit is kell változtatni, mint én, hogy? Én, hogy ne evict-- mi a neved? 

Közönség: Jack. 

David J. MALAN: Jack. Én nem csak evict-- szabad Jack, így a szó szoros értelmében hívás ingyenes Jack, vagy legalábbis a mutató ott is, de most már mit kell változtatni a Peter? Keze jobban indul lefelé. Mert amint hívom mentes a Jack, ha Péter még mindig mutat Jack és ezért folyamatosan áthaladó a listát, és nem férhet hozzá ehhez mutató, ez az, amikor a régi barát szegmentáció hiba talán valóban rúg. Mert már adott a memória vissza Jack. 

Akkor ott ügyetlenül egy pillanatra. Mert már csak egy pár utolsó művelet, hogy fontolja meg. Eltávolítása a lista élére, vagy a beginning-- és ez a Egy kicsit bosszantó. Mert tudnunk kell, hogy Gabe egyfajta különleges ebben a programban. Mert valóban, ő a saját mutató. Ő nem csak, hogy rámutatott, mint szinte mindenki más itt. 

Tehát, amikor a feje a lista eltávolították, akinek keze kell változtatni most? Mi a neved? 

Közönség: Christine. 

David J. MALAN: vagyok szörnyű A nevek, látszólag. Tehát Christine és Gabe, akinek a kezében kell változtatni amikor megpróbáljuk eltávolítani Christine, 5-ös, a kép? OK, így csináljuk Gabe. Gabe fog mutatni, Feltételezhető, hogy a 9-es szám. De mi a következő lépés történjen? Közönség: Christine kellene null [nem hallható]. David J. MALAN: OK, akkor valószínűleg make-- hallottam "null" valahol. Közönség: Null és szabad neki. David J. MALAN: NULL mi? Közönség: Null és szabad neki. David J. MALAN: Null és szabad neki. Tehát ez nagyon egyszerű. És ez így tökéletes, hogy te most már sort ott áll, nem tartozik. Mert már függetlenített a listából. Már ténylegesen árva a listából. És így még jobban hívják szabad most Christine adni, hogy az emlékezet vissza. Ellenkező esetben minden egyes alkalommal, amikor törölni egy csomópontot a listából mi lehet, hogy a lista rövidebb, de valójában nem csökkenő a méret a memóriában. És ha folyamatosan hozzá és hozzátéve, hozzátéve, a dolgok a listán, a számítógép lehet, hogy lassabb és lassabb és lassabb, mert én fut ki memória, akkor is, ha én nem vagyok valójában a Christine bytes memória többé. 

Így a végén vannak más forgatókönyvek, a course-- eltávolítás középen, eltávolítás a végén, ahogy láttuk. De sokkal érdekesebb kihívás most az, lesz, hogy fontolja meg pontosan mi a működési idő. Tehát nem csak tudja tartani a darab papír, ha Gabe, nem bánnád ad mindenki a stressz labdát. Köszönöm szépen, hogy a láncolt lista Az önkéntesek itt, ha lehet. 

[Taps] 

David J. MALAN: Rendben. Tehát egy pár analitikai kérdés akkor, ha tehetném. Láttuk ezt a jelölést korábban, nagy O és az Omega, a felső korlátok és alsó határ a futási ideje néhány algoritmus. Tehát nézzük csak egy pár kérdést. 

Egyet, és azt mondta, hogy előtt, mi a futó keresés ideje a lista szempontjából nagy O? Mi egy felső határt a futó ideje keres a láncolt lista végrehajtott önkénteseink itt? Ez a nagy O N lineáris. Mert a legrosszabb esetben, az elem, mint a 55, mi lehet, hogy keres lehet, ahol a Jack volt, egészen a végén. És sajnos, ellentétben egy tömb nem tudjuk divatos ebben az időben. Annak ellenére, hogy minden a mi az emberek voltak, sorrendje a kis elemeket, 5, egészen a nagyobb elem, 55, ez általában egy jó dolog. De mit csinál az a feltételezés már nem teszi lehetővé számunkra, hogy nem? KÖZÖNSÉG: [nem hallható] David J. MALAN: Mondd még egyszer? Közönség: Random hozzáférés. David J. MALAN: Véletlen hozzáférés. És viszont, hogy azt jelenti, hogy nincs már nem használja gyenge nulla, intuíció, és nyilvánvaló a bináris keresés és oszd meg és uralkodj. Mert még akkor is, emberek képesek nyilvánvalóan látom, hogy Andy vagy keresztény volt nagyjából a közepén a lista, Annyit tudunk, hogy egy számítógép futást a lista a kezdetektől fogva. Így már feladta, hogy a véletlen hozzáférés. 

Tehát nagy O n most a felső kötött a keresési idő. Mi a helyzet omega a keresési? Mi ez az alsó határ a keresést néhány szám a listán? KÖZÖNSÉG: [nem hallható] David J. MALAN: Mondd még egyszer? Közönség: Egy. David J. MALAN: Egy. Így állandó idő. A legjobb esetben, Christine sőt az elején a lista. És keresünk 5-ös, így találtunk rá. Tehát nem nagy ügy. De kell, hogy legyen a a lista elején ebben az esetben. Mi valami hasonló Delete? Mi van, ha azt szeretné, hogy törölni egy elemet? Mi az a felső határ és az alsó határ A törlés valamit a kapcsolt listát? KÖZÖNSÉG: [nem hallható] David J. MALAN: Mondd még egyszer? Közönség: n. David J. MALAN: n valóban a felső határ. Mert a legrosszabb esetben igyekszünk törölni Jack, mint mi most nem. Ő egészen a végén. Visz minket örökre, vagy n lépéseket, hogy megtalálja őt. Szóval ez egy felső korlátot. Ez lineáris, biztos. És a legjobb esetben futási idő vagy az alsó határt a legjobb esetben lenne állandó idő. Mert talán megpróbáljuk törölni Christine, és mi csak szerencséd ő az elején. Várj egy percet. Gabe volt az elején, és mi is kellett frissíteni Gabe. Szóval ez nem csak egy lépés. Így van ez valóban állandó időben, a legjobb esetben, hogy távolítsa el a legkisebb elem? Ez, bár lehet, hogy két, három, vagy akár 100 sornyi kódot, ha ez azonos számú vonalak, nem néhány hurok, és független a méret A lista, teljesen. Törlése az elem, az elején a lista, akkor is, ha meg kell foglalkozni Gabe még mindig állandó idő. 

Szóval, ez úgy tűnik, mint egy hatalmas lépés visszafelé. És micsoda időpocsékolás Ha a hét egy és hét nulla volt nem csak pszeudokódja kód de a tényleges kód végrehajtani valamit, ami log alap n, vagy jelentkezzen, inkább, n, 2-es alapú, tekintve a működési idő. Akkor miért a fene azt szeretnénk kezdeni használ valamit, mint a láncolt lista? Igen. 

Közönség: így hozzá elemeket a tömb. David J. MALAN: így hozzá elemeket a tömb. És ez is a tematikus. És mi továbbra is látni ez, ez a trade-off, sok mint láttuk a trade-off a merge sort. Mi tényleg felgyorsíthatja keresés vagy válogatás, inkább, ha kiad egy kicsit több helyet és egy további darab memória vagy egy tömb a merge sort. De többet költenek helyet, de időt takaríthat meg. Ebben az esetben, mi feladom idő, de vagyunk egyre rugalmasság, dinamizmus ha úgy tetszik, amely vitathatatlanul pozitív funkciót. 

Mi is a kiadások helyet. Milyen értelemben kapcsolt lista drágább szempontjából a tér, mint egy tömb? Hol van az extra helyet jön? Igen? 

KÖZÖNSÉG: [nem hallható] mutató. 

David J. MALAN: Igen, is a mutató. Tehát ez minorly bosszantó hogy többé nem am Én tárolása csak egy int képviseletére int. Én tárolása egy int és a mutatót, ami szintén 32 bit. Szóval szó szerint megduplázódott az összeg a tér szó. Szóval ez egy trade-off, de ez abban az esetben, int. Tegyük fel, hogy te nem tárolja int, de tegyük fel, mindegyik téglalap vagy minden egyes ilyen emberre volt képviselő Egy szó, egy angol szó, amely Lehet, hogy öt karakter, 10 karakter, talán még jobban. Akkor hozzá csak 32 több bit Lehet, hogy kevésbé a nagy dolog. 

Mi van, ha minden a diákok a demonstráció szó szerint diák struktúrákat az neveket és házak, és talán telefonszámok és a Twitter kezeli és a hasonlók. Tehát az összes mezőt kezdtük beszélt a minap, sokkal kisebb a nagy dolog, mint a csomópontok minél több érdekes és nagy költeni, ugye, egy további mutató csak azok összekötésére. De valóban, ez egy trade-off. És valóban, a kód bonyolultabb, mint majd lásd a lapoz hogy az adott példa. De mi van, ha nem volt néhány szent grál itt. Mi lenne, ha nem egy lépést hátra, hanem egy hatalmas lépés előre és végrehajtása adat szerkezet, amelyen keresztül mi megtalálható elemeket, mint a Jack vagy Christine vagy bármely más elemek ebben tömb igazi konstans időben? Search állandó. Törlés állandó. Betét állandó. Mindezek a műveletek állandó. Ez lenne a szent grál. És ez az, ahol mi felveszi legközelebb. Viszlát akkor.