一、单向循环链表基础概念单向循环链表在普通单向链表基础上尾结点的next指针不再置NULL指向链表的头结点形成闭环。 结点数据域 后继指针域。 管理结构体保存头指针、结点计数。优点可以从任意结点出发遍历整个链表访问尾结点时从尾部可以直接回到头部适合环形业务环形队列、时间轮。缺点遍历终止条件不再是NULL而是回到头结点容易死循环不支持随机访问插入删除需要小心处理闭环指针易错。文件说明ring001.h头文件结构体定义 函数声明ring001.c源文件单向循环链表功能实现main_ring.c测试main函数二、头文件 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.c1. create_rlink 创建单向循环链表功能分配管理结构体头指针置NULL计数clen0。 返回成功返回链表指针失败返回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_demovalgrind检测内存泄漏valgrind --leak-checkfull ./ring_demo运行输出示例原始循环链表10 20 30 头插55 10 20 30 尾删5 10 20 删除205 10