[Powered by Google Translate] [Праходжанне - Праблема Set 5] [Zamyla Chan - Гарвардскі універсітэт] [Гэта CS50. - CS50.TV] 

Добра. Прывітанне ўсім, і дабро запрашаем Пакрокавае кіраўніцтва 5. 

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

Так што сардэчна запрашаем Праходжанне 5, у якім мы будзем казаць пра pset5: арфаграфічныя памылкі, , У якой мы будзем рабіць нашы ўласныя праверкі арфаграфіі. Панэль інструментаў на гэтым тыдні, размеркаванне кода, будзе важна паглядзець на проста каб зразумець розныя функцыі, што ваш слоўнік будзе мець. Мы на самай справе будзе мець некалькі. З файламі, якія разам робяць нашы PSET. І вось, гледзячы праз розныя аспекты, хоць на самай справе мы не рэдагуючы адзін з файлаў, speller.c, ведаючы, як ён працуе з адносінах да dictionary.c, якую мы будзем пісаць, будзе вельмі важным. Спецыфікацыя PSET таксама змяшчае шмат карыснай інфармацыі з пункту гледжання рэчаў, якія вы можаце выказаць здагадку, правілы і да таго падобнае, так што не забудзьцеся прачытаць PSET спецыфікацыю старанна саветы. І ў выпадку сумневаў правілы ці нешта ў гэтым родзе, то заўсёды ставяцца да PSET спецыфікацыі або абмеркаваць. Гэта PSET будзе спадзявацца на паказальнікі, таму мы хочам пераканацца, што мы разумеем розніцу паміж даданнем зорак перад імем паказальніка і амперсанда, як вызваліць іх, і г.д. Такім чынам, будучы майстрам паказальнікаў будзе вельмі карысным у гэтай задачы мноства. Мы збіраемся зазірнуць у звязаных спісах трохі больш, дзе ў нас ёсць элементы, якiя мы называем вузлы, якія маюць як каштоўнасць, а таксама паказальнік на наступны вузел, і так істотна якія злучаюць розныя элементы адзін за іншым. Ёсць некалькі розных варыянтаў рэалізацыі вашых фактычных слоўнік. Мы будзем глядзець на два асноўных метаду, які з'яўляецца хэш-табліцы, а затым спрабуе. У абодвух з іх, яны звязаны з нейкім паняццем звязаны спіс дзе вы элементаў, звязаных адзін з адным. І так мы будзем глядзець за тым, як вы маглі б працаваць па ўсім звязаных спісаў, стварыць іх, перайдзіце ў плане таго, як, напрыклад, ўставіць у яго вузла або свабоднае ўсіх вузлоў, а таксама. З пункту гледжання вызвалення вузлоў, што сапраўды важна што калі мы таНос памяці, потым мы яго вызвалення. Таму мы хочам, каб пераканацца, што няма паказальніка ідзе unfreed, што ў нас няма ніякіх уцечак памяці. Мы збіраемся ўвесці інструмент пад назвай Valgrind, які працуе ваша праграма і правярае, ці ўсё памяці, якую вы вылучылі затым вызвалены. Ваша PSET толькі завяршыць, калі яна працуе і мае поўную функцыянальнасць, але таксама, Valgrind кажа вам, што вы не знайшлі уцечку памяці. Нарэшце, для гэтага PSET, я сапраўды хачу падкрэсліць - Я маю на ўвазе, як звычайна, я, безумоўна, прыхільнік дапамогай пяра і паперы для мноства праблем, але для гэтага, я думаю, што ручка і папера будзе асабліва важным калі вы хочаце быць малюнак стрэлкі на рэчы і разуменне таго, як працуюць рэчы. Так што абавязкова паспрабуйце выкарыстоўваць ручку і паперу, каб зрабіць рэчы, перш чым пачаць кадаваньне таму што гэта можа стаць трохі бруднымі. 

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

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

Каб атрымаць лепшае ўяўленне аб звязаных спісах, таму што гэта вельмі важна сачыць за пераканаўшыся, што вы падтрымліваеце ланцуга, Мне падабаецца думаць пра яго, як людзі ў лінію, трымаючыся за рукі, дзе кожны чалавек, трымаючыся за рукі наступнага. Вы не можаце бачыць на гэтым малюнку, але ў асноўным яны паказваюць на наступны чалавек , Што ў іх ланцуга. І таму, калі вы хочаце, каб прайсці звязаны спіс, дзе гэтыя людзі - Уявіце сабе ўсе гэтыя людзі маюць значэння, звязаныя з імі , А таксама паказваць на наступны чалавек у лініі - калі вы хочаце, каб прайсці звязанага спісу, напрыклад, альбо змяніць значэння або шукаць значэння ці нешта накшталт гэтага, то вы хочаце мець паказальнік на канкрэтнага чалавека. Такім чынам, мы будзем мець вузел тыпу дадзеных паказальніка. Для гэтага, напрыклад, назавем яго курсорам. Іншы распаўсюджаны спосаб, каб назваць гэта будзе итератор ці нешта накшталт таго таму што гэта ітэрацыі і на самай справе рухаецца, які вузел ён паказвае. Гэта тут будзе наш курсор. Наш курсор спачатку ўказваць на першы элемент у нашым спісе. І таму тое, што мы хочам зрабіць, гэта мы хацелі б быць у асноўным працягвае курсор, перамяшчаючы яго з боку ў бок. У гэтым выпадку, мы хочам, каб перамясціць яго на наступны элемент у спісе. З масівамі, тое, што мы робім, што мы б проста сказаць, што мы павелічэнню індэкса на 1. У гэтым выпадку, тое, што мы павінны зрабіць, гэта на самай справе знайсці чалавека які гэты ток чалавек, якія паказваюць на, і што гэта будзе наступнае значэнне. Так што, калі курсор знаходзіцца ўсяго ў вузле паказальнік, тое, што мы хочам зрабіць што мы хочам, каб дабрацца да значэння, што курсор паказвае. Мы хочам, каб дабрацца да гэтага вузла, а затым, калі мы знаходзімся ў гэтым вузле, даведацца, дзе ён паказвае. Каб дабрацца да фактычнага вузла, што курсор паказвае на, Звычайна мы паказваем яго (* курсора). Гэта дасць вам фактычнага вузла, што курсор паказвае. І потым, пасля таго, што мы хочам зрабіць, гэта мы хочам атрымаць доступ усё, што наступнае значэнне вузла ёсць. Каб зрабіць гэта, каб атрымаць доступ да значэнняў ўнутры структуры, у нас ёсць кропка аператара. Такім чынам, то гэта было б (* курсора). Наступны. Але гэта трохі брудны з пункту гледжання наяўнасці дужкі вакол * курсора, і таму мы замяніць ўвесь гэты заявы з курсорам>. Гэта працяжнік, а затым знак больш, такім чынам робячы стрэлкі. Курсор-> далей. Гэта будзе на самой справе вам вузел, які курсор мышы. Гэта значэнне з'яўляецца наступнай. Такім чынам, замест таго, зоркі і кропка, вы замяняе, што са стрэлкай. Будзьце вельмі асцярожныя, каб пераканацца, што вы спрабуеце выкарыстаць гэты сінтаксіс. 

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

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

