[Powered by Google Translate] A programozás, gyakran kell, hogy képviselje Értéklistákon, mint például a nevek a diákok egy része vagy az eredmények a legújabb kvíz. 

A C nyelven bejelentett tömböket lehet használni tárolására listákat. Ez könnyű felsorolni elemeit lista tömb tárolja, és ha kell elérni vagy módosítsa az i-edik lista elem néhány önkényes index I, hogy lehet tenni állandó időben, de tömbök vannak hátrányai is. 

Amikor állapítsa meg őket, mi kell mondani elöl mekkora vannak, azaz, hogy hány elemet tudnak tárolni és mekkorák ezek az elemek, amelyek meghatározott típusát. Például, int arr (10) tud tárolni 10 darab , amelyek a mérete int. 

Nem tudjuk megváltoztatni egy tömb méretét után nyilatkozatot. Van, hogy egy új tömb, ha meg akarjuk tárolni több elemet. Az ok, ez a korlátozás létezik, hogy a mi program tárolja az egész tömböt mint a szomszédos darab memória. Mondja ez a puffer, ahol tárolják a tömbben. Lehet, hogy más változók közvetlen közelében található a tömbben a memóriában, így nem csak, hogy a tömb nagyobb. 

Néha szeretnénk kereskedni a tömb gyors adathozzáférés sebességét egy kicsit rugalmasabb. Adja meg a láncolt lista, a másik alapvető adatstruktúra lehet, hogy nem lesz olyan ismerős. Magas szinten, A láncolt lista tárolja az adatokat egy sorozat csomópontok , amelyek kapcsolódnak egymáshoz linkek, ezért neve: 'láncolt lista. " Mint látni fogjuk, ez a különbség a tervezési vezet különböző előnyei és hátrányai mint egy tömb. 

Íme néhány C kód egy nagyon egyszerű láncolt lista egészek. Láthatjuk, hogy az általunk képviselt minden csomópont a listán, mint a struct amely 2 dolog, egy egész tárolására úgynevezett "val" és egy linket a következő csomópont a listán amit képviselnek, mint a mutató úgynevezett "next". Így tudjuk követni a teljes lista mindössze egy mutatót az 1. csomópont, és akkor kövesse a következő mutatók a 2. csomópont, a 3. csomópont, a 4. csomópont, és így tovább, amíg eljutunk az a lista végére. 

Lehet, hogy képes látni 1 előnye ennek át a statikus tömb szerkezet - a láncolt lista, nem kell egy nagy darab memória összesen. Az 1. csomópont a lista élhetnénk ezen a helyen a memóriában, és a 2. csomópont lehet egészen át ide. Mi lehet eljutni az összes csomópont nem számít, hol a memóriában vannak, mert kezdődik az 1. csomópont, minden csomópont next mutató azt mondja, hogy pontosan hová menjen legközelebb. 

Továbbá, nem kell, hogy mondjam elöl mekkora a láncolt lista lesz, mint mi statikus tömbök, hiszen tudjuk tartani hozzá csomópontok listáját amíg van hely valahol a memóriában, az új csomópont. Ezért a linkelt listák könnyen átméretezni dinamikusan. Mondja el, később a program kell, hogy adjunk több csomópont a mi listáját. Ha új csomópontot A lista on the fly, minden, amit meg kell tennie, hogy a memóriát az adott csomópont, puff az adatok értékét, majd helyezze, hogy hová szeretnénk beállításával a megfelelő mutatókat. 

Például, ha azt akartuk helyeznie egy csomópont között a 2. és 3. csomópontok a lista,  akkor nem kell mozgatni a 2. vagy 3. csomópontok egyáltalán. Mondja el, mi behelyezése a piros csomópont. Minden mi volna tennie, hogy megadja az új csomópont next mutató pont a 3. csomópont majd újból felhasználni a 2. csomópont next mutató arra utalnak, hogy az új csomópont. Szóval, mi lehet átméretezni a listákat on the fly hiszen a számítógép nem hivatkozhat indexálás, hanem össze a mutató tárolja. 

Azonban az a hátránya, láncolt listák az, hogy ellentétben a statikus tömb, a számítógép nem csak ugrik a közepén a listán. Mivel a számítógép, hogy látogassa meg minden csomópont a láncolt lista hogy a következő egy, ez fog hosszabb időt vesz igénybe, hogy megtalálja egy adott csomóponton , mint lenne egy tömbben. Ahhoz, hogy keresztezik a teljes lista időt vesz igénybe, arányos a hossza a jegyzék, vagy O (n) aszimptotikus jelöléssel. Átlagban, elérve minden csomópont is időt vesz igénybe, arányos n. 

