Liste liniare

Liste liniare

Definitie:

Se numeste lista liniara o multime secventiala de elemente de acelasi tip avand un numar arbitrar de elemente.

Dupa definitia anterioara se remarca asemanarea acestui tip de structura de date cu o structura standard: - tipul tablou cu o singura dimensiune (vector), - ambele structuri contin elemente de acelasi tip, iar intre elementele structurilor putandu-se stabili o relatie de ordine.

Exista insa si deosebiri, unele dintre ele relevand avantajul folosirii listelor in ambele probleme de rezolvat, in locul vectorilor.

Listele liniare pot contine un numar variabil de elemente, dimensiunea lor nu trebuie declarata anticipat, ea putandu-se modifica dinamic in timpul programului.

Unele deosebiri insa pot favoriza folosirea vectorilor, daca accesul la un element al vectorilor se poate face direct prin specificarea numarului de ordine al respectivului element, accesul la elementele unei liste liniare se face secvential, de la primul element al listei pina la ultimul element (aceasta presupune un timp mai mare de acces pentru gasirea unui element intr-o lista ).

Inlantuirea secventiala a elementelor intr-o lista se face cu ajutorul unei variabile de tip pointer care specifica adresa urmatorului element din lista.

Aceasta inseamna ca un element al unei liste liniare trebuie sa aiba o structura de tip articol (record), in care cel putin un cimp sa fie referinta. Celelalte cimpuri ale articolului contin informatia utila asociata fiecarui element.

In acest mod putem defini elementele unei liste liniare intr-o structura de tip articol (inregistrare) astfel:

Typedef struct lista

plista;

Cimpul 'inf' al unui articol de tip 'lista' contine informatia utila asociata unui element al listei, iar cimpul 'next' este pointerul spre urmatorul element din lista.

Pentru a putea identifica mai usor elementele unei liste liniare, in cimpul informatiei utile se poate departaja un cimp special, numit cimp de identificare al elementelor, sau cheie de identificare. Cel mai simplu mod de a defini o cheie de identificare il reprezinta asocierea fiecarui element cu un numa intreg, asemanator numarului de ordine al elementului unui tablou.

Putem defini acum elementul unei liste liniare printr-o structura de tip articol astfel:

typedef struct lista

unde 'key' reprezinta cheia de identificare a elementelor.

Observatie

Se pot defini mai multe chei de identificare pentru elementele unei liste: spre exemplu se pot defini doua chei care corespund respectiv liniei si coloanei unei matrici putind simula astfel o matrice de elemente printr-o structura :

typedef struct matrice

pmatrice;

Specificarea elementelor dintr-o lista liniara

Se reprezinta intii grafic elementele unei liste liniare

Se pun doua probleme in specificarea listelor liniare: cum se specifica primul element al unei asemenea liste si cum se specifica ultimul element.

Pentru rezolvarea primei probleme este necesara definirea in cadrul programului care lucreaza cu lista respectiva a unei variabile referinta (pointer) care sa memoreze adresa primului element al listei; pentru rezolvarea celei de-a doua probleme este necesar ca pointerul 'next' al ultimului articol sa primeasca valoarea NIL (NULL).

Cu aceste doua probleme rezolvate, pentru specificarea unui element al unei liste este necesara definirea in program a doua variabile:

-una de tipul elementelor listei declarate (o variabila de tipul articol LISTA in exemplul precedent) si o variabila referinta asociata tipului elementelor listei.

Exemplu:

Typedef struct lista plist;

lista elem;

plist *p0,*p1;

S-a definit tipul 'lista' ca tipul elementelor listei. Tipul 'plist' ca tipul pointerilor ce indica spre elementele de tip lista. De asemenea s-au definit variabilele: 'elem' care va contine informatia unui element al listei , 'p0' care va contine adresa primului element al listei si 'p1' cu ajutorul caruia se va specifica elementul respectiv.

Operatii elementare asupra listelor liniare

1. Parcurgera listei

Parcurgera unei liste se poate face de la primul element al listei pina la ultimul, sau parcurgerea pina la un anumit element cu o anumita cheie specificata (parcurgerea completa si parcurgerea partiala).

a) Parcurgerea completa a listei

