1 武汉大学国际软件学院 数据结构讲稿 薛超英 薛超英

2 课程简介 对计算机专业的本科生来说，高级语言程序设计、数 据结构、算法设计与分析是三门重要的必修课。 这三门课程都是教学生如何编写计算机程序的。 高级语言程序设计是程序设计的初级课程，主要是向 学生传授高级程序设计语言的基础知识，对学生进行程序 设计的初步训练。 数据结构是程序设计的中级课程，主要是培养学生分 析数据、组织数据的能力，教学生如何编写效率高、结构 好的程序。 算法设计与分析是程序设计的高级课程，主要是教学 生学习各种典型的问题求解策略，学习对程序的时空性能 作定量分析的方法。

3 教学用书 u 教材 薛超英著. 数据结构 ( 第二版 ). 华中科技大学出版社 u 习题集 薛超英著. 数据结构学习指导与题解. 华中科技大学出版社  参考书 严蔚敏等著. 数据结构. 清华大学出版社 许卓群等著. 数据结构. 高等教育出版社 王海涛等译. 数据结构. 清华大学出版社 胡广斌等译. 数据结构与算法. 电子工业出版社

4 教学内容  第一章 概论  第二章 线性表  第三章 栈和队列  第四章 树形结构  第五章 图状结构  第六章 矩阵和广义表  第七章 查找  第八章 排序

5 第一章 概论 计算机的应用领域非常广泛，既可以用于科学 计算，也可以用于情报检索、企业管理，等等，而 它的功能概括起来却只有一个，那就是处理数据。 计算机所处理的数据不是杂乱无章的，而是有 着某种内在联系的。只有分清楚数据的内在联系， 合理地组织数据，才能对它们进行有效处理。如何 合理地组织数据、高效率地处理数据，正是本课程 的教学目的之所在。 作为全书的导引，本章扼要介绍有关数据结构 的几个重要概念和将要学习的主要内容。

6 本章学习内容 u 基本术语 u 数据的逻辑结构 u 数据的存储结构 u 数据的运算 u 算法分析 u 算法分析举例

7 基本术语 u 数据 一切能够输入到计算机中并被计算机程序处理的信息. u 数据元素 ( 结点 ) 数据的基本单位. u 数据项 ( 字段 ) 数据的最小单位. u 逻辑结构 结点和结点之间逻辑上的相互关系. u 存储结构 数据在计算机中的存储表示.

8 例 藏书登记表 藏书登记表 假设某人购买了许多图书，他打算用计算机来存储、管 理购书信息。他设计的个人书库管理程序具有以下功能： 统计某个时段买了哪些书？化了多少钱？ 检查是否买过指定书号（或书名，或作者名）的书？ 购书信息包括书号、书名、作者、购书时间、价格。他 设计的个人书库管理程序所要处理的数据就是这样的一些信 息。 为了能够有效处理数据，可以将数据组织成一张藏书登 记表（线性表 ）。 数据 一张表格，描述所有藏书信息。 结点 表格的某一行，描述一本书的信息。 字段 表格某一行中的某一列，描述一本书的某项信息。

9 数据的逻辑结构 u 逻辑结构的二元组描述 u 逻辑结构的分类 u 逻辑结构的图示法描述

10 逻辑结构的二元组描述 在大多数情况下，数据的逻辑结构可以 用二元组 S=(D,R) 来表示。其中， D 是结点的有限集合； R 是结 点有序对的集合，表示 D 上的一种关系。

11 例如，二元组 list=(D,R1),tree=(D,R2) 和 graph=(D,R3) 分别描述了具有 5 个结点的三种 不同的逻辑结构，其中， D={a,b,c,d,e} R1={,,, } R2={,,, } R3={,,, }

12 几个相关术语 对于某个逻辑结构 S=(D,R) ， 若 a ∈ D,b ∈ D, ∈ R ，则称 a 是 b 的前驱， b 是 a 的 后继； 若某结点没有前驱，则称该结点为开始结点； 若某结点没有后继，则称该结点为终端结点。

13 逻辑结构的分类 u 线性结构 有唯一的开始结点和终端结点 ; 其余结点有且仅 有一个前驱，有且仅有一个后继。 u 树形结构 每个结点最多只有一个前驱，但可以有多个后 继，可以有多个终端结点。 u 图状结构 每个结点的前驱和后继的数目都可以是任意的。

14 逻辑结构的图示法描述 除二元组外，数据的逻辑结构还有其他 表示方法。例如，对于非线性结构，通常采 用图示法： 用小圆圈表示结点，在圈内或圈外附近 标注结点名称或数值，用带箭头的弧线表示 结点之间的关系。

15 例 D={a,b,c,d,e} R2={,,, } R3={,,, }

16 数据的存储结构 存储数据时，通常要求既存储各结点的数值， 又存储结点与结点之间的逻辑关系。 数据的存储方法灵活多样，应根据问题规模和 运算种类等因素适当选择。 将要学习的四种基本的存储结构是：  顺序存储  链接存储  索引存储  散列存储

