C语言超详细讲解数据结构中双向带头循环链表
什么是双向带头循环链表
双向带头循环链表是一种非常常用的数据结构，它由多个节点组成，每个节点都有一个前驱指针和一个后继指针，形成一个双向链表；同时，它也是循环链表，即链表的头指针和尾指针是相连的形成一个环的结构；而带头链表则是在链表的开头添加一个头节点来方便书写，方便读者理解，常见于书籍和教程中。
因此，双向带头循环链表的结构可以表示为：
------ ------ ------
|head | <----> |node1| <----> |node2| <----> ... <----> |nodeN| <----> |head |
------ ------ ------ ------
双向带头循环链表的实现
定义节点结构体
首先，我们需要定义一个节点的结构体，如下所示：
typedef struct DNode {
int data; // 节点数值 data
struct DNode *prior, *next; // 指向直接前驱和直接后继的指针
} DNode, *DLinkList;
节点结构体中，除了记录节点的数值外，还有指向前驱和后继节点的指针，此处用prior和next变量表示，方便我们理解。
初始化双向带头循环链表
接下来我们需要初始化双向带头循环链表，我们定义一个InitList()函数来实现链表的初始化。
int InitList(DLinkList *L) {
DNode *head = (DNode*)malloc(sizeof(DNode)); // 为头节点分配内存空间
if (!head) // 内存分配失败
return 0; // 返回0表示初始化失败
head->data = 0; // 头节点的数据域为0
head->next = head; // 头节点的后继指针指向头节点本身
head->prior= head; // 头节点的前驱指针指向头节点本身
*L = head; // 将头节点赋给L指向的链表指针
return 1; // 返回1表示初始化成功
}
双向带头循环链表的插入
接下来，我们需要实现双向带头循环链表的插入，即在链表指定位置插入一个新节点。此处我们定义一个InsertList()函数来实现节点的插入。
int InsertList(DLinkList L, int pos, int e) {
int i = 0; // i为计数器
DNode *p = L, *s; // p为指向当前遍历到的节点, s为插入的新节点
while (p && i < pos - 1) { // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
i++;
p = p->next;
}
if (!p || i > pos - 1) // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
return 0; // 返回0表示插入失败
s = (DNode*)malloc(sizeof(DNode)); // 为新节点分配内存空间
s->data = e; // 新节点的数据域为e
s->prior= p; // 新节点的前驱指向p
s->next = p->next; // 新节点的后继指向p的后继
p->next->prior= s; // p的后继的前驱指向s
p->next = s; // p的后继指向s
return 1; // 返回1表示插入成功
}
双向带头循环链表的删除
除了插入节点，我们还需要实现双向带头循环链表的删除操作。这里我们定义一个DeleteList()函数来实现删除操作。
int DeleteList(DLinkList L, int pos) {
int i = 0; // i为计数器
DNode *p = L, *q; // p为指向当前遍历到的节点，q为被删除的节点
while (p->next != L && i < pos - 1) { // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
i++;
p = p->next;
}
if (p->next == L || i > pos - 1) // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
return 0; // 返回0表示删除失败
q = p->next; // q指向要删除的节点
q->next->prior= p; // q的后继的前驱指向p
p->next = q->next; // p的后继指向q的后继
free(q); // 释放q节点的内存空间
return 1; // 返回1表示删除成功
}
双向带头循环链表的遍历
最后，我们需要遍历整个双向带头循环链表，即输出链表中的每一个节点。此处我们定义一个TraverseList()函数来实现链表的遍历。
int TraverseList(DLinkList L) {
DNode *p = L->next; // 从第一个节点开始遍历
while (p != L) { // 遍历到尾节点为止
printf("%d ", p->data); // 输出节点的数据域
p = p->next; // 指向下一个节点
}
printf("\n");
return 1; // 返回1表示遍历成功
}
示例说明
示例1：向链表中插入3个节点，并输出链表
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode {
int data; // 节点数值 data
struct DNode *prior, *next; // 指向直接前驱和直接后继的指针
} DNode, *DLinkList;
int InitList(DLinkList *L) {
DNode *head = (DNode*)malloc(sizeof(DNode)); // 为头节点分配内存空间
if (!head) // 内存分配失败
return 0; // 返回0表示初始化失败
head->data = 0; // 头节点的数据域为0
head->next = head; // 头节点的后继指针指向头节点本身
head->prior= head; // 头节点的前驱指针指向头节点本身
*L = head; // 将头节点赋给L指向的链表指针
return 1; // 返回1表示初始化成功
}
int InsertList(DLinkList L, int pos, int e) {
int i = 0; // i为计数器
DNode *p = L, *s; // p为指向当前遍历到的节点, s为插入的新节点
while (p && i < pos - 1) { // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
i++;
p = p->next;
}
if (!p || i > pos - 1) // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
return 0; // 返回0表示插入失败
s = (DNode*)malloc(sizeof(DNode)); // 为新节点分配内存空间
s->data = e; // 新节点的数据域为e
s->prior= p; // 新节点的前驱指向p
s->next = p->next; // 新节点的后继指向p的后继
p->next->prior= s; // p的后继的前驱指向s
p->next = s; // p的后继指向s
return 1; // 返回1表示插入成功
}
int DeleteList(DLinkList L, int pos) {
int i = 0; // i为计数器
DNode *p = L, *q; // p为指向当前遍历到的节点，q为被删除的节点
while (p->next != L && i < pos - 1) { // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
i++;
p = p->next;
}
if (p->next == L || i > pos - 1) // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
return 0; // 返回0表示删除失败
q = p->next; // q指向要删除的节点
q->next->prior= p; // q的后继的前驱指向p
p->next = q->next; // p的后继指向q的后继
free(q); // 释放q节点的内存空间
return 1; // 返回1表示删除成功
}
int TraverseList(DLinkList L) {
DNode *p = L->next; // 从第一个节点开始遍历
while (p != L) { // 遍历到尾节点为止
printf("%d ", p->data); // 输出节点的数据域
p = p->next; // 指向下一个节点
}
printf("\n");
return 1; // 返回1表示遍历成功
}
int main() {
DLinkList L; // 声明双向带头循环链表
if (InitList(&L)) { // 初始化链表
InsertList(L, 1, 1); // 向链表的第一个位置插入节点1
InsertList(L, 2, 2); // 向链表的第二个位置插入节点2
InsertList(L, 3, 3); // 向链表的第三个位置插入节点3
TraverseList(L); // 输出链表
return 0;
}
}
输出结果为：
1 2 3
示例2：删除链表中第二个节点，并输出链表
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode {
int data; // 节点数值 data
struct DNode *prior, *next; // 指向直接前驱和直接后继的指针
} DNode, *DLinkList;
int InitList(DLinkList *L) {
DNode *head = (DNode*)malloc(sizeof(DNode)); // 为头节点分配内存空间
if (!head) // 内存分配失败
return 0; // 返回0表示初始化失败
head->data = 0; // 头节点的数据域为0
head->next = head; // 头节点的后继指针指向头节点本身
head->prior= head; // 头节点的前驱指针指向头节点本身
*L = head; // 将头节点赋给L指向的链表指针
return 1; // 返回1表示初始化成功
}
int InsertList(DLinkList L, int pos, int e) {
int i = 0; // i为计数器
DNode *p = L, *s; // p为指向当前遍历到的节点, s为插入的新节点
while (p && i < pos - 1) { // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
i++;
p = p->next;
}
if (!p || i > pos - 1) // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
return 0; // 返回0表示插入失败
s = (DNode*)malloc(sizeof(DNode)); // 为新节点分配内存空间
s->data = e; // 新节点的数据域为e
s->prior= p; // 新节点的前驱指向p
s->next = p->next; // 新节点的后继指向p的后继
p->next->prior= s; // p的后继的前驱指向s
p->next = s; // p的后继指向s
return 1; // 返回1表示插入成功
}
int DeleteList(DLinkList L, int pos) {
int i = 0; // i为计数器
DNode *p = L, *q; // p为指向当前遍历到的节点，q为被删除的节点
while (p->next != L && i < pos - 1) { // 定位到 pos 的前一位，如果 pos 为 1，则 p 为头节点
i++;
p = p->next;
}
if (p->next == L || i > pos - 1) // 跳出循环有两种情况, i > pos - 1 表示 pos 已经越界
return 0; // 返回0表示删除失败
q = p->next; // q指向要删除的节点
q->next->prior= p; // q的后继的前驱指向p
p->next = q->next; // p的后继指向q的后继
free(q); // 释放q节点的内存空间
return 1; // 返回1表示删除成功
}
int TraverseList(DLinkList L) {
DNode *p = L->next; // 从第一个节点开始遍历
while (p != L) { // 遍历到尾节点为止
printf("%d ", p->data); // 输出节点的数据域
p = p->next; // 指向下一个节点
}
printf("\n");
return 1; // 返回1表示遍历成功
}
int main() {
DLinkList L; // 声明双向带头循环链表
if (InitList(&L)) { // 初始化链表
InsertList(L, 1, 1); // 向链表的第一个位置插入节点1
InsertList(L, 2, 2); // 向链表的第二个位置插入节点2
InsertList(L, 3, 3); // 向链表的第三个位置插入节点3
DeleteList(L, 2); // 删除节点2
TraverseList(L); // 输出链表
return 0;
}
}
输出结果为：
1 3
阅读剩余 84%
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言超详细讲解数据结构中双向带头循环链表 - Python技术站
微信扫一扫 
支付宝扫一扫 