Parcurgerea completa a unei liste liniare nu reprezinta un scop in sine, operatia respectiva se executa atunci cind se doreste ca o anumita actiune sa se execute asupra tuturor elementelor listei. Daca de exemplu exista o lista liniara unde elementele sale reprezinta examenele pe care un student le-a sustinut intr-un an precum si nota obtinuta si se doreste sa se calculeze media anuala a studentului respectiv atunci trebuie parcuse toate elementele listei citind notele obtinute, iar suma lor se va imparti la numarul total de examene. Actiunea ce trebuie executata asupra fiecarui element al listei o reprezinta citirea tipului care reprezinta nota obtinuta la respectivul examen si adunarea sa la o variabila globala (suma notelor).

Indiferent de tipul actiunii asupra elementelor, algoritmul de parcurgere al listei este foarte simplu si unitar, prezentindu-se in felul urmator:

p=p0;

do

while (p!=NULL);

Daca insa p0 nu a fost initializat, ciclul nu trebuie sa se execute. Corect este urmatorul algoritm:

p1=p0;

while (p1!=NULL)

b) Parcurgerea partiala a listei (cautare)

Parcurgerea partiala a unei liste se face cind se cauta in lista un element cu o anumita cheie. Se initializeaza lista prin capul ei (primul element) si se parcurg succesiv elementele pina se gaseste primul element cu o cheie identica cu cea cautata.

Un algoritm de cautare ar putea fi urmatorul:

p=p0;

while (p->key!=x) p=p->next;

unde am notat cu x valoarea cheii elementului ce trebuie gasit (ea trebuie sa fie de acelasi tip cu cimpul key).

Daca insa cheia x nu se gaseste la nici un element din lista algoritmul este gresit. Pentru corectare trebuie prevazut faptul ca ciclul de cautare se va opri, fie cind s-a detectat un element cu cheia x fie cind s-a ajuns la ultimul element al listei.

p=p0;

while (p!=NULL || p->key!=x) p=p->next;

2. Eliminarea unui element dintr-o lista

Actiunile ce se intreprind la eliminarea unui element dintr-o lista depind de pozitia elementului: primul element al listei, ultimul element, sau un element interior al listei.

a) Eliminarea primului element al listei

Se face foarte simplu modificind doar valoarea adresei pointerului p0 (care indica primul element). p0 trebuie sa indice spre urmatorul element care trebuie intii gasit. Trebuie intii parcusi deci doi pasi:

-gasirea adresei elementului al doilea al listei (care va deveni ulterior primul element);

-modificarea valorii pointerului p0.

Un model de algoritm care realizeaza aceasta actiune este urmatorul:

p=p0->next;

p0=p;

Grafic se poate reprezenta:

b)Eliminarea ultimului element

Pentru eliminarea acestuia trebuie gasit elementul care are drept succesor ultimul element (deci penultimul) si modificarea cimpului 'next' a respectivului element cu valoarea NIL (NULL).

Ar trebui folosite doua variabila pointer p1 si p2, prima care va parcurge lista pina la ultimul element, iar a doua pentru memorarea adresei elementului anterior (cind p1 ajunge la ultimul element, p2 va ajunge la penultimul element); pentru simplitate se poate folosi un singur pointer, testind insa cu ajutorul lui cimpul 'next' al urmatorului element:

p->next->next;

Acest lucru va fi valabil doar in cazul cind lista are cel putin doua elemente; daca are unul singur, el va fi eliminat modificind valoarea lui p0 la NIL (NULL).

p=p0;

if (p->next==NULL) p0=NULL;

else

Grafic lista se poate reprezenta:

c) Eliminarea unui element intermediar

Pentru eliminarea nodului, acesta trebuie specificat fie prin adresa sa (data de valoarea unui pointer p1) fie prin valoarea cheii.

Dupa determinare elementul va fi eliminat prin modificarea cimpului next al elementului anterior cu valoarea adresei elementului urmator.

Grafic acest lucru se poate reprezenta :

In orice mod ar fi specificat elementul ce trebuie eliminat lista trebuie parcursa de la inceput pina la elementul respectiv. In algoritmul prezentat in continuare vom considera elementul specificat prin cheia sa (notata x). Ca si in exemplul precedent folosim o singura variabila pointer p in loc de doua (p1 si p2).

