[Powered by Google Translate] [Walkthrough - Проблем Set 5] [Zamyla Chan - Харвардския университет] [Това е CS50. - CS50.TV] 

Добре. Здравейте на всички, и добре дошли Walkthrough 5. 

Pset5 е правописни грешки, в който ние ще се направи проверка на правописа. Правописа пулове са изключително важни. Дали това се е случило с теб? Вие работите много, много трупат върху хартия за сблъсък и след това пак ще свършат много Раде светят като D или D = и всички, защото вие сте лебервурст спойлер в широк дума на кита. Да, корекция чушки си е въпрос на изключително импотентност. Това е проблем, който засяга Менли, мъжествен студенти. Веднъж бях казал от моя клас ситите мъчителя, че никога няма да влязат в добър колега. И това е всичко, което някога съм искал, че всяко дете иска на моята възраст, само за да получите в добър колега. И не само всеки колега. Исках да отида до Правна колега Кот. Така че, ако не подобрение, няма ще бъде мечтите ми ще Харвард, Жале, или затвор - нали знаете, в затвора, Ню Джърси. Така че аз имам проверка на правописа. Това е малък откъс от една от любимите ми говорими художници дума, Тейлър Мали. Както и да е, както казва той, е много важно, че е важно да има проверка на правописа. 

Така че добре дошли да Walkthrough 5, в който ние ще се говори за pset5: правописни грешки, , в което ще се направи нашата собствена проверка на правописа. Инструментариум за тази седмица, разпределението код, ще бъде важно да се гледа само за да разберат различните функции, които ви речник ще има. Ние всъщност ще бъде с множество файлове в които заедно правят нашата pset. И така през различните аспекти, въпреки че ние всъщност не редактирате един от файловете, speller.c, знаейки как работи той с връзка с dictionary.c, които ще се пише, ще се окаже много важно. Спец. pset също съдържа много полезна информация по отношение на неща, които може да се предположи, правила и неща като това, така че не забравяйте да прочетете внимателно спец. pset за съвети. И при съмнение за правило или нещо подобно, тогава винаги се отнасят към pset спец. или дискусирай. Това pset ще разчитат предимно на указатели, така че искаме да сме сигурни, че сме се разбере разликата между добавянето на звезди пред името на показалеца и амперсанди, как да ги освободи и др. Така че е майстор на указатели се случва да бъде много полезен в този проблем набор. Отиваме да разгледа свързани списъци малко повече, където имаме елементи, които ние наричаме възли, които имат стойност, както и показалеца към следващия възел, и така по същество свързването на различни елементи един след друг. Има няколко различни варианти на изпълнение на реалните ви речник. Отиваме да се търсят в две основни методи, които е хеш-таблици и след това се опитва. В тези две, те са свързани с някакъв вид на понятието свързан списък , където са елементи, свързани един с друг. И така, ние ще разгледаме как може да сте в състояние да работи около свързани списъци, ги създавате, се движите по отношение на това как да, например, поставете възел в нея или безплатно всички възли, както и. По отношение на освобождаващите възли, това е много важно , че всеки път, когато ние заделяне на памет, след това го освободи. Така че ние искаме да се уверите, че не отива unfreed показалеца, че ние не разполагат с никакви изтичане на памет. Отиваме да се въведе инструмент наречен Valgrind, че стартира вашата програма и проверява дали цялата памет, която отпусна след това освободени. Да попълнят Вашият pset е, когато тя работи и има пълна функционалност, но също така, Valgrind ви казва, че не са открили никакви изтичане на памет. Накрая, за тази pset, аз наистина искам да подчертая - Искам да кажа, както обикновено, определено съм привърженик на използването на писалка и хартия за вашия проблем комплекти, , но и за това, мисля, че писалка и хартия ще бъде особено важно , когато искате да бъде изготвянето стрелките на нещата и да се разбере как работят нещата. Така че определено се опитате да използвате хартия и писалка, за да рисуват неща, преди да се кодиране , защото той може да получи малко разхвърлян. 

Първо, нека да отидат в свързани списъци малко. Свързани списъци се състоят от възли, където всеки възел има стойност, свързани с нея, , както и указател към следващия възел след него. Няколко неща, които са важни със свързани списъци са, че ние трябва да помним, където първата ни възел, а след това веднъж знаем къде първо възел е, по този начин можем да имаме достъп възел, че първите точки възел до и след това след това и една след това. И тогава на последния елемент в свързан списъка си, че възел показалеца винаги ще сочи към NULL. Когато възел точки, за да NULL, тогава знаете, че сте достигнали до края на списъка, че този възел е последната, че няма нищо след това. Тук, в тази схема, ще видите, че стрелките са указатели, и синята раздел е мястото, където стойността се съхранява, и след това червената кутия с показалеца, за да е възел показалеца сочи към следващия възел след него. И така, което виждате тук, D възел ще сочи към NULL, защото това е последният елемент в списъка. 

