敢死队问题数据结构课程设计

目录HYPERLINK一．问题描述HYPERLINK二.线性表数据结构HYPERLINK（一）.需求分析HYPERLINK（二）.概要设计HYPERLINK（三）.具体设计HYPERLINK（四）.程序调试及运营HYPERLINK（五）.设计总结HYPERLINK（六）.附件HYPERLINK三.单循环链表数据结构（一）.需求分析（二）.概要设计（三）.具体设计（四）.程序调试及运营（五）.设计总结（六）.附件一．问题描述敢死队问题有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。假如前一个战士没完毕任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，相应的战士就去执行任务，且此战士不再参与下一轮计数。假如此战士没完毕任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完毕为止。排长是不乐意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才干让排长最后一个留下来而不去执行任务。规定：至少采用两种不同的数据结构的方法实现。二．线性表数据结构(一)、需求分析1.本程序输入队伍人数n为任意的，最终输出记数的初始位置，一方面输入一个报数上限m，当达成报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，通过数学思想求得题目规定即队长为首的情况下需要记数初始位置。2.程序执行的命令涉及：（1）构造数据结构；（2）数据输入；（3）执行队员出列；（4）输出规定数值（5）结束。3.数据测试：当n=10输出结果为：规定的位置是：9（二）、概要设计算法思想:本程序其实质是约瑟夫环问题,本次实验用了线性表和循环队列两种数据结构,并运用模块化的程序设计思想,算法的实现是这样的:定义结构体类型定义变量并初始化线性表初始化队员报数,是5的倍数出列当队员数等于1时,输出程序框图:开始开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数敢死队员人数>线性表长度队员报数报数值=偏移值?队员出列即L.elem[i]清零剩下的队员数>1?输出增长存储分派（三）、具体设计宏定义:#defineLIST_INIT_SIZE100#defineLISTINCCREMENT10数据类型定义:typedefintElemType;定义数据结构:typedefstructKList/*定义数据结构体类型*/{ ElemType*elem;/*存储空间基址*/ intlength;/*当前长度*/ intlistsize;/*当前分派的存储容量(以sizeof(ElemType)为单位)*/}SqList;模块一:创建线性表函数SqListInitList_Sq()/*创建线性表函数*/{ SqListL; L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));/**/ if(!L.elem)printf("Failinnewcreatlist"),exit(0);/*存储分派失败*/ else { L.length=0;/*空表长度为0*/ L.listsize=LIST_INIT_SIZE;/*初始存储容量*/ }}模块二:线性表再分派函数SqListListInsert_Sq(SqListL)/*线性表再分派函数*/{ /*SqListL;*/ int*newbase; newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCCREMENT)*sizeof(ElemType));/*为顺序表增长一个大小为存储LISTINCCREMENT个数据元素的空间*/ if(!newbase)printf("Failinnewaddlist"),exit(0);/*存储分派失败*/else{L.elem=newbase;/*新基址*/L.listsize+=LISTINCCREMENT;/*增长存储容量*/}}主模块:实现总体功能main(){SqListL; ints,i,m,count=0;/*声明变量*/L=InitList_Sq(); printf("Pleaseinputthetataloftheteam:"); scanf("%d",&m);/*输入敢死队员总数*/while(m!=0)/*当输入为0时退出程序*/{while(m>L.length)/*当顺序表当前分派的存储空间大小局限性时进行再分派*/ L=ListInsert_Sq(L); for(i=0;i<m;i++)L.elem[i]=i+1;/*为队员赋值*/ s=m; i=0; while(s>1)/*当所剩敢死队员总数为1时,总循环结束*/ { for(i=0;i<m;i++) if(L.elem[i]!=0) { count++; if(count==5)/*报数循环*/ { L.elem[i]=0;/*表达队员出列*/ count=0;/*计数器清零*/ s--;/*敢死队员数-1*/ } } } for(i=0;i<m;i++)/*输出*/ if(L.elem[i]!=0) if((m-L.elem[i]+2)%m==0)/**/ printf("\nThewantedorderis%dth\n",m); else printf("\nThewantedorderis%dth\n",(m-L.elem[i]+2)%m);printf("Exitpleaseinput'0'OrGoon...\nPleaseinputthetataloftheteam:"); scanf("%d",&m);/*输入敢死队员总数*/}}思考：本次设计问题的核心是如何输出，由于这影响到了程序的时间复杂度。总模块的输出设计是这样实现的：总是从第一个开始报数，报到5出列，直到剩下最后一个为止，然后就令这个位置为队长位置，队首为开始报数的位置，并按此设计输出即可。这种方法大大的减少了时间复杂度，其复杂度为O(mn)。（四）、程序调试及运营程序调试过程中出现了下面的警告:经查询错误为:不可移动的指针（地址常数）赋值最终发现是下面的定义错误导致的在变量定义中int*newbase=0;定义成了intnewbase=0;经改正程序运营正常了.数据测试如下：时间复杂度为O(mn)（五）、设计总结通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构编程。我一方面是用线性表来做的，开始的想法是想用实验的方法来查找到所规定的位置，即一方面从第一号开始报数，然后检查最后剩下的一个是否是队首，然后从第二个开始报数……从第三个开始报数……直到所剩下的最后一个是队首。虽然这种方法可以实现查找，可却是以消耗更多的时间为代价的，于是我又想到了这个方法：总是从第一个开始报数，报到5出列，直到剩下最后一个为止，然后就令这个位置为队长位置，队首为开始报数的位置，并按此设计输出即可。这种方法大大的减少了时间复杂度，复杂度为O(mn)。（六）、附件程序源代码:#defineLIST_INIT_SIZE100#defineLISTINCCREMENT10typedefintElemType;typedefstructKList/*定义数据结构体类型*/{ ElemType*elem;/*存储空间基址*/ intlength;/*当前长度*/ intlistsize;/*当前分派的存储容量(以sizeof(ElemType)为单位)*/}SqList;SqListInitList_Sq()/*创建线性表函数*/{ SqListL; L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));/**/ if(!L.elem)printf("Failinnewcreatlist"),exit(0);/*存储分派失败*/ else { L.length=0;/*空表长度为0*/ L.listsize=LIST_INIT_SIZE;/*初始存储容量*/ }}SqListListInsert_Sq(SqListL)/*线性表再分派函数*/{ /*SqListL;*/ int*newbase; newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCCREMENT)*sizeof(ElemType));/*为顺序表增长一个大小为存储LISTINCCREMENT个数据元素的空间*/ if(!newbase)printf("Failinnewaddlist"),exit(0);/*存储分派失败*/else{L.elem=newbase;/*新基址*/L.listsize+=LISTINCCREMENT;/*增长存储容量*/}}main(){SqListL; ints,i,m,count=0;/*声明变量*/L=InitList_Sq(); printf("Pleaseinputthetataloftheteam:"); scanf("%d",&m);/*输入敢死队员总数*/while(m!=0)/*当输入为0时退出程序*/{while(m>L.length)/*当顺序表当前分派的存储空间大小局限性时进行再分派*/ L=ListInsert_Sq(L); for(i=0;i<m;i++)L.elem[i]=i+1;/*为队员赋值*/ s=m; i=0; while(s>1)/*当所剩敢死队员总数为1时,总循环结束*/ { for(i=0;i<m;i++) if(L.elem[i]!=0) { count++; if(count==5)/*报数循环*/ { L.elem[i]=0;/*表达队员出列*/ count=0;/*计数器清零*/ s--;/*敢死队员数-1*/ } } } for(i=0;i<m;i++)/*输出*/ if(L.elem[i]!=0) if((m-L.elem[i]+2)%m==0)/**/ printf("\nThewantedorderis%dth\n",m); else printf("\nThewantedorderis%dth\n",(m-L.elem[i]+2)%m);printf("Exitpleaseinput'0'OrGoon...\nPleaseinputthetataloftheteam:\n"); scanf("%d",&m);/*输入敢死队员总数*/}}三.单循环链表数据结构(一)、需求分析1.本程序输入队伍人数n为任意的，最终输出记数的初始位置，一方面输入一个报数上限m，当达成报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，通过数学思想求得题目规定即队长为首的情况下需要记数初始位置。2.程序执行的命令涉及：（1）构造链表；（2）数据输入；（3）执行删除；（4）输出规定数值（5）结束。3.数据测试：当n=10，m=5,输出结果为：规定的位置是：9(二)、概要设计以单循环链表为存储结构，包含三个模块：1.主程序模块2.构造链表并初始化3．删除结点(三)、具体设计1．结点类型和指针类型typedefstructnode{intdata;structnode*next;}LNode;/*定义结点类型*/LNode*p;2．每个模块的分析：主程序模块：main(){LNode*p;intm,n,z,y;do{printf("Pleaseinputthepeoplenumber:\n");scanf("%d",&n);}while(n<=0);do{printf("Pleaseinputtheexcursion:\n");scanf("%d",&m);}while(m<=0);if(n=1)printf("thepositionis:1");else{p=CREAT(n);y=DELETE(p,m);z=n-y+2;if(z%n==0)/*排除特殊情况*/printf("thepositionis:\n%d\n",z);elseprintf("thepositionis:\n%d\n",(n-y+2)%n);}/*通过数学思想求得实验规定情况下的数值*/}2．构造单循环链表并初始化模块：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;/*给第i个结点赋值i*/q=q->next;}q->next=t;}/*生成后续结点，并使其data值即为它所在链表（队伍）中的位置*/returnt;}3．删除结点模块：DELETE(LNode*t,intm)/*链表的删除*/{LNode*a;inti;while(t->next!=t){for(i=1;i<m-1;i++)/*查找要删除结点的前一结点*/t=t->next;a=t->next;t->next=a->next;free(a);/*释放结点*/t=t->next;}/*while循环依次删除被点到的士兵*/printf("\n");return(t->data);}(四)．调试分析：说明：（1）本程序的运营环境是TC（2）进入演示程序后显示提醒信息：Exitpleaseinput'0'OrGoonPleaseinputthetataloftheteam:输入队伍总人数Pleaseinputtheexcursion:输入间隔人数结果显示：Thewantedpositionisth选择的位置（3）调试程序调试过程中碰到如下警告：发现错误为if(m=1)后改正为if(m==1)程序运营对的了，运营如下：显示输出如图：(3)由程序分析可得：本程序时间复杂度为O（nm）!(4)①在设计生成循环单链表时，考虑到程序结果需要士兵的位序，故将每个结点的data值设立为他们在队列中的位置，方便返回。②在删除单链表时，假如在报数时直接数到出列士兵则不方便链表的删除，可设立i<m-1找到出列士兵的前一位执行如下：for(i=1;i<m-1;i++)/*查找要删除结点的前一结点*/t=t->next;a=t->next;t->next=a->next;free(a);/*释放结点*/t=t->next;③．在程序设计前，假如按原题所设，则需设队长为第一位，再分别测试从第几个开始才干符合条件。现在改变思想，通过数学思想：单循环链表自身是一个循环体，可先求出当从第一个出发的话，求出每隔m个出去一个最后是谁未出列，然后再设立它为链头，求出当他为队首时从第几个开始方能使其不出列。(n-y+2)%n即可实现这功能！(五)、设计总结通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构.这个方法是用单循环链表来做的，实现的方法是这样的：一方面从第一号开始报数，循环到指定的偏移位置删除结点，直至剩下一个结点。然后设计输出，令这个位置为队长位置，队首为开始报数的位置，并按此输出即为所求。这种方法大大的减少了时间复杂度，复杂度为O(mn)。(六)、附件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;/*给第i个结点赋值i*/ q=q->next;}q->next=t;}/*生成后续结点，并使其data值即为它所在链表（队伍）中的位置*/returnt;}DELETE(LNode*t,intm)/*链表的删除*/{LNode*a;inti;while(t->next!=t){for(i=1;i<m-1;i++)/*查找要删除结点的前一结点*/t=t->next;a=t->next;t->next=a->next;free(a);/*释放结点*/t=t->next;