单向循环链表

循环链表和单链表的区别

1. 表中最后结点的指针不是NULL，而是改为指向头结点，从而整个链表形成了一个环。

2. 循环单链表中没有指针域为NULL的结点，故判空条件为判断 *A （表尾节点） *A 的next是否为头指针

3. 空表：if(A->next == H) { 空表 }

循环链表的特点

• 循环单链表插入，删除算法于单链表几乎一样

正是因为循环单链表是一个“环”，在任何位置插入和删除操作都是等价的，无须判断是否是表全。循环链表可以从任意一个结点开始遍历整个链表，循环链表不设头指针而仅设尾指针，若只设置尾指针A，A->next即为头指针，对表头，表尾进行操作都只要O(n).

• 关于两个循环链表合并为一个循环链表
  

双向循环链表——概念

在单链表L中，查找ai的后继Next(L，a;)，耗时仅为O(1)，因为取ai后继指针即可。
但查找ai的直接前驱Prior(L，ai);则需从链表的头指针开始，找到结点ai前一结点即是。故运算Prior(L，ai)依赖表长n，耗时为O(n)。另外，若链表中有一指针值被破坏，则整个链表脱节。这是单链表的不足

为此，引入双向链表。先定义双向链表中的结点:

其中，data和next同单链表，增加一指针域prior，其指向本结点的直接前驱。
结点描述:

typedef int data_t; 
typedef struct dnode_t
{ 
        data_tdata;
        struct dnode_t *prior;
        struct dnode_t *next;
}dlinknode_t , *dlinklist_t;

• 表L=(a0·····an-1)(设n=2) 的双向循环链表如图：
  
  设p为链表中某结点的指针，有对称性：

  (p->prior)->next = p =(p->next)->prior

• 双向链表的查找等运算基本上和单链表类似。
• 在双向循环链表中，某结点 *p 为尾结点时，p->next == H,当循环双链表尾空表时，某头结点的prior域和next域都等于H

下面我们学习一下双向循环链表的插入和删除运算

1. 双向循环链表——插入

插入： 即实现在链表L的第i结点前插入一结点x的运算，如图

① q->prior = p->prior;
② (p->prior)->next = q;
③ q->next = p;
④ p->prior=q;

• 算法思路：
  调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在，申请一q结点，存入元素x，然后修改指针，将q结点插入p结点之前。
  此算法时间复杂度主要算在查找算法getlist(L,i);上，故T(n)=O(n);

2. 双向循环链表——删除

删除： 即实现删除链表L的第i结点 的运算，如图

• 算法思路：
  调用查找算法Getlist(L,i);,获取结点ai的指针p，若p存在，则修改指针删除

概念我们了解了，接下来我们要去实现双向链表的操作。

双向链表的插入创建

文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;


extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
#endif

文件二：dlist.c 插入创建双向链表

#include"dlist.h"

