[Powered by Google Translate] У праграмаванні, мы часта павінны падаваць спісы значэнняў, такія як імёны студэнтаў у раздзеле або іх вынікі на апошняй віктарыны. 

У мове C, заявіў масівы могуць быць выкарыстаны для захоўвання спісаў. Лёгка пералічыць элементы спісу захоўваюцца ў масіве, і калі вам трэба атрымаць доступ ці змяніць га элемента спісу для некаторага адвольнага індэкса I, што можа быць зроблена ў пастаянным часу, але масівы маюць недахопы. 

Калі мы аб'явім іх, мы абавязаны сказаць, фронт, як яны вялікія, гэта значыць, колькі элементаў яны могуць захоўваць і наколькі вялікі гэтыя элементы, якія вызначаюцца іх тыпам. Напрыклад, унутр обр (10) можа захоўваць 10 пунктаў , Якія з'яўляюцца памер Int. 

Мы не можам змяніць памер масіва пасля дэкларацыі. Мы павінны стварыць новы масіў, калі мы хочам захаваць некалькі элементаў. Прычына гэтага абмежаванні ў тым, што існуе наша Праграма захоўвае ўвесь масіў як бесперапынны кавалак памяці. Кажуць, што гэта буфер, дзе мы захоўвалі ў нашым масіве. Там могуць быць і іншыя зменныя размешчаны ў непасрэднай блізкасці да масіву ў памяці, таму мы не можам проста зрабіць масіва больш. 

Часам мы хацелі б гандляваць хуткі доступ да дадзеных масіва хуткасці для трохі больш гнуткасці. Калі ласка, увядзіце звязаны спіс, іншая асноўная структура дадзеных Вы можа быць не так добра знаёмыя. На высокім узроўні, Звязаны спіс захоўвае дадзеныя ў паслядоўнасць вузлоў , Якія звязаны адзін з адным спасылкамі, адсюль і назва «звязаны спіс. Як мы ўбачым, гэтая розніца ў дызайне прыводзіць да розных перавагі і недахопы чым масіў. 

Вось код C па вельмі просты звязаны спіс цэлых лікаў. Вы бачыце, што мы ўяўляем кожнаму вузлу У спісе, як структура, якая утрымоўвае 2 рэчы, цэлае для захоўвання пад назвай «Вал» і спасылку на наступны вузел у спісе , Якія мы прадстаўляем у якасці паказальніка называецца "Далей". Такім чынам, мы можам адсачыць увесь спіс з дапамогай ўсяго аднаго паказальніка на вузле 1, і тады мы зможам выканаць наступныя паказальнікі на 2-й вузел, да 3-га вузлу, да 4-га вузлу, і гэтак далей, пакуль мы не атрымаем да канца спісу. 

Вы маглі б глядзець 1 Перавага гэтага ёсць на статычную структуру масіва - з звязанага спісу, нам не трэба вялікі кавалак памяці ў цэлым. Першы вузел спісу маглі б жыць на гэтым месцы ў памяці, і 2-га вузла можа быць на ўсім шляху сюды. Мы можам дабрацца да ўсіх вузлоў, незалежна ад таго, дзе ў памяці яны ёсць, таму што, пачынаючы з першага вузла, наступнага паказальніка кожнага вузла кажа нам дакладна, куды ісці далей. 

Акрамя таго, мы не павінны гаварыць фронт наколькі вялікі звязаны спіс будзе так, як мы робім з статычныя масівы, так як мы можам працягваць дадаваць вузлы ў спіс тых часоў, пакуль ёсць вольнае месца дзесьці ў памяці для новых вузлоў. Таму, звязаных спісаў можна лёгка змяніць памер дынамічна. Скажам, пазней у праграме, нам трэба дадаць некалькі вузлоў у нашым спісе. Для ўстаўкі новага вузла ў нашым спісе на лета, усё, што нам трэба зрабіць, гэта вылучыць памяць для гэтага вузла, пляснуць у значэнні дадзеных, , А затым змясціць яго там, дзе мы хочам шляхам карэкціроўкі адпаведных паказальнікаў. 

