数据结构 Java语言描述.ppt

《数据结构 Java语言描述.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据结构Java语言描述面向对象的方法&注释、条件和断言数据结构数据结构即是描述数据的组织形式及操作的一门课程。数据的组织形式相关研究对相应组织形式的数据上的操作研究。什么是程序？程序（Program）就是供计算机执行后，能完成特定功能的指令序列（Instructionssequence）程序=计算机指令序列程序包含两方面的内容数据对象（Objects）及数据对象之间关系数据结构(Datastructure)对这些对象的处理过程算法(Algorithm)程序／数据结构／算法程序＝数据结构＋算法（Program＝DataStructure＋Algorithm）这个公式由Nikla

2、usWirth首先提出。NiklausWirth是PASCAL之父和结构化程序设计的首创者，1984图灵奖获得者。数据数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。数据元素（DataElement）数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录等。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。数据结构数据的逻辑结构可描述为：Group=（D，R）有限个数据元素的集合这些数据元素间关系的集合数据的逻辑结构

3、可描述为：Group=（D，R）数据的逻辑结构——线性结构A,B,C,·······，X,Y,Z学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表——结点间是以线性关系联结数据的逻辑结构——树形结构全校学生档案管理的组织方式1423213数据的逻辑结构——图形结构节点间的连结是任意的数据的存储结构——顺序存储数据的存储结构——链式存储数据的运算通过算法(Algorithm)描述，讨论算法是数据结构课程的重要内容之一。算法是对特定问题求解步骤的一种描述。数据结构中常见的算法有：检索、排序、插入、删除、修改等。算法和算法分析（1）有

4、穷性——算法必须总是在执行有穷步之后结束。（2）确定性——算法中每一条指令必须有确切的含义。不存在二义性。（3）可行性——即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入——一个算法有零个或多个输入。（5）输出——一个算法有一个或多个输出。算法具有以下五个特性：求解同一计算问题可能有许多不同的算法，如何去评价这些算法的优劣？选用的算法首先应该是“正确”的。此外，主要考虑如下三点：执行算法所耗费的时间；执行算法所耗费的存储空间，其中主要考虑辅助存储空间；算法应易于理解，易于编码，易于调试等等。评价算法好坏的标准算法执行的时间等于所有语句执行时间的总和，

5、是算法所处理的数据个数n的函数，表示为：O(f(n))，O(f(n))称为该算法的时间复杂度。O(1)表示算法的时间是一个常数，不依赖于n；O(n)表示算法的时间与n成正比，是线性关系；O(n2)，O(n3)，O(2n)分别称为平方阶、立方阶和指数阶；O(log2n)为对数阶算法的时间性能分析定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n)︳≦c｜g(n)︳记作：f(n)=O(g(n))定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则：A(n)=O(nm)算法的时间性能分析例1、{x++;s=0;}其时间复杂度仍为Ｏ(1)，即

6、常量阶。例2、for(i=0;i

7、运算时间远远超过多项式时间算法。多项式时间复杂度和指数时间复杂度空间复杂度:算法所需存储空间的度量，记作:S(n)=O(g(n))其中n为问题的规模(或大小)算法的存储空间需求数据类型类型是一组值的集合。数据类型是指一个类型和定义在该类型上的操作集合。数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作。如：Java中整型类型int的值集是{-232,…,-2,-1,0,1,2,…,232-1},还包括对这个整数类型进行的加(+)、减(-)、乘(*)、除(/)和求模(%)操作。数据