C语言解决约瑟夫环(PTA链表）

题意：就是 N个人围成一个圈（想到循环），开始报数，报到一个指定的数p，则这个人出局，后延，比如本题的样例，第三个人报了3，则第四个人继续从1开始报数，一直循环下去，第七个人报完之后，再到第一个人，直到只剩下一个人，那么下一个出局的只剩下这个人。

解题思路：我们看到，最后一个人报数之后，又回到了第一个人开始报数，则可以使用循环链表，首先建立循环链表，把各个结点存入，最后一个结点再连接到头结点，再写一个函数用来使得某人出局，抽象到链表中也就是删除某个结点（出局的人），最后输入人数N和count（报数为count的人出局）。

首先定义结构体

其包括两个域，数据域和指针域。

typedef struct node 
{	
    int data;
    struct node* next;
} node;

 createCircularList函数：建立循环链表

 最需要注意也是最核心的即为把新结点插入到链表中 具体思路的可以看上一篇文章

node* createCircularList(int N)
{	//给头结点创建空间
	node *L=(node *)malloc(sizeof(node));
	//带头结点的链表
	L->next=NULL;
	//p与L指向头结点
	node *p=L;
	int i;
	//第几个人i就是几 通过1到N的循环将把i赋值给结点data域
	for(i=1;i<=N;i++)
	{
		node *s=(node *)malloc(sizeof(node));
		s->data=i;
		//新结点s连接到头结点之后
		s->next=p->next;
		p->next=s;
		//更新p的位置 便于后续完成收尾相接
		p=s;
	}
	//首尾相接 此时p是尾结点 next连接到头结点 完成首尾相连
	p->next=L->next;
	//创建之后 返回L
	return L;
}

 work函数（用于删除结点 即让某人出局）

ps:要注意free（shan）与其它代码的顺序 一定要先把准备工作做好（q指向current下一个 current顺延） 然后再free 

void work(node *L,int count)
{	//current指针为实质性的遍历链表的指针
	node *current=L->next;
	//因为我们要删除结点 所以需要得到要删除结点的前一个结点 即q
	node *q;
	int j;
	//last指针用来指向头结点 完成首尾相连
	node *last=current;
	//last遍历到最后一个结点 与currrnt指向相同时 说明到了最后一个结点 退出循环
	while(last->next!=current)
	{
		last=last->next;
	}
	//首尾相连
	last->next=current;
	//所有人从第一个人开始报数 直到剩下一个人 退出循环
	while(current->next!=current)
	{	//for循环表示每次更新q的位置 让其始终在current前一位 
		for(j=1;j<count;j++)
		{
		q=current;
		current=current->next;
		}
		//退出for循环 说明current对应的人报数为count 则将其输出
		printf("%d ",current->data);
		//字面意思  shan指针用来存储current指针 因为要将其free掉
		node *shan=current;
		//表示q连接到current下一个结点
		q->next=current->next;
		//某个人报数为count 继续进行 currrnt->next 表示开始下一个人报数
		current=current->next;
		free(shan);	
	}
	//退出while循环 表示current==current->next 即链表中只剩下一个元素 人数为1 直接输出
	printf("%d\n",current->data);
	//从题中可以知道 N个人全部出局 则将最后的current也free掉
	free(current);
}

 main函数

int main()
{
	int N,count;
	//此处if保证输入的两个数均为%d 否则不执行
	if(scanf("%d %d",&N,&count)==2)
	{
		node *L=createCircularList(N);
		 work(L,count);
		 return 0;
	}
}

 完整代码

#include <stdio.h>
#include <stdlib.h>
typedef struct node 
{	
    int data;
    struct node* next;
} node;
node* createCircularList(int N)
{
	node *L=(node *)malloc(sizeof(node));
	L->next=NULL;
	node *p=L;
	int i;
	for(i=1;i<=N;i++)
	{
		node *s=(node *)malloc(sizeof(node));
		s->data=i;
		s->next=p->next;
		p->next=s;
		p=s;
	}
	p->next=L->next;
	return L;
}
void work(node *L,int count)
{
	node *current=L->next;
	node *q;
	int j;
	node *last=current;
	while(last->next!=current)
	{
		last=last->next;
	}
	last->next=current;
	while(current->next!=current)
	{
		for(j=1;j<count;j++)
		{
		q=current;
		current=current->next;
		}
		printf("%d ",current->data);
		node *shan=current;
		q->next=current->next;
		current=current->next;
		free(shan);	
	}
	printf("%d\n",current->data);
	free(current);
}
int main()
{
	int N,count;
	if(scanf("%d %d",&N,&count)==2)
	{
		node *L=createCircularList(N);
		 work(L,count);
		 return 0;
	}
}

 运行结果