[Powered by Google Translate] Sa programming, madalas naming kailangan upang kumatawan sa listahan ng mga halaga, tulad ng mga pangalan ng mga mag-aaral sa isang seksyon o ang kanilang mga marka sa mga pinakabagong pagsusulit. 

Sa wika ng C, ipinahayag array ay maaaring magamit upang mag-imbak ng mga listahan. Madaling magbilang ang mga elemento ng isang listahan naka-imbak sa isang array, at kung kailangan mo upang ma-access o baguhin ang ith elemento listahan para sa ilang arbitrary index ako, na maaaring gawin sa pare-pareho ang oras, ngunit array ay may disadvantages, masyadong. 

Kapag ipinapahayag namin ang mga ito, kami ay kinakailangan upang sabihin up front kung gaano kalaki ang mga ito, iyon ay, kung gaano karaming mga elemento ang maaari silang mag-imbak at kung gaano kalaki ang mga elementong ito, na kung saan ay tinutukoy sa pamamagitan ng kanilang mga uri. Halimbawa, int arr (10) maaaring iimbak ng 10 mga item na ang laki ng isang int. 

Hindi namin maaaring baguhin ang laki ng isang array pagkatapos ng deklarasyon. Mayroon kaming upang gumawa ng isang bagong array kung gusto namin upang mag-imbak ng higit pang mga elemento. Ang dahilan ng limitasyong ito ang umiiral na ay na ang aming programa iniimbak ang buong array bilang isang magkadikit na tipak ng memorya. Sabihing ito ay ang buffer kung saan kami naka-imbak sa aming array. Maaaring may iba pang mga variable matatagpuan sa tabi mismo sa array sa memory, kaya hindi namin mai- array ang mas malaking. 

Minsan nais naming ikakalakal mabilis ang array data sa bilis ng access para sa isang maliit na higit pang kakayahang umangkop. Ipasok ang naka-link na listahan, ang isa pang pangunahing istraktura ng data hindi mo maaaring maging pamilyar sa. Sa isang mataas na antas, naka-link na listahan ay nag-iimbak ng mga data sa isang pagkakasunud-sunod ng mga node na konektado sa bawat isa sa mga link, samakatuwid 'naka-link na listahan.' ang pangalan Tulad ng makikita namin makita, ang pagkakaibang ito sa disenyo humantong sa iba't ibang mga kalamangan at disadvantages kaysa sa isang array. 

Narito ang ilang C code para sa isang napaka-simpleng naka-link na listahan ng mga integer. Maaari mong makita na namin kinakatawan ang bawat node sa listahan bilang isang struct na naglalaman ng 2 bagay, isang integer upang mag-imbak na tinatawag na 'Val' at isang link sa susunod na node sa listahan kung saan ay kumakatawan namin bilang isang pointer na tinatawag na 'susunod.' Sa ganitong paraan, maaari naming subaybayan ang buong listahan ng isang pointer sa node 1st, at pagkatapos ay maaari naming sundin ang mga susunod na mga pointer sa 2nd node, sa 3rd node, sa ika-4 na node, at iba pa, hanggang sa makuha namin sa dulo ng listahan. 

Na maaaring magawa upang makita ang 1 samantalahin ito ay may sa ibabaw ng static na istraktura ng array - na may naka-link na listahan, hindi namin kailangan ng isang malaking tipak ng memory sa kabuuan. Ang 1st node ng listahan ay maaaring manirahan sa lugar na ito sa memory, at sa 2nd na node ay maaaring ang lahat ng mga paraan sa paglipas dito. Maaari naming makakuha ng sa lahat ng mga node hindi mahalaga kung saan sa memory ang mga ito, dahil simula sa node 1st, susunod na pointer sa bawat node ay nagsasabi sa amin kung saan mismo upang pumunta sa susunod na. 

Bukod pa rito, hindi namin upang sabihin up front kung gaano kalaki ang isang naka-link na listahan ay ang paraan na gawin namin sa static array, dahil maaari naming patuloy na magdagdag ng mga node sa isang listahan hangga't may espasyo sa isang lugar sa memory para sa bagong mga node. Samakatuwid, ang mga naka-link na listahan ay madaling upang baguhin ang laki dynamic. Sabihin nating, sa ibang pagkakataon sa programa kailangan namin upang magdagdag ng higit pang mga node sa aming listahan. Upang magpasok ng isang bagong node sa aming listahan sa mabilisang, lahat kami ay may sa gawin ay magtalaga ng memory para sa node, magsabuwatan sa ang halaga ng data, at pagkatapos ay ilagay ito kung saan nais naming sa pamamagitan ng pagsasaayos ng mga naaangkop na payo. 

