Dinamikus listák pascal-Pascal - Pascal - Programozás - cikk Directory

Dinamikus adatszerkezetek (kb megtalálható a fórumon)

Az adat objektum dinamikus szerkezetet, ha a mérete változik végrehajtása során a program vagy potenciálisan végtelen.

Osztályozása adatstruktúrák

Programozására használjuk az adatokat lehet osztani két fő csoport:

Ezek statikus szerkezet - ezeket az adatokat, a relatív helyzete és a kapcsolatok az elemek, amelyek mindig állandó marad.

Dinamikus adatstruktúra - ezeket az adatokat, a belső szerkezete van, amelyet bármely törvény, de az elemek száma és azok relatív kapcsolata dinamikusan változtatható program végrehajtása során, a törvény szerint a kialakulását.

Dinamikus adatszerkezet:

A dinamikus struktúra adatfájlok közé tartoznak, nem kapcsolt és kapcsolt dinamikus adatokat.

Megjegyezzük, hogy a fájlokat a besorolás rendelt dinamikus adatszerkezeteket. Ez alapján történik a fenti definíció. Bár eltávolítása és behelyezése elemek középre a fájl nem engedélyezett, de a hossza a fájlt a program változtatásának jogát - növelheti vagy csökkentheti a nullához. És ez a dinamikus tulajdonságokat a fájl adatstruktúraként.

A statikus és dinamikus változók Pascal

Dinamikus memória (DP) - a memória PC program által biztosított a működése során, kevesebb adatot szegmens (64K), a köteg (16 Kb) és a tényleges test a program. dinamikus memória mérete változó lehet. Default DP - minden rendelkezésre álló memóriát a PC.

DP - valójában az egyetlen lehetőség a folyamat nagy tömbök dimenzió adatokat. Sok gyakorlati problémák nehéz vagy lehetetlen megoldani a DP. Például a fejlesztés CAD statikus memória kiosztás lehetetlen, mivel A dimenzió matematikai modellek különböző projektekben jelentősen változhat.

Együttműködik dinamikus változó a program a következő lépéseket kell követni:

• memóriafoglalási dinamikus változó;
• Inicializálása a mutató;
• Memória felszabadítása után egy dinamikus változó.

A programozó maga kell foglalni a helyet, hogy meghatározza az értéket a mutató, engedje el a DP.

Ehelyett használjon statikus változó dinamikus, de anélkül, hogy valóban szükség van erre nem éri meg.

Pointer kapcsolatos néhány konkrét adattípus, az úgynevezett típusos pointer. Az ő leírása a következő:

A mutató, amely nem kapcsolódik semmilyen különösebb típusú adatok nevezzük típustalan mutatót. Leírni típustalan mutatókat Pascal van egy szabványos típusú mutató. Leírás Az indikátor a következő:

Alapján pointerek segítségével, amely típustalan dinamikusan osztja az adatok szerkezete és típusa változó a program végrehajtása során.

Az ember azt várná, hogy az érték a mutató lehet vezetni a másikra. Sőt, akkor át értékeket csak közötti mutatókat társított egy adattípust. Rámutatnak a különböző típusú adatok a különböző típusú, és ezek a típusok nem kompatibilisek.

Ez a korlátozás azonban nem vonatkozik olyan típustalan mutató. A program magában foglalja a következő műveletek engedélyezve lesz:

Kiosztása és felszabadítva dinamikus memória

Minden DP minősül folyamatos bájttömböt hogy hívják kupac.

Elhelyezkedés kupac a PC memória.

• Heaporg - az elején a kupac;
• Heapend - a végén a kupac;
• Heapptr - a jelenlegi korlátozás üres DP.

Memóriakezelését keretében végzett dinamikus változó eljárás:

Grafikailag az új cselekvési eljárásokat is képviselteti magát az alábbiak szerint:

Elengedte a kupac járunk el:

Példa eljárást programot fragmenst megsemmisíteni

Ne feledje, hogy az ismételt eljárások felett szabadon mutató vezethet hiba.

