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

1、内容提要,1.1 数据结构研究的内容 对所加工的数据对象进行逻辑组织 将数据对象存储在计算机中 数据运算或处理 1.2 基本概念和术语 数据、数据元素、数据结构、逻辑结构 1.3 抽象数据类型 数据类型、抽象数据类型 1.4 算法和算法分析 算法、算法设计、算法效率,1.1 数据结构研究的内容,计算机中的非数值运算：字符、表格、声音、图象等 (1) 对所加工的数据对象进行逻辑组织 数据元素及其数据项 数据元素之间的逻辑关系：线性或是非线性 (2) 将数据对象存储在计算机中 逻辑结构在计算机中的存储被成为“物理结构”或“存储结构” 物理结构要存储：数据元素本身和数据元素之间的关系 物理结构的设计

2、要满足：算法的实现、时间和内存空间的节省 (3) 数据运算或处理 基于某种特定程序语言的算法,数据结构研究的内容(contd),用计算机解决一个具体问题的步骤： (1) 从具体问题抽象出一个适当的数学模型 寻求数学模型的实质是分析问题 (2) 设计一个解此数学模型的算法 从中提取操作的对象，并找出这些操作对象之间含有的关系，用数学语言加以描述 (3) 编出程序、进行测试、调整直至得到最终解答,数据结构研究的内容(contd),Example ： 1-1 图书馆的书目检索系统自动化问题 由四张表构成的文件为本系统的数学模型（见书P2） 文档管理的数学模型 线性数据结构 1-2 计算机和人对奕问题

3、 格局（对奕过程中可能出现的棋盘状态） 格局之间的关系由比赛规则决定 非线性（树型）数据结构 1-3 多叉路口交通灯的管理问题 非线性（图）数据结构,数据结构研究的内容(contd),Example 1-1：图书目录文件示例,数据结构研究的内容(contd),Example 1-2：井字棋对奕 “树 ”,(a),(b),(a) 棋盘格局示例； (b) 对奕树的局部,数据结构研究的内容(contd),Example 1-3：五叉路口交通管理示意图,(a) 五叉路口,在路口有13条可行的通路，如：AB和E C 不能同时通行，如：E B和A D,1.2 基本概念和术语,数据(Data)：对客观事物的

4、符号表示 数据元素(data element)：是作为整体考虑和处理的数据的基本单位 数据项(Data Item)：组成数据元素，是数据不可分割的最小单位 (主)关键字：能唯一标识数据元素的数据项 次关键字：不能唯一标识数据元素的数据项 数据对象(data object) ：性质相同的数据元素的有限集 数据结构(Data Structure)：数据元素之间所具有的特定关系的有限集 逻辑结构：数据元素之间的逻辑关系 存储结构：数据结构在计算机中的表示,基本概念和术语(contd),1、数据结构的形式化定义： Data-Structure=( D, R ) 二元组 数据元素的有限集 D上关系的有限

5、集(逻辑结构) 2、四种逻辑结构： (1) 集合 (2) 线性结构：元素之间是一一对应的关系，首元素无前趋，尾元素无后继，其他元素都只有一个前驱和后继 【例】Linear=(D,R) D=1,2,3,4,5 R=,基本概念和术语(contd),四种逻辑结构： (3) 树型结构 ：元素之间存在一对多的关系，其中只有一个元素没有前驱，称为根。其他元素只有一个前驱，但可以有多个后继。 【例】Tree=(D,R) D=a,b,c,d,e,f R=,基本概念和术语(contd),四种逻辑结构： (4)图型结构：元素之间存在多对多的关系，任何元素之间都可以存在关系 【例】Graph=(D,R) D=1,2

6、,3,4 R=,基本概念和术语(contd),3、两种基本的存储结构： (1) 顺序存储结构：利用元素在内存中相对位置来表示元素之间的关系 (2) 链式存储结构：利用“指针”来单独存储数据元素之间的关系。,这个“指针”不一定就是指针型数据，可能是个整型数据。,1.3 数据类型和抽象数据类型,数据类型：是一个值的集合及定义于其上的一组操作的总称。也称为“抽象数据类型”。 抽象数据类型的形式定义： ADT=( D , S , P ) 三元组 数据对象 D上的关系 对D的基本操作,软件系统的框架应该建立在数据之上，而不是操作（功能）之上,抽象是强调数据类型的数学特性，而与它们在不同计算机中的实现方法

7、和细节无关。,使用抽象数据类型定义程序模块，将提高模块的复用率,数据类型和抽象数据类型(contd),抽象数据类型的格式定义： ADT抽象数据类型名 数据对象： 数据关系： 基本操作： ADT抽象数据类型名 P的基本格式： 基本操作名(参数表) 初始条件： 操作结果：,1.4 算法和算法分析,算法（Algorithm）：是对特定问题的求解步骤的描述，是指令的有限集合。 算法的特性： 输入，零个输入和多个输入 输出 ，一个或多个输出 有穷性，不会死循环 可行性，新的操作必须是基本操作的有限组合 确定性，相同输入必须有相同的执行结果,算法和算法分析(contd),算法设计的要求： 正确性(Corr

8、ectness),必须利用边界数据进行算法测试 可读性(Readability) ,必须为算法增加丰富的注释信息 健壮性(Robustness),必须利用非法数据对算法进行测试 高效性，时间复杂度和空间复杂度都尽量的低。时间复杂度是对算法速度的衡量；空间复杂度是对算法占用内存量的衡量。,时间复杂度和空间复杂度是一对矛盾，可以相互转化,算法和算法分析(contd),算法效率的度量：算法执行时间需要通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。度量一个程序的执行时间通常有两种方法： 事后统计法，存在两个缺陷 事前分析估算的方法，常用方法 算法的时间复杂度： 一个算法由控制结构（顺序、

9、分支和循环三种）和原操作（指固有数据类型的操作）构成，我们用对所研究的问题来说是基本操作的原操作的重复执行次数作为算法时间复杂度的量度。,原操作指对固有数据类型的操作,算法和算法分析(contd),【例】 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(rjrk) k=j; if(i!=k) temp=ri; ri=rk; rk=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)表示复杂度。左例的时间复杂度可