文章編號：1672-5913(2008)20-0140-05

摘 要：單鏈表是線性表的鏈?zhǔn)酱鎯Ψ绞剑瑢W(xué)生的理解和掌握將為以后學(xué)習(xí)二叉樹和圖奠定堅實的基礎(chǔ)。本文對單鏈表的存儲類型定義、頭結(jié)點問題和單鏈表長度問題進(jìn)行了分析和探討。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；單鏈表；頭結(jié)點；單鏈表長度

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

單鏈表是線性表的鏈?zhǔn)酱鎯?，它在程序設(shè)計中占有很重要的地位，學(xué)生對其理解和掌握將為以后學(xué)習(xí)二叉樹和圖奠定堅實的基礎(chǔ)。好多學(xué)校使用顏蔚敏老師編寫的《數(shù)據(jù)結(jié)構(gòu)(C語言版)》作為教材，而這本教材在講解單鏈表時給出單鏈表的有關(guān)概念后，直接給出單鏈表的存儲結(jié)構(gòu)定義，然后就講解帶頭結(jié)點的單鏈表的取元素、插入、刪除和創(chuàng)建單鏈表操作的實現(xiàn)。并沒有講解如何理解單鏈表的存儲結(jié)構(gòu)定義，為什么要用帶頭結(jié)點的單鏈表，導(dǎo)致學(xué)生對單鏈表這一結(jié)構(gòu)理解不夠透徹，也搞不清楚頭結(jié)點的主要作用是什么。對于取元素、插入、刪除操作，總是在操作結(jié)束后通過活動指針是否為空或計數(shù)器與給定位置的大小關(guān)系來判斷給定位置是否合法，這不但嚴(yán)重影響了算法的效率，也使學(xué)生覺得隱晦難懂，更增加了學(xué)生對單鏈表操作理解的難度。故筆者在本文對單鏈表的存儲類型定義、頭結(jié)點問題和鏈表長度問題進(jìn)行了分析和探討。

1 單鏈表存儲類型定義的理解

筆者在教學(xué)過程中發(fā)現(xiàn)有好多學(xué)生直到單鏈表所有操作學(xué)完也搞不清楚單鏈表到底是一個什么樣的結(jié)構(gòu)，在內(nèi)存中是如何存儲的，對單鏈表的插入、刪除等操作更是一知半解，被指針的變化弄得暈頭轉(zhuǎn)向。因此，有必要在開始就給學(xué)生講解清楚指針是怎么回事、單鏈表是如何存儲的。

1.1 指針

內(nèi)存空間是以字節(jié)為單位來存儲數(shù)據(jù)的一段區(qū)域，其中每一個字節(jié)都有一個編號，該編號稱為該字節(jié)的地址，以64M內(nèi)存為例，因為64M=216，所以為了區(qū)分216個存儲單元就需要16位二進(jìn)制數(shù)，即每一個存儲單元的地址用一個16位的二進(jìn)制數(shù)或4位十六進(jìn)制數(shù)來表示，如圖1所示。要想在內(nèi)存中找到某個數(shù)據(jù)就應(yīng)該知道它所在的內(nèi)存單元的地址。不同的數(shù)據(jù)在內(nèi)存中被分配的字節(jié)數(shù)一般是不相同的，這樣對某些類型的數(shù)據(jù)就對應(yīng)著若干個地址編號，這些地址中第一個字節(jié)的地址就稱為該數(shù)據(jù)的首地址。在C語言中，對于變量的訪問形式之一，就是先得出變量的地址，然后再通過地址對變量的值進(jìn)行訪問。例如有定義int x=20；假設(shè)編譯系統(tǒng)為變量x分配的存儲單元的地址為2000H和2001H(如圖1所示)，則變量x的首地址就是2000H，程序在執(zhí)行時根據(jù)變量名x就可以找到內(nèi)存單元2000H，然后對其值20進(jìn)行訪問。

圖1 內(nèi)存空間表示

指針是描述計算機(jī)內(nèi)存的，指針與計算機(jī)內(nèi)存單元地址之間是一一對應(yīng)的，它實質(zhì)代表了某一個內(nèi)存單元的地址。“指針變量”也是一個變量，只是這個變量中存放的是內(nèi)存單元的某一地址(即存放的是指針)。例如有定義：int *p；p=x；則表示p是一指針變量，假設(shè)編譯系統(tǒng)為變量p分配的存儲單元的地址為000FH和0010H，則在000FH和0010H兩個存儲單元中存放著變量x的首地址2000H(如圖1所示)，我們形象地稱p指向x，用圖2表示。

