数据结构-严蔚敏4

《数据结构-严蔚敏4》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上课前需要说明的几个问题：1.任课教师：焦贤沛联系电话：838166562.交流信箱：jxp1972@163.com3.关于数据结构课程：教材、重要性、时间安排（64+32）、考试第一章绪论1.1数据结构讨论的范畴1.2基本概念1.3算法和算法的量度1.1数据结构讨论的范畴NiklausWirth：Algorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型结构静力分析计算例如:数值计算的程序设计问题─━线性代数方程组─━环流模式方程(球面坐标

2、系)全球天气预报【例1-1】图书目录表由于表中每条记录（表示每一本书）的登录号各不相同，所以可用登录号来唯一地标识每条记录（一本图书）。在计算机的数据管理中，能唯一地标识一条记录的数据项被称为关键字。因为每本图书的登录排列位置有先后次序，所以在表中会按登录号形成一种次序关系，即整个二维表就是图书数据的一个线性序列。这种关系被称为线性结构。非数值计算的程序设计问题返回返回描述磁盘目录和文件结构时，假设每个磁盘包括一个根目录（root）和若干个一级子目录，每个一级子目录中又包含若干个二级子目录….这种关系很像自然界中的树，所以称为目录树

3、。如左图所示。【例1-2】磁盘目录结构和文件管理系统在这种结构中，目录和目录以及目录和文件之间呈现出一对多的非线性关系。即根root有多个下属（也称为后代），每一后代又有属于自己的后代；而任一个子目录或文件都只有一个唯一的上级（也称为双亲）。称这种数学模型为树型数据结构。【例1-3】教学计划编排问题假如一个教学计划中包含许多课程。在课程之间，有些必须按规定的先后次序排课，如：学C6课程必须先学C3课，学C3课程必须先学C1课。这些课程之间存在先修和后续的关系。在这种结构中，表示课程的数据之间呈现多对多的非线性关系，称这类数学模型为图

4、形结构。图结构还有：多岔路口交通灯的控制和管理、煤气管道的铺设造价等。数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。概括地说：1.2基本概念一、数据与数据结构二、数据类型三、抽象数据类型一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个学生

5、的数据元素可以是称之为组合项数据结构：带结构的数据元素的集合假设用三个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}中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={,,

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

7、i=1,2,3,4,5}或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。数据结构：带结构的数据元素的集合可见，不同的“关系”构成不同的“结构”数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构数据结构的形式定义为:数据结构是一个二元组Data

8、_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。数据的存储结构——逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2关系的映象方法：（表示x,y的方法）顺序映象以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息xy链式映象以附加信息(指针)表示后继关系

9、需要用一个和x在一起的附加信息指示y的存储位置yx在不同的编程环境中，存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言