《數(shù)據(jù)結(jié)構(gòu)》課程中抽象概念與程序語句間的橋梁

祝恩

國防科技大學(xué)計(jì)算機(jī)學(xué)院, 湖南 長沙 410073

《數(shù)據(jù)結(jié)構(gòu)》課程中抽象概念與程序語句間的橋梁

祝恩

國防科技大學(xué)計(jì)算機(jī)學(xué)院, 湖南 長沙 410073

在課程教學(xué)中，我們經(jīng)常遇到算法及其程序?qū)崿F(xiàn)的講解，一些抽象概念在程序中體現(xiàn)為具體的程序語句，為了將這些程序語句和抽象概念聯(lián)系起來，通常需要給程序加大量的注解。一種將程序語句與抽象概念聯(lián)系起來的做法是在程序代碼中使用宏，宏的名稱以抽象概念命名，這樣可以簡化對程序的理解，將注意力集中在算法的邏輯層次上。論文以數(shù)據(jù)結(jié)構(gòu)課程中的二叉樹中序遍歷算法和堆排序算法為實(shí)例，探討在在程序中使用宏，以幫助建立抽象概念與程序語句的橋梁，達(dá)到讓學(xué)生更容易理解程序的目的。

抽象概念；程序語句；宏

abstract concept；program sentence；Macro

引言

在課程教學(xué)中，我們發(fā)現(xiàn)在講解算法及其程序?qū)崿F(xiàn)時，特別當(dāng)算法是用程序語句描述的時候，學(xué)生表現(xiàn)得理解更困難。一些抽象的概念在程序中體現(xiàn)為具體的程序語句，為了將這些程序語句和抽象的概念聯(lián)系起來，通常需要給程序加大量的注解，閱讀程序時也需要反復(fù)在抽象概念與程序語句之間建立聯(lián)系，同時也容易深入到語句細(xì)節(jié)而忽視了對算法的邏輯上的理解。一種將程序語句與抽象概念聯(lián)系起來以回避語句細(xì)節(jié)的做法是在程序代碼中使用宏，宏的名稱以抽象概念命名，這有利于學(xué)生把注意力集中在對算法的邏輯理解，也有利于教員對算法的講解。論文以數(shù)據(jù)結(jié)構(gòu)課程（使用[1]為教材）中二叉樹中序遍歷非遞歸算法和堆排序算法為實(shí)例，探討在在程序中使用宏，以幫助建立抽象概念與程序語句的橋梁，達(dá)到讓學(xué)生更容易理解程序的目的。這種思路也有利于數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)[2-6]。

1 運(yùn)用宏的實(shí)例

1.1 實(shí)例一： 二叉樹中序遍歷非遞歸算法

二叉樹中序遍歷非遞歸算法需要使用堆棧，圖1給出了該算法的源程序。在圖1所示源程序的第10行和第11行分別定義了需要使用的堆棧及其棧頂。對堆棧的常見操作包括進(jìn)棧、出棧和判斷棧是否為空。圖1源程序的第15行和第19行分別是進(jìn)棧和出棧操作，第23行的top＞=0表示要求棧不為空。閱讀或講解該算法時，時刻要在這些具體的語句和數(shù)據(jù)結(jié)構(gòu)概念之間建立聯(lián)系，不利于對算法的理解和講解。因此，我們針對進(jìn)棧、出棧、判斷棧是否為空定義宏，如圖2所示。圖2的第6行、第7行和第8行分別是這3個操作的宏定義，圖2的第12行、第16行和第20行對應(yīng)地使用這些宏。

圖 1 中序遍歷非遞歸算法

圖 2 使用宏以后的中序遍歷非遞歸算法

1.2 實(shí)例二：堆排序算法

