DAVID малая: Добра. Сардэчна запрашаем назад у CS50. Гэта пачатак 8-га тыдня. І нагадаць, што праблема набору 5 скончыўся з трохі складанай задачай. Так што калі вы аднавіць усе вашыя навучання стыпендыятаў і фатаграфіі СА у файле card.raw, Вы маеце права Зараз, каб знайсці ўсе гэтыя людзі, і адзін шчаслівы пераможца будзе хадзіць дадому з адным з гэтых рэчаў, скачок руху прылада, якое можна выкарыстоўваць для канчатковай праектаў, напрыклад. Гэта, кожны год прыводзіць да трохі жудасны. І так, што я думаў, што зрабіць, гэта падзяліцца з вамі некаторымі з нот, якія маюць туды і назад на працягу штатны расклад позна. Напрыклад, толькі ўчора ўвечары, цытаты канец цытаты, ад аднаго з персаналу Члены "Я проста быў студэнт стук у мяне ў дом, каб зрабіць здымак са мной. Сталкеры, скажу я вам. "Пачаўся дастатковым апісаннем, а затым мы пераехалі на, гадзіну ці крыху пазней, "У мяне было студэнт чакае мяне пасля падзелу і ў яго былі ўсе нашы імёны і фатаграфіі на некалькі лістоў паперы. "Добра. Так арганізавана, але не усё, што жудаснае яшчэ. Затым: "Я быў за горадам, у гэтыя выхадныя, і калі я вярнуўся, было адзін у маё спальню. "[смяецца] DAVID малая: Наступная цытата з персаналу карыстальніка ", студэнт прыйшоў да мяне дадому на Сомервилла ў 4 раніцы сёння раніцай. "Далей персаналу ", я дабраўся да гасцініцы ў Сан- Францыска і студэнт чакаў мяне ў лобі з трыма зеркалок ". Тып камеры. "Я нават не на персанал у гэтым семестры, але студэнт уварваўся ў мой дом гэта раніцай і запісаў усё гэта са шклом Google. "І тады, нарэшце, "Па крайняй меры 12 чалавек былі з нецярпеннем чакае мяне, калі я выйшаў з свайго лімузіна, а потым я прачнуўся. "Добра. Так што сярод фатаграфій, як вы Нагадаем, што ў гэты хлопец тут, хто вы маглі б ведаць, як Міла банан, які жыве з Ларэн Карвалью, нашы галовы выкладанні Fellow. Міла, Міла, ідзі сюды хлопчык. Майл. Майл. Майце на ўвазе, што ён носіць Google шкла, так што мы пакажам вам усё гэта пасля. Так што гэта Міла, калі вы хацелі б сфатаграфавацца з ім пазней. Калі вы хочаце, каб выглядваць на аўдыторыю там. ОК. Гэта добрыя кадры. Ну, Міла банан. О, не рабіце гэтага. [Смяецца] ОК. Так слова, то пра тое, што чакае наперадзе, таму што, як мы пачынаем пераход, На гэтым тыдні У прыватнасці, з С у каманднага радка асяроддзя і PHP JavaScript і SQL і HTML і CSS у вэб-асяроддзі, мы будзем аснашчэння вам усё больш ведаў для патэнцыйных канчатковага праектаў. З гэтай мэтай, вядома, мае Традыцыя правядзення семінараў, якія знаходзяцца на тангенцыйным тэмы да курсу. Вельмі, звязаных з праграмаваннем і распрацоўкі прыкладанняў і гэтак далей, але не абавязкова вывучаны ўласнай курсу вучэбнай праграме. Так што калі вы маглі б быць зацікаўлены ў адным або некалькі семінараў у гэтым годзе, зарэгістравацца на cs50.net/seminar. Ёсць старэйшы семінары на cs50.net/seminars. І ў рэестр да гэтага часу ў гэтым годзе Цудоўныя вэб-прыкладанняў з Рубінам на Рэйкі, які з'яўляецца альтэрнатывай мовы PHP. Кампутарная лінгвістыка. Увядзенне ў IOS, якая з'яўляецца платформе, якая выкарыстоўваецца для iPhone і Ipad развіцця. JavaScript для вэб-прыкладанняў, мы разгледзім , Але ў гэтым семінары, вы пяройдзеце больш падрабязна. Скачок руху, так што мы на самай справе ёсць нашых сяброў з Leap руху, самой кампаніі, далучайцеся да нас. Заўтра, па сутнасці, забяспечыць практычны семінар, калі прадстаўляць цікавасць для Вас. Meteor.js, альтэрнатыўны прыём Выкарыстанне JavaScript не ў браўзэры, а на серверы. Node.js, які вельмі у тым жа духу, а таксама. Гладкі дызайн Android. Android Будучы вельмі папулярным альтэрнатыўным Тэлефон для IOS і Windows і іншых мабільных платформаў. І вэб актыўнай абароне. Такім чынам, на самай справе, калі вы хочаце прыняць удзел у гэтым, дазвольце мне зрабіць гэта да ведама. Мы вельмі рады паведаміць, што нашы сябры ў Leap Рух, які з'яўляецца запуск - гэта прылада сапраўды проста прыйшоў з некалькі месяцаў таму - ласкава ахвяраваў 30 такіх прылад класу столькі студэнтаў, калі Вы хацелі б пазычаць апаратных да канца семестра і выкарыстоўваць яго для фактычнага канчатковага праекта. Яны падтрымліваюць некалькі моў. Ніхто з іх не C, ні адзін з іх PHP, так рэалізаваць адзін або некалькі з гэтых семінары можа апынуцца інтарэсаў. І ўсе яны будуць знятыя ў тым выпадку, калі вы не ў стане асабіста прысутнічаць на пасяджэнні. Расклад будзе абвешчана праз электроннай пошты, як мы ўмацаваць нумароў. І, нарэшце, калі вы ідзяце ў projects.cs.50.net, гэта вэб-сайт мы падтрымліваем кожны год, што мы запрашаем Людзі з супольнасці, выкладчыкаў ведамстваў, персаналу, і абедзве ў межах CS50 да прапанаваць праектныя ідэі. Рэчы, якія прадстаўляюць інтарэс для студэнцкіх груп. Рэчы, якія прадстаўляюць інтарэс для аддзелаў. Так што сваю чаргу, значыць, калі вы змагаецеся з нявызначанасцю адносна таго, што вы самі хацелі б заняцца. Так, апошні раз мы ўвялі магчыма больш складаную структуру дадзеных, чым мы бачылі ў мінулыя тыдні. Мы былі даволі выкарыстанні масіваў шчасліва, як карысна, калі спрошчаныя структуры дадзеных. Тады мы ўвялі гэтыя, якія Вядома гэта сувязныя спісы. І тое, што было адным з матываў для ўвядзення гэтай структуры дадзеных? Да? Што гэта? АЎДЫТОРЫЯ: дынамічныя памеры. DAVID малая: дынамічныя памеры. Так у той час як у масіве, вы павінны ведаю яго памер загадзя, калі Вы перадаць яго. У звязаным спісе, вы не павінны ведаць, што. Вы можаце проста Malloc ці, больш агульна, вылучыць дадаткова вузла, так бы мовіць, у любы час вы ўставіць дадатковыя дадзеныя. І не вузел без папярэдне сэнс. Гэта ўсяго толькі агульны тэрмін, які апісвае свайго роду кантэйнер, які мы выкарыстанне ў нашай структура дадзеных для захоўвання некаторы пункт цікавасці, які ў гэтым выпадку, аказваецца, цэлых лікаў. Але заўсёды ёсць кампраміс. Такім чынам, мы атрымліваем дынамічныя памеры дадзеных структуры, але якую цану мы плацім? Чым недахоп звязаных спісаў? Да? АЎДЫТОРЫЯ: патрабуецца больш памяці. DAVID малая: яна патрабуе больш памяці, як менавіта? АЎДЫТОРЫЯ: [неразборліва]. DAVID малая: Цалкам дакладна. Так што цяпер мы паказальнікаў займаючы дадатковую памяць, што мы раней не патрэбныя, таму што перавага масіва, вядома, з'яўляецца тое, што усё ў сумежных, спіны каб спіна да спіны, якая дае адвольным доступам. Таму што толькі з дапамогай квадратных дужак абазначэння, або больш тэхнічна паказальнік арыфметыка, вельмі простая таго, Вы можаце атрымаць доступ да любога элементаў у пастаяннае час. І на самай справе, гэта свайго роду намёк на іншая цана, якую мы плацім з звязаны спіс. Што адбываецца з час працы нешта накшталт пошуку, калі я хачу Прывядзіце прыклад і ўнутры звязанага спісу? Што значыць мой час працы стаў? Big O н. Калі ён сартуецца? Што рабіць, калі структура дадзеных разбіраюцца? Ці магу я зрабіць лепш, чым вялікія Аб п для пошуку? Не, таму што ў горшым выпадку ён можа вельмі добра быць адсартаваныя, але колькасць Вы шукаеце можа быць вялікім. Гэта можа быць нумар 100, якая можа здарыцца, што ўсе шляху ў канцы. І таму што вы можаце атрымаць доступ толькі да звязаным Спіс у гэтым ажыццяўленнем шляхі яе першы вузел, ты ўсё яшчэ збольшага не пашэнціла. Вы павінны прайсці ўсе гэта ад першага да апошняга, каб знайсці што вялікае значэнне, як 100. Альбо вызначыць, калі гэта нават не было. Таму мы не можам рабіць тое, што алгарытм ў дадзеных структуру, якая выглядае наступным? Мы не можам зрабіць бінарны пошук, таму што бінарны пошук патрабуе, каб у нас былі адвольным доступам. Мы маглі б проста скокнуць з месца на месцы без наступнай гэтыя хлебныя дробкі ў выглядзе ўсіх гэтых паказальнікаў. Цяпер, як мы ажыццявіць гэта? Ну, калі мы ідзем на экран пры гэтым, калі мы можам хутка перавызначыць гэтыя дадзеныя Структура - мой почырк не ўсё, што выдатная тут, але мы паспрабуем. Так ЬурейеЕ структуры, і што я хачу, каб гэтая рэч тут? Node. Так што я буду прыступіць да нас. А цяпер, тое, што павінна быць унутры Структура дадзеных для гэтага асобна звязаны спіс? Колькі палёў? Так два. Адзін з іх даволі лёгка. Так Int N. І мы маглі б назваць N, што мы хочам, але яна павінна быць цэлалікавай калі мы рэалізацыі звязанага спісу для цэлых лікаў. А цяпер што ж другі палі павінны быць? Struct вузла *. Таму, калі я структуру вузла *, а потым я можна назваць гэта таксама тое, што хачу, але толькі быць ясна, што я буду называць яго побач, як мы рабілі. І тады я зачыню фігурныя дужкі. І цяпер, як у мінулы раз, Я паклаў вузел тут. Але калі я абвяшчаю гэта як вузла, чаму я турбаваць быць такім падрабязны тут ў аб'яве структуры * Наступны вузел, у адрозненне проста вузел * наступны? Да? АЎДЫТОРЫЯ: [неразборліва]. DAVID малая: Цалкам дакладна. Менавіта так. Паколькі C сапраўды прывядзе вас у прамым і бачыць толькі вызначэнне вузла шляху сюды, вы не можаце спасылацца на яго тут. Такім чынам, мы маем такую ​​пераважнага Аб'яву тут, якія па агульным прызнанні больш падрабязны. Struct вузел, гэта значыць зараз мы можам атрымаць доступ да яго ўнутранай структуры дадзеных. І, як у баку, таму што гэта становіцца крыху больш суб'ектыўны зараз, зоркі тэхнічна можа пайсці сюды, ён можа пайсці тут, ён можа нават пайсці ў сярэдзіне. Мы прынялі, у стылі кіраўніцтва для Вядома, Канвенцыя здачы зоркі побач з дадзенымі тып, які ў дадзеным выпадку будзе структура вузла. Але зразумейце, у многіх падручніках і онлайн спасылкі, вы, магчыма, сапраўды убачыць яго на другім баку. Але гэтак жа, як разумеюць, што будзе на самой справе працаваць, і вы павінны быць проста паслядоўным. Добра. Так, каб было наша заяву з структуры вузла. Затым мы пачалі рабіць больш складаныя рэчы. Напрыклад, мы вырашылі ўвесці нешта накшталт хэш-табліцы. Дык вось хэш-табліцу памерам N, індэксуецца ад 0 у левым верхнім куце, каб н мінус 1 у левым ніжнім куце. Гэта можа быць хэш табліца на ўсё. Але якія рэчы мы размаўлялі аб выкарыстанні хэш-табліцу для? Захоўванне Што? Імёны. Мы маглі б зрабіць імёны, як мы зрабілі ў мінулы раз. І на самай справе, вы можаце захоўваць усё што заўгодна. І мы ўбачым гэта зноў PHP і JavaScript. Хэш-табліцы з'яўляецца добрым роду швейцарскіх Армейскі нож, што дазваляе захоўваць амаль усё, што вы хочаце ўнутры , Звязваючы яго са значэннямі ключоў. Ключы з каштоўнасцямі. Зараз у гэтым простым выпадку, нашы Ключы проста лічбы. Мы рэалізацыі хэш табліцы ў выглядзе масіва. І так ключы 0, 1, 2, і гэтак далей. І таму мы, як людзі, вырашыў у мінулым тыдня, што вы ведаеце, што, калі мы збіраецеся захоўваць імёны, давайце проста адвольна, але даволі разумна, Выкажам здагадку, што Аліса, імя, проста быць праіндэксаваныя на 0. І Боб, імя B, будуць індэксавацца у 1, і гэтак далей. Так у нас было адпаведнасць паміж ўваходамі, якія з'яўляюцца радкамі, і хэш месцах, якія з'яўляюцца лікамі. Такім чынам, гэты працэс звычайна называюць хэш-функцыі, і вы сапраўды можаце рэалізаваць яго ў кодзе. Калі б я хацеў рэалізаваць хэш-функцыі , Які робіць менавіта тое, што мы толькі што апісаў у мінулы раз, я мог бы абвясціць функцыю, якая прымае ў якасці уваходнага напрыклад - і давайце зробім гэта на гэтым Экран тут. Калі б я хацеў рэалізаваць хэш Функцыя, я мог бы сказаць нешта накшталт гэтага. Гэта збіраецца вярнуцца Int. Гэта будзе называцца хэш, і гэта збіраецца прыняць у якасці аргументу радок, ці мы можам быць больш належнага зараз, і сказаць, сімвал *, мы будзем называць яго з. І тады ўся гэтая функцыя павінна рабіць, У канчатковым рахунку, гэта вярнуць Int. Зараз, як ён гэта робіць, што можа Калi б не было так ясна. Я збіраюся рэалізаваць гэта без любога форма праверкі памылак прама цяпер. Я проста збіраюся слепа сказаць, вярнуцца што ёсць пад кранштэйн з 0, мінус, скажам, у сталіцы коскі. Цалкам парушаная. Гэта не ідэальна, таму што Адзін з іх, што, калі з з'яўляецца несапраўдным? Дрэнныя рэчы будуць адбывацца. Два, што, калі першая літара ў гэтым імя не літары? Гэта не збіраецца ператварыць з добра таксама. Гэта можа быць малой літары ці не ліст наогул. Так цалкам магчымасці для паляпшэння, але гэта асноўная ідэя. Тое, што мы на мінулым тыдні апісаў вуснай форме проста працэс карціравання Аліса 0 і Боба 1 могуць быць выяўленыя вядома, больш formulaically як C Тут дзейнічаюць. Зайшоў яшчэ хэш, прымае радок як ўвод, а затым нейкім чынам робіць нешта з гэтага ўваходу для атрымання выхаднога. Не ў адрозненне ад нашага чорнага поле Апісанне што мы даўно зрабілі. Я не ведаю, як гэта магло б быць работ пад капотам. Для задачы набор 6, адна з праблем, для вас, каб вырашыць, што Ці будзе ваш хэш-функцыя можа быць? Што будзе ўнутры гэтага чорнага рамкі, і, як мяркуецца, гэта будзе трохі больш цікава, чым гэта, і безумоўна, больш схільныя да памылак праверак, чым дадзены ажыццяўленне. Але могуць узнікнуць праблемы, ці не так? Калі ёсць структура дадзеных, такіх як гэта Адзін з іх, што адна з праблем вы можаце сутыкнуцца з цягам часу, як вы ўстаўляеце усё больш і больш імёнаў у хэш-табліцы? Вы атрымліваеце сутыкненняў, ці не так? Што рабіць, калі ў вас ёсць Аліса і Аарон, два чалавекі, імёны якіх адбылося пачаць з? То ўзнікае пытанне, дзе вы пакласці другі такую ​​назву? Ну, вы можаце наіўна проста пакласці яго дзе Боб належыць, але потым Боб віды разьбовых, калі вы паспрабуеце ўставіць яго імя побач і там няма месца для яго. Так што вы можаце пакласці Боб дзе Чарлі, і вы можаце сабе ўявіць, гэта вельмі хутка ўскладзеных ў трохі беспарадак. Нешта лінейнай у рэшце рэшт, дзе вы проста прыйдзецца шукаць усё гэта шукае Алісу або Боба або Аарона або Чарлі. Так замест гэтага мы прапанавалі, а не проста лінейна зандзіравання для адкрытых прастор і шлёп імёны там, мы прапанаваў незвычайны падыход. Хэш-табліцы па-ранейшаму ажыццяўляцца з масіў індэксаў, але тып дадзеных Цяпер гэтыя паказчыкі былі паказальнікі. Паказальнікі на што? Паказальнікі на звязаныя спісы. Таму нагадаем, што звязаны спіс сапраўды толькі паказальнік на вузел і вузел мае наступнае поле, і вузел мае наступнае поле, і гэтак далей. Так што вы можаце думаць аб гэтым масіве на левай баку хэш-табліцу ў якасці вядучыя на звязаны спіс. Перавага які, калі вы атрымаеце сутыкненні паміж Алісай і Аарон, што вы будзеце рабіць з другога такога чалавека? Вы проста прымацаваць яго ці яе канцы, ці нават пачатак гэтага звязаны спіс. А на самай справе, давайце проста локшыны праз , Што толькі на адну секунду. Дзе б лепш за ўсё падыходзяць? Калі я ўстаўляю Аліса і яна заканчваецца на першага месца, то я імкнуся ўставіць імя Аарона, і ёсць Відавочна, сутыкненні, я павінен пакласці яго ў пачатку звязанага спісу? Вось на гэтым першым месцы, ці ў канцы? АЎДЫТОРЫЯ: [неразборліва]. DAVID малая: OK. Я чуў пачынаецца. Чаму ў самым пачатку? АЎДЫТОРЫЯ: [неразборліва]. DAVID малая: OK. Гэта алфавітны, так што гэта добра. Гэта добры уласнасці. Гэта зэканоміць мне некаторы час патэнцыйна. Яна не дазволіць мне зрабіць бінарны пошук, але я можа па крайняй меры быць у стане вырвацца з з цыкла, калі я разумею, ну, я дарэчы Аарон мінулым былі б у такім адсартаваны звязаны спіс. Я не прыйдзецца марнаваць свой час, гледзячы ўвесь шлях да канца. Так, што гэта разумна. Чаму яшчэ можа вы хочаце ўставіць сутыкаюцца імя ў пачатак спісу? Што гэта? АЎДЫТОРЫЯ: [неразборліва]. DAVID малая: Гэта можа заняць шмат часу, каб атрымаць у канцы спісу. І на самай справе, больш і больш. Чым больш імёнаў, што вы ўстаўляеце пачаць з, тым больш, што Ланцуг збіраецеся атрымаць. Чым даўжэй, што звязана Спіс збіраецеся атрымаць. Значыць, вы сапраўды проста марнуеце свой час. Можа быць, вам лепш падтрыманне пастаянны час ўстаўкі, Big O 1, , Заўсёды паклаўшы сутыкаюцца на імя пачатку звязанага спісу, а не турбавацца столькі аб сартаванні. Які самы лепшы адказ? Незразумела. Гэта збольшага залежыць ад таго, размеркаванне, што карціна з імёнаў вы ўстаўляеце. Гэта не абавязкова Відавочны адказ. Але вось, зноў жа, Дызайн магчымасць. Такім чынам, мы тады глядзелі на гэтую рэч, якая сапраўды іншыя вялікія магчымасці для р-набор 6. І зразумейце, калі вы яшчэ не зрабілі, Zamyla нырае ў абодва гэтыя, хэш табліц і спроб, больш падрабязна. І відэа пакрокавае кіраўніцтва убудаваныя ў р-набор спец. Гэта было сінтаксічнага дрэва - Т-Р-І-Е. І тое, што было цікава гэта было, што час працы пошуку імя, як Максвел у мінулы раз, было вялікім O чаго? Што гэта? Аўдыторыі: колькасць літар. DAVID малая: Колькасць літар. Я чуў пра дзве рэчы. Колькасць лістоў і пастаяннае час. Так што давайце ісці з гэтым у першую чаргу. Колькасць літар. Ну, гэтая структура дадзеных, нагадаем, з'яўляецца як дрэва, генеалагічнае дрэва, кожная з вузлы якога складаюцца з масіваў. А тыя масівы паказальнікаў на іншых падобных вузлоў ці іншых падобных масіваў у дрэве. Так што, калі мы хацелі затым вызначыць Ці Максвел знаходзіцца тут, я мог бы пайсці у першым масіве, на самым версе дрэва, так званы корань, верхняй частцы дрэва, а затым ісці за паказальнікам м, Затым паказальнік, то х, W, E, L, L. А потым, калі я бачу некаторыя спецыяльныя сімвалы, пазначаецца тут як трохкутнік. У кодзе вы ўбачыце, што мы прапануем Вам рэалізаваны як лагічны, проста кажу, што так ці не, слова заканчваецца. Ну, раз мы пайшлі ў M-A-X-W-E-L-L, адчувае, як сем, можа быць, восем, калі мы зробім яшчэ адзін міма яго, восем крокі, каб знайсці Максвелла. Ці назавем яго К. Але ўспомнім апошні час, я сцвярджаў, што, калі ёсць рэальна максімальнай даўжынёй па Словам, як 40 з лішнім персанажаў, Максімальная даўжыня мае на ўвазе пастаяннае значэнне. Так на самай справе, так, гэта тэхнічна Big O 8 ці 7, або сапраўды вялікі O К. Але калі ёсць канчатковая вечка на тое, што K можа быць, гэта канстанта. І так гэта вялікае Аб ад 1 на канцы дня. Не ў рэальным свеце. Не тады, калі вы на самой справе пачаць глядзець вашыя гадзіны, як працуе ваша праграмы. Гэта абсалютна будзе трохі павольней, чым сапраўды пастаяннай Час з аднаго кроку. Гэта будзе сем ці восем крокаў, але ўсё ж гэта значна, значна лепш , Чым алгарытм, як Big O п, што залежыць ад памеру таго, што ў структуры дадзеных. Звярніце ўвагу на уверх тут мы можам ўставіць яшчэ мільён імёнаў у гэтай Структура дадзеных, але колькі яшчэ крокаў ён збіраецца ўзяць нас знайсці Максвел ў такім выпадку? Ні адзін. Ён не ўплывае. І на сённяшні дзень, я не думаю, што мы бачылі Прыклад структуры дадзеных, альбо Алгарытм, які быў цалкам не залежыць ад знешніх паводзін, як, што. Але гэта не можа быць дзіўным. Гэта не можа быць адзіным рашэннем для р-набор І гэта не так. Гэта не абавязкова дадзеныя структуру вы павінны імкнуцца да, таму што, як хэш-табліцы, кампраміс. Якой цаной вы плаціце тут? Памяці. Я маю на ўвазе, гэта зверскае аб'ём памяці. І вы не можаце досыць убачыць яго тут, таму што Аўтар гэтага здымка Відавочна, ўсечаны ўсіх масіваў і мы не бачым шмат і B і C і Q і Y ў і Z у гэтых масівах. Але яны там. Кожны з гэтых вузлоў цэлы шэраг ад каля 26 ці больш байтаў, кожны з якая ўяўляе сабой літару. 27 у нашым выпадку, так што мы можам падтрымаць апострафа ў задачы набору. Так што гэтая структура дадзеных сапраўды, сапраўды шчыльная і шырокая. І ўжо адно гэта можа ў канчатковым выніку запаволенне рэчы ўніз, або па крайняй меры каштаваць вам нашмат больш месца. Але, зноў жа, можна зрабіць параўнання тут. Нагадаем, некаторы час таму, мы дабіліся многага больш за захапляльнае час працы ў сартаванні калі мы выкарыстоўваем сартавання зліццём, але кошт мы заплацілі, каб дасягнуць N § п аб зліцці Сартаваць патрабуе, каб мы трацім больш, што рэсурс? Больш месца. Мы мелі патрэбу ў масіў другасных скапіяваць людзей у, гэтак жа, як мы зрабілі тут на сцэне. Такім чынам, яшчэ раз, няма відавочных пераможцаў, але проста суб'ектыўныя дызайну прымаць рашэнні. Добра. Так як наконт гэтага? Любы прызнае якіх D-Hall? ОК. Так тры з нас. Mather дом. Так што гэта для сталовай Мазер. Б'юся аб заклад, усе залы сталовай ёсць стэкі латкі, як гэта. І гэта на самай справе прадстаўнік у тое, што мы відавочна, ужо бачылі. Мы назвалі яе літаральна стэк. І ў стэк, з пункту гледжання вашага памяці кампутара, дзе дадзеныя ідуць у той час як функцыі пры выкліку. Напрыклад, якія рэчы ідуць ў стэку ў адносінах да Разметка памяці мы абмяркоўвалі тыдняў у мінулым? Што гэта? АЎДЫТОРЫЯ: выклікі функцый. DAVID малая: Мне вельмі шкада. АЎДЫТОРЫЯ: выклікі функцый. DAVID малая: выклікі функцый, але У прыватнасці, тое, што ўнутры кожнага гэтыя кадры? Якія рэчы? Да. Так што лакальныя зменныя. У любы час мы мелі патрэбу ў некаторым лакальным сховішча, як аргумент, або INT I, або дзесятковага Temp, або любы іншы мясцовы зменная, мы былі пакласці, што ў стэку. І мы называем гэта стэк, таму што гэтага напластаванні ідэя. Проста выгляд матчаў з рэальнасцю, Канцэпцыя іх. Але аказваецца, што стэк можа таксама разглядацца як структура дадзеных, Альтэрнатывай масіве, альтэрнатыўныя на звязаны спіс. Нешта канцэптуальна больш цікавым што ўсё яшчэ можа быць рэалізаваны з выкарыстаннем любой з гэтых рэчы, але гэта іншы тып Дадзеныя структуры падтрымкі, на самай справе, толькі дзве аперацыі. Але вы можаце дадаць на аматара магчымасцяў, чым гэтыя. Але гэтыя асновы - штурхаць і поп-музыкі. А ідэя са стэкам ў тым, што калі маем тут, з або без Анненберга ведаючы, паднос з суседняга дома з нумарам 9 на ім. Так што проста Int. І я хачу, каб націснуць на гэтую дадзенымі Структура, якая ў цяперашні час з'яўляецца пустым. Разгледзім у ніжняй частцы чаркі. Я б падштурхнуць гэты нумар 9 на стэк, а цяпер гэта прама там. Але самае цікавае пра стэку тым, што калі цяпер я хачу, каб падштурхнуць іншае значэнне, як і 17, і я штурхаю гэтага ў стэк, я збіраюся зрабіць толькі інтуітыўна рэч, я проста хачу, паставіць яго менавіта там, дзе мы, людзі, быў бы схільны выказаўся, на вяршыні. Але што цікава зараз у тым, як я магу атрымаць у 9? Вы ведаеце, я не без некаторага намаганні. Так што цікава стэк ў тым, што дызайн, гэта структура дадзеных ЛИФО. Дурны спосаб апісання апошні ўвайшоў, першы выйшаў. Такім чынам, апошняе чысло ў ў гэты час было 17 гадоў. Так што, калі я хачу што-то ад поп чаркі, ён можа быць толькі 17. Такім чынам, ёсць абавязковы парадак аперацый тут, дзе апошні элемент У павінен быць першым аднаго з іх. Такім чынам акронім, LIFO. Дык чаму гэта магло б быць карысным? Ці з'яўляюцца іх кантэксту, у якім трэба хочуць структуру дадзеных, як гэта? Ну, гэта, безумоўна, карысна ўнутры кампутара. Так аперацыйных сістэм выразна выкарыстоўваць гэтую выгляд структуры дадзеных для стэкаў. Мы таксама ўбачым тую ж ідэю калі справа даходзіць да вэб-старонак. Так на гэтым тыдні і на наступным тыдні і за яе межамі, і, як вы прыступіць да рэалізацыі вэб- старонак на мове, званым HTML, Вы можаце фактычна выкарыстоўваць структуру дадзеных, як гэта вызначыць, ці з'яўляецца старонка правільна адфарматаваны. Таму што мы ўбачым ўсё вэб-старонкі варта свайго роду іерархію, водступы які, у рэшце рэшт, быць дрэвападобнай структуры пад капотам. Так пра гэта крыху пазней. Але цяпер, давайце прапаноўваць для моманту, як мы маглі б ісці аб прадстаўляюць, што стэк? Дазвольце мне прапанаваць, каб мы ажыццявілі стэк з такой код. Так стэк будзе мець ўнутры яго дзве рэчы, масіў, званы паддоны проста каб быць у адпаведнасці з дэма. І кожны з элементаў у гэтым масіве будзе тыпу Int. І магутнасці, па-відаць, што? Таму што я не напісаў Поўнае вызначэнне тут. Гэта, мабыць, максімальна памер масіва. І гэта, верагодна, абвешчаны як рэзкае вызначаюць у верхняй часткі файла, некаторыя выгляд пастаяннай, як вынікае з проста капіталізацыі. Такім чынам, дзесьці магутнасць вызначаецца ў якасці максімальнага памеру. Між тым, усярэдзіне структуры дадзеных вядомага як стэк там будзе быць цэлым лікам толькі вядомыя проста як памер. Так што, калі б я павінен быў прадставіць гэта цяпер графічна, давайце выкажам здагадку, што гэта увесь чорны прастакутнік прадстаўляе свой стэк. Унутры гэта двума зменнымі. Так што я збіраюся зрабіць Першы, як памер. А другі я збіраюся прыцягнуць у выглядзе масіва. Але толькі, каб трымаць рэчы упорядоченно, Звычайна я хацеў бы звярнуць масіў як гэта, але гэта збольшага добра калі мы адпавядае рэчаіснасці, або адпавядае ментальнай мадэлі. Такім чынам, дазвольце мне зрабіць замест масіва вертыкальна, які знаходзіцца ўсяго, зноў жа, мастака выканання. На самай справе не важна, што гэта знаходзіцца пад капотам. І мы будзем казаць, што, па змаўчанні, магутнасць будзе тры. Так што гэта будзе размяшчэнне 0, то гэта будзе нумарам 1, гэта будзе размешчаны ў 2. Калі б я з падкупіць стрэс мяч, не так нехта хацеў, каб прыдумаць і запусціць борце тут на імгненне? Добра, бачыў вашу руку першым. Падымайся. Добра. Так што я лічу, што гэта Стывэн. Падымайся. Добра. Але выкажам здагадку, што зараз мы пераматаць на пачатковым стан свету, дзе я толькі што абвясціў стэка, і гэта будзе магутнасцю тры. Аднак памер яшчэ не вызначаны. Латкі яшчэ не быў вызначаны. Такім чынам, некалькі пытанняў у першую чаргу. І дазвольце мне даць вам мікрафон, каб вы маглі больш актыўны ўдзел у гэтым. Дык што ж знаходзіцца ўсярэдзіне памер у дадзены момант ў тэрмін, калі ўсё, што я зрабіў, заявіў стэк з аднаго радка кода? Стывен: Не так шмат. DAVID малая: Добра, не так шмат. Ці ведаем мы, што ўнутры памер, мы ведаем, што ўсярэдзіне гэтага масіва тут? Стывен: Проста выпадковы код, праўда? Проста - DAVID малая: Так, я збіраюся называюць гэта код, але выпадковых - Стывен: Рэчаў. DAVID малая: Такія рэчы, як выпадковая Стывен: біт. DAVID малая: біты, так? Так смецце значэння, праўда? Так перастаноўкі з 0 і 1 ст. Рэшткі папярэдніх выпадках выкарыстання гэтай памяці. І мы сапраўды не ведаем, якія менавіта значэнні якія, такім чынам, мы, як правіла прыцягнуць іх ў выглядзе знакаў пытання. Таму першае, што мы па-відаць збіраецца хочаце зрабіць тут - і дазвольце мне даць гэта поле ўнутры адтуль назва - латкі. Што мы павінны меркавана ініцыялізацыі памер, калі мы хочам пачаць выкарыстоўваць гэты стэк? Стывен: Латок 3 да поўдня. DAVID малая: Так, добра. Каб было ясна, магутнасцю абвешчаны ў іншым месцы, як тры. І вось што я выкарыстаў вылучыць масіва. Памер збіраецца звярнуцца да колькі Латкі дадзены момант у стэку. Стывен: Нуль. DAVID малая: Так яно і павінна быць роўна нулю. Так што наперад, і з любым пальцам, намаляваць нуля ў памерах. Добра. Так што цяпер, што ўнутры гэтага тут, мы не ведаем. Гэта сапраўды проста значэнні смецце. Так мы змаглі прыцягнуць пытальныя знакі, але Давайце трымаць савет чыстымі пакуль таму што гэта не мае значэння што там. Нам не трэба для ініцыялізацыі масіва ні да чаго, таму што, калі мы ведаем, што памер стэка роўны нулю, а мы Не варта глядзець на што-небудзь у гэты масіў ва ўсякім выпадку ў дадзены момант часу. Зараз выкажам здагадку, што я націскаю 9 чысла ў стэк. Як мы павінны абнавіць структуру дадзеных ўнутры гэтага чорнага скрыні? Якія каштоўнасці трэба змяніць? Стывен: У - памер? DAVID малая: OK. Памер павінна стаць тое, што? Стывен: памер павінен быць адзін. DAVID малая: OK. Так што памер павінен стаць адным. Такім чынам, вы можаце зрабіць гэта ў некалькі спосабаў. Дазвольце мне даць вам, цяпер ваша палец гумка. Добра. Тады зараз пальца пэндзля. Добра. А цяпер, што яшчэ павінна змяніцца, відавочна, што ў структуры дадзеных? Стывен: Мы збіраемся ад знізу ўверх да 9. DAVID малая: 9. ОК, добра. Так да гэтага часу не мае значэння, што пастаўлена на месцазнаходжанне аднаго ці двух, таму што яны смецце значэння, але мы не павінны турбавацца шукае там, таму што памер кажа нам, што толькі першы элемент на самай справе законна. Так што цяпер я націскаю на 17 спісу. Што адбываецца з гэтай карцінай? Стывен: Так памер будзе ісці да двух. DAVID малая: OK. Ты гумка - Ой. Ты гумка. Стывен: Eraser. DAVID малая: Ты пэндзля. Стывен: Brush. DAVID малая: OK. А што яшчэ? Стывен: І тады мы - DAVID малая: Мы вылучылі 17. Стывен: Мы прытрымліваемся 17 зверху, а значыць - DAVID малая: Добра, добра. Стывен: - змесціце яго ўніз. DAVID малая: Добра. Гэта становіцца лёгка. Я не збіраюся, каб дапамагчы вам у гэты раз. Націсніце 22. Стывен: Гатова. Стаць гумка. Я раблюся пэндзля. І тады я стаўлю 22. DAVID малая: 22. Выдатна. Так што яшчэ раз. Я цяпер збіраюся націснуць стэк 26. Стывен: Ох. О, чорт вазьмі. Вы сапраўды заспела мяне знянацку. DAVID малая: Вы не зрабілі гэта прадбачыць? Стывен: Я не бачыў гэтага чакаць. Ці можам мы паўторна Першапачатковая магутнасць? DAVID малая: Гэта добры пытанне. Такім чынам, у нас выгляд афарбаваныя сябе ў куце тут. Там сапраўды нічога добрага за Стывен таму што ў нас выдзелена ў гэтым масіве статычна, так бы мовіць, усярэдзіне структуры дадзеных. І мы па сутнасці жорстка гэта будзе памерам тры. Так што мы не можам вызваліць яго. Мы маглі б, калі б мы вярнуліся, мы перагледзеў латкі быць паказальнік, які затым мы выкарыстоўваем Malloc ў рукі памяці. Таму што, калі мы атрымалі ад памяці праз кучу Malloc, мы маглі б вызваліць яго. Але перад вызваленнем, мы маглі б пераразмеркаваць большы кавалак памяці, абнавіць паказальнік, і гэтак далей. Але на сённяшні дзень, гэта сапраўды што мы можам зрабіць. Націсніце і поп, як мяркуецца, збіраўся мець, каб сігналізаваць некаторыя памылкі. Так, напрыклад, наша рэалізацыя штуршок можа вярнуцца BOOL якія вернуты раней праўда, праўда, праўда. Але ў чацвёрты раз, ён будзе мець вярнуцца ілжывым, напрыклад. Добра. Вельмі добра зроблена. Віншую. Вы зарабілі свой стрэс мяч сёння. [Апладысменты] Стывен: Дзякуй. DAVID малая: Дзякуй. Такім чынам, гэта, здаецца, не так шмат з крок наперад, ці не так? Мы апісалі гэтую структуру дадзеных. Гэта было пераканаўчым, ці не так? Аперацыйныя сістэмы падабаецца. Мабыць у Інтэрнэце можа скарыстацца гэтым, і іншых прыкладанняў на месцы. Але тое, што дурныя абмежаванні, што мы вярнуцца да роду тыдні два мяжы дзе мы зафіксавалі памер масіваў. Такім чынам, ёсць сапраўды пара спосабы, якімі мы маглі б вырашыць гэтую. Мы маглі дынамічна вылучаць масіў, не цвёрдае кадаваньне гэта, як я зроблена тут, але замест паўторнага аб'явы гэта, проста каб было ясна, як нешта накшталт гэтага. Латкі Int *, не адважваючыся на працаздольнасць яшчэ. Але калі я заяўляю стэка ў іншым месцы ў маім кодзе, я мог бы назваць Malloc, атрымаць адрас кавалак памяці, і я мог прызначыць гэты адрас латкоў. І потым, таму што гэта проста кавалак памяці, я мог бы працягваць выкарыстоўваць квадратныя дужак у звычайным парадку. Таму што зноў жа, накшталт гэтага функцыянальны эквівалент масівы і ўчасткі памяці, якія прыходзяць назад ад Malloc. Мы можам ставіцца адзін, як і іншыя выкарыстаннем арыфметыкі паказальнікаў або квадратных абазначэння кранштэйна. Так што гэта адзін падыход. Але як яшчэ мы можам рэалізаваць гэтую тую ж структуру дадзеных, патэнцыйна? Дакладна? Я адчуваю, што мы проста вырашылі гэтую праблемы, як тыдзень таму. Тое, што было рашэнне гэтай праблемы што Стывен сутыкнуўся? Так звязаныя спісы, маюць рацыю. Калі праблема ў тым, што мы фарбуем сябе ў кут, вылучыўшы Загадзя занадта мала памяці, што мы тады давядзецца неяк мець справу з, ну, Чаму б проста не пазбегнуць пытанне наогул? Чаму б проста не абвясціць латкі быць паказальнік на вузел, ERGO звязаны спіс, і потым вылучыць новыя вузлы кожны раз, калі Стывен неабходныя, каб адпавядаць лік у структуру дадзеных. Такім чынам, карціна павінна змяніцца. Гэта не будзе так чыста і, як проста, як толькі масіў з трох цэлых лікаў. Цяпер гэта будзе паказальнік на структуры, і што структура збіраецца ёсць цэлалікавых і наступны паказальнік. Гэта будзе весці праз гэты паказальнік ў іншую такую ​​структуру, каб іншай такой структуры. Такім чынам, карціна была б на самой справе атрымаць крыху брудней. І мы б стрэлкі звязваючы ўсе разам. Але гэта нармальна, правільна, таму што мы бачылі, як гэта зрабіць. І як толькі вы асвоіцеся ствараеце нешта накшталт звязанага спіс, які вы павінны будзеце зрабіць, калі Вы выбраць для рэалізацыі хэш-табліцу з раздзельнае звязванне для р-набор 6, вы можаце выкарыстоўваць яго ў якасці будаўнічага блока, альбо інгрэдыента або ў драпін кажуць, працэдуры, тое, што вы паклалі, вы стварылі свой уласны кавалачак пазла , Які затым можна выкарыстоўваць паўторна. Так кампрамісы, але патэнцыйныя рашэння што мы на самай справе бачыў раней. Так даволі часта, вы бачыце гэта кожны год ці два, калі Apple выпусціла нешта новае, і ўсе вар'яты людзі лінія за межамі Apple, краму, каб купіць іх гранічныя абнавіць на абсталяванні. Я кажу пра гэта, гэта нармальна, таму што Я адзін з тых людзей. Дык якія структуры дадзеных можа прадстаўляць гэтую рэальнасць? Ну, давайце назавем гэта чарзе, лінія. Так ангельцы называюць гэта звычайна Чарга ў любым выпадку, так што гэта добрае імя. І дзве аперацыі, якія чаргу павінна падтрымліваць мы будзем называць Enqueue аперацыі і аперацыі з чаргі, якія падобныя па духу націснуць і поп-музыкі. Гэта проста як бы ў розных Канвенцыі, тое, што мы называем гэтым. Але для пастаноўкі ў чаргу нешта азначае, дадаць або ўставіць яго ў структуры дадзеных. Каб з чаргі азначае, каб выдаліць яго. Але ў той час быў стэк дадзеных LIFO структуры чэргі ў першай, першы з структуры дадзеных. Калі вы першы чалавек у чарзе, Вы будзеце першым чалавекам, каб атрымаць з лініі і купіць новае прыладу. Уявіце сабе, як засмучэнне гэтыя людзі былі б Калі Apple, замест гэтага выкарыстоўвалі стэк, для Напрыклад, для ажыццяўлення выбару да вашай новай цацкай. Так чэргаў сэнсу, вядома, і мы можам думаць аб усякіх прыкладанняў, па-відаць, для чэргаў, асабліва калі вы хочаце справядлівасці. Такім чынам, як мы маглі б рэалізаваць гэтыя у якасці структуры дадзеных? Ну, я прапаную, каб мы маглі трэба зрабіць гэта такім чынам. Так што я збіраюся зараз маюць нумары. Такім чынам, мы будзем трымаць яго простым і не абавязкова гаварыць з пункту гледжання латкоў. Проста колькасці, якія народ атрымаў. Ёмістасць збіраецца, зноў жа, выправіць агульная колькасць людзей, якія могуць быць у гэтай лініі, а тры, ці любыя іншыя значэння. Але я прапаную, што мне трэба, каб адсочваць не толькі памер Чарга, як многія рэчы ў ім. Таму памер бягучага памеру, магутнасці гэта максімальны памер. Проста яшчэ раз, намэнклятура У адпаведнасці з пагадненнем. Навошта мне патрэбен дадатковы дзесятковага ўнутры чарзе, каб адсочваць, хто знаходзіцца ў пярэдняй лініі? Чаму я павінен гэта рабіць у гэтым выпадку? Ну, як гэтая карціна збіраюся мяняць? Я, верагодна, можа паўторна найбольш гэтай карціны. Дазвольце мне ісці наперад і сцерці тое, што тут. Мы дамо гэтым крыху іншае імя тут. Давайце пазбавіцца ад 17, давайце пазбавімся з 9, давайце пазбаўляцца ад 3. І давайце дадамо яшчэ адну рэч. Я мяркую, што мне трэба сачыць за пярэдняй частцы спісу, які з'яўляецца толькі будзе ІНТАС добра. І мы збіраемся зрабіць яго простым. Няма звязанага спісу на дадзены момант. Мы прызнаем, што мы збіраемся натыкаюцца на гэта абмежаванне. Але тое, што я хачу бачыць на гэты раз? Такім чынам, няхай я іду наперад і першым Чалавек прыходзіць у лінію, а гэты лік 9. У нас ёсць стрэс шароў. Ці магу я скрасці, скажам, два ці тры чалавекі? Адзін, два, тры? Падымайся. Прама з фронту, таму што мы будзем рабіць гэта адным хуткім. Кожны з вас цяпер будзе Вентылятар хлопчыка ў чэргі ў Apple. Вы не будзеце атрымліваць Apple Hardware У канцы гэтага ж. Добра. Значыць, ты нумар 9, вы № 17, № 22. Гэтыя адвольныя ліку, напрыклад, Студэнт ідэнтыфікатары і яшчэ шмат чаго. І праз хвіліну, давайце пачнем , Каб пачаць дадаваць рэчаў. І я пабягу борце тут на гэты раз. Так што ў гэтым выпадку я ініцыялізаваць пярэдняй быць - Я на самой справе не ўсё роўна, што фронт, так як памер роўны нулю. Так што гэта можа таксама проста быць знакам пытання. Усе гэтыя знакі пытання. Так што цяпер мы пачнем рэальна ўбачыць некаторыя людзі выстройваюцца ў чаргу ў краме. Такім чынам, калі лік 9, ты першая там у 5-й раніцы, ісці наперад і выстройваюцца ў чаргу, ці напярэдадні вечарам. ОК. Так што зараз тут 9. Так 9 знаходзіцца ў пачатку спісу. Так што я збіраюся ісці наперад і абнаўлення Памер гэтага бягучыя дадзеныя структуры, каб не быць больш 0, але роўным 1. Я збіраюся паставіць на 9 перад спісам. Дазвольце мне ісці наперад і пераключэння экрана так што мы можам бачыць мінулае з намі тут. А цяпер што я хачу паставіць на фронт? Я буду адсочваць, што пачатку чарзе зараз знаходзіцца ў месцазнаходжанні 0. Таму што далей будзе? Ну, выкажам здагадку, што цяпер я паставіць у чаргу 17, а. Так што скакаць у лінію там. І зноў жа, накшталт дзверы Крама будзе тут. Так што цяпер я дадаў 17. І хоць гэтыя хлопцы блакуюць экрана, гэта нармальна, таму што мы бачым гэта тут. Прабачце. АЎДЫТОРЫЯ: Мы можам рухацца - DAVID малая: Не, гэта нармальна. Гэта велізарны там. Так 17 цяпер ўнутры чэргі. Мне трэба абнаўленне, якое палёў цяпер, хоць? Добра, вызначана памеру. А як наконт фронту? ОК, няма. Пярэдняя ня павінна змяніцца, так як У адрозненне ад стэка, мы хочуць захаваць справядлівасць. Так што калі 9 выйшаў на першае, мы хочам, 9 быць першай з лініі і ў краму. На самай справе, давайце паглядзім, што. Перад тым, як ўставіць 22, давайце ісці наперад і Dequeue 9. Як цябе завуць? АЎДЫТОРЫЯ: Джэйк. DAVID малая: Джэйк збіраецца быць выдаленая з чаргі цяпер. Такім чынам, вы дабіраецеся, каб ісці ў краму. І рабіць выгляд, што ў краме вунь там. Так што цяпер трэба, - ДИТ-ДИТ-дит! Што павінна адбыцца зараз? Дызайн рашэння. Так не дрэнны інстынкт, але - як цябе клічуць? АЎДЫТОРЫЯ: Дэвід. DAVID малая: Дэвід. Такім чынам, што зрабіў Давід? Ён спрабаваў выправіць сартаваць дадзеныя Структура і перайсці ад яго размяшчэння ў ранейшым месцы Джэйка. І гэта выдатна, калі мы гатовыя прызнаць, што, як дэталь рэалізацыі. Але спачатку, давайце абновім дадзеныя структуры, перш чым рабіць гэта. Таму што я не падабаецца ідэя ўсіх людзі зрух у гэтай лініі. Гэта не страшна, калі Дэвід робіць гэта з адзін крок, але зноў жа, успомніце , Калі ў нас было восем добраахвотнікаў па этапе, і мы зрабілі, як ўстаўкі Сартаванне, дзе мы павінны былі пачаць перамяшчэнне ўсіх вакол. То бок дарогі, ці не так? Гэта прымушае мяне здрыгануцца аб Big O п, Big O п квадрат зноў. Гэта не пачуццё, як ідэальны вынік. Так што давайце проста абнаўляць гэта. Такім чынам, памер чэргі больш не з'яўляецца 2. Гэта цяпер проста 1. Але цяпер я магу нешта абнавіць Я не абнаўлялася раней, перад спісам. Я мог бы проста сказаць, што размяшчэнне 1? Так што цяпер у нас ёсць смецце каштоўнасць тут, смецця значэнне тут, і Дэвід ў сярэдзіне гэтага смецця. Аднак структура дадзеных па-ранейшаму некранутымі. І на самай справе, я нават не трэба змяніць ранейшы нумар Джэйка 9, таму што, хто клапоціцца. У мяне ёсць дастаткова інфармацыі, у цяперашні час у памеру, што я ведаю, што ёсць адзін чалавек у гэтай чарзе. І я ведаю, што гэты чалавек знаходзіцца ў месцазнаходжанні 1, а ня 0. Я не разлічваю. Такім чынам, 1, а таксама. Так што дадзеныя структуры ўсё яшчэ добра. Ну, а што будзе далей? Давайце Enqueue - Як цябе завуць? АЎДЫТОРЫЯ: Каллен. DAVID малая: Каллен. Давайце пастаноўкі ў чаргу Каллен, і 22 у цяперашні час у чарзе. Так што цяпер павінен змяніць тут? Пярэдняя не збіраецца змяніць, гэта відавочна. Памер будзе мяняцца, каб быць 2 зноў. І 22 сканчаецца тут, 9 па-ранейшаму прысутнічае, але гэта эфектыўна смецця значэнне цяпер. Гэта проста перажытак мінулага Джэйкам. Так што цяпер, што адбудзецца, калі Я з чаргі Дэвід? Адна апошняя аперацыя, Dequeue Давіда. Мы маглі б перайсці, але я прапаную давайце зрабіць так мала працы, колькі магчыма. Цяпер мая структура дадзеных ідзе Рэзервовае ў памеры ад 2 да 1. Але наперадзе чэргі зараз становіцца 2. Мне не трэба, каб змяніць гэты лік Пакуль яшчэ няма, таму што яны проста значэнні смецце. Але зараз тое, што адбываецца? Выкажам здагадку, што я сябе паставіць у чаргу, 26? Я адчуваю, што я належу тут. Так што я быць устаноўлены ў чаргу. Так што я як бы да нас далучыцца. І нават калі вы не зусім візуальна ацаніць гэта на сцэне, таму што ў нас шмат месца, я павінен Не стаяць тут, то чаму? Залы: Вы знаходзіцеся па-за межамі поля. DAVID малая: Дакладна. Я па-за законам. Я праіндэксаваныя за рамках дадзенага масіва. Я сапраўды павінен быць у адным з тры магчымых месцах. Такім чынам, дзе найбольш натуральным пайсці? Я прапаную пазыковых сродкаў тыдні адзін трук. Аператар Mod, у працэнтах. Таму што я стаяў на тэхнічна Размяшчэнне 3, але ў мяне 3 мод магутнасці, SO 3, знак адсотка, 3 - ёмістасць 3. Што гэта? Які рэшту пры Вы дзеліце 3 на 3? 0. Так што гэта ставіць мяне былі Джэйк быў, які на самай справе добра. Так што ў цяперашні час ажыццяўленне гэтай рэчы збіраецца быць трохі галаўнога болю. Гэта сапраўды проста адна радок галаўнога болю, кода. Але па крайняй меры зараз ёсць смецце Значэнне тут, але ёсць два законных цэлымі тут. І я сцвярджаю, што зараз мы зрабілі менавіта тое, што нам трэба зрабіць, так доўга, як змяніць тое, што мы Джэйка Значэнне павінна было быць 26. Цяпер у нас ёсць дастаткова інфармацыі па-ранейшаму для падтрымання цэласнасці гэтай структуры дадзеных. Мы ўсё яшчэ збольшага не пашэнціла, калі мы ўставіць чатыры ці больш агульнай элементы, але я магу па крайняй меры зрабіць даволі эфектыўнае выкарыстанне гэтай канстанты час, на самай справе. Я не прыйдзецца турбавацца аб пераносе Кожны чалавек, як нахіл Давіда была. Любыя пытанні па стэкі, ці гэтая чаргу? Залы: прычына, чаму Вам патрэбен памер, каб вы ведалі Дзе ёсць чалавек? DAVID малая: Цалкам дакладна. Мне трэба ведаць памер масіва таму што мне трэба дакладна ведаць, як многія з гэтых значэнняў з'яўляюцца законнымі, і так, што я магу знайсці, дзе паставіць наступны чалавек. Менавіта так. Памер - На самай справе, мы не абнаўлялі гэта пакуль. Я дадаў сябе ў 26. Памер у цяперашні час, а не адзін, а два. Так што зараз гэта сапраўды дапамагае мне знайсці на чале спісу, які не можа ісці ў 0, ня 1, але 2. Перад спісам на самай справе колькасць 22. Таму што ён прыйшоў першым, таму ён павінен пусцяць у краме перада мной, хоць візуальна я стаю бліжэй да крамы. Усё ў парадку? Апладысментаў для гэтых хлопцаў , І мы паведамім іх адтуль. [Апладысменты] DAVID малая: Я мог дазволіць Вы трымаеце латок. Мы маглі бачыць, што адбываецца, калі Вы хочаце, але можа і няма. Добра. І што цяпер што нам застаецца? Ну, дазвольце мне прапанаваць, што ёсць Некалькі іншыя структуры дадзеных, мы маглі пачаць дадаваць да нашага набор інструментаў, які будзе сапраўды можа быць вельмі, вельмі актуальная, як мы пагрузіліся ў матэрыял Інтэрнэту. Што зноў жа, ёсць нейкая сувязь да дрэў у выглядзе тое, што называецца DOM, дакумент аб'ектнай мадэлі. Але мы ўбачым больш што ў хуткім часе. Дазвольце мне прапанаваць, што мы definitionally дрэва выклікаў зараз тое, што вы ведаеце, як больш сямейнага дрэва, дзе вы ёсць продкам Карані дрэва. Патрыярхальнай ці матрыярхат ў самай вяршыні дрэва. Без іх мужа і жонкі, у гэтым выпадку. Але цяпер мы маем тое, што мы будзем называць дзяцей, якія з'яўляюцца вузламі, якія вісяць за левым дзіцем або права дзіцяці, стрэлкі, як паказана тут. Іншымі словамі, у структуры дадзеных дрэва ў кампутар, дрэва мае нулявую ці больш вузлоў. Калі ў яго ёсць хоць бы адзін вузел, Гэта называецца коранем. Гэта рэчы, што візуальна мы звяртаем на самым версе. І гэты вузел, як і любы іншы вузел, можа мець нуль, адзін ці два, ці тры, ці колькі дзяцей Структура дадзеных падтрымлівае. У гэтым выпадку, корань, захоўванне Значэнне аднаго, мае дваіх дзяцей, 2 і 3, таму мы звычайна называем 2 левых дзіцяці і 3 правам дзіцяці. А потым, калі мы прыступім да 5, 6, і 7, 6 можна назваць сярэднім дзіцем. Калі ў вас ёсць чацвёра дзяцей, гэта збівае з толку. Такім чынам, мы спыніць выкарыстанне такога спалучэнняў у вуснай форме. Але гэта сапраўды толькі генеалагічнае дрэва. І лісце тут вузлы, якія самі па сабе не маюць дзяцей. Яны вісяць ад ніжняй часткі дрэва. Так як мы можам рэалізаваць дрэва, мае толькі дзве дзецям максімальна? Мы назавем гэта бінарнае дрэва. Бі зноў азначае два, у гэтым выпадку, як і з бінарнымі. І таму ён можа мець нуль, адзін, або двух дзяцей максімальна. Я прапаную, каб мы ажыццявілі вузла для гэтай структуры з Int N, а затым два паказальніка, адна называецца пакінулі, адна называецца правам. Але гэта проста прыемна адвольныя пагаднення. І тое, што прыемна цяпер, асабліва, калі вы выгляд змагаўся канцэптуальна рэкурсіі, ці думаў, што гэта не было Рашэнне сапраўды ні да чаго, Асабліва калі б вы маглі запусціць з памяці. Цяпер, калі мы гаворым пра дадзеныя структуры і алгарытмы, якія дазваляюць нам, каб прайсці іх і маніпуляваць імі, Аказваецца, што Рэкурсія вяртаецца ў значна больш пераканаўчай калі не прыгожым спосабам. Так што я прапаную, з'яўляецца рэалізацыя з функцыі пошуку. Улічваючы два ўваходу - таму думайце пра гэта як чорны скрыню. Улічваючы два ўваходу, N, цэлае і паказальнік на дрэве, паказальнік на вузла, ці сапраўды корань дрэва, я сцвярджаюць, што гэтая функцыя можа вяртаць сапраўдным або ілжывых, што значэнне N ўнутры гэтага дрэва. Што ўнутры гэтага чорнага скрыні? Ну, чатыры галіны. Спачатку проста правярае. Калі дрэва з'яўляецца пустым, проста вярнуць ілжывае. Калі няма вузла, няма N, ліку няма, як раз вяртае ілжывае. Калі хоць, N, значэнне, якое вы шукаеце для, менш дрэва стрэлку N, і проста каб было ясна, што гэта значыць, калі Я пішу дрэва, а затым стрэлка пазначэнне, п? Менавіта так. Гэта азначае, што разнаймення Паказальнік называецца дрэвам. Адпраўляйцеся туды, а затым патрапіць унутр, што вузла і атрымаць яго поле, названае N. А потым параўнаць фактычныя N, якая была перайшла ў пошук супраць яго. Такім чынам, калі N менш, значэнне N ў вузле дрэва сам, ну, Што гэта значыць? Гэта нічога не значыць на першы погляд. Дакладна? Як і калі вы ёсць масіў Значэнні, якія Вы хацелі б прымяніць двайковы шукаць як форма разрыву і ўладар. Але тое, што зрабіў здагадку мы павінны зрабіць для бінарнага пошуку працуе наогул у тэлефоннай кнізе і больш раннія прыклады? Як быць адсартаваныя. Так што давайце ўдакладніць вызначэнне дрэва Тут, каб не быць проста дрэва, якое можа мець любую колькасць дзяцей. Не толькі бінарнае дрэва, якое можа мець 0, 1 або 2 максімальна. Але, як бінарнае дрэва пошуку або BST, , Якая з'яўляецца проста мудрагелісты спосаб сказаць бінарнае дрэва так, што кожны вузла левы дзіцяці, калі ён прысутнічае, менш вузла. І права кожнага вузла дзіцем, калі яны прысутнічаюць, больш акрамя самога вузла. Такім чынам, іншымі словамі, калі вы павінны былі зрабіць дрэва з ўсе лічбы старанна збалансаваны, як гэта так, што калі у вас ёсць 55 у якасці каранёвага, 33 можа пайсці злева ад яго, таму што гэта менш, чым 55. 77 можа пайсці ў сваім праве, таму што гэта больш, чым 55. Але цяпер заўважылі, тое ж вызначэнне, гэта рэкурсіўнае вызначэнне ў вуснай форме, павінен накіраваць заяўку на 33. 33 у левай дзіця павінен быць менш яго, правы дзіцяці і ў 33, 44, павінны быць больш, чым ён. Так што гэта бінарнае дрэва пошуку, а Я прапаную, выкарыстоўваючы трохі рэкурсіі, зараз мы можам знайсці N. Такім чынам, калі N менш, чым значэнне N гэта бягучага вузла, я пайду наперад і выбіваць з рук, так бы мовіць, і проста вяртаючы тое, што адказ на гэтае пытанне з пошук п ад левага дрэва дзіцяці. Яшчэ раз звярніце ўвагу, гэтая функцыя проста чакае вузла зоркі, паказальнік на вузел. Так што, вядома, я проста магу зрабіць дрэва стрэлка налева, што прыводзіць мне на іншы вузел. Але што гэта за вузел? Ну, у адпаведнасці з гэтай дэкларацыяй, Злева толькі паказальнік, так што толькі азначае, што я пераходзячы да функцыі пошуку розных паказальнікаў, а менавіта адзін, які ўяўляе мая левая дзіцяці дрэва. Такім чынам, у гэтым выпадку паказальнік 33, калі гэта наш прыклад ўводу Між тым, калі п больш значэнне п пры бягучага вузла ў дрэве, то я збіраюся ісці наперад і выбіваць з рук у іншыя Кірунак і проста сказаць, я не ведаю, калі гэта значэнне п ў дрэве, але я ведаю, калі гэта так, гэта на маю Правая галіна, так бы мовіць. Такім чынам, дазвольце мне рэкурсіўна шукаць, які праходзіць N раз, але пераходзячая ў паказальнік на маім правам дзіцяці. Іншымі словамі, калі я ў цяперашні час знаходжуся на 55 і я шукаю 99, я ведаю, што 99 больш 55, гэтак жа, як я разарваў тыдняў тэлефонную кнігу таму, і мы пайшоў прама, як і мы збіраюся ісці прама тут. І я не ведаю, ці будзе гэта на маё права дзіцяці, а гэта не так, 77 ёсць, але Я ведаю, што ў гэтым кірунку. Таму я называю пошуку справа ад мяне дзіцяці, 77, і хай пошук фігуры з там, калі 99 у гэтым адвольным Прыкладам з'яўляецца на самай справе. У адваротным выпадку, тое, што апошні выпадак? Калі дрэва з'яўляецца несапраўдным адзін выпадак. Калі п менш бягучага вузла значэнне яшчэ адзін выпадак. Калі п больш, чым бягучы Значэнне вузла трэці выпадак. Што чацвёртым і апошнім выпадку? Я думаю, што мы з выпадкаў, ці не так? Павінна быць, п у бягучага вузла, што я на. Так што, калі Я шукаю 55 на дадзены момант ў гэтай гісторыі, што філіял Дрэва будзе вернута ісціна. Так што тут цікава тое, што мы на самай справе, у адрозненне ад мінулых тыдняў, мы як-то з двух выпадкаў ёсць падставы. І яны не павінны усё будзе на самым версе. Верхняя частка базавага варыянту, таму што калі Дрэва з'яўляецца несапраўдным, няма нічога агульнага. Проста вярнуць жорстка зададзены Значэнне ілжывым. Ніжняя галіна роду па змаўчанні, згодна з якім, калі мы праверылі для нулявым, мы праверылі, калі яна павінна быць засталося, але яно не павінна быць, у нас правяраецца, калі гэта павінна быць правільна, але гэта не павінна быць, відавочна, што яно павінна быць там, дзе мы ёсць. Гэта базавы варыянт. Такім чынам, ёсць два рэкурсіўных выпадкаў заціснутая там у сярэдзіне. Але я мог бы напісаць гэта ў любым парадку. Я проста думаў, што гэта як бы адчуваў, прыродныя спачатку праверыць на магчымую памылку, затым праверыць налева, затым праверыць прама, то Выкажам здагадку, што вы знаходзіцеся ў вузле на самай справе вы шукаеце. Дык чаму гэта магло б быць карысным? Вось і атрымліваецца - і дазвольце мне перайсці да тізер тут, гэта ў Сеткі. Мы збіраемся, каб пачаць выкарыстаць не мова праграмавання на першы, але мова разметкі. Мова разметкі з'яўляецца адным гэта блізкія па духу да праграмавання мовы, але гэта не дае вам Магчымасць выказаць сябе лагічна. Гэта толькі дае вам магчымасць выказаць сябе структурна. Дзе Вы хочаце, каб пакласці што-то на старонцы, вэб-старонка? Які колер вы хочаце гэта зрабіць? Які памер шрыфта вы хочаце гэта зрабіць? Якія словы вы на самой справе хочаце на вэб-старонку? Так што гэта мова разметкі. Але тады мы вельмі хутка ўвесці JavaScript, які з'яўляецца паўнавартасным мовы праграмавання. Вельмі падобны па вонкавым выглядзе сінтаксічна З, але гэта будзе мець некаторыя добра, больш магутная, больш зручных для карыстальніка характарыстык. І адным з расчараванняў ў гэты кропка ў семестр, што мы будзем хутка ў рэалізацыі спеллер значна менш радкоў кода з выкарыстаннем іншых мовах C чым сама дазваляе, але для розуму мы хутка зразумелі. Гэта будзе першы такі вэб-старонкі. Ён будзе цалкам у захапленне, Першае мы робім. Ён проста скажа: прывітанне свет. Але калі вы ніколі не бачылі яго раней, гэта HTML, Мова разметкі гіпертэксту. Калі вы ідзяце ў пэўны пункт меню ў Найбольш любым браўзэры, на любы вэб-старонцы Інтэрнэт, вы можаце ўбачыць HTML што некаторыя людзі напісалі стварыць гэтую вэб-старонку. І гэта, верагодна, выглядае не так кароткая ці жа акуратна, як гэты. Але гэта будзе па той жа схеме гэтых адкрытыя дужкі і касая рыса і Лісты і патэнцыйна лікаў. Я думаў, што дам вам тізер таго, што вы будзеце ў стане зрабіць пасля прыёму CS50. Пусціце мяне да cs.harvard.edu / рабаваць, Хатняя старонка нашай уласнай Роб Боуден. Ён зрабіў гэта для нас. Такім чынам, вы хутка будзеце ў стане зрабіць гэта. А таксама, што вы чулі Сёння раніцай - тое, што вы чулі сёння раніцай - [HAMSTER Танцавальная музыка] - Вы будзеце мець магчымасць зрабіць гэта. Што чакае нас у сераду. Мы будзем бачыць вас тады. [HAMSTER Танцавальная музыка] DAVID малая: На наступным CS50 -