[Powered by Google Translate] [Тыдзень 6] [David J. малая] [Harvard University] [Гэта CS50.] [CS50.TV] 

Гэта CS50, і гэта пачатак тыдня 6, так што пару новых інструментаў цяпер даступныя для вас, каб скарыстацца перавагамі, першая з якіх называецца CS50 стылю. Хутчэй за ўсё, калі вы падобныя на мяне ці любога вучэнні хлопцы, Вы, напэўна, бачылі праграму, чый стыль выглядае крыху нешта накшталт гэтага. Можа быць, вы пачнеце рэзкі некаторыя вуглы позна ўначы, ці вы будзеце мець справу з ім пазней, , А затым TF або CA прыходзіць ў працоўны час. Тады гэта цяжка для нас, каб чытаць. Ну, гэты код сінтаксічна правільныя, і ён будзе кампіляваць, і яна будзе рэальна працаваць. Але гэта вызначана не 5 за стыль. 

Але цяпер, калі мы пойдзем у гэты каталог тут- і заўважыў, што ў мяне ёсць conditions2.c- і я бягу гэтую новую каманду, style50, на гэты файл conditions2.c, Enter заўважыце, што ён паведаміў мне, што ён быў стылізаваны. Gedit заўважыў, што файл быў зменены на дыску, і калі я націскаю кнопку перазагрузкі, усе вашы праблемы ў цяперашні час аўтаматызаваныя. [Апладысменты] Гэта адна з рэчаў, якія мы зрабілі ў гэтыя выходныя. Зразумейце, што яна недасканалая, таму што ёсць некаторы код што ён проста не зможа стылізаваць выдатна, але разумею, што гэта цяпер інструмента вы можаце скарыстацца калі толькі прывесці ў парадак некаторыя з больш errantly размешчаны фігурныя дужкі і таму падобнае. 

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

Тэсты, якія вы хочаце запусціць вызначаны адназначна гэты радок, 2012/pset4/resize. Іншымі словамі, гэта проста адвольнае, але унікальная радок , Якія мы выкарыстоўваем, каб адназначна ідэнтыфікаваць правільнасці PSET 4 у тэстах. А потым вы задаеце прабел спіс файлаў, якія вы хочаце загрузіць Праверыць, каб CS50 для аналізу. Напрыклад, калі я іду на маё рашэнне тут Змена памеру- Дазвольце мне адкрыць вялікія вокны тэрмінала- і я іду наперад і запусціць скажам check50-с 2012/pset4/resize, а потым ісці наперад і паказаць імёны файлаў, Змена памеру, а затым націсніце Enter, ён сціскае, Ён загружае, ён правярае, і я проста не змог цэлую кучу тэстаў. Той у чырвоным у левым верхнім куце кажа, што Змяненне памеру і BMP існуе. Гэта быў тэст. Такое пытанне мы задалі. І гэта няшчасныя, таму што адказ быў ілжывым. Белы тэкст ніжэй ён кажа чакаецца bmp.h існаваць, і гэта проста мая віна. Я забыўся, каб загрузіць яго, так што мне трэба загружаць як файлы, Змяненне памеру і bmp.h. Але цяпер заўважаю ўсе іншыя тэсты ў жоўты, таму што яны не працуюць, і так смайлік вертыкальна, таму што ён не з'яўляецца ні шчаслівым, ні сумна, але ў нас ёсць для ліквідацыі гэтага пытання ў чырвоным перад тымі, іншых праверак будзе працаваць. 

Дазвольце мне выправіць гэта. Дазвольце мне маштаб і паўторыце гэта, на гэты раз з bmp.h таксама у камандным радку, Enter, і зараз, калі ўсё пойдзе добра, ён збіраецца праверыць, а затым вяртаюць вынік, затрымаеце дыханне- Усе зялёнае, а гэта значыць, што я раблю вельмі добра на PSET 4 да гэтага часу. Вы можаце бачыць і вывесці з апісальных тэксту тут дакладна, што гэта мы праверылі. Мы пратэставалі першы ж файлы існуюць? Мы тады пратэставаны робіць Змена памеру кампіляцыі? Затым мы праверылі гэта не памер 1x1 піксель BMP, калі п, змяненне памеру фактар, 1. Зараз, калі вы не ведаеце, што п, вы будзеце толькі вы пагрузіцца ў PSET 4, але гэта проста здаровае праверыць, каб пераканацца, што вы не змена памеру Малюнак наогул, калі змяненне памеру каэфіцыент роўны 1. Калі ж, наадварот, ён змяняе 1x1 піксель у піксель 1x1 2x2 BMP, каб правільна пры п = 2, то аналагічна, мой фармуе адпаведна. 

Карацей кажучы, гэта азначала, адзін, прымаць перасячэння пальцаў з раўнання права, перш чым падаць PSET. Вы будзеце дакладна ведаць, што ваш TF хутка даведаемся калі вы ідзяце аб адпраўцы некаторых з гэтых набораў праблемы, а таксама педагагічныя матывацыя сапраўды паставіць магчымасць перад вамі, так што, калі вы ведаеце, апрыёрна што ёсць памылкі ў кодзе і тэстах, якія не прайшлі, Вы можаце змясціць у больш эфектыўныя часу наперадзе, каб вырашыць гэтыя праблемы , А не губляць ачкі, атрымаць зваротную сувязь ад вашых TF, , А затым ісці, "Ах", як я зразумеў гэта. Зараз па крайняй меры ёсць інструмент, каб дапамагчы вам знайсці гэта. Гэта не збіраецца паказаць, дзе памылка, але яна скажа вам, , Што з'яўляецца сімптомам яго. 

Цяпер разумею, тэсты не з'яўляецца вычарпальным. Проста таму, што вы атрымліваеце экран, поўны зялёных смайлікаў не азначае, што ваш код з'яўляецца дасканалай, але гэта не азначае, што яна прайшла пэўныя выпрабаванні, прадугледжаныя ў спецыфікацыі. Часам мы не выпусцім праверак. Напрыклад, дэтэктыўны раман, адным з аспектаў PSET 4, гэта свайго роду расчараванне, калі мы даем вам адказ на пытанне, што гэта такое, і ёсць некалькі спосабаў, каб паказаць хто гэты чалавек у тым, што чырвоныя шуму. У спецыфікацыі будуць заўсёды паказваць у будучыні для PSET 5 наперад Якія віды кантролю існуюць для вас. Вы заўважыце, што гэта за белыя URL у ніжняй часткі. На дадзены момант гэта ўсяго толькі дыягнастычны выхад. Калі вы наведаеце гэты адрас, вы атрымаеце цэлую кучу вар'ятаў, загадкавыя паведамленні што вы можаце праглядаць, але гэта ў асноўным для супрацоўнікаў так што мы можам дыягнаставаць і адладжваць памылкі ў check50 сябе. 

Без цырымоній, давайце пяройдзем туды, дзе мы спыніліся. CS50 бібліятэцы мы лічылі само сабой якія разумеюцца на працягу некалькіх тыдняў, але затым на мінулым тыдні, мы пачалі пілінг таму адзін з пластоў яго. Мы пачалі адклаўшы радок у карысць таго, што замест гэтага? [Студэнты] Char. Char *, які быў сімвал * ўвесь гэты час, але цяпер мы не павінны рабіць выгляд, што гэта фактычны тып дадзеных радок. Хутчэй, гэта быў сінонім роду для знакаў *, і радок ўяўляе сабой паслядоўнасць знакаў, Так чаму гэта мае сэнс прадстаўляць радкі як сімвал * з? Што азначае сімвал * прадстаўляе ў кантэксце гэтай канцэпцыі радкі? Так. >> [Студэнт] першы знак. Добра, першы знак, але не зусім першы знак. Гэта-[Студэнты] адрас. Добра, адрас першага знака. Усё, што неабходна для прадстаўлення радкоў у памяці кампутара гэта проста унікальны адрас самага першага байта. Вам нават не трэба ведаць, як доўга гэта таму што, як вы можаце зразумець, што з дынамічна? [Студэнт] даўжыня радка. Вы можаце патэлефанаваць даўжыня радка, выдатна, але як праца даўжыню радка? Што ён робіць? Так. [Студэнт] Працягвайце, пакуль не атрымаеце нулявой сімвал. Так, сапраўды, ён проста выконвае ітэрацыі з цыклу, у той час як цыкл, незалежна ад * да канца, і ў канцы прадстаўлена на \ 0, так званай нулявой сімвал, н, Не блытаць з нулявым, які з'яўляецца паказальнікам, які ўступіць у размове зноў сёння. 