Напрыклад, калі мы хочам размясціць вузел паміж 2-й і 3-й вузлы спісу,  Мы не павінны былі б рухацца 2-й або 3. Вузлы на ўсіх. Сказаць, што мы чырвоныя ўстаўкі гэтых вузлоў. Усё, што мы павінны былі б зрабіць, гэта ўсталяваць наступны паказальнік новага вузла паказваць на 3-м вузле , А затым перамантаваць наступны паказальнік 2-га вузла паказваюць на нашым новым вузле. Такім чынам, мы можам змяніць памер нашых спісаў на лета З нашага кампутара не спадзявацца на індэксацыю, а на сувязі з дапамогай паказальнікаў для іх захоўвання. 

Тым не менш, недахоп звязаныя спісы з'яўляецца тое, што, у адрозненне ад статычнага масіва, Кампутар не можа проста скокнуць у сярэдзіну спісу. Так як кампутар павінен наведаць кожны вузел у звязаным спісе каб дабрацца да наступнага, гэта зойме больш часу, каб знайсці пэўны вузел чым гэта было б у масіве. Каб прайсці ўвесь спіс займае час, прапарцыйнае да даўжыні спісу, або O (N) у асімптатычнай наймення. У сярэднім, дасягнуўшы любога вузла таксама займае час, прапарцыйнае да н. 

Цяпер, давайце на самай справе напісаць код , Які працуе са звязанымі спісамі. Скажам, мы хочам звязаны спіс цэлых лікаў. Мы можам прадставіць вузел у наш спіс яшчэ раз як структура з 2 палямі, Цэлы лік называецца "Вал" і наступны паказальнік на наступны вузел спісу. Ну, здаецца досыць простым. 

Скажам, мы хочам напісаць функцыю, які праходзіць па спісе і выводзіць Значэнне, якое захоўваецца ў апошні вузел спісу. Ну, значыць, мы павінны будзем прайсці ўсе вузлы ў спісе каб знайсці апошняга, але так як мы не дадаем або выдаляючы, мы не хочам змяніць Унутраная структура наступнага паказальніка ў спісе. 

Такім чынам, нам спатрэбіцца паказальнік спецыяльна для абыходу які мы называем «гусенічныя». Яна будзе сканаваць праз усе элементы спісу , Выканаўшы наступную ланцужок паказальнікаў. Усё, што мы захавалі гэта паказальнік на вузел 1, або «галавы» спісу. Кіраўнік паказвае на першы вузел. Гэта тыпу паказальнік-на-вузла. 

Каб атрымаць фактычна першай вузел у спісе, мы павінны разнаймення гэтага паказальніка, але перш чым мы зможам разыменовать гэта, нам трэба праверыць калі паказальнік з'яўляецца нулявым першым. Калі ён пусты, спіс пусты, і мы павінны надрукаваць паведамленне, што, паколькі спіс пусты, няма апошняга вузла. Але, скажам, у спіс не пусты. Калі гэта не так, то мы павінны паўзці праз увесь спіс пакуль мы не атрымаем на апошні вузел спісу, і як мы можам сказаць, калі мы глядзім на апошні вузел у спісе? 

Ну, калі наступны паказальнік вузла з'яўляецца нулявым, Мы ведаем, што мы знаходзімся ў канцы З апошнім наступны паказальнік будзе мець наступны вузел у спісе, каб паказваць. Гэта добрая практыка, каб заўсёды мець наступны паказальнік апошняга вузла ініцыялізаваць да нуля мець стандартызаваны маёмасць, якое папярэджвае нас, калі мы дасягнулі канца спісу. 

