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