第二章线性表、栈和队列 任课教员:张铭 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)