Мы вычышчаныя назад пластом GetInt, і тады мы зірнулі на GetString, і нагадаем, што абедзве гэтыя функцыі, ці сапраўды, GetString, было выкарыстанне пэўных функцый на самай справе разабраць, гэта значыць, чытаць і аналізаваць, уведзеных карыстальнікам. І што гэта за новая функцыя? Scanf або Sscanf. Гэта на самай справе адбываецца ў некалькі розных водараў. Там у SCANF, ёсць Sscanf, ёсць fscanf. Цяпер, аднак, давайце засяродзімся на адно найбольш лёгка праілюстраваць, і дазвольце мне ісці наперад і адкрыць у прыборы Файл, як гэта, scanf1.c. Гэта супер простая праграма, але што робіць нешта, што мы ніколі не рабілі без дапамогі CS50 бібліятэкі. Гэта становіцца Int ад карыстальніка. Як гэта працуе? Ну, а ў радку 16 маецца, заўважыце, што мы заяўляем Int называецца х, і ў гэты момант у гісторыі, што такое значэнне х? [Неразборліва адказ студэнта] [David M.] Права, хто ведае, смецце значэння патэнцыйна, так і ў 17, мы проста паведаміць карыстачу дайце мне нумар, калі ласка, і крок 18, дзе гэта становіцца цікавым. Scanf здаецца запазычаць ідэі з Printf у тым, што ён выкарыстоўвае фармат кодаў у двукоссі. % D, вядома, дзесятковы лік. Але чаму я якая праходзіць у & х, а не проста х? Былы правільна. Так. [Неразборліва адказ студэнта] Менавіта, калі мэта гэтай праграмы, як і функцыя GetInt сябе, , Каб атрымаць цэлы лік ад карыстальнікаў я магу перадаць функцыі ўсе зменныя, я хачу, але калі я не перадаваць іх па спасылцы або па адрасе або па паказальніку, усё сінонімам для мэт сённяшняй, то гэтая функцыя не мае магчымасці змяняць змесціва гэтай зменнай. Гэта павінна перадаць у копіі, як багі версіі своп што мы казалі пра некалькі разоў цяпер. 

Але замест гэтага, робячы & х, я літаральна які праходзіць у чым? [Студэнт] адрас. >> Адрасамі х. Гэта падобна на маляванне карты для функцыі называецца SCANF і кажуць тут, гэтыя напрамкі кавалак памяці ў кампутары што вы можаце пайсці захоўваць некаторы цэлае цалі Для таго, каб Sscanf гэтага часу зрабіць гэта які аператар, што частка сінтаксісу гэтага прыйдзецца выкарыстоўваць нават калі мы не можам бачыць, таму што хтосьці іншы напісаў гэтую функцыю? Іншымі словамі - што гэта такое? [Студэнт] X чытаць. Там збіраецца быць некаторы чытанне, але толькі ў дачыненні да х тут. Калі SCANF ў цяперашні час перадаецца адрас х, Сінтаксічна, што аператар абавязаны існаваць дзесьці Усярэдзіне рэалізацыі SCANF так, што SCANF сапраўды можа напісаць нумар 2 па гэтым адрасе? Так, так *. Нагадаем, што * гэта наш аператар разнаймення, якая па сутнасці азначае пайсці туды. 

Пасля таго як вы перадалі адрасы, як у дадзеным выпадку, SCANF, верагодна, калі мы на самай справе агледзеў яго зыходны код- робіць * х ці эквівалент на самай справе пайсці па гэтым адрасе і пакласці некаторы значэнне там. Цяпер, як і пра тое, як SCANF атрымлівае увод з клавіятуры, мы махаем рукамі за сёння. Проста выкажам здагадку, што аперацыйная сістэма дазваляе Sscanf казаць з клавіятуры карыстальнікам, але на дадзены момант цяпер у радку 19, Калі мы проста раздрукаваць х, гэта, здаецца, выпадак што SCANF паставіў Int х. Гэта сапраўды, як SCANF працуе, і ўспомніць апошні тыдзень гэта дакладна, як GetString і GetInt і іншых яго сямейства функцый у канчатковым выніку працуе, хоць і з невялікім дысперсіі, як Sscanf, што азначае сканаванне радкоў замест клавіятуры. Але давайце зірнем на невялікай розніцы ў гэтым. У scanf2, я сапраўды аблажаўся. Што не так, і я схаваю каментар, які тлумачыць, як шмат- што не так з гэтай праграмай, версія 2? Будзьце як тэхнічныя магчымасці на гэты раз. Гэта выглядае даволі добра. Гэта прыемна водступу, але- Добра, а як наконт давайце скарачаць яго да кароткіх пытанняў? Лінія 16. Што рабіць лініі 16 ст дакладнай, але тэхнічны ангельскую мову? Атрыманне крыху няёмка. Так, Майкл. [Студэнт] Гэта паказвае на першыя літары радкоў. 

Добра, блізка. Дазвольце мне наладзіць, што няшмат. Паказваючы на ​​першую літару радкі, вы аб'яўляеце зменную буфера , Што будзе ўказваць на першы адрас радкі, ці, хутчэй, будзе паказваць больш канкрэтна знак. Звярніце ўвагу, што гэта на самай справе не паказваючы дзе заўгодна, таму што няма аператара прысвойвання. Там няма знака роўнасці, таму ўсё, што мы робім, вылучэнне зменнай званага буфера. Гэта здараецца, 32 біт, таму што гэта паказальнік, і змесціва буфера як мяркуецца, у рэшце рэшт будзе ўтрымліваць адрас сімвал, але цяпер, што ж буферы ўтрымліваць? Проста некаторыя фіктыўныя, хто ведае, смецце значэнне, таму, што мы відавочна не ініцыялізаваны, так што мы не павінны меркаваць, што заўгодна. Такім чынам, цяпер лінія 17,-што ж лініі 17 рабіць? Можа быць, сагрэе гэта. Яна выводзіць радок, ці не так? Ён друкуе струннага калі ласка. 

Радок 18 з'яўляецца своеасаблівай знаёмы цяпер у тым, што мы толькі што бачылі дысперсія гэтага але з іншым кодам фармату, так і ў радку 18, мы кажам SCANF тут з'яўляецца адрасам блока памяці. Я хачу, каб ты тэлефанаваў у радок, як гэта маецца на ўвазе% З, але праблема ў тым, што мы не зрабілі пару рэчаў. Што адна з праблем? [Студэнт] Гэта спроба разнаймення нулявога паказальніка. Добра, нулявыя ці проста ў адваротным выпадку невядомыя паказальнікаў. Вы ўручэння SCANF адрас, але вы толькі што сказалі хвіліну назад , Што адрас смецце значэнне, таму што мы на самай справе не прысвоіць яму ні да чаго, і таму вы кажаце SCANF эфектыўна ісці пакласці радкі тут, але мы не ведаем, дзе тут яшчэ ёсць, так што мы, уласна, не выдзеленай памяці для буфера. Акрамя таго, што вы таксама нават не кажу SCANF? Выкажам здагадку, што гэта быў кавалак памяці, і гэта не было смецця значэнне, але вы ўсё яшчэ не казаў SCANF нешта важнае. [Студэнт] Дзе на самой справе, амперсанда. Амперсанда, таму ў дадзеным выпадку, гэта нармальна. Таму што буфер ўжо абвешчаны як паказальнік з * частку сінтаксісу, мы не павінны выкарыстоўваць амперсанда таму што гэта ўжо адрас, але я думаю, што я чуў, гэта тут. [Студэнт] Як ён вялікі? Добра, што мы не гаворым SCANF, наколькі вялікі гэты буфер, які азначае, што нават калі буфер быў паказальнік, Мы кажам SCANF, пакласці тут радок, Але тут можа быць 2 байта, гэта можа быць 10 байт, ён можа быць мегабайт. Scanf паняцця не мае, а таму, што гэта кавалак памяці Як мяркуецца, гэта не радок, пакуль няма. Гэта ўсяго толькі радок, як толькі вы пісаць сімвалы і \ 0 да гэтага кавалак памяці. Цяпер гэта толькі некаторыя кавалак памяці. Scanf не будзе ведаць, калі перастаць пісаць па гэтым адрасе. 

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

