数据结构实验报告(校园导游咨询)

软件学院学生实验报告册实验课程名称：数据结构与算法实验项目名称：校园导游咨询实验类型（打√）：（基础、综合、设计√）院系：信息工程学院计算机系专业：*****姓名：***学号：*****指导老师：***软件学院教务处编制一、实验预习报告内容预习日期：2010年6月19日实验预习报告内容原则上应包括实验目的、实验所用的主要仪器药品、实验原理与公式、实验预习疑问等项目。【实验目的】熟悉图的各种存储结构及其构造、遍历算法，掌握各种图的应用算法，如求最短路径等。【需要分析】设计一个校园导游程序，为来访的客人提供各种信息查询服务。要求学校所含景点不少于10个，图中顶点表述景点，边表示景点间的路径。【软件平台】Windows2000，VisualC＋＋6.0或WINTC【概要设计】ADTArray{数据对象:V是具有相同特性的数据元素的集合，称为顶点集。数据关系:Graph=(V,R),其中，VR＝{<v,w>|v,w∈V且P(v,w)}<v,w>表示从v到w的一条弧，并称v为弧头，w为弧尾。谓词P(v,w)定义了弧<v,w>的意义或信息。基本操作：CreatGraph(&G,V,VR)；//按定义(V,VR)构造图DestroyGraph(&G)；//销毁图LocateVex(G,u);//若G中存在顶点u，则返回该顶点在图中“位置”；则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。FirstAdjVex(G,v);//返回v的“第一个邻接点”。若该顶点在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w的）“下一个邻接点”。//若w是v的最后一个邻接点，则返回“空”。InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。InsertArc(&G,v,w);//在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>。DeleteArc(&G,v,w);//在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>。DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。}ADTArray【疑问】（这部分内容因人而异，也可不写）实验预习评分：二、实验原始（数据）记录实验时间：2007年6月20日（星期三第7，8节）实验同组人：如有实验实验数据表格，学生在实验预习时应画好实验数据表格，供实验填写数据。软件学院校园平面图＿＿＿13体育馆--14音乐楼｜(20)(5)｜(15)12游泳场15北区宿舍区-16第一饭堂(30)/｜(30)｜11信息工程学院______(200)______________(50)｜｜(50)｜\/(20)｜｜(50)18青年湖－17理工楼－－－-----1学校正门/\|/(120)\10英东生物工程学院|(50)19黎灿活动中心\|\|/(30)|(300)|(80)\(100)/－－4西教学楼－2行政楼－－3东教学楼||\/|(20)(20)\||8图书馆\(120)|(30)\|(150)|/\__7第四饭堂\(70)||//\||(200)//\6第三饭堂|//\/(30)9西区宿舍区/___(250)____/5南区宿舍区如查询南区宿舍区到信息工程学院的最短路径：南区宿舍区——东教学楼——行政楼——学校正门——信息工程学院路程是190指导教师批阅及签名三、实验报告内容

2010年6月21日实验报告内容原则上应包括主要实验步骤、实验数据计算（实验操作）结果、实验结果（疑问）分析等项目。【主程序模块】：voidmain(){初始化;do{接受命令;处理命令;}while(命令!=“退出”)；}【功能模块调用关系图】主程序模块主程序模块建立及修改地图模块建立及修改地图模块导游咨询模块显示平面图模块显示平面图模块创建地图模块查询景点信息模块查询景点信息模块增加一条路径模块查询景点间的最短路径模块查询景点间的最短路径模块删除一条路径模块【详细设计】structArcCell//弧类型表示路径{VRTypeadj;//路径的权值Infotypeinfo;//路径的相关信息};structVertexType//顶点类型表示景点{charname[MAX_NAME],number[MAX_NAME];//景点的名称name、代号numberInfotypeinfo;//景点的简介};structMGraph//图类型表示校园的地图{VertexType*Vexs;//顶点向量指针ArcCell*Arcs;//邻接矩阵指针int*Short_st_Path;//存放最短路径的三维数组指针intvexnum,arcnum;//图的顶点vexnum数和弧数arcnum};StatusOpenWriteFile(PFILE&fp,charstring[MAX_NAME])//打开写的文件名为string的文件StatusOpenReadFile(PFILE&fp,charstring[MAX_NAME])//打开读的文件名为string的文件StatusGetVex(int&v,charstring[MAX_NAME],MGraphM)//返回图string顶点的位置,如果找到则返回它的位置，否则返回-1StatusInitMGraph(MGraph&M,intn)//初始化一个顶点数为n的图StatusDestroyGraph(MGraph&M)//销毁一个图StatusPutMGrap(MGraphM,charstring[MAX_NAME])//把内存中的图保存在string文件中StatusGetMGrap(MGraph&M,charstring[MAX_NAME])//从文件中取出一个文件名为string的图调入内存StatusCreateMGraph()//创建一个图，并保存在string文件中StatusShortest_Path_FLOYD(charstring[MAX_NAME])//对以文件名为string的地图求最短路径StatusSearch_Shortest_Path(charstring[MAX_NAME])//查询地图文件名为string的最短路径StatusSearch_Sight(charstring[MAX_NAME])//查询地图文件名为string的景点StatusInsertArc(charstring[MAX_NAME])//对保存在string的地图增加一条弧StatusDeleteArc(charstring[MAX_NAME])//对保存在string的地图删除一条弧【调试分析】（这部分内容因人而异）这里最大的问题就是文件的运用了，一开始，我用的是freopen()函数，这个函数能完成在文件里面的输入输出操作，但是无法完成在屏幕上显示出来。后来，查了课本，发现fopen(),fclose()更好用。【用户手册】本程序运行环境为ＤＯＳ，进入演示程序后，出现提示信息：——进行相应输入后程序执行相应操作，显示相应结果。实验报告评分：注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。【源程序】#include<iostream.h>#include<stdlib.h>#include<string.h>#include<conio.h>#include<stdio.h>#include<process.h>#defineOK1#defineERROR0#defineMAX_CHARSTRING100#defineMAX_NAME30#defineINFINITY32767 typedefboolStatus;typedefintVRType;typedefFILE*PFILE;typedefchar*Infotype;//模块一：用邻接矩阵存储校园的地图structArcCell//弧类型表示路径{VRTypeadj;//路径的权值Infotypeinfo;//路径的相关信息};structVertexType//顶点类型表示景点{charname[MAX_NAME],number[MAX_NAME];//景点的名称name、代号numberInfotypeinfo;//景点的简介};structMGraph//图类型表示校园的地图{VertexType*Vexs;//顶点向量指针ArcCell*Arcs;//邻接矩阵指针int*Short_st_Path;//存放最短路径的三维数组指针intvexnum,arcnum;//图的顶点vexnum数和弧数arcnum};intCalTwoDimPos(intb,inti,intj)//把第一维为b的二维数组的下标为[i][j]的地址转换成一维数组的地址,并返回{returni*b+j;}intCalThreeDimPos(intb,inti,intj,intk)//把第一、二维为b的三维数组的下标为[i][j][k]的地址转换成一维数组的地址,并返回{returni*b*b+j*b+k;}StatusOpenWriteFile(PFILE&fp,charstring[MAX_NAME])//打开写的文件名为string的文件{if(!(fp=fopen(string,"wb"))){cout<<"文件打开失败"<<endl;cout<<"Pressanykeytoexit"<<endl;getch();exit(ERROR);}returnOK;}StatusOpenReadFile(PFILE&fp,charstring[MAX_NAME])//打开读的文件名为string的文件{if(!(fp=fopen(string,"rb"))){cout<<"文件打开失败"<<endl;cout<<"Pressanykeytoexit"<<endl;getch();exit(ERROR);}returnOK;}StatusMakeString(Infotype&ch)//分配一个字符串成功则返回1,否则返回0{if(!(ch=newchar[MAX_CHARSTRING])){cout<<"字符串存储空间分配失败"<<endl;returnERROR;}returnOK;}StatusGetVex(int&v,charstring[MAX_NAME],MGraphM)//返回图string顶点的位置,如果找到则返回它的位置，否则返回-1{for(v=M.vexnum-1;v>=0;v--)if(!(strcmp(string,M.Vexs[v].name)))returnOK;returnERROR;}StatusInitMGraph(MGraph&M,intn)//初始化一个顶点数为n的图{inti,adr;if(!((M.Arcs=newArcCell[n*n])&&(M.Vexs=newVertexType[n])&& (M.Short_st_Path=newint[n*n*n]))){cout<<"图的存储空间分配失败"<<endl;exit(ERROR);}for(i=0,adr=0;i<n*n;i++,adr++)//对表示弧的邻接矩阵进行初始化 {M.Arcs[adr].adj=INFINITY; M.Arcs[adr].info=NULL;}for(i=0,adr=0;i<n*n*n;i++,adr++)M.Short_st_Path[adr]=-1;returnOK;}StatusDestroyGraph(MGraph&M){inti,adr;for(i=0;i<M.vexnum;i++){delete(M.Vexs[i].info);M.Vexs[i].info=NULL;}delete(M.Vexs);M.Vexs=NULL;for(i=0,adr=0;i<M.vexnum*M.vexnum;i++,adr++){if(M.Arcs[adr].info!=NULL){delete(M.Arcs[adr].info); M.Arcs[adr].info=NULL;}}delete(M.Arcs);M.Arcs=NULL;delete(M.Short_st_Path);M.Short_st_Path=NULL;returnOK;}StatusPutMGrap(MGraphM,charstring[MAX_NAME])//把内存中的图保存在string文件中{FILE*fp;inti,adr;OpenWriteFile(fp,string);fwrite(&M.vexnum,sizeof(int),1,fp);fwrite(&M.arcnum,sizeof(int),1,fp);fwrite(M.Vexs,sizeof(VertexType),M.vexnum,fp);for(i=0;i<M.vexnum;i++)fwrite(M.Vexs[i].info,sizeof(char),MAX_CHARSTRING,fp);fwrite(M.Arcs,sizeof(ArcCell),M.vexnum*M.vexnum,fp);for(i=0,adr=0;i<M.vexnum*M.vexnum;i++,adr++)if(M.Arcs[adr].info!=NULL)fwrite(M.Arcs[adr].info,sizeof(char),MAX_CHARSTRING,fp);fwrite(M.Short_st_Path,sizeof(int),M.vexnum*M.vexnum*M.vexnum,fp);fclose(fp);returnOK;}StatusGetMGrap(MGraph&M,charstring[MAX_NAME])//从文件中取出一个文件名为string的图调入内存{FILE*fp;inti,adr;OpenReadFile(fp,string);fread(&M.vexnum,sizeof(int),1,fp);InitMGraph(M,M.vexnum);fread(&M.arcnum,sizeof(int),1,fp);fread(M.Vexs,sizeof(VertexType),M.vexnum,fp);for(i=0;i<M.vexnum;i++){MakeString(M.Vexs[i].info);fread(M.Vexs[i].info,sizeof(char),MAX_CHARSTRING,fp);}fread(M.Arcs,sizeof(ArcCell),M.vexnum*M.vexnum,fp);for(i=0,adr=0;i<M.vexnum*M.vexnum;i++,adr++)if(M.Arcs[adr].info!=NULL){MakeString(M.Arcs[adr].info); fread(M.Arcs[adr].info,sizeof(char),MAX_CHARSTRING,fp); }fread(M.Short_st_Path,sizeof(int),M.vexnum*M.vexnum*M.vexnum,fp);fclose(fp);returnOK;}StatusCreateMGraph()//创建一个图，并保存在string文件中{MGraphM;inti,j,k,adr,adr1;charv1[MAX_NAME],v2[MAX_NAME],string[MAX_NAME];VRTypew;cout<<"请输入图的景点数和路径数:";cin>>M.vexnum>>M.arcnum;InitMGraph(M,M.vexnum);cout<<"请输入图名称、代号、简介:"<<endl;for(i=0;i<M.vexnum;i++)//输入景点的名称、代号、简介{MakeString(M.Vexs[i].info); cin>>M.Vexs[i].name>>M.Vexs[i].number>>M.Vexs[i].info; }cout<<"请输入路径的起点、终点、权值和相关信息"<<endl;for(k=0;k<M.arcnum;k++){LEAP:cin>>v1>>v2;GetVex(i,v1,M);GetVex(j,v2,M);while(i==-1||j==-1){cout<<"输入景点名错误,请重新输入"<<endl;gotoLEAP;}cin>>w; adr=CalTwoDimPos(M.vexnum,i,j);M.Arcs[adr].adj=w; MakeString(M.Arcs[adr].info); cin>>M.Arcs[adr].info; adr1=CalTwoDimPos(M.vexnum,j,i); MakeString(M.Arcs[adr1].info); M.Arcs[adr1].adj=w; strcpy(M.Arcs[adr1].info,M.Arcs[adr].info); }cout<<"请输入图的保存路径\\名称:";cin>>string;PutMGrap(M,string);DestroyGraph(M);returnOK;}StatusShortest_Path_FLOYD(charstring[MAX_NAME])//对以文件名为string的地图求最短路径{MGraphM;inti,j,k,n,adr,adr1,adr2,*d;GetMGrap(M,string);if(!(d=newint[M.vexnum*M.vexnum])){cout<<"数组D[i][j]存储空间分配失败"<<endl;exit(ERROR); }for(i=0;i<M.vexnum;i++) for(j=0;j<M.vexnum;j++){adr=CalTwoDimPos(M.vexnum,i,j); d[adr]=M.Arcs[adr].adj; if(d[adr]<INFINITY){adr=CalThreeDimPos(M.vexnum,i,j,0); M.Short_st_Path[adr]=i; M.Short_st_Path[adr+1]=j;}}for(i=0;i<M.vexnum;i++) for(j=0;j<M.vexnum;j++) for(k=0;k<M.vexnum;k++)if(j!=k){adr=CalTwoDimPos(M.vexnum,j,k); adr1=CalTwoDimPos(M.vexnum,j,i); adr2=CalTwoDimPos(M.vexnum,i,k); if(d[adr1]+d[adr2]<d[adr]){d[adr]=d[adr1]+d[adr2];adr=CalThreeDimPos(M.vexnum,j,k,0); for(n=0;n<M.vexnum;n++)M.Short_st_Path[adr+n]=-1; adr1=CalThreeDimPos(M.vexnum,j,i,0); adr2=CalThreeDimPos(M.vexnum,i,k,0); for(;M.Short_st_Path[adr1]!=-1;){M.Short_st_Path[adr++]=M.Short_st_Path[adr1++];} adr--; for(;M.Short_st_Path[adr2]!=-1;){M.Short_st_Path[adr++]=M.Short_st_Path[adr2++];}}}PutMGrap(M,string);DestroyGraph(M);returnOK;}StatusSearch_Shortest_Path(charstring[MAX_NAME])//查询地图文件名为string的最短路径{MGraphM;charv1[MAX_NAME],v2[MAX_NAME];inti,j,k,adr;GetMGrap(M,string);cout<<"请输入起始位置和终点位置名称:";cin>>v1>>v2;GetVex(i,v1,M);GetVex(j,v2,M);if(i==-1||j==-1){cout<<"输入景点名错误,请重新输入"<<endl;returnERROR;}adr=CalThreeDimPos(M.vexnum,i,j,0);if(M.Short_st_Path[adr]==-1){cout<<v1<<"到"<<v2<<"的路径:没有路径"<<endl;returnOK;}cout<<v1<<"到"<<v2<<"的路径:";for(k=0;M.Short_st_Path[adr]!=-1&&k<M.vexnum;adr++,k++)cout<<M.Vexs[M.Short_st_Path[adr]].name<<"-->";cout<<"\b\b\b"<<endl;cout<<v1<<"到"<<v2<<"途经路径的信息:"<<endl;adr=CalThreeDimPos(M.vexnum,i,j,0);for(k=0;M.Short_st_Path[adr+1]!=-1&&k<M.vexnum-1;k++){i=M.Short_st_Path[adr];j=M.Short_st_Path[++adr]; cout<<M.Vexs[i].name<<"-->"<<M.Vexs[j].name<<"路径信息:"<<M.Arcs[CalTwoDimPos(M.vexnum,i,j)].info<<endl; }DestroyGraph(M);returnOK;}StatusSearch_Sight(charstring[MAX_NAME])//查询地图文件名为string的景点{MGraphM;charv1[MAX_NAME];inti;GetMGrap(M,string);cout<<"请输入景点名称:";cin>>v1;GetVex(i,v1,M);if(i==-1){cout<<"输入景点名错误,请重新输入"<<endl;returnERROR; }cout<<"代号:"<<M.Vexs[i].number<<";相关信息:"<<M.Vexs[i].info<<endl;DestroyGraph(M);returnOK;}StatusInsertArc(charstring[MAX_NAME])//对保存在string的地图增加一条弧{MGraphM;charv1[MAX_NAME],v2[MAX_NAME];inti,j,adr,adr1,w;GetMGrap(M,string);cout<<"请输入路径的起点、终点、权值和相关信息:";cin>>v1>>v2;GetVex(i,v1,M);GetVex(j,v2,M);if(i==-1||j==-1){cout<<"输入景点名错误,请重新输入"<<endl;returnERROR; }cin>>w;adr=CalTwoDimPos(M.vexnum,i,j);M.Arcs[adr].adj=w;MakeString(M.Arcs[adr].info);cin>>M.Arcs[adr].info;adr1=CalTwoDimPos(M.vexnum,j,i);MakeString(M.Arcs[adr1].info);M.Arcs[adr1].adj=w;strcpy(M.Arcs[adr1].info,M.Arcs[adr].info);M.arcnum++;PutMGrap(M,string);DestroyGraph(M);returnOK;}StatusDeleteArc(charstring[MAX_NAME])//对保存在string的地图删除一条弧{MGraphM;charv1[MAX_NAME],v2[MAX_NAME];inti,j,adr;GetMGrap(M,string);cout<<"请输入景点的起点、终点:";cin>>v1>>v2;GetVex(i,v1,M);GetVex(j,v2,M);if(i==-1||j==-1){cout<<"输入景点名错误,请重新输入"<<endl;returnERROR; }adr=CalTwoDimPos(M.vexnum,i,j);M.Arcs[adr].adj=INFINITY;if(M.Arcs[adr].info!=NULL)delete(M.Arcs[adr].info);M.Arcs[adr].info=NULL;adr=CalTwoDimPos(M.vexnum,j,i);M.Arcs[adr].adj=INFINITY;if(M.Arcs[adr].info!=NULL)delete(M.Arcs[adr].info);M.Arcs[adr].info=NULL;M.arcnum--;PutMGrap(M,string);DestroyGraph(M);returnOK;}voidPrintMGrap(charstring[MAX_NAME]){FILE*fp;charc;OpenReadFile(fp,string);while(!feof(fp)){c=getc(fp);cout<<c;}cout<<endl;}voidmain(){charstring[MAX_NAME],str[MAX_NAME],c,c1;do{system("cls");cout<<"*******************************************************************************"<<endl;cout<<"*主功能及主要命令:(1)建立及修改地图C;"<<endl;cout<<"*菜(2)导游咨询T."<<endl;cout<<"*单(3)退出程序Q"<<endl;cout<<"*******************************************************************************"<<endl;cout<<"请输入命令(C,T,Q):";cin>>c;switch(c){case'C':system("cls"); cout<<"**********************************************************