校园导航问题.docx
《校园导航问题.docx》由会员分享，可在线阅读，更多相关《校园导航问题.docx（26页珍藏版）》请在冰点文库上搜索。
校园导航问题
实验七校园导航问题
一．需求分析
设计你的学校的平面图，至少包括10个以上的景点（场所），每两个景点间可以有不同的路，且路长也可能不同，找出从任意景点到达另一景点的最佳路径（最短路径）。
要求：
（1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。
（4）修改景点信息。
实现提示：
一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。
顶点和边均含有相关信息。
二．设计
2.1设计思想
（1）数据结构设计（包括逻辑结构设计和存储结构设计）
1.创建有向图G，在空图G中插入n个顶点和e条边。
并实现最短路径算法。
2.定义邻接矩阵实现图的存储类型定义。
用来保存景点的数据信息，如景点间的距离。
3.定义结构体数组实现景点信息的保存，如景点名称等
（2）算法设计
1.根据景点信息建立临接矩阵
2.调用Dijkstra求出两景点的最短路径
3.建立结构体数组存储数据
4.将修改的信息直接写入数组中
2.2设计表示
（1）函数调用关系图
主函数main（）依次调用以下个函数
#include"AdjMGraph.h"
#include"Dijkstra.h"
（2）函数接口规格说明
调用库函数为
#include
#include
#include
调用自定义函数为
#include"AdjMGraph.h"
#include"Dijkstra.h"
各函数说明
voidListInitiate（SeqList*L）/*初始化顺序表L*/
intListLength（SeqListL）/*返回顺序表L的当前数据元素个数*/
intListInsert（SeqList*L,inti,DataTypex）
intListDelete（SeqList*L,inti,DataType*x）
/*删除顺序表L中位置为i（0<=i=size-1）的数据元素并存放到x中*/
/*删除成功返回1，删除失败返回0*/
intListGet（SeqListL,inti,DataType*x）
/*取顺序表L中第i个数据元素存于x中，成功返回1，失败返回0*/
voidDijkstra（AdjMGraphG,intv0,intdistance[],intpath[]）最短路径算法
//置带权有向图G为空图
voidGraphInitiate（AdjMGraph*G）
//判断顶点vertex是否是有向图G的顶点，是则返回顶点在顶点顺序表中的序号，否则返回-1。
intIsVertex（AdjMGraph*G,DataTypevertex）
//在带权有向图G中插入顶点vertex。
如果图中已经有顶点vertex,则图不变
voidInsertVertex（AdjMGraph*G,DataTypevertex）
/*在带权有向图G中插入一条第v1个顶点指向第v2个顶点，权值为weight的有向边。
*如果v1和v2有一个不是图中的顶点，则图不变；如果v1和v2相等，则图不变。
*如果图已经包含该边，则边的权值更改为新的权值，时间复杂度:
O
（1）。
*/
voidInsertEdge（AdjMGraph*G,intv1,intv2,intweight）
//判断第v1个顶点到第v2个顶点的边是否是有向图G的边，是则返回1，否则返回0.时间复杂度O
（1）。
intIsEdge（AdjMGraph*G,intv1,intv2）
/*在带权有向图G中删除一条第v1个顶点指向第v2个顶点的有向边。
*如果v1和v2有一个不是图中的顶点，则图不变；如果v1和v2相等，则图不变。
*如果不是图的边，则图不变。
时间复杂度:
O
（1）。
*/
voidDeleteEdge（AdjMGraph*G,intv1,intv2）
//在带权有向图G中取第v个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该顶点在顶点顺序表的序号，否则返回-1.时间复杂度:
O（n）。
intGetFirstVex（AdjMGraphG,intv）
//创建有向图G，通过在空图G中插入n个顶点和e条边实现。
时间复杂度:
O（n^2+e）。
voidGraphCreat（AdjMGraph*G,DataTypev[],intn,RowColWeightW[],inte）
2.3详细设计
（1）数据结构设计（包括逻辑结构设计和存储结构设计）
（2）算法设计
基本数据结构为：
typedefstruct
{
DataTypelist[MaxSize];
intsize;
}SeqList;
/////初始化顺序表
voidListInitiate（SeqList*L）/*初始化顺序表L*/
{
L->size=0;
}
intListLength（SeqListL）/*返回顺序表L的当前数据元素个数*/
{
returnL.size;
}
intListInsert（SeqList*L,inti,DataTypex）
/*在顺序表L的第i（0<=i=size）个位置前插入数据元素值x*/
/*插入成功返回1，插入失败返回0*/
{
intj;
if（L->size>=MaxSize）
{
printf（"顺序表已满无法插入!
\n"）;
return0;
}
elseif（i<0||i>L->size）
{
printf（"参数i不合法!
\n"）;
return0;
}
else
{
/*为插入做准备*/
for（j=L->size;j>i;j--）
L->list[j]=L->list[j-1];
L->list[i]=x;
L->size++;//元素个数加1
return1;
}
}
intListDelete（SeqList*L,inti,DataType*x）
/*删除顺序表L中位置为i（0<=i=size-1）的数据元素并存放到x中*/
/*删除成功返回1，删除失败返回0*/
{
intj;
if（L->size<=0）
{
printf（"顺序表已空无数据元素可删!
\n"）;
return0;
}
elseif（i<0||i>L->size-1）
{
printf（"参数i不合法!
\n"）;
return0;
}
else
{
*x=L->list[i];/*保存删除的元素到x中*/
/*依次前移*/
for（j=i+1;j<=L->size-1;j++）
L->list[j-1]=L->list[j];
L->size--;//元素个数减1
return1;
}
}
intListGet（SeqListL,inti,DataType*x）
/*取顺序表L中第i个数据元素存于x中，成功返回1，失败返回0*/
{
if（i<0||i>L.size-1）
{
printf（"参数i不合法!
\n"）;
return0;
}
else
{
*x=L.list[i];
return1;
}
}
基本函数为
Dijkstra算法
算法具体步骤
（1）初始时，S只包含源点，即S=，v的距离为0。
U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。
（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（uU）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
（4）重复步骤
（2）和（3）直到所有顶点都包含在S中
三．调试分析
Dijkstra算法思想为：
设G=（V,E）是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径,就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。
在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。
此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
空间复杂度度
Dijkstra算法的时间复杂度为O（n^2）
空间复杂度取决于存储方式，邻接矩阵为O（n^2）
四．用户手册
1.首先选择要进行的操作
2选1、2、3、4分别为查询景点信息、问路查询、修改景点信息、退出。
3.选1输入景点代号即可进行信息查询。
4.选2输入两景点代号即可进行问路查询。
并输出最短路径长度以及两路径的景点。
4.选3输入景点代号即可进行修改。
5选4退出
五．测试数据及测试结果
六．源程序清单
typedefstruct
{
DataTypelist[MaxSize];
intsize;
}SeqList;
/////初始化顺序表
voidListInitiate（SeqList*L）/*初始化顺序表L*/
{
L->size=0;
}
intListLength（SeqListL）/*返回顺序表L的当前数据元素个数*/
{
returnL.size;
}
intListInsert（SeqList*L,inti,DataTypex）
/*在顺序表L的第i（0<=i=size）个位置前插入数据元素值x*/
/*插入成功返回1，插入失败返回0*/
{
intj;
if（L->size>=MaxSize）
{
printf（"顺序表已满无法插入!
\n"）;
return0;
}
elseif（i<0||i>L->size）
{
printf（"参数i不合法!
\n"）;
return0;
}
else
{
/*为插入做准备*/
for（j=L->size;j>i;j--）
L->list[j]=L->list[j-1];
L->list[i]=x;
L->size++;//元素个数加1
return1;
}
}
intListDelete（SeqList*L,inti,DataType*x）
/*删除顺序表L中位置为i（0<=i=size-1）的数据元素并存放到x中*/
/*删除成功返回1，删除失败返回0*/
{
intj;
if（L->size<=0）
{
printf（"顺序表已空无数据元素可删!
\n"）;
return0;
}
elseif（i<0||i>L->size-1）
{
printf（"参数i不合法!
\n"）;
return0;
}
else
{
*x=L->list[i];/*保存删除的元素到x中*/
/*依次前移*/
for（j=i+1;j<=L->size-1;j++）
L->list[j-1]=L->list[j];
L->size--;//元素个数减1
return1;
}
}
intListGet（SeqListL,inti,DataType*x）
/*取顺序表L中第i个数据元素存于x中，成功返回1，失败返回0*/
{
if（i<0||i>L.size-1）
{
printf（"参数i不合法!
\n"）;
return0;
}
else
{
*x=L.list[i];
return1;
}
}
#include"SeqList.h"
//邻接矩阵实现图的存储类型定义
typedefstruct
{
SeqListvertices;//存放顶点的顺序表
intedge[MaxVertices][MaxVertices];//存放边的邻接矩阵
intnumOfEdges;//边的数目
}AdjMGraph;//图的结构体定义
typedefstruct
{
introw;//行下标
intcol;//列下标
intweight;//权值
}RowColWeight;//边信息结构体定义
structmassages
{
charname[20];
intnum;
intcen;
}massage[10]={{"教一楼",50,7},{"教二楼",50,7},{"教三楼",50,7},{"主楼",50,7},{"图书馆",50},{"北一楼",50,7},{"北二楼",50,7},{"北三楼",50,7},{"北综",50,7},{"北区图书馆",50,7}};
//置带权有向图G为空图，时间复杂度:
O
（1）。
voidGraphInitiate（AdjMGraph*G）
{
inti,j;
for（i=0;ifor（j=0;j{
if（i==j）G->edge[i][j]=0;
elseG->edge[i][j]=MaxWeight;//MaxWeight表示权值无穷大
}
G->numOfEdges=0;//边的条数置为0
ListInitiate（&G->vertices）;//顶点顺序表初始化
}
intIsVertex（AdjMGraph*G,DataTypevertex）
{
inti;
for（i=0;ivertices.size;i++）
{
if（G->vertices.list[i]==vertex）
{
break;
}
}
if（i==G->vertices.size）
return-1;
else
returni;
}
voidInsertVertex（AdjMGraph*G,DataTypevertex）
{
if（IsVertex（G,vertex）<0）
if（ListInsert（&G->vertices,G->vertices.size,vertex）==0）//在顶点顺序表的表尾插入顶点vertex
{
printf（"插入顶点时空间已满无法插入！
"）;
exit
（1）;
}
}
voidInsertEdge（AdjMGraph*G,intv1,intv2,intweight）
{
DataTypex;
if（v1!
=v2）
{
if（（ListGet（G->vertices,v1,&x）==0）||（ListGet（G->vertices,v2,&x）==0））
{
printf（"插入边时参数v1和v2越界出错！
\n"）;
exit
（1）;
}
G->edge[v1][v2]=weight;
G->numOfEdges++;
}
}
intIsEdge（AdjMGraph*G,intv1,intv2）
{
DataTypex;
if（（ListGet（G->vertices,v1,&x）==0）||（ListGet（G->vertices,v2,&x）==0））
{
printf（"边的参数v1和v2越界出错！
\n"）;
return0;
}
if（G->edge[v1][v2]==MaxWeight||v1==v2）
{
printf（"该边不存在！
\n"）;
return0;
}
return1;
}
voidDeleteEdge（AdjMGraph*G,intv1,intv2）
{
if（IsEdge（G,v1,v2）==0）
{
printf（"删除边时出错！
"）;
exit
（1）;
}
else
{
G->edge[v1][v2]=MaxWeight;
G->numOfEdges--;
}
}
//计算带权有向图G中第v个顶点的入度，时间复杂度:
O（n）。
intInDegree（AdjMGraph*G,intv）
{
//在此插入你第二步的代码，替换掉下面的语句
intdin=0,j;
for（j=0;jvertices.size;j++）
{
if（G->edge[v][j]!
=0&&G->edge[v][j]!
=MaxWeight）
din++;
}
returndin;
}
//计算带权有向图G中第v个顶点的出度，时间复杂度:
O（n）。
intOutDegree（AdjMGraph*G,intv）
{
//在此插入你第二步的代码，替换掉下面的语句
intdou=0,j;
for（j=0;jvertices.size;j++）
{
if（G->edge[j][v]!
=0&&G->edge[v][j]!
=MaxWeight）
dou++;
}
returndou;
}
//计算带权有向图G中第v个顶点的度，时间复杂度:
O（n）。
intDegree（AdjMGraph*G,intv）
{
return（InDegree（G,v）+OutDegree（G,v））;
}
//在带权有向图G中删除第v个顶点，时间复杂度:
O（n^2）。
voidDeleteVertex（AdjMGraph*G,intv）
{
//在此插入你第一步的代码
intj=0,i;
if（v>G->vertices.size）
{
printf（"参数v出错！
\n"）;
return;
}
for（j=v;jvertices.size;j++）
{
for（i=0;ivertices.size;i++）
{
G->edge[j][i]=G->edge[j][i+1];
}
}
for（j=v;jvertices.size-1;j++）
{
for（i=0;ivertices.size;i++）
{
G->edge[i][j]=G->edge[i+1][j];
}
}
for（j=v;jvertices.size-1;j++）
G->vertices.list[j]=G->vertices.list[j+1];
G->vertices.size--;
}
//在带权有向图G中取第v个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该顶点在顶点顺序表的序号，否则返回-1.时间复杂度:
O（n）。
intGetFirstVex（AdjMGraphG,intv）
{
intcol;DataTypex;
if（ListGet（G.vertices,v,&x）==0）
{
printf（"取第一个邻接顶点时参数v越界出错！
\n"）;
exit
（1）;
}
//寻找邻接矩阵v行中从最左开始第一个值非零且非无穷大的权值对应的顶点
for（col=0;colif（G.edge[v][col]>0&&G.edge[v][col]returncol;
return-1;
}
//在带权有向图G中取第v1个顶点的继邻接结点第v2个顶点之后的下一个邻接结点,时间复杂度:
O（n）。
intGetNextVex（AdjMGraphG,intv1,intv2）
{
intcol;DataTypex;
if（（ListGet（G.vertices,v1,&x）==0）||（ListGet（G.vertices,v2,&x）==0））
{
printf（"取下一邻接顶点时参数v1和v2越界出错！
\n"）;
exit
（1）;
}
if（G.edge[v1][v2]==0）
{
printf（"v2不是v1的邻接顶点\n"）;
exit
（1）;
}
//寻找邻接矩阵v行中从第v2+1列开始的第一个值非零且非无穷大的权值对应的顶点
for（col=v2+1;colif（G.edge[v1][col]>0&&G.edge[v1][col]returncol;
return-1;
}
//创建有向图G，通过在空图G中插入n个顶点和e条边实现。
时间复杂度:
O（n^2+e）。
voidGraphCreat（AdjMGraph*G,DataTypev[],intn,RowColWeightW[],inte）
{
inti,k;
GraphInitiate（G）;
for（i=0;iInsertVertex（G,v[i]）;
for（k=0;kInsertEdge（G,W[k].row,W[k].col,W[k].weight）;
}
voidDijkstra（AdjMGraphG,intv0,intdistance[],intpath[]）
{
intn=G.vertices.size;
int*s=（int*）malloc（sizeof（int）*n）;
intminDis,i,j,u;
for（i=0;i{
distance[i]=G.edge[v0][i];
s
升级会员 