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

题目

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;
}

本文由 越行勤 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://blog.yxqin.top/2021/03/15/clinklist
最后更新于:  215  天前,内容可能已经不具有时效性,请谨慎参考。

Q.E.D.


努力学习的小菜鸟