Capitolul 8

Capitolul II. Alocarea dinamică a memoriei în Turbo Pascal. Structuri dinamice

Yüklə 0,55 Mb.

səhifə	3/4
tarix	07.09.2018
ölçüsü	0,55 Mb.
	#79713

1 2 3 4

Capitolul II. Alocarea dinamică a memoriei în Turbo Pascal. Structuri dinamice

Folosind datele cu structură implicită (statică), putem rezolva reprezentativ o clasă limitată de probleme. În multe cazuri relaţiile dintre componente nu numai că se modifică dinamic, dar în acelaşi timp, pot deveni deosebit de complexe.

De exemplu, în cazul unui şir de aşteptare la o casă de bilete relaţiile dintre persoane se modifică: persoanele nou-sosite se aşază în rînd; persoanele în criză de timp pleacă fără să-şi mai procure bilete; persoanele care au plecat pentru un timp îşi păstrează rîndul ş.a.m.d. În astfel de situaţii utilizarea datelor cu structură implicită devine nenaturală, dificilă şi ineficientă.

Prin urmare, este necesară folosirea unor structuri de date în care relaţiile dintre componente să fie reprezentate şi prelucrate în mod explicit. Acest efect se poate obţine ataşînd fiecărei componente o informaţie ce caracterizează relaţiile acesteia cu alte date ale structurii. În cele mai multe cazuri, informaţie, numită informaţie de structură, se reprezintă prin variabile de tipul referinţă. Astfel de structuri de date se numesc dinamice. Structurile dinamice frecvent utilizate sunt: listele unidirecţionale, listele bidirecţionale, listele circulare, stivele, cozile, arborii.

O structură de date este recursivă dacă ea poate fi descompusă în date de aceeaşi structură. De exemplu, listele unidirecţionale, arborii.

Astfel, pentru structurile statice memoria se alocă la începutul execuţiei programului şi rămîne alocată pînă cînd se încheie execuţia acestuia. Pentru structurile dinamice se alocă memorie în timpul execuţiei programului, iar cînd nu mai este necesară, memoria se eliberează.

Din punct de vedere al unui programator, memoria calculatorului se prezintă ca o succesiune de octeţi, fiecare octet avînd o adresă binară bine stabilită. Aceşti octeţi sunt identificaţi prin numere cuprinse între 0 şi n-1. Convenim să numim adresă numărul de ordine al unui octet. Un octet este format din 8 biţi. Fiecare bit poate memora fie cifra binară 1, fie cifra binară 0, diversele tipuri de date cunoscute pînă acum (integer, real) ocupă 2 sau mai mulţi octeţi consecutivi. Pentru fiecare tip de dată cunoscut există o anumită logică potrivit căreia se face memorarea efectivă a conţinutului. De exemplu, pentru tipul integer memorarea se face în cod complementar. O variabilă folosită de noi în program are un nume (simbolic), o valoare şi o adresă la care o găsim memorată (adresa primului octet din cei p octeţi consecutivi ocupaţi de variabilă). În general, nu este necesar ca programatorul să cunoască adresa la care se găsesc variabilele cu care lucrează.

Se cunosc două forme de alocare a memoriei de către programator în cadrul limbajului Pascal: statică şi dinamică.

Utilizînd forma de alocare statică, variabilele se declară utilizînd cuvîntul cheie var la începutul programului.
Utilizînd forma de alocare dinamică, în timpul rulării programului, în funcţie de necesităţi, se alocă memorie suplimentară sau se renunţă la ea.

Pentru alocarea dinamică utilizăm tipul de date referinţă. Se consideră secvenţa de program:

type ref=^inr;

inr=record

nr:integer;

adrurm:ref

end;

var c:ref;

Aici variabila c este o variabilă de tip referinţă. Ea reţine adrese de înregistrări. La rîndul ei, o înregistrare are două cîmpuri: nr, care reţine un număr întreg (informaţia utilă) şi adrurm (adresa următoare), care reţine adresa unei alte înregistrări.

Procedura new(c) rezervă spaţiu (un număr de octeţi cosecutivi) pentru o înregistrare, adresa primului octet fiind depusă în variabila c. Presupunem că variabila c conţine adresa unei înregistrări.

Procedura dispose(c) eliberează spaţiul de memorie afectat acelei înregistrări care avea adresa în c. Cuvîntul cheie nil are semnificaţia “nici o adresă”.

Observaţii:

c se referă la adresa care se găseşte în variabila c;
c^.nr se referă la cîmpul numeric al înregistrării care are adresa memorată în variabila c;
c^.adrurm semnifică adresa de înregistrare care se găseşte memorată în cadrul înregistrării care are adresa c;
c^.adrurm.nr semnifică variabila nr care se găseşte în înregistrarea care are adresa plasată în cîmpul adrurm al înregistrării cu adresa c.

Important: spaţiul necesar variabilelor alocate dinamic se rezervă într-o zonă de memorie, special destinată numită heap (pentru PC compatibile I.B.M.).

Listele înlănţuite, stivele, cozile sunt structuri dinamice de date.

§1. Lista liniară simplu înlănţuită

O listă liniară simplu înlănţuită este o structură de forma:

	in1	adr2			in2	adr3			inn	nil
adr1				adr2				adrn

Semnificaţia notaţiilor folosite este următoarea:

adr1, adr2,…,adrn reprezintă adresele din memorie ale celor n înregistrări;
in1, in2,…, inn reprezintă informaţiile utile din cele n înregistrări (altele decît cele de adresă pentru înregistrarea următoare ).

Denumirea "simplu înlănţuită" provine din faptul că fiecare element al listei conţine o singură adresă, şi anume adresa elementului următor din listă. Aici avem o excepţie pentru ultimul element, care are în cîmpul de adresă cuvîntul cheie nil (semnificînd “nici o adresă”). Operaţiile pe care le putem face în legătură cu această structură de date sunt următoarele:

creare;
listare;
adăugare;
ştergere;

În programul care urmează aceste operaţii sunt realizate de procedurile cu acelaşi nume (facem precizarea că, în program, informaţiile utile sunt date de numerele 1,2,…,n). Am recurs la această cale din dorinţa de a simplifica pe cît posibil prezentarea.

Creare

Se cere numărul n de înregistrări. Se creează o primă înregistrare avînd ca informaţie utilă numărul 1. Variabila b de tip referinţă reţine adresa primei înregistrări din listă. Pentru fiecare i cuprins între 2 şi n se adaugă cîte o nouă înregistrare listei. Variabila d reţine adresa ultimei înregistrări deja create pentru a-i completa cîmpul de adresă. Se procedează astfel pentru că în momentul în care am creat o înregistrare nu se cunoaşte adresa înregistrării care urmează.

