数据结构课程设计实习报告
班 级： 学生姓名： 学 号：
2011.6
1
目 录
一、需求分析 ................................................................................................. 错误！未定义书签。 二、逻辑设计 ................................................................................................................................... 2 三、详细设计 ................................................................................................................................... 5 四、程序编码 ................................................................................................................................... 9 五、程序调试与测试 ..................................................................................................................... 35 六、结果分析 ................................................................................................................................. 39
2
一、 需求分析：
1、 程序一：单链表的应用
（1）要求生成线性表时，可以键盘上读取元素。通过在键盘上输入的数据构造成单链表，进而对构造成的单链表进行插入、删除、遍历等操作的实现。
（2）限制条件是要求在生成线性表的时候，线性表中的元素是从键盘上输入而不是自动生成，这样就可以对自己想要进行的元素序列进行各种操作。
2、 程序二：表达式求值
表达式求值的程序是要求从键盘上输入一个以字符序列的形式从键盘输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值。设计的程序是中缀表达式求值，即直接将表达式以一般的序列输入，从而得出结果。
3、 程序三：二叉排序树的操作（创建，插入，查询，删除）
二叉排序树的程序是通过构造程序来实现对二叉树的创建、插入、查询、删除等基本操作，从键盘上输入一序列的数据构造成二叉排序树，再对构建的二叉排序树进行插入、查询、删除等操作。
4、 程序四：二叉树的遍历
二叉树的遍历程序是通过构造一棵二叉树来实现对二叉树的前序遍历、中序遍历、后序遍历以及求出二叉树的叶子结点的个数。
5、 程序五：最小生成树
最小生成树是通过输入一个图，此图表示了各个顶点的信息以及边上的权值，用最小生成树的程序可以得出最短的路径，此路径把所有的顶点以最经济的方式联系起来，即构造成了最小的生成树。
6、 程序六：拓扑排序：
拓扑排序程序是一个建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，实现图的拓扑排序。要求选择邻接表作为有向图的存储结构模拟整个过程，并输出拓扑排序的顶点序列。 7、 程序七：图的建立与遍历
该程序是一个建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，实现图的两种遍历。要求选择邻接表作为图的存储结构模拟整个过程，并输出图的深
1
度优先遍历和广度优先遍历。
二、 逻辑设计：
表达 式 求 值
单链表 二叉树 二叉排序树 拓扑排序 图的建立与遍历 最小生成树 主函数main
图一：课程设计总体分析
单链表的输出 删除 主函数 单链表的创建 插入 单链表的应用 查找 图二、单链表的功能
2
比较 计算 判断运算符和运算取栈顶元素 判断空 初始化堆栈 主函数 进栈 表达式求值 出栈 图三：表达式逻辑分析
菜单 中序遍历 插入 删除 查找结点 主函数 创建二叉树 二叉排序树 图四：二叉排序树逻辑分析
3
主函数 创建二叉树 菜单选择 二叉树的遍历 叶子结点数 后序 前序 中序