[Музыка, якая іграе] DAVID Малання: Гэта CS50. І гэта як пачатак і end-- як literally-- амаль да канца з шостым тыдні. 

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

АЎДЫТОРЫЯ: [неразборліва] DAVID Малання: Сапраўды. І яшчэ пацешна, не дай бог, мы праводзім адну лекцыю ў пятніцу ў пачатку семестра, гэта тое, што мы бачым здарыцца. Таму сёння, калі мы прымаем ў трохі больш пра структурах дадзеных. І, каб даць вам больш цвёрдага цела Ментальная мадэль для задач у пяць, які ў цяперашні час па-за. Арфаграфічныя памылкі, у якім мы будзем ўручыць вам тэкставы файл некаторыя 100000 плюс ангельскія словы, і Вы будзеце мець, каб высветліць, як спрытна загружаць іх у памяць, у аператыўнай памяці, выкарыстоўваючы некаторыя дадзеныя Структура вашага выбару. 

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

АЎДЫТОРЫЯ: Устаўка. 

DAVID Малання: Устаўка. Што вы маеце на ўвазе? 

АЎДЫТОРЫЯ: Дзе заўгодна разам Спіс [неразборліва]. 

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

Што яшчэ было выгадна аб звязаным спісе? Так? 

АЎДЫТОРЫЯ: [неразборліва] DAVID Малання: Выдатна. Ідэальны. Гэта сапраўды дынамічным. І што вы не здзяйсняе, загадзя, да некаторай фіксаванага памеру ўчастак памяці, як вам прыйдзецца каб з масівам, уверх з якіх з'яўляецца тое, што вы можаце вылучыць вузлы толькі на Попыт, такім чынам, выкарыстоўваючы толькі столькі месца як вы на самой справе трэба. У адрозненне ад масіва, вы маглі б выпадкова вылучыць занадта мала. А потым ён проста будзе быць боль у шыі пераразмеркаваць новы большы масіў, капіяваць ўсё больш, вызваліць стары масіў, а затым перайсці аб вашым бізнэсе. Ці яшчэ горш, вы можаце вылучыць шлях больш памяці, чым вы на самой справе трэба, і такім чынам, вы будзеце мець вельмі маланаселенай масіў, так бы мовіць. 

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

АЎДЫТОРЫЯ: Няма адвольнага доступу. 

DAVID Малання: Няма адвольнага доступу. Але каго гэта хвалюе? Адвольны доступ гучыць не пераканаўча. 

АЎДЫТОРЫЯ: [неразборліва] DAVID Малання: Цалкам дакладна. Калі вы хочаце мець пэўная algorithm-- і дазвольце мне на самай справе прапануюць бінарны пошук, у прыватнасці, што з'яўляецца адным мы выкарыстоўвалі даволі bit-- калі ў вас няма выпадковага доступу, Вы не можаце зрабіць што простую арыфметыку знайсці як сярэдні элемент і скача прама да яго. Вы замест гэтага пачаць у першы элемент і лінейна пошук злева направа, калі вы хочаце знайсці сярэдні ці любы іншы элемент. 

АЎДЫТОРЫЯ: Гэта, верагодна, зойме больш памяці. 

DAVID Малання: зойме больш памяці. Дзе, што дадатковы Кошт які прыбывае з памяці? 

АЎДЫТОРЫЯ: [неразборліва] DAVID Малання: Цалкам дакладна. У гэтым выпадку тут, у нас былі звязаны спіс для цэлых лікаў, і яшчэ мы падвойвае аб'ём памяці мы павінны таксама шляхам захоўвання гэтыя паказальнікі. Цяпер менш буйной здзелкі, як Вашы Структуры атрымаць больш і вы захоўваеце ня шэраг, але можа быць, студэнт ці нейкі іншы аб'ект. Але справа, вядома, застаецца. І так лік аперацый на звязаных спісах называліся былі вялікімі вываду N-- лінейнай. Такія рэчы, як ўстаўкі ці пошуку або выдаленне ў выпадку элемента апынуўся ў самым канцы Спіс няхай гэта будзе сартуюцца ці не. 

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

