“数据结构”课程中算法实现的学习方法研究*

2014-04-29李燕

计算机时代 2014年11期

李燕

摘要：数据结构课程以算法描述为基础诠释了各种具体数据结构的概念和特点，而算法的实现则用更加直观的方式巩固了所学理论知识。文章结合数据结构的教学实践，总结学生实现算法遇到的普遍性问题，进而提出一种“三步曲”的数据结构算法实现学习方法。通过在教学实践中实际应用发现，该方法可以有效地帮助学生提高算法转化的效率。

关键词：数据结构；算法实现；教学实践；三步曲；学习方法

中图分类号：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"）；