簡介
將表中元素一個接一個的存入一組連續的存儲單元中，這種存儲結構是順序結構。
採用順序存儲結構的線性表簡稱為“ 順序表”。順序表的存儲特點是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素占用存儲單元的長度。
順序表的結構定義：
順序表#define maxlen 50 //定義順序表中元素個數最多有幾個
typedef struct
{
elementtype data[maxlen]; //elementtype是元素的類型 依具體情況而定
int listlen; //便於時刻了解順序表里元素的個數
}seqlist; //順序表的名稱 不妨為seqlist
聲明順序表類型變數：
seqlist L,L1;
如順序表的每個結點占用len個記憶體單元，用location (ki)表示順序表中第i個結點ki所占記憶體空間的第1個單元的地址。則有如下的關係:location (ki+1) = location (ki) +len
location (ki) = location(k1) + (i-1)len
存儲結構要體現數據的邏輯結構，順序表的存儲結構中，記憶體中物理地址相鄰的結點一定具有順序表中的邏輯關係。
基本操作
1.構造一個空的順序線性表
Status InitList(SqList &L) // 算法2.3
{ // 操作結果：構造一個空的順序線性表
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;
}
2.銷毀順序線性表L
Status DestroyList(SqList &L)
{ // 初始條件：順序線性表L已存在。操作結果：銷毀順序線性表L
free(L.elem);
L.elem=NULL;
L.length=0;
L.listsize=0;
return OK;
}
3.將L重置為空表
Status ClearList(SqList &L)
{ // 初始條件：順序線性表L已存在。操作結果：將L重置為空表
L.length=0;
return OK;
}
4.判斷是否為空表
Status ListEmpty(SqList L)
{ // 初始條件：順序線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE
if(L.length==0)
return TRUE;
else
return FALSE;
}
5.返回L中數據元素個數
int ListLength(SqList L)
{ // 初始條件：順序線性表L已存在。操作結果：返回L中數據元素個數
return L.length;
}
6.用e返回L中第i個 數據元素 的值
Status GetElem(SqList L,int i,ElemType &e)
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)
// 操作結果：用e返回L中第i個數據元素的值
if(i<1||i>L.length)
exit(ERROR);
e=*(L.elem+i-1);
return OK;
}
7.返回L中第1個與e滿足關係，不存在，則返回值為0
int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ // 初始條件：順序線性表L已存在，compare()是數據元素判定函式(滿足為1,否則為0)
// 操作結果：返回L中第1個與e滿足關係compare()的數據元素的位序。
// 若這樣的數據元素不存在，則返回值為0。算法2.6
ElemType *p;
int i=1; // i的初值為第1個元素的位序
p=L.elem; // p的初值為第1個元素的存儲位置
while(i<=L.length&&!compare(*p++,e))
++i;
if(i<=L.length)
return i;
else
return 0;
}
8.是L的 數據元素 ，且不是第一個，則用pre_e返回它的前驅
Status PriorElem(SqList L,ElemType cur_e,ElemType ⪯_e)
{ // 初始條件：順序線性表L已存在
// 操作結果：若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅，
// 否則操作失敗，pre_e無定義
int i=2;
ElemType *p=L.elem+1;
while(i<=L.length&&*p!=cur_e)
{
p++;
i++;
}
if(i>L.length)
return INFEASIBLE;
else
{
pre_e=*--p;
return OK;
}
}
9.cur_e是L的 數據元素 ，且不是最後一個，用next_e返回它的後繼
Status NextElem(SqList L,ElemType cur_e,ElemType ≠xt_e)
{ // 初始條件：順序線性表L已存在
// 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼，
// 否則操作失敗，next_e無定義
int i=1;
ElemType *p=L.elem;
while(i<L.length&&*p!=cur_e)
{
i++;
p++;
}
if(i==L.length)
return INFEASIBLE;
else
{
next_e=*++p;
return OK;
}
}
10.在L中第i個位置之前插入新的 數據元素 e
Status ListInsert(SqList &L,int i,ElemType e) // 算法2.4
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)+1
// 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1
ElemType *newbase,*q,*p;
if(i<1||i>L.length+1) // i值不合法
return ERROR;
if(L.length>=L.listsize) // 當前存儲空間已滿,增加分配
{
if(!(newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))))
exit(OVERFLOW); // 存儲分配失敗
L.elem=newbase; // 新基址
L.listsize+=LISTINCREMENT; // 增加存儲容量
}
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;
}
11.刪除L的第i個 數據元素 ，並用e返回其值
Status ListDelete(SqList &L,int i,ElemType &e) // 算法2.5
{ // 初始條件：順序線性表L已存在，1≤i≤ListLength(L)
// 操作結果：刪除L的第i個數據元素，並用e返回其值，L的長度減1
ElemType *p,*q;
if(i<1||i>L.length) // i值不合法
return ERROR;
p=L.elem+i-1; // p為被刪除元素的位置
e=*p; // 被刪除元素的值賦給e
q=L.elem+L.length-1; // 表尾元素的位置
for(++p;p<=q;++p) // 被刪除元素之後的元素左移
*(p-1)=*p;
L.length--; // 表長減1
return OK;
}
12.依次對L的每個 數據元素 調用函式vi()。一旦vi()失敗，則操作失敗
Status ListTraverse(SqList L,void(*vi)(ElemType&))
{ // 初始條件：順序線性表L已存在
// 操作結果：依次對L的每個數據元素調用函式vi()。一旦vi()失敗，則操作失敗
// vi()的形參加'&'，表明可通過調用vi()改變元素的值
ElemType *p;
int i;
p=L.elem;
for(i=1;i<=L.length;i++)
vi(*p++);
cout<<endl;
return OK;
}
