[Daqq tal-mużika] 

Doug LLOYD: OK, so fuq dan il-punt fil-kors, konna koperti ħafna ta 'l-baŜi ta C. Nafu ħafna dwar varjabbli, arrays, pointers, dak kollu li Jittieħed tajba. Dawk huma kollha tip ta 'mibnija biex tara kif l-prinċipji fundamentali, iżda nistgħu nagħmlu aktar, id-dritt? Nistgħu jgħaqqdu affarijiet flimkien b'modi interessanti. 

U hekk ejja tagħmel dan, Nibdew li l-fergħa ta 'dak C tagħtina, u tibda biex joħolqu data tagħna stess istrutturi bl-użu dawn bini blokki flimkien biex jagħmlu xi ħaġa tassew siewja, utli. Mod wieħed nistgħu nagħmlu dan hu biex jitkellmu dwar kollezzjonijiet. Allura s'issa aħna kellna tip wieħed ta 'data struttura għal jirrappreżenta kollezzjonijiet ta 'prodotti simili valuri, valuri simili. Dan ikun firxa. Aħna kollezzjonijiet tan-numri interi, jew kollezzjonijiet ta 'karattri u l-bqija. 

Strutturi huma wkoll sort ta 'data struttura għal ġbir ta 'informazzjoni, iżda mhux għall-ġbir bħal valuri. Normalment taħlitiet tipi differenti ta 'dejta flimkien ġewwa ta 'kaxxa waħda. Imma din mhix fiha nnifisha użati biex katina flimkien jew qabbad flimkien simili oġġetti, bħal firxa. Arrays huma kbira għall element wieħed ifittex, iżda recall li huwa diffiċli ħafna li ddaħħal fil-firxa, sakemm aħna qed ddaħħal fil l-aħħar stess ta 'din array. 

U l-aħjar eżempju I jkollhom għal dan hija tip inserzjoni. Jekk inti recall vidjo tagħna fuq sort inserzjoni, kien hemm ħafna ta ' ispejjeż li huma involuti jkollhom li jtellgħu l-elementi, u tbiddilhom barra mill-mod li jitwaħħal xi ħaġa fis-nofs ta 'firxa tiegħek. Arrays ibatu wkoll minn ieħor problema, li hija inflessibbiltà. Meta aħna niddikjaraw firxa, nikbru wieħed maqtul fiha. Nikbru ngħid, nixtieq dan ħafna elementi. Jista 'jkun ta' 100, jista ' tkun 1000, jista ' jkun x fejn x huwa numru li l-utent tana fi pront jew fuq kmand linja. 

Iżda aħna biss jiksbu sparatura waħda lejn dan, aħna ma jsibux li mbagħad jgħidu oh, fil-fatt I meħtieġa 101, jew I meħtieġa x plus 20. Tard wisq, konna diġà ddikjarat il- firxa, u jekk aħna rridu nġibu 101 jew x plus 20, irridu jiddikjaraw firxa kompletament differenti, kopja l-elementi kollha tal-firxa fuq, u allura għandna biżżejjed. U jekk dak li aħna huma żbaljati mill-ġdid, dak jekk aħna verament bżonn 102, jew x plus 40, għandna nagħmlu dan mill-ġdid. Allura jkunu inflessibbli ħafna għall ristrutturazzjoni data tagħna, imma jekk aħna ngħaqqdu flimkien xi mill-affarijiet bażiċi li aħna stajt diġà tgħallmu dwar pointers u strutturi, partikolarment bl-użu tal-memorja dinamika allokazzjoni ma malloc, aħna tista 'tpoġġi dawn il-biċċiet flimkien li jinħoloq data ġdida structure-- a weħidhom lista nistgħu say-- marbuta li jippermetti li jikbru u tiċkien ġabra ta 'valuri u aħna mhux se jkollhom xi spazju moħli. 

Għalhekk għal darb'oħra, nagħmlu sejħa din l-idea, dan il-kunċett, lista marbuta. B'mod partikolari, f'dan il-video aħna qed jitkellem dwar lista marbuta waħdu, u mbagħad ieħor video aħna ser nitkellmu listi dwar doppjament marbuta, li huwa biss varjazzjoni fuq tema hawn. Iżda lista marbuta weħidhom huwa magħmul minn lymph, nodes sempliċement l term-- astratt huwa biss xi ħaġa jien ssejjaħ li l-tip ta ' istruttura, bażikament, jien? Biss se sejħa hija ta 'node-- u dan node għandha żewġ membri, jew żewġ oqsma. Hija għandha data, normalment numru sħiħ, float karattru, jew jista 'jkun xi tip data oħra li inti stajt definit bi def tip. U fiha pointer li node oħra tal-istess tip. 

