Structuri de date si algoritmi

[AxeL]

Laborator 1

Structuri de date si algoritmi

Recapitularea unor notiuni ale limbajujului C:
Pointeri si Structuri

Informatii introductive

La laboratorul de "Programarea Calculatoarelor" veti lucra cu
compilatorul Borland C++. Programele vor fi scrise in C, dar vom folosi
citeva facilitati specifice limbajului C++ care vor fi
expuse in continuare. Fisierele sursa vor avea extensia .CPP (de
exemplu STUDENT.CPP).

Iata deja o prima simplificare: doua semne // arata inceputul unui
comentariu. Acest tip de comentariu incepe cu // si se termina la
sfirsitul liniei.

Expresii si valori stinga

In C ne putem referi la un obiect folosind o expresie "valoare-stinga".
O expresie "valoare-stinga" este o expresie care poate sa apara in
STINGA unei atribuiri. De exemplu numele unei variabile
este o expresie valoare-stinga in timp ce rezultatul unei operatii
aritmetice nu este valoare-stinga.

int i;
int v[10];

Valori stinga: i, v[i], v[i+1];
Nu sint valori stinga: i+1, 2*v[i]

In C prin combinarea numelor de variabile cu anumiti operatori se obtin
valori-stinga:

Operatorul *
Se aplica numai pointerilor, rezultatul fiind o valoare-stinga care se
refera la obiectul a carei adresa este continuta de catre pointer:

int* p; // valori stinga:
p = &i; // p nume_variabila
*p=5; // *p * pointer

Observati ca expresia *p (rezulatata din combinatia numelui lui p cu
operatorul *) apare in stinga atribuirii.

Operatorul []
Se aplica numelor de tablouri si pointerilor, rezultatul fiind o
valoare-stinga care se refera la obiectul al n-lea din tablou:

int tab[10];
int* p = &tab[0]; // valori stinga:
tab[2] = 3; // nume_tablou [ index ]
p[2] = 4; // pointer [ index ]

Mai sus, pointerul p este initializat cu adresa primului element din
vectorul tab. Expresia p[2] va referi al doilea element din vectorul a
carui adresa este memorata in pointerul p, deci tab[2].

Operatorii . si ->
Apar in legatura cu structurile si vor fi tratati putin mai tirziu.

Structuri

1. Definire
O structura este un tip de date nou. Atunci cind definim o structura,
trebuie sa specificam numele structurii si cimpurile ei:

struct student {
char* nume;
int nota;
};

Am introdus tipul "struct student". Pentru a evita repetarea lui
"struct" putem sa introducem un pseudonim pentru tipul "struct student"
si anume "Student" astfel:

typedef struct student Student;

Cele doua declaratii de mai sus pot fi comprimate in una singura:

typedef struct {
char* nume;
int nota;
} Student ;

In C++, tipul definit de declaratia:

struct Student {
char* nume;
int nota;
};

poate fi denumit "struct Student" sau, doar simplu, "Student". In
continuare ne vom folosi de aceasta facilitate care mareste
lizibilitatea programelor. Repetam: programele vor avea extensia
.CPP .

2. Obiecte de tip structura
Am definit structura Student avind CIMPURILE "nume" (adresa unui sir de
caractere) si "nota" de tip int.

Odata definit tipul, acesta poate fi folosit pentru a declara
variabile:

Student s1, s2; // s1 si s2 sint doua variabile de tip Student
Student grupa[5]; // un tablou de variable Student
Student* ps; // o variabila pointer la Student
Student* idx[5]; // o variabila tablou de pointeri la Student

3. Operatorii . si ->
Folosirea cimpurilor unei structuri se face NUMAI CU REFERIRE LA UN
OBIECT de tipul respectiv. Obiectul este referit printr-o valoare
stinga care semnifica obiectul structura sau adresa obiectului
structura.

Operatorul . cere in stinga sa o valoare stinga de tip structura iar in
dreapta, numele cimpului selectat, rezultatul fiind o valoare-stinga
care se refera la cimpul selectat. De exemplu, din
declaratiile de mai sus, cimpurile variabilei grupa[3] vor fi denumite:
grupa[3].nume si grupa[3].nota
Operatorul -> cere in stinga sa o expresie de tip "pointer la
structura" iar in dreapta numele cimpului selectat, rezultatul fiind o
valoare-stinga care se refera la cimpul selectat:

Exercitii
Avand urmatoarele declaratii:

int i, *pi;
Student s;
Student* ps;
Student ts[5];
Student* tps[5];