[Студэнт] Ці можна зрабіць спісам, які захоўвае выхаду паказальніка да канца? Гэта вызначана было б магчыма. Каб паўтарыць пытанне, ці магчыма, каб мець звязаны спіс структуру такое, што ў вас ёсць паказальнік на канец звязанага спісу? Я б сказаў, што гэта магчыма, і кожны раз, калі вы ўстаўляеце нешта ў вашай звязаны спіс Вам прыйдзецца абнаўляць паказальнік і таму падобнае. Вы б вузлом хвост *, напрыклад. Але калі вы рэалізуеце гэтую функцыю, вы павінны думаць аб кампрамісах, як тое, колькі разоў я збіраюся быць ітэрацыі з гэтай нагоды, Наколькі цяжка будзе сачыць за хвост, а таксама кіраўнік а таксама мае итератор, і таму падобнае. Ці значыць гэта -? >> [Студэнт] Так. Гэта магчыма, але з пункту гледжання дызайнерскіх рашэнняў, вы павінны ўзважыць усе варыянты. 

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

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

Але што, калі мы хочам, каб ўставіць вузел паміж другім і трэцім? Гэта адна не так проста, таму што мы хочам, каб пераканацца, што мы не адпусціць любога вузла ў нашым звязаны спіс. Што мы павінны зрабіць, гэта пераканацца, што мы якар сябе кожны з іх. Напрыклад, давайце назавем гэта другое. Калі вы сказалі, другая цяпер паказвае на гэтую новую і вы толькі што зрабілі паказальнік там, то гэта прывядзе гэты хлопец губляецца таму што няма ніякай спасылкі на яго. Замест гэтага - я намалюю гэта зноў. Прабачце мае мастацкія здольнасці. Мы ведаем, што мы не можам напрамую звязаць 2 да новай. Мы павінны пераканацца, што мы трымаемся да апошняга. Што мы маглі б зрабіць, гэта часовы паказальнік на элемент, які збіраецца быць дададзены на. Такім чынам у нас ёсць часовы паказальнік там. Паколькі мы ведаем, што гэта трэці ў цяперашні час сачыў, 2 можа звязацца з нашым новым. І калі гэты новы хлопец чырвона будзе паміж 2 і 3, тое, што паказальнік, хлопец збіраўся паказаць на? >> [Студэнт] Тэмп. Тэмпература Так. Такім чынам наступнае значэнне гэтага чырвонага хлопец будзе тэмп. Калі вы ўстаўкі ў звязаныя спісы, мы ўбачылі, што мы маглі б Лёгка дадаць нешта да канца шляхам стварэння часовага масіва, або калі мы хацелі нешта дадаць у сярэдзіну нашага масіва, то гэта зойме трохі больш ператасоўкі вакол. Калі вы хочаце, напрыклад, ёсць адсартаваны звязанага спісу, то вы павінны выгляду ўзважыць выдаткі і выгады, што таму што калі вы хочаце мець спарадкаваны масіў, гэта азначае, што кожны раз, калі вы ўстаўляеце ў яго, гэта зойме трохі больш часу. Аднак, калі вы хочаце, каб у далейшым, як мы знойдзем мы хочам, пошук у звязаным спісе, то было б лягчэй, калі вы ведаеце, што ўсё ў парадку. Такім чынам, вы можаце ўзважыць выдаткі і выгады ад гэтага. 

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

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

Арфаграфічныя памылкі мае ў размеркаванні кода пару файлаў важнасці. Спачатку мы заўважылі, што ў нас ёсць гэты Makefile тут, якія мы сапраўды не сустракаліся раней. Калі Вы зазірнулі ўнутр pset5 тэчку, вы заўважыце, што ў вас ёсць. Ч. файл, то ў вас ёсць два. з файламі. Што гэта Makefile робіць гэта раней, мы б проста ўвесці зрабіць, а затым назва праграмы і тады мы ўбачым усе гэтыя аргументы і сцягі перадаецца ў кампілятар. Што Makefile робіць гэта дазваляе кампіляваць некалькі файлаў адначасова і перадаць сцягі, якія мы хочам. Тут мы толькі бачым, што ёсць файл загалоўка тут. Тады мы на самай справе ёсць два зыходных файлаў. У нас ёсць speller.c і dictionary.c. Мы рады вітаць Вас адрэдагаваць Makefile, калі хочаце. Звярніце ўвагу, што тут, калі вы ўводзіце чысты, тое, што ён робіць на самай справе выдаляе ўсе , Што з'яўляецца асноўнай. Калі ў вас ёсць памылка сегментацыі, у асноўным вы атрымаеце дамп памяці. Такім чынам, гэта пачварнае маленькі файл з'явіцца ў тэчцы завецца ядром. Вы хочаце, каб выдаліць гэта, каб зрабіць яго чыстым. Яна выдаляе ўсе файлы EXE і. Аб файлах. 

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

