第一章 绪论 学习提要 1.1 什么是数据结构 1.2 基本概念 1.3 抽象数据类型 1.4 算法及其分析

学习提要 掌握本课程所涉及到的基本名词、术语和概念，特别是数据的逻辑结构和存储结构之间的关系及性质。 了解抽象数据类型的定义、表示和实现方法。 理解算法设计的五个要素和基本要求；掌握算法效率的度量方法，着重学习算法的时间复杂度分析。

1.1 什么是数据结构 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 1.1 什么是数据结构 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 形成背景：计算机应用由科学计算——〉控制、管理、数据处理；加工对象由纯数值——〉字符、表格、图象、声音等具有一定结构的数据 瑞士计算机科学家沃思(N.Wirth)教授提出： 程序=算法+数据结构

算法设计方法： 五种基本算法 其它高级算法 贪婪算法、分而治之算法、动态规划、回朔法、分枝定界 线性规划、整数规划、遗传算法、模拟退火等 返回

数据结构研究的主要内容： 数据的逻辑结构：反映数据元素间的逻辑关系 数据的物理（存储）结构：反映数据元素及其关系在计算机存储器内的存储安排； 包括线性结构、树形结构、图形结构 数据的物理（存储）结构：反映数据元素及其关系在计算机存储器内的存储安排； 包括：顺序存储、 链接存储、 索引存储、 散列存储 数据的运算：对数据元素施加的操作，如插入、删除、排序等。 一般将逻辑上的数据结构简称为 数据结构。

数据结构对我们解决问题有什么实际作用啊？ 计算机专业学生一定要学好数据结构么？

用计算机解决问题的过程 建立模型 构造求解算法 选择存储结构 编写程序 测试 数据结构的作用 描述问题的共性 选择合适的模型 描述问题的求解方法 构造求解算法 进行更为复杂的算法设计 将问题涉及的数据存储到计算机中 选择存储结构 选择合理的存储结构 编写程序 提高编程技术 测试

他们是否该掌握数据结构知识？需要掌握到什么程度？ 举例： 计算机专业人员可能从事的职业 程序员 高级程序员 系统架构师 项目经理 技术、业务顾问 测试 信息系统维护 自行创业 数据结构知识掌握程度： 1级——理解基本概念 2级——掌握基本算法 3级——运用所学知识解决常见问题 4级——建立数据模型解决复杂问题

引 例 书目自动检索系统的数学模型 书目卡片 线性表 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目文件 索引表 引 例 线性表 书目自动检索系统的数学模型 书目文件 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 按书名 按作者名 按分类号 索引表

人机对奕问题的数学模型 树 …….. …...

引 例 十字路口的交通灯管理问题的数学模型 图 AB AC AD BA BC BD DA DB DC EA EB EC ED C E D A 引 例 图 十字路口的交通灯管理问题的数学模型 AB AC AD BA BC BD DA DB DC EA EB EC ED C E D A B

1.2 基本概念 1.2.1 几个名词 1、数据（data） 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合, 是计算机程序加工的”原料”。 分类： 数值性数据 非数值性数据

2、数据元素 (data element) 数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 有时一个数据元素可以由若干数据项(Data Item)组成。数据项是具有独立含义的最小标识单位。 数据元素又称为元素、结点、记录。 学号 姓名 成绩 101 jane 80 103 jack 90 102 jerry 75

3、数据对象 (data object) 数据对象是具有相同性质的数据元素的集合。 整数数据对象 N = { 0, 1, 2, … } 字母字符数据对象 C={‘A’，’B’，…，’Z’} 学生成绩数据对象 Cj={（‘101’，‘jane’，80）， （ ‘102’，‘jack’，90 ）， （ ‘103’，‘jerry’，75 ）} 学号 姓名 成绩 101 jane 80 103 jack 90 102 jerry 75

4、数据结构 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 用一个二元组表示，记为： Data_Structure = （D, S） 其中，D 是数据元素的有限集（即一个数据对象），S 是该对象中所有数据成员之间的关系的有限集合。

