南开大的学 数据结构Week4 线性表.pdf

第三章 线性表 线性表的定义和基本运算 线性表的实现 线性表的应用 示例 例 （2，6，8，3，9，4）是一个线性表， 其中的数据元素是整数，按表中列出的顺 序排列，表中共有6个数据元素。 例 （A，B，C，D，E，…，X，Y，Z）是一 个线性表，其中的数据元素是英文大写字 母，按字母表的顺序排列，共有26个数据 元素。 示例 例 学生入学成绩表也是一个线性表。其 中的数据元素是每个学生在表中所占的一 行，包括姓名、准考证号、性别、年龄和 总分等共5个数据项。通常把这种数据元素 称为纪录。 姓名 准考证号 性别 年龄 总分 陈义平 030010023 男 18 589 陆东 030010025 男 19 568 王晓敏 030010037 女 18 574 ┇ ┇ ┇ ┇ ┇ 李志强 030010123 男 19 617 线性表的定义 线性表：一个线性表（list）是由同类型 数据元素构成的有限序列， 记作 （a , a , … , a ）。 0 1 n-1 这个定义中强调两个特性，一个是强调每 个数据元素ai （i=0，…，n-1）必须是同 类型的数据，不能将不同类型的数据并列 在一个线性表内。另一个是强调表中数据 元素的有序性，也就是说每个元素在表中 都有自己的位置。 术语 当线性表中不包含任何元素时，称之为空 表，记作（）。 表中具有元素的个数称为线性表的长度。 线性表的第一个元素称为表头，最后一个 元素称为表尾。 对于表中第i个元素ai来说，第i-1个元素 ai-1称为它的直接前驱 （简称前驱），第 i+1个元素ai+1称为它的直接后继 （简称后 继）。当然，表头没有直接前驱，表尾没 有直接后继。 线性表类的ADT class list { // 线性表类的ADT public: list(const int sz LIST_SIZE); // 构造函数 ~list( )； // 析构函数 void clear( );// 从表中清除所有元素 void insert(const ELEM); // 在当前位置插入一个元素 ELEM remove()； // 删除并返回当前元素的值 void setFirst(); // 置光标于第一个位置 void prev(); // 移动光标到前一位置