numiti tipurile urmatoarelor expresii. Decideti daca sint valori stinga
sau nu:

i+2, pi, i, p+3;
ts[2], ts, ps, ps[2];
ps->nume, *pi, *(pi+2), *pi+2;
(ps+3)->nume, ps->nume[2], tps, tps[2];
tps[2]->nume, tps[2]->nume[2];

Pointeri

1. Definire
Pentru un tip de date T o variabila "pointer la T" se defineste astfel:

T* ptrT; // ptrT este un pointer la T

O variabila pointer la T poate retine adresa unui obiect de tip T.

Exemple:

int* pi; // pi este un pointer la int
char* tab; // tab este un pointer la char
Nod *nou, *cap; // nou si cap sint pointeri la tipul Nod

2. Initializare
Prima operatie care se face cu un pointer este initializarea. Un
"pointer la T" poate fi initializat cu:

a) adresa unui T (care exista)

pi = &i;

b) valoarea 0 (sau NULL) care semnifica adresa invalida

cap = 0;

c) valoarea altui "pointer la T". De exemplu: daca p si q sint de tip
T* si p contine adresa unei variabile de tip T (a fost initializat in
prealabil), atribuirea q = p va face ca ambii pointeri sa indice
aceeasi variabila.

d) adresa unui spatiu de memorie alocat in zona de alocare dinamica.
Spatiul alocat poate sa contina un singur obiect de tip T, acesta se
exprima:

in C: p = (T*) malloc( sizeof(T) );
in C++: p = new T;
sau poate sa contina mai multe (n) obiecte de tip T:

in C: p = (T*) malloc( n*sizeof(T) );
in C++: p = new T[n];

Exprimarile din C++ sint in mod evident mult mai simple, si le vom
folosi pe acestea in continuare.

Iata un exemplu:

typedef Student* PStudent;
PStudent* ptps; // pointer la tablou de pointeri la studenti
ptps = new PStudent[nr];

3. Dereferentierea
Este operatia prin care avind un "pointer la T" (care contine adresa
unui T) obtinem o valoare stinga care se refera la obiectul pointat
(vezi operatorul *).

Pentru a obtine obiectul pointat folosim operatorul * astfel:

*pi = 5; // obiectul pointat ia valoarea 5

Atentie !!! Aceasta operatie poate fi aplicata numai pointerilor care
contin intr-adevar adresa unui obiect. De exemplu nu puteti face
dereferentierea unui pointer nul (cu valoare 0) sau
a unui pointer neinitializat. Este valabil si pentru operatorul -> care
contine si el o dereferentiere care se observa in scrierea echivalenta:
ps->nota este echivalent cu (*ps).nota

4. Pointeri si tablouri
Numele unui "tablou de T" este convertit automat la tipul "pointer la
T", deci poate fi folosit pentru a initializa un "pointer la T".
Valoarea acestui pointer este adresa primului element al tabloului:

T tab[10];
T* ptrT = tab; // ptrT contine adresa primului element

Un "pointer la T" este deseori folosit pentru a se referi pe rind la
elementele unui tablou. Urmatoarele operatii semnifica:

ptrT++ // pointeaza la urmatorul element din tablou
// creeaza o valoare stinga!
ptrT-- // pointeaza la elementul precedent din tablou
// creeaza o valoare stinga!

5. Eliberarea spatiului alocat dinamic
Daca un pointer a fost initializat cu adresa unui spatiu din zona de
alocare dinamica, atunci cind nu mai avem nevoie de spatiul respectiv
(adica nu mai avem nevoie de obiectul din spatiul
respectiv) vom elibera spatiul. El va putea fi astfel utilizat pentru
alocari ulterioare.
Daca p este un pointer care a fost initalizat printr-o alocare de
memorie, eliberarea memoriei alocate se exprima:

in C: free(p);
in C++: delete p;

Atentie!!!

Nici free() nici delete nu modifica valoarea pointerului p dar obiectul
a carui adresa este continuta de p nu trebuie sa fie referit dupa
eliberare.

6. Observatie
In laboratoarele urmatoare, vor exista cazuri in care anumiti pointeri
nu sint varibile simple, ci vor fi componente ale unor structuri de
date complexe. Toate regulile de mai sus se pastreaza.

Referinte
Cind vrem ca o functie, atunci cind este apelata, sa modifice valoarea
unei variabile din functia apelanta, trebuie sa trimitem ca argument un
pointer la acea varibila. De exemplu, o
functie care interschimba valoarea a doi "pointeri la student" va
trebui sa primeasca ca parametri doi "pointeri la pointeri la student":