Allura aħna għandna żewġ affarijiet ġewwa tal dan node, data u pointer li node ieħor. U jekk inti tibda biex Ħares dan, inti tista 'taħseb dwarha bħal katina ta 'punti ta' konġunzjoni li huma konnessi flimkien. Għandna l-ewwel node, huwa fih data, u pointer għat-tieni node, li fih data, u werrej li għat-tielet node. U hekk huwa għalhekk li għandna sejħa hija ta ' lista marbuta, dawn qed marbuta flimkien. 

Xi jfisser dan speċjali istruttura node look like? Ukoll, jekk inti recall mill-video tagħna fuq jiddefinixxu tipi dwana, bl def tip, nistgħu jiddefinixxu structure-- u tip jiddefinixxu struttura bħal din. tyepdef sllist Struct, u allura jien permezz tal-valur kelma hawn arbitrarju biex jindikaw kwalunkwe tip ta 'data verament. Inti tista 'tgħaddi fuq numru sħiħ jew float, inti jista 'jkollhom xi trid. Huwa mhux ristrett għal ftit interi, jew xi ħaġa bħal dik. Allura valur huwa biss arbitrarju tip ta 'data, u mbagħad pointer li node ieħor tal-istess tip. 

Issa, hemm qabda ftit hawn ma tiddefinixxi struttura meta huwa struttura referenzjali awto. I għandhom ikollhom temporanju isem għall-istruttura tiegħi. Fl-aħħar tal-ġurnata I b'mod ċar tixtieq li hija sejħa node sll, li finalment l-ġdida isem parti tad-definizzjoni tip tiegħi, imma I ma tistax tuża node SLL fin-nofs ta 'dan. Ir-raġuni li, I ma jkunux ħolqot tip imsejjaħ node SLL sal I hit dan il-punt finali hawnhekk. Sa dak il-punt, I għandhom ikollhom mod ieħor biex jirreferi għal dan it-tip tad-data. 

U dan huwa awto tip ta 'data referenzjali. Hija; i tip tad-data ta ' struttura li fiha data, u pointer għall-ieħor istruttura tal-istess tip. So I jeħtieġu li jkunu jistgħu jirreferu għal dan it-tip tad-data almenu temporanjament, għalhekk jtuha temporanju isem ta sllist Struct tippermetti me imbagħad ngħid Irrid pointer li sllist ieħor Struct, stilla sllist Struct, u mbagħad wara Stajt kompletati id-definizzjoni, I issa tista 'sejħa dan it-tip ta' node SLL. 

Allura hu għalhekk li inti tara hemm isem temporanju hawn, iżda isem permanenti hawn. Kultant inti tista 'tara definizzjonijiet ta 'struttura, per eżempju, li mhumiex referenzjali innifsu, dan ma jkollhomx isem specifier hawn. Ikun biss jgħidu Struct typedef, miftuħa kaboċċi Brace u mbagħad jiddefinixxu dan. Imma jekk int Istituzzjonjijiet hija awto referenzjali, kif dan huwa wieħed, għandek bżonn biex tispeċifika isem tip temporanja. Iżda fl-aħħar, issa li aħna ghamilt dan, nistgħu jirreferu biss għall dawn in-nodi, dawn l-unitajiet, ta 'punti strateġiċi sll għal skopijiet tal-bqija ta 'dan il-video. 

