[Мусиц плаиинг] 

Даг Ллоид: У реду, тако да Ова тачка у току, покрили смо пуно основама Ц. Ми знамо много о променљиве, низови, показивачи, све добре ствари. Они су сви некако изградио у да видим као основе, али можемо учинити више, зар не? Ми могу комбиновати ствари заједно интересантне начине. 

И тако урадимо то, хајде да почнемо да се грана из онога што нам даје, Ц, и почети да креирате сопствени податке структуре које користе ове зграде блокови заједно да урадимо нешто заиста вредан и користан. Један од начина можемо да урадимо је ово да разговарамо о колекцијама. Дакле, до сада смо имали једну врсту података структура за заступање колекције Као вредности, сличне вредности. То би било низ. Имамо колекцију целих бројева, или колекције ликова и тако даље. 

Структуре су такође врста података структура за прикупљање информација, али то није за прикупљање као вредности. Обично се меша различите врсте података заједно унутар једног кутије. Али то није сама некада ланац заједно или се повежите заједно слично предмети, попут низа. Низови су одличне за Елемент погледати, али рецалл да је веома тешко да убаците у матрици, осим ако смо убацивањем у на самом крају тог низа. 

А најбољи пример имам за то је уметање врста. Ако се сећате наш видео на унесени врсте, било је доста расход укључени у има да покупи елементе, а схифт их из начин да се уклапају нешто у средини вашег поља. Низови такође пате од другог проблем, који је нефлексибилност. Када смо прогласити низ, добијамо једну шансу у томе. Ми добијамо да кажем, хоћу оволико елемената. Може бити 100, могло би бити 1.000, могло би бити х где је к број који је корисник дао нас на упит или у команди линија. 

Али ми само један хитац у томе, ми немој да се онда каже Ох, уствари потребно 101 или ми је потребно Кс плус 20. Прекасно, већ смо је прогласио Арраи, и ако желимо да се 101 или х Плус 20, морамо да се изјасни потпуно другачији низ, копирати све елементе низа преко, а онда имамо довољно. А шта ако смо опет у праву, шта ако стварно треба 102, или к плус 40, морамо ово поново да урадимо. Дакле, они су врло нефлексибилна за промену величине наше податке, али ако смо заједно неки комбинујемо од основа које смо већ сазнао показивачима и структура, посебно уз динамичке меморије расподела са маллоц, ми можете ставити ове коцкице Да бисте креирали нове податке струцтуре-- А појединачно повезане листе можемо говоре-- који нам омогућава да расте и скупити колекцију вредности и нећемо имати расипа простора. 

Дакле, опет зовемо ову идеју, Овај појам, повезане листе. Конкретно, у овом видеу смо говоримо о појединачно повезане листе, а онда још један видео снимак који смо разговараћемо о двоструко повезане листе, које је само варијација на тему овде. Али појединачно повезана листа се састоји од чворова, чворови само што апстрактна терм-- то је само нешто што зовем То је нека врста структура, у основи, ја сам? Само ћу га назвати ноде-- и ово чвор има два члана, или два поља. Има података, обично цео број, флоат карактер, или може бити неки други тип података да сте дефинисан типа деф. И то садржи показивач на други чвор истог типа. 

Дакле, имамо две ствари унутар Овај чвор, података и показивач у други чвор. А ако почнете замислити , можете мислити о томе као ланац чворова који су повезана заједно. Имамо први чвор, то садржи податке, и показивач на други чвор која садржи података и показивач на трећем чвор. И то је разлог зашто смо то позив линкед лист, да су они повезани заједно. 

Шта ова посебна Структура чвор изгледа? Па, ако се сећате из наше видео на дефинисање прилагођене врсте, са типом деф, можемо дефинисати и струцтуре-- тип дефинише структуру овако. тиепдеф струцт сллист, а онда сам коришћењем овде реч вредност произвољно да укаже заиста било коју врсту података. Можете да пренесем цео или пловак, можете имати шта год желите. Није ограничено на само целих, или тако нешто. Дакле, вредност није само произвољна тип података, а затим и показивач на другу чвор истог типа. 