dispose eljárás felszabadítja a memóriát által hozott dinamikus változó. Ebben az esetben a mutató nem definiált.

Bármilyen akció a mutatót a program között található az új eljárások és ártalmatlanítani.

Amikor a dinamikusan allokált változók gyakran felmerül egy általános probléma az úgynevezett dinamikus memória szivárgás. memóriavesztés - ez a helyzet, amikor teret osztják a kupac, majd elvesztette - valamilyen oknál fogva, a mutató nem több, mint az elkülönített területen, így nem tud helyet szabadítson fel. A leggyakoribb oka a memória szivárgás van rebindings dinamikus változók nélkül, az előző kiadás. A legegyszerűbb esetben a következő:

Példa program fragmenst

var IntPointer: ^ egész;
kezdődik
Új (IntPointer);
Új (IntPointer);
végén.

Az első hívást az új kupac elkülönített 2 bájtot, és állítsa IntPointer mutatót. A második hívás Új kiemeli másik 2 bájt, és IntPointer telepítve rájuk. Most már nem kell egy mutatót az első 2 byte, tehát nem lehet kioldani őket. A program ezen byte fog veszni.

Hozzárendelése a mutatót

Inicializálni mutatók több lehetőség is van.

pointer működés

Pointerek csak meghatározott értékadó operátor, és ellenőrizzük az egyenlőség vagy egyenlőtlenség. A Pascal tilt minden aritmetikai műveletek mutatók, azok input-output és az összehasonlítás több-kevesebb.

Ismét a megbízás szabályai mutatók:

• Meg lehet rendelni bármelyik index nulla szabvány állandó, ami azt jelenti, hogy az index nem utal semmilyen konkrét memória cella;
• szabványos típusú mutató pointerek mutatókat kompatibilis minden típusú;
• mutató, amely egy adott adattípus lehet rendelni csak a mutató értéke azonos adattípusok vagy szabvány.

Pointerek lehet hasonlítani az egyenlőség vagy egyenlőtlenség, például:

Ha p1 = p2 majd ... ..
Ha p1<>p2 majd ... ..

standard függvények vannak definiálva Pascal pointerek:

Ha értékeket a dinamikus változók

Dinamikus elosztás adatokat fel lehet használni bárhol a programban, amely lehetővé tette a megfelelő, típusú kifejezések.

R ^: = sqr (R ^) + I ^ -17;
q ^: = 2; Inc (q ^); writeln (q ^)

Megengedhetetlen, hogy kifejezéseket használ, mint például a következők:

Tekintsük a példát dolgozik mutatók:

dinamikus struktúrák

Lineáris listák (egyirányú lánc).

List egy adatstruktúra, ahol minden elem egy pointer társított következő elem.

Minden eleme a láncolt listában az első helyen, tartja néhány információ, másrészt rámutat arra, hogy a következő elem. Mivel a lista elem tárolja a különböző típusú (tárolt információk és a pointer), akkor természetes, hogy képviselje a rekordot, amelynek területén található egy tárgy, a másik - egy mutatót a következő rekordot az azonos típusú. Ez a rekord az úgynevezett link. és a szerkezet ezen bejegyzések nevezzük lista, vagy egy lánc.

Csak az első elemet a listában (a fej), egy külön index. Az utolsó elem a listában nem jelzi.

Leírás listája

Példa Leírás lista

Típus Térkép = ^ S;
S = rekord
Inf: integer;
Következő: Térkép;
Vége;

A Pascal van egy alapvető szabály, hogy le kell írni, mielőtt bármilyen tárgy. Ez alól kivételt képeznek csak a mutatók, amelyek lehet hivatkozni még be nem írja.

Listájának létrehozása

Hogy lista létezett, akkor meg kell határozni egy mutatót az elejétől.

Példa Leírás lista

Típus Térkép = ^ S;
S = rekord
Inf: integer;
Következő: Térkép;
Vége;

Hozzunk létre az első lista elem:

Továbbra is létrehozhat egy listát. Ehhez hozzáadunk egy elemet sem a lista végén, vagy a fejét.

