[Powered by Google Translate] [Раздел 6: по-малко удобни]
[Нейт Hardison] [Харвардския университет]
[Това е CS50. [CS50.TV]
Добре. Добре дошли в раздел 6.
Тази седмица, ние отиваме да се говори за структури от данни в раздел
на първо място, защото проблема тази седмица на spellr
прави куп на различни данни за изследване на структурата.
Има един куп различни начини, по които можете да отидете с проблема,
и структури от данни, които знаят, по-готини неща, които можете да направите.
>> Така че нека да започнем. Първо отиваме да се говори за стакове,
стека и опашката структури от данни, че отиваме да се говори за.
Стекове и опашки са наистина полезни, когато ние започнем да говорим за графики,
които ние няма да направи толкова много за сега.
Но те са наистина добре да се разбират един от големите основните структури от данни на КС.
Описание в спецификацията проблем набор
ако го издърпайте нагоре, говори за стакове като близък до
купчина от заведения за хранене скари, че имате в кафенето в трапезарията
където при хранене на персонала идва и си поставя за хранене тави, след като са ги почистват,
те да ги комина на върха на другата.
И тогава, когато децата идват, за да си набавят храна,
издърпайте тавите, първо горната, а след това под него, тогава е по-малко от това, което.
Така че, в смисъл, първата тава, че трапезарията остави, е последният, който получава излетяло.
Последният, че за хранене на персонала, е първият, който получава за вечеря.
В спец. проблема, който можете да изтеглите, ако все още не сте,
говорим за моделиране удържат стека данни, използването на този вид структура.
>> Така че това, което имаме тук, това е подобно на това, което беше представено в лекцията,
освен в лекция ние представихме това с цели числа, за разлика от Чар * S.
Това ще бъде комин, че магазините какво?
Даниел? Какво съхраняване в тази стека?
[Даниел] Strings? >> Ние съхранявате конците в тази стека, точно така.
Всичко, което трябва да имат, за да се създаде комин е масив
на определен капацитет, което в този случай,
капацитет ще бъде във всички капачки, защото това е константа.
И тогава, в допълнение към масива, всичко, което трябва да следите е текущия размер на масива.
Едно нещо е да се отбележи, че това е нещо готино
е, че ние създаваме подредени структурата на данните на върха на друга структура на данните, масив.
Има различни начини за изпълнение стакове.
Ние няма да го направя доста още, но се надявам след това свързан списък проблеми,
ще видите как можете лесно прилагане на топчето на върха на свързан списък, както и.
Но за сега, ние ще се придържаме към масивите.
Така че отново, всичко, от което се нуждаем е масив и ние просто трябва да следите размера на масива.
[Сам Съжаляваме, защо е, че каза, че стека е на върха на струните?
За мен това изглежда като струни са в стека.
[Hardison] Да. Ние създаваме, ние сме като нашата масив структурата на данните -
това е един голям въпрос. Така че въпросът е защо, за хората, които гледат това онлайн,
защо се казва, че топчето е на върха на струните,
защото тук тя изглежда като струни са вътре в комина?
Което е напълно случая.
Това, което имах предвид, е, че ние имаме структура масив данни.
Имаме набор от Чар *, този масив от низове,
и ние ще добавим, че за да се създаде подредени структура на данните.
>> Така че стека е малко по-сложно, отколкото масив.
Ние можем да използваме масив за изграждане на комин.
Така че това е мястото, където ние казваме, че топчето е построен на върха на масива.
По същия начин, както казах по-рано, може да се изгради комин на върха на свързан списък.
Вместо да използвате масив, за да държат нашите елементи,
бихме могли да използваме свързан списък, за да държат нашите елементи и изграждането на стак около това.
Нека разгледаме няколко примера, в някакъв код,
за да се види какво всъщност се случва тук.
От лявата страна, аз съм сринат какво структура на стека ще изглежда в паметта
Ако капацитетът # определени, за да бъде четири.
Имаме четири елемент Чар масив *.
Имаме струни [0], струнни [1], струнни [2], струнни [3],
и след това, че миналата пространство за нашия размер цяло число.
Това прави ли смисъл? Добре.
Това е така, какво ще се случи, ако това, което правя в дясно,
, който ще бъде моя код, е просто да обяви структура, подредени структура, наречена S.
Това е това, което получаваме. Тя определя този отпечатък в паметта.
Първият въпрос тук е какви са съдържанието на тази стека структура?
Точно сега те са нищо, но те не са напълно нищо.
Те са този вид боклук. Ние нямаме представа какво има в тях.
Когато ние заявяваме стека S, ние просто хвърляне, че на върха на паметта.
Той е нещо като обявяване вътр аз и да не го инициализиране.
Ти не знаеш какво има вътре. Можете да прочетете това, което е там,
но той не може да бъде супер полезно.
Едно нещо, което искате винаги да помним, да се направи, е да се инициализира каквото е необходимо да се инициализира.
В този случай, ние ще да се инициализира размер е равен на нула,
защото това ще се обърне, за да бъде много важно за нас.
Бихме могли да отидем напред и инициализира всички указатели, Чар * S,
да има някаква разбираема стойност, вероятно нула.
Но това не е напълно необходимо, че ние правим това.
>> Сега, двете основни операции по стакове?
Някой помни от лекция, това, което правите с купища? Да?
[Стела] бутане и мак? >> Точно така.
Бутане и мак са двете основни операции по стакове.
И какво тласък направя? >> Поставя нещо върху горната
на комина, а след това мак го сваля.
[Hardison] Точно така. Така бутане избутва нещо на върха на стека.
Той е като трапезарията персонал пускането трапезария подноса на тезгяха.
И мак се трапезария тава на разстояние от стека.
Нека разгледаме няколко примера за това, което се случва
, когато насилваме нещата в стека.
Ако трябва да натиснете низ "здравей" на нашия стак,
това е нашата диаграма ще изглежда сега.
Вижте какво се случва?
Ние избута в първия елемент на нашата струни масив
и ние Увеличихме нашия размер брой да бъде 1.
Така че, ако погледнем в разликата между две пързалки, тук е 0, тук е преди натискане.
Ето след натискане.
Преди тласък, след натискане.
И сега имаме един елемент в нашия стак.
Това е низ "здравей", и това е всичко.
Всичко останало в масива в ни струни масив, все още е боклук.
Не сме го инициализира.
Да кажем, че прокара друг низ върху нашия стак.
Отиваме да прокара "свят" този път.
Така можете да видите "свят", тук отива на върха на "здравей",
и размера брой достига до 2.
Сега можем да избута "CS50" и че ще отида отново на върха.
Ако се върнем, можете да видите как сме бутане нещата на върха на стека.
И сега стигаме до поп.
Когато изскочи нещо на комина, какво се е случило?
Някой да е виждал разликата? Това е доста коварен.
[Student] размер. >> Да, променя размера.
>> Какво друго бихте очаквали да се промени?
[Студентски] низове, също. >> Точно така. Струните също.
Оказва се, че когато го правиш по този начин,
защото ние не сме копиране на елементи в нашия стак,
ние всъщност не е нужно да правите нищо, може просто да използвате размер
да следите броя на нещата в нашата масив
така че когато изскочи отново, отново ние просто снижаване нашия размер до 1.
Няма нужда да отида и презаписване на нещо.
Вид на фънки.
Оказва се, че ние обикновено просто остави нещата сами, защото това е по-малко работа за нас да направим.
Ако ние не трябва да се върна и презаписване на нещо, тогава защо го направи?
Така че, когато изскочи два пъти на комина, всичко, което прави е снижаване на размера на няколко пъти.
И пак, това е само защото не сме копирате неща в нашия стак.
Да? Продължавай.
[Student, неразбираем] >> И какво се случва тогава, когато натиснете нещо отново?
Когато натиснете нещо отново, къде отиде?
Къде отиват, Базил? >> В низове [1]? >> Точно така.
Защо не отидете в низове [3]?
[Василий], тъй като тя е забравила, че има нещо в низ [1] и [2]?
[Hardison] Точно така. Нашата комин, по същество, "забравил", че тя се държеше с нищо
в струни [1] или низове [2], така че когато натиснете "Woot",
просто поставя в елемент струни [1].
Има ли някакви въпроси относно това как работи, на основно ниво?
[Сам] Така че това по никакъв начин не е динамична, по отношение на размера
или по отношение на размера на стека?
[Hardison] Точно така. Това е - въпросът е, че това не е динамично growning стека.
Това е комин, който може да побере най-много четири Чар * и, най-много четири неща.
Ако бяхме да се опита да прокара Петото нещо, какво смятате, че трябва да се случи?
[Студенти, неразбираеми]
[Hardison] Точно така. Има редица неща, които могат да се случат.
Това би могло да Seg вина, в зависимост от това, което бяхме -
как точно прилагане на гърба в края.
Тя може да затриете. Той може да има, че препълване на буфера, че ние говорихме за в клас.
Какво ще бъде най-очевидното нещо, което може да бъдат презаписани
ако се опита да прокара допълнително нещо на нашия стак?
Така споменахте препълване на буфера.
Какво може да бъде нещо, които ще получи писмени или стъпкал
ако ние препълни случайно, като се опитва да прокара нещо допълнително?
[Даниел, неразбираем] >> възможни.
А всъщност това, какво може да се случи? Какво ще стане ако се опита да прокара 1/4 нещо?
Тя може да презапише размер, най-малко с тази памет диаграма, която ние имаме.
>> В спецификацията проблем набор, който е това, което ние ще се реализира днес,
това, което искам да правя е просто връщане фалшиви.
Нашата натискане метод ще се върне булева стойност,
и че булева стойност ще бъде вярно, ако Пряк успее
и невярно, ако не можем да прокара нещо повече, защото стека е пълен.
Нека разгледаме малко от същия кодекс, точно сега.
Ето нашата натискане функция.
Нашата тласък функция за комин ще се предприемат в низ да се сложи на стека.
Той ще се върне вярно, ако низът е успешно избута
стека и лъжа в противен случай.
Всички предложения за това какво може да е добра първото нещо, което трябва да направим тук?
[Сам] Ако размерът се равнява на капацитета след това се върнете невярно?
[Hardison Бинго. Хубава работа.
Ако размерът е капацитетът, отиваме да се върне фалшиви.
Не можеш да сложиш нищо повече в нашия стак.
В противен случай, ние искаме да се сложи нещо на върха на стека.
Какво е "на върха на стека," първоначално?
Даниел] Размер 0? >> Размер на 0.
Какво е на върха на комина, след като има едно нещо, в стека? Миси, знаеш ли?
[Missy]. >> Размер е един, точно така. Поддържа добавянето на размера,
и всеки път, когато сте въвеждането на нов елемент в размер на индекса в масива.
Можем да го направим с този вид на една подложка, ако това има смисъл.
Така че ние имаме ни струни масив, отиваме за достъп до нея в размер индекс,
и ние просто ще съхранява нашата Чар * там.
Забележете как не е низ копиране става тук,
не динамично разпределение на паметта?
И тогава Missy донесе това, което сега трябва да направите,
защото сме съхранява низ в подходящо място в масива,
и тя каза, че ние трябваше да увеличите размера по един, така че сме готови за следващото натискане.
Така че можем да направим това с s.size + +.
В този момент, ние сме избута в нашия масив. Какво е последното нещо, което трябва да направим?
[Student] Назад вярно. >> Назад вярно.
Така че това е доста проста, доста прост код. Не е твърде много.
След като сте увита главата си около това как работи стека,
това е доста лесно да се осъществи.
>> Сега, следващата част от това се пръкват низ от стека.
Отивам да се даде на вас известно време да работят върху това малко.
Това е почти същество обратното на това, което сме направили тук, в тласък.
Това, което съм направил, е всъщност - Опа.
Съм заредил един уред тук, и в уреда,
Съм спря на проблема, 5 спецификация.
Ако ние я увеличите тук, можем да видим съм cdn.cs50.net/2012/fall/psets/pset5.pdf.
Бяхте изтеглили този код, който се намира тук, section6.zip?
Добре. Ако не сте го направили, че направи това точно сега, наистина бързо.
Аз ще го направя в моя терминален прозорец.
Аз всъщност го е направил тук. Да.
Да, Сам? >> Аз имам един въпрос за това, защо казахте s.string "скоби на размера = ул.?
Какво е ул.? Е определена някъде преди, или - о, в Чар ул. *?
[Hardison] Да, точно така. Това е аргумент. >> О, добре. Извинете.
[Hardison Ние сме посочва низ да прокара.
Другият въпрос, който може да излезе, че ние всъщност не говоря за тук
взехме за даденост, че имахме тази променлива и
, която е в обхвата и достъпни за нас.
Приема за даденост, че тази стека структура.
Така че поглеждайки назад на този натиск код,
можете да видите, че правим неща с този низ, който бил приет в
, но след това изведнъж, достъп s.size, като, откъде е дошъл?
В кода, който отива да погледнете в секцията архив
и след това неща, за които ще се прави във вашия проблем залязва,
сме направили нашия стак структура на глобалната променлива
, така че ние можем да имаме достъп до него във всички наши различни функции
, без да се налага ръчно да я премине и да го предадат чрез позоваване,
направи този вид неща за него.
Ние сме просто измама малко, ако щете, да направим нещата по-хубав.
И това е нещо, което правим тук, защото става дума за забавление, това е по-лесно.
Често ще видите хора правят това, ако те имат една голяма структура на данните
че се работи в рамките на тяхната програма.
>> Нека се върнем на уреда.
Знаете всички успешно да section6.zip?
Всеки го разархивирайте Разархивирайте section6.zip?
Ако отидете в раздел 6 директория -
Ааа, навсякъде -
и списък за какво е тук, ще видите, че имаш три различни в. файлове.
Имаш на опашка, SLL, които поотделно е свързан списък и стек.
Ако отворите stack.c,
можете да видите, че ние имаме тази структура, определена за нас,
точната структура, че ние просто говорихме за в слайдовете.
Имаме нашата глобална променлива за стека,
ние имаме нашия тласък функция,
и след това имаме нашата поп функция.
Ще сложа код за отблъсне на слайда,
но това, което бих искал вие да направите най-доброто от способността ви
отидете и изпълнение на поп функция.
След като сте го внедрили, можете да компилирате с комин,
и след това пуснете крайния изпълним стека,
и че ще работи тук, която е в основната на този тест код.
И главните се грижи всъщност прави натискане и поп повиквания
и като се уверите, че всичко минава добре.
Инициализира размера на стака тук
така че не е нужно да се притеснявате за инициализиране.
Може да се предположи, че това е било правилно инициализиран
от момента, в който влезете в поп функция.
Това прави ли смисъл?
Така че тук ние тръгваме. Има тласък код.
Ще ви дам момчета 5 или 10 минути.
И ако имате някакви въпроси в междинния докато сте кодиране,
моля ги помолете на глас.
Така че, ако можете да получите в деликатен момент, просто питам.
Нека да знаят, нека всички останали знаят.
Работа с ближния си.
Даниел Ние просто прилагане на поп точно сега? >> Просто поп.
Въпреки че можете да копирате изпълнението на тласък, ако искате
така, че изпитанието ще работи.
Защото е трудно да се тестват неща, които навлизат в
или, че е трудно да се тества пръкват неща от комин, ако няма нищо в стека да започнем с това.
>> Какво е поп трябваше да се върне? Елемент от върха на стека.
Той е трябвало да получите елемент на върха на стека
и след това снижаване на размера на стека,
и сега сте загубили елемента на върха.
И след това да се върнете елемента на върха.
[Student, неразбираем]
[Hardison] И така, какво се случва, ако направите това? [Student, неразбираем]
Какво в крайна сметка се случи е, че най-вероятно достъп или
елемент, който все още не е инициализиран, така че вашето изчисление
когато последният елемент е изключен.
Така че тук, ако забележите, в усилията си, ние достъп струни в s.size елемент
защото това е нов индекс.
Това е новият върха на стека.
Като има предвид, че в поп, s.size ще бъде следващото място,
пространство, което е на върха на всички елементи във вашия стак.
Така че най-горния елемент не е в s.size,
, а по-скоро, това е под него.
>> Другото нещо, което трябва да правите, когато сте в поп,
ви е нужно за снижаване на размера.
Ако си спомняте обратно към нашата малка диаграма точно тук,
наистина, единственото нещо, което видяхме случва, когато ние наричаме поп
е, че този размер е намалял, от първо до две, след това на 1.
Тогава, когато ние бутна нов елемент на, ще отиде на правилното място.
[Василий] Ако s.size е 2, тогава няма да отиде на елемент 2,
и след това, което бихте искали да се появи този елемент?
Така че, ако отиде - >> Така че нека да погледнем отново.
Ако това е нашата стак в този момент
и ние наричаме поп,
, в който индексът е на най-горния елемент?
[Василий] 2, но това се случва да се появи 3. >> Точно така.
Така че това е мястото, където нашата размер е 3, но ние искаме да се появи елемент в индекс 2.
Това е типичния вид на разстояние от един, че имате с нулева индексиране на масиви.
Така че искам да се появи третият елемент, но на третия елемент, който не е в индекса 3.
И причината, поради която не трябва да направите това минус 1, когато сме бутане
е така, защото точно сега, вие забележите, че най-горния елемент,
ако бяхме да прокара нещо друго върху стека в този момент,
бихме искали да го бута при индекс 3.
И просто така се случва, че размерът и индексите линия, когато сте натискане.
>> Кой има работен стека изпълнение?
Имаш работи стека. Имате ли поп?
[Даниел] Да. Мисля, че да.
>> Програмата работи и не Seg Faulting, отпечатване?
Ли да го отпечатате "успех", когато го изпълним?
Да. Направете стека, стартирайте го, ако отпечатва "успех" и не излиза бум,
тогава всичко е добре.
Добре. Нека да отидем на уреда наистина бързо,
и ние ще вървим през тази.
Ако погледнем какво се случва тук с поп,
Даниел, какво е първото нещо, което си направил?
Даниел] Ако s.size е по-голяма от 0.
[Hardison Добре. И защо го направи?
Даниел] За да сте сигурни, че има нещо вътре в комина.
[Hardison] Точно така. Вие искате да тествате за да се уверите, че s.size е по-голяма от 0;
по друг начин, какво искаш да се случи?
Даниел Върни нула? >> Връщане нула, точно.
Така че, ако s.size е по-голяма от 0. Тогава какво ще правим?
Какво правим, ако стека не е празна?
Стела] снижаване на размера? >> Снижаване на размера, добре.
И така, как го направи? >> S.size -
[Hardison Велики. И после какво си направил?
[Stella] И тогава казах връщане s.string s.size].
[Hardison Велики.
В противен случай се върнете нула. Да, Сам?
Сам Защо тя не трябва да бъде s.size + 1?
[Hardison] Plus 1? >> Да. >> Взех го.
[Сам] Мислех, защото сте като 1,
тогава започваш да се върне не този, който те са поискали.
[Hardison И това е точно това, което ние говорим за това с целия този въпрос от 0 индекси.
Така че, ако ние я увеличите тук.
Ако погледнем към този човек тук, можете да видите, че когато поп,
сме се пръкват елемент в индекс 2.
>> Така че ние намали нашия размер, а след това нашите размери съвпада с нашия индекс.
Ако не снижаване на размера на първо място, а след това ние трябва да направим -1 и след това декремент размер.
Велики. Всичко е наред?
Всякакви въпроси за това?
Има няколко различни начини, за да напиша това, както и.
В действителност, ние можем да направим нещо дори - ние можем да направим една подложка.
Ние можем да направим един ред връщане.
Така че ние можем реално снижаване, преди да се върнем от това.
Така че пускането на преди s.size.
Това прави линията наистина гъста.
Когато разликата между размера и s.size -
е, че това Postfix - те го наричат ​​Postfix, защото идва след s.size -
означава, че s.size се оценява за целите на намирането на индекса
тъй като тя е в момента, когато се изпълнява този ред,
и след това се случва, след като линията ще се изпълни.
След елемент в s.size форум е достъпна.
И това не е това, което искаме, защото искаме декремент да се случи първо.
Ефективно, othewise, ние ще трябва да се достъп до масива, извън границите.
Отиваме да се достъп до елемент над едно, че ние всъщност искате да получите достъп.
Да, Сам? >> Е по-бързо или да използвате по-малко RAM да се направи в един ред или не?
[Hardison] Честно казано, това наистина зависи.
[Сам, неразбираем] >> Да, това зависи. Можете да направите компилатора трикове
за да получите компилатора да се признае, че, обикновено, предполагам.
>> Така че ние споменахме малко за тези неща компилатор оптимизация
, които можете да направите в съставянето,
и това е нещото, от което компилатор може да бъде в състояние да разбера,
като О, хей, може би мога да направя всичко това в една операция,
за разлика от зареждане на размера променлива от RAM,
декрементирането, да го приберете обратно, а след това да го заредите отново
за обработка на останалата част от тази операция.
Но обикновено, не, това не е вид на нещо
че ще направи програмата си значително по-бързо.
Други въпроси за стакове?
>> Така бутане и мак. Ако вие искате да изпробвате издание хакер,
това, което ние сме направили в хакер издание всъщност няма
и тази стека расте динамично.
Предизвикателството е преди всичко тук в натискане функция,
да разбера как да се направи този масив расте
да продължаваш да се бориш все повече и повече елементи на стека.
То всъщност не е твърде много допълнителен код.
Само на повикване - трябва да помните, за да получите повиквания към изчистване там правилно,
и след това да разбера, когато започваш да се обадя презаделяне.
Това е забавно предизвикателство, ако сте заинтересувани.
>> Но за момента, нека да преминем, и нека да поговорим за опашки.
Превъртете през тук.
Опашката е близък събрат на стека.
Така в стека, неща, които са били поставени в последния
са първите неща, които трябва да се изтеглят.
Имаме тази последна, първа, или LIFO, поръчване.
Като има предвид, че в опашката, както можете да очаквате, когато стоите в съответствие,
първият човек, за да получите в ред, първото нещо, за да получите в опашката,
е първото нещо, което ще възстановен от опашката.
Опашките са също често се използва, когато си имаме работа с графики,
като говорихме за кратко с купища
и опашки също са удобни за куп други неща.
Едно нещо, което идва често се опитва да се поддържа, например,
сортиран списък на елементите.
И вие можете да направите това с масив. Можете да поддържате сортиран списък на нещата в масив,
но когато това получава опасно е тогава, че винаги трябва да се намери
подходящо място, за да вмъкнете следващото нещо.
Така че, ако имате масив от числа, от 1 до 10,
и след това искате да разширите, че до всички номера от 1 до 100,
и сте се тези числа в произволен ред и се опитва да запази всичко
сортирани като ти мине през, в крайна сметка се налага да се направи много за пренасочване.
При някои видове опашки и някои видове на основните структури от данни,
всъщност можете да го държи доста проста.
Не е нужно да се добави нещо и след това да прехвърля цялата работа всеки път.
Нито пък трябва да се направи много за изместване на тежестта на вътрешните елементи около.
Когато погледнем към опашка, виждате, че и в queue.c в раздела код -
структура, че сме ви даде наистина е подобен на структурата, че ви дадохме за комин.
>> Има едно изключение от това, че едно изключение
е, че имаме тази допълнителна цяло число, наречено главата,
и главата тук е за следене на главата на опашката,
или първия елемент на опашката.
Със стак, ние бяхме в състояние да следите на елемента, който предстоеше да изтеглите
или на върха на комина, като се използва само размера,
като има предвид, че с опашка, се налага да се справят с противоположни краища.
Опитваме се да халс неща в края, но след това се върнете нещата от предната.
Толкова ефективно, с главата, имаме индекса от началото на опашката,
и размера ни дава индекса на края на опашката
, така че ние може да изтеглите неща от главата и се добавят неща на опашката.
Като има предвид, че с стека, ние бяхме само се занимават с върха на стека.
Никога не сме имали за достъп до дъното на стека.
Ние само добавя нещата до върха и взе нещата на върха
така че не е необходимо допълнително поле в нашата структура.
Ли, че като цяло има ли смисъл?
Добре. Да, Шарлот? Шарлот, неразбираем]
[Hardison Това е чудесен въпрос, и това е този, който идва в лекция.
Може би се разхождах из няколко примера ще илюстрират защо
ние не искаме да се използват струни [0] като главата на опашката.
>> Така че представете си, че ние имаме опашка, отиваме да го наричат ​​опашката.
В началото, когато току-що сте го инстанция,
, когато току-що той обяви, че не сме инициализира нищо.
Всичко е боклук. Така че, разбира се, искаме да се уверите, че ние се инициализира
както размера, така и в областта на главата, за да бъде 0, нещо разумно.
Ние също може да отидете напред и нула на елементи в нашата опашка.
И за да направи тази годни схема, забележите, че сега нашата опашката може да проведе три елемента;
като има предвид, че нашата стека можеше да побере четири, опашката може да притежават само три.
И това е само за да направят годни диаграма.
Първото нещо, което се случва тук е, че подреждането на низ в опашка "здрасти".
И точно както направихме с стека, нищо различно тук,
ние изхвърляме низ на струните [0] и нарастване нашия размер от 1.
Ние enqueue "чао", той се облече.
Така че това прилича на купчина в по-голямата си част.
Започнахме тук, нов елемент, нов елемент, размер продължава.
Какво се случва в този момент, когато искаме да dequeue нещо?
Когато искаме да dequeue, която е елемент, който искаме да dequeue?
[Василий] Strings [0]. >> Zero. Точно така, Базил.
Ние искаме да се отървем от първия низ, това, "здрасти".
И така, какво е другото нещо, което променя?
Забележете, когато изскочи нещо на разстояние от стека, ние просто променили размера,
но тук, имаме няколко неща, които се променят.
Не само промяна на размера, но промените главата.
Това се връщаме към точка на Шарлот по-рано:
защо имаме тази глава, както и?
Има ли смисъл сега, Шарлот? >> Нещо такова.
[Hardison] Вид? Така че това, което се е случило, когато dequeued?
Какво главата, че сега е интересен?
[Шарлот] О, защото го променя - добре. Разбирам.
Защото главата - когато главата е насочена към промени в оглед на мястото.
Това вече не е винаги нула един индекс. >> Да, точно така.
Това, което се случи, беше ако dequeueing високата елемент
е направено и ние не разполагаме с тази област на главата
защото ние винаги сме се обадите на този низ 0 индекса на главата на нашата опашка,
тогава ние ще трябва да се пренасочат останалите на опашката.
Ние ще трябва да се премине "чао" от струните [1] на струните [0].
И струнни [2] надолу в низове [1].
И ние ще трябва да направите това за пълния списък на елементите,
целия масив от елементи.
И когато правим това и с масив, че става наистина скъпо.
Така че тук, това не е голяма работа. Ние просто трябва три елемента в нашия масив.
Но ако имаше опашка от хиляди елементи или един милион елемента,
и след това изведнъж, ние започнем да правим един куп dequeue призовава всички в една линия,
нещата наистина ще се забави, защото измества всичко постоянно.
Знаеш ли, превключете от 1 смени от 1, смени един смени от 1.
Вместо това, ние използваме тази глава, ние го наричаме "указател", въпреки че това не е наистина указател
в тесния смисъл на думата, то не е тип указател.
Това не е INT * или Чар * или нещо подобно.
Но това сочи или посочва ръководителят на нашата опашка. Да?
>> Студентски] Как dequeue знам само поп всичко, което е в главата?
[Hardison] Как dequeue знаят как да гърмя, каквото е в главата? >> Точно така, да.
>> Какво е просто каквото областта на главата е настроен да го гледа.
Така че в първия случай, ако погледнем точно тук,
главата ни е 0, индекс 0. >> Точно така.
[Hardison] Така тя просто казва, добре, добре, елементът с индекс 0, низ "здрасти",
е елемент начело на нашата опашка.
Така че ние ще да dequeue този човек.
И това ще бъде елемент, който получава връща на повикващия.
Да, Саад? >> Така главата основно определя - къде отиваш да го индекс?
Това е началото на? >> Да. >> Добре.
[Hardison Това се превръща в ново начало за нашия масив.
Така че, когато dequeue нещо, всичко, което трябва да направите, е достъп до елемент в индекса q.head
и това ще бъде елемент, който искате да dequeue.
Вие също трябва да снижаване на размера.
Ще видим след малко, когато нещата стават малко трудно с това.
Ние dequeue, и сега, ако ние enqueue отново,
къде ние enqueue?
Къде следващия елемент в нашата опашка?
Да кажем, че искате да подреждането низ "CS" в опашка.
, В която индексът ще отиде? [Студенти] Strings [2]. >> Втора.
Защо две, а не 0?
[Василий] Защото сега на главата е едно, така че това е като в началото на списъка?
[Hardison] Точно така. И какво обозначава края на списъка?
Какво използва, за да обозначи края на нашата опашка?
Главата е главата на нашия опашката, в началото на нашата опашка.
Какво е края на нашия опашката? Студентите] Размер. >> Размер, точно така.
Така че нашите нови елементи в размер, както и елементите, които ние приемаме изключване идват в главата.
Когато enqueue следващия елемент, ние сме го поставя в размер.
[Студентски] Преди да поставите, че макар размер е един, нали?
[Hardison] Точно така. Така че не е съвсем размер. Размер + не една, но + на главата.
Защото ние се размърда всичко от главата сума.
Така че тук, сега имаме опашка с размер 1, който започва с индекс 1.
Опашката е индекс 2. Да?
>> [Student] Какво се случва, когато dequeue струни [0], и струнни слотове в паметта
просто се изпразва, основно, или просто забравени?
[Hardison] Да. В този смисъл, ние просто ги забравя.
Ако бяхме съхраняване на копия от тях -
много структури от данни често ще съхраняват своите собствени копия на елементите
така, че лицето, което управлява структурата на данните не трябва да се притеснявате
къде всички тези указатели се ще.
Структурата на данните държи на всичко, държи на всички копия,
за да се уверите, че всичко продължава по подходящ начин.
Въпреки това, в този случай, тези структури от данни, за простота,
не са прави копия на всичко, което сме съхранение в тях.
[Student] Така че това е един непрекъснат масив - >> Да.
Ако погледнем назад към определението на тази структура.
Това е просто стандартен масив като теб съм виждал,
масив от Чар * S.
Ли това? >> Да, аз просто се чудех
ако в крайна сметка ще се изчерпи на паметта, до известна степен,
ако имате всички тези празни места във вашия масив?
[Hardison] Да, това е добра отправна точка.
>> Ако погледнем какво се е случило в този момент,
сме попълнили нашата опашка, изглежда.
Но не сме наистина напълни нашата опашка
защото имаме опашка, която е размер на 2, но тя започва с индекс 1,
защото това е, когато главата ни показалеца.
Както казахте, че елемент на струните [0], с индекс 0, не е наистина там.
Това не е в нашата опашка вече.
Ние просто не се притеснява да ида и да го презапише, когато го dequeued.
Така че, дори и да изглежда, че сме изчерпване на паметта, ние наистина не са.
Това място е достъпно за нас, за да използвате.
Подходящото поведение, ако бяхме да се опитаме и първата dequeue нещо
като "довиждане", който ще се появи сбогом на разстояние.
Сега нашата опашка започва от индекс 2 и е с размер 1.
И сега, ако ние се опитваме и enqueue нещо отново, да речем 50,
50 трябва да отида на това място с индекс 0
, защото тя все още е на разположение за нас. Да, Саад?
Саад] ли това да се случи автоматично?
[Hardison] Това не се случва автоматично. Вие трябва да направите по математика
, за да работи, но същество това, което сме направили, е, че ние току-що увита около.
[Саад] И това е добре, ако има дупка в средата на?
[Hardison] е, ако можем да направим по математика работят правилно.
>> И се оказва, че това всъщност не е толкова трудно да се направи с Министерството на отбраната оператор.
Така че просто като ние направихме с Цезар и крипто неща,
използване на Министерството на отбраната, ние можем да получите нещата да се увива около и продължавай
наоколо и наоколо и наоколо с опашка
запазване че главата показалеца, които се движат наоколо.
Забележете, че размера винаги се спазва броя на елементите всъщност в рамките на опашката.
И това е само показалеца на главата, която поддържа пътя си през.
Ако погледнем какво се е случило тук, ако се върнем към началото,
и просто гледам какво се случва в главата
, когато ние enqueue нещо, нищо не се е случило в главата.
Когато enqueued нещо друго, нищо не се е случило в главата.
Веднага след като dequeued нещо, главата отива по един.
Ние enqueued нещо, нищо не се случва в главата.
, Когато dequeue нещо, изведнъж главата получава увеличава.
, Когато enqueue нещо, нищо не се случва в главата.
>> Какво ще се случи в този момент, ако бяхме да dequeue нещо отново?
Някакви идеи? Какво ще се случи с главата?
Какво трябва да се случи в главата
ако бяхме да dequeue нещо друго?
Главата в момента е в индекс 2,
което означава, че главата на опашката е струни [2].
[Студентски], която връща 0? >> Той трябва да се върне до 0. Тя трябва да приключи около, точно така.
Досега всеки път, когато се обадихме dequeue, ние сме били добавянето на един в главата,
добави един в главата, един в главата, добавя се една в главата.
Веднага след като това главата показалеца се стигне до последния индекс в нашия масив,
тогава ние трябва да го увийте около началото, върнете се на 0.
Шарлот] Какво определя капацитета на опашката в комин?
[Hardison] В този случай, ние току-що използва # дефинирана константа. >> Добре.
[Hardison] В действителния файл в можете да отидете и мръсотия с малко
и да я направи по-голям или малко, колкото искате.
Шарлот] Така че, когато сте го прави на опашка, как да направите компютъра знам
колко големи искате да стека?
[Hardison Това е чудесен въпрос.
Има няколко начина. Един от тях е просто да го определят отпред
и да кажа това ще бъде опашка, която има четири елементи или 50 елементи или 10000.
Другият начин е да се направи какво правят хора хакерски издание
и създаване на функции, да имат опашката си расте динамично, тъй като все повече неща се добавят.
>> Шарлот], така да отида с първия вариант, какъв синтаксис използвате
да кажете на програмата, какъв е размерът на опашката?
[Hardison Ah. Така че нека да се измъкнем от тази.
Аз все още съм в stack.c тук, така че аз съм просто ще да се придвижите нагоре към върха тук.
Виждате ли това право? Това е # определят капацитет 10.
И това е почти точно същия синтаксис, който имаме за опашката.
С изключение на опашката, ние имаме, че допълнително поле структура тук.
[Шарлот] О, помислих си аз капацитет означава капацитет за низ.
[Hardison Ah. >> Това е максималната дължина на думата. >> Взех го.
Да. Капацитетът тук - това е страхотна точка.
И това е нещо, което е трудно
защото това, което сме декларирали тук е масив от Чар * S.
Масив от указатели.
Това е масив от символи.
Това е може би това, което сте виждали, когато сте били обявяване буфери за файла I / O,
, когато сте били създаване струни ръчно на стека.
Но това, което имаме тук е масив от Чар *.
Така че това е масив от указатели.
Всъщност, ако ние я увеличите назад и погледнем какво става тук
в презентацията, ще видите, че реалните елементи, символни данни
не се съхраняват в рамките на самия масив.
Това, което се съхранява в масив ни тук са указатели към символни данни.
Добре. Така че ние сме виждали как размера на опашката е точно като с стека,
размера винаги се съобразява с броя на елементите на опашката.
След като две enqueues, размерът е 2.
След вземане на dequeue размер е 1.
След като направи още enqueue размер е до 2.
Така размерът определено спазва броя на елементите в опашката,
и след това главата просто продължава колоездене.
Тя отива от 0-1-2, 0-1-2, 0-1-2.
И всеки път ние наричаме dequeue, показалеца на главата ще увеличи на следващия индекс.
И ако главата е на път да премине, контури около 0.
Така че с това, ние можем да напишем dequeue функция.
И отиваме да напусне enqueue функция за вас, момчета да прилагат вместо.
>> Когато dequeue елемент на нашата опашка,
какво беше първото нещо, което Даниел направих, когато започнах да пиша поп функция за стакове?
Дай ми да чуя от някой, който все още не е говорил.
Да видим, Саад, помниш ли какво Даниел като първото нещо, когато той пише поп?
[Саад] беше - >> Той тества за нещо.
Саад] Ако размерът е по-голям от 0. >> Точно така.
И това, което е, че тестването за?
Саад] Това е изпитване, за да се види дали има нещо вътре в масива.
[Hardison] Да. Точно така. Така че не може да изскочи нещо на комина, ако е празно.
Също така, не може да dequeue нищо от опашката, ако тя е празна.
Какво е първото нещо, което трябва да направите в нашата dequeue функция тук, не мислиш ли?
Саад] Ако размерът е по-голяма от 0? >> Да.
В този случай, аз всъщност само тестван, за да се види дали е 0.
Ако е 0, можем да се върнем нула.
Но точно същата логика.
И нека продължим с това.
Ако размерът не е 0, където е елемент, който искаме да dequeue?
Саад] В главата? >> Точно така.
Ние можем само да извадя първия елемент в нашата опашка
достъп до елемент на главата.
Нищо луд.
След това, какво трябва да направя? Какво трябва да се случи?
Какво е другото нещо, което ние говорихме за dequeue?
Две неща трябва да се случи, защото нашата опашка се е променило.
[Даниел Намаляване на размера. >> Ние трябва да се намали размера и увеличаване на главата? Точно така.
За да се увеличи на главата, ние не може да просто сляпо увеличаване на главата, не забравяйте.
Ние не може просто да направи queue.head + +.
Ние също трябва да включва този мод от капацитета.
И защо Министерството на отбраната от капацитета, Стела?
Стела, защото тя трябва да обгърне. >> Точно така.
Министерството на отбраната от капацитета, тъй като тя трябва да приключи около 0.
Така че сега, в този момент, ние можем да направим това, което Даниил рече.
Ние можем да снижаване на размера.
И тогава можем само да се върне елемент, който е в горната част на опашката.
Изглежда някак чепат на първо време. Може би имам един въпрос. Моля?
>> Сам Защо е първата в горната част на опашката? Къде отиде?
[Hardison Той идва от четвъртия ред отдолу.
След като тест, за да се уверите, че нашата опашката не е празна,
ние премахваме Чар * На първо място, ние премахваме елемент, който седи на главата индекс
на нашия масив, на нашия струни масив, >> и разговор, че първата?
[Hardison И ние го наричаме първа. Да.
Само за проследяване на това, защо мислиш, че ние трябваше да направим това?
[Сам] Всяка първа е просто връщане q.strings [q.head? >> Да.
>> Защото ние правим тази променяща се на q.head с Министерството на отбраната функция,
и няма начин да се направи, че в рамките на връщащия тръбопровод.
[Hardison] Точно така. Ти си на място. Сам е напълно на място.
Причината, поради която трябваше да извадя първия елемент в нашата опашка и да го съхранява в променлива
е така, защото тази линия, където ние току-що q.head,
Министерството на отбраната оператор там не е нещо, което можем да направим
и той да влезе в сила по главата, без - в една линия.
Така че ние действително трябва да извади първия елемент, след това регулирайте главата,
регулирате размера, а след това се върнете елемент, който извади.
И това е нещо, което ще видите по-късно с
свързани списъци, тъй като ние си поиграете с тях.
Често, когато сте освобождаване или изхвърляне на свързани списъци
трябва да се помни следващият елемент, следващия показалеца на свързан списък
преди да изхвърлите на текущата.
Защото в противен случай те изхвърли на информация за това, което е останало в списъка.
Сега, ако отидете на вашия уред, отвори queue.c-х за това.
Така че, ако се отвори queue.c, нека увеличение тук,
ще видите, че имате подобен файл.
Подобни на вид файл, което имахме по-рано с stack.c.
Имаме нашата структура за опашката, определя точно както видяхме на слайдовете.
>> Ние имаме enqueue функция, която е да направя за вас.
И ние имаме dequeue функция тук.
Се dequeue функция във файла се прилагат,
но аз ще го пуснат обратно на PowerPoint, така че можете да го напишете, ако искате.
Така че за следващите 5 минути, или така, момчета работят по enqueue
което е почти само обратното на dequeue.
Вие не трябва да се коригира главата, когато сте enqueueing, но какво трябва да се коригира?
Size. Така че, когато enqueue, главата остава недокосната, размерът се сменя.
Но тя не взема малко - ще трябва да си поиграете с тази мода
да разбера точно какво индекса на нов елемент трябва да се добавят в.
Така че аз ще ви дам момчета малко, dequeue резервно копие на слайда,
и вие имате въпроси, ги вика, така че можем да
всички говорят за тях като група.
Също така, с размера, който не ... - когато регулирате размера, винаги можете просто -
имате моден размера някога? [Даниел бр. >> Не е нужно да моден размера, нали.
Тъй като размерът винаги ще, ако вие сте - ако приемем, че управлението неща по подходящ начин,
размера винаги ще бъде между 0 и 3.
Къде трябва да моден когато правиш enqueue?
[Студент] Само за главата. >> Само за главата, точно така.
И защо трябва да моден в enqueue?
Кога е ситуация, в която ще трябва да мод?
[Student] Ако имате неща в пространства, като в пространства 1 и 2,
и след това ви е необходимо да се добави нещо на 0.
[Hardison Да, точно така. Така че, ако главата ти е позициониран в самия край,
или ако вашият размер плюс главата ти е по-голям, или по-скоро ще да се увива около опашката.
>> Така че в тази ситуация, че сме тук на слайда точно сега,
ако искам да enqueue нещо точно сега,
искаме да enqueue нещо с индекс 0.
Така че, ако търсите къде 50 отива и аз наричам enqueue 50,
той отива там на дъното. То върви индекс 0.
Той замества "здрасти", която вече е била dequeued.
Даниел] Да не можеш да се погрижи за това през dequeue вече?
Защо го направя нещо с глава в enqueue?
[Hardison] О, така че не сте модифициране на главата, съжалявам.
Но вие трябва да използвате оператора на Министерството на отбраната, когато сте отворили
елемент, който искате да enqueue при достъп
следващия елемент в опашката ви.
[Василий] не съм направил, че и аз имам "успех" там.
[Даниел] О, аз разбирам това, което казваш.
[Hardison] Значи ... ти направи в q.size?
[Василий] Да. Току-що промених страни, аз не съм направил нищо с главата.
[Hardison] не всъщност трябва да рестартирате главата, за да бъде нещо,
но когато индексът в струни масив,
всъщност трябва да вървим напред и да се изчисли, където на следващия елемент,
защото withe стека, следващият елемент в стака си винаги е бил
на индекса, съответстваща на размера.
Ако погледнем назад в нашата функция стека тласък,
ние винаги може да дрънкам в нашия нов елемент в размер на индекса.
Като има предвид, че с опашка, не можем да направим, че
защото, ако ние сме в тази ситуация,
ако enqueued 50 нов низ ще отиде право в струни [1]
които не искам да правя.
Ние искаме да имаме нов низ с индекс 0.
>> Дали някой - нали? Студентски] Аз имам един въпрос, но това не е наистина свързани.
Какво означава, когато някой просто нарича нещо като pred показалеца?
Какво е това име за кратко? Знам, че е просто едно име.
[Hardison] Pred показалеца? Да видим. В какъв контекст?
[Student] Това беше за вмъкване. Мога да ви попитам късно, ако искате
, защото не е свързана, но аз просто -
[Hardison] От въведете кода от лекция на Дейвид?
Ние можем да дръпнете, че и да поговорим за това.
Ще говорим за това, че през следващата, след като стигнем до свързани списъци.
>> Така че нека наистина бързо погледнете какво прилича enqueue функция.
Какво беше първото нещо, което хората се опитах да направя в enqueue си линия? В тази опашка?
Подобно на това, което сте направили за стека бутане.
Какво направихте, Стела?
Стела, неразбираем]
[Hardison] Точно така. Ако (q.size == КАПАЦИТЕТ) -
Трябва да си сложа скоби на точното място - връщане фалшиви.
Увеличи малко. Добре.
Сега какво е следващото нещо, което ние трябваше да направим?
Точно както с стека, поставена на точното място.
И така, какво е точното място да вмъкнете това?
С стека индекс размер, с това не е чак толкова.
Даниел] Имам q.head-или - >> q.strings? >> Да.
q.strings [q.head + q.size МО КАПАЦИТЕТ?
[Hardison Вероятно искат да поставят скоби около
, така че ние сме много подходящ предимство и така че е cleart за всички.
И които са равни? >> До ул.? >> Ул.. Велики.
И сега какво е последното нещо, което ние трябва да направим?
Точно както ние направихме в комин. >> Увеличите размера? >> Увеличите размера.
Boom. И тогава, тъй като стартер код що се е завърнал фалшива по подразбиране,
ние искаме да променим това да е истина, ако всичко минава и всичко върви добре.
Добре. Това е много информация за раздел.
Ние не сме доста над. Искаме да говорим наистина бързо за поединично свързани списъци.
Ще оставя това така че можем да се върнем към него по-късно.
Но нека се върнем към нашата презентация за още няколко пързалки.
Така enqueue е TODO, сега сме го правили.
>> Сега нека да разгледаме поотделно свързани списъци.
Ние говорихме за тези малко повече в лекция.
Колко от вас видя демо, където имахме хора
неловко посочи помежду си и стопанството номера? >> Бях в това.
>> Какво вие мислите? Ли това, надявам се демистифицира тези малко?
Със списък, се оказва, че си имаме работа с този тип, че отива да се обадя на възел.
Като има предвид, че с опашката и стека имахме structs, че ние ще се обади опашка в стека,
имахме тези нови опашка в стек видове,
тук списъкът е наистина само състои на куп възли.
По същия начин, че конците са само един куп от символи, подредени един до друг.
Свързан списък е само един възел и друг възел и друг възел и друг възел.
И вместо да се разбием всички възли и ги складирайте Последователно
всички в непосредствена близост една до друга в паметта,
като следващия показалеца ни позволява да съхранявате възли, където и на случаен принцип.
И тогава вид на тел ги всички заедно да се отбележи от една до следващата.
>> И това, което е голямо предимство, че това е оказало върху група?
Над съхранение всичко Последователно просто вдигнахме един до друг?
Спомняш ли си? Да? >> Динамично разпределяне на паметта?
>> Динамично разпределяне на паметта в какъв смисъл?
[Student] В това можете да поддържате което го прави по-големи и не е нужно да преместите целия масив?
[Hardison] Точно така. Така че с масив, когато искате да поставите нов елемент в средата на
, който трябва да смени всичко, за да направи място.
И като говорихме с опашката,
това е защо ние поддържаме, че показалецът на главата,
така, че ние не сме постоянно пренасочване неща.
Защото това стане скъпо, ако имаш голям масив
и сте непрекъснато прави тези случайни вмъквания.
Като има предвид, че със списък, всичко, което трябва да направите, е да го хвърли на нов възел,
коригира указатели, и сте готови.
Какво е гадно за това?
Да оставим настрана факта, че това не е толкова лесно да се работи с масив? Да?
Даниел] Е, предполагам, че е много по-труден достъп до определен елемент в свързан списък?
[Hardison] Не може просто да скочи до произволен елемент в средата на свързаното вашия списък.
Как ли трябва да го направи вместо? >> Трябва да преминете през цялото нещо.
[Hardison] Да. Трябва да се мине през един по един, един по един.
Това е огромна - това е болка.
Каква е другата - има още един провал на това.
[Василий] не може да върви напред и назад? Вие трябва да отидете в една посока?
[Hardison] Да. Е, как да решим, че понякога?
[Василий] двойно свързани списъци? >> Точно така. Има двойно свързани списъци.
Има също така - съжалявам?
>> Сам е, че същото като с помощта на pred нещо, което
Аз просто си спомни, не е, че това, което pred нещо е?
Не е ли това между двойно и единично?
[Hardison] Нека да разгледаме какво точно е правил.
Така че тук ние тръгваме. Ето списък с кодове.
Тук имаме predptr тук. Това, което се говори за?
Така че това беше - той освобождава списък и той се опитва да се съхранява указател към него.
Това не е двойно, единично, свързани списъци.
Можем да говорим повече за това по-късно, тъй като това говори за освобождаването на списъка
и аз искам първо да покаже някои други неща.
но това е просто - това е запомняне на стойността на паметта
Студентски] О, това е предходната показалеца? >> Да.
Така че тогава ще можем да увеличите паметта себе си, преди да сме свободни, какво predptr.
Защото ние не можем безплатно паметта и след това се обадете PTR = PTR следващия, нали?
Това би било лошо.
Така че нека да видим, към този човек.
>> Другото лошо нещо за списъците е, че като има предвид, че с масив
ние просто трябва всички елементи, които се подредени един до друг,
тук ние също са въвели този указател.
Така че има допълнително парче на паметта, която ни се налага да използвате
за всеки елемент, който ние сме съхранение в нашия списък.
Ще получите гъвкавост, но то е въпрос на цена.
Той идва с цената този път,
и той идва с тази памет разходи.
Време, в смисъл, че сега трябва да мине през всеки елемент в масива
да намерите този, при индекс 10, или че би било индекс 10 в масив.
>> Просто наистина бързо, когато ние диаграма тези списъци,
обикновено държим в главата на списъка или първо показалеца на списъка
и забележете, че това е вярно показалеца.
Той е само на 4 байта. Това не е самата възел.
Така че виждате, че няма вътр. Стойност в него, не следващия показалеца в него.
Това е буквално само показалеца.
Това ще да сочи към нещо, което е действително структура възел.
[Сам] показалеца нарича възел? >> Това е - не. Това е показалеца на нещо от типа възел.
Това е указател към структура възел. >> О, добре.
Схема в ляво, код на правото.
Да я настроите към нула, което е добър начин да започнете.
Когато го диаграма, или да го напиша като унищожаем или линия през харесва.
>> Един от най-лесните начини за работа със списъци,
и ние ви помоля да прикрепяне, така и добавете да видите разликите между двете,
но пред всяка определено е по-лесно.
Когато бъде предшестван, това е мястото, където - когато Добавя (7),
да отидете и да се създаде структура възел
и вие първи да сочи към него, защото сега, тъй като той бъде поставен,
ще бъде в началото на списъка.
Ако Добавя (3), който създава друг възел, но сега 3 идва преди 7.
Така че ние сме по същество бутане неща върху нашия списък.
Сега можете да видите, че прикрепяне, понякога хората го наричат ​​натиснете,
защото ти си прокарва нов елемент към списъка си.
Това е също така лесно да изтриете в предната част на списъка.
Така че хората често ще се обади, че поп.
И по този начин, можете да подражават на топчето с помощта на свързан списък.
Опа. За съжаление, сега сме на добавяне. Така че тук имаме бъде поставен (7), сега ние Добавя (3).
Ако бъде поставен нещо друго върху този списък, ако бъде поставен (4),
тогава щяхме да имаме 4 и след това 3 и след това 7.
Така че тогава ще можем да се появи и премахване на четири, извадете 3, отстранете 7.
Често по-интуитивен начин да се мисли за това, е с добавяне.
Така че аз съм диаграмата какво ще изглежда като с добавите тук.
Ето, приложен (7) не изглежда по-различно
, защото има само един елемент в списъка.
И вмъкване (3) поставя в края.
Може би можете да видите точно сега трик с добавяне
е, че тъй като знаем само, където е началото на списъка е,
да се добави към списъка, който трябва да извървят целия път през списъка
да стигнем до края, стоп, след това изгради своя възел и всичко удрям силно надолу.
Тел и всички други неща.
Така че с Добавя, ние просто връхлетя наистина бързо,
когато бъде предшестван към списък, това е доста проста.
>> Можете да направите своя нов възел, включват някои динамично разпределение на паметта.
Така че тук ние правим възел структура чрез изчистване.
Така изчистване ние използваме, защото това ще задели памет за нас за по-късно
защото ние не искаме това - ние искаме тази памет да се задържат за дълго време.
И ние се указател към място в паметта, че ние просто разпределят.
Ние използваме размера на възел, ние не се сумират полета.
Ние не въвеждаме ръчно генериране на броя на байтове,
вместо ние използваме sizeof, така че ние знаем, че сте се подходящ брой байтове.
Ние правим забравяйте да тествате, че нашата изчистване повикване успя.
Това е нещо, което искам да направя по принцип.
На съвременни машини, изчерпване на паметта не е нещо, което е лесно
освен ако не сте разпределяне на тон неща и огромен списък,
но ако строим неща, да речем, като iPhone или Android,
все пак разполагат с ограничени ресурси от памет, особено ако правиш нещо интензивен.
Така че е добре да се получи на практика.
>> Забележете, че съм използвал няколко различни функции тук
, които съм виждал, че са вид на нови.
Така че fprintf е точно като ФОРМАТ
с изключение на първия си аргумент е поток, към който искате да отпечатате.
В този случай, ние искаме да печатате низ стандартната грешка
което е различен от стандартния outstream.
По подразбиране тя се появи на същото място.
Той също така се отпечатва в терминала, но можете да
използването на тези команди сте научили, пренасочване техники
сте научили за видео Томи за проблем набор 4, можете да го насочи
различни области; след това излизане, точно тук, излиза вашата програма.
Това е по същество като връщане от основната,
освен ние използваме изход, защото тук връщане няма да направи нищо.
Ние не сме в основната, така че завръщането не излезете от програмата, като искаме.
Така че ние използваме функцията на изхода и да му дадете код за грешка.
Тогава ние стойност областта на нов възел, I областта да бъде равен да съм, и тогава ние го преведете.
Разположен в непосредствена близост показалеца на нов възел да посочим първо,
и след това първо ще се отбележи на нов възел.
Тези първи редове код, ние всъщност изграждането на нов възел.
Не на последно място два реда на тази функция, но първите.
Всъщност можете да извади във функция, в помощната функция.
Това е често това, което правя е, че аз я издърпайте във функция,
Аз го наричам нещо като възел изграждане,
и че поддържа прикрепяне функция доста малък, той е само на 3 линии, тогава.
Ли да се обадя да ми възел изграждане функция, и след това тел всичко.
>> Крайният нещо, което искам да ти покажа,
и аз ще ви позволи да направите добавяне и всичко това на собствения си,
е как за обхождане на списък.
Има един куп различни начини за обхождане на списък.
В този случай, ние ще да се намери дължината на списъка.
Така че ние започваме с дължина = 0.
Това е много подобно да пише strlen за низ.
Това е, което искам да ви покажа, това за цикъл точно тук.
Той изглежда доста фънки, това не е обичайната Int = 0, I <каквото, аз + +.
Вместо това, той инициализиране на нашата променлива н е в началото на списъка.
И тогава, докато нашият итератор променлива не е празен, ние продължаваме.
Това е така, защото по силата на споразумение, в края на нашия списък ще бъде нула.
И тогава, за да увеличите, а от това + +
свързан списък еквивалент на + + N = N-> Next.
>> Аз ще ви позволи да попълнят пропуските тук, защото ние сме извън времето.
Но имайте това предвид, докато работите върху вашите spellr psets.
Свързани списъци, ако сте прилагане на хеш таблица,
със сигурност ще дойде в много удобен.
И тъй като този идиом за лупинг над нещата ще направят живота много по-лесно, да се надяваме.
Всички въпроси, бързо?
[Сам ще Ви изпратим попълнения SLL и SC?
[Hardison] Да. Ще изпратя попълнени пързалки и SLL стека и queue.cs.
[CS50.TV]