【大学数据结构课件】绪论_1.pptVIP

一、数据结构研究的内容 计算机中的非数值运算：字符、表格、声音、图象等 (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} 2、基本概念和术语 四种逻辑结构(续)： (3)树型结构：元素之间存在一对多的关系，其中只有一个元素没有前驱，称为根。其他元素只有一个前驱，但可以有多个后继。 【例】Tree=(D,R) D={a,b,c,d,e,f} R={a,b,a,c,a,d,c,e,c,f} 2、基本概念和术语 四种逻辑结构(续)： (4)图型结构：元素之间存在多对多的关系，任何元素之间都可以存在关系 【例】Graph=(D,R) D={1,2,3,4} R={1,2,1,3,2,4,3,4,3,2} 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;in-1;i++) { k=i; for(j=i+1;jn;j++) if(r[j]r[k]) k=j; if(i!=k){temp=r[i];r[i]=r[k];r[k]=temp;} } } 4、算法和算法分析 算法的空间复杂度： 记做 S(n)=O(f(n)) ，n为问题规模 f(n)不是指算法中指令、常数、变量和输入数据所占内存的量，而是指为了对数据进行操作而设置的工作单元的内存量。 * 序偶 1 2 3 5 4 a b c d e f 3 1 2 4 这个“指针”不一定就是指针型数据，可能是个整型数据。 软件系统的框架应该建立在数据之上，而不是操作（功能）之上 抽象是强调数据类型的数学特性，而与它们