>> [Zenelejátszási]
>> DOUG LLOYD: OK, így a Ezen a ponton során,
már lefedett sok az alapokat a C. Tudjuk, hogy sokat változók, tömbök,
mutatók, minden, ami jó dolog.
Ezek mind egyfajta beépített hogy lássa, mint a fundamentumok,
de ennél többre vagyunk képesek, igaz?
Tudjuk kombinálni a dolgokat valamint érdekes módon.
>> És így csináljuk meg, kezdjük ágaznak, amit C ad nekünk,
és meg kell kezdeni, hogy hozzon létre saját adatok szerkezetek segítségével ezeket épület
blokkok együtt csinálni valamit igazán értékes, hasznos.
Ennek egyik módja, amit tehetünk ez beszélni gyűjtemények.
Szóval eddig is megvolt egyfajta adatok struktúra képviselő gyűjtemények
A tetszik értékek, hasonló értékeket.
Ez lenne egy tömbben.
Van gyűjtemények egészek, vagy gyűjtemények karakterek és így tovább.
>> Struktúrák is egyfajta adatok szerkezete az információgyűjtés,
de ez nem gyűjtésére, mint értékek.
Ez általában keverékek különböző adattípusok együtt belsejében egy dobozban.
De ez önmagában nem használt lánc együtt
vagy csatlakoztassa a hasonló tételek, mint egy tömb.
A tömbök nagy elem felnéz, de visszahívás
hogy ez nagyon nehéz szúrni egy tömb,
hacsak mi behelyezése a A legvégén a tömbben.
>> És a legjobb példa van mert ez a fajta behelyezése.
Ha felidézzük videónkat elhelyezésének sort,
volt egy csomó költségén részt, amelynek
felvenni elemeket, és a több műszakos őket az útból, hogy illeszkedjen valamit
a közepén a tömb.
Tömbök is szenvednek a másik probléma, ami rugalmatlansága.
Amikor egy tömböt, kapunk egy lövés is.
Kapunk mondani, azt akarom, ez a sok eleme van.
Lehet, hogy a 100, talán legyen 1000, talán
legyen x ahol x jelentése egy szám, hogy a felhasználói adott nekünk egy azonnali, vagy a parancs
vonal.
>> De mi csak kap egy lövés, mi nem értem, hogy majd azt mondják, jaj, valójában én
szükséges 101, vagy szükségem x plusz 20.
Túl késő, mi már kijelentette, a tömb, és ha azt akarjuk, hogy 101 vagy x
plusz 20, van, hogy állapítsa egy teljesen más tömb,
másolja az összes elemet a tömb vége, és akkor mi van elég.
És mi van, ha tévedünk újra, mi ha valóban szükség van 102, vagy x plusz 40,
van, hogy ezt újra.
Tehát ők nagyon rugalmatlan átméretezni adataink,
de ha kombináljuk össze néhány Az alapokat, hogy mi már
értesült mutatók és struktúrák, különösen a dinamikus memória
elosztása a malloc, mi lehet, hogy ezeket a darabokat össze
hogy hozzon létre egy új adatok structure-- egy egyszeresen láncolt lista talán say--
amely lehetővé teszi számunkra, hogy nő, és zsugorodik a gyűjtemény értékek
és mi nem lesz elvesztegetett hely.
>> Tehát újra, hívja ezt a gondolatot, ez a fogalom, egy láncolt lista.
Különösen ez a videó vagyunk beszélünk egyszeresen láncolt lista,
majd egy másik videó beszélgetünk mintegy kétszeresen láncolt listák, amelyek
csak változata a téma itt.
De egyszeresen láncolt lista áll csomópontok,
csomópontok csak, hogy egy absztrakt term-- ez csak valami hívom
ez egyfajta szerkezete alapvetően én vagyok?
Csak megy, hogy ez egy node-- és ez csomópont két tag, vagy a két területen.
Azt adatokat, általában egy egész, egy karakter úszó,
vagy lehet más adattípus hogy már definiált típusú def.
És tartalmaz egy mutatót egy másik csomópontot az azonos típusú.
>> Tehát van két dolog belsejét ez a csomópont, adatok és mutatóját
egy másik csomópont.
És ha elkezd láthatóvá ezt, akkor gondolj rá
mint egy lánc csomópontok vannak egymáshoz csatlakoztatva.
Megvan az első csomópontot, akkor adatokat tartalmaz, és egy mutatót
a második csomóponthoz, amely tartalmaz adatokat, és egy mutatót a harmadik csomópont.
És hogy ezért nevezzük ezt a láncolt lista, ők kapcsolódnak egymáshoz.
>> Mit jelent ez a különleges node szerkezet néz ki?
Nos, ha visszahívja a videót meghatározó egyéni típusú, típusú def,
tudjuk meg egy structure-- és írja meg egy szerkezetet, mint ez.
tyepdef struct sllist, és akkor én vagyok szó használatával érték itt önkényesen
jelzi, bármilyen típusú adatot igazán.
Lehet hárítani integer vagy float, akkor lehetett volna, amit akarsz.
Ez nem korlátozódik csupán egészek, vagy ilyesmi.
Tehát az érték mindössze egy tetszőleges adatok típusát, majd egy mutatót
egy másik csomópont azonos típusú.
>> Nos, van egy kis fogás Itt a meghatározó struktúra
ha ez egy önálló referenciális szerkezetet.
Van, hogy egy ideiglenes Íme az én szerkezetet.
A nap végén I egyértelműen akar nevezni
sll csomópont, ami végső soron az új Íme egy részét az esetem meghatározása,
de nem tudom használni sll csomópont a közepén ezt.
Az ok pedig, én nem létrehozott egy típusú úgynevezett sll csomópont
amíg nem hit ez az utolsó pont itt.
Addig a pontig, azt kell, hogy legyen Egy másik módja annak, hogy olvassa el ezt a típusú adatokat.
>> És ez egy önálló referenciális típusú adatokat.
Ez, s egy adat típusát szerkezet, amely tartalmaz egy adat,
és egy mutató egy másik szerkezete az azonos típusú.
Szóval kell, hogy képes hivatkozni Ezen adatok típusa legalábbis átmenetileg,
így adva, hogy egy átmeneti neve struct sllist
lehetővé teszi számomra, hogy majd azt mondják, szeretnék egy mutatót egy másik struct sllist,
Egy struct sllist csillag, majd miután már befejezte a meghatározása,
Én most hívják ezt a fajta egy sll csomópontot.
>> Szóval ezért látod van egy ideiglenes nevet itt,
hanem állandó nevét.
Néha lehet látni meghatározásai szerkezet,
például, hogy a nem önálló referenciális, hogy
nincs specifikátor nevét.
Ez csak azt mondom typedef struct, nyissa kapcsos zárójel, majd határozza meg.
De ha struct magától referenciális, mivel ez az egyik,
akkor meg kell adnia a átmeneti típus neve.
De végül is, most hogy ezt megtette,
mi csak utalnak ezek a csomópontok, ezek az egységek,
mint sll csomópontok célokra A többi ezt a videót.
>> Rendben, tehát tudjuk, hogyan kell hozzon létre egy láncolt lista csomópontot.
Tudjuk, hogyan kell meghatározni láncolt listájának csomópontot.
Most, ha fogunk kezdeni használja őket, hogy információt gyűjtsön,
van egy pár műtétekhez meg kell érteniük és dolgozni.
Tudnunk kell, hogyan kell létrehozni A láncolt lista a semmiből.
Ha nincs lista már, akarunk kezdeni egy.
Tehát szükségünk van ahhoz, hogy hozzon létre egy láncolt lista,
meg kell keresni valószínűleg linken keresztül lista
találni egy elem keresünk.
Meg kell, hogy tudja beszúrni új dolgokat a listán,
azt akarjuk, hogy a listát, hogy képes növekedni.
És hasonlóképpen, szeretnénk tudni törölni a dolgokat a listánkról,
azt akarjuk, hogy a listát, hogy képes zsugorodni.
És a végén a mi programok, különösen
ha felidézni, hogy mi vagyunk dinamikusan memórialefoglalás
építeni ezeket a listákat általában, szeretnénk felszabadítani az összes, hogy a memória
ha végeztünk vele dolgozni.
És ezért meg kell, hogy képes legyen törlése teljes kapcsolt lista egy sikertelen csapásra.
Szóval menjünk át Néhány ilyen műveletek
és hogyan lehet elképzelni őket, beszélgettek pszeudokódja kódot pontosan.
Ezért szeretnénk létrehozni láncolt lista, így talán
szeretnénk, hogy egy függvény definiálása ezzel a prototípus.
sll csomópont csillag, hozzon létre, és én halad egy érv, néhány tetszőleges adat
írja újra, néhány tetszőleges típusú adatokat.
De én returning-- ezt a funkciót kell vissza hozzám egy mutatót, hogy egy egyszeresen
láncolt lista csomópont.
Ismét próbálunk létrehozni A láncolt lista a semmiből,
így kell egy pointert a listán amikor végzek.
>> Tehát mi a lépések itt?
Nos, az első dolog, én vagyok eredménye, hogy dinamikusan
osztja helyet egy új csomópontot.
Ismét mi hozzuk létre a semmiből levegőt, így szükséges, hogy a malloc helyet érte.
És persze azonnal miután malloc,
mi mindig győződjön meg arról, hogy mi pointer-- nem kaptunk vissza null.
Mert ha megpróbálunk hódolat null pointer,
fogunk szenvedni segfault és nem akarjuk, hogy.
>> Aztán azt akarjuk, hogy töltse ki a mezőt, akarjuk inicializálni az érték mezőbe
és alapértéket a következő mezőbe.
És akkor mi szeretnénk az alábbiakra: végül a függvény prototípus indicates-- akarunk
vissza a mutató egy sll csomópontot.
Szóval mit csinál ez kinézni vizuálisan?
Nos, először is meg fogunk dinamikusan osztja helyet egy új sll csomópont,
így malloc-- ez A vizuális ábrázolás
A csomópont most létrehozott.
És győződjön meg róla, ez nem null-- ebben az esetben,
A kép nem lenne mutattak ki, ha ez nulla,
mi lett volna elfogyott a memória, így vagyunk jó odamenni.
Szóval most mi vagyunk a lépéssel C, formázza meg a csomópontok érték mezőbe.
Nos, ez alapján a funkciót hívja használok itt,
úgy néz ki, mint szeretnék átadni a 6., úgyhogy 6 Az Érték mezőben.
Most, formázza meg a következő mezőbe.
Nos, mit fogok ott csinálni, semmi sem jövő, igaz,
ez az egyetlen dolog a listán.
Szóval mi a következő dolog a listán?
>> Nem szabad mutat sehova, ugye.
Semmi mást nem, akkor mi az, az a koncepció, tudom, hogy ez nothing--
mutatókat semmi?
Meg kell talán azt akarjuk, hogy egy null pointer van,
és én képviseli a null mutatót csak egy piros doboz,
nem tudunk tovább menni.
Mint látni fogjuk egy kicsit később, mi lesz végül láncok
A nyilak összekötő ezek a csomópontok együtt,
de ha bejön a piros doboz, ami null,
nem tudunk tovább menni, itt a vége a lista.
>> És végül, mi csak szeretnénk vissza mutatót a csomóponton.
Így hívjuk meg az új, és vissza fog térni az új
így lehet használni bármilyen funkciót létrehozta.
Tehát ott megy, Létrehoztunk egy egyszeresen láncolt lista csomópont a semmiből,
és most van egy lista tudunk dolgozni.
>> Most, mondjuk már Van egy nagy lánc,
és meg akarjuk találni valamit.
És azt akarjuk, hogy a funkció folyik vissza igaz vagy hamis, attól függően,
arról, hogy létezik az érték a listán.
A függvény prototípus, vagy nyilatkozatot adott funkció,
nézhet this-- bool találni, és akkor szeretnénk átadni a két érvet.
>> Az első, egy mutatót a első eleme a láncolt lista.
Ez tulajdonképpen az, amit egy mindig szeretné nyomon követni,
és valóban lehet valami, hogy Ön még fel a globális változót.
Ha létrehozott egy listát, Mindig, mindig
Nyomon szeretné követni az igen első eleme a listán.
Így lehet hivatkozni a többi elemek csak a következő a láncot,
anélkül, hogy tartani pointerek ép minden egyes eleme.
Csak akkor kell nyomon követni az első egy, ha ők mind egymáshoz láncolva.
>> És akkor a második dolog mi elhaladó újra
önkényesen some-- bármilyen adattípust vagyunk
keres ott van belül remélhetőleg egyik csomópont a listában.
Tehát mi a lépések?
Nos, az első dolog, amit tennie, hozunk létre egy keresztirányú mutatót
rámutatva, hogy a listák fejét.
Nos, miért csináljuk ezt, már Van egy mutató a listák vezetője,
miért nem csak mozgatni, hogy az egyik körül?
Nos, mint mondtam, ez tényleg fontos számunkra
hogy mindig nyomon követni a legelső elem a listában.
És így sokkal jobb hogy hozzon létre egy másolatot, hogy
és használni, hogy mozogni így soha Véletlenül elmozdulni, vagy mindig
Van egy mutató egy bizonyos ponton, amely jobbra az első eleme a listán.
Tehát jobb, hogy hozzon létre egy második, hogy az általunk használt mozgatni.
>> Aztán csak összehasonlítani, hogy Az érték mező a csomóponton
az, amit keresünk, és ha ez Nem, mi csak lépjen a következő csomópontot.
És mi csinálom, hogy újra és újra, és újra,
amíg akár meg, az elem, vagy elérünk
null-- elértük a végét A listán van, és nincs ott.
Ez remélhetőleg cseng Önnek, mint csak lineáris keresés,
mi csak lemásolják azt egyszeresen láncolt lista szerkezete
ahelyett, hogy a tömb csinálni.
>> Tehát itt egy példa egyszeresen láncolt lista.
Ez az egyik áll Öt csomópontok, és van
egy mutatót a fejét a listát, amely az úgynevezett listán.
Az első dolog, amit akarok, újra létrehozni, hogy a bejárás mutató.
Így most már két mutató Ezen a ponton, hogy ugyanaz a dolog.
>> Most, itt megjegyezni azt is, én nem Van malloc minden helyet trav.
Azt nem mondtam, trav egyenlő malloc valamit, hogy csomópont már létezik,
hogy a tér a memóriában már létezik.
Tehát minden, amit valójában csinál van létrehoz egy másik mutatót is.
Én nem mallocing további hely, csak most már két mutató
rámutatva, hogy ugyanaz a dolog.
>> Szóval van 2, amit én keresek?
Nos, nem, így ahelyett, hogy én vagyok fog átmenni a következőre.
Tehát alapvetően azt mondanám, trav egyenlő trav következő.
3, amit én keresek, nem.
Szóval továbbra is megy keresztül, míg végül
eljutni 6 ami azt, amit keresek alapozva, a függvényhívás
Nekem van a csúcson ott, és így kész vagyok.
>> Mi lenne, ha az elem vagyok keres nincs a listán,
tart még mindig dolgozni?
Nos, észreveheti, hogy a listán Itt finoman más,
Ez is egy olyan dolog, ami Fontos a láncolt listák,
Önnek nem kell megőrizni ezek az adott sorrendben.
Próbálja ki Ön is szeretné, de lehet, hogy már észre,
hogy mi nem követi nyomon a mi több elemet vagyunk.
>> És ez a fajta egy kereskedelmi, hogy mi Van a láncolt lista versek tömbök,
van az, nincs véletlen hozzáférésű többé.
Nem lehet csak mondani, azt akarom, menni a 0. elem,
vagy a 6. elem az én tömb, amit tehetünk egy tömbben.
Nem tudok mondani akarok menni a 0. elem, vagy a 6. elem,
vagy a 25. eleme én láncolt lista, nincs index velük kapcsolatban.
És ez így nem igazán számít ha megőrizzük a listát érdekében.
Ha azt szeretnénk, hogy Ön biztosan, de van
nincs ok, miért kell kell őrizni bármilyen sorrendben.
Tehát újra, próbáljuk meg megtalálja 6 ebben a listában.
Nos, kezdjük a kezdődő, nem találunk 6,
és akkor továbbra sem találni 6, amíg végül eljut ide.
Szóval most trav pontot a csomópont amely 8 és hat nem ott.
>> Így a következő lépés az lenne, hogy menjen a következő mutató,
így mondják trav egyenlő trav következő.
Nos, trav következő, jelzett A piros doboz van, null.
Szóval van hová menj, és ezért ezen a ponton
arra lehet következtetni, hogy elértük a végén a láncolt lista,
és 6 nem ott.
És akkor vissza kell hamis ebben az esetben.
>> OK, hogyan tegyen be egy új csomópontot az láncolt lista?
Így voltunk képesek létrehozni A láncolt lista a semmiből,
de akkor ehhez felépíteni egy láncot, és nem
hozzon létre egy csomó különböző listákat.
Azt szeretnénk, hogy egy listát, hogy van egy csomó csomópontok benne,
Nem egy csomó listák egyetlen csomópont.
Tehát nem csak tartani a CREATE funkció a korábban megadott, most
akar szúrni egy listáját, amely már létezik.
>> Tehát ebben az esetben, megyünk átadni két érv,
A mutatót a fejét, hogy láncolt lista, hogy szeretnénk felvenni.
Ismét, ez miért olyan Fontos, hogy mindig
nyomon követni azt, mert ez az egyetlen módja annak, hogy valóban
hivatkoznia kell az egész lista Csak egy mutatót az első elemet.
Tehát szeretnénk átadni a mutatót, hogy az első elem,
és milyen értéket is szeretnénk felvenni a listára.
És végül ez a funkció fog visszatérni egy mutatót
hogy az új vezetője a láncolt lista.
>> Milyen lépésekben itt szó?
Nos, például csak létre, meg kell dinamikusan osztja
hely egy új csomópontot, és ellenőrizze, Biztos, hogy ne fogyjon el a memóriában, újra,
mert mi használ malloc.
Aztán szeretne venni és helyezze be a csomópont,
így fel a számot, amit Val, a csomópont.
Azt akarjuk, hogy helyezze be a csomópontra Az elején a láncolt lista.
>> Oka van annak, hogy én akarom ezt, és ez
Lehet, hogy érdemes egy második szünetelteti a videót itt,
és arra gondolok, miért akarná illessze elején egy kapcsolt
listán.
Ismét azt már korábban említettem hogy nem igazán
számít, ha megőrizzük azt bármilyen érdekében, így lehet, hogy ez egy nyom.
És láttad, hogy mi történne, ha akart az alábbiakra: vagy csak egy pillanatot
ezelőtt, amikor megyünk a keresés akkor
látta, hogy mi történne, ha akartuk
beszúrni végén a listában.
Mert nincs mutatót az a lista végére.
>> Tehát az ok, hogy szeretnék beilleszteni az elején,
azért van, mert meg tudom csinálni azonnal.
Nekem van egy mutató az elején, és fogjuk látni ezt a vizuális második.
De ha azt szeretné szúrni a végén, El kell kezdeni az elején,
áthalad egészen a végéhez, majd tack be.
Szóval ez azt jelentené, hogy behelyezése végén a lista
válna o n működését, megy vissza
hogy a vitát a számítási komplexitás.
Ez lett belőle egy o n működését, ahol a lista egyre nagyobbak, és nagyobb,
és nagyobb, ez lesz egyre nehezebb a forduláshoz valamit
a végén.
De ez mindig nagyon könnyű csapáson valamit az elején,
Ön mindig az elején.
>> És majd meglátjuk vizuális e újra.
És akkor egyszer kész vagyunk, ha egyszer mi már be az új csomópontot,
szeretnénk visszatérni a mutatót az új vezetője a láncolt lista, amely
mivel mi behelyezése a kezdődő, valóban lesz
egy mutatót a csomópont most létrehozott.
Nézzük elképzelni ezt, mert azt hiszem, hogy segíteni fog.
>> Tehát itt a lista, áll négy elem, egy csomópont, amely 15,
amely rámutat, hogy egy csomópont tartalmazó 9, amely
rámutat, hogy egy csomópont, amely 13, amely rámutat, hogy egy csomópont tartalmazó
10, amely a null mutatót a következő mutatót
úgy, hogy a vége a listán.
Ezért szeretnénk beszúrni új csomópont, melynek értéke 12
elején az e listát, mit csináljunk?
Nos, először is malloc helyet a csomópontot, majd rakjuk 12 odabent.
>> Így most már elérte a döntési pont, ugye?
Van egy pár mutatókat, hogy mi lehet
mozog, melyiket haladunk először?
Nem kellene, hogy 12 pont Az új vezetője a list--
vagy megbocsát, kéne tenni 12 pont a régi lista élére?
Vagy azt mondjuk, hogy a lista most kezdődik 12.
Van egy különbség ott, és akkor nézd
mi történik mind a második.
>> De ez vezet nagy téma a tálaló,
ami az, hogy az egyik legtrükkösebb dolog a láncolt listák
az, hogy gondoskodjon a mutatók a megfelelő sorrendben.
Ha mozgatja a dolgokat ki annak érdekében, akkor a végén véletlenül
orphaning a többi a lista.
És itt egy példa erre.
Szóval menjünk a gondolattal of-- Nos, éppen most létrehozott 12.
Tudjuk 12 lesz Az új lista élére,
és így miért nem csak mozgatni A lista mutatóját van.
>> OK, tehát ez jó.
Tehát most, ha nem 12 következő pont?
Úgy értem, vizuálisan láthatjuk hogy fog mutatni 15,
mint az emberek, hogy tényleg nyilvánvaló számunkra.
Hogyan működik a számítógép tudja?
Nem kell semmit rámutatva, hogy 15 már, ugye?
>> Elvesztettük minden képességét, hogy olvassa el 15.
Nem tudjuk megmondani, az új melletti nyílra egyenlők valamit, nincs ott semmi.
Sőt, most már árva a többi a lista
ezzel, most már véletlenül tört a láncot.
És mi persze nem akarom csinálni.
>> Szóval menjünk vissza, és próbáljuk meg újra.
Lehet, hogy a helyes dolog az, hogy hozzanak 12 következő mutatót
a régi lista élére első, akkor tudjuk mozgatni a lista vége.
És valóban, hogy a megfelelő sorrendben, hogy mi
kell, hogy kövesse, mikor vagyunk dolgozó egyszeresen láncolt lista.
Mi mindig szeretne csatlakozni a Új elem a listán,
mielőtt vesszük, hogy milyen fontos lépés a változó
ahol a fej a linkelt lista.
Ismét, ez egy ilyen alapvető dolog, nem akarjuk elveszíteni követni.
>> Ezért szeretnénk, hogy győződjön meg arról, hogy minden egymáshoz láncolva,
mielőtt tovább megyünk, hogy a mutató.
És így ez lenne a helyes sorrendben, amely kapcsolódni 12 a listához,
akkor azt mondják, hogy a lista kezdődik a 12.
Ha azt mondtuk a listán indul 12 és Ezután megpróbált csatlakozni a 12. a listán,
már láttuk, mi történik.
Elveszítjük a listában a hibát.
>> OK, így még egy dolog beszélni.
Mi van, ha azt akarjuk, hogy megszabaduljon Egy egész láncolt lista egyszerre?
Ismét mi mallocing mindez teret, és így
kell kiszabadítani, ha végeztünk.
Tehát most, hogy törli a teljes láncolt lista.
Nos, mit akarunk csinálni?
>> Ha elértük a null pointer, mi akarjuk állítani, különben csak törölni
a többi a listát, majd szabadíts meg.
Törlés a többi a lista, majd szabadítani a jelenlegi csomópont.
Mit szól hozzá, mint, milyen technikát kell beszélgettünk
a korábban, hogy hangzik, mint a?
Törlés mindenki más, akkor gyere vissza és törölje nekem.
>> Ez a rekurzió tettük a probléma egy kicsit kisebb,
azt mondjuk törölni mindenkinek más, akkor törölheti nekem.
És tovább az úton, hogy a csomópont azt fogja mondani, törölje mindenki más.
De végül mi lesz a pont, ahol a lista null,
és ez a mi alapeset.
>> Szóval vessünk egy pillantást erre, és hogy ez hogyan működik.
Tehát itt a lista, hogy ez ugyanaz felsorolni mi csak beszélünk,
és van az a lépéseket.
Van egy csomó szöveget itt, de Remélhetőleg a vizualizáció segít.
>> Tehát have-- és én is húzta a mi verem keret illusztráció
a mi video hívás halom, és remélhetőleg mindezt
együtt megmutatja, mi folyik itt.
Tehát itt van a pszeudokódja kódot.
Ha elérjük a null pointer, hagyja abba, különben
törölje a többi a lista, akkor szabad a jelenlegi csomópont.
Tehát most, list-- A mutató, hogy mi vagyunk
halad, hogy elpusztítsa pontot és 12.
12 nem egy null pointer, így vagyunk megy, hogy törölje a többi a lista.
>> Mi törlésével többiek részt?
Nos, ez azt jelenti, hogy egy hívja elpusztítani, mondván
hogy 15 a kezdete a többi listát akarunk pusztítani.
És így a hívás, hogy elpusztítsa 12 fajta tartásban.
Fagyott ott vár a hívja, hogy elpusztítsa 15, hogy befejezze a munkát.
>> Nos, 15 nem egy null pointer, és így fog mondani, rendben,
Nos, törölje a többit a lista.
A többi a lista kezd 9, és ezért most is csak
várj, amíg nem törli az összes, hogy cucc, akkor gyere vissza, és törölje nekem.
Nos 9 fog mondani, nos, Nem vagyok egy null pointer,
így törölje a többit a lista itt.
És így próbálja megsemmisíteni 13.
13 azt mondja, nem vagyok null pointer, Ugyanez, átadja a bak.
10 nem null pointer, 10 tartalmaz egy null mutató,
de 10 önmaga nem nullmutató most,
És ez így megy a bak is.
>> És most felsorolni pont ott, Tényleg emlékeztet az some--
ha lenne több hely van a kép, ez a pont, hogy néhány véletlenszerű tér
hogy nem tudjuk, mi az.
Ez a nullmutató bár a lista van szó most meg ez értékei null.
Ez mutatva legbelül, hogy piros doboz.
Elérkeztünk egy null pointer, így meg tudjuk állítani, és már készen is vagyunk.
>> És így, hogy a lila keret now-- a tetejére stack-- ez az aktív keret,
de ez kész.
Ha elértük a null pointer, hagyja abba.
Nem csinálunk semmit, Nem szabad egy null pointer,
mi nem malloc semmilyen helyet, és így készen vagyunk.
Annak érdekében, hogy a funkció keret megsemmisül, és mi
resume-- kezünkbe veszünk, ahol hagytuk le a következő legmagasabb, ami
ez sötétkék kerettel itt.
Tehát vedd fel ott, ahol abbahagytuk.
Mi törölve a többi a listán már, így most mi vagyunk
fog felszabadítani a jelenlegi csomópont.
Tehát most is szabad ezt a csomópontot, és most elértük a funkció végét.
És így a függvény keret megsemmisül, és mi vedd fel a fény kék.
>> Tehát says-- Már done-- törlése a többi a listán, így
szabad a jelenlegi csomópont.
És most a sárga keret vissza a köteg tetején.
És így látod, mi most tönkretéve a listán jobbról balra.
>> Mi történt volna, mégis, Ha mi tette a dolgokat, hogy rossz irányba?
Csakúgy, mint amikor megpróbáltuk hogy egy elemet.
Ha elrontotta a lánc, ha mi nem csatlakozhat a mutatók
a helyes sorrendben, ha Csak kiszabadította az első elemet,
ha csak megszabadult a A lista élére, most
nincs lehetősége arra utalnak a többi a lista.
És így lett volna árva mindent,
mi lett volna, mi van nevezett memóriavesztés.
Ha felidézzük a mi video A memória dinamikus,
ez nem túl jó dolog.
>> Szóval mint mondtam, több művelet
hogy meg kell használni a munka A láncolt lista hatékonyan.
És lehet, hogy észre kihagytam egyet, törlése egyetlen eleme egy csatlakoztatott
listán.
Az ok, hogy ezt tettem ez valójában egyfajta
trükkös gondolkodni, hogyan kell törölni Egyetlen elem egyszeresen
láncolt lista.
Meg kell tudni, hogy átugorják valamit a listán, amely
azt jelenti, hogy egy point-- vagyunk törölni akarja ezt node--
de ahhoz, hogy ez így ne vesszenek el adatok,
szükségünk van, hogy csatlakoztassa a node ide, itt.
>> Szóval valószínűleg azért, hogy rossz vizuális szempontból.
Úgyhogy elején a listát, mi átrágja magát,
akarjuk törölni a csomópontot.
Ha csak törölni, mi már megtört a lánc.
Ez a csomópont itt utal minden mást,
ez tartalmazza a láncot Innen ki.
>> Szóval mit kell tennünk ténylegesen után megkapjuk a pontig,
van szükségünk, hogy lépjen vissza egyet, és csatlakoztassa a csomópont át a csomóponton,
így tudjuk majd törölje az egyik a közepén.
De egyedül láncolt listák nem adjon nekünk egy út visszafelé.
Tehát meg kell tartani vagy két pointert, és mozgassa őket
fajta off lépésben, egymás mögött Más, ahogy haladunk, vagy kap egy pontot
majd küldeni egy másik mutatót keresztül.
És mint látható, ez lehet, hogy egy kicsit rendetlen.
Szerencsére van Egy másik módja annak, hogy megoldja ezt,
amikor arról beszélünk, kétszeresen láncolt listák.
>> Én Doug Lloyd, ez CS50.