[Powered by Google Translate] [Тыдзень 6, працяг] [David J. малая] [Harvard University] [Гэта CS50.] [CS50.TV] Гэта CS50 і гэта ў канцы тыдня 6. Так CS50x, адзін з першых курсаў Гарвардскага універсітэта, якія ўдзельнічаюць у EDX ініцыятывы Сапраўды дэбютаваў у мінулы панядзелак. Калі вы хочаце атрымаць уяўленне аб тым, што іншых у Інтэрнэце У цяперашні час наступных разам з, вы можаце адправіцца на x.cs50.net. Гэта будзе перанакіраваць вас у патрэбнае месца на edx.org, які быў, дзе гэтая і іншыя праграмы навучання ў MIT і Берклі зараз жывем. Вы павінны зарэгістравацца для ўліковага запісу, вы знойдзеце, што матэрыял з'яўляецца ў значнай ступені тое ж самае як у вас было ў гэтым семестры, хоць і некалькі тыдняў затрымліваецца, так як мы атрымліваем ўсё гатова. Але тое, што студэнты ў CS50x ўбачыце гэта інтэрфейс, зусім як гэты. Гэта, напрыклад, з'яўляецца Zamyla вядучых пакрокавае кіраўніцтва для задачы набору 0. Пры ўваходзе ў edx.org, CS50x студэнт бачыць розныя рэчы Вы чакалі б убачыць у курсе: лекцыя для панядзелка, Лекцыя на сераду, розныя шорты, праблема набору, пакрокавыя кіраўніцтва, PDF-файлы. Акрамя таго, як вы тут бачыце, пераклады машыны з ангельскага стэнаграмы на кітайскі, японскі, іспанскі, італьянскі, і цэлая куча іншых моў, якія, безумоўна, будзе недасканалым як мы коцімся іх праграмна, выкарыстоўваючы так званы API, ці інтэрфейс прыкладнога праграмавання, ад Google , Што дазваляе нам пераўтварыць ангельскай на гэтыя іншыя мовы. Але дзякуючы выдатнаму духу некаторых сто з лішнім добраахвотнікаў, выпадковых людзей у інтэрнэце, якія ласкава прапанавалі прыняць удзел У гэтым праекце, мы будзем паступова паляпшаючы якасць гэтых перакладаў пры наяўнасці людзей выпраўляць памылкі, што нашы кампутары зрабілі. 

Вось і атрымліваецца, што мы яшчэ некалькім студэнтам паказаць у панядзелак, чым мы першапачаткова чакалі. На самай справе, цяпер CS50x мае 100.000 чалавек вынікаючы ўздоўж дома. Так разумею, вы усе часткі гэтага першага класа робіць гэты курс па інфарматыцы адукацыі ў цэлым, больш шырока, даступна. А рэальнасць такая цяпер, з некаторымі з гэтых маштабнай онлайн-курсы, усе яны пачынаюцца з гэтых вельмі вялікіх колькасцях, як мы, здаецца, зрабілі тут. Але мэта, у канчатковым рахунку, для CS50x сапраўды атрымаць як мага больш людзей да фінішу наколькі гэта магчыма. Паводле задумы, CS50x збіраецца быць прапанаваная з гэтага ў мінулы панядзелак на ўсім шляху па 15 красавіка 2013 года, так што людзі, якія маюць школы абавязацельстваў у іншых месцах, праца, сям'я, іншыя канфлікты і да таго падобнае, ёсць трохі больш гнуткасці , З якой пагрузіцца ў гэты курс, які, дастаткова сказаць, даволі амбіцыйна зрабіць, калі толькі на працягу толькі тры месяцы на працягу звычайнага семестра. Але гэтых студэнтаў будзе вырашаць тыя ж мноства праблем, прагляду таго ж зместу, якія маюць доступ да тых жа шорты і таму падобнае. Так разумею, што мы ўсе сапраўды ў гэтым разам. І адна з канчатковых мэтаў CS50x не толькі атрымаць як мага больш людзей да фінішу і даць ім гэтую зноў здабытую разуменне інфарматыкі і праграмавання, але і мець іх у гэтага падзяліліся вопытам. Адной з вызначальных характарыстык з 50 на тэрыторыі кампуса, мы спадзяемся, была такая камунальная вопыт, да лепшага ці да горшага, часам, але маюць гэтыя людзі звяртаюцца да налева і направа, і офісных гадзін і Hackathon і справядлівай. Гэта крыху больш складана зрабіць гэта ў твар з людзьмі ў Інтэрнэце, але CS50x завершыцца ў красавіку з першым CS50 Expo, , Які будзе онлайн адаптацыі наша ўяўленне аб справядлівай дзе гэтыя тысячы студэнтаў усё будзе прапанавана прадставіць 1 - 2-хвіліннае відэа, альбо скринкаст іх канчатковага праекта або відэа з іх размахваў прывітанне і казаць аб сваім праекце і demoing гэта, гэтак жа, як вашы папярэднікі зрабілі тут, на тэрыторыі кампуса у кірмашы, так што да канца семестра, надзея на тое, каб мець глабальныя выставы канчатковых праектаў CS50x студэнтаў, як і тое, што чакае вас у снежні гэтага года тут, на тэрыторыі кампуса. Так пра гэта ў бліжэйшыя месяцы. 

З 100.000 студэнтаў, аднак, прыходзіць неабходнасць яшчэ некалькі цэнтраў сертыфікацыі. Улічваючы тое, што вы, хлопцы, пракладвае шлях тут і прымаючы CS50 некалькі тыдняў да выпуску гэтага матэрыялу, каб людзі на EDX, разумею, што мы хацелі б прыцягнуць як многія з нашых студэнтаў, як магчыма ў гэтай ініцыятыве, як на працягу семестра, а таксама гэтай зімой, і гэта маючай адбыцца вясной. Так што, калі вы хочаце прыняць удзел у CS50x, Асабліва на ўступленне ў CS50x Абмеркаваць, версія EDX з Абмеркаваць CS50, якія многія з вас ужо выкарыстоўваюць на тэрыторыі кампуса, онлайн табло, калі ласка, зрабіце галаву, што URL, дайце нам ведаць, хто вы, таму што мы хацелі б пабудаваць каманду студэнтаў і супрацоўнікаў і выкладчыкаў, так на тэрыторыі кампуса, якія проста гуляюць разам і дапамагаць. І калі яны бачаць, што гэта пытанне знаёмыя з імі, Вы чуеце студэнт справаздачнасці нейкая памылка дзесьці там, у нейкай краіне ў Інтэрнэт, і што тэлефануе ў звон, таму што вы таксама былі ў тым жа пытанні ў г-зале некаторы час таму, мы спадзяемся, то вы можаце тэлефанаваць у і падзяліцца сваім уласным вопытам. Таму, калі ласка, удзел, калі вы хочаце. 

Інфарматыка курсы ў Гарвардзе ёсць трохі традыцыі, CS50 сярод іх, які мае некаторы вопратку, вопратку, якую можна насіць з гонарам ў канцы семестра, заявіўшы, што не без гонару, што вы скончылі CS50 і ўзяў CS50 і да таго падобнае, і мы заўсёды стараемся прыцягнуць студэнтаў У гэтым працэсе як мага больш, прычым мы запрашаем, прыкладна ў гэты час семестра, студэнты прадставіць праекты выкарыстанне Photoshop, або любы іншы інструмент выбару вы хацелі б выкарыстоўваць Калі вы дызайнер, прадставіць праекты для футболкі і талстоўцы і парасонамі і мала банданы для сабак у нас зараз ёсць і да таго падобнае. І ўсё гэта затым - пераможцы кожнага года, затым выстаўлены на вэб-сайце курсу на store.cs50.net. Усе прадаецца па кошце там, але сайт проста працуе сабе і дазваляе людзям выбіраць колеру і дызайну, што ім падабаецца. Такім чынам, я думаў, што мы проста падзяліцца некаторымі з канструкцый апошні год , Якія былі на сайце, акрамя гэтага тут, які з'яўляецца штогадовай традыцыяй. "Кожны дзень я Seg Faultn" была адной з прадстаўленых у мінулым годзе, які па-ранейшаму даступныя там для выпускнікоў. У нас была адна, "CS50, падставы 1989". Адзін з нашых Bowdens, Боб, быў вельмі папулярны ў мінулым годзе. "Каманда Боуден" нарадзіўся, гэты праект быў прадстаўлены, сярод лепшых прадаўцоў. Як гэта было тут. Многія людзі былі "Боуден Fever" па продажах часопісаў. Зразумейце, што зараз можа быць ваш дызайн там, на Інтэрнэт. Падрабязней пра гэта ў наступнай праблемай ўсталёўвае ў будучыні. 

Яшчэ адзін інструмент: Вы мелі некаторы ўздзеянне і, спадзяюся, цяпер некаторы практычны досвед працы з GDB, які, вядома, адладчык і дазваляе маніпуляваць Ваша праграма на даволі нізкім узроўні, рабіць нейкія рэчы? Што GDB дазваляюць вам рабіць? Да? Дайце мне што-небудзь. [Студэнт адказ, неразборліва] Добра. Крок у функцыі, так што вы не проста павінны ўвесці працаваць і ёсць праграма ўдар па ўсёй яго паўнаце, раздрукаваныя рэчы на ​​стандартны вывад. Замест гэтага, вы можаце пакрокава яго радок за радком, альбо увёўшы наступную ісці радок за радком па лініі або крок, каб паглыбіцца ў функцыю, як правіла, той, які вы напісалі. Што яшчэ GDB дазваляюць вам рабіць? Да? [Студэнт адказ, неразборліва] Друк зменных. Так што калі вы хочаце зрабіць невялікі самааналіз ўнутры вашай праграмы , Не звяртаючыся да напісання заявы Printf паўсюль, Вы можаце проста раздрукаваць зменнай або адлюстроўваць зменнай. Што яшчэ можна зрабіць з дапамогай адладчыка, як GDB? [Студэнт адказ, неразборліва] Менавіта так. Вы можаце ўсталяваць кропкі супыну, можна сказаць, перапынак выканання на асноўнай функцыі або функцыі Foo. Можна сказаць, перапынак выкананне з радка 123. І супыну з'яўляюцца вельмі магутнай тэхнікай таму што, калі ў вас ёсць агульнае адчуванне ад таго, дзе ваша праблема Верагодна, вы не павінны марнаваць час пакрокавага аб'ёме праграмы. Вы можаце істотна скакаць прама там і тады пачаць друкаваць - ступаючы па іх з крокам або наступнага або таго падобнае. Але злавіць нешта накшталт GDB з'яўляецца тое, што ён дапамагае вам, чалавеку, знайсці вашыя праблемы і знайсці свае памылкі. Гэта не абавязкова знойдзе іх так шмат для вас. 