void Schimba(Student** unu, Student** doi)
{
Student* trei;

trei = *unu;
*unu = *doi;
*doi = trei;
}

Daca argumentele au tipuri mai complicate, atunci sintaxa din
interiorul functiei devine greoaie. Pentru a rezolva aceasta problema
putem trimite ca argumente REFERINTE. Un argument
referinta trebuie interpretat ca fiind un PSEUDONIM pentru argumentul
pasat. Orice modificare a referintei se va face asupra argumentului
pasat:

void Schimba(Student*& unu, Student*& doi)
{
Student* trei;
trei = unu;
unu = doi;
doi = trei;
}

Observati ca sintaxa din interiorul functiei a devenit mai simpla.

Exercitiu
Sa se scrie un program care citeste studentii dintr-o grupa si ii
afiseaza in ordinea numelui si a notei. Programul va fi impartit in
patru module:

Modulul Student
Interfata acestui modul va fi STUDENT.H :

#ifndef _STUDENT_
#define _STUDENT_

struct Student {
char* nume;
int nota;
};

void InitStudent (Student&);
void AfisStudent (Student);
void StergeStudent (Student&);

#endif

Implementarea (fisierul STUDENT.CPP) cuprinde:

InitStudent citeste numele studentului (pentru care va aloca spatiu cu
malloc sau new) si nota.
AfisStudent afiseaza cimpurile structurii.
StergeStudent va elibera spatiul de memorie ocupat de nume (cu free sau
delete).

Modulul Grupa
Interfata acestui modul va fi GRUPA.H :

#ifndef _GRUPA_
#define _GRUPA_

#include "student.h"

struct Grupa {
Student* tab;
int nr;
int id; // numarul grupei, de exemplu 1105
};

void InitGrupa (Grupa&);
void AfisGrupa (Grupa);
void StergeGrupa (Grupa&);

#endif

Implementarea (fisierul GRUPA.CPP) cuprinde:

InitGrupa citeste numarul grupei si numarul de studenti, dupa care va
aloca spatiu cu malloc pentru acestia. Fiecare student va fi apoi
initializat cu InitStudent.
AfisGrupa afiseaza studentii.
StergeGrupa va elibera spatiul de memorie ocupat de cei nr studenti.

Modulul Index
Interfata acestui modul va fi INDEX.H :

#ifndef _INDEX_
#define _INDEX_

#include "student.h"
#include "grupa.h"

typedef Student* PStudent;
struct Index {
PStudent* idx;
int nr;
char* titlu;
};

void InitIndex (Grupa, Index&);
void SortNume (Index&);
void SortNota (Index&);
void AfisIndex (Index);
void AfisGrupaIndexata (Grupa, Index);
void StergeIndex (Index&);

#endif

Implementarea (fisierul INDEX.CPP) cuprinde:

Un Index contine adresa unui tablou de pointeri la studentii grupei. La
initializare (InitIndex) cimpul nr este initilizat cu numarul de
studenti din grupa, iar cimpul titlu cu sirul vid "".

InitIndex va aloca spatiu cu malloc pentru nr "pointeri la student" si
initializa fiecare pointer cu adresa studentului corespunzator.
AfisIndex afiseaza studentii in ordinea tabloului de pointeri.
StergeIndex va elibera spatiul de memorie ocupat de tablou si titlu.
AfisGrupaIndexata afiseaza numele grupei, titlul indexarii si apoi
apeleaza AfisIndex pentru a afisa studentii.
SortNume si SortNota ordoneaza tabloul de pointeri in ordinea
numelor/notelor studentilor la care se refera pointerii respectivi
(prin orice metoda).

Ordinea logica de apel este:
- InitIndex
- Afis / Sort / AfisGrupa
- StergeIndex

Modulul Program principal
Se va gasi in fisierul MAIN.CPP:

#include <stdio.h>
#include "student.h"
#include "grupa.h"
#include "index.h"

void main()
{
Grupa g;
Index x;
InitGrupa(g); // citeste studentii
AfisGrupa(g); // afiseaza grupa
InitIndex(g,x); // initializeaza un index
AfisGrupaIndexata(g,x); // afiseaza grupa prin index
SortNume(x); // ordoneaza indexul dupa nume
AfisGrupaIndexata(g,x); // afiseaza
SortNota(x); // ordonare dupa nota
AfisGrupaIndexata(g,x); // afisare
StergeIndex(x); // elibereaza spatiul
StergeGrupa(g); // elibereaza spatiul
}

