案例驱动下数据结构教材的编写

摘要：介绍数据结构的基本概念，讨论对数据结构课程的认知，提出教材编写过程中的几个要点，强调案例驱动教学模式在教材编写中的重要性，从而形成教材自身的特色。

关键词：数据结构；算法；C++语言；案例驱动

1研究背景

“数据结构”的概念最早是C.A.R.Hoare于1966年提出的。在他的经典论文《数据结构笔记》中，他首次系统地论述了一组数据结构的构造、表示和操作等问题。1973年，D.E.Knuth在《计算机程序设计技巧》第一卷中给出了关于“信息结构”的系统论述。1976年，N.Wirtnh用“算法+数据结构=程序”这个公式表达了算法与数据结构的联系和它们在程序中的地位[1]。从此，数据结构确立了在计算机相关专业中的核心基础课程地位。

数据结构是一门关于非数值数据在计算机中表示、变换及处理的课程。这里的数据，实质是指计算机所能表示的各种不同数据对象(性质相同的数据元素的集合)的集合。对于每一具体的数据对象，数据元素之间的关系都不是孤立的。数据元素之间的内在联系被称之为结构。从数据元素之间的关系特征分析，各种数据对象的数据元素之间的关系仅呈以下四种结构之一：集合结构、线性结构、树形结构、图形结构。

数据结构课程的主要内容，是针对以上四种结构，先从逻辑层面讨论结构的关系特征及抽象操作；再讨论结构在计算机中的存储表示(映像)；并在存储表示的基础上给出相应结构的基本操作及实现；最后讨论各种结构的应用。

已有教材编写的思路莫不如此。但许多教材过于抽象而甚少工程背景，原因在于那些教材描述算法所使用的语言工具常是伪代码指令[2-3]，或在涉及数据结构转化于应用时往往不能完整地展开。因此，许多刚学完计算机高级语言、编程能力尚且不足的学生为此而深感困惑。

在长期的教学过程中，我们认为数据结构是一门兼具理论性与实践性的课程，也是在掌握程序设计语言后加强与提高学生程序设计能力的课程。因此，我们在编写数据结构教材时，以基本数据结构的主要内容为主线，在充分讨论结构的逻辑特征基础上给出结构在计算机中经典的存储表示(映像)，并在存储表示的基础上，用C++语言实现结构下的各个基本操作(建立结构的顺序类或链式类)。我们强调数据结构的应用，以模板的形式给出各种不同数据对象应用数据结构(线性结构、树形结构、图形结构、集合结构)的多个实例。每一算法或程序的编写高效、易读，并遵循程序设计的规范，从而使学习者将数据结构与工程应用有机结合。

2教材编写的几个要点

2.1教学大纲及教材内容

历经三十多年的发展，数据结构课程的主要讨论范畴已基本取得共识。尽管计算机应用领域仍在不断扩大，并产生了许多新的数据结构和算法，但数据结构最基本、最核心的内容还是各种经典教材中反复强调的最具有代表性的那些知识。2006年，教育部高等学校计算机科学与技术教学指导委员会编制了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》[4]，其中，算法与数据结构涉及AL1、AL2、AL3、AL4、AL5、PF2、PF3、PF4等多个知识单元，知识点包括递归，面向对象程序设计的基本理论，基本数据结构(栈、队列、链表、串、数组、广义表、树、图、哈希表等)，常用排序算法，常用查找技术，算法分析基础等。2009年，教育部考试中心制订了全国硕士研究生入学统一考试关于数据结构的考试大纲。以上内容构成了我们编写教材的大纲依据。

我们编写的教材[5]共七章，内容如下。

1) 第一章：绪论。

内容包括数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、算法的概念、算法时间复杂度和空间复杂度的分析等。

2) 第二章：线性表。

内容包括线性表的基本概念和类型定义、线性表的顺序存储结构、线性表顺序类的实现、线性表的链接存储结构、线性表单链表类的实现、循环链表及双向链表的存储结构、线性表的应用等。

