[Powered by Google Translate] [Раздел 6] [по-комфортно]
[Роб Bowden] [Харвардския университет]
[Това е CS50. [CS50.TV]
>> Ние можем да се отправят към нашата секция на въпроси.
Пратих URL за интервал преди.
В началото на част от въпросите, казват
явно аз не съм изцяло unsick е много лесен въпрос
на какво точно се valgrind?
Какво се valgrind направя?
Някой иска ли да каже какво прави valgrind?
[Student] проверява изтичане на памет.
Да, valgrind е общ за проверка на паметта.
Това, в крайна сметка, ти казва, ако имате някакви изтичане на памет,
, която е най-вече това, което ние го използвате, защото ако искате да
се справят добре в проблема набор или ако искате да
да получите на големия съвет, имате нужда от каквато и да няма изтичане на памет,
и в случай, че има изтичане на памет, че не можете да намерите,
също така имайте предвид, че всеки път, когато отворите файл
и ако не го затворите, това е изтичане на памет.
>> Много хора се търсят за някои възел, че те не са освобождаване
когато наистина, те не затворите речник в най-първата стъпка.
Той също така ви казва, ако имате някакви невалиден чете или пише,
което означава, че ако се опита и задайте стойност
това е отвъд края на куп и това не се случи сегмента вина
но valgrind я хваща, тъй като не трябва да се пише там,
и така вие определено не трябва да има някое от тези или.
Как да използвате valgrind?
>> Това е общ въпрос
вид, стартирайте го и на изхода.
Изходът е поразителен много пъти.
Има също така и забавни грешки, където, ако имате някаква ужасно нещо погрешно
случва в една линия, а след това в крайна сметка ще кажа, "твърде много грешки.
Отивам да спре да брои сега. "
Това е основно текстова продукция, която трябва да се направи разбор.
В крайна сметка, тя ще ви каже изтичане на памет, които имате,
колко блокове, които могат да бъдат полезни, защото
ако това е един блок unfreed, тогава това е обикновено е по-лесно да се намери
от 1000 блокове unfreed.
1000 блокове unfreed вероятно означава, че не освобождава
свързани списъци по подходящ начин или нещо такова.
Това е valgrind.
>> Сега имаме нашата секция на въпроси,
които не е нужно да изтеглите.
Можете да кликнете върху името ми и ги издърпайте нагоре в пространството.
Сега кликнете върху мен.
Преглед на 1 ще бъде стека, което правим първото.
Revision 2 ще бъде опашка и ревизия 3 ще бъде поотделно свързан списък.
Започвайки с нашия стак.
Както се казва тук, комин е един от най-основните,
основните структури от данни на компютърната наука.
Много прототипни пример за това е
стека на плочки в трапезарията.
Това е основно, когато се запознават с комин,
някой ще каже: "О, като купчина тави".
Можете стека тава.
Тогава, когато отидете да дръпнете поднос,
първата тава, която ще се извади, е последният, който е бил пуснат на стека.
Стак също така като казва тук
имаме сегмент на памет, наречена стека.
И защо се нарича стека?
>> Тъй като структурата на стека данни,
настоява и се появи стека рамки на стека,
където стаковете рамки са като специална покана на функция.
И като комин, винаги ще трябва да се върне
от извикване на функция, преди да можете да получите на олекотени рамки стека отново.
Не можете да имате повикване Foo повикване бар и връщане бар на основното директно.
Винаги трябва да следи за правилното стека бутане и мак.
Две операции, както казах, са тласък и поп.
Това са универсални термини.
Трябва да знаете, натискане и поп в условията на стекове без значение какво.
Ще видим опашки са вид на различни.
Всъщност няма универсален план, но тласък и поп са универсални за стакове.
Push е само на стека.
Поп е излитане стека.
И ние виждаме тук ние имаме typedef стека структура,
така че ние имаме Чар струни **.
Да не се получи плаши от никакви **.
Това е в крайна сметка ще е масив от низове
или масив от указатели към символи, където
указатели към героите са склонни да бъдат струни.
Тя не трябва да бъде струни, но тук, те ще бъдат струни.
>> Ние имаме масив от низове.
Имаме размер, което представлява колко елементи са в момента на стека,
и ние имаме капацитет, което е колко елементи могат да бъдат в стека.
Капацитет трябва да започне като нещо по-голямо от 1,
но размерът ще започне като 0.
Сега там са основно три различни начини, по които можеш да се сетиш на комин.
Е, там вероятно са повече, но два основни начина
можете да го въведе масив, или да го изпълни с помощта на свързан списък.
Свързани списъци са вид тривиално да направи купища.
Много е лесно да се направи комин с помощта на свързани списъци,
така че тук, ние ще направим комин употребата на масиви,
и след това с помощта на масиви, има и два начини, по които можете да се сетите за това.
Преди, когато казах, че имаме капацитет за стека,
така че ние може да се побере елемент на стека.
>> Единственият начин може да се случи веднага след като удари 10 елемента, а след това сте готови.
Може би знаете, че има горна граница от 10 неща в света
че никога няма да има повече от 10 неща на вашия стак,
в който случай може да има горна граница на размера на стака си.
Или бихте могли да имат вашия стак безгранична,
но ако правиш масив, това означава, че всеки път, когато удари 10 елемента,
това означава, че ще трябва да нарасне до 20 елемента, и когато ви удари 20 елементи,
вие ще трябва да развиете своя масив до 30 елементи или 40 елементи.
Вие ще трябва да се увеличи капацитет, което е това, което ние ще направим тук.
Всеки път стигаме до максималния размер на нашия стак,
когато натиснете нещо друго, ние ще трябва да увеличи капацитета.
Ето, ние тласък декларирани като булев натискане (Чар * ул.).
Чар * ул. е низ, че ние се мъчим върху стека,
и булев просто казва дали сме успели или не са успели.
>> Как можем да се провали?
Каква е само обстоятелството, че можеш да се сетиш
когато ние ще трябва да се върне фалшива?
Да.
Студентски] Ако това е пълна и ние използваме ограничена изпълнение.
Да, така как ние определяме той отговори
ако тя е пълна и ние използваме ограничена изпълнение.
След това със сигурност ще се върне фалшиви.
Веднага след като удари 10 неща в масива, ние не може да се побере 11, така че връщане фалшиви.
Какво ще стане, ако тя е безгранична? Да.
Ако по някаква причина не можете да разширите масив.
Да, така паметта е ограничен ресурс,
и в крайна сметка, ако продължаваш да се бориш неща върху стека отново и отново,
ние ще се опитаме и да заделят по-голям масив да се поберат
ще се върне по-голям капацитет, и изчистване или каквото и да използвате фалшив.
Е, изчистване ще се върне празно.
>> Не забравяйте, че всеки път, когато някога се обръщат изчистване, трябва да бъдат проверка да се види дали
връща нула или друго, което е за вярност приспадане.
Тъй като искаме да имаме неограничено стак,
единственият случай, ние ще се завърне невярно е, ако ние се опитваме да
увеличаване на капацитета и изчистване или каквото и да връща.
Тогава поп не възприема аргументи,
и го връща низ, който е на върха на стека.
Каквото и да е най-скоро търсената върху стека е какво поп се връща,
и тя също така премахва от стека.
И забележите, че той се връща нула, ако няма нищо в стека.
Той винаги е възможно, че стека е празен.
В Java, ако сте свикнали с това, или на други езици,
се опитва да изскочи от празна стак може да предизвика изключение или нещо такова.
>> Но в C, нула е на много случаи, в начина, по който се справят с тези проблеми.
Връщането на нула е как ние ще означава, че стека е празен.
Сме предоставили кода, който ще тества функционалността на вашия стак,
изпълнение натиснете и поп.
Това няма да е много код.
Ще го направя - всъщност, преди да направите това, намек, намек-
ако не сте го виждали, изчистване не е единствената функция
, която заделя памет на куп за вас.
Има семейството на заделянето на памет функции.
Първата е изчистване, което сме свикнали да.
Тогава там е calloc, който прави същото нещо като изчистване,
но това ще нулира всичко за вас.
Ако някога сте искали да зададете всичко на нула, след mallocing нещо
трябва да сте просто използва calloc на първо място, вместо на писане
за линия до нула за целия блок от паметта.
>> Презаделяне е като изчистване и има много специални случаи,
но в общи линии какво презаделяне
отнема показалеца, които вече са били разпределени.
Презаделяне е функцията, която искате да се обръща внимание тук.
Това отнема показалеца, които вече са били върнати от изчистване.
Да речем, че поиска от изчистване на показалеца на 10 байта.
По-късно осъзнаваш, че искаш 20 байта,
така ти се обадя презаделяне на тази показалеца с 20 байта,
и презаделяне автоматично ще копира всичко за вас.
Ако току що се обади изчистване отново, като имам блок от 10 байта.
Сега имам нужда от блок от 20 байта,
така че, ако изчистване 20 байта, тогава аз трябва да копирате ръчно над 10 байта от първото нещо,
във втората нещо и след това първото нещо.
Презаделяне ще се справят с това за теб.
>> Забележете подпис ще бъде нищожен *,
която е просто връщане на показалеца на блок от памет,
тогава нищожен * PTR.
Можете да мислите за нищожен * като родово показалеца.
Като цяло, никога няма да се справят с нищожен *,
но изчистване се завръща нищожен *, и след това просто се използва като
това всъщност ще бъде знак *.
Предишната * нищожен, които са били върнати от изчистване
вече ще бъдат предадени на презаделяне, и след това размер
е новият брой на байтовете, които искат да се отпуснат, така че нови мощности.
Ще ви дам няколко минути, и да го направя в нашето пространство.
Започнете с Преработка 1.
Аз ще ви спре след като се надяваме за достатъчно време да изпълнят тласък,
и след това аз ще ви дам още една почивка, за да се направи поп.
Но това наистина не е, че много код на всички.
Най-код вероятно е разширяване на неща, разширяване на капацитета.
Добре, няма натиск да бъдат напълно прави,
но толкова дълго, колкото се почувствате сякаш сте на прав път, това е добре.
>> Някой има ли код, те се чувстват комфортно с мен дърпа нагоре?
Да, ще го направя, но не всеки има код на приложението, който може да тегли до?
Добре, може да започнете, да го запишете, каквото и да е то?
Аз винаги забравям тази стъпка.
Добре, при натискане,
искам да обясните вашата код?
[Student] Преди всичко, аз увеличи размера.
Предполагам, че може би трябва да има, че така или иначе, аз увеличи размера,
и аз виждам, ако това е по-малко от капацитета.
И ако това е по-малко от капацитета, добавя към масива, че вече имаме.
И ако не е, ще умножа капацитет от 2,
и аз да преразпредели струни масив за нещо с по-голям капацитет.
И тогава, ако това не стане, казвам на потребителя и връщане фалшиви,
и ако всичко е наред, след това сложих низ в ново място.
>> [Роб Б. Също така забележете, че ние използвахме хубава оператор побитови тук
се умножава по две.
Не забравяйте, че олевяване винаги ще се умножава по две.
Право промяна е разделен на две толкова дълго, колкото не забравяйте, че това означава,
разделете на две, както в цяло число, разделено на две.
Тя може да се отреже 1 тук или там.
Но промяна, оставена от 1 винаги ще се умножава по две,
освен ако не препълване на обхвата на целочисления, и след това тя няма да бъде.
А страна коментар.
Харесва ми да направя това не се случва за промяна на кодирането никакъв начин,
но обичам да правя нещо подобно.
То всъщност се случва да го правят малко по-дълго.
Може би това не е идеалния случай да се покаже това,
но ми харесва да сегмент в тези блокове-
добре, ако това, ако се случи, тогава аз ще направя нещо,
и след това функцията е направено.
Не трябва след това да превъртите очите ми по целия път надолу функцията
да видим какво ще стане след друго.
Това е, ако това, ако се случи, тогава аз просто се върне.
Той също така има хубаво допълнителна полза от всичко след това
сега е изместен веднъж на ляво.
Аз вече не се налага да, ако някога в близост до безумно дългите линии,
тогава тези 4 байта може да помогне, а също и по-ляво нещо е,
по-малко претоварени се почувствате, ако искал-добре, трябва да се помни
Аз съм в момента в линия, докато във вътрешността на друг вътрешността на линия.
Където и да може да направи това завръщане веднага, мен ми харесва.
Това е напълно по желание и не се очаква по какъвто и да е начин.
>> Студентски] Трябва ли да има размери - в провалят състояние?
Се провалят условие тук е, че ние не успя да презаделяне, така че да.
Забележете как в непременно условие, вероятно,
освен ако ние безплатни неща по-късно, ние винаги ще се провалят
без значение колко пъти ние се опитваме да прокара нещо.
Ако продължаваш да се бориш, ние продължаваме увеличаване размера,
въпреки че ние не поставяме нищо върху стека.
Обикновено ние не увеличите размера, докато
след като успешно са го постави на стека.
Ние ще го направя, да речем, тук и тук.
И тогава вместо да каже s.size ≤ капацитет, това е по-малко от капацитета,
само защото ние се преместихме, където всичко беше.
>> И помнете, единственото място, което бихме могли да евентуално връщане фалшиви
е тук, където презаделяне връща нула,
и ако се случи да се помни, стандартна грешка,
може би ще може да разгледа този случай, когато искате да отпечатате стандартна грешка,
така fprintf STDERR вместо просто директен печат на стандартния изход.
Отново, това не е очаквания, но ако това е грешка,
въведете ФОРМАТ, тогава може да искате да го отпечатате на стандартната грешка вместо на стандартния изход.
>> Всеки, който има нещо друго, за да се отбележи? Да.
[Student] Може ли да отидете над [недоловим]?
[Rob B.] Да, действително binariness от него или от това, което е?
[Student] Значи го умножете по две?
[Rob B.] Да, общо взето.
В двоичен земя, ние винаги имаме набор от цифри.
Този променящ ляво от 1 По същество това вложки Тук, в дясната страна.
Върнете се в това, просто се забравя, че всичко в двоичен
е с мощност от 2, така че това представлява 2 до 0,
2 към 1, този 2 на 2.
Чрез въвеждане от 0 до дясната страна, ние просто смени всичко.
Какво да бъде 2 на 0 сега е 2 към 1, 2 на 2.
Дясната страна, че сме поставили
е задължително да бъде 0,
което има смисъл.
Ако някога сте се размножават номер 2, това няма да се свърши странно,
така трябва да бъде от 2 до мястото 0 0,
и това е, което едва ли не предупреди за това, преди да е, ако ви се случи да се променя
извън броя на битовете в цяло число,
след това 1 ще свърши тръгна.
Това е единственото притеснение, ако се случи да се занимава с наистина големи възможности.
Но в този момент, а след това сте се занимават с набор от милиарди неща,
, които не могат да се поберат в паметта, така или иначе.
>> Сега ние можем да стигнем до поп, което е още по-лесно.
Може да ми харесва, ако се случи да се появи цял куп,
и сега сте на половин капацитет.
Можете да презаделяне да се свие размера на паметта имате,
но вие не трябва да се тревожи за това, така че единственият случай презаделяне ще бъде
отглеждането на паметта, никога не свива памет,
която ще направи поп супер лесно.
Сега опашки, които ще бъдат като стакове,
но за да ви отведе нещата да се отпише.
Прототипният пример на опашката е една линия,
така че предполагам, ако бяха англичани, бих казал,
прототип на пример на опашката е опашката.
Така че, като, ако сте първият човек, в съответствие,
очаквате да бъде първият човек на линията.
Ако сте последният човек в съответствие, ще бъде последният човек, трябва да се ремонтира.
Ние наричаме това FIFO модел, като има предвид, че стека е LIFO модел.
Тези думи са доста универсални.
>> Както стакове и за разлика от масиви, опашки обикновено не позволява достъп до елементите в средата.
Тук комин, ние имаме тласък и поп.
Ето, ние се случи да ги призовал enqueue и dequeue.
Аз съм чувал и ги нарича смяна и unshift.
Съм чувала хора да казват тласък и поп да се прилага по отношение на опашки.
Чувал съм, поставяйте, не изваждайте,
натиснете и поп, ако говорим за стакове, се мъчим и мак.
Ако говориш за опашки, бихте могли да изберете думите, които искате да използвате
за поставяне и премахване, и няма консенсус за това какво трябва да се нарича.
Но тук имаме enqueue и dequeue.
Сега, структура изглежда почти идентичен с стека структура.
Но ние трябва да следим на главата.
Предполагам, че се казва тук, но защо ние се нуждаем от главата?
Прототипите са основно еднакви, за да прокара и поп.
Можете да мислите за него като натискане и поп.
Единствената разлика е, поп се връща, вместо на последния, е връщането на първо.
2, 1, 3, 4, или нещо такова.
И тук е началото.
Нашата опашката се напълни догоре, така че има четири елемента в него.
Края на опашката ни в момента е 2,
и сега отиваме да вмъкнете нещо друго.
>> Когато искаме да вмъкнем, че нещо друго, това, което направихме за стека версия
се удължава блок на паметта.
Какъв е проблемът с това?
[Student] преместите 2.
Това, което казах преди около края на опашката,
това не прави смисъл, че ние започваме на 1,
тогава ние искаме да dequeue 1, а след това dequeue 3, след което dequeue 4,
dequeue два след това, тогава dequeue това.
Презаделяне Не можем да използваме сега,
или най-малкото, трябва да използвате презаделяне по различен начин.
Но най-вероятно не трябва просто да използвате презаделяне.
Вие ще трябва да копирате ръчно паметта си.
>> Има две функции, за да копирате памет.
Има memcopy и memmove.
Аз съм в момента четене мъж страници, за да видите кои от тях вие ще искате да използвате.
Добре, memcopy, разликата е
memcopy и memmove, дръжки случая правилно
, където можете копирате в региона, което се случва, да се припокриват региона
копирате.
Memcopy не се справя. Memmove.
Можете да мислите за проблем, тъй като
Да кажем, че искате да копирате този човек,
тези четири с този човек повече.
В крайна сметка, това, което масива трябва да изглежда така
след копието е 2, 1, 2, 1, 3, 4, и след това някои неща в края.
Но това е в зависимост от реда, в който ние всъщност копирате,
тъй като, ако не се вземат под внимание факта, че регионът ни копирате в
припокрива сме копиране,
тогава бихме могли да направим като начало тук, копирате 2 в мястото, където искаме да отидем,
след това преместете указатели напред.
>> Сега ще бъда тук и тук, и сега ние искаме да копирате
този човек над този човек и да се премести на нашите указатели напред.
Това, което ще се намира на 2, 1, 2, 1, 2, 1
вместо на съответния 2, 1, 2, 1, 3, 4, тъй като
2, 1, припокрива първоначалното 3, 4.
Memmove обработва правилно.
В този случай, просто винаги използвайте memmove
тъй като тя борави правилно.
Като цяло не се представят по-зле.
Идеята е вместо да се започне от самото начало и копиране този начин
като ние просто направих тук, тя започва от края и да копира,
и в този случай, никога не може да има проблем.
Няма да има изпълнение загуби.
Винаги използвайте memmove. Никога не се тревожи за memcopy.
И това е мястото, където вие ще трябва да отделно memmove
увит около част от опашката си.
Не се тревожете, ако не и напълно прави.
Това е по-трудно, отколкото стека, тласък, и поп.
>> Всеки, който има всеки код, който може да работи с?
Дори ако напълно непълна?
Студентски Да, това е напълно непълна, все пак.
Напълно непълна е добре, докато ние може да ви спести преразглеждане?
Забравяме, че всеки един момент.
Добре, без да обръща внимание на това, което се случва, когато имаме нужда, за да преоразмерите неща.
Напълно да игнорира преоразмеряване.
Обяснете този код.
Аз съм проверка на първо място, ако размерът е по-малко от копие на първо място
и тогава, след това, като поставя-I главата + размер,
и съм сигурен, че го обгръща капацитета на масива,
и аз поставете на новия стринг в това положение.
Тогава увеличаване на размера и връщане вярно.
>> [Rob B.] Това определено е един от онези случаи, когато започваш да искате да се използва мод.
Каквато и да е случай, когато сте обвивка около, ако мислите, обвивка около
непосредствена мисъл трябва да бъде мод.
Като бърза оптимизация / вашия код един ред по-кратък,
забележите, че линията веднага след това
е само размера + +, така че се сливат, че в този ред, размер + +.
Сега тук имаме случай
където ние не разполагат с достатъчно памет,
така че ние се увеличава способността ни по 2.
Предполагам, че тук може да има същия проблем, но можем да го игнорирате,
, където, ако не успя да увеличи капацитета си,
тогава вие ще искате да намалите капацитет от 2 отново.
Друг кратка бележка е точно като можете да направите + =,
можете да направите << =.
Почти всичко да мине преди равен, + =, | =, & =, << =.
Чар * нов е нашият нов блок от памет.
О, тук.
>> Какво мислят хората за вида на нашия нов блок от памет?
[Student] Тя трябва да бъде Чар **.
Мисля обратно към нашата структура тук,
низ е това, което ние сме преразпределение.
Ние сме цяла нова динамика за съхранение на елементите в опашката.
Това, което ще бъде възлагане на вашите струни е това, което ние сме mallocing точно сега,
и толкова ново ще бъде знак **.
Ще бъде масив от низове.
Тогава какъв е случаят, при които отиваме да се върне фалшива?
[Student] трябва да правим Чар *?
[Роб Б. Да, добър разговор.
Студентски] Какво беше това?
[Rob B.] Искахме да направим размера на Чар *, защото ние вече не сме
това всъщност ще бъде много голям проблем, защото sizeof (Чар) ще бъде 1.
Sizeof Чар * ще бъде 4,
толкова много пъти, когато имаш работа с цели числа,
сте склонни да се размине с него, защото размера на вътр и размера на INT *
на 32-битова система ще бъде едно и също нещо.
Но тук, sizeof (Чар) и sizeof (Чар *) са сега щеше да бъде едно и също нещо.
>> Каква е обстоятелство, при връщане фалшиви?
[Студентски] Нови е нула.
Да, ако нова е нищожна, ние връщаме невярна,
и аз отивам да хвърли тук
[Студентски] [недоловим]
[Rob B.] Да, това е добре.
Можете да направите два пъти капацитета или смяна капацитет 1 и след това само го тук или каквото.
Ще го направим както трябва.
Капацитет >> = 1.
И ти никога няма да трябва да се притеснявате за загуба на 1 място
защото сте оставили изместен от 1, така че на едно място е задължително 0
толкова прав преместване от едно, ти все още ще бъде наред.
Студентски Имате ли нужда да направя това преди завръщането?
Rob B.] Да, това няма никакъв смисъл.
>> Сега си отиваме до края връщане верен до края.
Начинът, по който ние ще направим тези memmoves,
ние трябва да бъдем внимателни с това как ние ги правим.
Някой има ли някакви предложения за това как ги правим?
Ето нашето начало.
Неизбежно, искаме да започнем отново в началото
и копирни неща от там, 1, 3, 4, 2.
Как го правиш това?
Първо, аз трябва да гледам към мъжа страница за memmove отново.
Memmove, за аргументи винаги е важно.
Искаме нашата дестинация първият източник второто, размер трета.
Има много функции, които обратната източника и дестинацията.
Дестинация източник води до известна степен да бъдат последователни.
Преместване, какво се върне?
Тя връща указател към дестинация, за каквато и да е причина да искате, че.
Мога да картина го прочете, но ние искаме да се движи в нашата дестинация.
>> Какво е нашата дестинация ще бъде?
[Студентски] New.
[Rob B.] Да, и къде сме копиране?
Първото нещо, което копирате това е 1, 3, 4.
Какъв е този 1, 3, 4.
Какъв е адресът на този 1?
Какъв е адресът на тази една?
[Студентски] [недоловим]
[Роб Б.] Head + адреса на първия елемент.
Как да стигнем до първия елемент в масива?
[Student] опашката.
[Роб Б. Да, q.strings.
Не забравяйте, че тук, главата ни е 1.
Дяволски. Просто мисля, че това е магически
Ето, главата ни е една. Отивам да си сменя цвета също.
И тук е струни.
Това може да го напиша, както направихме тук
с глави + q.strings.
Много хора също го напиша и q.strings [глава].
Това не е много по-малко ефективен.
Може би си мислите за него като го dereferencing и след получаване на адрес на
но компилатора ще все пак да го преведете на това, което сме имали преди, q.strings + главата.
Така или иначе, искате да мисля за него.
>> И колко байта искате да копирате?
[Student] Капацитет - главата.
Капацитет - главата.
И тогава вие винаги може да напишете пример
за да разбера дали това е точно.
[Student] Необходимо е да се раздели на две след това.
Да, така че предполагам, бихме могли да използваме размер.
Ние все още имаме размер-
използване на размер, имаме размер, равен на 4.
Нашата размер е 4. Нашата глава е 1.
Ние искаме да копирате тези три елемента.
Това е здрав разум да се провери дали размера - главата е правилно 3.
И да се върнем тук, както казахме преди,
ако използваме капацитет, тогава ние ще трябва да се разделят с 2
, защото ние сме вече пораснали нашия капацитет, така че вместо ние отиваме да използвате размер.
Копия тази част.
Сега, ние трябва да копирате друга част, частта, която е останало от самото начало.
>> Това ще да memmove в каква позиция?
[Student] Плюс Размер - главата.
Да, така че ние вече са копирани в размер байта за глава,
и така, когато искаме да копирате останалите байта ново
и след това размер на минус-добре, броят на байтовете сме вече копира инча
И тогава къде сме копиране?
[Студентски] Q.strings [0].
[Роб Б. Да, q.strings.
Бихме могли да направите и q.strings [0].
Това е значително по-често, отколкото това.
Ако това е просто ще бъде 0, тогава ще са склонни да видите q.strings.
Това е мястото, където ние сме копиране от.
Колко байта ние оставихме да копирате? >> Студентски] 10.
Точно така.
[Student] имаме да се размножават 5 - 10 пъти по-голяма от байтове или нещо?
Да, така че това е къде-какво точно копиране?
[Студентски] [недоловим]
Какъв е типът на нещо, което копирате?
[Студентски] [недоловим]
Да, така Чар * е, че ние сме копиране, ние не знам къде са тези, идващи от.
Е, където те се посочи, подобно на струните, ние в крайна сметка го натиснете върху опашката
или enqueuing върху опашката.
Когато тези, които идват, ние нямаме идея.
Ние просто трябва да следим на знак * и се.
Ние не искаме да копирате размер - главата байта.
Ние искаме да копирате размер - главата Чар * S,
така че отиваме да се размножават от sizeof (Чар *).
Същото тук главата * sizeof (Чар *).
>> [Student] [чува?
Това право тук?
[Student] Не, по-долу, размер на главата.
[Rob B.] Това тук?
Pointer аритметика.
Как ще работи показалеца аритметика
той автоматично се размножава от размера на вид, че си имаме работа с.
Точно както тук, нов + (размер - главата)
е точно еквивалентна на & [размер - началник]
докато ние очакваме, че за да работи правилно,
тъй като, ако си имаме работа с едно цяло число масив, тогава ние не индекс от INT-
или ако е по размер на 5 и искате 4-ти елемент, тогава ние индекс в
Int масив [4].
Не ... [4] * размер на вътр.
Това обработва автоматично, и този случай
е буквално еквивалент, така че скобата синтаксис
тепърва ще се превръща в това, веднага след като се състави.
Това е нещо, което трябва да бъдат внимателни на това
когато добавяте размер - главата
не се добавят един байт.
Добавяте един знак *, който може да бъде един байта или каквито и да било.
>> Други въпроси?
Добре, dequeue ще бъде по-лесно.
Ще ви дам минути за изпълнение.
О, и аз предполагам, че това е същата ситуация, където
какво enqueue случай,, ако сме enqueuing нула,
може би искаме да се справя, може би не го правим.
Ние няма да го направя отново тук, но същата като нашата стека случай.
Ако ние enqueue нула, бихме искали да го отхвърлят.
Всеки, който има някакъв код мога да спра?
[Student] Аз просто имам dequeue.
Версия 2 е, че става.
Искаш ли да обясни?
[Student] Първо, се уверете, че има нещо в опашката
и че размерът е от 1.
Вие трябва да направите това, а после се върнете главата
и след това преместете главата 1.
Добре, така че има ъгъл случай, че трябва да се помисли. Да.
[Student] Ако главата ти е последният елемент,
след това не искате главата до точка извън масива.
>> Да, така че веднага след като главата удари края на нашата масив,
когато ние dequeue, главата ни трябва да бъде Modded обратно в 0.
За съжаление, ние не можем да направим това в една стъпка.
Предполагам, че вероятно щях да се определи, че е
това ще бъде знак *, какво Връщаме
каквото си име на променлива иска да бъде.
След това ние искаме да моден главата от способността ни
и след това се върнете кисна.
Много хора тук биха могли да сторят-
такъв е случаят - Ще видите хора, ако главата
е по-голяма от капацитета, главата - капацитет.
И това е само около това, което Министерството на отбраната.
Ръководител мод = капацитет е много по-чист
на обвивка около отколкото ако главата по-голяма от капацитета на главата - капацитет.
>> Въпроси?
Добре, последното нещо, което ни е останало, е нашето свързан списък.
Може да се използва за някои от свързан списък поведение, ако си направил
свързани списъци във вашите хеш таблици, ако си направил хеш таблица.
Горещо препоръчвам прави хеш таблица.
Може би вече са го направили Trie
но се опитва по-трудно.
На теория, те са асимптотично по-добре.
Но просто погледнете голямата съвет,
и се опитва никога не се справят по-добре, и те заемат повече памет.
Всичко за опитва в крайна сметка е по-лошо за повече работа.
Това е това, което винаги е решение Дейвид Малан
Той винаги е мнението му Trie решение, и нека видим къде в момента той е.
Това, което той е бил под, Дейвид J?
Той е # 18, така че не е ужасно лош,
и това ще бъде един от най-добрите опитва можеш да се сетиш
или на един от най-добрите се опитва на Trie.
Не е дори първоначалното си решение?
Аз се чувствам като Trie решения са склонни да бъдат повече в този диапазон на използване на RAM.
>> Отиди до самия връх, както и използването на RAM е в едноцифрени числа.
Слез надолу към дъното, а след това започнете да виждате опитва
, където можете да получите огромна RAM използване,
и се опитва по-трудно.
Не съвсем си струва, но образователен опит, ако си направил.
Последното нещо, което е нашата свързан списък,
и тези три неща, стекове, опашки и свързани списъци,
всяко бъдещо нещо, което някога по компютърни науки
ще предположим, че имате запознати с тези неща.
Те са също толкова фундаментално значение за всичко.
>> Свързани списъци, и тук имаме самостоятелно свързан списък ще бъде нашето изпълнение.
Какво прави поотделно свързани кажа, за разлика от двойно свързан? Да.
[Student само насочва към следващия показалеца, а не на указатели,
като един преди и след него.
Да, така и в формат на картината, какво съм просто правя?
Аз имам две неща. Имам картина и картина.
Формат на картината, нашите единично свързани списъци,
неизбежно, ние имаме някакъв вид на показалеца на главата на нашия списък,
и след това в рамките на нашия списък, ние просто трябва указатели,
и може би това показва нула.
Ще бъде типичен чертеж на самостоятелно свързан списък.
Двойно свързан списък, можете да се върнете назад.
Ако ти дам всеки възел в списъка, а след това е задължително да се стигне до
всеки друг възел в списъка, ако е двойно свързан списък.
Но ако можете да получите на трети възел в списъка и това е самостоятелно свързан списък,
никакъв начин не сте никога няма да стигнем до първа и втора възли.
А има и ползи и вреди, и една очевидна
ви отнеме повече размер, и вие трябва да следите, където тези неща са насочени сега.
Но ние само се грижи за самостоятелно свързани.
>> Няколко неща, които ще трябва да прилагат.
Typedef възел структура, вътр аз: структура възел * следващия; възел.
Това typedef трябва да се изгори в съзнанието си.
Quiz 1 трябва да се даде typedef на свързан списък възел,
и трябва да бъде в състояние незабавно да драскам, че
без дори да мисля за това.
Предполагам, че няколко въпроса, защо имаме нужда от структура тук?
Защо не можем да кажем възел *?
[Студентски] [недоловим]
Да.
Единственото нещо, което определя възел като нещо
е самата typedef.
Но от този момент, когато сме на морфологичните чрез това определение структурата възел,
не сме готови все още ни typedef така, тъй като typedef не е приключил,
възел не съществува.
Но структурата на възел прави, и този възел тук,
това може да се нарече всичко друго.
Това може да се нарече N.
Това може да се нарече свързан списък възел.
Това може да се нарече нищо.
Но тази структура възел трябва да се нарича едно и също нещо, тъй като това структурата възел.
Това, което наричате това трябва да бъде тук,
и така, че отговаря също на втората точка на въпроса
поради което много пъти, когато видите structs и typedefs на structs
ще видите анонимни structs където ще видите typedef структура,
изпълнението на структура, речник, или каквото.
>> Защо тук трябва да кажем възел?
Защо не може да е анонимен структура?
Това е почти един и същ отговор.
Студентски] трябва да се отнасят към него в рамките на структурата.
Да, в рамките на структура, трябва да се отнасят до самата структура.
Ако не дават структура име, ако е анонимен структура, не може да се отнася към него.
И накрая, но не на последно място, всички те трябва да бъдат малко по-ясно,
и те трябва да ви помогнат да реализирате ако пишете това
, че правиш нещо нередно, ако тези видове неща не правят смисъл.
И накрая, но не на последно място, защо това да бъде структура * възел?
Защо не може просто да се структура възел следващият?
[Student] Pointer към следващия структура.
Това е неизбежно, което искаме.
Защо никога не може да бъде структура възел следващия?
Защо това трябва да бъде структурата възел * следващия? Да.
[Student] Това е като един безкраен цикъл.
Да.
[Student] Всичко щеше да бъде в едно.
Да, просто мисля за това как ние ще направим размер или нещо.
Размер на структурата е основно + или - някои модел тук или там.
Това е основно ще бъде сумата от размерите на нещата в структурата.
Това право тук, без да се променя нищо, размерът ще бъде лесно.
Размер на структурата възел ще бъде размера на I + размера на следващата.
Размер на I ще бъде 4. Размер на следващата ще бъде 4.
Размер на структурата възел ще бъде 8.
Ако ние нямаме *, мислейки, sizeof,
sizeof (I) ще бъде 4.
Размер на структурата възел следващата ще бъде размера на I + размера на структурата възел следващия
+ Размера на I + размера на структурата възел следващия.
Това ще бъде безкрайна рекурсия на възли.
Това е така, защо това е начина, по който нещата трябва да бъдат.
>> Отново, определено запомните, че
или поне го разбирам достатъчно, че да може да бъде в състояние да
причина през това, което би трябвало да изглежда.
Неща, които ще искат да приложат.
Ако дължината на списъка
да надхитриш и поддържа около
общата продължителност или нещо подобно, но ние няма да направим това.
Отиваме да отчитат дължината на списъка.
Ние сме съдържа, така че това е основно като търсене,
така че ние имаме свързан списък от цели числа, за да видите, ако това число е в свързан списък.
Добавя се случва да вмъкнете в началото на списъка.
Добавяне ще се вмъкнете в края.
Insert_sorted ще да вмъкнете в сортират позиция в списъка.
Insert_sorted вид предполага, че никога не сте използвали добавя нищо в лоши отношения.
>> Insert_sorted когато сте прилагане insert_sorted
Да кажем, че имаме свързан списък.
Това е, което в момента изглежда, 2, 4, 5.
Искам да вмъкнете три, толкова дълго, колкото самият списък вече е сортиран,
това е лесно да се намери, където три принадлежи.
Започват от 2.
Добре, 3 е по-голямо от 2, така че искам да продължа.
О, 4 е твърде голям, така че аз знам 3 ще отиде между 2 и 4,
и аз трябва да определи насоки и всички тези неща.
Но ако ние не строго използвате insert_sorted,
харесва нека просто кажем, предшестван 6,
след това ми свързан списък ще стане това.
Сега няма смисъл, така че за insert_sorted, можете просто да поеме
че списъкът се сортира, въпреки че операциите съществуват
което може да причини да не бъде сортирана и това е всичко.
Вижте полезна вмъква така че тези са основните неща, които ще трябва да прилагат.
>> За сега, отделете малко време да се направи дължина и съдържа
и тези, които трябва да бъдат сравнително бързо.
Наближава края на работното време, така че всеки има нещо за дължина или съдържа?
Те ще бъдат почти идентични.
[Student] Дължина.
Да видим, преразглеждане.
Добре.
Искаш ли да обясни?
[Student] Аз просто се създаде възел показалеца и да я инициализираме на първото, което е нашата глобална променлива,
и след това да проверя, за да се види дали е нула, така че аз не се получи сегмент вина и да се върне 0, ако случаят е такъв.
В противен случай, аз верига, следене в рамките на цяло число
колко пъти съм достъп до следващия елемент от списъка
и в една и съща операция нарастване също, че реалният елемент,
и след това аз постоянно се направи проверка, за да видите дали това е нищожна,
и ако това е нищожно, то тогава прекъсва и се връща броя на елементите, които съм достъпни.
>> [Rob B.] Някой има ли някакви коментари за нещо?
Глоба коректност Това изглежда разумно.
[Студентски] Аз не мисля, че трябва възел == нула.
Да, така че ако възел == нула връщането на 0.
Но ако възел == нула, то това О, там е въпросът за вярност.
Това беше просто сте и връщане, но това не е в обхвата точно сега.
Ти просто трябва Int I, така че аз = 0.
Но ако възел е нула, тогава аз все още ще бъде 0,
и ние ще върне 0, така че този случай е идентичен.
Друг често срещан нещо е да съхранява декларацията
възел вътрешната страна за цикъла.
Може да се каже, о, не.
Да се ​​запази, тъй като това.
Вероятно бих Int I = 0 тук,
възел * възел = първо тук.
И това е може би как да се отървем от това сега.
Това е може би, как щях да го написали.
Вие също може да го гледа по този начин.
Това за контур структура тук
трябва да бъде почти толкова естествено за вас като за Int I = 0
I е по-малко от дължината на масива + +.
Ако това е начина, по който обхождане на масив, това е начина, по който обхождане на свързан списък.
>> Това трябва да е втора природа в някакъв момент.
С това се има предвид, че това ще е почти едно и също нещо.
Вие ще искате за обхождане на свързан списък.
Ако възел Нямам представа каква стойност се нарича.
Възел.
Ако стойността на този възел = върна вярно, и това е всичко.
Забележете, че единствения начин да се върнат някога фалшива
е, ако ние обхождане на цялата свързан списък и никога не се връщат истина,
така че какво прави това.
Като страна нота-вероятно няма да стигнем до добавяте или да се добавя нищо.
>> Бързо последната нота.
Ако видите статично ключова дума, така че нека кажем статичен Int брой = 0,
тогава ние се броят + +, можете да основно мисля за него като глобална променлива,
въпреки че току-що казах, това не е начина, по който ще приложи дължина.
Правя това, и след това разчитат + +.
Всеки път, можем да влезем възел в свързан нашия списък са увеличаване броя.
Смисълът на това е, какво означава статичното ключова дума.
Ако аз просто трябваше INT брой = 0, това би било редовно стар глобална променлива.
Какво статични INT брой на средствата е, че тя е глобална променлива за този файл.
Невъзможно е за някой друг файл,
мисля за pset 5, ако сте започнали.
Имате и двете speller.c и имате dictionary.c,
и ако просто декларира нещо в световен мащаб, а след това нещо в speller.c
могат да бъдат достъпни в dictionary.c и обратно.
Глобалните променливи са достъпни от всеки файл в
но статични променливи са достъпни само от самия файл,
така че в рамките на проверка на правописа или отвътре dictionary.c
това е един вид как щях да заявя променлива за размера на моя масив
или размера на броя на думите в речника.
Тъй като аз не искам да обяви глобална променлива, че всеки има достъп до
Аз наистина само се грижи за собствените си цели.
>> Хубавото на това е цялото име сблъсък неща.
Ако някой друг файл се опитва да използва глобална променлива, наречена брой, нещата вървят много, много грешно,
така че това добре поддържа нещата безопасно, и само вие можете да получите достъп до него,
и никой друг не може, а ако някой друг декларира глобална променлива, наречена брой,
то тогава няма да се намесва със статично променлива наречена брой.
Ето какво статично. Това е глобална променлива файл.
>> Въпроси за всичко?
Всичко е готово. Чао.
[CS50.TV]