lista circular

Prévia do material em texto

#include <stdio.h>
#include <malloc.h>
#define false 0
#define true 1
typedef int bool;
typedef int KEY;
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT cabeca;
} LISTA;
void initialize(LISTA *l){
l->cabeca = (PONT) malloc(sizeof(ELEMENTO));
l->cabeca->prox = l->cabeca;
}
int count(LISTA *l){
PONT fim = l->cabeca->prox;
int tamanho = 0;
while(fim != l->cabeca) {
tamanho++;
fim = fim->prox;
}
return tamanho;
}
int print(LISTA *l){
PONT fim = l->cabeca->prox;
printf("Lista: ");
while(fim != l->cabeca) {
printf("%i ", fim->reg.chave);
fim = fim->prox;
}
printf("\n");
}
PONT buscaSentinela(LISTA *l, KEY chave) {
PONT pos = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while(pos->reg.chave != chave) pos = pos->prox;
if(pos != l->cabeca) return pos;
return NULL;
}
PONT buscaSentinelaOrd(LISTA *l, KEY chave) {
PONT pos = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while(pos->reg.chave < chave) pos = pos->prox;
if(pos != l->cabeca && pos->reg.chave==chave) return pos;
return NULL;
}
PONT buscaAtualAnt(LISTA *l, KEY chave, PONT *ant){
*ant = l->cabeca;
PONT atual = l->cabeca->prox;
l->cabeca->reg.chave = chave;
while (atual->reg.chave < chave) {
*ant = atual;
atual = atual->prox;
}
if (atual!=l->cabeca && atual->reg.chave==chave) return atual;
return NULL;
}
bool addEmOrdem(LISTA *l, REGISTRO reg) {
PONT ant, i;
i = buscaAtualAnt(l, reg.chave, &ant);
if(i!=NULL) return false;//já existe na lista
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
i->prox = ant->prox;
ant->prox = i;
return true;
}
bool excluir(LISTA *l, KEY chave) {
PONT ant, i;
i = buscaAtualAnt(l, chave, &ant);
if(i == NULL) return false;
ant->prox = i->prox;
free(i);
return true;
}
void reinicializar(LISTA *l) {
PONT fim = l->cabeca->prox;
while(fim != l->cabeca) {
PONT apagar = fim;
fim = fim->prox;
free(apagar);
}
l->cabeca->prox = l->cabeca;
}
void main(){
LISTA lista;
initialize(&lista);
REGISTRO r1,r2,r3,r4,r5;
r1.chave = 1;
r2.chave = 2;
r3.chave = 3;
r4.chave = 4;
r5.chave = 5;
addEmOrdem(&lista,r5);
addEmOrdem(&lista,r4);
addEmOrdem(&lista,r3);
addEmOrdem(&lista,r2);
addEmOrdem(&lista,r1);
print(&lista);
excluir(&lista, r3.chave);
excluir(&lista, r1.chave);
excluir(&lista, r5.chave);
print(&lista);
reinicializar(&lista);
print(&lista);
addEmOrdem(&lista,r5);
print(&lista);
}