[数据结构与算法] 循环链表（线性表的链式存储）---C语言版

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 循环链表（线性表的链式存储）---C语言版 -> 正文阅读

[数据结构与算法]循环链表（线性表的链式存储）---C语言版

循环链表

特点：表中最后一个结点的指针域指向头结点，整个链表形成一个环。
既然是环的话，那就不难想象，从表中任意一个结点出发都可以找到表中其他结点。
在这里插入图片描述

一、循环单链表

仍旧使用该例子，我们要如何存储用循环单链表实现它呢？

id	name	description
1	史强	最强辅助
2	章北海	我不需要钢印，我是自己思想的主人
3	罗辑	人类不感谢罗辑
4	维德	失去人性，失去很多。失去兽性，失去一切

循环单链表与单链表唯一的区别就是多了一个由尾结点指向头结点的指针。
所以循环链表的操作与单链表基本一致
唯一的差别就是循环的条件不是p或p->next是否为空，而是它们是否等于头指针(p==L或p->next==L)。

循环单链表示例图(含头结点)：
在这里插入图片描述
循环单链表逻辑图(含头结点)：

1、循环单链表定义

步骤一：声明数据元素类型

typedef struct{
    int id;//对应表中的id
    char name[100];//对应表中的姓名
    char description[200];//对应表中的描述
}ElemType;//此处的ElemType是个类型名

步骤二：声明结点

typedef struct CNode{
    ElemType data;//数据域
    struct CNode *next;//指针域
}CNode,*CLinkList;

2、循环单链表操作

与单链表相比，循环单链表有两处操作与单链表不同。
一是：尾结点的指针域指向头结点
二是：遍历时，条件变成了p->next是否为头指针
这里只详细展示两个具体操作

初始化表。构造一个空表。

/*初始化*/
int InitList_CLink(CLinkList *L){
    *L=(CLinkList)malloc(sizeof(CNode));//创建头结点，并让头指针指向头结点
    if (!(*L)) return FALSE;//分配失败
    (*L)->next=(*L);//初始化为头指针
    return TRUE;//初始化成功
}

空表逻辑图:
在这里插入图片描述

求表长

/*求表长*/
int Length_CLink(CLinkList L){
    int i=0;//空表返回0
    CNode *s=L;
    while (s->next!=L){//遍历，直到尾结点，空表不进入循环
        s=s->next;//向后移动一个
        i++;//表长加一
    }
    return i;//返回表长
}

3、含尾指针的循环单链表

有时候在循环单链表中设立尾指针而不设头指针，可以时有些操作简化。
比如合并两个循环单链表时

在这里插入图片描述

二、循环双链表

循环双链表的逻辑图(含头结点)：
在这里插入图片描述

1、循环双链表定义

步骤一：声明数据元素类型

typedef struct{
    int id;//对应表中的id
    char name[100];//对应表中的姓名
    char description[200];//对应表中的描述
}ElemType;//此处的ElemType是个类型名

步骤二：声明结点

typedef struct CDNode{
    ElemType data;//数据域
    struct CDNode *prior;//指针域，指向前驱结点
    struct CDNode *next;//指针域，指向后继结点
}CDNode,*CDLinkList;

2、循环双链表操作

循环双链表与循环单链表唯一的区别就是多了一个指向前驱的指针。
所以循环双链表的操作与循环单链表也基本一致
就是对结点操作时，需要多操作一步，让p->prior指向前驱结点。
这里展示相对于循环单链表有变化的操作。

初始化表。构造一个空表。

/*初始化*/
int InitList_CLink(CDLinkList *L){
    *L=(CDLinkList)malloc(sizeof(CDNode));//创建头结点，并让头指针指向头结点
    if (!(*L)) return FALSE;//分配失败
    (*L)->prior=(*L);//初始化为头指针
    (*L)->next=(*L);//初始化为头指针
    return TRUE;//初始化成功
}

空表逻辑图：
在这里插入图片描述

根据数组创建双链表

1.头插法

