数据结构 （第二版） 严蔚敏 吴伟民 主讲：李树全 计算机学院

Presentation on theme: "数据结构 （第二版） 严蔚敏 吴伟民 主讲：李树全 计算机学院"— Presentation transcript:

1 数据结构 （第二版） 严蔚敏 吴伟民 主讲：李树全 计算机学院
严蔚敏 吴伟民 清华大学出版社 主讲：李树全 电子科技大学 计算机学院 新的一学期又开始了，同学们又要在新的起点，抱着新的希望，去追求新的知识。《数据结构》是计算机专业知识的起步基石。因此，我将与您们一起前行，去掀开《数据结构》这本丰富多彩的书，象一只小虫漫游在数据结构这棵大树上，去领略各种数据结构的功用和风采，去品味各种算法的精妙和乐趣。希望我们能共同圆满地完成教与学的任务，希望在最后的回首中，能记得这次轻松愉快的知识之旅。

2 第一章 绪论 1.1 学习<数据结构>的意义及要求 1.2 <数据结构>的主要内容 1.3 基本术语
第一章 绪论 1.1 学习<数据结构>的意义及要求 1.2 <数据结构>的主要内容 1.3 基本术语 1.4 算法描述及分析

3 1.1 学习<数据结构>的意义及要求
一. 意义 1. 算法和数据结构是计算机科学的两大支柱 计算机科学早期定义为: 研究算法的科学 近期定义为: 研究数据的科学 一.数据结构的起源和重要性 1968年《数据结构》作为一门独立的课程在国外正式开出，同年出版的美国D.E.Knuth所著的《计算机程序设计技巧》第一卷《基本算法》是一本较系统地阐述数据的逻辑结构与存贮结构以及运算的理论方法与技巧的著作。在这以前，数据结构的有关内容，如表处理、串处理、树结构等已包含在《表处理语言》和《离散结构》等课程中。我国于七十年代末期在大学开设了《数据结构》课程。 《数据结构》在计算机科学中占有十分重要的地位，其重要性体现在以下几方面： ⒈ 数据结构和算法是计算机科学的两大支柱 计算机科学早期定义为：是研究算法的科学；近期定义为：是研究数据的科学。 ⒉ 数据结构是程序设计的重要基础。 N.Wirth在1976年写下了《Algorithms+Data Structure=programs》的著作，表明了数据结构是进行程序设计(包括系统程序和应用程序)的重要基础。 ⒊《数据结构》是计算机科学中的一门综合性专业基础课。 该课程是计算机专业的必修学位课；通常也是计算机专业研究生入学考试的科目；并且还是软件人员水平考试必考内容。数据结构是介于数学、计算机硬件和软件三者之间的一门核心课程。

4 1.1 学习<数据结构>的意义及要求
2. 数据结构是程序设计的基础 Program=Algorithms+Data Structure 数据结构是设计OS、DBMS、编译等系统程序 和各种应用程序 的重要基础

5 1.1 学习<数据结构>的意义及要求
3. <数据结构>是计算机专业的一门综合性 专业基础课，是一门理论与实际紧密结合 的基础课。 是计算机专业本科生必修学位课程 是计算机研究生入学考试必考科目 是软件人员水平考试内容

6 1.1 学习<数据结构>的意义及要求
4. <数据结构>与计算机科学技术其他相关 领域的关系 数据结构 问题求解 算法理论 数据模型 设计方法 描述语言

7 1.1 学习<数据结构>的意义及要求
二. 要求 1. 掌握各类基本数据结构类型 和相应的存储 结构 2. 提高阅读 和编写算法 的能力 3. 能针对给定问题，选择相适应的数据结构， 并能设计和分析算法

