A dinamikus adatok szerkezetét listák

A korábbi cikkekben megnéztük a programozással kapcsolatos feldolgozását csak statikus adatokat. Statikus változók azok, amely számára fordítási időben, és megmarad az egész programot.

A programozási nyelvek (Pascal, C, et al.), Van egy másik módszer elosztásának memória az adatok, amelyek az úgynevezett dinamikus. Ebben az esetben a memória rendelt érték a futás során. Ezek az értékek fogják hívni dinamikus. KATEGÓRIA memória kell elosztani statikusan, az úgynevezett statikus memória; dinamikusan memóriát része úgynevezett dinamikus memória (kupac memória).

Használata dinamikai mennyiségek ad a programozó számos további funkciókat. Először is, a dinamikus memória kapcsolat megnöveli az adatok feldolgozása folyamatban van. Másodszor, ha a szükség semmilyen adat megszűnik vége előtt a program, akkor a memória általuk elfoglalt lehet szabadítani az egyéb információkat. Harmadszor, a dinamikus memória lehetővé teszi, hogy a változó méretű adatszerkezeteket.

A dinamikus értékek használatával összefüggő más típusú adatok - referencia típus. Változók referencia típus, az úgynevezett mutatók.

Következő megbeszéljük részletesebben mutatók és intézkedések velük a nyelvet Pascal, példák vezet Pascal és C

Nagysága a referencia típusú (pointer) van leírva a leíró részben változókat az alábbiak szerint:

Íme néhány példa az leírásai jelek:

Itt P1 - egy mutatót a dinamikus az egész szám típusú; P2 - mutató dinamikus típusú érték string; Pm - egy mutatót a dinamikus tömb típusú pontban meghatározott típus.

Sami dinamikus mennyiségek nem igényel a program leírását, mert a fordítás során memória számukra kiosztott. Fordítási időben, memóriát csak egy statikus érték. Pointerek - egy statikus érték, ezért szükség van egy leírás.

Hogyan, akkor ez alapján történik a memória dinamikus érték? Memória dinamikus társított értéket mutató elengedi végre a szokásos eljárás ÚJ. Format igénybevételének ezt az eljárást:

Úgy véljük, hogy ez a kijelentés után létrehoz egy dinamikus érték, amelynek a neve a következő:

Hagyja, hogy a program, amely a fenti leírás, ott vannak a következő állítások:

Miután a végrehajtás szentelt teret három értéke (két skalár és egy tömb), amelyek azonosítókat dinamikus memória:

Például, a P1 ^ szimbólum lehet dekódolni a következőképpen: a dinamikus változó, amely által hivatkozott P1 mutató.

További munka a dinamikus változók pontosan ugyanaz, mint a statikus változók megfelelő típusú. Ezek értéket adhatunk, akkor lehet használni, mint operandusok kifejezést, paraméterek, rutin és így tovább. Például, ha a változó P1 ^ kívánja rendelni a 25-ös szám, a változó P2 ^ értéket rendelni a „Write” szimbólum, és egy sor Pm ^ töltse ki a sorrendben egész számok 1 és 100, ez történik az alábbiak szerint:

Amellett, hogy az eljárás ÚJ pointer értéke lehet meghatározni az értékadó operátor:

Referenciaként használja a kifejezést

  • pointer;
  • egy referencia funkciót (azaz egy olyan függvény, amelynek értéke egy pointer);
  • állandó Nil.

Nil - fenntartott állandó, jelezve egy üres kapcsolat, azaz a hivatkoznak, hogy bármi nem pont. Ha hozzá az alapvető típusa mutató és referencia kifejezéseket meg kell egyeznie. Állandó Nil lehet rendelni egy mutatót tartalmaz, amely alap típus.

Mielőtt hozzárendel egy értéket a referencia változó (az értékadó operátor vagy egy eljárás NEW) bizonytalan.

A bemeneti és kimeneti mutatók nem engedélyezettek.

Vegyünk egy példát. Hagyja, hogy a leírt program az alábbi mutatókat:

Akkor érvényes hozzárendelés operátorokat a tisztelt típusú elvét. Az üzemeltető K: = D hibás, mivel alaptípust a jobb és a bal oldali eltérő.

Ha a dinamikus érték elveszíti mutatót, akkor lesz egy „szemét”. A programozás során ezt a szót információkra utal, hogy vesz memóriát, de már nincs szükség.

Képzeljük el, hogy a programban, ahol olyan mutatókat részben fenti állítások írva a következő:

Így egy dinamikus változó értéke 5, elvesztette mutató és elérhetetlen lett. Ugyanakkor a memóriát foglal. Ez egy példa a megjelenése „szemetet”. Ez az ábra azt mutatja, hogy mi történt eredményeként az üzemeltető P: = D.

