大数据时代的医学院校数据结构课程教学改革初探

邢丹 姚俊明 张红伟

摘要：为了适应大数据时代对计算机专业的用人需求，总结了数据结构课程中常用的概念、特点、在前沿领域的应用，并在数据、线性表、哈希表、B-树及图的知识点中融入热点问题及大数据技术的应用实例，对学生实施启发式教学，使学生在掌握数据结构课程知识点的同时，进一步增强自主学习和计算机技术的实际应用能力。

关键词：数据结构；大数据；启发式教学；教学改革；自主学习

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）20-0114-03

Teaching Reform Preliminary Discussion of Data Structure Course in the era of Big Data

XING Dan1， YAO Jun-ming1， ZHANG Hong-wei2

（1.School of Medical Information Engineering of Jining Medical University， Rizhao 276826， China； 2.The Library of Jining Medical University， Jining 272067， China）

Abstract： In order to adapt to the era of big data on the computer professional needs of the people， summary the common concept， data structure course characteristics， applications in frontier areas， and in the data， linear table， hash table， application examples into hot issues and big data technology of B- tree and graph knowledge， elaborated how to carry out the heuristic the teaching of students. making students grasp the knowledge points in the course of data structure at the same time， to improve the ability of self-study and innovation.

Key words： Data Structure； Big Data； Heuristic Teaching； Teaching Reform； Autonomous Learning

1 问题的提出

计算机科学与技术专业的教学应当适应未来社会的用人需求，大数据作为国家的发展战略，能否为社会培养和输送一大批具备大数据素养的高级人才，满足社会对大数据人才日益旺盛的需求，是决定我国在新时期能否抢夺战略机遇期的关键。大数据既是一类数据，也是一项技术，还是一种理念。大数据是一种人人都需要掌握的科学方法论，是信息时代认识和改造我们这个世界的有效工具。因此，作为计算机专业的骨干课程——数据结构，迫切需要融入前沿知识、大数据理论和技术相关的知识。同时，由于数据结构课程逻辑性强，学生学起来比较吃力，笔者总结多年的教学经验发现，学生碰到较难掌握的问题时，第一反应就是有何用。很多学生仅仅是为了学习而学习，忽视了数据结构的重要作用，学习一段时间之后就会失去兴趣，学习效果较差。为了激发学习的积极性，笔者深入研究了常用数据结构在前沿领域的应用，系统地学习了大数据原理和技术，针对大数据中使用到的数据结构，总结了数据结构在热点问题中的应用场合和大数据技术中用到的数据结构类型，将其贯穿到数据结构课程教学始终。在讲授相关知识点时，抽取出前沿技术领域的主要核心思想，引导学生思考为了适应大数据领域的特点需要进行何种改进和优化。这种启发式教学方法的讲授使学生的学习更加有的放矢，也能增强学生对数据结构课程对后续课程的重要指导意义，培养了学生的创新思维、大数据思维和素养。

2 数据

在讲授数据概念时首先以C语言中的整数和实数为例，较复杂的数据还包括由多个分量组成的结构体的数据。在大数据时代处理的数据类型要比早期多，既包括图像、视频、音频等非结构化的大量数据，也意味着对大数据的处理难度要大，因此要学习数据结构，以后还要学习大数据处理技术。这样的讲解在学习知识点的同时，也激励学生进一步自主学习。

3 线性表及其应用

栈和队列都是操作受限的线性表。栈的应用主要利用其具有“后进先出”的特点，广泛地应用于计算机的各个领域。计算机网络中的协议组通常放置在协议栈中；编译原理中的括号的匹配检查、表达式求值等问题是采用栈作为辅助数据结构；程序设计中的递归实现内部采取的是递归工作栈，动态网站中页面树状导航采用栈作为存储，论坛帖子的回复是递归形式，Struts2框架中的核心控制器调用业务控制器程序设计是一种采用栈的递归程序。

