[Powered by Google Translate] [Тиждень 6, продовження] [David J. Малан] [Harvard University] [Це CS50.] [CS50.TV] Це CS50 і це в кінці тижня 6. Так CS50x, один з перших курсів Гарвардського університету, що беруть участь в EDX ініціативи Дійсно дебютував в минулий понеділок. Якщо ви хочете отримати уявлення про те, що інших в Інтернеті В даний час наступних разом з, ви можете відправитися на x.cs50.net. Це буде перенаправити вас в потрібне місце на edx.org, який був, де ця та інші програми навчання в MIT і Берклі зараз живемо. Ви повинні зареєструватися для облікового запису, ви знайдете, що матеріал є в значній мірі те ж саме як у вас було в цьому семестрі, хоча і декілька тижнів затримується, оскільки ми отримуємо все готово. Але те, що студенти в CS50x побачите це інтерфейс, зовсім як цей. Це, наприклад, є Zamyla провідних покрокове керівництво для завдання набору 0. При вході в edx.org, CS50x студент бачить різні речі Ви очікували б побачити в курсі: лекція для понеділка, Лекція на середу, різні шорти, проблема набору, покрокові керівництва, PDF-файли. Крім того, як ви тут бачите, переклади машини з англійського стенограми на китайський, японський, іспанський, італійський, і ціла купа інших мов, які, безумовно, буде недосконалим як ми котимося їх програмно, використовуючи так званий API, або інтерфейс прикладного програмування, від Google , Що дозволяє нам перетворити англійської на ці інші мови. Але завдяки чудовому духу деяких сто з гаком добровольців, випадкових людей в інтернеті, які люб'язно запропонували взяти участь У цьому проекті, ми будемо поступово покращуючи якість цих перекладів при наявності людей виправляти помилки, що наші комп'ютери зробили. 

Ось і виходить, що ми ще кільком студентам показати в понеділок, чим ми спочатку очікували. У самому справі, тепер CS50x має 100.000 чоловік слідуючи уздовж будинку. Так розумію, ви всі частини цього першого класу робить цей курс з інформатики освіти в цілому, більш широко, доступно. А реальність така тепер, з деякими з цих масштабної онлайн-курси, всі вони починаються з цих дуже великих кількостях, як ми, здається, зробили тут. Але мета, в кінцевому рахунку, для CS50x дійсно отримати якомога більше людей до фінішу наскільки це можливо. За задумом, CS50x збирається бути запропонована з цього в минулий понеділок на всьому шляху по 15 квітня 2013 року, так що люди, які мають школи зобов'язань в інших місцях, робота, сім'я, інші конфлікти тощо, є трохи більше гнучкості , З якої зануритися в цей курс, який, досить сказати, досить амбіційно зробити, якщо тільки протягом лише трьох місяців протягом звичайного семестру. Але цих студентів буде вирішувати ті ж безлічі проблем, перегляду того ж змісту, мають доступ до тих же шорти тощо. Так розумію, що ми всі дійсно в цьому разом. І одна з кінцевих цілей CS50x не тільки отримати якомога більше людей до фінішу і дати їм цю знову знайдену розуміння інформатики і програмування, але і мати їх у цього поділилися досвідом. Однією з визначальних характеристик з 50 на території кампусу, ми сподіваємося, була така комунальна досвід, на краще чи на гірше, інколи, але мають ці люди звертаються до наліво і направо, і офісних годин і Hackathon і справедливою. Це трохи складніше зробити це в обличчя з людьми в Інтернеті, але CS50x завершиться в квітні з першим CS50 Expo, , Який буде онлайн адаптації наше уявлення про справедливу де ці тисячі студентів все буде запропоновано представити 1 - 2-хвилинне відео, або скрінкасти їх остаточного проекту або відео з них розмахував привіт і говорити про свій проект і demoing це, так само, як ваші попередники зробили тут, на території кампусу в ярмарку, так що до кінця семестру, надія на те, щоб мати глобальні виставки кінцевих проектів CS50x студентів, як і те, що чекає вас в грудні цього року тут, на території кампусу. Так про це в найближчі місяці. 

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

Інформатика курси у Гарварді є трохи традиції, CS50 серед них, що має деякий одяг, одяг, який можна носити з гордістю в кінці семестру, заявивши, що не без гордості, що ви закінчили CS50 і взяв CS50 і тому подібне, і ми завжди намагаємося залучити студентів У цьому процесі якомога більше, причому ми запрошуємо, приблизно в цей час семестру, студенти представити проекти використання Photoshop, або будь-який інший інструмент вибору ви хотіли б використовувати Якщо ви дизайнер, представити проекти для футболки та толстовки і парасольками і мало бандани для собак у нас тепер є і тому подібне. І все це потім - переможці кожного року, потім виставлені на веб-сайті курсу на store.cs50.net. Все продається за вартістю там, але сайт просто працює собі і дозволяє людям вибирати кольори та дизайну, що їм подобається. Таким чином, я думав, що ми просто поділитися деякими з конструкцій останній рік , Які були на сайті, крім цього тут, який є щорічною традицією. "Кожен день я Seg Faultn" була однією з представлених в минулому році, який як і раніше доступні там для випускників. У нас була одна, "CS50, підстави 1989". Один з наших Bowdens, Боб, був дуже популярний в минулому році. "Команда Боуден" народився, цей проект був представлений, серед кращих продавців. Як це було тут. Багато людей були "Боуден Fever" з продажу журналів. Зрозумійте, що тепер може бути ваш дизайн там, на Інтернет. Докладніше про це в наступній проблемою встановлює в майбутньому. 

Ще один інструмент: Ви мали деякий вплив і, сподіваюсь, тепер деякий практичний досвід роботи з GDB, який, звичайно, відладчик і дозволяє маніпулювати Ваша програма на досить низькому рівні, робити якісь речі? Що GDB дозволяють вам робити? Так? Дайте мені що-небудь. [Студент відповідь, нерозбірливо] Добре. Крок у функції, так що ви не просто повинні ввести працювати і є програма удар по всій його повноті, роздрукувавши речі на стандартний вивід. Замість цього, ви можете покроково його рядок за рядком, або ввівши наступну йти рядок за рядком по лінії чи крок, щоб зануритися в функцію, як правило, той, який ви написали. Що ще GDB дозволяють вам робити? Так? [Студент відповідь, нерозбірливо] Друк змінних. Так що якщо ви хочете зробити невеликий самоаналіз усередині вашої програми , Не вдаючись до написання заяви Printf всюди, Ви можете просто роздрукувати змінної або відображати змінної. Що ще можна зробити за допомогою відладчика, як GDB? [Студент відповідь, нерозбірливо] Саме так. Ви можете встановити точки зупину, можна сказати, перерва виконання на основній функції або функції Foo. Можна сказати, перерва виконання з рядка 123. І останову є дуже потужною технікою тому що, якщо у вас є загальне відчуття від того, де ваша проблема Ймовірно, ви не повинні витрачати час покрокового обсязі програми. Ви можете істотно стрибати прямо там і тоді почати друкувати - ступаючи по них з кроком або наступного або тому подібне. Але зловити щось на зразок GDB є те, що він допомагає вам, людині, знайти ваші проблеми і знайти свої помилки. Це не обов'язково знайде їх так багато для вас. 

