周張?zhí)m

摘要：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中的一種存儲(chǔ)方式，是數(shù)據(jù)結(jié)構(gòu)課程中重要的教學(xué)內(nèi)容。然而，掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)并靈活使用是不容易的。在分析平時(shí)教學(xué)中學(xué)生學(xué)習(xí)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)常出現(xiàn)的問(wèn)題的基礎(chǔ)上，分別在概念、特點(diǎn)、定義和操作四個(gè)方面探討了講授鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的方法和技巧。

關(guān)鍵詞：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)；存儲(chǔ)結(jié)構(gòu)；教學(xué)方法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）14-0110-02

在數(shù)據(jù)結(jié)構(gòu)中，無(wú)論是棧、隊(duì)列、數(shù)組等線性結(jié)構(gòu)還是廣義表、樹和圖等非線性結(jié)構(gòu)都可以使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)數(shù)據(jù)元素和關(guān)系的存儲(chǔ)，如何讓學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)，并能在實(shí)際應(yīng)用中靈活使用是數(shù)據(jù)結(jié)構(gòu)課程教學(xué)中的重點(diǎn)和難點(diǎn)。下面分別從概念、特點(diǎn)、定義和操作四個(gè)方面來(lái)探討講授鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的方法，以供教學(xué)參考。

1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的概念

掌握鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的概念是學(xué)習(xí)各種不同數(shù)據(jù)結(jié)構(gòu)的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)的前提。因此，教學(xué)中首先要讓學(xué)生明白什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。相對(duì)于可使用數(shù)組實(shí)現(xiàn)的順序存儲(chǔ)結(jié)構(gòu)來(lái)說(shuō)，學(xué)生在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前不僅對(duì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的概念是陌生的，而且大多對(duì)實(shí)現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)的基礎(chǔ)知識(shí)如結(jié)構(gòu)體、指針等也不熟練。因此，在教學(xué)中深入淺出地將鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)概念講解清楚很重要。講授時(shí)可按數(shù)據(jù)的結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)再到鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的順序從外到內(nèi)逐層深入地方式講解，以幫助學(xué)生理解概念。

1.1結(jié)構(gòu)

結(jié)構(gòu)指數(shù)據(jù)元素之間的一種或多種關(guān)系，關(guān)系可能是線性的，也可能是非線性的。常見(jiàn)的基本結(jié)構(gòu)分為四類，分別是集合、線性表、樹和圖。當(dāng)然，通常所說(shuō)的關(guān)系是指數(shù)據(jù)元素之間的邏輯關(guān)系即數(shù)據(jù)的邏輯結(jié)構(gòu)。簡(jiǎn)單地理解，結(jié)構(gòu)就是關(guān)系。

1.2存儲(chǔ)結(jié)構(gòu)

為了在計(jì)算機(jī)中實(shí)現(xiàn)操作，除了分析數(shù)據(jù)元素之間的關(guān)系即得到數(shù)據(jù)的邏輯結(jié)構(gòu)外，還要考慮它們?cè)谟?jì)算機(jī)中如何存儲(chǔ)。數(shù)據(jù)元素和關(guān)系在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。簡(jiǎn)單地理解，存儲(chǔ)結(jié)構(gòu)就是數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式。

1.3鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)記錄元素的位置來(lái)表示元素與元素之間邏輯關(guān)系的一種存儲(chǔ)結(jié)構(gòu)。比如，在線性結(jié)構(gòu)中，若兩個(gè)邏輯上相鄰的數(shù)據(jù)元素在實(shí)際存儲(chǔ)時(shí)不相鄰，則可以通過(guò)將后一個(gè)元素所在的位置記錄到前一個(gè)元素來(lái)實(shí)現(xiàn)兩個(gè)數(shù)據(jù)元素之間的前后關(guān)系。若是非線性結(jié)構(gòu)，同樣可以通過(guò)記錄位置的方式實(shí)現(xiàn)兩個(gè)元素之間的非線性關(guān)系，比如雙親和孩子的關(guān)系、鄰接點(diǎn)關(guān)系等。其中，位置是存儲(chǔ)元素的地址即指針。在靜態(tài)鏈表中，位置是數(shù)組的下標(biāo)。

2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)

數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)科學(xué)和工程的基礎(chǔ)，任何一個(gè)算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。因此，只有掌握了數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，才能根據(jù)實(shí)際情況使用合適地存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)算法。作為一種非順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)有著其自身的特點(diǎn)，掌握這些特點(diǎn)是靈活使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)并充分發(fā)揮其優(yōu)點(diǎn)的基礎(chǔ)。授課時(shí)，可以通過(guò)比喻和類比等方式幫助學(xué)生掌握其優(yōu)缺點(diǎn)。

