摘要：本文分析了算法設(shè)計(jì)與分析在“數(shù)據(jù)結(jié)構(gòu)”教學(xué)中地位和作用，討論了與算法有關(guān)的內(nèi)容在教學(xué)中如何體現(xiàn)，總結(jié)了培養(yǎng)算法設(shè)計(jì)與分析能力的方法。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；算法設(shè)計(jì)與分析；教學(xué)方法

中圖分類號(hào)：G642文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1672-5913(2007)16-0027-03

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門重要的專業(yè)基礎(chǔ)課，在整個(gè)專業(yè)教學(xué)體系中占有重要地位。這門課程學(xué)習(xí)的好壞，對(duì)學(xué)生學(xué)好后續(xù)課程如編譯原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)等以及培養(yǎng)學(xué)生分析問題、解決問題的能力和軟件設(shè)計(jì)與開發(fā)的能力起著至關(guān)重要的作用。這門課程不僅涉及的概念多、內(nèi)容廣，而且對(duì)數(shù)學(xué)基礎(chǔ)有一定的要求，解題又需要有一定的技巧，因此，相當(dāng)一部分學(xué)生感到理解書上的基本概念并不難，基本操作的實(shí)現(xiàn)也都聽得懂，可是一到解決具體問題時(shí)就覺到困難重重，對(duì)于有一定難度的算法設(shè)計(jì)題，更是感到無(wú)從下手。因此，如何學(xué)好、怎樣教好“數(shù)據(jù)結(jié)構(gòu)”成為學(xué)生和教師普遍關(guān)注的一個(gè)問題。

1算法設(shè)計(jì)與分析在數(shù)據(jù)結(jié)構(gòu)課程中的定位

算法是對(duì)解決問題所采用的方法的描述。因此，在教學(xué)過程中應(yīng)強(qiáng)調(diào)算法的概念，在算法設(shè)計(jì)的同時(shí)培養(yǎng)算法分析的習(xí)慣，這也是這門課程中能力培養(yǎng)的核心問題。“數(shù)據(jù)結(jié)構(gòu)”課程的能力培養(yǎng)目標(biāo)應(yīng)當(dāng)是：要求學(xué)生在學(xué)完這門課程后應(yīng)能夠掌握本學(xué)科系統(tǒng)分析、解決問題的基本科學(xué)方法。這種基本科學(xué)方法在很大程度上受到教師課堂講授思想的影響。大學(xué)課堂講授的內(nèi)容主要分為兩個(gè)方面，一個(gè)是具體的知識(shí)，另一個(gè)就是分析問題和解決問題的科學(xué)方法，而后者通常要在教師的教學(xué)過程中來體現(xiàn)?？茖W(xué)的教學(xué)方法能夠使得教師所傳授的知識(shí)易于被學(xué)生有效接受和消化，同時(shí)其解決問題的思想方法也潛移默化被學(xué)生所吸納轉(zhuǎn)變?yōu)橐环N潛在的能力。因此，在“數(shù)據(jù)結(jié)構(gòu)”課程的講授中應(yīng)當(dāng)避免就概念而概念、就結(jié)構(gòu)而結(jié)構(gòu)的簡(jiǎn)單教學(xué)模式，而應(yīng)當(dāng)結(jié)合每個(gè)具體知識(shí)單元的特點(diǎn)傳授分析問題、解決問題的一般思路和方法。這就要求教師要不斷提升自己的知識(shí)層次和知識(shí)的綜合能力，并轉(zhuǎn)變觀念，使自己的地位逐漸由講解員過渡為導(dǎo)航員。這樣才能使學(xué)生由被動(dòng)的旁聽者變?yōu)閰⑴c實(shí)踐者，從而達(dá)到對(duì)學(xué)生綜合能力的培養(yǎng)目標(biāo)。

2算法設(shè)計(jì)與分析在數(shù)據(jù)結(jié)構(gòu)課程教學(xué)中的體現(xiàn)

在“數(shù)據(jù)結(jié)構(gòu)”的教學(xué)內(nèi)容中，完成同一功能有多個(gè)算法的例子比比皆是。例如串的模式匹配。假設(shè)目標(biāo)串和模式串的長(zhǎng)度分別為N和M，由于樸素的模式匹配算法需要回溯，使得算法的時(shí)間復(fù)雜度為O(N×M)，要想提高模式匹配算法的性能，就應(yīng)該著眼于消除回溯。這就引出了快速模式匹配算法(KMP算法)。消除了回溯的模式匹配算法的時(shí)間復(fù)雜度成為O(N＋M)，算法的性能得到了顯著的提高[1]。

