“數據結構”課程中算法實現的學習方法研究*

李燕

摘 要： 數據結構課程以算法描述為基礎詮釋了各種具體數據結構的概念和特點，而算法的實現則用更加直觀的方式鞏固了所學理論知識。文章結合數據結構的教學實踐，總結學生實現算法遇到的普遍性問題，進而提出一種“三步曲”的數據結構算法實現學習方法。通過在教學實踐中實際應用發現，該方法可以有效地幫助學生提高算法轉化的效率。

關鍵詞： 數據結構； 算法實現； 教學實踐； 三步曲； 學習方法

中圖分類號：G642 文獻標志碼：A 文章編號：1006-8228（2014）11-52-03

Research on study method of algorithm implementation in data structure course

Li Yan

（College of Information and Engineering， Nanjing University of Finance and Economics， Nanjing， Jiangsu 210003， China）

Abstract： The concept and characteristics of various specific data structures are illustrated via algorithm description in data structure course. The speculative knowledge can be enhanced by algorithm implementation within an intuitive way. Combined with the teaching practice of data structure， the common problems are summarized， which are encountered by students in algorithm implementation practice. A "three-step" study method for data structure algorithm implementation is proposed. The method can significantly improve the efficiency of algorithm conversion by applying it to teaching practice.

Key words： data structure； algorithm implementation； teaching practice； three-step； study method

0 引言

數據結構是計算機專業一門重要的專業基礎課，旨在教會學生抽象出問題的邏輯結構，選擇有效的存儲結構，從而編寫出高效的程序。實際教學中，大多通過類高級語言（諸如C，C++，Java）的算法描述介紹各種具體數據結構的概念和特點。因此，讓學生在理論學習的基礎上實現課程中涉及的各類算法可以有效地幫助學生消化鞏固所學知識，這也是數據結構教學配備實驗環節的主要原因之一。

然而在實際教學中發現，很多學生并不能有效地將偽代碼描述的算法轉化為可執行程序，在某一個算法轉化中遇到的問題會在實現其他算法時重復出現。這其中不乏對算法本身理解不充分的因素，但更多的原因卻在于缺少系統的算法實現學習方法。因此，本文對數據結構實際教學中學生實現算法遇到的各種問題進行歸納，研究數據結構算法實現的學習方法，為實際教學提供一定的借鑒。

1 普遍性問題歸納

在數據結構實際教學中，學生實現算法的過程會出現各式各樣的問題，其中很多問題存在著普遍性，即多數學生在同一算法或一個學生在不同算法的實現中會遇到的問題一般具有普遍性。下面對這些普遍性問題進行歸納，為學習方法的研究奠定基礎。

1.1 全局層面的問題

這里所謂全局層面指的是學生在實現算法時所采取的整體套路。這個層面存在的普遍性問題有兩個。

⑴ 照搬照抄。實際中發現很多學生在實現一個算法時不加以思考，直接把書本上的偽代碼描述照搬至程序編輯器中。而這其中的大部分學生通常也明白這樣的程序是無法運行的，所以他們會在其上根據編譯的錯誤提示不斷進行修改。對于一些簡短的程序，這樣的方法或許還可行，但是只要算法稍微復雜，學生很少能通過這樣的方法將算法有效地實現。

⑵ 盲目追求全面至錯誤累積。數據結構中很多算法往往涉及到多個環環相扣的子算法，一個子算法如果無法正確實現則會直接影響后續問題的解決。很多學生面對這樣的算法就會盲目追求算法的全面性，在一些子算法沒有成功實現的情況又繼續編寫后續程序，使得錯誤越積越多直至最后很難找出算法無法實現的根源所在。例如，數據結構中求有向網上關鍵路徑的算法需要先進行拓撲排序，在確定有向網中無回路的基礎上進行關鍵路徑的求解。如果無法正確實現拓撲排序算法而繼續嘗試實現關鍵路徑算法，則只會使得錯誤不斷累積。

1.2 技術層面的問題

實際算法實現中，除了上述全局觀問題外，技術層面的問題更是層出不窮。結合教學實踐歸納出技術層面的普遍性問題如下。

⑴ 常量和數據類型名稱的定義問題。偽代碼描述的各類算法中可能直接使用了一些自定義的常量和數據類型名稱，例如條件為真時返回True、定義某個變量的類型為Status，一部分學生在實現算法時就直接使用了這些在高級語言中可能并不存在的名稱致使算法實現出現問題，而另外一部分學生可能注意到了這個問題，會將算法中出現的不合法名稱進行修改，但是由于這些常量和數據類型名稱可能在多處出現，一處的疏忽則會導致算法無法實現并且還很難察覺。

