《数据结构》课程教学改革的思路与实践

赵福生

(泉州师范学院 数学与计算机科学学院，福建 泉州 362000)

《数据结构》课程教学改革的思路与实践

赵福生

(泉州师范学院 数学与计算机科学学院，福建 泉州 362000)

针对《数据结构》课堂教学，提出了教学改革的五点思路，通过实例对五点思路进行详细的分析.在实际的课堂教学过程中，不断实践与丰富所提出的五点思路.教学的结果表明，教学改革的五点思路是行之有效的.

数据结构；指导思想；面向对象；抽象类型

0 引言

《数据结构》课程是计算机类专业基础核心课程，该课程一般安排在大二时进行学习，在学这门课程以前，学生一般学过高级语言程序设计、概率论等专业课程，但面向对象的思维仍然没有得到很好的训练，对编程语言的理解仍然缺少正确有效的方法，学生如何学好《数据结构》这门课程缺少方向性的指导.本文针对该课程的学习，提出了五点思路：牢牢记住一个指导思想，采用两种方法，实现三个过程，学习四个方面，掌握五种抽象类型.

1 牢牢记住一个指导思想

在《数据结构》课程的学习过程中，必须牢记如下指导思想：阅读算法时，要看到算法中语句表达的意思，要领悟算法中语句执行的过程，要理解算法中语句发生的操作.

任何语言都是形式化的东西，当然包括数学语言(数学符号)、计算机语言、自然语言(英语汉语等).语言都表达一定的意思，语言背后蕴含着丰富的信息.透过语言这种形式化的东西看到语言表达的意思与蕴含的信息，语言作为一堆符号就不再枯燥.自然语言是人与人交流的一种工具.利用自然语言，人可以表达丰富多彩的信息.计算机语言也是一种语言，计算机语言用来完成人与计算机的交流，人利用计算机语言告诉计算机该完成哪些工作，计算机也可以通过某些方式告诉人相关的信息.计算机语言的形式化程度高于自然语言低于数学语言.计算机语言所表达的语义是唯一的，这不同于自然语言，有时自然语言所表达的意思会产生歧义，计算机语言表达的意思(语义)唯一，一个语句、一段代码、一个模块、一个函数表达的意思、完成的操作、执行的过程都是唯一的.这种唯一性进一步说明，阅读计算机语言书写的算法时要看到计算机语言背后所蕴含的编程思想.这一点与计算机程序是根据某个编程思想来编写的也完全相符.

在阅读计算机语言(如C语言)书写的算法时，要逐步提高分析总结的能力.先看懂每一个语句表达的意思、执行的过程、发生的操作，接下来要总结出每一段代码、每一个模块、每一个函数完成的功能.因此，在教学过程中，要逐步提高学生的学习能力与总结能力.在实际教学过程中，采用严蔚敏、吴伟民编写的《数据结构》(C语言版)(清华大学出版社)，[1]该教材比较抽象，里面的代码不是很完整，每个函数里面使用的局部变量没有相应的定义语句，函数里面调用的函数也没给出相应的完整实现代码，有些操作函数只给出函数的功能介绍没有给出完整的实现代码.[2]教材里面只给出一部分操作函数的实现代码，没有编写相关的主函数代码对操作函数进行调用，因此不能对操作函数的功能进行验证，对操作函数功能的理解还是比较抽象的.[3]在教学过程中，笔者编写了完整的程序代码并且提前印刷给学生，这些程序代码以一种抽象类型在某一存储结构上的完整实现为一份资料，里面给出了抽象类型的每个操作在存储结构上的完整实现，里面还编写了一个主函数对每个操作函数进行调用，从而可以对操作函数的功能有比较形象的理解，每份资料的后面还给出整个程序的运行结果，同时也根据主函数的执行过程画出数据结构的变化.

