胡傳福

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

1 數據結構課程及教學

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

2 C/C++與數據結構的關系

數據結構的主要內容之一是典型數據結構及其操作的算法實現，這與程序設計語言密切相關。

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

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

C++除了修正了許多C 語言的語法方面的缺陷之外，還提供了直接結構(類和模版)來實現抽象數據類型的通用數據結構。面向對象的方法更是將數據和對數據的操作放在一起，作為一個相互依存、不可分離的整體—對象。即對同類型對象抽象出其共性，形成類，只通過一個簡單的外部接口與外界發(fā)生關系［2］。

3 鏈表的不同實現

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

根據存儲方式的不同，單鏈表主要有以下幾種不同的實現方式:

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

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

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

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

圖1 鏈表中的結點結構圖

鏈表正是通過每個結點的指針域將線性表的n 個結點按其邏輯次序鏈接在一起的。

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

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

data :數據域，存放結點的值。next :指針域，存放結點的直接后繼的地址。

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

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

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

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

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

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

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

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

對于此類數組有關的數據結構的教學中，理解并把握一些數組的基本特性對于初學者來說是非常重要的，筆者建議在教學中應該著重強調!下面是C/C++基本數組的一些重要特性:

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

②內存塊可以通過malloc 函數或new［］來分配，對應的用free 函數或delete 釋放。

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

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

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

4 結語

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

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

［2］嚴蔚敏，吳偉民. 數據結構:C 語言版［M］.北京:清華大學出版社，2002.

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

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