李燕

摘 要： 數(shù)據(jù)結(jié)構(gòu)課程以算法描述為基礎(chǔ)詮釋了各種具體數(shù)據(jù)結(jié)構(gòu)的概念和特點(diǎn)，而算法的實(shí)現(xiàn)則用更加直觀的方式鞏固了所學(xué)理論知識(shí)。文章結(jié)合數(shù)據(jù)結(jié)構(gòu)的教學(xué)實(shí)踐，總結(jié)學(xué)生實(shí)現(xiàn)算法遇到的普遍性問(wèn)題，進(jìn)而提出一種“三步曲”的數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)學(xué)習(xí)方法。通過(guò)在教學(xué)實(shí)踐中實(shí)際應(yīng)用發(fā)現(xiàn)，該方法可以有效地幫助學(xué)生提高算法轉(zhuǎn)化的效率。

關(guān)鍵詞： 數(shù)據(jù)結(jié)構(gòu)； 算法實(shí)現(xiàn)； 教學(xué)實(shí)踐； 三步曲； 學(xué)習(xí)方法

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)一門重要的專業(yè)基礎(chǔ)課，旨在教會(huì)學(xué)生抽象出問(wèn)題的邏輯結(jié)構(gòu)，選擇有效的存儲(chǔ)結(jié)構(gòu)，從而編寫出高效的程序。實(shí)際教學(xué)中，大多通過(guò)類高級(jí)語(yǔ)言（諸如C，C++，Java）的算法描述介紹各種具體數(shù)據(jù)結(jié)構(gòu)的概念和特點(diǎn)。因此，讓學(xué)生在理論學(xué)習(xí)的基礎(chǔ)上實(shí)現(xiàn)課程中涉及的各類算法可以有效地幫助學(xué)生消化鞏固所學(xué)知識(shí)，這也是數(shù)據(jù)結(jié)構(gòu)教學(xué)配備實(shí)驗(yàn)環(huán)節(jié)的主要原因之一。

然而在實(shí)際教學(xué)中發(fā)現(xiàn)，很多學(xué)生并不能有效地將偽代碼描述的算法轉(zhuǎn)化為可執(zhí)行程序，在某一個(gè)算法轉(zhuǎn)化中遇到的問(wèn)題會(huì)在實(shí)現(xiàn)其他算法時(shí)重復(fù)出現(xiàn)。這其中不乏對(duì)算法本身理解不充分的因素，但更多的原因卻在于缺少系統(tǒng)的算法實(shí)現(xiàn)學(xué)習(xí)方法。因此，本文對(duì)數(shù)據(jù)結(jié)構(gòu)實(shí)際教學(xué)中學(xué)生實(shí)現(xiàn)算法遇到的各種問(wèn)題進(jìn)行歸納，研究數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)的學(xué)習(xí)方法，為實(shí)際教學(xué)提供一定的借鑒。

1 普遍性問(wèn)題歸納

在數(shù)據(jù)結(jié)構(gòu)實(shí)際教學(xué)中，學(xué)生實(shí)現(xiàn)算法的過(guò)程會(huì)出現(xiàn)各式各樣的問(wèn)題，其中很多問(wèn)題存在著普遍性，即多數(shù)學(xué)生在同一算法或一個(gè)學(xué)生在不同算法的實(shí)現(xiàn)中會(huì)遇到的問(wèn)題一般具有普遍性。下面對(duì)這些普遍性問(wèn)題進(jìn)行歸納，為學(xué)習(xí)方法的研究奠定基礎(chǔ)。

1.1 全局層面的問(wèn)題

這里所謂全局層面指的是學(xué)生在實(shí)現(xiàn)算法時(shí)所采取的整體套路。這個(gè)層面存在的普遍性問(wèn)題有兩個(gè)。

