数据结构课程设计最短路径.doc

数据结构课程设计 题目名称： 最短路径 计算机科学与技术学院 需求分析 (1)题目：最短路径 实现图的输入，选择合适的结构表示图，在此基础上实现求解最短路径的算法，可以从任意一点求最短路径，学生必须准备多组测试数据，并设计清晰易懂的输入输出界面， 要求：如何用多种数据结构来求解问题。同时要求实现对应数据结构的所有基本操作。 程序的输入与输出:要求用多种数据结构求解问题，也就是要用邻接表与邻接矩阵实现最短路径的算法，需要有多组输入输出， 输入的形式和输入值的范围：输入的形式为整型 先输入共需要创建几次图 再分别输入边数和顶点数（范围：1~100） 输入1和2选择是否为有向图图（1为有向，2为无向） 对应每条边输入起点和终点下标，以及对这条边的权值（最大的权值为100）。 输入在邻接表的基础上输入深度与广度优先搜索的起点 我们输入求各种最短路径起点和终点 输出的形式； 输出所建立的邻接表（表结点后面的括号是头结点与表结点的权值） 输出DFS和BFS的结果 输出该图不带权值的最短路径与路径 接下来输入起点和终点，求带权值的最短路径也就是Dijstra算法，输出长度并给出路径 前面都是用邻接表实现的各种算法，接下来的Floyd算法就用矩阵实现，于是直接邻接表转矩阵输出 用Floyd算法求出图的多源最短路径，给出起点终点输出最短路径长度，接着便到了第二次创建图，直至循环结束。 程序的功能: 求给出带权图的任意两点，输出最短路径长度并给出其最短路径所经过的顶点。 在实际应用中可以将交通网络化成带权的图，图中顶点表示城市，边代表城市之间的公路，边上的权值表示公路的长度。这样可以发现两个地方之间有无公路可连，在几条公路可通的情况下，可以找到那条路径最短。也就是现在地图app中的功能。 （4）测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。 在有向图中输入错误的数据（顶点与顶点方向相反），会输出逆向信息。 概要设计 1.主程序流程 主程序首先多组输入一个n，在n不为0的前提下循环执行 调用 BuildGraph()函数，创建一个图并以邻接表的形式存储 BuildGraph()函数输入顶点、边数调用CreateGraph(Nv）函数，初始化一个有Nv个顶点但没有边的图，再根据结构体Edge输入每个边的信息，调用InsertEdge( Graph, E ,c );函数将每条边插入到仅仅初始化的图中，完成一个图的建立，并返回一个邻接表类型的结构体 主函数接到返回来的邻接表结构体,调用outL()函数，输出这个邻接表 输入起点，调用DFS(Graph,v1,1);函数进行递归求解深度优先搜索并直接输出 输入起点，调用BFS(Graph,v1);函数，求解广度优先搜索并直接输出 输入起点、终点，调用Unweighted ( Graph, v1 );函数求得起点到每个点的最短路径，再用dist[v2]输出。 如果dist[v2]大于0证明v1可以到达v2，调用outpath(v2)输出路径 输入起点、终点，调用Dijkstra(Graph,v1);函数求得起点到每个点的最短路径，再用dist[v2]输出。 如果dist[v2]小于定义的INF，证明v1可以到达v2，再次调用outpath(v2)输出路径 用MGraph gra;创建一个邻接矩阵之后，调用transform(Graph);进行邻接表与邻接矩阵的转换 outM(gra);函数，以二维数组的形式输出邻接矩阵 调用Floyd(gra,D,pa);函数求得多源最短路径，存储在D这个二维数组中，给出起点，终点直接输出。 2.所有用到的抽象数据类型 （1）边的定义 （a）表示边的起点和终点 （b）边的权重 （2） 邻接表的表结点的定义 （a）邻接点下标 （b）边权重 （c）指向下一个邻接点的指针 （3）邻接表的顶点表头结点的定义 （a）边表头指针 （b）存顶点的数据 （c）邻接表类型的 AdjList存储邻接表的头结点 （4） 邻接表对应图结点的定义 （a）顶点数 （b）边数 （c）邻接表 （5）邻接矩阵的定义 （a） 顶点数 （b） 边数 （c）二维数组形式的邻接矩阵 （6） BFS存数据的队列 （a）队头 front标记 （b）队头 rear标记 （c）存数据的数组 （7）用于输出最短路径的栈 （a）栈顶top标记 （b）存数据的数组 3.设计程序的各个模块（即函数）功能及设计思想 CreateGraph( int VertexNum )函数 功能：初始化一个有Vert