队列的应用广泛利用其具有“先进先出”的特点，网络中的路由器采用队列接收包和采用不同的隊列调度算法进行路由转发，操作系统中的作业和进程都是利用队列来存放。

同时在教学中指出，在传统的存储结构化数据的关系型数据库中主要是采用线性表进行存放。但在大数据领域，不同于传统的关系型数据库存储较小的数据量，所使用的是扩展意义上的线性表，主要用来存储非结构化和半结构化的松散数据。大数据技术体系架构中的HBase数据库区别于传统按行存储的方式，按列进行存储。医疗健康领域中可用来存储电子健康记录，优点在于可以实现并发读写操作。还可用于将临床数据流和脑电图数据存储在HBase数据库中用以监测病人状况。

4 哈希表

4.1在前沿领域的应用

在理解顺序和链式结构的特点基础上引入哈希表的原因。首先指出数据的存储主要采用顺序和链式结构，但这两者各有利弊。数组存储区间是连续的，占用内存严重，故空间复杂的很大。数组的优点是寻址容易，而插入和删除困难。而链式存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大。链表的特点是：寻址困难，插入和删除容易。由此引入哈希表（散列表）的目的是通过函数实现从关键码到存储位置的映射。这使得在进行查找操作时，其检索的效率不依赖于给定值与关键码的比较次数，而是将节点的关键码与节点的存储位置建立一种对应关系，只需通过节点的关键码便可定位该节点。同时指出它不仅是一种高效的存储结构，而且也是一种常见的查找方法，它能以常数平均时间执行增删改查四种常见基本操作。因此，它是一种面向查找的存储结构，在精确匹配查询方面，它有着广泛的应用，它的缺点是不支持范围查找。综合国内外研究表明凡是需要高效的存储和查找时都可以采用哈希表。

哈希转换是将n位数转换为m位数，通过哈希转换可以将一个索引器空间转换为哈希表，进而实现用哈希函数压缩序数索引；在信息安全方面，路由器上利用哈希表记录IP报文头部信息，重构攻击路径，达到追踪攻击主机地址的目的；在信息加密方面，利用哈希函数的非单射构造不可逆的加密算法的特点，实现信息的安全传输；在数据库中的数据查找方面，由于哈希表在记录查找时不发生哈希冲突的情况下O（1）级时间复杂度内便能得到查询记录，所以在需要对大规模文件进行查找时具有相当高的效率；在传统的网络体系架构中采用集中式的方式，其缺点在于中心点的瓶颈和网络规模小，因此产生可以适应网络规模的分布式对等计算系统。在这些系统中，通常是文件名经过哈希计算生成系统的标识进行排列。系统中保存相关联标识和对应文件的信息。当分布式哈希表需要对标识进行查询时，通过哈希函数的运算便会返回结点对应的信息。

哈希函数是构建哈希表的关键，在目前的前沿邻域尤其是海量数据环境下对哈希表和哈希函数应用的不同特点进行改进和优化。

由于哈希算法具有高计算效率与维度不敏感的优势，其已经引起了众多学者和专家的研究兴趣。通过哈希方法将不同数据流的相同候选模式发送至同一个计算单元[1]；改进的哈希算法——一致性哈希，设计了基于一致性哈希的分布式内存缓存，支持高效的基于非主键的查询[2]。依据覆盖网络的思想，借助分布式哈希表技术为数据中心构建一个纯分布式架构成为一种新型解决方案，更加适用于海量资源的检索和管理需求[3]，利用哈希函数具有相似性保持的特点，通过汉明排序或者哈希表来进行检索[4]。将分布式哈希表和CHORD环结构应用于分布式文件系统数据的存储和查询中，将存储节点与数据都进行散列，并根据哈希值进行映射存储，通过对保存的元数据信息进行二分查找来定位所需数据的存储位置[5]。

4.2 在hadoop大数据技术体系中的应用

NoSQL数据库、键值数据库使用哈希表，表中有一个特定的Key和一个指针指向特定的Value。