在教学过程中，让学生提前阅读编写的程序代码，每次上课时，都抽出十分钟左右的时间检查学生的学习情况.[4]检查的形式采用互动的方式，通过提问，了解学生对程序代码的理解.提问时，先让学生叙述每个语句发生的操作，然后让学生逐步概括出每个模块表达的意思，总结出每个函数的功能.让学生叙述执行过程时，同时也让学生描述数据结构的变化，并且与程序的运行结果结合起来.每次提问都进行评分并且记录，作为期末成绩的一部分.通过这种方式，可以让学生自觉利用本节的指导思想进行学习，从而逐步提高学习能力与总结能力.通过提问，还可以深入了解学生的学习情况，增进师生之间的情感交流.上课过程中，围绕本节的指导思想来展开教学，先讲每个语句发生的操作，同时画出执行的过程，进而概括出函数的功能，最后介绍如何调用函数.

2 采用两种方法

在整个教学过程中，始终采用两种方法：实际例子，结合算法，进行分析；面向对象(只采用引用形参与动态存储分配).

数据结构的算法是比较抽象的，单单只看算法，理解起来肯定是比较困难的.在阅读算法时，找出一个实际例子来运行算法程序，可以对每行代码的功能有更加形象的理解.这个方法可以更加形象地描述为：把人脑当作电脑，来运行程序代码.运转完以后，程序代码的功能会在脑袋里面留下更深的痕迹.下面以单链表的插入操作为例来讲述该方法.

(1)Status ListInsert_L(LinkList amp;L,int i,ElemType e)

(2){LinkList p; int j; LinkList s;

(3)p=L; j=0;

(4)while(pamp;amp;jlt;i-1)

(5){p=p-gt;next; j++;}

(6)if(!p||jgt;i-1) return ERROR;

(7)else {s=(LinkList)malloc(sizeof(LNode));

(8)s-gt;data=e;

(9)s-gt;next=p-gt;next;

(0)p-gt;next=s;

(11)return OK;

(12) }

(13) }

该操作函数的形参i里面的值为插入位置，形参e里面的值为插入元素.插入以前单链表已经存在，i里面的插入位置有可能太小(i≤0)有可能太大(i≥表长+2)也有可能合法(1≤i≤表长+1).当i≤0时，(3)p指向表头结点，j为0，(4)jlt;i-1马上为假，马上结束while循环，流程转到第(6)行，(6)jgt;i-1为真，返回ERROR，说明插入操作没有成功.当i≥表长+2时，(3)p指向表头结点，j为0，(4)(5)while循环里面p指针一直往后移，j里面的值一直加1，while循环结束时，p为null，j为表长+1，流程转到第( 6)行，if条件!p为真，返回ERROR，说明插入操作没有成功.当1≤i≤表长+1时，(3)p指向表头结点，j为0，(4)(5)while循环里面p指针一直往后移，j里面的值一直加1，直到p指向第i-1个结点，这时j为i-1，结束while循环，流程转到第(6)行，if条件(!p||jgt;i-1)为假执行else部分(7)～(12)，(7)动态分配一个结点的存储空间，动态分配完以后把结点的指针存放在s里面，(8)把形参e里面的插入元素存放在新结点的data成员里面，(9)使得新结点的next成员指向第i个结点，(10)使得第i-1个结点的next成员指向新结点，(11)返回OK，说明插入操作已经成功.该函数执行完以后，函数的返回值要么为OK要么为ERROR，如果返回值为ERROR，单链表的结构没有变化，如果返回值为OK，单链表的结构有变化，增加了一个新元素.由此我们可以得出ListInsert_L函数的功能，在单链表的第i个位置上插入一个新的元素，插入操作有可能成功也有可能不成功.

数据结构的传统教学只注重算法的具体实现，没有采用面向对象的方法.如果采用真正的面向对象语言(如C++语言)来描述数据结构，则面向对象语言的语法格式比较复杂，使得学习者很难透过复杂的语法格式来掌握蕴含的编程思想.因此，在教学过程中往往采用标准的C语言与引用类型的参数(简称引用形参)来描述数据结构.数据结构所使用的存储空间利用malloc、realloc函数来动态分配，当数据结构所使用的存储空间不再需要时，利用free函数来释放.利用malloc、realloc函数动态分配的存储空间只有当调用free函数以后才会释放.正因为引用形参与动态存储分配，才可以在C语言的基础上采用面向对象的方法来研究数据结构.可以借助下面的程序代码来更好地理解什么是面向对象.

(1)void main()

