发布时间 : 星期三 文章孙华老师--《数据结构》课程设计题目及要求20131210更新完毕开始阅读f4b23356caaedd3383c4d36c
2013-2014学年第一学期 <数据结构>课程设计题目及要求
本课程设计一共包括六道大题，请同学们根据自己的爱好选择其中一道大题。每道大题分为若干小题，请根据要求完成，并撰写课程设计报告（电子版）。 实习报告规范
实习报告的开头给出题目、班级、姓名、学号和完成日期，并包括以下内容： 1、需求分析
说明调和设计的任务，主要内容包括： （1）输入的形式和输入值得范围。 （2）输出的形式。
（3）程序所能达到的功能。 （4）测试数据。 2、概要设计
说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系（最好用图说明） 3、详细设计
实现概要设计中定义的所有数据类型，画出函数的调用关系图。 4、调试分析
5、用户使用说明 6、测试结果
7、附录（附全部代码）
一、线性表（第1和第2题均为必做题，难度：?）
1、集合的并、交和差运算的算法。（必做）
问题描述：设计一个能演示集合的并、交和差运算的程序。 要求：演示程序以用户和计算机的对话方式执行。 o
2、一元多项式的操作。(任意选择三项要求)
问题描述：设计一个一元稀疏多项式简单计算器。 要求：
（1）输入并建立多项式。
（2）输出多项式，输出形式为整数序列：n，c1，e1，，c2，e2，?，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。
（3）多项式a和b相加，建立多项式a+b。 （4）多项式a和b相减，建立多项式a-b。 （5）计算多项式在x处的值。 （6）求多项式a的导函数。
（7）多项式a和b相乘，建立多项式a*b。
二、栈、队列和递归程序设计（第1题必做，第2和3题任选一题，难度：???）
1、求算术表达式的值。（必做）
问题描述：设计一个程序，演示用算符优先法对算术表达式求值的过程。
要求：以字符序列的形式从终端输入以“#”结束表达式。如果表达式正确计算表达式的值，否则指出表达式中错误的类型。在输入的表达式中可以有加、减、乘、除和括号运算，输入的数据为实数。输出表达式的值，并且输出在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。
2、迷宫问题。
问题描述：随机产生一个m*n的迷宫，0和1分别表示迷宫中的通路和障碍。求出一条从入口到出口的通路，或得到没有通路的结论。 要求：以链表作存储结构的栈类型，写一个非递归程序。
3、HANOI问题的求解演示。
问题描述：设计一个程序，演示HANOI问题的实现过程。 要求：
（1）用户可手工移动圆盘实现求解。 （2）用户可让计算机演示求解过程。 （3）用非递归算法实现。
三、数组和广义表（第1和2题均为必做题，难度：??） 1、三元组表示的稀疏矩阵的转置、加法和乘法的实现。（必做）
问题描述：设计一个程序，演示用三元组和十字链表表示的稀疏矩阵的转置、加法和乘法的实现。 要求：
（1）演示稀疏矩阵A的三元组和十字链表的建立过程。 （2）演示稀疏矩阵A的转置过程。
（3）演示稀疏矩阵A和B的相加过程。 （4）演示稀疏矩阵A和B的相乘过程。
2、识别广义表的“头”或“尾”的演示。（必做）
问题描述：设计一个程序，建立广义表的存储结构，演示在此存储结构上实现的广义表求头/尾操作序列的结果。 要求：
（1）设计一个广义表，允许分多行输入，其中可以任意输入空格符，原则上
是不限长的仅由字母或数字组成的串。
（2）按表头和表尾的分解方法编写建立广义表存储结构的算法。
四、树（第1和2题均为必做题，难度：???） 1、二叉树的遍历。（必做）
问题描述：设计一个程序演示在二叉树上进行三种遍历的过程。 要求：
（1）从键盘上输入二叉树的每一个结点，演示二叉树T的建立过程。 （2）演示各种遍历的遍历过程。
2、线索二叉树的应用。（必做）
问题描述：设计一个程序，演示线索二叉树的建立和插入、删除结点的过程。 要求： （1）从键盘上输入线索二叉树的每一个结点，演示线索二叉树T的建立过程。 （2）演示在T上插入一棵子树的过程。 （3）演示在T上删除一棵子树的过程。
五、图（第1和2题均为必做题，难度：???） 1、图扁历的演示。（必做）
问题描述：设计一个程序，演示在有向图或无向图中遍历所有结点的过程。 要求：
（1）分别用深度优先或广度优先实现（选择一项）。
（2）从任意指定的结点为起点，分别输出每种遍历下的结点访问序列和相应
生成树的边集。
2、最小生成树。（必做）
问题描述：设计一个程序求连通网中的最小生成树 要求：
（1）构造一个不少于10个顶点30条边的连通网。
（2）用Kruskal算法求从任意指定的结点开始的最小生成树。 （3）演示生成过程。
六、查找和排序（第1和2题均为必做题，难度：???） 1、平衡二叉树的操作。
问题描述：利用平衡二叉树实现一个动态查找表 要求：
（1）从键盘上接受数据，建立一棵平衡二叉树的过程。 （2）实现动态查找表的三种基本功能：查找、插入和删除。 （3）合并两棵平衡二叉树。
（4）把一棵平衡二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键
字都小于或等于X，另一棵树中的任一关键字都大于X。
2、内部排序算法的比较。 问题描述：设计一个程序演示各种内部排序方法在排序时，关键字的比较次数和关键字的移动次数 要求：
（1）对常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择
排序、快速排序、系尔排序和堆排序。 （2）随机产生100个以上数据。