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

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

中圖分類號(hào)：G642

文獻(xiàn)標(biāo)識(shí)碼：B

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

1實(shí)習(xí)的重要性

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

2實(shí)驗(yàn)課選題的基本要求

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

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

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

struct EdgeNode {

int endvex;/* 相鄰頂點(diǎn)字段 */

PEdgeNode nextedge;/* 鏈字段 */

};

typedef struct {

/*VexType vertex;*//* 頂點(diǎn)信息 */

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

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

typedef struct {

int n;/* 圖的頂點(diǎn)個(gè)數(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àn)題考查了學(xué)生對(duì)字符串?dāng)?shù)組、鏈表、棧、隊(duì)列、圖的遍歷以及遞歸算法等知識(shí)點(diǎn)的理解和綜合應(yīng)用能力。題目要求輸出的結(jié)果是各城市名稱，所以需要建立一個(gè)字符數(shù)組存儲(chǔ)各頂點(diǎn)所對(duì)應(yīng)的城市名稱，這樣就涉及和強(qiáng)調(diào)了字符串這一知識(shí)點(diǎn)；使用鄰接表存儲(chǔ)圖的各個(gè)頂點(diǎn)，涉及到鏈表這一知識(shí)點(diǎn)；遞歸算法、棧和隊(duì)列的操作，則體現(xiàn)在圖的遍歷過程中。

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

3實(shí)習(xí)的步驟

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

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

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

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

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

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

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

參考文獻(xiàn)

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

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

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