吴及《数据与算法课程讲义》清华大学：2基本数据结构2-线性表.pdfVIP

2015-2016秋季学期数据与算法课程讲义 基础数据结构 吴 及 wuji_ee@tsinghua.edu.cn 清华大学电子工程系 2015年9月 内容提要  二元关系与抽象数据类型  线性表 栈与队列  串 树与二叉树  图 数据与算法 2 吴及 电子工程系 线性表  线性表是一种 “有序”结构，即在数据元素的非空有限集合中：  存在唯一的一个被称为 “第一个”的数据元素，无前驱；  存在唯一的一个被称为 “最后一个”的数据元素，无后继；  除第一个之外，每个数据元素均只有一个直接前驱；  除最后一个之外，每个数据元素均只有一个直接后继； 0 … −1 +1 … 第一个 的直接前驱 的直接后继 最后一个 数据与算法 3 吴及 电子工程系 线性表的定义  线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定 具有相同特性– 同质  线性表中的相邻元素之间存在有序关系– 位序  若将线性表记为（ , , … , , , , … , ） 0 1 −1 +1  领先于 ， 领先于 ； −1 +1  称 是 的直接前驱元素 −1  称a 是 的直接后继元素 i+1  当 = 0, 1, 2 … − 1时，有且仅有一个直接后继元素；  当 = 1, 2,3 ⋯ 时，有且仅有一个直接前驱元素； 数据与算法 4 吴及 电子工程系 线性表的长度和位序  线性表中元素的个数定义为线性表的长度 , , ⋯ , , , , ⋯ , 0 1 −1 +1 −1  若线性表为空，则其长度为0 ；称为空表  在非空表中，每个数据元素都有一个确定的位置  是第0个数据元素 0  −1是第 − 1 个数据元素 