⑵ 變量的定義問題。為了方便起見，數據結構算法描述中常在需要時直接使用一個變量而并沒有對其定義。在具體算法實現時，學生往往因忽略這些變量的定義而出現錯誤。

⑶ 子函數的功能實現問題。數據結構中很多算法的實現需要基于一些子函數，而在偽代碼描述中可能直接調用了這些沒有函數體的函數。具體實現時，很多學生并沒有考慮這些子函數的功能實現而使得算法實現遇到問題。

⑷ 語句規范性問題。數據結構課程中的算法描述，旨在通過簡潔的方式讓學生了解算法的精髓，而其中的一些語句并不符合實際的語法規范，但這些語句可能與規范的語句非常類似，使得學生在學習中極易發生混淆。例如算法中經常出現的輸入一個字符型變量ch的語句可能描述scanf（&ch），而實際規范的語句應為scanf（"%c"，&ch）。

⑸ 指針變量的定義問題。指針是數據結構算法中頻繁出現的一個重要元素，指針實際是一個地址常量，它指示的是一個數據結構的首地址，因而用它來描述具體的數據結構更加明確。而指針變量則是一個可以被賦予不同指針值的變量，與指針的概念是有嚴格意義上的區別的。在數據結構教學實踐中，學生普遍對這一概念理解不好，在指針變量的使用時常出現錯誤。具體而言，數據結構算法描述中，常會出現如下的結構體類型定義：

typedef struct BiTNode {

ElemType data；

struct BiTNode *lchild， *rchild；

} BiTNode， *BiTree；

上述語句描述了二叉樹中的結點結構，定義了一個結點結構體類型BiTNode，而BiTree則是二叉樹結點指針的類型名。也即，如果后續定義一個二叉樹結點指針變量T，可以描述為

BiTNode *T；

而這等價于

BiTree T；

算法實現中，學生容易混淆這兩個類型的含義，從而發生定義錯誤，影響后續的變量使用，使算法無法實現或得到不正確的結果。

⑹ 變量值返回問題。數據結構課程中的很多算法需要將子函數中變量的值返回以供后繼函數使用。在有返回值的函數中通常以如下方式定義：

Status Funcname （…， ElemType &e， …）

這實際是借用了C++語言中的參數引用調用。如果算法以C++語言實現，則可以在主調函數中直接使用Funcname （...， e， ...） 進行調用。而如若算法以C語言實現，則這樣的描述無法直接實現，需要轉換為C語言中的傳地址調用才可。實際數據結構教學中，很多教學機構都是介紹C語言版的數據結構，所以這樣不同語言之間的差異使得學生在變量返回值上容易出現問題。

⑺ 結構體分量的引用問題。數據結構算法描述中，具體的數據結構定義一般是以結構體的形式給出的，因此結構體變量的分量引用非常關鍵。而普通結構體變量和結構體指針變量對分量的引用方式是不同的。例如在上述的二叉樹結點結構體定義中，如果定義了如下兩個變量：

BiTNode T1；

BiTNode *T2；（等價于BiTree T2；）

則分量的引用形式分別為：

T1.data； T1.lchild； T1.rchild；

T2->data； T2->lchild； T2->rchild；

實際中，兩種引用方式經常交替出現，如果不加以注意，就容易出現混淆。

2 算法實現的“三步曲”學習方法

基于上述歸納，本文提出一種“三步曲”的數據結構算法實現學習方法。

第一步，縱觀全局，找出算法描述中存在的不合法常量和數據類型名稱定義并在算法實現之初對其進行規范化。這一步可以將一些冗繁的細節性問題在程序規模形成之前解決，避免在算法實現過程中反復的處理這些小問題。

第二步，在透徹理解算法思想的基礎上將算法進行模塊化劃分。具體而言，先找出算法中涉及的未實現子函數，再根據算法內部的關系將整個算法劃分為若干個子算法。

第三步，在熟練掌握一門高級語言的基礎上具體定義第二步中找出的子函數，并依次逐步實現相應子算法，使得算法實現代碼由少到多，不斷擴展，直至完整正確地實現整個算法。在具體實現算法的過程中，要特別留意上述可能出現的技術層面問題，做到變量有定義、結構體分量引用合法、常用語句規范化以及正確使用指針變量，還要特別注意變量返回值的實現。

這種“三步曲”的學習方法，一方面克服了上述的全局層面問題，即告訴學生不要照搬照抄，追求全面，而是要由小至大，不斷擴充；另一方面也提醒學生在具體實現算法的過程中應該注意普遍存在的技術問題，做到了然于胸，應對自如。相信遵循這樣的步驟，實現算法時一定會事半功倍。

