以下为《数据结构课程设计第九组》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

河南******

《数据结构》课程设计报告

最短路径算法

学生姓名：Z计某某203班 秦某某

Z计某某203班 李某某

所在院系： 信息工程系

所学专业： 计算机科学与技术

完成时间： 2020-12

需求分析

最短路径算法是图论研究中一个经典算法，旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体形式包含：

实现图的输入：选择合适的结构表示图，在此基础上实现求解最短路径的算法，可以从任意一点求最短路径，我们必须准备很多组的测试数据，并设计清晰易懂的输入输出界面。对此有一些要求：如何用多种数据结构来求解问题。同时要求实现对应数据结构的所有基本操作。

程序的输入与输出：要求用多种数据结构求解问题，也就是要用邻接表与邻接矩阵实现最短路径的算法，需要有多组输入输出，(a)输入的形式和输入值的范围:输入的形式为整型1.先输入共需要创建几次图2.再分别输入边某某和顶点数(范围:?1^?100)?3.输入1和2选择是否为有向图图(1为有向，2为无向)

对应每条边输入起点和终点下标，以及对这条边的权值(最大的权值为100)5.输入在邻接表的基础上输入深度与广度优先搜索的起点6.我们输入求各种最短路径起点和终点(b)输出的形式;1.输出所建立的邻接表(表结点后面的括号是头结点与表结点的权值)2.输出DFS和BFS的结果

输出该图不带权值的最短路径与路径4.接下来输入起点和终点，求带权值的最短路径也就是.Dijstra算法，输出长度并给出路径5.前面都是用邻接表实现的各种算法，接下来的Floyd?算法就用矩阵实现，于是直接邻接表转矩阵输出6.用Floyd算法求出图的多源最短路径，给出起点终点输出最短路径长度，接着便到了第二次创建图，直至循环结束。(3)程序的功能:求给出带权图的任意两点，输出最短路径长度并给出其最短路径所经过的项某某。在实际应用中可以将交通网络化成带权的图，图中顶点表示城市，边代表城市之间的公路，边上的权值表示公路的长度。这样可以发现两个地方之间有无公路可连，在几条公路可通的情况下，可以找到那条路径最短。也就是现在地图app中的功能。

（4）测试数据：包括正确对待输入及输出结果和含有错误的输入及输出结果

在有向图中输入错误的数据（顶点与顶点方向向反），会输出逆向信息。

概要设计

主程序流程(a)主程序首先多组输入一个n,在n不为0的前提下循环执行(b)调用BuildGraph()函数，创建-一个图并以邻接表的形式存储(c)?BuildGraph()函数输入顶点、边某某调用CreateGraph?(Nv)函数，初始化-一个有Nv个顶点但没有边的图，再根据结构体Edge输?入每个边的信息，调用InsertEdge(?Graph，?E?,c?);函数将每条边插入到仅仅初始化的图中，完成一个图的建立，并返回一个邻接表类型的结构体

(d)主函数接到返回来的邻接表结构体,调用outL()函数，输出这个邻接表(e)输入起点，调用DFS?(Graph,?v1,?1)?;函数进行递归求解深度优先搜索并直接输出(f)输入起点，调用BFS(Graph,?v1);函数，求解广度优先搜索并直接输出(g)输入起点、终点，调用Unweighted?(?Graph，?v1?);函数求得起点到每个点的最短路径，再用dist[v2]输出。(h)如果dist[v2]大于0证明v1可以到达v2,调用outpath(v2)输出路径

(i)输入起点、终点，调用Di?jkstra?(Graph,?v1)?;函数求得起点到每个点的最短路径，再用dist[v2]输出。(?j)如果dist[v2]小于定义的INF，?证明v1可以到达v2，再次调用outpath(v2)输出路径(k)用MGraph?gra;创建一个邻接矩阵之后，调用transform?(Graph)?;进行邻接表与邻接矩阵的转换

(1)?outM(gra)?;函数，以二维数组的形式输出邻接矩阵(m)调用Floyd(gra,?D,?pa)?;函数求得多源最短路径，存储在D这个二维数组中，给出起点，终点直接输出。2.所有用到的抽象数据类型(1)边的定义(a)表示边的起点和终点(b)边的权重(2)?邻接表的表结点的定义?(a)?邻接点下标(b)边权重(c)指向下一个邻接点的指针

