[Музыка гуляе] 

ROB BOWDEN: Прывітанне. Я Роб. І давайце гэта рашэнне па-за. І вось мы збіраемся рэалізаваць Агульная табліца. Мы бачым, што структура вузел Нашы табліца будзе выглядаць наступным чынам. Так што гэта будзе мець сЬаг слова Масіў Памер + 1. Не забывайце, + 1, паколькі максімальная слова ў слоўніку 45 знакаў. А потым мы збіраемся трэба адзін дадатковы сімвал для нуля зваротнай касой. 

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

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

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

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

І зараз мы збіраемся Malloc адзін вузел. І, вядома, мы павінны праветрываць праверце яшчэ раз. Так што калі mallocing не ўдалося, то мы хочам, каб разгрузіць любы вузел, які мы здарылася з Таноса раней, зачыніць слоўнік і вярнуцца ілжывым. Але ігнаруючы, што, мяркуючы, што мы атрымалася, то мы хочам выкарыстоўваць fscanf чытаць ні аднаго слова з нашага слоўнік у нашу вузла. Так што памятаеце, што ўступленне> слова з'яўляецца сімвал Слова буфер памерам Lenghth + 1 што мы збіраемся захоўваць слова цалі 

Так fscanf збіраецца вяртаць 1, да тых часоў, , Як гэта было ў стане паспяхова прачытаць слова з файла. Калі адзін адбываецца памылка, або мы дойдзе да канца файла, то не верне 1. У гэтым выпадку ён не вяртае 1, мы, нарэшце, збіраецца вырвацца з гэта ў той час як пятля. Такім чынам, мы бачым, што як толькі ў нас ёсць паспяхова чытаць слова ў запіс> слова, тое, што мы збіраемся, што слова з дапамогай нашага хэш-функцыю. 

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

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

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

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

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

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

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

Зараз гэта цыкл збіраецца перабору звязанага спісу гэта было па гэтым індэксе. Так заўважыць мы ініцыялізацыі запіс паказаць на тое індэкс. Мы збіраемся працягнуць у той час як запіс! = NULL. І памятайце, што абнаўленне паказальнік у наш звязаны спіс запіс = запіс> наступная. Так што наш бягучы кропку ўваходу Наступны пункт у звязаным спісе. 

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

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

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

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

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

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

Давайце гэта рашэнне паспрабаваць. Такім чынам, давайце паглядзім, што наш структура вузел будзе выглядаць. Тут мы бачым, што мы збіраемся мець лагічнае значэнне слова і структура вузла * дзеці Кранштэйны алфавіт. Таму першае, што вы маглі б быць цікава, чаму алфавіт рэд вызначаецца як 27? Ну, памятаеце, што мы збіраемся трэба быць апрацоўкі апостраф. Так што гэта будзе свайго роду Асаблівы выпадак ўсёй гэтай праграмы. 

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

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

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

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

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

Так першае, што мы збіраемся хачу зрабіць, гэта ў нас ёсць гэта глабальная пераменная корань. Цяпер корань будзе вузел *. Гэта вяршыня нашага сінтаксічнага дрэва, што мы будзе ітэрацыі. Такім чынам, першае, што мы збіраемся хочуць зрабіць, гэта вылучыць памяць для нашага кораня. Звярніце ўвагу, што мы выкарыстоўваем calloc Функцыя, якая ў асноўным тое ж самае як функцыя Таноса, за выключэннем, што гэта гарантавана вярнуць тое, што з'яўляецца цалкам абнуляецца. Так што, калі мы выкарыстоўвалі Таноса, мы павінны былі б прайсці праз усе ўказальнікі ў нашай вузел, і пераканайцеся, што яны ўсё нуль. Так calloc зробіць гэта за нас. 

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

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

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