Такім чынам, мы прадставілі іншыя style50 дзень, які знаходзіцца ў некалькіх хвілінах інструмент каманднага радка , Які спрабуе стылізаваць код трохі чысцей, чым вы, чалавек, магчыма, прыйдзецца зрабіць. Але гэта таксама, на самай справе проста эстэтычная рэч. Але, аказваецца, ёсць гэты іншы інструмент пад назвай Valgrind, што з'яўляецца крыху больш таямніцай для выкарыстання. Яго выхад па-зверску загадкавыя на першы погляд. Але гэта дзіўна карысныя, асабліва цяпер, калі мы знаходзімся ў частцы тэрміну дзе вы пачынаеце выкарыстоўваць таНос і дынамічнага размеркавання памяці. Усё можа пайсці вельмі, вельмі няправільна хутка. Таму што, калі вы забыліся, каб вызваліць памяць, ці вы разыменовать некаторыя NULL паказальніка, ці вы разыменовать смецце паказальнік, што, як правіла, прыкмета таго, што вынікі? Seg віна. І вы атрымаеце гэты файл ядра некаторага ліку кілабайтах або мегабайтах , Які ўяўляе стан памяці вашай праграмы, калі ён разбіўся, але ваша праграма ў канчатковым рахунку сегментах недахопы, памылкі сегментацыі, што азначае нешта дрэннае здарылася амаль заўсёды звязаны у звязаных з памяццю памылкі, якія вы зрабілі недзе. Так Valgrind дапаможа вам знайсці такія рэчы. Гэта інструмент, які вы выкарыстоўваеце, як GDB, пасля таго як вы сабралі вашы праграмы, але замест запуску праграмы непасрэдна, Вы запускаеце Valgrind і вы перадаеце яму сваю праграму, гэтак жа, як вы робіце з GDB. Цяпер, выкарыстання, каб атрымаць лепшы від прадукцыі, гэта крыху доўга, так што тут па-над экрана вы ўбачыце Valgrind-V. "-V" амаль паўсюдна азначае, падрабязны, калі вы выкарыстоўваеце праграмы на Linux кампутар. Такім чынам, гэта азначае, выплюнуць больш дадзеных, чым вы маглі б па змаўчанні. »- Уцечка праверыць = поўны". Гэта проста кажу праверкі для ўсіх магчымых уцечак памяці, памылкі, якія я мог бы зрабіць. Гэта таксама з'яўляецца агульнай парадыгмы з Linux праграм. Наогул, калі ў вас ёсць аргументы каманднага радка, што гэта «перамыкач», , Які павінен змяніць паводзіны праграмы, і гэта адна літара, гэта-V, але калі гэта ўключаецца, проста дызайн праграміст, з'яўляецца цэлае слова або шэраг слоў, аргументаў каманднага радка пачынаецца з -. Гэта ўсяго толькі чалавек канвенцый, але вы ўбачыце іх усё больш і больш. І вось, нарэшце, "a.out" з'яўляецца адвольнае імя праграмы ў гэтым канкрэтным прыкладзе. А вось некаторыя прадстаўніком прадукцыі. 

Перш чым мы паглядзім на тое, што гэта можа азначаць, дазвольце мне перайсці да фрагмент кода тут. І дазвольце мне рухацца гэтым з шляху, у бліжэйшы час, і давайце зірнем на memory.c, што гэты кароткі прыклад. Так што ў гэтай праграме, дазвольце мне павялічыць на функцыі і пытанні. У нас ёсць асноўная функцыя, якая выклікае функцыю, F, і што ж F зраблю, у некалькі тэхнічных ангельскую мову? Што F працягнуць рабіць? Як наконт я пачну з лініі 20, і размяшчэнне зорак не мае значэння, але я проста быць паслядоўным тут з мінулым лекцыі. Што лініі 20 зрабіць для нас? На левай баку. Мы разбіць яго далей. Int * х: што ж гэта зрабіць? Добра. Гэта аб'ява паказальніка, а цяпер давайце яшчэ больш тэхнічнай. Што гэта значыць, вельмі канкрэтна, аб'явіць паказальнік? Хто-небудзь яшчэ? Да? [Студэнт адказ, неразборліва] Занадта далёка. Так што вы чытаеце ў правай часткі ад знака роўнасці. Давайце засяродзімся толькі на левым, толькі на Int * х. Гэта "аб'явіць" паказальнік, а цяпер давайце пагрузілі ў больш глыбокіх гэтага азначэння. Што гэта канкрэтна, тэхнічна маю на ўвазе? Да? [Студэнт адказ, неразборліва] Добра. Ён рыхтуе для захавання адрасы ў памяці. Добра. І давайце яшчэ адзін крок, гэта аб'ява зменнай х, гэта 32 біт. І я ведаю, што гэта 32 біт, таму што -? Гэта не таму, што гэта цэлы лік, таму што гэта паказальнік ў гэтым выпадку. Супадзенне, што гэта адно і тое ж з INT, Але тое, што там ёсць зоркі азначае, што гэта паказальнік і ў прыбор, як і ў многіх кампутарах, але не ўсё, паказальнікі з'яўляюцца 32-бітнымі. На больш сучасным абсталяванні, як апошняя Mac, апошняя ПК, вы маглі б мець 64-разрадныя паказальнікі, але ў прыбор, гэтыя рэчы з'яўляюцца 32-бітнымі. Такім чынам, мы будзем стандартызацыі на гэта. Больш канкрэтна, гісторыя ідзе наступным чынам: Мы "аб'явіць" паказальніка, што гэта значыць? Мы рыхтуем для захоўвання адрасоў памяці. Што гэта значыць? Мы ствараем зменную званую х, які займае 32 біта што хутка захаваць адрас цэлага ліку. І гэта, напэўна, прыкладна гэтак жа дакладна, як мы можам атрымаць. Гэта нармальна рухацца наперад, каб спрасціць свет і проста сказаць, аб'явіць паказальнік называецца х. Абвясьцеце паказальнік, але і зразумець, што адбываецца на самай справе нават як раз у тых некалькіх сімвалаў. 

Цяпер, на гэты раз амаль крыху лягчэй, хоць гэта больш выраз. Дык што ж гэта робіш, гэта падкрэсліў цяпер: "таНос (10 * SizeOf (INT));" Да? [Студэнт адказ, неразборліва] Добра. І я вазьму яго там. Гэта вылучэнне блока памяці на працягу дзесяці цэлых лікаў. А цяпер давайце ныраць ў ледзь глыбей, гэта вылучэнне блока памяці на працягу дзесяці цэлых лікаў. Што таНос затым вяртаюцца? Адрас гэтага блока, або, больш канкрэтна, адрас першых байта, што кавалак. Як жа я, праграміст, каб ведаць, дзе што частка памяці рэшт? Я ведаю, што гэта бесперапынна. Malloc, па вызначэнні, дасць Вам бесперапынны кавалак памяці. Няма прабелаў у ім. Вы маеце доступ да кожны байт у тым, што кавалак, спіна да спіны да спіны, але як я магу ведаць, дзе ў канцы гэтага кавалка памяці? Пры выкарыстанні таНос? [Студэнт адказ, неразборліва] Добра. Вы не робіце. Вы павінны памятаць. Я павінен памятаць, што я выкарыстаў значэнне 10, і я нават не здаецца, зрабілі гэта тут. Але адказнасць ляжыць цалкам на мне. STRLEN, што мы сталі трохі залежыць ад радкамі, працуе толькі таму, што гэтая канвенцыя наяўнасці \ 0 ці гэта спецыяльнае нулявой сімвал, NUL, у канцы радка. Гэта не выконваецца для адвольнага толькі кавалкі памяці. Гэта залежыць ад вас. Такім чынам, радок 20, то, вылучае блок памяці , Які можа захоўваць дзесяці цэлых лікаў, і ён захоўвае адрас першых байта гэтага блока памяці ў зменную х. Ergo, які з'яўляецца паказальнікам. Такім чынам, радок 21, на жаль, была памылкай. Але першае, што ён робіць? Гэта кажа крамы на месцы 10, 0 індэксуюцца, з блока памяці называецца х значэнне 0. 

Так заўважылі некалькі рэчаў, якія адбываюцца. Нават калі х з'яўляецца паказальнікам, памятаеце з пару тыдняў таму што вы ўсё яшчэ можаце выкарыстоўваць масіў у стылі квадратных дужак. Таму што на самой справе кароткія рукі пазначэнняў для больш загадкавым выгляд арыфметыкі паказальнікаў. , Дзе мы маглі б зрабіць нешта накшталт гэтага: Вазьміце адрас X, перанесці на 10 месцаў, Затым ідуць туды, каб любы адрас, захоўваюцца ў гэтым месцы. Але, шчыра кажучы, гэта проста зверскі чытаць і асвоіцца з. Такім чынам, свет звычайна выкарыстоўваюцца квадратныя дужкі толькі таму, што гэта значна больш зразумелыя чалавеку чытаць. Але вось што адбываецца на самай справе пад капотам; х адрасе, а не масіў, як такой. Такім чынам, гэта захоўванне 0 у размяшчэнне 10 у х. Чаму гэта дрэнна? Да? [Студэнт адказ, неразборліва] Менавіта так. Мы толькі вылучыў 10 цэлых лікаў, але мы разлічваем ад 0 пры праграмаванні на C, так што ў вас ёсць доступ да 0 1 2 3 4 5 6 7 8 9, а не 10. Так што альбо праграма будзе сегменце віна ці гэта не так. Але мы не ведаем, гэта свайго роду недетерминированными паводзін. Гэта сапраўды залежыць ад таго, нам пашанцуе. Калі высветліцца, што аперацыйная сістэма не пярэчыце, калі я выкарыстоўваю гэта дадатковы байт, хоць ён не даў яго мне, мая праграма не можа прывесці да збою. Гэта сыравіна, ён памылковы, але вы не можаце бачыць, што сімптом, ці вы маглі б бачыць яго толькі адзін раз у той час. Але рэальнасць такая, што памылка, на самай справе, няма. І гэта сапраўды праблематычна, калі вы напісалі праграму, якую вы хочаце быць правільнай, што вы прадалі праграмы, якія людзі выкарыстоўваюць, што кожны раз у той час аварый таму што, вядома, гэта не добра. На самай справе, калі ў вас ёсць тэлефон Android або iPhone і вы можаце спампаваць праграмы ў гэтыя дні, калі вы калі-небудзь мелі прыкладанне проста кінуць паліць, раптам ён знікае, гэта амаль заўсёды вынік некаторага звязаных з памяццю праблемы, прычым праграміст аблажаліся і разыменован паказальнік што ён ці яна не павінна мець, і вынік IOS або Android, каб проста забіць праграму ў цэлым чым рызыкаваць нявызначаны паводзіны ці нейкі кампраміс бяспекі. 

