【大学数据结构课件】（绪论）

《【大学数据结构课件】（绪论）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、数据结构研究的内容计算机中的非数值运算：字符、表格、声音、图象等(1)对所加工的数据对象进行逻辑组织数据元素及其数据项数据元素之间的逻辑关系：线性或是非线性(2)将数据对象存储在计算机中逻辑结构在计算机中的存储被成为“物理结构”或“存储结构”物理结构要存储：数据元素本身和数据元素之间的关系物理结构的设计要满足：算法的实现、时间和内存空间的节省(3)数据运算或处理基于某种特定程序语言的算法2、基本概念和术语数据：对客观事物的符号表示数据元素：是作为整体考虑和处理的数据的基本单位(dataele

2、ment)数据项：组成数据元素(主)关键字：能唯一标识数据元素的数据项次关键字：不能唯一标识数据元素的数据项数据对象：性质相同的数据元素的有限集(dataobject)数据结构：数据元素之间所具有的特定关系的有限集逻辑结构、存储结构2、基本概念和术语数据结构的形式化定义：Data-Structure=(D,R)二元组数据元素的有限集D上关系的有限集(逻辑结构)四种逻辑结构：(1)集合(2)线性结构：元素之间是一一对应的关系，首元素无前趋，尾元素无后继，其他元素都只有一个前驱和后继【例】Linea

3、r=(D,R)D={1,2,3,4,5}R={<1,2>,<2,3>,<3,4>,<4,5>}序偶123542、基本概念和术语四种逻辑结构(续)：(3)树型结构：元素之间存在一对多的关系，其中只有一个元素没有前驱，称为根。其他元素只有一个前驱，但可以有多个后继。【例】Tree=(D,R)D={a,b,c,d,e,f}R={,,,,}abcdef2、基本概念和术语四种逻辑结构(续)：(4)图型结构：元素之间存在多对多的关系，任何元素之间都可以存在关

4、系【例】Graph=(D,R)D={1,2,3,4}R={<1,2>,<1,3>,<2,4>,<3,4>,<3,2>}31242、基本概念和术语两种基本的存储结构：(1)顺序存储结构：利用元素在内存中相对位置来表示元素之间的关系(2)链式存储结构：利用“指针”来单独存储数据元素之间的关系。这个“指针”不一定就是指针型数据，可能是个整型数据。3、数据类型和抽象数据类型数据类型：是一个值的集合及定义于其上的一组操作的总称。也称为“抽象数据类型”。抽象数据类型的形式定义：ADT=(D,S,P)三元组数

5、据对象D上的关系对D的基本操作P的基本格式：基本操作名(参数表)初始条件：<初始条件描述>操作结果：<操作结果描述>软件系统的框架应该建立在数据之上，而不是操作（功能）之上抽象是强调数据类型的数学特性，而与它们在不同计算机中的实现方法和细节无关。使用抽象数据类型定义程序模块，将提高模块的复用率4、算法和算法分析算法：是对特定问题的求解步骤的描述，是指令的有限集合。算法的特性：零个输入和多个输入一个或多个输出有穷性，不会死循环可行性，新的操作必须是基本操作的有限组合确定性，相同输入必须有相同的执行

6、结果4、算法和算法分析算法设计的要求：正确性，必须利用边界数据进行算法测试可读性，必须为算法增加丰富的注释信息健壮性(Robustness)，必须利用非法数据对算法进行测试高效性，时间复杂度和空间复杂度都尽量的低。时间复杂度是对算法速度的衡量；空间复杂度是对算法占用内存量的衡量。时间复杂度和空间复杂度是一对矛盾，可以相互转化4、算法和算法分析算法的时间复杂度：一个算法由控制结构和原操作构成，我们用对所研究的问题来说是基本操作的原操作的重复执行次数作为算法时间复杂度的量度。【例】voidselec

7、tor(intr[],intn){inttemp;inti,j,kfor(i=0;i

8、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)不是指算法中指令、常数、变量和输入数据所占内存的量，而是指为了对数据进行操作而设置的工作单元的内存量。