《数据结构》实验教案叶双.docVIP

数 据 结 构 课程实验教案 第 1 页 实验题目： 线性表及其应用 约瑟夫环 机时安排 4小时 实验时间 第4-5周 实验目的： 帮助学生熟练掌握线性表的基本操作在顺序和链式两种存储结构上的实现，其中以各种链表的操作和应用作为重点内容。 实验内容： 　　 １、问题描述：约瑟夫问题的一种描述为，编号为1,2,3,……n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m的值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序求出出列顺序。 ２、基本操作：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 ３、测试数据：m的初值为20；n=7,7个人的密码依次为：3,1,7,2,4,8,4,首先m值为6（正确的出列顺序应为6,1,4,7,2,3,5）。 ４、实现提示：程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n≤30。此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。 ５、选作内容：集合的并、交、差运算。 参考资料（含参考书、文献等）： 《数据结构题集》（Ｃ语言版）严蔚敏　吴伟民 清华大学出版社 1999.2 教学过程设计：复习 分钟，授新课 　　 分钟，安排讨论 分钟，布置作业 分钟，其他 分钟 授课类型（请打√）：理论课□ 讨论课□ 实验课□ 练习课□ 其他□ 教学方式（请打√）：讲授□ 讨论□ 示教□ 指导□ 其他□ 教学资源（请打√）：多媒体□ 模型□ 实物□ 挂图□ 音像□ 其他□ 填表说明：1、每项页面大小可自行添减；2、教学内容与讨论、思考题、作业部分可合二为一。 数 据 结 构 课程实验教案 第 2 页 实验题目： 栈和队列及应用 迷宫问题 机时安排 4小时 实验时间 第6-7周 实验目的： 　　使学生深入了解栈和队列的特性，以便在实际问题背景下灵活运用它们，同时还将巩固对这两个结构的构造方法的掌握及基本操作的实现。 实验内容： 　　１、问题描述：以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得到没有通路的结论。 ２、基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2)… ３、测试数据：迷宫的测试数据如下：左下角(1,1)为入口，右下角(8,9)为出口。 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 ４、实现提示：计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为(1,1)，出口点的下标为(n,n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。 ５、选作内容： 算术表达式求值。 参考资料（含参考书、文献等）： 《数据结构题集》（Ｃ语言版）严蔚敏　吴伟民 清华大学出版社 1999.2 教学过程设计：复习 分钟，授新课 　　 分钟，安排讨论 分钟，布置作业 分钟，其他 分钟 授课类型（请打√）：理论课□ 讨论课□ 实验课□ 练习课