A) Elemek hozzáadása a lista fejét. Ehhez el kell végezni egy műveletsor:

• kap memóriát az új elem;
• tegye vissza az információt;
• csatolja az elemet a lista fejét.

Míg u<> nulla do
kezdődik
WriteLn (u ^ .inf);
u: = u ^ .next;>
végén;

Ha eltávolít egy elemet a listából

A) eltávolítása az első tag. Ebből a célból a másodlagos index emlékezni fog az első tételt, egy mutatót a lista élére, hogy váltson a következő elemet a listában, és szabad a régióban a kupac, ami azt jelzi, al-index.

X: = u;
míg a (X<> nil) és (x ^. inf<> számjegy) do
kezdődik
dx: = x;
X: = x ^ .next;
végén;
dx: = x ^ .next:
dobja (x);

B) eltávolítása a végén a lista. Ehhez meg kell találni az utolsó előtti elem.

X: = u; dx: = u;
míg X ^ .next<> nulla do
kezdődik
dx: = x; X: = x ^ .next;
végén;
dx ^ .next: = nil;
dobja (x);

Passage a lista. Fontos, hogy képes rendezni a lista elemeit, végre minden műveletet. Tegyük fel, hogy meg akarjuk találni az összeg elemek listáját.

Summa: = 0;
X: = u;
míg x<> nulla do
kezdődik
Summa: = Summa + x ^ INF;
X: = x ^ .next;
végén;

Dinamikus objektumok bonyolult szerkezetű

Használata egyirányú listák okozhat némi nehézséget megoldásában számos problémát. Az a tény, hogy a tulajdonosa lista csak egy irányban mozog, a lista élére, hogy az utolsó láncszem. Közben gyakran szükséges ahhoz, hogy egy műveletet az elem megelőző eleme a kívánt tulajdonságokkal. Azonban miután az elem egy adott ingatlan egy egyirányú listában, akkor nincs módja, hogy gyorsan és kényelmesen hozzáférni az előző elemre.

Típus Térkép = ^ S;
S = rekord
Inf: integer;
Következő: Térkép;
Pred: Térkép;
Vége;

Dinamikus szerkezet, amely egységek a típusú úgynevezett kétirányú listát. amely sematikusan a következőképpen:

A programozás, kétszeresen láncolt listák gyakran következőképpen általánosítható: a mező értéke az utolsó láncszem a Next, hogy egy hivatkozás a title elem, valamint a mező értéke Pred címlinkre - egy linket az utolsó láncszem:

Vannak különböző módszerek segítségével a dinamikus listákat:

• Stack - egy speciális típusú lista, ahová a belépés csak egy mutató az első elemet. Ha azt szeretnénk, hogy a halomra elem bekerül előtt az első elem, a mutatót a verem tetején van kapcsolva az új elemet. Az algoritmus a verem jellemzi a szabály „utolsó - első ki”.
• Sor - listás, amelynek két mutató az első és utolsó eleme a lánc. Az új elemek vannak írva, miután az utolsó, és a minta komponensei az első. Az algoritmus az „elsőnek jött - elsőnek ki”.
• Lehet szervezni listákat véletlen hozzáférésű az elemeknek. Ebben az esetben szükség van egy további mutató az aktuális elem.

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.

