[数据结构与算法]约瑟夫环问题(结构体、链表)（C语言实现）

【题目描述】

设有n个人围坐一圈并按顺时针方向从1到n（n<500）编号，从第1个人开始进行1到m的报数，报数到第个m人，此人出圈，再从他的下一个人重新开始1到m的报数，如此进行下去直到所剩下一人为止。求每一行中最后剩下这个人的编号，编号从1开始。要求利用链表完成编程。

【输入说明】

输入有一行数据，２个数，分别表示n和m.

【输入样例】

10 3

【输出样例】

4

代码实现

#include?<stdio.h>

#include?<stdlib.h>

int?i;

typedef?struct?node{

????int?pos;//编号

????struct?node?*next;

}?LINK;

//创建圆圈，返回链表的头指针

LINK?*p1,*p2,*head=NULL;

LINK?*CreateList(int?n)

{

????for(i=1;i<=n;i++)

????{

????????p1=(LINK*)malloc(sizeof(LINK));

????????p1->pos=i;

????????if(i==1)?head=p1;

????????else?p2->next=p1;

????????p2=p1;

????}

????p2->next=head;

????return?head;

}

//?删除第x个结点

void?DeleteList(LINK?*p,?int?x)

{

????int?t=1;

????while(p->next!=p)

????{

????????if(t==x-1)p1=p;

????????if(t==x+1)

????????{

????????????p1->next=p;

????????????t=1;

????????}

????????p=p->next;

????????t++;

????}

????head=p;

}

int?main()

{

????int?m,n,t;

????scanf("%d%d",&n,&m);

????head=CreateList(n);

????DeleteList(head,m);

????printf("%d",head->pos);

????return?0;

?}