Ну, калі вы, як я, вы маглі б бачыць, што гэта м, так што я збіраюся роду паставіць гэта ў, калі гэта мой стол ці мой паверх, дзе Я распаўсюдзе рэчы out-- ці мой масіў really-- Я мог бы паставіць усё Ms там. О. Вось А. Такім чынам, я мог бы пакласці As тут. О. Вось яшчэ А. Я збіраюся пакласці, што тут. Вось З. Вось яшчэ М. І так Я мог бы пачаць рабіць палі, як гэта. І тады, магчыма, я б у далейшым і свайго роду вельмі nitpicky-лы роду асобныя палі. Але справа ў тым, я хацеў бы паглядзець на ўваходзе, што я рукамі і я хацеў бы зрабіць некаторыя разлічваецца Рашэнне заснавана на гэтым ўваходзе. Калі ён пачынаецца з, паклаў яго там. Калі ён пачынаецца з Z, паставіць яго на там, і ўсё паміж імі. 

Так што гэта тэхніка, гэта як правіла, вядомыя як hashing-- Н-A-S-Н- Звычайна гэта азначае, узяўшы ў якасці ўваход і з дапамогай гэтага уваход для разліку Значэнне, як правіла, колькасць, і што лік з'яўляецца індэксам ў захоўванні Кантэйнер, як масіў. Такім чынам, іншымі словамі, я мог бы Хэш функцыя, як і я, у маёй галаве, што, калі я бачу кагосьці гэта Назва, хто пачынае з А, Я збіраюся карту, што да нуля ў маёй галаве. І калі я бачу кагосьці, з Z, я збіраецца карту, што да 25 у мяне ў галаве а затым пакласці, што ў апошні найбольш куча. 

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

АЎДЫТОРЫЯ: Мінус А. 

DAVID Малання: Так. Так мінус-мінус спецыяльна 65, калі гэта Сталіца А. Або 98, калі гэта маленькая. І так, што дазволіць нам, вельмі проста і вельмі арыфметычна, пакласці што-то ў вядро, як, што. Вось і атрымліваецца, што мы на самай справе гэта таксама яшчэ з віктарыны. 

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

Так гэтая ідэя хэшавання што вы ўбачыце гэта даволі магутны на самай справе даволі звычайным і вельмі інтуітыўна, так жа, як, магчыма, падзяліць і захоп быў нулявы тыдні. Я перанясемся ў Hackathon Пару гадоў таму. Гэта было Zamyla і пару Іншыя студэнты персанал віншавальныя як яны ўвайшлі. І ў нас быў цэлы букет складвання сталы там з бэйджы. І мы тэгі імёнаў арганізаваны з як як над там і Zs там. І таму адзін з ТФ вельмі разумна напісаў гэта як інструкцыі на працягу дня. І ў 12-й тыдню семестра гэтым усё мела сэнс, і ўсё ведаў, што рабіць. Але ў любы час вы маеце чаргу такім жа чынам, вы рэалізуеце ж паняцце хэш. Так што давайце фармалізаваць гэта няшмат. Вось гэта масіў. Гэта звяртаецца, каб быць трохі Шырокі проста адлюстраваць, візуальна, што мы маглі б паставіць струны у чымсьці накшталт гэтага. І гэты масіў відавочна памер 26 за ўсё. І справа называецца Табліца адвольна. Але гэта ўсяго толькі выкананне мастака таго, што можа быць хэш-табліцу. 

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

Так з хэш-табліцы мы маглі б рэалізаваць яго ў памяці наглядна, як гэта, але як можа ён на самай справе быць закадзіраваны да? Ну, можа быць, як проста гэта. Калі ПАТЭНЦЫЯЛ загалоўнымі літарамі, гэта проста некаторыя constant-- напрыклад 26, для 26 літар alphabet-- Я мог бы назваць сваю табліцу зменных, і я мог бы сцвярджаць, што я збіраюся пакласці тэкставыя зоркі ў там, ці радкі. Так што гэта так проста, як гэта, калі вы хочаце рэалізаваць хэш-табліцу. І ўсё ж, гэта сапраўды проста масіў. Але, зноў жа, хэш Табліца зараз тое, што мы будзем называюць абстрактны тып дадзеных, гэта толькі роду канцэптуальнай слаёў зверху аб чым-то больш свецкага Цяпер хацелася масіў. 

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

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

