数据结构课程实践的螺旋式教学

张玉华

（苏州大学 计算机科学与技术学院，江苏 苏州 215006）

1 存在问题及对策

数据结构课程是计算机相关专业的核心基础课，是培养学生利用高级语言存储表示外部数据，并对这些数据进行操作和运算的学科，是提升学生的逻辑思维能力、算法设计能力和编程能力，引领学生真正进入计算机技术领域的桥梁课程，是一门非常重要且实践性极强的课程。

多年来，数据结构的实现语言随着技术的发展不断变化发展。从Pascal语言，到C、C++、Java语言，甚至Python语言，数据结构的应用实践始终是一个令学生烦恼、教师失望的环节，从总体来看，实践教学的效果一直不够理想。除了学生高级语言的编程基础薄弱等原因之外[1]，最重要的原因还有3个：①数据结构的实验题目或陈旧缺乏新意，或粗制滥造缺乏实用性[2]，学生对数据结构的实验题目没有兴趣；②整个实践过程处于无序、随意、缺乏指导的状态，教师的大部分工作是辅导个别学生进行程序调试，没有起到整体的引领作用；③缺乏及时、有效、公正的学习反馈和评价机制。

针对这样的现状，在较为充足的实践课时保证下，可以将基本数据结构和算法的实现、选择和灵活运用以及提高编程能力作为整体教学目标，将实践课程设计为验证与设计并重，理论与实践、教学与实践相结合，由教师、学生和助教共同参与，采用七步螺旋式教学的系统化工程。

2 七步螺旋式教学及实践流程

七步螺旋式教学将每个数据结构实验的完成分成7个步骤，分别是选题、题目分解、学生初步设计阶段、中期指导和设计阶段、学生后期实现阶段、撰写实验报告阶段以及批改、反馈、分析、展示阶段，每个步骤都精心设计，7个步骤环环相扣，总体自下向上，即后续的步骤是前面步骤的加强、反复和综合，但存在回溯再向上的反复过程。

2.1 题目挑选和设计

通过对现有数据结构实验教材大量的研究和学习，结合教师多年来对数据结构理论和实践教学的理解，可以进行题目挑选、改编或自主设计。

选题的原则一是系统性和完整性，即根据理论课程的知识体系和教学流程进行选题，保证对数据结构基本理论系统全面的验证、应用和实践，围绕数据结构的核心知识（栈、队列、线性表、二叉树、图等数据结构），递归的算法思想的运用，查找、排序的算法实现及性能测试进行题目的精选，完整覆盖数据结构的重要内容。

二是保证题目的新颖性、有趣性、实用性、综合性和可扩展性。

三是各实验的独立性和相关性，一个实验可以对多种数据结构或多个技能进行操作，一个数据结构、算法也可以在多个实验中反复出现。

比如用算24点游戏作为栈的综合应用设计题，不仅考查栈的实现和应用，还考查穷举、递归等算法思想，利用栈完成对输入的算24点表达式的括号是否配对的检查，对合法的表达式进行求值，题目新颖，具有应用意义，并且内容全面，由浅入深，同时考虑到学生对知识点掌握的不同程度，设立选做和必做部分。由于选题极具实用性和可扩展性，有些学有余力的学生还可将该题修改扩充后做成手机上的算24点APP，极大地提升学习兴趣和编程能力。

2.2 实验题目分解

如果直接把题目抛给学生，那么很多学生可能就会无所适从，因此需要教师围绕该实践课题的教学要求，将题目进行由浅入深、由易到难的层层分解，即使是基础较弱的学生，也可以从完成第一个小目标入手，慢慢获得信心，达到分层次教学的目的。

2.3 学生初步设计阶段

教师将题目分解后通过教学网站发布，学生进入初步设计阶段。这个阶段通常是完成验证性实验、基本输入输出等部分，要求学生分析初步设计阶段的要求及整个题目中的核心数据结构并加以定义和实现，要求学生必须细读题目，结合所学数据结构理论知识，运用C++语言给出实现方案。工作量控制在大多数学生可以在2个学时之内初步完成，教师和助教进行巡视和个别指导。

2.4 中期指导和设计阶段