Нека да погледнем как можем да определим структура за възел. И тъй като искаме да имаме множество възли, това ще стане typedef структура , в която ще има няколко различни случаи на възли. И така, ние го определят като нов тип данни. Тук, ние имаме typedef възел структура. В този пример, ние сме се занимават с целочислени възли, така че ние имаме име цяло число стойност и тогава имаме друг показалеца, и в този случай, това е указател към възел, така че ние имаме структура възел * нарича следващия. И тогава ние призоваваме целия този възел нещо. Уверете се, че следвате този синтаксис. Забележете, че възел е посочен по-горе, както и под фигурни скоби. След това, за да следите къде ми е първата възел е в тази свързан списък, тогава имам възел показалеца главата, и аз изчистване достатъчно място за размера на възел. Забележете, обаче, че главата е всъщност възел показалеца, за разлика от самия възел. Така че главата всъщност не съдържа никаква стойност, само се посочва в зависимост от това кое от двете първа възел в свързани моя списък. 

За да получите по-добро чувство за свързани списъци, защото това е много важно да следите да сте сигурни, че поддържат веригата, Харесва ми да мисля за него, тъй като хората в линия, държейки се за ръце, , където всеки човек се държат за ръце със следващата. Вие не можете да видите в тази рисунка, но основно те насочват към следващия човек , която е във веригата си. И така, ако искате да преминават свързан списък, когато тези хора - представете си всички тези хора имат стойности, свързани с тях , а също и сочи към следващия човек на линията - ако искате да прекосяват свързан списък, например, или да редактирате стойностите или търсене на стойност или нещо подобно, тогава вие ще искате да има указател към конкретно лице. Така че ние отиваме да има данни възел тип показалка. За този случай, нека да го наречем курсора. Друг често срещан начин да назовем това ще бъде итератор или нещо подобно защото това е итерации и наистина се движи, които възел посочи. Това ще бъде нашата курсора. Нашата курсора първо ще сочи към първия елемент в нашия списък. И така, това, което искаме да направим, е бихме основно продължава курсора, се движи от едната страна към другата. В този случай, ние искаме да го преместите в следващия елемент в списъка. С масиви, какво ще правим, е, че ние просто ще кажа, че увеличаване на индекса от 1. В този случай, това, което трябва да направите, е действително човек това лице е насочена към и това ще бъде следващата стойност. Така че, ако курсора е само един възел показалеца, тогава това, което искаме да направим е, искаме да стигнем до стойността, която курсора е насочена към. Искаме да стигнем до този възел, а след това, след като сме в този възел, където сочи. За да стигнете до действителната възел, че курсора сочи, обикновено го показват от (* курсора). Това ще ви даде действителното възел, който курсорът е насочена към. И тогава, след това, това, което искаме да направим, е, че искаме достъп независимо, че следващата стойност възел. За да направите това, за достъп до стойностите вътре на структурата, имаме точка оператор. Така че след това тя ще бъде (* курсора). Следващата. Но това е малко разхвърлян по отношение на скоби около курсора * и затова замени цялото това изявление с курсора->. Това е тире, и след това по-голяма, отколкото знак, така че като стрела. курсора-> следващия. Това действително ще ви накара възела, че курсорът точки. Тази стойност е на следващата. Така че, вместо да се налага на звездата и точка, вие замени това със стрелка. Бъдете много внимателни, за да се уверите, че се опитвате да използвате този синтаксис. 

Сега, че ние имаме курсора, ако искаме да достъп до стойност, преди, имахме курсора-> Next но за достъп до стойността на възела, че курсора сочи, ние просто кажа възел-> стойност. От там, това е тип данни, каквото и да сте определили ценностите и възли, които трябва да бъдат. Ако това е INT възел, а след това курсора-> стойност е просто щеше да бъде цяло число. Така че можем да направим операции на това, проверете равенства, я зададете различни стойности, и т.н. Значи това, което искате да направите, ако искате да преместите курсора на следващия човек, всъщност променя стойността на курсора. Тъй като курсорът е възел показалеца, промяна на настоящ адрес показалеца на адреса на следващия възел във вашия списък. Това е просто някакъв код, където можете да превъртате. Когато имам коментар направи нещо, това е мястото, където вие вероятно ще получите достъп до стойността или да се направи нещо да се направи с този специфичен възел. Да го започнем, аз казвам, че моята курсора първоначално ще сочи към първия елемент в свързан списък. И така напред, го определя като ръководител на възела. 

Както споменах и преди, освобождавайки е наистина важно. Вие искате да сте сигурни, че ви освободи всеки елемент в списъка, след като сте приключили с него. Когато не трябва да се разбира всяко от тези указатели вече, искате да се уверите, че ви освободи всички тези указатели. Но вие искате да бъдете много внимателни тук по това, че искат да избегнат изтичане на памет. Ако ви освободи един човек преждевременно, а след това всички указатели, че този възел точки ще бъдат загубени. Връщайки се към лицето, например, за да го направи малко по-високи залози, да имат тези хора, освен в случаите, в този случай те са кръжи над езерото с чудовището. Ние искаме да сме сигурни, че всеки път, когато се освободи, да не загубим и нека на всички възли, преди да сме ги е освободил. Например, ако сте били просто да се обадя на този човек тук, тогава той ще бъде освободен, но след това всички тези момчета ще бъдат загубени и те ще се унесете и да падне. Така че ние искаме да се уверите, че вместо това, ние искаме да се поддържа връзка с останалата част. Нашият главен показалеца, който сочи към първия елемент в списъка. Това е нещо като въже за закрепване на първо лице. Какво може да искате да направите, когато ви освободи списък Ако искате първо да освободи първия елемент, тогава може да има временно показалеца който сочи към първия елемент. Така че трябва временно показалеца сочи тук. По този начин, ние имаме държат на първото възел. И тогава, тъй като ние знаем, че на първия възел ще бъдат освободени, тогава можем да продължим това въже, тази котва, главата ни, действително се прави какъвто и да е първата е насочена към. Така че това главата всъщност се насочва към втория елемент. Сега ни е позволено да се освободи, каквото и да се съхраняват при температура, и така можем да изтрие без да я застрашава всички други възли в нашия списък. Друг начин, че можете да направите това може да бъде всеки път, когато се освободи последния елемент в списъка защото те са гаранция, че не трябва да се посочи за нищо. Така бихте могли просто да освободи този, а след това без този, тогава без това. Това определено работи, но е малко по-бавно, защото от естеството на свързаните списъци, ние не можем просто веднага скочи до последния. Ние трябва да преминават всеки елемент в свързан списък и проверете дали е насочена към NULL, проверете всеки път, а след това веднъж стигнем до края, а след това без, че. Ако ви се налага да се направи този процес, всъщност ще бъде проверка, проверка тук, после проверка тук, го освобождава, отново се връща, проверка тук, проверка тук, го освобождава, проверка, и след това го освобождава. Това отнема малко повече време. Да. 