Вось, я кажу SCANF вось кавалак памяці. На гэты раз, гэта на самай справе частка памяці, Але чаму гэтай праграмы да гэтага часу ўразлівасцям? Што здарылася яшчэ? Я ўжо казаў, дайце мне 16 байт, але- [Студэнт] Што рабіць, калі яны друкуюць больш чым у 16? Вось менавіта, што калі карыстальнік ўводзіць 17 сімвалаў або 1700 знакаў? На самай справе, давайце паглядзім, калі мы не можам спатыкнуцца гэтую памылку цяпер. Гэта лепш, але не ідэальна. Дазвольце мне ісці наперад і працаваць scanf3 зрабіць для кампіляцыі гэтай праграмы. Дазвольце мне выканаць scanf3, String калі ласка: прывітанне, і мы, здаецца, у парадку. Дазвольце мне паспрабаваць крыху больш аднаго, прывітанне. Добра, давайце зробім прывітанне, як справы, Enter. Атрыманне віду пашанцавала тут, скажам, прывітанне як справы. Чорт вазьмі. Такім чынам, нам пашанцавала. Давайце паглядзім, калі мы не можам гэта выправіць. Не, яна не збіраецца дазволіць мне скапіяваць. Давайце паспрабуем гэта зноў. Добра, стаяць у баку. Мы ўбачым, як доўга я магу прыкідвацца, каб засяродзіцца ў той жа час зрабіць гэта. Чорт вазьмі. Гэта даволі неабходнасці, на самай справе. Там мы ідзем. Кропка зрабіў. 

Гэта, няёмка, хоць яно і ёсць, ён таксама з'яўляецца адным з крыніц вялікую блытаніну Пры напісанні праграм, якія маюць памылкі, таму што яны выяўляюцца Толькі раз у той час часам. Рэальнасць такая, што нават калі ваш код цалкам зламаная, гэта можа быць цалкам разбурана раз у той час таму што часам, па сутнасці, адбываецца тое, вылучае аперацыйнай сістэмы трохі больш памяці, чым вам сапраўды трэба па любой прычыне, і так ніхто не выкарыстоўвае памяць адразу пасля кавалак з 16 сімвалаў, так што калі вы ідзяце ў 17, 18, 19, незалежна, гэта не такая вялікая праблема. Цяпер, кампутар, нават калі яна не абрынецца ў той момант, у канчатковым выніку можа выкарыстоўваць Байт нумар 17 ці 18, ці 19 на нешта іншае, У гэты момант вашы дадзеныя, якія вы стварылі, хоць і празмерна доўгімі, будзе страчаны патэнцыйна некаторыя іншыя функцыі. Гэта не абавязкова застанецца некранутым, але гэта не абавязкова выклікаць сегменце віна. Але ў дадзеным выпадку, я, нарэшце, далі досыць сімвалаў што я істотна перавысіў мае сегмент памяці, і бац, Аперацыйная сістэма сказала: "Выбачай, гэта не добра, памылкі сегментацыі." 

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

[Студэнт] Чаму вы не павінны паставіць амперсанда побач з часткі- Добры пытанне. Чаму ў мяне не было паставіць амперсанда побач з масіў сімвалаў, як я зрабіў раней з большасцю нашых прыкладах? Кароткі адказ складаецца ў масівах трохі асаблівым. Вы можаце падумаць, буфер, на самай справе з'яўляецца адрасам, і так ужо здарылася, каб быць так, што плошча пазначэнне кранштэйна з'яўляецца зручным, так што мы можам пайсці ў кранштэйны 0, кранштэйны 1, Кранштэйны 2, не звяртаючыся да выкарыстання * наймення. Гэта трохі белага хлусня, таму што масівы і паказальнікі , На самай справе, крыху па-іншаму, але яны могуць часта, але не заўсёды выкарыстоўваюцца як узаемазаменныя. Карацей кажучы, калі функцыя чакае паказальнік на ўчастак памяці, Вы можаце альбо перадаць яго адрас, які быў вернуты таНос, і мы ўбачым, таНос зноў у хуткім часе, ці вы можаце перадаць яго імя масіва. Вы не павінны рабіць амперсанда з масівамі, таму што яны ўжо істотна хацеў адрасоў. Гэта адно выключэнне. У квадратных дужках зрабіць іх асаблівымі. 

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

GetString з'яўляецца выдатным прыкладам. GetString, напісаныя намі, паняцця не мае, колькі знакаў чакаць, Таму той факт, што мы можам вылучыць куски бесперапыннай памяці гэта добра. Масівы таксама вырашыць праблему, мы ўбачылі пару тыдняў назад, цяпер , Дзе ваш код пачынае ператворыцца ў нешта вельмі дрэнна распрацавана. Нагадаем, што Я стварыў студэнт па імі Дэвід структуры, а затым, што было на самай справе альтэрнатыва, хоць, да наяўнасці зменнай імя і іншую зменную, я думаю, дома, і іншая пераменная ID, таму што ў гэтай гісторыі я тады хацеў прадставіць нешта іншае Роб падабаецца ў праграме, так што потым я вырашыў пачакаць хвіліну, Мне трэба перайменаваць гэтыя зменныя. Давайце называць маё name1, ID1, House1. Давайце назавем Адзежа name2, house2, ID2. Але пачакайце хвілінку, што пра Томі? Тады ў нас было яшчэ тры зменныя. Мы ўвялі кагосьці іншага, чатыры набору зменных. Свет пачаў заблытацца вельмі хутка, такім чынам, мы ўвялі структуры, і тое, што пераканаўчых аб структуры? Што структуру C дазволіць вам зрабіць? Гэта вельмі нязручна сёння. Што? >> [Неразборліва адказ студэнта] Так, у прыватнасці, ЬурейеЕ дазваляе стварыць новы тып дадзеных, і структуры, структуры ключавых слоў, дазваляе інкапсуляваць канцэптуальна звязаныя элементы дадзеных разам і пасля гэтага называць іх чымсьці накшталт студэнта. 

Гэта было добра, таму што цяпер мы можам змадэляваць значна больш рода канцэптуальна адпавядае паняццю студэнта ў зменную , А не адвольна якія маюць адзін для радкі, па адным для ID, і гэтак далей. Масівы прыемна, таму што яны дазваляюць пачаць уборку нашага кода. Але тое, што ёсць і зваротная бок цяпер масіва? Што вы можаце не рабіць? Так. [Студэнт] Вы павінны ведаць, наколькі яна вялікая. Вы павінны ведаць, наколькі ён вялікі, так што гэта выгляд болю. Тыя з вас, з вопытам праграмавання ведаем, што ў шматлікіх мовах, як Java, вы можаце папрасіць кавалак памяці, у прыватнасці масіва, наколькі вялікі ты, з даўжынёй, ўласнасць, так бы мовіць, і гэта сапраўды зручна. У C, вы не можаце нават назваць StrLen на агульным масіве таму што StrLen, як слова мае на ўвазе, толькі для радкоў, і вы можаце высветліць даўжыню радка, таму што гэтага чалавека канвенцыі наяўнасці \ 0, але масіве, у больш агульным, гэта проста кавалак памяці. Калі гэта масіў цэлых лікаў, там не будзе нейкі асаблівы характар У канцы вас чакае. Вы павінны памятаць, даўжыня масіва. Яшчэ адным недахопам масіва падняў сваю галаву ў GetString сябе. Што яшчэ адным недахопам масіва? Сэр, толькі ты і я сёння. [Неразборліва адказ студэнта] >> Гэта што? Ён абвешчаны ў стэку. Добра, заявіў у стэку. Чаму б вам не падабаецца? [Студэнт] Таму што ён будзе выкарыстоўваць паўторна. Ён атрымлівае паўторна. Добра, калі вы выкарыстоўваеце масіў для выдзялення памяці, Вы не можаце, напрыклад, вярнуцца, таму што гэта ў стэку. Добра, што гэта недахоп. А як наконт яшчэ аднаго з масівам? Пасля таго як вы вылучыце яе, ты накшталт п'яны, калі вам трэба больш месца , Чым у масіва. 

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