? 200 '200px': '' + (this.scrollHeight + 5) + 'px'); „>
Program Srednee;
Const nmax = 10000;
Írja Diapazon = 1..NMax;
MasInt = Array # 91; Diapazon] egész szám;
MasReal = Array # 91; Diapazon] Real;
Var PIint. ^ MasInt; PReal. ^ MasReal;
I, Midint. longInt; MidReal. Valódi; T. szöveg; S. string;
kezdődik
Write ( 'Add meg a fájl nevét:' # 41 ;; ReadLn (S # 41 ;;
Hozzárendelése (T, S # 41 ;; visszaállítása (T # 41 ;; MidReal: = 0; MidInt: = 0;
Véletlenszerű;
NEW (PReal # 41 ;;

Bár nem EOF (T # 41; Do
Kezdjük ReadLn (T, PReal ^ # 91; I] # 41 ;; MidReal: = MidReal + PReal ^ # 91; I] Vége;
ÁRTALMATLANÍTANI (PReal # 41 ;;
NEW (pint # 41 ;;

Mert: = 1 To Do NMax
Kezdjük pint ^ # 91; I]: = -100 + Random (41 # 201 ;; MidInt: = MidInt + pint ^ # 91; I] Vége;

WriteLn ( 'átlagos egész szám, értéke:', MidInt Div NMax # 41 ;;
WriteLn ( 'átlagos valós is:', (MidReal / NMax # 41;. 10. 6 No. 41;
Vége.

// C ++ nyelven
#include
#include
#include
#include
#define NMax 10000
typedef int MasInt;
typedef úszó MasReal;
MasInt * pint; MasReal * PReal;
int i, n, MidInt; float MidReal; char S # 91; 255];
FILE * t; char * endptr;
void main (# 41;
> S;
t = fopen (S, "r" # 41 ;;
MidReal = 0; MidInt = 0;
randomize (# 41 ;; i = 0;
/ * Memóriát kiosztani hagyományos tömb * /
PReal = (MasReal * # 41; malloc (sizeof (MasReal # 41; # 41 ;;
/ * A bemeneti és összegzés valós tömb * /
while (feof (t # 41; #! 41;
PReal # 91; I] = strtod (S, endptr # 41 ;; // átalakítani a bemeneti karakterlánc egy valós szám
MidReal + = PReal # 91; I]; I ++;>
n = i + 1;
ingyenes (PReal # 41 ;; / * Törlés valós tömb * /
Pint = (MasInt * # 41; malloc (sizeof (MasInt # 41; # 41 ;; / * memóriát lefoglalni tömb alatt * /
/ * Számoljuk az összeg a teljes tömb * /
for (i = 0; I MidInt + = pint # 91; I];>
/ * A kijelző az átlagértékek * /
cout <<"\nсреднее целое равно " < cout <<"среднее вещественное равно: " < fclose (t # 41 ;;
>

Készítsen programot, amely alapján egy előre meghatározott lista képezi a két másik, forgalomba az első közülük pozitív és a második - negatív eredeti lista terméket.

? 200 '200px': '' + (this.scrollHeight + 5) + 'px'); „>
Program Ex_sp_1;
Felhasználás Spisok;
Var S1, S2, S3, V1, V2, V3. U; A. BT; I, N. bájt;
kezdődik
Véletlenszerű;
N: = 1 + Random (20 # 41 ;;
S1: = Nil; A: = -100 + Random (41 # 201 ;;
V_Nachalo (S1, A # 41 ;; V1: = S1;
Az I: = 2 és n Do
Kezdődik egy: = -100 + Random (41 # 201 ;; V_Spisok (V1, A # 41 ;; V1: = V1 ^ .Next End;
WriteLn (ravaszt lista '# 41 ;; Print (S1 # 41 ;;
V1: = s1; S2: = Nil; S3: = Nil;
Míg V1 <> nulla Do
kezdődik
Ha V1 ^ inf> 0
Akkor, ha S2 = Nil
Ezután kezdődik V_Nachalo (S2, V1 ^ .inf # 41 ;; V2: = S2 End
Else Begin V_Spisok (V2, V1 ^ .inf # 41 ;; V2: = V2 ^ .Next vége;
Ha V1 ^ inf <0
Akkor, ha S3 = Nil
Ezután kezdődik V_Nachalo (s3, V1 ^ .inf # 41 ;; V3: = S3 End
Else Begin V_Spisok (V3 V1 ^ .inf # 41 ;; V3: = V3 ^ .Next vége;
V1: = V1 ^ .Next
Vége;
WriteLn ( 'A kapott listája pozitív elemek:' # 41 ;; Print (S2 # 41 ;;
WriteLn ( 'A kapott lista negatív elemek:' # 41 ;; Print (S3 # 41 ;;
Ochistka (S1 # 41 ;; Ochistka (S2 # 41 ;; Ochistka (S3 # 41 ;;
Vége.

---