数据驱动的数据结构课程案例设计研究与实践

张安勤 田秀霞 张挺

摘  要：我们在各行各业的诸多领域以及学习和生活中产生了大量的数据，现在的时代已经是一个数据时代。文章分析了当前数据结构课程教学中存在的问题，结合当前数据时代前沿研究领域和行业应用，设计了单个知识点的案例和融合多个知识点的综合案例。在此基础上，对教学方法和考核方式进行了改革。我们的教学改革拓展了学生的知识和技能，提高了学生分析和解决实际复杂问题的综合素质和创新能力。

关键词：数据结构;数据驱动;案例设计;教学改革

中图分类号：TP311     文献标识码：A

Abstract：Lots of data are generated in many fields of our study and life.Our present time is the data era.This paper analyzes the main problems existing in the teaching of data structure course at present.Combined with frontier research fields and industrial applications in the current data era，this paper designs the course cases with a single knowledge point and comprehensive cases integrating multiple knowledge points.On this basis，the teaching methods and assessment methods are reformed.Our teaching reform has expanded students' knowledge and skills and has improved students' comprehensive quality and innovation ability to analyze and solve complex practical problems.

Keywords：data structure;data driven;case design;teaching reform

1   引言（Introduction）

数据结构课程是计算机相关专业的专业基础课程，在专业课程体系中起着承上启下的作用。课程对培养学生的数据模型抽象能力、算法设计能力和复杂的程序设计能力具有重要的作用。课程所讨论的知识内容和算法技术，无论对于后续学习其他专业课程，或是将来从事软件开发工作，都是必须掌握的基础内容[1]。

我们的各行各业学习和生活中的诸多领域产生了大量的数据，现在的时代已经是一个数据时代，数据已经成为一种新能源，对数据的存储、处理，以及分析面临着巨大的需求。

在这个数据时代，一方面，我们的《数据结构》课程内容仍然是前沿研究领域的重要基础;另一方面，这些基础理论内容也需要针对数据时代的新问题与新挑战进行调整和改革。但目前，我们的课程教学采用传统主流数据结构的知识讲解，伪代码描述算法，再附加一些课程实验的教学模式，已无法适应数据时代的需求和挑战。因此，在《数据结构》课程教学过程中，需要将课程基础理论内容与数据时代的特点相融合、与学界和业界前沿领域相融合，兼顾基础知识与学科前沿、理论与实践并重。

2  教学中存在的问题及原因（Problems and reasons existing in the teaching ）

在数据结构的实际教学中，存在的问题主要有两种情况：

（1）学生基本理论听得懂，算法理解和实现存在困难。甚至出现笔试分数很高，但是实验和课程设计环节无法完成算法实现和一个完整的应用系统的情况。

（2）学生觉得学习内容枯燥无味，对课程内容没兴趣。

造成这种情况的原因主要有以下几点：

（1）课程本身有难度，课程概念繁多、体系复杂、操作种类多以及部分算法难理解等特点[2]。

（2）受数据结构传统教学的影响，重视理论部分的课堂教学，轻视实践环节。虽然近几年，由于我校定位为应用型本科大学，对实验和实践环节的重视情况有所改善，但是力度不够，没有具体的方法和措施。

（3）由于目前主流数据结构教材中提供的都是伪代码描述，学生无法看到完整的实现过程，不能产生直观的印象，造成算法理解困难。这方面，目前笔者所在数据结构教学團队已经做了一些工作，把教材中的伪代码已经用Java语言完整地实现出来，并提供给学生。有些代码在实验课程中对学生进行了演示、讲解和分析。

（4）教材和实验中的案例老套，没有紧跟当前学术和业界的最新发展，难以吸引学生的注意力，学生的学习和编码没有积极性。

《数据结构》课程的教学目的是分析待解决问题数据的特性，选择合适的逻辑结构和相应的存储结构以及相关算法，并能从时间和空间两个角度来衡量算法的性能。因此在课程的内容中必须有能够体现从数据角度进行分析，选择逻辑结构、存储结构和相应算法，并对算法进行衡量的案例。同时，对于面向应用型的本科专业的学生来说，解决实际问题的能力尤为重要。因此，设计与当前学术和业界最新发展和应用结合的案例，不仅可以提高学生的课程学习的热情，而且也可以在教学过程中培养学生的数据思维与学科前沿意识。

3   案例设计（Case design ）

3.1   案例设计的要求

案例需要满足的要求：

（1）切合教学的知识点;

（2）与学界和业界前沿领域相融合;

（3）学生比较容易接受，能够激发学生兴趣。