Там яшчэ адна памылка ў гэтай праграме, акрамя гэтага. Што яшчэ я аблажаўся ў гэтай праграме? Я не практыкаваў тое, што я прапаведаваў. Да? [Студэнт адказ, неразборліва] Добра. Я не вызваліў памяць. Такім чынам, правіла зараз павінна быць у любы час вы тэлефануеце таНос, вы павінны патэлефанаваць бясплатна, калі вы зрабілі з дапамогай гэтай памяці. Цяпер, калі я хачу, каб вызваліць гэтую памяць? Мабыць, мяркуючы, што гэта першая лінія была правільнай, я хацеў бы зрабіць гэта тут. Таму што я не магла б, напрыклад, зрабіць гэта тут. Чаму? Толькі з вобласці бачнасці. Таму, нават калі мы гаворым пра паказальнікаў, гэта тыдні 2 ці 3 пытання, дзе х толькі ў сферу ўнутры фігурных дужак, дзе яна была абвешчаная. Такім чынам, вы дакладна не можа вызваліць яго там. Мой адзіны шанец, каб вызваліць гэта прыкладна пасля радка 21. Гэта даволі простая праграма, гэта было даволі лёгка, калі вы выгляд загорнутыя вашага розуму вакол таго, што праграма робіць, дзе памылкі былі. І нават калі вы не бачыце яго ў першы, спадзяюся, гэта крыху відавочным, што гэтыя памылкі даволі лёгка вырашаецца і лёгка зрабіць. Але калі праграма складае больш за 12 радкоў, гэта 50 радкоў, 100 радкоў, пешшу праз код радок за радком, думаючы, што праз яго лагічна, Магчыма, але не асабліва весела рабіць, пастаянна шукае памылкі, і гэта таксама цяжка зрабіць, і таму такі інструмент, як Valgrind існуе. Дазвольце мне ісці наперад і рабіць гэтага: хай мяне адкрыць акно тэрмінала, і хай на мяне не проста запусціць памяці, так як памяць, здаецца, добра. Я атрымліваю пашанцавала. Пераходзячы да дадатковых байтах, што ў канцы масіва не здаюцца занадта праблематычна. Але дазвольце мне, тым не менш, зрабіць агульны кантроль, які проста азначае, што для праверкі Ці так гэта на самай справе правільна. 

Так давайце зробім Valgrind-V - уцечка праверыць = поўны, , А затым назва праграмы ў гэтым выпадку памяць, не a.out. Такім чынам, дазвольце мне ісці наперад і рабіць гэта. Націсніце Enter. Дарагі Бог. Гэта яе выхаду, і гэта тое, што я згадаў раней. Але, калі вы навучыцеся чытаць праз ўсё глупства тут, большасці гэта ўсяго толькі дыягнастычны выснову, што гэта не так цікава. Што вашы вочы сапраўды хоча, шукае любую згадку пра памылку або несапраўдным. Словы, якія прапануюць праблем. І на самай справе, давайце паглядзім, што адбываецца не так тут. У мяне ёсць рэзюмэ свайго роду, "у выкарыстанні на выхадзе: 40. Байт ў 1 блокаў" Я не зусім упэўнены, што блок пакуль няма, але 40 байт на самай справе адчувае, як я мог зразумець, дзе што ідзе. 40 байт. Чаму 40 байт, якія выкарыстоўваюцца на выхадзе? І больш канкрэтна, калі мы пракруціць ўніз тут, чаму я вызначана страціў 40 байт? Да? [Студэнт адказ, неразборліва] Perfect. Так, менавіта так. Былі дзесяці цэлых лікаў, і кожны з іх з'яўляецца памер 4 ці 32 біт, так што я страціў менавіта 40 байт, таму што, як вы прапанавалі, я не называюцца свабоднымі. Гэта адна памылка, і цяпер давайце паглядзім крыху далей і бачыць побач з гэтым, "Несапраўдныя запісу памерам 4". А што гэта такое? Гэты адрас выяўляецца тое, што база абазначэння, па-відаць? Гэта шаснаццатковым, і ў любы час вы бачыце нумар, які пачынаецца з 0x, гэта азначае, шаснаццатковай, які мы зрабілі адваротны шлях, я думаю, профіль PSET 0 'пытанні, , Якая была проста рабіць размінку практыкаванні, ператвараючы дзесятковай ў шаснаццатковай ў двойкавую і гэтак далей. Шаснаццаткавыя, проста чалавечыя канвенцыі, як правіла, выкарыстоўваюцца для прадстаўлення паказальнікаў ці, больш агульна, адрасу. Гэта проста канвенцыі, таму што гэта крыху лягчэй чытаць, гэта крыху больш кампактны, чым нешта накшталт дзесятковай, і бінарных бескарысныя для большасці людзей у выкарыстанні. Так што зараз гэта значыць? Ну, падобна, ёсць несапраўднай запісу памерам 4 на лініі 21 з memory.c. Так што давайце вернемся да радка 21, і сапраўды, у тым, што несапраўдныя запісу. Так Valgrind не збіраецца цалкам трымаць мяне за руку і скажыце, што выправіць гэта, але выявіўшы, што я раблю несапраўднымі запісу. Я дакранаючыся 4 байт, што не павінна быць, і, мабыць, гэта таму, што, як вы адзначылі, я раблю [10] замест [9] максімальна або [0] або нешта паміж імі. З Valgrind, разумеюць любы час Вы зараз пішу праграму , Якая выкарыстоўвае паказальнікі і выкарыстоўвае памяць, і таНос больш канкрэтна, Вызначана ўвайсці ў звычку выканання гэтага доўга але вельмі лёгка скапіяваць і ўставіць каманду Valgrind , Каб убачыць, калі ёсць нейкія памылкі там. І гэта будзе пераважнай кожны раз, калі вы бачыце выйсце, а проста разабраць праз візуальна усе выходныя і паглядзець, калі вы бачыце згадвае памылак або папярэджання або несапраўдным або страчаныя. Любыя словы, якія гучаць як вы аблажаліся недзе. Так разумею, што гэта новы інструмент у ваш інструментар. 

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

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

Што рабіць, калі мы хочам, каб маніпуляваць гэтым? Мы зрабілі вялікую частку гэтага візуальна, і з людзьмі, Але што, калі мы хочам зрабіць ўстаўкі? Такім чынам, у першапачатковым спісе было 9, 17, 20, 22, 29, 34. Што, калі мы тады хацелі таНос прастору для нумар 55, вузел для яго, і мы хочам, каб ўставіць 55 у спісе гэтак жа, як мы зрабілі ў панядзелак? Як мы гэта робім? Ну, Аніта падышла і яна па сутнасці ішоў у спісе. Яна пачалася з першага элемента, то ў наступны, наступны, наступны, наступны, наступны. Нарэшце ўдар левай ўсю дарогу ўніз і зразумелі, о, гэта NULL. Так што паказальнік маніпуляцыі трэба зрабіць? Чалавек, які быў на канцы, № 34, неабходна левай рукой падняў , Каб паказаць на 55, 55 мелі патрэбу ў іх левай рукой паказвае ўніз, каб стаць новым NULL тэрмінатар. Гатова. Даволі лёгка ўставіць 55 у адсартаваным спісе. І як гэта магло б выглядаць? 

Дазвольце мне ісці наперад і адкрываць код, напрыклад, тут. Я буду адкрываць Gedit, і дазвольце мне адкрыць два файла ў першую чаргу. Адным з іх з'яўляецца list1.h, і дазвольце мне нагадаць, што гэта быў кавалак кода , Якія мы выкарыстоўвалі для прадстаўлення вузла. Вузел мае як Int называецца п і паказальнік называюць цяпер, што проста паказвае на наступную рэч у спісе. Гэта значыць, у цяперашні час. Файлаў гадзіну. Чаму? Там у гэта пагадненне, і мы не скарысталіся гэтым вялікай колькасцю саміх сябе, але чалавек, які напісаў Printf і іншыя функцыі далі ў якасці падарунка да міру ўсе гэтыя функцыі ў пісьмовым выглядзе файла з імем stdio.h. А тут яшчэ string.h, а там Map.h, і ёсць усе гэтыя файлы г што вы, магчыма, бачылі ці выкарыстоўвалі на працягу тэрміну, напісаныя іншымі людзьмі. Звычайна ў іх. Ч файлы толькі рэчы, як ЬурейеЕ або дэкларацыі аб карыстацкіх тыпаў або дэкларацыі канстант. Вы не ставіце рэалізацыі функцыі "ў загалоўку файла. Вы ставіце, а не проста іх прататыпы. Вы змяшчаеце рэчы, якія вы хочаце падзяліцца з светам, што ім трэба Для кампіляцыі кода. Так, каб патрапіць у гэтую звычку, мы вырашылі зрабіць тое ж самае. Там не шмат у list1.h, але мы ўклалі тое, што можа прадстаўляць цікавасць для людзей у свеце якія хочуць выкарыстоўваць нашу звязанага рэалізацыі спісе. Зараз, у list1.c, я не буду ўсё гэта справа таму што гэта трохі доўга, гэтую праграму, але давайце запусцім гэта рэальна хутка ў камандным радку. Дазвольце мне скампіляваць list1, дазвольце мне запусціць list1, і тое, што вы бачыце, Мы мадэлявалі прасценькая праграма тут што адбываецца, каб дазволіць мне дадаваць і выдаляць нумары ў спіс. Такім чынам, дазвольце мне пайсці далей і ўвесці 3 для 3-меню. Я хачу, каб ўставіць нумар - давайце зробім першы нумар, які быў 9, і зараз я сказала спісе цяпер 9. Дазвольце мне ісці наперад і рабіць іншае ўстаўкі, так што я ўдарыў меню 3. Які нумар вы хочаце ўставіць? 17. Enter. І я зраблю яшчэ адну. Дазвольце мне паказаць лік 22. Такім чынам, мы маем пачатак спісам, які мы мелі ў форме слайд хвіліну таму. Як гэтая ўстаўка адбываецца на самай справе? Сапраўды, 22 у цяперашні час знаходзіцца ў канцы спісу. Так што гісторыя, якую мы распавялі на сцэне ў панядзелак і рэзюмаваў зараз павінна быць на самай справе адбываецца ў кодзе. Давайце паглядзім. Дазвольце мне пракруціць ўніз у гэтым файле. Мы будзем замоўчваць некаторыя з функцый, але мы пойдзем, скажам, функцыі ўстаўкі. 

