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

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

З аднаго боку, мы маглі б выкарыстоўваць масіў, што мы дынамічна змяняць памеры або мы маглі б выкарыстоўваць звязаны спіс, хэш-табліцы або бінарнае дрэва. Але што б мы ні абралі, мы павінны памятаць аб эфектыўнасці і Прадукцыйнасць падсістэмы. Мы павінны думаць пра алгарытму, які выкарыстоўваецца ўставіць і паглядзець элементы ў наша структура дадзеных. 

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

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

Аб'ект, тып якога з'яўляецца структура вузел складаецца з двух частак называюцца дадзенымі і дзяцей. Мы пакінулі частка дадзеных як каментар павінны быць замененыя складнікам Дэкларацыя, калі структура вузел ўключаны ў праграму C. Частка дадзеных вузла можа быць Лагічнае значэнне, каб паказаць, ці з'яўляецца ці ня вузел, які ўяўляе сабой завяршэнне з слоўніка ключа ці гэта можа быць Радок, якая ўяўляе вызначэнне слова ў слоўніку. 

Мы будзем выкарыстоўваць смайлік для абазначэння калі дадзеныя прысутнічаюць у вузле. Ёсць 26 элементаў у нашай дзеці масіў, адзін індэкс за літары. Мы ўбачым значэнне гэта ў бліжэйшы час. 

Давайце больш уважліва паглядзім каранёвага вузла ў нашай схеме, якая не мае дадзеных звязаныя з ім, як паказана адсутнасць смайлік ў частка дадзеных. Стрэлкі, якія ідуць ад частак дзеці масіва прадстаўляюць не-вузел паказальнікі на іншыя вузлы. Напрыклад, стрэлка праходзіць ад другі элемент дзяцей ўяўляе літару B у ключы слоўніка. І ў больш шырокім дыяграме мы называем яго з В. 

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

Выкажам здагадку, мы хочам паглядзець адпаведнае значэнне для ключавога ваннай. Мы пачнем наш погляд уверх у каранёвым вузле. Тады мы будзем прымаць першую літару нашай Ключ, У і знайсці адпаведны пляма ў нашай дзіцячай масіва. Звярніце ўвагу, што існуе роўна 26 месцаў ў масіве, па адным для кожнай літары алфавіт. І мы будзем мець плямы ўяўляюць літары алфавіту па парадку. 

Мы разгледзім другі індэкс, то, Індэкс адзін, для В. Увогуле, калі мы ёсць алфавітны сімвал з мы можа вызначыць адпаведную кропку ў масіве дзяцей з выкарыстаннем Разлік, як гэта. Мы маглі б выкарыстоўваць большы дзяцей Масіў, калі мы хацелі прапанаваць Глядзі вышэй клавішы з больш шырокім дыяпазонам знакаў, такіх як усёй Набор сімвалаў ASCII. 

У гэтым выпадку паказальнік ў нашых дзецях масіва ў Індэкс адзін не з'яўляецца нулявым. Таму мы будзем працягваць шукаць да ключавога ваннай. Калі мы калі-небудзь сутыкаліся нулявы паказальнік на належным месцы ў дзяцей Масіў у той час як мы перасеклі вузлы, то мы павінны будзем сказаць, што мы не мог знайсці нічога для гэтага ключа. 

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

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

Калі б мы паспрабавалі паглядзець ключавую ванну, другі індэкса масіва ў мінулым вузла, адпаведны літарай H, будзе правялі нулявы паказальнік. Так ванна не ў слоўніку. І так сінтаксічнага дрэва унікальны тым, што ключоў ніколі не відавочна захоўваецца ў Структура дадзеных. Так як жа нам ўставіць нешта ў выглядзе дрэва? 

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

Мы пачнем з каранёвага вузла зноў, Наступныя паказальнікі, якія адпавядаюць літары наш ключ. На шчасце, мы былі ў стане прытрымлівацца паказальнікі на ўсім шляху, пакуль мы не дасягнулі канец ключа. Паколькі заапарк з'яўляецца прэфіксам словы зум, які з'яўляецца членам слоўнік, мы не павінны вылучыць якіх-небудзь новых вузлоў. 

Мы можам змяніць вузел, каб паказаць, што шлях персанажаў, якія вядуць да яна ўяўляе сабой ключ ў нашым слоўніку. Цяпер, давайце паспрабуем ўстаўкі Ключ БАНЯ ў сінтаксічнага дрэва. Мы пачнем ў каранёвым вузле і вынікайце паказальнікі зноў. Але ў гэтай сітуацыі, мы патрапілі ў мёртвых канец да мы ў стане дабрацца да канец ключа. Цяпер мы павінны вылучыць некаторыя новыя вузлы спатрэбіцца вылучыць адзін новы вузел для кожнага хто застаўся Ліст нашым ключом. 

У гэтым выпадку, мы проста павінны вылучыць адзін новы вузел. Тады мы павінны будзем зрабіць індэкс H спасылайцеся на гэты новы вузел. Яшчэ раз, мы можам змяніць вузел сведчаць аб тым, што шлях знакаў вядучая да яго ўяўляе сабой Ключавым у нашым слоўніку. Давайце разважаць пра асімптатычнае Складанасць нашых працэдур для гэтых дзве аперацыі. 

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

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

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

З іншага боку, даданне элементаў, скажам, хэш-табліцу прыводзіць да таго, Будучыня паглядзець больш павольна. Хоць гэта можа здацца прывабным у першую чаргу, мы павінны мець на ўвазе, што спрыяльная асімптатычнай складанасці не азначае, што на практыцы дадзеныя Структура абавязкова бездакорным. Мы таксама павінны ўлічваць, што для захоўвання слова ў выглядзе дрэва, мы павінны, у горшым так, лік вузлоў прапарцыйная даўжыні самога слова. 

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

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

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

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

Гэта таксама лёгка атрымаць гэты лістынг ў алфавітным парадку, так як Элементы масіва дзяцей размяшчаюцца ў алфавітным парадку. Так, спадзяюся, вы разгледзець прадастаўленне спрабуе паспрабаваць. Я Кевін Шмід, і гэта CS50. 

Ах, гэта пачатак заняпаду. Мне вельмі шкада. Выбачайце. Выбачайце. Выбачайце. 

Удар чатыры. Я сыходжу. Выбачайце. Выбачайце. Выбачайце. Выбачайце за чалавека, які павінен змяніць гэтую сысці з розуму. 

Выбачайце. Выбачайце. Выбачайце. Выбачайце. 

Выступоўца 1: Малайцы. Гэта было сапраўды добра зроблена.