列组数据库，数据库由多个行构成，每行数据包含多个列族，不同的行可以具有不用数量的列组，属于同一列族的数据会被存放在一起，每行数据通过行键进行定位，与这个行键对应的是一个列族，列族数据库也被视为一个键值数据库[6]。

在HBase中使用哈希表，用于在列存储时将行关键字和位置主机之间的对应关系。有人采用HBase基础架构设计网上心脏疾病数据分析系统。

MapReduce包含运行于大规模集群上的两个函数Map和Reduce构成，这两个函数及其核心思想都源自函数式编程语言，构造的实质是哈希表。基于MapReduce技术使得分析医疗数据可以在合理的时间内完成，并可用于分析电子病历数据预测疾病，提高临床医疗质量，还可以实现病人的个性化药物治疗。

5 树

5.1 二叉树的应用

二叉树的定义、性质和遍历操作是学生要掌握的重点，为了引导学生进一步学习和研究，在课堂扩展环节以数据挖掘中常用的决策树为例。首先说明分类算法是识别样本数据所属类别的一种方法，常用的决策树分类算法，因其输出结果易于理解和解释，广泛用于医疗诊断、金融分析、评估贷款申请的信用风险等领域。决策树是用二叉树表示处理逻辑的一种工具。可以直观、清晰地表达加工的逻辑要求。特别适合于判断因素比较少、逻辑组合关系不复杂的情况。决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。

接下来采用和二叉树类比的方法讲解决策树。在决策树中最上面的节点称为根节点，是整个决策树的开始。每个节点拥有的子节点的个数与决策树中所用的算法有关。如CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树，也就是我们学习的树的概念。每个分支或是一个新的决策节点，或是树的叶子。在沿着决策树从上到下遍历的过程中，在每个节点都会遇到一个问题，对每个节点上问题的不同回答导致不同的分支，最后会到达一个叶节点。这个过程就是利用决策树进行分类的过程，利用几个变量（每个变量对应一个问题）来判断所属的类别（最后每个叶子会对应一个类别）。

进而指出随着数据产生速度、内存容量和处理器速度等限制，常规的决策樹算法无法对大数据集进行处理，因此需要对决策树算法的实现进行针对性的改进，在课外阅读中参阅相关文献[7，8]。进而激发学生自主学习和创新的动力。

5.2 B-树的变形及其应用

作为B-树的变形B+树，不同于B-树其一是在所有的非终端结点中仅含有其子树根结点中最大（或最小）关键字，二是所有的叶子结点中包含了全部关键字的信息 （而B-树的叶子节点并没有包括全部需要查找的信息），使其具有磁盘读写代价更低及查询效率更加稳定的特点，因此广泛的作为常用数据库（尤其是传统的关系型数据库）的索引结构之一。

索引是对数据库表中一列或多列的值进行排序的一种存储结构，使用索引可快速访问数据库表中的特定信息。在关系数据库中，索引是一种与表有关的数据库结构，它可以使对应于表的SQL语句执行得更快。如果对信息搜索采用全表搜索，将所有记录和查询条件进行一一对比，会造成大量磁盘I/O操作，消耗数据库系统大量时间；可行的方法就是在表中建立索引，然后在索引中找到符合查询条件的索引值，快速找到表中对应的记录。另外由于在B+树中拥有大量分支，在以块为单位的存储系统（比如文件系统中），也选用B+树作为索引。

同时指出对于非结构化数据[9]及非关系型数据库（NoSQL）[10]的特点需要对现有的索引技术进行改进和优化，比如采用T树、红黑树和LSM树，适应数据的特点和应用场合，提高检索效率，在课外阅读中参阅相关文献[9，10]。

XML 文档中的元素形成了一棵文档树。这棵树从根部开始，并扩展到树的最底端。XML因其具有自描述性和可扩展性，已经成为网络中一种主要数据组织形式，得到了广泛的应用。单一XML文档数据量变得越来越大，而XML文档具有半结构化的特性，使得采取结构化的关系型数据库不适用于XML文档的查询处理，扩展阅读参考文献[11]。

