线性结构分类 线性结构 直接访问型 顺序访问型 目录索引型 向量 记录 宇典 散列表 顺序文佯 广义表 栈 队列 北京大学信息学院 版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 线性结构分类
21线性表( inear list 211线性表的抽象数据类型 212线性表的存储结构 213线性表运算分类 北京大学信息学院 @版权所有,转载或翻印必究 Page 7
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 2.1 线性表(linear list) ◼ 2.1.1 线性表的抽象数据类型 ◼ 2.1.2 线性表的存储结构 ◼ 2.1.3 线性表运算分类
线性表的抽象数据类型 线性表定义: 由结点集N,以及定义在结点集N 上的线性关系r所组成的线性结构。 这些结点称为线性表的元素。 北京大学信息学院 @版权所有,转载或翻印必究 Page 8
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 线性表的抽象数据类型 ◼ 线性表定义： ◼ 由结点集N，以及定义在结点集N 上的线性关系r所组成的线性结构。 这些结点称为线性表的元素
线性表的性质 线性表(N,r) (a)结点集N中有一个唯一的开始结 点,它没有前驱,但有一个唯一的后 继 的终止结点该结点有一个唯一的前 驱而没有后继; (c)其它的结点皆称为内部结点,每 个内部结点既有一个唯一的前驱, 也有一个唯一的后继 北京大学信息学院 @版权所有,转载或翻印必究 Page 9
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 线性表的性质 ◼ 线性表（N , r）： ◼ （a）结点集N中有一个唯一的开始结 点，它没有前驱，但有一个唯一的后 继； ◼ （b）对于有限集N, 它存在一个唯一 的终止结点，该结点有一个唯一的前 驱而没有后继； ◼ （c）其它的结点皆称为内部结点，每 一个内部结点既有一个唯一的前驱， 也有一个唯一的后继；
线性表的性质(续) 线性表(N,r) (d)线性表所包含的结点个数称 个量要参数:长度为0的线性表 性表的长度,它是线性表的 称为空表; (e)线性表的关系r,简称前驱 关系,应具有反对称性和传递性。 北京大学信息学院 版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 线性表的性质（续） ◼ 线性表（N , r）： ◼ （d）线性表所包含的结点个数称 为线性表的长度，它是线性表的 一个重要参数；长度为0的线性表 称为空表； ◼ （e）线性表的关系r，简称前驱 关系，应具有反对称性和传递性