/*头插法创建循环双链表*/
int create_HeadInsert(CDLinkList *L,ElemType a[],int n){
 // InitList_CLink(L);
    CDNode *s;//用来指示新创建的结点
    int i;
    for(i=n-1;i>=0;i--){//由于头插法是倒序插入，所以这里我们从数组最后开始遍历
        s=(CDLinkList)malloc(sizeof(CDNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        s->next=(*L)->next;//让该结点指向第一个结点
        (*L)->next->prior=s;//第一个结点的前驱指向该结点
        s->prior=(*L);//该节点的前驱指向头结点
        (*L)->next=s;//让头结点指向该结点
    }
}

2.尾插法

/*尾插法创建循环双链表*/
int create_TailInsert(CDLinkList *L,ElemType a[],int n){
 // InitList_CLink(L);
    CDNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表
    int i;
    for(i=0;i<n;i++){//遍历数组
        s=(CDLinkList)malloc(sizeof(CDNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        r->next=s;//r始终指向链表的尾端，这里将新结点连接到r的后面
        s->prior=r;//该结点的前驱指向r
        r=s;//r移动到链表尾端
    }
    r->next=(*L);//结束时，最后一个结点的指针域赋值为头指针
}

插入操作。在表L中的第i个位置上插入指定元素e。

/*插入*/
int ListInsert_CDLink(CDLinkList *L,int i,ElemType e){
    int j=0;//空表序号为0
    CDNode *p=(*L);//p指向头结点
    CDNode *s;//s用来指示新创建的结点
    while (p->next!=(*L)&&j<i-1){//找到被插入序号的前一个位置
       p=p->next;//向后移动一个
       j++; 
    }
    if(p==(*L)||(i-j)>1) return FALSE;//序号在无效范围内
    s=(CDLinkList)malloc(sizeof(CDNode));//创建一个新结点
    s->data=e;//赋值
    s->next=p->next;//让该结点指向p（插入位置的前一个结点）的下一个结点
    p->next->prior=s;//让p的下一个结点的前驱指向该结点
    s->prior=p;//让该结点的前驱指向p
    p->next=s; //让p指向该结点  
}

删除操作。删除表中L中第i个位置的元素，并用e返回删除的元素。

/*删除*/
int ListDelete_CDLink(CDLinkList *L,int i,ElemType *e){
    int j=0;//空表序号为0
    CDNode *p=(*L);//p指向头结点
    CDNode *q;//q用来指向被删除的结点
    while (p->next!=(*L)&&j<i-1){//找到要被删除结点的前一个结点
        p=p->next;//向后移动一个
        j++;
    }
    if ((p->next)==(*L)||i<1) return FALSE;//序号在无效范围内
    q=p->next;//让q指向被删除的结点
    p->next=q->next;//让p（被删除结点的前一个结点）指向被删除结点的下一个结点，q从链表中断开
    q->next->prior=p;//让删除结点的下一个结点的前驱指向p；
    *e=q->data;//把被删除的结点的值返回
    free(q);//释放该结点
    return TRUE; //删除成功
}

三、循环单链表完整源码

#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0

typedef struct{
    int id;//对应表中的id
    char name[100];//对应表中的姓名
    char description[200];//对应表中的描述
}ElemType;//此处的ElemType是个类型名

typedef struct CNode{
    ElemType data;//数据域
    struct CNode *next;//指针域
}CNode,*CLinkList;

/*初始化*/
int InitList_CLink(CLinkList *L){
    *L=(CLinkList)malloc(sizeof(CNode));//创建头结点，并让头指针指向头结点
    if (!(*L)) return FALSE;//分配失败
    (*L)->next=(*L);//初始化为头指针
    return TRUE;//初始化成功
}

/*头插法创建循环单链表*/
int create_HeadInsert(CLinkList *L,ElemType a[],int n){
 // InitList_CLink(L);
    CNode *s;//用来指示新创建的结点
    int i;
    for(i=n-1;i>=0;i--){//由于头插法是倒序插入，所以这里我们从数组最后开始遍历
        s=(CLinkList)malloc(sizeof(CNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        s->next=(*L)->next;//让该结点指向第一个结点
        (*L)->next=s;//让头结点指向该结点
    }
}
/*尾插法创建循环单链表*/
int create_TailInsert(CLinkList *L,ElemType a[],int n){
 // InitList_CLink(L);
    CNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表
    int i;
    for(i=0;i<n;i++){//遍历数组
        s=(CLinkList)malloc(sizeof(CNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        r->next=s;//r始终指向链表的尾端，这里将新结点连接到r的后面
        r=s;//r移动到链表尾端
    }
    r->next=(*L);//结束时，最后一个结点的指针域赋值为头指针
}

/*求表长*/
int Length_CLink(CLinkList L){
    int i=0;//空表返回0
    CNode *s=L;
    while (s->next!=L){//遍历，直到尾结点，空表不进入循环
        s=s->next;//向后移动一个
        i++;//表长加一
    }
    return i;//返回表长
}

/*插入*/
int ListInsert_CLink(CLinkList *L,int i,ElemType e){
    int j=0;//空表序号为0
    CNode *p=(*L);//p指向头结点
    CNode *s;//s用来指示新创建的结点
    while (p->next!=(*L)&&j<i-1){//找到被插入序号的前一个位置
       p=p->next;//向后移动一个
       j++; 
    }
    if(p==(*L)||(i-j)>1) return FALSE;//序号在无效范围内
    s=(CLinkList)malloc(sizeof(CNode));//创建一个新结点
    s->data=e;//赋值
    s->next=p->next;//让该结点指向p（插入位置的前一个结点）的下一个结点
    p->next=s; //让p指向该结点  
}

/*删除*/
int ListDelete_CLink(CLinkList *L,int i,ElemType *e){
    int j=0;//空表序号为0
    CNode *p=(*L);//p指向头结点
    CNode *q;//q用来指向被删除的结点
    while (p->next!=(*L)&&j<i-1){//找到要被删除结点的前一个结点
        p=p->next;//向后移动一个
        j++;
    }
    if ((p->next)==(*L)||i<1) return FALSE;//序号在无效范围内
    q=p->next;//让q指向被删除的结点
    p->next=q->next;//让p（被删除结点的前一个结点）指向被删除结点的下一个结点，q从链表中断开
    *e=q->data;//把被删除的结点的值返回
    free(q);//释放该结点
    return TRUE; //删除成功
}

/*按位查找*/
int GetElem_CList(CLinkList L,int i,ElemType *e){
    CNode *p=L; //p指向头结点
    int j=0;//空表序号为0
    while (p->next!=L&&j<i){//找到第i个位置
        p=p->next;//向后移动一个
        ++j;
    }
    if(p==L||i<1)  return FALSE; //i不在有效范围内
    *e=p->data; //把第i个结点的值用e返回
    return TRUE;
}

/*按值查找*/
int LocateElem_CList(CLinkList L,ElemType e,int *i){
    CNode *s=L;
    int j=0;//空表序号为0
    while (s->next!=L){//遍历链表
        s=s->next;//向后移动
        j++;//序号加一
        if (s->data.id==e.id){//这里我们只用id来判断元素的值是否相等，假设id唯一
            *i=j;//如果相等，用i返回序号
            return TRUE;//查找成功
        }    
    }
    return FALSE;
}

/*打印*/
void PrintList_CLink(CLinkList L){
    CNode *s=L;
    int i=0;//空表序号为0
    while (s->next!=L)//遍历表
    {
        s=s->next;
        i++;
        printf("第%d行：id=%d,name=%s,description=%s\n",i,s->data.id,s->data.name,s->data.description);
    }
}

/*销毁循环单链表*/
void DestroyCList(CLinkList *L){
    while((*L)->next!=(*L)) {//遍历
    	CNode *p=(*L)->next;
    	(*L)->next=p->next;
    	free(p);
	}
}

int main(){
    CLinkList L;
    int i=InitList_CLink(&L);
    if(i==1){
        printf("初始化成功\n");
    }
    printf("\n");    
///
    ElemType a[4]={
        {1,"史强","最强辅助"},
        {2,"章北海","我不需要钢印，我是自己思想的主人"},
        {3,"罗辑","人类不感谢罗辑"},
        {4,"维德","失去人性，失去很多。失去兽性，失去一切"}
    };  
    //create_HeadInsert(&L,a,4);
    create_TailInsert(&L,a,4);  
    PrintList_CLink(L);
    printf("\n");    
///
    ElemType e={5,"xxx","xxxxxxxxxxxxxxxxxxxx"};
    ListInsert_CLink(&L,5,e); 
    PrintList_CLink(L);
    printf("\n");    
///
    ListDelete_CLink(&L,5,&e);
    PrintList_CLink(L);
    printf("被删除的元素：id=%d,name=%s,description=%s\n",e.id,e.name,e.description);
    printf("\n");    
///
    GetElem_CList(L,4,&e);
    printf("查询到的元素：id=%d,name=%s,description=%s\n",e.id,e.name,e.description);
    printf("\n");    
//
    LocateElem_CList(L,a[2],&i);
    printf("查询到的位序为：%d\n",i);
    printf("\n");    
//
    i=Length_CLink(L);
    printf("表长为：%d\n",i);
    printf("\n");    
//
    DestroyCList(&L);
    PrintList_CLink(L);
}

运行结果：

初始化成功

第1行：id=1,name=史强,description=最强辅助
第2行：id=2,name=章北海,description=我不需要钢印，我是自己思想的主人
第3行：id=3,name=罗辑,description=人类不感谢罗辑
第4行：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切

第1行：id=1,name=史强,description=最强辅助
第2行：id=2,name=章北海,description=我不需要钢印，我是自己思想的主人
第3行：id=3,name=罗辑,description=人类不感谢罗辑
第4行：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切
第5行：id=5,name=xxx,description=xxxxxxxxxxxxxxxxxxxx

第1行：id=1,name=史强,description=最强辅助
第2行：id=2,name=章北海,description=我不需要钢印，我是自己思想的主人
第3行：id=3,name=罗辑,description=人类不感谢罗辑
第4行：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切
被删除的元素：id=5,name=xxx,description=xxxxxxxxxxxxxxxxxxxx

查询到的元素：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切

查询到的位序为：3

表长为：4

四、循环双链表完整源码

#include<stdio.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0

typedef struct{
    int id;//对应表中的id
    char name[100];//对应表中的姓名
    char description[200];//对应表中的描述
}ElemType;//此处的ElemType是个类型名

typedef struct CDNode{
    ElemType data;//数据域
    struct CDNode *prior;//指针域
    struct CDNode *next;//指针域
}CDNode,*CDLinkList;

/*初始化*/
int InitList_CDLink(CDLinkList *L){
    *L=(CDLinkList)malloc(sizeof(CDNode));//创建头结点，并让头指针指向头结点
    if (!(*L)) return FALSE;//分配失败
    (*L)->prior=(*L);//初始化为头指针
    (*L)->next=(*L);//初始化为头指针
    return TRUE;//初始化成功
}

/*头插法创建循环双链表*/
int create_HeadInsert(CDLinkList *L,ElemType a[],int n){
 // InitList_CLink(L);
    CDNode *s;//用来指示新创建的结点
    int i;
    for(i=n-1;i>=0;i--){//由于头插法是倒序插入，所以这里我们从数组最后开始遍历
        s=(CDLinkList)malloc(sizeof(CDNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        s->next=(*L)->next;//让该结点指向第一个结点
        (*L)->next->prior=s;//第一个结点的前驱指向该结点
        s->prior=(*L);//该节点的前驱指向头结点
        (*L)->next=s;//让头结点指向该结点
    }
}
/*尾插法创建循环双链表*/
int create_TailInsert(CDLinkList *L,ElemType a[],int n){
 // InitList_CLink(L);
    CDNode *s,*r=(*L); //s用来指示新创建的结点，r用来移动以连接链表
    int i;
    for(i=0;i<n;i++){//遍历数组
        s=(CDLinkList)malloc(sizeof(CDNode));//创建一个新结点
        s->data=a[i];//为结点赋值
        r->next=s;//r始终指向链表的尾端，这里将新结点连接到r的后面
        s->prior=r;//该结点的前驱指向r
        r=s;//r移动到链表尾端
    }
    r->next=(*L);//结束时，最后一个结点的指针域赋值为头指针
}

/*求表长*/
int Length_CDLink(CDLinkList L){
    int i=0;//空表返回0
    CDNode *s=L;
    while (s->next!=L){//遍历，直到尾结点，空表不进入循环
        s=s->next;//向后移动一个
        i++;//表长加一
    }
    return i;//返回表长
}

/*插入*/
int ListInsert_CDLink(CDLinkList *L,int i,ElemType e){
    int j=0;//空表序号为0
    CDNode *p=(*L);//p指向头结点
    CDNode *s;//s用来指示新创建的结点
    while (p->next!=(*L)&&j<i-1){//找到被插入序号的前一个位置
       p=p->next;//向后移动一个
       j++; 
    }
    if(p==(*L)||(i-j)>1) return FALSE;//序号在无效范围内
    s=(CDLinkList)malloc(sizeof(CDNode));//创建一个新结点
    s->data=e;//赋值
    s->next=p->next;//让该结点指向p（插入位置的前一个结点）的下一个结点
    p->next->prior=s;//让p的下一个结点的前驱指向该结点
    s->prior=p;//让该结点的前驱指向p
    p->next=s; //让p指向该结点  
}

/*删除*/
int ListDelete_CDLink(CDLinkList *L,int i,ElemType *e){
    int j=0;//空表序号为0
    CDNode *p=(*L);//p指向头结点
    CDNode *q;//q用来指向被删除的结点
    while (p->next!=(*L)&&j<i-1){//找到要被删除结点的前一个结点
        p=p->next;//向后移动一个
        j++;
    }
    if ((p->next)==(*L)||i<1) return FALSE;//序号在无效范围内
    q=p->next;//让q指向被删除的结点
    p->next=q->next;//让p（被删除结点的前一个结点）指向被删除结点的下一个结点，q从链表中断开
    q->next->prior=p;//让删除结点的下一个结点的前驱指向p；
    *e=q->data;//把被删除的结点的值返回
    free(q);//释放该结点
    return TRUE; //删除成功
}

/*按位查找*/
int GetElem_CDList(CDLinkList L,int i,ElemType *e){
    CDNode *p=L; //p指向头结点
    int j=0;//空表序号为0
    while (p->next!=L&&j<i){//找到第i个位置
        p=p->next;//向后移动一个
        ++j;
    }
    if(p==L||i<1)  return FALSE; //i不在有效范围内
    *e=p->data; //把第i个结点的值用e返回
    return TRUE;
}

/*按值查找*/
int LocateElem_CDList(CDLinkList L,ElemType e,int *i){
    CDNode *s=L;
    int j=0;//空表序号为0
    while (s->next!=L){//遍历链表
        s=s->next;//向后移动
        j++;//序号加一
        if (s->data.id==e.id){//这里我们只用id来判断元素的值是否相等，假设id唯一
            *i=j;//如果相等，用i返回序号
            return TRUE;//查找成功
        }    
    }
    return FALSE;
}

/*打印*/
void PrintList_CDLink(CDLinkList L){
    CDNode *s=L;
    int i=0;//空表序号为0
    while (s->next!=L)//遍历表
    {
        s=s->next;
        i++;
        printf("第%d行：id=%d,name=%s,description=%s\n",i,s->data.id,s->data.name,s->data.description);
    }
}

/*销毁循环双链表*/
void DestroyCDList(CDLinkList *L){
    while((*L)->next!=(*L)) {//遍历
    	CDNode *p=(*L)->next;
    	(*L)->next=p->next;
    	free(p);
	}
}

int main(){
    CDLinkList L;
    int i=InitList_CDLink(&L);
    if(i==1){
        printf("初始化成功\n");
    }
    printf("\n");    
///
    ElemType a[4]={
        {1,"史强","最强辅助"},
        {2,"章北海","我不需要钢印，我是自己思想的主人"},
        {3,"罗辑","人类不感谢罗辑"},
        {4,"维德","失去人性，失去很多。失去兽性，失去一切"}
    };  
   // create_HeadInsert(&L,a,4);
    create_TailInsert(&L,a,4);  
    PrintList_CDLink(L);
    printf("\n");    
///
    ElemType e={5,"xxx","xxxxxxxxxxxxxxxxxxxx"};
    ListInsert_CDLink(&L,5,e); 
    PrintList_CDLink(L);
    printf("\n");    
///
    ListDelete_CDLink(&L,5,&e);
    PrintList_CDLink(L);
    printf("被删除的元素：id=%d,name=%s,description=%s\n",e.id,e.name,e.description);
    printf("\n");    
///
    GetElem_CDList(L,4,&e);
    printf("查询到的元素：id=%d,name=%s,description=%s\n",e.id,e.name,e.description);
    printf("\n");    
//
    LocateElem_CDList(L,a[2],&i);
    printf("查询到的位序为：%d\n",i);
    printf("\n");    
//
    i=Length_CDLink(L);
    printf("表长为：%d\n",i);
    printf("\n");    
//
    DestroyCDList(&L);
    PrintList_CDLink(L);
}

运行结果：

初始化成功

第1行：id=1,name=史强,description=最强辅助
第2行：id=2,name=章北海,description=我不需要钢印，我是自己思想的主人
第3行：id=3,name=罗辑,description=人类不感谢罗辑
第4行：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切

第1行：id=1,name=史强,description=最强辅助
第2行：id=2,name=章北海,description=我不需要钢印，我是自己思想的主人
第3行：id=3,name=罗辑,description=人类不感谢罗辑
第4行：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切
第5行：id=5,name=xxx,description=xxxxxxxxxxxxxxxxxxxx

第1行：id=1,name=史强,description=最强辅助
第2行：id=2,name=章北海,description=我不需要钢印，我是自己思想的主人
第3行：id=3,name=罗辑,description=人类不感谢罗辑
第4行：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切
被删除的元素：id=5,name=xxx,description=xxxxxxxxxxxxxxxxxxxx

查询到的元素：id=4,name=维德,description=失去人性，失去很多。失去兽性，失去一切

查询到的位序为：3

表长为：4