[МУЗЫКА ГУЛЯЕ] David J. малая: Добра. Гэта CS50. Гэта пяць тыдні працягваў, і мы ёсць добрыя навіны і дрэнныя навіны. Так Добрай навіной з'яўляецца тое, што CS50 запускае ў гэтую пятніцу. Калі вы хацелі б далучыцца да нас, накіравацца ў звычайнай URL тут. ня Нават лепшыя навіны, не лекцыя быць панядзелак 13.. Крыху менш за лепшага навіны, віктарына нуля ў наступную сераду. Больш падрабязна можна знайшоў па гэтым адрасе тут. І ў бліжэйшыя пару дзён мы будзем запаўняючы прабелы з адносна нумароў што мы зарэзервавалі. Лепш навіна заключаецца ў тым, што буду быць курс ўсёй водгук сесія ў бліжэйшую Панядзелак увечары. Заставайцеся з намі, каб Курсу сайт для размяшчэння і дэталяў. Раздзелы, нават калі ён з'яўляецца свята, таксама сустрэнецца таксама. Лепшы навіны, лекцыі ў наступную пятніцу. Так што гэта традыцыя, якую мы ёсць, у адпаведнасці з вучэбнай праграме. Просто-- гэта будзе дзіўна. Вы ўбачыце рэчы, як структуры дадзеных сталай часу і хэш-табліцы, дрэвы і спрабуе. І мы будзем казаць аб праблемах дня нараджэння. Цэлая куча рэчаў чакае ў наступную пятніцу. Добра. Ва ўсякім выпадку. Так нагадаем, што мы былі упорам на гэтай карціне тое, што ўнутры памяці нашага кампутара. Так памяці або аператыўнай памяці, дзе праграмы існуюць у той час як вы працуеце іх. Калі вы двойчы пстрыкніце значок, каб запусціць некаторыя праграмы або двойчы пстрыкніце значок, каб адкрыць файл, ён загружаны з жорсткага дыск або цвёрдацельны назапашвальнік ў аператыўнай памяці, памяці адвольнага доступу, дзе ён жыве, пакуль харчаванне не адключыцца, вечка наўтбука зачыняецца, або выхадзе з праграмы. Цяпер, калі памяць, з якія вы, верагодна, 1 гігабайт у гэтыя дні, 2 гігабайт, ці нават нашмат больш, як правіла, выкладзеныя па зададзенай праграме у гэтым выглядзе прамавугольнай Канцэптуальная мадэль у выніку чаго мы маем стэк на дне і кучу іншых рэчаў на самым версе. Справа на самым версе мы бачылі на гэтым малюначку раней, але не казаў пра гэта так званы тэкставы сегмент. Сегмент тэксту проста мудрагелісты спосаб сказаць нулі і тыя, якія скласці свой фактычны скампіляваць праграму. Такім чынам, калі вы двойчы пстрыкніце Microsoft Word на Mac або ПК, або пры запуску кропку слэш Марыё на Linux кампутар у вашым акне тэрміналу, нулі і адзінкі, якія складаюць Слова або Марыё часова захоўваюцца ў аператыўнай памяці кампутара ў так званы тэкставы сегмент для канкрэтнай праграмы. Ніжэй, што ідзе ініцыялізацыя і неинициализированные дадзеныя. Гэта такія рэчы, як глабальныя зменныя, што мы не выкарыстоўвалі многія, але часам мы ў меў глабальныя зменныя або статычна вызначаны радкі, закадавана такія словы, як "прывітанне" , Якія не прыняты ў ад карыстальніка якія жорстка ў вашу праграму. Зараз, на дне мы ёсць так званы стэкам. І стэк, да гэтага часу, мы былі выкарыстоўваючы для якіх відаў мэтаў? Што стэк выкарыстоўваецца для? Так? Аўдыторыя: Функцыі. David J. малая: Для функцый? У якім сэнсе для функцый? АЎДЫТОРЫЯ: Калі вы выклікаеце функцыю, Аргументы капіююцца ў стэк. David J. малая: Точно. Пры выкліку функцыі, яе Аргументы капіююцца ў стэк. Таму любыя іксы або Y сайт або сайт або B, што вы перадаеце ў функцыю часова паставіць на так званы стэкам, як аднаго з Анненберг Сталовая латкі, а таксама рэчы, як лакальных зменных. Калі ваша функцыя Foo або падпампоўкі Функцыя мець лакальныя зменныя, як тэмп, тыя два ў канчатковым выніку ў стэку. Зараз, мы не будзем занадта шмат казаць пра ім, але гэтыя зменныя асяроддзі унізе мы ўбачылі некаторы час таму, калі Я быў важдацца з клавіятуры адзін дзень і я пачаў доступу рэчы як агду 100 ці агду 1000, проста elements-- я забываю numbers-- але што не павінны былі быць даступныя мне. Мы пачалі бачыць некаторыя фанкі знакі на экране. Гэта былі так званыя зменныя асяроддзі як глабальных параметраў для асабістых Праграма або для майго кампутара, а не звязаны з нядаўняй памылка, што мы абмяркоўвалі, Кантузія, што было жыцця даволі шмат кампутараў. Цяпер, нарэшце, у сучасным цэнтры ўвагі мы ў канчатковым рахунку быць у кучы. Гэта яшчэ адзін кавалак памяці. І прынцыпова ўсё гэта памяць той жа самы матэрыял. Гэта тое ж самае абсталяванне. Мы толькі выгляд лячэння розных кластараў байтаў для розных мэтаў. Куча таксама будзе дзе зменныя і памяці, што вы пытаецеся ад аперацыйнай сістэмы часова захоўваецца. Але ёсць свайго роду праблемы тут, як і карціна мяркуе. Мы-то ёсць два караблі каля сутыкацца. Таму што, як вы выкарыстоўваеце ўсе больш і больш стэка, і, як мы бачым сёння, наперад, як вы выкарыстоўваеце ўсе больш і больш куча, безумоўна, дрэнныя рэчы могуць здарыцца. І на самай справе, мы можам выклікаць, што наўмысна ці ненаўмысна. Так у кульмінацыі апошняга раз быў гэтая праграма, якія ня служаць любая функцыянальная Мэта акрамя прадэманстраваць як вам, як дрэнны хлопец сапраўды можа прыняць Перавага памылак у чужой праграме і ўзяць на сябе праграму ці нават Увесь кампутарная сістэма або сервер. Так што проста зазірнуць ненадоўга, вам заўважыць, што асноўныя унізе прымае ў камандным радку Аргументы, як за ARGV. І гэта мае выклік функцыі F, істотна безназоўны функцыя называецца е, і гэта праходжанне ў ARGV [1]. Таму, што б слова карыстальнік ўводзіць у на выводзіцца пасля імя гэтай праграмы, а затым гэтая адвольная функцыя да зверху, е, займае ў радку, AKA сімвал *, як мы пачалі абмяркоўваць, і ён проста называе яго "бар". Але мы маглі б называць яго інакш. А потым ён заяўляе, усярэдзіне з F, масіў сімвалаў называецца c-- 12 такіх знакаў. Зараз, па гісторыі, якую я распавядаў хвіліну таму, калі ў памяці з'яўляецца с, або тыя, 12 сімвалы будзе ў канчатковым выніку? Проста каб быць ясна. Так? АЎДЫТОРЫЯ: На стэку. David J. малая: На стэку. Так з з'яўляецца лакальнай зменнай. Мы просім 12 сімвалаў або 12 байт. Тыя збіраюцца ў канчатковым выніку на так званым стэку. Цяпер, нарэшце, гэта іншая функцыя што на самой справе вельмі карысна, але мы на самай справе не выкарыстоўваецца гэта самі, strncopy. Гэта азначае радок копію, але толькі рускія літары, п знакаў. Так п сімвалаў будзе капіюецца з бара ў с. А колькі? Даўжыня панэлі. Такім чынам, іншымі словамі, што адна лінія, strncopy, збіраецца капіяваць афіцыйна забараніць і ст. Зараз, проста выгляд прадбачыць Мараль гэтай гісторыі, што патэнцыйна праблематычна тут? Нават пры тым, што мы правяраем даўжыню з бара, і перадаючы яе ў strncopy, што вашы кішкі кажу вам гэта яшчэ зламанае аб гэтай праграме? Так? АЎДЫТОРЫЯ: Не ўключае пакой для нулявога знака. David J. малая: Не ўключае пакой для нулявога знака. Патэнцыйна, у адрозненне ад Ранейшая практыка, мы нават не ёсць так шмат як плюс 1 да размясціць гэтую нулявы знак. Але гэта яшчэ горш, чым гэта. Што яшчэ мы не ў стане зрабіць? Так? АЎДЫТОРЫЯ: [неразборліва] David J. малая: Выдатна. Мы жорстка 12 даволі адвольна. Гэта не так шмат праблема, але той факт, што мы нават не правяраючы, калі даўжыня панэлі менш 12, у гэтым выпадку ён будзе бяспечна пакласці яго ў памяці называецца с, што мы выдзелена. Сапраўды, калі бар як 20 сімвалаў, Гэта функцыя па-відаць, капіраванне 20 знакаў з бара ў С, тым самым прымаць, па меншай меры 8 байтаў што гэта не павінна быць. Вось падтэкст тут. Такім чынам, у кароткатэрміновай, зламанай праграмы. Не такое ўжо вялікая справа. Можа быць, вы атрымаеце памылку сегментацыі. Мы ўсе былі памылкі ў праграмах. Мы ўсе маглі б мець памылкі у праграмах прама цяпер. Але тое, што маецца на ўвазе? Ну, вось у маштабе ў версіі што карціна памяці майго кампутара. Гэта дно маёй стэка. І сапраўды, у самым нізе гэта тое, што называецца бацькам руціна стэк, мудрагелісты спосаб сказаць, што гэта асноўны. Так што той, хто называецца функцыяй е, што мы гаворым пра. Такім чынам, гэта ў ніжняй частцы чаркі. Зваротны адрас нешта новае. Гэта заўсёды было там, заўсёды быў у гэтай карціне. Мы проста ніколі не звяртаў увагу на яе. Таму што атрымліваецца, то, як з працы з'яўляецца што, калі адна функцыя выклікае іншую, не толькі зрабіць, каб аргументы, што Функцыя атрымаць у стэк, не толькі зрабіць мясцовыя функцыя сайт Зменныя атрымаць у стэк, тое, што называецца зваротны адрас таксама атрымлівае пакласці ў стэк. У прыватнасці, калі асноўныя выклікі Фу, асноўныя сайт уласны адрас у памяці, бык-то, эфектыўна атрымлівае пакласці ў стэк так што, калі е робіцца выкананне якога ведае, дзе пераходзіць туды, у тэксце сегмент для таго, каб працягнуць выкананне. Так што, калі мы тут канцэптуальна, у асноўны, то F выклікаецца. Як е ведаю, хто у ручной кантроль задняй? Ну, гэта крыху дробка ў чырвоным тут, называецца зваротны адрас, ён проста правярае, што гэта за адрас вяртання? О, дазвольце мне перайсці назад на галоўную тут. І гэта крыху з спрашчэннем, таму нулёў і адзінак для магістралі тэхнічна тут у тэхнічным сегменце. Але гэта ідэя. е проста павінен ведаць, што туды, дзе кантроль у канчатковым рахунку ўзыходзіць. Але тое, як кампутары ўжо даўно выкладзеныя рэчы як лакальных зменных і Аргументы, як гэта. Такім чынам, у верхняй частцы гэтай карціны ў сіні кадр стэка для F, так што ўсе з памяці, што F спецыяльна выкарыстоўвае. Так, адпаведна, заўважыць, што Бар у гэтай карціне. Бар быў яго аргумент. І мы сцвярджалі, што аргументы Функцыі атрымаць у стэк. І з, вядома, Таксама ў гэтай карціне. І толькі для пазначэнняў мэтаў, заўважыць ў верхнім левым куце тое, што было б з кранштэйнам 0 і затым злёгку ўніз, направа з'яўляецца з кранштэйна 11. Такім чынам, іншымі словамі, вы можаце сабе ўявіць што ёсць сетка байт ёсць, першы з якіх верхні левы, ніжні з якіх апошні з гэтых 12 байт. Але цяпер паспрабуйце для хуткай перамоткі наперад. Што павінна адбыцца, калі мы перадамо у струннай бары, гэта больш, чым з? І мы не праверка, калі гэта сапраўды больш, чым 12. Якая частка гэтай карціны збіраецца страчаны байт 0, 1, 2, 3, кропка кропка кропка, 11, а затым дрэнна, 12, 13 праз 19? Што адбудзецца тут, калі вы вывесці з замовы што з кранштэйны 0 знаходзіцца на вяршыні і з кранштэйны 11 з'яўляецца свайго роду ўніз ў парадку? Так? АЎДЫТОРЫЯ: Ну, гэта будзе перазапісаць сімвал * бар. David J. малая: Так, гэта выглядае як Вы збіраецеся перазапісаць сімвал * бар. І што яшчэ горш, калі вы адпраўляеце на самай справе доўга Радок, вы маглі б нават перапісаць тое, што? У якасці зваротнага адрасу. Што яшчэ раз, гэтак жа, як дробка сказаць праграме, дзе вярнуцца да таго, калі F робіцца пры выкліку. Так што дрэнныя хлопцы, як правіла, робяць , Калі яны прыходзяць праз праграмы што яны цікава ці для выкарыстання, багі такім чынам што ён ці яна можа прымаць Перавага гэтай памылкі, як правіла, яны не атрымліваюць гэта правільна з першага разу. Яны проста пачаць перадачу, напрыклад, выпадковыя радкі ў вашай праграме, Ці на клавіятуры, або адкрыта яны, верагодна, напісаць невялікую праграму для ўсяго аўтаматычна генераваць радкі, і пачаць стукаць па вашай праграмы, адпраўка ў вялікай колькасці розных уваходаў на розных даўжынях. Як толькі вашыя збоі праграм, што дзіўная рэч. Таму што гэта азначае, што ён ці яна выявіла , Што, верагодна, сапраўды памылка. І тады яны могуць атрымаць больш разумны і пачаць факусоўку больш вузка аб тым, як выкарыстоўваць гэтую памылку. У прыватнасці, тое, што ён ці яна маглі б зрабіць, гэта адправіць, у лепшым выпадку, прывітанне. Нічога страшнага. Гэта радок, гэта досыць кароткім. Але што, калі ён ці яна пасылае, і мы будзем абагульняць яго як, Напад code-- так нулёў і тыя, якія робяць рэчы як RM-РФ, што выдаліць усе з жорсткага дыска ці рассылання спаму ці інакш атакаваць машыну? Такім чынам, калі кожны з іх Лісты проста ўяўляе, канцэптуальна, атака, атака, атака, атака, некаторыя дрэнныя код што хто-то напісаў, але калi гэта асоба досыць разумны, каб не толькі ўключаць у сябе ўсе з тых RM-RFS, але і ёсць свае апошнія некалькі байт быць лік, якое адпавядае ў адрас яго ці яе уласны код атака што ён ці яна прайшла ў толькі шляхам прадастаўлення яму ў камандным радку, Вы можаце эфектыўна падмануць кампутар у заўважаючы пры е робіцца выканання, о, гэта час для мяне, каб перайсці назад да чырвонага зваротнага адрасу. Але так як ён ці яна мае так ці інакш перакрываюцца, што зваротны адрас з іх уласным лікам, і яны досыць разумныя, каб наладзілі, што лік для абазначэння, як вы см у супер верхняй левы кут там, Фактычны адрас у кампутарнай гадоў Памяць аб некаторых з іх шкоднасны код, дрэнны хлопец можа падмануць кампутар у выкананні яго ці яе уласны код. І, што код, зноў жа, можа быць што заўгодна. Гэта звычайна называецца Абалонка код, які з'яўляецца толькі спосаб сказаць, што гэта не як правіла, такая простая рэч, як RM-РФ. Гэта на самай справе-то як Bash, або фактычнае праграма, якая дае яму ці яе праграмны кантроль, каб выканаць ўсё астатняе, што яны хочуць. Карацей кажучы, усё гэта паходзіць ад таго простага факту, што гэтая памылка ўдзел не правяраючы межы вашага масіва. І таму, што шляху Кампутары праца ў тым, што яны выкарыстоўваюць стэк ад эфектыўна, канцэптуальна, Ніжняя далей уверх, але тое элементы Вы націскаеце на стэк расці зверху ўніз, гэта неверагодна праблематычна. Зараз, ёсць спосабы абысці гэта. І, шчыра кажучы, ёсць мовы з якой абыйсці гэта. Java мае імунітэт, напрыклад, да гэтага канкрэтным пытанні. Таму што яны не даюць вам паказальнікі. Яны не даюць вам прамыя адрасы памяці. Так што з гэтай уладай, што ў нас да чаго дакранацца ў памяці мы хочам прыходзіць, па агульным прызнанні, вялікая рызыка. Так што сочыце. Калі, шчыра кажучы, на працягу некалькіх месяцаў ці гадоў, каб прыйсці ў любы час Вы чытаеце аб некаторых эксплуатацыі праграмы або сервера, калі вы ніколі не ўбачыць намёк-то як атакі перапаўнення буфера, або перапаўненне стэка і іншы тып атакі, блізкага па духу, колькі выклікае сайта назваць, калі вы яго ведаеце, гэта ўсё кажу аб проста перапоўненыя памер некаторым характарам масіў ці некаторы масіў у цэлым. Любыя пытанні, то, з гэтай нагоды? Не спрабуйце паўтарыць гэта дома. Добра. Так Таноса да гэтага часу быў наш новы Сябар у тым, што мы можам вылучыць памяць што мы не абавязкова ведаць, у загадзя, што мы хочам, каб мы не павінны на жорсткі код у нашу нумары праграм, як 12. Як толькі карыстач кажа нам, колькі Дадзеныя ён ці яна хоча, каб ўваход, мы можам Malloc што шмат памяці. Так Таноса аказваецца, каб Ступень мы выкарыстоўвалі яго, відавочна апошні раз, а затым вы, хлопцы ўжо выкарыстоўваюць яго для GetString неўсвядомлена для некалькі тыдняў, усё памяці Malloc ў зыходзіць з так званай дынамічнай памяці. І вось чаму GetString, напрыклад, можа вылучыць памяць дынамічна не ведаючы, што вы збіраецца ўвесці загадзя, ўручыць Вам паказальнік на гэтую памяць, і што памяць яшчэ ваш трымаць, нават пасля GetString аддачу. Таму нагадаем, у рэшце рэшт, што стэк пастаянна ідзе ўверх і ўніз, уверх і ўніз. І як толькі яна ідзе ўніз, што азначае любую памяць гэтая функцыя выкарыстоўваецца павінны ня быць выкарыстаны ў іншых месцах. Гэта значэння смеццевыя цяпер. Але куча тут. І, што прыемна пра Таноса з'яўляецца тое, што калі Таноса вылучае памяць тут, гэта не паўплывала, для Большая частка, стэкам. І таму любая функцыя можа атрымаць доступ памяці, якая была malloc'd, нават на функцыю як GetString, нават пасля таго, як ён будзе вернуты. Цяпер, адваротнае Таноса бясплатна. І на самай справе, гэта правіла вам трэба, каб пачаць прыняцця гэта любы, любы, у любы час вы карыстаецеся Таноса вы самі павінны выкарыстоўваць бясплатна, у рэшце рэшт, у той жа паказальнік. Увесь гэты час мы пісалі багі, код памылкі, па многіх прычынах. Але адзін з якіх быў з выкарыстаннем бібліятэкі CS50, які Сам наўмысна багі, гэта уцечак памяці. Кожны раз, калі вы назвалі GetString на працягу апошніх некалькіх тыдняў мы просім аперацыйныя Сістэма, Linux, на памяць. І вы ні разу не далі яго назад. І гэта не ў практыкаваць, добрая рэч. І Valgrind, адзін з інструменты, уведзеныя ў Pset 4, гэта ўсё аб дапамагаючы вам Цяпер знайсці памылкі, як, што. Але, на шчасце для Pset 4 вам не трэба выкарыстоўваць бібліятэку CS50 або GetString. Таму любыя памылкі, звязаныя з памяццю з'яўляюцца у канчатковым рахунку, будзе свой уласны. Так Таноса больш, чым проста зручная для гэтай мэты. Мы можам на самай справе цяпер вырашыць прынцыпова розныя праблемы, і прынцыпова вырашыць праблемы больш эфектыўна, як за тыдзень нуля абяцанне. Да гэтага часу гэта самая сэксуальная Структура дадзеных у нас былі. І па структуры дадзеных я проста маю на ўвазе спосаб канцэптуалізацыі памяці такім чынам, што выходзіць за рамкі проста кажу, Гэта Int, гэта сімвал. Мы можам пачаць кластара рэчаў разам. Так масіў выглядае наступным чынам. І тое, што было ключавым у аб Масіў з'яўляецца тое, што яна дае вам спіна да спіны кавалкі памяці, кожны з якіх будзе таго ж тыпу, Int, Int, Int, Int, або сімвал, знак, сімвал, сімвал. Але ёсць некалькі недахопаў. Гэта, напрыклад, гэта масіў памерам шэсць. Выкажам здагадку, што вы запоўніце гэты масіў з шасцю колькасці і затым, па тых ці іншых прычынах, ваш карыстальнік хоча даць Вы сёмы нумар. Дзе вы паклалі яго? Які ж выхад, калі ў вас ёсць стварылі масіў у стэку, напрыклад, толькі з тыдзень два абазначэння, што мы ўвялі, квадратных дужак з шэрагам ўнутры? Ну, у вас ёсць шэсць Лічбы ў гэтых скрынках. Што б вашыя інстынкты быць? Дзе б вы хацелі сказаць? АЎДЫТОРЫЯ: [неразборліва] David J. малая: Выбачайце? АЎДЫТОРЫЯ: Пакладзеце яго на канцы. David J. малая: Пакладзеце яго на канцы. Так што проста на правы, па-за гэтай рамкі. Які б добра, але гэта Аказваецца, вы не можаце зрабіць гэта. Таму што, калі вы не спыталі Для гэтага блока памяці, гэта можа быць супадзеннем той гэта у цяперашні час выкарыстоўваецца некаторай іншай зменнай ў цэлым. Ўспомніце тыдзень або каля таго, калі мы заклалі з імёнаў Zamyla і Дэвин і Гейба ў памяці. Яны былі літаральна спіна да спіны да спіны. Такім чынам, мы не можам абавязкова давяраць, што б ні было тут даступная для мяне, каб выкарыстаць. Так, што яшчэ вы маглі б зрабіць? Ну, раз разумеючы вас патрэбен масіў памерам сем, вы маглі б проста стварыць масіў памерам сем затым выкарыстоўваць цыкл або час цыклу, скапіяваць яго ў новы масіў, і потым як-то проста пазбавіцца ад гэты масіў або проста адмовіцца ад яго выкарыстання. Але гэта не вельмі эфектыўна. Карацей кажучы, масівы не дазваляюць дынамічна змяняць памер. Такім чынам, з аднаго боку, вы атрымліваеце адвольнага доступу, што дзіўна. Таму што гэта дазваляе нам рабіць тое, як падзяляй і ўладар, бінарны пошук, усе з якіх мы ў казалі аб на экране тут. Але вы малюеце сябе ў кут. Як толькі вы націснеце канец вашага масіва, што вам трэба зрабіць вельмі дарагая аперацыя або напісаць цэлую кучу кода каб зараз мець справу з гэтай праблемай. Так што, калі замест таго, каб у нас былі тое, што называецца спіс, або звязаны спіс, у прыватнасці ,? Што рабіць, калі замест таго, прастакутнікі спіна да спіны да спіны, у нас ёсць прастакутнікі, якія пакідаюць трохі трохі манеўру паміж імі? І хоць я намаляваў гэта малюнак або адаптаваць гэтую карцінку ад аднаго з тэкстаў тут, каб вярнуцца да спіна да спіны вельмі арганізавана, на самай справе, адзін з гэтых прастакутнікаў можа быць тут у памяці. Адзін з іх можа быць тут. Адзін з іх можа быць тут, тут і так далей. Але што, калі мы малявалі, у гэтым выпадку, стрэлкі што так ці інакш звязаць іх прастакутнікі разам? Сапраўды, мы бачылі тэхнічная ўвасабленне стрэлкай. Што мы выкарыстоўвалі ў апошні час дзён, што, пад капотам, з'яўляецца прадстаўніком стрэлкай? Паказальнік, ці не так? Так што, калі замест проста захоўваць нумары, як 9, 17, 22, 26, 34, што, калі мы не захоўваецца толькі нумар, але паказальнік побач з кожнай такой колькасці? Так што гэтак жа, як вы б нітка іголку праз цэлую кучу тканіны, так ці інакш звязваючы рэчы разам, гэтак жа можа мы з паказальнікамі, як увасобіўся стрэлкамі тут, выгляд ткаць разам гэтыя асобныя прастакутнікі шляхам эфектыўнага выкарыстання паказальніка Побач з кожным нумарам, які паказвае на некаторы наступнага колькасці, што паказвае на, у сваю чаргу, некаторыя наступны нумар? Такім чынам, іншымі словамі, тое, што калі мы на самай справе хацелі рэалізаваць нешта падобнае? Ну, на жаль, гэтыя прастакутнікі, Па крайняй меры, адзін з 9, 17, 22, ня і гэтак далей, яны больш не добрыя квадраты з асобных нумароў. Дно, прастакутнік Ніжэй за 9, напрыклад, ўяўляе, што павінна быць паказальнікам, 32 біта. Зараз, я яшчэ не ў курсе любога тыпу дадзеных у С, што дае не толькі Int але паказальнік ў цэлым. Так у чым жа рашэнне, калі мы хочам каб вынаходзіць уласны адказ на гэтае? Так? АЎДЫТОРЫЯ: [неразборліва] David J. малая: Што гэта? АЎДЫТОРЫЯ: Новая структура. David J. малая: Так, так чаму ня мы ствараем новую структуру, або ў С, структуры? Мы бачылі структур і раней, калі коратка, дзе мы мелі справу са студэнцкай структуры як гэта, хто меў імя і дом. У Pset 3 прарыў вы выкарыстоўвалі цэлы куча structs-- GRect і GOvals , Што Стэнфард стварыў у Кластар інфармацыя разам. Так што, калі мы возьмем гэтую ж ідэю ключавыя словы "аб'яваў тыпаў" і "структурай," а затым некаторыя студэнт-канкрэтныя рэчы, і развівацца гэта ў наступным: ЬурейеЕ структуры node-- і вузел толькі вельмі агульнае інфарматыка Тэрмін-то ў структуры дадзеных, Кантэйнер ў структуры дадзеных. Вузел я сцвярджаю, будзе мець Int N, вельмі просты ,, а затым яшчэ трохі загадкава, гэта другая лінія, структура вузла * наступны. Але ў менш тэхнічных тэрмінаў, што гэта за другая лінія кода ў фігурных дужках? Так? АЎДЫТОРЫЯ: [неразборліва] David J. малая: паказальнік на іншы вузел. Так па агульным прызнанні, сінтаксіс трохі загадкавым. Але калі вы чытаеце гэта літаральна, Наступны гэтае імя зменнай. Што такое тып дадзеных? Гэта крыху шматслоўны на гэты раз, але гэта тып структура вузла *. Кожны раз, калі мы бачылі нешта зорку, што азначае, што гэта паказальнік на гэтага тыпу дадзеных. Так што ў наступны, па-відаць паказальнік ў структуры вузла. Цяпер, што гэта структура вузла? Ну, заўважылі вы бачыце тых, тыя ж словы ў правым верхнім куце. І на самай справе, вы таксама бачыце слова "Вузел" сюды ў левым ніжнім куце. І гэта на самай справе проста зручнасць. Звярніце ўвагу, што ў нашым вызначэнні студэнцкай ёсць слова "студэнт" толькі адзін раз. І гэта таму, што студэнт аб'ект не быў самоссылающиеся. Там няма нічога ўнутры студэнта што трэба, каб паказаць на іншага студэнта, persay. Гэта было б свайго роду дзіўна ў рэальным свеце. Але з вузлом ў звязаны Спіс, мы робім хочаце вузел быць спасылачныя да падобнага аб'екта. І так заўважыць змена тут не толькі тое, што ўнутры фігурных дужак. Але мы дадаем слова «вузел» уверсе, а таксама дадаўшы яго на дно замест "студэнта". І гэта толькі тэхнічная дэталь такім чынам, што, зноў жа, ваша структура дадзеных, можа быць самоссылающиеся, так што Вузел можа паказваць на іншы такі вузел. Дык што ж гэта, у канчатковым рахунку будзе азначаць для нас? Ну, адзін, гэты матэрыял ўнутры гэта змест нашага вузла. Гэтая рэч тут, уверсе справа, гэта проста так што, зноў жа, мы можам звярнуцца да сябе. А потым знешні матэрыял, нават пры тым, што вузел з'яўляецца новы тэрмін, магчыма, гэта ўсё яшчэ жа, як студэнт і што быў пад капотам у SPL. Так што, калі мы зараз хацелі пачаць рэалізацыі гэтага звязаны спіс, як мы маглі б перавесці как то так, каб кадаваць? Ну, давайце проста паглядзім, Прыкладам праграмы, якія фактычна выкарыстоўвае звязаны спіс. Сярод сённяшніх кода размеркавання з'яўляецца праграма пад назвай Спіс нулявы. І калі я запускаю гэта я стварыў супер просты графічны інтэрфейс, графічны інтэрфейс карыстальніка, але гэта сапраўды проста PRINTF. І зараз я даў сабе некалькі меню options-- Выдаліць, Уставіць, Пошук, і Traverse. І Quit. Такія толькі агульныя аперацыі па Структура дадзеных вядомыя як спіс спасылак. Зараз, Выдаліць збіраецца выдаліць нумар з спісу. Устаўце збіраецца дадаць лік у спіс. Пошук будзе выглядаць лікі ў спісе. І траверс толькі мудрагелісты спосаб сказаць, хадзіць па спісе, раздрукаваць яго, але гэта так. Не змяняйце яго ў любым выпадку. Так давайце паспрабуем гэта. Давайце пойдзем далей і ўвесці 2. А потым я збіраюся ўвядзіце нумар, кажуць 9. Enter. І цяпер мая праграма проста запраграмаваны сказаць, спіс зараз 9. Зараз, калі я пайду наперад і у Устаўце зноў, хай мне ісці наперад і памяншэння маштабу і ўвядзіце ў 17. Цяпер мой спіс 9, затым 17. Калі я ўставіць зноў, давайце прапусцім адзін. Замест 22, як за карціны мы ў глядзеў на тут, дазвольце мне перайсці наперад і ўставіць 26 наступная. Так што я збіраюся набраць 26. Гэты спіс, як я чакаю. Але цяпер, проста каб паглядзець, калі гэтага кода збіраецца быць гнуткім, дазвольце мне цяпер Тып 22, якая, па меншай меры канцэптуальна, калі мы Маючы гэта сартуюцца, якія сапраўды будзе іншая мэта прама зараз, павінны пайсці ў перыяд з 17 па 26. Так я трапіў Enter. На самай справе, што працуе. І вось цяпер дазвольце мне ўставіць нарэшце, за карціны, 34. Добра. Так што на дадзены дазвольце мне прадугледжваюць, што Выдаліць і Traverse і пошук зрабіць, На самай справе, працаваць. На самай справе, калі я запусціць пошук, давайце пошук па нумары 22, Enter. Было ўстаноўлена, 22. Так што тое, што гэта Праграма Спіс Нуль робіць. Але што на самай справе адбываецца на які рэалізуе гэта? Ну, спачатку я, магчыма, прыйдзецца, і на самай справе У мяне ёсць, файл з імем list0.h. І дзе-то там гэта лінія, ЬурейеЕ, структура вузла, то ў мяне ёсць фігурныя дужкі, Int N, і затым struct-- што было вызначэнне? Структура, вузел побач. Так што мы павінны зорку. Цяпер тэхнічна мы трапляем у звычка малюнак яго тут. Вы можаце ўбачыць падручнікі і онлайн спасылкі зрабіць гэта там. Гэта функцыянальна эквівалентныя. На самай справе, гэта крыху больш тыповым. Але я буду паслядоўны з чым мы зрабілі ў мінулы раз і зрабіць гэта. І тады, нарэшце, я збіраюся зрабіць гэта. Так у файле загалоўка дзе, у list0.h сёння гэта вызначэнне структуры, і, магчыма, некаторыя іншыя рэчы. Між тым у list0c ёсць будзе некалькі рэчаў. Але мы збіраемся проста пачаць і ня скончыць гэта. List0.h гэта файл я хачу ўключыць у маёй C файл. А потым у пэўны момант я прыйдзецца Int, галоўная, анулявання. А потым я збіраюся ёсць некаторыя да справы тут. Я таксама збіраюся мець Прататып, як пустэч, пошук, INT, н, чыя мэта ў жыцці шукаць элемента. А потым сюды я сцвярджаю ў сённяшняя код, несапраўднымі, пошук, Int, н, няма коскі, але адкрытыя фігурныя дужкі. А цяпер я хачу, каб так ці інакш шукаць для элемента ў гэтым спісе. Але мы не маем дастаткова інфармацыя на экране яшчэ. У мяне на самай справе не ўяўляў сам спіс. Так адзін з спосабаў мы маглі б рэалізаваць звязаны спіс у праграме будзе я накшталт хачу рабіць тое, як дэкларуюць звязана спіс тут. Для прастаты я збіраюся зрабіць гэтая глабальная, хоць у цэлым мы не павінны рабіць гэтага занадта шмат. Але гэта спросціць гэты прыклад. Таму я хачу заявіць звязаны спіс тут. Зараз, як я мог бы гэта зрабіць? Вось карціна звязанага спісу. І я сапраўды не вядома на дадзены момант хаў Я збіраюся ісці аб якія прадстаўляюць так шмат рэчаў, толькі з адным пераменная ў памяці. Але ўспомніце момант. Увесь гэты час у нас было радкі, якія затым паказаў, што масівы сімвалаў, якія мы затым паказалі, каб быць проста паказальнік на першы сімвал у масіў сімвалаў які нулём. Так па гэтай логіцы, і з гэтым фота выгляд пасеву вашыя думкі, на што яшчэ нам на самай справе пісаць у наш Код для прадстаўлення звязаны спіс? Колькі з гэтай інфармацыі нам трэба захапіць у C код, вы можаце сказаць? Так? АЎДЫТОРЫЯ: Нам патрэбен паказальнік на вузел. David J. малая: паказальнік на вузел. У прыватнасці, які вузел б ваша інстынкты б захоўваць паказальнік на? АЎДЫТОРЫЯ: Першы вузел. David J. малая: Так, верагодна, толькі першы. І звярніце ўвагу, першы вузел іншую форму. Гэта толькі палова памер структуры, таму што гэта сапраўды толькі паказальнік. Так што вы сапраўды можаце зрабіць, гэта аб'явіць звязаны спіс, каб мець тып вузла *. І давайце проста называць яго першым і ініцыялізаваць яго да нуля. Так нуль, зноў жа, ідзе у карціну тут. Мала таго, што выкарыстоўваецца ў якасці нуль, як спецыяльная Вяртаецца значэнне для таго, як GetString і Таноса, нуль таксама нулявая паказальнік, адсутнасць паказальніка, калі вы будзеце. Гэта проста азначае, нішто не згаданы тут. Цяпер першы, я мог бы назваў гэта нічога. Я мог бы назваць яго "спіс" або любую колькасць іншых рэчаў. Але я тэлефаную яго "першым", так што ён выбудоўваецца ў лінію з гэтай карціны. Гэтак жа, як струны можа быць прадстаўлена з адрасам яго першага байта, так можа звязаны спіс. І мы ўбачым іншыя дадзеныя структуры можна ўявіць толькі з адным паказальнікам, 32-разрадная стрэлка, паказваючы на першым вузле ў структуры. Але цяпер давайце прадбачыць праблему. Калі я толькі успомніўшы у маёй праграме адраснай з першага вузла, першы прастакутнік ў гэтай структуры дадзеных, што лепш быць справа аб Рэалізацыя астатніх маім спісе? Што ключавы дэталлю, што адбываецца забяспечыць гэта на самай справе працуе? І "на самай справе працуе" я значыць, гэтак жа, як радкі, дазваляе нам перайсці ад першага сімвала у імя Давина да другога, у трэціх, чацвёрты, да самага канца, як мы ведаем, калі мы знаходзімся ў канцы звязанага спісу, які выглядае наступным? Калі гэта нуль. І я ўяўляў гэты від як як інжынер-электрык моцы, з маленькім зазямлення сімвал, свайго роду. Але гэта проста азначае, нуль ў гэтым выпадку. Вы можаце намаляваць яго любую колькасць спосабаў, але гэты аўтар адбылося выкарыстоўваць гэты сімвал тут. Пакуль мы нанізваючы ўсе гэтыя вузлы разам, толькі успамінаючы, дзе Першы, да таго часу, як мы ставім спецыяльны сімвал на самы апошні вузел у спісе, і мы будзем выкарыстоўваць нуль, таму што гэта тое, што мы маем у распараджэнні, каб нас, гэты спіс будзе завершана. І нават калі б я толькі даць вам паказальнік першы элемент, вы, праграміст, безумоўна, можа атрымаць доступ да астатніх яго. Але давайце няхай вашыя розумы пабадзяцца трохі, калі яны не ўжо даволі wandered-- што будзе час працы знайшоўшы нічога ў гэтым спісе? Чорт вазьмі, гэта вялікая O н, што не дрэнна, справядлівасці дзеля. Але гэта з'яўляецца лінейным. Мы адмовіліся ад таго, што функцыя масіваў шляхам перамяшчэння больш да гэтай карціне дынамічна пераплятаюцца або звязаны вузлы? Мы адмовіліся ад выпадковага доступу. Масіў прыемна, таму што матэматычна ўсе з'яўляецца спіна да спіны да спіны да спіны. Нават пры тым, што гэтай карціне выглядае прыгожа, і нават хоць гэта выглядае як гэтых вузлоў прыгожа разнесеныя, у рэальнасці яны могуць быць дзе заўгодна. Ox1, Ox50, Ox123, Ox99, гэтыя вузлы могуць быць дзе заўгодна. Таму Таноса робіць вылучыць памяць з кучы, але ў любым месцы ў кучы. Вам не абавязкова ведаць, што гэта будзе спіна да спіны да спіны. І так гэтая карціна ў Рэальнасці не збіраецца быць гэтак значнай. Так ён збіраецца заняць крыху працаваць над рэалізацыяй гэтай функцыі. Так давайце рэалізуем пошук цяпер. І мы ўбачым роду разумны спосаб зрабіць гэта. Так што, калі я функцыя пошуку і Я даў зменнай, лік п шукаць, мне трэба ведаць, Новы сінтаксіс для пошуку ўнутры структуры, гэта паказаў на, каб знайсці н. Так давайце зробім гэта. Такім чынам, спачатку я пайду наперад і абвясціць вузел *. І я буду называць яго паказальнік, толькі па пагадненні. І я збіраюся, каб падрыхтаваць яго да першага. І зараз я магу гэта зрабіць У некалькімі спосабамі. Але я збіраюся прыняць агульны падыход. У той час як паказальнік ня роўны нуль, і гэта дапушчальны сінтаксіс. І гэта як раз азначае, выканайце наступныя дзеянні, так Пакуль вы не паказваючы ні перад чым. Што я хачу зрабіць? Калі паказальнік кропка п, дазвольце мне вярнуцца ў тым, што, equals-- роўна што? Якое значэнне я шукаю? Фактычная п, які быў прыняты ў. Дык вось яшчэ адна асаблівасць С і шматлікія мовы. Нават пры тым, што структуры называецца вузлом мае значэнне п, цалкам законнай таксама ёсць мясцовы аргумент або пераменная называецца н. Таму што нават мы, з чалавечыя вочы, можна вылучыць што гэта п-відаць адрозніваецца ад гэтага п. Паколькі сінтаксіс адрозніваецца. У вас ёсць кропка і паказальнік, у той час як гэты не мае нічога падобнага. Так што гэта ў парадку. Гэта нармальна, каб называць іх тыя ж самыя рэчы. Калі я вам знайсці гэта, я захоча зрабіць нешта як паведаміць, што мы знайшлі н. І мы пакінем гэта як каментаваць або псевдокод код. Астатняе, і вось цікавая частка, што я хачу рабіць, калі бягучы вузел які не ўтрымлівае п, што я клапачуся аб? Як мне дамагчыся наступнае? Калі мой палец на момант PTR, і гэта паказваючы на ​​тое, што Першы паказваючы на, як я магу паварушыць пальцам на наступны вузел у кодзе? Ну, што дробка мы збіраецца прытрымлівацца ў гэтым выпадку? АЎДЫТОРЫЯ: [неразборліва]. David J. малая: Так, так што ў наступны. Так што, калі я вярнуся ў мой Код тут, сапраўды, я збіраюся ісці наперад і сказаць, паказальнік, які гэта толькі часовае переменная-- гэта дзіўнае імя, PTR, але гэта проста як temp-- Я збіраюся ўсталяваць паказальнік роўна якой паказальніка is-- і зноў жа, гэта будзе невялікая дзіцячая калыска для moment-- кропкай наступнага. Іншымі словамі, я збіраюся прыняць мае палец, які, паказваючы на ​​гэтым вузле тут, і я збіраюся сказаць, вы ведаеце, што, зірніце на наступнае поле і перамясціць палец у там яно паказваючы на. І гэта будзе Паўтараю, паўтараць, паўтараць. Але калі робіць свой палец спыніць рабіць амаль нічога? Як толькі што радок кода удараў у? АЎДЫТОРЫЯ: [неразборліва] David J. малая: Калі кропка а паказальнік ня роўны нулю. У нейкі момант мой пальца будзе паказваючы на ​​нуль і я збіраюся рэалізаваць гэта канец гэтага спісу. Цяпер, гэта трохі хлусня для прастаты. Атрымліваецца, што нават пры тым, што мы толькі што даведаўся пра гэтую кропкавую натацыю для структур, паказальнік не структура. PTR ёсць што? Проста, каб быць больш nitpicky. Гэта паказальнік на вузел. Гэта не сам вузел. Калі ў мяне не было зоркай тут, паказальнік absolutely-- гэта вузел. Гэта як тыдня адзін Дэкларацыя зменнай, хоць слова «вузел» з'яўляецца новым. Але як толькі мы ўводзім зорка, то зараз гэта паказальнік на вузел. І, на жаль, вы не можаце выкарыстоўваць кропкавай натацыі для паказальніка. Вы павінны выкарыстоўваць стрэлку абазначэння, якія, дзіўна, Упершыню любы кавалак сінтаксісу выглядае інтуітыўна зразумелым. Гэта літаральна выглядае як страла. І так, што гэта добрая рэч. І тут літаральна выглядае, як страла. Так што я думаю, што гэта la-- я не думаю, што я больш-здзяйсненне здесь-- Я думаю, што гэта апошні новы кавалак сінтаксісу мы збіраемся, каб убачыць. І да шчасця, гэта сапраўды трохі больш інтуітыўным. Зараз, для тых з вас, хто магчыма, аддадуць перавагу па-старому, Вы ўсё яшчэ можаце выкарыстоўваць кропкавай натацыі. Але ў адпаведнасці з панядзелка Размова, мы спачатку павінны пайсці туды, ісці да таго, што рашэнні, а затым перайсці ў полі. Так што гэта таксама правільна. І, шчыра кажучы, гэта трохі больш педантычным. Ты літаральна кажучы, разыменовать ўказальнік і пайсці туды. Затым бярэм .n, поле называецца н. Але, шчыра кажучы, ніхто не хоча ўвесці або прачытаць гэта. І таму свет прыдумаў абазначэнне стрэлка, якая эквівалентна, ідэнтычныя, гэта проста сінтаксічны цукар. Так мудрагелісты спосаб сказаць гэта выглядае лепш, ці выглядае прасцей. Так што цяпер я збіраюся зрабіць яшчэ адну рэч. Я збіраюся сказаць "перапынак" Як толькі я выявілі, што гэта так, я не працягваць шукаць для яго. Але гэта сутнасць функцыі пошуку. Але гэта нашмат лягчэй, у канец, не хадзіць праз код. Гэта сапраўды фармальнае выкананне пошуку ў сённяшнім кодзе размеркавання. Адважуся сказаць, што ўстаўка ня асабліва цікава ісці праз візуальна, ні выдаліць, нават пры тым, што ў канцы дня яны зводзяцца да даволі простыя эўрыстыкі. Так давайце зробім гэта. Калі вы будзеце гумар мяне тут, я зрабіў прынесці кучу стрэсавых шароў. Я прынёс кучу лічбаў. І мы маглі б атрымаць толькі некалькі добраахвотнікаў прадстаўляць 9, 17, 20, 22, 29 і 34? Так па сутнасці ўсе хто тут сёння. Гэта быў адзін, два, тры, чатыры, пяць, шэсць чалавек. І я папрасіў go-- ўбачыць, няма адзін у спіну падымае свае рукі. ОК, раз, два, тры, чатыры, five-- дазвольце мне загрузіць balance-- шэсць. ОК, вы шэсць давай до. Мы патрэбныя іншыя людзі. Мы прынеслі дадатковыя шары стрэс. І калі б вы маглі, для толькі на імгненне, лінія самі да ўсяго любіце гэтую фатаграфію тут. Добра. Давайце паглядзім, як цябе завуць? АЎДЫТОРЫЯ: Андрэй. David J. малая: Андрэй, вы нумар 9. Прыемна пазнаёміцца. Трымай. АЎДЫТОРЫЯ: Джэн. David J. малая: Джэн. Дэвід. Нумар 17. Так? АЎДЫТОРЫЯ: Я Юля. David J. малая: Юлія, Дэвід. Колькасць 20. АЎДЫТОРЫЯ: Крысціян. David J. малая: Крысціян, Дэвід. Колькасць 22. І? АЎДЫТОРЫЯ: JP. David J. малая: JP. Колькасць 29. Так ісці наперад і атрымаць в-- Ой-ой. Ой-ой. У рэжыме чакання. 20. Хто-небудзь ёсць маркер? АЎДЫТОРЫЯ: У мяне ёсць шулеры. David J. малая: Вы атрымалі шулеры? Добра. І хто-небудзь ёсць лісток паперы? Захавайце лекцыю. Падыдзі. АЎДЫТОРЫЯ: У нас ёсць яго. David J. малая: Мы атрымалі яго? Добра, дзякуй. Тут мы ідзем. Ці быў гэты ад вас? Вы проста выратавалі дзень. Так 29. Добра. Я няправільна 29, але добра. Працягвай. Добра, я дам вам Ваш пяро назад на імгненне. Таму ў нас ёсць гэтыя людзі тут. Давайце адзін іншы. Гейб, ты хочаш гуляць Першы элемент тут? Мы маем патрэбу ў вас, каб паказаць на гэтых выдатных людзей. Так 9, 17, 20, 22, адсартуйце з 29, а затым 34. Хіба мы губляем каго? У мяне ёсць 34. Дзе did-- ОК, хто хоча быць 34? ОК, давай да, 34. Добра, гэта будзе варта кульмінацыя. Як цябе завуць? АЎДЫТОРЫЯ: Піцер. David J. малая: Піцер, давай до. Добра, так вось цэлая куча вузлоў. Кожны з вас, хлопцы, уяўляе адзін з гэтых прастакутнікаў. І Гейб, трохі дзіўны чалавек з, уяўляе першы. Такім чынам, яго паказальнік крыху менш на экране, чым усе астатнія. І ў гэтым выпадку, кожны з вашай левай рукі збіраецца альбо накіраваныя ўніз, тым самым прадстаўляючы нуль, так толькі адсутнасць паказальніка, ці гэта збіраецца быць паказваючы ў вузле побач з вамі. Так што цяпер, калі вы ўпрыгожваюць будзьце падобныя на малюнку тут, ісці наперад і кропка адзін на аднаго, з Gabe у прыватнасці, паказваючы на нумар 9 для прадстаўлення спісу. ОК, і лік 34, левая рука трэба проста паказваючы на ​​падлозе. ОК, так што гэта звязаны спіс. Так што гэта сцэнар пад пытаннем. І на самай справе, гэта прадстаўнік з аднаго класа задач што вы маглі б паспрабаваць вырашыць з кодам. Вы хочаце, каб у канчатковым рахунку ўставіць новы элемент у спіс. У гэтым выпадку, мы збіраемся паспрабуйце ўставіць лік 55. Але ёсць будзе розныя выпадкі разгледзець. І на самай справе, гэта будзе адзін з вялікай карціны ежы на дом тут, з'яўляецца, якія розныя выпадкі. Якія існуюць Ці ўмовы або філіялы, што ваша праграма можа быць? Ну, нумар, які вы спрабуеце устаўка, які мы зараз ведаем, 55, але калі вы не ведаеце, загадзя, я адважуся сказаць, трапляе ў па меншай меры трох магчымыя сітуацыі. Дзе можа новы элемент быць? АЎДЫТОРЫЯ: І канец або сярэдзіну. David J. малая: У канцы, у сярэдні, або ў пачатку. Так я сцвярджаю, што ёсць па меншай меры тры праблемы, якія мы павінны вырашыць. Давайце выбіраць, што, магчыма, магчыма найпросты адзін, дзе новы элемент належыць у пачатку. Так што я буду мець код даволі як шукаць, што я толькі што напісаў. І я буду мець PTR, якія Я ўяўляю пальцам, як звычайна. І памятайце, якое значэнне ж мы ініцыялізаваць паказальнік на? Такім чынам, мы ініцыялізаваць яго абнуліць першапачаткова. Але тады што ж мы робім, як толькі мы былі ў нашым функцыі пошуку? Пакладзем яго роўным першаму, што не азначае рабіць гэта. Калі я ўсталёўваю PTR роўную першай, што павінны мая рука сапраўды паказваючы на? Права. Так што, калі Гейб і я збіраемся быць роўныя значэння тут, мы павінны як кропкі, у лік 9. Так што гэта быў пачатак нашай гісторыі. А цяпер гэта проста прамы, нягледзячы на ​​тое, што сінтаксіс з'яўляецца новым. Канцэптуальна гэта толькі лінейны пошук. З'яўляецца 55 роўны 9? Дакладней, скажам менш за 9. Таму што я спрабую высветліць, дзе паставіць 55. Менш за 9, менш 17, менш чым 20, менш за 22, меней 29, менш 34, няма. Так што цяпер мы ў выпадку адзін з па меншай меры трох. Калі я хачу, каб ўставіць 55 над тут, што радкоў кода неабходнасці атрымаць выкананы? Як гэта карціну людзі павінны змяніць? Што мне рабіць з маёй левай рукой? Гэта павінна быць нулявым, першапачаткова, таму што я ў канцы спісу. А што павінна адбыцца, тут з Пятром, гэта было? Ён, відавочна, збіраецца паказваць на мяне. Так я сцвярджаю, што ёсць па меншай меры дзве лініі кода ў прыкладзе кода з сённяшняга дня што збіраецца ажыццявіць гэта Сцэнар дадання 55 у хвасце. І можа мяне хто-то-хоп і проста ўяўляюць 55? Добра, вы новы 55. Так што цяпер, калі наступная сцэнар прыходзіць, і мы хочам, каб ўставіць у пачынаючы або кіраўнік гэтага спісу? І тое, што ваша імя, нумар 55? АЎДЫТОРЫЯ: Джэк. David J. малая: Джэк? ОК, прыемна пазнаёміцца. Сардэчна запрашаем на борт. Так што цяпер мы збіраемся ўставіць, скажам, лік 5. Вось другі выпадак тры мы прыдумалі раней. Так што калі 5 належыць у пачатку, давайце паглядзім, як мы бачым, што з. Я ініцыялізаваць мой PTR паказальнік на нумар 9 зноў. І я зразумеў ,, о, 5 менш 9. Так выправіць гэтую карцінку для нас. Чые рукі, Гейба або Давіда или-- што нумар 9 ў назву? АЎДЫТОРЫЯ: Джэн. David J. малая: hands-- Джэн якія з нашых рук трэба змяніць? Такім чынам, Гейб паказвае на што цяпер? У мяне. Я новы вузел. Так што я проста выгляд хаду тут, каб паглядзець яго візуальна. А між тым, што я паказаць, што? Тым не менш, калі я паказваю. Дык вось яно што. Так што проста сапраўды адна радок кода выпраўлення гэта канкрэтнае пытанне, здавалася б. Добра, так што гэта добра. А можа хто б гэта месца для 5? Падымайцеся. Мы цябе ў наступны раз. Добра, так now-- і Як у баку, імёны Я не раблю прамога згадвання правы Зараз, před паказальнік, паказальнік папярэднік і новы паказальнік, гэта толькі імёны далі у прыкладзе кода да паказальнікаў або мае рукі, гэта збольшага якія паказваюць вакол. Як цябе завуць? АЎДЫТОРЫЯ: Крысціна. David J. малая: Крысціна. Сардэчна запрашаем на борт. Добра, так што давайце разгледзім зараз трохі больш раздражняе сцэнар, у выніку чаго я хачу, каб ўставіць нешта накшталт 26 у гэтым. 20? Што? Гэтыя are-- добрая рэч у нас ёсць гэтую ручку. Добра, 20. Калі хто-то можа атрымаць яшчэ адзін кавалак папера гатовая, толькі ў case-- усё ў парадку. О, цікава. Ну гэта прыклад лекцыйнага памылкі. Добра, такім чынам, што цябе клічуць? АЎДЫТОРЫЯ: Юлія. David J. малая: Юлія, вы можаце поп , І бабінец, што вы ніколі не былі там? ОК, гэта ніколі не адбывалася. Дзякуй. Так што мы хочам ўставіць Юлія ў гэты звязанага спісу. Яна з'яўляецца лік 20. І, вядома, яна збіраецца належаць на begin-- не паказваюць ні на што яшчэ. Так што ваша рука можа збольшага быць ўніз нуль або некаторы значэнне смецця. Давайце казаць кароткую гісторыю. Я паказваю на 5 на гэты раз. Тады я правяраю 9. Тады я правяраю 17. Тады я правяраю 22. І я разумею ,, ох, Юля павінен ісці да 22. Так што павінна адбыцца? Чые рукі трэба змяніць? Джулія, шахта, или-- як цябе клічуць? АЎДЫТОРЫЯ: Крысціян. David J. малая: хрысціянін ці? АЎДЫТОРЫЯ: Эндзі. David J. малая: Эндзі. Крысціян або Эндзі? Эндзі павінен паказаць на? Юлія. Добра. Так Эндзі, ты хочаш, каб паказаць на Джулію? Але пачакайце хвіліну. У гісторыі да гэтага часу, Я-то адзін адказвае, у тым сэнсе, што паказальнік з'яўляецца рэч, якая перасоўванне па спісе. Мы можам мець імя для Эндзі, але няма пераменная называецца Эндзі. Адзіны іншай зменнай ў нас ёсць, першы, хто прадстаўлены Гейба. Так што гэта на самай справе, чаму такім чынам Пакуль мы не мелі патрэбу ў гэтым. Але цяпер на экране ёсць яшчэ раз адзначыць, з před паказальніка. Такім чынам, дазвольце мне быць больш відавочным. Калі гэта паказальнік, я павінен быў лепш атрымаць крыху разумнейшыя аб маім ітэрацыі. Калі вы не супраць, што я збіраюся праз тут зноў, паказваючы тут, паказваючы тут. Але дазвольце мне ёсць před паказальнік, паказальнік папярэднік, гэта выгляд паказваючы на элемент я быў проста ў. Таму, калі я іду сюды, зараз Мая левая рука абнаўлення. Калі я іду тут мае левыя абнаўлення ўручную. І зараз у мяне ёсць не толькі паказальнік элемент, які ідзе пасля Джуліі, Я да гэтага часу ёсць паказальнік на Эндзі, элемент раней. Так у вас ёсць доступ, па сутнасці, паніровачных сухароў, калі хочаце, для ўсіх неабходных паказальнікаў. Так што, калі я, паказваючы на Эндзі і я таксама паказваючы на Крысціяна, чые рукі павінны зараз адзначыць у іншым месцы? Так Эндзі цяпер могуць паказаць на Джулію. Цяпер Юлія можа паказваць на хрысціяніна. Таму што яна можа скапіяваць мой паказальнік правай рукі. І, што эфектыўна ставіць вас назад у гэтым месцы тут. Такім чынам, у агульным, хоць гэта вядзе нас накшталт назаўжды на самай справе абнаўлення звязаны спіс, рэалізаваць што аперацыі адносна простыя. Гэта з аднаго, двух, трох радкоў кода, у канчатковым рахунку. Але абгорнутыя вакол тых, радкоў кода меркавана трохі логікі, якія эфектыўна задае пытанне, дзе мы знаходзімся? Няўжо мы ў самым пачатку, сярэдні, ці канец? Зараз, ёсць, вядома, некаторыя іншыя Аперацыі, якія мы маглі б рэалізаваць. І гэтыя фатаграфіі тут проста адлюстраваць тое, што мы толькі што зрабілі з людзьмі. А як наконт выдалення? Калі я хачу, напрыклад, выдаліць нумар 34 ці 55, Я мог бы мець такі ж код, але я буду мець патрэбу ў адзін ці два этапы. Таму што новага? Калі я выдалю каго ў канцы, як лікі 55, а затым 34, што таксама павінна змяніцца, як мне гэта зрабіць? Я павінен не evict-- як цябе клічуць? АЎДЫТОРЫЯ: Джэк. David J. малая: Джэк. Я павінен не толькі evict-- бясплатна Джэк, так літаральна назваць бясплатны Джэк, ці, па меншай меры, паказальнік там жа, але цяпер што неабходна змяніць з Пятром? Яго рука лепш пачаць ўніз. Таму што, як толькі я тэлефанаваць бясплатна на Джэк, калі яшчэ паказвае Пятра на Джэка і я таму трымаеце абыходзе спіс і доступ гэты паказальнік, вось калі наш стары сябар сегментацыя абвінаваціць сапраўды можа памерці. Таму што мы далі памяці назад да Джэка. Вы можаце застацца там няёмка на імгненне. Таму што ў нас усяго пару заключныя аперацыі разгледзець. Зняцце галаву спісу, або beginning-- і гэты сайт крыху раздражняе. Таму што мы павінны ведаць, што Гейб гэта свайго роду спецыяльнае ў гэтай праграме. Таму што на самой справе, у яго ёсць свая паказальнік. Ён не проста на якую спасылаюцца ,, як амаль усе астатнія тут. Таму, калі кіраўнік спісу выдаленыя, чые рукі павінны змяніць цяпер? Як цябе клічуць зноў? АЎДЫТОРЫЯ: Крысціна. David J. малая: Я жудасна на імёны, па-відаць. Так Крысціна і Гейб, чые рукі неабходна змяніць калі мы спрабуем выдаліць Крысціну, лік 5, ад карціны? Такім чынам, давайце зробім Гейб. Гейб збіраецца паказаць, як мяркуецца, у доме нумар 9. Але што наступны павінен адбыцца? АЎДЫТОРЫЯ: Крысціна павінна быць пустым [неразборліва]. David J. малая: Добра, мы павінны, верагодна, make-- я пачуў "нулявы" дзе. АЎДЫТОРЫЯ: Null і вызваліць яе. David J. малая: Null што? АЎДЫТОРЫЯ: Null і вызваліць яе. David J. малая: Null і вызваліць яе. Так што гэта вельмі лёгка. І гэта выдатна, што ты зараз роду стаяць там, не належаць. Таму што вы былі аддзелены ад спісу. Вы эфектыўна было сіротамі з спісу. І такім чынам, мы лепш патэлефанаваць бясплатна зараз на Крысцін, каб даць гэтую памяць таму. У адваротным выпадку кожны раз, калі мы выдаліць вузел з спісу мы маглі б рабіць спіс карацей, але на самой справе не памяншаецца памер у памяці. І таму, калі мы працягваем дадаваць і дадаўшы, даданне элементаў у спісе, мой кампутар становіцца менш эфектыўным і ўсё павольней і павольней, таму што я бягу з памяці, нават калі я на самой справе не выкарыстоўваючы байт Крысціны памяці больш. Так, у канцы ёсць і іншыя сцэнары, з course-- выдалення ў сярэдняй, выдаленні у канцы, як мы бачылі. Але тым цікавей Цяпер задача ў будзе разглядаць менавіта што час працы з'яўляецца. Так што не толькі вы можаце захаваць ваш паперак, калі, Гейб, вы не пярэчыце даючы кожны мяч стрэс. Вялікі дзякуй нашаму звязанага спісу добраахвотнікаў тут, калі б вы маглі. [Апладысменты] David J. малая: Добра. Так пару аналітычная пытанні потым, калі я мог. Мы бачылі гэта абазначэнне раней, Big O і амега, верхнія мяжы і ніжнія мяжы час працы ад некаторага алгарытму. Такім чынам, давайце разгледзім толькі пару пытанняў. Адзін, і мы сказалі, гэта перш, чым жа працуе час пошуку Спіс па вялікай O? Што верхнюю мяжу працуючым Час пошуку звязаны спіс як ажыццяўляецца нашымі валанцёрамі тут? Гэта вялікі O н, лінейны. Таму што ў горшым выпадку, элемент, як 55, мы маглі б шукаць можа быць там, дзе Джэк быў, усю дарогу ў канцы. І, на жаль, у адрозненне ад масіва мы не можам атрымаць фантазіі на гэты раз. Нават пры тым, што ўсе нашы людзі былі адсартаваныя ад невялікіх элементаў, 5, усё, аж да большага элемента, 55, што, як правіла, добрая рэч. Але тое, што робіць гэта здагадка больш не дазваляюць нам рабіць? АЎДЫТОРЫЯ: [неразборліва] David J. малая: зноў сказаць? АЎДЫТОРЫЯ: Адвольны доступ. David J. малая: Адвольны доступ. І ў сваю чаргу гэта азначае, што мы можам не больш выкарыстоўваць слабы нулі, інтуіцыю, і відавочнасць выкарыстоўваючы двайковы пошук і падзяляй і ўладар. Таму што нават пры тым, што мы людзі маглі, відавочна, бачыць, што Эндзі або хрысціянін былі прыкладна ў сярэдзіне спісу, вядома толькі, што, як кампутар шляхам зняцця верхняга пласта спіс з самага пачатку. Такім чынам, мы адмовіліся, што адвольны доступ. Настолькі вялікі O п цяпер гэта верхняя мяжа нашага часу пошуку. Як наконт амега нашага пошуку? Што ніжняя мяжа па пошуку на працягу некаторага ліку ў гэтым спісе? АЎДЫТОРЫЯ: [неразборліва] David J. малая: зноў сказаць? АЎДЫТОРЫЯ: Адзін. David J. малая: Адзін. Так пастаянная часу. У лепшым выпадку, Крысціна На самай справе ў пачатку спісу. І мы шукаем лік 5, так што мы знайшлі яе. Дык няма нічога складанага. Але ў яе ёсць, каб быць у пачатак спісу ў гэтым выпадку. Што пра што-то як Выдаліць? Што рабіць, калі вы хочаце выдаліць элемент? Што верхняя мяжа і ніжняя мяжа на выдаленні чаго ад звязаны пералічыць? АЎДЫТОРЫЯ: [неразборліва] David J. малая: зноў сказаць? АЎДЫТОРЫЯ: н. David J. малая: п сапраўды верхняя мяжа. Таму што ў горшым выпадку мы стараемся выдаліць Джэк, як мы толькі што зрабілі. Ён усю дарогу ў канцы. Прымае ад нас назаўсёды, ці п крокаў, каб знайсці яго. Дык вось верхняя мяжа. Гэта лінейная, упэўнены. І ў лепшым выпадку час працы, або ніжнія мяжы ў лепшым выпадку будзе сталая часу. Таму што, можа быць, мы спрабуем выдаліць Крысцін, і мы проста павезці яна ў пачатку. Цяпер пачакайце хвіліну. Гейб таксама ў пачатку, і мы таксама павінны былі абнавіць Гейб. Так што не было яшчэ адзін этап. Так гэта сапраўды пастаяннай Час, у лепшым выпадку, выдаліць найменшы элемент? Гэта, нягледзячы на ​​тое, што можа быць два, тры ці нават 100 радкоў кода, калі гэта тое ж самае колькасць лініі, не ў некаторай завесы, і не залежыць ад памеру са спісу, абсалютна. Выдаленне элемента ў пачатак спісу, нават калі мы маем справу з Гейб, яшчэ пастаянная часу. Так гэта здаецца масіўны крок назад. І тое, што гэта пустая трата часу калі, у тыдзень адзін і тыдня нуля, мы павінны былі не толькі Код псевдокод але фактычны код рэалізаваць тое, што гэта часопіс база н, або ўвайдзіце, хутчэй, з п, база 2, з пункту гледжання яго часу працы. Дык чаму, чорт вазьмі, мы хацелі б пачаць выкарыстоўваючы нешта накшталт звязанага спісу? Так. АЎДЫТОРЫЯ: Такім чынам, вы можаце дадаць элементы ў масіў. David J. малая: Такім чынам, вы можаце дадаваць элементы ў масіў. І гэта таксама з'яўляецца тэматычным. І мы будзем працягваць бачыць гэта, гэта кампраміс, значна як мы бачылі Кампраміс з сартавання зліццём. Мы маглі б рэальна паскорыць пошук або сартавання, а, калі мы трацім трохі больш месца і мець дадатковы кавалак памяці або масіў для сартавання зліццём. Але мы праводзім больш прастору, але мы эканомім час. У гэтым выпадку, мы адмовіўшыся ад часу, але мы забеспячэнне гнуткасці, Дынамізм, калі хочаце, якія, магчыма, станоўчая рыса. Мы таксама праводзіць прастору. У якім сэнсе звязаны пералічыць даражэй з пункту гледжання прасторы, чым масіў? Дзе дадатковае прастору прыходзяць? Так? АЎДЫТОРЫЯ: [неразборліва] паказальнік. David J. малая: Так, мы таксама ёсць паказальнік. Так што гэта minorly раздражняе у тым, што больш не з'яўляюся Я захоўвання проста Int для прадстаўлення Int. Я запамінання Int і а паказальнік, які таксама 32 біт. Так што я літаральна падвойваючы ўдзел аб'ём прасторы. Дык вось кампраміс, але вось у выпадку міжнар. Выкажам здагадку, што вы не захоўвання Int, але выкажам здагадку, што кожны з гэтых прастакутнікаў або кожны з гэтых людзей прадстаўляў слова, ангельскае слова, якое можа ўтрымліваць пяць знакаў, 10 сімвалы, можа быць, нават больш. Тады дадаўшы ўсяго 32 больш бітаў можа быць менш буйной здзелкі. Што рабіць, калі кожны са студэнтаў у дэманстрацыі былі літаральна студэнцкія Структуры, якія маюць імёны і дамоў і, магчыма, тэлефонаў і Twitter ручкі і таму падобнае. Так усё поля мы пачалі гаворым пра другі дзень, значна менш буйной здзелкі, як нашы вузлы становяцца больш цікавымі і вялікі, каб правесці, а, дадатковы паказальнік проста звязаць іх разам. Але на самой справе, гэта кампраміс. І на самай справе, код складаней, як вы будзеце гл па бегла што канкрэтны прыклад. Але што, калі было некаторыя Святой Грааль тут. Што рабіць, калі мы не зробім крок таму, але масіўны крок наперад і ўкараніць дадзеныя Структура, праз які мы можа знайсці элементы, такія як Джэк або Christine або любыя іншыя элементы у гэтым масіве ў сапраўды пастаяннага часу? Пошук сталая. Выдаліць сталая. Устаўка сталая. Усе гэтыя аперацыі з'яўляюцца сталымі. Гэта было б нашым Святога Грааля. І што гэта, дзе мы падбяруць наступны раз. Ўбачымся.