Liste

3.1.1 Operatii fundamentale

/* Declaratii */

typedef int INFO; typedef int NODEPTR, LISTA, POZITIE, BOOL; typedef struct nod { INFO info; NODEPTR urm; } NOD; #ifndef GLOBAL

extern NOD *cursor_space;

#else

NOD *cursor_space;

#endif

void error(const char *s);

void init_cursor_space(int dim);

POZITIE cursor_alloc(void);

void cursor_free(const POZITIE p);

LISTA create_empty_list(INFO header);

LISTA create_list(INFO header);

BOOL is_empty(const LISTA l);

BOOL is_last(const POZITIE p);

POZITIE find(INFO x, LISTA l);

POZITIE find_pred(INFO x, LISTA l);

void insert_after(INFO x, POZITIE p);

void delete(INFO x, LISTA l);

void add_beg(INFO x, LISTA l);

void print_list(LISTA l);

Figura L1 Listst.h

/* Implementare */

#include <stdio.h> #include <alloc.h> #include <string.h> #include <stdlib.h> #include "listst.h" void error(const char *s) { fprintf(stderr, "n%sn", s); exit(1); } void init_cursor_space(int dim)

{ int i;

if((cursor_space=(NOD *)malloc(dim*sizeof(struct nod)))==NULL)

error("init_cursor_space: eroare malloc");

for(i=0; i<dim-1; i++)

cursor_space[i].urm=i+1;

cursor_space[dim-1].urm=0;

}

POZITIE cursor_alloc(void)

{ POZITIE p;

p=cursor_space[0].urm;

cursor_space[0].urm=cursor_space[p].urm;

return p;

}

void cursor_free(const POZITIE p)

{

cursor_space[p].urm=cursor_space[0].urm;

cursor_space[0].urm=p;

}

BOOL is_empty(const LISTA l)

{

return (cursor_space[l].urm==0);

}

BOOL is_last(const POZITIE p)

{

return (cursor_space[p].urm==0);

}

POZITIE find(INFO x, LISTA l)

{ POZITIE p;

p=cursor_space[l].urm;

while((p!=0) && (cursor_space[p].info!=x))

p=cursor_space[p].urm;

return p;

}

POZITIE find_pred(INFO x, LISTA l)

{ POZITIE p;

p=l;

l=cursor_space[l].urm;

while((cursor_space[p].urm!=0) && (cursor_space[l].info!=x)) {

p=l;

l=cursor_space[l].urm;

}

return p;

}

void insert_after(INFO x, POZITIE p)

{ NODEPTR nou=cursor_alloc();

if(nou==0) error("insert_after: eroare cursor_alloc");

else {

cursor_space[nou].info=x;

cursor_space[nou].urm=cursor_space[p].urm;

cursor_space[p].urm=nou;

}

}

void delete(INFO x, LISTA l)

{ POZITIE p, nou;

if(cursor_space[p=find_pred(x,l)].urm!=0){

nou=cursor_space[p].urm;

cursor_space[p].urm=cursor_space[nou].urm;

cursor_free(nou);

}

}

void del_list(LISTA l)

{ POZITIE p;

while(l!=0) {

p=cursor_space[l].urm;

cursor_free(l);

l=p;

}

}

void add_beg(INFO x, LISTA l)

{ POZITIE nou=cursor_alloc();

if(nou==0) error("add_beg: eroare in cursor_alloc");

cursor_space[nou].info=x;

cursor_space[nou].urm=cursor_space[l].urm;

cursor_space[l].urm=nou;

}

void print_list(LISTA l)

{

printf("nLISTA %d n",cursor_space[l].info);

l=cursor_space[l].urm;

while(l!=0){

printf("%3d --> ",cursor_space[l].info);

l=cursor_space[l].urm;

}

printf("NULLnn");

}

LISTA create_empty_list(INFO header)

{ POZITIE l=cursor_alloc();

if(l==0) error("create_empty_list: eroare cursor_alloc");

cursor_space[l].info=header;

cursor_space[l].urm=0;

return l;

}

LISTA create_list(INFO header)

{ POZITIE l;

INFO val;

int k;

char s[30];

l=create_empty_list(header);

printf("Introduceti elementele listei %2dn",header);

while(1) {

do {

printf("Element: "); gets(s);

if(strlen(s)==0) {return l;}

if((k=sscanf(s,"%d",&val))!=1) printf("Reintroduceti ultima valoare: ");

} while(k!=1);

add_beg(val, l);

}

}