#### 線性表的定義和特點
##### 定義：
##### 有n(n≥0)個數據特性相同的元素構成的有序序列稱為線性表。
##### 當個數n(n≥0)定于為線性表的長度，n=0時成為空表。
##### 特點：
1.
只有一個首結點和尾結點；
1.
除首尾結點外，其他結點只有一個直接前驅和一個直接后繼。
#### 分析26個英文字母組成的英文表（A,B,C,D,…..,Z）數據元素都是字母，元素間關系是線性
##### 抽象數據類型的定義為:
~~~
ADT List
{
數據對象：D={ai|ai∈ElemSet，i1,2,3...n,n≥0}
數據關系：R={<ai-1,ai|ai-1,ai∈D,i=2,...,n}
線性表的基本操作
1.初始化線性表 L
2.銷毀線性表L
3.清空線性表L
4.求線性表L的長度
5.判斷線性表L是否為空
6.獲取線性表L中的某個數據元素內容
7.檢索值為e的數據元素
8.在線性表L中插入一個數據元素
9.刪除線性表L中第i個數據元素
}ADT List
~~~
### 線性表的順序表示和實現
線性表的順序表示又稱為順序存儲結構或順序映像。
##### 順序存儲定義：把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元中的存儲結構。（邏輯上相鄰，物理上也相鄰）
##### 順序存儲方法：用一組地址連續的存儲單元依次存儲線性表的元素，可通過數組V[n]來實現。
### 順序表的類型定義
~~~
#define MAXSIZE 100//最大長度
typedef struct{
ElemType *elem；//指向順序表的基地址
int length；//順序表的當前長度
}SqList；//順序表的類型定義
~~~
如果你的C和C++基礎不夠扎實，建議看下我這篇博客
[C、C++函數傳參疑難解析](http://blog.csdn.net/it_ds/article/details/50510962)
#### 初始化線性表L（參數用引用）
~~~
Status InitList_Sq（SqList &L）
{ //構造一個空的順序表L
L.elem=new ElemTyPe[MAXSIZE];
//為順序表分配空間
//存儲分配失敗
if(!L.elem)exit(OVERFLOW);
//空表長度為0
L.length=0;
return OK;
}
~~~
#### 初始化線性表L（參數用指針）
~~~
"Status InitList_Sq（SqList *L）
{
L->elem=new ElemType[MAXSIZE];
if(!L->elem)exit(OVERFLOW);
L->length=0;
return OK;
}
~~~
#### 銷毀線性表L
~~~
void DestroyList(Sqlist &L)
{
if(L.elem)
delete[]L.elem;//釋放存儲空間
}
~~~
#### 清空線性表L
~~~
void ClearList(SqList &L)
{
L.length=0;//將線性表的長度置為0
}
~~~
#### 求線性表L的長度
~~~
int GetLength（SqList L）
{
return（L.length);
}
~~~
##### 判斷線性表L是否為空
~~~
int IsEmpty(SqList L)
{
if(L.length==0)
return 1;
else
return 0;
}
~~~
#### 6.獲取線性表L中的某個數據元素的內容
~~~
根據指定位置，獲取相應位置數據元素的內容
int GetElem(SqList L,int i,ElemType &e)
{ //判斷i值是否合理，若不合理，返回ERROR
if(i<1||i>L.length)
return ERROR;
e=L.elem[i-1];//第i-1的單元存儲著第i個數據
return OK;
}
~~~
#### 7.在線性表L中查找值為e的數據元素
~~~
int LocateELem(SqList L,ElemType e)
{
for(i=0;i<L.length;i++)
if(L.elem[i]==e)
return i+1;
return 0;
}
~~~
##### 8.在線性表L中的第i個數據元素之前插入數據元素e
~~~
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{ //值不合法
if(i<1||i>L.length+1)return ERROR;
//當前存儲空間已滿
if(L.length==MAXSIZE)return ERROR;
for(j=L.length-1;j>i-1;j--)
//插入位置及以后的元素后移
//將新元素e放入第i個位置
L.elem[j+1]=L.elem[j];
L.elem[i-1]=e;
++L.length;//表長增加1
return OK;
}
~~~
#### 9.將線性表L中第i個數據元素刪除
~~~
Status ListDelete_Sq(SqList &L,int i,ElemType &e)
{
if((i<1)||(i>L.length))return ERROR;//i值不合法
e=L.elem[i-1];//將欲刪除的元素保留在e中
for(j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j];//被刪除元素之后的元素前移
--L.length;//表長減1
return OK;
}
~~~
### 順序存儲結構的特點
1. 利用數據元素的存儲位置表示線性表中相鄰數據元素之間的前后關系，即線性表的邏輯結構與存儲結構一致
1. 在訪問線性表時，可以快速地計算出任何一個數據元素的存儲地址。因此可以粗略地認為，訪問每個元素所花時間相等。
### 順序表的優缺點
#### 優點：
1. 存儲密度大（結點本身所占存儲量/結點結構所占存儲量）
1. 可以隨機存取表中任一元素
#### 缺點：
1. 在插入、刪除某一元素時，需要移動大量元素浪費存儲空間
1. 屬于靜態存儲形式，數據元素的個數不能自由擴充
