数据结构-严蔚敏

上课前需要说明的几个问题：1.任课教师：焦贤沛联系电话：838166562.交流信箱：[e-mail]3.关于数据结构课程：教材、重要性、时间安排（64+32）、考试第一章绪论1.1数据结构讨论的范畴1.2基本概念1.3算法和算法的量度1.1数据结构讨论的范畴NiklausWirth：Algorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型结构静力分析计算例如:数值计算的程序设计问题─━线性代数方程组─━环流模式方程(球面坐标系)全球天气预报【例1-1】图书目录表由于表中每条记录（表示每一本书）的登录号各不相同，所以可用登录号来唯一地标识每条记录（一本图书）。在计算机的数据管理中，能唯一地标识一条记录的数据项被称为关键字。因为每本图书的登录排列位置有先后次序，所以在表中会按登录号形成一种次序关系，即整个二维表就是图书数据的一个线性序列。这种关系被称为线性结构。非数值计算的程序设计问题返回返回登录号书号书名作者出版社定价1ISBN7-302-02368-9/TP．1185数据结构严蔚敏清华大学222ISBN7-302-00860-4/TP．312C程序设计谭浩强清华大学17.33ISBN7-5053-9279-4/TP．311数据结构徐孝凯电子工业294ISBN7-5053-8168-7/TP．4757计算机系统原理张基温电子工业255ISBN7-5609-2351-8/TP．316操作系统原理庞丽萍华中科技大学22.86ISBN7-304-01404-0/TP．68数据库基础与应用王利中央电大23.37ISBN7-5084-1648-1/TP．706网页制作实例教程齐建玲中国水利水电20………………表1-1图书目录表描述磁盘目录和文件结构时，假设每个磁盘包括一个根目录（root）和若干个一级子目录，每个一级子目录中又包含若干个二级子目录….这种关系很像自然界中的树，所以称为目录树。如左图所示。【例1-2】磁盘目录结构和文件管理系统binrootlibuseretcmathdszhaojiangshaoliqueuetreegraphstacksw在这种结构中，目录和目录以及目录和文件之间呈现出一对多的非线性关系。即根root有多个下属（也称为后代），每一后代又有属于自己的后代；而任一个子目录或文件都只有一个唯一的上级（也称为双亲）。称这种数学模型为树型数据结构。【例1-3】教学计划编排问题假如一个教学计划中包含许多课程。在课程之间，有些必须按规定的先后次序排课，如：学C6课程必须先学C3课，学C3课程必须先学C1课。这些课程之间存在先修和后续的关系。在这种结构中，表示课程的数据之间呈现多对多的非线性关系，称这类数学模型为图形结构。课程编号课程名称先修课程C1计算机导论无C2数据结构C3汇编语言C4C程序设计C5计算机图形学C6接口技术C7数据库原理C8编译原理C9操作系统C1，C4C2C1C1C2，C3，C4C3C2，C9C4C1C3C6C5C2C4C9C8C7C1图结构还有：多岔路口交通灯的控制和管理、煤气管道的铺设造价等。数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。概括地说：1.2基本概念一、数据与数据结构二、数据类型三、抽象数据类型一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个学生的数据元素可以是年月日学号姓名出生日期籍贯专业是否团员称之为组合项数据结构：带结构的数据元素的集合假设用三个4位的十进制数表示一个含12位数的十进制数。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}中六个元素之间存在两个关系:a1a2a3a4a5a6行的次序关系:列的次序关系:row={a1,a2,a2,a3,a4,a5,a5,a6}col={a1,a4,a2,a5,a3,a6}a1a3a5a2a4a6a1a2a3a4a5a6数据结构：带结构的数据元素的集合再例，在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系:{ai,ai+1|i=1,2,3,4,5}或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。数据结构：带结构的数据元素的集合可见，不同的“关系”构成不同的“结构”数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。数据的存储结构——逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息xy链式映象以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx在不同的编程环境中，存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型。typedefintLong_int[3]；定义长整数为:二、数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。例如，C语言中提供的基本数据类型有:整型int浮点型float字符型char逻辑型bool（C++语言）双精度型double实型（C++语言）数据类型是一个值的集合和定义在此集合上的一组操作的总称。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。三、抽象数据类型(AbstractDataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如，抽象数据类型复数的定义：数据对象：D＝{e1,e2｜e1,e2∈RealSet}数据关系：R1＝{e1,e2|e1是复数的实数部分|e2是复数的虚数部分}ADTComplex{基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex假设:z1和z2是上述定义的复数则Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的结果ADT有两个重要特征:数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉赋值参数只为操作提供输入值。引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。抽象数据类型的表示和实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。例如，对以上定义的复数。typedefstruct{floatrealpart；floatimagpart；}complex；//-----存储结构的定义//-----基本操作的函数原型说明voidAssign(complex&Z,floatrealval,floatimagval)；//构造复数Z,其实部和虚部分别被赋以参数//realval和imagval的值floatGetReal(cpmplexZ)；//返回复数Z的实部值floatGetimag(cpmplexZ)；//返回复数Z的虚部值voidadd(complexz1,complexz2,complex&sum)；//以sum返回两个复数z1,z2的和//-----基本操作的实现voidadd(complexz1,complexz2,complex&sum){//以sum返回两个复数z1,z2的和sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}{其它省略}1.3算法和算法的衡量一、算法二、算法设计的原则三、算法效率的衡量方法和准则四、算法的存储空间需求算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出一、算法1．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。2．确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。3．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。5．有输出它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。二、算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性2.可读性3．健壮性4．高效率与低存储量需求1．正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。d．程序对于一切合法的输入数据都能得出满足要求的结果；2.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。3．健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4