《数据结构A》第01章.ppt

《《数据结构A》第01章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DataStructuresinC++掌握现代信息技术知识具有概念化和抽象化能力能力知识算法与数据结构什么是数据结构数据抽象和抽象数据类型描述数据结构和算法算法分析的基本方法1.1算法与数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法第1章基础知识数据结构和算法是计算机学科的基础之一，更是软件技术的基础。数据的组织和表示方法直接影响使用计算机求解问题的效率。程序=数据结构+算法1.1算法与数据结构1.2.1基本概念基本术语数据（data）：计算

2、机加工处理的对象。数据元素：组成数据的基本单位数值数据(numericaldata)非数值数据(non-numericaldata)1.2什么是数据结构什么是数据结构一个数据结构是由数据元素依据某种逻辑联系组织起来的，对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；一个数据结构必须讨论在该类数据上执行的运算才有意义。数据结构包括三个方面逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作。

3、1.2.2数据的逻辑结构数据的逻辑结构对数据元素间逻辑关系的描述被称为数据的逻辑结构(logicalstructure)，它可以用一个二元组表示：DS=（D，R），其中，D是数据元素的有限集合，R是D中元素序偶的集合。四类基本逻辑结构（a）集合结构（b）线性结构（c）树形结构（d）图状结构（a）集合结构（b）线性结构（c）树型结构（d）图形结构四类基本结构的示意图例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c)

4、,(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。（2）S=(D,R)D={di

5、1≤i≤5}R={(di,dj),i

6、见的运算创建运算:创建一个数据结构；清除运算:删除数据结构中的全部元素；插入运算:在数据结构的指定位置上插入一个新元素；删除运算:将数据结构中的某个元素删除；……静态数据结构和动态数据结构如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。1.3.1抽象、数据抽象和过程抽象抽象：其实质是抽取共同的和本质的内容，忽略非本质的细节。数据抽象：使程序设计者可以将数据元素间的逻辑关系和数据在计算机内的具体表示分别考虑。过程抽象：使程序设计者将一个运算的定义与实现运算的具体方法分开考

7、虑。抽象的好处主要在于降低了问题求解的难度。1.3数据抽象和抽象数据类型1.3.2封装与信息隐蔽封装:是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。信息隐蔽：对使用者隐藏了数据结构或程序的实现细节。通常将数据和操纵数据的运算组成模块。每个模块有一个明确定义的界面，模块内部信息只能经过这一界面被外部访问。1.3.3数据类型和抽象数据类型数据类型是程序设计语言中的概念，它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。程序设计语言中，一个

8、数据类型不仅规定了该类型的变量（或常量）的取值范围，还定义了该类型允许的运算。整型int的规范变量a的取值范围是：-32768~32767对变量a执行的操作有：算术运算+、-、*、/、%关系运算<、>、<=、>=、==、!=赋值运算=整型int的实现变量a在计算机内存储表示方法。操作的具体实现方法。抽象数据类型（abstractdatatypeADT）是一个数据类型，其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离。1.3.4数据结构与抽象

9、数据类型逻辑结构和运算的定义组成了数据结构的规范（specification）数据的存储表示和运算算法的描述构成数据结构的实现(implementation)。从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。一种数据结构被视为一个抽象数据类型。数据结构的抽象层次抽象层：讨论数据的逻辑结构及其运算定义，实现层：讨论数据的存储表示以及运算的算法实现。1.4.1数据结构的规范数据结构被看成是一个类属抽象数据