Выступоўца 1: Усё ў парадку, так што мы вярнуліся. Сардэчна запрашаем у CS50. Гэта канец тыдня сем. Таму нагадаем, што ў мінулы раз, мы пачалі гледзячы на ​​некалькі больш складана структур дадзеных. Так як да гэтага часу, усё, што мы былі сапраўды У нашым распараджэнні было гэтага, масіў. Але перш чым адкінуць масіў як ня усё, што цікава, што гэта сапраўды так на самай справе, тое, што некаторыя з Плюсы гэтага простага дадзеных структуры да гэтага часу? Якое гэта добра? Да гэтага часу, як мы бачылі? Што ў цябе? Нічога. Студэнт: [неразборліва]. Выступоўца 1: Што гэта? Студэнт: [неразборліва]. Выступоўца 1: фіксаваны памер. Такім чынам, чаму фіксаваны памер добры, хоць? Студэнт: [неразборліва]. Выступоўца 1: Добра, так што гэта эфектыўна ў тое сэнсе, што вы можаце вылучыць Фіксаваная сума ў прасторы, якая, мы спадзяемся, Менавіта столькі прасторы, як вы хочаце. Так што можа быць абсалютна плюс. Што яшчэ па адным баку масіва? Да? Студэнт: [неразборліва]. Выступоўца 1: Усё - Прабачце? Студэнт: [неразборліва]. Выступоўца 1: Усе скрынкі ў памяці або побач адзін з адным. І гэта карысна - чаму? Цалкам дакладна. Але як мы можам выкарыстоўваць гэта праўда? Студэнт: [неразборліва]. Выступоўца 1: Сапраўды, мы можам адсочваць , Дзе ўсё проста, ведаючы, адзін адрас, а менавіта, адрасы Першы байт, што блок памяці. Ці ў выпадку радкі, адрас першага знак у гэтай радку. А адтуль, мы можам знайсці канца радка. Мы можам знайсці другі элемент, трэці элемент, і так далей. І такім мудрагелістым спосабам апісання, што асаблівасць у тым, што масівы даюць нам адвольным доступам. Проста з дапамогай квадратных дужак абазначэння і нумары, вы можаце перайсці да канкрэтнага элемента ў масіве за пастаянны час, Big O аднаго, так бы мовіць. Але ёсць некаторыя мінусы. Што масіў не рабіць вельмі лёгка? Што гэта не вельмі добра? Студэнт: [неразборліва]. Выступоўца 1: Што гэта? Студэнт: [неразборліва]. Выступоўца 1: Пашырэнне ў памерах. Такім чынам, недахопы масіва дакладна адваротнае таму, што расквітацца ёсць. Таму адным з недахопаў з'яўляецца што гэта фіксаваны памер. Такім чынам, вы не можаце рэальна выгадаваць яго. Вы можаце пераразмеркаваць большы кавалак памяці, а затым перамесціце стары элементы у новы масіў. , А затым вызваліць старога масіва, для Напрыклад, пры выкарыстанні Таноса або аналагічнага Функцыя называецца Realloc, якая пераразмяркоўвае памяць. Realloc, як у бок, спрабуе даць вам памяці, што гэта побач з масівам што вы ўжо маеце. Але гэта можа перамяшчаць прадметы вакол у цэлым. Але ў агульным, што дорага, ці не так? Таму што, калі ў вас ёсць кавалак памяці такога памеру, але вы сапраўды хочаце адзін такога памеру, і вы хочаце захаваць арыгінальныя элементы, у вас ёсць прыкладна лінейны працэс капіявання час што павінна адбыцца ад старога масіва на новы. А рэальнасць такая просяць аперацыйнай Сістэма зноў і зноў і зноў на вялікія кавалкі памяці можа пачацца каштаваць вам некаторы час, а таксама. Так што гэта як дабраславеньне і праклён у замаскіраваць той факт, што гэтыя масівы маюць фіксаваны памер. Але калі ўвесці замест нешта як гэта, якое мы назвалі звязанага спіс, мы атрымліваем некалькі плюсы і некалькі недахопаў і тут. Так звязаны спіс проста дадзеныя структура, якая складаецца з структур C у гэтым выпадку, калі структура, нагадаем, з'яўляецца проста кантэйнер для аднаго або больш канкрэтных тыпы зменных. У гэтым выпадку, што ж тыпы дадзеных Відаць, усярэдзіне структуры, які Апошні раз мы называецца вузлом? Кожны з гэтых прастакутнікаў вузла. І кожны з меншых прастакутнікаў Унутры гэта тып дадзеных. Якія ж тады мы казалі яны былі ў панядзелак? Да? Студэнт: [неразборліва]. Выступоўца 1: зменныя і паказальнік, або дакладней, цэлае для N, і паказальнік на дне. Абодва гэтыя, аказваецца, 32 біта, па крайняй меры на кампутары, як гэта CS50 Appliance, і таму яны звяртаецца аднолькава ў памеры. Так што з дапамогай паказальніка хоць для па-відаць? Навошта дадаваць гэтую стрэлку цяпер, калі масівы, былі так добра і чыста і проста? Што робіце для паказальніка намі у кожным з гэтых вузлоў? Студэнт: [неразборліва]. Выступоўца 1: Цалкам дакладна. Гэта кажа вам, дзе далей ідзе. Так што я, вядома, выкарыстоўваць аналогію выкарыстаннем патоку да выгляду нітка гэтыя вузлы разам. І гэта менавіта тое, што мы робім з паказальнікаў, паколькі кожны з гэтых участкаў памяці можа ці не можа быць сумежныя, спіна да спіны да спіны ўнутры аператыўнай памяці, таму што кожны раз, калі вы патэлефануеце Malloc кажуць: дай мне дастаткова байтаў для новага вузла, ён можа быць тут, ці ён можа быць тут. Гэта магло б быць тут. Гэта магло б быць тут. Вы проста не ведаю. Але з дапамогай паказальнікаў у адрасах гэтыя вузлы, вы можаце пашыць іх разам такім чынам, што візуальна выглядае як спіс, нават калі гэтыя рэчы ўсе распаўсюджаныя на працягу ўсяго аднаго або Вашы два ці вашы чатыры гігабайта аператыўнай памяці ўнутры вашага ўласнага кампутара. Такім чынам, недахоп, то, Звязаны спіс ёсць што? Што такое цана, што мы мабыць плаціць? Студэнт: [неразборліва]. Выступоўца 1: Больш месца, ці не так? Мы, у дадзеным выпадку, падвоіў суму прасторы, таму што мы прайшлі з 32 біт для кожнага вузла, для кожнага Інтэлект, так што зараз 64 біта, таму што мы павінны трымаць вакол паказальніка, а таксама. Вы атрымліваеце больш эфектыўнасці, калі вашай структуры больш, чым гэтая простая рэч. Калі ў вас сапраўды ёсць унутры студэнта з якіх уяўляе сабой пару радкоў для імя і дом, можа быць, нумар пасведчання асобы, магчыма, некаторыя іншыя вобласці ў цэлым. Так што калі ў вас ёсць дастаткова вялікая структура, то, магчыма, кошт паказальнік Не такое ўжо вялікая справа. Гэта крыху з кута ў гэтым выпадку мы захоўваем такія простыя прымітыўныя ўнутр звязанага спісу. Але сутнасць тая ж. Вы вызначана марнаваць больш памяці, але вы атрымліваеце гнуткасць. Таму што цяпер, калі я хачу дадаць элемент У пачатку гэтага спісу, Я павінен вылучыць новы вузел. І я павінен проста абнавіць гэтыя Стрэлкі-то проста перасоўванне некаторыя паказальнікі вакол. Калі я хачу, каб ўставіць нешта ў сярэдзіне спісу, я не прыйдзецца штурхаць у бок усё, што мы зрабілі ў тыдняў мінулае з нашым добраахвотнікам, якія прадстаўлена масівам. Я магу проста вылучыць новы вузел і Затым проста паказаць стрэлкамі на розных напрамках, паколькі яна не павінны заставацца ў фактычным памяці сапраўдных лініі, як я намаляваў яе тут на экране. А потым, нарэшце, калі вы хочаце ўставіць то ў канцы спісу, гэта яшчэ прасцей. Гэта свайго роду адвольныя абазначэння, але ў 34 паказальнікаў, зрабіць здагадку. Што такое значэнне яго паказальніка найбольш верагодна, звяртаецца накшталт як старыя школе ёсць антэна? Студэнт: [неразборліва]. Выступоўца 1: Гэта, верагодна, нулявым. І на самай справе, што з'яўляецца адным аўтара ўяўленне нулявы. І гэта нуль, таму што вы абсалютна трэба ведаць, дзе да канца звязанага спіс, каб вы працягваеце пасля і пасля і пасля гэтых стрэлак некаторым смеццем значэння. Так нулявых не будзе азначаць, што няма ніякай больш вузлоў справа ад колькасці 34, ў гэтым выпадку. Таму мы лічым, што мы можам рэалізаваць гэты вузел у кодзе. І мы бачылі такую сінтаксісу раней. Typedef проста вызначае новы тып для нас, дае нам як сінонім Радок была для сімвал *. У гэтым выпадку, ён збіраецца даць нам скарочаны запіс, так што структура вузла Замест гэтага можна проста быць запісана ў выглядзе вузел, які з'яўляецца нашмат больш чыстай. Гэта значна менш шматслоўным. Усярэдзіне вузла відаць цэлалікавай называецца п, а затым структуры вузла * што азначае менавіта тое, што мы хацелі Стрэлкі на ўвазе, паказальнік на іншы вузел сапраўды такі жа тып дадзеных. І я прапаную, каб мы маглі рэалізаваць Функцыя пошуку, як гэта, якое ў першы погляд можа здацца, трохі складаным. Але давайце паглядзім яго ў кантэксце. Дазвольце мне перайсці да прыбора тут. Дазвольце мне адкрыць файл з імем Спіс нуля кропка ч. І што толькі змяшчае вызначэнне мы толькі што бачылі хвіліну назад для гэтых дадзеных тып завецца вузлом. Таму мы ўвялі, што ў файл кропка ч. І, як у баку, хоць гэта праграма, якую вы збіраецеся, каб убачыць гэта не ўсё, што комплекс, гэта сапраўды Канвенцыі пры напісанні праграмы пакласці рэчы, як тыпы дадзеных, цягнуць Канстанты часам, ўнутры вашага загаловак файла, а не абавязкова ў З вашага файла, вядома ж, калі ваш праграм атрымаць больш і больш, так што Вы ведаеце, дзе шукаць, як для дакументацыі ў некаторых выпадках ці для асновы, як гэта, вызначэнне некаторага тыпу. Калі б я цяпер адкрыць спіс нуля кропка C, заўважыць некалькі рэчаў. Яна ўключае ў сябе некалькі файлаў загалоўка, большасць якога мы бачылі раней. Яна ўключае ў сябе свой уласны файл загалоўка. І, як у баку, чаму гэта падвойная каціроўкі тут, у адрозненне ад кута кранштэйны на лініі, якая Я выдзеліў там? Студэнт: [неразборліва]. Выступоўца 1: Так, так што гэта лакальны файл. Так што, калі гэта лакальны файл ўласнай тут на лініі 15, напрыклад, вы карыстаецеся падвойныя двукоссі замест ў вуглавыя дужкі. Зараз гэта збольшага цікава. Звярніце ўвагу, што я абвясціў глабальную зменнай у гэтай праграме ў радку 18 называецца першай, ідэя ў тым, што гэта будзе паказальнік на першы вузел у маім звязаны спіс, а я ініцыялізаваць яго да нуля, таму, што я не вылучаецца якіх-небудзь фактычных вузлы толькі пакуль. Так што гэта ўяўляе, графічна, тое, што мы ўбачыў хвіліну таму на малюнку як што паказальнік на Далёкім з левага боку. Так што цяпер, што паказальнік не мае стрэлкі. Замест гэтага ён проста нулявы. Але ён ўяўляе, які будзе адрас першага фактычнага вузла ў гэтым спісе. Так я рэалізаваў гэта глабальная таму што, як вы ўбачыце, усё гэта Праграма робіць у жыцці, гэта рэалізаваць звязаны спіс для мяне. Цяпер у мяне ёсць некалькі прататыпаў тут. Я вырашыў рэалізаваць функцыі, такія як дзялок, устаўкі, пошуку і абыходу - Апошні проста быць шпацыр праз Спіс, раздрукаваць яе элементаў. А цяпер вось мой асноўнай праграме. І мы не будзем марнаваць занадта шмат часу на гэта, так як гэта з'яўляецца свайго роду, мы спадзяемся, старая капялюш да гэтага часу. Я збіраюся зрабіць наступнае, у той час як карыстальнік ўзаемадзейнічае. Так што, я збіраюся друкаваць з гэтага меню. І я адфарматаваць яго ў якасці чыста, як я мог. Калі карыстальнік ўводзіць у адным, гэта значыць яны хочуць, каб выдаліць што-небудзь. Калі карыстальнік ўвядзе ў двух, гэта азначае, што яны хочуць, каб ўставіць нешта. І гэтак далей. Я збіраюся потым падкажуць Тады для каманды. А потым я збіраюся выкарыстоўваць GetInt. Так што гэта сапраўды проста menuing інтэрфейс, дзе вы проста павінны ўвесці лік адлюстраванне аднаго з гэтых каманд. І зараз у мяне ёсць добрая чыстая перамыкач заяву, што збіраецца ўключыць любы карыстальнік ўвялі цалі І калі яны набралі адно, я буду выкліку выдалення і ламацца. Калі яны ўвялі два, я буду патэлефануеце ўставіць і ламацца. А цяпер звярніце ўвагу я змясціў кожнага з іх на той жа лініі. Гэта ўсяго толькі стылістычнае рашэнне. Звычайна мы бачылі нешта як гэта. Але я проста вырашыў, шчыра кажучы, мая праграма выглядаў больш для чытання, так гэта было толькі чатыры выпадкі проста пералічыць гэта так. Цалкам законнае выкарыстанне стылю. І я буду рабіць гэта так доўга, як Карыстальнік не набрала нуля, што я вырашана будзе азначаць, што яны жадаюць кінуць паліць. Так што цяпер заўважаю, што я будзем рабіць тут. Я збіраюся вызваліць спісе па-відаць. Але пра гэта праз хвіліну. Давайце спачатку запусціць гэтую праграму. Такім чынам, дазвольце мне зрабіць большы тэрмінал вокны, кропка слэш спіс 0. Я збіраюся ісці наперад і ўстаўляйце іх набраўшы два, як лік 50, а цяпер Вы ўбачыце спіс зараз на 50. І мой тэкст, проста пракручваецца няшмат. Так што цяпер Звярніце ўвагу на спіс ўтрымлівае лік 50. Давайце яшчэ устаўкай, узяўшы два. Давайце увядзіце нумар, як адзін. Спіс з'яўляецца адной, а затым 50. Так што гэта проста тэкставае ўяўленне спісу. І давайце уставім яшчэ адзін нумар, як нумар 42, які з надзеяй будзе ў канчатковым выніку ў сярэдзіне, таму што гэтай праграмы, у прыватнасці, сартуе яго элементы, як ён устаўляе іх. Так што ў нас гэта ёсць. Супер просто праграму, якая можа Абсалютна выкарыстоўвалі мноства, але я , Здараецца, выкарыстоўваюць звязаны спіс менавіта так я магу дынамічна павялічваюцца і памяншаюцца яго. Такім чынам, давайце зірнем на пошукі, калі я запусціць каманду тры, я хачу пошуку , Скажам, лікі 43. І нічога не было знойдзена па-відаць, таму што я не вярнуўся без адказу. Такім чынам, давайце зробім гэта зноў. Пошук. Давайце шукаць для 50, ці, хутчэй, пошук для 42, у якога ёсць добрая амаль няўлоўная сэнс. І я знайшоў сэнс жыцця там. Лік 42, калі вы не ведаеце, спасылкі Пошук у Інтэрнэце. Добра. Так, што гэтая праграма для мяне зрабіў? Гэта проста дазволіў мне ўставіць такім чынам, далёка і пошук элементаў. Давай наперад, то, каб функцыі, мы зірнуў на у панядзелак, як цвялілкі. Так што гэтая функцыя, я сцвярджаю, шукае элемента ў спісе па першым адна, прапаноўваючы карыстачу з наступным выклікам GetInt, каб атрымаць фактычныя дзесятковага што вы хочаце знайсці. Потым заўважыў гэтага. Я збіраюся стварыць часовую зменную У лініі 188 называецца паказальнікам - PTR - мог бы назваць яе, як заўгодна. І гэта паказальнік на вузле бо Я сказаў вузла * там. І я ініцыялізацыі роўным першы, так што я эфектыўна маё пальца, так бы мовіць, на самай Першы элемент спісу. Так што, калі мая правая рука тут PTR Я паказваючы на ​​тое ж самае, што першы паказвае на. Так што цяпер яшчэ ў кодзе, што будзе далей - гэта агульная парадыгма пры пераборы па структуры, як звязаны спіс. Я збіраюся зрабіць наступнае ў той час як паказальнік ня роўны нулю Такім чынам, хоць мой палец не паказвае на некаторыя нулявым кошту, калі стрэлка паказальніка N роўна N. Мы заўважылі, што першыя N з'яўляецца тое, што карыстач уводзіць у GetInts называю тут. І стрэлка паказальніка N азначае, што? Ну, калі мы вернемся да карціны тут, ці ёсць у мяне пальцам, паказваючы на што першы вузел, які змяшчае дзевяць, стрэлкі па сутнасці азначае, што перайсці да вузла і захапіць значэнне ў кропцы N, У гэтым выпадку, поле дадзеных называецца н. Як у бок - і мы ўбачылі гэтую пару тыдняў таму, калі хто-то спытаў - гэты сінтаксіс з'яўляецца новай, але гэта не так даць нам сілы, якія мы ўжо не было. Што гэта за фраза эквівалентна выкарыстанню кропкавай натацыі і зорка пара тыдняў таму, калі мы вычышчаныя назад гэты пласт трохі заўчасна? Студэнт: [неразборліва]. Выступоўца 1: Сапраўды, гэта была зорка, і тады гэта была зорка кропкай N, з Тут дужкі, які выглядае, шчыра кажучы, я думаю, што шмат больш загадкавыя чытаць. Але паказальнік зоркі, як заўсёды, сродкі ідуць туды. І як толькі вы там, якія дадзеныя поля вы хочаце атрымаць доступ? Ну вы выкарыстоўваюць кропку доступу да поля структур дадзеных, і я спецыяльна хочуць н. Шчыра кажучы, я б сказаў, гэта проста цяжка чытаць. Гэта складаней ўспомніць, дзе зрабіць дужках ісці, зорка і ўсё такое. Такім чынам, свет прыняў некаторыя сінтаксічныя цукар, так бы мовіць. Проста сэксуальна спосаб сказаць, гэта эквівалентна, а таксама магчыма, больш інтуітыўным. Калі паказальнік сапраўды з'яўляецца паказальнікам, сродкаў стрэлкі абазначэння пайсці туды і знайсці поля ў гэтым выпадку называюцца N. Так што, калі я знаходжу гэта, заўважце, што я раблю. Я проста раздрукаваць, я выявіў, я адсоткаў, падлучэнне значэнне для гэтага Int. Я называю спаць на працягу адной секунды проста выгляд паўзы рэчы на ​​экране, каб даць карыстачу другі паглынаць што толькі што адбылося. І тады я парушу. У адваротным выпадку, што мне рабіць? Абнавіць паказальнік на роўных паказальніка стрэлкі побач. Так што проста каб быць ясным, гэта азначае пайсці там, з дапамогай маёй старой школы мелі наймення. Так што гэта проста азначае, ісці да таго, што Вы паказваеце на, які ў самым Першы выпадак я паказваючы на Структура з дзевяццю ў ім. Так што я пайшоў туды. І тады кропкавай натацыі азначае, атрымаць значэнне ў наступным. Але каштоўнасць, хоць ён малюецца як вузкія, проста нумар. Гэта адрас у лікавы. Так што гэта адзін радок кода, няхай гэта будзе напісана, як гэта, больш схаваным шляху, ці, як гэта, некалькі больш інтуітыўна зразумелым спосабам, проста азначае, паварушыць рукой ад першага вузла да наступнага, а затым наступны, а затым наступнай, і так далей. Такім чынам, мы не будзем спыняцца на іншых рэалізацый ўстаўляць і выдаляць і абыходу, першыя два з якія з'яўляюцца дастаткова складанай. І я думаю, што гэта даволі лёгка атрымаць страціў, калі робяць гэта ў вуснай форме. Але што мы можам зрабіць тут Паспрабуйце вызначыць, як Лепш рабіць гэта візуальна. Таму што я хацеў бы прапанаваць, што калі мы хочаце ўставіць элементы ў гэтай існуючы спіс, які складаецца з пяці элементаў - 9, 17, 22, 26 і 33 - Калі б я збіраўся ажыццявіць гэта ў код, мне трэба падумаць, як ісці пра гэта. І я хацеў бы прапанаваць крокі дзіцяці якой, у дадзеным выпадку я маю на ўвазе, якія магчымых сцэнарыяў, якія мы могуць паўстаць у цэлым? Пры рэалізацыі ўстаўкі для звязанага спісе, гэта толькі, здараецца, Пэўным прыкладам памер пяць. Ну, калі вы хочаце ўставіць лічбу, як, скажам, нумар адзін, і падтрыманне парадку сартавання, дзе , Відавочна, нумар адзін трэба ісці ў гэтым канкрэтным прыкладзе? Напрыклад, у пачатку. Але што цікава, ёсць тое, што Калі Вы хочаце ўставіць адну ў гэтую спіс, што трэба спецыяльны паказальнік абнавіць відавочна? Першая. Так што я б сказаў, што гэта першы выпадак што мы маглі б хацець разгледзець, сцэнар, які ўключае ўвядзенне, па пачатку спісу. Давайце абрываць, можа быць, так лёгка, ці нават просты выпадак, умоўна кажучы. Выкажам здагадку, я хачу, каб ўставіць 35 чысла ў парадку сартавання. Гэта, відавочна, належыць там. Так што, відавочна, паказальнік будзе павінны быць абноўлены ў гэтым сцэнары? 34 у паказальнік становіцца NOT NULL але адрас структуры які змяшчае нумар 35. Дык вось выпадак два. Так што ўжо, я накшталт квантавання колькі працы я павінен зрабіць тут. І, нарэшце, відавочны выпадак сярэдзіна Сапраўды, у сярэдзіне, калі я хачу ўстаўляць нешта накшталт кажуць 23, які ідзе паміж 23 і 26, але Зараз усё становіцца трохі больш ўдзельнічае, таму што паказальнікі павінны быць зменены? 22 Так, безумоўна, павінна быць зменена таму што ён не можа паказаць на 26 больш. Яму трэба, каб ён паказваў на новы вузел, Мне прыйдзецца вылучыць па тэлефоне Malloc ці некаторы эквівалент. Але потым я таксама трэба, каб новы вузел, 23 У гэтым выпадку, каб мець свой паказальнік паказваючы на ​​каго? 26. І там будзе Парадак аперацый тут. Таму што калі я зраблю гэта па-дурному і я Напрыклад пачатку ў пачатку спісе, і мая мэта, каб ўставіць 23. І я правяраў, яно належыць тут, каля дзевяці? Няма. Ці мае месца тут, побач з 17? Няма. Ці мае яна належыць тут побач з 22? Да. Цяпер, калі я дурны тут, і ня думаючы, што гэта да канца, я мог бы вылучыць мой новы вузел 23. Я мог бы абнавіць паказальнік з вузел, які называецца 22, паказваючы яго на новы вузел. І што тады мне давядзецца абнаўляць паказальнік на новы вузел, каб быць? Студэнт: [неразборліва]. Выступоўца 1: Цалкам дакладна. Паказваючы на ​​26. Але, чорт вазьмі, калі б я ўжо не абнаўляць Паказальнік 22, каб яна паказвала на гэтага хлопца, і зараз у мяне ёсць сіроты, астатнія спісу, так бы мовіць. Так што парадак аперацый тут будзе важна. Для гэтага я мог скрасці, скажам, шэсць добраахвотнікаў. І давайце паглядзім, калі мы не можам зрабіць гэтага візуальна замест кода-мудрым. І ў нас ёсць некаторыя выдатныя стрэсу шары для вас сёння. Добра, а як аб адным, двух, у Назад - у канцы там. тры, чатыры, вы абодва Хлопцы на канцы. І пяць, шэсць. Вядома. Пяць і шэсць. Добра, і мы прыедзем каб вы, хлопцы, у наступны раз. Добра, падымайся. Добра, раз ужо ты тут, па-першае, Вы хацелі б быць тым, няёмка Шкло ў Google тут? Добра, добра, шкло, Запіс відэа. Добра, вы добра ісці. Добра, так што калі вы, хлопцы, можаце прыехаць Тут, я падрыхтаваў загадзя некаторыя лічбы. Добра, ідзі сюды. А чаму б вам не пайсці крыху далей, што шлях. І паглядзім, як цябе завуць, Шкло з Google? Студэнт: Бэн. Выступоўца 1: Бэн? ОК, Бэн, ты будзеш першым, літаральна. Такім чынам, мы збіраемся адправіць вам ў канцы стадыі. Добра, і ваша імя? Студэнт: Джэйсан. Выступоўца 1: Джэйсан, OK вы будзеце быць нумарам дзевяць. Так што, калі вы хочаце прытрымлівацца Бэн такім чынам. Студэнт: Джыл. Выступоўца 1: Джыл, вы збіраецеся быць 17, які, калі б я зрабіў гэта больш разумна, я б пачалося на іншым канцы. Вы ісці па гэтым шляху. 22. А вы хто? Студэнт: Марыі. Выступоўца 1: Марыя, вы будзеце 22. А ваша імя? Студэнт: Крыс. Выступоўца 1: Крыс, вы будзеце 26. А потым, нарэшце. Студэнт: Дыяны. Выступоўца 1: Дыяна, вы будзеце 34. Такім чынам, вы ідзі сюды. Добра, настолькі дасканалы адсартаваны Замовіць ужо. І давайце ісці наперад і рабіць гэта так што мы можам на самай справе - Бэн, ты проста выгляд гледзячы з ў нікуды там. Такім чынам, давайце пойдзем далей і малююць гэтую ужываннем зброі, гэтак жа, як я быў, уласна, што адбываецца. Так што ісці наперад і даць сабе фут ці два паміж сабой. І ісці наперад і адзначыць з аднаго боку, хто б ты павінен быць накіраваны на на аснове гэтага. І калі вы проста паказаць нулявы прама ўніз да падлогі. Добра, так добра. Так што цяпер у нас ёсць звязаны спіс, і дазвольце мне прапаную, што я буду гуляць ролю PTR, так што я не буду турбавацца правядзенне гэтага вакол. А потым - нехта дурны Канвенцыі - Вы можаце называць гэта ўсё, што заўгодна - папярэдніка паказальнік, паказальнік PRED - гэта проста мянушка мы далі ў наш ўзор кода для маёй левай руцэ. З іншага боку, што будзе захаванне адсочваць, хто ёсць хто ў Наступныя сцэнары. Такім чынам, няхай, па-першае, я хачу абрываць што першы прыклад ўстаўкі, скажам 20 у спісе. Так што я збіраюся трэба, каб хтосьці ўвасабляюць у сабе лік 20 для нас. Так што мне трэба каго-то Malloc ад аўдыторыі. Падымайся. Як цябе завуць? Студэнт: Браян. Выступоўца 1: Браян, усё ў парадку, так што вы павінен быць вузел, які змяшчае 20. Добра, ідзі сюды. І відавочна, што, дзе Браян сапраўды належыце? Такім чынам, у сярэдзіне - уласна, пачакай хвілінку. Мы робім гэта не ў парадку. Мы робім гэта нашмат складаней , Чым яна павінна быць у першую чаргу. Добра, мы збіраемся бясплатна Браян Браян і Realloc як пяць. Такім чынам, зараз мы хочам, каб ўставіць Браян, як пяць. Так ідзі сюды побач з Бэн на імгненне. І вы, верагодна, можа сказаць дзе гэтая гісторыя ідзе. Але давайце старанна абдумайце парадак выканання аперацый. І гэта менавіта гэта візуальнае што адбываецца, каб выстраіцца з гэты ўзор кода. Дык вось я PTR першапачаткова паказваючы Ці не на Бэна, як такой, але на любым ацэньваюць ён утрымлівае, які ў дадзеным выпадку - Што цябе клічуць? Студэнт: Джэйсан. Выступоўца 1: Джэйсан, так як Бэн і я паказваючы на ​​Джэйсана ў гэты момант. Так што зараз у мяне ёсць, каб вызначыць, дзе ж Браян належыце? Таму адзінае, што я маю доступ да Прама цяпер яго N элемента дадзеных. Так што я збіраюся праверыць, ці з'яўляецца Браян менш Джэйсан? Адказ на гэтае пытанне так. Так што зараз павінна адбыцца, у правільным парадку? Мне трэба ўдакладніць, колькі паказальнікаў Усяго ў гэтай гісторыі? Дзе мая рука ўсё яшчэ паказваючы на Джэйсан, і ваша рука - калі вы хочаце пакласці руку, як, кшталту, я Не ведаю, знакам пытання. Добра, добра. Добра, так што вы павінны некалькі кандыдатаў. Альбо Бэн ці я ці Джэйсан Браян або ці ўсе астатнія, якія паказальнікі трэба змяніць? Колькі за ўсё? Такім чынам, два. Мой паказальнік на самай справе не мае ніякага значэння таму што я толькі часова. Так што гэтыя два хлопцы, па-відаць, як Бэн і Браяна. Такім чынам, дазвольце мне прапанаваць, што мы абнаўляем Бэн, так як ён у першую чаргу. Першым элементам гэтага спісу Цяпер будзе Браян. Так Бэн кропкі на Браяна. Добра, што цяпер? Хто атрымлівае паказаў на каго? Студэнт: [неразборліва]. Выступоўца 1: Добра, такім чынам Браян каб паказаць на Джэйсана. Але я страціў гэты паказальнік? Ці ведаю я, дзе Джэйсан? Студэнт: [неразборліва]. Выступоўца 1: я раблю, так як я часовы паказальнік. І па-відаць, я не змяніў , Каб паказаць на новы вузел. Так што мы можам проста Браян пункту той, хто на мяне паказваючы на. І мы зрабілі. Такім выпадкам, устаўка на пачатак спісу. Былі два ключавых кроку. Па-першае, мы павінны абнавіць Бэна, а затым Мы таксама павінны абнавіць Браян. І тады я не прыйдзецца турбавацца тащась праз астатнюю спіс, таму што мы ўжо знайшлі яго размяшчэнне, таму што ён належаў да злева ад першага элемента. Добра, даволі простая. На самай справе, здаецца, што мы ўжо амаль робіць гэта занадта складана. Такім чынам, давайце абрываць канца спісу, і ўбачыць, дзе Складанасць пачынаецца. Так што калі цяпер, я Alloc ад аўдыторыі. Любы хоча гуляць 55? Добра, я бачыў вашу руку першым. Падымайся. Да. Як цябе завуць? Студэнт: [неразборліва]. Выступоўца 1: Habata. ОК, давай ўверх. Вы будзеце нумарам 55. Такім чынам, вы, вядома, належаць ў канцы спісу. Так што давайце перайграць мадэлявання са мной быўшы PTR на імгненне. Так што я збіраюся першым, каб паказаць на усё, што Бэна паказваючы на. Мы абодва цяпер, паказваючы на ​​Браяна. Так 55 ня менш, чым пяць. Так што я збіраюся абнавіць сябе, паказваючы на ​​наступны паказальнік Браяна, які Цяпер, вядома, Джэйсан. 55 складае не менш за дзевяць, так Я збіраюся абнавіць PTR. Я збіраюся абнавіць PTR. Я збіраюся абнавіць PTR Я збіраюся абнавіць PTR. І я збіраюся - Хм, што гэта цябе завуць? Студэнт: Дыяны. Выступоўца 1: Дыяна паказвае, вядома, пры нулявым левай рукой. Дык дзе ж на самай справе Habata належаць ясна? З левага боку, тут. Так як я ведаю, паставіць яе тут Я думаю, што я аблажаўся. Бо што такое мастацтва PTR дадзены момант часу? Null. Так што, хоць, візуальна, мы можам Відавочна, усе гэтыя хлопцы тут на сцэне. Я не сачыў за папярэднімі чалавек у спісе. У мяне няма пальцам паказваючы, У гэтым выпадку нумар вузла 34. Так што давайце на самай справе пачаць над гэтым. Так што цяпер я на самой справе трэба Другая лакальнай зменнай. І гэта тое, што вы ўбачыце ў Сам ўзор кода C, дзе, як я іду, калі я абнаўляю маю правую руку, каб паказаць Джэйсан, тым самым пакідаючы Браяна ззаду, я лепш пачаць выкарыстоўваць маю левую руку, каб абнаўлення, дзе я быў, так што, як я іду праз гэты спіс - больш няёмка, чым хацеў Цяпер вось візуальна - Я іду, каб дабрацца да канцы спісу. Гэтая рука па-ранейшаму нулявы, які з'яўляецца даволі бескарысным, акрамя ўказваць Я ясна ў канцы спісу але цяпер па меншай меры, у мяне ёсць гэтая папярэдніка паказальнік, які паказвае тут, так што Цяпер тое, што рукі і тое, што трэба паказальнікі ў абнаўленні? Чыя рука вы хочаце пераналадзіць у першую чаргу? Студэнт: [неразборліва]. Выступоўца 1: Такім чынам, Дыяны. Дзе Вы хочаце, каб паказаць Левая Дыяны паказальнік ў? На 55, па-відаць, з тым каб мы ўставілі туды. А дзе павінны 55 паказальніка ісці? Ўніз, якая прадстаўляе нулявы. І мае рукі, на дадзены момант, не значэння, таму што яны былі проста часовых зменных. Так што цяпер мы скончым. Такім чынам, дадатковыя складанасці там - і гэта не так складана рэалізаваць, але нам патрэбна другая зменная, каб зрабіць упэўнены, што перш, чым я магу рухаць правай боку, я абнавіць значэнне маёй левай боку, прад паказальнік у гэтым выпадку, так што ў мяне ёсць задні паказальнік адсочваць, дзе я быў. Зараз, як у баку, калі вы думаеце, што гэта праз гэта пачуццё, што гэта крыху раздражняе, каб захаваць след гэтага левай рукой. Што б іншае рашэнне гэтай праблемы былі? Калі ў вас ёсць, каб перапраектоўваць дадзеных структуры мы гаворым праз прама цяпер? Калі гэта толькі збольшага адчувае сябе крыху раздражняльным, быццам бы, два паказальніка збіраецца па спісе, хто яшчэ мог былі, у ідэальным свеце, падтрымліваецца інфармацыю, якая нам патрэбна? Да? Студэнт: [неразборліва]. Выступоўца 1: Цалкам дакладна. Права так ёсць на самой справе цікавае зародак ідэі. І гэтая ідэя папярэдняга паказальніка, паказваючы на ​​папярэдні элемент. Што рабіць, калі я проста увасабленнем гэтага ўнутры самога спісу? І гэта будзе цяжка візуалізаваць Усё гэта без паперы падзення на падлогу. Але выкажам здагадку, што гэтыя хлопцы выкарыстоўвацца як іх рукі, каб мець папярэднія паказальнік, і наступны паказальнік, тым самым рэалізаваць тое, што мы назавем ўдвая звязаны спіс. Якая дазволіла б мне, каб разабрацца перамоткі, значна лягчэй без мяне, праграміст, неабходнасці трымаць адсочваць ўручную - сапраўды ўручную - ад таго, дзе я быў раней у спісе. Таму мы не будзем гэтага рабіць. Мы будзем трымаць яго проста, таму што гэта збіраецца прыйсці ў цане, у два разы шмат месца для паказальнікаў, калі вы хочаце другую. Але гэта сапраўды агульны Структура дадзеных вядомых як двойчы звязаны спіс. Давайце зробім апошні прыклад тут і пакласці гэтыя хлопцы з іх пакуты. Так Malloc 20. Падымайцеся з праходу там. Добра, як цябе завуць? Студэнт: [неразборліва]. Выступоўца 1: Прабачце? Студэнт: [неразборліва]. Выступоўца 1: Demeron? ОК падымайся. Вы павінны быць 20. Вы, відавочна, збіраюцца належаць ад 17 да 22. Такім чынам, дазвольце мне даведацца пра свой ўрок. Я збіраюся пачаць паказальнік паказваючы на ​​Браяна. І я буду мець маю левую руку абнаўляць толькі з Браянам, як я пераехаць у Джэйсан, 20 праверка робіць менш за дзевяць? Няма. На 20 менш, чым 17? Няма. На 20 менш, чым 22? Да. Так што паказальнікі ці рук трэба змяніць дзе яны паказваючы цяпер? Так што мы можам зрабіць, паказваючы на ​​17 20. Так што гэта нармальна. Куды мы хочам, каб паказаць паказальнік цяпер? У 22. І мы ведаем, дзе 22, зноў жа дзякуючы на мой часовы паказальнік. Такім чынам, мы ўсё ў парадку там. Дык з-за гэтага часовага захоўвання Я сачыў, дзе ўсё. І цяпер вы можаце візуальна ўдавацца у якім Вы належыце, і цяпер нам трэба 1, 2, 3, 4, 5, 6, 7, 8, 9 шароў стрэс, і апладысменты для гэтыя хлопцы, калі мы маглі. Прыгожа зроблена. [Апладысменты] Выступоўца 1: Добра. І вы можаце трымаць часткі паперы на памяць. Добра, так што, паверце мне, гэта нашмат лягчэй ісці праз гэта з людзей, чым з фактычным кодам. Але тое, што вы знойдзеце ў імгненне Цяпер, то, што ж - о, дзякуй. Дзякуй - з'яўляецца тое, што вы ўбачыце, што тыя ж дадзеныя структуры, звязаны спіс, можа на самай справе выкарыстоўвацца ў якасці будаўнічага блока, каб яшчэ больш складаных структур дадзеных. І зразумейце, занадта тэма тут з'яўляецца тое, што мы абсалютна ўвялі больш Складанасць у рэалізацыі гэтага алгарытму. Ўстаўкі, і калі мы прайшлі праз гэта, выдаленне і пошук, трохі складаней, чым быў з масівам. Але мы атрымаць некаторую дынаміку. Мы атрымліваем адаптыўную структуру дадзеных. Але зноў жа, мы плацім цану наяўнасцю некаторых дадатковыя складанасці, як у яго ажыццяўленні. І мы адмовіліся ад выпадковага доступу. І, шчыра кажучы, няма некаторых добрых чыстае прадметнае я магу даць вам, што кажа вось чаму звязаны спіс лепш, чым масіў. І пакінуць усё як ёсць. Таму што тэма паўтарэння цяпер, нават больш, што ў бліжэйшыя тыдні, з'яўляецца што значыць не абавязкова правільны адказ. Вось чаму ў нас ёсць асобныя восі дызайну для хатніх заданняў. Гэта будзе вельмі кантэкстна-залежных ці вы хочаце выкарыстоўваць гэтыя дадзеныя структуру або, што адно і яно будзе залежыць ад таго, што для вас важна ў плане рэсурсаў і складанасці. Але дазвольце мне прапанаваць, што ідэальныя дадзеныя Структура, Святы Грааль, былі б тое, што сталая часу, незалежна ад таго, колькі матэрыял ўнутры яе, не было б дзіўна, калі структура дадзеных, якая вяртаецца адказы пастаяннае час. Да. Гэтае слова ў вашым велізарным слоўніку. Ці не, гэта слова не з'яўляецца. Або любая такая праблема. Ну давайце паглядзім, калі мы не можам па крайняй меры, зрабіць крок на гэтым шляху. Дазвольце мне прапанаваць новую структуру дадзеных, якая могуць быць выкарыстаны для розных мэтаў, У гэтым выпадку называюць хэш-табліцы. І вось мы на самай справе вярнуцца да зірнуўшы ў масіве, і ў гэтым выпадку, а таксама некалькі адвольна, я намаляваў тую хэш-табліцы ў выглядзе масіва роду двухмерных масіў - ці, хутчэй, ён намаляваны тут як два аднамерны масіў - але гэта толькі масіў памерам 26, так што, калі мы называюць масівам, настольны кранштэйны нуля прамавугольніка ў верхняй частцы. Табліца 25 кранштэйны ўяўляе сабой прастакутнік у ніжняй часткі. І гэта, як я мог бы намаляваць дадзеныя структура, у якой я хачу захаваць імёны людзей. Так, напрыклад, і я не буду маляваць Усё гэта тут, на накладныя выдаткі, калі я было гэта масіў, які я зараз збіраюся называюць хэш-табліцу, і гэта зноў жа Размяшчэнне нуля. Гэта вось размяшчэнне , І гэтак далей. Я сцвярджаю, што я хачу выкарыстоўваць гэтыя дадзеныя Структура, дзеля абмеркавання, захоўваць імёны людзей, Аліса і Боб і Чарлі і іншыя падобныя імёны. Так што думаць пра гэта цяпер, калі пачаў , Скажам, слоўнік з вялікай колькасцю слоў. Яны, аказваецца, імёны У нашым прыкладзе. І ўсё гэта занадта дарэчныя, мабыць, ажыццяўленне праверкі арфаграфіі, як мы можа для праблемных ўсталяваць шэсць. Так што, калі ў нас ёсць масіў ад агульнага памеру 26 так што гэта 25-й размяшчэнне у ніжняй часткі, і я сцвярджаю, што Аліса Першае слова ў слоўніку імёны, якія я хачу ўставіць у аператыўную памяць, у гэтую структуру дадзеных, дзе інстынкты кажуць вам, што Алісы імя павінна ісці ў гэтым масіве? У нас ёсць 26 варыянтаў. Дзе мы хочам паставіць яе? Мы хочам яе ў кранштэйны нуля, ці не так? Для Алісы, давайце назавем што нуля. І B будзе адной і С будуць два. Такім чынам, мы збіраемся пісаць Аліса імя тут. Калі мы затым устаўце Боб, яго Назва пайду сюды. Чарлі пайду сюды. І гэтак далей ўніз праз гэтай структуры дадзеных. Гэта выдатная структуры дадзеных. Чаму? Ну тое, што час працы ўстаўка імя чалавека ў гэтую Структура дадзеных прама цяпер? Улічваючы, што гэтая табліца будзе рэалізаваны, сапраўды, як масіў. Ну, гэта пастаяннае час. Гэта парадку адзінкі. Чаму? Ну як вы вызначаеце, Дзе Alice належыць? Ты глядзіш на якую літару яе імя? Першае. І вы можаце атрымаць там, калі гэта радок, проста гледзячы на ​​радок Кранштэйн нуля. Такім чынам, нулявы сімвал радка. Гэта лёгка. Мы зрабілі гэта ў Crypto Прызначэнне тыдні таму. І тое, як толькі вы ведаеце, што Алісы Ліст капіталу, мы можам адняць ад 65 гадоў і сам капітал, , Што дае нам нуля. Такім чынам, мы цяпер ведаем, што Аліса належыць па месцы знаходжання нуля. А калі ўлічыць, паказальнік на гэтыя дадзеныя структуры, нейкай, як доўга мне спатрэбіцца, каб знайсці размяшчэнне нуля ў масіў? Усяго толькі адзін крок, правая Гэта пастаяннае час з-за выпадковага доступу мы Прапанаваны было асаблівасцю масіва. Карацей кажучы, высветліць, што індэкс імя Алісы, якая, па гэтым выпадку, або давайце проста вырашаць што да нуля, дзе B з'яўляецца адным і С два, мяркуючы, што з пастаянная часу. Я проста глядзець на яе першы ліст, высвятляючы, дзе нуль масіў таксама пастаяннае час. Так што тэхнічна гэта як цяпер два кроку. Але гэта ўсё роўна пастаянна. Так мы называем гэта Big O аднаго Такім чынам мы устаўленыя Аліса ў гэтую табліцу ў пастаяннае час. Але, вядома, я вяду сябе наіўная, так? Што рабіць, калі ёсць Аарона ў класе? Ці Алісія? Або любыя іншыя імёны, якія пачынаюцца з А. Куды мы збіраемся паставіць што чалавек, ці не так? Я маю на ўвазе, прама зараз ёсць толькі тры людзі на стол, таму магчыма, мы Аарон павінен пакласці па месцы знаходжання нуль адзін два тры. Права, я мог бы паставіць тут. Але тады, калі мы спрабуем ўставіць Давіда ў гэтага спісу, дзе ж Давід ісці? Цяпер наша сістэма пачынае парушэнні ўніз, направа? Таму што цяпер Дэвід заканчвае тут Калі на самай справе Аарон тут. І вось цяпер уся гэтая ідэя з чыстая структура дадзеных, якая дае нам уставак пастаяннага часу ўжо не пастаянны час, таму што я павінен праверыць, о, чорт вазьмі, хто-то ўжо па месцы знаходжання Алісы. Дазвольце мне даследаваць астатнюю частку гэтага дадзеныя Структура, шукаючы месца, каб пакласці хтосьці, як імя Аарона. І так, што таксама пачынае прыняць лінейнае час. Больш за тое, калі вы цяпер хочаце знайсці Аарон ў гэтай структуры дадзеных, і вы праверыць і імя Аарона тут няма. У ідэале, вы проста сказалі б Аарона не ў структуры дадзеных. Але калі вы пачынаеце вызваляючы месца для Аарон, дзе павінна было быць D або E, вы, горшым выпадку, прыйдзецца праверыць Уся структура дадзеных, у гэтым выпадку яна пераходзіць ў нешта лінейны у памер табліцы. Так што ўсё ў парадку, я буду гэта выправіць. Праблема тут у тым, што ў мяне было 26 элементаў у гэтым масіве. Дазвольце мне змяніць. На жаль. Дазвольце мне змяніць яго так, што замест быцця памер 26 у агульнай складанасці, звярніце ўвагу на ніжнюю Індэкс будзе мяняцца да N мінус 1. Калі 26 відавочна занадта малы для людзей " імёны, таму што ёсць тысячы імёны свету, давайце проста рабіць ў 100 або 1000 ці 10000. Давайце проста вылучыць нашмат больш месца. Ну, што зусім не абавязкова зніжае верагоднасць таго, што мы не будзем мець два людзі з імёнамі, якія пачынаюцца з, і Такім чынам, вы збіраецеся, каб паспрабаваць пакласці імёны па месцы знаходжання нуля да гэтага часу. Яны ўсё яшчэ збіраемся сутыкаюцца, якая азначае, што мы ўсё яшчэ трэба рашэнне, каб пакласці Аліса і Аарона і Алісія і іншыя імёны, якія пачынаюцца з у іншым месцы. Але як вялікая праблема гэта? Якая верагоднасць таго, што вы могуць узнікаць канфлікты ў дадзеных структуры, як гэта? Ну, дазвольце мне - мы вернемся На гэтае пытанне тут. І паглядзіце, як мы маглі б вырашыць у першую чаргу. Дазвольце мне падцягнуць гэтую прапанову тут. Тое, што мы толькі што апісалі алгарытм, эўрыстычныя называюцца лінейнымі зандзіравання якой, калі б вы паспрабавалі ўставіць нешта тут, у гэтым дадзеныя Структура, якая называецца хэш-табліцу, і там няма месца там, вы сапраўды даследаваць структуры дадзеных праверкі, гэта даступна? Ці з'яўляецца гэта даступна гэта даступна? Ці з'яўляецца гэта даступна? І калі ён, нарэшце, вы устаўце імя, якое вы першапачаткова ў іншых месцах у гэтым месцы. Але ў горшым выпадку, адзінае месца, можа быць у самым нізе дадзеных Структура, у самым канцы масіва. Так лінейнага зандзіравання, у горшым выпадку, ператворыцца ў лінейны алгарытм, дзе Аарона, калі ён адбудзецца, будзе ўстаўлены апошні У гэтай структуры дадзеных, ён можа сутыкацца з гэтай першай месцы, але Затым скончыцца няўдачай ў самым канцы. Так што гэта не пастаянная час святой Грааль для нас. Гэты падыход ўстаўкі элементаў у структуру дадзеных, званую хэш Табліца не здаецца, пастаянны час па меншай меры, у агульным выпадку. Гэта можа ператворыцца ў нешта лінейнай. Так што, калі мы дазволу калізій некалькі па-іншаму? Такім чынам, вось больш складаныя падыходзіць да таго, што да гэтага часу званы хэш-табліцу. І хэш, а ў бок, што Я маю на ўвазе, што індэкс Якім я казаў раней. Для хэш нешта можа быць разглядаць як дзеяслоў. Так што калі вы хэш Алісы імя, хэш-функцыі, так бы мовіць, павінна вяртаць лік. У гэтым выпадку роўна нулю, калі яна належыць на нулявым месцы, адзін, калі яна належыць на месцазнаходжанне, і гэтак далей. Так што мой хэш-функцыі да гэтага часу было супер проста, толькі гледзячы на Першая літара ў чыё-то імя. Але хэш-функцыя прымае ў якасці ўвесці некаторыя часткі дадзеных, радок, цэлае ўсё. І ён выплёўвае звычайна лік. І гэты лік, дзе, што дадзеныя элемент належыць у структуры дадзеных вядомы тут як хэш-табліцу. Так што проста інтуітыўна, гэта некалькі іншым кантэксце. Гэта фактычна мае на ўвазе прыклад з удзелам дні нараджэння, дзе там можа быць столькі, колькі 31 дзён у месяцы. Але тое, што гэтаму чалавеку вырашыць рабіць у выпадку сутыкнення? Кантэкст у цяперашні час, а не сутыкненне імёны, але сутыкненне дні нараджэння, калі два чалавекі маюць аднолькавы дзень нараджэння 2-га кастрычніка, напрыклад. Студэнт: [неразборліва]. Выступоўца 1: Так, так што тут мы маем больш эфектыўнага выкарыстання звязаных спісаў. Так гэта выглядае крыху па-іншаму чым мы звярнулі яго раней. Але мы, здаецца, ёсць у масіў на левай баку. У гэтым няма аднаго індэкса, для якія не асаблівай прычыны. Але гэта ўсё яшчэ масіве. Гэта масіў паказальнікаў. І кожны з тых элементаў, кожны з гэтыя колы або касая рыса - слэш прадстаўляе нулявы - кожная з гэтых паказальнікаў па-відаць, якія паказваюць на якія дадзеныя структуры? Звязаны спіс. Так што цяпер у нас ёсць магчымасць жорсткі код у нашай праграме Памер табліцы. У гэтым выпадку, мы ведаем, ніколі няма больш за 31 дзён у месяц. Так жорсткае кадаваньне значэння, як 31 разумнае ў гэтым кантэксце. У кантэксце імёнаў, жорсткага кадавання 26 не зьяўляецца неабгрунтаваным яго людзей толькі імёны пачынаюцца з, напрыклад, алфавіту з удзелам да Z. Мы можам ўціснуць іх усё ў гэтых дадзеных Структура пакуль, калі мы атрымліваем сутыкнення, мы не ставім тут імёны, мы замест гэтага думаць аб гэтых клетках а не як радкі сябе, але ў якасці паказальнікаў, напрыклад, Эліс. І тады Аліса можа мець іншы паказальнік ў іншае імя, якое пачынаецца з А. і Боб на самой справе ідзе сюды. І, калі ёсць іншы імя, якое пачынаецца з В, ён сканчаецца тут. І таму кожны з элементаў гэтай Табліца два, калі мы распрацавалі гэтую трохі разумнейшыя - Давай, - калі мы распрацавалі гэта крыху больш разумнейшы, зараз становіцца адаптивами структура, у якой няма цвёрдага абмежавання ад таго, колькі элементаў вы можаце ўставіць ў гэта, таму што калі ў вас ёсць сутыкнення, гэта нармальна. Проста ісці наперад і дадаць яго ў што мы бачылі трохі назад было вядомы як звязаны спіс. Ну давайце паўзу на імгненне. Якая верагоднасць сутыкнення у першую чаргу? Права, можа быць, я па думаў, можа быць, Я на інжынерных гэтую праблему, таму што вы ведаеце, што? Так, я магу прыдумаць адвольнае Прыклады з верхняй частцы маёй галавы, як Allison і Аарона, але ў рэчаіснасці, зададзена раўнамернае размеркаванне уваходаў, то ёсць некаторыя выпадковыя ўстаўкі у структуру дадзеных, што на самой справе Верагоднасць сутыкнення? Добра атрымліваецца, гэта на самай справе супер высокай. Дазвольце мне абагульніць гэтую Праблема, як гэты. Такім чынам, у пакоі N CS50 студэнтаў, што верагоднасць таго, што па меншай меры Два студэнта ў пакоі маюць аднолькавы дзень нараджэння? Так што ёсць што. Некалькі Hund - 200, 300 людзей тут і некалькі сотні людзей у сябе дома сёння. Так што калі вы хацелі спытаць сябе, што гэта верагоднасць два чалавекі У гэтым нумары, які мае той жа дзень нараджэння, мы можам зразумець гэта. І я сцвярджаю, на самай справе ёсць два людзей з такімі ж дзень нараджэння. Напрыклад, хто-небудзь маюць сёння дзень нараджэння? Учора? Заўтра? Усё ў парадку, таму ён адчувае сябе, як я збіраюся каб зрабіць гэта 363 або каля таго больш раз на самай справе высветліць, Калі ў нас ёсць сутыкнення. Ці мы маглі б проста зрабіць гэта матэматычна а ня стомна рабіць гэта. І прапаную наступнае. Таму я прапаную, каб мы маглі мадэляваць Верагоднасць двух людзей з ж дзень нараджэння, як і верагоднасць 1 мінус верагоднасць які не мае той жа дзень нараджэння. Такім чынам, каб атрымаць гэта, і гэта толькі мудрагелісты спосаб напісання гэтага, для Першы чалавек у пакоі, ён ці яна можа мець любую адну з магчымых Дні нараджэння мяркуючы, 365 дзён у годзе, з выбачэннямі для асоб з Лютаўская 29 гадоў. Такім чынам, першы чалавек у гэтым нумары бясплатны мець любую колькасць нараджэнняў з 365 магчымасцяў так, каб мы зробім гэта 365 падзяліць на 365, які з'яўляецца адным. Наступны чалавек у пакоі, калі мэта , Каб пазбегнуць сутыкнення, можна толькі яго ці яе дзень нараджэння аб тым, як шмат розных магчымых дзён? 364. Такім чынам, другое складнік ў гэтым выразе па сутнасці робяць, што матэматыка для нас шляхам адымання ад аднаго магчымы дзень. А потым на наступны дзень, на наступны дзень, на наступны дзень да агульнай колькасці людзей у пакоі. І калі мы, то разгледзім, што ж тады ёсць верагоднасць не кожны які мае унікальныя дні нараджэння, але зноў жа мінус 1 што, што мы атрымліваем выраз , Што можа вельмі мудрагеліста выглядаць наступным чынам. Але гэта больш цікава глядзець на візуальна. Гэта графік, дзе па восі абсцыс ўяўляе Колькасць чалавек у пакоі, колькасць нараджэнняў. На восі ардынат верагоднасць сутыкнення, два чалавекі якія маюць той жа дзень нараджэння. І ежу на дом ад гэтай крывой што, як толькі вы атрымаеце як 40 студэнты, твая чарга на 90% верагоднасці камбінаторнага двух чалавек ці больш якая мае той жа дзень нараджэння. І як толькі вы атрымаеце 58 чалавек падабаецца гэта амаль 100% шанец двух людзей у пакоі збіраюцца мець ж дзень нараджэння, хоць ёсць 365 або 366 магчымых вядра, і Толькі 58 чалавек у пакоі. Проста статыстычна вы, верагодна, атрымаць сутыкненняў, якая ў кароткія матывуе гэта абмеркаванне. Што нават калі мы атрымаць фантазіі тут, і пачаць з гэтых ланцугоў, мы ўсё яшчэ прыйдзецца сутыкненняў. Так што ўзнікае пытанне, што такое затраты на вядзенне аперацыі ўстаўкі і выдаленні у структуру дадзеных, як гэта? Ну дазвольце мне прапанаваць - і дазвольце мне вярнуцца да экрана над тут - калі мы п элементаў у спіс, так што калі мы спрабуем ўставіць N элементаў, і ў нас ёсць колькі ўсяго вядра? Скажам, 31 за ўсё вядра у выпадку нараджэння. Якая максімальная даўжыня аднаго гэтых ланцугоў патэнцыйна? Калі зноў ёсць 31 магчымых Дні нараджэння ў дадзеным месяцы. А бо гэта толькі зліпання ўсіх - на самай справе гэта дурны прыклад. Давайце рабіць, а не 26. Так што, калі на самай справе ёсць людзі, чые імёны Пачніце з праз Z, тым самым даючы нам 26 магчымасцяў. І мы, выкарыстоўваючы структуру дадзеных, як той, які мы толькі што бачылі, у выніку чаго мы маем масіў паказальнікаў, кожны з якіх паказвае на звязаны спіс, дзе Першы спіс усё з імем Эліс. Другі спіс з кожным імя, якое пачынаецца з, пачынаючы з В, і гэтак далей. Якая верагоднасць даўжыня кожнага з гэтыя спісы, калі выказаць здагадку, добры чысты Размеркаванне імёнаў праз Z па ўсёй структуры дадзеных? Там у рускіх людзей у структуры дадзеных падзеленае на 26, калі яны прыгожа распаўсюдзіцца па ўсёй структуры дадзеных. Такім чынам, даўжыня кожнага з гэтых ланцугоў п падзеленае на 26. Але ў вялікіх абазначэнне О, што гэта? Што гэта на самай справе? Так што гэта сапраўды проста п, ці не так? Таму што мы казалі ў мінулым, цьфу, што вы падзеліце на 26. Так, на самай справе гэта хутчэй. Але ў тэорыі, гэта не прынцыпова усё, што хутчэй. Такім чынам, мы, здаецца, не так ужо шмат бліжэй да гэтай Святой Грааль. На самай справе, гэта ўсяго толькі лінейнае час. Чорт вазьмі, у гэты момант, чаму б нам не Размесціце адзін велізарны звязаны спіс? Чаму б нам не выкарыстоўваць толькі адзін велізарны масіў для захоўвання імёнаў усё ў пакоі? Ну, ёсць яшчэ нешта пераканаўчым аб хэш-табліцы? Ці ёсць яшчэ нешта пераканаўчых аб структуры дадзеных , Які выглядае, як гэта? Гэта. Студэнт: [неразборліва]. Выступоўца 1: Так, і яшчэ раз, калі гэта проста лінейны алгарытм часу і лінейнае час структура дадзеных, чаму б мне не проста захоўваць імя кожнага ў вялікі масіве або ў вялікім звязаны спіс? І спыніце рабіць CS нашмат цяжэй , Чым яна павінна быць? Што з'яўляецца пераканаўчым з гэтай нагоды, нават хоць я падрапаў яго? Студэнт: [неразборліва]. Выступоўца 1: заказчыкам не? Дарагія больш. Так ўстаўкамі патэнцыйна маглі яшчэ сталай часу, нават калі вашы дадзеныя структура выглядае наступным чынам, масіў паказальнікаў, кожны з якіх паказвае на патэнцыйна звязаны спіс. Як вы маглі б дасягнуць пастаяннай Час ўвядзення імёны? Прыляпіце налепку на фронце, ці не так? Калі мы ахвяруем дызайн гол раней, дзе мы хацелі захаваць ўсіх па імёнах, напрыклад, сартуюць, ці ўсе лічбы на этапе адсартаваныя, Выкажам здагадку, што ў нас ёсць малокомплектных звязаны спіс. Гэта толькі варта нам адзін або два этапы, Як і ў выпадку з Бэнам і Браян раней, ўставіць элемент у пачатку спісу. Так што, калі мы не клапоцімся пра сартаванні ўсё з імёнаў, пачынаючы з або ўсё імёны, якія пачынаюцца з B, мы ўсё яшчэ можам дасягнення пастаяннай час ўстаўкі. Цяпер гледзячы Алісы або Боба або любое імя ў цэлым усё яшчэ што? Гэта вялікае Аб ад N падзеленае на 26, у ідэальным выпадку, калі ўсё гэта раўнамерна размеркаваны, дзе ёсць столькі аўтара як ёсць Z, які, верагодна, нерэальна. Але гэта па-ранейшаму лінейна. Але і тут мы вяртаемся да кропкі асімптатычнай абазначэння быцця Тэарэтычна дакладна. Але ў рэальным свеце, калі я сцвярджаю, што мая праграма можа зрабіць што-то 26 разоў хутчэй, чым ваша, чыя праграма Вы збіраецеся аддаеце перавагу выкарыстоўваць? Ваша або мая, якая у 26 разоў хутчэй? Рэальна, асобы, складае 26 разы хутчэй, нават калі тэарэтычна нашы алгарытмы працуюць у тым жа асімптатычнае час. Дазвольце мне прапанаваць іншую Рашэнне ў цэлым. І калі гэтага не адразу вас напавал, мы са структур дадзеных. Дык гэта ён, сінтаксічнага дрэва - выгляд дурное імя. Яно паходзіць ад вымання, і слова пішацца сінтаксічнага дрэва, т-р-і-е, з-за Вядома пошуку гучыць як сінтаксічнага дрэва. Але гэта гісторыя словы сінтаксічнага дрэва. Так сінтаксічнага дрэва сапраўды свайго роду дрэва, і гэта таксама гульня на гэтае слова. І хоць вы не можаце досыць убачыць яго з гэтай візуалізацыі, сінтаксічнага дрэва з'яўляецца дрэва структураваныя, як сям'я дрэва з адным продкам наверсе і шмат з унукаў і праўнукаў як пакідае на дне. Але кожнаму вузлу ў выглядзе дрэва з'яўляецца масівам. І гэта ў масіве - і давай спрашчаць на імгненне - гэта масіў, у гэтым выпадку, памер 26, дзе кожны вузел зноў масіў памеру 26, дзе нулявы элемент у гэтым Масіў ўяўляе, а апошні элемент у кожным такім Масіў ўяўляе Z. Так што я прапаную, тое, што гэтыя дадзеныя структуры, вядомай як выглядзе дрэва, можа быць выкарыстоўвацца таксама для захоўвання слоў. Мы бачылі, як хвіліну назад, мы маглі захаваць словамі, ці ў дадзеным выпадку імёны, і мы бачылі раней, як мы можам захоўваць лікі, але калі мы арыентуемся на імёны ці радкі заўважце, што цікава. Я сцвярджаю, што імя Максвелла Унутры гэтай структуры дадзеных. Дзе вы бачыце Максвелла? Студэнт: [неразборліва]. Выступоўца 1: на левай баку. Так што цікава, з гэтымі дадзенымі структура, а не крама Радок M-A-X-W-E-L-L зваротнай касой рысы нуля, усё бесперапынна, а не тое, што вы робіце складаецца ў наступным. Калі гэта так сінтаксічнага дрэва структуры дадзеных, кожны з якіх вузлоў зноў масіва і вы хочаце захаваць Максвелла, спачатку індэкс і так кораня вузла, так што сказаць, верхні вузел, ў становішчы М, направа, так прыкладна ў сярэдзіне. , А затым адтуль, вы будзеце прытрымлівацца паказальніка на даччыныя вузлы, так бы мовіць. Такім чынам, у тым сэнсе, дрэва сям'і, вы будзеце прытрымлівацца яго ўніз. І гэта прывядзе вас да іншага вузла На левым баку, якая з'яўляецца проста яшчэ адзін масіў. І потым, калі вы хочаце захаваць Максвел, вы знойдзеце паказальнік, які ўяўляе , Якая з'яўляецца гэты тут. Тады вы ідзяце да наступнага вузла. І звярніце ўвагу - менавіта таму карціны трохі падманвае - гэты вузел выглядаць супер малюсенькія. Але права гэта Y і Z. Гэта проста аўтар ўсечанай здымак так, каб вы на самой справе бачыць рэчы. У адваротным выпадку гэта фота б надзвычай шырокі. Такім чынам, зараз вы індэкса ў вочка X, то W, то Е, то L, то L. Тады ў чым гэта цікаўнасць? Ну, калі мы выкарыстоўваем гэты выгляд новых ўзяць на сябе, як захоўваць радок у структуры дадзеных, вам усё роўна прыйдзецца істотна галачку ў дадзеных структуры, што слова заканчваецца. Іншымі словамі, кожны з гэтых вузлоў так ці інакш трэба памятаць, што мы фактычна выканалі ўсе гэтыя паказальнікі і з'язджаюць крыху хлебных дробак на дне тут гэтага Структура, каб паказаць, M-A-X-W-E-L-L ўяўляе сапраўды, у гэтай структуры дадзеных. Такім чынам, можна зрабіць наступным чынам. Кожны з вузлоў на малюнку мы проста піла мае адзін, масіў памерам 27. І гэта зараз 27, так як у P ўсталяваць шэсць, мы фактычна даюць вам апостраф, каб мы маглі мець імёны, як O'Reilly і іншыя з апострафа. Але тая самая ідэя. Кожны з гэтых элементаў у масіва паказвае на структуру вузел, так што проста вузлом. Так што гэта вельмі нагадвае нашай звязанага спісу. А то ў мяне лагічны, які я называю слова, якое проста будзе дакладна, калі слова заканчваецца на гэтым вузел у дрэве. Гэта па сутнасці, ёсць трохі трыкутніка мы бачылі некалькі хвілін таму. Так што, калі слова заканчваецца ў гэтым вузле ў Дрэва, гэтае слова поле будзе праўдай, які канцэптуальна галачкі, або мы малюем гэты трохкутнік, ды там гэтае слова тут. Так што гэта сінтаксічнага дрэва. А цяпер пытанне ў тым, што з'яўляецца час яго працы? Ён вялікі O п? Гэта што-то яшчэ? Ну, калі вы п імёны ў гэтых дадзеных Структура, Максвел ўсяго толькі адзін з іх, што час працы ўстаўкі або знайсці Максвелла? Што час працы ўстаўкі Максвелла? Калі ёсць іншыя назвы N ўжо ў табліцы? Да? Студэнт: [неразборліва]. Выступоўца 1: Так, гэта даўжыня імя, ці не так? Так М-а-х-З-е-л-л таму ён адчувае сябе, як гэта Алгарытм Big O сямі. Цяпер, вядома, імя будзе вар'іравацца ў даўжыню. Можа быць, гэта кароткае імя. Можа быць, гэта доўгае імя. Але тое, што ключавым тут з'яўляецца тое, што гэта пастаяннае лік. А можа быць, гэта не зусім сталае, але Бог, калі рэальна, у слоўнік, там, напэўна, некаторы мяжа на колькасць літар у імя чалавека ў канкрэтнай краіне. І такім чынам, мы можам выказаць здагадку, што значэнне з'яўляецца сталым. Я не ведаю, што гэта такое. Гэта, напэўна, больш, чым мы думаем, што гэта такое. Таму што заўсёды ёсць які-небудзь кут выпадку з вар'ятам доўгае імя. Так што давайце называць гэта К, але яна па-ранейшаму пастаянная як мяркуецца, таму што кожны назваць у свеце, па меншай меры канкрэтнай краіны, з'яўляецца тое, што даўжыня або карацей, так што гэта пастаянна. Але калі мы сказалі нешта вялікае O пастаяннага значэння, што гэта такое сапраўды эквівалентныя? Гэта сапраўды адно і тое ж як кажуць пастаяннае час. Зараз мы накшталт падману, праўда? Мы накшталт выкарыстоўваючы некаторыя тэорыі тут, каб сказаць, што добра, парадку Да сапраўды толькі парадку адной, і гэта пастаяннае час. Але гэта на самай справе. Паколькі ключавое разуменне ў тым, што калі мы маем п імёны ўжо ў гэтым структуру дадзеных, і мы ўстаўляем Максвел, гэта колькасць часу, якое патрабуецца нам ўставіць Максвелла на ўсіх пацярпелых па тым, як шмат іншых людзей ў структуры дадзеных? Не падобна, каб быць. Калі б я быў мільярд больш элементаў у гэтай дрэва, а затым ўставіць Максвеллом Ён на ўсіх пацярпелых? Няма. І гэта ў адрозненне ад любога дня дадзеныя структур, якія мы бачылі да гэтага часу, дзе час працы вашага алгарытму зусім не залежыць ад таго, колькі матэрыял або яшчэ не быў У гэтай структуры дадзеных. І так з гэтым дае вам цяпер магчымасць усталяваць шэсць р, якая будзе зноў звязана з ажыццяўленнем ўласнай праверка арфаграфіі, чытання ў 150000 словамі, як лепш захаваць гэтую не абавязкова з'яўляецца відавочным. І хоць я імкнуўся знайсці Святой Грааль, я не сцвярджаюць, што гэта сінтаксічнага дрэва. На самай справе, Хэш-табліцу можна вельмі добра апынуцца значна больш эфектыўным. Але гэта толькі - гэта толькі адна з праектных рашэнняў Вы павінны зрабіць. Але ў заключэнне давайце 50 або каля таго секунды, каб зірнуць на тое, што ляжыць наперадзе на наступным тыдні і далей мы пераходзім з гэтай каманднага радка З светам, калі на вэб-праграмы рэчаў заснаваны і моў, як PHP і JavaScript і сам Інтэрнэт, пратаколаў, такіх як HTTP, якія ў вас ёсць само сабой якія разумеюцца, на працягу многіх гадоў цяпер, і кожны набраў больш дзень, мабыць, і не бачыў. І мы пачнем адхіліце пластах Што такое Інтэрнэт. А што гэта за код, які ляжыць у аснове сённяшняй інструментаў. Так 50 секунд гэты тізер тут. Я даю вам Воіны Сеткі. [Прайграванне відэа] -Ён прыйшоў з паведамленнем. З пратаколам усё сваё. Ён прыйшоў у свет жорсткіх брандмаўэраў, абыякавымі маршрутызатары, і небяспекі далёка горш, чым смерць. Ён хуткі. Ён моцны. Ён TCPIP. І ў яго ёсць ваш адрас. Ваяры ў Сеткі. [КАНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ] Выступоўца 1: Гэта значыць, як у інтэрнэце будзем працаваць на наступным тыдні.