Listare

Am precizat faptul că b reţine adresa primei înregistrări. Pentru a nu deteriora această valoare, o vom memora în variabila c . Atît timp cît nu am ajuns la sfîrşitul listei, tipărim informaţia utilă şi încărcăm în c adresa înregistrării următoare.

Adăugare

Operaţia de adăugare a unui nou element la listă comportă cunoaşterea a două informaţii:

Informaţia utilă a elementului (înregistrării) din listă după care urmează să se facă adăugarea;
Informaţia utilă a elmentului care urmează să fie adăugat.

Adăugarea propriu-zisă constă în următoarele:

Poziţionarea pe înregistrarea după care urmează să adăugăm noua înregistrare;
Alocarea spaţiului pentru noua înregistrare;
Completarea informaţiei utile pentru aceasta;
Completarea adresei următoare a noii înregistrări, care va fi adresa următoare a înregistrării pe care suntem poziţionaţi;
Cîmpul de adresă al înregistrării pe care suntem poziţionaţi va lua ca valoare adresa noii înregistrări.

Observaţie: Aşa cum este concepută procedura, nu se poate adăuga o primă înregistrare listei.

4) Ştergerea

Pentru a şterge o înregistrare este necesar să cunoaştem informaţia utilă a acesteia. Vom proceda în mod diferit pentru situaţiile în care se şterge prima înregistrare sau una diferită de prima.

În cazul în care ştergem prima înregistrare, efectuăm operaţiile:

Se salvează în variabila c adresa primei înregistrări (cea care urmează a fi ştearsă);
Variabila b (care reţine adresa primei înregistrări) va lua ca valoare adresa următoare primei înregistrări;
Se eliberează spaţiul rezervat înregistrării şterse;

În situaţia în care ştergem o altă înregistrare decît prima, procedăm în felul următor:

Se face poziţionarea pe înregistrarea care urmează a fi ştearsă;
Cîmpul de adresă al înregistrării precedente capătă valoarea cîmpului de adresă al înregistrării curente;
Eliberăm spaţiul rezervat înregistrării curente.

program lln;

type ref=^inr;

inr=record

nr:integer;

adrurm:ref

end;

var b,c,d:ref;

n,i: integer;

procedure creare;

begin

write (‘n=’); readln(n);

new ( c); c^.nr:=1;

b:=c; d:=c;

for i:=2 to n do

begin

new ( c);

c^.nr:=i;

d^.adrurm:=c;

d:=c

end;
procedure listare;

begin

c:=b;

while c<>nil do

begin

writeln( c^.nr);

c:=c^.adrurm

end

end;
procedure ştergere;

begin

write (‘i=’); readln(i);

if i=1 then

begin

c:=b;

b:=b^.adrurm;

dispose (c)

end

else

begin

c:=b;

while c^.nr<>i do

begin

d:=c;

c:=c^.adrurm

end;

d^.adrurm:=c^.adrurm;

dispose ( c)

end

end;
procedure adăugare;

begin

write(‘i=’); readln(i);

write(‘n=’); readln(n);

c:=b;

while c^.nr<>i do c:=c^.adrurm;

new (d );

d^.nr:=n;

d^.adrurm:=c^.adrurm;

c^.adrurm:=d

end;
begin

creare;

listare;

adăugare;

listare;

ştergere;

listare

end.
În continuare ne propunem să construim şi să tipărim o listă liniară simplu înlănţuită, utilizînd tehnici recursive.

Funcţia lista are sarcina de a construi lista liniară înlănţuită. La început se cere informaţia utilă. În situaţia în care aceasta este diferită de 0 (valoare care semnifică faptul că nu mai avem de adăugat nici un element), se rezervă un spaţiu pentru noua înregistrare, se completează informaţia utilă, iar cîmpul adrurm va lua valoarea funcţiei de tip lista care se autoapelează. În încheiere lista va lua valoarea c a cîmpului care reţine adresa noului element.

Este interesant să observăm că iniţial se creează lista simplu înlănţuită fără a completa cîmpul adresa, această completare urmînd să se facă la revenirea în procedură.

Să ne imaginăm că rulînd acest program dorim să creăm o listă cu două înregistrări care au informaţiile utile 1 şi 2.

Rularea decurge astfel:

Apelăm procedura;
Citim valoarea lui n şi anume 1;
Se alocă spaţiu pentru prima înregistrare;
Completăm informaţia utilă;
Pentru a completa adresa următoare înregistrării curente, se apelează din nou funcţia;
Citim valoarea lui n şi anume 2;
Alocăm spaţiu pentru a doua înregistrare;
Completăm informaţia utilă cu 2;
Se apelează din nou funcţia;
Se citeşte 0;
Funcţia ia valoarea nil;
Se revine din apel şi se continuă de acolo de unde am rămas;
Cîmpul de adresă al celei de a doua înregistrări va lua valoarea nil;
Funcţia capătă valoarea adresei înregistrării 2,
Se revine din apel;
Cîmpul de adresă al primei înregistrări ia valoarea celei de-a doua înregistrări;
Funcţia ia valoarea adresei primei înregistrări;
Se revine în programul principal.

Observăm că valoarea variabilei c a programului principal va fi după rulare adresa primei înregistrări.

Putem defini recursiv lista astfel:

O mulţime vidă de înregistrări este o listă;
Dacă la o listă se adaugă o înregistrare, se obţine o listă.

Recursiv putem tipări informaţia utilă din listă în două moduri:

În ordinea în care a fost creată;
În ordinea inversă celei în care a fost creată.

program llr;

type ref=^inr;

inr=record

nr:integer;

adrurm:ref

end;

var n:integer;

c:ref;
function lista:ref;

var c:ref;

begin

write(‘n=’); readln(n);

if n< >0

then

begin

new(c);

c^.nr:=n;

c^.adrurm:=lista;

lista:=c;

end

else lista:nil

end;
procedure tipard(c:ref);

begin

if c<>nil

then

begin

writeln(c^.nr);

tipard (c^.adrurm)

end

end;

procedure tipari(c:ref);

begin

if c<> nil then

begin

tipari (c^.adrurm);

writeln(c^.nr)

end

end;

begin

c:=lista;

tipard(c);

writeln(‘------------’);

tipari(c)