Зараз, толькі загваздка ў тым, што гэта амаль адчувае, як у мяне цэлы букет розных зменных. Гэта адчувае сябе пяць розных зменных патэнцыйна. Але што, калі мы выкрасці ідэю з радкоў якім мы неяк звязаць гэтыя рэчы разам канцэптуальна, а што, калі я гэта зрабіў? Гэта мой вельмі дрэнна звяртаецца стрэлкі. Але выкажам здагадку, што кожны з гэтых участкаў памяці паказаў на аднаго, і гэты хлопец, у якога няма брата, каб яго правы, не мае такога стрэлка. Гэта на самай справе тое, што называецца звязанага спісу. Гэта новая структура дадзеных, якая дазваляе вылучыць кавалак памяці, потым другая, потым яшчэ, потым яшчэ, у любы час мы хочам падчас выканання праграмы, і мы памятаем, што ўсе яны так ці інакш звязаных літаральна ланцужок іх разам, і мы зрабілі гэта наглядна тут са стрэлкай. Але ў кодзе, які будзе механізм, праз які вы маглі б нейкім чынам падключыць, амаль як Scratch, адзін кавалак на іншы кавалак? Мы маглі б выкарыстоўваць паказальнік, ці не так? Таму што на самой справе стрэлка, якая адбываецца з верхняга левага квадрата, гэты хлопец тут, каб гэтую, можа ўтрымлівацца ўнутры гэтага квадрата Не толькі некаторыя цэлыя, а не толькі некаторых знакаў, але што, калі я на самай справе вылучыў трохі дадатковага прасторы, так што цяпер, Кожны з маіх участкаў памяці, нават калі гэта будзе каштаваць мне, зараз выглядае крыху больш прастакутнай, дзе адзін з участкаў памяці Выкарыстоўваецца для нумар, як нумар 1, а затым, калі гэты хлопец захоўвае нумар 2, гэтая іншая частка памяці выкарыстоўваецца для стрэлка, або больш канкрэтна, паказальнік. І няхай я захоўваю № 3 тут у той час як я выкарыстоўваю гэта, каб паказаць на таго хлопца, і зараз гэты хлопец, выкажам здагадку, я хачу толькі тры такіх участкаў памяці. Я намалюю лінію праз якія, з указаннем нулявы. Існуе ніякага дадатковага характару. 

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

Гэтак жа, як з радком, вы павінны ведаць адрас першага знака. Тое ж здзелка для звязаных спісаў. Вы павінны ведаць адрас першага блока памяці таму што адтуль можна дабрацца да любога іншага. Даунсайд. Якую цану мы плацім за гэтую універсальнасць якія маюць дынамічнае значную структуру дадзеных, што калі мы калі-небудзь спатрэбіцца больш памяці, штраф, проста выдзеліць яшчэ адзін кавалак і намалюйце стрэлкі ад старога да новага хвасце спісу? Так. [Студэнт] Гэта займае прыкладна ўдвая больш прасторы. Яна займае ўдвая больш месца, так што гэта вызначана недахоп, і мы бачылі гэта Кампраміс, перш чым паміж часам і прасторай і гнуткасць дзе ў цяперашні час, нам не трэба 32 біт для кожнага з гэтых лікаў. Нам сапраўды трэба 64, 32 чысла і 32 для паказальніка. Але пачакайце, у мяне ёсць 2 гігабайта аператыўнай памяці. Даданне яшчэ 32 біта тут і тут не здаецца, што вялікія здзелкі. Але для вялікіх набораў дадзеных, гэта вызначана дадае літаральна ў два разы больш. Што яшчэ адным недахопам зараз, або тое, што функцыі мы здавацца, калі мы прадставім спісы рэчаў з звязанага спісу, а не масіў? [Студэнт] Вы не можаце прайсці ў зваротным кірунку. Вы не можаце прайсці ў зваротным кірунку, так што вы выгляд разьбовых калі вы ідзяце злева на права выкарыстання цыкла або час цыклу а потым разумееш: «О, я хачу вярнуцца ў пачатак спісу". Вы не можаце, таму што гэтыя паказальнікі ісці толькі злева направа, як стрэлкі паказваюць. 

Зараз, вы маглі ўспомніць пачатак спісу з іншай зменнай, але гэта складанасць мець на ўвазе. Масіваў, незалежна ад таго, як далёка вы пойдзеце, вы заўсёды можаце зрабіць мінус, мінус, мінус, мінус і вярнуцца, адкуль вы прыйшлі. Што яшчэ адным недахопам тут? Так. [Неразборліва пытанне студэнта] Можна, такім чынам, вы сапраўды толькі што прапанаваў структуру дадзеных, званую двойчы звязаны спіс, І сапраўды, можна дадаць яшчэ адзін паказальнік на кожны з гэтых прастакутнікаў , Які ідзе ў іншым накірунку, патэнцыял росту якіх Цяпер вы можаце прайсці туды і назад, Недахопам які ў цяперашні час вы выкарыстоўваеце ў тры разы больш памяці, чым мы прывыклі а таксама ўскладнення з пункту гледжання кода, вы павінны напісаць, каб атрымаць гэта права. Але ўсё гэта, магчыма, вельмі разумныя кампрамісы, калі зварот з'яўляецца больш важным. Так. [Студэнт] Вы таксама не можаце мець 2D звязанага спісу. Добра, вы не можаце сапраўды ёсць 2D звязаны спіс. Вы маглі б. Гэта не так проста, як масіў. Як і масіў, вы адкрывае дужкі, закрытая дужкі, якая адкрывае дужкі, закрытая дужкі, , І вы атрымаеце некаторы 2-мерных структуру. Вы можаце рэалізаваць 2-мерных звязаны спіс калі вы робіце дапаўненні, як вы прапанавалі, 1/3 паказальніка на кожную з гэтых рэчаў, і калі вы думаеце пра іншае спісе прыходзіць на вас 3D стыль з экрана ўсім нам, што гэта проста яшчэ адна ланцужок нейкі. Мы маглі б гэта зрабіць, але гэта не так проста, як друкаваць адкрытай дужкі, квадратныя дужкі. Так. [Неразборліва пытанне студэнта] Добра, так што гэта рэальны футбаліст. 

Гэтыя алгарытмы, якія мы тужылі па, як аб, бінарны пошук, Вы можаце шукаць масіў лікаў на дошцы або тэлефонную кнігу так значна хутчэй, калі вы выкарыстоўваеце падзяляй і ўладар і алгарытм двайковага пошуку, але бінарны пошук неабходных два здагадкі. Адзін з іх, што дадзеныя былі адсартаваныя. Цяпер мы можам па-відаць трымаць гэтую сартуюцца, так што, магчыма, гэта не мае значэння, але бінарны пошук Мяркуецца таксама, што вы мелі выпадковы доступ да спісу лікаў, і масіў дазваляе мець адвольны доступ, і выпадковага доступу, Я маю на ўвазе, калі вы гэтага масіва, колькі часу гэта зойме ў вас каб дабрацца да кранштэйна 0? Адна аперацыя, вы проста карыстаецеся [0], і вы тут жа. Колькі крокаў трэба для таго, каб дабрацца да размяшчэння 10? Адзін крок, вы проста ідзяце ў [10], і вы там. У адрозненне ад гэтага, як вы атрымліваеце па 10 лік у звязаным спісе? Вы павінны пачаць з самага пачатку, таму што вы толькі памятаючы пачатак звязанага спісу, як і радок у цяперашні час памятала па адрасе яе першы знак, і выявілі, што дзесятая Int або што дзесятая знакаў у радку, вы павінны шукаць ўсю гэтую чортаву рэч. 

Зноў жа, мы не рашэнне ўсіх нашых праблем. Мы ўяўляем новыя, але гэта залежыць ад таго, што вы спрабуеце праектаваць для. У плане рэалізацыі гэтага, мы можам запазычаць ідэі з гэтага студэнта структуры. Сінтаксіс вельмі падобны, толькі цяпер, ідэя трохі больш абстрактных чым дома, назву і ID. Але я прапаную, каб мы маглі мець структуру дадзеных у C што называецца вузлом, так як апошняе слова на слайд прапановы, Усярэдзіне вузла і вузел проста агульны кантэйнер ў кампутарнай навуцы. Гэта звычайна малюецца ў выглядзе круга або квадрата альбо прастакутніка, як мы зрабілі. І ў гэтай структуры дадзеных, у нас ёсць цэлы лік, N, так што гэта лік я хачу захаваць. Але што гэта другая лінія, структура вузла * далей? Чаму гэта правільна, альбо якую ролю гэтая рэч гульні, хоць гэта крыху загадкавае на першы погляд? Так. [Неразборліва адказ студэнта] Менавіта, таму * роду трафеі, што гэта паказальнік нейкі. Назва гэтага паказальніка калі заўгодна іншы, але мы маглі б назваў гэта ўсё, што мы хочам, але тое, што робіць гэты паказальнік паказвае на? [Студэнт] Іншы вузел. >> Сапраўды, ён паказвае на іншай такой вузел. 

