
敢死队问题说明书.docx
10页敢死队问题说明书 目录 摘要 (1) 前言 (2) 正文 (3) 1.采用类c语言定义相关的数据类型 (3) 2.各模块的伪码算法 (4) 3.函数的关系调用图 (8) 4.调试分析 (13) 5.测试结果 (14) 6.源代码(带注释) (16) 总结 (23) 参考文献 (24) 致谢 (25) 附件I部分源代码: (26) 敢死队问题是二战时期攻城方为了突破桥对面敌人的碉堡而产生的一类问题,它和我们所说的约瑟夫换问题有一定的联系,或者应该说是有点儿类似,从根本上讲就是从围成一圈的人(数字),按照一定的规则由某一个数开始,以一定的基数为一个密码,顺序性的取出密码的终结者,而后以终结者以后的第一人(数字)并且以当前刚刚跳出的终结者所给与的密码为基数,再一次开始顺序性取出 关键字:单循环链表,循环队列,线性表,C语言 数据结构是研究数据元素之间的逻辑关系的一门课程,以及数据元 素及其关系在计算机中的存储表示和对这些数据所施加的运算该课程 设计的目的是通过课程设计的综合训练,培养分析和编程等实际动手能力,系统掌握数据结构这门课程的主要内容。
本次课程设计的内容是敢死队问题,循环链表是一种首尾相接链表,其特点是无须增加存储容量,仅对表的链接方式稍作改变,使表处 理更加灵活队列是另一种限定性的线性表,它只允许在表的一端插入 元素,而在另一端删除元素,所以队列具有先进先出的特性而敢死队 问题就是对子类问题的先进性的应用,通过这个设计事例,我们有理由 相信至此以后,我们对循环链表和循环队列的理解将会是更上一层楼 通过该课程设计,能运用所学知识,能上机解决一些实际问题,了解并初步掌握设计、实现较大程序的完整过程,包括系统分析、编码设计、以及调试分析,熟练掌握数据结构的选择、设计、实现以及操作方法,为进一步的应用开发打好基础 1.采用类c语言定义相关的数据类型 a.循环单链表存储结构 typedef struct node { int data; struct node *next; }LNode;/* 定义结点类型 */ b.线性表存储结构 #define LIST_INIT_SIZE 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; c.循环队列存储结构 #define QueueSize 1000 //假定预分配的队列空间最多为1000个元素typedef struct{ int data[QueueSize]; int front; int rear; int count; //计数器,记录队中元素总数 }CirQueue; 2.各模块的伪码算法 创建循环链表: LNode* CREAT(int n) /* 创建循环链表 */ { LNode *s,*q,*T; int i; if(n!=0) { T=q=(LNode *)malloc(sizeof(LNode)); q->data=1;/* 生成第一个结点并使其data值为1 */ for(i=2;inext=s; q->next->data=i;/*赋值*/ q=q->next; } q->next=T; } return T; } 链表的删除: DELETE (LNode* T,int m)/* 链表的删除 */ { LNode *a;int i; while (T->next!=T) { for (i=1;inext; a=T->next; T->next=a->next; free(a); T=T->next; } printf("\n"); return (T->data); } 创建线性表: int InitList_Sq( SqList &L) /*创建线性表函数*/ { L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) { printf("存储分配失败"); return ERROR; } else { L.length=0; /*空表长度为0*/ L.listsize=LIST_INIT_SIZE; return OK;/*初始存储容量*/ } } 线性表再分配: int ListInsert_Sq(SqList &L) /*线性表再分配函数*/ { /*SqList L;*/ int *newbase; newbase=(ElemType *)realloc(L.elem, (L.listsize+LISTINCCREMENT)*sizeof(ElemType)); /*为顺序表增加一个大小为存储LISTINCCREMENT个数据元素的空间*/ if(!newbase) {printf("存储分配失败"); return ERROR;} else { L.elem=newbase; /*新基址*/ L.listsize+=LISTINCCREMENT; /*增加存储容量*/ return OK; } } 队列初始化: void Initial(CirQueue *Q) {//将顺序队列置空 Q->front=Q->rear=0; Q->count=0; //计数器置 } 判队列空: int Empty(CirQueue *Q) { return Q->front==Q->rear; } 判队列满: int Full(CirQueue *Q) { return Q->rear==QueueSize-1+Q->front; } 进队列: void EnQueue(CirQueue *Q,int x) { if (Full(Q)) { printf("队列上溢"); //上溢,退出运行 exit(1); } Q->count ++; //队列元素个数加 Q->data[Q->rear]=x; //新元素插入队尾 Q->rear=(Q->rear+1)%QueueSize; //循环意义下将尾指针加} 出队列: int DeQueue(CirQueue *Q) { int temp; if(Empty(Q)) { printf("队列为空"); //下溢,退出运行 exit(1); } temp=Q->data[Q->front]; Q->count--; //队列元素个数减 Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1 return temp; } 3.函数的关系调用图 系统结构图 本程序有四个功能模块,包括三个解决敢死队问题方案的模块和一个退出系统模块。
三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构功能模块如下图所示 功能模块具体简介如下: (1).循环单链表 以单循环链表为存储结构,包含三个模块: a.主程序模块: 包含敢死队人数的输入,死亡数字的输入,函数的调用,结果的输出 b.构造链表并初始化: 构造链表,给每个结点赋值,给队员编号 敢死队问题 循环单链表储存结构 线性表储存结构 循环队列储存结构 退出 c.删除: 当报数到死亡数字时队员出列去执行任务,删除该节点 (2)线性表储存结构 功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的: 定义类类型 a.定义变量并初始化 b.线性表初始化 c.当队员数小于等于1时,输出结果算法流程图 (3)循环队列储存结构解决 。