Цяпер раней я накшталт падманулі і зрабілі гэта, ці я толькі збольшага ўкладваюцца іх адно над адным. Але што не збіраецца ляцець у кодзе. Дык дзе я мог бы паставіць Другі студэнт, чыё імя гэта калі ўсё, што я меў гэта даступныя таблічнага прасторы? І я выкарыстаў тры слота і яго Падобна на тое, ёсць толькі некалькі іншых. Што вы маглі б зрабіць? АЎДЫТОРЫЯ: [неразборліва] DAVID Малання: Так. Можа быць, давайце проста трымаць яго проста. Ці не так? Гэта не ўкладаецца, дзе я хачу паставіць яго. Так што я збіраюся паставіць яго тэхнічна, дзе B пойдзе. Цяпер, вядома, я пачынаю маляваць сябе ў кут. Калі я дабяруся да студэнта чыё імя на самай справе B, Цяпер B збіраецца быць трохі ссунуўся наперад, як можа здарыцца, так, калі гэта B, цяпер ён павінен прайсці тут. 

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

Зараз, цана надаецца цяпер для гэтага рашэння з'яўляецца тое, што? У нас ёсць масіў фіксаванага памеру, і калі я ўстаўляю імёны у яе, па меншай меры, на пачатковым этапе, што час працы ўстаўкі для здачы студэнтаў віктарыны ў правільных вядра? Big O чаго? 

АЎДЫТОРЫЯ: н. DAVID Малання: Я чуў, вялікі O п. Гэта не так. Але мы будзем дражніць адзін ад аднаго чаму праз хвіліну. Што яшчэ гэта можа быць? 

АЎДЫТОРЫЯ: [неразборліва] DAVID Малання: І дазвольце мне зрабіць гэта візуальна. Так, напрыклад, гэта літара S. 

АЎДЫТОРЫЯ: Гэта адзін. DAVID Малання: Гэта адзін. Ці не так? Гэта масіў, які значыць, у нас ёсць адвольны доступ. І калі мы думаем, што гэта як нуль і гэта як 25, і мы разумеем, што, ой, вось мой ўклад S, Я магу, вядома, канвертаваць S, ASCII сімвалаў, на адпаведны нумар паміж нулём і 25 , А затым неадкладна пакласці яго дзе яна належыць. 

Але, вядома, як толькі я дабяруся да Другі чалавек, які клічуць А ці У або З у рэшце рэшт, калі я выкарыстаў лінейны зандзіравання ў якасці майго рашэння, час працы ўстаўкі ў горшым выпадку на самай справе адбываецца, каб ператворыцца ў чым? І я чую яго тут Правільна рана. АЎДЫТОРЫЯ: [неразборліва] DAVID Малання: Дык гэта н сапраўды калі-то ў вас ёсць дастаткова вялікі набор дадзеных. Так, з аднаго боку, калі ваш масіў досыць вялікі і вашы дадзеныя досыць рэдкія, вы атрымаць гэтую прыгожую пастаяннае час. Але як толькі вы пачынаеце усё больш і больш элементаў, і толькі статыстычна Вы атрымліваеце больш людзей з літарай Як іх імя або ліст B, гэта можа патэнцыйна пераходзіць у што-то больш лінейнымі. Так што не зусім ідэальна. Так мы маглі зрабіць лепш? 