Таким чином, ми представили інші style50 день, який знаходиться в декількох хвилинах інструмент командного рядка , Який намагається стилізувати код трохи чистіше, ніж ви, людина, можливо, доведеться зробити. Але це теж, насправді просто естетична річ. Але, виявляється, є цей інший інструмент під назвою Valgrind, що є трохи більш таємницею для використання. Його вихід звірячому загадкові на перший погляд. Але це дивно корисні, особливо зараз, коли ми знаходимося в частині терміну де ви починаєте використовувати Танос і динамічного розподілу пам'яті. Все може піти дуже, дуже неправильно швидко. Тому що, якщо ви забули, щоб звільнити пам'ять, або ви разименовать деякі NULL покажчика, або ви разименовать сміття покажчик, що, як правило, ознака того, що результати? Seg вина. І ви отримаєте цей файл ядра деякого числа кілобайтах або мегабайтах , Який представляє стан пам'яті вашої програми, коли він розбився, але ваша програма в кінцевому рахунку сегментам недоліки, помилки сегментації, що означає щось погане сталося майже завжди пов'язані в пов'язаних з пам'яттю помилки, які ви зробили десь. Так Valgrind допоможе вам знайти такі речі. Це інструмент, який ви використовуєте, як GDB, після того як ви зібрали ваші програми, але замість запуску програми безпосередньо, Ви запускаєте Valgrind і ви передаєте йому свою програму, так само, як ви робите з GDB. Тепер, використання, щоб отримати кращий вигляд продукції, це трохи довго, так що тут поверх екрана ви побачите Valgrind-V. "-V" майже повсюдно означає, докладний, коли ви використовуєте програми на Linux комп'ютер. Таким чином, це означає, виплюнути більше даних, ніж ви могли б за умовчанням. »- Витік перевірити = повний". Це просто кажу перевірки для всіх можливих витоків пам'яті, помилки, які я міг би зробити. Це теж є загальної парадигми з Linux програм. Взагалі, якщо у вас є аргументи командного рядка, що це «перемикач», , Який повинен змінити поведінку програми, і це одна буква, це-V, але якщо це включається, просто дизайн програміст, є ціле слово або ряд слів, аргументів командного рядка починається з -. Це всього лише людина конвенцій, але ви побачите їх все більше і більше. І ось, нарешті, "a.out" є довільне ім'я програми в цьому конкретному прикладі. А ось деякі представником продукції. 

Перш ніж ми подивимося на те, що це може означати, дозвольте мені перейти до фрагмент коду тут. І дозвольте мені рухатися цим з шляху, найближчим часом, і давайте поглянемо на memory.c, що цей короткий приклад. Так що в цій програмі, дозвольте мені збільшити на функції і питання. У нас є основна функція, яка викликає функцію, F, і що ж F поступлю, в кілька технічних англійську мову? Що F продовжити робити? Як щодо я почну з лінії 20, і розташування зірок не має значення, але я просто бути послідовним тут з минулого лекції. Що лінії 20 зробити для нас? На лівій стороні. Ми розбити його далі. Int * х: що ж це зробити? Добре. Це оголошення покажчика, а тепер давайте ще більш технічною. Що це значить, дуже конкретно, оголосити покажчик? Хтось ще? Так? [Студент відповідь, нерозбірливо] Надто далеко. Так що ви читаєте в правій частині від знака рівності. Давайте зосередимося тільки на лівому, тільки на Int * х. Це "оголосити" покажчик, а тепер давайте поринемо в більш глибоких цьому визначенню. Що це конкретно, технічно маю на увазі? Так? [Студент відповідь, нерозбірливо] Добре. Він готує для збереження адреси в пам'яті. Добре. І давайте ще один крок, це оголошення змінної х, це 32 біт. І я знаю, що це 32 біт, тому що -? Це не тому, що це ціле число, тому що це покажчик в цьому випадку. Збіг, що це одне і те ж з INT, Але те, що там є зірки означає, що це покажчик і в прилад, як і в багатьох комп'ютерах, але не всі, покажчики є 32-бітними. На більш сучасному устаткуванні, як остання Mac, остання ПК, ви могли б мати 64-розрядні покажчики, але в прилад, ці речі є 32-бітними. Таким чином, ми будемо стандартизації на це. Більш конкретно, історія йде наступним чином: Ми "оголосити" покажчика, що це значить? Ми готуємо для зберігання адрес пам'яті. Що це значить? Ми створюємо змінну звану х, який займає 32 біта що скоро зберегти адресу цілого числа. І це, напевно, приблизно так само точно, як ми можемо отримати. Це нормально рухатися вперед, щоб спростити світ і просто сказати, оголосити покажчик називається х. Оголосіть покажчик, але і зрозуміти, що відбувається насправді навіть як раз в тих кількох символів. 

Тепер, на цей раз майже трохи легше, хоча це більше вираз. Так що ж це робиш, це підкреслив зараз: "Танос (10 * SizeOf (INT));" Так? [Студент відповідь, нерозбірливо] Добре. І я візьму його там. Це виділення блоку пам'яті протягом десяти цілих чисел. А тепер давайте пірнати в трохи глибше, це виділення блоку пам'яті протягом десяти цілих чисел. Що Танос потім повертаються? Адреса цього блоку, або, більш конкретно, адреса першого байта, що шматок. Як же я, програміст, щоб знати, де що частина пам'яті решт? Я знаю, що це безперервно. Malloc, за визначенням, дасть Вам безперервний шматок пам'яті. Ні прогалин у ньому. Ви маєте доступ до кожний байт в тому, що шматок, спина до спини до спини, але як я можу знати, де в кінці цього шматка пам'яті? При використанні Танос? [Студент відповідь, нерозбірливо] Добре. Ви не робите. Ви повинні пам'ятати. Я повинен пам'ятати, що я використовував значення 10, і я навіть не здається, зробили це тут. Але відповідальність лежить повністю на мені. STRLEN, що ми стали трохи залежить від рядками, працює тільки тому, що ця конвенція наявності \ 0 або це спеціальне нульовий символ, NUL, в кінці рядка. Це не виконується для довільного тільки шматки пам'яті. Це залежить від вас. Таким чином, рядок 20, то, виділяє блок пам'яті , Який може зберігати десяти цілих чисел, і він зберігає адресу першого байта цього блоку пам'яті в змінну х. Ergo, який є дороговказом. Таким чином, рядок 21, на жаль, була помилкою. Але перше, що він робить? Це говорить магазину на місці 10, 0 індексуються, з блоку пам'яті називається х значення 0. 

Так помітили кілька речей, які відбуваються. Навіть якщо х є покажчиком, пам'ятаєте з пару тижнів тому що ви все ще можете використовувати масив в стилі квадратних дужок. Тому що насправді короткі руки позначень для більш загадковим вид арифметики покажчиків. , Де ми могли б зробити щось на зразок цього: Візьміть адресу X, перенести на 10 місць, Потім йдуть туди, щоб будь-яку адресу, зберігаються в цьому місці. Але, відверто кажучи, це просто звірячий читати і освоїтися з. Таким чином, світ зазвичай використовуються квадратні дужки тільки тому, що це набагато більш зрозумілі людині читати. Але ось що відбувається насправді під капотом; х адресою, а не масив, як такої. Отже, це зберігання 0 в розташування 10 в х. Чому це погано? Так? [Студент відповідь, нерозбірливо] Саме так. Ми тільки виділив десять цілих чисел, але ми розраховуємо від 0 при програмуванні на C, так що у вас є доступ до 0 1 2 3 4 5 6 7 8 9, а не 10. Так що або програма буде сегменті вина або це не так. Але ми не знаємо, це свого роду недетермінованої поведінки. Це дійсно залежить від того, нам пощастить. Якщо з'ясується, що операційна система не заперечуєте, якщо я використовую це додатковий байт, хоча він не дав його мені, моя програма не може привести до збою. Це сировина, він помилковий, але ви не можете бачити, що симптом, або ви могли б бачити його тільки один раз в той час. Але реальність така, що помилка, насправді, немає. І це дійсно проблематично, якщо ви написали програму, яку ви хочете бути правильною, що ви продали програми, які люди використовують, що кожен раз в той час аварій тому що, звичайно, це не добре. У самому справі, якщо у вас є телефон Android або iPhone і ви можете завантажити програми в ці дні, якщо ви коли-небудь мали додаток просто кинути палити, раптом він зникає, це майже завжди результат деякого пов'язаних з пам'яттю проблеми, причому програміст облажались і разименован покажчик що він або вона не повинна мати, і результат IOS або Android, щоб просто вбити програму в цілому ніж ризикувати невизначений поведінку або якийсь компроміс безпеки. 

