数据结构校园导游实验报告.doc

数据结构上机实验报告
厦门大学信息科学与技术学院计算机系
姓名:彭钰杰年级:2012 指导老师:陈锦绣
实验题目:校园导游
问题描述: 设计一个校园导游程序,为来访的客人提供各种信息查询服务。
数据结构设计: 因地点与地点之间道路为双向的,所以可看成是一个无向图,本程序采用邻接多重表结构储存,在个别子函数中转化为多维数组以便运算。
实验测试:
构造如下的图:
程序测试图:
主界面
景点道路修改和扩建(模拟地图也会随之更新)
道路导航系统
道路导航系统 2两点间所有路径
道路导航系统 3多地点的最佳路径
求关节点
景点清单
模拟地图
增添景点并为其添加道路数据后模拟地图随之更新
程序中并未加入自动检测输入是否错误的系统,模拟地图系统也会出现边界溢出的情况。
程序代码:
##include<>
#include<>
#include<>
#include <>
#include <>
char *heng="━",*shu="┃",*zuos="┏",*zuox="┗",*yous="┓",*youx="┛";
struct adjinfo //路信息
{
int len; //道路长度8
int category; // 道路类别 1:车道 2:人行道 3:观景路径
int dir; //方向 1表示i在j的西边,2表示i在j的北边,3表示i在j的西北边,。
};
struct adj //边结构体
{
int mark;
int ivex;
int jvex;
adj *ilink,*jlink;
adjinfo info;
};
typedef struct //地点结构体
{
char name[50];
char intro[50];
adj *firstedge;
}site;
typedef struct
{
site spot[50];
int spotnum,adjnum;
}graph;
void init(graph &t)//初始化图
{
=0;
=0;
}
void addsite(char* Name,char* Intro,graph &t)//添加地点
{
strcpy([].intro,Intro);
strcpy([].name,Name);
[].firstedge=NULL;
++;
}
void addadj(int i,int j,int length,int cate,int di,graph &t)//添加道路
{
adj *p1,*p2;
int mark;
p1=(adj*)malloc(sizeof(adj));
p1->ilink=NULL;p1->jlink=NULL;p1->ivex=i;p1->jvex=j;p1->mark=0;
p1->=cate;p1->=di;p1->=length;
p2=[i].firstedge;
if(p2==NULL)
[i].firstedge=p1;
else
{
mark=0;
while(mark==0)
{
if(p2->ivex==i&&p2->ilink==NULL)mark=1;
else if(p2->jvex==i&&p2->jlink==NULL)mark=2;
else if(p2->ivex==i)p2=p2->ilink;
else if(p2->jvex==i)p2=p2->jlink;
}
if(mark==1)
p2->ilink=p1;
else
p2->jlink=p1;
}
p2=[j].firstedge;
if(p2==NULL)
[j].firstedge=p1;
else
{
mark=0;
while(mark==0)
{
if(p2->ivex==j&&p2->ilink==NULL)mark=1;
else if(p2->jvex==j&&p2->jlink==NULL)mark=2;
else if(p2-