[Powered by Google Translate] [Частина 6] [більш комфортним] [Rob Боуден] [Harvard University] [Це CS50.] [CS50.TV] 

Ми можемо відправитися в нашому розділі питань. Я послав URL для космічних раніше. На початку розділу запитань говорите- мабуть я не зовсім unsick-це дуже просте питання всього того, що Valgrind? Що Valgrind робити? Будь хочу сказати, що Valgrind робить? [Студент] Перевірка витоків пам'яті. Так, Valgrind загальна перевірка пам'яті. Це, врешті-решт, говорить вам, якщо у вас є якісь витоку пам'яті, який в основному те, що ми використовуємо його для, тому що, якщо ви хочете досягти успіху в завданні набору або якщо ви хочете отримати на великій дошці, ви повинні мати витоків пам'яті взагалі, і в разі, якщо є витоку пам'яті, які ви не можете знайти, Також майте на увазі, що всякий раз, коли ви відкриваєте файл і якщо ви не закриєте його, що це витік пам'яті. 

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

Це загальне питання вид запустіть її і подивіться на виході. Вихід переважної багато разів. Там же, де весело помилки, якщо у вас є деякі дуже неправильні речі відбувається в циклі, то вона буде в кінцевому підсумку сказати: "Занадто багато помилок. Я збираюся припинити підрахунок зараз ". Це в основному текстовий вивід, що вам доведеться розібрати. Зрештою, він скаже вам будь витоку пам'яті, які у вас є, скільки блоків, які можуть бути корисні, тому що якщо це один блок unfreed, то вона, як правило, легше знайти ніж 1.000 блоків unfreed. 1000 блоків unfreed, ймовірно, означає, що ви не звільняючи ваша зв'язані списки належним чи щось. Це Valgrind. 

Тепер у нас є розділ питань, які вам не потрібні для завантаження. Ви можете натиснути на моє ім'я, і ​​потягнути їх в просторі. Тепер натисніть на мене. 1-а редакція буде стек, який ми робимо в першу чергу. Перегляд 2 буде черги, і 3-я редакція буде односпрямованого списку. Почавши з нашим стеком. Як сказано тут, стек є одним із самих основних, фундаментальні структури даних, інформатики. Сам прототип прикладу стопку тарілок в їдальні. Це в основному, коли ви вводяться в стек, хтось скаже: "О, як стек лотків". Ви стек лотками. Потім, коли ви йдете витягнути лоток, перший лоток, який стає витягнув є останньою, яка була введена в стеці. Стек також, як він говорить тут- у нас є сегмент пам'яті, званої стеком. І чому це називається стеком? 

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

У нас є масив рядків. У нас є розмір, який представляє, скільки елементів у даний час в стеку, і у нас є потенціал, який, як багато елементів можуть бути в стеці. Ємність повинна початися як щось більше, ніж 1, але розмір буде починатися як 0. Зараз, в основному існують три різні способи ви можете думати про стек. Ну, є, ймовірно, більше, але два основних шляхи Ви можете здійснити це за допомогою масиву, або ви можете реалізувати його за допомогою пов'язаного списку. Пов'язані списки є свого роду тривіальна, щоб стік с. Це дуже легко зробити стек за допомогою пов'язаних списків, так от, ми збираємося зробити стек за допомогою масиву, а потім за допомогою масивів, є також два шляхи ви можете думати про це. Раніше, коли я сказав, у нас є потенціал для стека, так що ми можемо відповідати елементу в стеці. 

Одного боку, це могло статися, як тільки ви натиснете 10 елементів, то ви зробили. Можливо, ви знаєте, що є верхня межа з 10 речей в світі що ви ніколи не будете мати більше, ніж 10 речей, на ваш стек, У цьому випадку ви можете мати верхню межу розміру вашого стека. Або ви могли б ваш стек бути необмеженим, Але якщо ви робите масив, це означає, що кожного разу, коли ви потрапили 10 елементів, тоді ви будете мати, щоб вирости до 20 елементів, і коли ви потрапили 20 елементів, Вам доведеться вирощувати масиву до 30 елементів і 40 елементів. Ви будете потребувати, щоб збільшити пропускну здатність, яка є те, що ми збираємося зробити тут. Кожен раз, коли ми досягаємо максимального розміру нашого стека, коли ми натискаємо на щось інше, ми будемо потребувати, щоб збільшити пропускну здатність. Тут ми поштовх оголошені як BOOL поштовх (символ * вул). Char * вул являє собою рядок, ми добиваємося в стек, і BOOL просто говорить чи ми успіху або невдачі. 