end.
Exemplul 1: La o casă de bilete s-a format un şir de aşteptare. Relaţiile dintre persoane se modifică permanent: persoanele nou-sosite se aşază în rînd; persoanele în criză de timp pleacă fără să-şi mai procure bilete; persoanele care au plecat pentru un timp îşi păstreză rîndul şi revin ş.a.m.d.

Să se creeze un algoritm care citeşte de la tastatură informaţia despre numele acestor persoane, apoi creează o listă în ordine lexicografică. Să se creeze subprograme care ar permite inserarea în listă a cîtorva persoane, ştergerea unor persoane din listă, afişarea listei pensionarilor. Să se păstreze lista într-un fişier text.

Rezolvare:

Vom rezolva mai întîi această problemă utilizînd structuri statice de date: articolul şi tabloul. Vom păstra lista de persoane într-un masiv unudimensional unde fiecare element al masivului este de tip record (numele persoanei, vîrsta, sexul). Lista va fi citită dintr-un fişier cu tip care a fost creat anterior cu ajutorul unui program Pascal foarte simplu.

Varianta 1.

Program ex1;

uses crt,Utimp;

type Oameni=record

name:string[20];

virsta:integer;

sex:char;

end;

vector=array[1..100] of oameni;

var list:oameni;

T1,T2,t:real;

n:integer;

z:vector;

c:char;

nume:string[20];

Procedure Formare_lista(m:integer);{Se citesc datele dintr-un fisier cu tip creat anterior}

var i:integer;

f:file of oameni;

begin

assign(f,'tip_fis');

reset(f);

for i:=1 to m do

read(f,z[i]);

close(f);

end;

Procedure Afisare_lista(q:vector;m:integer);{Afiseaza lista personelor}

var i:integer;

begin

for i:=1 to m do

writeln(q[i].name,' ',q[i].virsta,' ',q[i].sex);

end;

Procedure Pensionar(m:integer);{Creaza lista pensionarilor din rind}

var i:integer;

begin

for i:=1 to m do begin

if (z[i].virsta>60) and (z[i].sex='f') then

writeln(z[i].name,' ',z[i].virsta);

if (z[i].virsta>65) and (z[i].sex='m') then

writeln(z[i].name,' ',z[i].virsta);

end;

Procedure Ordonare_lista(m:integer;var w:vector); {Ordoneaza lista in ordine lexicografica dupa nume}

var i,j:integer;

k:oameni;

y:boolean;

begin

repeat

y:=false;

for i:= 1 to n-1 do

if w[i].name>w[i+1].name then begin

k:=w[i];

w[i]:=w[i+1];

w[i+1]:=k;

y:=true;

end;

until not y;

end;

Procedure Inserare_lista(m:integer);{Introduce o noua persoana in lista}

var i:integer;

k,t:oameni;

begin

write('Nume: ');readln(k.name);

write('Virsta: ');readln(k.virsta);

write('Sex: ');readln(k.sex);

for i:=1 to m do

if k.name

t:=z[i];

z[i]:=k;

k:=t;end;

z[m+1]:=k;

end;

Procedure Sterge_lista(var m:integer;num:string);{Sterge informatia despre o persoana din lista}

var i:integer;

begin

for i:=1 to m-1 do

if z[i].name=nume then z[i]:=z[i+1];

z[m].name:='';

z[m].virsta:=0;

z[m].sex:=' ';

m:=m-1;

end;

Procedure Fisier_lista(m:integer);{Creaza un fisier text in care se va pastra lista persoanelor}

var i:integer;

f:text;

begin

assign(f,'list_p.txt');

rewrite(f);

for i:=1 to m do

writeln(f,z[i].name,' ',z[i].virsta,' ',z[i].sex);

close(f);

end;
Begin

clrscr;

writeln('-------Formarea listei-----');

write('introdu numarul de persoane, n=');readln(n);

T1:=TimpulCurent;

Formare_lista(n);

writeln('------Lista initiala--------');

afisare_lista(z,n);

writeln('-------Lista pensionarilor-----');

pensionar(n);

writeln('-----Lista oronata----');

Ordonare_lista(n,z);

afisare_lista(z,n);T2:=TimpulCurent;t:=T2-T1;

repeat

write('Mai doriti sa introduce-ti o persoana in lista?:y/n');

readln(c);

T1:=TimpulCurent;

if c='y' then begin inserare_lista(n);n:=n+1;end;

T2:=TimpulCurent;t:=t+(T2-T1);

until c<>'y';

T1:=TimpulCurent;

afisare_lista(z,n);

T2:=TimpulCurent;t:=t+(T2-T1);

write('Introdu numele persoanei care trebuie eliminata din lista: ');

readln(nume);T1:=TimpulCurent;

sterge_lista(n,nume);

afisare_lista(z,n);

fisier_lista(n);

T2:=TimpulCurent;t:=t+(T2-T1);

writeln('Timpul de executie este: ',t:7:2,' secunde');

readkey;

End.

Pentru această problemă se va aloca static următorul volum de memorie:

list (o înregistrare): 20+2+1=23 octeţi

T1,T2: 2*6=12 octeţi

n:2 octeţi

z: 23*100=2300 octeţi

c: 1 octet

nume: 20 octeţi

În total: 23+12+2+2300+1+20=2358 octeţi

Acest număr de octeţi va fi alocat static indiferent de numărul de persoane din listă. La alocarea statică a memoriei se va ţine cont că volumul de memorie disponibil pentru alocare este nu mai mare de 64Ko.

În rezultatul rulării programului pentru n=50 se obţine:

Timpul de execuţie este: 7,03 secunde
În algoritmul propus în continuare se utilizează alocarea dinamică a memoriei. Am încercat să păstrez aceleaşi tipuri de date pentru a vedea mai clar diferenţa dintre aceşti doi algoritmi, pentru a estima cît mai corect timpul de execuţie al fiecăruia. Lista de persoane este implementată cu ajutorul unei liste simplu înlănţuite. Informaţia utilă a listei este de tip record (numele persoanei, vîrsta, sexul) şi este citită de la tastatură.

Varianta 2.

Program lista;

uses crt;

type ref=^persoana;

persoana=record

name:string[20];

virsta:byte;

sex:char;

urm:ref;

end;

var first:ref;

nume:string;

n:integer;

c:char;

Procedure Pensionar(primul:ref);

var temp:ref;

begin

temp:=primul;

while temp<>nil do begin

if (temp^.virsta>60) and (temp^.sex='f') then

writeln(temp^.name,' ',temp^.virsta);

if (temp^.virsta>65) and (temp^.sex='m') then

