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

Во јазик C, изјави низи може да се користи за чување листи. Тоа е лесно да наведеме елементи на листа чуваат во низа, и ако ви треба за да пристапите или модифицирање на ith елемент од листа за некои произволни индекс јас, што може да се направи во постојан време, но низи имаат недостатоци, исто така. 

Кога ќе ги прогласи, ние треба да се каже до пред колку е голема се тие, што е, колку елементи ќе може да се сместат и колку е голема овие елементи се, што го утврдува нивниот вид. На пример, int arr (10) може да се сместат 10 предмети кои се со големина на инт. 

Ние не може да се промени големината низа по декларацијата. Ние треба да се направи нова низа, ако сакаме да се складираат повеќе елементи. Причината ова ограничување постои е дека нашата програма продавници целата низа како соседни парче на меморија. Велат дека ова е тампон каде што се чуваат во нашата низа. Може да има други променливи наоѓа веднаш до низа во меморијата, па не можеме да само направи низа поголем. 

Понекогаш ние би сакале да тргуваат брзо низа на податоци брзината на пристап за малку повеќе флексибилност. Внесете го поврзана листа, друг основни податоци структура Вие не може да биде запознаен со. На високо ниво, на поврзани листа продавници податоци во низа на јазли кои се поврзани едни со други со линкови, па оттука и називот "поврзани листа". Како што ќе видиме, оваа разлика во дизајн доведува до различни предности и недостатоци од низа. 

Еве некои кодот C за еден многу едноставен поврзани листа на цели броеви. Можете да видите дека имаме претставен секој јазол во списокот како struct, која содржи 2 работи, целобројна за чување наречена "вредност" и линк до следниот јазол во листата кои ние ги претставуваме како покажувач кој се нарекува "Следно". На овој начин, можеме да ги следиме целата листа со само еден покажувач на јазол 1, и потоа можеме да се следи во следните совети на 2 јазол, од 3-тиот јазол, до 4 јазол, и така натаму, се додека не стигнете до крајот на листата. 

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

Покрај тоа, ние не треба да се каже однапред колку е голема на поврзани листа ќе биде начинот на кој ние се направи со статички низи, бидејќи ние може да ги задржи додавајќи јазли на листата додека има простор некаде во меморија за нови јазли. Затоа, поврзани листи се лесно да се промени големината динамично. Каже, подоцна во програмата ние треба да додадете повеќе лимфни јазли во нашата листа. За да внесете нов јазол во нашата листа на мува, сите ние треба да направите е да алоцира меморија за тој јазол, одеднаш во податоците вредност, и тогаш тоа место каде што сакаме со прилагодување на соодветни совети. 

На пример, ако сакаме да поставите јазол помеѓу 2 и 3 јазли на листата,  ние не ќе мора да се преселат на 2ра или 3та јазли на сите. Велат ние сме вметнување овој црвено јазол. Сите ние ќе треба да направите е да поставите следниот покажувачот новиот јазол да се укаже на 3 јазол а потоа rewire следната покажувачот на 2 јазол да се укаже на нашата нова јазол. Значи, можеме да ја промените големината нашите листи во лет Од нашиот компјутер не се потпира на индексирање, туку за поврзување со користење совети како да ги чува. 

Сепак, недостаток на поврзани листи е дека, за разлика од статична низа, компјутерот не само да скокнете до средината на листата. Од компјутер мора да ја посетите секој јазол во поврзани листа да се дојде до следното едно, тоа нема да потрае подолго за да најдете одреден јазол отколку што би во низа. Да напречни целата листа е потребно време пропорционална должината на листата, или О (n) во асимптотска нотација. Во просек, достигнувајќи било кој јазол Исто така е потребно време пропорционална на n. 

Сега, ајде да всушност пишува некаков код која работи со поврзани листи. Да речеме дека сакаме поврзани листа на цели броеви. Ние може да претставува еден јазол во нашата листа повторно како struct со 2 области, целобројна вредност наречена "вредност" и следната покажувач кон следниот јазол на листа. Па, се чини едноставна. 

Да речеме дека сакаме да напише функција кој преминува листата и отпечатоци од вредност се чуваат во последните јазол на листа. Па, тоа значи дека ние ќе треба да напречни сите јазли во листата да се најде на последната, но бидејќи ние не сме додавање на или бришење на ништо, ние не сакаме да се промени внатрешната структура на следниот совети во листата. 

Значи, ние ќе треба покажувач специјално за traversal кој ќе го наречеме "Роботот". Тоа ќе ползи преку сите елементи на листата со следење на синџирот на следната совети. Сите ние се чуваат е покажувач на јазол 1, или 'глава' на листата. Раководител поени 1 јазол. Тоа е од тип покажувач до-јазол. 

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

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