Як ми можемо зазнати невдачі? Що є єдиною обставиною, що ви можете думати про де ми повинні були б повернутися помилковим? Так. [Студент] Якщо це повна і ми використовуємо обмежену реалізацію. Так, оскільки ми визначаємо, він відповів якщо це повна і ми використовуємо обмеженою реалізації. Тоді ми безумовно повернемося помилковим. Як тільки ми потрапили 10 речей, які в масиві, ми не може поміститися 11, так що ми повертаємося помилковим. Що, якщо вона не обмежена? Так. Якщо ви не можете розширити масив з деяких причин. Так, так що пам'ять є обмеженим ресурсом, і врешті-решт, якщо ми продовжуватимемо наполягати речі в стек знову і знову, Ми збираємося спробувати і виділити більший масив, щоб відповідати велику ємність, і Танос або будь-який інший ми використовуємо збирається повернутися помилковим. Ну, Танос поверне NULL. 

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

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

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

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

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

[Rob B.] Також зверніть увагу, що ми використовували хороший оператор побітового тут помножити на 2. Пам'ятайте, що зрушення вліво завжди буде помножити на 2. Зсув вправо ділиться на 2, поки ви пам'ятаєте, що це означає ділимо на 2, як в ціле число ділиться на 2. Це може обрізати на 1 тут або там. Але зрушення вліво на 1 завжди буде необхідно помножити на 2, якщо ви переповнення межі цілого, і тоді вона не буде. Сторони коментаря. Мені подобається робити-це не збирається змінювати кодування будь-якій формі, Але я хотів би зробити щось на зразок цього. Це насправді відбувається, щоб зробити його трохи довше. Може бути, це не ідеальний випадок, щоб показати це, але мені подобається сегменті його в ці блоки- Добре, якщо це, якщо станеться, то я буду щось робити, , А потім функція виконується. Мені не потрібно, щоб потім прокрутити мої очі все, аж функції , Щоб побачити, що відбувається після іншого. Це, якщо це, якщо станеться, то я просто повернутися. Вона також має гарне додаткова перевага все, що за цим В даний час зсувається вліво один раз. Я більше не потрібно, якщо ви завжди поруч смішного довгі черги, Потім ці 4 байти може допомогти, а також лівіше щось є, менше перевантажені ви себе почували, якщо хочете, добре, я повинен пам'ятати, Я в даний час перебуваю в той час як цикл всередині іншого всередині циклу. Скрізь ви можете зробити це повернення негайно, я ніби як. Це зовсім необов'язковим і не очікував ніяк. 

[Студент] Чи повинні бути розміром - в обов'язковому порядку умови? Неодмінно умова тут ми не змогли перерозподілити, так що так. Зверніть увагу, що в обов'язковому порядку умова, мабуть, якщо ми безкоштовно речі пізніше, ми завжди будемо на провал незалежно від того, скільки разів ми намагаємося підштовхнути щось. Якщо ми будемо продовжувати наполягати, ми продовжуємо збільшуючи розмір, навіть якщо ми не ставить нічого в стек. Зазвичай ми не збільшуємо розмір до після того, як ми успішно покласти його в стек. Ми хотіли б це зробити, скажімо, або тут і тут. І тоді замість того щоб сказати s.size ≤ потенціал, це менше, ніж потужність, тільки тому, що ми переїхали, де все було. 

І пам'ятайте, що єдине місце, де ми могли б повернутися помилковим Тут, де перерозподілити повертається нуль, і якщо Ви випадково не пам'ятаєте стандартна помилка, Може бути, ви могли б розглянути цей випадок, коли ви хочете друкувати стандартні помилки, так Fprintf STDERR, а не просто друк безпосередньо на стандартний вивід. Знову ж таки, це не очікування, але якщо це помилка, Введіть Printf, то ви можете зробити це друк на стандартної помилки, а не стандартний вивід. 