Цяпер, гэта свайго роду цікаўнасць C. Нагадаем, што C чытаецца кампілятарам зверху ўніз, злева направа, што азначае, калі-гэта трохі адрозніваецца ад таго, што мы рабілі з вучнем. Калі мы вызначылі студэнт, мы на самай справе не ставіў слова там. Ён проста сказаў ЬурейеЕ. Тады ў нас была Int Ідэнтыфікатар, імя радкі, радкі дом, , А затым студэнтам у ніжняй частцы структуры. Гэта заяву трохі адрозніваецца, таму што, зноў жа, кампілятар гэта трохі дурное. Гэта толькі збіраецца чытаць зверху ўніз, Такім чынам, калі яно дасягае 2-й лініі тут дзе побач абвешчаны, і ён бачыць, ой, вось пераменная наступным. Гэта паказальнік на структуру вузла. Кампілятар будзе разумець, што гэта структура вузла? Я ніколі не чуў аб гэтай рэчы раней, таму што слова вузел не маглі б з'явіцца да дна, так што гэтая надмернасць. Вы павінны сказаць структуры вузлоў тут, якія затым можна скараціць у далейшым Дзякуючы ЬурейеЕ тут, але гэта таму, што Мы спасылкай на саму структуру ўнутры структуры. Гэта той, Гоча там. 

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

З значна больш задавальнення, калі яна разыгрываецца. Хто б літаральна хацеў быць першым? Добра, давай ўверх. Вы знаходзіцеся ў першую чаргу. Хто хацеў бы быць 9? Добра, 9. Як наконт 9? 17? Трохі кліку тут. 22 і 26 у гэтым шэрагу. І потым, як аб кім-то там, на якую спасылаюцца. Вы 34. Добра, 34, давай ўверх. Па-першае, гэта там. Добра, усе чатыры з вас, хлопцы. А хто ж мы гаворым на 9? Хто наш 9? Хто сапраўды хоча быць 9? Добра, давай, быць 9. Тут мы ідзем. 34, мы сустрэнемся з вамі там. Першая частка ўяўляе сабой зрабіць сабе выглядаць. 26, 22, 17, добра. Калі вы можаце стаяць у баку, таму што мы збіраемся Malloc вас у дадзены момант. 

Добра, добра. Добра, выдатна, так што давайце задаць пару пытанняў тут. А на самай справе, як цябе завуць? >> Аніта. Аніта, добра, ідзі сюды. Аніта збіраецца дапамагчы нам накшталт вырашыць адзін досыць простае пытанне ў першым, які, як вы лічыце, ці з'яўляецца значэнне знаходзіцца ў спісе? Зараз звернеце ўвагу, што, па-першае, прадстаўленыя тут Лукас, трохі адрозніваецца, і таму яго паперку ​​свядома бокам таму што гэта не так высокі і не займае столькі бітаў, хоць тэхнічна ён мае такі ж памер паперы, проста паварочваецца. Але ён крыху адрозніваецца тым, што ён усяго толькі 32 біт для паказальніка, і ўсе гэтыя хлопцы з'яўляюцца 64-бітнымі, палова з якіх гэты лік, палова з якіх з'яўляецца паказальнікам. Але паказальнік ня намалявана, так што калі вы, хлопцы, маглі б некалькі нязграбна выкарыстоўваць левую руку, каб паказаць на чалавека побач з вамі. І ты нумар 34. Як цябе клічуць? Ары. Ары, так што на самай справе, трымаць паперу ў правую руку, а левая рука ідзе ўніз. Вы ўяўляеце нулявы злева. 

Цяпер наша чалавечая карціна вельмі паслядоўныя. На самай справе гэта як паказальнікі працуюць. І калі вы паспрабуеце можа трохі Такім чынам, так што я не на вашым шляху. Аніта тут, знайсці мне нумар 22, але выказаць здагадку, абмежаванне не людзі, падняўшы паперкі, Але гэта спіс, і ў вас ёсць толькі Лукас з самага пачатку таму што ён літаральна першы паказальнік. Выкажам здагадку, што вы самі паказальнік, так што вы таксама маеце магчымасць паказаць на нешта. Чаму б вам не пачаць, паказваючы на ​​тое, што Лукас паказвае на? Добра, і дазвольце мне прыняць на гэта тут. Толькі дзеля абмеркавання, дазвольце мне падцягнуць пустую старонку тут. Як пішацца ваша імя? >> Аніта. Добра, Аніта. Дапусцім, вузел * Аніта = Лукас. Ну, мы не павінны называць вас Лукас. Мы павінны патэлефанаваць вам у першую чаргу. Чаму гэта на самай справе адпавядае рэчаіснасці тут? Адзін, першы ўжо існуе. Першае было выдзелена як мяркуецца, недзе тут. Node * Па-першае, і гэта было выдзелена спісу как-то. Я не ведаю, як гэта адбылося. Гэта адбылося да пачатку класа. Гэта звязана спіс людзей была створана. А зараз у гэты момант у гісторыі-гэта ўсё адбываецца на Facebook мабыць пазней на дадзены момант у гэтай гісторыі, Аніта была ініцыялізаваць роўнай першай, але гэта не значыць, што Аніта паказвае на Лукаса. Хутчэй за ўсё, яна паказвае на тое, што ён паказвае на таму што той жа адрас, што знаходзіцца ўнутры 32 біт Лукас - 1, 2, 3 - Цяпер і ўнутры 32 біт Аніта - 1, 2, 3. 

Цяпер знайдзіце 22. Як бы вы пра гэта? Што гэта? >> Кропка заўгодна. Каб навесьці курсор на любы іншы, так што ісці наперад і дзейнічаць яго як лепшае, што вы можаце тут. Добра, добра, і цяпер вы, паказваючы на ​​тое, што, як цябе клічуць з 22? Рамон. >> Рамон, так Рамон трымаецца 22. Вы ўжо зрабілі чэк. Хіба Рамон == 22, і калі так, напрыклад, мы можам вярнуцца дакладна. Дазвольце мне, у той час як гэтыя хлопцы стаяць тут некалькі нязграбна- Дазвольце мне зрабіць нешта хутка, як BOOL знайсці. Я збіраюся ісці наперад і казаць (спіс вузлоў *, Int N). Я хутка вярнуся з вамі, хлопцы. Мне проста трэба напісаць код. А цяпер я збіраюся ісці наперад і рабіць гэта, вузел * Аніта = спісе. І я буду ісці наперад і казаць у той час як (Анита! = NULL). 

Метафара тут становіцца трохі расцягнута, але ў той час (Анита! = NULL), што я хачу рабіць? Мне трэба нейкім чынам спасылкі цэлы лік, Аніта паказвае на. У мінулым, калі мы мелі структур, якія вузла, Мы выкарыстоўвалі пазначэнне кропкі, і мы хацелі б сказаць нешта накшталт: anita.n, але праблема ў тым, што Аніта не з'яўляецца структурай як такой. Што яна? Яна паказальнік, так што сапраўды, калі мы хочам выкарыстоўваць гэтую кропкавую натацыю- і гэта будзе выглядаць знарочыста трохі загадкава- Мы павінны зрабіць нешта накшталт пераходу на левай руцэ усё, што Аніта паказвае на , А затым атрымаць полі называецца п. Аніта з'яўляецца паказальнікам, але тое, што * Аніта? Што вы знаходзіце, калі вы ідзяце да таго, што Аніта паказвае на? Структуры, вузлоў і вузлоў, нагадаем, мае поле з назвай п таму што яна, нагадаем, гэтыя 2 поля, у наступным і п, , Які мы бачылі некалькі хвілін назад прама тут. 

Каб на самай справе імітаваць гэта ў кодзе, мы маглі б зрабіць гэта і кажуць, што калі ((* Anita). == п п), п, што я шукаў. Звярніце ўвагу, што функцыя была перададзена ў колькасці я клапачуся. Тады я магу ісці наперад і рабіць нешта накшталт вяртання праўда. У адваротным выпадку, калі гэта не так, што я хачу рабіць? Як перавесці ў код, што Аніта зрабіла гэта інтуітыўна, ідучы па спісе? Што я павінен рабіць тут, каб імітаваць Аніта гэтага кроку налева, што крок налева? [Неразборліва адказ студэнта] >> Што гэта такое? [Неразборліва адказ студэнта] Добра, не дрэнная ідэя, але ў мінулым, калі мы зрабілі гэта, мы зрабілі Аніта + + таму што гэта было дадаць лік ад 1 да Аніты, якія, як правіла, паказваюць на наступны чалавек, як Рамон, або асобай, побач з ім ці побач з ім тварам уніз лінію. Але гэта не зусім добра тут, таму што гэта рэч выглядаць у памяці? Не тое, каб. Мы павінны адключыць гэта. Падобна на тое, што гэта ў памяці, і, хоць я намаляваў 1 і 2 і 3 блізкія адзін да аднаго, калі мы сапраўды імітацыі гэтага, вы, хлопцы, у той жа час паказваючы на ​​тыя ж людзі, можа, некаторыя з вас прымаюць выпадковыя крок назад, некаторыя з вас выпадковы крок наперад? 

