循环双向链结表
插入元素
int insert(DList *L, ElemType e) {
Link current = L->head;
Link previous = L->tail;
Link newNode;
int size = getSize(*L);
int position=0;
if (current==NULL) { // Case 1:当循环双向链结表为空时。
newNode = (Link) malloc(sizeof(Node));
newNode->elem = e;
newNode->prev = newNode;
newNode->next = newNode;
L->head = newNode;
L->tail = newNode;
return position;
}
for (position=0; position<size; position++) {
if (current->elem>=e) break;
previous = current;
current = current->next;
}
// Cases 2, 3 & 4: 插入一个节点的 current 之前。
newNode = (Link) malloc(sizeof(Node));
newNode->elem = e;
newNode->prev = previous;
previous->next = newNode;
newNode->next = current;
current->prev = newNode;
if (position==0) L->head = newNode;
else if (position==size) L->tail = newNode;
return position; // 返回位置
删除元素
int delete(DList *L, ElemType e) {
Link current = L->head;
Link previous = L->tail;
int position = 0;
if (current==NULL) return -1;
do 。
if (current->elem==e) {
if (position==0) {
if (current->next==current) {
L->head = NULL;
L->tail = NULL;
}else {
previous->next = current->next;
current->next->prev = previous;
L->head = current->next;
}
free(current);
return position;
}
else {
if (current->next==L->head) // 删除的是尾节点。
L->tail = previous;
previous->next = current->next;
current->next->prev = previous;
free(current);
return position;
}
}
else if (current->elem<e) { // 检查下一个节点。
previous = current;
current = current->next;
position++;
}
else return -1; // 目前节点数据已超过删除的值;删除失败。
} while (current!=L->head);
return -1; // current 回到头节点,删除失败。
}