Pentru crearea listei se va crea mai intâi un prim nod al listei. Fie p o variabilă pointer care va indica mereu adresa primului nod al listei şi q o variabilă pointer auxiliară tot de tipul referinţă. Pentru realizarea acestui program avem nevoie de următoarele funcţii:
-funcţia creare() care realizează crearea listei apelând funcţia ins_cf() unde inserarea se face în faţa listei în modul următor: se generează o nouă locaţie de memorie cu structura definită la început, se pregătesc câmpurile cheie şi info, în câmpul urm a acestui nod se pune adresa primului nod, iar variabila pointer p va conţine adresa noului nod care devine primul nod.
-funcţia inserare după un nod dat ins_d() care insereaza nodul s după nodul r. În primul rând se generează o nouă locaţie de memorie pentru nodul s, apoi se pregătesc campurile cheie şi info ale acestuia, în s->urm se pune r->urm, iar în final în r->urm se pune s.
-funcţia inserare inaintea unui nod dat ins_i() care insereaza nodul s înaintea nodului r. În primul rând se generează o nouă locaţie de memorie pentru nodul s, se copiază nodul *r peste nodul *s şi apoi se introduc câmpurile cheie şi info care definesc noul nod în câmpurile corespunzătoare ale vechiului nod *r.
-funcţia de căutare cautare(int k) care caută în listă nodul cu cheia k. În această funcţie se parcurge lista, iar în cazul în care cheia căutată se află în listă funcţia returnează 1, în caz contrar returnează 0.
-funcţia suprimare după un nod dat suprima_d(). Se dă un nod printr-o variabilă pointer r, se cere suprimarea nodului de după nodul *r.Suprimarea se face cu uşurinţă modificând câmpul urm al nodului *r astfel încât să indice succesorul succesorului său. Acest lucru se realizează mai simplu dacă în s memorăm succesorul lui r(s=r->urm) iar în r->urm memorăm s->urm. Dacă în cele ce urmează nu mai avem nevoie de informaţia din locaţia succesorului nodului *r atunci putem pune la dispoziţia sistemului locaţia succesorului prin apelul funcţiei free(s).Dacă *r este ultimul nod al listei liniare atunci nu există nodul *s şi în acest caz nu avem ce suprima.
-funcţia de suprimare a unui nod dat suprima_n().Fie r variabila pointer care desemnează adresa nodului care trebuie suprimat. Dacă nodul care trebuie suprimat nu e ultimul atunci fie s variabila pointer care desemnează succesorul lui r(s=r->urm) se copiază succesorul peste nodul *r(*r=*s) şi se eliberează zona ocupată de s (free(s)). Dacă nodul de suprimat este ultimul dar nu e primul luăm o variabilă s care parcurge lista de la început şi până când s indică nodul care are ca successor pe r şi punem în s->urm NULL iar apoi eliberăm zona r. Dacă *r este ultimul şi primul se eliberează pur şi simplu zona r prin apelarea lui free(r).
-funcţia de listare (listare()) care parcurge lista de la început şi până la sfârşit şi afişează câmpurile cheie şi info ale fiecărui nod.
Programul C care efectuează toate aceste operaţii asupra unei liste liniare simplu înlănţuite cu inserare în faţă este:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
#include<ctype.h>
struct nod
{
int cheie;
char info[10];
struct nod *urm;
};
typedef struct nod Tnod;
typedef Tnod *ref;
ref p,q,r,s;
void ins_cf(void)
{
q=malloc(sizeof(Tnod));
printf("Cheia=");scanf("%d",&q->cheie);
printf("Info=");
scanf("%s",q->info);
fflush(stdin);
q->urm=p;
p=q;
}/*inc_cf*/
void ins_i(void)
{
ref s;
s=malloc(sizeof(Tnod));
*s=*r;
r->urm=s;
printf("Cheia=");scanf("%d",&s->cheie);
printf("Info=");
fflush(stdin);
scanf("%s",s->info);
}/*ins_i*/
void ins_d(void)
{
s=malloc(sizeof(Tnod));
printf("Cheia=");scanf("%d",&s->cheie);
printf("Info=");
fflush(stdin);
scanf("%s",s->info);
s->urm=r->urm;
r->urm=s;
}/*ins_d*/
void creare(void)
{
char opt;
p=NULL;
clrscr();
do
{
ins_cf();
printf("Introduceti elem?dn");
fflush(stdin);
scanf("%c",&opt);
opt=toupper(opt);
}
while(opt=='D');
}/*creare*/
int cautare(int k)
{
int b=0;
r=p;
while ((b==0)&&(r!=NULL))
if ((r->cheie)==k)
b=1;
else r=r->urm;
Laborator nr 5
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
