[科普中国]-顺序存储

顺序存储是所有的结点存放在一块连续的存储区域中，用存储结点的位置来体现结点之间的逻辑关系的存储方法。在高级语言中，一块连续的存储空间通常可用一个数组来表示。因此，顺序存储通常用一个数据元素类型的数组来存储。最经典的顺序存储结构是顺序表，将线性结构的元素按序存放在一个数组中1。

简介顺序存储是指用一段地址连续的存储单元存储相邻数据元素，或把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现（逻辑与物理统一），要求内存中可用的存储单元的地址必须是连续的。优点：存储密度大，存储空间利用概率高。缺点：插入或删除元素时不方便。与顺序存储相对应是链接存储。这种方法主要用于线性的数据结构。对非线性结构也可以采用局部线性化的方法实现顺序存储。例如，在树形结构中可以把结点按某种规则排成序列，用顺序存储方法把结点内部的信息稠密地存放在一起，而对结点之间的关系采用其他的存放方法。

顺序存储主要使用数组，采用顺序存储的优点：可以随机访问数组中的元素，即通过下标去访问数组的元素；其缺点主要有二：其一，由于C语言中，数组一旦被声明，其长度即该结构占用的存储空间是固定的，申请的空间过大，造成空间的浪费同时也为维护该结构造成困难，申请过小，在程序运行过程中，有可能会造成结构空间不足，导致程序故障；其二，在插入，删除数据时，通常会导致大量数据的移动，在等概率的前提下，平均需要移动整个结构中一半的元素，如果元素个体比较复杂问题将更为明显2。

链接存储数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构，也称为数据的物理结构，是数据的逻辑结构在计算机中的实现。

链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。数据的链式存储结构可用链接表来表示。

其中data表示值域，用来存储节点的数值部分。Pl，p2，…，Pill(1n≥1)均为指针域，每个指针域为其对应的后继元素或前驱元素所在结点(以后简称为后继结点或前驱结点)的存储位置。通过结点的指针域(又称为链域)可以访问到对应的后继结点或前驱结点，若一个结点中的某个指针域不需要指向其他结点，则令它的值为空（NULL）。在数据的顺序存储中，由于每个元素的存储位置都可以通过简单计算得到，所以访问元素的时间都相同；而在数据的链接存储中，由于每个元素的存储位置保存在它的前驱或后继结点中，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到，访问任一元素的时间与该元素结点在链式存储结构中的位置有关。

顺序表顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中3。

/* 线性表的动态分配顺序存储结构 */#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */#define LIST_INCREMENT 2 /* 线性表存储空间的分配增量 */typedef struct{ ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */}SqList;/* 顺序表示的线性表的基本操作(12个) */void InitList(SqList *L) /* 算法2.3 */{ /* 操作结果：构造一个空的顺序线性表L */ L->elem=malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L->elem) exit(OVERFLOW); /* 存储分配失败 */ L->length=0; /* 空表长度为0 */ L->listsize=LIST_INIT_SIZE; /* 初始存储容量 */}void DestroyList(SqList *L){ /* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */ free(L->elem); L->elem=NULL; L->length=0; L->listsize=0;}void ClearList(SqList *L){ /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */ L->length=0;}Status ListEmpty(SqList L){ /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */ if(L.length==0) return TRUE; else return FALSE;}int ListLength(SqList L){ /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */ return L.length;}Status GetElem(SqList L,int i,ElemType *e){ /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值 */ if(iL.length) return ERROR; *e=*(L.elem+i-1); return OK;}int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)){ /* 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0) */ /* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */ /* 若这样的数据元素不存在，则返回值为0。 */ ElemType *p; int i=1; /* i的初值为第1个元素的位序 */ p=L.elem; /* p的初值为第1个元素的存储位置 */ while(i=L->listsize) /* 当前存储空间已满,增加分配 */ { newbase=realloc(L->elem,(L->listsize+LIST_INCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); /* 存储分配失败 */ L->elem=newbase; /* 新基址 */ L->listsize+=LIST_INCREMENT; /* 增加存储容量 */ } q=L->elem+i-1; /* q为插入位置 */ for(p=L->elem+L->length-1;p>=q;--p) /* 插入位置及之后的元素右移 */ *(p+1)=*p; *q=e; /* 插入e */ ++L->length; /* 表长增1 */ return OK;}Status ListDelete(SqList *L,int i,ElemType *e) { /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */ ElemType *p,*q; if(iL->length) /* i值不合法 */ return ERROR; p=L->elem+i-1; /* p为被删除元素的位置 */ *e=*p; /* 被删除元素的值赋给e */ q=L->elem+L->length-1; /* 表尾元素的位置 */ for(++p;plength--; /* 表长减1 */ return OK;}void ListTraverse(SqList L,void(*vi)(ElemType*)){ /* 初始条件：顺序线性表L已存在 */ /* 操作结果：依次对L的每个数据元素调用函数vi() */ /* vi()的形参加'&'，表明可通过调用vi()改变元素的值 */ ElemType *p; int i; p=L.elem; for(i=1;i