面向复杂工程问题的数据结构综合教学案例设计＊

康长青，朱丽娟，胡春阳，吴中博，谷 琼，宁 彬

(1.湖北文理学院计算机工程学院，湖北 襄阳 441053；2.湖北文理学院物理与电子工程学院)

0 引言

无论是工程教育认证还是两性一度的金课，都强调培养学生解决复杂工程问题的综合能力。计算机类专业教学体系的各环节都应主动将工程问题的复杂性融入教学内容，对解决复杂工程问题进行教学设计、组织实施和能力达成评价。数据结构与算法作为计算机类专业的骨干基础核心课程，更应该责无旁贷，持续进行课程改革，努力承担起逐步培养学生解决复杂工程问题的责任。

1 实验教学改革研究现状

实验教学具有直观性、综合性、探究性、启发性等多个优点，因而日益受到教学研究者的重视。文献[5]针对培养科学型、工程型、应用型人才定位的不同，提出了基础实验内容，课程设计实践要求，教学重难点和相应的教学方案。文献[6]详细分析了传统型、平台型和复合型实验教学模式的优缺点，提出基于SPOC 的复合型实验教学模型。文献[7]从教材建设、教学平台的拓展、教学方法的提升、考核机制的改革、实践方案的优化及教学团队的沉淀等六个方面，开展了数据结构课程的金课建设。文献[8]提出了多层次、立体化、以线上线下相结合的实验金课建设方案。然而，目前有关实验教学案例设计的研究较少，这是一个薄弱环节，如文献[10]设计了基于线性表和二叉树的砖块地图系统，飞机游戏等游戏开发案例，文献[11]提出了疫情期间面向应用场景的线上实践教学案例(软件系统中的自动补全功能,拼写纠错功能，STL 中的sort 函数源码设计)，文献[12]提出了“求二叉树宽度”复杂算法案例，文献[13]提出以“学生基本信息系统”的各章节分步式案例等。但是总的来说，这些案例还不能满足教学需求。①覆盖的知识点单一，综合性不高；②案例描述简单，设计过程不详细，借鉴性不强；③教学方式单一，学生积极性不高,无法承载培养学生解决复杂问题的综合能力和高级思维的教学需要。因此，面向实际的复杂工程问题来设计实验教学案例，已成当务之急。

2 基于德州扑克游戏的综合性实验案例设计

2.1 综合训练项目的培养目的

游戏有助于激发学生的学习动机，帮助学生学习各种知识，培养解决问题能力等高阶能力，培养正确的情感、态度和价值观，也能够促进自主学习的方式形成，并有助于构建富有吸引力的建构主义学习环境。为了培养学生能够灵活地、综合地运用所学到的知识来解决实际的复杂工程问题的能力，我们精心设计了“德州扑克游戏系统的设计和实现”综合实验项目，该项目作为数据结构与算法的必做实验，采用2-3 人兴趣小组，分步骤分阶段完成相应的综合训练任务。该项目将培养学生如下几个方面的能力。

⑴ 综合运用所学到的理论知识独立完成一个游戏系统的设计和实现项目，系统地进行需求分析、功能和流程设计、数据结构与算法设计、程序编码与测试、文档总结的训练。

⑵学会并掌握文献搜索技能，即培养获取专业文献的能力，理解和描述问题的能力，能够较准确的编写系统方案和详细设计有关的技术说明书。

⑶具备一定的项目风险意识，能够制定和管理开发计划，具备一定的项目管理能力。

⑷能够自主学习、协作学习、和探究性学习，具有独立分析和解决实际问题的能力。

⑸能主动与同学共享解决方案，讨论算法的优缺点，胜任团队成员的角色与责任。

⑹能够就项目中疑问和难点，和团队成员，老师进行有效沟通和交流。

⑺用文字、图表等表达自己的设计思路、测试结果及心得体会，能撰写质量较高的软件工程项目报告。

2.2 综合训练项目的具体内容

为了培养学生具有熟悉软件工程开发，了解一定软件测试和软件管理，会理解和应用常用的数据结构和算法，我们设计了“德州扑克游戏系统设计和实现”综合训练项目，如图1所示。

图1 综合项目的工程设计流程图

需求分析阶段，通过设计引导性问题要求学生完成①用文字或图表介绍德州扑克牌型的牌型定义和打牌规则；②理解发牌，转牌，比牌等专业术语，利用程序流程图模拟整个游戏工作流程；③从国家政策、需求风险、市场风险、成本风险等角度分析和讨论项目的风险因素。这个阶段主要培养学生使用文献搜索技巧查询所需资料，具备理解和描述问题的能力，用文字和图表成功描述项目的能力。

方案设计阶段，需要在完成需求分析后进行总体设计。任务包括：明确研究的对象是什么、如何定义和表示、需要完成哪些功能、计划使用何种界面、绘制功能图、构思软件的操作流程等。这个阶段培养学生具备一定的项目需求分析和总体设计能力，能够收集、辨别并组织相关资讯的能力，能够画出软件项目开发进度的关键路径图，能够估算整个项目的开发成本的能力。

