一、定義：
線性表是具有像線一樣的性質(zhì)的表，是一個序列，元素間是有順序的，如果存在多個元素的話，第一個元素?zé)o前驅(qū)，后一個元素?zé)o后繼，其他每個元素都有且只有一個前驅(qū)和后繼，線性表強調(diào)有限性。
線性表的元素個數(shù)n（n>=0）定義為線性表的長度，當(dāng)n=0時，成為空表。
非空表中每個元素都有一個確定的位置，如果a1是第一個元素，a7是第七個元素，1成為a1元素在線性表中的位序。
線性表最典型的例子就是星座和生肖了。星座中都是白羊座第一，雙魚座收尾，當(dāng)中的每個星座有且僅有一個前驅(qū)和后繼，而且個數(shù)是有限的12個；生肖中以鼠開頭以豬結(jié)尾。每個星座和生肖的位置（位序）是固定的，白羊座和鼠是1，金牛座和牛是2......
要成為線性表中的元素比較有相同的數(shù)據(jù)類型，不同的數(shù)據(jù)類型是不能組成線性表的。人和衣服就不能組成線性表。
復(fù)雜的線性表允許每個元素有若干個數(shù)據(jù)項組成，例如按照學(xué)號排序的學(xué)生組成了一個線性表，每個學(xué)生都可以有姓名，性別，出生年月等多個數(shù)據(jù)項。
二、線性表的抽象數(shù)據(jù)類型
2.1什么是線性表
線性表的數(shù)據(jù)對象元素為{a1,a2,a3,......,an}，每個元素的類型均為DataType。其中，除了第一個元素a1外，每個元素都有前驅(qū)；除了最后一個元素an外，每個元素都有后繼。數(shù)據(jù)元素間的關(guān)系是一對一的關(guān)系。
幼兒園的小朋友按照固定的順序排隊，并且長期使用這個順序，每個小朋友就對應(yīng)一個元素，所以小朋友組成的順序隊列就叫線性表。
2.2線性表的操作
- InitList（*L）：
初始化操作，建立一個空的線性表。
老師讓小朋友按照一定順序排隊的過程就是線性表的創(chuàng)建與初始化的過程。
- ListEmpty（L）：
若線性表為空，返回true，否則返回false。
- ClearList（L）：
將線性表清空。
沒經(jīng)驗的小朋友排好隊后，老師發(fā)現(xiàn)有高有矮很不整齊，隊伍很難看，于是讓小朋友解散重新排列，這就是一個線性表重置為空的操作。
- GetElem（L,i,*e）:
將線性表L中的第i個元素值返回給e。
- LocateElem（L,e）：
在線性表中查找與e相等的元素，如果查找成功返回該元素的序號，查找失敗返回0；
- ListInsert（*L,i,e）:
在線性表第i個位置插入新元素e
- ListDelete（*L,i,e）:
刪除線性表第i個位置，并用e返回
- ListLength（L）:
獲取線性表元素個數(shù)
使用以上幾個基本操作實現(xiàn)求 線性表A和線性表B的并集，思路大致為，查找B中的每個元素判斷是否在A中，如果不在則插入。
void unionL(List *La,List Lb){
int La_length,Lb_length,i;
//聲明相同的數(shù)據(jù)元素e
ElemType e;
La_length = ListLength(La);
Lb_length = ListLength(Lb);
//遍歷Lb所以元素，在La中查找，沒有就插入
for(i=1; i<=Lb_length; i++){
//取出Lb中第i個元素給e
GetElem(Lb,i,e);
//Lb中如果沒找到e就插入
if(!LocateElem(La,e)){
ListInsert(La, ++La_length, e);
}
}
}
三、線性表的物理結(jié)構(gòu)---順序存儲結(jié)構(gòu)
3.1 定義
線性表的順序存儲結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。
3.2存儲方式
線性表的順序存儲結(jié)構(gòu)，就是在內(nèi)存中找了快地方，通過占位的形式，把一定內(nèi)存空間給占了，然后把相同數(shù)據(jù)類型的數(shù)據(jù)元素一次存放在這塊空地中。想象下C的一維數(shù)組，里面的每個元素數(shù)據(jù)類型都相同，下標(biāo)0存放線性數(shù)組第一個元素，接著把線性表相鄰 元素存儲在數(shù)組匯總相鄰的位置。
如果線性表的個數(shù)小于它的最大存儲容量，這個時候是可以往線性表里面添加元素的，隨著數(shù)據(jù)的插入，線性表的長度慢慢增大，但是不能超過它的最大存儲容量。
順序存儲的結(jié)構(gòu)代碼：
#define MAXSIZE 20
typedef struct
{
ElemType data[MAXSIZE]; //存儲數(shù)據(jù)元素的數(shù)組，最大容量為MAXSIZE
int length; //當(dāng)前線性表的長度
}
描述順序存儲需要三個屬性：
- 存儲空間的起始位置：數(shù)組data的存儲位置就是存儲空間的存儲位置。
- 線性表的最大容量：數(shù)組data的長度MAXSIZE。
- 線性表的當(dāng)前長度：length。
NOTE：兩個概念的比較：數(shù)組的長度和線性表的長度。數(shù)組的長度是指存放線性表的存儲空間的長度，存儲分配后這個量一般是不變的（高級語言中可以通過編程手動實現(xiàn)動態(tài)分配數(shù)組長度，不過這個會帶來性能損耗）；線性表的長度是線性表中的數(shù)據(jù)元素的個數(shù)，隨著線性表的插入和刪除而改變。任何時刻，線性表長度應(yīng)小于等于數(shù)組長度
3.3地址的計算方法
地址：存儲器中的每個存儲單元都有自己的編碼，這個編碼成為地址。
使用LOC表示獲取存儲位置的函數(shù)，每個元素占據(jù)的存儲單元個數(shù)為c，那么第i個元素與第i+1個元素的地址關(guān)系可以表示為：
LOC(i+1) = LOC(i) + c
相應(yīng)的，我們可以很快得出第i個元素與第一個元素的地址關(guān)系為：
LOC(i) = LOC(1) + (i-1)*c
通過這個公式，我們可以隨時算出線性表中任一一個元素的位置，而且時間是固定的，這個對于計算機(jī)來說也是一樣，每次都用同樣的時間就能取出任一位置的元素，同時這個時間是一個常數(shù)，從時間復(fù)雜度的角度來說，它的存取性能為O(1)，我們把具有這一特點的存儲結(jié)構(gòu)稱之為隨機(jī)存取結(jié)構(gòu)。
3.4 線性表元素的獲取、插入、刪除
- 獲取元素：
這個和獲取數(shù)組中的某個位置的元素的原理相似，先判斷數(shù)組長度是否為0，該位置是否合法，然后取出元素，這里需要注意的是線性表的下標(biāo)起始是從1開始，因此第i個元素對應(yīng)數(shù)組中的下標(biāo)為i-1。
status GetElem(sqList L, int i,ElemType *e){
/*判斷i是否合法*/
if(L.length == 0 || i < 1 || i > L.length) return ERROR;
*e = L.data[i-1];
return OK;
}
- 插入元素
步驟：
1、判斷插入的位置是否合法。
2、找到合適的位置后該位置開始到最后一個元素，每個元素都向后移動一個位置，
3、插入元素
4、線性表的長度增加1
用代碼實現(xiàn)為：
status ListInsert(Sqlist L, int i, ElemType e){
int k;
/*線性表已滿*/
if (L.length == MAXSIZE) return ERROR;
/*插入位置不合法*/
if (i < 1 || i > L.length+1) return ERROR;
//從后向前遍歷，所以元素向后移動一個位置
if (i <= L.length) {
for(k = L.length; k >= i；k--){
L.data[k+1] = L.data[k];
}
}
L.data[i] = e;
L.length ++;
return OK;
}
- 刪除元素
步驟：
1、判斷要刪除位置是否合法
2、刪除該元素，用e返回其值
3、遍歷線性表，該元素以后的每個元素向前移動一個位置
4、線性表的長度-1
status (SqList L, int i, ElemType *e){
int k;
if (L.length == 0 || i < 1 || i > L.length) return ERROR;
/*取出待刪除元素，用e返回*/
*e = L.data[i];
/*i以后的每個元素向前移動一個位置*/
for(k = i; k < L.length; k --){
L.data[k-1] = L.data[k];
}
/*線程表的長度-1*/
L.length--;
return OK;
}
-
順序存儲的優(yōu)缺點
優(yōu)點：
1、無需為表中元素之間的邏輯關(guān)系而增加額外的存儲空間
2、可以快速地存取表中任一位置的元素缺點：
1、插入和刪除操作需要移動大量元素。
2、當(dāng)線性表長度變化較大時，難以確定存儲空間的容量。
3、容易造成存儲空間的碎片。
