数据结构课程难点讲授方法与必备知识

陈燕+屈莉莉+李桃迎

摘要：数据结构是计算机等相关专业重要的专业基础课，各大高校都十分重视该课程的教学效果。捋顺数据结构的先修后继课程，构建该课程的知识体系结构，凝练线性与非线性两大分类知识点，有助于形成该课程的系统化教学体系。将理论学习与工程实践的紧密结合作为讲授课程的侧重点，提高学生解决实际问题的能力。注重培养学生阅读和编制程序的技能，将是突破课程难点的重要方法。

关键词：数据结构；知识点；课程体系；程序设计

中图分类号：G642.41 文献标志码：A 文章编号：1674-9324（2015）27-0125-03

一、引言

《数据结构》一直被认为是计算机、信息管理与信息系统、电子商务等专业重要的基础课程之一。该课程的知识涉及到多学科与多专业，掌握该课程将对学生后续课程的学习起到重要的知识链接作用。数据结构课程的主要知识点包括：①线性表的顺序存储结构与链式存储结构及对应算法；②栈的顺序存储与链式结构及对应算法；③队列的顺序存储与链式结构及对应算法；④串的顺序与链式存储结构及对应算法；⑤数组和广义表的存储结构及对应算法；⑥树和二叉树的顺序与链式存储结构及对应算法；⑦查找方法；⑧排序方法等。为学好这门课程，必须依据课程体系，明确数据结构课程中的概念与术语，灵活运用这些知识点，以达到扎实掌握该课程难点的目的。

二、数据结构的先修后继课程及知识体系结构

1.掌握数据结构课程的先修与后继课程。以信息管理与信息系统专业课程体系为例，清晰了解和掌握与数据结构相关联的先修与后继课程（如图1所示）。先修课程主要有：计算机信息处理概论、汇编语言程序设计、高级语言程序设计（C、C++、Java等）、计算机组成原理、离散数学、运筹学、图论等。后续课程主要有：数据库原理、信息系统开发方法、编译原理、信息检索、数据仓库与数据挖掘、操作系统、信息集成技术及应用、电子商务与物流信息管理、大数据分析等相关课程。

2.数据结构课程实施框架体系的创新模式。围绕如下页图2所示的数据结构课程实施框架体系的创新模式讲授数据结构课程。明确数据结构课程的知识体系和主要知识点。该模式的优势在于：能够使学生快速掌握数据结构的概念、术语，客观世界问题对应在计算机外部的表示方式，在计算机内部的存储方式，以及如何对它们进行操作（运算）；除此之外，还能够严格按照数据结构课程的各个知识点进行梳理，清楚地归纳出数据结构与其他相关课程的关联关系。

三、运用归纳总结方法对数据结构课程的知识点进行分类

以严蔚敏教授出版的数据结构经典教材为例，将数据结构的知识点进行分类：第一类将第二章“线性表”、第三章“栈与队列”、第四章“串”、第五章“广义表”划分为数据的线性结构部分；第二类将第六章“树与二叉树”、第七章“图”划分为数据的非线性结构部分。

将自然界的线性问题对应的数据结构实例例举出来，形成数据结构问题的感性和直观的认识；然后再由浅入深地掌握其相关的知识点。例如：①为使管理人员快速找到客户相关信息，用计算机处理该业务应首先确定所使用的数据结构形式，如果希望将电话号码作为关键字，姓名的拼音作为次关键字，那么，会容易地查找出“陈”性拼音顺序排在“周”性之前的线性关系。②到银行办理业务对应的数据结构形式是队列模式，即满足“先来先服务，后来后服务”的服务规律。③对字符串进行存储与处理时，其存储结构具有紧凑和非紧凑形式，因此需按照形式的不同，进行分类处理后，再对其进行操作（如：插入、删除、查找、模式串匹配等）。④到图书馆借书时，图书管理员检索的模式与图书的存放形式有关。

与线性结构相比，非线性结构要复杂得多，即线性表的数据结构中数据元素的逻辑结构与物理结构之间存在一一对应的顺序关系；而非线性的数据结构中数据元素的逻辑结构与物理结构之间不存在一一对应的顺序关系，它们之间的顺序是任意的，也就是说非线性的数据结构中数据元素之间不存在前驱和后继的顺序关系，为使初学者掌握其存储结构对应的操作等相关知识点，必须将数据结构教科书中关于树与图的遍历进行深入而细腻的讲授。以二叉树的遍历问题为例，说明非线性结构应该着重讲授的知识点与教学方式。一般遍历某二叉树的原则是：先确定树根，然后按照树的递归原则进行先序、中序和后序等遍历，下图3所示。从三种遍历的序列可以看出，其每种遍历的结果序列都有其唯一的前驱和后继结点。这个规律说明一个道理：任何的非线性结构的结点元素都可以通过先确定遍历的名称，然后通过遍历方便地对其进行访问，比如：在前序遍历的序列“-+a*b-cd/ef”仿照线性表的定义找出它们之间的前驱与后继之间的关系；另外，同样中序和后继的遍历结果也可以仿照线性表的定义找出它们之间的前驱与后继之间的关系。同时，注意对学生发散性思维的培养，可通过三种遍历结果，进一步解释难以理解的概念推理，推论一：若已知一棵二叉树的前序序列和中序序列，则可以唯一地确定这棵二叉树；推论二：若已知一棵二叉树的后序序列和中序序列，则也可以唯一地确定这棵二叉树。在讲授该本课程知识点的同时，应考虑对后继课程的铺垫与衔接，上述三种遍历结果，对后续《编译原理》课程的前缀码、中缀码、后缀码等概念的理解与掌握将起到重要作用。