1.2 單鏈表的存儲類型定義

鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素，而這一組存儲單元可以是連續(xù)的也可以是不連續(xù)的，為了表示數(shù)據(jù)元素之間的邏輯關(guān)系，在存放數(shù)據(jù)元素的同時，還需存儲指示其后繼的信息，即其后繼的存儲地址(指針)，這兩部分信息就組成了鏈?zhǔn)酱鎯Ψ绞较戮€性表數(shù)據(jù)元素的存儲映像，稱為結(jié)點。結(jié)點結(jié)構(gòu)如圖3所示，其中data為數(shù)據(jù)元素，next為后繼的存儲地址，如果沒有后繼，則其next為空指針NULL。

圖2 指針與變量的指向關(guān)系

圖3 單鏈表結(jié)點結(jié)構(gòu)

結(jié)點的存儲類型定義為：

typedef struct LNode {

ElemType data; // 數(shù)據(jù)域

struct LNode *next; // 指針域

} LNode；

以“結(jié)點序列”表示的線性表稱為單鏈表，如圖4所示，以線性表中第一個數(shù)據(jù)元素a1的存儲地址作為線性表的地址，稱作線性表的頭指針。

定義一個指向LNode的指針類型typedef LNode *LinkList；然后就可以定義頭指針變量為：LinkList L；該定義語句等價于LNode *L。講解時給學(xué)生強(qiáng)調(diào)L就是一指針變量，它所指向的存儲單元中存放的是結(jié)點LNode類型的數(shù)據(jù)。例如圖5所示的單鏈表L，假設(shè)系統(tǒng)為變量L分配的存儲單元的地址為3004H～3005H，為數(shù)據(jù)10所在的結(jié)點分配的存儲單元的地址為3000H～3003H，為數(shù)據(jù)

圖4 單鏈表(a1，a2，…，an)

20所在的結(jié)點分配的存儲單元的地址為2000H～2003H，為數(shù)據(jù)30所在的結(jié)點分配的存儲單元的地址為5019H～501CH，則其存儲結(jié)構(gòu)如圖6所示。

圖5 單鏈表L

圖6 單鏈表L的存儲表示

從圖6中可以看出，根據(jù)變量名L可以找到3004H這一個存儲單元，根據(jù)其區(qū)域存儲的3000H可以找到10這一數(shù)據(jù)元素所在的存儲位置，根據(jù)存放10的同時所存放的2000H，就可以找到20這一數(shù)據(jù)元素所在的存儲位置，再根據(jù)存放20的同時所存放的5019H，就可以找到30這一數(shù)據(jù)元素所在的存儲位置，在存放30的同時存放了空指針，代表元素30沒有后繼，就不用再繼續(xù)往后找了。

對于鏈?zhǔn)酱鎯Y(jié)構(gòu)，我們關(guān)心的是結(jié)點間的邏輯關(guān)系，而不是每個結(jié)點的實際地址，所以通常用圖4和圖5這樣的形式表示單鏈表。

2 頭結(jié)點問題分析

顏蔚敏老師編寫的《數(shù)據(jù)結(jié)構(gòu)(C語言版)》在講解單鏈表時只說有時為了操作方便，在第一個結(jié)點之前虛加一個“頭結(jié)點”，以指向頭結(jié)點的指針為鏈表的頭指針，如圖7所示。該教材并沒有講解為什么要加頭結(jié)點，所以好多學(xué)生對頭結(jié)點的作用不能理解。我們在教學(xué)過程中，先給同學(xué)們講解一般單鏈表即不帶頭結(jié)點的單鏈表的表示和基本操作的實現(xiàn)，然后分析得出加頭結(jié)點的好處。

2.1 初始化不帶頭結(jié)點的單鏈表

對于不帶頭結(jié)點的單鏈表L，開始初始化為空表，即變量L的值為零，如圖8所示。

2.2 不帶頭結(jié)點的單鏈表插入操作ListInsert(L，i，e)

在前面學(xué)習(xí)線性表的抽象數(shù)據(jù)類型定義時講過ListInsert (L，i，e)的作用是在線性表的第i個位置之前插入數(shù)據(jù)元素e，也就是將數(shù)據(jù)元素插入到線性表L中作為第i個數(shù)據(jù)元素，其前提條件是L存在，且1≤i≤ListLength (L)+1。

