数据结构课程设计---关于最短路径问题 和 二叉树排序问题

1、 课程设计综合成绩评定课程设计综合成绩评定 设计题目一：设计题目一： 二 叉 排 序 树 设计题目二：设计题目二： 最 短 路 径 问 题 设计题目三：设计题目三： 考核项目 分值 A C 得分 设计 情况 （共 70 分） 设计工 作量与 难度 20 设计工作量大与设 计有一定难度 设计工作量与难度 一般，基本达到了要 求 设计 方案 15 设计方案正确、合 理 设计方案较正确、基 本合理，但不是最优 设计完 成情况 35 完成了选题的设计 内容，设计功能完 整，相关算法设计 正确，程序结果正 确、直观性好 基本完成了选题的 设计内容及主要选 题功能，相关算法设 计基本正确，程序结 果正确

2、设计 报告 （共 15 分） 报告组 织结构 及内容 10 内容组织及结构合 理、内容充实、层 次清晰、图表得当 内容组织及结构较 合理、内容较充实、 层次较清晰、图表应 用基本得当 报告排 版格式 5 格式规范，完全符 合要求 格式基本规范，基本 符合要求 设计态度 （共 15 分） 15 设计态度认真、积 极 设计态度比较认真 综合得分 课程设计综合成绩（折合为优、良、中、及格与不及格计折合为优、良、中、及格与不及格计） 其它说明： 目 录 1.二叉排序树 . 1 1.1 问题描述 1 1.2 设计方案与概要设计 2 1.3 详细设计 4 1.4 程序运行说明与结果 . 11 2.最短路径

3、问题 13 2.1 问题描述 . 13 2.2 设计方案与概要设计 . 16 2.3 详细设计 . 17 2.4 程序运行说明与结果 . 27 3.总结与分析 32 数据结构课程设计数据结构课程设计 1 1. 二叉排序树 1.1 问题描述 知二叉排序树的二叉链表存储结构的类型定义如下： typedef struct node int data; /用整数表示一个结点的名用整数表示一个结点的名 struct node *LChild,*RChild; /左右指针域左右指针域 BSTNode,*BSTree; （1）键盘输入一个元素序列创建一棵如图（1）的二叉排序树，并输出 该二叉排序树的中序遍历

4、序列； 图（1） （2）在图（1）中所得的二叉排序树中插入一个值为 58 的结点，输 出它的中序遍历序列； （3）在题（2）中所得的二叉排序树中删除值为 45 的结点，输出它的中 序遍历序列； （4）我们知道教材中 P220 给出的二叉排序树的删除操作算法中，是用 左子树中最右下结点来替代要被删除的结点（即为要被删除结点的中序前 驱），也可以用右子树中最左下结点来替代要被删除的结点（即为要被删除 结点的中序后继），根据此思路修改 P220 算法在写一个删除操作，并利用 45 55 60 53 40 23 70 37 12 24 数据结构课程设计数据结构课程设计 2 修改后的删除算法删除图（1）中二叉排序树的值为 45 的结点，输出它的中 序遍历序列； （5）利用题（2）中所得的二叉排序树的所有叶子结点构造一个带头结 点的单链表 L。要求不能破坏这棵二叉排序树。所得的单链表 L 元素递增， 并输出单链表 L。 （6）设计算法将图（1）的二叉排序树的左右子树进