Джейсон Хіршхорна: Вітаю всіх в розділі Seven. Ми знаходимося в тиждень сім курсу. І майбутній четвер Хеллоуїн, так що я одягнені як гарбуз. Я не міг нахилитися і покласти на мої черевики, так ось чому я просто носити шкарпетки. Я також нічого не носити під це, тому я не можу зняти його, якщо це відволікаючи до вас. Заздалегідь прошу вибачення за це. Вам не потрібно представити що відбувається. Я ношу боксерів. Так що все добре. 

У мене є довгий розповідь про те, чому я одягнений як гарбуза, але я збираюся крім того, що пізніше в цьому розділі тому що я хочу, щоб почати роботу. У нас є багато цікавих речей, перейти на цьому тижні. Більшість з них мають безпосереднє відношення до цього тижня проблема набір, друкарськими помилками. Ми збираємося йти по пов'язані списки та хеш-таблиці для всієї секції. Я поклав цей список щотижня, список ресурси для вас, щоб допомогти вам матеріал на цьому курсі. Якщо у збиток або якщо заводжуся більше інформації, перевірити один з ці ресурси. 

Знову ж, pset6 є друкарськими помилками, PSET на цьому тижні. І це також закликає вас, і я рекомендуємо вам, щоб використовувати деякі інші ресурси спеціально для цієї PSet. Зокрема, три у мене є перераховані на екрані - GDB, який ми були знайомі з і використовували на деякий час тепер, є буде дуже корисно на цьому тижні. Так що я поклав, що тут. Але всякий раз, коли ви працюєте з C, ви завжди повинні використовувати GDB для налагодження програм. На цьому тижні також Valgrind. Хто-небудь знає, що Valgrind робить? 

АУДИТОРІЯ: Він перевіряє витоків пам'яті? 

Джейсон Хіршхорна: Valgrind перевіряє витоку пам'яті. Так що якщо ви Танос щось у вашому Програма, ви просите пам'яті. Наприкінці програми, у вас є написати безкоштовно на все, що ви malloced дати пам'ять назад. Якщо ви не пишете безкоштовно в кінці і ваша програма приходить до висновку, все автоматично бути звільнені. А для невеликих програм, це не так вже страшно. Але якщо ви пишете довгий хід програма, що не вийде, обов'язково, протягом декількох хвилин або пару секунд, потім витоку пам'яті може стати величезна угода. 

Таким чином, для pset6, очікується, що ви будете мати витоків нульові пам'яті з ваша програма. Для перевірки витоку пам'яті, запустіть Valgrind і вона буде давати вам деякі цікаві Вихід даючи вам знати чи або не все було безкоштовно. Ми будемо практикувати з цим пізніше сьогодні, з надією. 

Нарешті, команда різн .. Ви щось схоже на нього використовується в pset5 з інструментом швидкого погляду. Дозволено вам заглянути всередину. Ви також використовується диференціал теж за проблема встановити спец. Але в дозволив вам порівняння двох файлів. Ви можете порівняти файл растрового зображення і Інформація заголовки розчину персоналу та Ваше рішення в pset5 якщо ви вирішили використовувати його. Різниця дозволить вам зробити це, а також. Ви можете порівняти правильну відповідь для Проблема цьому тижні встановити на свій відповідь і подивитися, якщо він вибудовується в лінію або см. де помилки. 

Отже, це три хороших інструментів, які Ви повинні використовувати протягом цього тижня, і обов'язково перевірити вашу програму з цими трьома інструментами перед включенням його дюйма Знову ж, як я вже згадував щотижня, якщо у вас є зворотній зв'язок для мене - як позитивним і конструктивним - не соромтеся, щоб очолити на сайт в нижній частині цього слайда і ввести його там. Я дуже ціную будь і все із зворотним зв'язком. І якщо ви дасте мені конкретні речі, які Що я можу зробити, щоб поліпшити або, що я все добре, що ви хотіли, щоб я продовжити, я беру це близько до серця і дійсно дуже стараються слухати ваші відгуки. Я не можу пообіцяти, що я збираюся зробити все, хоча, як носити гарбуз костюм щотижня. 

Отже, ми збираємося провести більшу частину розділ, як я вже говорив, йдеться про зв'язані списки і хеш-таблиці, які буде безпосередньо застосовні до Проблема встановити на цьому тижні. Пов'язані списки ми підемо на відносно швидко, тому що ми витратили справедливий біт часу збирається над нею в розділі. І тому ми отримати прямо в кодування проблеми для пов'язаних списків. А потім в кінці ми поговоримо про хеши і як вони застосовуються до цього Проблема тижні встановити. 

Ви бачили цей код раніше. Це структура, і це визначення щось нове називається вузлом. А усередині вузла існує ціле прямо тут і є вказівник на інший вузол. Ми бачили це раніше. Це було придумувати для пару тижнів зараз. Вона поєднує в собі покажчики, які ми відвідували роботи з, і структури, які дозволяють нам об'єднати два різних речі в один тип даних. 

Там дуже багато відбувається на екрані. Але все це має бути відносно знайомі з вами. На першій лінії, ми оголосити новий вузол. А потім всередині цієї нового вузла, я поставив ціле число в цьому вузлі до одного. Ми бачимо, на наступному рядку я роблю Е команда, але я сірим кольором команда Е, тому що насправді Важливою частиною є ця лінія тут - new_node.n. Що точка на увазі? 

АУДИТОРІЯ: Перейдіть у вузол і оцінити вартість н для нього. 

Джейсон Хіршхорна: Це Абсолютно вірно. Dot означає переходу до північна частина цього нового вузла. У наступному рядку що робить? Майкл. 

АУДИТОРІЯ: Створюється ще один вузол що буде вказувати на новий вузол. 

Джейсон Хіршхорна: Так це не створити новий вузол. Він створює те, що? 

АУДИТОРІЯ: Покажчик. 

Джейсон Хіршхорна: покажчик на вузол, як зазначено цьому вузол * тут. Таким чином, це створює покажчик на вузол. І який вузол він вказуючи щоб, Майкл? 

АУДИТОРІЯ: Новий вузол? 

Джейсон Хіршхорна: Новий вузол. І це вказує там, тому що ми дав йому адресу нового вузла. І тепер в цій лінії ми бачимо два різні способи висловлюючи те ж саме. І я хотів би відзначити, як ці дві речі однакові. У першому рядку ми разименовать покажчик. Так ми йдемо до вузла. Це те, що ця зірка означає. Ми бачили, що перед з покажчиками. До цього вузла. Ось в дужках. А потім доступ через оператора точки н елементом цього вузла. 

Так що бере синтаксис ми побачили прямо тут і зараз використовувати його з покажчиком. Звичайно, він отримує трохи зайнятий, якщо ви пишете ці дужки - що зірка і що крапка. Це стає трохи зайнятий. Тому у нас є деякі синтаксичний цукор. І ця лінія прямо тут - ptr_node-> п. Це робить точно такий же речі. Так що ті два рядки коду еквівалентні і буде робити та ж сама річ. 

Але я хотів би відзначити тих, перед ми підемо далі, щоб ви розумієте що дійсно ця річ прямо тут є просто синтаксичний цукор для разименованія покажчик, а потім збирається н частиною цієї структури. Будь-які питання про цьому слайді? ОК. 

Так що ми збираємося пройти через пару операцій, які ви можете зробити на зв'язані списки. Зв'язаний список, нагадаємо, являє собою серію вузлів, які вказують на іншому. І ми зазвичай починають з покажчиком називається глава, як правило,, що вказує на перше, що в списку. Так на першій лінії тут, ми є наш початковий L в першу чергу. Так що, що ви можете думати - це текст прямо тут ви можете думати про якість просто покажчик ми зберегли десь, що точки на перший елемент. І в цьому пов'язаного списку у нас є чотири вузла. Кожен вузол являє собою великий ящик. Чим більше коробка всередині великої коробка ціла частина. І тоді у нас є вказівник участь. 

Ці коробки не тягне шкала тому, наскільки велика собою ціле число в байтах? Наскільки велика зараз? Чотири. І, наскільки великий це покажчик? Чотири. Так насправді, якщо ми повинні були зробити це в масштабі обидві коробки буде такий же розмір. У цьому випадку, ми хочемо, щоб вставити щось у зв'язаному списку. Таким чином, ви можете бачити тут ми вставки п'ять Ми пройти через зв'язаний список, знайти, де п'ять йде, а потім вставте його. 

Давайте розберемо, що вниз і йти трохи повільніше. Я збираюся вказати на борту. Так у нас є вузол п'ять, що ми створили в mallocs. Чому всі сміються? Жартую. ОК. Таким чином, ми malloced п'ять. Ми створили цей вузол десь в іншому місці. У нас є це готові піти. Ми починаємо в передній частині наш список з двома. І ми хочемо, щоб вставити в відсортованому моди. 

