数据结构讲义完整版

1、第一章 绪论p学习数据结构的意义p基本概念和术语p算法的描述和分析1.1 什么是数据结构p图书的基本信息登记号，书名，作者，分类编号，出版单位，出版时间登记号，书名，作者，分类编号，出版单位，出版时间作者简介，内容简介，等等。作者简介，内容简介，等等。p操作检索，排序，等等检索，排序，等等p数据之间的关系线性关系线性关系p数据表示和算法操作的设计与需求有关与需求有关p数据的逻辑结构，存储结构，算法操作n逻辑结构是客观事物特性的一种抽象逻辑结构是客观事物特性的一种抽象n存储结构是逻辑结构的计算机实现存储结构是逻辑结构的计算机实现n算法操作是基于存储结构的操作，反映客观事物的变化算法操作是基于存储

2、结构的操作，反映客观事物的变化p如何表示一个棋局p数据之间的逻辑结构表示棋局之间的演化关系 树型结构p算法如何设计基于数据表示的基础上算法设计逻辑结构：图状结构p研究和解决非数值数据的组织和处理研究和解决非数值数据的组织和处理n描述非数值计算问题的数学模型，不再是数学方程n例如：前述的三个例子：数据的线性结构，树型结构，图p算法算法+数据结构数据结构=程序程序n算法和数据结构之间的关系n软件系统的框架应当建立在数据之上，而不是建立在操作之上p数据结构的作用范畴数据结构的作用范畴n抽象数据对象的数学模型（逻辑结构）例：图状结构n明确操作（运算的定义） 例：查找、插入、n在存储结构上映射数据（存储

3、结构） 例：顺序存储n实现操作 p1968年斯坦福的Knuth教授开创了数据结构的最初体系，在他所著的计算机程序设计技巧第一卷基本算法中第一次较系统地阐述了数据的逻辑结构和存储结构及其操作。 Donald Ervin Knuth The Art of Computer Programming Art Evansp数据结构在计算机科学中是一门综合性的专业基础课，也是计算机专业的必修课，是其它许多课程的先修课程，是设计编译程序、操作系统、数据库系统等系统程序和大型应用程序的重要基础。1.2 基本概念和术语p数据数据 被计算机加工处理的对象。p数据元素数据元素（记录记录、表目表目） 数据的基本单位，

4、是数据集合中的一个有意义的个体。p数据项数据项 一个数据元素可由若干个数据项数据项组成。 组合项组合项年 月 日学 号姓 名班 号性别出生日期入学成绩原子项原子项p数据对象数据对象 是性质相同的数据元素的集合，是数据的一个子集。 学号 姓名 班号 性别 出生日期 入学成绩 001 刘影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陈诚 02 男 19840910 638 p数据结构数据结构 具有结构的数据元素的集合。它包括数据元素的逻辑结构逻辑结构、存储结构存储结构和相适应的运算。数据元素 数据元素之间的逻辑关系，与计算机无关。 可用一个二元组

5、表示：Data_Structure = (D,R) D：数据元素的有穷集合，R：集合D上关系的有穷集合。 例例 设有数据结构 B = (D,R) ， 其中 D= d1, d2, d3, d4, d5, d6， R=r， r=, , , , ， 试画出其逻辑结构图。 d1d2 d3 d4d5 d6（以班级学生关系为例）(1)集合结构集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。(2)线性结构线性结构 数据元素之间存在一对一的关系。(3)树型结构树型结构 数据元素之间存在一对多的关系。(4)图状结构图状结构或网状结构网状结构 数据元素之间存在多对多的关系。成员关系长幼关系管理关

6、系朋友关系存储结构存储结构：数据的逻辑结构在计算机中如何表示。p数据元素的映象数据元素的映象 用二进制位(bit)的位串表示数据元素。 每个数据元素的映象称为每个数据元素的映象称为结点结点 每个数据项的映象称为每个数据项的映象称为数据域数据域p关系的映象关系的映象两种基本方法及其组合使用。两种基本方法及其组合使用。n顺序映象顺序映象：以相对的存储位置表示关系以相对的存储位置表示关系n链式映象链式映象：以附加信息：以附加信息( (指针指针) )表示关系表示关系在不同的编程环境下，存储结构有不同的描述方式。用高级程序语言编程时，直接用其提供的数据类型描述。(1)顺序存储顺序存储：数据元素依次放在连

7、续的存储单元中。 a1 a2 . ai . an (2)链式存储链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。 a1 1220 . a3 1342 . a21072 .1000 1004 1000 1004 1072 1076 1220 1224指针结点结点运算运算（操作操作）：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。几种常用的运算有： (1)建立数据结构 (6)检索* (2)清除数据结构 (7)更新 (3)插入数据元素 (8)判空和判满* (4)删除数据元素 (9)求长* (5)排序 *操作为引用型操作引用型操作，即数据值不发生变

