7.4 鏈表的建立、插入和刪除
數(shù)組作為存放同類數(shù)據(jù)的集合，給我們在程序設(shè)計(jì)時帶來很多的方便，增加了靈活性。但數(shù)組也同樣存在一些弊病。如數(shù)組的大小在定義時要事先規(guī)定，不能在程序中進(jìn)行調(diào)整，這樣一來，在程序設(shè)計(jì)中針對不同問題有時需要3 0個大小的數(shù)組，有時需要5 0個數(shù)組的大小，難于統(tǒng)一。我們只能夠根據(jù)可能的需求來定義數(shù)組，常常會造成一定存儲空間的浪費(fèi)。
我們希望構(gòu)造動態(tài)的數(shù)組，隨時可以調(diào)整數(shù)組的大小，以滿足不同問題的需要。鏈表就是我們需要的動態(tài)數(shù)組。它是在程序的執(zhí)行過程中根據(jù)需要有數(shù)據(jù)存儲就向系統(tǒng)要求申請存儲空間，決不構(gòu)成對存儲區(qū)的浪費(fèi)。
鏈表是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)之間的相互關(guān)系使鏈表分成三種：單鏈表、循環(huán)鏈表、雙向鏈表，下面將逐一介紹。
7.4.1 單鏈表
單鏈表有一個頭節(jié)點(diǎn)head，指向鏈表在內(nèi)存的首地址。鏈表中的每一個節(jié)點(diǎn)的數(shù)據(jù)類型為結(jié)構(gòu)體類型，節(jié)點(diǎn)有兩個成員：整型成員（實(shí)際需要保存的數(shù)據(jù)）和指向下一個結(jié)構(gòu)體類型節(jié)點(diǎn)的指針即下一個節(jié)點(diǎn)的地址（事實(shí)上，此單鏈表是用于存放整型數(shù)據(jù)的動態(tài)數(shù)組）。鏈表按此結(jié)構(gòu)對各節(jié)點(diǎn)的訪問需從鏈表的頭找起，后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出。無論在表中訪問那一個節(jié)點(diǎn)，都需要從鏈表的頭開始，順序向后查找。鏈表的尾節(jié)點(diǎn)由于無后續(xù)節(jié)點(diǎn)，其指針域?yàn)榭?，寫作為NULL。
圖7 - 3還給出這樣一層含義，鏈表中的各節(jié)點(diǎn)在內(nèi)存的存儲地址不是連續(xù)的，其各節(jié)點(diǎn)的地址是在需要時向系統(tǒng)申請分配的，系統(tǒng)根據(jù)內(nèi)存的當(dāng)前情況，既可以連續(xù)分配地址，也可以跳躍式分配地址。
看一下鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義：
struct node
{
int num;
struct node *p;
} ;
在鏈表節(jié)點(diǎn)的定義中，除一個整型的成員外，成員p是指向與節(jié)點(diǎn)類型完全相同的指針。在鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中，非常特殊的一點(diǎn)就是結(jié)構(gòu)體內(nèi)的指針域的數(shù)據(jù)類型使用了未定義成功的數(shù)據(jù)類型。這是在C中規(guī)定可以先使用后定義的數(shù)據(jù)結(jié)構(gòu)。
• 單鏈表的創(chuàng)建過程有以下幾步：
1 ) 定義鏈表的數(shù)據(jù)結(jié)構(gòu)。
2 ) 創(chuàng)建一個空表。
3 ) 利用malloc( )函數(shù)向系統(tǒng)申請分配一個節(jié)點(diǎn)。
4) 將新節(jié)點(diǎn)的指針成員賦值為空。若是空表，將新節(jié)點(diǎn)連接到表頭；若是非空表，將新
節(jié)點(diǎn)接到表尾。
5) 判斷一下是否有后續(xù)節(jié)點(diǎn)要接入鏈表，若有轉(zhuǎn)到3 )，否則結(jié)束。
• 單鏈表的輸出過程有以下幾步
1) 找到表頭。
2) 若是非空表，輸出節(jié)點(diǎn)的值成員，是空表則退出。
3) 跟蹤鏈表的增長，即找到下一個節(jié)點(diǎn)的地址。
4) 轉(zhuǎn)到2 )。
[例7-5] 創(chuàng)建一個存放正整數(shù)（輸入- 9 9 9做結(jié)束標(biāo)志）的單鏈表，并打印輸出。
#include /* 包含malloc( ) 的頭文件*/
#include
struct node /*鏈表節(jié)點(diǎn)的結(jié)構(gòu)* /
{
int num;
struct node *next;
} ;
main( )
{
struct node *creat(); / *函數(shù)聲明* /
void print();
struct node *head; / * 定義頭指針* /
head=NULL; /* 建一個空表*/
head=creat(head); /* 創(chuàng)建單鏈表*/
print(head);/*打印單鏈表*/
}
/******************************************************/
struct node *creat(struct node *head) /* 函數(shù)返回的是與節(jié)點(diǎn)相同類型的指針*/
{
struct node *p1,*p2;
p1=p2=(struct node*) malloc(sizeof(struct node)); /* 申請新節(jié)點(diǎn)*/
scanf("%d", &p1->num); /* 輸入節(jié)點(diǎn)的值*/
p1-> next = NULL; /* 將新節(jié)點(diǎn)的指針置為空*/
while(p1->num>0) /* 輸入節(jié)點(diǎn)的數(shù)值大于0 */
{
if (head==NULL) head=p1; /* 空表，接入表頭*/
else p2->next=p1; /* 非空表，接到表尾*/
p2 = p1;
p1=(struct node *)malloc(sizeof(struct node)); /* 申請下一個新節(jié)點(diǎn)*/
scanf("%d", &p1->num); /*輸入節(jié)點(diǎn)的值*/
}
return head; /*返回鏈表的頭指針*/
}
/****************************************************/
void print(struct node *head) /* 輸出以head 為頭的鏈表各節(jié)點(diǎn)的值*/
{
struct node *temp;
temp=head; /*取得鏈表的頭指針*/
while (temp!=NULL) / *只要是非空表* /
{
printf("%6d", temp->num); /*輸出鏈表節(jié)點(diǎn)的值*/
數(shù)組作為存放同類數(shù)據(jù)的集合，給我們在程序設(shè)計(jì)時帶來很多的方便，增加了靈活性。但數(shù)組也同樣存在一些弊病。如數(shù)組的大小在定義時要事先規(guī)定，不能在程序中進(jìn)行調(diào)整，這樣一來，在程序設(shè)計(jì)中針對不同問題有時需要3 0個大小的數(shù)組，有時需要5 0個數(shù)組的大小，難于統(tǒng)一。我們只能夠根據(jù)可能的需求來定義數(shù)組，常常會造成一定存儲空間的浪費(fèi)。
我們希望構(gòu)造動態(tài)的數(shù)組，隨時可以調(diào)整數(shù)組的大小，以滿足不同問題的需要。鏈表就是我們需要的動態(tài)數(shù)組。它是在程序的執(zhí)行過程中根據(jù)需要有數(shù)據(jù)存儲就向系統(tǒng)要求申請存儲空間，決不構(gòu)成對存儲區(qū)的浪費(fèi)。
鏈表是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)之間的相互關(guān)系使鏈表分成三種：單鏈表、循環(huán)鏈表、雙向鏈表，下面將逐一介紹。
7.4.1 單鏈表
單鏈表有一個頭節(jié)點(diǎn)head，指向鏈表在內(nèi)存的首地址。鏈表中的每一個節(jié)點(diǎn)的數(shù)據(jù)類型為結(jié)構(gòu)體類型，節(jié)點(diǎn)有兩個成員：整型成員（實(shí)際需要保存的數(shù)據(jù)）和指向下一個結(jié)構(gòu)體類型節(jié)點(diǎn)的指針即下一個節(jié)點(diǎn)的地址（事實(shí)上，此單鏈表是用于存放整型數(shù)據(jù)的動態(tài)數(shù)組）。鏈表按此結(jié)構(gòu)對各節(jié)點(diǎn)的訪問需從鏈表的頭找起，后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出。無論在表中訪問那一個節(jié)點(diǎn)，都需要從鏈表的頭開始，順序向后查找。鏈表的尾節(jié)點(diǎn)由于無后續(xù)節(jié)點(diǎn)，其指針域?yàn)榭?，寫作為NULL。
圖7 - 3還給出這樣一層含義，鏈表中的各節(jié)點(diǎn)在內(nèi)存的存儲地址不是連續(xù)的，其各節(jié)點(diǎn)的地址是在需要時向系統(tǒng)申請分配的，系統(tǒng)根據(jù)內(nèi)存的當(dāng)前情況，既可以連續(xù)分配地址，也可以跳躍式分配地址。
看一下鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義：
struct node
{
int num;
struct node *p;
} ;
在鏈表節(jié)點(diǎn)的定義中，除一個整型的成員外，成員p是指向與節(jié)點(diǎn)類型完全相同的指針。在鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中，非常特殊的一點(diǎn)就是結(jié)構(gòu)體內(nèi)的指針域的數(shù)據(jù)類型使用了未定義成功的數(shù)據(jù)類型。這是在C中規(guī)定可以先使用后定義的數(shù)據(jù)結(jié)構(gòu)。
• 單鏈表的創(chuàng)建過程有以下幾步：
1 ) 定義鏈表的數(shù)據(jù)結(jié)構(gòu)。
2 ) 創(chuàng)建一個空表。
3 ) 利用malloc( )函數(shù)向系統(tǒng)申請分配一個節(jié)點(diǎn)。
4) 將新節(jié)點(diǎn)的指針成員賦值為空。若是空表，將新節(jié)點(diǎn)連接到表頭；若是非空表，將新
節(jié)點(diǎn)接到表尾。
5) 判斷一下是否有后續(xù)節(jié)點(diǎn)要接入鏈表，若有轉(zhuǎn)到3 )，否則結(jié)束。
• 單鏈表的輸出過程有以下幾步
1) 找到表頭。
2) 若是非空表，輸出節(jié)點(diǎn)的值成員，是空表則退出。
3) 跟蹤鏈表的增長，即找到下一個節(jié)點(diǎn)的地址。
4) 轉(zhuǎn)到2 )。
[例7-5] 創(chuàng)建一個存放正整數(shù)（輸入- 9 9 9做結(jié)束標(biāo)志）的單鏈表，并打印輸出。
#include
#include
struct node /*鏈表節(jié)點(diǎn)的結(jié)構(gòu)* /
{
int num;
struct node *next;
} ;
main( )
{
struct node *creat(); / *函數(shù)聲明* /
void print();
struct node *head; / * 定義頭指針* /
head=NULL; /* 建一個空表*/
head=creat(head); /* 創(chuàng)建單鏈表*/
print(head);/*打印單鏈表*/
}
/******************************************************/
struct node *creat(struct node *head) /* 函數(shù)返回的是與節(jié)點(diǎn)相同類型的指針*/
{
struct node *p1,*p2;
p1=p2=(struct node*) malloc(sizeof(struct node)); /* 申請新節(jié)點(diǎn)*/
scanf("%d", &p1->num); /* 輸入節(jié)點(diǎn)的值*/
p1-> next = NULL; /* 將新節(jié)點(diǎn)的指針置為空*/
while(p1->num>0) /* 輸入節(jié)點(diǎn)的數(shù)值大于0 */
{
if (head==NULL) head=p1; /* 空表，接入表頭*/
else p2->next=p1; /* 非空表，接到表尾*/
p2 = p1;
p1=(struct node *)malloc(sizeof(struct node)); /* 申請下一個新節(jié)點(diǎn)*/
scanf("%d", &p1->num); /*輸入節(jié)點(diǎn)的值*/
}
return head; /*返回鏈表的頭指針*/
}
/****************************************************/
void print(struct node *head) /* 輸出以head 為頭的鏈表各節(jié)點(diǎn)的值*/
{
struct node *temp;
temp=head; /*取得鏈表的頭指針*/
while (temp!=NULL) / *只要是非空表* /
{
printf("%6d", temp->num); /*輸出鏈表節(jié)點(diǎn)的值*/