敢死队问题.doc

洛 阳 理 工 学 院 课 程 设 计 报 告洛 阳 理 工 学 院课 程 设 计 报 告 课程名称 数据结构课程设计 设计题目 敢死队问题 课 程 设 计 任 务 书设计题目： 敢死队问题 设计内容与要求：有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。【基本要求】至少采用两种不同的数据结构的方法实现。 课 程 设 计 评 语 成绩： 指导教师：_ 年 月 日1.数据结构数据结构中涉及的类型定义a.循环单链表存储结构typedef struct node int data; struct node *next;LNode;/* 定义结点类型 */ b.线性表存储结构#define LIST_INIT_SIZE 100#define LISTINCCREMENT 10#define OK 1#define ERROR 0typedef int ElemType;typedef struct KList /*定义数据结构体类型*/ElemType *elem; /*存储空间基址*/int length; /*当前长度*/int listsize; /*当前分配的存储容量(以sizeof(ElemType)为单位)*/SqList;c.循环队列存储结构#define QueueSize 1000 /假定预分配的队列空间最多为1000个元素typedef struct int dataQueueSize; int front;int rear; int count; /计数器，记录队中元素总数CirQueue;2.总体设计1.系统结构图本程序有四个功能模块，包括三个解决敢死队问题方案的模块和一个退出系统模块。三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构。功能模块如下图所示。敢死队问题循环单链表储存结构线性表储存结构循环队列储存结构退出功能模块具体简介如下：1.循环单链表以单循环链表为存储结构，包含三个模块： a.主程序模块: 包含敢死队人数的输入，死亡数字的输入，函数的调用，结果的输出。b.构造链表并初始化: 构造链表，给每个结点赋值，给队员编号。c删除: 当报数到死亡数字时队员出列去执行任务，删除该节点。算法流程图开始声明类型定义变量并初始化初始化单链表循环模块输入敢死队员总数剩下的队员数1?队员报数报数值=死亡队员出列输出结果2.线性表储存结构功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的:定义类类型a.定义变量并初始化b.线性表初始化c.当队员数小于等于1时,输出结果算法流程图敢死队员人数线性表长度开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数增加存储分配队员报数报数值=5？队员出列剩下的队员数1?输出3.循环队列储存结构解决功能设计本程序其实质是约瑟夫环问题,本次实验用了循环队列数据结构,并运用模块化的程序设计思想,算法的实现是这样的:这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。算法流程图编号=1？开始声明数据类型定义变量并初始化初始化循环队列输入敢死队员总数队列满？队员报数报数值=5?队员出列即清零剩下的队员输出增加存储分配给队员编号入队列3.测试与调试1.调试中遇到的问题及对问题的解决方法(1).函数调用:函数调用是语言中一块十分重要部分，它可以把一个程序分成若干部分，然后进行配置，所以这块内容对我们很重要。(2).循环的问题:大量的循环语句的应用，分析使我很头疼，循环是计算机语言中很重要的部分，什么程序也离不开循环，这个问题的解决使我有了坚实的基础。对多层循环的应用也有了深刻的理解。2.算法的时间复杂度和空间复杂度 算法的时间复杂度是指算法在编程后在机器中所耗费的时间。在创建单链表的算法中时间复杂度为O（n），在单链表删除算法中时间复杂度为O（m），其他算法的时间复杂度为O（1）。算法的空间复杂度是指算法在编程后在机器中所占的存储量。程序的空间复杂度为S(n)。4.测试结果进入用户主界面，选择实现结果的方法运用循环链表存储结构,以10个队员，死亡数字为5来运行，结果如下选择第2项功能，运用线性表储存结构,输入敢死队人数和死亡人数 选择第3项功能，运用循环队列来实现结果.输入敢死队人数和死亡人数 5.源程序清单#include #include#include#include/-循环单链表-typedef struct node int data; struct node *next;LNode;/* 定义结点类型 */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);/- /-线性表-#define LIST_INIT_SIZE 100#define LISTINCCREMENT 10#define OK 1#define ERROR 0typedef int ElemType;typedef struct KList /*定义数据结构体类型*/ElemType *elem; /*存储空间基址*/int length; /*当前长度*/int listsize; /*当前分配的存储容量(以sizeof(ElemType)为单位)*/SqList;int InitList_Sq(SqList &L) /*创建线性表函数*/L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType); if(!L.elem)printf(存储分配失败);return ERROR; elseL.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; /-/-循环队列-#define QueueSize 1000 /假定预分配的队列空间最多为1000个元素typedef struct int dataQueueSize; int front;int rear; int count; /计数器，记录队中元素总数CirQueue;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-dataQ-rear=x; /新元素插入队尾Q-rear=(Q-rear+1)%QueueSize; /循环意义下将尾指针加1 /出队列int DeQueue(CirQueue *Q) int temp; if(Empty(Q) printf(队列为空); /下溢,退出运行exit(1); temp=Q-dataQ-front; Q-count-; /队列元素个数减Q-front=(Q-front+1)%QueueSize; /循环意义下的头指针加1return temp; /-void main () SqList L; int s,i,m,count=0; /*声明变量*/ LNode *p; int z,y; int num;int opt; abc: printf(_n);printf(| 1.循环链表 |n);printf(| 2.线性表 |n);printf(| 3.循环队列 |n);printf(| 4.退出 |n); printf(_n);printf(请选择实现结果的方法：（14）nn);scanf(%d,&opt);if(opt4 | opt1) printf(输入有误请重新输入n);goto abc;switch(opt)case 1:system(cls);printf(您使用是循环链表储存结构nn);efg:printf(请输入敢死队的人数：n);scanf(%d,&num);if(numnum | m1) printf(输入有误请重新输入); goto m; else p=CREAT(num); y=DELETE(p,m); z=num-y+2; if(z%num=0) printf (从第 %dth:开始计数n,z); else printf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n,(num-y+2)%num);break;case 2:system(cls);printf(您使用的是线性表储存结构nn);e:printf(请输入敢死队的人数：n);scanf(%d,&num);if(numL.listsize ) /*当顺序表当前分配的存储空间大小不足时进行再分配*/ ListInsert_Sq(L); for(i=0;i1) /*当所剩敢死队员总数为1时,总循环结束*/ for(i=0;inum;i+) if(L.elemi!=0) count+; if(count=5) /*报数循环*/ L.elemi=0; /*表示队员出列*/ count=0; /*计数器清零*/ s-; /*敢死队员数-1*/ for(i=0;inum;i+) /*输出*/if(L.elemi!=0)if(num-L.elemi+2)%num=0) printf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n,num);elseprintf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n,(num-L.elemi+2)%num); break;case 3:system(cls);printf(您使用的是循环队列储存结构nn);int start,count,j; CirQueue s; g:printf(请输入敢死队的人数：n);scanf(%d,&num);if(num1)printf(输入有误请重新输入n);goto g;for(start=1;start=num;start+)/start为测试起点 Initial(&s); for(i=1;i=num;i+) EnQueue(&s,i); for(i=1;istart;i+) j=DeQueue(&s); EnQueue(&s,j); count=1; while(countnum) for(i=1;i5;i+) j=DeQueue(&s); EnQueue(&s,j); j=DeQueue(&s); count+; if(s.datas.front=1) break; printf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。n,start); break; case 4:exit(0);goto abc; 6.总结 我这次的课程设计为敢死队问题，通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌握了课本中所学的各种数据结构，尤其是对单循环链表上基本运算及队列的实现,学会了如何把学到的