从零开始的敲代码生活--数据结构篇（循环链表）

一、单向循环链表基础概念

单向循环链表：在普通单向链表基础上，尾结点的next指针不再置NULL，指向链表的头结点，形成闭环。 结点：数据域 + 后继指针域。 管理结构体保存头指针、结点计数。

优点：

缺点：

二、头文件 ring001.h

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

typedef int Data_t;

//结点
typedef struct rnode
{
Data_t data;
struct rnode *pnext;
}RNode_t;

//循环链表管理结构体
typedef struct rlink
{
RNode_t *phead;
int clen;
}RLink_t;

extern RLink_t *create_rlink();
extern int insert_rlink_head(RLink_t *plink, Data_t data);
extern int insert_rlink_tail(RLink_t *plink, Data_t data);
extern void free_rlink_head(RLink_t *plink);
extern void free_rlink_tail(RLink_t *plink);
extern int free_rlink_all(RLink_t *plink);
extern void show_rlink(RLink_t *plink);
extern RNode_t *search_rlink(RLink_t *plink, Data_t data);
extern int del_by_data_r(RLink_t *plink, Data_t data);

#endif

三、功能实现 ring001.c

1. create_rlink 创建单向循环链表

功能：分配管理结构体；头指针置NULL，计数clen=0。 返回：成功返回链表指针，失败返回NULL。

#include "ring001.h"

RLink_t *create_rlink()
{
RLink_t *plink = malloc(sizeof(RLink_t));
if(plink == NULL)
{
printf("malloc error\\n");
return NULL;
}
plink->phead = NULL;
plink->clen = 0;
return plink;
}

2. insert_rlink_head 头插法

功能：头部插入新结点；空链表新结点自环；非空新结点接在头部，尾结点指向新头；计数++。 返回：0成功，‑1失败。

int insert_rlink_head(RLink_t *plink, Data_t data)
{
if(plink == NULL)
return -1;
RNode_t *pnew = malloc(sizeof(RNode_t));
if(pnew == NULL)
{
printf("malloc error\\n");
return -1;
}
pnew->data = data;

if(plink->clen == 0)
{
//空链表：自己指向自己
pnew->pnext = pnew;
plink->phead = pnew;
}
else
{
//找到尾结点（尾结点pnext == phead）
RNode_t *ptail = plink->phead;
while(ptail->pnext != plink->phead)
{
ptail = ptail->pnext;
}
pnew->pnext = plink->phead;
ptail->pnext = pnew;
plink->phead = pnew;
}
plink->clen++;
return 0;
}

3. insert_rlink_tail 尾插法

功能：尾部插入；空链表自环；非空找到尾结点，新结点接入尾部，新尾指向头结点；计数++。 返回：0成功，‑1失败。

int insert_rlink_tail(RLink_t *plink, Data_t data)
{
if(plink == NULL)
return -1;
RNode_t *pnew = malloc(sizeof(RNode_t));
if(pnew == NULL)
{
printf("malloc error\\n");
return -1;
}
pnew->data = data;

if(plink->clen == 0)
{
pnew->pnext = pnew;
plink->phead = pnew;
}
else
{
RNode_t *ptail = plink->phead;
while(ptail->pnext != plink->phead)
{
ptail = ptail->pnext;
}
ptail->pnext = pnew;
pnew->pnext = plink->phead;
}
plink->clen++;
return 0;
}

4. free_rlink_head 头删

功能：删除头结点；区分只有1个结点、多个结点场景；维护闭环；计数‑‑；空链表直接返回。

void free_rlink_head(RLink_t *plink)
{
if(plink == NULL || plink->clen == 0)
return;
RNode_t *pfree = plink->phead;
if(plink->clen == 1)
{
plink->phead = NULL;
}
else
{
RNode_t *ptail = plink->phead;
while(ptail->pnext != plink->phead)
{
ptail = ptail->pnext;
}
plink->phead = pfree->pnext;
ptail->pnext = plink->phead;
}
free(pfree);
plink->clen–;
}

