[Гуляе музыка] [Прайграванне відэа] -Ён Хлусіць. -О Чым? -Не ведаю. -Так Што мы ведаем? -Гэта У 9:15, Рэй Сантойя быў у банкамаце. -Так. Такім чынам, пытанне, што ён робіць у 09:16? -Съемки 9-міліметровага на нешта. Можа быць, ён убачыў снайпера. Ужо ці не разагнаўся Працаваў з ім. Пачакай. Зварот на адзін. -Што Ты бачыш? -Bring Яго тварам уверх поўным экране. -яго Ачкі. -Ёсць Гэта адлюстраванне. -Гэта Бейсбольнай каманды Nuevitas. Гэта іх лагатып. -А Ён размаўляе з хто носіць гэтую куртку. [КАНЕЦ ПРАГЛЯДУ] Дэвід малая: Добра. Гэта CS50 і гэта трохі больш з [неразборліва], з якой вы ўмешваюцца з праблемай ўсталяваць чатыры. Сёння мы пачынаем выглядаць трохі больш глыбока ў гэтых рэчах, званых паказальнікаў, які, хоць гэта даволі таямніцай тэма, Аказваецца, што ён збіраецца быць сродкам, з дапамогай якога мы можа пачаць будаўніцтва і мантаж значна больш складаныя праграмы. Але мы зрабілі гэта ў апошнюю сераду пасродкам некаторага claymation першай. Так што гэта, нагадаем, з'яўляецца Бинки, і мы выкарыстоўвалі яго каб зірнуць на праграму, якая ня сапраўды што-небудзь цікавае, але ён раскрыць некалькі праблем. Такім чынам, каб пачаць сёння, чаму мы не хадзіць хутка праз некалькі з гэтых крокаў, паспрабуйце, каб адагнаць ва ўмовах чалавечы ў менавіта тое, што тут адбываецца і чаму гэта дрэнна, а затым перайсці на а на самай справе пачаць будаваць нешта з гэтай тэхнікай? Так што гэта былі першы дзве лініі гэтай праграмы і з пункту гледжання непрафесіяналы, тое, што якія гэтыя дзве лініі робяць? Хтосьці, хто досыць камфортна з тым, што заявіў на экране? Якія гэтыя дзве лініі робяць? Гэта не ўсё, што адрозніваецца ад тыдня адзін, але ёсць некаторыя новыя спецыяльныя сімвалы. Да? Вярнуцца там. АЎДЫТОРЫЯ: Аб'ява паказальнікі? Дэвід малая: раз сказаць? АЎДЫТОРЫЯ: Аб'ява паказальнікі? Дэвід малая: Аб'ява паказальнікі і давайце ўдакладніць яго крыху больш. АЎДЫТОРЫЯ: [неразборліва] адрас, а затым х у. Дэвід малая: А потым звярнуцца. Так што канкрэтна мы робім што мы аб'яўляем дзве зменныя. Гэтыя зменныя, хоць, збіраюцца да тыпу INT зоркі, больш канкрэтна азначае яны збіраюцца захоўваць адрас з Int, адпаведна, х і у. Зараз ёсць якія-небудзь каштоўнасці? Ці ёсць нейкія фактычны адрасы ў іх дзве зменныя ў дадзены момант? Няма. Гэта проста так называецца значэння смецця. Калі вы на самой справе не прызначаць Пераменная, усё, што было ў памяці раней збіраецца запоўніць нулямі і тыя, абодва з гэтых зменных. Але мы яшчэ не ведаем, якія яны ёсць, і гэта будзе ключом да чаму Binky страціў галаву на мінулым тыдні. Так што гэта быў claymation Ўвасабленне гэтага у выніку чаго ў вас ёсць толькі дзве зменныя, маленькія кругавыя часткі гліны, які можа захоўваць зменныя, але, як абгорнутых стрэлкі прапанаваць, яны на самой справе не паказваючы у любую кропку па сабе вядомыя. Такім чынам, мы мелі гэтую лінію, і гэта была новай на мінулым тыдні, Таноса на памяць размеркаванне, які з'яўляецца толькі мудрагелісты спосаб распавядаць аперацыйную сістэму Linux, або Mac OS або Windows, Цэнтр эй, дайце мне памяць, і ўсё, што вы павінны сказаць аперацыйная сістэма гэта тое, што, калі яго просяць на памяць. Гэта не збіраецца клапаціцца, што Вы збіраецеся з ім рабіць, але вы павінны сказаць аперацыйнай Сістэма, што шляхам Таноса. Да? АЎДЫТОРЫЯ: Колькі? Дэвід малая: Колькі? Наколькі ў байтах, а гэта так, то, зноў жа, надуманы прыклад, проста кажучы, даць мне памер у міжнар. Цяпер, памерам з Int чатыры байта ці 32 біта. Так што гэта проста спосаб кажучы, эй, аперацыйная сістэма, дайце мне чатыры байта памяці што я магу выкарыстоўваць у маім распараджэнні, і, у прыватнасці, тое, што робіць Таноса вяртанне па у гэтым фрагменце з чатырох байтаў? АЎДЫТОРЫЯ: Адрас? Дэвід малая: Адрас. Адрас гэтай порцыі з чатырох байтаў. Дакладна. І вось што ў канчатковым рахунку захоўваецца х, і таму мы сапраўды ня ўсё роўна, што колькасць, што адрас, няхай гэта будзе OX1 ці OX2 ці некаторыя загадкавыя адрас шаснаццатковай. Мы проста клапоцімся графічна што пераменная х цяпер паказваючы на ​​тое кавалак памяці. Такім чынам, стрэлка ўяўляе сабой паказальнік або Больш канкрэтна, адрас памяці. Але, зноў жа, мы звычайна не клапоцяцца што гэтыя фактычныя адрасы. Цяпер, кажа, што гэта лінія тое, што з пункту гледжання непрафесіяналы? Зорка х атрымлівае 42 з коскі. Што гэта значыць? Ты хочаш пайсці? Не падрапаць вашу шыю. Аўдыторыя: адрас х знаходзіцца ў 42. Дэвід малая: Адрас х знаходзіцца ў 42. Не зусім. Так блізка, але не зусім, таму што ёсць зорка, якая, папярэднічаючы гэты х. Такім чынам, мы павінны наладзіць няшмат. Да? АЎДЫТОРЫЯ: Значэнне, якое Паказальнік х паказваючы на ​​гэта 42. Дэвід малая: ОК. Значэнне, паказальнік х паказваючы на, скажам, будзе 42, або іншымі словамі, зоркі х кажа, перайдзіце да любой адрас у х, няхай гэта будзе 1 Оксфард Вуліца або 33 Оксфард-стрыт або OX1 ці ox33, незалежна што лікавае адрас, зоркавы х з'яўляецца разнаймення х. Так што па гэтым адрасе і Затым пакласці туды лік 42. Так што было б Эквівалентны спосаб сказаць, што. Так што ўсё нармальна, а затым мы будзе прадстаўляць карціну наступным, дзе мы дадалі 42 да гэтага кавалак чатырох байты на правай баку, але Гэтая лінія была, дзе ўсё пайшло наперакасяк і кіраўнік Бинки выскачыў ад ў гэтай кропцы, таму што дрэнныя рэчы здараюцца, калі Вы разнаймення значэння для смецця ці вы разнаймення несапраўдным паказальнікі, і я кажу несапраўдным таму што ў дадзены момант у гісторыя, тое, што знаходзіцца ўнутры ў? Што значэнне у на аснове на апошнія некалькі крокаў? Да? Што гэта? АЎДЫТОРЫЯ: адрас. Дэвід малая: адрас. Гэта павінен быць адрас але я яе ініцыялізацыі? Так што ў мяне яшчэ няма. Так што, як вядома, там? Гэта проста некаторы значэнне смецця. Гэта можа быць любы адрас ад нуля да 2 млрд, калі ў вас ёсць два гігабайтамі аператыўнай памяці, або ад нуля да 4 млрд калі ў Вас ёсць атрымаў чатыры гігабайта аператыўнай памяці. Гэта некаторы значэнне смецця, але праблема ў тым, што ў аперацыйнай сістэме, калі ён не даў вам што частка памяці спецыяльна што вы спрабуеце ісці, гэта наогул будзе выклікаць што мы бачылі, як памылкі сегментацыі. Такім чынам, на самай справе, любы з вас, хто змагаўся на праблемы ў працоўны час або ў праблемах, якія больш як правіла, у спробе высветліць, памылкі сегментацыі, што звычайна азначае, ты датыкаешся сегмент памяці, што вы не павінны быць. Вы дакранаючыся памяці, аперацыйная сістэма не мае дазволіў вам дакрануцца, няхай гэта будзе па заходзіць занадта далёка ў вашым масіве ці пачынаючы з сённяшняга дня, будзь гэта таму, што ты датыкаешся памяці, проста некаторы значэнне смецця. Так робяць зоркі х тут накшталт нявызначанага паводзін. Вы ніколі не павінны рабіць гэта, таму што шанцы якія, праграма проста будзе крах, таму што вы кажаце, перайсці на гэты адрас і вы паняцця не маю, дзе што адрас на самай справе. Такім чынам, аперацыйная сістэма, хутчэй за ўсё, збіраецца да краху праграмы у выніку і на самай справе, што гэта што там адбылося на Бинки. Так у канчатковым рахунку, Бинки фіксаванай гэтая праблема з гэтым. Так гэтай праграмы сам быў сапсаваны. Але калі вы як бы прасоўвацца наперад і выканаць гэты радок замест у роўны х проста азначае тое, што адрас з'яўляецца х, таксама пакласці яго ў у. І так наглядна, мы прадстаўлены ў гэтым з двума стрэлкамі ад х і ад у паказваючы у тое ж месца. Так семантычна, х роўны каб у таму што абодва з іх захоўваеце той жа адрас, такім чынам, паказваючы на ​​42, і цяпер, калі вы кажаце, зоркі у, перайсці па адрасе ў к, гэта мае цікавы пабочны эфект. Такім чынам, адрас у ў з'яўляецца Тое ж самае, як адрас у х. Так што, калі вы кажаце, ісці па адрасе у у і зменіце значэнне на 13, хто яшчэ ўплывае? Х, кропка D, так бы мовіць, павінны быць закрануты таксама. І на самай справе, як Нік звярнуў гэтую карціну у claymation менавіта гэта. Нават калі мы будзем прытрымлівацца паказальнік у, мы апынуліся ў тым жа месцы, і таму, калі мы павінны былі раздрукаваць з х ці pointee Y, у то мы ўбачылі б значэнне 13. Зараз, я кажу pointee быць у адпаведнасці з відэа. Праграмісты, на мой веданне, на самай справе ніколі не кажуць слова pointee, што з'яўляецца вострым у, але для паслядоўнасці з відэа, разумеюць, гэта ўсё, што было азначала ў такой сітуацыі. Дык якія-небудзь пытанні па claymation або паказальнікі або Таноса толькі пакуль? Няма? Добра. Так што без далейшага шуму, давайце зірнем у якім гэта мае на самай справе былі выкарыстаныя на працягу некаторага часу. Такім чынам, мы мелі гэтую бібліятэку CS50 што ёсць усе гэтыя функцыі. Мы выкарыстоўвалі GetInt шмат, GetString, верагодна, GetLongLong раней ў маім Pset адзін або так, але што на самой справе адбываецца? Ну, давайце зірнем пад капотам на праграму, якая натхняе таму мы даем вам CS50 бібліятэка, і на самай справе, як на мінулым тыдні, мы пачалі прымаць тых, навучальныя колы ад. Так што гэта зараз сартуюцца з таго, што пасмяротных мае ўжо на у бібліятэцы CS50, нават калі мы зараз пачне рухацца ад яго для большасці праграм. Так што гэта праграма называецца зсапЕ 0. Гэта супер кароткі. Гэта проста ёсць гэтыя радкі, але гэта уводзіць функцыю называюць зсапЕ што мы на самай справе адбываецца, каб бачыць у момант ўнутры бібліятэкі CS50, хоць і ў некалькі іншай форме. Так што гэта праграма на лініі 16 аб'яўляе зменную х. Так дайце мне чатыры байта для Int. Гэта было распавядаць карыстачу, Колькасць калі ласка, а затым гэта цікава, што лінія на самай справе звязвае мінулым тыдні і гэта. Scanf, і звярніце ўвагу на тое, што займае Радок фармату, як Printf, % Я азначае Int, а затым яна займае Другі аргумент, які выглядае крыху фанкі. Гэта Ампэрсанд х, і ўспомніць, мы бачылі толькі адзін раз на мінулым тыдні. Што Ампэрсанд х ўяўляюць? Што рабіць у Ампэрсанд C? Да? Аўдыторыя: адрас. Дэвід малая: Адрас. Так гэта наадварот зорнага аператара, у той час як зорка аператар кажа, перайдзіце да гэты адрас, Ампэрсанд аператар кажа, высветліць адрас гэтай зменнай, і такім чынам гэта з'яўляецца ключавым, таму што Мэта Scanf ў жыцці гэта для сканавання карыстальніка ўвесці з клавіятуры, у залежнасці ад усё, што ён ці яна тыпы, а затым чытаць ўвод дадзенага карыстальніка ў зменную, але мы бачылі ў апошнія два тыдні што гэтая функцыя падпампоўкі, што мы спрабаваў намаганняў для рэалізацыі проста разбітыя. Нагадаем, што з функцыяй падпампоўкі, калі мы толькі што абвясцілі А і У, цэлых лікаў, мы сапраўды паспяхова своп дзве зменныя ўнутры своп проста падабаецца з малаком і OJ, але як толькі вярнуўся падпампоўкі, які быў вынік па х і у, арыгінальныя значэння? Нічога. Так. Нічога не адбылося, што час, таму што свопы змяніць толькі свае лакальныя копіі, які павінен сказаць, усё на гэты раз, кожны раз, калі мы ў былі перадаючы аргументаў да функцый, мы проста праходзячы копіі гэтых аргументаў. Вы можаце рабіць з гэтым што вы хочаце з імі, але яны збіраюцца мець не Ўплыў на зыходныя значэння. Так што гэта праблематычна, калі вам хочаце мець функцыю, як зсапЕ у жыцці, мэта якога складаецца ў сканаванні уваход карыстальніка з клавіятуры а затым запоўніць прабелы, так кажуць, што гэта, даюць зменную х, як значэнне, таму што, калі б я быў проста перадаць х у Scanf, калі вы лічыце, логіку ў мінулым тыдзень, зсапЕ можа рабіць усё, што ён хоча з копіяй х, але яна не магла назаўжды змяніць х, калі мы не дамо Scanf карту скарбаў, так бы мовіць, дзе х пазначае месца, у выніку чаго мы праходзім ў адрас х, так што зсапЕ можаце пайсці туды і фактычна змена значэнне х. І так сапраўды, усё што гэтая праграма робіць калі я зсапЕ 0, на мой крыніцы Каталог 5м, зрабіць зсапЕ 0, кропка слэш зсапЕ, нумар калі ласка, 50, дзякуй за 50. Так што гэта не ўсё, што цікава, Але тое, што сапраўды адбываецца з'яўляецца тое, што, як толькі я называю Scanf тут, значэнне х у цяперашні час пастаянна змяняецца. Цяпер, гэта, здаецца, добры і добра, а на самай справе, гэта Падобна на тое, мы сапраўды не трэба бібліятэка CS50 наогул больш. Напрыклад, давайце працаваць гэта яшчэ раз тут. Дазвольце мне адкрыць яго на працягу секунды. Давайце паспрабуем нумар, калі ласка, і замест таго каб сказаць 50, як раней, давайце проста сказаць няма. ОК, гэта крыху дзіўна. ДОБРА. І толькі некаторыя глупства тут. Так што, здаецца, не апрацоўваць памылковыя сітуацыі. Такім чынам, мы павінны мінімальна старт дадаўшы некаторыя праверкі памылак каб пераканацца, што карыстальнік мае надрукаваная ў фактычная колькасць як 50, таму што відавочна набраўшы слоў не выяўлена праблематычным, але гэта, верагодна, павінна быць. Давайце паглядзім на гэтую версію цяпер гэта мая спроба перавызначыць GetString. Калі зсапЕ ўсё гэта мае Функцыянальнасць убудаваная, чаму мы былі з імі песціцца навучальныя дыскі, як GetString? Ну, вось, мабыць, мая ўласная простая версія GetString у выніку чаго тыдзень таму, я б сказаў даць мне радок і называюць гэта буфер. Сёння, я збіраюся пачаць толькі кажучы сЬаг зоркі, які, нагадаем, гэта проста сінонімы. Гэта выглядае страшней, але гэта дакладна такая ж рэч. Так дайце мне зменнай называецца буфер што збіраецца захоўваць радок, скажыце калі ласка, радок карыстальніка, а затым, як і раней, давайце паспрабуем заняць гэты ўрок зсапЕ % S гэты час, а затым перадаць у буферы. Цяпер, хуткая праверка здаровае. Чаму я не кажу, Ампэрсанд буфер на гэты раз? Вывад з папярэдняга прыкладу. АЎДЫТОРЫЯ: Чар зорка паказальнік. Дэвід малая: Роўна, таму што гэты час, гольца зорка ўжо паказальнік, адрас, па вызначэнні гэтай зоркі быць там. І калі зсапЕ чакае адрас, дастаткова толькі прайсці ў буферы. Мне не трэба, каб сказаць, Ампэрсанд буфер. Для цікаўных, вы маглі б зрабіць нешта накшталт гэтага. Гэта будзе мець іншае значэнне. Гэта дасць вам паказальнік на паказальнік, які на самай справе сапраўдны рэч у C, але для Цяпер, давайце трымаць яго простая і трымаць гісторыю ў адпаведнасці. Я проста хачу, каб перадаць у буфер і гэта правільна. Праблема, аднак, заключаецца ў наступным. Дазвольце мне ісці наперад і працаваць у гэтым Праграма пасля кампіляцыі. Зрабіць зсапЕ 1. Чорт вазьмі, мой кампілятара лавіць сваю памылку. Дайце мне адну секунду. Clang. Скажам Scanf-1.c. ДОБРА. Там мы ідзем. Мне гэта трэба. CS50 ID мае розныя Параметры канфігурацыі што абароніць вас ад сябе. Мне трэба адключыць тыя, па працуе ляск уручную ў гэты раз. Так радок калі ласка. Я збіраюся ісці наперад і ўвесці у маім каханым свеце прывітанне. ОК, нуль. Гэта не тое, што я набраў. Так што гэта сведчыць аб то памыліцца. Дазвольце мне ісці наперад і ўвесці на самай справе доўгай радкі. Падзяку за нуль, і я не ведаю, калі я збіраюся быць у стане разбіць яго. Давайце паспрабуем трохі копію ўставіць і паглядзець, калі гэта дапамагае. Проста ўстаўце многае з гэтага. Гэта, безумоўна, больш Радок, чым звычайна. Давайце проста сапраўды напісаць яго. Няма. Чорт вазьмі. Каманда не знойдзена. Дык вось не звязаныя. Гэта таму, што я ўставіў некаторыя дрэнныя персанажы, але гэта аказваецца не будзе працаваць. Давайце паспрабуем гэта яшчэ раз, таму што гэта больш цікава, калі мы на самай справе крах яго. Давайце друкую гэта, і цяпер, я збіраецца капіяваць сапраўды доўгую радок а цяпер давайце паглядзім, калі мы можа прывесці да збою гэтую рэч. Звярніце ўвагу, я апусціў прасторы і новыя лініі і кропкі з коскай і ўсе незразумелыя сімвалы. Enter. І цяпер у сеткі проста быць павольным. Я трымаў ўніз Command-V занадта доўга, ясна. Чорт вазьмі! Каманда не знойдзена. ДОБРА. Ну, справа ў тым, тым не менш, пасля. Так што на самай справе адбываецца з гэтай дэкларацыяй Чар зорак буфера на лініі 16? Так што я атрымліваю Калі я абвяшчаю паказальнік? Усё, што я атрымліваю значэнне байта чатыры званая буферная, але тое, што ўнутры яго на дадзены момант? Гэта проста некаторы значэнне смецця. Таму любы час вы аб'яўляеце зменную ў C, гэта проста некаторы значэнне смецця, і мы пачынаем Паездка па гэтай рэальнасці. Цяпер, калі я кажу зсапЕ, перайсці на гэты адрас і пакласці ўсе тыпы карыстальнікаў у. Калі карыстальнік ў прывітанне Свет, ну, куды я паклаў яго? Буфер значэнне смецця. Так што накшталт як страла які, паказваючы, хто ведае, дзе. Можа быць, гэта паказвае прама тут, у маёй памяці. І таму, калі карыстальнік тыпы ў свеце, здравствулте! праграма спрабуе паставіць Радок прывітанне свет зваротны слеш 0 у гэтым кавалку памяці. Але з вялікай доляй верагоднасці, але відавочна не 100% верагоднасць, кампутар будзе крах, то Праграма, таму што гэта не памяці я павінен быць дазволена дакрануцца. Карацей кажучы, гэтая праграма недахопы менавіта па гэтай прычыне. Я прынцыпова не робіць? Якія крокі я апушчаны, як мы апусцілі з першага прыкладу Бинки? Да? АЎДЫТОРЫЯ: размеркаванне памяці? Дэвід малая: размеркаванне памяці. Я на самой справе не выдзелены любая памяць для гэтага радка. Такім чынам, мы можам выправіць гэта ў некалькі спосабаў. Адзін з іх, мы можам захаваць яго простым і на самай справе, цяпер ты збіраецца пачаць бачыць размыванне ліній паміж тым, што Масіў, то, што радок з'яўляецца, тое, што сімвал зорка, якая масіў сімвалаў ёсць. Вось другі прыклад з удзелам струнных і апавяшчэння Усё, што я зрабіў на лініі 16, замест таго каб сказаць што буфер будзе сімвал зорка, паказальнік на кавалак памяці, Я збіраюся вельмі актыўна даюць сам буфер 16 сімвалаў, і на самай справе, калі вы знаёмыя з тэрмінам буферызацыі, верагодна, са свету відэа, дзе відэа буферызацыі, буферызацыя, буферызацыі. Ну, якая сувязь тут? Ну, унутры YouTube і ўнутры відэаплэераў як правіла, уяўляе сабой масіў гэта больш, чым 16 гадоў. Гэта можа быць масіў памеру аднаго мегабайт, можа быць, 10 мегабайт, і ў гэтым масіве робіць ваш браўзэр спампаваць цэлую кучу байтаў, цэлая куча мегабайт відэа, і відэа-плэер, YouTube, альбо хто б там ні, пачынаецца чытаць байты з гэтага масіва, і ў любы час вы бачыце Слова буферызацыі, буферызацыя, гэта азначае, што гулец мае дайшлі да канца масіва. Сетка настолькі павольна, што гэта не мае напоўніў масіў з больш байт і так вы з бітаў для адлюстравання карыстальніку. Так буфера з'яўляецца ўдалы тэрмін тут у тым, гэта проста масіў, кавалак памяці. І гэта будзе выправіць таму што гэта аказваецца што вы можаце звяртацца масівы, як быццам яны адрасы, нават калі буфер гэта проста сімвал, гэта паслядоўнасць знакаў, буфер гэта карысна для мяне, праграміст, Вы можаце перадаць сваё імя вакол як калі б гэта былі паказальнік, як бы гэта былі таксама адрас кавалак памяці для 16 знакаў. Дык вось, каб сказаць, што я магу прайсці зсапЕ менавіта гэтае слова і цяпер, калі я гэтую праграму, зрабіць зсапЕ 2, кропка слэш зсапЕ 2, і ўвядзіце ў прывітанне свет, Калі ласка, увядзіце, што time-- Хм, што здарылася? Радок калі ласка. Што я зрабіў не так? Прывітанне свет, буфер. Прывітанне свет. Ах, я ведаю, што ён робіць. ДОБРА. Так што чытае да да першага прабелу. Так што давайце падмануць на імгненне і сказаць, што я проста хацеў, каб нешта тыпу сапраўды доўга, як гэта доўгае прапанову гэта адна, дзве, тры, чатыры, пяць, шэсць, сем, восем, дзевяць, 10, 11, 12, 13, 14, 15, 16. ДОБРА. Гэта сапраўды доўгае прапанову. Такім чынам, гэта прапанова з'яўляецца больш, чым 16 сімвалаў і таму, калі я ударыў Enter, што адбудзецца? Ну, у гэтым выпадку з гісторыя, я абвясціў буфер на самай справе з'яўляецца масіў з 16 сымбалі гатовы да працы. Так адзін, два, тры, чатыры, пяць, шэсць, сем, восем, дзевяць, 10, 11, 12, 13, 14, 15, 16. Так 16 сімвалаў, і цяпер, калі я чытаць нешта, як гэта доўга Прысуд, што адбудзецца ў што я збіраюся чытаць у гэта доўга S-Е-Н-Т-Е-Н-С-Е, прапанову. Так што гэта наўмысна дрэнна, што я працягваць пісаць за межамі Межы майго масіва, за межамі майго буфера. Я мог бы атрымаць пашанцавала, і праграма будзе працягваць працаваць і не хвалюе, але, наогул кажучы, гэта сапраўды крах маю праграму, і гэта памылка ў маім код момант, калі я крок за мяжы з гэтага масіва, таму што я не ведаю, калі гэта абавязкова ўрэжацца або калі я проста хачу, каб павезці. Так што гэта праблематычна, таму што ў гэты выпадак, ён, здаецца, працуюць і давайце спакушаць лёс тут, хоць інтэграванае асяроддзе, здаецца, трываць зусім няшмат of-- Там мы ідзем. Нарэшце-то. Так што я адзіны, хто можа гэта ўбачыць. Так што я проста было шмат весялосці, набраўшы з вельмі доўгі фактычнай фразу што гэта, вядома, перавысіла 16 байт, таму што я набралі ў гэтым вар'яцкім працяглага мульты-лініі Фраза, і звярніце ўвагу на тое, што адбылося. Праграма спрабавала яго друку а затым атрымаў памылку сегментацыі і памылкі сегментацыі, калі нешта падобнае і аперацыйная сістэма кажа няма, не могуць дакрануцца да памяці. Мы збіраемся, каб забіць Праграма ў цэлым. Такім чынам, гэта ўяўляецца праблематычным. Я палепшыў праграму, з дапамогай якой па меншай меры, ёсць памяць, але гэта, здавалася б абмежавацца функцыя GetString, каб атрымаць струны некаторай канчатковай даўжыні 16. Так што, калі вы хочаце падтрымліваць больш прысуды, чым 16 сімвалаў, што ты робіш? Ну, вы можаце павялічыць Памер гэтага буфера да 32 або, што здаецца збольшага кароткім. Чаму б нам не проста зрабіць гэта 1000, але адсунуць. Што адказ інтуітыўна з проста пазбегнуць гэтай праблемы шляхам мой буфер больш, як 1000 знакаў? Рэалізуючы GetString гэты шлях. Тое, што добра ці дрэнна тут? Да? АЎДЫТОРЫЯ: Калі вы звязваць шмат прасторы, і вы не выкарыстоўваеце яго, то вы не можаце пераразмеркаваць гэта прастора. Дэвід малая: Вы маеце рацыю. Гэта марнатраўна, паколькі, калі вы не на самай справе трэба 900 байт з гэтых і яшчэ вы просіце 1000 у агульнай складанасці ў любым выпадку, вы проста спажываць больш памяці на кампутар карыстальніка, чым трэба, і ў рэшце рэшт, некаторыя з Вы ўжо сустракаліся у жыцці, што, калі вы працуе мноства праграм і што яны ядуць да шмат памяці, гэта сапраўды можа паўплываць на прадукцыйнасць і вопыт карыстальніка на кампутары. Так што быццам лянівы рашэнне, напэўна, і, наадварот, гэта не толькі марнатраўна, тое, што праблема па-ранейшаму застаецца, нават калі я магу зрабіць мой буфера 1000? Да? Аўдыторыя: радок даўжынёй 1,001. Дэвід малая: Дакладна. Калі радок даўжынёй 1001, ў вас ёсць сапраўды такі жа праблемай, і мой аргумент, я б толькі затым зрабіць яго 2000 але вы не ведаеце, у загадзя, наколькі вялікі гэта павінна быць, і ўсё ж, я павінен сабраць сваю праграму перш чым даць людзям выкарыстоўваць і спампаваць гэта. Так што гэта менавіта тое, рэчы, якія бібліятэка спрабуе CS50 каб дапамагчы нам з, і мы будзем толькі погляд на некаторыя з базавай рэалізацыі тут, але гэта CS50 кропка С. Гэта гэта файл, які быў на CS50 IDE усе гэтыя тыдні, што вы выкарыстоўваеце. Гэта папярэдне складзены і ў Вас ёсць выкарыстоўвае яго аўтаматычна па характары, які мае працяжнік L CS50 сцяг з ляскам, але калі я пракруціць ўніз праз усе гэтыя функцыі, вось GetString, і проста каб даць вам густ таго, што адбываецца, давайце хуткі погляд на адносную складанасць. Гэта не супер доўга Функцыя, але мы не зрабілі павінны думаю, што ўсе цяжка аб як ісці аб атрыманні радкоў. Такім чынам, вось мой буфер, і я па-відаць, яго ініцыялізацыі да нуля. Гэта, вядома, з'яўляецца Тое ж самае, як паўкокс зоркі, але я вырашыў у рэалізацыі бібліятэкі CS50 што калі мы збіраемся цалкам дынамічны, Я не ведаю, загадзя, наколькі вялікая ў радок карыстальнікі будуць хочаце атрымаць. Так што я збіраюся пачаць толькі з пустым радком і я збіраюся пабудаваць столькі памяці, як мне трэба, каб адпавядаць радок карыстальніка і калі я не дастаткова, я папрашу аперацыйная сістэма для атрымання дадатковай памяці. Я збіраюся перамясціць іх радок ў большы кавалак памяці і я збіраюся выпусціць або вызваліць недастаткова вялікі кавалак памяці і мы толькі збіраемся зрабіць гэта шматкроць. Такім чынам, хуткі погляд, вось толькі зменнай з якой я іду, каб адсочваць ёмістасці маёй буфера. Колькі байт я магу адпавядаць? Вось пераменная п з які я буду трымаць трэк колькі байт на самай справе ў буфер, ці што карыстач увёў. Калі вы не бачылі гэта раней, вам можна паказаць, што пераменная, як Int без знака, які, як вынікае з назвы, азначае, што гэта не-адмоўным, а чаму б Я калі-небудзь хацеў турбаваць удакладненнем што INT гэта не проста INT, але гэта беззнаковое INT? Гэта неадмоўнага Int. Што азначае [неразборліва] на ўвазе? АЎДЫТОРЫЯ: Гэта апісанні колькасць памяці, які можа быць [неразборліва]. Дэвід малая: Так. Так што, калі я кажу без знака, гэта на самай справе даючы вам адзін біт дадатковай памяці і, здаецца, па-дурному, але калі вы ёсць адзін біт дадатковай памяці, што азначае, што вы павінны ў два разы больш значэння можна ўявіць, таму што гэта можа быць 0 або 1. Так, па змаўчанні, цэлалікавых можа быць прыкладна адмоўнае 2 млрд ўвесь шлях да станоўчага 2 млрд. Тыя вялікія дыяпазоны, але ён па-ранейшаму выгляд марнатраўна калі вы толькі клапаціцца пра памеры, якія проста інтуітыўна не павінны быць адмоўнымі або станоўчае або 0, ну а потым, чаму вы марнуеце 2 млрд Магчымыя значэння для адмоўных лікаў калі вы ніколі не збіраецеся іх выкарыстоўваць? Так, кажучы без знака, цяпер мая Int можа быць паміж 0 і прыкладна 4 млрд. Так вось проста INT C па прычынах, мы не зможам атрымаць у цяпер, як чаму гэта цэлалікавых замест з гольца, але вось сутнасць таго, што адбываецца на, і некаторыя з вас могуць выкарыстоўваць, напрыклад, fgetc функцыя нават у чатыры Pset або пасля таго, што мы ўбачым яго зноў ў задачы ўсталяваць пяць, fgetc прыемна, таму што, як імя выгляд, накшталт arcanely мяркуе, гэта функцыя, якая атрымлівае характар ​​і таму, што прынцыпова адрозніваецца пра тое, што мы робім у GetString гэта мы не выкарыстоўваем зсапЕ такім жа чынам. Мы проста паўзе крок за крокам на працягу любога карыстальнік ўвёў у, таму што мы заўсёды можам вылучыць адзін сімвал, і такім чынам, мы заўсёды можам смела глядзець у адну гольца ў той час, і магія пачынае адбывацца тут. Я збіраюся пракруціць ўніз да сярэдзіна гэтай функцыі проста коратка прадставіць гэтую функцыю. Многае, як ёсць Функцыя Таноса, ёсць функцыя Realloc дзе Realloc дазваляе вам пераразмеркаваць частку памяці і зрабіць яго больш ці менш. Так Карацей кажучы, і з хваля майго боку на сённяшні дзень, ведаю, што GetString робіць гэта свайго роду магічна расце або скарачаецца буфер як карыстальнік тыпы ў яго ці яе радка. Так што, калі карыстач уводзіць Кароткая радок, гэты код толькі выдзяляе дастаткова памяці, каб адпавядаць радок. Калі карыстальнік захоўвае ўвод як я зрабіў гэта зноў і зноў і зноў, і, калі буфера першапачаткова гэты вялікі і праграма рэалізуе, каб пачакай, я з космасу, гэта збіраецца падвоіць памер буфера і затым два разы памер буфера і код, які робіць падваенне, калі мы паглядзім на яго тут, гэта толькі гэтая разумная адзін ўкладыш. Вы, магчыма, не бачыў гэты сінтаксіс раней, але калі вы кажаце, зоркі роўная, гэта тое ж самае, кажучы раз Умяшчальнасць 2. Так ён проста працягвае падваенне ёмістасць буфера а затым распавядаць Realloc даць Сам, што значна больш памяці. Цяпер, як у бок, там іншыя функцыі ў тут што мы не будзем глядзець у дэталі акрамя як паказаць у GetInt, мы выкарыстоўваем GetString ў GetInt. Мы правяраем, што гэта не NULL, які, нагадаем, гэта спецыяльнае значэнне, што азначае што-то пайшло не так. Мы з памяці. Лепш праверыць гэта. І мы вяртаем значэнне дазорнай. Але я адкласці на каментары адносна таго, чаму, а затым мы выкарыстоўваем гэтую стрыечны брат зсапЕ называецца sscanf і атрымліваецца, што sscanf, або радок зсапЕ, дазваляе вам зірнуць на лініі, карыстач увёў у вас, і хай прааналізаваць яго па сутнасці і тое, што я робім тут, я кажу sscanf, прааналізаваць усе карыстальнік набралі ў і пераканайцеся,% I, існуе цэлы лік у ім, і мы не будзем трапіць у сёння дакладна, чаму ёсць таксама A% C тут, але ў двух словах дазваляе нам выявіць, калі карыстальнік увёў у чымсьці фіктыўныя пасля нумары. Так што прычына, што GetInt і GetString сказаць вам, каб паўтарыць спробу, паўторыце, паўторыце спробу з-за ўсіх што код, які мы напісалі, гэта свайго роду погляд на ўваходзе карыстальніка у пераканаўшыся, што ён цалкам лічбавая Гэта ці гэта рэальная плавае значэнне кропкі і да т.п., у залежнасці ад таго, якой велічыні функцыянаваць вы выкарыстоўваеце. Вось так. ДОБРА. Гэта быў глыток але справа тут што прычына ў нас было гэтыя навучальныя дыскі па у тым, што на самым нізкім узроўні, Ёсць толькі так шмат рэчаў, якія можа пайсці не так, што мы хацелі прэвентыўна апрацоўваць гэтыя рэчы, вядома, у Першыя тыдні класа, але зараз з Pset чатыры і пяць, і Pset за вы ўбачыце, што гэта больш да Вы, але і вы больш здольныя вырашэння гэтых праблем віды самастойна. Любыя пытанні па GetString або GetInt? Да? АЎДЫТОРЫЯ: Чаму б вам падвоіць ёмістасць буфера а не проста павелічэнне гэта па дакладнай сумы? Дэвід малая: Добры пытанне. Чаму мы ўдвая ёмістасць буфера, у адрозненне проста павялічваючы яго некаторай пастаяннай велічыні? Гэта было дызайнерскае рашэнне. Мы проста вырашылі, што, таму што гэта, як правіла, быць трохі даражэй часу мудра спытаць аперацыйная сістэма на памяць, мы не хочаце ў канчатковым выніку атрымаць у сітуацыя для вялікіх радкоў што мы прасілі АС зноў і зноў і зноў, і зноў у Хуткая змена на памяць. Такім чынам, мы проста вырашылі, некалькі адвольна, але мы спадзяемся, што разумна, што, вы ведаеце, што, давайце паспрабаваць атрымаць наперадзе сябе і проста працягваць падвойвае яго так, што мы мінімізуем колькасць разоў мы павінны называць Таноса або Realloc, але ў агульнай складанасці суд назваць у адсутнасць ведаючы тое, што карыстальнікі, магчыма, захочаце, каб увесці ў. Абодва спосабу могуць быць спрэчным. Магчыма добра. Такім чынам, давайце зірнем на пару іншых пабочных эфектаў памяці, рэчы, якія могуць пайсці не так і інструменты, якія вы можаце выкарыстоўваць, каб злавіць гэтыя віды памылак. Аказваецца ўсё з вас, нават калі check50 ня сказаў вам, як шмат, пішу багі Код, паколькі тыдня адзін, нават калі ўсе тэсты з'яўляюцца check50 прайшло, і нават калі вы і ваш TF супер ўпэўненыя, што Ваш код працуе, як меркавалася. Ваш код быў багі або недахопы ў тым, што ўсё з вас, пры дапамозе бібліятэкі CS50, былі ўцечкі памяці. Ты пытаўся аперацыйную сістэму на памяць у большасці праграм Вы напісалі, але вы ніколі не вярнула яго. Вы назвалі GetString і GetInt і GetFloat, але з GetString, вы, ніколі не называў unGetString або Дайце Радок Назад або да т.п., але мы бачылі, што робіць GetString вылучыць памяць шляхам Таноса ці гэта Функцыя Realloc, які знаходзіцца ўсяго вельмі падобныя па духу, і ўсё ж, мы былі прасіць аперацыйную сістэму для памяць і памяць зноў і зноў але ніколі не даючы яго назад. Цяпер, як у бок, то атрымліваецца, што калі праграма завяршае працу, уся памяць аўтаматычна вызваляецца. Такім чынам, гэта не было велізарная справа. Гэта не збіраецца зламаць IDE або павольна рэчы ўніз, Але калі праграмы не як правіла, ўцечка памяці і яны працуюць на працягу доўгага часу. Калі вы калі-небудзь бачылі дурная маленькая пляжны мяч у Mac OS або пясочныя гадзіны У Windows, дзе гэта выгляд запаволенне або думаць або думаць ці проста сапраўды пачынае каб замарудзіцца, вельмі магчыма, можа быць вынікам ўцечкі памяці. Праграмісты, якія пісалі праграмнае забеспячэнне вы карыстаецеся прасіць аперацыйную сістэму для памяці кожныя некалькі хвілін, кожную гадзіну. Але калі вы выканаўшы Праграмнае забеспячэнне, нават калі гэта звесці да мінімуму ў вашым кампутары на працягу некалькіх гадзін або дзён запар, Вы маглі б прасіць больш і больш памяці і ніколі не выкарыстоўваць яго на самай справе і так што ваш код можа быць, або праграмы могуць быць ўцечка памяці, і калі вы пачынаеце ўцечка памяці, ёсць менш памяці для іншых праграм, і эфект у запаволіць ўсе ўніз. Цяпер, гэта, безумоўна, адзін з Найбольш жорсткія праграмы Вы будзеце мець магчымасць працаваць у той CS50 а яго выхад яшчэ больш эзатэрычных, чым ляск Ці зрабіць або любой каманды Праграмы лініі мы запускаем раней, але На шчасце, убудаваныя ў яго выхадзе гэта некаторыя супер карысныя парады, што будзе карысная як для Pset чатыры або, вядома, Pset пяць. Так Valgrind з'яўляецца інструментам які можа быць выкарыстаны, каб паглядзець уцечак памяці ў вашай праграме. Гэта адносна проста працаваць. Вы запускаеце Valgrind, а затым, нават хоць гэта крыху шматслоўны, працяжнік праверка ўцечка працяжнік роўная поўнай, а затым кропка слэш і імя вашай праграмы. Так Valgrind будзе запусціць праграму і ў самым канцы сваёй праграмы працуе, перш чым ён сыходзіць і дае вам яшчэ падкажыце, ён збіраецца для аналізу Праграма пакуль яна бегла і сказаць, што ты вы ўцечка любая памяць і яшчэ лепш, ты Touch Memory, што не належыць вам? Ён не можа злавіць ўсе, але гэта вельмі добра пры лоўлі большасць рэчаў. Дык вось прыклад маёй прабегшы гэтая праграма, прабегшы Valgrind, на праграму пад назвай памяці, і я збіраюся вылучыць радкі, якія у канчатковым рахунку, для нас цікавая. Так што яшчэ больш адцягвацца што я выдалены з слайда. Але давайце паглядзім, што гэта Праграма здольная сказаць нам. Ён здольны распавядаць нам рэчы як несапраўднай запісу памерам 4. Іншымі словамі, калі вы дакранаецеся памяць, у прыватнасці 4 байт памяці што вы не павінны мець, Valgrind магу сказаць вам, што. Няправільны запісу памерам 4. Вы закранулі чатыры байта што вы не павінны мець. Дзе ты гэта зрабіў? Гэта прыгажосць. Кропка памяці з лініі 21, дзе вас аблажаліся, і менавіта таму гэта карысна. Многае, як GDB, ён можа дапамагчы пазначыць вам на памылкі фактычнага. Цяпер, гэты трохі больш шматслоўны, калі не блытаю. 40 байт 1 блокаў, безумоўна, страцілі ў страты запісу 1 з 1. Што гэта азначае? Ну, гэта проста азначае, што вы прасілі 40 байт і ты ніколі не даў яго назад. Вы назвалі Таноса ці вы назваць GetString і аперацыйная сістэма ня даў вам 40 байт, але вы ніколі не вызваленыя або вызваленыя, што памяць, і быць справядлівымі, мы ніколі не паказваем Вы, як аддаць памяць. Аказваецца, ёсць супер простая функцыя называецца свабодным. Прымае адзін аргумент, рэч Вы хочаце, каб вызваліць або аддаць, але 40 байт, па-відаць, у гэтай праграме былі страчаныя ў радку 20 памяці кропка гр. Такім чынам, давайце паглядзім гэтую праграму. Гэта супер бескарысна. Гэта толькі дэманструе гэта канкрэтная памылка. Такім чынам, давайце зірнем. Вось асноўныя і галоўныя, апавяшчэнне, званкі функцыя называецца F, а затым вяртаецца. Так што не ўсё, што цікава. Што е рабіць? Звярніце ўвагу, я не стаў з прататыпам. Я хацеў, каб захаваць код як мага менш. Так што я паклаў п вышэй асноўнай і гэта нармальна, вядома, для кароткіх праграм, як гэта. Так е нічога не вяртае і робіць не ўзяць што-небудзь, але гэта зрабіць. Гэта заяўляе, падобна у прыкладзе Binky, паказальнік называецца х, што адбываецца захоўваць адрас у міжнар. Дык вось левы бок. У ангельскай мове, што з'яўляецца Правая рабіць? Хто-небудзь? Што гэта робіць для нас? Да? АЎДЫТОРЫЯ: [неразборліва] раз памер з Int што ў 10 разоў больш, чым [неразборліва] Дэвід малая: Добра, і дазвольце мне падвесці вынік. Так вылучыць досыць месцы для 10 лікаў або 10, што памерам з Int, гэта чатыры байта, таму ў 10 разоў 4 40, так што з правага боку, што я выдзелены гэта даць мне 40 байт і захаваць адрас першага байта у х. А цяпер, нарэшце, і вось, дзе гэтая праграма глючыць, што так з лініі 21 на аснове гэтай логікі? Што здарылася з лініяй 21? Да? АЎДЫТОРЫЯ: Вы не можаце індэкс у х [неразборліва]. Дэвід малая: Так. Я не павінен індэкс у х, як, што. Так сінтаксічна, гэта нармальна. Што прыемна, гэтак жа, як вам можа ставіцца да імя масіва як быццам гэта паказальнік, аналагічна Вы можаце лячыць паказальнік як быццам гэта масіў, і таму я магу сінтаксічна кажуць нешта х кранштэйн, кранштэйны х я, але 10 з'яўляецца праблематычным. Чаму? АЎДЫТОРЫЯ: Таму што гэта не ўнутры. Дэвід малая: Гэта не ўнутры гэтага кавалка памяці. Што найбольшае значэнне я павінен класці ў гэтых квадратных дужках? Да 9 верасня, 0. З-за нулявой індэксацыі. Так ад 0 да 9 будзе ў парадку. Кранштэйны 10 не добра, і але, нагадаем, аднак, кожны раз, Я, здаецца, каб паспрабаваць зрабіць CS50 IDE аварыі, набраўшы ў фіктыўных каштоўнасцяў, гэта не заўсёды супрацоўнічаць, і, сапраўды, часта пашанцуе толькі таму, што Аперацыйная сістэма не Вы заўважыце, што ледзь-ледзь прайсці некаторы кавалак памяці, таму што вы засталіся ў тэхнічна Ваш сегмент, але пра гэта у класе аперацыйных сістэм, і так нешта накшталт гэтага можа вельмі лёгка застацца незаўважанымі. Ваша праграма ніколі не будзе ўрэзацца паслядоўна, але, магчыма адзін раз у некаторы час. І так давайце паспрабуем Valgrind на гэта, і вось дзе мы перагружаныя па выхадзе на імгненне. Так што праверку на уцечку памяці Valgrind роўная поўнай памяці кропка слэш. І вось чаму я абяцаю гэта сьцерці. Вось тое, што Valgrind, вось што праграміст, некалькі гадоў ago- вырашыў, што гэта будзе добрая ідэя, для выхаду выглядаць. Такім чынам, давайце разабрацца ў гэтым. Так усю дарогу на левай бок без паважнай прычыны ідэнтыфікатар працэсу праграмы мы проста запусціць, унікальны ідэнтыфікатар для праграмы мы проста беглі. Мы выдалілі, што з слайд, але гэта некаторая карысная інфармацыя тут. Давайце пракруткі да самага верху. Вось дзе мы пачалі. Так што гэта не ўсё, што многае выхад. Вось, што пішуць несапраўдным памер 4 на лініі 21. Ну, тое, што было 21 лінія? Лінія 21 была дакладна гэта і ёсць сэнс што я знаходжуся ў валіднасці пісаць 4 байта, таму што я спрабуюць паставіць гэты цэлае, які можа быць што заўгодна, гэта проста адбываецца, каб быць нуля, але я спрабую пакласці яго на месцы што не належыць мне. Больш за тое, тут, 40 байт ў адным блокі, безумоўна, страціў у запісе 1. Гэта таму, што, калі я называю Таноса тут, я ніколі не вызваліць памяць. Так як мы можам гэта выправіць? Дазвольце мне ісці наперад і быць трохі бяспечней і рабіць там 9, і хай мяне тут бясплатна X. Гэта новая функцыя на сённяшні дзень. Калі цяпер я паўторна зрабіць кропкавы памяці рысу, давайце працаваць Valgrind на яго зноў, павялічыць маё акно і націсніце Enter. Цяпер, гэта добра. Яны хаваюць добрыя навіны усяго гэтага выхаду. Усе блокі кучы былі вольныя. Мы вернемся да таго, што кучы ёсць, але ніякіх уцечак ня магчыма. Так што гэта проста яшчэ адзін інструмент для вашага набору інструментаў з якой вы можаце пачаць зараз знайсці памылкі, як, што. Але давайце паглядзім, што больш можа пайсці не так тут. Давайце пераход зараз на самай справе вырашыць праблему. Як у баку, калі гэта пазбавіць трохі блытаніны або напружанасці, цяпер гэта смешна. Так. Гэта вельмі добра. Таму што паказальнікі адрасы і адрасы як правіла, па пагадненні напісана шаснаццатковым выглядзе. Ха-ха, гэта смешна сёння. Ва ўсякім разе, так што давайце прама цяпер на самай справе вырашыць праблему. Гэта было супер, супер нізкага ўзроўню да гэтага часу, і мы можам на самай справе карысна рэчы з гэтых нізкаўзроўневых дэталяў. Такім чынам, мы ўвялі некалькі тыдняў таму паняцце масіва. Масіў быў добры, таму што цяжка ачысціць наш код таму што, калі мы хацелі, каб напісаць Праграма з некалькімі студэнтамі або некалькі імёнаў і дома, і інтэрната і каледжаў, і ўсё, што, мы маглі б захоўваць усе больш чыста ўнутры масіва. Але прапанаваць адзін недахоп масіва да гэтага часу. Нават калі вы не пакутавалі самі у праграме, проста інстынктыўна, тое, што гэта дрэнна аб масіве, можа быць? Я чуў некаторыя шумы. АЎДЫТОРЫЯ: Гэта складана змяніць памер. Дэвід малая: Цяжка змяніць памер. Вы не можаце змяніць памер масіва, на самай справе, як такія у C. Вы можаце вылучыць яшчэ адзін масіў, перамясціць усё, што ад старога у новае, і ў цяперашні час ёсць некаторы дадатковае прастору, але гэта не як мова, як Java або Python або любую колькасць іншых мовы, з якімі некаторыя з вас можа быць знакам дзе вы можна проста працягваць дадаваць рэчы млоснасці да канца масіва. Калі ў вас ёсць масіў Памер 6, гэта значыць яго памер, і так шмат, як раней ідэя якія маюць буфер пэўнага памеру, вы павінны здагадацца з варот які памер вы хочаце быць? Калі вы адгадаеце занадта вялікі, вы марнуеце прастору. Калі вы адгадаеце занадта малы, вам не можа захоўваць гэтыя дадзеныя, па меншай меры, без шмат працы. Такім чынам, сёння дзякуючы паказальнікаў, мы можам пачаць шыць разам наш уласны звычай структуры дадзеных, і ў Тое, тут што-то што выглядае крыху больш загадкавыя на першы погляд, але гэта тое, што мы называем звязаны Спіс, і яго імя роду сумуе гэта. Гэта спіс лікаў, або ў гэты выпадак, спіс нумароў, але гэта можа быць спіс што-небудзь, але гэта звязана разам шляхам стрэлак, і проста зрабіць здагадку з тым, што тэхніка мы збіраемся, каб мець магчымасць пашыць разам, накшталт папкорна з разьбой, звязаны спісы прастакутнікі тут? Яго нумара? Што функцыя асноўны мову? АЎДЫТОРЫЯ: Паказальнік. Дэвід малая: Паказальнік. Такім чынам, кожны з гэтых стрэл тут уяўляе паказальнік або проста адрас. Такім чынам, іншымі словамі, калі я хачу захоўваць спіс нумароў, Я не магу проста захоўваць яго, калі я хачу здольнасць павялічвацца і памяншацца мой структура дадзеных у масіве. Таму мне трэба, каб мець трохі больш вытанчанасць, але заўважыць, што гэта карціна выгляд мяркуе што калі вы толькі што атрымалі маленькія тэмы падлучэння ўсе разам, верагодна, гэта не так складана зрабіць прастору паміж двума гэтымі прастакутнікамі ці два з гэтых вузлоў, як мы пачнем называючы іх, пакласці ў новы вузел, а затым з нейкай новай ніткі, проста канаву тры вузла разам, першы, апошні, і той, што вы толькі што ўставілі ў сярэдзіну. І сапраўды звязаны спіс, у адрозненне ад масіва, з'яўляецца дынамічным. Ён можа расці і можа скарачацца і вы не павінны ведаць, ці сыходу загадзя, як шмат дадзеных вы збіраецеся быць захоўвання, але, аказваецца, мы павінны быць трохі асцярожныя аб тым, як ажыццявіць гэта. Такім чынам, спачатку давайце разгледзім, як мы рэалізуем адзін з гэтых маленькіх прастакутнікаў. Гэта лёгка рэалізаваць Int. Вы проста кажаце Int N, а затым Вы атрымліваеце 4 байта для Int, але як я магу атрымаць Int, назавем яго N, а затым паказальнік, давайце называць яго побач. Мы маглі б назваць гэта рэчы ўсё, што мы хочам але мне трэба структуру карыстацкіх дадзеных. Да? АЎДЫТОРЫЯ: Ампэрсанд [неразборліва]. Дэвід малая: Так Ампэрсанд мы будзем выкарыстоўваць для атрымаць адрас вузла патэнцыйна. Але нам патрэбны яшчэ Функцыя С у парадак каб даць мне магчымасць ствараць гэты звычай прастакутнік, гэты звычай Пераменная, калі хочаце, у памяці. Залы: структура. Дэвід малая: а структурай. Нагадаем, на мінулым тыдні, мы ўвялі структура, гэта адносна простае ключавое слова, што дазваляе нам зрабіць такія рэчы, як гэта. З не прыйшоў з дадзеным Структура называецца студэнта. Ён пастаўляецца з Int і плаваць і гольца і напрыклад, але ён не прыходзіць са студэнтамі, але мы можам стварыць тып дадзеных студэнтам, студэнт структура, з гэтым сінтаксісам тут. І вы ўбачыце, што гэта зноў і зноў. Так што не турбуйцеся аб запамінання слоў, але ключавое слова, што гэта важна, толькі той факт, што мы сказалі, структура і тады мы называлі гэта студэнт і ўнутры студэнта было імя і дом або агульны нумар ці таму падобнае. І так вось сёння, давайце прапаноўваць гэта. Я дадаў некалькі слоў, але калі я хачу ажыццявіць гэты прастакутнік, што гэта атрымаў адначасова Int і А паказальнік, вы ведаеце, што я збіраецца абвясціць на структуру пад назвай вузел. Я таксама, унутры яго, хачу сказаць, што вузел, гэты прастакутнік, мае Int і мы будзем называць яго п і яна мае наступны паказальнік. І гэта крыху шматслоўны, але калі вы думаеце пра гэта, стрэлкі, якія былі на малюнку момант назад, якога тыпу дадзеных? Дзе кожны з гэтых стрэлак паказвае які тып структуры дадзеных? Гэта не паказваючы толькі на міжнар на сабе. Гэта паказвае на Уся прастакутная рэч і што прастакутная рэч, мы сказалі, называецца вузлом. І такім чынам, мы збольшага павінны рэкурсіўна вызначыць гэта такое што вузел, мы будзем казаць, будзе ўтрымліваць Int пад назвай п і паказальнік называецца побач і тып структуры дадзеных, да якіх што паказальнік паказвае, па-відаць будзе структура вузла. Так што гэта прыкра, шматслоўным і проста быць педантычным, прычына, чаму мы не можам проста сказаць, што гэта, што, шчыра кажучы выглядае нашмат больш чытэльным, таму, што нагадаем, што C чытання рэчы зверху ўніз, злева направа. Гэта не пакуль мы не атрымаем кропку з коскі што вузел ключавое слова на самай справе існуе. Так што, калі мы хочам мець такую цыклічны спасылкі ўнутры дадзеных Структура, што мы павінны зрабіць гэта, калі мы кажам структуры вузла ў верхняй частцы, якая дае нам доўгі шлях апісання гэтага рэч, то ўсярэдзіне мы гаворым структуры вузла, а затым у самы апошні лініі мы кажам, усё ў парадку, З, дарэчы, проста патэлефануеце ўвесь гэты пракляты што вузел і спыніць выкарыстоўваючы ключавое слова-структуру ў цэлым. Так што гэта проста свайго роду сінтаксічны Хітрасць у канчатковым рахунку, дазваляе, што нам стварыць тое, што выглядае гэтак жа, як гэта. Так што, калі мы выкажам здагадку цяпер, мы можам рэалізаваць гэтую рэч у C, Як мы на самай справе пачаць абыход гэтага? Ну, на самай справе, усё, што мы павінны зрабіць, гэта ітэрацыі злева направа і проста выгляд ўставіць вузлы або выдаляць вузлы або шукаць рэчы там, дзе мы хочам, але каб зрабіць гэта, давайце ісці наперад і зрабіць рэчы крыху больш рэальным, таму што гэта быў супер нізкага ўзроўню да гэтага часу. Хто літаральна хацелі б быць першым? ДОБРА. Давай до. Ваша імя? Дэвід: Дэвід. Дэвід малая: Дэвід. Вельмі прыемна. Я таксама. Добра. І нам спатрэбіцца шэраг 9. Не так добра, як па-першае, магчыма. ОК, нумар 9. Шэраг 17, калі ласка. Дазвольце мне вярнуцца крыху далей. Колькасць 22, калі ласка, і як пра далей таму калі я бачу якіх-небудзь рукі з усімі святла ці не. Хтосьці падахвоціўся быць прама там. Вы хочаце, каб прыдумаць? Ваша перадплечча прымусова ідзе ўверх. ОК, 17. 22. 26 спускаецца. Нехта яшчэ хацелі б forcefully-- Давай да. Фактычны грамадскіх пачатках. Так вельмі хутка, калі вы, хлопцы, маглі б арганізаваць самі проста хацеў вузлы на экране. Дзякуй. І вы будзеце 26. Усе правільныя і хуткія ўвядзення. Так што я Дэвід, і вы таксама? Дэвід: Дэвід. Дэвід малая: А вы? Джэйк: Джэйк. ГУП: Сью. АЛЕКС: Алекс. Рафаэль: Рафаэль. Тэйлар: Тэйлар. Дэвід малая: Тэйлар. Выдатна. Такім чынам, гэтыя нашы валанцёры сёння і ісці наперад і зрух мала што шлях, і проста ісці наперад і трымаць правядзенне вашыя нумары, як вы ці вашы Першы прыкмета і левай рукой, ісці наперад і проста рэалізаваць гэтыя стрэлкі, толькі так што ваша левая рука літаральна паказваючы на ​​тое, што вы павінны паказаць на, і даць сабе некаторую пакой так, што мы можам наглядна ўбачыць вашыя рукі на самай справе паказваючы, і вы можаце проста паказаць роду на зямлю ў парадку. Так вось у нас ёсць звязаны спіс аднаго, два, тры, чатыры, пяць вузлоў на пачатковым этапе, і звярніце ўвагу, у нас ёсць гэтая спецыяльная паказальнік на пачатак, хто ключавым, таму што мы павінны адсочваць з усяго спісу даўжыні нейкім чынам. Гэтыя хлопцы, нават калі яны застаюцца направа, спіной да спіны ў памяці, яны сапраўды могуць быць у любым месцы ў памяці кампутара. Такім чынам, гэтыя хлопцы маглі б быць стоячы на ​​любым этапе і гэта нармальна, так доўга, як яны на самай справе, паказваючы адзін на аднаго, але трымаць рэчы чысты і просты, мы будзем проста звярнуць іх злева направа, як гэта, але не можа быць масіўныя прамежкі паміж гэтымі вузламі. Цяпер, калі я хачу на самай справе ўставіць некаторыя новае значэнне, давайце ісці наперад і рабіць гэта. У нас ёсць магчымасць у цяперашні час выбраць іншы вузел. Скажыце давайце пачнем з mallocing 55. Ці будзе хто-супраць таго Таноса? ОК, давай да. Ваша імя? РАДУГА: Вясёлка. Дэвід малая: Вясёлка? Добра. Маллок Вясёлка. Давай до. Так што цяпер мы павінны спытаць сябе, алгарытмічных, дзе мы можам паставіць 55. Такім чынам, усе мы ведаем ,, відавочна, дзе яна, верагодна, належыць, калі мы спрабуем каб гэтая сартуюцца і калі вы, хлопцы, можа прыняць адно крок назад, таму мы не ўпасці этап, што было б выдатна. Так на самой справе, Вясёлка, пачаць тут са мной, таму што мы, як кампутар цяпер можа ўбачыць толькі адну зменную адначасова. Такім чынам, калі гэта першы вузел. Звярніце ўвагу, што ён не з'яўляецца вузлом, ён проста паказальнік, і вось чаму ён звяртаецца, каб быць толькі памер паказальніка, а не адзін з тых поўных прастакутнікаў. Такім чынам, мы збіраемся, каб праверыць адзін на ітэрацыя 55 менш, чым 9? Няма. Ёсць 55 менш 17? Няма. Менш за 22? Менш за 26? Менш за 34? І вось цяпер, відавочна, Вясёлка належыць у канцы. Такім чынам, каб было ясна, і тое, што быў ваша імя, Тэйлар? Тэйлар: Тэйлар. Дэвід малая: Так сярод Тэйлар левая рука і рукі вясёлкі тут, Чыя рука павінна паказваць на тое, што ў Каб ўставіць 55 у гэтым спісе? Што нам трэба рабіць? Да? АЎДЫТОРЫЯ: ручная Тэйлара трэба паказаць левай. Дэвід малая: Дакладна. Так ўстаўцы вузла ў канцы спісу даволі проста, таму што Тэйлар проста павінен паказваць, а не на зямлі ці мы будзем называць яго пустым, нуль з'яўляецца свайго роду адсутнасць паказальніка або спецыяльны нулявы паказальнік, вы будзем паказваць з левай руку на Вясёлка Вясёлка, а затым, дзе, калі ваш левы рука, верагодна, паказваюць? Ўніз Гэта не добра, калі яе рука накшталт ўказваць тут або ад свайго роду любы якім чынам. Гэта будзе разглядацца значэнне смецця, але калі яна паказвае на некаторыя вядомыя значэнне, мы будзем называюць яго нуля або нулявы, гэта нармальна таму што ў нас у гэтым тэрмін і мы ведаем, што спіс у цяперашні час завершана. Так што яшчэ адзін адносна просты выпадак? Ці можам мы Таноса 5? Давай до. Ваша імя? Ціфані: Ціфані. Дэвід малая: Я прашу прабачэння? Ціфані: Ціфані. Дэвід малая: Ціфані. Добра. Ціфані была malloced са значэннем 5. Давай до. Гэты параўнальна лёгка занадта, але давайце разгледзім парадак аперацый у цяперашні час. Гэта было даволі лёгка з Тэйларам у канцы. Нумар 5, вядома, менш, чым 9, і таму мы павінны Давіда, у нас ёсць Ціфані, і тое, што было ваша імя? Джэйк: Джэйк. Дэвід малая: Джэйк. Ціфані, Джэйк, і Дэвід. Чыя рука павінна быць абноўлена ў першую чаргу? Што вы хочаце зрабіць тут? Там ёсць пара магчымых шляхоў, але ёсць таксама адзін або больш няправільныя спосабы. АЎДЫТОРЫЯ: Пачніце з крайняга левага. Дэвід малая: Пачніце з крайняга левага. Хто крайні левы тут тады? АЎДЫТОРЫЯ: Па-першае. Дэвід малая: ОК. Так што пачніце з першай і дзе вы хочаце абнавіць рукі Давіда, каб быць? АЎДЫТОРЫЯ: Да 5. Дэвід малая: ОК. Давід, кропка, у пяці або Ціфані тут, а цяпер? АЎДЫТОРЫЯ: Ціфані паказвае на 9? Дэвід малая: Цалкам, за выключэннем таго, Бинки Кіраўнік толькі выгляд ўпаў, ці не так? Таму што тое, што здарылася з гэтая карціна літаральна? АЎДЫТОРЫЯ: Нішто не паказвае. Дэвід малая: Нішто не з'яўляецца паказваючы на ​​Джэйка ў цяперашні час. Мы літаральна асірацеў 9 і 17, і мы літаральна ўцечка ўся гэтая памяць, таму што абнаўлення руку Давіда першае, гэта ў парадку, паколькі гэта правільна паказваючы на ​​Ціфані зараз, але калі ніхто не меў прадбачліва паказваюць на Джэйка, Затым мы страцілі Сукупнасць гэтага спісу. Такім чынам, давайце адмяніць. Так што гэта добрая рэч, каб спатыкнуцца, але давайце выправім сучаснасць. Тое, што мы павінны зрабіць у першую чаргу, а? Да? АЎДЫТОРЫЯ: Ціфані павінна паказваць на 9? Дэвід малая: я не магу атрымаць так блізка да вас. Хто павінен паказаць на 9? АЎДЫТОРЫЯ: Ціфані. Дэвід малая: Добра. Так Ціфані павінна першая кропка на 9. Так Ціфані павінны прыняць на аднолькавым значэннем Давіду, які, здаецца, залішнім на імгненне, але гэта нармальна, таму што цяпер, па-другое крок, мы можам абнавіць руку Давіда каб паказаць на Ціфані, а затым, калі мы толькі збольшага ачысціць рэчы як быццам гэта свайго роду вясны-як, вось гэта правільны ўстаўкі. Так выдатна. Так што цяпер мы амаль там. Давайце ўставіць адзін фінал значэнне як значэнне 20. Калі б мы маглі Таноса адзін заключны добраахвотнікам? Давай до. Так што гэта адно крыху больш складана. Але на самой справе, код мы пісаць, хоць і ў вуснай форме, гэта ўсё роўна, што кучу з, калі ўмовы зараз, праўда? Мы мелі стан праверкі, калі ён належыць У рэшце рэшт, можа быць, з самага пачатку. Мы павінны нейкі цыкл у знайсці месца ў сярэдзіне. Так давайце зробім гэта з тым, што ваша імя? Эрык: Эрык. Дэвід малая: Эрык? Эрык. Вельмі прыемна. Такім чынам, мы маем 20. Менш за пяць? Няма. Менш за дзевяць? Няма. Менш за 17? Няма. ДОБРА. Ён належыць тут і Вашы імёны зноў ёсць? ГУП: Сью. Дэвід малая: Сью. АЛЕКС: Алекс. Дэвід малая: Сью, Алекс, а? Эрык: Эрык. Дэвід малая: Эрык. Чые рукі павінны атрымаць абнаўленне ў першую чаргу? АЎДЫТОРЫЯ: Эрык. ДОБРА. Так Эрык павінен паказаць на тое, дзе? У 22. Добра. А цяпер, што будзе далей? Сью можа паказваць на Эрыка і цяпер, калі вы, хлопцы, проста пацясніцца, які выдатны візуальна, зараз мы зрабілі ўстаўку. Дык няхай зараз разгледзім пытанне, але дзякуй так шмат для нашых валанцёраў. Вельмі добра зроблена. Вы можаце захаваць тыя, калі вам падабаецца. І ў нас ёсць выдатны падарунак, калі развітальны вы кожны хацеў узяць стрэс мяч. Дазвольце мне перадаць гэта ўніз. Так што вынас гэта? Гэта, здаецца, дзіўна паколькі мы маем цяпер прадставіла альтэрнатывай Масіў, які не так абмежаваныя на масіў некаторага фіксаванага памеру. Яны могуць расці дынамічна. Але гэтак жа, як мы бачылі на працягу некалькіх тыдняў мінулае, мы ніколі не атрымаем нічога бясплатна, як, безумоўна, ёсць кампраміс тут. Так з патэнцыялам росту звязаны Спіс, гэта дынамізм? Гэтая здольнасць расці і, шчыра кажучы, мы маглі б зрабіць выдалення і мы маглі б сціснуць па меры неабходнасці. Якую цану мы плацім? У два разы больш прасторы, у першую чаргу. Калі вы паглядзіце на карціну, больш не я захоўваць спіс цэлых лікаў. Я захоўвання спісу цэлыя плюс паказальнікі. Так што я падваенне колькасці прасторы. Цяпер, можа быць, гэта не такая вялікую справу 4 байта, 8 байт, але гэта, безумоўна, можа дадаць на вялікіх набораў дадзеных. Што іншы недахоп? Да? АЎДЫТОРЫЯ: Мы павінны прайсці іх адзін за адным. Дэвід малая: Так. Мы павінны прайсці іх адзін за адным. Вы ведаеце, што мы адмовіліся ад гэтай супер зручная функцыя квадратнага кранштэйна абазначэння, больш правільна вядомы як адвольнага доступу, дзе мы можам проста скокнуць да асобнага элемента але цяпер, калі я да гэтага часу мае добраахвотнікі тут, калі б я хацеў, каб знайсці № 22, я не магу проста перайсці да кранштэйны-небудзь што-небудзь. Я павінен глядзець на спіс, шмат як нашы прыклады пошуку лінейна, каб знайсці нумар 22. Такім чынам, мы, здаецца, заплацілі цану там. Але, тым не менш, мы можам вырашыць іншыя праблемы. На самай справе, дазвольце мне прадставіць толькі пару візуальныя эфекты. Так што, калі вы былі да Сталовая Mather нядаўна, вы памятаеце, што іх стэкі падносаў, як гэта, мы запазычылі іх з Анненберга перад класам. Такім чынам, гэта чарка талерак, хоць, з'яўляецца прадстаўніком на самай справе структуры дадзеных кампутарнай навукі. Існуе структура дадзеных у інфарматыцы Вядома, як стэк, які вельмі прыгожа паддаецца менавіта гэта візуальна. Такім чынам, калі кожны з гэтых латкоў ня латок, але, як і шэраг, і я хацеў для захоўвання нумары, я можа паставіць адзін тут, і я мог бы паставіць іншы сюды, і працягнуць кладку лік на верхняй частцы адзін аднаго, і тое, што патэнцыйна карысным пра гэта гэта тое, што гэта маецца на ўвазе гэтай структуры дадзеных? Які лік я магу выцягнуць у першую чаргу найбольш зручна? Найбольш нядаўна выказаўся адзін там. Так што гэта тое, што мы называем ў інфарматыка структура дадзеных ЛИФО. Апошні прыйшоў, першы. І мы ўбачым, у хуткім часе, чаму што можа быць карысным, але цяпер, проста разгледзець ўласнасць. І гэта збольшага па-дурному, калі вы думаеце, пра тое, як сталовая гэта робіць. Кожны раз, калі яны чыстыя латкі і пакласці свежыя з іх на вяршыні, вы маглі б раней чыстая але ў рэшце рэшт вельмі брудны і пыльны латок на самым дне калі вы на самой справе ніколі не трапіць у ніжняй частцы, што стэк, таму што вы проста трымаць пакласці новы і чыстыя тыя, на вяршыні гэтага. Тое ж самае можа здарыцца у супермаркеце таксама. Калі ў вас ёсць вітрыну малака і кожны раз CVS або той, хто атрымлівае больш малака, вы проста засунуць малако ў вас ужо ёсць на спіне і Вы змяшчаеце новыя наперадзе, Вы будзеце мець некаторыя даволі брыдка Малако ў канцы структуры дадзеных, таму што гэта заўсёды на дне або што тое ж самае, гэта заўсёды на спіне. Але ёсць яшчэ адзін спосаб думаць аб выстройваюцца дадзеных і, напрыклад, гэты. Калі вы адзін з тых людзей, хто любіць выбудоўвацца за межамі Apple, крамы калі новы прадукт пастаўляецца з, вы, верагодна, не выкарыстоўваючы дадзеныя стэка Структура, таму што вы адштурхне ўсіх, хто знаходзіцца выстройваюцца, каб купіць некаторыя новыя цацкі. Хутчэй за ўсё, вы, верагодна, з выкарыстаннем якія структуры дадзеных або якая сістэма у рэальным свеце? Спадзяюся, гэта лінія, або больш правільна ці больш брытанскі, як, чэргі. І атрымліваецца, чаргу таксама Структура дадзеных у інфарматыцы, але чаргу мае вельмі адрозніваецца ўласцівасць. Гэта не ЛИФО. Апошні прыйшоў, першы. Не дай Бог. Гэта замест таго, каб FIFO. Па-першае, першым сышоў. І гэта добра Дзеля справядлівасці вядома, калі вы выстройваюцца да супер рана раніцай. Калі вы там спачатку, Вы хочаце, каб выйсці спачатку ў якасці добра. І так усе гэтыя дадзеныя структуры, чэргі і стэкі і гронкі іншых, аказваецца вас можа думаць пра гэта, як толькі што масіў. Гэта масіў, можа быць, фіксаваны памер 4, але гэта было б быць свайго роду добра, калі мы маглі б проста куча Латкі амаль бясконца высокі, калі мы ёсць, што многія падносы або лічбы. Так, можа быць, мы хочам, каб выкарыстоўваць звязаны спіс тут, але кампраміс будзе патэнцыйна, што нам трэба больш памяці, займае крыху больш часу, але мы не абмяжоўваюць вышыню чаркі, гэтак жа, як вітрыне Мазер можа абмежаваць памер стэка, і такім чынам, яны праектныя рашэнні ці варыянты, даступныя для нас у канчатковым рахунку. Так што з гэтымі дадзенымі структуры, мы пачалі бачачы новыя верхнія межы патэнцыйна на тое, што раней было супер хутка і дзе мы пакінем ад сёньня і дзе мы спадзяемся атрымаць у на сераду, мы будзем пачаць глядзець на дадзеных Структура, што дазваляе нам шукаць праз дадзеныя ў канцы часу часопіса зноў. І мы ўбачылі, што, памятаю, у нулявы тыдні і адзін з бінарнага пошуку або разрыву і ўладар. Гэта вяртаецца, і яшчэ лепш, Святы Грааль для гэтага сераду будзе прыдумаць з структура дадзеных, якая працуе сапраўды або тэарэтычна Пастаянная часу, у выніку чаго гэта не мае значэння, колькі мільёны або мільярды рэчаў мы маем у структуры дадзеных, гэта будзе ўзяць нас пастаяннае час, можа быць, адзін крок ці два кроку або 10 крокаў, але пастаянныя колькасці крокаў шукаць у гэтай структуры дадзеных. Гэта сапраўды будзе Святой Грааль але пра гэта ў сераду. Ўбачымся тады. [Гуляе музыка]