#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int data;
struct LNode *next;
}Node;//定义链表结构体
Node* Creat(Node* head,int n); //申明建立循环链表函数
Node* Delete(Node* head,int m); //申明删除函数
int main()
{
int M,N,S,j;
Node *head=NULL;
printf("多少人围成一圈: \n");
scanf("%d",&N);
head=Creat(head,N); //调用creat函数,建立循环链表
printf("从第几个人开始数起: \n");
scanf("%d",&S);
printf("相隔几人开始被杀掉: \n");
scanf("%d",&M);
for(j=1;j<S;j++)//寻找开始的节点
{
head=head->next;
}
printf("\n");
if(M==1)//当人数为1的时候,只需进行删除下一个即可
{
for(j=0;j<N-1;j++)
{
printf("被杀掉的人是:%d\n",head->data);
head=head->next;
}
if(head!=NULL)//剩余最后一个数据时,返回该值
{
printf("存活的人是:%d\n",head->data);
}
}
else //当人数大于1时,调用delete函数, 删除M个之后的人,并将删除后的头节点返回
{
while(head!=head->next)
{
head=Delete(head,M);
}
if(head!=NULL)//删除至最后一个值时,返回该值
{
printf("存活的人是:%d\n",head->data);
}
}
free(head);
system("pause");
return 0;
}
Node* Creat(Node *head,int n)//建立链表函数
{
Node *p=NULL;
Node *q=head;
int i;
for (i=1; i<=n;i++)
{
if (head==NULL)
{
head=(Node*)malloc(sizeof(Node));
head->next=head;
head->data=i;
q=head;
}
else
{
p=(Node*)malloc(sizeof(Node));
q->next=p;
p->data=i;
p->next=head;
q=p;
}
}
return head;
}
Node* Delete(Node *head,int m) //删除函数
{
int i=1;
Node *q=head,*p=NULL;
while(i<m)//移动指针,找到M个后需要删除的数据
{
p=q;
q=q->next;
i++;
}
printf("被杀掉的人是:%d\n",q->data);
p->next=q->next;//修改头指针
head=p->next;
free(q); //删除数据
return head;
}