九江学院《数据结构》第01章 绪论

退出主目录下一页2020/2/7第一章绪论1.1基本概念和术语1.2什么是数据结构1.3数据类型1.4算法和算法分析主目录下一页上一页退出本章要点2020/2/7数据和信息数据：是客观事物的符号表示，是对现实世界的事物采用计算机能够识别、存储和处理的形式进行描述的符号的集合信息：是其中的含义，不同的形式可以传达同样的信息数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的原料，应用程序处理各种各样的数据。是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。1.1基本概念和术语主目录下一页上一页退出本章要点2020/2/7数据元素(DataElement)数据元素是数据的基本单位，即数据集合中的个体。数据元素亦称节点或记录在计算机程序中通常作为一个整体进行考虑和处理。有时一个数据元素可由若干数据项(DataItem)组成。数据项是数据的最小单位。数据项：分为组合项和原子项1.1基本概念和术语学号姓名性别籍贯出生年月1,2，”a”，”b”，…主目录下一页上一页退出本章要点2020/2/7“学生”表格学号姓名性别籍贯出生年月98131刘激扬男北京1979.121.1基本概念和术语主目录下一页上一页退出本章要点2020/2/7数据对象(DataObject)数据对象是性质相同的数据元素的集合，是数据的一个子集例如整数数据对象N={0,1,2,…}学生数据对象1.1基本概念和术语主目录下一页上一页退出本章要点2020/2/7“学生”表格学号姓名性别籍贯出生年月198131刘激扬男北京1979.12298164衣春生男青岛1979.07398165卢声凯男天津1981.02498182袁秋慧女广州1980.10598203林德康男上海1980.05698224洪伟男太原1981.01798236熊南燕女苏州1980.03898297宫力男北京1981.01998310蔡晓莉女昆明1981.021098318陈健男杭州1979.12主目录下一页上一页退出本章要点2020/2/7数据结构（DataStructure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。是相互之间存在一种或多种特定关系的数据元素的集合数据结构的逻辑结构和物理结构（又称为存储结构）两个方面（层次）逻辑结构：是对数据元素之间的逻辑关系的描述物理结构：是逻辑结构在计算机中的表示或实现1.2什么是数据结构主目录下一页上一页退出本章要点2020/2/7逻辑结构可描述为B=（D，R）有限个数据元素的集合有限个节点间关系的集合一般用二元组a,b表示D中各数据元素之间的前驱、后继关系1.2.1逻辑结构主目录下一页上一页退出本章要点2020/2/7B=（D，R）D={Sun，Mon，Tue，Wed，Thu，Fri，Sat}R={Sun,Mon，Mon,Tue，Tue,Wed，Wed,Thu，Thu,Fri，Fri,Sat}SunMonTueWedThuFriSat例1：一周七天的数据结构的表示1.2.1逻辑结构主目录下一页上一页退出本章要点2020/2/7SunMonTueWedThuFriSat线性结构：指的是数据元素之间存在着“一对一”的线性关系的数据结构例1：一周七天的数据结构的表示1.2.1逻辑结构主目录下一页上一页退出本章要点2020/2/7B=（D，R）D={学院，计算机系，电子系，机电系，土木系，应用专业，网络专业，信息管理专业}R={学院,计算机系，学院,电子系，学院,机电系，学院,土木系，计算机系,应用专业，计算机系,网络专业，计算机系,信息管理专业}例2：学校的人事管理1.2.1逻辑结构主目录下一页上一页退出本章要点2020/2/7学院电子系土木系计算机系机电系应用专业网络专业信息管理专业树型结构：指的是数据元素之间存在着“一对多”的树形关系的数据结构例2：学校的人事管理1.2.1逻辑结构主目录下一页上一页退出本章要点2020/2/7主目录下一页上一页退出本章要点2020/2/7123图状或网状结构：指的是数据元素之间存在着“多对多”的网络关系的数据结构例3：3个站点的关系图1.2.1逻辑结构主目录下一页上一页退出本章要点2020/2/7B=（D，R）D={丁一，王五，李四}R=丁一王五李四纯集合结构：指的是在数据元素之间除了“同属一个集合”之外，别无其他关系例4：3个没有任何关系的学生1.2.1逻辑结构主目录下一页上一页退出本章要点2020/2/7数据之间的相互关系称为逻辑结构。通常分为四类基本结构：集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构结构中的数据元素之间存在一对一的关系。树型结构结构中的数据元素之间存在一对多的关系。图状结构或网状结构结构中的数据元素之间存在多对多的关系。1.2.1逻辑结构主目录下一页上一页退出本章要点2020/2/71.2.2物理结构数据结构包括数据的逻辑结构和数据的物理结构。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关。我们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构。数据结构在计算机中的标识（又称映像）称为数据的物理结构，或称存储结构。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。主目录下一页上一页退出本章要点2020/2/7数据的存储结构可采用顺序存储或链式存储的方法。顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。1.2.2物理结构主目录下一页上一页退出本章要点2020/2/71.2.2物理结构元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容顺序存储顺序存储结构常用于线性逻辑结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里主目录下一页上一页退出本章要点2020/2/7数据的存储结构可采用顺序存储或链式存储的方法。链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。除了通常采用的顺序存储方法和链式存储方法外，有时为了查找的方便还采用索引存储方法和散列存储方法。1.2.2物理结构主目录下一页上一页退出本章要点2020/2/71536元素21400元素11346元素3∧元素4head1346元素31536…….……..…….1536元素21400…….……..…….∧元素413461400元素11345指针存储内容存储地址链式存储13451.2.2物理结构主目录下一页上一页退出本章要点2020/2/7链式存储一般情况下，每个节点都由两部分组成：数据域和指针域数据域存放元素本身的数据指针域存放指针数据元素之间逻辑上的联系由指针来体现1536元素21400元素11346元素3∧元素4head13451.2.2物理结构主目录下一页上一页退出本章要点2020/2/7数据类型定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称C语言中的基本数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值1.3数据类型主目录下一页上一页退出本章要点2020/2/7抽象数据类型（AbstructDataType，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。例如，各种计算机都拥有的整数类型就是一个抽象数据类型，尽管它们在不同处理器上的实现方法可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。1.3数据类型主目录下一页上一页退出本章要点2020/2/7但在另一方面，抽象数据类型的范畴更广,它不再局限于前述各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的重用性，在近代程序设计方法学中，要求在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块的内部给出这些数据的表示及其操作的细节，而在模块的外部使用的只是抽象的数据及抽象的操作。这也就是面向对象的程序设计方法。1.3数据类型主目录下一页上一页退出本章要点2020/2/7抽象数据类型的定义可以由一种数据结构和定义在其上的一组操作组成，而数据结构又包括数据元素及元素间的关系，因此抽象数据类型一般可以由元素、关系及操作三种要素来定义。抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。1.3数据类型主目录下一页上一页退出本章要点2020/2/7数据结构的三个方面1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队列树形结构图形结构(亦称物理结构)数据结构可描述为B=（D，R）按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构主目录下一页上一页退出本章要点2020/2/7算法：是对特定问题求解步骤的一种描述算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（4）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。（5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1.4算法和算法分析1.4.1算法主目录下一页上一页退出本章要点2020/2/71.4.2算法设计的要求评价一个好的算法有以下几个标准:(1)正确性(Correctness)：算法应满足具体问题的需求。(2)可读性(Readability)：算法应该好读。以有利于阅读者对程序的理解。(3)健壮性(Robustness)：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。主目录下一页上一页退出本章要点2020/2/7性能评价——对问题规模和该算法在运行时所占的空间S和所耗费的时间T给出一个数量关系的评价数量关系评价体现在时间数量关系评价体现在空间1.4.3算法效率的度量主目录下一页上一页退出本章要点2020/2/7算法一：For(i=1;i=100;i++)s=s+i;算法二：For(i=1;i=50;i++)s=s+101;算法三：s=101*50;求1~100这100个数的总和1.4.3算法效率的度量主目录下一页上一页退出本章要点2020/2/7时间评价算法执行时间：所有语句执行时间的总和。一般是对算法中语句的执行次数做出估计语句频度：该语句在一个算法中重复执行的次数。1.4.3算法效率的度量主目录下一页上一页退出本章要点2020/2/7算法的时间复杂度:一般情况下，算法中基本操作重复