writeln(temp^.name,' ',temp^.virsta);

temp:=temp^.urm;

end;

Procedure Afisare_lista(primul:ref);

var temp:ref;

begin

temp:=primul;

while temp<> nil do begin

writeln(temp^.name,' ',temp^.virsta,' ',temp^.sex);

temp:=temp^.urm;

end;

Procedure Sterge_lista(primul:ref;nume:string);

var ind,temp:ref;

begin

ind:=primul;

if primul^.name=nume then begin

primul:=primul^.urm;

dispose(ind);

exit;

end;

while (ind^.urm^.name<>nume) and (ind^.urm<>nil) do ind:=ind^.urm;

if ind^.urm=nil then exit;

temp:=ind^.urm;

ind^.urm:=ind^.urm^.urm;

dispose(temp);

end;

Procedure Formare_lista(var primul:ref;m:integer);

var j:integer;

q,temp:ref;

begin

new(primul);

write('Numele pers 1: ');readln(primul^.name);

write('Virsta pers 1: ');readln(primul^.virsta);

write('Sexul pers 1: ');readln(primul^.sex);

primul^.urm:=nil;

for j:=2 to m do begin

new(q);

write('Numele pers ',j,': ');readln(q^.name);

write('Virsta pers ',j,': ');readln(q^.virsta);

write('Sexul pers ',j,': ');readln(q^.sex);

q^.name[1]:=upcase(q^.name[1]);

if q^.name<=primul^.name then begin

q^.urm:=primul;

primul:=q;

end

else begin

temp:=primul;

while (temp^.urm<>nil) and (q^.name>temp^.urm^.name) do

temp:=temp^.urm;

q^.urm:=temp^.urm;

temp^.urm:=q;

end;

Procedure Inserare_lista(var primul:ref);

var q,temp:ref;

begin

new(q);

write('Numele pers: ');readln(q^.name);

write('Virsta pers: ');readln(q^.virsta);

write('Sexul pers: ');readln(q^.sex);

q^.name[1]:=upcase(q^.name[1]);

if q^.name<=primul^.name then begin

q^.urm:=primul;

primul:=q;

end

else begin

temp:=primul;

while (temp^.urm<>nil) and (q^.name>temp^.urm^.name) do

temp:=temp^.urm;

q^.urm:=temp^.urm;

temp^.urm:=q;

end;

Procedure Fisier_lista(primul:ref);

var ind:ref;

f:text;

begin

assign(f,'lista_p.txt');

rewrite(f);

ind:=primul;

while ind<>nil do begin

writeln(f,ind^.name,' ',ind^.virsta,' ',ind^.sex);

ind:=ind^.urm;

end;

close(f);

end;
Begin

clrscr;

writeln('-------Formarea listei-----');

write('introdu numarul de persoane, n=');readln(n);

Formare_lista(first,n);

writeln('------Lista initiala--------');

afisare_lista(first);

writeln('-------Lista pensionarilor-----');

pensionar(first);

repeat

write('Mai doriti sa introduce-ti o persoana in lista?:y/n');

readln(c);if c='y' then inserare_lista(first);

until c<>'y';

afisare_lista(first);

write('Introdu numele persoanei care trebuie eliminata din lista: ');

readln(nume);

sterge_lista(first,nume);

afisare_lista(first);

fisier_lista(first);

readkey;

End.
-------Formarea listei-----

introdu numarul de persoane, n=2

Numele pers 1: Mihai

Virsta pers 1: 12

Sexul pers 1: m

Numele pers 2: Corina

Virsta pers 2: 69

Sexul pers 2: f

------Lista initiala--------

Corina 69 f

Mihai 12 m

-------Lista pensionarilor-----

Corina 69

Mai doriti sa introduce-ti o persoana in lista?:y/ny

Numele pers: alina

Virsta pers: 56

Sexul pers: f

Mai doriti sa introduce-ti o persoana in lista?:y/nn

Alina 56 f

Corina 69 f

Mihai 12 m

Introdu numele persoanei care trebuie eliminata din lista: Corina

Alina 56 f

Mihai 12 f

Citirea datelor de la tastatură este un lucru destul de anevoios, care admite o sumedenie de erori, din care cauză suntem nevoiţi s-o luăm de la început. Mai mult ca atît, testarea programului cere de fiecare dată introducerea de date care ne ia mult timp. Deci, la fel ca şi pentru algoritmul din varianta 1, lista poate citită dintr-un fişier cu tip creat anterior.

Varianta 3.

Program ex1;

uses crt,Utimp;

type ref=^persoana;

persoana=record

name:string[20];

virsta:byte;

sex:char;

urm:ref;

end;
Oameni=record

name:string[20];

virsta:integer;

sex:char;

end;

var list:oameni;

nume:string[20];

i,j:byte;

q:file of oameni;

var first:ref;

n:integer;

c:char;

T1,T2,t:real;

Procedure Pensionar(primul:ref);

var temp:ref;

begin

temp:=primul;

while temp<>nil do begin

if (temp^.virsta>60) and (temp^.sex='f') then

writeln(temp^.name,' ',temp^.virsta);

if (temp^.virsta>65) and (temp^.sex='m') then

writeln(temp^.name,' ',temp^.virsta);

temp:=temp^.urm;

end;

Procedure Afisare_lista(primul:ref);

var temp:ref;

begin

temp:=primul;

while temp<> nil do begin

writeln(temp^.name,' ',temp^.virsta,' ',temp^.sex);

temp:=temp^.urm;

end;

Procedure Sterge_lista(primul:ref;nume:string);

var ind,temp:ref;

begin

ind:=primul;

if primul^.name=nume then begin

primul:=primul^.urm;

dispose(ind);

exit;

end;

while (ind^.urm^.name<>nume) and (ind^.urm<>nil) do ind:=ind^.urm;

if ind^.urm=nil then exit;

temp:=ind^.urm;

ind^.urm:=ind^.urm^.urm;

dispose(temp);

end;

Procedure Formare_lista(var primul:ref;m:integer);

var j:integer;

q,temp:ref;

f:file of oameni;

z:oameni;

begin

new(primul);

assign(f,'tip_fis');

reset(f);

read(f,z);writeln(z.name,z.virsta,z.sex);

primul^.name:=z.name;

primul^.virsta:=z.virsta;

primul^.sex:=z.sex;

primul^.urm:=nil;

for j:=2 to m do begin

new(q);

read(f,z);

q^.name:=z.name;

q^.virsta:=z.virsta;

q^.sex:=z.sex;