Значи, ако Роботот → следната е нула, се сеќавам дека стрелките на синтаксата е кратенка за dereferencing покажувач на struct, тогаш пристап својот следен областа еквивалентни на непријатна: (* Роботот). Следната. Откако ќе го најде последниот јазол, ние сакаме да се печати Роботот → вредност, вредност во тековниот јазол кои знаеме е последен. Инаку, ако ние не сме уште во последниот јазол во листата, ние треба да се движи кон следниот јазол во листата и проверете дали тоа е последен. Да го направите ова, ние само го постави нашиот Роботот покажувачот да се укаже следната вредност тековната јазол, што е, следниот јазол во листата. Ова е направено со поставување Роботот = Роботот → следната. Тогаш ние го повтори овој процес, со еден циклус на пример, додека не се најде на последната јазол. Така, на пример, ако Роботот беше укажува на главата, ние во собата Роботот да се укаже Роботот → следната, кој е ист како на следната област на 1 јазол. Значи, сега нашите Роботот е да се покажува на 2 јазол, и, повторно, се повторува со еден циклус, додека ние Наидовме на последниот јазол, што е, каде следната покажувачот на јазол е да се покажува на нула. И таму го имаме, ние Наидовме на последниот јазол во листата, и да се печати својата вредност, ние само користење пребарувач → вредност. 

Traversing не е толку лошо, но она што за вметнување? Да речеме ние сакаме да вметнете број во 4-то место во целобројна листа. Тоа е меѓу сегашните 3 и 4 јазли. Повторно, ние треба да напречни листата само за да стигнете до 3 елемент, еден ние сме вметнување после. Значи, ние создаваме Роботот покажувачот повторно да напречни листата, проверете дали нашата глава покажувачот е нула, а ако не е, посочуваат нашите Роботот покажувачот на чело јазол. Значи, ние сме на 1 елемент. Ние треба да одиме напред уште 2 елементи пред да можеме да вметнете, па ние да го користите за телефонска линија int i = 1; i <3; i + + и во секоја повторување на јамка, унапредиме нашите Роботот покажувачот нанапред со 1 јазол со проверка дали наредното поле тековната јазол е нула, а ако не е, се движи нашиот Роботот покажувач кон следниот јазол со поставување еднаква на следниот покажувач на тековната јазол. Значи, бидејќи нашите за јамка вели да го направите тоа двапати, Дојдовме до 3 јазол, и еднаш нашите Роботот покажувачот достигна јазол по која сакате да вметнете нашиот нов број, како ние всушност направиме вметнување? 

Па, нашата нова цел број мора да биде вметната во листата како дел од своите јазол struct, бидејќи ова е навистина низа на јазли. Значи, ајде да се направи нов покажувач на јазол се вика 'new_node " и го постави на точка за меморија што ние сега се распредели на грамада за јазол себе, и колку меморија не ни треба да ги распредели? Па, големината на еден јазол, и ние сакаме да се постави вредност областа на цел број кој сакаме да го внесете. Да речеме, 6. Сега, на јазол содржи нашите целобројна вредност. Тоа е исто така добра пракса да се иницијализира следната областа на новиот јазол да се укаже на нула, но сега што? 

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

Значи, да се поедностави тоа, да речеме дека нашата прва 4 јазли се нарекуваат А, Б, Ц и Д, со стрели претставуваат синџир на покажувачи кои ги поврзуваат јазли. Значи, ние треба да го вметнете нашиот нов јазол помеѓу јазли C и D. Тоа е критичко да го стори тоа во вистинската цел, а јас ќе ви покажеме зошто. 

Да ги погледнеме на погрешен начин да го направи тоа во прв план. Еј, знаеме нов јазол мора да дојде веднаш по Ц, па ајде постави следната покажувачот на C да се укаже new_node. Добро, се чини во ред, ние само треба да завршам сега со правење следната новиот јазол покажувачот точка за развој, Но чекајте, како можеме да го направите тоа? Единственото нешто што може да ни каже каде d е, беше следниот покажувачот претходно зачувани во C, но ние едноставно rewrote дека покажувачот да укаже на нов јазол, па ние веќе немаш поим од каде D е во меморијата, и ние сме изгубени остатокот на листата. Не е добро на сите. 

Значи, како ние да го направите ова, нели? Прво, точка следната покажувачот новиот јазол на Д Сега, двете нови јазол и C следната совети се укажува на истиот јазол, Д, но тоа е во ред. Сега можеме да укаже следната покажувачот на C на нов јазол. Значи, ние го направиле тоа без губење на сите податоци. Во код, C е тековната јазол дека traversal покажувачот Роботот е да се покажува, и Д се претставени од страна на јазол посочи до следната областа на тековната јазол, или Роботот → следната. Значи, ние првиот сет следната покажувачот новиот јазол да се укаже Роботот → следната, На ист начин можеме рече следната покажувачот new_node треба точка до D на илустрацијата. Потоа, ние може да се постави следното покажувач на тековната јазол на нашиот нов јазол, како што моравме да чекаме да се укаже C до new_node во цртежот. Сега сè е во ред, и ние не ја загубивме ги пратите на сите податоци, а ние бевме во можност да само држи нашиот нов јазол во средината на листата без обновата на целата работа, па дури и менувањето на било какви елементи начинот на кој ние би требало да со фиксна должина низа. 

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

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

Моето име е Џексон Steinkamp, ​​ова е CS50.