分析：在線性表的第i(i>1)個位置之前插入數(shù)據(jù)元素e，線性表的邏輯結(jié)構(gòu)發(fā)生了變化，有序?qū)?ai-1，ai>改變?yōu)?ai-1，e>和，在單鏈表存儲結(jié)構(gòu)下，為了插入一個數(shù)據(jù)元素e，首先要生成一個數(shù)據(jù)域為e的結(jié)點，然后將其插入到單鏈表中，其指針變化如圖9所示。

圖7 帶頭結(jié)點的單鏈表

圖8 不帶頭結(jié)點的單鏈表空表表示

圖9 在單鏈表中插入結(jié)點時指針變化情況

可見，在單鏈表中插入結(jié)點只需要修改指針，若要在第i(i>1)個結(jié)點之前插入元素，修改的是第i-1個結(jié)點的指針。因此，在單鏈表中第i個結(jié)點之前進(jìn)行插入的基本操作為：找到第i-1個結(jié)點，然后修改其指向后繼的指針，此時頭指針并沒有發(fā)生任何變化。

如果i=1，插入結(jié)點后，原來的第一個變成了第二個，剛插入的變成了第一個，頭指針L發(fā)生了變化，如圖10所示，因此當(dāng)i=1時，要單獨處理。

圖10 在單鏈表第一個位置前插入結(jié)點時指針變化情況

2.3 不帶頭結(jié)點的單鏈表刪除操作ListDelete(L，i，e)

在前面學(xué)習(xí)線性表的抽象數(shù)據(jù)類型定義時講過ListDelete (L，i，e)的作用是刪除線性表L中的第i個結(jié)點，用e返回其值，其前提條件是L存在，且1≤i≤ListLength(L)。

分析：刪除線性表中的第i(i>1)個數(shù)據(jù)元素，線性表的邏輯結(jié)構(gòu)發(fā)生了變化，有序?qū)?ai-1，ai>和改變?yōu)?ai-1， ai+1="">，在單鏈表存儲結(jié)構(gòu)下，其指針變化如圖11所示。

可見，在單鏈表中刪除第i(i>1)個數(shù)據(jù)元素只需要修改第i-1個結(jié)點的指針，因此其基本操作為：找到單鏈表中第i-1個結(jié)點，修改其指向后繼的指針。此時頭指針并沒有發(fā)生任何變化。

如果i=1，刪除第一個結(jié)點后，原來的第二個變成了現(xiàn)在的第一個，頭指針L發(fā)生了變化，如圖12所示，因此當(dāng)i=1時，要單獨處理。

圖11 在單鏈表中刪除結(jié)點時指針變化情況

圖12 刪除單鏈表中第一個結(jié)點時指針變化情況

由以上分析可以看出，對不帶頭結(jié)點的單鏈表的第一個位置進(jìn)行插入和刪除時，頭指針L都發(fā)生了變化，而對其它位置進(jìn)行插入和刪除時，頭指針L不會受到任何影響，因此對不帶頭結(jié)點的單鏈表進(jìn)行插入和刪除時，要對第一個位置進(jìn)行單獨處理。

那么加上頭結(jié)點會怎么樣呢？

2.4 初始化帶頭結(jié)點的單鏈表

對于帶頭結(jié)點的單鏈表，初始化時要生成頭結(jié)點，并讓頭指針指向，如圖13所示。

圖13 初始化后的帶頭結(jié)點的單鏈表

2.5 帶頭結(jié)點的單鏈表插入操作ListInsert(L，i，e)

如圖14(a)所示的帶頭結(jié)點的單鏈表Lacute;，頭指針Lacute;指向頭結(jié)點，頭結(jié)點的指針域指向第一個元素結(jié)點a1，在第一個位置前插入數(shù)據(jù)元素e后，如圖13(b)所示，頭結(jié)點的指針域指向數(shù)據(jù)元素e所在的結(jié)點，數(shù)據(jù)元素e所在結(jié)點的指針域指向第一個元素結(jié)點a1。此時，頭指針Lacute;并沒有發(fā)生變化，仍然指向頭結(jié)點。

在帶頭結(jié)點的單鏈表的其它位置進(jìn)行插入時的操作與不帶頭結(jié)點的單鏈表完全相同。

2.6 帶頭結(jié)點的單鏈表刪除操作ListDelete(L，i，e)

如圖15(a)所示的帶頭結(jié)點的單鏈表L'，頭指針L'指向頭結(jié)點，頭結(jié)點的指針域指向第一個元素結(jié)點a1，刪除第一個結(jié)點后，如圖13(b)所示，頭結(jié)點的指針域指向第二個元素結(jié)點a2，此時，頭指針L'并沒有發(fā)生變化，仍然指向頭結(jié)點。

