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

    

    

    

    摘要：数据结构是计算机专业的核心课程之一，它在计算机专业人才培养中起着举足轻重的作用。数据结构也是一门被公认的难、广、多的课程，作者针对数据结构课程的特点，提出了以问题为导向、以实际问题为原型的PBL教学方法。与传统的教学方法相比，以问题为导向的数据结构课程PBL教学方法能够更好地培养学生分析问题和解决问题的能力，能够有效地提高学生的学习兴趣和编程能力。

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

    中图分类号：G642 ?文献标识码：B ?论文编号：1674-2117（2021）05-0103-04

    困扰学生的问题

    “数据结构”是一门被公认的难、广、多的课程，其中的“难”表示理解难，“广”表示算法广，“多”表示内容多。对于初学者来说，往往有一系列的问题困扰着他们，如什么是数据，如何表示数据，数据之间存在哪些逻辑关联，如何利用数据元素之间的逻辑关联关系组织数据以便高效地对数据进行操作，如何将数据和数据的关联关系映射到内存，数据结构与编程语言以及数据结构与算法有什么关系等。要想让学生学好这门课程，首先必须帮助学生解开这些疑问。

    1.数据的表示

    数据是信息的表示形式，是信息的载体。[1]计算机程序的实质是对信息的处理，也就是对数据进行处理。在现实世界中，数据往往以文字的形式呈现出来，而在计算机的世界里，数据是以信号的形式呈现出来的，如电信号、光信号或脉冲信号等，用信号的不同状态之间的组合来表示不同的数据。二进制信号是冯·诺依曼计算机体系结构中数据的表示形式，二进制信号是最容易产生的信号形式，如用高电平表示0，低电平表示1，或者用有光信号表示1，没光信号表示0等。根据冯·诺依曼计算机体系结构，首先需要将数据存储在计算机的内存中，计算机内存中表示数据的方式是使用线性的二值位串，如“0100100011110110”到底表示了几个数据、表示什么数据，需要进行事先约定。如果规定用每8位二进制数表示一个英文字母，那这8位二进制数据就能表示256个英文字母，而英文字母大小写一起才52个，因此，用8位来表示英文字母足够了。如果用8位来表示数值数据，显然就不够了。因此，对不同的数据就要指定不同的表示方法，于是就有了计算机程序中不同的数据类型。

    数据结构中的数据元素是指同一种数据类型中的单个数据，如整数1是整数数据类型中的一个数据元素，某个学生是“学生”数据类型中的一个数据元素，因此，数据元素是数据结构处理的基本数据单位。

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

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

    现实问题中的数据元素之间的组织可能存在一定的内在关系，这些关系是数据元素之间固有的，称之为逻辑关系。有一些数据元素之间存在一对一的线性关系，如一个班的学生信息一般采用线性表的形式进行管理，如下表所示。

    有一些数据元素之间存在一对多的层次结构关系，如家谱中的成员一般呈现出一对多的层次结构，如图1所示。还有一些数据元素之间存在着多对多的关系，如朋友圈中的成员之间就存在着多对多的网状关系（如图2）。数据元素之间的逻辑结构一般可以在二维平面上用点和边的形式抽象出来。其中的点就是数据元素，边就是数据元素之间存在的某种关联。这种用点和边抽象出来的二维结构图形称为数据元素的拓扑结构。根据拓扑结构划分，常见的数据逻辑结构有线性结构、树型结构和图型结构。[2]

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

    图书馆的书为什么是按照某种次序排列的？因为图书馆的书很多，而且要对书进行频繁的借阅、归还和增加书籍等操作，而个人书架本身书不多，对书进行的相关操作也比较少。由此可见，当数据量比较大，而且要对这些数据进行大量操作时，有必要对数据进行组织。那么，如何进行组织？这就需要分析数据元素之间存在哪些逻辑关系。例如，图书有类别、书名、作者、出版时间等属性，根据图书的这些属性，对图书进行组织，如根据图书的类别可以按层次结构组织，按书名、作者、出版時间可以按线性结构组织。

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

    4.数据的映射方式

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

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

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

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

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

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

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

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

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

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

    PBL教学方法

    PBL（Proble Based Learning）是一种从实际问题出发，运用教学内容中的知识和技能，一步一步解决实际问题的教学方法。国际和国内的部分高校采用PBL教学方法以后，在教学中取得了較好的效果。

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

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

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

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

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

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

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

    第五步，设计算法。

    ①创建约瑟夫环L。

    List_create（）

    ②定位到m处的结点node。

    List_RetrieveNode（&p，m，&

    node）;

    ③将node结点的密码赋值给m，并输出node结点的id。

    m = node-> elem.pwd

    print（node-> elem .id）

    ④查找node的前驱。

    List_prior（&node，&prior）;

    ⑤如果prior！=node，则大于1个结点，删除node。

    重复执行（2）-（5）

    如果prior==node，则该结点为最后一个结点，程序结束。

    ⑥使用一种编程语言进行实现。

    总结

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

    参考文献：

    [1]王绍强.应用型本科计算机网络教学改革的研究与实践[J].计算机教育，2009（18）：16-18.

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

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

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

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