p=p0;

while (p->next->key!=x) p=p->next;

p->next=p->next->next;

3. Inserarea unui element intr-o lista

Inserarea unui element intr-o lista necesita urmatoarele actiuni:

-alocarea dinamica de memorie pentru elementul ce urmeaza sa fie introdus ;

-introducerea informatiei utile a elementului (inclusiv cheia);

-legarea elementului introdus in elementele listei ;

Dupa pozitia pe care o va ocupa in cadrul listei, elementul respectiv, pentru orice situatie avem:

a) Inserarea elementului la inceputul listei:

Algoritmul pentru inserare poate fi urmatorul:

p=(plist *)malloc(sizeof(plist));

(incarcare informatie utila);

p->next=p0;

p0=p;

Grafic avem:

Observatie

Trebuie modificata valoarea lui 'p0' cu adresa noului element introdus.

b) Inserarea unui element la sfirsitul listei

De data aceasta trebuie folosite doua variabile referinta p si p1; pointerul p va parcurge lista, iar p1 se va folosi pentru generarea unei noi zone de memorie.

p1=(plist *)malloc(sizeof(plist));

p1->next=NULL;

(incarcare informatie utila);

p=p0;

while (p->next!=NULL) p=p->next;

p->next=p1;

Algoritmul presupune ca lista nu este vida. Pentru a prevedea si situatia aceasta , el trebuie modificat astfel:

if (p0==NULL)

else

c) Inserarea unui element in interiorul listei

Cel mai comod se face inserarea dupa un element specificat al listei.

Specificarea se poate face fie prin cheie, fie prin adresa (valoarea unui pointer). Se va presupune ca lista are cel putin doua elemente.

Grafic:

Actiunile ce trebuie realizate sunt:

-alocarea memoriei prin noul element si incarcarea informatiei utile (mai putin cimpul next);

-cautarea in lista a elementului specificat;

-legare a elementului in lista ;

Algoritmul de inserare este urmatorul:

p1=(plist *)malloc(sizeof(plist));

(incarcare informatii utile);

p=p0;

while (p->key!=x) p=p->next;

p1->next=p->next;

p->next=p1;

4. Crearea listelor liniare simplu legate

Desi crearea este prima operatie care trebuie facuta am preferat descrierea sa la sfirsit pentru ca foloseste elemente descrise anterior si anume inserarea unui element intr-o lista.

Crearea unei liste presupune crearea primului element si apoi inserarea de noi elemente inainte sau dupa elementul deja creat. Rezulta ca o lista se poate crea ori de la ultimul element, ori de la primul spre ultimul element, dupa cum inserarea se face de la inceputul, sau la sfirsitul listei.

Testarea momentului cind nu se mai insereaza elemente in lista (cind s-a creat toata lista) depinde strict de programul respectiv. Pentru exemplificarea algoritmului de creare al listelor liniare, presupunem ca aceasta se specifica printr-o introducere a unui caracter de la tastatura.

a) Crearea unei liste liniare incepind cu primul element

p=(plist *)malloc(sizeof(plist));;

p->next=NULL;

(introducere informatii utile);

p0=p;

do pelem;

pelem *p1, *p2, *p, *pp;

int i, j, n;

int vect[10];

void main(void)

p2 = NULL;

p = p1;

i = 1;

/* inverseaza lista */

do while (!(p == NULL));

printf('Elem. in ordine descrescatoare:    n');

p = p2;

do

while (!(p == NULL));

Observatie:

Se remarca o simplitate a algoritmului de creare a listei incepind cu ultimul element, in sensul ca primul element creat din lista nu are pozitie privilegiata (crearea sa se face in cadrul aceluiasi ciclu cu celelalte elemente).

Putem rescrie algoritmul b) de creare a listelor inlantuite astfel:

p0=NULL;

do

while (ch!='y');

2. Presupunem ca un program poate apela direct subrutine si fiecare subrutina poate apela la rindul sau cel mult o subrutina. Studiindu-se necesarul de memorie pentru fiecare subrutina (si pentru programul principal) sa se stabileasca necesarul de memorie pentru incarcarea intregului program.

Programul va avea o structura de apelare a subrutinelor de genul arbore pe doua nivele, asemanator cu cel din figura.

