Dinamikus adatszerkezetek

Dinamikus memóriaelosztás

A p = select (N) függvény egy mutatót visz vissza az N hosszúságú memóriaterületre,

C, p = új (N) (egy határozatlan mutatótípus).

1) A mutató beírása.

Szigorú gépelési nyelveken az int * p és a char * g nem egyenértékű => típus konverzióra van szükség.

2) Engedje el az elkülönített memóriát

· Explicit mechanizmus (programozó) - elpusztítani (p);

· Nincsenek kifejezett mechanizmusok (OS) - megsemmisül, ha nincs hivatkozás az objektumra, lehetséges az időzítésen keresztül végrehajtani, programok befejezése után túlcsordulás esetén.

3) Az akasztás problémája (amikor egy dinamikus objektum egy másik dinamikus objektumra utal)

A memóriában vannak tárgyak, amelyeknek nincs referenciája. Ennek az objektumnak a megsemmisítésével elveszítheti a referenciáit az összes al-objektumára.

4) A lógó mutatók problémája (a megrongálódott tárgyakra való hivatkozások továbbra is fennmaradnak);

5) Memória fragmentálása

Destroy p3 és p5 - az új objektum elég memóriával rendelkezik, de nem lesz egyetlen

A dinamikus memóriával való munkavégzés szabályai kifejezett megsemmisítési mechanizmusok esetén:

1) Ne engedje meg a lógó tárgyak jelenlétét. Ehhez először el kell pusztítania az összes csatolt objektumot.

2) Ne hagyja a lógó kapcsolatokat, azaz az objektum megsemmisítése után törölje és hivatkozzon rá - p = NULL.

3) A fragmentáció minimalizálása. Ehhez el kell pusztítani az objektumokat a létrehozásuk fordított sorrendjében: p5 - p4 - p3.

A dinamikus memória mechanizmus végrehajtása C:

1) Dinamikus memória kiosztása a void * malloc (size_t size) függvény segítségével.

Például ha 10 tömb elemre van szüksége, akkor:

A szükséges size_t méret nagyobb lehet, mint a szükséges (az igazításhoz)

2) A function void * calloc (méret_t szám, méret_t méret);

a fogadott memória összes értéke nulla.

3) üres szabad (üres * p)

a mutató az előzőleg rögzített memóriablokkra mutat a műveletekkel malloc, calloc, realloc, azaz a szabadítandó bájtok száma = a rögzítés során kapott bájtok száma

konvertálja az int-et a szabad ((void *) A) érvénytelenítéséhez;

4) A function void * realloc (void * p, méret_t új méret)

Megváltoztatja a korábban rögzített memória blokk méretét, p - a mutató a blokk elejére, a méret méretét bájtban. A blokk áthelyezhető a memóriába, ha a méret megváltozik.

Fák. FOGALOMMEGHATÁROZÁSOK, OSZTÁLYOZÁS, MUTATÓ MÓDSZEREK.

A T alaptípusú fa:

1) Vagy egy üres fa

2) Vagy a T típusú csúcs véges számú társult fával, T típusú alapokkal (alsókkal).

(Egy csúcspont által hivatkozott fa - egy rész)

A csúcs, amelyre a másik csúcs közvetlenül hivatkozik, az leszármazottja. A fordított csúcs az őse.

A csúcs, amely nem lesz leszármazotta, egy fa levele.

Ha a csúcsokat számoljuk úgy, hogy minden egyes következő gyermek egy szinttel magasabb, akkor a 0-os csúcs a fa gyökere.

A csúcs, amely nem levél, belső csúcspontja.

Minden csúcs szintje a mélység (magasság). és maga a fa mélysége a csúcsok maximális mélysége.

A csúcsok azonnali leszármazottjainak számát egy adott csúcs fokának nevezik, a fák mértéke az összes lehetséges fok maximális.

Az ágak (szélek) száma, amelyeknek a gyökérről az x csúcsra kell haladni, úgy nevezzük, hogy az elérési út hossza x-re (a gyökérnek 0-as útvonala van).

Az egész fa útvonala (a belső útvonal hossza) az útvonal hosszainak összege az összes csúcsához.

