[Powered by Google Translate] Ohjelmoinnissa me usein tarve edustamaan luettelot arvoja,
kuten nimiä opiskelijoiden osiossa
tai niiden tulokset viimeisimmistä tietovisa.
>> C-kielellä, julisti matriiseja voidaan käyttää
tallentaa luetteloihin.
On helppo luetella elementtejä luettelon
tallennetaan array, ja jos haluat käyttää
tai muokata nnen listaelementin
joidenkin mielivaltainen indeksi I,
, joka voidaan tehdä jatkuvasti ajan,
mutta taulukot ovat haittoja, too.
>> Kun me julistamme heille, me tarvitaan sanoa
edessä kuinka suuria ne ovat,
eli kuinka monta elementtiä he voivat tallentaa
ja kuinka suuri nämä tekijät ovat, joka määräytyy niiden tyypin mukaan.
Esimerkiksi, int sov. (10)
voidaan tallentaa 10 kohdetta
, jotka ovat koko int.
>> Emme voi muuttaa taulukon kokoa jälkeen ilmoituksen.
Meidän täytyy tehdä uusi array jos haluamme tallentaa enemmän elementtejä.
Syynä tähän rajoitus on olemassa, että
Ohjelma tallentaa koko joukko
koska yhtenäinen kimpale muistia.
Sano tämä on puskuri jossa tallennetaan myös array.
Saattaa olla muita muuttujia
sijaitsee aivan array
muistiin, joten emme voi
vain tehdä array isompi.
>> Joskus haluaisimme vaihtaa array nopean tietojen käytön nopeus
ja hieman enemmän joustavuutta.
Syötä linkitetty lista, toinen perustiedot rakenne
et ehkä niin tuttu.
Korkealla tasolla,
linkitetty lista tallentaa tietoa sekvenssi solmujen
, jotka on liitetty toisiinsa linkkien
tästä nimi "linkitetty lista."
Kuten näemme, tämä ero suunnittelussa
johtaa erilaisia ​​etuja ja haittoja
kuin array.
>> Seuraavassa joitakin C-koodin hyvin yksinkertainen linkitetty kokonaislukujen lista.
Voit nähdä, että olemme edustettuina kussakin solmussa
luettelossa kuin struct joka sisältää 2 asioita,
kokonaisluku tallentaa kutsutaan Val-
ja linkki seuraavalle solmulle luettelossa
jota edustavat niin osoitin kutsutaan seuraavaksi. "
Näin voimme seurata koko lista
vain yksi osoitin ensimmäinen solmu,
ja sitten voimme seurata ensi osoittimet
että toinen solmu,
on 3rd solmuun,
että neljäs solmu,
ja niin edelleen, kunnes saamme luettelon loppuun.
>> Saatat nähdä 1 etu tämä on
yli staattinen matriisirakenne - jossa linkitetty lista,
Emme tarvitse iso kimpale muistin kokonaan.
1. solmu listaa voisi asua tässä paikassa muistiin,
ja toinen solmu voisi aina tänne.
Voimme saada kaikki solmut missä muistissa ne ovat,
koska alkaen ensimmäinen solmu, kukin solmu seuraava osoitin
kertoo meille täsmälleen, minne mennä seuraavaksi.
>> Lisäksi meillä ei ole sanottavaa edessä
kuinka suuri linkitetty lista on tapamme tehdä staattinen taulukot,
koska voimme pitää lisätä solmuja lista
niin kauan kuin on tilaa jossain muistia uusia solmuja.
Siksi linkitettyjen listojen helppo muuttaa dynaamisesti.
Sano, myöhemmin ohjelmassa meidän täytyy lisätä enemmän solmuja
meidän luetteloon.
Jos haluat lisätä uuden solmun lista lennossa,
kaikki mitä on tehtävä, on varata muistia että solmu,
plop tiedon arvolle,
ja aseta se missä haluamme säätämällä asianmukaisia ​​viitteitä.
>> Esimerkiksi, jos haluamme sijoittaa solmun välillä
2. ja 3. solmujen luettelon,
meillä ei olisi siirtää 2. tai 3. solmuja ollenkaan.
Sano olemme Sijoittamalla tämä punainen solmu.
Meidän täytyisi tehdä asetetaan uusi solmu seuraava osoitin
viitata 3rd solmuun
ja sitten ReWire 2. solmun seuraava osoitin
osoittamaan uuden solmun.
Joten voimme muuttaa meidän luetteloita lennossa
koska meidän tietokone ei luottaa indeksointi,
vaan yhdistää käyttäen osoittimia tallentaa ne.
>> Kuitenkin haittana linkitettyjä listoja
on, että toisin kuin staattinen array,
tietokone voi vain hypätä keskelle luettelon.
Koska tietokone on käydä jokaisen solmuun linkitetyn listan
päästä seuraavaan,
se tulee kestää kauemmin löytää tietty solmu
kuin ne olisivat array.
Kulkemaan koko luettelon vie aikaa verrannollinen
on listan pituus,
tai O (n) asymptoottinen merkintä.
Keskimäärin päästä mihin tahansa solmuun
vie myös aikaa verrannollinen n.
>> Nyt, oikeastaan ​​kirjoittaa joitakin koodi
joka toimii linkitettyjä listoja.
Sanotaan haluamme liittyy kokonaislukujen lista.
Voimme edustaa solmun listalta uudelleen
kuten struct 2 aloilla,
kokonaislukuarvo nimeltään "Val"
ja seuraavan osoittimen seuraavalle solmulle luettelon.
No, näyttää helpolta.
>> Sanotaan haluamme kirjoittaa funktion
joka kulkee listan ja tulostaa
tallennettua arvoa viimeinen solmu luettelon.
No, se tarkoittaa, että meidän täytyy kulkea kaikkien solmujen luettelon
löytää viimeinen, mutta koska emme lisää
tai poistamatta mitään, emme halua muuttaa
sisäistä rakennetta seuraavan viitteitä luettelosta.
>> Joten, me tarvitsemme osoittimen erityisesti läpikäyminen
jonka me kutsumme "crawler."
Se ryömiä läpi kaikki osat luettelon
seuraamalla ketjun seuraavan osoittimia.
Kaikki olemme tallennettu on osoitin 1. solmuun,
tai "johtaja" luettelon.
Head pistettä 1. solmuun.
Se on tyypin osoitin-solmuun.
>> Saadaksesi todelliset ensimmäinen solmu listassa,
meidän on dereference tätä osoitin,
mutta ennen kuin voimme dereference sen, meidän täytyy tarkistaa
Jos osoitin on nolla ensimmäinen.
Jos se on nolla, luettelo on tyhjä,
ja meidän pitäisi tulostaa viestin, että koska lista on tyhjä,
ei ole viimeinen solmu.
Mutta sanokaamme luettelo ei ole tyhjä.
Jos se ei ole, niin meidän pitäisi ryömiä läpi koko luettelon
kunnes pääsemme viimeiseen solmuun luettelon,
ja miten voimme kertoa, jos me tarkastelemme viime solmu luettelossa?
>> No, jos solmu seuraava osoitin on nolla,
tiedämme, että olemme lopussa
koska viimeinen seuraava osoitin ei olisi ensi solmun luettelossa osoittamaan.
On hyvä käytäntö aina pitää viimeisen solmun vieressä osoitin alustetaan null
on standardoitu ominaisuus, joka varoittaa meitä, kun olemme saavuttaneet luettelon loppuun.
>> Joten, jos crawler → seuraava on nolla,
Muista, että nuoli syntaksi on oikotie dereferencing
osoittimen struct, sitten päästä
sen seuraavaan kenttään vastaava kiusallinen:
(* Crawler). Seuraavaksi.
Kun olemme löytäneet viimeisen solmun,
haluamme tulostaa crawler → val-
arvo nykyinen solmu
jonka tiedämme olevan viimeinen.
Muuten, jos emme ole vielä viime solmun luettelossa,
meidän täytyy siirtyä seuraavalle solmulle luettelossa
ja tarkista, jos se on viimeinen.
Voit tehdä tämän, me vain asettaa roboteillemme osoitin
osoittamaan nykyisen solmun seuraavaan arvoon,
joka on, seuraava solmu listassa.
Tämä tehdään asettamalla
crawler = crawler → Seuraava.
Sitten me toistaa tätä prosessia, jossa on silmukka esimerkiksi
kunnes löydämme viimeinen solmu.
Niinpä esimerkiksi, jos crawler oli osoittaen päätä,
asetimme crawler osoittamaan crawler → seuraavaksi
joka on sama kuin seuraavan kentän ensimmäinen solmu.
Joten, nyt meidän crawler osoittaa 2. solmuun,
ja, jälleen kerran me toista, jossa on silmukka,
kunnes olemme löytäneet viimeinen solmu, joka on,
jos solmun seuraava osoitin osoittaa null.
Ja meillä on,
olemme löytäneet viimeisen solmun luettelossa, ja tulostaa sen arvo,
me vain käyttää crawler → Val.
>> Piste ei ole niin paha, mutta entä lisäämällä?
Sanotaan haluamme lisätä kokonaisluvun 4. asemassa
on kokonaisluku luettelossa.
, Joka on välillä nykyisen 3. ja 4. solmut.
Jälleen olemme kulkemaan luetteloon vain
saada kolmas elementti, jota me olemme asetat jälkeen.
Joten luomme crawler osoitin jälleen kulkemaan luetteloon,
tarkista päämme osoitin on nolla,
ja jos se ei ole, osoittaa indeksointirobottimme osoitin pääsolmussa.
Joten me olemme ensimmäinen elementti.
Meidän täytyy mennä eteenpäin 2 enemmän elementtejä ennen kuin voimme lisätä,
joten voimme käyttää varten silmukka
int i = 1; i <3; i + +
ja kunkin iteroinnin silmukan,
etukäteen indeksoijan osoitin eteenpäin 1 solmu
tarkistamalla, jos nykyinen solmu seuraava kenttä on nolla,
ja jos se ei ole, siirrä indeksointirobottimme osoitin seuraavaan solmuun
asettamalla se yhtä kuin sen hetkisen solmun seuraava osoitin.
Joten, koska meidän on silmukka sanoo tehdä, että
kahdesti,
olemme saavuttaneet 3. solmu,
ja kun indeksointirobottimme osoitin on saavuttanut solmun jälkeen
jonka haluamme lisätä uuden kokonaisluku,
miten me oikeastaan ​​tehdä työntämällä?
>> No, uusi kokonaisluku on lisätty luetteloon
osana omaa solmun struct,
koska tämä on todella sekvenssi solmuja.
Joten, tehkäämme uusi osoittimen solmuun
nimeltään "new_node, '
ja aseta se osoittamaan muistin että nyt jakaa
kasaan ja solmu itse,
ja kuinka paljon muistia meidän tarvitse varata?
Hyvin, koko solmun,
ja haluamme asettaa sen Val kenttä kokonaisluku, että haluamme lisätä.
Sanotaan, 6.
Nyt solmu sisältää myös kokonaisluku.
On myös hyvä käytäntö alustaa uuden solmun seuraavaan kenttään
viitata null,
mutta mitä nyt?
>> Meidän täytyy muuttaa sisäistä rakennetta luettelon
ja seuraava osoittimet sisältyvät luetteloon nykyisen
3. ja 4. solmuja.
Koska seuraava osoittimet määrittää luettelon järjestystä,
ja koska olemme laittamalla uuden solmun
oikealle keskelle luettelon
Se voi olla vähän hankala.
Tämä johtuu siitä, muistan, meidän tietokone
tuntee vain sijainti solmujen luetteloon
koska seuraavan osoittimien tallennettu aiempien solmujen.
Joten, jos me joskus kadottaa kaikista näistä paikoista,
sanovat muuttamalla yhden seuraavan viitteitä listallamme,
esimerkiksi sanoa muutimme
3. solmun seuraavaan kenttään
osoittamaan joitakin solmuun tänne.
Olisimme epäonninen, koska ei olisi
mitään käsitystä mistä loput luettelon
ja se on tietysti todella huono.
Joten meidän on oltava todella varovainen, jotta
jossa me manipuloida meidän seuraava viitteitä asettamisen aikana.
>> Joten, yksinkertaistaa tätä, sanotaanko, että
ensimmäinen 4 solmua
kutsutaan A, B, C ja D, joissa nuolet edustavat ketjun osoittimia
joka yhdistää solmut.
Joten meidän täytyy lisätä uusi solmu
välillä solmujen C ja D.
On tärkeää tehdä se oikeassa järjestyksessä, ja minä näytän sinulle miksi.
>> Katsokaamme väärä tapa tehdä se ensin.
Hei, me tiedämme uusi solmu on tultava heti C,
joten katsotaanpa asettaa C: n seuraava osoitin
osoittamaan new_node.
Okei, näyttää okei, meidän täytyy vain viimeistellä nyt by
jolloin uusi solmu seuraava osoitin pisteen D,
Mutta hetkinen, miten voimme tehdä sen?
Ainoa asia, joka voisi kertoa meille, missä D oli,
oli seuraava osoitin aiemmin tallennettu C,
mutta me vain rewrote että osoitin
osoittamaan uusi solmu,
joten meillä ei ole enää hajuakaan missä D on muistissa,
ja olemme menettäneet loput luettelosta.
Ei hyvä ollenkaan.
>> Joten, miten teemme tätä oikeutta?
Ensinnäkin, kohta uuden solmun seuraava osoitin D.
Nyt sekä uuden solmun n ja C: n seuraavan osoittimia
osoittavat samaan solmuun, D,
mutta se on hieno.
Nyt voimme osoittaa C: n vieressä osoitin uuteen solmuun.
Niin, olemme tehneet tämän menettämättä mitään tietoja.
Koodin, C on nykyinen solmu
että läpikäynti osoitin crawler osoittaa,
ja D edustaa solmun osoittamat senhetkisen solmun seuraavaan kenttään
tai telaketjuilla → Seuraava.
Joten me ensin uuden solmun seuraava osoitin
viitata crawler → seuraavaksi
samoin sanoimme new_node seuraava osoitin tulisi
viittaavat D kuvassa.
Sitten voimme asettaa nykyisen solmun seuraava osoitin
meidän uusi solmu,
aivan kuten jouduimme odottamaan pisteeseen C new_node piirustuksessa.
Nyt kaikki on kunnossa, ja emme menetä
Seuraa mitään tietoja, ja pystyimme vain
kiinni meidän uusi solmu keskellä luettelon
ilman uudelleenrakentaminen koko juttu tai jopa siirtää kaikki elementit
miten meidän olisi pitänyt kanssa samanpituisia array.
>> Joten linkitettyjen listojen ovat perus, mutta tärkeä, dynaaminen tietorakenne
joka on sekä etuja että haittoja
verrattuna paneelit ja muiden tietorakenteiden,
ja kuten usein tietotekniikassa,
on tärkeää tietää, milloin kutakin työkalua,
joten voit valita oikea väline oikeaan työhön.
>> Lisätietoja Käytännössä yrittää kirjoittaa toimintoja
Poista solmut linkitetty lista -
Muista olla varovainen missä järjestyksessä voit järjestää
seuraava osoittimia, jotta et menetä kimpale listasi -
tai toiminto laskea solmut linkitetty lista,
tai hauska yksi, kääntää järjestyksessä kaikki solmut on linkitetty lista.
>> Nimeni on Jackson Steinkamp, ​​tämä on CS50.