線性表
定義：
線性表：是一種典型的線性結(jié)構(gòu)，由零個(gè)或多個(gè)數(shù)據(jù)元素組成的
有限數(shù)列
- 首先他是一個(gè)序列越锈，也就是說(shuō)在相互數(shù)據(jù)元素之間是有順序的
- 其次線性表強(qiáng)調(diào)的是有限個(gè)數(shù)據(jù)元素
- 除了開頭元素只有一個(gè)后繼扛施，結(jié)尾元素只有一個(gè)前驅(qū)之外酬荞，其他元素有且僅有一個(gè)后繼元素和一個(gè)前驅(qū)元素
若把線性表表示為a1,a2,a3...ai,ai+1...an那婉，這里a1為開始
結(jié)點(diǎn)塑荒，an為終端結(jié)點(diǎn)，ai-1是ai的前驅(qū)元素玩裙，ai+1是ai的后繼元素兼贸。
我們把線性表中的元素的個(gè)數(shù)n定義為線性表的長(zhǎng)度段直，當(dāng)n = 0時(shí)稱為
空表
線性表的基本操作
在線性表這種邏輯結(jié)構(gòu)上定義了八種基本的運(yùn)算
- InitList(*L): 對(duì)表L初始化，建立一個(gè)空的線性表
- ListEmpty(L): 判斷線性表是否為空表
- ClearList(*L): 將線性表清空
- GetElem(L, i, *e): 將線性表L中的第i個(gè)位置的元素值返回給e
- LocateElem(L, e): 在線性表中查找一個(gè)值為e的元素溶诞，若找到則返回該元素的位置鸯檬，否則返回一個(gè)特殊值表示查找失敗
- ListInsert(*L, i, e): 在線性表L中第i個(gè)位置插入一個(gè)元素e
- ListDelete(*L, i, *e): 刪除線性表L中第i個(gè)位置元素，并用e返回其值
- ListLength(L): 表L的長(zhǎng)度
由于存儲(chǔ)方式的不同螺垢，這幾種基本運(yùn)算的實(shí)現(xiàn)方式亦不同喧务，線性表主要
有兩種存儲(chǔ)方式：
順序存儲(chǔ)結(jié)構(gòu)
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
線性表的順序存儲(chǔ)結(jié)構(gòu)
線性表的順序存儲(chǔ)結(jié)構(gòu)指的是用一段地址連續(xù)的存儲(chǔ)單元以此存儲(chǔ)線性表的數(shù)據(jù)元素。
所以邏輯上相鄰的數(shù)據(jù)元素其物理存儲(chǔ)位置必須緊鄰
線性表順序存儲(chǔ)結(jié)構(gòu)的類型定義：
#define MAXSIZE 20 //線性表的最大容量
typedef int ElemType; //線性表的數(shù)據(jù)類型
typedef struct
{
ElemType data[MAXSIZE];
int length; //線性表的當(dāng)前長(zhǎng)度
}SqList;
線性表順序存儲(chǔ)結(jié)構(gòu)的具體操作：
//狀態(tài)碼定義
#define OK 1
#define ERROR 0
typedef int Status;
//初始化順序線性表
Status InitList(SqList *L)
{
L->length = 0;
return OK;
}
//判斷順序線性表是否為空表
int ListEmpty(SqList L)
{
if(L.length)
return 0;
return 1;
}
//清空線性表
Status ClearList(SqList *L)
{
L->length = 0;
return OK;
}
//GetElem的具體操作
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length == 0 || i<1 || i>L.length)
return ERROR;
else *e = L.data[i];
return OK;
}
//LocateElem操作
int LocateElem(SqList L,ElemType e)
{
int i;
for(i=1;i<=L.length;i++)
{
if(L.data[i]==e)
return i;
}
return ERROR;
}
//ListInsert操作
Status ListInsert(SqList *L,int i,ElemType e)
{
if(L->length == MAXSIZE-1)
{
//順序線性表已經(jīng)滿了
return ERROR;
}
if(i<1 || i>L->length+1)
{
//當(dāng)插入的位置不合理時(shí)
return ERROR;
}
if(i<=L->length) //當(dāng)插入的位置不是表尾時(shí)
{
//所有元素向后移一位
int k;
for(k=L->length;k>=i;k--)
L->data[k+1]=L->data[k];
}
L->data[i]=e;
L->length++;
return OK;
}
//ListDelete操作
Status ListDelete(SqList *L, int i, ElemType *e)
{
int k;
//判斷線性表是否為空表
if(L->length == 0)
return ERROR;
//判斷刪除的元素位置是否異常
if(i<1 || i>L->length)
return ERROR;
//返回刪除的值
*e=L->data[i];
for(k=i;k<L->length;k++)
L->data[k]=L->data[k+1];
L->length--;
return OK;
}
//ListLength操作
int ListLenght(SqList L)
{
return L.length;
}
線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn):
優(yōu)點(diǎn)：
- 無(wú)需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間
- 可以快速的存取表中任意位置的元素
缺點(diǎn)
- 插入和刪除操作需要移動(dòng)大量元素（O（n））
- 線性表的長(zhǎng)度難以確定
- 容易造成存儲(chǔ)空間的“碎片”枉圃，因?yàn)樯暾?qǐng)空間時(shí)功茴，是成塊成塊的，所以塊與塊之間肯能會(huì)存在碎片