Давайце зірнем на dictionary.c. Мы бачым, што яна вельмі падобная на dictionary.h, толькі цяпер ён проста ўсе гэтыя нязробленым ў гэтым. І так, што гэта ваша праца. У рэшце рэшт, вы будзеце запоўніць speller.c з усім гэтым кодам. Dictionary.c, калі бегчы, на самай справе не збіраецца нічога рабіць, таму мы глядзім у speller.c, каб убачыць фактычнае ажыццяўленне праверкі правапісу. Нават калі вы не збіраецеся рэдагавання любога гэтага Кодэкса, Важна, каб чытаць, разумець, калі будзе нагрузка называецца, калі я выкліку праверкі, проста каб зразумець, карта яго, паглядзець, як працуе функцыя. Мы бачым, што гэта праверка для правільнага выкарыстання. Па сутнасці, калі нехта бяжыць правапісу, гэта азначае, што гэта неабавязкова для іх, каб прайсці ў файл слоўніка, таму што гэта будзе стандартны файл слоўніка. А затым яны павінны прайсці ў тэкст, які будзе арфаграфіі правяраюцца. rusage тычыцца часу, таму што частка гэтай PSET якой мы будзем мець справу з больш познімі не толькі атрымліваць функцыянавання праверкі арфаграфіі працоўных але на самой справе прымусіць яго быць хуткім. І так, то што там rusage збіраецца ўвайсці Тут мы бачым, што першы званок на адзін з нашых dictionary.c файлаў, што з'яўляецца нагрузкай. Нагрузка вяртае ісціну альбо ва хлусня - праўда на поспех, ілжывых пасля збою. Так, калі ў слоўніку не загружаецца належным чынам, то speller.c верне 1 і выйсці. Але калі ён робіць нагрузку належным чынам, то гэта будзе працягвацца. Мы па-ранейшаму, і мы бачым некаторы файлавы ўвод / выснова тут, , Дзе ён збіраецца мець справу з адкрыцця тэкставага файла. Тут, як гэта робіць арфаграфіі правярае кожнае слова ў тэксце. Так што speller.c робіць прама тут ітэрацыі па кожным з слоў у тэкставым файле , А затым правяраць іх у слоўніку. Тут мы маем лагічны памылкамі, якія ўбачаць, калі праверка вяртае ісціну ці не. Калі слова на самай справе ў слоўніку, то праверка будзе вяртаць праўда. Гэта азначае, што слова не напісана няправільна. Такім чынам, няправільна было б ілжывым, і менавіта таму мы маем выбух там, індыкацыя. Мы працягваем ісці, а затым адсочвае, як шмат слоў з памылкамі Ёсць у файл. Гэта працягваецца і закрывае файл. Тады вось, ён паведамляе, колькі слоў з памылкамі ў вас. Ён вылічае, колькі часу спатрэбілася, каб загрузіць слоўнік, Колькі часу спатрэбілася, каб праверыць гэта, Колькі часу спатрэбілася, каб вылічыць памер, , Які, як мы пойдзем далей, павінна быць вельмі малая, і колькі часу спатрэбілася, каб разгрузіць слоўнік. Тут наверсе мы бачым заклік да выгрузцы тут. Калі мы правяраем памер тут, Затым мы бачым, што тут ёсць выклік памеру, дзе яна вызначае памер слоўніка. Awesome. 

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

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