Halimbawa, kung gusto naming maglagay ng node sa pagitan ang ika-2 at ika-3 na node ng listahan,  hindi namin ay upang ilipat ang 2nd o 3rd node sa lahat. Sabihing namin ang pagpasok ng ito pulang node. Ang lahat na gusto naming gawin ay nakatakda sa susunod na pointer ang bagong node upang tumuro sa ika-3 na node at pagkatapos ay rewire ng susunod na pointer sa 2nd node ituro sa aming bagong node. Kaya, maaari naming baguhin ang laki ng aming mga listahan sa mabilisang simula ng aming computer ay hindi umaasa sa pag-i-index, kundi sa pagli-link gamit ang pointer upang mag-imbak ang mga ito. 

Gayunpaman, ang dehado ng naka-link na listahan ay na, hindi katulad ng static na array, ang computer ay hindi maaari lamang tumalon sa gitna ng listahan. Dahil ang computer ay may upang bisitahin ang bawat node sa naka-link na listahan upang makakuha ng sa susunod na, ito ay pagpunta sa magtagal upang mahanap ang isang partikular na node kaysa sa gagawin ito sa isang array. Upang pagbagtas ang buong listahan ay tumatagal ng oras proporsyonal sa haba ng listahan, o O (n) sa asymptotic pagtatanda. Sa average, na umaabot sa anumang node nangangailangan ng panahon proporsyonal sa n. 

Ngayon, sabihin aktwal na magsulat ng ilang mga code na gumagana sa naka-link na listahan. Ipagpalagay natin na nais namin ang isang naka-link na listahan ng mga integer. Maaari naming kumakatawan sa isang node muli sa aming listahan bilang isang struct may 2 mga patlang, ng isang integer value na tinatawag na 'Val' at susunod na pointer sa susunod na node ng listahan. Well, tila simpleng sapat. 

Ipagpalagay natin na nais namin upang magsulat ng isang function kung aling mga traverses ang listahan at print ang halaga na naka-imbak sa huling node ng listahan. Well, na ibig sabihin nito ay kailangan nating pagbagtas ang lahat ng mga node sa listahan upang mahanap ang huling, ngunit dahil hindi namin pagdaragdag ng o tinatanggal, hindi namin nais na baguhin ang panloob na istraktura ng susunod na pointer sa listahan. 

Kaya, makikita namin kailangan ang isang pointer para traversal na kami tatawag sa 'crawler.' Ito ay crawl sa pamamagitan ng ang lahat ng mga elemento ng listahan sa pamamagitan ng pagsunod sa mga kadena ng mga susunod na pointer. Lahat na naka-imbak namin ay isang pointer sa node 1st, o 'ulo' ng listahan. Head ng mga puntos sa 1st node. Ng uri ng pointer-sa-node. 

Upang makuha ang aktwal na 1st node sa listahan, mayroon kaming dereference pointer na ito, ngunit bago namin ito dereference, kailangan namin upang suriin kung ang pointer ay null unang. Kung ito ay null, listahan ay walang laman, at dapat naming i-print ang isang mensahe, dahil ang listahan ay walang laman, walang huling node. Ngunit, sabihin nating ay hindi walang laman ang listahan. Kung ito ay hindi, pagkatapos ay dapat namin crawl sa pamamagitan ng buong listahan hanggang sa makuha namin sa huling node ng listahan, at kung paano maaari naming sabihin kung kaming naghahanap sa huling node sa listahan? 

Well, kung ang susunod na pointer ng node ay null, alam namin na hindi namin sa dulo dahil ang huling susunod na pointer ay walang susunod na node sa listahan upang tumuro sa. Ito ay mahusay na kasanayan upang laging panatilihin ang susunod na pointer sa huling node nasimulan sa null Standardized ari-arian na inaalertuhan sa amin kapag kami naabot ang dulo ng listahan. 