//创建双向链表
dlistnode *dlist_create(){
   dlistnode *H,*p,*r;
   int num;

   if(( H =(dlistnode *)malloc(sizeof(dlistnode))) == NULL){
	puts("malloc failed");
	return NULL;
   }
   //建立空双向链表
   H->prior = H;   //头结点前驱后继都指向自己
   H->next = H;    
   r = H;          //指针r 指向头结点
   //用户输入
   while(1) {
       puts("please input(-1 exit):");
       scanf("%d",&num);
       if(num == -1){
	       puts("-1 exit");
	       break;
       }

       if((p = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
	puts("malloc failed");
	return NULL;
       }
       //新节点赋值
       p->data = num;
       
       //插入双向链表
       p->prior = r;
       p->next = r->next;
       r->next = p;
       H->prior = p;
       r = p;

   } 
   return H;
}

//遍历链表并输出链表数据
void dlist_show(dlistnode *H){

   dlistnode *p;
   p = H->next;

   while(p != H){
       printf("%d ",p->data);
       p=p->next;
   }
   puts("");
}

文件三：test.c 插入创建双向链表

#include"dlist.h"


int main(){

   dlistnode *H;

   H=dlist_create();

   dlist_show(H);

   return 0;
}

双向链表——查找

查找：getlist(L,i);提供要查找结点ai的编号，返回指向该结点ai的指针

结点个数 n=3; i的范围【0，n-1】

文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;

extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
extern dlistnode *dlist_get(dlistnode *H,int pos)；
#endif

文件二：dlist.c 按位查找双向链表

dlistnode *dlist_get(dlistnode *H,int pos){
    int i =-1;
    dlistnode *p = H;

    if(pos < 0){
        puts("pos < 0,invalid");
        return NULL;
    }
    
    while(i < pos){
	   p = p->next;
	   i++;
	   if(p == H){
	       puts("pos is invalid");
	       return NULL;
	   }
    }
    return p;
}

文件三：test.c 用户输入按位查找双向链表

#include"dlist.h"


int main(){

   dlistnode *H,*p;
   int pos;

   H=dlist_create();

   dlist_show(H);
   
   //用户输入按位查找
   while(1){
      puts("input pos");
      scanf("%d",&pos);
      p =  dlist_get(H,pos);
      if(p){
         printf("%d \n",p->data);
      }
   }
   return 0;
}

双向链表——插入

插入： 即实现在链表L的第i结点前插入一结点x的运算，如图

• 算法思路：
  调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在，申请一q结点，存入元素x，然后修改指针，将q结点插入p结点之前。
  此算法时间复杂度主要算在查找算法getlist(L,i);上，故T(n)=O(n);

文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;

extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
extern dlistnode *dlist_get(dlistnode *H,int pos);
extern int dlist_insert(dlistnode *H , int value ,int pos);
#endif

文件二：dlist.c 按位插入双向链表

int dlist_insert(dlistnode *H , int value ,int pos){
	dlistnode *p,*q;

	p = dlist_get(H,pos);
	if(p == NULL){
            return -1;
	}
        
        if((q = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
	   puts("malloc failed");
	   return -1;
        } 
	q->data = value;

	q->prior = p->prior;
	q->next = p;
	p->prior->next = q;
	q->prior = q;

	return 0;
}

文件三：test.c 用户输入按位插入双向链表

#include"dlist.h"


int main(){

   dlistnode *H;
   int pos;

   H=dlist_create();

   dlist_show(H);
   
   //用户输入按位查找
     while(1){
      puts("input pos");
      scanf("%d",&pos);
      
      dlist_insert(H,100,pos);
      dlist_show(H);
      }
   return 0;
}

双向链表——删除

删除： 即实现删除链表L的第i结点 的运算，如图

 p->prior->next = p->next;
 p->next->prior = p-prior;

• 算法思路：
  调用查找算法Getlist(L,i);,获取结点ai的指针p，若p存在，则修改指针删除
  文件一：dlist.h 插入创建双向链表

#ifndef __DLIST_H__
#define __DLIST_H__
#include<stdio.h>
#include<stdlib.h>

typedef struct node{

   int data;
   struct node *prior;
   struct node *next;

}dlistnode;

extern dlistnode *dlist_create();
extern void dlist_show(dlistnode *H);
extern dlistnode *dlist_get(dlistnode *H,int pos);
extern int dlist_insert(dlistnode *H , int value ,int pos);
extern int dlist_delete(dlistnode *H ,int pos);
#endif

文件二：dlist.c 用户输入按位删除双向链表

int dlist_delete(dlistnode *H ,int pos){
    dlistnode *p;

    p = dlist_get(H,pos);
    if(p == NULL){
            return -1;
    }
    
    p->prior->next = p->next;
    p->next->prior = p-prior;

    free(p);
    p=NULL;
    return 0;
}

文件三：test.c 用户输入按位删除双向链表

#include"dlist.h"

int main(){

   dlistnode *H;
   int pos;

   H=dlist_create();

   dlist_show(H);

    while(1){
      puts("input pos");
      scanf("%d",&pos);
      
      dlist_delete(H,pos);
      dlist_show(H);
    }
   return 0;
}

-----------------------------------------很棒学习完了数据结构的 双向循环链表--------------------------------------------------

--------------------------------------------------------[下期预告：线性表的应用举例]------------------------------------------------------

【数据结构算法】③、双向链表和双向循环链表的实现

数据结构与算法 总共分为19个系列
①、数据结构与算法[基础]+线性结构部分内容篇
②、单向循环链表的创建插入删除实现篇
③、双向链表和双向循环链表的实现篇

⭐️本文章知识点大纲

双向链表

0. 双向链表的介绍
1. 双向链表的介绍-创建遍历
2. 双向链表的插入
3. 双向链表的删除
4. 双向链表的删除指定元素
5. 双向链表的查找指定元素

---

双向循环链表

0. 双向循环链表的介绍
1. 双向循环链表的介绍-创建遍历
2. 双向循环链表的插入
3. 双向循环链表的删除

---

⭐️双向链表

①、线性表 - 双向链表的介绍

双向链表(创建/插入/删除/查找/替换)

双向链表的特点
每个节点都包含3个部分

1. 包含前驱 prior
2. 包含数据源
3. 包含后继 指针域

1.1 流程图 - 双向链表 - 单个节点 结构

1.2 流程图 - 双向链表 整个链表

双向链表 带有头节点 和不带有头节点的结构图
链表最好不要使用头插法。因为头插法插入的数据是倒序的

---

②、线性表 - 双向链表 创建

2.1 流程图 - 双向链表 创建

双向链表的 头节点的前驱不是L,而是空,后继也是空。因为我们不知道后继有没有东西。所以后继也要是空的。

2. 🌰案例 - 双向链表 - 创建、遍历 代码实现

#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 Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *prior; // 前驱
    struct Node *next; // 后继
}Node;

typedef struct Node * LinkList;

//5.1 创建双向链接
Status createLinkList(LinkList *L){
    
    //*L 指向头结点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;
    
    //新增数据
    LinkList p = *L; // 创建一个临时变量 指向*L
    // 使用尾插法插入数据 插入10个数据    
    for(int i=0; i < 10;i++){
        
        //1.创建1个临时的结点
        LinkList temp = (LinkList)malloc(sizeof(Node));
        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){
    
    //  不需要把头结点打印出来 
    // 所以拿到L->next 也就是头结点的下一个结点
    LinkList temp = L->next;
    // 判断打印的结点是不是空
    if(temp == NULL){
        printf("打印的双向链表为空!\n");
        return;
    }
    // 循环打印
    while (temp) {
        printf("%d  ",temp->data);
        temp = temp->next;
    }
    printf("\n");
    
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    Status iStatus = 0;
    LinkList L;
    int temp,item,e;
    
    iStatus =  createLinkList(&L);
    printf("iStatus = %d\n",iStatus);
    printf("链表创建成功,打印链表:\n");
    display(L);

    return 0;
}

---

③、线性表 - 双向链表 插入

比如我要往AB中间插入一个C
也就是ACB
那么步骤流程就是
1.1 先找到A结点§
2.1 创建C结点 (temp)
3.1 把B(p-next)的前驱指向C .
3.2 把C结点(temp)的后继(next)指向B(p-next)。
4.1 把A的后继(next)指向C(temp).
4.2 把C结点的前驱指向A

如果插入到尾部的时候情况
比如从ABC
插入一个D
那么步骤就是
1.1 先找到C结点§
2.1 创建D结点(temp)(后继一开始就是空的)
3.1 先把D的前驱 指向 C
3.2 把C的后继(p->next)(之前是空的) 指向D

3.1 流程图 - 双向链表 插入

3.2 结果图 - 双向链表 插入

3. 🌰案例 - 双向链表 - 插入 代码实现

//5.3 双向链表插入元素
Status ListInsert(LinkList *L, int i, ElemType data){
    // 不能插入到头结点 头结点相当于牵头人
    //1. 插入的位置不合法 为0或者为负数
    if(i < 1) return ERROR;
    
    //2. 新建结点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    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;
}

---

④、线性表 - 双向链表 删除

比如我要往ABC中间删除B
删除的步骤

1. 先找到A(变量p)
2. 创建一个临时变量(delTemp)记录B
3. 用A(变量p)的后继(next)
   指向
   B的前驱(deltemp的prior)的
   指向
   C的前驱(C的prior)
4. 然后C的前驱指向A的后续
5. 把B结点删除 释放掉

4.2 结果图 - 双向链表 删除

4. 🌰案例 - 双向链表 - 删除 代码实现

//5.4 删除双向链表指定位置上的结点
// e表示删除的元素 可以返回回去
Status ListDelete(LinkList *L, int i, ElemType *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;
    
}

---

⑤、线性表 - 双向链表 删除指定元素

比如我从一个双向链表1-10
我要删除5(变量p)
步骤

1. 找到p的前驱(prior) - 也就是4的(p->prior)
2. 找到4的next 指向 6的前驱
   (p->next->prior)
3. 没有找到 那么就将p=p->next

5. 🌰案例 - 双向链表 - 删除指定元素 代码实现

//5.5 删除双向链表指定的元素
Status 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;
    
}

---

⑥、线性表 - 双向链表 查找元素

6. 🌰案例 - 双向链表 - 删除指定元素 代码实现

//5.6.1 在双向链表中查找元素
int selectElem(LinkList L,ElemType elem){
    
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == elem) {
            return i;
        }
        
        i++;
        p = p->next;
    }
    
    return  -1;
}

