數(shù)組作為存放同類數(shù)據(jù)的集合，給我們?cè)诔绦蛟O(shè)計(jì)時(shí)帶來(lái)很多的方便，增加了靈活性。但數(shù)組也同樣存在一些弊病。如數(shù)組的大小在定義時(shí)要事先規(guī)定，不能在程序中進(jìn)行調(diào)整，這樣一來(lái)，在程序設(shè)計(jì)中針對(duì)不同問(wèn)題有時(shí)需要3 0個(gè)大小的數(shù)組，有時(shí)需要5 0個(gè)數(shù)組的大小，
難于統(tǒng)一。我們只能夠根據(jù)可能的最大需求來(lái)定義數(shù)組，常常會(huì)造成一定存儲(chǔ)空間的浪費(fèi)。
我們希望構(gòu)造動(dòng)態(tài)的數(shù)組，隨時(shí)可以調(diào)整數(shù)組的大小，以滿足不同問(wèn)題的需要。鏈表就是我們需要的動(dòng)態(tài)數(shù)組。它是在程序的執(zhí)行過(guò)程中根據(jù)需要有數(shù)據(jù)存儲(chǔ)就向系統(tǒng)要求申請(qǐng)存儲(chǔ)空間，決不構(gòu)成對(duì)存儲(chǔ)區(qū)的浪費(fèi)。
鏈表是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)之間的相互關(guān)系使鏈表分成三種：?jiǎn)捂湵?、循環(huán)鏈表、雙向鏈表，下面將逐一介紹。
7.4.1 單鏈表
圖7 – 3是單鏈表的結(jié)構(gòu)。

單鏈表有一個(gè)頭節(jié)點(diǎn)h e a d，指向鏈表在內(nèi)存的首地址。鏈表中的每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)類型為結(jié)構(gòu)體類型，節(jié)點(diǎn)有兩個(gè)成員：整型成員（實(shí)際需要保存的數(shù)據(jù)）和指向下一個(gè)結(jié)構(gòu)體類型節(jié)點(diǎn)的指針即下一個(gè)節(jié)點(diǎn)的地址（事實(shí)上，此單鏈表是用于存放整型數(shù)據(jù)的動(dòng)態(tài)數(shù)組）。鏈表按此結(jié)構(gòu)對(duì)各節(jié)點(diǎn)的訪問(wèn)需從鏈表的頭找起，后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出。無(wú)論在表中訪問(wèn)那一個(gè)節(jié)點(diǎn)，都需要從鏈表的頭開(kāi)始，順序向后查找。鏈表的尾節(jié)點(diǎn)由于無(wú)后續(xù)節(jié)點(diǎn)，其指針域?yàn)榭眨瑢?xiě)作為N U L L。
圖7 – 3還給出這樣一層含義，鏈表中的各節(jié)點(diǎn)在內(nèi)存的存儲(chǔ)地址不是連續(xù)的，其各節(jié)點(diǎn)的地址是在需要時(shí)向系統(tǒng)申請(qǐ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)的定義中，除一個(gè)整型的成員外，成員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)建過(guò)程有以下幾步：
1 ) 定義鏈表的數(shù)據(jù)結(jié)構(gòu)。
2 ) 創(chuàng)建一個(gè)空表。
3 ) 利用m a l l o c ( )函數(shù)向系統(tǒng)申請(qǐng)分配一個(gè)節(jié)點(diǎn)。
4 ) 將新節(jié)點(diǎn)的指針成員賦值為空。若是空表，將新節(jié)點(diǎn)連接到表頭；若是非空表，將新
節(jié)點(diǎn)接到表尾。
5 ) 判斷一下是否有后續(xù)節(jié)點(diǎn)要接入鏈表，若有轉(zhuǎn)到3 )，否則結(jié)束。
? 單鏈表的輸出過(guò)程有以下幾步
1) 找到表頭。
2) 若是非空表，輸出節(jié)點(diǎn)的值成員，是空表則退出。
3 ) 跟蹤鏈表的增長(zhǎng)，即找到下一個(gè)節(jié)點(diǎn)的地址。
4) 轉(zhuǎn)到2 )。
[例7-5] 創(chuàng)建一個(gè)存放正整數(shù)（輸入- 9 9 9做結(jié)束標(biāo)志）的單鏈表，并打印輸出。
#include <stdlib.h> /包*含ma l l o c ( ) 的頭文件*/
#include <stdio.h>
struct node /*鏈表節(jié)點(diǎn)的結(jié)構(gòu)* /
{
int num;
struct node *next;
} ;
m a i n ( )
{
struct node *creat(); / *函數(shù)聲明* /
void print();
struct node *head; / * 定義頭指針* /
head=NULL;/*建一個(gè)空表*/
head=creat(head);/*創(chuàng)建單鏈表*/
print(head);/*打印單鏈表*/
}
/******************************************/
struct node*creat(structnode*head)函/數(shù)*返回的是與節(jié)點(diǎn)相同類型的指針*/
{
struct node*p1,*p2;
p1=p2=(structnode*)malloc(sizeof(structnode));申請(qǐng)/*新節(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;/*空表，接入表頭*/
elsep2->next=p1;/*非空表，接到表尾*/
p2=p1;
p1=(structnode*)malloc(sizeof(structnode));申/請(qǐng)*下一個(gè)新節(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)的值*/
temp=temp->next;/*跟蹤鏈表增長(zhǎng)*/
}
}
在鏈表的創(chuàng)建過(guò)程中，鏈表的頭指針是非常重要的參數(shù)。因?yàn)閷?duì)鏈表的輸出和查找都要從鏈表的頭開(kāi)始，所以鏈表創(chuàng)建成功后，要返回一個(gè)鏈表頭節(jié)點(diǎn)的地址，即頭指針。