根据以上要求，笔者所在教学团队根据教学的知识点设计了针对知识点的教学案例和融合各知识点的综合案例，这些案例有的来源于学生的生活，有的来源于课程教学团队老师的科研项目[3]，这样的和实际生活相联系的项目[4]不仅能激发学生的兴趣，而且和当前数据时代的发展紧密结合。我们在实际教学过程中，配合案例教学，我们还对教学方法和考核方式进行了改革。

3.2   结合知识点的教学案例

数据结构课程的主要知识点有线性表、栈、队列、串、二叉树、图、查找、排序。数据结构教学团队设计的案例围绕课程的主要知识点展开。

以案例班级社交网络分析为例，同学收集整理了班级同学手机通话和短信数据、微信数据、QQ数据和邮件数据，对数据进行了预处理，分析了数据的逻辑结构，并选择合适的存储结构，建立班级社交网络，再按照一定算法找出核心人物、活跃人物和指定同学的交往圈子，并与实际情况对比。在这个过程中，他们不仅理解了数据处理的整个过程，也体会到了课程内容在实际应用和理论研究中的重要意义。

不同知识点的案例如下表1所示。

1 手机通讯录管理 线性表线性表的顺序存储和链式存储 手机通讯录上的联系人数据的逻辑结构是线性结构，手机联系数据在手机中用顺序表存储和链表存储时，实现插入、删除和查找功能

2 分隔符匹配 栈的先进后出，入栈和出栈 检查字符串数据中分隔符是否左右匹配。分隔符包括大括号，中括号，小括号，每个分隔符都要左右进行匹配，如果不匹配报错并输出不匹配位置

3 手机通话数据管理 队列的先进先出，入队和出队 手机通话数据可以分为三类：未接来电，已接来电和已拨电话。这三类数据按照事件发生的时间先后以队列形式存储和管理[5]

4 英文词频统计 串的概念、基本操作以及串的模式匹配算法 一首英文的歌词或文章或小说的文本文件。从文件读出字符串。将所有大写转换为小写，将所有其他分隔符（替换为空格，分隔出一个一个的单词，并统计单词出现的次数

5 图像的压缩与解压缩 二叉树中的哈夫曼树和哈夫曼编码 图像中每个灰度值出现的概率是不相同的，概率高的灰度值用短码，概率低的灰度值用长码，可以实现压缩编码。获取图像的灰度值，计算每个灰度值的频率，构造哈夫曼树，进行哈夫曼编码和解码，实现图像的解压缩

6 班级社交网络分析 图的构建和图的遍历算法 收集班级同学之间的手机通话数据，短信数据，微信数据和QQ数据，建立班級同学社交网络图。查找核心同学，活跃同学，以及指定同学的交往圈子

7 警察找坏人 不同查找算法的思想 有m条包含有身份证号码的嫌疑人信息，其中有n个坏人的身份证号码，如何把m个人中的n个坏人找出来。如果m的数据量非常大，应该如何查找

8 个性化推荐排序 不同排序算法的思想 电商的个性化推荐一般都转化成点击率预估问题，把用户点击率越高的商品排在前面，即根据商品点击率降序排列。输出排名前100的商品

3.3   综合教学案例

除了针对各个知识点的案例外，课程团队还设计了融合多个知识点的综合案例。

笔者所在大学是以电力为特色的学校，为了使学生了解和体会自己所学知识和电力的关系，在电力行业的应用，我们设计了综合案例2低压配电网构建。低压配电网直接和广大用户相联系，是电力系统中极为重要的一环。基于最小生成树的低压配电网布局方法操作简单、实用性强，是一种有效地电网规划层面的辅助决策方法[6]。这个案例主要是利用课程中最小生成树算法来进行低压配电网构建。

综合案例表如表2所示。通过这些案例的实现，学生在理解理论模型的同时，熟悉和强化了模型的实际应用，解决复杂实际问题的综合能力和创新能力得到了提高。

1 小说人物分析 下载小说，存储为文本文档。任取其中10个人物，考虑他们的姓名、别名等因素。主要功能包括：（1）统计每个人物在小说中出现的次数。（2）统计每个人在小说中出现的篇幅跨度（第一次出现和最后一次出现的行间距），并按照篇幅跨度排序。（3）给出10个人物的交往情况;如果两个在相距较短的一段文字中出现，我们认为两个人有交往关系，距离越短，关系越近。找出10个人中：关系最紧密的两个人，关系最不紧密的两个人。（4）输入一个人名，列出该人和其他人关系的紧密程度排名

2 低压配电网构建 若要在n个小区之间铺设电网线路，只需要架设n-1条线路即可。以最低的经济代价建设这个电网，是一个图的最小生成树问题

3 地铁换乘推荐 利用上海市地铁交通网数据，给出从指定起点到终点的可推荐路线，并按照最短时间，最少换乘对推荐路线排序

