基于数据结构知识解决敢死队问题

这篇具有很好参考价值的文章主要介绍了基于数据结构知识解决敢死队问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

摘  要

有 M 个敢死队员要炸掉敌人的一碉堡,谁都不想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到 5 时,对应的战士就去执行任务,且此战士不再参加下一轮计数。如果此战士没完成任务,再从下一个战士开始数数,被数到第 5 时,此战士接着去执行任务。以此类推,直到任务完成为止。

 假设排长是不愿意去的,假设排长为 1 号,请你设计一程序,求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

设计用顺序表、循环单链表、循环队列来实现该问题:

第一种是用顺序表来实现,用数组来描述线性表的顺序存储结构,先是定义变量并初始化,再将线性表初始化,最后在队员数小于等于1的时候,输出结果。

第二种是用循环链表来实现,以循环单链表为存储结构,包含三个模块:主程序模块,构造链表并初始化,删除。

第三种的用循环队列来实现,首先从第一号开始报数,循环到指定的偏移位置删除结点,直至剩下一个结点,再比较它的编号是不是等于1,如果等于则输出开始计数位置;如果不等,继续循环查找,直到找出符合条件的计数起始位置,输出结果。

关键词:轮回数数  约瑟夫环  顺序表  循环单链表  循环队列

章  绪  论

1.1 课设主要研究问题

有 M 个敢死队员要炸掉敌人的一碉堡,谁都不想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到 5 时,对应的战士就去执行任务,且此战士不再参加下一轮计数。如果此战士没完成任务,再从下一个战士开始数数,被数到第 5 时,此战士接着去执行任务。以此类推,直到任务完成为止。

 假设排长是不愿意去的,假设排长为 1 号,请你设计一程序,求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

 敢死队问题包括:两个数据的输入,一个是敢死队队员数量,另一个是模拟的形式。

由于问题给出的轮回数数的数量为5,则K值默认为5,不再设置数据输入。

1.2 课设应用的理论知识

数据结构类型:顺序表、循环单链表、循环队列

1.2.1 顺序表

本程序实质是约瑟夫环问题,用了线性表数据结构,并运用模块化的程序设计思想。

  1. 定义变量并初始化。
  2. 顺序表初始化。
  3. 当队员数量小于等于1时,输出结果。

1.2.2 循环单链表

以循环单链表为存储结构,包含三个模块:

  1. 主程序模块:包含敢死队人数的输入,从根结点出发最后剩下的结点的值的输入,函数的调用,结果的输出。
  2. 构造链表并初始化:构造链表,给每个结点赋值,给队员编号。
  3. 删除:当报数到死亡数字时队员出列去执行任务,删除该结点。

1.2.3 循环队列

本程序实质是约瑟夫环问题,用了循环队列数据结构,并运用模块化的程序设计思想。

首先从第一号开始报数,循环到指定的偏移位置删除结点,直至剩下一个结点,再比较一下它的号码是不是等于1,如果等于则输出开始计数位置;如果不等,继续循环查找,直到找出符合条件的计数起始位置,输出结果。

第二章  课设实现过程

2.1 需求分析和概要设计

本程序有四个功能模块,包括三个解决敢死队问题方案的模块和一个退出系统模块。三个解决方案分别采用了顺序表存储结构,循环单链表存储结构,循环队列存储结构。功能模块

基于数据结构知识解决敢死队问题,数据结构,链表,算法

功能模块具体介绍如下:

顺序表的程序流程图

基于数据结构知识解决敢死队问题,数据结构,链表,算法

循环单链表的程序流程图

基于数据结构知识解决敢死队问题,数据结构,链表,算法

循环队列的程序流程图

基于数据结构知识解决敢死队问题,数据结构,链表,算法

程序代码文章来源地址https://www.toymoban.com/news/detail-765380.html

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
//顺序表
#define MAXSIZE 100
#define LISTINCCREMENT 10
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct KList //定义数据结构体类型
{
	ElemType *elem;//储存空间基址
	int length ; //当前长度
	int listsize;//当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
int InitList(SqList &L)//创建线性表函数
{
	L.elem=(ElemType *)malloc(MAXSIZE *sizeof(ElemType));//动态分配一个大小为MAXSIZE的数组空间 
	if(!L.elem)
	{
		printf("存储分配失败");
		return ERROR;
	}
	else
	{
		L.length=0;//空表长度为0
		L.listsize=MAXSIZE;
		return OK;//初始存储容量
	}
}
int ListInsert_Sq(SqList &L)//线性表再分配函数
{
	//SqList L;
	int *newbase;
	newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCCREMENT)*sizeof(ElemType));
	//为顺序表增加一个大小为存储LISTNCCREMENT 个数据元素的空间
	if(!newbase)
	{
		printf("存储分配失败");
		return ERROR;
	}
	else
	{
		L.elem=newbase;//新基址
		L.listsize+=LISTINCCREMENT;
		//增加存储容量
		return OK;
	}
}

