Implementarea tipului de date abstract - lista simplu înlănțuită în C

Lucrare de laborator Nr.2 si 3

Tema: Implementarea tipului de date abstract “Lista simplu inlantuita” in C

Scopul lucrarii: obtinerea deprinderilor practice de implementare a unui tip de date abstract (TDA) in limbajul C si anume a TDA “Lista simplu inlantuita”

Sarcina de lucru: De scris trei fisiere in limbajul C pentru implementarea (2 fisiere) si utilizarea (1 fisier – program cu functia main ) a TDA “Lista simplu inlantuita”:

1. Fișierul antet cu extensia .h care descrie structura de date a elementului listei simplu inlantuite (conform variantei din lucrare precedenta) și prototipurile funcțiilor care asigură operațiunile de prelucrare a listei simplu inlantuite.

2. Fișier cu extensia .cpp (sau .c) care contine codurile (implementarile) tuturor functiilor declarate în fișierul antet.

3. Fișierul utilizatorului - programul cu funcția main () pentru prelucrarea listei simplu inlantuite cu afisarea meniului de optiuni pe ecran, si anume: crearea listei simplu inlantuite in memoria dinamica, introducerea informatiei despre elementele listei de la tastatura, afisarea informatiei despre elementele listei pe ecran, cautarea elementului listei dupa unui cimp informational, modificarea cimpurilor elementului listei, interschimbarea a 2 elemente listei, determinarea lungimei listei, sortarea elementelor listei dupa unui cimp, eliberarea memoriei dinamice alocate pntru lista (lucrare de laborator 2), adaugarea unui element nou la sfirsitul listei, inserarea unui element nou in lista dupa elementul indicat, inserarea unui element nou in lista inainte elementul indicat, stergerea unui element al listei, divizarea listei simplu inlantuite in doua liste separate, unirea a 2 liste simlu inlantuite separate intr-o singura lista, scrierea informatiei despre elementele listei in fisier, citirea informatiei despre elementele listei dintr-un fișier, ieșire din program (lucrari de laborator 2 si 3).

Descrierea scurta a teoriei care se refera la tema lucrarii de laborator si metode folosite.

Structura de date listă

În cadrul structurilor avansate de date, structura listă ocupă un loc important.O listă, este o structură dinamică, care se defineşte pornind de la noţiunea de vector. Elementele unei liste sunt toate de acelaşi tip şi sunt înregistrate în memoria centrală a sistemului de calcul.Spre deosebire de structura statică tablou la care se impune ca numărul componentelor să fie constant, în cazul listelor acest număr poate fi variabil, chiar nul. Listele sunt structuri flexibi le particulare, care funcţie de necesităţi pot creşte sau descreşte şi ale căror elemente pot fi referite, inserate sau şterse în orice poziţie din cadrul listei. Două sau mai multe liste pot fi concatenate sau scindate în subliste.În practica programării listele apar în mod obişnuit în aplicaţii referitoare la regăsirea informaţiei, implementarea translatoarelor de programe, simulare etc.

TDA Listă

Din punct de vedere matematic, o listă este o secvenţă de zero sau mai multe elemente numite noduri aparţinând unui anumit tip numit tip de bază, care se reprezintă de regulă astfel : a1, a2,...,an Unde n ≥ 0 şi fiecare ai aparţine tipului de bază.

Numărul n al nodurilor se numeşte lungimea l istei. Presupunând că n ≥ 1, se spune că a1 est e primul nod al listei iar an est e ultimul nod.Dacă n = 0 avem de-a face cu o listă vidă.O proprietate importantă a unei liste este aceea că nodurile sale pot fi ordonate liniar funcţie de poziţia lor în cadrul listei.Se spune că ai precede pe ai+1 pentru i=1,2,...,n-1 şi că ai succede (urmează) lui ai-1 pentru i=2,3,4, ...,n. De regulă se spune că nodul ai se află pe poziţia i. Este de asemenea convenabil să se postuleze existenţa poziţiei următoare ultimului element al listei.În această idee se introduce funcţia FIN(L):TipPozitie care returnează poziţia următoare poziţiei n în l ista L având n elemente. Se observă că FIN(L) are o distanţă variabilă faţă de începutul listei, funcţie de faptul că lista creşte sau se reduce, în timp ce alte poziţii au o distanţă fixă faţă de începutul listei. Pentru a defini un tip de date abstract, în cazul de faţă TDA Listă. Pe lângă definirea din punct de vedere matematic a modelului asociat(mai sus precizată). Este necesar să se definească şi un set de operatori aplicabili obiectelor de tip l istă. Din păcate, pe de o parte este relativ greu de definit un set de operatori valabil în toate aplicaţiile, iar pe de altă parte natura setului depinde esenţial de maniera de implementare a listelor. În continuare se prezintă două seturi reprezentative de operatori care acţionează asupra listelor, unul restrâns şi altul extins.

Textul programului in limbajul „C”

head 2-3_6.h

typedef struct automobil

{

char den[40]; //denumirea automobilului

char model[40];//marca automobilului

char cul[40]; //Culoarea automobilului

int an; //Anul fabricarii

char cv[40]; //Cutie de viteze

float cc; //Capacitate cilindrica

struct automobil *next;

}automobil;

automobil *head;

int creat(int n);

void read();

void show(automobil *head_2);

int search(int s);

void modif(int m);

int lenght();

void swap(automobil *a,automobil *b);

void sort();

void freemem();

void add_after_id(int id);

void add_before_id(int id);

void add_to_end();

void del_auto(int id);

void divide(int l,automobil **head_2);

void join(automobil **head_2);

void save(char *fname);

void read_file(char *fname);

fun 2-3_6.cpp

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "Head 2-3_6.h"

//Functia de alocare dinamica a memoriei

int creat(int n){

int i;

automobil *c,*p;

for(i=0;i<n;i++){

c=(automobil*)malloc(sizeof(automobil));

if(c == NULL) return 0;

if(i == 0){

head=c;

p=c;

} else {

p->next=c;

p=c;

} }

p->next=NULL;

return 1.