[Powered by Google Translate] [Розділ 6: менш комфортно]
[Nate Хардісон] [Harvard University]
[Це CS50.] [CS50.TV]
Добре. Ласкаво просимо до розділу 6.
На цьому тижні ми збираємося говорити про структури даних в розділі
в першу чергу тому, що проблема на цьому тижні встановлені на spellr
робить цілий букет різних досліджень структури даних.
Є безліч різних способів, ви можете піти з проблемою набору,
і більше структур даних ви знаєте про, тим більше цікавих речей можна зробити.
>> Отже, давайте почнемо. Спочатку ми поговоримо про стеки,
стека і черги структур даних, які ми збираємося поговорити.
Стеки і черги дійсно корисні, коли ми починаємо говорити про графіки,
які ми не збираємося робити так багато зараз.
Але вони дуже добре розуміють однієї з великих фундаментальних структур даних CS.
Опис в специфікації поставленого завдання,
якщо ви потягніть його вгору, говорить про стеки те саме
Купа їдальнею лотки, які у вас є в їдальні за обіднім залам
де, коли обідній персонал приходить і ставить їдальнею лотків після вони очищають їх,
вони складають їх одна на іншу.
А потім, коли діти приходять, щоб отримати їжу,
вони тягнуть з лотків, спочатку верхню, а потім один нижче його, то той, що нижче.
Так що, по суті, перший лоток, обідній персонал поклав є останньою, яка отримує зняті.
Останнім, що співробітники їдальні поставити на перше один, який отримує зняті на вечерю.
У специфікації поставленого завдання, які ви можете завантажити, якщо ви цього ще не зробили,
ми говоримо про моделювання stucture стека даних за допомогою такої структури.
>> Отже, що ми маємо тут, це схоже на те, що була представлена ​​в лекції,
крім лекції ми представили це з цілими, а не символ * с.
Це буде стек, який зберігає і що?
Деніел? Що ми зберіганню в цьому стеку?
[Даниїл] рядків? >> Ми зберігання рядків в цьому стеці, це точно.
Все, що вам потрібно мати для того, щоб створити стек являє собою масив
конкретної потужності, яка в даному випадку,
потужності буде у всіх заголовних буквах, тому що це постійно.
І тоді на додаток до масиву, всі ми повинні відслідковувати це поточний розмір масиву.
Одна річ, щоб відзначити тут, що це круто
є те, що ми створюємо складені структури даних на іншу структуру даних, масив.
Існують різні способи реалізації стеків.
Ми не будемо робити цього зовсім ще, але, сподіваюся, після виконання пов'язаного списку проблем,
Ви побачите, як ви можете легко реалізувати стек поверх пов'язаного списку, а також.
Але зараз, ми будемо дотримуватися масивів.
Отже, ще раз, все що нам потрібно це масив, і ми просто необхідно відслідковувати розмір масиву.
[Сем] Вибачте, чому це, що ви сказали, що стек знаходиться на вершині рядки?
Мені здається, що рядки в стеці.
[Хардісон] Так. Ми створюємо, ми беремо наш масив структури даних -
це велике питання. Таким чином, питання, чому, для людей, які спостерігають за цим в Інтернеті,
Тому ми говоримо, що стек у верхній частині рядка,
тому що тут вона виглядає як рядки всередині стека?
Який повністю справі.
Те, що я мав на увазі, що у нас є структури масиву даних.
У нас є масив символів * с, це масив рядків,
і ми збираємося додати до цього, щоб створити стек структури даних.
>> Таким чином, стек трохи більш складним, ніж масив.
Ми можемо використовувати масив для створення стека.
Так от, коли ми говоримо, що стек побудований на вершині масиву.
Точно так само, як я сказав раніше, ми можемо побудувати стек на початок пов'язаного списку.
Замість того щоб використовувати масив для зберігання наших елементи,
ми могли б використовувати зв'язаний список для зберігання наших елементи та побудувати стек навколо цього.
Давайте розглянемо декілька прикладів, дивлячись на код,
щоб побачити, що насправді тут відбувається.
На лівому, я кинув, що це стек структура буде виглядати в пам'яті
якщо ємність була # визначається як чотири.
У нас є наші чотири елементи масив символів *.
У нас є рядки [0], рядків [1], рядків [2], струни [3],
а потім, що в минулому простір для нашого розміру цілого числа.
Чи має це сенс? Добре.
Це те, що станеться, якщо те, що я роблю на праву,
який буде свій код, це просто оголосити структуру, складені структура називається с.
Це те, що ми отримуємо. Вона встановлює цей слід в пам'яті.
Перше питання, ось те, що є змістом цього стека структури?
Зараз вони нічого, але вони не цілком нічого.
Вони такого сміття. Ми поняття не маємо, що в них.
Коли ми оголошуємо стек S, ми просто кидали вниз, що у верхній частині пам'яті.
Це ніби як оголошення Int я, а не його ініціалізації.
Ви не знаєте, що там. Ви можете прочитати, що там,
але вона не може бути супер корисним.
Одна річ, яку ви хочете завжди пам'ятати, щоб зробити це ініціалізувати все, що необхідно ініціалізувати.
У цьому випадку, ми збираємося, щоб ініціалізувати розмір рівним нулю,
тому що це обернеться дуже важливо для нас.
Ми могли б піти далі і ініціалізувати всі покажчики, все символ S *
щоб бути зрозумілими деякі значення, ймовірно, нульовий.
Але це не абсолютно необхідно, щоб ми це робимо.
>> Тепер дві основні операції по стеки?
Хтось пам'ятає з лекції, що ви робите зі стеками? Так?
[Stella] Натискання і плескати? >> Саме так.
Натискання і з'являються дві основні операції по стеки.
І що ж поштовх робити? >> Це ставить щось на верхньому
з стека, а потім бавовна знімає його.
[Хардісон] Саме так. Таким чином, натиснувши штовхає щось на вершині стека.
Це схоже на їдальню персоналу покласти столову піднос на столі.
І з'являються приймає їдальнею лоток з стека.
Давайте розглянемо декілька прикладів того, що відбувається
Коли ми штовхати речі в стек.
Якби ми були натиснути на рядок "привіт" на наш стек,
це те, що наша схема буде виглядати зараз.
Подивіться, що відбувається?
Ми висунули на перший елемент нашого масиву рядків
і ми збільшили кількість наших розміром рівним 1.
Таким чином, якщо ми подивимося на різницю між двома гірками, тут був 0, то ось перед поштовхом.
Ось після поштовху.
Перед натисненням, після поштовху.
І тепер у нас є один елемент в нашому стеку.
Це рядок "привіт", і це все.
Все інше в масиві, на наш масив рядків, ще сміття.
Ми не ініціалізації.
Скажімо, ми натискаємо інший рядок на наш стек.
Ми збираємося натиснути "світ" на цей раз.
Таким чином, ви можете бачити "світ" тут йде зверху "привіт",
і розмір відлік йде до 2.
Тепер ми можемо натиснути "CS50», і що піду на вершині знову.
Якщо ми повернемося, ви можете побачити, як ми натисканні речі на вершині стека.
А тепер ми перейдемо до поп-музики.
Коли ми зайшли щось із стека, що трапилося?
Ніхто бачите різницю? Це досить тонкий.
[Студент] розміру. >> Так, розмір змінився.
>> Що б ви ще очікували змінити?
[Студент] рядків, теж. >> Праві. Рядків теж.
Виявляється, що, коли ви робите це таким чином,
тому що ми не копіюючи елементи в нашому стеку,
Ми насправді не потрібно нічого робити, ми можемо просто використовувати розмір
відслідковувати кількість речей в нашому масиві
так що, коли ми спливав знову, знову, ми просто зменшуємо нашу розміром до 1.
Там немає необхідності насправді піти і переписати все.
Вид обладнаний.
Виходить, що ми зазвичай просто залишити речі в спокої, тому що це менше роботи для нас.
Якщо ми не маємо повернутися і переписати щось, то навіщо це робити?
Тому, коли ми двічі спливав з стека, все, що робить зменшення розміру пару раз.
І знову ж таки, це тільки тому, що ми не копіювати речі в нашому стеку.
Так? Йдемо далі.
[Студент, нерозбірливо] >> І що відбувається тоді, коли ви натискаєте знову щось?
Коли ви натискаєте знову щось, де воно дівається?
Куди воно дівається, Василь? >> У рядки [1]? >> Праві.
Чому вони не йдуть в рядки [3]?
[Василь], бо забув, що було щось у рядку [1] і [2]?
[Хардісон] Саме так. Наш стек, по суті, "забув", що він тримався за щось
в рядку [1] або рядків [2], тому, коли ми натискаємо "Woot»,
він просто ставить, що в елемент рядка [1].
Чи є питання про те, як це працює, на базовому рівні?
[Сем] Так що це не динамічний в будь-якому випадку, з точки зору кількості
або в термінах розміру стека?
[Хардісон] Саме так. Це - Справа в тому, що це не було динамічно growning стека.
Це стека, який може містити не більше чотирьох символів * с, не більше чотирьох речей.
Якби ми були, щоб спробувати підштовхнути 1/5 річ, що ви думаєте повинно відбутися?
[Студенти, нерозбірливо]
[Хардісон] Саме так. Є цілий ряд речей, які можуть трапитися.
Це могло сегментам вина, в залежності від того, що ми були -
як саме ми здійснювали задньому кінці.
Це може перезаписати. Він міг би мати, що переповнення буферу, що ми говорили в класі.
Що було б найбільш очевидні речі, які можуть бути перезаписані
якби ми намагалися проштовхнути зайва річ на нашому стеку?
Таким чином, ви згадали переповнювання буфера.
Що може бути те, що б отримати письмову більш або розтоптав
якщо ми переповнені випадково, намагаючись підштовхнути зайва річ?
[Даниїл, нерозбірливо] >> Можливо.
Але на початковому етапі, що може трапитися? Що, якщо ми намагалися проштовхнути 1/4 річ?
Це може переписати розмір, принаймні, з цією пам'яттю схемою, що у нас є.
>> В описі безлічі проблем, що ми і збираємося реалізації сьогодні,
те, що ми хочемо зробити, це просто повернення хибним.
Наші методу примусової збирається повернути логічне значення,
і що логічне значення буде істинним, якщо поштовх успішно
і помилково, якщо ми не можемо висунути нічого більше, тому що стек переповнений.
Давайте розглянемо трохи, що код прямо зараз.
Ось наш поштовх функції.
Наші поштовх функції для стека збирається взяти в рядку покласти на стек.
Він збирається повернутися вірно, якщо рядок була успішно витіснили
в стеку, а в іншому випадку.
Будь-які пропозиції про те, що може бути хорошим перше, що потрібно робити тут?
[Сем] Якщо розмір дорівнює потужністю потім повернутися помилковим?
[Хардісон] Bingo. Хороша робота.
Якщо розмір має потенціал, ми збираємося повернутися помилковим.
Ми не можемо помістити більше нічого в нашому стеку.
В іншому випадку, ми хочемо покласти щось на вершині стека.
Що таке "вершину стека," спочатку?
[Даниїл] Розмір 0? Розмір >> 0.
Що таке вершини стека після є одна річ, в стеці? Міссі, ви знаєте?
[Missy] One. >> Розмір один, точно. Ви продовжуйте додавати до розміру,
і кожного разу, коли ви ставите в новий елемент на розмір індексу в масиві.
Ми можемо зробити це з такою один-лайнер, якщо це має сенс.
Отже, ми отримали наш масив рядків, ми збираємося отримати до нього доступ на розмір індексу,
і ми тільки збираємося, щоб зберегти наш символ * в там.
Зверніть увагу, що там немає рядка копіювання відбувається тут,
немає динамічного розподілу пам'яті?
А потім Missy виховували, що ми зараз повинні зробити,
тому що ми зберігати рядок у відповідне місце в масиві,
і вона сказала, що ми повинні були збільшувати розмір одного, так що ми готові для наступного поштовху.
Таким чином, ми можемо зробити це з s.size + +.
На даний момент, ми заштовхнули в нашому масиві. Що це останнє, що ми повинні робити?
[Студент] Повернутися правда. >> Повернутися правда.
Так що це досить простий, дуже простий код. Не надто багато.
Після того як ви обгорнені навколо голови, як стек працює,
це досить просто реалізувати.
>> Тепер, наступна частина цього з'являються рядки з стека.
Я збираюся дати вам, хлопці якийсь час, щоб працювати над цим трохи.
Це майже по суті, протилежне тому, що ми зробили тут, у поштовху.
Що я зробив насправді - ой.
Я завантажився приладу тут, і в прилад,
Я підняв проблеми встановити 5 специфікації.
Якщо ми збільшимо тут, ми можемо бачити, що я перебуваю на cdn.cs50.net/2012/fall/psets/pset5.pdf.
Хіба ви, хлопці, скачав цей код, що знаходиться тут, section6.zip?
Добре. Якщо ви ще не зробили цього, зробіть це прямо зараз, дуже швидко.
Я зроблю це в моєму вікні терміналу.
Я дійсно зробив це тут. Так.
Так, Сем? >> У мене є питання про те, чому ти сказав s.string 'и дужках розмір = вул?
Що таке СТО? Хіба що певна десь раніше, чи - о, в символ вул *?
[Хардісон] Так, саме так. Це був аргумент. >> Ну, гаразд. Вибачте.
[Хардісон] Ми зазначенням рядка натиснути дюйма
Інше питання, що може придумати, що ми дійсно не говоримо про тут був
Ми вважали само собою зрозумілим, що у нас була ця змінна з
, Який був за своїми масштабами і доступним для нас.
Ми вважали само собою зрозумілим, що було з цим стеком структури.
Таким чином, озираючись на цей поштовх код,
Ви можете бачити, що ми робимо речі з цього рядка, які отримали пройшло в
але потім все раптово, ми доступі s.size, начебто, звідки їй прийшов?
У коді, який ми збираємося подивитися в розділі Архів
, А потім речі, які ви будете робити в вашій проблемі встановлює,
ми зробили наш стек будуємо глобальну змінну
так що ми можемо мати доступ до нього в усіх наших різних функцій
без необхідності вручну передавати його і передати його по посиланню,
робити все в такому ж роді до нього.
Ми просто обманює небагато, якщо хочете, щоб зробити речі краще.
І це те, що ми тут робимо, тому що це для задоволення, це простіше.
Часто, ви побачите, люди роблять це, якщо вони мають один великий структури даних
який експлуатується в рамках своїх програм.
>> Давайте повернемося до приладі.
У кожного успішного отримати section6.zip?
Всі розпакувати його за допомогою розпакувати section6.zip?
Якщо ви зайдете в розділ 6 каталогів -
ааа, всюди -
і ви перерахуйте те, що тут, ви бачите, що у вас є три різних. с файлами.
У вас є черги, SLL, який є односвязного список, і стек.
Якщо ви відкриєте stack.c,
Ви бачите, що у нас є ця структура визначена для нас,
точні структури, який ми тільки що говорили в слайдах.
У нас є наші глобальні змінні для стека,
Ми отримали наш поштовх функції,
а то у нас є наша поп-функції.
Я поставлю код відсунути на слайді тут,
але те, що я хотів би вам, хлопці, щоб зробити це, в міру ваших можливостей,
піти і реалізації поп-функції.
Після того як ви реалізували його, ви можете скомпілювати це з робити стек,
, А потім запустити результуючий виконуваний стек,
і що буде працювати весь цей тестовий код сюди, це в основному.
А головне дбає про справу робить поштовх і поп-дзвінки
і переконавшись, що все йде через все гаразд.
Він також ініціалізує розмір стека прямо тут
так що вам не доведеться турбуватися про те, що ініціалізація.
Можна припустити, що це було правильно инициализирован
До того часу, доступ до нього в поп-функції.
Чи має це сенс?
Таким чином, тут ми йдемо. Там в поштовх код.
Я дам вам, хлопці 5 або 10 хвилин.
І якщо у вас є які-небудь питання в проміжному той час як ви кодування,
Будь ласка, попросіть їх вголос.
Так що якщо ви отримаєте камінь спотикання, просто запитайте.
Дозвольте мені знати, нехай всі інші знають.
Робота з вашим сусідом теж.
[Даниїл] Ми просто здійсненні поп прямо зараз? >> Просто поп-музики.
Хоча Ви можете скопіювати реалізації поштовх, якщо ви хочете
так що тестування буде працювати.
Тому що це важко перевірити речі потрапити в -
або, важко перевірити з'являтися речі з стека, якщо немає нічого в стек з самого початку.
>> Що таке поп має бути повернення? Елемент з вершини стека.
Він повинен отримати елемент з вершини стека
, А потім зменшувати розмір стека,
і тепер ви втратили елемент на вершині.
І тоді ви повернетеся елемент на вершині.
[Студент, нерозбірливо]
[Хардісон] Що трапиться, якщо ви це зробите? [Студент, нерозбірливо]
Що в підсумку відбувається це ви, ймовірно, доступ або
Елемент, який не був ініціалізований, так що ваш розрахунок
, Де останній елемент вимкнений.
Так от, якщо ви помітили, у поштовху, ми доступі рядків в елементі s.size
тому що це новий індекс.
Це нова вершина стека.
Якщо в поп, s.size буде наступний просторі,
простір, що знаходиться на вершині всіх елементів в стеку.
Таким чином, самий верхній елемент не в s.size,
але, скоріше, це під ним.
>> Інша річ, щоб зробити, коли ви - в поп,
це у вас є для зменшення розміру.
Якщо ви пам'ятаєте, повернемося до нашої маленької діаграмі прямо тут,
насправді, єдине, що ми бачили, відбувається, коли ми називали поп-
було те, що цей розмір впала, спочатку в 2, то до 1.
Потім, коли ми висунули новий елемент, він піде на на належному місці.
[Василь] Якщо s.size дорівнює 2, то не було б перейти до елемента 2,
і ви хочете, щоб спливав цей елемент геть?
Таким чином, якщо ми пішли в - >> Отже, давайте подивимося на це ще раз.
Якщо це наш стек на даний момент
і ми називаємо поп,
, При якому індекс самого верхнього елементу?
[Василь] В 2, але це буде поп-3. >> Праві.
Так от, де наш розмір 3, але ми хочемо, щоб сунути елемент з індексом 2.
Це дуже типовий вид на одиницю, що у вас з нульовою індексації масивів.
Отже, ви хочете, щоб сунути третій елемент, а третій елемент не з індексом 3.
І тому ми не повинні робити це мінус 1, коли ми натискання
відбувається тому, що прямо зараз, ви помітите, що самий верхній елемент,
якщо б ми були висунути щось ще в стек на даний момент,
Ми хотіли б, щоб підштовхнути її з індексом 3.
І так уже сталося, що розмір і індекси шикуються, коли ви натискаєте.
>> У кого є робоча реалізації стека?
У вас є робочий стек один. Чи є у вас поп робітники ще?
[Даниїл] Так. Я так думаю.
>> Програма працює, а не сегментам розломів, це роздруківка?
Чи роздрукувати "успіх" при запуску?
Так. Зробити стек, запустити його, якщо він друкує «успіх» і не йде бум,
то все добре.
Добре. Давайте перейдемо до пристрою дуже швидко,
і ми пройдемо через це.
Якщо ми подивимося на те, що відбувається тут з поп-
Daniel, що було перше, що ви зробили?
[Даниїл] Якщо s.size більше 0.
[Хардісон] Добре. А навіщо ви це зробили?
[Даниїл] Щоб переконатися в тому, що щось всередині стека.
[Хардісон] Вірно. Ви хочете, щоб перевірити, щоб переконатися, що s.size більше 0;
в іншому випадку, що ви хочете, щоб сталося?
[Даниїл] Return нуль? >> Повернутися нульовий, це точно.
Так що, якщо s.size більше 0. Тоді що ж ми будемо робити?
Що ми будемо робити, якщо стік не порожній?
[Stella] Ви зменшите розмір? >> Ви зменшення розміру, все в порядку.
Так як же ви це зробите? >> S.size--.
[Хардісон] Великий. А те, що ти зробив?
[Stella] І тоді я сказав повернення s.string [s.size].
[Хардісон] Великий.
В іншому випадку ви повернетеся нульовий. Так, Сем?
[Сем] Чому вона не повинна бути s.size + 1?
[Хардісон] плюс 1? >> Да. >> Є.
[Сем] Я думав, тому що ви приймаєте 1 з,
то ви будете повертатися не той, що вони просили.
[Хардісон] І це було саме те, що ми говоримо про ціле з цим питанням від 0 індексів.
Тому, якщо ми масштаб тут.
Якщо ми подивимося на цього хлопця прямо тут, ви можете побачити, що коли ми поп,
Ми з'являтися елемент з індексом 2.
>> Таким чином, ми знижуємо наш розмір, а потім наш розмір відповідає нашому індексі.
Якщо ми не зменшуємо розмір, а потім ми повинні зробити розмір -1, а потім декремента.
Великий. Все добре?
Є запитання з цього приводу?
Є багато різних способів, щоб написати це, а також.
У самому справі, ми можемо зробити щось ще - ми можемо зробити один-лайнер.
Ми можемо зробити одну лінію повернення.
Таким чином, ми дійсно можемо зменшувати перш ніж ми повернемося на цьому.
Таким чином, поклавши - до s.size.
Це робить лінію дуже щільний.
Де різниця між -. З розміром і s.size--
що це постфікси - вони називають це постфікси, тому що - приходить після s.size--
означає, що s.size оцінюється для цілей знаходження індексу
як в даний час, коли ця лінія буде виконана,
і тоді це - відбувається після рядка запускається на виконання.
Після того, як елемент s.size індекс доступний.
І це не те, що ми хочемо, тому що ми хочемо декремент відбудеться в першу чергу.
Othewise, ми будемо отримувати доступ до масиву, по суті, поза законом.
Ми збираємося отримувати доступ до елемента вище тієї, що ми насправді хочемо отримати доступ.
Так, Сем? >> Це швидше і використовує менше пам'яті, щоб в одному рядку чи ні?
[Хардісон] Чесно кажучи, це дійсно залежить.
[Сем, нерозбірливо] >> Так, це залежить від обставин. Ви можете зробити компілятор трюки
щоб отримати компілятор визнати, що, як правило, я вважаю.
>> Таким чином, ми вже говорили трохи про цю річ оптимізації компіляторів
що ви можете зробити в зборі,
і це така річ, що компілятор може бути в змозі з'ясувати,
як Ей, може бути, я можу зробити це все в одній операції,
на відміну від завантаження розмір змінної з оперативної пам'яті,
його зменшення, зберігання його назад, а потім завантаження його знову
Для обробки решті частини цієї роботи.
Але, як правило, немає, це не та річ,
що збирається зробити програму значно швидше.
Є ще питання по стеків?
>> Таким чином, штовхаючись і з'являються. Якщо ви, хлопці, хочете спробувати хакером видання,
те, що ми зробили в хакером видання фактично пішов
і зробив це стек динамічно зростати.
Проблема є в першу чергу тут, в поштовх функції,
щоб з'ясувати, як зробити цей масив рости
як ви продовжувати наполягати більше і більше елементів в стек.
Це насправді не так вже багато додаткового коду.
Просто виклик - ви повинні пам'ятати, щоб отримати дзвінки на Танос там належним чином,
, А потім з'ясувати, коли ви збираєтеся дзвонити перерозподілити.
Це весело проблемою, якщо ви зацікавлені.
>> Але на даний момент, давайте рухатися далі, і давайте поговоримо про черги.
Прокрутіть тут.
Черга близько споріднений стека.
Таким чином, в стеці, речі, які були введені в останньому
були першими речами, щоб потім бути відновлена.
У нас є останній увійшов, першим вийшов, або ЛІФО, замовлення.
У той час як у черзі, як ви очікували б від того, коли ви стоїте в черзі,
Першою людиною, стати в чергу, першою справою, щоб потрапити в чергу,
це перше, що отримує витягується з черги.
Черги також часто використовується, коли ми маємо справу з графіками,
про яку ми говорили коротко стеки,
і черг також зручні для купу інших речей.
Одна річ, яка приходить часто намагається підтримувати, наприклад,
відсортований список елементів.
І ви можете зробити це за допомогою масиву. Ви можете підтримувати відсортований список речей в масиві,
проте там, де стає складно тоді у вас завжди є, щоб знайти
відповідне місце, щоб вставити наступну річ.
Так що якщо у вас є масив чисел, від 1 до 10,
і ви хочете розширити, що для всіх чисел від 1 до 100,
і ви отримуєте цих цифр у довільному порядку і намагалися тримати всі
відсортовано як ви йдете через, ви в кінцевому підсумку доводиться робити багато передач.
При деяких типах черг і деяких видів базових структур даних
Ви можете фактично тримати його досить просто.
Ви не маєте щось додати, а потім перерозподілить все це кожен раз.
Також ви повинні зробити багато зміщення внутрішніх елементів навколо.
Коли ми дивимося на черзі, ви бачите, що - і в queue.c в розділі коду -
Структура, яку ми дали вам дійсно схожа на структуру, яку ми дали вам за стека.
>> Там в один виняток з цього, і що за одним винятком
є те, що у нас є це додаткові ціле число, зване головою,
і голова тут для відстеження голові черги,
або перший елемент у черзі.
З стек, ми змогли відслідковувати елемент, який ми збиралися одержати,
або на вершині стека, використовуючи тільки розмір,
в той час як з чергою, ми мати справу з протилежних кінців.
Ми намагаємося треку речі на кінці, а потім повернути речі з фронту.
Таким чином, ефективно, з головою, у нас є індекс початку черги,
і розмір дає нам індекс кінця черги
так що ми можемо отримати речі з голови і додати речі на хвості.
У той час як зі стеком, ми були тільки коли-небудь справу з вершини стека.
Ми ніколи не мали доступу до нижньої частини стека.
Ми тільки додали речі на верхні і взяв речі з верхньої
так що нам не потрібно, що додаткові поля всередині нашої структури.
Чи означає це взагалі сенс?
Добре. Так, Шарлотта? [Charlotte, нерозбірливо]
[Хардісон] Це велике питання, а що було одне, що прийшли в лекції.
Може бути, йдучи через кілька прикладів проілюструвати, чому
Ми не хочемо, щоб використовувати рядки [0] в якості глави черги.
>> Отже, уявіть, що у нас є черга, ми будемо називати його черга.
На початку, коли ми тільки що створений він,
коли ми тільки оголосили його, ми не ініціалізований нічого.
Це все фігня. Тому, звичайно, ми хочемо переконатися, що ми ініціалізували
і розмір, і глава поля дорівнює 0, то розумно.
Ми також могли б піти далі і обнуляти елементи в нашій черзі.
А щоб ця схема підходить, зауважив, що тепер наша черга може мати тільки трьох елементів;
в той час як наш стек може провести чотири, наша чергу може мати тільки три.
І це тільки щоб зробити схему потрібним.
Перше, що тут відбувається, що ми постановки в чергу рядки "привіт".
І так само, як ми це робили зі стеком, нічого не страшно тут по-іншому,
ми кидаємо рядки, по крайней рядки [0] і збільшуємо наш розмір на 1.
Ми постановки в чергу "до побачення", вона буде надіти.
Так це виглядає як стопка по більшій частині.
Ми почали тут, новий елемент, новий елемент, розміром продовжує йти вгору.
Що відбувається в цей момент, коли ми хочемо щось з черги?
Коли ми хочемо з черги, яка є елементом, який ми хочемо з черги?
[Василь] струнних [0]. >> Zero. Абсолютно вірно, Василь.
Ми хочемо, щоб позбутися від першого рядка, на цей раз, "привіт".
Так що ж інша річ, яка змінилася?
Зверніть увагу, коли ми щось вискочив з стека, ми просто змінили розмір,
але тут, у нас є пара речей, які змінюються.
Не тільки змінити розмір, але глава змін.
Це повертаючись до точки Шарлотти раніше:
чому ми повинні це голова, а?
Чи є сенс зараз, Шарлотта? >> На зразок того.
[Хардісон] Вид? Так що ж сталося, коли ми з черги?
Що ж глава зробити це зараз цікаво?
[Charlotte] О, тому що вона змінилася - все в порядку. Розумію.
Тому що голова - де голова вказує на зміни в плані розташування.
Це вже не завжди нульового індексу. >> Так, саме так.
Те, що відбулося, якщо dequeueing високого елемента
було зроблено, і у нас не було цієї глави поля
тому що ми завжди називав цей рядок в 0 індекс глава нашої черги,
тоді ми повинні перейти решта черзі вниз.
Ми повинні перейти "до побачення" з з рядків [1] рядки [0].
І рядків [2] аж до рядка [1].
І ми повинні зробити це, щоб весь список елементів,
Весь масив елементів.
І коли ми робимо це за допомогою масиву, який отримує дуже дорого.
Так от, це не має великого значення. Ми просто повинні трьох елементів в масиві.
Але якщо у нас була черга з тисяч елементів або мільйон елементів,
а потім все раптово, ми починаємо робити купу з черги називає все в циклі,
речі дійсно збирається сповільнюватися, як він перекладає всі вниз постійно.
Ви знаєте, перекласти на 1, зрушення на 1, зрушення на 1, зрушення на 1.
Замість цього, ми використовуємо цю голову, ми називаємо це "покажчик", хоча це не зовсім покажчик
У строгому сенсі, це не тип покажчика.
Це не Int * або символ * або щось подібне.
Але це вказівки чи із зазначенням глави нашої черги. Так?
>> [Студент] Як йедіеіе знати, щоб просто палити все, що в голову?
[Хардісон] Як йедіеіе знаю, як палити все це в голові? >> Да, да.
>> Що вона дивиться на тільки що голова поле встановлено.
Таким чином, у першому випадку, якщо ми подивимося прямо тут,
наші голови дорівнює 0, індекс 0. >> Праві.
[Хардісон] Так що це просто говорить, добре, добре, елемент з індексом 0, рядок "привіт",
є елементом на чолі нашої черги.
Таким чином, ми збираємося з черги цього хлопця.
І це буде елемент, який отримує повернулися до абонента.
Так, Саад? >> Так глава в основному задає - де ви збираєтеся індексувати?
Ось початок цього? >> Да. >> Добре.
[Хардісон] Це стає новим початком для нашого масиву.
Отже, коли ви щось з черги, все що вам потрібно зробити, це отримати доступ до елемента за індексом q.head,
і це буде елемент, який ви хочете з черги.
Ви також повинні зменшувати розмір.
Ми побачимо в біт, де все стає трохи складніше з цим.
Ми з черги, і тепер, якщо ми знову поставити в чергу,
де ж ми поставити в чергу?
Де наступного елемента піти в нашій черзі?
Скажімо, ми хочемо поставити в чергу рядки "CS".
У якій індекс він піде? [Студенти] струнних [2]. Два >>.
Чому 2, а не 0?
[Василь] Тому що зараз голова 1, так що схоже на початок списку?
[Хардісон] Вірно. А що позначає кінець списку?
Що ми використовуємо для позначення кінця нашої черги?
Голова глава нашої черги, на початку нашої черги.
Що в кінці нашої черги? [Студенти] Size. >> Розмір, точно.
Таким чином, наші нові елементи піти, по крайней розмір, і елементи, які ми злітаємо відірватися на голову.
Коли ми постановки в чергу на наступний елемент, ми поміщаємо його в в розмірах.
[Студент] Перед тим, як покласти, що в, хоча, розмір становив 1, вірно?
[Хардісон] Вірно. Так що не зовсім за розміром. Розмір +, а не +1, але + голова.
Тому що ми перейшли всі по голові суми.
Так от, тепер у нас є черги розміром 1, який починається з індексом 1.
Хвіст індекс 2. Так?
>> [Студент] Що відбувається, коли ви з черги рядки [0], і рядки 'слотів пам'яті
просто отримати спорожніли, в основному, або просто забули?
[Хардісон] Так. У цьому сенсі, ми просто забули їх.
Якби ми були зберігання копій їх -
багато структур даних часто зберігають свої власні копії елементів
так що людина управляє структурою даних не потрібно турбуватися
про те, де всі ці покажчики збираються.
Структура даних виконується на всьому, проводить на всіх копіях,
щоб переконатися, що все зберігається належним чином.
Тим не менш, в даному випадку, ці структури даних тільки для простоти,
не робимо копії всього, що ми зберіганні в них.
[Студент] Так це безперервний масив -? >> Да.
Якщо ми оглянемося на те, що визначення було цієї структури, це так.
Це всього лише стандартний набір, як ви бачили,
масив символів S *.
Чи означає це -? >> Так, мені було просто цікаво
якщо ви в кінцевому підсумку запустити з пам'яті, певною мірою,
якщо у вас є всі ці порожні місця у вашому масиві?
[Хардісон] Так, це хороша точка.
>> Якщо ми подивимося на те, що відбулося зараз в цій точці,
ми заповнили наші черги, як він виглядає.
Але ми дійсно не заповнені нашими черзі
тому що у нас чергу це розмір 2, але він починається з індексу 1,
тому що там наші голови покажчик.
Як ви казали, що елемент рядка [0], індекс 0, насправді не існує.
Це не в нашій черзі більше.
Ми просто не потрудилися піти і переписати його, коли ми його з черги.
Тому, навіть якщо це виглядає як ми запускаємо з пам'яті, ми насправді не мають.
Це місце є для нас, щоб використовувати.
Відповідну поведінку, якби ми намагалися і перший з черги щось
подобається "до побачення", що б поп побачення з.
Тепер наша черга починається з індексом 2 і має розмір 1.
І тепер, якщо ми будемо намагатися поставити в чергу знову щось, скажімо, 50,
50 повинні йти в це місце з індексом 0
тому що він як і раніше доступні для нас. Так, Саад?
[Саад] Чи означає це відбуватиметься автоматично?
[Хардісон] Це не відбувається абсолютно автоматично. Ви повинні зробити математику
щоб змусити його працювати, але по суті те, що ми зробили, ми тільки обгорнутий навколо.
[Саад] І це добре, якщо це має отвір в середині цього?
[Хардісон] Це якщо ми можемо зробити математику працювати належним чином.
>> І виявляється, що це насправді не так вже важко зробити з модом оператора.
Так само, як ми це робили з Цезарем і матеріал крипто,
використання мода, ми можемо домогтися, щоб обернути навколо і продовжувати йти
навкруги і навколо нашої черги,
підтриманню, що голова покажчик пересуватися.
Зверніть увагу, що розмір завжди повазі кількість елементів насправді в черзі.
І це тільки голова покажчик, який тримає велосипеді через.
Якщо ми подивимося на те, що сталося тут, якщо ми повернемося до початку,
і ви тільки подивіться, що відбувається в голові
Коли ми щось поставити в чергу, нічого не сталося з головою.
Коли ми в черзі щось ще, нічого не сталося з головою.
Як тільки ми щось з черги, голова йде вгору на одну.
Ми в черзі щось, нічого не відбувається в голові.
Коли ми щось з черги, раптом голова чинить зріст.
Коли ми щось поставити в чергу, нічого не відбувається в голові.
>> Що відбудеться в цей момент, якщо б ми з черги знову щось?
Будь-які думки? Що буде з головою?
Що має відбутися в голову
якщо б ми з черги щось ще?
Голова прямо зараз з індексом 2,
Це означає, що глава чергу рядків [2].
[Студент] Який повертає 0? >> Вона повинна повертати 0. Слід обернути навколо спини, точно.
До цих пір, кожен раз, коли ми дзвонили з черги, ми були додавши до нього один в голову,
додати до голови, додайте один в голову, додайте один в голову.
Як тільки що голова покажчик потрапляє на останній індекс в масиві,
Потім ми повинні обернути його назад до початку, поверніться до 0.
[Charlotte] Що визначає здатність черзі в стеку?
[Хардісон] У цьому випадку, ми просто використовували # визначена постійна. >> Добре.
[Хардісон] У реальній. Файл C, ви можете піти і скинути з неї трохи
і зробити це як великий або як мало, як ви хочете.
[Charlotte] Отже, коли ви робите це черзі, як ви робите комп'ютера знаю
наскільки великий Ви хочете, щоб стік бути?
[Хардісон] Це велике питання.
Є кілька способів. Одним з них є просто визначити його передня
і сказати, що це буде черги, яка має 4 елементи або 50 елементів або 10.000.
Інший спосіб зробити те, що люди, хакер видання робить
і створити функції, щоб ваша черга динамічно зростати, як інші речі додаються дюйма
>> [Charlotte] Так, щоб піти з першим варіантом, який синтаксис ви використовуєте
вказати програмі, що розмір черги?
[Хардісон] Ah. Отже, давайте з цього.
Я все ще в stack.c тут, так що я просто хочу, щоб прокрутити до самого верху тут.
Ви можете побачити це прямо тут? Це # визначити ємність 10.
І це майже точно такий же синтаксис, який ми маємо для черги.
За винятком чергу, ми отримали, що додаткове поле структури тут.
[Charlotte] О, я думав, що потужність означає здатність до рядка.
[Хардісон] Ah. >> Що це максимальна довжина слова. >> Є.
Так. Ємність тут - це відмінна точка.
І це щось, що складно
тому що ми оголосили тут масив символів S *.
Масив покажчиків.
Це масив символів.
Це, напевно, те, що ви бачили, коли ви були ваші оголошення буферів для файлового введення / виводу,
коли ви створювали рядки вручну в стеці.
Однак те, що ми маємо тут являє собою масив символів S *.
Так що це масив покажчиків.
Насправді, якщо ми масштаб, і ми подивимося, що тут відбувається
У презентації, ви бачите, що фактичні елементи, характер даних
не зберігається в масиві себе.
Що зберігається в нашому масиві тут є покажчиками на символьні дані.
Добре. Таким чином, ми бачили, як розмір черги такої ж, як зі стеком,
Розмір завжди з повагою відноситься до числа елементів в даний час в черзі.
Після того, як 2 ставить в чергу, розмір 2.
Після того, як з черги розмірі Зараз 1.
Після того, як інший постановки в чергу Розмір назад до 2.
Так що розмір, безумовно поважає число елементів в черзі,
, А потім голову просто тримає на велосипеді.
Це йде від 0-1-2, 0-1-2, 0-1-2.
І кожен раз, коли ми називаємо з черги, керівник отримує покажчик збільшиться до наступного індексу.
І якщо голова збирається переходити, він повертається назад близько 0.
Так з цим, ми можемо написати функцію з черги.
І ми збираємося залишити функцію постановки в чергу для вас, хлопці, а не для реалізації.
>> Коли ми з черги елемента з нашої черги,
те, що було перше, що зробив Данило, коли ми почали писати поп-функції для стеків?
Дай мені почути від когось, хто не говорив ще.
Давайте подивимося, Саад, ти пам'ятаєш, що Даніель зробив так, як перше, що коли він писав поп?
[Саад] Там було, це було - >> Він випробував щось.
[Саад] Якщо розмір більше, ніж 0. >> Саме так.
І те, що було, що тестування на?
[Саад] Це було випробування, щоб подивитися, чи є щось всередині масиву.
[Хардісон] Так. Саме так. Таким чином, ви не можете поп-небудь з стека, якщо вона порожня.
Крім того, ви не можете нічого з черги з черги, якщо вона порожня.
Що таке перше, що ми повинні зробити в нашій йедіеіе функції тут, як ви думаєте?
[Саад] Якщо розмір більше 0? >> Да.
У цьому випадку, я на самом деле просто перевіряв, щоб побачити, якщо вона дорівнює 0.
Якщо він дорівнює 0, ми можемо повернутися нульовий.
Але точно така ж логіка.
І давайте продовжимо з цим.
Якщо розмір не дорівнює 0, де знаходиться елемент, який ми хочемо з черги?
[Саад] В голові? >> Саме так.
Ми можемо просто взяти і вийняти перший елемент в нашій черзі
при зверненні до елементу в голову.
Нічого не божевільний.
Після цього, що ми повинні робити? Що має статися?
Яка була інша річ, про які ми говорили в йедіеіе?
Дві речі повинні відбутися, тому що наша черга змінився.
[Даниїл] Зменшення розміру. >> Ми повинні зменшити розмір і збільшити голову? Саме так.
Для збільшення голови, ми не можемо сліпо збільшити голову, пам'ятаю.
Ми не можемо просто зробити queue.head + +.
Ми повинні також включати цей мод по потужності.
І чому ми мода на потужність, Stella?
[Stella] Тому що він має, щоб обернути навколо. >> Саме так.
Ми мод по потужності, оскільки вона має обернути назад до 0.
Так от, на даний момент, ми можемо робити те, що сказав Деніел.
Ми можемо зменшувати розмір.
І тоді ми можемо просто повернути елемент, який був на початку черги.
Це виглядає роду незграбний на перший погляд. Ви можете їсти запитання. Пробачте?
>> [Сем] Чому це спочатку в початок черги? Де це піти?
[Хардісон] Воно походить від четвертому рядку знизу.
Після того як ми перевірити, щоб переконатися, що наша черга не порожня,
Ми витягнути символ * По-перше, ми витягнути елемент, який сидить на чолі індексу
нашого масиву, наші рядків масиву, >> і виклик, який в першу чергу?
[Хардісон] І ми називаємо це в першу чергу. Так.
Просто стежити за що, чому ви думаєте, ми повинні були це зробити?
[Сем] Кожен перший просто повернення q.strings [q.head]? >> Да.
>> Тому що ми робимо це зміна q.head з модом функції,
і немає ніякого способу зробити це в зворотній лінії теж.
[Хардісон] Саме так. Ти пляма на. Сем абсолютно місцем на.
Причина ми повинні були витягти перший елемент в нашій черзі і зберегти його в змінну
тому, що це лінія, де ми тільки що q.head,
Тобто мод оператора там не те, що ми можемо зробити
і вона набуде чинності на голові без - в одну лінію.
Таким чином, ми насправді потрібно витягти перший елемент, а потім налаштувати голову,
змінити розмір, а потім повернути елемент, який ми витягнули.
І це те, що ми побачимо придумали пізніше
зв'язані списки, як ми пограти з ними.
Часто, коли ви звільненні або утилізації зв'язані списки
Ви повинні пам'ятати, наступний елемент, наступний покажчик зв'язаний список
Перед утилізацією поточного.
Тому що в противному випадку ви викинете інформацію про те, що залишилося в списку.
Тепер, якщо ви йдете в прилад, ви відкриєте queue.c--х з цього.
Так що, якщо я відкриваю queue.c, дозвольте мені збільшити тут,
Ви побачите, що у вас є подібний вид файлу.
Схожі вид файлу, що ми мали раніше з stack.c.
У нас є наша структура для черги визначається так само, як ми бачили на слайдах.
>> У нас є поставити в чергу функцію, яка для вас зробити.
А у нас з черги функцій тут.
Йедіеіе функції у файлі невиконаними,
Але я покладу його назад на PowerPoint, так що ви можете ввести його, якщо ви хочете.
Таким чином, протягом наступних 5 хвилин або близько того, ви, хлопці працюють на постановки в чергу
яка майже прямо протилежна з черги.
Ви не повинні регулювати голову, коли ви enqueueing, але те, що ви повинні налаштувати?
Розмір. Отже, коли ви постановки в чергу, голова залишається недоторканою, розмір не змінюється.
Але для цього треба небагато - вам доведеться пограти з цим мод
, Щоб з'ясувати точно, що індекс нового елемента має бути вставлений в.
Тому я дам вам, хлопці трохи, поклав назад з черги на слайді,
і як ви, хлопці, є питання, кричати їх, так що ми можемо
всі розмови про них як про групу.
Крім того, з розміром ви не - при налаштуванні розміру, ви завжди можете просто -
Ви повинні мода розмір небудь? [Даниїл] Немає >> Ви не повинні мода розміру, мають рацію.
Оскільки розмір буде завжди, якщо ви - передбачається, що ви все правильно управляти,
Розмір завжди буде між 0 і 3.
Де ви повинні мода, коли ви робите постановки в чергу?
[Студент] Тільки для голови. >> Тільки за голову, точно.
І чому ви повинні мода на всі постановки в чергу?
Коли ситуація, в якій вам доведеться мода?
[Студент] Якщо у вас є речі в просторі, як на просторах 1 і 2,
, А потім вам потрібно додати щось в 0.
[Хардісон] Так, саме так. Таким чином, якщо ваша голова покажчик знаходиться в самому кінці,
або якщо ваш розмір плюс ваша голова більше, або, скоріше, буде обернути навколо черзі.
>> Таким чином, в цій ситуації, що ми отримали тут, на слайді прямо зараз,
якщо я хочу щось поставити в чергу прямо зараз,
Ми хочемо поставити в чергу щось за індексом 0.
Так що якщо ви подивитеся, де в 50 йде, і я закликаю епдіеіе 50,
вона йде там на дні. Він йде в індекс 0.
Він замінює «привіт», яка вже була видалена з черги.
[Даниїл] Не ви піклуєтеся про те, що в йедіеіе вже?
Чому він нічого зробити з головою постановки в чергу?
[Хардісон] Ах, так ви не змінивши головою, вибачте.
Але ви повинні використовувати мод оператора, коли ви звертаєтеся
елемент, який ви хочете поставити в чергу, коли ви звертаєтеся
Наступний елемент в черзі.
[Василь] я цього не зробив, і я отримав "Успіх" там.
[Даниїл] О, я розумію, що ви говорите.
[Хардісон] Таким чином, ви didn't - ви тільки що зробили в q.size?
[Василь] Так. Я просто перейшла на інший бік, я нічого не робив з головою.
[Хардісон] Ви насправді не мають для скидання головою бути що завгодно,
але коли ви індекс в масиві рядків,
Ви насправді потрібно йти вперед і обчислити, де наступний елемент,
тому що лоза стека, наступний елемент в стеку завжди була
на індекс, відповідний розмір.
Якщо ми оглянемося назад в нашому функцією натискання стека,
Ми завжди міг жбурнути в нашому новому елементі права на розмір індексу.
У той час як з чергою, ми не можемо зробити це
тому що, якщо ми в цій ситуації,
якщо ми в черзі 50 наших новарядок буде йти прямо на рядки [1]
які ми не хочемо робити.
Ми хочемо, щоб новий рядок піти на індекс 0.
>> Хто-небудь - так? [Студент] У мене є питання, але це насправді не пов'язані між собою.
Що це означає, коли хтось просто викликає щось подібне до PRED покажчик?
Що ця назва скорочено? Я знаю, це просто назва.
[Хардісон] Pred покажчик? Давайте подивимося. В якому контексті?
[Студент] Це було для вставки. Я можу поставити вам пізніше, якщо ви хочете
тому що це насправді не пов'язані, але я просто -
[Хардісон] З вставки коду Давид з лекції?
Ми можемо тягнути, що і говорити про це.
Ми поговоримо про це наступного, як тільки ми доберемося до пов'язаних списків.
>> Так що давайте дійсно швидко поглянути на те, що функція постановки в чергу виглядає.
Якою була перша річ, яку люди намагалися зробити у вашій постановки в чергу рядки? У цій черзі?
Як і те, що ви зробили для стека натисненням.
Що ви робили, Стела?
[Stella, нерозбірливо]
[Хардісон] Саме так. Якщо (q.size == місткості) -
Мені потрібно поставити мою дужки в потрібному місці - повернутися помилковим.
Збільшити небагато. Добре.
Тепер те, що наступна річ, яку ми повинні були зробити?
Так само, як зі стеком, і вставляється в потрібне місце.
І те, що було в потрібному місці, щоб вставити це?
З стек це був розмір індексу, з цим не зовсім так.
[Даниїл] У мене є q.head--або - q.strings? >> >> Да.
q.strings [q.head + q.size мод якості]?
[Хардісон] Ми, ймовірно, хочуть поставити дужки навколо цього
так що ми отримуємо відповідний пріоритет і так ось cleart для всіх.
І встановлено, що рівні? Щоб >> вул? Щоб >> вул. Великий.
А тепер те, що остання річ, яку ми повинні зробити?
Так само, як ми це робили в стеці. >> Прирощення розміру? >> Прирощення розміру.
Boom. А потім, оскільки стартовий код щойно повернувся помилкової за замовчуванням,
Ми хочемо змінити це вірно, якщо все проходить і все йде добре.
Добре. Це дуже багато інформації для розділу.
Ми не зовсім закінчена. Ми хочемо говорити про дійсно швидко односвязного списку.
Я покладу це так, ми можемо повернутися до нього пізніше.
Але давайте повернемося до нашої презентації всього за кілька слайдів.
Так епдіеіе є TODO, тепер ми зробили це.
>> Тепер давайте поглянемо на односвязного списку.
Ми говорили про це трохи більше в лекції.
Як багато хто з вас, хлопці побачили демо, де у нас були люди
ніяково вказуючи один до одного і проведення цифри? >> Я була в цьому.
>> Що ви думаєте, хлопці? Хіба що, як ми сподіваємося прояснити це трохи?
У списку, то виходить, що ми маємо справу з цим типом, який ми будемо називати вузлом.
У той час як з чергою і стеком у нас були структури, які ми назвали б черги в стеку,
у нас були ці нові черги в стеку типу,
Тут список насправді просто складається з купу вузлів.
Таким же чином, що рядки просто набір символів всі вишикувалися поруч один з одним.
Зв'язаний список всього вузла і інший вузол, а інший вузол, а інший вузол.
І замість того, розбивши всі вузли разом, і зберігати їх безперервно
всі поруч один з одним в пам'яті,
з цієї наступний покажчик дозволяє зберігати вузлах, де, у випадковому порядку.
А потім начебто проводів їх всі разом, щоб вказати від одного до іншого.
>> І те, що було великою перевагою, що це було більш ніж масив?
За зберігання всі безперервно просто застряг поруч один з одним?
Ви пам'ятаєте? Так? >> Динамічний розподіл пам'яті?
>> Динамічний розподіл пам'яті в якому сенсі?
[Студент], що ви можете зробити його ще більше, і ви не повинні перемістити весь масив?
[Хардісон] Саме так. Таким чином, з масивом, коли ви хочете поставити новий елемент в середині,
Ви повинні перейти все, щоб звільнити місце.
І, як ми говорили з чергою,
Ось чому ми тримаємо голову, що покажчик,
так що ми не постійно міняються речі.
Тому що стає дорогим, якщо у вас є великий масив
і ви постійно робите ці випадкові вставки.
У той час як зі списком, все що вам потрібно зробити, це викинути його на новий вузол,
налаштувати покажчики, і ви зробили.
Що смокче з цього приводу?
Крім того, що це не так просто, як працювати з масивом? Так?
[Даниїл] Ну, я думаю, це набагато важче отримати доступ до певного елемента в зв'язаному списку?
[Хардісон] Ви не можете просто перейти до довільного елементу в середині вашого пов'язаного списку.
Як ви повинні це зробити замість цього? >> Ви повинні покроково всю річ.
[Хардісон] Так. Ви повинні пройти по одному, по одному за раз.
Це величезна - це біль.
Що з іншого - є ще один крах до цього.
[Василь] Ви не можете піти вперед і назад? Ви повинні йти в одному напрямку?
[Хардісон] Так. Так як же нам вирішити, що іноді?
[Василь] двунаправленного списків? >> Саме так. Є двічі зв'язані списки.
Є також - шкода?
>> [Сем] Це те ж саме, що і використання PRED те, що -
Я тільки що згадав, це не те, що PRED річ, це?
Хіба це не між двох-і поодинці?
[Хардісон] Давайте подивимося, що саме він робить.
Таким чином, тут ми йдемо. Ось список коду.
Тут ми маємо predptr, тут. Це те, що ви говорите?
Так що це було - він звільняючи список, і він намагається зберегти покажчик на нього.
Це не двічі, окремо зв'язані списки.
Ми можемо поговорити про це пізніше, оскільки це говорить про звільнення список
і я хочу показати деякі інші речі першої.
але це просто - це пам'ятати значення PTR
[Студент] О, це попередньої покажчик? >> Да.
Так що ми можемо збільшити PTR себе, перш ніж ми тоді безкоштовно, що є predptr.
Оскільки ми не можемо безкоштовно PTR, а потім викликати PTR = PTR далі, чи не так?
Це було б погано.
Отже, давайте подивимося, повернемося до цього хлопця.
>> Інші погані речі про списках є те, що в той час як з масивом
ми просто повинні все самі елементи укладені поруч один з одним,
Тут ми також ввели цей покажчик.
Так що є додатковий блок пам'яті, що ми вдаючись до використання
для кожного елемента, що ми зберіганні в нашому списку.
Ми отримуємо гнучкість, але це пов'язано з певними витратами.
Він поставляється з цим витрати часу,
і він приходить з цією пам'яттю вартість теж.
Час в тому сенсі, що ми тепер повинні пройти через кожен елемент масиву
щоб знайти той, з індексом 10, або, що було б індекс 10 в масиві.
>> Просто дуже швидко, коли ми діаграму з цих списків,
Зазвичай ми проводимо на голову списку або перший покажчик списку
і відзначити, що це є істинним покажчиком.
Це просто 4 байт. Це не самого вузла.
Таким чином, ви бачите, що він не має цілочисельне значення в ній, не наступного покажчика в ньому.
Це буквально покажчик.
Це буде вказувати на те, що фактична структура вузла.
[Сем] покажчик називається вузол? >> Це - ні. Це покажчик на щось типу вузла.
Це покажчик на вузол структури. >> Ну, гаразд.
Діаграма зліва, код праворуч.
Ми можемо встановити його в нуль, який є гарним способом для початку.
При схемі, ви або написати його в якості нульового або ви покладете лінії, що проходить через це так.
>> Один з найпростіших способів роботи зі списками,
і ми просимо Вас як додаємо і додаємо побачити відмінності між ними,
але додаючи, безумовно, легше.
Коли ви випереджати, це, де ви - коли ви додаємо (7),
Ви йдете і створити вузол структури
і ви встановили першим вказав на це, тому що зараз, так як ми додається його,
це буде на початку списку.
Якщо ми додаємо (3), що створює ще один вузол, але тепер 3 йде до 7.
Таким чином, ми істотно натисканням речі на нашому списку.
Тепер ви можете бачити, що початок, кінець, іноді люди називають його штовхати,
тому що ви натискаєте новий елемент на вашому списку.
Це також легко видалити в передній частині списку.
Таким чином, люди часто називають це поп-музики.
І в цьому випадку, ви можете емулювати стек за допомогою пов'язаного списку.
Вигуки. На жаль, зараз ми входимо в додавання. І ось ми додається (7), тепер ми додаємо (3).
Якщо додається щось ще на цей список, якщо ми додається (4),
Потім ми повинні були б 4, а потім 3, а потім 7.
І тоді ми могли б поп-і видалити 4, видалити 3, видалити 7.
Часто більш інтуїтивний спосіб думати про це з додавання.
Так що я діаграмі, що вона буде виглядати з додати тут.
Тут додається (7) не виглядає по-іншому
тому що є тільки один елемент у списку.
І додавання (3) ставить його в кінці.
Може бути, ви можете побачити прямо зараз трюк з додавання
є те, що, так як ми тільки знаємо, де на початку списку,
додати в список, треба пройти весь шлях до кінця списку
щоб дістатися до кінця, зупинити, а потім побудувати свій вузол і бухнути все вниз.
З'єднайте всі речі вгору.
Так що з початок, кінець, як ми тільки що розірвав це дійсно швидко,
При випереджати в список, це досить просто.
>> Ви робите свій новий вузол, включають деякі динамічного розподілу пам'яті.
Отже, ось що ми робимо вузол структури використанням Танос.
Так Танос ми використовуємо, тому що буде виділено пам'яті для нас, для подальшого
тому що ми не хочемо цього - ми хочемо, щоб ця пам'ять збережеться протягом тривалого часу.
І ми отримуємо покажчик на місце в пам'яті, що ми просто виділені.
Ми використовуємо розмір вузла, ми не підвести поля.
Ми не вручну генерувати кількість байтів,
замість цього ми використовуємо SizeOf, так що ми знаємо, ми отримуємо відповідну кількість байтів.
Ми дбаємо про те, щоб перевірити, що наш Танос виклику вдалося.
Це те, що ви хочете зробити в цілому.
На сучасних машинах, йде з пам'яті це не те, що легко
якщо ви виділенні тонни матеріалу і вносять величезний список,
Але якщо ви будуєте речі, скажімо, як iPhone або Android,
у вас є обмеженість ресурсів пам'яті, особливо якщо ви робите щось інтенсивно.
Так що це добре, щоб отримати на практиці.
>> Зверніть увагу, що я використав кілька різних функцій тут
що ви бачили, що це свого роду нове.
Так Fprintf такий же, як Printf
крім її перший аргумент є потік, в який ви хочете надрукувати.
У цьому випадку, ми хочемо, щоб друкувати на стандартний рядок помилки
, Який відрізняється від стандартного outstream.
За умовчанням вона з'являється в тому ж місці.
Вона також виводить на термінал, а можна -
за допомогою цих команд ви дізналися про, методи перенаправлення
Ви дізналися про в відео Томмі проблемою для безлічі 4, Ви можете направляти її
в різних областях, а потім вийти, прямо тут, виходить вашу програму.
Це, по суті, як повертався з головних,
за винятком ми використовуємо вихід, тому що тут повернення не буде нічого робити.
Ми не в основній, так що повертатися не вийти з програми, як ми хочемо.
Тому ми використовуємо функцію виходу і дати йому код помилки.
Тоді тут ми встановлюємо значення нового вузла поля, його я поля рівним я, а потім підключити його.
Ми встановили наступний покажчик нового вузла, щоб вказати на перший,
, А потім першим буде вказувати на новий вузол.
Ці перші рядки коду, ми фактично будівництво нового вузла.
Не дві останні рядки цієї функції, але перший з них.
Ви дійсно можете вийти в функцію, у допоміжну функцію.
Це часто, що я роблю, я витягти його в функцію,
Я називаю це щось подібне вузла зборки,
і що тримає додаємо функцію досить невеликий, це просто 3 лінії тоді.
Я роблю виклик моїй функції вузла зборки, а потім я дроти все вгору.
>> Останнє, що я хочу показати вам,
і я дам вам зробити додавання і все, що на свій власний,
як для перебору списку.
Є безліч різних способів для перебору списку.
У цьому випадку, ми збираємося, щоб знайти довжину списку.
Отже, ми починаємо з довжиною = 0.
Це дуже схоже на написання StrLen для рядка.
Це те, що я хочу показати вам, це цикл прямо тут.
Це виглядає свого роду фанк, це не звичайна Int я = 0, <що завгодно, я + +.
Замість цього він ініціалізацію нашої змінної п буде на початку списку.
І потім, коли наш ітератор змінної не є нульовим, ми продовжуємо.
Це тому, що, за угодою, в кінці нашого списку буде нульовим.
І тоді, щоб збільшити, а не робити + +,
Зв'язаний список еквіваленті + + п = п-> далі.
>> Я дам вам заповнити прогалини тут, тому що ми знаходимося поза часом.
Але майте це на увазі, як ви працюєте на psets spellr.
Зв'язані списки, якщо ви реалізуєте хеш-таблиці,
, Безумовно, дуже зручний.
І з цієї ідіомою цикл над речами зробить життя набагато простіше, сподіваюся.
Будь-які питання, швидко?
[Сем] Чи будете ви відправити заповнену SLL і ПК?
[Хардісон] Так. Я буду посилати завершена слайди і завершив стек SLL і queue.cs.
[CS50.TV]