⑴ 照搬照抄。實(shí)際中發(fā)現(xiàn)很多學(xué)生在實(shí)現(xiàn)一個(gè)算法時(shí)不加以思考，直接把書本上的偽代碼描述照搬至程序編輯器中。而這其中的大部分學(xué)生通常也明白這樣的程序是無(wú)法運(yùn)行的，所以他們會(huì)在其上根據(jù)編譯的錯(cuò)誤提示不斷進(jìn)行修改。對(duì)于一些簡(jiǎn)短的程序，這樣的方法或許還可行，但是只要算法稍微復(fù)雜，學(xué)生很少能通過(guò)這樣的方法將算法有效地實(shí)現(xiàn)。

⑵ 盲目追求全面至錯(cuò)誤累積。數(shù)據(jù)結(jié)構(gòu)中很多算法往往涉及到多個(gè)環(huán)環(huán)相扣的子算法，一個(gè)子算法如果無(wú)法正確實(shí)現(xiàn)則會(huì)直接影響后續(xù)問(wèn)題的解決。很多學(xué)生面對(duì)這樣的算法就會(huì)盲目追求算法的全面性，在一些子算法沒(méi)有成功實(shí)現(xiàn)的情況又繼續(xù)編寫后續(xù)程序，使得錯(cuò)誤越積越多直至最后很難找出算法無(wú)法實(shí)現(xiàn)的根源所在。例如，數(shù)據(jù)結(jié)構(gòu)中求有向網(wǎng)上關(guān)鍵路徑的算法需要先進(jìn)行拓?fù)渑判?，在確定有向網(wǎng)中無(wú)回路的基礎(chǔ)上進(jìn)行關(guān)鍵路徑的求解。如果無(wú)法正確實(shí)現(xiàn)拓?fù)渑判蛩惴ǘ^續(xù)嘗試實(shí)現(xiàn)關(guān)鍵路徑算法，則只會(huì)使得錯(cuò)誤不斷累積。

1.2 技術(shù)層面的問(wèn)題

實(shí)際算法實(shí)現(xiàn)中，除了上述全局觀問(wèn)題外，技術(shù)層面的問(wèn)題更是層出不窮。結(jié)合教學(xué)實(shí)踐歸納出技術(shù)層面的普遍性問(wèn)題如下。

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

⑵ 變量的定義問(wèn)題。為了方便起見(jiàn)，數(shù)據(jù)結(jié)構(gòu)算法描述中常在需要時(shí)直接使用一個(gè)變量而并沒(méi)有對(duì)其定義。在具體算法實(shí)現(xiàn)時(shí)，學(xué)生往往因忽略這些變量的定義而出現(xiàn)錯(cuò)誤。

⑶ 子函數(shù)的功能實(shí)現(xiàn)問(wèn)題。數(shù)據(jù)結(jié)構(gòu)中很多算法的實(shí)現(xiàn)需要基于一些子函數(shù)，而在偽代碼描述中可能直接調(diào)用了這些沒(méi)有函數(shù)體的函數(shù)。具體實(shí)現(xiàn)時(shí)，很多學(xué)生并沒(méi)有考慮這些子函數(shù)的功能實(shí)現(xiàn)而使得算法實(shí)現(xiàn)遇到問(wèn)題。

⑷ 語(yǔ)句規(guī)范性問(wèn)題。數(shù)據(jù)結(jié)構(gòu)課程中的算法描述，旨在通過(guò)簡(jiǎn)潔的方式讓學(xué)生了解算法的精髓，而其中的一些語(yǔ)句并不符合實(shí)際的語(yǔ)法規(guī)范，但這些語(yǔ)句可能與規(guī)范的語(yǔ)句非常類似，使得學(xué)生在學(xué)習(xí)中極易發(fā)生混淆。例如算法中經(jīng)常出現(xiàn)的輸入一個(gè)字符型變量ch的語(yǔ)句可能描述scanf（&ch），而實(shí)際規(guī)范的語(yǔ)句應(yīng)為scanf（"%c"，&ch）。

