C语言循环单链表解决约瑟夫问题
 #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

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;
}

weixin_41807114
Grey000 回复weixin_43191340: 尾指针是指这个链表最后一个节点,在创建链表的过程中是指(如果用尾插法的话就是指新增的那个节点)
大约一年之前 回复
weixin_41807114
Grey000 回复weixin_43191340: 这个是指创建单链表的过程中的吗?
大约一年之前 回复
weixin_43191340
那边的薯片半价阿 而且p->next=q和p=q这两句作用不是一样吗
大约一年之前 回复
weixin_43191340
那边的薯片半价阿 对不起,我还想问问您,您说p是尾指针,为什么令这个尾指针指向链表最后一个结点后,又在这个尾指针里放上头结点的地址就构成循环链表了呢?我觉得没有链成环呀,尾指针放了头结点的 地址那之前指向最后一个结点不就不作数了
大约一年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!

相似问题