[Powered by Google Translate] [Частка 7] [менш камфортна]
[Nate Хардисон] [Harvard University]
[Гэта CS50.] [CS50.TV]
>> Сардэчна запрашаем у профіль 7.
Дзякуючы ўраган Sandy,
замест таго нармальнага сячэння на гэтым тыдні,
Мы робім гэта прахадной, праз профіль пытанняў.
Я збіраюся быць наступныя Разам з праблемай Set 6 Спецыфікацыя,
і перажывае ўсе пытанні ў
Раздзел падзелу Пытанні.
Калі ёсць якія-небудзь пытанні,
калі ласка, напішыце іх на CS50 абмеркаваць.
>> Добра. Давайце пачнем.
Прама цяпер я гляджу на стр. 3 Спецыфікацыя пастаўленай задачы.
Мы ідзем да першага пачаць размову аб бінарных дрэў
З тых ёсць шмат, якія маюць дачыненне да праблемы набору на гэтым тыдні -
Кадаванне Хафман дрэва.
Адзін з самых першых структур дадзеных мы казалі аб на CS50 быў масіва.
Памятаеце, што масіў ўяўляе сабой паслядоўнасць элементаў -
Усё ж тыпу - захоўваюцца побач адзін з адным у памяці.
Калі ў мяне ёсць масіў цэлых лікаў, што я магу зрабіць з дапамогай гэтай скрынкі-ліку-цэлыя стыль -
Скажам, у мяне ёсць 5 у першым полі, у мяне 7 у другой,
то ў мяне ёсць 8, 10, і 20 у канчатковым поле.
Памятаеце, што два сапраўды добрых рэчаў аб гэтым масіве
у тым, што ў нас ёсць гэтая пастаянная часу доступ да любой канкрэтны элемент
ў масіве, калі мы ведаем яго індэкс.
Напрыклад, калі я хачу, каб захапіць трэці элемент масіва -
з індэксам 2, выкарыстоўваючы нашу з нуля сістэмы -
Я літаральна толькі што трэба зрабіць просты матэматычны разлік,
скакаць на гэтую пасаду ў масіве,
выцягнеце 8, які захоўваецца там,
і я добра ісці.
>> Адзін з дрэнных рэчаў пра гэта масіва - пра якія мы казалі
Калі мы абмяркоўвалі звязаныя спісы -
з'яўляецца тое, што калі я хачу, каб ўставіць элемент у гэтым масіве,
Я збіраюся зрабіць некаторы перасоўванне вакол.
Напрыклад, гэты масіў прама тут
з'яўляецца ў пэўным парадку - адсартаваныя ў парадку ўзрастання -
5, потым 7, потым 8, потым 10, а затым 20 -
але калі я хачу, каб ўставіць нумар 9 у гэтым масіве,
Я хачу, каб перанесці некаторыя элементы для таго, каб вызваліць месца.
Мы можам зрабіць гэта тут.
Я збіраюся павінны рухацца 5, 7, а затым 8;
стварыць зазор, дзе я магу паставіць 9,
, А затым 10 і 20 можа пайсці ў праве 9.
Гэта свайго роду болю, таму што ў горшым выпадку -
калі мы таго, каб ўставіць альбо ў пачатку, альбо ў канцы
масіва, у залежнасці ад таго, як мы зрушэння -
Мы маглі б у канчатковым выніку таго, каб зрушыць ўсе элементы
што мы ў цяперашні час захоўванне ў масіве.
>> Такім чынам, што быў спосаб абыйсці гэта?
Спосаб абыйсці гэта быў пайсці ў наш звязанага спісу метад, дзе -
замест захоўвання элементаў 5, 7, 8, 10 і 20 усё побач адзін з адным у памяці -
Замест таго, што мы рабілі, было захоўваць іх выгляду, дзе б мы хацелі, каб захаваць іх
У гэтых звязаны спіс вузлоў, якія я малюю тут, накшталт адмысловых.
І тады мы злучылі іх разам, выкарыстоўваючы гэтыя наступныя паказальнікі.
Я магу ёсць паказальнік ад 5 да 7,
Паказальнік ад 7 да 8,
Паказальнік ад 8 да 10,
І, нарэшце, паказальнік ад 10 да 20,
, А затым нулявым паказальнікам на 20 пра тое, што там нічога не засталося.
Кампраміс, што мы маем тут
з'яўляецца тое, што цяпер, калі мы хочам, каб ўставіць нумар 9 у нашай адсартаваны спіс,
усё, што нам трэба зрабіць, гэта стварыць новы вузел з 9,
падлучыць яго да кропкі ў патрэбнае месца,
, А затым паўторна провада ад 8 да кропкі да 9.
Гэта даволі хутка, мяркуючы, што мы дакладна ведаем, дзе мы хочам, каб ўставіць 9.
Але кампраміс у абмен на гэта, што мы цяпер страцілі пастаяннае час доступу
любы канкрэтны элемент у нашай структуры дадзеных.
Напрыклад, калі я хачу знайсці чацвёрты элемент у гэтай звязанага спісу,
Я збіраюся мець, каб пачаць у самым пачатку спісу
і працуе свой шлях праз рахункі вузла-на-вузле, пакуль не знайду чацвёрты.
>> Для таго каб атрымаць больш шырокі доступ прадукцыйнасць, чым звязаны спіс -
але і захаваць некаторыя з пераваг, якія ў нас былі
Ва ўмовах увядзення часу ад звязанага спісу -
бінарнае дрэва будзе неабходна выкарыстоўваць трохі больш памяці.
У прыватнасці, замест таго, каб проста мець адзін паказальнік ў бінарным дрэве вузлоў -
як звязаны спіс вузлоў робіць -
Мы збіраемся дадаць другі паказальнік на двайковы вузла дрэва.
Замест таго, каб проста мець адзін паказальнік на наступны элемент,
мы будзем мець паказальнік на левы дзіцяці і права дзіцяці.
>> Давайце намалюем карцінку, каб паглядзець, што на самой справе выглядае.
Зноў жа, я збіраюся выкарыстоўваць гэтыя скрынкі і стрэлы.
Бінарны вузел дрэва будзе пачаць з простай скрынцы.
Гэта будзе мець месца для значэння,
а затым ён таксама будзе мець прастору для левага дзіцяці і права дзіцяці.
Я буду называць іх тут.
Мы збіраемся ў левая дзіцяці, і тады мы будзем мець права дзіцяці.
Ёсць шмат розных спосабаў зрабіць гэта.
Часам для прасторы і выгоды,
Я на самой справе зрабіць гэта, як я раблю тут на дне
дзе я збіраюся мець значэнне ў верхняй частцы,
, А затым правую дзіцяці на правай ніжняй,
і левай дзіцяці на левай ніжняй.
Вяртаючыся да гэтай вяршыні дыяграмы,
у нас ёсць значэнне на самым версе,
Затым у нас ёсць левы паказальнік дзіцяці, і тады мы маем права дзіцяці паказальнік.
>> У спецыфікацыі пастаўленай задачы,
мы гаворым аб распрацоўцы вузла, які мае значэнне 7,
, А затым левую дзіцяці паказальнік, які з'яўляецца пустым, і правы дзіцяці-паказальнік, які з'яўляецца нулявым.
Мы можам альбо напісаць капіталу NULL ў прасторы для
як левай дзіцяці і права дзіцяці, ці мы можам зрабіць гэта касая рыса
у кожным з скрынкі, каб паказаць, што гэта нулявы.
Я збіраюся зрабіць гэта проста, таму што гэта прасцей.
Тое, што вы бачыце тут два спосабу пабудовы дыяграм вельмі просты вузел двайковага дрэва
дзе ў нас ёсць значэнне 7 і нулявых паказальнікаў дзіцяці.
>> Другая частка нашай спецыфікацыі перамовы аб тым, як са звязанымі спісамі -
Памятаеце, мы толькі павінны былі трымацца за першы элемент у спісе
ўспомніць ўвесь спіс -
і аналагічна, з бінарным дрэвам, мы толькі павінны трымаць на аднаго паказальніка на дрэве
У мэтах захавання кантролю над усёй структурай дадзеных.
Гэты адмысловы элемент дрэва называецца каранёвым вузлом дрэва.
Напрыклад, калі гэты вузел - гэта вузел, які змяшчае значэнне 7
з нулявой левай і правай дзіцяці паказальнікі -
былі адзінай каштоўнасцю ў нашым дрэве,
то гэта будзе нашым каранёвым вузлом.
Гэта самы пачатак нашага дрэва.
Мы можам убачыць гэта трохі ясней, як толькі мы пачнем дадаваць дадатковыя вузлы да нашага дрэве.
Дазвольце мне падцягнуць новую старонку.
>> Цяпер мы будзем маляваць дрэва, якое мае 7 на пні,
і 3 ўнутраным боку левага дзіцяці, і 9 ў правым дзіцяці.
Зноў жа, гэта даволі проста.
У нас ёсць 7, намаляваць вузел 3, вузел 9,
і я збіраюся ўсталяваць левы паказальнік дзіця ад 7 да паказваюць на вузел, які змяшчае 3,
і права дзіцяці паказальнік вузел, які змяшчае ад 7 да вузел, які змяшчае 9.
Цяпер, так як 3 і 9 не маюць дзяцей,
мы збіраемся ўсталяваць ўсе іх паказальнікі дзіцяці, з'яўляюцца несапраўднымі.
Тут корань нашага дрэва адпавядае вузел, які змяшчае нумар 7.
Вы можаце бачыць, што калі ўсе мы маем паказальнік на каранёвай вузел,
мы можам прайсці праз наша дрэва і доступ як даччыныя вузлы -
як 3 і 9.
Не трэба захаваць паказальнікі на кожным вузле дрэва.
Добра. Цяпер мы збіраемся дадаць яшчэ адзін вузел да гэтай схеме.
Мы збіраемся дадаць вузел, які змяшчае 6,
і мы збіраемся дадаць яго ў якасці правага нашчадка вузла, які змяшчае 3.
Каб зрабіць гэта, я збіраюся сцерці гэтую нулявога паказальніка ў 3-вузле
і падлучыць яго да паказвала на вузел, які змяшчае 6. Добра.
>> На дадзены момант, давайце пяройдзем трохі тэрміналогіі.
Для пачатку, прычына таго, што гэта называецца бінарнае дрэва, у прыватнасці,
з'яўляецца тое, што яна мае два паказальніка дзіцяці.
Ёсць і іншыя віды дрэў, якія маюць больш паказальнікаў дзіцяці.
У прыватнасці, вы зрабілі "паспрабаваць" ў праблеме Set 5.
Вы заўважыце, што ў гэтай спробе, у вас было 27 розных паказальнікаў на розныя дзеці -
па адным для кожнай з 26 літар англійскага алфавіту,
, А затым 27-й па апострафа -
так, што падобны на тып дрэва.
Але тут, так як гэта двайковы, у нас ёсць толькі два паказальніка дзіцяці.
>> У дадатак да гэтай каранёвай вузел, што мы казалі пра тое,
Мы таксама кідалі вакол гэтага тэрміну "дзіця".
Што гэта значыць для аднаго вузла, каб быць нашчадкам іншага вузла?
Гэта літаральна азначае, што дзіця вузел з'яўляецца нашчадкам іншага вузла
калі іншы вузел мае адну з яго даччыных паказальнікі ўстаноўлены, каб паказаць на гэтым вузле.
Каб паставіць гэта ў больш канкрэтных тэрмінах,
калі 3, паказаў на аднаго дзіцяці паказальнікі 7, затым 3 з'яўляецца даччыным 7.
Калі б мы маглі зразумець, што дзеці да 7 гадоў -
Ну, мы бачым, што 7 мае паказальнік на 3 і паказальнік на 9,
таму 9 і 3 дзяцей 7.
Дзевяць дзяцей няма, таму што яго паказальнікі дзіцяці з'яўляюцца несапраўднымі,
і 3 мае толькі аднаго дзіцяці, 6.
Шэсць таксама не мае дзяцей, таму што абодва яго паказальнікі з'яўляюцца несапраўднымі, якую мы будзем маляваць прама цяпер.
>> Акрамя таго, мы таксама гаворым пра бацькоў канкрэтнага вузла,
і гэта, як і варта было чакаць, зваротны гэтага дзіцяці апісання.
Кожны вузел мае толькі аднаго з бацькоў - замест двух, як вы маглі б чакаць з людзьмі.
Напрыклад, бацька 3, 7.
Бацька 9 таксама 7 і бацькоў 6, 3. Не так шмат да яго.
У нас таксама ёсць умовы, каб казаць пра бабуль і дзядуляў і ўнукаў,
і наогул мы гаворым пра продкаў
і нашчадкаў канкрэтнага вузла.
Продкам вузла - ці продкаў, хутчэй, вузел -
Усе вузлоў, якія ляжаць на шляху ад кораня да гэтага вузла.
Напрыклад, калі я гляджу на вузле 6,
Затым продкі збіраюцца быць як 3 і 7.
Продкі 9, напрыклад, ёсць - калі я гляджу на вузле 9 -
Затым продка з 9 знаходзіцца ўсяго ў 7.
І нашчадкі ў дакладнасці наадварот.
Калі я хачу паглядзець на ўсе нашчадкі 7,
Затым я павінен глядзець на ўсе вузлы пад ім.
Такім чынам, у мяне ёсць 3, 9 і 6, усё як нашчадкі 7.
>> Апошні тэрмін, які мы будзем казаць пра гэта паняцце быцця роднага брата.
Браты і сёстры - накшталт наступных разам на гэтых сямейных умовах -
вузлы, якія знаходзяцца на тым жа ўзроўні ў дрэве.
Так, 3 і 9 братоў і сясцёр, таму што яны на тым жа ўзроўні ў дрэве.
Яны абодва маюць аднаго з бацькоў, 7.
6 не мае братоў і сясцёр, таму што 9 не мае дзяцей.
І 7 не мае братоў і сясцёр, таму што гэта корань нашага дрэва,
і ёсьць толькі калі-небудзь 1 корань.
На 7 братоў і сясцёр, каб там павінны былі б быць вышэй 7 вузлоў.
Там павінна было б быць бацькам 7, у якім выпадку 7 больш не будзе коранем дрэва.
Затым, што новыя бацькі з 7 таксама будзе мець дзіцяці,
і што дзіця б тады брат 7.
>> Добра. Рухаемся далей.
Калі мы пачалі наш размова аб бінарных дрэў,
мы казалі пра тое, як мы збіраемся выкарыстаць іх для
атрымаць перавагу над абодвух масіваў і звязаных спісаў.
І тое, як мы збіраемся зрабіць гэта з гэтай замовай уласнасці.
Мы кажам, што бінарнае дрэва упарадкаваны, у адпаведнасці са спецыфікацыяй,
калі для кожнага вузла ў дрэве, усе яго нашчадкі злева -
левы дзіцяці, і ўсіх нашчадкаў левай дзіцяці -
маюць меншыя значэння, а ўсе вузлы справа -
правы дзіцяці і ўсіх нашчадкаў правы дзіцяці -
ёсць вузлы больш, чым значэнне бягучага вузла, што мы глядзім.
Проста для прастаты мы будзем лічыць, што няма ніякіх дублюючых вузлоў у нашым дрэве.
Напрыклад, у гэтым дрэве мы не збіраемся мець справу з выпадкам
дзе ў нас ёсць значэнне 7 у корані
і ў нас таксама ёсць значэнне 7 у іншым месцы ў дрэва.
У гэтым выпадку, вы заўважыце, што гэта дрэва сапраўды замоўлены.
У нас ёсць значэнне 7 на пні.
Усе злева ад 7 -
калі я адмяню ўсе гэтыя маленькія знакі тут -
усё, што злева ад 7 - 3 і 6 -
гэтыя значэнні знаходзяцца менш чым у 7, і ўсё, што правей - што менавіта гэта 9 -
больш за 7.
>> Гэта не толькі спарадкаванае дрэва, якія змяшчаюць гэтыя значэнні,
Але давайце намаляваць некалькі з іх.
Існуе на самой справе цэлая куча спосабаў, якімі мы можам гэта зрабіць.
Я збіраюся выкарыстоўваць скарочаны толькі, каб трымаць рэчы простымі, дзе -
, А не расцягваючы цэлым скрынкі-і-стрэлкі -
Я проста хачу звярнуць нумароў і дадаць стрэлкі, якія злучаюць іх.
Для пачатку, мы будзем проста пісаць свае арыгінальныя дрэва яшчэ раз, дзе ў нас было 7, а затым 3,
, А затым 3 паказана назад у праве на 6,
і 7 мелі права дзіцяці, які быў 9.
Добра. Якія яшчэ адзін спосаб, што мы маглі б напісаць гэта дрэва?
Замест таго, каб быць 3 левы дзіця 7,
Мы таксама маглі б быць 6 левым дзіця 7,
, А затым 3 будзе левы дзіцяці 6.
Гэта будзе выглядаць наступным чынам дрэва прама тут, дзе ў мяне 7,
потым 6, потым 3, і 9 справа.
Мы таксама не павінны мець 7, як наш каранёвай вузел.
Мы маглі б таксама мець 6, як наш каранёвай вузел.
Што б выглядаць?
Калі мы збіраемся захаваць гэтую загадаў уласнасці,
усё, што лявей з 6 павінен быць менш, чым яна.
Там толькі адна магчымасць, і вось 3.
Але тады, як права дзіцяці з 6, у нас ёсць дзве магчымасці.
Па-першае, мы маглі б 7, а затым 9,
ці мы можам зрабіць гэта - як я збіраюся зрабіць тут -
дзе ў нас ёсць 9, правы дзіцяці 6,
, А затым 7 у якасці левага дзіцем з 9.
>> Цяпер, 7 і 6 не з'яўляюцца адзіна магчымымі значэннямі кораня.
Мы маглі б таксама мець 3 быць у корані.
Што адбудзецца, калі 3 з'яўляецца ў корані?
Тут усё становіцца трохі цікавей.
Тры не мае ніякага значэння, якія менш, чым ён,
так што ўся левая бок дрэва проста будзе нулявы.
Там не будзе нічога няма.
Справа, мы маглі б пералічыць рэчы ў парадку ўзрастання.
Мы маглі б 3, то 6, то 7, то 9.
Ці, мы маглі б зрабіць 3, то 6, то 9, то 7.
Ці, мы маглі б зрабіць 3, затым 7, потым 6, потым 9.
Ці, 3, 7 - на самай справе няма, мы не можам зрабіць 7 больш.
Гэта наша адно там.
Мы можам зрабіць 9, а затым з 9 мы можам зрабіць 6, а затым 7.
Або, што мы можам зрабіць 3, то 9, то 7, а затым 6.
>> Адна рэч, каб звярнуць вашу ўвагу на тут
што гэтыя дрэвы трохі дзіўны выгляд.
У прыватнасці, калі мы глядзім на 4 дрэва на правай баку -
Я іх кола, тут -
гэтыя дрэвы выглядаюць амаль гэтак жа, як звязаны спіс.
Кожны вузел мае толькі адно дзіця,
і таму мы не павінны ўсё гэта дрэвападобная структура, якую мы бачым, напрыклад,
У гэтым самотнае дрэва тут на ніжняй левай.
Гэтыя дрэвы на самай справе называецца звод, бінарныя дрэвы,
і мы пагаворым аб гэтым падрабязней у будучыні -
Асабліва калі вы ідзяце на прыняцце іншых курсаў па інфарматыцы.
Гэтыя дрэвы з'яўляюцца звод.
Яны не вельмі карысна, таму што, сапраўды, гэтая структура паддаецца
для пошуку разы падобны на звязаны спіс.
Мы не атрымліваем, каб скарыстацца дадатковай памяці - гэта дадатковы паказальнік -
таму што нашы структуры дрэнных такім чынам.
Замест таго, каб ісці далей і зрабіць з бінарных дрэў, якія маюць 9 на пні,
якая з'яўляецца апошні выпадак, што мы павінны,
мы замест гэтага, на дадзены момант, пагаворым крыху аб гэтым іншым тэрмінам
, Якія мы выкарыстоўваем, калі гаворым аб дрэвах, якія называюць вышынёй.
>> Вышыня дрэва гэта адлегласць ад кораня да самых аддаленых вузлоў,
ці, дакладней, колькасць скачкоў, што вы павінны зрабіць для таго, каб
пачынаецца з кораня і затым у канчатковым выніку на самым аддаленым вузел у дрэве.
Калі мы паглядзім на некаторыя з гэтых дрэў, якія мы намалявалі прама тут,
мы бачым, што калі мы возьмем гэта дрэва ў левым верхнім куце, і мы пачынаем на 3,
Затым мы павінны зрабіць 1-хопа, каб дабрацца да 6, другога скачка, каб дабрацца да 7,
і трэці хоп, каб дабрацца да 9.
Такім чынам, вышыня гэтага дрэва 3.
Мы можам зрабіць тое ж самае практыкаванне для іншых дрэў, выкладзеныя з гэтай зялёнай,
і мы бачым, што вышыня ўсіх гэтых дрэў таксама сапраўды 3.
Гэта частка таго, што робіць іх звод -
што іх вышыня складае ўсяго адзін менш, чым колькасць вузлоў па ўсім дрэве.
Калі мы паглядзім на гэтай другой дрэва, што гэта асяроддзе з чырвоным, з другога боку,
мы бачым, што найбольш аддаленых вузлоў лісця 6 і 9 -
лісце аказваюцца тыя вузлы, якія не маюць дзяцей.
Такім чынам, для таго, каб атрымаць ад каранёвага вузла альбо 6 або 9,
мы павінны зрабіць адно-хопа, каб дабрацца да 7, а затым другім скачку, каб дабрацца да 9,
і аналагічна, толькі другога скачка з 7, каб дабрацца да 6.
Такім чынам, вышыня гэтага дрэва тут толькі 2.
Вы можаце вярнуцца назад і зрабіць гэта для ўсіх іншых дрэў, якія мы раней абмяркоўвалі
пачынаючы з 7 і 6,
і вы ўбачыце, што вышыня ўсіх гэтых дрэў таксама 2.
>> Таму мы гаварылі пра загадаў бінарныя дрэвы
і чаму яны стромкія, таму што вы можаце шукаць праз іх у
вельмі падобна на пошукі больш спарадкаваны масіў.
Тут мы гаворым пра тое, што паляпшэнне час пошуку
над просты звязаны спіс.
З звязаны спіс - калі вы хочаце знайсці канкрэтны элемент -
Вы ў лепшым выпадку збіраецца зрабіць нейкі лінейны пошук
дзе вы пачынаеце ў пачатку спісу і хмеля адзін-на-адзін -
аднаго вузла на адзін вузел -
ўвесь спіс, пакуль не знойдзеце тое, што вы шукаеце.
Прымаючы пад увагу, калі ў вас ёсць бінарнае дрэва, якое захоўваецца ў гэтым добрым фармаце,
Вы можаце фактычна атрымаць больш бінарны пошук працягваецца
дзе вы падзяляй і ўладар
і пошуку пры дапамозе адпаведных паловы дрэў на кожным кроку.
Давайце паглядзім, як гэта працуе.
>> Калі ў нас ёсць - зноў жа, вяртаючыся да нашай першапачатковай дрэва -
мы пачынаем у 7, у нас ёсць 3 злева, 9 справа,
і пад 3 маем 6.
Калі мы хочам, каб знайсці нумар 6 у гэтым дрэве, мы б пачалі ў корані.
Мы б параўнаць значэнне мы шукаем, скажам, 6,
са значэннем, якія захоўваюцца ў вузле, які мы ў цяперашні час глядзім, 7,
выявіце, што 6 з'яўляецца сапраўды менш, чым 7, так што мы б рухацца налева.
Калі значэнне 6 было больш, чым 7, мы б замест перамяшчаецца направа.
Паколькі мы ведаем, што - дзякуючы структуры нашай загадаў бінарным дрэве -
усе значэння менш 7 будуць захоўвацца злева ад 7,
няма неабходнасці нават турбавацца, гледзячы праз правы бок дрэва.
Як толькі мы пераходзім да левай, і мы зараз на вузел, які змяшчае 3,
мы можам зрабіць тое ж параўнанне яшчэ раз, дзе мы параўноўваем 3 і 6.
І мы бачым, што ў той час як 6 - каштоўнасць, якую мы шукаем, - гэта больш, чым 3,
мы можам перайсці да правай баку вузел, які змяшчае 3.
Там няма левай баку тут, так што мы маглі б праігнараваў.
Але мы ведаем толькі, што, паколькі мы глядзім на само дрэва,
і мы бачым, што дрэва не мае дзяцей.
>> Гэта таксама даволі лёгка знайсці 6 у гэтым дрэве, калі мы робім гэта самі, як людзі,
Але давайце сачыць за гэтым працэсам механічна, як кампутар будзе рабіць
каб зразумець алгарытм.
На дадзены момант, мы зараз глядзім на вузел, які змяшчае 6,
і мы шукаем значэнне 6,
так, сапраўды, мы знайшлі патрэбны вузел.
Мы выявілі, што значэнне 6 у нашым дрэве, і мы можам спыніць нашы пошукі.
На дадзены момант, у залежнасці ад таго, што адбываецца,
мы можам сказаць, так, мы знайшлі значэння 6, яна існуе ў нашым дрэве.
Ці, калі мы плануем ўставіць вузел ці зрабіць нешта, што мы можам зрабіць, што ў гэтай кропцы.
>> Давайце зробім яшчэ пару пошуку, каб паглядзець, як гэта працуе.
Давайце паглядзім, што адбудзецца, калі мы павінны былі паспрабаваць і паглядзець значэнне 10.
Калі б мы шукаць значэнне 10, мы хацелі б пачаць з кораня.
Мы бачым, што 10 больш, чым 7, таму мы будзем рухацца направа.
Мы хацелі патрапіць на 9 і параўнайце 9 да 10 і бачым, што 9 з'яўляецца сапраўды менш, чым 10.
Такім чынам, яшчэ раз, мы будзем спрабаваць рухацца направа.
Але на дадзены момант, мы б заўважылі, што мы знаходзімся на нулявы вузел.
Там нічога няма. Там няма нічога, дзе 10 павінна быць.
Гэта тое, дзе мы можам паведаміць няўдача - што там на самой справе няма 10 у дрэва.
І, нарэшце, давайце пройдзем выпадку, калі мы спрабуем знайсці 1 у дрэва.
Гэта падобна на тое, што адбываецца, калі мы паглядзім на 10, толькі замест таго, каб ісці направа,
Мы збіраемся пайсці налева.
Мы пачынаем у 7 і бачым, што 1 менш 7, таму мы рухаемся налева.
Мы дабіраемся да 3 і бачым, што 1 менш, чым 3, таму зноў мы спрабуем рухацца налева.
На дадзены момант мы маем нулявы вузел, так што зноў мы можам паведаміць пра няўдачу.
>> Калі вы хочаце даведацца больш аб бінарных дрэў,
Ёсць цэлая куча весялосці мала праблем, якія вы можаце зрабіць з імі.
Я прапаную практыкаваць малюнак з гэтых дыяграмах адзін-на-адзін
і наступныя праз усе розныя крокі,
таму што гэта прыйдзе ў супер-зручная
Не толькі тады, калі вы робіце праблема Huffman кадавання набору
але і ў будучых курсаў -
проста навучыцца маляваць гэтыя структуры дадзеных і думаю, праз праблемы
з ручкай і паперай, ці, у дадзеным выпадку, IPad і стылусам.
>> На дадзены момант, аднак, мы збіраемся рухацца далей, каб зрабіць некаторыя практыкі кадавання
а на самай справе гуляць з гэтымі бінарныя дрэвы і паглядзець.
Я збіраюся вярнуцца да майго кампутара.
Для гэтай частцы разрэзу, замест выкарыстання CS50 або CS50 Run прасторы,
Я збіраюся выкарыстоўваць прыбор.
>> Пасля разам з спецыфікацыяй пастаўленай задачы,
Я бачу, што я павінен адкрыць прыбор,
іду ў тэчку Dropbox, стварыць тэчку з імем Раздзел 7,
, А затым стварыць файл з імем binary_tree.c.
Тут мы ідзем. У мяне ёсць прыбор ўжо адкрыты.
Я збіраюся цягнуць да тэрмінала.
Я збіраюся пайсці ў тэчку Dropbox, стварыце каталог называецца section7,
і ўбачыць яго зусім пустым.
Цяпер я збіраюся адкрыць binary_tree.c.
Добра. Тут мы ідзем - пусты файл.
>> Давайце вернемся да спецыфікацыі.
Спецыфікацыя просіць, каб стварыць новае вызначэнне тыпу
для двайковага дрэва вузлоў якія змяшчаюць Int значэння -
так жа як і каштоўнасці, якія мы звярнулі ў нашай дыяграм раней.
Мы збіраемся выкарыстаць гэты шаблонны ЬурейеЕ, што мы зрабілі тут
што вы павінны даведацца з задач 5 -
калі вы зрабілі хэш-табліцы шляхам заваёвы правапісу праграмы.
Вы павінны таксама прызнаць, што ў раздзеле мінулым тыдні
дзе мы казалі аб звязаных спісаў.
У нас гэта ЬурейеЕ з структуры вузла,
і мы далі гэтай структуры вузла гэта назва структуры вузла загадзя
так што мы можам спасылацца на яго, так як мы хочам мець паказальнікі структуры вузла
як частка нашай структуры, але мы тады атачылі гэтую -
ці, хутчэй, заключаны гэтым - у ЬурейеЕ
так што, у канцы кода, мы можам звярнуцца да гэтай структуры, як толькі вузел, а структура вузла.
>> Гэта будзе вельмі падобны на односвязный вызначэнне спісу, які мы бачылі на мінулым тыдні.
Каб зрабіць гэта, давайце пачнем з выпісваючы шаблону.
Мы ведаем, што мы павінны мець цэлае значэнне,
так што мы трапілі ў цэлалікавых значэнне, а затым замест таго, каб толькі адзін паказальнік на наступны элемент -
як мы зрабілі з односвязный спісаў -
Мы збіраемся мець левы і правы паказальнікі дзіцяці.
Гэта даволі простая таксама - структура вузла * левы дзіцяці;
і структура вузла * Права дзіцяці;. Cool.
Гэта выглядае як вельмі добры старт.
Давайце вернемся да спецыфікацыі.
>> Цяпер нам трэба абвясціць глабальную зменную * вузел каранёвага дрэва.
Мы збіраемся зрабіць гэта глабальны так жа, як мы зрабілі першы паказальнік у нашым спісе таксама звязана глабальным.
Гэта было так, што ў функцыях, якія мы пішам
мы не павінны трымаць праходзіць вакол гэтага кораня -
хоць мы ўбачым, што, калі вы хочаце напісаць гэтыя функцыі рэкурсіўна,
што можа быць лепш нават не перадаваць яго ў якасці глабальнай, у першую чаргу
і замест таго, ініцыялізаваць яго лакальна ў асноўнай функцыяй.
Але, мы зробім гэта ў глабальным маштабе для пачатку.
Зноў жа, мы дамо пару прастор, і я збіраюся абвясціць каранёвай вузел *.
Проста каб пераканацца, што я не пакідаю гэтай неинициализированные, я збіраюся ўсталяваць яго роўным нулю.
Зараз, у асноўнай функцыі - якія мы будзем пісаць вельмі хутка, прама тут -
Int асноўных (Int агдс, сопзЬ сЬаг * ARGV []) -
і я збіраюся пачаць дэклараванне мой ARGV масіва як константного проста так, што я ведаю,
што тыя аргументы аргументамі, якія я, верагодна, не хочуць змяніць.
Калі я хачу змяніць іх, я, верагодна, варта рабіць іх копіі.
Вы ўбачыце гэта шмат кода.
Гэта добра ў любым выпадку. Гэта выдатна, каб пакінуць усё як - апусціць сопзЬ, калі вы хочаце.
Як правіла, я паклаў яго ў проста так, што я нагадваю сабе,
што я, верагодна, не хочаце змяняць гэтыя аргументы.
>> Як заўсёды, я збіраюся ўключыць гэта вяртанне 0 лінію ў канцы асноўнага.
Тут я ініцыялізацыі майго каранёвага вузла.
Як яна каштуе зараз, у мяне ёсць паказальнік, які ўсталяваны ў нуль,
такім чынам, гэта паказвае на нічога.
Для таго каб сапраўды пачаць будаўніцтва вузла,
Я ў першую чаргу неабходна вылучыць памяць для яго.
Я збіраюся зрабіць гэта, зрабіўшы памяці кучы з дапамогай таНос.
Я збіраюся ўсталяваць корань, роўны вынік таНос,
і я збіраюся выкарыстоўваць SizeOf аператара для разліку памеру вузла.
Прычына, па якой я выкарыстоўваю SizeOf вузла, у адрозненне ад, скажам,
рабіць нешта накшталт гэтага - таНос (4 + 4 +4) або таНос 12 -
таму што я хачу, каб мой код, каб быць сумяшчальным наколькі гэта магчыма.
Я хачу быць у стане прыняць гэта. З файлам, скампіляваць яго на прыбор,
, А затым кампіляваць яго на маім 64-разрадны Mac -
або на зусім іншы архітэктуры -
і я хачу гэта ўсё будзе працаваць так жа.
>> Калі я раблю здагадкі адносна памеру зменных -
Памер Int або памер паказальніка -
Затым я таксама робіць здагадкі аб відах архітэктуры
, На якім мой код можа паспяхова скампіляваць пры запуску.
Заўсёды выкарыстоўвайце SizeOf, у адрозненне ад ручной сумавання структура палёў.
Іншая прычына ў тым, што там можа быць таксама абіўка, што кампілятар змяшчае ў структуру.
Нават проста сумаванне асобных палёў не тое, што вы звычайна хочуць рабіць,
так, выдаліце ​​гэтую радок.
Цяпер, каб сапраўды ініцыялізацыі гэтага каранёвага вузла,
Я хачу, каб падключыць значэння для кожнага з сваіх розных галінах.
Напрыклад, для значэння Я ведаю, я хачу, каб ініцыялізаваць да 7,
і цяпер я збіраюся ўсталяваць левы дзіця будзе нулявым
і права дзіцяці быць нулявым. Выдатна!
Мы зрабілі гэта частка спектру.
>> Спецыфікацыя ўніз ў ніжняй частцы старонкі 3 пытаецца мяне на стварэнне яшчэ трох вузлоў -
адна з якіх 3, адна з якіх 6, і адзін з 9 -
, А затым падлучыць іх так, што выглядае сапраўды гэтак жа, як наша дрэва схема
што гаворка ішла аб раней.
Давайце зробім гэта вельмі хутка тут.
Вы ўбачыце вельмі хутка, што я збіраюся пачаць пісаць кучу паўтаральнага кода.
Я збіраюся стварыць вузел *, і я збіраюся называць гэта тры.
Я збіраюся ўсталяваць яго роўным таНос (SizeOf (вузла)).
Я збіраюся ўсталяваць тры-> значэнне = 3.
Тры -> left_child = NULL; трох -> правай _child = NULL; таксама.
Гэта выглядае вельмі падобна на ініцыялізацыю корань, і гэта менавіта тое, што
Я збіраюся трэба зрабіць, калі я пачну ініцыялізацыі 6 і 9, а таксама.
Я зраблю гэта вельмі хутка тут - на самай справе, я збіраюся зрабіць невялікі капіявання і ўстаўкі,
і пераканацца, што я - усё ў парадку.
Зараз, я атрымаў яго скапіяваць, і я магу пайсці далей і ўсталяваць роўным 6.
Вы бачыце, што гэта займае некаторы час, і не супер-эфектыўным.
У зусім крыху, мы напішам функцыю, якая будзе рабіць гэта за нас.
Я хачу, каб замяніць гэтым з 9, замяніць, што з 6.
>> Цяпер у нас ёсць усе нашы вузлы створаны і ініцыялізаваць.
У нас ёсць наш корань роўным 7, або якія змяшчаюць значэнне 7,
наш вузел, які змяшчае 3, наш вузел, які змяшчае 6, і наш вузел, які змяшчае 9.
На дадзены момант, усё, што нам трэба зрабіць, гэта правады ўсё дагары.
Таму я ініцыялізуецца ўсе паказальнікі да нуля, гэта проста так, што я пераканацца, што
Я не ёсць нейкія неинициализированных паказальнікаў там выпадкова.
А таксама, паколькі, на дадзены момант, у мяне толькі ёсць на самой справе злучэння вузлоў адзін з адным -
з тымі, што яны на самой справе звязаны з - я не павінен ісці да канца і зрабіць
Пераканайцеся, што ўсе нулі знаходзяцца там у адпаведных месцах.
>> Пачынаючы з коранем, я ведаю, што левая дзіцяці кораня роўная 3.
Я ведаю, што правы дзіцяці кораня роўная 9.
Пасля гэтага, толькі іншы дзіця, што я пакінуў для турботы
гэта права дзіцяці 3, якая з'яўляецца 6.
На дадзены момант, усё гэта выглядае даволі добра.
Мы выдалім некаторыя з гэтых ліній.
Цяпер усё выглядае даволі добра.
Давайце вернемся да нашай спецыфікацыі і паглядзець, што мы павінны рабіць далей.
>> На дадзены момант, мы павінны напісаць функцыю, званую 'змяшчае'
з прататыпам "BOOL ўтрымоўвае (цэлалікавых значэнне).
І гэта змяшчае функцыю збіраецца вярнуць сапраўдны
калі дрэва на якое паказвае наша глабальная пераменная каранёвай
утрымоўвае значэнне перадаецца ў функцыю і хлусня ў адваротным выпадку.
Давайце пойдзем далей і што рабіць.
Гэта будзе так жа, як пошук, што мы зрабілі ўручную на IPad проста трохі назад.
Давайце маштаб ў трохі, і пракрутка ўверх.
Мы збіраемся паставіць гэтую функцыю прама над нашай асноўнай функцыяй
так што мы не павінны рабіць ніякіх прататыпаў.
Такім чынам, лагічны ўтрымоўвае (цэлалікавых значэнне).
Там мы ідзем. Там наш шаблонны дэкларацыі.
Проста каб пераканацца, што гэта будзе кампіляваць,
Я збіраюся ісці наперад і проста ўсталяваць яго роўным вярнуцца ілжывым.
Цяпер гэтая функцыя проста не будзе рабіць нічога, і заўсёды паведамляюць, што
значэнне, якое мы шукаем не ў дрэве.
>> У гэты момант, верагодна, гэта добрая ідэя -
так як мы напісалі цэлую кучу кода, і мы нават не спрабавалі тэставанне яшчэ -
каб пераканацца, што ўсе кампілюецца.
Ёсць некалькі рэчаў, якія мы павінны зрабіць, каб пераканацца, што гэта будзе на самой справе кампіляцыі.
Па-першае, убачыць, калі мы выкарыстоўваем любыя функцыі ў любой бібліятэкі, якія мы яшчэ не ўключаны.
Функцыі, якія мы выкарысталі да гэтага часу, таНос,
і мы таксама выкарысталі гэты тып - гэта нестандартны тып, званы "bool '-
якая ўваходзіць у стандартную BOOL загалоўка файла.
Мы дакладна хочам ўключаць у сябе стандартныя bool.h для лагічнага тыпу,
і мы таксама хочам # ўключаюць у сябе стандартныя lib.h для стандартных бібліятэк
, Якія ўключаюць таНос, і свабодныя, і ўсё такое.
Такім чынам, маштаб, мы збіраемся кінуць паліць.
Давайце паспрабуем і пераканацца, што гэта на самай справе зрабіў кампіляцыю.
Мы бачым, што ён робіць, так што мы на правільным шляху.
>> Давайце адкрываць binary_tree.c зноў.
Ён кампілюе. Давайце спусцімся і пераканацца, што мы ўстаўляем некалькі званкоў, каб наша функцыя змяшчае -
проста каб пераканацца, што ўсё добра.
Напрыклад, калі мы зрабілі некаторыя пошуку ў нашым дрэве раней,
Мы спрабавалі знайсці значэння 6, 10 і 1, і мы ведалі, што 6 было ў дрэве,
10 быў не ў дрэве, і 1 не быў у дрэва альбо.
Давайце выкарыстоўваць гэтыя ўзоры званкі як спосаб высветліць, ці з'яўляецца ці не
нашы ўтрымлівае функцыю працуе.
Для таго, каб зрабіць гэта, я збіраюся выкарыстоўваць Е функцыя,
і мы збіраемся, каб раздрукаваць вынік выкліку ўтрымлівае.
Я збіраюся паставіць у радок "змяшчае (% D) = таму што
мы збіраемся падлучыць значэнне, што мы збіраемся шукаць,
і% = з \ п "і выкарыстаць яго ў якасці нашага фармату радка.
Мы проста збіраемся, каб убачыць - у літаральным сэнсе раздрукаваць на экране -
, Што выглядае як выклік функцыі.
Гэта на самай справе не выклік функцыі.
Гэта проста радок прызначана для выглядаць як выклік функцыі.
>> Зараз, мы збіраемся падлучыць значэння.
Мы збіраемся паспрабаваць змяшчае 6,
і тое, што мы збіраемся зрабіць, так гэта выкарыстоўваць, што патройны аператар.
Давайце паглядзім, - утрымоўвае 6 - так, цяпер я утрымліваў 6 і калі змяшчае 6 праўда,
Радок, што мы збіраемся адправіць у фармаце характар% з
будзе радок "ісціна".
Давайце вылучыце на трохі.
У адваротным выпадку, мы хочам даслаць радок "ілжывай", калі змяшчае 6 вяртае хлусня.
Гэта крыху бесталковы з выгляду, але я думаю, я мог бы таксама ілюструюць
што патройны аператар выглядае так як мы не бачылі яго на некаторы час.
Гэта будзе добры, зручны спосаб высветліць, калі нашы ўтрымлівае функцыю працуе.
Я буду пракручваць назад на левую,
і я збіраюся скапіяваць і ўставіць гэты радок некалькі разоў.
Ён змяніў некаторыя з гэтых каштоўнасцяў па ўсім,
так што гэта будзе 1, а гэта будзе 10.
>> На дадзены момант у нас ёсць добрая функцыя ўтрымлівае.
У нас ёсць некалькі тэстаў, і мы ўбачым, калі ўсё гэта працуе.
На дадзены момант мы напісалі яшчэ некалькі кодзе.
Час, каб выйсці, і пераканайцеся, што ўсё яшчэ кампілюе.
Выйсці, і цяпер давайце паспрабуем рабіць бінарнае дрэва зноў.
Што ж, падобна, у нас ёсць памылкі,
І ў нас ёсць гэтая відавочнага аб'явы бібліятэчныя функцыі Printf.
Падобна на тое, што мы павінны пайсці і # ўключыць standardio.h.
І з гэтым, усё павінна кампілявацца. Мы ўсе добра.
Зараз паспрабуйце запусціць бінарнае дрэва і паглядзець, што адбываецца.
Вось і мы,. / Binary_tree,
і мы бачым, што, як мы і чакалі -
таму што мы не рэалізавалі змяшчае яшчэ,
ці, хутчэй, мы проста пакласці ў сваю чаргу ілжывымі -
мы бачым, што гэта проста вяртанне ілжывым для ўсіх з іх,
Так што ўсе працоўныя, па большай частцы даволі добра.
>> Давайце вернемся ў справе ажыццяўлення і ўтрымліваецца ў гэтай кропцы.
Я хачу, каб пракруціць ўніз, павялічваць, і -
Памятаеце, што алгарытм, які мы выкарыстоўвалі ў тым, што мы пачалі ў каранёвай вузел
, А затым у кожным вузле з якімі мы сутыкаемся, мы робім для параўнання,
і на аснове гэтага параўнання мы альбо рухацца налева дзіцяці або правы дзіцяці.
Гэта будзе выглядаць вельмі падобна на двайковы код пошуку, які мы пісалі раней у тэрмін.
Калі мы пачынаем, мы ведаем, што мы хочам правесці на бягучы вузел
што мы глядзім, і бягучы вузел будзе ініцыялізаваны на каранёвай вузел.
І зараз, мы збіраемся працягваць ісці па дрэве,
і памятайце, што нашы прыпынку стане -
Калі мы фактычна працавалі на прыкладзе ўручную -
быў, калі мы сутыкнуліся з нулявой вузел,
не тады, калі мы глядзелі на нулявы дзіцяці,
а калі мы сапраўды пераехалі ў вузел у дрэве
і выявіў, што мы знаходзімся на нулявы вузел.
Мы збіраемся паўтараць, пакуль току не роўная нулю.
І што мы будзем рабіць?
Мы збіраемся праверыць, калі (з актуальн -> значэнне == значэнне),
Затым мы ведаем, што мы на самай справе знайшлі вузел, які мы шукаем.
Дык вось, мы можам вярнуцца дакладна.
У адваротным выпадку, мы хочам бачыць ці не значэнне менш, чым значэнне.
Калі значэнне бягучага вузла менш, чым значэнне, якое мы шукаем,
мы будзем рухацца направа.
Такім чынам, з актуальн. = З актуальн. -> Right_child, а ў адваротным выпадку, мы будзем рухацца налева.
актуальн. = з актуальн. -> left_child;. Даволі проста.
>> Вы, напэўна, прызнаць цыкл, які вельмі падобны на гэтага ад
бінарны пошук у пачатку тэрміну, за выключэннем то мы маем справу з нізкай, сярэдняй і высокай.
Тут мы проста павінны паглядзець на бягучае значэнне,
так што гэта проста і прыгожа.
Давайце пераканацца, што гэты код працуе.
Па-першае, пераканайцеся, што ён кампілюе. Падобна на тое, што ён робіць.
Давайце паспрабуем запусціць яго.
І сапраўды, ён друкуе ўсё, што мы чакалі.
Ён знаходзіць 6 у дрэве, не знайсці 10, таму што 10 не ў дрэве,
і не знаходзіць 1, альбо таму, што 1 таксама не ў дрэве.
Прышпільных рэчаў.
>> Добра. Давайце вернемся да нашай спецыфікацыі і паглядзець, што будзе далей.
Цяпер ён хоча дадаць яшчэ некалькі вузлоў для нашага дрэва.
Яна хоча дадаць 5, 2 і 8, і пераканацца, што нашы змяшчае код
па-ранейшаму працуе, як чакалася.
Давайце рабіць гэта.
На дадзены момант, а не рабіць тое, што раздражняе капіяваць і ўстаўляць зноў,
давайце напішам функцыю, каб фактычна стварыць вузел.
Калі пракруціць ўвесь шлях да галоўнага, мы бачым, што мы рабілі гэта
вельмі падобны код зноў і зноў, кожны раз, калі мы хочам стварыць вузел.
>> Давайце напішам функцыю, якая будзе рэальна пабудаваць вузел для нас, і вярнуць яго.
Я буду называць яго build_node.
Я збіраюся пабудаваць вузел з пэўным значэннем.
Павялічыць тут.
Першае, што я збіраюся зрабіць, гэта на самай справе стварыць прастору для вузла ў кучы.
Такім чынам, вузел * п = таНос (SizeOf (вузла)), п -> значэнне = значэнне;
а потым тут, я проста хачу, каб ініцыялізаваць усе палі, каб быць адпаведныя значэння.
І ў самым канцы, мы вернем наш вузел.
Добра. Адзінае, што варта адзначыць, што гэтая функцыя тут
збіраецца вярнуць паказальнік на вобласць памяці, якая была кучы.
Што прыемна аб гэтым з'яўляецца тое, што гэты вузел цяпер -
мы павінны аб'явіць яго ў кучы, таму што калі мы абвясцілі яго ў стэк
мы не былі б у стане зрабіць гэта ў гэтай функцыі, як гэта.
Гэтая памяць будзе выйсці з сферы
і былі б несапраўднымі, калі мы паспрабавалі атрымаць доступ да яго ў далейшым.
Паколькі мы аб'яўляем кучы памяці,
мы будзем мець, каб клапаціцца аб вызваляючы яго пазней
для нашай праграмы не ўцечка любой памяці.
Мы понтировавшего на што на ўсё астатняе ў кодзе
толькі для прастаты ў той час,
але калі вы калі-небудзь напісаць функцыю, якая выглядае наступным чынам
дзе ў вас ёсць - некаторыя называюць гэта таНос або пераразмеркаваць ўсярэдзіне -
Вы хочаце, каб пераканацца, што вы паклалі нейкі каментар тут, які кажа:
эй, вы ведаеце, вяртае кучы вузлоў ініцыялізуецца перададзены ў кошце.
І тады вы хочаце, каб пераканацца, што вы паклалі ў нейкі ўвагу, што кажа
Выклікае павінен вызваліць вярнулася памяць.
Такім чынам, калі хто-то ніколі не ідзе, і выкарыстоўвае гэтую функцыю,
яны ведаюць, што ўсё, што яны вернуцца з гэтай функцыі
ў нейкі момант трэба будзе вызвалены.
>> Калі выказаць здагадку, што ўсё добра, і тут добра,
мы можам спусціцца ў наш код і замяніць усе гэтыя радкі прама тут
з заклікамі да нашай функцыі вузла зборкі.
Давайце зробім гэта вельмі хутка.
Адна частка, што мы не збіраемся замяніць гэтая частка тут
на дно, дзе мы на самай справе злучаць вузлы, каб паказваць адзін на аднаго,
таму што мы не можам зрабіць у нашых функцый.
Але, давайце зробім корань = build_node (7); вузел * 3 = build_node (3);
вузел * 6 = build_node (6); вузел * 9 = build_node (9),.
І зараз, мы таксама хацелі б дадаць вузлы -
вузел * 5 = build_node (5); вузел * = build_node 8 (8);
і тое, што было на другі вузел? Давайце паглядзім тут. Мы хацелі б таксама дадаць 2 -
* Два клункі = build_node (2);.
Добра. На дадзены момант, мы ведаем, што ў нас ёсць 7, 3, 9, і 6
Усе правадныя адпаведным чынам, але як наконт 5, 8 і 2?
Каб захаваць усё ў належны парадак,
Мы ведаем, што права дзіцяці 3 з'яўляецца 6.
Такім чынам, калі мы збіраемся дадаць 5,
5 таксама належыць да правага боку дрэў, з якіх 3 з'яўляецца коранем,
5 належыць так як левая дзіцяці 6.
Мы можам зрабіць гэта, сказаўшы, шэсць -> left_child = пяць;
, А затым 8 належыць як левая дзіцем з 9, такім чынам, дзевяць -> left_child = восем;
, А затым 2 з'яўляецца левым дзіцем 3, так што мы можам зрабіць гэта тут - Цябе -> left_child = два,.
Калі вы не зусім разумею разам з тым, я прапаную вам зрабіць гэта самастойна.
>> Добра. Давайце захаваем гэта. Давайце выходзіць на вуліцу і пераканайцеся, што ён збірае,
і тады мы можам дадаць у нашу змяшчае выклікі.
Падобна на тое, усё яшчэ кампілюе.
Давайце і дадаць у некаторых змяшчае выклікі.
Зноў жа, я збіраюся зрабіць трохі капіявання і ўстаўкі.
Зараз давайце шукаць 5, 8, і 2. Добра.
Давайце пераканаемся, што гэта ўсё выглядае добра да гэтага часу. Выдатна! Захаваць і выйсці.
Зараз давайце зробім, кампіляцыі, а цяпер давайце працаваць.
З вынікаў, падобна, усё працуе проста прыемна і добра.
Выдатна! Так што цяпер у нас ёсць нашы ўтрымлівае функцыю напісана.
Давайце рухацца далей і пачаць працаваць на тым, як ўставіць вузлы ў дрэва
, Паколькі, як мы робім гэта цяпер, усё не вельмі прыгожа.
>> Калі мы вернемся да спецыфікацыі,
ён просіць, каб мы напісалі функцыю пад назвай ўставіць - зноў, вяртаючыся лагічнае
для таго ці не, мы маглі фактычна ўстаўкі вузла ў дрэва -
, А затым значэнне для ўстаўкі ў дрэва вызначаецца як
Адзіны аргумент, каб нашы функцыі ўстаўкі.
Мы вернемся дакладна, калі мы маглі б сапраўды ўставіць вузел, які змяшчае значэнне ў дрэве,
Гэта азначае, што мы, адзін, меў досыць памяці,
, А затым два, то гэты вузел ўжо не існуюць у дрэве, так -
Памятаеце, што мы не будзем мець аднолькавыя значэння ў дрэве, проста каб зрабіць рэчы простымі.
Добра. Перайсці да коду.
Адкрыйце яго. Павялічыць трохі, а потым пракруціць ўніз.
Скажам функцыі ўстаўкі прама над ўтрымлівае.
Зноў жа, гэта будзе называцца BOOL ўстаўкі (цэлалікавых значэнне).
Дайце яму трохі больш прасторы, а затым, па змаўчанні,
давайце наўзамен ілжывага ў самым канцы.
Цяпер ўніз, на дно, давайце ісці наперад і замест таго, каб ўручную ствараць вузлы
У асноўнай сабе і праводка іх да ўказваць адзін на аднаго, як мы робім,
мы належым на нашыя функцыі ўстаўкі, каб зрабіць гэта.
Мы не будзем спадзявацца на нашы функцыі ўстаўкі для зборкі за ўсё дрэва з нуля, толькі ўсё ж,
а мы пазбавіцца ад гэтых ліній - МЫ закомментируйте гэтыя радкі -
што будаваць вузлы 5, 8 і 2.
А замест гэтага, мы уставім званкі на наш функцыі ўстаўкі
каб пераканацца, што гэта сапраўды працуе.
Тут мы ідзем.
>> Цяпер мы закаментаваць гэтыя радкі.
У нас ёсць толькі 7, 3, 9 і 6 у нашай дрэва ў гэтай кропцы.
Каб пераканацца ў тым, што ўсё гэта працуе,
мы можам паменшыць маштаб, каб нашы бінарнае дрэва,
запусціць яго, і мы бачым, што ўтрымліваецца ў цяперашні час кажа нам, што мы цалкам правы -
5, 8, і 2 ужо не ў дрэве.
Вярніцеся ў кодзе,
і як мы збіраемся ўставіць?
Памятаеце, што мы рабілі, калі мы былі на самай справе ўстаўка 5, 8, і 2 раней.
Мы гулялі ў гэтую гульню Plinko, дзе мы пачалі ў корані,
спусціўся па дрэве адзін на адзін за адным
пакуль мы не знайшлі адпаведную шчыліну,
і тады мы падлучаныя вузла ў адпаведным месцы.
Мы збіраемся зрабіць тое ж самае.
Гэта, у асноўным, як напісанне кода, які мы выкарыстоўвалі ў ўтрымлівае функцыю
Каб знайсці месца, дзе вузел павінен быць,
а потым мы толькі збіраемся, каб ўставіць вузел прама там.
Давайце пачнем гэта рабіць.
>> Такім чынам, мы маем вузел * з актуальн. = Корань; мы толькі збіраемся прытрымлівацца код змяшчае
пакуль мы не знойдзем, што гэта не зусім праца для нас.
Мы збіраемся прайсці праз дрэва ў той час як бягучы элемент не з'яўляецца нулявым,
і калі мы выявім, што значэнне току, роўная значэнню, што мы спрабуем ўставіць -
Ну, гэта адзін з выпадкаў, у якіх мы не маглі фактычна ўстаўкі вузла
ў дрэва, таму што гэта азначае, што ў нас ёсць паўтараюцца значэння.
Тут мы на самай справе збіраемся вярнуцца ілжывым.
Цяпер, інакш, калі значэнне току складае менш значэння,
Цяпер мы ведаем, што мы рухаемся направа
таму што значэнне належыць у правай палове з актуальн. дрэва.
У адваротным выпадку, мы будзем рухацца налева.
Гэта ў асноўным нашы ўтрымлівае функцыю прама там.
>> На дадзены момант, як толькі мы скончылі гэта ў той час цыклу,
шему паказальнік будзе паказваць на нуль
калі функцыя ўжо не вярнуўся.
Мы таму маюць з актуальн. Ў тым месцы, дзе мы хочам, каб ўставіць новы вузел.
Тое, што застаецца зрабіць, гэта на самай справе пабудаваць новы вузел,
што мы можам зрабіць даволі лёгка.
Мы можам выкарыстоўваць нашы супер-зручная зборка вузлоў функцыі,
і тое, што мы не рабілі раней -
мы проста нейкая лічылі само сабой якія разумеюцца, але зараз мы будзем рабіць проста каб пераканацца -
мы будзем праверыць, каб пераканацца, што значэнне вяртаецца новы вузел быў на самай справе
не нулявы, таму што мы не хочам, каб пачаць доступ да гэтай памяці, калі яна не з'яўляецца несапраўдным.
Мы можам праверыць, каб пераканацца, што новы вузел не роўная нулю.
Або замест гэтага, мы можам проста паглядзець, калі ён на самай справе з'яўляецца пустым,
і калі ён роўны нулю, то мы можам проста вярнуцца ілжывым рана.
>> На дадзены момант, мы павінны падлучыць новы вузел у сваю адпаведнае месца ў дрэве.
Калі мы паглядзім на асноўныя і дзе мы былі на самай справе праводкі ў значэннях раней,
мы бачым, што тое, як мы гэта рабілі, калі мы хацелі паставіць 3 у дрэва
Мы былі даступныя левым дзіцяці кораня.
Калі мы ставім 9 у дрэва, мы павінны былі атрымаць доступ да права дзіцяці на пні.
Мы павінны былі мець паказальнік на аднаго з бацькоў для таго, каб пакласці новае значэнне ў дрэва.
Пракрутка назад уставіць, што не збіраецца працаваць тут цалкам
таму што ў нас няма продка.
Што мы хочам быць у стане рабіць гэта, на дадзены момант,
праверце значэнне бацькоў і паглядзець - ну, чорт вазьмі,
калі значэнне аднаго з бацькоў менш, чым бягучае значэнне,
Затым права дзіцяці бацька павінен быць новы вузел;
У адваротным выпадку левая дзіцяці бацька павінен быць новы вузел.
Але мы не павінны гэтага аднаго з бацькоў паказальнік зусім яшчэ.
>> Для таго, каб атрымаць яго, мы фактычна прыйдзецца адсочваць яго, як мы ідзем па дрэве
і знайсці адпаведнае месца ў нашым цыкле вышэй.
Мы можам зрабіць гэта з дапамогай пракруткі назад да вяршыні нашай функцыі ўстаўкі
і адсочвання іншы паказальнік зменнай бацькоў.
Мы збіраемся ўсталяваць яго роўным нулю на пачатковым этапе,
, А затым кожны раз, калі мы ідзем па дрэве,
Мы збіраемся ўсталяваць аднаго з бацькоў, каб адпавядаць бягучых паказальнікам.
Ўсталяваць бацькоўскі роўна з актуальн ..
Такім чынам, кожны раз, калі мы прайсці,
Мы збіраемся пераканацца, што ў якасці бягучага паказальніка павялічваецца на адзінку
бацькоўскага паказальнік варта за ім - проста на адзін узровень вышэй бягучага паказальніка ў дрэве.
Гэта ўсё выглядае даволі добра.
>> Я думаю, што адна рэч, якую мы хочам наладзіць гэта пабудаваць вузел вяртаецца NULL.
Для таго, каб пабудаваць вузел на самай справе паспяхова вяртаюць NULL,
мы павінны змяніць гэты код,
таму што тут, мы ніколі не правяралі, каб пераканацца, што таНос вярнуўся сапраўдны паказальнік.
Так што, калі (п = NULL!), Затым -
калі таНос вярнуўся сапраўдны паказальнік, то мы яго ініцыялізацыі;
У адваротным выпадку мы будзем проста вярнуць, і што ў канчатковым выніку вяртаецца NULL для нас.
Цяпер усё выглядае даволі добра. Давайце пераканацца, што гэта на самай справе кампілюе.
Зрабіць бінарнае дрэва, і ах, у нас ёсць некаторыя рэчы тут адбываецца.
>> У нас ёсць няяўнай дэкларацыя функцыі стварэння вузла.
Зноў жа, гэтыя кампілятары, мы збіраемся пачаць з самага верху.
Што гэта павінна азначаць, што я тэлефаную пабудаваць вузел, перш чым я на самой справе аб'яўлена.
Давайце вернемся да коду вельмі хутка.
Пракруціць ўніз, і, вядома ж, мая ўстаўка функцыя аб'яўлена
вышэй функцыі вузла зборкі,
Але я спрабую выкарыстоўваць пабудаваць вузел ўнутры ўстаўкі.
Я збіраюся пайсці і копію - а затым устаўце функцыю зборкі вузлоў шлях тут, на самым версе.
Такім чынам, мы спадзяемся, што будзе працаваць. Давайце дамо гэтага яшчэ адзін шанец.
Цяпер усё кампілюецца. Усё гэта добра.
>> Але на дадзены момант, мы на самай справе не называлі нашы функцыі ўстаўкі.
Мы проста ведаем, што ён збірае, так што давайце пойдзем і пакласці некалькі званкоў цалі
Давайце зробім, што ў нашых асноўных функцый.
Тут мы закаментаваны 5, 8 і 2,
і тады мы не падключыць іх сюды.
Давайце зробім некалькі званкоў, каб ўставіць,
і давайце таксама выкарыстоўваць такія ж рэчы, якія мы выкарыстоўвалі
Калі мы зрабілі гэтыя Printf званкоў, каб пераканацца, што ўсё сапраўды станавіліся адсутнічае правільна.
Я збіраюся капіяваць і ўстаўляць,
і замест таго, утрымлівае мы збіраемся зрабіць ўстаўку.
І замест таго, 6, 10 і 1, мы збіраемся выкарыстаць 5, 8 і 2.
Гэта павінна, мы спадзяемся, уставіць 5, 8, і 2 у дрэва.
Кампіляцыя. Усё гэта добра. Цяпер мы будзем рэальна працаваць наша праграма.
>> Усе вярнуліся ілжывай.
Так, 5, 8 і 2 не пайшоў, і гэта выглядае як Утрымоўвае не знайшлі іх альбо.
Што адбываецца? Давайце маштабу.
Першай праблемай было тое, што, здавалася ўстаўкі, каб вярнуцца ілжывым,
і, падобна, гэта таму, што мы пакінулі ў нашым вяртанні ілжывы выклік,
і мы ніколі не вярнуліся праўда.
Мы можам ўсталяваць, што.
Другая праблема ў тым, зараз, нават калі мы робім - захаваць гэта, кінуць гэта,
запусціць зрабіць зноў, хай ён скампіляваць, а затым запусціць яго -
мы бачым, што нешта яшчэ адбылося.
5, 8, і 2 яшчэ не знайшоў у дрэве.
Такім чынам, што адбываецца?
>> Давайце паглядзім на гэта ў кодзе.
Давайце паглядзім, ці зможам мы зразумець гэта.
Пачнем з бацькамі не быць нулявым.
Мы ўсталёўваем паказальнік бягучай роўных у каранёвай паказальнік,
і мы збіраемся працаваць наш шлях ўніз па дрэве.
Калі бягучы вузел не з'яўляецца нулявым, то мы ведаем, што мы можам рухацца ўніз трохі.
Мы ўсталёўваем нашы бацькі паказальнік роўным бягучаму паказальніку,
праверыць значэнне - калі значэння супадаюць, мы вярнуліся ілжывай.
Калі значэнні менш мы пераехалі ў правую;
У адваротным выпадку мы пераехалі на левы.
Затым мы будуем вузла. Я павялічыць няшмат.
І вось, мы збіраемся, каб паспрабаваць падлучыць да значэнняў, тое ж самае.
Што адбываецца? Давайце паглядзім, калі магчыма Valgrind можа даць нам падказку.
>> Мне падабаецца выкарыстоўваць Valgrind Valgrind толькі таму, што вельмі хутка бяжыць
і кажа вам, калі ёсць якія-небудзь памылкі памяці.
Калі мы запускаем Valgrind на код,
як вы можаце бачыць правы ўдар here--Valgrind./binary_tree--and ўваходу.
Вы бачыце, што ў нас не было ніякіх памылак памяці, так што падобна, усё ў парадку да гэтага часу.
У нас ёсць некаторыя ўцечкі памяці, якія мы ведаем, таму што мы не
адбываецца, каб вызваліць любога з нашых вузлоў.
Давайце паспрабуем працуе GDB, каб паглядзець, што адбываецца на самай справе.
Мы зробім GDB. / Binary_tree. Ён загрузіўся нармальна.
Давайце ўсталюем кропку супыну на ўстаўку.
Давайце запусцім.
Падобна на тое, мы ніколі не называлі ўстаўкі.
Падобна на тое, праблема была толькі што, калі я змяніў тут, у галоўным -
Усе гэтыя Printf званкі з ўтрымлівае -
Я ніколі на самай справе змянілася гэтых патэлефанаваць ўстаўкі.
Зараз давайце даць яму паспрабаваць. Давайце кампіляцыі.
Усё выглядае добра там. Зараз давайце паспрабуем запусціць яго, паглядзець, што адбываецца.
Добра! Усё выглядае даволі добра там.
>> Апошняя рэч, каб думаць пра тое, ці ёсць нейкія крайнія выпадкі гэтай ўстаўкі?
І атрымліваецца, што, маўляў, адно рабро выпадку гэта заўсёды цікава думаць пра
у тым, што адбудзецца, калі ваша дрэва пуста, і вы называеце гэта ўстаўка функцыі?
Ці будзе яна працаваць? Што ж, давайце паспрабуем.
- Binary_tree с. -
Тое, як мы збіраемся праверыць гэта, мы збіраемся спусціцца да нашай асноўнай функцыі,
і замест праводкі гэтых вузлах вось так,
мы толькі збіраемся, каб закаментаваць ўсю рэч,
і замест праводкі да вузлы сабе,
мы сапраўды можам проста ісці наперад і выдаліць усё гэта.
Мы збіраемся зрабіць усё выклік для ўстаўкі.
Такім чынам, давайце рабіць - замест 5, 8 і 2, мы збіраемся, каб ўставіць 7, 3 і 9.
І тады мы таксама хочам, каб ўставіць 6, а.
Захаваць. Выйсці. Зрабіць бінарнае дрэва.
Гэта ўсё кампілюецца.
Мы можам проста запусціце яго як ёсць і паглядзець, што адбываецца,
але гэта таксама будзе вельмі важна, каб пераканацца, што
Мы не маюць ніякіх памылак памяці,
так як гэта з'яўляецца адным з нашых крайніх выпадках, што мы ведаем пра.
>> Давайце пераканаемся, што ён добра працуе пад Valgrind,
якія мы будзем рабіць, проста выдаўшы Valgrind. / binary_tree.
Падобна на тое, у нас сапраўды адна памылка з аднаго кантэксту -
у нас ёсць гэтая памылка сегментацыі.
Што здарылася?
Valgrind на самай справе кажа нам, дзе ён знаходзіцца.
Паменшыць трохі.
Падобна на тое, што адбываецца ў нашай функцыі ўстаўкі,
дзе ў нас ёсць несапраўдным чытання памерам 4 на ўстаўку, радок 60.
Давайце вернемся і паглядзім, што тут адбываецца.
Паменшыць вельмі хутка.
Я хачу, каб пераканацца, што ён не ідзе да краю экрана, каб мы маглі бачыць усё.
Пацягніце, што ў няшмат. Добра.
Пракруціць ўніз, і праблема прама тут.
Што адбудзецца, калі мы спускаемся і наш бягучы вузел ўжо нулявыя,
наш бацькоўскі вузел з'яўляецца нулявым, таму, калі мы глядзім на самым версе, прама тут -
Калі гэта час цыклу ніколі не выконваецца
таму што наша бягучае значэнне роўна нулю - наш корань нулявы так з актуальн. з'яўляецца несапраўдным -
Затым нашы бацькі ніколі не будзе ўсталяваны ў актуальн. Або дапушчальнае значэнне,
Такім чынам, бацькі таксама будзе нулявы.
Мы павінны памятаць, каб праверыць, што
Да таго часу мы прыступім тут, і мы пачынаем доступ да значэння бацькоў.
Такім чынам, што адбываецца? Ну, калі бацька з'яўляецца нуль -
калі (== NULL аднаго з бацькоў), - то мы ведаем, што
не павінна быць нічога ў дрэва.
Мы павінны спрабаваць ўставіць яго ў корані.
Мы можам зрабіць гэта, проста задаўшы корань, роўны новы вузел.
Тады ў гэтай кропцы мы на самай справе не хочуць, каб прайсці праз гэтыя іншыя рэчы.
Замест гэтага, прама тут, мы можам зрабіць альбо іншае-калі-іншаму,
ці мы маглі б аб'яднаць усе тут у іншым,
але тут мы будзем выкарыстоўваць яшчэ і зрабіць гэта такім чынам.
Зараз, мы збіраемся праверыць, каб пераканацца, што нашы бацькі не нулявы
да гэтага на самай справе спрабуе атрымаць доступ да яго палях.
Гэта дапаможа нам пазбегнуць памылкі сегментацыі.
Такім чынам, мы кінуць паліць, паменшыць маштаб, кампіляваць, запускаць.
>> Няма памылкі, але ў нас яшчэ ёсць куча уцечак памяці
таму што мы не вызваліць любога з нашых вузлоў.
Але, калі мы ідзем сюды, і мы глядзім на нашу раздрукоўку,
мы бачым, што, ну, падобна, што ўсе нашы ўстаўкамі вярталіся праўда, і гэта добра.
Устаўкі усё правільна,
, А затым адпаведныя выклікі змяшчае, таксама дакладна.
>> Добрая праца! Падобна на тое, мы паспяхова напісана ўстаўкі.
Гэта ўсё, што ў нас ёсць праблемы спецыфікацыі для набору на гэтым тыдні.
Адна пацешная магчымасць падумаць аб тым, як бы вы на самой справе ідуць у
і бясплатна усе вузлы ў гэтым дрэве.
Мы можам зрабіць гэта рознымі спосабамі,
але я пакіну гэта да вас, каб эксперымент,
і як весела задачай, паспрабуйце і пераканайцеся, што вы можаце пераканацца,
што гэты даклад Valgrind не вяртае памылкі і ўцечкі.
>> Поспехі на Хафман гэтым тыдні пастаўленай задачы кадавання,
і мы будзем бачыць вас на наступным тыдні!
[CS50.TV]