第一章 绪论第一节 数据结构讨论的范畴
算法 +数据结构 = 程序设计
很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述，而大量 非数值计算问题 的数学模型正是本门课程要讨论的数据结构。
例一,求 n 个整数中的最大值。这似乎不成问题，但如果这些整数的值有可能达到 1012，那么对 32位的计算机来说，就存在一个如何表示的问题。
例
例二,交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、
直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？
例三,煤气管道的铺设问题。如右图需为城市的各小区之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境不同等因素使各条管线所需投资不同 (如图上所标识 )，
如何使投资成本最低？
什么是数据结构?
计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行 组织管理,将此称为 非数值性处理 。
数据结构是一门讨论,描述现实世界实体的数学模型 (非数值计算 )及其上的操作在计算机中如何表示和实现,的学科。
要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的 表示方式 以及 各个操作 的具体实现手段。这些就是,数据结构,这门课程研究的主要内容。
1.2.1 基本概念和术语
数据是所有能被输入到计算机中，且能被计算机处理的符号 (数字、字符等 )的集合，它是计算机操作对象的总称。
数据是个集合，如果用集合的表示方法来写的话，就是数据 ={x|x是计算机操作的对象 }
数据元素是数据 (集合 )中的一个 "个体 "，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的 "基本单位 "。
两类数据元素
一类是不可分割的“原子”型数据元素，如：整数,5”，字符,N” 等
另一类是由多个款项构成的数据元素,其中每个款项 被称为一个,数据项,。
例如 描述一个学生的信息的数据元素可由下列 6
个数据项组成。
数据项是数据结构中讨论的 "最小单位 "。
在由多个数据项构成的数据元素中必定存在关键字。
关键字指的是能识别一个或多个数据元素的数据项。
若能起唯一识别作用，则称之为,主” 关键字，
否则称之为,次” 关键字。
数据对象是具有相同特性的数据元素的集合，如：整数、实数等。它是数据的一个子集。
在同一个数学模型中的数据元素必然具有相同特性。
1.2.2 数据结构
若在 特性相同的数据元素集合中 的数据元素之间存在一种或多种特定的 关系,则称该数据元素的集合为 "数据结构,
换句话说，数据结构是带,结构,的数据元素的集合。
,结构,即指数据元素之间存在的 关系 。
数据结构 是一堆数据元素和这些数据元素之间的关系的总和。
例
可以用下述数据结构来描述 2行 3列的矩阵：它是一个含 6个数据元素 {a1,a2,a3,a4,a5,a6} 的集合，
且集合上存在“行关系”和“列关系”两个次序关系，其中行关系为 {<a1,a2>,<a2,a3>，
<a4,a5>,<a5,a6>}，列关系为
{<a1,a4>,<a2,a5>,<a3,a6>}。
<x,y> 意为 x 和 y 之间存在 "x领先于 y" 的次序关系。
654
321
aaa
aaa
例
某校一个年级有两个班，由一个级主任带班，每个班按所住宿舍分组，他们之间的关系可如下描述,{ <班主任，班长 1>,<班主任，班长 2>,<
班长 1，舍长 1>,……,<班长 2，舍长 p>,<舍长
1，学生 1>,<舍长 1，学生 2>,……,<舍长 p，
学生 n> }
数据结构的形式定义
数据结构是一个二元组
Data_Structures = ( D,S )
其中,D是 数据元素 的有限集，
S是 D上 关系 的有限集。
按关系或结构分，数据结构可归结为以下四类：
①
②
③
④
数据结构的两个方面
包括数据的,逻辑结构,和数据的,物理结构,两个方面
数据逻辑结构 是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。
数据物理结构 是数据逻辑结构在计算机中的表示和实现，故又称数据 "存储结构 "。
存储结构
存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。
有两种表示方法：
以 <x,y>的有序对为例,即 x和 y在逻辑上有先后关系
一为“顺序映象”。以,y 相对于 x 的存储位置”
表示,y 是 x的后继”,(即 x和 y在存储位置上是有先后关系的 )由此得到的数据存储结构为,顺序存储结构,。
二为“链式映象”。以和 x绑定在一起的附加信息
(指针 )表示后继关系,(即 x和 y在存储位置上是没有先后关系的 )这个指针即为 y 的存储地址，由此得到的数据存储结构为 "链式存储结构 "。
1.2.3 数据类型和抽象数据类型
数据类型 是一个“值”的集合和定义在此集合上的“一组操作”的总称。
程序中对变量或常量说明其所属类型的作用是，对它们加上两个约束条件：一是可取值的范围，二是可进行的操作。
抽象数据类型 （ Abstract Data Type 简称
ADT）是指一个数学模型以及定义在此数学模型上的一组操作。
抽象数据类型的形式描述为：
ADT = ( 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
常见的特殊约定
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
常见的特殊约定
赋值参数只为操作提供输入值；
引用参数以 &打头,除可提供输入值外，还将返回操作结果。
成组赋值 （变量名 1,...，变量名 n） =（表达式 1,,..，
表达式 n）；
结构赋值 结构名 1 = 结构名 2；
结构名 =（值 1，值 2,...，值 n）；
条件赋值 变量名 = 条件表达式? 表达式 1：表达式 2；
交换赋值 变量名 1? 变量名 2；
1.3.1 算法及其设计原则
算法 是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、
有限长的操作序列。
算法必须满足五个重要特性
(1) 有穷性 对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。即算法中的操作步骤 为有限个，且每个步骤都能在有限 时间 内完成。
(2) 确定性 对于每种情况下所应执行的操作，
在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。表现在对算法中每一步的描述都 没有二义性,只要输入相同，初始状态相同，则无论执行多少遍，
所得结果都应该相同。
(3) 可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。指的是，序列中的每个操作都是可以简单完成的，其本身不存在算法问题,
(4) 有输入
(5) 有输出算法的评价标准
(1) 正确性,要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。
(2) 可读性,为了便于理解、测试和修改算法，算法应该具有良好的可读性。
(3) 健壮性,算法中拥有对输入数据、打开文件、
读取文件记录、分配内存空间等操作的结果检测，
并通过与用户对话的形式做出相应的处理选择。
(4) 时间与空间效率,算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。
1.3.3 算法效率的衡量方法
如何估算算法的时间效率？
和算法执行时间相关的因素有：
1）算法所用“策略”；
2）算法所解问题的“规模”；
3）编程所用“语言”；
4）“编译”的质量；
5）执行算法的计算机的 "速度 "。
一个算法的执行时间可以看成是所有原操作的执行时间之和
∑( 原操作 (i)的执行次数 × 原操作 (i)的执行时间 )
这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。
例,两个 n × n 的矩阵相乘。
void Mult_matrix( int c[][],int a[][],int b[][],int n)
{
// a,b 和 c 均为 n 阶方阵，且 c 是 a 和 b 的乘积
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];
}
}// Mult_matrix
算法的时间复杂度为 O (n3)
例,对 n 个整数进行选择排序。
void select_sort(int a[],int n)
{
// 将 a 中整数序列重新排列成自小至大有序的整数序列。
for ( i = 0; i< n-1; ++i )
{
j = i;
for ( k = i+1; k < n; ++k )
if (a[k] < a[j] ) j = k;
if ( j != i ) { w = a[j]; a[j] = a[i]; a[i] = w;}
}
} // select_sort
算法的时间复杂度为 O (n2) 。
例,对 n 个整数的序列进行起泡排序
void bubble_sort(int a[],int n)
{
// 将 a 中整数序列重新排列成自小至大有序的整数序列。
for (i=n-1,change=TRUE; i>1 && change; --i)
{
change = FALSE;
for (j=0; j<i; ++j)
if (a[j] > a[j+1])
{ w = a[j]; a[j]= a[j+1]; a[j+1]= w; change = TRUE }
}
} // bubble_sort
算法的时间复杂度为 O (n2) 。
1.3.4 算法的存储空间需求
算法的存储量 指的是算法执行过程中所需的最大存储空间。
包括以下三部分：
(1)输入数据所占空间；
(2)程序本身所占空间；
(3)辅助变量所占空间。
练习
设 n 为正整数。试确定下列各程序段中前置以记号 @ 的语句的频度
i=1; k=0;
while ( i<=n-1)
{
@ k += 10 * i;
i++;
}
n-1
i=1; k=0;
do {
@ k +=10 * i;
i++;
} while(i<=n-1);
n-1,但 n=1时特殊,是 1次
x=n; y=0; // n 是不小于 1的常数
while (x>=(y+1)*(y+1))
{
@ y++;
}
n
x=91; y=100;
while (y>0 ) {
@ if (x>100 ) { x -= 10; y- -; }
else x++;
}
1100
算法 +数据结构 = 程序设计
很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述，而大量 非数值计算问题 的数学模型正是本门课程要讨论的数据结构。
例一,求 n 个整数中的最大值。这似乎不成问题，但如果这些整数的值有可能达到 1012，那么对 32位的计算机来说，就存在一个如何表示的问题。
例
例二,交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、
直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？
例三,煤气管道的铺设问题。如右图需为城市的各小区之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境不同等因素使各条管线所需投资不同 (如图上所标识 )，
如何使投资成本最低？
什么是数据结构?
计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行 组织管理,将此称为 非数值性处理 。
数据结构是一门讨论,描述现实世界实体的数学模型 (非数值计算 )及其上的操作在计算机中如何表示和实现,的学科。
要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的 表示方式 以及 各个操作 的具体实现手段。这些就是,数据结构,这门课程研究的主要内容。
1.2.1 基本概念和术语
数据是所有能被输入到计算机中，且能被计算机处理的符号 (数字、字符等 )的集合，它是计算机操作对象的总称。
数据是个集合，如果用集合的表示方法来写的话，就是数据 ={x|x是计算机操作的对象 }
数据元素是数据 (集合 )中的一个 "个体 "，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的 "基本单位 "。
两类数据元素
一类是不可分割的“原子”型数据元素，如：整数,5”，字符,N” 等
另一类是由多个款项构成的数据元素,其中每个款项 被称为一个,数据项,。
例如 描述一个学生的信息的数据元素可由下列 6
个数据项组成。
数据项是数据结构中讨论的 "最小单位 "。
在由多个数据项构成的数据元素中必定存在关键字。
关键字指的是能识别一个或多个数据元素的数据项。
若能起唯一识别作用，则称之为,主” 关键字，
否则称之为,次” 关键字。
数据对象是具有相同特性的数据元素的集合，如：整数、实数等。它是数据的一个子集。
在同一个数学模型中的数据元素必然具有相同特性。
1.2.2 数据结构
若在 特性相同的数据元素集合中 的数据元素之间存在一种或多种特定的 关系,则称该数据元素的集合为 "数据结构,
换句话说，数据结构是带,结构,的数据元素的集合。
,结构,即指数据元素之间存在的 关系 。
数据结构 是一堆数据元素和这些数据元素之间的关系的总和。
例
可以用下述数据结构来描述 2行 3列的矩阵：它是一个含 6个数据元素 {a1,a2,a3,a4,a5,a6} 的集合，
且集合上存在“行关系”和“列关系”两个次序关系，其中行关系为 {<a1,a2>,<a2,a3>，
<a4,a5>,<a5,a6>}，列关系为
{<a1,a4>,<a2,a5>,<a3,a6>}。
<x,y> 意为 x 和 y 之间存在 "x领先于 y" 的次序关系。
654
321
aaa
aaa
例
某校一个年级有两个班，由一个级主任带班，每个班按所住宿舍分组，他们之间的关系可如下描述,{ <班主任，班长 1>,<班主任，班长 2>,<
班长 1，舍长 1>,……,<班长 2，舍长 p>,<舍长
1，学生 1>,<舍长 1，学生 2>,……,<舍长 p，
学生 n> }
数据结构的形式定义
数据结构是一个二元组
Data_Structures = ( D,S )
其中,D是 数据元素 的有限集，
S是 D上 关系 的有限集。
按关系或结构分，数据结构可归结为以下四类：
①
②
③
④
数据结构的两个方面
包括数据的,逻辑结构,和数据的,物理结构,两个方面
数据逻辑结构 是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。
数据物理结构 是数据逻辑结构在计算机中的表示和实现，故又称数据 "存储结构 "。
存储结构
存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。
有两种表示方法：
以 <x,y>的有序对为例,即 x和 y在逻辑上有先后关系
一为“顺序映象”。以,y 相对于 x 的存储位置”
表示,y 是 x的后继”,(即 x和 y在存储位置上是有先后关系的 )由此得到的数据存储结构为,顺序存储结构,。
二为“链式映象”。以和 x绑定在一起的附加信息
(指针 )表示后继关系,(即 x和 y在存储位置上是没有先后关系的 )这个指针即为 y 的存储地址，由此得到的数据存储结构为 "链式存储结构 "。
1.2.3 数据类型和抽象数据类型
数据类型 是一个“值”的集合和定义在此集合上的“一组操作”的总称。
程序中对变量或常量说明其所属类型的作用是，对它们加上两个约束条件：一是可取值的范围，二是可进行的操作。
抽象数据类型 （ Abstract Data Type 简称
ADT）是指一个数学模型以及定义在此数学模型上的一组操作。
抽象数据类型的形式描述为：
ADT = ( 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
常见的特殊约定
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
常见的特殊约定
赋值参数只为操作提供输入值；
引用参数以 &打头,除可提供输入值外，还将返回操作结果。
成组赋值 （变量名 1,...，变量名 n） =（表达式 1,,..，
表达式 n）；
结构赋值 结构名 1 = 结构名 2；
结构名 =（值 1，值 2,...，值 n）；
条件赋值 变量名 = 条件表达式? 表达式 1：表达式 2；
交换赋值 变量名 1? 变量名 2；
1.3.1 算法及其设计原则
算法 是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、
有限长的操作序列。
算法必须满足五个重要特性
(1) 有穷性 对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。即算法中的操作步骤 为有限个，且每个步骤都能在有限 时间 内完成。
(2) 确定性 对于每种情况下所应执行的操作，
在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。表现在对算法中每一步的描述都 没有二义性,只要输入相同，初始状态相同，则无论执行多少遍，
所得结果都应该相同。
(3) 可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。指的是，序列中的每个操作都是可以简单完成的，其本身不存在算法问题,
(4) 有输入
(5) 有输出算法的评价标准
(1) 正确性,要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。
(2) 可读性,为了便于理解、测试和修改算法，算法应该具有良好的可读性。
(3) 健壮性,算法中拥有对输入数据、打开文件、
读取文件记录、分配内存空间等操作的结果检测，
并通过与用户对话的形式做出相应的处理选择。
(4) 时间与空间效率,算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。
1.3.3 算法效率的衡量方法
如何估算算法的时间效率？
和算法执行时间相关的因素有：
1）算法所用“策略”；
2）算法所解问题的“规模”；
3）编程所用“语言”；
4）“编译”的质量；
5）执行算法的计算机的 "速度 "。
一个算法的执行时间可以看成是所有原操作的执行时间之和
∑( 原操作 (i)的执行次数 × 原操作 (i)的执行时间 )
这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。
例,两个 n × n 的矩阵相乘。
void Mult_matrix( int c[][],int a[][],int b[][],int n)
{
// a,b 和 c 均为 n 阶方阵，且 c 是 a 和 b 的乘积
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];
}
}// Mult_matrix
算法的时间复杂度为 O (n3)
例,对 n 个整数进行选择排序。
void select_sort(int a[],int n)
{
// 将 a 中整数序列重新排列成自小至大有序的整数序列。
for ( i = 0; i< n-1; ++i )
{
j = i;
for ( k = i+1; k < n; ++k )
if (a[k] < a[j] ) j = k;
if ( j != i ) { w = a[j]; a[j] = a[i]; a[i] = w;}
}
} // select_sort
算法的时间复杂度为 O (n2) 。
例,对 n 个整数的序列进行起泡排序
void bubble_sort(int a[],int n)
{
// 将 a 中整数序列重新排列成自小至大有序的整数序列。
for (i=n-1,change=TRUE; i>1 && change; --i)
{
change = FALSE;
for (j=0; j<i; ++j)
if (a[j] > a[j+1])
{ w = a[j]; a[j]= a[j+1]; a[j+1]= w; change = TRUE }
}
} // bubble_sort
算法的时间复杂度为 O (n2) 。
1.3.4 算法的存储空间需求
算法的存储量 指的是算法执行过程中所需的最大存储空间。
包括以下三部分：
(1)输入数据所占空间；
(2)程序本身所占空间；
(3)辅助变量所占空间。
练习
设 n 为正整数。试确定下列各程序段中前置以记号 @ 的语句的频度
i=1; k=0;
while ( i<=n-1)
{
@ k += 10 * i;
i++;
}
n-1
i=1; k=0;
do {
@ k +=10 * i;
i++;
} while(i<=n-1);
n-1,但 n=1时特殊,是 1次
x=n; y=0; // n 是不小于 1的常数
while (x>=(y+1)*(y+1))
{
@ y++;
}
n
x=91; y=100;
while (y>0 ) {
@ if (x>100 ) { x -= 10; y- -; }
else x++;
}
1100