Гэтая чахарда па-ранейшаму звязанага спісу, але гэтыя хлопцы могуць быць дзе заўгодна ў памяці, так што Аніта + + не будзе працаваць, чаму? Што на месцы Аніта + +? Хто яго ведае. Гэта некаторыя іншыя значэнні, проста так здараецца быць устаўлены сярод усіх гэтых вузлоў выпадкова, таму што мы не выкарыстоўваем масіў. Мы вылучылі кожнаму з гэтых вузлоў па асобнасці. Добра, калі вы, хлопцы, можаце ачысціць сябе назад. Дазвольце мне прапанаваць, што замест Аніты + +, мы замест гэтага атрымлівае Аніта- Ну, чаму б нам не пайсці на любыя Аніта паказвае на тое і робім. Наступны? Іншымі словамі, мы ідзем да Рамон, які трымае нумар 22, і потым. наступная як быццам Аніта будзе капіяваць яго левы паказальнік руку. Але яна не хацела ісці далей, чым Ramon таму што мы знайшлі 22. Але гэта была б ідэя. Цяпер, гэта бог-жудасны беспарадак. Шчыра кажучы, ніхто ніколі не будзе памятаць гэты сінтаксіс, і таму, на шчасце, гэта на самай справе трохі наўмысным-ой, вы на самой справе не разумееце, што я напісаў. Гэта было б больш пераканаўчым, калі б маглі. Voila! 

За кулісамі, я быў вырашыць праблему такім чынам. Аніта, пайсці на гэты крок налева, Па-першае, мы сапраўды ідуць на адрас, які Аніта паказвае на і дзе яна знойдзе не толькі рускіх, якія мы толькі што праверыў для параўнання, але вы таксама знойдзеце наступную - у гэтым выпадку, Левай рукой Рамона, паказваючы на ​​наступны вузел у спісе. Але гэта бог-жудасны беспарадак пра якія я казаў раней, але аказваецца, C дазваляе нам спрасціць гэта. Замест лісты (* Anita), мы можам замест гэтага проста напісаць Аніта-> п, і гэта адно і тое ж функцыянальна, але гэта нашмат больш зразумелым, і гэта нашмат больш адпавядае з карцінай, якую мы прыцягвалі Увесь гэты час з дапамогай стрэлак. 

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

Зараз давайце паспрабуем яшчэ адзін. Аніта, вы хочаце, каб вярнуцца сюды? Чаму б нам не пайсці далей і вылучыць аднаго чалавека з аўдыторыі? Malloc-як цябе клічуць? >> Рэбека. Рэбека. Рэбека была malloced ад аўдыторыі, і зараз яна захоўваецца нумар 55. І мэта пад рукой цяпер для Аніты, каб ўставіць Рэбека ў звязаны спіс тут у адпаведным месцы. Давай сюды на хвілінку. Я зрабіў нешта накшталт гэтага. Я зрабіў вузел *. А што цябе клічуць? Рэбека. >> Рэбека, усё ў парадку. Рэбека атрымлівае таНос (SizeOf (вузла)). Гэтак жа, як мы выдзелілі такія рэчы, як студэнты і яшчэ шмат чаго ў мінулым, Мы маем патрэбу ў памеры вузла, так што зараз Рэбека паказвае на тое, што? Рэбека мае два поля ўнутры яе, адным з якіх з'яўляецца 55. Давайце рабіць тое, што, Рэбека-> = 55. Але тады Рэбека-> наступная павінна быць, як цяпер, яе рука гэта свайго роду хто ведае? Гэта паказвае на некаторы смецце значэнне, дык чаму б не для добрай мерай Мы па крайняй меры, зрабіць так, каб левая рука цяпер на яго баку. Цяпер Аніта, вазьмі яго адсюль. Вы павінны Рэбека таго, былі вылучаныя. Ідзем далей і знайсці, дзе мы павінны паставіць Рэбека. Добра, вельмі добра. Добра, добра, і зараз мы маем патрэбу ў вас, каб забяспечыць трохі кірунак, так што вы дасягнулі Ары. Яго левая рука з'яўляецца сапраўдным, але Рэбека, відавочна, належыць права, Так як жа мы павінны змяніць гэта звязаны спіс для таго, каб ўставіць Рэбека ў адпаведным месцы? Калі б вы маглі літаральна рухаць левай рукі людзей па ўсім меры неабходнасці, мы вырашыць гэтую праблему такім чынам. Добра, добра, а тым часам левая рука Рэбека цяпер на яго баку. 

Гэта было занадта проста. Давайце паспрабуем вылучэнне-Мы амаль скончылі, 20. Добра, давай ўверх. 20 былі вылучаныя, так што дазвольце мне ісці наперад і сказаць зноў тут мы толькі што зрабілі Саад вузел *. У нас ёсць таНос (SizeOf (вузла)). Затым мы робім дакладна такі ж сінтаксіс, як мы рабілі раней на 20, і я буду рабіць далей = NULL, і цяпер справа за Анітай ўставіць вас у звязаным спісе, калі б вы маглі гуляць, што дакладна такую ​​ж ролю. Выканаць. Добра, добра. Цяпер падумайце, перш чым пачаць рух левай рукі вакол. Вы на сённяшні дзень атрымалі самы нязручны ролю сёння. Чыя рука павінна быць перанесена ў першую чаргу? Добра, пачакай, я чую некаторых няма ў. Калі некаторыя людзі хацелі б ветліва, каб дапамагчы вырашыць няёмкую сітуацыю тут. Чыя левай рукой неабходна спачатку абнавіць магчыма? Так. [Студэнт] Саад аўтара. Добра, Саад, чаму, праўда? [Неразборліва адказ студэнта] Добра, таму што калі мы будзем рухацца, як цябе завуць? >> Маршал. Marshall, калі мы будзем рухацца руку спачатку ўніз да нуля, Цяпер мы ў літаральным сэнсе сіротамі чатырох чалавек у гэтым спісе таму што ён быў адзіным, паказваючы на ​​Рамона, і ўсе налева, так што абнаўленне паказальнікаў першы быў дрэнны. Давайце адмяніць гэта. Добра, а цяпер ідзіце наперад і перамясціць адпаведныя левай рукой, паказваючы на ​​Рамона. Гэта адчувае сябе крыху залішнім. Зараз ёсць два чалавекі, паказваючы на ​​Рамона, але гэта нармальна таму што цяпер, як яшчэ мы можам атрымаць спіс? Што з іншага боку павінен рухацца? Выдатна, зараз мы страцілі памяць? Не, так добра, давайце паглядзім, калі мы не можам разарваць гэты раз. 

Mallocing ў апошні раз, нумар 5. Усю дарогу ў спіну, давай ўніз. Гэта вельмі цікава. [Апладысменты] Як цябе клічуць? >> Рон. Рон, добра, вы malloced як нумар 5. Мы толькі выкананы код, які амаль ідэнтычныя гэтыя толькі з іншай назвай. Выдатна. Цяпер, Аніта, поспеху ўстаўкі № 5 у спісе цяпер. Добра, а? Выдатна, так што гэта сапраўды трэці з трох агульнага ліку выпадкаў. Спачатку быў хтосьці, у рэшце рэшт, Рэбека. У нас тады быў нехта ў сярэдзіне. Цяпер у нас ёсць хтосьці ў самым пачатку, і ў гэтым прыкладзе, у нас цяпер абнавіць Лукас ўпершыню таму што першы элемент у спісе зараз павінен паказваць на новы вузел, якія, у сваю чаргу, паказвае на нумар вузла 9. 

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