---

⑦、线性表 - 双向链表 更新

7. 🌰案例 - 双向链表 - 更新 代码实现

//5.6.2 在双向链表中更新结点
Status replaceLinkList(LinkList *L,int index,ElemType newElem){
    LinkList p = (*L)->next;
    
    for (int i = 1; i < index; i++) {
        p = p->next;
    }
    
    p->data = newElem;
    return OK;
}

---

💡⑧、双向链表end - 双向链表 - 综合代码

#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 Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

//5.1 创建双向链接
Status createLinkList(LinkList *L){
    
    //*L 指向头结点
    *L = (LinkList)malloc(sizeof(Node));
    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(Node));
        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 双向链表插入元素
Status ListInsert(LinkList *L, int i, ElemType data){
    
    //1. 插入的位置不合法 为0或者为负数
    if(i < 1) return ERROR;
    
    //2. 新建结点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    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 删除双向链表指定位置上的结点
// e表示删除的元素 可以返回回去
Status ListDelete(LinkList *L, int i, ElemType *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 删除双向链表指定的元素
Status 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,ElemType 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 在双向链表中更新结点
Status replaceLinkList(LinkList *L,int index,ElemType newElem){
    LinkList p = (*L)->next;
    
    for (int i = 1; i < index; i++) {
        p = p->next;
    }
    
    p->data = newElem;
    return OK;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    Status 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);
    ElemType 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);

    return 0;
}

