[Powered by Google Translate] У програмирању, често је потребно да представљају листе вредности, као што су имена ученика у одељку или њихови резултати на последњим квизу. 

У језику Ц, изјавио низови могу користити за складиштење листе. То је лако набројати елементе листе ускладиштени у низу, а ако вам је потребан приступ или модификује ИТХ елемент листе за неке произвољне индекс сам, који може да се уради у сталном времену, али низови имају недостатке, превише. 

Када смо их објави, ми смо у обавези да кажу напред колики су, који је, колико елементи могу чувати и колики су ти елементи, који се одређује њихов тип. На пример, инт арр (10) може да ускладишти 10 ставки које су величине једног инт. 

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

Понекад бисмо волели да тргују брзо низу је дата брзину приступа за мало више флексибилности. Унесите повезане листе, друга основна структура података можда нећете бити упознат са. На високом нивоу, повезана листа складишти податке у низу чворова који су међусобно повезани са линковима, па 'повезана листа ". његово име Као што ћемо видети, ова разлика у дизајну доводи до различите предности и мане него низа. 

Ево неких Ц код за врло једноставне повезане листе целих бројева. Можете видети да смо представљали сваки чвор на листи као струцт који садржи 2 ствари, цео за складиштење зове 'вал' и линк на следећу чвор у листи које представљају као показивач зове 'поред'. На овај начин, можемо пратити целу листу са само једним показивачем 1. чвора, и онда можемо пратити следеће савете на 2. чвора, до 3. чвора, до 4. чвора, и тако даље, све док не дођемо до краја листе. 

Можда ћете моћи да видите 1 предност то има преко статичког низа структура - са повезаном листом, не сасвим потребан велики комад меморије. 1. чвор листе могао да живи на овом месту у меморији, и 2. чвор може бити скроз овамо. Можемо доћи до свих чворова, без обзира где се у меморији су, јер почевши од 1. чвор, поред показивача сваког чвора говори нам тачно где да идемо даље. 

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

На пример, ако бисмо желели да поставите чвор између 2. и 3. чворови на листи,  не бисмо имали да се крећу 2. или 3. чворове уопште. Реци ми убацивањем ову црвену чвор. Све ћемо морати да урадимо је Сет нект показивач новог чвора да укаже на 3. чвора и онда РеВире нект показивач 2. чвора да укаже на нашем новом чвору. Дакле, можемо величину наше листе на лету јер наш рачунар не ослања на индексирање, већ на повезивању коришћења тројке да их сачувате. 

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

Сада, хајде да ствари напише неки код који ради са повезаним листама. Рецимо желимо повезано листу целих бројева. Можемо представљају чвор у нашем списку поново као струцт са 2 поља, интегер вредност назива 'вал' и следећег показивач на следећи чвор листе. Па, изгледа једноставно. 

Рецимо да желите да напишете функцију који прелази на листи и отиске Оут Вредност чувају у последњем чвору листе. Па, то значи да ћемо морати да прођу све чворове на листи да пронађе последњи, али пошто нисмо додајући или брисање ништа, ми не желимо да промените унутрашња структура наредних показивача на листи. 

Дакле, ми ћемо морати показивач посебно за пролаза који ћемо назвати "пописивача". То ће пузати кроз све елементе листе пратећи ланац од наредне показивача. Све смо ускладиштена је показивач на 1. чвора, или "шеф" листе. Шеф указује 1. чвора. То је типа показивач до чвора. 

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

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

Дакле, ако пописивач → следећи је нула, запамтите да стрелица синтакса је пречица за дереференцинг показивач на структуру, онда приступ Његова следећа поља једнак незгодно: (* Пописивач) поред.. Када смо открили последњи чвор, желимо да одштампате пописивача → Вал, вредност у текућем чвору што знамо да је последњи. У супротном, ако нисмо још на последњем чвора у листи, морамо да пређемо на следећи чвор у листи и проверите да ли је то последњи. Да бисте то урадили, само смо поставили наш пописивача показивач да укаже на следећу вредност тренутног чвора, који је, следећи чвор у листи. Ово се ради постављањем пописивач = пописивач → следећи. Онда смо поновите овај процес, са петље, на пример, док не нађемо последњи чвор. Тако, на пример, ако је пописивач указује на глави, смо поставили пописивачу да укажемо на гусеничар → нект, што је исто као и следеће области 1. чвора. Дакле, сада је наш пописивач указује на 2. чвора, и, опет, понављамо ово са петље, док смо нашли последњи чвор, то јест, Куда даље показивачем чвора указује на нулл. И тамо га имамо, нашли смо последњи чвор у листи, као и да штампају његову вредност, ми само користимо финишер → Вал. 