8 1.2 <数据结构>的主要内容 例1： 99080-33202670610054510102780618748
班号 计算机学院办公室电话号码 电子科技大学邮编 身份证号码 二.《 数据结构》研究的主要内容 ⒈ 杂乱无序的数据，没有信息。 例1：有一数字串为 ，它表示什么？含有哪些信息？若不知道数字之间的结构或联系，就很难得知信息。这串数字的结构是：前六位为一整体表示邮编，中间七位为一整体是电子科技大学的总机电话号码，最后五位为一整体表示八系92级。 ⒉数据之间是有联系的 例2：设电话号码薄为(a1，b1)(a2，b2)...(an，bn)其中ai为姓名，bi为电话号码，(i=1，2，...n)，如果名字和电话号码排列没有规律，在查找某人的电话号码时，只能逐一地进行比较；如果把名字按字典顺序组织，则查找会方便得多。可见数据之间的联系常常影响算法的选择和效率。《数据结构》就是要研究数据之间的各种联系和各类数据结构。 ⒊ 在某类数据结构上定义了一组运算 例3：图书目录管理问题。设每个书目含书名、作者、登录号、分类、出版日期等项，对图书目录应定义如下一组运算： · 查找：某书是否在书库中？ . 插入：购进新书时的登录。 · 删除：从目录中去掉报废或丢失的书。 《数据结构》还要研究种各类数据结构上的各种运算。 《数据结构》主要研究数据的逻辑结构和物理结构，以及两者的相互关系；并对每种结构定义相适应的运算，设计出相应的算法；分析算法的效率。常见的数据结构类型有：向量、数组、记录、栈、队列、表、串、树、图和文件等. 结论1. 杂乱的数据不能表达和交流信息

9 1.2 <数据结构>的主要内容 结论2. 数据之间是有联系的 这些联系常常影响算法的选择和效率。
例2: 电话号码簿 (a1，b1) (a2，b2)…(an，bn) 其中： ai为某人姓名，bi为该人的电话号码。 要求：设计一个算法，给定一个姓名时， 能查出此人的电话号码。 如果姓名和电话号码的排列次序无规律， 则只能逐一比较姓名进行查找 如果姓名按字典顺序组织，则查找就快捷多了 结论2. 数据之间是有联系的 　　这些联系常常影响算法的选择和效率。 　 《DS》就是要研究数据之间的联系。

10 1.2 <数据结构>的主要内容 例3：大学学生管理机构 学校 一年级 二年级 三年级 四年级 １班 ．．．８班
　　　　一系　　．．．八系　．．． 　　　　　　　一年级　二年级　三年级　四年级　 　　　　　　　１班　．．．８班 　　　　　　　　张三．．．李四 结论３． 数据之间是有结构的 例３中数据之间呈分层结构（树状结构） 《DS》就是要研究数据之间的各类结构。

11 1.2 <数据结构>的主要内容 例４：图书目录管理 结论４． 在某种数据结构上可定义一组运算
设每个书目含：书名，作者，登录号，分类，出版年月 对图书目录常有如下操作： 查找：某书在书库中是否存在？ 插入：购进新书时的登录； 删除：报废或丢失的书，需从目录中去掉； 结论４． 在某种数据结构上可定义一组运算 《DS》就是要研究各类数据结构上的各种运算。

12 1.2 <数据结构>的主要内容 综上所述： 《DS》主要研究内容： 设计出相应的算法； 分析算法的效率。
数据的各种逻辑结构和物理结构，以及它 们之间的相应关系； 对每种结构定义相适应的各种运算； 设计出相应的算法； 分析算法的效率。 常见的数据结构有：数组、栈、队列、表、串、树、图和文件等。

13 数据结构与问题求解 1. 在计算机中建立一个与实际问题有比较密 切对应关系的模型；
2. 计算机内部的数据 表示了需要被处理的 实际对象，包括其内在的性质和关系； 3. 处理这些数据的程序 则模拟对象领域中 的实际过程； 4. 将计算机程序的运行结果 在实际领域中 给予解释，便得到实际问题的解。

