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