публичен статичен void блог ()

Тавата е страхотно нещо. Можем да го използваме, за да разберем дали изразът е правилно затворен в скоби:

róbert

Например тази програма Clojure е правилно затворена в скоби:

И този JSON не е:

Един прост алгоритъм изглежда така:

Все още маргинални случаи!

  • ако при премахване на скобата от горната част на стека открием, че имаме празен стек, имаме твърде много десни скоби (някой е забравил да спомене лявата скоба).
  • ако четем всички символи и стекът не е празен, това означава твърде много оставени скоби. Това е по-често срещана грешка: това означава, че липсва някаква дясна скоба.

За Clojure процедурата ще изглежда така:

  • character: (, поставяме на стека: (
  • характер: [, поставяме на стека: [`(
  • знак:], издърпайте от стека [, стека: (
  • character: (, поставяме на стека: ((
  • характер: (, ние поставяме на стека: (((
  • символ:), издърпайте от стека (, стека: ((
  • символ:), издърпайте от стека (, стека: (
  • character:), извадете го от стека (и стекът ще остане празен.

Нека да разгледаме лошия JSON:

  • знак: <, strčíme na štós: `
  • характер: [, поставяме на стека: [
  • знак:>, издърпайте от горната част на стека]. Това обаче не е приятелска скоба и имаме грешка в твърде много леви скоби.

За да обобщим, имаме нужда от три операции от стъблото:

  • вмъкнете отгоре
  • вземете отгоре
  • и вижте дали е празно

Много пъти се доставя четвъртата операция:

  • възхищавайте се на хълма му

На английски операциите им съответстват натиснете (печат), поп (изберете), надникнете (надникнете) a празен (откриване на празнота).

И защо цена? Тъй като той най-добре съвпада с купчината хартии или още по-добре с купчината чинии:

На словашки език обаче никой компютърен учен няма да използва думата štós (въпреки че корпусът на словашкия език няма проблем с това); използвано е обозначението тава, очевидно под влияние на военната служба:

Можете да закупите списанието за автомата CZ Scorpion, например от AFG.sk:

Отделно céčko има много минималистична библиотека и не съществува вариант на java.util.Stack или Python букви.

Ако имаме късмет и програмираме за BSD или Linux, можем да използваме библиотеката sys/queue.h и ако не, можем да го направим по нашия начин.

Структури на данни

Това е стекът:

Очевидно балоните и децата на UML не са свързани със списанието? Напротив !. Всеки балон е елемент свързан списък и всеки низ не е нищо друго освен начин да стигнете до следващия балон (като го изтеглите към ръката си).

И няма да го пазим в тайна, всеки низ представлява указател към балона, защото този, който държи връвта, може да улови самия балон в края му, като дърпа.

В допълнение към своя цвят, размер и други атрибути (напр. Вид газ вътре, хелийът е забавен), всеки балон има низ за следващия балон, т.е. също указател към балона.

В тази аналогия ще се прилага следното:

Щастливото дете може да стигне до първия балон благодарение на струната и когато погледнем по различен начин, това представлява радостна радост, която държи списък с балони. (Той може да предаде тези пакети на друго дете, ако е необходимо.)

Това води до очарователна функция: списъкът с балони може да бъде объркан с точката за първия балон по желание.

Защото който има връв за първия балон, може постепенно да стигне до останалите.

Но нека го запишем в C!

Представяме балона като структура, представляваща елемент от контейнер. В стека няма да записваме нито цвят, нито хелий, а само символи: защото няма да забравим задачата от началото на статията.

Някои хора се притесняват, че елементът на структурата се дефинира като съединение от символ и указател към елемент на структура, но това не е нищо особено: рекурсията е естествено свойство не само в математиката.

Нека не забравяме да включим и точка и запетая след къдравата скоба!

Имаме структура от данни и нека направим празен списък! Ще изглежда така:

Да. Тъжно-весело дете държи връв, но няма балон в края. Нулеви балони означава празен списък:

Променливата empty_list има тип указател към елемента struct (Да не забравяме, това е низ! Низът е указател!) И тъй като в края няма балон, ще го представим с NULL указател.

Нека също не забравяме, че „списък с елементи може да бъде объркан с указател към първия му елемент!“ и следователно целият списък е от тип struct item * .

Определено ще ни раздразни - тези мултианологии, които трябва да имаме предвид, лесно се забравят.

За щастие в C можем да дадем персонализирани имена на типовете данни (моля за псевдоними, дори ако нито една торта не го нарича така):

В превод: отсега нататък елементът от типа структура * се кръщава TRAY. (Някои конвенции на C казват, че типовете данни typedef/alias са главни.)

След редактиране програмата ще изглежда така:

Празен контейнер

Засега трябва да имаме оборудвани структури от данни и е време за алгоритми! Хм, или по-скоро изпълнението на четири функции.

Нека започнем с най-простия: да разберем дали тавата е празна. Заглавка на функцията?

Функцията връща устройството, ако тавата е празна, в противен случай връща нула. А параметрите? С радост можем да мислим за прясно дефинирания тип данни TRAY, след което можем да си представим указател към първия елемент на стека.

Внедряването е просто:

Чудесно, можем да тестваме програмата!

Добавяне в тавата

Саундтракът на този блок е Garbage: Push It. С изключение на Garbage, може би ще добавим разумни неща в горната част на тавата.

Тук обаче алгоритъмът ще бъде малко по-сложен, защото трябва да следваме основния принцип, когато играем с балони:

Балон, който не държи нито една ръка или не е вързан за друг балон, ще лети необратимо!

Ще говорим за летящи балони по-късно, в C това означава голяма галиба.

А сега си представете, че Зузанка води списък с балони.

За героя, който добавяме, трябва да надуем нов балон. Някой ще трябва да го задържи (в противен случай ще отлети, което означава избягване!). Обаждаме се на нашия приятел Петрик да му помогне и му даваме връв за нов балон.

Ще се надуваме динамично. Ще запазим място в паметта за елемент от списък (елемент на структура), ще получим низ към него (т.е. указател) и след това ще говорим с него допълнително.

Функцията malloc () разпределя точно толкова байта памет, колкото заема типът на данните от структурата, които намираме, използвайки sizeof band meter. Поставяме показалеца за нов елемент (= низ за балон) в ръката на спомагателната променлива p ˙.

Боком: ако конструкцията изглежда странна, няма нужда да се паникьосвате. Ако искаме да разпределим памет за един int, нека напишем int * element = malloc (sizeof (int)). Ако искаме памет за петнадесет знака (т.е. низ от 14 знака), char * field = malloc (sizeof (char) * 15) .

Ще обвържем останалата част от списъка с току-що напомпан балон. С други думи, ще завържем връв към балона, държан от Петрик, който ще завърши на първия балон на Зузанка. Не казахме това, но няколко кабела могат да бъдат вързани за един балон (децата са свестни и никога няма да се опънат за балони.)

Да не забравяме: Петрик държи връв за нов балон. Ако искаме да променим свойствата на балона, трябва да стигнем до него през низа, който ще предоставим дереферентен оператор, пиша като * .

  • на нов балон чертаем знак, който ще се задържи
  • и връзваме връв върху него за първия балон на Зузанкин. В този случай си струва да проверите типовете данни:
    • следващият елемент е от тип struct * елемент (балонен низ), а променливата z (Zuzankinka ruka) е от тип TRAY, което е псевдоним за struct * елемент. Така че всичко е наред.

Сега ще има само приятелски обмен. Ако Зузанка пусне балона си, нищо не се случва, защото Петрик държи цялата верига от балони. (Да, Петрик поддържа цял нов списък с балони!)

В C кода обменът не трябва да се отразява по никакъв начин.

Ако Петрик предаде веригата си на Зузанка, която има празни ръце, ние сме почти на финала. Изпращаме Петрик у дома (той ще плаче, но при променливи C те никога не плачат) и готово! Имаме по-дълго списание!

Нека обобщим целия код. Функцията ще се нуждае от две неща: стек и символ, които да добави в горната си част.

Какво ще върне? Може да върне прясно разширена тава. Първият изстрел на функцията може да е такъв, но внимавайте! съдържа няколко грешки:

Можем да го тестваме:

Ако стартираме програмата, трябва да видим:

Нека обаче поправим tray_push () много бързо. Първо:

Всеки път, когато се извика функцията malloc (), проверявайте дали връща нула. (четене от стандарти за кодиране на GNU, 4.2, параграф 3).

Много лесно може да се случи, че malloc () се провали, най-често, когато наличната памет за вашата програма свърши.

Но какво да правя в такъв момент?

Ако malloc се провали в неинтерактивна програма, помислете за фатална грешка. (Четене от стандарти за кодиране на GNU, 4.2, параграф 7).

Програмата може да приключи незабавно, например с код за изход 2, който ще бъде нашето споразумение, показващо липса на памет. За да нямаме магически числа, хвърлени след кода, дефинираме константа:

Втората модификация ще бъде естетична: на език C достъпът до свойствата на балон чрез низове (нека го прочетем като „достъп до структурни елементи чрез указател“) е толкова често срещан, че е спечелил собствен синтаксис:

можем да напишем синтаксис на стрелката:

Надникване в списанието

Накрая можем да добавим данни! Но ако не искаме да имаме черна дупка от списанието, нека умно напишем начин да надникнем в него.

Отново първото, макар и не много правилно решение:

Нека се опитаме да го проверим:

След стартиране трябва да видим скоба. Но нека опитаме това!

След като стартираме, почти сигурно ще видим:

Функцията се предлага с променлива от тип TRAY, съдържаща NULL, която определено няма елемент с имена. Какво е изключение NullPointerException в Java, в C това е неоторизиран достъп до паметта и срив на програмата.

Нека поправим функцията бързо! Но какво, ако тавата е празна? Някой предложи да върнем специален знак, като \ 0 .

Време за балони, спукване и разрушителна дейност! Алгоритъмът на популацията ще бъде както следва:

А сега си представете, че Зузанка води списък с балони. Да се ​​отървем от първия балон, но без да летим!

Обаждаме се на приятел на Петър и му казваме да държи първия балон от списъка, който е същият балон, на който Зузанка държи връв.

Някъде отстрани маркираме знака от първия балон. Ще ни трябва по-късно.

Нека кажем на Зузанка да изтегли втория балон в опашката.

Сега е много важно първият балон да се държи от Питър, защото в противен случай той би летял завинаги!

В момента Zuzanka държи по-кратък списък и бихме могли да завършим. Но още нещо!

Вече няма да имаме нужда от първия балон: знакът, който беше нарисуван върху него, вече е маркиран отстрани. В такъв случай имаме нужда от него да се спука. Балоните, които са динамично разпределени структура y (разпределени чрез malloc ()) заемат памет и ако нямаме нужда от тях, трябва ръчно да освободим паметта.

Паметта може да се освободи чрез функцията free () .

В C принципът е, че всяко повикване на malloc () трябва да има безплатно () повикване. !

Обобщеният код, традиционно с много грешки, ще изглежда така:

Нека се опитаме да го проверим, като използваме примера на празна тава:

Програмата е предназначена някъде около c = z-> символ. Ако бяхме внимателни в предишния раздел, знаем защо: NULL указателят няма символ.

Затова трябва да проверим, че не случайно изскачаме от празен контейнер! Ако е така, можем да върнем традиционното \ 0 .

Нека опитаме това сега:

След стартирането ще видим:

Завийте къдравата скоба! Ако го разгледаме по-отблизо, ще открием, че pop () не работи правилно: същият най-горният елемент все още е изваден от стека, или с други думи: функцията не работи като pop (), но като надникнете () .

Нашата функция връща един параметър: символ, но всъщност трябва да върнем до две неща! Не само герой, но и по-кратко списание!

Досега разбрахме функцията като месомелачка, в която задаваме входните параметри и обработеният резултат отпада от другия си край.

Но С-функциите могат да функционират и като миксер за кухненски робот, където зареждаме данните, смесваме ги и след това ги избираме от него. В нашия случай трябва да "смесим" променливата със стека: по-точно трябва да отрежем първия елемент от нея.

Такава обработка на параметри в C се нарича предаване на параметри по референция. Променливата, изпратена до функцията чрез препратка, е не само входна (пътува до мелницата), но и входна/изходна. Функцията може да промени съдържанието на променливата вътре и промените ще бъдат видими дори след изпълнението на функцията.

Ако искаме да маркираме променлива като вход-изход, използваме ... ТУК ... указатели!

Заглавката на функцията ще изглежда така:

В този случай променливата z се превръща в указател към TRAY. Ако не искаме да работим с точката на ZASOBNIK, а със ZASOBNIK, ще използваме старата добре позната dereference, т.е. оператора * .

Започваме да виждаме звездите пред очите си!

Може да се каже, че входно-изходните променливи просто трябва да бъдат механично предшествани от оператора за пренасочване и всичко ще бъде наред. С една бележка: ако имаме I/O променлива, представляваща * указател към struct` и искаме да осъществим достъп до нейните елементи, трябва да приложим израза правилно:

Нека опитаме в предишния случай ... Но внимавайте! Функцията storage_pop вече не приема TRAY, а указател към нея!

Ако имаме променлива и искаме да получим нейния адрес (т.е. да получим указател към нея), използваме референтен оператор: амперсанд & .

Амперсандът и звездичката са приятелски оператори: звездичката слиза надолу по стрелката, така че получава съдържанието от показалеца. Амперсандът от своя страна получава адреса си в паметта за дадена променлива, т.е. връща указател.

Хубава (друга) аналогия са ключовете за хотелска стая: ако имате ключовете в ръката си, държите показалец. Звездичка означава да влезете в една стая и да я отворите и да можете да използвате инвентара ѝ. Амперсандът, използван в стаята, означава да вземете ключовете от него.

Да се ​​върнем към изтласкването на нещата в горната част на стека: функцията tray_push ще изглежда „по-подредена“, ако я коригираме в поп дух: тя ще вземе променливата TRAY input/output и няма да върне нищо.

Тъй като C философията на функциите често е да връщат параметри чрез референтни повиквания и да връщат връщани стойности за успех/неуспех на функцията. (Ето как scanf и много функции от stdio.h работят по този начин.)

Ако погледнем какво е направено, откриваме, че ... имаме всичко необходимо от тавата.

Време е да направим целия алгоритъм от въведението!

Отначало липсващият стек в C изглеждаше като ужасна трагедия, но честно казано: внедрихме го много бързо и също така ефективно. Всъщност дори го внедрихме списък с връзки, въпреки че можем да добавяме елементи към него само в началото и да ги премахваме само от самото начало.

В същото време показахме редица цекоидни свойства: указатели, структура и дори предаване на параметри по препратка!