Question

用数据结构的单循环链表写的约瑟夫环（C语言），哪错了？

约瑟夫环 问题描述：约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 测试数据 M的初值为20；n=7，7各人的密码依次为3，1，7，2，4，8，4，首先m值为6（正确出栈顺序为6，1，4，7，2，3，5）
#include<stdio.h>
#include<stdlib.h>

struct LNode
{
int num;
int code;
LNode *next;
};
typedef LNode *LinkList;
void Create(LinkList &L){ //创建头结点
L=(LinkList)malloc(sizeof(LNode));
if(!L) exit(0);
L->next=NULL;
}
void AddToL(LinkList &L){ //加入结点
LinkList p=L,s;
s=(LinkList)malloc(sizeof(LNode));// 生成新结点
if(!s) exit(0);
p->next=s;
p=s;
}
void Delete(LinkList L,int i,int m){ //输出编号后删除结点
int j;
LinkList p=L,q;
for(j=1;j<i;j++,p=p->next);
m=p->code;
printf("%d",p->num);
if(!p->next||j>i-1) // 删除位置不合理
exit(0);
p->num=p->next->num;
p->code=p->next->code;
q=p->next;
p->next=p->next->next;
free(q);
}
main(){
int m,n,i,j;
LinkList p,q,L,s;
printf("请输入m初始值:");
scanf("%d",&m);
printf("请输入人数:");
scanf("%d",&n);
for(i=1;i<=n;i++){
if(i==1)
Create(L);
else
AddToL(L);
printf("请输入第%d个人的密码:",i);
scanf("%d",&(p->code));
p->num=i;
}
p->next=L; //形成循环链表
p=L;
for(i=1;i<=n;i++){
Delete(L,n,m);
}

return 0;
}

Answer 1

问题还不少，指针变量p,q在主函数中都没有值，如何运算，注意各个函数中定义的变量都是局部变量，只能在本函数中可见（使用），AddToL()函数中的p和Delete()中的q在main()中不可见，就是不能共用。main()函数中的语句：
scanf("%d",&(p->code));
p->num=i;//p没有（值），这样容易出大问题

建议：首先你要有一个思路，想象一下，n个人手拉（链）手，从编号为1的人开始报数，执行约瑟夫循环过程。用两个函数完成，Create_CL(LinkList &L,int n)完成环（循环链表）的创建，第二个是约瑟夫循环过程（包括输出）。下面是我写的代码，你参考下
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int num;
int code;
LNode *next;
}LNode,*LinkList;
void CreateList(LinkList &L,int n){
//创建带头结点的循环单链表
L=(LinkList)malloc(sizeof(LNode));
L->next=L;
LinkList p,q=L;
int i;
for(i=1;i<=n;i++){
p=(LinkList)malloc(sizeof(LNode));
if(!p) exit(0);
p->num=i;
printf("请输入第%d个人的密码值",i);
scanf("%d",&p->code);
p->next=q->next;
q->next=p;q=p;
}
}
void Joseph(LinkList L,int n){
LinkList p=L,q;
int count=0,m=p->next->code;//读取第一个人的密码
printf("\n出列序列：\n");
while(L->next!=L){
if(count==m-1){
q=p->next ;p->next =q->next ;//删除结点(出列)
printf("%d\t",q->num);
if(p->code<=0)exit(0);
m=q->code;n--;
free(q);count=0;
}else{
p=p->next ;
if(p->next==L)p=p->next;//报数时跳过头结点
count++;
}
}
printf("\n");
}
int main()
{
LinkList L,p;
int n=5;
CreateList(L,n);
Joseph(L,n);
return 0;
}