[Ученик] Ще бъде ли възможно да се направи свързан списък, който съхранява показалеца изход до края? Това определено ще бъде възможно. Да се ​​повторя въпроса, че е възможно да има свързан списък структура такава, че имате показалец сочи към края на свързан списък? Бих казал, че това е възможно, и всеки път, че сте поставили нещо в свързали списък ще трябва да се актуализира тази показалеца и подобни неща. Може би трябва възел * опашката, например. Но когато сте прилагане на тази функция, трябва да се мисли за компромисите, искал колко пъти съм ще бъде итерации върху това, колко трудно ще бъде, за да следите на опашката, както и главата както и итератор, и такива неща. Ли това? >> Студент Да. Това е възможно, но по отношение на проектните решения, трябва да се преценят възможностите. 

Ето скелет на кода, който ще ви позволи да освободи всеки елемент в свързан списък. Отново, тъй като аз съм итерации над свързан списък, аз ще искам да има някакъв вид на курсора или итератор. Ние сме итерации докато курсорът е NULL. Вие не искате да превъртате, когато курсорът е NULL защото това означава, че там не е нещо в списъка. Така че след това тук направя временна възел * сочи към това, което аз съм обмисля е първа на моя списък, и след това да си движа курсора напред една и след това без каквото имах в временно съхранение. 

Сега стигаме до поставите в свързани списъци. Имам три възли в свързани моя списък, и нека продължим с простия случай там, където искаме да вмъкнем друг възел в края на свързаното нашия списък. За да направите това, всичко, което ние ще направим, е, че ние ще преминават да открия къде е текущата края на свързан списък, така че в зависимост от това коя от двете възел се сочи NULL че е това - и след това казват, всъщност, това няма да бъде последният възел; ние всъщност ще има още един. Така че ние ще имаме тази една точка, за каквото и да си поставите. Така че сега този червен човек тук става последния възел в свързан списък. И така характеристиката на последния възел в свързан списък е, че да сочи към NULL. Значи това, което ще трябва да направите, е да изберете показалеца този червен човек да NULL. Има. 

Но какво ще стане, ако искахме да вмъкнете възел между втория и третия? Това не е чак толкова просто, защото искаме да се уверите, че ние не пусна на всеки възел в свързани нашия списък. Това, което ще трябва да направите, е да сме сигурни, че се закотвят на всеки един. Например, нека наречем това втората. Ако ти каза вторият сега сочи към тази нова и просто показалеца там, това би довело до този човек се губи защото няма никаква връзка с него. Вместо това - Ще направим това отново. Извинете артистичните си способности. Ние знаем, че не можем просто да се свърже директно от 2 до новата. Трябва да сме сигурни, че ние държим на последния. Това, което може да искате да направите, е да имат временен показалеца елемент, който ще бъде приложена на. Така че тогава ще имаме временно показалеца. Тъй като ние знаем, че това трето се съхранява следите, 2 може да се свържете с нашия нов. И дали този нов човек на червено ще бъде между 2 и 3, тогава какво е указател, който човек ще посочим? >> Студент Temp. Temp. Да. Тогава следващата стойност този червен човек ще бъде темп. Когато сте поставите в свързани списъци, видяхме, че можем лесно да добавите нещо до края, чрез създаване на временна масив, или ако искаме да се добави нещо в средата на нашия масив, а след това ще отнеме малко повече размесването на около. Ако искате, например, имат сортиран свързан списък, тогава ще трябва някак да се оценят разходите и ползите от това защото, ако искате да имате сортиран масив, това означава, че всеки път, че сте поставили в него, , че ще отнеме малко повече време. Въпреки това, ако искате да по-късно, тъй като ние ще намерим ние ще искате да търсене чрез свързан списък, а след това може да бъде по-лесно, ако знаете, че всичко е в ред. Така че може да искате да се оценят разходите и ползите от това. 

