第 1章概论
目录
1,数据结构概述
2,什么是 数据结构
3,算法
二十世纪四十年代，电子数字计算机问世就是解
决复杂的计算问题。早期，电子计算机的应用范围，
也只局限于科学和工程的计算，其处理的对象是纯数
值性的信息，通常，人们把这类问题称为数值计算。
随着计算机科学技术的迅猛发展, 计算机的应用已从
传统的数值计算领域发展到各种非数值计算领域 。 当
前, 计算机已广泛地应用于情报检索, 企业管理, 系
统工程等各个领域；与此相应, 计算机的处理对象也
从简单的纯数值性数据发展到一般的符号和具有一定
结构的数据 。
1.1 数据结构概述
问题, 对于每一种应用领域的处理对象，如何选择合
适的数据表示,如何有效地组织计算机存储, 并在此基
础上又如何有效地实现对象之间的“运算”关系。 传统
的解决数值计算的许多理论、方法和技术已不能满足解
决非数值计算问题的需要，必须进行新的探索。
方法, 数据结构就是研究和解决这些问题的重要基
础理论。
数据结构是一门研究非数值计算的程序设计问题中
计算机的操作对象以及它们之间的关系和操作等等的
学科。“数据结构”课程已成为计算机类专业的一门
重要专业基础课。
相关术语
1.2什么是数据结构
?数据 (Data)是信息的载体，它能够被计算机识别、存
储和加工处理。它是计算机程序加工的“原料”，而
电子计算机则是加工处理数据（信息）的工具。
??数据元素 (Data Element)是数据的基本单位。有些
情况下，数据元素也称为结点、顶点、元素、记录。
??数据项 (Data Item)数据的不可分割的具有独立含义
的最小单位，数据元素是数据项的集合 。
??数据对象 (Data Object)是具有相同性质的数据元素
的集合。
??数据结构 (Data Structure)是研究数据元素之间的相互
关系，即数据的组织形式。虽然至今还没有一个关于数
据结构的标准定义，但它一般包括以下三方面的内容：
① 数据元素之间的逻辑关系, 也称为数据的逻辑结构
(Logical Structure)。
② 数据元素及其关系在计算机存储器内的表示, 也称为
数据的存储结构 (Storage Structure)。
③ 数据的运算, 即对数据施加的操作 (operation)。
?数据的逻辑结构是指数据元素和数据元素之间的逻辑
关系，它与数据的存储无关，是从具体问题抽象出来
的数学模型。
??数据的存储结构是指逻辑结构在计算机存储器里的
实现（亦称为映象），它是依赖于计算机的，我们只
在高级语言的层次上讨论存储结构。
??数据的运算是定义在数据的逻辑结构上的，每种逻
辑结构都有一个运算的集合。例如，最常用的运算有：
检索、插入、删除、更新、排序等。这些运算实际上
是在抽象的数据上所施加的一系列抽象的操作。 。
?所谓抽象的操作，是指我们只知道这些操作是“做什
么”，而无须考虑“如何做”。只有确定了存储结构
之后，我们才考虑如何具体实现这些运算。换句话说，
算法的设计取决于数据的逻辑结构，算法的实现取决
于数据的物理存储结构。
根据数据元素
之间关系的不
同，可将数据
的逻辑结构分
为集合、线性
结构、树、图
四类
数据类型 (Data Type)是指程序设计语言中各变量可取
的数据种类。是在程序设计语言中已经实现了的数据
结构。
抽象数据类型 (Abstract Data Type)是指由用户定义，
用以表示应用问题的数据模型。抽象数据类型由基本
的数据类型构成，并包括一组相关的服务（操作） ;
抽象数据类型简写做 ADT。
算法与数据结构密切相关，因为数据
的运算是通过算法描述的，算法就是解决
问题的策略、规则与方法。所以讨论算法
是数据结构课程的重要内容之一。
1.3 算法
简单地说算法就是解决特定问题的方法。确切地说，就是
对于某一类特定的问题，算法规定了一个运算过程（一系列
操作），它必须满足下述准则：
① 输入：具有零个或多个输入的外界量, 它们是算法开始
前对算法最初给出的量 。
② 输出：至少产生一个输出, 它们是同输入有某种关系的
量 。
③ 有穷性：一个算法必须在执行有穷步之后结束, 且每一
步都可在有限时间内完成 。
④ 确定性：算法的每一操作的含义都必须明确, 无二义性 。
⑤ 可行性：算法中每一操作, 都是能够由计算机执行的 。
1.3.1 什么是算法
求解同一类问题, 可以有许多不同的算法, 那么如何来评价
这些算法的优劣呢？ 通常可从以下几个方面来衡量：
⑴ 正确性 （ 算法应该是, 正确的,, 即对任何合法的输入,
算法都能够得到正确的输出 。
⑵ 可读性 ） 算法应易于理解, 即在正确性满足的前提下,
越简单越好 。
⑶ 健壮性 （ 算法应能识别非法的输入并能做出处理, 而不
是产生误动作或者陷入瘫痪 。
⑷ 时间复杂度 （ time complexity） 执行算法所耗费的时间
的 度量, 即算法的时间性能 。
⑸ 空间复杂度 （ space complexity） 执行算法所耗费的存
储空间的度量, 主要考虑辅助存储空间 。
1.3,2 算法的评价
语句频度 （ frequency count） 是指语句被重复执行的
次数 。 即在算法中某一语句被重复执行了 n次, 则
其语句频度为 n。
算法中各语句的频度是问题规模 n的某个函数 f (n),算
法的时间量度记作：
T(n) = O (f (n) ) （ 1.1）
它表示随问题规模 n的增大，算法执行时间的增长
率和 f(n)的增长率相同，称为算法的渐近时间复杂度
(asymptotic time complexity)，简称时间复杂度。
void MatrixMult( int n,float a[max][max],
float b[max][max],float c[max][max] )
{ int i,j,k; float x;
① for(i=1; i<=n; i++) // n+1
② { for(j=1;j<=n;j++) // n(n+1)
③ { x=0; // n2
④ for(k=1;k<=n;k++) // n2(n+1)
⑤ x=x+a[i][k]*b[k][j]; // n3
} //end_for j
⑥ c[i][j]=x; // n2
} //end_for i
}
该算法中所有语句的频度之和 （ 即算法的时间耗费 ） 为：
T(n)=2n3+3n2+2n+1 （ 1.2）
由此可知, 算法 MatrixMult的时间耗费 T(n)是矩阵
阶数 n的函数 。
该算法的时间复杂度 T(n)当 n趋向无穷大时, 有：
2n 12n3n2nT ( n ) 3
23
nn
limlim ?????
????
即，当 n充分大时,T(n)和 n3之比是一个不等于零的常
数、即 T(n)和 n3是同阶的，或说 T(n)和 n3的数量级相
同，记作 T(n)=O(n3)。我们称 T(n)=O(n3)是算法
MatrixMult的 渐近时间复杂度 。
记号, O”是数学符号, 其严格的数学定义是：
当我们评价一个算法的时间性能时，主要标
准是算法时间复杂度的数量级，即算法的渐近
时间复杂度。
若 T(n)和 f (n)是定义在正整数集合上的两个
函数, 当存在两个正的常数 c和 n0,使得对所有
的 n≥n0,都有 T(n)≤cf(n)成立, 则 T(n)=O(f(n))。
设有两个算法 A1和 A2，求解同一问题，它们
的时间复杂度分别是 T1(n)=100n,T2(n)=n2。
当输入量 n<100时，有 T1(n)>T2(n)，后者花
费的时间较少。但是，随着问题规模 n的增大，
两个算法的时间开销之比 n2/100n亦随着增大。
也就是说，当问题规模较大时，算法 A1比算法 A2
要有效得多，它们的渐近时间复杂度 O(n)和
O(n2)，正是从宏观上评价了这两个算法在时间
方面的质量。
在算法分析时, 往往对算法的 时间复杂度 和 渐近时间复
杂度 不予区分, 而经常是 将渐近时间复杂度 T(n)=O(f(n))
简称为时间复杂度, 其中的 f (n)一般是算法中频度最大
的语句频度 。 例如, 我们说：算法 MatrixMult的时间复
杂度是 T(n)=O(n3),这里的 f(n)= n3是该算法中语句 ⑤ 的
频度 。
按数量级递增排列, 常见的时间复杂度有,
常数阶 O(1),对数阶 O(log2n),线性阶 O(n)，
线性对数阶 O(nlog2n ),平方阶 O(n2),立方阶 O(n3)，
…, k次方阶 O(nk),指数阶 O(2 n)。 即下面的 (1.3)
O(1) ? O(log2n) ? O(nlog2n) ? O(n2) ? O(n3) ? … ? O(nk) ?
O(2 n)
类似于算法的时间复杂度, 本书中以 空间复杂度
(space complexity)作为 算法所需存储空间的量度,
记作 S(n)= O(f(n)) （ 1.4）
其中 n为问题的规模 (或大小 )。
一个上机执行的程序除了需要存储空间来寄存本身所
用指令, 常数, 变量和输入数据外, 也需要一些对数据
进行操作的工作单元和存储一些为实现计算所需信息的
辅助空间 。 如果输入数据所占空间只取决于问题本身,
和算法无关, 则只需要分析除输入和程序之外的额外空
间；否则应同时考虑输入本身所需空间 （ 和输入数据的
表示形式有关 ） 。
设计一个算法后, 要对它进行描述, 可以用自然语言,
数字语言或约定的符号来描述, 也可以用计算机高级程
序语言来描述 。
1.3,3 算法的描述
我们用 C++语言描述数据结构及算法；对每种数据结构
先用抽象数据类型 （ ADT） 简单给出这种数据结构的定
义及基本运算, 并用类 C语言讲解一些典型的基本运算 （
操作 ）, 在每章的末尾用 C++的类声明给出该数据结构
的数据及操作 （ 接口部分 ）, 并且给出典型操作的实现
代码 （ 经过调试的算法 ） ； ADT是在概念层上描述问题；类是在实现层上描述问题；在应用层上操作对象 （ 类
的实例 ） 解决问题 。
目录
1,数据结构概述
2,什么是 数据结构
3,算法
二十世纪四十年代，电子数字计算机问世就是解
决复杂的计算问题。早期，电子计算机的应用范围，
也只局限于科学和工程的计算，其处理的对象是纯数
值性的信息，通常，人们把这类问题称为数值计算。
随着计算机科学技术的迅猛发展, 计算机的应用已从
传统的数值计算领域发展到各种非数值计算领域 。 当
前, 计算机已广泛地应用于情报检索, 企业管理, 系
统工程等各个领域；与此相应, 计算机的处理对象也
从简单的纯数值性数据发展到一般的符号和具有一定
结构的数据 。
1.1 数据结构概述
问题, 对于每一种应用领域的处理对象，如何选择合
适的数据表示,如何有效地组织计算机存储, 并在此基
础上又如何有效地实现对象之间的“运算”关系。 传统
的解决数值计算的许多理论、方法和技术已不能满足解
决非数值计算问题的需要，必须进行新的探索。
方法, 数据结构就是研究和解决这些问题的重要基
础理论。
数据结构是一门研究非数值计算的程序设计问题中
计算机的操作对象以及它们之间的关系和操作等等的
学科。“数据结构”课程已成为计算机类专业的一门
重要专业基础课。
相关术语
1.2什么是数据结构
?数据 (Data)是信息的载体，它能够被计算机识别、存
储和加工处理。它是计算机程序加工的“原料”，而
电子计算机则是加工处理数据（信息）的工具。
??数据元素 (Data Element)是数据的基本单位。有些
情况下，数据元素也称为结点、顶点、元素、记录。
??数据项 (Data Item)数据的不可分割的具有独立含义
的最小单位，数据元素是数据项的集合 。
??数据对象 (Data Object)是具有相同性质的数据元素
的集合。
??数据结构 (Data Structure)是研究数据元素之间的相互
关系，即数据的组织形式。虽然至今还没有一个关于数
据结构的标准定义，但它一般包括以下三方面的内容：
① 数据元素之间的逻辑关系, 也称为数据的逻辑结构
(Logical Structure)。
② 数据元素及其关系在计算机存储器内的表示, 也称为
数据的存储结构 (Storage Structure)。
③ 数据的运算, 即对数据施加的操作 (operation)。
?数据的逻辑结构是指数据元素和数据元素之间的逻辑
关系，它与数据的存储无关，是从具体问题抽象出来
的数学模型。
??数据的存储结构是指逻辑结构在计算机存储器里的
实现（亦称为映象），它是依赖于计算机的，我们只
在高级语言的层次上讨论存储结构。
??数据的运算是定义在数据的逻辑结构上的，每种逻
辑结构都有一个运算的集合。例如，最常用的运算有：
检索、插入、删除、更新、排序等。这些运算实际上
是在抽象的数据上所施加的一系列抽象的操作。 。
?所谓抽象的操作，是指我们只知道这些操作是“做什
么”，而无须考虑“如何做”。只有确定了存储结构
之后，我们才考虑如何具体实现这些运算。换句话说，
算法的设计取决于数据的逻辑结构，算法的实现取决
于数据的物理存储结构。
根据数据元素
之间关系的不
同，可将数据
的逻辑结构分
为集合、线性
结构、树、图
四类
数据类型 (Data Type)是指程序设计语言中各变量可取
的数据种类。是在程序设计语言中已经实现了的数据
结构。
抽象数据类型 (Abstract Data Type)是指由用户定义，
用以表示应用问题的数据模型。抽象数据类型由基本
的数据类型构成，并包括一组相关的服务（操作） ;
抽象数据类型简写做 ADT。
算法与数据结构密切相关，因为数据
的运算是通过算法描述的，算法就是解决
问题的策略、规则与方法。所以讨论算法
是数据结构课程的重要内容之一。
1.3 算法
简单地说算法就是解决特定问题的方法。确切地说，就是
对于某一类特定的问题，算法规定了一个运算过程（一系列
操作），它必须满足下述准则：
① 输入：具有零个或多个输入的外界量, 它们是算法开始
前对算法最初给出的量 。
② 输出：至少产生一个输出, 它们是同输入有某种关系的
量 。
③ 有穷性：一个算法必须在执行有穷步之后结束, 且每一
步都可在有限时间内完成 。
④ 确定性：算法的每一操作的含义都必须明确, 无二义性 。
⑤ 可行性：算法中每一操作, 都是能够由计算机执行的 。
1.3.1 什么是算法
求解同一类问题, 可以有许多不同的算法, 那么如何来评价
这些算法的优劣呢？ 通常可从以下几个方面来衡量：
⑴ 正确性 （ 算法应该是, 正确的,, 即对任何合法的输入,
算法都能够得到正确的输出 。
⑵ 可读性 ） 算法应易于理解, 即在正确性满足的前提下,
越简单越好 。
⑶ 健壮性 （ 算法应能识别非法的输入并能做出处理, 而不
是产生误动作或者陷入瘫痪 。
⑷ 时间复杂度 （ time complexity） 执行算法所耗费的时间
的 度量, 即算法的时间性能 。
⑸ 空间复杂度 （ space complexity） 执行算法所耗费的存
储空间的度量, 主要考虑辅助存储空间 。
1.3,2 算法的评价
语句频度 （ frequency count） 是指语句被重复执行的
次数 。 即在算法中某一语句被重复执行了 n次, 则
其语句频度为 n。
算法中各语句的频度是问题规模 n的某个函数 f (n),算
法的时间量度记作：
T(n) = O (f (n) ) （ 1.1）
它表示随问题规模 n的增大，算法执行时间的增长
率和 f(n)的增长率相同，称为算法的渐近时间复杂度
(asymptotic time complexity)，简称时间复杂度。
void MatrixMult( int n,float a[max][max],
float b[max][max],float c[max][max] )
{ int i,j,k; float x;
① for(i=1; i<=n; i++) // n+1
② { for(j=1;j<=n;j++) // n(n+1)
③ { x=0; // n2
④ for(k=1;k<=n;k++) // n2(n+1)
⑤ x=x+a[i][k]*b[k][j]; // n3
} //end_for j
⑥ c[i][j]=x; // n2
} //end_for i
}
该算法中所有语句的频度之和 （ 即算法的时间耗费 ） 为：
T(n)=2n3+3n2+2n+1 （ 1.2）
由此可知, 算法 MatrixMult的时间耗费 T(n)是矩阵
阶数 n的函数 。
该算法的时间复杂度 T(n)当 n趋向无穷大时, 有：
2n 12n3n2nT ( n ) 3
23
nn
limlim ?????
????
即，当 n充分大时,T(n)和 n3之比是一个不等于零的常
数、即 T(n)和 n3是同阶的，或说 T(n)和 n3的数量级相
同，记作 T(n)=O(n3)。我们称 T(n)=O(n3)是算法
MatrixMult的 渐近时间复杂度 。
记号, O”是数学符号, 其严格的数学定义是：
当我们评价一个算法的时间性能时，主要标
准是算法时间复杂度的数量级，即算法的渐近
时间复杂度。
若 T(n)和 f (n)是定义在正整数集合上的两个
函数, 当存在两个正的常数 c和 n0,使得对所有
的 n≥n0,都有 T(n)≤cf(n)成立, 则 T(n)=O(f(n))。
设有两个算法 A1和 A2，求解同一问题，它们
的时间复杂度分别是 T1(n)=100n,T2(n)=n2。
当输入量 n<100时，有 T1(n)>T2(n)，后者花
费的时间较少。但是，随着问题规模 n的增大，
两个算法的时间开销之比 n2/100n亦随着增大。
也就是说，当问题规模较大时，算法 A1比算法 A2
要有效得多，它们的渐近时间复杂度 O(n)和
O(n2)，正是从宏观上评价了这两个算法在时间
方面的质量。
在算法分析时, 往往对算法的 时间复杂度 和 渐近时间复
杂度 不予区分, 而经常是 将渐近时间复杂度 T(n)=O(f(n))
简称为时间复杂度, 其中的 f (n)一般是算法中频度最大
的语句频度 。 例如, 我们说：算法 MatrixMult的时间复
杂度是 T(n)=O(n3),这里的 f(n)= n3是该算法中语句 ⑤ 的
频度 。
按数量级递增排列, 常见的时间复杂度有,
常数阶 O(1),对数阶 O(log2n),线性阶 O(n)，
线性对数阶 O(nlog2n ),平方阶 O(n2),立方阶 O(n3)，
…, k次方阶 O(nk),指数阶 O(2 n)。 即下面的 (1.3)
O(1) ? O(log2n) ? O(nlog2n) ? O(n2) ? O(n3) ? … ? O(nk) ?
O(2 n)
类似于算法的时间复杂度, 本书中以 空间复杂度
(space complexity)作为 算法所需存储空间的量度,
记作 S(n)= O(f(n)) （ 1.4）
其中 n为问题的规模 (或大小 )。
一个上机执行的程序除了需要存储空间来寄存本身所
用指令, 常数, 变量和输入数据外, 也需要一些对数据
进行操作的工作单元和存储一些为实现计算所需信息的
辅助空间 。 如果输入数据所占空间只取决于问题本身,
和算法无关, 则只需要分析除输入和程序之外的额外空
间；否则应同时考虑输入本身所需空间 （ 和输入数据的
表示形式有关 ） 。
设计一个算法后, 要对它进行描述, 可以用自然语言,
数字语言或约定的符号来描述, 也可以用计算机高级程
序语言来描述 。
1.3,3 算法的描述
我们用 C++语言描述数据结构及算法；对每种数据结构
先用抽象数据类型 （ ADT） 简单给出这种数据结构的定
义及基本运算, 并用类 C语言讲解一些典型的基本运算 （
操作 ）, 在每章的末尾用 C++的类声明给出该数据结构
的数据及操作 （ 接口部分 ）, 并且给出典型操作的实现
代码 （ 经过调试的算法 ） ； ADT是在概念层上描述问题；类是在实现层上描述问题；在应用层上操作对象 （ 类
的实例 ） 解决问题 。
