[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.