Давайце ў хэш-табліцы метадаў. Хэш-табліца складаецца з спісу вядра. Кожнае значэнне, кожнае слова, збіраецца пайсці ў адну з гэтых вёдраў. Хэш-табліцы ідэальна раўнамерна размяркоўвае ўсе гэтыя значэння, што вы перадаеце , А затым запаўняе іх у вядро так, што кожнае вядро мае прыкладна аднолькавая колькасць значэнняў у гэтым. Структура хэш-табліцы, у нас ёсць масіў звязаных спісаў. Што мы робім, калі мы пераходзім у значэнні, мы правяраем, дзе гэта значэнне павінна належаць, якія вядро яна належыць, а затым змясціць яго ў звязаны спіс, звязаны з гэтым вядром. Вось, што ў мяне ёсць хэш-функцыі. Гэта цэлы лік хэш-табліцы. Такім чынам, для першага вядра, любыя цэлыя ніжэй за 10 ўдавацца ў першым вядры. Любыя цэлыя вышэй за 10, але ніжэй 20 Перайсці ў секунду, і гэтак далей, і гэтак далей. Для мяне кожнае вядро, якія прадстаўляюць гэтыя лічбы. Тым не менш, сказаць, што я была адбыцца ў 50, напрыклад. Здаецца, як быццам першыя тры ўтрымліваюць шэраг з дзесяці лічбаў. Але я хачу, каб мае хэш-табліцы, каб прымаць у любым выглядзе цэлых лікаў, так, то я павінен быў бы адфільтраваць усё ліку больш за 30, у апошнія вядро. І такім чынам, які прывядзе да свайго роду незбалансаванае хэш-табліцы. Паўтаруся, Хэш-табліца проста масіў вядра дзе кожнае вядро звязанага спісу. І вось каб вызначыць, дзе кожнае значэнне выходзіць, што вядро ён пераходзіць у, Вы будзеце хацець тое, што называецца хэш-функцыі , Якая прымае значэнне, а затым кажа, што гэта значэнне адпавядае пэўны вядро. Так што наверсе ў гэтым прыкладзе, мой хэш-функцыі ўзяў кожнага значэння. Ён праверыў, ці было гэта менш, чым 10. Калі б гэта было, гэта было б пакласці яго ў першым вядры. Ён правярае, ці з'яўляецца гэта менш за 20, ставіць яго ў другую калі гэта праўда, правярае, ці з'яўляецца гэта менш, чым 30, а затым кладзе яго ў трэцюю вядро, а потым усё астатняе проста падае на чацвёрты вядро. Таму, калі ў вас ёсць значэнне, ваш хэш-функцыі Пакладзеце гэта значэнне ў адпаведнае вядро. Хэш-функцыя ў асноўным трэба ведаць, колькі ў вас ёсць вядра. Ваш памер хэш-табліцы, колькасць сегментаў ў вас ёсць, што гэта будзе фіксаваны лік гэта да вас, для вас, каб вырашыць, але гэта будзе фіксаваны лік. Так што ваш хэш-функцыя будзе спадзявацца на тое, каб вызначыць, да якой кожны ключ пераходзіць у такі, што ён раўнамерна размеркаваны. Як і ў нашай рэалізацыі звязаных спісаў, зараз кожны вузел у хэш-табліцы на самай справе будзе мець тып знака. Таму ў нас ёсць масіў сімвалаў называюцца словы, а затым яшчэ адзін паказальнік на наступны вузел, які мае сэнс, таму што гэта будзе звязаны спіс. Памятаеце, калі мы былі звязаныя спісы, я зрабіў вузел * завецца галавой , Што паказвала на першы вузел у звязаным спісе. Але для нашай хэш-табліцу, таму што ў нас ёсць некалькі звязаных спісаў, тое, што мы хочам, мы хочам, каб наша хэш-табліцы, каб быць, як: "Што такое вядро?" Коўш ўяўляе сабой спіс вузлоў паказальнікаў, і так кожны элемент у вядры на самай справе паказвае на адпаведны звязаны спіс. Каб вярнуцца да гэтай схеме, вы бачыце, што вядра самі стрэлкі, не актуальна вузлоў. Адным з найважнейшых уласцівасцяў хэш-функцый з'яўляецца тое, што яны дэтэрмінавана. Гэта азначае, што кожны раз, калі вы хэш № 2, яна заўсёды павінна вяртаць той жа вядро. Кожнае значэнне, якое ўваходзіць у хэш-функцыю, калі паўтараецца, павінен атрымаць той жа індэкс. Так што ваш хэш-функцыя вяртае індэкс масіва дзе гэта значэнне належыць. Як я згадваў раней, колькасць сегментаў фіксавана, і таму ваш індэкс, што вы вернецеся павінна быць менш, чым колькасць каўшоў але больш 0. Прычына, чаму мы маем хэш-функцыі, а не толькі аднаго звязанага спісу або аднаго масіва з'яўляецца тое, што мы хочам, каб мець магчымасць перайсці да пэўнай часткі найбольш лёгка калі мы ведаем, характэрныя значэння - замест таго, каб шукаць праз увесь увесь слоўнік, магчымасць пераходу да пэўнай яе часткі. Ваш хэш-функцыя павінна прымаць да ўвагі, што ў ідэале, кожнага сегмента мае прыкладна такое ж колькасць ключоў. Так як хэш-табліцы ўяўляе сабой серыю звязаных спісаў, Затым звязаных спісаў самі будзеце мець больш, чым аднаго вузла. У папярэднім прыкладзе, два розных нумары, хоць яны былі не роўныя, Пры хэшируется, вернецца тым жа індэксам. Так што, калі вы маеце справу са словамі, адным словам, калі хэшируется будзе такі ж хэш-значэнне, як іншым словам. Гэта тое, што мы называем сутыкнення, калі ў нас ёсць вузел, які, калі хэшируется Звязаны спіс у гэтым вядры не пусты. Тэхніка, якую мы называем ёсць лінейнае зандаванне, куды вы ідзяце ў звязаным спісе, а затым знайсці, дзе вы хочаце ўставіць гэты вузел таму што ў вас сутыкнення. Вы можаце бачыць, што там можа быць кампраміс тут, ці не так? Калі ў вас ёсць вельмі маленькі хэш-табліцы, вельмі невялікая колькасць сегментаў, то вы будзеце мець шмат сутыкненняў. Але тады, калі вы робіце вельмі вялікае хэш-табліцы, вы, верагодна, каб звесці да мінімуму сутыкнення, але гэта будзе вельмі вялікі структуры дадзеных. Там збіраецца быць кампрамісы з гэтым. Таму, калі вы робіце вашу PSET, паспрабуйце пагуляць паміж магчыма, зрабіць менш хэш-табліцы але потым, ведаючы, што ён збіраецца заняць крыху больш часу, каб прайсці розныя элементы з тых, звязаныя спісы. 

