数据结构实现猴子吃桃

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

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

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

3、 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10 这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容： 逻辑结构、存储结构、和对数据的操作 。这一段比较重要，用自己的语言来说就比如一个 表 ( 数据库 )，我们就称它为一个数据结构，它由很多 记录 ( 数据元素 )组成，每个元素又包括很多字 ( 数据项 )组成。那么这张表的逻辑

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

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

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

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

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

9、。求第一天共摘了多少？”我们要通过对这一例子的简要分析，不对这四种存储方法之中的链表进行一下分析。先将数学问题分析得到公式：求出桃子总数 YY3/2-1得到第五天总数 Y5得到第六天总数 Y6得到第七天总数 Y7 得到第八天总数 Y8 得到第九天总数 Y9得到第十天总数 Y10=1Y4/2-1Y5/2-1Y6/2-1 Y7/2-1 Y8/2-1Y9/2-1图 1程序分析：采取逆向思维的方法，从后往前推断。C程序源代码：main()int day,x1,x2;day=9;x2=1;while(day0)x1=(x2+1)*2;/*第一天的桃子数是第 2天桃子数加 1后的 2倍*/x2=x1;da

10、y-;printf(the total is %dn,x1);根据分析图 1，它的运算方式和数据结构中的链表相本相似，其实数学结构中链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组单元可以是连续的，也可以是不连续的。因此，为了表示每个数据元素 ai与其直接后继数据元素 ai+1之间的关系，对数据 ai来说除了存储本身的信息之外，还需存储一个指示其直接后继的住处即直接后继的存储位置。这两部分住处组成数据元素 ai 的存储映象，称为结点（node） 。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指第一天的桃子总数 Y1 得到第二天总数 Y

11、2Y1/2-1得到第三天总数 Y3Y2/2-1得到第四天总数 Y46针域中存储的信息称做指针或链。n 个结点（a i（1in）的存储映像）链结成一个链表，即为线性表（a 1，a 2，a n）的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表：（Y 1，Y 2，Y 3，Y 4，Y 5，Y 6，Y 7，Y 8，Y 9，Y 10）的线性存储结构，必须从头指针开始进行，头指针指示链表中第一个结点，即第一个数据元素的存储映像的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”NULL。如图 2存储地址 数据域 指针域1 Y4 437 Y

12、2 1313 Y3 119 Y8 5225 Y6 3731 Y1 737 Y7 1943 Y5 2552 Y9 6161 Y10 NULL头指针 H31图 2用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中指针指示的。指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不一定相邻。通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针如图2的线性链表可表示成图 3的形式，这是国为在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。H Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9

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

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

15、node *p;p=head;int day=10;while(p&day0) printf(第%d 天的桃子数:%d 个n,day,p-data);p=p-next;day-;8void 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 using namespace std;int eat(int n)if (10=n) return 1;else return 2*(eat(n+1)+1);void main() for (int i=1; i=10;