数据结构程序库建设

代文征 杨勇 蒋文娟

摘要：针对数据结构综合程序库建设的内容匮乏问题，分析数据结构课程的特点，提出基于经典的数据结构形式以及采用两种基本的存储方式实现相关基础算法，实现扩展的综合项目程序，并通过实践结果验证构建综合程序库的教学效果。

关键词：数据结构；程序库；实践

背景

随着网络和信息技术的不断普及，人们的生活及生产活动产生的数据正在呈指数级增长。对海量数据进行处理及应用，是衡量现代化国家信息技术能力的一个重要标准，是一个国家信息技术发展程度的展板。因此，让学生认识数据的重要性、树立数据处理的计算思维是很重要的。数据结构是高校计算机、信息类专业的重要专业基础必修课，是培养学生计算思维的基础课。数据结构有助于程序员更有效地组织数据、设计高效的算法、完成高质量的程序，以满足错综复杂的实际需要。

数据结构课程涵盖了各种基本数据结构，其目的是使学生掌握并熟练应用各种基本数据结构及复杂数据结构来解决实际的数据处理问题。在实际教学中，由于没有较好的案例，学生无法将基础算法规律化，更无法将其应用到实际问题上。

2数据结构内容与特点

数据结构课程主要介绍基础数据结构的逻辑结构、算法及算法在存储结构体上的实现，并扩展了基本数据结构。学生要重点掌握基本数据结构的逻辑结构、存储方式及算法实现。数据结构课程的基本内容比较多，需要学生深刻理解并掌握。在众多的教学内容中存在着某种可遵循的规律，也就是“算法公式化”。学生需要不断地阅读并动手编写算法程序，才能从中找到这些规律。学生切身体会并掌握基本规律后，就能够轻松简单地进行相关数据结构算法程序的编写及应用。因此，课程教学内容以基础数据结构为切入点，讲解如何分析逻辑结构和基本算法，并在两种基本的存储方式下进行相关算法程序的编写。数据结构课程的主要特点如下：

（1）数据结构知识点多。针对线性结构的基础数据结构形式包括线性表、栈、队列、串等，非线性结构的包括树、二叉树、图（有向图，无向图）等。

（2）算法实现思想多。针对不同的数据结构形式有两种基本的存储方式：顺序存储及链式存储，而每种数据结构的常见操作（如插入、删除、查找、排序、修改等）算法的实现又与存储结构有关。

（3）知识关联性多。数据结构的学习需要线性代数、离散数学、概率统计等数学知识，还需要具有相关的程序语言基础。

（4）实践性强。数据结构需要学生动手使用程序语言实现相关的抽象算法，来验证算法的正确性及可行性，即最终的目的不是掌握算法，而是使用程序语言具体实现算法。

3构建程序库

简单的课程讲解和实验实践并不能让学生真正了解和掌握该课程所要求的知识。因此，需要建立一个基础程序及应用程序库，帮助学生更好地掌握数据结构的算法及具体程序实现，为学生进行创新学习打下一定的算法及实现基础。数据结构基础程序及应用程序库包含以下几方面。

（1）数据结构基础算法及程序：典型的数据结构基本操作算法及相关存储体上的具体实现程序库。

（2）数据结构应用程序库。典型的数据结构在大中型项目中的具体使用及相关操作算法实现，例如购票系统、多通道病人就医系统、旅游引导系统等，让学生了解这些系统的具体实现，帮助学生树立知识应用的思想，增强学生的学习兴趣。

（3）在线互动平台和资源库。构建针对各项目的在线资源和答疑区，锻炼学生的组织能力、沟通能力和协作能力。

（4）课程内容库。针对数据结构课程的各个数据结构形式，建设相应的课程内容，方便学生自主学习。

（5）数据结构文档库。让学生使用文档模板记录开发过程中的各个元素，规范学生的文档写作。

4程序库更新、维护及代码复用

构建的程序库随着算法研究的发展，可以根据需要在服务端进行相关案例及算法的更新和维护。程序库的管理操作是由程序库管理平台来实现的，用户只有使用权，但用户可以反馈自己在使用中发现的问题及对程序库的意见，程序库管理系统收集用户的反馈信息进行针对性的维护。

构建程序库系统前，首先对系统进行用例模型、领域知识模型的分析，然后采用正向工程，生成系统需要设计的相关对象，从而保证功能代码的复用，方便后期进行系统维护。

5程序库实施与使用

课程共安排64课时，包括52课时的理论教学和12课时的实验教学，基本保证了知识点的传授和实际项目的锻炼。另外，在52课时的理论教学课程中，有4课时的讨论时间。基础理论授课时，将基础程序库中的部分算法进行现场的编程实现，如果学生想在课后进行强化的自学，可以到程序库中进行检索。在构建程序库时，要求函数名能够体现程序功能，学生在课后自主学习进行程序库检索时，需要提供基本的功能名，系统进行粗糙匹配、相似度评价，在半监督的方式下由学生进行精确定位算法函数。

为帮助学生学习，我们已经建立了校内在线学习系统，将主讲教师的讲课录像及相关课程库发布到移动互联网中。此外，还为学生开放了相关实验室，帮助学生研究一些开放性问题，激发学生利用移动互联网寻求问题的答案，培养学生解决问题、撰写文档的能力。

6结语

目前，数据结构算法及案例库研究和构建非常匮乏。由于学生的兴趣点不同，案例库应提供不同关注点的项目案例，使学生有更多的选择，在达到同样的教学目的的同时，能够满足学生不同的兴趣需要。因此，构建一个完整的自成体系的综合项目案例库是很有必要的。将该程序库应用到学校计算机信息类专业的数据结构教学中后，经过4个学期的效果对比，教学效果较好，相关成果获得了河南省教育厅教学成果二等奖。