数据结构课程设计-猴子吃桃问题.doc

数学与计算机学院 课程设计说明书 课 程 名 称: 数据结构-课程设计 课 程 代 码: 8404181 题 目: 猴子吃桃子问题 年级/专业/班: 2009 级软件工程四班 学 生 姓 名: 学 号: 开 始 时 间: 2011 年 6 月 13 日 完 成 时 间: 2011 年 6 月 26 日 课程设计成绩： 学习态度及平 时成绩（30） 技术水平与实际 能力（20） 创新（5）说明书撰写质量（45） 总 分 （100） 指导教师签名： 年 月 猴子吃桃子问题 摘摘 要要 数据结构是一门结合 C+知识的重要课程，因此我们要学会用平时课本的知 识运用到我们的现实生活当中，这样才能让我们所学的知识更加深刻。 分析了猴子吃桃子问题的实质，得到了其数学模型 ni-1= 2*（ni+1）(0 ，接下来就是其需求分析和概要设计，大致的制定出其实现方案以及其 )10 i 系统结构，然后就是利用掌握的语言 C/C+编程实现这一生活问题，该软件用了 几种不同的方法解答出了所需要的答案。猴子吃桃的问题就是一个例子，我们可 以运用简单的四种解法进行解题，即数组求值解法，链表求值解法，递归求值解 法和队列求值法，通过分析四种解法，根据各种解法的功能，从而我们得到最合 适的求法。 关键词：关键词：猴子吃桃子；数组法；链表发；递归法；队列法；分析 猴子吃桃子问题 目目 录录 1 需求分析需求分析.1 1.1 问题描述.1 1.2 基本要求.1 1.3 题目分析.1 1.4 需求分析规格说明书 .1 2 开发及运行平台开发及运行平台.2 3 概要设计概要设计.2 3.1 解法分析 .2 3.1.1 数组求解法分析.2 3.1.2 链表求解法分析.2 3.1.3 递归法分析.3 3.1.3 队列法分析.3 3.2 数据流图 .4 4 详细设计详细设计.5 4.1 数据类型定义 .5 4.2 主要模块设计 .5 4.2.1 模块 1数组求解模块.5 4.2.2 模块 2链表求解模块.6 4.2.3 模块 3递归求解模块.7 4.2.4 模块 4队列求解模块.8 5 调试分析调试分析.9 6 测试结果测试结果.10 7 结论结论.11 参考文献参考文献.12 附附 录录.13 数据结构课程设计 1 1 需求分析需求分析 1.11.1 问题描述问题描述 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个， 到了第 10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少 个桃子。 1.21.2 基本要求基本要求 (1)采用数组数据结构实现上述求解 (2)采用链式数据结构实现上述求解 (3)采用递归实现上述求解 (4)采用队列实现上述求解 1.31.3 题目分析题目分析 根据题目要求，设猴子共摘的桃子个数为 n 即是第一天桃子的个数 n1, 第 第二天时桃子个数 n2，第三天时桃子个数 n3，第四天时桃子个数 n4，第五天时 桃子个数 n5，第六天时桃子个数 n6，第七天时桃子个数 n7，第八天时桃子个数 n8，第九天时桃子个数 n9，第十天时桃子个数 n10。 由题中“每天都吃当前桃子的一半且再多吃一个”很容易知道 n10=1，n9- （n9/2+1）=n10，n8-（n8/2+1）= n9 依 次推出公式：ni-1-（ni-1/2+1）= ni (0。即 ni-1= 2*（ni+1）(0。)10 i)10 i 1.41.4 需求分析规格说明书需求分析规格说明书 由上述描述及分析可知，该系统所要做的工作就是计算出原来这群猴子共 摘了多少个桃子。通过分析不同的解法，找到每种解法的优劣，得到最合适的 求解方法。由问题描述可知，该系统运行时，不需要手动输入任何数据，因此 就没有输入的测试数据，只有输出的测试数据，且输出数据的形式是输出每天 剩下的桃子数，最后输出这群猴子总共摘了多少桃子。 数据结构课程设计 猴子吃桃问题 第 3 页 共 21 页 2 2 开发及运行平台开发及运行平台 本软件是在基于 windows 的操作系统上的 VC+6.0 的环境下开发的，并在 VC+6.0 下编译通过。 3 3 概要设计概要设计 3.13.1 解法分析解法分析 3.1.13.1.1 数组求解法分析数组求解法分析 分析： 声明一个长度为 10 的整形数组 a10,分别存放各天猴子吃前的桃子数。下 图 1 所示： 图 1 数组元素分布图 先将 a9赋值为 1，用一个循环语句 for(int i=8;i=0;i-) ai=2*(ai+1+1);为其余各数组元素赋值，则数组元素 a0的值便是该 问题的解。 数据类型定义： int a10; a9=1; 3.1.23.1.2 链表求解法分析链表求解法分析 分析： 建立单链表，声明一个类用来对链表的结点指针进行定义，在初始化函数 中利用头插法创建具有 10 个元素的链表，并依次安公式 ni-1= 2*（ni+1）(0 。赋值得到一个如图 2 所示的链表。)10 i n1n2n3n4n5n6n7n8n9n10 a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 数据结构课程设计 猴子吃桃问题 第 4 页 共 21 页 head 图 2 链表结点逻辑结构图 那么N1便是要求问题的解。 数据类型定义： class list public: int data; class list *next; void push(); ;typedef class list node; /建立单链表(将 class 重定义为 node) typedef node *link; /定义结点指针 3.1.33.1.3 递归法分析递归法分析 分析： 利用一个递归函数来进行求值：依据返回值来记录每一天剩余桃子情况。 int process(int n) if(n=10) return 1; else return 2*(process(n+1)+1); 3.1.33.1.3 队列法分析队列法分析 nextN10 nextN9 nextN8 next N7 nextN6 nextN5 nextN4 next N3 nextN2 nextN1 NULL 数据结构课程设计 猴子吃桃问题 第 5 页 共 21 页 分析： 定义一个队列，和一个临时变量，临时变量存放第十天到第一天的剩下的 桃子数目，每计算出一天的剩余的桃子数，就将其入队，十天的剩余桃子 数全部入队以后就出对，即得到每一天的剩余桃子数，最后得到的一个数 据就是所要求的桃子的总数。 数据类型定义： typedef struct SqQueue int dataQueueSize; int fornt,rear; / 队首、队尾指针 SqQueue; 3.23.2 数据流图数据流图 猴子吃桃子问题 求解系统 已知：第十天剩 1个桃，每天吃 当前桃子的一半 再加1个 解的结果，以及 每天剩下的桃子 个数 图 3 系统数据流图 3.33.3 结结构构图图 数据结构课程设计 猴子吃桃问题 第 6 页 共 21 页 猴子吃桃子求解系统 采 用 数 组 存 储 结 果 求 解 采 用 递 归 过 程 求 解 采 用 队 列 存 储 结 果 求 解 采 用 链 表 存 储 结 果 求 解 图 4 系统结构图 4 4 详细设计详细设计 4.14.1 数据类型定义数据类型定义 in a10; class list public: int data; class list *next; void push(); ;typedef class list node; /建立单链表(将 class 重定义为 node) typedef node *link; /定义结点指针 typedef struct SqQueue int dataQueueSize; int fornt,rear; / 队首、队尾指针 SqQueue; 数据结构课程设计 猴子吃桃问题 第 7 页 共 21 页 4.24.2 主要模块设计主要模块设计 4.2.14.2.1 模块模块 1 1数组求解模块数组求解模块 4.2.1.1 模块算法： /数组求解 void Array_Solve() int a10; / 存放 int i; a9=1; cout数组数据结构实现:endl; cout第 10 天剩下的桃子为:a9=0;i-) ai=(ai+1+1)*2; cout第 i+1天剩下的桃子为:aiendl; cout所以猴子共摘了a0个桃子endl; cout=0;i-) ai=(ai+1+1)*2; coutnext; cout链式数据结构实现:endl; cout第 10 天剩下的桃子为:1endl; int i=9; while(p) cout第 i天剩下的桃子为:dataendl; if(i=1) 数据结构课程设计 猴子吃桃问题 第 9 页 共 21 页 cout所以猴子共摘了data个桃子next; i-; coutendl; 4.2.34.2.3 模块模块 3 3递归求解模块递归求解模块 4.2.3.1 模块算法 int process(int n) /递归 if(n=10) return 1; else return 2*(process(n+1)+1); /递归求解 void Fac_Solve() cout递归方法实现:0;i-) cout第 i天剩下的桃子为:process(i)endl; cout所以猴子共摘了process(1)个桃子endlendl; 4.2.44.2.4 模块模块 4 4队列求解模块队列求解模块 4.2.4.1 模块算法 /队列求解 void Queue_Solve() SqQueue SQ; SQ.fornt=SQ.rear=0; int temp; / 临时变量，存放每一天剩的桃子数 数据结构课程设计 猴子吃桃问题 第 10 页 共 21 页 temp=1; / 初始放第十天的 for(int i=0;i10;i+) SQ.dataSQ.rear+=temp; temp=2*(temp+1); cout队列数据结构实现:endl; while(SQ.fornt!=SQ.rear) cout第11-SQ.fornt天剩下的桃子为: SQ.dataSQ.fornt+endl; cout所以猴子共摘了SQ.dataSQ.fornt-1个桃子 endl=0;i-)，因 此其时间复杂度为 O(9). 数组求解模块的空间复杂度：因为不需要输入任何数据，所以该算法 为原地工作。 5.2 链表求解模块的时间复杂度：因为算法中用到一个循环来输出，因此 其时间复杂度为 O(9). 链表求解模块的空间复杂度：原地工作。 5.3 队列求解模块的时间复杂度：因为 for(i=0;idata=j; for(int i=9;i0;i-) s=new node; s-data=(j+1)*2; j=s-data; s-next=NULL; p-next=s; p=p-next; 数据结构课程设计 猴子吃桃问题 第 15 页 共 21 页 typedef struct SqQueue int dataQueueSize; int fornt,rear; / 队首、队尾指针 SqQueue; /数组求解 void Array_Solve() int a10; / 存放 int i; a9=1; cout数组数据结构实现:endl; cout第 10 天剩下的桃子为:a9=0;i-) ai=(ai+1+1)*2; cout第 i+1天剩下的桃子为:aiendl; cout所以猴子共摘了a0个桃子endl; coutnext; cout链式数据结构实现:endl; cout第 10 天剩下的桃子为:1endl; int i=9; while(p) cout第 i天剩下的桃子为:dataendl; if(i=1) cout所以猴子共摘了data个桃子next; 数据结构课程设计 猴子吃桃问题 第 16 页 共 21 页 i-; coutendl; int process(int n) /递归 if(n=10) return 1; else return 2*(process(n+1)+1); /递归求解 void Fac_Solve() cout递归方法实现:0;i-) cout第 i天剩下的桃子为:process(i)endl; cout所以猴子共摘了process(1)个桃子endlendl; /队列求解 void Queue_Solve() SqQueue SQ; SQ.fornt=SQ.rear=0; int temp; / 临时变量，存放每一天剩的桃子数 temp=1; / 初始放第十天的 for(int i=0;i10;i+) SQ.dataSQ.rear+=temp; temp=2*(temp+1); cout队列数据结构实现:endl; while(SQ.fornt!=SQ.rear) cout第11-SQ.fornt天剩下的桃子为: SQ.dataSQ.fornt+endl; cout所以猴子共摘了SQ.dataSQ.fornt-1个桃子 endlendl; 数据结构课程设计 猴子吃桃问题 第 17 页 共 21 页 v