Якія нагрузкі збіраюся зрабіць, гэта перабор кожнае слова ў слоўніку. Ён праходзіць у паказальнік на файл слоўніка. Такім чынам, вы збіраецеся скарыстацца файла I / O функцыі, якія вы асвоілі ў pset4 і перабіраць кожнае слова ў слоўніку. Вы хочаце, каб кожнае слова ў слоўнік, каб стаць новым вузлом, і вы збіраецеся змясціць кожны з гэтых вузлоў ўнутры вашай структуры дадзеных слоўніка. Кожны раз, калі вы атрымліваеце новае слова, вы ведаеце, што ён збіраецца стаць вузлом. Такім чынам, вы можаце пайсці адразу і таНос вузла паказальнік для кожнага новага слова, якое ў вас ёсць. Тут я тэлефаную мой вузел паказальнікаў new_node і я mallocing што? Памер вузла. Тады чытаць фактычнай радкі з файла, паколькі слоўнік на самай справе захоўваецца словам, а затым на новую радок, што мы можам скарыстацца з'яўляецца функцыяй fscanf, якім файл файл слоўніка, які мы праходзілі ў, так ён скануе файл на радкі і радкі месцах, якія ў апошні аргумент. Калі вы памятаеце назад у адной з лекцый, калі мы перайшлі і выгляд вычышчаныя пласты назад на бібліятэку CS50, мы бачылі ажыццяўленне fscanf там. Каб вярнуцца да fscanf, у нас ёсць файл, які мы чытаем с, Мы шукаем радок у файл, а затым мы змясціўшы яго ў Тут у мяне ёсць new_node-> слова, таму што new_node гэта вузел паказальнікаў, Ня фактычнага вузла. І тады я кажу new_node, я хачу, каб перайсці да вузла, што гэта паказвае на , А затым прысвоіць гэта значэнне слова. Мы хочам, каб затым ўзяць гэтае слова і ўставіць яго ў хэш-табліцы. Зразумейце, што мы зрабілі new_node вузла паказальніка таму што мы збіраемся хочам ведаць, што адрас гэтага вузла калі мы ўстаўляем яго ў таму, што структура вузлоў сабе, аб структуры, з'яўляецца тое, што ў іх ёсць паказальнік на новы вузел. Так што тое што адрас гэтага вузла будзе ўказваць? Гэты адрас будзе new_node. Ці мае гэта сэнс, чаму мы робім new_node вузел * у адрозненне ад вузла? Добра. У нас ёсць слова. Гэта значэнне з'яўляецца new_node-> слова. , Які змяшчае слова з слоўніка, які мы хочам ўваход. Такім чынам, што мы хочам зрабіць, гэта мы хочам, каб патэлефанаваць у наш хэш-функцыі на гэты радок таму што наш хэш-функцыя прымае радок, а затым вяртае нас цэлы лік, дзе гэты лік з'яўляецца індэксам, дзе хэш-табліцы па гэтым індэксе ўяўляе, што вядро. Мы хочам, каб гэты індэкс, а затым перайсці на гэтую індэкса Хэш-табліцы а затым выкарыстоўваць гэта звязаны спіс, каб ўставіць вузел у new_node. Памятаеце, што як бы вы вырашылі ўставіць свой вузел, будзь то ў сярэдзіне, калі вы хочаце, каб улагодзіць яго або ў пачатку ці ў канцы, проста пераканайцеся, што ваш апошні вузел заўсёды паказвае на NULL таму што гэта адзіны шлях, які мы ведаем, дзе апошні элемент нашага звязаны спіс. 

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

Так што цяпер мы атрымліваем для праверкі. Цяпер мы маем справу са словамі з файла ўводу тэксту, і таму мы збіраемся правяраць, ці ўсё з гэтых ўваходных слоў на самай справе ў слоўніку ці не. Падобны Scramble, мы хочам, каб забяспечыць неадчувальнасць да рэгістра. Вы хочаце, каб пераканацца, што ўсе словы перадаецца, нават калі яны змешаныя выпадку, пры выкліку з радком параўнання, эквівалентныя. Слоў у файлы ўводу тэксту на самай справе ўсё ў ніжнім рэгістры. Іншая справа, што можна выказаць здагадку, што кожнае слова перадаецца, кожны радок, будзе альбо алфавітным або ўтрымліваюць апострафы. Апострафы будзе сапраўдная слоў у нашым слоўніку. Так што калі ў вас ёсць слова з апострафам S, гэта фактычныя законныя слова ў слоўніку што гэта будзе адзін з вузлоў у хэш-табліцы. Калі ласка, праверце працуе з калі слова існуе, то ён павінен быць у нашым хэш-табліцы. Калі слова ёсць у слоўніку, то ўсе словы ў слоўніку знаходзяцца ў хэш-табліцы, так што давайце паглядзім на гэтае слова ў хэш-табліцы. Мы ведаем, што, паколькі мы рэалізавалі наш хэш-функцыі такія, што кожны унікальны слова заўсёды хэшируется тое ж значэнне, Затым мы ведаем, што замест пошуку праз усю нашу ўсёй Хэш-табліцы, мы сапраўды можам знайсці звязанага спісу, што гэта слова павінна належаць. Калі б гэта было ў слоўніку, то гэта было б у гэтым вядры. Што мы можам зрабіць, калі слова гэтае імя нашай радкі перадаецца, Мы можам толькі хэш, што слова і погляд на звязаны спіс на значэнне Хэш-табліцы [хэша (слова)]. Адтуль, што мы можам зрабіць, гэта ў нас ёсць меншае падмноства вузлоў для пошуку гэтага слова, і таму мы можам прайсці праз звязаны спіс, выкарыстоўваючы прыклад з раней у кіраўніцтве , А затым выклікаць параўнанне радкоў на слова там, дзе курсор паказвае на, гэтае слова, і паглядзець, ці з'яўляюцца гэтыя параўнання. У залежнасці ад спосабу, што Вам арганізаваць свой хэш-функцыі, калі яна сартуецца, вы маглі б вярнуцца ілжывым крыху раней, але калі гэта несортированные, то вы хочаце, каб працягнуць абыход праз звязаны спіс пакуль вы не знойдзеце апошні элемент спісу. І калі вы ўсё яшчэ не знайшлі слоў да таго часу, як вы дайшлі да канца звязанага спісу, гэта азначае, што вашыя словы не існуе ў слоўніку, і так, што слова з'яўляецца несапраўдным, і чэк павінен вярнуцца ілжывым. 

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