Друг начин да се вмъкнете в свързан списък е да поставите в самото начало на списъка. Ако черпим нашата котва тук - това е главата ни - и след това са тези хора, свързани с нея, и тогава ние трябва да се добавя нова точка в началото, тогава какво може да искаме да направим? Какво би било погрешно Само казвам, че искате да се свържете на червено до синьо, защото това е първото? Какво ще се случи тук? Всички тези три ще се загуби. Така че ние не искаме да направим това. Отново, ние научихме, че ние трябва да имаме някаква временна показалеца. Нека да изберат да имат временен точка за този човек. Тогава ние можем да имаме син една точка до временно и след това червен на син. Причината, поради която аз съм с хората тук е така, защото ние наистина искаме да се визуализира на хората и да сме сигурни, че имат връзка с тях преди да пусне на друга страна или нещо подобно. 

Сега, когато имаме чувство за свързани списъци - как би могло да създаде свързан списък и създаване на структури за това, състояща се от определение за вида на възел и след като се уверите, че имаме показалеца на главата на това свързано списък след като имаме, че и ние знаем как да преминават през масив, достъп до различни елементи, ние знаем как да вмъквате и ние знаем как да ги освободи, тогава можем да получим в правописни грешки. Както обикновено, ние имаме една част от въпросите, които ще се използва за работа с свързани списъци и различни структури като опашки и стекове. Тогава ние можем да преминат в правописни грешки. 

Правописни грешки в разпределението код двойка на файлове, които са от значение. Първо ние забелязваме, че имаме този Makefile тук, които не сме се срещат преди. Ако сте разглеждали в папката pset5, вие ще забележите, че имате ч. файл, имате две в. файлове. Това Makefile преди, ние просто ще въведете направи и след това името на програмата и тогава ще видите всички тези аргументи и знамена премина в компилатора. Какво Makefile прави, ни позволява да компилирате няколко файла наведнъж и преминават в тръстиката, които искаме. Тук можем само да видите, че има заглавния файл тук. Тогава ние всъщност имаме два изходни файлове. Имаме speller.c и dictionary.c. Вие сте добре дошли да редактирате Makefile, ако желаете. Забележете, че тук, ако въведете чиста, тогава това, което прави, е действително премахва всичко , която е в основата. Ако имаш сегментация вина, основно получите сметището ядро. Така че този грозен малък файл, ще се появи във вашата директория, наречена ядро. Вие ще искате да премахнете, че за да го почистите. Това премахва всички EXE файлове и О файлове. 

Нека да погледнем в dictionary.h. Това казва, че декларира функционалността речник. Ние имаме максимална дължина на всяка дума в речника. Ние казваме, че това ще бъде възможно най-дългата дума. Тя е с дължина 45. Така че ние няма да имате някакви думи, които надвишават тази дължина. Тук ние просто трябва прототипа на функция. Ние нямаме действителното изпълнение, защото това е, което ще се прави за тази pset. Но това, което прави е, тъй като ние сме се занимават с по-големи файлове тук и функционалност в по-голям мащаб, това е полезно да има з файл така че някой друг чете или да използвате код може да разбере какво става. И може би те искат да приложат опитва, ако си направил хеш таблици или обратното. Тогава те ще кажа моето функция за зареждане, действителното изпълнение ще се различават, но този прототип няма да се промени. Тук сме проверка, която връща вярно, ако дадена дума в речника. Тогава ние имаме натоварване, което основно се отнема в речника файл и след това го зарежда в някакъв структурата на данните. Имаме размер, който, когато бъде призован, връща размера на вашия речник, колко думи се съхраняват в него, и след това разтоварване, което освобождава цялата памет, която може да са взели като в същото време ви речник. 

Нека да разгледаме dictionary.c. Виждаме, че изглежда много сходна на dictionary.h, с изключение на сега просто трябва всички тези Todos в него. И така, това е вашата работа. Крайна сметка, ще се попълване speller.c с всички на този кодекс. Dictionary.c, когато тичам, не е наистина се случва да правите нищо, така че ние гледаме към speller.c, за да видите реалното изпълнение на проверка на правописа. Дори и да не започваш да се редактиране на този кодекс, че е важно да се чете, да се разбере, когато се нарича натоварване, когато съм обаждаш проверка, само за да разберете, че се набележат, за да видим как работи функцията. Ние виждаме, че това е проверка за правилното използване. По същество, когато някой работи правопис, това показва, че това е задължително те да преминат в речника файл, защото там ще бъде файл речник по подразбиране. И тогава те трябва да преминат в текста на правописа проверява. на rusage сделки с течение на времето, тъй като част от този pset които ние ще се справим с по-късно не е само получаване функциониране на програмата за проверка на правописа работи но всъщност да е тя да бъде бързо. И така, това е мястото, където rusage ще дойде инча Ето, виждаме първата покана на един на нашите dictionary.c файлове, което е натоварване. Load връща истина или лъжа - вярно при успех фалшиви при неизпълнение. Така че, ако речника не е поставена правилно, тогава speller.c ще се върне един и напусна. Но ако тя се зарежда правилно, тогава е щял да продължи. Ние продължаваме и ние виждаме някой файл I / O, къде ще се занимава с отваряне на текстов файл. Ето, това, което прави е на правописа проверява всяка една дума в текста. Така че това, което speller.c прави точно тук е итерации всяка една от думите в текстов файл и след това да ги проверява в речника. Тук, ние имаме сгрешена Булев, които ще видите, ако проверката се връща истина или не. Ако думата е всъщност в речника, а след това проверка ще се върне вярно. Това означава, че думата не е сгрешена. Така сгрешена би било невярно, и това е защо ние имаме взрив там, посочване. Ние продължаваме да отиде, и след това го следи колко неправилно изписани думи има във файла. Тя продължава и затваря файла. Тогава тук, той докладва колко сгрешените думи. Той изчислява, колко време да се зареди речника, колко време да го проверите, колко време го взе за изчисляване на размера, , тъй като ние ще отидем, трябва да бъде много малка, и след колко време да се разтоварят речника. Ето до горе виждаме поканата да се разтоварят тук. Ако ние проверяваме за размера тук, после виждаме, че тук е призивът на размера, когато определя размера на речника. Страхотно. 