---

⭐️双向循环链表

①、线性表 - 双向循环链表的介绍

双向循环链表特点是:
最后一个结点的next指向链表的指针(*L)

1.1 流程图 - 双向循环链表 - 整个链表结构

---

②、线性表 - 双向循环链表 创建

2. 🌰案例 - 双向循环链表 创建 代码实现

//6.1 双向循环链表初始化
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;
   
}

---

③、线性表 - 双向循环链表 遍历

3. 🌰案例 - 双向循环链表 遍历 代码实现

//6.3 遍历双向循环链表
Status 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;
}

---

④、线性表 - 双向循环链表 插入

双向循环链表我们没有创建头结点
双向循环我们创建了头结点
因为有了头结点
我们插入的时候 不需要判断是不是要添加到首元节点
所以我们根本就不需要去判断*L 头部
尾部还是要判断的

🌰说明步骤
比如在AB之间插入C
A表示(变量p)
C表示(temp)

1. 先判断索引值的异常 也就是在链表哪个位置进行插入
2. 先找到 A(变量p)
3. 创建C结点(temp)
4. 将C结点的(next) 指向 B(p->next)
5. 将B结点（p->next）的前驱(p->next->prior)指向C
6. 将A结点(变量p)next 指向C结点(temp)
7. 将C结点的前驱(temp->prior) 指向A结点(变量p)

4.1 结果图 - 双向循环链表 插入

4. 🌰案例 - 双向循环链表 插入 代码实现

//6.2 双向循环链表插入元素
/*当插入位置超过链表长度则插入到链表末尾*/
Status LinkListInsert(LinkList *L, int index, ElemType 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(Node));
    
    //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个结点 包含头节点)