⑸ 指針變量的定義問(wèn)題。指針是數(shù)據(jù)結(jié)構(gòu)算法中頻繁出現(xiàn)的一個(gè)重要元素，指針實(shí)際是一個(gè)地址常量，它指示的是一個(gè)數(shù)據(jù)結(jié)構(gòu)的首地址，因而用它來(lái)描述具體的數(shù)據(jù)結(jié)構(gòu)更加明確。而指針變量則是一個(gè)可以被賦予不同指針值的變量，與指針的概念是有嚴(yán)格意義上的區(qū)別的。在數(shù)據(jù)結(jié)構(gòu)教學(xué)實(shí)踐中，學(xué)生普遍對(duì)這一概念理解不好，在指針變量的使用時(shí)常出現(xiàn)錯(cuò)誤。具體而言，數(shù)據(jù)結(jié)構(gòu)算法描述中，常會(huì)出現(xiàn)如下的結(jié)構(gòu)體類型定義：

typedef struct BiTNode {

ElemType data；

struct BiTNode *lchild， *rchild；

} BiTNode， *BiTree；

上述語(yǔ)句描述了二叉樹(shù)中的結(jié)點(diǎn)結(jié)構(gòu)，定義了一個(gè)結(jié)點(diǎn)結(jié)構(gòu)體類型BiTNode，而B(niǎo)iTree則是二叉樹(shù)結(jié)點(diǎn)指針的類型名。也即，如果后續(xù)定義一個(gè)二叉樹(shù)結(jié)點(diǎn)指針變量T，可以描述為

BiTNode *T；

而這等價(jià)于

BiTree T；

算法實(shí)現(xiàn)中，學(xué)生容易混淆這兩個(gè)類型的含義，從而發(fā)生定義錯(cuò)誤，影響后續(xù)的變量使用，使算法無(wú)法實(shí)現(xiàn)或得到不正確的結(jié)果。

⑹ 變量值返回問(wèn)題。數(shù)據(jù)結(jié)構(gòu)課程中的很多算法需要將子函數(shù)中變量的值返回以供后繼函數(shù)使用。在有返回值的函數(shù)中通常以如下方式定義：

Status Funcname （…， ElemType &e， …）

這實(shí)際是借用了C++語(yǔ)言中的參數(shù)引用調(diào)用。如果算法以C++語(yǔ)言實(shí)現(xiàn)，則可以在主調(diào)函數(shù)中直接使用Funcname （...， e， ...） 進(jìn)行調(diào)用。而如若算法以C語(yǔ)言實(shí)現(xiàn)，則這樣的描述無(wú)法直接實(shí)現(xiàn)，需要轉(zhuǎn)換為C語(yǔ)言中的傳地址調(diào)用才可。實(shí)際數(shù)據(jù)結(jié)構(gòu)教學(xué)中，很多教學(xué)機(jī)構(gòu)都是介紹C語(yǔ)言版的數(shù)據(jù)結(jié)構(gòu)，所以這樣不同語(yǔ)言之間的差異使得學(xué)生在變量返回值上容易出現(xiàn)問(wèn)題。

⑺ 結(jié)構(gòu)體分量的引用問(wèn)題。數(shù)據(jù)結(jié)構(gòu)算法描述中，具體的數(shù)據(jù)結(jié)構(gòu)定義一般是以結(jié)構(gòu)體的形式給出的，因此結(jié)構(gòu)體變量的分量引用非常關(guān)鍵。而普通結(jié)構(gòu)體變量和結(jié)構(gòu)體指針變量對(duì)分量的引用方式是不同的。例如在上述的二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)體定義中，如果定義了如下兩個(gè)變量：

BiTNode T1；

BiTNode *T2；（等價(jià)于BiTree T2；）

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

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

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

實(shí)際中，兩種引用方式經(jīng)常交替出現(xiàn)，如果不加以注意，就容易出現(xiàn)混淆。

2 算法實(shí)現(xiàn)的“三步曲”學(xué)習(xí)方法

基于上述歸納，本文提出一種“三步曲”的數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)學(xué)習(xí)方法。

第一步，縱觀全局，找出算法描述中存在的不合法常量和數(shù)據(jù)類型名稱定義并在算法實(shí)現(xiàn)之初對(duì)其進(jìn)行規(guī)范化。這一步可以將一些冗繁的細(xì)節(jié)性問(wèn)題在程序規(guī)模形成之前解決，避免在算法實(shí)現(xiàn)過(guò)程中反復(fù)的處理這些小問(wèn)題。

