public static void blog ()

A tálca nagyszerű dolog. Használhatjuk annak kiderítésére, hogy egy kifejezés megfelelően van-e zárójelben:

saját

Például ez a Clojure program megfelelően van zárójelben:

És ez a JSON nem:

Egy egyszerű algoritmus így néz ki:

Még mindig marginális esetek!

  • ha a konzol eltávolításakor a verem tetejéről azt találjuk, hogy üres a verem, akkor túl sok jobb zárójel van (valaki elfelejtette megemlíteni a bal zárójelet).
  • ha az összes karaktert elolvassuk, és a verem nem üres, az túl sok bal zárójelet jelent. Ez egy gyakoribb hiba: azt jelenti, hogy hiányzik néhány helyes zárójel.

A Clojure esetében az eljárás így fog kinézni:

  • karakter: (, veremre tesszük: (
  • karakter: [, veremre tesszük: [`(
  • karakter:], húzza ki a veremből [, verem: (
  • karakter: (, veremre tesszük: ((
  • karakter: (, veremre tesszük: (((
  • karakter:), húzd a veremből (, verem: ((
  • karakter:), húzd a veremből (, verem: (
  • karakter:), húzd ki a veremből (és a verem üres marad.

Nézzük meg a rossz JSON-t:

  • jel: <, strčíme na štós: `
  • karakter: [, veremre tesszük: [
  • karakter:>, húzza a verem tetejéről]. Ez azonban nem barátságos zárójel, és túl sok bal zárójelet hibáztunk.

Összefoglalva, három műveletre van szükségünk a szárból:

  • helyezze be a tetejére
  • válasszon a tetejéről
  • és nézze meg, hogy üres-e

Sokszor a negyedik műveletet hajtják végre:

  • csodálja a dombját

Angolul a műveletek megfelelnek nekik nyom (nyomtatás), pop (kiválaszt), kandikál (kukucskál) a üres (üresség észlelése).

És miért költség? Mivel a legjobban megfelel a papírkötegnek, vagy ami még jobb, a lemezkötegnek:

Szlovákul azonban egyetlen számítógépes sem fogja használni a štós szót (bár a szlovák nyelvű korpusznak ezzel nincs problémája); a megjelölést használták tálca, nyilván katonai szolgálat hatása alatt:

A CZ Scorpion géppisztolyhoz tartozó magazint például megvásárolhatja az AFG.sk webhelyről:

Egy külön céčko nagyon minimalista könyvtárral rendelkezik, és a java.util változata nincs. A Stack vagy Python betűk léteznek.

Ha szerencsénk van, és BSD-re vagy Linux-ra programozunk, használhatjuk a sys/queue.h könyvtárat, és ha nem, akkor a mi utunkra is megtehetjük.

Adatszerkezetek

Ez a verem:

Állítólag a lufik és az UML-gyerekek nem kapcsolódnak a magazinhoz? Ellenkezőleg !. Minden léggömb egy tétel linkelt lista és minden húr nem más, mint a következő ballonhoz jutás módja (a kezéhez húzva).

És nem titkoljuk, minden húr képviseli mutató a ballonra, mert aki a húrt tartja, húzással megfoghatja magát a ballont a végén.

A színén, méretén és egyéb tulajdonságain (pl. A belsejében lévő gáz típusa, a hélium szórakoztató) kívül minden léggömbön van egy húr a következő léggömbhöz, vagyis mutató is van a ballonra.

Ebben az analógiában a következőket kell alkalmazni:

Egy boldog gyermek a húrnak köszönhetően eljuthat az első lufihoz, és ha másképp nézzük, ez örömteli örömet jelent, amely megtartja lufik listája. (Szükség esetén átadhatja ezeket a csomagokat egy másik gyermeknek.)

Ez egy imádnivaló tulajdonságot eredményez: a léggömbök listája tetszés szerint összekeverhető az első léggömb pontjával.

Mert akinek van húrja az első lufihoz, az fokozatosan eljuthat a többiekhez.

De írjuk C-be!

A léggömböt mint konténer elemet ábrázoló szerkezetet képviseljük. Sem a színt, sem a héliumot nem rögzítjük a veremben, hanem csak karaktereket: mert a cikk elejétől nem felejtjük el a feladatot.

Vannak, akiket zavar, hogy a strukturált elemet egy karakter összetettjeként és egy struktúrára mutató mutatóként definiálják, de ez semmi különös: a rekurzió nemcsak matematikában természetes tulajdonság.

Ne felejtsük el, hogy a göndör zárójel után pontosvesszőt kell beilleszteni!

Adatszerkezetünk van, és készítsünk egy üres listát! Így fog kinézni:

Igen. Egy szomorú-vidám gyermek húrt tart, de a végén nincs léggömb. A nulla lufi azt jelenti üres lista:

Az empty_list változó típusa mutató a strukturált elemre (Ne felejtsük el, ez egy karakterlánc! A karakterlánc egy mutató!) És mivel a végén nincs léggömb, NULL mutatóval fogjuk ábrázolni.

Ne felejtsük el azt sem, hogy "az elemek listája összetéveszthető az első elem mutatójával!" és ezért a teljes lista típusú struct elem * .

Ez mindenképpen irritálni fog minket - ezeket a multianológiákat, amelyeket szem előtt kell tartanunk, könnyen el lehet felejteni.

Szerencsére a C-ben egyedi neveket adhatunk az adattípusoknak (álneveket kérek, még akkor is, ha egyik torta sem hívja így):

Fordításban: ezentúl a struktúra elem * adattípust TRAY-nek keresztelik. (Egyes C konvenciók szerint a typedef/alias adattípusok nagybetűk.)

Szerkesztés után a program így fog kinézni:

Üres tartály

Egyelőre rendelkeznünk kell adatstruktúrákkal, és itt az ideje az algoritmusoknak! Hm, vagy inkább négy funkció megvalósítása.

Kezdjük a legegyszerűbbel: megtudjuk, hogy üres-e a tálca. Funkció fejléc?

A függvény visszaadja az egységet, ha a tálca üres, különben nullát ad vissza. És a paraméterek? Örömmel gondolhatunk a frissen definiált TRAY adattípusra, ami után el tudunk képzelni egy mutatót a verem első elemére.

A megvalósítás egyszerű:

Remek, tesztelhetjük a programot!

Hozzáadás a tálcához

A blokk filmzenéje a Garbage: Push It. A Szemetet leszámítva talán ésszerű dolgokat adunk a tálca tetejére.

Itt azonban az algoritmus egy kicsit bonyolultabb lesz, mert a léggömbökkel való játék során az alapelvet kell követnünk:

Az a léggömb, amely nem fog semmilyen kezet, vagy nincs más léggömbhöz kötve, visszafordíthatatlanul repül!

A lufirepülésről valamikor később beszélünk, C-ben ez egy nagy galibát jelent.

Most képzelje el, hogy Zuzanka vezeti a léggömbök listáját.

Az általunk felvett karakterhez új léggömböt kell felfújnunk. Valakinek meg kell fognia (különben elrepül, ami szökést jelent!). Felhívjuk Petrík barátunkat, hogy segítsen neki, és adunk neki egy húrt egy új lufihoz.

Dinamikusan felfújjuk. Foglalunk helyet a memóriában egy listaelem (struktúra elem) számára, kapunk hozzá egy karakterláncot (azaz egy mutatót), majd tovább beszélünk vele.

A malloc () függvény pontosan annyi bájt memóriát oszt le, amennyit a struktúra elem adattípusa felvesz, amelyet a sávmérő méretének felhasználásával találunk meg. A p point segédváltozó kezébe tesszük az új elem mutatóját (= húr egy ballonhoz).

Bokom: ha az építkezés furcsának tűnik, nem kell pánikba esni. Ha egy int-hez memóriát akarunk lefoglalni, írjuk meg az int * elem = malloc (sizeof (int)) értéket. Ha tizenöt char ov-ra (azaz 14 karakteres karakterláncra) akarunk memóriát, akkor char * mező = malloc (sizeof (char) * 15) .

A lista többi részét egy frissen felfújt léggömbhöz kötjük. Más szavakkal, húrot kötünk a Petrík által tartott ballonhoz, amely Zuzanka első lufiján ér véget. Nem ezt mondtuk, de egy léggömbhöz több zsinór is köthető (a gyerekek tisztességesek, és soha nem fognak lufiért nyújtózkodni.)

Ne felejtsük el: Petrík egy húrt tart egy friss lufihoz. Ha meg akarjuk változtatni a léggömb tulajdonságait, el kell érnünk hozzá a húron keresztül, amelyet megadunk dereference operátor, írás * .

  • egy új léggömbön felhívunk egy jelet, amely megtartja
  • és egy húrt kötünk rá Zuzankin első lufijához. Ebben az esetben érdemes ellenőrizni az adattípusokat:
    • a következő elem a struct * elem (ballon húr) típusú, a z változó (Zuzankinka ruka) pedig a TRAY típusú, ami a struct * elem álneve. Tehát minden rendben van.

Most csak barátságos csere folyik majd. Ha Zuzanka elengedi a léggömbjét, semmi sem történik, mert Petrík tartja az egész léggömbláncot. (Igen, Petrík egy teljesen új listát vezet a léggömbökről!)

A C kódban a cserét semmilyen módon nem kell tükrözni.

Ha Petrík átadja a láncát Zuzankának, akinek üres a keze, akkor már majdnem a végén járunk. Hazaküldjük Petríkot (sírni fog, de C változóban soha nem sírnak), és kész! Van egy hosszabb magazinunk!

Foglaljuk össze az egész kódot. A funkcióhoz két dologra lesz szükség: egy veremre és egy karakterre, amelyet hozzá lehet adni a tetejéhez.

Mit fog visszaadni? Visszaadhat egy frissen kibővített tálcát. A funkció első felvétele lehet ilyen, de vigyázz! több hibát tartalmaz:

Tesztelhetjük:

Ha futtatjuk a programot, látnunk kell:

Javítsuk ki azonban nagyon gyorsan a tray_push () -t. Először:

A malloc () függvény minden egyes meghívásakor ellenőrizze, hogy nullát adott-e vissza. (Olvasás a GNU kódolási szabványaiból, 4.2, 3. bekezdés).

Nagyon könnyen előfordulhat, hogy a malloc () meghibásodik, leggyakrabban akkor, amikor a program számára rendelkezésre álló memória elfogy.

De mit kell tenni egy ilyen pillanatban?

Ha a malloc meghiúsul egy nem interaktív programban, akkor tekintse végzetes hibának. (Olvasás a GNU kódolási szabványaiból, 4.2, 7. bekezdés).

A program azonnal véget érhet, például a 2-es kilépési kóddal, amely megállapodásunk a memóriahiányra utal. Annak érdekében, hogy ne legyenek mágikus számok a kód után, definiálunk egy konstansot:

A második módosítás esztétikus lesz: a C-ben a léggömb tulajdonságainak húrokon keresztüli elérése (olvassuk úgy, hogy "strukturált elemek elérése pointre-on keresztül") olyan általános, hogy kiérdemelte a saját szintaxisát:

írhatunk nyíl szintaxist:

Bekukucskál a magazinba

Végül adatot adhatunk hozzá! De ha nem akarunk fekete lyukat kapni a magazinból, írjunk okosan módot arra, hogy bekukkantsunk.

Ismét az első, bár nem túl helyes megoldás:

Próbáljuk meg ellenőrizni:

Az indulás után zárójelet kell látnunk. De próbáljuk ki!

Miután elindította, szinte biztosan meglátjuk:

A függvény egy TRUL típusú változót tartalmaz, amely NULL-t tartalmaz, és amely határozottan nem rendelkezik névkarakterrel. Mi a NullPointerException kivétel a Java-ban, C-ben ez az illetéktelen memória-hozzáférés és a program összeomlása.

Gyorsan javítsuk ki a funkciót! De mi van, ha a tálca üres? Valaki azt javasolta, hogy adjunk vissza egy speciális karaktert, például \ 0 .

Ideje a lufiknak, a kitörő és a pusztító tevékenységnek! A populációs algoritmus a következő lesz:

Most képzelje el, hogy Zuzanka vezeti a léggömbök listáját. Szabaduljunk meg az első lufitól, de repülés nélkül!

Hívjuk Petr egyik barátját, és azt mondjuk neki, hogy tartsa a listán az első lufit, amely ugyanaz a lufi, amin Zuzanka egy húrt tart.

Valahol oldalra jelöljük az első léggömbtől a jelzést. Később szükségünk lesz rá.

Mondjuk Zuzankának, hogy húzza a sorban a második lufit.

Most nagyon fontos, hogy az első lufit Péter tartsa, mert különben örökké repülne!

Zuzanka jelenleg rövidebb listát tart, és végezhetünk. De még egy dolog!

Az első lufira már nem lesz szükségünk: a rajta festett jel már az oldalán is fel van tüntetve. Ebben az esetben szükségünk van rá robbantani. A dinamikusan kiosztott léggömbök (a malloc () keresztül allokálva) memóriát vesznek fel, és ha nincs rájuk szükségünk, akkor manuálisan kell felszabadítanunk a memóriát.

A memória felszabadítható a free () funkcióval .

A C-ben az elv az, hogy minden malloc () hívásnak legyen ingyenes () hívása. !

Az összefoglaló kód, hagyományosan sok hibával, a következőképpen fog kinézni:

Próbáljuk meg ellenőrizni egy üres tálca példáján:

A program valahol a c = z-> karakter körül van. Ha óvatosak voltunk az előző részben, akkor tudjuk, miért: A NULL mutatónak nincs karaktere.

Tehát ellenőriznünk kell, hogy nem véletlenül pattanunk-e ki egy üres edényből! Ha igen, akkor visszaadhatjuk a hagyományos \ 0 értéket .

Próbáljuk ki most:

Indítás után látni fogjuk:

Csavarja be a göndör konzolt! Ha jobban megnézzük, azt találnánk, hogy a pop () nem működik megfelelően: ugyanazt a legfelső elemet továbbra is kihúzzák a veremből, vagy más szavakkal: a függvény nem úgy működik, mint a pop (), de mint kukucskálni () .

Funkciónk egyetlen paramétert ad vissza: egy karaktert, de valójában két dolgot kell visszaadnunk! Nem csak egy karakter, hanem egy rövidebb magazin is!

Eddig húsdarálóként értettük a funkciót, amelybe beállítottuk a bemeneti paramétereket, és a feldolgozott eredmény kiesik a másik végéből.

De a C-funkciók működhetnek élelmiszer-feldolgozó-keverőként is, ahová betöltjük az adatokat, összekeverjük, majd kiválasztjuk belőle. Esetünkben a változót "össze kell kevernünk" a veremmel: pontosabban az első elemet kell kivágnunk belőle.

A paraméterek ilyen feldolgozását C-ben nevezzük paraméterek átadása referenciaként. A függvénynek hivatkozással elküldött változó nem csak bemenet (a darálóhoz halad), hanem bemenet/kimenet is. A függvény megváltoztathatja a benne lévő változó tartalmát, és a változások a függvény végrehajtása után is láthatók lesznek.

Ha egy változót bemenet-kimenetként akarunk megjelölni, akkor… HERE… mutatókat használunk!

A függvényfejléc a következőképpen fog kinézni:

Ebben az esetben a z változó a TRAY mutatójává válik. Ha nem a ZASOBNIK pontjával akarunk dolgozni, hanem a ZASOBNIK-mal, akkor a régi jól ismert eltérést, azaz az operátort * .

Kezdjük látni a csillagokat a szemünk előtt!

Mondhatni, hogy a bemeneti-kimeneti változókat csak mechanikusan kell megelőznie a dereference operátornak, és minden rendben lesz. Egy megjegyzéssel: ha van egy I/O változó, amely a * mutatót jelöli a struktúrához, és el akarunk férni annak elemeihez, akkor helyesen kell csatolnunk a kifejezést:

Próbáljuk ki az előző esetben ... De vigyázz! A storage_pop függvény már nem a TRAY-t veszi, hanem egy mutatót!

Ha van egy változónk, és meg akarjuk szerezni a címét (azaz mutatót kapunk rá), akkor használjuk referencia operátor: ampersand & .

Az és jel és a csillag barát operátorok: a csillag lefelé megy a nyílra, így a mutatóból kapja meg a tartalmat. Az ampersand pedig a memóriában kapja meg a címét egy adott változó számára, azaz mutatót ad vissza.

Kedves (más) hasonlat a szállodai szoba kulcsa: ha a kulcsok a kezedben vannak, akkor mutatót tartasz. A csillag azt jelenti, hogy besétálunk egy szobába, kinyitjuk, és felhasználhatjuk a készletét. A szobában használt amper jel azt jelenti, hogy megszerzi a kulcsokat.

Térjünk vissza arra, hogy a dolgokat a verem tetejére tegyük: a tray_push függvény "rendezettebbnek" tűnik, ha a pop szellemben állítjuk be: a TRAY bemeneti/kimeneti változót veszi fel, és nem ad vissza semmit.

Mivel a függvények C filozófiája gyakran a paraméterek referenciahívások útján történő visszaadása és a függvény sikerének/sikertelenségének visszatérési értékeinek visszaadása. (Így működik a scanf és az stdio.h számos funkciója.)

Ha megnézzük, mi történt, akkor azt tapasztaljuk, hogy… minden megvan, amire szükségünk van a tálcáról.

Itt az ideje, hogy elvégezzük a teljes algoritmust a bevezetéstől kezdve!

Eleinte a C hiányzó vereme szörnyű tragédiának tűnt, de őszintén szólva: nagyon gyorsan és hatékonyan megvalósítottuk. Valójában még megvalósítottuk is kapcsolati lista, bár csak az elején adhatunk hozzá elemeket, és csak az elejétől távolíthatjuk el őket.

Ugyanakkor számos ceccoid tulajdonságot mutattunk: mutatók, y struktúra és még paraméterek átadása referenciaként!