單鏈表不同建立算法研究

摘 要:單鏈表是最簡單的一類數據結構——線性表的非順序機內表示，在計算機科學以及其他研究領域都有廣泛應用。深入分析基于C++引用參數和基于C/C++指針建立單鏈表的兩類不同算法的具體實現原理。并在對后一算法常見錯誤進行深入分析的基礎上，給出兩種基于C/C++指針的單鏈表建立算法。以期對相關領域的研究及軟件開發有啟發和指導意義。

關鍵詞:單鏈表;算法;指針;引用參數

中圖分類號:TP311文獻標識碼:A

文章編號:1004-373X(2010)04-132-03

Study of Algorithms for Creating Simply-linked Linear List

XIE Juanying

(School of Computer Science，Shaanxi Normal University，Xi′an，710062，China)

Abstract:Simply-linked linear list is the physical structure of a linear list，and it can be applied in many fields.A thorough analysis is carried out on the algorithms of creating a simply-linked linear list based on the reference parameter of C++ and on the pointers of C/C++.Then the error that often occurs in the later algorithm is analyzed，and two pointer-based algorithms are presented for creating a simply-linked linear list as well.

Keywords:simply-linked linear list;algorithm;pointer;reference parameter

0 引 言

單鏈表是線性表的一種非順序存儲表示[1-5]，屬于非數值計算領域的數學模型——線性結構的范疇，是計算機科學中數據結構的一項重要研究內容，也是數學建模的一個非常重要部分，在應用軟件開發和科學研究中有著重要且廣泛的應用[6-11]。關于單鏈表的建立算法，目前存在兩種方案:采用C++中的引用參數和基于C/C++的指針。但是，基于指針的單鏈表建立算法，稍不細心，或者程序語言中變量的有效范圍、參數傳遞的方式、指針的應用等稍不留神，就會出現問題，達不到預期目標，甚至引起意想不到的錯誤。

在此結合C/C++程序設計語言中的變量有效范圍、參數傳遞方式、指針應用等，深入分析了基于C++引用參數的單鏈表建立算法和基于C/C++指針的單鏈表建立算法;剖析了常見的基于指針建立單鏈表的算法所容易犯的錯誤;給出了基于指針的兩種單鏈表建立算法，同時對他們的正確性進行了深入分析。

1 建立單鏈表的兩類不同實現方案

單鏈表建立算法所用到的類型定義:

struct Lnode;

typedef Lnode* linklist;

typedef struct Lnode

{

datatype data;//datatype可以根據實際應用需要給出具體定義

linklist next;

}LNode;

1.1 基于C++引用參數的單鏈表建立算法

1.1.1 基于C++引用參數的單鏈表建立算法描述和一個簡單的driver

void creat( linklist la)

{

p=new LNode;

p->next=NULL;

la=p;

cin>>x;

while(cin)

{

s=new LNode;

s->data=x;

s->next=la->next;

la->next=s;

cin>>x;

}

}

int main()

{

creat(l);// linklist l;

traverse(l);//訪問單鏈表

return 0;

}

1.1.2 基于C++引用參數的單鏈表建立算法實現原理分析

上面基于C++引用參數的單鏈表建立算法，由于采用了C++的引用參數作為單鏈表建立函數creat的參數，在creat函數被調用時，形參la獲得并接受了實參指針變量l的地址[10]。因此，形參la和實參l共享了同一段存儲空間，在creat函數的函數體內部對于形參la所指存儲單元內容的修改直接影響實參l的內容。即在creat函數體內對于函數形參la所指存儲單元內容的修改實際上是修改了實參l指存儲單元的內容，因此修改后的值可以被帶回主調函數，從而建立了單鏈表。

1.2 基于C/C++指針的單鏈表建立算法

1.2.1 基于C/C++指針的單鏈表建立算法的常見錯誤及其分析

void creat( linklist la)

{

p=new LNode;

p->next=NULL;

la=p;

cin>>x;

while(cin)

{

s=new LNode;

s->data=x;

s->next=la->next;

la->next=s;

cin>>x;

}

}

對應的simple driver 如下:

int main()

{

creat(l);//linklist l;

traverse(l);//訪問單鏈表

return 0;

}