17 顺序存储 占用一组连续的存储单元；结点与结点 之间的逻辑关系由存储单元地址间的关系隐 含表示。

18 例 顺序存储 a b c d e 逻辑结构 （ a ， b ， c ， d ， e ） 存储结构

19 顺序存储的优缺点 顺序存储的主要优点是节省存储空间。 另外，线性结构若用这种方法存储，可实现对 各结点的随机访问。 顺序存储的主要缺点是在进行插入、删除运算 时，可能要移动一系列的结点。

20 例 插入操作 a b c d e 将逻辑结构（ a ， b ， c ， d ， e ）改成（ a ， b ， x ， c ， d ， e ） 存储结构 操作前

21 例 插入操作 a b x c d e 将逻辑结构（ a ， b ， c ， d ， e ）改成（ a ， b ， x ， c ， d ， e ） 存储结构 操作后

22 链接存储 给每个结点附加指针字段，用于存放相邻结点 的存储地址。 逻辑上相邻的结点在存储器中不一定放在相邻 的单元中。但是，分配给单个结点的存储单元是连 续的。

23 例 链接存储 逻辑结构 （ a ， b ， c ， d ） 存储结构 200 d b c a

24 链接存储的优缺点 链接存储的主要优点是，在进行插入删除运算 时，仅需修改结点的指针字段值，不必移动结点。 链接存储的主要缺点是，存储空间的利用率较 低。另外，线性结构若用这种方法存储，就不能对 结点进行随机访问。

25 例 插入操作 将逻辑结构 （ a ， b ， c ， d ） 改成（ a ， b ， x ， c ， d ） 存储结构 200 d b c a 操作前

26 例 插入操作 将逻辑结构 （ a ， b ， c ， d ） 改成（ a ， b ， x ， c ， d ） 存储结构 200 d x b c a 操作后

27 例 删除操作 将逻辑结构 （ a ， b ， c ， d ） 改成（ a ， b ， d ） 存储结构 200 d b c a 操作前

28 例 删除操作 将逻辑结构 （ a ， b ， c ， d ） 改成（ a ， b ， d ） 存储结构 200 d b c a 操作后

29 索引存储 建立索引表和结点表；将各结点的数值按任意 顺序存放在结点表中，而将每个结点的存储地址 ( 即 在结点表中的位置 ) 用顺序存储方法存入索引表中。

30 例 索引存储 索引表 结点表 逻辑结构（ a ， b ， c ， d ， e ） bacedbaced 存储结构

31 索引存储的优缺点 线性结构采用索引存储后，可以对结点进行随 机访问。 在进行插入删除运算时，由于只需移动存储在 索引表中的结点的存储地址，而不必移动存储在结 点表中的结点的数值，所以仍可保持较高的运算效 率。

32 例 插入操作 索引表 结点表 将逻辑结构（ a ， b ， c ， d ）改成 （ a ， b ， x ， c ， d ） bacdbacd 存储结构 操作前

33 例 插入操作 索引表 结点表 将逻辑结构（ a ， b ， c ， d ）改成 （ a ， b ， x ， c ， d ） bacxdbacxd 存储结构 操作后

34 散列存储 以结点中某个字段的值为自变量，通过某个函 数（称为散列函数）计算出对应的函数值，将这个 函数值当作结点的存储地址。

35 例 散列存储 逻辑结构 （ ‘ Wuhan ’ 、 ‘ Nanjing ’ 、 ‘ Shanghai ’ 、 ‘ Xian ’ 、 ‘ Beijing ’ ） 散列函数取值： 字符串中第一个字符的 ASCII 码 被 8 除所得余数。 0 ‘Xian’ 1 2 ‘Beijing’ 3 ‘Shanghai’ ‘Nanjing’ 7 ‘Wuhan’ 存储结构

36 散列存储的优缺点 散列存储的优点是查找速度快，只要给出待查 找结点的数值，就有可能立即找到存储单元。 与前三种存储方法不同的是，散列存储方法只 存储结点的数值，不存储结点与结点之间的逻辑关 系。 采用散列存储的关键是要选择一个好的散列函 数和处理 “ 冲突 ” 的办法。

37 数据的运算 数据的运算是指对数据的操作。数据的各种运 算都是在逻辑结构上定义的，但运算的具体实现要 在一定的存储结构上进行。 数据的运算用算法来表示。 算法和程序的主要区别在于：程序一定要用程 序设计语言书写，而算法则不必。

38 算法分析 对于数据的任何一种运算，如果数据的存储结 构不同，则其算法描述一般是不相同的，即使在存 储结构相同的情况下，由于可以采用不同的求解策 略，往往也可以有许多不同的算法。 算法分析的目的是要选择一个 “ 好 ” 的算法。

39 算法分析的任务 u “ 好 ” 算法的 4 个特征 正确 算法必须满足问题的要求，对合法的输入能产生问题要求 的输出结果；对非法的输入能作出适当的反应或处理。 可读 算法是给人看的，其可读性有助于人们对算法的理解。一 个晦涩难懂的算法易于隐藏错误，而且难以调试和修改。 运行时间较短 占用较少的存储空间  算法分析的主要任务是分析算法执行时间与问题规模之间 的关系。