Будь-який, є що-небудь ще відзначити? Так. [Студент] Чи можете ви перейти на [нерозбірливо]? [Rob B.] Так, фактично binariness це або просто, що це таке? [Студент] Таким чином, ви помножити на 2? [Rob B.] Так, в основному. У двійковій землі, у нас завжди є наш набір цифр. Перехід цьому ліва на 1 основному вставляє його тут, на правій стороні. Повернутися до цього, просто пам'ятайте, що все в двійковому є ступенем 2, так що це являє 2 до 0, це 2 до 1, це 2 до 2. Додаючи 0 до правої сторони зараз, ми просто перекласти все скінчено. Те, що було 2 до 0, в даний час 2 до 1, 2 до 2. На правій стороні, що ми вставили обов'язково буде 0, який має сенс. Якщо ви коли-небудь помножити число на 2, це не буде в кінцевому підсумку непарних, так що 2 до 0 місце повинне бути 0, і це те, що перше півріччя попередив, перш ніж є, якщо ви все-таки перейти за кількість біт в ціле, то це 1, буде в кінцевому підсумку йти. Це єдине занепокоєння, якщо вам трапиться мати справу з дійсно великими можливостями. Але в цей момент, то ви маєте справу з масивом мільярди речей, яка може не поміститися у пам'яті в будь-якому випадку. 

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

Як стеки і на відміну від масивів, черг зазвичай не допускають доступ до елементів в середині. Тут, стек, ми повинні штовхати і поп-музики. Тут ми, трапляється, називають їх постановки в чергу і видалення з черги. Крім того, я чув, як вони називають зрушенням і Скасувати заміну. Я чув, люди говорять, поштовх і поп застосовуються також до черг. Я чув, вставки, видалення, так штовхати і поп, якщо ви говорите про стеки, ви штовхаєте і плескати. Якщо ви говорите про черги, ви могли б вибрати слова, які ви хочете використовувати для вставки і видалення, і немає єдиної думки про те, що вони повинні бути названі. Але тут, у нас є поставити в чергу і видалення з черги. Тепер, структура виглядає майже ідентично стек структури. Але ми повинні стежити за голову. Я думаю, це говорить тут, але чому ми потребуємо голову? Прототипи в основному ідентичні штовхати і поп-музики. Ви можете думати про це як поштовх і поп-музики. Різниця лише в тому поп повертається, замість останнього, він повертає перший. 2, 1, 3, 4, або щось ще. І ось старт. Наша черга повністю заповнена, так що чотири елементи в ньому. В кінці нашої черги в даний час 2, і тепер ми йдемо, щоб вставити щось інше. 

Коли ми хочемо, щоб вставити щось інше, що ми зробили для стека версія це ми розширили наш блок пам'яті. У чому проблема з цим? [Студент] Ви рухаєтеся 2. Як я вже говорив про кінець черги, це не має сенсу, що ми починаємо з 1, Потім ми хочемо, щоб з черги 1, то з черги 3, то з черги 4, то з черги 2, то з черги цього. Ми не можемо використовувати перерозподілити зараз, або, принаймні, ви повинні використовувати перерозподілити по-іншому. Але ви, мабуть, не слід використовувати тільки перерозподілити. Ви будете повинні вручну скопіювати пам'яті. 

Є дві функції для копіювання пам'яті. Там в memcopy і memmove. Я зараз читаю людина сторінок, щоб побачити, який ви збираєтеся хочете використовувати. Добре, memcopy, різниця що memcopy і memmove, один обробляє випадку правильно де ви копіюєте в регіоні, що відбувається перекриття регіоні Ви копіюванні. Memcopy не впоратися. Memmove робить. Ви можете думати про проблему, як- скажімо, я хочу, щоб скопіювати цей хлопець, ці чотири з цим хлопцем старше. Зрештою, те, що масив повинен виглядати після того, як копія 2, 1, 2, 1, 3, 4, а потім деякі речі в кінці. Але це залежить від порядку, в якому ми насправді копіювати, оскільки якщо ми не вважаємо той факт, що регіон ми копіювання в перекривається один ми копіюванні, Потім ми могли б зробити, як почати тут, копіювання 2 в місце, де ми хочемо піти, потім перемістити наші покажчики вперед. 

