[Powered by Google Translate] [Огляд] [Вікторина 0]
>> [Lexi Росс, Томмі MacWilliam, Лукас Фрейтас, Йосип Ong] [Harvard University]
>> [Це CS50.] [CS50.TV]
>> Привіт, всім.
Ласкаво просимо на розгляд сесії Вікторина 0, яке проходить у середу.
Що ми збираємося робити сьогодні ввечері, я з 3 іншими ТФ,
і разом ми збираємося пройти через огляд того, що ми зробили в ході цих пір.
Це не збирається бути на 100% всеосяжної, але вона повинна дати вам більш повне уявлення
про те, що у вас вже є вниз і те, що ви все ще потрібно вивчити, перш ніж в середу.
І не соромтеся піднімати руку з питаннями, коли ми збираємося разом,
але майте на увазі, що ми будемо мати трохи часу в кінці-
якщо ми пройдемо з декількох хвилин, щоб запасних, щоб зробити загальні питання,
так що майте це на увазі, і тому ми збираємося почати на початку тижня з 0.
>> [Вікторина 0 Огляд] [Частина 0] [Lexi Ross] Але перш ніж ми це зробимо, давайте поговоримо про
матеріально-технічне забезпечення вікторини.
>> [Логістика] [вікторини відбудеться в середу 10/10 замість лекції]
>> [(Див. http://cdn.cs50.net/2012/fall/quizzes/0/about0.pdf подробиці)] Це в середу, 10 жовтня.
>> Ось в цю середу, і якщо ви йдете на цю адресу тут,
який також доступний з CS50.net-Там посилання на нього-
Ви можете побачити інформацію про те, куди піти на основі
Ваше прізвище або школу приналежності, а також
він говорить саме про те, що тест буде охоплювати і типів питань, що ви збираєтеся отримати.
Майте на увазі, що ви також будете мати можливість переглянути на вікторину в розділі
так що ваші ТФ повинні йти на деякі практики проблеми,
і це ще один хороший шанс, щоб побачити, де ви все ще потрібно вивчити для вікторини.
Давайте почнемо з самого початку з Б-н-біт.
Пам'ятайте, трохи тільки 0 або 1,
і байт являє собою набір з 8 цих бітів.
Давайте подивимося на цю колекцію бітів прямо тут.
Ми повинні бути в змозі з'ясувати, скільки біт є.
Де ми розраховуємо є тільки 8 з них вісім 0 або 1 шт.
А так як є 8 біт, це 1 байт,
і давайте перетворити його в шістнадцятковий.
Шістнадцяткові є підставою 16, і це досить легко перетворити
Число в двійковій системі, яка є, що це таке, і їх число в шістнадцяткове.
Все що ми робимо, ми дивимося на групи по 4,
і ми конвертувати їх у відповідний шістнадцятковий.
Почнемо з самої правої групі 4, тому 0011.
Це буде одна 1 та одна 2, так разом, що робить 3.
А потім давайте подивимося на інший блок 4.
1101. Це буде одна 1, одна 4, і один 8.
Разом що це буде 13, що робить D.
І ми будемо пам'ятати, що в шістнадцятковій ми не просто йти від 0 до 9.
Ми йдемо від 0 до F, так що після 9, 10 відповідає,
Від 11 до B, і так далі, де F 15.
Тут 13 являє собою D,
так, щоб перетворити його в десяткове все що ми робимо, ми насправді
ставитися один до позиції сили 2.
Це одна 1, одна 2, нульовий 4s, 8s нуля, однієї 16, і так далі,
і це трохи важко обчислити у вашій голові, але якщо ми йдемо до наступного слайду
ми бачимо, відповідь на це питання.
>> По суті, ми збираємося навпроти право повернутися до лівих,
і ми множачи кожну цифру відповідним ступенем 2.
І пам'ятайте, для шістнадцяткових позначити ці цифри з 0x на початку
тому ми не плутайте його з десяткове число.
Продовжуючи, це ASCII таблиці,
і те, що ми використовуємо для ASCII є перетворення із символів в числові значення.
Пам'ятаєте, в PSET криптографії ми широко використовували ASCII таблиці
Для використання різних методів криптографії,
Цезар і шифр Віженер, конвертувати різні букви
У рядок у відповідності з ключовими задається користувачем.
Давайте подивимося на трохи ASCII математики.
Дивлячись на 'P' + 1, в символьній формі, яка була б Q,
і пам'ятайте, що '5 '≠ 5.
І як би ми точно конвертувати між цими 2 форми?
Це насправді не дуже важко.
Для того, щоб отримати 5 ми віднімаємо '0 '
тому що є 5 місць між '0 'і '5.
Для того, щоб піти по іншому шляху, ми просто додамо 0,
так що це ніби як регулярні арифметика.
Тільки пам'ятайте, що, коли щось лапки, це характер
і, отже, відповідає значенню в таблиці ASCII.
Переміщення в більш загальні теми з інформатики.
Ми дізналися, що таке алгоритм і як ми використовуємо програмуванню
для реалізації алгоритмів.
Деякі приклади алгоритмів щось просте, як
перевірки, чи є число парних або непарних.
Для цього пам'ятаєте, що ми мода число на 2 і перевірити, якщо результат дорівнює 0.
Якщо це так, то це ще. Якщо ні, то це дивно.
І це приклад дійсно основний алгоритм.
>> Трохи складніше один бінарний пошук,
які ми розглянемо пізніше в огляді сесії.
І програмуванні термін, який ми використовуємо для прийняття алгоритму
і перетворення його в код, комп'ютер може читати.
2 приклади програмування Scratch,
що ми і зробили в тиждень 0.
Навіть якщо ми насправді не вдрукувати код це спосіб реалізації
Цей алгоритм, який друкує номери 1-10,
і тут ми зробити те ж саме на мові програмування Сі.
Ці функціонально еквівалентні, щойно написані на різних мовах або синтаксису.
Потім ми дізналися про логічних виразів,
і логічне є значення, яке або істинно, або помилково,
і тут часто логічні вирази
Заходимо всередину умовах, так що якщо (х ≤ 5),
Ну, ми вже встановлені х = 5, так що умова буде оцінити, вірно.
І якщо це правда, що код під умову
буде оцінюватися за допомогою комп'ютера, так що рядок буде друкуватися
на стандартний вивід, а термін умова
ставиться до того, що знаходиться всередині дужки, якщо заяву.
Пам'ятайте, що всі оператори.
Пам'ятайте, що це && і | |, коли ми намагаємося об'єднати 2 або більше умов,
Чи не === перевірити 2 речі дорівнюють.
Пам'ятайте, що = для призначення в той час як == це логічний оператор.
≤, ≥, а потім остаточний 2 говорять самі за себе.
Загальний огляд булевої логіки тут.
І логічні вирази також є важливими у петлях,
які ми розглянемо зараз.
Ми дізналися про 3 види петель досі в CS50, бо, в той час як, і зробити в той час.
І це важливо знати, що в той час як для більшості цілей
ми дійсно можемо використати будь-який тип циклу в цілому
Є певні типи цілей або загальних закономірностей
в програмуванні, що конкретний заклик до одного з цих петель
, Які роблять його найбільш ефективним і елегантним, щоб закодувати його таким чином.
Давайте подивимося, що кожна з цих петель, як правило, використовується для найбільш часто.
>> У цикл ми в цілому вже знаю, скільки разів ми хочемо перебрати.
Це те, що ми вкладаємо в змозі.
Бо, я = 0, <10, наприклад.
Ми вже знаємо, що ми хочемо зробити щось у 10 разів.
Тепер, у той час як цикл, як правило, ми не обов'язково
знаю, скільки разів ми хочемо, щоб петля для запуску.
Але ми знаємо, свого роду умова, що ми хочемо, щоб
Завжди бути істинним або хибним завжди.
Наприклад, у той час встановлена.
Давайте говорити, що це логічна змінна.
Хоча це правда, ми хочемо, щоб код, щоб оцінити,
так що трохи більш розширюваної, трохи більш загальне, ніж цикл,
але будь цикл може бути перетворено в той час як петля.
І, нарешті, робити, поки петлі, яка може бути найскладніша зрозуміти відразу,
часто використовується, коли ми хочемо оцінити Спочатку код
Перед Вперше ми перевіряємо стан.
Загальний випадок використання робити під час циклу
коли ви хочете отримати користувача введення, і ви знаєте, ви хочете запитати користувача
для введення принаймні один раз, але якщо вони не дають вам хороші вхідні відразу
Ви хочете продовжувати просити їх, поки вони дають вам хороший вхід.
Це найпоширеніший спосіб використання цього час циклу,
і давайте подивимося на реальну структуру цих петель.
Як правило, вони завжди прагнуть слідувати цим паттернам.
>> На цикл всередині вас є 3 компоненти:
ініціалізації, як правило, щось на зразок Int я = 0, де я є лічильник,
стан, в якому ми хочемо сказати, запустити цей цикл, поки ця умова залишається в силі,
як я <10, і, нарешті, оновлення, який є, як ми збільшуємо
змінна лічильника в кожній точці циклу.
Звичайна річ, щоб бачити, що є тільки я + +,
що означає збільшувати я на 1 кожен раз.
Ви також можете зробити щось подібне я + = 2,
що означає, додайте 2 до я кожен раз ви йдете через петлю.
І тоді зробити це тільки відноситься до будь-який код, який фактично працює як частина циклу.
І на деякий час циклу, на цей раз у нас дійсно є ініціалізація поза циклом,
Так, наприклад, припустимо, що ми намагаємося зробити те ж саме тип циклу, як я тільки що описав.
Ми хотіли б сказати Int = 0 перед початком циклу.
Тоді ми могли б сказати, коли я <10 цього
так само блок коду, як і колись,
і на цей раз оновлення частини коду, наприклад, я + +,
насправді відбувається всередині циклу.
І, нарешті, в той час як робити, це схоже на час циклу,
але ми повинні пам'ятати, що код буде оцінювати рази
Перед умова перевіряється, тому він робить набагато більше сенсу
якщо ви подивитеся на неї в порядку зверху вниз.
У той час як цикл зробити код оцінює перш, ніж ви навіть дивитися на цей час умови,
в той час як час циклу, вона перевіряє в першу чергу.
Заяви та змінні.
Коли ми хочемо створити нову змінну, ми спочатку хочемо ініціалізувати його.
>> Наприклад, внутр бар ініціалізує змінну бар,
але це не дає їй значення, так що значення барі зараз?
Ми не знаємо.
Це може бути якась фігня значення, яке зберігається в пам'яті там,
і ми не хочемо використовувати цю змінну
поки ми фактично не дати йому значення,
таким чином, ми оголосимо його тут.
Потім ми ініціалізували, що це буде 42 нижче.
Зараз, звичайно, ми знаємо, що це може бути зроблено на одній лінії, внутр бар = 42.
Але Просто щоб бути ясно декількох кроків, що відбувається,
Декларація і ініціалізація відбувається роздільно.
Це відбувається на один крок, і наступний, внутр Баз = бар + 1,
це твердження нижче, яке збільшує Баз, так що в кінці цього блоку коду
якби ми були на друк значення Баз було б 44
тому що ми оголосити і ініціалізувати, що це буде 1> бару,
і тоді ми збільшуємо його ще раз з + +.
Ми пішли на це досить коротко, але це добре, щоб мати загальне
розуміння того, що теми і події.
В основному ми зробили це в Scratch,
так що ви можете думати про теми, як кілька послідовностей коду
працює в той же час.
Насправді, це, ймовірно, не працює, в той же час,
а як би абстрактно ми можемо думати про це таким чином.
>> У Scratch, наприклад, у нас було кілька спрайтів.
Це може бути виконання іншого коду, в той же час.
Можна було ходити, а інший говорить щось
В іншій частині екрану.
Події ще один спосіб виділення логіки
між різними елементами коду,
і подряпин, ми змогли змоделювати події за допомогою трансляції,
і що насправді, коли я отримую, а не коли я чую,
але по суті це спосіб передачі інформації
від одного спрайту на інший.
Наприклад, ви можете передати гру на себе,
і коли інший спрайт отримує за гру,
він реагує певним чином.
Це важлива модель для розуміння програмування.
Просто перейти на основну тиждень 0, те, що ми перейшли до цих пір,
давайте подивимося на це просте програми на Сі.
Текст може бути трохи невеликим звідси, але я піду на це дуже швидко.
Ми в тому числі 2 файли заголовків у верхній частині, cs50.h і stdio.h.
Ми тоді визначенні постійної називається межею в 100.
Ми тоді здійсненні нашої головної функції.
Так як ми не будемо використовувати аргументи командного рядка тут ми повинні поставити недійсними
в якості аргументів для основного.
Ми бачимо Int вище основного. Це тип значення, що повертається, тому повертати 0 у нижній частині.
І ми використовуємо CS50 функції бібліотеки отримують Int
запитати користувача для входу, і ми зберігаємо його в цій змінній х,
таким чином, ми заявляємо х вище, і ми ініціалізувати його з х = GetInt.
>> Потім ми перевіряємо, якщо користувач дав нам хороший вхід.
Якщо це ≥ LIMIT ми хочемо повернути код помилки 1 і друкувати повідомлення про помилку.
І, нарешті, якщо користувач дав нам хороший вхід
ми збираємося звести в квадрат числа і роздрукувати цей результат.
Просто щоб переконатися, що ті всі хіт додому
Ви можете бачити етикетки різних частин коду тут.
Я згадував постійно, файли заголовків.
О, Int х. Переконайтеся в тому, пам'ятайте, що це локальна змінна.
Це контрастує його від глобальних змінних, які ми будемо говорити про
Трохи пізніше в огляді сесії
і ми закликаємо бібліотечні функції Printf,
так що, якщо б ми не включили заголовний файл stdio.h
ми не були б в змозі назвати Printf.
І я вважаю, що стрілка, яка отримала відрізати тут вказує на% D,
яка є форматування рядка в Printf.
Він каже, роздрукуйте цю змінну як число,% D.
І це все за тиждень 0.
Тепер Лукас має намір продовжувати.
Гей, хлопці. Мене звуть Лукас.
Я на другому курсі в кращому будинку на території кампусу, Mather,
і я хочу поговорити трохи про тиждень 1 і 2,1.
[Тиждень 1 і 2,1!] [Лукас Фрейтас]
Як Lexi говорив, коли ми почали переводити код з нуля C
одна з речей, які ми помітили, що ви не можете просто
написати свій код і запустити його за допомогою зеленого прапора більше.
Насправді, ви повинні використовувати деякі кроки, щоб зробити вашу програму C
стали виконуваний файл.
В основному, що ви робите, коли ви пишете програми є те, що
Ви переводите ваші ідеї на мову, компілятор може зрозуміти,
тому, коли ви пишете програму в C
що ви робите насправді щось писав, що компілятор буде розуміти,
, А потім компілятор збирається перевести цей код
в те, що ваш комп'ютер буде розуміти.
>> А справа в тому, комп'ютер насправді дуже нерозумно.
Ваш комп'ютер може зрозуміти тільки 0 і 1,
так насправді в перші комп'ютери зазвичай люди запрограмовані
використання 0 і 1, але не більше, слава Богу.
Ми не потрібно запам'ятовувати послідовності 0 та 1
за цикл або цикл, поки і так далі.
Ось чому у нас є компілятор.
Який компілятор робить це в основному переводить код C,
У нашому випадку, до мови, що ваш комп'ютер буде розуміти,
яка є об'єктний код, а компілятор, який ми використовуємо
називається дзвін, так що це насправді символ брязкіт.
Якщо у вас є програма, що вам потрібно зробити 2 речі.
По-перше, ви повинні компілювати вашу програму, а потім ви збираєтеся запустити програму.
Для компіляції програми у вас є багато варіантів, щоб зробити це.
Перший робити брязкіт program.c
В якій програмі це назва вашої програми.
У цьому випадку ви можете бачити, що вони просто кажуть: "Ей, компіляції моєї програми".
Ви не говорите "я хочу це назва для моєї програми", або нічого.
>> Другий варіант дає назву вашої програми.
Можна сказати, брязкіт-O, а потім ім'я, яке ви хочете
виконуваний файл буде називатися, як і program.c.
І ви також можете зробити зробити програму, і подивитися, як у перших 2-х випадках
Я ставлю. С, а в третьому у мене тільки програми?
Так, ви насправді не варто ставити. С, коли ви використовуєте зробити.
В іншому випадку компілятор насправді відбувається, щоб кричати на вас.
А також, я не знаю, якщо ви, хлопці, пам'ятайте,
але багато разів ми також використовували lcs50-або-лм.
Це називається зв'язків.
Він просто повідомляє компілятору, що ви будете використовувати ці бібліотеки тут же,
так що якщо ви хочете використовувати cs50.h ви насправді повинні ввести
брязкіт program.c-lcs50.
Якщо ви не зробите цього, компілятор не буде знати,
що ви використовуєте ці функції в cs50.h.
І коли ви хочете запустити вашу програму у вас є 2 варіанти.
Якщо ви зробили брязкіт program.c Ви не дати назву вашої програми.
Ви повинні запустити його за допомогою. / A.out.
A.out є стандартним ім'ям, брязкіт дає вашій програмі, якщо ви не даєте йому ім'я.
В іншому випадку ви збираєтеся робити. / Програма, якщо ви дали назву вашої програми,
а також, якщо ви робили програму ім'я, яке програма буде отримати
вже буде запрограмований тим же ім'ям, що і файл с.
Тоді ми говорили про типи даних і даних.
>> Основному типів даних одні і ті ж речі, як маленькі коробочки вони використовують
для зберігання значень, так що типи даних насправді так само, як покемонів.
Вони бувають різних розмірів і типів.
Я не знаю, що аналогія має сенс.
Розмір даних насправді залежить від архітектури машини.
Всі дані розмірів, що я збираюся показати тут
насправді для 32-бітних машин, які в разі нашого приладу,
Але якщо ви насправді кодування вашого Mac або Windows, в також
ймовірно, ви будете мати 64-розрядні машини,
так що не забудьте, що дані розміри, які я збираюся показати тут
призначені для 32-розрядних машин.
Перше, що ми побачили, було INT,
який є досить простим.
Ви можете використовувати Int для зберігання цілого числа.
Ми також бачили символ, символ.
Якщо ви хочете використовувати букви або символу мало ви, ймовірно, будете використовувати символ.
Символ має 1 байт, що означає 8 біт, як сказала Лексі.
В основному ми повинні ASCII таблиці, що має 256
можливі комбінації 0 і 1,
, А потім, коли ви вводите символ він збирається переводити
символ, який ви входів номер, який ви маєте в ASCII таблиці, як Лексі сказала.
У нас також є поплавець, який ми використовуємо для зберігання десяткових чисел.
Якщо ви хочете вибрати 3.14, наприклад, ви збираєтеся використовувати поплавець
або подвійною, який має більше точності.
Поплавок має 4 байт.
Подвійне має 8 байт, тому різниця тільки в тому точністю.
У нас також є довгий, який використовується для цілих чисел,
і ви можете бачити на 32-бітної машині Int і довгий мають однаковий розмір,
таким чином, це дійсно не має сенсу використовувати довгий в 32-бітної машині.
>> Але якщо ви використовуєте Mac і 64-розрядних машин, насправді давно має розмір 8,
так що це дійсно залежить від архітектури.
Для 32-бітної машині він не має сенсу використовувати довгий дійсності.
А потім довго довго, з іншого боку, має 8 байт,
так що це дуже добре, якщо ви хочете мати більше цілого.
І, нарешті, у нас є рядок, яка є насправді символ *,
, Який є дороговказом на символ.
Це дуже легко думати, що розмір рядка буде, як
Кількість символів, які у вас там,
але насправді символ * сама
має розмір покажчика на символ, який становить 4 байти.
Розмір символ * 4 байти.
Це не має значення, якщо у вас є невеликий словом або письмом або нічого.
Це буде 4 байт.
Ми також дізналися дещо про литва,
так як ви можете бачити, якщо у вас, наприклад, програму, яка говорить
Int х = 3, а потім Е ("% D", х / 2)
ви, хлопці, знаєте, що він збирається друкувати на екрані?
>> Хтось? >> [Студенти] 2.
1. >> 1, так.
Коли ви робите 3/2 він збирається отримати 1,5,
але так як ми використовуємо ціле вона збирається ігнорувати дробової частини,
і ви будете мати 1.
Якщо ви не хочете, щоб це сталося, що ви можете зробити, наприклад,
це оголосити поплавок у = х.
Тоді х, що раніше було 3, тепер буде 3,000 в рік.
І тоді ви можете друкувати у / 2.
Насправді, я повинен мати 2. там.
Він збирається зробити 3.00/2.00,
і ви будете отримувати 1,5.
А у нас це 0,2 F просто питати 2 десяткових одиниць в десятковій частині.
Якщо у вас є 0,3 F, що це буде мати насправді 1.500.
Якщо це 2 це буде 1,50.
У нас також є це в даному випадку.
Якщо ви поплавок х = 3,14, і тоді ви Printf х
Ви збираєтеся отримати 3,14.
І якщо ви робите х = Int х,
, Що означає лікування х у вигляді цілого числа і друку х зараз
Ви будете мати 3,00.
Чи має це сенс?
Тому що ви перший лікуванні х як ціле, так що ви не звертаючи уваги на дробову частину,
а потім ви друкуєте х.
І, нарешті, ви також можете зробити це,
Int х = 65, а потім оголосити символ з = х,
а потім, якщо ви друкуєте з ви насправді збираєтеся отримати
, Тому в основному те, що ви тут робите
переводить ціле число в символ,
як ASCII таблиці робить.
Ми також говорили про математику операторів.
Більшість з них досить прості, тому +, -, *, /,
а також ми говорили про моду, яка є залишок від ділення 2-х номерів.
Якщо у вас є 10% 3, наприклад,
це означає, розділіть 10 на 3, а що решта?
Це буде 1, так що це насправді дуже корисно для багатьох програм.
Для Віженер і Цезаря я впевнений, що всі ви, хлопці використовували мод.
Про математичні оператори, будьте дуже обережні при комбінуванні * і /.
>> Наприклад, якщо ви робите (3/2) * 2, що ви збираєтеся отримати?
[Студенти] 2.
Так, 2, так як 3/2 буде 1,5,
але так як ви робите операції між 2 цілих чисел
насправді ви тільки збираєтеся вважати 1,
і 1 * 2 буде 2, так що будьте дуже, дуже обережні
коли робити арифметичні дії з цілими числами, тому що
Ви могли б отримати, що 2 = 3, в цьому випадку.
А також бути дуже обережним пріоритет.
Ви повинні зазвичай використовувати дужки, щоб бути впевненим, що ви знаєте, що ви робите.
Деякі корисні ярлики, звичайно, один я + + або я + = 1
або за допомогою + =.
Це те ж саме, що робив I = I + 1.
Ви також можете зробити я - чи я - = 1,
що те ж саме, що і I = -1,
щось ви, хлопці використовують багато в цикли, по крайней мере.
Крім того, для *, якщо ви використовуєте * = і, якщо ви, наприклад,
я * = 2, те ж саме, кажучи, що я = I * 2,
і те ж саме для поділу.
Якщо у вас в / = 2 це те ж саме, що я = я / 2.
>> Тепер про функції.
Ви, хлопці дізналися, що функції є дуже хорошою стратегією для збереження коду
в той час як ви програмуєте, тому, якщо ви хочете виконати ту ж задачу
в код знову і знову, ймовірно, ви хочете використовувати функцію
просто так вам не доведеться скопіювати і вставити код знову і знову.
Насправді, основна функція, і коли я покажу вам формат функції
Ви побачите, що це досить очевидно.
Ми також використовуємо деякі функції з бібліотеки,
Наприклад, Printf, Getin, що з бібліотеки CS50,
та інші функції, такі як ToUpper.
Всі ці функції реалізуються на практиці в інших бібліотеках,
і коли ви помістити ці файли троса на початку вашої програми
Ви кажете, не могли б ви дати мені код для цих функцій
так що я не повинна реалізовувати їх самостійно?
Також ви можете написати свої власні функції, тому, коли ви починаєте програмування
Ви розумієте, що бібліотеки не мають всі функції, які вам потрібно.
За останні PSET, наприклад, ми писали малювати, боротьба і пошук,
, І це дуже, дуже важливо, щоб мати змогу писати функції
тому що вони корисні, і ми використовуємо їх весь час в програмуванні,
і це економить багато коду.
Формат функції цього.
У нас є возвращаемого типу на самому початку. Який тип значення, що повертається?
Це просто, коли ваша функція буде повертати.
Якщо у вас є функція, наприклад, факторного,
, Яка буде обчислювати факторіал цілого числа,
ймовірно, він збирається повертати ціле число, теж.
Тоді возвращаемого типу буде Int.
Printf насправді має порожнечу возвращаемого типу
тому що ви не повертається нічого.
Ти просто друкувати речі на екрані
і вихід з функції після цього.
Тоді у вас є ім'я функції, які ви можете вибрати.
Ви повинні бути трохи розумні, як не вибирають ім'я, як XYZ
або як х2.
Спробуйте зробити собі ім'я, яке має сенс.
>> Наприклад, якщо це факторіал, скажімо факторіал.
Якщо це функція, яка буде малювати щось, назвіть його малювати.
І тоді у нас є параметри, які також називаються аргументами,
, Які, як ресурси, що ваша функція повинна
з вашого коду для виконання своїх завдань.
Якщо ви хочете, щоб обчислити факторіал числа
ймовірно, у Вас повинен бути поруч, щоб обчислити факторіал.
Один з аргументів, які ви збираєтеся їсти, сам номер.
І тоді це буде щось робити, і повертати значення в кінці
якщо це не пустота функції.
Давайте подивимося на прикладі.
Якщо я хочу написати функцію, яка підсумовує всі числа в масив цілих чисел,
Перш за все, возвращаемого типу буде Int
тому що в мене є масив цілих чисел.
І тоді я буду мати ім'я функції, як sumArray,
а потім він збирається взяти сам масив, в ціле НУМС,
, А потім довжину масиву, тому я знаю, як багато чисел, у мене підвести.
Тоді у мене є для ініціалізації змінної називають суму, наприклад, 0,
і кожного разу, коли я бачу елемент в масиві я повинен додати його в суму, тому я зробив цикл.
Так само, як Лексі сказала, ви робите Int я = 0, <довжина і я + +.
І для кожного елемента в масиві я зробив суму + = НУМС [я],
а потім я повернувся суму, так що це дуже просто, і це економить багато коду
якщо ви використовуєте цю функцію багато разів.
Потім ми розглянули умови.
У нас, якщо, ще, і ще, якщо.
Давайте подивимося, в чому різниця між тими, хто.
Погляньте на ці 2 коди. У чому різниця між ними?
Перша була в основному-коди хочу, щоб ти
якщо число +, - або 0.
Перший каже, що якщо він> 0, то це позитивно.
Якщо це = 0, то це 0, а якщо <0, то це негативно.
>> А інший робить, якщо, інакше, якщо інше.
Різниця між ними полягає в тому, що ця людина насправді збирається
перевірити, якщо> 0, <0 = 0 або три рази,
так що якщо у вас є номер 2, наприклад, він збирається приїхати сюди і сказати:
Якщо (X> 0), і він скаже так, так я друкувати позитивні.
Але, хоча я знаю, що це> 0, і він не збирається бути 0 або <0
Я все ще збираюся робити це 0, то <0,
так що я насправді відбувається всередині IFS, що я не повинна
тому що я вже знаю, що він не збирається, щоб задовольнити будь-яке з цих умов.
Я можу використовувати, якщо, інакше, якщо іншу заяву.
Це в основному говорить, що якщо х = 0 надрукувати позитивні.
Якщо це не так, я буду також перевірити це.
Якщо це 2 не я збираюся це зробити.
В принципі, якщо у мене було х = 2 ви могли б сказати
Якщо (X> 0), так, так друкувати.
Тепер, коли я знаю, що це> 0 і що він задоволений першим, якщо
Я навіть не збираюся запустити цей код.
Код працює швидше, насправді, в 3 рази швидше, якщо ви використовуєте це.
Ми також дізналися про і і або.
Я не збираюся пройти через це, тому що Лексі вже говорили про них.
Це просто && і | | оператора.
>> Єдине, що я скажу, будьте обережні, коли у вас є 3 умови.
Використовуйте дужки, тому що це дуже заплутаним, коли у Вас є умова
і ще одне або інше.
Використовуйте дужки просто щоб бути впевненим, що ваші умови сенсу
тому що в цьому випадку, наприклад, ви можете собі уявити, що
це може бути першою умовою і одним або іншим
або 2 умови об'єднаних в і
або третя, так що будьте обережні.
І, нарешті, ми говорили про комутаторах.
Вимикач дуже корисно, коли у вас є змінна.
Давайте припустимо, що у вас є змінна, як п
що може бути 0, 1 або 2, і для кожного з цих випадків
Ви збираєтеся виконати завдання.
Ви можете сказати перемикання змінної, а це означає, що
значення те, як value1 я збираюся зробити це,
а потім ламається, який означає, що я не буду дивитися на будь-яку з інших випадках
тому що ми вже задоволені тим, що справа
, А потім value2 і так далі, і я також може мати значення за замовчуванням перемикача.
Це означає, що, якщо він не задовольняє ні одній зі справ, які у мене були
що я збираюся зробити щось ще, але це необов'язково.
Це все для мене. Тепер давайте Томмі.
Все правильно, це буде тиждень 3-іш.
Ось деякі з тем, які ми будемо покриття, крипто, сфери застосування, масиви, і так далі.
Просто слів про криптографії. Ми не збираємося забивати цим будинком.
>> Ми зробили це в PSET 2, але для тест переконаєтеся, що ви знаєте різницю
між шифр Цезаря і шифр Віженер,
як обидві ці роботи шифрів і що це таке для шифрування
і розшифрувати текст, використовуючи ці 2 шифри.
Пам'ятайте, що шифр Цезаря просто повертає кожен символ на ту ж суму,
переконавшись, що ви мода на кількість літер в алфавіті.
І шифру Віженер, з іншого боку, обертається кожен символ
по іншу суму, так що замість того, щоб говорити
кожен персонаж повернуть на 3 Віженер буде обертати кожен символ
на різну кількість залежно від деяких ключових слів
де кожна буква в ключове слово являє собою деяку іншу суму
щоб повернути відкритим текстом по.
Давайте спочатку поговоримо про змінної області.
Є 2 різних типів змінних.
У нас є локальні змінні, і ці будуть визначені
за межами основного або поза небудь функції або блоку,
і вони будуть доступні в будь-якому місці програми.
Якщо у вас є функція, і в цій функції є час циклу
великі глобальні змінні доступні скрізь.
Локальна змінна, з іншого боку, є областю до місця, де вона визначена.
>> Якщо у вас є функція Ось, наприклад, у нас є ця функція г,
і всередині G є змінна тут називається в,
і це означає, що це локальна змінна.
Навіть якщо ця змінна називається у
і ця змінна називається у цих 2 функцій
не знаю, що один одного локальних змінних.
З іншого боку, тут ми говоримо Int х = 5,
і це виходить за рамки будь-якої функції.
Це виходить за рамки основного, так це глобальна змінна.
Це означає, що всередині цих 2 функцій, коли я говорю х - або х + +
Я доступ до тієї ж х причому це у і у цього є різними змінними.
Ось в чому різниця між глобальних змінних і локальних змінних.
Що стосується дизайну, то, іноді це хорошою ідеєю
зберегти локальні змінні, коли ви, можливо, може
так як з купою глобальних змінних можна отримати дуже заплутаною.
Якщо у вас є купа функцій всі зміни одне і те ж
Ви можете забути, що якщо ця функція випадкового змінює цей глобальний,
і ця інша функція не знає про це,
і це дійсно стає досить заплутаним, як ви отримаєте більше коду.
Збереження локальних змінних, коли ви, можливо, може
просто гарний дизайн.
Масиви, пам'ятайте, що це просто списки з елементів того ж типу.
Усередині CI не може мати список, як 1, 2,0, здрастуйте.
Ми просто не можемо цього зробити.
>> Коли ми оголошуємо масив в C усі елементи повинні бути того ж типу.
Тут у мене є масив з 3 цілих чисел.
Ось у мене є довжина масиву, але якщо я просто оголосити його в цей синтаксис
де я вказую, що всі елементи я технічно не потрібна ця 3.
Компілятор досить розумний, щоб зрозуміти, наскільки великий масив повинен бути.
Тепер, коли я хочу, щоб отримати або встановити значення масиву
це синтаксис, щоб зробити це.
Це насправді змінити другий елемент масиву, тому що, пам'ятаєте,
Нумерація починається з 0, а не з 1.
Якщо я хочу прочитати, що значення я можу сказати щось подібне Int х = масив [1].
Або, якщо я хочу встановити це значення, як я тут роблю,
Я можу сказати, масив [1] = 4.
У цей час доступ до елементів за індексом
або їх положення або де вони знаходяться в масиві,
і що в каталозі починається з 0.
Ми можемо також є масиви масивів,
і це називається багатовимірним масивом.
Коли у нас є багатовимірний масив
це означає, що ми можемо мати щось подібне рядків і стовпців,
і це тільки один із способів візуалізації цього або думати про це.
Коли у мене є багатовимірний масив, який означає, що я збираюся почати нужденних
більш ніж на 1 індекс, тому що якщо у мене є сітка
просто кажу, що рядок ви перебуваєте в не дає нам номер.
Це дійсно просто хочу, щоб дати нам список номерів.
Скажімо, у мене є цей масив тут.
У мене є масив називається сітка, і я кажу, що це 2 рядки і 3 стовпці,
і таким чином, це є одним із способів візуалізації його.
Коли я говорю, я хочу, щоб елемент [1] [2]
це означає, що, оскільки ці рядки, а потім стовпчики
Я збираюся перейти на рядок 1, так як я сказав 1.
>> Тоді я збираюся приїхати сюди в колонці 2, і я збираюся отримати значення 6.
Сенс?
Багатовимірні масиви, пам'ятайте, що технічно просто масив масивів.
Ми можемо мати масиви масивів масивів.
Ми можемо продовжувати, але дійсно один спосіб думати про
як це в даний час закладений, і те, що відбувається, щоб візуалізувати
в сітці, як це.
Коли ми передаємо масивів у функції, вони будуть вести себе
трохи по-іншому, ніж коли ми переходимо регулярних змінних функції
як передача Int або з плаваючою точкою.
Коли ми передаємо в Int або символ або будь-який з цих інших типів даних
ми тільки що розглянули, якщо функція змінює
значення цієї змінної, що зміни не збираюся поширюватися вгору
в зухвалу функцію.
З масивом, з іншого боку, що буде відбуватися.
Якби я передати масив до деякої функції і функція змінює деякі елементи,
коли я повернуся до функції, які назвали його
мій масив тепер буде по-іншому, і словник для цього
це масиви передаються по посиланню, як ми побачимо пізніше.
Це пов'язано як покажчики роботи, де ці основні типи даних,
З іншого боку, передаються за значенням.
>> Ми можемо думати про те, як зробити копію деякі змінні і переходячи потім у копії.
Не має значення, що ми робимо з цієї змінної.
Зухвала функція не буде знати, що він змінився.
Масиви є лише трохи відрізняється в цьому відношенні.
Наприклад, як ми тільки що бачили, основним є просто функцією
що можна взяти в 2 аргументів.
Перший аргумент основною функцією є агдс, або кількість аргументів,
а другий аргумент називається ARGV,
і ті фактичні значення цих аргументів.
Скажімо, у мене є програма під назвою this.c,
і я кажу це зробити, і я збираюся запустити в командному рядку.
Тепер, щоб пройти в деякі аргументи, щоб моя програма називається це,
Я міг би сказати щось подібне. / Це CS 50.
Це те, що ми уявляємо, Девід робити кожен день на терміналі.
Але тепер основна функція всередині цієї програми
має наступні значення, так агдс дорівнює 4.
Це може бути трохи заплутаним, тому що насправді ми тільки що проходять в цей CS 50.
Ось тільки 3.
Але пам'ятайте, що перший елемент ARGV або перший аргумент
це ім'я самої функції.
Таким чином, це означає, що у нас є 4 речі тут,
і перший елемент буде. / це.
І це буде представлено у вигляді рядка.
Тоді інші елементи того, що ми набрали після назви програми.
Так само, як в стороні, так як ми, напевно, бачили в PSET 2,
пам'ятаєте, що рядок 50, ≠ цілих 50.
Тому ми не можемо сказати щось на кшталт: "INT X = ARGV 3".
>> От тільки не збирається сенсу, тому що це рядок, і це число.
Так що, якщо ви хочете конвертувати між 2, пам'ятайте, що ми збираємося
Тобто ця чарівна функція називається atoi.
, Яка приймає рядок і повертає ціле число представлено в цьому рядку.
Так що це легко зробити помилку у вікторині,
просто думав, що це буде автоматично правильний тип.
Але точно знаю, що це завжди буде рядків
навіть якщо рядок містить тільки ціле число або символ або з плаваючою точкою.
Отже, тепер давайте поговоримо про час роботи.
Коли у нас є всі ці алгоритми, які роблять всі ці божевільні речі,
це стає дійсно корисно задатися питанням: «Як довго вони приймають?"
Ми уявляємо, що дещо, зване асимптотичне позначення.
Таким чином, це означає, що - ну, скажімо, ми даємо нашим алгоритмом
деякі дуже, дуже, дуже великий внесок.
Ми хочемо поставити запитання: "Як довго це займе?
Скільки кроків займе наш алгоритм для запуску
в залежності від розміру вхідних даних? "
Отже, перший спосіб, яким ми можемо описати час виконання з великою О.
І це наш найгірший хід часу.
Тому якщо ми хочемо, щоб відсортувати масив, і ми даємо нашим алгоритмом масиву
це в порядку убування, коли воно має бути в порядку зростання,
що буде в гіршому випадку.
Це наша верхня грань в максимальний час наш алгоритм буде.
З іншого боку, ця Ω буде описувати кращому випадку час роботи.
Так що, якщо ми дамо вже відсортований масив в алгоритм сортування,
Як довго це займе, щоб залагодити його?
І це, то, описує нижню межу на час роботи.
Отже, ось лише деякі слова, які описують деякі загальні працює рази.
Це в порядку зростання.
Самий швидкий біг часу у нас називається постійним.
>> Це означає, що незалежно від того, скільки елементів ми даємо нашим алгоритмом,
незалежно від того, наскільки велика наша масив, сортування
або робити те, що ми робимо в масив завжди буде така ж кількість часу.
Таким чином, ми можемо уявити, що тільки з 1, який є постійним.
Ми також подивилися на логарифмічне час перспективі.
Так щось подібне двійкового пошуку є логарифмічною,
де ми скоротили проблема в два рази кожен раз, коли
а потім все просто отримати вищу звідти.
І якщо ви коли-небудь письмово про будь факторіал алгоритм,
Ви, ймовірно, не слід розглядати це як свою роботу дня.
Коли ми порівнюємо часу роботи дуже важливо мати на увазі ці речі.
Так що, якщо у мене є алгоритм, який O (N), а хтось інший
була алгоритму O (2n), це насправді асимптотично еквівалентні.
Таким чином, якщо уявити собі, п бути велика кількість, як eleventy млрд:
тому, коли ми порівнюємо eleventy млрд. щось подібне eleventy млрд. + 3,
+3 Раптово, що насправді не роблять великої різниці більше.
Ось чому ми збираємося почати розглядати ці речі, щоб бути еквівалентними.
Так що такі речі, як ці константи тут, є 2 х це, або додавання 3,
це просто константи, і вони збираються кинути вгору.
Так ось чому всі ці 3 рази перспективі такі ж, як кажуть вони O (N).
Аналогічно, якщо у нас є 2 інші часи перспективі, скажімо, O (N ³ + 2n ²), ми можемо додати
+ П, + 7, а потім у нас є ще час виконання, що просто O (N ³).
знову ж таки, це одне і те ж, тому що це - це не те ж саме.
Це ті ж самі речі, вибачте. Таким чином, це ті ж самі, тому що
ця ³ п буде домінувати в цьому 2n ².
>> Що не одне і те ж, якщо ми вже запустили час, як O (N ³) і O (N ²)
тому що ця ³ п набагато більше, ніж ця ² н.
Так що, якщо у нас є показники, раптом це починає значення,
Але коли ми просто справу з факторами, як ми тут,
то він не збирається значення, тому що вони тільки збираються кидати.
Давайте поглянемо на деякі алгоритми, які ми бачили до сих пір
і говорити про їх виконання.
Перший погляд на номер у списку, який ми бачили, був лінійний пошук.
І реалізація лінійного пошуку супер просто.
Ми просто є список, і ми будемо дивитися на кожний окремий елемент у списку
поки ми не знайдемо число, яке ми шукаємо.
Таким чином, це означає, що в гіршому випадку, це O (N).
А в гіршому випадку тут могло б бути, якщо елемент
Останній елемент, то за допомогою лінійного пошуку, ми повинні дивитися на кожен окремий елемент
поки ми не отримаємо до останнього, щоб знати, що це було насправді в списку.
Ми не можемо просто кинути на півдорозі і сказати: "Це, напевно, немає».
З лінійний пошук, ми повинні дивитися на все це.
Кращому випадку час роботи, з іншого боку, постійно
тому що в кращому випадку елемент ми шукаємо це тільки перший у списку.
Таким чином, він збирається взяти нас рівно на 1 крок, незалежно від того, наскільки великий список
якщо ми шукаємо перший елемент кожного разу.
>> Тому, коли ви будете шукати, пам'ятайте, це не вимагає, щоб наш список буде відсортований.
Тому що ми просто будемо дивитися на кожний окремий елемент, і це дійсно не має значення
в якому порядку ці елементи дюйма
Більш інтелектуальний алгоритм пошуку щось на зразок бінарного пошуку.
Пам'ятайте, що реалізація бінарного пошуку, коли ви збираєтеся
продовжуйте дивитися в середину списку.
І тому, що ми дивимося на середині, ми вимагаємо, щоб список сортується
інакше ми не знаємо, де середина, і ми повинні дивитися на
весь список, щоб знайти його, а потім на той момент ми просто втрачаємо час.
Так що, якщо у нас є відсортований список, і ми знаходимо середину, ми збираємося порівняти середні
до елементу ми шукаємо.
Якщо вона занадто висока, то ми можемо забути правої половини
тому що ми знаємо, що якщо наш елемент вже занадто високі
і все, що правіше цього елемента ще вище,
то ми не повинні дивитися там більше.
Якщо, з іншого боку, якщо наш елемент є занадто низькою,
Ми знаємо все, аби зліва від цього елемента також є занадто низькою,
таким чином, це дійсно не має сенсу шукати там, також.
Таким чином, з кожним кроком, і кожен раз, коли ми дивимося на середину списку,
Ми збираємося скоротити наші проблеми в половину, тому що раптово ми знаємо,
цілу купу цифр, що не може бути той, який ми шукаємо.
>> У псевдокоді це виглядатиме приблизно так,
і тому, що ми різання списку в два рази кожен раз,
наші найгірші час виконання стрибків з лінійною до логарифмічної.
Так несподівано ми маємо вхід в систему кроки для того, щоб знайти елемент у списку.
Кращому випадку хід часу, хоча, як і раніше постійної
тому що тепер, давайте просто скажемо, що елемент ми шукаємо є
Завжди точно посередині початкового списку.
Так що ми можемо розвивати наш список як великий, як ми хочемо, але якщо елемент ми шукаємо знаходиться на середині,
Потім вона тільки збирається взяти нас на 1 крок.
Так ось чому ми O (журнал N) і Ω (1) або постійними.
Давайте реально працювати бінарний пошук в цьому списку.
Так що давайте говорити, що ми шукаємо елемент 164.
Перше, що ми збираємося зробити, це знайти середину цього списку.
Просто так вийшло, що середина буде падати між цими 2 номери,
так що давайте просто як завгодно говорити, кожен раз середина знаходиться між 2 номери,
Давайте просто округлити.
Нам просто потрібно переконатися, що ми робимо це кожен крок шляху.
Так що ми збираємося зганяти, і ми збираємося сказати, що 161 є середнім з нашого списку.
Так що 161 <164, і кожен елемент в лівому з 161
Також <164, так що ми знаємо, що це не допоможе нам на всіх
, Щоб почати шукати тут, тому що елемент ми шукаємо не може бути там.
Отже, що ми можемо зробити, ми можемо просто забути про те, що вся ліва половина списку,
а тепер розглядати тільки з правої з 161 і далі.
>> Отже, ще раз, це середина, давайте просто округлити.
Зараз 175 є надто великою.
Отже, ми знаємо, що це не допоможе нам шукати тут або тут,
тому ми можемо просто кинути, що далеко, і в підсумку ми потрапили в 164.
Будь-які питання по двійкового пошуку?
Давайте перейдемо від пошуку в уже відсортований список
насправді приймає список чисел в будь-якому порядку
і зробити цей список в порядку зростання.
Перший алгоритм ми дивилися на називалося бульбашкового сортування.
І це буде набагато простіше алгоритмів, які ми бачили.
Bubble роду говорить, що коли будь-які 2 елементи всередині списку не на місці,
тобто є більше число зліва від меншого числа,
Потім ми збираємося поміняти їх місцями, тому що це означає, що список буде
"Більш впорядковані", ніж це було раніше.
І ми просто будемо продовжувати цей процес знову і знову, і знову
поки в кінці кінців елементів виду міхур на їх правильне розташування і у нас є відсортований список.
>> Час виконання цього буде O (N ²). Чому?
Ну, тому що в гіршому випадку, ми збираємося взяти кожен елемент, і
ми збираємося в кінцевому підсумку, порівнюючи її з будь інший елемент у списку.
Але в кращому випадку, у нас є вже відсортований список, бульбашкового сортування в
тільки збирається пройти один раз, сказати: "Ні. Я не робив ніяких свопів, так що я зробив".
Отже, ми маємо кращому випадку час роботи Ω (N).
Давайте запустимо бульбашкового сортування в списку.
Чи спочатку, давайте просто подивимося на деякі псевдокод дуже швидко.
Ми хочемо сказати, що ми хочемо відслідковувати, в кожній ітерації циклу,
відслідковувати чи ми змінили небудь елементи.
Таким чином, причина цього в тому, що ми збираємося зупинитися, коли ми не помінялися місцями будь-які елементи.
Таким чином, на початку нашого циклу ми не помінялися місцями нічого, тому ми будемо говорити, що це брехня.
Тепер, ми збираємося пройтися за списком і порівняти елемента до елемента я я + 1
і якщо це так, що є більше число зліва від меншого числа,
Потім ми тільки збираємося, щоб поміняти їх місцями.
>> І тоді ми будемо пам'ятати, що ми помінялися місцями елемент.
Це означає, що ми повинні йти за списком, принаймні, ще 1 раз
тому що стан, в якому ми зупинилися, коли весь список вже відсортований,
означає, що ми не зробили ніяких свопів.
Так ось чому наші умови тут є «в той час як деякі елементи були замінені.
Отже, тепер давайте подивимося на це працює на список.
У мене є список 5,0,1,6,4.
Bubble роду збирається почати весь шлях зліва, і це буде для порівняння
я елементів, так від 0 до + 1, яке є елементом 1.
Він скаже, ну 5> 0, але прямо зараз 5 знаходиться зліва,
так що мені потрібно поміняти місцями 5 і 0.
Коли я поміняти їх місцями, раптом я отримую це інший список.
Зараз 5> 1, так що ми збираємося поміняти їх місцями.
5 не> 6, тому ми не повинні нічого робити тут.
Але 6> 4, так що ми повинні поміняти.
Знову ж таки, нам потрібно запустити весь список, щоб врешті-решт виявити
що ці вийшли з ладу, ми поміняти їх місцями,
і в цей момент нам потрібно запустити через список ще 1 раз
щоб переконатися, що все в його розпорядженні, і в цей момент бульбашкового сортування закінчений.
Різних алгоритмів для прийняття деяких елементів і сортування них є вибір роду.
Ідея вибору роду є те, що ми збираємося побудувати відсортований частину списку
1 елемент одночасно.
>> І те, як ми збираємося зробити це шляхом створення лівій частині списку.
А в принципі, кожен - на кожному кроці, ми збираємося взяти найменший елемент ми залишили
, Які не були відсортовані ще, і ми збираємося, щоб перемістити його в це відсортований сегменті.
Це означає, що ми повинні постійно знаходити мінімальний елемент несортовані
, А потім прийняти, що мінімальний елемент і поміняти його з тим, що
лівий елемент, який не сортується.
Час виконання цього буде O (N ²), тому що в гіршому випадку
ми повинні порівняти кожен елемент будь інший елемент.
Тому що ми говоримо, що якщо ми почнемо в лівій половині списку, ми повинні
пройти через весь правий сегмент, щоб знайти найменший елемент.
А потім, знову ж таки, ми повинні йти протягом всього правого сегмента і
продовжувати над цим знову і знову, і знову.
Це буде п ². Ми збираємося потрібно цикл всередині іншого циклу
що свідчить про п ².
У кращому випадку думка, скажімо, ми даємо йому вже відсортований список;
ми насправді не роблять краще, ніж ² н.
Тому що вибір роду не має можливості дізнатися, що
мінімальний елемент тільки один я, трапляється, дивиться.
Він як і раніше повинен переконатися, що це дійсно мінімум.
>> І єдиний спосіб, щоб переконатися, що це мінімум, за допомогою цього алгоритму,
, Щоб дивитися на кожен окремий елемент знову.
Так насправді, якщо ви даєте йому - якщо ви дасте вибір роду вже відсортований список,
він не збирається робити краще, ніж дати йому список, що не відсортований ще немає.
До речі, якщо воно відбудеться, буде випадок, що щось O (щось)
і омега-то, ми можемо тільки сказати, більш коротко, що це θ чогось.
Так що якщо ви бачите, що придумати в будь-якому місці, це те, що це просто означає.
>> Якщо щось тета-н ², це і велика O (N ²) і Ω (N ²).
Так кращому випадку, а гіршому випадку, це не робить різниці,
Алгоритм збирається зробити те ж саме кожного разу.
Так це те, що псевдокод для вибору роду могла б виглядати.
Ми в основному будемо говорити, що я хочу пройти за списком
зліва направо, і на кожній ітерації циклу, я збираюся переїхати
мінімальний елемент у цій відсортовані частину списку.
І як тільки я переходжу щось там, я ніколи не повинні дивитися на цей елемент знову.
Тому що як тільки я поміняти елемент в лівій частині списку, це відсортований
тому що ми робимо все, що в порядку зростання з використанням мінімуму.
Тому ми сказали, добре, що ми в положенні я, і ми повинні дивитися на всі елементи
праворуч від мене, щоб знайти мінімум.
Таким чином, це означає, що ми хочемо дивитися з г + 1 в кінець списку.
І тепер, якщо елемент, який ми в даний час дивимося на це менше, ніж наші мінімальні досі,
який, пам'ятайте, що ми починаємо з мінімальним просто бути
будь-якого елемента ми в даний час, я буду вважати, що це мінімум.
Якщо я знайду елемент, який менше, ніж це, то я буду говорити, ладно,
Ну, я знайшов новий мінімум.
Я буду пам'ятати, де що було мінімальним.
>> Так що тепер, коли я пройшов через це право несортовані сегменті,
Я можу сказати, що я збираюся поміняти місцями мінімальний елемент з елементом, який знаходиться в положенні я.
Це збирається побудувати мій список, відсортований моєї частині списку зліва направо,
і ми ніколи не повинні дивитися на елемент знову, як тільки вона в цій частині.
Як тільки ми змінив його.
Так що давайте працювати вибір роду в цьому списку.
Сині елементом тут буде я, а червоний елемент буде мінімальним елементом.
Так що я все починається шлях в лівій частині списку, так на 5.
Тепер нам потрібно знайти мінімум несортовані елемент.
Тому ми говоримо, 0 <5, так що 0 є мій новий мінімум.
>> Але я не можу зупинитися, тому що навіть якщо ми можемо визнати, що 0 є найменшим,
нам потрібно запустити через будь-який інший елемент списку, щоб переконатися.
Таким чином, 1 більше, 6 більше, 4 більше.
Це означає, що після того, дивлячись на всі ці елементи, я визначали 0 є найменшим.
Так що я збираюся поміняти 5 і 0.
Одного разу я поміняти, що я збираюся отримати новий список, і я знаю, що я ніколи не потрібно дивитися на що 0 раз
тому що як тільки я змінив його, я залагодив його, і ми зробили.
Тепер так уже сталося, що синій елемент знову 5,
і ми повинні дивитися на 1, 6 і 4, щоб визначити, що 1
є найменшим мінімальним елементом, тому ми переставляємо 1 і 5.
Знову ж таки, ми повинні дивитися на - порівняти від 5 до 6 і 4,
і ми збираємося поміняти 4 і 5, і, нарешті, порівняти
ці 2 номери і поміняти їх місцями, поки ми не отримаємо наші відсортований список.
Будь-які питання по вибору роду?
Добре. Давайте перейдемо до останньої теми тут, і це рекурсія.
>> Рекурсія, пам'ятайте, що це дійсно мета річ, де функція
неодноразово називає себе.
Так що в якийсь момент, у той час як наші Fuction неодноразово називає себе,
там має бути якийсь точці, в якій ми перестати називати себе.
Тому що якщо ми не зробимо цього, то ми просто будемо продовжувати робити це вічно,
і наша програма просто не буде припинятися.
Ми називаємо цей стан базового варіанту.
І базовий варіант, говорить, замість виклику функції знову,
Я просто хочу повернути деяке значення.
Тому, як тільки ми повернулися значення, ми перестали називати себе,
і інші виклики ми зробили до сих пір можна повернути.
На противагу базу випадку є рекурсивним випадку.
І це, коли ми хочемо зробити ще один виклик функції, які ми в даний час дюйма
І ми, ймовірно, хоча і не завжди, хочуть використовувати різні аргументи.
>> Так що, якщо у нас є функція під назвою F і F щойно подзвонив приймати по 1 аргумент,
і ми просто дзвонять F (1), F (1), F (1), і так вже сталося, що
аргумент 1 потрапляє в рекурсивному випадку, ми ще жодного разу не збирається зупинятися.
Навіть якщо у нас є базовий варіант, ми повинні переконатися, що в кінцевому рахунку ми збираємося вдарити, що базовий варіант.
Ми не просто зберегти, що проживають в цьому випадку рекурсивної.
Взагалі, коли ми називаємо себе, ми, ймовірно, будемо мати інший аргумент кожен раз.
Ось дуже простий рекурсивної функції.
Так що це буде обчислити факторіал числа.
До початку тут ми маємо нашу базу випадку.
У випадку, коли п ≤ 1, ми не будемо називати факторіальних знову.
Ми збираємося зупинятися, ми просто збираємося повернути деяке значення.
Якщо це не так, то ми збираємося вдарити нашому випадку рекурсивної.
Зауважте, що тут ми не просто викликом факторіал (п), тому що це було б дуже корисно.
Ми будемо називати факторіал щось інше.
>> І тому ви можете побачити, в кінці кінців, якщо ми передамо факторіал (5) або щось,
ми будемо називати факторіал (4) і так далі, і в кінці кінців ми збираємося вдарити цю базу випадку.
Таким чином, це добре виглядає. Давайте подивимося, що відбувається, коли ми реально працювати це.
Це стека, і давайте скажемо, що основним буде викликати цю функцію з аргументом (4).
Тому, як тільки бачить і факторіал = 4, факторний буде називати себе.
Тепер, раптом, у нас є факторіал (3).
Таким чином, ці функції буде продовжувати рости, поки врешті-решт ми потрапили нашу базу випадку.
На даний момент, повертаним значенням цього є повернення (NX значення, що повертається цього),
повертаним значенням цього NX значення, що повертається цьому.
В кінцевому рахунку ми повинні вразити деяке число.
У верхній тут, ми говоримо, повертає 1.
Це означає, що, коли ми повернемося це число, ми можемо поп цьому з стека.
Так що це факторіал (1), то зроблено.
Коли 1 повертається, це факторіал (1) повертається, це повернення до 1.
Значенням цього, пам'ятаю, був NX значення, що повертається цьому.
Так несподівано, цей хлопець знає, що я хочу повернути 2.
>> Так що пам'ятайте, повернути значення це просто NX значення, що повертається тут.
Так що тепер ми можемо сказати, 3 х 2 і, нарешті, тут ми можемо сказати,
це просто буде 4 х 3 х 2.
І як тільки це повертається, ми спускаємося до одного всередині цілого основний.
Будь-які питання по рекурсії?
Добре. Таким чином, є більше часу на питання в кінці,
але тепер Джозеф покриє залишилися питання.
>> [Джозеф Ong] Все в порядку. Так що тепер ми говорили про рекурсії,
Давайте трохи поговоримо про те, що злиття сортування.
Злиття роду в основному інший спосіб сортування списку чисел.
І як це працює, з сортування злиттям у вас є список, і те, що ми робимо,
ми говоримо, давайте розділити це на 2 половинки.
Ми спочатку запустити сортування злиттям знову на лівій половині,
Потім ми запустимо сортування злиттям на правій половині,
і це дає нам зараз 2 половинки, які сортуються, і тепер ми збираємося об'єднати ці половинки разом.
Це трохи важко зрозуміти без прикладу, тому ми будемо проходити через рухи і подивитися, що відбувається.
Таким чином, ви починаєте з цього списку, ми розділили його на 2 половинки.
Ми проводимо сортування злиттям на лівій половині першого.
Так от ліву половину, і тепер ми пропустити їх через цей список ще раз
який передається в сортування злиттям, а потім ми подивимося, знову ж таки,
в лівій частині цього списку, і ми побігли сортування злиттям на ньому.
Тепер ми перейдемо до списку з 2 цифр,
і тепер ліва половина всього 1 елемент довгий, і ми не можемо
розділити список, в якому тільки 1 елемент у половину, так що ми просто скажемо, раз у нас є 50,
який знаходиться всього в 1 елемент, він вже відсортований.
>> Як тільки ми закінчимо з цим, ми бачимо, що ми можемо
перейти на праву половину цього списку,
і 3 також сортуються, і тому зараз, що обидві половини цього списку сортуються
ми можемо об'єднати ці цифри разом.
Таким чином, ми дивимося на 50 і 3, 3 менше, ніж 50, тому він іде в перший і потім 50 приходить дюйма
Тепер це буде зроблено, ми повернемося до цього списку і сортування це права половина.
42 є його власний номер, так що це вже відсортовані.
Отже, тепер ми порівняємо ці 2 і 3 менше, ніж 42, так що отримує покласти в першому,
тепер 42 отримує покласти в, і 50 отримує вставив
Так от, це впорядковані, ми пройти весь шлях наверх, 1337 і 15.
Ну, ми зараз подивимося на ліву половину цього списку; 1337 сама по собі так що він сортується і те ж саме з 15.
Так що тепер ми об'єднаємо ці 2 номери для сортування, що первісний список, 15 <1337,
тому вона йде в перший, то 1337 йде дюйма
А тепер сортуються обидві половинки вихідного списку нагорі.
І все, що нам потрібно зробити, це об'єднати ці.
Ми дивимося на перші 2 номери з цього списку, 3 <15, тому вона йде в сортування масиву в першу чергу.
15 <42, тому вона йде дюйма Тепер, 42 <1337, який йде дюйма
50 <1337, тому вона йде дюйма І зауважив, що ми просто взяли 2 номери з цього списку.
Таким чином, ми не тільки чергуючи 2 списку.
Ми просто дивлячись на початок, і ми беремо елемент
от і менше, а потім покласти його в наш масив.
Тепер ми об'єдналися всі половинки, і ми зробили.
>> Будь-які питання про злиття роду? Так?
[Студент] Якщо це розщеплення в різних групах, чому вони не просто розділити його один раз
і у вас є 3 і 2 в групі? [Інші питання нерозбірливо]
Причина - так що питання в тому, чому ми не можемо просто об'єднати їх в той перший крок після того, як вони у нас є?
Тому ми можемо зробити це, почніть з самого лівого елементи з обох сторін,
, А потім взяти поменше і поклав його в тому, що ми знаємо, що ці
окремі списки в відсортованому замовлень.
Так що, якщо я дивлюся на самий лівий елементи обох половин,
Я знаю, що вони збираються бути найдрібніших елементів з цих списків.
Так що я можу покласти їх в місцях найменшого елемента цього великого списку.
З іншого боку, якщо я дивлюся на ці 2 списку другого рівня там,
50, 3, 42, 1337 і 15, тим не сортуються.
Так що, якщо я дивлюся на 50 і 1337, я збираюся поставити 50 в моєму списку першим.
Але це не має сенсу, так як 3 найменший елемент з усіх з них.
Таким чином, єдина причина, ми можемо зробити це об'єднання крок, тому що наші списки вже відсортовані.
Саме тому ми повинні спускатися на всьому шляху до дна
тому що, коли у нас є тільки одне число, ви знаєте, що один номер
саме по собі вже є відсортований список.
>> Є питання? Ні?
Складність? Ну, ви бачите, що на кожному кроці є кінець числа,
і ми можемо розділити список журналу 1/2 п раз,
де ми одержимо цей журнал п х п складності.
І ви побачите, в кращому випадку для сортування злиттям п § п, і так уже сталося,
, Що в гіршому випадку, або Ω там, також п п увійти.
Потрібно мати на увазі.
Рухаємося далі, давайте перейдемо до деяких супер основний файл I / O.
Якщо ви подивитеся на Scramble, ви помітите, у нас була якась система
де ви могли б написати в лог-файл, якщо ви читаєте по коду.
Давайте подивимося, як ви могли б зробити це.
Ну, у нас Fprintf, які ви можете думати, як тільки Printf,
але тільки друк у файл, а й, отже, F на самому початку.
Такий код тут, що він робить, як ви, можливо, бачили в Scramble,
вона проходить через вашу 2-мірний масив з друку ряд за рядом, що числа.
У цьому випадку Виводить на ваш термінал або що ми називаємо стандартний вивід розділі.
>> І тепер, в цьому випадку, все, що ми повинні зробити, це замінити Printf з Fprintf,
сказати йому, що файл, який ви хочете друкувати, і в цьому випадку він просто виводить її на цей файл
замість того, щоб друкувати його на термінал.
Ну, те, що напрошується питання: Де ж взяти такого роду файлів з, вірно?
Ми пройшли увійти в цю Fprintf Fuction але ми поняття не мав, звідки воно взялося.
Ну, на самому початку коду, те, що ми мали, був цей шматок коду сюди,
, Який в основному говорить, що відкрити файл викликає log.txt.
Що ми робимо після цього, що ми повинні переконатися, що файл насправді був успішно відкритий.
Так що, можливо, не з кількох причин, вам не вистачає місця на вашому комп'ютері, наприклад.
Таким чином, це завжди важливо, перш ніж робити будь-які операції з файлами
що ми перевіряємо, що файл був відкритий успішно.
Так що це, це аргумент Еореп, добре, ми можемо відкрити файл по-різному.
Що ми можемо зробити, ми можемо передати його вага, а значить змінити файл, якщо він виходить вже,
Ми можемо передати, що вони додаємо в кінець файлу, а не перекриваючи його,
або ми можемо вказати R, що означає, давайте відкрити файл лише для читання.
Таким чином, якщо програма намагається внести зміни в файл,
кричати на них і не дозволяють їм це зробити.
Нарешті, коли ми закінчили з файлом, зробив роблять операції на ній,
Ми повинні переконатися, що ми закриваємо файл.
І ось в кінці вашої програми, ви збираєтеся передати їх знову
це файл, який ви відкрили, і просто закрити його.
Так що це щось важливе, що ви повинні переконатися, що ви робите.
Так що пам'ятайте, що ви можете відкрити файл, то ви можете записати у файл,
робити операції у файлі, але тоді ви повинні закрити файл в кінці.
>> Будь-які питання по основним файлу I / O? Так?
[Студент питання, нерозбірливо]
Прямо тут. Питання в тому, де ж цей файл log.txt з'являються?
Ну, якщо ви просто дати йому log.txt, він створює його в тому ж каталозі, що і виконуваний файл.
Так що, якщо ви - >> [Студентський питання, нерозбірливо]
Так. У тій же папці, або в тому ж каталозі, як ви це називаєте.
Тепер пам'ять, стек та купу.
Так, як це пам'ять, викладених у комп'ютері?
Ну, ви можете собі пам'ять як свого роду цьому блоці тут.
І в пам'яті у нас є те, що називається купою застрягли там, і стек, що там внизу.
І купа росте вниз, а стек росте вгору.
Так як Томмі згадував, - про, добре, і у нас є ці інші 4 сегментів, які я отримаю в секунду -
Як сказав Томмі раніше, ви знаєте, як його називають себе функції і називають один одного?
Вони створюють такого роду кадру стека.
Ну, якщо основні виклики Фу, Фу отримує покласти в стек.
Foo називає, бар отримаєте поставимо в стек, і що отримує покласти в стек після.
І коли вони повернуться, кожна з них отримують зняти стек.
Що кожен з цих місць і пам'ять тримати?
Ну, верхній, який є сегмент тексту, містить саму програму.
Таким чином, машинний код, що там, як тільки ви скомпілювати програму.
Далі, будь ініціалізувалися глобальні змінні.
>> Таким чином, у Вас є глобальні змінні у вашій програмі, а ви говорите, як, = 5,
, Який отримує покласти в цьому сегменті, і прямо під цим,
у вас є якісь неініціалізовані глобальні дані, які просто INT,
але ви не кажу, що це однаково нічого.
Зрозумійте, це глобальні змінні, так що вони за межами основного.
Таким чином, це означає, що будь-які глобальні змінні, які оголошені, але не ініціалізуються.
Так що в купі? Пам'ять розподіляється за допомогою Танос, який ми отримаємо в трохи.
І, нарешті, зі стеком у вас є якісь локальні змінні
і будь-якої функції можна викликати в будь-який з їхніх параметрів.
Остання річ, ви дійсно не повинні знати, що змінні оточення робити,
але всякий раз, коли ви запускаєте програму, є щось пов'язане, як
це ім'я користувача, який запустив програму.
І це буде як би на дні.
З точки зору адреси пам'яті, які є шістнадцяткові значення,
Значення у верхній починаються з 0, і пройти весь шлях до дна.
У цьому випадку, якщо ви знаходитесь на 32-бітної системі,
адресою, вказаною внизу буде 0x, а потім А.Ф., тому що це 32 біт,
, Що на 8 байт, і в цьому випадку 8 байт відповідає 8 шістнадцятирічних цифр.
Так що тут ви будете мати, начебто, 0xffffff, і там ви будете мати 0.
Так що покажчики? Деякі з вас, можливо, не покриті цим в розділі раніше.
але ми не вдаватися в лекції, тому покажчик просто тип даних
які магазинах, а не якесь значення, наприклад 50, вона зберігає адресу певне місце в пам'яті.
Як і що пам'ять [нерозбірливо].
Таким чином, в даному випадку, те, що ми є, ми маємо покажчик на ціле або ціле число *,
і містить цьому шістнадцятковий адресу 0xDEADBEEF.
>> Отже, що ми маємо зараз, цей покажчик вказує на певне місце в пам'яті,
і це тільки, значення 50 в це розташування в пам'яті.
На деяких 32-бітних системах, на всіх 32-бітових систем, покажчики займають 32 біта або 4 байти.
Але, наприклад, на 64-бітної системі, покажчики є 64-бітними.
Так що те, що ви хочете, щоб тримати в голові.
Таким чином, на кінець-бітної системи, покажчик кінця біт.
Покажчики є свого роду важко переварити без додаткових речей,
так давайте пройдемо приклад динамічного розподілу пам'яті.
Що динамічного розподілу пам'яті робить для вас, або те, що ми називаємо Танос,
вона дозволяє виділити якийсь даних за межами знімального майданчику.
Таким чином, ці дані є свого роду більш постійним протягом всього терміну програми.
Тому що, як ви знаєте, якщо ви оголосите х всередині функції, а функція повертає значення,
Вам більше не мають доступу до даних, які зберігаються в х.
Що покажчики будемо робити, вони дозволяють нам зберігати пам'ять або зберігають значення
в інший сегмент пам'яті, а саме в купу.
Тепер, коли ми повернемося з функцій тих пір, поки у нас є покажчик
в те ж місце в пам'яті, то, що ми можемо зробити, ми можемо просто дивитися на значення там.
Давайте подивимося на прикладі: Це наша пам'ять макет знову.
І у нас є ця функція, основною.
Що вона робить це - добре, так просто, правда? - Int х = 5, от тільки на стеці в головному.
>> З іншого боку, тепер ми оголошуємо покажчик, який викликає функцію giveMeThreeInts.
І ось тепер ми йдемо в цю функцію, і ми створюємо новий кадр стека для нього.
Однак, в цьому кадрі стека, ми заявляємо Int * температура,
який в mallocs 3 цілих для нас.
Таким чином, розмір Int дасть нам скільки байт цьому Int є,
і Танос дає нам, що багато байт простору в купі.
Таким чином, в цьому випадку, ми створили достатньо місця для 3 числа,
і купа шлях там, тому я намалював її вище.
Як тільки ми закінчимо, ми повернемося сюди, вам потрібно всього лише 3 цілими повернулися,
і вона повертає адресу, в даному випадку над тим, де ця пам'ять.
І ми поставили покажчик = вимикач, і там у нас є ще один покажчик.
Але те, що ця функція повертає укладається тут і зникає.
Таким чином, темп зникає, але ми як і раніше підтримують адреси, де
ці 3 числа знаходяться всередині мережі.
Таким чином, в цьому наборі, покажчики областю на місцевому рівні для складених кадрів,
але пам'ять до яких вони відносяться до купи.
>> Чи має це сенс?
[Студент] Не могли б ви повторити? >> [Йосип] Так.
Так що, якщо я повернуся трохи, ви бачите, що температура виділено
деякий обсяг пам'яті в купі там.
Тому, коли ця функція, giveMeThreeInts повертається, цей стек тут збирається зникати.
А разом з нею будь-який з змінних, в даному випадку, це покажчик, який був виділений в стек кадру.
Тобто зникне, але так як ми повернулися температура
і ми покажчика = температура, покажчик тепер буде вказувати ту ж саму згадку про місце, темп був.
Так що тепер, навіть якщо ми втратимо темп, що місцеві покажчик,
Ми як і раніше зберігають адресу пам'яті, що він був спрямований всередину цієї змінної покажчик.
Питання? Це може бути навіть заплутаною теми, якщо ви не перейшли в розділі.
Ми можемо, ваш TF виразно піде на це і, звичайно, ми можемо відповісти на питання
В кінці сесії з огляду для цього.
Але це свого роду складне питання, і у мене є інші приклади, які збираються, щоб показати
, Яка допоможе прояснити, що покажчики на самом деле.
>> У цьому випадку, покажчиків еквівалентно масивів,
так що я можу просто використовувати цей покажчик, як те ж саме, Int масиву.
Так що я індексації в 0, і зміна перше число 1,
зміна другого числа 2, і 3-й ціле число 3.
Так що більше на покажчики. Ну, згадайте Бінки.
У цьому випадку ми виділили покажчик, або ми оголосили покажчик,
але спочатку, коли я тільки що оголосили покажчик, це не вказує на будь пам'яті.
Це просто сміття значення всередині нього.
Так що я поняття не маю, де цей покажчик вказує.
Він має адресу, що просто наповнений 0 і 1, де він був спочатку оголошений.
Я нічого не можу зробити з цим, поки я називаю Танос на неї
і це дає мені мало місця в купі, де я можу поставити значення всередині.
Знову ж таки, я не знаю, що всередині цієї пам'яті.
Тому перше, що я повинен зробити, це перевірити, чи є система мала досить пам'яті
, Щоб дати мені назад 1 ціле, в першу чергу, тому я роблю це перевірити.
Якщо покажчик порожній, це означає, що у нього не було достатньо місця, або інші помилки,
так що я повинен вийти з моєї програми.
Але якщо це і не вдалося, тепер я можу використовувати цей покажчик
і те, що * покажчик робить це таким де адресу
де це значення, і це відрізняє його рівним 1.
Так що тут, ми перевіряємо, якщо що пам'ять існує.
>> Коли ви знаєте, вона існує, ви можете помістити в неї
Яке значення ви хочете вкласти в неї, в цьому випадку 1.
Як тільки ми покінчимо з цим, необхідно, щоб звільнити цей покажчик
тому що ми повинні повернутися до системи, пам'яті, які ви просили в першу чергу.
Оскільки комп'ютер не знає, коли ми покінчимо з цим.
У цьому випадку ми явно говорить він, добре, ми закінчили з цією пам'яттю.
Якщо деякі інші процеси в ній потребує, деякі інші програми в ній потребує, не соромтеся йти вперед і приймати його.
Що ми можемо зробити, це ми можемо просто отримати адресу локальних змінних на знімальному майданчику.
Так Int х знаходиться всередині складені рамках основної.
І коли ми використовуємо цей символ, це і оператора, що вона робить це
він приймає х, і х лише деякі дані в пам'яті, але в нього є адреса.
Вона знаходиться десь. Так, подзвонивши по телефону і х, те, що це робить він дає нам за адресою х.
Роблячи це, ми робимо покажчик точки, де х знаходиться в пам'яті.
Тепер ми просто зробити щось подібне * х, ми збираємося, щоб отримати 5 тому.
Зірка називається разименованія його.
Ви прямуєте адресу, і ви отримаєте значення вона зберігається там.
>> Є питання? Так?
[Студент] Якщо ви цього не зробите 3-загострені річ, це все ще скомпілювати?
Так. Якщо ви цього не зробите 3-покажчик річ, вона як і раніше буде становити,
Але я покажу вам, що відбувається в секунду, а без цього,
це те, що ми називаємо витоком пам'яті. Ви не даєте системі
Резервне його пам'яті, так що через деякий час програма буде накопичуватися
пам'ять, що вона не використовується, і ніщо інше не може його використовувати.
Якщо ви коли-небудь бачили Firefox з 1,5 мільйона кілобайт на вашому комп'ютері,
в диспетчері завдань, ось що відбувається.
У вас є витоку пам'яті в програмі, що вони не обробляє.
Так як же арифметика покажчиків роботи?
Ну, арифметика покажчиків ніби як індексація в масиві.
У цьому випадку, у мене є покажчик, і те, що я роблю, я роблю покажчик вказує на перший елемент
цього масив з 3 цілих чисел, які я виділив.
Так що тепер мені робити, зірка просто змінює покажчик на перший елемент у списку.
Зірка покажчик +1 очок тут.
Таким чином, покажчик миші тут, +1 є покажчиком тут, покажчик +2 є тут.
>> Так що додавання 1, те ж саме, рухаючись по цьому масиву.
Що ми робимо, коли ми робимо покажчик +1 Ви отримаєте адресу тут,
і для того, щоб отримати значення тут, ви поклали зірку в від всього виразу
Звертатися до них.
Таким чином, в даному випадку, я встановлюю перше місце в цьому масиві в 1,
Друге місце 2, а третє місце на 3.
Потім, що я роблю тут є я друкую наш покажчик +1,
який просто дає мені 2.
Тепер я збільшуючи покажчик, тому покажчик одно покажчик +1,
, Яка рухається вперед.
І ось тепер, якщо я роздрукувати покажчик +1, покажчик +1 тепер 3,
який в даному випадку виводить 3.
І для того, щоб щось безкоштовно, покажчик, який я даю йому
повинні бути спрямовані на початок масиву, який я повернувся з Танос.
Таким чином, в даному випадку, якщо б я був дзвонити 3 прямо тут, це було б неправильно,
тому що це в середині масиву.
Я повинен відняти, щоб отримати на колишньому місці
початкова першому місці перш ніж я зможу звільнити його.
Отже, ось більш складний приклад.
У цьому випадку, ми виділенні 7 символів в масив символів.
>> І в цьому випадку те, що ми робимо, ми циклів протягом перших 6 з них,
і ми встановлюємо їх в Z.
Таким чином, для Int я = 0, г> 6, я + +,
Таким чином, покажчик + Я просто дати нам, в даному випадку,
покажчик, покажчик +1, +2 покажчик, покажчик +3, і так далі, і так далі в циклі.
Що він збирається робити це отримує, що адреса, разименовивает його, щоб отримати значення,
і зміни, значення Z.
Потім, в кінці пам'ятайте, що це рядок, чи не так?
Всі рядки повинні закінчити з нульовою символ завершення.
Отже, що я роблю, це покажчик в 6 я поставив порожній символ кінця дюйма
А тепер те, що я в основному роблю тут реалізується Printf для рядка, чи не так?
>> Отже, коли ж Printf тепер, коли вона досягла кінця рядка?
Коли вона знизиться до нульової символ завершення.
Таким чином, в даному випадку, мої вихідні точки, покажчик на початок цього масиву.
Я надрукувати перший символ з. Я перемістити його на один.
Я друкую цей символ з. Я рухаюся його.
І я продовжую робити це, поки я дійти до кінця.
А тепер покажчик кінця * буде разименовать і отримати нульовий завершальний символ назад.
І тому моя в той час як цикл виконується тільки тоді, коли це значення не є нульовий символ завершення.
Отже, тепер я вийти з цієї петлі.
І тому, якщо я відняти 6 з цього покажчика,
Я повертаюся весь шлях з самого початку.
Пам'ятаєте, я роблю це тому, що я повинен піти до початку, щоб звільнити його.
>> Так от, я знаю, що було багато. Чи є запитання?
Будь ласка, да?
[Студент питання нерозбірливо]
Чи можете ви сказати, що голосніше? Вибачте.
[Студент] На останньому слайді право, перш ніж звільнити покажчик,
де ви були насправді змінити значення покажчика?
[Джозеф] Так, прямо тут. >> [Студент] О, все в порядку.
[Джозеф] Отже, у мене є покажчик мінус мінус, право,
який переміщує речі назад на один, а потім звільнити його,
тому що цей покажчик повинен бути вказала на початок масиву.
[Студент] Але це був би не потрібен, якщо б ви зупинилися після цього рядка.
[Джозеф] Так що, якщо я зупинився після цього, це буде розглядатися як витік пам'яті,
тому що я не запустити безкоштовний.
[Студент] Я [нерозбірливо] після перших трьох лініях, де ви були покажчика +1 [нерозбірливо].
[Джозеф] Угу. Так, що питання там?
Вибачте. Ні, ні. Іди, іди, будь ласка.
[Студент] Таким чином, ви не змінивши значення покажчиків.
Ви не повинні були б зробити покажчик мінус мінус.
[Джозеф] Так, саме так.
Так що, коли я роблю покажчик та покажчик +1 +2,
Я не роблю покажчика одно покажчик +1.
Таким чином, покажчик залишається тільки вказує на початок масиву.
І тільки коли я роблю плюс плюс, що він встановлює значення назад в покажчик,
що він фактично рухається вздовж цього.
Добре.
Ще питання?
>> Знову ж таки, якщо це є свого роду переважною, це будуть розглянуті на сесії.
Попросіть вашого навчання колег про це, і ми можемо відповісти на питання в кінці.
І звичайно ми не хотіли робити це мінус річ.
Це повинно вимагають від мене відстежувати, наскільки я Зсув у масиві.
Так, загалом, це просто пояснити, як працює арифметика покажчиків.
Але те, що ми зазвичай подобається робити, ми хотіли б створити копію покажчика,
і тоді ми будемо використовувати цю копію, коли ми рухаємося навколо в рядок.
Таким чином, в цих випадку якщо ви використовуєте копії надрукувати весь рядок,
але ми не повинні робити, як покажчик мінус 6 або відслідковувати, скільки ми переїхали в це,
тільки тому, що ми знаємо, що наша вихідна точка і раніше вказує на початок списку
і все, що ми змінили ця копія.
Так, загалом, змінювати копії оригінальних покажчик.
Не намагайтеся щось подібне - don't змінити примірниках.
Спроба змінити тільки копії оригіналу.
Таким чином, ви помітите, коли ми передаємо рядок в Printf
Ви не повинні помістити зірку перед ним, як ми робили з усіма іншими разименовивает, вірно?
Так що, якщо ви друкуєте з усієї рядки з% очікує, що це адреса,
і в цьому випадку покажчик або в даному випадку, як масив символів.
>> Персонажі, символ * с, і масиви одне і те ж.
Покажчик складається в символи і символьні масиви одне і те ж.
А так, все, що ми повинні зробити, це передати в покажчик.
Ми не повинні проходити в як покажчик * або щось подібне.
Таким чином, масиви і покажчики одне і те ж.
Коли ви робите щось подібне X [Y] тут для масиву,
що він робить під капотом це говорить, добре, що це масив символів,
так що це покажчик.
І тому х одне і те ж,
і так, що він робить це додає г х,
що те ж саме, що рухатися вперед в пам'яті, що багато.
А тепер х + у дає нам якусь адресу,
і ми разименовать адресу або стежити за стрілками
де це місце в пам'яті, і ми отримаємо значення з цього місця в пам'яті.
Таким чином, так що ці дві точно такі ж речі.
Це просто синтаксичний цукор.
Вони роблять те ж саме. Вони просто різні синтактика один для одного.
>> Отже, що може піти не так з покажчиками? Мовляв, багато. Добре. Так, погані речі.
Деякі погані речі, які ви можете зробити, не перевіряючи, якщо ваш Танос виклик повертає нуль, вірно?
У цьому випадку, я прошу системи, щоб дати мені - що це за номер?
Мені подобається 2000000000 разів 4, так як розмір ціле 4 байти.
Я питаю його для як 8 мільярдів байт.
Звичайно, мій комп'ютер не буде в змозі дати мені, що стільки ж назад пам'яті.
І ми не перевірити, якщо це нуль, тому, коли ми намагаємося разименованія його там -
стежити за стрілками, де вона збирається - у нас немає цієї пам'яті.
Це те, що ми називаємо разименованія нульового покажчика.
А це суттєво змушує Вас падати.
Це один із способів сегментації.
Інші погані речі, які ви можете зробити - да ладно.
Це було разименованія нульового покажчика. Добре.
Інші поганих речей - ну, щоб виправити, що ви просто поставте галочку там
, Яка перевіряє, чи є покажчик є нульовим
і вийти з програми, якщо вона трапляється, що Танос повертає нульовий покажчик.
Це XKCD коміксів. Люди розуміють це зараз. На зразок того.
>> Таким чином, пам'ять. І я пішов із цього приводу.
Ми закликаємо Танос в циклі, але кожен раз, коли ми називаємо Танос
ми втрачаємо відстежувати, де цей покажчик вказує на,
тому що ми видаливши його.
Таким чином, початковий виклик Танос дає мені пам'яті тут.
Моя покажчик покажчики на це.
Тепер, я не звільнити його, так що тепер я називаю Танос знову.
Тепер він вказує тут. Зараз в моїй пам'яті вказує тут.
Вказуючи тут. Вказуючи тут.
Але я втратив всі адреси пам'яті тут, що я виділив.
І ось тепер у мене немає ніяких посилань на них більше.
Таким чином, я не можу звільнити їх за межами цього циклу.
І тому для того, щоб виправити щось на зразок цього,
якщо ви забули, щоб звільнити пам'ять, і ви отримаєте цей витік пам'яті,
Ви повинні звільнити пам'ять, всередині цієї петлі, як тільки ви зробили з ним.
Ну, це те, що відбувається. Я знаю, багато хто з вас ненавиджу це.
Але тепер - ура! Ви отримуєте як 44000 кілобайт.
Таким чином, ви звільните його в кінці циклу,
і що збирається просто звільнити пам'ять кожного разу.
По суті, ваша програма не має витоку пам'яті більше.
>> А тепер щось ще, що ви можете зробити, це звільнити частину пам'яті, що ви просили в два рази.
У цьому випадку, ви Танос щось, ви зміните його значення.
Ви звільнити його відразу, тому що ви казали, що зробили з ним.
Але тоді ми звільнили його знову.
Це те, що дуже погано.
Він не збирався спочатку сегментації,
але через деякий час, що це буде подвійне звільнення цієї псує вашу купу структури,
і ви дізнаєтеся трохи більше про це, якщо ви вирішили взяти клас, як CS61.
Але по суті, через деякий час ваш комп'ютер буде заплутатися
про те, що комірки пам'яті, куди і де він зберігається -
де дані зберігаються в пам'яті.
І тому звільнення покажчика двічі це погано, що ви не хочете робити.
>> Інші речі, які можуть піти не так, не використовує SizeOf.
Таким чином, в цьому випадку ви Malloc 8 байт,
і це те ж саме, що і два цілих числа, правильно?
Таким чином, це абсолютно безпечно, але це таке?
Ну, як Лукас говорив про на різних архітектурах,
цілих чисел різної довжини.
Так, на пристрій, який ви використовуєте, цілі близько 4 байти,
але на деяких інших системах вони можуть бути 8 байтів або вони можуть бути 16 байт.
Так що, якщо я просто використовувати цей номер тут,
ця програма може працювати на приладі,
але він не збирається виділити достатньо пам'яті на деякі інші системи.
У цьому випадку, це те, що оператор SizeOf використовується.
Коли ми називаємо SizeOf (INT), що це робить
це дає нам розмір цілого в системі, що програма працює.
Таким чином, в даному випадку, SizeOf (INT) поверне 4 на щось подібне до приладу,
і тепер це буде 4 * 2, що на 8,
, Який є тільки обсяг простору, необхідного для двох цілих чисел.
На іншій системі, якщо Int, як 16 байт або 8 байтів,
це просто збирається повернутися достатньо байта для зберігання цієї суми.
>> І, нарешті, структури.
Так що, якщо ви хочете зберегти судоку дошка в пам'ять, як ми могли б це зробити?
Ви можете уявити собі, як змінної для першою річчю,
змінних для другого річ, змінна третя річ,
Змінна за четвертий річ - погано, вірно?
Так, один поліпшенню ви можете зробити на верхній частині цього зробити 9 х 9 масиву.
Це прекрасно, але що, якщо ви хочете, щоб зв'язати інші речі з дошки судоку
подобається те, що труднощі плати,
або, приміром, що ваш рахунок, і скільки часу це зайняло вам вирішити цю конференцію?
Ну, що ви можете зробити, ви можете створити структури.
Те, що я в основному кажу я визначаю цю структуру тут,
і я визначаю судоку борту якого складається з плати, що становить 9 х 9.
>> І те, що вона у нього є покажчики на ім'я рівні.
Вона також має х і у, які є координатами, де я перебуваю зараз.
Він також час, витрачений [нерозбірливо], і він має загальне число ходів я введені досі.
І тому в даному випадку, я можу згрупувати цілу купу даних в одну структуру
замість того, щоб, як він літає в як різні змінні
що я не можу відслідковувати.
І це дозволяє нам мати просто хороший синтаксис для роду посилання різні речі всередині цієї структури.
Я просто можу зробити board.board, і я отримую судоку дошка тому.
Board.level, я зрозумів, як важко це.
Board.x і board.y дати мені координати, де я міг би бути в раді.
І тому я доступі, що ми називаємо поля в структурі.
Це визначає sudokuBoard, який є типом, який у мене є.
І ось тепер ми тут. У мене є змінна називається "дошка" типу sudokuBoard.
І ось тепер я можу отримати доступ до всіх полів, які складають цю структуру сюди.
>> Будь-які питання про структурах? Так?
[Студент] Для Int х, у, ви оголосили обидві на одній лінії? >> [Йосип] Угу.
[Студент] Таким чином, ви могли б просто зробити це з ними з усіма?
Як і в х, у комою раз, що загальне?
[Джозеф] Так, можна впевнено зробити це, але причина, я поклав х і у на тій же рядку -
і питання в тому, чому ми можемо просто зробити це на тій же лінії?
Чому ми не просто поставити все це на одній лінії
х і у зв'язані один з одним,
і це тільки стилістично більш правильно, в певному сенсі,
тому що це угруповання дві речі, на тій же лінії
що, як і роду відносяться до однієї речі.
І я просто розділити ці частини. Це просто стиль річ.
Це функціонально робить ніякої різниці.
Будь-які інші питання, що стосуються структури?
Ви можете визначити з Pokédex структури.
Покемон має номер і він має листі, власник, тип.
І потім, якщо у вас є масив з покемонів, ви можете скласти Pokédex, вірно?
Добре, прохолодно. Таким чином, питання про структур. Це пов'язано з структурам.
>> Нарешті, GDB. Що GDB дозволяють вам робити? Це дозволяє відлагоджувати вашу програму.
І якщо ви не використовували GDB, я б рекомендував дивитися на короткий
і якраз збирався за те, що GDB є, як ви з ним працювати, як ви можете використовувати його,
і перевірити його на програму.
І те, що GDB дозволяє вам робити це дозволяє призупинити [нерозбірливо] до вашої програми
і практичної лінії.
Наприклад, я хочу, щоб призупинити виконання в рядку 3, як з моєї програми,
і поки я на лінії 3 я можу надрукувати всі значення, які є.
І так, що ми називаємо, як пауза в лінію
це ми називаємо це покласти останову на цій лінії
і тоді ми зможемо роздрукувати змінних на стан програми в той час.
>> Ми можемо потім звідти пройти по програмі лінія за лінією.
І тоді ми можемо подивитися на стан стека в той час.
І так, щоб використовувати GDB, що ми робимо, ми називаємо брязкіт на файл C,
але ми повинні його пройти, ggdb прапор.
І як тільки ми закінчимо з цим, ми просто запустити GDB на результуючий файл виводу.
І тому ви зможете отримати деякі, як маса тексту, як це,
але насправді все, що вам потрібно зробити, це ввести команди на самому початку.
Перерва основні ставить крапку останова на основний.
Список 400 перераховані рядків коду навколо лінії 400.
І тому в цьому випадку ви можете просто подивитися навколо і сказати, ой,
Я хочу, щоб встановити точки зупину в рядку 397, який цю лінію,
і тоді ваша програма працює на такий крок, і він збирається зламати.
Це збирається зробити паузу там, і Ви можете роздрукувати, наприклад, значення низьке або високе.
І так є купа команд, які ви повинні знати,
і це слайд-шоу буде йти на сайт,
так що якщо ви просто хочете, щоб посилання на ці або, як покласти їх на свій шпаргалок, не соромтеся.
>> Cool. Це була вікторина відгук 0, і ми будемо дотримуватися навколо, якщо ви маєте будь-які питання.
Добре.
>> [Оплески]
>> [CS50.TV]