Fisierele STUDENT.CPP, GRUPA.CPP, INDEX. CPP si MAIN.CPP se introduc
intr-un project LAB1.PRJ, si se compileaza impreuna.

Click aici pentru arhiva cu fisiere.

Laborator 2

Liste Inlantuite
Introducere
O lista este o colectie de elemente intre care este specificata o
anumita ordine. Pentru o lista inlantuita ordinea elementelor este
specificata
explicit printr-un cimp de informatie care face parte din fiecare
element,
specificind elementul urmator.

Deci fiecare element de lista inlantuita are urmatoarea structura:

Informatie utila Informatie de inlantuire
data link

Pe baza informatiei de inlantuire (pastrata in cimpul link) trebuie sa
poata
fi identificat urmatorul element din lista.
Lista inlantuita statica
Consideram urmatoarele declaratii:

struct Element {
char* data;
int link;
};

Element V[8];

Pentru elementele vectorului V exista o ordine naturala data de
aranjarea in
memorie a elemetelor sale: V[0], V[1], ... V[7]. Vom reperezenta
memoria
ocupata de vectorul V astfel incit fiecare element sa fie reprezentat
vertical, in felul urmator:
0 1 2 3 4 5 6 7
ÚÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄÂÄÄ¿
data ³ ³ ³ ³ ³ ³ ³ ³ ³
³ ³ ³ ³ ³ ³ ³ ³ ³
ÃÄÄÅÄÄÅÄÄÅÄÄÅÄÄÅÄÄÅÄÄÅÄÄ´
link ³ ³ ³ ³ ³ ³ ³ ³ ³
ÀÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÁÄÄÙ

Completind cimpul link pentru fiecare element al vectorului putem
obtine o
lista inlantuita. Valoarea cimpului link va fi index in vector al
urmatorului
element din lista.

Vectorul V:
V[0] V[1] V[2] V[3] V[4] V[5] V[6] V[7]

Pe baza inlantuirii stabilita de valorile din figura de mai sus se
obtine
ordinea: V[3], V[6], V[7], V[0], V[1], V[2], V[4], V[5].

Este necesar sa cunoastem care este primul element din inlantuire,
pentru
aceasta retinem intr-o variabila:

int cap;

indexul primului element

cap=3.

Parcurgerea in ordine a elemntelor listei se face in felul urmator:

int crt;
.................
crt = cap;
while (crt!=-1) {
Prelucreaza V[crt]
crt = V[crt].link;
}

Indiferent de modul cum se materializeaza informatiile de legatura
pentru a
reprezenta o lista inlantuita vom folosi urmatoarea reprezentare:

data link data link
Sageata care porneste din cimpul link arata faptul valoarea memorata
aici
indica elementul la care duce sageata.

Structuri autoreferite in C si C++

Pentru rolul pe care il joaca informatiile de legatura in structurile
inlantuite, cel mai potrivit este tipul pointer. Tipul cimpului link va
fi
"pointer la element de lista". Iata cum arata declaratiile tipului
"element de lista" in C++:

struct Element {
TipOarecare data; // informatia utila
Element* link; // legatura
};

In C va trebui sa scriem:

typedef struct _Element {
TipOarecare data;
struct _Element* link;
} Element;

Avind declaratiile de mai sus (una din forme), si

Element* p; // un pointer la Element

in urma unei operatii:

p = (Element*) malloc( sizeof(Element) ); // in C

sau, simplu

p = new Element; // in C++

p a fost initializat cu adresa unei variabile de tip Element alocata in
zona
de alocare dinamica:

*p
data link
p
p->data p->link

Atunci, aceasta din urma va fi identificata prin expresia *p iar
cimpurile
sale prin expresiile p->data si respectiv p->link .
Constanta 0 (NULL) pentru un pointer inseamna o adresa imposibila.
Aceasta valoare va fi folosita pentru a sfirsi inlantuirea (ultimul
element
din lista va avea p->link==0).
Pentru a manevra o lista avem nevoie doar de un pointer la primul
element al listei. Pentru a indica o lista vida acest pointer va primi
valoarea 0.

Operatii in liste inlantuite

Consideram declaratiile de tipuri de mai sus si variabilele:

Element* cap; // pointer la primul element al unei liste
Element* p;
Element* q;

Operatiile primitive pentru acces la o lista inlantuita sint:

Inserarea unui element in lista
Consideram: cap - contine adresa primului element din lista;
p - contine adresa unui element izolat care dorim
sa fie inserat in lista.