四、运用灵活的教学方式讲授难点章节

由于数据结构课程设计到多学科（专业）知识点，因此，教与学的过程中，难免存在难点、“瓶颈”问题和难以理解的算法。为解决此问题，在教学中应注重选用具有代表性的例子，如：在第七章的许多工程类例子与运筹学的例子非常相似，因此，在讲授此章节时，注重教材例子与运筹学学习的重点，但不同专业基础课程的侧重点不同。

1.非线性数据结构的讲授方法。以第七章为例，该章的相关知识内容有：图论、数据的逻辑结构及其对应的物理结构、算法实现的技巧与方法、优化问题、非线性问题的映射方法。主要存在如下难点：①非线性问题的逻辑表示方法。根据工程类例子的实际需求，找出该问题的逻辑表示方法是解决问题的核心。如：将符合多种方案选择的工程类的工序问题（如：排课问题、具有先后时间次序的问题），运用有向图的知识点将该问题表示清晰；应该标明该数据元素属于邻接表还是顺序存储形式。②非线性问题的物理表示方法。通过问题的逻辑表示方法可以将工程类的工序问题转换成有向图的存储方式，然后再选择图的存储结构，如：数组（顺序）存储、邻接表（链式）存储等方式。③如何编制实现解决非线性问题的算法（程序）。上述的逻辑结构确定了之后，再根据实际问题的要求进行实现程序的核心部分即算法的编制工作，当算法太复杂时，则先设计算法流程图然后再编写实现算法的程序。endprint

2.非线性数据结构的上机实践方法。最为有效的方法是选择学生日常生活中与工程类算法处理流程相近的例子。如在拓扑排序的上机实践选择的题目是给某专业课程进行排序，这个例子的选课过程正好符合工程类工序（周期）施工排序的案例；设计报文或字符编码时，按照第六章中的哈弗曼树的存储结构对报文进行编码；选择顺序线性表的上机例子是在一张学生登记表中进行插入和删除运算；选择链式线性表的上机例子是在一张按照拼音顺序进行插入和删除运算的线性表。

五、阅读程序的技巧与必备知识

数据结构的大量算法都要靠其对应的程序来验证，那么，如何针对数据结构经典算法来编程并且阅读这些经典的算法（程序）呢？这也是学好数据结构这门课程的关键。

1.让学生通过阅读程序，了解如何科学选取一个好的程序（算法）。由于程序是依靠“算法+数据结构”实现的，对一个实际问题来说，可以有不同的程序来实现。仅以一个简单的例子说明，如：运用计算机进行n的平方计算，有3种方法：n的平方=n n；n的平方=1+3+…+2n-1；高级语言自带的求平方函数，如double pow（n，2）。上述算法一个采用乘法，一个采用加法，一个是高级语言自带的，究竟哪种方法好呢？主要还是看其运算精度、算法的复杂度和空间复杂度等综合指标。

2.让学生通过阅读程序，了解和掌握相关知识点。应补充程序设计分类的相关知识。程序包括：直接程序设计，条件控制的程序，循环控制的程序（计数器控制的循环结构程序的算法、条件控制的循环结构程序的算法、变量控制的循环结构程序的算法）。还应该向学生介绍算法转换为运行程序的经验，如：数据的初始化如何处理；程序中的循环计数器与判断条件以及检验结果如何检验；递归程序中的出口条件判断问题；逻辑变量、精度、机器零、数值零、文本非结构化等归一问题。

3.快速阅读程序的必备知识。按照数据结构的课程要求，必须在读懂经典算法的基础上，才能够编制一个逻辑结构严谨的程序。但是，在教学中发现，有的学生学习方法不当，导致阅读程序的能力低而不能系统掌握数据结构课程的知识点。为了解决这一“瓶颈”问题，在讲授数据结构第一章绪论内容中，增加了程序设计方法、编制算法流程图的标准与规定、算法与程序的区分、如何选用大O来计算算法的时间复杂度和空间复杂度等知识点。递归程序的阅读是数据结构中较难掌握的内容。为让学生顺利阅读递归程序，必须在阅读递归算法之前，补充相关的知识，如：计算机原理“中断”的概念；程序设计中的过程调用的步骤和阅读方法；递归程序本身的特点，以及递归过程与一般过程的区别等。

六、小结

数据结构课程是计算机相关专业重要的基础课程之一，但课程学习难度较大，为提高该课程的教学质量和教学效果，本文梳理了数据结构的先修后继课程，构建了课程的知识体系结构，提炼出数据结构知识点分类的线性与非线性两条主线，强调将理论学习与工程实践的有机结合，提出实现程序设计与具备阅读程序的技巧是解决课程难点的重要手段。

参考文献：

[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2011.

[2]陈燕，等.数据结构[M].北京：科学出版社，2014.

[3]陈志珍，等.数据结构算法应用—基于Floyd算法的医院选址问题求解[J].教育教学论坛，2014，（36）：280-281.

[4]陈燕，等.数据结构教学方法的探讨[J].教育教学论坛，2013，（49）：82-84.endprint