Ну, тое, што было нашым Рашэнне раней, калі мы хочуць мець большы дынамізм, чым нешта накшталт масіва дазволена? АЎДЫТОРЫЯ: [неразборліва] DAVID Малання: Што мы ўводзім? Так. Так звязаны спіс. Ну, давайце паглядзім, што звязана Спіс можа зрабіць для нас, а не. Ну, дазвольце мне прапанаваць, што мы маляваць карціну наступным чынам. Зараз гэта ўжо іншая карцінка з прыкладу з другога тэкст, на самай справе, што на самай справе, выкарыстоўваючы масіў памерам 31. І гэты аўтар проста вырашыў хэш радкі не на аснове імёнаў гэтай асобы, але на аснове іх даты нараджэння. Незалежна ад месяца, яны лічылі, калі вы нарадзіліся з першага месяца або 31-е чысло месяца, аўтар будзе хэш на аснове гэтага значэння, з тым, каб распаўсюдзіць імёны з трохі больш, чым проста 26 плямы могуць дазволіць. І, магчыма, гэта крыху больш раўнамернае чым ісці з літар алфавіту, таму што, вядома, ёсць, верагодна, Чым больш людзей у свеце з імёнамі што пачатак з чым, вядома, некаторыя іншыя літары алфавіту. Так, можа быць, гэта крыху больш раўнамернае, мяркуючы Раўнамернае размеркаванне немаўлятаў праз месяц. 

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

АЎДЫТОРЫЯ: звязаны спіс. 

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

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

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

АЎДЫТОРЫЯ: Таму што, калі ўсё мае той жа дзень нараджэння, яны збіраюцца быць адна лінія. DAVID Малання: Выдатна. Гэта можа быць трохі надуманы, але сапраўды, у горшым выпадку, калі кожны чалавек мае той жа дзень нараджэння, улічваючы ўваходы ў вас ёсць, Вы будзеце мець, масава доўгі ланцужок. І так, вы маглі б назваць гэта хэш-табліцу, але на самой справе гэта проста масіўны звязаны спіс з ў цэлым шмат невыкарыстоўваемай прасторы. Але ў цэлым, калі лічыць, што па меншай меры, дні нараджэння uniform-- і гэта, верагодна, не. Я раблю гэта. Але калі выказаць здагадку, для дзеля абмеркавання што яны, то ў тэорыі, калі Гэта вертыкальнае прадстаўленне з масіва, а затым, спадзяюся, вы збіраецца атрымаць ланцугоў, якія з'яўляюцца, вы ведаеце, прыкладна такой жа даўжыні, дзе кожны з гэта ўяўляе сабой дзень месяца. 

Цяпер, калі ёсць 31 дзён у месяц, што азначае мой час працы сапраўды вялікі вываду п над 31, якія адчувае сябе лепш, чым лінейны. Але тое, што было адным з нашых Абавязацельствы пару тыдняў таму, калі ён прыйшоў да выказвання час працы алгарытму? Проста толькі паглядзіце на высокім тэрмін замовы. Ці не так? 31, безумоўна, карысна. Але гэта па-ранейшаму вялікі O п. Але адна з тым, з праблем ўсталяваць пяць будзе ў прызнаць, што абсалютна, асімптатычна, тэарэтычна Гэтая структура дадзеных няма лепш, чым проста адзін масіўны звязаны спіс. І на самай справе, у горшым выпадку, гэта Хэш-табліцы можа ператворыцца ў што. 

Але ў рэальным свеце, з намі людзі што ўласных кампутарах Mac або ПК або што і працуеце рэальны свет Праграмнае забеспячэнне на рэальных дадзеных, які алгарытм вы збіраецеся аддаеце перавагу? Той, які прымае канчатковыя крокі або той, які бярэ н дзеліцца на 31 крокаў знайсці нейкі фрагмент дадзеных або шукаць некаторую інфармацыю? Я маю на ўвазе, абсалютна тыя 31 марак Розніца ў рэальным свеце. Гэта ў 31 разоў хутчэй. І мы, людзі, вядома, спадабаецца, што. 

Так разумею, дыхатамію там паміж фактычна казаць пра тое, тэарэтычна і асімптатычна якія вызначана мае значэнне, як мы бачылі, але ў рэальным свеце, калі вы клапоціцеся аб проста зрабіць чалавек шчаслівы па агульных уваходам, Вы маглі б вельмі добра хочуць прымаць Справа ў тым, што, так, гэта лінейная, але гэта ў 31 разоў хутчэй чым лінейная можа быць. А яшчэ лепш, мы не проста павінны зрабіць што-то адвольнае, як дата нараджэння, мы маглі б выдаткаваць трохі Чым больш часу і розум і думаю пра тое, што мы маглі б зрабіць, імя чалавека і, можа быць, іх дата нараджэння аб'яднаць тых, інгрэдыенты, каб высветліць што-то што гэта сапраўды больш, раўнамернае і менш п'яны, так бы мовіць, чым гэтай карціне У цяперашні час мяркуе, што гэта магло б быць. Як мы маглі рэалізаваць гэта ў кодзе? Ну, дазвольце мне прапанаваць, што мы проста пазычыць сінтаксіс мы выкарыстоўваць пару разоў да гэтага часу. І я збіраюся вызначыць Вузел, які зноў гэта агульны тэрмін для толькі некаторыя Кантэйнер па якой структуры дадзеных. Я збіраюся прапанаваць, каб радок будзе там. Але мы збіраемся пачаць прымаць тыя, навучанне колаў ад цяпер. 

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