Kull dritt, hekk nafu kif tinħoloq node lista marbuta. Nafu kif għandu jkun definit a node lista marbuta. Issa, jekk aħna qed tmur biex tibda jużawhom biex jiġbru tagħrif, hemm koppja ta 'operazzjonijiet aħna jeħtieġ li jifhmu u jaħdmu magħhom. Għandna bżonn inkunu nafu kif tinħoloq lista marbut fl-arja irqiq. Jekk hemm l-ebda lista diġà, rridu nibdew wieħed. Għalhekk għandna bżonn li jkunu kapaċi biex joħolqu lista marbuta, għandna bżonn li probabbilment tfittex permezz tal-lista link biex issib element aħna qed tfittex. Għandna bżonn li tkun tista 'tiddaħħal affarijiet ġodda fil-lista, irridu lista tagħna biex ikunu jistgħu jikbru. U l-istess, irridu nkunu kapaċi li tħassar affarijiet mill-lista tagħna, irridu lista tagħna biex ikunu jistgħu tiċkien. U fl-aħħar ta 'tagħna programmi, speċjalment jekk inti recall li aħna qed dinamikament allokazzjoni memorja biex jibnu dawn il-listi tipikament, irridu biex ħielsa kollha ta 'dak memorja meta aħna qed isir jaħdmu magħha. U għalhekk għandna bżonn li tkun tista 'tħassar l Lista marbuta sħiħa f'waħda jonqsu swoop. Mela ejja jmorru permezz xi wħud minn dawn l-operazzjonijiet u kif nistgħu Ħares minnhom, jitkellem fil-kodiċi pseudocode speċifikament. Allura aħna tixtieq li toħloq marbuta lista, hekk forsi aħna tixtieq li jiddefinixxu funzjoni ma 'dan prototip. sll star node, joħolqu, u jien tgħaddi fi argument wieħed, xi data arbitrarja tip ġdid, ta 'xi tip ta' data arbitrarja. Imma jien returning-- din il-funzjoni għandhom ritorn għall me pointer, għal weħidhom node lista marbuta. Għal darb'oħra, aħna qed tipprova toħloq lista marbut fl-arja irqiq, so I bżonn pointer li dik il-lista meta jien jsir. 

Allura x'inhuma l-passi kollha involuti hawn? Ukoll, l-ewwel ħaġa jien ser tagħmel hu dinamikament jalloka territorju għal node ġdid. Għal darb'oħra, aħna qed joħolqu out ta 'irqiq arja, għalhekk għandna bżonn għall-ispazju malloc għal dan. U ovvjament, minnufih wara we malloc, aħna dejjem jivverifika sabiex ikun żgur li tagħna Pointer aħna ma jiksbu lura null. Għaliex jekk nippruvaw u b'rispett pointer null, aħna qed tmur biex jbatu minn segfault u ma rridux li. 

Imbagħad irridu li timla l-qasam, irridu li initialize-qasam valur u initialize-qasam li jmiss. U allura aħna rridu to-- eventwalment bħala l- funzjoni prototip indicates-- irridu li jirritornaw pointer għal node SLL. Allura dak li tagħmel dan look like viżwalment? Ukoll, qabel aħna qed tmur biex dinamikament jalloka territorju għal node SLL ġdid, hekk aħna malloc-- li l- rappreżentazzjoni viżiva tal-node aħna biss maħluqa. U aħna jivverifika sabiex ikun żgur mhuwiex null-- f'dan il-każ, l-istampa ma jkollhomx muri up jekk kien null, aħna kieku jispiċċaw ta 'memorja, hekk aħna qed tajba li jmorru hemm. Allura issa aħna qed dwar li pass C, initialize-qasam valur lymph. Ukoll, ibbażata fuq din il-funzjoni sejħa Jien jużaw hawnhekk, qisu Irrid li jgħaddu 6, so I ser 6 fil-qasam tal-valur. Issa, initialize-qasam li jmiss. Ukoll, dak li jien ser tagħmel hemmhekk, m'hemm xejn li jmiss, id-dritt, dan huwa l-unika ħaġa fil-lista. Allura x'inhu l-ħaġa li jmiss fil-lista? 

M'għandux punt għal xejn, id-dritt. M'hemm xejn hemm, iva, liema huwa il-kunċett nafu li l-nothing-- indikaturi għall-xejn? Għandu jkun forsi rridu li jitqiegħed pointer null hemm, u jien ser jirrappreżentaw il-null pointer biss bħala kaxxa aħmar, aħna ma tistax tmur aktar. Kif aħna ser tara ftit aktar tard, se jkollna eventwalment ktajjen ta vleġeġ konnessjoni dawn in-nodi flimkien, imma meta inti laqat il- kaxxa aħmar, li null, aħna ma tistax tmur aktar, dak l-aħħar tal-lista. 

U fl-aħħar, aħna biss jixtiequ ritorn pointer għal dan node. Allura aħna ser sejħa hija ġdida, u se terġa 'lura ġdida sabiex ikun jista 'jintuża fil tkun xi tkun il-funzjoni maħluqa minnha. Allura hemm immorru, Imxejna ħolqot weħidhom marbuta lista node fl-arja irqiq, u issa għandna lista nistgħu naħdmu magħhom. 

