敢死队问题数据结构专业课程设计.doc

目录一问题描述二. 线性表数据构造（一）. 需求分析（二）. 概要设计（三）. 详细设计（四）. 程序调试及运营（五）. 设计总结（六）. 附件三. 单循环链表数据构造（一）. 需求分析（二）. 概要设计（三）. 详细设计（四）. 程序调试及运营（五）. 设计总结（六）. 附件一问题描述敢死队问题 有M个敢死队员要炸掉敌人一碉堡，谁都不想去，排长决定用轮回数数办法来决定哪个战士去执行任务。如果前一种战士没完毕任务，则要再派一种战士上去。现给每个战士编一种号，人们围坐成一圈，随便从某一种战士开始计数，当数到5时，相应战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完毕任务，再从下一种战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完毕为止。 排长是不乐意去，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才干让排长最后一种留下来而不去执行任务。 规定：至少采用两种不同数据构造办法实现。二线性表数据构造(一)、需求分析1.本程序输入队伍人数n为任意，最后输出记数初始位置，一方面输入一种报数上限m，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中位置，通过数学思想求得题目规定即队长为首状况下 需要记数初始位置。2.程序执行命令涉及： （1）构造数据构造；（2）数据输入；（3）执行队员出列；（4）输出规定数值 （5）结束。3.数据测试：当 n=10 输出成果为：规定位置是：9（二）、概要设计算法思想：本程序其实质是约瑟夫环问题,本次实验用了线性表和循环队列两种数据构造,并运用模块化程序设计思想,算法实现是这样:1. 定义构造体类型2. 定义变量并初始化3. 线性表初始化4. 队员报数,是5倍数出列5. 当队员数等于1时,输出程序框图:开始声明数据类型定义变量并初始化初始化线性表输入敢死队员总数敢死队员人数线性表长度队员报数报数值=偏移值?队员出列即L.elemi清零剩余队员数1?输出增长存储分派（三）、详细设计宏定义:#define LIST_INIT_SIZE 100#define LISTINCCREMENT 10数据类型定义:typedef int ElemType;定义数据构造:typedef struct KList /*定义数据构造体类型*/ElemType *elem； /*存储空间基址*/int length； /*当前长度*/int listsize； /*当前分派存储容量(以sizeof(ElemType)为单位)*/SqList;模块一:创立线性表函数SqList InitList_Sq() /*创立线性表函数*/SqList L;L.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)；/*/if(!L.elem) printf(Fail in new creat list),exit(0)； /*存储分派失败*/elseL.length=0； /*空表长度为0*/L.listsize=LIST_INIT_SIZE；/*初始存储容量*/模块二：线性表再分派函数SqList ListInsert_Sq(SqList L) /*线性表再分派函数*/*SqList L;*/int *newbase;newbase=(ElemType *)realloc(L.elem, (L.listsize+LISTINCCREMENT)*sizeof(ElemType); /*为顺序表增长一种大小为存储LISTINCCREMENT个数据元素空间*/if(!newbase) printf(Fail in new add list),exit(0);/*存储分派失败*/ else L.elem=newbase； /*新基址*/ L.listsize+=LISTINCCREMENT； /*增长存储容量*/ 主模块:实现总体功能main() SqList L;int s,i,m,count=0； /*声明变量*/ L=InitList_Sq();printf(Please input the tatal of the team:);scanf(%d,&m)； /*输入敢死队员总数*/ while(m!=0)/*当输入为0时退出程序*/ while(mL.length) /*当顺序表当前分派存储空间大小局限性时进行再分派*/ L=ListInsert_Sq(L);for(i=0;i1) /*当所剩敢死队员总数为1时,总循环结束*/for(i=0;im;i+)if(L.elemi!=0)count+;if(count=5) /*报数循环*/L.elemi=0；/*表达队员出列*/count=0； /*计数器清零*/s-； /*敢死队员数-1*/for(i=0;iL.length) /*当顺序表当前分派存储空间大小局限性时进行再分派*/ L=ListInsert_Sq(L);for(i=0;i1) /*当所剩敢死队员总数为1时,总循环结束*/for(i=0;im;i+)if(L.elemi!=0)count+;if(count=5) /*报数循环*/L.elemi=0；/*表达队员出列*/count=0； /*计数器清零*/s-； /*敢死队员数-1*/for(i=0;im;i+) /*输出*/if(L.elemi!=0)if(m-L.elemi+2)%m=0) /*/printf(nThe wanted order is %dthn,m);elseprintf(nThe wanted order is %dthn,(m-L.elemi+2)%m); printf(Exit please input 0 Or Go on.nPlease input the tatal of the team:n);scanf(%d,&m)； /*输入敢死队员总数*/ 三. 单循环链表数据构造(一)、需求分析 1.本程序输入队伍人数n为任意，最后输出记数初始位置，一方面输入一种报数上限m，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中位置，通过数学思想求得题目规定即队长为首状况下 需要记数初始位置。2.程序执行命令涉及： （1）构造链表；（2）数据输入；（3）执行删除；（4）输出规定数值 （5）结束。3.数据测试：当 n=10，m=5，输出成果为：规定位置是：9(二)、概要设计以单循环链表为存储构造，包括三个模块： 1.主程序模块 2.构造链表并初始化3删除结点 (三)、详细设计1结点类型和指针类型typedef struct node int data; struct node *next;LNode;/* 定义结点类型 */LNode *p;2每个模块分析：主程序模块：main() LNode *p; int m,n,z,y; do printf( Please input the people number:n); scanf (%d,&n); while (n=0); do printf( Please input the excursion:n); scanf(%d,&m); while (mdata=1;/* 生成第一种结点并使其data值为1 */ for(i=2;inext=s; q-next-data=i;/*给第i个结点赋值i*/ q=q-next; q-next=t; /* 生成后续结点，并使其data值即为它所在链表（队伍）中位置 */ return t;3删除结点模块：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; /* while循环依次删除被点到士兵 */ printf(n); return (t-data);(四)调试分析： 阐明：（1）本程序运营环境是TC （2）进入演示程序后显示提示信息： Exit please input 0 Or Go on Please input the tatal of the team: 输入队伍总人数 Please input the excursion: 输入间隔人数 成果显示：The wanted position is th 选取位置（3）调试程序调试过程中遇到如下警告：发现错误为 if(m=1)后改正为 if(m=1)程序运营对的了，运营如下：显示输出如图：(3)由程序分析可得：本程序时间复杂度为O（nm）!(4)在设计生成循环单链表时，考虑到程序成果需要士兵位序，故将每个结点data值设立为她们在队列中位置，以便返回。 在删除单链表时，如果在报数时直接数到出列士兵则不以便链表删除，可设立im-1找到出列士兵前一位执行如下：for (i=1;inext; a=t-next; t-next=a-next; free(a);/*释放结点*/ t=t-next; 在程序设计前，如果按原题所设，则需设队长为第一位，再分别测试从第几种开始才干符合条件。当前变化思想，通过数学思想：单循环链表自身是一种循环体，可先求出当从第一种出发话，求出每隔m个出去一种最后是谁未出列，然后再设立它为链头，求出当她为队首时从第几种开始方能使其不出列。(n-y+2)%n 即可实现这功能！(五)、设计总结通过这次课程设计我又学到了诸多东西,如程序模块化设计思想，同步也加深了对数据构造这门课程理解和学会了如何在实际中应用数据构造.这个办法是用单循环链表来做，实现办法是这样：一方面从第一号开始报数，循环到指定偏移位置删除结点，直至剩余一种结点。然后设计输出，令这个位置为队长位置，队首为开始报数位置，并按此输出即为所求。这种办法大大减少了时间复杂度，复杂度为O(mn)。(六)、附件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;/*给第i个结点赋值i*/ q=q-next; q-next=t; /* 生成后续结点，并使其data值即为它所在链表（队伍）中位置 */ 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; /* while循环依次删除被点到士兵 */ printf(n); return (t-data);main() LNode *p; int m,n,z,y; printf(Exit please input 0 Or Go on.nPlease input the tatal of the team:); scanf (%d,&n)； /*输入队员总数*/ while(n!=0) /*当队员总数等于0时退出*/ do printf(Please input the excursion:)； /*输入偏移数*/ scanf(%d,&m); while (m=0); if(m=1) printf(The wanted position is 1th.n); else p=CREAT(n); y=DELETE(p,m); z=n-y+2; if(z%n=0) /* 排除特殊状况 */ printf (The wanted position is %dth:n,z); else printf(The wanted position is %dth:n,(n-y+2)%n); /* 通过数学思想求得实验规定状况下数值 */ printf(Exit please input 0 Or Go on.nPlease input the tatal of the team:); scanf(%d,&n)； /*输入敢死队员总数*/