第二步，在透徹理解算法思想的基礎(chǔ)上將算法進(jìn)行模塊化劃分。具體而言，先找出算法中涉及的未實(shí)現(xiàn)子函數(shù)，再根據(jù)算法內(nèi)部的關(guān)系將整個(gè)算法劃分為若干個(gè)子算法。

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

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

3 算法實(shí)現(xiàn)實(shí)例說(shuō)明

針對(duì)數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)中算法實(shí)現(xiàn)時(shí)存在的普遍性問(wèn)題，本文所提出的“三步曲”的學(xué)習(xí)方法，其文字性的闡述可能比較抽象，下面我們通過(guò)二叉樹(shù)的先序遍歷算法實(shí)現(xiàn)這一實(shí)例來(lái)直觀地展示該學(xué)習(xí)方法。

二叉樹(shù)先序遍歷算法的描述可以參見(jiàn)文獻(xiàn)[1]中第6.3節(jié)的相關(guān)內(nèi)容，此處不再贅述。以下基于C語(yǔ)言實(shí)現(xiàn)該算法。

第一步先將常量和數(shù)據(jù)類型定義如下：

#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；

第二步，找出算法中未定義的子函數(shù)Status Visit（TElemType e），分析出該算法應(yīng)該包含二叉樹(shù)創(chuàng)建和二叉樹(shù)遍歷兩個(gè)子算法。

第三步，依次實(shí)現(xiàn)Visit函數(shù)和二叉樹(shù)的創(chuàng)建和遍歷子算法。具體而言，Visit函數(shù)是對(duì)每個(gè)數(shù)據(jù)元素的操作，因此最簡(jiǎn)單的操作可實(shí)現(xiàn)為輸出數(shù)據(jù)元素的值。實(shí)現(xiàn)細(xì)節(jié)如下：

Status Visit （TElemType e） {

printf（"%c"， e）；

return OK；

}

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

Status CreateBiTree （BiTree *T） {

/* 按先序次序輸入二叉樹(shù)中的結(jié)點(diǎn)值，空格字符表示空樹(shù)，構(gòu)造二叉鏈表表示的二叉樹(shù)T。*/

char ch；

scanf （"%c"， &ch）；

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

else {

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

exit （OVERFLOW）；

（*T）->data=ch； /*生成根結(jié)點(diǎn)*/

CreateBiTree （&（（*T）->lchild））； /*創(chuàng)建左子樹(shù)*/

CreateBiTree （&（（*T）->rchild））； /*創(chuàng)建右子樹(shù)*/

}

return OK；

}

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

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；

}

在完成常量定義以及子函數(shù)和二叉樹(shù)創(chuàng)建子算法功能實(shí)現(xiàn)的基礎(chǔ)上，先序遍歷子算法的描述基本上可以直接實(shí)現(xiàn)了。在成功實(shí)現(xiàn)上述子算法，只需定義一個(gè)如下的簡(jiǎn)單主函數(shù)作為執(zhí)行入口，整個(gè)算法即可完整實(shí)現(xiàn)并得到正確的結(jié)果。

main（） {

BiTNode *B；

printf（"請(qǐng)輸入二叉樹(shù)的結(jié)點(diǎn)：＼n"）；

CreateBiTree（&B）；

printf （"二叉樹(shù)的先序遍歷結(jié)果如下："）；

PreOrderTraverse（B，Visit）；

printf（"＼n"）；

}

圖1 先序遍歷算法實(shí)現(xiàn)運(yùn)行實(shí)例

圖1給出了一個(gè)上述先序遍歷算法實(shí)現(xiàn)的運(yùn)行實(shí)例，其中圖1（a）給出了所構(gòu)建二叉樹(shù)的結(jié)構(gòu)，圖1（b）顯示了算法實(shí)現(xiàn)的運(yùn)行結(jié)果。

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

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

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].清華大學(xué)出版社，2012.

[2] 楊曉波.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)[M].中國(guó)電力出版社，2010.

[3] 彭軍，向毅.數(shù)據(jù)結(jié)構(gòu)與算法[M].人民郵電出版社，2013.