[Powered by Google Translate] [Частка 7: больш камфортным]
[Rob Боуден] [Harvard University]
[Гэта CS50] [CS50.TV]
Добра. Так як я сказаў у маёй электроннай пошце,
гэта будзе двайковага дрэва інтэнсіўнай раздзеле.
Але ёсць не тое, што многія пытанні.
Такім чынам, мы збіраемся, каб паспрабаваць выцягнуць на кожнае пытанне
і перайсці ў хваравітае падрабязна ўсё лепшыя спосабы вядзення спраў.
Такім чынам, у самым пачатку, мы праходзім праз узораў малюнкаў бінарныя дрэвы і іншае.
Дык вось, "Помні, што бінарнае дрэва мае вузлы, аналагічныя звязаны спіс,
толькі замест аднаго паказальніка існуе два: адзін для «дзіцяці» левы
і адзін для правага "дзіця".
Такім чынам, бінарнае дрэва гэтак жа, як звязаны спіс,
акрамя структура будзе мець два паказальніка.
Там у Тройская дрэў, якія будзе мець тры паказальніка,
Ёсць N-арной дрэвы, якія толькі ёсць агульны паказальнік
што вы тады павінны таНос быць дастаткова вялікім, каб мець
Дастаткова паказальнікі на ўсе магчымыя дзяцей.
Такім чынам, бінарнае дрэва толькі, здараецца, маюць пастаяннае лік два.
Калі вы хочаце, вы можаце даць звязаны спіс як унарный дрэва,
Але я не думаю, што нехта называе яе гэтым.
"Нічыя скрынкі-і-стрэлкі схема двайковага дрэва вузлоў
якія змяшчаюць любімы нумар Нейт, 7, дзе кожны дзіця паказальнік нулявы ".
Так Ipad рэжыме.
>> Гэта будзе даволі проста.
Мы проста будзем мець вузел, я намалюю яго як квадрат.
І я намалюю значэння тут.
Такім чынам, значэнне будзе ісці сюды,
, А затым тут мы будзем мець левы паказальнік на левы і правы паказальнік справа.
І гэта нават вельмі канвенцыі назваць яго левым і правым, імёны паказальнікаў.
Абодва гэтых збіраецеся быць нулявым.
Гэта будзе проста нулявым, і гэта будзе проста нулявым.
Добра. Такім чынам, вернемся сюды.
"З звязанага спісу, мы толькі павінны былі захоўваць паказальнік
на першы вузел у спісе, каб запомніць ўвесь звязаны спіс, ці ўвесь спіс.
Акрамя таго, з дрэвамі, у нас ёсць толькі для захоўвання паказальніка
ў адзін вузел, каб памятаць усё дрэва.
Гэты вузел Calle «корань» дрэва.
Пабудаваць на вашай схеме ад да або прыцягнуць новае
такое, што ў вас ёсць скрынкі-і-стрэлкі малюнак бінарнае дрэва
з значэннем 7, затым 3 у левай,
Затым 9 на правую, а затым 6 на права 3 ".
Давайце паглядзім, калі я магу памятаць усё, што ў маёй галаве.
Такім чынам, гэта будзе наш корань тут.
У нас будзе некалькі паказальнікаў дзесьці, нешта, што мы называем коранем,
, І гэта паказвае на гэтага хлопца.
Зараз, каб зрабіць новы вузел,
Што мы маем, 3 злева?
Такім чынам, новы вузел з 3 гадоў, і першапачаткова адзначае нулявы.
Я проста паклаў N.
Цяпер мы хочам, каб гэта пайсці налева 7.
Такім чынам, мы змяніць гэта паказальнік цяпер паказвае на гэтага хлопца.
І мы робім тое ж самае. Мы хочам, каб у 9 тут
які першапачаткова проста кажа нулявым.
Мы збіраемся змяніць гэта паказальнік, кропка да 9,
і цяпер мы хочам пакласці 6 на права 3.
Так што гэта будзе - зрабіць 6.
І гэты хлопец будзе ўказваць там.
Добра. Так што гэта ўсё, што просіць нас зрабіць.
>> Зараз давайце пройдземся па тэрміналогіі.
Мы ўжо казалі пра тое, як корань дрэва з'яўляецца самы верхні вузел у дрэве.
Адна з якіх 7. Вузлоў у ніжняй часткі дрэва называюцца лісцем.
Любы вузел, які проста мае нулявое сваім дзецям ліста.
Такім чынам, гэта магчыма, калі нашы бінарнае дрэва знаходзіцца ўсяго ў адным вузле,
, Што дрэва з'яўляецца лістом, і гэта ўсё.
"" Вышыня "дрэва з'яўляецца колькасць скачкоў вы павінны зрабіць
каб атрымаць ад вяршыні да ліста ".
Мы ўвойдзем у ў другім, розніца
паміж сіметрычнымі і несіметрычнае бінарныя дрэвы,
але цяпер, агульная вышыня гэтага дрэва
Я б сказаў, гэта 3, хоць калі палічыць колькасць скачкоў
Вы павінны зрабіць для таго, каб дабрацца да 9, то гэта сапраўды толькі вышыня 2.
Цяпер гэта незбалансаванае бінарнае дрэва,
але мы казалі аб збалансаваным, калі яно стане актуальным.
Так што цяпер мы можам казаць пра вузлоў у дрэве з пункту гледжання
па адносінах да іншых вузлоў у дрэве.
Так што цяпер у нас ёсць бацькі, дзеці, браты, сёстры, продкі, і нашчадкі.
Яны даволі здаровага сэнсу, што яны азначаюць.
Калі мы будзем патрабаваць, - гэта бацькі.
Так што бацька 3?
[Студэнты] 7. >> Так. Бацька проста будзе тое, што паказвае на вас.
Тады што дзеці ад 7?
[Студэнты] 3 і 9. >> Так.
Звярніце ўвагу, што "дзеці" літаральна азначае дзеці,
так 6 не будзе прымяняцца, таму што гэта, як унук.
Але тады, калі мы пойдзем нашчадкаў, так што з'яўляюцца нашчадкамі 7?
[Студэнты] 3, 6 і 9. >> Так.
Нашчадкі каранёвага вузла будзе ўсё ў дрэве,
акрамя, можа быць каранёвым вузлом сябе, калі вы не хочаце, каб разгледзець, што нашчадак.
І, нарэшце, продкі, так што гэта ў процілеглым кірунку.
Так што продкі 6?
[Студэнты] 3 і 7. >> Так. 9 не ўключаны.
Гэта проста прамая спіна лініі ў корань
будзе вашым продкам.
>> "Мы кажам, што бінарнае дрэва" замовіць ", калі для кожнага вузла ў дрэве,
ўсе яго нашчадкі злева маюць меншыя значэння
і ўсе тыя, на правым мець больш значэння.
Напрыклад, дрэва вышэй замовілі, але гэта не адзіны магчымы спарадкаванае размяшчэнне ".
Перш чым мы пяройдзем да гэтага,
загадаў бінарнае дрэва таксама вядомы як бінарнае дрэва пошуку.
Тут мы, здараецца, назваўшы яго замовіў бінарнае дрэва,
Але я ніколі не чуў яго называюць загадаў двайковага дрэва раней,
і на тэст мы значна больш шанцаў паставіць двайковага дрэва пошуку.
Яны адно і тое ж,
і вельмі важна, вы даведаецеся адрозненне паміж бінарнае дрэва і дрэва двайковага пошуку.
Бінарнае дрэва гэта проста дрэва, якое паказвае на дзве рэчы.
Кожны вузел паказвае на дзве рэчы.
Існуе няма разваг пра каштоўнасці, якія ён паказвае.
Так як тут, так як гэта бінарнае дрэва пошуку,
Мы ведаем, што калі мы пойдзем злева ад 7,
Затым усе каштоўнасці, якія мы можа дасягнуць
, Ідучы злева ад 7 павінны быць менш 7.
Звярніце ўвагу, што ўсе значэння менш, чым 7, 3 і 6.
Гэта ўсё да левай 7.
Калі мы ідзем направа з 7, усё павінна быць больш, чым 7,
таму 9 з правага боку 7, так што мы добрыя.
Гэта не так у выпадку двайковага дрэва,
для звычайнага бінарнага дрэва мы можам проста ёсць 3 у верхнім, 7 налева,
9 злева ад 7: няма спарадкаванасці значэнняў наогул.
Цяпер мы на самай справе не робяць гэтага, таму што гэта сумна і не трэба,
але "спрабуюць прыцягнуць столькі загадаў дрэў, як вы можаце думаць аб
з дапамогай лікаў 7, 3, 9 і 6.
Колькі розных механізмаў ёсць? Што такое вышыня кожнага з іх? "
>> Мы зробім пару, але асноўная ідэя ў тым,
гэта ні ў якай меры унікальнае прадстаўленне двайковага дрэва, які змяшчае гэтыя значэння.
Усё, што нам трэба, гэта некаторы бінарнае дрэва, якое змяшчае 7, 3, 6 і 9.
Іншы магчымы сапраўды быў бы корань 3,
ідзіце налева, і гэта 6, ісці налева, і гэта 7,
ідзіце налева, і гэта 9.
Гэта цалкам дапушчальна бінарнае дрэва пошуку.
Гэта не вельмі карысна, таму што гэта як звязаны спіс
і ўсе гэтыя паказальнікі проста нулявы.
Але гэта сапраўды дрэва. Да?
[Студэнт] Не значэнні павінны быць больш на правай?
Ці гэта -? >> Гэтыя Я хацеў пайсці іншым шляхам.
Там жа - так, давайце пяройдзем гэта.
9, 7, 6, 3. Добры ўлоў.
Ён па-ранейшаму павінен падпарадкоўвацца, што пошук бінарнае дрэва, што павінен рабіць.
Такім чынам, усё, што лявей павінна быць менш любога зададзенага вузла.
Мы маглі б проста рухацца, казаць, што гэта 6 і паклаў яго тут.
Не, мы не можам. Чаму я раблю гэта?
Давайце рабіць - вось 6, тут 7, 6 ачкоў 3.
Гэта па-ранейшаму сапраўдныя бінарнае дрэва пошуку.
Што дрэннага, калі я - паглядзім, ці змагу я прыдумаць дамоўленасці.
Так, усё ў парадку. Так што ж не так з гэтым дрэвам?
Я мяркую, што я ўжо даў вам падказку, што нешта не ў парадку з гэтым.
Чаму я раблю гэта?
Добра. Гэта выглядае разумным.
Калі мы паглядзім на кожны вузел, як і 7, то злева ад 7, 3.
Такім чынам, мы маем 3, рэч справа ад 3 уяўляе сабой 6.
І калі вы паглядзіце на 6, рэч справа ад 6, 9.
Дык чаму ж гэта не з'яўляецца дапушчальным бінарнае дрэва пошуку?
[Студэнты] 9-ранейшаму ў левай частцы 7. >> Так.
Гэта павінна быць дакладна, што ўсе значэння, якія можа дасягнуць, перайшоўшы ў левую ад 7 менш, чым 7.
Калі мы ідзем налева з 7, мы атрымліваем 3, і мы ўсё яшчэ можаце атрымаць да 6,
Мы ўсё яшчэ можаце атрымаць да 9, але, прайшоўшы менш 7,
мы не павінны быць у стане дабрацца да шэрагу, што гэта больш 7.
Так што гэта не з'яўляецца дапушчальным бінарнае дрэва пошуку.
>> Мой брат на самай справе было інтэрв'ю пытанне
, Што ў асноўным гэта, проста код нешта для праверкі
Ці дрэва бінарнае дрэва пошуку,
і таму першае, што ён зрабіў, было проста праверыць,
калі левы і правы правільна, а затым паўтараць там.
Але вы не можаце проста зрабіць гэта, вы павінны сачыць
той факт, што зараз, калі я сышоў лявей 7,
ўсё ў гэтым поддереве павінна быць менш 7.
Правільны алгарытм павінен сачыць
за межы значэнняў, што можа ўпасці магчыма цалі
Мы не будзем прайсці праз усе з іх.
Існуе добрае стаўленне рэцыдыву,
хоць мы яшчэ не дайшлі да таго, ці мы не атрымаем тых,
вызначальная, колькі там на самай справе.
Такім чынам, існуе 14 з іх.
Ідэя пра тое, як вы маглі б зрабіць гэта матэматычна, як,
Вы можаце выбраць якой-небудзь адной, каб быць каранёвай вузел,
а затым, калі я выбіраю быць ад 7 да каранёвага вузла,
гэта значыць, скажам, некаторыя лічбы, якія могуць пайсці маім левым вузлом,
і ёсць некаторыя нумары, якія могуць быць мая правая вузла,
але калі я п агульнай колькасці, то сума, якая можа пайсці налева
плюс сума, якая можа пайсці на права N - 1.
Такім чынам, з пакінутых лікаў, яны павінны быць у стане пайсці альбо налева або направа.
Здаецца, цяжка, што, калі я пастаўлю 3 першых, то ўсё павінна пайсці налева,
але калі я пастаўлю 7, то некаторыя рэчы могуць пайсці левай і некаторыя рэчы могуць пайсці направа.
І '3 першы "я меў на ўвазе ўсё можа пайсці направа.
Гэта сапраўды, вы проста павінны думаць пра гэта, як,
як шмат што можа пайсці на наступным узроўні дрэва.
І ён выходзіць на 14, ці вы можаце намаляваць усё,
і тады вы атрымаеце 14.
>> Вяртаючыся сюды,
"Спарадкаваныя бінарныя дрэвы з'яўляюцца выдатна, таму што мы можам шукаць праз іх
У вельмі падобна на пошукі больш спарадкаваны масіў.
Каб зрабіць гэта, мы пачынаем з кораня і працаваць наш шлях ўніз па дрэве
на лісці, правяраючы значэння кожнага вузла ў дачыненні да каштоўнасцяў, якія мы шукаем.
Калі значэнне бягучага вузла менш, чым значэнне, якое мы шукаем,
Вы ідзяце побач з правым нашчадкам вузла.
У адваротным выпадку, вы ідзяце ў левым нашчадка.
У нейкі момант, вы альбо знайсці значэнне, якое вы шукаеце, ці вы будзеце працаваць у нуль,
з указаннем значэння не ў дрэве ".
У мяне ёсць для перамалёўкі дрэва, што было раней, то вазьму другі.
Але мы хочам, каб шукаць ці 6, 10, і 1 у дрэва.
Дык што ж гэта было, 7, 9, 3, 6. Добра.
Лічбы, якія вы хочаце паглядзець, мы хочам, каб паглядзець 6.
Як гэта алгарытм працы?
Ну, у нас ёсць некалькі каранёвых паказальнік на дрэва.
І мы пайшлі б у корані і казаць, гэта значэнне роўна значэнню мы шукаем?
Такім чынам, мы шукаем 6, так што гэта не роўныя.
Такім чынам, мы працягваем, і цяпер мы гаворым, добра, так 6 менш 7.
Ці азначае гэта, мы хочам ісці налева, ці мы хочам, каб пайсці ў парадку?
[Студэнт] налева. >> Так.
Гэта значна прасцей, усё, што вам трэба зрабіць, гэта зрабіць адзін магчымы вузел дрэва
і тады вы не - замест таго, каб думаць галавой,
Добра, калі яна менш, я магу пайсці налева або пайсці направа,
проста гледзячы на ​​гэтую карціну, гэта вельмі ясна, што я павінен ісці злева
калі гэты сайт больш, чым значэнне, што я шукаў.
Такім чынам, вы ідзіце налева, цяпер я на 3.
Я хачу - 3 менш, чым значэнне, я шукаю, што на 6.
Такім чынам, мы ідзем направа, і цяпер я ў канчатковым выніку на 6,
якая з'яўляецца значэннем я шукаю, так што я вяртаюся праўда.
Наступнае значэнне, я буду глядзець на гэта 10.
Добра. Так што 10, зараз будзе - адрэзаў, што - будзем прытрымлівацца кораня.
Цяпер, 10 будзе больш за 7, таму я хачу, каб глядзець направа.
Я збіраюся прыехаць сюды, 10 будзе больш за 9,
так што я збіраюся хочаце паглядзець направа.
Я прыйшоў сюды, але тут цяпер я ў нуль.
Што мне рабіць, калі я ударыў нуль?
[Студэнт] Вярнуцца ілжывым? >> Так. Я не знайшоў 10.
1, будзе амаль ідэнтычная выпадку,
выключэннем таго, што толькі збіраецца быць перавернутая, замест таго каб шукаць
ўніз па правай баку, я буду глядзець на левы бок.
>> Цяпер я думаю, што мы на самай справе атрымаць код.
Вось дзе - адкрыць CS50 прыбор і пракладвае свой шлях там,
але вы таксама можаце проста зрабіць гэта ў прасторы.
Гэта, напэўна, ідэальны зрабіць гэта ў прасторы,
таму што мы можам працаваць у космасе.
"Спачатку трэба новае вызначэнне тыпу для бінарнага вузла дрэва, які змяшчае Int значэння.
Выкарыстанне шаблону ЬурейеЕ ніжэй,
стварыць новае вызначэнне тыпу для вузла ў бінарным дрэве.
Калі вы затрымаліся. . . "Бла, бла, бла. Добра.
Так давайце шаблоннага тут,
ЬурейеЕ вузла структуры і вузлоў. Так, усё ў парадку.
Так што поле мы збіраемся хочам у нашай вузла?
[Студэнт] Int, а затым два паказальніка?
>> Int значэння, два паказальніка? Як напісаць паказальнікі?
[Студэнт] Struct. >> Я павінна павялічыць маштаб Так, так што структура вузла * сышоў,
і структура вузла * мае рацыю.
І памятайце абмеркаванне ў мінулы раз,
што гэта не мае сэнсу, гэта не мае сэнсу,
гэта не мае сэнсу.
Вам трэба ўсё, для таго, каб вызначыць гэта рэкурсіўная структура.
Добра, так гэта тое, што наша дрэва будзе выглядаць.
Калі б мы зрабілі Тройская дрэва, то вузел можа выглядаць В1, В2, структура вузла * b3,
дзе Ь філіяла - на самай справе, я больш чуў ён пакінуў, сярэдні, правы, але незалежна.
Мы клапоцімся толькі пра бінарных, так направа, налева.
"Зараз абвясціць глабальную зменную * вузел для кораня дрэва".
Такім чынам, мы не збіраемся гэтага рабіць.
Для таго, каб зрабіць рэчы крыху больш складаным і больш абагульненыя,
у нас не будзе глабальнай зменнай вузла.
Замест гэтага, у галоўным мы аб'явім ўсе нашы вузел рэчы,
і гэта азначае, што ніжэй, калі мы пачнем працы
нашы ўтрымлівае функцыю і нашы функцыі ўстаўкі,
замест таго, каб нашы ўтрымлівае функцыю толькі з дапамогай гэтай глабальнай зменнай вузла,
мы будзем мець яго прыняць у якасці аргументу дрэва, якое мы хочам, каб апрацаваць.
Наяўнасць глабальных зменных павінен быў зрабіць рэчы прасцей.
Мы збіраемся зрабіць усё цяжэй.
Зараз вазьміце хвіліну ці каля таго, каб проста рабіць такога роду рэчы,
дзе ўнутры асноўнага вы хочаце стварыць гэтае дрэва, і гэта ўсё, што вы хочаце зрабіць.
Паспрабуйце пабудаваць гэта дрэва ў асноўнай функцыяй.
>> Добра. Такім чынам, вы не павінны нават пабудавалі дрэва ўсю дарогу пакуль няма.
Але ў каго нешта я мог бы падцягнуць
каб паказаць, як можна было б пачаць будаўніцтва такога дрэва?
[Студэнт] Хтосьці стук, спрабуючы выбрацца вонкі.
[Боуден] Любы камфортна з іх пабудовы дрэва?
[Студэнт] Вядома. Гэта не зроблена. >> Гэта нармальна. Мы можам проста скончыць -
ой, вы можаце захаваць яго? Ура.
Такім чынам, тут мы маем - ой, я трохі абразаюцца.
Ці магу я павялічыў?
Павелічэнне, пракрутка з. >> У мяне ёсць пытанне. >> Да?
[Студэнт] Пры вызначэнні структуры, такія рэчы, як ініцыялізуецца што-небудзь?
[Боуден] Няма >> Добра. Такім чынам, вы павінны ініцыялізаваць -
[Боуден] Няма Калі вы вызначаеце, або пры аб'яўленні структуры,
ён не ініцыялізаваны па змаўчанні, гэта ўсё роўна, калі вы аб'явіце Int.
Гэта роўна тое ж самае. Гэта як кожны з яе асобных палёў
можа мець значэнне смецця ў ім. >> А ці можна вызначыць - ці абвясціць структуру
такім чынам, што гэта робіць іх ініцыялізацыі?
[Боуден] Так. Такім чынам, кантэкстнае сінтаксіс ініцыялізацыі
будзе выглядаць -
Там дзве, як мы можам гэта зрабіць. Я думаю, мы павінны скампіляваць яго
каб пераканацца, што Clang робіць тое ж самае.
Парадак аргументаў, які ўваходзіць у структуру,
вы пакладзеце ў парадак аргументаў ўнутры гэтых фігурныя дужкі.
Таму калі вы хочаце, каб падрыхтаваць яго да 9 і пакінулі быць нулявы, а затым правую быць нулявым,
было б 9, NULL, NULL.
У якасці альтэрнатывы, і рэдактар ​​не падабаецца гэты сінтаксіс,
і ён думае, што я хачу новы блок,
але альтэрнатыва ёсць нешта накшталт -
Тут, я пакладу яе на новы радок.
Можна прама сказаць, не памятаю дакладна сінтаксіс.
Такім чынам, вы можаце відавочна звярнуцца да іх па імя, і кажу:
. З, або. Значэнне = 9. Левая = NULL.
Я мяркую, гэта неабходнасць быць коскі.
. Права = NULL, каб такім чынам вы не
на самай справе трэба ведаць парадак структуры,
і калі вы гэта чытаеце, гэта значна больш відавочную
пра тое, што каштоўнасць быцця ініцыялізуецца.
>> Гэта здараецца, адна з рэчаў, якія -
так, па большай частцы, C + + з'яўляецца пашырэннем C.
Вы можаце ўзяць C код, перамясціць яго на C + +, і яна павінна сабраць.
Гэта адна з рэчаў, якія C + + не падтрымлівае, так што людзі, як правіла не рабіць гэтага.
Я не ведаю, калі гэта адзіная прычына, людзі, як правіла не рабіць гэтага,
але справа, дзе я павінен яго выкарыстоўваць неабходныя для працы з C + + і таму я не мог выкарыстаць гэта.
Іншы прыклад таго, што не працуе з C + + з'яўляецца
як таНос вяртае "пустата *," тэхнічна,
але вы маглі б проста сказаць, сімвал * х = таНос што заўгодна,
і ён аўтаматычна будзе прыведзены да сімвал *.
Гэта аўтаматычны літых не бывае ў C + +.
Гэта не будзе кампілявацца, і вы б відавочна трэба сказаць
сімвал *, таНос, што заўгодна, каб кінуць яго ў знак *.
Ёсць не так шмат рэчаў, якія C і C + + не згодныя з,
але гэтыя два.
Такім чынам, мы пойдзем з гэтым сінтаксісам.
Але нават калі б мы не ішлі з сінтаксісам,
што такое - можа быць дрэннага ў гэтым?
[Студэнт] Мне не трэба разыменовать гэта? >> Так.
Памятаеце, што стрэлка мае няяўна разнаймення,
і таму, калі мы проста маем справу з структурай,
Мы хочам выкарыстаць. каб дабрацца да поля ўнутры структуры.
І адзіны раз, калі мы выкарыстоўваем стрэлкі, калі мы хочам зрабіць -
Ну, стрэлкі эквівалентна -
вось што гэта азначала б, калі б я выкарыстаў стрэлку.
Усе стрэлкі сродак, разыменовать, цяпер я ў структуры, і я магу атрымаць полі.
Альбо атрымаць полі прама або разнаймення і атрымаць полі -
Я думаю, гэта павінна быць значэнне.
Але тут я маю справу толькі з структуру, а не паказальнік на структуру,
і таму я не магу выкарыстоўваць стрэлкі.
Але такога роду рэчы мы можам зрабіць для ўсіх вузлоў.
О, мой Бог.
Гэта 6, 7 і 3.
Тады мы можам стварыць філіялы ў нашым дрэве, мы можам мець 7 -
Мы можам мець, яго левая павінна паказваць на 3.
Так як жа нам гэта зрабіць?
[Студэнты, неразборліва] >> Так. Адрас node3,
і калі ў вас не было адрасы, то ён проста не будзе кампілявацца.
Але памятайце, што гэтыя паказальнікі на наступны вузлоў.
Права павінна ўказваць на 9,
і 3 варта паказаць на права 6.
Я думаю, што гэта ўсё ў парадку. Любыя каментары ці пытанні?
[Студэнт, неразборліва] корань будзе 7.
Мы можам толькі сказаць, вузел * PTR =
або корань = & node7.
>> Для нашых мэтаў, мы будзем мець справу з устаўкай,
так што мы збіраемся хочаце напісаць функцыю, каб ўставіць у гэтую бінарнае дрэва
і ўстаўкі непазбежна будзем называць таНос, каб стварыць новы вузел гэтага дрэва.
Так што ўсё будзе заблытацца з тым, што некаторыя вузлы
У цяперашні час у стэку
і іншыя вузлы збіраюцца ў канчатковым выніку на кучы калі мы ўстаўляем іх.
Гэта цалкам справядліва, але адзіная прычына,
мы ў стане зрабіць гэта ў стэку
Таму што гэта такі надуманы прыклад, што мы ведаем
Дрэва павінна быць пабудавана як 7, 3, 6, 9.
Калі мы гэтага не было, то мы не павінны былі б таНос у першую чаргу.
Як мы ўбачым крыху пазней, мы павінны malloc'ing.
Цяпер гэта цалкам разумна паставіць у стэк,
але давайце зменім гэтую таНос рэалізацыі.
Такім чынам, кожны з іх зараз будзе нешта накшталт
вузел * node9 = таНос (SizeOf (вузла)).
І зараз мы збіраемся трэба зрабіць наш чэк.
калі (node9 == NULL) - я не хачу, -
вяртае 1, а затым мы можам зрабіць node9-> таму што зараз гэта паказальнік,
Значэнне = 6, node9-> налева = NULL,
node9-> Права = NULL,
і мы збіраемся трэба зрабіць, што для кожнага з гэтых вузлоў.
Такім чынам, замест, скажам ўнутры асобнай функцыі.
Давайце назавем гэта вузел * build_node,
і гэта некалькі падобна на API, мы прапануем для кадавання Хафман.
Мы даем вам инициализатор функцый для дрэва
деконструктор і «функцыі» для тых, дрэвы і тое ж самае для лесу.
>> Такім чынам, мы збіраемся мець функцыю ініцыялізацыі
проста пабудаваць вузел для нас.
І гэта будзе выглядаць даволі шмат менавіта так.
І я нават збіраўся быць лянівым і не змяняць імя зменнай,
хоць node9 не мае ніякага сэнсу.
О, я думаю node9 значэнне не павінна было быць 6.
Цяпер мы можам вярнуцца node9.
І тут мы павінны вярнуцца нулявы.
Усе згодныя з гэтым Build-A-вузла функцыю?
Так што цяпер мы можам проста патэлефанаваць, што для стварэння любога вузла з зададзеным значэннем і нулявых паказальнікаў.
Цяпер мы можам выклікаць тым, што мы можам зрабіць вузел * node9 = build_node (9).
І давайце рабіць. . .
6, 3, 7, 6, 3, 7.
І зараз мы хочам стварыць такі ж паказальнікі,
толькі цяпер усё гэта ўжо ў тэрмінах паказальнікаў
так больш не патрэбныя адрасы.
Добра. Так што апошняе, што я хачу зрабіць?
Там у выпраўленне памылак, што я не раблю.
Што пабудаваць вузел наўзамен?
[Студэнт, неразборліва] >> Так. Калі таНос не ўдалося, ён будзе вяртаць NULL.
Так што я збіраюся ляніва паклаў яго сюды, а не рабіць ўмова для кожнага.
Калі (node9 == NULL, або - яшчэ прасцей,
гэта раўнасільна таму, калі толькі не node9.
Так што, калі не node9, ці не node6, ці не node3, ці не node7, вярнуць 1.
Можа быць, мы павінны друкаваць таНос не ўдалося, ці нешта яшчэ.
[Студэнт] ілжывай роўная нулю, а?
[Боуден] Любое нулявое значэнне з'яўляецца ілжывым.
Такім чынам, нулявыя з'яўляецца нулявое значэнне.
Нуль нуль. Ілжывыя з'яўляецца нулявое значэнне.
Любы - у значнай ступені толькі 2 нулявыя значэння не маюць законнай нуля,
ілжывымі толькі хэш вызначаецца як нуль.
Гэта ставіцца і калі мы заяўляем глабальнай зменнай.
Калі б мы мелі каранёвай вузел * тут,
Затым - добрая рэч аб глабальных зменных з'яўляецца тое, што яны заўсёды маюць пачатковае значэнне.
Гэта не праўда функцый, як унутры тут,
калі ў нас ёсць, быццам бы, вузла або вузла * х.
Мы паняцця не маем, што x.value, x.whatever,
ці мы можам раздрукаваць іх, і яны могуць быць адвольнымі.
Гэта не праўда глабальных зменных.
Так каранёвага вузла або вузла х.
Па змаўчанні, усё, што глабальнае, калі відавочна не ініцыялізаваны да некаторага значэння,
мае нулявое значэнне ў якасці значэння.
Дык вось, вузел * корань, мы відавочна не ініцыялізаваць яго ні да чаго,
такім чынам, яго значэнне па змаўчанні будзе нулявым, якая з'яўляецца нулявое значэнне паказальніка.
Па змаўчанні значэнне х будзе азначаць, што x.value роўная нулю,
x.left з'яўляецца несапраўдным, і x.right з'яўляецца несапраўдным.
Такім чынам, так як ён з'яўляецца структурай, усе палі структуры будуць роўныя нулю значэнняў.
Мы не павінны выкарыстоўваць што тут, аднак.
[Студэнт] структуры адрозніваюцца ад іншых зменных, і іншыя зменныя
смецце каштоўнасцяў; гэтыя нулі?
[Боуден] Іншыя значэння таксама. Такім чынам, у х, х будзе роўная нулю.
Калі гэта ў глабальнай вобласці, яна мае першапачатковае значэнне. >> Добра.
[Боуден] Альбо пачатковае значэнне вы далі яго ці роўныя нулю.
Я думаю, што бярэ на сябе ўсё гэта.
>> Добра. Так што ў наступны частцы пытання пытаецца,
"Зараз мы хочам напісаць функцыю, называецца змяшчае
з прататыпам BOOL ўтрымлівае цэлалікавых значэнне ".
Мы не збіраемся рабіць BOOL ўтрымлівае цэлалікавых значэнне.
Наш прататып будзе выглядаць
BOOL ўтрымоўвае (цэлалікавых значэнне.
І тады мы таксама збіраемся перадаць яго дрэва
што яна павінна быць праверка, каб убачыць, калі яна мае гэта значэнне.
Такім чынам, вузел * дрэва). Добра.
І тады мы можам назваць гэта чымсьці накшталт,
можа быць, мы хочам Printf ці чамусьці.
Змяшчае 6, наш корань.
Гэта павінна вярнуць адзін або праўда,
у той час як утрымоўвае 5 корань павінен вярнуцца ілжывым.
Так што бярыце другая для рэалізацыі гэтага.
Вы можаце зрабіць гэта альбо итерационно або рэкурсіўна.
Добрая рэч аб тым, як мы ўсталявалі рэчаў з'яўляецца тое, што
яна даецца нам рэкурсіўнае рашэнне значна прасцей
чым глабальная пераменная шляху і зрабілі.
Таму што, калі мы проста ўтрымлівае цэлалікавых значэнне, то няма ніякага спосабу рэкурсіі ўніз поддеревьев.
Мы павінны былі б мець асобную дапаможную функцыю, якая рэкурсіўна ўніз поддеревья для нас.
Але так як мы змянілі яго ўзяць дрэва ў якасці аргументу,
якія ён павінен заўсёды былі на першым месцы,
Цяпер мы можам рэкурсіўна больш лёгка.
Такім чынам, итерационный або рэкурсіўны, мы пойдзем на абодвух,
але мы ўбачым, што рэкурсіўнага заканчвае тым, што даволі лёгка.
Добра. Хто-небудзь ёсць нешта, што мы можам працаваць з?
>> [Студэнт] У мяне ёсць рашэнне итеративным. >> Добра, итерационные.
Добра, гэта добра выглядае.
Так што, хочаце ісці з намі праз гэта?
[Студэнт] Вядома. Таму я часовую зменную, каб атрымаць першы вузел дрэва.
А потым я проста петельная праз час тэмпература не роўная нулю,
так што пакуль усё яшчэ быў у дрэва, я думаю.
І калі значэнне роўна значэнню, тэмпература паказвае на,
Затым ён вяртае гэта значэнне.
У адваротным выпадку, ён правярае, калі ён знаходзіцца на правай баку або да левай баку.
Калі вы калі-небудзь сітуацыя, калі няма больш дрэў,
Затым ён вяртаецца - ён выходзіць з цыклу і вяртае хлусня.
[Боуден] Добра. Так што здаецца добрым.
Любы, ёсць якія-небудзь каментары на што-небудзь?
У мяне няма карэктнасці каментарыяў наогул.
Адзінае, што мы можам зрабіць гэта за хлопец.
О, ён збіраецца пайсці крыху даўгаваты.
Я палатаю, што да. Добра.
>> Кожны павінен памятаць, як патройны працуе.
Там пэўна былі тэсты ў мінулым
, Якія даюць вам функцыі з патройны аператар,
і кажуць, перавесці гэта, рабіць тое, што не выкарыстоўваецца патройны.
Так што гэта вельмі распаўсюджаны выпадак, калі я думаў выкарыстоўваць патройныя,
дзе, калі некаторыя ўмовы ўсталяваць пераменную на нешта,
яшчэ ўстанавіць, што ж зменную на нешта іншае.
Гэта тое, што вельмі часта можа быць ператворана ў такога роду рэчы
, Дзе ўстаноўлена, што пераменная гэта - ці, ну, гэта праўда? Тады гэта, інакш гэта.
[Студэнт] Першая калі гэта праўда, ці не так?
[Боуден] Так. Тое, як я заўсёды чытаў гэта, тэмп роўна значэнне большае, чым часовы значэнне,
то гэта, інакш гэта. Ён задае пытанне.
Гэта больш? Тады зрабіце першы крок. Астатняе робяць другое.
Я амаль заўсёды - тоўстую кішку, я проста - у мяне ў галаве, я чытаў, як астатнія.
>> Хто-небудзь ёсць рэкурсіўнае рашэнне?
Добра. Гэта той, які мы збіраемся - гэта ўжо можа быць вялікім,
але мы збіраемся зрабіць яго яшчэ лепш.
Гэта ў значнай ступені сапраўды такі жа ідэяй.
Гэта проста, ну, ты хочаш растлумачыць?
[Студэнт] Вядома. Такім чынам, мы пераканайцеся, што дрэва не з'яўляецца нулявым першым,
таму што, калі дрэва з'яўляецца нулявым, тады яна збіраецца вярнуцца ілжывым, таму што мы не знайшлі яго.
І калі ёсць яшчэ дрэва, ідзем у - мы спачатку правяраем, калі значэнне бягучага вузла.
Вярнуцца дакладна, калі яна ёсць, і калі не мы рэкурсіўна злева ці справа.
Гучыць ці гэта неабходна? >> Угу. (Пагадненне)
Так заўважыць, што гэта амаль - канструктыўна вельмі падобныя на итерационном рашэнні.
Гэта проста, што замест рэкурсіі, у нас быў час цыклу.
І справа тут базу, дзе дрэў не роўна NULL
было ўмова, пры якім мы вырваліся з цыклу.
Яны вельмі падобныя. Але мы збіраемся зрабіць яшчэ адзін крок наперад.
Цяпер мы робім тое ж самае і тут.
Звярніце ўвагу, мы вяртаемся адно і тое ж у абодвух гэтых радкоў,
за выключэннем аднаго аргументу іншы.
Так што мы збіраемся зрабіць гэта ў трайным.
Я ўдарыў варыянт нешта, і ён зрабіў сімвалам. Добра.
Так што мы збіраемся вярнуцца ўтрымлівае гэтым.
Гэта становіцца быць некалькі радкоў, а, павялічанай у гэтым ёсць.
Як правіла, у якасці стылістычнага рэч, я не думаю, што многія людзі
паставіць прабел пасля стрэлкі, але я думаю, калі вы паслядоўныя, гэта выдатна.
Калі значэнне менш, чым значэнне дрэва, мы хочам, каб рэкурсіўна па дрэве злева,
яшчэ мы хочам, каб рэкурсіўна па дрэве права.
Так што было крокам адным з рашэнняў гэтай выглядаць менш.
Другі крок зрабіць гэты выгляд менш -
мы можам падзяліць гэта на некалькі радкоў.
Добра. Крок 2 робячы яго падобным менш тут,
так што вяртаецца значэнне роўна дрэва значэнне, або змяшчае заўгодна.
>> Гэта важная рэч.
Я не ўпэўнены, калі б ён сказаў, што гэта ў відавочным выглядзе ў класе,
але гэта называецца кароткае замыканне ацэнкі.
Ідэя тут складаецца значэнне == дрэва значэнне.
Калі гэта праўда, то гэта сапраўды так, і мы хочам »ці« што з тым, што ёсць тут.
Такім чынам, нават не думаючы пра ўсё, што знаходзіцца тут,
што ўсе выраз збіраецца вярнуцца?
[Студэнт] True? >> Так, таму што сапраўднае нічога,
злучаныя праз АБО - ці праўдзівы злучаныя праз АБО з чым абавязкова дакладна.
Таму, як толькі мы бачым, вяртаецца значэнне = Дрэва значэнне,
мы толькі збіраемся вярнуцца дакладна.
Нават не збіраюся рэкурсіўна дадаткова змяшчае па лініі.
Мы можам прыняць гэта яшчэ адзін крок наперад.
Вярнуцца дрэва не роўная NULL і ўсё гэта.
Ён зрабіў гэта адзін радок функцыі.
Гэта таксама прыклад кароткага замыкання ацэнкі.
Але цяпер гэта тая ж самая ідэя -
замест таго, каб - так, калі дрэва не роўна NULL - або, ну,
калі дрэва мае роўныя нулю, што з'яўляецца дрэнны выпадак,
калі дрэва роўная нулю, то першае ўмова будзе ілжывым.
Так ілжывая аперацыя AND з чым будзе што?
[Студэнт] False. >> Так. Гэта іншая палова кароткага замыкання ацэнкі,
дзе, калі дрэва не роўныя нулю, то мы не збіраемся нават пайсці -
або калі дрэва мае роўныя нулю, то мы не збіраемся рабіць значэнне == дрэва значэнне.
Мы проста збіраемся, каб неадкладна вярнуцца ілжывым.
Што важна, так як калі гэта не кароткае замыканне ацэнкі,
затым, калі дрэва мае роўныя нулю, гэта другая ўмова будзе віне сегмента,
таму што дрэва-> значэнне разнаймення NULL.
Дык вось што. Ці можаце зрабіць гэта - перайсці разы старэй.
Гэта вельмі звычайная рэч, таксама, не робіць гэта адзін адпаведнасці з гэтым,
але гэта звычайная справа ва ўмовах, можа быць, не прама тут,
але калі (дерево! = NULL, і дрэва-> значэнне == значэнне), рабіць што заўгодна.
Гэта вельмі распаўсюджанае захворванне, дзе замест таго,
разарваць яе на дзве IFS, дзе заўгодна, гэта дрэва нуль?
Добра, гэта не нулявы, так што зараз гэта дрэва значэння, роўнага кошту? Зрабіце гэта.
Замест гэтага стану, гэтага ніколі не будзе сегментах віна
таму што ён вырвецца вонкі, калі гэта адбудзецца, з'яўляюцца несапраўднымі.
Ну, я думаю, калі ваша дрэва зусім няправільны паказальнік, ён усё яшчэ можа сегментах віна,
але яна не можа сегментах віна, калі дрэва з'яўляецца несапраўдным.
Калі б гэта быў нулявым, гэта парушыла б перш, чым вы калі-небудзь разыменован паказальнік на першае месца.
[Студэнт] Гэта званых лянівых ацэнкі?
>> [Боуден] Гультаяватыя вылічэнні асобная рэч.
Гультаяватыя вылічэнні больш, як вы просіце значэнне,
Вы спытаеце для вылічэння значэння, свайго роду, але вы не павінны яго неадкладна.
Так што, пакуль вы на самой справе трэба, яно не вылічаецца.
Гэта не зусім тое ж самае, але ў Хафман PSET,
ён кажа, што мы "ляніва" пісаць.
Таму мы робім гэта таму, што мы на самай справе буферызацыі запісу -
Мы не хочам, каб напісаць асобныя біты у той час,
або асобных байтаў за раз, замест гэтага мы хочам атрымаць кавалак байт.
Затым, калі ў нас ёсць кавалак байт, то мы будзем яго выпісваць.
Нават калі вы папытаеце яго напісаць - і FWRITE і FREAD зрабіць такую ​​ж рэч.
Яны буфер вашага чытання і запісы.
Нават калі вы папытаеце яго напісаць адразу, ён, верагодна, не будзе.
І вы не можаце быць упэўнены, што рэчы будуць напісаны
да выкліку hfclose або што гэта такое,
якія потым кажа, добра, я заплюшчваю свой файл,
гэта азначае, што мне лепш напісаць усё, што я яшчэ не напісана.
Гэта не трэба пісаць усё з
пакуль вы не зачыняеце файл, а затым гэта неабходна.
Так што гэта менавіта тое, што лянота - ён чакае, пакуль гэта павінна адбыцца.
Гэта - узяць 51 і вы будзеце ўваходзіць у яго больш падрабязна,
таму што OCaml і ўсё ў 51, ​​усё рэкурсіі.
Ёсць ніякіх итерационного рашэнні, у асноўным.
Усе рэкурсіі і лянівыя вылічэнні
будзе важным для многіх абставінаў
дзе, калі не ляніва ацэнку, гэта будзе азначаць -
Прыкладам з'яўляецца патокаў, якія з'яўляюцца бясконца доўга.
У тэорыі, вы можаце думаць аб натуральных лікаў у выглядзе патоку 1-2-3-4-5-6-7,
Так ляніва ацэньваць рэчы ў парадку.
Калі я кажу, я хачу 10. ліку, то я магу ацаніць да дзясятага чысла.
Калі я хачу ў соты нумар, то я магу ацаніць да 100. Нумары.
Без лянівых вылічэнняў, то ён будзе спрабаваць ацаніць ўсе нумары адразу.
Ты ацэнцы бясконца шмат лікаў, і гэта проста не магчыма.
Такім чынам, ёсць шмат выпадкаў, калі гультаяватыя вылічэнні
проста неабходна для атрымання рэчаў на працу.
>> Цяпер мы хочам напісаць ўстаўку, дзе ўстаўка будзе
Аналагічна змены ў яго вызначэнні.
Так што цяпер гэта BOOL ўстаўкі (цэлалікавых значэнне).
Мы збіраемся змяніць гэта BOOL ўстаўкі (цэлалікавых значэнне, вузел * дрэва).
Мы сапраўды збіраемся змяніць гэта зноў у трохі, мы ўбачым, чаму.
І давайце пяройдзем build_node, проста дзеля гэтага,
ўставіць вышэй, таму мы не павінны напісаць прататып функцыі.
Якія гэта намёк, што вы збіраецеся выкарыстоўваць build_node у ўстаўкі.
Добра. Спыніцеся на хвілінку за гэта.
Я думаю, што я выратаваў рэдакцыі, калі вы хочаце, каб выцягнуць з гэтага,
або, па крайняй меры, я зрабіў цяпер.
Я хацела невялікі перапынак, каб думаць пра логіцы ўстаўкі,
калі вы не можаце думаць пра гэта.
У прынцыпе, вы толькі калі-небудзь ўстаўкі на лісці.
Маўляў, калі я ўстаўляю 1, то я непазбежна будзе ўстаўка 1 -
Я змяню ў чорным - I'll быць ўстаўка 1 на тут.
Ці, калі я ўстаўляю 4, я хачу, каб ўстаўка 4 над тут.
Так што не мае значэння, што вы робіце, вы будзеце ўстаўкі на ліст.
Усё, што вам трэба зрабіць, гэта ітэрацыі ўніз па дрэве, пакуль не дойдзе да вузла
, Якія павінны быць бацькам вузла, бацька новага вузла,
, А затым змяніць яе налева або направа, паказальнік, у залежнасці ад таго,
гэта больш ці менш бягучага вузла.
Змяніць гэты паказальнік, каб паказаць на новы вузел.
Такім чынам, ітэрацыі па дрэве, зрабіць канчатковы пункт новага вузла.
Акрамя таго, думаю аб тым, чаму, які забараняе тып сітуацыі і раней,
дзе я пабудаваў двайковага дрэва, дзе гэта было правільна
калі вы глядзелі толькі на адным вузле,
але 9 быў злева ад 7, калі вы паўторных ўніз да ўпора.
Так, што гэта немагчыма ў гэтай сітуацыі, так як -
думаю аб усталёўцы 9 або нешта; на самым першым вузле,
Я збіраюся глядзець 7, і я проста збіраюся ісці з правага боку.
Так што не мае значэння, што мне рабіць, калі я ўстаўка, перайшоўшы на ліст,
і лісце дапамогай адпаведнага алгарытму,
гэта будзе для мяне немагчыма ўставіць 9 да левага з 7
таму што як толькі я трапіў 7 я пайду направа.
Хто-небудзь ёсць нешта пачаць?
[Студэнт] я раблю. >> Вядома.
[Студэнт, неразборліва]
[Іншы студэнт, неразборліва]
[Боуден] Гэта цэніцца. Добра. Хочаце растлумачыць?
>> [Студэнт] Паколькі мы ведаем, што мы ўстаўка
новыя вузлы ў канцы дрэва,
Я пятлю па дрэве итеративно
пакуль я не дабраўся да вузла, які паказаў на нуль.
І тады я вырашыў паставіць яго альбо на правай, альбо з левага боку
выкарыстанне гэтага права зменная, яна сказала мне, куды яго пакласці.
І тады, па сутнасці, я толькі што зрабіў, што ў мінулым -
гэтага пункту тэмпература вузла на новы вузел, які ён стварае,
альбо на левай баку або на правай баку, у залежнасці ад таго, што значэнне мае рацыю быў.
Нарэшце, я ўсталяваў новае значэнне вузла да кошту яго тэставанне.
[Боуден] Такім чынам, я бачу адно пытанне тут.
Гэта як 95% шляху.
Адно пытанне, які я бачу, ну, хто-небудзь яшчэ бачыў праблемы?
Што такое акалічнасць, пры якіх яны вырвацца з пятлі?
[Студэнт] Калі тэмпература з'яўляецца несапраўдным? >> Так. Такім чынам, як вы вырвацца з пятлі, калі тэмпература з'яўляецца несапраўдным.
Але тое, што я раблю тут?
Я разнаймення тэмпература, якая непазбежна нулявы.
Такім чынам, іншыя, што вам трэба зрабіць, гэта не проста адсочваць, пакуль тэмпература пусты,
Вы хочаце, каб сачыць за бацькоў ва ўсе часы.
Мы таксама хочам бацькоўскі вузел *, я думаю, мы можам захаваць, што пры нулявых на першы погляд.
Гэта будзе мець дзіўныя паводзіны для кораня дрэва,
але мы вернемся да гэтага.
Калі значэнне больш, чым любы іншы, то Temp = Тэмпература права.
Але перш чым мы гэта зробім, бацька = тэмп.
Ці бацькі заўсёды будуць роўныя тэмпературы? Ці так гэта?
Калі тэмпература не з'яўляецца нулявым, то я буду рухацца ўніз, нягледзячы ні на што,
да вузла, для якога часовы бацькоў.
Такім чынам, бацька гэта будзе часовы, а потым рухацца тэмп ўніз.
Зараз тэмпература з'яўляецца сапраўдным, але бацька паказвае на аднаго з бацькоў тое, што з'яўляецца нулявым.
Так што тут, я не хачу, каб усталяваць права роўная 1.
Так я пераехаў у правую, так што калі правы = 1,
і я думаю, вы таксама хочаце рабіць -
калі рухацца налева, вы хочаце ўсталяваць правы роўныя 0.
Або жа, калі вы калі-небудзь рухацца направа.
Такім чынам, права = 0. Калі права = 1,
Цяпер мы хочам, каб бацькі права newnode паказальнік,
яшчэ мы хочам, каб бацькі левай newnode паказальнік.
Пытанняў з гэтай нагоды?
Добра. Такім чынам, гэта тое, як мы - ну, на самай справе, а не рабіць гэтага,
Мы амаль чакаў выкарыстоўваць build_node.
І потым, калі newnode роўная нулю, вярнуцца ілжывым.
Вось і ўсё. Зараз, гэта тое, што мы чакалі, што вы робіце.
>> Гэта тое, што супрацоўнікі рашэнняў робяць.
Я не згодны з гэтым, як "правільны" спосаб ісці аб ім
Але гэта выдатна, і яна будзе працаваць.
Адзінае, што крыху дзіўна прама цяпер
калі дрэва пачынаецца як нулявыя, мы перадаем у нулявое дрэва.
Я думаю, гэта залежыць ад таго, як вызначаць паводзіны якія праходзяць у нулявых дрэва.
Я думаю, што калі вы праходзіце ў нулявое дрэва,
затым ўставіць значэнне ў нулявы дрэва
трэба проста вярнуць дрэва, дзе адзіная каштоўнасць у тым, што адзін вузел.
У людзей з гэтым згодны? Вы маглі б, калі б вы хацелі,
калі вы праходзіце ў нулявое дрэва
і вы хочаце ўставіць значэнне ў ёй, вярнуцца ілжывым.
Гэта да вас, каб вызначыць, што.
Для гэтага першае, што я сказаў, а потым -
добра, вы будзеце мець праблемы робяць гэта, таму што
было б лягчэй, калі б мы мелі глабальны паказальнік на рэч,
але ў нас няма, так што калі дрэва з'яўляецца нулявым, то мы нічога не можам з гэтым зрабіць.
Мы можам проста вярнуцца ілжывым.
Так што я збіраюся змяніць ўстаўкі.
Мы тэхнічна мог бы проста змяніць гэта прама тут,
як гэта ітэрацыі рэчы,
але я збіраюся змяніць ўстаўкі прыняць вузла ** дрэва.
Двухмесны паказальнікаў.
Што гэта значыць?
Замест таго, каб мець справу з паказальнікамі на вузлы,
што я збіраюся быць маніпулявання гэта паказальнік.
Я збіраюся быць маніпулявання гэты паказальнік.
Я збіраюся быць маніпуляцый паказальнікамі напрамую.
Гэта мае сэнс, так як, думаю пра ўніз -
Ну, цяпер гэта паказвае на нуль.
Тое, што я хачу зрабіць, гэта кіраваць гэтай паказальнік, каб паказаць на не нулявы.
Я хачу, каб яна паказвала на маім новым вузле.
Калі б я проста сачыць за паказальнікамі на мой паказальнікаў,
то мне не трэба сачыць за продка.
Я магу толькі сачыць, каб пераканацца, што паказальнік накіраваны да нуля,
і калі паказальнік паказвае на нуль,
змяніць яго, каб паказаць на вузел я хачу.
І я магу змяніць яго, так як у мяне ёсць паказальнік на паказальнік.
Давайце паглядзім гэта прама цяпер.
Вы сапраўды можаце зрабіць гэта рэкурсіўна даволі лёгка.
Хочам Ці мы гэта зрабіць?
Так, мы робім.
>> Давайце паглядзім, што рэкурсіўна.
Па-першае, тое, што наш базавы сцэнар будзе?
Амаль заўсёды наш базавы сцэнар, але на самой справе, гэта накшталт складана.
Перш-наперш, калі (дрэва == NULL)
Я думаю, мы проста збіраемся, каб вярнуцца ілжывым.
Гэта адрозніваецца ад вашага дрэва быць нулявым.
Гэта паказальнік на каранёвай паказальнік быць нулявым
Гэта азначае, што ваш каранёвай паказальнік не існуе.
Так што тут, калі я раблю
вузел * - давайце проста паўторна выкарыстоўваць гэты.
Node * корань = NULL,
і тады я буду называць ўстаўкі, робячы нешта накшталт,
ўстаўце 4 і ў корані.
Так і кораня, калі корань вузел *
то і корань будзе вузлом. **
Гэта справядліва. У гэтым выпадку, дрэва, тут,
Дрэва не пусты - ці ўстаўкі.
Тут. Дрэва не з'яўляецца нулявым; * Дрэва з'яўляецца несапраўдным, і гэта добра
таму што, калі * Дрэва з'яўляецца нулявым, то я магу кіраваць ім
у цяперашні час паказваюць на тое, што я хачу, каб гэта паказваюць.
Але калі дрэва з'яўляецца пустым, гэта азначае, што я толькі што прыйшоў сюды і сказаў, нулявы.
Гэта не мае сэнсу. Я нічога не магу зрабіць з гэтым.
Калі дрэва з'яўляецца пустым, вярнуцца ілжывым.
Так што я ў прынцыпе ўжо казаў, што нашы рэальныя справы базы.
І што гэта будзе?
[Студэнт, неразборліва]
[Боуден] Так. Так што, калі (* дрэва == NULL).
Гэта ставіцца да выпадку тут
дзе, калі мой чырвоны паказальнік з'яўляецца паказальнікам я засяроджаны на,
так як я засяроджаны на гэты паказальнік, зараз я засяроджаны на гэты паказальнік.
Зараз я засяроджаны на гэты паказальнік.
Так што, калі мой чырвоны паказальнік, які з'яўляецца маім ** вузла,
гэта ўсё - калі *, мая чырвоная стрэлка, гэта ніколі не нулявы,
гэта азначае, што я знаходжуся ў тым выпадку, калі я засяроджаны на паказальнік, які паказвае -
гэта паказальнік, які належыць ліста.
Я хачу змяніць гэты паказальнік, каб паказаць на маім новым вузле.
Прыходзьце сюды.
Мой newnode будзе проста вузел * п = build_node (кошт)
Затым п, калі п = NULL, вяртае хлусня.
Астатняе мы хочам змяніць тое, што паказальнік ў дадзены момант паказвае
у цяперашні час паказваюць на нашым новым вузле.
Мы можам рэальна зрабіць гэта тут.
Замест таго каб сказаць я, мы гаворым * = дрэва, калі дрэва *.
Усе разумеюць, што? Гэта, маючы справу з паказальнікамі на паказальнікі,
мы можам змяніць нулявыя паказальнікі паказваюць на тое, што мы хочам, каб яны паказваюць.
Гэта наш базавы сцэнар.
>> Цяпер нашы рэцыдыву, або наш рэкурсіі,
будзе вельмі падобны на ўсе іншыя рэкурсіі мы рабілі.
Мы збіраемся хочаце ўставіць значэнне,
і цяпер я збіраюся выкарыстоўваць патройныя зноў, але тое, што наша ўмова будзе?
Што гэта мы шукаем вырашыць, ці жадаем мы ісці налева або направа?
Давайце рабіць гэта ў асобных крокаў.
Калі (значэнне <) што?
[Студэнт] Значэнне дрэва?
[Боуден] Таму памятайце, што я ў цяперашні час -
[Студэнты, неразборліва]
[Боуден] Так, так прама тут, скажам, што гэтая зялёная стрэлка
з'яўляецца прыкладам таго, што дрэва ў цяперашні час, з'яўляецца паказальнікам на гэты паказальнік.
Такім чынам, гэта азначае, што я паказальнік на паказальнік да 3.
Разнаймення двойчы гучала добра.
Што мне - як я магу гэта зрабіць?
[Студэнт] Dereference адзін раз, а затым зрабіць стрэлкі такім чынам?
[Боуден] Такім чынам, (* дрэва) з'яўляецца разнаймення адзін раз, -> значэнне
збіраецца даць мне значэнне вузла, што я ўскосна паказвае.
Так што я таксама магу пісаць ** tree.value, калі вы аддаеце перавагу гэта.
Альбо працуе.
Калі гэта так, то я хачу звярнуць ўставіць са значэннем.
І тое, што мой абноўлены вузел ** будзе?
Я хачу пайсці налева, так ** tree.left будзе злева ад мяне.
І я хачу, паказальнік на гэтую рэч
так што калі левая заканчвае тым, што нулявы паказальнік,
Я магу змяніць яго, каб паказаць на маім новым вузле.
>> І ў іншым выпадку могуць быць вельмі падобныя.
Давайце рэальна зрабіць, што мой патройны прама цяпер.
Устаўце значэнне, калі значэнне <(** дрэва). Значэнне.
Затым мы хочам абнавіць нашу ** налева,
яшчэ мы хочам абнавіць нашу ** направа.
[Студэнт] Ці гэта, што атрымаць паказальнік на паказальнік?
[Боуден] Памятаеце, што - ** tree.right з'яўляецца вузлом зоркі.
[Студэнт, неразборліва] >> Так.
** Tree.right, як гэты паказальнік ці чамусьці.
Такім чынам, прымаючы паказальнік на тым, што гэта дае мне тое, што я хачу
паказальніка на гэтага хлопца.
[Студэнт] Ці можам мы пайсці зноў, чаму мы выкарыстоўваем два паказальнікі?
[Боуден] Так. Так што - не, вы можаце, і гэта рашэнне да
быў спосаб зрабіць гэта, не робячы двух паказальнікаў.
Вы павінны быць у стане зразумець з дапамогай двух паказальнікаў,
і гэта чыстае рашэнне.
Акрамя таго, заўважыў, што тое, што адбываецца, калі маё дрэва -
Што адбудзецца, калі мой корань быў нулявым? Што адбудзецца, калі я зраблю гэта выпадак прама тут?
Такім чынам, вузел * корань = NULL, устаўце 4 і ў корані.
Тое, што корань будзе пасля гэтага?
[Студэнт, неразборліва] >> Так.
Каранёвая значэнне будзе 4.
Каранёвая левага будзе нулявым, корань права будзе нулявы.
У выпадку, калі мы не прайшлі корань па адрасе,
мы не маглі змяніць корань.
У выпадку, калі дрэва - дзе корань быў нулявым,
мы проста павінны былі вярнуцца ілжывым. Там няма нічога, што мы маглі зрабіць.
Мы не можам ўставіць вузел у пустое дрэва.
Але цяпер мы можам, мы проста зрабіць пустое дрэва ў адной вузла дрэва.
Якая звычайна чаканым чынам, што яно павінна працаваць.
>> Акрамя таго, гэта значна менш, чым
Таксама сачыць за бацькамі, і таму вы ітэрацыі да ўпора.
Цяпер у мяне ёсць мае бацькі, і я проста мае бацькі права паказальнік на што заўгодна.
Замест гэтага, калі б мы рабілі гэта ў шмат разоў, гэта было б тое ж ідэю з цыклу.
Але замест таго, каб мець справу з маімі бацькамі паказальнік,
Замест майго бягучага паказальніка бы рэч
што я наўпрост змяняць, каб паказаць на маім новым вузле.
Я не прыходзіцца мець справу з таго, што гэта паказвае на левым.
Я не прыходзіцца мець справу з таго, што гэта паказвае на права.
Гэта проста, што гэты паказальнік, я збіраюся ўсталяваць яго, каб паказаць на маім новым вузле.
Усе разумеюць, як гэта працуе?
Калі няма, то чаму мы хочам зрабіць гэта такім чынам,
але па крайняй меры, што гэта працуе як рашэнне?
[Студэнт] Куды мы вяртаемся праўда?
[Боуден] Гэта, напэўна, прама тут.
Калі мы правільна ўставіць яго, вярнуць праўдзівы.
У адваротным выпадку, тут мы збіраемся жадаеце вярнуць усё вяртаецца ўстаўкі.
>> А што асаблівага ў гэтай рэкурсіўнай функцыі?
Гэта хвост рэкурсіўнай, бо пакуль мы складаем з некаторай аптымізацыі,
яна будзе прызнаць, што і вы ніколі не атрымаеце перапаўненне стэка з гэтага,
нават калі наша дрэва мае вышыню 10.000 або 10 мільёнаў.
[Студэнт, неразборліва]
[Боуден] Я думаю, што ён гэта робіць на Dash - ці тое, што ўзровень аптымізацыі
патрабуецца для хваставой рэкурсіі каб быць прызнаным.
Я думаю, што ён прызнае - GCC і Clang
Таксама маюць розныя значэнні для іх ўзроўню аптымізацыі.
Я хачу сказаць, што гэта Дашо 2, пераканацца, што ён не прызнае хваставой рэкурсіі.
Але мы - вы можаце пабудаваць, як напрыклад Fibonocci ці чамусьці.
Гэта не лёгка праверыць з гэтым, таму што гэта цяжка пабудаваць
бінарнае дрэва, што такі вялікі.
Але так, я думаю, што гэта Дашо 2,
Калі вы компилируете з Дашо 2, ён будзе шукаць хваставую рэкурсіі
і аптымізаваць гэта.
Давайце вернемся да - уставіць літаральна апошнім, што яму трэба.
Давайце вернемся да ўстаўкі тут
дзе мы збіраемся рабіць тую ж ідэю.
Ён усё яшчэ будзеце мець недахоп не ў стане цалкам справіцца
калі сам корань з'яўляецца пустым, ці мінулае ўступлення пусты,
але замест таго каб справіцца з адным з бацькоў паказальнік,
Давайце ўжыць тую ж логіку захоўвання паказальнікаў на паказальнікі.
Калі пры гэтым мы працягваем наш вузел ** з актуальн.,
і нам не трэба сачыць за права больш,
але вузле ** = з актуальн. і дрэва.
І зараз наша ў той час як цыкл будзе час * току не роўная нулю.
Не трэба сачыць за бацькоў больш.
Не трэба сачыць за левую і правую.
І я буду называць яго тэмп, таму што мы ўжо выкарыстоўвае тэмп.
Добра. Так што, калі (значэнне> * тэмпература),
то і (* тэмпература) -> Права
яшчэ Temp = & (* тэмпература) -> сышоў.
І цяпер, у дадзены момант, пасля гэтага час цыклу,
Я толькі раблю гэта таму, можа быць, лягчэй думаць пра што шматкроць рэкурсіўна,
але пасля гэтага час цыклу,
* Часовы паказальнік мы хочам змяніць.
>> Перш, чым мы мелі бацькоў, і мы хацелі б змяніць або левай бацькоў або аднаго з бацькоў права,
Але калі мы хочам змяніць бацькоўскі правоў,
Затым * часовы бацькі маюць рацыю, і мы можам змяніць яго непасрэдна.
Так што тут, унізе, мы можам зрабіць * Temp = newnode, вось і ўсё.
Такім чынам, апавяшчэнне, усё, што мы зрабілі ў гэтым было вывезці радкоў кода.
Для таго, каб сачыць за бацькоў ва ўсім, што дадатковыя намаганні.
Пры гэтым, калі мы проста сачыць за паказальнікам на паказальнік,
і нават калі б мы хацелі, каб пазбавіцца ад усіх гэтых фігурныя дужкі зараз,
зрабіць яго карацей.
Гэта цяпер сапраўды такі жа раствор,
але менш радкоў кода.
Як толькі вы пачынаеце прызнаючы гэта як правільнае рашэнне,
гэта таксама лягчэй разважаць пра што, як, у парадку,
чаму я павінен гэтым сцягам на Int дакладна?
Што гэта значыць? О, гэта азначала, што
кожны раз, калі я іду маюць рацыю, мне трэба, каб усталяваць яго,
яшчэ, калі я іду пакінуў мне трэба ўсталяваць яго да нуля.
Вось, у мяне няма прычын, каб пра гэта, гэта проста лягчэй думаць.
Пытанні?
[Студэнт, неразборліва] >> Так.
Такім чынам, у апошні біт -
Я думаю, адна хуткі і просты функцыі мы можам зрабіць, гэта,
let's - разам, я думаю, паспрабаваць і напісаць функцыю, змяшчае
які не клапоціцца, ці з'яўляецца гэта бінарнае дрэва пошуку.
У ім утрымліваецца функцыя павінна вяртаць сапраўдным
калі дзе-небудзь у гэтым агульным бінарнае дрэва з'яўляецца значэнне, якое мы шукаем.
Так давайце рабіць гэта рэкурсіўна, і тады мы будзем рабіць гэта паўторна.
Мы можам на самай справе проста рабіць гэта разам, таму што гэта будзе вельмі кароткім.
>> Тое, што мой базавы варыянт будзе?
[Студэнт, неразборліва]
[Боуден] Так што, калі (дрэва == NULL), то што?
[Студэнт] Вярнуцца ілжывым.
[Боуден] астатняе, ну, мне не трэба іншага.
Калі быў маім сябрам выпадку база.
[Студэнт] Дрэва значэнне? >> Так.
Так што, калі (дрэва-> значэнне == значэнне.
Звярніце ўвагу, што мы вярнуліся да вузла *, а не вузла ** ы?
Утрымоўвае ніколі не трэба будзе выкарыстоўваць вузел **
так як мы не змяняны паказальнікаў.
Мы проста праз іх.
Калі гэта адбудзецца, то мы хочам вярнуць праўдзівы.
Астатняе мы хочам, каб перасекчы дзяцей.
Таму мы не можам разважаць пра тое, каб усё засталося менш
і ўсё, што правей больш.
Так што ж наш стан будзе тут - ці, што мы будзем рабіць?
[Студэнт, неразборліва] >> Так.
Вярнуцца змяшчае (значэнне, дрэва-> злева)
ці ўтрымоўвае (значэнне, дрэва-> справа). І гэта ўсё.
І звярніце ўвагу, ёсць некаторы кароткае замыканне ацэнкі,
дзе, калі мы, здараецца, знаходзіць сэнс у левым дрэве,
Мы ніколі не павінны глядзець на правым дрэве.
Гэта цэлая функцыя.
Зараз давайце рабіць гэта шматкроць,
які будзе менш прыемна.
Мы возьмем звычайную пачатку вузла * з актуальн. = Дрэва.
У той час (з актуальн! = NULL).
Хутка збіраемся бачу праблемы.
Калі з актуальн. - Тут, калі мы калі-небудзь вырвацца з гэтага,
Затым мы запускаем з рэчаў, каб глядзець на, так што вярнуцца ілжывым.
Калі (у цяперашні> значэнне == значэнне), вярнуцца дакладна.
Такім чынам, зараз мы знаходзімся на месцы -
Мы не ведаем, ці жадаем мы, каб пайсці налева або направа.
Такім чынам, адвольна, давайце проста пайсці налева.
Я, відавочна, сутыкнуліся з пытаннем, дзе я цалкам адмовілася ад усяго -
Я толькі калі-небудзь праверыць левай баку дрэва.
Я ніколі не буду праверыць усё, што права дзіцяці на ўсё.
Як я магу гэта выправіць?
[Студэнт] Вы павінны сачыць за левы і правы ў стэку.
[Боуден] Так. Так давайце зробім гэта
Структура спісу вузлоў * N, а затым вузел ** далей?
Я думаю, што выдатна працуе.
Мы хочам ісці па левай ці let's - тут.
Struct = спіс спіс, ён пачне
пры гэтым структура спісу.
* Спіс = NULL. Так што гэта будзе наш звязанага спісу
поддеревьев, якія мы прапусцілі.
Мы збіраемся прайсці засталося,
але так як мы непазбежна павінны вярнуцца да права,
Мы збіраемся трымаць у правай частцы ўнутры нашай структуры спісу.
Тады мы будзем мець new_list або структуры,
Структура спісу *, new_list = таНос (SizeOf (спіс)).
Я збіраюся ігнараваць праверкі памылак, але вы павінны праверыць, калі гэта нулявы.
New_list вузла гэта будзе ўказваць на -
Ах, вось чаму я хацеў яго тут. Гэта будзе паказваць на другі спіс структуру.
Вось толькі як звязаныя спісы работ.
Гэта тое ж самае, як Int звязаны спіс
акрамя мы проста замяніўшы Int з вузлом *.
Гэта сапраўды гэтак жа.
Так new_list, кошт нашых new_list вузла,
будзе ток> правы.
Каштоўнасць нашага new_list-> наступны будзе наш першапачатковы спіс,
, А затым мы будзем абнаўляць наш спіс, каб паказаць на new_list.
>> Цяпер нам трэба нейкі спосаб выцягвання рэчаў,
як у нас прайшоў увесь левага поддерева.
Цяпер нам трэба выцягнуць рэчы з яго,
як току з'яўляецца нулявым, мы не хочам, каб проста вярнуцца ілжывым.
Мы хочам зараз цягнуць за межамі на нашым новым спісе.
Зручны спосаб зрабіць гэта - добра, на самай справе, ёсць некалькі спосабаў зрабіць гэта.
Любы, ёсць прапановы?
Дзе я павінен гэта зрабіць, або, як я павінен гэта зрабіць?
У нас ёсць толькі пара хвілін, але якія-небудзь прапановы?
Замест таго, каб - у адзін бок, а нашы умовай з'яўляецца час,
тое, што мы ў цяперашні час глядзім на гэта не нулявы,
Замест гэтага мы збіраемся працягваць ісці, пакуль нашы Сам спіс з'яўляецца пустым.
Такім чынам, калі наш спіс заканчвае тым, што нулявы,
Затым мы запусцілі з рэчаў, каб шукаць, шукаць больш.
Але гэта азначае, што ў першую чаргу ў нашым спісе толькі збіраецца стаць першым вузлом.
Самае першае, што будзе - мы больш не павінны бачыць, што.
Такім чынам, спіс-> N будзе наша дрэва.
Спіс-> наступная будзе нулявы.
І зараз, пакуль спіс не роўная нулю.
Cur збіраецца выцягнуць нешта з нашага спісу.
Так з актуальн. Будзе роўным спіс-> л.
І тады спіс будзе роўным спіс-> п, ці спіс-> далей.
Так што, калі з актуальн. Значэнне роўна значэнні.
Цяпер мы можам дадаць і наша права і наш паказальнік левага паказальніка
тых часоў, пакуль яны не нулявыя.
Тут, унізе, я думаю, мы павінны былі гэта зрабіць у першую чаргу.
Калі (у цяперашні> правы! = NULL)
Затым мы збіраемся, каб ўставіць гэты вузел у наш спіс.
Калі (у цяперашні> злева), гэта крыху дадатковай працы, але гэта нармальна.
Калі (у цяперашні> злева! = NULL),
і мы збіраемся, каб ўставіць злева ў нашу звязаны спіс,
і што павінна быць.
Мы ітэрацыі - пакуль у нас ёсць нешта ў нашым спісе
у нас ёсць яшчэ адзін вузел на што паглядзець.
Такім чынам, мы глядзім на гэты вузел,
мы прасоўваем наш спіс у наступным.
Калі вузел з'яўляецца значэнне, якое мы шукаем, мы можам вярнуцца дакладна.
Астатняе ўставіць абедзве нашы левыя і правыя поддеревья,
тых часоў, пакуль яны не нулявы, у нашым спісе
так што мы непазбежна ідуць за імі.
Так што, калі яны не былі нулявыя,
калі наш каранёвай паказальнік паказваў на дзве рэчы:
Затым мы спачатку выцягнуў нешта з нашага спісу так заканчвае тым, што нулявы.
І тады мы ставім дзве рэчы назад, так што зараз наш спіс мае памер 2.
Затым мы збіраемся цыклу рэзервовага капіявання і мы толькі збіраемся цягнуць,
скажам, левы паказальнік нашага каранёвага вузла.
І гэта будзе проста трымаць адбываецца, мы скончым цыкл над усім.
>> Звярніце ўвагу, што гэта было значна складаней
У рэкурсіўнае рашэнне.
І я ўжо казаў некалькі разоў
, Што рэкурсіўнае рашэнне, як правіла, мае шмат агульнага з рашэннем итеративным.
Вось гэта менавіта тое, што рэкурсіўнае рашэнне робіць.
Адзінае змяненне складаецца ў тым, што замест няяўна з дапамогай стэка, стэк праграмы,
як ваш спосаб адсочваць, якія вузлы вы ўсё яшчэ павінны наведаць,
Цяпер вы павінны відавочна выкарыстоўваць звязаны спіс.
У абодвух выпадках вы адсочвання таго, што вузел яшчэ трэба наведаць.
У рэкурсіўнага выпадку гэта проста лягчэй, таму што стэк
рэалізуецца для вас, як стэк праграмы.
Звярніце ўвагу, што гэта звязаны спіс, гэта стэк.
Усё, што мы проста пакласці ў стэк
адразу, што мы збіраемся выцягнуць з стэка, каб наведаць наступны.
Мы па-за часам, але ёсць пытанні?
[Студэнт, неразборліва]
[Боуден] Так. Так што, калі ў нас ёсць звязаны спіс,
Ток будзе ўказваць на гэтага хлопца,
і зараз мы проста прасоўванне нашых звязаны спіс, каб засяродзіцца на гэтага хлопца.
Мы перамяшчэння праз звязаны спіс у гэтым радку.
І тады я думаю, мы павінны вызваліць нашы звязаны спіс і іншае
раз, перш чым вярнуцца сапраўдным або ілжывых, мы павінны
перабору нашых звязаны спіс і заўсёды тут, я думаю,
калі мы з актуальн. права не з'яўляецца роўным, дадайце яго, так што зараз мы хочам, каб вызваліць
актуальн. таму што, ну, хіба мы зусім забываемся пра спіс? Так.
Дык вось што мы хочам зрабіць тут.
Дзе паказальнік?
Cur было потым - мы хочам, каб спіс структур * 10 роўная спісе побач.
Бясплатныя спіс, спіс = тэмп.
І ў выпадку, калі мы вяртаемся праўда, нам трэба ітэрацыі
на працягу пакінутай часткі нашы звязаны спіс, вызваляючы рэчы.
Добрая рэч аб рэкурсіўнага рашэння вызваленне рэчы
проста азначае, з'яўляюцца factorings стэка, якія будуць адбывацца для вас.
Такім чынам, мы пайшлі ад чагосьці, што паходзіць на 3 лініі цяжка думаць пра код-
да таго, што значна многія іншыя цяжка думаць-о радках кода.
Ёсць яшчэ пытанні?
Добра. Мы добра. Bye!
[CS50.TV]