数据结构 张秀虹 青岛理工大学计算机系zxh@qdiae.edu.cn

与其他课程的关系 后续课的基础如 课时安排： 先修——C语言, 算法描述的基础之一 操作系统、数据库、编译原理… 数据结构——64学时 （4学分） 上机——20学时 考核要求 作业+平时+上机： 30% 期末考试： 70%

教材： 数据结构C语言版 严蔚敏 吴伟民（清华） 参考文献 Data Structures & Program Design in C(2nd ed.), Robert L.Kruse, Clovis L. Tondo, Bruce P. Leung, 1997, Prentice Hall. 数据结构与程序设计(C语言描述)-影印版(gravure).北京：清华大学出版社，1998.7.

第一章 绪 论

1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度

1.1 数据结构讨论的范畴 Niklaus Wirth： Algorithm + Data Structures = Programs 程序设计: 算法: 数据结构: 为计算机处理问题编制 一组指令集 处理问题的策略 问题的数学模型

例如: 数值计算的程序设计问题 结构静力分析计算 ─━ 线性代数方程组 全球天气预报 ─━ 环流模式方程 (球面坐标系)

非数值计算的程序设计问题 例1 书目自动检索系统 书目卡片 线性表 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目文件 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 按书名 按作者名 按分类号 索引表

树 例2 人机对奕问题 …….. …...

图 多叉路口交通灯管理问题 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED

概括地说： 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。

1.2 基本概念 一、数据与数据结构 二、数据类型 三、抽象数据类型

一、数据与数据结构 数据: 所有能被输入到计算机中，且能被计算机处理的符号的集合。 是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符号表示形式。

数据元素: 是数据（集合）中的一个“个体” 是数据结构中讨论的基本单位

数据项： 是数据结构中讨论的最小单位 数据元素可以是数据项的集合 例如： 描述一个运动员的数据元素可以是 称之为组合项

数据结构： 带结构的数据元素的集合 ≠ 则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a3 假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。 例如: 3214,6587,9345 ─ a1(3214),a2(6587),a3(9345) 则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a3 ≠ 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3

数据结构： 带结构的数据元素的集合 行的次序关系: 列的次序关系: a1 a3 a5 a2 a4 a6 a1 a2 a3 a4 a5 a6 中六个元素之间 存在两个关系: 行的次序关系: 列的次序关系: row = {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>} col = {<a1,a4>,<a2,a5>,<a3,a6>} a1 a3 a5 a2 a4 a6 a1 a2 a3 a4 a5 a6

{<ai, ai+1>| i=1, 2, 3, 4, 5} 数据结构： 带结构的数据元素的集合 再例，在一维数组 {a1, a2, a3, a4, a5, a6} 的数据元素之间存在如下的次序关系: {<ai, ai+1>| i=1, 2, 3, 4, 5} 可见，不同的“关系”构成不同的“结构” 或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。

数据的逻辑结构可归结为以下四类: 线性结构 树形结构 图状结构 集合结构

Data_Structures = (D, S) 数据结构的形式定义为: 数据结构是一个二元组 Data_Structures = (D, S) 其中:D 是数据元素的有限集， S 是 D上关系的有限集。

例1-4 复数的数据结构定义如下 Complex=(C，R) 其中： C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。

定义DS如下： Group=（D，R） 其中： 例1-5 课题组由1名教师、1~3名研究生、1~6名本科生组成；成员关系是：教师指导研究生、研究生指导1~2名本科生。 定义DS如下： Group=（D，R） 其中： D={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 }

数据的存储结构 —— 逻辑结构在存储器中的映象 “数据元素”的映象 ？ “关系”的映象 ？

数据的逻辑结构—只抽象反映数据元素的逻辑关系 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构

存储结构分为： 顺序存储结构——借助元素在存储器中的 相对位置来表示数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系

顺序存储 元素n …….. 元素i 元素2 元素1 Lo Lo+m Lo+(i-1)*m Lo+（n-1)*m 存储地址 存储内容 Loc(元素i)=Lo+（i-1)*m 顺序存储

h h ∧ 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. 元素2 1536 元素3 1345 链式存储 1345 h 元素1 1400 元素2 1536 元素3 1346 元素4 ∧ 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. 元素2 1536 元素3

二、数据类型 在用高级程序语言编写的程序中， 必须对程序中出现的每个变量、 常量或表达式，明确说明它们所 属的数据类型。

例如，C 语言中提供的基本数据类型有: 整型 int 浮点型 float 实型（ C++语言） 双精度型 double 字符型 char 逻辑型 bool （ C++语言）

不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。 数据类型 是一个 值的集合 和定义在此集合上的 一组操作 的总称。

是指一个数学模型以及定义在此数学模型上的一组操作。 三、抽象数据类型 (Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作。

例如，抽象数据类型复数的定义： ADT Complex { 数据对象： D＝{e1,e2｜e1,e2∈RealSet } 数据关系： R1＝{<e1,e2> | e1是复数的实数部分 | e2 是复数的虚数部分 }

AssignComplex( &Z, v1, v2 ) 基本操作： 操作结果：构造复数 Z,其实部和虚部 DestroyComplex( &Z) 操作结果：复数Z被销毁。 GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。

GetImag( Z, &ImagPart ) } ADT Complex 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的 和值。 } ADT Complex

假设:z1和z2是上述定义的复数 则 Add(z1, z2, z3) 操作的结果 即为用户企求的结果 z3 = z1 + z2

ADT 有两个重要特征: 数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 数据封装

抽象数据类型的描述方法 其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。 抽象数据类型可用（D，S，P）三元组表示。 其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。

ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉

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

抽象数据类型的表示和实现 抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 例如，对以上定义的复数。

