线性表的顺序存储

一、顺序表

1、顺序存储：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。

2、顺序表：采用顺序存储方法存储的线性表称顺序表。

3、存储地址的计算：

LOC(ai)=LOC(a1)+(i-1)*c 1<=i<=n

这里：LOC(a1)为结点a1的存储起址(基地址），c为每个结点所占存储单元数。

顺序表是一种随机存取结构

顺序表的描述：

typedef  int  datetype;

       #define  maxsize 1024

       typedef struct

       {   datatype data[maxsize];

            int  last;

       } sequenlist; 

说明

(1).datatype是表中的数据类型,依具体情况而定

(2).向量下标可以看作表中结点的相对地址

(3). 顺序表的长度为last+1

(4).结点的引用:定义一个顺序表：sequenlist *L; (*L).data[0]->a1

(*L).data[1]->a2

(*L).data[(*L).last]->an

二、 顺序表上的基本运算（实现）

SETNULL（L）： (*L).last = -1

LENGTH(L): (*L).last+1

GET(L,i): (*L).data[i-1]

LOCATE(L,x)

INSERT(L,x,i)

DELETE(L,i)

顺序表的特点：

用物理位置上的邻接关系表示结点间的逻辑关系

顺序表的优点：

（1）无须增加额外的存储空间表示结点间的逻辑关系。

（2）可以方便地随机存取表中任一结点。

顺序表的缺点：

（1）插入和删除运算不方便，通常须移动大量结点，效率较低。

（2）难以进行连续的存储空间的预分配，尤其是当表变化较大时。