Question

数据结构用c编写约瑟夫环，要求用单循环链表，不知道为什么有问题，求解答。。

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef struct lnode
{
int num;
int data;
struct lnode *next;
}lnode,*linklist;
void chulie(int k,int d,linklist q,linklist t)
{
t=(linklist)malloc(sizeof(lnode));
t->next=(linklist)malloc(sizeof(lnode));
for(k=q->num;k<=q->num+d-1;k++)
{
q->next=(linklist)malloc(sizeof(lnode));
if(q->next==NULL)
q->next=t->next;
q->next->next=(linklist)malloc(sizeof(lnode));

if(q->next->next==NULL)
q->next->next=t->next;

}
q->next=(linklist)malloc(sizeof(lnode));
printf("%d,",q->next->num);
d=q->next->data;
q->next->next=(linklist)malloc(sizeof(lnode));
q=q->next->next;
free(q->next);

}
void main()
{
linklist p,l;
l=(linklist)malloc(sizeof(lnode));
l->next=(linklist)malloc(sizeof(lnode));
p=l->next;
int m,n,i,j=1;
printf("请输入报数上限值m:");
scanf("%d",&m);
printf("请输入总人数n:");
scanf("%d",&n);
for(i=1;i<n;i++)
{
printf("请输入密码:");
scanf("%d",&p->data);
p->num=i;
p->next=(linklist)malloc(sizeof(lnode));
p=p->next;

}
printf("请输入密码:");
scanf("%d",&p->data);
p->num=i;
p=l->next;
for(i=1;i<=n;i++)
{

chulie(j,m,p,l);
}
}

Answer 1

/*耶稣有13个门徒，其中有一个就是出卖耶稣的叛徒，请用排除法找出这位叛徒：
13人围坐一圈，从第一个开始报号：1，2，3，1，2，3……，凡是报到“3”就退出圈子，
最后留在圈内的人就是出卖耶稣的叛徒，请找出它原来的序号。
*/

// approach one
#define N 13
#include<stdio.h>
#include<conio.h>

struct person
{
int number; //its order in the original circle
int nextp; //record its next person
};

struct person link[N+1]; //link[0] for no use

void main()
{
int i,count,next; //count for 12 persons,and
//next for the person not out of circle yet

for (i=1;i<=N;i++)
{
link[i].number=i; //numbering each person
if(i==N)
link[i].nextp=1;
else
link[i].nextp=i+1; //numbering each next person
}

printf("\nThe sequence out of the circle is:\n");

for(next=1,count=1;count<N;count++) //count until 12 persons
{
i=1;
while (i!=3) //i counts 1,2,3
{
do //skip the ones whose numbers are zero
next=link[next].nextp;
while(link[next].number==0); //end of do
i++;
}

printf("%3d ",link[next].number);

link[next].number=0; //indicate out of circle already

do //start from the ones whose numbers are not zero next time
next=link[next].nextp;
while(link[next].number==0);
}

printf("\n\nThe betrayer of them is:");

for(i=1;i<=N;i++)
if(link[i].number)
printf("%3d\n",link[i].number);
getch();
}

/*
// approach two using cyclic list
#define N 13
#define LEN sizeof(struct person)
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>

void main()
{
int i,count;
struct person
{
int number;
struct person *next;
};
struct person *head,*p1,*p2;
head=p2=NULL;

for(i=1;i<=N;i++)
{
p1=(struct person *)malloc(LEN);
p1->number=i;
if(head==NULL)
head=p1;
else
p2->next=p1;

p2=p1;
} //构造有十三个人的链表

p2->next=head; //指向头指针，构成循环链表

printf("\nThe sequence out of the circle is:\n");

for (count=1;count<N;count++)//12次循环
{
i=1;
while(i!=3)
{
p1=head;
head=head->next;
i++;
} //每次循环的头一个人
p2=head;
printf("%3d ",p2->number);
p1->next=head=p2->next;
free(p2);
} //报数出圈

printf("\nThe betrayer of them is:\n%3d",head->number);

getch(); //运行不会自动结束
}
*/