数据结构实现猴子吃桃

《数据结构实现猴子吃桃》由会员分享，可在线阅读，更多相关《数据结构实现猴子吃桃（9页珍藏版）》请在装配图网上搜索。

1、课程设计报告（猴子吃桃）学 院：东方科技学院班级：08级信息工程1班学号：200841919116姓 名：朱旭指导教师：贺细平老师一、题目概要二、基本概念和要点三、举例分析四、设计分析五、运行结果六、总结体会目录101011课程论文题目学 生：朱旭（ 东方科技学院 08 级信息工程一班，学号 200841919116）一、题目概要实现课题猴子吃桃摘 要：猴子吃桃这一典型的数学课题 ,其主要实现的过程是将其数学课题公式化，用一 些简单的数据定义、初使化、通过一系列的条件判断和循环用来实现学数公式的计算机化。通过C语言基础分析和数据结构初步了解，我们使用C语言，利用C和数据结构的结合使 用,让我们

2、在短时间内建立起对数据结构的进一步认识。然后,形成正确的对算法和优有个的 理解观念。关键词：C语言的基本了解，数据结构的基本了解，数据中数组的使用，用C语言实现 数据链表题目 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了 第 10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求 1链数据结构实现上述求解2数组数据结构实现上述求解3递归实现上述求解二、基本概念和要点数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻 辑结构和四种常用的存储表示方法。数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基

3、本单位，有时一个数据元素可以由若干个数据项组成。数据项是具 有独立含义的最小标识单位。如整数这个集合中，10 这个数就可称是一个数据元素.又比如 在一个数据库（关系式数据库）中，一个记录可称为一个数据元素，而这个元素中的某一字段 就是一个数据项。数据结构的定义虽然没有标准，但是它包括以下三方面内容： 逻辑结构、存储结构、 和对数据的操作 。这一段比较重要，用自己的语言来说就比如一个 表 （ 数据库 ），我们 就称它为一个数据结构，它由很多 记录 （ 数据元素 ）组成，每个元素又包括很多字 （ 数 据项 ）组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从 结点 （其实 也就是元素

4、、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东）之间的 关系来分析的，对于这个表中的任一个记录（结点），它只有一个 直接前趋 ，只有一个 直 接后继 （前趋后继就是前相邻后相邻的意思），整个表只有一个 开始结点 和一个 终端结 点 ，那我们知道了这些关系就能明白这个表的逻辑结构了。数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶 点、记录。数据元素有时可以由若干 数据项 组成。 数据类型 ：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构 ：指的是数据之间的相互关系，即数据的组织形式。一般包

5、括三个方面的 内容:数据的 逻辑结构 、 存储结构 和 数据的运算 。 逻辑结构 ：指各数据元素之间的逻辑关系。 存储结构 ：就是数据的逻辑结构用计算机语言的实现。 线性结构 ：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只 有一个 开始结点 和一个 终端结点 ，并且所有结点都最多只有一个 直接前趋 和一个 直 接后继 。线性表就是一个典型的线性结构。存储结构则是指用计算机语言来表示结点之间的这种关系。如上面的表，在计算机语言 中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一 起，这两种表示法就成为两种不同的存储结构。数据的运算 ，比如一张表格，我

6、们需要进行查找，增加，修改，删除记录等工作，而怎么 样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在 数据结构中，这些运算常常涉及算法问题。通常我们就将数据的逻辑结构称之为数据结构 ，数据的逻辑结构分两大类： 线性结 构 和 非线性结构 （这两个很容易理解）数据的存储方法有四种： 顺序存储方法 、 链接存储方法 、 索引存储方法和散列存 储方法 。 顺序存储方法 ：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的 逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为 顺序存储结构 。 链接存储方法 ：它不要求逻辑上相邻的结点在物理位置上亦相

7、邻，结点间的逻辑关系是 由附加的指针字段表示的。由此得到的存储表示称为 链式存储结构 。 索引存储方法 ：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法 ：就是根据结点的关键字直接计算出该结点的存储地址。递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直 接或间接调用自身而产生的重入现象.程序调用自身的编程技巧称为递归一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大 型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的 程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码

8、量。递归的能力 在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递 归前进；当边界条件满足时，递归返回。递归算法一般用于解决三类问题：（1）数据的定义是按递归定义的。(2) 问题解法按递归算法实现。(3) 数据的结构形式是按递归定义的。三、举例分析 题目：“猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个，第二天 早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一 个。到第 10 天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少？”我们要通过 对

9、这一例子的简要分析，不对这四种存储方法之中的链表进行一下分析。先将数学问题分析得到公式：求出桃子总数Y程序分析：采取逆向思维的方法，从后往前推断。C 程序源代码：main()int day,x1,x2;day=9;x2=1;while(day0)xl=(x2+l)*2;/*第一天的桃子数是第2天桃子数加1后的2倍*/x2=x1;day-;printf(the total is %dn,x1);根据分析图 1，它的运算方式和数据结构中的链表相本相似，其实数学结构中链式存储结构 的特点是用一组任意的存储单元存储线性表的数据元素，这组单元可以是连续的，也可以是 不连续的。因此，为了表示每个数据元素a

