双向循环链表

一、概念

双向循环链表是指每个结点由三部分组成：数据域、直接前驱结点指针、直接后继结点指针，该链表的最后一个结点的直接后继指针指向头结点，头结点的直接前驱指针指向尾节点。

二、图解

结点图示

双向循环链表图示

三、实现源码

常量定义

typedef int ET;

---

双向循环链表定义

typedef struct Node
{ET data;Node* next;Node* prev;
}Node;
typedef Node* BCList;

---

获取一个新节点

Node* CreateNode(ET val){Node* s = (Node*)malloc(sizeof(Node));assert(s != NULL);s->data = val;s->next = s->prev = s;return s;
}

---

初始化一个带头结点的双向循环链表

void BCLinkedListInitial(BCList* phead){*phead = CreateNode(-1);
}

---

头插法

void BCLinkedListAddFromHead(BCList* phead, ET val){assert(phead != NULL);Node* s = CreateNode(val);Node* p = (*phead)->next;s->next = p;s->prev = *phead;(*phead)->next = s;p->prev = s;
}

---

尾插法

void BCLinkedListAddFromBack(BCList* phead, ET val){assert(phead != NULL);Node* s = CreateNode(val);Node* p = (*phead)->prev;(*phead)->prev = s;s->next = *phead;s->prev = p;p->next = s;}

---

显示数据

void BCLinkedListShowData(BCList phead){Node* p = phead->next;while (p != phead){printf("%d ", p->data);p = p->next;}printf("\n");
}

---

判断表是否为空

bool IsEmpty(BCList* phead){if ((*phead)->prev == (*phead)){return true;}return false;
}

---

删除尾部结点

void BCLinkedListDeleteFromBack(BCList* phead){assert(phead != NULL);if (IsEmpty(phead)){printf("表空，无法删除！\n");return;}Node* s = (*phead)->prev;(*phead)->prev = s->prev;s->prev->next = *phead;free(s);
}

---

删除首元结点

void BCLinkedListDeleteFromHead(BCList* phead){assert(phead != NULL);if (IsEmpty(phead)){printf("表空，无法删除！\n");return;}Node* s = (*phead)->next;Node* p = s->next;(*phead)->next = p;p->prev = *phead;free(s);
}

---

获取尾结点

Node* BCLinkedListGetBack(BCList* phead){assert(phead != NULL);if (IsEmpty(phead)){printf("表空，无法获得！\n");return NULL;}return (*phead)->prev;
}

---

获取首元结点

Node* BCLinkedListGetHead(BCList* phead){assert(phead != NULL);if (IsEmpty(phead)){printf("表空，无法获得！\n");return NULL;}return (*phead)->next;
}

---

获取表长度

size_t BCLinkedListGetListLength(BCList* phead){assert(phead != NULL);Node* p = (*phead)->next;size_t len = 0;while (p != (*phead)){p = p->next;len++;}return len;
}

---

清空表中数据

void BCLinkedListClear(BCList* phead){assert(phead != NULL);Node* p = (*phead)->next;Node* q = (*phead)->next;while (q != (*phead)){q = q->next;free(p);p = q;}(*phead)->next = *phead;(*phead)->prev = *phead;
}

---

摧毁表结构

void BCLinkedListDestroy(BCList* phead){assert(phead != NULL);Node* p = (*phead)->next;Node* q = (*phead)->next;(*phead)->next = NULL;while (q != NULL){q = q->next;free(p);p = q;}*phead = NULL;
}

---

按值查找

Node* BCLinkedListFindByValue(BCList* phead, ET key){assert(phead != NULL);Node* p = (*phead)->next;while (p != (*phead) && p->data != key){p = p->next;}if (p == *phead) return NULL;return p;
}

---

按值的大小插入

void BCLinkedListInsertByValue(BCList* phead, ET val){assert(phead != NULL);Node *p = (*phead)->next;while (p != *phead && p->data < val){p = p->next;}if (p == *phead){BCLinkedListAddFromBack(phead, val);}else{Node* s = CreateNode(val);Node* q = p->prev;q->next = s;s->next = p;p->prev = s;s->prev = q;}
}

---

将表中结点按照数据升序链接

void BCLinkedListSortByData(BCList* phead){assert(phead != NULL);Node *p = (*phead)->next->next;Node *q = (*phead)->next->next;(*phead)->prev->next = NULL;(*phead)->next->next = (*phead);(*phead)->prev = (*phead)->next;while (q != NULL){q = q->next;if ((*phead)->next->data > p->data){BCLinkedListAddFromHead(phead, p->data);free(p);}else{Node* temp = (*phead)->next;while (temp->next != (*phead) && temp->data < p->data){temp = temp->next;}if (temp->next == (*phead)){BCLinkedListAddFromBack(phead, p->data);free(p);}else{p->next = temp;p->prev = temp->prev;temp->prev->next = p;temp->prev = p;}}p = q;}
}

---

反转链表

void BCLinkedListReverseList(BCList* phead){assert(phead != NULL);if (IsEmpty(phead))	return;Node* p = (*phead)->prev;Node* q = (*phead)->prev;(*phead)->next->prev = NULL;	//创造循环结束条件 //将头结点置空(*phead)->next = (*phead)->prev = *phead;while (q != NULL){q = q->prev;BCLinkedListAddFromBack(phead, p->data);free(p);p = q;}
}