A Pascal van egy szabványos eljárás, amely lehetővé teszi, hogy szabad memória az adatokat, amelyek szükségességére eltűnt. A formátum:

Például, ha a dinamikus változó P ^ már nincs szükség, az üzemeltető

távolítsa el a memóriában. Ezt követően, a mutató értéke P bizonytalanná válik. Különösen hatása jelentőssé válik a memória megtakarítás eltávolításakor nagy tömbök.

A változat a Turbo Pascal, alatt futó MS DOS operációs rendszer, 64 kilobájt memóriát egy program (vagy, pontosabban, 65.520 bájt). Ez egy statikus memória területet. Ha szükséges, a munka nagy tömbök információ, hogy lehet, hogy nem lesz elég. Kupacmérete - sokkal nagyobb (több száz kilobájt). Ezért a dinamikus memória jelentősen megnöveli az adatok feldolgozása folyamatban van.

Világosan meg kell érteni, hogy a munka dinamikus adatokkal lassítja a program végrehajtását, mivel hozzáférést biztosít az értéket két lépésben zajlik: először egy pointer kérik, akkor - értéket. Amint az gyakran előfordul, úgy viselkedik, „megmaradási törvénye baj”: a nyereség a memóriában ellensúlyozza az időveszteség.

Példa. Adott egy szöveges fájl, ami nem nagyobb, mint 64 Kb tartalmaz valós szám, egy-egy sorban. Felülírja a fájl tartalmát egy tömb, helyezze azt egy kupacban. Kiszámítjuk az átlagos értéke az elemek a tömb. Tiszta kupac. Hozzon létre egy egész tömb mérete 10000, töltse meg véletlen egész számok a -100 és 100, és számítsuk ki az átlagos értéket.

Megbeszéljük a kérdést, hogy a kupac, akkor létrehozhat egy olyan struktúra változó méretű adatokat.

Nézzük a következő példát. Ennek során a fizikai kísérlet, leolvasásokat több alkalommal (például hőmérővel), és rögzíteni kell a számítógép memóriájában további feldolgozásra. Nem ismert, hogy hány lesz méréseket.

Ha az ilyen adatok feldolgozása nem használ külső memória (fájlok), célszerű elhelyezni őket egy kupacban. Először is, a dinamikus memória tárolását teszi lehetővé nagyobb mennyiségű információt, mint a statikus. És másodszor, a dinamikus memória, ezek a számok lehet elhelyezni egy kapcsolt listán, amely nem igényel előre meghatározott számú számok, mint tömb. Mi az a „láncolt lista”? Vázlatosan ez így néz ki:

itt Inf # 151; Link információk a listán (az érték minden egyszerű vagy strukturált típusú, kivéve a fájl), Next # 151; egy mutatót a következő hivatkozás a listán; első # 151; egy mutatót a cím lista link.

A definíció szerint egy lista található a kupac, egy link mutatót a cím alatt statikus memóriát. A szerkezet, ellentétben a tömb, valóban dinamikus: egység létrehozására és törlésére, ha szükséges a program végrehajtása során.

Van BT # 151; néhány alapvető típusa listában terméket.

Ha a mutató csupán a következő hivatkozás a listán (amint az a fenti szerkezet a bejelentett), akkor egy ilyen lista úgynevezett egyirányú. Ha a következő és az előző hivatkozások # 151; kétirányú lista. Ha a mutatót az utolsó láncszem nincs telepítve Nil, és a cím utal a kapcsolat listán, ez a lista az úgynevezett gyűrűt. Gyűrű lehet egyirányú és kétirányú listák.

Ha közelebbről szemügyre vesszük a munka kapcsolt listák példát egyirányú, nem gyűrűs listán.

Különbséget teszünk a tipikus műveletek jelent meg:

  • hozzáad egy linket a lista tetején;
  • eltávolítja a link lista elején;
  • egy link hozzáadása egy tetszőleges helyen listát eltérő az elejétől (például, miután a link mutató, amely meg van adva);
  • eltávolítjuk a Link lista egy tetszőleges helyen más, mint az elején (például, miután a link mutató, amelyhez be van állítva);
  • ellenőrizze, hogy a lista üres;
  • Listájának törlése;
  • lista nyomtatás.

Végre egy olyan dedikált műveletek egy modult. Csatlakoztatja ezt a modult, akkor lehet, hogy megoldja a leggyakoribb feladatokat a lista. Hagyja, hogy a lista nyilvánították a fent leírtak szerint. Az első négy lépésben, először eladni külön, biztosítva számukra illusztrációk.

1. hozzáadása egy link a lista elejére