Тепер ми збираємося бути тут і тут, і тепер ми хочемо, щоб скопіювати цей хлопець за цим хлопцем, і перемістити наші покажчики вперед. Те, що ми збираємося в кінцевому підсумку отримати в 2, 1, 2, 1, 2, 1 замість того, щоб відповідні 2, 1, 2, 1, 3, 4, тому що 2, 1 подолав оригінальний 3, 4. Memmove обробляє це правильно. У цьому випадку, в основному завжди використовувати memmove тому що він працює правильно. Як правило, він не виконує гірше. Ідея полягає в тому, а не з початку і копіювання таким чином, як ми тільки що зробили тут, вона починається з кінця і копіює в, і в цьому випадку, ви не можете мати проблеми. Там продуктивність не втратив. Завжди використовуйте memmove. Ніколи не турбуйтеся про memcopy. І ось, коли ви будете мати, щоб окремо memmove обгорнутий навколо частини вашої черги. Не турбуйтеся, якщо не повністю зроблено. Це важче, ніж стік, поштовх, і поп-музики. 

Будь-який, є які-небудь коду ми могли б працювати? Навіть якщо повністю неповним? [Студент] Так, це абсолютно неповним, проте. Повністю неповної чудово до тих пір, як ми, ви можете заощадити перегляду? Я забуваю, що кожен раз. Добре, ігноруючи те, що відбувається, коли ми повинні змінити розмір речі. Повністю ігнорувати зміни розміру. Пояснити цей код. Я перевіряю, перш за все, якщо розмір менше, ніж копія, перш за все, і після цього, я вставляю-я беру голову + розмір, і я переконатися, що вона оточує ємність масиву, і я вставити новий рядок в цьому положенні. Тоді я збільшити розмір і повернути істинний. 

[Rob B.] Це, безумовно, один з тих випадків, коли ви захочете використовувати мод. Будь-який випадок, коли ви обтікання, якщо ви думаєте обтікання, безпосередній думка повинна бути мода. Як швидко оптимізації / зробити ваш код один рядок коротший, Ви помітили, що рядки відразу після цього тільки розмір + +, так що ви поєднуєте, що в цю лінію, розмір + +. Тепер тут ми маємо випадок , Де у нас не вистачає пам'яті, так ми збільшуємо нашу здатність на 2. Я думаю, ви могли б мати ті ж проблеми, але ми можемо ігнорувати це зараз, , Де, якщо ви не змогли збільшити потужність, то ви будете хотіти, щоб зменшити ємність на 2 знову. Інший коротку записку так само, як ви можете зробити, + =, Ви також можете зробити << =. Майже все, що може піти до рівних, + =, | =, & =, << =. Char * новий наш новий блок пам'яті. О, тут. 

Що люди думають про тип наш новий блок пам'яті? [Студент] Він повинен бути символ **. Згадуючи нашу структуру тут, рядків те, що ми перерозподілу. Ми робимо абсолютно новий динамічної пам'яті для елементів в черзі. Те, що ми збираємося призначенні на ваші рядки є те, що ми mallocing прямо зараз, і так нова буде символ **. Це буде масив рядків. Тоді в чому ж справа, по якій ми збираємося повернутися помилковим? [Студент] ми повинні робити символів *? [Rob B.] Так, хороший виклик. [Студент] Що це було? [Rob B.] Ми хотіли зробити розмір символів *, тому що ми вже не- це фактично буде дуже велика проблема, тому що SizeOf (Char) буде 1. Sizeof символ * буде 4, так багато разів, коли ви маєте справу з цілими, Ви, як правило, все зійде з рук, тому що розмір Int і розмір Int * на 32-розрядні системи буде те ж саме. Але тут, SizeOf (Char) і SizeOf (Char *) тепер буде те ж саме. 