Такім чынам, калі гусенічных → наступны пусты, памятаеце, што стрэлка сінтаксіс ярлык для разнаймення паказальнік на структуру, то доступ свайго наступнага поля эквівалентныя няёмка: (* Гусенічныя). Наступны. Як толькі мы выявілі, што апошні вузел, мы хочам надрукаваць гусенічных → Вал, значэнне ў бягучым вузле які мы ведаем, гэта апошні. У адваротным выпадку, калі мы яшчэ не ў апошнюю вузла ў спісе, мы павінны перайсці да наступнага вузла ў спісе і пераканайцеся, што гэта апошняя. Каб зрабіць гэта, мы проста ўсталяваць наш сканер паказальнік , Каб паказаць на наступнае значэнне бягучага вузла, , Гэта значыць на наступны вузел у спісе. Гэта робіцца шляхам усталёўкі Гусенічны = гусенічных → Далей. Тады мы паўтараем гэты працэс, з пятлёй напрыклад, пакуль мы не знойдзем апошні вузел. Так, напрыклад, калі гусенічных паказваў на галаву, Пакладзем гусенічных паказваюць на гусенічным → наступным, які гэтак жа, як у наступным поле 1-га вузла. Такім чынам, цяпер наш сканер паказвае на другім вузле, і, зноў жа, мы паўтараем гэта з пятлёй, пакуль мы не знайшлі апошняга вузла, гэта значыць, дзе наступны паказальнік вузла паказвае на нуль. І ў нас гэта ёсць, мы знайшлі апошняга вузла ў спісе, а каб надрукаваць яго значэнне, мы проста выкарыстоўваем гусенічных → знач. 

Перамяшчэнне не так ужо дрэнна, але тое, што аб устаноўцы? Дапусцім, мы хочам, каб ўставіць лік у 4-й пазіцыі У цэлага спісу. Гэта значыць паміж бягучых 3 і 4 вузлоў. Зноў жа, у нас ёсць для прагляду спісу толькі дабрацца да 3-га элемента, адзін мы ўстаўка пасля. Такім чынам, мы ствараем гусенічных паказальнік зноў прайсці спісу, праверыць, калі наша галава паказальнік з'яўляецца нулявым, і калі гэта не так, паказаць наш сканер паказальнік на галаўным вузле. Такім чынам, мы на 1-м элементам. Мы павінны ісці наперад яшчэ 2 элемента перш чым мы зможам ўставіць, таму мы можам выкарыстоўваць для цыклу Int я = 1; I <3, Я + + і ў кожнай ітэрацыі цыклу, прасоўваць наш сканер паказальнік наперад на 1 вузел , Правяраючы, калі наступнае поле бягучага вузла з'яўляецца нулявым, і калі гэта не так, перамесціце наш сканер паказальнік на наступны вузел , Усталяваўшы яго роўным наступны паказальнік бягучага вузла. Такім чынам, паколькі наш цыкл кажа, каб зрабіць гэта у два разы, мы дасягнулі 3. вузла, і як толькі наш сканер паказальнік дасягнуў вузел пасля які мы хочам ўставіць наш новы цэлы лік, Як мы на самай справе ўстаўка? 

Ну, наша новае цэлае павінен быць устаўлены ў спіс як частку сваёй уласнай структуры вузла, так як гэта сапраўды паслядоўнасць вузлоў. Такім чынам, давайце зробім новы паказальнік на вузел называецца "new_node" і ўсталяваць яго, каб паказаць на памяць, што мы зараз вылучыць ў кучы для самога вузла, памяці і колькі нам трэба вылучыць? Ну, памер вузла, і мы хочам ўсталяваць яго вал поле лік, якое мы хочам ўставіць. Скажам, 6. Цяпер вузел ўтрымлівае наш цэлае значэнне. Гэта таксама добрая практыка для ініцыялізацыі наступнага поля новага вузла паказваюць на нуль, Але што цяпер? 

Мы павінны змяніць ўнутраную структуру спісу і на наступны паказальнікаў, якія змяшчаюцца ў існуючых спісу 3 і 4 вузлоў. З наступнага паказальніка вызначаюць парадак спісу, і так як мы ўстаўкі нашага новага вузла проста ў сярэдзіне спісу, яна можа быць крыху больш складана. Гэта таму, што памятаю, наш кампутар толькі ведае размяшчэнне вузлоў у спісе з-за чарговага паказальнікі захоўваюцца ў папярэдніх вузлах. Такім чынам, калі мы калі-небудзь страціў любую з гэтых месцаў, кажуць, змяніўшы адну з наступных паказальнікаў у нашым спісе Напрыклад, сказаць, што мы змяніліся Наступны 3. вузла поля паказаць на некаторыя вузла сюды. Мы былі б не пашанцавала, таму што мы не хочам ёсць ідэі, дзе знайсці астатнія часткі спісу, і гэта, відавочна, вельмі дрэнна. Такім чынам, мы павінны быць вельмі асцярожныя, аб парадку , У якой мы маніпуляваць нашым наступным паказальнікаў падчас усталёўкі. 

