《数据结构实验课.doc》由会员分享，可在线阅读，更多相关《数据结构实验课.doc（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程实验实施方案（2015年）一、总体设计要求1、采用C编程语言，应用抽象数据类型的设计，在实现数据结构基本操作的基础上，完成数据结构的基本应用。2、程序采用模块化设计思想，划分功能模块结构，确定必要的模块间的联系，按照基本操作调试、主算法设计与实现、主函数模块调用的步骤进行实验。3、给出必要的测试用例数据。4、推荐程序完成必要的界面设计。5、完成实验题目中规定的基本功能，在完成基本功能的基础上，可以增加和完善功能。6、对所完成的实验课题的算法进行必要的时间和空间的性能评价。二、实验分组要求1、每个班分成若干个实验课题小组，每组原则上2-3人，个人自愿入组，采用组长负责制。2、每个实验
2、给出若干个实验参考题目供课题组选择其中之一。三、实验题目参考实验一 线性表应用类实验题目参考1、约瑟夫环问题 【问题描述】Josephus排列问题定义如下：假设n个竞赛者排成一个环形。给定一个正整数mn，从第1人开始，沿环计数，第m人出列。这个过程一直进行到所有人都出列为止。最后出列者为优胜者。全部出列次序定义了1，2，n的一个排列。称为（n，m）Josephus排列。例如，（7，3）Josephus排列为3,6,2,7,5,1,4。【实验要求】设计求解Josephus排列问题程序。（1）采用顺序表、单链表等数据结构。（2）或者，问题转化为“奇数次顺时针轮转，偶数次逆时针轮转”，采用双向循环链
3、表实现Josephus排列问题。2、集合的并交差运算【问题描述】设计一个能演示集合的并、交、差运算程序。【实验要求】（1）采用顺序表或链表等数据结构。（2）集合的元素限定为数字和小写英文字母。3、一元多项式运算 【问题描述】设计一个一元多项式简单计算器。【实验要求】（1）采用顺序表或链表等数据结构。（2）输入并建立多项式。（3）输出一元多项式加、减运算结果的多项式。4、学生成绩管理【问题描述】对信息学院计算机科学与技术专业的20xx级本科生的学生成绩管理作一个简单的模拟。【实验要求】设计学生成绩管理的模拟程序。（1）采用顺序表登录学生成绩。（2）可以登记、查询、插入、删除学生成绩。（3）将成绩
4、按科目存储到链表中。5、图书信息管理【问题描述】对图书馆的图书信息管理作一个简单的模拟。【实验要求】设计图书信息管理的模拟程序。（1）采用顺序表登录图书成绩。（2）可以登记、查询、插入、删除图书信息。（3）将图书信息按类别存储到链表中。6、运动会竞赛成绩统计 【问题描述】东北大学第51届运动大会成功举行。共有N个学院的男女代表队参赛。大会共设M个男子项目和W个女子项目。大会即将闭幕，准备公布成绩。【实验要求】设计运动会竞赛成绩统计程序。（1）采用顺序表或链表等数据结构。（2）统计各代表队的男女总分和团体总分。（3）公布各单项成绩的前六名和团体成绩的前三名。（4）可以查询成绩。实验二 栈和队列应
5、用类实验题目参考1、算术表达式求值【问题描述】由输入的四则算术表达式字符串，动态生成算术表达式所对应的后缀式，通过后缀式求值并输出。【实验要求】设计十进制整数四则运算计算器。（1）采用顺序栈等数据结构。可以将数据存储在顺序表中。（2）给定表达式字符串，后缀表达式。（3）对后缀表达式求值并输出。2、运动员混合双打组合 【问题描述】设有M个男羽毛球运动员和N个女羽毛球运动员，现进行男女混合双打组合K轮配对。男女运动员分别编号排队在等候队列，按顺序依次从男女运动员中各出队1人组合配对。本轮没成功配对者等待下一轮次配对。【实验要求】设计程序模拟完成运动员组合配对过程。（1）采用队列等数据结构。（2）输
6、出每轮的配对信息。3、车厢调度 【问题描述】假设停在铁路调度入口处的列车编号依次为1,2,n。【实验要求】设计程序求出所有可能的长度为n的输出车厢序列。（1）采用栈或队列等数据结构。（2）输出调度序列。（3）推荐采用双栈结构求解。4、八皇后问题 【问题描述】设一个88的棋盘里放置8个皇后，要求在每行、每列、没斜线只允许放置1个皇后。【实验要求】设计实现所有可能解的程序。（1）采用栈等数据结构。（2）应用穷举法回溯策略求解。（3）尝试采用递归和非递归算法求解。5、简单背包问题【问题描述】设一个背包所允许的重量是M，假设有N件物品，物品的重量分别是Wi，可以任意挑选物品，从N件物品中选择若干物品，
7、所选物品的重量之和洽为S。【实验要求】设计程序实现将给定背包装满的可能解。（1）采用栈等数据结构。（2）应用穷举法回溯策略求解。（3）尝试采用递归和非递归算法求解。6、迷宫问题 【问题描述】设一个MN的迷宫，0和1分别表示通道和障碍。【实验要求】设计程序实现求从入口到出口的任意通道。（1）采用栈等数据结构。（2）应用穷举法回溯策略求解。（3）尝试求解所有通路或最佳路径。实验三 树和图应用类实验题目参考1、哈夫曼编码【问题描述】利用哈夫曼树求得用于通信的二进制编码称为哈夫曼编码。以N中字符出现的频率作为权值，设计电文总长度最短的二进制前缀编码（哈夫曼编码）。【实验要求】设计哈夫曼编码及解码程序。
8、（1）采用二叉树等存储结构。（2）创建哈夫曼树，生成哈夫曼编码。（3）给出一个文件的编码和译码。2二叉排序树【问题描述】对于一个随机序列，创建二叉排序树，通过遍历给出有序序列，并实现元素的定位和动态删除。【实验要求】设计二叉排序树及应用程序。（1）采用二叉树等存储结构。（2）输入一个随机序列，创建二叉排序树。（3）给出相应的有序序列。（4）实现二叉排序树的定位操作，即查找指定元素，如果存在给出在序列中的序位号。（5）实现二叉排序树的删除操作。3、图遍历生成树演示【问题描述】通过对连通图和非连通图的遍历，访问图中全部结点。【实验要求】设计图遍历生成树演示程序。（1）采用邻接表和邻接矩阵等存储结构
9、。（2）分别采用深度优先和广度优先遍历实现。（3）尝试插入或删除一条边或一个结点的访问操作。4、光纤管道铺设施工问题【问题描述】设计校园内有N个教学楼及办公楼，要铺设校园光纤网，如何设计施工方案使得工程总的造价为最省。【实验要求】设计校园光纤网铺设的最小生成树模拟程序。（1）采用邻接表或邻接矩阵存储结构。（2）分别采用普利姆算法和克鲁斯卡尔算法实现。5、关键路径问题【问题描述】设计有N个工序的工程施工图，为保证工程进度，求其关键路径，以保证工期完成。【实验要求】设计求解工程关键路径的模拟程序。（1）采用邻接表或邻接矩阵存储结构。（2）使用栈或队列等作为拓扑排序的辅助数据结构。（3）可以尝试采用
10、深度优先遍历求解问题。实验四 查找和排序应用类实验题目参考1、快速排序应用【问题描述】应用快速排序算法，查找顺序表中的第K小的元素。【实验要求】设计求顺序表中的第K小元素。（1）采用顺序表存储结构。（2）完成顺序表的快速排序。（3）应用快速排序求第K小元素。（4）通过性能分析，尝试如何改进。2、堆排序【问题描述】应用堆排序求出记录中的前K名。【实验要求】设计堆排序应用程序。（1）采用二叉树的二叉链表结构。（2）完成堆排序的插入、删除、查找等基本操作。（3）给出应用实例。3、计数式基数排序【问题描述】统计研究生入学成绩的排名。除了总分的要求外，还有专业课等单科小分的要求。【实验要求】设计计数式基
11、数排序的应用程序。（1）采用顺序表存储结构。（2）利用对关键字位的统计和复制的方法实现计数式基数排序。（3）给出应用实例。4、平衡二叉树演示【问题描述】利用平衡二叉树设计动态查找表。【实验要求】设计平衡二叉树的动态演示的模拟程序。（1）采用平衡二叉树存储结构。（2）完成平衡二叉树的创建、查找、插入和删除的演示操作。（3）可以考虑两棵平衡二叉树的合并。5、传统排序与优化排序比较【问题描述】传统的插入、选择、交换排序，对应优化的排序方法有希尔排序、堆排序和快速排序。【实验要求】设计传统排序和优化排序算法的比较程序。（1）采用顺序表等存储结构。（2）比较算法的关键字比较次数、移动次数、时间复杂度、平
12、均性能、空间复杂度等。（3）测试数据由随机数生成器生成。四、实验报告要求实验教师收集每个人递交个人实验报告的全部电子版，实验报告格式按标准格式写作。实验报告的内容包括：1、 问题定义及需求分析说明课题的目的和任务。应包括：输入的形式和输入值的范围；输出的形式；程序的功能；测试数据。2、 概要设计说明程序中所用到的抽象数据类型的定义、主程序的流程以及各程序模块之间的调用关系。3、 详细设计实现概要设计中定义的所有数据类型及存储结构；对每个模块及操作写出伪码算法。4、 调试分析对所遇问题的解决方法及分析；算法的时间复杂度分析；经验和体会。5、 使用说明如何使用该程序，详细列出每一步的操作步骤。6、 测试结果列出包括输入和输出的测试结果。7、 附录带注释的源程序。五、实验成绩实验成绩采用百分制，由平时实验课成绩（20%），实验报告成绩（30%），实验程序验收（50%）组成，按比例折算到课程的总成绩。六、实验教材及参考书1 严蔚敏、吴伟民 编著.数据结构题集（C语言版）. 北京：清华大学出版社. 19992 严蔚敏、吴伟民 编著.数据结构（C语言版）.北京：清华大学出版社. 20073 严蔚敏、陈文博 编著.数据结构及应用算法教程（修订版）. 北京：清华大学出版社. 2011