[Powered by Google Translate] В програмирането, ние често трябва да представят списъци със стойностите, като имената на учениците в раздел или техните резултати за последното викторина. 

В езика C, обявена масиви може да се използва да съхранявате списъци. Това е лесно да се изброят елементите на списък съхраняват в масив, а ако имате нужда от достъп или модифицирате ItH елемент от списъка за някои произволно индекс I, може да се направи за константно време, но масиви имат недостатъци. 

Когато ние ги декларират, ние сме длъжни да се каже отпред, колко са големи, е, колко елементи, те може да се съхранява и колко е голяма тези елементи, който се определя от вида им. Например, вътр ARR (10) може да се съхранява 10 позиции , които са с размер на вътр. 

Не можем да променим големината на масива след декларацията. Ние трябва да направим нов масив, ако искаме да се съхранява повече елементи. Причината това ограничение съществува е, че нашата Програмата съхранява целия масив като свързано парче от паметта. Кажи това е буфер, където се съхраняват в нашия масив. Може да има други променливи се намира в непосредствена близост до масива в паметта, така че ние не можем да просто по-голям масив. 

Понякога ние бихме искали да търгуват бързо масив скорост на достъп до данните за малко по-голяма гъвкавост. Въведете свързан списък, друга основна структура на данните може да не е запознат с. На по-високо ниво, свързан списък съхранява данни в последователност от възли , които са свързани помежду си с връзки, оттук и името "свързан списък. Както ще видим, тази разлика в дизайна води до различни предимства и недостатъци от масив. 

Ето част от кода на C за един много прост свързан списък от цели числа. Можете да видите, че ние сме представени всеки възел в списъка като структура, която съдържа две неща, цяло число, магазин, наречен "Вал" и връзка към следващия възел в списъка , които ние представляваме като показалка, наречена "до". По този начин, можем да проследим целия списък само с едно показалеца на 1 възел, и след това ние можем да проследим следващите указатели до 2-ри възел, на 3-ти възел, от 4 възел, и така нататък, докато не стигнем до края на списъка. 

Може да бъде в състояние да се види 1 предимство има над статична структура масив - свързан списък, ние не се нуждаят от голяма част от паметта напълно. 1-во възел на списъка могат да живеят на това място в паметта, и 2-ри възел може да бъде по целия път тук. Ние можем да стигнем до всички възли, без значение къде в паметта са, защото, започвайки от 1 възел, в непосредствена близост показалеца на всеки възел ни казва къде точно да се върви напред. 

Освен това, ние не трябва да кажа, отпред колко голям свързан списък ще бъде начина, по който правим с статични масиви, , тъй като можем да поддържаме добавяне на възли към списък толкова дълго, колкото има място някъде в паметта за нови възли. Следователно, свързани списъци са лесни за да преоразмерите динамично. Кажи, по-късно в програмата трябва да добавите още възли в нашия списък. За да вмъкнете нов възел в нашия списък в движение, всичко, което трябва да направим, е да заделя памет за този възел, цоп в стойността на данните, и го поставете където искаме чрез адаптиране на съответните указатели. 

Например, ако искаме да поставите възел между 2-ри и 3-ти възли на списъка,  ние не би трябвало да се движат на 2-ри или 3-ти възли на всички. Казал, че сме поставите този червен възел. Всичко, което ще трябва да направите, е разположен в непосредствена близост показалеца на нов възел да сочи към 3-та възел и след това Повторното свързване следващия показалеца на 2-ри възел да сочи към нашия нов възел. Така че, можем да преоразмерите нашите списъци в движение тъй като нашия компютър не разчита на индексиране, , а по-скоро за свързване на използване на указатели да ги съхранявате. 

Въпреки това, недостатък на свързани списъци е, че, за разлика от статичен масив, компютърът не може просто да скочи в средата на списъка. Тъй като компютърът трябва да посети всеки възел в свързан списък да стигнем до следващия, , че ще отнеме повече време, за да намерите конкретна възел отколкото би в масив. Да прекосяват целия списък отнема време пропорционално дължината на списъка, или O (N) в асимптотичната бройна система. Като цяло, достигайки всеки възел също отнема време пропорционално н. 

