线性表的顺序表示与实现

线性表的顺序表示与实现2013-05-24线性表是线性结构，我们来研究它的逻辑关系，用ADT（抽象数据类型）来表示，ADT的描述可以从顺序结构表示和链式结构表示。

线性表的表示与实现-------顺序结构

关于顺序结构

顺序结构用顺序表来实现和描述。顺序表在C语言中通常会用一维数组来表示顺序存储结构。

顺序表结构特点：随机查找，删除插入麻烦，可变大小。

用一组地址连续的存储单元依次存放线性表中的数据元素，顺序表中的每个在逻辑上相邻的元素在物理存储位置上也是相邻的。如下图所示，a1,a2在逻辑上相邻，在物理表中的存储位置也是相邻的。

设每个元素占用C个存储单元，线性表中第i+1个元素的存储位置LOC（a i+1）和第i个元素存储位置之间的关系：

LOC（ai） = LOC（ai-1） + C

一个数据元素所占存储量↑

所有数据元素的存储位置均取决于第一个数据元素的存储位置

LOC（ai） = LOC（a1） + （i-1）×C

↑基地址

顺序映像的描述定义：

注意：在顺序结构中，由于顺序结构的特点（逻辑上相邻，物理上也相邻），在定义和实现顺序结构的时候，可以不使用指针，因为顺序结构每个元素的指向都是根据存储位置而固定好的，就是一个挨着一个。为了大家好理解，在顺序结构中，我们会用两种做法来描述顺序结构。一种是使用指针，一种是不使用指针。

不使用指针#defineMAXSIZE 100// 线性表存储空间的分配量，即数组长度typedefstruct {ElemType elem[MAXSIZE]; 定义数组intlength; // 当前长度 ，线性表的元素个数，并不是数组长度} SqList;// 俗称 顺序表指针定义#defineMAXSIZE 100// 线性表存储空间的分配量，即数组长度#define LISTINCREMENT10 //线性表存储空间的分配增量typedefstruct {ElemType *elem;//存储空间基地址  intlength; // 当前长度 ，线性表的元素个数，并不是数组长度  intlistsize;//当前分配的存储容量} SqList;// 俗称 顺序表

在上述代码中，用两种方法定义了一个结构体的顺序表，用ElemType表示未知数据类型的总称。

SqList为表的名称。

注意：不使用指针的顺序定义是定义了一个长度不可变的空间，即空间的大小不能变，就是MAXSIZE（100）个元素。而使用指针定义是定义了一个长度可变的空间，它是动态内存分配的一维数组，可以在原来分配空间大小的基础上再增加LISTINCREMENT（10）个空间大小。

线性表的顺序实现（初始化、查找、插入、删除、取元素）

线性表有两种实现，一种是顺序实现，一种是链式实现。上述中我们已经定义了顺序表SqList，那么我们现在先用顺序实现。

顺序实现的几个例子：注意：在上述定义顺序表SqList时，我们用了两种方法（非指针和指针），那么在实现顺序结构时，也用两种方法进行实现，分别对应两种定义。