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

1目录一．问题描述二.线性表数据结构（一）.需求分析（二）.概要设计（三）.详细设计（四）.程序调试及运行（五）.设计总结（六）.附件三.单循环链表数据结构（一）.需求分析（二）.概要设计（三）.详细设计2（四）.程序调试及运行（五）.设计总结（六）.附件一．问题描述敢死队问题有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。要求：至少采用两种不同的数据结构的方法实现。二．线性表数据结构(一)、需求分析1.本程序输入队伍人数n为任意的，最终输出记数的初始位置，首先输入一个报数上限m，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，通过数学思想求得题目要求即队长为首的情况下需要记数初始位置。2.程序执行的命令包括：（1）构造数据结构；（2）数据输入；（3）执行队员出列；（4）输出要求数值（5）结束。3.数据测试：当n=10输出结果为：要求的位置是：93（二）、概要设计算法思想:本程序其实质是约瑟夫环问题,本次实验用了线性表和循环队列两种数据结构,并运用模块化的程序设计思想,算法的实现是这样的:1.定义结构体类型2.定义变量并初始化3.线性表初始化4.队员报数,是5的倍数出列5.当队员数等于1时,输出程序框图:4（三）、详细设计宏定义:开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数敢死队员人数线性表长度队员报数报数值=偏移值?队员出列即L.elem[i]清零剩下的队员数1?输出增加存储分配5#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:);6scanf(%d,&m);/*输入敢死队员总数*/while(m!=0)/*当输入为0时退出程序*/{while(mL.length)/*当顺序表当前分配的存储空间大小不足时进行再分配*/L=ListInsert_Sq(L);for(i=0;im;i++)L.elem[i]=i+1;/*为队员赋值*/s=m;i=0;while(s1)/*当所剩敢死队员总数为1时,总循环结束*/{for(i=0;im;i++)if(L.elem[i]!=0){count++;if(count==5)/*报数循环*/{L.elem[i]=0;/*表示队员出列*/count=0;/*计数器清零*/s--;/*敢死队员数-1*/}}}for(i=0;im;i++)/*输出*/if(L.elem[i]!=0)if((m-L.elem[i]+2)%m==0)/**/printf(\nThewantedorderis%dth\n,m);elseprintf(\nThewantedorderis%dth\n,(m-L.elem[i]+2)%m);printf(Exitpleaseinput'0'OrGoon...\nPleaseinputthetataloftheteam:);scanf(%d,&m);/*输入敢死队员总数*/}}思考：本次设计问题的核心是如何输出，因为这影响到了程序的时间复杂度。总模块的输出设计是这样实现的：总是从第一个开始报数，报到5出列，直到剩下最后一个为止，然后就令这个位置为队长位置，队首为开始报数的位置，并按此设计输出即可。这种方法大大的降低了时间复杂度，其复杂度为O(mn)。（四）、程序调试及运行程序调试过程中出现了下面的警告:7经查询错误为:不可移动的指针（地址常数）赋值最终发现是下面的定义错误造成的在变量定义中int*newbase=0;定义成了intnewbase=0;经改正程序运行正常了.数据测试如下：时间复杂度为O(mn)（五）、设计总结8通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构编程。我首先是用线性表来做的，开始的想法是想用试验的方法来查找到所要求的位置，即首先从第一号开始报数，然后检查最后剩下的一个是否是队首，然后从第二个开始报数……从第三个开始报数……直到所剩下的最后一个是队首。虽然这种方法可以实现查找，可却是以消耗更多的时间为代价的，于是我又想到了这个方法：总是从第一个开始报数，报到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;/*增加存储容量*/}9}main(){SqListL;ints,i,m,count=0;/*声明变量*/L=InitList_Sq();printf(Pleaseinputthetataloftheteam:);scanf(%d,&m);/*输入敢死队员总数*/while(m!=0)/*当输入为0时退出程序*/{while(mL.length)/*当顺序表当前分配的存储空间大小不足时进行再分配*/L=ListInsert_Sq(L);for(i=0;im;i++)L.elem[i]=i+1;/*为队员赋值*/s=m;i=0;while(s1)/*当所剩敢死队员总数为1时,总循环结束*/{for(i=0;im;i++)if(L.elem[i]!=0){count++;if(count==5)/*报数循环*/{L.elem[i]=0;/*表示队员出列*/count=0;/*计数器清零*/s--;/*敢死队员数-1*/}}}for(i=0;im;i++)/*输出*/if(L.elem[i]!=0)if((m-L.elem[i]+2)%m==0)/**/printf(\nThewantedorderis%dth\n,m);elseprintf(\nThewantedorderis%dth\n,(m-L.elem[i]+2)%m);printf(Exitpleaseinput'0'OrGoon...\nPleaseinputthetataloftheteam:\n);scanf(%d,&m);/*输入敢死队员总数*/}}三.单循环链表数据结构10(一)、需求分析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);do11{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．构造单循环链表并初始化模块：L