“數據結構”教學過程中應重視算法設計與分析能力的培養

摘要：本文分析了算法設計與分析在“數據結構”教學中地位和作用，討論了與算法有關的內容在教學中如何體現，總結了培養算法設計與分析能力的方法。

關鍵詞：數據結構；算法設計與分析；教學方法

中圖分類號：G642文獻標識碼：B

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

“數據結構”是計算機科學與技術專業的一門重要的專業基礎課，在整個專業教學體系中占有重要地位。這門課程學習的好壞，對學生學好后續課程如編譯原理、操作系統、數據庫系統、計算機網絡等以及培養學生分析問題、解決問題的能力和軟件設計與開發的能力起著至關重要的作用。這門課程不僅涉及的概念多、內容廣，而且對數學基礎有一定的要求，解題又需要有一定的技巧，因此，相當一部分學生感到理解書上的基本概念并不難，基本操作的實現也都聽得懂，可是一到解決具體問題時就覺到困難重重，對于有一定難度的算法設計題，更是感到無從下手。因此，如何學好、怎樣教好“數據結構”成為學生和教師普遍關注的一個問題。

1算法設計與分析在數據結構課程中的定位

算法是對解決問題所采用的方法的描述。因此，在教學過程中應強調算法的概念，在算法設計的同時培養算法分析的習慣，這也是這門課程中能力培養的核心問題。“數據結構”課程的能力培養目標應當是：要求學生在學完這門課程后應能夠掌握本學科系統分析、解決問題的基本科學方法。這種基本科學方法在很大程度上受到教師課堂講授思想的影響。大學課堂講授的內容主要分為兩個方面，一個是具體的知識，另一個就是分析問題和解決問題的科學方法，而后者通常要在教師的教學過程中來體現。科學的教學方法能夠使得教師所傳授的知識易于被學生有效接受和消化，同時其解決問題的思想方法也潛移默化被學生所吸納轉變為一種潛在的能力。因此，在“數據結構”課程的講授中應當避免就概念而概念、就結構而結構的簡單教學模式，而應當結合每個具體知識單元的特點傳授分析問題、解決問題的一般思路和方法。這就要求教師要不斷提升自己的知識層次和知識的綜合能力，并轉變觀念，使自己的地位逐漸由講解員過渡為導航員。這樣才能使學生由被動的旁聽者變為參與實踐者，從而達到對學生綜合能力的培養目標。

2算法設計與分析在數據結構課程教學中的體現

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

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

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

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

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

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

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

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

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

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

}

估計時間復雜度的遞推公式如下：

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，所以上述時間復雜度為O(2ⁿ)。

(2) 設計一個算法，并分析其時間復雜度。這一類問題在上一問題的基礎上增加了算法設計的內容。

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

3如何培養算法設計與分析的能力

(1) 明確教學目的

課堂教學的主要目的是培養學生分析問題和解決問題的能力，教學的組織和教學過程都應圍繞這一點展開，這是無容置疑的。而對算法的討論和分析不僅是“數據結構”教學的主要內容之一，同時也是培養學生能力的有效途徑。因此，在實際教學過程中，應突出算法的設計思想和算法分析的技巧，注重培養學生解決實際問題的能力。

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

在問題求解過程中，我們所追求的是高效率地解決問題，而不僅僅是設計出一個算法。可以通過一些具體的演示使學生對算法效率有一個感性的了解。例如，將多個排序算法做成動畫演示出來，通過對執行算法所花費的時間的比較，使學生明白，即使效率非常接近的算法，在問題規模達到一定程度時，求解問題所花費的時間之間的差距也是非常明顯的。事實上，只有多項式時間復雜度的算法才是有意義的，許多效率低下的算法并沒有多少實際應用上的價值。

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

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

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

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

(5) 實驗的設計做到理論聯系實際

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

4結束語

數據結構課程教學的難點是算法的設計與分析。在算法設計的教學過程中，應強調算法設計的思想，

不能過多的沉溺于具體的實現細節。應當明確，“數據結構”課程教學的目標是提高學生分析問題和解決問題的能力，這本質上反映了教師是“授人以漁”還是“授人以魚”。只有解決好這個問題，才有可能促進學生實現從知識型向能力型、從模仿型向創新型、從單一型向復合型人才的轉變。

參考文獻

[1] 殷仁昆，陶永雷. 數據結構(用面向對象方法與C++描述)[M]. 北京:清華大學出版社，1999.

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

[3] 陳慶章，何文秀，金冠卓，夏明. 國外可視化數據結構教學軟件及其比較[J]. 計算機教育，2005，(2):21-23.

[4] 吳偉民. 數據結構和算法的可視化教學研究與實踐[J]. 現在計算機，1999，(3):35-37.

投稿日期：2007-06-08

通信地址：南京市，東南大學計算機學院，210096

電話：025-83965001

E-mail：hjiang@seu.edu.cn