Такім чынам, каб спрасціць гэта, давайце скажам, што нашы першыя 4 вузлоў называюцца A, B, C, і D, са стрэлкамі, які ўяўляе ланцужок паказальнікаў , Якія злучаюць вузлы. Такім чынам, нам трэба ўставіць наш новы вузел паміж вузламі C і D. Вельмі важна рабіць гэта ў правільным парадку, і я пакажу вам, чаму. 

Давайце паглядзім на няправільны спосаб зрабіць гэта першым. Гэй, мы ведаем, што новы вузел павінен прыйсці адразу пасля C, так што давайце ўсталяваць наступны паказальнік Сі паказваюць на new_node. Добра, здаецца, усё ў парадку, мы проста павінны скончыць зараз, робіць наступны пункт паказальнік на новы вузел у D, Але пачакайце, як мы можам гэта зрабіць? Адзінае, што можа сказаць нам, дзе D быў, быў наступны паказальнік Раней захоўваецца ў C, але мы проста перапісалі, што паказальнік каб яна паказвала на новы вузел, такім чынам, мы больш не маюць паняцця, дзе D знаходзіцца ў памяці, і мы страцілі астатнюю частку спісу. Не падыходзіць. 

Такім чынам, як мы робім гэта правільна? Па-першае, пазначыць наступны паказальнік на новы вузел па адрасе D. Цяпер, як новы вузел і C у наступным паказальнікі паказваюць на той жа вузел, D, але гэта нармальна. Цяпер мы можам адзначыць наступны паказальнік C на новым вузле. Такім чынам, мы зрабілі гэта без страты дадзеных. У кодзе З бягучага вузла што абыход паказальнік гусенічных паказвае на, і D ўяўляе вузел, на які паказвае наступнае поле бягучага вузла, або гусенічным → Далей. Такім чынам, мы спачатку ўсталяваць наступны паказальнік новага вузла паказваюць на гусенічным → наступным, Сапраўды гэтак жа мы сказалі, наступны паказальнік павінен new_node паказваюць на D на малюнку. Тады, мы можам усталяваць наступны паказальнік бягучага вузла на нашым новым вузле, гэтак жа, як мы павінны былі чакаць да кропкі С, каб new_node на чарцяжы. Цяпер усё ў парадку, і мы не страцілі адсочванне любых дадзеных, і мы змаглі проста прытрымлівацца нашага новага вузла ў сярэдзіне спісу без перабудовы ўсё гэта ці нават перамяшчэнне любых элементаў тое, як мы павінны былі б з фіксаванай даўжынёй масіва. 

Такім чынам, звязаныя спісы з'яўляюцца асноўнымі, але важна, дынамічныя структуры дадзеных якія маюць як перавагі, так і недахопы у параўнанні з масіваў і іншых структур дадзеных, і, як гэта часта бывае ў кампутарнай навуцы, важна ведаць, калі выкарыстоўваць кожны інструмент, так што вы можаце выбраць правільны інструмент для правільнай працы. 

Для атрымання дадатковай практыкай, паспрабаваць напісаць функцый выдаліць вузлы з звязанага спісу - не забывайце быць асцярожнымі аб парадку, у якім вы пераставіць Ваш наступны паказальнік, каб не страціць кавалак вашага спісу - ці функцыя для падліку вузлы ў звязаным спісе, ці весела адзін, каб змяніць парадак усе вузлы ў звязаным спісе. 

Мяне клічуць Джэксан Steinkamp, ​​гэта CS50.