结点类型:复合数据类型 复合类型是由基本数据类型组合而成的数据结构 类型 口例如:在程序语言中常用的数组类型,结构 (记录)类型等皆属复合数据类型 复合数据类型本身,又可以参与定义结构更为复 杂的结点类型 结点的类型不限于基本数据类型,可以根据应用 的需要来灵活定义 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 结点类型 ：复合数据类型 ◼ 复合类型是由基本数据类型组合而成的数据结构 类型 ❑ 例如：在程序语言中常用的数组类型，结构 （记录）类型等皆属复合数据类型 ◼ 复合数据类型本身，又可以参与定义结构更为复 杂的结点类型 ◼ 结点的类型不限于基本数据类型，可以根据应用 的需要来灵活定义
结构的分类 数据的逻辑结构(K,R)的讨论,一般把重点放 在关系集R上; 根据R的性质刻划数据结构的特点,并对数据结 构进行分类: 口线性结构( linear structure) 口树型结构( tree structure) a图结构( graph structure) “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 结构的分类 ◼ 数据的逻辑结构（K, R）的讨论，一般把重点放 在关系集R上； ◼ 根据 R的性质 刻划数据结构的特点，并对数据结 构进行分类： ❑ 线性结构（linear structure） ❑ 树型结构（tree structure） ❑ 图结构（graph structure）
线性结构 关系r是一种线性关系,或称为“前后关系”,有 时也称为“大小关系”。关系r是有向的,且满足 全序性和单索性等约束条件 a全序性是指,线性结构的全部结点两两皆可以比 较前后(关系r 单索性是指,每一个结点x都存在唯一的一个 直接后继结点y。如果其他结点z在y之前,则 这个z也一定在x之前,不会在x,y之间 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 线性结构 ◼ 关系r 是一种线性关系，或称为“前后关系”，有 时也称为“大小关系”。关系 r 是有向的，且满足 全序性和单索性等约束条件 ❑ 全序性是指，线性结构的全部结点两两皆可以比 较前后（关系 r） ❑ 单索性是指，每一个结点 x 都存在唯一的一个 直接后继结点 y。如果其他结点 z 在 y 之前，则 这个 z 也一定在 x 之前，不会在x，y之间
树型结构 ■简称树结构,或层次结构。其关系r称为层次关 系,或称“父子关系”、“上下级关系”等 每一个结点可以有多于一个的“直接下级”,但 是它只能有唯一的“直接上级”。 口树型结构的最高层次的结点称为根(root)结点。只有 它没有父结点 ■树型结构存在着很多变种,如二叉树结构,堆结 构等,都有各自独特的有效应用 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 树型结构 ◼ 简称树结构，或层次结构。其关系 r 称为层次关 系，或称“父子关系”、“上下级关系”等 ◼ 每一个结点可以有多于一个的“直接下级”，但 是它只能有唯一的“直接上级”。 ❑ 树型结构的最高层次的结点称为根（root）结点。只有 它没有父结点 ◼ 树型结构存在着很多变种，如二叉树结构，堆结 构等，都有各自独特的有效应用
图结构 有时称为结点互联的网络结构,因特网的网页链接关系就 是一个非常复杂的图结构 对于图结构的关系r没有加任何约束。这样也就无法象线 性结构及树结构那样,利用关系r的约束来设计图结构的 存储结构 在日常应用中图结构往往只是层次结构的一种扩展一一允 许结点具有多个“直接上级结点”,关系r表现为树型 结构约束的放松 从数学上看,树型结构和图结构的基本区别就是“每个结 点是否仅仅从属一个直接上级”。而线性结构和树型结构 的基本区别是“每个结点是否仅仅有一个直接后继” “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 图结构 ◼ 有时称为结点互联的网络结构，因特网的网页链接关系就 是一个非常复杂的图结构 ◼ 对于图结构的关系 r 没有加任何约束。这样也就无法象线 性结构及树结构那样，利用关系 r 的约束来设计图结构的 存储结构 ◼ 在日常应用中图结构往往只是层次结构的一种扩展――允 许结点具有多个“直接上级结点” ，关系 r 表现为树型 结构约束的放松 ◼ 从数学上看，树型结构和图结构的基本区别就是“每个结 点是否仅仅从属一个直接上级”。而线性结构和树型结构 的基本区别是“每个结点是否仅仅有一个直接后继