根据数据元素之间关系的不同特性，可分为四种基本结构： 集合 线性结构 树形结构 图形结构 数据元素之间存在着一个对多个的关系 树 二叉树 二叉搜索树 14 13 12 11 2 3 4 5 6 7 8 9 10 1 根据数据元素之间关系的不同特性，可分为四种基本结构： 集合 线性结构 树形结构 图形结构 图形（网状）结构 数据元素之间存 在着多对多的关系。 1 5 2 4 3 6 etc user 集合 数据元素之间无特殊关系 dev lib bin 线性结构 数据元素之间存在着一个对一个的关系 bin dev etc lib user

5. 数据的逻辑结构 数据的逻辑结构从逻辑关系上描述数据，可以看作是从具体问题抽象出来的数据模型，与数据的存储无关，也与数据元素本身的形式、内容、相对位置无关； 数据的逻辑结构分类： 线性结构 线性表、栈、队列 、串 非线性结构 树 、图（或网络） 一维数组是线性结构， 多维数组为非线性结构

6. 数据的存储结构 数据的存储结构是逻辑结构用计算机语言的实现，依赖于计算机语言； 存储结构分类: 顺序存储表示 链接存储表示 6. 数据的存储结构 数据的存储结构是逻辑结构用计算机语言的实现，依赖于计算机语言； 存储结构分类: 顺序存储表示 链接存储表示 索引存储表示 散列存储表示

注意: 通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

1.3 抽象数据类型 1. 数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称. C语言中的基本数据类型 1.3 抽象数据类型 1. 数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称. C语言中的基本数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值

数据类型就是数据结构，不过它是从编程者的角度来使用的。 数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。 基本数据类型可以看作是计算机中已实现的数据结构。 构造数据类型由基本数据类型或构造数据类型组成。 构造数据类型由不同成分类型构成。

2. 抽象数据类型的概念 (ADTs: Abstract Data Types) 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作） 信息隐蔽和数据封装，使用与实现相分离

3. 抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名

其中，数据对象和数据关系的定义用伪码（不真正执行的符号）描述 基本操作的定义格式为： 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头， 除了可以提供输入值外，还将返回操作结果。 “初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。 “操作结果” 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。

举例——抽象数据类型复数的定义： ADT Complex { 数据对象：D＝{e1,e2｜e1,e2∈RealSet } 数据关系：R1＝{<e1,e2| e1是复数的实数部分, e2 是复数的虚数部分 } 基本操作： InitComplex( &Z, v1, v2 ) 操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( &Z) 操作结果：复数Z被销毁。

GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, &ImagPart ) 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum ) 初始条件：z1,z2是复数。 操作结果：用sum返回两个复数z1,z2的和值。 } ADT Complex 假设: z1和z2是上述定义的复数，则Add(z1,z2,z3)操作的结果将得到z3=z1+z2

1.4 算法和算法分析 算法的定义：是对特定问题求解步骤的一种描述,是一个有穷的指令集，这些指令表示一个或多个操作 算法的特性(要素)： 有穷性 算法应在执行有穷步后结束,且每一步都在有穷时间内完成 确定性 每步定义都是确切、无歧义的 可行性 算法中描述的操作应能通过执行有限次已经实现的基本运算而实现 输入 有0个或多个输入 输出 有一个或多个输出(处理结果)

算法的描述 流程图、代码符号专用工具 程序设计语言 自然语言（易产生歧义，繁琐，且当今的计算机尚不能处理）

正确性：不含有语法错误；对于各种合法的输 算法设计的要求 正确性：不含有语法错误；对于各种合法的输 入数据能够得到满足规格说明要求的 结果。 可读性：要求程序有较好的人机交互性,有 助于人们对算法的理解。 健壮性：对输入的非法数据能作出适当的 响应或处理。 效率与低存储需求：主要指算法的执行时间和 所需的最大存储空间，这两方面主要和问题 的规模有关。