3 算法實現實例說明

針對數據結構實踐教學中算法實現時存在的普遍性問題，本文所提出的“三步曲”的學習方法，其文字性的闡述可能比較抽象，下面我們通過二叉樹的先序遍歷算法實現這一實例來直觀地展示該學習方法。

二叉樹先序遍歷算法的描述可以參見文獻[1]中第6.3節的相關內容，此處不再贅述。以下基于C語言實現該算法。

第一步先將常量和數據類型定義如下：

#define OVERFLOW -2

#define OK 1

#define ERROR 0

typedef int Status

typedef char TElemType；

typedef struct BiTNode {

TElemType data；

struct BiTNode *lchild， *rchild；

} BiTNode， *BiTree；

第二步，找出算法中未定義的子函數Status Visit（TElemType e），分析出該算法應該包含二叉樹創建和二叉樹遍歷兩個子算法。

第三步，依次實現Visit函數和二叉樹的創建和遍歷子算法。具體而言，Visit函數是對每個數據元素的操作，因此最簡單的操作可實現為輸出數據元素的值。實現細節如下：

Status Visit （TElemType e） {

printf（"%c"， e）；

return OK；

}

可以看出，對于Status、TElemType以及OK這樣的常量或數據類型，由于此前已經作了全局定義，此處可以直接使用。而輸出語句也注意了其在C語言環境下的規范性。在此基礎上，可以繼續實現二叉樹的創建算法。此處以先序次序建立二叉樹（算法描述可參見[1]中算法6.4），具體實現如下：

Status CreateBiTree （BiTree *T） {

/* 按先序次序輸入二叉樹中的結點值，空格字符表示空樹，構造二叉鏈表表示的二叉樹T。*/

char ch；

scanf （"%c"， &ch）；

if （ch==′′）*T=NULL；

else {

if （！ （*T=（BiTNode*） malloc （sizeof （BiTNode））））

exit （OVERFLOW）；

（*T）->data=ch； /*生成根結點*/

CreateBiTree （&（（*T）->lchild））； /*創建左子樹*/

CreateBiTree （&（（*T）->rchild））； /*創建右子樹*/

}

return OK；

}

同樣的，由于作了全局定義，算法描述中涉及的類型和常量在實現時也不需再一一校正，而是直接使用。實現代碼中也給出了變量ch的具體定義。由于構建好的二叉樹要返回以供后繼的遍歷算法訪問，因此代碼中利用C語言的傳地址調用加以實現。具體而言，在此子算法的實現中定義函數形參為BiTree類型的指針 （即BiTree *T），后續在調用時將一個BiTree類型變量的地址作為實參傳遞過來即可 （諸如CreateBiTree （&（（*T）->rchild）））。在正確實現了二叉樹構建算法的基礎上，繼續進行二叉樹先序遍歷的算法，具體實現如下：

Status PreOrderTraverse（BiTree T， Status（*Visit）（TelemType e））

{ if （T） {

if （Visit （T->data））

if （PreOrderTraverse（T->lchild，Visit）

if （PreOrderTraverse（T->rchild，Visit） return OK；

return ERROR；

} else return OK；

}

在完成常量定義以及子函數和二叉樹創建子算法功能實現的基礎上，先序遍歷子算法的描述基本上可以直接實現了。在成功實現上述子算法，只需定義一個如下的簡單主函數作為執行入口，整個算法即可完整實現并得到正確的結果。

main（） {

BiTNode *B；

printf（"請輸入二叉樹的結點：＼n"）；

CreateBiTree（&B）；

printf （"二叉樹的先序遍歷結果如下："）；

PreOrderTraverse（B，Visit）；

printf（"＼n"）；

}

圖1 先序遍歷算法實現運行實例

圖1給出了一個上述先序遍歷算法實現的運行實例，其中圖1（a）給出了所構建二叉樹的結構，圖1（b）顯示了算法實現的運行結果。

4 結束語

本文基于數據結構課程的教學實踐，總結并歸納了學生在數據結構算法實現中容易出現的問題，提出了一種“三步曲”的學習方法。從具體的實例描述可以看出，該學習方法可以讓學生清晰明了、快速正確地實現數據結構算法，從而幫助他們更好地學習數據結構這門課程。在教學實踐中，這一方法也取得了理想的效果。

參考文獻：

[1] 嚴蔚敏，吳偉民.數據結構（C語言版）[M].清華大學出版社，2012.

[2] 楊曉波.數據結構實驗指導[M].中國電力出版社，2010.

[3] 彭軍，向毅.數據結構與算法[M].人民郵電出版社，2013.