3) 第三章：其他线性结构。

内容包括栈的存储及操作实现、栈的应用举例、递归、队列的定义和基本操作、字符串、数组及矩阵的存储压缩、广义表等。

4) 第四章：树型结构。

内容包括树、森林的定义及基本术语、二叉树的结构定义、二叉树的存储结构、二叉树的遍历、二叉树基本操作的实现、树和森林的遍历、树型结构的应用(算术表达式求值、树与等价问题、赫夫曼树及赫夫曼编码)等。

5) 第五章：图。

内容包括图的定义和术语、图的存储结构、图的基本操作、图的遍历、图的应用(最小生成树、最短路径、拓扑排序和关键路径、最短路径)等。

6) 第六章：查找。

内容包括静态查找表(顺序查找、折半查找、分块查找)，动态查找表(二叉排序树、平衡二叉树、B-树和B+树)，哈希查找等。

7) 第七章：排序。

内容包括插入类排序、分划类排序、选择类排序、归并类排序、基数排序、外部排序介绍等。

在教材的编写过程中，我们注重在体系完整、结构合理、概念清晰的基础上形成自己的特色。如对于线性表，强调注重在顺序及链式存储映像下基本操作的实现，对于栈和队列等操作上受限制的线性结构，强调注重相关环境下的应用，对于树、图等非线性结构，强调注重遍历及遍历的应用，对于查找和排序等，强调注重在消化各种经典算法的基础上时间效率的评估。

2.2选择C++语言描述算法

本教材的另一个特点是将面向对象的方法引入到数据结构领域。面向对象技术不仅是一种程序设计方法学，而且是一种认识方法学，数据结构讨论的正是数据的描述与处理，与面向对象的认知方法具有天然的联系。面向对象程序设计语言提供的封装、继承、多态和泛型程序设计等机制，为数据结构抽象数据类型的程序实现提供了很好的描述工具。

此外，面向对象的最大好处是复用、复用、再复用。数据结构中涉及的各类结构下的基本操作，在实际应用中也是常用的基本操作，而选择面向对象的高级语言C++作为描述算法的工具，既能将高级语言程序设计与数据结构紧密结合，又能通过数据结构进一步认识C++中的STL(标准模板库)，从而为实际编程的复用带来方便。显然，在数据结构的学习过程中，面向对象的主流语言C++较伪码语言更值得推崇。

2.3典型案例设计及举例

基于案例驱动的教学模式设计是以兴趣引导出发、以培养学生的设计能力为宗旨的教学模式，即通过对具体实例的演示、讲解，引导学生利用已学的知识，学会分析问题的方法，培养学生解决问题的能力[6]，以达到对问题更高层次的认知。在数据结构教材编写过程中，我们首先在存储表示的基础上，以类的方式实现相应结构的抽象数据类型，然后精心设计案例，通过模板的方式，使用类解决各个不同的应用问题，且对每一案例的解题都附有主函数，以确保应用的完整性。

例如，对于二叉树的学习，遍历是课程的重点，其重要性不仅在于遍历操作自身，更重要的是，它还是许多树形结构应用的基础。因此，我们设计了算术表达式求值这一案例。在这一案例中，使用二叉树的先序遍历次序和中序遍历次序建立二叉表达式树，使用二叉树后序遍历的思想对表达式求值，通过这一案例的学习，将二叉树三种重要的遍历融于一处。

图1是表达式用二叉树表示的例子。

图1算术表达式二叉树

在实现了用二叉链表结构定义的表达式类BinaryExpTree后，利用表达式的前缀式及中缀式建立二叉表达式树的函数如图2中的算法1所示。其中

ch1为表达式的前缀表示，ch2为表达式的中缀表示，low、high分别为中缀次序的起始和最终位置，本函数根据先序次序和中序次序的形成规律，运用先序递归遍历的思想逐个为先序次序中的第k个元素(k的初值为0)生成二叉链表中的结点。

