A dinamikus tömb - studopediya

Egy tömb, amelynek mérete változtatható, míg a program az úgynevezett dinamikus. Más szóval, a dinamikus tömb - egy változó méretű adatszerkezet, amely lehetővé teszi a végrehajtása során a program automatikusan hozzáadni és eltávolítani az elemeket. A maximális méretét meg lehet határozni egy állandó vagy meghatározni a futás során. Az első esetben egy dinamikus tömb épül alapján statikus tömb, és a második - a hálózati, azaz olyan méretű, ami hozzá van rendelve a futás során. Előfordul, hogy a változó hosszúságú tömb venni, mint egy dinamikus tömb. De gyakran nem ez a helyzet, mivel a méret a második, amint említettük, automatikusan meg lehet változtatni, ami nem igaz az első. Például, a méret a bejelentett tömb A. n. ahol n - .. inicializált változó, azaz az elején a program, n nincs hozzárendelve semmilyen értéket. Feltételezzük, hogy az ár-érték, és vele együtt az a tömb méretét, a felhasználó által megadott. Ez arra enged következtetni, hogy az A - egy sor változó hosszúságú, de ez nem jelenti azt, hogy feltétlenül dinamikus, bár, mint már említettük, ez lehetséges.

Végrehajtása egy egyszerű dinamikus tömb alapján az alábbi manipuláció. Lekötött tömb rögzített méretű. Ez két részből áll: az első tömb üzletek dinamikus elemek, és a második egy tartalék helyet, amely alkalmazható, ha szükséges. Egy ilyen szervezet, akkor adjunk hozzá elemeket a végén egy dinamikus tömb, valamint törölheti őket, és mindezt változatlan időben. Ha a tömb teljes (teli mindkét oldalán az eredeti tömb), akkor azt mondjuk, hogy kimerítette a fizikai méretét; az elemek száma használt dinamikus tartalom a tömb, az úgynevezett logikai méretet.

A legtöbb jelenlegi magas szintű programozási nyelv támogatja a dinamikus tömbök. Együttműködik a legújabb vannak beépített operátorok és függvények, és néhány programozási nyelvek számos lehetőséget biztosítanak azok végrehajtását. Például, a C ++ lehet használni erre a célra:

· Malloc funkció calloc, realloc és ingyenes;

Példa a teremtés és tisztítása egész dinamikus tömb álló 33 elem:

int * A = malloc (sizeof (int) * 33); // Létrehozunk

· Az üzemeltetők új és törlése (ezek is csak egy módja annak, hogy változtatni a méret a tömb -, hogy teljesen tiszta it);

Példa a teremtés és tisztítása valós dinamikus tömb álló 11 elemek:

float * A = új float [10]; // Létrehozunk

törölni [] A; // eltávolítás

Példa a teremtés és tisztítása egész dinamikus tömb álló 22 ​​elemek:

vektor A (22); // Létrehozunk

Fent, példák mutatták három módon, hogy hozzon létre egy dinamikus tömb és tisztítása C ++. De ez nem minden jellemzője a nyelvet. Például, vektor osztály egy sor módszerek eléréséhez az elemek, hozzátéve, és eltávolítja őket, és így tovább. N.

A Pascal dinamikus tömb lehet meghatározni két módon. Az első magában foglalja a használata az eljárás új, és a második SetLength eljárást. Mindkét esetben az első tömb nyilatkoznak:

var <имя массива>: Array <тип данных>;

Ezt követően, a fő egység segítségével az egyik eljárások:

<имя массива>: = Új <имя типа>[<значение>]

SetLength (<имя массива>, <значение>);

SetLength eljárás és az új tartalék hely a memóriában a dinamikus változót (ebben az esetben a dinamikus tömb).

Egy átlagos statikus tömb dinamikus győzelem sebesség, amely kompenzálja továbbfejlesztett funkciók az utóbbi. Általában, az idő összetettsége az alapvető műveletek a dinamikus elemek a tömb az alábbiak szerint:

Hozzáférés egy elem által index végezzük állandó időben O (1);

· Beszúrása vagy törlése elemek:

- kezdve a tömb: O (n) (lineáris idő);

- középső tömb: O (n) (lineáris idő);

- végén a tömb: O (1) (a konstans idő).