数据结构课程中的综合性实验案例设计

康长青　朱丽娟　胡春阳　吴中博　王敏

摘  要： 综合性实验案例是提升实践教学质量的关键环节。针对现有的数据结构算法时空分析实验安排缺失或综合性不强的现状，提出融合知识、能力、素质的综合性实验设计模式。通过课前资料查询，课上对比分析和课后优化拓展三个阶段，介绍了综合性实验案例的设计框架和能力素质目标。详细介绍了结构体和函数、空间复杂度、时间复杂度和系统优化四个功能模块的阶段实验目标、分级递进内容和教学策略。给出了实验的考核方案和教学效果分析。该教学模式有助于达成一流本科课程目标，可供同行借鉴和参考。

关键词： 综合性实验; 数据结构; 设计框架; 对比分析; 教学策略

中图分类号：G642          文献标识码：A     文章编号：1006-8228（2022）04-83-03

Comprehensive experimental case design in the course of data structure

Kang Changqing Zhu Lijuan Hu Chunyang Wu Zhongbo Wang Min

（1. School of Computer Engineering， Hubei University of Arts and Science， Xiangyang， Hubei 441053， China;

2. School of Physics and Electronic Engineering， Hubei University of Arts and Science）

Abstract： Comprehensive experimental cases have an important impact on improving teaching quality. Taking algorithm time complexity and space complexity of data structure as examples，the existing algorithms experiments have the disadvantages of lack of arrangement or lack of comprehensiveness. A comprehensive experimental design model that integrates knowledge， ability and quality was proposed to solve the above problems. Firstly， the design framework and goals of comprehensive experimental cases are introduced through three stages of pre-class information search， comparative analysis in class， and optimization and expansion after class. Then the stage experiment objectives， graded progressive content and teaching strategies of the four functional modules of structure and function， space complexity， time complexity and system optimization were presented in detail. Finally， the evaluation method of the experiment and the analysis of the teaching effect were given. The proposed model is beneficial to achieving the goals of first-class undergraduate courses and has some reference significance and promotion value.

Key words： comprehensive experiment; data structure; design framework; comparative analysis; teaching strategies

0 引言

教育部《关于一流本科课程建设的实施意见》中要求确立学生中心、产出导向、持续改进的理念，提升课程的高阶性，突出课程的创新性，增加课程的挑战度[1]。在此背景下，地方应用型本科院校如何进行专业核心课程的改革和建设[2]，对人才培养质量的提高起着举足轻重的作用。

數据结构作为计算机类专业课程体系中的核心课程，理应率先进行高阶性、创新性和挑战性改革，努力创建省级一流本科课程。

掌握算法的时间分析和空间分析的技术是数据结构课程的教学目标之一[3，4]，经常采用传统的课堂讲授来达成目标，存在学生印象不深，方法未学会，短时间不能掌握等问题，而现有的算法时空分析实验要么安排缺失，要么综合性不强[5]，因此论文提出采用综合性实验案例设计来达成课程目标，并逐步培养学生解决复杂工程问题的综合能力和高级思维。

1 融合知识、能力、素质的综合实验课设计思路

算法的时空分析实验是数据结构课程的第一个实验，考虑以提升学生综合能力和素质为重点目标，重新设计算法的时空分析实验内容如表1所示。

从表1可以看出，实验分为五个功能模块，分别为：结构体和函数复习模块，空间复杂度模块，时间复杂度模块，系统优化模块、实验总结和分析模块。