Цяпер мы падышлі да спробаў. Спрабуе выгляд выглядае так, і я таксама выцягнуць прыклад. У прынцыпе, у вас ёсць цэлы шэраг патэнцыйных літары, а затым, калі вы ствараеце слова, , Што ліст можа быць звязана для слоўніка да шырокага спектру магчымасцяў. Некалькі слоў пачынаюцца з C, а затым працягнуць, але іншыя працягваюць з ушчыльняльным, напрыклад. Trie гэта спосаб візуалізаваць ўсе магчымыя камбінацыі гэтых словаў. Trie будзе сачыць за паслядоўнасцю літар, якія складаюць словы, адгалінаванне, калі гэта неабходна, калі адна літара можа ісці некалькі лістоў, і ў канцы паказаць у кожнай кропцы ці гэта слова з'яўляецца сапраўдным ці не таму што калі вы правапіс словы MAT, MA Я не думаю, што гэта сапраўды слова, але мат. І таму ў вашым Trie, гэта будзе азначаць, што пасля MAT, што на самой справе гэта сапраўды слова. Кожны вузел у нашай Trie на самай справе адбываецца, каб утрымліваць масіў вузел паказальнікаў, і мы будзем мець, у прыватнасці, 27 з гэтых вузлоў паказальнікаў, па адным на кожную літару алфавіту, а таксама знак апострафа. Кожны элемент у гэтым масіве сама збіраюся паказваць на іншы вузел. Так што, калі вузел з'яўляецца NULL, калі няма нічога пасля гэтага, Затым мы ведаем, што няма ніякай далейшай літары ў гэтым слове паслядоўнасці. Але калі вузел не NULL, што азначае, што ёсць больш літар у гэтым лісце паслядоўнасці. І потым, акрамя таго, кожны вузел паказвае, ці з'яўляецца гэта апошні сімвал слова ці няма. 

Пойдзем у прыклад выглядзе дрэва. Першы ў мяне ёсць пакой на 27 вузлах у гэтым масіве. Калі ў мяне ёсць слова BAR - Калі ў мяне ёсць слова BAR, і я хачу, каб ўставіць, што, першая літара B, так што калі мая Trie пусты, B з'яўляецца другой літары алфавіту, так што я збіраюся абраць, каб паставіць гэта тут, на гэтым індэксе. Я хачу, каб мець B тут. B будзе вузел, які паказвае на іншы масіў ўсіх магчымых сімвалаў , Якія могуць ісці за літарай B. У дадзеным выпадку я маю справу са словам BAR, так будзе ісці тут. Пасля таго, у мяне ёсць літара R, так, то зараз паказвае на яе ўласныя камбінацыі, , А затым R будзе тут. BAR поўнае слова, і тады я буду мець пункт R на іншы вузел які кажа, што гэта слова з'яўляецца сапраўдным. Гэта вузел таксама будзе мець мноства вузлоў, але тыя, можа быць NULL. Але ў прынцыпе, гэта можа працягвацца падобнае. Гэта стане крыху больш ясным, калі мы ідзем у іншую, напрыклад, так што церпіце мяне там. Цяпер у нас ёсць бар ўнутры нашага слоўніка. Цяпер у нас ёсць слова БАЗ. Пачнем з B, і мы ўжо маем B якасці адной з літар, якая ў нашым слоўніку. Гэта вынікае з А. У нас ёсць ужо. Але замест гэтага, мы маем Z наступнае. Такім чынам элемента ў масіве будзе Z, і так, то, што ніхто не збіраецца паказваць на іншы сапраўдны канцы слова. Такім чынам, мы бачым, што, калі мы па-ранейшаму праз B, а затым, Ёсць два розных варыянту ў цяперашні час у нашым слоўніку словы, якія пачынаюцца з B і A. Скажам, мы хацелі, каб ўставіць слова FOOBAR. Тады мы хацелі б зрабіць запіс у F. F гэта вузел, які паказвае на ўвесь масіў. Мы хацелі б знайсці O, перайдзіце на O, O, то спасылкі на ўвесь спіс. Мы б B, а затым працягнуць, мы б і R. Такім чынам FOOBAR праходзіць ўвесь шлях ўніз, пакуль FOOBAR гэта правільнае слова. І вось тады гэта было б сапраўды слова. Зараз кажуць, што нашы наступнае слова ў слоўніку самой справе слова FOO. Мы б сказалі, што варта F. F? Я на самой справе ўжо ёсць прастора для высновы, таму я збіраюся працягваць. Мне не трэба, каб зрабіць новую. Працягнуць. FOO з'яўляецца сапраўдным слова ў гэтым слоўніку, так што потым я збіраюся ўказваць , Што з'яўляецца дапушчальным. Калі я кіну маю паслядоўнасць там, гэта было б правільна. Але калі мы працягнулі нашу паслядоўнасць з FOO да B і толькі што FOOB, FOOB ні слова, і гэта не ўказана ў якасці дапушчальным. У выглядзе дрэва, вы кожны вузел паказвае, ці з'яўляецца гэта сапраўды слова або няма, , А затым кожны вузел таксама мае масіў з 27 вузлоў паказальнікі што затым абярыце вузлы самі. 

