基于HowNet的数据结构综合实践课程改革

蒋玉茹，张仰森，陈若愚，刘城霞

摘要：文章设计了一个适合于数据结构综合实践课程的实践项目。该实践项目的特点是可以让学生综合运用线性结构、树形结构和图形结构三种数据结构，让学生体验到分析、设计、实践的全过程。

关键词：数据结构;HowNet;知网;综合实践

中图分类号：G642.0     文献标志码：A     文章编号：1674-9324（2020）01-0133-04

一、概述

数据结构是计算机程序设计的重要理论技术基础，是计算机学科的核心课程，而且是设计和实现编译系统、操作系统、数据库系统及其他系统软件和大型应用软件的重要基础。在教学中遇到的主要问题是学生普遍在逻辑层面能够理解和掌握数据结构，但是在面对具体问题的时候，却不知如何下手。这其中主要的问题是数据结构理论教学多数偏重算法思想形成过程的分析，重在算法思想的描述，在实验教学过程中，多为分散的、小型的验證性实验。

为了改变这种情况，我们在学生学习完面向对象程序设计（JAVA）课程和数据结构课程之后，安排了数据结构综合实践课程，该课程共24个学时，8小时授课，16小时实验。目的是通过一两个综合项目培养学生问题分析能力，利用适当的数据结构来表征问题中的数据，利用JAVA构建数据结构、操纵数据结构的能力。如何选择一个合适的综合项目实践题目是一个难度较大的问题。这个题目需要满足几项要求：（1）能够引起学生的学习兴趣。（2）能够综合运用多种数据结构。（3）学生在有限的时间内可以完成。

目前国内外出版的关于数据结构实践方面的教材多是注重某个单一数据结构或者算法的运用，这种实践的优点是可以针对具体问题予以深入的研究，但是这些题目多是解决通用的问题，比如车辆调度问题等。此类程序在网上或者书本上都能够找到解决方案乃至程序源代码。学生因为思考和实践上的惰性，或者因为面对困难的勇气不足，就会照搬照抄，也因为问题简明、直截，所以学生不需要在数据结构设计和选择上做过多的思考。

我们在课程改革中提出了选择项目的几项原则：（1）综合性。综合性定位在综合运用多种数据结构的能力。在有限的课程学时范围内，既要体现实践项目的综合性，又不能附加太多的非核心元素。（2）新颖性。与科研前沿结合，与社会需求结合，与学校特色结合。（3）重点在数据结构，弱化算法。（4）要与培养目标结合：动手能力，结合JAVA课程。（5）挑战性：网上找不到现成的代码。

数据结构课程组的多位教师从事自然语言处理相关的科研工作，因此产生了从科研中提取相关内容转化为优质教学内容的想法。在大数据和人工智能被提高到国家战略层面的今天，HowNet作为知识图谱的一个典型代表被广泛用于自然语言处理领域的研究中，比如词汇语义计算、信息检索、语义网等。

本文首先分析HowNet的结构，指出利用HowNet作为数据结构综合实践项目的意义，然后围绕HowNet设计课程的内容，最后对本课程改革的效果进行分析。

二、HowNet分析

知网（HowNet）是一个以汉语和英语的词语所代表的概念为描述对象，以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库。知网利用义原来定义概念的含义。义原是最基本的、不易于再分割的意义的最小单位。义原之间不是孤立的，是有关系的，具体可以利用多叉树结构表示。义原的个数是有限的，概念的个数是开放的，知网认为可以利用有限的义原定义所有概念的含义。由于每个概念的含义可以利用一个或者多个义原来定义，因此，概念和义原就形成了一个网状结构。

知网官网中提供了一个简单的知网知识库，其中包括概念词典glossary.dat和义原词典whole.dat两个重要文件。whole.txt文件为所有义原信息，每一行是一个义原，包括该义原的编号、义原名称、该义原的父义原的编号，如表1所示。表1中展示的义原数据可以利用图1所示的树形结构展示。

HowNet概念词典Glossary.txt中每一个概念用一行记录来表示，该记录中主要利用知识描述语言，使用义原对对应概念进行定义。比如：“北京”被定义为“place—地方，capital—国都，ProperName—专，（China|中国）”，其中“place|地方”为主义原。图2中展示了知网概念义原关系图的一个局部内容。在知网中，“安眠药”被定义为“medicine—药物，CauseToDo—使动，sleep—睡”，即其含义可以利用三个义原“medicin—药物”“CauseToDo—使动”和“sleep—睡”表示。由这三个义原定义的其他概念，比如“催眠药”“催眠”“催眠曲”“催眠术”和“药枕”等，也被显示在图2中。

