以问题为导向的数据结构课程PBL教学方法研究

摘要：本文针对数据结构课程的特点，提出了以问题为导向、以实际问题为原型的PBL教学方法。同时提出，相对于传统的教学方法，以问题为导向的数据结构课程PBL教学方法能够更好地培养学生分析问题和解决问题的能力，能够有效地提高学生的学习兴趣和编程能力。

关键词：数据结构;教学方法;引导式;PBL;算法

中图分类号：G434  文献标识码：A  论文编号：1674-2117（2022）14-0090-03

困扰学生的问题

数据结构是计算机专业的核心课程之一，也是一门被公认的难、广、多的课程，其中的“难”表示理解难，“广”表示算法广，“多”表示内容多。对初学者来说，往往有一系列的问题困扰着他们，如什么是数据、如何表示数据、数据之间存在哪些逻辑关联等。笔者认为，要想让学生学好这门课程，首先须帮助學生解开这些疑问。

1.数据的表示

数据是信息的表示形式，在现实世界中，数据往往以文字的形式呈现出来，而在计算机的世界里，数据是以信号的形式呈现出来的，如电信号、光信号或脉冲信号等，用信号的不同状态之间的组合来表示不同的数据。在数据结构中的数据元素是指同一种数据类型中的单个数据，如整数1是整数数据类型中的一个数据元素，某个学生是“学生”数据类型中的一个数据元素，因此数据元素是数据结构处理的基本数据单位。

在数据结构中还有一个基本术语就是数据项。一个数据元素可能由多个数据项组成，如一个学生数据元素包含了学号、姓名等数据项。数据项是数据结构中处理的最小数据单位。

2.数据元素之间的逻辑结构

现实问题中的数据元素之间的组织存在一定的内在关系，这些关系是数据元素之间固有的，被称为逻辑关系。例如，有一些数据元素之间存在一对一的线性关系，如一个班的学生信息一般采用线性表的形式进行管理;有一些数据元素之间存在一对多的层次结构关系，如家谱中的成员一般呈现出一对多的层次结构;还有一些数据元素之间存在着多对多的关系，如朋友圈中的成员之间就存在着多对多的网状关系。根据拓扑结构划分，常见的数据逻辑结构有线性结构、树型结构和图型结构。[1]

3.分析数据逻辑结构的原因

为什么要分析数据元素之间存在的逻辑结构呢？这里先来看一个简单的例子。相信每个人都有去图书馆借书的经历，只要观察就能够发现，图书馆的书是按照某种次序排列的。为什么会这样呢？因为图书馆的书很多，而且要对书进行频繁的借阅、归还和增加书籍等操作。当数据量比较大，而且要对这些数据进行大量操作时，就有必要对数据进行组织。那么，如何进行组织呢？这就要分析数据元素之间存在哪些逻辑关系。对于图书来说，图书有类别、书名、作者、出版时间等属性，可根据图书的这些属性对图书进行组织，如根据图书的类别可以按层次结构组织，根据书名、作者、出版时间可以按线性结构组织。

总之，当数据量很大，而且对这些数据要进行大量的增、删、改、查等操作时，合理地对数据进行组织可以大大提高操作的效率，而分析数据元素之间的逻辑结构是对数据进行合理组织的基础。

4.数据的映射方式

拓扑图可以非常直观地在二维平面上将数据元素及数据元素之间的关系表示出来。然而，根据冯·诺依曼体系结构的原理[2]，计算机的存储结构是一种线性结构，如何将二维的拓扑结构映射到一维的计算机存储器是数据结构这门课程研究的一个重要课题。在已有的研究结果中，映射的方式主要有四种，分别是顺序映射、链式映射、索引映射和哈希映射。根据不同的映射方式，得到数据在内存中的不同存储结构，分别称为顺序存储结构、链式存储结构、索引存储结构和哈希存储结构。

顺序映射是将拓扑图上的元素先按照一定的规则排列成一维线性结构，然后将这组线性化以后的数据元素按顺序存储在一块连续的内存空间上。

链式映射是指为每个数据元素增加一个指向与其相关联的元素的指针（一种属性），每个元素在内存中的存放位置可以随意选择，但是每次在存放一个数据元素时，都要在这个数据元素的指针上记录与它关联的数据元素在内存中的存储地址。这里的指针属性就类似于拓扑结构中的边。

索引映射是指专门使用一个表格记录每个数据元素的关键字以及这个数据元素在内存中的存储地址。数据元素的关键字要求具有唯一性，能唯一地代表一个数据元素。与链式映射类似的是，在索引映射方式下，数据元素在内存中的存储位置也是任意的。与链式映射方式不同的是，索引映射是单独用一个表格来对数据元素之间的关系进行管理的，而不是为每个数据元素设置一个指针。

