敢死队问题数据结构专业课程设计.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.elem[i]清零剩余队员数>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)； /*存储分派失败*/ else { L.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(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("\nThe wanted order is %dth\n",m); else printf("\nThe wanted order is %dth\n",(m-L.elem[i]+2)%m); printf("Exit please input '0' Or Go on...\nPlease input the tatal of the team:"); scanf("%d",&m)； /*输入敢死队员总数*/ } } 思考：本次设计问题核心是如何输出，由于这影响到了程序时间复杂度。总模块输出设计是这样实现：总是从第一种开始报数，报到5出列，直到剩余最后一种为止，然后就令这个位置为队长位置，队首为开始报数位置，并按此设计输出即可。这种办法大大减少了时间复杂度，其复杂度为O(mn)。（四）、程序调试及运营程序调试过程中浮现了下面警告: 经查询错误为:不可移动指针（地址常数）赋值最后发现是下面定义错误导致在变量定义中int *newbase =0；定义成了 int newbase =0; 经改正程序运营正常了. 数据测试如下：时间复杂度为O(mn) （五）、设计总结通过这次课程设计我又学到了诸多东西,如程序模块化设计思想，同步也加深了对数据构造这门课程理解和学会了如何在实际中应用数据构造编程。我一方面是用线性表来做，开始想法是想用实验办法来查找到所规定位置，即一方面从第一号开始报数，然后检查最后剩余一种与否是队首，然后从第二个开始报数……从第三个开始报数……直到所剩余最后一种是队首。虽然这种办法可以实现查找，可却是以消耗更多时间为代价，于是我又想到了这个办法：总是从第一种开始报数，报到5出列，直到剩余最后一种为止，然后就令这个位置为队长位置，队首为开始报数位置，并按此设计输出即可。这种办法大大减少了时间复杂度，复杂度为O(mn)。（六）、附件程序源代码: #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)； /*存储分派失败*/ else { L.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(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("\nThe wanted order is %dth\n",m); else printf("\nThe wanted order is %dth\n",(m-L.elem[i]+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 (m<=0); if (n=1) printf("the position is：1"); else { p=CREAT(n); y=DELETE(p,m); z=n-y+2; if(z%n==0) /* 排除特殊状况 */ printf ("the position is:\n%d\n",z); else printf("the position is:\n%d\n",(n-y+2)%n); }/* 通过数学思想求得实验规定状况下数值 */ } 2．构造单循环链表并初始化模块： 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;i<=n;i++) { s=(LNode *)malloc(sizeof(LNode));/*自动生成结点*/ q->next=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;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）进入演示程序后显示提示信息： 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值设立为她们在队列中位置，以便返回。 ②在删除单链表时，如果在报数时直接数到出列士兵则不以便链表删除，可设立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)。 (六)、附件 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;i<=n;i++) { s=(LNode *)malloc(sizeof(LNode));/*自动生成结点*/ q->next=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;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); } 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)； /*输入敢死队员总数*/ } }

展开阅读全文