[Гуляе музыка] 

Даг Lloyd: ОК, так што ў гэтая кропка ў працэсе, мы разгледзелі шмат асновам З Мы ведаем шмат пра зменных, масіваў, паказальнікі, усё, што добры матэрыял. Тыя, усё накшталт убудаваных паглядзець, як асновы, але мы можам зрабіць больш, праўда? Мы можам аб'яднаць рэчы разам у цікавых спосабаў. 

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

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

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

Але мы атрымаць толькі адзін стрэл на яго, мы не патрапіць у той казаць пра, на самай справе я неабходна 101 або мне трэба х плюс 20. Занадта позна, мы ўжо абвясціў Масіў, і калі мы хочам, каб атрымаць 101 або х плюс 20, мы павінны абвясьціць зусім іншы масіў, скапіяваць ўсе элементы масіва над, а затым у нас ёсць дастаткова. А што, калі мы не маюць рацыю, зноў жа, калі мы на самой справе трэба 102 або х плюс 40, мы павінны зрабіць гэта зноў. Так што яны вельмі нягнуткая для змены памеру нашы дадзеныя, але калі мы аб'яднаем разам некаторыя з асноў, якія мы ўжо даведаўся пра паказальнікі і збудаванняў, у прыватнасці, з выкарыстаннем дынамічнай памяці размеркаванне з Таноса, мы можа паставіць гэтыя часткі разам стварыць новыя дадзеныя structure-- A односвязанны спіс мы маглі б say-- што дазваляе нам расці і скароціцца калекцыю значэнняў і мы не будзе мець ніякага невыкарыстоўваемай прасторы. 

Такім чынам, яшчэ раз, мы называем гэтую ідэю, гэта паняцце, звязаны спіс. У прыватнасці, у гэтым відэа мы казаць пра односвязный спіс, а потым яшчэ відэа мы пагаворым аб ўдвая звязаныя спісы, якія гэта проста варыяцыя на тэму тут. Але односвязанны спіс складаецца з вузлоў, вузлы проста быць абстрактнай term-- гэта проста тое, што я тэлефаную гэта свайго роду Структура, у асноўным, я? Проста буду называць яго node-- і гэта вузел мае двух членаў, ці два поля. Ён мае дадзеныя, звычайна лік, лік з якая плавае кропкай характар, ці можа быць некаторым іншым тыпам дадзеных, што вы вызначыліся з тыпам DEF. І яна ўтрымлівае паказальнік на іншы вузел таго ж тыпу. 

Такім чынам, мы маем дзве рэчы ўнутры гэты вузел, дадзеныя і паказальнік на іншы вузел. І калі вы пачынаеце візуалізаваць гэта, вы можаце думаць пра гэта як ланцуг вузлоў, злучаныя адзін з адным. У нас ёсць першы вузел, яго змяшчае дадзеныя і паказальнік да другога вузла, які змяшчае Дадзеныя, і паказальнік на трэцім вузле. І вось чаму мы называем яго Звязаны спіс, яны звязаны адзін з адным. 

Што робіць гэта спецыяльнае Структура вузла выглядаць? Ну, калі вы памятаеце з нашага відэа на вызначэнне карыстацкіх тыпаў, з тыпу DEF, мы можам вызначыць structure-- і увядзіце вызначыць структуру, як гэта. tyepdef структуры sllist, а затым я выкарыстоўваючы значэнне слова тут адвольна для абазначэння любога тыпу дадзеных на самай справе. Вы можаце перайсці на цэлы лік або паплаўка, Вы маглі б мець усе, што вы хочаце. Гэта не абмяжоўваецца толькі цэлыя лікі, або што-небудзь падобнае. Так значэнне толькі адвольнае Тып дадзеных, а затым паказальнік на іншы вузел таго ж тыпу. 

Цяпер, ёсць трохі злавіць тут з вызначэння структуры калі гэта структура самакіравання спасылачныя. Я павінен мець часовы імя для майго будынкі. У канцы дня я відавочна хочуць называць яго SLL вузел, што ў канчатковым рахунку новы назваць частка майго вызначэння тыпу, але я не магу выкарыстоўваць SLL вузел ў сярэдзіне гэтага. Прычына ў тым, я не стварыў тып завецца SLL вузел пакуль я не ўдарыў гэтага канчатковую кропку тут. Да гэтага моманту, я павінен мець яшчэ адзін спосаб, каб звярнуцца да гэтага тыпу дадзеных. 

