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