李　崇

摘 要：鏈表是線性表的一種表現(xiàn)形式，是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)重要組成部分，而鏈表的創(chuàng)建方法直接影響人們對(duì)鏈表的理解，尤其是初學(xué)者。通過對(duì)“數(shù)據(jù)結(jié)構(gòu)”多年教學(xué)實(shí)踐經(jīng)驗(yàn)的積累，對(duì)鏈表的創(chuàng)建方法進(jìn)行了研究，并經(jīng)過歸納和總結(jié)，提出了相對(duì)容易理解的創(chuàng)建思路；形成了簡(jiǎn)明、易懂的創(chuàng)建方法。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；線性表；鏈表；順序創(chuàng)建法；逆序創(chuàng)建法；有序創(chuàng)建法

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004 373X(2009)02 117 03

Exploration of Link Table Creation Based on Data Structure

LI Chong

(Chongqing Vocational Institute of Engineering,Chongqing,400037,China)

Abstract：Link table is a form of linear table,which is an important part in data structure.Creation methods of link table helps apprehension of the link table directly,especially fornew learners.Based on many years teaching practice on "data structure",the creation methods of link table is explored.Creation methods relatively easy to understand are promoted after conclusion of the methods.

Keywords：data structure;linear list;link table;ascending creation;descending creation;in－order creation

0 引 言

線性表是數(shù)據(jù)結(jié)構(gòu)中的重要組成部分。也是程序設(shè)計(jì)中應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，它的主要特點(diǎn)是在線性序列中的每一個(gè)結(jié)點(diǎn)只有1個(gè)前驅(qū)，也只有1個(gè)后繼。線性表的存儲(chǔ)方式有順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式。用順序存儲(chǔ)方式實(shí)現(xiàn)線性表的存儲(chǔ)，使得邏輯上連續(xù)的元素在物理存儲(chǔ)上也是連續(xù)的，同時(shí)對(duì)線性表中的數(shù)據(jù)可以實(shí)現(xiàn)隨機(jī)存取，而鏈?zhǔn)酱鎯?chǔ)主要是對(duì)線性表中的相鄰元素以相鄰或不相鄰的存儲(chǔ)單元來保存。所以在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)除了保存元素信息以外，都至少還需1個(gè)指針來保存后繼結(jié)點(diǎn)的地址。也就是說，1個(gè)結(jié)點(diǎn)由1個(gè)數(shù)據(jù)域和1個(gè)指針域組成。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示線性表中的數(shù)據(jù)元素時(shí)，要先通過1個(gè)算法來創(chuàng)建1個(gè)鏈表，稱為線性鏈表。1個(gè)結(jié)點(diǎn)中只含有1個(gè)指針域的線性鏈表稱為單鏈表或單向鏈表。而含有2個(gè)指針域的鏈表稱為雙向鏈表或雙鏈表，雙鏈表的每個(gè)結(jié)點(diǎn)中1個(gè)指針指向前驅(qū)結(jié)點(diǎn)，另一個(gè)指針指向后繼結(jié)點(diǎn)。

鏈表是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)難點(diǎn)，也是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)重要組成部分。它對(duì)數(shù)據(jù)結(jié)構(gòu)中其他知識(shí)點(diǎn)的理解具有重要的意義，而鏈表的創(chuàng)建是鏈表算法中的重點(diǎn)，很多關(guān)于數(shù)據(jù)結(jié)構(gòu)的書籍都闡述了關(guān)于鏈表的創(chuàng)建方法，但都沒有一個(gè)統(tǒng)一、全面、易懂的算法。通過多年對(duì)鏈表的研究發(fā)現(xiàn)，在鏈表的創(chuàng)建過程中，總是存在一定的規(guī)律。即每個(gè)鏈表都由若干個(gè)離散的結(jié)點(diǎn)組成，這些結(jié)點(diǎn)在創(chuàng)建鏈表時(shí)總是逐個(gè)生成的，從而把這些生成的結(jié)點(diǎn)逐個(gè)地鏈接起來，形成鏈表。

