实验一：第五题循环链表的应用（约瑟夫回环问题）

n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素。

提示：用一个无头结点的循环单链表来实现n个元素的存储。

参考代码：

#include<stdio.h>  //声明
#include<malloc.h>
#define ERROR 0
#define OK 1    //宏定义 oK 相当于 1
typedef  int ElemType; //定义表元素的类型
typedef struct LNode   //线性表的单链表存储
{ElemType data;       //数据元素datastruct LNode *next;   //指向下一个节点的指针next
} LNode,*LinkList;      //定义单链表别名 LinklistLinkList Creat(int t)   //创建长度为 t 的单向循环链表
{int n;    //整型变量LinkList p1,p2,head; p1=(LinkList)malloc(sizeof(LNode));  //分配一个内存，大小是LNode的大小，p2=(LinkList)malloc(sizeof(LNode));  //并将这个内存地址转化为Link型，然后将赋给 p1，p2head = NULL;   //链表为空n = 1;   //从1开始while(n<=t)  // n<=t 循环{p1->data = n;  // n 赋值给p1所指向的数据元素dataif(n==1)    //若 n 等于 1head = p1;  //p1 赋值给headelse        //不等p2->next = p1;  //p1 赋值给p2所指向的nextp2 = p1;  //p1 赋值给p2if(n!=t)  // 若 n 不等于 tp1 = (LinkList)malloc(sizeof(LNode)); //为p1重新分配一个是LNode大小的内存n++;  //自增}p2->next = head;   //将最后一个节点p2的指针指向头节点 headreturn head;    //返回头节点}
LinkList Start(LinkList L,int k)  //start函数，用于找链表中第 K 个节点的位置
{int i;i=1;while(i!=k){L=L->next;  //L 指向下一个节点赋值给 L i++;        //自增，i+1}return L;  //返回该节点的指针}
LinkList Delete(int n,int m,LinkList L)  //Delete函数用于删除每个 m 节点
{int i,j,k;LinkList p;p=L;k=0;while(n>1){j=0;for(i=1+k; i<=n; i++){if((i+1)%m==0)  //i+1对 m 取余{printf("%d ",p->next->data);  // 输出p的下一个的节点.p->next=p->next->next;   // 把 p的下一个的下一个赋给p的下一个.i++;j++;}p=p->next;  // p 的下一个指针赋值给 pk=i%m;      // i 对 m 取余赋值给 K}n=n-j;}printf("%d\\n",p->data);  //输出被删除的节点数据return p;   //返回最后一个节点的指针
}
int main()
{int m,n,k;scanf("%d%d%d",&n,&m,&k); //从输入读入n,m,K三个整数LinkList L,cur;L=Creat(n);     //调用Creat 函数创建一个长度为 n 的单向循环链表cur=Start(L,k); //调用 Start 函数找到第 K 个节点的位置，赋值给 cur 传给Delete函数Delete(n,m,cur); //调用 Delete函数，进行链表节点的删除操作return 0;  //程序退出
}