(a)?顶点数(b)边某某(c)二维数组形式的邻接矩阵(6)BFS存数据的队列(a)队头front标记(b)队头rear标记(c)存数据的数组(7)用于输出最短路径的栈(a)栈顶top标记(b)存数据的数组3.设计程序的各个模块(即函数)功能及设计思想(1)?CreateGraph(?int?VertexNum?)函数功能:初始化一个有VertexNum个顶点但没有边的图设计思想:(a)根据邻接表结构体分配--块空间

(b)初始化图的顶点数和边某某(c)初始化邻接表头指针(d)注意:这里默认顶点编号从1开始，到Graph->Nv(e)初始化dist[]与path[]数组(2)?InsertEdge(?LGraph?Graph，Edge?E，int?c?)函数功能:在建立的图中插入边设计思想:?(a)?输入v1，v2,建立一个v2的新的邻接点(b)将V2插入V1的表头，用c做标志位，在调用函数时输入(c)若c=2,表示图为无向图，还要插入边(d)接着为V1建立新的邻接点，将V1插入V2的表头(3)?Bui?ldGraph()函数

功能:输入顶点和边某某，定义有向图和无向图，建立图，并返.回邻接表类型的指针设计思想:?(a)读入顶点个数，调用CreateGraph?(Nv)初始化有Nv个顶点但没有边的图(b)读入边某某，定义有向、无向，如果有边，建立边结点，读入边，格式为”起点终点权重”，插入邻接表(c)注意:如果权重不是整型，Weight的读入格式要改

(4)?clrv(LGraph?g)函数功能:初始化图的访问数组Visited[]为0设计思想:重置被DFS和BFS修改过的visited数组(5)?DFS(?LGraph?Graph，?Vertex?V?,?int?x)函数功能:以V为出发点对邻接表存储的图Graph进行DFS搜索设计思想:?(a)首先访问出发点v，并将其标记为已访问过;(b)然后依次从v出发搜索v的每个邻接点w。若v未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。.(c)若此时图中仍有未访问的顶点，则另选-一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