А цяпер, як я заяўляю, саму табліцу? Як аб'явіць усю гэтую структуру? Ну, на самай справе, гэтак жа, як я выкарыстаў паказальнік каб толькі першы элемент спісу да, так жа я магу толькі сказаць, Мне проста трэба кучу паказальнікаў ажыццявіць увесь гэты хэш-табліцу. Я збіраюся ёсць масіў называецца табліца для хэш-табліцы. Гэта збіраецца быць ёмістасці памеру. Вось колькі элементаў можа змясціцца ў яго. І кожны з гэтых элементаў у гэтым Масіў будзе вузел зорка. Чаму? Ну, за гэтую карціну, тое, што я рэалізацыі хэш-табліцу ў якасці эфектыўна ў пачатак усяго гэта масіў, які мы намалявалі вертыкальна, кожны з якіх квадратаў ўяўляе сабой паказальнік. Гэта тыя, якія маюць касую рысу праз іх проста нулявым. І тыя, якія маюць Стрэлкі, якія ідуць справа фактычныя паказальнікі на фактычныя вузлоў, Ergo пачатак звязанага спісу. 

Дык вось, тое, як мы маглі б рэалізацыі хэш-табліцу, што рэалізуе асобны ланцужкі. Цяпер мы можам зрабіць лепш? Добра, я абяцаў у мінулы раз, што мы маглі б дамагчыся сталага часу. І я як бы даў вам пастаянная часу тут, але тады не сказаў на самай справе Пастаянная часу, таму што гэта ўсё ж такі залежыць ад агульнага Колькасць элементаў Вы ўводу ў Структура дадзеных. Але выкажам здагадку, што мы зрабілі гэта. Дазвольце мне вярнуцца да экрана тут. Дазвольце мне таксама праецыраваць гэта тут, відавочна, экран, і выкажам здагадку, што я зрабіў гэта. Выкажам здагадку, што я хацеў, каб ўставіць імя Daven ў ў маёй структуры дадзеных. 

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

У прыватнасці, я збіраюся лячыць гэта, то В, то С, затым D, гэты тут. Дык гэта будзе эфектыўна ўяўляюць літару D. Але, каб ўставіць ўсе Daven-х назваць мне трэба зрабіць трохі больш. Так што я спачатку буду хэш, так бы мовіць. Я збіраюся паглядзець на першую літару у Daven, які, відавочна, з'яўляецца D, і я збіраюся вылучыць вузел, які выглядае як this-- вялікі прастакутнік вялікі дастаткова, каб адпавядаць ўвесь алфавіт. 

Цяпер D робіцца. Цяпер А. Д-А-В-Е-Н і з'яўляецца мэтай. Так што цяпер я збіраюся зрабіць гэта. Як толькі я пачаў D апавяшчэнне няма паказальніка там. Гэта каштоўнасці смецця на дадзены момант, ці я мог бы ініцыялізаваць яго да нуля. Але дазвольце мне працягваць ісці з гэтая ідэя пабудовы дрэва. Дазвольце мне вылучыць яшчэ адзін з іх вузлы, якія мае 26 элементаў у ім. 

І ведаеце што? Калі гэта ўсяго толькі вузел у памяці, што Я стварыў з Таноса, выкарыстоўваючы-структуру як мы хутка ўбачым, Я збіраюся зрабіць this-- Я збіраюся намаляваць стрэлку ад рэч, якая прадстаўлена D ўніз у гэтым новым вузле. А цяпер, па-першае побач Ліст на імя Daven ў, V-- D-A-V-- я збіраюся ісці наперад і зрабіць яшчэ адзін вузел, як гэта, у выніку чаго, у V элементы тут, якія мы будзем маляваць для instance-- воклічамі. Мы не будзем маляваць там. Гэта збіраецца ісці сюды. 

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

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

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