Fiecare sageata nou creeata insemna o atribuire: se atribuie varibilei
in
care sageata nou creata isi are originea, valoarea luata dintr-o
variabila in
care se afla originea unei sageti cu aceeasi destinatie.

In cazul nostru avem atribuirile (fiecare atribuire corespunde sagetii
cu
acelasi numar din figura):
(1) p->link = cap;
(2) cap = p;

Sa detaliem: Prima atribuire

p->link = cap;

leaga elementul de inserat de restul listei. In urma acestei atribuiri,
cap
si p->link vor indica ambii inceputul listei initiale
A doua atribuire:

cap = p;

pune in pointerul cap adresa elementului inserat in fata listei.

cap
ÉÍÍÍ» ÉÍÍÍÍÍÍÑÍÍÍ» ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍÍÍÍÑÍÍÍ»
ºÛÛÛº º ³ þÄ×ÄÄ>º ³ þÄ×ÄÄ>º ³ 0 º
Èͺͼ ÚÄ>ÈÍÍÍÍÍÍÏÍÍͼ ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍÍ» ÀÄÄÄÄÄÄÄ¿
p 2º ÉÍÍÍÍÍÍÑͳͻ
ÉÍÍÍ» ÈÍ>º ³ þ º
ºÛÛÛ×ÄÄÄ>ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍͼ
Observatie:
Daca pointerul cap este initial nul, (ceea ce inseamna inserarea intr-o
lista vida) atribuirile de mai sus functioneaza corect rezultind o
lista cu un singur element.

p->link = cap; // de fapt p->link = 0;
cap = p;
ÉÍÍÍ» ÉÍÍÍ»
º 0 º capº þÄ×Ä¿
ÈÍÍͼ ÉÍÍÍÍÍÍÑÍÍÍ» ÈÍÍͼ ³
ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍ» º ³ º ÉÍÍÍ» ÀÄ>º ³ 0 º
º þÄ×ÄÄÄ>ÈÍÍÍÍÍÍÏÍÍͼ p º
þÄ×ÄÄÄ>ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍͼ ÈÍÍͼ p->link

[B] Inserarea la mijloc sau la sfirsit
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß

Varibila q va indica elementul dupa care se face inserarea.
Situatia initiala:

cap ÉÍÍÍÍÍÍÑÍÍÍ» ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍ» º ³ þÄ×ÄÄÄÄÄ>º ³ þÄ×ÄÄÄÄÄÄ>º ³ 0 º
º þÄ×ÄÄÄ>ÈÍÍÍÍÍÍÏÍÍͼ ÚÄ>ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍͼ ÉÍÍÍ» ³
qº þÄ×ÄÙ ÉÍÍÍÍÍÍÑÍÍÍ»
ÈÍÍͼ ÉÍÍÍ» º ³ º
pº þÄ×ÄÄÄ>ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍͼ

Situatia finala: q->link
cap ÉÍÍÍÍÍÍÑÍÍÍ» ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍ» º ³ þÄ×ÄÄÄÄÄ>º ³ þ º ÚÄ>º ³ 0 º
º þÄ×ÄÄÄ>ÈÍÍÍÍÍÍÏÍÍͼ ÚÄ>ÈÍÍÍÍÍÍÏÍØͼ
³ ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍͼ ÉÍÍÍ» ³ ÚÄÄÙ ÀÄÄÄÄÄ¿
qº þÄ×ÄÙ ³ ÉÍÍÍÍÍÍÑÍÍÍ» ³
ÈÍÍͼ ÉÍÍÍ» ÀÄ>º ³ þÄ×ÄÙ
pº þÄ×ÄÄÄ>ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍͼ p->link

(1) p->link = q->link;
(2) q->link = p;

Observatii:
Atunci cind q indica ultimul element dintr-o lista, atribuirile de mai
sus functioneaza corect si adauga elementul indicat de p la sfirsitul
listei.

Nu se poate face inserarea in fata unui element dat (prin q) fara a
parcurge
lista de la capat.

Stergerea unui element din lista

Consideram: cap - contine adresa primului element din lista.

[A] Stergerea din fata
Prin operatia de stergere se intelege scoaterea unui element din
inlantuire.
Elementul care a fost izolat de lista trebuie sa fie procesat in
continuare,
cel putin pentru a fi eliberata zona de memorie pe care o ocupa, de
aceea
adresa lui trebuie salvata (sa zicem in variabila pointer p).

Situatia initiala:

cap ÉÍÍÍÍÍÍÑÍÍÍ» ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍ» º ³ þÄ×ÄÄ>º ³ þÄ×ÄÄ>º ³ 0 º
º þÄ×ÄÄÄ>ÈÍÍÍÍÍÍÏÍÍͼ ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍͼ

