一、数据结构研究的内容
计算机中的非数值运算：字符、表格、声音、图象等
(1)对所加工的数据对象进行逻辑组织
? 数据元素及其数据项
? 数据元素之间的逻辑关系：线性或是非线性
(2)将数据对象存储在计算机中
逻辑结构在计算机中的存储被成为“物理结构”或“存储结构”
物理结构要存储：数据元素本身和数据元素之间的关系
物理结构的设计要满足：算法的实现、时间和内存空间的节省
(3)数据运算或处理
基于某种特定程序语言的算法
2、基本概念和术语
? 数据：对客观事物的符号表示
? 数据元素：是作为整体考虑和处理的数据的基本单位
(data element)
? 数据项：组成数据元素
? (主 )关键字：能唯一标识数据元素的数据项
? 次关键字：不能唯一标识数据元素的数据项
? 数据对象：性质相同的数据元素的有限集
(data object)
? 数据结构：数据元素之间所具有的特定关系的有限集
? 逻辑结构、存储结构
2、基本概念和术语
? 数据结构的形式化定义,
Data-Structure=(D,R) 二元组
数据元素的有限集 D上关系的有限集 (逻辑结构 )
? 四种逻辑结构,
(1)集合
(2)线性结构,元素之间是一一对应的关系，首元素无前趋，尾
元素无后继，其他元素都只有一个前驱和后继
【 例 】 Linear=(D,R)
D={1,2,3,4,5}
R={<1,2>,<2,3>,<3,4>,<4,5>}
序偶
1 2 3 54
2、基本概念和术语
? 四种逻辑结构 (续 )：
(3)树型结构,元素之间存在一对多的关系，其中只有一个元素
没有前驱，称为根。其他元素只有一个前驱，但可以有多个
后继。
【 例 】 Tree=(D,R)
D={a,b,c,d,e,f}
R={<a,b>,<a,c>,<a,d>,<c,e>,<c,f>}
a
b c d
e f
2、基本概念和术语
? 四种逻辑结构 (续 )：
(4)图型结构,元素之间存在多对多的关系，任何元素之间都可
以存在关系
【 例 】 Graph=(D,R)
D={1,2,3,4}
R={<1,2>,<1,3>,<2,4>,<3,4>,<3,2>}
3
1
2
4
2、基本概念和术语
? 两种基本的存储结构,
(1)顺序存储结构,利用元素在内存中相对位置来表示元素之间
的关系
(2)链式存储结构,利用“指针”来单独存储数据元素之间的关
系。
这个“指针”不一定就是 指针型 数据，可能是个 整型 数据。
3、数据类型和抽象数据类型
? 数据类型,是一个值的集合及定义于其上的一组操作的
总称。也称为“抽象数据类型”。
? 抽象数据类型的形式定义,
ADT=( D,S,P ) 三元组
数据对象 D上的关系 对 D的基本操作
P的基本格式,
基本操作名 (参数表 )
初始条件,<初始条件描述 >
操作结果,<操作结果描述 >
软件系统的框架应该建立在数据
之上，而不是操作（功能）之上
抽象是强调数据类型的数学
特性，而与它们在不同计算
机中的实现方法和细节无关。
使用抽象数据类型定义程序
模块，将提高模块的复用率
4、算法和算法分析
? 算法：是对特定问题的求解步骤的描述，是指令的有
限集合。
? 算法的特性：
– 零个输入和多个输入
– 一个或多个输出
– 有穷性，不会死循环
– 可行性，新的操作必须是基本操作的有限组合
– 确定性，相同输入必须有相同的执行结果
4、算法和算法分析
? 算法设计的要求：
– 正确性，必须利用边界数据进行算法测试
– 可读性，必须为算法增加丰富的注释信息
– 健壮性 (Robustness)，必须利用非法数据对算法进行测试
– 高效性，时间复杂度和空间复杂度都尽量的低。时间复杂度
是对算法速度的衡量；空间复杂度是对算法占用内存量的衡
量。
时间复杂度和空间复杂度是
一对矛盾，可以相互转化
4、算法和算法分析
? 算法的时间复杂度：
一个算法由控制结构和原操作构成，我们用对所研究的问
题来说是基本操作的原操作的重复执行次数作为算法时间复杂
度的量度。
【 例 】
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)
4、算法和算法分析
? 算法的空间复杂度：
记做 S(n)=O(f(n)), n为问题规模
f(n)不是指算法中指令、常数、变量和输入数据所占内存的量，
而是指为了对数据进行操作而设置的工作单元的内存量。
计算机中的非数值运算：字符、表格、声音、图象等
(1)对所加工的数据对象进行逻辑组织
? 数据元素及其数据项
? 数据元素之间的逻辑关系：线性或是非线性
(2)将数据对象存储在计算机中
逻辑结构在计算机中的存储被成为“物理结构”或“存储结构”
物理结构要存储：数据元素本身和数据元素之间的关系
物理结构的设计要满足：算法的实现、时间和内存空间的节省
(3)数据运算或处理
基于某种特定程序语言的算法
2、基本概念和术语
? 数据：对客观事物的符号表示
? 数据元素：是作为整体考虑和处理的数据的基本单位
(data element)
? 数据项：组成数据元素
? (主 )关键字：能唯一标识数据元素的数据项
? 次关键字：不能唯一标识数据元素的数据项
? 数据对象：性质相同的数据元素的有限集
(data object)
? 数据结构：数据元素之间所具有的特定关系的有限集
? 逻辑结构、存储结构
2、基本概念和术语
? 数据结构的形式化定义,
Data-Structure=(D,R) 二元组
数据元素的有限集 D上关系的有限集 (逻辑结构 )
? 四种逻辑结构,
(1)集合
(2)线性结构,元素之间是一一对应的关系，首元素无前趋，尾
元素无后继，其他元素都只有一个前驱和后继
【 例 】 Linear=(D,R)
D={1,2,3,4,5}
R={<1,2>,<2,3>,<3,4>,<4,5>}
序偶
1 2 3 54
2、基本概念和术语
? 四种逻辑结构 (续 )：
(3)树型结构,元素之间存在一对多的关系，其中只有一个元素
没有前驱，称为根。其他元素只有一个前驱，但可以有多个
后继。
【 例 】 Tree=(D,R)
D={a,b,c,d,e,f}
R={<a,b>,<a,c>,<a,d>,<c,e>,<c,f>}
a
b c d
e f
2、基本概念和术语
? 四种逻辑结构 (续 )：
(4)图型结构,元素之间存在多对多的关系，任何元素之间都可
以存在关系
【 例 】 Graph=(D,R)
D={1,2,3,4}
R={<1,2>,<1,3>,<2,4>,<3,4>,<3,2>}
3
1
2
4
2、基本概念和术语
? 两种基本的存储结构,
(1)顺序存储结构,利用元素在内存中相对位置来表示元素之间
的关系
(2)链式存储结构,利用“指针”来单独存储数据元素之间的关
系。
这个“指针”不一定就是 指针型 数据，可能是个 整型 数据。
3、数据类型和抽象数据类型
? 数据类型,是一个值的集合及定义于其上的一组操作的
总称。也称为“抽象数据类型”。
? 抽象数据类型的形式定义,
ADT=( D,S,P ) 三元组
数据对象 D上的关系 对 D的基本操作
P的基本格式,
基本操作名 (参数表 )
初始条件,<初始条件描述 >
操作结果,<操作结果描述 >
软件系统的框架应该建立在数据
之上，而不是操作（功能）之上
抽象是强调数据类型的数学
特性，而与它们在不同计算
机中的实现方法和细节无关。
使用抽象数据类型定义程序
模块，将提高模块的复用率
4、算法和算法分析
? 算法：是对特定问题的求解步骤的描述，是指令的有
限集合。
? 算法的特性：
– 零个输入和多个输入
– 一个或多个输出
– 有穷性，不会死循环
– 可行性，新的操作必须是基本操作的有限组合
– 确定性，相同输入必须有相同的执行结果
4、算法和算法分析
? 算法设计的要求：
– 正确性，必须利用边界数据进行算法测试
– 可读性，必须为算法增加丰富的注释信息
– 健壮性 (Robustness)，必须利用非法数据对算法进行测试
– 高效性，时间复杂度和空间复杂度都尽量的低。时间复杂度
是对算法速度的衡量；空间复杂度是对算法占用内存量的衡
量。
时间复杂度和空间复杂度是
一对矛盾，可以相互转化
4、算法和算法分析
? 算法的时间复杂度：
一个算法由控制结构和原操作构成，我们用对所研究的问
题来说是基本操作的原操作的重复执行次数作为算法时间复杂
度的量度。
【 例 】
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)
4、算法和算法分析
? 算法的空间复杂度：
记做 S(n)=O(f(n)), n为问题规模
f(n)不是指算法中指令、常数、变量和输入数据所占内存的量，
而是指为了对数据进行操作而设置的工作单元的内存量。
