數據結構中經典算法的教學研究

摘要：闡述了經典算法的教學要結合具體實例，精心組織教學內容、巧妙設計教學方法和靈活實施教學進程，同時要遵循情景、實效和點面結合等原則的觀點。

關鍵詞：數據結構；經典算法；教學研究；教學原則

O引言

在數據結構的教學活動中，幾乎在所有的數據類型里，我們都涉及到有關經典算法的教學。由于經典算法具有特殊性、示范性和基礎性，因而它們在數據結構的教學活動中占有很重要的地位和作用。如何將經典算法的思想、方法和作用講授給學生，讓學生快速地理解和掌握經典算法的精髓和實質，使得他們牢固地掌握相關的數據結構，是每一位從事數據結構教學的教育工作者不可回避的一個現實問題。本文對數據結構中經典算法的地位和作用作了分析，同時結合具體實例，對幾個具有代表性的經典算法教學作了一定的探討。

1經典算法在數據結構中的地位和作用

數據結構中的經典算法應能夠給學習者以啟示、示范作用。因此，在篩選經典算法的時候，必須遵守以下三個原則：

(1)代表性原則。所選擇的經典算法能集中體現某個數據結構的基本特征，代表著該類數據結構的典型應用，傳承著解決這一類問題的思想。

(2)適中性原則。所選擇的經典算法既不能太簡單，但也不能太復雜，要便于學生理解。

(3)綜合性原則。經典算法要有一定的理論深度，既能有助于學習數據結構，又能有助于提高軟件設計能力。經過我們多年的教學研究和探索，結合目前數據結構中的教學內容和要求，我們篩選出以下算法作為我們在教學過程中重點講解的經典算法。

經典算法在數據結構課程教學中有著極其重要的地位和作用。具體表現在以下三個方面：

經典性數據結構中的經典算法的最重要特點就是它們的經典性。這些算法都由一些計算機界專家和學者們經過悉心研究為解決一些經典問題而設計的。這些設計者們有的因為發明相關的算法而一舉成名，并由此而獲得ACM的“圖靈獎”，大多數算法以他們的名字命名，如KMP算法、Prinm算法等。這些算法構思巧妙，有的甚至令人拍案叫絕。每個經典算法在數據結構教學中往往能起到以一當十、以點帶面的關鍵性作用。

示范性在數據結構中，經典算法有著非常重要的示范性功能。這些算法通常是結構嚴謹、步驟明確。通過對經典算法的分析和講解，一方面可以讓學生加深對數據結構基本理論和方法的理解，另一方面還可以讓學生學習程序設計方法。學生可以模仿經典算法處理問題的思想，學會舉一反三，融會貫通。

基礎性我們所選擇的經典算法，它們都是某一類數據結構的典型代表，體現了最基本的數據結構。因此從一定意義上說，學生如果掌握了某種數據結構中的典型算法，也就相應地掌握了該類型的數據結構。

2數據結構中的經典算法教學研究

我們認為，要教好數據結構中的經典算法，必須處理好以下幾個方面的問題：

(1)精心組織教學內容。對于每一個經典算法，要詳細分析算法的設計思想和所要解決的實際問題，要分析算法的重點和難點。例如KMP算法，它是對BF算法的改進。其基本思想仍然是把模式串和主串中的字符逐一進行比較。那么為什么還要有KMP算法呢?因為BF算法在最壞的情況下的時間復雜度為O(m*n)，而且這種情況在模式串和主串中含有大量的O和1這兩種字符的時候會變得更加突出。但在實際問題處理中，無論是文本處理中的查找和替換，還是圖象處理中的有關模式的識別，恰又會遇到主串的模式串中的大量的。和l的情況。因此，人們要改進算法，降低時間復雜度以提高算法的效率。在KMP算法的教學中，其難點又是什么呢?在教學過程中，通過對問題的分析，要提高算法的效率，主要是要解決在匹配過程中失配時的指針回溯問題，要想讓指向主串的指針不回溯，那就必須要確定在失配的時候主串中的字符應該和子串中的哪個字符比較。因此，KMP算法的難點就在于確定next[j]這個函數。在教學中我們就必須要把此函數作為難點內容來講解。

