[Powered by Google Translate] Programmeerimise, me sageli vaja esindada väärtuste loetelusid,
nagu nimed õpilaste osa
või nende hinded hiljemalt viktoriini.
>> C-keeles, deklareeritud massiivide saab kasutada
salvestada nimekirjad.
See on lihtne loetleda elemendid nimekiri
salvestatakse massiivi, ja kui teil on vaja pääseda
või muuta nda nimekirja element
mõne suvalise indeks i,
mida saab teha pidevalt aega,
kuid massiivid on puudusi ka.
>> Kui me kuulutame neid, me peame ütlema
Esiplaanil kui suur see on,
mis on, kui palju elemente, mida nad saavad salvestada
ja kui suur need elemendid on, mis määrab nende tüüpi.
Näiteks int arr (10)
mahutab 10 vastet
mis suurus int.
>> Me ei saa muuta massiivi suuruse pärast deklaratsiooni.
Me peame tegema uue massiivi kui me tahame säilitada rohkem elemente.
Põhjus, miks see piirang olemas on, et meie
Programm salvestab kogu massiiv
kui külgnevas patakas mälu.
Ütle see on puhver, kus me hoida meie massiivi.
Võib olla teiste muutujatega
asub kohe massiivi
mälu, seega ei saa me
lihtsalt massiivi suurem.
>> Vahel me tahaks kaubelda massiiv on kiire andmetele juurdepääsu kiirus
eest natuke rohkem paindlikkust.
Sisesta seotud nimekirja, teine ​​põhi andmestruktuur
sa ei pruugi olla tuttav.
Kõrgel tasemel,
seotud nimekirja salvestab andmeid jada sõlmede
mis on ühendatud omavahel sidemeid,
sellest ka nimi "seotud nimekirja."
Nagu me näeme, see vahe on disain
toob kaasa erinevad plussid ja miinused
kui massiivi.
>> Siin on mõned C koodi väga lihtne seotud nimekirja täisarvud.
Te näete, et meil on esindatud iga sõlm
Nimekirja nagu struct mis sisaldab 2 asja,
täisarv salvestada nimega "Val"
ja linki järgmise sõlme nimekiri
mis me esindame nagu osuti nimega "kõrval."
Nii, me saame jälgida kogu nimekiri
vaid ühe kursor 1. sõlme,
ja siis saame jälgida kõrval viiteid
kuni 2. sõlme,
aasta 3. sõlme,
aasta 4. sõlme,
ja nii edasi, kuni jõuame loetelu lõppu.
>> Sul võib olla võimalik näha 1 eelis see on
üle staatiline maatriksstruktuur - koos seotud nimekirja,
me ei pea suur patakas mälu kokku.
1. sõlme loetelu võiks elada selles kohas mälu,
ja 2. sõlme võiks olla kogu tee siia.
Saame kõik sõlmed ükskõik kus mälu nad on,
sest alates 1. sõlme, iga tipp järgmiseks pointer
ütleb meile täpselt, kuhu minna järgmiseks.
>> Lisaks ei ole meil öelda, kuni ees
kui suur lingitud nimekiri on kuidas me teeme koos staatilise massiivid
kuna suudame hoida lisades sõlmede nimekirja
niikaua kui seal on ruumi kuskil mälus uute tippude.
Seetõttu lingitud nimekirjad on lihtne suurust dünaamiliselt.
Ütle, hiljem programmi on vaja lisada rohkem nodes
meie nimekirjas.
Sõnumisse uue sõlme meie nimekirja lennult,
kõik me peame tegema, on mälu eraldada, et sõlme,
sulpsti andmete väärtust,
ja siis panna see, kui me tahame, reguleerides korral viiteid.
>> Näiteks, kui me tahtsime panna sõlme vahel
2. ja 3. sõlmede loetelu,
ei oleks meil liikuda 2. või 3. sõlmede üldse.
Ütle me lisada see punane sõlme.
Kõik me tahaks pead tegema, on määrata uus sõlm järgmisel pointer
osutada 3. sõlme
ja siis rewire 2. sõlme järgmisel pointer
juhtida meie uus sõlm.
Nii võime suurust meie nimekirju lennult
kuna meie arvuti ei tugine indekseerimine,
vaid pigem ühendab kasutades viiteid need salvestada.
>> Kuid kahjuks seotud nimekirjad
on see, et erinevalt staatiline massiiv,
arvuti ei saa lihtsalt hüpata keset nimekirja.
Kuna arvuti on külastada iga sõlme seotud nimekirja
saada järgmise juurde,
see läheb kauem aega, et leida eelkõige sõlme
kui see oleks massiivi.
Läbida kogu nimekiri võtab aega proportsionaalne
kuni pikkust nimekirja,
või O (n) asümptootilisest märke.
Keskmiselt jõudes iga sõlme
Samuti võtab aega võrdeline n.
>> Nüüd saab tegelikult kirjutada mõned kood
mis töötab koos seotud nimekirju.
Oletame, et me tahame seotud nimekirja täisarvud.
Me ei esinda sõlme meie nimekirja uuesti
nagu struct 2 valdkondades,
täisarvuni nimega "Val"
ja järgmisel kursor järgmisele sõlme nimekirja.
Noh, tundub lihtne.
>> Oletame, et me tahame kirjutada funktsioon
mis läbib nimekirja ja trükib
väärtus salvestatakse viimase sõlme nimekirja.
Noh, see tähendab, et me peame läbida kõik sõlmed nimekirja
leida viimane, kuid kuna me ei lisades
või midagi kustutama, me ei taha muuta
siseehitus järgmise suunanäitajaks nimekirjas.
>> Niisiis, me vajame osuti spetsiaalselt läbipääsusüsteemid
mis me kutsume "roomik".
See poeb läbi kõik elemendid nimekiri
järgides kett järgmisel lähtekohtadeks.
Kõik me oleme salvestatud on viit 1. sõlme,
või "pea" nimekirja.
Head punktid 1. sõlme.
See on tüüpi pointer-to-sõlme.
>> Et saada tegelik 1. sõlme nimekiri,
meil dereference see pointer,
kuid enne kui saame dereference see, peame kontrollima
Kui osuti on null esimene.
Kui see on null, nimekiri on tühi,
ja me peaks välja printida sõnum, et kuna nimekiri on tühi,
ei ole viimase sõlme.
Aga oletame, et loetelu ei ole tühi.
Kui see ei ole, siis peaksime roomata läbi kogu nimekiri
kuni jõuame viimase sõlme loetelu,
ja kuidas me saame öelda, kui me vaatame viimast sõlme nimekirja?
>> Noh, kui sõlm järgmisel osuti on null,
me teame, et me oleme lõpus
pärast viimast järgmisel osuti ei oleks järgmine sõlme nimekiri osutada.
See on hea tava, et hoiavad viimase sõlme järgmisel osuti käivitub tühjaks
on standardiseeritud vara mis hoiatab meid, kui oleme jõudnud nimekirja.
>> Niisiis, kui roomik → kõrval on null,
meeles pidama, et arrow süntaks on otsetee viite mahavõtmine
kursor struct, siis tutvumise
selle järgmisele väljale samaväärne ebamugav:
(* Roomik). Kõrval.
Kui oleme leidnud viimase sõlme,
me tahame prindi roomik → Val,
väärtus aktiivse sõlme
mis me teame, on viimane.
Vastasel juhul, kui me ei ole veel viimasel sõlme loetelu,
meil liikuda edasi järgmise sõlme nimekiri
ja vaadata, kas see on viimane.
Selleks me lihtsalt paneme meie roomik pointer
osutada praeguse sõlme järgmine väärtus,
see tähendab, et järgmise sõlme nimekirja.
Seda tehakse, seades
roomik = roomik → järgmine.
Siis korrake seda protsessi, mille ahela näiteks
kuni leiame viimase sõlme.
Nii näiteks, kui roomik oli osutades peaga
seadsime roomik osutada roomik → kõrval,
mis on sama järgmise välja 1. sõlme.
Nii, nüüd meie roomik on suunaga 2. sõlme,
ja jällegi, me kordame seda silmus,
kuni oleme leidnud viimase sõlme, mis on
kus sõlm järgmisel osuti osutab tühjaks.
Ja seal on meil siis,
oleme leidnud viimase sõlme loetelu, ja printida oma väärtust,
me lihtsalt kasutada roomik → Val.
>> Liiklevad ei ole nii halb, kuid kuidas lisada?
Lets öelda tahame sisestada täisarv arvesse 4. kohal
aastal täisarv nimekirja.
See on senise 3. ja 4. sõlmed.
Jällegi, meil on läbida nimekirja lihtsalt
saada 3. osa, üks me lisades pärast.
Niisiis, loome roomik osuti uuesti läbida nimekirja,
vaadata, kas meie peas osuti on null,
ja kui see ei ole, suunake oma roomik osuti eesotsas sõlme.
Niisiis, me oleme 1. osa.
Me peame minema edasi veel 2 sätteid enne kui saame sisestada,
nii saame kasutada loop
int i = 1; i <3; i + +
ja iga iteratsiooni silmus,
edendada meie roomik osuti edasi 1 sõlm
kontrollib, kas praegune tipp järgmiseks valdkonnas on null,
ja kui see ei ole, liikuda meie roomik kursor järgmisele sõlme
seades see võrdne praeguse sõlme järgmisel pointer.
Niisiis, kuna meie jaoks silmus ütleb, mida teha, et
kaks korda,
oleme jõudnud 3. sõlme,
ja kui meie roomik osuti on jõudnud sõlme pärast
mida me tahame lisada meie uus täisarv,
kuidas me tegelikult ei sisestamist?
>> Noh, meie uus täisarv tuleb lisada nimekiri
osana oma sõlme struct,
sest see on tõesti jada sõlmed.
Nii, teeme uue kursor sõlme
nn new_node "
ja seadke see viidata mälu, et me nüüd eraldada
edasi hunnik jaoks sõlme ise,
ja kui palju mälu on meil vaja eraldada?
Noh, suurus sõlme,
ja me tahame, et määrata oma val põllult täisarv, et me tahame lisada.
Oletame, 6.
Nüüd, sõlm sisaldab meie täisarvuni.
See on ka hea tava initsialiseerida uus sõlm järgmisele väljale
juhtida null,
aga nüüd?
>> Me peame muutma siseehitus nimekirja
ja järgmine suunanäitajaks loetelus sisalduva olemasoleva
3. ja 4. sõlmed.
Kuna järgmine suunanäitajaks kindlaks nimekirja järjestuse alusel,
ja kuna me lisada meie uus sõlm
otse keset nimekirja,
see võib olla veidi keeruline.
Seda seetõttu, pea meeles, meie arvuti
ainult teab, kus asuvad tippe nimekirja
sest järgmisel lähtekohtadeks salvestatud eelmise sõlmed.
Niisiis, kui me kunagi kaotanud jälgida, et nendes kohtades,
öelda muutes ühe järgmise viiteid meie nimekirja,
Ütleme näiteks, et oleme muutnud
3. sõlme järgmisele väljale
et osutada mõnele sõlme siin.
Me tahaks olla läbi õnne, sest me ei
on aimu, kust leida ülejäänud nimekirja,
ja see on ilmselt tõesti halb.
Niisiis, me peame olema väga ettevaatlikud, et
kus me manipuleerida meie kõrval suunanäitajaks sisestamise ajal.
>> Nii, et lihtsustada käesoleva oletame, et
meie esimene 4 tippu
nimetatakse A-, B-, C-, ja D, nooled esindavad kett viiteid
et ühendada sõlmed.
Niisiis, me peame lisada meie uus sõlm
vahel sõlmed C ja D.
On oluline teha seda õiges järjekorras, ja ma näitan teile, miks.
>> Vaatame vale viis seda teha esimesena.
Hei, me teame, et uus sõlm peab tulema kohe pärast C,
niiet seatud C järgmiseks pointer
osutada new_node.
Olgu, tundub okei, me lihtsalt peame lopeteltiin nüüd poolt
tegemist uue sõlme järgmisel pointer punkt D,
Aga oota, kuidas me seda teeme?
Ainuke asi, mis võiks meile öelda, kus D oli,
aastal järgmise pointer varem salvestatud C,
kuid me lihtsalt rewrote et osuti
osutada uus sõlm,
nii et me ei ole enam aimugi, kus D on mälu,
ja me oleme kaotanud ülejäänud nimekirja.
Mitte üldse hea.
>> Niisiis, kuidas me seda teha eks?
Esimene punkt Uue sõlme järgmisel pointer D.
Nüüd, kui uus sõlm ja C järgmiseks viiteid
osutades sama sõlme, D,
aga sellest pole midagi.
Nüüd saame punkti C järgmiseks viitaja uus sõlm.
Niisiis, oleme teinud seda ilma andmeid kaotamata.
Kood, C on praegune tipp
et läbipääsusüsteemid osuti roomik on suunaga,
ja D on esindatud sõlme poolt esile tõstetud praeguse sõlme järgmisele väljale,
või roomikutel → kõrval.
Niisiis, me kõigepealt kehtestada uus sõlm järgmisel pointer
osutada roomik → kõrval,
Samamoodi me ütlesime new_node järgmiseks osuti peaks
osutada D joonisel.
Siis saame praegune tipp järgmiseks pointer
meie uus sõlm,
nagu pidime ootama punktis C new_node joonisel.
Nüüd kõik on korras, ja me ei kaotanud
jälgida mis tahes andmed, ja me saime lihtsalt
kinni meie uus sõlm keset nimekiri
ilma ümberehitust kogu asja või isegi minnes kõikidest elementidest
kuidas me oleks pidanud koos kindla pikkusega massiiv.
>> Niisiis, lingitud nimekirjad on lihtne, kuid oluline, dünaamiline andmestruktuur
mis on nii plusse ja miinuseid
võrreldes massiivid ja teiste andmestruktuuride
ja nagu sageli juhtub infotehnoloogia,
see on oluline teada, millal kasutada iga vahend,
nii et saate valida õige vahend õige töö.
>> Rohkem praktikas proovida kirjalikult ülesandeid
kustutada sõlmede alates lingitud nimekiri -
meeles olla ettevaatlik, millises järjekorras sa ümber
oma järgmise viiteid, et sa ei kaota tüki oma nimekirja -
või funktsiooni loota tippe seotud nimekirja,
või lõbus, et vastupidises järjekorras kõik sõlmed seotud nimekirja.
>> Minu nimi on Jackson Steinkamp, ​​see on CS50.