Nos, hadd valójában írni egy kódot amely együttműködik a kapcsolódó listákat. Tegyük fel, hogy szeretnénk egy láncolt lista egészek. Tudunk jelentenek csomópont listánkon újra mint egy struct, 2 területen, Egy egész érték úgynevezett "ertek" és a következő mutató a következő csomópont a listán. Nos, úgy tűnik, elég egyszerű. 

Tegyük fel, hogy szeretnénk írni egy függvényt amely bejárja a listát, és kiírja a tárolt érték az utolsó csomópont a lista. Nos, ez azt jelenti, hogy kell majd áthalad az összes csomópont a lista hogy megtalálja az utolsó, de mivel nem vagyunk hozzá vagy törlése semmit, nem akar változtatni a belső szerkezete a következő mutatók a listában. 

Szóval, szükségünk lesz egy mutató kifejezetten bejárás amely hívjuk "bejáró". Ez feltérképezni az összes elemét a lista követve a lánc a következő mutatók. Minden általunk tárolt egy mutató az 1. csomópont, vagy "feje" a listán. Head rámutat az 1. csomóponton. Ez a típusú pointer-to-node. 

Ahhoz, hogy a tényleges 1. csomópont szerepel a listán, meg kell dereference ez a mutató, de mielőtt tudjuk feloldani, mi kell, hogy ellenőrizze ha a mutató null először. Ha ez nulla, a lista üres, és meg kell nyomtassa ki egy üzenetet, hogy mivel a lista üres, nincs utolsó csomópont. De mondjuk a lista nem üres. Ha ez nem, akkor meg kell feltérképezni a teljes lista addig, amíg eljutunk az utolsó csomópont a lista és hogyan lehet mondani, ha keresünk az utolsó csomópont a listán? 

Nos, ha a csomópont melletti mutató null, tudjuk, hogy mi vagyunk a végén mivel az utolsó következő mutató nem lenne következő csomópontot a listában mutasson. Ez jó gyakorlat, hogy mindig az utolsó csomópont melletti mutató inicializálni null hogy egy szabványos tulajdonság, amely figyelmeztet bennünket, ha elértük a lista végét. 

Tehát, ha a bejáró → következő null, ne feledjük, hogy a nyíl szintaxis egy parancsikont dereferencing a mutató egy struct, akkor hozzáférés a következő mező megegyezik a kínos: (* Bejáró). Következő. Amint megtaláltuk az utolsó csomópont, szeretnénk nyomtatni bejáró → val, az értéket a jelenlegi csomópont amiről tudjuk, hogy az utolsó. Ellenkező esetben, ha nem vagyunk még az utolsó csomópont a listán, meg kell mozgatni, hogy a következő csomópont a listán és ellenőrizze, hogy ez az utolsó. Ehhez már csak meg robotunk pointer pont a jelenlegi csomópont következő értéket, vagyis, a következő csomópont a listában. Ez úgy történik, beállításával bejáró = bejáró → következő. Akkor megismételjük ezt a folyamatot, és egy hurok például, amíg meg nem találjuk az utolsó csomópontot. Így például, ha a bejáró mutatott a fejét, elindultunk bejáró mutasson bejáró → következő, amely ugyanaz, mint a következő mező az 1. csomópont. Szóval, most a bejáró mutat a 2. csomópont, és újra, hogy ismételje meg a hurok, amíg meg nem találtuk az utolsó csomópont, azaz amennyiben a csomópont melletti mutató mutat null. És ott van ez, találtunk az utolsó csomópont a listáról, és nyomtatni annak értékét, mi csak használni bejáró → val. 

Mozgás nem olyan rossz, de mi van beszúrásával? Mondjuk szeretnénk beszúrni egy egész a 4. pozíció egy egész listát. Vagyis a jelenlegi 3. és 4. csomópontok. Ismét meg kell mozogni a lista csak a kap a 3. elem, az egyik mi behelyezése után. Tehát, hozzon létre egy bejáró mutató ismét áthalad a listán, ellenőrizze, hogy a fejünk mutató nulla, és ha ez nem, mutasson robotunk mutató élén csomópontot. Szóval, mi vagyunk az 1. elem. Meg kell, hogy menjen előre 2 további elem, mielőtt mi is be, így tudjuk használni a for ciklus int i = 1; i <3, i + + és minden iteráció a hurok, előre robotunk előre mutató 1-csomópont ellenőrzi, ha a jelenlegi csomópont melletti mező null, és ha ez nem, helyezze robotunk mutatót a következő csomópont azáltal, hogy egyenlő a jelenlegi csomópont next mutató. Szóval, hiszen a for ciklus azt mondja erre kétszer, elértük a 3. csomópont, és egyszer robotunk mutató elérte a csomópont után amelyhez be szeretné szúrni az új egész, hogyan tudjuk valójában nem az behelyezése? 