4 出租车合乘系统 由于出租车的运输方式属于“点对点的最短路径运输”[7]，如果要提供合乘服务，必须是在最短路径上的乘客才能提供接载多位乘客的任务。利用最短路径，字符串模式匹配的算法，实现乘客从指定起点到终点的出租车合乘要求

4  教学方法的改革（The reform of teaching methods）

针对各个知识点案例和综合案例的引入，我们对教学方法做了一些改革。

（1）提出问题，唤醒学生学习课程的好奇心。在课程的第一节课，课程绪论中就提出针对各个知识点的案例，吸引学生注意力，提高学生对即将要学习课程的兴趣和积极性。

（2）研讨交流[8]。课程的每个章节的知识点学习后，引导学生围绕课堂的基本知识点对案例问题的求解算法进行研讨并在课下实现案例，在实验课上进行点评，并请完成优秀的同学走上讲台和大家分享交流。

这种教学方法不仅训练了学生表达能力，也提高了同学的学习积极性，得到了同学、同行和督导老师的认可。

（3）线上线下相结合。课程中引入各个知识点的案例，并对案例进行分析，对课程知识点讲解时间造成了影响，我们采用的方法是把课程的基本知识点的概念性知识录成视频提前放到课程网站上，提前让学生预先在网站上学习，有些容易理解的概念性知识在课堂上可以少花时间或不花时间，大大提高课堂教学的效率。

（4）分等級的综合案例。针对综合案例，我们是在课程结束后，专门安排一周的时间来完成。因为同学的数据分析能力、算法设计能力和代码编写能力参差不齐，我们对综合案例题目按照难易程度分成难、中、易三个等级，共25个案例，同学可以根据自己的能力进行选择。

（5）算法设计比赛。围绕课程，我们还安排了整个学院的算法设计大赛，赛题主要针对大数据问题的算法设计。比赛的过程中参照正式ICPC（国际大学生程序设计竞赛）比赛的规则为参赛选手发放象征着“通过”的气球，通过一题，发放题目对应颜色的气球。这样的比赛提高了学生算法设计和编程的兴趣，促进了学生课程学习的积极性。

5  考核方式的改革（The reform of assessment methods）

在课程的考核方式上，改变传统的一次考试决定课程考试结果的情况。整个课程的成绩由线上学习成绩，课程知识点案例完成成绩，参加算法大赛成绩，期末考试的卷面成绩综合评价。这种考核方式综合评价了自学能力、抽象建模能力和编程能力。避免了出现考分高，动手编程能力差的情况。综合案例的实现相当于一门独立的1学分的实践课程，根据完成情况另外计分，考核了学生解决复杂实际问题的综合能力和创新能力。

6   结论（Conclusion）

当前的时代是数据的时代，数据已经成为一种新的能源。数据已经成为当前学界和业界研究的热点。以后的软件开发和研究都将以数据为中心。数据结构课程正是这样一门融合数据分析，数据存储和算法设计的一门课程。我们在课程的教学过程中，设计了以数据驱动的，针对课程知识点的案例和融合多个知识点综合案例。结合案例教学，对教学方法和考核方式进行了改革，对培养学生综合运用所学知识与技能分析和解决复杂实际问题的综合能力和创新能力起到较好的效果。后续，将进一步结合团队老师的科研项目，完善案例，让学生早一点体会课程学习在科学研究中的作用，并对课堂教学进行更深入的改革，提高学生培养的质量。

参考文献（References）

[1] 陈青青.数据结构课程中分步式案例设计的探索与实践[J].计算机教育，2019（10）：109-112.

[2] 张兆维，刘慧.兼顾考研与就业的数据结构课程教学探索[J].计算机教育，2019（10）：82-85.

[3] 杨武，卢玲，陈媛.数据结构课程的大案例构建方法[J].计算机教育，2018（7）：92-95.

[4] 霍玲玲，王智，孙江.数据结构教学方法的研究[J].计算机教育，2015（2）：73-76.

[5] 叶核亚.数据结构（Java版）（第4版）[M].北京：电子工业出版社，2015.

[6] 谢建强.基于最小生成树的低压配电网布局研究[J].电气技术，2016（6）：86-89.

[7] 邓向林.基于动态规划算法的出租车合乘模式研究[J].微型机与应用，2013（8）：79-81.

[8] 张玉红，李培培，胡学钢.关于人工智能专业中数据结构课程教学的几点思考[J].计算机教育，2019（8）：106-109.

作者简介：

张安勤（1974-），女，博士，副教授.研究领域：数据挖掘.

田秀霞（1976-），女，博士，教授.研究领域：信息安全.

张   挺（1979-），男，博士，副教授.研究领域：图像处理.