Сега, нека да пиша някакъв код , който работи със свързани списъци. Нека кажем, че искаме свързан списък от цели числа. Ние може да представлява възел в нашия списък, отново като структура с 2 полета, целочислена стойност, наречена "Вал" и следващата указател към следващия възел на списъка. Е, изглежда достатъчно проста. 

Да кажем, че искате да напишете функция която пресича списък и отпечатва стойност, съхранявана в последния възел на списъка. Е, това означава, че ние ще трябва да преминават през всички възли в списъка да намерите последната, но тъй като ние не сме добавяне или да триете нищо, ние не искаме да се промени вътрешната структура на следващите указатели в списъка. 

Така че, ние ще трябва показалеца специално за преодоляване които ние ще наричаме "робот". Ще пълзи през всички елементи на списъка от след верига от следващите указатели. Всичко, което сте съхранили е указател към 1 възел, или "главата" на списъка. Head пункта до 1 възел. Тя е от типа на показалеца на възел. 

За да получите действителната 1-во възел в списъка, ние трябва да сочен този указател, но преди да можем да го сочените файлове, ние трябва да се провери ако показалецът е първата нула. Ако е нула, списъкът е празен, и ние трябва да отпечатате съобщение, че тъй като списъкът е празен, няма последна възел. Но, нека кажем, че списъкът не е празен. Ако не е, тогава ние трябва да се пълзи през целия списък докато стигнем до последния възел на списъка, и как можем да кажем, ако търсим в последния възел в списъка? 

Е, ако следващия показалеца възел е нула, Знаем, че сме в края след последното следващия показалеца няма да има следващия възел в списъка за точка. Това е добра практика да се поддържа винаги следващия показалеца на миналата възел инициализира с нула да има стандартизиран имот, който ни предупреждава, когато сме достигнали края на списъка. 

Така че, ако верижен → следващата е нула, не забравяйте, че стрелката синтаксис е пряк път за dereferencing указател на структура, а след това достъп до следващото поле равностойни на неловко: (* Робота). Следващата. След като ние открихме последния възел, искаме да отпечатате верижен → Вал, стойност в текущия възел което знаем, е последната. В противен случай, ако още не сме в последния възел в списъка, ние трябва да се премине към следващия възел в списъка и проверете дали това е последният. За да направите това, ние просто нашия робот показалеца да сочи към следващата стойност на текущия възел, че е следващия възел в списъка. Това се прави чрез определяне верижен = верижен → следващия. След това се повтаря този процес, с примка например, докато не намерим последния възел. Така например, ако верижен сочеше към главата, ние робота да се отбележи → следващия верижен което е същото като следващото поле на 1-вия възел. Така че, сега роботът ни е насочена към 2-ри възел, и отново, ние повтаряме това с една линия, докато ние открихме последния възел, това е, където следващия показалеца възел е насочена към нула. И там ние я имаме, ние открихме последния възел в списъка, и да отпечата стойността си, ние просто използвайте верижен → Вал. 

Преминаващи не е толкова лошо, но какво да кажем за поставяне? Да кажем, че искате да вмъкнете цяло число в 4-то място в списъка цяло число. Това е между сегашните 3-ти и 4-ти възли. Отново, ние трябва да преминават през списък, само за да стигнем до 3-ти елемент, ние сме поставите след. Така че, ние създаваме показалеца робота отново да прекосяват списък проверите дали главата ни показалецът е нула, и ако не е, насочете показалеца на нашия робот в главата възел. Така че, ние сме в 1-вия елемент. Ние трябва да вървим напред, две повече елементи, преди да могат да се монтират, така че можем да използваме за цикъл Int = 1; <3; + + и при всяка итерация на цикъла, напред нашия робот показалеца напред от 1 възел чрез проверка дали следващото поле на текущия възел е нула, и ако не е, преместете показалеца на робот до следващия възел чрез създаване равна на следващия показалеца на текущия възел. Така че, тъй като нашата цел контур казва, че два пъти, сме достигнали 3-та възел, и веднъж на нашия робот показалеца е достигнал възел след който искаме да вмъкнем нашата нова цяло число, как в действителност можем да поставите? 

