本文來自本人著作《趣學(xué)數(shù)據(jù)結(jié)構(gòu)》
鏈表是線性表的鏈?zhǔn)酱鎯Ψ绞?，邏輯上相鄰的?shù)據(jù)在計算機(jī)內(nèi)的存儲位置不一定相鄰，那么怎么表示邏輯上的相鄰關(guān)系呢？可以給每個元素附加一個指針域，指向下一個元素的存儲位置。如圖所示：
從圖中可以看出，每個結(jié)點包含兩個域：數(shù)據(jù)域和指針域，指針域存儲下一個結(jié)點的地址，因此指針指向的類型也是結(jié)點類型。
結(jié)點結(jié)構(gòu)體的定義：
定義了結(jié)點之后，我們就可以把若干個結(jié)點連接在一起，形成一個鏈表：
是不是像一個鐵鏈子，一環(huán)扣一環(huán)的連在一起？
不管這個鐵鏈子有多長，只要我們找到它的頭，就可以拉起整個鐵鏈子，因此我們給這個鏈表設(shè)置一個頭指針，這個鏈表中的每個結(jié)點都可以找到了。
有時候為了操作方便，我們還會給鏈表增加一個不存放數(shù)據(jù)的頭結(jié)點：
就像是給鐵鏈子加個鑰匙扣：
我們可以看到剛才的鏈表每個指針都是指向下一個結(jié)點，都是朝向一個方向的，這樣的鏈表稱為單向鏈表，或單鏈表。
在順序表中，想找第i個元素，就可以立即通過L.elem[i-1]找到，稱為隨機(jī)存取方式，而在單鏈表中，想找第i個元素？沒那么容易，必須從頭開始，按順序一個一個來，一直數(shù)到第i個元素，稱為順序存取方式。
下面以帶頭結(jié)點的單鏈表為例，講解單鏈表的初始化、創(chuàng)建、取值、查找、插入、刪除操作。
1. 單鏈表初始化
單鏈表初始化是指構(gòu)建一個空表：
bool InitList_L(LinkList &L)//構(gòu)造一個空的單鏈表L
{
L=new LNode; //生成新結(jié)點作為頭結(jié)點，用頭指針L指向頭結(jié)點
if(!L)
return false; //生成結(jié)點失敗
L->next=NULL; //頭結(jié)點的指針域置空
return true;
}
2. 單鏈表的創(chuàng)建
創(chuàng)建單鏈表分為前插法和尾插法兩種，前插法創(chuàng)建的單鏈表和輸入順序正好相反，因此稱為逆序建表，尾插法創(chuàng)建的單鏈表和輸入順序一致，因此稱為正序建表。
前插法建表如圖：
初始狀態(tài)
輸入數(shù)據(jù)元素1，創(chuàng)建新結(jié)點，把元素1放入新結(jié)點數(shù)據(jù)域：
s=new LNode; //生成新結(jié)點s
cin>>s->data; //輸入元素值賦給新結(jié)點的數(shù)據(jù)域
前插操作，插入到頭結(jié)點的后面：
輸入數(shù)據(jù)元素2，創(chuàng)建新結(jié)點，把元素2放入新結(jié)點數(shù)據(jù)域：
前插操作，插入到頭結(jié)點的后面：
解釋：
為什么要先修改后面那個指針呢？
因為一旦修改了L結(jié)點的指針域指向s，那么原來L結(jié)點后面的結(jié)點就找不到了，
注意：修改指針順序的原則：先修改沒有指針標(biāo)記的那一端。
如果要插入結(jié)點的兩端都有標(biāo)記，例如再定義一個指針q指向第1個結(jié)點，那么先修改哪個指針都無所謂了。
拉直鏈表之后：
繼續(xù)依次輸入數(shù)據(jù)元素3，4，5，6，7，8，9，10，前插法創(chuàng)建鏈表的結(jié)果：
void CreateList_H(LinkList &L)//前插法創(chuàng)建單鏈表
{
int n; //輸入n個元素的值，建立到頭結(jié)點的單鏈表L
LinkList s; //定義一個指針變量
L=new LNode;
L->next=NULL; //先建立一個帶頭結(jié)點的空鏈表
cout <<"請輸入元素個數(shù)n：" <
cin>>n;
cout <<"請依次輸入n個元素：" <
cout <<"前插法創(chuàng)建單鏈表..." <
while(n--)
{
s=new LNode; //生成新結(jié)點s
cin>>s->data; //輸入元素值賦給新結(jié)點的數(shù)據(jù)域
s->next=L->next;
L->next=s; //將新結(jié)點s插入到頭結(jié)點之后
}
}
尾插法建表如圖：
初始狀態(tài)(尾插法需要一個尾指針永遠(yuǎn)指向鏈表的尾結(jié)點)
輸入數(shù)據(jù)元素1，創(chuàng)建新結(jié)點，把元素1放入新結(jié)點數(shù)據(jù)域：
s=new LNode; //生成新結(jié)點s
cin>>s->data; //輸入元素值賦給新結(jié)點的數(shù)據(jù)域
尾插操作，插入到尾結(jié)點的后面：
解釋：
輸入數(shù)據(jù)元素2，創(chuàng)建新結(jié)點，把元素2放入新結(jié)點數(shù)據(jù)域：
尾插操作，插入到尾結(jié)點的后面：
繼續(xù)依次輸入數(shù)據(jù)元素3，4，5，6，7，8，9，10，前插法創(chuàng)建鏈表的結(jié)果：
void CreateList_R(LinkList &L)//尾插法創(chuàng)建單鏈表
{
//輸入n個元素的值，建立帶表頭結(jié)點的單鏈表L
int n;
LinkList s, r;
L=new LNode;
L->next=NULL; //先建立一個帶頭結(jié)點的空鏈表
r=L; //尾指針r指向頭結(jié)點
cout <<"請輸入元素個數(shù)n：" <
cin>>n;
cout <<"請依次輸入n個元素：" <
cout <<"尾插法創(chuàng)建單鏈表..." <
while(n--)
{
s=new LNode;//生成新結(jié)點
cin>>s->data; //輸入元素值賦給新結(jié)點的數(shù)據(jù)域
s->next=NULL;
r->next=s;//將新結(jié)點s插入尾結(jié)點r之后
r=s;//r指向新的尾結(jié)點s
}
}
3. 單鏈表取值
單鏈表的取值不像順序表那樣可以隨機(jī)訪問任何一個元素，單鏈表只有頭指針，各個結(jié)點的物理地址是不連續(xù)的，要想找到第i個結(jié)點，就必須從第一個結(jié)點開始按順序往后數(shù)，一直數(shù)到第i個結(jié)點。
那么具體怎么做呢？
注意：鏈表的頭指針不可以隨意改動！一個鏈表是由頭指針來標(biāo)識的，一旦頭指針改動或丟失，這個鏈表就不完整或找不到了。想想看，你拉著鐵鏈子一頭，另一端綁著水桶，到井里打水，你手一松，鏈子掉井里，找不到了。所以鏈表的頭指針是不能隨意改動的，如果需要用指針移動，可定義一個指針變量進(jìn)行移動。
可以定義一個p指針，指向第一個元素結(jié)點，用j作為計數(shù)器，j=1；
然后p指向p的下一個結(jié)點，即：
p=p->next; //p指向下一個結(jié)點
j++; //計數(shù)器j加1
直到p為空或者j=i停止，p為空說明沒有數(shù)到i，鏈表就結(jié)束了，j=i說明找到了第i個結(jié)點。
bool GetElem_L(LinkList L, int i, int &e)//單鏈表的取值
{
//在帶頭結(jié)點的單鏈表L中查找第i個元素
//用e記錄L中第i個數(shù)據(jù)元素的值
int j;
LinkList p;
p=L->next; //p指向第一個數(shù)據(jù)結(jié)點
j=1; //j為計數(shù)器
while (j
{
p=p->next; //p指向下一個結(jié)點
j++; //計數(shù)器j相應(yīng)加1
}
if (!p || j>i)
return false; //i值不合法i＞n或i<=0
e=p->data; //取第i個結(jié)點的數(shù)據(jù)域
return true;
}
4. 單鏈表查找
在一個單鏈表中查找是否存在元素e，可以定義一個p指針，指向第一個元素結(jié)點，比較p指向結(jié)點的數(shù)據(jù)域是否為e，如果相等，查找成功返回true，如果不等，則p指向p的下一個結(jié)點，即：
p=p->next; //p指向下一個結(jié)點
繼續(xù)比較，如果p為空，查找失敗返回false。
bool LocateElem_L(LinkList L, int e) //在帶頭結(jié)點的單鏈表L中查找值為e的元素
{
LinkList p;
p=L->next;
while (p && p->data!=e)//沿著鏈表向后掃描，直到p空或p所指結(jié)點數(shù)據(jù)域等于e
p=p->next; //p指向下一個結(jié)點
if(!p)
return false; //查找失敗p為NULL
return true;
}
5. 單鏈表插入
如果要在第i個結(jié)點之前插入一個元素，則必須先找到第i-1個結(jié)點，想一想：為什么？
單鏈表只有一個指針域，是向后操作的，不可以向前處理，第i個結(jié)點之前插入一個元素相當(dāng)于把新結(jié)點放在第i-1個結(jié)點和第i個結(jié)點之間。
解釋：
是不是有似曾相識的感覺？
前面講的前插法建鏈表，就是每次將新結(jié)點插入到頭結(jié)點和第一個結(jié)點之間。
bool ListInsert_L(LinkList &L, int i, int &e)//單鏈表的插入
{
//在帶頭結(jié)點的單鏈表L中第i個位置插入值為e的新結(jié)點
int j;
LinkList p, s;
p=L;
j=0;
while (p&&j
{
p=p->next;
j++;
}
if (!p || j>i-1) //i＞n+1或者i＜1
return false;
s=new LNode; //生成新結(jié)點
s->data=e; //將新結(jié)點的數(shù)據(jù)域置為e
s->next=p->next; //將新結(jié)點的指針域指向結(jié)點ai
p->next=s; //將結(jié)點p的指針域指向結(jié)點s
return true;
}
6. 單鏈表刪除
刪除一個結(jié)點，實際上是把這個結(jié)點跳過去。如圖：
要想跳過第i個結(jié)點，就必須先找到第i-1個結(jié)點，否則是無法跳過去的。
p->next=q->next；含義是將q結(jié)點的下一個結(jié)點地址賦值給p結(jié)點的指針域。在這些有關(guān)指針的賦值語句中，很多同學(xué)不理解，容易混淆，在此說明一下，等號的右側(cè)是結(jié)點的地址，等號的左側(cè)是結(jié)點的指針域：
q結(jié)點的下一個結(jié)點地址存儲在q->next里面，等號右側(cè)的q->next就相當(dāng)于把q結(jié)點的下一個結(jié)點地址讀出來，賦值給p結(jié)點的next指針域，這樣，就把q結(jié)點跳過去了。然后用delete q釋放被刪除結(jié)點的空間。
bool ListDelete_L(LinkList &L, int i) //單鏈表的刪除
{
//在帶頭結(jié)點的單鏈表L中，刪除第i個位置
LinkList p, q;
int j;
p=L;
j=0;
while((p->next)&&(j
{
p=p->next;
j++;
}
if (!(p->next)||(j>i-1))//當(dāng)i>n或i<1時，刪除位置不合理
return false;
q=p->next; //臨時保存被刪結(jié)點的地址以備釋放空間
p->next=q->next; //改變刪除結(jié)點前驅(qū)結(jié)點的指針域
delete q; //釋放被刪除結(jié)點的空間
return true;
}
單鏈表基本操作完整代碼：
完整代碼：
#include
#include
#include
#include
using namespace std;
typedef struct LNode {
int data; //結(jié)點的數(shù)據(jù)域
struct LNode *next; //結(jié)點的指針域
}LNode, *LinkList; //LinkList為指向結(jié)構(gòu)體LNode的指針類型
bool InitList_L(LinkList &L)//構(gòu)造一個空的單鏈表L
{
L=new LNode; //生成新結(jié)點作為頭結(jié)點，用頭指針L指向頭結(jié)點
if(!L)
return false; //生成結(jié)點失敗
L->next=NULL; //頭結(jié)點的指針域置空
return true;
}
void CreateList_H(LinkList &L)//前插法創(chuàng)建單鏈表
{
//輸入n個元素的值，建立到頭結(jié)點的單鏈表L
int n;
LinkList s; //定義一個指針變量
L=new LNode;
L->next=NULL; //先建立一個帶頭結(jié)點的空鏈表
cout <<"請輸入元素個數(shù)n：" <
cin>>n;
cout <<"請依次輸入n個元素：" <
cout <<"前插法創(chuàng)建單鏈表..." <
while(n--)
{
s=new LNode; //生成新結(jié)點s
cin>>s->data; //輸入元素值賦給新結(jié)點的數(shù)據(jù)域
s->next=L->next;
L->next=s; //將新結(jié)點s插入到頭結(jié)點之后
}
}
void CreateList_R(LinkList &L)//尾插法創(chuàng)建單鏈表
{
//輸入n個元素的值，建立帶表頭結(jié)點的單鏈表L
int n;
LinkList s, r;
L=new LNode;
L->next=NULL; //先建立一個帶頭結(jié)點的空鏈表
r=L; //尾指針r指向頭結(jié)點
cout <<"請輸入元素個數(shù)n：" <
cin>>n;
cout <<"請依次輸入n個元素：" <
cout <<"尾插法創(chuàng)建單鏈表..." <
while(n--)
{
s=new LNode;//生成新結(jié)點
cin>>s->data; //輸入元素值賦給新結(jié)點的數(shù)據(jù)域
s->next=NULL;
r->next=s;//將新結(jié)點s插入尾結(jié)點r之后
r=s;//r指向新的尾結(jié)點s
}
}
bool GetElem_L(LinkList L, int i, int &e)//單鏈表的取值
{
//在帶頭結(jié)點的單鏈表L中查找第i個元素
//用e記錄L中第i個數(shù)據(jù)元素的值
int j;
LinkList p;
p=L->next;//p指向第一個結(jié)點，
j=1; //j為計數(shù)器
while (j
{
p=p->next; //p指向下一個結(jié)點
j++; //計數(shù)器j相應(yīng)加1
}
if (!p || j>i)
return false; //i值不合法i＞n或i<=0
e=p->data; //取第i個結(jié)點的數(shù)據(jù)域
return true;
}
bool LocateElem_L(LinkList L, int e) //按值查找
{
//在帶頭結(jié)點的單鏈表L中查找值為e的元素
LinkList p;
p=L->next;
while (p && p->data!=e)//順鏈域向后掃描，直到p為空或p所指結(jié)點的數(shù)據(jù)域等于e
p=p->next; //p指向下一個結(jié)點
if(!p)
return false; //查找失敗p為NULL
return true;
}
bool ListInsert_L(LinkList &L, int i, int &e)//單鏈表的插入
{
//在帶頭結(jié)點的單鏈表L中第i個位置插入值為e的新結(jié)點
int j;
LinkList p, s;
p=L;
j=0;
while (p&&j
{
p=p->next;
j++;
}
if (!p || j>i-1)//i＞n+1或者i＜1
return false;
s=new LNode; //生成新結(jié)點
s->data=e; //將新結(jié)點的數(shù)據(jù)域置為e
s->next=p->next; //將新結(jié)點的指針域指向結(jié)點ai
p->next=s; //將結(jié)點p的指針域指向結(jié)點s
return true;
}
bool ListDelete_L(LinkList &L, int i) //單鏈表的刪除
{
//在帶頭結(jié)點的單鏈表L中，刪除第i個位置
LinkList p, q;
int j;
p=L;
j=0;
while((p->next)&&(j
{
p=p->next;
j++;
}
if (!(p->next)||(j>i-1))//當(dāng)i>n或i<1時，刪除位置不合理
return false;
q=p->next; //臨時保存被刪結(jié)點的地址以備釋放空間
p->next=q->next; //改變刪除結(jié)點前驅(qū)結(jié)點的指針域
delete q; //釋放被刪除結(jié)點的空間
return true;
}
void Listprint_L(LinkList L) //單鏈表的輸出
{
LinkList p;
p=L->next;
while (p)
{
cout <data <<"\t";
p=p->next;
}
cout<
}
int main()
{
int i,x,e,choose;
LinkList L;
cout << "1. 初始化\n";
cout << "2. 創(chuàng)建單鏈表（前插法）\n";
cout << "3. 創(chuàng)建單鏈表（尾插法）\n";
cout << "4. 取值\n";
cout << "5. 查找\n";
cout << "6. 插入\n";
cout << "7. 刪除\n";
cout << "8. 輸出\n";
cout << "0. 退出\n";
choose=-1;
while (choose!=0)
{
cout<<"請輸入數(shù)字選擇:";
cin>>choose;
switch (choose)
{
case 1: //初始化一個空的單鏈表
if (InitList_L(L))
cout << "初始化一個空的單鏈表!\n";
break;
case 2: //創(chuàng)建單鏈表（前插法）
CreateList_H(L);
cout << "前插法創(chuàng)建單鏈表輸出結(jié)果:\n";
Listprint_L(L);
break;
case 3: //創(chuàng)建單鏈表（尾插法）
CreateList_R(L);
cout << "尾插法創(chuàng)建單鏈表輸出結(jié)果:\n";
Listprint_L(L);
break;
case 4: //單鏈表的按序號取值
cout << "請輸入一個位置i用來取值:";
cin >> i;
if (GetElem_L(L,i,e))
{
cout << "查找成功\n";
cout << "第" << i << "個元素是："<
}
else
cout << "查找失敗\n\n";
break;
case 5: //單鏈表的按值查找
cout<<"請輸入所要查找元素x:";
cin>>x;
if (LocateElem_L(L,x))
cout << "查找成功\n";
else
cout << "查找失敗! " <
break;
case 6: //單鏈表的插入
cout << "請輸入插入的位置和元素（用空格隔開）:";
cin >> i;
cin >> x;
if (ListInsert_L(L, i, x))
cout << "插入成功.\n\n";
else
cout << "插入失敗!\n\n";
break;
case 7: //單鏈表的刪除
cout<<"請輸入所要刪除的元素位置i:";
cin>>i;
if (ListDelete_L(L, i))
cout<<"刪除成功!\n";
else
cout<<"刪除失敗!\n";
break;
case 8: //單鏈表的輸出
cout << "當(dāng)前單鏈表的數(shù)據(jù)元素分別為:\n";
Listprint_L(L);
cout << endl;
break;
}
}
return 0;
}
本文來自本人著作《趣學(xué)數(shù)據(jù)結(jié)構(gòu)》。