算法设计思路： 自顶向下，逐步求精 事例学习：将全班同学按身高从低到高排成一列 ——用选择排序方法解决问题 明确问题：递增排序 解决方案：逐个选择最小身高的同学 算法框架： for ( int i = 0; i < n-1; i++ ) { //n-1趟 从a[i]检查到a[n-1]; 若最小整数在a[k], 交换a[i]与a[k]; } 细化程序：程序 SelectSort

开始时: i=0, k=i=0 , a[k]=8 , j=i+1=1 ∵ a[j]=a[1]=5<a[k]=8 ∴ k=j=1 以 8, 5 ,7 ,6 ,9 ,10 为例：a[0]=8,a[1]=5…a[5]=10 开始时: i=0, k=i=0 , a[k]=8 , j=i+1=1 ∵ a[j]=a[1]=5<a[k]=8 ∴ k=j=1 交换： temp=a[i]=8 ，a[i]=a[k] ，a[k]= a[1]=temp void selectSort ( int a[ ], int n ) { //对n个整数a[0],a[1],…,a[n-1]按递增顺序排序 for ( int i = 0; i < n-1; i++ ) { int k = i; //从a[i]查到a[n-1], 找最小整数, 在a[k] for ( int j = i+1; j < n; j++ ) if ( a[j] < a[k] ) k = j; int temp = a[i]; a[i] = a[k]; a[k] = temp; } 5 8

算法的性能分析与度量 算法的后期测试：在算法中的某些部位 算法的事前估计： 空间复杂度 插装时间函数 time ( )测定算法完成 某一功能所花费时间 算法的事前估计： 空间复杂度 时间复杂度

插装 time( ) 的计时程序 顺序搜索 (Sequenial Search) int seqsearch ( int a[ ], int n, int x ) { //在a[0],…,a[n-1]中搜索x int i = 0; while ( i < n && a[i] != x ) i++; if ( i == n ) return -1; return i; } 插装 time( ) 的计时程序 double start, stop; time (&start); int k = seqsearch (a, n, x); time (&stop); double runTime = stop - start; printf ( ”%d%d\n " , n, runTime );

与算法执行时间相关的因素有： 1）算法选用的策略 2）问题的规模 3）编写程序的语言 4）编译程序产生的机器代码的质量 5）计算机执行指令的速度 通常把算法中所包含的简单操作次数的多少叫做算法的时间复杂度。算法的执行时间与简单操作执行次数之和成正比。简单操作次数越少，运行时间也越少。

时间复杂度度量 运行时间 = 算法中每条语句执行时间之和。 每条语句执行时间 = 该语句的执行次数（频度）* 语句执行一次所需时间。 语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。 设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。

例1 求两个n阶方阵的乘积C = AB void MatrixMultiply ( int A[n][n], int B[n][n], int C[n][n] ) { for ( int i = 0; i < n; i++ ) … n+1 for ( int j = 0; j < n; j++ ) { … n(n+1) C[i][j] = 0; … n2 for ( int k = 0; k < n; k++ ) … n2(n+1) C[i][j] = C[i][j] + A[i][k] * B[k][j]; … n3 } 2n3 + 3n2 + 2n +1

例2 累加求和的时间复杂度计算 int sum(int b[ ],int n) { int s=0; // 执行1次 例2 累加求和的时间复杂度计算 int sum(int b[ ],int n) { int s=0; // 执行1次 for(int i=0;i<n;i++) s+=b[i]; return s; // 执行1次 } 执行次数分解 合计： f(n)=1+4n+2+1=4n+4

FOR循环所包含的简单操作次数的分解： Int i; // 非执行语句，运行时不执行任何操作 i=0; // 1次 Mark1: if(i>=n) goto mark2; //n+1次 S+=b[i]; //n次 i++; //n次 Goto mark1; //n次 Mark2: return s; 小计：4n+2

时间复杂度度量方法 设解决一个问题的规模为n ，简单操作被重复执行的次数是n的一个函数 f（n），假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T (n) = O(f(n)) 其中T（n）叫算法的渐进时间复杂度，简称时间复杂度， O是Order（数量级）的首字母，意思是T（n）与f（n）只差一个常数倍。 例1中： T(n) = 2n3 +3n2 + 2n +1 = O(n3)

渐进时间复杂度的计算 加法规则—— 针对并列程序段 = O(max (f (n), g (m))) T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m))) 注：c < log2n < n < nlog2n < n2 < n3 < 2n < 3n < n!

for ( int k = 0; k < n; k ++ ) x ++; 变量计数 x = 0; y = 0; for ( int k = 0; k < n; k ++ ) x ++; for ( int i = 0; i < n; i++ ) for ( int j = 0; j < n; j++ ) y ++; T1(n) = O(1) T2(n) = O(n) T3(n) = O(n2) T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)

乘法规则——针对嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m)) 举例

