论文部分内容阅读
摘要：存储结构和基于各种存储结构上基本操作的算法实现是数据结构课程的重点教学内容。分析了上述内容教学过程中存在的问题，以有向图十字链表存储结构和Prim算法程序实现的教学过程为例，探讨了启发式授课方法在数据结构课堂教学中的运用，实践证明取得了良好的教学效果。
关键词：数据结构；课堂教学；启发式；存储结构；算法实现
作者简介：余艳（1980-），女，湖北襄阳人，武汉科技大学理学院，讲师；刘燕丽（1980-），女，河南西平人，武汉科技大学理学院，讲师。（湖北 武汉 430065）
基金项目：本文系武汉科技大学教学研究项目（项目编号：2012X51）、武汉科技大学教学研究项目（项目编号：2013x065）的研究成果。
中图分类号：G642.0 文献标识码：A 文章编号：1007-0079（2014）08-0098-02
数据结构是信息类相关专业本科生必修的专业基础课，该课程探讨了各种经典数据结构的逻辑特性、存储结构以及相关算法，为后续课程提供了理论基础和技术支持。数据结构是课堂教学与实践教学并重的课程，通常开设在本科二年级上学期，对于大学低年级本科生而言，课堂学习仍是获取知识的重要渠道。文献[1]指出在课堂教学中教师通过不断设疑和释疑，可以更好地展示自己的思维过程并揭示知识的来龙去脉，并引起教师教与学生学的思维共振。本文以武汉科技大学信息与计算科学系为例，分析数据结构课程存储结构及算法实现的课堂教学中遇到的问题，并针对这些问题探讨启发式授课在数据结构课堂教学中的实际运用方法及效果。
一、课堂教学中存在的问题
第一，数据结构教材对知识的讲解严谨简洁，但是对知识的表达过于生硬，缺少对问题背景、存储结构和算法设计思想的讨论；第二，部分学生在学习过程中习惯记忆各种存储结构的表示方法，却未理解各种存储结构的设计原理，这些学生有可能获得比较高的卷面分数，却难以在未来学习和工作中灵活运用数据结构知识；[2]第三，数据结构的学习过程也是学生进行复杂程序设计的训练过程，部分学生反映可以轻松理解数据结构中的算法策略，但对从算法到代码的转换工作却感到困难。
二、存储结构的启发式教学
数据结构课程讲授了线性表、栈、队列、串、数组、广义表、二叉树和图等经典存储结构，如果直接将各种存储方法灌输给学生，势必造成学生知其然而不能知其所以然，且容易导致课堂教学中问题2的发生。采用不断创造问题情境的方法激发学生思考，使其主动参与到存储结构的设计过程中，则可以加深学生对存储方法的理解，同时为将来根据应用需求自行设计存储结构积累经验。下面以有向图的十字链表为例讨论存储结构教学中的启发式讲授方法。
启发问题1：在正式讲授十字链表结构之前，询问学生已学习的邻接表及逆邻接表在计算出度和入度时各有什么特点。通过回忆学生会发现，使用邻接表时通过遍历依附于顶点的单链表便可以轻松地计算出该顶点的出度，但计算入度则需要遍历整个邻接表结构；使用逆邻接表则恰恰相反，可以轻松计算出各顶点的入度，但计算出度则需遍历整个逆邻接表结构。接下来教师引出，为了弥补邻接表和逆邻接表各自的不足，人们考虑设计另外一种存储结构，通过将邻接表和逆邻接表相结合从而得到十字链表结构。这样讲解可以使学生明白十字链表结构的设计初衷，同时领悟到各种存储结构的存在都有潜在需求。
启发问题2：十字链表的结构是怎样的呢？首先引导学生分析顶点的特点并设计其存储结构。对于任何数据结构而言，设计它的存储结构无非是考虑如何存储数据元素以及元素间的关系。元素的存储往往简单，而关系的设计则需要动些脑筋。有向图中的顶点即数据元素，它们具有相同的特性，结构整齐划一，因此可以考虑使用顺序结构存储所有顶点。每个顶点元素的结构就非常简单了，如图1（a）所示，其中data用于存放顶点信息。
启发问题3：弧结点的结构又应该是怎样的呢？根据十字链表的结构定义，对于有向图中的每个顶点有一个结点，每一条弧也有一个结点。这里有必要引导学生思考，怎样用一个结点表示一条弧。学生会想到，表示一条弧需要给出弧尾和弧头。那么进一步引导学生思考，在弧结点中如何表示弧尾和弧头？学生会给出多种方案，比如直接存储弧尾和弧头顶点的信息；或是存储弧尾和弧头顶点的位置。这时，需要进一步比较两种方案的优劣。如果在弧结点中直接存储弧尾和弧头顶点的信息，那么在图结构中势必存在顶点的多个备份，这样一方面会导致存储空间的浪费，另一方面修改某个顶点信息時，它的多个备份需要做相应修改，如果没有全部修改则会带来数据不一致的问题。比较之后，学生会得出结论，在弧结点中存储弧尾和弧头的位置信息更合适。此时，继续引导学生思考，如何表示弧尾和弧头的位置？学生通常会想到可以用绝对的地址。此时可以提醒学生顶点存储在数组中，在已知数组基址及元素下标时，可以容易地计算出该元素的地址。进一步地，学生会想到可以用顶点在数组中的下标表示位置信息。接下来再引出程序设计中的经验，当使用顺序结构存储数据元素时，为方便起见通常更倾向于使用下标访问元素，而不是使用指针。结合以上分析，学生会设计出如图1（b）所示的弧结点。其中，tailvex表示弧尾顶点在顶点向量中的下标；headvex表示弧头顶点在顶点向量中的下标。
启发问题4：如上设计的弧结点结构可以满足常用操作的需求吗？按照如上思路设计的弧结点可以描述出顶点间的逻辑关系，但是却不足以满足常用的操作需求。比如给定某个顶点寻找它的所有出弧或入弧，则需要遍历图中所有的弧结点，导致算法效率低下。为了能够方便地找到顶点的所有邻接点，有必要进一步改进弧结点的结构设计。考虑将所有弧尾相同的弧结点链接起来形成一个行链表，顺着这个链表就可以找到弧尾顶点的所有出弧，同理将弧头相同的弧结点也链接起来形成一个列链表，可以方便地找到弧头顶点的所有入弧。综上分析，需要在弧结点中增加两个指针域，得到如图1（d）所示的弧结点结构。其中，hlink表示指向弧头相同的下一个弧结点的指针，tlink表示指向弧尾相同的下一个弧结点的指针。 启发问题5：存放弧结点链表的头指针应该保存在哪里呢？为使图的各种操作最为方便，由于行链表保存着所有弧尾顶点相同的弧，可以把它的头指针和弧尾顶点保存在一起；同理列链表的头指针则和弧头顶点保存在一起。综上分析，需要在顶点结点中增加两个链域，如图1（c）所示。其中data用于存放顶点本身信息，firstin指向第一條入弧，firstout指向第一条出弧。
十字链表存储结构的分析与设计完成后，有必要用实例来展示有向图的十字链表结构，如图2所示。其中左图为有向图逻辑结构，右图为其对应的十字链表结构。按照如上启发式方法进行存储结构的讲解，可以使学生对各种存储结构产生更深刻的认识，使其成为知识的构建者，而不再是被灌输的对象。
三、算法实现的启发式教学
数据结构课程包含一些经典算法，如串的模式匹配、二叉树的遍历、图的深度和广度优先遍历、拓扑排序等。学生在学习这些算法的过程中，普遍反应理解算法策略很轻松，但从算法转化到代码时就觉得困难重重了，在数据结构课程的授课过程中加强对此环节的教学极为重要。依据多年教学经验来看，采用基于问题的启发式教学方法能够激发学生求解问题的热情，摆脱枯燥厌烦的情绪，使其乐于思考算法到代码的转化方法，避免课堂教学中问题3的发生，同时为复杂程序设计积累经验和技巧。下面以Prim算法的程序实现方法为例探讨算法实现中的启发式讲授方法。
启发问题2：如何存储最小生成树？对于含n个顶点的连通网，最小生成树的顶点集和连通网的顶点集相同，边的集合为连通网上边集合的子集，因此最小生成树的结果可使用包含n-1条边的集合表示。进一步引导学生思考最小生成树的每条边如何表示。每条边依附于两个顶点且具备权值。在最小生成树构造过程中，需要用到最小两栖边，最小两栖边的两个顶点分别位于集合U和集合V-U，所以边的类型定义应包含三个成员：beg为位于集合U中的顶点，end为位于集合V-U中的顶点，w为边的权值。设计了最小生成树的存储结构以后，就可以开始讲解在该存储结构上跑算法的过程了，如图3所示。通过图3分步演示Prim算法程序实现的整个过程，使学生对程序实现有更直观的理解。在讲解过程中可以进一步引导学生思考有关代码编写的细节问题，例如启发问题3。
四、结束语
在数据结构课堂教学中强调对问题解决方法的思考，通过启发式教学激发学生的研究性思维，让他们积极参与到知识构建与理解的过程中。按照本文方法进行课堂教学，学生普遍反应对存储结构的授课内容理解起来很轻松，数据结构实验课中编写程序的思路也很清晰，实践证明启发式授课取得了良好的教学效果。由于同一个课堂内学生在接受知识的能力上存在较大差异，如何兼顾层次不同的同学，因材施教达到更好的教学效果，是需要进一步研究的问题。
参考文献：
[1]孙式武.课堂教学中师生思维同步的实现策略[J].教育理论与实践，2013，33（8）：44-46.
[2]余艳，刘燕丽.数据结构教学方法探讨[J].计算机教育，2013，
（9）：56-58.
[3]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.
（责任编辑：王意琴）
关键词：数据结构；课堂教学；启发式；存储结构；算法实现
作者简介：余艳（1980-），女，湖北襄阳人，武汉科技大学理学院，讲师；刘燕丽（1980-），女，河南西平人，武汉科技大学理学院，讲师。（湖北 武汉 430065）
基金项目：本文系武汉科技大学教学研究项目（项目编号：2012X51）、武汉科技大学教学研究项目（项目编号：2013x065）的研究成果。
中图分类号：G642.0 文献标识码：A 文章编号：1007-0079（2014）08-0098-02
数据结构是信息类相关专业本科生必修的专业基础课，该课程探讨了各种经典数据结构的逻辑特性、存储结构以及相关算法，为后续课程提供了理论基础和技术支持。数据结构是课堂教学与实践教学并重的课程，通常开设在本科二年级上学期，对于大学低年级本科生而言，课堂学习仍是获取知识的重要渠道。文献[1]指出在课堂教学中教师通过不断设疑和释疑，可以更好地展示自己的思维过程并揭示知识的来龙去脉，并引起教师教与学生学的思维共振。本文以武汉科技大学信息与计算科学系为例，分析数据结构课程存储结构及算法实现的课堂教学中遇到的问题，并针对这些问题探讨启发式授课在数据结构课堂教学中的实际运用方法及效果。
一、课堂教学中存在的问题
第一，数据结构教材对知识的讲解严谨简洁，但是对知识的表达过于生硬，缺少对问题背景、存储结构和算法设计思想的讨论；第二，部分学生在学习过程中习惯记忆各种存储结构的表示方法，却未理解各种存储结构的设计原理，这些学生有可能获得比较高的卷面分数，却难以在未来学习和工作中灵活运用数据结构知识；[2]第三，数据结构的学习过程也是学生进行复杂程序设计的训练过程，部分学生反映可以轻松理解数据结构中的算法策略，但对从算法到代码的转换工作却感到困难。
二、存储结构的启发式教学
数据结构课程讲授了线性表、栈、队列、串、数组、广义表、二叉树和图等经典存储结构，如果直接将各种存储方法灌输给学生，势必造成学生知其然而不能知其所以然，且容易导致课堂教学中问题2的发生。采用不断创造问题情境的方法激发学生思考，使其主动参与到存储结构的设计过程中，则可以加深学生对存储方法的理解，同时为将来根据应用需求自行设计存储结构积累经验。下面以有向图的十字链表为例讨论存储结构教学中的启发式讲授方法。
启发问题1：在正式讲授十字链表结构之前，询问学生已学习的邻接表及逆邻接表在计算出度和入度时各有什么特点。通过回忆学生会发现，使用邻接表时通过遍历依附于顶点的单链表便可以轻松地计算出该顶点的出度，但计算入度则需要遍历整个邻接表结构；使用逆邻接表则恰恰相反，可以轻松计算出各顶点的入度，但计算出度则需遍历整个逆邻接表结构。接下来教师引出，为了弥补邻接表和逆邻接表各自的不足，人们考虑设计另外一种存储结构，通过将邻接表和逆邻接表相结合从而得到十字链表结构。这样讲解可以使学生明白十字链表结构的设计初衷，同时领悟到各种存储结构的存在都有潜在需求。
启发问题2：十字链表的结构是怎样的呢？首先引导学生分析顶点的特点并设计其存储结构。对于任何数据结构而言，设计它的存储结构无非是考虑如何存储数据元素以及元素间的关系。元素的存储往往简单，而关系的设计则需要动些脑筋。有向图中的顶点即数据元素，它们具有相同的特性，结构整齐划一，因此可以考虑使用顺序结构存储所有顶点。每个顶点元素的结构就非常简单了，如图1（a）所示，其中data用于存放顶点信息。
启发问题3：弧结点的结构又应该是怎样的呢？根据十字链表的结构定义，对于有向图中的每个顶点有一个结点，每一条弧也有一个结点。这里有必要引导学生思考，怎样用一个结点表示一条弧。学生会想到，表示一条弧需要给出弧尾和弧头。那么进一步引导学生思考，在弧结点中如何表示弧尾和弧头？学生会给出多种方案，比如直接存储弧尾和弧头顶点的信息；或是存储弧尾和弧头顶点的位置。这时，需要进一步比较两种方案的优劣。如果在弧结点中直接存储弧尾和弧头顶点的信息，那么在图结构中势必存在顶点的多个备份，这样一方面会导致存储空间的浪费，另一方面修改某个顶点信息時，它的多个备份需要做相应修改，如果没有全部修改则会带来数据不一致的问题。比较之后，学生会得出结论，在弧结点中存储弧尾和弧头的位置信息更合适。此时，继续引导学生思考，如何表示弧尾和弧头的位置？学生通常会想到可以用绝对的地址。此时可以提醒学生顶点存储在数组中，在已知数组基址及元素下标时，可以容易地计算出该元素的地址。进一步地，学生会想到可以用顶点在数组中的下标表示位置信息。接下来再引出程序设计中的经验，当使用顺序结构存储数据元素时，为方便起见通常更倾向于使用下标访问元素，而不是使用指针。结合以上分析，学生会设计出如图1（b）所示的弧结点。其中，tailvex表示弧尾顶点在顶点向量中的下标；headvex表示弧头顶点在顶点向量中的下标。
启发问题4：如上设计的弧结点结构可以满足常用操作的需求吗？按照如上思路设计的弧结点可以描述出顶点间的逻辑关系，但是却不足以满足常用的操作需求。比如给定某个顶点寻找它的所有出弧或入弧，则需要遍历图中所有的弧结点，导致算法效率低下。为了能够方便地找到顶点的所有邻接点，有必要进一步改进弧结点的结构设计。考虑将所有弧尾相同的弧结点链接起来形成一个行链表，顺着这个链表就可以找到弧尾顶点的所有出弧，同理将弧头相同的弧结点也链接起来形成一个列链表，可以方便地找到弧头顶点的所有入弧。综上分析，需要在弧结点中增加两个指针域，得到如图1（d）所示的弧结点结构。其中，hlink表示指向弧头相同的下一个弧结点的指针，tlink表示指向弧尾相同的下一个弧结点的指针。 启发问题5：存放弧结点链表的头指针应该保存在哪里呢？为使图的各种操作最为方便，由于行链表保存着所有弧尾顶点相同的弧，可以把它的头指针和弧尾顶点保存在一起；同理列链表的头指针则和弧头顶点保存在一起。综上分析，需要在顶点结点中增加两个链域，如图1（c）所示。其中data用于存放顶点本身信息，firstin指向第一條入弧，firstout指向第一条出弧。
十字链表存储结构的分析与设计完成后，有必要用实例来展示有向图的十字链表结构，如图2所示。其中左图为有向图逻辑结构，右图为其对应的十字链表结构。按照如上启发式方法进行存储结构的讲解，可以使学生对各种存储结构产生更深刻的认识，使其成为知识的构建者，而不再是被灌输的对象。
三、算法实现的启发式教学
数据结构课程包含一些经典算法，如串的模式匹配、二叉树的遍历、图的深度和广度优先遍历、拓扑排序等。学生在学习这些算法的过程中，普遍反应理解算法策略很轻松，但从算法转化到代码时就觉得困难重重了，在数据结构课程的授课过程中加强对此环节的教学极为重要。依据多年教学经验来看，采用基于问题的启发式教学方法能够激发学生求解问题的热情，摆脱枯燥厌烦的情绪，使其乐于思考算法到代码的转化方法，避免课堂教学中问题3的发生，同时为复杂程序设计积累经验和技巧。下面以Prim算法的程序实现方法为例探讨算法实现中的启发式讲授方法。
启发问题2：如何存储最小生成树？对于含n个顶点的连通网，最小生成树的顶点集和连通网的顶点集相同，边的集合为连通网上边集合的子集，因此最小生成树的结果可使用包含n-1条边的集合表示。进一步引导学生思考最小生成树的每条边如何表示。每条边依附于两个顶点且具备权值。在最小生成树构造过程中，需要用到最小两栖边，最小两栖边的两个顶点分别位于集合U和集合V-U，所以边的类型定义应包含三个成员：beg为位于集合U中的顶点，end为位于集合V-U中的顶点，w为边的权值。设计了最小生成树的存储结构以后，就可以开始讲解在该存储结构上跑算法的过程了，如图3所示。通过图3分步演示Prim算法程序实现的整个过程，使学生对程序实现有更直观的理解。在讲解过程中可以进一步引导学生思考有关代码编写的细节问题，例如启发问题3。
四、结束语
在数据结构课堂教学中强调对问题解决方法的思考，通过启发式教学激发学生的研究性思维，让他们积极参与到知识构建与理解的过程中。按照本文方法进行课堂教学，学生普遍反应对存储结构的授课内容理解起来很轻松，数据结构实验课中编写程序的思路也很清晰，实践证明启发式授课取得了良好的教学效果。由于同一个课堂内学生在接受知识的能力上存在较大差异，如何兼顾层次不同的同学，因材施教达到更好的教学效果，是需要进一步研究的问题。
参考文献：
[1]孙式武.课堂教学中师生思维同步的实现策略[J].教育理论与实践，2013，33（8）：44-46.
[2]余艳，刘燕丽.数据结构教学方法探讨[J].计算机教育，2013，
（9）：56-58.
[3]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.
（责任编辑：王意琴）