线性表的顺序表示和实现

cyxs · 发表于 2016-7-12 15:15

EDA365欢迎您！

您需要登录才可以下载或查看，没有帐号？注册

x

线性表的顺序表示指的是用一组地址连续的存储单元一次存储线性表的数据元素。
假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置LOC（ai）之间满足下列关系：
LOC（ai）= LOC（ai）+l
一般来说，线性表的第i个数据元素ai的存储位置为
LOC（ai）= LOC（ai）+（i-1）×l
式中LOC（ai）是线性表的第一个数据元素ai的存储位置，通常称作线性表的其实位置或基地址。
线性表的这种机内表示称做线性表的顺序存储机构或顺序映像，通常，称这种存储结构的线性表为顺序表。它的特点是，为表中相邻的元素ai和ai+1赋以相邻的存储位置LOC（ai）和LOC（ai+1）。换句话说，每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。在此，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组，如下描述。
#define LIST_INIT_SIZE    100       //线性表存储空间的初始分配量
#define LISTINCREMENT 10          //线性表存储空间的分配增量
typedef struct{
   ElemType    *elem;                //存储空间基址
   int             length                //当前长度
   int             listsize;                //当前分配的存储容量
}SqList;
在上述定义中，数组指针elem指示线性表的基地址，lenth指示线性表的当前长度。顺序表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为“0”。Listsize指示顺序表当前分配的存储空间大小，一旦因插入元素而空间不足时，可进行再分配，即为顺序表增加一个大小为存储LISTINCREMENT个数据元素的空间。
Status InitList——Sq（SqList 7L）{
//构造一个空的线性表L。
L．elem=（ElemType *）malloc（LIST_INIT_SIZE *sizeof（ElemType））；
If（！ L.elem）exit(OVERFLOW);          //存储分配失败
L．length=0；                                        //空表长度为0
L．listsize= LIST_INIT_SIZE；             //初始存储容量
return OK；
}//InitList_Sq