最短距离问题数据结构课程设计报告
更新时间:2023-07-17 20:26:01 阅读量: 实用文档 文档下载
- 数据结构最短工期推荐度:
- 相关推荐
数据结构课程设计报告
题目:北海公园主要游览景点之间最短距离问题
一、课程设计题目:北海公园主要游览景点之间最短距离问题 二、问题定义:(由教师指定)
图的最短路径问题是指从指定的某一点v开始,求得从该地点到图中其它各地点的最短路径。并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求
解外,还能对该图进行修改,如顶点以及边的增删、边上权值的修改等。
三、需求分析
1、设计北海公园的平面图。选取若干个有代表性的景点抽象成一个无向带权图,以图
中顶点表示公园内各景点,边上的权值表示两景点之间的距离。 2、输入的形式:整型数字
输入值的范围:0-10
3、输出的形式:由二元组表示以邻接矩阵存储的图
4、程序所能达到的功能;
(1)输出顶点信息:将公园内各景点输出。
(2)输出边的信息:将公园内每两个位置的距离输出。
(3)修改:修改两个位置的距离,并重新输出每两个位置的距离;
(4)求最短路径:输出给定两点之间的最短路径的长度及途经的地点,输出任意
一点与其他各点的最短路径。 (5)删除:删除任意一条边。 (6)插入:插入任意一条边。 5、算法涉及的基本理论分析: 定义邻接矩阵adjmatrix; 自定义顶点结构体VertexType;
定义邻接表中的边结点类型edgenode; switch算法;
狄克斯特拉法(Dijkstra)求任意两结点之间的最短路径; 6、题目研究和实现的价值。
四、算法设计
1、概要设计
(1)存储结构设计
本系统采用图结构类型存储抽象北海公园地图的信息。其中:各景点间的
邻接关系用图的邻接矩阵类型(adjmatrix)存储;景点(顶点)信息用结构数组(VertexType)存储,其中每个数组元素是一个结构变量,包含景点编号、景点名称两个分量;图的顶点个数由分量MaxVertexNum表示,它是整型数据。
(2)主界面设计
为了实现公园导游系统各功能的管理,首先设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能,方便用户使用本系统。
(3)系统功能设计
a学校景点介绍
公园景点介绍由函数PrintMatrix根据邻接矩阵输出二元组表示实现。当用户选择该功能,系统即能输出全部景点的信息:包括景点编号、景点名称。 b查看浏览路线
查看浏览路线采用狄克斯特拉(Dijkstra)算法实现。当用户选择该功能,系统能根据用户所在门起始编号,求出从该门到其它景点的最短路径线路。 c更改图的信息
更改图的信息功能由主调函数change函数完成,可以实现图的若干基本操作。例如:插入、删除边,重建图等。
2、主程序的流程以及各程序模块之间的层次(调用)关系。 (1)公园抽象图设计
(2)模块设计
本程序包含3个模块:主程序模块、工作区模块和无向网操作模块。
3、详细设计
(1)实现概要设计中定义的所有数据类型; //邻接矩阵的结构体
const int MaxVertexNum=9;
const int MaxEdgeNum=16300; typedef int WeightType; const WeightType MaxValue=28; //顶点结构体 struct VertexType {
int num_d;//顶点代号 char name[20];//顶点名称 };
typedef VertexType vexlist[MaxVertexNum];
typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; //定义邻接表中的边结点类型 struct edgenode {
int adjvex;
WeightType weight;
edgenode *next; };
(2)所有函数的接口描述;
//将二维数组里的数据传输给邻接矩阵 void InitMatrix( )
//将景点名称数据传输给顶点结构体 void InitVT( )
//邻接矩阵的二元组表示 void PrintMatrix( ) //PATH void PATH( )
//最短路径:狄克斯特拉 void Dijkstra( ) //输出最短路径 void Print( ) //插入路径问题
void change( )
(3)所有函数的算法描述(只需要写出伪码算法);
//将二维数组data[][ ]的数据传输给邻接矩阵GA void InitMatrix(adjmatrix &GA,int data[9][9]) {
}
GA[i][j]=data[i][j];
//将景点名称数据a[]传输给顶点结构体VT[] void InitVT(VertexType VT[9],char *a[9]) { strcpy(VT[i].name,a[i]);
}
//邻接矩阵的二元组表示
void PrintMatrix(adjmatrix GA,VertexType VT[9]) {
cout<<"V={";
cout<<i<<"--"<<VT[i].name<<','; cout<<"8--"<<VT[8].name<<'}'<<endl; cout<<"E={";
cout<<'<'<<i<<','<<j<<'>'<<GA[i][j]<<',';
cout<<'}'<<endl; }
//输出最短路径
void Print(edgenode *path[9],int begin,VertexType VT[9]) { }
//插入路径问题
void change(int x,int y,int z,adjmatrix &GA) { GA[x][y]=z;
GA[y][x]=z;
cout<<"从起点到达 "<<VT[i].name<<" 的最短路径为"<<"-----"; cout<<VT[p->adjvex].name<<"→";
cout<<VT[i].name<<"\n";
cout<<"无法通行至 "<<VT[i].name<<" ,请检查路径问题!"<<endl;
}
(4)对主程序和其他模块也都需要写出伪码算法 void main() { char *a[9]={ };//动态字符串数组
int chose1=0,chose2=0,chose3=0,jidong_1=0,start=0,insert1=-1,insert2=-1,insert3=-1;//循环,选择,机动元素
do
int dist[];
edgenode *path[];
int data[9][9]={ };
adjmatrix GA;//定义邻接矩阵
VertexType VT[];//定义顶点结构体 InitVT(VT,a);//传输顶点数据
InitMatrix(GA,data);//传输结构体数据
cout<<"*---------------欢迎使用北海公园路径查询程序-----------------*\n"; cout<<"*------------------------------------------------------------*"<<endl; cin>>chose1; switch(chose1) {
case 1:
PrintMatrix(GA,VT);//根据邻接矩阵输出二元组表示 break;
do {
cout<<"*欢迎进行最短路径选择界面!请输入您从哪个门进入!*\n"; cout<<"------------------------------------------------\n"<<endl;
cin>>chose2; switch(chose2)
{
case 1: cout<<"您选择的起点为东门"<<endl;
start=2;
Dijkstra(GA,dist,path,start,9); Print(path,start,VT); break; case 2: cout<<"您选择的起点为前门"<<endl;
start=0;
Dijkstra(GA,dist,path,start,9); Print(path,start,VT); break;
case 2:
case 3: cout<<"您选择的起点为后门"<<endl;
start=5;
Dijkstra(GA,dist,path,start,9); Print(path,start,VT); break;
case 0: system("cls");//清屏语句 cout<<"退出成功,返回主菜单!\n"<<endl;
break;
default: system("cls");//清屏语句 cout<<"您的输入有误,返回最短路径界面重新输入!"<<endl;
break;
}while(chose2!=0); break;
case 3:
do {
cout<<"*欢迎进入路径修改界面!*\n"; cin>>chose3; switch(chose3)
{
case 1: cout<<"请输入插入路径的起点"; cin>>insert1; cout<<"请输入插入路径的终点";
cin>>insert2;
cout<<"请输入插入路径的路长"; cin>>insert3;
change(insert1,insert2,insert3,GA); cout<<"插入成功!\n"<<endl; break;
case 2: cout<<"请输入修改路径的起点";
cin>>insert1;
cout<<"请输入修改路径的终点"; cin>>insert2;
cout<<"请输入修改路径的路长"; cin>>insert3;
change(insert1,insert2,insert3,GA); cout<<"修改成功!\n"<<endl;
break; case 3: cout<<"请输入删除路径的起点"; cin>>insert1; cout<<"请输入删除路径的终点";
cin>>insert2;
change(insert1,insert2,100000,GA); cout<<"删除成功!\n"<<endl; break; break;
case 0:
default: cout<<"您的输入有误,即将返回路径修改界面"<<endl;
break;
}while(chose3!=0);
system("cls");//清屏语句 break;
case 4: system("cls");//清屏语句
default: cout<<"您的输入有误,即将返回主菜单!\n\n\n"<<endl; }
break;
cout<<"退出成功~欢迎您再次使用本系统~O(∩_∩)O谢谢"<<endl; break;
}while(chose1!=4);
}
(5)画出函数的调用关系图。 系统子程序及功能设计
本系统共设置18个子程序,各子程序的函数名及功能说明如下。
(1)InitVT(VT,a);//传输顶点数据 (2)InitMatrix(GA,data);//传输结构体数据
(3)PrintMatrix(GA,VT);//根据邻接矩阵输出二元组表示 (4)Dijkstra(GA,dist,path,start,9);
Print(path,start,VT); // 用Dijkstra算法,求一个景点到其他景点间的最短路径,并打印
(5)change(insert1,insert2,insert3,GA);//修改图,包括增删边,修改权 (6)switch
函数主要调用关系图 图中数字是各函数的编号
五、算法实现 六、软件测试
七、技术讨论(可选) 八、收获与体会
本次实践让我们小组懂得如何运用图结构来编写与地图有关的查询程序,小组成员发挥团队合作精神,分工合作,各尽其职,在短时间内完成程序编写。 九、软件运行的部分截图及说明
主菜单界面
查询景点及路径
查询从东门进入各景点的最短路径
返回主菜单
修改路径页面
插入路径
退出程序
正在阅读:
最短距离问题数据结构课程设计报告07-17
2013年突发事件应急处理09-05
五星级酒店员工守则03-02
重庆售电侧改革试点问答01-20
德清县旅游产业发展总体规划(有用)10-28
策划书格式01-21
参观科技馆作文400字07-10
文明祭扫倡议书03-27
办公楼施工组织设计06-06
施工组织课程设计112-16
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 短距离
- 数据结构
- 课程
- 报告
- 问题
- 设计