Сада, постоји мало улов овде са дефинисања структуре када је само референтна структура. Морам имати привремени наме фор ми структуре. На крају дана сам се оцигледно зелис да га зову СЛЛ чвор, то је на крају нова наме дио мојој дефиницији типа, али ја не могу користити Слл чвор у сред овога. Разлог је тај што нисам створио тип се зове Слл чвор док сам погодио ову последњу тачку овде. До тада, морам да имам још један начин да се односи на ову врсту података. 

И ово је само референтни тип података. То; с врсту података Оф А структуре која садржи податке, и показивач на други структура истог типа. Зато морам да будем у могућности да се односи на ове податке Тип барем привремено, тако му даје привремени Име струцт сллист ми дозвољава да се каже Желим поинтер на другу струцт сллист, струцт сллист звезда, а затим након што сам завршио дефиницију, Ја сада могу назвати укуцајте СЛЛ чвор. 

Зато сте видели ту привремени назив овде, али трајно име овде. Понекад можете видети дефиниције структуре, на пример, да нису само референтна, да немају овде име спецификатором. Само бих типедеф струцт, отвори коврџаву браце, а затим га дефинисати. Али, ако сте струцт је само референтна, јер ово је, морате да наведете привремени тип име. Али на крају, сада да смо урадили ово, можемо да се односе на ови чворови, ове јединице, као СЛЛ чворова за сврхе остатка овај видео. 

У реду, тако да знамо како да створити повезане листе чвор. Ми знамо како да дефинишемо повезане листе чвор. Сада, ако ћемо да почне користећи их за прикупљање информација, има неколико операција смо треба да схвате и рад. Морамо да знамо како да направите повезане листе из ведра неба. Ако већ нема листе, желимо да покренемо једну. Дакле, морамо бити у стању да створи повезану листу, морамо да вероватно тражити кроз листу линкова да пронађе елемента смо у потрази за. Морамо бити у стању да убаците нове ствари у попис, желимо да наша листа бити у стању да расте. Слично томе, желимо да будемо у стању да бисте избрисали ствари из наше листе, желимо да наша листа бити у могућности да смањује. И на крају нашег програми, посебно ако се сећате да смо динамички доделе меморије за изградњу ове листе обично, желимо да ослободимо све те меморије када смо завршили рад са њим. И тако морамо бити у стању да избришете Цео повезана листа у једном не упале. Дакле, идемо кроз неке од ових операција и како бисмо могли да их визуализовати, говори у псеудокоду код конкретно. Зато желимо да створимо повезане листе, тако да можда можемо Желим да дефинишемо функцију са овом прототипу. СЛЛ чвор звезда, стварају, а ја пролазу у једном аргумент, нека произвољна подаци тип опет неког произвољног типа података. Али ја ретурнинг-- ову функцију треба врати ми се показивач, до А појединачно линкед лист чвор. Опет, покушавамо да створимо повезане листе из ведра неба, па ми треба показивач на та листа кад завршим. 

Дакле, шта су кораци који су укључени овде? Па, прва ствар коју сам да урадите је динамички доделити простор за нови чвор. Опет, ми то стварање из ничега ваздух, тако да морамо да маллоц простора за њега. И наравно, одмах након што смо маллоц, увек проверите да бисте се уверили наши поинтер-- нисмо вратимо нула. Јер ако покушамо и попустљивост нулл показивач, ћемо патити сегфаулт и не желимо то. 

Затим желимо да попуните поље, желимо да покрене поље Валуе и покрене следеће поље. А онда ми желимо да-- на крају као Функција прототип индицатес-- желимо да се врати показивач на слл чвора. Дакле, оно што чини ово личи визуелно? Па, прво ћемо да динамички доделити простор за нови слл чвора, тако да маллоц-- да је визуелна представа чвора смо створили. И ми проверите да ли није нулл-- у овом случају, слика не би имао појавио ако је нула, ми би понестало меморије, тако да смо добри да идем тамо. Дакле, сада смо на корак Ц, покрене поље чворови вредности. Па, на основу ове функције звати ја користим овде, Изгледа као да желим да прође у 6, па ћу 6 на терену вредности. Сада, покрените следеће поље. Па, шта ћу тамо да ради, не постоји ништа следећи, зар не, ово је једина ствар на листи. Дакле, шта је следећа ствар на листи? 