因此，在算法中只需要考慮這些結(jié)點(diǎn)的鏈接方式與鏈接順序即可。在此從這些結(jié)點(diǎn)的鏈接順序進(jìn)行分析與歸納，以單向鏈表為例對(duì)鏈表的創(chuàng)建方法總結(jié)為以下3種，即順序創(chuàng)建法、逆序創(chuàng)建法、有序創(chuàng)建法。

當(dāng)然，在創(chuàng)建鏈表之前，也要對(duì)鏈表的特點(diǎn)進(jìn)行全面的掌握。因?yàn)樗鶆?chuàng)建的鏈表要符合這些特點(diǎn)，也便于對(duì)鏈表創(chuàng)建算法的實(shí)現(xiàn)。

現(xiàn)以單向鏈表為例，對(duì)鏈表的特點(diǎn)總結(jié)為如下5點(diǎn)：

（1） 記住首結(jié)點(diǎn)；

（2） 尾結(jié)點(diǎn)指向空；

（3） 在某個(gè)結(jié)點(diǎn)之前插入1個(gè)新結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；

（4） 在某個(gè)結(jié)點(diǎn)之后插入1個(gè)新結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)；

(5) 在單向鏈表中訪問任一結(jié)點(diǎn)，都必須從頭開始，直走到待訪問結(jié)點(diǎn)。

1 由前往后的順序創(chuàng)建法

在順序創(chuàng)建法中，根據(jù)單向鏈表的這些特點(diǎn)，從單向鏈表的首結(jié)點(diǎn)開始，由前往后一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的生成與鏈接，最終形成整個(gè)鏈表。其主要步驟如下：

（1） 創(chuàng)建第一個(gè)結(jié)點(diǎn)A1，并用1個(gè)指針（在此中用指針P）指向這個(gè)新結(jié)點(diǎn)，第一個(gè)被創(chuàng)建的結(jié)點(diǎn)為首結(jié)點(diǎn)，并用1個(gè)專門的指針（在此中用h）記住這個(gè)結(jié)點(diǎn)。這時(shí)，鏈表中只有一個(gè)結(jié)點(diǎn)。因此，這個(gè)結(jié)點(diǎn)也是已經(jīng)生成鏈表的尾結(jié)點(diǎn)。也用1個(gè)專門的指針(這里用q)記住這個(gè)鏈表的尾結(jié)點(diǎn)。如圖1所示。

圖1 創(chuàng)建結(jié)點(diǎn)A1

即:

p=(ND)malloc(sizeof(ND));

p-＞key=A1;

h=p;

q=p;

（2） 生成第二個(gè)結(jié)點(diǎn)A2，并用前面已經(jīng)形成鏈表的尾結(jié)點(diǎn)的指針指向這個(gè)新結(jié)點(diǎn)(即將新結(jié)點(diǎn)鏈接在已生成鏈表的尾部)。這時(shí)，這個(gè)新結(jié)點(diǎn)變成了已經(jīng)生成鏈表的新的尾結(jié)點(diǎn)。所以，鏈表的尾指針q也要指向這個(gè)新的尾結(jié)點(diǎn)。如圖2所示。

P=(ND)malloc(sizeof(ND));

p-＞key=A2;

q-＞next=p;

q=p;

（3） 重復(fù)第二步的工作，直到所有結(jié)點(diǎn)都生成。

圖2 生成節(jié)點(diǎn)A2

（4） 將尾結(jié)點(diǎn)的指針指向空。

這種創(chuàng)建方法即為從鏈表的首結(jié)點(diǎn)開始，一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的往后連接，直到鏈表的尾結(jié)點(diǎn)便結(jié)束。下面以ＴＣ為例：

typedef struct node

{

int key;

struct node *next;

}ND;

ND * create(int n)

{

ND *p, *q ,*h;

int i;

for(i=1;i＜=n;i++)

{p=(ND *)malloc (sizeof(ND));

scanf(“%d”,&(p-＞key));

if(i= =1)h=p;/*記住首結(jié)點(diǎn)*/

else

q-＞next=p;

q=p;/*記住剛插入的結(jié)點(diǎn)*/

}

p-＞next=NULL;/*尾結(jié)點(diǎn)指針針向空*/

return (h);

}