Давайце паглядзім, як мы ідзем аб устаноўцы новага вузла ў гэтай звязаны спіс. Дзе спіс аб'яўлена? Ну, давайце вылучыце ўвесь шлях на вяршыні, і заўважыў, што мае звязаны спіс, па сутнасці абвешчаны як аднаго паказальніка, што гэта першапачаткова NULL. Так што я з дапамогай глабальнай зменнай тут, што ў цэлым мы прапаведавалі супраць таму што гэта робіць ваш код крыху брудны падтрымліваць, гэта свайго роду лянівы, як правіла, але гэта не лянота, і гэта не так, і гэта не дрэнна калі адзінай мэтай вашай праграмы ў жыцці, каб мадэляваць 1 звязаны спіс. Якія менавіта тое, што мы робім. Такім чынам, замест заявіць пра гэта ў асноўным і затым перадаць яго на кожную функцыю Мы ўжо пісалі ў гэтай праграме, мы разумеем, замест ой, давайце проста зрабіць яго глабальным таму што ўся мэта гэтай праграмы заключаецца ў дэманстрацыі аднаго і толькі аднаго звязанага спісу. Так, што адчувае сябе добра. Вось мае прататыпы, і мы не будзем прайсці праз усё гэта, Але я напісаў функцыю выдалення, знайсці функцыі, функцыі ўстаўкі і функцыі ходу. Але давайце цяпер вярнуцца ўніз да функцыі ўстаўкі і паглядзець, як гэта працуе тут. Уставіць на лініі - тут мы ідзем. Уставіць. Такім чынам, ён не прымае ніякіх аргументаў, таму што мы збіраемся папрасіць Карыстальнік ўнутры гэтай функцыі чысла яны хочуць ўставіць. Але, па-першае, мы рыхтуемся, каб даць ім прастору. Гэта свайго роду капіявання і ўстаўкі з іншы прыклад. У гэтым выпадку, мы былі выдзялення Int, на гэты раз мы выдзяленні вузла. Я сапраўды не памятаю, колькі байт вузел, але гэта нармальна. Sizeof магу зразумець, што для мяне. І чаму я праверкі на NULL ў радку 120? Што можа пайсці не так у лініі 119? Да? [Студэнт адказ, неразборліва] Добра. Проста можа быць так, што я папрасіў занадта шмат памяці ці нешта не так і аперацыйная сістэма не хапае байтаў, каб даць мне, такім чынам, гэта сігналізуе столькі, вяртаючы NULL, і калі я не правяраюць, што і я проста слепа працягваць выкарыстоўваць адрас вярнулася, яна можа быць NULL. Гэта можа быць невядомай коштам; не вельмі добрая рэч, калі я - на самай справе не будзе невядомага значэння. Гэта можа быць NULL, так што я не хачу злоўжываць гэтым і рызыкаваць разнаймення яго. Калі гэта адбудзецца, я проста вярнуцца, і мы будзем рабіць выгляд, што я не вярнуся любым памяці наогул. 

У адваротным выпадку, я кажу карыстальнік даць мне нумар, каб уставіць, я называю наш стары сябар GetInt, і тады гэта быў новы сінтаксіс мы ўвялі ў панядзелак. "Newptr-> N 'азначае ўзяць адрас, які вы далі таНос які ўяўляе сабой першы байт новы аб'ект вузла, а затым перайдзіце да вобласці, званай п. Трохі дробязі пытанне: Гэта раўнасільна таму, што больш загадкавым радкі кода? Як яшчэ я мог бы напісаць гэта? Жадаеце прыняць ўдар? [Студэнт адказ, неразборліва] Добра. Па. П., але гэта не так проста, як гэта. Што мне ў першую чаргу неабходна зрабіць? [Студэнт адказ, неразборліва] Добра. Мне трэба зрабіць * newptr.n. Такім чынам, гэта кажа новы паказальнік, відавочна, адрас. Чаму? Таму што ён быў вернуты таНос. * Newptr кажуць "туды" і як толькі вы там, то вы можаце выкарыстоўваць больш звыклы. п але гэта толькі выглядае трохі невыносны, асабліва, калі мы, людзі збіраюцца зрабіць паказальнікі са стрэлкамі ўвесь час у свеце ёсць стандартызаваная на гэтую стрэлку абазначэння, , Які робіць роўна тое ж самае. Такім чынам, вы толькі выкарыстаць -> пазначэнняў калі рэч злева паказальнік. У адваротным выпадку, калі гэта фактычная структура, выкарыстоўваць. Н. І тады гэта: Чаму я ініцыялізацыі newptr-> побач з NULL? Мы не хочам, абадраных левую руку ад канца сцэны. Мы хочам, паказваючы прама ўніз, што азначае канец гэтага спісу патэнцыйна можа быць у гэтым вузле, так што мы лепш пераканацца, што гэта NULL. І, увогуле, ініцыялізацыя пераменныя або элементы дадзеных і структуры нешта проста добрая практыка. Калі проста дазволіць смецця існуюць і працягваюць існаваць як правіла атрымлівае вас у бядзе калі вы забыліся нешта зрабіць пазней. 

Вось некалькі выпадкаў. Гэта, зноў жа, ёсць функцыі ўстаўкі, і першае, што я магу праверыць, калі зменная завецца першым, што глабальная пераменная NULL, гэта азначае, што не існуе звязанага спісу. Мы не устаўленыя лічбы, дык гэта трывіяльна, каб ўставіць гэты нумар бягучай ў спіс, таму што ён проста належыць у пачатку спісу. Так гэта было, калі Аніта проста стаяў тут адзін, прыкідваючыся нікога не было тут, на сцэне, пакуль мы вылучылі вузла, Затым яна магла падняць руку ў першы раз, калі ўсе астатнія прыйшлі на сцэну пасля яе ў панядзелак. Цяпер вось, гэта крыху праверку, дзе я павінен сказаць, што, калі новы вузла значэнне п складае <значэнне п у ​​бягучай першай вузла, , Што азначае, што ёсць звязаны спіс, які пачаўся. Там, па меншай меры адзін вузел у спісе, але гэты новы хлопец належыць да яго, такім чынам, мы павінны рухацца рэчы. Іншымі словамі, калі ў спісе пачаўся з проста, скажам так, толькі нумар 17, гэта - на самай справе, мы можам зрабіць гэта больш выразна. Калі мы пачнем наш аповяд з паказальнікам тут называюць першым, і першапачаткова гэта NULL, і мы ўстаўляем нумар 9, № 9, безумоўна, належыць у пачатку спісу. Так давайце ўявім, што мы проста malloced адрас або нумар 9 і паклаў яго тут. Калі першы 9 па змаўчанні, першы сцэнар, які мы абмяркоўвалі толькі азначае кропку давайце гэты хлопец тут, пакінуць гэта як NULL; цяпер у нас ёсць нумар 9. Наступны нумар мы хочам ўставіць складае 17. 17 належыць тут, так што мы збіраемся зрабіць некаторыя лагічныя стэпінг праз гэта. Такім чынам, давайце замест гэтага, перш чым зрабіць гэта, давайце ўявім, што мы хацелі, каб ўставіць нумар 8. 

Так што проста для выгоды, я збіраюся зрабіць тут. Але памятайце, таНос можаце пакласці яго найбольш заўгодна. Але дзеля чарцяжа, я пакладу яго тут. Так прыкідвацца, што я толькі што вылучыў вузел нумар 8, гэта NULL па змаўчанні. Што цяпер будзе? Некалькі рэчаў. Мы зрабілі гэтую памылку на сцэну ў панядзелак, дзе мы абнавілі паказальніка, як гэта, Затым зрабіў гэта, і тады мы заявілі - мы сіротамі і ўсе астатнія на сцэне. Таму што ты не можаш - парадак аперацый тут вельмі важна, таму што цяпер мы страцілі гэты вузел 9, што гэта толькі выгляд, якія плаваюць у прасторы. Так што гэта быў не правільны падыход у панядзелак. Спачатку мы павінны рабіць нешта іншае. Стан свету выглядае наступным чынам. Першапачаткова, 8 былі вылучаныя. Што было б лепшым спосабам ўстаўкі 8? Замест абнаўлення гэтага паказальніка спачатку проста абнавіць гэты тут замест гэтага. Так што мы павінны радок кода, якая збіраецца ператварыць гэты знак NULL ў фактычных паказальнік які, паказваючы на ​​вузел 9, і тады мы зможам бяспечна змяніць у першую чаргу, каб паказаць на гэты хлопец тут. Цяпер у нас ёсць спіс, звязаны спіс, з двух элементаў. І што гэта на самай справе выглядае тут? Калі мы паглядзім на код, заўважылі, што я зрабіў менавіта гэта. Я сказаў newptr, і ў гэтай гісторыі, newptr паказваў на гэтага хлопца. 

Такім чынам, дазвольце мне зрабіць яшчэ адну рэч, і я павінен быў пакінуць трохі больш месца для гэтага. Так што даруйце маленькі малюнак. Гэты хлопец называецца newptr. Гэта значыць зменная, якую мы абвясцілі некалькі радкоў раней, у лінію - ледзь вышэй 25. І гэта паказвае на 8. Таму калі я кажу newptr-> Далей, гэта азначае, што пайсці на структуру што быццё, на які паказвае newptr, таму мы тут, ідзіце туды. Тады стрэлкі кажуць атрымаць наступнае поле, а затым = кажуць пакласці тое, што значэнне там? Значэнне, якое было ў першым, якое значэнне было ў першую чаргу? Першы быў накіраваны на гэтым вузле, так што азначае, што гэта павінны цяпер паказваць на гэтым вузле. Іншымі словамі, тое, што выглядае хоць і смешна важдацца з маім почыркам, што простая ідэя проста перасоўванне гэтыя стрэлкі вакол транслюецца ў код ўсяго гэтага лайнера. Захоўвайце тое, што ў першыя ў наступным поле, а затым абнавіць тое, што спачатку на самай справе. Давайце ісці наперад і перамотка наперад праз некаторыя з гэтага, і глядзець толькі на гэты хвост ўстаўкі на дадзены момант. Выкажам здагадку, што я дабрацца да кропкі, дзе я знаходжу, што ў наступным поле некаторага вузла NULL. І ў гэты момант у гісторыі, падрабязна, што я замазвання з'яўляецца тое, што я прадставіў яшчэ адзін паказальнік тут, у лініі 142, папярэднік паказальнік. Па сутнасці, у гэты момант у гісторыі, калі спіс становіцца доўгім, Я, здаецца, мусяць ісці ён двума пальцамі, таму што калі я іду занадта далёка, Памятаецца, у адной даўжыні спісу, вы не можаце пайсці ў зваротным кірунку. Так што гэтая ідэя predptr мой палец левай рукі, і newptr - не newptr. Іншым паказальнікам, што гэта вось мой іншы палец, і я накшталт як хадзіць па спісе. Вось чаму, што існуе. Але давайце разглядаць толькі адзін з самых простых выпадкаў тут. Калі ў наступным поле, якое з'яўляецца паказальнікам NULL, што лагічнага следавання? Калі вы абыходу гэтага спісу, і вы патрапілі NULL паказальніка? Ты ў канцы спісу, і таму код, каб затым дадаць гэты адзін дадатковы элемент з'яўляецца свайго роду інтуітыўнае будзе лічыць, што вузел якога наступны паказальнік NULL, так што гэта ў цяперашні час NULL, і змяніць яго, хоць, як адрас новага вузла. Так што мы проста малюнак у кодзе стрэлкі, што мы звярнулі на сцэну, падымаючы левую руку нехта. 