再比如，對(duì)三元組表示的N×M矩陣的轉(zhuǎn)置運(yùn)算就可以提出三種算法[2]。首先，最簡(jiǎn)單和直觀的算法是將源三元組表中元素的行號(hào)和列號(hào)互換，然后再按照三元組要求的按行排列的要求重新排序。如果采用直接選擇或插入的方式進(jìn)行排序，那么這個(gè)過程的時(shí)間復(fù)雜度應(yīng)為O(N2×M2)。其次，注意到源三元組中的列就是目的三元組中的行這一特點(diǎn)，引出第二個(gè)算法?？梢钥紤]對(duì)源三元組進(jìn)行多趟掃描，第一趟處理源三元組中第1列元素，第二趟處理源三元組中第2列元素，……，第M趟處理源三元組中第M列元素，第k趟掃描將源三元組中第k列的元素順次復(fù)制到目的三元組中。這個(gè)處理過程的時(shí)間復(fù)雜度是O(N×M2)，優(yōu)于前一種算法。第二個(gè)算法還可以進(jìn)一步優(yōu)化嗎？答案是肯定的。換一種思路來考慮，就可以提出第三種算法(快速轉(zhuǎn)置算法)：首先計(jì)算出源三元組中每一個(gè)元素在目的三元組中的位置，然后依次將源三元組中的元素按照預(yù)先計(jì)算出的位置放置在目的三元組中。這個(gè)過程只需先后掃描源三元組兩次，時(shí)間復(fù)雜度為O(N×M)。當(dāng)然，為了存放位置信息，需要一定的額外存儲(chǔ)空間。

按照對(duì)算法的效率分析來對(duì)教學(xué)內(nèi)容進(jìn)行總結(jié)和歸納，是培養(yǎng)學(xué)生算法分析能力的另一種方式。對(duì)于數(shù)據(jù)的排序，通常是按照插入、選擇、交換等分類進(jìn)行教學(xué)，在對(duì)這一部分內(nèi)容進(jìn)行總結(jié)時(shí)，則可按算法的時(shí)間性能進(jìn)行歸類。在對(duì)N個(gè)元素進(jìn)行排序時(shí)，直接選擇、插入和冒泡排序算法都是通過兩重循環(huán)來實(shí)現(xiàn)的，思路直觀、簡(jiǎn)單，但效率不高(O(N2))。采用“分而治之”的思想，可以引出快速、堆和歸并排序三種算法，它們的效率都可達(dá)到O(Nlog2N)。通過對(duì)比較樹的分析，推導(dǎo)出基于比較的算法的最好平均時(shí)間性能為O(Nlog2N)，由此得出結(jié)論：要想得到效率更高的排序算法，就不能采用基于比較的方法。順著這個(gè)思路，可以進(jìn)一步介紹具有線性時(shí)間復(fù)雜度的基數(shù)排序和計(jì)數(shù)排序算法?？梢?，在這里，算法的效率分析是主線，順著這根主線，可以很好地把排序的所有算法串在一起，使學(xué)生能夠較好地把握住排序的主要教學(xué)內(nèi)容。

對(duì)于涉及到算法分析的練習(xí)，按題目的難易程度，可以分為三種類型：

(1) 給出算法或程序代碼段，要求分析其時(shí)間復(fù)雜度。這一類問題的難點(diǎn)是對(duì)遞歸算法的分析，通常應(yīng)該采用遞推法。具體方法是：逐次展開等式右邊的函數(shù)項(xiàng)，最終得到一個(gè)收斂的級(jí)數(shù)，最后對(duì)該級(jí)數(shù)求和。例如，對(duì)求解Hanoi塔的遞歸算法的時(shí)間復(fù)雜度進(jìn)行分析，算法的代碼段如下：

Void TOH(int n， Pole_start， Pole_goal， Pole_temp) {

if (n == 0 ) return;// 遞歸結(jié)束

TOH(n-1， start， temp， goal);// 遞歸地移動(dòng)上面的n-1個(gè)盤子

MOVE(start， goal); // 移動(dòng)最下面的盤子

TOH(n-1， temp， goal， start); // 遞歸地移動(dòng)上面的n-1個(gè)盤子

}

估計(jì)時(shí)間復(fù)雜度的遞推公式如下：

T_hanoi(n)=1+2×T_hanoi(n-1)

=1+2+4×T_hanoi(n-2)

=……

=1+2+4+……+2^n-1

注意到1+2+4+……2^n-1=2ⁿ-1，所以上述時(shí)間復(fù)雜度為O(2ⁿ)。

(2) 設(shè)計(jì)一個(gè)算法，并分析其時(shí)間復(fù)雜度。這一類問題在上一問題的基礎(chǔ)上增加了算法設(shè)計(jì)的內(nèi)容。