上述算法不能建立單鏈表。因為creat函數參數表中的la屬于該函數的局部變量[12]。它的有效范圍只局限于其所在函數，在creat函數內對于la的改變不能被帶回主調函數。同時，C/C++函數參數的傳遞都是單方向的值傳遞，要想將在函數內部改變了的值帶回主調函數，只有讓形參接受實參的地址，在被調函數內修改實參地址中的內容，從而達到目的。這樣，就必須使用指針或引用參數。在此，實際上是需要使用指向指針相變量la的指針作為creat函數形參。因此，該creat函數不能達到建立一個帶頭結點的單鏈表l的預期目標。

1.2.2 基于C/C++指針建立單鏈表的兩種算法

算法1:creat函數的參數使用指針，即指向指針的指針。

void creat( linklist* la)

{

p=new LNode;

p->next=NULL;

*la=p;

cin>>x;

while(cin)

{

s=new LNode;

s->data=x;

s->next=(*la)->next;

(*la)->next=s;

cin>>x;

}

}

相應的簡單主調函數如下:

int main()

{

creat(l);//linklist l;

traverse(l);//訪問單鏈表

return 0;

}

特別注意:此處調用傳遞的是指針型變量l的地址[13]。這樣形參才能獲得指針性變量l的地址，對于實參l內容的改變才可以被帶回主調函數，從而實現單鏈表的建立。此處，改變的是指針l值。

算法2:增加一個獨立的初始化函數。creat函數也作相應修改。對應的simple driver也需要一些小改動。

void initiate(linklist* la)

{

(*la)=new LNode;

(*la)->next=NULL;

}

void creat(linklist la)

{

cin>>x;

while(cin)

{

s=new LNode;

s->data=x;

s->next=la->next;

la->next=s;

cin>>x;

}

}

int main()

{

initiate(l);//linklist l;

creat(l);

traverse(l);//訪問單鏈表

return 0;

}

這樣，就可以正確建立單鏈表。因為經過初始化，已經建立了一個空的帶頭結點的單鏈表，creat函數將實參l的值傳遞給形參la，la接受了實參l的值，在creat函數中修改實參l(頭指針)所指單元內的內容，即修改實參l所指單元的值，而并沒有改變實參l的值。

2 結 語

從以上單鏈表建立算法的詳細分析可見，關鍵問題還是需要深刻理解C/C++程序設計語言中的參數傳遞方式、變量有效范圍、指針等，并能靈活應用。這樣在實際應用編程中就不會出錯，也不會在調試軟件過程中出現一些莫名其妙的錯誤。

參考文獻

[1]嚴蔚敏，吳偉民.數據結構(C語言版)[M].北京:清華大學出版社，2006.

[2]耿國華.數據結構C語言描述[M].北京:高等教育出版社，2006.

[3][美] Robert L Kruse，Clovis L Tondo，Bruce P Leung.Data Structures Program Design in C[M].Second Edition.Prentice-Hall International Inc.，1998.

[4][美]William Ford，William Topp.Data Structures with C++[M].Prentice-Hall International Inc.，1997.

[5]Wikipedia，The freeencyclopedia Linked List[EB/OL].http://en.wikipedia.org/wiki/Linked-list，2008.

[6]張敬敏，王培崇，路鳳佳.道路網絡中的移動對象索引方法研究[J].計算機工程與應用，2009，45(12):144-146.

[7]孫玉強，顧玉宛，張聰品，等.基于PRAM模型的二叉樹A序列并行算法的研究[J].計算機科學，2009，36(3):256-257，294.

[8]劉小龍，楊維芳.基于最小距離簡單多邊形的Delaunay三角剖分算法[J].計算機工程與設計，2009，30(5):1 270-1 271，1 275.

[9]王小兵，段振華.框架投影時序邏輯程序設計語言中的指針[J].西安電子科技大學學報:自然科學版，2008，35(6):1 069-1 074.

[10]李廣元，唐稚松.時序邏輯語言 XYZ/E中指針的形式化表示與驗證[J].軟件學報，2000，11(3):285-292.

[11]何煦嵐，何曉嵐.基于多鏈表結構的嵌入式系統內存管理[J].計算機應用與軟件，2008，25(4):58-59，81.

[12][美]Nell Dale，Chip Weems，Mark Heading.Programming and Problem Solving with C++[M].Third Edition.Jones and Bartlett Publishers，2003.

[13][美]Brian W Kernighan，Dennis M Ritchie.The C Programming Language[M].Second Edition.Prentice-Hall International，Inc.，2008.