(2){InitList_L(L);

(3)ListInsert_L(L,1,40); ListInsert_L(L,1,30); ListInsert_L(L,1,20); ListInsert_L(L,1,10);

(4)ListDelete_L(L,1,e);

(5)PriorElem_L(L,30,pre_e);

(6)NextElem_L(L,30,next_e);

(7)GetElem_L(L,2,e);

(8)i=LocateElem_L(L,10,Equal);

(9)s=ListEmpty_L(L);

(10)i=ListLength_L(L);

(11)ClearList_L(L);

(12)DestroyList_L(L);

(13) }

这段代码里面，可以把单链表L看成一个对象，在主函数main里面面向L这么一个对象.(2)InitList_L(L);用来初始化L这么一个对象，(12)DestroyList_L(L);用来破坏L这么一个对象，在初始化(2)与破坏(12)之间就可以调用单链表的任何操作函数.(2)InitList_L(L);函数的功能相当于C++的构造函数，(12)DestroyList_L(L);函数的功能相当于C++的析构函数.(2)初始化以后单链表为空L=( )，(3)的作用为依次往单链表的第1个位置上插入一个元素，(3)整行执行完以后单链表为L=(10,20,30,40).(4)ListDelete_L(L,1,e);的作用为删除单链表L=(10,20,30,40)第一个位置上的元素，删除以后，单链表为L=(20,30,40)，参数e里面存放删除元素10.(5)PriorElem_L(L,30,pre_e);用来求单链表L=(20,30,40)里面30的前一个元素，执行完以后，单链表没有变化仍然为L=(20,30,40)，参数pre_e里面存放20.(6)NextElem_L(L,30,next_e);用来求单链表L=(20,30,40)里面30的后一个元素，执行完以后，单链表没有变化仍然为L=(20,30,40)，参数next_e里面存放40.(7)GetElem_L(L,2,e);用来获得单链表L=(20,30,40)里面的第二个元素，执行完以后，单链表没有变化仍然为L=(20,30,40)，参数e里面存放30.(8)i=LocateElem_L(L,10,Equal);用来求单链表L=(20,30,40)里面与10满足Equal关系的第一个元素的位置，因为不存在，所以执行完以后i为0.(9)s=ListEmpty_L(L);用来判断单链表L=(20,30,40)是否为空，执行完以后s里面的值为FALSE，说明单链表非空.(10)i=ListLength_L(L);用来求单链表L=(20,30,40)里面元素的个数，执行完以后i里面的值为3.(11)ClearList_L(L);用来清空单链表，使得单链表由L=(20,30,40)变为L=( ).

3 实现三个过程

知识传递可以分为三个过程：第一个过程，严蔚敏老师为了传播她的编程思想，把她的编程思想整理成文字，这些文字通过书出版发行.第二个过程，学生拿到出版发行的书以后，就要阅读文字，掌握里面蕴含的编程思想.第三个过程，学生掌握了编程思想以后，就要利用编程思想来编程进而解决实际问题.第一个过程对于学生来说，无须参与.在教学过程中，要求学生必须完成第二个过程与第三个过程，第二个过程的要求在“牢牢记住一个指导思想”里面已经有详细讲解.第三个过程就是要求学生经常编写程序，编程工具采用Microsoft Visual Studio 2008，编写的程序必须是完整可以运行的代码，编写的内容包括每种抽象类型在某一存储结构上的完整实现，并且把每种抽象类型封装成类模板以便以后可以直接拿来使用.基于目前手提电脑已经非常普及，实践教学时，要求学生每台手提电脑都必须安装Microsoft Visual Studio 2008.C#语言是网络上比较流行的一种语言，C#语言吸收C语言、C++语言精华部分隐藏比较复杂的指针部分.在练习编程时，让学生逐步利用C#语言来编写程序，从而为后序课程的学习打下坚实的基础，也为日后的软件开发做了充分的准备.Web服务是网页开发的一种中间件，Web服务有输入与输出，Web服务里面可以封装复杂的计算，可以把图论部分路径计算的程序代码封装在Web服务里面.路径计算的Web服务设计完以后，可以通过编程的方式来调用Web服务，把图的相关信息传给Web服务，Web服务计算完以后再把计算结果传回来，然后可以通过编程的方式对计算结果进行处理.在实践教学中，让学生编写如下问题的Web服务：最小生成树，关键路径，最短路径，两点间的所有路径.

