,数据结构,
第一章
数据结构
tjm
第一章 绪 论
1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现
1.4 算法和算法分析
1.4.1 算法
1.4.2 算法设计的要求
1.4.3 算法效率的度量
1.4.4 算法的存储空间的需求
数据结构
tjm
1.1 什么是数据结构
“数据结构”作为一门计算机专业基础课，是编译
原理，操作系统，数据库等课程的基础。也是设
计及实现系统程序和大型应用程序的重要基础。
“数据结构”的主要内容是研究数据的逻辑结构，
存储结构及对每种结构所定义的运算。
程序设计的实质是数据表示和数据处理
1)数据表示 --把原始数据从机外表示转化为机内
表示。
2)数据处理 --编写程序，对机内的数据进行各种
操作,获得所需结果。
数据结构
tjm
例 1、职工档案管理问题
工作证号 姓名 性别 出生日期 职称
0001 刘晓军 男 19491001 工程师
0003 张 红 女 19650506 助工
0007 李 华 女 19461118 高工
...,..,..,..,..
数据结构
tjm
每位职工的档案由五个项目构成，所有职工的档案组成一
张数据表。要管理这张表，至少可进行以下操作 (运算 )：
查找、读取、插入、删除、更新、排序等。
用计算机解决上述管理问题，设计人员要完成二项任务：
第一，将档案表转化为机内表示，让计算机直接处理；
—— 数据表示
第二，编写计算机程序实现人工管理的要求。
—— 数据处理
在大多数情况下，这些数据并不是没有组织，数据之间往
往具有重要的结构关系，这就是数据结构的内容。那么，
什么是数据结构呢？先看以下几个例子。
数据结构
tjm
例 1：学籍管理问题,某班学生基本情况表，记录了
每个学生的学号,姓名，专业，政治面貌,表中的记录
是按学生的学号顺序排列的。
学号 姓名 专业 政治面貌
001 王 丽 计算机 党员
002 孙 文 计算机 团员
003 谢小军 计算机 团员
004 李 辉 计算机 团员
005 刘 慧 计算机 党员
006 余 军 计算机 团员
007 李 力 计算机 团员
008 张爱东 计算机 团员
001 003002 004 006005 008007
在这类文档管理的数学模型中,计算机处理的对象
之间通常存在着一种最简单的线性关系,这类数学
模型称为线性的数据结构。
线性
表
数据结构
tjm
例 2,人机对奕问题
……..……..
…..,…..,…..,…...
树
数据结构
tjm
例 3,多叉路口交通灯管理问题
C
E
D
A
B
AB AC AD
BA BC BD
DA DB DC
EA EB EC ED
可见：描述这类非数值计算问题的数学模型不再是数学方程，
而是线性表、树和图之类的数据结构。简言之，数据结构是一
门研究非数值计算的程序设计问题中计算机的操作对象以及它
们之间的关系和操作等等的学科。
图
数据结构
tjm
1.2 基本概念和术语
数据 (Data):是对信息的一种符号表示。在计算机
科学中是指所有能输入到计算机中并被计算机程
序处理的符号的总称。
数据元素 (Data Element):是数据的基本单位，
在计算机程序中通常作为一个整体进行考虑和处
理。
一个数据元素可由若干个 数据项 组成。数据项是
数据的不可分割的最小单位。
数据对象 (Data Object),是性质相同的数据元
素的集合。是数据的一个子集。
数据对象 可以是有限的，也可以是无限的。
数据结构
tjm
例,整数的数据对象是 {…-3,-2,-1,0,1，
2,3,…}
英文字符类型的数据对象是 {A,B,C,D,E，
F,…}
结构（ Structure):是数据之间彼此存在的相互关系。
数据结构 (Data Structure),是相互之间存在一种或
多种特定 关系 的数据元素的集合。
这种关系体现在三个方面：
1、数据之间的逻辑关系
2、数据在计算机内的存储方式
3、数据在计算机内的运算
数据的结构主要指 逻辑结构 和 物理结构
数据结构
tjm
数据之间的相互关系称为 逻辑结构 。通常分为
四类基本结构：
一、集合 结构中的数据元素除了同属于
一种类型外，别无其它关系。
二、线性结构 结构中的数据元素之间存在一
对一的关系。
三、树型结构 结构中的数据元素之间存在一
对多的关系。
四、图状结构或网状结构 结构中的数据元素之
间存在多对多的关系。
数据结构
tjm
数据结构的形式定义：
数据结构是一个二元组：
Data-Structure=(D,S)
其中,D是数据元素的有限集,S是 D上关系的有限
集。
例,复数的数据结构定义如下：
Complex=(C,R)
其中,C是含两个实数的集合 ﹛ C1,C2﹜,分别表
示复数的实部和虚部。 R={P},P是定义在集合
上的一种关系 {〈 C1,C2〉 }。
数据结构
tjm
例,5个结点的顺序表示
D={d1,d2,d3,d4,d5}
S={<d1,d2>,<d2,d3>,<d3,d4>,<d4,d5>}
d1— d5为元素（结点）,<di,dj>表示结点 di与
dj的关系,
d2 d3 d5d1 d4
数据结构
tjm
例,5个结点的树型表示
D={d1,d2,d3,d4,d5}
S={<d1,d2>,<d1,d3>,<d1,d4>,<d3,d5>}
d1— d5为元素（结点）,<di,dj>表示结点 di与
dj的关系,
d2 d3
d5
d1
d4
数据结构
tjm
数据结构
tjm
数据结构在计算机中的表示称为数据的 物理
结构, 又称为存储结构。
数据结构在计算机中有两种不同的表示方法：
顺序表示和非顺序表示
由此得出两种不同的存储结构,顺序存储结
构和链式存储结构
顺序存储结构,用数据元素在存储器中的相对
位置来表示数据元素之间的逻辑关系 。
链式存储结构,在每一个数据元素中增加一个
存放地址的 指针,用此指针来表示数据元素
之间的逻辑关系。
数据结构
tjm
数据结构 不同于数据类型，也不同于数据对象，
它不仅要描述数据类型的数据对象，而且要
描述数据对象各元素之间的相互关系。
抽象数据类型,一个数学模型以及定义在该模
型上的一组操作。
抽象数据类型实际上就是对该数据结构
的定义。因为它定义了一个数据的逻辑结构
以及在此结构上的一组算法。
用三元组描述：（Ｄ，Ｓ，Ｐ）
数据结构
tjm
数据类型, 在一种程序设计语言中，变量所具有
的数据种类。是一个值的集合和定义在这个值
集上的一组操作的总称。
例,在 C语言中
数据类型：基本类型和构造类型
基本类型：整型、浮点型、字符型
构造类型：数组、结构、联合、枚举型、自定义
1.3 抽象数据类型的表示和实现
本书采用类 C语言（介于伪码和 C），详见 P10
数据结构
tjm
1.4 算法和算法分析
1.4.1 算法
算法,是对特定问题求解步骤的一种描述，是指令
的有限序列，其中每一条指令表示一个或多个操
作。
算法具有以下五个特性：
1）有穷性 一个算法必须总是在执行有穷步之后
结束，且每一步都在有穷时间内完成。
2）确定性 算法中每一条指令必须有确切的含义。
不存在二义性。且算法只有一个入口和一个出口。
3）可行性 一个算法是可行的。即算法描述的操作
都是可以通过已经实现的基本运算执行有限次来
实现的。
数据结构
tjm
4）输入 一个算法有零个或多个输入，这些输入取
自于某个特定的对象集合。
5）输出 一个算法有一个或多个输出，这些输出是
同输入有着某些特定关系的量。
1.4.2 算法设计的要求
1) 正确性 (Correctness ) 算法应满足具体问题
的需求。
2)可读性 (Readability) 算法应该好读。以有利
于阅读者对程序的理解。
3)健状性 (Robustness) 算法应具有容错处理。
当输入非法数据时，算法应对其作出反应，而不
是产生莫名其妙的输出结果。
数据结构
tjm
4)效率与存储量需求 效率指的是算法执行的时间；
存储量需求指算法执行过程中所需要的最大存储
空间。一般，这两者与问题的规模有关。
1.4.3 算法效率的度量
对一个算法效率的度量有两种方法，即 事前分析
和 事后统计。
事前分析 求出该算法的一个时间界限函数
事后统计 收集此算法的执行时间和实际占用空间
的统计资料。
定义,如果存在两个正常数 c和 n0，对于所有的
n≧ n0，有 ︱ f(n) ︳ ≦ c｜ g(n) ︳
则记作 f(n)=O(g(n))
数据结构
tjm
一般情况下，算法中基本操作重复执行的次数是
问题规模 n的某个函数，算法的时间量度记作
T(n)=O(f(n))
称作 算法的渐近时间复杂度（简称时间复杂度） 。
例１,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];
}
由于是一个三重循环，每个循环从 1到 n，则总次数
为, n× n× n=n3
时间复杂度为 T(n)=O(n3)
数据结构
tjm
频度,是指语句执行的次数
例２,{++x;s=0;}
将 x自增看成是基本操作，则语句频度为１，即 时间
复杂度为Ｏ (1)
如果将 s=0也看成是基本操作，则语句频度为２，其
时间复杂度仍为Ｏ (1)，即常量阶。
例３,for(i=1;i<=n;++i)
{++x;s+=x;}
语句频度为,2n，其 时间复杂度为,O(n)
即时间复杂度为线性阶。
数据结构
tjm
例４,for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{++x;s+=x;}
语句频度为,2n2
其时间复杂度为,O(n2)
即时间复杂度为平方阶。
定理,若 A(n)=a m n m +a m-1 n m-1
+…+a1n+a0是一个 m次多项式，则
A(n)=O(n m)
数据结构
tjm
例５,for(i=2;i<=n;++i)
for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
语句频度为：
(1+2+3+…+n-2) × 2
=(1+n-2) × (n-2)/2 × 2
=(n-1)(n-2)
=n2-3n+2
∴ 时间复杂度为 O(n2)
即此算法的时间复杂度为平方阶,
数据结构
tjm
以下六种计算算法时间复杂度的多项式是最常用的。
其关系为：
O(1)<O(logn)<O(n)<O(nlogn)
<O(n2)<O(n3)
指数时间的关系为：
O(2n)<O(n!)<O(nn)
当 n取得很大时，指数时间算法和多项式时间算
法在所需时间上非常悬殊。因此，只要有人能将
现有指数时间算法中的任何一个算法化简为多项
式时间算法，那就取得了一个伟大的成就。
数据结构
tjm
有的情况下，算法中基本操作重复执行的次数还随
问题的输入数据集不同而不同。例如：
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
}
}
数据结构
tjm
最好情况,0次
最坏情况,1+2+3+…+n-1
=n(n-1)/2
平均时间复杂度为,O(n2)
1.4.4 算法的存储空间需求
空间复杂度,算法所需存储空间的度量，记作,
S(n)=O(f(n))
其中 n为问题的规模,
第一章
数据结构
tjm
第一章 绪 论
1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现
1.4 算法和算法分析
1.4.1 算法
1.4.2 算法设计的要求
1.4.3 算法效率的度量
1.4.4 算法的存储空间的需求
数据结构
tjm
1.1 什么是数据结构
“数据结构”作为一门计算机专业基础课，是编译
原理，操作系统，数据库等课程的基础。也是设
计及实现系统程序和大型应用程序的重要基础。
“数据结构”的主要内容是研究数据的逻辑结构，
存储结构及对每种结构所定义的运算。
程序设计的实质是数据表示和数据处理
1)数据表示 --把原始数据从机外表示转化为机内
表示。
2)数据处理 --编写程序，对机内的数据进行各种
操作,获得所需结果。
数据结构
tjm
例 1、职工档案管理问题
工作证号 姓名 性别 出生日期 职称
0001 刘晓军 男 19491001 工程师
0003 张 红 女 19650506 助工
0007 李 华 女 19461118 高工
...,..,..,..,..
数据结构
tjm
每位职工的档案由五个项目构成，所有职工的档案组成一
张数据表。要管理这张表，至少可进行以下操作 (运算 )：
查找、读取、插入、删除、更新、排序等。
用计算机解决上述管理问题，设计人员要完成二项任务：
第一，将档案表转化为机内表示，让计算机直接处理；
—— 数据表示
第二，编写计算机程序实现人工管理的要求。
—— 数据处理
在大多数情况下，这些数据并不是没有组织，数据之间往
往具有重要的结构关系，这就是数据结构的内容。那么，
什么是数据结构呢？先看以下几个例子。
数据结构
tjm
例 1：学籍管理问题,某班学生基本情况表，记录了
每个学生的学号,姓名，专业，政治面貌,表中的记录
是按学生的学号顺序排列的。
学号 姓名 专业 政治面貌
001 王 丽 计算机 党员
002 孙 文 计算机 团员
003 谢小军 计算机 团员
004 李 辉 计算机 团员
005 刘 慧 计算机 党员
006 余 军 计算机 团员
007 李 力 计算机 团员
008 张爱东 计算机 团员
001 003002 004 006005 008007
在这类文档管理的数学模型中,计算机处理的对象
之间通常存在着一种最简单的线性关系,这类数学
模型称为线性的数据结构。
线性
表
数据结构
tjm
例 2,人机对奕问题
……..……..
…..,…..,…..,…...
树
数据结构
tjm
例 3,多叉路口交通灯管理问题
C
E
D
A
B
AB AC AD
BA BC BD
DA DB DC
EA EB EC ED
可见：描述这类非数值计算问题的数学模型不再是数学方程，
而是线性表、树和图之类的数据结构。简言之，数据结构是一
门研究非数值计算的程序设计问题中计算机的操作对象以及它
们之间的关系和操作等等的学科。
图
数据结构
tjm
1.2 基本概念和术语
数据 (Data):是对信息的一种符号表示。在计算机
科学中是指所有能输入到计算机中并被计算机程
序处理的符号的总称。
数据元素 (Data Element):是数据的基本单位，
在计算机程序中通常作为一个整体进行考虑和处
理。
一个数据元素可由若干个 数据项 组成。数据项是
数据的不可分割的最小单位。
数据对象 (Data Object),是性质相同的数据元
素的集合。是数据的一个子集。
数据对象 可以是有限的，也可以是无限的。
数据结构
tjm
例,整数的数据对象是 {…-3,-2,-1,0,1，
2,3,…}
英文字符类型的数据对象是 {A,B,C,D,E，
F,…}
结构（ Structure):是数据之间彼此存在的相互关系。
数据结构 (Data Structure),是相互之间存在一种或
多种特定 关系 的数据元素的集合。
这种关系体现在三个方面：
1、数据之间的逻辑关系
2、数据在计算机内的存储方式
3、数据在计算机内的运算
数据的结构主要指 逻辑结构 和 物理结构
数据结构
tjm
数据之间的相互关系称为 逻辑结构 。通常分为
四类基本结构：
一、集合 结构中的数据元素除了同属于
一种类型外，别无其它关系。
二、线性结构 结构中的数据元素之间存在一
对一的关系。
三、树型结构 结构中的数据元素之间存在一
对多的关系。
四、图状结构或网状结构 结构中的数据元素之
间存在多对多的关系。
数据结构
tjm
数据结构的形式定义：
数据结构是一个二元组：
Data-Structure=(D,S)
其中,D是数据元素的有限集,S是 D上关系的有限
集。
例,复数的数据结构定义如下：
Complex=(C,R)
其中,C是含两个实数的集合 ﹛ C1,C2﹜,分别表
示复数的实部和虚部。 R={P},P是定义在集合
上的一种关系 {〈 C1,C2〉 }。
数据结构
tjm
例,5个结点的顺序表示
D={d1,d2,d3,d4,d5}
S={<d1,d2>,<d2,d3>,<d3,d4>,<d4,d5>}
d1— d5为元素（结点）,<di,dj>表示结点 di与
dj的关系,
d2 d3 d5d1 d4
数据结构
tjm
例,5个结点的树型表示
D={d1,d2,d3,d4,d5}
S={<d1,d2>,<d1,d3>,<d1,d4>,<d3,d5>}
d1— d5为元素（结点）,<di,dj>表示结点 di与
dj的关系,
d2 d3
d5
d1
d4
数据结构
tjm
数据结构
tjm
数据结构在计算机中的表示称为数据的 物理
结构, 又称为存储结构。
数据结构在计算机中有两种不同的表示方法：
顺序表示和非顺序表示
由此得出两种不同的存储结构,顺序存储结
构和链式存储结构
顺序存储结构,用数据元素在存储器中的相对
位置来表示数据元素之间的逻辑关系 。
链式存储结构,在每一个数据元素中增加一个
存放地址的 指针,用此指针来表示数据元素
之间的逻辑关系。
数据结构
tjm
数据结构 不同于数据类型，也不同于数据对象，
它不仅要描述数据类型的数据对象，而且要
描述数据对象各元素之间的相互关系。
抽象数据类型,一个数学模型以及定义在该模
型上的一组操作。
抽象数据类型实际上就是对该数据结构
的定义。因为它定义了一个数据的逻辑结构
以及在此结构上的一组算法。
用三元组描述：（Ｄ，Ｓ，Ｐ）
数据结构
tjm
数据类型, 在一种程序设计语言中，变量所具有
的数据种类。是一个值的集合和定义在这个值
集上的一组操作的总称。
例,在 C语言中
数据类型：基本类型和构造类型
基本类型：整型、浮点型、字符型
构造类型：数组、结构、联合、枚举型、自定义
1.3 抽象数据类型的表示和实现
本书采用类 C语言（介于伪码和 C），详见 P10
数据结构
tjm
1.4 算法和算法分析
1.4.1 算法
算法,是对特定问题求解步骤的一种描述，是指令
的有限序列，其中每一条指令表示一个或多个操
作。
算法具有以下五个特性：
1）有穷性 一个算法必须总是在执行有穷步之后
结束，且每一步都在有穷时间内完成。
2）确定性 算法中每一条指令必须有确切的含义。
不存在二义性。且算法只有一个入口和一个出口。
3）可行性 一个算法是可行的。即算法描述的操作
都是可以通过已经实现的基本运算执行有限次来
实现的。
数据结构
tjm
4）输入 一个算法有零个或多个输入，这些输入取
自于某个特定的对象集合。
5）输出 一个算法有一个或多个输出，这些输出是
同输入有着某些特定关系的量。
1.4.2 算法设计的要求
1) 正确性 (Correctness ) 算法应满足具体问题
的需求。
2)可读性 (Readability) 算法应该好读。以有利
于阅读者对程序的理解。
3)健状性 (Robustness) 算法应具有容错处理。
当输入非法数据时，算法应对其作出反应，而不
是产生莫名其妙的输出结果。
数据结构
tjm
4)效率与存储量需求 效率指的是算法执行的时间；
存储量需求指算法执行过程中所需要的最大存储
空间。一般，这两者与问题的规模有关。
1.4.3 算法效率的度量
对一个算法效率的度量有两种方法，即 事前分析
和 事后统计。
事前分析 求出该算法的一个时间界限函数
事后统计 收集此算法的执行时间和实际占用空间
的统计资料。
定义,如果存在两个正常数 c和 n0，对于所有的
n≧ n0，有 ︱ f(n) ︳ ≦ c｜ g(n) ︳
则记作 f(n)=O(g(n))
数据结构
tjm
一般情况下，算法中基本操作重复执行的次数是
问题规模 n的某个函数，算法的时间量度记作
T(n)=O(f(n))
称作 算法的渐近时间复杂度（简称时间复杂度） 。
例１,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];
}
由于是一个三重循环，每个循环从 1到 n，则总次数
为, n× n× n=n3
时间复杂度为 T(n)=O(n3)
数据结构
tjm
频度,是指语句执行的次数
例２,{++x;s=0;}
将 x自增看成是基本操作，则语句频度为１，即 时间
复杂度为Ｏ (1)
如果将 s=0也看成是基本操作，则语句频度为２，其
时间复杂度仍为Ｏ (1)，即常量阶。
例３,for(i=1;i<=n;++i)
{++x;s+=x;}
语句频度为,2n，其 时间复杂度为,O(n)
即时间复杂度为线性阶。
数据结构
tjm
例４,for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{++x;s+=x;}
语句频度为,2n2
其时间复杂度为,O(n2)
即时间复杂度为平方阶。
定理,若 A(n)=a m n m +a m-1 n m-1
+…+a1n+a0是一个 m次多项式，则
A(n)=O(n m)
数据结构
tjm
例５,for(i=2;i<=n;++i)
for(j=2;j<=i-1;++j)
{++x;a[i,j]=x;}
语句频度为：
(1+2+3+…+n-2) × 2
=(1+n-2) × (n-2)/2 × 2
=(n-1)(n-2)
=n2-3n+2
∴ 时间复杂度为 O(n2)
即此算法的时间复杂度为平方阶,
数据结构
tjm
以下六种计算算法时间复杂度的多项式是最常用的。
其关系为：
O(1)<O(logn)<O(n)<O(nlogn)
<O(n2)<O(n3)
指数时间的关系为：
O(2n)<O(n!)<O(nn)
当 n取得很大时，指数时间算法和多项式时间算
法在所需时间上非常悬殊。因此，只要有人能将
现有指数时间算法中的任何一个算法化简为多项
式时间算法，那就取得了一个伟大的成就。
数据结构
tjm
有的情况下，算法中基本操作重复执行的次数还随
问题的输入数据集不同而不同。例如：
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
}
}
数据结构
tjm
最好情况,0次
最坏情况,1+2+3+…+n-1
=n(n-1)/2
平均时间复杂度为,O(n2)
1.4.4 算法的存储空间需求
空间复杂度,算法所需存储空间的度量，记作,
S(n)=O(f(n))
其中 n为问题的规模,