Так що, якщо ми бачимо два, і ми хочемо, щоб покласти в п'ять, що ж нам робити, коли ми бачимо, щось менше, ніж ми? Що? Ми хочемо, щоб вставити п'ять у це зв'язаний список, зберігаючи його сортувати. Ми бачимо, номер два. Так що ж нам робити? Маркус? 

АУДИТОРІЯ: Зателефонуйте покажчик до наступного вузла. 

Джейсон Хіршхорна: І чому ми йдемо до наступного? 

АУДИТОРІЯ: Тому що це Наступний вузол у списку. І ми знаємо тільки, що інше місце. 

Джейсон Хіршхорна: І п'ять більше, ніж два, зокрема. Тому що ми хочемо, щоб тримати його відсортований. Так п'ять більше двох. Таким чином, ми перейдемо до наступного. І тепер ми досягнемо чотири. І що відбувається, коли ми досягаємо чотири? 

П'ять більше чотирьох. Так ми продовжуємо. І тепер ми в шість. І що ж ми бачимо в шість? Так, Карлос? 

АУДИТОРІЯ: Шість більше п'яти. 

Джейсон Хіршхорна: Шість є більше п'яти. Так от де ми хочемо вставити п'ять. Однак, майте на увазі, що якщо ми є тільки один покажчик тут - це наша додаткова покажчик ось обході за списком. І ми вказуємо до шести. Ми втратили слід того, що приходить раніше шести. Так що, якщо ми хочемо, щоб вставити щось у цей список тримати його сортують, ми ймовірно, потрібно, як багато покажчиків? 

АУДИТОРІЯ: Два. 

Джейсон Хіршхорна: Два. Один відстежувати струму один і один, щоб відстежувати попередній. Це тільки односпрямований список. Це тільки йде в одному напрямку. Якби ми мали двусвязний список, де все було вказуючи на речі після нього і речі до нього, то ми не повинні були б зробити це. Але в даному випадку ми не хочемо втратити трек, що було до нас, у разі ми повинні вставити п'ять десь в середині. Скажімо, у нас були вставки дев'ять. Що станеться, коли ми дісталися до восьми? 

АУДИТОРІЯ: Ви повинні були б отримати, що порожню точку. Замість того, нульову точку, яку ви повинні були б додати елемент, а потім є він вказував на дев'яти. 

Джейсон Хіршхорна: Абсолютно вірно. Отже, ми отримуємо вісім. Ми дійдете до кінця списку, тому що це вказує на нуль. І тепер, замість того, він вказував на нуль у нас він вказував на наш новий вузол. І ми встановити покажчик в наш новий вузол на нуль. Хто-небудь є які-небудь питання про вставці? Що, якщо я не піклуються про зберігаючи список упорядковано? 

АУДИТОРІЯ: Дотримуйтеся його на початку або в кінці. 

Джейсон Хіршхорна: Дотримуйтеся його на початок або кінець. Який ми повинні робити? Боббі? Чому кінець? 

АУДИТОРІЯ: Тому що початок вже заповнений. 

Джейсон Хіршхорна: ОК. Початок вже заповнена. Хто хоче сперечатися з Боббі. Маркус. 

АУДИТОРІЯ: Ну ви, ймовірно, хочете дотримуватися його на початку, тому що в іншому випадку, якщо ви кладете його на кінець вам доведеться пройти весь список. 

Джейсон Хіршхорна: Абсолютно вірно. Так що, якщо ми думаємо про виконання, Час роботи, включивши в кінці б н, розмір цього. Що таке велика O виконання вставки на початку? Постійний час. Так що, якщо ви не дбаєте про збереження щось сортуються, набагато краще просто вставити на початку цього списку. І це може бути зроблено за постійний час. 

ОК. Наступна операція знайти, що інший - ми формулюванні це як категорії. Але ми будемо дивитися через зв'язаний список протягом деякого об'єкта. Ви, хлопці, бачили код для пошук перш в лекції. Але ми начебто тільки що зробив це з вставити, або принаймні вставки щось відсортовані. Ви переглядаєте, збирається вузла до вузла, поки ви не знайдете номер, що ви шукаю. Що станеться, якщо ви досягнете кінець списку? Скажи я шукаю дев'яти і I дійдете до кінця списку. Що нам робити? 

АУДИТОРІЯ: Повернутися брехня? 

Джейсон Хіршхорна: Повернутися хибним. Ми не знайшли його. Якщо ви дійдете до кінця списку і Ви не знайшли номер, який ви знаходитесь шукаю, це не там. Будь-які питання про знайти? Якби це було відсортований список, що б бути різними для нашого пошуку? Так. 

АУДИТОРІЯ: Було б знайти перше значення от більше того, ви шукаєте і потім повернутися помилковим. 

Джейсон Хіршхорна: Абсолютно вірно. Так що, якщо це відсортований список, якщо ми доберемося до щось, що це більше, ніж те, що ми шукаємо, ми не повинні продовжувати йти в кінець списку. Ми можемо в цій точці повернутися помилковим тому що ми не збираємося, щоб знайти його. Питання тепер, ми говорили про зберігаючи пов'язані списки сортуються, тримати їх без сортування. Це буде те, що ви перебуваєте , Ймовірно, доведеться думати про коли проблема кодування встановити п'ять, якщо ви вибрати хеш-таблицю з окремою ланцюжка підхід, який ми поговоримо трохи пізніше. 

Але чи варто це того, щоб зберегти список відсортований і потім мати можливість, може бути, є швидше результати? Або краще, щоб швидко вставити щось в постійному виконання, але тоді є більше пошуку? Це компроміс тут же, що вам самим вирішувати, що є більш доцільним для вашої конкретної проблеми. І є не обов'язково один абсолютно правильну відповідь. Але це, безумовно, рішення, яке ви отримуєте зробити, і, ймовірно, добре, щоб захистити що, скажімо, коментар або два, чому ви вибрали один над іншим. 

Нарешті, видалення. Ми бачили видалення. Це схоже на пошук. Ми шукаємо елемента. Скажіть, що ми намагаємося видалити шість. Так ми знаходимо шість прямо тут. Справа в тому, що ми повинні переконатися, що ми робити те, що все, що вказує на шість - як ми бачимо в дії два вниз тут - що б не вказуючи на шести потреб в пропустити шість зараз і бути змінений на всі шість вказує на. Ми не хочемо, щоб коли-небудь сиротам решту наш список, забувши встановити, що попередня покажчик. А потім іноді, залежно за програмою, вони просто видалити цей вузол цілком. Іноді ви хочете, щоб повернутися значення, яке знаходиться в цьому вузлі. Так от, як видалення робіт. Будь-які питання по видалити? 

АУДИТОРІЯ: Так що, якщо ви збираєтеся видалити це, ви б просто використовувати безкоштовно, тому що імовірно було malloced? 

Джейсон Хіршхорна: Якщо ви хочете, щоб звільнити те, що цілком правильно, і ви malloced його. Скажімо ми хотіли повернутися це значення. Ми могли б повернутися шість, а потім безкоштовно цей вузол і виклик безкоштовно на нього. Або ми, ймовірно, дзвонити безкоштовно перший , А потім повернутися шість. 

ОК. Так давайте перейдемо до практики кодування. Ми збираємося, щоб закодувати три функції. Перший з них називається insert_node. Так у вас є код, який я послав по електронній пошті вам, і якщо ви дивитеся це пізніше Ви можете отримати доступ до коду в linked.c на сайті CS50. Але в linked.c, є деякі скелет код, який вже була написана для вас. А тут ще пару ФУНКЦІЇ вам потрібно написати. 

Спочатку ми збираємося написати insert_node. А що insert_node робить є вставляє ціле. І ви даєте ціле число в зв'язний список. І зокрема, необхідно зберегти список, відсортований від меншого до більшого. Крім того, ви не хочете, щоб вставити всі дублікати. Нарешті, як ви можете бачити insert_node повертає логічне значення. Таким чином, ви, як передбачається, щоб користувач знав, чи ні вставка була успішним, повертаючи істинним або хибним. Наприкінці цієї програми - і для цієї стадії вам не потрібно турбуватися про звільнення нічого. Так що все, що ви робите це взяття цілої і вставки його в список. 

Це те, що я прошу вас зробити зараз. Знову ж, в linked.c, які ви у всіх є, це код скелет. І ви повинні побачити в нижній Оголошення функції зразка. Проте, перш ніж в його кодування в С, я настійно рекомендую вам піти через ряд кроків, ми були практикуючих щотижня. Ми вже пройшли через картина цього. Таким чином, ви повинні мати певне уявлення , Як це працює. Але я хотів би закликати вас, щоб написати деякі псевдокод, перш ніж поринути дюйма І ми збираємося перейти на псевдокод як група. А потім, як тільки ви написали псевдокод, і як тільки ми написали наш псевдокод як група, ви можете йти в кодування його в С. 

Як один на один, функція insert_node Ймовірно, найскладніша з три ми збираємося написати, тому що я додані деякі додаткові обмеження на Ваш програмування, зокрема, що ви не збираєтеся вставити будь дублікатів та, що список повинні залишатися відсортований. Так що це нетривіальна програма що ви повинні кодувати. І чому б вам не взяти 6:55 хвилин тільки, щоб отримати роботу на псевдокод і код. А потім ми почнемо збирається в якості групи. Знову ж, якщо у вас є які-небудь питання, просто підніміть руку, і я прийду навколо. . 

