初学请多指教
一．实验内容
1.地图导航
2查看个点及其信息
3修改一个点相关信息
4.增加一个点及信息
5.增加路线
6.删减路线
7.删减一个点
8.输出点
9.输出边
二．实验目的
1．掌握图的邻接矩阵的存储定义；
2．了解图的最短路径（Dijsktra）算法的实现。
三. 需求分析
设计xx大学的校园平面图，所含景点不少于8个。以图中顶点表示学校内各景点，存放景点的名称、景点介绍信息等；以边表示路径，存放路径长度信息。要求将这些信息保存在文件graph.txt中，系统执行时所处理的数据要对此文件分别进行读写操作。
（1）由于本实验主要关于图的操作，所以对图的点名会进行字符串的输入，图的长度也需要数字的输入，保证点的个数不超过200。输入格式为 spot distance spot。
（2）输出形式点名已遍历数组输出，边长以邻接矩阵输出。
（3）地图导航，对地图信息的修改。
四 概要设计
此实验采用邻接矩阵，节点第一如下：
struct verType{
char info[512];
char name[100];
};
using namespace std;
struct graph
{
verType vertex[100];
int arc[100][100];
int vexnum, arcnum;
};
使用函数封装将函数功能化，函数除实验内容所提及的之外还包括地图信息初始化（对文件信息的读取），最短路径函数，主函数。函数的整合主要是先把地图初始化，再用分支语句把数据的输入与各个函数相连接。另外最短路径函数被地图导航调用
五．详细设计
void initmap(graph &g）
对文件信息的读入，构造一个邻接矩阵。
int locate(graph &g, char vname[])
找出点在 vexs数组中的位置并返回。
void check(graph &g)
输入店名的主关键字，找出与点名匹配所在info数组的信息，并输出。
void Dijkstra(graph &G, int v, int path[], int dist[])
v为点名，返回一个到v的最近点，保存在path数组中。
void track(graph &g）
通过最短路径函数的相匹配，可以实现地图导航，输入目的点，逆序输出path数组，知道遍历出出发点
void addspot(graph &g)
添加一个点，将信息和点名从键盘输入，添加到vertex数组中，但不改变arc数组的信息。
void addways(graph &g)
添加路线，操作前先从键盘输入添加路线的个数，在输入两个点名及之间的距离，在通过 locate函数返回点的位置，在邻接矩阵中直接将distance给赋值。
void delspot(graph &g)
删除一个点，将vertex数组中将与点名相匹配的位置信息找出，通过顺序表的删除删除该位置上的点。
void delways(graph &g)
删除路线，操作前从键盘中输入你想删除路线个数，再从点名找出在arc数组中的位置上。用100赋值。
void modify(graph &g)
在实行修改操作前，先选择修改点还是路线，从键盘输入修改信息直接赋值。
六．调试分析
文件的读入，该文件要和代码文件放在同一体路径下，还有fstream的操作，比用指针操作更为简便，通过在arc数组中建立了一个邻接矩阵，可以直观的看出路径在地图的体现。
本实验用两个数组实现点和边,通过locate将两数组连接，时间复杂度为o(n)。
函数封装将各个功能与输入相结合，通过对0-9的输入实现各个函数功能。
八．实验总结
有了第一次实验的基础，这次实验的难点在数据收集，对数据的读入，还有邻接矩阵的创立，其余的所谓线路修改也就是在文件初始化上的附加题吧。也就是邻接矩阵相对简单。
附代码
#include
#include
#include
#include
#include
#include
struct verType{
char info[512];
char name[100];
};
using namespace std;
struct graph
{
verType vertex[100];// 存放图中顶点的数组
int arc[100][100];// 存放图中边的数组
int vexnum, arcnum;// 图中顶点数和边数
};
void initmap(graph &g);
void outspot(graph &g);
int locate(graph &g, char vname[])
{
for (int i = 0; i < g.vexnum; i++)
{
if (strcmp(g.vertex[i].name, vname) == 0) return i;
}
return -1;
}
void initmap(graph &g){
ifstream in;
if(! in) cout<<"can not find the file"<
in>>g.arcnum;in>>g.vexnum;
for(int i=0;i
//for(int i=0;i
for(int i=0;i<20;i++){
for(int j=0;j<20;j++){g.arc[i][j]=100;}}
char v1[200], v2[200];
int dis=0;
for (int i = 0; i
in>>v1;in>>v2,in>>dis;
int s1 = locate(g, v1);
int s2 = locate(g, v2);
g.arc[s1][s2] = dis;
g.arc[s2][s1] = dis;
}
}
void check(graph &g){
printf("-----------------2查看一个点及其信息--------------------n");
int a;
cout<<"spot:";cin>>a;
cout<
void Dijkstra(graph &G, int v, int path[], int dist[])
{
//最短路径算法.；路线查询
int s[100]; // 已找到最短路径的点的集合
bool Final[100]; //Final[w]=1表示求得顶点V0至Vw的最短路径
// 初始化distpath: path[i] 存放 到i的前驱结点编号, -1表示没有
for (int i = 0; i < G.vexnum; i++)
{
Final[i] = false;
dist[i] = G.arc[v][i];
if (dist[i] != 100)
{
path[i] = v;
}
else
{
path[i] = -1;
}
}
s[0] = v; // 初始化s
Final[v] = true;
int num = 1;
while (num < G.vexnum)
{
// 在dist中查找最小值元素
int k = 0, min = 100;
for (int i = 0; i < G.vexnum; i++)
{
if (i == v)
continue;
if (!Final[i] && dist[i] < min)
{
k = i;
min = dist[i];
}
}
s[num++] = k; // 将新生成的结点加入集合s
Final[k] = true;
// 修改dist和path数组
for (int i = 0; i < G.vexnum; i++)
{
if (!Final[i] && dist[i] > dist[k] + G.arc[k][i])
{
dist[i] = dist[k] + G.arc[k][i];
path[i] = k;
}
}
}
}
void track(graph &g){
printf("-----------------1.地图导航-----------------------------n");
int v ,path[100],map[100]={0},i,e,z=0,dist[100];
cout<<"start:"<
if(v<0||v>g.vexnum){printf("ninput:t");cin>>v;}
cout<<"end:"<
if(v<0||v>g.vexnum||v==e){printf("ninput:t");cin>>e;}
Dijkstra(g,v,path,dist);
map[z]=e;
while (path[e]!=v){
map[++z]=path[e];
e=path[e];
}
map[++z]=v;
printf("%s",g.vertex[map[z]].name);
while(z!=0) printf("-->%s",g.vertex[map[--z]].name);
printf("n");
}
void addspot(graph &g)
{
printf("-----------------4.增加一个点及信息---------------------n");
cout<<"spot:";
cin>>g.vertex[(++g.vexnum)-1].name;
printf("information:");
cin>>g.vertex[g.vexnum-1].info;
outspot(g);
}
void addways(graph &g){
printf("-----------------5.增加一条路线-------------------------n");
int dis=0,v,v1,v2;
cout<<"ways:";cin>>v;
cout<
cin>>v1>>dis>>v2;
int s1 = locate(g,g.vertex[v1].name);
int s2 = locate(g,g.vertex[v2].name);
g.arc[s1][s2] = dis;
g.arc[s2][s1] = dis;
g.arcnum++;
}
}
void delspot(graph &g){
printf("-----------------7.删减一个点---------------------------n");
int a;
cout<<"spot：";
cin>>a;
while(a<0||a>=g.vexnum)cout<
g.vexnum--;
outspot(g);
}
void delways(graph &g){
printf("-----------------6.删减一条路线-------------------------n");
int a,v1,v2,dis;
cout<<"ways:";cin>>a;
cout<<"route:spottspot"<
cin>>v1>>v2;
int s1 = locate(g, g.vertex[v1].name);
int s2 = locate(g,g.vertex[v2].name);
g.arc[s1][s2] = 100;
g.arc[s2][s1] = 100;
if(s1==s2) g.arcnum--;
else g.arcnum-=2;
}
}
void modify(graph &g){
printf("-----------------3.修改一个点相关信息-------------------n");
int a,b;
cout<<"spot:";cin>>a;
while(a<0||a>g.vexnum){
cout<
}
cout<<"modify spot:1tmodify information:2"<
while(b<1||b>2){
cout<<"modify spot:1tmodify information:2"<
}
if(b==1){
cout<
}
if(b==2){
cout<
}
outspot(g);
}
void outspot(graph &g){
for(int i=0;i
void outarc(graph &g){
for(int i=0;i
for(int j=0;j
}
}
void menu()
{
//功能菜单的实现
printf("---------------xx大学导航图-------------n");
printf("-----------------1.地图导航-----------------------------n");
printf("-----------------2查看一个点及其信息--------------------n");
printf("-----------------3.修改一个点相关信息-------------------n");
printf("-----------------4.增加一个点及信息---------------------n");
printf("-----------------5.增加一条路线-------------------------n");
printf("-----------------6.删减一条路线-------------------------n");
printf("-----------------7.删减一个点---------------------------n");
printf("-----------------8.输出点-------------------------------n");
printf("-----------------9.输出边-------------------------------n");
printf("-----------------0.退出系统-----------------------------n");
}
void main()
{
graph g;
initmap(g);
int a;
menu();
outspot(g);
cout<<"menu:";
cin>>a;
while(a!=0){
switch(a){
case 1:track(g);break;
case 2:check(g);break;
case 3:modify(g);break;
case 4:addspot(g);break;
case 5:addways(g);break;
case 6:delways(g);break;
case 7:delspot(g);break;
case 8:outspot(g);break;
case 9:outarc(g);break;
case 0:break;
default:cout<<"wrong date"<
cout<<"menu:";cin>>a;
}
}