7.4.2 單鏈表的插入與刪除
在鏈表這種特殊的數(shù)據(jù)結(jié)構(gòu)中，鏈表的長(zhǎng)短需要根據(jù)具體情況來(lái)設(shè)定，當(dāng)需要保存數(shù)據(jù)時(shí)向系統(tǒng)申請(qǐng)存儲(chǔ)空間，并將數(shù)據(jù)接入鏈表中。對(duì)鏈表而言，表中的數(shù)據(jù)可以依此接到表尾或連結(jié)到表頭，也可以視情況插入表中；對(duì)不再需要的數(shù)據(jù)，將其從表中刪除并釋放其所占空間，但不能破壞鏈表的結(jié)構(gòu)。這就是下面將介紹的鏈表的插入與刪除。
1. 鏈表的刪除
在鏈表中刪除一個(gè)節(jié)點(diǎn)，用圖7 – 4描述如下：
[例7-6] 創(chuàng)建一個(gè)學(xué)生學(xué)號(hào)及姓名的單鏈表，即節(jié)點(diǎn)包括學(xué)生學(xué)號(hào)、姓名及指向下一個(gè)節(jié)點(diǎn)的指針，鏈表按學(xué)生的學(xué)號(hào)排列。再?gòu)逆I盤(pán)輸入某一學(xué)生姓名，將其從鏈表中刪除。
首先定義鏈表的結(jié)構(gòu)：
struct
從圖7 – 4中看到，從鏈表中刪除一個(gè)節(jié)點(diǎn)有三種情況，即刪除鏈表頭節(jié)點(diǎn)、刪除鏈表的中
間節(jié)點(diǎn)、刪除鏈表的尾節(jié)點(diǎn)。題目給出的是學(xué)生姓名，則應(yīng)在鏈表中從頭到尾依此查找各節(jié)
點(diǎn)，并與各節(jié)點(diǎn)的學(xué)生姓名比較，若相同，則查找成功，否則，找不到節(jié)點(diǎn)。由于刪除的節(jié)
點(diǎn)可能在鏈表的頭，會(huì)對(duì)鏈表的頭指針造成丟失，所以定義刪除節(jié)點(diǎn)的函數(shù)的返回值定義為
返回結(jié)構(gòu)體類型的指針。
struct node *delet(head,pstr)以/*he a d 為頭指針，刪除ps t r 所在節(jié)點(diǎn)*/
struct node *head;
char *pstr;
{
struct node *temp,*p;
t e m p = h e a d ; / * 鏈表的頭指針* /
if (head==NULL) / *鏈表為空* /
printf(“nList is null!n”);
else /*非空表* /
{
t e m p = h e a d ;
while (strcmp(temp->str,pstr)!=0&&temp->next!=NULL)
/ * 若節(jié)點(diǎn)的字符串與輸入字符串不同，并且未到鏈表尾* /
{
p = t e m p ;
t e m p = t e m p – > n e x t ; / * 跟蹤鏈表的增長(zhǎng)，即指針后移* /
}
if(strcmp(temp->str,pstr)==0 ) / *找到字符串* /
{
if(temp==head) { / * 表頭節(jié)點(diǎn)* /
printf(“delete string :%sn”,temp->str);
h e a d = h e a d – > n e x t ;
f r e e ( t e m p ) ; / *釋放被刪節(jié)點(diǎn)* /
}
e l s e
{
p->next=temp->next; /表*中節(jié)點(diǎn)*/
printf(“delete string :%sn”,temp->str);
f r e e ( t e m p ) ;
}
}
else printf(“nno find string!n”);沒(méi)/找* 到要?jiǎng)h除的字符串*/
}
r e t u r n ( h e a d ) ; / *返回表頭指針* /
}
2. 鏈表的插入
首先定義鏈表的結(jié)構(gòu)：
struct
{
int num; /*學(xué)生學(xué)號(hào)* /
char str[20]; /*姓名* /
struct node *next;
} ;
在建立的單鏈表中，插入節(jié)點(diǎn)有三種情況，如圖7 – 5所示。

插入的節(jié)點(diǎn)可以在表頭、表中或表尾。假定我們按照以學(xué)號(hào)為順序建立鏈表，則插入的節(jié)點(diǎn)依次與表中節(jié)點(diǎn)相比較，找到插入位置。由于插入的節(jié)點(diǎn)可能在鏈表的頭，會(huì)對(duì)鏈表的頭指針造成修改，所以定義插入節(jié)點(diǎn)的函數(shù)的返回值定義為返回結(jié)構(gòu)體類型的指針。節(jié)點(diǎn)的
插入函數(shù)如下：
struct node *insert(head,pstr,n) / *插入學(xué)號(hào)為n、姓名為p s t r 的節(jié)點(diǎn)* /
struct node *head; / *鏈表的頭指針* /
char *pstr;
int n;
{
struct node *p1,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node))分;配/*一個(gè)新節(jié)點(diǎn)*/
s t r c p y ( p 1 – > s t r , p s t r ) ; / * 寫(xiě)入節(jié)點(diǎn)的姓名字串* /
p 1 – > n u m = n ; / * 學(xué)號(hào)* /
p 2 = h e a d ;
if (head==NULL) / * 空表* /
{
head=p1; p1->next=NULL;/ *新節(jié)點(diǎn)插入表頭* /
}
e l s e
{ /*非空表* /
while(n>p2->num&&p2->next!=NULL)
/ *輸入的學(xué)號(hào)小于節(jié)點(diǎn)的學(xué)號(hào)，并且未到表尾* /
{
p 3 = p 2 ;
p 2 = p 2 – > n e x t ; / * 跟蹤鏈表增長(zhǎng)* /
}
if (n<=p2->num) / *找到插入位置* /
if (head==p2) / * 插入位置在表頭* /
{
h e a d = p 1 ;
p 1 – > n e x t = p 2 ;
}
e l s e
{ /*插入位置在表中* /
p 3 – > n e x t = p 1 ;
p 1 – > n e x t = p 2 ;
}
e l s e
{ /*插入位置在表尾* /
p 2 – > n e x t = p 1 ;
p 1 – > n e x t = N U L L ;
}
}
r e t u r n ( h e a d ) ; / * 返回鏈表的頭指針* /
}

3. 實(shí)例[例7 – 7 ]
創(chuàng)建包含學(xué)號(hào)、姓名節(jié)點(diǎn)的單鏈表。其節(jié)點(diǎn)數(shù)任意個(gè)，表以學(xué)號(hào)為序，低學(xué)號(hào)的在前，高學(xué)號(hào)的在后，以輸入姓名為空作結(jié)束。在此鏈表中，要求刪除一個(gè)給定姓名的節(jié)點(diǎn)，并插入一個(gè)給定學(xué)號(hào)和姓名的節(jié)點(diǎn)。
# include “stdlib.h”
# include “malloc. h”
struct node /*節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)* /
{
int num;
char str[20];
struct node *next;
} ;
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
main( )
{
/ *函數(shù)聲明* /
struct node *creat();
struct node *insert();
struct node *delet();
void print( );
struct node *head;
char str[20];
int n;
head=NULL; /*做空表* /
head=creat (head); / *調(diào)用函數(shù)創(chuàng)建以head 為頭的鏈表* /
p r i n t ( h e a d ) ；/ *調(diào)用函數(shù)輸出節(jié)點(diǎn)* /
printf(“n input inserted num,name:n”);
gets(str); /*輸入學(xué)號(hào)* /
n=atoi (str);
gets(str); /*輸入姓名* /
head=insert (head, str, n); 將/*節(jié)點(diǎn)插入鏈表*/
print (head)； / *調(diào)用函數(shù)輸出節(jié)點(diǎn)*/
printf(“n input deleted name:n”);
gets(str); /*輸入被刪姓名* /
head=delet(head,str); /調(diào)*用函數(shù)刪除節(jié)點(diǎn)*/
print (head); /*調(diào)用函數(shù)輸出節(jié)點(diǎn)* /
r e t u r n ;
}
/ * * * * * * * * * * * * * * * * * * * * * * /
/ * * * 創(chuàng)建鏈表* * * * * * * * * * * * /
struct node *creat(struct node *head)
{
char temp[30];
struct node *pl,*p2;
pl=p2=(struct node*) malloc(sizeof(struct node));
printf (“input num, name: n;”)
printf(“exit:double times Enter!n”);
g e t s ( t e m p ) ;
gets (p1->str);
pl->num=atoi (temp);
p l – > n e x t = N U L L ;
while (strlen (pl->str)>0
{
if (head==NULL) head=pl；
else p2->next=p1;
P 2 = p l ；
pl=(struct node *)malloc(sizeof(struct node));
printf (“input num, name: n”);
printf(“exit:double times Enter!n”);
g e t s ( t e m p ) ;
gets(pl ->str);
p1->num=atoi (temp);
P 1 – > n e x t = N U L L ;
}
return head;
}
/ * * * * * * * * * * * * * * * * * * * * /
/ * * * * * * * * * * 插入節(jié)點(diǎn)* * * * * * * * * * /
struct node *insert (head, pstr,n);
struct node *head;
char *pstr;
int n;
{
struct node *pl,*p2,*p3;
p1=(struct node*)malloc(sizeof(struct node));
strcpy (p1->str, pstr);
p 1 – > n u m = n ;
p 2 = h e a d ;
i f ( h e a d = = N U L L )
{
h e a d = p l ; p l – > n e x t = N U L L ;
}
e l s e
{
while (n>p2->num&&p2->next!=NULL)
{
p 3 = P 2
p 2 = p 2 – > n e x t ;
}
if (n<=p2->num)
if (head==p2)
{
h e a d = p l ;
p l – > n e x t = p 2 ;
}
else
{
p 3 – > n e x t = p l ;
p l – > n e x t = p 2 ;
}
else
{
p 2 – > n e x t = p l ;
p l – > n e x t = N U L L ;
}
}
r e t u r n ( h e a d ) ;
}
/ * * * * * * * * * * * * * * * * * * * * * * * * * /
/ * * * * * 刪除節(jié)點(diǎn)* * * * * * * * * * * * * /
struct node *delet (head, pstr)
struct node *head;
char *pstr;
{
struct node *temp,*p;
t e m p = h e a d ;
if (head==NULL)
printf(“nList is null!n”);
else
{
t e m p = h e a d ;
while (strcmp(temp->str,pstr)!=O&&temp->next!=NULL)
{
p = t e m p ;
t e m p = t e m p – > n e x t ,
}
i f ( s t r c m p ( t e m p – > s t r , p s t r ) = = 0 )
{
if (temp== head)
{
h e a d = h e a d – > n e x t ;
f r e e ( t e m p ) ;
}
else
{
p->next =temp->next;
printf(“delete string :%sn”,temp->str);
f r e e ( t e m p ) ;
}
}
else printf(“nno find string!n”);
}
return(head);
}
/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
/ * * * * * * * * * * 鏈表各節(jié)點(diǎn)的輸出* * * * * * * * * * /
void print (struct node *head)
{
struct node *temp;
t e m p = h e a d ;
printf(“n output strings:n”);
while (temp!=NULL)
{
p r i n t f ( ” n % d – – – – % s n ” , t e m p – > n u m ，t e m p – > s t r ) ；
t e m p = t e m p – > n e x t ；
}
r e t u r n ;
}