Преласком није тако лоше, али шта је са убацивањем? Рецимо да желите да убаците цео број у 4. позицији у цео листи. То је између садашњих 3. и 4. чворова. Опет, морамо прећи листу само да доћи до 3. елемента, онај смо убацивање после. Дакле, ми стварамо показивач пописивачу поново да пролазе листу, проверите да ли је наша показивач глава је нула, а ако то није, истичу наше показивач пописивача на челу чвора. Дакле, ми смо на 1. елемента. Морамо да идемо напред још 2 елемента пре него што можемо да убаците тако да можемо да користимо за петљу инт и = 1; и <3 и + + иу свакој итерацији петље, унапредити нашу показивач пописивачу напред за 1 чвора провером ако Следеће поље тренутни чвор је нула, а ако није, преместите показивач нашу пописивача до следећег чвора постављајући га једнако на следећи показивач тренутног чвора. Дакле, пошто је наш јер петља каже да то уради два пута, Стигли смо на 3. чвор, и када је наш показивач пописивач је достигао чвор после коју желите да убаците цео наш нови, како ми заправо урадите убацивање? 

Па, наш нови цео мора да се убаци у листу као део сопственог чвора струцт, јер ово је стварно низ чворова. Дакле, хајде да направимо нови показивач на чвор зове 'нев_ноде' и подесите га да укаже на меморију која се сада издвајају на гомили за саму чвора, и колико меморије морамо да издвоји? Па, величине чвора, и желимо да подесите поље Вал да цео да желимо да убаците. Рецимо, 6. Сада, чвор садржи нашу целобројну вредност. Такође је добра пракса да се покрене следеће поље новог чвора да укаже на нулл, али шта сада? 

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

Дакле, да поједностави ово, рецимо да наши први 4 чворови се зову А, Б, Ц и Д, са стрелицама представљају ланац показивачи који повезују чворове. Дакле, морамо да убаците наш нови чвор између чворова Ц и Д. То је важно да то уради у правом циљу, а ја ћу вам показати зашто. 

Погледајмо на погрешан начин да то уради први. Хеј, ми знамо нови чвор мора доћи одмах после Ц, па хајде да поставимо Ц је следећи показивач да укаже на нев_ноде. Добро, изгледа ок, само морамо да завршимо до сада од чинећи следећу тачку показивач новог чвора до Д, Али чекај, како можемо то да урадимо? Једина ствар која је могла да нам кажете где је Д био, је следећи показивач претходно ускладиштени у Ц, али ми преписао тај показивач да укаже на нови чвор, тако да више немамо никакву представу где је Д је у меморији, а ми смо изгубили остатак листе. Није добро. 

Дакле, како да радимо ово право? Прво, усмерите показивач на нект Д. Нови чвора Сада, како нови чвор и Ц је следећи показивачи указују на исти чвор, Д, али то је у реду. Сада можемо да тачка Ц је следећи показивач на новом чвору. Дакле, ми смо урадили без губљења података. У коду, Ц је тренутни чвор да траверсал показивач финишер указује да, и Д представља чвора истакао да до следећег поља тренутног чвора, или пописивач → следећи. Дакле, ми смо први Сет нект показивач новог чвора да укаже на гусеничар → нект, Исто тако смо рекли нев_ноде идуће показивач треба указују на Д на слици. Онда можемо да поставимо следећи показивач тренутног чвора нашем новом чвору, баш као што смо морали да чекамо да се укаже Ц до нев_ноде у цртежу. Сада је све у реду, а нисмо изгубили евиденцију о свим подацима, а ми смо били у стању да само држимо нашу нову чвор у средини листе без обнови целу ствар, или чак мења елементе Тако бисмо морали да са фиксне дужине низа. 

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

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

Моје име је Џексон Стеинкамп, ово је ЦС50.