基于數據結構的鏈表創建方法探究

李　崇

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

關鍵詞：數據結構；線性表；鏈表；順序創建法；逆序創建法；有序創建法

中圖分類號：TP311文獻標識碼：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 引 言

線性表是數據結構中的重要組成部分。也是程序設計中應用最廣泛的一種數據結構，它的主要特點是在線性序列中的每一個結點只有1個前驅，也只有1個后繼。線性表的存儲方式有順序存儲方式和鏈式存儲方式。用順序存儲方式實現線性表的存儲，使得邏輯上連續的元素在物理存儲上也是連續的，同時對線性表中的數據可以實現隨機存取，而鏈式存儲主要是對線性表中的相鄰元素以相鄰或不相鄰的存儲單元來保存。所以在鏈式存儲結構中，每個結點除了保存元素信息以外，都至少還需1個指針來保存后繼結點的地址。也就是說，1個結點由1個數據域和1個指針域組成。鏈式存儲結構表示線性表中的數據元素時，要先通過1個算法來創建1個鏈表，稱為線性鏈表。1個結點中只含有1個指針域的線性鏈表稱為單鏈表或單向鏈表。而含有2個指針域的鏈表稱為雙向鏈表或雙鏈表，雙鏈表的每個結點中1個指針指向前驅結點，另一個指針指向后繼結點。

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

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

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

現以單向鏈表為例，對鏈表的特點總結為如下5點：

（1） 記住首結點；

（2） 尾結點指向空；

（3） 在某個結點之前插入1個新結點，必須找到該結點的前驅結點；

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

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

1 由前往后的順序創建法

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

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

圖1 創建結點A1

即:

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

p-＞key=A1;

h=p;

q=p;

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

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

p-＞key=A2;

q-＞next=p;

q=p;

（3） 重復第二步的工作，直到所有結點都生成。

圖2 生成節點A2

（4） 將尾結點的指針指向空。

這種創建方法即為從鏈表的首結點開始，一個結點一個結點的往后連接，直到鏈表的尾結點便結束。下面以ＴＣ為例：

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;/*記住首結點*/

else

q-＞next=p;

q=p;/*記住剛插入的結點*/

}

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

return (h);

}

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

圖3 順序創建方式建立的鏈表

2 由后往前的逆序創建法

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

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

圖4 創建第一個結點A1

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

圖5 創建第二個節點A2

（3） 重復第二步的工作，直到所有的結點都生成。

以下通過代碼來實現從后往前的逆序創建方法：

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;/*將新結點連接在已經創建的

鏈表之前*/

h=p;/*指針h指向新創建的結點*/

}

return (h);

}

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

圖6 逆序創建的鏈表

3 有序創建法

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

當然，在插入第一個結點之前，整個鏈表為空。而在插入第一個結點后，鏈表中就存在一個結點了。以后的每個結點都依次插入到這個鏈表中的合適位置。從而生成有序鏈表。現按從大到小的順序創建有序鏈表，其程序代碼如下：

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 結 語

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

參考文獻

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

［2］張福炎.程序員級高級程序員級程序設計［M］.北京:清華大學出版社，1996.

［3］［美］Mark Allen Weiss.數據結構與算法分析C++描述［M］.張懷勇,譯.北京:人民郵電出版社，2007.

［4］［美］Adam Drozdek.數據結構與算法C++描述［M］.3版.鄭巖，譯.北京:清華大學出版社，2006.

［5］陳守孔.算法與數據結構(C語言版)［M］.北京:機械工業出版社，2008.

［6］［美］Ellis Horowitz.數據結構基礎（C語言版）［M］.李建中,譯.北京:機械工業出版社，2006.

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

［8］［美］薩尼.數據結構、算法與應用.北京:中國水利水電出版社，2007.

［9］［美］柯林斯.數據結構和Java集合框架.北京:清華大學出版社，2006.

［10］楊海玲.數據結構與問題求解Java語言描述.北京：人民郵電出版社，2006.

［11］周偉明.多任務下的數據結構與算法.北京：華中科技大學出版社，2006.

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