Там ще одна помилка в цій програмі, крім цього. Що ще я облажався в цій програмі? Я не практикував те, що я проповідував. Так? [Студент відповідь, нерозбірливо] Добре. Я не звільнив пам'ять. Таким чином, правило тепер повинна бути в будь-який час ви дзвоните Танос, ви повинні зателефонувати безкоштовно, коли ви зробили за допомогою цієї пам'яті. Тепер, коли я хочу, щоб звільнити цю пам'ять? Мабуть, припускаючи, що це перша лінія була правильною, я хотів би зробити це тут. Тому що я не могла б, наприклад, зробити це тут. Чому? Тільки з області видимості. Тому, навіть якщо ми говоримо про покажчиків, це тижні 2 або 3 питання, де х тільки в сферу всередині фігурних дужок, де вона була оголошена. Таким чином, ви напевне не може звільнити його там. Мій єдиний шанс, щоб звільнити це приблизно після рядка 21. Це досить проста програма, це було досить легко, якщо ви вигляд загорнуті вашого розуму навколо того, що програма робить, де помилки були. І навіть якщо ви не бачите його в перший, сподіваюся, це трохи очевидним, що ці помилки досить легко вирішується і легко зробити. Але коли програма складає більше 12 рядків, це 50 рядків, 100 рядків, пішки через код рядок за рядком, думаючи, що через нього логічно, Можливо, але не особливо весело робити, постійно шукає помилки, і це також важко зробити, і тому такий інструмент, як Valgrind існує. Дозвольте мені йти вперед і робити цього: нехай мене відкрити вікно терміналу, і нехай на мене не просто запустити пам'яті, так як пам'ять, здається, добре. Я отримую пощастило. Переходячи до додаткових байтом, що в кінці масиву не здаються надто проблематично. Але дозвольте мені, тим не менш, зробити загальний контроль, який просто означає, що для перевірки Чи так це насправді правильно. 

Так давайте зробимо Valgrind-V - витік перевірити = повний, , А потім назву програми в цьому випадку пам'ять, не a.out. Отже, дозвольте мені йти вперед і робити це. Натисніть Enter. Дорогий Бог. Це її виходу, і це те, що я згадав раніше. Але, якщо ви навчитеся читати через все дурниця тут, більшості це всього лише діагностичний висновок, що це не так цікаво. Що ваші очі дійсно хоче, шукає будь-яку згадку про помилку або недійсним. Слова, які пропонують проблем. І справді, давайте подивимося, що відбувається не так тут. У мене є резюме свого роду, "у використанні на виході: 40. Байт в 1 блоків" Я не зовсім впевнений, що блок поки немає, але 40 байт насправді відчуває, як я міг зрозуміти, де що йде. 40 байт. Чому 40 байт, використовуваних на виході? І більш конкретно, якщо ми прокрутити вниз тут, чому я виразно втратила 40 байт? Так? [Студент відповідь, нерозбірливо] Perfect. Так, саме так. Були десяти цілих чисел, і кожен з них є розмір 4 або 32 біт, так що я втратив саме 40 байт, тому що, як ви запропонували, я не називаються вільними. Це одна помилка, і тепер давайте подивимося трохи далі і бачити поряд з цим, "Недійсні запису розміром 4". А що це таке? Ця адреса виражається те, що база позначення, мабуть? Це шістнадцятковому, і в будь-який час ви бачите номер, що починається з 0x, це означає, шістнадцятковій, який ми зробили зворотний шлях, я думаю, розділ PSET 0 'питання, , Яка була просто робити розминку вправи, перетворюючи десяткової в шістнадцяткову в двійкову і так далі. Шістнадцяткові, просто людські конвенції, як правило, використовуються для представлення покажчиків або, більш загально, адреси. Це просто конвенції, тому що це трохи легше читати, це трохи більш компактний, ніж щось подібне десятковій, і бінарних марні для більшості людей у ​​використанні. Так що тепер це значить? Ну, схоже, є недійсним запису розміром 4 на лінії 21 з memory.c. Так що давайте повернемося до рядку 21, і дійсно, в тому, що недійсні записи. Так Valgrind не збирається повністю тримати мене за руку і скажіть, що виправити це, але виявивши, що я роблю недійсними запису. Я торкаючись 4 байт, що не повинно бути, і, мабуть, це тому, що, як ви зазначили, я роблю [10] замість [9] максимально або [0] або щось між ними. З Valgrind, розуміють будь-який час Ви зараз пишу програму , Яка використовує покажчики і використовує пам'ять, і Танос більш конкретно, Виразно увійти у звичку виконання цього довго але дуже легко скопіювати і вставити команду Valgrind , Щоб побачити, якщо є якісь помилки там. І це буде переважною кожен раз, коли ви бачите вихід, а просто розібрати через візуально всі вихідні і подивитися, якщо ви бачите згадує помилок або попередження або недійсним або втрачені. Будь-які слова, які звучать як ви облажались десь. Так розумію, що це новий інструмент в ваш інструментарій. 

Тепер в понеділок, у нас була ціла купа людей приходять сюди і являють собою поняття, пов'язані списку. І ми ввели зв'язаний список як рішення якої проблеми? Так? [Студент відповідь, нерозбірливо] Добре. Масиви не може мати пам'ять додав до них. Якщо ви виділити масив розміром 10, от і все у вас вийде. Ви можете викликати функцію, як перерозподілити, якщо ви спочатку називався Танос, і що можна спробувати вирощувати масив, якщо є місце до кінця цього що ніхто не використовує, а якщо ні, то він просто буде знайти вас більший шматок в іншому місці. Але тоді він буде копіювати всі ці байти в новому масиві. Це звучить як дуже правильне рішення. Чому це непривабливо? Я маю на увазі це працює, люди вирішили цю проблему. Чому ми повинні вирішити це в понеділок зі зв'язаними списками? Так? [Студент відповідь, нерозбірливо] Це може зайняти тривалий час. У самому справі, в будь-який час ви дзвоните Танос або перерозподілити або calloc, який є ще одна, в будь-який час, програма, говоримо з операційною системою, Ви схильні уповільнювати програму вниз. І якщо ви робите такі речі в петлі, ви дійсно уповільнює роботу. Ви не будете помічати цього для найпростіших "привіт світ" програм типу, але в набагато більших програм, питаючи, операційна система знову і знову для пам'яті або даючи йому знову і знову прагне не бути хорошою річчю. Плюс, це тільки вид інтелектуально - це марна трата часу. Навіщо виділяти більше і більше пам'яті, ризик копіювання все в новий масив, якщо у вас є альтернатива, яка дозволяє виділити лише стільки пам'яті, скільки ви насправді потрібно? Так що є плюси і мінуси тут. Одним з плюсів є те, що тепер у нас є динамізм. Не важливо, де шматки пам'яті, які є вільними, Я можу тільки вид створюють ці хлібні крихти через покажчики в рядок вся моя зв'язаний список разом. Але я плачу принаймні одна ціна. 

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

Що робити, якщо ми хочемо, щоб маніпулювати цим? Ми зробили велику частину цього візуально, і з людьми, Але що, якщо ми хочемо зробити вставки? Таким чином, в первинному списку було 9, 17, 20, 22, 29, 34. Що, якщо ми тоді хотіли Танос простір для номер 55, вузол для нього, і ми хочемо, щоб вставити 55 в списку так само, як ми зробили в понеділок? Як ми це робимо? Ну, Аніта підійшла і вона по суті йшов у списку. Вона почалася з першого елементу, то в наступний, наступний, наступний, наступний, наступний. Нарешті удар лівою всю дорогу вниз і зрозуміли, про, це NULL. Так що покажчик маніпуляції потрібно зробити? Людина, яка була на кінці, № 34, необхідно лівою рукою підняв , Щоб вказати на 55, 55 потребували їх лівою рукою вказує вниз, щоб стати новим NULL термінатор. Готово. Досить легко вставити 55 в відсортованому списку. І як це могло б виглядати? 

