2.2线性表的顺序存储结构2.2.1顺序表结构线性表的顺序存储结构.也称为顺序表。其存储方式为：在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推
2.2线性表的顺序存储结构 2.2.1 顺序表结构 线性表的顺序存储结构,也称为顺序表。其存储方式为： 在内存中开辟一片连续存储空间，但该连续存储空间 的大小要大于或等于顺序表的长度，然后让线性表中 第一个元素存放在连续存储空间第一个位置，第二个 元素紧跟着第一个之后，其余依此类推
假设线性表中元素为（aj，a2，……,a），设第一个元素a,的内存地址为LOC(a）（在图2-2中表示为b），而每个元素在计算机内占d个存贮单元，则第i个元素a的地址为LOC(a,)-LOC(a,)+(i-1)×d (其中1<i<n)于是可用C语言描述为//maxlen表示线性表允#define maxsize maxlen;许的最大长度typedef struct sequenlist//表示线性表（aj，a2’..,anelemtype a[maxsize];int len,/len表示线性表的实际长度fSqList;
假设线性表中元素为（a1，a2，.,an），设第一个元 素a1的内存地址为LOC(a1 )（在图2-2中表示为b），而 每个元素在计算机内占d个存贮单元,则第i个元素ai的 地址为LOC(ai )=LOC(a1 )+(i-1)×d (其中1≤i≤n) 于是可用C语言描述为: #define maxsize maxlen； //maxlen表示线性表允 许的最大长度 typedef struct sequenlist { elemtype a[maxsize]; //表示线性表（a1，a2，.,an） int len; //len表示线性表的实际长度 }SqList；
位置序号存储地址内存排列0Xb1ai2b+da21b+(i-1) X dainanb+(n-1) Xdmaxlen-1图2-2顺序存储结构示意图
存储地址 内存排列 位置序号 a1 a2 . ai . an . 0 1 2 . i . n . maxlen-1 b b+d . b+(i-1)×d „ b+(n-1)×d 图 2-2 顺序存储结构示意图
2.2.2顺序表运算1．求顺序表的长度length(L)int length(SqList L)return L.len;7该算法的语句频度为1，时间复杂度为0(1)
2.2.2 顺序表运算 1．求顺序表的长度length(L) int length(SqList L) { return L.len; } 该算法的语句频度为1，时间复杂度为0(1)
2． 插入运算 ListInsert(&L,x,i)void Listlnsert(SqList &L,elemtype x,int i)( int j;if(L.len>=maxsize-1)printf(overflow");else if ((i<1)(i>L.len+ 1)printf(position is not correct!");else ( for(i-L.len;j>=i;j--)1元素后移L.a[j+1]-L.a[i];//插入元素L.a[i]=x;L.len++;/表长度增加1
2．插入运算 ListInsert( &L,x,i) void ListInsert(SqList &L,elemtype x,int i) { int j; if(L.len>=maxsize-1) printf(“overflow”); else if ((i<1)||(i>L.len+1) printf(“position is not correct!”); else { for(j=L.len;j>=i;j-) L.a[j+1]=L.a[j]; //元素后移 L.a[i]=x; //插入元素 L.len++; //表长度增加1 }}