数据结构 第一章 绪论

选用教材 《数据结构学习辅导》 《数据结构(C语言版)》 选用教材： 严蔚敏 吴伟民 编著.清华出版社出版 推荐参考书： 　选用教材： 　　严蔚敏 吴伟民 编著.清华出版社出版 　　《数据结构(C语言版)》 　推荐参考书： 　　宁正元编著 清华大学出版社出版 　　《数据结构学习辅导》 1-2

课程意义 数据结构是计算机专业的一门专业基础课。 数据结构是关于数据组织和处理的基本技术的一门学科。 程序 = 数据结构 + 算法 + 文档 数据结构是一门实践性很强的课程。 1-3

1.1 什么是数据结构？ 问题1：图书检索自动化 图书的基本信息：书名，作者，分类号，出版单位，出版时间 作者简介，内容简介等等。 操作：检索，排序，等等 数据之间的关系：线性关系 数据表示和算法操作的设计：与需求有关 1-4

1.1 什么是数据结构？ 线性表 书目文件 索引表 … L003 006 清华大学出版社 1979 刘永年 运筹学 K005 005 1958 栾汝书 线性代数 L002 004 1982 张之 化学 M003 003 高教出版社 1965 罗远祥 理论力学 S002 002 1964 樊映川 高等数学 L001 001 出版社 出版时间 作 者 书 名 书 号 … 004 线性代数 003 化学 002 理论力学 001 高等数学 索引表 按书名 栾汝书 张之 罗远祥 樊映川 按作者名 S M 005 K 001,004,006 L 按分类 1-5

1.1 什么是数据结构？ 树 问题2：井子棋 好的棋手不仅要看当 前的格局，还要预测 棋局发生的趋势，甚 至最后的胜负结局 如何表示一个棋局 　前的格局，还要预测 　棋局发生的趋势，甚 　至最后的胜负结局 如何表示一个棋局 数据的逻辑结构：表 　示棋局之间的演化关 　系：树型结构 算法如何设计 　基于数据表示的基础 　上算法设计 棋盘的当前格局 棋盘的对弈树局部 1-6

数据结构课程的主要任务 研究和解决非数值数据的组织和处理 算法+数据结构=程序 数据结构的作用范畴 描述非数值计算问题的数学模型，不再是数学方程 例如：前述的三个例子：数据的线性结构，树型结构，图 算法+数据结构=程序 算法和数据结构之间的关系 软件系统的框架应当建立在数据之上，而不是建立在操作之上 数据结构的作用范畴 抽象数据对象的数学模型（逻辑结构）例：图状结构 明确操作（运算的定义） 例：查找、插入、…… 在存储结构上映射数据（存储结构） 例：顺序存储 实现操作 1-7

组合项 1.2 基本概念和术语 学号 姓名 班号 性别 出生日期 入学成绩 年 月 日 基本术语 数据：被计算机加工处理的对象。 1.2 基本概念和术语 基本术语 数据：被计算机加工处理的对象。 数据元素：是数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。 数据项：是数据不可分割的最小单位。 一个数据元素可由若干个数据项组成。 组合项 年 月 日 学号　 姓名 班号 性别 出生日期 入学成绩 原子项 1-8

1.2 基本概念和术语 数据对象 是性质相同的数据元素的集合。 1.2 基本概念和术语 数据对象 是性质相同的数据元素的集合。 什么叫数据结构？ 具有结构的数据元素的集合。它包括数据元素的逻辑结构、存储结构和相适应的运算。 数据元素 学号 姓名 班号 性别 出生日期 入学成绩 001 刘影 01 女 19840417 623 002 李恒 男 19831211 679 003 陈诚 02 19840910 638 004 … 整个表是学生成绩数据对象 1-9

逻辑结构 数据元素之间的逻辑关系，与计算机无关。 可用一个二元组表示：Data_Structure = (D,R) D：数据元素的有穷集合，R：集合D上关系的有穷集合。 [例] 设有数据结构 B = (D,R) ， 其中 D= {d1, d2, d3, d4, d5, d6}， R={r}， r={<d1,d2>, <d1,d3>, <d1,d4>, <d3,d5>, <d3,d6>}， 试画出其逻辑结构图。 d1 d2 d3 d4 d5 d6 1-10

