[Powered by Google Translate] Í forritun, þurfum við oft að tákna lista af gildum,
svo sem nöfn nemenda í kafla
eða frammistöðu þeirra á síðustu spurningakeppni.
>> Í C tungumál, lýsti fylki er hægt að nota
að geyma lista.
Það er auðvelt að telja upp þætti lista
geymd í fylki, og ef þú þarft að fá aðgang
eða breyta ith lista þáttur
fyrir sumir handahófi vísitölu I,
sem hægt er að gera í föstu tíma,
en fylki hafa ókosti líka.
>> Þegar við lýsa þeim, erum við að þurfa að segja
upp að framan hversu stór þau eru,
það er, hversu margir þættir sem þeir geta geymt
og hversu stór þessir þættir eru, sem ræðst af gerð þeirra.
Til dæmis, int Arr (10)
getur geymt 10 atriði
sem eru á stærð við heiltala.
>> Við getum ekki breytt stærð fylki eftir að yfirlýsingu.
Við verðum að gera nýjan array ef við viljum geyma fleiri atriði.
Ástæðan þessi takmörkun er að okkar
program geymir alla array
sem samfelldu klumpur af minni.
Segja þetta er biðminni þar geymdar í array okkar.
Það gæti verið aðrar breytur
staðsett rétt við hliðina á fjölda
í minni, þannig að við getum ekki
bara gera array stærri.
>> Stundum viljum við eiga viðskipti fljótur gögn fylki er aðgangur hraði
fyrir smá meiri sveigjanleika.
Sláðu tengda lista, annar undirstöðu gögn uppbygging
þú getur ekki verið eins kunnugur.
Á háu stigi,
a tengda listanum geymir gögn í röð hnúta
sem eru tengd við hvert annað með tenglum,
þess vegna the nafn "tengda listanum."
Eins og við munum sjá, þessi munur á hönnun
leiðir til mismunandi kostum og göllum
en fylki.
>> Villutrú 'sumir C kóða fyrir mjög einfalt tengd lista heiltölur.
Þú getur séð að við höfum fulltrúa hver hnútur
í skránni sem strúktúr sem inniheldur 2 hluti,
heiltala að geyma kallast "Val '
og tengill á næsta hnút á listanum
sem við komum fram sem bendill sem heitir "næst."
Þannig getum við fylgst með öllu lista
með aðeins einn bendi á 1 hnút,
og þá getum við fylgst með næsta ábendingum
til 2. hnút,
á 3. hnút,
til 4. hnút,
og svo framvegis, þar til við fá til the endir af the listi.
>> Þú might vera fær til að sjá 1 kostur það hefur
yfir truflanir array uppbyggingu - með tengda lista,
við þurfum ekki að stór klumpur af minni öllu.
The 1. hnútur á listanum gæti lifað á þessum stað í minni,
og 2. hnút gæti verið alla leið hérna.
Við getum fengið að öllum hnúður sama hvar í minni sem þeir eru,
því að byrja á 1 hnút, næsta músina hver hnútur er
segir okkur nákvæmlega hvar á að fara næst.
>> Auk þess höfum við ekki að segja upp fyrir framan
hversu stór tengdur listi vilja vera the vegur við gera við truflanir fylki,
þar sem við getum haldið áfram að bæta hnút við lista
svo lengi sem það er pláss einhvers staðar í minni fyrir nýjum hnúður.
Því eru tengdir listar auðvelt að búa virk.
Segja, síðar í áætluninni sem við þurfum að bæta við fleiri hnútar
í listanum okkar.
Til að setja inn nýjan hnút í listanum okkar á flugu,
allt sem við þurfum að gera er að úthluta minni fyrir að hnút,
plop í gögn gildi,
og þá setja það sem við viljum með því að breyta viðeigandi ábendingum.
>> Til dæmis, ef við vildum að setja hnút á milli
2. og 3. hnútar á listanum,
við myndum ekki þurfa að færa 2 eða 3 hnúður yfirleitt.
Segja að við erum að setja þetta rauða hnút.
Allt sem við myndum þurfa að gera er að setja næstu músina nýju hnút á
að benda á 3. hnút
og þá rewire næstu músina 2. Hnútur er
að benda á nýja hnút okkar.
Svo getum við breyta listum okkar á flugu
þar sem tölvan okkar er ekki að treysta á flokkun,
heldur á að tengja með ábendingum til að geyma þá.
>> Hins vegar ókostur tengdir listar
er að ólíkt kyrrstæða fylking,
tölvan getur ekki bara hoppa á miðjum listanum.
Þar sem tölvan er að heimsækja hvern hnút í tengda listanum
til að fá til the næstur einn,
það er að fara að taka lengri tíma til að finna tiltekna hnút
en það væri í fylki.
Til að fara yfir allt listi tekur tíma hlutfalli
að lengd á listanum,
eða O (n) í asymptotic merki.
Að meðaltali ná hvaða hnút
einnig tekur tíma í réttu hlutfalli við n.
>> Nú, við skulum í raun að skrifa nokkur númer
sem virkar með tengd listum.
Segjum að við viljum tengd lista yfir heiltölur.
Við getur táknað hnút í lista okkar aftur
sem strúktúr með 2 sviðum,
heiltala gildi kallast "Val '
og næsta bendi á næsta hnút á listanum.
Jæja virðist nógu einfalt.
>> Segjum að við viljum að skrifa fall
sem traverses listanum og prentar út
gildi sem eru geymdar í síðustu hnút listanum.
Jæja, það þýðir að við þurfum að fara yfir alla hnúta á listanum
að finna það síðasta, en þar sem við erum ekki að bæta
eða eyða neitt, gera við viljum ekki að breyta
innri uppbyggingu næstu ábendingum á listanum.
>> Svo þurfum við að fá bendi sérstaklega fyrir traversal
sem við munum kalla "vefskriðillinn.
Það mun skríða í gegnum alla þætti listanum
með því að fylgja keðju næstu ábendingum.
Allt sem við höfum geymt er bendi á 1 hnút,
eða "höfuð" af listanum.
Head bendir á 1. hnút.
Það er af gerðinni músina til hnút.
>> Til að fá raunverulegan 1 hnút á listanum,
við verðum að dereference þetta bendi,
en áður en við getum dereference það, þurfum við að athuga
Ef bendillinn er núll fyrst.
Ef það er núll, sem er tómur,
og við ættum að prenta út skilaboð að þar sem listinn er tómur,
Það er ekkert síðasta hnút.
En, segja skulum listinn er ekki tómur.
Ef það er ekki, þá ættum við að skríða í gegnum allt lista
þangað til við komum að síðasta hnút á listanum,
og hvernig getum við sagt ef við erum að horfa á síðasta hnút í listanum?
>> Jæja, ef næsta músina hnúturinn er núll,
við vitum að við erum í lok
síðan síðasta næsta bendillinn hefði ekki næstu hnút í listanum til að benda á.
Það er gott að alltaf að halda næstu músina þau síðast Hnútur er frumstilla að null
að hafa staðlað eign sem tónar okkur þegar við höfum náð að listanum er lokið.
>> Svo, ef vefskriðillinn → Næst er núll,
muna að örin setningafræði er flýtileið fyrir dereferencing
bendi til strúktúr, þá aðgang
næsta reit hennar jafngildir óþægilega:
(* Beltum). Næst.
Þegar við höfum fundið síðustu hnút,
við viljum prenta vefskriðillinn → Val,
gildi í núverandi hnút
sem við vitum er það síðasta.
Annars, ef við erum ekki enn á síðasta hnút í skránni,
við verðum að fara í næsta hnút á listanum
og athuga hvort það er sá síðasti.
Til að gera þetta, setjum bara vefskriðillinn músina okkar
að benda á næsta gildi núverandi hnút á,
það er næsta hnút á listanum.
Þetta er gert með því að setja
vefskriðillinn = vefskriðillinn → næst.
Þá erum við að endurtaka þetta ferli, með lykkju til dæmis,
þar er að finna síðasta hnút.
Svo, til dæmis, ef vefskriðillinn var að benda á höfuð,
við setjum vefskriðillinn að benda á vefskriðillinn → næst,
sem er það sama og næsta sviði 1. hnút.
Svo, nú vefskriðillinn okkar bendir til 2. hnút,
og aftur, endurtaka við þetta með lykkju
fyrr en við höfum fundið síðustu hnút, það er,
þar næsta músina hnúturinn er benda null.
Og þar sem við höfum það,
Við höfum fundið síðustu hnút í listanum, og að prenta gildi þess,
við notum bara vefskriðillinn → Val.
>> Fara yfir er ekki svo slæmt, en hvað um að setja?
Lets segja að við viljum að setja heiltala í 4. stöðu
í heiltölu lista.
Það er á milli núverandi 3. og 4. hnúður.
Aftur verðum við að fara yfir lista bara til
fá til 3. þáttur, sá sem við erum að setja eftir.
Svo búum við til vefskriðillinn músina aftur til að fara yfir listann
athuga hvort höfuð músina okkar er núll,
og ef það er ekki, benda vefskriðillinn músina okkar á höfuð hnút.
Svo erum við á 1. frumefni.
Við verðum að fara fram 2 fleiri atriði áður en við getum sett,
þannig að við getum notað til að lykkja
int i = 1; i <3, i + +
og í hverri ítrun í lykkju,
fara vefskriðillinn músina okkar fram um 1 hnútur
með því að athuga hvort næsta reit núverandi Hnútur er núll,
og ef það er ekki, færa vefskriðillinn bendilinn okkar á næsta hnút
því að setja það jafn næstu músina núverandi hnút á.
Svo, þar til lykkja okkar segir að gera það
tvisvar,
við höfum náð 3. hnút,
og þegar vefskriðillinn músina okkar hefur náð hnút eftir
sem við viljum setja inn nýja heiltölu okkar,
hvernig við raunverulega gera the setja?
>> Jæja, nýja heiltölu okkar þarf að vera sett inn í listann
sem hluta af eigin hnút struct þess,
þar sem þetta er í raun röð hnúta.
Svo, við skulum gera nýja bendi til hnút
kallað new_node, '
og setja það til að benda á minni sem við úthluta nú
á hrúga fyrir hnút sig,
og hversu mikið minni þurfum við að úthluta?
Jæja, á stærð við hnút,
og við viljum að setja Val á sínu sviði á heiltölu sem við viljum setja inn.
Segjum, 6.
Nú, hnúturinn inniheldur heiltölu gildi okkar.
Það er líka góð regla að frumstilla næsta reit nýju hnút á
að benda á núll,
en nú hvað?
>> Við verðum að breyta innra skipulagi á listanum
og næstu ábendingum að finna í núverandi lista er
3 og 4 hnútar.
Þar næstu ábendingum ákvarða röð á listanum,
og þar sem við erum að setja nýjan hnút okkar
réttur í the miðja af the listi,
það geta vera a hluti erfiður.
Þetta er vegna þess að muna, tölva okkar
bara veit hvar hnúta á lista
vegna næstu ábendingum geymdar í fyrri hnúður.
Svo ef við misstum alltaf utan um eitthvað af þessum stöðum,
segja með því að breyta einu af næstu ábendingum á listanum okkar,
til dæmis, segjum við breytt
Næst á 3 Hnútur er sviði
að benda á einhvern hnút hérna.
Við myndum vera út af heppni, því við myndum ekki
hafa allir hugmynd um hvar á að finna afganginn af listanum,
og það er augljóslega mjög slæmt.
Svo verðum við að vera mjög varkár um röð
þar sem við stjórna næsta ábendingum okkar við innsetningu.
>> Svo, til að einfalda þetta, skulum segja að
okkar fyrstu 4 hnúður
eru kallaðir A, B, C og D, með örvarnar tákna keðju ábendingum
að tengja hnúður.
Svo þurfum við að setja inn nýjan hnút okkar
á milli hnúður C og D.
Það er mikilvægt að gera það í réttri röð, og ég mun sýna þér hvers vegna.
>> Við skulum líta á rangan hátt til að gera það fyrst.
Hey, við vitum að nýr hnútur hefur að koma rétt eftir C,
þannig að við skulum setja næstu músina c er
að benda á new_node.
Allt í lagi, virðist allt í lagi, höfum við bara að klára allt núna með
gerð næstu músina nýja Hnútur er benda til D,
En bíddu, hvernig getum við gert það?
Það eina sem gæti sagt okkur hvar D var,
var næsta bendill geymd áður í C,
en við rewrote bara að bendi
til að benda á nýjan hnút,
þannig að við höfum ekki lengur neina vísbendingu hvar D er í minni,
og við höfum misst restina af listanum.
Ekki góður yfirleitt.
>> Svo, hvernig við gerum þetta rétt?
Fyrst, benda næstu músina nýja Hnútur er í D.
Nú, bæði nýja hnút og er C næstu ábendingum
vísi til sömu hnút, D,
en það er allt í lagi.
Nú getum við benda næstu músina c er í nýjan hnút.
Svo höfum við gert þetta án þess að tapa neinum gögnum.
Í kóða, C er núverandi hnút
að traversal bendilinn Skrið bendir til,
og D er táknað með hnút bent á næsta reit núverandi hnút á,
eða vefskriðillinn → næst.
Svo fórum við fyrst næstu músina í nýjan hnút á
að benda á vefskriðillinn → næst,
á sama hátt og við sögðum næsta músina new_node er ætti
benda til D á myndinni.
Þá getum við sett næstu músina núverandi hnút á
að nýja hnút okkar,
alveg eins og við þurftum að bíða til að benda C til new_node á teikningunni.
Nú er allt í röð og við ekki missa
utan um öll gögn, og við gátum bara
stafur nýjan hnút okkar í the miðja af the listi
án þess að byggja upp allt hlutur eða jafnvel að breytast hvaða þætti
hvernig við hefðum þurft að með fasta lengd fylkisins.
>> Svo eru tengdir listar undirstöðu, en mikilvægt, dynamic gögn uppbygging
sem hafa bæði kosti og galla
miðað við fylki og önnur gögn uppbygging,
og eins og oft er raunin í tölvunarfræði,
það er mikilvægt að vita hvenær á að nota hvert tól,
svo er hægt að velja rétt tól til hægri starf.
>> Fyrir frekari starfi, reyna að skrifa aðgerðir til
eyða hnúður úr tengda listanum -
Mundu að vera varkár óður í þeirri röð sem þú endurraða
næstu ábendingum þínum til að tryggja að þú missir ekki klumpur af listanum -
eða fall til að telja hnúta í tengda listanum,
eða skemmtilegt, til að snúa röð öllum hnúður í tengda listanum.
>> Ég heiti Jackson Steinkamp, ​​þetta er CS50.