//循环单链表
typedef struct node
{
	int data;
	struct node *next ;
}LNode;//定义结点类型
LNode *CREAT(int n)//创建循环单链表(n个敢死队队员) 
{
	LNode *s,*q,*T;
	int i;
	if(n!=0)
	{
		T=q=(LNode *)malloc(sizeof(LNode));//生成第一个结点
		q->data=1;//使其data值为1
		for(i=2;i<=n;i++)
		{
			s=(LNode*)malloc(sizeof(LNode));//自动生成结点
			q->next=s;
			q->next->data=i;//赋值
			q=q->next;
		}	
		q->next=T;
	}
	return T;//返回头结点,形成循环链表
}
DELETE (LNode *T)//链表的删除
{
	LNode *a;
	int i;
	while(T->next!=T)
	{
		for(i=1;i<4;i++)//查找要删除节点的前一个结点
		{
		  T=T->next;	
		}	
		a=T->next;
		T->next=a->next;//删除数据
		free(a);
		T=T->next ;
	}
	printf("\n");
	return (T->data );
}

//循环队列
#define QueueSize 1000//假定预分配的队列空间最多为1000个元素
//typedef int DataType;//假定队列元素的数据类型为字符
typedef struct{
	int data[QueueSize];
	int front;//头指针
	int rear;//尾指针
	int count; //计数器,记录队中元素总数
}SqQueue;

// 循环队列初始化 
void InitQueue(SqQueue *Q)
{//构造空队列Q 
	Q->front=Q->rear=0;
	Q->count=0; //计数器置0
}

// 判队列空
int IsEmpty(SqQueue *Q)
{
	return Q->front==Q->rear;
}

//判队列满
int IsFull(SqQueue *Q)
{
	return Q->rear==QueueSize-1+Q->front;
}

//进队列
void EnQueue(SqQueue *Q,int x)
{
	if (IsFull(Q))
	{
		printf("队列上溢"); //上溢,退出运行
		exit(0);
	}
	Q->data[Q->rear]=x; //新元素插入队尾
	Q->rear=(Q->rear+1)%QueueSize; //循环意义下将尾指针加1
	Q->count ++; //队列数加1
}

//出队列
int DeQueue(SqQueue *Q)
{
	int temp;
	if(IsEmpty(Q))
	{
		printf("队列为空"); //队列空,退出运行
		exit(0);
	}
	temp=Q->data[Q->front];
	Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1
	Q->count--; //队列数减1
	return temp;
}


int main()
{
	SqList L;
	int s,i,count=0;//声明变量
	LNode *p;
	int z ,y,e=1,c=1;
	int num;
	int opt;
	while(c)
	{
	printf("\n————敢死队问题————\n");	
	printf("1.顺序表\n");
	printf("2.循环单链表\n");
	printf("3.循环队列\n");
	printf("4.退出\n");
	printf("请选择使用的存储结构:(1~4)\n\n");
	scanf("%d",&opt);
	if(opt >4||opt <1)
	{
		printf("输入有误请重新输入\n");
		continue;
	}
	switch(opt)
	{
	case 1:
		printf("您使用的是顺序表存储结构\n\n");
		while(e)
		{
			printf("请输入敢死队的人数:\n");
			scanf("%d",&num);
			if(num<1)
			{
				printf("输入有误请重新输入\n");
				continue;
			}
			InitList(L);
			while(num>L.listsize)//当顺序表当前分配的存储空间大小不足时进行再分配
				ListInsert_Sq(L);
			for(i=0;i<num;i++) L.elem[i]=i+1;//为队员赋值
			s=num;
			i=0;
			while(s>1)//当所剩敢死队员总数为1时,总循环结束
			{
				for(i=0;i<num;i++)
					if(L.elem[i]!=0)
					{
						count++;
						if(count==5)//报数循环
						{
							L.elem[i]=0;//表示队员出列
							count =0;//计数器清零
							s--;//敢死队员数-1
						}
					}
			}
			for(i=0;i<num;i++)//输出从一开始最后剩余队员的位置为 L.elem[i]
				if(L.elem[i]!=0)
					if((num-L.elem[i]+2)%num==0)
						printf("从第%d号开始计数能让排长最后一个留下。\n",num);
					else
						printf("从第%d号开始计数能让排长最后一个留下。\n",(num-L.elem[i]+2)%num);
			break;
		}
		break;
	
	case 2:
		e=1;
		printf("您使用的是循环单链表存储结构\n");
		while(e)
		{
			printf("请输入敢死队的人数:\n");
			scanf("%d",&num);
			if(num<1)
			{
				printf("输入有误重新输入\n");
				continue;
			}
			else
			{
				p=CREAT(num);
				y=DELETE(p);//计算从根结点出发剩下的y
				z=num-y+2;//计算从谁出发剩下根结点,公式1+num-y+1
				if(z%num==0)
					printf("从第%d号开始计数能让排长最后一个留下。\n",z);
				else
					printf("从第%d号开始计数能让排长最后一个留下。\n",(num-y+2)%num);
			}
			break;
		}
		break;
		
	case 3:
		e=1;
		printf("您使用的是循环队列存储结构\n\n");
		int start,count,j;
		SqQueue s;
		while(e)
		{
			printf("请输入敢死队的人数 :\n");
			scanf("%d",&num);
			if(num<1)
			{
				printf("输入有误请重新输入\n");
				continue;
			}
			for(start=1;start<=num;start++)//start为测试起点
			{
				InitQueue(&s);
				for(i=1;i<=num;i++)
				{
					EnQueue(&s,i);
				}//初始化
				for(i=1;i<start;i++)
				{
					j=DeQueue(&s);
					EnQueue(&s,j);
				}//将队头元素放到队尾,这样循环后start就会在队头
				count=1;
				while(count<num)
				{
					for(i=1;i<5;i++)
					{
						j=DeQueue(&s);
						EnQueue(&s,j);
					}//4个放到队尾
				j=DeQueue(&s);//删除队头
				count++;
				}
				if(s.data[s.front]==1)
					break;
			}
			printf("从第%d号开始计数能让排长最后一个留下。\n",start);
			break;
		}
		break;
	case 4:
		exit(0);
	}
	}
}

