weixin_43191340
那边的薯片半价阿
采纳率83.3%
2018-10-12 11:03

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条回答

  • weixin_41807114 Grey000 3年前

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

    点赞 评论 复制链接分享

相关推荐