Нашата задача за тази pset е за изпълнение на товара, който ще се зареди речника структурата на данните - Каквото и да изберете, било то хеш таблица или да опитате - с думи от речника файл. След това трябва размер, който ще се върне на броя на думите в речника. И ако решите да реализирате натоварване по интелигентен начин, тогава размер трябва да бъде доста лесно. След това можете да проверите, която ще провери дали дадена дума в речника. Така speller.c преминава в низ, и тогава ще трябва да се провери дали тази струна се съдържа в речника си. Забележете, че ние по принцип са стандартни речници, но в този pset, основно речника премина в какъвто и да е език. Така че ние не можем просто да приемем, че думата е вътре. В определен речник Думата Foobar може да се определи, че минаваме. И тогава ние сме разтоварване,, което освобождава речник от паметта. 

Първо, бих искал да отида хеш таблицата метод за това как бихме могли да се приложат всички тези четири функции, и тогава аз ще отида опитва метод, как ние прилагаме тези четири функции, и в края поговорим за някои общи съвети, когато сте прави pset , а също и как може да сте в състояние да използват Valgrind за да проверите за изтичане на памет. 

Нека се в хеш таблицата метод. Хеш таблица се състои от списък на кофи. Всяка стойност, всяка дума, ще отиде в един от тези кофи. Хеш таблица идеално разпределя равномерно всички тези ценности, че сте преминаване в и след това ги населяват в кофата по такъв начин, че всеки кофа има равен брой на ценностите в него. Структура за хеш таблица, имаме набор от свързани списъци. Какво правим, когато преминем в стойност, ние проверяваме, където тази стойност трябва да принадлежат, кофа принадлежи, и след това го поставете в свързан списък, свързан с тази кофа. Ето, това, което имам, е хеш функция. Това е INT хеш таблица. Така че за първата страница, всички числа под 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-> дума. Това съдържа дума от речника, че искаме да въведете. Така че това, което искаме да направим е, че ние искаме да се обадите на нашия хеш функция на тази струна защото нашата хеш функция в низ и след това се връща цяло число, където това число е индекс, при Hashtable в този индекс представлява тази кофа. Искаме да вземем този индекс и след това отидете на този индекс на хеш таблица и след това да използвате тази свързан списък, за да вмъкнете възел в new_node. Не забравяйте, че все пак решите да поставите вашия възел, независимо дали е в средата, ако искате да я сортирате или в началото или в края, просто се уверете, че последният ти възел винаги сочи към NULL защото това е единственият начин, че ние знаем къде последният елемент от свързани нашия списък. 

Ако размерът е цяло число, което представлява броя на думите в речника, един начин да направите това е, че всеки път, когато размерът се нарича ние преминаваме през всеки елемент в хеш нашата трапеза и след това през всеки свързан списък в хеш таблица превъртите и след това да се изчисли дължината на увеличаване на нашия брояч 1 от 1. Но всеки път, когато се казва, че размерът, че това ще отнеме много време защото отиваме да бъде линейно сондиране всеки един свързан списък. Вместо това, тя ще бъде много по-лесно, ако можете да следите колко думи са преминали. Значи, ако включите брояч в рамките на Вашия товар функция актуализации, колкото е необходимо, а след това контра, ако сте задали в глобална променлива, ще могат да бъдат достъпни по размер. Така че, какъв размер може просто да направи е в един ред, просто връщат стойността на брояча, размер на речника, който вече се занимава с натоварване. Това е, което имах предвид, когато казах, ако приложи натоварване по полезен начин, тогава размер ще бъде доста лесно. 

Така че сега ние да се провери. Сега си имаме работа с думи от файла за въвеждане на текст, и затова ще трябва да се провери дали всички тези входни думи всъщност са в речника или не. Подобно на Scramble, ние искаме да се даде възможност за случай нечувствителност. Вие искате да сте сигурни, че всички думи, приет през, въпреки че те са смесени случай, когато бъде призован с низ сравнения, са еквивалентни. Думи в речника текстови файлове са действително с малки букви. Друго нещо е, че може да се предположи, че всяка дума прие, всеки стринг, ще бъде азбучен ред или съдържа апострофи. Апострофи ще бъдат валидни думи в нашия речник. Така че, ако имате дума с апостроф S, това е действително легитимен дума в речника си , че това ще бъде един от възлите в хеш таблицата. Проверете работи, ако думата съществува, тогава той трябва да бъде в хеш нашата маса. Ако думата е в речника, а след това всички думи в речника са в хеш таблица, така че нека да погледнем за тази дума в хеш таблица. Ние знаем, че, тъй като ние въведохме нашата хеш функция такова, че всяка уникална думата винаги се сегментира на същата стойност, тогава знаем, че вместо да търсят през целия си целия хеш таблица, ние всъщност може да намерите свързан списък, че тази дума трябва да принадлежат на Ако беше в речника, то би било в тази кофа. Какво можем да направим, ако думата е името на нашия низ, приет през Ние можем само да хеш тази дума и поглед към свързан списък стойността на Hashtable [хеш (дума)]. От там, какво можем да направим е, че има по-малък подмножество на възли за търсене на тази дума, и така можем да прекосяват свързан списък, с помощта на пример от по-рано в помагалото, и след това се обадете низ сравнение със словото, където курсорът се посочи, тази дума, и да видим дали тези сравнение. В зависимост от начина, по който организирате вашата хеш функция, ако това е сортиран, може да сте в състояние да се върне фалшиви малко по-рано, но ако това е сортиран, а след това искате да продължите преминаващи през свързали списък докато не се намери последния елемент на списъка. И ако все още не са намерили думата от времето, когато сте достигнали края на свързан списък, това означава, че вашата дума не съществува в речника, и така тази дума е невалидна, и проверката трябва да се върне фалшиви. 

