[Powered by Google Translate] U programiranju, često je potrebno da predstavljaju popise vrijednosti,
kao što su imena učenika u odjeljku
ili njihovi rezultati na posljednjem kvizu.
>> U C jeziku, izjavio polja mogu se koristiti
za pohranu liste.
To je lako nabrojati elemente popisa
pohranjene u niz, a ako je potrebno pristupiti
ili modificirati ith elementa popisa
za neke proizvoljne indeksa sam,
koji se može obaviti u stalnom vrijeme,
ali nizovi imaju nedostatke, previše.
>> Kada smo ih proglasiti, mi smo dužni reći
up front koliki su,
da je, koliko elementi mogu pohraniti
i koliko su ti elementi, koji se određuje prema vrsti.
Na primjer, int arr (10)
može pohraniti 10 artikala
koje su veličine int.
>> Mi ne možemo promijeniti niz veličinu nakon proglašenja.
Moramo napraviti novi niz ako želimo pohraniti više elemenata.
Razlog je to ograničenje postoji je da su naši
Program pohranjuje cijeli niz
kao granični komad memorije.
Recimo to je tampon gdje smo pohranjeni u našem polju.
Tu bi moglo biti druge varijable
nalazi tik do niza
u memoriji, tako da ne možemo
Upravo bi polje veći.
>> Ponekad bismo željeli trgovati polje je brzo pristup podacima brzinu
za malo više fleksibilnosti.
Unesite povezanu listu, jedan od osnovnih struktura podataka
možda neće biti kao upoznati.
Na visokoj razini,
povezani popis pohranjuje podatke u nizu čvorova
koji su međusobno povezani s vezama,
otud ime 'povezani popis.'
Kao što ćemo vidjeti, ta razlika u dizajnu
dovodi do različitih prednosti i nedostataka
nego niz.
>> Evo nekih C kod za vrlo jednostavan povezan popisu brojeva.
Možete vidjeti da smo zastupljeni svaki čvor
u popisu kao struct koji sadrži 2 stvari,
cijeli pohraniti zove 'val'
i veza na sljedeći čvor na popisu
koje predstavljaju kao pokazivač zove 'sljedeći. "
Na taj način, možemo pratiti cijeli popis
sa samo jednim pokazivač na prvi čvor,
i onda možemo slijediti sljedećoj pokazivače
na drugi čvor,
do 3. čvor,
na 4. čvor,
i tako dalje, dok ne dođemo do kraja popisa.
>> Možda ćete biti u mogućnosti vidjeti jedan prednost to ima
preko statičkog polja strukture - s povezan popisu,
ne trebamo veliki komad memorije uopce.
Na 1. čvor liste mogao živjeti na tom mjestu u memoriji,
a drugi čvor mogao biti skroz ovamo.
Možemo doći do svih čvorova, bez obzira gdje se u memoriji su,
jer počevši od 1. čvora, svaki čvor je sljedeći pokazivač
nam govori točno gdje ići sljedeći.
>> Osim toga, mi nemamo za reći up front
koliko je velik povezani popis će biti način radimo s statičkih polja,
jer možemo držati dodajući čvorova na popis
dokle god postoji prostor negdje u memoriji za nove čvorova.
Stoga, povezane liste su lako promijeniti veličinu dinamički.
Recimo, kasnije u programu moramo dodati više čvorova
u našem popisu.
Da biste umetnuli novi čvor na našem popisu u letu,
sve što morate učiniti je alocirati memoriju za taj čvor,
buć u podatkovnom vrijednosti,
i onda ga na mjesto gdje želimo podešavanjem odgovarajuće naputke.
>> Na primjer, ako smo htjeli da se čvor između
2. i 3. čvorovi popisu,
ne bismo imali da se presele drugi ili treći čvorova na sve.
Reci mi umetanjem ovaj crveni čvor.
Sve ćemo morati učiniti je postaviti novog čvora sljedeći pokazivač
ukazati na treći čvor
a zatim dobitak drugi čvora sljedeći pokazivač
ukazati na našoj novi čvor.
Dakle, možemo promijeniti veličinu naše liste na letu
jer naše računalo ne oslanjaju na indeksiranje,
nego na povezivanje pomoću pokazivača ih pohraniti.
>> Međutim, nedostatak povezani popisi
je da, za razliku od statičnog polja,
računalo ne može samo skočiti na sredini popisa.
Budući da računalo mora posjetiti svaki čvor u povezane liste
doći do sljedeću,
to će trebati više vremena za pronaći određeni čvor
nego što bi u polju.
Prijeći cijeli popis treba vremena proporcionalna
na duljinu popisa,
ili O (n) u asimptotska zapis.
U prosjeku, dosegnuvši bilo čvor
Također je potrebno vrijeme proporcionalna n.
>> Sada, neka je zapravo napisati neki kod
da radi s povezanim listama.
Recimo želimo povezane popis brojeva.
Mi može predstavljati čvor u našem popisu ponovno
kao struct s 2 polja,
cjelobrojna vrijednost zove 'val'
i uz pokazivač na sljedeći čvor popisa.
Pa, čini se jednostavna.
>> Recimo da želimo napisati funkciju
koji prolazi popisa i ispisuje
vrijednost pohranjena u posljednjem čvoru liste.
Pa, to znači da ćemo morati proći sve čvorove u popisu
pronaći zadnji, ali budući da nismo dodavanjem
ili brisanje ništa, ne želimo mijenjati
unutarnje ustrojstvo sljedećih upućuje na popisu.
>> Dakle, morat ćemo pokazivač posebno za obuhvaćanje
koje ćemo nazvati "robot".
To će puzati kroz sve elemente na popisu
slijedeći lanac idućih upućuje.
Svi smo pohranjena je pokazivač na prvi čvor,
ili 'glava' popisa.
Voditelj ukazuje na prvi čvor.
To je tipa pokazivač do čvora.
>> Da biste dobili stvarni prvi čvor u popisu,
moramo dereference ovaj pokazivač,
ali prije nego što ga možemo dereference, trebamo provjeriti
ako pokazivač null prvi.
Ako je nula, popis je prazan,
a mi bi trebali ispisati poruku da je, jer je popis prazan,
ne postoji zadnja čvor.
No, recimo da taj popis nije prazna.
Ako nije, onda bismo trebali puzati kroz cijeli popis
dok ne dođemo do posljednjeg čvora popisa,
i kako možemo reći ako gledamo na zadnji čvor na popisu?
>> Pa, ako je čvor je sljedeći pokazivač null,
znamo da smo na kraju
budući da je posljednja sljedeći pokazivač ne bi imao sljedeći čvor u popisu da pokazuje.
To je dobra praksa da se uvijek držati zadnji čvor na sljedeći pokazivač pokrenutog na nulu
imati standardizirani imovinu koja nas upozorava kad smo došli do kraja popisa.
>> Dakle, ako je pauk → sljedeća null,
sjetite se da je strelica sintaksa je prečac za dereferencing
pokazivač na struct, a zatim pristupa
njegov sljedeći polje ekvivalent nespretan:
(* Pauk). Sljedeći.
Nakon što smo našli zadnji čvor,
želimo ispisati indeksiranje → Val,
vrijednost u trenutnom čvoru
što znamo je posljednji.
Inače, ako još nismo u posljednji čvor u popisu,
moramo prijeći na sljedeći čvor u popisu
i provjerite je li da je zadnji.
Da biste to učinili, mi samo postaviti pauku pokazivač
ukazati na tekuće čvora sljedeću vrijednosti,
to je, sljedeći čvor u popisu.
To se postiže postavljanjem
pauk pauk = → sljedeća.
Onda smo ponoviti ovaj postupak, s petlje za primjer,
dok ne nađemo zadnji čvor.
Tako, na primjer, ako je pauk je pokazujući na glavi,
postavili smo indeksiranje ukazati na crawler → Next,
koji je isti kao sljedeći području 1. čvora.
Dakle, sada pauku je pokazujući na drugi čvor,
i, opet, mi ponoviti ovo s petlje,
dok smo našli zadnji čvor, koji je,
gdje je čvor je sljedeći pokazivač pokazuje na nulu.
I tu smo ga,
pronašli smo zadnji čvor na popisu, i ispisati svoju vrijednost,
mi samo koristiti indeksiranje → Val.
>> Poprijeko i nije tako loše, ali što je s umetanjem?
Recimo da želimo umetnuti cijeli u 4. poziciju
u integer popisu.
To je između tekućih 3. i 4. čvorova.
Opet, moramo proći popis samo
doći do 3. element, jedan smo umetanja nakon.
Dakle, možemo stvoriti pokazivač alata za indeksiranje ponovno prošli popis,
provjerite je li naša glava pokazivač null,
a ako to nije, ističu pauku pokazivač na glavnom čvoru.
Dakle, mi smo na prvi element.
Moramo ići naprijed dva više elemenata prije možemo ubaciti,
tako da možemo koristiti za petlju
int i = 1; ja <3; i + +
iu svakoj iteraciju petlje,
unaprijediti našu pokazivač indeksiranje naprijed jedan čvor
ako se provjerom trenutnog čvora sljedeće polje null,
a ako to nije, pomaknite pokazivač naš alat za indeksiranje na sljedeći čvor
postavljanjem je jednak struji čvora sljedeći pointer.
Dakle, budući da naša za petlje kaže da to učini
dva puta,
dosegli smo treći čvor,
i jednom pauku pokazivač dosegla čvor nakon
koji želimo umetnuti našu novu cijeli,
kako mi zapravo obaviti umetanjem?
>> Pa, naš novi cijeli mora biti umetnuta u popisu
kao dio svoje vlastite čvor struct,
jer ovo je stvarno slijed čvorova.
Dakle, ajmo napraviti novi pokazivač na čvor
pod nazivom 'new_node'
i postaviti ga da ukažu na spomen da smo sada izdvojiti
na hrpi za čvor sama,
i koliko memorije trebamo izdvojiti?
Pa, veličina čvora,
i želimo postaviti svoj val polje za cijeli koji želimo umetnuti.
Recimo, šest.
Sada, čvor sadrži naš cjelobrojne vrijednosti.
To je također dobra praksa da inicijalizirati novog čvora sljedeći polje
ukazati na nulu,
ali što sada?
>> Moramo promijeniti unutarnju strukturu popisa
i sljedeći pokazivači sadržane u popisu je postojeća
3. i 4. čvorovi.
Budući da su sljedeći pokazivači odrediti redoslijed na popisu,
a budući da smo umetanjem naš novi čvor
desno u sredini popisa,
to može biti malo zeznuto.
To je zato što, ne zaboravite, naša računalo
samo zna mjesto čvorova na popisu
zbog sljedećih upućuje pohranjenih u prethodnim čvorovima.
Dakle, ako mi ikada izgubila pojam o bilo kojem od tih mjesta,
recimo promjenom jedne od sljedećih upućuje na našem popisu,
na primjer, reći da smo promijenili
3. čvora sljedeće polje
ukazati na neke čvoru ovamo.
Mi bi se od sreće, jer mi ne bi
imaju ikakvu ideju gdje pronaći ostatak popisa,
i to je očito jako loše.
Dakle, moramo biti jako oprezni o nalogu
u kojem smo manipulirati naše sljedećoj upućuje tijekom umetanja.
>> Dakle, pojednostaviti ovaj, ajmo reći da
naši prvi četiri čvorovi
su pozvani A, B, C i D, sa strelice predstavljaju lanac pokazivače
koje povezuju čvorove.
Dakle, trebamo umetnuti naš novi čvor
između čvorova C i D.
To je važno da to učinite u pravom redoslijedu, a ja ću vam pokazati zašto.
>> Pogledajmo na pogrešan način to učiniti prvi.
Hej, znamo da je novi čvor mora doći odmah nakon C,
pa neka je postavljen C je sljedeći pokazivač
ukazati na new_node.
U redu, čini se ok, samo moramo završiti do sada po
izradu novog čvora pokraj pokazivača točku D,
ali čekaj, kako mi možemo učiniti?
Jedina stvar koja bi nas mogla reći gdje je D bio,
je sljedeći pokazivač prethodno pohranjena u C,
ali mi jednostavno rewrote da pokazivač
ukazati na novi čvor,
tako da mi više ne imati bilo koji pojma gdje je D u memoriju,
i izgubili smo ostatak popisa.
Nije dobro na sve.
>> Dakle, kako mi to pravo?
Prvo, ukazati novog čvora sljedeći pokazivač na D.
Sada, kako nova čvora i Kasiopejci sljedeći pokazivači
ukazuju na istom čvoru, D,
ali to je u redu.
Sada možemo točka C je sljedeći pokazivač na novi čvor.
Dakle, mi smo to učinili bez gubljenja podataka.
U kodu, C je trenutni čvor
da obuhvaćanje pokazivač robot pokazuje da,
i D predstavljaju čvor istaknuo da u trenutnoj čvora sljedećem polju,
ili gusjenicama → sljedeća.
Dakle, prvo smo postavili novog čvora sljedeći pokazivač
ukazati na crawler → Next,
Isto tako mi je rekao new_node je sljedeći pointer treba
ukazati na D na slici.
Zatim, možemo postaviti trenutnog čvora sljedeći pokazivač
našem novom čvoru,
baš kao što smo morali čekati do točke C do new_node u crtežu.
Sada je sve u redu, i nismo izgubili
praćenje svih podataka, i bili smo u mogućnosti da samo
držati naš novi čvor u sredini popisa
bez obnovi cijelu stvar ili čak prebacivanjem nikakve elemente
način na koji smo morali s fiksne duljine niza.
>> Dakle, povezane liste su osnovne, ali važna, dinamična struktura podataka
koji imaju svoje prednosti i nedostatke
u odnosu na poljima i drugih struktura podataka,
i kao što je često slučaj u računalnoj znanosti,
važno je znati kada koristiti svaki alat,
tako da možete odabrati pravi alat za pravi posao.
>> Za više praksi, pokušajte pisanja funkcije
brisanje čvorova iz povezane liste -
zapamtite biti oprezni o redoslijedu kojim ste preinake
Vaši sljedeći pokazivači kako bi se osiguralo da se ne izgubite komad popisu -
ili funkcija računati čvorove u povezane liste,
ili zabavno jedan, obrnuti redoslijed svih čvorova u povezane liste.
>> Moje ime je Jackson Steinkamp, ​​ovo je CS50.