系统详细设计阶段，引导学生将一个较大的功能分解成多个函数来实现。设计内容包括数据类型的规划和设计、函数功能和函数首部的设计、函数间调用关系的设计、主要算法的设计与分析。比如发牌程序是游戏程序的关键步骤，将牌抽象为一个长度52位数组，常见的发牌思路有①每次随机取两张牌交换，循环K次；②随机取一张，从数组中删除后再随机取一张再删除；③取52 个数全排列中的任意一个；④经典Knuth-shuffle算法等。鼓励学生发散思维，头脑风暴，相互讨论，分析算法的时间复杂度和空间复杂度，选取合适的发牌算法。这一阶段培养学生具备在掌握数据结构专业知识的基础上，能够针对具体问题设计或选择合适的数据结构和算法，能够自主学习、协作学习和探究性学习。

程序编码阶段，我们设计了一系列的核心编程任务，内容包括①给一人发五张牌，运行10万次，给出牌型的概率；②给两人各发五张牌，给出所属牌型和输赢情况；③两人打牌，公共牌分别为三张，四张，五张时的型和输赢情况。这部分内容是设计牌型判断，牌型比较，排列组合函数编程等编程难点，团队成员间讨论如何应用数据结构排序算法，各种同类牌型比较时的编程思路，排列组合函数的递归和非递归算法，能够调用系统排序函数和排列组合函数等等。这个阶段主要培养学生求真务实，脚踏实地学习态度，培养学生应用专业知识进行程序设计和程序调试，能够独立分析和解决实际问题的能力，胜任团队成员的角色与责任。

软件测试阶段，主要任务是单元测试和系统集成调试，培养学生掌握一定的单元测试和集成调试的基本方法，持续改进算法或函数设计，依靠团队不断学习和经验积累，养成追求正确，科学严谨，尽善尽美的个人品格。

系统评价与改进阶段，主要任务是用文字、图表等表达个人设计的思路，分析系统的优缺点，以研究式的学习进行系统优化和完善。我们设计的开放式优化任务包括①针对牌型计算模块的优化算法，优化的思路有牌整数编码比较法，正则表达式比较法，哈希查表比较法等，以及如何实现；②考虑客户端服务器模式，如何对发的牌定义，减少传递的数据量，节省服务器资源？如何对牌进行加密解密，来防止棋牌作弊器；③基于牌力值，潜力值，有效牌力值等牌力评估指标，查询资料了解最近的研究现状，学习Cactus Kev,Paul Senzee,TPT 算法，并进行算法实现和效率评估等。这个阶段主要培养学生学会采用探究式学习策略进行系统优化的思维，从系统角度去认识整个项目，积累项目的合作协调，开发测试经验，使用各种工具性地解决复杂工程中遇到的各种问题。。

2.3 综合训练项目的复杂工程问题特征分析

“德州扑克游戏系统设计和实现”综合训练项目融合了数据结构与算法综合知识（如线性表，排序，查找和图等四个教学章节的理论教学内容结构，各种算法的分析和比较），软件工程的开发流程（包括需求分析，方案设计,系统详细设计，程序编码，软件测试和系统评价等教学内容），软件项目管理和成本效率分析（包括开发进度的关键路径图，项目开发成本估计）等，可以看作是一个课程群的综合实践项目，因此具有较高的挑战性和综合性。完成整个项目需要学生运用深入的工程原理分析，建立合适的牌型和牌型比较模型，考虑项目风险因素和时间管理等非技术因素，综合所学的数据结构和软件工程基础知识，独立设计和团队分工合作才能顺利完成，达到项目的教学目标。项目锻炼了学生系统分析与理解、算法设计和运用、文献查询和系统理解、性能测试与对比分析、文档撰写和团队沟通等多方面综合能力和高阶思维，为培养学生在课程中逐步培养解决复杂工程问题提供了有力支撑。

3 教学效果

经过面向复杂工程问题的综合性实验案例改革后，选取经过综合训练改革前后学生的项目吸引力，能力成长满意度，实验课平均成绩等三方面指标进行教学效果的评价。其中，项目吸引力和能力成长满意度指标通过课程结束后的调查问卷得到，单个学生的实验课成绩由任课老师评分得到。我们得到的改革前后的教学效果对比如表1所示。

表1 效果对比

从表1 数据可以看出，改革前的综合项目吸引力平均得分为66 分，能力成长满意度为64 分，实验课平均成绩为73.5 分；而改革后综合项目吸引力平均得分为84 分，能力成长满意度为82 分，实验课平均成绩为81.7 分。仔细分析其中的原因，可以得知，改革前，学生觉得综合性项目吸引力一般，对自己能力提升也就那样，导致实验平均成绩不高。改革后，游戏案例来源于生活，应用广泛，学生有较高的兴趣，加上项目难度适中，能够锻炼其综合能力，因此实验平均成绩有了较大的提升，取得了较好的教学效果。

4 结束语

综合教学案例设计是培养学生解决复杂工程问题的关键环节。设计一个符合复杂工程问题特征的教学案例，既要考虑学生学情，又要考虑综合性和挑战度，是一件不容易的事情。论文以德州扑克游戏系统设计为例，探讨了在课程实验中进行综合教学案例设计的思路和具体实践，取得了较好的教学效果。在未来的教学实践中，作者将不断收集和分类学生在该项目学习中的问题和建议，持续改进，不断完善。