数据结构课程设计报告敢死队问题 (2)

黑龙江科技大学课程设计说明书（数据结构课程设计）班级:统计12-1姓名:包旭学号：2012027159设计题目：敢死队问题设计时间:__2013-11-5_____至___2013-11-25____指导教师:________________________评语:____________________________________________________________________________________________________________________________________________________________________________________________________评阅成绩:＿＿＿＿评阅教师:＿＿＿＿＿22《数据结构》课程设计实验报告开课实验室：基础实验室一2013年11月16日实验题目敢死队问题1.实验题目敢死队问题2.实验设备及环境PC兼容机、Windows操作系统、VB软件等。3.功能模块简介和系统结构图系统结构图本程序有四个功能模块，包括三个解决敢死队问题方案的模块和一个退出系统模块。三个解决方案分别采用了循环聊表储存结构、线性表储存结构、循环队列储存结构。功能模块如下图所示。功能模块具体简介如下：(1).循环单链表以单循环链表为存储结构，包含三个模块：1.主程序模块包含敢死队人数的输入，死亡数字的输入，函数的调用，结果的输出。2.构造链表并初始化构造链表，给每个结点赋值，给队员编号。3．删除当报数到死亡数字时队员出列去执行任务，删除该节点。敢死队问题循环单链表储存结构线性表储存结构循环队列储存结构退出33（2）.线性表储存结构功能设计本程序其实质是约瑟夫环问题,本次实验用了线性表数据结构,并运用模块化的程序设计思想,算法的实现是这样的:定义类类型1.定义变量并初始化2.线性表初始化3.当队员数小于等于1时,输出结果开始声明类型定义变量并初始化初始化单链表循环模块输入敢死队员总数剩下的队员数1?队员报数报数值=死亡数?队员出列输出结果44算法流程图循环队列储存结构解决功能设计本程序其实质是约瑟夫环问题,本次实验用了循环队列数据结构,并运用模块化的程序设计思想,算法的实现是这样的:这个方法是用队列循环来做的，实现的方法是这样的：首先从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后再比较一下它的号码是不是等于1，如果等于则输出开始计数位置，如果不等，继续循环查找，直到找出符合条件的计数起始位置，输出结果。开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数敢死队员人数线性表长度队员报数报数值=5？队员出列剩下的队员数1?输出增加存储分配55算法流程图4.系统的主要界面设计及运行说明：开始声明数据类型定义变量并初始化初始化循环队列输入敢死队员总数队列满？队员报数报数值=5?队员出列即清零剩下的队员数1?输出增加存储分配编号=1？给队员编号入队列66进入用户主界面，选者实现结果的方法以10个队员，死亡数字为5来运行，结果如下选择第2项功能，运用线性表储存结构77选择第3项功能，运用循环队列来实现结果5.程序的主要代码：#includestdio.h#includestring.h#includestdlib.h#includemalloc.h//-------------------循环单链表----------------------------------------------typedefstructnode{intdata;structnode*next;}LNode;/*定义结点类型*/88LNode*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;}q-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;/*存储空间基址*/99intlength;/*当前长度*/intlistsize;/*当前分配的存储容量(以sizeof(ElemType)为单位)*/}SqList;intInitList_Sq(SqList&L)/*创建线性表函数*/{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem){printf(存储分配失败);returnERROR;}else{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;//计数器，记录队中元素总数1010}CirQueue;voidInitial(CirQueue*Q){//将顺序队列置空Q-front=Q-rear=0;Q-count=0;//计数器置}//判队列空intEmpty(CirQueue*Q){returnQ-front==Q-rear;}//判队列满intFull(CirQueue*Q){returnQ-rear==QueueSize-1+Q-front;}//进队列voidEnQueue(CirQueue*Q,intx){if(IsFull(Q)){printf(队列上溢);//上溢,退出运行exit(1);}Q-count++;//队列元素个数加Q-data[Q-rear]=x;//新元素插入队尾Q-rear=(Q-rear+1)%QueueSize;//循环意义下将尾指针加}//出队列intDeQueue(CirQueue*Q){inttemp;if(IsEmpty(Q)){printf(队列为空);//下溢,退出运行exit(1);}temp=Q-data[Q-front];Q-count--;//队列元素个数减1111Q-front=(Q-front+1)%QueueSize;//循环意义下的头指针加1returntemp;}//-----------------------------------------------------------------------------voidmain(){SqListL;ints,i,m,count=0;/*声明变量*/LNode*p;intz,y;intnum;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(您使用是循环链表储存结构\n\n);efg:printf(请输入敢死队的人数：\n);scanf(%d,&num);if(num1){printf(输入有误请重新输入\n);gotoefg;1212}printf(请输入死亡数数字\n);m:scanf(%d,&m);if(mnum||m1){printf(输入有误请重新输入);gotom;}else{p=CREAT(num);y=DELETE(p,m);z=num-y+2;if(z%num==0)printf(从第%dth:开始计数\n,z);elseprintf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。\n,(num-y+2)%num);}break;case2:system(cls);printf(您使用的是线性表储存结构\n\n);e:printf(请输入敢死队的人数：\n);scanf(%d,&num);if(num1){printf(输入有误请重新输入\n);gotoe;}m=5;InitList_Sq(L);while(numL.listsize)/*当顺序表当前分配的存储空间大小不足时进行再分配*/ListInsert_Sq(L);for(i=0;inum;i++)L.elem[i]=i+1;/*为队员赋值*/s=num;i=0;while(s1)/*当所剩敢死队员总数为1时,总循环结束*/{for(i=0;inum;i++)if(L.elem[i]!=0)1313{count++;if(count==5)/*报数循环*/{L.elem[i]=0;/*表示队员出列*/count=0;/*计数器清零*/s--;/*敢死队员数-1*/}}}for(i=0;inum;i++)/*输出*/if(L.elem[i]!=0)if((num-L.elem[i]+2)%num==0)printf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。\n,num);elseprintf(从第%d号战士开始计数才能让排长最后一个留下来而不去执行任务。\n,