|
Liste
|
Structuri recursive
|
La
capitolul privitor la recursivitate, aceasta a fost ilustrata ca o proprietate
specifica algoritmilor. Sa revedem
definitia recursivitatii:
Un
obiect sau un fenomen se defineste in mod recursiv daca in definitia sa
exista o referire la el insusi.
Se
va prezenta in continuare extinderea acestei proprietati asupra tipurilor
de date, in forma structurilor de date
recursive.
Prin
analogie cu algoritmii, prin structura recursiva se intelege o structura
care are cel putin o componenta de acelasi tip cu structura insasi. Si
in acest caz poate exista recursivitate directa sau indirecta.
Pentru
evitarea structurilor infinite, in definitia recursiva trebuie sa existe
o conditie de care depinde prezenta efectiva a componentei sau componentelor
recursive.
Structurile
recursive pot fi implementate in C numai in forma unor structuri dinamice,
deoarece o structura nu poate avea un camp de acelasi tip structura, ci
doar pointer la structura.. Deci definitia unei structurii recursive recursiva
va deveni: o structura care are o componenta de tip pointer la structura
insasi.
Limitarea
structurilor recursive se realizeaza prin existenta valorii NULL
pentru pointeri.
La
modul general, o structura recursiva
se defineste:
struct recursiva{ //
reprezinta un nod al unui arbore generalizat
tip1 camp1; //
m campuri de tipuri oarecare
tip2 camp2;
...
tipm campm;
struct recursiva *p1,
*p2, ..., *pn; //
L
//
n campuri de tip pointer la structura
};
Cu extensiile
aduse de C++, cum numele unei structuri este nume de tip, linia L devine:
recursiva
*p1, *p2, ..., *pn;
In
continuare discutia se va referi la structurile recursive care au o
singura componenta pointer la structura.
Structura de date lista
|
Lista
este o structura dinamica, situata in memoria centrala, in care
toate elementele sunt de acelasi tip; numarul de elemente este variabil,
chiar nul.
De
remarcat diferentele fata de definitia tabloului: tabloul este o
structura
statica, situata in memoria centrala, in care toate elementele sunt
de acelasi tip; numarul de elemente este constant.
O alta
definire a listei este:
O
lista L este o secventa de zero sau mai multe elemente, numite noduri,
toate fiind de acelasi tip de baza T.
L=a1,a2,...,an
(n>=0)
Daca
n>=1, a1 se spune ca este primul nod al listei, iar an, ultimul
nod. Daca n=0, lista este vida.
Numarul
de noduri se numeste lungimea listei.
Un
nod
al listei liniare care apare ca o structura recursiva, avand o componenta
de tip pointer la structura, reprezentand legatura ( inlantuirea
) spre nodul urmator. Lista in care fiecare nod are o sinfura inlantuire
se numeste lista simplu inlantuita.
struct
nod{
TipCheie cheie;
TipInfo info;
struct Nod* urmator;
};
struct nod* inceput;
//pentru
o scriere mai compacta se pot defini tipurile:
typedef struct nod Nod, *pNod;
pNod inceput; |
Caracteristica
unei astfel de structuri consta in prezenta unei singure inlantuiri. Campul
cheieserveste
la identificarea nodului, campul urmatore
pointer de inlantuire la nodul urmator, iar cel infocontine
informatia utila.
Variabilainceputindica
spre primul nod al listei. In unele situatii in locul lui inceputse
utilizeaza un nod fictiv, adica o variabila de tip struct
Nod cu
campurile cheie
si info neprecizate,
dar campul urmatorindicand
spre primul nod al listei.
De
asemenea uneori este util a se pastra pointerul spre ultimul nod al listei.
O varianta
este a listelor circulare la care dispare notiunea de prim, ultim
nod, lista fiind un pointer ce se plimba pe lista.
Tehnici de insertie a nodurilor
|
-
Insertia
unui nod la inceputul listei
Daca inceputeste
variabila pointer ce indica spre primul nod al listei, iarqo
variabila auxiliara de tip pointer, secventa urmatoare realizeaza insertia
la inceputul listei si actualizeaza pointerulinceput:
pNod inceput, q;
q=(pNod)malloc(sizeof(Nod)); //creaza
spatiu pentru un nou nod
q->urmator=inceput;
//asignarea
campurilor cheie si info
inceput=q; |
Secventa
este corecta si pentru insertia intr-o lista vida, caz in care valoarea
lui inceput
esteNULL.
-
Insertia
unui nod la sfarsitul listei
Devine
mai simpla daca se pastreaza o variabilasfarsit
indicand spre ultimul nod al listei:
pNod inceput, sfarsit, q;
q=(pNod)malloc(sizeof(Nod)); //creaza
spatiu pentru nou nod ultim
sfarsit->urmator=q;
q->urmator=NULL;
//asignarea
campurilor cheie si info
sfarsit=q; |
Pentru
insertia la sfarsitul listei este necesara existenta a cel putin unui nod,
care se creaza prin secventa de la paragraful anterior.
-
Insertia
unui nod dupa unul indicat
Este simpla
pentru ca se cunoaste pointerul spre nodul anterior si spre cel urmator
celui care se insereaza (pointerul spre nodul urmator este valoarea campului
urmator al nodului indicat).
-
Insertia
unui nod in fata unui nod indicat
Printr-un
artificiu, se reduce acest caz la cel anterior: se insereaza un nod dupa
cel indicat, cheia si informatia din nodul indicat fiind atribuite noului
nod inserat si fiind inlocuite cu valorile nodului care trebuia inserat.
Tehnici de suprimare a nodurilor
|
Pentru
suprimarea nodului urmator celui indicat de o variabila pointerq,
prin
atribuirea:
q->urmator=q->urmator->urmator;
se
exclud din lista legaturile la si de la nodul de suprimat.
Pentru
suprimarea nodului anterior unuia precizat, se aduce nodul precizat in
cel de suprimat. Apoi se suprima succesorul lui, deci cel indicat initial
de variabila pointer q:
*q=*q->urmator;
/*
pentru expresia din dreapta, operatorul de selectie indirecta ->
este mai prioritar decat cel de indirectare *, deci nu sunt necesare
parantezele */
Traversarea unei liste
|
Daca
nodul de inceput al listei este indicat de variabila
inceput,
o variabila auxiliara q,
care parcurge toate nodurile listei pana cand valoarea ei devine NULL,
permite accesul la fiecare nod si efectuarea operatiei specifice traversarii:
for(q=inceput;q!=NULL;q=q->urmator)
//prelucrarea
nodului indicat de q
Daca
lista are doua noduri fictive, unul de inceput si unul de sfarsit, secventa
de traversare devine:
for(q=inceput->urmator;q!=sfarsit;q=q->urmator)
//prelucrarea
nodului indicat de q
Aplicatii ale listelor
|
-
Liste
ordonate si reorganizarea listelor
a)Cautarea
intr-o lista neordonata; tehnica fanionului
Se considera
o lista simplu inlantuita, cu nodurile de tip Nod. Daca inceput indica
spre primul nod al listei, iar ordinea cheilor in lista este aleatoare,
cautarea unei chei implica traversarea listei. Functia booleana gasit returneaza
valoarea pointerului spre nodul cu cheia egala cu cea cautata, daca un
astfel de nod exista si valoarea NULL in caz contrar:
pNod gasit(TipCheie val){
pNod poz;
poz=inceput;
while (poz!=NULL)
if (poz->cheie==val)
return poz;
else
poz=poz->urmator;
return poz; //
cu valoarea NULL |
Cautarea
se poate perfectiona prin utilizarea
metodei fanionului, lista prelungindu-se
cu un nod fictiv numit fanion, la creare lista continand acest unic
nod. In functia gasit,
inainte de baleierea listei, informatia cautata se introduce in cheia nodului
fanion, astfel incat va exista cel putin un nod cu cheia cautata:
pNod fanion;
pNod gasit(TipCheie val){
pNod poz;
for(poz=inceput,fanion->cheie=val;poz->cheie!=val;
poz=poz->urmator);
if(poz==fanion)
return NULL;
return poz; |
b)Crearea
unei liste ordonate; tehnica celor doi pointeri
In
continuare se prezinta o metoda foarte simpla pentru crearea unei liste
ordonate, tipurile pNod si Nod fiind cele definite anterior. Lista se initializeaza
cu doua noduri fictive pointate de doua variabile pointer, inceput
sifanion:
pNod inceput, fanion;
void init(void);
inceput=(pNod)malloc(sizeof(Nod));
fanion=(pNod)malloc(sizeof(Nod));
inceput->urmator=fanion;
} |
Pentru
introducerea unei noi chei in lista, pastrand ordonarea, se va scrie o
functie gasit, care daca gaseste cheia in lista returneaza valoarea 1 si
pointerii p1 spre nodul gasit si p2 spre cel anterior, respectiv in cazul
negasirii cheii, valoarea 0 si pointerii p1 si p2 spre nodurile intre care
trebuie facuta insertia:
int gasit(TipCheie val, pNod* p1, pNod* p2){
for(*p2=inceput,*p1=(*p2)->urmator,fanion->cheie=val;
(*p1)->cheie<=val;p2=p1,*p1=(*p1)->urmator);
return *p1!=fanion && (*p1)->cheie==val; |
Fragmentul
de program care insereaza o noua cheie este:
pNod p1,p2,p3;
TipCheie val;
...
if (!gasit(val,&p1,&p2)){
p3=(pNod)malloc(sizeof(Nod)); //creare
nod nou
p2->urmator=p3; //legatura de la nodul anterior la cel nou
p3->cheie=val;
//completare p3->info
p3->urmator=p1; //legatura
de la noul nod la cel urmator
} |
Pentru
tiparirea cheilor dintr-o lista ordonata astfel creata, pointerul care
parcurge nodurile trebuie sa fie initializat cu valoarea pointerului spre
primul nod efectiv al listei, urmator celui
inceput,
iar parcurgerea listei se face pana la intilnirea nodului fanion:
pNod p;
for(p=inceput->urmator;p!=fanion;p=p->urmator)
//prelucrarea
nodului indicat de p |
Exemplu
|
Sa
se realizeze un program care raspunde la urmatoarele comenzi:
'a' - Citeste o linie de forma
identificator , numar ;
unde
numar este un numar intreg si retine in evidenta identificatorul impreuna
cu numarul asociat lui.
't' - Citeste o linie care contine un identificator. Daca acesta se gaseste
in evidenta se tipareste valoarea asociata lui , in caz contrar se tipareste
un mesaj de eroare.
's' - Citeste o linie ce contine un identificator si il sterge din evidenta.
'l' - Tipareste in ordine alfabetica identificatorii din evidenta impreuna
cu valorile asociate lor
'+' - Citeste doua linii , fiecare continand un identificator. In cazul
in care ambii se afla in evidenta , se tipareste suma lor. In caz ca unul
sau ambii identificatori lipsesc din evidenta se tipareste un mesaj de
eroare.
'-' - Citeste doua linii , fiecare continind un identificator. In cazul
in care ambii se afla in evidenta , se tipareste diferenta lor. In caz
ca unul sau ambii identificatori lipsesc din evidenta se tipareste un mesaj
de eroare.
'*' - Citeste doua linii , fiecare continand un identificator. In cazul
in care ambii se afla in evidenta , se tipareste produsul lor. In caz ca
unul sau ambii identificatori lipsesc din evidenta se tipareste un mesaj
de eroare.
'/' - Citeste doua linii , fiecare continind un identificator. In cazul
in care ambii se afla in evidenta , se tipareste rezultatul impartirii
lor. In caz ca unul sau ambii identificatori lipsesc din evidenta se tipareste
un mesaj de eroare.
'f' - Se termina programul
In
lista identificatorii sunt pastrati in mod ordonat.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max 10
typedef struct elem{
char *id;
int valoare;
struct elem *urm;
} Nod,*pNod;
void listare( void );
pNod cauta( char* );
void sterge( char* );
void introdu( char*, int );
nod *radacina = NULL;
pNod ccauta( pNod lista , char *s )
{
pNnod q1 ;
for( q1 = lista ; q1 != NULL && strcmp( q1->id,s ) < 0 ;
q1 = q1->urm );
if ( q1 != NULL && strcmp( q1->id,s ) == 0 )
return q1;
return NULL;
}
void clist( pNod lista )
{
pNod q;
for( q = lista ; q != NULL ; q = q->urm )
printf(" identificator:%s, valoare:%d\n",q->id,q->valoare);
}
pNod csterge( pNod lista, char *s )
{
pNod q1 , q2;
for( q1 = q2 = lista ; q1 != NULL && strcmp( q1->id,s ) < 0;
q2 = q1, q1 = q1->urm);
if( q1 != NULL && strcmp( q1->id,s ) == 0 )
if( q1 != q2 )
{
q2->urm = q1->urm;
return lista ;
}
else return lista->urm;
else
{
printf("Eroare:identificatorul %s nu apare in lista\n",s);
return lista;
}
}
pNod cintrodu( pNod lista , char *s ,int v)
{
pNod q1 , q2 , aux;
if( ( aux = (pNod)malloc(sizeof(Nod))) == NULL ||
( aux->id = (char *) malloc(strlen(s) +1)) == NULL )
{
printf(" Eroare: memorie insuficienta\n");
exit( 1 );
}
else
{
strcpy( aux->id,s );
aux->valoare = v;
}
for( q1 = q2 = lista ; q1 != NULL && strcmp( q1->id,s ) < 0;
q2 = q1, q1 = q1->urm);
if( q1 != NULL && strcmp( q1->id,s ) == 0 )
{
printf(" Eroare : %s apare in lista\n",s);
return lista;
}
else
if( q1 != q2 )
{
q2->urm = aux ;
aux->urm = q1;
return lista ;
}
else
{
aux->urm = lista;
return aux;
}
}
void listare(void)
{
clist( radacina );
}
pNod cauta( char *s )
{
return ccauta( radacina , s );
}
void sterge( char *s )
{
radacina = csterge ( radacina, s );
}
void introdu( char *s, int v)
{
radacina = cintrodu( radacina, s, v );
}
void getlin( char *s , int *val )
{
int i = 0, j;
char temp[ Max ];
gets( temp );
s[ i ] = '\0' ; *val = 0;
while( temp[ i ] != '\0' )
if( isalpha( temp[ i ] ))
{
j = 0;
while( isalnum( temp[ i ])) s[ j++ ] = temp[ i++ ];
s[ j ] = '\0';
}
else
if( isdigit( temp[i] ))
while( isdigit( temp[i] ))
{
*val = *val * 10 + temp[i] - '0' ;
i++;
}
else i++;
}
void ad( void )
{
int
val;
char
s[ Max ];
getlin(
s , &val );
if(
strlen( s ) != 0 ) introdu( s , val );
else printf(" Eroare : linie incorecta \n");
}
void ti( void )
{
char s[ Max ];
nod *p;
int val;
getlin( s , &val );
if( strlen( s ) != 0 )
{
if( ( p = cauta( s )) != NULL )
printf("identificator:%s,valoare :%d \n",p->id,p->valoare);
else printf(" Eroare: identificator nedefinit \n");
}
else printf(" Eroare: linie incorecta \n");
}
void st( void )
{
char s[ Max ];
int val;
getlin(s , &val );
if( strlen( s ) != 0 ) sterge( s );
else printf(" Eroare: linie incorecta \n");
}
void oper( char c )
{
char s1[ Max ] , s2[ Max ];
int val;
nod *p1 , *p2;
getlin(s1 , &val);
getlin(s2, &val);
if(( strlen( s1 ) != 0 ) && ( strlen( s2 ) != 0))
if((( p1 = cauta( s1 )) != NULL) &&
(( p2 = cauta( s2 )) != NULL ))
{
switch( c )
{
case '+' : val = p1->valoare + p2->valoare ; break;
case '-' : val = p1->valoare - p2->valoare ; break;
case '*' : val = p1->valoare * p2->valoare ; break;
case '/' : if( p2-> valoare != 0 )
val = p1->valoare / p2->valoare ;
else printf(" Eroare: Impartire la 0\n") ;
break;
}
printf(" Rezultatul operatiei e %d \n", val);
}
else printf(" Eroare: linie eronata \n ");
}
void meniu(void)
{
char o;
while( 1 )
{
clrscr();
printf(" a .... adauga in evidenta un id si val asociata \n");
printf(" t .... tipareste valoarea asociata unui id \n");
printf(" s .... sterge un id \n");
printf(" l .... listeaza id-rii si valorile asociate \n");
printf(" + .... calculeaza suma pt. 2 id \n");
printf(" - .... calculeaza diferenta pt. 2 id \n");
printf(" * .... calculeaza produsul pt. 2 id \n");
printf(" / .... calculeaza impartirea pt. 2 id \n");
printf(" f .... termina programul \n");
printf("\n Introduceti optiune :"); o = getchar(); getchar();
switch(tolower(o))
{
case 'a': ad();break;
case 't': ti();break;
case 's': st();break;
case 'l': listare();break;
case '+': case '-' : case '*' : case '/' : oper(o); break;
case 'f' : return;
default : printf(" Eroare : Comanda inexistenta \n");
}
getchar();
}
}
void main( void )
{
meniu();
} |
Functiaccauta
cauta un identificator in lista returnand pointerul nodului in care s-a
gasit identificatorul. Functia clist
afiseaza
continutul listei. csterge
elimina un nod din lista, iar cintrodu
va introduce un nod in lista. Aceste functii au ca si parametru formal
pointerul de inceput al listei prelucrate.
Folosind
aceste functii se definesc cauta,
sterge
si introdu cu
rolul de cautare , stergere si introducere a unui identificator, precum
si functia listare
, care va lista identificatorii din lista.
Functia
meniuafiseaza
meniul programului , preia un caracter , reprezentand o comanda , care
se va prelucra prin apelul functiei asociate.
Functia
operare
ca si parametru operatorul de executat .Functia citeste doi identificatori
gaseste in lista valorile asociate lor, dupa care executa si afiseaza rezultatul
operatiei.
Exercitii
|
1.Informatiile
despre abonatii telefonici (nume, adresa, numar de telefon) se pastreaza
intr-o lista ordonata alfabetic dupa numele abonatilor. Sa se realizeze
un program interactiv care realizeaza operatiile:
-
adaugarea
unui nou abonat
-
scoaterea
din evidenta a unui abonat
-
afisarea
numarului de telefon al unui abonat
-
afisarea
datelor unui abonat cu un numar dat
-
afisarea
intregii liste.
2.Se prelucreaza
un fisier text oarecare, contorizand pentru fiecare identificator, numarul
de aparitii. Se vor crea doua liste, in variantele:
-
lista
neordonata, cu nod fanion si insertie la inceputul listei
-
lista
ordonata avand doua noduri fictive.
3.Sa se
implementeze un set de functii care realizeaza urmatoarele operatii:
-
adauga(
t, id ) : introduce identificatorul id in lista t
-
prezent(
t, id ): returneaza 1 sau 0 dupa cum identificatorul id este sau
nu prezent in lista t
-
sterge(
t, id ) : elimina identificatorul id din lista t
-
reuneste(
t1,t2,t ) : lista t va contine toti identificatorii din t1 sau t2
-
intersectie(
t1,t2,t ) : lista t va contine toti identificatorii care sint prezenti
in t1 si t2
-
scadere(
t1,t2,t ) : lista t va contine identificatorii care sunt prezenti in t1
si absenti in t2
-
tipareste(
t ) : tipareste in ordine alfabetica identificatorii din t
Folosind
functiile de mai sus, sa se realizeze un program care citeste doua secvente
de text consecutive , care se termina fiecare cu o marca EOF. Dupa citirea
textelor se cere sa se tipareasca in ordine alfabetica identificatorii
prezenti in primul text , apoi cei din al doilea text. In final se vor
tipari in ordine alfabetica identificatorii care sunt prezenti atat in
primul cat si in al doilea text.
Copyright
© 2001-2002. Carmen Holotescu
All
rights reserved. Published by Timsoft
|