Question

约瑟夫环 数据结构

大神的代码 求注释，尤其是中间要求输入人序号的那段。。看不懂。。。TOT
好像运行之后没有最后剩余的人的编号。求加。。。
作业描述：
从键盘输入人数N（N<50）及N个人的编号（整型），正向建立循环链表；
输出循环链表各结点的值；
输入开始报数的人的编号S及间隔的个数M；
在循环链表中查找到编号为S的结点；
从1开始向后报数，将报M的人（结点）从循环链表中删除，并输出该人的编号；
从刚才被删除人的下一个人开始重复步骤5，直至最后只剩下一个人为止；
输出最后剩余的人的编号。

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}
LNode,*LinkList;
LinkList look(LNode *p,int e)
{
LNode *p3;
p3=(LNode *)malloc(sizeof(LNode));
if(!p3) exit(1);
p3=p;
while(p3->next!=p&&p3->data!=e) p3=p3->next;
if(p3->next==p&&p3->data!=e)
{
printf("no exist ,enter again\n");
scanf("%d",&e);
look(p,e);
}
return (p3);
}
int main()
{
int x,s,y,i;
printf("please enter the number of people:2<=x<=50\n");
scanf("%d",&x);
while(x<=2||x>=50)
{
printf("out of range ,enter again\n");
scanf("%d",&x);
}
printf("enter each people's number\n");
LinkList head=(LNode *)malloc(sizeof(LNode));
LNode *p1,*p2;
p1=head;
for(i=1;i<=x;i++)
{
p1->next=(LNode *)malloc(sizeof(LNode));
scanf("%d",&s);
p1=p1->next;
p1->data=s;
p1->next=head->next;
}
p1=head->next;
for(i=1;i<=x;i++)
{
printf("%d ",p1->data);
p1=p1->next;
if(i%10==0) printf("\n");
}
printf("please enter the interval number\n");
scanf("%d",&y);
while(y<1)
{
printf("insignificance,erter again\n");
scanf("%d",&y);
}
printf("enter the first number\n");
scanf("%d",&s);
p1=look(head->next,s);
while(p1->next!=p1)
{
int j=1;
while(j<y-1)
{
p1=p1->next;
j++;
}
p2=p1->next;
p1->next=p2->next;
printf("%d ",p2->data);
free(p2);
p1=p1->next;
}
printf("OK!\n");
return 0;
}

Answer 1

你看看这个如何
#include <stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;
void Create(LinkList &L,int n)
{//创建不带头结点的循环链表，从1开始自动编号
int i;
LinkList p,q;
for(i=1;i<=n;i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;//编号
if(L==NULL)L=q=p;
else
{
q->next=p;
q=p;
}
}
q->next=L;//构成循环链表
}
void Joseph(LinkList &L,int n,int s,int m)
{//解约瑟夫环，输出出局序列
int i=1,j=1;//j表示报数号
LinkList p=L,q;
printf("出局人的编号序列：\n");
while(i++<s)p=p->next;//移动到开始报数的编号结点
i=1;
while(n>0)
{
if(j==m-1)//报数到m-1时，准备删除下个结点（即报数到m的人）
{
q=p->next;//q所指的结点即是要删除的
printf("%d\t",q->data);
if(i++%10==0)printf("\n");//每行输出10个数据
p->next=q->next;//删除结点（出局）
free(q);
p=p->next;j=1;//重新开始报数
n--;
}
else
{
j++;
p=p->next;
}
}
printf("\n");
}
void main()
{
LinkList L=NULL;
int N,s,m;//总人数N、开始报数的编号s和出局所报的数字m
printf("输入N,s,m:\n");
scanf("%d%d%d",&N,&s,&m);
Create(L,N);
Joseph(L,N,s,m);
}

Answer 2

本人感觉你上面的这段代码不太好，main()函数代码太多了，main()应该只是一个测试功能，请你参考下面的代码：
//用循环链表求解约瑟夫的问题
#include"stdio.h"
#include"malloc.h"
typedef int DataType;
typedef struct node{
DataType data;
struct node *next;
}LNode,*LinkList;
//创建一个链表结构，返回指针
LinkList Creat_LinkList(int n)
{
LinkList H,P,Q;
H=(LinkList)malloc(sizeof(LNode));
H->data=1;
Q=H;
for(int i=2;i<=n;i++){
P=(LinkList)malloc(sizeof(LNode));
P->data=i;
Q->next=P;
Q=P;
}
Q->next=H;
return H;
}
//求约瑟夫问题函数，s为起始位置，m为报数个数
int josephus_LinkList(LinkList josephus_Link,int s,int m)
{
LinkList p,q;
q=josephus_Link;
for(int i=1;i<s;i++)//找到s的位置
q=q->next;
p=q;
while(q!=q->next){//判断是不是只有一个结点了!!!
for(int j=1;j<m;j++){
q=p;
p=p->next;
}
printf("%d ",p->data);
q->next=p->next;
free(p);
q=q->next;
p=q;
}
printf("%d\n",q->data);
free(q);
return 1;
}
int main()
{
int n,a,b;
printf("输入参加约瑟夫问题的人数:");
scanf("%d",&n);
LinkList josephus=Creat_LinkList(n);
printf("输入起始的位置:");
scanf("%d",&a);
printf("输入相隔的人数:");
scanf("%d",&b);
if(josephus_LinkList(josephus,a,b))
printf("游戏结束 !!!");
else
printf("游戏出现问题!!!");
return 0;
}
欢迎采纳

Answer 3

　　从键盘输入人数N（N<50）及N个人的编号（整型），正向建立循环链表；
输出循环链表各结点的值；
输入开始报数的人的编号S及间隔的个数M；
在循环链表中查找到编号为S的结点；
从1开始向后报数，将报M的人（结点）从循环链表中删除，并输出该人的编号；
从刚才被删除人的下一个人开始重复步骤5，直至最后只剩下一个人为止；
输出最后剩余的人的编号。

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}
LNode,*LinkList;
LinkList look(LNode *p,int e)
{
LNode *p3;
p3=(LNode *)malloc(sizeof(LNode));
if(!p3) exit(1);
p3=p;
while(p3->next!=p&&p3->data!=e) p3=p3->next;
if(p3->next==p&&p3->data!=e)
{
printf("no exist ,enter again\n");
scanf("%d",&e);
look(p,e);
}
return (p3);
}
int main()
{
int x,s,y,i;
printf("please enter the number of people:2<=x<=50\n");
scanf("%d",&x);
while(x<=2||x>=50)
{
printf("out of range ,enter again\n");
scanf("%d",&x);
}
printf("enter each people's number\n");
LinkList head=(LNode *)malloc(sizeof(LNode));
LNode *p1,*p2;
p1=head;
for(i=1;i<=x;i++)
{
p1->next=(LNode *)malloc(sizeof(LNode));
scanf("%d",&s);
p1=p1->next;
p1->data=s;
p1->next=head->next;
}
p1=head->next;
for(i=1;i<=x;i++)
{
printf("%d ",p1->data);
p1=p1->next;
if(i%10==0) printf("\n");
}
printf("please enter the interval number\n");
scanf("%d",&y);
while(y<1)
{
printf("insignificance,erter again\n");
scanf("%d",&y);
}
printf("enter the first number\n");
scanf("%d",&s);
p1=look(head->next,s);
while(p1->next!=p1)
{
int j=1;
while(j<y-1)
{
p1=p1->next;
j++;
}
p2=p1->next;
p1->next=p2->next;
printf("%d ",p2->data);
free(p2);
p1=p1->next;
}
printf("OK!\n");
return 0;
}