Що таке обставина, де ми повернутися помилковим? [Студент] Новий дорівнює нулю. Так, якщо новий порожній, ми повертаємося помилковими, і я збираюся кинути тут- [Студент] [нерозбірливо] [Rob B.] Так, це прекрасно. Ви можете або робити 2 рази потужність або ємність зсув 1, а потім тільки встановити його тут або будь-який інший. Ми зробимо це, як у нас було. Ємність >> = 1. І ви ніколи не доведеться турбуватися про втрату 1-Місце тому що ви залишили зрушать на 1, тому 1-Місце обов'язково 0, так прямо зрушення на 1, ви все ще буде добре. [Студент] Вам необхідно зробити це до повернення? [Rob B.] Так, це не має абсолютно ніякого сенсу. 

Тепер припустимо, що ми збираємося в кінцевому підсумку повертається істинним до кінця. Як ми збираємося зробити це memmoves, Ми повинні бути обережні з тим, як ми їх робимо. Хто-небудь є які-небудь пропозиції про те, як ми їх робимо? Ось наш старт. Безумовно, ми хочемо почати з самого початку ще раз і копії речей в Звідти, 1, 3, 4, 2. Як ви це зробили? По-перше, я повинен дивитися на чоловіка сторінки для memmove знову. Memmove, порядок аргументів завжди важливо. Ми хочемо, щоб наше призначення першого, другого джерела, розміру третього. Є багато функцій, які зворотному джерела і призначення. Напрямок, джерело, як правило, відповідає кілька. Move, що це повернення? Вона повертає покажчик до місця призначення, з якої причини ви, можливо, захочете цього. Я можу собі читати, але ми хочемо рухатися в нашому призначення. 

Те, що наш пункт призначення буде? [Студент] New. [Rob B.] Так, і де ми копіюванні? Перше, що ми копіюємо це 1, 3, 4. Що таке-це 1, 3, 4. Що таке адресу цього 1? Що це адреса, що 1? [Студент] [нерозбірливо] [Rob B.] Керівник + адреса першого елемента. Як ми можемо отримати перший елемент у масиві? [Студент] Queue. [Rob B.] Так, q.strings. Пам'ятайте, що тут, наші голови 1. Штопати його. Я просто думаю, що це чарівно- Тут наші голови 1. Я збираюся змінювати свій колір теж. А ось рядки. Це, ми можемо або написати його, як ми зробили тут з главами + q.strings. Багато людей також писати і q.strings [глава]. В дійсності це не будь менш ефективним. Ви можете думати про це, як ви разименованія його, а потім отримати адресу, але компілятор збирається перевести його на те, що ми були представлені в усякому разі, q.strings + голова. У будь-якому випадку ви хочете, щоб думати про це. 

І скільки байт ми хочемо, щоб скопіювати? [Студент] Потужність - голова. Місткість - голова. І тоді ви завжди можете написати приклад щоб з'ясувати, якщо це так. [Студент] Вона повинна бути розділена на 2, то. Так, тому я думаю, ми могли б використовувати розмір. У нас ще є розмір буття- з використанням розміру, у нас є розмір, рівний 4. Наш розмір 4. Наші голови 1. Ми хочемо, щоб скопіювати ці 3 елементи. Це розсудливість перевірити, що розмір - голова правильно 3. І повертатися сюди, як ми вже говорили, якби ми використовували потенціал, то ми повинні були б поділити на 2 тому що ми вже виросли наші можливості, тому замість цього ми збираємося використовувати розмір. Це копій цієї частини. Тепер нам потрібно скопіювати інша частина, частина, що залишилася від самого початку. 

