[Powered by Google Translate] V programování, často potřebujeme reprezentovat seznamy hodnot,
například názvy studentů v sekci
nebo jejich skóre na poslední kvízu.
>> V jazyce C, prohlásila pole mohou být použity
uložit seznamy.
Je to snadné vyjmenovat prvky seznamu
uloženy v poli, a pokud budete potřebovat pro přístup k
nebo upravit Ith prvek seznamu
pro nějaký svévolný index I,
který může být proveden v konstantním čase,
ale pole mají nevýhody.
>> Když jsme je deklarovat, že jsme povinni říci
up front, jak velké jsou,
že je, kolik prvků, které mohou uložit
a jak velké tyto prvky jsou, která je určena jejich typu.
Například, int arr (10)
lze uložit 10 položek
že jsou o velikosti typu int.
>> Nemůžeme změnit celou řadu jeho velikost po vyhlášení.
Musíme vytvořit nové pole, pokud chceme uložit více prvků.
Důvodem toto omezení existuje, je, že naše
Program ukládá celou řadu
jako souvislý kus paměti.
Řekněme to je vyrovnávací paměť, kde se uloží v našem poli.
Tam by mohlo být jiné proměnné
Nachází se hned vedle pole
v paměti, takže nemůžeme
jen aby pole větší.
>> Někdy jsme chtěli obchodovat Array je rychlý přístup k datům rychlostí
o trochu více flexibility.
Zadejte spojový seznam, další základní údaje struktura
nemusíte být obeznámeni s.
Na vysoké úrovni,
spojový seznam ukládá data v pořadí uzlů
, které jsou vzájemně propojeny s odkazy,
Odtud název "spojový seznam."
Jak uvidíme, tento rozdíl v designu
vede k různým výhodám a nevýhodám
než pole.
>> Zde je nějaký kód C pro velmi jednoduché propojeného seznamu celých čísel.
Můžete vidět, že jsme zástupci každý uzel
v seznamu jako struct, který obsahuje 2 věci,
číslo uložit tzv. "val"
a odkaz na další uzel v seznamu
které představují jako ukazatel s názvem "Další."
Tímto způsobem, lze sledovat celý seznam
pouze s jedním ukazatel na uzel 1st,
a pak můžeme sledovat další ukazatele
na druhé uzlu,
na 3. uzlu,
na 4. uzlu,
a tak dále, dokud se na konec seznamu.
>> Ty by mohly být schopni vidět 1 výhodu to má
přes statické pole struktury - s propojeného seznamu,
nepotřebujeme velký kus paměti dohromady.
1. uzel seznamu by mohl žít na tomto místě v paměti,
a 2. uzel by mohl být po celou cestu sem.
Můžeme dostat do všech uzlů bez ohledu na to, kde v paměti jsou,
protože začíná v uzlu 1st, každý uzel příští ukazatel
nám říká přesně, kam jít dál.
>> Navíc, nemáme říkat dopředu
jak velký spojový seznam bude stejným způsobem jako my se statickými poli,
protože můžeme držet přidání uzlů do seznamu
jak dlouho jak tam je prostor někde v paměti pro nové uzly.
Proto, propojené seznamy snadno změnit velikost dynamicky.
Řekni, později v programu musíme přidat další uzly
do našeho seznamu.
Chcete-li vložit nový uzel do našeho seznamu za běhu,
všechno, co musíme udělat, je alokovat paměť pro tento uzel,
plop v datové hodnoty,
a pak na místo, kde chceme úpravou vhodné ukazatele.
>> Například, pokud chceme umístit uzel mezi
2. a 3. uzly seznamu,
bychom neměli přesunout 2. nebo 3. uzly vůbec.
Řekněme, že jsme vložením tuto červenou uzel.
Vše budeme muset udělat, je nastavit nový uzel je další ukazatel
poukázat na 3. uzlu
a potom přepojit druhé uzlu je další ukazatel
upozornit na náš nový uzel.
Takže, můžeme měnit velikost své seznamy za běhu
protože náš počítač nespoléhá na indexování,
ale spíše na propojení s ukazateli jejich uložení.
>> Nicméně, nevýhodou spojené seznamy
je skutečnost, že na rozdíl od statické pole,
Počítač nemůže jen tak skočit do středu seznamu.
Vzhledem k tomu, že počítač má navštívit každý uzel v propojeném seznamu
se dostat na další,
to bude trvat déle najít určitý uzel
, než by se v poli.
Přejít celý seznam trvá dlouho úměrná
k délce seznamu,
nebo O (n) v asymptotické notaci.
V průměru, dosažení libovolného uzlu
bere rovněž časově proporcionální k n..
>> Nyní, pojďme vlastně napsat nějaký kód
, který pracuje s lineárními seznamy.
Řekněme, že chceme propojeného seznamu celých čísel.
Můžeme reprezentovat uzel v našem seznamu znovu
jako struct s 2 polí,
celočíselná hodnota tzv. "val"
a další ukazatel na další uzel seznamu.
No, vypadá docela jednoduché.
>> Řekněme, že chcete napsat funkci
který překročí seznamu a vytiskne
Hodnota uložená v posledním uzlu seznamu.
No, to znamená, že budeme muset přejít všechny uzly v seznamu
najít ten poslední, ale protože nejsme přidání
nebo cokoli smazali, nechceme měnit
vnitřní struktura dalších ukazatelů v seznamu.
>> Takže, budeme potřebovat ukazatel speciálně pro průchod
které budeme nazývat "prolézací modul."
To bude procházet přes všechny prvky seznamu
podle pokynů řetězce dalších ukazatelů.
Vše máme uloženy, je ukazatel na uzel 1st,
nebo "hlava" ze seznamu.
Head poukazuje na 1. uzlu.
Je to typu pointer-to-uzlu.
>> Chcete-li získat aktuální první uzel v seznamu,
musíme dereference tento ukazatel,
ale před tím, než může dereference to, musíme zkontrolovat
v případě, že ukazatel je null první.
Pokud je to null, seznam je prázdný,
a my bychom měli vytisknout zprávu, že, protože seznam je prázdný,
není poslední uzel.
Ale řekněme, že seznam není prázdný.
Pokud tomu tak není, pak bychom měli procházet celý seznam
dokud se na poslední uzel seznamu,
a jak můžeme říct, jestli se díváme na poslední uzel v seznamu?
>> No, pokud uzel je další ukazatel je null,
my víme, že jsme na konci
od posledního další ukazatel by neměl další uzel v seznamu, aby ukazoval na.
Je dobrým zvykem vždy poslední uzel je další ukazatel inicializován null
mít standardizovanou vlastnost, která upozorní nás, když jsme došli na konec seznamu.
>> Takže, pokud crawler → další je null,
nezapomeňte, že šipka syntaxe je zkratka pro dereferencing
ukazatel na struct, pak přístup
její další pole odpovídá nepříjemné:
(* Crawler). Další.
Jakmile jsme našli poslední uzel,
chceme tisknout prolézacího → val,
hodnota v aktuálním uzlu
které známe, je poslední.
V opačném případě, když jsme ještě na poslední uzlu v seznamu,
musíme přesunout na další uzel v seznamu
a zkontrolujte, zda je to poslední.
Chcete-li to, jen jsme nastavili pásové ukazatel
bodu za aktuálním uzlem je další hodnoty,
to znamená, že další uzel v seznamu.
To se provádí nastavením
crawler = crawler → další.
Pak se tento proces opakovat, se smyčkou například,
dokud nenajdeme poslední uzel.
Tak například, jestliže pásový ukazoval na hlavu,
jsme se vydali prolézací modul, aby ukazoval na pásový → Další,
který je stejný jako další oblasti prvního uzlu.
Takže, teď náš prohledávač ukazuje na 2. uzlu,
a opět, opakujeme to se smyčkou,
až jsme zjistili, poslední uzel, který je,
kde uzlu další ukazatel ukazuje na null.
A tady to máme,
jsme našli poslední uzel v seznamu, a vytisknout svou hodnotu,
stačí použít pásový → val.
>> Pojezdu není tak špatné, ale co o vkládání?
Řekněme, že chceme vložit celé číslo do 4. místě
v celé číslo seznamu.
To je mezi současnými 3. a 4. uzlů.
Opět musíme procházet seznam jen
dostat do 3. prvek, jeden jsme vkládání po.
Takže, jsme vytvořit prolézacího ukazatel znovu procházet seznam,
zkontrolujte, zda naše hlava ukazatel je null,
a pokud tomu tak není, přejděte náš prohledávač ukazatel na hlavním uzlu.
Takže, jsme na 1. prvek.
Musíme jít vpřed 2 více prvků, než můžeme vložit,
takže můžeme použít pro smyčce
int i = 1; i <3; i + +
a v každém opakování smyčky,
Rozšíření našich pásový ukazatel vpřed o 1 uzel
zkontrolovat, zda je aktuální uzel je další pole null,
a je-li to není, přesunout naše pásový ukazatel na další uzel
nastavením je roven aktuálnímu uzlu příštího ukazatel.
Takže, protože naše cyklu for říká k tomu, že
dvakrát,
jsme dosáhli 3. uzel,
a poté, co náš prohledávač ukazatel dosáhl uzel po
které chceme vložit náš nový integer,
Jak jsme vlastně se liší vkládání?
>> No, náš nový integer musí být vložen do seznamu
jako součást vlastního uzlu struct,
, protože to je ve skutečnosti sekvence uzlů.
Takže, pojďme se nový ukazatel na uzel
tzv. "new_node,"
a nastavte ji upozornit na paměti, že jsme nyní přidělit
na haldě pro uzel sám,
a kolik paměti potřebujeme přidělit?
No, o velikosti uzlu,
a chceme nastavit svůj val pole na celé číslo, které chceme vložit.
Řekněme, 6.
Nyní, uzel obsahuje náš celočíselnou hodnotu.
Je také dobrým zvykem inicializovat nový uzel je další pole
bodu na hodnotu null,
ale co teď?
>> Máme změnit vnitřní strukturu seznamu
a další ukazatele obsažené v seznamu je existující
3. a 4. uzly.
Vzhledem k tomu, další ukazatele určují pořadí v seznamu,
a od té doby jsme vložením náš nový uzel
přímo do středu seznamu,
to může být trochu složitější.
To je proto, pamatujte, náš počítač
zná jen umístění uzlů v seznamu
protože z dalších ukazatelů uložených v předchozích uzlů.
Takže, pokud se někdy ztratil některé z těchto lokalit,
říci změnou jednoho z následujících ukazatelů v našem seznamu,
Například, že jsme změnily
od 3. uzlu vedle pole
poukázat na některé uzlu sem.
Byli bychom smůlu, protože bychom
tušení, kde najít zbytek seznamu,
a to je zřejmě opravdu špatné.
Takže, musíme být opravdu pozor na jejich pořadí
, ve kterém jsme se manipulovat naše další ukazatele během zavádění.
>> Takže, zjednodušit to, řekněme, že
naše první 4 uzly
se nazývá A, B, C a D, s šipkami představující řetěz ukazatelů
která spojují uzly.
Takže, je nutné vložit náš nový uzel
mezi uzly C a D.
Je důležité, aby to ve správném pořadí, a já vám ukážu, proč.
>> Pojďme se podívat na špatně se to udělat jako první.
Hele, my víme, že nový uzel má přijít hned po C,
takže se pojďme nastavit C je další ukazatel
poukázat na new_node.
Dobře, zdá se v pořádku, jen musíme dokončit již nyní
Díky nového uzlu je další ukazatel bod D,
Ale počkejte, jak můžeme udělat, že?
Jediná věc, která by nám mohl říct, kde D je,
byla další ukazatel dříve uložené v C,
ale my prostě přepsal tento ukazatel
přejděte na nový uzel,
takže již nemáme ponětí, kde D je v paměti,
a my jsme ztratili zbytek seznamu.
Vůbec dobré.
>> Tak, jak to uděláme toto právo?
Za prvé, bodu nového uzlu je další ukazatel na D.
Nyní, jak nový uzel je a C je další ukazatele
směřují na stejný uzel, D,
ale to je v pořádku.
Nyní můžeme bod C je další ukazatel na nový uzel.
Takže jsme udělali to bez ztráty dat.
V kódu, C je aktuální uzel
že traversal ukazatel prolézací modul ukazuje na,
a D je reprezentován uzlem na který ukazuje aktuální uzlu následujícího pole,
nebo pásovém podvozku → další.
Takže, nejprve nastavte nový uzel je další ukazatel
poukázat na pásový → Další,
stejným způsobem jsme si řekli, new_node příští ukazatel by měl
poukazují na D na obrázku.
Pak můžeme nastavit aktuální uzel je další ukazatel
do našeho nového uzlu,
stejně jako jsme museli čekat, až bodu C na new_node ve výkresu.
Nyní je všechno v pořádku, a my jsme neztratili
přehled o veškerých údajů, a my jsme byli schopni jen
držet náš nový uzel ve středu seznamu
bez přestavět celou věc, nebo dokonce posunutí všechny prvky
způsob, jakým by se museli s pevnou délkou pole.
>> Takže, propojené seznamy jsou základní, ale důležité, dynamická datová struktura
které mají výhody i nevýhody
ve srovnání s poli a jiných datových struktur,
a jak je tomu často v informatice,
je důležité vědět, kdy použít každý nástroj,
takže si můžete vybrat ten správný nástroj na správné místo.
>> Pro více praxe, zkuste napsat funkce
odstranění uzlů z propojeného seznamu -
nezapomeňte dávat pozor na pořadí, ve kterém jste změny uspořádání
vaše další ukazatele, aby zajistily, že neztratíte kus svého seznamu -
nebo funkci počítat uzly v propojeném seznamu,
nebo legrace jeden, obrátit pořadí všech uzlů v propojeném seznamu.
>> Jmenuji se Jackson Steinkamp, ​​je to CS50.