從鏈表的實現(xiàn)論C/C++與數(shù)據(jù)結(jié)構(gòu)教學

胡傳福

(東莞理工學院 計算機學院，廣東東莞 523808)

1 數(shù)據(jù)結(jié)構(gòu)課程及教學

《數(shù)據(jù)結(jié)構(gòu)》課程是計算機科學與技術(shù)的一門綜合性專業(yè)基礎(chǔ)課，是學習操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理等專業(yè)核心課程的基礎(chǔ);同時也是設(shè)計和實現(xiàn)各種系統(tǒng)軟件和大型應(yīng)用程序的重要基礎(chǔ)。由于其內(nèi)容多，難度大，針對現(xiàn)代大學生的實際情況，最初的面授課程非常重要，除了從總體上把握本課程主要內(nèi)容和作用外，更要回顧、補充有關(guān)的C/C++相關(guān)程序設(shè)計語言的基本知識。平時的面授輔導，做到概念講解簡潔，甚至跳過，可以多作相同點和不同點的比較，針對算法思想和算法描述，多用習題講解，并用多媒體課件進行實例演示，同時強調(diào)上機操作。

2 C/C++與數(shù)據(jù)結(jié)構(gòu)的關(guān)系

數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容之一是典型數(shù)據(jù)結(jié)構(gòu)及其操作的算法實現(xiàn)，這與程序設(shè)計語言密切相關(guān)。

C 語言是在國內(nèi)外廣泛使用的一種計算機語言。C 語言功能豐富、表達能力強、使用靈活方便、應(yīng)用面廣、目標程序效率高、可移植性好。特別適合于編寫系統(tǒng)軟件［1］。因此，許多高校都開設(shè)了C 語言課程。C++更是全面兼容了C，同時提供了比C 更嚴格、更安全的語法［2］。從這個意義上講，C++首先是一個更好的C。

雖然數(shù)據(jù)結(jié)構(gòu)的大部分內(nèi)容(尤其是算法及算法分析)都是描述性的、與語言無關(guān)的，但是，算法要真正實現(xiàn)還是需要特定程序設(shè)計語言的支持。由于C 語言的簡潔易懂、同時又是計算機相關(guān)專業(yè)的最基礎(chǔ)課程(高中升大學即可學習，無需先修課)，故國內(nèi)外很多數(shù)據(jù)結(jié)構(gòu)相關(guān)的書籍教材大多采用類C 語言作為數(shù)據(jù)結(jié)構(gòu)的描述語言，并把C 語言作為數(shù)據(jù)結(jié)構(gòu)算法的實現(xiàn)語言。

C++除了修正了許多C 語言的語法方面的缺陷之外，還提供了直接結(jié)構(gòu)(類和模版)來實現(xiàn)抽象數(shù)據(jù)類型的通用數(shù)據(jù)結(jié)構(gòu)。面向?qū)ο蟮姆椒ǜ菍?shù)據(jù)和對數(shù)據(jù)的操作放在一起，作為一個相互依存、不可分離的整體—對象。即對同類型對象抽象出其共性，形成類，只通過一個簡單的外部接口與外界發(fā)生關(guān)系［2］。

3 鏈表的不同實現(xiàn)

線性表一般是《數(shù)據(jù)結(jié)構(gòu)》課程的開篇章節(jié)，是一種線性結(jié)構(gòu)，同時也是一種最簡單的數(shù)據(jù)結(jié)構(gòu)。線性表可以用順序存儲結(jié)構(gòu)或鏈式存儲結(jié)構(gòu)存儲，分別叫順序表和鏈表。鏈表存儲數(shù)據(jù)元素的方法是，把存儲有數(shù)據(jù)元素的結(jié)點用指針域構(gòu)造成鏈。指針是指向物理存儲單元地址的變量，以單鏈表為例，一個數(shù)據(jù)元素域和一個指針域(指向直接后繼結(jié)點的指針)組成的結(jié)構(gòu)體稱為單鏈表的一個結(jié)點。其中，數(shù)據(jù)域用來存放數(shù)據(jù)元素，指針域用來構(gòu)造數(shù)據(jù)元素之間的關(guān)聯(lián)關(guān)系。鏈式存儲結(jié)構(gòu)的特點是，數(shù)據(jù)元素間的邏輯關(guān)系表現(xiàn)在結(jié)點的鏈接關(guān)系上［2］。

根據(jù)存儲方式的不同，單鏈表主要有以下幾種不同的實現(xiàn)方式:

1)單鏈表:用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素。用這種方法存儲的線性表簡稱線性鏈表。

存儲鏈表中結(jié)點的一組任意的存儲單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。

鏈表中結(jié)點的邏輯順序和物理順序不一定相同。

為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其直接后繼結(jié)點的地址(或位置)信息，這個信息稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)，如圖1 所示。

圖1 鏈表中的結(jié)點結(jié)構(gòu)圖

鏈表正是通過每個結(jié)點的指針域?qū)⒕€性表的n 個結(jié)點按其邏輯次序鏈接在一起的。

每一個結(jié)點只包含一個指針域的鏈表，稱為單鏈表。

為了操作方便，總是在鏈表的第一個結(jié)點之前附設(shè)一個頭結(jié)點(頭指針)head 指向第一個結(jié)點。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息(或鏈表長度等信息)。

data :數(shù)據(jù)域，存放結(jié)點的值。next :指針域，存放結(jié)點的直接后繼的地址。

單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。

例1:線性表L=(bat，cat，eat，fat，hat)

