约瑟夫环问题,创造链表后,无法输入位置i和数m。
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int data;
struct LNode next;
}LNode,LinkList;
LinkList initLink(LinkList head)
{
int x;
head=(LNode)malloc(sizeof(LNode));
head->next=NULL;
LNode cyclic=head;
scanf("%d",&x);
while(x!=-1) {
LNode * body=(LNode*)malloc(sizeof(LNode));
body->data=x;
body->next=NULL;
cyclic->next=body;
cyclic=cyclic->next;
}
cyclic->next=head;//首尾相连
return head;
}
void JosephusRing(int i,int m,LNode *head)
{
if(i<1||m<1)
printf("error");
LNode *tail=head;//tail的作用是删除结点
//找到链表第一个结点的上一个结点,为删除操作做准备
while (tail->next!=head)
{
tail=tail->next;
}
LNode *p=head;
//找到编号为i的人
while (p->data!=m)
{
tail=p;
p=p->next;
}
//从编号为i的人开始,只有符合p->next==p时,说明链表中除了p结点,所有编号都出列了,
while (p->next!=p) //不是指向自己
{
//找到从p报数1开始,报m的人,并且还要知道数m-1的人的位置tail,方便做删除操作。
for (int i=1;i<m;i++)
{
tail=p;
p=p->next;
}
tail->next=p->next;//从链表上将p结点摘下来
printf("%d",p->data);
free(p);
p=tail->next;//继续使用p指针指向出列编号的下一个编号,游戏继续
}
printf("%d",p->data);
free(p);
}
int main()
{
LinkList head;
int i,m;
head=initLink(head);
scanf("%d",&i);
scanf("%d",&m);
JosephusRing(i,m,head);
return 0;
}