Nos, a mi új egész szám kell illeszteni a lista részeként a saját node struct, mivel ez valóban sorozata csomópontok. Szóval, most egy új mutatót csomópont úgynevezett "new_node" és állítsa pont a memóriában, hogy most osztják A halom a csomópont is, és mennyi memória van szükségünk, hogy fordítsanak? Nos, akkora, mint egy csomópont, és azt akarjuk állítani, hogy val mezőt az egész, hogy szeretnénk beszúrni. Mondjuk, 6. Most, a csomópont tartalmazza a egész szám. Ez is jó gyakorlat inicializálni az új csomópont következő mezőre mutasson null, de most mi lesz? 

Meg kell változtatni a belső szerkezete a lista és a következő mutatók listában szereplő meglévő 3. és 4. csomópontok. Mivel a következő mutatók határozzák meg sorrendben a lista és mivel mi beilleszteni az új csomópont egyenesen a közepén a lista ez lehet egy kicsit trükkös. Ennek az az oka, emlékszem, a számítógépes tudja a helyét a csomópontok a lista mert a következő mutatók tárolt előző csomópontok. Tehát, ha valaha vereség pálya bármely ezeken a helyeken, mondjuk megváltoztatásával egyik következő mutatók a listán, Például, mondjuk mi változott a 3. csomópont következő mezőre arra utalnak, hogy egyes node ide. Mi lenne a szerencse, mert nem Van valami ötlete, hogy hol találja a többi lista és ez nyilvánvalóan nagyon rossz. Szóval, van, hogy nagyon óvatos a megrendeléshez melyben manipulálják a következő mutatók behelyezés során. 

Tehát, egyszerűsítése, mondjuk, hogy az első 4 csomópont nevezzük A, B, C, és D, a nyilakkal képviselő a lánc mutatókat hogy csatlakoztassa a csomópontokat. Szóval, kell helyezni az új csomópont között csomópontok C és D Ez a kritikus csinálni a megfelelő sorrendben, és megmutatom, miért. 

Nézzük meg a rossz irányba kell csinálni az első. Hé, tudjuk, hogy az új csomópont jön rögtön C, úgyhogy meghatározott C soron következő mutató mutasson new_node. Rendben, úgy tűnik, rendben van, csak be kell fejeznem most a hogy az új csomópont mellett pointer mutasson a D, De várjunk csak, hogyan lehet csinálni? Az egyetlen dolog, ami elmondja, hol D volt, volt a következő mutató korábban tárolt C, de mi csak átírta, hogy pointer mutatni, hogy az új csomópont, így már nincs semmi nyom, ahol a D a memóriában, és mi elvesztettük a többi listán. Nem jó egyáltalán. 

Szóval, hogyan csináljuk ezt a jogot? Először is, pont az új csomópont melletti mutató a D. Most mind az új csomópont és a C soron következő mutatók mutatnak, hogy ugyanazon a csomóponton, D, de ez rendben van. Most C. pontja a következő mutató az új csomópontot. Szóval, csináltam ezt adatvesztés nélkül. A kód, C jelenlegi csomópont hogy a bejárás mutató bejáró mutat az, és D képviseli a csomópont által mutatott a jelenlegi csomópont melletti területen, vagy lánctalpas → következő. Tehát először az új csomópont next mutató mutasson bejáró → következő, ugyanúgy mondtuk new_node soron következő pointer kell mutatnak D az ábra mutatja. Akkor tudjuk meg az aktuális csomópont next mutató az új csomópont, mint ahogy meg kellett várni, hogy pont C new_node a rajzban. Most minden van rendben, és mi nem vesztett követni minden olyan adatot, és tudtuk, hogy csak kibír az új csomópont közepén a lista anélkül, újjáépítése az egész dolog, vagy akár változó olyan elemeket hogy hogyan kellett volna egy fix hosszúságú tömbben. 

Tehát linkelt listák az alap, de fontos, dinamikus adatszerkezet amelyek előnyei és hátrányai összehasonlítva tömbök és más adatszerkezetek, és ahogy az gyakran előfordul a számítógép-tudomány, ezért fontos, hogy tudja, mikor kell használni az egyes eszközöket, így akkor vedd a megfelelő eszközt a megfelelő munkát. 

További gyakorlat, próbálja írás funkciók törölni csomópontok egy láncolt lista - emlékszem, hogy legyen óvatos a sorrend, amelyben átrendezéséhez a következő mutatókat annak érdekében, hogy ne veszítse el a darab a lista - vagy funkció számolni a csomópontok egy láncolt lista, vagy szórakoztató egy, fordított sorrendben az összes csomópont egy láncolt lista. 

A nevem Jackson Steinkamp, ​​ez CS50.