Ми також в цілому зробити це - або я не явно говорять вам може працювати з людьми. Але очевидно, що я настійно рекомендую Вам, якщо у вас є питання, запитати сусід сидить поруч з вами або навіть працювати з кимось ще, якщо ви хочете. Це не повинно бути індивідуальним мовчання діяльності. 

Давайте почнемо з написання деяких псевдокод на дошці. Хто може дати мені першу лінію псевдокод для цієї програми? Для цієї функції, а - insert_node. Олден? 

АУДИТОРІЯ: Тому перше, що я зробив, було створити новий покажчик на вузол і I ініціалізації він вказуючи на те ж саме річ, яка список вказує на. 

Джейсон Хіршхорна: ОК. Так ви створюєте новий покажчик в список, а не до вузла. 

АУДИТОРІЯ: Вірно. Так. 

Джейсон Хіршхорна: ОК. А потім що ми хочемо зробити? Що після цього? А як щодо вузла? У нас немає вузла. Ми просто мати значення. Якщо ми хочемо, щоб вставити вузол, що ми потрібно зробити, перш ніж ми можемо навіть думати про вставивши його? 

АУДИТОРІЯ: Ой, вибачте. ми повинні Malloc простір для вузла. 

Джейсон Хіршхорна: Відмінно. Давайте зробимо - ОК. Не можете досягти цього максимуму. ОК. Ми збираємося йти вниз, а потім ми використовуємо два стовпці. Я не можу піти, що - ОК. Створіть новий вузол. Ви можете створити ще один покажчик на список або ви можете просто використовувати список, як вона існує. Ви дійсно не потрібно цього робити. 

Так ми створюємо новий вузол. Великий. Це те, що ми робимо в першу чергу. Що далі? 

АУДИТОРІЯ: Зачекайте. Чи повинні ми створити новий вузол зараз або ми повинні чекати, щоб переконатися, що немає ніяких дублікатів вузла в списку, перш ніж ми його створити? 

Джейсон Хіршхорна: Хороше питання. Давайте проведемо це на потім, бо Велику частину часу ми будемо створювати новий вузол. Так ми будемо тримати це тут. Але це хороше запитання. Якщо ми створюємо його, і ми знаходимо дублікат, що повинно ми робимо, перш ніж повернутися? 

АУДИТОРІЯ: Звільніть його. 

Джейсон Хіршхорна: Так. Напевно звільнити його. ОК. Що ми робимо після того як ми створити новий вузол? Енні? 

АУДИТОРІЯ: Ставимо число у вузлі? 

Джейсон Хіршхорна: Абсолютно вірно. Ми, число - ми Malloc простір. Я збираюся залишити це всі як одна рядок. Але ви праві. Ми Malloc пробіл, а потім ми ставимо номер дюйма Ми можемо навіть встановити покажчик частина її до нуля. Ось саме. І то що говорити про після цього? Ми намалював цю картину на дошці. Так що ж нам робити? 

АУДИТОРІЯ: Ми йдемо за списком. 

Джейсон Хіршхорна: Пройтися по списку. ОК. І що ж ми перевіряємо для кожного вузла. Курт, що ж ми перевіряємо для кожного вузла? 

АУДИТОРІЯ: Чи дивитеся н значення що вузол більше, ніж п значенням нашого вузла. 

Джейсон Хіршхорна: ОК. Я збираюся зробити - так, добре. Так що це п - Я збираюся сказати, якщо значення більше ніж цей вузол, то що ж нам робити? 

АУДИТОРІЯ: Ну, тоді ми вставляємо річ прямо перед цим. 

Джейсон Хіршхорна: ОК. Таким чином, якщо це більше, ніж ця, то ми хочемо вставити. Але ми хочемо, щоб вставити його прямо перед тому що ми також повинні були б бути відстеження, то, з того, що було раніше. Так вставити раніше. Таким чином, ми, ймовірно, щось пропустив раніше. Ми, ймовірно, повинні бути зберігаючи трек, що відбувається. Але ми повернемося туди. Так що значення менше? Курт, що ми будемо робити, якщо значення менше? 

АУДИТОРІЯ: Тоді вам просто продовжувати йти якщо це не останній. 

Джейсон Хіршхорна: Мені це подобається. Так що до наступного вузла. Якщо це не останній - ми, ймовірно, перевіряючи, що в термінах стану. Але так, наступний вузол. І це стає занадто низьким, так що ми будемо рухатися тут. Але якщо - може все це бачиш? Якщо ми рівні, що ми робимо? Якщо значення ми намагаємося вставити дорівнює вартості цього вузла? Так? 

АУДИТОРІЯ: [нерозбірливо]. 

Джейсон Хіршхорна: Так. Враховуючи це - Маркус прав. Ми могли б, можливо, зроблено щось інше. Але, враховуючи, що ми створили його, тут ми повинні звільнити, а потім повернутися. Про хлопчик. Так краще? Як це? ОК. Безкоштовний і те що ми повернутися, [нерозбірливо]? ОК. Ми не написали нічого? Так куди ми відстеження попереднього вузла? 

Зали: Я думаю, що це піде після створення нового вузла. 

Джейсон Хіршхорна: ОК. Тому на початку ми, напевно, - так, ми можемо створити покажчик на новий вузол, як попередній покажчик вузла і поточний покажчик вузла. Так що давайте вставити, що тут. Створення поточний і попередній покажчики на вузлах. Але коли ми налаштувати ці покажчики? Де ж нам робити, що в коді? Джефф? 

АУДИТОРІЯ: - умови значення? 

Джейсон Хіршхорна: Які один, зокрема? 

АУДИТОРІЯ: Я просто в замішанні. Якщо значення більше цього вузла, чи не означає це, що ви хочете піти на наступний вузол? 

Джейсон Хіршхорна: Так що, якщо наша значення більше, ніж значення цього вузла. 

АУДИТОРІЯ: Так, то ви хотіли б йти далі по лінії, чи не так? 

Джейсон Хіршхорна: Вірно. Таким чином, ми не вставляйте його тут. Якщо значення менше цього вузла, то ми йдемо до наступного вузла - або тоді ми вставити раніше. 

АУДИТОРІЯ: Зачекайте, що це вузол і що значення? 

Джейсон Хіршхорна: Хороше питання. Значення за цим визначенням функції це те, що нам дають. Так значення є числом нам дають. Таким чином, якщо значення менше, ніж це вузол, нам потрібен час, щоб вставити. Якщо значення більше цього вузла, ми йдемо до наступного вузла. І повернутися до початкового питання, хоча, де - 

АУДИТОРІЯ: Якщо значення більше ніж цього вузла. 

Джейсон Хіршхорна: І так що нам робити тут? Солодкий. Це вірно. Я просто збираюся написати зміна покажчики. Але так, з поточною ви б оновити її до вказують на наступній. Все інше ми пропустили? Так що я збираюся ввести цей код в Gedit. І в той час я роблю це, ви можете мати Ще пара хвилин, щоб працювати з кодування це в С. 

Так що я свій внесок псевдокод. Невелика примітка перш ніж ми почнемо. Ми не можемо бути в змозі повністю закінчити це всього три з цих функцій. Існує правильні шляхи їх вирішення що я буду по електронній пошті до вас, хлопці після розділу, і він буде будуть розміщені на CS50.net. Так що я не закликаю вас піти подивитися на секціях. Я закликаю вас, щоб спробувати їх на ваш володіти, а потім використовувати практику проблеми, щоб перевірити свої відповіді. Всі вони були розроблені, щоб тісно відносяться до і дотримуватися того, що що вам потрібно зробити на безлічі проблем. Так що я закликаю вас до практики це за своїм розсудом, а потім використовувати код для перевірити свої відповіді. Тому що я хочу, щоб рухатися далі, щоб прояснити столи в якийсь момент у розділі. Таким чином, ми не могли б отримати через все це. Але ми зробимо стільки, скільки ми можемо зараз. 

ОК. Почнемо. Асам, як ми створюємо новий вузол? 

АУДИТОРІЯ: Ви структури *. 

Джейсон Хіршхорна: Таким чином, ми є, що тут. Ой, вибачте. Ви говорили структуру *. 

АУДИТОРІЯ: А потім [? вид?] вузол або з вузлом. 

Джейсон Хіршхорна: ОК. Я буду називати його new_node так що ми можемо залишатися послідовним. 

АУДИТОРІЯ: І ви хочете встановити, що очолити, перший вузол. 

Джейсон Хіршхорна: ОК. Так що тепер це, вказує на - так це не створив новий вузол ще. Це просто вказуючи на Перший вузол у списку. Як створити новий вузол? Якщо мені потрібно простір, щоб створити новий вузол. Malloc. І наскільки великий? 

АУДИТОРІЯ: Розмір структури. 