Сега стигаме до разтоварване, където искаме да освободи всички възли, които са malloc'd толкова свободно всички възли вътре в хеш нашата маса. Отиваме да искат за обхождане на всички свързани списъци и да освободи всички възли в това. Ако се вгледате по-горе в помагалото например, където ние освобождаваме свързан списък, тогава вие ще искате да повторите този процес за всеки елемент в хеш таблица. И аз ще отида към края на помагалото, но Valgrind е инструмент, където можете да видите, ако правилно сте освободени всеки възел, който сте malloc'd или нещо друго, което сте malloc'd, всяка друга показалеца. Така че това е хеш таблици, където имаме ограничен брой кофи и хеш функция, която ще отнеме стойност и след това присвоите стойност до известна кофа. 

Сега стигаме до опита. Опитва вид изглежда така, и аз ще извади един пример. Принцип, имате цял набор от потенциални писма, и след това, когато сте изграждане на думата, това писмо може да бъде свързана за речника на широка гама от възможности. Някои думи започват с C, но след това продължи с но други продължават с O, например. Trie е начин за визуализиране на всички възможни комбинации от тези думи. Trie се случва, за да следите на поредица от писма, които включват думи, отклоняване, когато е необходимо, когато едно писмо може да бъде последвано от кратно на писма, и в края показват, във всяка точка, независимо дали тази дума е валиден или не защото ако сте правописа на думата MAT, MA Не мисля, че е валидна дума, но МАТ е. И така във вашата Trie, би означавало, че след МАТ, това всъщност е валидна дума. Всеки възел в нашата Trie всъщност ще съдържа набор от възли указатели, и ние ще трябва, по-специално, 27 от тези възел указатели, един за всяка буква от азбуката, както и апостроф характер. Всеки елемент в този масив се ще да сочи към друг възел. Така че, ако този възел е NULL, ако няма нищо след това, тогава ние знаем, че няма никакви допълнителни букви в тази дума последователност. Но ако този възел не е NULL, това означава, че има повече писма в това писмо, последователност. И освен това, всеки възел показва дали това е последния знак на думата или не. 

Нека отидем в пример на Trie. Първо имам място за 27 възела в този масив. Ако имам думата BAR - Ако имам думата BAR и аз искам да вмъкнете, че в първата буква Б, така че ако ми Trie е празна, B е втората буква от азбуката, така че аз отивам да избират дали да сложа това тук в този индекс. Отивам да имат Б тук. B ще бъде възел, който сочи към друг масив от всички възможни символи , които могат да следват след буквата Б. В този случай, аз се занимавам с думата BAR, така че ще отидете тук. След, имам буквата R, така че след това вече точки на своя комбинация, и след това R ще бъде тук. BAR е завършена дума, така че тогава аз отивам да имат R точка за друг възел , който казва, че тази дума е валидна. Това възел също ще имат множество от възли, но тези, които може да бъде NULL. Но в основата си той може да продължи по този начин. Това ще стане малко по-ясно, когато отидем в друг пример, така че просто носят с мен. Сега имаме BAR вътре в нашия речник. Сега казват, че имаме думата BAZ. Започваме с B, и ние вече имаме Б като един от писмата, които в нашия речник. Това е последвано с А. имаме вече. Но след това вместо да имаме Z-долу. Тогава елемент в нашата масив ще бъде Z, и така, че един ще посочим с друг валиден края на думата. Така виждаме, че когато ние продължаваме през Б и след това, има два различни варианта в момента са в нашия речник за думи, които започват с B и A. Да речем, ние искахме да вмъкнете Foobar дума. Тогава ние ще извърши вписване на F. F е възел, който сочи към целия масив. Ние ще намерите O, до О, о, тогава се свързва с цял списък. Щяхме да имаме Б и след това да продължи, трябва да имаме и след това R. Тогава Foobar пресича целия път надолу, докато Foobar е правилната дума. И така, то това ще бъде валиден дума. Сега казват, че всъщност е нашата следваща дума в речника думата FOO. Бихме казали, F. Какво следва F? Аз всъщност вече има място за О, така че аз съм щял да продължи. Не трябва да се направи нова. Продължи. FOO е валидна дума в този речник, така че след това отивам да се посочи , че това е валидно. Ако спра последователност ми там, това би било правилно. Но ако ние продължихме нашата последователност от FOO B и просто трябваше FOOB, FOOB не е една дума, а това не е посочено като валиден. В Trie, всеки възел се посочва дали е валиден дума или не, и след това всеки възел има масив от 27 възел указатели че след това посочете възли самите. 