Це збирається memmove в якому становищі? [Студент] Великі розміри - голова. Так, так ми вже скопіювали в розмірі - глава байт, і тому там, де ми хочемо скопіювати залишилися байти нового , А потім розмір мінус, ну, кількість байт, ми вже скопіювали дюйма А потім куди ми копіюванні? [Студент] Q.strings [0]. [Rob B.] Так, q.strings. Ми могли або зробити і q.strings [0]. Це значно рідше, ніж це. Якщо він просто буде 0, то ви будете схильні бачити q.strings. Ось де ми копіюванні. Скільки байт в нас залишилося скопіювати? >> [Студент] 10. Право. [Студент] Чи повинні ми помножимо 5 - 10 разів більше байта або ще що-небудь? Так, так це десь, що саме ми копіювання? [Студент] [нерозбірливо] Який тип річ, яку ми копіювання? [Студент] [нерозбірливо] Так, так що символ * и, що ми копіювання, ми не знаємо, де ті й звідки. Ну, де вони вказують на, як струни, ми в кінцевому підсумку натиснувши на неї в чергу або enqueuing на черзі. Де ті, і звідки, ми поняття не маємо. Нам просто потрібно стежити за символ * з себе. Ми не хочемо, щоб скопіювати розміру - начальник байт. Ми хочемо, щоб скопіювати розміру - начальник символ * с, так що ми збираємося помножити це на SizeOf (Char *). Те ж саме тут, внизу, голова * SizeOf (Char *). 

[Студент] А [нерозбірливо]? Це прямо тут? [Студент] Ні, нижче, розмір - голова. [Rob B.] Це прямо тут? Покажчик арифметика. Як арифметика покажчиків буде працювати це він автоматично збільшується на розмір типу, що ми маємо справу з. Так само, як тут, нова + (розмір - голова) точно відповідає і нова [розмір - начальник] поки ми не очікуємо, що працює правильно, так як якщо ми маємо справу з Int масиву, то ми не робимо індекс INT- або, якщо це розмір з 5, і ви хочете 4-й елемент, то індекс у Int масиву [4]. Ви не-[4] * розмір Int. , Який обробляє його автоматично, і цей випадок Буквально еквівалентні, тому кронштейн синтаксису тільки збирається бути перетворений в цьому, як тільки ви компіляції. Це те, що ви повинні бути обережні, що при додаванні розмірів - голова Ви додаєте не один байт. Ви додаєте один символ *, який може бути одним байт або будь-який інший. 

Інші питання? Так, з черги буде легше. Я дам вам хвилину, щоб реалізувати. Так, і я припускаю, що це та ж сама ситуація, де що епдіеіе випадку, якщо ми enqueuing нульовий, Може бути, ми хочемо впоратися з цим, може бути, ми не знаємо. Ми не будемо робити це знову тут, але так само, як наш стек випадку. Якщо поставити в чергу нульові, ми могли б на нього уваги. Будь-який, є певний код, я можу потягнути? [Студент] Я просто з черги. Версія 2 є те, що, все в порядку. Ви хочете, щоб пояснити? [Студент] По-перше, ви переконаєтеся, що є щось в черзі і що розмір знижується на 1. Ви повинні зробити це, а потім повернути його голову а потім перемістити голову 1. Отже, є куточок випадку ми повинні розглянути. Так. [Студент] Якщо ваша голова знаходиться на останньому елементі, то ви не хочете голову, щоб вказати межі масиву. 

Так, так, як тільки голова стосується кінці нашого масиву, Коли ми з черги, наша голова повинна бути мода на 0. На жаль, ми не можемо зробити це за один крок. Я думаю, так, як я б, ймовірно, виправити це це буде символ *, те, що ми повертаємося, Незалежно від вашого імені змінної хоче бути. Потім ми хочемо мода голови наших можливостей , А потім повернутися у відставці. Багато людей тут, вони могли б зробити- це випадок-ви будете бачити, як люди робити, якщо голова більше місткість, зробити голову - ємність. І це тільки робоча навколо того, що мод. Глава МО = ємність набагато чистіше з обтікання, ніж якщо б голова більше, ніж потужність головою - ємність. 