Situatia finala:
p
ÉÍÍÍ»
º þÄ×Ä¿1
ÈÍÍͼ ³
cap ³ ÉÍÍÍÍÍÍÑÍÍÍ» ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍ» ÀÄ>º ³ þÄ×ÄÄ>º ³ þÄ×ÄÄ>º ³ 0 º
º þ º ÈÍÍÍÍÍÍÏÍÍͼÚÄ>ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍØͼ ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ2

(1) p = cap;
(2) cap = cap->link;
delete p ; // Elibereaza zona de memorie

[B] Stergerea din mijloc sau de la sfirsit
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß

Varibila q va indica elementul din fata celui care va fi sters.

Situatia initiala:

ÍÍÑÍÍÍ» ÉÍÍÍÍÍÍÑÍÍÍ» ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍþ
³ þÄ×ÄÄÄÄÄ>º ³ þÄ×ÄÄÄÄÄÄ>º ³
þÄ×ÄÄÄÄÄÄ>º
ÍÍÏÍÍͼ Ú>ÈÍÍÍÍÍÍÏÍÍͼ ÈÍÍÍÍÍÍÏÍÍͼ
ÈÍÍÍþ
ÉÍÍÍ» ³
qº þÄ×ÄÙ
ÈÍÍͼ
p
Situatia finala: ÉÍÍÍ»
º þ º
ÈÍØͼ
ÍÍÑÍÍÍ» ÉÍÍÍÍÍÍÑÍÍÍ» ³ ÉÍÍÍÍÍÍÑÍÍÍ»
ÉÍÍÍþ
³ þÄ×ÄÄÄÄÄ>º ³ þ º ÀÄ>º ³ þÄ×ÄÄÄÄÄÄ>º
ÍÍÏÍÍͼ Ú>ÈÍÍÍÍÍÍÏÍØͼ ÈÍÍÍÍÍÍÏÍÍͼ
ÚÄ>ÈÍÍÍþ
ÉÍÍÍ» ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
qº þÄ×ÄÙ
ÈÍÍͼ
(1) p = q->link;
(2) q->link = p->link; // sau q->link = q->link->link;
delete p;

Observatii:
Atunci cind q indica penultimul element dintr-o lista, atribuirile de
mai sus functioneaza corect si sterg ultimul element din lista.

Nu se poate face steergerea elementului indicat de q fara parcurgerea
listei
de la capat.

ÛßßßÛßßßßßßßßßßßßßßßßßßßßÛ
Û 3 Û Parcurgerea listei Û
ÛÜÜÜÛÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÛ

Consideram: cap - contine adresa primului element din lista.

O parcurgere inseamna prelucrarea pe rind a tuturor elementelor listei,
in
ordinea in care acestea apar in lista. Vom avea o variabila pointer p
care va
indica pe rind fiecare element al listei:

p = cap; ³
while (p!=0){ ³ for(p=cap; p!=0; p=p->link){
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ Prelucreaza p->data ³ ³ ³ Prelucreaza p->data ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
p = p->link; ³ }
} ³

Un caz special apare atunci cind dorim sa facem o parcurgere care sa se
opreasca in fata unui element care sa indeplineasca o conditie (ca in
cazul
cind inseram un element intr-o pozitie data printr-o conditie, sau
stergem un
elemen care indeplineste o conditie).
Presupunem ca lista are cel putin un element.

p = cap;
while (p->link!=0 && !conditie(p->link))
p = p->link;

Bucla while se poate opri pe condifia "p->link==0", ceea ce insemna ca
nici
un element din lista nu indeplineste conditia iar poinertul p indica
ultimul
element din lista, sau pe conditia "conditie(p->link)" , ceea ce
insemna ca
pointerul p va contine adresa elementului din fata primului element
care
indeplineste conditia.

ÉÍÍÍÍÍÍ»
º Tema º Se citeste de la intrare un sir de numere intregi, pe o
linie, sir
ÈÍÍÍÍÍͼ incheiat cu o valoare zero.

a) Sa se plaseze numerele citite intr-o lista inlantuita, prin inserari

repetate in fata listei.
b) Sa se afiseze lista creata.
c) Se citeste un numar si sa se determine daca acesta se afla printre
elementele listei creat.
d) Sa se insereze un numar citit de la intrare intr-o pozitie citita
de la intrare.
e) Se se stearga un element din lista dintr-o pozitie citita de la
intrare.

