第二章　线性表

第二章 线性表一、线性结构的特点：二、线性表的定义线性表是最常用且最简单的一种数据结构。一个线性表是 n 个数据元素的有限序列。数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。线性表例：1、12345672、3、学号姓名语文数学C 语言6201001张三8554926201002李四9284646201003王五8774736201004 ... 数据元素也可由若干个数据项组成（如上例 3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。在数据元素的非空有限集中，1）存在唯一的一个被称做“第一个”的数据元素；2）存在唯一的一个被称做“最后一个”的数据元素；3）除第一个之外，集合中的每个数据元素均只有一个前驱；4）除最后一个之外，集合中每个数据元素均只有一个后继。线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。a1...ai-1aiai+1...anai是 ai+1的直接前驱元素，ai+1是 ai的直接后继元素。线性表中元素的个数 n 定义为线性表的长度，为 0 时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第 i 个元素，把 i 称为数据元素 ai在线性中的位序。三、线性表的顺序存储结构线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单，又自然的。如图 2.1 所示。设 a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为： Loc(ai)=Loc(a１)+(i-1)*d 1<=i<=n这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的。考虑到线性表的运算有插入、删除等运算，即表长是可变的，因此，数组的容量需设计的足够大，设用：data[MAXSIZE]来表示，其中MAXSIZE是一个根据实际问题定义的足够大的整数，线性表中的数据从 data[0] 开始依次顺序存放，但当前线性表中的实际元素个数可能未达到MAXSIZE多个，因此需用一个变量 last 记录当前线性表中最后一个元素在数组中的位置，即 last 起一个指针的作用，始终指向...