结构体和函数复习模块主要考虑学生程序设计基础薄弱的现状，设计一些程序填空题和编程兴趣题，用两周时间，在课前完成，培养学生查阅文献，沟通交流的意识，让学生反思自己的知识薄弱点，主动查缺补漏。空间复杂度模块主要任务是同一问题的不同函数设计，培养学生程序设计和软件测试技能，学会在判断和权衡的基础上深度分析，树立空间资源管理和积极学习的意识。 时间复杂度模块要求对数学问题进行快慢算法的设计，培养学生算法设计和测试技巧，树立探究和验证，克服障碍，勇于探究的职业技能和态度。系统优化模块通过让学生查阅阅读实用的系统优化资料，培养学生整体思维，分析确定系统优化的优先级和焦点，激发求知欲和终生学习的意识，为自己进行职业规划，明确自己职业的任务和责任。实验总结分析模块主要对实验进行总结和分析，内容包括解决问题的新思路，自己实验工作的优势和不足，在综合能力提升方面的进步等等，锻炼学生的图标和写作交流能力，为未来职业工作汇报和团队交流，打下基础。

2 综合性实验具体案例设计和实践

依据表1的实验设计思路，开展综合性实验具体案例设计，因此我们精心设计了五个功能模塊（结构体和函数复习模块，空间复杂度模块，时间复杂度模块，系统优化模块和实验总结和分析模块）的实验子目标、实验内容和教学策略等。

2.1 结构体和函数复习模块案例设计

实验目标：①能够学会使用文献搜索技巧查询资料;②学会库函数的调用，掌握计算代码段运行时间的基本步骤;③能够掌握常见的库函数的调用错误及调试方法。

实验内容：①在C语言库文件time.h中有哪些不同的结构体和操作日期和时间的函数，这些结构体的详细成员有哪些，代表的含义是什么？有哪些操作日期和时间的函数以及函数的作用是什么？②以结构体time_t，和对应的time（）函数为例，给出一段成功调用time（）的程序代码并截图给出效果图;③以结构体timeb，或clock_t为例，给出计算代码段运行时间的程序代码和运行结果;④程序调试中有哪些常见的调用错误。⑤分析time_t， timeb， timeval， clock_t这四个结构体调用时间精度的差别和适用范围。

教学策略：以学生线下自学为主，通过小组交流汇报，肯定学生的过程努力和结果。教师讲解关键字搜索和中英文资料搜索的技巧。

2.2 空间复杂度测试模块案例设计

实验目标：①了解软件测试中的静态测试，动态测试和单元测试;②理解空间复杂度的概念和理论分析方法;③培养合理利用空间资源的意识，判断和权衡，主动问题分析。

实验内容：①用循环的编程思想依次输出从N个有规律整数的函数设计（程序1）;②编写一个递归的函数（程序2），实现依次输出N个有规律整数;③针对程序1和2，给出一组相同N的值来确定两个程序都能正常运行，其中一个非正常运行，利用空间复杂度的概念，分析两个程序的空间复杂度。

教学策略：教师讲解各种测试概念，强调测试的重要性，引导学生分析递归程序的复杂度，学生自主完成函数设计和软件测试。

2.3 时间复杂度测试模块案例设计

实验目标：①掌握利用递推算法求解问题;②理解时间复杂度的概念和理论分析方法;③学会调用时间函数，编写同一问题不同算法的运行时间的程序;④了解利用软件测试技术，分析验证不同算法的时间效率。

实验内容：①利用循环语句设计算法（算法1）进行多项式1+x+…+ x求和，并分析其时间复杂度;②利用递推算法（算法2）进行多项式1+x+…+x求和，并分析其时间复杂度;③利用timeb，及相关函数设计利用循环和非递推算法的计算时间的程序;④软件测试中计算时间都为零，原因是什么，如何设计输入相同的避免函数时间为零;⑤分析表2中X和N的值是否相同，两个程序输入参数不一样，能够比较算法的计算时间？两个算法的计算时间是否和理论复杂度的分析结果一致，为什么？

教学策略：学生自主完成算法设计和问题分析，辅助部分学生进行递推算法的计算程序设计，必要时提供参考代码，引导学生克服困难和障碍，学会分析实验结果，验证理论。

2.4 系统优化模块案例设计

