Course Design of Data Structure
计算机科学与技术082
姓名：** ** ** 学号：08422137
指导老师：** ** ** 2010年7月9日
目 录
1．需求分析说明
2．概要设计说明
3．详细设计说明
4．调试分析
5．课程设计总结
6．参考书目
7．致谢
需求分析说明
随着高校校园的逐渐扩展，来访校园的人士逐渐增多， 随着校园透明度的提高，各界人士对学术氛围的追求，越来越多的人走进了大学校园，走进了象牙塔，这片静土也以它崭新的面貌，迎接着所有的到来者，以前封闭以及半封闭的校园状况随之改变，派生的是它积极的迎接挑战的状态。
高等院校，历来以其悠久的历史、深厚的文化底蕴、优美的自然和人文景观吸引着人们的目光。高校校园旅游在掀起“羞答答的头盖“后，正悄然走向市场，当今高校在确立了旅游的市场可行性之后，随之而来的导游系统是势在必行，高校的旅游可以让人陶冶情操，也可以让人对学术产生浓厚的兴趣。那么如何更好的更科学的更科学的组织好高校导游，如何更方便更便捷的把高校的校园展示给世人，就成为了一个需要解决的问题。利用计算机建立一个自动的导游系统，可以很好的解决这个问题。当客人来访时，系统可以根据客人指定的景点给予相关的信息，游客可以方便的了解到每个景点的详细信息，同时可以通过系统找到起始点和终点的多条路径，通过系统的分析后，能得出一条最短路径。各个景点的全景图、局部图可以在景点浏览中找到，付予语音、图片以及相关文字说明，让游客轻轻松松掌握景点信息。
概要设计说明
用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求实现以下功能：
（1）查询各景点的相关信息。
（2）查询图中任意两个景点间的最短路径。
（3）查询图中任意两个景点间的所有路径。
用图的结点代表景点，用图的边代表景点意见的路径，首先设计一个图类，结点值代表景点的信息，边的权值代表景点之间的距离，结点值及边的权值用顺序表存储，所以需要设计一个顺序表类，本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个编号，用结构体类型来实现。计算路径长度和最短路线是可以用Dijkstra(迪杰斯特拉)算法实现，在主函数中用switch选择语句执行浏览景点信息或查询最短路径
typedef struct ArCell
{
int adj; //路径长度
}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct //图中顶点表示主要景点，存放景点的编号、名称、简介等信息，
{
char name[30];
int num;
char introduction[200];//简介
}infotype;
typedef struct
{
infotype vexs[MAX_VERTEX_NUM];//景点
AdjMatrix arcs;//路径数组
int vexnum,arcnum;//景点数，路径长度记录
}MGraph;
void cmd(void);//在主函数中用来调用其他应用子函数的函数声明
MGraph InitGraph(void);//用来构造学校地图的子函数 返回MGraph类型
void Menu(void);//菜单函数；
void Browser(MGraph *G);//调用MGraph类型的地址，进行
void ShortestPath_DIJ(MGraph * G);//迪杰斯特拉算法求最短路径的子函数
void Floyd(MGraph *G);//佛洛伊德算法
void Search(MGraph *G);//寻找要查询的景点，并输出该景点的信息
int LocateVex(MGraph *G,char* v);//定点位置
MGraph * CreatUDN(MGraph *G);////初始化图形，接受用户输入
void print(MGraph *G);//打印输出子函数
详细设计说明
#define INFINITY 10000 /*无穷大*/
#define MAX_VERTEX_NUM 40
#define MAX 40
#include #include #include #include typedef struct ArCell { int adj; //路径长度 }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct //图中顶点表示主要景点，存放景点的编号、名称、简介等信息， { char name[30]; int num; char introduction[200];//简介 }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM];//景点 AdjMatrix arcs;//路径数组 int vexnum,arcnum;//景点数，路径长度记录 }MGraph; MGraph b;//全局变量 void cmd(void);//在主函数中用来调用其他应用子函数的函数声明 MGraph InitGraph(void);//用来构造学校地图的子函数 返回MGraph类型 void Menu(void);//菜单函数； void Browser(MGraph *G);//调用MGraph类型的地址，进行 void ShortestPath_DIJ(MGraph * G);//迪杰斯特拉算法求最短路径的子函数 void Floyd(MGraph *G);//佛洛伊德算法 void Search(MGraph *G);//寻找要查询的景点，并输出该景点的信息 int LocateVex(MGraph *G,char* v);//定点位置 MGraph * CreatUDN(MGraph *G);////初始化图形，接受用户输入 void print(MGraph *G);//打印输出子函数 /******************************************************/ void main(void) { system("color 1f");//设置调试窗口背景和字体颜色 system("mode con: cols=140 lines=130");//设置调试窗口的大小 cmd();//用该函数来调用其他需要用到的函数 } /******************************************************/ void cmd(void)//用来调用其他需要用到的函数的子函数 { int i; b=InitGraph();//构造校园地图 Menu();//调用菜单函数 scanf("%d",&i); while(i!=5) { switch(i) { case 1:system("cls");Browser(&b);Menu();break; case 2:system("cls");ShortestPath_DIJ(&b);Menu();break; case 3:system("cls");Floyd(&b);Menu();break; case 4:system("cls");Search(&b);Menu();break; case 5:exit(1);break; default:break; } scanf("%d",&i); } } //************************************************************************ MGraph InitGraph(void)//构造校园地图 { MGraph G; int i,j; G.vexnum=10;//景点数量 G.arcnum=14;//路径数量 for(i=0;i /*对对应的景点编号进行命名，输入简介*/ strcpy(G.vexs[0].name,"行政楼"); strcpy(G.vexs[0].introduction,"学校的行政机构"); strcpy(G.vexs[1].name,"图书馆"); strcpy(G.vexs[1].introduction,"藏书200万册,设施良好，环境幽雅"); strcpy(G.vexs[2].name,"新理科楼"); strcpy(G.vexs[2].introduction,"学校最气派的教学楼，里面的设施比较好"); strcpy(G.vexs[3].name,"川味府"); strcpy(G.vexs[3].introduction,"里面有南方各种美食，就餐环境幽雅"); strcpy(G.vexs[4].name,"洗浴中心"); strcpy(G.vexs[4].introduction,"学校唯一的澡堂，在川味府旁边"); strcpy(G.vexs[5].name,"中心体育场"); strcpy(G.vexs[5].introduction,"化塑胶跑道,人造草坪,适宜锻炼身体的场所"); strcpy(G.vexs[6].name,"会堂"); strcpy(G.vexs[6].introduction,"学校有大型的晚会都在这里举行"); strcpy(G.vexs[7].name,"钟楼广场"); strcpy(G.vexs[7].introduction,"是连大学子展现才华的地方，旁有邮局"); strcpy(G.vexs[8].name,"新文科楼"); strcpy(G.vexs[8].introduction,"里面包含几个学院"); strcpy(G.vexs[9].name,"清缘超市"); strcpy(G.vexs[9].introduction,"学校最大的超市，里面有很多学生使用的商品"); //对有路的各景点之间的路径长度进行设置,没路的设置为无穷大 for(i=0;i G.arcs[0][1].adj=100; G.arcs[0][2].adj=150; G.arcs[0][6].adj=200; G.arcs[1][7].adj=150; G.arcs[2][3].adj=50; G.arcs[3][6].adj=50; G.arcs[3][4].adj=20; G.arcs[4][5].adj=200; G.arcs[4][9].adj=150; G.arcs[5][9].adj=350; G.arcs[6][7].adj=60; G.arcs[6][9].adj=80; G.arcs[7][8].adj=50; G.arcs[8][9].adj=20; //无向图的路径是相互的 for(i=0;i return G; }//InitGraph end //***************************************************************************** //菜单函数，打印出导游项目菜单 void Menu() { printf("\\n 大连大学校园导游图\\n"); printf(" ┏━━━━━━━━━━━━━━━━━━━━┓\\n"); printf(" ┃ 1.浏览校园全景 ┃\\n"); printf(" ┃ 2.查看所有游览路线 ┃\\n"); printf(" ┃ 3.选择出发点和目的地 ┃\\n"); printf(" ┃ 4.查看景点信息 ┃\\n"); printf(" ┃ 5.退出系统 ┃\\n"); printf(" ┗━━━━━━━━━━━━━━━━━━━━┛\\n"); printf("Option-->:"); } //******************************************************************************** //输出所有景点信息 void Browser(MGraph *G) { int v; printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n"); printf("┃编号┃景点名称 ┃简介 ┃\\n"); for(v=0;v printf("┃%-4d┃%-16s┃%-58s┃\\n",G->vexs[v].num,G->vexs[v].name,G->vexs[v].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\\n"); } //*********************************************************************************** // 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点 void ShortestPath_DIJ(MGraph * G) { int v,w,i,min,t=0,x,flag=1,v0; int final[20], D[20], p[20][20]; while(flag) { printf("请输入一个起始景点编号:"); scanf("%d",&v0); if(v0<0||v0>G->vexnum) { printf("景点编号不存在!请重新输入景点编号:"); scanf("%d",&v0); } if(v0>=0&&v0 flag=0; } for(v=0;v { final[v]=0; D[v]=G->arcs[v0][v].adj; for(w=0;w p[v][w]=0; if(D[v] p[v][v0]=1;p[v][v]=1; } } D[v0]=0;final[v0]=1; for(i=1;i { min=INFINITY; for(w=0;w if(!final[w]) if(D[w] for(w=0;w if(!final[w]&&(min+G->arcs[v][w].adj D[w]=min+G->arcs[v][w].adj; for(x=0;x p[w][x]=p[v][x]; p[w][w]=1; } } for(v=0;v { if(v0!=v) printf("%s",G->vexs[v0].name); for(w=0;w { if(p[v][w]&&w!=v0) printf("-->%s",G->vexs[w].name); t++; } if(t>G->vexnum-1&&v0!=v)printf(" 总路线长%dm\\n\\n",D[v]); } }//ShortestPath_DIJ end //********************************************************************* void Floyd(MGraph *G) { int v,u,i,w,k,j,flag=1,p[10][10][10],D[10][10]; for(v=0;v for(w=0;w { D[v][w]=G->arcs[v][w].adj; for(u=0;u p[v][w][u]=0; if(D[v][w] p[v][w][v]=1;p[v][w][w]=1; } } for(u=0;u for(v=0;v for(w=0;w if(D[v][u]+D[u][w] D[v][w]=D[v][u]+D[u][w]; for(i=0;i p[v][w][i]=p[v][u][i]||p[u][w][i]; } while(flag) { printf("请输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); if(k<0||k>G->vexnum||j<0||j>G->vexnum) { printf("景点编号不存在!请重新输入出发点和目的地的编号:"); scanf("%d%d",&k,&j); } if(k>=0&&k flag=0; } printf("%s",G->vexs[k].name); for(u=0;u if(p[k][j][u]&&k!=u&&j!=u) printf("-->%s",G->vexs[u].name); printf("-->%s",G->vexs[j].name); printf(" 总路线长%dm\\n",D[k][j]); }//Floyd end //**************************************************************** //寻找要查询的景点，并输出该景点的信息 void Search(MGraph *G) { int k,flag=1; while(flag) { printf("请输入要查询的景点编号:"); scanf("%d",&k); if(k<0||k>G->vexnum) { printf("景点编号不存在!请重新输入景点编号:"); scanf("%d",&k); } if(k>=0&&k flag=0; } printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n"); printf("┃编号┃景点名称 ┃简介 ┃\\n"); printf("┃%-4d┃%-16s┃%-56s┃\\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\\n"); }//Search end //************************************************************************* int LocateVex(MGraph *G,char* v) { int c=-1,i; for(i=0;i if(strcmp(v,G->vexs[i].name)==0) {c=i;break;} return c; } //************************************************************************** MGraph * CreatUDN(MGraph *G)//初始化图形，接受用户输入 { int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum); printf("请输入景点的编号:、名称、简介:\\n"); for(i=0;i { printf("景点编号:"); scanf("%d",&G->vexs->num); printf("景点名称:"); scanf("%s",G->vexs[i].name); printf("景点简介:"); scanf("%s",G->vexs->introduction); } for(i=0;i for(j=0;j G->arcs[i][j].adj=INFINITY; printf("请输入路径长度:\\n"); for(k=0;k { printf("第%d条边:\\n",k+1); printf("景点对(x,y):"); scanf("%s",v1); scanf("%s",v2); printf("路径长度:"); scanf("%d",&w); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i>=0&&j>=0) { G->arcs[i][j].adj=w; G->arcs[j][i]=G->arcs[i][j]; } } return G; } //******************************************************************** void print(MGraph *G) { int v,w,t=0; for(v=0;v for(w=0;w { if(G->arcs[v][w].adj==INFINITY) printf("∞ "); else printf("%-7d",G->arcs[v][w].adj); t++; if(t%G->vexnum==0) printf("\\n"); } } //******************************************************************** 调试分析 课程设计总结 通过本次课程设计实验，使我更能熟练地掌握数据结构以及C语言等知识的综合应用。当然在课程设计期间，也遇到了大大小小的一些问题，也看到了自己的不足之处，使我认识到在以后的学习中要善于发现自己的不足，找到自己的薄弱环节，以便能够更好的去巩固所学。 本次设计中要求求最短路径，就必须要理解求最短路径的算法：Dijkstra算法或者是Floyd算法。在拿到题目值，通过查找相关的资料才回忆起这两种算法的具体实现，比较着两种算法的复杂度，尽量选用复杂度小的算法，当然任何程序都不可能完美，往往会牺牲程序的空间来换取时间，或者牺牲时间类换取足够大的空间，这就需要根据程序的具体要求来设计算法。在选用存储方法时，要尽量选用时间复杂度较小的算法，这样能够节省程序执行时间，提高查询效率。 课程设计中所使用的计算机语言其使用范围比较广阔，在很多编程中都可以用到，所以无论以后我们从事计算机编程，软件设计还是硬件，网络等领域，都应该学会，学精一门编程语言，这对我们以后学习和工作有很大的帮助。 测试结果 参考书目 [1]数据结构C语言版，严蔚敏，吴伟民编著，—北京：清华大学出版社 [2]数据结构（习题与解析），李春葆编著，清华大学出版社 致谢 首先感谢我的指导老师高秀娥胡老师，他在我的课程设计过程中提出了指导性的方案和架构，并指引我阅读相关的资料和书籍，使我在不熟悉的领域中仍能迅速掌握新的技术。 感谢我的数据结构老师汤老师和C语言老师在以往的基础课学习中为我打下良好的基础，这是我这次课程设计能够顺利完成的前提。 我的同学在设计完成后对程序的测试，没有他们，也许就难以发现一些潜在的错误，在此一并表示感谢。下载本文