(3) 在給定時(shí)間復(fù)雜度的前提下設(shè)計(jì)算法。這一類問題難度較大，要求學(xué)生能夠設(shè)計(jì)出高效率的算法。例如求解如下問題：給定整型數(shù)組A[m][n]。已知A中數(shù)據(jù)在每一維方向上都按從小到大的次序排列。試設(shè)計(jì)一個(gè)算法，找出一對(duì)滿足A[i][j]=x的i，j值(如果存在的話)，要求比較次數(shù)不超過m+n。對(duì)題目做如下分析：矩陣中元素按行和按列都已排序，要求查找時(shí)間復(fù)雜度為O(m+n)，因此不能采用常規(guī)的二層循環(huán)的查找?？梢韵扔糜疑辖?i=0，j=n-1)元素與x比較，只有三種情況：一是xA[i，j]，下一步應(yīng)向i大的方向查找；三是A[i，j]=x，查找成功。否則，若下標(biāo)已超出范圍，則查找失敗，查找路線如圖1所示。對(duì)該算法的效率進(jìn)行分析，算法中查找x的路線從右上角開始，向下(當(dāng)x>A[i，j])或向左(當(dāng)x

3如何培養(yǎng)算法設(shè)計(jì)與分析的能力

(1) 明確教學(xué)目的

課堂教學(xué)的主要目的是培養(yǎng)學(xué)生分析問題和解決問題的能力，教學(xué)的組織和教學(xué)過程都應(yīng)圍繞這一點(diǎn)展開，這是無(wú)容置疑的。而對(duì)算法的討論和分析不僅是“數(shù)據(jù)結(jié)構(gòu)”教學(xué)的主要內(nèi)容之一，同時(shí)也是培養(yǎng)學(xué)生能力的有效途徑。因此，在實(shí)際教學(xué)過程中，應(yīng)突出算法的設(shè)計(jì)思想和算法分析的技巧，注重培養(yǎng)學(xué)生解決實(shí)際問題的能力。

(2) 使學(xué)生充分理解算法分析的重要性

在問題求解過程中，我們所追求的是高效率地解決問題，而不僅僅是設(shè)計(jì)出一個(gè)算法?？梢酝ㄟ^一些具體的演示使學(xué)生對(duì)算法效率有一個(gè)感性的了解。例如，將多個(gè)排序算法做成動(dòng)畫演示出來，通過對(duì)執(zhí)行算法所花費(fèi)的時(shí)間的比較，使學(xué)生明白，即使效率非常接近的算法，在問題規(guī)模達(dá)到一定程度時(shí)，求解問題所花費(fèi)的時(shí)間之間的差距也是非常明顯的。事實(shí)上，只有多項(xiàng)式時(shí)間復(fù)雜度的算法才是有意義的，許多效率低下的算法并沒有多少實(shí)際應(yīng)用上的價(jià)值。

(3) 理解典型算法是基礎(chǔ)。

學(xué)生對(duì)算法的理解是從教材中一些典型算法開始的。因此，在教學(xué)過程中，算法的設(shè)計(jì)思想是重點(diǎn)，不必過多的沉溺于具體的實(shí)現(xiàn)細(xì)節(jié)(程序設(shè)計(jì)的技巧不是這門課程的重點(diǎn))。首先，通過對(duì)典型算法的講解，使學(xué)生了解前人在問題求解過程中是如何考慮問題的，這會(huì)對(duì)學(xué)生產(chǎn)生潛移默化的影響，逐漸提高他們舉一反三的能力。其次，通過對(duì)教材中的經(jīng)典算法的分析和總結(jié)，使學(xué)生了解算法設(shè)計(jì)的一般原則和方法。比如，數(shù)組中的三元組表示的矩陣的轉(zhuǎn)置和乘法運(yùn)算以及排序中的歸并排序和計(jì)數(shù)排序等，都是借助于額外的輔助空間以得到效率更高的算法，這就反映出了一種以空間換時(shí)間的思路。再比如，遞歸是一種非常有力的工具，使用遞歸方法往往使算法的描述既簡(jiǎn)潔又易于理解，且設(shè)計(jì)出的算法易于分析，尤其在復(fù)雜算法的描述中，遞歸技術(shù)被經(jīng)常采用。遞歸本質(zhì)上反映的是一種“分而治之”的算法設(shè)計(jì)思想。

(4) 借助輔助教學(xué)手段加深對(duì)算法的理解

多媒體教學(xué)作為一種新興的現(xiàn)代教育技術(shù)已顯示出非常強(qiáng)大的生命力，它已成為深化教學(xué)改革的一種有效手段?！皵?shù)據(jù)結(jié)構(gòu)”中算法的教學(xué)難點(diǎn)之一就在于其抽象性和動(dòng)態(tài)性。學(xué)生在閱讀一些算法(特別是復(fù)雜算法)的程序描述時(shí)，常常需要充分的想象力，通過跟蹤算法的執(zhí)行過程來揣摩算法思想，這使得學(xué)習(xí)的效率低下。在有些情況下，教材上即便是給出了呈現(xiàn)關(guān)鍵概念的圖示，但細(xì)節(jié)部分還需靠學(xué)生自己的想象力去補(bǔ)充，因此仍然不能從根本上解決問題。利用可視化教學(xué)軟件可以在一定程度上化抽象為直觀，幫助學(xué)生加深對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的理解。這種軟件既可以用于課堂教學(xué)的現(xiàn)場(chǎng)演示，又可以供學(xué)生課外反復(fù)觀察體會(huì)，對(duì)提高教學(xué)質(zhì)量和效率有顯著效果[3] [4]。

