@TOC
回顾一下，前面一篇博客“数据结构和算法（二）单向循环链表的创建插入删除实现”中讲解了单向链表和单向循环链表。 这篇博客主要讲解双向链表和双向循环链表的基本操作实现。
本篇博客的Demo下载：
1. 双向链表
- 我们为啥要使用双向链表，相比单向链表，双向链表的优点是什么？
单链表相对于顺序表，确实在某些场景下解决了一些重要的问题，例如在需要插入或者删除大量元素的时候，它并不需要像顺序表一样移动很多元素，只需要修改指针的指向就可以了，其时间复杂度为 O(1) 但是这可是有前提的，那就是这一切都基于确定节点后，纯粹考虑删除和插入的情况下，但是如果我们仍未确定节点的位置，那么单链表就会出现一些问题了
我们先来对比一下单链表和双链表的删除操作:
回顾一下前面一篇博客“数据结构和算法（二）单向循环链表的创建插入删除实现”中讲解的单向链表删除操作，如下图我们要删除一个结点，假如想要删除第2个节点 a1 只需要 将首元结点的指针指向到第三个节点的地址去：
单链表删除结点
我们遇到的问题就在于我们如何得到待删除节点的前驱，也就是我们图中的首元结点，我们给出两种方法：
- A：定位待删除节点的同时，一直顺便保存当前节点的前驱
- B：删除节点后，重新回到单链表表头，定位到其指定前驱
但是无论我们选择哪一种方法，指针的总移动数都会是 2n 次，而双链表却在这一类型问题上做出了很好的处理。
我们接下来看一下双链表的删除结点的过程：
双向链表删除结点
双链表相比单链表每个结点都多了一个指向前驱的指针，这样我们无论是向前查找，还是向后查找都比较方便。单链表中之所以出现问题，就是因为各个节点只有一个指向后继的指针域 next，只能向后移动查找，一旦我们想要查询前一节点，就变得很麻烦，所以双链表就在每个节点前面增加一个指向前驱的指针域 prior，这样我们就可以直接定位到我们的前一个节点了，这也就是双链表的优点。
我们可以计算一下它们删除是的操作数量：
单链表和双链表删除操作数量对比
双链表虽然解决了单链表中的反向查找痛点，但是是以每个结点增加了一个指针域为代价的，也就是用空间来换取的。
接下来，我们来了解一下双向链表的基本操作代码实现。
1.1 结点定义
双向链表结点定义
//定义结点
typedef struct KNode{
KElementType data; //数据
struct KNode *prior; //前驱指针
struct KNode *next; //后继指针
}Node;
1.2 建表
非空的双链表-带头结点
非空的双链表-不带头结点
//5.1 创建双向链接
KStatus createLinkList(LinkList *L){
//*L 指向头结点
*L = (LinkList)malloc(sizeof(KNode));
if (*L == NULL) return ERROR;
(*L)->prior = NULL;
(*L)->next = NULL;
(*L)->data = -1;
//新增数据
LinkList p = *L;
for(int i=0; i < 10;i++){
//1.创建1个临时的结点
LinkList temp = (LinkList)malloc(sizeof(KNode));
temp->prior = NULL;
temp->next = NULL;
temp->data = I;
//2.为新增的结点建立双向链表关系
//① temp 是p的后继
p->next = temp;
//② temp 的前驱是p
temp->prior = p;
//③ p 要记录最后的结点的位置,方便下一次插入
p = p->next;
}
return OK;
}
1.3 插入结点
双向链表-插入结点1
在第i个位置插入元素，大概步骤如下：
- 创建新结点q
- 遍历链表，找到需要插入的位置的前一个元素p
- 将新元素q的前驱指向p，后继指向p->next
- 将p->next的前驱指向新元素q
- 将p的后继指向新元素q
插入结点的实现代码如下：
//5.3 双向链表插入元素
KStatus ListInsert(LinkList *L, int i, KElementType data){
//1. 插入的位置不合法 为0或者为负数
if(i < 1) return ERROR;
//2. 新建结点
LinkList temp = (LinkList)malloc(sizeof(KNode));
temp->data = data;
temp->prior = NULL;
temp->next = NULL;
//3.将p指向头结点!
LinkList p = *L;
//4. 找到插入位置i直接的结点
for(int j = 1; j < i && p;j++)
p = p->next;
//5. 如果插入的位置超过链表本身的长度
if(p == NULL){
return ERROR;
}
//6. 判断插入位置是否为链表尾部;
if (p->next == NULL) {
p->next = temp;
temp->prior = p;
}else
{
//1️⃣ 将p->next 结点的前驱prior = temp
p->next->prior = temp;
//2️⃣ 将temp->next 指向原来的p->next
temp->next = p->next;
//3️⃣ p->next 更新成新创建的temp
p->next = temp;
//4️⃣ 新创建的temp前驱 = p
temp->prior = p;
}
return OK;
}
1.4 删除结点
双向链表-删除结点
删除第i个位置的元素，大概步骤如下：
- 遍历链表，找到想要删除的位置的前一个元素p
- 创建新结点q，将要删除的元素赋值给p
- 将p->next指向q->next，将q->next的前驱指向p
- 释放q
删除结点的代码实现如下：
（1） 删除双向链表指定位置上的结点
//5.4 删除双向链表指定位置上的结点
KStatus ListDelete(LinkList *L, int i, KElementType *e){
int k = 1;
LinkList p = (*L);
//1.判断双向链表是否为空,如果为空则返回ERROR;
if (*L == NULL) {
return ERROR;
}
//2. 将指针p移动到删除元素位置前一个
while (k < i && p != NULL) {
p = p->next;
k++;
}
//3.如果k>i 或者 p == NULL 则返回ERROR
if (k>i || p == NULL) {
return ERROR;
}
//4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
LinkList delTemp = p->next;
*e = delTemp->data;
//5. p->next 等于要删除的结点的下一个结点
p->next = delTemp->next;
//6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
if (delTemp->next != NULL) {
delTemp->next->prior = p;
}
//7.删除delTemp结点
free(delTemp);
return OK;
}
（2） 删除双向链表指定的元素
//5.5 删除双向链表指定的元素
KStatus LinkListDeletVAL(LinkList *L, int data){
LinkList p = *L;
//1.遍历双向循环链表
while (p) {
//2.判断当前结点的数据域和data是否相等,若相等则删除该结点
if (p->data == data) {
//修改被删除结点的前驱结点的后继指针,参考图上步骤1️⃣
p->prior->next = p->next;
//修改被删除结点的后继结点的前驱指针,参考图上步骤2️⃣
if(p->next != NULL){
p->next->prior = p->prior;
}
//释放被删除结点p
free(p);
//退出循环
break;
}
//没有找到该结点,则继续移动指针p
p = p->next;
}
return OK;
}
1.5 遍历
//5.2 打印循环链表的元素
void display(LinkList L){
LinkList temp = L->next;
if(temp == NULL){
printf("打印的双向链表为空!\n");
return;
}
while (temp) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
1.6 查找
//5.6.1 在双向链表中查找元素
int selectElem(LinkList L,KElementType elem){
LinkList p = L->next;
int i = 1;
while (p) {
if (p->data == elem) {
return I;
}
I++;
p = p->next;
}
return -1;
}
1.7 更新
//5.6.2 在双向链表中更新结点
KStatus replaceLinkList(LinkList *L,int index,KElementType newElem){
LinkList p = (*L)->next;
for (int i = 1; i < index; i++) {
p = p->next;
}
p->data = newElem;
return OK;
}
1.8 单元测试
void test () {
KStatus iStatus = 0;
LinkList L;
int temp,item,e;
iStatus = createLinkList(&L);
printf("iStatus = %d\n",iStatus);
printf("链表创建成功,打印链表:\n");
display(L);
printf("请输入插入的位置\n");
scanf("%d %d",&temp,&item);
iStatus = ListInsert(&L, temp, item);
printf("插入数据,打印链表:\n");
display(L);
printf("请输入插入的位置\n");
scanf("%d %d",&temp,&item);
iStatus = ListInsert(&L, temp, item);
printf("插入数据,打印链表:\n");
display(L);
printf("请输入插入的位置\n");
scanf("%d %d",&temp,&item);
iStatus = ListInsert(&L, temp, item);
printf("插入数据,打印链表:\n");
display(L);
printf("请输入删除的位置\n");
scanf("%d",&temp);
iStatus = ListDelete(&L, temp, &e);
printf("删除元素: 删除位置为%d,data = %d\n",temp,e);
printf("删除操作之后的,双向链表:\n");
display(L);
printf("请输入你要删除的内容\n");
scanf("%d",&temp);
iStatus = LinkListDeletVAL(&L, temp);
printf("删除指定data域等于%d的结点,双向链表:\n",temp);
display(L);
printf("请输入你要查找的内容\n");
scanf("%d",&temp);
KElementType index = selectElem(L, temp);
printf("在双向链表中查找到数据域为%d的结点,位置是:%d\n",temp,index);
printf("请输入你要更新的结点以及内容\n");
scanf("%d %d",&temp,&item);
iStatus = replaceLinkList(&L, temp, item);
printf("更新结点数据后的双向链表:\n");
display(L);
}
输出结果：
Hello, World!
iStatus = 1
链表创建成功,打印链表:
0 1 2 3 4 5 6 7 8 9
请输入插入的位置
1 66
插入数据,打印链表:
66 0 1 2 3 4 5 6 7 8 9
请输入插入的位置
10 66
插入数据,打印链表:
66 0 1 2 3 4 5 6 7 66 8 9
请输入插入的位置
12 77
插入数据,打印链表:
66 0 1 2 3 4 5 6 7 66 8 77 9
请输入删除的位置
1 66
删除元素: 删除位置为1,data = 66
删除操作之后的,双向链表:
0 1 2 3 4 5 6 7 66 8 77 9
请输入你要删除的内容
删除指定data域等于66的结点,双向链表:
0 1 2 3 4 5 6 7 8 77 9
请输入你要查找的内容
77
在双向链表中查找到数据域为77的结点,位置是:10
请输入你要更新的结点以及内容
1.9 完整代码
//
// main.c
// 005_DoubleLinkedList
//
// Created by 孔雨露 on 2020/4/5.
// Copyright © 2020 Apple. All rights reserved.
//
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int KStatus;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int KElementType;/* KElementType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct KNode{
KElementType data;
struct KNode *prior;
struct KNode *next;
}KNode;
typedef struct KNode * LinkList;
//5.1 创建双向链接
KStatus createLinkList(LinkList *L){
//*L 指向头结点
*L = (LinkList)malloc(sizeof(KNode));
if (*L == NULL) return ERROR;
(*L)->prior = NULL;
(*L)->next = NULL;
(*L)->data = -1;
//新增数据
LinkList p = *L;
for(int i=0; i < 10;i++){
//1.创建1个临时的结点
LinkList temp = (LinkList)malloc(sizeof(KNode));
temp->prior = NULL;
temp->next = NULL;
temp->data = I;
//2.为新增的结点建立双向链表关系
//① temp 是p的后继
p->next = temp;
//② temp 的前驱是p
temp->prior = p;
//③ p 要记录最后的结点的位置,方便下一次插入
p = p->next;
}
return OK;
}
//5.2 打印循环链表的元素
void display(LinkList L){
LinkList temp = L->next;
if(temp == NULL){
printf("打印的双向链表为空!\n");
return;
}
while (temp) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
//5.3 双向链表插入元素
KStatus ListInsert(LinkList *L, int i, KElementType data){
//1. 插入的位置不合法 为0或者为负数
if(i < 1) return ERROR;
//2. 新建结点
LinkList temp = (LinkList)malloc(sizeof(KNode));
temp->data = data;
temp->prior = NULL;
temp->next = NULL;
//3.将p指向头结点!
LinkList p = *L;
//4. 找到插入位置i直接的结点
for(int j = 1; j < i && p;j++)
p = p->next;
//5. 如果插入的位置超过链表本身的长度
if(p == NULL){
return ERROR;
}
//6. 判断插入位置是否为链表尾部;
if (p->next == NULL) {
p->next = temp;
temp->prior = p;
}else
{
//1️⃣ 将p->next 结点的前驱prior = temp
p->next->prior = temp;
//2️⃣ 将temp->next 指向原来的p->next
temp->next = p->next;
//3️⃣ p->next 更新成新创建的temp
p->next = temp;
//4️⃣ 新创建的temp前驱 = p
temp->prior = p;
}
return OK;
}
//5.4 删除双向链表指定位置上的结点
KStatus ListDelete(LinkList *L, int i, KElementType *e){
int k = 1;
LinkList p = (*L);
//1.判断双向链表是否为空,如果为空则返回ERROR;
if (*L == NULL) {
return ERROR;
}
//2. 将指针p移动到删除元素位置前一个
while (k < i && p != NULL) {
p = p->next;
k++;
}
//3.如果k>i 或者 p == NULL 则返回ERROR
if (k>i || p == NULL) {
return ERROR;
}
//4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
LinkList delTemp = p->next;
*e = delTemp->data;
//5. p->next 等于要删除的结点的下一个结点
p->next = delTemp->next;
//6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
if (delTemp->next != NULL) {
delTemp->next->prior = p;
}
//7.删除delTemp结点
free(delTemp);
return OK;
}
//5.5 删除双向链表指定的元素
KStatus LinkListDeletVAL(LinkList *L, int data){
LinkList p = *L;
//1.遍历双向循环链表
while (p) {
//2.判断当前结点的数据域和data是否相等,若相等则删除该结点
if (p->data == data) {
//修改被删除结点的前驱结点的后继指针,参考图上步骤1️⃣
p->prior->next = p->next;
//修改被删除结点的后继结点的前驱指针,参考图上步骤2️⃣
if(p->next != NULL){
p->next->prior = p->prior;
}
//释放被删除结点p
free(p);
//退出循环
break;
}
//没有找到该结点,则继续移动指针p
p = p->next;
}
return OK;
}
//5.6.1 在双向链表中查找元素
int selectElem(LinkList L,KElementType elem){
LinkList p = L->next;
int i = 1;
while (p) {
if (p->data == elem) {
return I;
}
I++;
p = p->next;
}
return -1;
}
//5.6.2 在双向链表中更新结点
KStatus replaceLinkList(LinkList *L,int index,KElementType newElem){
LinkList p = (*L)->next;
for (int i = 1; i < index; i++) {
p = p->next;
}
p->data = newElem;
return OK;
}
void test () {
KStatus iStatus = 0;
LinkList L;
int temp,item,e;
iStatus = createLinkList(&L);
printf("iStatus = %d\n",iStatus);
printf("链表创建成功,打印链表:\n");
display(L);
printf("请输入插入的位置\n");
scanf("%d %d",&temp,&item);
iStatus = ListInsert(&L, temp, item);
printf("插入数据,打印链表:\n");
display(L);
printf("请输入插入的位置\n");
scanf("%d %d",&temp,&item);
iStatus = ListInsert(&L, temp, item);
printf("插入数据,打印链表:\n");
display(L);
printf("请输入插入的位置\n");
scanf("%d %d",&temp,&item);
iStatus = ListInsert(&L, temp, item);
printf("插入数据,打印链表:\n");
display(L);
printf("请输入删除的位置\n");
scanf("%d",&temp);
iStatus = ListDelete(&L, temp, &e);
printf("删除元素: 删除位置为%d,data = %d\n",temp,e);
printf("删除操作之后的,双向链表:\n");
display(L);
printf("请输入你要删除的内容\n");
scanf("%d",&temp);
iStatus = LinkListDeletVAL(&L, temp);
printf("删除指定data域等于%d的结点,双向链表:\n",temp);
display(L);
printf("请输入你要查找的内容\n");
scanf("%d",&temp);
KElementType index = selectElem(L, temp);
printf("在双向链表中查找到数据域为%d的结点,位置是:%d\n",temp,index);
printf("请输入你要更新的结点以及内容\n");
scanf("%d %d",&temp,&item);
iStatus = replaceLinkList(&L, temp, item);
printf("更新结点数据后的双向链表:\n");
display(L);
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
test();
return 0;
}
2. 双向循环链表
2.1 结点定义
双向循环链表的结点定义和双向链表是一样的
双向链表结点定义
//定义结点
typedef struct KNode{
KElementType data;
struct KNode *prior;
struct KNode *next;
}KNode;
2.2 建表
建表过程，实际上就是从一个空表，按照我们给到的数据创建一个非空链表的过程。
如下图定义的是一个空的双向循环链表，带头结点的，头结点的前驱指针prior和后继指针next都指向它自己：
空的双向循环链表
如下图：是上面空链表一次从尾部插入A，B元素后得到的链表，另外我们还可以从首部插入B,A 元素，也可以得到下面的表：
非空的双向循环链表
下面的代码是循环链表创建过程，代码中我们通过尾部插入法，插入0，1，2，3，4，5，6，7，8，9 总共10个元素。
//6.1 双向循环链表初始化
KStatus creatLinkList(LinkList *L){
*L = (LinkList)malloc(sizeof(KNode));
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(KNode));
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;
}
2.3 插入结点
双向循环链表-插入结点
双向循环链表的插入过程如下：
- 先找到要插入的元素的前驱，(如上图我们找到B结点的前驱A，用p指针指向A)
- 新建一个结点赋值为CC，并用临时指针temp指向CC结点：
temp->data = e; - 将结点temp 的前驱结点为p：
temp->prior = p; - 将新建结点temp的后继结点指向p->next：
temp->next = p->next; - 让p的后继指向新结点temp：
p->next = temp; - 判断当前要插入的新结点temp是不是最后一个结点，如果是则：让L的前驱结点指向temp:
(*L)->prior = temp;；如果不是是则将temp节点的下一个结点的前驱为temp 结点：temp->next->prior = temp;
插入结点的代码实现如下：
//6.2 双向循环链表插入元素
/*当插入位置超过链表长度则插入到链表末尾*/
KStatus LinkListInsert(LinkList *L, int index, KElementType e){
//1. 创建指针p,指向双向链表头
LinkList p = (*L);
int i = 1;
//2.双向循环链表为空,则返回error
if(*L == NULL) return ERROR;
//3.找到插入前一个位置上的结点p
while (i < index && p->next != *L) {
p = p->next;
I++;
}
//4.如果i>index 则返回error
if (i > index) return ERROR;
//5.创建新结点temp
LinkList temp = (LinkList)malloc(sizeof(KNode));
//6.temp 结点为空,则返回error
if (temp == NULL) return ERROR;
//7.将生成的新结点temp数据域赋值e.
temp->data = e;
//8.将结点temp 的前驱结点为p;
temp->prior = p;
//9.temp的后继结点指向p->next;
temp->next = p->next;
//10.p的后继结点为新结点temp;
p->next = temp;
//如果temp 结点不是最后一个结点
if (*L != temp->next) {
//11.temp节点的下一个结点的前驱为temp 结点
temp->next->prior = temp;
}else{
(*L)->prior = temp;
}
return OK;
}
2.4 删除结点
双向循环链表-删除结点
循环双链表删除结点的过程如下：
- 1.找到要删除的结点（如上图用temp指针指向要删除的结点B）
- 2.给e赋值要删除结点的数据域：
*e = temp->data; - 3.修改被删除结点的前驱结点的后继指针 图1️⃣：
temp->prior->next = temp->next;(也就B结点的前驱结点A的next指向B结点的后继C) - 4.修改被删除结点的后继结点的前驱指针 图2️⃣:
temp->next->prior = temp->prior;(让B结点的后继结点C的前驱指针指向B结点的前驱A) - 删除结点temp，释放内存：
free(temp);
- 删除结点temp，释放内存：
循环双链表删除结点的实现代码如下：
//6.4 双向循环链表删除结点
KStatus LinkListDelete(LinkList *L,int index,KElementType *e){
int i = 1;
LinkList temp = (*L)->next;
if (*L == NULL) {
return ERROR;
}
//①.如果删除到只剩下首元结点了,则直接将*L置空;
if(temp->next == *L){
free(*L);
(*L) = NULL;
return OK;
}
//1.找到要删除的结点
while (i < index) {
temp = temp->next;
I++;
}
//2.给e赋值要删除结点的数据域
*e = temp->data;
//3.修改被删除结点的前驱结点的后继指针 图1️⃣
temp->prior->next = temp->next;
//4.修改被删除结点的后继结点的前驱指针 图2️⃣
temp->next->prior = temp->prior;
//5. 删除结点temp
free(temp);
return OK;
}
2.5 遍历
//6.3 遍历双向循环链表
KStatus Display(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;
}
2.6 单元测试
void test() {
LinkList L;
KStatus iStatus;
KElementType temp,item;
iStatus = creatLinkList(&L);
printf("双向循环链表初始化是否成功(1->YES)/ (0->NO): %d\n\n",iStatus);
Display(L);
printf("输入要插入的位置和数据用空格隔开：");
scanf("%d %d",&temp,&item);
iStatus = LinkListInsert(&L,temp,item);
Display(L);
printf("输入要删除位置：");
scanf("%d",&temp);
iStatus = LinkListDelete(&L, temp, &item);
printf("删除链表位置为%d,结点数据域为:%d\n",temp,item);
Display(L);
}
输出结果：
Hello, World!
双向循环链表初始化是否成功(1->YES)/ (0->NO): 1
双向循环链表内容: 0 1 2 3 4 5 6 7 8 9
输入要插入的位置和数据用空格隔开：1 88
双向循环链表内容: 88 0 1 2 3 4 5 6 7 8 9
输入要删除位置：1 88
删除链表位置为1,结点数据域为:88
双向循环链表内容: 0 1 2 3 4 5 6 7 8 9
2.7 完整代码
//
// main.c
// 006_DoubleCircularLinkList
//
// Created by 孔雨露 on 2020/4/5.
// Copyright © 2020 Apple. All rights reserved.
//
#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int KStatus;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int KElementType;/* KElementType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct KNode{
KElementType data;
struct KNode *prior;
struct KNode *next;
}KNode;
typedef struct KNode * LinkList;
//6.1 双向循环链表初始化
KStatus creatLinkList(LinkList *L){
*L = (LinkList)malloc(sizeof(KNode));
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(KNode));
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;
}
//6.2 双向循环链表插入元素
/*当插入位置超过链表长度则插入到链表末尾*/
KStatus LinkListInsert(LinkList *L, int index, KElementType e){
//1. 创建指针p,指向双向链表头
LinkList p = (*L);
int i = 1;
//2.双向循环链表为空,则返回error
if(*L == NULL) return ERROR;
//3.找到插入前一个位置上的结点p
while (i < index && p->next != *L) {
p = p->next;
I++;
}
//4.如果i>index 则返回error
if (i > index) return ERROR;
//5.创建新结点temp
LinkList temp = (LinkList)malloc(sizeof(KNode));
//6.temp 结点为空,则返回error
if (temp == NULL) return ERROR;
//7.将生成的新结点temp数据域赋值e.
temp->data = e;
//8.将结点temp 的前驱结点为p;
temp->prior = p;
//9.temp的后继结点指向p->next;
temp->next = p->next;
//10.p的后继结点为新结点temp;
p->next = temp;
//如果temp 结点不是最后一个结点
if (*L != temp->next) {
//11.temp节点的下一个结点的前驱为temp 结点
temp->next->prior = temp;
}else{
(*L)->prior = temp;
}
return OK;
}
//6.3 遍历双向循环链表
KStatus Display(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;
}
//6.4 双向循环链表删除结点
KStatus LinkListDelete(LinkList *L,int index,KElementType *e){
int i = 1;
LinkList temp = (*L)->next;
if (*L == NULL) {
return ERROR;
}
//①.如果删除到只剩下首元结点了,则直接将*L置空;
if(temp->next == *L){
free(*L);
(*L) = NULL;
return OK;
}
//1.找到要删除的结点
while (i < index) {
temp = temp->next;
I++;
}
//2.给e赋值要删除结点的数据域
*e = temp->data;
//3.修改被删除结点的前驱结点的后继指针 图1️⃣
temp->prior->next = temp->next;
//4.修改被删除结点的后继结点的前驱指针 图2️⃣
temp->next->prior = temp->prior;
//5. 删除结点temp
free(temp);
return OK;
}
void test() {
LinkList L;
KStatus iStatus;
KElementType temp,item;
iStatus = creatLinkList(&L);
printf("双向循环链表初始化是否成功(1->YES)/ (0->NO): %d\n\n",iStatus);
Display(L);
printf("输入要插入的位置和数据用空格隔开：");
scanf("%d %d",&temp,&item);
iStatus = LinkListInsert(&L,temp,item);
Display(L);
printf("输入要删除位置：");
scanf("%d",&temp);
iStatus = LinkListDelete(&L, temp, &item);
printf("删除链表位置为%d,结点数据域为:%d\n",temp,item);
Display(L);
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
test();
return 0;
}
网友评论