Джейсон Хіршхорна: розмір структури. І що структура називається? 

АУДИТОРІЯ: Вузол? 

Джейсон Хіршхорна: Вузол. Так Танос (SizeOf (вузол)); дає нам простір. І ця лінія - один неправильний на цій лінії. Є new_node покажчик на структуру? Це загальна назва. Що це - вузол, точно. Це вузол *. І що ж нам робити відразу після ми Malloc щось, Асан? Що перше, що ми робимо? Що робити, якщо він не працює? 

АУДИТОРІЯ: О, перевірити, якщо він вказує на вузлі? 

Джейсон Хіршхорна: Абсолютно вірно. Так що якщо ви new_node дорівнює рівних нуль, що ж нам робити? Це повертає логічне значення, цю функцію. Саме так. Виглядає добре. Все, що додати туди? Ми додамо речі в кінці. Але що до цих пір виглядає добре. Створення поточні і попередні покажчики. Майкл, як я можу це зробити? 

АУДИТОРІЯ: Ви повинні були б зробити вузол *. Ви повинні були б зробити один не для new_node але для вузли у нас вже є. 

Джейсон Хіршхорна: ОК. Таким чином, поточний вузол ми на. Я подзвоню, що ин. Добре. Ми вирішили, що ми хочемо зберегти два, тому що ми повинні знати що перед ним. Що вони инициализируются? 

АУДИТОРІЯ: Їх цінність в нашому списку. 

Джейсон Хіршхорна: Так в чому ж Перше, що в нашому списку? Або як ми знаємо, де початок нашому списку є? 

АУДИТОРІЯ: Хіба це не пройшло у функцію? 

Джейсон Хіршхорна: Вірно. Він був прийнятий в прямо тут. Так що, якщо він передається у функцію, початок списку, що ми повинні встановити струм, рівний? 

АУДИТОРІЯ: Список. 

Джейсон Хіршхорна: Список. Ось саме. Тепер він має адресу початок нашого списку. А як щодо попередній? 

АУДИТОРІЯ: Список мінус одна? 

Джейсон Хіршхорна: Там в нічого перед ним. Так що ми можемо зробити, щоб показати, нічого? 

АУДИТОРІЯ: Null. 

Джейсон Хіршхорна: Так. Це звучить як хороша ідея. Прекрасно. Спасибо. Пройтися по списку. Костянтин, як довго ми будемо йти за списком? 

АУДИТОРІЯ: поки ми не досягнемо нульової. 

Джейсон Хіршхорна: ОК. Так що якщо, в той час, протягом циклу. Що ми робимо? 

АУДИТОРІЯ: Може бути, для циклу? 

Джейсон Хіршхорна: Давайте зробимо цикл. ОК. 

АУДИТОРІЯ: І ми говоримо на - до поточного покажчика НЕ дорівнює NULL. 

Джейсон Хіршхорна: Так що, якщо ми знаємо, що стан, як ми можемо написати цикл засновані від цього умови. Які циклі ми повинні використовувати? 

АУДИТОРІЯ: У той час як. 

Джейсон Хіршхорна: Так. Це має більше сенсу, засновану від того, що ви сказали. Якщо ми просто хочемо, щоб увійти в ми це було б просто знаю, що річ, було б сенс робити якийсь час циклу. У той час як струм не дорівнює NULL, якщо значення менше цього вузла. Akshar, дай мені цю лінію. 

АУДИТОРІЯ: Якщо ток-> п н менш вартості. Або зворотна що. Перемикач що кронштейн. 

Джейсон Хіршхорна: Вибачте. 

АУДИТОРІЯ: Змініть кронштейн. 

Джейсон Хіршхорна: Так що, якщо це більше, ніж значення. Тому що це помилка з вище коментар, я збираюся це зробити. Але так. Якщо наша цінність менше, ніж це вузол, що ж нам робити? О. У мене є його прямо тут. Вставте раніше. ОК. Як ми це робимо? 

АУДИТОРІЯ: Це все ще я? 

Джейсон Хіршхорна: Так. 

АУДИТОРІЯ: Ви - new_node-> наступна. 

Джейсон Хіршхорна: Так в чому що збирається рівнятися? 

АУДИТОРІЯ: Це буде рівний струму. 

Джейсон Хіршхорна: Абсолютно вірно. І так з іншого - що ще потрібно для оновлення? 

АУДИТОРІЯ: Переконайтеся, що повз дорівнює нулю. 

Джейсон Хіршхорна: Якщо попередня - так що якщо перед дорівнює нулю. 

АУДИТОРІЯ: Це означає, що він збирається стати главою. 

Джейсон Хіршхорна: Це означає це стати главою. Отже, що ж нам робити? 

АУДИТОРІЯ: Ми робимо голову одно new_node. 

Джейсон Хіршхорна: Керівник дорівнює new_node. І чому очолити тут, не перелічити? 

АУДИТОРІЯ: Тому що голова є світовим змінна, яка є відправною точкою. 

Джейсон Хіршхорна: Солодкий. ОК. І - 

АУДИТОРІЯ: Тоді ви ще перед-> Наступний одно new_node. А потім ви повернетеся правда. 

Джейсон Хіршхорна: Куди ми встановлюємо new_node кінець? 

Зали: Я - Я встановив, що на початку. 

Джейсон Хіршхорна: Так що лінія? 

АУДИТОРІЯ: Після того, як якщо заява перевірки, якщо він відомий. 

Джейсон Хіршхорна: Прямо тут? 

АУДИТОРІЯ: я зроблю new_node-> п дорівнює вартості. 

Джейсон Хіршхорна: Звучить добре. Напевно, має сенс - ми не робимо повинні знати, що список ми на тому що ми маємо справу тільки з одного списку. Так краще оголошення функції для це просто, щоб позбутися цього цілком і просто вставити значення в голову. Ми навіть не повинні знати, що список ми дюйма Але я буду тримати його на даний момент і потім змінити його з модернізації слайди і код. Так що добре виглядає на даний момент. Якщо значення - хто може зробити цю лінію? Якщо - що нам робити тут, Ной. 

АУДИТОРІЯ: Якщо значення більше ніж вал-> п - 

Джейсон Хіршхорна: Як зробити ми йдемо до наступного вузла? 

АУДИТОРІЯ: Керр-> п дорівнює new_node. 

Джейсон Хіршхорна: Так п яка частина структури? Ціле. І new_node є покажчиком на вузол. Так що частина тек ми повинні оновити? Якщо не я, то що інша частина? Ной, що інша частина. 

АУДИТОРІЯ: О, в наступний. 

Джейсон Хіршхорна: Далі, точно. Саме так. Наступна є правильним. А що ще потрібно оновити, Ной? 

АУДИТОРІЯ: Покажчики. 

Джейсон Хіршхорна: Так ми оновили струм. 

АУДИТОРІЯ: Попередня-> наступна. 

Джейсон Хіршхорна: Так. Добре, ми паузу. Хто може допомогти нам тут? Ману, що ми повинні робити? 

АУДИТОРІЯ: Ви повинні встановити його рівним тек-> наступний. Але зробити це раніше, ніж в попередньому рядку. 

Джейсон Хіршхорна: ОК. Що-небудь ще? Akshar. 

АУДИТОРІЯ: Я не думаю, що ти означало змінити Curr-> наступний. Я думаю, ви на увазі, щоб зробити вал рівних вал-> Далі для переходу до наступного вузла. 

Джейсон Хіршхорна: Так жаль, де? На якій лінії? Ця лінія? 

АУДИТОРІЯ: Так. Зробити вал дорівнює вал-> наступна. 

Джейсон Хіршхорна: Так от правильно оскільки в даний час є покажчик до вузла. І ми хочемо, щоб вона вказувала на наступний вузол, що стає в даний час вказав на. Сам Керр має наступний. Але якби ми мали оновити curr.next, ми буде оновлювати фактичні відома сама не там, де це покажчик вказував. А як щодо цієї лінії, хоча. Аві? 

АУДИТОРІЯ: Попередня-> наступна дорівнює ін. 

Джейсон Хіршхорна: Отже, ще раз, якщо перед є покажчик на вузол, перед-> наступний є Фактичний покажчик у вузлі. Так що це буде оновлення покажчик у вузлі до Curr. Ми не хочемо, щоб оновити покажчик на вузол. Ми хочемо, щоб оновити попередній. Так як же нам це зробити? 

АУДИТОРІЯ: Було б просто бути пред. 

Джейсон Хіршхорна: Вірно. Попередня є покажчиком на вузол. Тепер ми міняємо його на Новий покажчик на вузол. ОК Давайте рухатися вниз. Нарешті, остання умова. Джефф, що ми робимо тут? 

АУДИТОРІЯ: Якщо значення дорівнює вал-> п. 

Джейсон Хіршхорна: Вибачте. О боже мій. Що? Значення == вал-> п. Що нам робити? 

АУДИТОРІЯ: Ви б звільнити нашу new_node, і тоді ви б повернутися помилковим. 