Питання? Гаразд, остання річ, яку ми залишили наш пов'язаного списку. Ви могли б бути використані для деяких із зв'язаного списку поведінку, якщо ви зробили пов'язаних списків у вашій хеш-таблиці, якщо ви зробили хеш-таблиці. Я настійно рекомендую робити хеш-таблиці. Можливо, ви вже зробили вигляді дерева, але намагається важче. У теорії, вони асимптотично краще. Але подивіться на великій дошці, і намагається ніколи не робити краще, і вони займають більше пам'яті. Все про спробу закінчує тим, що ще гірше для додаткової роботи. Це те, що рішення David Malan завжди є він завжди свої повідомлення Trie рішення, і давайте подивимося, де він в даний час. Що він під землею, David J? Він № 18, так що це не дуже погано, і що це буде один з кращих намагається Ви можете думати або одна з кращих намагається з Trie. Це навіть не його оригінальне рішення? Я відчуваю, як Trie рішення, як правило, більше в цій області використання оперативної пам'яті. 

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

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

Кілька речей, які ми збираємося мати реалізувати. Ваша ЬурейеЕ вузла структури, Int I: Структура вузла * наступний; вузла. Це ЬурейеЕ повинні бути спалені у вашому розумі. Вікторина 1 слід хотіли дати визначення типу пов'язаного списку вузлів, і ви повинні бути в змозі негайно строчити, що вниз навіть не замислюючись про це. Я думаю, пара питань, чому ми повинні побудуємо тут? Чому ми не можемо сказати вузла *? [Студент] [нерозбірливо] Так. Єдине, що визначає вузол, як річ є ЬурейеЕ себе. Але на даний момент, коли ми начебто розбору через це визначення вузла структури, Ми ще не закінчили нашу ЬурейеЕ ще, так що з ЬурейеЕ не закінчена, вузол не існує. Але структура вузла робить, і цей вузол сюди, це також можна назвати щось ще. Це можна назвати с. Це можна було б назвати зв'язаний список вузлів. Його можна назвати що завгодно. Але ця структура вузол повинен бути названо ж саме, що ця структура вузла. Що ви називаєте це має бути тут, і так, що також відповідає на другій точці питання Саме тому-багато разів, коли ви бачите структур і визначення типів із структури, Ви побачите, анонімні структури, де ви побачите тільки ЬурейеЕ структури, реалізація структури, словник, або Що завгодно. 

Чому тут ми повинні сказати вузла? Чому вона не може бути анонімною структури? Це майже той же відповідь. [Студент] Вам потрібно посилатися на нього в межах структури. Так, в межах структури, необхідно звернутися до структури самого. Якщо ви не даєте структури імені, якщо це анонімна структура, ви не можете посилатися на нього. І останнє, але не менш всі вони повинні бути дещо прямолінійно, і вони повинні допомогти вам зрозуміти, якщо ви пишете це вниз що ви робите щось неправильно, якщо такого роду речі не мають сенсу. Останнє, але не менш важливо, чому це повинна бути структура вузла *? Чому це не може бути просто будуємо вузла далі? [Студент] Покажчик на наступну структуру. Це неминуче, що ми хочемо. Чому б це ніколи не буде структура вузла далі? Чому це має бути структура вузла * далі? Так. [Студент] Це як нескінченний цикл. Так. [Студент], що все буде в одному. Так, просто думаю про те, як ми будемо робити розміру або щось. Розмір структури в основному + або - деякі картини тут або там. Це в основному буде сума розміри речей в структурі. Це прямо тут, нічого не змінюючи, розмір буде легко. Розмір структури вузла буде розміром я + розмір наступного. Розмір мені буде 4. Розмір наступний буде 4. Розмір структури вузла буде 8. Якщо ми не будемо мати *, думаючи про SizeOf, Потім SizeOf (I) буде 4. Розмір структури вузла наступний буде розміром я + розмір структури вузла наступного + Розмір я + розмір структури вузла наступного. Було б нескінченною рекурсії вузлів. Ось чому все це так має бути. 

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