Am notat programul principal cu cifra zero si fiecare subrutina cu un numar. Putem structura informatia de intare astfel: pentru fiecare rutina apelata direct se poate specifica necesarul de memorie si rutina apelata din aceasta intr-o matrice cu linii si 2 coloane (numarul subrutinei proprii si numarul ultimei apelate).

De asemenea se poate crea o lista simpla inlantuita ce are ca elemente programul principal si toate rutinele folosite si fiecare element are ca informatie utila (in afara de cheie care este numarul rutinei) marimea zonei de memorie necesara. In acest fel, parcurgind liniile matricei de intrare pentru fiecare din acestea se parcurge lista de mai sus determinind memoria totala prin insumare.

#include <stdio.h>

#include <stdlib.h>

#include <alloc.h>

typedef struct brutina

prutina;

prutina *p0, *p;

int direct[20][3];

int i, j, k, n;

void main()

while (i>=0);

printf('Introduceti nr. de rutine apelate direct');

scanf('%d',&n);

printf('Pentru fiecare rutina introduceti numarul rutinei', 'apelate');

for (i=1;i<=n;i++) scanf('%d%d',&direct[i][1],&direct[i][2]);

k=0;

for (i=1;i<=n;i++)

while (p!=NULL);

}

printf('Necesarul de memorie pt. incarcare este: %d',k);

Probleme propuse

1. Sa se scrie algoritmul a) pentru crearea unei liste simple inlantuite incepind cu primul element, generind toate elementele listei in cadrul unui singur ciclu.

2. Sa se scrie programul de inversare a unei liste din problema rezolvata 1 folosind problema propusa.

3. Sa se rescrie programul de inversare a unei liste de la problema rezolvata 2 folosind problema propusa 1.

4. Sa se scrie procedurile pentru introducerea si extragerea unui element dintr-o lista liniara simplu inlantuita eliberindu-se in acelasi timp memoria afectata unui element in urma extragerii lui din lista. Sa se foloseasca acestea pentru crearea unei liste plecind de la un vector de numere reale si apoi sa se extraga elementele negative si sa se testeze elementele ramase in urma extragerii.

5. Sa presupunem ca pentru reprezentarea coeficientilor unui polinom de o variabila utilizam o lista liniara simplu legata descrisa astfel:

type

polypointer=^polynode;

polynode=record

coef:integer;

exp:integer;

link:polypointer;

end;

Sa se scrie proceduri pentru:

a) Citirea unui polinom;

b) Afisarea unui polinom;

c) Calculul valorii unui polinom intr-un punct;

d) Calculul derivatei unui polinom;

e) Adunarea a doua polinoame;

f) Scaderea a duua polinoame;

g) Inmultirea a doua polinoame;

h) Dealocarea spatiului rezervat unui polinom.

6. Sa se scrie o procedura care determina inversa pe loc a unei liste liniare simplu legate.

7. Se considera o lista liniara simplu legata care contine un numar par de elemente. Sa se scrie proceduri pentru construirea unei liste formate din elementele de rang par din lista data, in urmatoarele ipoteze:

a) Pastrarea ordinii lor din lista initiala;

b) Inversarea ordinii lor din lista initiala;

8. Aceeasi problema pentru cazul cind lista initiala contine un numar impar de elemente.

9. Se considera doua liste liniare simplu legate avind acelasi numar de elemente. Sa se scrie o procedura ce construieste o a treia lista simplu legata prin preluarea succesiva a cite unui element din fiecare dintre cele doua liste initiale, in ordinea in care acestea apar in cadrul acestor liste. Procedura va construi lista prezentata.

10. Aceeasi problema ca si cea anterioara cu mentiunea ca alegerea succesiva a cite unui element din fiecare dintre listele initiale se va face la intimplare, indiferent de ordinea de aparitie a elementelor din cadrul celor doua liste. Se presupune existenta unei functii 'random (a,b)' care la fiecare apel intoarce un numar aleator intreg cuprins intre a si b.

11. Sa se scrie o procedura care testeaza apartenenta unui anumit element dat la o lista liniara simplu legata data.

12. Scrieti o procedura care verifica daca o lista liniara simplu legata contine sau nu elemente care se repeta.