发布时间 : 星期二 文章数据结构课程设计论文(手机通讯录管理系统,最佳旅游路线规划问题,图书租借管理问题)更新完毕开始阅读4a02b052ce2f0066f533228f
附录
源程序清单 //3.h
#include
#define INFINITY 100 //最大值
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef struct{
char city[MAX_VERTEX_NUM][10]; int cout;
}Path; //用于储存路径
typedef struct{
char vexs[MAX_VERTEX_NUM][10]; //顶点信息 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 } MGraph; //采用数组表示法的图的结构体 int LocateVex(MGraph &G,char city[]){ int i;
for(i=0;i if(strcmp(G.vexs[i],city)==0) return i; if(i==G.vexnum) return -1; } //定位城市在邻接表中的位置 void print(MGraph G) { int i,j; printf(\图的邻接矩阵为：\\n\ for(i=0;i for(j=0;j printf(\if((j+1)%7==0) printf(\ 29 printf(\ } //输出邻接矩阵 void CreateGraph(MGraph &G) {printf(\涉及城市为：\\n\ FILE *fp; if((fp=fopen(\ } int i,j,k,w; char city1[10],city2[10]; fscanf(fp,\读入城市的数量以及城市之间路径的总数 for(i=0;i for(i=0;i void Dijkstra(MGraph G,char city[]) //用迪杰斯塔拉算法求最短路径 { int i,v,w,min,v0; int D[MAX_VERTEX_NUM]={0}; //带权路径长度 int final[MAX_VERTEX_NUM]={0}; //建立一数组，并将所有值置为0，方便后续置换有最短路径的结点 Path path[MAX_VERTEX_NUM]={0}; //path[v]中储存着从v0到v当前求得最短路径上的顶点信息 for(j=0;j G.arcs[i][j]=INFINITY; for(k=0;k fscanf(fp,\ //输入一条边依附的顶点和权值 i=LocateVex(G,city1); //确定顶点位置 j=LocateVex(G,city2); G.arcs[i][j]=G.arcs[j][i]=w; //给弧赋值 printf(\读入信息出错\\n\ 30 if((v0=LocateVex(G,city))==-1) { for(v=0;v final[v0]=1; //初始化，将主函数输入的城市的标志置为1，即加入集合Q printf(\起始点 终止点 旅行时间 路径 \\n\\n\ //开始主循环，每次求得v0到某个v顶点的最短路径，并输出最短路径 for(i=1;i min=INFINITY; //当前的最短路径为最大值 for(w=0;w if(!final[w]) if(D[w] {v=w;min=D[w];} //如果找到w顶点离v0顶点更近，则更改v和min D[v]=G.arcs[v0][v]; //从v0到v的路径长度 if(D[v] strcpy(path[v].city[path[v].cout++],city); strcpy(path[v].city[path[v].cout++],G.vexs[v]); printf(\图中无该点\\n\return; } //如果显示为-1，则图中无所输入的结点 } //将主函数输入的城市作为起始点 final[v]=1; printf(\for(w=0;w for(w=0;w if(!final[w]&&(min+G.arcs[v][w] D[w]=min+G.arcs[v][w]; path[w]=path[v]; 31 strcpy(path[w].city[path[w].cout++],G.vexs[w]); } } } //3.cpp #include MGraph G; char city[10]={'\\0'},ch[10],b; while(1) { CreateGraph(G); print(G); printf(\读取数据成功\\n\ printf(\请输入起始点：\ scanf(\ strcpy(city,ch); Dijkstra(G,city); } } 32