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