循环链表实现约瑟夫问题

问题描述

利用循环链表实现：读入 2 个整数 A 和 B，然后输出 2 个整数 C 和 D。

其中 A 表示人数，这些人的 id 分别为1，2，3，. . . A，他们按照id依次围成一圈。

从id为1的人开始报数，报到B的人退出圈，然后从下一个人开始重新报数，报到 B的人又退出圈，

如此反复，直到剩下2人为止。C和D为剩下的2人的id。

输入描述

在一行中输入大于0且不超过1000的整数A和B，要求A大于B。

输出描述

在一行中输出C和D，由空格隔开，要求D大于C。

样例输入

41 3                  

样例输出

16 31
      

注意 

分配内存可以采用new和malloc两种方法。

删除结点需要释放内存，以免内存泄漏。

内存泄漏是指向系统申请分配内存进行使用(new)，可是使用结束却不归还(delete)，导致申请到的内存无法再次访问（地址丢失），系统也不能再次将它分配给需要的程序。内存泄漏本身不会产生什么危害，真正有危害的是内存泄漏的堆积，这会最终消耗尽系统所有的内存。

表格数据来源：【C++】C++ new和malloc到底哪里不一样 - 李春港 - 博客园 (cnblogs.com)

完整代码

#include<stdio.h>
typedef int DataType;
//定义单链表
typedef struct LNode
{
	DataType data;   //数据域
	struct LNode* next;   //指针域
}LNode;   
//创建循环单链表
static LNode* CreateList(int a)
{
	LNode* head = new LNode;  //创建首元结点  new分配内存
	head->data = 1;  //首元结点数据域存放1
	LNode* p = head;
	for (int i = 2; i <= a; i++)
	{
		LNode* newnode = new LNode;  //创建新结点
		newnode->data = i;  
		p->next=newnode;
		p = newnode;
	}
	p->next = head;  //首尾闭合
	return head;  //返回首元结点
}
static void Operate(int a, int b)
{
	LNode* head = CreateList(a);  //接收首元结点
	LNode* p = head;  //用于遍历循环单链表
	LNode* del = head;  //标记需要删除的结点
	while (a > 2)
	{
		for (int i = 1; i < b; i++)
		{
			p = del;
			del = del->next;
		}
		//删除结点
		p->next = del->next;  
		delete(del);  //释放已删除结点内存
		del = p->next;
		a--;
	}
	int c = del->data;   //赋值便于比较
	int d = del->next->data;
	if (c > d)   //比较cd大小
		printf("%d %d\n", d, c);
	else
		printf("%d %d\n", c, d);
}
int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	Operate(a, b);
	return 0;
}