[Powered by Google Translate] V načrtovanje, smo pogosto morali predstavljati sezname vrednosti, kot so imena učencev v oddelku ali njihovi rezultati na zadnji kviza. 

V jeziku C, razglasila nizi se lahko uporablja za shranjevanje seznamov. To je težko našteti elementi seznama shranjeni v matriki, in če morate za dostop do ali spreminjanje i-element seznama Za poljubni indeks I, ki jih je mogoče storiti v stalnem času, vendar nizi so v slabšem položaju, preveč. 

Ko smo jih razglasi, smo morali reči spredaj kako velike so, to je, koliko elementov lahko shranite in kako velika so ti elementi, ki se določi glede na njihovo vrsto. Na primer, int arr (10) lahko shranite 10 predmetov da sta velikost notr. 

Ne moremo spremeniti array na velikost po deklaraciji. Moramo narediti nov niz, če želimo shraniti več elementov. Razlog za to omejitev obstaja, je, da se naše Program shrani celoten spekter kot sosednje kos pomnilnika. Povejte to je buffer, kjer hranijo v naši matriki. Morda obstaja druge spremenljivke ki se nahaja tik ob polju v spomin, tako da ne moremo samo da je polje večje. 

Včasih bi radi v trgovini array za hiter dostop do podatkov, hitrost za malo več prožnosti. Vpišite povezani seznam, drugo osnovno strukturo podatkov vam morda ne bo tako seznanjeni. Na visoki ravni, povezani seznam shranjuje podatke v zaporedju vozlišč , ki so med seboj povezani s povezavami, od tod tudi ime "povezani seznam." Kot bomo videli, je ta razlika v oblikovanju prihaja do različnih prednosti in slabosti kot matriko. 

Tukaj je del kode C zelo enostaven povezan seznam celih števil. Vidite lahko, da smo prikazali vsako vozlišče v seznamu kot struct, ki vsebuje 2 stvari, celo za shranjevanje imenuje "val" in povezava na naslednji vozel v seznamu ki jih predstavljamo kot kazalec, imenovano "next". Na ta način bomo lahko spremljali celoten seznam Z enim samim kazalcem na vozlišču 1., in potem bomo lahko sledite naslednjim kazalci do 2. vozlišča, do 3. vozlišče, do 4. vozlišča, in tako naprej, dokler ne pridemo do konca seznama. 

Morda boste lahko videli 1 prednost, ki jo ima več statične strukture matrike - z povezan seznam, Ne potrebujemo velik kos pomnilnika v celoti. 1. vozlišče seznama lahko živeli na tem mestu v spominu, in bi 2. vozlišče je vso pot tja. Mi lahko prišli do vseh vozlišč, ne glede na to, kje v pomnilniku so, ker se začne na vozlišču 1., vsako vozlišče je naslednji kazalec nam pove točno kam naprej. 

Poleg tega nimamo povedati vnaprej kako velik bo povezan seznam je način delamo s statičnimi polji, saj lahko vodijo dodajanje vozlišča na seznam tako dolgo, kot je prostor nekje v spominu po novih vozlišč. Zato povezani seznami so enostavne za dinamično spreminjanje velikosti. Recimo, kasneje v programu moramo dodati več vozlišč v našem seznamu. Če želite vstaviti novo vozlišče v našem seznamu na letenje, vse, kar moramo storiti, je dodeliti pomnilnika za to vozlišče, plop vrednosti podatkov, nato pa kraj, kjer želimo s prilagoditvijo ustrezne kazalce. 

Na primer, če bi želeli, da se vozlišče v med 2. in 3. vozlišča seznama  mi ne bi bilo treba premakniti 2. ali 3. vozlišč na vse. Povejte smo vstavitve te rdeče vozlišče. Vse, kar bi morali storiti, je nastaviti novega vozlišča naslednji kazalec opozoriti na 3. vozlišče in potem rewire 2. vozlišča naslednji kazalec izpostaviti našega novega vozlišča. Torej, lahko spremenite velikost naše sezname na letenje saj je naš računalnik se ne sklicuje na indeksiranje, ampak o povezovanju z napotke za njihovo shranjevanje. 

Vendar pa je pomanjkljivost povezani seznam je, da za razliko od statičnega array, računalnik ne more samo skoči na sredino seznama. Ker računalnik mora obiskati vsak vozlišča v povezanem seznamu priti do naslednjega, to bo trajalo dlje, da najdejo določeno vozlišče kot bi se v matriki. Prečkanje celoten seznam potreben čas sorazmerno na dolžino seznama, ali O (n) v asimptotične zapisu. V povprečju dosegale vozlišče meni tudi čas sorazmerno n. 

