> 上一篇博客學習了順序表，最后也說明了順序表屬于靜態存儲，數據元素的個數不能自由的擴充。為了解決這個問題我們引入了鏈表
### 鏈表存儲結構
結點在存儲器中的位置是任意的，即邏輯上相鄰的數據元素在物理上不一定相鄰，因此線性表的鏈式表示又稱為非順序映像或鏈式映像。
### 各個結點有兩個域組成：
* 數據域:存儲元素數值數據
* 指針域：存儲直接后繼結點的存儲位置
### 名詞解析
1. 結點：數據元素的存儲映像。有數據域和指針域兩部分組成。
2. 鏈表：n個結點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像，稱為線性表的鏈式存儲結構
3. 單鏈表、雙鏈表、循環鏈表：
* 結點只有一個指針域的鏈表，稱為單鏈表或線性鏈表
* 有兩個指針域的鏈表，稱為雙鏈表
* 首尾相接的鏈表稱為循環鏈表
4. 頭指針是指向鏈表中第一個結點的指針
5. 首元結點是指鏈表中存儲第一個數據元素a1的結點
6. 頭結點是在鏈表的首元結點之前附設的一個結點；數據域內只放空表標志和表長等信息（可無）
當頭結點的指針域為空時表示空表
頭結點不能計入鏈表長度值
### 單鏈表的定義和實現
非空表
空表
單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名
若頭指針名是L，則把鏈表稱為表L
單鏈表的存儲結構定義
~~~
typedef struct LNode
{
ElemType data; //數據域
struct LNode *next; //指針域
}LNode,*LinkList; //*LinkList為Lnode類型的指針
~~~
注意：
指針變量p：表示結點地址
結點變量*p：表示一個結點
### 單鏈表基本操作的實現
#### 1.初始化(構造一個空表)
【算法思想】
(1)生成新結點作為頭結點，用頭結點L指向頭結點。
(2)頭結點的指針域置空。
【算法描述】
~~~
Status InitList_L(LinkList &L)
{
L=new LNode;
L->next=NULL;
return OK;
}
~~~
#### 2.查找
##### （1）按序號查找
【算法思想】
從鏈表的第一個結點（L->next）開始順著鏈域掃描，用指針p指向當前掃描到的結點，p的初始值指向第1個結點（p=L->next）。用j做計數器，累計當前掃描過的結點數，j的初值為1，當p指向掃描到的下一個結點時，計數器j相應加1.當j=i時，p所指向的結點是想要找的第i個結點。
【算法描述】
~~~
Status GetElem_L（LinkList L，int i，ElemType &e）
{
p=L->next;j=1;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
return ERROR;
e=p->data;
return OK;
}
~~~
#### 按值查找
【算法思想】
鏈表中查找其值與給定e相等的數據元素的過程和順序表類似，從第一個結點起，依次和e相比較，如果找到一個其值與e相等的數據元素，則返回其在鏈表中的“位置”；如果查遍整個鏈表都沒有找到其值和e相等的元素，則返回“NULL”。因此需要設置一個指針變量p順鏈掃描，直至p為“NULL”，或者p->data和e相等為止。
【算法描述】
~~~
LNode *LocateElem_L(LinkList L,ElemType e)
{
p=L->next;
while(p&&p->data!=e)
{
p=p->next;
}
return p;
}
~~~
### 3.插入
【算法思想】
將值為e的新結點插入到表的第i個結點的位置上，即插入到結點ai-1與ai之間，分為一下幾步：
1. 找到結點ai-1并由指針p指向該結點。
1. 生成一個新結點*s。
1. 將新結點*s的數據域置為e。
1. 將新結點*s的指針域指向結點ai。
1. 令結點ai-1的指針域指向新結點*s。
【算法描述】
~~~
Status ListInsert_L(LinkList &L,int i,ElemType e)
{
p=L;j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if(!p||j>i-1)
return ERROR;
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
~~~
### 4.刪除
【算法思想】
要刪除單鏈表的第i個結點ai，分以下幾步：
1. 找到結點ai-1并由指針p指向該結點。
2. 臨時保存待刪除結點ai的地址在q中，以備釋放。
3. 令p->next指向ai的直接后繼結點。
4. 將待刪除結點ai的值保留在e中
5. 釋放結點ai的空間。
【算法描述】
~~~
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
p=L;j=0;
while(p->next&&j<i-1)
{
p=p->next;++j;
}
if(!(p->next)||j>i-1)
return ERROR;
q=p->next;
e=q->data;
delete q;
return OK;
}
~~~
### 5.創建單鏈表
#### （1）前插法
【算法思想】
前插法是通過將新結點逐個插入鏈表的頭部（頭結點之后）來創建鏈表。首先建立只有一個頭結點的空鏈表，每讀入一個數據元素則申請一個新結點，并將新結點插入到頭結點之后。
【算法描述】
~~~
void CreateLst_F(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
for(i=n;i>0;--i)
{
p=new LNode;
cin>>p->data;
p->next=L->next;L->next=p;
}
}
~~~
#### (2)后插法
【算法思想】
后插法是通過將新結點逐個插入到鏈表的尾部來創建鏈表。同前插法一樣，首先要創建一個只有頭結點的空鏈表L，不同的是，為了使新結點能夠插入到表尾，需要增加一個尾指針r指向鏈表的尾結點，初始化時，r同L均指向頭結點。每讀入一個數據元素則申請一個新結點，將新結點插入到尾結點*r之后，然后使r指向新的尾結點。
【算法描述】
~~~
void CreateList_L(LinkList &L,int n)
{
L=new LNode;
L->next=NULL;
r=L;
for(i=0;i<n;++i)
{
p=new LNode;
cin>>p->data;
p->next=NULL;r->next=p;
r=p;
}
}
~~~
### 循環鏈表
循環鏈表是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。
兩個線性表合并成一個表，將第一個表的尾指針指向第二個表的第一個結點，第二個表的尾指針指向第一個表的頭結點，然后釋放第二個表的頭結點。
~~~
p=B->next->next;
B->next=A->next;
A->next=p;
~~~