Ето един начин, как може да искате да се определи това. Все пак, точно както в хеш таблицата например, когато сме имали възел главата * за да покаже началото на свързаното нашия списък, ние сме също така ще искате някакъв начин да знае къде началото на нашата Trie. Някои хора наричат ​​се опитва дървета, и това е мястото, където корен идва от. Така че ние искаме основата на нашето дърво, за да се уверите, че ние останеш верен там, където ни Trie. Ние вече се приближи начина, по който можеше да мисли за зареждане на всяка дума в речника. Същество, за всяка дума, вие ще искате да превъртате чрез вашия Trie и знаейки, че всеки елемент в децата - ние го наричат ​​децата в този случай - съответства на различна буква, вие ще искате да проверите тези стойности в този конкретен индекс, който отговаря на писмото. Така че мисля по целия път обратно към Цезар и Vigenere, знаейки, че всяка буква може да се вид на картата обратно към азбучен указател, определено от А до Z ще бъде доста лесно да се очертаят азбучен писмо, но за съжаление, апострофи и приета характер с думи. Аз дори не съм сигурен какво ASCII стойност е така, че ако искате да намерите индекс, за да решите дали искате тя да бъде нито първата или последният, ще трябва да се направи трудно кодирани проверка за това и след това пуснати, че в индекса на 26, например. Тогава проверка на стойност към децата [I] [I] съответства какъвто и да е писмо сте. Ако това е NULL, това означава, че в момента не е евентуални писма , произтичащо от предишната серия, така че вие ​​ще искате да изчистване и да направи нов възел и че децата [I] точка за , така че да се създаде - когато сме поставили писмо в правоъгълник - да накараш децата да непразна и точка в този нов възел. Но ако това не е NULL, като в случай на FOO , когато вече имахме Foobar, ние продължаваме, и ние не сме някога направи нов възел, а само за определяне is_word да е истина в края на тази дума. 

Тогава, както и преди, защото тук се занимават с всяка буква в даден момент, , че ще бъде по-лесно за вас размер, вместо да се налага да се изчисли и да премине през цялото дърво и да се изчисли колко деца имам и след това отклоняване, спомняйки си колко са от лявата страна и от дясната страна и такива неща, тя ще бъде много по-лесно за вас ако просто да следите колко думи вие добавяте в когато имаш работа с товар. И така, след това начина, по който този размер може просто да се върне глобална променлива от размера. 

Сега ние идваме да се провери. Същите стандарти, както преди, когато искаме да се даде възможност за случай нечувствителност. Както е добре, ние предполагаме, че конците са само букви от азбуката или апострофи защото децата е масив от 27 дълго, така че всички букви от азбуката плюс апостроф. За да проверите какво вие ще искате да направите, е, вие ще искате да започнете в основата защото коренът ще сочи към масив, който съдържа всички възможни началните букви на думата. Ти ще започнем от там, и тогава започваш да проверите е тази стойност NULL или не, защото, ако стойността е NULL, това означава, че речникът не са изпитали някакви стойности , които съдържат това писмо в тази конкретна цел. Ако това е NULL, то това означава, че думата е сгрешена веднага. Но ако това не е NULL, тогава можете да продължите, се каже, че първото писмо е възможно първата буква в думата, така че сега искам да се провери дали второ писмо, тази серия е в моя речник. Така че ще отидем на индекса на децата на първо възел и да се провери дали съществува второто писмо. След това се повтаря този процес, за да се провери дали тази последователност е валиден или не в рамките на Trie си. Когато възел деца в този индекс точки NULL, ли, че тази последователност не съществува, но след това, ако стигнат до края на думата, че сте въведена, тогава искате да проверите сега, че сте завършили тази последователност и го е намерил в моята Trie е, че думата валиден или не? И така, след това искате да проверите, че и това е, когато, ако сте установили, че последователността, тогава искате да проверите дали тази дума е валиден или не защото си спомни в предишния случай, че привлече където имахме FOOB, че е валиден последователност, която ние открихме, но не е действително валидна самата дума. 

По същия начин, за разтоварване в опитите, които искат да се разтоварят всички възли в Trie си. Извинете. Подобно на хеш таблици, където в разтоварят освободени всички възли, в опитите искаме да освободи всички възли. Разтоварете действително ще работи най-лесно от дъното към върха тъй като те са по същество свързани списъци. Така че ние искаме да се уверите, че държим на всички стойности и безплатно всички от тях изрично. Това, което ще искате да направите, ако работите с Trie е да пътуват до дъното и да освободи възможно най-ниската възел и след това отидете до всички тези деца и след това без всички онези, и след това безплатно, и др. Нещо като занимаващи се с долния слой на Trie първа и след това отидете до върха, след като веднъж сте освободени всичко. Това е един добър пример за рекурсивна функция, може да дойде по-удобно. След като сте освободени долния слой на Trie си, тогава ти се обадя разтоварване на останалата част от него, като се уверите, че ви освободи всеки мини - Можете да вид визуализира като мини опита. Така че тук имате корен. Аз съм просто за опростяване, така че аз не трябва да изготвят 26 от тях. Така че имате някои от тези, а след това те представляват последователности от думи където всички тези малки кръгчета са писма, които са валидни секвенции на писмата. Да продължим малко повече. Това, което вие ще искате да направите, е свободен дъното и след това този и след това този на дъното, преди да освободи горната тук защото, ако нещо тук във второто ниво тогава всъщност ще загубят тази стойност. Ето защо е важно в разтоварване за Trie, за да се уверите, че първата ви освободи дъното. Какво може да искате да направите, е да се каже за всеки възел Искам да се разтоварят всички деца. 