Issa, ejja ngħidu aħna diġà ikun hemm katina kbar, u rridu li ssib xi ħaġa fiha. U rridu funzjoni li għaddej li jirritornaw vera jew falza, jiddependi dwar jekk il-valur jeżisti f'dik il-lista. A prototip funzjoni, jew b'dikjarazzjoni għal dik il-funzjoni, jista 'dehra this-- BOOL isibu, u imbagħad irridu jgħaddu f'żewġ argumenti. 

L-ewwel, huwa pointer għall- ewwel element tal-lista marbuta. Dan huwa attwalment xi ħaġa tkun taf dejjem tixtieq li jżommu rekord ta ', u fil-fatt jista 'jkun xi ħaġa li inti anke tpoġġi fil-varjabbli globali. Ladarba inti toħloq lista, inti dejjem, dejjem tixtieq li jżommu rekord ta 'l-ħafna ewwel element tal-lista. B'dak il-mod inti tista 'tirreferi għal kulħadd l-oħra Elementi bi ftit wara l-katina, mingħajr ma jkollhom iżommu pointers intatti għal kull element wieħed. Ghandek bzonn biss li jżommu rekord ta 'l-ewwel wieħed jekk dawn qed kollha b'katina flimkien. 

U allura l-ħaġa tieni aħna qed tgħaddi fl-ġdid huwa arbitrarju some-- kwalunkwe tip data nkunu tfittex hemm ġewwa tal nisperaw wieħed mill-lymph fil-lista. Allura x'inhuma l-passi? Ukoll, l-ewwel ħaġa li għandna nagħmlu huwa noħolqu pointer trasversali tipponta lejn il-kap listi. Well, għaliex għandna nagħmlu dan, aħna diġà jkollhom pointer fil-kap listi, għaliex ma we biss jiċċaqalqu li wieħed madwar? Well, bħal I biss qal, huwa verament importanti għalina li dejjem iżżomm kont ta 'l- ewwel element fil-lista. U dan huwa attwalment aħjar biex joħolqu kopja ta 'dik, u l-użu li jiċċaqalqu hekk aħna qatt aċċidentalment jitbiegħed, jew aħna dejjem jkollhom pointer f'xi punt li huwa dritt fuq l-ewwel element tal-lista. Allura huwa aħjar biex joħolqu tieni waħda li nużaw biex jiċċaqalqu. 

Imbagħad aħna biss iqabbel jekk qasam valur f'dak node huwa dak li aħna qed tfittex, u jekk huwa le, aħna biss jimxu lejn il-node li jmiss. U aħna iżommu tagħmel dak fuq, u aktar, u aktar, sakemm aħna kemm issib l-element, jew aħna hit null-- konna laħqu t-tmiem tal-lista u mhuwiex hemmhekk. Dan għandu nisperaw ring qanpiena lilek bħala biss tfittxija lineari, aħna qed biss jirreplikaw fil struttura lista marbuta weħidhom minflok jużaw firxa biex tagħmel dan. 

Allura hawnhekk eżempju ta ' lista marbuta weħidhom. Dan wieħed jikkonsisti ħames lymph, u għandna a pointer għall-kap tal- lista, li huwa msejjaħ il-lista. L-ewwel ħaġa li rridu nagħmlu huwa għal darb'oħra, joħolqu li l-pointer traversal. Allura aħna għandna issa żewġ pointers dak il-punt għall-istess ħaġa. 

Issa, l-avviż hawnhekk ukoll, I ma għandek malloc kull spazju għall trav. I ma jgħidu trav ugwali malloc xi ħaġa, li node diġà teżisti, li l-ispazju fil-memorja diġà teżisti. Allura kull Jien fil-fatt jagħmlu huwa ħolqien pointer ieħor lilha. Jien ma mallocing addizzjonali ispazju, biss ikollhom issa żewġ pointers tipponta lejn l-istess ħaġa. 

Allura huwa 2 dak li jien tfittex? Well, no, hekk minflok jien ser jiċċaqalqu għal dak li jmiss. Għalhekk bażikament nixtieq ngħid, trav ugwali trav jmiss. Hija ta '3 dak li jien tfittex, no. So I tkompli titla permezz, sakemm eventwalment jiksbu sa 6 li huwa dak li jien tfittex għall ibbażati fuq is-sejħa funzjoni I jkollhom fil-quċċata hemm, u għalhekk jien jsir. 

