论坛 › 数据结构与算法 › 约瑟夫环(运用单向循环链表来实现约瑟夫环问题)

小米豆子 发表于 2021-6-7 09:44:03

约瑟夫环(运用单向循环链表来实现约瑟夫环问题)

/*
约瑟夫环问题
*/

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

typedef struct LinkNode
{
    int data;
    struct LinkNode *next;
}LinkNode,*LinkList;



//创立一个不带头节点的循环链表
void build(LinkList &L)
{
    L=(LinkNode *)malloc(sizeof(LinkNode));
    LinkList q=L;
    int e;
    scanf("%d",&e);
    L->data=e;
    scanf("%d",&e);
    while(e!=-1)
    {
      LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
      s->data=e;
      q->next=s;
      q=s;
      scanf("%d",&e);
    }
    q->next=L;
}



void yuesefu(LinkList &L,int m)
{
    int n=1;
    LinkList p=L;
    //遍历
    while(L->next!=L)
    {
      p=p->next;
      n++;
      if(n==m)
      {
            LinkList r=L;
            while(r->next!=p)
            {
                r=r->next;
            }
            r->next=p->next;
            printf("%d ",p->data);
            free(p);
            p=r;
            L=r->next;//让新开始报数的结点当头
            n=0;//重新从0开始计数
      }

    }
}


int main()
{
    LinkList L;
    build(L);
    yuesefu(L,5);
}

小米豆子 发表于 2021-6-7 09:47:03

双向循环链表更简单一些，时间复杂度也更低，但是约束条件较多，在题目中一般是不准许使用双线链表，还有人问静态数组可以实现吗，答案当然是可以，但是为什么我不用，别问，问就是不喜欢数组{:10_256:}

查看完整版本: 约瑟夫环(运用单向循环链表来实现约瑟夫环问题)