Сега, след като сме преминали през разтоварване за хеш метод маса, както и метода Trie, отиваме да искате да погледнете в Valgrind. Valgrind работи със следните команди. Valgrind-V. Ти проверка за всички течове, когато стартирате правопис, като се има предвид този определен текст защото правописа трябва да се вземат в текстов файл. Така Valgrind ще продължи програмата си, да ви кажа колко байта разпределени, колко байта освободени, и тя ще ви каже дали ще освободи достатъчно или дали не безплатно достатъчно, или понякога можете да дори по-свободно, като безплатен възел, които вече са освободени и така тя ще ви върне грешки. Ако използвате Valgrind, тя ще ви даде някои съобщения показва дали сте освободени или по-малко от достатъчно, просто достатъчно, или повече от достатъчно пъти. 

Част на този pset, че е задължително да се оспори The Big съвет. Но когато си имаме работа с тези структури от данни това е нещо забавно да се види колко бързо и колко ефективно структури от данни може да бъде. Има ли вашата хеш функция в резултат много сблъсъци? Или данни размерът наистина голям? Отнема много време да преминават? В дневника на правопис, да подава, колко време използвате, за да се зареди, да се провери, да провежда размер, както и да се разтоварят, и така тези, които са публикувани в The Big съвет, , където можете да се състезавате срещу съучениците си и някои членове на персонала, за да видим кой е най-бързата проверка на правописа. Едно нещо, което бих искал да отбележа, за хеш-таблици е, че има някои доста прости хеш функции, които бихме могли да се сетите. Например, имате 26 кофи, и така всеки кофа съответства на първата буква в думата, но това ще доведе до доста небалансирано хеш таблица , защото има много по-малко думи, започващи с X от началото с М, например. Един от начините да отида за правопис е, ако искате да получите всички други функции надолу, след това просто да използвате един прост хеш функция, за да бъде в състояние да получите код, работещ и след това се върна и да променя размера на хеш маса и дефиниция. Има много ресурси в Интернет за хеш функции, и така за тази pset ви е позволено да изследват хеш функции в Интернет за някои съвети и вдъхновение, стига да Уверете се, че да се цитират, когато сте го получили от. Вие сте добре дошли да изглеждате и да се изтълкуват някои хеш функция, които ще намерите в интернет. Обратно на това, може да сте в състояние да видите дали някой използва Trie дали изпълнението им е по-бързо, отколкото хеш вашата маса или не. Тук можете да подадете The Big съвет няколко пъти. Тя ще запише най-скорошното влизане. Така че може би промените хеш функция и след това осъзнават, че това е действително много по-бързо или много по-бавно от преди. Това е малко на един забавен начин. Винаги има една или две членове на персонала, които се опитват да направят възможно най-бавния речник, така че винаги е забавно за гледане. 

Използването за pset е тече правопис с допълнителен речник и след това задължително текстов файл. По подразбиране, когато стартирате правопис само с текстов файл и не уточняват речник, ще използва файла на речника текст, голям в папка, на cs50/pset5/dictionaries. Това има над 100 000 думи. Те също имат малък речник, който има значително по-малко думи CS50 е направен за вас. Въпреки това, вие може много лесно просто да направите своя собствена речник ако просто искате да се работи в малки примери - Например, ако искате да използвате GDB и вие знаете, конкретните стойности , който искате хеш таблица, за да се очертаят. Така че можете просто да направите своя собствена текстов файл само с БАР, Баз, FOO и Foobar направи това в текстов файл, отделете тези с 1 ред, и след това да направите своя собствена текстов файл, който буквално съдържа само може би един или два думи така че да знаете какво точно изходът ще бъде. Някои от примерните файлове с текст, че Големият съвет, когато стартирате предизвикателство, ще се провери Война и мир "и романа на Джейн Остин или нещо подобно. Така че, когато сте се започне, това е много по-лесно да направите свои собствени текстови файлове , които съдържат само няколко думи или може би 10 , така че да може да се предскаже какъв ще е изходът трябва да бъде и след това да го сравнят с това, така повече от контролирана например. И така, тъй като ние сме се занимават с прогнозиране и изготвяне на нещата около отново искам да ви насърча да използвате хартия и писалка , защото наистина ще ви помогне с това - изготвяне на стрели, как хеш таблица или как Trie изглежда, , когато сте освобождаването нещо, когато стрелките ще провеждане на достатъчно, виждаш ли всички връзки изчезват и попадащи в бездната на изтекла памет. Така че, моля, моля, опитайте да рисуват неща, дори и преди да стигнем до писането на код за определяне. Рисуват неща, за да разберете как се развиват нещата да работят защото тогава ти гарантирам, че ще се сблъскате по-малко muddles на показалеца. 

Добре. Искам да ви пожелая най-доброто от късмет с този pset. Това е може би най-трудното. Затова се опитайте да започне работа в началото, изготвя нещата, изготвя нещата и добър късмет. Това е репетиция 5. 

[CS50.TV]