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

摘  要

有 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 需求分析和概要设计

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

功能模块具体介绍如下：

顺序表的程序流程图

循环单链表的程序流程图

循环队列的程序流程图

程序代码

#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;//空表长度为0L.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值为1for(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; //循环意义下将尾指针加1Q->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; //循环意义下的头指针加1Q->count--; //队列数减1return 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);elseprintf("从第%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);//计算从根结点出发剩下的yz=num-y+2;//计算从谁出发剩下根结点，公式1+num-y+1if(z%num==0)printf("从第%d号开始计数能让排长最后一个留下。\n",z);elseprintf("从第%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);}}
}