Так што, як я ўжо казаў, мы павінны Асаблівы выпадак апостраф. Звярніце ўвагу, што мы выкарыстоўваем патройных аператар тут. Так што мы збіраемся, каб прачытаць гэта як, калі характар ​​мы чытаем, быў апостраф, то мы збіраемся ўсталяваць індэкс = "алфавіт" -1, які будзе быць індэкс 26. 

У адваротным выпадку, калі гэта не было апостраф, ёсць мы збіраемся ўсталяваць індэкс роўная с -. Так што памятаеце параўнанні з раней р-набораў, с - а будзе даваць нам алфавітны пазіцыя С. Так што калі З літара А, гэта будзе даць нам нулявы індэкс. Для лісты B, гэта дасць нам індэкс 1, і гэтак далей. 

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

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

Цяпер, калі гэта не было пустой для пачатку, то курсор можна проста перабраць да гэтага дзіцяці, фактычна не таго, каб вылучыць нічога. Гэта той выпадак, калі мы ўпершыню адбылося вылучыць слова «кот». І гэта азначае, што, калі мы ідзем вылучыць "Катастрофа", нам не трэба ствараць вузлы для C-A-T зноў. Яны ўжо існуюць. 

Што гэта яшчэ? Гэта стан, пры якім кандыцыянер быў касая рыса п, дзе кандыцыянер быў новая лінія. Гэта азначае, што мы паспяхова завяршыла слова. Цяпер тое, што мы хочам зрабіць, калі мы паспяхова завяршыла слова? Мы збіраемся выкарыстоўваць гэта поле слова ўнутры нашага структуры вузла. Мы хочам, каб усталяваць, што да ісціны. Так што паказвае, што гэты вузел паказвае паспяховым Слова, фактычны слова. 

Зараз усталюеце, што да ісціны. Мы хочам, каб скінуць нашу курсор да кропкі ў пачатку сінтаксічнага дрэва зноў. І, нарэшце, павялічыць наш слоўнік памер, так як мы знайшлі іншай працы. Так што мы збіраемся працягваць рабіць гэта, чытанне ў посимвольно, пабудовы новых вузлоў у нашай сінтаксічнага дрэва і для кожнага слова ў слоўніку, да мы, нарэшце, дасягнуць C! = EOF, у якім выпадку мы вырвацца з файла. 

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

Так што цяпер давайце праверым чэк. Гледзячы на ​​функцыі праверкі, мы бачым, , Што рэгістрацыя будзе вяртаць лагічнае значэнне. Гэта вяртае ісціну, калі гэта слова, што гэта перадаецца ў нашай сінтаксічнага дрэва. Гэта вяртае хлусня ў адваротным выпадку. Так як жа вызначыць, ці з'яўляецца гэтае слова ў нашым сінтаксічнага дрэва? 

Мы бачым тут, што, як і раней, мы збіраемся выкарыстоўваць курсор для перабору праз нашу сінтаксічнага дрэва. Цяпер вось мы збіраемся ітэрацыі над усім нашым словам. Так ітэрацыі словы мы мінулае, мы збіраемся вызначыць індэкс ў масіве дзяцей, што адпавядае слова кранштэйна I. Такім чынам, гэта будзе выглядаць гэтак жа, як нагрузка, дзе, калі слова [я] з'яўляецца апостраф, то мы хочам выкарыстоўваць індэкс «алфавіт» - 1. Таму мы вырашылі, што, што Тут мы збіраемся захоўваць апострафа. 

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

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

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

Мы не хочам, каб проста вярнуць дакладна. Мы хочам вярнуцца курсора> слова. Так памятаеце зноў жа, "кошка" ня ў нашым слоўніку, і «катастрофа» будзе, то мы будзем паспяхова мы атрымліваем праз слова "кот". Але курсора Слова будзе ілжывым, а не праўда. Так мы вяртаемся курсора слова для абазначэння Ці гэты вузел на самой справе слова. І гэта ўсё для праверкі. 

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

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

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

[Музыка гуляе]