Tema
ßßßßß
Sa se construiasca modul (fisierle .H si .CPP) care sa contina tipurile

de date si operatiile care implementeaza sub forma unei liste
inlantuite o
agenda de numere de telefon. Elementele listei vor contine ca
informatie
utila doua cimpuri:
-nume - numele persoanei;
-tel - numarul de telefon;
Elementele listei vor fi pastrate in ordine alfabetica dupa numele
persoanei.
Sa se definiesca procedurile care:
- insereaza un element in lista;
- sterge din lista o persoana data;
- cauta in lista numarul de telefon al unei persoane date;
- afiseaza lista in intregime.

Sa se construiasca un program care cu ajutorului unui meniu simplu sa
permita selectarea operatiilor definite mai sus.

1Laborator de Algoritmi Fundamentali si Structuri de Date
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°
°°°°°°°°°°°°°°°°°°
°°°°°°°°°°°°°°°°°°
°°°°°°°°°°°°°°°°°° Lucrarea nr. 3
²²°°°°°°°°°°°°°°°°
°°°°°°°°°°°°°°°°°°
²²°°°°°°°°°°°°°°°°
°°°°°°°°°°°°°°°°°° Stive
²²°°°°°°°°°°°°°°°°
°°°°°°°°°°°°°°°°°°
²²°°°°°°°°°°°°°°°°
°°°°°°°°°°°°°°°°°°°°²²²²²²²²²²²²²²²²²²²²²²²²²²²²°°°°°°°°°°°°°°°°
°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°

Introducere
ßßßßßßßßßßßß
O stiva este o structura de date de tip "container"
(depoziteaza obiecte de un anumit tip) organizata dupa principiul
LIFO (Last In First Out). Operatiile de acces la stiva (push -
adauga un element in stiva si pop -scoate un element din stiva)
sint create astfel incit pop scoate din stiva elementul introdus
cel mai recent.

push pop
ÄÄÄÄÄÄÄÄÄÄÄ¿ ÚÄÄÄÄÄÄÄÄÄÄÄ
º ³ ³ º
º ³ º
ÇÄÄÄÄÄÄÄÄÄÄĶ
ÇÄÄÄÄÄÄÄÄÄÄĶ
ÇÄÄÄÄÄÄÄÄÄÄĶ
ÇÄÄÄÄÄÄÄÄÄÄĶ
ÇÄÄÄÄÄÄÄÄÄÄĶ
ÇÄÄÄÄÄÄÄÄÄÄĶ
ÈÍÍÍÍÍÍÍÍÍÍͼ
Stiva

O stiva este un caz particular de lista, si anume este o lista
pentru care operatiile de acces (inserare, stergere, accesare
element) se efectueaza la un singur capat al listei.
Daca STACK este tipul stiva si ATOM tipul obiectele continute
in stiva atunci operatiile care definesc tipul structura de stiva
pentru tipul STACK sint:
þ CREATE() -> STACK
Operatia CREATE nu primeste paramatri si creeaza o stiva
care pentru inceput este vida (nu contine nici un
obiect).
þ PUSH(STACK, ATOM) -> STACK
Operatia PUSH primeste ca parametri o stiva si un obiect
si produce stiva modificata prin adaugarea obiectului in
stiva.
þ POP(STACK) -> STACK, ATOM
Operatia POP primeste ca parametri o stiva pe care o
modifica scotind un obiect. Deasemenea produce ca
rezultat obiectul scos din stiva.
þ TOP(STACK) -> ATOM
Operatia TOP intoarce ca rezultat obiectul din virful
stivei pe care o primeste ca parametru.
þ ISEMPTY(STACK) -> boolean
Operatia ISEMPTY este folosita pentru a testa daca stiva
este vida.

Implementari ale conceptului de stiva in C (++)
ßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßßß
[A] Stiva liniara
ßßßßßßßßßßßßßßßßßß
O stiva poate fi organizata pe un spatiu de memorare de tip
tablou (vector). Astfel, o stiva va fi formata dintr-un vector de
elemente de tip Atom si un indicator (index) al virfului stivei.

struct Stack{
int sp; // "stack pointer"
Atom vect[DIMSTACK];
};

Operatiile care definesc structura de stiva vor fi implementate
prin urmatoarele functii:

void initStack(Stack& S);
void push(Stack& S, Atom a);
Atom pop(Stack& S);
Atom top(Stack S);
int isEmpty(Stack S);