q^.name[1]:=upcase(q^.name[1]);

if q^.name<=primul^.name then begin

q^.urm:=primul;

primul:=q;

end

else begin

temp:=primul;

while (temp^.urm<>nil) and (q^.name>temp^.urm^.name) do

temp:=temp^.urm;

q^.urm:=temp^.urm;

temp^.urm:=q;

end;

close(f);

end;

Procedure Inserare_lista(var primul:ref);

var q,temp:ref;

begin

new(q);

write('Numele pers: ');readln(q^.name);

write('Virsta pers: ');readln(q^.virsta);

write('Sexul pers: ');readln(q^.sex);

q^.name[1]:=upcase(q^.name[1]);

if q^.name<=primul^.name then begin

q^.urm:=primul;

primul:=q;

end

else begin

temp:=primul;

while (temp^.urm<>nil) and (q^.name>temp^.urm^.name) do

temp:=temp^.urm;

q^.urm:=temp^.urm;

temp^.urm:=q;

end;

Procedure Fisier_lista(primul:ref);

var ind:ref;

f:text;

begin

assign(f,'lista_p.txt');

rewrite(f);

ind:=primul;

while ind<>nil do begin

writeln(f,ind^.name,' ',ind^.virsta,' ',ind^.sex);

ind:=ind^.urm;

end;

close(f);

end;
Begin

clrscr;

writeln('-------Formarea listei-----');

write('introdu numarul de persoane, n=');readln(n);

T1:=TimpulCurent;

Formare_lista(first,n);

writeln('------Lista initiala--------');

afisare_lista(first);

writeln('-------Lista pensionarilor-----');

pensionar(first);

T2:=TimpulCurent;

t:=T2-T1;

repeat

write('Mai doriti sa introduce-ti o persoana in lista?:y/n');

readln(c);

T1:=TimpulCurent;

if c='y' then inserare_lista(first);

T2:=TimpulCurent;t:=t+(T2-T1);

until c<>'y';

T1:=TimpulCurent;

afisare_lista(first);

T2:=TimpulCurent;t:=t+(T2-T1);

write('Introdu numele persoanei care trebuie eliminata din lista: ');

readln(nume);T1:=TimpulCurent;

sterge_lista(first,nume);

afisare_lista(first);

fisier_lista(first);

T2:=TimpulCurent;t:=t+(T2-T1);

writeln('Timpul de executie este: ',t:7:2,' secunde');

readkey;

End.
Pentru problema dată se alocă dinamic următorul volum de memorie:

list (o înregistrare): 20+2+1=23 octeţi

T1,T2,t: 3*6=18 octeţi

i, j,n:2*3=6 octeţi

c: 1 octet

nume: 20 octeţi

În total: 23+18+6+1+20=68 octeţi

Volumul de memorie necesar pentru memorarea componentelor listei este egal cu: 23*n_p octeţi, unde n_p este numărul de înregistrări din listă.

În rezultatul rulării programului pentru n=50 se obţine:

Timpul de execuţie este: 4,94 secunde
După cum vedem, la alocarea dinamică a memoriei volumul necesar de memorie se reduce considerabil. Un dezavantaj ar fi, că textul programelor este destul de mare. Analizînd şi timpul de execuţie, observăm că şi aici vom da preferinţă algoritmului unde s-a folosit alocarea dinamică a memoriei. În cazul dat avem că, pentru algoritmul din varianta 1 timpul de execuţie este de ≈1,5 ori mai mare decît timpul de execuţie necesar pentru algoritmul din varianta 3, pentru n=50. Evident, că cu cît este mai mare n cu atît diferenţa dintre timpul de execuţie, necesar algoritmilor, va fi mai mare.

Un lucru ce trebuie menţionat este şi acela că, în mediul de programare Turbo Pascal pentru alocarea dinamică a memoriei sunt rezevaţi 256Ko, adică de 4 ori mai mult decît în cazul static (64Ko). Dimensiunile Heap-ului pot fi modificate cu ajutorul direvtivelor de compilare sau a comenzilor mediului de programare.

Exemplul 2: Sortare topologică. Presupunem că dorim sortarea numerelor. 1,2,.....,n, numere care se găsesc într-o ordine oarecare, alta decît cea naturală. Pentru a afla relaţia în care se găsesc numerele, introducem un număr finit de perechi (i,j). O astfel de pereche ne spune că, în relaţia de ordine considerată, i se află înaintea lui j.

De exemplu, pentru n=3 citim perechile (3,1) şi (3,2). Numărul 3 se află înaintea lui 1 şi 3 se află înaintea lui 2. Apar două soluţii posibile: 3,1,2 şi 3,2,1, întrucît nu avem nici o informaţie asupra relaţiilor dintre 1şi 2. Tragem de aici concluzia că o astfel de problemă poate avea mai multe soluţii.

De exemplu, pentru n=3 citim perechile(1,2), (2,3), (3,1). În acest caz nu avem soluţie. Din primele două relaţii rezultă că ordinea ar fi 1,2,3 iar a 3-a contrazice această ordine.

Din cele expuse mai sus, problema poate avea sau nu soluţie, iar dacă are poate fi sau nu unică.

Algoritmul prezentat în continuare furnizează o singură soluţie atunci cînd problema admite soluţii. În caz contrar specifică faptul că problema nu admite soluţie.

Vom exemplifica funcţionarea algoritmului pe exemplu următor: n=4 şi se citesc perechile (3,4), (4,2), (1,2), (3,1).

Pentru fiecare număr între 1 şi n trebuie să avem următoarele informaţii:

Numărul predecesorilor săi;
Succesorii săi;

Pentru aceasta folosim doi vectori:

contor, vector care reţine numărul predecesorilor fiecărui k, cu k Є {1..n}.
a, care reţine adresele de început ale listelor de succesori ai fiecărui element.

Pentru fiecare element există o listă simplu înlănţuită a succesorulor săi. Fiecare înregistrare din aceste liste conţine două elemente:

succesorul;
adresa următorului element din listă.

Iniţial, în dreptul fiecărui element în vectorul „contor” se trece 0, iar în vectorul „a” se trece nil.

Citirea unei perechi (i,j) înseamnă efectuarea următoarelor operaţii:

mărirea cu 1 a cîmpului contor(j) (j are un predecesor, şi anume pe i);
adăugarea lui j la lista succesorului lui i.

Pentru exemplu nostru, lucrurile decurg astfel:

Contor	0	0	0	0
A	nil	nil	nil	Nil

