胡傳福

(東莞理工學(xué)院 計(jì)算機(jī)學(xué)院，廣東東莞 523808)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 線性表L 的物理存儲(chǔ)方式

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

［2］嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu):C 語言版［M］.北京:清華大學(xué)出版社，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.