Дозвольте мені йти вперед і відкривати код, наприклад, тут. Я буду відкривати Gedit, і дозвольте мені відкрити два файли в першу чергу. Одним з них є list1.h, і дозвольте мені нагадати, що це був шматок коду , Які ми використовували для представлення вузла. Вузол має як Int називається п і покажчик називають тепер, що просто вказує на наступну річ у списку. Тобто в даний час. Файлів годину. Чому? Там в цю угоду, і ми не скористалися цим величезною кількістю самих себе, але чоловік, який написав Printf та інші функції дали в якості подарунка до світу всі ці функції в письмовому вигляді файлу з ім'ям stdio.h. А тут ще string.h, а там Map.h, і є всі ці файли ч що ви, можливо, бачили або використовували протягом строку, написані іншими людьми. Зазвичай в них. Ч файли тільки речі, як ЬурейеЕ або декларації про користувача типів або декларації констант. Ви не ставите реалізації функції "в заголовку файлу. Ви ставите, а не просто їх прототипи. Ви ставите речі, які ви хочете поділитися зі світом, що їм потрібно Для компіляції коду. Так, щоб потрапити в цю звичку, ми вирішили зробити те ж саме. Там не багато в list1.h, але ми вклали те, що може становити інтерес для людей в світі які хочуть використовувати нашу пов'язаного реалізації списку. Тепер, в list1.c, я не буду все це справа тому що це трохи довго, цю програму, але давайте запустимо це реально швидко в командному рядку. Дозвольте мені скомпілювати list1, дозвольте мені запустити list1, і те, що ви бачите, Ми моделювали простенька програма тут що відбувається, щоб дозволити мені додавати і видаляти номери у список. Отже, дозвольте мені піти далі і ввести 3 для 3-меню. Я хочу, щоб вставити номер - давайте зробимо перший номер, який був 9, і тепер я сказала списку тепер 9. Дозвольте мені йти вперед і робити інше вставки, так що я вдарив меню 3. Який номер ви хочете вставити? 17. Enter. І я зроблю ще одну. Дозвольте мені вказати число 22. Отже, ми маємо початок списком, який ми мали у формі слайд хвилину тому. Як ця вставка відбувається насправді? Дійсно, 22 в даний час знаходиться в кінці списку. Так що історія, яку ми розповіли на сцені в понеділок і резюмував зараз повинно бути насправді відбувається в коді. Давайте подивимося. Дозвольте мені пальцем прокрутіть в цьому файлі. Ми будемо замовчувати деякі з функцій, але ми підемо, скажімо, функції вставки. 

Давайте подивимося, як ми йдемо про встановлення нового вузла в цій зв'язаний список. Де список оголошена? Ну, давайте виділіть весь шлях на вершині, і помітив, що мої зв'язаний список, по суті оголошений як одного покажчика, що це споконвічно NULL. Так що я за допомогою глобальної змінної тут, що в цілому ми проповідували проти тому що це робить ваш код трохи брудний підтримувати, це свого роду ледачий, як правило, але це не лінь, і це не так, і це не погано якщо єдиною метою вашої програми в життя, щоб моделювати один зв'язаний список. Які саме те, що ми робимо. Таким чином, замість заявити про це в основному і потім передати його на кожну функцію Ми вже писали в цій програмі, ми розуміємо, замість ой, давайте просто зробити його глобальним тому що вся мета цієї програми полягає в демонстрації одного і тільки одного пов'язаного списку. Так, що почувається добре. Ось мої прототипи, і ми не будемо пройти через все це, Але я написав функцію видалення, знайти функції, функції вставки і функції ходу. Але давайте тепер повернутися вниз до функції вставки і подивитися, як це працює тут. Вставити на лінії - тут ми йдемо. Вставити. Таким чином, він не приймає ніяких аргументів, тому що ми збираємося попросити Користувач всередині цієї функції числа вони хочуть вставити. Але, по-перше, ми готуємося, щоб дати їм простір. Це свого роду копіювання і вставки з інший приклад. У цьому випадку, ми були виділення Int, на цей раз ми виділенні вузла. Я дійсно не пам'ятаю, скільки байт вузол, але це нормально. Sizeof можу зрозуміти, що для мене. І чому я перевірки на NULL у рядку 120? Що може піти не так в лінії 119? Так? [Студент відповідь, нерозбірливо] Добре. Просто може бути так, що я попросив занадто багато пам'яті або щось не так і операційна система не вистачає байтів, щоб дати мені, таким чином, це сигналізує стільки, повертаючи NULL, і якщо я не перевіряють, що і я просто сліпо продовжувати використовувати адресу повернулася, вона може бути NULL. Це може бути невідомою вартістю; не дуже хороша річ, якщо я - насправді не буде невідомого значення. Це може бути NULL, так що я не хочу зловживати цим і ризикувати разименованія його. Якщо це відбудеться, я просто повернутися, і ми будемо робити вигляд, що я не повернуся будь-якому пам'яті взагалі. 

В іншому випадку, я говорю користувач дати мені номер, щоб вставити, я називаю наш старий друг GetInt, і тоді це був новий синтаксис ми ввели в понеділок. "Newptr-> N 'означає взяти адресу, яку ви дали Танос який являє собою перший байт новий об'єкт вузла, а потім перейдіть до області, званої п. Трохи дрібниці питання: Це рівносильно тому, що більш загадковим рядки коду? Як ще я міг би написати це? Хочете прийняти удар? [Студент відповідь, нерозбірливо] Добре. Використовуючи. П., але це не так просто, як це. Що мені в першу чергу необхідно зробити? [Студент відповідь, нерозбірливо] Добре. Мені потрібно зробити * newptr.n. Таким чином, це говорить новий покажчик, очевидно, адреса. Чому? Тому що він був повернутий Танос. * Newptr говорять "туди" і як тільки ви там, то ви можете використовувати більш звичний. п але це тільки виглядає трохи потворно, особливо, якщо ми, люди збираються зробити покажчики зі стрілками весь час в світі є стандартизована на цю стрілку позначення, , Який робить рівно те ж саме. Таким чином, ви тільки використовувати -> позначень коли річ зліва покажчик. В іншому випадку, якщо це фактична структура, використовувати. Н. І тоді це: Чому я ініціалізації newptr-> поряд з NULL? Ми не хочемо, обірваних ліву руку від кінця сцени. Ми хочемо, вказуючи прямо вниз, що означає кінець цього списку потенційно може бути в цьому вузлі, так що ми краще переконатися, що це NULL. І, загалом, ініціалізація змінні або елементи даних і структури щось просто хороша практика. Якщо просто дозволити сміття існують і продовжують існувати як правило отримує вас в біді якщо ви забули щось зробити пізніше. 

Ось кілька випадків. Це, знову ж таки, є функції вставки, і перше, що я можу перевірити, якщо змінна називається першим, що глобальна змінна NULL, це означає, що не існує пов'язаного списку. Ми не вставлені цифри, так це тривіально, щоб вставити цей номер поточної в список, тому що він просто належить на початку списку. Так це було, коли Аніта просто стояв тут один, прикидаючись нікого не було тут, на сцені, поки ми виділили вузла, Потім вона могла підняти руку в перший раз, якщо всі інші прийшли на сцену після неї в понеділок. Тепер ось, це трохи перевірку, де я повинен сказати, що, якщо новий вузла значення п складає <значення п у поточному першого вузла, , Що означає, що є зв'язаний список, який почався. Там, принаймні один вузол у списку, але цей новий хлопець належить до нього, таким чином, ми повинні рухатися речі. Іншими словами, якщо в списку почався з просто, скажімо так, тільки номер 17, це - насправді, ми можемо зробити це більш чітко. Якщо ми почнемо нашу розповідь з покажчиком тут називають першим, і спочатку це NULL, і ми вставляємо номер 9, № 9, безумовно, належить до початку списку. Так давайте уявимо, що ми просто malloced адреса або номер 9 і поклав його тут. Якщо перший 9 за замовчуванням, перший сценарій, який ми обговорювали тільки означає точку давайте цей хлопець тут, залишити це як NULL; тепер у нас є номер 9. Наступний номер ми хочемо вставити становить 17. 17 належить тут, так що ми збираємося зробити деякі логічні степпінг через це. Отже, давайте замість цього, перш ніж зробити це, давайте уявимо, що ми хотіли, щоб вставити номер 8. 

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

