>> [MUSIC nagpe-play]
>> DOUG LLOYD: OK, para sa sa puntong ito sa panahon,
sakop na namin ang isang pulutong ng mga pangunahing kaalaman ng C. Alam namin ng maraming tungkol sa mga variable, array,
mga payo, lahat na magagandang bagay-bagay.
Ang mga ay ang lahat ng uri ng mga itinayo in upang makita ang bilang batayan,
ngunit maaari naming makagawa ng higit pa, i-right?
Maaari naming pagsamahin ang mga bagay sama-sama sa mga kawili-wiling paraan.
>> At ni gawin iyon upang ipaalam, sabihin magsimula upang magpalago ng negosiyo ng kung ano ang nagbibigay sa amin C,
at simulan upang lumikha ng aming sariling data kaayusan ng paggamit ng mga gusali
bloke ng magkasama upang gawin ang isang bagay talagang mahalaga, kapaki-pakinabang.
Ang isang paraan na maaari naming gawin ito ay upang makipag-usap tungkol sa mga koleksyon.
Kaya ngayon kami ay nagkaroon ng isang uri ng data structure para sa kumakatawan sa mga koleksyon
ng gusto halaga, katulad na halaga.
Iyon ay magiging isang array.
Mayroon kaming mga koleksyon ng mga integer, o mga koleksyon ng mga character at iba pa.
>> Istruktura ay ayusin din ng isang data structure para sa pagkolekta ng impormasyon,
ngunit ito ay hindi para sa pagkolekta ng tulad ng mga halaga.
Karaniwan itong mix iba't ibang mga uri ng data sama sa loob ng isang kahon.
Ngunit ito ay hindi mismo ginagamit upang chain magkasama
o kumonekta magkasama katulad bagay, tulad ng isang array.
Ang mga array ay mahalaga para sa element maghanap, ngunit pagpapabalik
na ito ay mahirap upang ipasok sa isang array,
maliban kung kami ay pagpasok sa sa dulo ng array na.
>> At ang pinakamahusay na halimbawa ko para sa na ay uri insertion.
Kung isipin mo ang aming mga video on-uuri,
nagkaroon ng maraming gastos na kasangkot sa pagkakaroon
upang kunin ang mga elemento, at ilipat ang mga ito sa labas ng paraan upang magkasya ang isang bagay
sa gitna ng iyong array.
Magtiis din Arrays mula sa isa pang problema, na kung saan ay katigasan.
Kung ating sinasabing isang array, makakakuha tayo ng isang shot at ito.
Makuha namin upang sabihin, gusto ko ito maraming mga sangkap.
Maaaring maging 100, maaaring ito maging 1000, maaaring ito
maging x kung saan ang x ay isang numero na ang gumagamit nagbigay sa amin sa isang prompt o sa utos
linya.
>> Ngunit lamang namin makakuha ng isa pagbaril sa ito, kami hindi makapunta sa pagkatapos ay sabihin oh, tunay na ako
kailangan 101, o kailangan ko x plus 20.
Masyadong huli, na ipinahayag na namin ang array, at kung gusto naming makuha 101 o x
plus 20, mayroon kaming na idedeklara isang ganap na magkaibang array,
kopyahin ang lahat ng mga elemento ng array sa ibabaw, at pagkatapos kami ay may sapat.
At paano kung tayo ay muli mali, kung ano kung talagang kailangan namin ng 102, o x plus 40,
kami ay may sa gawin ito muli.
Kaya ang mga ito masyadong matigas para sa pagbabago ng laki ng aming data,
ngunit kung pagsamahin namin magkasama ang ilang mga sa mga pangunahing kaalaman na kami na
natutunan ang tungkol sa mga payo at kaayusan, sa mga partikular na gumagamit ng mga dynamic memory
laang-gugulin sa malloc, namin maaaring ilagay ang mga piraso ng magkasama
upang lumikha ng isang bagong data structure-- isang isa-isa ang listahan upang tayo say-- naka-link
na nagbibigay-daan sa amin upang maging at pag-urong ng isang koleksyon ng mga halaga
at hindi kami ay may anumang mga nasayang na espasyo.
>> Kaya muli, ang tawag namin sa mga ideya na ito, paniwala na ito, ang isang listahan ng mga link.
Sa partikular, sa video na ito hindi namin pakikipag-usap tungkol sa kanyang sarili na naka-link na listahan,
at pagkatapos ng isa pang video namin makipag-usap tungkol sa doble-link na listahan, kung saan
ay isang pagkakaiba-iba lamang sa isang tema dito.
Ngunit isang isa-isa listahan ng mga link ay binubuo ng mga nodes,
nodes lamang pagiging isang abstract term-- ito ay isang bagay na lang ako ng pagtawag
iyan ay isang uri ng istraktura, karaniwang, ako?
Basta pagpunta sa tawag na ito ng isang node-- at ito node ay may dalawang mga kasapi, o dalawang mga patlang.
Ito ay may data, kadalasan ay isang integer, isang character float,
o maaaring ang ilang iba pang mga uri ng data na tinukoy mo sa isang uri def.
At ito ay naglalaman ng isang pointer sa isa pang node ng parehong uri.
>> Kaya kami ay may dalawang mga bagay-bagay sa loob ng ito node, data at isang pointer
sa ibang node.
At kung nagsimula ka upang mailarawan ito, maaari mong isipin ang tungkol dito
tulad ng isang kadena ng mga nodes na ay konektado magkasama.
Tayo ang unang node, ito naglalaman ng data, at ang isang pointer
sa ikalawang node, na naglalaman ng data, at isang pointer sa ikatlong node.
At kaya na ang dahilan kung bakit ang tawag namin ito ng isang listahan ng mga link, kasama ang mga ito ay naka-link.
>> Ano ang ginagawa ng mga ito ng espesyal istraktura node hitsura?
Well, kung ang pagpapabalik sa iyo mula sa aming mga video sa pagtukoy pasadyang uri, na may uri def,
maaari naming tukuyin ang isang structure-- at type tukuyin ang isang istraktura tulad nito.
tyepdef struct sllist, at pagkatapos ay ako gamit ang halaga ng salita dito nagkataon
upang ipahiwatig ang anumang uri ng data talaga.
Ikaw ay maaaring ipasa sa isang integer o float, maaari kang magkaroon ng anumang nais mo.
Hindi ito limitado sa mga lamang integer, o anumang bagay tulad na.
Kaya ang halaga ay lamang ng isang arbitrary uri ng data, at pagkatapos ay isang pointer
sa ibang node ng parehong uri.
>> Ngayon, may isang maliit na catch dito sa pagtukoy ng isang istraktura
kapag ito ay isang istraktura sa sarili referential.
Mayroon akong magkaroon ng isang pansamantalang pangalan para sa aking mga istraktura.
Sa katapusan ng araw ko malinaw na gusto pangalanan ito
sll node, na ang huli ang bagong pangalanan bahagi ng aking mga kahulugan ng uri,
ngunit hindi ako maaaring gumamit ng sll node sa gitna ng mga ito.
Ang dahilan ay, mayroon akong hindi lumikha ng isang uri ng tinatawag sll node
hanggang maabot ko ang huling punto dito.
Hanggang sa puntong iyon, kailangan kong magkaroon isa pang paraan upang sumangguni sa ganitong uri ng data.
>> At ito ay isang self referential uri ng data.
Ito; s isang uri ng data ng isang istraktura na naglalaman ng isang data,
at isang pointer sa isa pang istraktura ng parehong uri.
Kaya kailangan ko upang ma-refer sa ng ganitong uri ng data kahit pansamantala,
kaya nagbibigay ito ng isang pansamantalang pangalan ng struct sllist
ay nagbibigay-daan sa akin na pagkatapos sabihin Gusto ko ng isang pointer sa isa pang struct sllist,
isang struct sllist star, at pagkatapos ay matapos Nakumpleto ko na ang kahulugan,
Maaari ko ngayon tumawag sa ganitong uri ng sll node.
>> Kaya na ang dahilan kung bakit nakikita mo ang may isang pansamantalang pangalan dito,
ngunit isang permanenteng pangalan dito.
Minsan maaari mong makita ang mga kahulugan ng istraktura,
halimbawa, na hindi sa sarili referential, na
hindi magkaroon ng isang pangalan specifier dito.
Ito lamang sabihin typedef struct, buksan kulot suhay at pagkatapos ay tukuyin ang mga ito.
Ngunit kung ikaw ay struct ay self referential, tulad ng isang ito ay,
kailangan mong tukuyin ang isang pansamantalang uri ng pangalan.
Ngunit sa huli, ngayon na tapos na namin ito,
maaari naming lamang sumangguni sa mga nodes, ang mga yunit,
bilang sll nodes para sa mga layunin ng ibang bahagi ng video na ito.
>> Lahat ng mga karapatan, upang malaman namin kung paano sa lumikha ng isang listahan ng mga link node.
Alam namin kung paano upang tukuyin ang isang listahan ng mga link node.
Ngayon, kung kami ay pagpunta sa simulan paggamit ng mga ito upang mangolekta ng impormasyon,
may isang pares ng mga operasyon namin kailangan upang maunawaan at gumagana sa.
Kailangan nating malaman kung paano lumikha ng isang listahan ng mga link sa labas ng manipis na hangin.
Kung walang list na, gusto naming magsimula ng isa.
Kaya kailangan namin upang ma upang lumikha ng isang listahan ng mga link,
kailangan naming malamang na maghanap sa pamamagitan ng listahan ng link
upang maghanap ng isang elemento kaming naghahanap para sa.
Kailangan namin upang magawang ipasok ang mga bagong bagay sa listahan,
gusto namin ang aming listahan upang ma-lalaki.
At katulad, gusto naming ma upang tanggalin ang mga bagay mula sa aming listahan,
gusto namin ang aming listahan para ma-urong.
At sa dulo ng ating programa, lalo na
kung isipin mo na hindi namin magilas paglaan memory
upang bumuo ng mga listahang ito kadalasan, gusto naming magbakante ng lahat ng na memory
kapag kami ay tapos na nagtatrabaho sa mga ito.
At kaya kailangan namin upang ma-tanggalin ang isang buong listahan na naka-link sa isa mabibigo mabilis na pagsalakay.
Kaya sabihin pumunta sa pamamagitan ng ang ilan sa mga operasyon
at kung paano namin maaaring isalarawan ang mga ito, pakikipag-usap sa pseudocode code mismo.
Kaya gusto namin upang lumikha ng isang list na naka-link, kaya siguro kami
nais na tukuyin ang isang function na may ganitong prototype.
sll node star, lumikha, at ako makapasa sa isang argument, ang ilang mga di-makatwirang data
type muli, ng ilang di-makatwirang uri ng data.
Ngunit ako returning-- ang function na ito ay dapat bumalik sa akin ng isang pointer, sa isang isa-isa
listahan ng mga link node.
Muli, kami ay sinusubukan upang lumikha ng isang listahan ng mga link sa labas ng manipis na hangin,
kaya kailangan ko ng isang pointer sa na listahan kapag ako tapos na.
>> Kaya ano ang mga hakbang na kasangkot dito?
Well, unang bagay na ako pagpunta sa gawin ay magilas
maglaan ng espasyo para sa isang bagong node.
Muli, kami ay ang paglikha ito ng manipis hangin, kaya kailangan naming malloc espasyo para dito.
At siyempre, agad pagkatapos naming malloc,
palagi naming suriin upang tiyakin na ang aming pointer-- hindi kami makabalik null.
Dahil kung susubukan namin at pagsang-ayon ng isang null pointer,
kami ay pagpunta sa magdusa ng isang segfault at hindi namin nais na.
>> Pagkatapos na nais namin upang punan ang mga field, gusto naming i-initialize ang patlang ng halaga
at magpasimula ng mga susunod na field.
At pagkatapos ay nais naming to-- huli bilang ang function tularan indicates-- gusto namin
upang magbalik ng pointer sa isang sll node.
Kaya kung ano ang gumawa ng mga ito hitsura ng biswal?
Well, first namin ang pagpunta sa mga dynamic na maglaan ng espasyo para sa isang bagong sll node,
kaya malloc-- namin na isang visual na representasyon
ng node na nilikha para lamang namin.
At kami suriin upang tiyakin na hindi ito null-- sa kasong ito,
ang larawan ay hindi na kailangang ipinapakita up kung ito ay null,
Gusto namin Naubusan ng memorya, kaya kami ay handa na upang pumunta doon.
Kaya ngayon hindi namin sa hakbang C, magpasimula ang patlang na halaga nodes.
Well, ayon sa mga function na ito tumawag ako ng gamit dito,
Mukhang gusto kong pumasa sa 6, kaya makikita ko ang 6 sa patlang ng halaga.
Ngayon, magpasimula ang susunod na field.
Well, kung ano ako pagpunta sa gawin doon, walang anuman sa susunod, kanan,
ito ay ang tanging bagay sa listahan.
Kaya kung ano ang susunod na bagay sa listahan?
>> Hindi ito dapat tumuro sa anumang bagay, right.
May walang ibang tao doon, kaya kung ano ang ang konsepto na aming kilala na nothing--
mga payo sa wala?
Dapat ito ay marahil ay gusto namin maglagay ng isang null pointer doon,
at kukunin ko na kumakatawan sa mga null pointer bilang lamang ng isang red box,
hindi namin maaaring pumunta sa anumang karagdagang.
Tulad ng makikita namin makita ang isang maliit na sa susunod, magkakaroon kami ng huli chains
ng mga arrow sa pagkonekta mga nodes magkasama,
ngunit kapag ikaw ay pindutin ang red box, na null,
hindi namin maaaring pumunta anumang karagdagang, iyon ang katapusan ng listahan.
>> At bilang wakas, nais lang namin sa ibalik ang isang pointer sa node.
Kaya makikita tinatawag namin itong bago, at babalik bagong
kaya ito ay maaaring gamitin sa kahit anong function lumikha nito.
Kaya doon pumunta kami, Lumikha kami ng isa-isa listahan ng mga link node sa labas ng manipis na hangin,
at ngayon kami ay may isang listahan na maaari naming magtrabaho sa.
>> Ngayon, sabihin natin na namin na magkaroon ng isang malaking chain,
at gusto naming mahanap ang isang bagay sa loob nito.
At gusto namin ang isang function na pupuntahan upang bumalik true o false, depende
sa kung umiiral na ang isang halaga sa listahang iyon.
Ang isang function prototype, o deklarasyon para sa na function,
maaaring magmukhang this-- bool mahanap, at pagkatapos ay nais naming ipasa sa dalawang argumento.
>> Ang una, ay isang pointer sa unang elemento ng naka-link na listahan.
Ito ay talagang isang bagay na makikita mo laging nais na subaybayan,
at ang tunay na maaaring maging isang bagay na mong kahit na ilagay sa isang global variable.
Sa sandaling lumikha ka ng listahan, palagi kang, palaging
nais na subaybayan ang mga tunay unang elemento ng listahan.
Sa ganoong paraan maaari kang sumangguni sa lahat ng iba pang elemento sa pamamagitan ng mga sumusunod na lamang ang kadena,
nang hindi na kinakailangang upang panatilihin ang mga payo buo sa bawat solong elemento.
Kailangan mo lamang na subaybayan ang mga unang isa kung ang lahat ng mga ito ay chained magkasama.
>> At pagkatapos ay ang ikalawang bagay kami ay pagpasa sa muli
ay nagkataon some-- kahit anong uri ng data hindi namin
naghahanap para sa may loob ng sana isa sa mga node sa listahan.
Kaya ano ang mga hakbang na ito?
Well, ang unang bagay na ginagawa namin ay lumikha kami ng isang transversal pointer
nakaturo sa mga listahan ng ulo.
Well, bakit ginagawa namin na, kami ay magkaroon ng isang pointer sa listahan ulo,
bakit hindi lamang ilipat namin ang isa na sa paligid?
Well, tulad ng sinabi ko, ito ay talagang mahalaga para sa amin
na laging subaybayan ang pinakaunang elemento sa listahan.
At kaya ito ay aktwal na mas mahusay na upang lumikha ng isang dobleng ng iyon,
at gamitin iyon upang gumalaw sa paligid kaya hindi namin sinasadyang ilipat ang layo, o kami ay palaging
magkaroon ng isang pointer sa ilang mga punto na karapatan sa unang elemento ng listahan.
Kaya ito ay mas mahusay na upang lumikha ng isang pangalawang isa na ginagamit namin upang ilipat.
>> Pagkatapos ay ihambing lang namin kung ang halaga ng field sa na node
ay kung ano ang aming hinahanap, at kung ito ay hindi, lamang ilipat namin sa susunod na node.
At patuloy na namin ang paggawa na loob, at higit, at higit,
hanggang namin mahanap ang alinman sa ang elemento, o pindutin namin
null-- naabot na namin ang dulo ng listahan at ito ay hindi doon.
Ito ay dapat sana ng singsing na kampanilya sa iyo bilang lang linear paghahanap,
lang kami Kinokopya ang mga ito sa isang isa-isa na naka-link structure listahan
sa halip ng paggamit ng isang hanay upang gawin ito.
>> Kaya narito ang isang halimbawa ng isang isa-isa naka-link na listahan.
Isa na ito ay binubuo ng limang nodes, at kami ay
isang pointer sa pinuno ng listahan, na kung saan ay tinatawag na listahan.
Ang unang bagay na gusto naming gawin ay muli, lumikha na traversal pointer.
Kaya tayo ngayon ay dalawang payo sa puntong iyon sa parehong bagay.
>> Ngayon, mapapansin din dito, ako ay hindi kung malloc anumang puwang para trav.
Hindi ko sabihin trav katumbas malloc ang isang bagay, mayroon na node,
na espasyo sa memory ay mayroon na.
Kaya lahat talaga ako ng paggawa ay paglikha ng isa pang pointer sa mga ito.
Hindi ko mallocing isang karagdagang space, mayroon na lamang ngayon ng dalawang mga payo
na tumuturo sa parehong bagay.
>> Kaya ay 2 ano Naghahanap ako para sa?
Well, hindi, kaya sa halip na Ako pagpunta upang lumipat sa susunod na isa.
Kaya talaga sasabihin ko, trav katumbas trav susunod.
Ay 3 ano Naghahanap ako, hindi.
Kaya patuloy kong pumunta pamamagitan, hanggang sa huli
makakuha ng hanggang 6 na kung saan ay kung ano Naghahanap ako para sa batay sa function ng tawag
Mayroon akong sa tuktok doon, at kaya ako tapos na.
>> Ngayon, paano kung ang element Ako hinahanap ay wala sa listahan,
Pupunta pa rin ito sa trabaho?
Well, mapapansin na ang listahan dito ay subtly naiiba,
at ito ay isa pang bagay na mahalaga na may naka-link na mga listahan,
hindi mo na kailangang upang mapanatili ang mga ito sa anumang partikular na order.
Maaari mo kung nais mo, ngunit maaaring mayroon ka napansin
na hindi kami ay nag-iingat ng track ng ano ang bilang element na tayo sa.
>> At iyon ay uri ng isa sa kalakalan na tayo Mayroon na may listahan ng mga link talatang array,
ay ito wala tayong random access anymore.
Hindi lamang namin maaaring sabihin, gusto ko upang pumunta sa 0 element,
o ika-6 na elemento ng aking array, kung saan ang maaari kong gawin sa isang array.
Hindi ko masabi na gusto kong pumunta sa 0 element, o ika-6 na elemento,
o ang ika-25 na sangkap ng aking listahan na naka-link, walang index kaugnay sa kanila.
At kaya ito ay hindi tunay bagay kung namin panatilihin ang aming listahan sa order.
Kung nais mong iyo ay tiyak na makakaya, ngunit mayroong
walang dahilan kung bakit kailangan nila upang hindi mapangalagaan sa anumang pagkakasunud-sunod.
Kaya muli, sabihin subukan at hanapin 6 sa listahan na ito.
Well, kami ay magsisimula sa simula, hindi namin mahanap ang 6,
at pagkatapos ay hindi namin magpatuloy sa paghahanap 6, hanggang sa huli kami makarating sa dito.
Kaya karapatan trav ngayon points sa node na naglalaman ng 8, at anim na ito ay hindi sa doon.
>> Kaya ang susunod na hakbang ay upang pumunta sa susunod na pointer,
kaya sabihin trav katumbas trav susunod.
Well, trav susunod, na ipinapahiwatig ng ang pulang kahon doon, ay null.
Kaya may ibang tao na wala sa pumunta, at kaya sa puntong ito
maaari naming tapusin na naabot na namin ang sa dulo ng listahan ng mga link,
at 6 ay hindi sa doon.
At ito ay ibabalik false sa kasong ito.
>> OK, paano ipasok namin ang isang bagong node sa listahan ng mga link?
Kaya nagawa naming upang lumikha ng isang listahan ng mga link sa labas ng wala,
ngunit malamang na gusto naming bumuo ng isang hanay at hindi
lumikha ng isang grupo ng mga natatanging mga listahan.
Gusto naming magkaroon ng isang listahan na ay may isang bungkos ng mga node sa loob nito,
hindi isang grupo ng mga listahan na may isang solong node.
Kaya hindi lamang namin ay maaaring panatilihin ang paggamit ng Lumikha function na tinukoy ng mas maaga kami, ngayon kami
nais na ipasok sa isang list na mayroon na.
>> Kaya kasong ito, kami ay pagpunta upang pumasa sa dalawang argumento,
ang pointer sa pinuno ng na listahan ng mga link na gusto naming idagdag sa.
Muli, na ang dahilan kung bakit ito ay kaya Mahalaga na tayo ay palaging
subaybayan ang mga ito, dahil ito ay ang tanging paraan na kami ay talagang
kung sumangguni sa buong listahan ay sa pamamagitan lamang ng isang pointer sa unang elemento.
Kaya gusto namin upang pumasa sa isang pointer sa na unang elemento,
at kahit anong halaga natin nais na idagdag sa listahan.
At sa huli ang function na ito ay pagpunta upang magbalik ng pointer
na ang bagong pinuno ng isang naka-link na listahan.
>> Ano ang mga hakbang na kasangkot dito?
Well, tulad ng sa lumikha, kailangan namin upang magilas na magtalaga
space para sa isang bagong node, at suriin upang matiyak na hindi kami maubusan ng memory, muli,
dahil kami ay gumagamit ng malloc.
Pagkatapos na nais naming i-populate at ipasok ang node,
kaya ilagay ang numero, kahit na ano Val ay, sa node.
Gusto naming ipasok ang node sa simula ng naka-link na listahan.
>> May dahilan na ako gusto mong gawin ito, at ito
maaaring karapat-dapat sa pagkuha ng isang pangalawang upang i-pause ang video dito,
at sa tingin tungkol sa kung bakit Gusto ko nais na ipasok sa simula ng isang naka-link
listahan.
Muli, nabanggit ko mas maaga na ito ay hindi tunay
mahalaga kung namin panatilihin ang mga ito sa anumang order, kaya marahil na isang palatandaan.
At nakita mo kung ano ang mangyayari kung namin Nais to-- o mula sa isang segundo lamang
nakalipas kapag kami ay pagpunta sa pamamagitan ng paghahanap sa iyo
maaaring makita kung ano ang maaaring mangyayari kung kami ay nagsisikap
upang magsingit ng sa dulo ng listahan.
Dahil hindi namin ay may isang pointer sa dulo ng listahan.
>> Kaya ang dahilan na gusto ko gusto upang ipasok sa simula,
ay dahil ang maaari kong gawin ito kaagad.
Mayroon akong isang pointer sa simula, at kami ay makita ito sa isang visual na sa isang segundo.
Ngunit kung gusto kong ipasok sa dulo, Kailangan ko bang magsimula sa simula,
tawirin ang lahat ng mga paraan upang ang end, at pagkatapos ay tak ito sa.
Kaya na ay nangangahulugan na pagpasok sa dulo ng listahan
ay maging isang o ng n operasyon, balik
sa aming mga talakayan ng computational kumplikado.
Gusto itong maging isang o ng n operasyon, na kung saan ang bilang ang listahan nakuha ng mas malaki, at mas malaki,
at mas malaki, makikita ito maging mas at mas mahirap sa tak bagay
on sa dulo.
Ngunit ito ay palaging tunay madali sa tak ng isang bagay sa sa simula,
ikaw ay palaging sa simula.
>> At kami na makita ang isang visual ng mga ito muli.
At pagkatapos ay sa sandaling tapos na kami, sa sandaling nakapasok na namin ang bagong node,
gusto naming ibalik ang aming pointer sa ang bagong ulo ng isang listahan ng mga link, na kung saan
dahil kami ay pagpasok sa simula, ay tunay na maging
isang pointer sa node na nilikha namin lamang.
Ni maisalarawan na ito, dahil sa tingin ko na ito ay tumulong.
>> Kaya narito ang aming listahan, ito ay binubuo ng apat na mga sangkap, ang isang node na naglalaman ng 15,
na puntos sa isang node na naglalaman ng 9, na
puntos sa isang node na naglalaman ng 13, na puntos sa isang node na naglalaman ng
10, na kung saan ay may mga null pointer bilang kanyang susunod na pointer
kaya iyon ang katapusan ng listahan.
Kaya gusto namin upang magsingit ng isang bagong node sa halaga 12
sa simula ng ito list, ano ang gagawin namin?
Well, unang-malloc namin na puwang para sa node, at pagkatapos ay inilalagay namin 12 sa doon.
>> Kaya ngayon naabot na namin ang isang desisyon point, right?
Kami ay may isang pares ng mga mga payo na maaaring namin
ilipat, kung saan ang isa ay dapat munang ilipat namin?
Dapat gawin namin ang 12 point sa ang bagong ulo ng list--
o excuse me, dapat naming gumawa ng 12 point sa lumang ulo ng listahan?
O kaya dapat naming sabihin na ang list na ngayon ay nagsisimula sa 12.
Mayroong isang pagkakaiba doon, at kami ay tumingin
sa kung ano ang mangyayari sa parehong sa isang segundo.
>> Ngunit ito ay humahantong sa isang mahusay na paksa para sa sidebar,
na kung saan ay na ang isa sa mga trickiest bagay na may mga listahan ng link
ay upang ayusin ang mga payo sa tamang pagkakasunod-sunod.
Kung ililipat mo ang mga bagay-bagay sa labas ng order, maaari mong tapusin up sinasadyang
orphaning ang natitirang bahagi ng listahan.
At narito ang isang halimbawa ng na.
Kaya sabihin pumunta sa mga ideya of-- well, ako lamang nilikha namin 12.
Alam namin 12 ay magiging ang bagong ulo ng listahan,
at sa gayon bakit hindi ilipat namin lamang listahan pointer upang tumuro doon.
>> OK, sa gayon ay maganda.
Kaya ngayon kung saan ay 12 susunod point?
Ibig kong sabihin, biswal maaari naming makita na ito ay tumuturo sa 15,
bilang mga tao na ito ay talagang halata sa amin.
Paano nalalaman ng computer?
Wala kaming anumang bagay tumuturo sa 15 anymore, right?
>> Nawala namin ang anumang kakayahan na mag-refer sa 15.
Hindi namin sinasabi bagong arrow sa tabi equals isang bagay, walang may.
Sa katunayan, na naulila namin ang natitirang bahagi ng listahan
sa pamamagitan ng paggawa nito, na namin sinasadyang nasira ang kadena.
At kami ay tiyak na hindi mo nais na gawin iyon.
>> Kaya sabihin bumalik at subukan muli.
Siguro ang tamang gawin ay mag-set ng 12 ni susunod na pointer
sa lumang ulo ng listahan ng una, pagkatapos ay maaari naming ilipat ang mga listahan ng higit.
At sa katunayan, iyon ay ang tamang pagkakasunod-sunod na tayo
kailangang sundin kung hindi namin nagtatrabaho sa isa-isa na naka-link na listahan.
Lagi kaming nais na ikonekta ang mga bagong elemento sa listahan,
bago kami gumawa ng na uri ng mahalagang hakbang ng pagbabago
kung saan ang ulo ng listahan ng mga link ay.
Muli, na tulad ng isang pangunahing bagay, Hindi namin nais na mawala sa pagsubaybay ng mga ito.
>> Kaya gusto naming siguraduhin na ang lahat ng bagay ay chained magkasama,
bago namin ilipat na pointer.
At kaya ito ay ang tamang pagkakasunod-sunod, na kung saan ay upang ikonekta ang 12 sa listahan,
pagkatapos ay sabihin na ang listahan ay nagsisimula sa isang 12.
Kung namin sinabi ang listahan ay nagsisimula sa 12 at pagkatapos ay sinubukan upang kumonekta 12 sa listahan,
na namin nakita kung ano ang mangyayari.
Nawala namin ang listahan sa pamamagitan ng pagkakamali.
>> OK, kaya ang isa pang bagay na makipag-usap tungkol sa.
Paano kung gusto namin upang magtanggal ng isang buong listahan ng mga link sa isang beses?
Muli, kami ay mallocing lahat ng puwang na ito, at kaya namin
kailangan upang magbakante ito kapag tapos na kami.
Kaya ngayon gusto naming tanggalin ang buong listahan ng mga link.
Well, ano ang gusto naming gawin?
>> Kung naabot na namin ang null pointer, namin gusto mong itigil, kung hindi man, tanggalin lamang
ang natitirang bahagi ng listahan at pagkatapos ay libre ako.
Burahin ang natitirang bahagi ng listahan, at pagkatapos ay libre ang kasalukuyang node.
Ano ang ibig sabihin na ang tunog tulad ng, kung ano ang pamamaraan ay may usapan natin
tungkol sa dati na ang tunog tulad ng?
Tanggalin ang lahat ng iba pa, at pagkatapos ay bumalik at tanggalin sa akin.
>> Iyan ay recursion, ginawa naming ang problema ng isang maliit na piraso ng mas maliit,
namin sinasabi tanggalin ang lahat ng tao iba pa, pagkatapos ay maaari mong tanggalin sa akin.
At mas ibaba pa ng kalsada, na node sasabihin ng iba, tanggalin lahat ng iba pa.
Ngunit sa huli babalikan ka namin sa punto kung saan ang listahan ay null,
at iyon ang aming base kaso.
>> Kaya sabihin kumuha ng isang pagtingin sa ito, at kung paano ito maaaring gumana.
Kaya narito ang aming listahan, ito ay ang parehong listahan namin ay pakikipag-usap lamang tungkol sa,
at mayroong mga hakbang.
May isang pulutong ng mga teksto dito, ngunit inaasahan namin na ang visualization ay makakatulong.
>> Kaya have-- kami at hinila ko rin up aming stack frame na paglalarawan
mula sa aming mga video sa mga stack ng tawag, at sana ang lahat ng ito
magkasama ay magpapakita sa iyo kung ano ang nangyayari sa.
Kaya narito ang aming pseudocode code.
Kung naabot namin ang isang null pointer, stop, sa kabilang banda,
tanggalin ang natitirang bahagi ng listahan, pagkatapos ay libre ang kasalukuyang node.
Kaya ngayon, list-- ang pointer na hindi namin
pagpasa sa upang sirain ang mga puntos sa 12.
12 ay hindi isang null pointer, kaya kami ay pagpunta sa tanggalin ang natitirang bahagi ng listahan.
>> Ano ang pagtanggal ng mga iba sa atin na kasangkot?
Well, ito ay nangangahulugan ng paggawa ng isang tumawag upang sirain, na sinasabi
na ang 15 ay ang simula ng natitirang bahagi ng listahan na gusto namin upang sirain.
At upang ang mga tawag upang sirain 12 ay uri ng on hold.
Ito ay frozen doon, naghihintay para sa mga tumawag upang sirain 15, upang tapusin ang kanyang trabaho.
>> Well, 15 ay hindi isang null pointer, at kaya ito ay pagpunta sa sabihin, lahat ng karapatan,
, tanggalin muna ang natitirang bahagi ng listahan.
Ang natitirang bahagi ng listahan nagsisimula sa 9, at iba idedetalye namin lamang
maghintay hanggang sa tanggalin mo ang lahat na mga bagay-bagay, at pagkatapos ay bumalik at tanggalin sa akin.
Well 9 ay pagpunta sa sabihin, well, Hindi ako isang null pointer,
kaya tanggalin ang mga natitirang ang listahan mula dito.
At kaya subukan at sirain 13.
13 sabi, hindi ako null pointer, parehong bagay, ito pumasa sa usang lalaki.
10 ay hindi null pointer, 10 naglalaman ng isang null pointer,
ngunit 10 ay hindi mismo ng null pointer sa ngayon,
at kaya ito pumasa sa usang lalaki masyadong.
>> At ngayon ilista points doon, ito talagang ay tumuturo sa some--
kung ako ay mas maraming espasyo sa imahe, ito ay tumuturo sa ilang mga random na space
na hindi namin alam kung ano ito.
Ito ay ang null pointer bagaman, ang listahan Literal na ngayong itakda ito ay mga halaga null.
Ito ay tumuturo sa loob mismo na red box.
Naabot namin ang isang null pointer, kaya maaari naming ihinto, at tapos na kami.
>> At upang ang purple frame ay now-- sa tuktok ng stack-- iyon ang aktibong frame,
ngunit ito ay tapos na.
Kung naabot na namin ang isang null pointer, itigil.
Hindi namin gumawa ng anumang bagay, kami hindi maaaring magbakante ng isang null pointer,
hindi namin ginawa malloc anumang space, at sa gayon kami ay tapos na.
Kaya na function na frame ay nasira, at tayo
resume-- pick up namin kung saan kami iniwan off sa susunod na pinakamataas na isa, na
ay ang madilim na asul na frame dito.
Kaya namin kukunin ang karapatan kung saan namin kaliwa off.
Tinanggal namin ang natitirang bahagi ng list na, kaya ngayon kami ay
pagpunta sa magbakante ang kasalukuyang nodes.
Kaya ngayon maaari naming magbakante ito node, at ngayon naabot na namin ang dulo ng function.
At upang ang mga function na frame ay pupuksain, at kunin natin ang isa mapusyaw na asul.
>> Kaya ito ako says-- na ako na done-- tinatanggal ang natitirang bahagi ng listahan, kaya
libre ang kasalukuyang node.
At ngayon, ang dilaw na frame ay bumalik sa tuktok ng stack.
At kaya tulad ng nakikita mo, hindi namin ngayon pagsira sa mga listahan mula sa karapatan sa kaliwa.
>> Ano kaya ang nangyari, bagaman, kung kami ay tapos na bagay sa maling paraan?
Katulad ng kapag sinubukan naming upang magdagdag ng isang elemento.
Kung messed up namin ang kadena, kung hindi namin ay ikonekta ang mga payo
sa tamang pagkakasunod-sunod, kung tayo napalaya lang ang unang elemento,
kung napalaya lang namin ang ulo ng listahan, ngayon kami
ay walang paraan upang tumukoy sa ang natitirang bahagi ng listahan.
At kaya kami ay may naulila lahat ng bagay,
Gusto namin ay may kung ano ang tinatawag na isang memory tumagas.
Kung isipin ang mo mula sa aming mga video sa dynamic memory laang-gugulin,
na hindi masyadong magandang bagay.
>> Kaya tulad ng sinabi ko, may ilang mga operasyon
na kailangan namin upang gamitin sa trabaho may listahan na naka-link nang epektibo.
At maaari mong napansin na tinanggal ko ang isa, pagtanggal ng isang solong elemento mula sa isang naka-link
listahan.
Ang dahilan ko na ay ito ay aktwal na uri ng
nakakalito na mag-isip tungkol sa kung paano tanggalin ang isang solong elemento mula sa isang isa-isa
naka-link na listahan.
Kailangan namin upang ma-laktawan ang higit isang bagay sa listahan, na
nangangahulugan makuha namin sa isang point-- namin nais na tanggalin ito node--
ngunit upang gawin ito upang tayo huwag mawalan ng anumang impormasyon,
kailangan namin upang ikonekta ito node sa paglipas dito, dito.
>> Kaya marahil ginawa ko na mali mula sa isang visual na pananaw.
Kaya hindi namin sa simula ng aming listahan, kami ay magpatuloy sa pamamagitan ng,
gusto naming tanggalin ito node.
Kung tatanggalin namin ito lamang, nasira na namin ang kadena.
Node Ito karapatan dito ay tumutukoy sa lahat ng iba pa,
naglalaman ito ng mga kadena mula dito sa labas.
>> Kaya kung ano ang kailangan namin upang gawin ang tunay na pagkatapos naming makarating sa puntong ito,
ay kailangan namin sa hakbang likod ng isa, at ikonekta ito node sa ibabaw sa node na ito,
upang maaari naming pagkatapos ay tanggalin ang isa sa gitna.
Ngunit isa-isa mga listahan ng link ay hindi ay nagbibigay sa amin ng isang paraan upang pumunta paurong.
Kaya kailangan namin upang panatilihin ang alinman sa dalawang payo, at ilipat ang mga ito
uri ng off-hakbang, isa sa likod ng iba pang mga bilang pumunta kami, o makakuha ng sa isang punto
at pagkatapos ay magpadala ng isa pang pointer sa pamamagitan ng.
At bilang maaari mong makita, ito ay maaaring makakuha ng isang maliit na makalat.
Sa kabutihang palad, kami ay isa pang paraan upang malutas na,
kapag kami makipag-usap tungkol sa mga doble-link list.
>> Ako Doug Lloyd, ito ay CS50.