//strutture e operatori di supporto per manipolare il grafo
typedef int tipoelem;
//definizione del tipo di dato lista
typedef struct cella * lista;
typedef struct cella * posizione;
struct cella{
posizione successivo;
tipoelem val;
posizione precedente;
};
//operatori sulle liste
lista CREALISTA(){
lista l;
l = malloc(sizeof(struct cella));
l->successivo = l;
l->precedente = l;
return l;
}
int LISTAVUOTA(lista L){
return (((L->successivo == L && L->precedente ==L)) ? 1 : 0);
}
posizione PRIMOLISTA(lista L){
return L->successivo;
}
posizione SUCCLISTA(posizione P){
return P->successivo;
}
int FINELISTA(posizione P,lista L){
return ((P == L) ? 1 : 0);
}
tipoelem LEGGILISTA(posizione P){
return P->val;
}
void INLISTA(tipoelem el,posizione *p){
posizione tmp;
tmp = malloc(sizeof(struct cella));
tmp->val = el;
tmp->precedente = (*p)->precedente;
tmp->successivo = *p;
((*p)->precedente)->successivo = tmp;
(*p)->precedente = tmp;
*p = tmp;
}
void CANCLISTA(posizione *p){
posizione tmp;
tmp = *p;
((*p)->precedente)->successivo = (*p)->successivo;
((*p)->successivo)->precedente = (*p)->precedente;
*p = (*p)->successivo;
free(tmp);
}
int APPARTLISTA(tipoelem el,lista L){
int rt = 0;
if(!LISTAVUOTA(L)){
posizione pos = PRIMOLISTA(L);
while(!FINELISTA(pos,L) && rt == 0){
if(LEGGILISTA(pos) == el){rt = 1;}
pos = SUCCLISTA(pos);
}
}
return rt;
}
lista REVERSELISTA(lista L){
lista lr = CREALISTA();
posizione p = PRIMOLISTA(L);
posizione pr = PRIMOLISTA(lr);
while (!FINELISTA(p,L)){
INLISTA(LEGGILISTA(p),&pr);
p = SUCCLISTA(p);
pr = PRIMOLISTA(lr);
}
return lr;
}
//tipo di dato coda implementato tramite liste
typedef lista coda;
coda CREACODA(){
lista L = CREALISTA();
return L;
}
int CODAVUOTA(coda Q){
return LISTAVUOTA(Q);
}
void DISTRUGGICODA(coda Q){
posizione tmp;
posizione pos = PRIMOLISTA(Q);
while(!FINELISTA(pos, Q)){
tmp = pos;
pos = SUCCLISTA(pos);
CANCLISTA(&tmp);
}
}
void FUORICODA(coda Q){
posizione pos = PRIMOLISTA(Q);
CANCLISTA(&pos);
}
tipoelem LEGGICODA(coda Q){
tipoelem el;
posizione pos = PRIMOLISTA(Q);
el = pos->val;
return el;
}
void INCODA(tipoelem el,coda Q){
posizione pos = PRIMOLISTA(Q);
while(!FINELISTA(pos, Q)){
pos = SUCCLISTA(pos);
}
INLISTA(el, &pos);
}
coda REVERSECODA(coda Q){
coda P = CREACODA();
posizione pos = PRIMOLISTA(Q);
while(!FINELISTA(pos, Q)){
INCODA(pos->val, P);
CANCLISTA(&pos);
}
P = REVERSELISTA(P);
return P;
}
int APPARTCODA(tipoelem el,coda P){
int flag = 0;
coda Q = CREACODA();
while(!CODAVUOTA(P)){
if(el == LEGGICODA(P)){
flag = 1;
}
INCODA(LEGGICODA(P), Q);
FUORICODA(P);
}
while(!CODAVUOTA(Q)){
INCODA(LEGGICODA(Q), P);
FUORICODA(Q);
}
DISTRUGGICODA(Q);
return flag;
}
