数据结构与算法 [《数据结构》课程教学实践探索]
时间：2019-04-24 03:15:33 来源：雅意学习网 本文已影响 人 
摘 要：讨论了《数据结构》课程教学的基本知识框架体系，以问题驱动加深对基础知识理解，优化课堂教学方法，培养学生学习兴趣和创新能力，并以数据元素插入线性表为例，选取合适经典算法讲解基本原理， 给出了加强实践教学方法和改进措施。
关键词：数据结构；算法；教学方法；教学实践；创新
中图分类号：G642 文献标识码：A 文章编号：1002-7661（2012）12-008-03
《数据结构》是一门重要的综合性专业基础课程，数据结构是对计算机内存中的数据的安排，它涉及现实世界数据在计算机中的存储、表示、组织和处理，以及算法对这些数据结构进行各种处理的初步性能分析技术。
数据结构研究思想和研究方法在计算机科学深度研究领域有着广泛应用，它是计算机专业人员从事理论研究、应用开发、技术管理工作而必需学习的重要理论基础。通过各种基本数据结构及相应算法学习，使学生掌握把现实世界的客观问题转换为计算机内在表现形式，理解数据结构内在的逻辑关系，数据与关系在计算机中存储表示，以及在这些数据结构上的运算和算法执行。该课程具有相当的抽象性和动态性，如何学好《数据结构》这门课，让学生理解教材的理论结构体系需不断积累教学的经验，总结科学教学方法，以达到良好的教学效果。
《数据结构》的学习也是程序设计的学习过
程，通过对学生数据抽象能力的培养，使学生掌握软件工程的规范，能够编写正确易读，结构清楚的程序，具备一定的程序设计能力。本文将从教学方法，教学手段，启发式案例式教学研究，理论教学和实践教学的整合几个方面进行讨论。
一、明确数据结构课程的知识体系与教学目标
数据结构的研究涉及到计算机软、硬件方面，对于编译程序和操作系统都涉及到数据元素在存储中的分配问题，硬件的研究的方面涉及到编码理论、存储装置和存取方法，它是介于软硬件和数学三者之间的核心课程，是设计实现编译程序、操作系统和数据库系统等系统程序和大型应用程序的基础。数据结构作为主要研究数据的各种逻辑结构和存储结构以及对致据的各种操作的学科，对数据结构的教学应灵活运用与把握数据结构间纵向联系和纵横联系之中。从根本上掌握数据结构理论体系，这是数据结构教学工作做好的必备条件。数据结构课程的教学目标，是使学生学会分析计算机所加工数据的数据结构特性，为程序设计涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间效率分析和空间效率分析的技术。
1、数据结构课程的基本知识体系
一批具有某种逻辑关系的相关数据，按一定的存储方法被存储组织于计算机中，并在这些数据上定义了一个运算的集合，即是数据结构，它包括三个方面：逻辑结构、存储结构和数据的操作运算。数据结构的研究首先应对这三方面有一个清晰的探讨，针对每种数据结构均从逻辑结构、存储结构和操作运算等方面进行研究，是贯穿数据结构研究始终的主线。课程的基本知识模块是以数据的逻辑结构为主线，介绍线性结构、树形结构、图结构和文件结构，在介绍每种数据结构时，再讨论其存储方法以及相关的算法，存储方法有：顺序方法、链接方法、索引方法、散列方法。
数据结构课程的基本知识模块是以数据的逻辑结构为主线，顺序介绍线性结构、树形结构、图结构和文件结构。在介绍每种数据结构时，再讨论其存储结构以及相关的算法。基本模块教学，从以下几方面探讨：
（1）逻辑结构、存储结构、操作运算是数据结构间的横向联系。逻辑结构的定义、存储结构的实现、操作运算的实现是对数据结构研究的基本思想，研究数据结构首先应对这三方面进行详细清晰的探讨。
（2）数据结构间的纵向联系。以简单数据结构为基础实现对较复杂数据结构的研究，教学中让学生知道遍历操作对树、图结构是非常重要的运算。虽然从树、图的递归定义能设计出树、图遍历的递归算法，但从线性结构到树、图的发展是数据结构从简单到复杂的逐步发展过程。对于较复杂的数据结构树、图的遍历可用较简单的线性结构栈和队列来实现，这体现了数据结构间的纵向联系。
（3）数据结构间纵横联系。运用把握这种纵横联系，对从抽象数据类型（ADT）的角度进行数据结构的学习与研究有着重要的意义。ADT的操作就是实现对象的封装，把ADT和面向对象技术和抽象数据类型结合起来，更容易理解一些。和面向对象结合起来讲， ADT继续发展就是Object， ADT的操作就是对象的方法， STL(C++ Standard Template Library)是ADT的经典实现，介绍STL的实现让学生知道ADT究竟是如何被操作使用实现的。
2、课程教学目标
通过学习数据结构的概念、各种数据结构与算法的实现方式，不同数据结构和算法的特点比较。使学生能够提高用计算机解决实际问题的能力。
基本数据结构和基本算法分析技术部分，对常用基本数据结构的ADT 及其应用介绍，包括线性结构（线性表、串、栈和队列）、二叉树、树、图等；针对遍历二叉树这一教学内容，首先从遍历的概念讲起，引导学生掌握概念并理解遍历的本质就是非线性结构的线性化。
同时基于各种数据结构所实施的运算讨论算法分析的基本技术，掌握时间和空间权衡的原则。排序、检索和索引技术部分主要讨论插入排序、Shell 排序、堆排序、快速排序、归并排序、基数排序等常用的各种排序算法及其时间和空间开销，并介绍文件管理（数据在外存中的组织形式）和外排序技术，以及自组织线性表、散列表、倒排文件、B/B+树等常见的检索和索引技术，及其各自相应的时间和空间开销。
本课程的学习将使学生基本掌握数据结构和算法的设计分析技术，提高程序设计的能力；根据所求解问题的性质，选择合理的数据结构并对时间空间复杂性进行必要的控制。
二、创新课堂教学方法，培养学生学习兴趣
1、基于任务问题教学，实施启发式教学
主要数据结构包括栈、队列、列表、字符串、表、树、图、排序、查找等； 在数据结构的讨论中渗透典型的算法策略: 分治法、回溯法、贪心法、递归技术等； 使用典型的分析方法: 渐进分析法、缓冲分析技术等进行算法分析。数据结构课堂教学应以问题求解为导向，培养和提高学生理论、抽象、设计的能力。例如XMLDOM 树解析器、后缀树、搜索引擎等。激发学生的学习兴趣，培养学生的创新思维能力。 通过新的教学方法训练学生的数据结构思维，使其认识到数据结构的内在有趣，问题驱动的教学方法体现如下：掌握结构化问题解决技术和数据抽象原则；从架构师和设计师两个角度解决具体与抽象之间的难度；教授精巧数据结构给程序所带来的巨大改善；概括性地评价一个数据结构和程序的成本方法；数据结构来解决实际问具体应用。例如，搜索引擎问题询问，通过程序设计来实现搜索引擎会用到哪些数据结构，使用何种数据结构更有效。我们先尝试不用任何数据结构，发现无法构建搜索引擎；在用了简单的数组结构后可以构建搜索引擎，但效率很低；因此我们需要一步步引入构建更为精巧的矢量结构、树结构、索引表、哈希表结构等。再如教材管理问题，首先要考虑教材的各种信息，一般的方法是建立一个表，如表1所示，实际上，它就是1种称为线性表的数据结构。借助一个问题，围绕搜索引擎程序设计的实现，串起一系列的数据结构，学生看到了各种数据结构不是抽象的空的，而是因实际问题驱动、经过逻辑上的逐次演进推理而出现，从而帮助学生更加有趣地学习数据结构。逻辑上的数据结构反映数据成分之间的逻辑关系，物理上的数据结构反映数据成分在计算机内的存储安排。数据结构是数据存在的形式，以问题为驱动，以应用为轴线，对每一种数据结构的出现动机、发展逻辑、表示方式进行演绎，阐述如何从一种想法转换为一种设计，又如何从设计转化为具体程序，对每种数据结构都辅以程序设计中的实际应用，从而化抽象为具体，帮助学生利用数据结构思维解决实际问题。
2、结合实际问题，加强课堂互动
数据结构是反映数据的内部构成，即由哪些数据成分构成，构成方式，呈什么结构，也就是指相互之间存在一种或多种特定关系的数据元素的集合，数据结构是数据存在的形式。数据结构有逻辑上的数据结构和物理上的数据结构之分。目前国内较好的教材有清华大学出版社的严尉敏著《数据结构- C 语言描述》及其配套的《数据结构题集- C 语言描述》，殷人昆编著清华大学出版社出版的《数据结构( 用面向对象方法的C++ 描述)》等，Preiss 著《数据结构与算法- 面向对象的C+ + 设计模式》以及电子工业出版社的Clifford A. Shaffer著《数据结构与算法分析》都是很好的教学参考书。
课堂教学是教学有效的关键，课堂教学
中结合许多实际的讲解，如栈和车库停车、队列和火车站等地方的顺序服务； 树和人类的族谱、各种社会组织机构； 图和哥德斯堡七桥问题、四色定理等。结合现实问题，可以一定程度地提升教学效果。同时要充分进行课堂互动。讲解一个知识点时，而是要加强启发式引导，让学生接话，之后再重复强调如何理解。这样既能促进学生的思考，又能使学生加深理解课堂授课内容。
三、选择合适经典算法，科学讲授基本原理
1、选取经典算法算例
表1
计算机科学家N.沃斯提出“程序=数据结构+算法”，说明算法是对合理数据结构的操作(运算)，是数据处理的核心。《数据结构》课程中介绍的基本数据结构有线性表、堆栈、队列、数组、树、二叉树、图以及相应的算法。一个算法是建立在某种数据结构的基础上，一个算法不可能脱离数据结构而孤立存在。只有通过学习算法，才能真正掌握某种数据结构。学习《数据结构》的过程基本上是学习各种算法的过程，典型算法见表1。
在众多的算法中如何选择少量的典型算法进行分析讲解，往往能起到以点带面的关键作用。通过典型算法的分析，一方面让学生加深对数据结构基本理论的理解，另一方面让学生学习程序设计方法。例如在讲授线性表顺序存储教学内容时，可利用典型算法说明其存储特征，线性表的优点能对每个数据元素随机访问，其存储密度高，其缺点是插人、删除操作时需要移动大量的数据元素，操作效率低。可利用“向有序(由小到大或由大到小)的线性表(顺序存储)插人一个新的数据元素”，这一典型算法反映线性表顺序存储的特点。
算例：将一个值为X的数据元素插人到有序(由小到大或由大到小)的线性表(顺序存储)中，可以分两步进行，首先查找到值为X的数据元素在线性表中应有的位置，采用从头到尾循环比较的方法确定其位置I，然后，将第I个以后的全部数据元素向后移动一个存储单元，最后将值为X的数据元素存放到第I个位置上，线性表元素个数增1。线性表的元素插人(对数据的操作或算法)在线性表中进行元素插人，其示意图见图1所示：
图1
L= (a1，…a i-1，a i ， ai+1，…，an) 中的第i(1≤i≤n)个位置上插入一个新数据元素e，使其成为线性表 : L=( a1，…a i-1， e， a i ， ai+1，…，an)，除非i=n+1，否则必须将第i个到第n个数据元素均向后移动1个位置，然后将e存人第I个位置。
算法1
PROCEDURE INSERT(V，m，n，X)
//将值为X的数据元素插人到V数组中，(线性表顺序存贮在V中)m为最多元素个数，n为当前实际元素个数
IF (m = n)
T HEN( "OVERFLOW"；RETURN}
FOR I =1TO n DO
IF ( X (V (D) THEN BREAK
FOR J=nTO I BY-1 DO V(J+1)=V(J)
V(I)=X
n= n + 1
RETURN
该算法的优点是简单，便于理解，缺点是循环体内有提前退出语句，不利于结构化程序设计；确定新数据元素位置和移动数据元素分两步进行，有重复操作，那么可将两步合并一步以改进，即将循环比较与移动数据元素同时进行。从线性表的尾部开始向前循环比较，比新数据元素大者后移，直到小于等于时停止。
[算法2]
PROCEDURE INSERT(V，m，n，X)
IF(m= n) THEN( "OVERFLOW"；RETURN}
I= n WHILE(I)=1)AND(V(I))X)DO (V(I+1)=V(I)；I=I-1}
V (I+1)=X
n= n + l
RETURN
算法2中循环条件，当循环结束后I=0或V(I)(=X，新数据元素的位置为I+l，C算法1的时间复杂度为0(2n)，而算法2的时间复杂度为0(n)，循环结构采用结构化程序设计，该算法要归纳循环条件是关键，可改进推广应用。
[类C插人算法(数组的下标从0开始的)]
#define MAXLEN线性表可能达到的最大长度
Typedef struct
Elem type elem[MAXLEN]； Int length；
}Sqlist；
Sta tus Listin sert(Sqlist&L，inti， Elemtype e )
{//在线性表L中第i个元素之前插人新的元素e
//i的合法值为0≤i≤List Length(L )
if ( iL..length‖L .length>=
MAX LEN) return ERROR；
for (q=L.length-1；q≧i；q--)L.elem[q+1〕=L.elem[q]；
//将第i个元素及其后的元素后移
L.elem [i-1〕二e；//插人元素
L.le ngth++；//线性表长度增1
return OK；
通过对算法的分析要有助于程序设计能力的提高，有助于学生理解线性表的数据结构。还可使用流程图描述算法，进一步帮助学生更好地直观地理解算法。
3.2 优化实践教学，培养创新能力
数据结构课程，上机实习题的设计、学生的实习训练的数量和质量对学习效果都非常重要。通过适当的实习训练，使得学生深刻理解和掌握课程知识体系中的理论和抽象概念，以及各类设计实现方法，提高在复杂软件系统中的实践能力。以学生自主探究和开发活动为主体，培养学生学习的兴趣和能力。强化创新意识和创新能力，相应地提高理论联系实际能力、实践动手能力和科研能力，也能提高学生的学习和研究积极性，学生通过文献调研、开题、项目分析、项目设计、成果汇报、总结评价展开设计训练，可以把理论课上的很多算法得以实现，并且进行深入的数据结构和算法时间、空间效率讨论，达到理论与实践水平共同提高目的。
四、结语
本文针对数据结构课程进行了教学方法上的探讨，从广度和深度上把握课程的知识体系，了解基本数据结构和经典算法，掌握理论、抽象和设计方法进行探讨。以期为本课程的教学提供借鉴。文中讨论选取实际问题，选择合适的数据模型，选择经典算法，剖析重要数据结构与算法思想方法，突破常规教学方法，研究设计教学案例，通过这些例题让学生知道利用所学知识的对实际问题问题求解，助学生理解数据结构原理和算法技术，这样才能充分培养学生学习本课程的兴趣。
参考文献
[1] 严蔚敏,吴伟民. 数据结构(C语言版)[M] 北京:清华大学出版社，2006:156-163.
[2] 陈雪刚. 数据结构课程教学改革与实践[J] 计算机教育，2011 (4):34-37.
[3] 杨利英. 数据结构课程的教学方法探讨，2011 6 (24):131-133.
[4] Shaffer，A.数据结构与算法分析(C + + 版)[M] 2 版.北京:电子工业出版社，2010.
[5] 庞晓琼. 案例驱动的《数据结构》课程设计教学改革实践.计算机教育[J]，2009.1:53~64.
[6] 沙宗尧,边馥苓. 图示教学法在数据结构与算法教学中的应用［J］.计算机教育，2009(18):80-82.
[7]张立,王伟嘉. 基于学习兴趣开展数据结构教学 计算机教育[J]，2010 13 10:95~97.
[8] Thomas H Cormen，etc Introduction to Algorithms (2ndedition)[M] 北京:高等教育出版社，2005.
