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

3．设计要求

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

? 如果有两个同学同时完成该课题，要求分别采用不同的存储结构。 ? 输入两个多项式，通过菜单选择项依次求得两个多项式的加、减、乘、除[选做]运行结果，并比较程序运行结果是否和手工运算结果一致。 ? 撰写课程设计报告，报告格式按规范设置。

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

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

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

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

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

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

字母作为标志）；

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

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

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

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

24

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

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

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

? 复习队列的存储和实现方法。 ? 掌握队列的实际应用。 ? 掌握文件读写的基本方法。 2．主要内容

假设洗车处有一个工作站，即一个“服务器”。每个车需洗10分钟，队列中每次至多有5辆车等待洗车。当正在清洗一辆车并且队列中有5辆车时，如果有一辆车到达，那么它将作为“溢出”不准入内且不计算在内。

平均等待时间是将每辆车的等待时间加起来再除以车的数量。结束标记是-1。下面是关于到达和离开的详细情况：

（1）如果当队列为空且没有车被清洗时，到达了一辆车，那么就马上开始清洗

这辆车；它没有进入队列。

（2）每当一辆车通过10分钟的清洗后，它就马上离开洗车处，随之队头的车辆

出队进入清洗过程。

（3）所有车辆的到达时刻从arrive.txt文件中读入，求出清洗车辆总数、清洗

车辆等待的总时间、平均等待时间等信息写回arrive.txt文件后面。 （4）参与平均等待时间计算的车辆为所有参与清洗的车辆，不包括无等待位置

并没有进入洗车处洗车的车辆。

图C3-1 车辆到达时刻表及程序计算结果

3．设计要求

? 利用C、C++、C#或Java等语言实现该程序，程序应上机调试通过并运行正确。

25