到了这里,关于基于数据结构知识解决敢死队问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构--基础知识

    数据结构是计算机科学中研究数据组织、存储和管理的方法和原则。它涉及存储和操作数据的方式,以便能够高效地使用和访问数据。 数组(Array):数组是一种线性数据结构,由相同类型的元素按顺序排列而成。数组具有固定长度,在内存中占据连续的位置。可以通过索引

    2024年02月14日
    浏览(46)
  • 数据结构|基础知识定义

    1.值传递、地址传递、值返回、地址返回 1 值传递 :普通变量作为函数参数传递是单向的值传递,只是将实参的值复制一份给形参变量,形参的改变不会影响实参的值,因为所在内存空间不同 如果传递的是地址,被调函数使用指针接收,如果在被调函数中,没有更改指针指向

    2024年02月08日
    浏览(47)
  • 数据结构基础知识、名词概述

    整体知识框架 1.1.1 数据、 数据元素、 数据项和数据对象 数据 (Data) 是客观事物的符号表示,是所有 能输入到计算机中并被计算机程序处理的符号 的总称 。如数学计算中用到的整数和实数,文本编辑中用到的字符串,多媒体程序处理的图形、 图像、声音及动画等通过特殊编

    2024年02月15日
    浏览(53)
  • 数据结构~二叉树(基础知识)

    上一篇博客我们对树有了初步了解与学习,这篇我将初步学习二叉树!!(新年快乐!) 目录 二叉树   1、定义: 2、特点: 3、基本形态: 4、二叉树的种类: (1)满二叉树 (2)完全二叉树 (效率高) (3)斜树 5、二叉树的性质:  6、二叉树的存储: 1、定义: 二叉树

    2024年02月19日
    浏览(51)
  • 【数据结构】树的基础知识及三种存储结构

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 把它叫做树是因为它

    2024年02月09日
    浏览(51)
  • 【数据结构】五分钟自测主干知识(四)

    线性数据结构中有两个典型代表——栈和队列。它们的逻辑结构和线性表一致,不同之处在于其操作的特殊性:栈的插入和删除操作只能在线性表的一端进行,并且元素遵循“后进先出”的原则 今天我们先来讲述这个经典概念:“栈” 3.1栈的基本概念 栈 (Stack)是一种线性

    2024年03月19日
    浏览(36)
  • 数据结构—基础知识:哈夫曼树

    哈夫曼(Huffman)树 又称最优树,是一类带权路径长度最短的树,在实际中有广泛的用途。哈夫曼树的定义,涉及路径、路径长度、权等概念,下面先给出这些概念的定义,然后再介绍哈夫曼树 路径 :从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路

    2024年02月21日
    浏览(47)
  • 【考研易忘知识点】数据结构

    数据的逻辑结构独立于其存储结构 可以用抽象数据类型定义一个完整的数据结构 数据的运算也是数据结构的一个重要方面: 二叉树和二叉排序树的逻辑结构和物理结构完全相同,但运算效率大不相同;如查找,二叉树O(n),二叉排序树O(logn) 一个算法是问题求解步骤的描述,

    2024年02月08日
    浏览(45)
  • Java学习之数据结构知识点

    Java学习系列知识点纯干货: 1.Java学习之Java基础部分知识点—传送门 2.Java学习之Java多线程知识点—传送门 3.Java学习之数据库知识点—传送门 4.计算机网络知识点—传送门 5.Java学习之数据结构知识点—传送门 6.操作系统知识点学习—传送门 一棵深度为k的有n个结点的二叉树,

    2024年02月07日
    浏览(49)
  • 【数据结构】——二叉树的基础知识

    数的分类 二叉树、多叉树 数的概念 树是一种 非线性 的数据结构,它是由n(n=0)个有限节点组成一个具有层次关系的集合。 把它叫做树的原因是它看起来像一颗倒挂的树,也就是说它是跟朝上,而叶朝下的。 有一个特殊的节点,称为根节点,这个节点没有前驱节点。 除根节

    2024年02月07日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包