数据结构大作业
数据结构大作业
题目： xxxx 校园导航介绍程序
姓名： 文中的xxx 可以换成自己的学校名称，然后再根据学校具体情况扩充一下。
学号：
班级：
时间：
学院：
实际问题阐述：
1:今年暑假留校时，我发现我们学校暑假有好多其他地方的高中生，初中生，小学生„„来我们学校参观，这应该算是高校旅游，景点开发.
2:同时也注意到，周末时也有一些人来参观。当然，各种讲座，各种辅导班，如考研班等，各种校外人来学校时，问路也是一种问题。
3:最重要的是，每年新生来报到时，一下子来学校，他们人生地不熟，虽然有很多同学充当志愿者，但是大量的人流，显然工作量是有限.
„„„„
考虑到这些实际问题，渐渐地发现，其实可以做一个xxx 的校园介绍程序，当然不能仅仅局限于地图的功能，可以加入相应的文本和图片介绍相应的建筑，介绍一下学校的历史等，考虑到程序的实用性和方便性，制作成手机程序，可以安装在手机上，这样可以提高其方便性，用java 编程，但是现在考虑知识水平有限，现在只能用c 或c++编程相应的初步程序，其实这部分主要用到数据结构的图的知识。
考虑到现在课程对图的知识讲解刚刚开始，而且图论的算法有点难，但是感觉具有实用价值，自己还是先大体构造个框架，自己学习一下相应的知识，从编程中学习！
抽象问题分析：
首先要用无向网表示xxxx 校园建筑的平面图设计图，在设计平面图中，用顶点表示主要建筑物，构建相应的结构体存放存放建筑物的编号、名称、简介，图片等信息，在图中的边表示建筑物之间的道路，存放两座建筑物的距离等信息。最终要求能够实现回答有xxxx 建筑物介绍、到相关建筑物的路径等问题。
程序的基本功能要求：
查询学校里面相应建筑物的相关信息 查询学校里面任意两座建筑物之间的最短路径 查询学校里面任意两做建筑物之间的所有路径 增加、删除、更新有关建筑物和相应道路的信息； 。 。 。
xxxxxx 平面图:
程序功能的实现过程：
程序主要涉及数据结构中有关图的存储和操作。
其实“查询学校里面相应建筑物的相关信息”和“增加、删除、更新有关建筑物和相应道路的信息”的难度不大，就是基本的查找，修改，更新等操作。
另外“查询学校里面任意两座建筑物之间的最短路径”是最短路问题，最短路书上有现成的算法Dijkstra 算法，Bellman-ford 算法和可以求各个顶点间最短路的Floyd-Warshall 算法；可以用这些算法实现
最难的感觉是“查询学校里面任意两做建筑物之间的所有路径”这属于搜索类问题，可以用深度优先和广度优先，本试验中定义为 bfs （）广搜，和dfs （）深搜，刚开始我一直没想好怎么用bfs （）控制结束，所有就用dfs （）回溯法实现了！后来想想广搜也可以控制只要想到，最多的长度是n-1就可以了（没有重复走一条路，否则将是无穷种可能）！
那用什么存储图呢？考虑到我们学校校园建筑物不多，所以v 肯定不多，而校园中的路肯定多，所以是个v 少的稠密图，所以用邻接矩阵！本人对c++比较熟，就用了vector 代替数组来实现可变容量的数组！
上面虽然把每个要求都想好了，可是到具体实现是又遇到很多的难题： 比如要求求最短路我该用那个算法呢，是单源最短路的Dijkstra 还是一劳永逸的Floyd-Warshall 呢！从实际出发，考虑到这个导游程序查询最多的就是某两点间的最短了，而且顶点间的道路很少变化，就选了Floyd-Washall 了。（但是后来实现顶点的删除和增加时又感觉这样也不是很妥当，不过实际上道路的修改肯定不会频繁的！）
定义的部分操作：
输入格式：
第一行两个整数n m ；分别表示建筑物的个数和道路的个数；
接着n 行每行包含三个数据：顶点编号 x，建筑物名称 xxx，建筑物简介 xxxxxxxx; 其中x 为整型,xxx 及xxxxxx 为字符串
再接下来m 行每行包含三个整型数据: a b cost a,b表示顶点标号,cost 为道路的长度
之后的是对这个无向网的操作:
目前暂时只定义三种操作
check all //查看所有的节点信息
check id //察看顶点id 的信息
min a b //察看建筑物a b之间的最短路径
all a b //察看 a b 之间的所有路径
update a 顶点编号 a，建筑物名称 xxx，建筑物简介 xxxxxxxx//更新a 建筑物的信息
deleteid a //删除a 节点
end // 终止操作
输出格式:
对于 checkall 要求输出所有建筑物的 名称 简介
对于 check id 要求输出id 景点的 名称 简介
对于 min a b 要求输出 路径的长度和途径的顶点;
对于 all a b 要求输出 路径的长度和途径的顶点; 每个路径独占一行 对于 deleteid a 输出id 建筑物的 名称 简介 delete successfully !! 对于 update a a xxx xxxxxxxxx 输出 a updatesuccessfully !! 对于 end 结束操作
struct node{
int id;
char name[20];
char info[50];
};
vector vex;
int map[Max_Vex][Max_Vex];
int path[Max_Vex][Max_Vex];
int each_cost[Max_Vex][Max_Vex];
int n,m;//顶点个数和边的个数；
int vexnum;//实际的大小
int min(int a,int b,int cost);//a b 的最短路径
int check(int a);//返回a 顶点的信息
void dfs(int x,int cost,int b);//深搜
int all(int a,int b);//输出a b间的所有路径
void Floyd_Washall();//求各个点最短路径
int update(int a);//更新节点信息
int validnum();//检测输入的是否为数字
int deleteid(int a);//删除顶点a
int help();//帮助命令
编译环境：
Vc6.0
用c++编译
大体流程图：
程序源代码：
#include
#include
#include
#define Max_Vex 100
#define MaxNum 0x7ffffff
using namespace std;
struct node{
int id;
char name[20];
char info[50];
};
vector vex;
int map[Max_Vex][Max_Vex];
int path[Max_Vex][Max_Vex];
int each_cost[Max_Vex][Max_Vex];
int n,m;//顶点个数和边的个数；
int vexnum;//实际的大小
int min(int a,int b,int cost);//a b 的最短路径
int check(int a);//返回a 顶点的信息
void dfs(int x,int cost,int b);//深搜
int all(int a,int b);//输出a b间的所有路径
void Floyd_Washall();//求各个点最短路径
int update(int a);//更新节点信息
int validnum();//检测输入的是否为数字
int deleteid(int a);//删除顶点a
int help();//帮助命令
int main()
{
int j,i,a,b,cost;
node t;
system("cls");
system("mode con:cols=40 lines=20");
system("color 4f");
scanf("%d%d",&n,&m);
for(i=0;i
for(j=0;j
each_cost[i][j]=map[i][j]=MaxNum;
}
}
vexnum = n;//
vex.push_back(t);
for(i=0;i
scanf("%d%s%s",&t.id,t.name,t.info);
vex.push_back(t);
}
for(i=0;i
scanf("%d%d%d",&a,&b,&cost);//利用邻接矩阵存储
map[a][b] = map[b][a] = cost;
//each_cost[a][b] = each_cost[b][a] =cost;
}
//floyd求各个点之间的最短路径保存在each_cost中
Floyd_Washall();
//路径保存在path 中
char str[20];
do{//功能菜单
scanf("%s",str);
if(strcmp(str,"check")==0){a=validnum();if(a!=-1)check(a);} else if(strcmp(str,"cls")==0){system("cls");}
else if(strcmp(str,"help")==0){help();}
else
if(strcmp(str,"update")==0){a=validnum();if(a!=-1)update(a);} else if(strcmp(str,"deleteid")==0)
{a=validnum();if(a!=-1)deleteid(a);}
else if(strcmp(str,"checkall")==0){for(i=1;i
{scanf("%d%d",&a,&b);min(a,b,each_cost[a][b]);}
else if(strcmp(str,"all")==0){scanf("%d%d",&a,&b);all(a,b);} else if(strcmp(str,"end")==0){break;}
else{printf("error input!!!\nyou can type 'help' for detail!!\n");}
}while(1);
return 0;
}
int help()
{
cout
return 0;
}
int validnum()
{//若输入的是数字则返回数字，其他为非法输入，返回-1；
char str[10];
scanf("%s",str);
if(isdigit(str[0])) return atoi(str);
else printf(" error input!!\n");
return -1;
}
int deleteid(int a)
{
for(int i=1;i
for(i=1;i
//n--;
Floyd_Washall();
vexnum--;
check(a);
printf("delete successfully!!!\n");
vex[a].id = -1;
//vex.erase(vex.begin()+a);
return 0;
}
int update(int a)
{
node t;
scanf("%d%s%s",&t.id,t.name,t.info);
vex[a] = t;
return 0;
}
int min(int a,int b,int cost)
{
int i=path[b][a];
printf("%d-->",a);
while(i!=b) {
printf("%d-->",i);
i=path[b][i];
}
printf("%d cost %d\n",b,cost);
return 0;
}
int check(int a)
{
if(vex[a].id!=-1){
printf("%d%s%s\n",vex[a].id,vex[a].name,vex[a].info); return 1;
}
//else printf("%d isn't in!\n",a);
return -1;
}
int p[Max_Vex];
int used[Max_Vex];
void dfs(int x,int cost,int b)
{
p[p[0]++] = x;//x加入路径；
if(x==b){//找到一条路径则输出
for(int i=1;i
printf("%d-->",p[i]);
printf("%d cost %d\n",p[i],cost);
return ;
}
for(int j = 1;j
if(map[x][j]!=MaxNum&& !used[x]){//x到j 有路，并且x 到j 没走过 cost+=map[x][j];//记录总的花费
used[x] = 1;//标记已走
dfs(j,cost,b);
p[0]--;//去掉j
cost-=map[x][j];//恢复
used[x] = 0;//恢复
}
}
}
int all(int a,int b)
{
p[0] = 1;
memset(used,0,sizeof(used));
dfs(a,0,b);//利用深搜找所有路径；
return 0;
}
void Floyd_Washall()
{
int i,j,k;
for(i=1;i
for (j=1;j
each_cost[i][j] = map[i][j];
path[i][j]=i;
}
}
for(i=1;i
each_cost[i][i]=0;
path[i][i]=0;
}
for(k=1;k
for(i=1;i
for(j=1;j
if(each_cost[i][j]>each_cost[i][k]+each_cost[k][j]) {
each_cost[i][j]=each_cost[i][k]+each_cost[k][j]; path[i][j]=path[k][j];
}
}
参考资料：
1， visual c++6.0程序设计与开发技术大全 2， c++大学基础教程
3， 数据结构（清华大学出版社）