І так, што я махаю рукамі на дадзены момант, проста таму што я думаю, што гэта лёгка заблудзіцца, калі мы робім гэта ў такую ​​сераду, правярае для ўстаўкі ў сярэдзіне спісу. Але толькі інтуітыўна, што павінна адбыцца, калі вы хочаце, каб высветліць дзе некаторы лік павінна стаяць у сярэдзіне, вы павінны ісці ён з больш чым адным пальцам, больш як аднаго паказальніка, высветліць, дзе яна належыць па праверцы з'яўляецца элемент <бягучы, > Бягучы, і як толькі вы выявіце, што месца, Затым вы павінны рабіць такога роду абалонкі гульні, дзе вы перамяшчаеце паказальнік вакол вельмі старанна. І гэты адказ, калі вы хочаце, каб праз гэтую прычыну ў сябе дома на свой уласны, зводзіцца толькі да гэтых двух радкоў кода, але парадак гэтых радкоў гэта супер важна. Таму што, калі вы выпусціце нечую руку і падняць чужога не ў тым парадку, зноў, вы маглі б у канчатковым выніку сіротамі спісу. Падводзячы вынік больш канцэптуальна, устаўкі ў хвост адносна простая. Устаўкі ў галаву таксама адносна простая, але вам неабходна абнавіць дадатковы паказальнік на гэты раз выціснуць нумарам 5 у спісе тут, а потым ўстаўка ў сярэдзіне ўключае ў сябе яшчэ больш намаганняў, вельмі асцярожна ўставіць лік 20 ў правільным месцы, якая знаходзіцца паміж 17 і 22. Так што вам трэба зрабіць нешта накшталт ёсць новы вузел 20 пунктаў да 22, , А затым, паказальнік, які вузла павінна быць абноўленая ў апошні раз? Гэта 17, на самай справе яго ўставіць. Такім чынам, яшчэ раз, я буду адкласці фактычны код для гэтай канкрэтнай рэалізацыі. 

На першы погляд, гэта крыху пераважнай, але гэта сапраўды проста бясконцы цыкл якая цыклы, цыклы, цыклы, цыклы і парушэнні, як толькі вы патрапілі ў NULL паказальніка, у які момант вы можаце зрабіць неабходныя ўстаўкі. Гэта, такім чынам, з'яўляецца прадстаўніком звязаныя пералік кодаў ўстаўкі. Гэта было даволі шмат, і ён адчувае, як мы вырашылі адну праблему, але мы ўвялі цэлы іншы. Шчыра кажучы, мы выдаткавалі ўвесь гэты час на вялікіх O і Ω і час працы, спрабуючы вырашыць праблемы хутчэй, і тут мы робім вялікі крок назад, гэта адчувае. І ўсё ж, калі мэта для захоўвання дадзеных, ён адчувае, як Святы Грааль, як мы ўжо казалі ў панядзелак, будзе сапраўды для захоўвання рэчаў імгненна. 

На самай справе, выкажам здагадку, што мы зрабілі адкласці ў бок звязанага спісу на імгненне а мы замест гэтага ўведзена паняцце табліцы. І давайце проста думаць пра табліцы на імгненне ў выглядзе масіва. Гэты масіў і гэты выпадак тут маецца каля 26 элементаў, ад 0 да 25, і выкажам здагадку, што вам трэба некаторы кавалак для захоўвання назваў: Аліса і Боб і Чарлі і таму падобнае. І вам патрэбна структура дадзеных для захоўвання гэтых імёнаў. Ну, вы можаце выкарыстоўваць нешта накшталт звязаны спіс і вы маглі ісці спісе ўстаўкі Аліса перад Бобам і Чарлі пасля таго, як Боб і гэтак далей. І на самай справе, калі вы хочаце, каб убачыць код, як, што, як і ў бок, Вядома, што ў list2.h, мы робім менавіта гэта. Мы не будзем ісці па гэтым коду, але гэта варыянт першы прыклад , Які ўводзіць яшчэ адну структуру мы бачылі раней званая студэнта, і тое, што ён на самай справе захоўваюцца ў звязаным спісе з'яўляецца паказальнікам на структуру студэнта а не проста лікам мала, с. Так разумею, што гэта код там, што ўключае ў сябе фактычныя радкі, Але калі мэта пад рукой сапраўды цяпер з'яўляецца рашэнне праблемы эфектыўнасці, Не было б нядрэнна, калі мы дадзены аб'ект пад назвай Alice, Мы хочам, каб змясціць яе ў патрэбным месцы ў структуры дадзеных, ён адчувае, як гэта было б вельмі прыемна проста паставіць Аліса, чыё імя пачынаецца з, у першым месцы. І Боб, чыё імя пачынаецца з B, у другім месцы. З масівам, або давайце пачнём называць яго сталом, хэш-табліцы ў тым, што мы можам зрабіць менавіта гэта. Калі дадзена імя, як Аліса, Радок як Аліса, дзе ты паклаў-л-і-з-е? Мы павінны hueristic. Нам патрэбна функцыя прыняць некаторыя ўваходныя як Аліса і вярнуць адказ: "Пакладзі Аліса ў гэтым месцы". І гэтая функцыя, гэта чорны скрыню, будзе называцца хэш-функцыі. 

Хэш-функцыі з'яўляецца тое, што займае ўваход, як «Аліса», і вяртаецца да вас, як правіла, лікавыя месца ў некаторай структуры дадзеных, дзе Аліса належыць. У гэтым выпадку наша хэш-функцыя павінна быць адносна просты. Наш хэш-функцыя павінна сказаць, што калі вы атрымліваеце «Аліса», характар ​​якога я павінен клапаціцца аб? Першы. Так што я гляджу на [0], а затым я кажу, калі [0] характар, вяртаецца лік 0. Калі гэта B, вярнуць 1. Калі гэта C, вярнуць 2, і гэтак далей. Усе 0 індэкса, і якая дазволіла б мне, каб ўставіць Алісай і Бобам, то і тады Чарлі і г. д. у гэтую структуру дадзеных. Але ёсць адна праблема. Што рабіць, калі Аніта прыходзіць зноў? Куды пакласці Аніта? Яе імя таксама пачынаецца з літары А, і ён адчувае, як мы зрабілі яшчэ большы беспарадак гэтай праблемы. Цяпер у нас ёсць неадкладнае ўвядзенне, пастаянны час ўстаўкі, у структуру дадзеных чым горш справы лінейныя, Але што мы можам зрабіць з Анітай у гэтым выпадку? Якія два варыянты, на самай справе? Да? [Студэнт адказ, неразборліва] Такім чынам, мы маглі б мець іншае вымярэнне. Гэта добра. Такім чынам, мы можам пабудаваць рэчы ў 3D, як мы казалі аб вусна ў панядзелак. Мы маглі б дадаць яшчэ адзін доступе тут, але выкажам здагадку, што няма, я спрабую трымаць гэта простым. Уся мэта тут складаецца, каб мець непасрэднае пастаяннае час доступу, так вось дадаючы занадта шмат складанасці. Якія іншыя варыянты, калі спрабую ўставіць Аніта ў гэтую структуру дадзеных? Да? [Студэнт адказ, неразборліва] Добра. Такім чынам, мы маглі рухацца ўсе астатнія ўніз, як Чарлі штуршкі ўніз Боба і Алісы, а затым пакласці Аніта, дзе яна сапраўды хоча быць. 

Вядома, зараз, ёсць пабочны эфект гэтага. Гэтая структура дадзеных, верагодна, карысна не таму, што мы хочам ўставіць людзі раз а таму, што мы хочам праверыць, калі яны там пазней калі мы хочам, каб раздрукаваць ўсе імёны ў структуры дадзеных. Мы збіраемся зрабіць нешта з гэтымі дадзенымі ў рэшце рэшт. Такім чынам, зараз мы накшталт п'яны за Алісу, якая больш не дзе яна павінна быць. Не з'яўляецца Боб, ні Чарлі. Таму, магчыма, гэта не такая ўжо добрая ідэя. Але на самай справе, гэта адзін варыянт. Мы маглі зрушыць усё ўніз, ці чорт вазьмі, Аніта прыйшла позна ў гульні, чаму б нам не проста паставіць Anita Не тут, не тут, не тут, давайце проста пакласці яе крыху ніжэй у спісе. Але тады гэтая праблема пачынае пераходзіць зноў. Вы можаце быць у стане знайсці Алісу імгненна, заснаваны на яе імя. І Боб імгненна, і Чарлі. Але тады вы паглядзіце на Аніту, і вы ўбачыце, хм, Аліса ў шлях. Добра, дазвольце мне праверыць ніжэй Аліса. Боб не Аніта. Чарлі не Аніта. О, ёсць Аніта. І калі вы будзеце працягваць гэты цягнік логіцы да канца, Што найгоршае час выканання пошуку або ўстаўкі Аніта ў гэтую новую структуру дадзеных? Гэта Аб (п), правільна? Таму што ў горшым выпадку, ёсць Аліса, Боб, Чарлі. . . Усё, аж да нейкай "Y", таму ёсць толькі адно месца засталося. На шчасце, у нас ніхто не называў "Z", таму мы змясцілі Аніта ў самым нізе. 