40 算法的时间复杂度 算法的执行时间等于算法中各语句执行时间的总和，而某 个语句的执行时间等于该语句执行一次所需时间与执行次数的 乘积。 算法的执行时间通常表示成数量级的形式： T(n)=O(f(n)) 其含义为：当问题规模 n 足够大时，算法的执行时间 T(n) 和函 数 f(n) 成正比。 如果算法的执行时间 T(n) 与问题规模 n 无关，是个常数，则 记作 T(n)=O(1) 。 用数量级形式表示的算法的执行时间，通常称为算法的时 间复杂度。

41 三个重要定理 u 定理 1 若 T(n)=a m n m +a m – 1 n m – 1 +…+a 1 n+a 0 是一个 m 次多项式, 则 T(n)=O(n m ) u 定理 2 若 T 1 (n) 、 T 2 (n) 分别是算法 P1 、 P2 的执行时间，并且 T 1 (n) = O (f(n)) T 2 (n) = O (g(n)) 则依次执行算法 P1 和 P2 ，总的执行时间 T(n) = O (max (|f (n)| ， |g(n)|)) u 定理 3 若 T 1 (n) 、 T 2 (n) 分别是算法 P1 、 P2 的执行时间，并且 T 1 (n) = O(f (n)) T 2 (n) = k(n) T 1 (n) 则 T 2 (n) = O (k (n)f(n))

42 常见的时间复杂度 用数量级形式 O(f(n)) 表示算法执行时间 T(n) 的时 候，函数 f(n) 通常取较简单的形式，例如 1 、 log 2 n 、 n 、 nlog 2 n 、 n 2 、 n 3 、 2 n 在 n 较大的情况下，常见的时间复杂度之间存在下 列关系： O(1) < O (log 2 n) < O (n) < O (nlog 2 n) < O (n 2 ) < O (n 3 ) < O (2 n )

43 算法分析举例 (1) 假设 A[1] ～ A[n] 中存放了 n 个整数，下面程序段 的功能是确定其中值最大的整数在数组中的下标 i 。 请分析程序段中每个语句的执行次数，并用数 量级形式表示这个程序段的执行时间。 i=1; for(j=2;j<=n;j++) if(A[j]>A[i]) i=j; 1 次 n 次 n–1 次 最多 n–1 次 语句总的执行次数是 2n~3n–1 次，程序段执行时 间是 O(n) 。

44 算法分析举例 (2) 假设 A[1] ～ A[n] 中存放了 n 个整数，其中 n>100 。 下面程序段的功能是求其中前 100 个整数的平均值。 请分析程序段中每个语句的执行次数，并用数量 级形式表示这个程序段的执行时间。 s=0.0; for(i=1;i<=100;i++) s=s+A[i]; cout<<s/100; 1 次 101 次 100 次 1 次 语句的执行次数和 n 无关，程序段的执行时间是 O(1) 。

45 算法分析举例 (3) 下面程序段的功能是从 n 阶整型矩阵中找出两个 值最小的整数。请分析其时间复杂度。 m1=32767; m2=m1; for(i=0;i<n;i++) for(j=0;j<n;j++) if(A[i][j]<m1){ m2=m1;m1=A[i][j]; } else if(A[i][j]<m2) m2=A[i][j]; 执行第 1 行赋值 语句所需时间是 O(1), 执行一遍内循环 体所需时间也是 O(1), 由于内循环体总 共执行了 n 2 次, 因此, 程序段的执行时间为 O(n 2 ) 。

46 算法分析举例 (4) 下面的程序段可用于求 x n 。 请分析其时间复杂度。 y=1;u=x;v=n; while(v>0) { if (v%2==1) y=y*u; u=u*u;v=v/2; } cout<<y; 执行时间主要用 在 while 循环上。 由于 v 的初始值 是 n ，每循环一遍， v 值被减半，因此，循 环次数不超过 log 2 n 次。 执行一遍循环体 所需时间是 O(1) 。 程序段的执行时 间为 T(n)= (log 2 n)O(1) = O (log 2 n)

47 算法分析举例 (5) 下面的算法是用来求解著名 的 汉诺塔 问题的。 请分析算法的时间复杂度。 void hanoi(int n, char a,char b,char c) { if (n>0){ hanoi(n–1,a,c,b); cout "<<c; hanoi(n–1,b,a,c); } 当 n=0 时，所需时 间为 T(n)=O(1) ； 当 n>0 时，执行了一 个输出语句和两个递归 调用语句，所需时间为 O(1)+2T(n–1) 。 算法的执行时间是 T(n)=2T(n–1)+ O(1) = = O(2 n ) a b c

48 u 作业一 作业一 u 提交实习报告的方法 提交实习报告的方法 u 如何从文件中读数据从文件中读数据 u 如何往文件中写数据往文件中写数据

49 第一章结束