例3 起泡排序 void bubbleSort ( int A[n] ) { //对表逐趟比较, n是表当前长度 int i = 1; exchange = 1; while ( i < n && exchange ) { BubbleExchange ( A, i, exchange ); i++; } //一趟比较 }

void BubbleExchange( int A[n], int i ){ for ( int j = n -1; j >= i; j--) if ( A[j-1] > A[j] ) { int temp = A[j-1]; A[j-1] = A[j]; A[j] = temp;; //发生逆序, 交换 }

渐进时间复杂度 O(f (n)*g (n)) = O(n2) BubbleSort n-1趟 T1(n) = O(n) BubbleExchange ( ) n-i 次比较

有时, 算法的时间复杂度不仅依赖于问题规模n，还与输入实例的初始排列有关。 例如：在数组 A[n] 中查找给定值 k 的算法： int i = n-1; while ( i >= 0 && A[i] != k ) i--; return i; 算法的语句 i-- 的频度不仅与 n 有关，还与 A[ ] 中各元素的取值，以及 k 的取值有关。

例4：设有两个算法在同一机器上运行，其执行时间分别为 100n2 和 2n，问：要使前者快于后者，n 至少要取多大？ 解答： 问题是找出满足 100n2 <= 2n 的最小的n。用试探法： n = 13时，100n2 = 16900 > 2n = 8192 n = 14时，100n2 = 19600 > 2n = 16384 n = 15时，100n2 = 22500 < 2n = 32764 取 n = 15 满足要求。

算法的空间复杂度 1．输入数据所占空间; 2．程序本身所占空间； 3．辅助变量所占空间。 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，记作： S(n) = O(g(n)) 表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。 算法的存储量包括： 1．输入数据所占空间; 2．程序本身所占空间； 3．辅助变量所占空间。

存储空间的两个部分： 存储空间的固定部分 程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间 可变部分 尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间

提示： 算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。

一、判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 例 题 一、判断下列叙述的对错。如果正确，在题前打“”，否则打“”。 1、数据元素是数据的最小单位。 2、数据结构是数据对象与对象中数据元素之间关系的集合。 3、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 4、算法和程序原则上没有区别，在讨论数据结构时二者是通用的。

二、试计算以下求和程序中所有语句的总执行次数。 float sum ( float a[ ], int n ) { float s = 0.0; ---- 1 for ( int i = 0; i < n; i++ ) ---- n+1 s += a[i]; ---- n return s; ---- 1 } ---- 2n+3

用大O表示法给出程序的时间复杂性。 void out ( float x[ ][ ], int m, int n ) { float sum[ ]; O(1) for ( int i = 0; i < m; i++ ) { sum[i] = 0.0; for ( int j = 0; j < n; j++ ) sum[i] = x[i][j]; O(m*n) } for ( int i = 0; i < m; i++ ) cout << "Line: " << i << ":" << sum[i] << endl; O(m) T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, m*n, m ) ) = O(m*n )

本章小结 与数据结构相关的几个名词概念 数据结构研究的内容： 抽象数据类型 算法分析：时间复杂度、空间复杂度 数据的逻辑结构 数据的物理结构（存储结构） 在数据结构上的操作 抽象数据类型 算法分析：时间复杂度、空间复杂度