Issa, dak li jekk l-element jien tfittex ma tkunx fil-lista, huwa xorta sejjer jaħdem? Ukoll, l-avviż li l-lista hawnhekk hija sottili differenti, u dan huwa ħaġa oħra li l- importanti b'listi marbuta, inti ma għandekx biex jippreservaw minnhom fi kwalunkwe ordni partikolari. Tista 'jekk trid, imma jista 'jkollok diġà nnotat li aħna mhux qed iżżomm rekord ta ' liema numru element aħna fuq. 

U dan huwa tip ta 'kummerċ waħda li aħna għandhom flimkien ma 'lista marbuta versi arrays, huwa dan aħna ma jkollhomx aċċess bl-addoċċ aktar. Ma nistgħux biss jgħidu, nixtieq biex tmur fil-element 0, jew il-6 element ta 'firxa tiegħi, li I tista 'tagħmel fil-firxa. Ma nistax ngħid I jridu jmorru għall- Element 0, jew il-6 element, jew l-element 25 tal-lista marbuta tiegħi, hemm ebda indiċi assoċjati magħhom. U għalhekk ma verament kwistjoni jekk aħna tippreserva lista tagħna fl-ordni. Jekk inti tixtieq li int ċertament jista ', iżda hemm ebda raġuni għaliex jeħtieġ li jiġu ppreservati fi kwalunkwe ordni. Għalhekk għal darb'oħra, ejja jippruvaw u isibu 6 f'din il-lista. Well, aħna tibda fil- bidu, aħna ma jsibu 6, u allura aħna jibqgħu mhux konstatazzjoni 6, sakemm aħna eventwalment jiksbu l hawn. Punti issa TRAV hekk dritti għal-node li jikkontjeni 8, u sitta ma jkunx fil hemmhekk. 

Allura l-pass li jmiss ikun biex tmur fil-pointer li jmiss, hekk jgħidu trav ugwali trav jmiss. Ukoll, trav jmiss, indikat mill il-kaxxa aħmar hemm, huwa null. Allura hemm imkien ieħor biex go, u għalhekk f'dan il-punt nistgħu nikkonkludu li konna laħaq l-aħħar tal-lista marbuta, u 6 mhijiex fil hemmhekk. U jkun ritornat falza f'dan il-każ. 

OK, kif nistgħu daħħal ġdida node fil-lista marbuta? Allura aħna kont qed kapaċi joħolqu lista marbut minn imkien, imma aħna probabilment jridu jibnu katina u mhux joħolqu mazz ta 'listi distinti. Irridu li jkollna lista waħda li għandha mazz ta 'punti ta' konġunzjoni fiha, mhux mazz ta 'listi bi node wieħed. Allura ma nistgħux biss iżommu bl-użu Oħloq funzjoni aħna definita qabel, issa aħna tixtieq li daħħal fis- lista li diġà teżisti. 

Allura f'dan il-każ, aħna qed tmur jgħaddu f'żewġ argumenti, l pointer lill-kap ta 'dik marbuta lista li rridu li żżid mal. Għal darb'oħra, dan huwa għaliex huwa daqstant importanti li aħna dejjem iżżomm kont ta 'dan, għaliex huwa l-uniku mod aħna verament għandhom jirreferu għal-lista kollu huwa biss minn pointer għall-ewwel element. Allura rridu jgħaddu fil- pointer għal dak l-ewwel element, u tkun xi tkun il-valur aħna trid iżżid mal-lista. U eventwalment din il-funzjoni se jirritornaw pointer għall-kap il-ġdid ta 'lista marbuta. 

X'inhuma l-passi kollha involuti hawn? Ukoll, bħad bil joħolqu, għandna bżonn li dinamikament allokati spazju għal node ġdid, u jivverifika sabiex ikun żgur aħna ma spiċċawlhiex l-memorja, għal darb'oħra, għaliex aħna qed tuża malloc. Imbagħad irridu li timla u daħħal l-node, sabiex jitqiegħdu in-numru, tkun xi tkun val huwa, fil-node. Aħna rridu li daħħal il-node fil il-bidu tal-lista marbuta. 

Hemm raġuni li I tixtieq li tagħmel dan, u jista 'jkun min jieħu t-tieni biex nieqaf l-video hawn, u jaħsbu dwar għaliex nixtieq li daħħal fil-bidu ta 'marbut lista. Għal darb'oħra, semmejt qabel li ma verament importanza jekk din tkun ippreservata fi kwalunkwe ordni, hekk forsi li l-clue. U inti raw x'jista 'jiġri jekk aħna riedu to-- jew minn ftit tieni ilu meta konna se permezz ta 'riċerka inti tista 'tara dak li jista' jiġri jekk aħna kienu qegħdin jippruvaw li daħħal fl-aħħar tal-lista. Minħabba li aħna ma jkollhomx pointer sa l-aħħar tal-lista. 

