一、線性表的定義
1、線性結構的特點
在資料元素的非空有限集中，（1）存在唯一的一個被稱作“第一個”的資料元素；（2）存在惟一的一個被稱作“最後一個”的資料元素；（3）除第一個之外，集合中的每個資料元素均隻有一個前驅；（4）出最後一個之外，集合中每個資料元素均隻有一個後繼。
2、線性表
一個線性表n個資料元素（或結點）的有序序列：
a0，a1，a2，•••，an-1
其中a0是開始結點，an-1是終端結點，ai是ai+1的前驅結點，ai+1是ai的後繼結點。一個資料元素可以由若幹個資料項組成。在這種情況下，常把資料元素稱為記錄。含有大量記錄的線性表稱為檔案。
3、線性表的常用基本操作
ElemType GetElement(Sqlist L,int i,EleType &e) //用e傳回L中第i個資料元素的值
status ListInsert(Sqlist &L,int i,EleType e) //在L中第i個位置之前插入新的資料元素e，L長度加1
status ListDelete(Sqlist &L,int i,EleType &e); //删除L的第i個資料元素，并用e傳回s其值，L長度減1
注：
- 以上操作均限定1<=i<=ListLength(L)
- &這個符号并不是C語言中的取位址操作，而是為了便于C語言的算法描述，除了值調用以外，增添了C++語言的引用調用的參數傳遞方式。
二、線性表的順序表示和實作
1、線性表的順序表示
指的是用一組位址連續的存儲單元依次存儲線性表的資料元素。這樣，線性表中第0個元素的存儲位置就是指定的存儲位置，第i個元素(1<=i<=n-1)的存儲位置緊接在第i-1個元素的存儲位置的後面。順序存儲的線性表可簡稱為順序表。線性表的順序存儲示意圖見下圖1.1
（圖1.1 線性表的順序存儲示意圖）
假設線性表的元素類型為ElemType,那麼每個元素占用的存儲空間大小即為sizeof(ElemType)，圖中令l = sizeof(ElemType)。是以我們可以得出，在順序存儲方式下，隻要我們知道線性表的首址以及資料元素的為序以及大小，我們就能夠得到這個資料元素的存儲位址，是以線性表的順序存儲是可以實作随機存取的。
maxlen定義為一個整型常量，為線性表中的最大元素數。如果線性表最多隻有100個元素，可定義如下：
#define maxlen 100
typedef struct{
ElemType element[maxlen];//存放資料元素
int len; // 存放線性表的長度
}Sqlist;
2、順序表基本操作的實作
（1）ElemType GetElement(Sqlist L,int i)：傳回L中第i個資料元素的值
ElemType GetElem(Sqlist L,int i)
{
if(i<0 || i>L.len-1)
Error("順序表下标通路越界");
else
return(L.element[i]);
}
（2）status ListInsert(Sqlist &L,int i,EleType e)：在L中第i個位置之前插入新的資料元素e，L長度加1
<pre name="code" class="cpp"> status ListInsert(Sqlist &L,int i,EleType e)
{
int j;
if(i<0 || i>L.len-1) //順序表下界通路越界
return ERROR;
else
{
for(j=L.len-1;j>=i;j--) //結點後移，為插入騰出位置
{
L.data[j+1] = L.data[j];
}
L.data[i] = e; //插入e
L.len++;
return OK; //成功插入
}
}
說明：順序表進行插入時要移動i後的所有元素，是以，插入效率不高。
（3）status ListDelete(Sqlist &L,int i,EleType &e) ：删除L的第i個資料元素，并用e傳回s其值，L長度減1
status ListDelete(Sqlist &L,int i,EleType &e)
{
int j;
if(i<0 || i>L.len-1) <span style="font-family: Verdana, Arial, Helvetica, sans-serif;">//順序表下界通路越界</span>
return ERROR;
else
{
e = L.data[i];
for(j=i;j<L.len-1;j++) //結點依次前挪
L.data[j] = L.data[j+1];
L.len--;
return OK;
}
}
說明：對順序表進行删除時要将删除位置後的所有元素前移，是以删除的效率也不高。
3、線性表的鍊式存儲及其實作
鍊式存儲就是使用連結清單實作的存儲結構，它不需要一組連續的存儲單元，而是可以使用一組任意的，甚至是在存儲空間中零散分布的存儲單元存放線性表的資料，進而解決了順序存儲線性表需要大塊連續存儲單元的缺點。
（1）線性連結清單
為了表示每個資料元素與其直接後繼元素之間的邏輯關系，我們在每個節點中除包含有資料域外，還設定了一個指針域，用來指向其後續結點。這樣構成的連結清單稱為線性連結清單或者單連結清單。
單連結清單分為帶頭節點和不帶頭節點兩種。單連結清單帶頭節點好處有二：第一，有頭結點後，插入和删除資料元素的算法統一了，不再需要判斷是否在第一個元素之前插入和删除第一個元素；第二，不論連結清單是否為空，連結清單指針不變。是以，為了簡便，以下讨論的都是帶頭節點的單連結清單。如果為空表，那麼頭結點的指針域為空（NULL）。
頭指針是指訓示連結清單中第一個結點存儲位置的指針。頭結點是指在單連結清單第一個結點前所附設的一個結點，這個結點的指針域存儲指向第一個結點（包括頭結點）的 指針。圖1.2中，L為頭指針，帶陰影的結點為頭結點。
由以上描述可知，如果想知道連結清單中某一個結點的資訊，就必須知道這個結點的直接前驅結點的資訊，因為此節點的存儲位置儲存在其直接前驅的位址域裡。是以，連結清單是無法實作随機存取的。
下面定義線性連結清單的存儲結構：
typedef struct LNode
{
ElemType data; //資料域
struct LNode * next; //指針域
}LNode, *LinkList;
（2）線性連結清單基本操作的實作
1）ElemType GetElem(Linklist L, int i)：用e傳回L中第i個資料元素的值。
ElemType GetElem(Linklist L, int i)
{
//L為帶頭節點的單連結清單的頭指針
p = L->next; //讓p指向L中的第一個元素
j = 1 ; //j為計數器，
while(p&&j<i){
//順指針往下找，直到p指向第i個元素或者p為空（即下标越界）
p = p->next;
j++;
}
if(!p || j>i)
error(0);
e = p->data;
return e;
}
說明：在給出線性表某一節點的位序後，我們必須從單連結清單的頭結點開始，将位置标志指針p一直往下移動，如果我們需要的是線性表的最後一個元素，那麼這個指針就将從連結清單頭移動到連結清單尾，是以用單連結清單存儲的線性表在對結點進行随機查詢上效率是非常低的。
2）status ListInsert(LinkList &L,int i,ElemType e)：在L中第i個位置之前插入新的資料元素e
假設我們要線上性表的兩個元素a和b之間插入一個元素x,指針的指向情況如圖1.3所示。圖1.3：單連結清單插入結點的指針變化情況：
首先要生成一個資料域是x的結點，然後使得x的指針域指向b結點，最後修改a結點的指針域，使其指向x結點。注意：這個步驟是不能調換順序的！簡單描述如下：
s->next = p->next; p->next = s;
完整算法描述如下：
status ListInsert(LinkLiST &l,int i,ElemType e)
{
//在帶頭結點的單連結清單L中第i個位置之前插入元素e
p = L;
j = 0;
while(p&&j<i-1){ //尋找第i-1個結點
p = p->next;
j++;
}
if(!p || j>i-1)
return ERROR;
s = (LinkList)malloc(sizeof(LNode));//生存新節點
s->data = e; //插入結點
s->next = p->next;
p->next = s;
return OK;
}
說明：單連結清單中插入資料時，不再需要像順序表一樣大量移動大量的結點已完成結點的插入，而隻需要簡單的修改幾個指針即可，插入效率提高。并且還能很友善的實作線性表長度的動态變化，更加靈活的使用計算機記憶體資源。
3) status ListDelete(LinkList &L,int i,ElemType &e)：删除L的第i個資料元素，并用e傳回其值。
如下圖所示， 為了删除單連結清單中的b結點，僅需修改結點a的指針域，使其指向b的直接後繼結點c。
其修改指針的語句如下：
p->next = p->next->next;
完整算法描述如下：
status ListDelete(LinkList &L,int i,ElemType &e)
{
//在帶有頭結點的單連結清單中删除第i個元素
p = L;
j = 0;
while(p&&j<i-1){ //順着指針一直向後尋找插入位置
p = p->next;
j++;
}
if(!(p->next)||j>i-1) //删除位置不正确
return ERROR;
q = p->next; //因為考慮到要回收記憶體，是以用q指針儲存需要删除結點的位址
p->next = q->next;
e = q->data;
free(q); //回收記憶體
return OK;
}
說明：由以上算法我們可以知道，在已知連結清單中要删除的結點的确切位置的情況下，在單連結清單中删除一個結點時，僅需修改相關的指針，而不需要移動元素，删除的效率高。
（3）靜态連結清單
在有的情況下，也可借用一維數組來描述線性連結清單，其存儲結構如下：
#define MAX 100
typedef struct{
ElemType data;
int cur;
}SLinkList[MAX];
這種描述方法使得我們在沒有設定指針類型的某些進階程式設計語言中可以使用連結清單結構，如java中。cur分量存儲的不再是連結清單中的指針域，而是存儲其下一結點在一維數組中的位序。為了和指針描述的線性連結清單相差別，我們就将這種用數組描述的連結清單叫做靜态連結清單。如下圖1.5。
靜态連結清單以cur==0作為其結束的标志。總的來說，靜态連結清單沒有單連結清單使用起來靈活友善，但是在不支援指針的進階語言中，這又是一種非常巧妙的設計方法。
（4）循環連結清單
循環連結清單是另外一種形式的鍊式存儲結構，其中比較常用的是循環單連結清單和循環雙連結清單。
1）循環單連結清單
循環單連結清單的特點是表中最後一個結點的指針不再為空，而是指向該連結清單的表頭結點，将整個連結清單連結成一個環。這樣，由此表中的任一階段出發均可以通路到連結清單中的其他結點。
循環單連結清單的基本操作的實作方法與單連結清單基本相同，隻是在對表尾判斷的條件上有所改變。例如，在一個頭指針為h（此頭指針指向頭結點）的循環單連結清單中，判斷表空的條件不再是h->next == null，而是h->next == h；判斷表尾結點的條件是p->next == h。 如下圖1.6所示。
2）循環雙連結清單
以上讨論的鍊式存儲結構的結點中隻有一個訓示直接後繼結點的指針，這就造成了我們隻有順着指針往後通路其他結點。如果要通路某個節點的前驅，則必須從頭指針開始查找。換句話說，就是在以上所有的鍊式存儲結構中，找後繼容易，找前驅麻煩。是以，為了克服這個缺點，我們引入了循環雙向連結清單。
循環連結清單存儲結構：
typedef struct DulNode
{
ElemType data;
struct DulNode *prior;
struct DulNode *next;
}DulNode,*DulLinkList;
在雙向連結清單中，若p為指向其中某一結點的指針，則顯然有：
p->next->prior = p->prior->next = p;
如圖1.6.1：
圖1.6.1 雙向連結清單結點示意圖
循環雙向連結清單存儲示意圖如下所示：
（5）循環雙連結清單基本操作實作
1）ElemType GetElem(DulLinkList L,int i)：用e傳回L中第i個資料元素的值。
ElemType GetElem(DulLink L,int i)
{
<span style="white-space:pre"> </span>j = 0;
<span style="white-space:pre"> </span>q = L->next;
<span style="white-space:pre"> </span>while(j<i&&q!=L){//查找第i個結點
<span style="white-space:pre"> </span> q = q->next;
<span style="white-space:pre"> </span> j++
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>if(q!=L){ /傳回第i個元素值
<span style="white-space:pre"> </span> e = q->data;
<span style="white-space:pre"> </span> return e;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>else{
<span style="white-space:pre"> </span> error("位置參數i不正确");
return NULL;
<span style="white-space:pre"> </span>}
}
說明：雙向連結清單在的GetElem操作與單連結清單沒有很多差別，但是在通路結點直接前驅方面是非常友善的，隻要簡單的順着prior指針往前尋找即可。
2）status ListInsert(DulLinkList &L,int i,ElemType e)：在L中第i個位置之前插入新的資料元素e。插入時指針變化情況見下圖1.8.
status ListInsert(DulLinkList & L,int i,ElemTYpe e)
{
if(!(p = GetElemP_Dul(L,i)))//在L中确定第i個元素的位置指針p
return ERROR; //p=null，即第i個元素不存在，位置參數i錯誤
if(!(s = (DulLinkList)malloc(sizeof(DulNode))))
return ERROR; //記憶體配置設定不成功
s->data = e;
s->prior = p->prior; //(1)
p->prior->next = s; //(2)
s->next = p; //(3)
p->prior = s; //(4)
return OK;
}
說明：插入結點後指針的改變步驟見算法和圖1.8的對應标号。
3）status ListDelete(DulLinkList & L,int i,ElemType &e)：删除L的第i個資料元素，并用e傳回其值。删除時指針變化情況如圖1.9所示：
status ListDelete(DulLinkList &L,int i,ElemType &e)
{
if(!(p = GetElem_Dul(L,i)))//在L中确定第i個元素的位置指針p
return ERROR;
e = p->data;
p->prior->next = p->next; //(1)
p->next->prior = p->prior; //(2)
free(p); //記憶體回收
return OK;
}
說明：删除結點後指針的變化步驟見算法和圖1.9的對應标号。
（線性表的兩種存儲方式結構及其操作的實作整理完畢！）