Zdaj, kaj je dejansko napisati nekaj kode , ki deluje s povezanimi seznamov. Recimo, da želimo povezan seznam celih števil. Mi lahko predstavlja vozlišče v našem seznamu še enkrat kot struct z 2 področjih, celoštevilska vrednost se imenuje "val" in naslednji kazalec na naslednji vozel seznama. No, zdi dovolj preprosta. 

Recimo, da želimo napisati funkcijo ki prehaja iz seznama in izpise ven vrednost shranjena v zadnjem vozlišču seznama. No, to pomeni, da bomo morali za prečkanje vsa vozlišča v seznamu da je bil zadnji, ampak saj ne bomo dodajanjem ali izbris nič, ne želimo spremeniti notranja struktura prihodnjih kazalcev na seznamu. 

Torej se bomo morali kazalec posebej za prečkanje ki bomo poklicali "pajka". To bo plazijo skozi vse elemente na seznamu jih po verigo naslednjih kazalcev. Vsi smo shranili, je kazalec na vozlišče 1., ali "glava" seznama. Vodja opozarja na 1. vozlišča. To je tipa kazalec do vozlišča. 

Da bi dobili dejanski 1. vozlišča v seznamu moramo ciljne datoteke, to kazalec, vendar preden jo lahko dereference, moramo preveriti Če je kazalec null prvi. Če je ničen, je seznam prazen, in bi morali natisniti sporočilo, da je, ker je seznam prazen, ni zadnji vozel. Ampak, recimo, da seznam ni prazen. Če ni, potem bi morali plaziti skozi celoten seznam dokler ne pridemo do zadnje vozlišče seznama, in kako lahko poveste, če gledamo na zadnji vozel v seznamu? 

No, če je vozlišče je naslednji kazalec nič, Vemo, da smo na koncu ker bi zadnja Naslednji kazalec nimajo poleg vozlišča v seznamu, da kaže. To je dobra praksa, da vedno v lanskem vozlišča poleg kazalec inicializiranega na null da imajo standardizirano lastnost, ki nas opozori, ko smo prišli do konca seznama. 

Torej, če na gosenicah → naslednja nič, ne pozabite, da je puščica sintaksa je bližnjica za Dereferenciranje kazalec na struct, nato dostop njegovo naslednje polje enako, kar je nerodno: (* Pajek). Naslednjo. Ko smo našli zadnje vozlišče, želimo natisniti na gosenicah → val, vrednost v trenutnem vozlišču ki vemo, da je to zadnja. V nasprotnem primeru, če nismo še na zadnji vozel v seznamu, moramo premakniti na naslednji vozel v seznamu in preverite, če je to zadnja. Če želite to narediti, samo iz naše gosenicah kazalec opozoriti na naslednjo trenutnega vozlišča vrednosti, to je naslednji vozel v seznamu. To se opravi z določitvijo pajek pajek = → naslednja. Potem smo ponovite postopek, z zanko, na primer, dokler ne najdemo zadnje vozlišče. Tako, na primer, če pajek je obrnjena na glavo, smo postavili pajka opozoriti na gosenicah → naslednji, kar je enako kot v naslednjem polju 1. vozlišča. Torej, zdaj je naša pajek kaže na 2. vozlišča, in spet ponavljamo to z zanko, dokler ne bomo našli zadnje vozlišče, ki je, vozlišče, kjer je naslednji kazalec kaže na null. In tam jo imamo, smo našli zadnje vozlišče seznama, in natisniti svojo vrednost, smo samo uporabo gosenicah → val. 

Prečesava ni tako slabo, toda kaj vstavljanje? Lets reči hočemo, da vstavite celo število v 4. mesto celo v seznamu. To je med sedanjimi 3. in 4. vozlišč. Spet imamo za prečkanje seznam le priti do 3. element, na katerem sva po vstavitvi. Torej, smo ustvarili gosenicah kazalec ponovno prečkanje seznam, preveri, če je glava kazalec nič, in če ni, opozarja naš gosenicah kazalec na glavnem vozlišču. Torej, da smo na 1. elementa. Moramo iti naprej 2 več elementov, preden bomo lahko vstavite, tako da bomo lahko uporabite za zanko int i = 1; i <3; i + + in v vsaki ponovitvi zanke, izboljšanje našega gosenicah kazalec naprej za 1 vozlišče za preverjanje, če je trenutno vozlišče v naslednje polje je nična, in če ni, gremo naši gosenicah kazalec na naslednje vozlišče z določitvijo je enaka dostavo trenutnega vozlišča kazalca. Torej, ker smo v zanko pravi za to dvakrat, smo dosegli 3. vozlišče, in ko je naš pajek kazalec dosegel vozlišče po katero želimo vstaviti našo novo celo število, kako smo dejansko storite vstavljanje? 