Мы яшчэ не вырашылі гэтую праблему. Таму, магчыма, мы павінны ўвесці гэта трэцяе вымярэнне. А то атрымліваецца, калі мы ўвесці гэта трэцяе вымярэнне, мы не можам зрабіць гэта выдатна, але Святой Грааль будзе атрымліваць пастаянны час ўстаўкі і дынамічныя ўстаўкі, так што Мы не павінны жорстка-кода масіў памеру 26. Мы можам ўставіць як шмат імёнаў, як мы хочам, але давайце возьмем наш 5-хвілінны перапынак тут , А затым зрабіць гэта правільна. Добра. Я паставіў гісторыю ўверх даволі штучна існуе выбраўшы Аліса і Боб затым і Чарлі, а затым Аніта, чыё імя было відавочна, будзе сутыкацца з Алісай. Але пытанне, які мы скончылі ў панядзелак толькі, як верагоднае гэта што вы атрымаеце гэтыя віды сутыкненняў? Іншымі словамі, калі мы пачнем выкарыстоўваць гэтую таблічную структуру, якая на самай справе масіў, У гэтым выпадку з 26 месцаў, Што рабіць, калі нашы ўваходы, а раўнамерна размеркавана? Гэта не штучна Аліса і Боб і Чарлі і Дэвіда і гэтак далей па алфавіце, яна раўнамерна размеркавана па да Z. 

Можа быць, мы проста пашанцуе, і мы не збіраемся мець два ці два Б з вельмі высокай верагоднасцю, але, як хтосьці паказаў, калі мы абагульнілі гэтую праблему і не рабіць ад 0 да 25 але, скажам, ад 0 да 364 або 65, часта колькасць дзён у звычайным годзе, і задаў пытанне: "Што верагоднасць таго, што два з нас у гэтай зале ёсць той жа дзень нараджэння?" Інакш кажучы, тое, што верагоднасць таго, што два з нас ёсць імя, якое пачынаецца з? Такое пытанне тое ж самае, але гэта адрасная прастора, гэта прастора пошуку, больш у выпадку нараджэння, таму што ў нас яшчэ вельмі шмат дзён у годзе, чым літар у алфавіце. Якая верагоднасць сутыкнення? Ну, мы можам думаць пра гэта, высвятляючы, матэматыка наадварот. Якая верагоднасць сутыкнення не? Ну, гэты выраз тут кажа, што тое, што верагоднасць калі ёсць толькі адзін чалавек у гэтым пакоі, што ў іх ёсць унікальная дзень нараджэння? Гэта на 100%. Таму што калі ёсць толькі адзін чалавек у пакоі, яго ці яе нараджэння можа быць любы з 365 дзён у годзе. Такім чынам, 365/365 варыянтаў дае мне значэнне 1. Такім чынам, верагоднасць якіх ідзе гаворка ў дадзены момант знаходзіцца ўсяго ў 1. Але калі ёсць другі чалавек у пакоі, што верагоднасць таго, што свой дзень нараджэння па-іншаму? Там толькі 364 магчымых дзён, без уліку высакосны гадоў, на свой дзень нараджэння, каб не сутыкнуцца з іншымі асобамі. Такім чынам, 364/365. Калі трэцяя асоба прыходзіць, гэта 363/365, і гэтак далей. Такім чынам, мы размножвацца разам гэтыя фракцыі, якія становяцца ўсё менш і менш, высветліць, якая верагоднасць таго, што ва ўсіх нас ёсць унікальная дзень нараджэння? Але тады мы можам, вядома, проста прыняць гэты адказ і перавярнуць яго вакол і зрабіць 1 мінус усё, што выраз мы ў рэшце рэшт атрымаем калі вы памятаеце заднюю частку кнігі матэматыка, гэта выглядае крыху нешта накшталт гэтага, які значна лягчэй інтэрпрэтаваць графічна. І гэта графічнае тут мае на восі х колькасць нараджэнняў, ці колькасць людзей з нараджэння, а па восі Y ёсць верагоднасць матчу. І што гэта кажа, што калі ў вас ёсць, скажам, нават, давайце абярэм нешта накшталт 22, 23. Калі ёсць 22 або 23 чалавек у пакоі, Верагоднасць таго, што два з тых вельмі нешматлікіх людзей будуць мець той жа дзень нараджэння на самай справе вельмі высока, камбінаторныя. 50% шанцаў, што ў класе ўсяго 22 чалавек, семінараў, практычна, 2 з гэтых людзей будуць мець той жа дзень нараджэння. Таму што ёсць вельмі шмат спосабаў, якімі вы можаце мець той жа дзень нараджэння. Яшчэ горш, калі вы паглядзіце на правую частку дыяграмы, да таго часу, у вас ёсць клас з 58 студэнтаў у ім, Верагоднасць 2 чалавекі свой дзень нараджэння супер, супер высокая, амаль 100%. Дык вось, гэта свайго роду пацешны факт аб рэальным жыцці. 

Але наступствы, цяпер, для структур дадзеных і захоўвання інфармацыі азначае, што толькі калі ў вас ёсць добрае, чыстае, раўнамернае размеркаванне дадзеных і ў вас ёсць дастаткова вялікі масіў, каб адпавядаць кучу рэчаў не азначае, што вы збіраецеся прымусіць людзей у унікальных месцах. Вы будзеце мець сутыкненняў. Такім чынам, гэта паняцце мяшання, як гэта называецца, прымаючы ўваход, як "Аліса" і масажуючы яго ў пэўным сэнсе , А затым атрымаць назад адказ тыпу 0 або 1 або 2. Вяртаючыся некаторых выхадзе з гэтай функцыі пакутуюць ад гэтай верагоднасці сутыкнення. Так як мы можам апрацоўваць гэтыя сутыкнення? Ну, на адным выпадку, мы можам прыняць ідэю, што было прапанавана. Мы можам проста перакласці ўсё ўніз, або, магчыма, трохі прасцей, , А не рух і ўсе астатнія, давайце рухацца Anita на дно вольнае месца. Так што, калі Аліса ў 0, Боб знаходзіцца ў 1, Charlie знаходзіцца ў 2, Мы проста пакласці Anita на месцы 3. І гэта тэхніка, у дадзеных структурах, званых лінейных зандзіравання. Лінейная, таму што вы проста хадзіць гэтую лінію, і вы роду зандаванне даступных месцаў у структуры дадзеных. Вядома, гэта ператворыцца ў O (N). Калі структура дадзеных сапраўды поўны, ёсць 25 чалавек, у ім ужо, , А затым Аніта прыходзіць, яна заканчваецца на тое, што б размяшчэнне Z, і гэта нармальна. Яна па-ранейшаму падыходзіць, і мы можам знайсці яе пазней. 

Але гэта ідзе насуперак з мэтай паскарэння рэчы. Так што, калі мы замест гэтага ўвёў гэта трэцяе вымярэнне? Гэты метад звычайна называюць асобныя ланцужкі, або з ланцугамі. І тое, што хэш-табліцу зараз, гэта Таблічная структура, Ваш стол гэта проста масіў паказальнікаў. Але тое, што гэтыя паказальнікі паказваюць на тое здагадку, што? Звязаны спіс. Так што, калі ўзяць лепшае з абодвух сьветаў? Мы выкарыстоўваем масівы зыходных паказчыкаў у структуры дадзеных, таму мы можам адразу перайсці да [0] [1], [30] і гэтак далей, але так, што ў нас ёсць пэўная гнуткасць, і мы можам падыходзіць Аніта і Эліс і Адам і любыя іншыя назвы, мы замест гэтага хай іншыя восі расці як заўгодна. І мы, нарэшце, як у панядзелак, ёсць, што выразныя магчымасці з звязанага спісу. Мы можам вырошчваць структуры дадзеных адвольна. Акрамя таго, мы маглі б проста зрабіць велізарны 2-мерны масіў, але гэта будзе жахлівая сітуацыя, калі адзін з радкоў у 2-мерны масіў не з'яўляецца дастаткова вялікім для дадатковага чалавека, чыё імя адбываецца пачаць з A. Не дай Бог мы павінны пераразмеркаваць велізарны 2-мернай структуры толькі таму, што ёсць вельмі шмат людзей па імені, Асабліва, калі ёсць так мала людзей па імя Z нешта. Гэта проста будзе вельмі рэдкай структурай дадзеных. Так што гэта не ідэальны любым спосабам, але цяпер мы па крайняй меры, мець магчымасць імгненна знайсці, дзе Аліса і Аніта належыць, па крайняй меры, з пункту гледжання вертыкальнай восі, а потым мы проста павінны вырашыць, куды змясціць Anita або Аліса ў краіне гэта звязаны спіс. Калі мы не будзем клапаціцца аб сартаванні рэчаў, як хутка мы можам ўставіць Аліса ў структуру, як гэта? Гэта пастаяннае час. Мы індэкса ў [0], і калі ніхто, Аліса ідзе ў пачатку, што звязаны спіс. Але гэта не велізарная здзелка. Таму што калі Аніта затым прыходзіць разам некаторы колькасць крокаў праз, адкуль Аніта належаць? Ну, [0]. ООП. Аліса ужо ў тым, што звязаны спіс. 

Але калі мы не клапоцімся пра сартаванні гэтыя імёны, мы можам проста перамясціць Аліса больш, устаўкі Аніта, але нават гэта пастаяннае час. Нават калі ёсць Эліс і Адам, і ўсе гэтыя іншыя імёны, гэта сапраўды не зрушваючы іх фізічна. Чаму? Таму што мы толькі што зрабілі тут з звязаны спіс, хто ведае, ці былі гэтыя вузлы так ці інакш? Усё, што вам трэба зрабіць, гэта перамясціць хлебныя крошкі. Перамяшчэнне стрэлкі вакол, вы не павінны фізічна перамяшчаць любыя дадзеныя вакол. Такім чынам, мы можам ўставіць Аніта, у такім выпадку, неадкладна. Сталая часу. Такім чынам, мы маем пастаянны час пошуку, і пастаянная часу ўвядзення такога чалавека, як Аніта. Але выгляд спрошчанага свету. Што рабіць, калі пазней мы хочам знайсці Алісу? Што рабіць, калі пазней мы хочам знайсці Алісу? Колькі крокаў з'яўляецца тое, што збіраецеся зрабіць? [Студэнт адказ, неразборліва] Менавіта так. Колькасьць людзей, перш чым Аліса ў звязаным спісе. Так што гэта не зусім дасканалы, таму што нашы структуры дадзеных, зноў жа, гэта мае вертыкальную доступу І тады ён гэтыя звязаныя спісы вісяць - на самай справе, давайце не будзем маляваць масіва. Ён гэтыя звязаныя спісы, віслыя ад гэтага, што выглядае трохі нешта накшталт гэтага. Але праблема ў тым, калі Аліса і Адам, і ўсе гэтыя іншыя імёны у канчатковым выніку ўсё больш і больш там, знайсці каго-то, можа ў канчатковым выніку прымае кучу крокаў, bcause Вы павінны прайсці звязанага спісу, , Якая з'яўляецца лінейнай аперацыяй. Так на самай справе, то, у канчатковым рахунку, час ўстаўкі з'яўляецца O (N), дзе N лік элементаў у спісе. Падзеленыя, давайце ўмоўна называем яе, дзе т лік звязаных спісаў што мы маем у гэтай вертыкальнай восі. Іншымі словамі, калі мы сапраўды лічыць раўнамерным размеркаваннем імёнаў, цалкам нерэальна. Там, відавочна яшчэ некаторых літар, чым іншыя. 

