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

Presentation on theme: "1 武汉大学国际软件学院 数据结构讲稿 薛超英 薛超英"— Presentation transcript:

1 1 武汉大学国际软件学院 数据结构讲稿 薛超英 薛超英 www.whuxcy.spaces.live.com whuxcy@hotmail.com

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18 18 例 顺序存储 200 201 202 203 204 205 a b c d e 逻辑结构 （ a ， b ， c ， d ， e ） 存储结构

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

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

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

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

23 23 例 链接存储 逻辑结构 （ a ， b ， c ， d ） 存储结构 200 d 201 0 202 203 204 b 205 208 206 207 208 c 209 200 210 a 211 204

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

25 25 例 插入操作 将逻辑结构 （ a ， b ， c ， d ） 改成（ a ， b ， x ， c ， d ） 存储结构 200 d 201 0 202 203 204 b 205 208 206 207 208 c 209 200 210 a 211 204 操作前

26 26 例 插入操作 将逻辑结构 （ a ， b ， c ， d ） 改成（ a ， b ， x ， c ， d ） 存储结构 200 d 201 0 202 x 203 208 204 b 205 202 206 207 208 c 209 200 210 a 211 204 操作后

27 27 例 删除操作 将逻辑结构 （ a ， b ， c ， d ） 改成（ a ， b ， d ） 存储结构 200 d 201 0 202 203 204 b 205 208 206 207 208 c 209 200 210 a 211 204 操作前

28 28 例 删除操作 将逻辑结构 （ a ， b ， c ， d ） 改成（ a ， b ， d ） 存储结构 200 d 201 0 202 203 204 b 205 200 206 207 208 c 209 200 210 a 211 204 操作后

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

30 30 例 索引存储 索引表 结点表 逻辑结构（ a ， b ， c ， d ， e ） bacedbaced 200 201 202 203 204 205 206 100 202 101 200 102 203 103 206 104 205 105 106 存储结构

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

32 32 例 插入操作 索引表 结点表 将逻辑结构（ a ， b ， c ， d ）改成 （ a ， b ， x ， c ， d ） bacdbacd 200 201 202 203 204 205 206 100 202 101 200 102 203 103 206 104 105 106 存储结构 操作前

33 33 例 插入操作 索引表 结点表 将逻辑结构（ a ， b ， c ， d ）改成 （ a ， b ， x ， c ， d ） bacxdbacxd 200 201 202 203 204 205 206 100 202 101 200 102 205 103 203 104 206 105 106 存储结构 操作后

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

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

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

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

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

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

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

41 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 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 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 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 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 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 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 48 u 作业一 作业一 u 提交实习报告的方法 提交实习报告的方法 u 如何从文件中读数据从文件中读数据 u 如何往文件中写数据往文件中写数据

49 49 第一章结束