[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.