实验目标：①培养学生整体思维，系统思维和把握热点技术趋势的思维;②学会采用探究式学习进行系统优化，了解算法级别，函数级别，循环级别，语句级别，指令级别优化串行代码，激发求知欲并养成终生学习的良好习惯。③逐步养成尽善尽美的工作态度，崇尚奋斗，勇于担当的家国情怀。

实验内容：①阅读谷歌公司的C++编码规范中的头文件规则和命名约定规则，改造自己编写的程序;②阅读文献[6]中的算法性能和程序性能的度量与分析，串行代码性能优化技术，谈谈你的认识和看法;③Linux环境下提供了纳秒级精度的计时函数clock_gettime，在Linux环境下使用GCC编译器能否解决资金算法计时为0的问题;④基于SSE/AVX的向量化编程方法，改造算法，并进行时间效率的对比和分析。

教学策略：要求学生自主完成阅读任务，鼓励学生以小组形式完成探究性实验任务，把握系统优化的思维，强调代码规范对于求职面试和职业生涯的重要性。

2.5 实验总结分析模块案例设计

实验目标：①锻炼学生的图表和文字写作交流能力;②良好的软件工程文档和职业工作汇报材料;③学会利用口头和文字材料进行团队协作和沟通。

实验内容：①对实验结果进行分析，有没有解决求解程序运行时间到新方法和思路？②程序中遇见的错误有哪些，和自己如何解决的？未解决的问题有哪些？③在算法设计，资料查找，对比分析，软件测试，沟通交流等综合能力提升方面，收获和不足有哪些？是否有未来的学习计划和努力方向？

2.6 综合实验项目考核设计

针对本次算法的时空分析综合性实验，设计实验考评成绩构成和评价方式为：结构体和函数模块占15%，采用组内成员互评得分方式;空间复杂度模块占20%，以同学间现场检查互评进行;时间复杂度模块占40%，以教师检查提问形式评价;系统优化模块占15%，采用小组汇报整体得分形式;最终实验报告（含实验总结和分析模块）的占10%，需要学生提交到在线作业批改系统，教师通过内容查重后，單独评价。

经过以上综合式实验内容设计和实践后，学生普遍反映该实验项目衔接自然，挑战度较高，完成实验后增加了对算法的感性认识，增强了学习兴趣，特别在程序设计，文献查找，对比分析，系统思维，沟通讨论等综合能力提升度较大，取得了良好的教学成效。

3 结论

一流本科课程要求增加课程的高阶性、创新性和挑战度，要求培养学生解决复杂问题的综合能力和高级思维。本论文以数据结构课程中的算法时空分析内容为例，兼顾地方应用型本科高校的实际，探索了融合知识、能力、素质的综合性实验设计思路，取得了良好的教学效果，对其他相关课程的改革有一定的借鉴和参考意义。当然该综合性教学案例也存在耗费时间长，对基础不好的学生挑战性较高的不足，未来我们将在课程实践中不断听取学生的意见，并持续改进和优化案例，努力提升实践教学质量。

参考文献（References）：

[1] 教育部关于一流本科课程建设的实施意见[EB/OL].http：//www.moe.gov.cn/srcsite/A08/s7056/201910/t20191031_406269.html.

[2] 李敏之，王阳萍，李海军.新工科建设指引下的西部高校一流本科课程建设——以大学计算机基础课程为例[J].计算机教育，2020，311（11）：93-97

[3] 陈越，何钦铭.数据结构[M].北京：高等教育出版社，2012

[4] 陈越，何钦铭，冯雁.“数据结构”综合性课程设计教学探索与实践[J].计算机教育，2008，68（8）：56-57

[5] 张兆维，王建华，陶曦鸣.“数据结构”课程的课内实验教学探索与实践[J]. 计算机时代，2020，335（5）：96-99

[6] 刘文志.并行算法设计与性能优化[M].北京：机械工业出版社，2015