typedef struct { float realpart； float imagpart； }complex； // -----存储结构的定义 typedef struct { float realpart； float imagpart； }complex； // -----基本操作的函数原型说明 void Assign( complex &Z, float realval, float imagval )； // 构造复数 Z,其实部和虚部分别被赋以参数 // realval 和 imagval 的值

float GetReal( cpmplex Z )； float Getimag( cpmplex Z )； // 返回复数 Z 的虚部值 void add( complex z1, complex z2, complex &sum )； // 以 sum 返回两个复数 z1, z2 的和

{ 其它省略 } // -----基本操作的实现 void add( complex z1, complex z2, complex &sum ) { // 以 sum 返回两个复数 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; } { 其它省略 }

1.3 算法和算法的衡量 一、算法 二、算法设计的原则 三、算法效率的衡量方法和准则 四、算法的存储空间需求

一、算法 算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性： 1．有穷性 2．确定性 3．可行性 4．有输入 5．有输出

1．有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即： 算法中的每个步骤都能在有限时间内完成。 2．确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

3．可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。 4．有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。

5．有输出 它是一组与“输入”有确 定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

二、算法设计的原则 设计算法时，通常应考虑达到以下目标： 1．正确性 2. 可读性 3．健壮性 4．高效率与低存储量需求

1．正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次： a．程序中不含语法错误； b．程序对于几组输入数据能够得出满足要求的结果；

通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。 d．程序对于一切合法的输入数据都能得出满足要求的结果； 通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。

2. 可读性 算法主要是为了人的阅读与交流， 其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。

3．健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

4．高效率与低存储量需求 通常，效率指的是算法执行时间； 存储量指的是算法执行过程中所需的 最大存储空间，两者都与问题的规模 有关。

三、算法效率的 衡量方法和准则 通常有两种衡量算法效率的方法: 事后统计法 缺点：1．必须执行程序 2．其它因素掩盖算法本质 事前分析估算法

和算法执行时间相关的因素： 1．算法选用的策略 2．问题的规模 3．编写程序的语言 4．编译程序产生的机器代码的质量 5．计算机执行指令的速度

一个特定算法的“运行工作量” 的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。

T (n) = O(f(n)) 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：

算法评价的标准：时间复杂度和空间复杂度。 指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O（1） O（logn） O（n ） O（ n2 ） 常数阶 对数阶 线性阶 平方阶 空间复杂度 指算法在计算机上运行所占用的存储空间。度量同时间复杂度。

void mult(int a[], int b[], int& c[] ) for (i=1; i<=n; ++i) 例 一 两 个 矩 阵 相 乘 void mult(int a[], int b[], int& c[] ) { for (i=1; i<=n; ++i) for (j=1; j<=n; ++j) { c[i,j] = 0; for (k=1; k<=n; ++k) c[i,j] += a[i,k]*b[k,j]; } 基本操作: 乘法操作 时间复杂度: O(n3)

void select_sort(int& a[], int n) { // 将 a 中整数序列重新排列成自小至大有序的整数序列。 例 二 选 择 排 序 for ( i = 0; i< n-1; ++i ) { if ( j != i ) a[j] ←→ a[i] } j = i; // 选择第 i 个最小元素 for ( k = i+1; k < n; ++k ) if (a[k] < a[j] ) j = k; 基本操作: 比较(数据元素)操作 时间复杂度: O(n2)

基本操作: 赋值操作 时间复杂度: O(n2) 例 void bubble_sort(int& a[], int n) { 三 起 泡 排 序 void bubble_sort(int& a[], int n) { // 将 a 中整数序列重新排列成自小至大有序的整数序列。 for (i=n-1, change=TRUE; i>1 && change; --i) } // bubble_sort { change = FALSE; // change 为元素进行交换标志 for (j=0; j<i; ++j) if (a[j] > a[j+1]) { a[j] ←→ a[j+1]; change = TRUE ;} } // 一趟起泡 基本操作: 赋值操作 时间复杂度: O(n2)

语句频度：是指该语句重复执行的次数 例3 {++x;s=0;} 将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 例4、for(i=1;i<=n;++i) {++x;s+=x;} 语句频度为：n　其时间复杂度为：O(n) 即时间复杂度为线性阶。

例４、for(i=1;i<=n;++i) 　　　　for(j=1;j<=n;++j) {++x;s+=x;} 语句频度为：n2 　其时间复杂度为：O(n2) 即时间复杂度为平方阶。

例５for(i=2;i<=n;++I) for(j=2;j<=i-1;++j) {++x;a[i，j]=x;} 语句频度为： 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2) 即此算法的时间复杂度为平方阶

以下六种计算算法时间的多项式是最常用的。其关系为： O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3) 指数时间的关系为： O(2n)<O(n!)<O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。

有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如： Void bubble-sort(int a[]，int n) for(i=n-1;change=TURE;i>1 && change;--I) { change=false; for(j=0;j<i;++j) if (a[j]>a[j+1]) { a[j] ←→a[j+1]; change=TURE} } 最好情况：0次 最坏情况：1+2+3+…+n-1 =n(n-1)/2 平均时间复杂度为:O(n2)

算法的空间复杂度定义为: S(n) = O(g(n)) 四、算法的存储空间需求 表示随着问题规模 n 的增大， 算法运行所需存储量的增长率

算法的存储量包括: 1．输入数据所占空间 2．程序本身所占空间 3．辅助变量所占空间

本章学习要点 1. 熟悉各名词、术语的含义，掌握基本概念。 2. 理解算法五个要素的确切含义。 3. 掌握计算语句频度和估算算法时间复杂度的方法。

本章作业： 数据结构题集中 1.6 1.7 1.8 1.20