《数据结构》课程设计指导书(3)

课题A4：Prim或Kruskal算法求最小生成树[基于邻接表存储结构] 1．设计目的

? 掌握无向图的邻接表存储结构；

? 掌握基于邻接表存储结构无向图的遍历方法。

? 进一步掌握利用Prim或Kruskal算法求解最小生成树的过程。 2．主要内容

（1）输入给定无向网的顶点总数和所有顶点标志（每个顶点均用一个大写英文

字母作为标志）；

（2）输入图中边的总数，并利用循环依次输入各条边的端点标志及权值，建立

该无向网的邻接表存储结构；

（3）用Prim或者Kruskal算法求该无向网最小生成树。

图A4-1

3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。 ? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链

8

接库形式实现，则酌情加分。

? 如果有两个同学同时完成该课题，要求分别采用Prim和Kruskal算法求得该无向网的最小生成树。

? 按选取边的顺序输出最小生成树的各条边。 ? 撰写课程设计报告，报告格式按规范设置。

? 课程设计报告中应给出算法过程的具体分析、程序数据所采用的存储结构图、程序流程图、测试数据及其结果分析、算法的时间和空间复杂度等，另外还可以提出算法的进一步改进方法。 课题A5：Dijkstra算法求最短路径 1．设计目的

? 复习图的存储结构和遍历方法。

? 进一步掌握图的非线性特点、递归特点和动态特性。 ? 掌握并实现Dijkstra算法。 2．主要内容

（1）输入图的顶点总数和所有顶点标志（每个顶点用一个大写英文字母作为标

志）；

（2）输入图的各条边，建立该图的邻接表或邻接矩阵存储结构； （3）输入图中的任意一个顶点的标志；

（4）利用Dijkstra算法求出该顶点到其它所有顶点的最短路径和最短路径长

度，并输出。

图A5-1

3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。 ? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链接库形式实现，则酌情加分。

? 撰写课程设计报告，报告格式按规范设置。

? 课程设计报告中应给出算法过程的具体分析、程序数据所采用的存储结构图、程序流程图、测试数据及其结果分析、算法的时间和空间复杂度等，另外还

9

可以提出算法的进一步改进方法。 课题A6：拼写检查器[AVL树的应用] 1．设计目的

? 掌握平衡二叉树（AVL树）的存储结构，构造方法和查找过程。 ? 进一步掌握应用平衡二叉树解决实际问题。 2．主要内容

现代字处理器最有用的特点之一就是拼写检查，就是在文档中扫描可能的拼写错误。这里说的“可能的”拼写错误是因为文档中可能包含合法但不在字典中的单词。例如，在键入文章中使用的单词“iterator”和“postorder”时，这些单词就被看作是字处理器所找不到的。

完整的问题是：给出directionaryFile中的一个字典，以及由用户提供名称的文件中的一个文档，输出在文档中而在字典里找不到的所有单词。下面进行一些简单化的假设：

（1）字典只有小写字母组成。

（2）文档中的每个单词只由字母组成——其中可能有一些或全部是大写的。 （3）文档中的每个单词后面跟着0个或更多的标点符号，随后是任意数量的空

白和行尾标志。

（4）字典文件中的单词是按照字典序法排列的并且将被装入内存，文档文件中

的单词不必按照字典序法排列。 3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。 ? 如果程序采用C#或Java等语言实现，则酌情加分；如果主要函数采用动态链接库形式实现，则酌情加分。

? 从directionaryFile文件中读入字典中的各个单词构造二叉排序树。 ? 输入检查文档文件名，输出检查文档中在字典中未查找到的单词。 ? 撰写课程设计报告，报告格式按规范设置。

? 课程设计报告中应给出算法过程的具体分析、程序数据所采用的存储结构图、程序流程图、测试数据及其结果分析、算法的时间和空间复杂度等，另外还可以提出算法的进一步改进方法。

课题A7：中缀表达式转后缀表达式，并利用后缀表达式求值[运算对象为多位数] 1．设计目的

? 掌握栈“后进先出”的特点。

? 掌握栈的典型应用——中缀表达式转后缀表达式、后缀表达式求值。 2．主要内容

中缀表达式转换为后缀表达式的步骤：

10