( d）也就是访问顶点v，从v的未被访问的邻接点中选取一个顶点w,从 w出发进行深度优先遍历，重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

(6）CreateQueue()函数

功能:初始化一个队列

设计思想:(a）队列的front 与rear分别置-1

(b）为数组分配空间

( 7)） AddQ (Queue Q, Vertex S)函数功能:向队列中添加元素

设计思想:(a）将rear位置挪一位

(b）在rear这位加入一个数

(8) DeleteQ(Queue Q)函数

功能:队列中删除一个元素，并返回设计思想:(a）从队列的头出队

(b）也就是front 位置加一(c）将front这位的数据弹出

(9)IsEmpty (Queue Q)函数

功能:判断队列是否为空

设计思想:(a）判断front的位置与rear是否相等

(10)Unweighted ( LGraph Graph，Vertex S )函数功能:输入两点，求对应不带权值的图的最短路径

设计思想:(a）按照递增（非递减）的顺序找出各个顶点的

最短路，类似于BFS

(b）先创建空队列, MaxSize为外部定义的常数

(c）初始化源点.dist[s] = 0

(d）对Ⅳ的每个邻接点W一>AdjV

(e)若W->AdjV未被访问过， W->AdjV到S的距离

更新

(f)将Ⅳ记录在S到W->AdjV的路径上

(11)BFS( LGraph Graph，Vertex V)函数

功能:向队列中添加元素

设计思想:(a）顶点v入队列。

(b）当队列非空时则继续执行，否则算法结束。(c）出队列取得队头顶点v;访问顶点v并标记顶点v已被访问。

(d）查找顶点v的第一个邻接顶点first。

(e)若v的邻接顶点first未被访问过的,则first入队列。

(f)继续查找顶点v的另一个新的邻接顶点first，转到步骤（e）。

(g）直到顶点v 的所有未被访问过的邻接点处理完。转到步骤（f）。

(12)clr(LGraph Graph)函数

功能:重置dist[]数组与path[]数组

设计思想:(a）重置最短路径的举例与路径

(13） FindMinDist ( LGraph Graph,int collected[])函数功能:传入一个dist[]中没有被收录(collected[]对应为-1)

的数

设计思想:(a） V从1到顶点最大的下标

(b）若Ⅳ未被收录，且dist[V]更小(c）更新最小距离更新对应顶点

(d）若找到最小dist，返回对应的顶点下标

(e）若这样的顶点不存在，返回错误标记

(14）Dijkstra( LGraph Graph,Vertex S )函数

功能:求出输入Vertex S的单源最短路径

设计思想:(a) Dijkstra算法开始采用的是一种贪心的策略，

声明一个数组dist来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T

(b)初始时,原点s 的路径权重被赋为0 (dis[s]

= 0)

(c）若对于顶点s 存在能直接到达的边( s,m) ,则把dis[m]设为w (s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大( d）初始时，集合T只有顶点s。

(e）从dis数组选择最小值（贪心），则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，OK，此时完成一个顶点，

(f)我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis 中的值。

(g)然后，又从dis中找出最小值，重复上述动作,直到T中包含了图的所有顶点。

(15) transform(LGraph a)函数

功能:邻接矩阵与邻接表转换

设计思想:(a）分析邻接矩阵与邻接表的异同

(b）邻接表有一个头结点数组，每一个对应一串链

表，跟着的是每一个顶点与邻接点相连(c）邻接矩阵则是一个二维数组，两点有边值为权

重，没有则初始化为无穷

(d）先初始化一个空的二维数组

(e)再对应邻接表每个头结点遍历其链表，将其值

对应的加入到邻接矩阵中

(16） outM(MGraph gra)函数

功能:传入邻接矩阵结构体，输出邻接矩阵设计思想:(a）相当于输出一个二维数组

(17) outL(LGraph Graph)函数

功能:传入邻接表结构体，输出邻接表

设计思想:(a）第一个循环遍历每个头结点

(b）在第一个循环中表结点的地址不为空则输出(还要输出权值)

(18)Floyd ( MGraph Graph，WeightType D[][maxVnum]， Vertex

path[][maxVnum] )函数

功能:Floyd 算法求出多源最短路径

设计思想:(a）通过Floyd计算图G=(V,E)中各个顶点的最

短路径时，需要引入两个矩阵，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵XXXXX中的元素

b[i][j]，表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。

(b）假设图G中顶点个数为N，则需要对矩阵D和

矩阵XXXXX进行Ⅳ次更新。

(c）初始时，矩阵D中顶点a[i][j]的距离为顶点

i到顶点j的权值

( d）如果i和j不相邻，则a[i][j]=oo，矩阵P的值为顶点b[i][j]的j的值

(e），对矩阵D进行N次更新

(f）第1次更新时，如果”a[i][j]的距离”>

“a[i][0]+a[o][j]”(a[i][o]+a[0][门表示”i与j之间经过第1个顶点的距离”)，

则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。

(g）同理，第k次更新时，如果”a[i][j]的距离”> “a[i][k-1]+a[k-1][j]”，则更新a[i][j门]为”a[i][k-1]+a[k-1][j]”,b[i][j=b[i][k-1]。更新N次之后，求出最短路径

( 19) Strack createStr()函数功能:创建一个栈

设计思想:(a）分配空间，top = -1

(20） push(Strack ptr, int v)函数功能:向栈中添加元素

设计思想:(a） top加一

(b）对应位置存为v

(21 ) pop(Strack ptr)函数

功能:出栈

设计思想:(a）先将栈顶元素弹出，top 减一

(22） sIsEmpty (Strack ptr)函数

功能:判断栈是否为空

设计思想:(a）若果top=-1，为空，否则返回0

(23) outpath(int v)函数

功能:输出最短路径

设计思想:(a）由于存最短路径的path[]数组每位存的只是

上一个顶点，所以每次查找都会不断地找到每个顶点的上级，直至path[v]=-1，会形成一个方向的路径,就要利用堆栈后进先出的特点输出。(b）在 path存的数据不为-1时，将他们全部压入栈中，再将他们全部输出

三、详细设计

1.程序流程图

2。数据类型的实现

(1）边的定义

typedef struct ENode *PtrToENode;struct ENode{

Vertex V1，V2;/*有向边*/WeightType Weight;/*权重*/

};

typedef PtrToENode Edge;

(2)邻接表的表结点的定义

typedef struct AdjVNode*PtrToAdjVNode;

struct AdjVNode;

Vertex AdjV;

/*邻接点下标*/

WeightType Weight;/*边权重*/

PtrToAdjVNode Next;/*指向下一个邻接点的指针*/

};

typedef PtrToAdjVNode ANode;(3）邻接表的顶点表头结点的定义typedef struct Vnode{

PtrToAdjVNode FirstEdge;/*边表头指针*/DataType Data;

/*存顶点的数据*/

/*注意:很多情况下，顶点无数据，此时Data可以不用出现*/}AdjList[maxVnum];/*AdjList是邻接表类型*/

(4)邻接表对应图结点的定义

typedef struct GNode *PtrToGNode;struct GNode {

int Nv;

/*顶点数*/

int Ne;/*边某某*/AdjList G; /*邻接表*/

};

typedef PtrToGNode LGraph;/以邻接表方式存储的图类型*/(5）邻接矩阵的定义

typedef struct MNode *PtrToMNode;struct MNode{

int Nv;/*顶点数*/int Ne;/*边某某*/

WeightType G[max Vnum][max Vnum];/*邻接矩阵*/

};

typedef PtrToMNode MGraph;/*以邻接矩阵存储的图类型*/(6)BFS存数据的队列

typedef struct Que *Queue;struct Que{

int front;int rear;

int datalist[maxVnum];

};

(7)用于输出最短路径的栈

typedef struct Str *Strack;struct Str{

int top;

int Strlist[maxVnum];

};

3.重要函数的伪代码

(1）无权图的单源最短路径void Unweighted (Vertex s){

Enqueue (s, q) ;

while(队列不空){

v = Deququ(q) ;

for(v的每个邻接点w){if(w没被访问过){

更新w的距离;path[w]=v;Enqueue (w, q);

}

}

}

(2)有权图的单源最短路径

void Dijkstra(Vertex s){while(1){

v=未收录顶点中的dist最小者;if(这样的v不存在)

break ;

collected[v] = true;for(v的每个邻接点w)if(w没被收录){

if(dist[v] +v到w的权值< dist[w]){

更新w的最短距离;

path[w] = V;

}

}

}

(⑵有权图的单源最短路径

void Dijkstra(Vertex s){while(1){

v=未收录顶点中的dist最小者;if(这样的v不存在)

break;

collected[v] = true;for(v 的每个邻接点w)if(w没被收录){

if(dist[v] +v到w的权值< dist[w]){

更新w的最短距离;

path[w] = V;

}

}

}

(3)Depth-first search

访问顶点v;

visited[v]=1;//算法执行前visited[n]=O

w=顶点v的第一个邻接点;

while (w存在）{

if (w未被访问)

从顶点w出发递归执行该算法;

w=顶点v的下一个邻接点;}

(4)BFS广度优先搜索

初始化队列Q; visited[n]=0;

访问顶点v; visited[v]=1;顶点v入队列Q;

while(队列Q非空）{

v=队列Q的对头元素出队;

w=顶点v的第一个邻接点;

while (w存在）{

如果w未访问，则访问顶点 w;

visited[w]=1;

顶点w入队列Q;

W=顶点v的下一个邻接点。}}

四、调试分析

(1）调试过程中遇到的问题是如何解决的。

我是将每一个部分分开设计，运行成功再将他们整合到一起，不免会出现各种各样的问题，单独拿出去就可以运行，但放在一起没有报错，可就是做不对。而且后来我发现早成这种现象的不是因为程序有大问题，是一些根本就没有注意的小点造成的，例如定义的i加入到程序中就会被其中的i覆盖，结构体定义的不同等等，让我明白以后需要注重整体，在意细节，才能快速的完成任务。

(2）算法的时空分析和改进设想;

首先，利用邻接矩阵一定是稠密图才合算，对 DFS 时间复杂度为o（n^2），广度优先搜索相同。而利用邻接表存储稀疏图合算。对DFS时间复杂度为0(n+e)，广度优先搜索相同

内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 黑客可以利用这个安全漏洞黑客可以利用这个安全漏洞黑客可以利用这个安全漏洞黑客可以利用这个安全漏洞黑客可以利用这个安全漏洞………，如图2-1所示。（逐章单独编序，尽量避免隔页相望，图中若有文字，则不得大于小四号，不得小于小五号）

荷兰***ITS……，见表2.1。（表序以章排序，尽量避免隔页相望）

图2-1 系统结构图（五号仿宋_GB2312加粗居中）

（由若干分图组成的插图，分图用a、b、c……标序，分图的图名以及图中各种代号的意义，以图注形式写在图题下方，先写分图名，另起行后写代号的意义。）

2.1.2 PDU格式

(三级标题:为小四号仿宋_GB2312，段前、段后间距0.5行)

2002年1月荷兰***ITS1月荷兰***ITS1月荷兰***ITS1月荷兰***ITS1月荷兰***ITS…….

3结论

（一级标题：为四号仿宋_GB2312加粗，段前、段后间距0.5行)

在论文的完成过程中，在论文的完成过程中，在论文的完成过程中，在论文的完成过程中，在论文的完成过程中，在论文的完成过程中。 附 录

（单独一页，四号仿宋_GB2312加粗居中，段前、段后间距0.5行)

[文章尾部最后500字内容到此结束,中间部分内容请查看底下的图片预览]

以上为《数据结构课程设计第九组》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。