0	0	0	0	am citi (3,4)
nil	nil	nil	Nil	al3 – adresa listei 3
		4

0	1	0	1	am citi (4,2)
nil	nil	al3	al4
		4	2

1	1	0	1	am citi (4,1)
nil	nil	al3	al4
		4	2
			1

1	2	0	1	am citi (1,2)
al1	nil	al3	al4
2		4	2
			1

2	2	0	1	am citi (3,1)
all	nil	al3	al4
2		4	2
		1	1

În continuare se procedează astfel:

toate elementele care au 0 în cîmpul contor se reţin într-un vector c;
pentru fiecare element al vectorului c se procedează astfel:
se tipăreşte;
se marchează cu -1 cîmpul său de contor;
pentru toţi succesorii săi (aflaţi în lista succesorilor) se scade cu 1 din cîmpul contor (este normal, întrucît aceştia au un predecesor mai puţin).
Se reia algoritmul dacă nu este îndeplinită una din condiţiile următoare:
- Au fost tipărite toate elementele, caz în care algoritmul se încheie cu succes;
- Nu avem nici un element cu 0 în cîmpul contor, caz în care relaţiile au fost incoerente.

1	2	-1	1	tipăresc 3, scad 1 din predecesorii lui 4 şi 1, cu -1 contorul lui 3;
all	nil	Al3	al4
2		4	2
		1	1

0	1	-1	-1	tipăresc 4, scad 1 din predecesorii lui 2 şi 1, cu -1 contorul lui 4;
all	nil	Al3	al4
2		4	2
		1	1

-1	0	0	1	tipăresc 1, scad 1 din predecesorii lui 2, cu -1 contorul lui 1;
All	nil	Al3	al4
2		4	2
		1	1

Observaţie: Algoritmul are mai multe aplicaţii, ca de exemplu:

Ordonarea unor activităţi, atunci cînd ele sunt condiţionate una de alta;
Ordonarea unor termeni care se cer explicaţi pentru a-i putea explica prin alţii deja prezentaţi.

Program stopo;

Uses crt;

type ref=^inr;

inr=record

succ:integer;

urm:ref

end;

vector=array [1..100] of integer;

vectad=array [1..100]of ref;

var n,m,i,j,k:integer;

contor,c:vector;

a:vectad;

gasit:boolean;

Procedure adaug (i,j:integer);

var c,d:ref;

begin

contor [j]:=contor [j]+1;

c:=a[i];

new (d);

d^.urm:=nil;

d^.succ:=j;

if c=nil

then a[i]:=d

else

begin

while c^.urm<>nil do c:=c^.urm;

c^.urm:=d

end

end;

Procedure actual (i:integer);

var c:ref;

begin

c:=a[i];

while c <>nil do

begin

contor [c^.succ]:=contor[c^.succ]-1;

c:=c^.urm

end

end;

Begin

Clrscr;

write (’n=’); readln(n);

for i:=1 to n do

begin

contor [i]:=0;

a[i]:=nil

end;

while i<>0 do

begin

write (’Tastati i,j=’);

readln (i,j);

if i< >0 then adaug (i,j)

end;

m:=n;

repeat

k:=1;

gasit:false;

for i:=1 to n do if contor [i]=0

then

begin

gasit:=true;

m:=m-1;

c[k]:=i;

k:=k+1;

contor [i]:=-1

end;

for i:=1 to k-1 do

begin

actual(c[i]);

write(c[i]);

end;

until (not gasit) or (m=0);

writelnş

if m=0

then writeln (’totul e ok’)

else writeln (’relatii contradictorii’)

readkez;

end.

n=4

Tastati i,j=3 4

Tastati i,j=4 2

Tastati i,j=1 2

Tastati i,j=3 1

Tastati i,j=0 0

3 1 4 2

totul e ok

n=4

Tastati i,j=1 2

Tastati i,j=2 3

Tastati i,j=3 1

Tastati i,j=4 2

Tastati i,j=0 0

relatii contradictorii

§2. Lista liniară dublu înlănţuită

O listă dublu înlănţuită este o structură de date de forma:

nil

in₁

dr₂

adr₁

in₂

dr₃

adr_n-1

in_n

nil

adr₁

adr₂

dr_n

Operaţiile pe care le putem face cu o listă dublu înlănţuită sunt următoarele:

Creare;
Adăugare la dreapta;
Adăugare la stînga;
Adăugare în interiorul listei;
Ştergere din interiorul listei;
Ştergere la sînga listei;
Ştergere la dreapta listei;
Listare de la sînga la dreapta;
Listare de la dreapta la sînga;

Creare

O listă dublu înlănţuită se creează cu o singură înregistrare. Pentru a ajunge la numărul de înregistrări dorit, utilizăm proceduri de adăugare la stînga sau la dreapta. În programul de faţă acest lucru este realizat de procedura creare. Această procedură realizează operaţiile următoare:

Citirea informaţiei utile;
Alocarea de spaţiu pentru înregistrare;
Completarea înregistrării cu informaţia utilă;
Completarea adreselor de legătură la stînga şi la dreapta cu nil;
Variabilele tip referinţă b şi s vor căpăta valoarea adresei acestei prime înregistrări (b semnfică adresa înregistrării cea de mai din stînga, s adresa ultimei înregistrări din dreapta).

2) Adăugarea la dreapta

Această operaţie este realizată de procedura addr. Pentru adăugarea unei înregistrări se realizează următoarele operaţii:

Citirea informaţiei utile;
Alocarea spaţiului pentru înregistrare;
Completarea adresei la dreapta cu nil;
Completarea adresei din stînga cu adresa celei mai din dreapta înregistrări (reţinute în variabila s);
Modificarea cîmpului de adresă la dreapta a înregistrării din s cu adresa noii înregistrări;
s va lua valoarea noi înregistrări, deoarece aceasta va fi cea mai din dreapta.

Adăugare în interiorul listei

Această operaţie este realizată de procedura includ, care realizează următoarele operaţii:

Parcurge lista de la stînga la dreapta căutînd înregistarea cu informaţia utilă m, în dreapta căreia urmează să introducem noua înregisrare;
Citeşte informaţia utilă;
Alocă spaţiu pentru noua înregistrare;
Completează informaţia utilă;
Adresa stîngă a noii înregistrări ia valoarea adresei înregistrării de informaţie utilă m;
Adresa stîngă a înregistrării care urma la acest moment înregistrării cu informaţia utilă m capătă valoarea adresei noii înregistrări;
Adresa dreaptă a noii înregistrări ia valoarea adresei dreapta a înregistrării de informaţia utilă m;
Adresa dreaptă a înregistrării cu informaţia utilă m ia valoarea noii înregistrări;

