约瑟夫环 OJ

约瑟夫环 OJ

全栈程序员-用户IM • 2022年5月29日下午3:16 • 未分类

大家好，又见面了，我是你们的朋友全栈君。

约瑟夫环 OJ

循环链表的应用，并且应为不带头节点的循环链表，首先创建一个循环链表，在函数JOHEPHUS中进行操作，主要就是用for找到要删除的元素（注意p==1单独考虑，for中p至少为2），删除元素并输出直至链表为空。

for(j=1;j<=p-1;j++)把寻找报数的位置和寻找要删除的节点的前驱结合在一个循环中，减少时间复杂度，因为第一次写我是在主函数中用r指向找到的要删除的节点，然后传入delete(&L,r)中删除，而在delete中，需要从头找r的前驱，再修改指针，会发现这其中两个寻找的过程是重复进行的，所以基于函数功能的思想将它结合在一起，放入JOHEPHUS中，

第一次写加入了initList，但由于没有头节点，只是将头指针赋为空指针，并没有意义，而调用函数会使时间增长，可以将这一步放入到creat函数中，判空函数也完全可以有while(cur.next!=cur)来表示，当然这个函数判断是否只剩一个元素了，也完全不用重新写delete，

#include<stdio.h>
#include<stdlib.h>
#define error -1
typedef struct LNode{

int num;
struct LNode *next;
}LNode,* Link;

void creat_list(Link *L,int n){

*L=NULL;
int i;
LNode * s=(LNode * )malloc(sizeof(LNode));
(*s).num=1;
(*s).next=s;
(*L)=s;
if(n>=2)
{

for(i=2;i<=n;i++)
{

LNode * w=(LNode * )malloc(sizeof(LNode));
   (*w).num=i;
(*s).next=w;
   (*w).next=(*L);
s=w;
}
}
}

void JOHEPHUS(Link *L,int n,int p){

int j;
   LNode * cur=*L;
   LNode *r;
if(p==1){

   while(n-1){

   printf(“%d “,(*cur).num);
   cur=(*cur).next;
   n–;
   }
   printf(“%d”,(*cur).num);
   }
else//p>=2
{

while((*cur).next!=cur)
{

for(j=1;j<=p-1;j++)
{

r=cur;
   cur=(*cur).next;
}
   printf(“%d “,(*cur).num);
(*r).next=(*cur).next;
   free(cur);
   cur=(*r).next;
}//while
printf(“%d”,(*cur).num);
}//else
}//JOHEPHUS

int main()
{

int p,n;
Link L;
LNode * cur;
if(scanf(“%d %d”,&n,&p)!=EOF)
{

if(p>=1&&p<=5000 &&n>=1&&n<=3000)
{

creat_list(&L,n);
JOHEPHUS(&L,n,p);
}//if
}//if
return 0;
}