Між тым, калі б я меў больш месца тут, што я мог зрабіць P-O-R-T, і я мог бы паставіць праверку ў вузле што ёсць літара Т ў самым канцы. Так што гэта масава Комплекс выгляд структуры дадзеных. І мой почырк вядома, не дапаможа. Але калі б я хацеў, каб ўставіць што-то яшчэ, падумайце, што мы будзем рабіць. Калі б мы хацелі паставіць Давіда ў, мы прытрымлівацца той жа логіцы, D-A-V, але цяпер я хацеў бы адзначыць у наступным Элемент не ад Е, але ад I да D. Так што гэта будзе больш вузлоў у гэтым дрэве. Мы збіраемся мець выкліку Таноса больш. Але я не хачу, каб зрабіць поўны беспарадак малюнка. Такім чынам, давайце замест гэтага глядзець у адным які быў папярэдне сфармуляваны як гэта з не кропка, кропка, кропкі, але толькі скарочаныя масівы. Але кожны з вузлоў ў гэтым дрэве тут уяўляе той жа thing-- Масіў Прамень памеру 26. 

Ці, калі мы хочам быць сапраўды правільнае зараз, што калі хто-то імя, як апостраф, давайце Выкажам здагадку, што кожны вузел мае фактычна як 27 індэксаў ў гэтым, а не толькі 26. Так што гэта зараз будзе дадзеных Структура называецца trie-- T-R-I-Е. Trie, які, як мяркуецца, гістарычна разумны імя для дрэва які аптымізаваны для пошук, які вядома ж, пішацца з I-Е так гэта Trie. Але гэта гісторыя сінтаксічнага дрэва. 

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

Таму што нават пры тым, што, на дадзены момант, я толькі з дапамогай паказальніка Д і І V і Es і Ns, Я марнаваць чартоўску шмат памяці. Але дзе я праводжу адзін рэсурс, Я, як правіла, нічога атрымаць таму іншы. Так што, калі я марную больш месца, што, верагодна, надзея? Гэта я марную менш чым? АЎДЫТОРЫЯ: Менш часу. DAVID Малання: Час. Цяпер, чаму гэта можа быць? Ну, тое, што з'яўляецца ўстаўка час, з пункту гледжання вялікі O цяпер, імя, як Daven або Дэвенпорт або Дэвід? Ну, Daven было пяць крокаў. Дэвенпорт будзе дзевяць крокаў, так што было б некалькі крокаў. Дэвід будзе пяць крокаў, а таксама. Так што тыя, канкрэтныя нумары, але, безумоўна, ёсць верхняя мяжа Даўжыня чыё-то імя. І сапраўды, у задачы наборы пяці спецыфікацыі, мы збіраемся прапанаваць што гэта нешта гэта 40-некаторыя з лішнім персанажаў. 

Рэальна, ніхто не мае бясконца доўгае імя, які павінен сказаць, што даўжыня назваць або даўжыня радка мы маглі б ёсць пэўная стан Структура, магчыма, што? Гэта пастаянная. Ці не так? Гэта можа быць вялікі пастаяннай, як 40-тое, але гэта канстанта. І гэта не мае ніякага залежнасць ад таго, колькі іншыя назвы з'яўляюцца ў гэтай структуры дадзеных. Іншымі словамі, калі I хацеў зараз ўставіць Колтон або Габрыэль або Роб або Zamyla або Элісан або Белинда або любыя іншыя імёны ад персаналу ў гэтых дадзеных Структура, з'яўляецца час працы ўстаўкі і іншыя назвы будзе наогул ўплыў па тым, як і многія іншыя элементы з'яўляюцца ў структуры дадзеных, ужо? Гэта не так. Ці не так? Таму што мы эфектыўна выкарыстоўваць гэта шматслаёвая хэш-табліцы. І час працы любы з гэтых аперацый залежыць не ад колькасці элементы, якія ў структуры дадзеных або што ў канчатковым выніку адбываецца каб быць у структуры дадзеных, але па даўжыні, што канкрэтна? 