5. free_rlink_tail 尾删

功能：删除尾结点；结点数为1调用头删；找到倒数第二个结点，修改闭环，释放旧尾。

void free_rlink_tail(RLink_t *plink)
{
if(plink == NULL || plink->clen == 0)
return;
if(plink->clen == 1)
{
free_rlink_head(plink);
return;
}
RNode_t *ppre = plink->phead;
//找倒数第二个结点：ppre->pnext->pnext == phead
while(ppre->pnext->pnext != plink->phead)
{
ppre = ppre->pnext;
}
RNode_t *pfree = ppre->pnext;
ppre->pnext = plink->phead;
free(pfree);
plink->clen–;
}

6. free_rlink_all 销毁整个单向循环链表

功能：循环头删释放全部结点。返回0成功，‑1入参为NULL。

int free_rlink_all(RLink_t *plink)
{
if(plink == NULL)
return -1;
while(plink->clen != 0)
{
free_rlink_head(plink);
}
return 0;
}

7. show_rlink 遍历打印单向循环链表

功能：从phead开始遍历，回到phead停止，不能判NULL。

void show_rlink(RLink_t *plink)
{
if(plink == NULL)
{
printf("link ptr is NULL\\n");
return;
}
if(plink->clen == 0)
{
printf("链表为空\\n");
return;
}
RNode_t *ptmp = plink->phead;
do
{
printf("%d ",ptmp->data);
ptmp = ptmp->pnext;
}while(ptmp != plink->phead);
printf("\\n");
}

8. search_rlink 查找结点

功能：按data查找，找到返回结点地址，找不到返回NULL。

RNode_t *search_rlink(RLink_t *plink, Data_t data)
{
if(plink == NULL || plink->clen == 0)
return NULL;
RNode_t *ptmp = plink->phead;
do
{
if(ptmp->data == data)
{
return ptmp;
}
ptmp = ptmp->pnext;
}while(ptmp != plink->phead);
return NULL;
}

9. del_by_data_r 按值删除第一个匹配结点

功能：删除第一个值匹配结点，区分头、尾、中间结点。返回0成功，‑1失败。

int del_by_data_r(RLink_t *plink, Data_t data)
{
if(plink == NULL || plink->clen == 0)
return -1;
RNode_t *pfind = search_rlink(plink, data);
if(pfind == NULL)
return -1;
if(pfind == plink->phead)
{
free_rlink_head(plink);
}
else
{
//找pfind的前驱
RNode_t *ppre = plink->phead;
while(ppre->pnext != pfind)
{
ppre = ppre->pnext;
}
if(pfind->pnext == plink->phead)
{
//是尾结点
ppre->pnext = plink->phead;
}
else
{
ppre->pnext = pfind->pnext;
}
free(pfind);
plink->clen–;
}
return 0;
}

四、测试main函数 main_ring.c

#include "ring001.h"

int main(void)
{
RLink_t *plink = create_rlink();
if(plink == NULL)
return -1;

insert_rlink_tail(plink,10);
insert_rlink_tail(plink,20);
insert_rlink_tail(plink,30);
printf("原始循环链表：");
show_rlink(plink);

insert_rlink_head(plink,5);
printf("头插5：");
show_rlink(plink);

free_rlink_tail(plink);
printf("尾删：");
show_rlink(plink);

del_by_data_r(plink,20);
printf("删除20：");
show_rlink(plink);

free_rlink_all(plink);
free(plink);
plink = NULL;
return 0;
}

五、编译运行&内存检测

编译

gcc main_ring.c ring001.c -o ring_demo

运行程序

./ring_demo

valgrind检测内存泄漏

valgrind –leak-check=full ./ring_demo

运行输出示例

原始循环链表：10 20 30
头插5：5 10 20 30
尾删：5 10 20
删除20：5 10