Отже, дозвольте мені зробити ще одну річ, і я повинен був залишити трохи більше місця для цього. Так що вибачте маленький малюнок. Цей хлопець називається newptr. Тобто змінна, яку ми оголосили кілька рядків раніше, в лінію - трохи вище 25. І це вказує на 8. Тому коли я кажу newptr-> Далі, це означає, що піти на структуру що буття, на який вказує newptr, тому ми тут, йдіть туди. Тоді стрілки говорять отримати наступне поле, а потім = говорять покласти те, що значення там? Значення, яке було в першому, яке значення було в першу чергу? Перший був спрямований на цьому вузлі, так що означає, що це повинні тепер вказувати на цьому вузлі. Іншими словами, те, що виглядає хоч і смішно возитися з моїм почерком, що проста ідея просто переміщення ці стрілки навколо транслюється в код всього цього лайнера. Зберігайте те, що в перші в наступному полі, а потім обновити те, що спочатку насправді. Давайте йти вперед і перемотування вперед через деякі з цього, і дивитися тільки на цей хвіст вставки на даний момент. Припустимо, що я дістатися до точки, де я знаходжу, що в наступному полі деякого вузла NULL. І в цей момент в історії, докладно, що я замазування є те, що я представив ще один покажчик тут, в лінії 142, попередник покажчик. По суті, в цей момент в історії, коли список стає довгим, Я начебто повинні йти він двома пальцями, тому що якщо я йду занадто далеко, Пам'ятається, в одній довжини списку, ви не можете піти в зворотному напрямку. Так що ця ідея predptr мій палець лівої руки, і newptr - не newptr. Іншим покажчиком, що це ось мій другий палець, і я ніби як ходити по списку. Ось чому, що існує. Але давайте розглядати тільки один з найпростіших випадків тут. Якщо в наступному полі, яке є покажчиком NULL, що логічного слідування? Якщо ви обходу цього списку, і ви потрапили NULL покажчика? Ти в кінці списку, і тому код, щоб потім додати цей один додатковий елемент є свого роду інтуїтивне буде вважати, що вузол якого наступний покажчик NULL, так що це в даний час NULL, і змінити його, хоча, як адресу нового вузла. Так що ми просто малюнок в коді стрілки, що ми звернули на сцену, піднімаючи ліву руку хтось. 

І так, що я махаю руками на даний момент, просто тому що я думаю, що це легко заблукати, коли ми робимо це в таке середовище, перевіряє для вставки в середині списку. Але тільки інтуїтивно, що має відбутися, якщо ви хочете, щоб з'ясувати де деяке число повинне стояти в середині, ви повинні йти він з більш ніж одним пальцем, більше одного покажчика, з'ясувати, де вона належить по перевірці є елемент <поточний, > Поточний, і як тільки ви виявите, що місце, Потім ви повинні робити такого роду оболонки гри, де ви переміщаєте покажчик навколо дуже ретельно. І ця відповідь, якщо ви хочете, щоб через цю причину у себе вдома на свій власний, зводиться тільки до цих двох рядків коду, але порядок цих рядків це супер важливо. Тому що, якщо ви упустите чиюсь руку і підняти чужого не в тому порядку, знову, ви могли б у кінцевому підсумку сиротами списку. Підводячи підсумок більш концептуально, вставки в хвіст відносно проста. Вставки в голову також відносно проста, але вам необхідно оновити додатковий покажчик на цей раз вичавити номером 5 у списку тут, а потім вставка в середині включає в себе ще більше зусиль, дуже обережно вставити число 20 в правильному місці, яка знаходиться між 17 і 22. Так що вам потрібно зробити щось подібне є новий вузол 20 пунктів до 22, , А потім, покажчик, який вузла повинна бути оновлена ​​в останній раз? Це 17, насправді його вставити. Отже, ще раз, я буду відкласти фактичний код для цієї конкретної реалізації. 

На перший погляд, це трохи переважною, але це дійсно просто нескінченний цикл яка цикли, цикли, цикли, цикли і порушення, як тільки ви потрапили в NULL покажчика, в який момент ви можете зробити необхідні вставки. Це, таким чином, є представником пов'язані перелік кодів вставки. Це було досить багато, і він відчуває, як ми вирішили одну проблему, але ми ввели цілий інший. Чесно кажучи, ми витратили весь цей час на великих O і Ω і час роботи, намагаючись вирішити проблеми швидше, і тут ми вживаємо великий крок назад, це відчуває. І все ж, якщо мета для зберігання даних, він відчуває, як Святий Грааль, як ми вже говорили в понеділок, буде дійсно для зберігання речей миттєво. 

У самому справі, припустимо, що ми зробили відкласти в сторону пов'язаного списку на мить а ми замість цього введено поняття таблиці. І давайте просто думати про таблиці на мить у вигляді масиву. Цей масив і цей випадок тут мається близько 26 елементів, від 0 до 25, і припустимо, що вам потрібно деякий шматок для зберігання імен: Аліса і Боб і Чарлі тощо. І вам потрібна структура даних для зберігання цих імен. Ну, ви можете використовувати щось подібне зв'язаний список і ви могли йти списку вставки Аліса перед Бобом і Чарлі після того, як Боб і так далі. І справді, якщо ви хочете, щоб побачити код, як, що, як і в сторону, Відомо, що в list2.h, ми робимо саме це. Ми не будемо йти по цьому коду, але це варіант першого прикладу , Який вводить ще одну структуру ми бачили раніше звана студента, і те що він насправді зберігаються у зв'язаному списку є покажчиком на структуру студента а не просто мало числом, с. Так розумію, що це код там, що включає в себе фактичні рядки, Але якщо мета під рукою дійсно зараз є вирішення проблеми ефективності, Не було б непогано, якщо ми цей об'єкт під назвою Alice, Ми хочемо, щоб помістити її в потрібному місці в структурі даних, він відчуває, як це було б дуже приємно просто поставити Аліса, чиє ім'я починається з, в першому місці. І Боб, чиє ім'я починається з B, у другому місці. З масивом, або давайте почнемо називати його столом, хеш-таблиці в тому, що ми можемо зробити саме це. Якщо дано ім'я, як Аліса, Рядок як Аліса, де поклав ти-л-і-з-е? Ми повинні hueristic. Нам потрібна функція прийняти деякі вхідні як Аліса і повернути відповідь: "Поклади Аліса в цьому місці". І ця функція, це чорний ящик, буде називатися хеш-функції. 

Хеш-функції є те, що займає вхід, як «Аліса», і повертається до вас, як правило, числові місце в деякій структури даних, де Аліса належить. У цьому випадку наша хеш-функція повинна бути відносно простою. Наш хеш-функція повинна сказати, що якщо ви отримуєте «Аліса», характер якого я повинен піклуватися про? Перший. Так що я дивлюся на [0], а потім я кажу, якщо [0] характер, повертається число 0. Якщо це B, повернути 1. Якщо це C, повернути 2, і так далі. Всі 0 індексу, і яка дозволила б мені, щоб вставити Алісою і Бобом, то й тоді Чарлі і т. д. в цю структуру даних. Але є одна проблема. Що робити, якщо Аніта приходить знову? Куди покласти Аніта? Її ім'я теж починається з букви А, і він відчуває, як ми зробили ще більший безлад цієї проблеми. Тепер у нас є негайне введення, постійне час вставки, в структуру даних чим гірше справи лінійні, Але що ми можемо зробити з Анітою в цьому випадку? Які два варіанти, насправді? Так? [Студент відповідь, нерозбірливо] Отже, ми могли б мати інший вимір. Це добре. Таким чином, ми можемо побудувати речі в 3D, як ми говорили про усно в понеділок. Ми могли б додати ще один доступі тут, але припустимо, що ні, я намагаюся тримати це простим. Вся мета тут полягає, щоб мати безпосереднє постійне час доступу, так от додаючи занадто багато складності. Які інші варіанти, коли намагаюся вставити Аніта в цю структуру даних? Так? [Студент відповідь, нерозбірливо] Добре. Таким чином, ми могли рухатися всі інші вниз, як Чарлі поштовхи вниз Боба і Аліси, а потім покласти Аніта, де вона дійсно хоче бути. 