Джейсон Хіршхорна: Це те, що ми написали досі. Хто-небудь є нічого додати, перш ніж зробити? ОК. Давайте спробуємо. Контроль може дійти до кінця з не-порожнеча функції. Аві, що відбувається? 

АУДИТОРІЯ: Ви повинні поставити повернення правда за межами час циклу? 

Джейсон Хіршхорна: Я не знаю. Ви хочете, щоб я? 

АУДИТОРІЯ: Не беріть в голову. Ні. 

Джейсон Хіршхорна: Akshar? 

Зали: Я думаю, що ви призначені для покласти повернення помилковим наприкінці з той час циклу. 

Джейсон Хіршхорна: То де Ви хочете, щоб це пішло? 

АУДИТОРІЯ: Як за той час циклу. Так що, якщо ви виходите з той час як цикл Це означає, що що ви дійшли до кінця і нічого не трапилося. 

Джейсон Хіршхорна: ОК. Так що ж нам робити тут? 

АУДИТОРІЯ: Ви повернутися помилковим там же. 

Джейсон Хіршхорна: О, ми зробити це в обох місцях? 

АУДИТОРІЯ: Так. 

Джейсон Хіршхорна: ОК. Якщо ми йдемо? О боже мій. Мені дуже шкода. Я прошу вибачення за екрану. Це свого роду безконтрольного поведінки на нас. Так що вибирайте опцію. Нуль, відповідно до кодом, виходить з програми. Один вставляє щось. Давайте вставити три. Вставка була успішною. Я збираюся роздрукувати. Я не маю нічого. ОК. Може бути, це була просто випадковість. Вставте один. Чи не успішним. ОК. Давайте розглянемо GDB дуже швидко щоб перевірити, що відбувається. 

Запам'ятати GDB. / Ім'я вашого Програма отримує нас в GDB. Багато це чи мало, щоб впоратися? Блимає? Напевно. Закрийте очі і зробіть кілька глибоких дихає, якщо ви втомлюєтеся дивитися на це. Я в GDB. Що перше, що я роблю в GDB? Ми повинні з'ясувати, що відбувається тут. Давайте подивимося. У нас є шість хвилин, щоб зрозуміти , Що відбувається. Перерва основною. А потім що мені робити? Карлос? Запустіть. ОК. Давайте виберемо опцію. І що N робити? Наступна. Так. 

АУДИТОРІЯ: Ви не згадали - ти не сказав, що глава, це було инициализируется нулем на початку. Але я думав, ви сказали, що було в порядку. 

Джейсон Хіршхорна: Поїхали - давайте подивимося в GDB, а потім ми повернемося. Але це звучить як у вас вже є деякі ідеї про те, що відбувається. Тому ми хочемо, щоб вставити щось. ОК. Ми вставити. Будь ласка, введіть Int. Ми вставити три. А потім я на цій лінії. Як я можу йти почати налагодження вставка відомо функцію? О боже мій. Це багато. Хіба що хвилююся багато? 

АУДИТОРІЯ: О, це помер. 

Джейсон Хіршхорна: Я просто витягнув його. ОК. 

АУДИТОРІЯ: Може бути, це Інший кінець дроту. 

Джейсон Хіршхорна: Нічого собі. Так суть - що ти сказав? 

Зали: Я сказав, що іронія технічна Труднощі в цьому класі. 

Джейсон Хіршхорна: Я знаю. Якби тільки я мав контроль над цією частиною. [Нерозбірливості] Це звучить здорово. Чому б вам не почати думати про те, що ми могли б зробити так, і ми повернемося в 90 секунд. 

Avica, я збираюся запитати вас, як йти всередині insert_node налагодити його. Так що це, де ми востаннє зупинилися. Як я можу йти всередині insert_node, Avica, вивчити, що відбувається? Яка команда GDB? Перерва не візьме мене всередині. Чи знає маркіза? 

АУДИТОРІЯ: Що? 

Джейсон Хіршхорна: Яка команда GDB Я використовую, щоб зайти всередину цієї функції? 

АУДИТОРІЯ: Крок? 

Джейсон Хіршхорна: Крок через С. Це бере мене всередині. ОК. New_node mallocing деякий простір. Це все виглядає як його збираються. Давайте розглянемо new_node. Він отримав деяку адресу пам'яті. Давайте перевіримо - це все правильно. Так що все тут, здається, працює правильно. 

АУДИТОРІЯ: У чому різниця між Р і дисплея? 

Джейсон Хіршхорна: Р позначає для друку. І так ви питаєте у чому Різниця між цим і цим? У цьому випадку, нічого. Але в цілому є деякі відмінності. І ви повинні дивитися в керівництві GDB. Але в даному випадку, нічого. Ми схильні використовувати печатку, хоча, тому що нам не потрібно робити набагато більше, ніж роздрукувати одне значення. 

ОК. Таким чином, ми знаходимося на лінії 80 нашого коду, установка вузла * Curr рівну списку. Давайте роздрукувати ін. Вона дорівнює список. Солодкий. Зачекайте. Вона дорівнює щось. Це не здається правильним. Там ми йдемо. Це тому, що в GDB, праворуч, якщо це лінія ти на ньому ще не виконане. Так що вам потрібно насправді тип Наступний виконати лінію перш, ніж бачити його результати. І ось ми. Ми тільки що виконали цю лінію, попередня дорівнює нулю. Отже, ще раз, якщо ми друкуємо попередня ми не побачимо нічого дивного. Але якщо ми насправді виконати, що лінія, то ми побачимо, що ця лінія працювала. 

Тому у нас є ін. Ті, обидва хороші. Чи не так? Зараз ми знаходимося на цій лінії прямо тут. У той час як вал НЕ дорівнює NULL. Ну, що робить вал рівні? Ми тільки що бачили він дорівнював нулю. Ми надрукували його. Я роздрукувати його знову. Так що поки петля буде виконувати? 

АУДИТОРІЯ: Ні. 

Джейсон Хіршхорна: Так що, коли я набрав, що лінія, ви бачите, ми вскочили на всьому шляху вниз до основи, повернутися помилковим. А потім ми збираємося повернутися помилковим і повернутися до нашої програми і зрештою роздрукувати, як ми бачили, вставка була успішною. Так, у когось є якісь ідеї про те, що ми повинні зробити, щоб це виправити? Я збираюся чекати, поки я не бачу пару рук вгору. Ми не виконати це. Майте на увазі, це був перший що ми робили. Я не збираюся зробити пару. Я збираюся зробити декілька. Тому що пару означає два. Я буду чекати більше двох. 

Перший вставка, вал, за замовчуванням дорівнює нулю. І цей цикл виконується тільки якщо вал не є нульовим. Так як я можу обійти це? Я бачу три руки. Я буду чекати більше трьох. Маркус, що ти думаєш? 

АУДИТОРІЯ: Ну, якщо вам це потрібно, щоб виконати більше одного разу, ви просто змінити його на зроби час циклу. 

Джейсон Хіршхорна: ОК. Чи буде це вирішити нашу проблему, хоча? 

НЕ AUDIENCE: У цьому випадку немає через той факт, що список порожній. Так то ви, мабуть, просто потрібно додати заяву, що якщо цикл завершується то ви повинні бути в кінці список, після чого вас можна просто вставити її. 

Джейсон Хіршхорна: Мені це подобається. Це має сенс. Якщо цикл виходить - тому що це буде повернення помилковим тут. Так що, якщо цикл завершується, то ми на кінець списку, або, може бути початок списку, якщо немає нічого в це, яке є таким же, як в кінці. Так що тепер ми хочемо, щоб вставити щось тут. Так як же цей код шукати, Маркус? 

АУДИТОРІЯ: Якщо у вас вже є вузол malloced, ви могли б просто сказати, new_node-> наступна дорівнює нуль, тому що він повинен бути в кінці. Або new_node-> наступна дорівнює нулю. 

Джейсон Хіршхорна: ОК. Вибачте. New_node-> наступна одно нуль , Тому що ми знаходимося в кінці. Це не покласти його дюйма Як ми покласти його у списку? Вірно. Ось тільки поклавши її рівною. Ні, як же ми насправді покласти його у списку? Що вказуючи на кінець списку? 

АУДИТОРІЯ: зав. 

Джейсон Хіршхорна: Вибачте? 

АУДИТОРІЯ: керівник вказує в кінці списку. 

Джейсон Хіршхорна: Якщо немає нічого в список, голова вказуючи на кінець списку. Так що буду працювати на Перший вставки. Що, якщо є кілька речі в списку? Чим ми не хочемо, щоб встановити очолити одно new_node. Що ми хочемо, щоб там робити? Так? Напевно попередній. Чи буде це працювати? Нагадаємо, що попередня просто покажчик на вузол. І попередня є локальної змінної. Так ця лінія буде встановлена ​​локальна змінна, попередній, рівною або вказуючи на цьому новому вузлі. Це не буде насправді поклав його в нашому списку, хоча. Як ми покласти його в нашому списку? Akchar? 

Зали: Я думаю, що ви зробити поточний-> Next. 