Observatie:
þ Un obiect Stack este un obiect de dimensiuni mari, fapt
pentru care nu este eficienta pasarea obiectelor de acest tip
prin valoare. Este indicata folosirea parametrilor referinta
pentru pasarea stivei chiar daca procedura nu are intentia de
a o modifica (cazul functiilor top si isEmpty).

Tema
Copiati continutul directorului J:\SDA\L3 in directorul
L:\ . Completaþi fisierul STACK1.CPP care trebuie sa
contina implementarea operatiilor definite pentru o stiva ordonata,
respectind declaratiile din STACK1.H.
Deschideti proiectul STACKTST.PRJ. Acesta este foemat din
urmatoarele module:
MENIURI.H , MENIURI.CPP - structurile de date si functiile
necesare pentru meniul programului;
MAINSTCK.CPP - un program de test care definieste un meniu prin
care se pot selecta operatiile asupra unei stive.

Compilati si rulati acest proiect pentru a testa corectitudinea
implementarii stivei.
=================================================================
||(Programele se gasesc la www.colegiu.go.ro/struct_la/lab3.zip) ||
=================================================================

[B] Stiva inlantuita

O stiva poate fi implementata ca o lista inlantuita pentru
care operatiile de acces se fac numai asupra primului element din
lista. Deci operatia PUSH va insemna inserare in prima pozitie din
lista (in fata) iar POP va insemna stergerea primului element din
lista. Pentru a manevra o stiva vom avea nevoie de un pointer la
primul element din inlantuire, deci vom echivala tipul Stack cu
tipul "pointer la element de lista", iar functiile care
implementeaza operatiile de acces vor vor avea aceleasi prototipuri
cu cele date mai sus.

struct Element {
Atom data;
Element* link; //legatura
};

typedef Element* Stack;

ÉÍÍÍÍÍÍÍÍ»
º Tema º Creati fisierul STACK2.CPP si scrieti in el
ÈÍÍÍÍÍÍÍͼ implementarea unei liste inlantuite conform
declaratiilor din fisierul STACK2.H.
Modificati proiectul STACKTST.PRJ, inlocuind modulul STACK1.CPP
cu STACK2.CPP si modificati in fisierul MAINSTK.CPP linia
#include "STACK1.H" inlocuind-o cu #include "STACK2.H".
Executati proiectul pentru a testa corectitudinea implementarii
listei inlantuite.

Stiva generica
ßßßßßßßßßßßßßßß
Operatiile de acces la o stiva sint aceleasi indiferent de
tipul obiectelor continute in stiva. Ar fi normal sa folosim codul
scris pentru a implementa procedurile push si pop pentru operatiile
de acceas la orice tip particular de stiva (stiva de intregi, stiva
de ferestre, etc.). Acest lucru nu este posibil in implementarile
date mai sus, unde procedurile care implementeaza operatiile de
acces la stiva sint particularizate pentru tipul Atom.
Iata o solutie care ar permite definirea operatiilor de acces
la stiva independent de tipul informatiei care se depune in stiva.
Vom folosi o stiva inlantuita de pointeri fara tip. Astfel fiecare
element de lista va memora adresa unui bloc de memorie in care este
memorata informatia utila.

cap ÚÄÄÄÂÄÄÄ¿ ÚÄÄÄÂÄÄÄ¿ ÚÄÄÄÂÄÄÄ¿
ÚÄÄÄ¿ ³ þ ³ þÍØÍÍ>³ þ ³ þÍØÍÍ>³ þ ³nil³
³ þÍØÍÍÍ>ÀÄ×ÄÁÄÄÄÙ ÀÄ×ÄÁÄÄÄÙ
ÀÄ×ÄÁÄÄÄÙ
ÀÄÄÄÙ º ÚÄÄÄÄÄÄÄ¿º ÚÄÄÄÄÄÄÄ¿º
ÚÄÄÄÄÄÄÄ¿
ÈÍ>³ ³ÈÍ>³ ³ÈÍ>³ ³
ÀÄÄÄÄÄÄÄÙ ÀÄÄÄÄÄÄÄÙ
ÀÄÄÄÄÄÄÄÙ
Atom Atom Atom
Vom obtine aceasta implementare vom defini tipul Atom drept la
tipul "pointer" in definitia stivei inlantuite de mai sus.
O astfel de definitie va avea avantajul ca o aceeasi stiva sa
pastreze elemente de tipuri diferite, tipul pointer insemnind
tocmai "pointer la orice". Ramine in sarcina programatorului sa
defineasca un mecanism prin care sa recunoasca tipul elementului
scos din stiva.

Fara tema!
ßßßßßßßßßßß