5.1 结果图 - 双向循环链表 删除

5. 🌰案例 - 双向循环链表 删除 代码实现

//6.4 双向循环链表删除结点
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;
    }
    
    //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;
    
}

---

💡⑤、双向循环链表end - 双向链表 - 综合代码

#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 Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

//6.1 双向循环链表初始化
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;
   
}

//6.2 双向循环链表插入元素
/*当插入位置超过链表长度则插入到链表末尾*/
Status LinkListInsert(LinkList *L, int index, ElemType 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(Node));
    
    //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 遍历双向循环链表
Status 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 双向循环链表删除结点
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;
    }
    
    //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;
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    LinkList L;
    Status iStatus;
    ElemType 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);

    
    return 0;
}

目录

前言

 一、双向循环链表

循环结构

1.双向循环链表头文件及函数声明

2.初始化

1.结点构造

2.初始化函数

3.结点申请

 4.数据插入

1.按位置插入

2.尾插

3.头插

 5.查找

 6.数据删除

1.按位置删除

 2.按值删除

3.尾删 

4.头删 

7.清空与销毁 

1.清空

2.销毁

8.双向循环链表源文件及整体函数实现 

总结

---

前言

这次我们将学习双向循环链表，首先了解双向链表和循环链表的定义和讲解。

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，是单链表的进阶，比单链表的结点结构多出一个指向前驱的指针域，如下图所示：

循环链表是一种链式储存结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。方法是将尾结点中的指针域进行使用，指向首结点，如下图所示：

双向循环链表即是将上述二者联合起来使用，以达到完成各类工作的效用，在以后大多数链表结构的使用中，我们都会选择双向循环链表。

---

 一、双向循环链表

循环结构

 双向循环链表的循环方式是其尾结点的后继指针指向头结点(表头)，而头结点的前置指针指向尾结点，达到双向循环的目的，这样不仅使得对链表尾部的操作更为简单，也减少了对NULL指针的引用。

1.双向循环链表头文件及函数声明

新建头文件"dclist.h"(double circle list)对链表函数声明进行保存，方便我们后期查看及使用

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<ctype.h>
#include<stdlib.h>

typedef int Element;

typedef struct DNode
{
	Element data;
	DNode* next;
	DNode* prev;
}DNode, * PDNode;

//初始化链表
void InitList(PDNode plist);

//购买结点
PDNode BuyNode();

//头插
bool Push_Front(PDNode plist, Element val);

//尾插
bool Push_Back(PDNode plist, Element val);

//按位置插
bool Insert_Pos(PDNode plist, int pos, Element val);

//头删
bool Pop_Front(PDNode plist);

//尾删
bool Pop_Back(PDNode plist);

//按位置删
bool Erease_Pos(PDNode plist, int pos);

//按值删
bool Erease_Val(PDNode plist, Element val);

//查找  返回结点地址
PDNode Find(PDNode plist, Element val);

//判空
bool IsEmpty(PDNode plist);

//获取元素个数
int GetSize(PDNode plist);

//打印链表
void Print(PDNode plist);

//清空
void Clear(PDNode plist);

//销毁
void Destroy(PDNode plist);

 

2.初始化

在对使用链表进行数据的储存之前，我们需要进行链表的初始化

1.结点构造

如图所示，带双向循环链表的结点由三部分构成：

1.数据域

2.指针域1：指向后继结点的指针

3.指针域2：指向前置结点的指针

typedef int Element;//如此对数据类型进行改名操作，若要进行修改数据类型操作会更加方便

typedef struct DNode
{
	Element data;
	DNode* next;//后继指针
	DNode* prev;//前置指针
}DNode, * PDNode;

2.初始化函数

与单链表不同的是，在双向循环链表不存在数据时，头结点的指针域不置为NULL，其后继指针与前置指针都指向头结点本身，以形成最基础的循环形态：

//初始化链表
void InitList(PDNode plist)
{
	assert(plist != NULL);
	plist->next = plist->prev = plist;
}

3.结点申请

因为链表的结构特性，我们需要对结点进行多次申请，为了方便进行其他函数操作，并且为了优化代码，我们将结点的申请封装于一个函数

