Tipuri de date abstracte. Lista


Listele sunt siruri de elemente care pot fi parcurse secvential. Inserarea sau stergerea unui element pot fi facut in orice pozitie din lista. Listele pot fi implementate cu tablouri sau cu pointeri, cu avantaje si dezavantaje pentru fiecare din cazuri.

Cateva apecte ale unei probleme pot motiva folosirea implementarii cu pointeri listelor pentru rezolvare.

Operatii pentru tipul abstract lista

init(lista) creeaza o lista vida
empty(lista):boolean verifica daca lista este vida
first(lista) : pozitie returneaza prima pozitie din lista
next(pozitie) : pozitie returneaza urmatoarea pozitie, din aceeasi lista
lookup(lista, element): pozitie cauta un element in lista
insertfirst(lista, element) insereaza un element la inceputul listei
insertafter(pozitie, element) insereaza un element dupa pozitia specificata
delete(lista, pozitie) sterge elementul de la pozitia corespunzatoare din lista

Definirea tipurilor de date pentru implementare cu pointeri a listelor 

	/* definirea tipului pentru informatia corespunzatoarea fiecarui nod al listei */	
	typedef int element;	 
	
	/* fiecare nod al listei pastreaza anumite informatii (element)+ adresa urmatorului nod al listei (struct n*) */
	typedef struct n {
		element e;
		struct n* next;
	} node;		
		
	typedef node *list;

Problema rezolvata

Problema 1

Intr-un fisier sunt pastrate numele unor orase, in ordinea in care au fost ele parcurse de un grup de ciclisti.
  • Creati o lista care pastreaza numele acestor localitati.
  • Creati o lista care sa permita afisarea traseului parcurs (pastreaza ordinea in care au fost vizitate localitatile)
  • Verificati daca un oras al carui nume se citeste de la tastatura a fost vizitat sau nu de ciclisti.

OBSERVATII: Numele fisierului de intrare se da in linia de comanda. Se va implementa lista folosind pointeri.

Problema 2

Intr-un fisier sunt pastrate numele unor noduri feroviare si ale punctelor finale ale rutelor ce pornesc din acel punct. Fisierul contine pe fiecare linie numele unui nod feroviar, urmat de ":", apoi numele localitatilor finale pentru fiecare ruta existenta din acel punct, separate prin spatii. 
   
   Ex:
	Timisoara:Arad Jimbolia Buzias Resita Lugoj 
	Arad:Oradea Deva 
	Lugoj:Ilia Caransebes  
	Deva:Cluj Alba Petrosani
  • Creati o lista care sa pastreze doar numele nodurilor feroviare. Afisati-o.
  • Verificati daca un oras, al carui nume se citeste de la tastatura, este sau nu nod feroviar.
  • Creati o lista care pastreaza toate orasele extremitati ale rutelor feroviare existente.
  • Verificati daca intre doua orase exista legaturi directe. Numele oraselor se citeste de la tastatura.
  • Verificati daca intre doua orase exista legaturi feroviare.

OBSERVATII:
Numele fisierului de intrare se da in linia de comanda.
Se considera ca numele localitatilor nu contin spatii.
Listele se vor implementa cu pointeri.

RECOMANDARE: rezolvati problema in mai multi pasi.
  • Verificati intai daca numarul de argumente date in linia de comanda este corect. Daca nu, tipariti un mesaj si terminati executia programului.
  • Verificati daca deschiderea fisierului s-a realizat cu succes. Daca nu, terminati executia programului dupa ce tipariti un mesaj de eroare corespunzator. Compilati si rulati programul.
  • Parcurgeti fisierul linie cu linie. Pentru fiecare linie selectati informatiile utile pentru rezolvarea unei cerinte. Verificati prin afisare pe ecran ca citirea este corecta.
  • Definiti tipurile necesare pentru implemtarea cu pointeri a listelor.
  • Realizati functiile de care aveti nevoie pentru rezolvarea cerintelor. (crearea listei vide, inserarea unui element, tiparirea listei, etc.)

Exercitii

1. Descrieti tipul de date stiva/ coada/ lista.
2. Pentru implementarea cu tablou/pointeri a stivei, realizati operatia de extragere/inserare a unui element din/in stiva.
3. Pentru implementarea cu tablou/pointeri a cozii, realizati operatia de inserare/extragere a unui element in/din coada.
4. Pentru implementarea cu pointeri a listei simplu/dublu inlantuite, realizati operatia de inserare a unui element in lista la inceput/ dupa un element dat.
5. Pentru implementarea cu pointeri a listei simplu/dublu inlantuite, realizati operatia de stergere a unui element.

OBSERVATIE: pentru implementarile de mai sus se cere si definirea tipurile de date folosite, explicatii.