#include<stdio.h>
#include<malloc.h>
//定义结构体
typedef struct LNode
{
int password,num //节点权值和序号
struct LNode *next//递归定义下一个节点
}LNode,*LinkList //结构体的名称和指向它的指针
//创建列表
LinkList creatList_L(int n) //n是人数
{
LinkList p,head,q //定义三个节点类型 p和q都是中间变量
int i=1,key //整型局部变量
//为头结点分配内存 其中sizeof()函数获取数据类型长度
//malloc()函数分配内存大小 (LinkList)是强制类型转化
head=(LinkList)malloc(sizeof(LNode))
p=head//复制头结点
for(i=1i<=ni++) //进入循环赋值
{
//key是每个节点的密码，一共n个节点
scanf("%d",&key)
//p节点赋给q 这是个重复的过程 下一个节点变成了当前的了
q=p
//重新分配内存，也就是清空节点p
p=(LinkList)malloc(sizeof(LNode))
//给p节点的序号和密码赋值
p->num=ip->password=key
//把p节点作为q节点的下一个节点
q->next=p
}//这样一来列表就赋值完毕了
p->next=head->next//这句话没什么用
free(head)//这句也是
//现在的p节点是列表的尾节点 把尾节点的下一个指向头结点
//也就是形成了一个环
head=p->next
//返回头结点
return (head)
}
//输出并删除列表
void ListDelete_L(LinkList L,int key,int n) //为什么叫key呢
{
LinkList p,s
int j=1
//循环输出节点
while(n>0)
{
p=L
//key是人数上限M==key 现在开始循环叫数 叫到M的输出
//并从循环链表中删除
for(j=1j<keyj++)
{s=pp=p->next}
printf("%2d %5d\n",p->num,p->password)
key=p->password
//s是p的上一个节点，现在把s的下一个节点指向p的下一个
s->next=p->next
L=p->next
//释放p节点
free(p)
//链表总数减一，一直到n==0时退出while循环
n--
}
}
void main() //入口函数
{
LinkList s
int n,m
printf("请输入总人数N和上限数M:")
scanf("%d%d",&n,&m)
printf("请输入%d个人的密码:",n)
s=creatList_L(n)//调用创建列表
printf("序号 密码\n")
ListDelete_L(s,m,n)//调用输出并删除列表
}
约瑟夫环问题：length个人围成一圈，分别编号1到length，从1开始报数报到seg的出去，继续报，问最后剩下的是原来的几号？
#include "stdio.h"
#define MAX 20
/*length个人围成一圈，报到seg退出，返回最后留下人的序号(>=1)*/
int JohnsonRing(int length, int seg){
int arr[MAX]
int i, k, n
/*设置每一个人的出局标志：0在列，1退出*/
for(i=0i<lengthi++){
arr[i] = 0
}
i = 0
k = 1
n = length
while(n >1) {
if(arr[i] == 1){/*当前位置的人已退出，移到下一位置 */
i = (i + 1) % length
continue
}
if(k == seg){/*当前位置的人退出*/
arr[i] = 1
n--
printf("%d\n", i+1)
i = (i + 1) % length
k = 1
}
else{/*继续报数*/
k++
i = (i + 1) % length
}
}
for(i=0i<length &&arr[i]==1i++)
return i+1
}
void main()
{
int remain
printf("sequence :\n")
remain = JohnsonRing(10, 7)
printf("remain : %d\n", remain)
}
/*约瑟夫环问题，总共人数为length，从1报数，数到seg者退出，然后继续从1开始报数，直至最后只剩1人为止 */
int JohnsonRing(int length, int seg)
{
int arr[100]
int i, k, n
/*设置每一个人的出局标志：0在列，1退出*/
for(i=0i<lengthi++){
arr[i] = 0
}
i = 0
k = 1
n = length
while(n >1) {
if(arr[i] == 1){/*当前位置的人已退出，移到下一位置 */
i = (i + 1) % length
continue
}
if(k == seg){/*当前位置的人退出*/
arr[i] = 1
n--
printf("%d\n", i+1)
i = (i + 1) % length
k = 1
}
else{/*继续报数*/
k++
i = (i + 1) % length
}
}
for(i=0i<length &&arr[i]==1i++)
return i+1
}
void main()
{
int remain
int m, n
m = 6
n = 3
printf("出局顺序 :\n")
remain = JohnsonRing(m, n)
printf("最后的剩余者 : %d\n", remain)
}