//购买结点
PDNode BuyNode()
{
	PDNode node = (PDNode)malloc(sizeof(DNode));
	if (node == NULL)
	{
		exit(1);
	}
	memset(node, 0, sizeof(*node));//将申请的结点内存重置，防止数据残留
	return node;
}

 4.数据插入

双向循环链表存在多个指针指向的断开和重新指向，我们在此先进行分析和讲解，如下图所示：

 

按照正常逻辑，我们再重新指定指针指向时，首先需要打破原有的指针指向，即上图中红叉部分，但实际编写程序中，我们会直接修改指针的指向，从而在代码中只会体现重新指向的过程。

在图中，已经标注出4个指针指向的修改，首先，我们应该对新申请的结点中指针(即图中34箭头的指向)进行指定，因为如果我们先对旧有指针进行修改，那么我们可能会丢失结点的地址信息，从而失去我们已经保存的数据。

其中指针具体的指向修改，我们不用太在意顺序，只需要记住先考虑新节点的指向，后修改旧结点的指向即可，下面的代码中，我们将采用4321的顺序：

1.按位置插入

我们先进行通用插入的实现：

//按位置插
bool Insert_Pos(PDNode plist, int pos, Element val)
{
	assert(plist != NULL);
    //判断插入位置是否合法
	if (pos < 0 || pos > GetSize(plist))
	{
		return false;
	}
	PDNode node = plist;//将结点指针定位至需要插入数据位置之前的结点
	for (int i = 0; i < pos; i++)
	{
		node = node->next;
	}
	PDNode newnode = BuyNode();//申请新节点 
	newnode->data = val;
    //以下为插入步骤
	newnode->next = node->next;//4
	newnode->prev = node;//3
	node->next->prev = newnode;//2
	node->next = newnode;//1
	return true;
}

2.尾插

因为表头的前置指针指向尾结点，所以我们不用像单链表一样进行遍历后才能尾插。

//尾插
bool Push_Back(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode newnode = BuyNode();
	newnode->data = val;
    //插入
	newnode->next = plist;//4
	newnode->prev = plist->prev;//3
    plist->prev = newnode;//2
	plist->prev->next = newnode;//1
	return true;
}

3.头插

直接调用按位置插入，插入位置为0

//头插
bool Push_Front(PDNode plist, Element val)
{
	assert(plist != NULL);
	return Insert_Pos(plist, 0, val);
}

 5.查找

查找与普通链表的查找基本相同，但是在while循环中的结束条件不同，以结点指针是否指向表头来判断

//查找  返回结点地址
PDNode Find(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode node = plist->next;
    //遍历链表查找与val 相同的值
	while (node != plist && node->data != val)
	{
		node = node->next;
	}
	if (plist == node)
	{
		return NULL;
	}
	return node;
}

 6.数据删除

双向循环链表的删除大致与单链表相同，但在两相隔结点的重新链接时需要连结两个指针，即被删除结点的前置结点的后继指针指向被删除结点的后继结点，而后继结点的前置指针指向前置结点

1.按位置删除

//按位置删
bool Erease_Pos(PDNode plist, int pos)
{
	assert(plist != NULL);
	if (pos < 0 || pos >= GetSize(plist) || IsEmpty(plist))
	{
		return false;
	}
	PDNode delnode = plist;
	for (int i = 0; i <= pos; i++)
	{
		delnode = delnode->next;
	}
    //重新连结
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}

 2.按值删除

这里调用了查找函数，找到val值所在的结点

//按值删
bool Erease_Val(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode delnode = Find(plist, val);
	if (delnode == NULL)
	{
		return false;
	}
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}

3.尾删 

同样的，因为表头的前置指针指向尾结点，则可以减少遍历链表所消耗的资源。

//尾删
bool Pop_Back(PDNode plist)
{
	assert(plist != NULL);
	if (IsEmpty(plist))
	{
		return false;
	}
	PDNode delnode = plist->prev;
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}

4.头删 

直接调用按位置删除，删除位置为0

//头删
bool Pop_Front(PDNode plist)
{
	assert(plist != NULL);
	return Erease_Pos(plist, 0);
}

7.清空与销毁 