Джейсон Хіршхорна: ОК. вал-> наступна. Отже, ще раз, єдина причина, ми вниз ось, що значить струм, рівний? 

АУДИТОРІЯ: Дорівнює нулю. 

Джейсон Хіршхорна: І так, що відбудеться, якщо ми робимо нуль-> далі? Що ми збираємося отримати? Ми отримаємо помилку сегментації. 

АУДИТОРІЯ: Do вал дорівнює нулю. 

Джейсон Хіршхорна: Це те ж саме, як попередня, хоча, тому що є локальна змінна ми встановлюємо рівним цьому новому вузлу. Давайте повернемося до нашої картині вставки щось. Скажіть, що ми, включивши в кінці зі списку, так прямо тут. У нас є поточний покажчик Це вказуючи на нуль і попередній пункт який, вказуючи на 8. Так що ж нам потрібно оновити, Аві? 

АУДИТОРІЯ: Попередній-> далі? 

Джейсон Хіршхорна: Попередній-> наступна є те, що ми хочемо оновити, бо насправді вставити його в кінець списку. У нас ще є одна помилка, проте, що ми збираємося запустити в. Що це помилка? Так? 

АУДИТОРІЯ: Це збирається повернутися брехня в цьому випадку? 

Джейсон Хіршхорна: О, це буде збирається повернутися помилковим. Але є й інша помилка. Тому ми повинні поставити замість істинного. 

АУДИТОРІЯ: Чи є попередня раніше, дорівнює нуль у верхній частині списку? 

Джейсон Хіршхорна: Так попередня ще дорівнює нуль на самому початку. Так як ми можемо подолати це? Так? 

Зали: Я думаю, що ви можете зробити чек до в той час як цикл, щоб переконатися, що це порожній список. 

Джейсон Хіршхорна: ОК. Так що давайте йти сюди. У чек. Якщо - 

АУДИТОРІЯ: Так що, якщо керівник дорівнює дорівнює нулю. 

Джейсон Хіршхорна: Якщо голова дорівнює дорівнює нуль - що нам скаже, якщо це порожній список. 

АУДИТОРІЯ: І тоді ви зробити глава одно нова. 

Джейсон Хіршхорна: Керівник дорівнює new_node? А що ще потрібно зробити? 

АУДИТОРІЯ: А потім ви повернетеся правда. 

Джейсон Хіршхорна: Не зовсім. Ми не вистачає на один крок. 

АУДИТОРІЯ: new_node поруч повинен вказувати на нуль. 

Джейсон Хіршхорна: Точно, Олден. І тоді ми зможемо повернутися вірно. ОК. Але це все ще хороша ідея, щоб робити речі, в кінці списку, чи не так? Добре. Ми як і раніше може насправді отримати в кінці списку. Так це код прекрасно, якщо ми на кінець списку і є деякі речі в списку? Чи не так? Тому що у нас ще є ідея Маркуса. Ми могли б вийти з цього циклу, тому що ми в кінці списку. Так що ми як і раніше хочемо, щоб цей код тут? 

АУДИТОРІЯ: Так. 

Джейсон Хіршхорна: Так. І те, що нам потрібно змінити це? Правда. Це звучить добре всім досі? Хто-небудь є будь-яка - Аві, у вас є, що додати? 

АУДИТОРІЯ: Ні. 

Джейсон Хіршхорна: ОК. Таким чином, ми зробили кілька змін. Ми зробили цю перевірку перш, ніж ми займався порожній список. Таким чином, ми подбали про порожній список. І ось ми подбали про вставці щось в кінці списку. Так що, схоже, як це в той час як петлі взяття догляд за речами між ними, десь в списку, якщо є речі в списку. 

ОК. Давайте запустити цю програму ще раз. Чи не успішним. 

АУДИТОРІЯ: Ви не зробили це. 

Джейсон Хіршхорна: О, Я не робив це. Хороше запитання, Майкл. Давайте додамо марку пов'язані між собою. Лінія 87 є помилка. Лінія 87. Олден, це була лінія ви мені дали. Що не так? 

АУДИТОРІЯ: Вона повинна бути на нуль. 

Джейсон Хіршхорна: Відмінно. Абсолютно вірно. Він повинен бути нульовим. Давайте зробимо знову. Компіляція. ОК. Давайте вставити три. Вставка була успішною. Давайте роздрукувати його. О, якби ми могли перевірити. Але ми ще не зробили роздрукувати функцію ще. Давайте введемо щось ще. Що ми повинні ввести? 

АУДИТОРІЯ: Сім. 

Джейсон Хіршхорна: Сім? 

АУДИТОРІЯ: Так. 

Джейсон Хіршхорна: У нас є несправність сегм. Таким чином, ми отримали один, але ми чітко не може отримати два. Це 5:07. Таким чином, ми могли налагодити цей протягом трьох хвилин. Але я збираюся залишити нас тут і рухатися далі на хеши. Але, знову ж, відповіді на цей код Я буду відправити його до вас у небагато. Ми дуже близькі до нього. Я настійно рекомендую вам, щоб з'ясувати, що відбувається тут і виправити її. Так що я буду вам по електронній пошті цей код, як добре плюс рішення - ймовірно, рішення пізніше. Вперше цей код. 

Інша річ, що я хочу зробити, перш ніж ми обробка ми не звільнили нічого. Так що я хочу показати вам, що Valgrind виглядає. Якщо ми запустимо кордону Valgrind на нашій програмі,. / пов'язані між собою. Знову ж, відповідно з цим слайді, ми повинен працювати Valgrind з деяким типом варіант, в даному випадку - Витік перевірка = повний. Так давайте напишемо Valgrind - Витік перевірка = повний. Так що це буде працювати Valgrind на нашій програмі. А тепер програма насправді працює. Так що ми збираємося запустити його так само, як перш, покласти щось дюйма Я збираюся поставити в трьох. Це працює. Я не збираюся, щоб спробувати покласти в чомусь ще, тому що ми збираємося отримати сегм хибним в цьому випадку. Так що я просто хочу, щоб кинути палити. 

І тепер ви бачите тут витоку і резюме купа. Це хороші речі, які Ви хочете, щоб перевірити. Таким чином, резюме купа - це говорить, у використанні на виході - вісім байт в одному блоці. Це один блок є вузол ми malloced. Майкл, ти вже говорив вузол вісім укуси, оскільки він має ціле і покажчик. Так ось наш вузол. А потім каже, що ми використовували Танос сім разів, і ми звільнили щось в шість разів. Але ми ніколи не називається вільним, так що я не Ідея, що це говорить. 

Але досить сказати, що, коли ваш програма запускається, Танос в даний час називається в деяких інших місцях, які ми не потрібно турбуватися. Так Танос, ймовірно, називається в деяких місцях. Нам не потрібно турбуватися, де. Але це дійсно нам. Це перша лінія це ми. Ми залишили цей блок. І ви бачите, що тут в резюме витоку. Проте дістатися - вісім байт в одному блоці. Це означає, що пам'ять - ми просочилися, що пам'ять. Виразно втратив - щось втрачається назавжди. Як правило, ви не будете бачу нічого там. Проте дістатися, як правило, де ви побачите речі, де ви хочете, дивитися, щоб побачити, який код повинен Ви звільнили, але Ви забули звільнити. 

І потім, якщо це було не так, якби ми зробили безкоштовний все, ми можемо перевірити, що. Давайте просто запустити програму ставлячи ні в що. Ви побачите тут, у використанні на виході - нульові байти в нульових блоків. Це означає, що ми нічого не залишилося коли вийшов ця програма. Так, перш ніж включати в pset6, запустіть Valgrind і переконайтеся, що у вас немає просочується будь-яка пам'ять у вашій програмі. Якщо у вас є будь-які питання з Valgrind, не соромтеся звернутися. Але це, як ви його використовуєте. Дуже просто - подивитися, якщо ви є у використанні на виході - будь байт будь-яких блоків. 

Так ми працювали над вставки вузла. У мене було два інших функцій тут - роздрукувати вузлів і безкоштовні вузли. Знову ж, ці функції, які буде добре для вас на практиці тому що вони допоможуть вам не тільки з ці приклади вправ, а й з проблеми встановити. Вони карту на досить близько до речей ви збираєтеся потрібно зробити в Проблема встановити. Але я хочу, щоб переконатися, ми торкнемося всього. І хеш-таблиці також мають вирішальне значення для що ми робимо в розділі цієї тиждень - або в наборі проблеми. 

Так що ми збираємося закінчити розділ говорити про хеш-таблиці. Якщо ви помітите, що я зробив трохи хеш-таблиці. Тобто не те, що ми говоримо о, однако. Ми говоримо про другий тип хеш-таблиці. І за своєю суттю, хеш-таблицю не що інше, Масив плюс хеш-функція. Ми збираємося говорити на трохи просто переконайтеся, що всі розуміють, що таке хеш-функція є. І я кажу вам зараз, що це не більше, ніж двох речей - масив і хеш-функція. І ось кроки по який цього працює. 