6 图的应用

图是包含顶点集合和边的集合，图主要掌握两种搜索算法及其应用。在前沿领域的研究中主要有以下几个方面。

图模型能表达丰富语义，利用图模型能很好地表达传染病的传播过程[12]和脑网络中的链路预测[13]。社交网络分析是由图论、数学以及社会学中的社交网络理论发展而来，广告投放、推荐引擎、兴趣图谱、内容聚合、推荐等都是复杂网络关系在社交网络中的展现。

在图的搜索算法方面，社区发现算法中的一种就是根据图论相关知识，将用户直接抽象为图中的节点，用户之间的关系抽象为图中的边，从而直接对网络拓扑进行社区发现[14]。图搜索算法对数据网络进行查询、聚类、匹配等操作，从而将数据网络根据数据关联关系划分成连通子图；深度学习算法则对数据连通子图中纷繁复杂的数据进行特征抽取和分类，从而提取用户需要的关键信息[15]。

图数据是一种重要而普遍的大数据，在生物信息学、社会网络、化学信息学等领域都有众多应用。由于传统单机运行的图的发现算法不能够满足计算复杂度、存储容量等方面的要求，需要在分布式平台上实现发现算法[14]。对大数据处理的速度是解决问题的关键，因此图搜索和深度学习的速度优化成为前沿领域的研究热点和难点。基于社交网络的数据分析，由于在分析对象、分析形式及分析方法上异于传统的分析方法，需要对数学模型进行加工、优化[16]。

7总结

数据结构课程中的数据、线性表、哈希表、树、图是常用的数据类型。在目前的前沿及大数据技术等场合应用非常广泛。在讲授知识点时，给出后续课程应用的场景，激发了学生学习的积极性，也增强了学生自主学习的能力。后续可在课程设计时，给出基于大数据的应用案例的综合实验，加强学生综合实践和创新能力的培养。

参考文献：

[1] 于自强. 海量流数据挖掘相关问题研究[D]. 山东：山东大学， 2015.

[2] 葛微，罗圣美，周文辉，等. HiBase：一种基于分层式索引的高效HBase查询技术与系统[J]. 计算机学报， 2015，39（1）：144-145.

[3] 杨迪. 基于内容的分布式图像检索[D]. 北京：北京邮电大学，2015.

[4] 金仲明. 基于哈希算法的海量多媒体数据检索研究 [D]. 杭州：浙江大学，2015.

[5] 杨萌萌. 基于HDFS的结构化数据存储和查询方法研究 [D]. 济南：山东大学，2014.

[6] 林子雨.大数据技术原理与应用[M].北京：人民邮电出版社，2015：96-97.

[7] 李玲俐. 數据挖掘中分类算法综述[J]. 重庆师范大学学报，2011，28（4）：44-47.

[8] 张棪，曹健.面向大数据分析的决策树算法[J]. 计算机科学，2016，43（6）：374-383.

[9] 时亚南，张太红，陈燕红，等.大规模非结构化数据的索引技术研究[J]. 计算机技术与发展，2014，24（12）：109-113.

[10] 付佳. 基于LSM树的NoSQL数据库索引研究[D]. 北京：北京理工大学， 2016.

[11] 魏博文. 基于MapReduce的XML编码查询算法研究与实现 [D]. 武汉：武汉纺织大学， 2016.

[12] 陈坤. 基于图模型的传染病传播模拟算法研究 [D]. 南京：东南大学， 2015.

[13] 田甜. 基于层次随机图模型的复杂脑网络链路预测研究 [D]. 太原：太原理工大学， 2015.

[14] 王羽. 基于MapReduce的社区发现算法的设计与实现 [D]. 南京：南京理工大学， 2015.

[15]王强. 面向大数据处理的图搜索与深度学习算法并行优化技术研究 [D]. 长沙：国防科技大学， 2013.

[16] 周峰. 基于大数据的社交网络数据挖掘[D]. 苏州：苏州大学， 2015.