应用型本科计算机专业数据结构课程教学探讨

裴大容

摘要：该文主要针对应用型本科计算机专业的学生特点和数据结构课程的特点，通过有针对性的教学过程的把控，来提高数据结构课程的教学质量。

关键词：应用性本科;数据结构;教学过程

中图分类号：G424      文献标识码：A      文章编号：1009-3044（2018）35-0155-03

1 概述

数据结构课程是计算机专业一门非常重要的专业基础课，学好它为算法设计与分析等后续课程的学习奠定良好的基础，同时对软件设计和开发能力的提高也有极大的帮助。但由于数据结构课程中抽象型概念多且难于理解、知识点多、课内课时少等原因，加之应用型本科计算机专业的学生抽象型概念理解能力较差，分析和总结问题的能力不强，自学能力较弱等因素，导致了该课程总体学习效果较差。

针对以上问题，本人在教学过程中不断摸索，通过有针对性地进行教学过程中三方面的把控，使得教学质量得以提高。希望对同行们的教学有一定的参考价值。

2 教学过程把控

教学过程的把控，主要针对学生的特点和课程的特点，从以下三个方面来进行：

2.1 抽象概念具象化

数据结构中的概念通常都比较抽象，学生难于理解和记忆。只有尽量通过日常生活中的例子或情形来打比方，让学生好像看到了具体的情形或画面，这样才方便他们理解和记忆。

以线性表顺序存储时，顺序表的静态存储类型定义为例来讲。

此处用c语言来进行描述，顺序表类型定义如下：

#define MAXSIZE 100

typedef  int  DataType;

typedef   struct

{DataType   data[MAXSIZE];

int  length;}

SqList;

如刚讲了线性表的含义以及顺序存储的概念后，就直接给出以上类型定义，学生肯定感觉不好理解。原因主要在于三点：第一，前面基础语言课程学习掌握不扎实，对结构体定义感觉陌生;第二，对typedef语句不熟;第三，刚开始接触抽象数据元素类型DataType，感觉太抽象很别扭;因此总体上导致他们感觉很难，觉得这个定义太抽象不好理解。

此时我们可以在讲解时先不把抽象定义给学生看，而是先告诉他们任一个顺序表都可以看成由两部分构成：一个数组和一个表长，然后再尽量找一个现实生活中比较贴切的具象例子来让学生掌握其定义。

本人以新生入学报到为例来讲。在新生报到时，学院领导肯定很关心学生的报到情况。我们按学生报到的时间先后顺序来依次登记这些学生信息（为简单起见，学生信息仅记录姓名项），就构成了一张学生报到登记表。把每个学生看成一个数据元素，那这些同类型数据元素的集合，就构成了一个线性表。而存储这些学生的信息刚好可以用一个数组来实现。注意：数组的大小必须要足够大到可以装下所有可能报到的学生，所以应比预录人数适当增大。到目前为止，已经来报到的学生通过登记表可以一目了然了，但学校领导除了关心具体哪些同学已经来报到之外，还关心学生报到率的问题。而学生报到率可以通过实际报到人数来计算得到，所以在登记报到情况时，除了要登记已到同学的姓名，还要另外登记一个已到学生人数。那学生人数如何登记呢？一种方法是在存储学生信息的数组中加一个序号分量，但n个同就需要增加n个整型变量的存储空间;另一种方法是设置一个整形计数累加器变量，初值置为0，来一个学生就自增1，只需1个整型变量的存储空间;相较这2种方法，肯定第2种设置一个整形变量的方法更好，因为节约存储空间。由此例显而易见一个顺序表定义时需要2块内容：一块是存储学生信息的数组，另一块是表示实际人数的表长。然后再告诉学生对任何一个顺序表的定义都需要含这2部分内容，即：存储数據元素值的数组和表示元素个数的表长;此时，再把顺序表类型定义的代码给他们看并加以适当讲解，学生就很容易理解和记忆顺序表的类型定义了。以后再提及线性表顺序表类型定义时，他们就会联想到新生入学报到登记信息的情形，很快想到由数组和表长2部分构成。

因此，我们要尽量把一些抽象化的概念通过日常生活中的例子或现象来进行描述，让他们产生画面感，以便理解和记忆。

2.2 算法实例化

算法讲解前，尽量先演示典型实例，然后由点及面总结出算法思想，最后讲算法的实现代码。这样学生就不会觉得算法实现晦涩难懂了。

对于应用型本科计算机专业的学生来说，他们的数学基础不是特别好，直接讲算法时他们很难跟上思路;教材上的算法一般都是用类c或类pascal语言写的伪代码，再加之以前程序设计语言基础不太扎实，所以看代码时觉得很难理解。如果带入具体数值的有针对性的特例，他们能看到详细的计算或求解过程并且能理解这个过程，再稍加总结，最后转换为代码，这个时候他们就能理解了。

以线性表应用中稀疏一元多项式求和的算法为例来讲，其中一元多项式按幂指数递增的方式写，比如3+4x+6x100。假设用链式存储结构实现，因顺序存储相对来说容易实现。

首先在讲解算法之前，应设计一个特例，必须把求和过程中各种可能遇到的情况都考虑进去，包括：指数项不同时的情况以及指数项相同时系数项之和为0和不为0的情况;因遇到不同情况时，要做不同的处理。

比如有针对性的设计2个多项式A和B：

A=3+5X+8X99

B=7-5X+4X3