Allura r-raġuni li nixtieq li daħħal fil-bidu, huwa għaliex I tista 'tagħmel dan immedjatament. I jkollhom pointer fil-bidu, u Ser naraw dan fil-viżwali fit-tieni. Imma jekk jien tixtieq li daħħal fl-aħħar, I għandhom jibdew fil-bidu, travers-triq kollha lejn il- għan, u mbagħad atteġġjament tagħha fuq. Allura dan ikun ifisser li ddaħħal fl-aħħar tal-lista tkun tista 'ssir o ta n operazzjoni, li tmur lura għad-diskussjoni tagħna ta ' kumplessità komputazzjoni. Hija d issir o ta 'operazzjoni n, fejn bħala l-lista ltqajna akbar, u akbar, u akbar, dan ser isiru aktar u aktar diffiċli biex tindi xi ħaġa fuq fl-aħħar. Iżda huwa dejjem verament faċli biex tindi xi ħaġa fuq fil-bidu, int dejjem fil-bidu. 

U aħna ser tara viżwali ta 'dan mill-ġdid. U allura ladarba aħna qed isir, ladarba konna jiddaħħal l-node ġdid, irridu li jirritornaw pointer tagħna biex il-kap il-ġdid ta 'lista marbuta, li peress li aħna qed ddaħħal fil- bidu, fil-fatt se tkun a pointer għall-node aħna biss maħluqa. Ejja Ħares dan, għaliex naħseb li ser jgħinu. 

Allura hawnhekk lista tagħna, din tikkonsisti erba 'elementi, node fih 15, liema evalwazzjoni għamlet node li jkun fih 9, li jindika node fih 13, liema evalwazzjoni għamlet node fih 10, li għandha l-null pointer bħala pointer li jmiss tagħha b'tali mod li l-aħħar tal-lista. Allura rridu li tiddaħħal node ġdid mal-valur 12 fil-bidu ta 'din lista, dak li nagħmlu? Ukoll, qabel we malloc ispazju għall- node, u allura aħna jitqiegħdu 12 fil hemmhekk. 

Allura issa konna laħaq punt tad-deċiżjoni, id-dritt? Għandna ftit pointers li nistgħu jimxu, li wieħed għandu nimxu ewwel? Jekk nagħmlu 12 punt għal il-kap ġdid tal-list-- jew skuża me, għandu nagħmlu 12 punt li l-kap antika tal-lista? Jew għandna ngħidu li l- Lista issa jibda fil 12. Hemm distinzjoni hemm, u aħna ser tħares lejn dak li jiġri ma 'kemm fit-tieni. 

Iżda dan iwassal għal suġġett kbir għall sidebar, li huwa li wieħed mill- affarijiet trickiest ma 'listi marbuta huwa li jirranġa l-pointers fl-ordni korretta. Jekk inti tiċċaqlaq affarijiet out of order, inti tista 'tispiċċa aċċidentalment orphaning-bqija tal-lista. U hawnhekk eżempju ta 'dak. Mela ejja jmorru mal-idea of-- ukoll, konna biss maħluqa 12. Nafu 12 se tkun il-kap il-ġdid tal-lista, u hekk għaliex ma we biss jiċċaqalqu l pointer lista għall-punt hemmhekk. 

OK, hekk li tajjeb. Allura issa fejn ma 12 punt li jmiss? I mean, viżwalment nistgħu naraw li se punt sa 15, bħala bnedmin huwa verament ovvju għalina. Kif il-kompjuter taf? Aħna ma jkollhom xejn tipponta lejn 15 aktar, id-dritt? 

Imxejna tilfet kull kapaċità li tirreferi għall-15. Ma nistgħux ngħidu vleġġa ġdida ugwali jmiss xi ħaġa, hemm xejn hemmhekk. Fil-fatt, konna orfni il-bqija tal-lista billi tagħmel dan, aħna ħadthom aċċidentalment miksur il-katina. U aħna ċertament ma jridux jagħmlu dan. 