Давайце рэчы ў больш складаных кірунку да гэтага часу. Цяпер у нас ёсць паняцце звязанага спісу. У нас таксама ёсць, дзякуючы прапанове туды-двусвязный спіс, , Які выглядае амаль гэтак жа, але цяпер у нас ёсць два паказальніка ўнутры структуры замест аднаго, і мы маглі б, верагодна, назваць гэтыя паказальнікі папярэдняй і наступнай або налева або направа, але мы, на самай справе, патрэбныя два з іх. Код будзе крыху больш складана. Аніце прыйшлося б рабіць больш працы тут, на сцэне. Але мы, безумоўна, можа ажыццяўляць такую ​​структуру. З пункту гледжання часу працы, аднак, што было б час працы Аніта для знаходжання колькасці п ў звязаным спісе цяпер? Тым не менш вялікая O п, так што гэта не лепш, чым лінейны пошук. Мы не можам зрабіць бінарны пошук, хоць, зноў жа. Чаму гэта было так? Вы не можаце скакаць. Хоць мы, відавочна, усе людзі на сцэне, і Аніта магла б eyeballed яго і сказаў: "Вось сярэдзіне спісу" яна не будзе ведаць, што калі яна кампутарнай праграмы паколькі адзінае, што ёй давялося замкнуцца на ў пачатку сцэнара быў Лукас, які быў першым паказальнікам. Яна абавязкова павінна ісці за тымі спасылкамі, лічачы яе шляху, пакуль не знайшла прыкладна пасярэдзіне, і нават тады, яна не будзе ведаць, калі яна дасягнула сярэдзіны калі яна праходзіць ўвесь шлях да канца, каб высветліць, колькі ёсць, затым адступае, і, што таксама было б цяжка, калі вы не былі двусвязный спіс нейкі. 

Рашэнне некаторых праблем сёння, але ўвядзенне іншых. А як наконт розных структур дадзеных у цэлым? Гэта фотаздымак з латкоў у Mather House, і ў гэтым выпадку, у нас ёсць структура дадзеных, мы таксама выгляд ужо казалі. Мы гаварылі пра стэку ў кантэксце памяці, і гэта як бы наўмысна назвалі таму, што стэк ў тэрмінах памяці фактычна з'яўляецца структурай дадзеных, якая ўсё больш і больш рэчаў пласт па-над ёй. Але самае цікавае пра стэку, як гэта мае месца ў рэчаіснасці, тое, што гэта адмысловы выгляд структуры дадзеных. Гэта структура дадзеных, прычым першы элемент гэта апошні элемент з. Калі вы першы латок ставіць у стэк, Вы збіраецеся быць, на жаль, апошні латка павінны быць прыняты стэка, і гэта не заўсёды добра. І наадварот, вы можаце думаць пра яго наадварот, У апошні з'яўляецца першым з. 

Цяпер, любыя сцэнары прыходзяць на розум, дзе, маючы стэк структура дадзеных, дзе ў вас ёсць, што ўласнасць апошнія увайшоў, першым выйшаў, на самай справе пераканаўчым? Хіба гэта добра? Хіба гэта дрэнна? Гэта, безумоўна, дрэнна, калі латкоў не былі ўсе аднолькавыя і ўсе яны былі адмысловым розных колераў і яшчэ шмат чаго, і колер вы хочаце, усю дарогу ўнізе. Вядома, вы не можаце атрымаць, што без вялікіх высілкаў. Вы павінны пачаць з верхняй і працаваць ваш шлях ўніз. Сапраўды гэтак жа, як калі б вы былі адным з гэтых вентылятараў хлопчыкаў хто чакае ўсю ноч, спрабуючы атрымаць iPhone і ліній да у такім месцы, як гэта? Хіба не было б выдатна, калі б у Apple Store былі структуру стэка дадзеных? Ура? Мала таго? Гэта толькі для людзей, якія з'яўляюцца ў апошняй хвіліны , А затым атрымаць сарваў чарзе. І на самай справе, той факт, што я быў так схільны казаць чаргу на самай справе адпавядае таму, што мы б назвалі такую ​​структуру дадзеных, адзін у рэальнасці, дзе парадак мае значэнне, і вы хочаце першы, каб быць першай з калі толькі дзеля чалавечай справядлівасці. Мы звычайна называем гэта структура дадзеных чарзе. 

Аказваецца, акрамя звязаных спісаў, мы можам пачаць выкарыстоўваць гэтыя ж асноўныя ідэі і пачаць ствараць новае і розныя тыпы рашэнняў праблем. Напрыклад, у выпадку стэка, мы маглі б прадстаўляць сабой стэк , Выкарыстоўваючы структуру дадзеных, як гэта, я хацеў бы прапанаваць. У гэтым выпадку, я абвясціў структуры, і я ўжо казаў ўнутры гэтай структуры ўяўляе сабой масіў лікаў, а затым пераменная памеры, і Я буду называць гэтую рэч стэка. Цяпер, чаму гэта сапраўды працуе? У выпадку стэк, я мог бы зрабіць гэта эфектыўна на экране ў выглядзе масіва. Вось мой стэк. Такія мае нумары. І мы будзем маляваць іх, як гэта, гэта, гэта, гэта, гэта. А то ў мяне некаторыя іншыя члены дадзеных тут, якая называецца памер, так гэта памер, і гэта лікі, і калектыўна, усёй Ipad тут прадстаўляе сабой адзін стэк структуры. Цяпер, па змаўчанні, памер як мяркуецца, павінен быць ініцыялізаваны да 0, і тое, што ўнутры масіва лікаў першапачаткова Калі я ўпершыню вылучыць масіў? Garbage. Хто ведае? І гэта на самай справе не мае значэння. Гэта не мае значэння, калі гэта 1, 2, 3, 4, 5, цалкам выпадкова на нешанцаванне, якія захоўваюцца ў маёй структуры, таму што пакуль я ведаю, што памер стэка роўны 0, то я ведаю, праграмным, не глядзі на любы з элементаў у масіве. Гэта не мае значэння, што там. Не глядзі на іх, як бы следства памеры 0. 

Але выкажам здагадку, што цяпер я іду наперад і ўставіць нешта ў стэк. Я хачу, каб ўставіць нумар 5, так што я паклаў № 5 тут, і тое што я магу паставіць сюды? Зараз я бы на самай справе паклаў 1 для памеру, і ў цяперашні час стэк мае памер 1. Што рабіць, калі я іду наперад і ўставіць лік, скажам, 7 след? Гэта тое абнаўляецца да 2, а затым мы будзем рабіць 9, а затым гэтая абнаўляецца да 3. Але цікавая асаблівасць зараз гэты стэк з'яўляецца тое, што Я павінен выдаліць элемент якога, калі я хачу ўсплываў нешта з стэка, так бы мовіць? 9 была б першае, што трэба ісці. Як вынікае карціна зменіцца, калі я хачу поп элемент з стэка, хацелася латок Mather? Так. >> [Студэнт] Устанавіць памер да 2. Сапраўды, усё, што я зрабіць, гэта ўсталяваць памер 2, і што мне рабіць з масівам? Я не маю нічога рабіць. Я мог бы, проста каб быць анальны, пакласці 0 існуе, або -1 ці нешта азначаюць, што гэта не законна значэнне, але гэта не мае значэння, таму што Я магу запісваць за межамі самога масіва, як доўга гэта так што я ведаю толькі паглядзіце на першыя два элемента ў гэтым масіве. Цяпер, калі я пайду і дадайце нумар 8 да гэтага масіва, якім чынам карціна зменіцца наступным? Гэта становіцца 8, і гэта становіцца 3. Я рэзкі некалькі кутоў тут. Цяпер у нас ёсць 5, 7, 8, і мы вярнуліся да памеру 3. Гэта даволі просты ў рэалізацыі, Але калі мы будзем шкадаваць пра гэта дызайнерскае рашэнне? Калі рэчы пачынаюць ісці вельмі, вельмі няправільна? Так. [Неразборліва адказ студэнта] Калі вы хочаце, каб вярнуцца і атрымаць першы элемент, які уставіў 

Пры гэтым аказваецца, нават калі стэк ўяўляе сабой масіў пад капотам, гэтыя структуры дадзеных, мы пачалі казаць пра таксама вядомы як абстрактных структур дадзеных, якім, як яны рэалізуюцца цалкам, акрамя кропкі. Структура дадзеных, як стэк мяркуецца дадаць падтрымку аперацый, такіх як штуршок, які штурхае латок ў стэк, і поп-музыкі, якая выдаляе элемент з стэка, і гэта ўсё. Калі б вы загрузіце чужой код, які ўжо рэалізаваны тое, што называецца стэкам, што чалавек напісаў бы толькі дзве функцыі для вас, штурхаць і поп-музыкі, чыя адзіная мэта ў жыцці было б зрабіць менавіта гэта. Вы ці яго ці яе, хто ажыццяўляў гэтую праграму быў бы зусім адзін, каб вырашыць, як рэалізаваць Семантыка націску і з'яўляюцца пад капотам або функцыянальнасць націску і з'яўляюцца. І я зрабіў некалькі блізарукім рашэннем тут шляхам рэалізацыі свайго стэка з гэтай простай структурай дадзеных, то чаму? Калі ж гэты разрыў структуры дадзеных? У які момант я павінен вяртаць памылку, калі карыстач выклікае штуршок, напрыклад? [Студэнт] Калі няма больш месца. Менавіта, калі няма больш месца, калі я перавысіў ёмістасць, які ўсё загалоўныя літары, паколькі яна мяркуе, што гэта свайго роду глабальная канстанта. Ну, тады я проста хачу, каб сказаць: «Прабачце, я не магу вылучыць яшчэ адно значэнне ў стэк ", як у Mather. 

