首页 > 代码库 > 单向循环链表
单向循环链表
一，循环链表的概念
1.什么是循环链表
所谓的循环链表就是让单向链表的首尾相连，组成一个环状。
2.循环链表的典型应用
约瑟夫环问题。
3.实现循环链表的重点
1，循环链表在插入第一个元素的时候，需要我们将第一元素的指针域指向其自身，也就构成了循环链表。
2，循环链表基于单向链表而生，单是比循环链表多了游标这个概念。要想实现循环链表的插入，删除的关键是考虑头结点问题，因为在头插法方式（往链表的头部插入数据）中，需要将末尾数据元素的指针域指向新插入的节点。将新插入的节点的指针域指向头结点的指针域的指针域，还需要将头结点指向新插入的结点。（插入相同）。
二，循环链表新增概念和功能
1，什么是游标
所谓的游标就是在链表中可以移动的指针，游标初始化一般是指向链表的第一个结点。
2，游标的功能
- 初始化游标
- 移动游标：将移动前的游标所对应得结点返回，并将游标指向下一个数据元素。
- 获取游标：获取当前游标所对应得数据元素
- 删除游标：删除当前游标所对应得数据元素，并将游标指向下一个数据元素。
三，循环链表的实现
1，循环链表的功能
# ifndef CIRCLE_LINK_LIST# define CIRCLE_LINK_LIST/* 业务节点 */typedef void Node;/* 链表节点(被包含) */typedef struct CircleNode{ struct CircleNode * next;}CircleNode;/* 链表 */typedef struct CircleLinkList{ /* 头指针 */ Node * ptr; /* 头结点 */ CircleNode header; /* 游标 */ CircleNode slider; /* 长度 */ int length;}CircleLinkList;/* 创建循环链表 */CircleLinkList * createList();/* 获取链表长度 */int length(CircleLinkList * list);/* 销毁链表 */void destory(CircleLinkList * list);/* 清空链表 */void clear(CircleLinkList * list);/* 判断链表是否为空 */int empty(CircleLinkList * list);/* 插入结点 */void insert(CircleLinkList * list,int pos, Node * node);/* 删除结点 */Node * del(CircleLinkList * list, int pos);/* 获取结点 */Node * get(CircleLinkList * list, int pos);/* 将游标重置指向链表的第一个元素 */void resetSlider(CircleLinkList * list);/* 获取当前游标指向的数据元素 */Node * current(CircleLinkList * list);/* 将游标指向到链表的下一个数据元素并返回当前游标的数据元素 */Node * next(CircleLinkList * list);/* 删除游标，并将游标指向下一个数据元素 */Node * deleteNode(CircleLinkList * list);# endif
2，循环链表的实现
# include<stdio.h># include<stdlib.h># include"CircleLinkList.h"/* 创建循环链表 */CircleLinkList * createList(){ /* 在堆上分配内存 */ CircleLinkList * list = (CircleLinkList *)malloc(sizeof(CircleLinkList)); /* 初始化 */ list->ptr = &list->header; list->header.next = NULL; list->slider.next = NULL; list->length = 0; return list;}/* 获取链表长度 */int length(CircleLinkList * list){ return list->length;}/* 销毁链表 */void destory(CircleLinkList * list){ if (list != NULL) { free(list); }}/* 清空链表 */void clear(CircleLinkList * list){ if (list != NULL) { list->header.next = NULL; list->slider.next = NULL; }}/* 判断链表是否为空 */int empty(CircleLinkList * list){ if (list->length == 0) { return 1; } else { return 0; }}/* 插入结点 */void insert(CircleLinkList * list, int pos, Node * node){ if (list == NULL) { printf("链表为NULL\n"); return; } /* 判断插入位置是否超过链表长度或小于0 */ pos = pos < 0 ? 0 : pos; pos = pos > length(list) ? length(list) : pos; /* 注意：如果在第一个位置插入，则需要遍历到最后一个元素，然后再把最后一个元素的指针域指向第一个 */ /* 将业务节点转换为链表节点 */ CircleNode * _node = (CircleNode *)node; /* 判断是否第一次插入 */ if (length(list) == 0) { list->header.next = _node; _node->next = _node; list->length++; return; } /* 定义posNode结点 */ CircleNode * posNode = list->header.next; /* 判断是否在头部插入 */ if (pos == 0) { /* 将posNode移动到尾部 */ for (int i = 0; i < length(list)-1; i++) { posNode = posNode->next; } /* 将尾部指针指向新节点 */ posNode->next = _node; /* 将新节点指针指向头节点指向的节点 */ _node->next = list->header.next; /* 将头节点指向新节点 */ list->header.next = _node; } else { /* 将posNode移动到pos位置上 */ for (int i = 0; i < pos-1; i++) { posNode = posNode->next; } /* 插入 */ _node->next = posNode->next; posNode->next = _node; } list->length++;}/* 删除结点 */Node * del(CircleLinkList * list, int pos){ if (list == NULL) { printf("链表为NULL\n"); return NULL; } if (length(list) <= 0) { printf("链表已空\n"); return NULL; } /* 判断插入位置是否超过链表长度或小于0 */ pos = pos < 0 ? 0 : pos; pos = pos > length(list) ? length(list) : pos; /* 定义要删除的节点 */ CircleNode * result = NULL; /* 定义posNode结点 */ CircleNode * posNode = list->header.next; /* 判断是否删除头结点 */ if (pos == 0) { /* 移动posNode到pos位置 */ for (int i = 0; i < length(list) - 1; i++) { posNode = posNode->next; } /* 保存要删除的节点 */ result = posNode->next; /* 删除 */ posNode->next = list->header.next->next; list->header.next = list->header.next->next; } else { /* 定义缓存上一个结点 */ CircleNode * previous = posNode; /* 移动posNode到pos位置 */ for (int i = 0; i < pos; i++) { previous = posNode; posNode = posNode->next; } /* 保存要删除的节点 */ result = posNode; /* 删除 */ previous->next = posNode->next; } list->length--; return result;}/* 获取结点 */Node * get(CircleLinkList * list, int pos){ if (list == NULL) { printf("链表为NULL\n"); return NULL; } /* 判断插入位置是否超过链表长度或小于0 */ pos = pos < 0 ? 0 : pos; pos = pos > length(list) ? pos%length(list) : pos; /* 定义头结点 */ CircleNode * header = list->header.next; /* 定义pos结点 */ CircleNode * posNode = header; /* 移动posNode到指定位置 */ for (int i = 0; i < pos; i++) { posNode = posNode->next; } return posNode;}/* 将游标重置指向链表的第一个元素 */void resetSlider(CircleLinkList * list){ list->slider.next = list->header.next;}/* 获取当前游标指向的数据元素 */Node * current(CircleLinkList * list){ return list->slider.next;}/* 将游标指向到链表的下一个数据元素并返回当前游标的数据元素 */Node * next(CircleLinkList * list){ CircleNode * result = list->slider.next; list->slider.next = list->slider.next->next; return result;}/* 删除游标，并将游标指向下一个数据元素 */Node * deleteNode(CircleLinkList * list){ if (list == NULL) { printf("链表为NULL\n"); return NULL; } if (length(list) <= 0) { printf("链表已空\n"); return NULL; } /* 获取当前游标的数据结点 */ Node * node = current(list); /* 将当前游标下移 */ next(list); /* 定义要删除的节点 */ CircleNode * result = NULL; /* 定义posNode结点 */ CircleNode * posNode = list->header.next; /* 将业务节点转换为链表节点 */ CircleNode * _node = (CircleNode *)node; /* 判断是否删除头结点 */ if (_node == list->header.next) { /* 移动posNode到pos位置 */ for (int i = 0; i < length(list) - 1; i++) { posNode = posNode->next; } /* 保存要删除的节点 */ result = posNode->next; /* 删除 */ posNode->next = list->header.next->next; list->header.next = list->header.next->next; } else { /* 定义缓存上一个结点 */ CircleNode * previous = posNode; /* 移动posNode到pos位置 */ while (posNode != _node) { previous = posNode; posNode = posNode->next; } /* 保存要删除的节点 */ result = posNode; /* 删除 */ previous->next = posNode->next; } list->length--; return result;}
3，循环链表的测试
# include<stdio.h># include"CircleLinkList.h"typedef struct Student{ CircleNode next; char name[64]; int age;}Student;int main(){ Student s1 = { NULL,"刘备",56 }; Student s2 = { NULL,"关羽",40 }; Student s3 = { NULL,"张飞",36 }; Student s4 = { NULL,"赵云",34 }; Student s5 = { NULL,"马超",20 }; Student s6 = { NULL,"黄忠",80 }; CircleLinkList * list = createList(); insert(list, length(list), &s1); insert(list, length(list), &s2); insert(list, length(list), &s3); insert(list, length(list), &s4); insert(list, length(list), &s5); insert(list, length(list), &s6); printf("##############遍历################\n"); for (int i = 0; i < length(list); i++) { Student * student = (Student *)get(list, i); printf("name = %s,age = %d\n", student->name, student->age); } //printf("##############删除################\n"); //for (int i = 0; i < 6; i++) //{ // Student * student = (Student *)del(list, length(list)-1); // printf("name = %s,age = %d\n", student->name, student->age); //} resetSlider(list); printf("##############游标遍历################\n"); for (int i = 0; i < length(list); i++) { Student * student = next(list); printf("name = %s,age = %d\n", student->name, student->age); }}
三，约瑟夫环问题
/** 约瑟夫环运作如下：* 1、一群人围在一起坐成环状（如：N）* 2、从某个编号开始报数（如：K）* 3、数到某个数（如：M）的时候，此人出列，下一个人重新报数* 4、一直循环，直到所有人出列，约瑟夫环结束*/# include<stdio.h># include"CircleLinkList.h"typedef struct value { CircleNode next; int value;}value;int main(){ /* 创建循环链表 */ CircleLinkList * list = createList(); /* 从0到9十个学生围成环状 */ value v0 = { NULL,0 }; value v1 = { NULL,1 }; value v2 = { NULL,2 }; value v3 = { NULL,3 }; value v4 = { NULL,4 }; value v5 = { NULL,5 }; value v6 = { NULL,6 }; value v7 = { NULL,7 }; value v8 = { NULL,8 }; value v9 = { NULL,9 }; /* 尾插法 */ insert(list, length(list), &v0); insert(list, length(list), &v1); insert(list, length(list), &v2); insert(list, length(list), &v3); insert(list, length(list), &v4); insert(list, length(list), &v5); insert(list, length(list), &v6); insert(list, length(list), &v7); insert(list, length(list), &v8); insert(list, length(list), &v9); /* 重置游标 */ resetSlider(list); /* 将游标移动到2位置，从第三个人开始报数 */ for (int i = 0; i < 2; i++) { next(list); } /* 将数到4的人删除 */ while (empty(list) == 0) { /* 循环4次 */ for (int i = 0; i < 3; i++) { next(list); } /* 删除当前游标 */ value * t = (value *)deleteNode(list); printf("result = %d\n", t->value); } return 0;}
单向循环链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。