数据结构 使用不带头结点循环单链表解决约瑟夫问题

数据结构 使用不带头结点循环单链表解决约瑟夫问题

越行勤 1,097 2021-03-15

循环链表练习 --- 约瑟夫问题

题目

n个人围成一个圆圈，首先第S个人从1开始逐个顺时针报数 ，报告到第m个人令其出列，然后从下一个人开始，逐个顺时针从1开始报数，报导第m个人，再次令其出列，......。如此下去，知道最后一个即为获胜者。

  1. 选择合适的数据结构，涉及算法求出优胜者。
  2. 编程实现并验证结果

分析

选择循环链表是毋庸置疑的，根据此题，我们也只需要只有一个指针的循环列表即可。

基本思路就是使用一个计数器来负责计数，遍历该链表的元素，使用if判断等于m时删除数据。

当然我们还面对一个问题 是否带头结点？

我的回答是不带，如果遍历到头结点，计数器依旧会增加1，但是头结点又不作为实际的数据，这样会导致错误，当然也可以减去，实属不方便。

定义：

typedef struct CLNode
{
  ElemType data;
  struct CLNode* next;
}LNode,*CLinkList;

看起来要使用的算法有如下，

  1. 删除结点指定结点 ，DeleteNode(CLinkList&L,LNode* p)
  2. 判断是否为只有一个结点 , if(p->netx==L) //操作
  3. 创建链表 CreateCLinkList(CLinkList&L,n) 长度为n ；

以上都是最基本的链表操作，有了这些方法就可以着手解决这个问题了，

CLNode *p=L; //负责遍历结点
int i=1; //负责计数
	while (!(L->next == L)) //只剩一个结点，结束循环
	{
		if (i == m)
		{
			printf("%4d号出局\n", p->Index);
			i = 1;//重新计数
			DeleteNode(L,p);
		}
		p = p->next;
		i++;
	}
printf("Winner is L->data");

程序实现

遇到的问题

一个非常愚蠢的错误，
Snipaste_2021-03-15_20-02-29 只要free就报错 本以为，我又不小心改变了，malloc开辟空间的大小，实则不然，一个非常可笑的问题,

CLNode* s = (CLNode*)malloc(sizeof(CLNode*));
咋会开辟一个大小为 CLNode* 的空间呢

创建链表的问题

CreateCLinkList(CLinkList&L,n) ，由于我们不采用带头结点创建的链表方式，所以注意要独立讨论插入第一个元素的时候，我使用一个辅助变量p记录尾结点

  1. 如果插入第一个元素，那么L=s就好, 此时尾节点为s;
  2. 后面就使用尾插法，为了确保输入的数是正序
  3. 将最后一个结点连接到 L
bool Create_CLinkList(CLinkList& L, int n)
{
	L = NULL;
	CLNode* p = L;//记录p尾结点
    CLNode* s;//生成的新结点
	for (int i = 1; i <= n; i++)
	{
		s = (CLNode*)malloc(sizeof(CLNode));
		if (s == NULL)
			return false;
		s->Index = i;
		if (L == NULL) //不带头结点要单独考虑插入第一个元素时的特殊情况
		{
			L = s;
			p = s;
		}
		else
			p->next = s;
		p = s;
	}
	p->next = L;
	return true;
}
删除链表的问题

当然在上面简答描述了一个DeleteNode(L,p); ，到了具体的方法，还有一些问题没有考虑到

我采用的方法就 乾坤大挪移大法

其实方法很简单，两结点 p,q:

p--->q

我将q中的数据和next覆盖掉p的数据，然后再删除q，其实相当于删除了 p；

当然这又没考虑的问题：

  1. 使用本功法，其实又一个问题被忽略了，q结点的数据被提前了一个位置，但是我的是从1开始计数，所以无妨。
  2. 如果m==1,那么i++后，if (i == m),是无法相等的（当然 int类型溢出后可以相等），我的解决办法就是当m==1，无需添加语句 i++;p = p->next;,就利用本算法删除数据自动前移动一个位置的bug，自动p = p->next;`，

补充，当然链表中"序号这个概念 被弱化了不少，要使用序号的概念，还是要着重注意一下

完整代码

运行结果

#include<stdio.h>
#include<stdlib.h>

#pragma warning(disable:4996)

typedef struct CLNode
{
	int Index;//第 Index 人
	struct CLNode* next;
}CLNode, * CLinkList;


bool Create_CLinkList(CLinkList& L, int n);//创建本次的链表,长度为n

void test()
{
	CLinkList L;
	int n, m;
	CLNode* p=NULL; //负责遍历结点
	CLNode* q=NULL;
	printf("请输入人数 n,和 m   ");
	scanf("%d %d", &n, &m);
	if (!Create_CLinkList(L, n))
		printf("开辟空间失败\n");
	// 输出链表
	p = L;
	while (1)
	{
		printf("第 %3d 个人 ,地址为 %p ,next   %p\n", p->Index, p, p->next);
		if (p->next == L)
			break;
		p = p->next;
	}
	//开始运算
	int i = 1; //负责计数
	p = L;
	while (!(L->next == L)) //只剩一个结点，结束循环
	{
		if (i == m)
		{
			i = 1;
			printf("%4d号出局\n", p->Index);
			q = p->next;
			//交换 p和q的数据    删除q其实就是删除p
			if (q == L)//如果删除的时最后一个尾节点
			{
				p->Index = q->Index;
				L = L->next;
				p->next = L;
			}
			else
			{
				p->Index = q->Index;
				p->next = q->next;
			}
			free(q);
		}
		
		if (m != 1)//防止输入1的情况
		{
			p = p->next;
			i++;
		}		
	}
	printf("Winner is %3d\n", L->Index);
	getchar();
}
int main()
{
	test();
	return 0;
}

bool Create_CLinkList(CLinkList& L, int n)
{
	L = NULL;
	CLNode* p = L;//记录p尾结点
	for (int i = 1; i <= n; i++)
	{
		CLNode* s = (CLNode*)malloc(sizeof(CLNode));
		if (s == NULL)
			return false;
		s->Index = i;
		if (L == NULL) //不带头结点要单独考虑插入第一个元素时的特殊情况
		{
			L = s;
			p = s;
		}
		else
			p->next = s;
		p = s;
	}
	p->next = L;
	return true;
}
数据结构