数据结构课程设计教学中的案例巧用

摘

要：为改进数据结构课程设计教学效果，对教学中如何选取适当案例进行分析，以迷宫案例为例，说明选择的案例应该能够采用多种数据结构和多种算法来解决，便于在教学过程中从多个角度进行对比分析，有利于学生对更多课程知识点融会贯通，从而提高学生分析问题、解决问题的能力，完成课程设计教学的目标。关键词：数据结构；课程设计；案例；迷宫中图分类号：TP312

文献标识码：ASkillful

Use

of

Cases

in

the

Teaching

of

Data

Structure

Course

DesignSun

Yue

Jiang

Jing

Su

LiminSmart

City

College，Beijing

Union

University

Beijing

100101Abstract：In

order

to

improve

the

teaching

effect

of

data

structure

course

design，this

paper

analyzes

how

to

select

appropriate

cases

in

teaching.Taking

maze

cases

as

an

example，it

explains

that

the

selected

cases

should

be

able

to

be

solved

by

using

multiple

data

structures

and

algorithms，which

is

convenient

for

comparative

analysis

from

multiple

perspectives

in

the

teaching

process，and

is

conducive

to

students'

understanding

of

more

course

knowledge

points，so

as

to

improve

students'

ability

to

analyze

and

solve

problems，Complete

the

goal

of

curriculum

design

teaching.Keywords：Data

structure；Curriculum

design；Case；Maze數据结构课程是计算机相关专业的专业基础课程，主要描述非数值计算问题中的数据如何组织、存储和处理，讲解基本数据结构的应用并介绍典型的基本算法。数据结构课程设计虽然是一门独立的课程，但它是数据结构课程理论教学的延伸和补充，实现对理论知识的综合应用，课程的基本目标是帮助学生理论与实践相结合，巩固、加深和融合所学的专业课程知识，更重要的是能培养学生的独立思考能力、分析和解决问题的能力，锻炼学生的文献检索能力及合作能力［1］。传统的数据结构课程设计教学一般布置几个比较独立的题目，题目所采用的数据结构比较单一，算法单一，或者只要求学生实现其中一个［2］，这种方式不利于学生理解多种数据结构的特点，掌握如何选择正确的数据结构。选择合适的案例能够填补传统教学过程的不足，不仅可以帮助学生充分理解、巩固所学的基本概念、原理和方法，还能针对实际问题来选择不同的数据结构，设计相应的存储结构和算法，从而最终解决问题。下文以迷宫案例为例说明如何选择合适的案例并进行教学方式改革。1

如何选择设计适当的案例数据结构课程设计如果选用多个独立的小题目，所需要用到的知识点就是与课堂教学一一对应，比较简单直接，学生基本不需要自己去考虑各种可能的解决方案，研究最合适的方法，导致锻炼的层次和涉及面都比较窄，与实验教学区别不大。所以数据结构课程设计中选择的案例与数据结构课程教学过程中选择的案例相比，要强调知识的综合运用，锻炼学生对复杂问题进行分析与求解的能力，在选择案例内容时可以从以下两方面考虑。1.1

难度适中案例要有助于学生深刻理解数据结构模型，并引起学生的探究和思考，案例难易程度和学生水平相当，学生耐心阅读钻研就可以读懂会做，能够独立实现该案例，具有可行性。题目过大或过难，会让学生望而生畏，不知从何下手，产生消极抵触情绪；题目过小过易，则难以激发学生兴趣，使设计流于形式，实际效果与实验一样，不能达到教学目的。1.2

覆盖的知识点要广课程设计的目的是让学生更好地理解消化课堂理论知识，所以要求课程设计题目覆盖的知识点越广越好，尽可能避免单一，应该是对课程理论知识的综合应用，要求学生通过查找与分析有关参考资料，进行探究式的学习，给学生留出发挥想象力和创造力的空间。2

选择迷宫案例的原因迷宫问题是图形学、图论和数据结构等领域中广为人知的一个经典问题，无论是在日常生活中还是电脑游戏中，都有迷宫类游戏，其规则易于理解。解决迷宫问题的基本思想也比较简单，计算机解迷宫问题一般采用“穷举求解”法，即从入口出发，顺某一方向探索，若能走通，则继续探索；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止［3］。迷宫案例的广为人知和其特有的趣味性能够激发学生探索解决问题的积极性，另外，迷宫案例通俗易懂难度适中，能够利用多种数据结构和算法来解决，与理论教学过程中很多知识点密切相关，使其成为数据结构课程设计教学过程中一个理想的案例。2.1

采用多种数据结构迷宫问题的计算机表示通常采用线性表结构，用一个二维数组mg［M+2］［N+2］表示迷宫，如下图所示，M=8，N=8，状态为0时表示对应方块是通道，状态为1时表示对应方块是障碍物，为了实现算法方便，一般迷宫的外围加一条围墙。图中阴影部分为从入口mg［1］［1］到出口mg［8］［8］的一条路径。为了保证在任何位置上都能原路退回，在處理过程中常用栈或队列表示路径［3］。如果把迷宫中的每一个位置看作是一个点的话，可以把迷宫转换为一个个相连或分断的各个顶点之间的关系，使用无向图来表示。图都是由顶点和边构成的，把迷宫图中的每一个方块看成一个顶点，方块和方块之间的连通性看成顶点与顶点的边。因此，组织迷宫案例的数据可以采用线性表、栈、队列、图结构，每种结构都有相应的算法，是目前常用案例中涉及数据结构最多的案例之一。2.2

