[Powered by Google Translate] V programovaní, často potrebujeme reprezentovať zoznamy hodnôt,
napríklad názvy študentov v sekcii
alebo ich skóre na poslednej kvízu.
>> V jazyku C, vyhlásila polia môžu byť použité
uložiť zoznamy.
Je to jednoduché vymenovať prvky zoznamu
uložené v poli, a ak budete potrebovať pre prístup k
alebo upraviť Ith prvok zoznamu
pre nejaký svojvoľný index I,
ktorý môže byť vykonaný v konštantnom čase,
ale pole majú nevýhody.
>> Keď sme ich deklarovať, že sme povinní povedať
up front, aké veľké sú,
že je, koľko prvkov, ktoré môžu uložiť
a ako veľké tieto prvky sú, ktorá je určená ich typu.
Napríklad, int ARR (10)
možno uložiť 10 položiek
že sú o veľkosti typu int.
>> Nemôžeme zmeniť celý rad jeho veľkosť po uverejnení.
Musíme vytvoriť nové pole, ak chceme uložiť viac prvkov.
Dôvodom toto obmedzenie existuje, je, že naša
Program ukladá celý rad
ako súvislý kus pamäte.
Povedzme to je vyrovnávacia pamäť, kde sa uloží v našom poli.
Tam by mohlo byť iné premenné
Nachádza sa hneď vedľa poľa
v pamäti, takže nemôžeme
len aby polia väčšie.
>> Niekedy sme chceli obchodovať Array je rýchly prístup k dátam rýchlosťou
o trochu viac flexibility.
Zadajte spájať zoznam, ďalšie základné údaje štruktúra
nemusíte byť oboznámení s
Na vysokej úrovni,
spájať zoznam ukladá dáta v poradí uzlov
, Ktoré sú vzájomne prepojené s odkazmi,
Odtiaľ názov "spájať zoznam."
Ako uvidíme, tento rozdiel v dizajne
vedie k rôznym výhodám a nevýhodám
ako pole.
>> Tu je nejaký kód C pre veľmi jednoduché prepojeného zoznamu celých čísel.
Môžete vidieť, že sme zástupcovia každý uzol
v zozname ako struct, ktorý obsahuje 2 veci,
číslo uložiť tzv "val"
a odkaz na ďalšie uzol v zozname
ktoré predstavujú ako ukazovateľ s názvom "Ďalší."
Týmto spôsobom, možno sledovať celý zoznam
iba s jedným ukazovateľ na uzol 1st,
a potom môžeme sledovať ďalšie ukazovatele
na druhej uzla,
na 3. uzla,
na 4. uzla,
a tak ďalej, až kým sa na koniec zoznamu.
>> Tie by mohli byť schopní vidieť 1 výhodu to má
cez statické pole štruktúry - s prepojeného zoznamu,
nepotrebujeme veľký kus pamäte dohromady.
1. uzol zoznamu by mohol žiť na tomto mieste v pamäti,
a 2. uzol by mohol byť po celú cestu sem.
Môžeme dostať do všetkých uzlov bez ohľadu na to, kde v pamäti sú,
pretože začína v uzle 1st, každý uzol budúci ukazovateľ
nám hovorí presne, kam ísť ďalej.
>> Navyše, nemáme hovoriť dopredu
aký veľký spájať zoznam bude rovnakým spôsobom ako my so statickými poli,
pretože môžeme držať pridanie uzlov do zoznamu
ako dlho ako tam je priestor niekde v pamäti pre nové uzly.
Preto, prepojené zoznamy ľahko zmeniť veľkosť dynamicky.
Povedz, neskôr v programe musíme pridať ďalšie uzly
do nášho zoznamu.
Ak chcete vložiť nový uzol do nášho zoznamu za behu,
všetko, čo musíme urobiť, je alokovať pamäť pre tento uzol,
PLOP v dátovej hodnoty,
a potom na miesto, kde chceme úpravou vhodné ukazovatele.
>> Napríklad, ak chceme umiestniť uzol medzi
2. a 3. uzly zoznamu,
by sme nemali presunúť 2. alebo 3. uzly vôbec.
Povedzme, že sme vložením túto červenú uzol.
Všetko budeme musieť urobiť, je nastaviť nový uzol je ďalší ukazovateľ
poukázať na 3. uzla
a potom prepojiť druhej uzla je ďalší ukazovateľ
upozorniť na náš nový uzol.
Takže, môžeme meniť veľkosť svojej zoznamy za behu
pretože náš počítač nespolieha na indexovanie,
ale skôr na prepojenie s ukazovateľmi ich uloženia.
>> Avšak, nevýhodou spojené zoznamy
je skutočnosť, že na rozdiel od statické pole,
Počítač nemôže len tak skočiť do stredu zoznamu.
Vzhľadom k tomu, že počítač má navštíviť každý uzol v prepojenom zozname
sa dostať na ďalšie,
to bude trvať dlhšie nájsť určitý uzol
, Ako by sa v poli.
Prejsť celý zoznam trvá dlho úmerná
k dĺžke zoznamu,
alebo O (n) v asymptotickej notáciu.
V priemere, dosiahnutie ľubovoľného uzla
berie tiež časovo proporcionálne k n.
>> Teraz, poďme vlastne napísať nejaký kód
, Ktorý pracuje s lineárnymi zoznamy.
Povedzme, že chceme prepojeného zoznamu celých čísel.
Môžeme reprezentovať uzol v našom zozname znova
ako struct s 2 polí,
celočíselná hodnota tzv "val"
a ďalšie ukazovateľ na ďalší uzol zoznamu.
No, vyzerá celkom jednoduché.
>> Povedzme, že chcete napísať funkciu
ktorý prekročí zoznamu a vytlačí
Hodnota uložená v poslednej uzol zoznamu.
No, to znamená, že budeme musieť prejsť všetky uzly v zozname
nájsť ten posledný, ale pretože nie sme pridanie
alebo čokoľvek zmazali, nechceme meniť
vnútorná štruktúra ďalších ukazovateľov v zozname.
>> Takže, budeme potrebovať ukazovateľ špeciálne pre priechod
ktoré budeme nazývať "prolézací modul."
To bude prechádzať cez všetky prvky zoznamu
podľa pokynov reťazca ďalších ukazovateľov.
Všetko máme uložené, je ukazovateľ na uzol 1st,
alebo "hlava" zo zoznamu.
Head poukazuje na 1. uzla.
Je to typu pointer-to-uzla.
>> Ak chcete získať aktuálne prvý uzol v zozname,
musíme dereferencia tento ukazovateľ,
ale pred tým, než môže dereferencia to, musíme skontrolovať
v prípade, že ukazovateľ je null prvý.
Ak je to null, zoznam je prázdny,
a my by sme mali vytlačiť správu, že, pretože zoznam je prázdny,
nie je posledný uzol.
Ale povedzme, že zoznam nie je prázdny.
Ak tomu tak nie je, potom by sme mali prechádzať celý zoznam
kým sa na posledný uzol zoznamu,
a ako môžeme povedať, či sa pozeráme na posledné uzol v zozname?
>> No, ak uzol je ďalší ukazovateľ je null,
my vieme, že sme na konci
od posledného ďalšie ukazovateľ by nemal ďalšie uzol v zozname, aby ukazoval na.
Je dobrým zvykom vždy posledný uzol je ďalší ukazovateľ inicializovaný null
mať štandardizovanú vlastnosť, ktorá upozorní nás, keď sme došli na koniec zoznamu.
>> Takže, ak crawler → ďalšie je null,
nezabudnite, že šípka syntax je skratka pre dereferencing
ukazovateľ na struct, potom prístup
jej ďalšie pole zodpovedá nepríjemné:
(* Crawler). Ďalšie.
Akonáhle sme našli posledný uzol,
chceme tlačiť prolézacího → val,
hodnota v aktuálnom uzle
ktoré poznáme, je posledný.
V opačnom prípade, keď sme ešte na poslednú uzla v zozname,
musíme presunúť na ďalší uzol v zozname
a skontrolujte, či je to ten posledný.
Ak to chcete, len sme nastavili pásové ukazovateľ
bodu za aktuálnym uzlom je ďalšie hodnoty,
to znamená, že ďalší uzol v zozname.
To sa vykonáva nastavením
crawler = crawler → ďalšie.
Potom sa tento proces opakovať, sa slučkou napríklad,
kým nenájdeme posledný uzol.
Tak napríklad, ak pásový ukazoval na hlavu,
sme sa vydali prolézací modul, aby ukazoval na pásový → Ďalšie,
ktorý je rovnaký ako ďalšie oblasti prvého uzla.
Takže, teraz náš prehľadávač ukazuje na 2. uzla,
a opäť, opakujeme to sa slučkou,
až sme zistili, posledný uzol, ktorý je,
kde uzla ďalšie ukazovateľ ukazuje na null.
A tu to máme,
sme našli posledný uzol v zozname, a vytlačiť svoju hodnotu,
stačí použiť pásový → val.
>> Pojazdu nie je tak zlé, ale čo o vkladanie?
Povedzme, že chceme vložiť celé číslo do 4. mieste
v celé číslo zozname.
To je medzi súčasnými 3. a 4. uzlov.
Opäť musíme prechádzať zoznam len
dostať do 3. prvok, jeden sme vkladanie po.
Takže, sme vytvoriť prolézacího ukazovateľ znovu prechádzať zoznam,
skontrolujte, či naša hlava ukazovateľ je null,
a ak tomu tak nie je, prejdite náš prehľadávač ukazovateľ na hlavnom uzle.
Takže, sme na 1. prvok.
Musíme ísť vpred 2 viac prvkov, ako môžeme vložiť,
takže môžeme použiť pre sláčiky
int i = 1; i <3; i + +
a v každom opakovaní slučky,
Rozšírenie našich pásový ukazovateľ vpred o 1 uzol
skontrolovať, či je aktuálny uzol je ďalšie pole null,
a ak je to nie je, presunúť naše pásový ukazovateľ na ďalší uzol
nastavením je rovný aktuálnemu uzla budúceho ukazovateľ.
Takže, pretože naše cyklu for hovorí k tomu, že
dvakrát,
sme dosiahli 3. uzol,
a potom, čo náš prehľadávač ukazovateľ dosiahol uzol po
ktoré chceme vložiť náš nový integer,
ako sme vlastne robiť vkladanie?
>> No, náš nový integer musí byť vložený do zoznamu
ako súčasť vlastného uzla struct,
, Pretože to je v skutočnosti sekvencie uzlov.
Takže, poďme sa nový ukazovateľ na uzol
tzv "new_node,"
a nastavte ju upozorniť na pamäti, že sme teraz prideliť
na halde pre uzol sám,
a koľko pamäte potrebujeme prideliť?
No, o veľkosti uzla,
a chceme nastaviť svoj val poľa na celé číslo, ktoré chceme vložiť.
Povedzme, 6.
Teraz, uzol obsahuje náš celočíselnú hodnotu.
Je tiež dobrým zvykom inicializovať nový uzol je ďalšie pole
bodu na hodnotu null,
ale čo teraz?
>> Máme zmeniť vnútornú štruktúru zoznamu
a ďalšie ukazovatele obsiahnuté v zozname je existujúci
3. a 4. uzly.
Vzhľadom k tomu, že ďalšie ukazovatele určujú poradie v zozname,
a od tej doby sme vložením náš nový uzol
priamo do stredu zoznamu,
to môže byť trochu zložitejšie.
To je preto, pamätajte, náš počítač
pozná len umiestnenie uzlov v zozname
pretože z ďalších ukazovateľov uložených v predchádzajúcich uzlov.
Takže, ak sa niekedy stratil niektoré z týchto lokalít,
povedať zmenou jedného z nasledujúcich ukazovateľov v našom zozname,
Napríklad, že sme zmenili
od 3. uzla vedľa poľa
poukázať na niektoré uzla sem.
Boli by sme smolu, pretože by sme
tušenie, kde nájsť zvyšok zoznamu,
a to je zrejme naozaj zlé.
Takže, musíme byť naozaj pozor na ich poradie
, V ktorom sme sa manipulovať naše ďalšie ukazovatele počas zavádzania.
>> Takže, zjednodušiť to, povedzme, že
naše prvé 4 uzly
sa nazýva A, B, C a D, s šípkami predstavujúce reťaz ukazovateľov
ktoré spájajú uzly.
Takže, je nutné vložiť náš nový uzol
medzi uzlami C a D.
Je dôležité, aby to v správnom poradí, a ja vám ukážem, prečo.
>> Poďme sa pozrieť na zlý spôsob, ako to urobiť ako prvé.
Hele, my vieme, že nový uzol má prísť hneď po C,
takže sa poďme nastaviť C je ďalší ukazovateľ
poukázať na new_node.
Dobre, zdá sa v poriadku, len musíme dokončiť už teraz
Vďaka nového uzla je ďalší ukazovateľ bod D,
Ale počkajte, ako môžeme urobiť, že?
Jediná vec, ktorá by nám mohol povedať, kde D je,
bola ďalšia ukazovateľ skôr uložené v C,
ale my jednoducho prepísal tento ukazovateľ
prejdite na nový uzol,
takže už nemáme poňatia, kde D je v pamäti,
a my sme stratili zvyšok zoznamu.
Vôbec dobré.
>> Tak, ako to urobíme toto právo?
Po prvé, bodu nového uzla je ďalší ukazovateľ na D.
Teraz, ako nový uzol je a C je ďalšie ukazovatele
smerujú na rovnaký uzol, D,
ale to je v poriadku.
Teraz môžeme bod C je ďalší ukazovateľ na nový uzol.
Takže sme urobili to bez straty dát.
V kóde, C je aktuálny uzol
že traversal ukazovateľ prolézací modul ukazuje na,
a D je reprezentovaný uzlom na ktorý ukazuje aktuálnu uzla nasledujúceho poľa,
alebo pásovom podvozku → ďalšie.
Takže, najprv nastavte nový uzol je ďalší ukazovateľ
poukázať na pásový → Ďalšie,
rovnakým spôsobom sme si povedali, new_node budúci ukazovateľ by mal
poukazujú na D na obrázku.
Potom môžeme nastaviť aktuálny uzol je ďalší ukazovateľ
do nášho nového uzla,
rovnako ako sme museli čakať, až bodu C k new_node vo výkrese.
Teraz je všetko v poriadku, a my sme nestratili
prehľad o všetkých údajov, a my sme boli schopní len
držať náš nový uzol v stredu zoznamu
bez prestavať celú vec, alebo dokonca posunutie všetky prvky
spôsob, akým by sa museli s pevnou dĺžkou poľa.
>> Takže, prepojené zoznamy sú základné, ale dôležité, dynamická dátová štruktúra
ktoré majú výhody aj nevýhody
v porovnaní s poli a iných dátových štruktúr,
a ako je to často v informatike,
je dôležité vedieť, kedy použiť každý nástroj,
takže si môžete vybrať ten správny nástroj na správne miesto.
>> Pre viac praxe, skúste napísať funkcie
odstránenie uzlov z prepojeného zoznamu -
nezabudnite dávať pozor na poradie, v ktorom ste zmeny usporiadania
vaše ďalšie ukazovatele, aby zabezpečili, že nestratíte kus svojho zoznamu -
alebo funkciu počítať uzly v prepojenom zozname,
alebo legrace jeden, obrátiť poradie všetkých uzlov v prepojenom zozname.
>> Volám sa Jackson Steinkamp, ​​je to CS50.