4 学习四个方面

在教学过程中，要求学生学习以下四个方面：抽象类型的定义(包括逻辑结构的定义、逻辑算法的定义)；存储结构；实现算法；评价算法.

本节以抽象类型线性表为例来讲述学习的四个方面.抽象类型线性表里面可以有0个元素，也可以有1个2个3个4个……元素，除了第一个元素以外，每个元素都有一个直接前驱，除了最后一个元素以外，每个元素都有一个直接后继，可以在线性表的任何位置进行插入元素删除元素.线性表的逻辑操作如下：初始化操作InitList，破坏操作DestroyList，清空操作ClearList，判断空操作ListEmpty，求表长操作ListLength，获得元素GetElem，定位元素LocateElem，求前驱元素PriorElem，求后继元素NextElem，插入操作ListInsert，删除操作ListDelete，遍历操作ListTraverse.

抽象类型线性表的存储结构可以有七种：顺序表，单链表，双链表，循环单链表链表指针指向表头，循环双链表链表指针指向表头，循环单链表链表指针指向表尾，循环双链表链表指针指向表尾.

针对每种抽象类型的每种存储结构，可以根据抽象类型逻辑操作的要求与功能，写出每种逻辑操作算法的完整实现.

每种逻辑操作算法设计完以后，要从时间复杂度空间复杂度两个方面对算法进行分析，从而判断有没有更优的算法设计.下面以单链表的插入操作ListInsert_L为例，来评价算法，程序代码在“2采用两种方法”这一小节里面.该算法的问题规模为插入元素以前单链表的元素个数n，分三种情况来分析时间复杂度，①i里面的插入位置太小(i≤0)，这时算法执行所需要的时间T(n)为一个固定值，不随问题规模n的增大而增大，因此时间复杂度为T(n)=O(1)；②i里面的插入位置太大(i≥表长+2)，这时while循环体会执行n+1次，因此时间复杂度为T(n)=O(n)；③i里面的插入位置合法(1≤i≤表长+1)，最好情况i为1，while循环体执行0次，最坏情况i为表长+1，while循环体执行n次，平均情况while循环体执行n/2次，i里面的插入位置为各个合法值的概率相等，因此可以求平均情况下的时间复杂度，从而估算算法执行时间的增长率，时间复杂度为T(n)=O(n).该算法所需要的辅助存储空间S(n)为一个固定值，不随问题规模n的增大而增大，因此空间复杂度为S(n)=O(1).

在教学过程中，对于每种抽象类型，都给出具体的存储结构，并且针对存储结构来编写操作算法，最后从时间复杂度空间复杂度对操作算法进行分析.

5 掌握五种抽象类型

《数据结构》中主要的抽象类型有五种：线性表，栈，队列，树，图.

线性表的逻辑结构定义、逻辑算法定义在上一小节已经讲过.线性表的存储结构总共有七种，针对每种存储结构都编写了一份资料，每份资料里面都包括逻辑算法的完整实现、对算法进行调用的主函数、整个程序的运行结果、程序运行过程中数据结构的变化(用图表示).在编写资料时，不同份资料里面同一个算法的第一行(也就是同个操作函数的第一行)使用相同的函数名、相同的形参、相同的返回值类型，对算法进行调用的主函数也相同，因此程序的运行结果也相同.从这七份资料可以更好地理解线性表是一种抽象类型.在编写源代码时，用到赋值形参函数指针变量.

(1)void Visit(ElemTypeamp; e)

(2) {printf("%d ",e);}

(3)void Add(ElemTypeamp; e)

(4) {e++;}

(5)void ListTraverse_L(LinkListamp; L,void (* visit)(ElemTypeamp; e))

(6){LNode* p; p=L-gt;next;

(7)while(p!=NULL) {(* visit)(p-gt;data); p=p-gt;next;}

(8) }

(9)ListTraverse_L(L,Visit);

(10)ListTraverse_L(L,Add);