Е, нашият нов число трябва да се добавя в списъка като част от структурата на своя възел, тъй като това е наистина поредица от възли. Така че, нека направим нова показалеца на възел "new_node," и да го настроите да се отбележи в паметта, които сега разпределят на куп за самия възел, и колко памет ще трябва да отделят? Е, размера на възел, и ние искаме да настроите своята област Вал към цяло число, което искаме да вмъкнем. Да кажем, 6. Сега възела съдържа целочислена стойност. То също е добра практика да се инициализира следващото поле на нов възел да сочи към нула, но сега какво? 

Трябва да променим вътрешната структура на списъка и следващите насоки, съдържащи се в съществуващото списъка 3-ти и 4-ти възли. Тъй като следващите насоки определят реда на списъка, и тъй като ние сме поставяне на нашия нов възел точно в средата на списъка, тя може да бъде малко по-сложен. Това е така, защото не забравяйте, нашия компютър знае местоположението на възли в списъка защото на следващите указатели, съхранявани в предишните възли. Така че, ако някога сме изгубили следите на някое от тези места, се каже, чрез промяна на един от следващите указатели в нашия списък, Например, да кажем ние променихме следващия 3-ти възел поле да сочи към някакъв възел тук. Щяхме да сме на късмет, защото ние не бихме има някаква идея къде да намерят останалата част от списъка, и това е очевидно наистина лошо. Така че, ние трябва да бъдем много внимателни за реда , в които манипулират следващите ни указатели по време на вмъкване. 

Така че, за да се опрости тази процедура, нека кажем, че първите четири възли се наричат ​​A, B, C и D, със стрелките, представляващи веригата от указатели , които се свързват възлите. Така че, ние трябва да вмъкнете нов възел между възлите C и D. Това е много важно да го направим по правилния ред, и аз ще ви покажа защо. 

Нека да погледнем в неподходящ начин да го направя първо. Хей, ние знаем, нов възел трябва да дойде веднага след C, така че нека в непосредствена близост показалеца C да се отбележи да new_node. Добре, изглежда наред, ние просто трябва да си свършим сега от следващия показалеца на нов възел точка за D, Но чакайте, как можем да направим това? Единственото нещо, което може да ни каже къде D, е следващата показалеца съхраняват в C, но ние просто пренаписа че показалеца да сочат към нов възел, така че ние вече няма да има представа къде D е в памет, и ние сме загубили останалата част на списъка. Не е добре на всички. 

Е, как да правим това право? Първо, насочете следващата показалеца на нов възел в D. Сега, както нов възел и C следващите указатели са насочени към същия възел, D, но това е добре. Сега можем да посочим следващия показалеца C в нов възел. Така че, ние сме направили това без загуба на данни. Код, C е текущият възел че прекосява показалеца верижен сочат, и D се представлява от възела, посочи следващото поле на текущия възел, или верижен → следващата. Така че, ние за първи път в непосредствена близост показалеца на нов възел да се отбележи → следващия верижен, по същия начин, казахме следващия показалеца new_node посочи D на илюстрацията. След това можем да поставим следващия показалеца на текущия възел в нашия нов възел, точно както ние трябваше да чакаме да се отбележи C да new_node в чертежа. Сега всичко е в ред, и ние не губят проследяване на всички данни, и ние бяхме в състояние само да придържаме нашия нов възел в средата на списъка без възстановяване на всичко или дори преместване на всички елементи начина, по който би трябвало да с фиксирана дължина масив. 

Така че, свързани списъци са основно, но важно, динамична структура на данните които имат както предимства, така и недостатъци в сравнение с масиви и други структури от данни, и както често се случва в областта на компютърните науки, важно е да знаете кога да използвате всеки инструмент, така че можете да изберете най-подходящия инструмент за подходящата работа. 

За повече практика, се опитате да пишете функции за изтриване на възли от свързан списък - не забравяйте да бъдете внимателни, за реда, в който пренаредите следващите си указатели, за да сте сигурни, че не губят парче на вашия списък или функция да разчита на възли в свързан списък, или едно забавно да обърнете реда на всички възли в свързан списък. 

Казвам се Джаксън Steinkamp, ​​това е CS50.