То не би требало да укаже на било шта, зар не. Нема ништа друго тамо, па шта је концепт знамо да је нотхинг-- показивачи на ништа? То би требало да буде можда желимо тамо стави Нулл Поинтер, и ја ћу представљају нулл поинтер као само црвену кутију, не можемо ићи даље. Као ћемо видети нешто касније, ћемо морати евентуално ланце стрелица повезивање Те тачке заједно, али када ударио Ред Бок, то је нула, не можемо ићи даље, то је крај листе. 

И на крају, ми само желимо да вратити показивач на овом чвору. Дакле, ми ћемо га звати нова, и вратиће нови тако да се може користити у год функција је створио. Дакле, идемо, ми смо направили појединачно линкед лист чвор из ведра неба, и сада имамо списак можемо радити са. 

Сада, да смо већ рекли имају велики ланац, и желимо да пронађемо нешто у њој. И желимо функцију која се догађа да се врате тачно или нетачно, зависно о томе да ли вредност постоји у тој листи. Функција прототип, или декларација за ту функцију, може изгледати као ово-- боол наћи и онда желимо да прође у два аргумента. 

Први је показивач на први елемент повезане листе. Ово је заправо нешто што ћу увек желе да пратите, и заправо може бити нешто што чак ставити у глобалној променљивој. Када направите листу, Увек, увек желите да пратите од самог први елемент листе. На тај начин можете се односе на све остале елементи за само након ланац, без потребе да задржи савете нетакнута у сваком елементу. Потребно је само да пратите први једна ако су сви у ланцима заједно. 

А онда друга ствар Пролазимо поново је произвољно неке-- било које врсте података смо лоокинг фор постоји унутар надам се да је један од чворова на листи. Дакле, шта су кораци? Па, прва ствар коју радимо је стварамо трансверзалну показивач указујући на главу листе. Па, зашто ми то већ радимо има показивач на челу листе, зашто не бисмо се помери за око? Па, као што сам рекао, то је заиста важно за нас да увек водити евиденцију о Први елемент у листи. И тако је заправо боље да створи дупликат који, и користи га да се креће тако да нисмо случајно се удаљи, или увек има показивач у неком тренутку који је Право на први елемент листе. Тако да је боље да се створи Други је да користимо за кретање. 

Онда смо само упоредити да ли поље вредност у том чвору је оно што тражите, а ако је Не, ми смо само прелазимо на следећи чвор. И чувамо то ради више, и више, и више, док не нађемо било елемент, или смо ударили нулл-- смо стигли до краја листе и не постоји. Ово би требало да надамо се звони звоно за вас као само линеарно претраживање, Само је реплицира у појединачно повезана листа структура уместо да помоћу низа да то уради. 

Дакле, овде је пример појединачно повезана листа. Ово се састоји од пет чворова, и имамо показивач на шефа листа, која се зове листа. Прва ствар коју желите да урадите је опет, створили ту Траверсал показивач. Дакле, имамо сада два савете које указују на исту ствар. 

Сада, приметите и овде, нисам треба да Маллоц било простора за трав. Нисам рекао Трав једнака маллоц нешто што чвор већ постоји, тај простор у меморији већ постоји. Тако да све што заправо радим је стварајући још један показивач на њега. Нисам маллоцинг додатна простор, само су сада две тројке указујући на исту ствар. 

Тако је 2 оно што тражим? Па, не, тако да уместо да сам прећи на следећу. Дакле, у основи, рекао бих, Трав Трав једнака следећи. Да ли је 3 оно што тражим, бр. Тако сам и даље ићи кроз, док на крају дођете до 6 то је оно што тражим за заснован на позива функције Имам на врху тамо, па сам готов. 

Сада, шта ако елемент сам лоокинг фор није на листи, да ли је и даље иде на посао? Па, приметити да листа Овде је суптилно различит, и то је још једна ствар која је важно са повезаним листама, не морате да сачувају да у сваком конкретном циљу. Можете, ако желите, али Можда сте већ приметили да нисмо праћење Који број елеменат смо у. 