Mela ejja mur lura u tipprova dan mill-ġdid. Forsi l-aħjar ħaġa li tagħmel huwa li jiġu stabbiliti 12 ta pointer li jmiss lill-kap antika tal-lista l-ewwel, allura nistgħu jimxu l-lista fuq. U fil-fatt, li huwa l- ordni korretta li aħna jeħtieġ li jsegwu meta nkunu taħdem flimkien ma 'lista marbuta waħdu. Aħna dejjem tixtieq li jgħaqqdu l- element ġdid fil-lista, qabel nieħdu dak it-tip ta ' pass importanti tal-bdil fejn il-kap tal-lista marbuta hu. Għal darb'oħra, dan huwa tali ħaġa fundamentali, ma rridux li jitilfu l-mogħdija ta 'dan. 

Allura aħna tixtieq li tagħmel ċert li kollox huwa marbut b'katina flimkien, qabel nimxu dik pointer. U għalhekk dan ikun l-ordni korretta, li huwa li jgħaqqdu 12 mal-lista, allura jgħidu li l-lista jibda 12. Jekk aħna qal il-lista jibda fil-12 u mbagħad ippruvaw biex jgħaqqdu 12 mal-lista, konna diġà raw dak li jiġri. Aħna jitilfu l-lista bi żball. 

OK, so ħaġ'oħra biex jitkellmu dwar. X'jiġri jekk irridu li teħles minn l kollu lista marbuta f'daqqa? Għal darb'oħra, aħna qed mallocing dan l-ispazju, u hekk aħna bżonn biex ħielsa meta aħna qed isir. Allura issa aħna tixtieq li tħassar il-lista marbuta sħiħa. Ukoll, dak li rridu nagħmlu? 

Jekk konna laħqu l-pointer null, aħna tixtieq li twaqqaf, inkella, just iħassarha il-bqija tal-lista u mbagħad ħielsa me. Ħassar il-bqija tal-lista, u mbagħad ħielsa l node attwali. Xi jfisser li ħoss simili, dak it-teknika għandhom tkellimna dwar qabel ma dik ħoss bħal? Ħassar kulħadd, allura jiġu lura u ħassar lili. 

C'est recursion, aħna ħadna d- problema ftit iżgħar, aħna qed tgħid ħassar kulħadd inkella, allura inti tista 'tħassar me. U aktar fl-triq, li node se ngħid, iħassru kulħadd. Iżda eventwalment aħna ser jiksbu l- punt fejn il-lista hija nulla, u li l-każ bażi tagħna. 

Mela ejja tagħti ħarsa lejn dan, u kif dan jista 'jaħdem. Allura hawnhekk lista tagħna, huwa l-istess lista konna biss jitkellem dwar, u hemm l-passi. Hemm ħafna ta 'test hawn, iżda nisperaw li l-viżwalizzazzjoni se jgħinu. 

Allura aħna have-- u I wkoll miġbuda up frejms munzell tagħna illustrazzjoni mill-video tagħna fuq stacks sejħa, u nisperaw kollha ta 'dan flimkien se nuruk x'inhu għaddej. Allura hawnhekk kodiċi pseudocode tagħna. Jekk nilħqu null pointer, stop, inkella, tħassar il-bqija tal-lista, imbagħad ħielsa l node attwali. Allura issa dritt, list-- il pointer li aħna qed tgħaddi fil jeqirdu punti sa 12. 12 mhix pointer null, hekk aħna qed ser tħassar il-bqija tal-lista. 

X'inhu tħassar il- bqija tal us involut? Ukoll, dan ifisser tagħmel sejħa biex jeqirdu, qal li 15 huwa l-bidu tal- bqija tal-lista irridu li jeqirdu. U għalhekk l-sejħa li jeqirdu 12 huwa tip ta temporanjament. Huwa iffriżati hemmhekk, stennija għall- sejħa biex jeqirdu 15, biex jintemm ix-xogħol tagħha. 

Well, 15 mhix pointer null, u hekk li għaddej biex ngħid, id-dritt, ukoll, iħassru l-bqija tal-lista. Il-bqija tal-lista jibda fid-9, u hekk aħna ser biss stenna sakemm inti tħassar dak kollu li Jittieħed, imbagħad jiġu lura u ħassar lili. Well 9 għaddej biex ngħid, ukoll, Jien ma pointer null, hekk tħassar il-bqija tal-lista minn hawn. U sabiex jippruvaw u jeqirdu 13. 13 jgħid, jien ma pointer null, istess ħaġa, tgħaddi l-Buck. 10 mhux pointer null, 10 fih pointer null, iżda 10 m'hix hi stess null pointer dritt issa, u għalhekk tgħaddi l-Buck wisq. 