在從前往后的順序創(chuàng)建方式中，首結(jié)點(diǎn)一但形成，就不會(huì)發(fā)生變化，而尾結(jié)點(diǎn)在不斷變化。因?yàn)槊可梢粋€(gè)新結(jié)點(diǎn)，它都將鏈接在已經(jīng)存在的鏈表的尾部，變成新的尾結(jié)點(diǎn)。如果元素的輸入順序?yàn)椋ˋ1,A2,A3,…,A璶）,則通過這種方式所建立的鏈表如圖3所示：

圖3 順序創(chuàng)建方式建立的鏈表

2 由后往前的逆序創(chuàng)建法

在這種鏈表的創(chuàng)建方式中，首先也要掌握單向鏈表的特點(diǎn)，然后，根據(jù)單向鏈表的特點(diǎn)，從尾結(jié)點(diǎn)開始，逐個(gè)結(jié)點(diǎn)地向首結(jié)點(diǎn)方向鏈接，即每次生成的新結(jié)點(diǎn)，都將鏈接在已經(jīng)存在的鏈表的首部，變成新的首結(jié)點(diǎn)。而尾結(jié)點(diǎn)是第一個(gè)創(chuàng)建的結(jié)點(diǎn)。因此，首先就要考慮第一個(gè)結(jié)點(diǎn)的指針要指向空（即尾結(jié)點(diǎn)的指針指向空）。整個(gè)鏈表的創(chuàng)建步驟如下：

（1） 創(chuàng)建第1個(gè)結(jié)點(diǎn)A1。第1個(gè)被創(chuàng)建的結(jié)點(diǎn)為整個(gè)鏈表的尾結(jié)點(diǎn)。根據(jù)單向鏈表的特點(diǎn)，它的指針應(yīng)指向空。同時(shí)，鏈表中只有1個(gè)結(jié)點(diǎn)，因此這個(gè)結(jié)點(diǎn)也是已經(jīng)生成鏈表的首結(jié)點(diǎn)。并用一個(gè)專門的指針指（在此用h）向這個(gè)臨時(shí)的首結(jié)點(diǎn)。如圖4所示。

圖4 創(chuàng)建第一個(gè)結(jié)點(diǎn)A1

（2） 創(chuàng)建第2個(gè)結(jié)點(diǎn)A2，并用這個(gè)新創(chuàng)建的結(jié)點(diǎn)指向已經(jīng)生成鏈表的臨時(shí)首結(jié)點(diǎn)。這個(gè)新創(chuàng)建的結(jié)點(diǎn)A2就成為了已經(jīng)生成鏈表的新的臨時(shí)首結(jié)點(diǎn)。所以首結(jié)點(diǎn)指針h要指向這個(gè)新臨時(shí)首結(jié)點(diǎn)。如圖4所示。

圖5 創(chuàng)建第二個(gè)節(jié)點(diǎn)A2

（3） 重復(fù)第二步的工作，直到所有的結(jié)點(diǎn)都生成。

以下通過代碼來實(shí)現(xiàn)從后往前的逆序創(chuàng)建方法：

typedef struct node

{

int key;

struct node *next;

}ND;

ND * create(int n)

{ND *p,*h=NULL;

int i;

for(i=1;i＜=n;i++)

{p=(ND *)malloc (sizeof(ND));

Scanf("%d",&(p-＞key))

p-＞next=h;/*將新結(jié)點(diǎn)連接在已經(jīng)創(chuàng)建的

鏈表之前*/

h=p;/*指針h指向新創(chuàng)建的結(jié)點(diǎn)*/

}

return (h);

}

假設(shè)程序中的輸入順序?yàn)?A1,A2,…,A璶) ，則其所創(chuàng)建的鏈表如圖6所示：

圖6 逆序創(chuàng)建的鏈表

3 有序創(chuàng)建法