1.清空

这里我们使用比较简单的方法，一直头删即可，当然这里的尾删也可以使用，消耗资源相同。

//清空
void Clear(PDNode plist)
{
	assert(plist != NULL);
	while (!IsEmpty(plist))
	{
		Pop_Front(plist);
	}
}

2.销毁

调用清空函数，并使链表达到未初始化的状态。

//销毁
void Destroy(PDNode plist)
{
	Clear(plist);
	plist->next = plist->prev = NULL;
}

8.双向循环链表源文件及整体函数实现 

#include "dclist.h"

//初始化链表
void InitList(PDNode plist)
{
	assert(plist != NULL);
	plist->next = plist->prev = plist;
}

//购买结点
PDNode BuyNode()
{
	PDNode node = (PDNode)malloc(sizeof(DNode));
	if (node == NULL)
	{
		exit(1);
	}
	memset(node, 0, sizeof(*node));
	return node;
}

//头插
bool Push_Front(PDNode plist, Element val)
{
	assert(plist != NULL);
	return Insert_Pos(plist, 0, val);
}

//尾插
bool Push_Back(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode newnode = BuyNode();
	newnode->data = val;
	newnode->prev = plist->prev;
	newnode->next = plist;
	plist->prev->next = newnode;
	plist->prev = newnode;
	return true;
}

//按位置插
bool Insert_Pos(PDNode plist, int pos, Element val)
{
	assert(plist != NULL);
	if (pos < 0 || pos > GetSize(plist))
	{
		return false;
	}
	PDNode node = plist;
	for (int i = 0; i < pos; i++)
	{
		node = node->next;
	}
	PDNode newnode = BuyNode();
	newnode->data = val;
	newnode->next = node->next;
	newnode->prev = node;
	node->next->prev = newnode;
	node->next = newnode;
	return true;
}

//头删
bool Pop_Front(PDNode plist)
{
	assert(plist != NULL);
	return Erease_Pos(plist, 0);
}

//尾删
bool Pop_Back(PDNode plist)
{
	assert(plist != NULL);
	if (IsEmpty(plist))
	{
		return false;
	}
	PDNode delnode = plist->prev;
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}

//按位置删
bool Erease_Pos(PDNode plist, int pos)
{
	assert(plist != NULL);
	if (pos < 0 || pos >= GetSize(plist) || IsEmpty(plist))
	{
		return false;
	}
	PDNode delnode = plist;
	for (int i = 0; i <= pos; i++)
	{
		delnode = delnode->next;
	}
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}

//按值删
bool Erease_Val(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode delnode = Find(plist, val);
	if (delnode == NULL)
	{
		return false;
	}
	delnode->prev->next = delnode->next;
	delnode->next->prev = delnode->prev;
	free(delnode);
	delnode = NULL;
	return true;
}

//查找  返回结点地址
PDNode Find(PDNode plist, Element val)
{
	assert(plist != NULL);
	PDNode node = plist->next;
	while (node != plist && node->data != val)
	{
		node = node->next;
	}
	if (plist == node)
	{
		return NULL;
	}
	return node;
}

//判空
bool IsEmpty(PDNode plist)
{
	assert(plist != NULL);
	return (plist->next == plist->prev && plist->next == plist);
}

//获取元素个数
int GetSize(PDNode plist)
{
	assert(plist != NULL);
	PDNode node = plist->next;
	int count = 0;
	while (node != plist)
	{
		node = node->next;
		count++;
	}
	return count;
}

//打印链表
void Print(PDNode plist)
{
	assert(plist != NULL);
	PDNode node = plist->next;
	while (node != plist)
	{
		printf("%d ", node->data);
		node = node->next;
	}
	printf("\n");
}

//清空
void Clear(PDNode plist)
{
	assert(plist != NULL);
	while (!IsEmpty(plist))
	{
		Pop_Front(plist);
	}
}

//销毁
void Destroy(PDNode plist)
{
	Clear(plist);
	plist->next = plist->prev = NULL;
}

---

 

总结

以上为双向循环链表的实现和方法讲解，双向循环链表为比较常用的链表形式，学习并理解双向循环链表会方便以后的学习。