публічний статичний порожній блог ()
Лоток - чудова річ. Ми можемо використовувати його, щоб з’ясувати, чи правильно вираз укладено в дужки:
Наприклад, ця програма Clojure правильно вкладена в дужки:
І це JSON не є:
Простий алгоритм виглядає так:
Ще маргінальні випадки!
- якщо при видаленні дужки з верхньої частини стека ми виявимо, що у нас порожній стек, у нас занадто багато правих дужок (хтось забув згадати ліву дужку).
- якщо ми читаємо всі символи, а стек не порожній, це означає занадто багато лівих дужок. Це більш поширена помилка: це означає, що відсутня якась права дужка.
Для Clojure процедура буде виглядати так:
- символ: (, ми ставимо на стек: (
- символ: [, ми ставимо на стек: [`(
- символ:], витягнути зі стека [, стек: (
- символ: (, ми ставимо на стек: ((
- символ: (, ми ставимо на стек: (((
- символ:), витягніть зі стека (, стек: ((
- символ:), витягніть зі стека (, стек: (
- character:), витягніть його зі стопки (і стек залишиться порожнім.
Давайте подивимось на поганий JSON:
- знак: <, strčíme na štós: `
- символ: [, ми ставимо на стек: [
- символ:>, витягнути з верхньої частини стека]. Однак це не дружні дужки, і ми маємо помилку із занадто великою кількістю лівих дужок.
Підводячи підсумок, нам потрібні три операції від стебла:
- вставте зверху
- вибрати зверху
- і подивіться, чи порожньо
Багато разів проводиться четверта операція:
- милуватися його пагорбом
Англійською мовою операції їм відповідають штовхати (друк), поп (вибрати), зазирнути (заглянути) а порожній (виявлення порожнечі).
І чому вартість? Оскільки він найкраще відповідає стосі паперів, а ще краще - стосі тарілок:
Однак у словацькій мові жоден вчений-інформатик не вживатиме слова štós (хоча у словацького мовного корпусу з цим проблем немає); було використано позначення лоток, очевидно під впливом військової служби:
Ви можете придбати журнал для пістолета-кулемета CZ Scorpion, наприклад, у AFG.sk:
В окремому céčko є дуже мінімалістична бібліотека, і жодного варіанту букв java.util.Stack або Python не існує.
Якщо нам пощастить і ми програмуємо для BSD або Linux, ми можемо скористатися бібліотекою sys/queue.h, а якщо ні, то можемо зробити це по-своєму.
Структури даних
Це стек:
Мабуть повітряні кулі та діти UML не пов'язані з журналом? Навпаки !. Кожна повітряна куля - це предмет пов'язаний список і кожна струна - це не що інше, як спосіб дістатися до наступної повітряної кулі (потягнувши її до руки).
І ми не будемо тримати це в таємниці, кожен рядок представляє вказівник на повітряну кулю, тому що той, хто тримає струну, може вхопити повітряну кулю в її кінці, потягнувши її.
Кожен аеростат має, крім свого кольору, розміру та інших атрибутів (наприклад, тип газу всередині, бо гелій - це весело), рядок для наступного аеростата, тобто також вказівник на аеростат.
У цій аналогії застосовуватиметься таке:
Щаслива дитина може дістатись до першої повітряної кулі завдяки струні, і коли ми дивимось на неї по-іншому, це представляє радісну радість, яка тримає список повітряних куль. (Він може передати ці пакети іншій дитині, якщо це потрібно).
Це призводить до чарівної функції: список повітряних куль можна сплутати з точкою для першої повітряної кулі за бажанням.
Бо той, у кого є струна для першої повітряної кулі, може поступово дістатися до інших.
Але давайте напишемо це на Сі!
Ми представляємо повітряну кулю як структуру, що представляє елемент контейнера. Ми не будемо записувати в стосі ні колір, ні гелій, а лише символи: адже ми не забудемо завдання з початку статті.
Декого турбує те, що елемент структури визначається як складова символу та вказівник на елемент структури, але це нічого особливого: рекурсія є природною властивістю не тільки в математиці.
Не забуваймо включити крапку з комою після фігурної дужки!
У нас є структура даних, і давайте зробимо порожній список! Це буде виглядати так:
Так. Сумно-весела дитина тримає шнурок, але на кінці немає повітряної кулі. Нульові кулі означає порожній список:
Змінна empty_list має тип вказівник на елемент struct (Не забуваємо, це рядок! Рядок - це вказівник!) А оскільки в кінці немає повітряної кулі, ми будемо представляти його за допомогою покажчика NULL.
Не забуваймо також, що "список елементів можна сплутати з вказівником на його перший елемент!" і тому весь перелік складається з елемента структури struct * .
Це нас точно дратуватиме - ці мультианології, про які ми маємо пам’ятати, легко забути.
На щастя, в C ми можемо вказати спеціальні імена типів даних (я прошу псевдоніми, навіть якщо жоден торт так не називає):
У перекладі: відтепер елемент типу структури * структури структури * називається TRAY. (Деякі конвенції C говорять, що типи даних typedef/alias є великими.)
Після редагування програма буде виглядати так:
Порожній контейнер
Наразі нам слід обладнати структури даних, і настав час алгоритмів! Гм, точніше реалізація чотирьох функцій.
Почнемо з найпростішого: з’ясувати, чи лоток порожній. Заголовок функції?
Функція повертає одиницю, якщо лоток порожній, інакше вона повертає нуль. А параметри? Ми можемо із задоволенням подумати про щойно визначений тип даних TRAY, після чого можемо уявити вказівник на перший елемент стека.
Реалізація проста:
Чудово, ми можемо перевірити програму!
Додавання в лоток
Саундтрек цього блоку - Garbage: Push It. За винятком Сміття, можливо, ми додамо розумні речі у верхню частину лотка.
Однак тут алгоритм буде дещо складнішим, оскільки ми повинні дотримуватися основного принципу, граючи з повітряними кульками:
Повітряна куля, яку не тримає жодна рука або не прив'язана до іншої повітряної кулі, буде летіти безповоротно!
Про літаючі кулі ми поговоримо десь пізніше, в C це означає велику галібу.
А тепер уявіть, що Зузанка веде список повітряних куль.
Для персонажа, якого ми додаємо, нам потрібно надути нову повітряну кулю. Хтось повинен буде його потримати (інакше він полетів би, що означає втечу!). Ми кличемо нашого друга Петрика, щоб допомогти йому, і ми даємо йому струну для нової кулі.
Ми будемо надувати динамічно. Ми зарезервуємо місце в пам'яті для елемента списку (елемента структури), отримаємо до нього рядок (тобто покажчик), а потім поговоримо з ним далі.
Функція malloc () виділяє рівно стільки байт пам’яті, скільки займає тип даних елемента структури, як визначається розміром лічильника смуги. Ми поміщаємо вказівник на новий елемент (= рядок для повітряної кулі) в руку допоміжної змінної p ˙.
Боком: якщо будівництво здається дивним, панікувати не потрібно. Якщо ми хочемо виділити пам’ять для одного int, напишемо int * element = malloc (sizeof (int)). Якщо нам потрібна пам’ять на п’ятнадцять символів (тобто 14-значний рядок), char * field = malloc (sizeof (char) * 15) .
Решту списку ми прив’яжемо до щойно надутої повітряної кулі. Іншими словами, ми прив’яжемо нитку до повітряної кулі, яку тримав Петрік, яка закінчуватиметься на першій кулі Зузанки. Ми цього не говорили, але на одну повітряну кулю можна прив'язати кілька шнурів (діти порядні, і вони ніколи не потягнуться за повітряними кульками).
Не забуваємо: Петрік тримає в руках шнурок для свіжої кулі. Якщо ми хочемо змінити властивості повітряної кулі, ми повинні дістатися до неї через рядок, який ми надамо оператор дереференції, писати як * .
- на новій кулі ми малюємо знак, який буде тримати
- і ми прив’язуємо на ньому нитку до першої повітряної кулі Зузанкіна. У цьому випадку варто перевірити типи даних:
- наступний елемент має тип struct * елемент (повітряна куля), а змінна z (Zuzankinka ruka) - тип TRAY, що є псевдонімом для struct * елемента. Отже все добре.
Тепер буде лише дружній обмін. Якщо Зузанка випустить свою повітряну кулю, нічого не станеться, тому що Петрік тримає цілий ланцюжок повітряних куль. (Так, Петрік зберігає цілий новий список повітряних куль!)
У коді С обмін не повинен відображатися будь-яким чином.
Якщо Петрік передає ланцюг Зузанці, у якої порожні руки, ми вже майже в кінці. Ми відправляємо Петрика додому (він буде плакати, але в змінних C вони ніколи не плачуть), і ми закінчили! У нас журнал довший!
Давайте підведемо підсумок цілого коду. Функції знадобляться дві речі: стек і символ, які потрібно додати до її верхньої частини.
Що він поверне? Може повернути щойно розширений лоток. Перший знімок функції може бути таким, але будьте обережні! містить кілька помилок:
Ми можемо перевірити це:
Якщо ми запустимо програму, то побачимо:
Однак давайте дуже швидко виправимо tray_push (). По-перше:
Кожного разу, коли викликається функція malloc (), переконайтеся, що вона повернула нуль. (Читання зі стандартів кодування GNU, 4.2, пункт 3).
Дуже легко може статися так, що malloc () виходить з ладу, найчастіше, коли доступна пам’ять для вашої програми закінчується.
Але що робити в такий момент?
Якщо malloc виходить з ладу в неінтерактивній програмі, вважайте це фатальною помилкою. (Читання зі стандартів кодування GNU, 4.2, пункт 7).
Програма може негайно закінчитися, наприклад із кодом виходу 2, який буде нашою домовленістю про відсутність пам'яті. Щоб не мати магічних чисел після коду, ми визначаємо константу:
Друга модифікація буде естетичною: на мові C доступ до властивостей повітряної кулі за допомогою рядків (давайте прочитаємо це як "доступ до елементів структури через покажчик") настільки поширений, що він заслужив власний синтаксис:
ми можемо написати синтаксис стрілки:
Заглядаючи в журнал
Нарешті, ми можемо додати дані! Але якщо ми не хочемо мати чорну діру від журналу, давайте спритно напишемо спосіб зазирнути в неї.
Знову ж таки, перше, хоча і не дуже правильне рішення:
Спробуємо перевірити це:
Після початку ми повинні побачити дужки. Але спробуємо це!
Після запуску ми майже напевно побачимо:
Функція постачається зі змінною типу TRAY, що містить NULL, яка точно не має елемента з символом імені. Що таке виняток NullPointerException в Java, в C це несанкціонований доступ до пам'яті та збій програми.
Давайте швидко виправимо функцію! Але що, якщо лоток порожній? Хтось запропонував нам повернути спеціальний символ, наприклад \ 0 .
Час для повітряних куль, розривних та руйнівних дій! Алгоритм сукупності буде таким:
А тепер уявіть, що Зузанка веде список повітряних куль. Позбудемося першої повітряної кулі, але без польоту!
Ми закликаємо друга Петру на допомогу і кажемо йому тримати першу повітряну кулю у списку, тобто ту саму повітряну кулю, на якій Зузанка тримає нитку.
Десь збоку ми позначаємо знак з першої повітряної кулі. Нам це знадобиться пізніше.
Давайте скажемо Зузанці, щоб тягнув другу повітряну кулю в чергу.
Зараз дуже важливо, щоб перший аеростат утримував Петро, бо інакше він летів би вічно!
Наразі Зузанка має коротший список, і ми могли б закінчити. Але ще одне!
Перша повітряна куля нам більше не знадобиться: знак, який на ній намалювали, вже позначений збоку. У такому випадку він нам потрібен лопнути. Повітряні кулі, які динамічно розподіляються через структуру y (виділяються через malloc ()), займають пам’ять, і якщо вони нам не потрібні, ми повинні звільнити пам’ять вручну.
Звільнити пам’ять за допомогою функції free () .
У C принцип полягає в тому, що кожен виклик malloc () повинен мати безкоштовний () виклик. !
Зведений код, традиційно з багатьма помилками, буде виглядати так:
Спробуємо перевірити це на прикладі порожнього лотка:
Програма призначена десь навколо c = z-> символу. Якщо ми були обережні в попередньому розділі, ми знаємо чому: покажчик NULL не має символу.
Тому ми повинні перевірити, що ми випадково не вискакуємо з порожнього контейнера! Якщо так, ми можемо повернути традиційний \ 0 .
Давайте спробуємо це зараз:
Після запуску ми побачимо:
Скрутіть фігурну дужку! Якщо ми уважніше його розглянемо, то виявимо, що pop () не працює належним чином: той самий верхній предмет все ще витягується зі стека, або іншими словами: функція не працює як pop (), але як заглянути () .
Наша функція повертає один параметр: символ, але насправді нам потрібно повернути до двох речей! Не лише персонаж, а й коротший журнал!
Наразі ми розуміли цю функцію як м’ясорубку, в яку ми встановлюємо вхідні параметри, а оброблений результат випадає з іншого кінця.
Але С-функції можуть також функціонувати як змішувач кухонного комбайна, де ми завантажуємо дані, змішуємо їх, а потім вибираємо з них. У нашому випадку нам потрібно «змішати» змінну зі стеком: точніше, нам потрібно вирізати з неї перший елемент.
Така обробка параметрів у C називається передача параметрів за посиланням. Змінна, що надсилається до функції за допомогою посилання, є не тільки вхідною (переходить до шліфувальної машини), але вхідною/вихідною. Функція може змінювати вміст змінної всередині, і зміни будуть видимими навіть після виконання функції.
Якщо ми хочемо позначити змінну як вхід-вихід, ми використовуємо ... ТУТ ... покажчики!
Заголовок функції буде виглядати так:
У цьому випадку змінна z стає покажчиком на TRAY. Якщо ми не хочемо працювати з точкою на ZASOBNIK, а з ZASOBNIK, ми будемо використовувати старе відоме розпізнавання, тобто оператор * .
Ми починаємо бачити зірки перед очима!
Можна сказати, що вхідно-вихідним змінним просто потрібно механічно передувати оператор розвідки, і все буде добре. З однією приміткою: якщо у нас є змінна вводу-виводу, що представляє * покажчик на struct`, і ми хочемо отримати доступ до її елементів, нам потрібно правильно вкласти вираз:
Спробуємо на попередньому випадку ... Але будьте обережні! Функція storage_pop більше не приймає TRAY, а вказівник на неї!
Якщо у нас є змінна, і ми хочемо отримати її адресу (тобто отримати вказівник на неї), ми використовуємо довідковий оператор: амперсанд & .
Амперсанд та зірочка є операторами друзів: зірочка спускається вниз стрілкою, тому отримує вміст із вказівника. Амперсанд, у свою чергу, отримує свою адресу в пам'яті для даної змінної, тобто повертає покажчик.
Приємною (іншою) аналогією є ключі від готельного номера: якщо у вас є ключі в руці, ви тримаєте вказівник. Зірочка означає заходити в кімнату, відкривати її та мати можливість користуватися її інвентарем. Амперсанд, що використовується в кімнаті, означає отримання ключів від нього.
Повернемося до висунення речей у верх стека: функція tray_push буде виглядати «більш охайною», якщо ми її налаштуємо в поп-дусі: вона прийме змінну вводу/виводу TRAY і нічого не поверне.
Оскільки філософія функцій C часто полягає у поверненні параметрів за допомогою контрольних викликів та поверненні повернутих значень для успіху/відмови функції. (Ось як scanf та багато функцій від stdio.h працюють так.)
Якщо ми подивимось, що зроблено, то виявимо, що… у нас є все необхідне з лотка.
Пора зробити весь алгоритм з моменту вступу!
Спочатку зниклий стек в C здавався страшною трагедією, але чесно: ми реалізували його дуже швидко і також ефективно. Насправді ми це навіть реалізували список з'єднань, хоча ми можемо лише додавати елементи до нього на початку і видаляти їх лише з самого початку.
У той же час ми показали ряд властивостей цеккойда: покажчики, структуру і навіть передавання параметрів за посиланням!