(→Estruturas de Suporte) |
(→Inserção de Items na Lista) |
||
Line 47: | Line 47: | ||
int insert(int value) { | int insert(int value) { | ||
ItemPtr px, ni; | ItemPtr px, ni; | ||
− | + | ||
for (px = first->next; | for (px = first->next; | ||
px != last && px->value < value; | px != last && px->value < value; | ||
px = px->next); | px = px->next); | ||
− | + | ||
if (px != last && px->value == value) | if (px != last && px->value == value) | ||
return 0; /* no dups */ | return 0; /* no dups */ | ||
− | + | ||
ni = alloc_item(); | ni = alloc_item(); | ||
ni->value = value; | ni->value = value; | ||
Line 61: | Line 61: | ||
ni->next = px; | ni->next = px; | ||
px->prev = ni; | px->prev = ni; | ||
− | + | ||
return 1; | return 1; | ||
} | } |
Estruturas de suporte a uma lista duplamente ligada.
struct iitem { int value; struct iitem *next; struct iitem *prev; }; typedef struct iitem Item; typedef Item *ItemPtr;
Na implementação, consideram-se ainda os seguintes ponteiros: serão utilizados para referenciar as duas sentinelas utilizadas nos algoritmos que manipulam a lista.
static ItemPtr first = NULL, last = NULL;
static ItemPtr alloc_item() { return (ItemPtr)malloc(sizeof(IntItem)); }
A função init
define duas sentinelas, apontadas por first
e last
.
void init() { first = alloc_item(); last = alloc_item(); first->next = last; last->prev = next; first->prev = last->next = NULL; }
Note-se que a função que destrói a lista não afecta os items.
void destroy() { while (px = first) { first = first->next; free(px); } first = last = NULL; }
int insert(int value) { ItemPtr px, ni; for (px = first->next; px != last && px->value < value; px = px->next); if (px != last && px->value == value) return 0; /* no dups */ ni = alloc_item(); ni->value = value; px->prev->next = ni; ni->prev = px->prev; ni->next = px; px->prev = ni; return 1; }
int delete(int value) { ItemPtr px;
for (px = first->next; px != last && px->value < value; px = px->next);
if (px && px->value == value) { px->prev->next = px->next; px->next->prev = px->prev; free(px); return 1; }
return 0; }