Ştergere din interiorul listei

Această operaţie este realizată de procedura sterg. Operaţiile efectuate de această procedură următoarele:

Se parcurge lista de la stînga la dreapta pentru a ne poziţiona pe înregistrarea care urmează a fi ştearsă;
Cîmpul de adresă dreapta al înregistrării care o precede pe această şi va lua valoarea cîmpului de adresă dreapta al înregistrării care va fi ştearsă;
Cîmpul de adresă stînga al înregistrării care urmează înregistrării care va fi ştearsă va lua valoarea cîmpului de adresă stînga al înregistrării pe care o ştergem;
Se eliberează spaţiul de memorie rezervat înregistrării care se şterge.

5) Listare de la sînga la dreapta

Această operaţie este realizată de procedura listare, procedură care realizează următoarele operaţii:

Porneşte din stînga listei;
Atît timp cît nu s-a ajuns la capătul din dreapta al listei, se tipăreşte informaţia utilă şi se trece la înregistrarea următoare.

Program ldi;

uses crt;

type ref=^inr;

inr=record

as:ref;

nr:integer;

ad:ref

end;

var b,s,c:ref;

n,m,i:integer;

Procedure creare (var b,s:ref);

begin

write('n='); readln(n);

new(b); b^.nr:=n;

b^.as:=nil; b^.ad:=nil;

s:=b

end;

Procedure addr(var s:ref);

var d:ref;

begin

write('n='); readln(n);

new(d); d^.nr:=n;

d^.as:=s; d^.ad:=nil;

s^.ad:=d; s:=d

end;

Procedure listare(b:ref);

var d:ref;

begin

d:=b;

while d<>nil do

begin

writeln(d^.nr);

d:=d^.ad

end

end;

Procedure includ(m:integer;b:ref);

var d,e:ref;

begin

d:=b;

while d^.nr<>m do d:=d^.ad;

write('n=');readln(n);

new(e);

e^.nr:=n;

e^.as:=d;

d^.ad^.as:=e;

e^.ad:=d^.ad;

d^.ad:=e;

end;

Procedure sterg (m:integer; b:ref);

var d:ref;

begin

d:=b;

while d^.nr<>m do d:=d^.ad;

d^.as^.ad:=d^.ad;

d^.ad^.as:=d^.as;

dispose (d)

end;

Begin

clrscr;

writeln('Creare lista cu o singura inregistrare');

creare(b,s);

write('Cite inregistrari se adauga?');

readln(m);

for i:=1 to m do addr(s);

writeln('Acum listez de la stinga la dreapta');

listare(b);

writeln('Includem la dreapta o inregistrare');

write('Dupa care inregistrare se face includerea?');

readln(m);

includ(m,b);

writeln('Acum listez de la stinga la dreapta');

listare(b);

writeln('Acum stergem o inregistrare din interior');

write('Ce inregistrare stergem?');

readln(m);

sterg(m,b);

writeln('Acum listez de la stinga la dreapta');

listare(b);

readkey;

end.
Creare lista cu o singura inregistrare

n=2

Cite inregistrari se adauga?3

n=5

n=6

n=9

Acum listez de la stinga la dreapta

5

6

Includem la dreapta o inregistrare

Dupa care inregistrare se face includerea?6

n=12

Acum listez de la stinga la dreapta

Acum stergem o inregistrare din interior

Ce inregistrare stergem?5

Acum listez de la stinga la dreapta

9
Exemplul 1: Să se caluleze suma a două numere lungi. (:255 cifre).

Rezolvare:

Utilizarea tipului de date array rezolvă doar parţial problema programării numerelor mari, şi anume, se măreşte doar lungimea numărului. Neajunsul major este - volumul excesiv de memorie utilizat în acest caz. Deoarece la declararea statică a unui tip de date array în memorie se rezervează spaţiul declarat în

Type vector=Array[1..m] of byte; (m declarat în secţiunea const), adică m octeţi indifferent de faptul dacă vor fi luaţi în calcule toţi.

Alocarea dinamică a memoriei înlătură acest neajuns, deoarece la declararea variabilelor dinamice ale pot fi create şi nimicite la necesitatea programatorului.

Programul propus permite de a aduna numere de lungime nu mai mare de 21000 cifre şi permite utilizarea memoriei cît mai econom.

{Calcularea sumei a doua numere de aceeasi lungime}

Program suma1;

uses crt;

type ref=^numar;

numar=record

nr:integer;

anti,next:ref;

end;

var prim1,ultim1,prim2,ultim2,curent1,curent2,flag,s,sp,su:ref;

n,minte,i:integer;

Procedure Creare(var b,p:ref);

var j:integer;

temp:ref;

begin

new(p);b:=p;

write('Introdu primul: ');

readln(p^.nr);

p^.anti:=nil;

p^.next:=nil;

for j:=2 to n do begin

new(temp);

{ write('Introdu componenta ',j,' : ');}

readln(temp^.nr);

p^.next:=temp;

temp^.next:=nil;

temp^.anti:=p;

p:=temp;

end;

Procedure Afisare_inainte(var p:ref);

var curent:ref;

begin

curent:=p;

while curent<>nil do begin

write(curent^.nr);

curent:=curent^.next;

end;

writeln;

end;

Procedure Afisare_inapoi(var p:ref);

var curent:ref;

begin

curent:=p;

while curent<>nil do begin

write(curent^.nr);

curent:=curent^.anti;

end;

writeln;

end;

Begin

clrscr;

write('Introdu n=');

readln(n);

writeln('Introdu primul numar:');

Creare(prim1,ultim1);

writeln('Introdu numarul al doilea:');

Creare(prim2,ultim2);

writeln('--------------------');

Afisare_inainte(prim1);

Afisare_inainte(prim2);

{Crearea sumei}

new(s);sp:=s;

curent1:=ultim1;

curent2:=ultim2;

minte:=0;

s^.nr:=(curent1^.nr+curent2^.nr+minte) mod 10;

minte:= (curent1^.nr+curent2^.nr+minte) div 10;

s^.anti:=nil;

s^.next:=nil;

for i:=2 to n do begin

new(flag);curent1:=curent1^.anti;curent2:=curent2^.anti;

flag^.nr:=(curent1^.nr+curent2^.nr+minte) mod 10;

minte:= (curent1^.nr+curent2^.nr+minte) div 10;;

s^.next:=flag;

