数据与算法课程讲义（吴及）基础数据结构2-线性表.pdfVIP

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