《校园导游》课程设计报告.doc

课程设计报告课程：数据结构 学号：0810111026 姓名：章阳 班级：08普本非师 教师：王群芳 时间：2010.6.30 合肥师范学院计算机科学与技术系设计名称：校园导游日期： 2010 年 6月 30 日 设计内容：用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。设计目的与要求：1. 查询各景点的相关信息2. 查询图中任意两个景点间的最短路径3. 查询图中任意两个景点间的所有路径4. 增加、删除、更新有关景点和道路的信息系统分析：邻接表中的顶点的信息用数组存储，本系统为了实现景点的增加，删除功能，采用了顶点信息用链表做为存储结构，可以方便的实现这些功能。在顶点的存储结构中，不仅有数据域（一个景点结构体，存放景点的编号，名称，介绍），指针域有指向下一个景点地址的nextV和指向其所对应边的下一个景点编号nextArc。表结点里放有路径的长度和景点编号，这是本系统的存储方式。本系统实现了对景点和道路的增加，删除，更新功能，且实现了任意景点之间的最短路径，和任意两景点的所有路径。本系统可以按菜单的方式进行操作，并且在主菜单中设置了两个隐藏函数，其中操作6为Print用邻接表的形式显示景点编号和操作7为PrintMatrix用矩阵的形式显示道路长度，从而来检测对景点和道路的增加，删除，更新是否实现。测试数据及结果：上图中，共有10个景点，16条道路。其中圆圈为各个景点(编号、名称、介绍)，边为道路(长度)。进入程序，选择是否使用默认数据：创建图成功：选择主操作1：选择主操作2：选择主操作3：选择主操作4：选择副操作1：选择副操作2：选择副操作3：选择副操作4：选择副操作5：选择副操作6：选择隐藏菜单Print:选择隐藏菜单PrintMatrix：设计体会： 本程序从设计到实现一共花了一个星期，感觉不是很难，但是要用心去做。在这次课程设计中，我再次感觉到自己做程序要站在顾客角度上，让程序更加合理，更加人性化。对于本次课程设计所用到的算法，我都想了很长时间，其中怎么输出所有路径，我还参考了网上的一些资料，最后用了广度优先搜索完成。做完了课程设计，感觉自己一下轻松起来，程序出来了，我也该继续下了一个设计。附录（源程序清单）： #includeusing namespace std;#include#include#define MAX_VERTEX_NUM 50typedef struct Scenerychar sno4;/景点编号char sname21;/景点名称char stext201;/景点介绍Scenery;/景点结构typedef struct ArcNodechar sno4;/景点编号int length;/道路长度struct ArcNode* next;ArcNode;/表结构typedef struct VNodeScenery sc;struct VNode* nextV;ArcNode* nextArc; VNode;/顶点结构/图结构typedef structVNode* V;/指向第一个顶点的指针int vexnum,arcnum;Graph;/矩阵结构typedef structchar vexsMAX_VERTEX_NUM4;/景点编号数组int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/道路长度矩阵int vexnum,arcnum;Matrix;/一行星号void Start(int n)coutt;for(int i=0;in;+i)cout*;coutendl;/主菜单void FMenu()Start(60);coutttt1)查询各景点的相关信息endl;coutttt2)查询图中任意两个景点间的最短路径endl;coutttt3)查询图中任意两个景点间的所有路径endl;coutttt4)增加、删除、更新景点和道路的信息endl;coutttt0)退出程序endl;Start(60);/副菜单void SMenu()Start(60);coutttt1)增加景点信息endl;coutttt2)删除景点信息endl;coutttt3)更新景点信息endl;coutttt4)增加道路信息endl;coutttt5)删除道路信息endl;coutttt6)更新道路信息endl;coutttt0)返回主菜单endl;Start(60);/获得ArcNode地址VNode* GetAddress(char* sno,Graph& G)VNode* p;p=G.V;for(int i=0;isc.sno)return p;elsep=p-nextV;return NULL;/系统默认建图void DirectCreate(Graph& G)G.arcnum=16;G.vexnum=10;VNode* p1;VNode* p2;ArcNode* q1;ArcNode* q2;G.V=p1=(VNode*)malloc(sizeof(VNode);strcpy(p1-sc.sno,001);strcpy(p1-sc.sname,艺术楼);strcpy(p1-sc.stext,艺术);q1=(ArcNode*)malloc(sizeof(ArcNode);p1-nextArc=q1;q1-length=60;strcpy(q1-sno,009);q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=30;strcpy(q2-sno,008);q2-next=NULL;q1-next=q2;p2=(VNode*)malloc(sizeof(VNode);strcpy(p2-sc.sno,002);strcpy(p2-sc.sname,实验楼);strcpy(p2-sc.stext,实验);p1-nextV=p2;q1=(ArcNode*)malloc(sizeof(ArcNode);strcpy(q1-sno,009);q1-length=40;p2-nextArc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=150;strcpy(q2-sno,006);q1-next=q2;q2-next=NULL;p1=(VNode*)malloc(sizeof(VNode);strcpy(p1-sc.sno,003);strcpy(p1-sc.sname,男生宿舍);strcpy(p1-sc.stext,住宿);p2-nextV=p1;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=30;strcpy(q1-sno,010);p1-nextArc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=75;strcpy(q2-sno,005);q1-next=q2;q2-next=NULL;p2=(VNode*)malloc(sizeof(VNode);strcpy(p2-sc.sno,004);strcpy(p2-sc.sname,女生宿舍);strcpy(p2-sc.stext,住宿);p1-nextV=p2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=30;strcpy(q1-sno,003);p2-nextArc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=100;strcpy(q2-sno,007);q1-next=q2;q2-next=NULL;p1=(VNode*)malloc(sizeof(VNode);strcpy(p1-sc.sno,005);strcpy(p1-sc.sname,小湖);strcpy(p1-sc.stext,风景);p2-nextV=p1;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=70;strcpy(q1-sno,009);p1-nextArc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=100;strcpy(q2-sno,006);q1-next=q2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=70;strcpy(q1-sno,008);q2-next=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=120;strcpy(q2-sno,007);q1-next=q2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=60;strcpy(q1-sno,010);q2-next=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=75;strcpy(q2-sno,003);q1-next=q2;q2-next=NULL;p2=(VNode*)malloc(sizeof(VNode);strcpy(p2-sc.sno,006);strcpy(p2-sc.sname,食堂);strcpy(p2-sc.stext,吃饭);p1-nextV=p2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=70;strcpy(q1-sno,009);p2-nextArc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=150;strcpy(q2-sno,002);q1-next=q2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=100;strcpy(q1-sno,005);q2-next=q1;q1-next=NULL;p1=(VNode*)malloc(sizeof(VNode);strcpy(p1-sc.sno,007);strcpy(p1-sc.sname,图书馆);strcpy(p1-sc.stext,借书);p2-nextV=p1;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=120;strcpy(q1-sno,005);p1-nextArc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=100;strcpy(q2-sno,004);q1-next=q2;q2-next=NULL;p2=(VNode*)malloc(sizeof(VNode);strcpy(p2-sc.sno,008);strcpy(p2-sc.sname,篮球场);strcpy(p2-sc.stext,运动);p1-nextV=p2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=70;strcpy(q1-sno,009);p2-nextArc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=70;strcpy(q2-sno,005);q1-next=q2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=30;strcpy(q1-sno,001);q2-next=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=20;strcpy(q2-sno,010);q1-next=q2;q2-next=NULL;p1=(VNode*)malloc(sizeof(VNode);strcpy(p1-sc.sno,009);strcpy(p1-sc.sname,教学楼);strcpy(p1-sc.stext,教学);p2-nextV=p1;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=70;strcpy(q1-sno,005);p1-nextArc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=70;strcpy(q2-sno,006);q1-next=q2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=40;strcpy(q1-sno,002);q2-next=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=60;strcpy(q2-sno,001);q1-next=q2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=70;strcpy(q1-sno,008);q2-next=q1;q1-next=NULL;p2=(VNode*)malloc(sizeof(VNode);strcpy(p2-sc.sno,010);strcpy(p2-sc.sname,足球场);strcpy(p2-sc.stext,运动);p1-nextV=p2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=20;strcpy(q1-sno,008);p2-nextArc=q1;q2=(ArcNode*)malloc(sizeof(ArcNode);q2-length=60;strcpy(q2-sno,005);q1-next=q2;q1=(ArcNode*)malloc(sizeof(ArcNode);q1-length=30;strcpy(q1-sno,003);q2-next=q1;q1-next=NULL;p2-nextV=NULL;/创建图bool Create(Graph& G)VNode* last;VNode* p;cout请输入景点个数以及道路条数G.vexnumG.arcnum;if(G.vexnum=0)|(G.arcnum=0)return false;G.V=(VNode*)malloc(sizeof(VNode);last=G.V;cout请输入第1个景点的编号、名称、介绍last-sc.snolast-sc.snamelast-sc.stext;last-nextArc=NULL;for(int i=1;iG.vexnum;+i)p=(VNode*)malloc(sizeof(VNode);cout请输入第i+1个景点的编号、名称、介绍p-sc.snop-sc.snamep-sc.stext;p-nextArc=NULL;last-nextV=p;last=last-nextV;last-nextV=NULL;char startSno4;char endSno4;int length;ArcNode* q=NULL; VNode* address=NULL;for(i=0;iG.arcnum;+i)cout请输入第i+1条道路的起始景点编号和终点景点编号以及长度startSnoendSnolength;address=GetAddress(startSno,G);q=(ArcNode*)malloc(sizeof(ArcNode);strcpy(q-sno,endSno);q-length=length;q-next=address-nextArc;address-nextArc=q;/*-无向网需正反两次-*/address=GetAddress(endSno,G);q=(ArcNode*)malloc(sizeof(ArcNode);strcpy(q-sno,startSno);q-length=length;q-next=address-nextArc;address-nextArc=q;return true;/查询相关景点信息void SearchScenery(Graph& G)int count=0;VNode* p=G.V;char noOrName21;cout请输入你想要查询的景点的编号或名称noOrName;for(int i=0;isc.sno)&strcmp(noOrName,p-sc.sname)cout景点编号:sc.snoendl;cout景点名称:sc.snameendl;cout景点介绍:sc.stextnextV;if(!count)cout查找失败!endl;/增加景点信息void AddScenery(Graph& G)int count=0;int flag=0;char sno4;char sname21;char stext201;VNode* g=NULL;coutsno;g=G.V;while(g)if(!strcmp(g-sc.sno,sno)flag+;break;elseg=g-nextV;if(flag)cout输入的景点编号重复,请重新插入!endl;return;coutsname;coutstext;coutsc.sno,sno)count+;break;elseparent=p;p=p-nextV;if(!count)VNode* q;q=(VNode*)malloc(sizeof(VNode);strcpy(q-sc.sno,sno);strcpy(q-sc.sname,sname);strcpy(q-sc.stext,stext);parent-nextV=q;q-nextV=NULL;q-nextArc=NULL;G.vexnum+;cout增加景点信息成功!endl;elsecout增加景点编号重复,请重新增加!nextArc;parent1=address;while(last)if(!strcmp(sno1,last-sno)if(!count)parent1-nextArc=last-next;elseparent2-next=last-next;free(last);break;elsecount+;parent2=last;last=last-next;/删除景点信息1void DeleteScenery(Graph& G)int count=0;char noOrName21;VNode* p=NULL;VNode* parent=NULL;ArcNode* last;parent=p=G.V;cout请输入要删除的景点的编号或名称noOrName;while(p)if(!(strcmp(p-sc.sno,noOrName)&strcmp(p-sc.sname,noOrName)count+;break;elseparent=p;p=p-nextV;if(!count)cout无法删除该景点信息,请查核后在删除!nextV;elseparent-nextV=p-nextV;strcpy(sno,p-sc.sno);last=p-nextArc;ArcNode* q=NULL;while(last)Delete(sno,last-sno,G);q=last;last=last-next;free(q);free(p);G.vexnum-;cout成功删除该景点信息!endl;/更新景点信息void UpdateScenery(Graph& G)int count=0;cout提示:更新景点信息只允许更改景点名称以及景点介绍,编号作为主关键字不允许更改!endlendl;char noOrName21;coutnoOrName;VNode* p=G.V;while(p)if(!(strcmp(p-sc.sname,noOrName)&strcmp(p-sc.sno,noOrName)count+;coutp-sc.sname;coutp-sc.stext;break;elsep=p-nextV;if(!count)cout修改景点信息未成功!请查核后再次修改!endl;elsecout修改景点信息成功!endl;/增加道路信息void AddRode(Graph& G)int count=0;VNode* address=NULL;ArcNode* q=NULL;ArcNode* p=NULL;char sno14;char sno24;int length;cout请输入要增加道路两端的景点编号以及道路长度sno1sno2length;if(!strcmp(sno1,sno2)cout您输入的道路两端的景点编号一样,请核查后再试!nextArc;while(p)if(!strcmp(p-sno,sno2)count+;break;elsep=p-next;if(count)cout增加道路信息失败!sno,sno2);q-length=length;q-next=address-nextArc;address-nextArc=q;address=GetAddress(sno2,G);q=(ArcNode*)malloc(sizeof(ArcNode);strcpy(q-sno,sno1);q-length=length;q-next=address-nextArc;address-nextArc=q;G.arcnum+;cout增加道路信息成功!endl;/删除道路信息void DeleteRode(Graph& G)int count=0;VNode* address=NULL;ArcNode* p=NULL;char sno14;char sno24;cout请输入要删除道路两端的景点编号sno1sno2;if(!strcmp(sno1,sno2)cout您输入的道路两端的景点编号一样,请核查后再试!endl;elseaddress=GetAddress(sno1,G);if(!address)cout没有你要删除的道路两端的景点编号,请核查后再试!nextArc;VNode* parent1=address;ArcNode* parent2=address-nextArc;int flag=0;while(p)if(!strcmp(sno2,p-sno)count+;if(!flag)parent1-nextArc=p-next;elseparent2-next=p-next;break;elseflag+;p=p-next;if(count)address=GetAddress(sno2,G);parent1=address;parent2=address-nextArc;p=address-nextArc;flag=0;while(p)if(!strcmp(sno1,p-sno)if(!flag)parent1-nextArc=p-next;elseparent2-next=p-next;break;elseflag+;p=p-next;G.arcnum-;cout成功删除道路信息!endl;elsecout删除道路信息失败,请核查后再试!endl;/更新道路信息void UpdateRode(Graph& G)int count=0;VNode* address=NULL;ArcNode* p=NULL;int length;char sno14;char sno24;cout请输入要更新道路两端的景点编号以及更新后的道路长度sno1sno2length;if(!strcmp(sno1,sno2)cout您输入的道路两端的景点编号一样,请核查后再试!nextArc;while(p)if(!strcmp(sno2,p-sno)count+;p-length=length;break;elsep=p-next;if(!count)cout更新道路信息失败,请核查后再试!nextArc;while(p)if(!strcmp(sno1,p-sno)p-length=length;break;elsep=p-next;cout更新道路信息成功!endl;/检测景点编号void Print(Graph& G)VNode* p;p=G.V;ArcNode* q;while(p)coutsc.snonextArc;while(q)coutsnonext;coutnextV;/初始化矩阵void Initialize(Matrix& M)for(int i=0;iM.vexnum;i+)for(int j=0;jM.vexnum;j+)M.arcsij=99999;/定位int Locate(char* sno,Matrix& M)int n=0;char sno24;for(int i=0;iM.vexnum;+i)for(int j=0;j4;+j)sno2j=M.vexsij;if(!strcmp(sno2,sno)n=i;break;return n;/表转换为矩阵void ListToMatrix(Graph& G,Matrix& M)int v1,v2;M.arcnum=G.arcnum;M.vexnum=G.vexnum;VNode* p=G.V;ArcNode* q=NULL;for(int i=0;isc.sno);p=p-nextV;Initialize(M);p=G.V;while(p)q=p-nextArc;v1=Locate(p-sc.sno,M);while(q)v2=Locate(q-sno,M);M.arcsv1v2=q-length;q=q-next;p=p-nextV;/检查矩阵void PrintMatrix(Matrix& M)coutM.vexnum;for(int i=0;iM.vexnum;+i)for(int j=0;jM.vexnum;+j)coutM.arcsij ;coutendl;typedef int PathMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef int ShortPathTableMAX_VERTEX_NUM;/求从v0到各个顶点的最短路径，用P返回路径，用D返回各路径的总权值void ShortPath_DJIK(Matrix& M,int k,PathMatrix &P,ShortPathTable &D) int v,v0,w,i,j; int finalMAX_VERTEX_NUM; /用此数组表示某个顶点是否已经并入s集合，其中finali表示G中索引为i的顶点 v0=k;/求数值为k的顶点在M中的索引 for(v=0;vM.vexnum;+v) finalv=0; /初始化s集合为空集 Dv=M.arcsv0v; /初始化Di为v0到i顶点的权 for(w=0;wM.vexnum;+w) Pvw=0; /初始化路径 if(Dv99999) Pvv0=1;Pvv=1; Dv0=0; finalv0=1; /初始化，v0顶点属于s集 /开始主循环 for(i=1;iM.vexnum;+i) int min; min=99999; /给min赋一个较大的值以便比较 for(w=0;wM.vexnum;+w) if(!finalw) if(Dwmin)/求出距离v0顶点最近的顶点在G中的索引w，并把v0到它的权赋给Dw v=w; min=Dw; finalv=1; /将v顶点并入s集合 for(j=0;jM.vexnum;+j) if(!finalj&(min+M.arcsvjDj) Dj=min+M.arcsvj; for(int h=0;hM.vexnum;+h) Pjh=Pvh; Pjj=1; /打印两点间的最短路径void Print_DJIK(Matrix& M,PathMatrix& P,ShortPathTable& D) char sno14;char sno24;cout请输入需要查询的两个景点编号sno1sno2;if(!strcmp(sno1,sno2)cout您输入的两个景点编号一样,请核查后再试!endl;elseint k,a,b,c,d,q=0;int sight2,sight1;k=sight1=Locate(sno1,M);ShortPath_DJIK(M,k,P,D);sight2=Locate(sno2,M);a=sight2; if(a!=sight1) cout从M.vexssight1到M.vexssight2的最短路径是;coutt(最短距离为Da米)endl;coutM.vexssight1;d=sight1; for(c=0;cM.vexnum;+c)gate:; Pasight1=0; for(b=0;bM.vexnum;b+) if(M.arcsdb99999&Pab) coutM.vexsb; q=q+1; Pab=0; d=b; if(