综上所述，可以看到知网中的义原关系、概念关系需要用到树形结构和图形结构，而对于所有义原名称和概念名称的存储和管理则需要用到线性结构。因此，知网可以作为数据结构综合实践的项目之一。

三、基于知网的数据结构综合实践课程设计

1.本课程目标。本课程是学生在学完数据结构和高级程序设计语言课程之后，进行知识综合训练的一个实践环节。综合设计可以弥补课堂教学和实验教学中的不足，帮助学生充分理解和巩固所学的基本概念、原理和方法，使学生达到融会贯通、举一反三的目的，是学生进行知识综合训练的一个实践环节。

本课程的课程目标如下：（1）对数据结构课程中一些应用问题进行补充。（2）通过实践培养学生综合运用所学知识的能力，达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，提高学生的算法设计和算法分析能力，培养良好的程序设计技能，提高学生软件开发能力和利用调试技术对开发的软件进行调试的能力，训练用系统的观点进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。在实验中，要求学生使用某种程序设计语言，如JAVA语言，利用基本数据结构进行综合实例程序设计。

2.课程内容设计。本课程内容安排如表2所示。表2从数据结构、知网、JAVA三个维度描述了课程单元内容，给出了建议授课学时和实验学时。学生在给定的实验学时中并不能完成指定任务，基本能够掌握核心要素，课余时间至少还需要补充16个学时用于完成本课程的实践任务。为了提升学生的学习兴趣，本课程设置了树形结构和图形结构的可视化环节。树形结构的可视化利用了JFX中的TreeView组件，图形结构的可视化利用了D3JS的力学图（Force-Directed Graph）。

四、效果和需要注意的问题

在实施本课程改革之后，从学生报告总结中可以看出，学生普遍的感受是對数据结构有了更深刻的认识，包括理论和实践两个层面，学生的收获很大。有的学生在完成项目之后，开心地在社交媒体中展示其成果。大部分学生觉得本实践项目具备综合性和挑战性。通过本实践项目，学生获得了以下能力：（1）能够从问题中识别出对象并抽象出类的定义，包括义原类、概念类。（2）能够根据需求自定义数据结构，比如义原列表、概念列表、义原树、概念义原关系图。（3）能够利用现成组件，快速可视化开发，比如利用JFX和D3JS。

本实践项目实施中的主要问题是因为题目是从科研问题中抽取出来的，在网上找不到现成的可直接参考的代码，因此对于市属院校的一本学生而言，本题目具有一定的挑战性，因此教师需要帮助学生克服困难。（1）注重课堂教学中的引导，不仅引导学生学会分析和设计，还需要针对每个技术点给出一个小的示例程序。（2）在实验环节中需要通过检查实验的形式让学生尽快掌握关键技术，对仍掌握不好的地方给予详细指导。（3）注重答疑环节，对学生实施个别化指导，帮助学生克服困难，鼓励他们完成实验。

五、结语

本文设计了一个适合于数据结构综合实践课程的实践项目。该实践项目的特点是可以让学生综合运用线性结构、树形结构和图形结构三种数据结构，让学生体验到分析、设计、实践的全过程。希望今后能从科研中提取更多更好的题目用于数据结构实践课程。

参考文献：

[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2006.

[2]葛斌，李芳芳，郭丝路，汤大权.基于知网的词汇语义相似度计算方法研究[J].计算机应用研究，2010，27（09）：332-333.

[3]董振东，董强，郝长伶.知网的理论发现[J].中文信息学报，2007，（04）：3-9.

Reform of Comprehensive Practice Course of Data Structure Based on HowNet

JIANG Yu-ru，ZHANG Yang-sen，CHEN Ruo-yu，LIU Cheng-xia

（School of Computer，Beijing Information Science and Technology University，Beijing 100101，China）

Abstract：This paper designs a practical project suitable for the comprehensive practice course of data structure.The characteristic of this practice project is that it enables students to comprehensively use three data structures：linear structure，tree structure and graphic structure so that students can experience the whole process of analysis，design and practice.

Key words：data structure;HowNet;CNKI;comprehensive practice