C语言循环单链表解决约瑟夫问题

Question

 #include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct LNode
{
    Elemtype data;
    struct LNode *next;
}LNode,*LinkList;

void createlist(LinkList *head,int n)
{
    int i;
    LinkList p,q;
    *head=(LinkList)malloc(sizeof(LNode));
    (*head)->next=*head;
    p=(*head)->next;
    for(i=0;i<n;i++)
    {
        q=(LinkList)malloc(sizeof(LNode));
        q->data=i+1;
        q->next=p;
        p->next=(*head);
        p=q;//这句代码用处是什么呢？
        printf("%d\n",q->data);
    }
}

void yuesefuList(LinkList head,int n,int m,int k)
{
    int i,rec=0;
    LinkList p,q;
    p=head->next;
    if(m>n)
    {
        printf("error!");
    }
    for(i=1;i<m;i++)
    {
        p=p->next;
        printf("%d\n",p->data);
        if(p->next==head->next)
            p=p->next;
    }

    //开始报数
    while(rec!=n){
    for(i=0;i<k;i++)
    {
        p=p->next;
        if(p->next==head->next)
           p=p->next;
    }
    printf("%d ",p->data);
    //delete
    q=p->next;
    p->next=q->next;
    free(p);
    rec++;
    p=q->next;
    }
}
int main()
{
    LinkList head;
    int n,m,k;
    printf("please enter the number of person\n");
    printf("n=");
    scanf("%d",&n);
    printf("please enter the location of beginning\n");
    printf("m=");
    scanf("%d",&m);
    printf("please enter the number of gap\n");
    printf("k=");
    scanf("%d",&k);
    createlist(&head,n);
    //inputlist(head,n);
    yuesefuList(head,n,m,k);
    return 0;
}

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1，2，3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。

大概思路是建立一个循环链表，先遍历到开始位置，通过while循环找到下一个结点，输出结点的数据域
通过了编译，但是输出结果是乱七八糟的数字。。。
求大神教教小弟orz

Answer 1

1、你的链表创建的不对，你的建表方式使得最后两个节点为一个循环；
2、报数过程也有问题，遇到头结点要空开；并且过程逻辑好像不对
下面是改好的代码，没有测试太多例子
#include
#include

typedef int Elemtype;
typedef struct LNode
{
Elemtype data;
struct LNode *next;
}LNode,*LinkList;

void createlist(LinkList head,int n)
{
int i;
LinkList p,q;
*head=(LinkList)malloc(sizeof(LNode));
(*head)->next=*head;
p=(*head)->next;//p相当于尾指针
/*for(i=0;i {
q=(LinkList)malloc(sizeof(LNode));
q->data=i+1;
q->next=p;//这里面既要注意顺序问题，又要注意逻辑上是否正确
p->next=(*head);
p=q;//这句代码用处是什么呢？
printf("%d\n",q->data);
}/
for(i=0;i {
q=(LinkList)malloc(sizeof(LNode));
q->data=i+1;
p->next=q;
p=q;//使p指向最后一个节点
p->next=(*head);
//printf("%d\n",q->data);
}
}

void yuesefuList(LinkList head,int n,int m,int k)
{
int i,rec=0;
LinkList p,q;
p=head;
if(m>n)
{
printf("error!");
}
//将p永远指向报1的前一个人
//找到第m-1个人的位置，从下一个人开始报数
for(i=1;i {
p=p->next;
printf("%d\n",p->data);
/*if(p->next==head->next)
p=p->next;*///上面已经处理了m>n的情况
}

//开始报数
while(rec!=n){
    q=p->next;//q指向报1的 
for(i=1;i<k;i++)//报数报到k的人出列,为了方便找报k-1的人 
{
    p=q;
    q=q->next;//q指向报i+1的人 
    if(q==head)//由于加了头结点，当循环到头结点时需要移动到下一个节点  
       {q=q->next;p=p->next;}//此时q记录的是报到k的人的前一个人       
}
//本次循环之后，p指向报k-1的，q指向报k的 
//delete
printf("%d \n",q->data);
p->next=q->next;
free(q);
rec++;
}

}
int main()
{
LinkList head;
int n,m,k;
printf("please enter the number of person\n");
printf("n=");
scanf("%d",&n);
printf("please enter the location of beginning\n");
printf("m=");
scanf("%d",&m);
printf("please enter the number of gap\n");
printf("k=");
scanf("%d",&k);
createlist(&head,n);
//inputlist(head,n);
yuesefuList(head,n,m,k);
return 0;
}