2.1什么是鏈

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)體現(xiàn)在“鏈”字上。所謂“鏈”，可以想象為用一根繩將原本有一定關(guān)系的數(shù)據(jù)元素串起來(lái)，通過(guò)“鏈”可以訪問(wèn)與指定數(shù)據(jù)元素有關(guān)系的其它元素。舉個(gè)線性結(jié)構(gòu)的例子來(lái)說(shuō)明如何鏈接，比如，同學(xué)A的后面是同學(xué)B，即A是B前驅(qū)或者說(shuō)B是A的后繼。排座位時(shí)，為了能體現(xiàn)出兩者的前后關(guān)系，若A坐在某個(gè)位置，則可以將B直接安排在A的后面，這樣A直接往后就可以找到后面的同學(xué)B了。當(dāng)然，也可以選擇另一種方式，即B不直接坐在A的后面，而是坐在任何一個(gè)空位上，只要將他所坐的位置告訴A，這樣A同樣可以找到B了。這個(gè)例子里，兩個(gè)數(shù)據(jù)元素之間的先后關(guān)系不是在存儲(chǔ)時(shí)直接體現(xiàn)出來(lái)而是通過(guò)記錄位置完成的?？梢韵胂螅?dāng)多個(gè)數(shù)據(jù)元素都按這種方式存儲(chǔ)時(shí)就類似用一個(gè)鏈串起了所有的元素，用這種方式存儲(chǔ)的線性表就稱為鏈表。當(dāng)然，“鏈”不僅可以表示線性關(guān)系，還可以將“鏈”進(jìn)行擴(kuò)展，根據(jù)需要實(shí)現(xiàn)如樹、圖等其它更復(fù)雜的關(guān)系的表示。

2.2優(yōu)點(diǎn)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)借助地址來(lái)表示數(shù)據(jù)元素之間的關(guān)系，數(shù)據(jù)元素在存儲(chǔ)時(shí)是按非順序的方式存儲(chǔ)的，因此彌補(bǔ)了順序存儲(chǔ)結(jié)構(gòu)的不足。為使學(xué)生更清楚地了解鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)，授課時(shí)可采用與順序存儲(chǔ)結(jié)構(gòu)相比較的方式從以下兩個(gè)方面來(lái)講解。第一，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)元素時(shí)所需存儲(chǔ)單元是動(dòng)態(tài)申請(qǐng)的，不必?fù)?dān)心操作過(guò)程中隨數(shù)據(jù)量變化而引起的存儲(chǔ)空間不足或浪費(fèi)問(wèn)題。在順序存儲(chǔ)結(jié)構(gòu)中，存儲(chǔ)空間由一組連續(xù)的存儲(chǔ)單元組成，因此，存儲(chǔ)容量受限。然而，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)采用需要存儲(chǔ)一個(gè)元素就動(dòng)態(tài)申請(qǐng)一個(gè)存儲(chǔ)單元的方式，存儲(chǔ)單元可以是連續(xù)的，也可以是非連續(xù)的。第二，在插入和刪除操作時(shí)不需要移動(dòng)數(shù)據(jù)元素，并且插入、刪除操作靈活。在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，由于數(shù)據(jù)元素之間的關(guān)系是借助地址來(lái)表示的，因此在進(jìn)行插入、刪除操作時(shí)，只需要改變地址就可以實(shí)現(xiàn)數(shù)據(jù)元素之間關(guān)系的變化。相對(duì)于順序存儲(chǔ)結(jié)構(gòu)來(lái)說(shuō)，不需要將待插人的數(shù)據(jù)元素位置空出，也不需要將刪除的數(shù)據(jù)元素位置補(bǔ)上。

2.3缺點(diǎn)

