什么是数据结构 抽象数据类型及面向对象概念 模板 算法定义.ppt

《什么是数据结构 抽象数据类型及面向对象概念 模板 算法定义.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、什么是数据结构抽象数据类型及面向对象概念模板算法定义算法性能分析与度量Chapter1基本概念和算法分析1.1什么是数据结构数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。P.2——数值数据,非数值性数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。——整数数据对象N={0,1,2,…}——学生数据对象什么是数据结构？定义:由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure={D,R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合如

2、：n个网站之间的连通关系树形关系网状关系152643152643复数的数据结构定义如下：Complex=(C，R)C是包含两个实数的集合﹛C1，C2}R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。数据结构是数据的组织形式包括三个方面：数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数据的存储表示；数据的运算，即对数据元素施加的操作。相关：逻辑结构物理结构相关操作实现数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；数据的逻辑结构与数据元素本身的形式、内容无关；

3、数据的逻辑结构与数据元素的相对存储位置无关。数据的逻辑结构分类线性结构线性表非线性结构树图（或网络）线性结构bindevetclibuser树形结构树二叉树二叉搜索树14131211234567891031587101199874566231311堆结构“最大”堆“最小”堆123548711102916410121151236987图结构网络结构12543611331814665161921125634数据的存储结构数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构依赖于计算机语言。顺序存储表示链接存储表示索引存储表示散列存储表示主要用于内存的存储表示主要用于外存(

4、文件)的存储表示抽象数据类型：由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离抽象数据类型可用（D,S,P）三元组表示，其中，D是数据元素的集合（简称数据对象），S是D上的关系集合，P是对D的基本操作集合。1.2抽象数据类型及面向对象概念例：自然数的抽象数据类型定义(P.8)ADTNaturalNumberisobjects:一个整数的有序子集合,它开始于0,结束于机器能表示的最大整数(MaxInt)。Function:对于所有的x,yNaturalNumber;False,TrueBool

5、ean,+、-、<、==、=等都是可用的服务。Zero():NaturalNumber返回自然数0IsZero(x):Booleanif(x==0)返回Trueelse返回FalseAdd(x,y):NaturalNumber:if(x+y<=MaxInt)返回x+yelse返回MaxIntEqual(x,y):Booleanif(x==y)返回Trueelse返回FalseSuccessor(x):NaturalNumberif(x==MaxInt)返回xelse返回x+1Subtract(x,y):NaturalNumber`if(x

6、NaturalNumber定义适合多种数据类型的类定义或算法，在特定环境下通过简单地代换，变成针对具体某种数据类型的类定义或算法1.3模板用模板定义用于排序的数据表(dataList)类#ifndefDATALIST_H#defineDATALIST_H#includetemplateclassdataList{private:Type*Element;intArraySize;voidSwap(constintm1,constintm2);intMaxKey(constintlow,constinthigh);public:d

7、ataList(intsize=10):ArraySize(size),Element(newType[Size]){}~dataList(){delete[]Element;}voidSort();friendostream&operator<<(ostream&outStream,constdatalist&outList);friendistream&operator>>(istream&inStream,constdatalist&inList);};#endifdataList类中