И то је нека врста једне трговине да има са повезане листе стихови низове, је то што немамо директног приступа више. Не можемо само рећи, хоћу да иде на 0-тог елемента, или 6. елемент моје низа, што могу да урадим у низу. Ја не могу да кажем да желим да одем до 0тх елемент, односно 6. елемент, или 25. елемент моје повезане листе, нема индекс повезан са њима. И тако није битно ако сачувамо нашу листу како. Ако желите да вас Свакако, али постоји нема разлога зашто они треба да бити очуван у било ком редоследу. Дакле, опет, хајде да пробамо и финд 6 на овој листи. Па, ми почети на почиње, не нађемо 6, а онда и даље не проналажење 6, док смо на крају доћи до овде. Дакле, сада Трав указује на чвору садржи 8, а шест није унутра. 

Дакле, следећи корак би био да иде на следећи показивача, тако рећи Трав Трав једнака следећи. Па, Трав следеће, указује Тхе Ред Бок постоји, нулл. Дакле, нема где другде да иди, па у овом тренутку можемо закључити да смо стигли крај повезане листе, и 6 није унутра. И то ће бити враћена лажна у овом случају. 

У реду, како да убаците нови чвор у повезане листе? Тако смо били у стању да створи повезане листе ниоткуда, али ми вероватно желите да изгради ланац и не створити гомилу различитих спискова. Желимо да имамо један списак који има гомилу чворова у њему, не гомила листе са једним чвором. Дакле, не можемо само наставите користећи Цреате Функција смо дефинисали раније, сада желите да унесете у један Листа која већ постоји. 

Дакле овом случају, идемо да прође у два аргумента, показивач на главу да повезане листе које желимо да додате. Опет, зато је тако битно да смо увек пратити, јер то је једини начин да стварно треба да се односи на цео списак само од показивач на првог елемента. Дакле, желимо да прође у А Поинтер на том првом елементу, и све вредности ми желите да додате на листу. И на крају ова функција ће вратити показивач до новог шефа повезане листе. 

Који су кораци укључени овде? Па, баш као са стварају, морамо да динамички додели простор за нови чвор, и проверите да Сигурно да не понестане меморије, опет, јер ми користимо маллоц. Затим желимо да уведемо и убаците чвор, тако да је број, како год Вал је, у чвор. Желимо да убаците у чвор почетак повезане листе. 

Постоји разлог што сам желим ово да радим, и то можда вреди мало за паузирање видео овде, и мислим о томе зашто бих желео да убаците на почетку повезан листа. Опет, што сам раније поменуо да се то заправо не битно да смо га сачувати у једном ред, па можда то је траг. И видели сте шта би се десило ако бисмо Хтео да-- или само секунд пре када смо ишли кроз потрази сте могао да види шта би могло догодити ако смо покушавали за уметање на крају листе. Зато што немам поинтер на крај листе. 

Дакле, разлог због којег бих желео да убаците на почетку, је зато што може да уради одмах. Имам показивач на почетку, и ћемо видети у визуелни у секунди. Али, ако желим да убаците на крају, Морам да кренемо од почетка, пролазе скроз до крај, а затим га тацк на. Дакле, то би значило да уметање на крају листе би постао О од н рад, враћам на нашој дискусији о рачунарска комплексност. То би постао О од н операције, гдје као списак добио већи, и већи, и већи, то ће постати све више и теже да се осуши нешто на на крају. Али увек је стварно лако да тацк нешто на на почетку, ти си увек на почетку. 

А видећемо визуелни ово поново. И онда кад смо урадили, једном смо убаци нови чвор, желимо да се врати нашу показивач на нови шеф повезане листе, која јер смо убацивање На почетком, заправо ће бити показивач на чвор смо управо креирали. Хајде да визуализују ово, јер мислим да ће помоћи. 

