談“數據結構”實驗教學環節

摘要：本文闡述了“數據結構”課程教學中實驗環節的重要性，通過一道例題說明了實驗選題應該注意的基本要求以及如何通過實驗步驟加強上機的學習效果。

關鍵詞：數據結構；實驗；算法

中圖分類號：G642

文獻標識碼：B

文章編號：1672-5913(2008)06-0027-02

1實習的重要性

“數據結構”是一門理論和實踐性都很強的課程，但與實際編程又有一定的距離，在課程教學中常見的一種現象是學生理解授課內容并不困難，但一接觸到習題往往感到無從下手.理解課程內容與較好地完成習題之間存在著明顯的差距，算法題完成的質量與基本的程序設計素質的培養是密切相關的。平時的練習較偏重于如何編寫功能單一的“小”算法，涉及算法的習題較側重于局部程序設計，即如何編好“小程序”。但僅有這方面的訓練是不夠的，還應多做一些上機實習。實習中的問題往往比平時的習題要復雜得多，也更接近于實際。一般來說，實習著眼于原理與應用的結合點，使學生學會如何把書本上學到的知識用于解決實際問題。因此，實驗課是學生學習數據結構的重要環節，是將理論知識轉化為實踐的重要工具。

2實驗課選題的基本要求

在數據結構的學習過程中，學生比較困擾的是理論不能和實踐相結合，不知道學習數據結構能做什么，所以在課程講述中除了要求學生上機實現基本算法，并完成一定數量的較大的典型的程序外，更應以大量實例提高學生解決實際問題的能力。問題具有應用背景，以利于引導學生針對具體的應用問題，選擇合適的數據結構，有效地組織計算機存儲，并編寫出高質量的程序。

例如某民航線路如圖1所示，要求使用領接表存儲這個圖，分別輸出按廣度優先搜索算法和深度優先搜索算法對此圖進行遍歷所得到的結果(要求從頂點1開始遍歷，在遍歷過程中輸出相應頂點對應的城市名稱)。

圖1 民航線路模擬系統

struct EdgeNode {

int endvex;/* 相鄰頂點字段 */

PEdgeNode nextedge;/* 鏈字段 */

};

typedef struct {

/*VexType vertex;*//* 頂點信息 */

EdgeList edgelist;/* 邊表頭指針 */

} VexNode;/* 頂點表中的結點 */

typedef struct {

int n;/* 圖的頂點個數 */

VexNode vexs[MAXVEX];

} GraphList;

while ( !isEmptyQueue_seq(q) ) {

v1 = frontQueue_seq ( q ) ;

void bfs ( GraphList* g ， Vertex v ) {

Vertex v1 ， v2;

PSeqQueue q= createEmptyQueue_seq ( );

enQueue_seq ( q ，v ) ;

printf(\"%d \"，v);

visited[v] = TRUE;

deQueue_seq ( q );

v2 = firstAdjacent ( g ，v1 );

while ( v2 != NON ) {

if ( visited[v2] == FALSE ) {

enQueue_seq ( q，v2 );

visited[v2] = TRUE ;

printf(\"%d \"，v2); }

v2 = nextAdjacent ( g ， v1 ， v2 ) ; }

}

}

這道綜合實驗題考查了學生對字符串數組、鏈表、棧、隊列、圖的遍歷以及遞歸算法等知識點的理解和綜合應用能力。題目要求輸出的結果是各城市名稱，所以需要建立一個字符數組存儲各頂點所對應的城市名稱，這樣就涉及和強調了字符串這一知識點；使用鄰接表存儲圖的各個頂點，涉及到鏈表這一知識點；遞歸算法、棧和隊列的操作，則體現在圖的遍歷過程中。

這道綜合實驗題的知識面覆蓋了“數據結構”課程絕大部分的內容，充分體現了靜態數據結構與動態數據結構的結合，具有較強的綜合性。通過對綜合實驗題的練習，學生逐漸學會針對具體問題，自己選擇合適的數據邏輯結構以及有效組織這些數據的存儲結構，在實踐中真正體會到“數據結構+算法=程序”這一重要思想。

3實習的步驟

雖然“數據結構”課程中實習題的復雜度遠不如“真正的”軟件，但為了培養學生科學嚴謹的工作方法和作風，應要求他們在實習過程中遵循以下幾個實習步驟：

(1) 需求分析和抽象數據結構。充分地分析問題，指出問題完整、準確、清晰、具體的要求，明確問題要求做什么，限制條件是什么，用到哪些數據結構，需要哪些輸入數據、哪些輸出數據以及輸入、輸出數據的類型、值的范圍等。

(2) 數據類型和詳細設計。說明本程序中用到的所有抽象數據類型的定義、程序的總體框架。對每個操作寫出偽碼算法或畫出算法流程圖，并畫出模塊的調用關系圖。

(3) 程序設計和靜態檢查。在編寫程序時應避免大量使用循環嵌套和條件嵌套，沒必要以犧牲程序的清晰性和可讀性來提高算法效率，必要時加一些簡單注釋。上機之前應該認真地閱讀程序，分析程序的邏輯結構是否正確，設計測試數據(合法的和非法的)模擬計算機運行程序，并手工得出正確結果。

(4) 調試分析。調試過程中基本操作和其他算法的時間復雜度和空間復雜度的分析。

(5) 測試結果。列出測試結果，包括輸入和輸出。

(6) 附錄。打印出帶注釋的源程序。

參考文獻

[1] 嚴蔚敏，吳偉民. 數據結構[M]. 北京:清華大學出版社，1997.

[2] 嚴蔚敏，吳偉民. 數據結構題集[M]. 北京:清華大學出版社，1999.

[3] 譚浩強. C程序設計[M]. 北京:清華大學出版社，2000.