《数据结构》课程中抽象概念与程序语句间的桥梁

祝恩

国防科技大学计算机学院, 湖南 长沙 410073

《数据结构》课程中抽象概念与程序语句间的桥梁

祝恩

国防科技大学计算机学院, 湖南 长沙 410073

在课程教学中，我们经常遇到算法及其程序实现的讲解，一些抽象概念在程序中体现为具体的程序语句，为了将这些程序语句和抽象概念联系起来，通常需要给程序加大量的注解。一种将程序语句与抽象概念联系起来的做法是在程序代码中使用宏，宏的名称以抽象概念命名，这样可以简化对程序的理解，将注意力集中在算法的逻辑层次上。论文以数据结构课程中的二叉树中序遍历算法和堆排序算法为实例，探讨在在程序中使用宏，以帮助建立抽象概念与程序语句的桥梁，达到让学生更容易理解程序的目的。

抽象概念；程序语句；宏

abstract concept；program sentence；Macro

引言

在课程教学中，我们发现在讲解算法及其程序实现时，特别当算法是用程序语句描述的时候，学生表现得理解更困难。一些抽象的概念在程序中体现为具体的程序语句，为了将这些程序语句和抽象的概念联系起来，通常需要给程序加大量的注解，阅读程序时也需要反复在抽象概念与程序语句之间建立联系，同时也容易深入到语句细节而忽视了对算法的逻辑上的理解。一种将程序语句与抽象概念联系起来以回避语句细节的做法是在程序代码中使用宏，宏的名称以抽象概念命名，这有利于学生把注意力集中在对算法的逻辑理解，也有利于教员对算法的讲解。论文以数据结构课程（使用[1]为教材）中二叉树中序遍历非递归算法和堆排序算法为实例，探讨在在程序中使用宏，以帮助建立抽象概念与程序语句的桥梁，达到让学生更容易理解程序的目的。这种思路也有利于数据结构实践教学[2-6]。

1 运用宏的实例

1.1 实例一： 二叉树中序遍历非递归算法

二叉树中序遍历非递归算法需要使用堆栈，图1给出了该算法的源程序。在图1所示源程序的第10行和第11行分别定义了需要使用的堆栈及其栈顶。对堆栈的常见操作包括进栈、出栈和判断栈是否为空。图1源程序的第15行和第19行分别是进栈和出栈操作，第23行的top＞=0表示要求栈不为空。阅读或讲解该算法时，时刻要在这些具体的语句和数据结构概念之间建立联系，不利于对算法的理解和讲解。因此，我们针对进栈、出栈、判断栈是否为空定义宏，如图2所示。图2的第6行、第7行和第8行分别是这3个操作的宏定义，图2的第12行、第16行和第20行对应地使用这些宏。

图 1 中序遍历非递归算法

图 2 使用宏以后的中序遍历非递归算法

1.2 实例二：堆排序算法

对于堆排序算法（大根堆），用两个函数实现，如图3所示，使用宏定义后的算法如图4所示。BigHeap_PearchDown(heap，i，n)将堆heap[0..n-1]中以heap[i]为根的子树调整为堆，其中heap[i]的两颗子树已经是堆；BigHeap_Sort(a，n)将a[0..n-1]用堆排序法进行排序。图3第30-31行将a[0..n-1]建立为一个大根堆，第30行的(n-2)/2表示堆的按照层序的最后一个分支节点的编号（根节点编号为0）；在图4的第8行将这个编号定义为宏LastFork(n)，表示有n个节点的堆的最后一个分支节点的编号为LastFork(n)。图3第13行的2*i+1表示i号节点的左儿子的节点编号；类似地，第20行的2*son+1表示son的左儿子节点编号；在图4的第5行定义Leftof(i)表示i的左儿子节点编号；类似地，Rightof(i)表示i的右儿子节点编号。图3第19行和第22行(son-1)/2表示son的父节点编号，因此在图4的第7行定义Fatherof(i)，表示i的父节点编号。实践证明，使用图3讲解程序时，学生很容易陷入对这些计算公式的含义的理解，学生经常会针对这些计算公式提问；使用图4则帮助学生从逻辑上理解算法。

图 3 堆排序算法

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

2 结语

算法中涉及到的大量抽象概念很多情况下都可用宏来表示，而且可用抽象概念的符号来命名宏。以往我们经常费力地在抽象概念和程序语句之间建立联系，这阻碍了对用程序语句描述的算法的理解，因为这使得学生容易陷入语言细节。实践表明，使用宏可以帮助我们合理地回避语言细节，从而可将注意力集中在算法的逻辑层次上，这种思路已经收到良好的实践效果。

[1]熊岳山,刘越.数据结构与算法[M].电子工业出版社,2007年

[2]王淮亭.“数据结构”实践教学探讨与实践[J].计算机教育,2009(12):133-134

[3]徐薇,王志海.数据结构课程研究性教学理论及方法探索[J].计算机教育,2012(1):35-38

[4]徐慧.数据结构实践教程[M].清华大学出版社，2010年

[5]李天志.数据结构课程教学改革探讨[J].计算机时代，2009(10）:56-58

[6]宋会英,孙晓燕,孙岐峰. 《数据结构》课程教学改革研究与实践[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月生，博士，国防科技大学副教授。研究方向：模式识别、图像处理。

10.3969/j.issn.1001-8972.2012.10.181