І гэта само спасылачныя тып дадзеных. Гэта, S тып дадзеных з Структура, якая змяшчае дадзеныя, і паказальнік на іншы Структура аднаго тыпу. Таму мне трэба, каб мець магчымасць звярнуцца да Гэты тып дадзеных, па меншай меры часова, так даючы яму часовае Імя структуры sllist дазваляе мне сказаць, то я хачу паказальнік на іншай структуры sllist, на структуру sllist зорка, а затым пасля таго як я завяршыў вызначэнне, Цяпер я магу назваць гэты тып SLL вузел. 

Дык вось чаму вы бачыце там часовае імя тут, а пастаянны імя тут. Часам вы можаце ўбачыць вызначэння структуры, напрыклад, што не самастойна спасылачныя, што ня ёсьць імя спецификатор тут. Было б проста сказаць TYPEDEF-структуру, адкрыць фігурную дужку, а затым вызначыць яго. Але калі вы структура само спасылачныя, а гэта адзін, Вы павінны паказаць часовае імя тыпу. Але ў канчатковым выніку, у цяперашні час што мы зрабілі гэта, мы можам проста звярнуцца да гэтыя вузлы, агрэгаты, гэтыя а SLL вузлоў для мэт у астатняй частцы гэтага відэа. 

Добра, так што мы ведаем, як стварыць звязаны спіс вузел. Мы ведаем, як вызначыць звязаны спіс вузлоў. Цяпер, калі мы збіраемся, каб пачаць выкарыстоўваць іх, каб сабраць інфармацыю, ёсць пара аперацый мы трэба зразумець і працаваць. Мы павінны ведаць, як стварыць звязаны спіс з паветра. Калі няма ўжо ніякага спісу, мы хочам, каб пачаць адзін. Такім чынам, мы павінны быць у стане стварыць звязаны спіс, мы павінны, верагодна, шукаць па спісе спасылак знайсці элемент мы шукаем. Мы павінны быць у стане ўставіць новыя рэчы ў спісе, мы хочам, каб наш спіс, каб мець магчымасць расці. І сапраўды гэтак жа, мы хочам, каб мець магчымасць выдаліць рэчы з нашага спісу, мы хочам, каб наш спіс, каб мець магчымасць скарачацца. І ў канцы нашага праграмы, асабліва калі ўспомніць, што мы дынамічнага размеркавання памяці каб пабудаваць гэтыя спісы звычайна мы хочам, каб вызваліць ўсе, што памяць калі мы зрабілі з ім працаваць. І таму мы павінны быць у стане выдаліць Ўвесь звязаны спіс у адным няўдачу махам. Так давайце пройдзем некаторыя з гэтых аперацый і як мы маглі б візуалізаваць іх, гаварыць у псевдокода кода адмыслова. Таму мы хочам, каб стварыць звязаны спіс, так што, магчыма, мы хачу, каб вызначыць функцыю з гэтага прататыпа. SLL вузел зорка, ствараць, і я праходжання ў адзін аргумент, некаторыя адвольныя дадзеныя тып зноў, некаторага адвольнага тыпу дадзеных. Але я returning-- гэтую функцыю варта вярнуцца да мяне паказальнік, каб аднакратна Звязаны спіс вузел. Зноў жа, мы спрабуем стварыць звязаны спіс з паветра, так што мне трэба паказальнік на што спіс, калі я зрабіў. 

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

Затым мы хочам, каб запоўніць ў полі, мы хочам, каб ініцыялізаваць значэнне поля і ініцыялізаваць наступнае поле. А потым мы хочам, мэтай якіх у канчатковым выніку, як Прататып функцыі indicates-- мы хочам вярнуць паказальнік на SLL вузла. Так што зрабіць гэта выглядаць візуальна? Ну, па-першае, мы збіраемся, каб дынамічна вылучыць месца для новага вузла SLL, такім чынам, мы malloc-- гэта візуальнае прадстаўленне вузла мы толькі што стварылі. І мы правяраем, каб пераканацца, гэта не null-- ў гэтым выпадку, карціна не будзе мець паказана, калі гэта было пустым, мы б запусціць з памяці, так што мы добра ісці туды. Так што цяпер мы да кроку З, ініцыялізаваць поле вузлы значэнне. Ну, на аснове гэтай функцыі тэлефануйце, я выкарыстоўваю тут, Падобна на тое, я хачу, каб прайсці ў 6, Так што я 6 у полі значэння. Цяпер, ініцыялізаваць наступнае поле. Ну, што я збіраюся зрабіць там, няма нічога побач, справа, гэта адзінае, што ў спісе. Так што ў наступны момант у спісе? 

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

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