У нейкі момант яны збіраюцца патрапіць у верхнюю частку гэтага маленькага кабінета. Там няма больш месца або магутнасці ў стэку, і ў гэты момант там нейкая памылка. Яны павінны паставіць элемент дзесьці ў іншым месцы, латок дзесьці ў іншым месцы, ці ўвогуле нікуды. Цяпер, з чаргой, мы маглі б рэалізаваць гэта крыху па-іншаму. Чарга трохі адрозніваецца тым, што пад капотам, ён можа быць рэалізаваны як масіў, але чаму, у такім выпадку, я прапаную таксама ёсць галава элемент, які ўяўляе кіраўніка спісу, Перад спісу, першы чалавек у чарзе ў краму Apple, у дадатак да памеру? Навошта патрэбна дадатковая порцыя дадзеных тут? Успомніце, якія нумары ёсць калі я намаляваў яго наступным чынам. Хай гэта цяпер чэргі замест таго, каб стэк, розніца ў тым, як Apple Store ў чарзе справядліва. Першы чалавек у чарзе ў пачатак спісу, нумар 5 у гэтым выпадку, ён ці яна будзе даваць у краме ў першую чаргу. Давайце зробім гэта. Выкажам здагадку, што гэта стан маёй чэргі ў дадзены момант часу, і цяпер у Apple Store адкрываецца, і першая асоба, нумар 5, накіроўваецца ў краму. Як я магу змяніць карціну цяпер, калі я дэ-чарзе першай асобы на пярэдняй лініі? Што гэта? >> [Студэнт] Змены ў чарзе. Змена галавой, так што 5 знікае. На самай справе, гэта, як быццам, як лепш гэта зрабіць? На самай справе, гэта як быццам гэты хлопец знікае. Што б нумар 7 робім у рэальнай краме? Яны б зрабіць вялікі крок наперад. 

Але што мы прыйшлі да разумення, калі гаворка ідзе пра масівах і перамяшчэння рэчаў вакол? Гэта свайго роду пустая трата часу, так? Чаму вы павінны быць настолькі анальны, каб мець першай асобы У пачатку лініі на фізічным пачатак блока памяці? Гэта зусім не трэба. Чаму? Што можа я проста памятаю, а? >> [Неразборліва адказ студэнта] Сапраўды, я мог бы проста памятаю, з гэтай дадатковай галоўкай члена дадзеных што цяпер кіраўнік спіс не 0, што гэта было хвіліну таму. Цяпер гэта на самай справе нумар 1. Такім чынам, я атрымліваю невялікую аптымізацыю. Проста таму, што я дэ-чарзе хтосьці з лініі ў пачатку лініі ў Apple Store не азначае, што кожны павінен перамяшчацца, што нагадаем, з'яўляецца лінейнай аперацыяй. Я магу замест гэтага праводзіць пастаянную часу толькі і дасягненні, то значна хутчэй адказ. Але цана, якую я плачу гэта тое, што каб атрымаць, што дадатковая прадукцыйнасць і не маюць перакласці ўсё? Так. >> [Неразборліва адказ студэнта] Можна дадаць больш людзей, добра, што праблема артаганальнай з тым, што мы не перакладаючы людзей вакол. Ён па-ранейшаму масіва, ці так мы перакласці ўсё або не- О, я бачу, што вы маеце на ўвазе, добра. На самай справе, я згодны з тым, што вы кажаце, што ён амаль як калі б Мы зараз ніколі не будзе выкарыстоўваць пачатку гэтага масіва больш таму што, калі я выдалю 5, то я магу выдаліць 7. Але я толькі паставіць людзей з правага боку. 

Ён адчувае, як я марнаваць прастору, і ў выніку мая чарга распадаецца наогул нічога, такім чынам, мы маглі б проста ёсць людзі, пахам, і мы маглі думаць пра гэта масіў сапраўды як свайго роду кругавая структура, але мы выкарыстоўваем тое, што аператар C, каб рабіць такога роду пахам? [Неразборліва адказ студэнта] >> аператара па модулю. Было б крыху раздражняе прадумаць, як вы будзеце рабіць з пахам, але мы маглі б гэта зрабіць, і мы маглі пачаць збіраць людзей на тое, што раней пярэдняй лініі, але мы проста памятаем з гэтай галавой пераменная якія фактычнага кіраўніка лінія на самай справе. Што, калі, замест гэтага, наша мэта ў канчатковым выніку, аднак, было шукаць ліку, як мы зрабілі тут, на сцэне з Анітай, але мы сапраўды хочам лепшай з усіх гэтых мірах? Мы хочам больш складанасці, чым масіў дазваляе таму што мы хочам магчымасць дынамічна расці структуры дадзеных. Але мы не хочам звяртацца да таго, што мы паказалі, У першай лекцыі не быў аптымальным алгарытмам, , Што лінейнага пошуку. Аказваецца, што можна, на самай справе, дасягненні або па крайняй меры блізка да сталай часу, у выніку чаго хтосьці, як Аніта, калі яна настройвае яе структуру дадзеных, каб не быць звязаным спісам, каб не быць стэк, каб не быць чэргаў, можа, на самай справе, прыдумаць структуру дадзеных, якая дазваляе ёй шукаць рэчы, нават словы, а не проста лічбы, у тым, што мы будзем называць сталай часу. 

І на самай справе, забягаючы наперад, адна з psets ў гэтым класе амаль заўсёды ажыццяўленне праверкі правапісу, у выніку чаго мы даем вам зноў каля 150000 ангельскіх слоў і мэта загрузіць у памяць тых, і хутка зможа адказаць на пытанні аб форме гэтае слова напісана правільна? І гэта было б сапраўды смактаць, калі вам давялося перабрацца ўсе 150000 слоў, каб адказаць на гэтае пытанне. Але, на самой справе, мы ўбачым, што мы можам зрабіць гэта ў вельмі, вельмі хуткае час. І гэта будзе ўключаць ажыццяўленне так званых Хэш-табліцы, І хоць на першы погляд гэта тое, што называецца хэш-табліцы будзе Давайце дасягнення гэтых супер хуткага рэагавання, Аказваецца, што ёсць на самой справе праблема. Калі прыходзіць час для ажыццяўлення гэтага, што называецца, зноў жа, я раблю гэта зноў. Я толькі тут. Калі прыходзіць час для ажыццяўлення гэтай рэчы, званай хэш-табліцы, мы будзем мець, каб прыняць рашэнне. Якім павінен гэтую рэч на самай справе быць? І калі мы пачынаем ўстаўкі лічбаў у гэтай хэш-табліцы, як мы будзем захоўваць іх такім чынам, што мы можам атрымаць іх назад так хутка, як мы атрымалі іх? Але мы ўбачым неўзабаве, што гэтае пытанне калі дзень нараджэння кожнага чалавека ў класе будзе цалкам дарэчным. Аказваецца, што ў гэтым пакоі, у нас ёсць некалькі сотняў чалавек, так што верагоднасць таго, што два з нас ёсць той жа дзень нараджэння, верагодна, даволі высокая. Што, калі там былі толькі 40 з нас у гэтай пакоі? Якія шанцы двух людзей, якія маюць той жа дзень нараджэння? [Студэнты] Звыш 50%. Так, больш чым на 50%. На самай справе, я нават прынёс графік. Аказваецца, і гэта на самай справе проста папярэдні прагляд- калі ёсць толькі 58 з нас у гэтай зале, верагоднасць таго, 2 з нас які мае той жа дзень нараджэння з'яўляецца надзвычай высокім, амаль 100%, і што збіраецца выклікаць цэлы букет балюча для нас у сераду. 

З улікам сказанага, давайце адкладзем тут. Мы будзем бачыць Вас у сераду. [Апладысменты] [CS50.TV]