采用多种算法求解迷宫问题的方法有很多种，这些算法的基本思想是如何寻找从入口到出口的一条路径，这样的路径可能有多条，哪一条是最短路径也是迷宫问题的重点，所以迷宫问题相关的算法包括求出一条路径与求出最短路径的算法两大类。采用不同的数据结构，选择的算法也不尽相同，常用的数据结构及其相关算法主要包括以下几种。2.2.1

栈和队列结构相关算法解决迷宫问题常用的算法是用二维数组存储迷宫数据，用栈结构或队列结构表示路径，在使用栈结构解决该问题时是利用栈后进先出的特点，一步一步地查找可走的方块，直到找到出口为止，该方法类似于图的深度优先搜索方法，有关栈的主要操作就是出栈和入栈算法，通过不同元素的出栈和入栈操作完成搜索。使用队列结构时是利用队列先进先出的特点，一层一层向外扩展查找可走的方块，直到找到出口为止，该方法类似于图的广度优先搜索方法［3］，有关队列的操作包括出队、入队和取对头元素算法，重点是通过确定元素出队和入队顺序来完成搜索。2.2.2

递归算法解决迷宫问题也可以不使用栈和队列，直接使用线性表存储迷宫数据，用递归算法解决迷宫问题。后面介绍的算法有的也采用了递归思想，可以帮助学生理解递归算法和非递归算法的应用。2.2.3

图结构算法利用图结构解决迷宫问题，大多采用图的广度优先搜索或深度优先搜索算法，是图的遍历算法中要求学生重点掌握的两个算法。还可以考虑生成二维平面迷宫地图，转换为生成树的问题，采用普里姆算法或克鲁斯卡尔算法这两个最小生成树的经典算法，用图的导出连通子图来生成迷宫地图，从而得到相关路径。如果要找出最短路径，则可以采用迪杰斯特拉算法和弗洛伊德算法［4］，这些算法均是图结构教学中的教学重点和难点。2.2.4

人工智能算法随着迷宫规模的增大和复杂性的增加，传统搜索算法的空间和时间复杂性呈指数增加，求解最优路径是通过全部路径求出后进行比较得到的，这些算法非常费时［5］，所以后来又出现了利用人工智能算法的遗传算法［6］、蚁群算法［7］等很多算法，可以留给学生后期研究探讨。3

依据案例改革教学方式数据结构课程设计主要是培养学生选择合适数据结构解决实际问题的能力，同时提高学生今后从事软件开发所需要的各种能力与素质，包括测试能力和文档写作的能力。要求学生对布置的案例完成问题分析、逻辑设计、数据结构的选择、详细设计、编码、上机调试和课程设计报告。由于迷宫案例具备前述特点，在教学实施过程中，为更好地达成教学目标，可借助该案例的特点对教学方式进行改革，在教学过程中设置以下环节。3.1

讨论环节为帮助学生更好地完成课程设计，可在教学的不同阶段设置讨论环节。3.1.1

设计阶段组织学生分组讨论迷宫案例实现可选取哪些数据结构，如何存储数据，可用算法有哪些，学生讨论完成，教师要组织分组汇报，汇总学生的讨论结果。针对学生没有考虑周全的方案，教师要及时引导并补充完整，最终帮助学生完成数据结构选择和算法设计。3.1.2

开发阶段在开发过程中，学生会遇到不同的难点问题，发现设计阶段存在的漏洞，有些问题会让学生感觉是无法跨越的鸿沟，产生放弃思想，影响开发进度，可组织学生将遇到的问题进行汇总讨论，鼓舞士气的同时，对存在问题的解决办法进行研讨，切实可行地帮助学生渡过难关。3.1.3

验收阶段目前课程设计的教学过程中缺乏总结反馈的环节，学生提交报告后，对自己总结的结论是否正确并不确定，这个环节对于学生编程能力的提高以及对理论知识的理解很有帮助。在课程设计验收阶段，组织学生对问题分析阶段提出的问题以及设计实现后的总结分析进行讨论，引导学生得出正确的结论。教师对学生遇到的典型问题进行讲解，帮助学生提高编程水平，对优秀的作品进行点评，帮助学生开拓编程设计的思路。3.2

分组合作为培养学生合作能力和群体意识，把整个课程设计的内容进行系统安排，由2～3名同学组成一个设计小组共同完成。鉴于迷宫案例的解决可以采用多种算法，在进行任务安排时，每人可以分配一个独立的算法，分工明确可以有效地避免部分同学逃避编程的任务。要求教师在整个课程设计教学过程中，对每位同学的任务进行阶段检查。3.3

分层教学使用迷宫案例，小组分工时可以根据每个学生的水平，分配组内成员采用的数据结构及相应算法，各组之间也可以根据组间水平差异，选择不同数量的算法，要求每位同学至少完成一种算法，鼓励高水平同学尝试多种解法，组内成员互相帮助。成绩评定时，重视学生自主完成度，以是否为独立完成算法作为考查重点，避免学生由于畏难心理，网上查找算法完成，导致课程效果大打折扣。通过分层教学，鼓励学生靠自己的努力完成实践任务，改进教学效果，切实提高每个学生解决实际问题的能力。3.4

总结分析选用迷宫案例，小组成员是针对同一个问题采用不同的数据结构和算法来解决，可以进行多角度的比对分析，更有效地帮助学生提高对各种数据结构的理解与选择。3.4.1

算法的时间复杂度和空间复杂度分析采用不同数据结构和不同算法时算法的时间复杂度和空间复杂度，并通过程序运行时间进行佐证，帮助学生对时间复杂度和空间复杂度的概念有更清晰的认识。3.4.2

递归算法与非递归算法对递归算法与非递归算法进行比较，通过将递归算法修改为非递归算法实现，加深对递归思想的理解。3.4.3

各类算法优劣总结分析各类算法优劣，通过综合评估硬件配置、算法复杂性、可读