Цяпер, скажам, мы ўжо вялікі ланцуга, і мы хочам, каб знайсці нешта ў ім. І мы хочам, функцыю, якая збіраецца вярнуцца сапраўдным або ілжывым, у залежнасці ад таго, ці існуе значэнне ў гэтым спісе. Прататып функцыі, або Заяву для гэтай функцыі, можа выглядаць this-- BOOL знайсці, і то мы хочам, каб прайсці ў двух аргументаў. 

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

І тады другая рэч мы перадаем зноў адвольна some-- незалежна ад тыпу дадзеных мы шукаю там унутры мы спадзяемся, адзін з вузлоў у спісе. Такім чынам, якія крокі? Ну, першае, што мы робім, гэта мы ствараем паказальнік папярочны паказваючы на ​​галаву спісаў. Ну, чаму мы гэта робім, мы ўжо ёсць паказальнік на галаву спісаў, чаму б нам проста не рухацца, што адзін вакол? Ну, як я толькі што сказаў ,, гэта сапраўды важна для нас заўсёды сачыць з вельмі першы элемент у спісе. І так на самой справе лепш стварыць дублікат, што і выкарыстоўваць не для перамяшчэння, таму мы ніколі не выпадкова адысці, ці мы заўсёды ёсць паказальнік на нейкі момант, які Права на першы элемент спісу. Так што лепш, каб стварыць Другі, які мы выкарыстоўваем, каб рухацца. 

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

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

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

Так 2, што я шукаю? Ну, няма, так што замест я будзе рухацца да наступнага. Так у асноўным, я б сказаў, Траў роўная TRAV побач. Ёсць 3, што я шукаю, няма. Так што я па-ранейшаму ісці ня праз, пакуль у рэшце рэшт атрымаць да 6, які з'яўляецца тое, што я шукаю Для заснавана на выклік функцыі У мяне ў верхняй там і так я зрабіў. 

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

І гэта свайго роду адной угодзе, што мы ёсць са звязаным спісам вершы масіваў, гэта мы не маем адвольнага доступу больш. Мы не можам проста сказаць, я хачу каб перайсці да 0-й элемент, ці 6-й элемент майго масіва, які я магу зрабіць у масіве. Я не магу сказаць, што я хачу, каб перайсці да 0-я элемент або 6-й элемент, або 25-элемент майго звязанага спісу, няма індэкс, звязаны з імі. І так сапраўды не мае значэння калі мы захаваем наш спіс у парадку. Калі вы хочаце, каб вас , Вядома, можна, але ёсць няма прычыны, чаму яны павінны захаваць у любым парадку. Такім чынам, яшчэ раз, давайце паспрабуем знайсці 6 у гэтым спісе. Ну, мы пачынаем на пачатак, мы не знаходзім 6, а затым мы працягнем, не знойдучы 6, пакуль мы ў канчатковым выніку не атрымаеце тут. Так што цяпер Trav паказвае на вузел які змяшчае 8, а шэсць не там. 

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

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

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

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

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

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

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

Дык вось наш спіс, яна складаецца з чатыры элемента, вузел, які змяшчае 15, што паказвае на вузел які змяшчае 9, які паказвае на вузле, які змяшчае 13, што паказвае на вузел, які змяшчае 10, які мае нулявое Паказальнік ў сваім наступным паказальнік так што гэта канец спісу. Таму мы хочам, каб ўставіць Новы вузел са значэннем 12 У пачатку гэтага Спіс, што мы робім? Ну, па-першае, мы Таноса прастору для вузел, а затым пакласці 12 там. 

Так што цяпер мы дасягнулі кропка прыняцця рашэння, праўда? У нас ёсць некалькі паказальнікі, якія мы маглі б рухацца, што трэба рухацца, мы ў першую чаргу? Ці павінны мы зрабіць 12 пункт новы кіраўнік list-- або, прабачце, мы павінны зрабіць 12 паказваюць на стары чале спісу? Ці мы павінны сказаць, што Спіс у цяперашні час пачынаецца ў 12 гадоў. Там гэта адрозненне там, і мы будзем глядзець на тое, што адбываецца з абодвума у ​​секунду. 

Але гэта прыводзіць да вялікая тэма для бакавой панэлі, які што адзін з падступныя рэчы са звязанымі спісамі з'яўляецца арганізацыя паказальнікі у правільным парадку. Калі вы перамесціце рэчы з таго, Вы можаце ў канчатковым выніку выпадкова сіротамі астатняе спісу. І вось таму прыклад. Такім чынам, давайце з ідэяй of-- Ну, мы толькі што стварылі 12. Мы ведаем, 12 будзе новы кіраўнік спісу, і так, чаму б нам проста не перайсці паказальнік Спіс пазначыць там. 