(2)巧妙設計教學方法。對于確定的教學內容，教學方法的選擇關系到一堂課的得失與成敗。對于經典算法的教學，教學方法的選擇尤為重要。我們認為，經典算法的教學方法主要有情境教學法、任務驅動法和案例教學法等幾種。例如講授Dijkstra算法時，可以講述人們在外出旅游時，怎么選擇最短路徑，以便節省開銷和在路途上所花費的時間。知道了出發地和目的地，當到達目的地的路線有多種選擇的時候如何來確定最短路徑的問題就自然而然地顯現出來了。這樣學生在學習Dijkstra算法時，自然就會產生濃厚的學習興趣，經過老師的激發，學生會產生積極的學習熱情，從而達到掌握該算法的目的。不管是選擇哪一種教學方法，我們都要講清楚經典算法的來龍去脈，講清楚經典算法的內容、地位和應用，讓學生牢固掌握相關知識點。在教學過程中，我們還可以綜合各種教學方法，努力創建教學情境，遵循構建主義教學模式，把深奧的算法講得通俗易懂，把抽象的知識轉化為學生的能力。

(3)靈活實施教學進程。無庸置疑，對于經典算法的講解，其重點是算法的思想。對于經典算法，我們認為主要應講述算法產生的背景、算法內容和實質以及算法的具體應用。在課時的分配上可以按照1：1：1進行。過去我們往往忽視對算法產生背景的教學，只是一帶而過，造成學生對算法的成因感到莫名其妙。在講解經典算法的產生背景時，可以對這些經典算法的設計者發明者的生平簡介、成才經歷、對計算機科學發展的偉大貢獻作一些介紹，這樣一方面可以激發學生的學習自覺性和學習興趣，另一方面也可以加深學生對該經典算法的理解。熱愛是最好的老師，學生如果對數據結構的學習充滿了熱情，有著較高的學習積極性，這當然會有助于對本課程相關內容的理解和掌握。對于算法內容的講解，一定要結合具體的實際問題。經典算法都是隨著某個具有代表性的問題而產生的，都是隨著某個問題的解決而設計的，同時也都代表著某一種典型的數據結構。因此，在教學過程中，應該把握算法的內容實質，講清楚算法的重要步驟。如Huffman算法中的Huffman樹構造的第2、3兩步：第二步，在生成森林F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和；第三步，在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。在講解這兩步時，特別要說明清楚的是，構造的新二叉樹滿足的要求是F中權值最小的兩棵子樹。這是非常關鍵的要求，因為如果新構造的二叉樹不是這樣的話，那么就不能保證WPL最小!在介紹完本算法后，還可以組織學生進行有關問題的討論。討論的內容可以有：用Huffman算法生成的Huffman樹是惟一的，如果不惟一，在什么情況下是惟一的，進一步還可以討論在c++中如何實現此算法，等等。通過上述教學活動，再通過實例，給出此算法的實際應用，這樣就能夠進一步強化學生對此算法的理解，掌握此算法的應用，同時對樹型數據結構有—個比較深刻的理解。

3經典算法的教學經驗總結

經典算法的教學目的是為了更好地讓學生理解和掌握相應的數據結構。根據多年的教學經驗，我們認為在經典算法的教學過程中要注意掌握以下幾個原則：

情景原則。在講解有關經典算法時，一定要預設好教學情景。情景教學法告訴我們，為了讓學生能夠快速牢固地掌握某一個知識點，設立相關知識的情景，刨設經典算法的具有直觀形象的問題原形，可以使得經典算法的教學變得直觀自然。這一方面有助于學生對經典算法的理解和學習，另一方面也可以把學生帶入分析問題、解決問題的殿堂。

實效原則。講解經典算法時，要時時圍繞問題的中心，力求實用。要圍繞相應的數據結構來組織教學。要讓學生一方面加深對經典算法所代表的數據結構的理解，另一方面要讓學生在解決實際問題時能舉一反三。

點面原則。點，就是經典算法往往是針對某一類典型問題而設計的，是數據結構課程教學中的某一個知識點。面，就是經典算法同時又是某一類數據結構的代表。在教學中要遵循以點代面，以點及面，以點突破，最后達到以點概面的教學效果。

總之，對于經典算法的教學，要充分體現其經典性。要針對具體的算法來設計教學情景和精心組織教學，在教學過程中要靈活實施教學進程，力求實效，從而達到教學目標的順利實現。