Звичайно, зараз, є побічний ефект цього. Ця структура даних, ймовірно, корисно не тому, що ми хочемо вставити люди раз а тому, що ми хочемо перевірити, якщо вони там пізніше якщо ми хочемо, щоб роздрукувати всі імена в структурі даних. Ми збираємося зробити щось з цими даними в кінці кінців. Отже, тепер ми начебто п'яний за Алісу, яка більше не де вона повинна бути. Не є Боб, ні Чарлі. Тому, можливо, це не така вже хороша ідея. Але насправді, це один варіант. Ми могли зрушити все вниз, або чорт візьми, Аніта прийшла пізно в грі, чому б нам не просто поставити Anita Не тут, не тут, не тут, давайте просто покласти її трохи нижче в списку. Але тоді ця проблема починає переходити знову. Ви можете бути в змозі знайти Алісу миттєво, заснований на її ім'я. І Боб миттєво, і Чарлі. Але тоді ви подивіться на Аніту, і ви побачите, хм, Аліса в путь. Добре, дозвольте мені перевірити нижче Аліса. Боб не Аніта. Чарлі не Аніта. О, є Аніта. І якщо ви будете продовжувати цей поїзд логіці до кінця, Що найгірший час виконання пошуку або вставки Аніта в цю нову структуру даних? Це О (п), правильно? Тому що в гіршому випадку, є Аліса, Боб, Чарлі. . . Все, аж до якоїсь "Y", тому є тільки одне місце залишилося. На щастя, у нас ніхто не називав "Z", тому ми помістили Аніта в самому низу. 

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

Може бути, ми просто пощастить, і ми не збираємося мати два або два Б з дуже високою ймовірністю, але, як хтось вказав, якщо ми узагальнили цю проблему і не робити від 0 до 25 але, скажімо, від 0 до 364 або 65, часто кількість днів у звичайному році, і задав питання: "Що ймовірність того, що два з нас в цьому залі є той же день народження?" Інакше кажучи, те, що ймовірність того, що два з нас є ім'я, що починається з? Таке питання те ж саме, але це адресний простір, це простір пошуку, більше в разі народження, тому що у нас ще дуже багато днів у році, ніж букв в алфавіті. Яка ймовірність зіткнення? Ну, ми можемо думати про це, з'ясовуючи, математика навпаки. Яка ймовірність зіткнення немає? Ну, це вираз тут говорить, що те, що ймовірність якщо є тільки одна людина в цій кімнаті, що у них є унікальна день народження? Це на 100%. Бо якщо є тільки одна людина в кімнаті, його або її народження може бути будь-який з 365 днів у році. Таким чином, 365/365 варіантів дає мені значення 1. Таким чином, ймовірність яких йде мова в даний момент знаходиться всього в 1. Але якщо є друга людина в кімнаті, що ймовірність того, що свій день народження по-іншому? Там тільки 364 можливих днів, без урахування високосних років, на свій день народження, щоб не зіткнутися з іншими особами. Таким чином, 364/365. Якщо третя особа приходить, це 363/365, і так далі. Таким чином, ми розмножуватися разом ці фракції, які стають все менше і менше, з'ясувати, яка ймовірність того, що у всіх нас є унікальна день народження? Але тоді ми можемо, звичайно, просто прийняти цю відповідь і перевернути його навколо і зробити 1 мінус все, що вираз ми в кінці кінців отримаємо якщо ви пам'ятаєте задню частину книги математика, це виглядає трохи щось на зразок цього, який набагато легше інтерпретувати графічно. І це графічне тут має на осі х число народжень, або кількість людей з народження, а по осі Y є ймовірність матчу. І що це говорить, що якщо у вас є, скажімо, навіть, давайте виберемо щось подібне 22, 23. Якщо є 22 або 23 чоловік у кімнаті, Імовірність того, що два з тих дуже небагатьох людей будуть мати той же день народження насправді дуже високо, комбінаторно. 50% шансів, що в класі всього 22 осіб, семінарів, практично, 2 з цих людей будуть мати той же день народження. Тому що є дуже багато способів, якими ви можете мати той же день народження. Ще гірше, якщо ви подивитеся на праву частину діаграми, до того часу, у вас є клас з 58 студентів у ньому, Імовірність 2 людини свій день народження супер, супер висока, майже 100%. Так от, це свого роду забавний факт про реальне життя. 

Але наслідки, тепер, для структур даних і зберігання інформації означає, що тільки якщо у вас є гарне, чисте, рівномірний розподіл даних і у вас є досить великий масив, щоб відповідати купу речей не означає, що ви збираєтеся змусити людей в унікальних місцях. Ви будете мати зіткнень. Таким чином, це поняття перемішування, як це називається, приймаючи вхід, як "Аліса" і масажуючи його в деякому роді , А потім отримати назад відповідь типу 0 або 1 або 2. Повертаючись деяких виході з цієї функції страждають від цієї вірогідності зіткнення. Так як ми можемо обробляти ці зіткнення? Ну, на одному випадку, ми можемо прийняти ідею, що було запропоновано. Ми можемо просто перекласти всі вниз, або, можливо, трохи простіше, , А не рух і всі інші, давайте рухатися Anita на дно вільне місце. Так що, якщо Аліса в 0, Боб знаходиться в 1, Charlie знаходиться в 2, Ми просто покласти Anita на місці 3. І це техніка, в даних структурах, званих лінійних зондування. Лінійна, тому що ви просто ходити цю лінію, і ви роду зондування доступних місць в структурі даних. Звичайно, це перетвориться на O (N). Якщо структура даних дійсно повний, тобто 25 осіб, в ньому вже, , А потім Аніта приходить, вона закінчується на те, що б розташування Z, і це нормально. Вона як і раніше підходить, і ми можемо знайти її пізніше. 

Але це йде врозріз з метою прискорення речі. Так що, якщо ми замість цього ввів це третій вимір? Цей метод зазвичай називають окремі ланцюжки, або з ланцюгами. І те, що хеш-таблицю зараз, це таблична структура, Ваш стіл це просто масив покажчиків. Але те, що ці покажчики вказують на те припущення, що? Зв'язаний список. Так що, якщо взяти найкраще з обох світів? Ми використовуємо масиви вихідних показників в структурі даних, тому ми можемо відразу перейти до [0] [1], [30] і так далі, але так, що у нас є певна гнучкість, і ми можемо підходити Аніта і Еліс і Адам і будь-які інші назви, ми замість цього нехай інші осі рости як завгодно. І ми, нарешті, як в понеділок, є, що виразні можливості з пов'язаного списку. Ми можемо вирощувати структури даних довільно. Крім того, ми могли б просто зробити величезний 2-мірний масив, але це буде жахлива ситуація, якщо один з рядків в 2-мірний масив не є достатньо великим для додаткового людини, чиє ім'я походить почати з A. Не дай Бог ми повинні перерозподілити величезний 2-мірної структури тільки тому, що є дуже багато людей по імені, Особливо, коли є так мало людей на ім'я Z щось. Це просто буде дуже рідкісної структурою даних. Так що це не ідеальний будь-яким способом, але тепер ми принаймні, мати можливість миттєво знайти, де Аліса і Аніта належить, принаймні, з точки зору вертикальної осі, а потім ми просто повинні вирішити, куди помістити Anita або Аліса в країні це зв'язаний список. Якщо ми не будемо дбати про сортування речей, як швидко ми можемо вставити Аліса в структуру, як це? Це постійне час. Ми індексу в [0], і якщо ніхто, Аліса іде на початку, що зв'язаний список. Але це не величезна угода. Тому що якщо Аніта потім приходить разом деяка кількість кроків потому, звідки Аніта належать? Ну, [0]. ООП. Аліса вже в тому, що зв'язаний список. 

Але якщо ми не дбаємо про сортування ці імена, ми можемо просто перемістити Аліса більше, вставки Аніта, але навіть це постійне час. Навіть якщо є Еліс і Адам, і всі ці інші імена, це дійсно не зрушуючи їх фізично. Чому? Тому що ми тільки що зробили тут з зв'язаний список, хто знає, чи були ці вузли так чи інакше? Все, що вам потрібно зробити, це перемістити хлібні крихти. Переміщення стрілки навколо, ви не повинні фізично переміщати будь-які дані навколо. Таким чином, ми можемо вставити Аніта, в такому випадку, негайно. Постійна часу. Отже, ми маємо постійний час пошуку, і постійна часу введення такої людини, як Аніта. Але вид спрощеного світу. Що робити, якщо пізніше ми хочемо знайти Алісу? Що робити, якщо пізніше ми хочемо знайти Алісу? Скільки кроків є те, що збираєтесь робити? [Студент відповідь, нерозбірливо] Саме так. Число людей, перш ніж Аліса в зв'язаному списку. Так що це не зовсім досконалий, тому що наші структури даних, знову ж таки, це має вертикальну доступу І тоді він ці зв'язані списки висять - насправді, давайте не будемо малювати масиву. Він ці зв'язані списки, що висять від цього, що виглядає трохи щось на зразок цього. Але проблема в тому, якщо Аліса і Адам, і всі ці інші імена в кінцевому підсумку все більше і більше там, знайти когось, може в кінцевому підсумку приймає купу кроків, bcause Ви повинні пройти пов'язаного списку, , Яка є лінійною операцією. Так насправді, то, в кінцевому рахунку, час вставки є O (N), де N число елементів у списку. Розділені, давайте умовно називаємо її, де т число пов'язаних списків що ми маємо в цій вертикальній осі. Іншими словами, якщо ми дійсно вважати рівномірним розподілом імен, абсолютно нереально. Там, очевидно ще деяких букв, ніж інші. 