教师根据学生初步设计阶段完成的情况，利用实践课堂1学时左右的时间对基本部分中出现的典型问题进行范例分析，对接下来要完成的任务进行分析，以图解、提问等方式，对后续部分的要点和难点进行提示。学生根据教师提示或自行进行实验的整体设计，对初步设计阶段完成的部分进行修改、添加和完善，这是承前启后的关键一步。

2.5 学生后期实现阶段

学生定下总体设计方案，进行程序编写和调试，在这个阶段仍然可能会修改之前不合理的设计；接受教师和助教的指导，通常通过2～4课时完成全部实验程序并提交。

2.6 撰写实验报告阶段

实验报告是所完成实验项目的设计报告和说明书，应该重内容、轻形式，要求学生描述实验的总体设计方案、关键数据结构和算法，将实现过程中遇到的问题及解决的方法如实记录，展示完成情况和实验结果，并对实验结果进行分析，总结心得体会。考虑到很多学生没有撰写实验报告的经验，教师可以给出第一个实验报告的参考样例，并引导学生用流程图、模块结构图等方式清晰汇报所做工作。

2.7 批改、反馈、分析、展示阶段

及时、有效、公正的学习反馈和评价机制是提升学生的学习兴趣，帮助学生巩固所学知识的有效途径。在实验程序和报告提交之后，教师和助教对所有学生的程序和报告加以批改，为使实验成绩更真实，每次实验都随机选择部分学生进行面批，根据实验态度、分析能力、编程能力、实验结果、源代码质量、总结能力等多个方面进行给分，通过教学平台给出每个学生的实验评分和评语。最后评比出10%左右的优秀作业进行展示，学生以此作为一种荣誉，能够形成较好的学习氛围。

3 七步螺旋式教学实践案例

以线性表的实现和应用、查找和排序算法的实现和运用作为学习目标，以技能大赛信息查询和评奖作为题目，展开数据结构课程实践螺旋式教学。

3.1 实验题目

某行业组织一次行业技能大赛，共设有10组选手参赛，每组的参赛选手少于10位。每位选手有一个6位选手编号，其中第3—4位是组别代码，如编号是“030205”表明该选手在第2组。现在比赛已经结束，选手的编号、姓名和最终成绩存储在mark.txt中。mark.txt每行存储一个选手的信息，3项信息之间以tab键作为分隔符。

3.2 题目分解

1）初步设计阶段要求。

（1）设计并实现选手类，存储选手信息。

（2）选择一种数据结构及其存储结构，存储所有选手的数据。

（3）将mark.txt文件的内容存储到（2）所选定的类对象中，并加以全部输出。注意输出格式尽量美观。

2）最终完成阶段要求。

（1）根据输入的编号查询某位选手的成绩。

（2）根据输入的组别查询该组所有选手的成绩，如输入2，则显示2组全部选手信息。

（3）评出个人奖项。分别取个人成绩最高的前10%、成绩其次的前15%和成绩再次的25%依次作为个人一等奖、二等奖和三等奖选手，总共获奖选手为参赛选手人数的50%，得奖人数按四舍五入计数。按成绩递减序依次输出各奖项获得选手的各项信息。

（4）评出团体奖。根据每组成绩最高的3位选手的总成绩评出团体奖前3名，输出前3名的组别和3人总成绩。

要求界面友好美观，功能完整正确，可实现查找、排序等算法，以完成相应功能，可自行设计和添加其他的类和辅助算法。

3.3 学生初步设计阶段

1）比赛选手Player类。

在这个案例中，程序的主要操作对象是各位比赛选手，各位选手需存储处理的信息即为他的编号、姓名和成绩，因此设计Player类，其数据成员包括num，name和score，另外配备构造方法、输出方法等。

2）线性表List类模板。

根据题意，题目要求将所有选手的信息进行统一存储，之后要进行选手查找、根据成绩进行排序评奖等操作，所涉及的其他操作也都可以在线性结构下很方便地完成，因此采用线性表作为逻辑结构也是最合理自然的。

世界范围内对能源互联网没有统一的名称和定义,在众多对能源互联网不同形态的描述中,两种具有代表性的观点是:“能源系统的类互联网化”和“互联网+智能电网+智慧能源”。前者借鉴互联网开放对等、即插即用的理念和体系架构,结构上难以区分能源网络和信息网络,运行模式上采用区域自治和骨干管控相结合的方式,其研究和实践还没有统一的目标和方向,现阶段有一些示范工程建设和实验室的研究。后者借助互联网收集信息,分析决策后指导能源网络的运行调度,信息网络可以认为是能源网络的支持决策网络,其本质与早些时候提出的智能电网类似,以德国、中国为代表。在现阶段的技术水平下,后者比前者更具可操作性。