Радок быць устаўлены, які робіць гэта асімптатычна пастаянным time-- вялікі O аднаго. І, шчыра кажучы, проста ў рэальны свет, гэта азначае ўстаўкі назву Daven бярэ як пяць крокаў, або Дэвенпорт дзевяць крокі, або Дэвід пяць крокаў. Гэта па-чартоўску маленькія раз хадавыя. І, сапраўды, гэта вельмі добрая рэч, асабліва калі гэта не залежыць ад агульнай Колькасць элементаў у там. Так як мы можам гэта рэалізаваць Такая структура ў кодзе? Гэта крыху больш, Комплекс, але ўсё-такі гэта толькі ўжыванне асноўныя будаўнічыя блокі. Я збіраюся перагледзець нам вузел наступным чынам: Ьоо называецца word-- і гэта можна было б назваць што-небудзь. Але Ьоо ўяўляе тое, што я звярнуў як галачкай. Так. Гэта канец радка У гэтай структуры дадзеных. 

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

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

Цяпер Meanwhile-- О, пытанне. 

АЎДЫТОРЫЯ: Што Ьоо слова? 

DAVID Малання: Bool слова проста гэта C ўвасабленне з таго, што я апісаў у гэтым полі тут, калі Я пачаў падзелу кожнай з элементы масіва на дзве часткі. Адным з іх з'яўляецца паказальнікам на наступны вузел. Іншы павінен быць нешта накшталт сцяжка сказаць так, ёсць Слова Daven што тут сканчаецца, таму што мы не хочам, на дадзены момант, Дэйв. 

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

Любыя іншыя пытанні аб спробах? Так. 

АЎДЫТОРЫЯ: Што такое перакрыцце? Што рабіць, калі ў вас ёсць Дэйва і Daven? DAVID Малання: Выдатна. Што рабіць, калі ў вас ёсць Дэйва і Daven? Так што, калі мы ўстаўляем, кажуць мянушку, для David-- Dave-- D-A-V-E? На самай справе гэта супер проста. Такім чынам, мы толькі збіраемся распачаць чатыры кроку. Д-А-В-Е. І тое, што мне трэба зрабіць, як толькі я стукнуў, што чацвёрты вузел? Проста збіраюся праверыць. Мы ўжо добра ісці. Гатова. Чатыры кроку. Пастаяннае час асімптатычна. І зараз мы паказалі, што абодва Dave і Daven з'яўляюцца радкамі ў структуры. Так не праблема. І звярніце ўвагу, як прысутнасць з Daven не зрабіць гэта ўзяць больш часу або менш Час для Дэйва, і наадварот. 

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

І ў гэтым тыпе структуры дадзеных ў вас ёсць два operations-- ў вас ёсць адзін пад назвай штуршок для дадаючы што-то ў стэк, як пакласці яшчэ адзін латок Вярнуўшыся на вяршыні стэка. І тады поп, які азначае, што вы ўзяць верхні оф латка. Але тое, што ключ аб стэка з'яўляецца тое, што ён атрымаў гэтую цікавую характарыстыку. Як сталовай персаналу перастаўляючы латкі для наступнага прыёму ежы, што будзе праўда пра тое, як студэнты ўзаемадзейнічаць з гэтай структурай дадзеных? АЎДЫТОРЫЯ: Яны збіраюцца поп прэч. DAVID Малання: Яны збіраюцца поп прэч, мы спадзяемся на вяршыню. У адваротным выпадку гэта проста нейкая дурная каб прайсці ўвесь шлях да дна. Ці не так? Структура дадзеных на самай справе не дазваляюць Вы, каб захапіць ніжнюю латок, па меншай меры лёгка. Так што гэта цікава Ўласцівасць да стэку што апошні элемент у гэта будзе першым з. І кампутарныя навукоўцы называюць гэта LIFO-- апошнім прыйшоў, першым выйшаў. І гэта на самай справе ёсць цікавыя прыкладання. Гэта не абавязкова так відавочна, як некаторыя і іншыя, але ён можа, вядома, быць карысным, і яно можа, на самай справе, быць рэалізаваны праз пару-рознаму. 