14 例1、当你到图书馆借阅书籍时，你要通过计算机检索书目信息。
在书目自动检索系统中，有一张按登录号顺序排列的书目文件和 三张分别按书名、作者名和分类号顺序排列的索引表。计算机检 索就是按某个特定要求（如给定书名）对书目文件查询。 （书目文件） （书名索引） （作者索引） （分类索引）

15 例2、酒店管理系统中的客房分配问题。 酒店要求每间客房出租率相等，以保证维持一个平均磨损率。 对这一问题可用数据结构中的队列来解决；将酒店所有空闲 客房排成一个队列，有客人入住则从队头分配客房，客人结帐 离店则将空出的客房插入队尾。这样就能保证客房出租率相等。 队头 队尾 出租队头客房 客人离店，空出客房插入队尾 注：例1、例2都属于线性数据结构

16 例3、计算机和人对弈问题。计算机和人对弈是因为事先已将对
奕的策略输入计算机中。对弈的过程是在一定规则下随机进行， 计算机操作对象是对弈过程中可能出现的棋盘状态----称为格局。 下面看一下井字棋对弈。 目前我们所接触的象棋软件、围棋软件的实现原理和井字棋是 一样的。此类数据结构为树型结构

17 例4、一个城市的居民点铺设煤气管道，居民点之间的铺设费用
可以估算，要求工程完工后，每个居民点都能通气，并且总的 费用最少。 我们用图来表示这类问题。其中图的顶点表示居民点，边上 的权值表示铺设费用。 1 1 17.5 82.5 9 9 64.5 4 4 45.6 44.2 2 2 34.5 3 3 64.5 28.5 71.5 5 55.2 30.4 5 6 6 7 75.0 7 8 8 （B、铺设方案） (A、费用核算）

18 问题求解例子--五叉路口交通管理系统设计
B A C D E 对车辆可能行驶方向进行分组，要求任一组中各个方向行驶的车辆可以同时安全行驶。分组越少，可同时行驶的车辆越多，管理系统的质量就越高。 有13个可能通行的方向：AB， AC， AD， BA， BC， BD， DA， DB， DC， EA， EB， EC， ED。

19 交叉路口图式模型 将一种通行方向用一个结点表示(椭圆)； 在不能同时行驶的结点间画一条连线；
AB AC AD BC BD BA DB DC DA EB EC EA ED 问题求解：将图中结点进行分组，使有线连接的结点不在同一个组里。要解决的问题已借助图的模型 清楚而严格地表达出来。余下的问题是能否设计一个总能得到最佳的分组方案的程序。

20 求解方法（求着色问题的近似解） 1. 选出未着色的结点，并用该新颜色上色；
1. 选出未着色的结点，并用该新颜色上色； 2. 寻找仍未着色的结点，如果某结点与新颜色结点 没有边相连，则将该结点用该颜色上色。 AB AC AD BC BD BA DB DC DA EB EC EA ED 结果：1. AB AC AD BA DC ED 2. BC BD EA 3. DA DB 4. EB EC

21 问题：设有n个正常人和n个精神病患者要过一条河，
现有一条能容纳c(c<2n)个人的小船，为防止患者 伤害正常人，要求无论在河的哪一边，正常人的人数 不得少于患者人数（除非正常人数为0）。又设每个 人都会划船。试设计一个过河的最佳方案，即小船 来回次数最少的算法。

22 解：1、模型构造： 用一个三元组（x,y,t)表示渡河过程中的某个 状态。其中，x表示起始岸上正常人的人数，y表 示起始岸上患者人数，t表示小船的位置，即： T= 1 表示小船在起始岸边 0 表示小船在目的岸边

23 2、再构造一个图，图中的每一个顶点表示一个合
法状态。合法状态所对应的三元组（x,y,t)必须满 足：x=0 或 x=n 或 x=y. 于是，渡河方案的求解就转换成一个图的搜索问题 找出从起始顶点（n,n,1)到目的顶点(0,0,0)的一 条包含边数最少的通路。若该通路不存在，表明该 问题无解。