Але якщо ми припустимо, на даний момент рівномірний розподіл, і ми п повних людей, і м загальної ланцюга наявні у нас, то довжина кожної з цих ланцюгів достатньо просто буде загальний, п ділиться на кількість ланцюгів. Таким чином, п / т. Але от де ми можемо бути математично всі розумні. м є постійним, тому що там фіксоване число з них. Ви збираєтеся оголосити масив на початку, і ми не зміна розміру вертикальної осі. За визначенням, яка залишається фіксованою. Це тільки по горизонтальній осі, так би мовити, все змінюється. Таким чином, технічно, це константа. Так що тепер, час вставки в значній мірі O (N). Так що не відчуває себе все, що набагато краще. Але те, що тут правда? Ну, все це час, протягом тижнів, ми говорили O (N ²). О (п), 2 х п ², - я, діленої на 2. . . Чеха. Це просто п ². Але зараз, в цій частині семестру, ми можемо почати говорити про реальний світ знову. А п / т абсолютно швидше, ніж просто п поодинці. Якщо у вас є тисячі імен, і ви розбити їх на кілька ковшів так що у вас тільки десять імен у кожній із цих ланцюгів, Абсолютно пошуку Десять речей, це буде швидше, ніж тисяча речей. І ось одна з безлічі майбутніх проблема буде вам виклик думати саме про те, що, хоча, так, асимптотично і математично, це ще тільки лінійні, яка всмоктує в цілому, намагаючись знайти речі. Насправді, це буде швидше, ніж через це дільника. І там знову буде цей компроміс і цей конфлікт між теорією і реальністю, і одним з регуляторів почне обертатися в цей момент в семестр Більш реальності один, як ми ніби як готуватися до кінця semster, в як ми введемо в світі веб-програмування, де дійсно, продуктивність буде розраховувати, тому що ваші користувачі будуть починають відчувати і цінувати бідних дизайнерських рішень. 

Отже, як ви йти про реалізацію пов'язаних - хеш-таблицю з 31 елементами? А попередній приклад був довільним про дні народження. Якщо у когось є день народження 1 січня або 1 лютого, ми помістимо їх в цьому відрі. Якщо це 2 січня, 2 лютого, 2 березня, ми помістимо їх в цьому відрі. Ось чому він був 31 рік. Як ви оголосите хеш-таблиці? Це може бути досить простим, вузол таблиці * моє довільне ім'я для нього, [31]. Це дає мені 31 покажчиків на вузли, і який дозволяє мені є 31 покажчиків на пов'язані списки навіть якщо ці мережі споконвічно NULL. Що я хочу поставити, якщо я хочу зберегти "Аліса", "Боб", "Чарлі"? Ну, нам потрібно, щоб обернути ці речі в структурі бо нам потрібна Аліса, щоб вказати на Боба, щоб вона вказувала на Чарлі, і так далі. Ми не можемо просто мають імена в поодинці, тому я міг би створити нову структуру під назвою вузла тут. 

Що таке фактичне вузла? Що таке вузол у цій новій зв'язаний список? В першу чергу, називається словом, для імені людини. ДОВЖИНА, мабуть, відноситься до максимальної довжині імені людини, в що б це, 20, 30, 40 символів в божевільний випадках кут, і +1 для чого? Це просто додатковий символ NULL, \ 0. Таким чином, цей вузол упаковка "щось" усередині себе, але він також оголошує покажчик називається наступна так що ми можемо ланцюга Аліси до Боба Чарлі і так далі. Може бути NULL, але не обов'язково повинні бути. Будь-які питання по цим хеш-таблиці? Так? [Студент задаючи питання, нерозбірливо] масиву - хороше питання. Чому це символ слова в масиві, а не просто символ *? У цьому кілька довільно, наприклад, я не хочу, щоб вдаватися в Танос для кожного з оригінальної назви. Я хотів би оголосити максимальний обсяг пам'яті для рядка так що я міг скопіювати в структуру Alice \ 0, а не мати справу з Танос і безкоштовні тощо. Але я можу зробити, якщо я хотів бути більш свідомими використання простору. Хороше питання. Отже, давайте спробуємо узагальнити від цієї і зосередитися залишок сьогодні на структури даних в цілому та інші проблеми, які можна вирішити з використанням тих же засадах навіть якщо дані структури самі можуть відрізнятися в деталях. 

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

Що таке шаблон в тому, як ми заклали на це або як Патрік поставив його у своєму відео? Це свого роду очевидно, що є деякі сортування відбувається тут, але те, що це просте правило? Так? [Студент відповідь, нерозбірливо] Perfect. Якщо поглянути на це, ви побачите невелике число зліва, великі цифри на лівій, але це вірно для кожного вузла. Для кожного вузла, його ліва дитини менше, ніж він, і його право дитини більше, ніж він. Що це означає тепер, якщо я хочу знайти цю структуру даних, скажімо, числа 44, Я повинен почати з кореня, так як у всіх цих більш складних структур даних зараз, у нас є тільки покажчик на одному, самому початку. І в цьому випадку, початок кореня. Це не лівому краю, це корінь цієї структури. Так що я бачу ось 55, і я шукаю 44. В якому напрямку ви хочете поїхати? Ну, я хочу піти наліво, тому що, очевидно, справа буде занадто великим. Таким чином, помітити тут, ти ніби концептуально рубки дерев в два рази тому що ви ніколи не спускаючись у праву сторону. Так що тепер я йду від 55 до 33. Це занадто мале число. Я шукаю 44 років, але тепер я знаю, якщо 44, в цьому дереві, я можу піти, очевидно, з правого боку. Отже, ще раз, я обрізку дерев у два рази. Це в значній мірі ідентичні концептуально в телефонну книгу. Це ідентично тому, що ми зробили з паперу на дошку, але це більш складна структура, яка дозволяє нам насправді це розділяй і володарюй дизайн алгоритму, і справді, проходячи структури, як це - вигуки. Обхід структури, як це, де це тільки "йти по цьому шляху або йти по цьому шляху", означає, що все, що код, який нахилився ваш розум в першу чергу при його здійсненні у розділі або пішки через неї вдома, для бінарного пошуку, за допомогою рекурсії або ітерації, це біль в шиї. Знайти середнього елемента, то зробити вашу округлення вгору або вниз. 

Там в красі цього, тому що тепер ми можемо використовувати рекурсію знову, але набагато більш акуратно. У самому справі, якщо ви на число 55, і ви хочете, щоб знайти 44, Ви йдіть наліво в цьому випадку, те, що ви робите? Ви запускаєте той же алгоритм. Ви перевіряєте значення вузла, то ви йдете вліво або вправо. Потім ви перевіряєте значення вузла, перейдіть ліворуч чи праворуч. Це ідеально підходить для рекурсії. Так що, хоча в минулому ми зробили деякі досить довільні приклади з участю рекурсії , Які не повинні бути рекурсивними, з даними СТРУКТУР, Особливо дерева, це ідеальне застосування цієї ідеї з проблемою, скорочення її, а потім рішення того ж типу, але меншого, програми. 

