基于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