Вось спосаб, як вы можаце вызначыць гэта. Аднак, як і ў хэш-табліцу-прыклад, дзе ў нас было галаўным вузле * для абазначэння пачатку нашай звязаны спіс, мы таксама захочуць нейкім чынам ведаючы, дзе пачатак нашай Trie ёсць. Некаторыя людзі называюць спрабуе дрэў, а вось дзе корань прыходзіць. Таму мы хочам, корань нашага дрэва, каб пераканацца, што мы застаемся зазямленне туды, дзе нашы Trie ёсць. Мы ўжо, здаецца, падышоў як вы маглі б падумаць аб загрузцы кожнага слова ў слоўніку. Па сутнасці, за кожнае слова вы збіраецеся хочаце перабраць вашы Trie і ведаючы, што кожны элемент у дзяцей - мы назвалі яго дзяцей у дадзеным выпадку - адпавядае іншую літару, вы будзеце жадаць, каб праверыць гэтыя значэння у дадзены індэкс, які адпавядае літары. Так думаюць ўсе шляхі назад на Цэзара і Виженера, ведаючы, што кожны ліст вы можаце відаў карту назад у алфавітным паказальніку, Вызначана праз Z будзе даволі лёгка супаставіць з алфавітным лістом, але, на жаль, апострафы таксама прынятых знакаў у словах. Я нават не ўпэўнены, што ASCII значэнне, так для гэтага, калі вы хочаце, каб знайсці індэкс вырашыць, ці вы хочаце, каб быць першым ці апошні, вам прыйдзецца зрабіць цяжкі Кадаваць праверкі, што , А затым пакласці, што ў індэкс 26, напрыклад. І тады вы правяраеце значэнне ў дзяцей [я] дзе [я] адпавядае любой літары знаходзімся. Калі гэта NULL, што азначае, што ёсць у цяперашні час не любыя магчымыя літары вынікаюць з гэтага папярэдняй паслядоўнасці, так што вы будзеце жадаць, каб таНос і зрабіць новы вузел і ёсць, што дзеці [я] паказваюць на гэта так што вы ствараеце - калі мы ўставілі літару ў прастакутнік - каб дзеці не-NULL і кропка ў гэты новы вузел. Але калі гэта не NULL, як у нашым экзэмпляры FOO Калі мы ўжо былі FOOBAR, мы па-ранейшаму, і мы ніколі не робіць новы вузел, а проста задаўшы is_word да праўдзівага У канцы гэтага слова. 

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

Цяпер мы падышлі, каб праверыць. Тое ж стандартам, як і раней, дзе мы хочам, каб забяспечыць неадчувальнасць да рэгістра. Акрамя таго, мы мяркуем, што радкі з'яўляюцца толькі літары і апостраф таму што дзеці гэта масіў з 27 доўгі, так што ўсе літары алфавіту плюс апостраф. Для праверкі, што вы хочаце зрабіць, вы хочаце, каб пачаць у корані таму што корань будзе паказваць на масіў, які змяшчае ўсіх магчымых пачатковых літар слова. Вы збіраецеся пачаць там, а затым вы збіраецеся праверыць гэта значэнне NULL ці не, таму што, калі значэнне NULL, што азначае, што слоўнік не мае значэння , Якія ўтрымліваюць гэтую літару ў гэтым канкрэтным парадку. Калі гэта NULL, то гэта азначае, што слова напісана з памылкамі адразу. Але калі ён не NULL, то вы можаце працягваць, сказаць, што першая літара з'яўляецца магчымым першая літара ў слове, так што цяпер я хачу праверыць, калі другі ліст, што паслядоўнасць, знаходзіцца ў маім слоўніку. Такім чынам, вы збіраецеся пайсці ў індэксе дзяцей першага вузла і пераканайцеся ў тым, што другое ліст існуе. Тады вы паспрабуйце гэты працэс, каб праверыць, што паслядоўнасць з'яўляецца сапраўдным ці не ў вашым Trie. Кожны раз, калі вузел дзяцей, што індэкс паказвае на NULL, Вы ведаеце, што гэтая паслядоўнасць не існуе, але потым, калі вы дойдзеце да канца словы, якія вы ўводзіцца, Затым вы хочаце праверыць цяпер, калі я завяршыў гэтую паслядоўнасць і знайшоў яго ў маёй сінтаксічнага дрэва, у тым, што слова сапраўды ці не? І такім чынам вы хочаце праверыць гэта, і вось тады, калі вы выявілі, што паслядоўнасць, то вы хочаце праверыць, ці з'яўляецца гэта слова з'яўляецца сапраўдным ці не таму што памятаю яшчэ ў папярэднім выпадку, што я намаляваў, дзе мы мелі FOOB, , Якая была сапраўдная паслядоўнасці, якія мы знайшлі, але не быў фактычна сапраўды само слова. 

Аналагічна, для выгрузкі ў спробаў вы хочаце выгрузіць усе вузлы ў Trie. Выбачайце. Як і хэш-табліц, дзе ў разгружаць мы вызвалілі ўсіх вузлоў, У спробаў мы хочам таксама вызваліць усіх вузлоў. Выгрузка сапраўды будзе працаваць простым знізу ўверх таму што гэта, па сутнасці звязаныя спісы. Такім чынам, мы хочам пераканацца, што мы трымаемся за ўсё значэння і бясплатна ўсё з іх у відавочным выглядзе. Тое, што вы захочаце зрабіць, калі вы працуеце з Trie , Каб падарожнічаць на дно і бясплатны мінімальна магчымых вузел 1. , А затым падняцца на ўсе гэтыя дзеці, а затым вызваліць усіх тых, ўверх, а затым свабодна, і г.д. Накшталт як справа з ніжнім пластом Trie 1. , А затым збіраецца наверсе, як толькі вы вызвалілі ўсё. Гэта добры прыклад таго, дзе рэкурсіўная функцыя можа спатрэбіцца. Пасля таго як вы вызвалілі ніжні пласт вашага Trie, Затым вы тэлефануеце выгрузіць на астатняе, пераканаўшыся, што вы пазбавіць ўсіх міні - Вы можаце відаў візуалізаваць яго ў якасці міні спробаў. Такім чынам, у Вас ёсць корань тут. Я проста спрашчэнні гэта так, я не прыцягнуць 26 з іх. Так што ў вас ёсць гэтыя, а затым яны ўяўляюць сабой паслядоўнасці слоў дзе ўсе гэтыя маленькія кругі лісты, якія сапраўдныя паслядоўнасці літар. Давайце працягнем крыху больш. Тое, што вы захочаце зрабіць, гэта бясплатна ніжняй тут, а затым бясплатна гэтую , А затым вызваліць гэтую ўнізе, перш чым вызваліць верхнюю тут таму што калі вы нешта бясплатнае другога ўзроўня тут, Затым вы сапраўды страціце гэта значэнне тут. Вось чаму так важна для выгрузкі ў выглядзе дрэва, каб пераканацца, што вы вызваліць ніжнюю першым. Што вы можаце зрабіць, гэта сказаць для кожнага вузла Я хачу, каб выгрузіць усё пра дзяцей. 

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