Але калі мы выкажам здагадку, на дадзены момант раўнамернае размеркаванне, і мы п поўных людзей, і м агульнай ланцугу наяўныя ў нас, то даўжыня кожнай з гэтых ланцугоў дастаткова проста будзе агульны, п дзеліцца на колькасць ланцугоў. Такім чынам, п / т. Але вось дзе мы можам быць матэматычна ўсе разумныя. м з'яўляецца сталым, таму што там фіксаваны лік з іх. Вы збіраецеся абвясціць масіў у пачатку, і мы не змена памеру вертыкальнай восі. Па вызначэнні, якая застаецца фіксаванай. Гэта толькі па гарызантальнай восі, так бы мовіць, усё мяняецца. Такім чынам, тэхнічна, гэта канстанта. Так што цяпер, час ўстаўкі у значнай ступені O (N). Так што не адчувае сябе ўсё, што нашмат лепш. Але тое, што тут праўда? Ну, усё гэта час, на працягу тыдняў, мы казалі O (N ²). Аб (п), 2 х п ², - я, дзеленай на 2. . . Чэха. Гэта проста п ². Але цяпер, у гэтай частцы семестра, мы можам пачаць казаць аб рэальным свеце зноў. А п / т абсалютна хутчэй, чым проста п у адзіночку. Калі ў вас ёсць тысячы імёнаў, і вы разбіць іх на некалькі каўшоў так што ў вас толькі дзесяць імёнаў у кожнай з гэтых ланцугоў, Абсалютна пошуку 10 рэчаў, гэта будзе хутчэй, за тысячу рэчаў. І вось адна з мноства маючых адбыцца праблема будзе вам выклік думаць менавіта аб тым, што, хоць, ды, асімптатычна і матэматычна, гэта яшчэ толькі лінейныя, якая ўсмоктвае ў цэлым, спрабуючы знайсці рэчы. На самай справе, гэта будзе хутчэй, чым з-за гэтага дзельніка. І там зноў будзе гэты кампраміс і гэты канфлікт паміж тэорыяй і рэальнасцю, і адным з рэгулятараў пачне круціцца ў гэты момант у семестр Больш рэальнасці адзін, як мы накшталт як рыхтавацца да канца semster, у як мы ўвядзем у свеце вэб-праграмавання, дзе сапраўды, прадукцыйнасць будзе разлічваць, таму што вашы карыстачы будуць пачынаюць адчуваць і шанаваць бедных дызайнерскіх рашэнняў. 

Такім чынам, як вы ісці аб рэалізацыі звязаных - хэш-табліцу з 31 элементамі? А папярэдні прыклад быў адвольным аб днях нараджэння. Калі ў кагосьці ёсць дзень нараджэння 1 студзеня ці 1 лютага, мы змесцім іх у гэтым вядры. Калі гэта 2 студзеня, 2 лютага, 2 сакавіка, мы змесцім іх у гэтым вядры. Вось чаму ён быў 31 год. Як вы абвясьцеце хэш-табліцы? Гэта можа быць даволі простым, вузел табліцы * маё адвольнае імя для яго, [31]. Гэта дае мне 31 паказальнікаў на вузлы, і які дазваляе мне ёсьць 31 паказальнікаў на звязаныя спісы нават калі гэтыя сеткі першапачаткова NULL. Што я хачу паставіць, калі я хачу захаваць "Аліса", "Боб", "Чарлі"? Ну, нам трэба, каб абгарнуць гэтыя рэчы ў структуры таму што нам патрэбна Аліса, каб паказаць на Боба, каб яна паказвала на Чарлі, і гэтак далей. Мы не можам проста маюць імёны ў адзіночку, таму я мог бы стварыць новую структуру пад назвай вузла тут. 

Што такое фактычнае вузла? Што такое вузел у гэтай новай звязаны спіс? У першую чаргу, называецца словам, для імя чалавека. ДАЎЖЫНЯ, па-відаць, адносіцца да максімальнай даўжыні імя чалавека, у што б гэта, 20, 30, 40 знакаў у вар'ят выпадках кут, і 1 для чаго? Гэта проста дадатковы сімвал NULL, \ 0. Такім чынам, гэты вузел ўпакоўка "нешта" ўнутры сябе, але ён таксама аб'яўляе паказальнік называецца наступная так што мы можам ланцуга Алісы да Боба Чарлі і гэтак далей. Можа быць NULL, але не абавязкова павінны быць. Любыя пытанні па гэтых хэш-табліцы? Да? [Студэнт задаючы пытанне, неразборліва] масіва - добры пытанне. Чаму гэта сімвал слова ў масіве, а не проста сімвал *? У гэтым некалькі адвольна, напрыклад, я не хачу, каб прыйсьці у таНос для кожнага з арыгінальнага назвы. Я хацеў бы аб'явіць максімальны аб'ём памяці для радкі так што я мог скапіяваць у структуру Alice \ 0, а не мець справу з таНос і бясплатныя і таму падобнае. Але я магу зрабіць, калі я хацеў быць больш свядомымі выкарыстанне прасторы. Добры пытанне. Такім чынам, давайце паспрабуем абагульніць ад гэтай і засяродзіцца рэшту сёння на структуры дадзеных у цэлым і іншыя праблемы, якія можна вырашыць з выкарыстаннем тых жа асновах нават калі гэтыя структуры самі могуць адрознівацца ў дэталях. 

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

Што такое шаблон ў тым, як мы заклалі на гэта ці як Патрык паклаў яго ў сваім відэа? Гэта свайго роду відавочна, што ёсць некаторыя сартаванне адбываецца тут, але тое, што гэта простае правіла? Да? [Студэнт адказ, неразборліва] Perfect. Калі зірнуць на гэта, вы ўбачыце невялікі лік злева, вялікія лічбы на левай, але гэта дакладна для кожнага вузла. Для кожнага вузла, яго левая дзіцяці менш, чым ён, і яго права дзіцяці больш, чым ён. Што гэта азначае зараз, калі я хачу знайсці гэтую структуру дадзеных, скажам, лікі 44, Я павінен пачаць з кораня, так як ва ўсіх гэтых больш складаных структур дадзеных цяпер, у нас ёсць толькі паказальнік на адным, самым пачатку. І ў гэтым выпадку, пачатак кораня. Гэта не левым краі, гэта корань гэтай структуры. Так што я бачу вось 55, і я шукаю 44. У якім кірунку вы хочаце паехаць? Ну, я хачу пайсці налева, таму што, відавочна, справа будзе занадта вялікім. Такім чынам, заўважыць тут, ты накшталт канцэптуальна высечкі дрэў у два разы таму што вы ніколі не спускаючыся ў правы бок. Так што цяпер я іду ад 55 да 33. Гэта занадта малое лік. Я шукаю 44 гадоў, але цяпер я ведаю, калі 44, у гэтым дрэве, я магу пайсці, відавочна, з правага боку. Такім чынам, яшчэ раз, я абразанне дрэў у два разы. Гэта ў значнай ступені ідэнтычныя канцэптуальна ў тэлефонную кнігу. Гэта ідэнтычна таго, што мы зрабілі з паперы на дошку, але гэта больш складаная структура, якая дазваляе нам на самой справе гэта падзяляй і ўладар дызайн алгарытму, і на самай справе, праходзячы структуры, як гэта - воклічы. Абыход структуры, як гэта, дзе гэта толькі "ісці па гэтым шляху або ісці па гэтым шляху", азначае, што ўсё, што код, які нахіліўся ваш розум у першую чаргу пры яго ажыццяўленні ў раздзеле або пешшу праз яе дома, для бінарнага пошуку, з дапамогай рэкурсіі або ітэрацыі, гэта боль у шыі. Знайсці сярэдняга элемента, то зрабіць вашу акругленне уверх ці ўніз. 

Там у прыгажосці гэтага, таму што цяпер мы можам выкарыстоўваць рэкурсіі зноў, але значна больш акуратна. На самай справе, калі вы на лік 55, і вы хочаце, каб знайсці 44, Вы ідзіце налева ў гэтым выпадку, тое, што вы робіце? Вы запускаеце той жа алгарытм. Вы правяраеце значэнне вузла, то вы ідзяце налева або направа. Затым вы правяраеце значэнне вузла, перайдзіце налева або направа. Гэта ідэальна падыходзіць для рэкурсіі. Так што, хоць у мінулым мы зрабілі некаторыя даволі адвольныя прыклады з удзелам рэкурсіі , Якія не павінны быць рэкурсіўнага, з дадзенымі СТРУКТУР, Асабліва дрэвы, гэта ідэальнае ўжыванне гэтай ідэі з праблемай, скарачэнне яе, а затым рашэнне таго ж тыпу, але меншага, праграмы. 

Так што ёсць іншая структура дадзеных, мы можам ўвесці. Гэта адна прызначана на першы погляд выглядаюць загадкава, але гэта дзіўна. Так што гэта структуры дадзеных, званай выглядзе дрэва, Trie, які атрымліваецца ў спадчыну ад слова пошуку, якія не вымаўляюцца зноў паспрабаваць-вал, але гэта тое, што свет называе гэтыя рэчы. Спрабуе. Т-т-і-е. Ён уяўляе сабой дрэвападобную структуру нейкі, але кожны з вузлоў у выглядзе дрэва здаецца, што? І гэта крыху ўводзіць у зман, таму што гэта свайго роду скарочаным. Але, падобна, кожны вузел у гэтым Trie на самай справе з'яўляецца масівам. І хоць аўтар гэтай схеме не паказана гэта, У дадзеным выпадку, гэта Trie гэта структура дадзеных, мэта якога ў жыцці, каб захоўваць словы як-л-і-з-е-ці У-О-У. І тое, якім чынам гэтая Аліса сховішчаў дадзеных і Боб і Чарлі і Аніта і г. д. яно выкарыстоўвае масіў для захоўвання якіх Аліса ў выглядзе дрэва, мы пачынаем з каранёвага вузла, які выглядае як масіў, і гэта было напісана ў скарочанай форме. Аўтар апушчаны ABCDEFG, таму што не было ніякіх імёнаў з гэтым. Яны толькі паказалі М і Р і Т, але ў дадзеным выпадку, давайце пяройдзем ад Аліса і Боб і Чарлі некаторыя імёны, якія знаходзяцца тут. Максвел на самай справе ў гэтай схеме. Так як жа аўтар краме M - х-ш-е-л-л? Ён або яна пачалася ў каранёвай вузел, і пайшоў [M], такім чынам, прыкладна 13, 13 месца ў масіве. Затым адтуль, ёсць паказальнік. Паказальнікаў, якія вядуць да іншай масіў. Адтуль аўтар індэксавацца ў гэты масіў на месцы, як паказана там у левым верхнім куце, і тады ён ці яна вынікае, што паказальнік на іншы масіў, і пайшоў да паказальніка на месца X. Тады ў наступны масіў размяшчэння W, E, L, L, і гэтак далей, І, нарэшце, давайце на самой справе спрабуюць паставіць карціну да гэтага. Што робіць вузел выглядае ў кодзе? Вузле ў выглядзе дрэва змяшчае масіў паказальнікаў на некалькіх вузлах. Але ёсць і павінен быць свайго роду лагічнае значэнне, па меншай меры, у гэтай рэалізацыі. Я, здараецца, называюць яго is_word. Чаму? Таму што, калі вы ўстаўкі Максвел, вы не ўстаўляючы нічога ў гэтай структуры дадзеных. Вы не пішаце M. вы не пішаце X. Усё, што вы робіце, наступныя паказальнікі. Паказальнік, які ўяўляе М, то паказальнік, які ўяўляе, Затым паказальнік, які ўяўляе X, то W, E, L, L, але тое, што вам трэба зрабіць, у канцы накшталт пайсці, праверыць, я дабраўся да гэтага месца. Існаваў слова, якое заканчваецца ў структуры дадзеных. 

