北京大学：《数据结构与算法》课程教学资源（PPT课件讲稿）2、线性表、栈和队列（线性表（向量、链表））

国家级精品课程—《数据结构与算法》 第2章线性表 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:赵海燕 版权所有,转载或翻印必究

国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：赵海燕 ©版权所有，转载或翻印必究 第2章 线性表

主要内容 21线性表的概念 22顺序表 23链表 24线性表实现方法的比较 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 主要内容 ◼ 2.1 线性表的概念 ◼ 2.2 顺序表 ◼ 2.3 链表 ◼ 2.4 线性表实现方法的比较

问题求解 线性结构 顺序表 链表 线性表实现方法的比较 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。3

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 3 问题求解 ◼ 线性结构 ◼ 顺序表 ◼ 链表 ◼ 线性表实现方法的比较

线性结构 元素间满足线性关系 口“一对一”的关系 a按此关系结构中的所有元素排成一个线性序列 元组B=K,R), K={ao,a1,…,an-1},R={r}: 口结点集K中有一个唯一的开始结点,它没有前驱,但有一个 唯一的后继; 口对于有限集K,它存在一个唯一的终止结点,该结点有一个 唯一的前驱而没有后继 口其它的结点皆称为内部结点,每二个内部结点都有且仅有 个唯一的前驱,也有一个唯一的后继 yn-1 a是a的前驱,a+是a的后继 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。4

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 4 线性结构 ◼ 元素间满足线性关系 ❑ “一对一”的关系 ❑ 按此关系结构中的所有元素排成一个线性序列 ◼ 二元组B = (K, R) , K = {a0 , a1 , …, an-1 }, R = {r} ： ❑ 结点集K中有一个唯一的开始结点，它没有前驱，但有一个 唯一的后继； ❑ 对于有限集K , 它存在一个唯一的终止结点，该结点有一个 唯一的前驱而没有后继； ❑ 其它的结点皆称为内部结点，每一个内部结点都有且仅有一 个唯一的前驱，也有一个唯一的后继； a0 , a1 , …, an-1 ai是ai+1的前驱， ai+1是ai的后继

线性结构 特点: 均匀性:虽然不同线性表的数据元素可以是各种 各样的,但对于同一线性表的各数据元素必定具 有相同的数据类型和长度 口有序性:各数据元素在线性表中都有自己的位置, 且数据元素之间的相对位置是线性的 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。5

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5 线性结构 ◼ 特点： ❑ 均匀性：虽然不同线性表的数据元素可以是各种 各样的，但对于同一线性表的各数据元素必定具 有相同的数据类型和长度 ❑ 有序性：各数据元素在线性表中都有自己的位置， 且数据元素之间的相对位置是线性的

线性结构 包括: 口简单的 线性表 栈 胶列 口高级的 广义表 多维数组 文件 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。6

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6 线性结构 ◼ 包括： ❑ 简单的 ◼ 线性表 ◼ 栈 ◼ 队列 ◼ 散列表 ❑ 高级的 ◼ 广义表 ◼ 多维数组 ◼ 文件 ❑ ……

线性结构分类 ■按访问方式划分 口直接访间型 direct access) a顺序访间型( sequentia| access) 口目录索引型 directorv access) 线性结构 直接访问型 顺序访问型 目录索引型 向量 记录 宇典 散列表 顺序文 广义表 十一五”国家级规划教材。张铭 栈 队列

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7 线性结构分类 ◼ 按访问方式划分 ❑ 直接访问型(direct access) ❑ 顺序访问型( sequential access) ❑ 目录索引型(directory access)

线性结构分类 按操作划分 线性表 所有表目都是同一类型结点的线性表 不限制操作形式 根据存储的不同分为:顺序表,链表 口栈(L|FO, Last in first out) 插入和删除操作都限制在表的同一端进行 口队列(FIFO, First In First out ■插入操作在表的一端,删除操作在另一端 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6。8

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 8 线性结构分类 ◼ 按操作划分 ❑ 线性表 ◼ 所有表目都是同一类型结点的线性表 ◼ 不限制操作形式 ◼ 根据存储的不同分为：顺序表，链表 ❑ 栈(LIFO, Last In First Out) ◼ 插入和删除操作都限制在表的同一端进行 ❑ 队列(FIFO, First In First Out) ◼ 插入操作在表的一端， 删除操作在另一端

线性表( linear list 三个方面 口线性表的逻辑结构 口线性表的存储结构 口线性表运算分类 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。9

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 9 线性表 (linear list) ◼ 三个方面 ❑ 线性表的逻辑结构 ❑ 线性表的存储结构 ❑ 线性表运算分类

线性表的逻辑结构 线性表: a由称为元素( element)的数据项组成的一种有限且有 序的序列,这些元素也可称为结点或表目 二元组(K,r): a由结点集K,以及定义在结点集K上的线性关系r所组成 的线性结构 口线性表所包含的结点个数称为线性表的长度,它是线性 表的一个重要参数;长度为0的线性表称为空表 线性表的关系r,简称前驱后继关系,具有反对称性和 传递性 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6。10

“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 10 线性表的逻辑结构 ◼ 线性表： ❑ 由称为元素（element）的数据项组成的一种有限且有 序的序列，这些元素也可称为结点或表目 ◼ 二元组(K , r) ： ❑ 由结点集K，以及定义在结点集K上的线性关系 r 所组成 的线性结构 ❑ 线性表所包含的结点个数称为线性表的长度，它是线性 表的一个重要参数；长度为0的线性表称为空表； ❑ 线性表的关系 r，简称前驱/后继关系，具有反对称性和 传递性