第二章线性表、栈和队列 任课教员:张铭 http://db.pku.edu.cn/mzhang/dsl zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
第二章 线性表、栈和队列 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
大纲 21线性表( linear list 211线性表的抽象数据类型 212线性表的存储结构 213线性表运算分类 22顺序表一向量( sequential list-vector) 221向量的类定义 type definition 2.2.2向量的运算 北京大学信息学院 @版权所有,转载或翻印必究 Page 2
北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 大纲 ◼ 2.1 线性表(linear list) ◼ 2.1.1 线性表的抽象数据类型 ◼ 2.1.2 线性表的存储结构 ◼ 2.1.3 线性表运算分类 ◼ 2.2 顺序表—向量(sequential list—vector ) ◼ 2.2.1 向量的类定义(type definition) ◼ 2.2.2 向量的运算
2.5栈 25.1顺序栈 252链式栈 253顺序栈与链式栈的比较 254栈的应用—后缀表达式求值 2.54递归的实现 26队列 2.61顺序队列 262链式队列 2.23顺序队列与链式队列的比较 北京大学信息学院 @版权所有,转载或翻印必究 Page 3
北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 ◼ 2.5 栈 ◼ 2.5.1 顺序栈 ◼ 2.5.2 链式栈 ◼ 2.5.3 顺序栈与链式栈的比较 ◼ 2.5.4 栈的应用——后缀表达式求值 ◼ 2.5.4 递归的实现 ◼ 2.6 队列 ◼ 2.6.1 顺序队列 ◼ 2.6.2 链式队列 ◼ 2.2.3 顺序队列与链式队列的比较
大纲(续) 23链表( inked list) 231单链表( singly linked list) 232双链表( double linked list 233循环链表( circularly linked list) 24线性表实现方法的比较 北京大学信息学院 @版权所有,转载或翻印必究 Page 4
北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 大纲（续） ◼ 2.3 链表(linked list) ◼ 2.3.1单 链 表(singly linked list) ◼ 2.3.2 双 链 表(double linked list) ◼ 2.3.3 循 环 链 表(circularly linked list) ◼ 2.4 线性表实现方法的比较
线性结构分类 直接访问型( direct access) 顺序访问型( sequentia 弓 ccess n目录索引型( directory access) 北京大学信息学院 @版权所有,转载或翻印必究 Page 5
北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 线性结构分类 ◼ 直接访问型( direct access ) ◼ 顺序访问型(sequential access) ◼ 目录索引型(directory access)
线性结构分类 线性结构 直接访问型 顺序访问型 目录索引型 向量 记录 宇典 散列表 顺序文佯 广义表 栈 队列 北京大学信息学院 版权所有,转载或翻印必究 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，简称前驱 关系，应具有反对称性和传递性