因为多项式的每一项都可以看成由系数项和指数项2个分量构成，所以我们可以把2个多项式分别表示成（（3，0），（5，1），（8，99））和（（7，0），（-5，1），（4，3））;由线性表的定义可知，这2个多项式可以看成2个按幂指数递增的线性表。现在按链式存储结构画出多项式A和B对应的含头结点的2个链表La和Lb，如图1所示。其中每个结点由指数项（expn）、系数项（coef）和next指针域3部分构成。

此时让学生回顾，数学中对一元多项式求和的方法，他们会说出如下规则：首先比较指数项：指数项相同时，系数项求和;和为零时忽略，和不为零时，生成对应的一项放到求和表达式中;指数项不同时，按指数项从低到高的顺序分别放到求和表达式中即可;实质上用计算机实现一元多项式求和算法也是利用这样的思路，只不过要考虑到存储细节的问题还要删除原有链表中的部分结点。

运算过程如下：

初始状态：分别设置2个移动指针p和q，分别指向La和Lb的第1个数据元素结点，即：p=La→next，q=Lb→next;同时令求和的链表用Lc表示，此处借助现有的La的头结点生成一个空链（借助Lb也同样可行），用r表示其移动指针（也是其尾指针），此时指向La的头结点，即：Lc=La，r=La;因求和后的数据元素项按幂指数递增，所以采用尾插法来生成新链表Lc。当前状态如图2所示。

第1步：比较当前2个指针p和q所指向的结点的指数项，都为0相同，系数项求和3+7=10≠0，所以此时只需修改当前2个结点中任一结点的系数项作为新的尾结点插入新链表中即可。假设选取当前p所指向的结点进行修改插入新链表Lc尾结点后面，同时r尾指针后，然后p指针后移;即：p→coef=10，r→next=p，p=p→next;因当前q所指向的结点已经用过无效了，应释放，q也应后移;但应注意顺序，先定位要删除的结点（假设借助一个移动指针s），然后q后移，即：s=q，q=q→next;此时状态如图3所示;最后删除结点，free（s）;得到结果如图4所示：

第2步：再继续比较当前p和q所指向的结点，因指数项相同，但系数项之和为0，所以新链表Lc中不增加新结点， p和q指针后移。但后移前应先分别定位到原来p和q所指向的结点，用第1步中删除结点的方法进行相同处理。结果如图5所示：

第3步：依然比较当前p和q所指向结点的指数项，因q所指向的结点的指数项小，所以应将q所指的结点作为新的尾结点插入到新链表Lc中，尾指针r后移， q指针后移。即：r→next=q，r=r→next，q=q→next;结果如图6所示：

第4步：因q=NULL，表示q所指向的链表已完，此时只需将p所指的结点作为新链表Lc当前尾结点的下一个结点即可，即r→next=p，此时新链表Lc生成完毕。

但还应注意一个问题，Lb所指向的头结点无用了也必须要释放，即free（Lb）。至此整个运算过程结束。结束时的状态如图7所示。

针对以上计算过程，总结出一般稀疏一元多项式求和的算法思想如下：

1） 初始化：置Lc为带头结点的空链表，同时设置移动指针p，q分别指向原有的2个多项式链表La和Lb的第一个数据元素结点;设移动指针r指向Lc的头结点;

2） 当原有2个链表都未空时，即p和q都不为空时：

比较p和q所指向结点的指数项，如相同时：判断其系数项之和是否为0;为0，则应删除相应结点，且p和q均后移;不为0，则应修改其中一个结点的系数项为求和后的值，加入新链表Lc后面作为最新的尾结点，且尾指针r后移;再删除另外一个已经无用的结点，且p和q都后移。（结合刚才实现过程，提醒学生注意删除时操作顺序，应先定位删除结点，然后指针后移，最后删除结点，否则容易断链）;当指数项不同时，则应先把指数项小的结点加入新链表Lc后面作为最新的尾结点，且尾指針r和该指针均后移;

3） 重复步骤（2），直到某个链表为空时，把指向另一个非空链表的移动指针作为新链表Lc尾指针r→next的值;

4） 释放那个无用头结点;

整个算法结束。

然后再讲解完整的算法实现，此时学生结合刚才的运算过程就很容易弄懂算法，也能很快分析出时间复杂度等。此类情况不再赘述。

2.3 强调复习

强调复习从两个方面来进行。第一个：因应用型本科学生自学能力较差，所以只能强调课后复习，通过有目的性布置作业和上机实验题有效地促进他们复习，达到对课堂内容的消化理解吸收;另一个，在讲课的过程中当用到以前学过的相关知识点时，有针对性的适当复习，达到温故而知新的目的。比如讲链栈生成算法时，要用到头插法生成单链表的知识点，所以首先复习下头插法的特点和算法中的关键语句;然后再强调链栈和单链表的区别，在链栈中头指针top直接指向链表的第一个数据元素结点;这样链栈生成算法在此基础上很轻松就可以学会。因此强调复习，对知识的理解、掌握和衔接特别重要。

3 教学效果

通过近4年教学结果观察，采用该法后，教学效果有较明显的改进，学生兴趣也有较大的提高，算法设计和分析能力也有一定的提高。

参考文献：

[1] 王宁宁. 中日工科院校应用型本科人才培养模式比较研究[D].哈尔滨理工大学，2016.

[2] 陈宇文. 注重源程序在《数据结构》课程中的重要性[J].高教论坛，2004（2）：73-75.

[3] 汪军， 周鸣争. 《数据结构》课程教学方法的改革与实践[J].兰州工业高等专科学校学报，2004，11（3）：19-21.

[通联编辑：张薇]