8、化； 其它为加工型操作加工型操作。抽象数据类型抽象数据类型 ADT（ Abstract Data Type Abstract Data Type ）： 数据类型概念的引伸。指一个数学模型数学模型以及在其上定义的操作集操作集合合，与计算机无关。 数据类型数据类型：一组值的集合和定义在其上的一组操作的总称。ADT的特点的特点：将它的使用和实现分离，提高软件复用程度。 原子类型 固定聚合类型：值由确定数目的成分构成 结构类型 可变聚合类型：值的成分数目不确定 数据的逻辑结构+运算的定义-面向用户，需求分析 （抽象数据类型） 概念层 数据的存储结构+运算的实现-面向计算机 实现层 其中基本操作的定义格

9、式为:ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义 数据关系：数据关系：数据关系的定义 基本操作：基本操作：基本操作的定义 ADT 抽象数据类型名基本操作名基本操作名（参数表） 初始条件：初始条件：初始条件描述 操作结果操作结果：操作结果描述p参数参数n赋值参数 只为操作提供输入值。只为操作提供输入值。n引用参数 除可提供输入值外，还将返回该参数值在操作后的变化结除可提供输入值外，还将返回该参数值在操作后的变化结果果p初始条件初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。p操作结果操作结果 说明了操作正常完成之后，

10、数据结构的变化状况和应返回的结果。1.3 抽象数据类型的表示与实现1.4 算法和算法分析算法的概念算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。一个算法必须满足以下一个算法必须满足以下五五个重要特性个重要特性p有穷性：对任何合法输入执行有穷步后能结束。p确定性：每条指令必须有确切的含义。p可行性：算法的每一条指令均能执行。p输入：有零个或多个输入。p输出：有一个或多个输出。p正确性(Correctness)n算法应满足具体问题的需求算法应满足具体问题的需求n对于典型的、苛刻而带有刁难性的一组有效输入得到正确的对于典型的、苛刻而带有刁难性的一组有效输入得到正确的结果结果p可读性

11、(Readability)n算法应该好读。以有利于阅读者对程序的理解。算法应该好读。以有利于阅读者对程序的理解。p健壮性(Robustness) n算法应具有容错处理。当输入非法数据时，算法应对其作出算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果。反应，而不是产生莫名其妙或随机的输出结果。p高效性(Efficiency)算法效率的度量算法效率的度量n时间复杂度时间复杂度n空间复杂度空间复杂度算法效率的度量时间复杂度空间复杂度p事后统计的方法n先运行依据算法的程序先运行依据算法的程序n所得时间的统计量依赖于计算机的硬件、软件等环境所得时间的统计量依赖

12、于计算机的硬件、软件等环境因素因素n收集此算法的执行时间和实际占用空间的统计资料收集此算法的执行时间和实际占用空间的统计资料p事前分析估算的方法n求出该算法的一个时间界限函数；求出该算法的一个时间界限函数；pnn问题规模，一般为数据的输入量问题规模，一般为数据的输入量pf(n)n算法中基本操作重复执行的次数算法中基本操作重复执行的次数频度频度n是问题规模是问题规模n n的某个函数的某个函数p算法的算法的时间量度、时间复杂度时间复杂度n算法中各语句的频度之和算法中各语句的频度之和T(n)nT(n)=O( f(n) )n随问题规模的增大，算法执行时间的增长率和随问题规模的增大，算法执行时间的增长率

13、和f(n)的增长率相同的增长率相同pO的含义n 存在正的常数存在正的常数c和和n0，使得，使得当当n n0时，时， 0 T(n) c* f(n) 例1： x+; s = 0;将x+看成是基本操作，语句频度为T(n)=2算法的时间复杂度：O(1)-常量阶例2: for (i = 0; in; i+) /执行n+1次 x+; /语句频度为：n s += x; /语句频度为：n T(n)=2n+n+1=3n+1算法的时间复杂度为：O(n)-线性阶例3: 矩阵相乘C=AxB for (i =0; i n; i+)/n+1 for (j = 0; j n; j+) /n*(n+1) cij = 0;/n2 for (k = 0; k n; k+) /n2 *(n+1) cij += aik * bkj; /n3 T(n)= 2n3 +3n2+2n+1算法的时间复杂度：O(n3)p在难以精确计算基本操作执行次数的情况下，只求出关于n的增长率即可。例4: for (i = 2; i = n; +i) for (j = 2; j =0 & Ai!=K ) (3) i=i-1;(4) RETURN(i);最好情况的时间复杂度 T(n)=O(1) 最坏情况的时间复杂度 T(n)=O(n) 平均时间复杂度：所有可能的输入实例以等概率出现的情况 T(