Crearea și Vizualizarea unei Liste Liniare

Tema1: Scrieţi programul C care realizează crearea şi vizualizarea unei liste liniare implementată prin tipul pointer,dacă inserarea se face în faţa listei.

Tema2: Scrieţi programul C care vă permite efectuarea următoarelor operaţii asupra unei liste liniare simplu înlănţuite:

- creare cu inserare în faţă;

- inserarea unui nod după un nod dat;

- vizualizarea listei liniare;

- căutarea unui nod dat;

Tema3: Scrieţi programul C care vă permite efectuarea următoarelor operaţii asupra unei liste liniare simplu înlănţuite:

- creare cu inserare în spate;

- inserarea unui nod după un nod dat;

- vizualizarea listei liniare;

- căutarea unui nod dat;

Liste implementate prin tipul pointer:

Din punct de vedere matematic, o listă este o secvenţă de zero sau mai multe elemente numite noduri, de un anumit tip numit tip de bază. Aşadar o listă liniară este o colecţie de zero sau mai multe noduri ale căror proprietăţi se reduce în principal la poziţiile relative liniare(unidimensionale) ale acestor noduri.

În loc să păstrăm o listă liniară în locaţii successive de memorie se poate folosi o schemă mult mai flexibilă, în care fiecare nod este legat de următorul nod al listei prin câmpul urm(ător) al listei, unde p este o variabilă pointer care indică primul nod.

Există posibilitatea de a folosi o variabilă de tip nod, în care câmpul urm(ător) indică primul nod efectiv al listei, iar celelalte câmpuri, care ar conţine informaţia propriu-zisă, ar rămâne neasignate. Pointerul p va indica în aceaastă situaţie, acest nod fictive cap de listă. Utilizarea acestui nod de început simplifică în anumite situaţii prelucrarea listelor înlănţuite.

Tema 1: Scrieţi programul C care realizează crearea şi vizualizarea unei liste liniare implementată prin tipul pointer,dacă inserarea se face în faţa listei.

Pentru crearea listei se va crea mai întâi primul nod al listei. Fie p o variabilă pointer(de tip referinţă) care va indica mereu adresa primului nod al listei şi q o variabilă pointer auxiliară tot de tip referinţă.

Să considerăm că avem creat cel puţin primul nod al listei. Pentru adăugarea unui nou nod la începutul listei trebuie să procedăm astfel:

generăm o nouă locaţie de memorie cu aceeaşi structură a cărei adresă o memorăm într-o variabilă de tip pointer q;

pregătim câmpul cheie şi câmpul info al variabilei pointer q;

în câmpul urm al acestui nod trebuie să punem adresa primului nod p;

în final, lui p îi atribuim adresa noului nod care devine acum primul.

Programul C care realizează crearea unei liste liniare simplu înlănţuite prin inserare în faţa listei este următorul:

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

#include <ctype.h>

struct element

{

int cheie;

char info[10];

struct element *urm;

};

typedef struct element Telem;

typedef Telem *ref;

ref p,q,r;

char c;

void ins_p(void)

{

q=(ref)malloc(sizeof(Telem));

printf("inform=");

fflush(stdin);

scanf("%s",&q->info);

printf("cheia=");

scanf("%d",&q->cheie);

q->urm=NULL;

p=q;

}/*ins_p*/

void ins_cf(void)

{

q=(ref)malloc(sizeof(Telem));

printf("inform=");

fflush(stdin);

scanf("%s",&q->info);

printf("cheia=");

scanf("%d",&q->cheie);

q->urm=p;

p=q;

}/*ins_cf*/

void creare(void)

{

char c;

ins_p();

printf("Adaugi element?(D/N) : ");

fflush(stdin);

scanf("%c",&c);

c=toupper(c);

while (c=='D')

{

ins_cf();

printf("Mai adaugi?(D/N) : ");

fflush(stdin);

scanf("%c",&c);

c=toupper(c);

}

}/*creare*/

void listare(void)

{

r=p;

while(r!=NULL)

{

printf("cheia=%dninfo=%snn",r->cheie,r->info);

r=r->urm;

}

}/*listare*/

void main()

{

char op;

do

{

clrscr();

printf("Operatii asupra listelor liniare simplu inlantuitenn");

printf("C - Crearen”);

printf(“L - Listaren”);

printf(“E - Iesirenn");

printf("Introdu optiunea : ");

fflush(stdin);

scanf("%c",&op);op=toupper(op);

switch (op)

{

case 'C':creare(); break;

case 'L':listare(); break;

case 'E':break;

default : printf("Ai introdus o optiune eronata!n");

} /*switch*/

printf("Tastati ENTERn");

getch();

}

while(op!='E');

Laborator 4