在图3中，设在数组ch1中存有二叉表达式树的前缀表示，而在数组ch2中存有二叉表达式树的中缀表示。k指示了当前子树的根结点位置，在建立了根结点后，查找ch1[k]在ch2 中的位置i，从而形成新的划分L(low――i-1)、D(i)、R(i+1――high)。

K加1，对左右两部分依次递归地建树，直至某一子序列出现low > high，则子树建毕。

void BinaryExpTree :: _Create ( BTnode* &T,char ch1,char ch2,

int low,int high,int &k )

//利用表达式的前缀式及中缀式建立二叉表达式树

int i;

if(low > high)

T = NULL;

else{

T = new BTnode;

T->data = ch1[k];

//查找k在中序中的位置，从而划分D L R

for ( i = low;i

if(ch2[i] == ch1[k]){

k++;

_Create (T->Lchild,ch1,ch2,low,i-1,k); //建立左子树

_Create (T->Rchild,ch1,ch2,i+1,high,k); //建立左子树

}

}

}

图2算法1：建立二叉表达式树

图3先序次序和中序次序之间的关系

在建立了二叉算术表达式树后，用后序遍历的方式对表达式数求值，如图4中的算法2所示。

int BinaryExpTree ::_Evaluate(BTnode* &T)

{ // 在建立了二叉算术表达式树后，用后序遍历的方式对表达式树求值

if(T){

if(!T->Lchild && !T->Rchild )

return T->data C'0';//字符型转换成整型

return _Opreate(_Evaluate(T->Lchild),T->data,_Evaluate(T->Rchild));

}

return 0;

}

图4算法2：对表达式树求值

限于篇幅，其他函数及主函数不一一列举。

需要说明的是，上述表达式求值的过程仅是二叉树遍历的应用举例，真正应用于算术表达式求值尚有许多问题，如该方法输入数据是表达式的前缀式及中缀式、仅限于二元运算符、操作数是字符类型、表达式中的运算符不能重复等。

我们在教材的附件(程序光盘)中另给出了用栈的方式建立二叉表达式树的方法。该方法可直接用任意的算术表达式做输入数据、支持单目运算、支持各种类型的操作数。解决同一个问题，采用不同的方案

实现，无疑起到了开拓学者视野、加深问题认知的作用。

3结语

教材是根据教学大纲(课程标准)编写的系统反映学科内容的教学用书，是人们按照一定的教学目标、遵循相应的教学规律，组织并发展的科学技术理论及知识系统。合适的教材将协助学者更好地达到学习目标，期待我们的新编教材能接受学习者的检验并受到欢迎。

参考文献：

[1] 张乃孝. 编写“数据结构”教材的几点体会[C]//中国计算机学会,全国高等学校教学研究中心,全国高等学校教学研究会. 大学计算机课程报告论坛论文集. 北京:高等教育出版社,2007:543-547.

[2] 严蔚敏,吴伟民．数据结构[M]．北京:清华大学出版社,1997.

[3] Horrowitz E,Sahni S. Fundamentals of Data Structures[M].Pitmen Publishing Limited,1976.

[4] 教育部高等学校计算机科学与技术教学指导委员会. 高等学校计算机科学与技术专业发展战略研究报告暨专业规范(试行)[M]. 北京:高等教育出版社,2006:233-234.

[5] 万健,王立波．数据结构实用教程[M]．北京:电子工业出版社,2011.

[6] 陶影,张斌. 数据结构实验教学应重视算法设计与分析能力的培养[J]. 实验室研究与探索,2008,27(12):119-122.

Compiling Data Structure Textbook by Case Driving

WANG Libo, WAN Jian

(School of Computer, Hangzhou Dianzi University, Hangzhou 310018, China)

Abstract: This article introduces basic concepts of Data Structure, discusses understanding of Data Structure course. Main points are put forward in the process of compiling, stressing the importance of case driving teaching mode in teaching material compilation, forming characteristics of the material itself.

Key words: Data Structure; algorithm; C++ language; case driving

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文