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

内容提要 1.1 数据结构研究的内容 对所加工的数据对象进行逻辑组织 将数据对象存储在计算机中 数据运算或处理 1.2 基本概念和术语 数据、数据元素、数据结构、逻辑结构 1.3 抽象数据类型 数据类型、抽象数据类型 1.4 算法和算法分析 算法、算法设计、算法效率 1.1 数据结构研究的内容 计算机中的非数值运算：字符、表格、声音、图象等 (1) 对所加工的数据对象进行逻辑组织 数据元素及其数据项 数据元素之间的逻辑关系：线性或是非线性 (2) 将数据对象存储在计算机中 逻辑结构在计算机中的存储被成为“物理结构”或“存储结构” 物理结构要存储：数据元素本身和数据元素之间的关系 物理结构的设计要满足：算法的实现、时间和内存空间的节省 (3) 数据运算或处理 基于某种特定程序语言的算法 数据结构研究的内容(cont’d) 用计算机解决一个具体问题的步骤： (1) 从具体问题抽象出一个适当的数学模型 寻求数学模型的实质是分析问题 (2) 设计一个解此数学模型的算法 从中提取操作的对象，并找出这些操作对象之间含有的关系，用数学语言加以描述 (3) 编出程序、进行测试、调整直至得到最终解答 数据结构研究的内容(cont’d) Example ： 1-1 图书馆的书目检索系统自动化问题 由四张表构成的文件为本系统的数学模型（见书P2） 文档管理的数学模型 — 线性数据结构 1-2 计算机和人对奕问题 格局（对奕过程中可能出现的棋盘状态） 格局之间的关系由比赛规则决定 — 非线性（树型）数据结构 1-3 多叉路口交通灯的管理问题 非线性（图）数据结构 数据结构研究的内容(cont’d) Example 1-1：图书目录文件示例 数据结构研究的内容(cont’d) Example 1-2：井字棋对奕 “树 ” 数据结构研究的内容(cont’d) Example 1-3：五叉路口交通管理示意图 1.2 基本概念和术语 数据(Data)：对客观事物的符号表示 数据元素(data element)：是作为整体考虑和处理的数据的基本单位 数据项(Data Item)：组成数据元素，是数据不可分割的最小单位 (主)关键字：能唯一标识数据元素的数据项 次关键字：不能唯一标识数据元素的数据项 数据对象(data object) ：性质相同的数据元素的有限集 数据结构(Data Structure)：数据元素之间所具有的特定关系的有限集 逻辑结构：数据元素之间的逻辑关系 存储结构：数据结构在计算机中的表示 基本概念和术语(cont’d) 1、数据结构的形式化定义： Data-Structure=( D, R ) 二元组 数据元素的有限集 D上关系的有限集(逻辑结构) 2、四种逻辑结构： (1) 集合 (2) 线性结构：元素之间是一一对应的关系，首元素无前趋，尾元素无后继，其他元素都只有一个前驱和后继 【例】Linear=(D,R) D={1,2,3,4,5} R={1,2,2,3,3,4,4,5} 基本概念和术语(cont’d) 四种逻辑结构： (3) 树型结构 ：元素之间存在一对多的关系，其中只有一个元素没有前驱，称为根。其他元素只有一个前驱，但可以有多个后继。 【例】Tree=(D,R) D={a,b,c,d,e,f} R={a,b,a,c,a,d,b,e,b,f} 基本概念和术语(cont’d) 四种逻辑结构： (4)图型结构：元素之间存在多对多的关系，任何元素之间都可以存在关系 【例】Graph=(D,R) D={1,2,3,4} R={1,2,1,3,2,4,3,4,3,2} 基本概念和术语(cont’d) 3、两种基本的存储结构： (1) 顺序存储结构：利用元素在内存中相对位置来表示元素之间的关系 (2) 链式存储结构：利用“指针”来单独存储数据元素之间的关系。 1.3 数据类型和抽象数据类型 数据类型：是一个值的集合及定义于其上的一组操作的总称。也称为“抽象数据类型”。 抽象数据类型的形式定义： ADT=( D , S , P ) 三元组 数据对象 D上的关系 对D的基本操作 数据类型和抽象数据类型(cont’d) 抽象数据类型的格式定义： ADT抽象数据类型名 { 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本