Там в наш масив. Там наша функція. Зокрема, хеш-функції повинні зробити кілька речей з цим. Я збираюся говорити конкретно про ця проблема встановити. Це, ймовірно, буде прийняти в рядку. І те, що він збирається повернутися? Який тип даних? Олден? Ваш хеш-функція повернення? Ціле. Так що це те, що хеш Таблиця складається з - таблиця у вигляді масиву та хеш-функція. Як це працює? Він працює в три етапи. Ми даємо йому ключ. У цьому випадку, ми дамо йому рядок. Ми називаємо хеш-функцію на першому етапі на ключі, і ми отримуємо значення. 

Зокрема, ми будемо говорити ми отримуємо ціле. Це ціле число, є дуже специфічна межі того, що, що ціле може бути. У цьому прикладі, наш масив має розмір три. Так що цифри можуть, що ціле бути. Який діапазон допустимих значень для що ціле, повертається тип це хеш-функція? Нуль, один і два. Справа в хеш-функції є з'ясувати місце в масиві де наш ключ буде. Є тільки три можливих місця тут - нуль, один або два. Так ця функція більш високий дохід нуль, один або два. Деякі діє Indice в цьому масиві. 

А потім залежно від того, де він повертає, Ви можете побачити там безліч відкритий дужки значення. Ось де ми розмістили ключ. Так ми кидаємо в гарбузі, ми виходимо нулю. У масиві кронштейна 0, покладемо гарбуз. Кидаємо в кішок, ми отримуємо одну. Ставимо кішку в одному. Ставимо в павука. Ми виходимо два. Ставимо павука на масив кронштейна два. Це було б так добре, якщо він працював у цьому роді. Але, на жаль, як ми побачимо, це трохи складніше. 

Перш ніж ми перейдемо туди, на будь-які питання про це базова наладка хеш-таблиці? Це зображення точно те, що ми звернули на дошці. Але так як ми звернули його на дошці, я я не збираюся йти в неї далі. По суті ключі, магія чорного ящика - або в даному випадку, чирок коробка - з хеш-функція поміщає їх у відра. І в цьому прикладі ми не поінформувавши ім'я. Ми покласти відповідний телефон число імені у відрі. Але ви могли б дуже добре просто поставити ім'я у відрі. 

Це всього лише картина того, що ми звернули на дошці. У нас є потенційні пастки, однако. І є два зокрема ковзає, що я хочу, щоб перейти. Перший про хеш-функція. Тому я поставив питання, що робить хороша хеш-функція? Я даю дві відповіді. По-перше, це детерміноване. У контексті хеш-функцій, що це означає? Так? 

АУДИТОРІЯ: Він може знайти індекс за постійний час? 

Джейсон Хіршхорна: Це не те, що це означає. Але це хороше припущення. Хто-небудь ще є припущення до того, що це означає? Це гарна хеш-функція детермінована? Енні? 

АУДИТОРІЯ: Це ключовий можна зіставити тільки в одному місці в хеш-таблиці. 

Джейсон Хіршхорна: Це Абсолютно вірно. Кожен раз, коли ви кладете в гарбуза, вона завжди повертає нуль. Якщо ви покладете на гарбуз і вашої хеш Функція повертає нуль, але має ймовірність повернення щось ще більше нуля - тому можливо, це може повернути одне іноді або два інших рази - що це не дуже гарна хеш-функція. Ви абсолютно праві. Ваш хеш-функція повинна повертати точно такий же ціле число, в даному випадку, для точно такий же рядком. 

Може бути, вона повертає ту ж саму точну ціле з тієї ж точною рядка незалежно від капіталізації. Але в такому випадку він як і раніше детермінованою, так як кілька речей відображаються на те ж значення. Це нормально. Поки є тільки один вихід для даного входу. 

ОК. Друге, що те, що це повертає дійсні показники. Ми виховані, що раніше. Це хеш-функція - про хлопчик - хеш-функція повинна повернутися допустимі показники. Так би мовити - давайте повернемося до цього прикладу. Мій хеш-функція підраховує букви в слові. Це хеш-функція. І повертає, що ціле число. Так що, якщо у мене є слово А, це збирається повернутися один. І це буде поставити прямо тут. Що робити, якщо я ставлю в слові битою? Це збирається повернутися три. Де кажан йти? 

Це не підходить. Але для цього потрібно піти куди-небудь. Це мій хеш-таблиці зрештою, і все має піти куди-небудь. Так де повинні кажан йти? Будь-які думки? Вгадуємо? Хороші припущення? 

АУДИТОРІЯ: Нуль. 

Джейсон Хіршхорна: Чому нулю? 

АУДИТОРІЯ: Тому що три модулю три дорівнює нулю? 

Джейсон Хіршхорна: Три модулю три дорівнює нулю. Це велика здогадка, і це правильно. Таким чином, в цьому випадку він повинен ймовірно, піти на нулі. Так що хороший спосіб гарантувати, що цей хеш Функція повертає тільки допустимі показники в до модуля його розмірів таблиці. Якщо ви по модулю Що б це ні прибутку за рахунок три, ви завжди збираєтеся отримати щось середнє між нуль, один і два. І якщо це завжди повертає сім, і ви завжди модулю на три, ви завжди збираєтеся отримати те ж саме. 

Так що це ще детермінованим якщо ви по модулю. Але, що буде гарантувати, що вам ніколи не отримати щось - інвалід промисловості. Як правило, що за модулем має статися всередині хеш-функції. Так що вам не потрібно турбуватися про це. Ви просто можете гарантувати, що це правильний Indice. Є питання по цьому потенційна пастка? 

ОК. І там ми йдемо. Наступна потенційна пастка, і це великий. Що робити, якщо дві клавіші карту в те ж значення? Таким чином, є два способи впоратися з цим. Перший називається лінійним зондування, який я не збираюся перейти на. Але ви повинні бути знайомі з тим, як що працює, а що це таке. 

Другий я збираюся перейти на тому що це той, який багато люди, ймовірно, в кінцевому підсумку вирішити, використовувати у своїй проблемі набору. Звичайно, ви не повинні. Але для безлічі проблем, багатьох людей як правило, вибирають для створення хеш-таблицю з роздільного зв'язування реалізації їх словник. Так що ми збираємося перейти на те, що це означає, створити хеш-таблицю з окремий ланцюжка. 

Так що я поклав на гарбуз. Це повертає нуль. І я поклав гарбуз тут. Тоді я поклав у - що ще один Хеллоуїн-тематичний річ? 

АУДИТОРІЯ: Цукерки. 

Джейсон Хіршхорна: Цукерки! Це відмінне. Я поклав в цукерки, і цукерки також дає мені нулю. Що мені робити? Є ідеї? Тому що все, що ви начебто знаю що окремі ланцюжка є. Так будь-які ідеї, що робити? Так. 

АУДИТОРІЯ: Введення рядок насправді в хеш-таблиці. 

Джейсон Хіршхорна: Таким чином, ми збираємося залучити хорошу ідею тут. ОК. 

АУДИТОРІЯ: Є хеш-таблиці [Нерозбірливості] покажчик, який вказує на початок списку. А потім гарбуз бути перше значення в цьому пов'язаному списку і цукерки бути друге значення в цій пов'язаного списку. 

Джейсон Хіршхорна: ОК. Маркус, який був чудовим. Я збираюся зруйнувати це. Маркус кажу, що не перезаписати гарбуз. Це було б погано. Не ставте цукерки десь в іншому місці. Ми збираємося поставити їх обох на нулі. Але ми збираємося мати справу з покласти їх в нулі створення списку на нулі. І ми збираємося створити список все, що відображається на нуль. І найкращий спосіб ми навчилися створювати список, який може збільшуватися і зменшуватися динамічно чи не знаходиться в межах інший масив. Так не багатовимірний масив. Але просто створити зв'язаний список. 

Так що він запропонував - Я збираюся отримання нової - це створити масив з покажчиками, масив покажчиків. ОК. Будь-яка ідея чи натяк, що тип цього покажчиків має бути? Маркус? 

АУДИТОРІЯ: Покажчики на - 

Джейсон Хіршхорна: Тому що вам сказав зв'язаний список, а значить - 

АУДИТОРІЯ: Node покажчики? 

Джейсон Хіршхорна: Node покажчики. Якщо речі в наш пов'язані Список вузли, то вони повинні бути покажчики вузлів. І що ж вони рівні спочатку? 

АУДИТОРІЯ: Null. 

Джейсон Хіршхорна: Null. Так що наш порожній річчю. Гарбузове повертає нуль. Що нам робити? Прогулянка мене через нього? Насправді, Маркус вже дав мені. Хтось ще погуляти я через нього. Що ми робимо, коли ми - це виглядає дуже схоже на те, що ми просто робили. Аві. 

АУДИТОРІЯ: Я збираюся зробити припущення. Тому, коли ви отримуєте цукерки. 

Джейсон Хіршхорна: Так. Ну, ми отримали гарбуз. Давайте наш перший. Ми отримали гарбуз. 