U issa lista punti hemm, huwa verament jixtieq jenfasizza li some-- kieku kelli aktar spazju fil-immaġini, ikun jindika xi spazju każwali li ma nafux dak li hu. Hu l-pointer null għalkemm, il-lista huwa litteralment issa stabbilit huwa l-valuri nulla. Huwa tipponta dritt ġewwa l-kaxxa aħmar. Aħna laħaq pointer null, hekk nistgħu stop, u aħna qed isir. 

U sabiex il-qafas vjola huwa now-- fil- quċċata ta 'stack-- dak l-qafas attiva, iżda dan isir. Jekk konna laħaq pointer null, stop. Aħna ma tagħmel xejn, aħna ma tistax jeħles pointer null, aħna ma malloc xi ispazju, u hekk aħna qed isir. Allura dak il-qafas il-funzjoni hija meqruda, u aħna resume-- aħna pick up fejn aħna jitħalla off bl-ogħla wieħed li jmiss, li huwa dan il-qafas blu skur hawn. Allura aħna pick up dritt fejn aħna jitħalla 'off. Aħna imħassra-bqija tal- lista diġà, hekk issa aħna qed se ħielsa l-lymph attwali. Allura issa nistgħu ħielsa dan node, u issa konna laħqu t-tmiem tal-funzjoni. U sabiex il-qafas il-funzjoni hija meqruda, u aħna pick up fil-wieħed blu dawl. 

Għalhekk says-- stajt diġà done-- tħassar il-bqija tal-lista, hekk ħielsa l node attwali. U issa l-qafas isfar huwa lura fuq nett tal-munzell. U hekk kif tara, aħna qed issa jeqirdu l-lista mill-lemin għax-xellug. 

Dak li kien ġara, għalkemm, jekk aħna kienu għamlu affarijiet l-mod żbaljat? Eżatt bħal meta aħna ppruvaw iżidu element. Jekk aħna messed up-katina, jekk aħna ma jgħaqqdu l-pointers fl-ordni korretta, jekk aħna biss meħlusa l-ewwel element, jekk aħna biss meħlusa l kap tal-lista, issa aħna m'għandhom l-ebda mod biex jirreferu għal il-bqija tal-lista. U hekk aħna jkollhom kollox orfni, kien ikollna x'hemm imsejħa nixxija memorja. Jekk inti recall mill-video tagħna dwar l-allokazzjoni memorja dinamika, li mhux ħaġa tajba ħafna. 

So kif għidt, hemm diversi operazzjonijiet li għandna bżonn li jużaw biex jaħdmu flimkien ma 'lista marbuta b'mod effettiv. U jista 'jkollok ndunat I titħalla barra waħda, tħassir ta 'element wieħed minn marbut lista. Ir-raġuni I did li huwa huwa attwalment tip ta ' delikata biex jaħsbu dwar kif ħassar element wieħed minn weħidhom Lista marbuta. Għandna bżonn li tkun tista 'skip fuq xi ħaġa fil-lista, li tfisser nikbru għal point-- aħna tixtieq li tħassar dan node-- iżda sabiex tagħmel dan hekk aħna ma jitlef l-ebda informazzjoni, għandna bżonn biex jgħaqqdu dan node hawn, hawn. 

So I probabbilment ma li wrong minn perspettiva viżiva. Allura aħna qed fil-bidu ta 'tagħna lista, aħna qed għaddej proċess minn, aħna tixtieq li tħassar dan node. Jekk aħna biss iħassarha, konna maqsuma fil-katina. Dan node dritt hawn tirreferi għall kull ħaġa oħra, fih il-katina minn hawn fuq barra. 

Allura dak li għandna bżonn tagħmel attwalment wara irridu jiksbu dan il-punt, huwa għandna bżonn li pass lura waħda, u qabbad dan node fuq għal dan node, hekk nistgħu imbagħad tħassar l-waħda fin-nofs. Iżda listi marbuta weħidhom ma tagħtina mod biex imorru lura. Għalhekk għandna bżonn li jew iżommu żewġ pointers, u mċaqalqa tip ta 'off pass, wieħed wara l- oħra kif immorru, jew tikseb sa punt u mbagħad tibgħat pointer ieħor permezz. U kif tista 'tara, huwa jistgħu jiksbu messy ftit. Fortunatament, aħna għandna mod ieħor biex isolvu li, meta nitkellmu dwar listi marbuta doppjament. 

Jien Doug Lloyd, dan huwa CS50.