数据结构-线性表-具有独立头节点的双向循环链表

完整代码：

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6013)#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<time.h>// 一个具有独立头节点的双向循环链表，
// 区别在于将头节点和数据区域分开；
// 而且有独立头节点的链表为空的条件是：L->next等于L->prior等于NULL；
// 没有独立头节点的链表未空的条件是：L->next等于L->prior等于L；
// 还有一点要注意的是如何让p=L，指针转一圈之后不会回到L；typedef int ElemType;
typedef int Status;typedef struct Node {ElemType data;struct Node* next;	//直接后继指针struct Node* prior;	//直接前驱指针
}Node;
typedef Node* DuLinkList;// 函数声明
Status ListCreate(DuLinkList* L);
Status LinkEmpty(DuLinkList L);
Status ClearList(DuLinkList L);
Status GetElem(DuLinkList L, int i, ElemType* e);
Status LocateElem(DuLinkList L, ElemType e);
Status ListInsert(DuLinkList L, int i, ElemType e);
Status ListDelete(DuLinkList L, int i, ElemType* e);
void printAll(DuLinkList L);
void randList(DuLinkList L, int i);
Status insertHead(DuLinkList L, ElemType e);
Status insertEnd(DuLinkList L, ElemType e);
Status deleteEnd(DuLinkList L);
void ListReverse(DuLinkList L);
void test(DuLinkList L);/// <summary>
/// 创建一个空的链表，并创建头节点
/// </summary>
Status ListCreate(DuLinkList* L) {	//传递的是指针，要用指针接收*L = (DuLinkList)malloc(sizeof(Node));if (!L) {printf("创建失败!\n");return 0;}(*L)->data = 0;(*L)->next = NULL;(*L)->prior = NULL;printf("创建成功!\n");return 1;
}/// <summary>
/// 判断链表是否为空
/// </summary>
Status LinkEmpty(DuLinkList L) {int flag;flag = (L->next == NULL) ? 0 : 1;return flag;
}/// <summary>
/// 将链表清空。
/// </summary>
Status ClearList(DuLinkList L) {DuLinkList p;p = L->next;int j = 1;while (1) {if (p == L->prior) {free(p);break;}p = p->next;free(p->prior);}L->next = NULL;L->prior = NULL;L->data = 0;return 1;
}/// <summary>
/// 将链表L中的第i个位置元素值返回给e。
/// </summary>
Status GetElem(DuLinkList L, int i, ElemType* e) {DuLinkList p;p = L->next;int j = 1;while (j < i) {if (p == L->prior && j != 1 || p == NULL) { return 0; } //指针转了一圈，没找到第i个元素；p = p->next;j++;}if (j > i || p == NULL) { return 0; }*e = p->data;return 1;
}/// <summary>
/// 在链表L中查找与给定值e相等的元素，
/// 如果查找成功，返回该元素在表中序号表示成功；
/// 否则，返回0表示失败。
/// </summary>
Status LocateElem(DuLinkList L, ElemType e) {DuLinkList p;p = L->next;int i;i = 1;while (p) {if (p->data == e) { return i; }if (p == L->prior) { break; }p = p->next;i++;}return 0;
}/// <summary>
/// 在链表L中的第i个位置插入新元素e。
/// </summary>
Status ListInsert(DuLinkList L, int i, ElemType e) {DuLinkList p, s;p = L->next;s = NULL;int j = 1;if (i < 1) {printf("第%d个元素不存在。\n", i);return 0;}while (j < i) {if (p == L->next && j != 1) {printf("第%d个元素不存在。\n", i);return 0;}p = p->next;j++;}s = (DuLinkList)malloc(sizeof(Node));if (!s) {printf("内存申请失败！\n");}s->data = e;// 考虑极端情况if (L->next == NULL) {	//链表中没有数据元素；s->next = s;s->prior = s;L->next = s;L->prior = s;}else {	// 链表中有数据元素；s->next = p;s->prior = p->prior;p->prior->next = s;p->prior = s;if (i == 1) { //插入的位置是首元结点；L->next = s;}else if (i == L->data + 1) { //插入的位置是尾节点；L->prior = s;}}L->data++;return 1;
}/// <summary>
/// 删除链表L中第i个位置元素，并用e返回其值。
/// </summary>
Status ListDelete(DuLinkList L, int i, ElemType* e) {DuLinkList p;p = L->next;int j = 1;if (i < 1 || i>L->data) {printf("第%d个元素不存在。\n", i);return 0;}while (j < i) {p = p->next;j++;}*e = p->data;if (L->next == L->prior) {	// 链表中只有一个元素L->next = NULL;L->prior = NULL;}else if (L->next == p) {	// 删除第一个元素L->next = p->next;}else if (L->prior == p) {	// 删除最后一个元素L->prior = p->prior;}// 正常情况p->next->prior = p->prior;p->prior->next = p->next;free(p);L->data--;return 1;
}/// <summary>
/// 输出链表中所有元素。
/// </summary>
void printAll(DuLinkList L) {DuLinkList p;p = L->next;int i = 0;while (p) {printf("%d\t", p->data);if (p == L->prior)break;p = p->next;}printf("\n");
}/// <summary>
/// 向链表中添加i个随机元素。
/// </summary>
void randList(DuLinkList L, int i) {int min = 0;int max = 1000;int range = max - min + 1;for (int j = 0; j < i; j++) {ElemType e = min + rand() % range;insertEnd(L, e);}printf("\n");
}
/// <summary>
/// 在链表头部插入一个元素（头插法）
/// </summary>
Status insertHead(DuLinkList L, ElemType e) {DuLinkList p, s;p = L->next;s = (DuLinkList)malloc(sizeof(Node));if (s == NULL) {return 0;}s->data = e;L->next = s;if (!p) {    //链表中没有一个元素L->prior = s;s->next = s;s->prior = s;}else {    //链表中又元素s->next = p;s->prior = L->prior;L->prior->next = s;p->prior = s;}L->data++;return 1;
}/// <summary>
/// 在链表末尾插入一个元素（尾插法）
/// </summary>
Status insertEnd(DuLinkList L, ElemType e) {DuLinkList p, s;p = L->prior;s = (DuLinkList)malloc(sizeof(Node));if (!s) {return 0;}s->data = e;L->prior = s;if (!p) {    //链表中没有一个元素L->next = s;s->next = s;s->prior = s;}else {    //链表中有元素s->prior = p;s->next = L->next;L->next->prior = s;p->next = s;}L->data++;return 1;
}/// <summary>
/// 在链表末尾删除一个元素
/// </summary>
Status deleteEnd(DuLinkList L) {DuLinkList p;p = L->prior;if (!p) {    //链表中没有一个元素return 0;}if (L->prior == L->next) {   //链表中的元素只有一个L->prior = NULL;L->next = NULL;}else {                   //链表中的元素大于一个L->prior = p->prior;L->prior->next = L->next;L->next->prior = L->prior;}L->data--;free(p);return 1;
}/// <summary>
/// 将所有元素反转（交换每一个结点的next和prior指针）\
/// （还有一种实现方法是：创建一个新的头结点，将原链表的的结点根据一定顺序插进去）
/// </summary>
void ListReverse(DuLinkList L) {DuLinkList p, agent;p = L->next;agent = NULL;while (p) {agent = p->next;p->next = p->prior;p->prior = agent;if (p == L->prior) {break;}p = agent;}agent = L->next;L->next = L->prior;L->prior = agent;
}// 另一种实现方式
void Reverse(DuLinkList L) {DuLinkList p, s;p = L->next;s = NULL;ListCreate(&s);if (!s) {return;}while (p) {insertHead(s, p->data);if (p == L->prior) {break;}p = p->next;}//printf("%p\n", &L);//printf("%p\n", L);ClearList(L);*L = *s;//printf("%p\n", L);//test(L);//printf("---------\n");//test(s);free(s);
}/// <summary>
/// 获得链表长度（同ListEmpty）
/// </summary>
int ListLight(DuLinkList L) {return L->data;
}void menu() {printf("=============================菜单-双向循环链表===================================\n");printf("(1) 显示菜单\t\t\t\t(2) 判空\t\t\t\t|\n");printf("(3) 清空链表\t\t\t\t(4) 按位删除\t\t\t\t|\n");printf("(5) 按位查找\t\t\t\t(6) 按值查找\t\t\t\t|\n");printf("(7) 按位插入\t\t\t\t(8) 元素个数\t\t\t\t|\n");printf("(9) 输出链表\t\t\t\t(10) 随机生成\t\t\t\t|\n");printf("(11) 头插入\t\t\t\t(12) 尾插入\t\t\t\t|\n");printf("(13) 尾删除\t\t\t\t(14) 反转链表\t\t\t\t|\n");printf("(0) 结束程序\t\t\t\t\t\t\t\t\t|\n");printf("=================================================================================\n");
}void test(DuLinkList L) {int i = 1;printf("[0] data: %d\tself: %p   next: %p    prior: %p\n", L->data, L, L->next, L->prior);DuLinkList p;p = L->next;while (p) {printf("[%d] data: %d\tself: %p   next: %p    prior: %p\n", i++, p->data, p, p->next, p->prior);if (p == L->prior) { break; }p = p->next;}
}// 简化后的main函数
int main() {DuLinkList L = NULL;ListCreate(&L);int choice;ElemType e, * p_e = (ElemType*)malloc(sizeof(ElemType));int i;menu();while (1) {printf("请输入菜单序号：");scanf("%d", &choice);switch (choice) {case 999:test(L);break;case 0:free(L);printf("链表已经销毁。\n");return 0;case 1:menu();break;case 2:if (LinkEmpty(L)) {printf("非空。\n");}else {printf("空\n");}break;case 3:ClearList(L);printf("Ok\n");break;case 4:printf("要删除的位置是：");scanf("%d", &i);if (ListDelete(L, i, p_e)) {printf("Success：删除第%d个位置上的元素 %d\n", i, *p_e);}else {printf("Error：检查输入是否正确。\n");}break;case 5:printf("要查找的位置为：（下标从1开始）");scanf("%d", &i);if (GetElem(L, i, p_e)) {printf("Success：第%d个元素为：%d\n", i, *p_e);}else {printf("Error：无法找到第%d个元素，检查输入是否正确。\n", i);}break;case 6:printf("要查找的值为：");scanf("%d", &e);i = LocateElem(L, e);if (i) {printf("Success：第%d个位置\n", i);}else {printf("没有发现这个值。\n");}break;case 7:printf("输入插入的位置（下标从1开始）以及插入的数值，用空格隔开：\n");scanf("%d %d", &i, &e);if (ListInsert(L, i, e)) {printf("Success\n");}else {printf("Error：插入失败!\n");}break;case 8:printf("表中元素个数为：%d\n", ListLight(L));break;case 9:printAll(L);break;case 10:printf("随机生成几个数？");scanf("%d", &i);randList(L, i);break;case 11:printf("输入要插入的数：");scanf("%d", &e);if (insertHead(L, e)) {printf("Success：插入成功。\n");}else {printf("Error：插入失败!\n");}break;case 12:printf("输入要插入的数：");scanf("%d", &e);if (insertEnd(L, e)) {printf("Success：插入成功。\n");}else {printf("Error：插入失败!\n");}break;case 13:if (deleteEnd(L)) {printf("Success：删除成功。\n");}else {printf("Error：删除失败\n");}break;case 14:/*	printf("%p\n", &L);printf("%p\n", L);*/Reverse(L);break;default:printf("Error：错误输入。\n");break;}}free(p_e);return 0;
}

一、双向循环链表简介

双向循环链表是一种在链表基础上拓展而来的数据结构。与普通链表不同的是，它的每个节点都有两个指针，一个指向前驱节点（prior），一个指向后继节点（next）。而且，它是循环的，即链表的尾节点的后继指针指向头节点，头节点的前驱指针指向尾节点，形成一个闭合的环。

我们这里讨论的双向循环链表还有一个独立的头节点。这个独立头节点不存储数据，主要用于方便对链表的操作和维护。这种链表为空的条件是头节点的next和prior指针都指向NULL。

二、代码结构和数据类型定义

（一）数据类型定义

在代码中，首先定义了链表节点的数据类型。通过以下结构体来表示一个节点：

typedef struct Node {ElemType data;struct Node* next;struct Node* prior;
} Node;
typedef Node* DuLinkList;

这里，ElemType被定义为int类型，用于存储节点的数据。Node结构体包含了数据域data以及next和prior这两个指针，分别用于构建链表的双向连接。DuLinkList则是指向Node类型的指针，它代表了整个链表（实际上是从独立头节点开始）。

（二）函数声明

代码中声明了一系列操作双向循环链表的函数，包括创建链表、判断链表是否为空、清空链表、按位获取元素、按值查找元素、插入元素（按位插入、头插法、尾插法）、删除元素（按位删除、尾删除）以及链表的反转等功能。这些函数为我们全面操作链表提供了丰富的接口。

三、主要函数实现分析

（一）创建链表 - ListCreate函数

Status ListCreate(DuLinkList* L) {*L = (DuLinkList)malloc(sizeof(Node));if (!L) {printf("创建失败!\n");return 0;}(*L)->data = 0;(*L)->next = NULL;(*L)->prior = NULL;printf("创建成功!\n");return 1;
}

这个函数用于创建一个空的链表。它通过malloc函数为链表的头节点分配内存空间。如果分配成功，将头节点的data初始化为0，next和prior指针都设为NULL，并返回1表示创建成功；如果malloc失败，则返回0。

（二）判断链表是否为空 - LinkEmpty函数

Status LinkEmpty(DuLinkList L) {int flag;flag = (L->next == NULL)? 0 : 1;return flag;
}

通过检查链表头节点的next指针是否为NULL来判断链表是否为空。如果next为NULL，说明链表没有数据节点，返回0；否则返回1。

（三）清空链表 - ClearList函数

Status ClearList(DuLinkList L) {DuLinkList p;p = L->next;int j = 1;while (1) {if (p == L->prior) {free(p);break;}p = p->next;free(p->prior);}L->next = NULL;L->prior = NULL;L->data = 0;return 1;
}

这个函数用于清空链表。它从链表的第一个数据节点开始，依次释放每个节点的内存。在遍历过程中，通过free(p->prior)释放当前节点的前驱节点，直到到达尾节点。最后，将头节点的next和prior指针设为NULL，data设为0。

（四）按位获取元素 - GetElem函数

Status GetElem(DuLinkList L, int i, ElemType* e) {DuLinkList p;p = L->next;int j = 1;while (j < i) {if (p == L->prior && j!= 1 || p == NULL) { return 0; } p = p->next;j++;}if (j > i || p == NULL) { return 0; }*e = p->data;return 1;
}

该函数用于获取链表中指定位置i的元素值。通过遍历链表，从头节点的下一个节点开始，逐个移动指针p，直到找到第i个节点。如果找到了，将该节点的数据存储到e所指向的变量中，并返回1；如果在遍历过程中出现指针转了一圈还没找到或者p为NULL等情况，则返回0。

（五）按值查找元素 - LocateElem函数

Status LocateElem(DuLinkList L, ElemType e) {DuLinkList p;p = L->next;int i;i = 1;while (p) {if (p->data == e) { return i; }if (p == L->prior) { break; }p = p->next;i++;}return 0;
}

在链表中查找值为e的元素。从链表的第一个数据节点开始，逐个比较节点的数据值与e是否相等。如果找到相等的值，返回该元素在链表中的序号；如果遍历完整个链表都没找到，则返回0。

（六）按位插入元素 - ListInsert函数

Status ListInsert(DuLinkList L, int i, ElemType e) {DuLinkList p, s;p = L->next;s = NULL;int j = 1;if (i < 1) {printf("第%d个元素不存在。\n", i);return 0;}while (j < i) {if (p == L->next && j!= 1) {printf("第%d个元素不存在。\n", i);return 0;}p = p->next;j++;}s = (DuLinkList)malloc(sizeof(Node));if (!s) {printf("内存申请失败！\n");}s->data = e;if (L->next == NULL) {s->next = s;s->prior = s;L->next = s;L->prior = s;}else {s->next = p;s->prior = p->prior;p->prior->next = s;p->prior = s;if (i == 1) { L->next = s;}else if (i == L->data + 1) { L->prior = s;}}L->data++;return 1;
}

这个函数实现在链表的指定位置i插入新元素e。首先，通过遍历找到要插入位置的前一个节点p。然后创建一个新节点s，并根据链表是否为空以及插入位置是否为首元节点或尾节点等情况，调整节点之间的指针关系，最后增加链表长度计数器L->data的值。

（七）按位删除元素 - ListDelete函数

Status ListDelete(DuLinkList L, int i, ElemType* e) {DuLinkList p;p = L->next;int j = 1;if (i < 1 || i>L->data) {printf("第%d个元素不存在。\n", i);return 0;}while (j < i) {p = p->next;j++;}*e = p->data;if (L->next == L->prior) {L->next = NULL;L->prior = NULL;}else if (L->next == p) {L->next = p->next;}else if (L->prior == p) {L->prior = p->prior;}p->next->prior = p->prior;p->prior->next = p->next;free(p);L->data--;return 1;
}

用于删除链表中指定位置i的元素，并将删除元素的值存储到e所指向的变量中。先找到要删除的节点p，然后根据链表中节点的数量情况（如只有一个元素、删除第一个元素、删除最后一个元素等）调整指针关系，最后释放被删除节点的内存，并减少链表长度计数器的值。

（八）头插法 - insertHead函数

Status insertHead(DuLinkList L, ElemType e) {DuLinkList p, s;p = L->next;s = (DuLinkList)malloc(sizeof(Node));if (s == NULL) {return 0;}s->data = e;L->next = s;if (!p) {L->prior = s;s->next = s;s->prior = s;}else {s->next = p;s->prior = L->prior;L->prior->next = s;p->prior = s;}L->data++;return 1;
}

实现将一个元素插入到链表头部。创建一个新节点s，将其数据域设为e，然后调整头节点与新节点以及原第一个节点（如果存在）之间的指针关系，最后增加链表长度。

（九）尾插法 - insertEnd函数

Status insertEnd(DuLinkList L, ElemType e) {DuLinkList p, s;p = L->prior;s = (DuLinkList)malloc(sizeof(Node));if (!s) {return 0;}s->data = e;L->prior = s;if (!p) {L->next = s;s->next = s;s->prior = s;}else {s->prior = p;s->next = L->next;L->next->prior = s;p->next = s;}L->data++;return 1;
}

将元素插入到链表的末尾。创建新节点s，设置其数据值为e，然后根据链表是否为空来调整新节点与链表尾节点（如果存在）以及头节点之间的指针关系，最后更新链表长度。

（十）尾删除 - deleteEnd函数

Status deleteEnd(DuLinkList L) {DuLinkList p;p = L->prior;if (!p) {return 0;}if (L->prior == L->next) {L->prior = NULL;L->next = NULL;}else {L->prior = p->prior;L->prior->next = L->next;L->next->prior = L->prior;}L->data--;free(p);return 1;
}

用于删除链表的尾节点。首先判断链表是否为空，如果不为空，根据链表中节点数量情况（只有一个节点或多个节点）调整指针关系，释放尾节点内存并减少链表长度。

（十一）链表反转 - ListReverse函数

void ListReverse(DuLinkList L) {DuLinkList p, agent;p = L->next;agent = NULL;while (p) {agent = p->next;p->next = p->prior;p->prior = agent;if (p == L->prior) {break;}p = agent;}agent = L->next;L->next = L->prior;L->prior = agent;
}

这个函数通过交换每个节点的next和prior指针来实现链表的反转。使用一个临时指针agent来辅助交换过程，遍历链表，逐个交换节点的指针，最后调整头节点的next和prior指针，完成链表的反转。

（十二）另一种链表反转 - Reverse函数

void Reverse(DuLinkList L) {DuLinkList p, s;p = L->next;s = NULL;ListCreate(&s);if (!s) {return;}while (p) {insertHead(s, p->data);if (p == L->prior) {break;}p = p->next;}ClearList(L);*L = *s;free(s);
}

这是另一种实现链表反转的方法。它先创建一个新的链表s，然后通过遍历原链表L，将原链表的元素以头插法插入到新链表s中。接着清空原链表L，再将新链表s的内容复制到原链表L中（通过*L = *s），最后释放新链表s的头节点内存。