答是要 1.1数据结构研究的内容 °所加工的数据对象进行逻舞组织 °将数据对象存储在计算机中 数据运算或处理 1.2基本概念和术语 °数据、数据元素、数据结构、逻辑结构 1.3抽象数据类型 °数据类型、抽亲数据类型 1.4算法和算法分析 算法、算法设计、算法效率
内容提要 1.1 数据结构研究的内容 • 对所加工的数据对象进行逻辑组织 • 将数据对象存储在计算机中 • 数据运算或处理 1.2 基本概念和术语 • 数据、数据元素、数据结构、逻辑结构 1.3 抽象数据类型 • 数据类型、抽象数据类型 1.4 算法和算法分析 • 算法、算法设计、算法效率
数据结构充的内容 计算机中的非数值运算:字符、表格、声音、图象等 (1)对所加工的数据对象进行逻辑组织 数据元素及其数据项 数据元素之间的逻关系:线性或是非线性 (2)将数据对象存值在计算机中 逻舞结构在计算机中的存被成为“物理结构”或“存信结构” 物理结构要存信:数据元素本身和数据元素之间的关系 物理结构的设计要满足:算法的实现、的间和内存空间的节省 (3)数据运算或处理 基于某种特定程序语言的算法
1.1 数据结构研究的内容 计算机中的非数值运算：字符、表格、声音、图象等 (1) 对所加工的数据对象进行逻辑组织 – 数据元素及其数据项 – 数据元素之间的逻辑关系：线性或是非线性 (2) 将数据对象存储在计算机中 逻辑结构在计算机中的存储被成为“物理结构”或“存储结构” 物理结构要存储：数据元素本身和数据元素之间的关系 物理结构的设计要满足：算法的实现、时间和内存空间的节省 (3) 数据运算或处理 基于某种特定程序语言的算法
数据结构的成容cnt 用计算机解决一个具体问题的步骤 (1)从层体间题抽象出一个适当的数学模型 寻求数学模型的实质是分析问题 (2)设计一个解此数学模型的算法 从中提取操作的对象,并找出这些操作对象之间含有的关系 用数学语言加以描述 (3)编出程序、进行测、调整直至得到最终解答
数据结构研究的内容(cont’d) 用计算机解决一个具体问题的步骤： (1) 从具体问题抽象出一个适当的数学模型 – 寻求数学模型的实质是分析问题 (2) 设计一个解此数学模型的算法 – 从中提取操作的对象，并找出这些操作对象之间含有的关系 ，用数学语言加以描述 (3) 编出程序、进行测试、调整直至得到最终解答
数据结构的成容cnt Example: 1-1图书信的书目检索系统自动化问题 由四张表构成的文件为本系统的数学模型(见书2) 文档管理的数学模型一线性数据结构 1-2计算机和人剧交问题 格局(对奕过程中可能出现的盘状态) 格局之间的关系比赛规则决定一非线性(树型)数据结构 1-3多叉路口交通灯的管理问题 非线性(图)数据结构
数据结构研究的内容(cont’d) Example ： 1-1 图书馆的书目检索系统自动化问题 – 由四张表构成的文件为本系统的数学模型（见书P2） – 文档管理的数学模型 — 线性数据结构 1-2 计算机和人对奕问题 – 格局（对奕过程中可能出现的棋盘状态） – 格局之间的关系由比赛规则决定 — 非线性（树型）数据结构 1-3 多叉路口交通灯的管理问题 – 非线性（图）数据结构
数据结构的成容cnt Example1-1:图书目录文件示例 001高等数学欧∥S01 002 理论力学 罗远祥 L01 003 高等数学华罗庚 S01 004线性代数栾汝书S02 高等数学00,03-.燹∥001,「L002 理论力学002 华罗庚00.4s0010030.4 线性代数00 栾汝004
数据结构研究的内容(cont’d) Example 1-1：图书目录文件示例 001 高等数学 樊映川 S01 … 002 理论力学 罗远祥 L01 … 003 高等数学 华罗庚 S01 … 004 线性代数 栾汝书 S02 … … … … … … 高等数学 001,003,… 理论力学 002,… 线性代数 004,… … … 樊映川 001,… 华罗庚 003,… 栾汝书 004,… … … L 002,… S 001,003,… … …
数据结构的成容cnt Example1-2:并字棋对奕“树 X X XX X X XX X X O x O x O x O XOX (a (a)棋盘格局示例;(b)对奕树的局部
数据结构研究的内容(cont’d) Example 1-2：井字棋对奕 “树 ” o x x o (a) o x x o o x x x o x o x x o x o x x o o x x o x (b) (a) 棋盘格局示例； (b) 对奕树的局部 o x x x o
数据结构的成容cnt Example1-3:五叉路口交通管理示意图 在路口有13条可行的通路, 如:A→>B和E→C 不能同时通行,如:E→>B 和A→D (a)五叉路口
数据结构研究的内容(cont’d) Example 1-3：五叉路口交通管理示意图 (a) 五叉路口 C B A D E 在路口有13条可行的通路， 如：A→B和E → C 不能同时通行，如：E → B 和A → D
1.2差水燃念和水 数据(Data):对容观事物的符号表示 t数据元素 Yata elemen1):是作为整体考虑和处理的数据 的基本单位 数据项( Data Item):组成数据元素,是数据不可分割的 最小单位 (主关键字:能唯一标识数据元素的数据项 次关键字:不能一标识数据元素的数据项 ●数据对象 data object):性质相同的数据元素的有限集 数据结构 Data structure):数据元素之间所具有的特定 关系的有限集 逻瓣结构:数据元素之间的逻关系 0存储结构:数据结构在计算机中的表示
1.2 基本概念和术语 数据(Data)：对客观事物的符号表示 数据元素(data element)：是作为整体考虑和处理的数据 的基本单位 数据项(Data Item)：组成数据元素，是数据不可分割的 最小单位 (主)关键字：能唯一标识数据元素的数据项 次关键字：不能唯一标识数据元素的数据项 数据对象(data object) ：性质相同的数据元素的有限集 数据结构(Data Structure)：数据元素之间所具有的特定 关系的有限集 逻辑结构：数据元素之间的逻辑关系 存储结构：数据结构在计算机中的表示
1、数据结构的形式化定义: Data-Structure=(D, R,, ①23(45
基本概念和术语(cont’d) 1、数据结构的形式化定义： Data-Structure=( D, R ) 二元组 数据元素的有限集 D上关系的有限集(逻辑结构) 2、四种逻辑结构： (1) 集合 (2) 线性结构：元素之间是一一对应的关系，首元素无前趋，尾 元素无后继，其他元素都只有一个前驱和后继 【例】Linear=(D,R) D={1,2,3,4,5} R={,,,} 序偶 1 2 3 4 5
差含和(ct 四种逻辑结构 (3)树型结构:元素之间存在一对多的关系,其中只有一个元素没有前 驱,称为根。其他元素只有一个前驱,但可以有多个后继。 【例Tree=(D,R D=Ya, b, c, d, e, t 只={a,b>,,,,<b a b d
基本概念和术语(cont’d) 四种逻辑结构： (3) 树型结构 ：元素之间存在一对多的关系，其中只有一个元素没有前 驱，称为根。其他元素只有一个前驱，但可以有多个后继。 【例】Tree=(D,R) D={a,b,c,d,e,f} R={,,,,} a b c d e f