数据结构课程设计校园导航系统.doc
课程设计报告课程设计题目：校园导航系统 学生姓名 张强专 业 计算机科学与技术班 级 102004102学 号 1020410215指导教师 艾菊梅 2012年 6 月 19 日一、课程设计题目校园导航系统二、实验时间、地点时间：第19周地点：东华理工大学软件楼三、实验目的 本次课程设计的主要目的是综合运用所学的数据结构知识解决一个比较实际问题，侧重对链表、数组、字符串、图、树等相关内容的综合应用，使同学们能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下良好的基础。四、实验要求1. 了解数据结构及其分类、数据结构与算法的密切关系； 2. 熟悉各种基本数据结构及其操作，学会根据实际问题来选择数据结构； 3. 掌握设计算法的步骤和分析方法； 4. 掌握数据结构在排序和查找等常用算法中的应用。5. 独立完成；6 每个人需按照选题规则确定好自己的题目（注意不是多人完成一题，每人独立完成一题），不得以任何理由选择其他的题目，当然在完成自己的题目之后根据个人兴趣可以继续选做其他的题目；7课程设计完成后严格按照报告格式撰写课程设计报告，并于结束后的第三天上交到学习委员统一交给老师；8课程设计的成绩由两部分组成：程序检查成绩（40，每个功能占程序分的20%）报告检查成绩（40）平时考核（20%）五、实验思路 校园简图（无向图）：北门1体育馆3软件楼2西食堂4东门6图书馆5三栋7南区10适、西寝室9西食堂8对应的邻接矩阵：1 2 3 4 5 6 7 8 9 101 1 150 max max max max max max max max2 150 1 250 300 250 max max max max max 3 max 250 1 100 max max max max max max4 max 300 100 1 200 150 300 max max max5 max 250 max 200 1 350 50 max max max6 max max max 150 350 1 350 max max 6007 max max max 300 50 350 1 100 max max8 max max max max max max 100 1 100 max 9 max max max max max max max 100 1 45010 max max max max max 600 max max 450 1程序总流程：开始输出菜单，输入一个数判断输入的数值输入起点、目的输入查询点查找最短路径、路径查找周边地点输入一个数是否为1退出输出错误为2为1非1、2、3为3非1为1 程序使用无向图表示校园简图，采用邻接矩阵表示各点间的关系、距离，运用结构体记录各信息，通过迪杰斯特拉算法计算两个地点间的最短路径，运用算法记录点到各个点的最短路径、记录最短路径的上各个点。六实现过程用结构体记录图的各项信息：class Graph public:int arcsn+1n+1;int distn+1;int pathn+1;int sn+1;void shortest_path(Graph &t,const int v1,int m);void ars(Graph &t);void demand(Graph &t,int i);用邻接矩阵记录各点间的联系、路径等：void Graph:ars(Graph &t) int i,j;for(i=1;i<=n;i+)for(j=1;j<=n;j+) if(i=j) t.arcsij=0; else t.arcsij=max; t.arcs12=t.arcs21=150;t.arcs23=t.arcs32=250; t.arcs24=t.arcs42=300;t.arcs25=t.arcs52=250; t.arcs34=t.arcs43=100;t.arcs46=t.arcs64=150; t.arcs45=t.arcs54=200;t.arcs56=t.arcs65=350; t.arcs57=t.arcs75=50;t.arcs47=t.arcs74=300; t.arcs67=t.arcs76=350;t.arcs78=t.arcs87=100; t.arcs89=t.arcs98=100;t.arcs910=t.arcs109=450; t.arcs610=t.arcs106=600; 运用结构体里的void Graph:demand(Graph &t,int i)函数和arcs 求单点的周边点：void Graph:demand(Graph &t,int i) cout<<"周边有："for(int j=1;j<=n;j+)if(t.arcsij!=0)&&(t.arcsij!=max) cout<<namej<<" "cout<<endl;效果：程序运用迪杰斯特拉算法计算两个地点间的最短路径：void Graph:shortest_path(Graph &t,const int v1,int m) for(int i=1;i<=n;i+)t.disti=t.arcsv1i;t.si=0;if (i!=v1)&&(t.disti<max) t.pathi=v1;else t.pathi=0;t.sv1=1;t.distv1=0;for(i=1;i<n;i+)int min=max;int u=v1;for(int j=1;j<=n;j+)if(!t.sj&&t.distj<min) u=j;min=t.distj;t.su=1;for (int w=1;w<=n;w+)if(!t.sw&&t.arcsuw<max&&t.distu+t.arcsuw<t.distw)t.distw=t.distu+t.arcsuw;t.pathw=u;if(m!=v1)cout<<namev1<<"到"<<namem<<"最短路程为"<<t.distm<<": "int pre=t.pathm;cout<<namem;while(pre!=0) cout<<"<-"<<namepre;pre=t.pathpre;cout<<endl;else cout<<"终点、始点为同一个地方！"效果：源程序代码：#include<iostream.h>#include<stdlib.h>const int n=10;const int e=10;char name1115=' ',"北门","软件楼","体育馆","北区食堂","图书馆","东门","三栋教学楼","西区食堂","西区寝室","南区寝室"#define max 32767class Graph public:int arcsn+1n+1; /图的邻接矩阵int distn+1; /存放源点到其它各点的最短路径int pathn+1; /存放在最短路径上该该顶点的前一顶点号int sn+1; /已求得的在最短路径上的顶点的顶点号void shortest_path(Graph &t,const int v1,int m);void ars(Graph &t);void demand(Graph &t,int i);void printf()cout<<"*校园导航系统*nn"cout<<" 1.两地最短路程查询nn" cout<<" 2.查询周边nn" cout<<" 3.退出系统nnn" cout<<"*请选择一个操作(1/2/3)*n"<<endl;/返回或退出设置int continu()int c;cout<<"n返回(1)；退出(其它) "cin>>c;if(c=1) return 1;else return 0;/打印地点目录void text()cout<<"1.北门 "<<"2.软件楼"<<endl;cout<<"3.体育馆 "<<"4.北区食堂"<<endl; cout<<"5.图书馆 "<<"6.东门"<<endl;cout<<"7.三栋教学楼 "<<"8.西区食堂"<<endl;cout<<"9.西区寝室 "<<"10.南区寝室"<<endl;/选择int select() int j; cin>>j;while(j<1|j>10) cout<<"选择有误!请重选: "cin>>j;return j;/建立图的邻接矩阵void Graph:ars(Graph &t) int i,j;for(i=1;i<=n;i+)for(j=1;j<=n;j+) if(i=j) t.arcsij=0; else t.arcsij=max; t.arcs12=t.arcs21=150;t.arcs23=t.arcs32=250; t.arcs24=t.arcs42=300;t.arcs25=t.arcs52=250; t.arcs34=t.arcs43=100;t.arcs46=t.arcs64=150; t.arcs45=t.arcs54=200;t.arcs56=t.arcs65=350; t.arcs57=t.arcs75=50;t.arcs47=t.arcs74=300; t.arcs67=t.arcs76=350;t.arcs78=t.arcs87=100; t.arcs89=t.arcs98=100;t.arcs910=t.arcs109=450; t.arcs610=t.arcs106=600; /查询周边void Graph:demand(Graph &t,int i) cout<<"周边有："for(int j=1;j<=n;j+)if(t.arcsij!=0)&&(t.arcsij!=max) cout<<namej<<" "cout<<endl;/求最短路径void Graph:shortest_path(Graph &t,const int v1,int m) /v1为源点，m为终点 for(int i=1;i<=n;i+)t.disti=t.arcsv1i;t.si=0;if (i!=v1)&&(t.disti<max) t.pathi=v1;else t.pathi=0;t.sv1=1;t.distv1=0;for(i=1;i<n;i+)int min=max;int u=v1;for(int j=1;j<=n;j+)if(!t.sj&&t.distj<min) u=j;min=t.distj;t.su=1;for (int w=1;w<=n;w+)if(!t.sw&&t.arcsuw<max&&t.distu+t.arcsuw<t.distw)t.distw=t.distu+t.arcsuw;t.pathw=u;if(m!=v1)cout<<namev1<<"到"<<namem<<"最短路程为"<<t.distm<<": "int pre=t.pathm;cout<<namem;while(pre!=0) cout<<"<-"<<namepre;pre=t.pathpre;cout<<endl;else cout<<"终点、始点为同一个地方！"void main() int k;char c2;Graph t; t.ars(t);for(int g=1;g=1;) system("cls"); / 清屏语句printf();cout<<"输入你的选择的操作！n" cin>>c;if(c0='1')&&(c1=NULL) text();cout<<"n请选择起点： "k=select(); cout<<"请选择终点： "t.shortest_path(t,k,select();g=continu();elseif(c0='2')&&(c1=NULL) text();cout<<"请选择一个地点：nn"t.demand(t,select();g=continu(); else if(c0='3')&&(c1=NULL) g=0;elsecout<<"输入有误!nn"g=continu();七实验总结 程序实现了两点的最短路径查询和单点周边查询，满足设计的基本要求，考虑了返回、重输入等细节。 程序菜单基本功能功能不多。八心得体会实验让我了解数据结构及其分类、数据结构与算法的密切关系； 熟悉各种基本数据结构及其操作，学会根据实际问题来选择数据结构； 掌握设计算法的步骤和分析方法； 掌握数据结构在排序和查找等常用算法中的应用。