Az átlagos útvonalhosszat a következő képlet határozza meg:.

A fát rendelésnek nevezik. ha minden csúcsból származó fióktelep is megrendelt.

A második fokú rendezett fák bináris fáknak nevezhetők.

Az n-edik (nagyobb, mint 2) fát nevezzük erősen elágazónak.

A minimális magasságú fákat tökéletesen kiegyensúlyozottnak nevezik (a csúcsok száma a bal és a jobb alsó rétegben legfeljebb 1 lehet - az összes csúcs feltételét).

Az ilyen rekurzív struktúrák kifejezésére hivatkozásokra van szükség.

Számos különböző módon lehet megjeleníteni a fákat (például egy bináris fa):

1) A bináris fák listájának ábrázolása a fa csomópontjainak megfelelő elemeken alapul. Minden elemnek van egy adatmezője és két mutató meze. Egy mutató segítségével az elemet a jobb gyermekhez lehet kapcsolni, a másik pedig balra. A levelek üres mutatói vannak a leszármazottaknak. Ezzel a fa ábrázolásával mindig mutasson egy mutatót a csomópontnak, amely a fa gyökere.

Megfigyelhető, hogy a reprezentációnak ez a formája hasonló az egyszerű lineáris listákhoz. És ez a hasonlóság nem véletlen. Valójában a bináris fa ábrázolásának módja egyfajta multisesszió, amelyet egy sor lineáris listák kombinációja alkot. Minden egyes lineáris lista kombinálja azokat a csomópontokat, amelyek az ösvényt a fa gyökerétől az egyik levelig belépték.

struct binary_tree * left;

struct binary_tree * right;

Ezután az üres fa egyszerűen úgy határozható meg, hogy a Root változót nullára állítja:
Root = NULL;

2) A tömb formájában a teljes bináris fa legegyszerűbben ábrázolható, mivel minden szinten szigorúan meghatározott számú csúcsot tartalmaz. A csúcsok egymás után balról jobbra számozhatók a szintek szerint, és ezeket a számokat indexként egydimenziós tömbben használhatjuk.

Dinamikus adatszerkezetek

Ha a fa szintjeinek száma nem változik jelentősen a feldolgozás során, akkor egy teljes bináris fa reprezentálása ezáltal sokkal gazdaságosabb lesz, mint bármelyik listák szerkezete.

A bináris fa reprezentált módjának fő hátránya, hogy az adatszerkezet statikus. A tömb méretét a bináris fák maximális lehetséges szintje alapján határozzák meg. És annál kevésbé teljes a fa, annál kevésbé racionálisan használják a memóriát.

BINÁRIS FÓLIA, MŰVELETEK.

Bináris fa - egy véges halmaza (csomópontok), amely üres vagy egy gyökér két különálló bináris részfák nevezzük balra és jobbra részfáját a gyökér.

A minimális magasságú n csúcsokkal rendelkező bináris fa létrehozásához a következő szabályokat kell használni:

0) Ha n = 0, akkor a vég;

1) Építsd fel a csúcsot

2) Hozzon létre egy bal oldali foltot csúcsokkal;

3) Hozzon létre egy jobb oldali szubtétet csúcsokkal.

Műveletek bináris fákkal:

· Prefix bypass - csúcs, bal, jobb (+ ab):

prefix_walk (struct binary_tree * t)

· Infix bypass - bal, csúcs, jobb (a + b);

· Postfix - bal, jobb, csúcs (ab +);

Az adatelemek egy egyedi kulcs értékének keresésekor bináris keresési fákat használnak a keresési fában - a jobb oldali> x (csúcs) alatti összes csúcs, a bal oldali szubtree összes csúcsa

N elemeket lehet szervezni egy bináris fához, amelynek magassága nem nagyobb, mint a log2 (N). ezért N elemek között keresni, nem feltétlenül több mint log2 (N) összehasonlítást igényel, ha a fa tökéletesen kiegyensúlyozott. Ebből következik, hogy egy fa megfelelőbb struktúra a keresés megszervezéséhez, mint például egy lineáris lista.

Kapcsolódó cikkek