24 3、例如，当n=2,c=2时，各合法状态及其间的变 换如图：
（2，2，1） （0，2，0） （2，0，0） （1，1，0） （2，1，0） （2，1，1） （0，1，0） （0，2，1） （1，1，1） （0，0，0）

25 1.３ 基本术语 数据（Data)：所有能被计算机处理的符号的集合。 数据元素（Data Element）：是数据这个集合中的 一个个体。
设给定数据集合为： 　D={d1，d2，．．．，dn} 则di属于D，并称di为数据元素。 数据项（Data Item）：数据元素常常还可分为若干 个数据项，数据项是数据具有意义的最小单位。

26 1.３ 基本术语 数据对象（Data Object）: 具有相同特性的 数据元素的集合。 例如：数据集合D={0，1，…，A，B，…， Z}
则：数据对象正整数N＝｛ 0，1，…｝ 　　数据对象字母C＝｛ A，B，…，Z ｝ 数据元素是数据的一个个体， 数据对象是数据的一个子集。

27 基本概念和术语 集合 线性结构 树型结构 图型结构

28 1.３ 基本术语 数据结构（Data Structure）：是带有结构的数据元素的集合。
　所谓结构就是数据元素之间的关系，即描述数据元素之间的运算及运算规则。 　用集合的形式描述，数据结构是一个二元组： 　DS=(D，R)　　 其中：D是数据元素的集合，R是D上关系的集合。 简言之，数据元素和其相互关系称为数据结构

29 基本概念和术语 数据结构的形式定义： DATA_STRUCTURE=(D,S) 其中：D是数据元素的有限集，S是D上关系的有限集
例6、复数的数据结构为： 　　　COMPLEX=(C,R) 其中：C是含两个实数的集合｛C1,C2｝；R={P},P是定义在集 合C上的一种关系｛<C1,C2>}，其中有序偶<C1,C2>表示C1是 复数的实部，C2是复数的虚部。

30 基本概念和术语 例７、假设学校的每个课题小组由一位教师，一至三名研究生 及一至六名本科生组成，小组成员之间的关系是：教师指导研究
生，而由每位研究生指导一至二名本科生。则定义如下数据结构： 　　　　GROUP=(P,R) 其中：P={T,G1, ...,Gn,S11,...,Snm} 1≤n≤3,1≤m≤2 R={R1,R2} R1={<T,Gi>|1≤i≤n,1≤n≤3} R2={<Gi,Sij>|1≤i≤n,1≤j≤m,1≤n≤3,1≤m≤2} 上述数据结构的定义仅是对操作对象的一种数学描述，其中的关 系描述的是数据元素间的逻辑关系，又称数据的逻辑结构。

31 1.３ 基本术语 逻辑结构（Logical Structure）： 指数据元素之间的结构关系。
物理结构（Physical Structure）： 指数据结构在机内的表示，也称为存储结构。

32 基本概念和术语 假设用两个字长的位串表示一个实数，则可用地址相邻的四 个字串表示一个复数。下图（A）表示复数Z1=3.0-2.3i和
Z2= i的顺序存储结构；图（B）表示复数Z1的链式存 储结构，其中实部和虚部之间的关系用值为“0415”的指针来 表示 0300 3.0 0415 -2.3 0302 -2.3 0632 -0.7 0611 3.0 0634 4.8 0613 0415 (B) (A)

33 1.４ 算法描述和算法分析 ２．算法基本特性： 有穷性：算法经有限步后结束； 确定性：下一步必须是明确的； 可行性：每一步是可执行的；
一．算法（Algorithm） １．算法概念：算法是一个有限的指令集， 遵循指令流可以完成特定的功能。 ２．算法基本特性： 有穷性：算法经有限步后结束； 确定性：下一步必须是明确的； 可行性：每一步是可执行的；

