一，循环链表的概念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
"）;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
"）;return NULL;}if （length（list） <= 0）{printf（"链表已空
"）;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
"）;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
"）;return NULL;}if （length（list） <= 0）{printf（"链表已空
"）;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（"##############遍历################
"）;for （int i = 0; i < length（list）; i++）{Student * student = （Student *）get（list, i）;printf（"name = %s,age = %d
", student->name, student->age）;}//printf（"##############删除################
"）;//for （int i = 0; i < 6; i++）//{//Student * student = （Student *）del（list, length（list）-1）;//printf（"name = %s,age = %d
", student->name, student->age）;//}resetSlider（list）;printf（"##############游标遍历################
"）;for （int i = 0; i < length（list）; i++）{Student * student = next（list）;printf（"name = %s,age = %d
", 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
", t->value）;}return 0;}
本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-01/139296.htm
易网时代-编程资源站