順序表
順序表
順序表是在計算機內存中以數組的形式保存的線性表，線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表中的各個元素、使得線性表中在邏輯結構上相鄰的數據元素存儲在相鄰的物理存儲單元中，即通過數據元素物理存儲的相鄰關係來反映數據元素之間邏輯上的相鄰關係，採用順序存儲結構的線性表通常稱為順序表。順序表是將表中的結點依次存放在計算機內存中一組地址連續的存儲單元中。
將表中元素一個接一個的存入一組連續的存儲單元中，這種存儲結構是順序結構。
採用順序存儲結構的線性表簡稱為“順序表”。順序表的存儲特點是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素佔用存儲單元的長度。
順序表的結構定義：
順序表
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 &pre_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 &next_e)
{ // 初始條件：順序線性表L已存在
// 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼，
// 否則操作失敗，next_e無定義
int i=1;
ElemType *p=L.elem;
while(i
{
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<
return OK;
}
基本信息
- 中文名
- 順序表
- 外文名
- 無
- 結構
- 存儲結構
- 實質
- 線性表
- 形式
- 數組
目錄