對于堆排序算法（大根堆），用兩個函數(shù)實(shí)現(xiàn)，如圖3所示，使用宏定義后的算法如圖4所示。BigHeap_PearchDown(heap，i，n)將堆heap[0..n-1]中以heap[i]為根的子樹調(diào)整為堆，其中heap[i]的兩顆子樹已經(jīng)是堆；BigHeap_Sort(a，n)將a[0..n-1]用堆排序法進(jìn)行排序。圖3第30-31行將a[0..n-1]建立為一個大根堆，第30行的(n-2)/2表示堆的按照層序的最后一個分支節(jié)點(diǎn)的編號（根節(jié)點(diǎn)編號為0）；在圖4的第8行將這個編號定義為宏LastFork(n)，表示有n個節(jié)點(diǎn)的堆的最后一個分支節(jié)點(diǎn)的編號為LastFork(n)。圖3第13行的2*i+1表示i號節(jié)點(diǎn)的左兒子的節(jié)點(diǎn)編號；類似地，第20行的2*son+1表示son的左兒子節(jié)點(diǎn)編號；在圖4的第5行定義Leftof(i)表示i的左兒子節(jié)點(diǎn)編號；類似地，Rightof(i)表示i的右兒子節(jié)點(diǎn)編號。圖3第19行和第22行(son-1)/2表示son的父節(jié)點(diǎn)編號，因此在圖4的第7行定義Fatherof(i)，表示i的父節(jié)點(diǎn)編號。實(shí)踐證明，使用圖3講解程序時，學(xué)生很容易陷入對這些計(jì)算公式的含義的理解，學(xué)生經(jīng)常會針對這些計(jì)算公式提問；使用圖4則幫助學(xué)生從邏輯上理解算法。

圖 3 堆排序算法

圖 4 使用宏以后的堆排序算法

2 結(jié)語

算法中涉及到的大量抽象概念很多情況下都可用宏來表示，而且可用抽象概念的符號來命名宏。以往我們經(jīng)常費(fèi)力地在抽象概念和程序語句之間建立聯(lián)系，這阻礙了對用程序語句描述的算法的理解，因?yàn)檫@使得學(xué)生容易陷入語言細(xì)節(jié)。實(shí)踐表明，使用宏可以幫助我們合理地回避語言細(xì)節(jié)，從而可將注意力集中在算法的邏輯層次上，這種思路已經(jīng)收到良好的實(shí)踐效果。

[1]熊岳山,劉越.數(shù)據(jù)結(jié)構(gòu)與算法[M].電子工業(yè)出版社,2007年

[2]王淮亭.“數(shù)據(jù)結(jié)構(gòu)”實(shí)踐教學(xué)探討與實(shí)踐[J].計(jì)算機(jī)教育,2009(12):133-134

[3]徐薇,王志海.數(shù)據(jù)結(jié)構(gòu)課程研究性教學(xué)理論及方法探索[J].計(jì)算機(jī)教育,2012(1):35-38

[4]徐慧.數(shù)據(jù)結(jié)構(gòu)實(shí)踐教程[M].清華大學(xué)出版社，2010年

[5]李天志.數(shù)據(jù)結(jié)構(gòu)課程教學(xué)改革探討[J].計(jì)算機(jī)時代，2009(10）:56-58

[6]宋會英,孫曉燕,孫岐峰. 《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)改革研究與實(shí)踐[J]. 中國科技信息, 2011(22):168

In teachinga course, we have to frequent ly explain algorithmas nd programts o students. Som e abstract conceptas re presenti n the programa s concrete programmisneg ntences. When explain ing these sentences, we have to add extra comme nts to establishr elationshibpes tweent hese sentenc es and correspondainbgs tract conceptsA. nother mor e effective way for establishinsgu ch relationsh ips is using Macro definition。Twexo amplesn, ame ly middlet racing algorithmo f binary tree and hea p sort algorithma, re shownf or using Macro definition to establishb ridge betweenp rograms entenc es and abstract conceptss, o that the studentcs an understand more easily the algorithm in program.

祝恩，男，湖南益陽人，1976年5月生，博士，國防科技大學(xué)副教授。研究方向：模式識別、圖像處理。

10.3969/j.issn.1001-8972.2012.10.181