有序創(chuàng)建法即創(chuàng)建有序鏈表，也就是在創(chuàng)建鏈表時(shí)，就讓鏈表結(jié)點(diǎn)的關(guān)鍵字按指定順序進(jìn)行排序，使得創(chuàng)建出來的鏈表是經(jīng)過排序的有序鏈表。由于在創(chuàng)建鏈表之前，不知道輸入結(jié)點(diǎn)關(guān)鍵字的順序。因此，每生成一個(gè)結(jié)點(diǎn)，就要將它插入到已經(jīng)生成的鏈表中。為了保證有序，所以在插入新結(jié)點(diǎn)時(shí)，要在已經(jīng)存在的鏈表中查找它的合適位置，然后將該結(jié)點(diǎn)插入到所找到的位置上。

當(dāng)然，在插入第一個(gè)結(jié)點(diǎn)之前，整個(gè)鏈表為空。而在插入第一個(gè)結(jié)點(diǎn)后，鏈表中就存在一個(gè)結(jié)點(diǎn)了。以后的每個(gè)結(jié)點(diǎn)都依次插入到這個(gè)鏈表中的合適位置。從而生成有序鏈表?，F(xiàn)按從大到小的順序創(chuàng)建有序鏈表，其程序代碼如下：

typedef struct node

{

int key;

struct node *next;

}ND;

ND * insert(ND h,int k)

{ND *p,*q,*r;

P=(ND *)malloc(sizeof(ND));

p-＞key=k;

q=h;

while(q!==NULL&&q-;＞key＜k)

{r=q;q=q-＞next;}

if(q==h)h=p;

else

r-＞next=p;

p-＞next=q;

return(h);

}

Main()

{

ND *h=NULL;

int i,k,n;

scanf("%d",&n;);

for(i=1;i＜=n;i++)

{

scanf("%d",&k;);

h=insert(h,k);

}

while(h)

{printf("%4d",h-＞key);h=h-＞next;}

}

4 結(jié) 語(yǔ)

鏈表的創(chuàng)建方法思路各異，不盡相同，在此著重強(qiáng)調(diào)以簡(jiǎn)單、易懂的方式來創(chuàng)建鏈表，并且把那些復(fù)雜、多樣的思路進(jìn)行歸納，形成統(tǒng)一的創(chuàng)建模式。

參考文獻(xiàn)

［1］梁里寧.一個(gè)基于VFP的鏈表的實(shí)現(xiàn)［N］.軟件報(bào)，2007/06/04.

［2］張福炎.程序員級(jí)高級(jí)程序員級(jí)程序設(shè)計(jì)［M］.北京:清華大學(xué)出版社，1996.

［3］［美］Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析C++描述［M］.張懷勇,譯.北京:人民郵電出版社，2007.

［4］［美］Adam Drozdek.數(shù)據(jù)結(jié)構(gòu)與算法C++描述［M］.3版.鄭巖，譯.北京:清華大學(xué)出版社，2006.

［5］陳守孔.算法與數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)［M］.北京:機(jī)械工業(yè)出版社，2008.

［6］［美］Ellis Horowitz.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（C語(yǔ)言版）［M］.李建中,譯.北京:機(jī)械工業(yè)出版社，2006.

［7］［美］Thomas H Cormen,Charles E Leiserson.算法導(dǎo)論［M］.北京:機(jī)械工業(yè)出版社，2006.

［8］［美］薩尼.數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用.北京:中國(guó)水利水電出版社，2007.

［9］［美］柯林斯.數(shù)據(jù)結(jié)構(gòu)和Java集合框架.北京:清華大學(xué)出版社，2006.

［10］楊海玲.數(shù)據(jù)結(jié)構(gòu)與問題求解Java語(yǔ)言描述.北京：人民郵電出版社，2006.

［11］周偉明.多任務(wù)下的數(shù)據(jù)結(jié)構(gòu)與算法.北京：華中科技大學(xué)出版社，2006.

作者簡(jiǎn)介 李 崇 男,1975年出生，四川平昌人，講師，高級(jí)程序員。主要從事計(jì)算機(jī)軟件開發(fā)與設(shè)計(jì)的研究工作。