34 例：试说明下述过程是否是一个算法： 1、开始； 2、n<=0; 3、n:=n+1; 4、重复3； 5、结束。 1、开始；
例：试说明下述不超过100万次的计数过程是一个算法： 1、开始； 2、n<=0; 3、n:=n+1; 4、若n=10^6,则顺次执行5，否则重复3； 5、结束。

35 1.４ 算法描述和算法分析 ３．算法与程序的区别 主要区别在：有穷性 和描述方法 程序可以是无穷的，例如OS，算法是有穷的；
算法 是解决问题的一种方法或一个过程，考虑如何将 输入转换成输出，一个问题可以有多种算法。 程序 是用某种程序设计语言对算法的具体实现。 主要区别在：有穷性 和描述方法 程序可以是无穷的，例如OS，算法是有穷的； 程序是用程序设计语言描述，在机器上可以执行； 算法还可以用框图、自然语言等方式描述。

36 算法及其评价 评价一个算法一般从四个方面进行：正确性、运 行时间、占用空间和简单性。
运行时间用时间复杂度来衡量。所谓时间复杂度 是指算法中包含的简单操作次数，一般只计算相 应的数量级：O(1),O(log2n),O(n),O(n2)等。 常用时间复杂度有如下关系： O(1) ≤O(log2n) ≤O(n) ≤O(nlog2n) ≤O(n2) ≤... ≤O(n k) ≤O(2n)

37 1.４ 算法描述和算法分析 二．算法描述语言——类Pascal
所有的算法均以过程或函数的形式表示； 　PROC　过程名 (参数表)； 　｛算法说明｝ 　　语句组 　ENDP； {过程名}

38 1.４ 算法描述和算法分析 FUNC 函数名 (参数表)：类型； ｛函数说明｝ 语句组 RETURN(f) ENDF； {函数名}
　｛函数说明｝ 　　语句组 RETURN(f) 　ENDF； {函数名} 　调用过程语句为：过程名（参数表） 　调用函数语句为：变量名：＝函数名（参数表）

39 1.４ 算法描述和算法分析 出错语句：ERROR（‘出错信息’）； 注释语句：｛注释内容｝ 语句结束符号：； 语句组符号：［ ］
语句组符号：［　］ 基本函数：max()、min()、 　　　　　 abs() 、eof 、eoln 布尔运算：AND、OR、NOT、CAND、COR

40 1.４ 算法描述和算法分析 赋值语句：变量名：＝表达式； 分支语句：IF 条件 THEN 语句 ELSE 语 句； CASE
条件１：语句１； 　　　　　　 ．．． 　　　　　　 条件n ： 语句n； (ELSE 　语句n+1) ENDC；　　　　　　

41 1.４ 算法描述和算法分析 循环语句： FOR 变量名：＝初值 TO 终值 DO 循环体； 标准输入输出过程：read（变量表）；
FOR 变量名：＝初值 DOWNTO 终值 DO 循环体； WHILE 条件 DO 循环体； REPEAT 循环体 UNTIL 条件； 标准输入输出过程：read（变量表）； write（变量表）；

42 1.４ 算法描述和算法分析 三．算法分析 如何衡量一个正确算法的好坏？ 衡量的三个尺度： 运行所花费的时间（算法的时间特性）；
所占用存储空间的大小（算法的空间特性）； 其他（可读性、易调性、健壮性等）。 时间和空间特性的巨大改进源于更好的数据 结构或算法。 算法的复杂性是算法效率的度量，也是评价算法优劣的重要依据。对任意给定的问题，设计出复杂性低的算法是设计时追求的一个重要的目标；另一方面，当给定问题有多种算法时，选择复杂性最低者，是选用算法时应遵循的一个重要准则。 弄清：1、用什么量来表达一个算法的复杂性； 2、怎样计算一个算法的复杂性。

