赞
踩
- 让头结点的 前驱指针 指向 链表的最后一个结点
- 让 最后一个结点 的后继指针 指向 头结点。
双向循环链表的结构与双向链表完全一致,不同之处在于它的尾结点的next指针指向头结点,而头结点的prior指针指向尾结点,从而形成一个循环。
//1.双向循环链表的结构定义(与双向链表完全一致)
typedef struct DNode
{
ElemType data;// 数据域
struct DNode* prior, * next; //前驱和后继指针
}DNode,*HLinkList;
//HNode * 用来定义结点指针
//HLinkList 用来定义链表指针
InitLinkList(HLinkList* L)
双向链表初始化时,其头结点的next和prior分别指向NULL
双向循环链表初始化时,其头结点的next和prior分别指向自己,构成一个环
(1)初始化头结点内存空间
(2)初始化头结点两个指针域指向自身
// 2. 双向循环链表的初始化操作 bool InitLinkList(HLinkList* L) { // 1 为链表的头结点分配内存 *L = (DNode*)malloc(sizeof(DNode)); // 2 检查内存分配是否成功 if (*L == NULL) { printf("内存分配失败!\n"); return false; } // 3 初始化头结点的前驱和后继指针,指向自身,形成空的循环链表 (*L)->next = *L; (*L)->prior = *L; // 4 返回初始化成功的标志 return true; }
DLinkListEmpty(HLinkList L)
(1)检查头指针是否为NULL,如果是,则链表未初始化,可以认为是空
(2)若头结点的后继和前驱指针指向自身,则链表为空
// 3. 双向循环链表的判空操作 bool DLinkListEmpty(HLinkList L) { //1 如果链表指针为空,则链表为空 if (L == NULL) { return true; } //2 如果链表的头结点的后继和前驱指针指向自身,则链表为空 //这里可以取其一,但是为了严谨性,取两者 if (L->next == L&&L->prior==NULL) { return true; } else { return false; } }
InsertDLinkList(HLinkList L, int i, ElemType e)
由于链表是循环链表,因此终止条件不能直接使用 p != L;
应通过 p->next != L 来终止遍历
那么相应的 i 大于链表长度加1的情况的判断就有所不同
假设在p结点与p->next结点中插入一个新结点s
这里的p结点相当于指向待插入结点的前一个结点
<1>s->prior=p;//改变新结点前驱指向
<2>s->next=p->next;//改变新结点后继指向
<3>p->next->prior=s;//改变p->next结点前驱指向
<4>p->next=s;//改变p结点后继指向
图解图下:
在表中 头结点 与 尾结点之间任意位置插入
<1>s->prior = p;//等价于s->prior =L;
<2>s->next = p->next;//等价于s->next = L;
<3>L->prior = s;
<4>L->next = s;
空表尾部插入
(0) 错误处理:头结点不存在 或 i小于1
(1)初始化临时指针p指向头结点
(2)初始化计数器为0
(3)循环查找第i-1个结点的位置(注意终止条件:p->next != L)
(4)异常判断(i大于表长加1的情况(该插入位置错误))
(5)建立并初始化插入结点
(6)空表尾部插入操作(注意改变头结点的prior与next域)
(7)非空表的尾部插入或一般插入操作(与双向链表的正常插入过程一致)
// 4. 双向循环链表的按位插入操作 // 由于链表是循环链表,因此终止条件不能直接使用 p != L; // 应通过 p->next != L 来终止遍历 bool InsertDLinkList(HLinkList L, int i, ElemType e) { //[0]错误处理:头结点不存在 或 i小于1 if (L == NULL || i < 1) { return false; } //[1]初始化临时指针p指向头结点 DNode* p = L; //[2]初始化计数器为0 int j = 0; //[3]循环查找第i-1个结点的位置 //p->next!=L: //1.保证首元结点不存在时,不进入循环 //2.保证i大于表长时, p指向尾结点,终止循环(此时如果待插入位置为尾结点的下一个结点,这是有效的,所以i大于表长加1的情况需要特判) //j<i-1: //正常情况下,找到第i-1个结点 while (p->next != L && j < i - 1) { p = p->next; j++; } //[4]异常判断 //p->next == L && j != i - 1: //i大于表长加1的情况(该插入位置错误) if (p->next == L && j != i - 1) { return false; } //[5]建立并初始化插入结点 DNode* s = (DNode*)malloc(sizeof(DNode)); if (s == NULL) { printf("内存分配失败!\n"); return false; } s->data = e; //[6]空表尾部插入操作(注意改变头结点的prior与next域) // 此时 p 指向头结点,且链表为空(头结点的 next 和 prior 都指向头结点自身) if (p->next == L && p->prior == L) { s->prior = p;//等价于s->prior =L; s->next = p->next;//等价于s->next = L; //当前p指向空表的头结点,并不存在p->next 结点,所以直接更改头结点的prior,next域即可(为了维护循环结构的完整性) L->prior = s; L->next = s; } //[7]非空表的尾部插入或一般插入操作(与双向链表的正常插入过程一致) else { s->prior = p; s->next = p->next;//先解决待插入结点的前驱后继指向 p->next->prior = s;//然后解决 待插入结点 后继结点 的前驱指向 p->next = s;//最后解决 待插入结点 前驱结点的 后继指向 } return true; }
DeleteDLinkList(HLinkList L, int i, ElemType *e)
假设删除p结点,即待删除结点
只有一个元素时删除首元结点
正常情况下删除尾结点
正常情况下删除中间结点
(0)错误处理:头结点不存在 或 i小于1
(1)初始化临时指针p指向首元结点
(2)初始化计数器为1
(3)循环查找第i个结点的位置
(4)异常判断(主要是i大于表长的情况)
(5)核心:删除结点并释放空间
// 5. 双向循环链表的按位删除操作(与双向链表的删除过程完全一致,但是注意终止条件) bool DeleteDLinkList(HLinkList L, int i, ElemType *e) { //[0]错误处理:头结点不存在 或 i小于1 if (L == NULL || i < 1) { return false; } //[1]初始化临时指针p指向首元结点 DNode* p = L->next; //[2]初始化计数器为1 int j = 1; //[3]循环查找第i个结点的位置 //p!=L: //1.保证首元结点不存在时,不进入循环 //2.保证i大于表长时,p指向尾结点next域(L),终止循环(比如:i=表长加1:此时待删除位置是尾结点 的后面 该位置是头结点的位置) //j<i-1: //正常情况下,找到第i个结点 while (p != L && j < i) { p = p->next; j++; } //[4]异常判断 //p==L: //1.首元结点不存在的情况(空表) //2.i大于表长的情况(该删除位置为头结点) if (p == L) { return false; } //[5]核心:删除结点:更新前驱和后继结点的指针(只要不删除头结点就是对的) *e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p);//释放待删除结点空间 return true; }
bool CreateDLinkList_H(HLinkList* L, int n)
插入到空表表头(实际上与按位插入操作中插入到空表表头的操作完全一致)
插入到非空表表头(同样与按位插入操作中插入到正常位置的操作思路一致)
(1)建立链表头结点并初始化next与prior域 指向自身
(2)循环插入新结点到表头
<1>初始化新结点
<2>改变指针指向(与按位插入的操作大同小异)
<2.1>s插入到空表表头
<2.2>s插入到非空表表头
// 6. 双向循环链表的头插法建立 bool CreateDLinkList_H(HLinkList* L, int n) { //[1]建立链表头结点并初始化next与prior域:注意指向自身 *L = (DNode*)malloc(sizeof(DNode)); if ((*L) == NULL) { printf("内存分配失败!\n"); return false; } (*L)->next = (*L); (*L)->prior = (*L); DNode* s; //[2]循环插入新结点到表头 for (int i = 0; i < n; i++) { //<1>初始化新结点 s = (DNode*)malloc(sizeof(DNode)); if (s == NULL) { printf("内存分配失败!\n"); return false; } scanf_s("%d", &s->data); //<2>改变指针指向(与按位插入的操作大同小异) //<2.1>s插入到空表表头 if ((*L)->next == (*L) && (*L)->prior == (*L)) { //如果链表为空,将新结点插入到头结点之后 s->prior = *L; s->next = *L; (*L)->next = s; (*L)->prior = s; } //<2.2>s插入到非空表表头 else { //如果链表非空,将新结点插入到头结点之后 s->prior = (*L); s->next = (*L)->next; (*L)->next->prior = s; (*L)->next = s; } } return true; }
插入到表尾
(1)建立链表头结点并初始化next与prior域(注意指向自身)
(2)初始化尾指针,指向链表的头结点
(3)循环插入新结点到表尾
<1> 初始化新结点
<2> 改变指针指向 (插入到尾部 且 不需要特判)
<2.1>先解决新结点的next与prior域
<2.2> 再解决当前尾结点的next域 并 更新尾指针指向
这里着重注意更新头结点的prior域,以保证循环结构的完整性
// 7.双向循环链表的尾插建立 bool CreateDLinkList_T(HLinkList* L, int n) { // [1] 建立链表头结点并初始化next与prior域(注意指向自身) *L = (DNode*)malloc(sizeof(DNode)); if (*L == NULL) { printf("内存分配失败!\n"); return false; } (*L)->next = (*L); // 头结点的next指针指向自身,形成循环 (*L)->prior = (*L); // 头结点的prior指针指向自身,形成循环 // [2] 初始化尾指针,指向链表的头结点 DNode* t = (*L); DNode* s; // [3] 循环插入新结点到表尾 for (int i = 0; i < n; i++) { // <1> 初始化新结点 s = (DNode*)malloc(sizeof(DNode)); if (s == NULL) { printf("内存分配失败!\n"); return false; } scanf_s("%d", &s->data); // <2> 改变指针指向 (插入到尾部 且 不需要特判) //<2.1>先解决新结点的next与prior域 s->prior = t; s->next = *L;//注意循环结构的完整性 //<2.2> 再解决当前尾结点的next域 并 更新尾指针指向 //这里着重注意更新头结点的prior域,以保证循环结构的完整性 t->next = s; // 更新当前尾结点的next域 (*L)->prior = s; // 更新头结点的prior域指向新结点(保证循环结构的完整性) t = s; // 更新尾指针t,指向新的尾结点 } return true; }
printDLinkList(HLinkList L)
(0)错误处理: 头结点不存在或首元结点不存在
(1)初始化临时指针p指向首元结点
(2)错误处理: 首元结点不存在 (空表)
(3)循环遍历链表直到尾结点
// 8.双向循环链表的整表输出 bool printDLinkList(HLinkList L) { // [0] 错误处理: 头结点不存在或首元结点不存在 if (L == NULL || L->next == L) { return false; } // [1] 初始化临时指针p指向首元结点 DNode* p = L->next; // [3] 循环遍历链表直到尾结点 while (p != L) { printf("%d-->", p->data); p = p->next; } printf("end\n"); return true; }
#include <stdio.h> #include <stdlib.h> typedef int ElemType; #define bool int #define true 1 #define false 0 //1.双向循环链表的结构定义(与双向链表完全一致) typedef struct DNode { ElemType data;// 数据域 struct DNode* prior, * next; //前驱和后继指针 }DNode, * HLinkList; //DNode * 用来定义结点指针 //HLinkList 用来定义链表指针 // 2. 双向循环链表的初始化操作 bool InitLinkList(HLinkList* L) { // 1 为链表的头结点分配内存 *L = (DNode*)malloc(sizeof(DNode)); // 2 检查内存分配是否成功 if (*L == NULL) { printf("内存分配失败!\n"); return false; } // 3 初始化头结点的前驱和后继指针,指向自身,形成空的循环链表 (*L)->next = *L; (*L)->prior = *L; // 4 返回初始化成功的标志 return true; } // 3. 双向循环链表的判空操作 bool DLinkListEmpty(HLinkList L) { //1 如果链表指针为空,则链表为空 if (L == NULL) { return true; } //2 如果链表的头结点的后继和前驱指针指向自身,则链表为空 //这里可以取其一,但是为了严谨性,取两者 if (L->next == L&&L->prior==NULL) { return true; } else { return false; } } // 4. 双向循环链表的按位插入操作 // 由于链表是循环链表,因此终止条件不能直接使用 p != L; // 应通过 p->next != L 来终止遍历 bool InsertDLinkList(HLinkList L, int i, ElemType e) { //[0]错误处理:头结点不存在 或 i小于1 if (L == NULL || i < 1) { return false; } //[1]初始化临时指针p指向头结点 DNode* p = L; //[2]初始化计数器为0 int j = 0; //[3]循环查找第i-1个结点的位置 //p->next!=L: //1.保证首元结点不存在时,不进入循环 //2.保证i大于表长时, p指向尾结点,终止循环(此时如果待插入位置为尾结点的下一个结点,这是有效的,所以i大于表长加1的情况需要特判) //j<i-1: //正常情况下,找到第i-1个结点 while (p->next != L && j < i - 1) { p = p->next; j++; } //[4]异常判断 //p->next == L && j != i - 1: //i大于表长加1的情况(该插入位置错误) if (p->next == L && j != i - 1) { return false; } //[5]建立并初始化插入结点 DNode* s = (DNode*)malloc(sizeof(DNode)); if (s == NULL) { printf("内存分配失败!\n"); return false; } s->data = e; //[6]空表尾部插入操作(注意改变头结点的prior与next域) // 此时 p 指向头结点,且链表为空(头结点的 next 和 prior 都指向头结点自身) if (p->next == L && p->prior == L) { s->prior = p;//等价于s->prior =L; s->next = p->next;//等价于s->next = L; //当前p指向空表的头结点,并不存在p->next 结点,所以直接更改头结点的prior,next域即可(为了维护循环结构的完整性) L->prior = s; L->next = s; } //[7]非空表的尾部插入或一般插入操作(与双向链表的正常插入过程一致) else { s->prior = p; s->next = p->next;//先解决待插入结点的前驱后继指向 p->next->prior = s;//然后解决 待插入结点 后继结点 的前驱指向 p->next = s;//最后解决 待插入结点 前驱结点的 后继指向 } return true; } // 5. 双向循环链表的按位删除操作(与双向链表的删除过程完全一致,但是注意终止条件) bool DeleteDLinkList(HLinkList L, int i, ElemType *e) { //[0]错误处理:头结点不存在 或 i小于1 if (L == NULL || i < 1) { return false; } //[1]初始化临时指针p指向首元结点 DNode* p = L->next; //[2]初始化计数器为1 int j = 1; //[3]循环查找第i个结点的位置 //p!=L: //1.保证首元结点不存在时,不进入循环 //2.保证i大于表长时,p指向尾结点next域(L),终止循环(比如:i=表长加1:此时待删除位置是尾结点 的后面 该位置是头结点的位置) //j<i-1: //正常情况下,找到第i个结点 while (p != L && j < i) { p = p->next; j++; } //[4]异常判断 //p==L: //1.首元结点不存在的情况(空表) //2.i大于表长的情况(该删除位置为头结点) if (p == L) { return false; } //[5]核心:删除结点:更新前驱和后继结点的指针(只要不删除头结点就是对的) *e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p);//释放待删除结点空间 return true; } // 6. 双向循环链表的头插法建立 bool CreateDLinkList_H(HLinkList* L, int n) { //[1]建立链表头结点并初始化next与prior域:注意指向自身 *L = (DNode*)malloc(sizeof(DNode)); if ((*L) == NULL) { printf("内存分配失败!\n"); return false; } (*L)->next = (*L); (*L)->prior = (*L); DNode* s; //[2]循环插入新结点到表头 for (int i = 0; i < n; i++) { //<1>初始化新结点 s = (DNode*)malloc(sizeof(DNode)); if (s == NULL) { printf("内存分配失败!\n"); return false; } scanf_s("%d", &s->data); //<2>改变指针指向(与按位插入的操作大同小异) //<2.1>s插入到空表表头 if ((*L)->next == (*L) && (*L)->prior == (*L)) { //如果链表为空,将新结点插入到头结点之后 s->prior = *L; s->next = *L; (*L)->next = s; (*L)->prior = s; } //<2.2>s插入到非空表表头 else { //如果链表非空,将新结点插入到头结点之后 s->prior = (*L); s->next = (*L)->next; (*L)->next->prior = s; (*L)->next = s; } } return true; } // 7.双向循环链表的尾插建立 bool CreateDLinkList_T(HLinkList* L, int n) { // [1] 建立链表头结点并初始化next与prior域(注意指向自身) *L = (DNode*)malloc(sizeof(DNode)); if (*L == NULL) { printf("内存分配失败!\n"); return false; } (*L)->next = (*L); // 头结点的next指针指向自身,形成循环 (*L)->prior = (*L); // 头结点的prior指针指向自身,形成循环 // [2] 初始化尾指针,指向链表的头结点 DNode* t = (*L); DNode* s; // [3] 循环插入新结点到表尾 for (int i = 0; i < n; i++) { // <1> 初始化新结点 s = (DNode*)malloc(sizeof(DNode)); if (s == NULL) { printf("内存分配失败!\n"); return false; } scanf_s("%d", &s->data); // <2> 改变指针指向 (插入到尾部 且 不需要特判) //<2.1>先解决新结点的next与prior域 s->prior = t; s->next = *L;//注意循环结构的完整性 //<2.2> 再解决当前尾结点的next域 并 更新尾指针指向 //这里着重注意更新头结点的prior域,以保证循环结构的完整性 t->next = s; // 更新当前尾结点的next域 (*L)->prior = s; // 更新头结点的prior域指向新结点(保证循环结构的完整性) t = s; // 更新尾指针t,指向新的尾结点 } return true; } // 8.双向循环链表的整表输出 bool printDLinkList(HLinkList L) { // [0] 错误处理: 头结点不存在或首元结点不存在 if (L == NULL || L->next == L) { return false; } // [1] 初始化临时指针p指向首元结点 DNode* p = L->next; // [3] 循环遍历链表直到尾结点 while (p != L) { printf("%d-->", p->data); p = p->next; } printf("end\n"); return true; } int main() { HLinkList L1,L2; printf("头插法建立双向循环链表L1:\n"); CreateDLinkList_H(&L1, 6); printf("尾插法建立双向循环链表L2:\n"); CreateDLinkList_T(&L2, 6); printf("从头打印双向循环链表L1:\n"); printDLinkList(L1); printf("\n"); printf("从头打印双向循环链表L2:\n"); printDLinkList(L2); printf("向L2中插入部分元素!\n"); printf("表尾插入:\n"); InsertDLinkList(L2, 7, 3); printDLinkList(L2); printf("表头插入:\n"); InsertDLinkList(L2, 1, 33); printDLinkList(L2); printf("删除L2中部分元素:\n"); ElemType e1; printf("删除表头元素!\n"); DeleteDLinkList(L2, 1, &e1); printDLinkList(L2); ElemType e2; printf("删除表尾元素!\n"); DeleteDLinkList(L2, 7, &e2); printDLinkList(L2); if (DLinkListEmpty(L2)) { printf("L2为空表!\n"); } else { printf("L2不为空表!\n"); } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。