敢死队问题

洛阳理工学院课程设计报告1洛阳理工学院课程设计报告课程名称数据结构课程设计设计题目敢死队问题洛阳理工学院课程设计报告2课程设计任务书设计题目：敢死队问题设计内容与要求：有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。【基本要求】至少采用两种不同的数据结构的方法实现。课程设计评语成绩：指导教师：_______________年月日1.数据结构洛阳理工学院课程设计报告3数据结构中涉及的类型定义a.循环单链表存储结构typedefstructnode{intdata;structnode*next;}LNode;/*定义结点类型*/b.线性表存储结构#defineLIST_INIT_SIZE100#defineLISTINCCREMENT10#defineOK1#defineERROR0typedefintElemType;typedefstructKList/*定义数据结构体类型*/{ElemType*elem;/*存储空间基址*/intlength;/*当前长度*/intlistsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/}SqList;c.循环队列存储结构#defineQueueSize1000//假定预分配的队列空间最多为1000个元素typedefstruct{intdata[QueueSize];intfront;intrear;intcount;//计数器，记录队中元素总数}CirQueue;2.总体设计1.系统结构图本程序有四个功能模块，包括三个解决敢死队问题方案的模块和一个退出系统模块。三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构。功能模块如下图所示。洛阳理工学院课程设计报告4功能模块具体简介如下：1.循环单链表以单循环链表为存储结构，包含三个模块：a.主程序模块:包含敢死队人数的输入，死亡数字的输入，函数的调用，结果的输出。b.构造链表并初始化:构造链表，给每个结点赋值，给队员编号。c．删除:当报数到死亡数字时队员出列去执行任务，删除该节点。算法流程图敢死队问题循环单链表储存结构线性表储存结构循环队列储存结构退出洛阳理工学院课程设计报告52.线性表储存结构功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的:定义类类型a.定义变量并初始化b.线性表初始化c.当队员数小于等于1时,输出结果算法流程图开始声明类型定义变量并初始化初始化单链表循环模块输入敢死队员总数剩下的队员数1?队员报数报数值=死亡队员出列输出结果洛阳理工学院课程设计报告63.循环队列储存结构解决功能设计本程序其实质是约瑟夫环问题,本次实验用了循环队列数据结构,并运用模块化的程序设计思想,算法的实现是这样的:这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报敢死队员人数线性表长度开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数增加存储分配队员报数报数值=5？队员出列剩下的队员数1?输出洛阳理工学院课程设计报告7数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。算法流程图洛阳理工学院课程设计报告83.测试与调试1.调试中遇到的问题及对问题的解决方法编号=1？开始声明数据类型定义变量并初始化初始化循环队列输入敢死队员总数队列满？队员报数报数值=5?队员出列即清零剩下的队员输出增加存储分配给队员编号入队列洛阳理工学院课程设计报告9(1).函数调用:函数调用是语言中一块十分重要部分，它可以把一个程序分成若干部分，然后进行配置，所以这块内容对我们很重要。(2).循环的问题:大量的循环语句的应用，分析使我很头疼，循环是计算机语言中很重要的部分，什么程序也离不开循环，这个问题的解决使我有了坚实的基础。对多层循环的应用也有了深刻的理解。2.算法的时间复杂度和空间复杂度算法的时间复杂度是指算法在编程后在机器中所耗费的时间。在创建单链表的算法中时间复杂度为O（n），在单链表删除算法中时间复杂度为O（m），其他算法的时间复杂度为O（1）。算法的空间复杂度是指算法在编程后在机器中所占的存储量。程序的空间复杂度为S(n)。4.测试结果进入用户主界面，选择实现结果的方法运用循环链表存储结构,以10个队员，死亡数字为5来运行，结果如下洛阳理工学院课程设计报告10选择第2项功能，运用线性表储存结构,输入敢死队人数和死亡人数选择第3项功能，运用循环队列来实现结果.输入敢死队人数和死亡人数洛阳理工学院课程设计报告115.源程序清单#includestdio.h#includestring.h#includestdlib.h#includemalloc.h//-------------------循环单链表----------------------------------------------typedefstructnode{intdata;structnode*next;}LNode;/*定义结点类型*/LNode*CREAT(intn)/*创建循环链表*/{LNode*s,*q,*T;inti;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;}洛阳理工学院课程设计报告12q-next=T;}returnT;}DELETE(LNode*T,intm)/*链表的删除*/{LNode*a;inti;while(T-next!=T){for(i=1;im-1;i++)/*查找要删除结点的前一结点*/T=T-next;a=T-next;T-next=a-next;free(a);T=T-next;}printf(\n);return(T-data);}//-------------------------------------------------------------------------//----------------线性表-----------------------------------------------------#defineLIST_INIT_SIZE100#defineLISTINCCREMENT10#defineOK1#defineERROR0typedefintElemType;typedefstructKList/*定义数据结构体类型*/{ElemType*elem;/*存储空间基址*/intlength;/*当前长度*/intlistsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/}SqList;intInitList_Sq(SqList&L)/*创建线性表函数*/{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem){printf(存储分配失败);returnERROR;}else洛阳理工学院课程设计报告13{L.length=0;/*空表长度为0*/L.listsize=LIST_INIT_SIZE;returnOK;/*初始存储容量*/}}intListInsert_Sq(SqList&L)/*线性表再分配函数*/{/*SqListL;*/int*newbase;newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCCREMENT)*sizeof(ElemType));/*为顺序表增加一个大小为存储LISTINCCREMENT个数据元素的空间*/if(!newbase){printf(存储分配失败);returnERROR;}else{L.elem=newbase;/*新基址*/L.listsize+=LISTINCCREMENT;/*增加存储容量*/returnOK;}}//-----------------------------------------------------------------------------//---------------------循环队列-----------------------------------------------#defineQueueSize1000//假定预分配的队列空间最多为1000个元素typedefstruct{intdata[QueueSize];intfront;intrear;intcount;//计数器，记录队中元素总数}CirQueue;voidInitial(CirQueue*Q){//将顺序队列置空Q-front=Q-rear=0;Q-count=0;//计数器置}//判队列空intEmpty(CirQueue*Q)洛阳理工学院课程设计报告14{returnQ-front==Q-rear;}//判队列满intFull(CirQueue*Q){returnQ-rear==QueueSize-1+Q-front;}//进队列voidEnQueue(CirQueue*Q,intx){if(Full(Q)){printf(队列上溢);//上溢,退出运行exit(1);}Q-count++;//队列元素个数加Q-data[Q-rear]=x;//新元素插入队尾Q-rear=(Q-rear+1)%QueueSize;//循环意义下将尾指针加1}//出队列intDeQueue(CirQueue*Q){inttemp;if(Empty(Q)){printf(队列为空);//下溢,退出运行exit(1);}temp=Q-data[Q-front];Q-count--;//队列元素个数减Q-front=(Q-front+1)%QueueSize;//循环意义下的头指针加1returntemp;}//-----------------------------------------------------------------------------voidmain(){SqListL;ints,i,m,count=0;/*声明变量*/LNode*p;intz,y;洛阳理工学院课程设计报告15intnum;intopt;abc:printf(_____________________________________\n);printf(|1.循环链表|\n);printf(|2.线性表|\n);printf(|3.循环队列|\n);printf(|4.退出|\n);printf(_____________________________________\n);printf(请选择实现结果的方法：（1~4）\n\n);scanf(%d,&opt);if(opt4||opt1){printf(输入有误请重新输入\n);gotoabc;}switch(opt){case1:system(cls);printf(您使用是循环链表