43 1.４ 算法描述和算法分析 语句频度（Frequency Count）： 语句可能重复执行的最大次数。
时间复杂度（Time Complexity）： 设算法中所有语句的语句频度为t(n)， f(n)是当n趋向无穷大时与t(n)为同阶无穷大， 则算法的时间复杂度T(n)=O(f(n)) 其中：n为算法计算量或称为规模（size）； f(n)是运算时间随n增大时的增长率； O(f(n))是算法时间特性的量度。

44 1.４ 算法描述和算法分析 例：程序段 语句频度 时间复杂度 1. x:=x+1； 1 O(1) 常数阶
例：程序段 语句频度 时间复杂度 1. x:=x+1； O(1) 常数阶 2. FOR i:=1 TO n DO x:=x+1； n O(n) 线性阶 3. FOR i:=1 TO n DO n FOR j:= 1 TO n DO x:=x+1； n^2 O(n2) 平方阶

45 算法及其评价 例8、计算下面程序的时间复杂度： For i:=1 to (n-1) do [ y:=y+1; ①
for j:=0 to (2 * n) do x:=x+1; ② ] 其中语句①的频度是n-1,语句②的频度是(n-1)*(2n+1)= 2n2-n-1,则该程序段的时间复杂度T(n)=O(n2)

46 算法及其评价 例9、计算下面程序的时间复杂度: i:=1; ① while (i≤n) do i:=i*2; ②
语句①频度是1，语句②频度是f(n),则有： 2f(n) ≤n f(n) ≤log2n,取最大值f(n)=log2n 该段程序的时间复杂度T(n)=O(log2n)

47 算法及其评价 例10、计算下面程序的时间复杂度: A:=0;b:=1; ① for(i:=2;i≤n;i++) { s:=a+b; ②
b:=a; ③ a:=s; ④ } T(n)=2+3*(n-1)=3n-1=O(n)

48 算法及其评价 例11、计算下面程序中order()的时间复杂度: 设T(n)是排 a[]={2,5,1,7,9,3,6,8}
则有： T(n)= T(n-1)+n-1 (n>1) (n=1) a[]={2,5,1,7,9,3,6,8} order(int j,int m) { int i,temp; if(j<m) { for(i=j+1;i≤m;i++) if(a[i]<a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } j++; order(j,m); } } 求解过程： T(n)=[T(n-2)+(n-2)]+(n-1) =[T(n-3)+(n-3)]+(n-2)+(n-1) = =(T(1)+1)+2...+n-1 = n-1 =n(n-1)/2=O(n2)

49 算法与时间复杂性的关系 设：A1，A2和A3是求解同一问题的不同算法，其时间 复杂度分别为：O(n)，O(nlogn)，O(N!)。C1和C2 为计算机，且C2的计算速度是C1的10倍。 复杂度 C1可解规模 C2可解规模 可解规模的关系 O(n) N N N21=10N11 O(nlogn) N N N22=10N12 O(N!) N N N23=N13+小常数 不必追求高效算法，低效算法可由高速计算机来弥补的看法是错误的。

50 第一章 小结 数据结构概念 算法时间复杂度

51 作业1、设有数据结构(D,R),其中D=(e1,e2,e3,
E4,e5,e6,e7),R={r},r={(e1,e2),(e1,e7), (e2,e3),(e2,e4),(e3,e5),(e4,e5),(e2,e6), (e5,e6),(e6,e7)}.试按图论中图的画法惯例画出 该数据结构图。 作业2、已知6个队A,B,C,D,E和F进行球赛，已经 比赛过的场次有A同B,C，B同D,F，E同C,F.设每个 队每周比赛一次，试给出一种调度算法，使得所有 的队能在最短的时间内相互之间比赛完。

52 作业3 计算n!的递归函数fac(n)如下，试分析它的
运行时间。 Function fac(n:integer):integer; begin (1) if n<=1 then (2) fac:=1 else (3) fac:=n*fac(n-1) End;

53 作业4：试编写算法求一元多项式Pn=∑(aixi)
(0≤I≤n)的值Pn(x0).注意本题中的输入为ai, I=0,1,···,n,x0和n,输出量为pn(x0)