談“數(shù)據(jù)結(jié)構(gòu)”實驗教學環(huán)節(jié)

摘要：本文闡述了“數(shù)據(jù)結(jié)構(gòu)”課程教學中實驗環(huán)節(jié)的重要性，通過一道例題說明了實驗選題應(yīng)該注意的基本要求以及如何通過實驗步驟加強上機的學習效果。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；實驗；算法

中圖分類號：G642

文獻標識碼：B

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

1實習的重要性

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

2實驗課選題的基本要求

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

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

圖1 民航線路模擬系統(tǒng)

struct EdgeNode {

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

PEdgeNode nextedge;/* 鏈字段 */

};

typedef struct {

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

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

} VexNode;/* 頂點表中的結(jié)點 */

typedef struct {

int n;/* 圖的頂點個數(shù) */

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 ) ; }

}

}

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

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

3實習的步驟

雖然“數(shù)據(jù)結(jié)構(gòu)”課程中實習題的復雜度遠不如“真正的”軟件，但為了培養(yǎng)學生科學嚴謹?shù)墓ぷ鞣椒ê妥黠L，應(yīng)要求他們在實習過程中遵循以下幾個實習步驟：

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

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

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

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

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

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

參考文獻

[1] 嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京:清華大學出版社，1997.

[2] 嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)題集[M]. 北京:清華大學出版社，1999.

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