Так што, і на самой справе, хай мне не ныраць у тым, што. Давайце зробім гэта замест гэтага. Давайце паглядзім на той, які амаль Тая ж ідэя, але гэта крыху больш справядлівым. Ці не так? Калі вы адзін з гэтых хлопчыкаў вентылятараў або дзяўчынкі, што сапраўды любіць прадукты кампаніі Apple і вы прачнуліся у 3:00 выбудоўвацца ў нейкую краму каб атрымаць самую апошнюю iPhone, вы магчыма, у чарзе, як гэта. 

Цяпер чарга вельмі свядома назваў. Гэта лінія, таму што ёсць некаторыя справядлівасць да яго. Ці не так? Было б выгляд смактаў калі ў вас ёсць атрымаў там першы ў Apple Store але вы эфектыўна ніжні Латок, таму што супрацоўнікі Apple, затым поп апошні чалавек, які на самай справе трапіў у лінію. Так стэкаў і чэргаў, хоць функцыянальна яны накшталт ў same-- гэта проста гэтая калекцыя рэсурсаў, што гэта будзе расці і shrink-- там Гэты аспект справядлівасці да яго, па меншай меры, у рэальным свеце, дзе аперацыі вы трэніруецеся прынцыпова адрозніваюцца. Stack-- чарзе rather--, як кажуць, дзве аперацыі: чэргі н і чэргаў d. Ці вы можаце патэлефанаваць ім любую колькасць рэчаў. Але вы проста хочаце, каб захапіць паняцце, што чалавек дадання і, у канчатковым рахунку адзін аднімання. 

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

АЎДЫТОРЫЯ: Чарга. DAVID Малання: Ну, чэргі. Вядома. Што яшчэ? 

АЎДЫТОРЫЯ: звязаны спіс. 

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

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

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

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

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

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

АЎДЫТОРЫЯ: Невялікія тыя, што злева. 

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

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

У адваротным выпадку, калі п менш Дрэва стрэлкі N-- цяпер стрэлка н, Нагадаем, мы ўвялі супер коратка на днях, і гэта проста азначае, дэ-спасылку на ўказальнік і паглядзець на месцы, якое называецца н. Дык гэта значыць, пайсці туды і паглядзець на полі пад назвай п. Так што, калі п, значэнне вы далі, менш чым значэнне ў цэлы лік дрэў, дзе вы хочаце пайсці? Налева. 

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

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

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

Як мы begin-- шчасце вы маглі б think-- наш пераход павольна са свету C і ніжэй Дэталі рэалізацыі ўзроўню, ў свеце, у якім мы можам узяць для разумеюцца, што хто-то нарэшце- рэалізаваны гэтыя дадзеныя збудаванні для нас, і мы пачнем разумець, Рэальны свет азначае рэалізацыі праграмы вэб-аснове і сайты ў больш агульным а таксама вельмі бяспекі Наступствы, якія мы толькі пачалі драпаць паверхню. Вось што нас чакае у бліжэйшыя дні. 

[ВИДЕОВОСПРОИЗВЕДЕНИЕ] 

-Ён Прыйшоў з паведамленнем, з пратаколам усё сваё. Ён прыйшоў у свет жорсткі брандмаўэр, незаботливым маршрутызатары, і небяспекі значна горш, чым смерць. Ён хутка. Ён моцны. Ён TCP / IP, і ў яго ёсць свой адрас. «Воіны Сеткі". [END ВИДЕОВОСПРОИЗВЕДЕНИЕ] DAVID Малання: Coming наступным тыдні. Мы будзем бачыць вас тады. [ВИДЕОВОСПРОИЗВЕДЕНИЕ] -А Зараз, "Глыбокія думкі" па Daven Фарнэме. Дэвід заўсёды пачынаецца лекцыі з "Добра". Чаму не "Вось рашэнне на гэтым тыдні праблемы набору " або "Мы даем ўсе вы?" [Смяецца] [END ВИДЕОВОСПРОИЗВЕДЕНИЕ]