Tehnici de programare

Definiţie: O listă este o colecţie de elemente de informaţie (noduri) aranjate într-o anumită

ordine.

Lungimea unei liste este numărul de noduri din listă.

Structura corespunzătoare de date trebuie să ne permită să determinăm eficient care este

primul sau ultimul nod în structură şi care este predecesorul sau succesorul unui nod.

În imaginea de mai jos este reprezentată o listă liniară de lungime patru.

Operaţiile care se fac într-o listă se pot împărţii astfel:

A) Operaţii care schimbă conţinutul listei sunt:

- Adăugarea de noi noduri la începutul sau sfârşitul listei;

- Inserarea de noi noduri în orice loc din listă;

- Ştergerea de noduri din orice poziţie a listei;

- Modificarea unui nod dintr-o poziţie dată.

B) Operaţii care schimbă structura listei sunt:

- Inițializarea unei liste ca o listă vidă.

C) Operaţiile de caracterizare sunt:

- localizarea nodului din listă care satisface un anumit criteriu;

- determinarea lungimii unei liste.

D) Alte operaţii ce se pot face într-o listă:

- Parcurgerea unei liste;

- Separarea unei liste în două sau mai multe subliste;

- Selecţia nodurilor dintr-o listă care îndeplinesc anumite criterii;

- Crearea unei liste ordonate după valorile sale (ordonare crescătoare sau

descrescătoare)

- Combinarea a două sau a mai multor liste prin concatenare sau interclasare.

Primul

element

Ultimul

element

predecesor succesor

Capul

listei

Coada

listei nod 1 nod 2 nod 3 nod 4

Laborator 1 Tehnici de programare 2015

2

Lector dr. Laura Stoica

Spaţiul din memorie ocupat de listă poate fi alocat în două moduri: prin alocare secvenţială

sau prin alocare înlănţuită.

- Liste alocate secvenţial

Acest tip de alocare este întâlnit când se lucrează cu tablouri (vectori). Avantajul

alocării secvenţiale este dat de faptul că accesul la oricare din nodurile listei este

direct. Dezavantajul constă în faptul că operaţiile de adăugare, eliminare sau

schimbare de poziţie a unui nod necesită un efort mare de calcul.

- Liste alocate înlănţuit

Alocarea înlănţuită poate fi efectuată static (utilizând vectori) sau dinamic. În cazul

alocării dinamice, nodul unei liste este o structură care conţine alături de informaţie

şi adresa nodului următor (pentru liste simplu înlănţuite) sau adresele nodului

următor şi a celui precedent (pentru liste dublu înlănţuite).

Liste înlănţuite

Dacă un nod din listă conţine o singură legătură, cea la nodul următor, spunem că avem o

lista simplu înlănţuită.

Dacă un nod din listă conţine două legături: una la nodul următor şi cealaltă la nodul

precedent spunem că avem o lista dublu înlănţuită.

Liste simplu înlănţuite

Definiţie: O listă simplu înlănţuită este o înşiruire de elemente numite noduri, în care

fiecare nod se păstrează o zonă de informaţie (numită informaţie utilă) şi un pointer către elementul

următor.

O listă simplu înlănţuită se poate reprezenta astfel:

nod 1

primul

nod

ultimul

nod

nod 2 nod 3 nod 4

Info1 adr2 Info2 adr3 Info3 adr4 Info4 null

nod 2

adr1 Info2 adr3

nod 3

adr2 Info3 null

nod 1

null Info1 adr2

nod 1

primul

nod

ultimul

nod

nod 2 nod 3 nod 4

Info1 adr2 Info2 adr3 Info3 adr4 Info4 null

Laborator 1 Tehnici de programare 2015

3

Lector dr. Laura Stoica

Declararea tipului corespunzător de nod într-o listă simplu înlănţuită este:

typedef struct nod

{

tip_inf info;

nod *urm;

}*NOD;

Operaţii care se fac într-o listă:

1. Crearea unui nod într-o listă simplu înlănţuită

Operaţia de creare a listei este dată de funcţia următoare, utilizându-se definirea de mai jos a

nodului listei. Funcţia furnizează adresa nodului prim.

Caz 1: Situaţia în care lista e vidă avem

prim=NULL şi ultim=NULL