数据结构实现猴子吃桃

数据结构课程设计报告（猴子吃桃）学 院： 东方科技学院 班 级： 08级信息工程1班 学 号： 200841919116 姓 名： 朱旭 指导教师： 贺细平老师 目 录一、题目概要 1二、基本概念和要点 1三、举例分析 3四、设计分析 10五、运行结果 10六、总结体会 11课程论文题目 学 生：朱旭 (东方科技学院08级信息工程一班，学号200841919116)一、题目概要实现课题猴子吃桃摘 要：猴子吃桃这一典型的数学课题,其主要实现的过程是将其数学课题公式化，用一些简单的数据定义、初使化、通过一系列的条件判断和循环用来实现学数公式的计算机化。通过C语言基础分析和数据结构初步了解,我们使用C语言,利用C和数据结构的结合使用,让我们在短时间内建立起对数据结构的进一步认识。然后,形成正确的对算法和优有个的理解观念。关键词：C语言的基本了解，数据结构的基本了解, 数据中数组的使用，用C语言实现数据链表题目 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求 1链数据结构实现上述求解2数组数据结构实现上述求解3递归实现上述求解二、基本概念和要点数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，用自己的语言来说就比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字(数据项)组成。那么这张表的逻辑结构是怎么样的呢?我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言的实现。 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 存储结构则是指用计算机语言来表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢?这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 通常我们就将数据的逻辑结构称之为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.程序调用自身的编程技巧称为递归 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。(2)问题解法按递归算法实现。(3)数据的结构形式是按递归定义的。三、举例分析题目：“猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少？”我们要通过对这一例子的简要分析，不对这四种存储方法之中的链表进行一下分析。Y2/2-1先将数学问题分析得到公式：求出桃子总数YY1/2-1 得到第三天总数Y3得到第二天总数Y2第一天的桃子总数Y1得到第四天总数Y4Y3/2-1得到第五天总数Y5得到第六天总数Y6得到第七天总数Y7得到第八天总数Y8得到第九天总数Y9得到第十天总数Y10=1Y4/2-1Y5/2-1Y6/2-1Y7/2-1Y8/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; day-; printf(the total is %dn,x1);根据分析图1，它的运算方式和数据结构中的链表相本相似，其实数学结构中链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组单元可以是连续的，也可以是不连续的。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的关系，对数据ai来说除了存储本身的信息之外，还需存储一个指示其直接后继的住处即直接后继的存储位置。这两部分住处组成数据元素ai 的存储映象，称为结点（node）。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点（ai（1in）的存储映像）链结成一个链表，即为线性表（a1，a2，an）的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表：（Y1，Y2，Y3，Y4，Y5，Y6，Y7，Y8，Y9，Y10）的线性存储结构，必须从头指针开始进行，头指针指示链表中第一个结点，即第一个数据元素的存储映像的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”NULL。如图2存储地址数据域指针域1Y4437Y21313Y3119Y85225Y63731Y1737Y71943Y52552Y96161Y10NULL头指针H31图2图3用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中指针指示的。指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不一定相邻。通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针如图2的线性链表可表示成图3的形式，这是国为在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。HY1Y2Y3Y4Y5Y6Y7Y8Y9Y10由些可见，单链表可由头指会惟一确定，在C语言 可用“结构指针”来描述： Typedef struct LNodeElemType data;Struct Lnode *next; Lnode, *LinkList;这就是线性表的单链表存储结构四、设计分析猴子吃桃：采用链式结构实现编程如下;#include#include#define NULL 0typedef struct linknode int data; struct linknode *next;/链表指针node;node *head; /头结点void creat()/创建链表 node *p,*s; int peaches=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()/输出从这十天每天的桃子数 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+1天还剩桃子：arriendl; cout第1天还剩桃子：arr0endl;3) 采用递归实现编程如下;#include 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; i+) cout第i天还剩桃子：eat(i)endl;五、运行结果采用链式结构运行结果：采用数组数据结构运行结果：采用递归运行结果：六、总结体会通对对猴子吃桃这一典型例题的分析、理解到最后的解决都有助于我们对数据结构这门课程的正解认识和体