flag^.next:=nil;

flag^.anti:=s;

s:=flag;

end;

if minte <>0 then begin new(flag);flag^.nr:=minte;

s^.next:=flag;

flag^.next:=nil;

flag^.anti:=s;

s:=flag end;

su:=s;

{Afisarae sumei}

Afisare_inapoi(su);

readkey;

End.

{Calcularea sumei a doua numere de lungimi diferite}

Program suma2;

uses crt;

type ref=^numar;

numar=record

nr:integer;

anti,next:ref;

end;

var prim1,ultim1,prim2,ultim2,curent1,curent2,flag,s,sp,su:ref;

n,m,dd,minte,i:integer;
Procedure Creare(z:integer;var b,p:ref);

var j:integer;

temp:ref;

begin

new(p);b:=p;

write('Introdu primul: ');

readln(p^.nr);

p^.anti:=nil;

p^.next:=nil;

for j:=2 to z do begin

new(temp);

{ write('Introdu componenta ',j,' : ');}

readln(temp^.nr);

p^.next:=temp;

temp^.next:=nil;

temp^.anti:=p;

p:=temp;

end;

Procedure Afisare_inainte(var p:ref);

var curent:ref;

begin

curent:=p;

while curent<>nil do begin

write(curent^.nr);

curent:=curent^.next;

end;

writeln;

end;

Procedure Afisare_inapoi(var p:ref);

var curent:ref;

begin

curent:=p;

while curent<>nil do begin

write(curent^.nr);

curent:=curent^.anti;

end;

writeln;

end;

Begin

clrscr;

write('Introdu n=');

readln(n);

write('Introdu m=');

readln(m);

if n>=m then dd:=m else dd:=n;

writeln('Introdu primul numar:');

Creare(n,prim1,ultim1);

writeln('Introdu numarul al doilea:');

Creare(m,prim2,ultim2);

writeln('--------------------');

Afisare_inainte(prim1);

Afisare_inainte(prim2);

{Crearea sumei}

new(s);sp:=s;

curent1:=ultim1;

curent2:=ultim2;

minte:=0;

s^.nr:=(curent1^.nr+curent2^.nr+minte) mod 10;

minte:= (curent1^.nr+curent2^.nr+minte) div 10;

s^.anti:=nil;

s^.next:=nil;

for i:=2 to dd do begin

new(flag);curent1:=curent1^.anti;curent2:=curent2^.anti;

flag^.nr:=(curent1^.nr+curent2^.nr+minte) mod 10;

minte:= (curent1^.nr+curent2^.nr+minte) div 10;;

s^.next:=flag;

flag^.next:=nil;

flag^.anti:=s;

s:=flag;

end;

if n>m then for i:=dd+1 to n do begin

new(flag);curent1:=curent1^.anti;

flag^.nr:=(curent1^.nr+minte) mod 10;

minte:= (curent1^.nr+minte) div 10;;

s^.next:=flag;

flag^.next:=nil;

flag^.anti:=s;

s:=flag;

end;

if m>n then for i:=dd+1 to m do begin

new(flag);curent2:=curent2^.anti;

flag^.nr:=(curent2^.nr+minte) mod 10;

minte:= (curent2^.nr+minte) div 10;;

s^.next:=flag;

flag^.next:=nil;

flag^.anti:=s;

s:=flag;

end;

if minte<>0 then begin new(flag);flag^.nr:=minte;

s^.next:=flag;

flag^.next:=nil;

flag^.anti:=s;

s:=flag end;

su:=s;

{Afisarae sumei}

Afisare_inapoi(su);

readkey;

End.

§3. Lista circulară

Se consideră o listă simplu înlănţuită. Dacă, la ultima înregistrare, adresa următoare va fi adresa primei înregistrării, am definit o listă circulară simplu înlănţuită. Pentru lista dublu înlănţuită, dacă la prima înregisrare adresa precedentă va fi adresa ultimei înregistrări iar la ultima înregistrare, adresa următoare va fi adresa primei înregistrării, atunci am definit o listă circulară dublu înlănţuită.

Exemplul 1: Numărătoarea. Se dau numerele naturale m şi n, unde m>1. Considerăm m copii care au format un cerc şi unul dintre ei numără într-o direcţie pînă la al m-lea copil care iese din cerc. Numărătoarea continuă cu următorul jucător. Ultimul copil rămas în cerc mijeşte. Citind de la tastatură numele copiilor şi numărînd de la ultimul copil spre primul, să se determine:

ordinea de ieşire din cerc;
cine va miji.

Rezolvare:

Problema se va rezolva utilizînd o listă circulară simplu înlănţuită. Elementele acestei liste vor fi numele copiilor care se joacă.

Programul Pascal este:

program numaratoarea;

uses crt;

type legatura=^Persoana;

persoana=record

name:string[20];

next:legatura

end;

var Primul,p,ult,temp:legatura;

nume:string[20];

i,n,m:integer;

c:char;

BEGIN

clrscr;

write('Introdu numarul de copii: ');

readln(n);

write('Introdu numarul m=');

readln(m);

write('Scrie numele primului copil: ');

new(primul);

readln(primul^.name);

ult:=primul;

for i:=2 to n do begin

new(p);

write('Introdu numele copililui ',i,' :');

readln(p^.name);

p^.next:=primul;

primul:=p;

end;

ult^.next:=primul;

writeln('-----Afisarea listei-----');

p:=primul;

repeat

writeln(p^.name);

p:=p^.next;

until p=primul;

writeln('------------------');

i:=2;{i este numarul de ordine al urmatorului}

p:=primul;

repeat

if i mod m=0 then begin

temp:=p^.next;

p^.next:=p^.next^.next;

writeln(temp^.name,' - afara');

dispose(temp);

end else p:=p^.next;

i:=i+1;

until p^.next=p;

writeln('==========================');

writeln('Mijeste ',p^.name);

readkey;

END.

Introdu numarul de copii: 6

Introdu numarul m=2

Scrie numele primului copil: Ana

Introdu numele copililui 2 :Alina

Introdu numele copililui 3 :Marina

Introdu numele copililui 4 :Valentin

Introdu numele copililui 5 :Stefan

Introdu numele copililui 6 :Corina

-----Afisarea listei-----

Corina

Stefan

Valentin

Marina

Alina

Ana

------------------

Stefan - afara

Marina - afara

Ana - afara

Valentin - afara

Corina - afara

==========================

Mijeste Alina

Yüklə 0,55 Mb.

Dostları ilə paylaş:

1 2 3 4