Так що є інша структура даних, ми можемо ввести. Це одна призначена на перший погляд виглядають загадково, але це дивно. Так що це структури даних, називаної вигляді дерева, Trie, який успадковується від слова пошуку, які не вимовляються знову спробувати-вал, але це те, що світ називає ці речі. Намагається. Т-т-і-і. Він являє собою деревоподібну структуру якийсь, але кожен з вузлів у вигляді дерева здається, що? І це трохи вводить в оману, тому що це свого роду скороченим. Але, схоже, кожен вузол в цьому Trie насправді є масивом. І хоча автор цієї схемі не показано це, В даному випадку, це Trie це структура даних, мета якого в житті, щоб зберігати слова як-л-і-з-е-або В-О-В. І те, яким чином ця Аліса сховищ даних і Боб і Чарлі і Аніта і т. д. воно використовує масив для зберігання яких Аліса в вигляді дерева, ми починаємо з кореневого вузла, який виглядає як масив, і це було написано в скороченій формі. Автор опущені ABCDEFG, тому що не було ніяких імен з цим. Вони тільки показали М і Р і Т, але в даному випадку, давайте перейдемо від Аліса і Боб і Чарлі деякі імена, які знаходяться тут. Максвелл насправді в цій схемі. Так як же автор магазині M - х-ш-е-л-л? Він або вона почалася в кореневий вузол, і пішов [M], таким чином, приблизно 13, 13 місце в масиві. Потім звідти, є покажчик. Покажчиків, що ведуть до іншої масив. Звідти автор індексуватися в цей масив на місці, як показано там в лівому верхньому кутку, і тоді він або вона випливає, що покажчик на інший масив, і пішов до покажчика на місце X. Тоді в наступний масив розташування W, E, L, L, і так далі, І, нарешті, давайте насправді намагаються поставити картину до цього. Що робить вузол виглядає в коді? Вузлі у вигляді дерева містить масив покажчиків на кількох вузлах. Але є і повинен бути свого роду логічне значення, принаймні, в цій реалізації. Я, трапляється, називають його is_word. Чому? Тому що, коли ви вставки Максвел, ви не вставляючи нічого в цій структурі даних. Ви не пишете M. ви не пишете X. Все, що ви робите, наступні покажчики. Покажчик, що представляє М, то покажчик, який представляє, Потім покажчик, який представляє X, то W, E, L, L, але те, що вам потрібно зробити, врешті начебто піти, перевірити, я добрався до цього місця. Існував слово, яке закінчується в структурі даних. 

Так що Trie дійсно наповнений і автор вибрав в якості представника ці terminuses з невеликими трикутниками. Це просто означає, що факт цей трикутник тут, це логічне значення істини означає, що якщо ви йдете назад в дерево, , Що означає слово імені Максвелла в цьому. Але слово Фу, наприклад, Не в дереві, тому що якщо я почну в кореневому вузлі тут на вершині, Там немає F покажчик, покажчик не про, немає покажчиків о. Foo це не ім'я, в цьому словнику. Але на відміну від, Тьюринг, т-у-т-и-н-г. Знову ж таки, я не зберігайте т або й чи г або я або н або р. Але я зробив магазин в цю структуру даних значення істинний шлях тут, у цьому вузлі - в дерево , Встановивши для цього логічне значення is_word до істини. Так Trie це свого роду це дуже цікаво мета структури, де ви дійсно не зберігання самих слів для такого роду словник. Щоб було ясно, що ви просто зберігати так чи ні, є слово, яке закінчується тут. 

Тепер те, що мається на увазі? Якщо у вас є 150 тисяч слів у словнику, що ви намагаєтеся зберегти в пам'яті використовуючи щось на зразок пов'язаного списку, Ви будете мати 150000 вузлів у зв'язаному списку. І, знайшовши одне з цих слів в алфавітному порядку може прийняти O (п). Лінійне час. Але у випадку тут вигляді дерева, що час роботи знайти слова? Виявляється, краса тут є те, що навіть якщо у вас уже 149999 слів у цьому словнику, як це реалізовано з цією структурою даних, Скільки часу потрібно для того, щоб знайти або вставити ще одна людина в тому, як Аліса, Аліса? Ну, це тільки 5, може бути 6 кроків для заднього характер. Тому що presense інших імен в структурі не заважати вставки Аліса. Крім того, знаходження Аліса відразу виникають 150000 слів у цьому словнику не стояти на шляху знаходження Аліса взагалі, тому що Еліс. . . . . тут, тому що я знайшов логічне значення. А якщо немає логічне правда, то Аліса не в цій структурі даних слів. Іншими словами, час роботи таких речей і вставки речей в цій новій Структура даних Trie є O з - це не п. Тому що presense з 150.000 чоловік ніяк не впливає на Алісу, здається. Отже, давайте називати це до, де до максимальної довжини слова англійською мовою які, як правило, не більш ніж 20-те символи. Таким чином, до-постійна. Таким чином, Святий Грааль, ми, здається, знайшли зараз є те, що у вигляді дерева, постійна часу для вставок, для пошуку, для видалення. Оскільки кількість речей вже в структурі, які не є навіть фізично там. Знову ж таки, вони тільки вид відзначитися, так чи ні, не впливає на його майбутнє час роботи. 

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

Вірте чи ні, як же весело, як C була в протягом деякого часу, Ми наближаємося до того часу в семестрі, де цей час до переходу на більш сучасні речі. Речі на більш високому рівні. І хоча протягом наступних кількох тижнів ми все ще продовжуємо занурюватися у світ покажчики і керування пам'яттю щоб отримати це комфорт, з яким ми можемо розвивати, В кінці гри, в кінцевому рахунку ввести, за іронією долі, не в цю мову. Ми проведемо, як і 10 хвилин говорив про HTML. Все це HTML є мовою розмітки, і те, що мова розмітки Саме ці серії відкритих і закритих дужки дужки, які говорять, "зробити цей сміливий" 'Зробити це курсивом "," зробити це по центру. " Це ще не все, що інтелектуально цікава, але це супер корисно. І це, звичайно, всюдисущий в ці дні. Але те, що потужні про світ HTML і веб-програмування в цілому, будує динамічні речі, написання коду на мові PHP або як Python або Ruby, або Java або C #. Дійсно, незалежно від вашої мови вибір, і генеруючих HTML динамічно. Створення так званих CSS динамічно. Каскадні таблиці стилів, які також про естетику. І тому навіть сьогодні, якщо я йду на сайт як деякі знайомі Google.com, і я йду, щоб подивитися, розробник, вид джерела, який, може бути, ви зробили перш, але збираюся переглянути вихідний код, цей матеріал, ймовірно, виглядає досить загадково. Але це вихідний код, що реалізовує Google.com. На передньому кінці. А насправді все це пухнасті речі естетики. Це CSS тут. Якщо я буду прокрутки вниз, ми отримаємо деякі кольорові речі. Це HTML. Код Google виглядає як безлад, але якщо я насправді відкриває інше вікно, ми можемо бачити деякі структури до цього. Якби я відкрити це, зауважте, тут, це трохи більш читабельним. Ми збираємося, щоб побачити незабаром цей тег, [слово] тег, HTML, голови, тіла, DIV, сценарій, текст області, служби по центру, дів. І це теж ніби загадкового виду на перший погляд, але все це неподобство слід певним зразкам, і повторювані візерунки, так що як тільки ми отримаємо основами, ви зможете написати такий код , А потім маніпулювати код, як це, використовуючи ще одну мову, званий JavaScript. І JavaScript є мовою, який працює всередині браузера Сьогодні, яку ми використовуємо на курсах Гарварду, для інструменту курс покупки, які використовують карти Google , Щоб дати вам цілу купу динамізм, Facebook дає вам показати миттєві оновлення статусу, Twitter використовує це, щоб показати вам, замітки в соціальних мережах миттєво. Все це ми почнемо занурюватися дюйма Але щоб потрапити туди, ми повинні зрозуміти дещо про Інтернет. Цей кліп тут знаходиться всього в хвилині довго, і припустимо, на даний момент це, по суті, як працює Інтернет, як дразнилка для того, що ось-ось прийде. Я даю вам "Воїни Мережі". 

[♫ Повільна музика хор ♫] [Чоловік оповідача] Він прийшов із повідомленням. З протоколом все своє. [♫ швидка електронна музика ♫] Він прийшов у світ прохолодно брандмауери, маршрутизатори байдуже, і небезпек набагато гірше, ніж смерть. Він швидкий. Він сильний. Він TCP / IP, і у нього є свою адресу. Воїни в Мережі. [Малан] На наступному тижні, то. Інтернет. Веб-програмування. Це CS50. [CS50.TV]