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