假设用playerList对象来表示所有选手的线性表。

线性表的存储结构可以采用顺序存储或链式存储结构，假设本次实验采用顺序存储结构，即用连续的存储空间作为线性表元素的存储空间。可以将该类定义在list.h中，各方法的实现部分代码可以添加在该文件下方。

List类中定义的Error_code枚举类型用于返回各方法执行的结果状态代码，定义如下：

enum Error_code { success，underflow，overflow，not_present，range_error }；

3）文件内容读取到List对象中并加以输出。

（1）文件内容读取到playList中。

void readFile（string filename，List＜Player＞ &playerList） //将文件中的数据存入列表

3.4 教师中期指导阶段

1）教师分析学生初步设计阶段出现的问题。

（1）Player类的构造方法就可以完成3项信息的读取，有学生用3个方法分别设置3个变量，没有必要。

（2）List类为模板类时，定义和实现部分要放在一个文件中，有同学用list.h和list.cpp分别表示定义和实现部分时，注意在主程序要#include "list.cpp"。注意不能重复包含头文件。

（3）其他低级错误，如有学生在类定义结束时忘了加分号等。

2）进一步完成实验分析提示。

（1）根据编号进行查询。可在list类中添加一个新的方法：Error_code searchByNum（string &target，int &position）；即根据target字符串，到当前list中按选手的编号进行顺序查找。

（2）根据组别进行查询。由于需要根据组别选出所有该组选手的信息，需要得到一条新的链表以方便后续的输出，设为new_list，则可在list类中再添加一个方法：void getByGroup（List＜Player＞ &new_list，int &target，int &position）。

（3）个人奖项获取并输出。可以先将表进行逆序排序，然后根据题目给出的百分比依次获得获奖选手。排序算法可采用之前学过的insertionsort或其他在顺序表下有效的排序算法。注意将算法改写成递减排序的要求。另外，排序时按照成绩进行大小比较，因此在Player类中添加按照成绩比较大小的“＜”“＞”方法。

（4）团体奖获取并输出。可利用getByGroup方法按组别进行查询并生成各组子表，对每个子表按选手成绩进行递减排序，将每组的编号信息和前3名总成绩依次进行存储，假设存储在一个groupList中。可以定义Group类，存放各组的组号和该组前3名选手的总成绩。

（5）程序结构及函数间调用关系。关系图如图1所示。

3.5 学生后期完成阶段

学生根据教师的提示，可借鉴教师思路或自主完成接下来的任务。需主要完成的算法为查找算法、排序算法以及根据题目要求依次进行信息检索和评奖。

1）按编号查找算法。

图1 程序框架结构和函数间调用关系图

2）按组别查找算法。

3）排序算法。

4）主程序文件中调用List类的外部方法。

5）主程序。

3.6 撰写实践报告阶段

通过多个实践报告的练习，学生已经基本掌握了课程实践报告的撰写方法，不仅可以清晰地汇报所做工作，还对一些实验中具有共性的技术问题的解决方案有了相应的积累。

3.7 批改、反馈、分析和展示阶段

在本例题中，经过总共5个学时的代码编写和调试，63%的学生可以完成整个实验，19%的学生完成前面4个小题，12%的学生只完成前面3个小题，另有6%的学生完成2个或更少的实验。根据每个小题的得分点，对所有学生进行评分和反馈。

将完成较好的学生的实验程序进行演示，分析其合理和可以完善的地方，进一步总结编程思路，对程序结构作直观的演示，从而帮助更多的学生提高工程设计能力和编程能力。

4 结 语

通过将每个实验设计为围绕某种数据结构，综合运用已学的其他数据结构，选用或设计相关算法，熟练运用编程语言，实验目标的开放性螺旋式过程最终完成。一个学期的实践中，学生通过与教师的互动和充分的实践，在多个实验中对知识和技能进行螺旋式反复、交叉练习，能够在实际应用中正确选择数据结构、存储结构，分析并完成其基本算法的实现，基本达到数据结构课程学习和实践的目的，但由于教学任务紧，人力相对不足，具体实施的细节还需要更多的完善。