圖14 在帶頭結(jié)點的單鏈表第一個位置前插入結(jié)點時指針變化情況 圖15 刪除帶頭結(jié)點的單鏈表的第一結(jié)點時指針變化情況在帶頭結(jié)點的單鏈表的其它位置進(jìn)行刪除操作時與不帶頭結(jié)點的單鏈表完全相同。

由以上分析可以得出，如果我們把頭結(jié)點看作第0個結(jié)點，也就是第一個元素結(jié)點的前一個結(jié)點，就可以將第一個位置和其它位置的插入和刪除操作進(jìn)行統(tǒng)一，也就是在第一個元素之前插入和刪除第一個元素時不必另作判斷。另外，不論單鏈表是否為空，頭指針始終指向頭結(jié)點，不會發(fā)生變化。對于數(shù)據(jù)域為整型的單鏈表，頭結(jié)點中還可以存放鏈表長度等信息。

3 單鏈表長度問題分析

線性表的GetElem( L， i， e )、ListInsert( L， i， e )、ListDelete(L， i， e)操作都與位置i有關(guān)，因此這些操作應(yīng)該判斷給定的位置是否合法，如果不合法，就不能進(jìn)行相應(yīng)操作。順序表在處理i的合法性時比較方便，因為在順序表的定義中l(wèi)ength域指示了順序表的當(dāng)前長度，即給定順序表L后，L.length的值就是當(dāng)前順序表中的數(shù)據(jù)元素個數(shù)，所以可以在操作前通過L.length判斷給定的位置i是否合法。而對于鏈表，其定義中只包括data數(shù)據(jù)域和next指針域，那么給定鏈表L后，可以從L出發(fā)依次找到鏈表中的各個元素，但從L本身看不出當(dāng)前

鏈表中有多少個數(shù)據(jù)元素，也就不能在操作前判斷i的合法性，只能等到操作結(jié)束后通過活動指針是否為空或計數(shù)器與給定位置的大小關(guān)系來來判斷，這不僅會嚴(yán)重影響算法的效率，還使學(xué)生覺得隱晦難懂，更增加了學(xué)生對單鏈表操作理解的難度。鑒于此，筆者在此提出了帶長度的單鏈表(帶頭結(jié)點)。

3.1 帶長度的單鏈表的定義

結(jié)點類型定義為：

typedef struct LNode {

ElemType data; // 數(shù)據(jù)域

struct LNode *next; // 指針域

} LNode;

帶長度的單鏈表類型定義為：

typedef struct LLinkList {

LNode *head; //單鏈表的頭結(jié)點

int length; //單鏈表的長度

} LLinkList;

定義帶長度的單鏈表變量L\"：LLinkList L\"；如圖16所示為一帶長度的單鏈表，其長度為3。

3.2 帶長度的單鏈表的初始化操作

定義了帶長度的單鏈表L\"后，就應(yīng)對其length和head域的值進(jìn)行初始化，尤其是head域，因為head域是指針類型，不對其進(jìn)行初始化，可能會破壞系統(tǒng)數(shù)據(jù)，甚至使系統(tǒng)陷入癱瘓。具體算法如下：

圖16 帶長度的單鏈表L\"