第(9)行第二个实参Visit为一个函数名，代表第(1)行Visit函数的入口地址，第(9)行调用第(5)行的ListTraverse_L函数，流程转到第(5)行，第(5)行的visit是赋值形参函数指针变量，另外开辟存储空间，接收实参Visit传过来的函数入口地址，接收完以后，形参visit指向第(1)行的Visit函数，指向以后，第(7)行的(* visit)(p-gt;data);相当于调用第(1)行的Visit函数，也就是相当于Visit(p-gt;data);.第(9)行ListTraverse_L(L,Visit);整行的作用为：在ListTraverse_L函数里面，利用while循环，依次把单链表的每个元素作为实参调用第(1)行的Visit函数从而显示每个元素的值，第(9)行调用ListTraverse_L函数以前以后，单链表的结构没有变化.第(10)行ListTraverse_L(L,Add);整行的作用为：依次把单链表每个元素的值加1，调用函数以前以后，单链表发生变化.[4]

抽象类型栈逻辑结构的定义为：栈里面可以有0个元素，也可以有1个2个3个4个……元素，除了第一个元素以外，每个元素都有一个直接前驱，除了最后一个元素以外，每个元素都有一个直接后继，只能在栈顶位置插入元素(入栈)删除元素(出栈).抽象类型栈的逻辑操作如下：初始化操作InitStack，破坏操作DestroyStack，清空操作ClearStack，判断空操作StackEmpty，求元素个数操作StackLength，获得栈顶元素操作GetTop，入栈操作Push，出栈操作Pop，遍历栈操作StackTraverse.在编写源代码时，抽象类型栈的存储结构采用两种：顺序栈、链式栈.在这一章里面，给出了利用栈的一个例子：把递归函数转换成非递归函数.

抽象类型队列逻辑结构的定义为：队列里面可以有0个元素，也可以有1个2个3个4个……元素，除了第一个元素以外，每个元素都有一个直接前驱，除了最后一个元素以外，每个元素都有一个直接后继，只能在队尾插入元素(入队)，只能在队头删除元素(出队).抽象类型队列的逻辑操作如下：初始化操作InitQueue，破坏操作DestroyQueue，清空操作ClearQueue，判断空操作QueueEmpty，求元素个数操作QueueLength，获得队头元素操作GetHead，入队操作EnQueue，出队操作DeQueue，遍历队列操作QueueTraverse.在编写源代码时，抽象类型队列的存储结构只采用链式队列.链式队列编写完以后，就可以直接使用，使用时，把队列元素换成实际的数据类型即可.

树这一章的知识点可以概括为：二叉树、二叉排序树、线索二叉树、平衡二叉树、线索二叉排序树、线索平衡二叉树、平衡二叉排序树、线索平衡二叉排序树、孩子兄弟树.对于二叉排序树，每个结点的关键字，总大于左子树所有结点的关键字，总小于右子树所有结点的关键字.线索二叉树是在结点没有左孩子或者没有右孩子的情况下加上线索得来的.平衡二叉树的每个结点左子树的高度与右子树的高度最多相差1.在树这一章里面，总共编写了9份资料.

图的知识点包括：创建图，遍历图，深度优先生成树，广度优先生成树，连通分量，强连通分量，最小生成树，拓扑排序，关键路径，最短路径.[5]

[1] 严蔚敏，吴伟民．数据结构：C语言版[M]．北京：清华大学出版社，2003:18-39．

[2] 赵福生.最短路径的教学[J].福建电脑,2011(6):213-214.

[3] 戴传江.研究型理工科高校人文素质教育的创新[J].四川文理学院学报，2012(2):150-153.

[4] 吴开腾,覃燕梅.提高“数值分析”课程教学有效性的策略[J].内江师范学院学报，2011(4)：76-78 .

[5] 王 猛,覃燕梅,吴开腾.论程序设计教学中的习惯养成理念[J].内江师范学院学报,2011(8)：83-88.

[责任编辑邓杰]

MethodandPracticeinTeachingReformofDataStructureCourse

ZHAO Fu-sheng

(Mathematics and Computer Science School of Quanzhou Normal University,Quanzhou Fujian 362000,China)

Five suggestions of teaching reform are put forward and analyzed in detail with examples. The the ideas are practiced and perfected in the classroom teaching. The teaching results show that the teaching reform is effective.

DataStructure;guiding ideology;object-oriented;abstract type.

2013-04-09

赵福生(1980—),男，福建泉州人.助教,硕士，主要从事软件与算法研究.

G642

A

1674-5248(2013)05-0124-05