《数据结构教程》第一章 绪论.ppt

《《数据结构教程》第一章 绪论.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构南京航空航天大学数据结构课题组第一章绪论1.1数据结构讨论的范畴1.2基本概念1.3算法和算法的度量1.1数据结构讨论的范畴NiklausWirth：Algorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型非数值计算的程序设计问题例一:求一组(n个)整数中的最大值算法:?模型：？基本操作是“比较两个数的大小”取决于整数值的范围例二：计算机对弈算法：?模型：?对弈的规则和策略棋盘及棋盘的格局例三：足协的数据库管理算法：?模型：?需要管理的项目？如何管理？用户界面？各种表

2、格概括地说：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。1.2基本概念一、数据与数据结构二、数据类型三、抽象数据类型一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个运动员的数据元素可以是称之为组合项数据结构：带结构的数据元素的集合假设用三个4位的十进制数表示一个含12位数

3、的十进制数。3214,6587,9345─a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3之间存在着“次序”关系a1,a2、a2,a33214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:又例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={,,,}col={,,}a1a3a5a2a4a6a1a2a3a4a5a6数据结构：带

4、结构的数据元素的集合再例，在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系:{

5、i=1,2,3,4,5}或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。数据结构：带结构的数据元素的集合可见，不同的“关系”构成不同的“结构”数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。数据的存储结构——逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？数据元素的映

6、象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息xy链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx在不同的编程环境中，存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如:以三个带有次序关系的整数表示一

7、个长整数时，可利用C语言中提供的整数数组类型。typedefintLong_int[3]定义长整数为:二、数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C语言中提供的基本数据类型有:整型int浮点型float字符型char逻辑型bool双精度型double数据类型是一个值的集合和定义在此集合上的一组操作的总称。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。三、抽象数据类型(AbstractDataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如，抽象数据类型复数

8、的定义：数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{

9、e1是复数的实数部分

10、e2是复数的虚数部分}ADTComplex{基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的