双向循环链表概念
双向循环链表，每个结点都有一个前驱prior和一个后继next，链表的的尾结点的后继指向头结点，形成一个循环链。
结点
空链表的首节点的prior和next都指向它本身
空的双向链表结构图
L指向首节点，A的前驱指向L，A的后继next指向B,尾结点B不同之处在于它的next指向首节点L，并且L指针永远处于首节点的位置。
非空双向链表结构图
双向循环链表结点的构建，并设置一些宏定义
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
ElemType data;
struct Node *prior;
struct Node *next;
}Node;
typedef struct Node * LinkList;
双向循环链表初始化
- 创建一个头结点，并将结点的前驱和后继都指向自己
- 为初始化链表新增一些值（方便后面进行一些增删改查的操作）
Status creatLinkList(LinkList *L){
*L = (LinkList)malloc(sizeof(Node));
if (*L == NULL) {
return ERROR;
}
(*L)->next = (*L);
(*L)->prior = (*L);
//新增数据
LinkList p = *L;
for(int i=0; i < 10;i++){
//1.创建1个临时的结点
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->data = i;
//2.为新增的结点建立双向链表关系
//① temp 是p的后继
p->next = temp;
//② temp 的前驱是p
temp->prior = p;
//③ temp的后继是*L
temp->next = (*L);
//④ p 的前驱是新建的temp
p->prior = temp;
//⑤ p 要记录最后的结点的位置,方便下一次插入
p = p->next;
}
return OK;
}
双向循环链表插入元素
插入接点的时候一定要将插入的点的next指向操作一定要在p设置next的前面，否者的将丢失后面的结点
- 先找到插入结点的前一个结点p
- 创建新节点temp赋值，temp的后继等于p的后继
- p的后继等于temp ，temp的前驱等于p
- 判断插入的位置是不是尾结点，如果是尾结点，p后继的前驱等于temp，头结点的前驱要 等于temp，这样就完成了结点的插入。
Status LinkListInsert(LinkList *L, int index, ElemType e){
LinkList p = (*L);
int i = 1;
//判断链表是否为空
if (p == NULL) {
return ERROR;
}
//如果不为空则插入元素
//先找到插入结点的前一个结点p
while (i < index && p->next != *L) {
p = p->next;
i++;
}
//判断找到的位置i是否合法
if(i > index)return ERROR;
//创建新节点
LinkList temp = (LinkList)malloc(sizeof(Node));
//赋值
temp->data = e;
temp->next = p->next;
temp->prior = p;
p->next = temp;
if (p->next != *L) {
p->next->prior = temp;
}else{
(*L)->prior = temp;
}
return OK;
}
双向循环链表的遍历
p != L作为限制循环链表的遍历条件，只遍历链表一遍
Status DisplayLinkList(LinkList L){
if (L == NULL) {
printf("打印的双向循环链表为空!\n\n");
return ERROR;
}
printf("双向循环链表内容: ");
LinkList p = L->next;
while (p != L) {
printf("%d ",p->data);
p = p->next;
}
printf("\n\n");
return OK;
}
双向循环链表删除结点
- 如果删除到只剩下首元结点了,则直接将*L置空
- 找到要删除的结点
- 给要删除结点的数据域赋值给e
- 修改被删除结点的前驱结点的后继指针
- 修改被删除结点的后继结点的前驱指针
- 删除结点temp
Status LinkListDelete(LinkList *L,int index,ElemType *e){
int i = 1;
LinkList temp = (*L)->next;
if (*L == NULL) {
return ERROR;
}
//如果删除到只剩下首元结点了,则直接将*L置空;
if(temp->next == *L){
free(*L);
(*L) = NULL;
return OK;
}
//找到要删除的结点
while (i < index) {
temp = temp->next;
i++;
}
//给e赋值要删除结点的数据域
*e = temp->data;
//修改被删除结点的前驱结点的后继指针
temp->prior->next = temp->next;
//修改被删除结点的后继结点的前驱指针
temp->next->prior = temp->prior;
// 删除结点temp
free(temp);
return OK;
}
网友评论