其帶頭結(jié)點的單鏈表的邏輯狀態(tài)和物理存儲方式如圖2 和圖3所示。

圖2 線性表L 的邏輯狀態(tài)

圖3 線性表L 的物理存儲方式

對于鏈表的教學，一般的教材比較注重邏輯狀態(tài)的教學，雖然說邏輯狀態(tài)才是數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容，但是，僅僅描述鏈表的邏輯狀態(tài)對于那些C/C++功底不強尤其是指針內(nèi)容把握不清的初學者來說，理解起來就存在很大的障礙。而物理存儲方式能直觀地展現(xiàn)數(shù)據(jù)在內(nèi)存中存儲的方式，以圖示的方式準確、明了地說明各數(shù)據(jù)元素之間的關(guān)系以及從一個結(jié)點訪問下一個結(jié)點的方式，而不是以一個象圖2 的箭頭那樣就能對下一結(jié)點進行訪問了。實際上，在相關(guān)指針內(nèi)容的教學上，筆者更注重強調(diào)一點，其實箭頭并不存在!

2)靜態(tài)鏈表:在鏈式存儲結(jié)構(gòu)中，實現(xiàn)數(shù)據(jù)元素之間的關(guān)系依靠指針。也可以用數(shù)組來構(gòu)造鏈表，方法是:在數(shù)組中增加一個(或兩個)指針域，這些指針域用來存放下一個(或上一個)數(shù)據(jù)元素在數(shù)組中的下標，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。由于相對于申請結(jié)點內(nèi)存空間的動態(tài)性而言，數(shù)組內(nèi)存空間的申請方式是靜態(tài)的，所以這種存儲結(jié)構(gòu)稱作靜態(tài)鏈表。由于靜態(tài)鏈表中增加的指針仿真了鏈式存儲結(jié)構(gòu)中的指針，所以靜態(tài)鏈表中的指針也稱作仿真指針［3］。

靜態(tài)鏈表在內(nèi)存中的存儲方式與圖2 有點類似，不同的地方在于它的各結(jié)點是以數(shù)組方式順序存儲的，雖然當前被訪問的節(jié)點和它的下一個節(jié)點在存儲上也不要求是地址連續(xù)的，但是，所有的節(jié)點的確一定是存儲在一個連續(xù)地址空間的內(nèi)存塊中。而單鏈表的各節(jié)點并沒有這種要求。在教學中，一般可以作為單鏈表的實現(xiàn)形式的一種對比與補充。

對于此類數(shù)組有關(guān)的數(shù)據(jù)結(jié)構(gòu)的教學中，理解并把握一些數(shù)組的基本特性對于初學者來說是非常重要的，筆者建議在教學中應(yīng)該著重強調(diào)!下面是C/C++基本數(shù)組的一些重要特性:

①對程序員來說，數(shù)組是指向一塊內(nèi)存的指針變量，其實際大小必須由程序員確定。

②內(nèi)存塊可以通過malloc 函數(shù)或new［］來分配，對應(yīng)的用free 函數(shù)或delete 釋放。

③內(nèi)存塊的大小不能改變!如果想要一塊更大的，必需重新分配一塊。但可以通過用原數(shù)組來初始化新數(shù)組以達到宏觀上數(shù)組長大的表象。

3)STL 中的向量和表:在C++語言的庫中包含有公共數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)。就是標準模版庫(Standard Template Library，簡稱STL)。使用STL 中的vector 可以很輕松的實現(xiàn)一個可增長的表的數(shù)組實現(xiàn)，list提供了表的雙向鏈表的實現(xiàn)。Vector 和list 都是用其所包含的項的類型來例示的類模版［4］。

Vector 是基本類類型，這意味著不同于C++中的基本數(shù)組，vector 可以復制并且其占用的內(nèi)存可以自動回收(通過其析構(gòu)函數(shù))。由于Vector 類自身實現(xiàn)了內(nèi)存管理，對初學者來說，并不能從其學到相關(guān)數(shù)據(jù)結(jié)構(gòu)對內(nèi)存的要求等方面的知識，建議在教學中對中高級學員進行了解性的介紹，對初學數(shù)據(jù)結(jié)構(gòu)的學生不做介紹，以免陷入誤區(qū)。

4 結(jié)語

《數(shù)據(jù)結(jié)構(gòu)》課程是計算機科學教育的一個重要組成部分，是計算機相關(guān)專業(yè)重要的理論基礎(chǔ)課程，課程中涉及的內(nèi)容很多。而程序設(shè)計語言是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)工具，也是對客觀世界的具體描述，如何在課程教學中既能傳授基本知識，又能把當代計算機科學與技術(shù)學科和計算機科學技術(shù)的新發(fā)展、新技術(shù)初步傳授給學生，而且使學生初步了解一些解決實際應(yīng)用問題的方法和手段等方面，需要不斷地探索和實踐。

［1］譚浩強. C 程序設(shè)計_新世紀計算機基礎(chǔ)教育叢書［M］.3 版.北京:清華大學出版社，2005.

［2］嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu):C 語言版［M］.北京:清華大學出版社，2002.

［3］朱戰(zhàn)立. 數(shù)據(jù)結(jié)構(gòu)—使用C 語言［M］.4 版.北京:電子工業(yè)出版社，2011.

［4］(美)Mark Allen Weiss . 數(shù)據(jù)結(jié)構(gòu)與算法分析C++描述［M］.3 版.張懷勇，譯.北京:人民郵電出版社，2007.