ОК, так што гэта добра. Так што цяпер, калі робіць наступны пункт 12? Я маю на ўвазе, візуальна мы бачым што будзе паказваць на 15, як людзі гэта сапраўды відавочна для нас. Як кампутар ведаеце? Мы не маем нічога паказваючы на ​​15 больш, праўда? 

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

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

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

Такім чынам, яшчэ адна рэч, каб гаварыць аб. Што рабіць, калі мы хочам, каб пазбавіцца ад ўвесь звязаны спіс адразу? Зноў жа, мы mallocing Усё гэта прастору, і таму мы трэба вызваліць яго, калі мы зрабілі. Так што цяпер мы хочам, каб выдаліць ўвесь звязаны спіс. Ну, тое, што мы хочам зрабіць? 

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

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

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

Такім чынам, мы have-- і я таксама выцягнуў да нашай кадраў стэка ілюстрацыі з нашага відэа на стэкаў выклікаў, і, спадзяюся, усё гэта разам пакажу вам, што адбываецца. Дык вось наш код псевдокод. Калі мы дасягнем нуль паказальнік, спыніць, інакш, выдаліць астатнюю частку спісу, Затым вызваліць бягучы вузел. Так што цяпер, list-- паказальнік, што мы перадаючы знішчыць ачкоў да 12. 12 не з'яўляецца нулявым паказальнікам, таму мы збіраецца выдаліць астатнюю частку спісу. 

Што з'яўляецца выдаленне Астатнія з нас удзельнічае? Ну, гэта азначае, робячы патэлефануеце, каб знішчыць, кажучы што 15 гэта пачатак Астатняя частка спісу, які мы хочам знішчыць. І таму выклік, каб знішчыць 12 від на ўтрыманне. Гэта замарожаныя там, чакаючы патэлефануеце, каб знішчыць 15, каб скончыць сваю працу. 

Ну, 15 не з'яўляецца нулявым паказальнікам, і так што гэта, каб сказаць, усё ў парадку, добра, выдаліць астатнюю частку спісу. Астатняя частка спісу пачынае у 9, і таму мы проста чакаць, пакуль вы не выдаліце ​​ўсе, што матэрыял, а затым вярнуцца і выдаліць мяне. Ну 9 скажа, ну, Я не пусты паказальнік, так што выдаліце ​​астатнія спіс тут. І таму паспрабуйце і знішчыць 13. 13 кажа, што я не пусты паказальнік, Тое ж самае, ён перадае даляр. 10 не пусты паказальнік, 10 змяшчае пусты паказальнік, але 10 не само па сабе з'яўляецца NULL паказальнік прама цяпер, і так яна праходзіць даляр таксама. 

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

І так, што фіялетавы кадра now-- на Верх stack-- гэта актыўны кадр, але гэта робіцца. Калі мы дасягнулі нулявы паказальнік, спыніцца. Мы нічога не робім, мы не можа вызваліць нулявы паказальнік, мы не Таноса любы прастору, і таму мы зрабілі. Так, што функцыі кадра руйнуецца, і мы resume-- мы забраць, дзе мы пакінулі ад з наступнага вышэйшай аднаго, які гэта цёмна-сіняя рамка тут. Такім чынам, мы забраць там, дзе мы спыніліся. Мы выдалілі астатнюю частку Спіс ўжо, так што зараз мы збіраецца вызваліць бягучыя вузлы. Так што цяпер мы можам вызваліць гэты вузел, і ў цяперашні час мы дасягнулі канца функцыі. І так, што функцыя кадр будзе знішчаны, і мы забраць у блакітным адзін. 

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

Што здарылася б, хоць, Калі б мы зрабілі штосьці не так? Гэтак жа, як калі мы спрабавалі дадаць элемент. Калі мы пераблыталіся, калі ланцуг мы не падключыць паказальнікі у правільным парадку, калі мы проста вызваліў першы элемент, калі мы проста вызвалілі галава спісу, зараз мы няма ніякага спосабу спаслацца на астатняя частка спісу. І таму мы б сіротамі ўсе, мы б мелі тое, што называецца ўцечка памяці. Калі вы памятаеце з нашага відэа на дынамічным размеркаванні памяці, гэта не вельмі добрая рэч. 

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

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

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

Я Дуг Лойд, гэта CS50.