>> [Glazbom]
>> Doug LLOYD: U redu, tako da na ovom trenutku u tijeku,
smo pokriveni puno osnovama C. Mi znamo mnogo o varijable, polja,
pokazivače, sve to dobre stvari.
Oni su svi nekako izgrađena u vidjeti kao osnova,
ali možemo učiniti više, zar ne?
Možemo kombinirati stvari zajedno na zanimljive načine.
>> I tako ćemo učiniti, počnimo granaju od onoga što nam daje C,
i početi stvarati vlastitu podataka strukture pomoću tih zgrada
blokovi zajedno učiniti nešto jako vrijedan, koristan.
Jedan od načina možemo učiniti je razgovarati o zbirkama.
Dakle, do sada smo imali jednu vrstu podataka strukture za zastupanje zbirke
poput vrijednosti, slične vrijednosti.
To će biti niz.
Imamo zbirke brojeva ili zbirke likova i tako dalje.
>> Strukture su također svojevrsni podataka strukture za prikupljanje informacija,
ali to nije za prikupljanje kao i vrijednosti.
Obično se miješa različite vrste podataka zajedno unutar jednog okvira.
Ali to nije samo po sebi koristi za lanac zajedno
ili spojite zajedno slično stavke, poput niza.
Nizovi su super za Element pogledati, ali opoziva
da je vrlo teško umetnuti u niz,
osim ako smo ugurate samom kraju tog polja.
>> A najbolji primjer imam za to je umetanje vrsta.
Ako se sjećate naš video na umetanje vrsta,
bilo je dosta rashodi su uključeni u vlasništvo
pokupiti elemente, a pomak ih zabit da stane nešto
u sredini vaše polje.
Nizovi također pate od drugog Problem, koji je nefleksibilnost.
Kad smo proglasiti niz, dobili smo jedan metak u njega.
Mi smo dobili za reći, ja želim to mnogi elementi.
Moglo bi biti 100, to bi moglo biti 1.000, to bi moglo
biti x gdje je x broj koji je korisnik nam je dao na brz ili na zapovijed
linije.
>> No, možemo samo dobiti jedan metak u njega, mi ne bi se onda reći o, zapravo sam
potrebno 101 ili mi je trebalo x plus 20.
Prekasno, već smo je proglasio polje, a ako želimo dobiti 101 ili x
plus 20, moramo proglasiti potpuno različit niz,
kopirati sve elemente polja više, a onda imamo dovoljno.
A što ako smo u krivu opet, što ako mi zapravo treba 102 ili x plus 40,
moramo to učiniti opet.
Dakle, oni su vrlo kruti za promjenu veličine naše podatke,
ali ako ćemo povezati neke osnove koje smo već
naučili o pokazivače i objekata, posebice pomoću dinamičke memorije
Raspodjela s malloc smo možete staviti ove dijelove zajedno
Za stvaranje nove podatke structure-- A pojedinačno povezani popis možemo say--
koji nam omogućuje da raste i smanjiti zbirku vrijednosti
i nećemo imati nikakvu izgubiti prostora.
>> Pa opet, mi zovemo tu ideju, ovaj pojam, popis povezani.
Konkretno, u ovom videu smo govori o pojedinačno povezane liste,
a zatim još jedan video ćemo razgovarati oko dvostruko povezane liste, koje
je samo varijacija na temu ovdje.
No, popis s pojedinačno povezan se sastoji od čvorova,
čvorovi samo kao apstraktna term-- to je samo nešto što zovem
to je neka vrsta Struktura, u osnovi, ja sam?
Samo ću nazvati node-- i to čvor ima dva člana ili dva polja.
Ima podataka, obično broj, plovak lik,
ili može biti neka druga vrsta podataka da ste definiran tipa def.
I ona sadrži pokazivač na drugi čvor istog tipa.
>> Dakle, imamo dvije stvari unutar ovaj čvor, podataka i pokazivač
na drugi čvor.
A ako počnete zamišljati to, možete razmišljati o tome
kao lanac čvorova koji spojeni zajedno.
Imamo prvi čvor, to sadrži podatke i pokazivač
na drugi čvor, koji sadrži Podaci, a pokazivač trećeg čvora.
I tako to je razlog zašto smo ga poziva povezani popis, oni su međusobno povezani.
>> Što to posebna čvor struktura izgledati?
Pa, ako se sjećate iz našeg videa na definiranje prilagođene vrste, s tipom def,
možemo definirati structure-- i unesite definirati strukturu kao što je ovaj.
tyepdef struct sllist, a onda sam koristim riječ vrijednosti ovdje proizvoljno
naznačiti bilo koji tip podataka stvarno.
Ti bi mogao proći na cijeli broj ili plovak, možete imati sve što želite.
To nije ograničeno na samo cijeli brojevi, ili bilo što slično.
Tako je vrijednost samo proizvoljna tip podataka, a zatim pokazivač
na drugi čvor istog tipa.
>> Zatim, tu je malo ulov ovdje definiranje strukture
kada je self referencijalni struktura.
Moram imati privremeni ime moje strukture.
Na kraju dana sam očito želite nazvati
SLL čvor, to je u konačnici novi ime dio mog tipa definicije,
ali ne mogu koristiti SLL čvor u sredini ove.
Razlog je, nisam stvorio tip zove SLL čvor
dok sam pogodio ovo konačna točka ovdje.
Do tog trenutka, moram imati još jedan način da se odnosi na ovu vrstu podataka.
>> A to je self referentna vrsta podataka.
To, s tip podataka od struktura koja sadrži podatke,
a pokazivač na drugi Struktura istog tipa.
Pa moram biti u mogućnosti da se odnose na Ova vrsta podataka barem privremeno,
tako dajući mu privremeni naziv struct sllist
mi omogućuje onda reći da želite pokazivač na drugi struct sllist,
struct sllist zvijezda, a zatim Nakon što sam završio definiciju,
Ja sada mogu zvati upišite SLL čvor.
>> Dakle, to je razlog zašto možete vidjeti postoji privremeno ime ovdje,
ali stalni ime ovdje.
Ponekad možete vidjeti definicije strukture,
na primjer, koji nisu samouprave referencijalni, da
nemaju ime Specifier ovdje.
To bi samo reći typedef struct, otvori kovrčavu braće, a potom ga definirati.
Ali, ako ste struct je self referentna, jer to je jedan,
morate da odredite privremeni naziv tipa.
Ali u konačnici, sada da smo to učinili,
mi samo može odnositi na ovi čvorovi, ove jedinice,
kao SLL čvorova za svrhe ostatka ovog videa.
>> U redu, tako da znamo kako stvoriti povezani popis čvor.
Znamo kako definirati je povezani popis čvor.
Sada, ako ćemo početi ih koristi za prikupljanje podataka,
postoji nekoliko operacija smo morate razumjeti i raditi.
Moramo znati kako stvoriti je povezani popis iz ničega.
Ako nema popisa već, želimo pokrenuti jednu.
Dakle, moramo biti u stanju izraditi popis povezani,
trebamo vjerojatno tražiti kroz popis linkova
pronaći element tražimo.
Moramo biti u mogućnosti ubaciti nove stvari u popisu,
želimo da naša lista biti u mogućnosti da rastu.
A isto tako, želimo biti u mogućnosti za brisanje stvari iz našeg popisa,
želimo da naša lista biti u mogućnosti smanjiti.
I na kraju našeg programa, a posebno
Ako se sjećate da smo dinamički dodjele memorije
graditi ove popise obično, želimo osloboditi sve te memorije
kad završimo rad s njim.
I tako moramo biti u mogućnosti obrisati Cijeli povezani popis u jednom uspjeti prepad.
Tako ćemo proći kroz neke od tih operacija
i kako bi ih vizualizirati, govori u pseudokod kôd posebno.
Dakle, želimo stvoriti povezani popis, pa možda smo
Želite definirati funkcije s ovim prototip.
SLL čvor zvijezda, stvarati, a ja sam prolazu u jednom argumentu, neke proizvoljne podatke
upišite opet, neke proizvoljne vrste podataka.
Ali ja sam returning-- ovu funkciju treba povratak na mene pokazivač, do pojedinačno
povezani popis čvor.
Opet, mi pokušavamo stvoriti je povezani popis iz ničega,
pa mi treba pokazivač taj popis kad sam učinio.
>> Pa što su koraci uključeni ovdje?
Pa, prvo što sam učiniti je dinamički
izdvojiti prostor za novi čvor.
Opet, mi smo ga stvara ni iz čega zrak, tako da ćemo morati malloc prostora za to.
I naravno, odmah nakon što smo malloc,
uvijek provjerite je li da su naši pointer-- nismo dobili natrag null.
Jer ako ćemo pokušati popustljivost null pokazivača,
ćemo trpjeti segfault i ne želimo to.
>> Zatim želimo ispuniti u polju, želimo inicijalizirati polje vrijednosti
i inicijalizirati slijedeće polje.
A onda želimo to-- kraju kao Funkcija prototip indicates-- želimo
da se vrati pokazivač na SLL čvor.
Dakle, ono što bi se ova izgledati vizualno?
Pa, prvo ćemo dinamički izdvojiti prostor za novi SLL čvor,
pa smo malloc-- to vizualni prikaz
čvora smo upravo stvorili.
A mi provjerite je li to nije null-- u ovom slučaju,
slika ne bi pokazalo se ako je null,
bismo ponestane memorije, tako da smo dobri ići tamo.
Dakle, sada smo na korak C, inicijalizirati polje čvorovi vrijednost.
Pa, na temelju ove funkcije zvati Ja sam koristeći ovdje
Izgleda da želim proći u 6, pa ću 6 u polju vrijednosti.
Sada, inicijalizirati slijedeće polje.
Pa, što ću učiniti tamo, ne postoji ništa sljedeći, pravo,
to je jedina stvar na popisu.
Zato što je sljedeća stvar na popisu?
>> To ne bi trebalo ukazati na što, u pravu.
Nema ništa drugo tamo, tako da ono što je koncept znamo da je to nothing--
upućuje na ništa?
To bi trebao biti možda želimo staviti null pokazivača tamo,
a ja ću predstavljaju null pokazivač kao samo crvenu kutiju,
ne možemo ići dalje.
Kao što ćemo vidjeti malo kasnije, imat ćemo eventualno lanci
strelica povezivanje ovi čvorovi zajedno,
ali kada hit crvena kutija, to je null,
ne možemo ići dalje, to je kraj popisa.
>> I na kraju, mi samo želimo vratiti pokazivač na ovom čvoru.
Tako ćemo ga zvati novi, i da će se vratiti novi
tako da se može koristiti u god funkciju ga je stvorio.
Dakle, tamo idemo, Mi smo stvorili pojedinačno povezani popis čvor iz ničega,
a sada imamo popis možemo raditi.
>> Sada, recimo već imaju veliki lanac,
i želimo pronaći nešto u njemu.
I želimo funkciju koja se događa da se vrati true ili false, ovisno
o tome da li postoji vrijednost u tom popisu.
Funkcija prototip, ili izjava za tu funkciju,
može izgledati this-- bool naći i onda želimo proći u dva argumenta.
>> Prvi je pokazivač na Prvi element popisa povezane.
To je zapravo nešto što ćete uvijek žele pratiti,
i zapravo bi moglo biti nešto što Možete čak staviti u globalnoj varijabli.
Nakon što stvorite popis, ti uvijek, uvijek
želite pratiti vrlo Prvi element liste.
Na taj način možete se odnose na sve ostale elemenata samo nakon lanac,
bez da upućuje netaknut svakog pojedinog elementa.
Vi samo trebate pratiti prvi jednom, ako su svi ti ulancane.
>> A onda je druga stvar mi prolaze u jednom
je proizvoljno some-- Bez obzira na vrstu podataka smo
u potrazi za ne postoji unutar nadamo se jedan od čvorova u popisu.
Pa što su koraci?
Pa, prva stvar koju radimo je stvaramo poprečnog pokazivač
ukazujući na listi glavu.
Pa, zašto mi to učiniti, već smo imati pokazivač na listama glave,
zašto ne bismo samo premjestiti da je jedan oko?
Pa, kao što sam upravo rekao, to je jako važno za nas
uvijek pratiti prvi element u listi.
I to je zapravo bolje stvoriti duplikat toga,
i koristiti da bi se kretati tako mi nikada slučajno odmaknuti, ili ćemo uvijek
imaju pokazivač u nekom trenutku koji je Pravo na prvom elementu popisa.
Tako da je bolje stvoriti Drugi koji koristimo za pomicanje.
>> Onda smo samo usporediti li Polje vrijednosti na tom čvoru
je ono što tražimo, a ako je Ne, mi samo premjestiti na sljedeći čvor.
A mi bi da radi više, i više, i više,
dok ne bilo naći element, ili ćemo udariti
null-- smo stigli do kraja popisa i to ne postoji.
Ovaj nadamo trebao zvono zvoni za vas kao samo linearno pretraživanje,
mi smo samo replicira u pojedinačno povezani popis strukture
umjesto koristeći niz to učiniti.
>> Dakle ovdje je primjer popis pojedinačno povezani.
Ovaj se sastoji od pet čvorova, a imamo
pointer na glavi od Popis, koji se zove popis.
Prva stvar koju želite učiniti je opet, napravite obuhvaćanje pokazivač.
Dakle, sada imamo dva pokazivače koji ukazuju na istu stvar.
>> Sada, obavijest i ovdje, nisam moraju malloc bilo prostora za Trav.
Nisam rekao Trav jednak malloc nešto, da je čvor već postoji,
da je prostor u memoriji već postoji.
Dakle, sve sam zapravo radiš je stvarajući još jedan pokazivač na nju.
Neću mallocing dodatni prostor, upravo su dva pokazivače
ukazujući na istu stvar.
>> Tako je 2 ono što tražim?
Pa, ne, pa umjesto da sam će se premjestiti na sljedeću.
Tako je u osnovi, rekao bih, trav jednak Trav sljedeći.
Je 3 ono što ja tražim, ne.
Tako sam i dalje ići putem, dok na kraju
doći do 6 što je ono što tražim za temelje na funkciji poziva
Imam na vrhu tamo, pa sam učinio.
>> Sad, što ako je element sam tražite nije na popisu,
Je li još uvijek ide na posao?
Pa, primijetiti da je popis Ovdje je suptilno različita,
i to je još jedna stvar koja je važno s povezanim popisima,
ne morate sačuvati ih u bilo kojem određenom redoslijedu.
Možete ako želite, ali možda ste već primjetili
da nismo praćenje što je broj elemenata smo na.
>> I to je vrsta jednoj trgovini da mi imati s povezanom popisu stihova polja,
Je li to nemamo izravnim pristupom više.
Ne možemo samo reći, ja želim ići na 0th elementa,
ili 6. element moje polje, što ja mogu učiniti u nizu.
Ne mogu reći da želim ići na 0. element ili 6. elementa,
ili 25. element mom popisu povezane, nema indeks povezane s njima.
I tako se to zapravo ne smeta ako smo sačuvati naš popis u redu.
Ako želite tebe svakako može, ali postoji
nema razloga zašto im je potrebno očuvati u bilo kojem redoslijedu.
Pa opet, pokušajmo i naći 6 u ovom popisu.
Pa, mi početi na početak, ne nalazimo 6,
a onda nećemo nastaviti nalaz 6, dok smo na kraju doći do ovdje.
Tako sada Trav ukazuje na čvoru sadrži 8, a šest je nije tamo.
>> Dakle, sljedeći korak će biti ići na sljedeću pokazivač,
tako kažu trav jednak Trav sljedeći.
Pa, Trav sljedeći, naznačeno crveni okvir postoji, je null.
Dakle, postoji nigdje drugdje idu, pa u ovom trenutku
možemo zaključiti da smo postigli kraj popisa povezani,
i 6 nije tamo.
I to bi se vratio netočno u ovom slučaju.
>> U redu, kako ćemo umetnuti novi čvor u popis povezani?
Tako smo bili u mogućnosti stvoriti je povezani popis niotkuda,
ali vjerojatno želite izgraditi lanac, a ne
stvoriti hrpu različitih popisa.
Želimo imati jedan popis koji ima hrpa čvorova u njemu,
Ne hrpa liste s jednim čvor.
Dakle, ne možemo zadržati samo pomoću Napravite Funkcija smo definirali ranije, sada smo
želite umetnuti u popis koji već postoji.
>> Dakle ovom slučaju, idemo proći u dva argumenta,
pokazivač na glavu da povezani popis koji želimo dodati.
Opet, to je razlog zašto je tako važno da se uvijek
pratiti, jer to je jedini način na koji smo stvarno
moraju odnositi na cijeli popis samo pokazivač na prvi element.
Zato želimo proći u pokazivač na taj prvi element,
i što god mi vrijednost želite dodati na popis.
I na kraju ova funkcija će se vratiti pokazivač
za novog šefa popisu povezane.
>> Koji su koraci uključeni ovdje?
Pa, baš kao i sa stvaranje, moramo dinamički alocirati
prostor za novi čvor i provjerite sigurno mi ne ponestane memorije, opet,
jer mi koristimo malloc.
Zatim želimo popuniti i umetnite čvor,
pa stavite broj, bez obzira na Val je u čvor.
Želimo umetnuti čvor na početak popisa povezane.
>> Postoji razlog što sam želite to učiniti, i to
moglo biti vrijedno uzimanje trenutak za pauziranje video ovdje,
i razmišljati o tome zašto bih želio ubacite u početku povezan
Popis.
Opet, što sam spomenuo ranije da ne stvarno
smeta ako smo ga sačuvati u bilo red, pa možda je to trag.
A ste vidjeli što će se dogoditi ako Želio to-- ili samo na sekundu
Prije kad smo išli kroz potragu si
mogao vidjeti što bi moglo dogoditi ako smo pokušali
umetnuti na kraju liste.
Jer mi nemaju pokazivač na kraju liste.
>> Dakle razlog da bih htio umetnuti na početku,
je zato što ja mogu učiniti odmah.
Imam pokazivač na početku i ćemo vidjeti u vizualnom u sekundi.
Ali ako želite umetnuti na kraju, Moram početi na početku,
prošli sve do kraj, a zatim ga pričvrstiti na.
Dakle, to bi značilo da umetanje na kraju liste
će postati O n rad, ide natrag
u našu raspravu o računalna složenost.
To bi postati O n rada, gdje kao popis dobio veći i veći,
i veći, to će postati sve više i teže tack nešto
na je na kraju.
Ali to je uvijek jako jednostavno tack nešto na na početku,
ti si uvijek na početku.
>> I vidjet ćemo vizualni to opet.
I onda odjednom smo učinili, jednom smo umetnuli novi čvor,
želimo vratiti našu pokazivač novi šef popisu povezani, što
jer smo umetanje Na početak, zapravo će biti
pokazivač na čvor smo upravo stvorili.
Idemo vizualizirati to, jer mislim da ću vam pomoći.
>> Dakle, ovdje je naš popis, a sastoji se od četiri elementa, čvor koji sadrži 15,
što ukazuje na čvoru sadrži 9, koji je
ukazuje na čvor koji sadrži 13, što ukazuje na čvor koji sadrži
10, koji ima nula Pokazivač kao svoj sljedeći pokazivač
tako da je kraj popisa.
Dakle, želimo umetanje novi čvor s vrijednošću 12
na početku ovog Popis, što nam je činiti?
Pa, prvo smo malloc prostor za čvor, a onda smo stavili 12 tamo.
>> Dakle, sada smo postignut Odluka točka, zar ne?
Imamo par upućuje da smo mogli
kretati, koje smo trebali pomaknuti prvi?
Hoćemo li napraviti 12 točku novi šef list--
ili me ispričajte, trebali smo napraviti 12 ukazuju na staru glavu na popisu?
Ili bismo trebali reći da je Lista sada počinje u 12.
Postoji razlika tamo, a mi ćemo gledati
na ono što se događa s obje u sekundi.
>> No, to dovodi do super tema za sidebar,
što je to jedan od trickiest stvari s povezanim popisima
se dogovoriti pokazivače u ispravnom redoslijedu.
Ako premjestite stvari iz reda, možete završiti slučajno
orphaning ostatak liste.
I ovdje je primjer toga.
Dakle, idemo s idejom of-- Pa, upravo smo stvorili 12.
Znamo 12 će biti novi šef popisa,
pa zašto ne bismo samo premjestiti popis pokazivač ukazati tamo.
>> U redu, tako da je dobro.
Pa sad, gdje se 12 slijedeću točku?
Mislim, vizualno možemo vidjeti da će ukazati na 15.,
kao ljudi to je stvarno očito za nas.
Kako računalo zna?
Nemamo ništa ukazujući na 15 više, zar ne?
>> Izgubili smo svaku mogućnost da se odnosi na 15.
Ne možemo reći novi strelicu pored equals nešto, nema ničega.
U stvari, mi smo bez roditelja ostatak popisa
na taj način, mi smo slučajno razbiti lanac.
I sigurno ne želite to učiniti.
>> Tako ćemo se vratiti i pokušati to opet.
Možda je prava stvar za učiniti je postaviti 12 je sljedeći pokazivač
na staru glavu na popisu prvog, onda možemo pomaknuti popis više.
I, u stvari, da je točno da bismo
trebate slijediti kad smo rad s jednostruko povezane liste.
Mi uvijek želimo spojiti Novi element u popisu,
prije nego što smo uzeti takav važan korak promjene
gdje je voditelj popisa povezan je.
Opet, to je takva temeljna stvar, ne želimo izgubiti trag o tome.
>> Dakle, želimo biti sigurni da sve ulancane,
Prije nego smo prešli tu pokazivač.
I tako će to biti ispravan redoslijed, što je za spajanje 12 na listi,
onda kažu da se popis počinje 12.
Ako smo rekli popis počinje u 12 i a zatim pokušao spojiti 12 na listi,
već smo vidjeli što se događa.
Gubimo popis greškom.
>> U redu, tako da još jedna stvar o čemu razgovarati.
Što ako želimo riješiti cijeli povezani popis odjednom?
Opet, mi smo mallocing sve to prostor, pa smo
treba ga osloboditi kad završimo.
Dakle, sada želimo obrisati cijeli povezani popis.
Pa, što želimo učiniti?
>> Ako smo postigli nultu pokazivač, mi želite prestati, inače, jednostavno izbrišite
ostatak popisa, a zatim osloboditi me.
Brisanje ostatak popisa, a zatim osloboditi trenutni čvor.
Što to zvuči kao, koju tehniku ​​ima smo razgovarali
o prije to zvuči kao?
Brisanje i svi drugi, onda vratiti i obrisati me.
>> To je rekurzija smo napravili Problem malo manji,
Govorimo izbrisati svi drugo, onda možete me izbrisati.
I dalje niz cestu, koja čvor reći će izbrisati svi ostali.
Ali s vremenom ćemo na točka u kojoj je popis ništavan,
i to je naš osnovni scenarij.
>> Tako ćemo pogledati ovaj, i kako to može raditi.
Dakle, ovdje je naš popis, to je ista popis samo smo pričali o,
a tu je korake.
Ima puno teksta ovdje, ali nadamo se vizualizacija će vam pomoći.
>> Tako smo have-- i sam izvukao do našeg stog okviri slici
iz naše video na poziv dimnjaka, i nadamo se sve to
zajedno će vam pokazati što se događa.
Dakle, ovdje je naš pseudokod broj.
Ako dođe do null pokazivač, zaustavi, inače,
izbrisati ostatak popisa, zatim osloboditi trenutni čvor.
Tako sada, list-- pokazivač da smo
prolaze uništiti bodova 12.
12 nije null pointer, tako da smo će izbrisati ostatak liste.
>> Što se brisanja Ostatak od nas koji su uključeni?
Pa, to znači stvaranje pozvati uništiti, govoreći
da 15 je početak Ostatak popisa želimo uništiti.
I tako je poziv da uništi 12 je vrsta na čekanju.
To je zamrznuta tamo, čekajući pozvati uništiti 15, završiti svoj posao.
>> Pa, 15 nije NULL pokazivač, te pa to će reći, u redu,
dobro, izbrisati ostatak liste.
Ostatak popisa počinje u 9, i tako samo ćemo
pričekajte dok ne izbrišete sve stvari, a onda se vratiti i obrisati me.
Pa 9 će reći, dobro, Nisam null pointer,
tako izbrisati ostatak popisa odavde.
I tako pokušati uništiti 13.
13 kaže, nisam NULL pokazivač, Ista stvar, to prolazi mužjak.
10 nije NULL pokazivač, 10 sadrži null pokazivača,
ali 10 je sama po sebi nije null pokazivač upravo sada,
i tako to prolazi mužjak previše.
>> A sada popis bodove tamo, to stvarno bi ukazati na some--
ako sam imao više prostora u slici, to bi ukazati na neke slučajnim prostora
da ne znamo što je to.
To je nulta pokazivač ipak, popis je doslovno sada postavljena je vrijednost null.
To pokazuje upravo u toj crvenoj kutiji.
Došli smo null pointer, tako možemo zaustaviti, a mi smo učinili.
>> I tako da ljubičasta okvir now-- Na vrh stack-- to je aktivni okvir,
ali to je učinjeno.
Ako smo postigli null pokazivača, zaustaviti.
Mi ne radimo ništa, mi ne može osloboditi null pokazivača,
nismo malloc bilo prostor, pa smo gotovi.
Dakle tu funkciju okvira je uništen, a mi
resume-- smo pokupiti gdje smo ostavili off sa sljedećim najvećim jedan, koji
ovo tamno plavi okvir ovdje.
Tako smo pokupiti tamo gdje smo stali.
Izbrisali smo ostatak od Popis je već, tako da sada smo
će osloboditi trenutne čvorova.
Tako sada možemo osloboditi ovaj čvor, a sada Došli smo do kraja funkciju.
I tako da funkcija okvir je uništen, i mi pokupiti na svijetlo plave boje.
>> Tako da says-- sam već done-- brisanje ostatak popisa, tako da
osloboditi trenutni čvor.
A sada žuti okvir natrag na vrh dimnjaka.
I tako, kao što vidite, mi smo sada uništavanje popis s desna na lijevo.
>> Što bi se dogodilo, ipak, Ako smo učinili stvari na krivi način?
Baš kao i kada smo pokušali dodati element.
Ako zabrljao lanac, ako nismo povezati pokazivače
u ispravnom redoslijedu, ako Samo oslobodi prvi element,
ako mi samo oslobodio voditelj popisa, sada smo
nema načina da se odnosi na ostatak liste.
I tako bismo imali roditelja je sve,
mi bi imali ono što je naziva otjecanje memorije.
Ako se sjećate iz našeg videa na dinamičke dodjele memorije,
to nije vrlo dobra stvar.
>> Dakle, kao što sam rekao, ne postoji više operacija
da trebamo koristiti za rad sa povezane popis učinkovito.
A možda ste primijetili sam izostavljen jedan, brisanje jednog elementa iz povezani
Popis.
Razlog zbog kojeg sam to učinio je to je zapravo vrsta
lukav razmišljati o tome kako izbrisati jedan element iz pojedinačno
povezani popis.
Moramo biti u stanju preskočiti nešto u popisu, koji
znači da smo dobili na point-- mi želite izbrisati ovu node--
ali kako to napraviti tako da smo ne gube bilo kakve informacije,
moramo povezati ovo čvor ovdje, ovdje.
>> Tako sam vjerojatno učinio krivo iz vizualne perspektive.
Tako smo na početku naše Popis, mi smo napreduje kroz,
želimo obrisati ovaj čvor.
Ako smo samo ga izbrisati, smo slomljena lanac.
Ovaj čvor ovdje odnosi se na sve drugo,
sadrži lanac od ovdje na van.
>> Dakle, ono što trebamo učiniti je zapravo nakon što smo dobili na ovom mjestu,
je potrebno da se korak natrag jedan, i spojiti ovaj čvor u ovaj čvor,
pa onda možeš izbrisati onaj u sredini.
Ali pojedinačno povezani popisi ne pružaju nam način da ide unatrag.
Dakle, moramo ni čuvati Dva naputke, i premjestiti ih
vrsta off koraka, jedan iza druge kao što idemo, ili doći do točke
a zatim poslati još pokazivač preko.
I kao što možete vidjeti, to može dobiti malo neuredan.
Srećom, imamo još jedan način da se riješi to,
kada govorimo o dvostruko povezanim popisima.
>> Ja sam Doug Lloyd, ovo je CS50.