(3 intermediate revisions by the same user not shown) | |||
Line 11: | Line 11: | ||
typedef Item *ItemPtr; | typedef Item *ItemPtr; | ||
− | Na implementação, consideram-se ainda os seguintes ponteiros. | + | 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 first = NULL, last = NULL; | ||
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; | ||
} | } | ||
Line 69: | Line 69: | ||
int delete(int value) { | int delete(int value) { | ||
ItemPtr px; | ItemPtr px; | ||
− | + | ||
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 && px->value == value) { | if (px && px->value == value) { | ||
px->prev->next = px->next; | px->prev->next = px->next; | ||
Line 80: | Line 80: | ||
return 1; | return 1; | ||
} | } | ||
− | + | ||
return 0; | return 0; | ||
} | } | ||
+ | |||
+ | == Ver Também == | ||
+ | |||
+ | * [[Listas Duplamente Ligadas (genérica)|Lista duplamente ligada para dados genéricos]] |
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; }