数 据 结 构 主讲人:文 军

课程安排 总学时：64 讲课学时：54 实验学时：10 教材： 《数据结构C语言版》严蔚敏、吴伟民 教学参考书： -----清华大学出版社 教学参考书： （1）《数据结构C语言篇》习题与解析 李春葆 （2）《数据结构》黄杨铭 科学出版社 （3）《数据结构自学考试指导》丁宝康等 清华大学出版社，

内 容 安 排 1 2 7 10 6 8 略 3 4 9 5 11 12 章 内 容 学时 绪 论 图 线性表 动态存储管理 栈和队列 查找 内 容 学时 1 绪 论 2 7 图 10 线性表 6 8 动态存储管理 略 3 栈和队列 4 9 查找 串 内部排序 5 数组和广义表 11 外部排序 树和二叉树 12 文件

考核： 平时成绩（10%）+实验（20%）+考试（70%）

第一章 绪论 一、教学内容： 1、数据结构基本概念 数据、数据元素、数据对象、数据结构和数据类型等概念 2、算法及算法分析 性能分析与度量：算法的性能标准；空间复杂度度量；时间复杂度度量 二、教学要求： 1、了解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系 2、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价 3、掌握计算语句频度和估算算法时间复杂度的方法

什么是数据结构 基本概念和术语  抽象数据类型的概念 算法和算法分析 第一章 绪论 什么是数据结构 基本概念和术语  抽象数据类型的概念 算法和算法分析

1.1 什么是数据结构 一、了解计算机的主要用途： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 早期： 主要用于数值计算。 后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。

数值计算与非数值计算的区别? 数值计算的特点是： 数值计算的关键是： 如何得出数学模型（方程）？ 程序设计人员比较关注程序设计的技巧。 数据元素之间的相互关系一般无法用数学方程加以描述,程序设计人员主要关心的是如何设计出能恰当表达问题本质的数据模型,并在该模型上建立一组相应的服务(操作).

非数值计算问题举例： 例1.1 电话号码查询问题： （1）按顺序存储方式：须遍历表 （2）按姓氏索引方式：索引 例1.1 电话号码查询问题： （1）按顺序存储方式：须遍历表 （2）按姓氏索引方式：索引 要写出好的查找算法，取决于这张表的结构及存储方式。 电话号码表的结构和存储方式决定了查找（算法）的效率。

例1.2 田径赛的时间安排问题（无向图的着色问题） ： 例1.2 田径赛的时间安排问题（无向图的着色问题） ： 设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。

（1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时比赛）。

只需安排四个单位时间进行比赛 1 A，C 2 B，D 3 E 4 F 比赛时间 比赛项目 姓名 项目1 项目2 项目3 丁一 A B E 马二 C D 张三 F 李四 王五 只需安排四个单位时间进行比赛 比赛时间 比赛项目 1 A，C 2 B，D 3 E 4 F A B F E C D

求解非数值计算问题主要考虑的是： 设计出合适的数据结构及相应的算法。即先要考虑对相关的各种信息如何表示、组织和存储.

二、学习数据结构有什么用？ 程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。 计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

三、数据结构课程的形成和发展： 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，我国高校陆续开设该课程。

四、《数据结构课程》所处的地位：

1.2 基本概念和术语 一、几个概念： 1、数据(Data): 是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2、数据元素(Data Element): 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。

例如：学生卡片记录表 3、数据对象(Data Object)： 是性质相同的数据元素的集合。是数据的一个子集。例如，整数数据对象的集合可表示为N＝{0，±1，±2…….}，字母字符数据对象的集合可表示为C={‘A’,’B’,…’Z’}。

4、数据结构 是相互之间存在一种或多种特定关系的数据元素的集合。 形式化定义：数据结构是一个二元组 Data_Structure = (D,R) 其中，D是数据元素的有限集合，R是D上关系的集合

更具体的说明数据结构定义： 按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算（操作）。

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

（1）、集合： 结构中的数据元素除了同属于一种类型外，别无其它关系。 5、逻辑结构的分类： （1）、集合： 结构中的数据元素除了同属于一种类型外，别无其它关系。 （2）、线性结构：结构中的数据元素之间存在一对一的关系。 （3）、树型结构：结构中的数据元素之间存在一对多的关系。 a1 a2 a3 a4

（4）、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。

6、存储方法的分类： （1）顺序存储方法（顺序存储结构） （2）链接存储方法（链式存储结构） （3）索引存储方法 （4）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。

顺序存储结构: 用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构： 在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。

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

例2.1：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 例2.1：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。 （1） 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 此结构为线性的。

（2） S=(D, R) D={di | 1≤i≤5} R={(di , dj ), i<j} 解：上述表达式可用图形表示为： d1 d5 d2 d4 d3 该结构是非线性的。

1.3 抽象数据类型的表示与实现 思考： 1、数据类型与抽象数据类型的区别？ 2、 抽象数据类型如何定义？ 3、抽象数据类型如何表示和实现？ 提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，试请阅读。

一、数据类型与抽象数据类型的概念 1、数据类型：数据类型是一个值的集合和定义在这个值集上的一组操作的总称 2、抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

二、抽象数据类型如何定义 抽象数据类型可以用以下的三元组来表示： ADT = （D，R，P） 数据对象 D上的关系集 D上的操作集 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作 ：<基本操作的定义> } ADT抽象数据类型名 ADT常用定义格式

三、抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 注1 ：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。 注2 ：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。 但上机时要用具体语言实现，我们用C语言

1.4 算法和算法分析 一、算法的概念和描述： 1、什么是算法？ 是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。

2、 算法具有以下五个特性： （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 （3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 （4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 （5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

3、算法设计的要求： 评价一个好的算法有以下几个标准: (1) 正确性(Correctness ) 算法应满足具体问题的需求。 (2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解，便于调试和修改。 (3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。 注意：算法和程序的关系 算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。

二、算法的描述和实现 描述---可采用自然语言、数学语言或约定的符号语言。 实现---必须借助程序设计语言提供的数据类型及其运算。 本课的描述---采用类C语言。

三、算法分析 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

1、时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为f(n)。

例1 求下列算法段的语句频度   for(i=1; i<=n; i++) for(j =1; j <=i ; j++) x=x+1; 分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度f(n)=1+2+3+…+n=

2、时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度f(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数（。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐近时间复杂度，简称时间复杂度。

例如，若T(n)=n(n+1)/2,则有 1/4≤T(n)/n2≤1 故它的时间复杂度为Ｏ(n2), 即Ｔ(n)与n2 数量级相同。

例1.3 分析以下程序段的时间复杂度 i=1; while (i<=n) /* 1 * / 语句1的频度是：1 例1.3 分析以下程序段的时间复杂度 i=1; while (i<=n) i=i*2 语句1的频度是：1 设语句2的频度是f(n)，则有： 即 ，取最大值 则该程序段的时间复杂度为： /* 1 * / /* 2 * /

常见函数的时间复杂度按数量递增排列及增长率。 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3) …… k次方阶O(nk) 指数阶O(2n)

3、空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。

本章小结 数据、数据结构等基本概念 数据结构的三个方面的内容 抽象数据类型的概念 线性和非线性结构的逻辑特征 数据存储的四种基本方法 算法、算法的时间复杂度及其分析的简易方法

作业：