李　崇

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

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

中圖分類號：TP311文獻標(biāo)識碼：B

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

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

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

當(dāng)然，在創(chuàng)建鏈表之前，也要對鏈表的特點進行全面的掌握。因為所創(chuàng)建的鏈表要符合這些特點，也便于對鏈表創(chuàng)建算法的實現(xiàn)。

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

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

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

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

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

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

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

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

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

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

即:

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

p-＞key=A1;

h=p;

q=p;

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

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

p-＞key=A2;

q-＞next=p;

q=p;

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

圖2 生成節(jié)點A2

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

這種創(chuàng)建方法即為從鏈表的首結(jié)點開始，一個結(jié)點一個結(jié)點的往后連接，直到鏈表的尾結(jié)點便結(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é)點*/

else

q-＞next=p;

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

}

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

return (h);

}

在從前往后的順序創(chuàng)建方式中，首結(jié)點一但形成，就不會發(fā)生變化，而尾結(jié)點在不斷變化。因為每生成一個新結(jié)點，它都將鏈接在已經(jīng)存在的鏈表的尾部，變成新的尾結(jié)點。如果元素的輸入順序為（A1,A2,A3,…,A璶）,則通過這種方式所建立的鏈表如圖3所示：

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

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

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

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

圖4 創(chuàng)建第一個結(jié)點A1

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

圖5 創(chuàng)建第二個節(jié)點A2

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

以下通過代碼來實現(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é)點連接在已經(jīng)創(chuàng)建的

鏈表之前*/

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

}

return (h);

}

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

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

3 有序創(chuàng)建法

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

當(dāng)然，在插入第一個結(jié)點之前，整個鏈表為空。而在插入第一個結(jié)點后，鏈表中就存在一個結(jié)點了。以后的每個結(jié)點都依次插入到這個鏈表中的合適位置。從而生成有序鏈表?，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é) 語

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

參考文獻

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

［2］張福炎.程序員級高級程序員級程序設(shè)計［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語言版)［M］.北京:機械工業(yè)出版社，2008.

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

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

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

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

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

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

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