АУДИТОРІЯ: ОК. Гарбузове повертає нуль. Таким чином, ви покладете його в тому, що. Або насправді, ви поклали його у зв'язаному списку. 

Джейсон Хіршхорна: Як ми покласти його у зв'язаному списку? 

АУДИТОРІЯ: О, фактичний синтаксис? 

Джейсон Хіршхорна: Просто ходити - сказати більше. Що нам робити? 

АУДИТОРІЯ: Ви просто вставити це як перший вузол. 

Джейсон Хіршхорна: ОК. Таким чином, ми маємо нашу вузла, гарбуз. А тепер, як я вводжу його? 

АУДИТОРІЯ: Ви призначаєте це до покажчика. 

Джейсон Хіршхорна: Які покажчик? 

АУДИТОРІЯ: Покажчик на нулі. 

Джейсон Хіршхорна: То де робить це сенс? 

АУДИТОРІЯ: Щоб обнулити прямо зараз. 

Джейсон Хіршхорна: Ну, це вказує на нуль. Але я ставлю на гарбуз. Так де він повинен вказувати? 

АУДИТОРІЯ: Щоб гарбуз. 

Джейсон Хіршхорна: Для гарбуза. Саме так. Так що це вказує на гарбуз. А причому тут цей покажчик в гарбуза точки? До 

АУДИТОРІЯ: Null. 

Джейсон Хіршхорна: Щоб обнулити. Саме так. Так що ми просто вставляється щось у зв'язаному списку. Ми тільки що написав цей код, щоб зробити це. Майже ми майже вийшло повністю тріщини. Тепер ми вставляємо цукерки. Наша цукерки також прагне до нуля. Так що ж нам робити з цукерками? 

АУДИТОРІЯ: Це залежить від того, не ми намагаємося залагодити його. 

Джейсон Хіршхорна: Це Абсолютно вірно. Це залежить від наявності або відсутності ми намагаємося залагодити його. Давайте припустимо, що ми не збирається залагодити його. 

АУДИТОРІЯ: Ну що ж, як ми обговорювали раніше, то простіше просто поставити його на самому початку так покажчик від нуля вказує на цукерки. 

Джейсон Хіршхорна: ОК. Тримайся. Дозвольте мені створити цукерки прямо тут. Так цей покажчик - 

АУДИТОРІЯ: Так, треба зараз бути вказуючи на цукерки. Тоді є вказівник від цукерки вказують на гарбуз. 

Джейсон Хіршхорна: Як що? І сказати, що ми отримали ще один що потрібно зіставити з нуля? 

АУДИТОРІЯ: Ну, ви просто зробити те ж саме? 

Джейсон Хіршхорна: Зробіть те ж саме. Таким чином, в цьому випадку, якщо ми не будемо хочете зберегти це владнав його Звучить досить просто. Візьмемо покажчик в Indice дається нашої хеш-функції. У нас є, що крапка в наш новий вузол. І тоді все, що було вказуючи раніше - у разі нуль, в Другий випадок гарбуза - що, як там воно вказуючи на раніше, ми додаємо в найближчих наш новий вузол. Ми вставки щось на самому початку. Насправді це набагато простіше, ніж намагаючись зберегти список, відсортований. Але, знову ж, пошук буде Чим складніше тут. Ми завжди доведеться йти до кінця. 

ОК. Будь-які питання про роздільного зв'язування? Як це працює? Будь ласка, попросіть їх зараз. Я дуже хочу, щоб переконатися, що ви все зрозуміти це перш, ніж ми качан. 

Зал: А чому ви поставити гарбуз і цукерки в те ж саме частина хеш-таблиці? 

Джейсон Хіршхорна: Хороше питання. Чому ми ставимо їх у те ж саме частина хеш-таблиці? Ну, в цьому випадку наша хеш-функція повертає нуль для них обох. Таким чином, вони повинні піти на нулі Indice тому що там ми збираємося дивитися на них, якщо ми коли-небудь хочу подивитися їх. Знову ж, з лінійною зондування підхід ми б не покласти їх обох в нулі. Але в окремому підході ланцюга, ми збираємося поставити їх обох в нулі а потім створити список з нуля. 

І ми не хочемо, щоб перезаписати гарбуз просто для цього, тому що тоді ми будемо Припустимо, що гарбуз була ніколи не вставляється. Якщо ми просто тримати одну річ в місце, яке було б погано. Тоді не було б шанс з нас коли-небудь - якщо ми колись мали дублікат, то ми просто стерти нашу початкове значення. Так от чому ми робимо цей підхід. Або ось чому ми вибрали - але знову ж, ми вибрав окремий підхід ланцюгових, яких є багато інших підходів можна було вибрати. Я відповів на ваше запитання? 

ОК. Карлос. Лінійний зондування включатиме - Якщо ми знайшли зіткнення в нулі, виглядатиме в наступному місці, щоб побачити, якщо вона була відкрита і поклав його там. А потім ми подивимося в наступному спорту і подивитися, якщо це було відкрито, і поклав його туди. Таким чином, ми знаходимо наступний доступний відкрите місце і поклав його там. Будь-які інші питання? Так, Аві. 

АУДИТОРІЯ: У продовження до цього, що ви маєте на увазі наступне місце? У хеш-таблиці або у зв'язаному списку. 

Джейсон Хіршхорна: Для лінійних програмування, не пов'язані списки. Наступного пляма на хеш-таблиці. 

АУДИТОРІЯ: ОК. Таким чином, хеш-таблиця буде инициализирован розміром - як число рядків що ви були вставки? 

Джейсон Хіршхорна: Ви б хочу, щоб це дійсно великий. Так. Ось картина того, що ми просто звернув на дошці. Знову ж, у нас є зіткнення прямо тут. на 152. І ви побачите, ми створили зв'язаний список з нього. Знову ж, хеш-таблиці окремий ланцюжка підхід не той, який ви повинні прийняти для проблеми встановіть шість, але це той, який багато студенти, як правило, щоб взяти. Так на цій ноті, давайте коротко поговоримо перш, ніж ми качан про проблему шість, а потім я поділюся з вами історією. У нас є три хвилини. 

Архів завдань шість. У вас є чотири функції - навантаження, перевірте, розмір і вивантаження. Навантаження - добре, ми йшли над навантаженням тільки зараз. Ми звернули навантаження на дошці. І ми навіть почали кодування багато вставки у зв'язаному списку. Так навантаження не набагато більше, ніж що ми тільки що робили. 

Перевірити це, як тільки ви щось завантажений. Це той же самий процес, як цей. Ті ж перші дві частини, де ви кидаєте щось в хеш-функції і отримати його значення. Але зараз ми не вставляючи його. Зараз ми шукаємо для нього. Я зразок коду, написаного для знаходження щось у зв'язаному списку. Я закликаю вас, щоб практикувати це. Але інтуїтивно знайти щось буде досить схоже на вставку щось. Справді, ми намалювали картину знаходження щось у зв'язаному списку, рухаючись через, поки не дісталися до кінця. І якщо ви дісталися до кінця так і не змогли знайти його, то це не є. Так от перевірка, по суті. 

Далі йде розмір. Давай пропустимо розмір. Нарешті ви вивантажити. Розвантаження є одним ми не тягне на дошці або закодовані ще. Але я закликаю вас, щоб спробувати його кодування в нашому прикладі, пов'язаного, наприклад списку. Але вивантажити інтуїтивно схожий на замовлення - або я маю на увазі схожий на перевірити. Для тепер кожен раз, коли ви збираєтеся винятком через, ви не просто перевіряти, побачити, якщо у вас є свій значення там. Але ви приймаєте цей вузол і звільняючи його, по суті. Це те, що вивантаження просить вас зробити. Безкоштовний все, що ви malloced. Так що ви збираєтеся через весь список знову, проходячи через весь хеш Таблиця знову. На цей раз не перевіряти щоб подивитися, що там. Просто скачати, що там. 

І, нарешті розмір. Розмір повинен бути реалізований. Якщо ви не реалізуєте розмір - Я скажу це, як це. Якщо ви не реалізуєте розмір в точності одного рядка коду в тому числі повернутися заяву, ви робить розмір неправильно. Тому переконайтеся розмір, для повного дизайну точки, ви робите це в точності один рядок коду, в тому числі оператор повернення. 

І не зібратися ще, Akchar. Прагнучи бобра. Я хотів сказати спасибі вам, хлопці за те, щоб розділі. Майте Happy Halloween. Це мій костюм. Я буду носити це в четвер якщо я бачу вас в робочий час. І якщо вам цікаво, про деякі більш фон, щоб цього костюма, відчуваю можете перевірити 2011 розділ для історії про те, чому я носити гарбуза костюм. І це сумна історія. Тому переконайтеся, що у вас є деякі тканини поблизу. Але на цьому, якщо у вас є які-небудь питання, я буду дотримуватися навколо зовні після розділу. Удачи на проблеми встановити шість. І як завжди, якщо у вас є які-небудь питання, дайте мені знати.