Kaya, kung crawler → susunod ay null, tandaan na ang syntax ng arrow ay isang shortcut para sa dereferencing isang pointer sa isang struct, pagkatapos-access nito sa susunod na field katumbas sa mahirap: (* Crawler). Susunod. Kapag nalaman namin na ang huling node, gusto naming upang i-print ang crawler → Val, ang halaga sa kasalukuyang node kung saan alam namin ay ang huling. Kung hindi man, kung hindi kami pa sa huling node sa listahan, mayroon kaming upang lumipat sa susunod na node sa listahan at suriin kung iyon ang huling isa. Upang gawin ito, lamang namin-set ang aming crawler pointer upang ituro sa susunod na halaga ng ang kasalukuyang node, iyon ay, ang susunod na node sa listahan. Ito ay ginagawa sa pamamagitan ng pagtatakda crawler = crawler → susunod. Pagkatapos naming ulitin ang prosesong ito, na may isang loop halimbawa, hanggang sa nakita namin ang huling node. Kaya, halimbawa, kung crawler ay tumuturo sa ulo, kami ng crawler upang tumuro sa crawler → susunod, na ang parehong bilang ang susunod na field ng 1st node. Kaya, ngayon aming crawler ay tumuturo sa ika-2 node, at, muli, ulitin namin ito na may loop, hanggang sa natagpuan namin ang huling node, iyon ay, kung saan ang susunod na pointer sa node ay tumuturo sa null. At doon ay may namin ito, nalaman namin huling node sa listahan, at upang i-print ang halaga, namin lamang gamitin ang crawler → Val. 

Traversing ay hindi kaya masamang, ngunit kung ano ang tungkol sa pagpasok? Ay nagbibigay-daan nating gusto naming magpasok ng isang integer sa ika-4 na posisyon sa isang integer listahan. Ito ay sa pagitan ng kasalukuyang ika-3 at ika-4 na node. Muli, mayroon kami sa pagbagtas sa listahan lamang makuha ang 3rd elemento, namin ang pagpasok pagkatapos. Kaya, hindi namin muling lumikha ng isang crawler pointer sa pagbagtas sa listahan, suriin kung ang aming ulo pointer ay null, at kung ito ay hindi, ituro ang aming crawler pointer sa node ng ulo. Kaya, hindi namin sa 1st elemento. Mayroon kaming upang pumunta pasulong 2 higit pang mga elemento bago namin isingit, upang maaari naming gamitin para sa loop int i = 1; i <3; i + + at sa bawat pag-ulit ng loop, advance ang aming crawler pointer sa forward ng 1 node sa pamamagitan ng pagsuri kung ang susunod na field ang kasalukuyang node ay null, at kung ito ay hindi, ilipat ang aming crawler pointer sa susunod na node sa pamamagitan ng pagtatakda ng katumbas ng susunod na pointer ang kasalukuyang node. Kaya, dahil ang aming para sa loop sabi ni upang gawin iyon dalawang beses, Naabot namin ang 3rd node, at sabay-sabay ang aming crawler pointer ay naabot node pagkatapos kung saan gusto naming upang ipasok ang aming bagong integer, kung paano namin aktwal ang pagpasok? 

Well, ang aming bagong integer ay ipinasok sa listahan bilang bahagi ng sarili nitong node struct, dahil ito ay talagang isang pagkakasunud-sunod ng mga node. Kaya, sabihin gumawa ng isang bagong pointer sa node tinatawag na 'new_node,' at itakda ito upang tumuro sa memorya na namin ngayon na maglaan sa magbunton para sa node mismo, at kung gaano karaming memory ang kailangan namin upang magtalaga? Well, ang laki ng isang node, at gusto naming i-set ang Val field sa integer na gusto namin upang ipasok. Sabihin nating, 6. Ngayon, ang node ay naglalaman ng aming mga halaga ng integer. Ring mahusay na kasanayan upang simulan ang susunod na field ang bagong node upang tumuro sa null, ngunit ngayon ano? 

Mayroon kaming upang baguhin ang panloob na istraktura ng listahan at ang susunod na mga pointer na nilalaman sa umiiral sa listahan Ika-3 at ika-4 na node. Dahil ang mga susunod na pointer matukoy ang pagkakasunud-sunod ng listahan, at dahil kami ay pagpasok ng aming bagong node pakanan papunta sa kalagitnaan ng listahan, ito ay isang bit nakakalito. Ito ay dahil, tandaan, ang aming mga computer na lamang alam ang lokasyon ng mga node sa listahan dahil sa sa susunod na mga pointer na naka-imbak sa nakaraang node. Kaya, kung namin nawala ang pagsubaybay ng anumang mga lokasyong ito, sabihin sa pamamagitan ng pagbabago sa isa sa mga susunod na mga payo sa aming listahan, halimbawa, sinasabi namin ay nagbago susunod na field sa 3rd node upang tumuro sa ilang node sa paglipas dito. Gusto naming ka sana, dahil hindi namin gagawin anumang mga ideya kung saan upang mahanap ang natitirang bahagi ng listahan, at na malinaw naman ganap na hindi maayos. Kaya, mayroon kaming talagang maingat tungkol sa pagkakasunod-sunod kung saan namin manipulahin ang aming mga susunod na pointer sa panahon ng pagpapasok ng. 