10、与其直接后继数据元素a之间的关系，对数据i i+1a 来说除了存储本身的信息之外，还需存储一个指示其直接后继的住处即直接后继的存储位 i置。这两部分住处组成数据元素a的存储映象，称为结点(node)。它包括两个域：其中存i 储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的 信息称做指针或链。n个结点(a (1WiWn)的存储映像)链结成一个链表，即为线性表（a ，a ，a ）的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故 1 2 n又称线性链表或单链表：（工，Y2, Y3，Y4, Y5，Y6, y7, Y8, Y9, Y10）的线性存储结构,123

11、45678910必须从头指针开始进行，头指针指示链表中第一个结点，即第一个数据元素的存储映像的存 储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中指针指示的。指针为数据元 素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不一定相邻。通 常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针如图 2 的线性链表可表示成图 3 的形式，这是国为在使用链表时，关心的只是它所表示的线性表中 数据元素之间的逻辑顺序， 而不是每个数据元素在存储器中的实际位置。* Y2Y6Y3Y 一Y

12、415JY7Y8Y10由些可见，单链表可由头指会惟一确定，在 C 语言 可用“结构指针”来描述：Typedef struct LNode ElemType data; Struct Lnode *next; Lnode, *LinkList;这就是线性表的单链表存储结构四、设计分析猴子吃桃：采用链式结构实现编程如下;#include#include#define NULL 0typedef struct linknodeint data;struct linknode *next;/ 链表指针node;node *head; /头结点void crea t() /创建链表 node *p,*s

13、;int peaches=l;/第十天时只剩下一个桃子int day=10;head=(node*)malloc(sizeof(node);p=head;while(day0)s=(node*)malloc(sizeof(node);/分配存属空间s-da ta=peaches;/用来存放结点数据p-next=s; /把结点插入链表中p=s;peaches=(peaches+l)*2;/第一天的桃子数是第二天桃子数加1后的2倍; day-;p-next=NULL;p=head;head二head-nex t;/使头指针指向头结点free(p); /释放指针 Pvoid prin t()/输出从

14、这十天每天的桃子数 node *p;p=head;int day=10;while(p&day0) printf(第d 天的桃子数:d 个n,day,p-data);p=p-next;day-;void main()/主函数creat();print();猴子吃桃：采用数组结构实现编程如下;#include using namespace std;static unsigned short arr10=0,0,0,0,0,0,0,0,0,1;void main()for (int i=9; i0; i-)arri-1=2*(arri+1);cout第i+l天还剩桃子：arriendl;cout

15、第 1 天还剩桃子：arr0endl;3) 采用递归实现编程如下;#include using namespace std;int eat(int n) if (10=n) return 1;elsereturn 2*(eat(n+1)+1);void main()for (int i=1; i=10; i+)coutvv第vvivv天还剩桃子：vveat (i)vv endl;五、运行结果采用链式结构运行结果：宀宀宀宀个个个m I .r W w 0 2 6 3 1/- 02649865 O : 412491371t产数数数数数数数数数ey 子子子子子子子子子子ky FTlr.r.mT.mT.

16、一 na -V1- - - 1 - - 1 - - 1 - - 1 - - 1 - - 1 - - 1 - - 1 - 子.亡 FFFFFFFuys 0 IT. IT. IT. IT. IT. IT. IT. IT. s 1987654321 e I I -hLEJlLEJlLEJlLEJlLEJlLEJlLEJ：! rr-hjr-,h 1Ir.-r-lIr.-r-lIr.-r-lIr.-r-lIr.-r-lIr.-r-lIr.-r-lIr.-r-l采用数组数据结构运行结果：采用递归运行结果：弦天还剩 方天还剩 沁天还剩 丐天还剩 甬天还剩 挣天还剩 闪天还剩， 冷天还剩桃子: 皿0天还剩桃子六、总结体会 通对对猴子吃桃这一典型例题的分析、理解到最后的解决都有助于我们对数据结构这门 课程的正解认识和体会，能更好的培养我的学习分析能力，在分析中得到最有效率的算法 也更加说明了这门课程的重要性和应用于的广泛。当然，在课程设计的过程也碰到了一些问 题。而关键性问题经常出现在一些函数的使用上，由于对一些函数调用的正确使用不够熟悉 往往也会造成程序无法运行，出现错误。只有在实践中才会发现错误才能达到学习的最终目 的。这些就是我在这个设计中所得到的体会。参考文献1 严蔚敏吴伟民数据结构（C语言版）清华大学出版社.2007年9月2 王森.C语言编程基础.电子工业出版社.2001年12月