>> [Musiikkia]
>> DOUG Lloyd: OK, joten on tässä vaiheessa tietenkin
Selvitimme jo paljon perusasiat C. Tiedämme paljon muuttujia, taulukot,
osoittimet, kaikki hyvät jutut.
Ne ovat kaikki tavallaan rakennettu vuonna nähdä niin perustekijät,
mutta voimme tehdä enemmän, eikö?
Voimme yhdistää asioita yhdessä kiinnostavalla tavalla.
>> Ja niin tehdään se, aloitetaan sektoreita, mitä C antaa meille,
ja alkaa luoda omia tietoja rakenteet näiden rakennus
lohkot yhdessä tehdä jotain todella arvokas, hyödyllinen.
Yksi tapa tehdä tämä on puhua kokoelmista.
Joten toistaiseksi meillä on ollut yksi millaisia ​​tietoja rakenne edustaa kokoelmia
samankaltaisten arvot, samat arvot.
Se olisi jono.
Meillä on kokoelmia kokonaislukuja, tai kokoelmat merkkiä ja niin edelleen.
>> Rakenteet ovat myös eräänlainen tietojen rakenne tietojen keräämiseksi,
mutta se ei ole keräämiseksi kuten arvoja.
Se yleensä sekoittaa erilaiset tiedot yhdessä sisällä yhden laatikon.
Mutta se ei ole itse käytetään ketjun yhdessä
tai liittää yhteen samankaltaisia kohteita, kuten array.
Taulukot ovat hyvin elementti etsiä, mutta muistuttaa
että se on hyvin vaikeaa lisättävän array,
ellei olemme lisäämällä at aivan lopussa, että jono.
>> Ja paras esimerkki minulla on että on lisäyslajittelun.
Jos muistatte meidän video sijoittamista lajitella,
siellä oli paljon kustannuksella mukana ottaa
poimia elementtejä, ja siirtää niitä pois tieltä sopivaksi jotain
keskelle teidän array.
Paneelit kärsivät myös toinen ongelma, joka on joustamattomuus.
Kun me julistamme array, saamme yhden ampui sitä.
Saamme sanoa, haluan Tämän monia elementtejä.
Voi olla 100, se voisi olla 1000, se saattaa
olla X, jossa x on numero, että käyttäjä antoi meille nopeasti tai komento
linja.
>> Mutta me vain saada yksi laukaus sitä, me älä päästä sitten sanoa oh, itse asiassa
tarvitaan 101, tai tarvitsin x + 20.
Liian myöhäistä, olemme jo ilmoittanut array, ja jos haluamme saada 101 tai X
plus 20, meidän täytyy julistaa täysin eri array,
kopioi kaikki taulukon alkiot yli, ja sitten meillä on riittävästi.
Ja entä jos olemme väärässä jälleen, mitä jos me todella tarvitsemme 102, tai X + 40,
meidän täytyy tehdä tätä uudelleen.
Joten he ovat hyvin joustamaton koon muuttamisen tietomme,
mutta jos yhdistämme yhteen joitakin perusasiat, että olemme jo
oppinut viitteitä ja rakenteita, erityisesti käyttäen dynaaminen muisti
jakamista malloc, me voi laittaa nämä palaset yhteen
luoda uutta tietoa structure-- yksittäin linkitetty lista voisimme say--
jonka avulla voimme kasvaa ja kutistua kokoelma arvojen
ja meillä ei ole mitään hukkaan tilaa.
>> Joten jälleen, me kutsumme tätä ajatusta, käsitystä, linkitetty lista.
Erityisesti tämän videon olemme puhumme yksittäin linkitetty lista,
ja sitten toinen video jutellaan noin kaksinkertaisesti liittyvät luettelot, joka
on vain muunnelma teemasta täällä.
Mutta yksittäin linkitetty lista koostuu solmut,
solmut vain on abstrakti term-- se on vain jotain Soitan
se eräänlainen rakenne, periaatteessa, olen?
Juuri menossa kutsua sitä node-- ja tämä solmulla on kaksi jäsentä, tai kaksi kenttää.
Se on tietoja, yleensä kokonaisluku, merkki kellua,
tai voisi olla jokin muu tietolaji että olet määritetty tyyppi def.
Ja se sisältää osoittimen toisen solmun samaa tyyppiä.
>> Joten meillä on kaksi asiaa sisällä tämä solmu, tiedot ja osoitin
toiseen solmuun.
Ja jos alkaa visualisoida tämän, voit ajatella sitä
kuten ketju solmuja, jotka on liitetty yhteen.
Meillä on ensimmäinen solmu, se sisältää dataa, ja osoitin
toiselle solmulle, joka sisältää datan, ja osoitin kolmanteen solmuun.
Ja niin siksi me kutsumme sitä linkitetty lista, ne toisiinsa.
>> Mitä tämä erityinen solmu rakenne näyttää?
No, jos muistatte meidän video määritellään räätälöidyt tyypit, tyypin def,
voimme määritellä structure-- ja Define rakenne näin.
tyepdef struct sllist, ja sitten olen käyttämällä sanaa arvo tähän mielivaltaisesti
osoittamaan mitään tietotyyppi todella.
Voisit siirtää kokonaisluku tai float, sinulla voisi olla mitä haluat.
Se ei rajoitu vain kokonaisluvut, tai jotain sellaista.
Joten arvo on vain mielivaltainen tietotyyppi, ja sitten osoitin
toisen solmun samaa tyyppiä.
>> Nyt, siellä on pieni saalis täällä määritellään rakenne
kun se on itse viite rakenne.
Minun on väliaikainen nimi minun rakennetta.
Lopussa päivän I selvästi halua kutsua sitä
SLL solmu, joka on viime kädessä uusi nimi osa minun tyyppiä määritelmän,
mutta en voi käyttää SLL solmu keskellä tämä.
Syynä on, en ole luotu tyyppi nimeltä SLL solmu
kunnes osuin tämä viimeinen kohta täällä.
Tuohon asti, minun täytyy saada toinen tapa viitata tietojen tyyppi.
>> Ja tämä on itsestään viitetietojen tyyppi.
Se, s tietotyyppi rakenne, joka sisältää tiedot,
ja osoitin toiseen rakenne samaa tyyppiä.
Joten minun täytyy pystyä viitata Tämä datatyyppi ainakin väliaikaisesti,
joten antaa sille tilapäisen nimi struct sllist
sallii minun sitten sanoa haluan osoitin toiseen struct sllist,
struct sllist tähti, ja sitten kun olen suorittanut määritelmä,
Voin nyt soittaa tämäntyyppisiä SLL solmu.
>> Joten siksi näet siellä väliaikainen nimi täällä,
mutta pysyvä nimi tähän.
Joskus saatat nähdä määritelmät rakenne,
esimerkiksi, että eivät ole itse viite, että
ei ole määrittelyksi nimi tähän.
Se olisi vain sanoa typedef struct, avaa kihara ahdin ja sitten määritellä se.
Mutta jos olet struct on itsenäinen viite, koska tämä on,
sinun täytyy määrittää väliaikainen tyypin nimi.
Mutta lopulta, nyt että olemme tehneet tämän,
voimme vain viitata Nämä solmut, nämä yksiköt,
kuten SLL solmut tarkoituksiin muusta tämän videon.
>> Selvä, joten osaamme luoda linkitetyn listan solmu.
Tiedämme miten määritellä linkitetyn listan solmu.
Nyt, jos aiomme aloittaa käyttää niitä kerätä tietoa,
siellä on pari toiminnassamme täytyy ymmärtää ja työskennellä.
Meidän täytyy tietää, miten luoda linkitetty lista tyhjästä.
Jos ei ole luettelo jo, haluamme aloittaa yksi.
Joten meidän on pystyttävä luoda linkitetty lista,
meidän on luultavasti etsiä kautta linkkilista
löytää elementti etsimme.
Meidän täytyy pystyä lisätä uusia asioita listaan,
haluamme luettelo pystyä kasvamaan.
Ja samalla haluamme pystyä poistaa asioita listalta,
haluamme luettelo pystyä kutistua.
Ja lopussa meidän ohjelmat, erityisesti
Jos muistatte, että olemme dynaamisesti jaetut muisti
rakentaa nämä luettelot tyypillisesti, haluamme vapauttaa kaikki tämä muisti
kun olemme tehneet työtä se.
Ja niin meidän täytyy pystyä poistamaan koko linkitetty lista yhdellä epäonnistua syöksy.
Joten mene läpi jotkut näistä toiminnoista
ja kuinka voisimme visualisoida niitä, puhuu pseudokoodilla koodi erityisesti.
Joten haluamme luoda linkitetty lista, joten ehkä me
haluat määrittää funktion tämän prototyyppi.
SLL solmu tähti, luoda, ja olen ohimennen yksi argumentti, jotkut mielivaltaista dataa
tyyppi jälleen, joidenkin mielivaltaista tietojen tyyppi.
Mutta olen returning-- tämän toiminnon pitäisi palata minulle osoitin, että yksittäin
linkitetty lista solmu.
Jälleen me yritämme luoda linkitetty lista tyhjästä,
joten minun täytyy osoitin että luettelosta, kun olen valmis.
>> Mitkä ovat vaiheista täällä?
No, ensimmäinen asia olen aikoo tehdä on dynaamisesti
jakaa tilaa uusi solmu.
Jälleen Luomme se tyhjästä ilma, joten meidän on malloc tilaa se.
Ja tietenkin, heti kun olemme malloc,
aina varmista, että meidän pointer-- emme saaneet takaisin null.
Koska jos yritämme kunnioitus nollaosoittimen,
aiomme kärsiä segfault ja emme halua että.
>> Sitten haluamme täyttää alalla, haluamme alustaa arvon alalla
ja alustaa seuraavaan kenttään.
Ja sitten me haluamme to-- lopulta kuin toiminto prototyyppi indicates-- haluamme
palata osoitin SLL solmuun.
Joten mitä tehdä tämä näyttää visuaalisesti?
No, ensimmäinen aiomme dynaamisesti jakaa tilaa uuden SLL solmu,
joten malloc-- se visuaalinen esitys
solmun me juuri luotu.
Ja me varmista se ei ole null-- tässä tapauksessa,
kuva ei olisi saapunut jos se oli tyhjä,
olisimme loppuu muisti, joten olemme hyvä mennä sinne.
Joten nyt olemme vaiheeseen C, alustaa solmut arvo kenttään.
No, joka perustuu tämä toiminto soittaa Käytän tässä,
näyttää haluan välittää 6, niin minä 6 arvokentässä.
Nyt alustaa seuraavaan kenttään.
No, mitä aion tehdä siellä, ei ole mitään vieressä, oikealla,
tämä on ainoa asia luettelossa.
Niin mitä seuraavaksi asia listassa?
>> Se pitäisi ei viitannut mihinkään, oikealle.
Ei ole mitään muuta siellä, niin mikä on käsite tiedämme se nothing--
viitteitä mitään?
Sen pitäisi olla ehkä haluamme laittaa nollaosoittimen siellä,
ja minä edustavat null osoittimen juuri punainen laatikko,
emme voi mennä pidemmälle.
Kuten näemme hieman myöhemmin, saamme lopulta ketjut
nuolia yhdistää Nämä solmut yhdessä,
mutta kun osut punainen laatikko, joka on null,
emme voi mennä pidemmälle, se luettelon loppuun.
>> Ja lopuksi, me vain haluamme palata osoitin tähän solmuun.
Joten me kutsumme sitä uutta, ja palaa uuden
joten sitä voidaan käyttää mitä toimintoa luonut.
Joten siellä mennään, Olemme luoneet yksittäin linkitetty lista solmu tyhjästä,
ja nyt meillä on lista voimme työskennellä.
>> Nyt, sanokaamme meillä jo on suuri ketju,
ja haluamme löytää jotain se.
Ja haluamme toiminto, joka menee palata tosi tai epätosi riippuen
onko arvo on olemassa kyseisessä luettelossa.
Toiminto prototyyppi, tai ilmoituksen, että toiminto,
voisi näyttää this-- bool löytää, ja sitten haluamme kulkea kaksi perustelua.
>> Ensimmäinen, on osoitin ensimmäinen osa linkitetyn listan.
Tämä on todella jotain sinun aina haluavat seurata,
ja itse asiassa voi olla jotain, joka edes laittaa globaali muuttuja.
Kun olet luonut listan, aina, aina
haluavat seurata hyvin ensimmäinen osa luettelosta.
Näin voit viitata kaikki muut elementit vain seuraava ketjun,
ilman pitää viitteitä ehjä jokaiseen elementtiin.
Sinun tarvitsee vain seurata ensimmäisen yksi jos he kaikki ketjuttaa.
>> Ja sitten toinen asia olemme ohimennen uudelleen
on mielivaltaisesti some-- mitä tietotyyppi olemme
etsivät siellä on sisällä toivottavasti yksi solmujen luetteloon.
Mitä ovat vaiheet?
No, ensimmäinen asia mitä teemme on luomme poikittainen osoitin
osoittaa luetteloihin päähän.
No, miksi me teemme, että olemme jo on osoitin luettelot pään,
miksi emme siirrä että yksi noin?
No, kuten juuri sanoin, se on todella tärkeää meille
aina seurata ensimmäinen elementti luettelosta.
Ja niin se on itse asiassa parempi luoda päällekkäisiä kyseisen,
ja käyttää sitä liikkua niin emme koskaan vahingossa siirtää pois, tai aina
on osoitin jossain vaiheessa, että on aivan ensimmäinen osa luettelosta.
Joten on parempi luoda toisessa, että käytämme liikkua.
>> Sitten vain vertailla, onko arvo kentän että solmu
on mitä etsimme, ja jos se on ei, me vain siirry seuraavaan solmuun.
Ja me pitää tehdä, että yli, ja yli, ja yli,
kunnes joko löytää elementti, tai me osuma
null-- olemme päättynyt luettelon ja se ei ole siellä.
Tämä toivottavasti tutulta sinulle vain lineaarinen haku,
me vain jäljittelevän sitä yksittäin linkitetyn listan rakenne
käyttämisen sijaan array tehdä se.
>> Joten tässä on esimerkki yksittäin linkitetyn listan.
Tämä yksi koostuu viisi solmua, ja meillä on
osoitin johtaja luettelo, jota kutsutaan lista.
Ensimmäinen asia, jota haluamme tehdä, on jälleen, luoda että kulkea osoitin.
Joten meillä on nyt kaksi osoitinta että kohta sama asia.
>> Nyt, huomaa tässä myös, en on malloc mitään tilaa Trav.
En sanonut Trav vastaa malloc jotain, joka solmu on jo olemassa,
että muistitilaa on jo olemassa.
Joten kaikki Olen todella tekee on luomalla uuden osoitin sen.
En mallocing lisää tilaa, vain nyt kaksi osoitinta
osoittaa sama asia.
>> Joten on 2 mitä etsin?
No, ei, joten sen sijaan olen aikoo siirtyä seuraavaan.
Joten periaatteessa sanoisin, trav vastaa trav seuraava.
On 3 mitä etsin, ei.
Joten olen edelleen mennä kautta, kunnes lopulta
saada 6, joka on mitä etsin sillä perusteella funktiokutsua
Minulla on huipulla siellä, ja niin olen valmis.
>> Nyt, mitä jos elementti olen etsimässä ei ole luettelossa,
Onko se vielä menossa töihin?
No, huomaa, että luettelo tässä hieman toisenlainen,
ja tämä on toinen asia, joka on tärkeää liittyvät luettelot,
sinun ei tarvitse säilyttää niitä missään tietyssä järjestyksessä.
Voit, jos haluat, mutta olet ehkä jo huomannut
että emme pitää kirjaa mitä numero elementti olemme.
>> Ja se on eräänlainen yhden kaupan me on kanssa linkitetty lista säkeet paneelit,
se meillä ei ole random access enää.
Emme voi vain sanoa, haluan mennä 0. elementti,
tai 6. osa minun array, jota voin tehdä array.
En voi sanoa haluan mennä 0. elementti, tai 6. elementti,
tai 25. osa minun linkitetty lista, ei ole indeksiä niihin liittyviä.
Ja niin se ei ole oikeastaan ​​väliä jos säilytämme lista järjestyksessä.
Jos haluat sinua varmasti voi, mutta siellä on
mitään syytä, miksi ne tarvitsevat säilytettävä missä tahansa järjestyksessä.
Joten jälleen, yritetään ja löytää 6 tässä luettelossa.
No, me alkavat alkaa, emme löydä 6,
ja sitten jatkamme ei löytää 6, kunnes me lopulta päästä tänne.
Joten nyt trav pistettä solmuun sisältävät 8, ja kuusi ei ole siellä.
>> Niin seuraava askel olisi Siirry seuraavaan osoitin,
niin sanoa trav vastaa Trav seuraava.
No, trav seuraavaksi, merkitty punainen laatikko siellä, on nolla.
Joten ei muuta paikkaa minne mennä, ja niin tässä vaiheessa
voimme päätellä, että olemme saavuttaneet loppuun linkitetyn listan,
ja 6 ei ole siellä.
Ja se olisi palautettava väärä tässä tapauksessa.
>> OK, miten voimme lisätä uuden solmun linkitetty lista?
Joten olemme pystyneet luomaan linkitetty lista tyhjästä,
mutta me luultavasti halua rakentaa ketju eikä
luoda joukko erillisiä listoja.
Haluamme olla yksi luettelosta on joukko solmuja se,
ei nippu luettelot yhden solmun.
Joten emme voi vain pitää käyttämällä Luo toiminto määrittelimme aikaisemmin, nyt meillä
haluat lisätä osaksi luettelo jo olemassa.
>> Joten tässä tapauksessa, menemme kulkea kaksi argumenttia,
osoitin johtaja, joka linkitetty lista, että haluamme lisätä.
Jälleen siksi se on niin tärkeää, että aina
seurata sitä, koska se on ainoa tapa, jolla voimme todella
täytyy viitata koko lista on vain osoitin ensimmäinen osa.
Joten haluamme kulkea Osoitin, että ensimmäinen elementti,
ja arvosta riippumatta me haluavat lisätä luetteloon.
Ja lopulta tämä toiminto aikoo palata osoitin
jotta uusi johtaja linkitetyn listan.
>> Mitä vaiheita mukana täällä?
No, aivan kuten luoda, meidän on dynaamisesti varata
tilaa uusi solmu, ja tarkista, varma emme lopu muisti, jälleen,
koska käytämme malloc.
Sitten haluamme asuttaa ja aseta solmu,
niin laita numero riippumatta val on, osaksi solmu.
Haluamme lisätä solmun alussa linkitetyn listan.
>> On syy, että olen halua tehdä tätä, ja se
voisi olla hyvä ottaa toinen Keskeytä video tästä,
ja miettiä, miksi en haluaisi lisätä alussa linkitetyn
lista.
Jälleen mainitsin aiemmin että se ei ole oikeastaan
merkitystä, me säilyttää sitä millään järjestys, joten ehkä se vihje.
Ja näit mitä tapahtuisi, jos me halusi to-- tai vain toinen
sitten kun olimme menossa haun kautta voit
voisi nähdä, mitä voisi tapahtua, jos yritimme
lisätä lopussa luettelosta.
Koska meillä ei ole Osoitin listan loppuun.
>> Niin siitä syystä, että haluaisin lisätä alussa,
on koska voin tehdä sen heti.
Minulla osoitin alussa, ja näemme tämän visuaalisen toisessa.
Mutta jos haluan lisätä lopussa, Minun täytyy aloittaa alusta,
kulkea aina end, ja sitten tack se.
Niin se tarkoittaisi että työntämällä lopussa luettelo
tulisi o n toiminta, menee takaisin
meidän keskustelua laskennallinen monimutkaisuus.
Se olisi tullut o n toimintaa, jossa kuten luettelon sai isompi, ja isompi,
ja isompi, siitä tulee yhä vaikeampi tack jotain
on lopussa.
Mutta se on aina todella helppoa tack jotain alussa,
olet aina alussa.
>> Ja näemme visuaalinen tämän uudelleen.
Ja sitten kun olemme tehneet, kun olemme lisätään uusi solmu,
haluamme palata meidän osoitin uusi johtaja linkitetty lista, joka
koska olemme lisäämällä at alussa, todella on
osoitin solmuun me juuri luotu.
Katsotaanpa visualisoida, koska mielestäni se auttaa.
>> Joten tässä on meidän lista, se koostuu neljä elementtiä, solmu sisältää 15,
mikä viittaa solmuun jotka sisältävät 9, joka
viittaa solmuun, joka sisältää 13, mikä viittaa solmun sisältävä
10, joka on nolla- osoitin sen ensi osoitin
niin se luettelon loppuun.
Joten haluamme lisätä uusi solmu kanssa arvo 12
alussa tämän lista, mitä teemme?
No, ensin meidän malloc tilaa solmu, ja sitten laitamme 12 siellä.
>> Joten nyt olemme saavuttaneet päätös, eikö?
Meillä on pari viitteitä, että voisimme
liikkua, kumpi meidän pitäisi siirtyä ensin?
Pitäisikö meidän tehdä 12 kohta uusi johtaja list--
tai anteeksi, meidän pitäisi tehdä 12 viittaavat vanha pää listan?
Vai pitäisikö sanoa, että Listassa on nyt alkaa 12.
On ero siellä, ja me tutustumme
mitä tapahtuu sekä toisessa.
>> Mutta tämä johtaa suuri aihe sivupalkin,
joka on, että yksi vaikeimpia asioita liittyvät luettelot
on järjestää viitteitä oikeassa järjestyksessä.
Jos muutat asioita epäkunnossa, voit päätyä vahingossa
orpoutumista loput luettelon.
Ja tässä on esimerkki tästä.
Joten mennä ajatus of-- No, olemme juuri luotu 12.
Tiedämme 12 tulee olemaan uusi johtaja luettelo,
ja niin miksi emme siirrä luettelon osoitin kohtaan siellä.
>> OK, niin se on hyvä.
Joten nyt jos ei 12 seuraava kohta?
Tarkoitan, visuaalisesti voimme nähdä että se tulee kohta 15,
kuin ihmisillä se on todella selvää meille.
Miten tietokone tietää?
Meillä ei ole mitään osoittaen 15 enää, eikö?
>> Olemme menettäneet kyvyn viitata 15.
Emme voi sanoa uusia nuolta tasavertaisten jotain, ei ole mitään siellä.
Itse asiassa, olemme orvoiksi loput luettelon
tekemällä niin, olemme vahingossa rikki ketju.
Ja emme missään nimessä halua tehdä sitä.
>> Joten mennään takaisin ja kokeile tätä uudelleen.
Ehkä oikein on asettaa 12 seuraava osoitin
vanha johtaja listan ensimmäinen, sitten voimme siirtyä listan yli.
Ja itse asiassa, että on oikeassa järjestyksessä, että me
täytyy seurata, kun olemme työskennellä yksin linkitetyn listan.
Haluamme aina yhdistää uusi elementti listaan,
ennen kuin ryhdymme tuollaisen tärkeä askel muuttaa
jossa pää linkitetyn listan on.
Tämäkin on niin perustavanlaatuinen asia, emme halua menettää seurata sitä.
>> Joten haluamme varmistaa, että kaikki on ketjuttaa,
ennen kuin siirrymme että osoitin.
Ja niin tämä olisi oikeassa järjestyksessä, joka on kytkeä 12 listalle
sitten sanoa, että luettelo alkaa 12.
Jos me sanoi luettelo alkaa 12 ja sitten yrittänyt liittää 12 listalle
olemme jo nähneet, mitä tapahtuu.
Menetämme lista vahingossa.
>> OK, joten yksi asia puhua.
Mitä jos haluamme päästä eroon koko linkitetty lista kerralla?
Jälleen olemme mallocing kaikki tämä tila, ja niin me
täytyy vapauttaa, kun olemme tehneet.
Joten nyt haluamme poistaa koko linkitetyn listan.
No, mitä haluamme tehdä?
>> Jos olemme saavuttaneet nollaosoittimen, me halua lopettaa, muuten vain poistaa
loput luettelosta ja sitten vapauta minut.
Poistaa loput luettelon, ja sitten vapauttaa nykyisen solmun.
Mitä se kuulostaa, mitä tekniikkaa on puhuimme
noin aiemmin Kuulostaako?
Poista kaikki muutkin, niin palata ja poistaa minut.
>> Se rekursio, olemme tehneet ongelma hieman pienempi,
sanomme poistaa kaikki muuten, niin voit poistaa minut.
Ja edelleen tiellä, että solmu sanovat, poistaa kaikki muutkin.
Mutta lopulta me saamme kohdassa, jossa luettelo on tyhjä,
ja se on meidän perustapaus.
>> Joten katsomaan tämän, ja miten tämä voisi toimia.
Joten tässä on meidän lista, se on sama luetella me vain puhumme,
ja siellä vaiheet.
Siellä on paljon tekstiä täällä, mutta toivottavasti visualisointi auttaa.
>> Joten me have-- ja olen myös vetänyt jopa meidän pino kehyksiä kuva
meidän video soittaa pinoja, ja toivottavasti kaikki tämän
yhdessä näyttää mitä tapahtuu.
Joten tässä on meidän pseudokoodilla koodi.
Jos pääsemme null osoitin, stop, muuten,
poistaa loput luettelon, sitten vapauttaa nykyisen solmun.
Joten juuri nyt, list-- osoitin, että olemme
kulkee tuhota pistettä 12.
12 ei nollaosoittimen, joten olemme menossa poistaa loput luettelon.
>> Mikä on poistaa me muut mukana?
No, se tarkoittaa tehtävien soita tuhota, sanoi
että 15 on alku Loput luettelon haluamme tuhota.
Ja niin puhelu tuhota 12 on eräänlainen pidossa.
Se on jäädytetty siellä, odottamassa soita tuhota 15, loppuun työnsä.
>> No, 15 ei ole nollaosoittimen, ja joten se tulee sanoa, okei,
hyvin, poistaa loput luettelon.
Loput luettelo alkaa klo 9, ja niin me vain
odota kunnes poistat kaikki että kamaa, sitten tulevat takaisin ja poistaa minut.
No 9 tulee sanoa, hyvin, En ole nollaosoittimen,
joten poista loput listan täältä.
Ja niin kokeile ja tuhota 13.
13 sanoo, en ole nollaosoittimen, sama asia, se kulkee pukki.
10 ei nollaosoittimen, 10 sisältää nollaosoittimen,
mutta 10 ei itse nollaosoittimen juuri nyt,
ja niin se kulkee pukki liian.
>> Ja nyt luetella pistettä siellä, se todella osoittaisi some--
jos minulla olisi enemmän tilaa kuva, se osoittaa joitakin satunnaisia ​​tilaa
että emme tiedä mitä se on.
Se on tyhjän osoittimen kuitenkin, luettelo on kirjaimellisesti nyt asetettu se arvoja null.
Se osoittaa oikealle sisällä että punainen laatikko.
Pääsimme nollaosoittimen, joten voimme lopettaa, ja olemme tehneet.
>> Ja jotta violetti kehys on now-- klo päälle stack-- se aktiivinen kehys,
mutta se on tehty.
Jos olemme saavuttaneet nollaosoittimen, lopeta.
Emme tee mitään, me ei saa nollaosoittimen,
emme malloc mitään tilaa, ja niin olemme tehneet.
Jotta toiminto kehys tuhotaan, ja me
resume-- haemme jossa jätimme pois seuraavaksi korkein, joka
on tämä tummansininen runko täällä.
Joten me poimia oikea mihin jäimme.
Poistimme loput luettelo jo, joten nyt olemme
menossa vapauttaa nykyisen solmut.
Joten nyt voimme vapauttaa tämän solmun, ja nyt olemme lopussa funktion.
Ja niin että toiminta kehys on tuhottu, ja me poimia vaaleansininen yksi.
>> Joten se says-- olen jo done-- poistetaan loput listan, niin
vapauttaa nykyisen solmun.
Ja nyt keltainen kehys on takaisin pinon.
Ja niin näette, olemme nyt tuhoaa listan oikealta vasemmalle.
>> Mitä olisi tapahtunut, vaikka, jos olisimme tehneet asiat väärin?
Aivan kuten kun yritimme lisätä elementin.
Jos me sekaisin ketju, jos emme yhdistä viitteitä
oikeassa järjestyksessä, jos me vain vapautti ensimmäinen elementti,
jos me vain vapautti johtaja luettelon, nyt meillä
ei ole tapa viitata loput luettelon.
Ja niin meillä olisi orvoksi kaiken,
meillä olisi ollut mitä kutsutaan muisti vuotaa.
Jos muistatte meidän video dynaaminen muistin jakamista,
se ei ole kovin hyvä asia.
>> Joten kuten sanoin, siellä useita toimintoja
että meidän on käytettävä töihin kanssa linkitetty lista tehokkaasti.
Ja olet ehkä huomannut minä pois yksi, poistaa yksittäinen elementti liittyy
lista.
Syy Tein että on se oikeastaan ​​eräänlainen
hankala miettiä, miten poistaa yksittäinen elementti yksittäin
linkitetty lista.
Meidän täytyy pystyä ohittaa yli jotain luettelossa, joka
tarkoittaa saamme point-- me Poistetaanko node--
mutta jotta niin me älä hävitä tietoja,
Meidän täytyy liittää tähän solmu tänne, täällä.
>> Olen siis luultavasti teki sitä väärin ulkoasut keskenään.
Joten olemme alussa meidän lista, olemme etenee läpi,
haluamme poistaa tämän solmuun.
Jos me vain poistaa sen, olemme rikki ketju.
Tämä solmu täällä viittaa kaikki muu,
se sisältää ketjun täällä ulos.
>> Joten mitä meidän pitää tehdä todella kun olemme päästä tähän pisteeseen,
on meidän askel taaksepäin yksi, ja liitä tämä solmu yli tämän solmun,
jotta voimme sitten poistaa yksi keskellä.
Mutta yksittäin liittyy Luettelot eivät meille tie taaksepäin.
Joten meidän täytyy joko pitää kaksi osoitinta, ja siirtää ne
tavallaan pois askel, yksi takana muut kuin menemme, tai saada pisteeseen
ja sitten lähettää toisen osoitin kautta.
Ja kuten näette, se voi saada hieman sotkuinen.
Onneksi meillä on toinen tapa ratkaista että,
kun puhumme kaksin verroin linkitetty luetteloista.
>> Olen Doug Lloyd, tämä on CS50.