No, naš novi celo je treba vstaviti na seznam kot del svoje struct vozlišča, ker je to res zaporedje vozlišč. Torej, naredimo nov kazalec na vozlišče imenovano "new_node" in jo nastavite na točko v spomin, da smo zdaj dodeliti na kup za vozlišče sam, in koliko pomnilnika bomo morali dodeliti? No, velikost vozlišča, in želimo, da določijo svoje val polje na celo število, ki ga želite vstaviti. Recimo, 6. Zdaj, vozlišče vsebuje našo vrednost celega števila. Prav tako je dobra praksa za inicializacijo novega vozlišča naslednje polje opozoriti na null, pa kaj zdaj? 

Moramo spremeniti notranjo strukturo seznama in naslednji kazalci iz obstoječih na seznamu za 3. in 4. vozlišča. Ker se naslednji kazalci določi vrstni red na seznamu in ker smo vstavljanje našo novo vozlišče desno na sredini seznama, je lahko nekoliko zapleteno. To je zato, ker se spomnite, naš računalnik Samo ve, kje vozlišč v seznamu zaradi naslednjih kazalcev, shranjenih v prejšnjih vozlišč. Torej, če bomo kdaj izgubil občutek za vsako od teh mest, pravijo, da spremenite eno od naslednjih kazalcev v našem seznamu, Recimo, da smo spremenili 3. vozlišča naslednje polje izpostaviti nekatere vozlišča tam. Mi bi lahko od sreče, ker mi ne bi sanja, kje najti preostanek seznama in to je očitno res slabo. Torej, moramo biti zelo previdni, da , v katerem smo manipulirajo svoje naslednje napotke med vstavljanjem. 

Torej, poenostaviti to, recimo, da naša prva 4 vozlov se imenujejo A, B, C in D, s puščicami predstavljajo verige kazalcev ki povezujejo vozlišča. Torej, moramo vstaviti našo novo vozlišče vmes vozlišča C in D. To je ključnega pomena, da to storite v pravilnem zaporedju, in pokazal ti bom, zakaj. 

Oglejmo si na napačen način, da to storite najprej. Hej, vemo, da je novo vozlišče je prišel takoj po C, tako da je določeno naslednji kazalec C je izpostaviti new_node. V redu, se zdi v redu, bomo morali končati do zdaj, ki jih izdelavo novega vozlišča poleg kazalca točko D, ampak počakajte, kako lahko to storimo? Edina stvar, ki bi nam lahko poveste, kje je bil D, je naslednji kazalec prej shranjen v C, vendar smo šele na novo napisal, da je kazalec da kaže na novo vozlišče, tako da nimamo več nobenega pojma, kje je D v spominu, in smo izgubili preostanek seznama. Ni dobro. 

Torej, kako bomo to pravico? Prvič, poudariti novega vozlišča naslednji kazalec na D. Zdaj, oba nova vozlišča in C je naslednji kazalci obrnjena v isto vozlišče, D, ampak to je v redu. Sedaj lahko naslednji točki C je kazalec na novo vozlišče. Zato smo to storili, ne da bi pri tem izgubili podatke. V kode C je trenutna vozlišče da prečkanje kazalec kaže na gosenicah, in D zastopa vozlišče opozoril, da do naslednjega trenutnega vozlišča področju, ali gosenicah → naslednja. Torej, moramo najprej določiti novega vozlišča naslednji kazalec opozoriti na gosenicah → naslednji, na enak način, smo rekli naslednji kazalec new_node je treba kažejo D na sliki. Potem bomo lahko nastavite trenutno vozlišče v naslednji kazalec za našo novo vozlišče, tako kot smo morali čakati na točko C na new_node na sliki. Zdaj je vse v redu, in nismo izgubili spremljanje vseh podatkov, in smo lahko samo držati našega novega vozlišča v sredini seznama ne obnovi celotno stvar ali celo premika elementov tako bi si morali s fiksno dolžino niza. 

Torej, povezani seznami osnovni, vendar pomembna dinamična struktura podatkov ki imajo tako prednosti kot slabosti v primerjavi z nizi podatkov in drugih objektov, in kot se pogosto dogaja na področju računalništva, je pomembno, da vedo, kdaj uporabiti vsako orodje, tako da lahko izberete pravo orodje za pravo delo. 

Za več prakse, poskusite pisati funkcij Brisanje vozlišča iz povezan seznam - ne pozabite, da bodite previdni, o vrstnem redu, v katerem ste preurediti vaš naslednji kazalci, da se zagotovi, da ne boste izgubili kos seznama - ali funkcijo za štetje vozlišča v povezanem seznamu ali smešna, da se obrne vrstni red vseh vozlišč v povezanem seznamu. 

Moje ime je Jackson Steinkamp, ​​to je CS50.