内容提要
? 1.1 数据结构研究的内容
? 对所加工的数据对象进行逻辑组织
? 将数据对象存储在计算机中
? 数据运算或处理
? 1.2 基本概念和术语
? 数据、数据元素、数据结构、逻辑结构
? 1.3 抽象数据类型
? 数据类型、抽象数据类型
? 1.4 算法和算法分析
? 算法、算法设计、算法效率
1.1 数据结构研究的内容
? 计算机中的非数值运算：字符、表格、声音、图象等
(1) 对所加工的数据对象进行逻辑组织
– 数据元素及其数据项
– 数据元素之间的逻辑关系：线性或是非线性
(2) 将数据对象存储在计算机中
逻辑结构在计算机中的存储被成为“物理结构”或“存储结构”
物理结构要存储：数据元素本身和数据元素之间的关系
物理结构的设计要满足：算法的实现、时间和内存空间的节省
(3) 数据运算或处理
基于某种特定程序语言的算法
数据结构研究的内容 (cont’d)
? 用计算机解决一个具体问题的步骤：
(1) 从具体问题抽象出一个适当的数学模型
– 寻求数学模型的实质是分析问题
(2) 设计一个解此数学模型的算法
– 从中提取操作的对象，并找出这些操作对象之间含有的关系
，用数学语言加以描述
(3) 编出程序、进行测试、调整直至得到最终解答
数据结构研究的内容 (cont’d)
? Example,
1-1 图书馆的书目检索系统自动化问题
– 由四张表构成的文件为本系统的数学模型（见书 P2）
– 文档管理的数学模型 — 线性数据结构
1-2 计算机和人对奕问题
– 格局（对奕过程中可能出现的棋盘状态）
– 格局之间的关系由比赛规则决定 — 非线性（树型）数据结构
1-3 多叉路口交通灯的管理问题
– 非线性（图）数据结构
数据结构研究的内容 (cont’d)
? Example 1-1：图书目录文件示例
001 高等数学 樊映川 S01 …
002 理论力学 罗远祥 L01 …
003 高等数学 华罗庚 S01 …
004 线性代数 栾汝书 S02 …
… … … … …
高等数学 001,003,…
理论力学 002,…
线性代数 004,…
… …
樊映川 001,…
华罗庚 003,…
栾汝书 004,…
… …
L 002,…
S 001,003,…
… …
数据结构研究的内容 (cont’d)
? Example 1-2：井字棋对奕,树,
o
x
x o
(a)
o
x
x o
o
x x
x o
x o
x
x o
x o
x
x o
o
x
x o x
(b)
(a) 棋盘格局示例； (b) 对奕树的局部
o
x x
x o
数据结构研究的内容 (cont’d)
? Example 1-3：五叉路口交通管理示意图
(a) 五叉路口
C
B
A
D
E
在路口有 13条可行的通路，
如,A?B和 E ? C
不能同时通行，如,E ? B
和 A ? D
1.2 基本概念和术语
数据 (Data)：对客观事物的符号表示
数据元素 (data element)：是作为整体考虑和处理的 数据
的基本单位
数据项 (Data Item)：组成数据元素，是数据不可分割的
最小单位
(主 )关键字,能唯一标识数据元素的数据项
次关键字：不能唯一标识数据元素的数据项
数据对象 (data object),性质相同的数据元素的有限集
数据结构 (Data Structure)：数据元素之间所具有的特定
关系的有限集
逻辑结构,数据元素之间的逻辑关系
存储结构,数据结构在计算机中的表示
基本概念和术语 (cont’d)
? 1、数据结构的形式化定义,
Data-Structure=( D,R ) 二元组
数据元素的有限集 D上关系的有限集 (逻辑结构 )
? 2、四种逻辑结构,
(1) 集合
(2) 线性结构,元素之间是一一对应的关系，首元素无前趋，尾
元素无后继，其他元素都只有一个前驱和后继
【 例 】 Linear=(D,R)
D={1,2,3,4,5}
R={<1,2>,<2,3>,<3,4>,<4,5>}
序偶
1 2 3 54
基本概念和术语 (cont’d)
? 四种逻辑结构,
(3) 树型结构,元素之间存在一对多的关系，其中只有一个元素没有前
驱，称为根。其他元素只有一个前驱，但可以有多个后继。
【 例 】 Tree=(D,R)
D={a,b,c,d,e,f}
R={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>}
a
b c d
e f
基本概念和术语 (cont’d)
? 四种逻辑结构,
(4)图型结构, 元素之间存在多对多的关系，任何元素之间都可以
存在关系
【 例 】 Graph=(D,R)
D={1,2,3,4}
R={<1,2>,<1,3>,<2,4>,<3,4>,<3,2>}
3
1
2
4
基本概念和术语 (cont’d)
? 3、两种基本的存储结构,
(1) 顺序存储结构,利用元素在内存中相对位置来表示元素之
间的关系
(2) 链式存储结构,利用“指针”来单独存储数据元素之间的
关系。
这个“指针”不一定就是 指针型 数据，可能是个 整型 数据。
1.3 数据类型和抽象数据类型
? 数据类型,是一个值的集合及定义于其上的一组操作的
总称。也称为“抽象数据类型”。
? 抽象数据类型的形式定义,
ADT=( D,S,P ) 三元组
数据对象 D上的关系 对 D的基本操作
软件系统的框架应该建立在数据
之上，而不是操作（功能）之上
抽象是强调数据类型的数学
特性，而与它们在不同计算
机中的实现方法和细节无关。
使用抽象数据类型定义程序
模块，将提高模块的复用率
数据类型和抽象数据类型 (cont’d)
抽象数据类型的格式定义：
ADT抽象数据类型名 {
数据对象, <数据对象的定义 >
数据关系, <数据关系的定义 >
基本操作, <基本操作的定义 >
} ADT抽象数据类型名
P的基本格式,
基本操作名 (参数表 )
初始条件,<初始条件描述 >
操作结果,<操作结果描述 >
1.4 算法和算法分析
? 算法 （ Algorithm）：是对特定问题的求解步骤的描
述，是指令的有限集合。
? 算法的特性,
? 输入, 零个输入和多个输入
? 输出,一个或多个输出
? 有穷性, 不会死循环
? 可行性,新的操作必须是基本操作的有限组合
? 确定性,相同输入必须有相同的执行结果
算法和算法分析 (cont’d)
? 算法设计的要求,
? 正确性 (Correctness),必须利用边界数据进行算法测试
? 可读性 (Readability),必须为算法增加丰富的注释信息
? 健壮性 (Robustness),必须利用非法数据对算法进行测
试
? 高效性,时间复杂度和空间复杂度都尽量的低。时间
复杂度是对算法速度的衡量；空间复杂度是对算法占
用内存量的衡量。
时间复杂度和空间复杂度是
一对矛盾，可以相互转化
算法和算法分析 (cont’d)
? 算法效率的度量,算法执行时间需要通过依据该算
法编制的程序在计算机上运行时所消耗的时间来度
量。度量一个程序的执行时间通常有两种方法：
? 事后统计法, 存在两个缺陷
? 事前分析估算的方法,常用方法
? 算法的时间复杂度,
一个算法由 控制结构 （顺序、分支和循环三种）
和 原操作 （指固有数据类型的操作）构成，我们用
对所研究的问题来说是基本操作的原操作的重复执
行次数作为算法时间复杂度的量度。
原操作指对固有数据类型的操作
算法和算法分析 (cont’d)
【 例 】 void selector(int r[],int n)
{ int temp;int i,j,k
for(i=0;i<n-1;i++)
{ k=i;
for(j=i+1;j<n;j++)
if(r[j]<r[k]) k=j;
if(i!=k)
{ temp=r[i];
r[i]=r[k];
r[k]=temp;
}
}
}
最基本操作是比较操作，外
循环执行 n-1次，内循环平均执
行 (1+2+…+n -1)/(n-1)=n/2次，
总的比较次数是 T(n)=(n-1)*n/2，
它是 问题规模 n的函数。
在数据结构中，常常将复杂
度记做 O(f(n))。当 n>=n0时，
T(n)<=cf(n)，及 T(n)是 f(n)的常
数倍。也就是说，当 n足够大时，
T(n) 和 f(n)具有相同的增长率。
因此，在数据结构中，常常用
O(f(n))表示复杂度。左例的时
间复杂度可以记做 O(n2-n)，实
际上就是 O(n2)
算法和算法分析 (cont’d)
? 算法的空间复杂度：
记做 S(n)=O(f(n)), n为问题规模
f(n)不是指算法中指令、常数、变量和输入数
据所占内存的量，而是指为了对数据进行操作
而设置的工作单元的内存量。
Readings
? 第一章 绪论
? 第二章 数组
? 1.1 数据结构研究的内容
? 对所加工的数据对象进行逻辑组织
? 将数据对象存储在计算机中
? 数据运算或处理
? 1.2 基本概念和术语
? 数据、数据元素、数据结构、逻辑结构
? 1.3 抽象数据类型
? 数据类型、抽象数据类型
? 1.4 算法和算法分析
? 算法、算法设计、算法效率
1.1 数据结构研究的内容
? 计算机中的非数值运算：字符、表格、声音、图象等
(1) 对所加工的数据对象进行逻辑组织
– 数据元素及其数据项
– 数据元素之间的逻辑关系：线性或是非线性
(2) 将数据对象存储在计算机中
逻辑结构在计算机中的存储被成为“物理结构”或“存储结构”
物理结构要存储：数据元素本身和数据元素之间的关系
物理结构的设计要满足：算法的实现、时间和内存空间的节省
(3) 数据运算或处理
基于某种特定程序语言的算法
数据结构研究的内容 (cont’d)
? 用计算机解决一个具体问题的步骤：
(1) 从具体问题抽象出一个适当的数学模型
– 寻求数学模型的实质是分析问题
(2) 设计一个解此数学模型的算法
– 从中提取操作的对象，并找出这些操作对象之间含有的关系
，用数学语言加以描述
(3) 编出程序、进行测试、调整直至得到最终解答
数据结构研究的内容 (cont’d)
? Example,
1-1 图书馆的书目检索系统自动化问题
– 由四张表构成的文件为本系统的数学模型（见书 P2）
– 文档管理的数学模型 — 线性数据结构
1-2 计算机和人对奕问题
– 格局（对奕过程中可能出现的棋盘状态）
– 格局之间的关系由比赛规则决定 — 非线性（树型）数据结构
1-3 多叉路口交通灯的管理问题
– 非线性（图）数据结构
数据结构研究的内容 (cont’d)
? Example 1-1：图书目录文件示例
001 高等数学 樊映川 S01 …
002 理论力学 罗远祥 L01 …
003 高等数学 华罗庚 S01 …
004 线性代数 栾汝书 S02 …
… … … … …
高等数学 001,003,…
理论力学 002,…
线性代数 004,…
… …
樊映川 001,…
华罗庚 003,…
栾汝书 004,…
… …
L 002,…
S 001,003,…
… …
数据结构研究的内容 (cont’d)
? Example 1-2：井字棋对奕,树,
o
x
x o
(a)
o
x
x o
o
x x
x o
x o
x
x o
x o
x
x o
o
x
x o x
(b)
(a) 棋盘格局示例； (b) 对奕树的局部
o
x x
x o
数据结构研究的内容 (cont’d)
? Example 1-3：五叉路口交通管理示意图
(a) 五叉路口
C
B
A
D
E
在路口有 13条可行的通路，
如,A?B和 E ? C
不能同时通行，如,E ? B
和 A ? D
1.2 基本概念和术语
数据 (Data)：对客观事物的符号表示
数据元素 (data element)：是作为整体考虑和处理的 数据
的基本单位
数据项 (Data Item)：组成数据元素，是数据不可分割的
最小单位
(主 )关键字,能唯一标识数据元素的数据项
次关键字：不能唯一标识数据元素的数据项
数据对象 (data object),性质相同的数据元素的有限集
数据结构 (Data Structure)：数据元素之间所具有的特定
关系的有限集
逻辑结构,数据元素之间的逻辑关系
存储结构,数据结构在计算机中的表示
基本概念和术语 (cont’d)
? 1、数据结构的形式化定义,
Data-Structure=( D,R ) 二元组
数据元素的有限集 D上关系的有限集 (逻辑结构 )
? 2、四种逻辑结构,
(1) 集合
(2) 线性结构,元素之间是一一对应的关系，首元素无前趋，尾
元素无后继，其他元素都只有一个前驱和后继
【 例 】 Linear=(D,R)
D={1,2,3,4,5}
R={<1,2>,<2,3>,<3,4>,<4,5>}
序偶
1 2 3 54
基本概念和术语 (cont’d)
? 四种逻辑结构,
(3) 树型结构,元素之间存在一对多的关系，其中只有一个元素没有前
驱，称为根。其他元素只有一个前驱，但可以有多个后继。
【 例 】 Tree=(D,R)
D={a,b,c,d,e,f}
R={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>}
a
b c d
e f
基本概念和术语 (cont’d)
? 四种逻辑结构,
(4)图型结构, 元素之间存在多对多的关系，任何元素之间都可以
存在关系
【 例 】 Graph=(D,R)
D={1,2,3,4}
R={<1,2>,<1,3>,<2,4>,<3,4>,<3,2>}
3
1
2
4
基本概念和术语 (cont’d)
? 3、两种基本的存储结构,
(1) 顺序存储结构,利用元素在内存中相对位置来表示元素之
间的关系
(2) 链式存储结构,利用“指针”来单独存储数据元素之间的
关系。
这个“指针”不一定就是 指针型 数据，可能是个 整型 数据。
1.3 数据类型和抽象数据类型
? 数据类型,是一个值的集合及定义于其上的一组操作的
总称。也称为“抽象数据类型”。
? 抽象数据类型的形式定义,
ADT=( D,S,P ) 三元组
数据对象 D上的关系 对 D的基本操作
软件系统的框架应该建立在数据
之上，而不是操作（功能）之上
抽象是强调数据类型的数学
特性，而与它们在不同计算
机中的实现方法和细节无关。
使用抽象数据类型定义程序
模块，将提高模块的复用率
数据类型和抽象数据类型 (cont’d)
抽象数据类型的格式定义：
ADT抽象数据类型名 {
数据对象, <数据对象的定义 >
数据关系, <数据关系的定义 >
基本操作, <基本操作的定义 >
} ADT抽象数据类型名
P的基本格式,
基本操作名 (参数表 )
初始条件,<初始条件描述 >
操作结果,<操作结果描述 >
1.4 算法和算法分析
? 算法 （ Algorithm）：是对特定问题的求解步骤的描
述，是指令的有限集合。
? 算法的特性,
? 输入, 零个输入和多个输入
? 输出,一个或多个输出
? 有穷性, 不会死循环
? 可行性,新的操作必须是基本操作的有限组合
? 确定性,相同输入必须有相同的执行结果
算法和算法分析 (cont’d)
? 算法设计的要求,
? 正确性 (Correctness),必须利用边界数据进行算法测试
? 可读性 (Readability),必须为算法增加丰富的注释信息
? 健壮性 (Robustness),必须利用非法数据对算法进行测
试
? 高效性,时间复杂度和空间复杂度都尽量的低。时间
复杂度是对算法速度的衡量；空间复杂度是对算法占
用内存量的衡量。
时间复杂度和空间复杂度是
一对矛盾，可以相互转化
算法和算法分析 (cont’d)
? 算法效率的度量,算法执行时间需要通过依据该算
法编制的程序在计算机上运行时所消耗的时间来度
量。度量一个程序的执行时间通常有两种方法：
? 事后统计法, 存在两个缺陷
? 事前分析估算的方法,常用方法
? 算法的时间复杂度,
一个算法由 控制结构 （顺序、分支和循环三种）
和 原操作 （指固有数据类型的操作）构成，我们用
对所研究的问题来说是基本操作的原操作的重复执
行次数作为算法时间复杂度的量度。
原操作指对固有数据类型的操作
算法和算法分析 (cont’d)
【 例 】 void selector(int r[],int n)
{ int temp;int i,j,k
for(i=0;i<n-1;i++)
{ k=i;
for(j=i+1;j<n;j++)
if(r[j]<r[k]) k=j;
if(i!=k)
{ temp=r[i];
r[i]=r[k];
r[k]=temp;
}
}
}
最基本操作是比较操作，外
循环执行 n-1次，内循环平均执
行 (1+2+…+n -1)/(n-1)=n/2次，
总的比较次数是 T(n)=(n-1)*n/2，
它是 问题规模 n的函数。
在数据结构中，常常将复杂
度记做 O(f(n))。当 n>=n0时，
T(n)<=cf(n)，及 T(n)是 f(n)的常
数倍。也就是说，当 n足够大时，
T(n) 和 f(n)具有相同的增长率。
因此，在数据结构中，常常用
O(f(n))表示复杂度。左例的时
间复杂度可以记做 O(n2-n)，实
际上就是 O(n2)
算法和算法分析 (cont’d)
? 算法的空间复杂度：
记做 S(n)=O(f(n)), n为问题规模
f(n)不是指算法中指令、常数、变量和输入数
据所占内存的量，而是指为了对数据进行操作
而设置的工作单元的内存量。
Readings
? 第一章 绪论
? 第二章 数组