Частка гэтай PSET, гэта неабавязкова, каб кінуць выклік Big Board. Але калі мы маем справу з гэтымі структурамі дадзеных гэта пацешна бачыць, як хутка і наколькі эфектыўныя вашыя дадзеныя структуры маглі б быць. Ваш хэш-функцыя ў выніку шматлікіх сутыкненняў? Ці ваш памер дадзеных сапраўды вялікі? Ці значыць гэта зойме шмат часу, каб прайсці? У часопісе правапісу, ён выводзіць, колькі часу вы карыстаецеся для загрузкі, , Каб праверыць, правесці памеру, і для разгрузкі, і таму тыя, размешчаныя ў Вялікі савет, дзе вы можаце канкурыраваць з аднакласнікамі і некаторых супрацоўнікаў, каб бачыць, хто мае самыя хуткія праверкі арфаграфіі. Адна рэч, якую я хацеў бы адзначыць аб хэш-табліцы тое, што ёсць некаторыя даволі простыя хэш-функцыі, якія мы маглі б падумаць. Напрыклад, у вас ёсць 26 вёдраў, і так кожны коўш адпавядае першай літарай у слове, але гэта будзе прыводзіць да даволі незбалансаваным хэш-табліцы таму што ёсць нашмат менш слоў, якія пачынаюцца з X, чым пачынаць з M, напрыклад. Адзін са спосабаў ісці аб правапісу, калі вы хочаце атрымаць усе іншыя функцыянальныя ўніз, затым проста выкарыстоўваць просты хэш-функцыі, каб мець магчымасць атрымаць код працуе , А затым вярнуцца і змяніць памер хэш-табліцы і азначэнні. Ёсць шмат рэсурсаў у Інтэрнэце для Хэш-функцый, і так для гэтага PSET вам дазволена для пошуку хэш-функцыі ў Інтэрнэце для некаторых намёкаў і натхненне тых часоў, як вы пераканаецеся, каб цытаваць, дзе вы атрымалі яго ад. Вы заўсёды можаце паглядзець і інтэрпрэтаваць некаторыя хэш-функцыі, якія вы знойдзеце ў Інтэрнэце. Вярнуцца да гэтага, вы маглі б убачыць, калі хтосьці выкарыстаў выглядзе дрэва Ці іх рэалізацыя хутчэй, чым ваш хэш-табліцы ці не. Вы можаце ўявіць Big Board некалькі разоў. Яна будзе запісваць самыя апошнія запісы. Таму, магчыма, вы зменіце сваё хэш-функцыі, а затым зразумелі, што гэта на самай справе нашмат хутчэй ці шмат павольней, чым раней. Гэта крыху пацешным спосабам. Там заўсёды 1 або 2 супрацоўнікаў, якія спрабуюць зрабіць мінімальна магчымы слоўнік, так што гэта заўсёды цікава глядзець. 

Выкарыстанне для PSET з'яўляецца запуску правапісу з дапамогай дадатковага слоўніка , А затым абавязковая тэкставы файл. Па змаўчанні пры запуску правапісу з дапамогай усяго толькі тэкставы файл і не паказаць слоўнік, ён збіраецца выкарыстоўваць файл слоўніка тэкст, адзін вялікі у тэчцы cs50/pset5/dictionaries. Гэта адна мае больш 100000 слоў. Яны таксама маюць невялікі слоўнік, які мае значна менш слоў CS50, што зрабіў для вас. Тым не менш, вы можаце вельмі лёгка проста зрабіць свой уласны слоўнік калі вы проста хочаце працаваць у невялікіх прыкладаў - Напрыклад, калі вы хочаце выкарыстоўваць GDB, і вы ведаеце канкрэтныя значэння што вы хочаце, каб ваш хэш-табліцы, каб намеціць ст. Так што вы проста можаце зрабіць свой уласны тэкставы файл толькі з BAR, BAZ, FOO, і FOOBAR, зрабіць гэта ў тэкставым файле, аддзяліць тых, кожная з 1 лінія, , А затым зрабіць свой уласны тэкставы файл, які змяшчае толькі літаральна, можа быць 1 ці 2 слоў так што вы сапраўды ведаеце, што выснова павінен быць. Некаторыя файлы узораў тэксту, якія Вялікай рады пры запуску задачай будзе праверыць з'яўляюцца Вайна і свет рамана Джэйн Осцін ці нешта накшталт гэтага. Такім чынам, калі вы пачынаеце, гэта нашмат лягчэй зрабіць свае ўласныя тэкставыя файлы , Якія ўтрымліваюць толькі некалькі слоў ці, можа быць 10 так што вы можаце прадказаць, які вынік павінен быць , А затым праверыць яго супраць гэтага, дык яшчэ кантраляванай прыклад. І так, паколькі мы маем справу з прагназаванні і распрацоўцы рэчаў вакол, я зноў хачу заклікаць вас выкарыстоўваць ручку і паперу таму што на самой справе адбываецца, каб дапамагчы вам з гэтым - маляваць стрэлкі, як хэш-табліцы або як ваш Trie выглядае, калі вы нешта вызвалення дзе стрэлкі ідуць, Вы трымаючыся дастаткова, вы бачыце ўсе спасылкі знікаюць і падзенне ў бездань ўцечка памяці. Так што, калі ласка, паспрабуйце намаляваць рэчы, нават перш чым патрапіць да напісання кода ўніз. Нічыя рэчы, каб зразумець, як усё будзе працаваць таму што тады я гарантую, што вы будзеце працаваць у меншай блытаніны паказальнік там. 

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

[CS50.TV]