哈希映射是指先将每个数据元素映射成一个唯一的整数，然后为这组整数设计一个数学函数，这个数学函数被称为哈希函数，通过这个哈希函数将这组整数均匀地映射到一个指定的整数范围内（这个范围与数据元素个数相关，一般为数据元素个数的1.5倍），如[0，1.5n）这样的闭开区间，其中n为数据元素的个数。在内存上开辟一块大小为1.5n的连续的内存空间，按照哈希函数映射出来的数字，将每个数据元素存储在这块内存空间的一个确定的位置上。

综上所述，数据结构的本质内涵是研究现实问题中的数据和数据之间的逻辑关系，利用这些关系在计算机内存中合理地对数据进行组织，以便实现高效的算法。

5.数据结构与程序设计语言的关系

数据结构与程序设计语言的关系类似于设计师与工程师的关系。数据结构的重点是分析事物之间存在的关联，将事物及它们之间的关联抽象成数据元素和关系，设计出拓扑结构图，进而研究如何将拓扑结构图映射到计算机存储器中，最终的目的是能够对这些数据元素进行高效地操作。程序设计语言是具体工作的执行者，它负责在计算机上申请内存，将数据元素存储到内存中的某个位置上，然后编写相关的操作函数来实现对这组数据的操作。

6.数据结构与算法的关系

如果把编写一个计算机程序比作一场战役，其中的枪支弹药等武器好比程序中的数据，士兵们在战斗中的作战方法好比程序中的算法，那么武器的摆放结构会影响士兵的作战效率，而士兵的作战效率最终影响战役的成败。因此，数据结构的好坏会影响算法的执行效率，而算法的执行效率决定了一个程序的成败，这里引用著名计算机科学家N.Writh提出的一个公式来总结数据结构与算法的关系，那就是“数据结构+算法=程序”。[3]

PBL教学方法

PBL是Proble Based Learning的首字母缩写，它是一种从实际问题出发，运用教学內容中的知识和技能，一步一步解决实际问题的教学方法。

实践证明，在数据结构课程中运用PBL教学方法能够更好地培养学生分析问题和解决问题的能力，能够有效地提高学生学习和编程的兴趣。

笔者在数据结构课程中运用PBL教学方法的过程如下：首先，为每种数据结构类型设计一个以上现实问题的原型，引导学生找出问题原型中的数据对象和数据元素，结合要实现的操作，分析和挖掘出数据元素之间存在的逻辑关系，并将这些数据元素和它们之间的逻辑关系抽象成一个拓扑结构图;然后，结合操作的要求，选择一种数据存储结构;最后，用一种编程语言编写计算机程序，将拓扑结构图映射到计算机的存储器上，并实现相关的算法对数据进行操作，最终完成解决实际问题的目的。

下面，笔者以约瑟夫环为例，说明在数据结构课程中运用PBL教学方法的过程。

第一步，阐明问题。N个人围成一个环，给每个人进行编号，从1到N，并且给每个人的手上写上一个正整数作为该人的密码。取出编号为1的人的密码m，从编号为1的人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，从它的顺时针方向的下一个人开始重新从1报数，如此下去，直至全部人出列为止。最后按照出列的顺序输出每个人的编号。

第二步，分析数据元素。把环中的每个人抽象成一个数据元素。

第三步，分析数据元素之间的逻辑关系。每个数据元素有一个前驱和一个后继，即一对一的线性关系。

第四步，分析存储结构。问题中指出从顺时针方向报数，并且涉及大量的移除操作，因此选择单向环形链表作为数据存储结构，代码如图1所示。

第五步，设计算法。

①创建约瑟夫环L：List_create（）;

②定位到m处的结点node：List_RetrieveNode（&p，m，&node）;

③将node结点的密码赋值给m，并输出node结点的id（如图2）;

④查找node的前驱：List_prior（&node，&prior）;

⑤如果prior！=node，则大于1个结点，删除node，重复执行②到⑤;如果prior==node，则该结点为最后一个结点，程序结束。

第六步，使用一种编程语言进行实现。

总结

本文从数据结构的本质内涵出发，剖析了数据的含义及表示方式，分析了数据元素之间、数据结构与程序设计语言之间以及数据结构与算法之间存在的关系。在帮助学生理解数据结构内涵的基础上，利用PBL教学方法，从实际问题出发，分析实际问题中的逻辑模型和数据结构，设计相应的算法，利用程序设计语言实现对问题的求解过程。

参考文献：

[1]沈良.试论关于高校计算机网络课程教学改革的探讨[J].企业导报，2012（11）：194-195.

[2]李杰，青小渠，任堰牛.对比教学法在单片机课堂教学中的应用[J].计算机教育，2014（08）：58-60.

[3]李志华.本科《计算机网络》课程的教学改革实践[J].教育教学论坛，2012（01）：164-165.

作者简介：刘福泉（1981.12—），女，浙江农林大学暨阳学院计算机专业教师，讲师，研究方向为计算机网络、大数据、机器学习。