數(shù)據(jù)結(jié)構(gòu)中經(jīng)典算法的教學研究

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

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；經(jīng)典算法；教學研究；教學原則

O引言

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

1經(jīng)典算法在數(shù)據(jù)結(jié)構(gòu)中的地位和作用

數(shù)據(jù)結(jié)構(gòu)中的經(jīng)典算法應(yīng)能夠給學習者以啟示、示范作用。因此，在篩選經(jīng)典算法的時候，必須遵守以下三個原則：

(1)代表性原則。所選擇的經(jīng)典算法能集中體現(xiàn)某個數(shù)據(jù)結(jié)構(gòu)的基本特征，代表著該類數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用，傳承著解決這一類問題的思想。

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

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

經(jīng)典算法在數(shù)據(jù)結(jié)構(gòu)課程教學中有著極其重要的地位和作用。具體表現(xiàn)在以下三個方面：

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

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

基礎(chǔ)性我們所選擇的經(jīng)典算法，它們都是某一類數(shù)據(jù)結(jié)構(gòu)的典型代表，體現(xiàn)了最基本的數(shù)據(jù)結(jié)構(gòu)。因此從一定意義上說，學生如果掌握了某種數(shù)據(jù)結(jié)構(gòu)中的典型算法，也就相應(yīng)地掌握了該類型的數(shù)據(jù)結(jié)構(gòu)。

2數(shù)據(jù)結(jié)構(gòu)中的經(jīng)典算法教學研究

我們認為，要教好數(shù)據(jù)結(jié)構(gòu)中的經(jīng)典算法，必須處理好以下幾個方面的問題：

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

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

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

3經(jīng)典算法的教學經(jīng)驗總結(jié)

經(jīng)典算法的教學目的是為了更好地讓學生理解和掌握相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。根據(jù)多年的教學經(jīng)驗，我們認為在經(jīng)典算法的教學過程中要注意掌握以下幾個原則：

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

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

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

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