Kaya, upang gawing simple ito, sabihin nating aming unang 4 node ay tinatawag na A, B, C, at D, gamit ang mga arrow na kumakatawan sa hanay ng mga payo na ikonekta ang mga node. Kaya, kailangan namin upang ipasok ang aming bagong node sa pagitan ng node C at D. Ito ay kritikal na upang gawin ang mga ito sa tamang pagkakasunod-sunod, at kukunin ko na ipakita sa iyo kung bakit. 

Tingnan natin sa maling paraan upang gawin ito unang. Uy, alam namin ang bagong node ay darating karapatan pagkatapos C, kaya sabihin itakda ang susunod na pointer C upang ituro sa new_node. Karapatan lahat, mukhang okay, namin lamang upang tapusin ngayon sa pamamagitan ng susunod na pointer sa bagong node punto sa D, ngunit paghihintay, kung paano namin gawin iyon? Ang tanging bagay na maaaring sabihin sa amin kung saan ang D ay, ay sa susunod na pointer sa nakaraang naka-imbak sa C, ngunit hindi namin lamang rewrote na pointer upang ituro sa bagong node, kaya hindi na namin anumang bakas kung saan D sa memorya, at hindi na namin nawala ang natitirang bahagi ng listahan. Hindi magandang sa lahat. 

Kaya, kung paano ang gagawin namin ang karapatan na ito? Una, ituro ang susunod na pointer ang bagong node sa D. Ngayon, sa parehong bagong node at C susunod na pointer ay na tumuturo sa parehong node, D, ngunit ang fine. Ngayon ay maaari naming ituro ang susunod C pointer sa bagong node. Kaya, ginawa namin ito nang hindi nawawalan ng anumang data. Sa code, C ay ang kasalukuyang node na traversal pointer crawler ay tumuturo sa, at D ay kinakatawan ng node nakaumang sa pamamagitan ng susunod na field ang kasalukuyang node, o crawler → susunod. Kaya, muna namin magtakda ng susunod na pointer ang bagong node upang ituro sa crawler → susunod, sa parehong paraan na sinabi namin ang susunod na pointer new_node dapat tumuro sa D sa paglalarawan. Pagkatapos, maaari naming itakda ang susunod na pointer ang kasalukuyang node sa aming bagong node, tulad ng nagkaroon kami maghintay upang ituro ang C upang new_node sa drawing. Ngayon ang lahat sa pagkakasunod-sunod, at hindi namin mawala subaybayan ng anumang data, at hindi namin magagawang lamang dumikit ang aming bagong node sa gitna ng listahan walang muling pagtatayo ang buong bagay o kahit na paglilipat anumang mga elemento paraan ay namin ay nagkaroon na may isang nakapirming haba ng array. 

Kaya, ang mga naka-link na listahan ay isang pangunahing, ngunit mahalaga, dynamic na istraktura ng data na may parehong mga kalamangan at disadvantages kumpara sa mga array at iba pang mga data kaayusan, at bilang ay madalas na ang kaso sa computer science, Mahalagang malaman kapag upang gamitin sa bawat tool, sa gayon ay maaari mong piliin ang mga tamang tool para sa tamang trabaho. 

Para sa higit pang mga kasanayan, subukan ang pagsusulat ng mga function sa tanggalin ang node mula sa naka-link na listahan - tandaan na maging maingat tungkol sa pagkakasunud-sunod kung saan mong isaayos muli ang iyong mga susunod na pointer upang matiyak na hindi ka mawalan ng isang tipak ng iyong listahan - o isang function upang mabilang ang mga node sa isang naka-link na listahan, o isang masaya, upang baliktarin ang pagkakasunod-sunod ng lahat ng node sa isang naka-link na listahan. 

Ang pangalan ko ay Jackson Steinkamp, ​​ito ay CS50.