四种基本的逻辑结构 （以班级学生关系为例） (1)集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。 (1)集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。 (2)线性结构 数据元素之间存在一对一的关系。 (3)树型结构 数据元素之间存在一对多的关系。 (4)图状结构或网状结构 数据元素之间存在多对多的关系。 成员关系 长幼关系 管理关系 朋友关系 1-11

数据的逻辑结构 1-12

示例１ b c a e f d 用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 S=(D, R) 用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} 解：上述表达式可用图形表示为： b c a e f d 此结构为线性的。 1-13

示例２ 用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 S=(D, R) D={di | 1≤i≤5} R={(di , dj ), i<j} 解：上述表达式可用图形表示为： d1 d2 d3 d4 d5 该结构是非线性的。 1-14

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

顺序存储和链式存储 (1) 顺序存储：数据元素依次放在连续的存储单元中。 (2) 链式存储：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。 节点 1000 1004 a1 a2 … ai an 1272 1220 an 1224 1276 1004 1000 1072 1340 ai a1 节点 指针 1-16

数据运算 运算（操作）：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。 常用的运算有： (1)建立数据结构 (6)检索* (2)清除数据结构 (7)更新 (3)插入数据元素 (8)判空和判满* (4)删除数据元素 (9)求长* (5)排序 操作为引用型操作，即数据值不发生变化； 其它为加工型操作。 1-17

这三个方面的关系 数据的逻辑结构独立于计算机，是数据本身所固有的。 存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。 1-18

数据的运算：检索、排序、插入、删除、修改等 数据结构的三个方面 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队 树形结构 图形结构 1-19

1.3 数据类型和抽象数据类型 数据类型：是一个值的集合和定义在这个值集上一组操作总称。 分类：(按值的不同特性) 原子类型 ：每一个对象仅由单值构成的类型 ； 结构类型 ：每一个对象可由若干成分按某种结构 　　构成的类型。 1-20

抽象数据类型 抽象数据类型 ADT（Abstract Data Type） 作用：抽象数据类型可以使我们更容易描述实际问题。 例：用线性表描述学生成绩表，用树或图描述遗传关系。 定义：一个数学模型以及定义在该模型上的一组操作。 好处：可提高软件的复用程度。使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。 1-21

原子类型 固定聚合 类型 可变聚合 抽象数据类型分类 例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。 原子类型 值不可分解，如int 固定聚合 类型 值由确定数目的成分按某种结构组成，如复数 可变聚合 值的成分数目不确定，如学生基本情况 抽象数据类型分类 1-22

抽象数据类型表示法 表示方法： 三元组表示：（D，S，P） 其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。 标准定义格式： ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT 抽象数据类型名 1-23

例：线性表的表示 D={ai| ai(-ElemSet,i=1,2,...,n,n>=0} 名称 线性表 解释 数据对象 D={ai| ai(-ElemSet,i=1,2,...,n,n>=0} 任意数据元素的集合 数据关系 R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n} 除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继 基本操作 ListInsert(L,i,e) L为线性表，i为位置，e为数据元素。 ListDelete(L,i,e) ... 1-24

1.4 算法和算法分析 算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。 算法的五个特性 1.4 算法和算法分析 算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。 算法的五个特性 有穷性：对任何合法输入执行有穷步后能结束。 确定性：每条指令必须有确切的含义。 可行性：算法的每一条指令均能执行。 输入：有零个或多个输入。 输出：有一个或多个输出。 算法和程序的关系 　两者相似而又有区别。程序不一定满足有穷性（死循环）；程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。 1-25

评价算法优劣的基本标准 正确性(Correctness) 算法应满足具体问题的需求 对于典型的、苛刻而带有刁难性的一组有效输入得到正确的结果 可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。 健壮性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果。 高效性(Efficiency) 效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。 存储量需求指算法执行过程中所需要的最大存储空间。 时间复杂度和空间复杂度都与问题的规模有关。 1-26

算法效率的度量 事后统计的方法：求出该算法的一个时间界限函数； 事前分析估算的方法；要考虑以下的因素： 问题的规模； 编写程序时所用的程序设计语言； 机器的速度； 算法所用的策略。 渐近时间复杂度（时间复杂度）：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n))称作算法的渐近时间复杂度，简称时间复杂度。 频度：是指该语句重复执行的次数。频度与问题的基本操作执行次数相同，故时间复杂度可通过频度来计算。 估算时间复杂度的方法 ：从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则 。 1-27

