数据结构研究的内容 计算机中的非数值运算:字符、表格、声音、图象等 (1)对所加工的数据对象进行逻辑组织 数据元素及其数据项 数据元素之间的逻辑关系:线性或是非线性 (2)将数据对象存储在计算机中 逻辑结构在计算机中的存储被成为“物理结构”或“存储结构” 物理结构要存储:数据元素本身和数据元素之间的关系 物理结构的设计要满足:算法的实现、时间和内存空间的节省 (3)数据运算或处理 基于某种特定程序语言的算法
一、数据结构研究的内容 计算机中的非数值运算：字符、表格、声音、图象等 (1)对所加工的数据对象进行逻辑组织 • 数据元素及其数据项 • 数据元素之间的逻辑关系：线性或是非线性 (2)将数据对象存储在计算机中 逻辑结构在计算机中的存储被成为“物理结构”或“存储结构” 物理结构要存储：数据元素本身和数据元素之间的关系 物理结构的设计要满足：算法的实现、时间和内存空间的节省 (3)数据运算或处理 基于某种特定程序语言的算法
2、基本概念和术语 数据:对客观事物的符号表示 数据元素:是作为整体考虑和处理的数据的基本单位 (data element) 数据项:组成数据元素 (主)关键字:能唯一标识数据元素的数据项 次关键字:不能唯一标识数据元素的数据项 数据对象:性质相同的数据元素的有限集 ( data object) 数据结构:数据元素之间所具有的特定关系的有限集 逻辑结构、存储结构
2、基本概念和术语 • 数据：对客观事物的符号表示 • 数据元素：是作为整体考虑和处理的数据的基本单位 (data element) • 数据项：组成数据元素 • (主)关键字：能唯一标识数据元素的数据项 • 次关键字：不能唯一标识数据元素的数据项 • 数据对象：性质相同的数据元素的有限集 (data object) • 数据结构：数据元素之间所具有的特定关系的有限集 • 逻辑结构、存储结构
2、基本概念和术语 数据结构的形式化定义 Data-Structure=(D,RQ 组 数据元素的有限集D上关系的有限集(逻辑结构) 四种逻辑结构 (1)集合 (2)线性结构:元素之间是一一对应的关系,首元素无前趋,尾 元素无后继,其他元素都只有一个前驱和后继 【例】 Linear=①DR) 序偶 D={1,2,3,4,5 R={<1,2>,<2,3>34>,<4,5>}
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>} 序偶 1 2 3 4 5
2、基本概念和术语 四种逻辑结构(续): (3)树型结构:元素之间存在一对多的关系,其中只有一个元素 没有前驱,称为根。其他元素只有一个前驱,但可以有多个 后继 【例】Tree=(D,R) D-a, b, c, d, e, f R={a2b>,<aC>,<ad>,c,e>2<C,f>} a人 (d
2、基本概念和术语 • 四种逻辑结构(续)： (3)树型结构：元素之间存在一对多的关系，其中只有一个元素 没有前驱，称为根。其他元素只有一个前驱，但可以有多个 后继。 【例】Tree=(D,R) D={a,b,c,d,e,f} R={<a,b>,<a,c>,<a,d>,<c,e>,<c,f>} a b c d e f
2、基本概念和术语 四种逻辑结构(续): (4)图型结构:元素之间存在多对多的关系,任何元素之间都可 以存在关系 【例】 Graph=(DR) D={1,2,3,4} R={<1,2>,<1,3>,<2,4>,<34>,<3,2>} 3
2、基本概念和术语 • 四种逻辑结构(续)： (4)图型结构：元素之间存在多对多的关系，任何元素之间都可 以存在关系 【例】Graph=(D,R) D={1,2,3,4} R={<1,2>,<1,3>,<2,4>,<3,4>,<3,2>} 3 1 2 4