blog public public static ()

Tava este un lucru grozav. Îl putem folosi pentru a afla dacă o expresie este încadrată corect între paranteze:

propriu

De exemplu, acest program Clojure este inclus corect între paranteze:

Și acest JSON nu este:

Un algoritm simplu arată astfel:

Încă cazuri marginale!

  • dacă, când scoatem parantezul din partea de sus a teancului, constatăm că avem un teanc gol, avem prea multe paranteze drepte (cineva a uitat să menționeze parantezul stâng).
  • dacă citim toate caracterele și stiva nu este goală, înseamnă prea multe paranteze la stânga. Aceasta este o eroare mai frecventă: înseamnă că lipsește o paranteză dreaptă.

Pentru Clojure, procedura va arăta astfel:

  • caracter: (, punem pe stivă: (
  • caracter: [, am pus pe stiva: [`(
  • caracter:], scoate din stivă [, stivă: (
  • caracter: (, punem pe stivă: ((
  • caracter: (, punem pe stivă: (((
  • caracter:), trageți din stivă (, stiva: ((
  • caracter:), trage din stivă (, stivă: (
  • personaj:), scoate-l din stivă (și stiva va rămâne goală.

Să ne uităm la JSON rău:

  • semn: <, strčíme na štós: `
  • caracter: [, am pus pe stiva: [
  • personaj:>, trageți din partea de sus a stivei]. Cu toate acestea, aceasta nu este o paranteză prietenoasă și avem o eroare de prea multe paranteze stângi.

Pentru a rezuma, avem nevoie de trei operații din tulpină:

  • introduceți deasupra
  • alege din partea de sus
  • și vezi dacă este gol

De multe ori, a patra operație este livrată:

  • admira-i dealul

În limba engleză, operațiunile le corespund Apăsați (imprimare), pop (Selectați), arunca o privire (privi) a gol (detectarea golului).

Și de ce cost? Pentru că se potrivește cel mai bine cu teancul de hârtii sau, mai bine, cu teancul de farfurii:

Cu toate acestea, în slovacă, niciun informatician nu va folosi cuvântul štós (deși corpusul de limbă slovacă nu are nicio problemă în acest sens); a fost utilizată denumirea tavă, aparent sub influența serviciului militar:

Puteți cumpăra revista pentru mitraliera CZ Scorpion, de exemplu, de la AFG.sk:

Un céčko separat are o bibliotecă foarte minimalistă și nu există nicio variantă a literelor java.util.Stack sau Python.

Dacă avem noroc și programăm pentru BSD sau Linux, putem folosi biblioteca sys/queue.h și, dacă nu, o putem face în felul nostru.

Structuri de date

Aceasta este stiva:

Se pare că baloanele și copiii UML nu au legătură cu revista? Dimpotriva !. Fiecare balon este un obiect listă legată și fiecare șir nu este altceva decât o modalitate de a ajunge la următorul balon (trăgându-l la mână).

Și nu vom păstra secretul, fiecare șir reprezintă indicatorul către balon, deoarece cel care ține șirul poate prinde balonul însuși la capătul său trăgând.

În plus față de culoarea, dimensiunea și alte atribute (de exemplu, tipul de gaz din interior, heliul este distractiv), fiecare balon are un șir pentru următorul balon, adică și un indicator către balon.

În această analogie, se vor aplica următoarele:

Un copil fericit poate ajunge la primul balon datorită șirului și, atunci când îl privim diferit, reprezintă o bucurie veselă care ține lista cu baloane. (El poate transmite aceste pachete unui alt copil, dacă este necesar.)

Aceasta are ca rezultat o caracteristică adorabilă: lista baloanelor poate fi confundată cu punctul pentru primul balon după bunul plac.

Pentru că oricine are o coardă pentru primul balon poate ajunge treptat la ceilalți.

Dar hai să o scriem în C!

Reprezentăm balonul ca o structură care reprezintă un obiect container. Nu vom înregistra nici culoare, nici heliu în stivă, ci doar caractere: pentru că nu vom uita sarcina de la începutul articolului.

Unii oameni sunt deranjați de faptul că un element struct este definit ca un compus dintr-un caracter și un pointer către un element struct, dar asta nu este nimic special: recursiunea este o proprietate naturală nu numai în matematică.

Să nu uităm să includem un punct și virgulă după acoladă!

Avem o structură de date și să facem o listă goală! Va arăta astfel:

Da. Un copil trist și vesel ține un șir, dar nu are balon la final. Baloane zero înseamnă listă goală:

Variabila goal_list are tip pointer către struct element (Să nu uităm, este un șir! Un șir este un pointer!) Și din moment ce nu există balon la final, îl vom reprezenta cu un pointer NULL.

Să nu uităm, de asemenea, că „o listă de articole poate fi confundată cu un indicator către primul său element!” și, prin urmare, întreaga listă este de tip struct item * .

Cu siguranță ne va irita - aceste multianologii, pe care trebuie să le avem în vedere, sunt ușor de uitat.

Din fericire, în C, putem da tipurilor de date nume personalizate (cer aliasuri, chiar dacă niciun tort nu o numește așa):

În traducere: de acum înainte, tipul de date struct item * este botezat TRAY. (Unele convenții C spun că tipurile de date typedef/alias sunt majuscule.)

După editare, programul va arăta astfel:

Recipient gol

Ar trebui să avem structuri de date echipate pentru moment și este timpul pentru algoritmi! Um, sau mai bine zis implementarea a patru funcții.

Să începem cu cea mai simplă: să aflăm dacă tava este goală. Antetul funcției?

Funcția returnează unitatea dacă tava este goală, altfel revine la zero. Și parametrii? Ne putem gândi cu bucurie la tipul de date proaspăt definit TRAY, după care ne putem imagina un pointer către primul element al stivei.

Implementarea este simplă:

Super, putem testa programul!

Adăugarea la tavă

Coloana sonoră a acestui bloc este Garbage: Push It. Cu excepția gunoiului, poate vom adăuga lucruri sensibile în partea de sus a tăvii.

Aici, totuși, algoritmul va fi puțin mai complicat, deoarece trebuie să urmăm principiul de bază atunci când ne jucăm cu baloane:

Un balon care nu ține nicio mână sau nu este legat de un alt balon va zbura ireversibil!

Vom vorbi despre baloane zburătoare cândva mai târziu, în C înseamnă o galiba mare.

Acum imaginați-vă că Zuzanka păstrează o listă de baloane.

Pentru personajul pe care îl adăugăm, trebuie să umflăm un nou balon. Cineva va trebui să o țină (altfel ar zbura, ceea ce înseamnă fugit!). Îl sunăm pe prietenul nostru Petrík să-l ajute și îi dăm o sfoară pentru un nou balon.

Ne vom umfla dinamic. Vom rezerva spațiu în memorie pentru un element de listă (element struct), vom primi un șir (adică un pointer) și apoi vom vorbi cu el mai departe.

Funcția malloc () alocă exact atât de mulți octeți de memorie pe cât ocupă tipul de date struct element, pe care îl găsim folosind dimensiunea contorului de bandă. Punem indicatorul pentru un element nou (= șir pentru un balon) în mâna variabilei auxiliare p ˙.

Bokom: dacă construcția pare ciudată, nu este nevoie să intrăm în panică. Dacă dorim să alocăm memorie pentru un int, să scriem int * element = malloc (sizeof (int)). Dacă dorim memorie pentru cincisprezece caractere (adică un șir de 14 caractere), câmpul char * malloc (sizeof (char) * 15) .

Restul listei îl vom lega de un balon proaspăt umflat. Cu alte cuvinte, vom lega o sfoară de balonul ținut de Petrík, care se va termina pe primul balon al Zuzanka. Nu am spus asta, dar mai multe corzi pot fi legate de un balon (copiii sunt decenți și nu se vor întinde niciodată pentru baloane.)

Să nu uităm: Petrík ține un șir pentru un balon proaspăt. Dacă vrem să schimbăm proprietățile balonului, trebuie să ajungem la el prin șir, pe care îl vom furniza operator de dereferență, scriind ca * .

  • pe un balon nou desenăm un semn care va ține
  • și legăm un șnur pe primul balon al lui Zuzankin. În acest caz, este bine să verificați tipurile de date:
    • următorul articol este de tip struct * item (balon șir) și variabila z (Zuzankinka ruka) este de tip TRAY, care este un alias pentru struct * item. Deci totul este în regulă.

Acum va exista doar un schimb prietenos. Dacă Zuzanka își eliberează balonul, nu se întâmplă nimic, pentru că Petrík deține întregul lanț de baloane. (Da, Petrík păstrează o listă complet nouă de baloane!)

În codul C, schimbul nu trebuie să se reflecte în niciun fel.

Dacă Petrík îi dă lanțul lui Zuzanka, care are mâinile goale, suntem aproape la sfârșit. Îl trimitem pe Petrík acasă (el va plânge, dar în variabilele C ei nu plâng niciodată) și am terminat! Avem o revistă mai lungă!

Să rezumăm întregul cod. Funcția va avea nevoie de două lucruri: o stivă și un caracter pentru a le adăuga în partea de sus.

Ce se va întoarce? Poate returna o tavă proaspăt extinsă. Prima fotografie a funcției poate fi așa, dar atenție! conține mai multe erori:

Îl putem testa:

Dacă rulăm programul, ar trebui să vedem:

Cu toate acestea, hai să reparăm tray_push () foarte repede. In primul rand:

De fiecare dată când se apelează funcția malloc (), verificați dacă a returnat zero. (Citirea din standardele de codificare GNU, 4.2, paragraful 3).

Se poate întâmpla foarte ușor ca malloc () să eșueze, cel mai adesea când memoria disponibilă pentru programul dvs. se epuizează.

Dar ce să faci într-un astfel de moment?

Dacă malloc eșuează într-un program non-interactiv, considerați-l o eroare fatală. (Citirea din standardele de codificare GNU, 4.2, par. 7).

Programul se poate încheia imediat, de exemplu cu codul de ieșire 2, care va fi acordul nostru care indică o lipsă de memorie. Pentru a nu avea numere magice aruncate după cod, definim o constantă:

A doua modificare va fi estetică: în C, accesarea proprietăților balonului prin șiruri (să o citim ca „accesarea elementelor struct prin pointre”) este atât de comună încât și-a câștigat propria sintaxă:

putem scrie sintaxa săgeții:

Aruncând o privire în revistă

În cele din urmă putem adăuga date! Dar dacă nu vrem să avem o gaură neagră din revistă, să scriem cu înțelepciune o modalitate de a ne uita la ea.

Din nou, prima soluție, deși nu foarte corectă:

Să încercăm să o verificăm:

După început, ar trebui să vedem o paranteză. Dar să încercăm asta!

Odată lansat, vom vedea cu siguranță:

Funcția vine cu o variabilă de tip TRAY care conține NULL, care cu siguranță nu are un articol cu ​​caracterul de nume. Ce este o excepție NullPointerException în Java, în C este acces neautorizat la memorie și blocarea programului.

Să reparăm rapid funcția! Dar dacă tava este goală? Cineva a sugerat să returnăm un caracter special, cum ar fi \ 0 .

Timp pentru baloane, explozie și activitate distructivă! Algoritmul populației va fi după cum urmează:

Acum imaginați-vă că Zuzanka păstrează o listă de baloane. Să scăpăm de primul balon, dar fără să zburăm!

Chemăm un prieten de ajutor lui Petr și îi spunem să țină primul balon de pe listă, care este același balon pe care Zuzanka ține un șir.

Undeva lateral marcăm semnul din primul balon. Vom avea nevoie mai târziu.

Să-i spunem lui Zuzanka să tragă al doilea balon în linie.

Acum este foarte important ca primul balon să fie ținut de Peter, pentru că altfel ar zbura pentru totdeauna!

Zuzanka deține în prezent o listă mai scurtă și am putea termina. Dar încă un lucru!

Nu vom mai avea nevoie de primul balon: semnul care a fost pictat pe el este deja marcat pe lateral. În acest caz, avem nevoie de el a izbucni. Baloanele care sunt alocate dinamic struct y (alocate prin malloc ()) ocupă memorie și dacă nu avem nevoie de ele, trebuie să eliberăm manual memoria.

Memoria poate fi eliberată prin intermediul funcției free () .

În C, principiul este că fiecare apel malloc () ar trebui să aibă un apel gratuit (). !

Codul rezumat, în mod tradițional cu multe erori, va arăta astfel:

Să încercăm să o verificăm, folosind exemplul unei tăvi goale:

Programul este destinat undeva în jurul caracterului c = z->. Dacă am fost atenți în secțiunea anterioară, știm de ce: Un pointer NULL nu are un caracter.

Deci, trebuie să verificăm dacă nu ieșim din greșeală dintr-un container gol! Dacă da, putem returna tradiționalul \ 0 .

Să încercăm acum:

După lansare vom vedea:

Răsuciți suportul creț! Dacă aruncăm o privire mai atentă la el, am descoperi că pop () nu funcționează corect: același element cel mai de sus este încă extras din stivă, sau cu alte cuvinte: funcția nu funcționează ca pop (), dar ca peek () .

Funcția noastră returnează un singur parametru: un caracter, dar de fapt trebuie să returnăm până la două lucruri! Nu doar un personaj, ci și o revistă mai scurtă!

Până acum, am înțeles funcția ca o mașină de tocat carne, în care stabilim parametrii de intrare, iar rezultatul procesat cade din celălalt capăt al acestuia.

Dar funcțiile C pot funcționa și ca un robot de bucătărie-mixer, unde încărcăm datele, le amestecăm și apoi le selectăm din acesta. În cazul nostru, trebuie să „amestecăm” variabila cu stiva: mai exact, trebuie să avem primul element tăiat din ea.

O astfel de procesare a parametrilor în C se numește trecerea parametrilor prin referință. Variabila trimisă funcției prin referință nu este doar de intrare (se deplasează la polizor), ci de intrare/ieșire. Funcția poate modifica conținutul variabilei din interior și modificările vor fi vizibile chiar și după executarea funcției.

Dacă dorim să marchăm o variabilă ca intrare-ieșire, folosim ... AICI ... indicii!

Antetul funcției va arăta astfel:

În acest caz, variabila z devine un pointer către TRAY. Dacă nu dorim să lucrăm cu punctul de pe ZASOBNIK, ci cu ZASOBNIK, vom folosi vechea dereferință binecunoscută, adică operatorul * .

Începem să vedem stelele în fața ochilor noștri!

S-ar putea spune că variabilele de intrare-ieșire trebuie doar să fie precedate mecanic de operatorul de dereferință și totul va fi în ordine. Cu o singură notă: dacă avem o variabilă I/O care reprezintă * pointer to struct` și vrem să accesăm elementele sale, trebuie să închidem expresia corect:

Să încercăm cazul anterior ... Dar atenție! Funcția storage_pop nu mai necesită TRAY, ci un indicator către aceasta!

Dacă avem o variabilă și dorim să obținem adresa acesteia (adică să obținem un pointer către ea), vom folosi operator de referință: ampersand & .

Ampersand și asteriscul sunt operatori prieteni: asteriscul coboară în săgeată, astfel încât să obțină conținutul de la pointer. Ampersand, la rândul său, își primește adresa în memorie pentru o variabilă dată, adică returnează un pointer.

O frumoasă (altă) analogie sunt cheile unei camere de hotel: dacă aveți cheile în mână, țineți un indicator. Un asterisc înseamnă a intra într-o cameră și a o deschide și a-i putea folosi inventarul. Sandra folosită în cameră înseamnă a obține cheile de la ea.

Să revenim la împingerea lucrurilor în partea de sus a stivei: funcția tray_push va arăta „mai ordonată” dacă o ajustăm în stilul pop: va lua variabila de intrare/ieșire TRAY și nu va returna nimic.

Deoarece filozofia funcțiilor C este adesea de a returna parametrii prin apeluri de referință și de a returna valorile de retur pentru succesul/eșecul funcției. (Acesta este modul în care scanf și multe funcții din stdio.h funcționează astfel.)

Dacă ne uităm la ceea ce se face, descoperim că ... avem tot ce ne trebuia din tavă.

Este timpul să faceți întregul algoritm de la introducere!

La început, stiva lipsă din C părea o tragedie teribilă, dar sincer: am implementat-o ​​foarte repede și, de asemenea, în mod eficient. De fapt, chiar am implementat-o lista conexiunilor, deși putem adăuga elemente doar la început și le putem elimina doar de la început.

În același timp, am arătat o serie de proprietăți ceccoide: indicatori, struct y și chiar trecerea parametrilor prin referință!