Insert_sorted, коли ви реалізуєте insert_sorted- скажімо, у нас є зв'язаний список. Це те, що в даний час він виглядає, 2, 4, 5. Я хочу, щоб вставити 3, так як поки сам список вже відсортований, легко знайти, де 3 належить. Я починаю в 2. Гаразд, 3 більше, ніж 2, тому я хочу, щоб продовжувати йти. Ах, 4 занадто великий, так що я знаю 3 буде йти між 2 і 4, і у мене є, щоб виправити вказівники і все таке. Але якщо ми не будемо використовувати строго insert_sorted, хотілося давайте просто скажемо, я випереджати 6, Потім мій пов'язаного списку стане цим. В даний час вона не має ніякого сенсу, тому для insert_sorted, можна тільки припустити, що список відсортований, хоча існують операції які можуть призвести до не бути відсортовані, ось і все. Знайти корисним вставка-так це ті основні речі, які ви будете мати реалізувати. 

Зараз, знайдіть хвилинку, щоб зробити довжину і містить, і ті повинні бути відносно швидко. Наближається час закриття, так що у кого нічого довжину або містить? Вони збираються, щоб бути майже ідентичними. [Студент] Довжина. Давайте подивимося, перегляд. Добре. Ви хочете, щоб пояснити? [Студент] Я просто створити покажчик вузлів і ініціалізувати його до першого, який є нашою глобальної змінної, а потім перевірити, якщо це нульовий, тому я не отримую сегменті вина і повертати 0, якщо це так. В іншому випадку, я циклі, відстеження протягом цілого Скільки разів я звертався до наступного елементу списку і в тому ж операцію прирощення також доступу до цієї фактичної елемент, і тоді я безперервно зробити перевірку, щоб побачити, якщо це NULL, і якщо він нульовий, то він перериває і просто повертає кількість елементів я доступний. 

[Rob B.] Хто-небудь є які-небудь коментарі на що-небудь? Це виглядає чудово правильність мудро. [Студент] Я не думаю, що вам потрібно вузла == NULL. Так, так що якщо вузол == NULL 0 поверненню. Але якщо вузол == NULL, то це-о-о, є коректності питання. Це було просто ви поверненні я, але це не входить в комплект прямо зараз. Вам просто потрібно Int я, так що я = 0. Але якщо вузол є нульовим, то я як і раніше буде 0, і ми збираємося повертати 0, так що цей випадок є однаковим. Інша поширена річ, щоб зберегти декларацію вузлів всередині циклу. Можна сказати, що-о-о, немає. Давайте тримати це як це. Я б, напевно покласти Int = 0 тут, Потім вузол * = перший вузол тут. І це, напевно, як-позбутися цього зараз. Це, напевно, як би я написав. Крім того, можна-зважаючи на це, як це. Цей цикл структура прямо тут повинна бути майже настільки ж природно для вас, як і для Int я = 0 Я менше, ніж довжина масиву я + +. Якщо це, як ви ітерації по масиву, це, як ви ітерацію по списку. 

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

Швидкий останньої ноти. Якщо Ви бачите статичну ключовими словами, так скажемо статичного кількість Int = 0, Потім ми робимо фото + +, ви можете в основному думають про нього як про глобальної змінної, хоча я тільки що сказав, що це не так, як ми збираємося реалізувати довжини. Я роблю це тут, а потім розраховувати + +. У будь-якому випадку, ми можемо увійти вузла в нашому пов'язаного списку ми збільшуючи наш рахунок. Суть цього є те, що статична ключове слово означає. Якби я тільки що соіпЬ = 0, що буде регулярно старих глобальних змінних. Що статичного Int кількість коштів є те, що глобальна змінна за цей файл. Це неможливо для деяких інших файлів, хотілося думати про PSET 5, якщо ви почали. Ви обоє speller.c, і у вас є dictionary.c, і якщо ви просто оголосити глобальну річ, то нічого в speller.c можна отримати в dictionary.c і навпаки. Глобальні змінні доступні будь-кому. Файл с, але статичні змінні доступні тільки усередині самого файлу, так що всередині перевірку орфографії або всередині dictionary.c, це ніби як би я заявляю про свій змінної для розміру моєї масиву або розмір мого кількість слів у словнику. Так як я не хочу, щоб оголосити глобальну змінну, що хтось має доступ, Я дійсно піклуються тільки про нього для моїх власних цілей. 

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

Питання про щось? Все готово. Поки. [CS50.TV]