Status InitLList (LLinkList L\" )

{//初始化帶長度的單鏈表L\"

L\".head= (LNode *)malloc(sizeof (LNode));

if (L\".head = =NULL) return(ERROR);// 沒有足夠內(nèi)存空間

L\".head ->next=NULL;

L\".length=0;

return OK;

}

3.3 帶長度的單鏈表的取元素操作

取元素操作與位置有關(guān)，所以首先應(yīng)該判斷給定位置的合法性，如果i<1或者i>L\".length，則給定位置不合法，返回錯誤；否則就到單鏈表中去尋找第i個元素(具體過程與一般單鏈表相同)。假設(shè)給定圖16所示的單鏈表，分別舉例說明：

(1) i=2。i的值大于等于1小于等于單鏈表的長度L\".length=3，位置合法，開始初始化p指向第一個元素10所在的結(jié)點，即p= L\".head->next，計數(shù)器j=1，這時j

(2) i=5。i的值大于單鏈表的長度L\".length=3，給定位置不合法，返回ERROR。

(3) i=0。i的值小于1，給定位置不合法，返回ERROR。

通過分析可知，帶長度的單鏈表取元素操作主要分為四步：

(1) 判斷i的合法性

if (i<1 || i> L\".length )

return ERROR; // 第 i 個元素不存在

(2) 初始化指針變量ｐ指向第一個結(jié)點，計數(shù)器ｊ為１。

p= L\".head→next; j=1;

(3) 不斷執(zhí)行指針ｐ后移，計數(shù)器ｊ加1，直到j(luò)等于i。

while(j

p=p→next; ++j;

}

(4) 取第 i 個數(shù)據(jù)元素，返回OK

e=p→data; return(OK);

3.4 帶長度的單鏈表的插入操作

單鏈表的插入操作中，合法的插入位置應(yīng)該是1到單鏈表長度加1，即1≤i≤L\".length+1。如果給定位置不合法，則不能進(jìn)行插入操作。在給定插入位置i合法的前提下，在線性表的第i個位置之前插入數(shù)據(jù)元素e的思想與一般帶頭結(jié)點的單鏈表相同。

帶長度的單鏈表的插入元素操作主要分為三步：

(1) 判斷位置的合法性

if (i<1 || i> L\".length+1 )

return ERROR; // 給定位置i不合法

(2) 尋找第 i-1 個結(jié)點

p= L\".head; j=0;

while(j

(3) 執(zhí)行插入操作

s=( LNode *)malloc(sizeof(LNode));

s→data=e;

s→next=p→next;

p→next=s;

L\".length++;//鏈表長度增1

3.5 帶長度的單鏈表的刪除操作

單鏈表的刪除操作中，合法的位置應(yīng)該是1到單鏈表的長度，即1≤i≤L\".length。如果給定位置不合法，則不能進(jìn)行刪除操作。在給定位置i合法的前提下，刪除線性表中的第i個數(shù)據(jù)元素思想與一般帶頭結(jié)點的單鏈表相同。

帶長度的單鏈表的刪除元素操作主要分為三步：

(1) 判斷位置的合法性

if (i<1 || i>L\".length )

return ERROR; // 給定位置i不合法

(2) 尋找第 i-1 個結(jié)點。

p= L\".head; j=0;

while(j

(3) 執(zhí)行刪除操作

q=p→next;p→next=q→next;

e=q→data;free(q);

L\".length--;//鏈表長度減1

綜上所述，帶長度的單鏈表因為有l(wèi)ength域指示當(dāng)前單鏈表中的元素個數(shù)，在進(jìn)行取元素、插入、刪除等與位置有關(guān)的操作中，可以先通過length域判斷給定的位置是否合法，如果不合法，直接返回錯誤，不用再去遍歷整個鏈表，所以其操作比一般的單鏈表效率高得多，對學(xué)生來說也比較容易理解。

4 結(jié)束語

本文對單鏈表的存儲類型定義、頭結(jié)點問題和鏈表長度問題進(jìn)行了分析和探討，將單鏈表具體的存儲結(jié)構(gòu)利用抽象化的內(nèi)存來表示，通過分析不帶頭結(jié)點單鏈表的插

入、刪除操作存在的弊端引出為什么使用頭結(jié)點，通過對比順序表與單鏈表在與位置有關(guān)的三個基本操作中的操作特點，引出帶長度的單鏈表(帶頭結(jié)點)，并利用舉例和圖示講解其操作原理，這樣不僅可以加深學(xué)生對單鏈表的理解和掌握，更能增加學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課的信心，提高學(xué)生的學(xué)習(xí)興趣和效率，使學(xué)生在整個學(xué)習(xí)過程中始終保持良好的學(xué)習(xí)情緒和活躍的思維，進(jìn)而提高學(xué)生學(xué)習(xí)的主動性和靈活運(yùn)用知識的能力，達(dá)到學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的。

參考文獻(xiàn)

[1] 嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)(C語言版)[M]．北京：清華大學(xué)出版社，2007.

[2] 范策，周世平，胡瀟琨．算法與數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]．北京：機(jī)械工業(yè)出版社，2004.

[3] Sartaj Sahni．Data Structures， Algorithms and Applications in C++[M]．北京：機(jī)械工業(yè)出版社，2004.

[4] 陳琳，鄒文軍．插入數(shù)據(jù)結(jié)點算法的研究和應(yīng)用[J]．現(xiàn)代計算機(jī)，2007，(3):9-11.

[5] 吳勝華．C語言“指針”教學(xué)之思考[J]．淮北煤炭師范學(xué)院學(xué)報，2006，27(4):86-88.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”