(5) 實(shí)驗(yàn)的設(shè)計(jì)做到理論聯(lián)系實(shí)際

實(shí)驗(yàn)是學(xué)生提高算法設(shè)計(jì)和分析能力的重要手段。實(shí)驗(yàn)應(yīng)以綜合性實(shí)驗(yàn)為主，以培養(yǎng)學(xué)生分析問題和解決問題的能力為目標(biāo)。在實(shí)驗(yàn)過程中，學(xué)生在教師的指導(dǎo)下自主設(shè)計(jì)，充分調(diào)動(dòng)學(xué)生的主觀能動(dòng)性。學(xué)生通過實(shí)驗(yàn)，鞏固了課堂上所學(xué)到的知識(shí)，培養(yǎng)了創(chuàng)新意識(shí)和協(xié)作與團(tuán)隊(duì)精神。實(shí)驗(yàn)過程中既要求學(xué)生能夠綜合運(yùn)用課堂和書本上學(xué)到的基本理論與方法，又能夠結(jié)合實(shí)際問題進(jìn)行分析和設(shè)計(jì)。例如，在“城市交通導(dǎo)游”這樣一個(gè)綜合性實(shí)驗(yàn)中，要求在兩種方式下解決交通導(dǎo)游問題：自駕車交通方式是求解最短路徑，而搭乘公交的交通方式是求解在換乘次數(shù)最小約束下的乘車線路選擇。這里，既有典型算法的應(yīng)用，又需要在圖的基本概念和基本算法的基礎(chǔ)上考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的求解算法。這樣的綜合性實(shí)驗(yàn)可以使學(xué)生將課堂和書本上學(xué)到知識(shí)綜合地加以運(yùn)用，有效地提高學(xué)生的分析和解決實(shí)際問題的能力。

4結(jié)束語(yǔ)

數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的難點(diǎn)是算法的設(shè)計(jì)與分析。在算法設(shè)計(jì)的教學(xué)過程中，應(yīng)強(qiáng)調(diào)算法設(shè)計(jì)的思想，

不能過多的沉溺于具體的實(shí)現(xiàn)細(xì)節(jié)。應(yīng)當(dāng)明確，“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)的目標(biāo)是提高學(xué)生分析問題和解決問題的能力，這本質(zhì)上反映了教師是“授人以漁”還是“授人以魚”。只有解決好這個(gè)問題，才有可能促進(jìn)學(xué)生實(shí)現(xiàn)從知識(shí)型向能力型、從模仿型向創(chuàng)新型、從單一型向復(fù)合型人才的轉(zhuǎn)變。

參考文獻(xiàn)

[1] 殷仁昆，陶永雷. 數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++描述)[M]. 北京:清華大學(xué)出版社，1999.

[2] Ellis Horowitz， Sartaj Sahni. Fundamentals of Data Structure in C++[M]. COMPUTER SCIENCE PRESS， 1995.

[3] 陳慶章，何文秀，金冠卓，夏明. 國(guó)外可視化數(shù)據(jù)結(jié)構(gòu)教學(xué)軟件及其比較[J]. 計(jì)算機(jī)教育，2005，(2):21-23.

[4] 吳偉民. 數(shù)據(jù)結(jié)構(gòu)和算法的可視化教學(xué)研究與實(shí)踐[J]. 現(xiàn)在計(jì)算機(jī)，1999，(3):35-37.

投稿日期：2007-06-08

通信地址：南京市，東南大學(xué)計(jì)算機(jī)學(xué)院，210096

電話：025-83965001

E-mail：hjiang@seu.edu.cn