除了上述優(yōu)點(diǎn)之外，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也存在一些不足之處。教學(xué)中，對(duì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)缺點(diǎn)的講解，也可以采用與順序存儲(chǔ)結(jié)構(gòu)相比較的方式從兩個(gè)方面進(jìn)行。第一，存儲(chǔ)密度低。為了能實(shí)現(xiàn)通過(guò)地址來(lái)表示數(shù)據(jù)元素之間的關(guān)系，需要將數(shù)據(jù)元素進(jìn)行封裝。以線性結(jié)構(gòu)中的單鏈表為例，除了存儲(chǔ)數(shù)據(jù)元素本身外，還要存儲(chǔ)其后一個(gè)元素的地址。因此，應(yīng)將數(shù)據(jù)元素封裝成一個(gè)結(jié)點(diǎn)，其中結(jié)點(diǎn)包含兩個(gè)域，一個(gè)是數(shù)據(jù)域，用來(lái)存儲(chǔ)數(shù)據(jù)元素值；另一個(gè)是指針域，用來(lái)存儲(chǔ)后一個(gè)元素的地址。與順序存儲(chǔ)結(jié)構(gòu)相比，存儲(chǔ)一個(gè)數(shù)據(jù)元素的代價(jià)更大，不僅需要相應(yīng)大小的空間來(lái)存儲(chǔ)數(shù)據(jù)元素，而且還需要有額外的空間來(lái)存儲(chǔ)地址。因此，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)密度相對(duì)較低。第二，由于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不是按順序方式存儲(chǔ)的，因此不能隨機(jī)存取，即數(shù)據(jù)元素必須通過(guò)“鏈”來(lái)訪問(wèn)。比如，單鏈表只有一個(gè)鏈，只能從第一個(gè)結(jié)點(diǎn)開始通過(guò)指針依次訪問(wèn)鏈表中的每一個(gè)結(jié)點(diǎn)，當(dāng)查找某個(gè)數(shù)據(jù)元素時(shí)，即使知道該元素在表中的位置，也不能像數(shù)組那樣隨機(jī)訪問(wèn)，只能從第一個(gè)結(jié)點(diǎn)開始查找并計(jì)數(shù)，當(dāng)計(jì)數(shù)到與所給位置的值相同時(shí)才能找到該元素。當(dāng)然，“鏈”的方式不同，對(duì)應(yīng)的訪問(wèn)方式也不同。比如，雙向鏈表有兩個(gè)鏈，可以通過(guò)后繼鏈訪問(wèn)表中每一個(gè)元素，同時(shí)還可以通過(guò)前驅(qū)鏈以逆序的方式依次訪問(wèn)每個(gè)元素。

3鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義

在數(shù)據(jù)結(jié)構(gòu)中，常見(jiàn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有單鏈表、循環(huán)鏈表、雙向鏈表、十字鏈表、二叉鏈表和鄰接表等，不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可用來(lái)滿足不同的數(shù)據(jù)結(jié)構(gòu)的表示和實(shí)現(xiàn)。然而，無(wú)論哪一種數(shù)據(jù)結(jié)構(gòu)，若要使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，首先要完成它在計(jì)算機(jī)中的表示，即該鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所需的結(jié)構(gòu)體類型定義。

通常，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的結(jié)構(gòu)體類型包括兩部分：一是為存儲(chǔ)數(shù)據(jù)元素而封裝成結(jié)點(diǎn)的結(jié)點(diǎn)類型，二是描述該鏈?zhǔn)浇Y(jié)構(gòu)的結(jié)構(gòu)類型。比如，在單鏈表中，為了實(shí)現(xiàn)將后一個(gè)數(shù)據(jù)元素的地址記錄到前一個(gè)數(shù)據(jù)元素中，需要將數(shù)據(jù)元素封裝成一個(gè)結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)元素的值和其后繼元素所在的地址。因此，自定義一個(gè)結(jié)構(gòu)體類型即結(jié)點(diǎn)類型struct LNode，它包含兩個(gè)域，分別為數(shù)據(jù)域data和指向下一個(gè)結(jié)點(diǎn)的指針next。設(shè)數(shù)據(jù)元素類型為ElemType，則結(jié)點(diǎn)類型定義用C語(yǔ)言描述如下：

這里的指針next在定義時(shí)采用了遞歸定義，由于指針指向的是結(jié)點(diǎn)，因此定義為結(jié)點(diǎn)類型structLNode。另外，當(dāng)所有結(jié)點(diǎn)連接成一個(gè)鏈表后，這個(gè)鏈表就構(gòu)成了單鏈表，單鏈表也需要通過(guò)定義來(lái)描述其作為一個(gè)線性表所具有的特征，比如第一個(gè)數(shù)據(jù)元素的地址、數(shù)據(jù)元素個(gè)數(shù)等。顯然，若有一個(gè)指針L指向鏈表的第一個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)或首元結(jié)點(diǎn)），則通過(guò)此指針就可以找到整個(gè)鏈表，類似于數(shù)組的首地址，這個(gè)指向鏈表的指針L稱為頭指針，頭指針指向的是結(jié)點(diǎn)，因此定義為struct LNode類型。它的類型定義如下：

struct LNode*L；

顯然，對(duì)于一個(gè)單鏈表來(lái)說(shuō)，只要有了頭指針就可以找到鏈表并訪問(wèn)所有元素。因此對(duì)整個(gè)鏈表而言，定義一個(gè)頭指針即可，其它屬性如數(shù)據(jù)元素個(gè)數(shù)可以通過(guò)計(jì)數(shù)操作來(lái)實(shí)現(xiàn)。學(xué)生在初始學(xué)習(xí)時(shí)很容易在定義指針類型上犯錯(cuò)，不清楚指針究竟該定義成什么類型。其實(shí)，指針定義成什么類型完全取決于指針指向的對(duì)象類型。比如，單鏈表中指針next的類型是結(jié)點(diǎn)類型structLNode而不是數(shù)據(jù)元素類型ElemType，因?yàn)橹羔樦赶虻氖菍?shù)據(jù)元素封裝成包含數(shù)據(jù)域和指針域的結(jié)點(diǎn)而不是一個(gè)數(shù)據(jù)元素。

4鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的操作

當(dāng)使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，常常需要實(shí)現(xiàn)創(chuàng)建、插入、刪除、查找等操作。但是，無(wú)論哪種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其多數(shù)操作的實(shí)現(xiàn)主要還是單鏈表插入、刪除操作的延伸和擴(kuò)展。因此只要熟練掌握鏈表的插入和刪除，就能實(shí)現(xiàn)其它更為復(fù)雜的操作。舉例說(shuō)明，設(shè)q指向鏈表中的結(jié)點(diǎn)A，p指向待插入的結(jié)點(diǎn)B。若要將B插入到A之后，執(zhí)行p→next=q→next和q→next=p兩條語(yǔ)句即可。為了保證能正確地完成元素的插入，實(shí)現(xiàn)插人語(yǔ)句時(shí)需滿足“先連上，后斷開”的原則，即先使用p→next=q→next將待插入的結(jié)點(diǎn)B連到鏈表中（結(jié)點(diǎn)A的后面），然后再執(zhí)行q→next=p，將A的后繼鏈從鏈表中斷開并連到B上。這兩條語(yǔ)句不能顛倒，若將兩條語(yǔ)句的順序顛倒，即先將A的指針指向B，那么A后繼鏈就斷掉了，B就無(wú)法再連接到鏈表中。因此，插人操作中需要按“先連上，再斷開”的順序進(jìn)行，只要記住了這個(gè)原則就可避免實(shí)現(xiàn)插入時(shí)出錯(cuò)。

當(dāng)實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的刪除操作時(shí)，執(zhí)行語(yǔ)句也很簡(jiǎn)單。設(shè)p指向鏈表中的結(jié)點(diǎn)A，若要?jiǎng)h除A后面的結(jié)點(diǎn)B，執(zhí)行p→next=p→next→next即可。但是，實(shí)際操作中，往往還需要將刪除結(jié)點(diǎn)的元素值帶回，因此多引入一個(gè)指針q，讓q先指向待刪除的結(jié)點(diǎn)B，即執(zhí)行q=p→next，然后再執(zhí)行p→next=q→next，將B從鏈表中刪除。這樣，即使B已經(jīng)從鏈表中刪除，但是結(jié)點(diǎn)B還是由q指向，因?yàn)锽的地址存在q中，此時(shí)只要在釋放q之前把q→data賦值給某個(gè)變量就可以通過(guò)該變量繼續(xù)使用刪除的數(shù)據(jù)元素。因此，在刪除操作中，由被刪除的數(shù)據(jù)元素值是否還需要使用來(lái)決定刪除語(yǔ)句。如果不需要，執(zhí)行p→next=p→next→next即可。但是，若還需要使用被刪除的元素值，則多引入一個(gè)輔助的指針q，同時(shí)執(zhí)行q=p→next和p→next=q→next兩條語(yǔ)句。

相對(duì)單鏈表來(lái)說(shuō)，其它的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可能在指針域或數(shù)據(jù)域擴(kuò)充后有更為復(fù)雜的操作。然而，只要將最基本的單鏈表的插入和刪除操作掌握好，就可以在實(shí)現(xiàn)其它鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)操作時(shí)輕松應(yīng)對(duì)。

5結(jié)束語(yǔ)

在處理數(shù)據(jù)時(shí)，不僅要學(xué)會(huì)分析數(shù)據(jù)的邏輯結(jié)構(gòu)，還應(yīng)能使用合適的存儲(chǔ)結(jié)構(gòu)來(lái)高效地實(shí)現(xiàn)算法。在數(shù)據(jù)結(jié)構(gòu)中，盡管有多種不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如單鏈表、雙鏈表、循環(huán)鏈表、二叉鏈表、鄰接表和十字鏈表等，但這些存儲(chǔ)結(jié)構(gòu)畢竟是有限的，不一定能滿足實(shí)際應(yīng)用的需求。因此，學(xué)習(xí)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是學(xué)習(xí)借助地址表示數(shù)據(jù)元素之間關(guān)系的思維方法，即學(xué)習(xí)“鏈?zhǔn)健彼季S。當(dāng)用“鏈?zhǔn)健彼季S解決存儲(chǔ)問(wèn)題時(shí)，即使沒(méi)有已有的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可供使用，也能根據(jù)需要去自行設(shè)計(jì)。