Дакле, овде је наша листа, састоји се од четири елемента, чвор који садржи 15, што указује на чвор садрже 9, која указује на чвор који садржи 13, што указује на чвор који садржи 10, која има нулти показивач као следећем показивач тако да је крај листе. Дакле, желимо да уметање нови чвор са вредношћу 12 на почетку овог Листа, шта да радимо? Па, прво маллоц простор за чвор, а онда пут 12 унутра. 

Дакле, сада смо достигли Одлука поента, зар не? Имамо пар показивачи да смо могли селе, као што би требало да први корак? Ако правимо 12 поен у нови шеф лист-- или извините, треба да правимо 12 указују на старом носилац листе? Или да кажемо да је Листа сада почиње у 12. Ту је разлика тамо, а ми ћемо гледати шта се дешава са оба у секунди. 

Али ово доводи до велика тема за сидебар, а то је да једна од најтежих ствари са повезаним листама се договорити за савете у исправном редоследу. Ако преместите ствари из реда, можете завршити случајно орпханинг остатак листе. И ево примера за то. Дакле, идемо са идејом од-- Па, управо смо створили 12. Знамо да 12 ће бити нови носилац листе, па зашто не бисмо само померите листа показивач на ту укаже. 

У реду, то је добро. Дакле, сада гдје се 12 следећу тачку? Мислим, визуелно можемо да видимо да ће указати на 15, као људи стварно је очигледно за нас. Како компјутер зна? Ми немамо ништа указујући на 15 више, зар не? 

Изгубили смо сваку могућност да се обрати 15. Не можемо рећи да нова стрелицу поред једнаки нешто, тамо нема ништа. У ствари, ми смо сироче остатак листе на тај начин, ми смо случајно пробили ланац. А ми сигурно не желим то да урадим. 

Дакле, хајде да се вратимо и покушајте поново. Можда је права ствар је да постави 12 је следећи показивач старом носилац листе првог, онда можемо да пређемо преко листе. У ствари, то је тачно да бисмо треба да прати кад смо рад са појединачно повезане листе. Ми смо увек желе прикључити нови елемент у листи, пре него што се такав значајан корак промене где је шеф повезане листе је. Опет, то је тако основна ствар, не желимо да изгубимо траг о томе. 

Зато желимо да се уверите да све је окован заједно, пре него што кренемо да показивач. И то би био исправан поредак, што је за повезивање 12 на листу, онда рећи да је листа покреће 12. Ако смо рекли списак почиње у 12 и Онда је покушао да се повеже на листу 12, смо већ видели шта се дешава. Губимо списак грешком. 

У реду, тако да још једну ствар да разговарамо. Шта ако желимо да се ослободимо цео повезана листу одједном? Опет, ми маллоцинг све ово простор, па смо треба да га ослободе, када смо завршили. Тако да сада желите да избришете цела повезана листа. Па, шта желимо да урадимо? 

Ако смо стигли до Нулл Поинтер, ми Желим да престане, иначе, само брисање остатак листе, а затим ме ослободи. Обришите остатак листе, а затим ослободи тренутни чвор. Шта то звучи као, оно технику имамо разговарали о претходно вам то звучи? Обриши све друго, онда врати и брисање ме. 

То је рецурсион смо извршена Проблем мало мања, говоримо обрисати све друго, онда можете да ме избрисати. И даље низ пут, тај чвор ће рећи, избрисати све друго. Али на крају ћемо се до тачка у којој је листа нулл, и то је наш основни случај. 

Дакле, хајде да погледамо ово, и како то може радити. Дакле, овде је наша листа, то је иста лист смо причали, а ту су и кораци. Има пуно текста овде, али надамо се визуелизација ће помоћи. 

Тако смо бих-- и такође сам извукао до нашег стек фрамес илустрација из наше видео на гомиле позива, и надамо се све ово заједно ће вам показати шта се дешава. Дакле, овде је наш Псеудокод број. Ако се постигне нулл показивач, стоп, у супротном, обришите остатак листе, онда ослободи тренутни чвор. Тако сада, лист-- показивач да смо пролази да уништи поена за 12. 12 није Нулл Поинтер, тако да смо ће обрисати остатак листе. 