Так што Trie сапраўды напоўнены і аўтар абраў у якасці прадстаўніка гэтыя terminuses з невялікімі трыкутнікамі. Гэта проста азначае, што факт гэты трохкутнік тут, гэта лагічнае значэнне ісціны азначае, што калі вы ідзяце таму ў дрэва, , Што азначае слова імя Максвелла ў гэтым. Але слова Фу, напрыклад, Не ў дрэве, таму што калі я пачну ў каранёвым вузле тут на вяршыні, Там няма F паказальнік, паказальнік не пра, няма паказальнікаў а. Foo гэта не імя, у гэтым слоўніку. Але ў адрозненне ад, Т'юрынг, т-у-т-і-н-г. Зноў жа, я не захоўваеце т або і ці г ці я ці н або г. Але я зрабіў краму ў гэтую структуру дадзеных значэнне праўдзівы шлях тут, у гэтым вузле - у дрэва , Усталяваўшы для гэтага лагічнае значэнне is_word да ісціны. Так Trie гэта свайго роду гэта вельмі цікава мета структуры, дзе вы сапраўды не захоўванне саміх слоў для такога роду слоўнік. Каб было ясна, што вы проста захоўваць так ці не, ёсць слова, якое заканчваецца тут. 

Цяпер тое, што маецца на ўвазе? Калі ў вас ёсць 150 тысяч слоў у слоўніку, што вы спрабуеце захаваць у памяці выкарыстоўваючы нешта накшталт звязанага спісу, Вы будзеце мець 150000 вузлоў у звязаным спісе. І, знайшоўшы адно з гэтых слоў у алфавітным парадку можа прыняць O (п). Лінейнае час. Але ў выпадку тут выглядзе дрэва, што час працы знайсці словы? Аказваецца, прыгажосць тут з'яўляецца тое, што нават калі ў вас ужо 149999 слоў у гэтым слоўніку, як гэта рэалізавана з гэтай структурай дадзеных, Колькі часу трэба для таго, каб знайсці або ўставіць яшчэ адзін чалавек у тым, як Аліса, Аліса? Ну, гэта толькі 5, можа быць 6 крокаў для задняга характар. Таму што presense іншых імёнаў у структуры не перашкаджаць ўстаўкі Аліса. Акрамя таго, знаходжанне Аліса адразу ўзнікаюць 150000 слоў у гэтым слоўніку не стаяць на шляху знаходжання Аліса наогул, таму што Эліс. . . . . тут, таму што я знайшоў лагічнае значэнне. А калі няма лагічнае праўда, то Аліса не ў гэтай структуры дадзеных слоў. Іншымі словамі, час працы такіх рэчаў і ўстаўкі рэчаў у гэтай новай Структура дадзеных Trie з'яўляецца O з - гэта не п. Таму што presense з 150.000 чалавек ніяк не ўплывае на Алісу, здаецца. Такім чынам, давайце называць гэта да, дзе да максімальнай даўжыні словы на англійскай мове якія, як правіла, не больш чым 20-то сімвалы. Такім чынам, да-пастаянная. Такім чынам, Святы Грааль, мы, здаецца, знайшлі зараз з'яўляецца тое, што ў выглядзе дрэва, пастаянная часу для уставак, для пошуку, для выдалення. Паколькі колькасць рэчаў ужо ў структуры, якія не з'яўляюцца нават фізічна там. Зноў жа, яны толькі выгляд адзначыцца, так ці не, не ўплывае на яго будучы час працы. 

Але там павінен быць ўлову, у адваротным выпадку мы б не патрацілі так шмат часу на ўсіх гэтых іншых структур дадзеных, проста каб, нарэшце, дабрацца да сакрэтнай што дзіву даешся. Так што кошт мы плацім для дасягнення гэтага велічы тут? Прасторы. Гэтая рэч мае масавы характар. І прычына таго, што аўтар не ўяўлялі яго тут, заўважым, што ўсе гэтыя рэчы, якія выглядаюць як масівы, Ён не зрабіў астатнюю частку дрэва, астатняя частка сінтаксічнага дрэва, таму што яны проста не маюць дачынення да гісторыі. Але ўсе гэтыя вузлы з'яўляюцца супер шырокі, і кожны вузел у дрэве займае 26 ці на самай справе, можа быць 27 сімвалаў, таму што ў гэтым выпадку я быў у тым ліку месца для апостраф так што мы маглі б апострафам слова. У гэтым выпадку, гэтыя шырокія масівы. Таму, нават калі яны не picutured, гэта займае велізарную колькасць аператыўнай памяці. Які можа быць штраф, especilly ў сучасным абсталяванні, але гэта кампраміс. Мы атрымліваем менш часу марнаваць больш прасторы. Дык дзе ж гэта ўсё адбываецца? Ну, давайце - давайце паглядзім тут. Давайце зробім пераход да гэтага хлопца тут. 

Верце ці не, як жа весела, як C была на працягу некаторага часу, Мы набліжаемся да таго часу ў семестры, дзе гэты час да пераходу на больш сучасныя рэчы. Рэчы на ​​больш высокім узроўні. І хоць на працягу наступных некалькіх тыдняў мы ўсё яшчэ працягваем апускацца ў свет паказальнікі і кіраванне памяццю каб атрымаць гэта камфорт, з якім мы можам развіваць, У канцы гульні, у канчатковым рахунку ўвесці, па іроніі лёсу, не ў гэты мову. Мы правядзем, як і 10 хвілін казаў пра HTML. Усё гэта HTML з'яўляецца мовай разметкі, і тое, што мова разметкі Менавіта гэтыя серыі адкрытых і закрытых дужкі дужкі, якія кажуць, "зрабіць гэты смелы" 'Зрабіць гэта курсівам "," зрабіць гэта па цэнтру. " Гэта яшчэ не ўсё, што інтэлектуальна цікавая, але гэта супер карысна. І гэта, вядома, ўсюдыісны ў гэтыя дні. Але тое, што магутныя аб свеце HTML і вэб-праграмаванне ў цэлым, будуе дынамічныя рэчы, напісання кода на мове PHP або як Python або Ruby, або Java або C #. Сапраўды, незалежна ад вашага мовы выбар, і генерыруючых HTML дынамічна. Стварэнне так званых CSS дынамічна. Каскадныя табліцы стыляў, якія таксама аб эстэтыцы. І таму нават сёння, калі я іду на сайт як некаторыя знаёмыя Google.com, і я іду, каб паглядзець, распрацоўшчык, выгляд крыніцы, які, можа быць, вы зрабілі раней, але збіраюся прагледзець зыходны код, гэты матэрыял, верагодна, выглядае даволі загадкава. Але гэта зыходны код, які рэалізуе Google.com. На пярэднім канцы. А на самай справе ўсё гэта пухнатыя рэчы эстэтыкі. Гэта CSS тут. Калі я буду пракруткі ўніз, мы атрымаем некаторыя каляровыя рэчы. Гэта HTML. Код Google выглядае як беспарадак, але калі я на самай справе адкрывае іншае акно, мы можам бачыць некаторыя структуры да гэтага. Калі б я адкрыць гэта, заўважце, тут, гэта крыху больш чытэльным. Мы збіраемся, каб убачыць у хуткім часе гэты тэг, [слова] тэг, HTML, галавы, цела, DIV, сцэнар, тэкст вобласці, службы па цэнтры, гл. І гэта таксама накшталт загадкавага выгляду на першы погляд, але ўсё гэта бязладдзе варта вызначаным узорам, і паўтараюцца ўзоры, так што як толькі мы атрымаем асновамі, вы зможаце напісаць такі код , А затым маніпуляваць код, як гэта, выкарыстоўваючы яшчэ адну мову, званы JavaScript. І JavaScript з'яўляецца мовай, які працуе ўсярэдзіне браўзэра Сёння, якую мы выкарыстоўваем на курсах Гарварда, для прылады курс куплі, якія выкарыстоўваюць карты Google , Каб даць вам цэлую кучу дынамізм, Facebook дае вам паказаць імгненныя абнаўлення статусу, Twitter выкарыстоўвае гэта, каб паказаць вам, нататкі ў сацыяльных сетках імгненна. Усё гэта мы пачнем апускацца цалі Але каб патрапіць туды, мы павінны зразумець сёе-тое пра Інтэрнэт. Гэты кліп тут знаходзіцца ўсяго ў хвіліне доўга, і выкажам здагадку, на дадзены момант гэта, па сутнасці, як працуе Інтэрнэт, як цвялілкі для таго, што вось-вось прыйдзе. Я даю вам "Воіны Сеткі". 

[♫ Павольная музыка хор ♫] [Мужчына апавядальніка] Ён прыйшоў з паведамленнем. З пратаколам усё сваё. [♫ хуткая электронная музыка ♫] Ён прыйшоў у свет халаднавата брандмаўэра, маршрутызатары абыякава, і небяспек значна горш, чым смерць. Ён хуткі. Ён моцны. Ён TCP / IP, і ў яго ёсць свой адрас. Ваяры ў Сеткі. [Малая] На наступным тыдні, то. Інтэрнэт. Вэб-праграмаванне. Гэта CS50. [CS50.TV]