1、线性结构的特点：在数据元素的非空有限集中，（ 1） 存在唯一的一个被称为 “第一个 ”的数据元素（ 2） 存在唯一的一个被称为 “最后 一个 ”的数据元素（ 3）除第一个之外，集合中的每个数据元素均只有一个前驱（ 4）除最后一个之外，集合中的每个数据元素均只有一个后继第二章 线性表“ 线性表 ” 简称为表，是零个或多个元素的有穷序列，通常可以表示成 k0， k1, ， kn-1 （ n 1）。 表中所含元素的个数称为表的 “ 长度 ” 。长度为零的表称为 “ 空表 ”。表中的元素又称 “ 表目 ” 。线性表中的数据元素在不同的情况下可以有不同的具体含义，它可以是一个数、一个符号，也可是其它更复
2、杂的信息。 2.1 线性表的概念通常线性表有以下几种基本运算：1. 在线性表中插入一个元素；2. 在线性表中删除某个元素；3. 在线性表中查找某个特定元素；4. 在线性表中查找某个元素的后继元素；5. 在线性表中查找某个元素的前驱元素；6. 创建空线性表；7. 判别一个线性表是否为空表。由上面的基本运算还可以构成其它较为复杂的运算，如创建线性表。线性表的基本运算#include #include /* 符号常量 */#define MAXNUM 100 /* 线性表空间大小 */#define FALSE 0#define TRUE 1#define SPECIAL 2147483647 /*
3、 与 DataType 类型有关， 32位机上的最大整数为 231-1 */#define PI 3.1415926/* 常用结构 */typedef int DataType; /* 定义数据类型为整型，也可定义为其他类型 */typedef int ElemType; /* 定义元素类型为整型，也可定义为其他类型 */typedef int KeyType; 以元素在计算机 内存中的 “物理位置相邻 ”来表示线性表中数据元素之间的逻辑关系 ，如下所示：Locate(ai+1) = Locate(ai) + sizeof(DataType)Locate(ai) = Locate(a0) +
4、sizeof(DataType) * I只要确定了首地址，线性表中任意数据元素都可以随机存取。 2.2 线性表的顺序表示和实现逻辑 地址数据元素 存 储 地址 数据元素0 k0 Loc(k0) k01 k1 Loc(k0)+c k1 i ki Loc(k0)+i*c ki n-1 kn-1 Loc(k0)+(n-1)*c kn-1线性表的顺序存储结构示意图顺序表的定义在 C语言中可以用以下方式定义一个顺序表： DataType elementMAXNUM;int n;这种定义的缺点在于没有反映出 element和的内在联系：即没有指出是顺序表 element本身的属性。在这个定义中，和 ele
5、ment完全处于独立平等的地位，所以程序中完全可以将作为一个自由变量来使用。 为次， 引进 SeqList类型，它的定义为： typedef struct SeqListDataType elementMAXNUM; int n; /* n n 时有意义。2. int delete_seq( PSeqList palist, int p ) 在 palist所指顺序表中删除下标为的元素，并返回删除成功与否的标志。此运算在 0 p l-n时有意义。3. int first_seq( PSeqList palist ) 求 palist所指顺序表中第一个元素的下标。当 palist为空表时返回一个
6、特殊的下标值 -1。4. int locate_seq( PSeqList palist, DataType x ) 在 palist所指顺序表中寻找值为的元素的下标，若palist中不存在值为的元素，则返回一个特殊的下标值-1。5. DataType retrieve_seq( PSeqList palist,int p ) 在 palist所指顺序表中，寻找下标为（ 0 p l-n） 的元素，并将该元素的值作为函数值返回，若 palist中无下标为的元素，则返回一个特殊的值。6. int next_seq( PSeqList palist, int p ) 求 palist所指顺序表中下标为的元素的后继元素下标，当不存在下标为的元素或虽有该元素但无后继时，返回一个特殊的下标值 -1。