Шта је брисања остали укључени? Па, то значи чинећи позове да уништи, рекавши да 15 је на почетку Остатак листе желимо да уништимо. И тако је позив да се уништи 12 је некако на чекању. То је било замрзнуто, чекајући да се позове да уништи 15, да заврши свој посао. 

Па, 15 није Нулл Поинтер, и тако да ће рећи, у реду, добро, избришите остатак листе. Остатак листе почиње у 9, па само ћемо сачекајте док не избришете све то ствари, онда се врати и брисање ме. Па 9 ће рећи, добро, Ја нисам Нулл Поинтер, па обрисати остатак листе одавде. И тако покушати да униште 13. 13 каже, нисам Нулл Поинтер, иста ствар, она пролази долар. 10 није Нулл Поинтер, 10 садржи Нулл Поинтер, али 10 није само по себи Нулл Поинтер сада, па испуњава неке превише на долар. 

И сад лист бодова ето, Заиста би указивало на неке-- кад бих имао више простора у слици, то би указивало на неки случајних простора да ми не знамо шта је то. То је нула показивач ипак, листа се буквално сада постављен је вредност нулл. То је у реду показује у тој црвеној кутији. Постигли смо Нулл Поинтер, тако можемо зауставити, и готови смо. 

И то љубичаста оквир је сада-- На врх стацк-- да је активна оквир, али се то ради. Ако смо дошли до Нулл Поинтер, стоп. Ми не радимо ништа, ми не може ослободити нулл показивач, нисмо маллоц било простор, па смо урадили. Дакле, ту функцију оквира је уништена, а ми ресуме-- смо покупили где смо стали офф са следећим највећом један, која ово тамно плаве оквир овде. Тако смо покупили тамо где смо стали. Ми избрисан остатка Листа већ, па сад смо ће ослободити тренутне чворова. Сада можемо да ослободимо овај чвор, и сада смо стигли до краја функције. И тако да се функција оквир је уништен, и ми покупити на светло плавој. 

Тако да рекао-- сам већ доне-- брисање остатак листе, тако ослободи тренутни чвор. И сада добија жути оквир је назад на врх гомиле. И тако, као што видите, сада смо уништавање листу са десна на лево. 

Шта би се догодило, међутим, Ако смо урадили ствари на погрешан начин? Као када смо покушали да додате елемент. Ако забрљао ланац, ако нисмо повезали показивачи у исправном редоследу, ако Управо ослобођен први елемент, ако смо је ослободио носилац листе, сада Нема начина да се позива на остатак листе. И тако бисмо имали сироче све, имали бисмо шта је назива цурење меморије. Ако се сећате из наше видео на динамичког додељивања меморије, то није веома добра ствар. 

Дакле, као што сам рекао, тамо неколико операција да морамо да користимо за рад са ефикасно повезани листу. А можда сте приметили сам пропустио један, брисање један елемент са повезаног листа. Разлог зашто сам то урадио је то у ствари нека врста Трицки да размишљају о томе како да избришете један елемент из А појединачно линкед лист. Морамо бити у стању да прескочим нешто на листи, која значи да се до поента ве желите да избришете ову ноде-- али како да се направи тако да смо не губи било какву информацију, морамо повезати ово чвор овде, овде. 

Тако да сам вероватно урадио погрешно из визуелне перспективе. Дакле, ми смо на почетку нашег Листа, ми смо одвија кроз, желимо да обришете овај чвор. Ако смо га избрисати, смо пробили ланац. Овај чвор овде односи се на све друго, садржи ланац од сада па надаље. 

Дакле, оно што треба да урадите ствари након што дођемо до ове тачке, је морамо да вратимо корак један, и повезати овај чвор на ову чвора, па онда можете брисати онај у средини. Али појединачно повезане листе не пружају нам пут да се врати назад. Зато морамо да их задржите два показивачи, и да их врста офф корак, један иза другима као идемо, или дођете до тачке а затим послати још један показивач преко. И као што можете видети, то може добити мало неуредан. Срећом, имамо још један начин да се то реши, када говоримо о двоструко повезане листе. 

Ја сам Доуг Ллоид, ово је ЦС50.