时间复杂度 n 问题规模，一般为数据的输入量 f(n) 算法中基本操作重复执行的次数—频度 是问题规模n的某个函数 算法的时间量度、时间复杂度 算法中各语句的频度之和T(n) T(n)=O( f(n) ) 随问题规模的增大，算法执行时间的增长率和f(n)的增长率相同 O的含义 存在正的常数c和n0，使得当n  n0时， 0 T(n)  c* f(n) 1-28

时间复杂度计算 例1： x++; s = 0; 用频度法分析：将x++看成是基本操作，语句频度为１ T(n)=2 算法的时间复杂度：O(1)---常量阶 例2: for (i = 0; i<n; i++) { //执行n+1次 x++; //语句频度为：n　 s += x; //语句频度为：n　 } T(n)=2n+n+1=3n+1，则时间复杂度为：O(n) 也可以这样考虑：将x自增看成是基本操作，则语句频度为：n　其时间复杂度为：O(n)，即时间复杂度为线性阶。 1-29

时间复杂度计算 计算方法1：由于是一个三重循环，每个循环从1到n，则总次数为: n×n×n=n3 故时间复杂度为T(n)=O(n3)。 例3: 矩阵相乘C=AxB for (i =0; i < n; i++) //n+1 for (j = 0; j < n; j++) { //n*(n+1) c[i][j] = 0; // n2 for (k = 0; k <n; k++) //n2 *(n+1) c[i][j] += a[i][k] * b[k][j]; //n3 } T(n)= 2n3 +3n2+2n+1 算法的时间复杂度：O(n3) 计算方法1：由于是一个三重循环，每个循环从1到n，则总次数为: n×n×n=n3 故时间复杂度为T(n)=O(n3)。 计算方法2：由于“乘法”运算是本例的基本操作，故整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，故时间复杂度为T(n)=O(n3)。 1-30

时间复杂度计算 例4:分析以下程序段的时间复杂度 i=1; //语句频度为：１ while (i<=n) i=i*2　 //语句频度为：f(n) 因为：２f(n)≤n，即：f(n)≤log2n，取最大值f(n)=log2n ，则该程序的时间复杂度为： T(n)=1+f(n)=1+ log2n=O(log2n) 1-31

时间复杂度计算 补充)定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m)　（证略）。 例５for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) {++x;a[i，j]=x;} 语句频度为：1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =(n2-3n+2)/2 ∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。 1-32

时间复杂度计算 算法中基本操作重复执行的次数随问题的输入数据集不同而不同 例6：在数组A[n]查找给定值K (1) i=n-1; (2) while ( i>=0 && A[i]!=K ) (3) i=i-1; (4) RETURN(i); 　最好情况的时间复杂度 T(n)=O(1) 　最坏情况的时间复杂度 T(n)=O(n) 　平均时间复杂度： 所有可能的输入实例以等概率出现的情况 T(n)=(1+2+...+n)/n 算法的时间复杂度：O(n) 1-33

渐近复杂度的数学定义 定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n) ︳≦c｜g(n) ︳，则称函数f(n)当n充分大时有上界，且g(n)是它的一个上界，记为 f(n)=O(g(n))　　 此时，可以说f(n)的阶不高于g(n)。 大O标记法的几个性质： （1）O(f(n))+O(g(n))=O(max(f(n),g(n))) (2) O(f(n))+O(g(n))=O(f(n)+g(n)) (3) O(f(n))O(g(n))=O(f(n)g(n)) (4) O(cf(n))=O(f(n)) (5) f(n)=O(f(n)) 1-34

时间复杂度按数量递增排列及增长率 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。 以下六种计算算法时间的多项式是最常用的。其关系为： O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3) 指数时间的关系为： O(nk)<O(2n)<O(n!)<O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。 1-35

空间复杂度(Time Complexity) 类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。记作： S(n)=O(f(n)) 其中n为问题规模的大小。主要包括三个部分： （1）输入数据所占用的空间。 （2）程序本身所占用的空间。 （3）辅助变量所占用的空间。 存储密度d=数据本身存储量/实际所占存储量 1-36

习题 本章习题参见教师网页： http://staff.ustc.edu.cn/~leeyi 1-37