当前位置： 首页 > news >正文

数据结构 实验 3

news 来源：原创 2024/9/19 8:57:54

题目一：最短路径dijkstra算法

一、实验目的

  1. 熟练图的邻接矩阵和邻接表表示法
  2. 掌握图的最短路径Dijkstra算法的基本思想
  3. 用C语言实现Dijkstra算法

二、实验内容

从键盘输入的数据创建图（图的存储结构采用邻接矩阵），设计Dijkstra算法求出源点到所有点的最短路径。

三、实验步骤

  1. 先定义邻接矩阵类型
  2. 根据键盘输入的数据创建图，输出邻接矩阵
  3. 设计Dijkstra算法并在VC下用C语言实现算法

四、实验要求

程序代码：

#include <iostream>
#define INF 2147483647L
using namespace std;int main()
{int n, side, sign, i, j, v, w, min, v0;int q, p, num;cout << "请输入图中的顶点个数：";cin >> n;cout << "请输入图中边的条数：";cin >> side;cout << "请选择是有向图还是无向图（有向图为1，无向图为0）：";cin >> sign;int arcs[n][n], S[n], D[n], path[n];for (i = 0; i < n; i++)for (j = 0; j < n; j++)arcs[i][j] = INF;for (i = 1; i <= side; i++){cout << "请输入第" << i << "条边的顶点和权值：";cin >> q >> p >> num;arcs[q - 1][p - 1] = num;if (sign == 0) arcs[p - 1][q - 1] = num;}cout << "你输入的有向带权图的邻接矩阵表示：" << endl;for (i = 0; i < n; i++)for (j = 0; j < n; j++){if (arcs[i][j] == INF) cout << "∞";else cout << arcs[i][j];if (j == n - 1) cout << endl;else cout << "  ";}cout << "请输入源点：";cin >> v0;for (v = 0; v < n; ++v){S[v] = 0;D[v] = arcs[v0 - 1][v];if (D[v] < INF) path[v] = v0 - 1;else path[v] = -1;}S[v0 - 1] = 1; D[v0 - 1] = 0;for (i = 1; i < n; ++i){min = INF;for (w = 0; w < n; ++w)if (!S[w] && D[w] < min){v = w; min = D[w];}S[v] = 1;for (w = 0; w < n; ++w)if (!S[w] && arcs[v][w] != INF && (D[v] + arcs[v][w] < D[w])){D[w] = D[v] + arcs[v][w];path[w] = v;}}i = 0;if (i == v0 - 1) i++;while (i < n){cout << "顶点" << v0 << "到顶点" << i + 1 << "的最短路径长度：" << D[i] << ",最短路径为：";int pa[n];for (j = 0; j < n; j++)pa[j] = -1;num = 0;q = i;while (path[q] != v0 - 1){pa[num] = path[q];q = path[q];num++;}cout << v0 << "-->";for (j = n - 1; j >= 0; j--){if (pa[j] != -1){cout << pa[j] + 1;cout << "-->";}}cout << i + 1;i++;if (i == v0 - 1) i++;cout << endl;}return 0;
}
  1. 用无向图A和做实验

 

最短路径和最短距离为（可选择不同的源点，本例以源点分别为1和2 示例）： 

 

 

2. 再用有向网 B 做实验

 

 

题目二：用dijkstra算法实现

故宫导游路线设计

问题描述：游客游览某一景点时，对景点不熟悉。特别是对于故宫这样的大型景点，如果随便参观的话，可能会错过一些景点，也可能走许多冤枉路。为了方便游客，需要一套软件系统。

为游客提供以下功能：

①查询景点信息；②给出到某个景点的最佳路线；③给出到所有景点的最佳路线。

为系统管理员提供以下功能：

①修改景点信息；②撤销旅游线路。

问题分析：景点和旅游线路可以抽象为网状结构，景点作为图的顶点，旅游线路作为图的边，边上的权值作为景点间的距离，如下图所示。查询景点信息就是输出相应顶点的信息；给出到景点的最佳线路就是求最短路径问题；撤销旅游线路就是删除边；修改景点信息就是修改顶点信息。

程序简介：本程序包含两个模块

（1） 数据结构的设计  

#include <iostream>
#include<cstring>
#include<cstdlib>
#define MaxVertexNum 50
#define MaxValue 5000 //表示两点之间距离为无穷大 
#define INF 5000
#include <stack> 
using namespace std;typedef struct  //景点类型 
{
int no;   //景点编号 
char name[20];   //景点名称 
char desc[100];   //景点简介 
}DataType; typedef struct
{
int arcs[MaxVertexNum][MaxVertexNum];  //邻接矩阵
DataType data[MaxVertexNum];   //顶点信息 
int vexnum;   //顶点数 
}MGraph,*AdjMatrix;

（2）主程序模块

int main()
{
AdjMatrix g;
char name[20];
int choice,v,i;
int end;
int dist[MaxVertexNum],path[MaxVertexNum],S[MaxVertexNum];
g=new MGraph;
DataType d[]={{0,"午门","午门是紫禁城的正门，午门有五个门洞，明三暗五。"},{1,"太和殿","俗称金銮殿，是紫禁城最高最大的宫殿，是朝廷举行重大
典礼的地方。"},{2,"乾清宫","是后三宫中最大的宫殿，是清朝康熙帝以前的皇帝居住的
寝宫。"},{3,"御花园","宫中最大花园，供帝后玩耍。"},{4,"神武门","紫禁城北门，故宫博物院正门。"},{5,"养心殿","雍正时期，皇帝的寝宫。"},{6,"西六宫","西六宫包括永寿宫、翊坤宫、储秀宫、咸福宫、长春宫和
启祥宫。"},{7,"东六宫","东六宫包括景仁宫、承乾宫、钟粹宫、景阳宫、永和宫和
延禧宫。"}};
int m[][MaxVertexNum]={
{MaxValue,1500,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue},
{1500,MaxValue,1000,MaxValue,MaxValue,800,MaxValue,MaxValue},
{MaxValue,1000,MaxValue,400,MaxValue,300,200,200},
{MaxValue,MaxValue,400,MaxValue,200,MaxValue,100,100},
{MaxValue,MaxValue,MaxValue,200,MaxValue,MaxValue,250,260},
{MaxValue,800,300,MaxValue,MaxValue,MaxValue,50,400},
{MaxValue,MaxValue,200,100,250,50,MaxValue,MaxValue},
{MaxValue,MaxValue,200,100,260,400,MaxValue,MaxValue}
};
CreateGraph(g,m,d,8);
PrintMatrix(g);
while(1)
{
cout<<"     故宫导游咨询系统"<<endl;
cout<<"**********主菜单**********"<<endl;
cout<<"     (1)显示所有景点信息"<<endl; 
cout<<"     (2)查询景点信息"<<endl; 
cout<<"     (3)给出到某个景点的最佳路线"<<endl; 
cout<<"     (4)给出到所有景点的最佳路线"<<endl; 
cout<<"     (5)修改景点信息"<<endl; 
cout<<"     (6)撤销旅游线路"<<endl; 		
cout<<"     (0)退出"<<endl; 
cout<<"请选择(1,2,3,4,5,6,0):";
cin>>choice;
if(choice<0||choice>6)
continue;
switch(choice)
{
case 1:
DisplayMatrix(g); break;
case 2:
cout<<"请输入景点名称:"; 
cin>>name;	
QueryVertex(g,name);
cout<<endl;			
break;
case 3:
cout<<"请输入你现在所在景点名称:";
cin>>name;
v=Locate(g,name);
cout<<"请输入你要去的景点名称:";
cin>>name;
end=Locate(g,name);
Dijkstra(g,dist,path,S,v);				Printpath(g,dist,path,v,end);
break; 
case 4:
cout<<"请输入你现在所在景点名称:";
cin>>name;
v=Locate(g,name);
Dijkstra(g,dist,path,S,v);
Printpath(g,dist,path,v); 
break;
case 5:
cout<<"请输入景点名称:";
cin>>name;
v=Locate(g,name); 
cout<<"请输入修改后的景点名称:";
cin>>name;
strcpy(g->data[v].name,name);
cout<<"请输入修改后的景点简介:";
cin>>name;
strcpy(g->data[v].desc,name);
break;
case 6:
cout<<"请输入起始景点名称:";
cin>>name;
v=Locate(g,name);
cout<<"请输入结束景点名称:";
cin>>name;
end=Locate(g,name);
g->arcs[v][end]=MaxValue;
break;
case 0:
exit(0);
default:
break;
} 
}
system("pause");
return 0;
}

（3）各个函数功能

  1. voidCreateGraph(AdjMatrix&g,intm[][MaxVertexNum],DataType d[],int n)       //根据图的顶点d和权值m创建邻接矩阵g
  2. void DisplayMatrix(AdjMatrix g) //显示所有景点信息
  3. void PrintMatrix(AdjMatrix g)       //打印邻接矩阵
  4. void QueryVertex(AdjMatrix g,char name[])    //根据景点名称查询景点信息
  5. int Locate(AdjMatrix g,char name[])   //根据景点名称查询景点序号
  6. void Dijkstra(AdjMatrix g,int dist[],int path[],int S[],int v)     //求最短路径长度
  7. void Printpath(AdjMatrix g,int dist[],int path[],int v)     // 输出最短路径长度和最短路径
  8. void Printpath(AdjMatrix g,int dist[],int path[],int v,int end)// 输出到某个顶点的最短路径长度和最短路径；

（4）系统界面显示效果

 

 

实验要求：

给出程序，使之能够实现基本的功能。

1. 显示所有景点信息

2. 查询景点信息

3. 给出到某个景点的最佳路线

4. 给出到所有景点的最佳路线

5. 修改景点信息

6. 撤销旅游路线

实验代码：

#include <iostream>
#include <cstring>
#include <cstdlib>
#define MaxVertexNum 5000
#define MaxValue 5000 //表示两点之间距离为无穷大 
#define INF 5000
#include <stack> 
using namespace std;typedef struct  //景点类型 
{int no;   //景点编号 char name[20];   //景点名称 char desc[100];   //景点简介 
}DataType; typedef struct
{int arcs[MaxVertexNum][MaxVertexNum];  //邻接矩阵DataType data[MaxVertexNum];   //顶点信息 int vexnum;   //顶点数 
}MGraph,*AdjMatrix;
void CreateGraph(AdjMatrix &g,int m[][MaxVertexNum],DataType d[],int n)
{g->vexnum=n;int i,j;for(i=0;i<g->vexnum;i++){g->data[i].no=d[i].no;strcpy(g->data[i].name,d[i].name);strcpy(g->data[i].desc,d[i].desc);for(j=0;j<g->vexnum;j++)g->arcs[i][j]=m[i][j];}
}
void PrintMatrix(AdjMatrix g)
{int i,j;cout<<"       午门 太和殿 乾清宫 御花园 神武门 养心殿 西六宫 东六宫"<<endl;for(i=0;i<g->vexnum;i++){cout<<g->data[i].name<<"  ";if(i==0) cout<<"  ";for(j=0;j<g->vexnum;j++) {if(g->arcs[i][j]==INF) cout<<"∞";else cout<<g->arcs[i][j];if(j==g->vexnum-1) cout<<endl;else cout<<"     "; }}
}
void DisplayMatrix(AdjMatrix g)
{int i;cout<<"景点编号  景点名称  景点简介"<<endl; for(i=0;i<g->vexnum;i++){cout<<g->data[i].no<<"  ";cout<<g->data[i].name<<"  ";cout<<g->data[i].desc<<endl;}
}
void QueryVertex(AdjMatrix g,char name[])	//根据景点名称查询景点信息
{int i,sign=0;for(i=0;i<g->vexnum;i++){if(strcmp(g->data[i].name,name)==0){cout<<"景点编号  景点名称  景点简介"<<endl;cout<<g->data[i].no<<"  ";cout<<g->data[i].name<<"  ";cout<<g->data[i].desc<<endl;sign=1;break;}}if(sign==0) cout<<"未找到该景点！"<<endl;
}
int Locate(AdjMatrix g,char name[])
{int i;for(i=0;i<g->vexnum;i++){if(strcmp(g->data[i].name,name)==0)return g->data[i].no;}
}
void Dijkstra(AdjMatrix g,int D[],int path[],int S[],int v0)	  //求最短路径长度
{int v,w,min,i;for(v=0;v<g->vexnum;++v){S[v]=0;D[v]=g->arcs[v0][v];if(D[v]<INF) path[v]=v0;else path[v]=-1;}S[v0]=1;D[v0]=0;for(i=1;i<g->vexnum;++i){min=INF;for(w=0;w<g->vexnum;++w)if(!S[w]&&D[w]<min){v=w;min=D[w];}S[v]=1;for(w=0;w<g->vexnum;++w)if(!S[w]&&(D[v]+g->arcs[v][w]<D[w])){D[w]=D[v]+g->arcs[v][w];path[w]=v; }}
}
void Printpath(AdjMatrix g,int D[],int path[],int v0)
{int i=0,num,q,j;if(i==v0) i++;while(i<g->vexnum){cout<<g->data[v0].name<<g->data[i].name<<"的最短路径长度："<<D[i]<<",最短路径为：";int pa[g->vexnum];for(j=0;j<g->vexnum;j++)pa[j]=-1;num=0;q=i;while(path[q]!=v0){pa[num]=path[q];q=path[q];num++;}cout<<g->data[v0].name<<"-->";for(j=g->vexnum-1;j>=0;j--){	if(pa[j]!=-1) {cout<<g->data[pa[j]].name;cout<<"-->";}}cout<<g->data[i].name;i++;if(i==v0) i++;cout<<endl;}
}
void Printpath(AdjMatrix g,int D[],int path[],int v0,int i)
{int num,q,j;cout<<g->data[v0].name<<g->data[i].name<<"的最短路径长度："<<D[i]<<",最短路径为：";int pa[g->vexnum];for(j=0;j<g->vexnum;j++)pa[j]=-1;num=0;q=i;while(path[q]!=v0){pa[num]=path[q];q=path[q];num++;}cout<<g->data[v0].name<<"-->";for(j=g->vexnum-1;j>=0;j--){	if(pa[j]!=-1) {cout<<g->data[pa[j]].name;cout<<"-->";}}cout<<g->data[i].name<<endl;
}int main()
{AdjMatrix g;char name[20];int choice,v,i;int end;int D[MaxVertexNum],path[MaxVertexNum],S[MaxVertexNum];g=new MGraph;DataType d[]={{0,"午门","午门是紫禁城的正门，午门有五个门洞，明三暗五。"},{1,"太和殿","俗称金銮殿，是紫禁城最高最大的宫殿，是朝廷举行重大典礼的地方。"},{2,"乾清宫","是后三宫中最大的宫殿，是清朝康熙帝以前的皇帝居住的寝宫。"},{3,"御花园","宫中最大花园，供帝后玩耍。"},{4,"神武门","紫禁城北门，故宫博物院正门。"},{5,"养心殿","雍正时期，皇帝的寝宫。"},{6,"西六宫","西六宫包括永寿宫、翊坤宫、储秀宫、咸福宫、长春宫和启祥宫。"},{7,"东六宫","东六宫包括景仁宫、承乾宫、钟粹宫、景阳宫、永和宫和延禧宫。"}};int m[][MaxVertexNum]={{MaxValue,1500,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue},{1500,MaxValue,1000,MaxValue,MaxValue,800,MaxValue,MaxValue},{MaxValue,1000,MaxValue,400,MaxValue,300,200,200},{MaxValue,MaxValue,400,MaxValue,200,MaxValue,100,100},{MaxValue,MaxValue,MaxValue,200,MaxValue,MaxValue,250,260},{MaxValue,800,300,MaxValue,MaxValue,MaxValue,50,400},{MaxValue,MaxValue,200,100,250,50,MaxValue,MaxValue},{MaxValue,MaxValue,200,100,260,400,MaxValue,MaxValue}};CreateGraph(g,m,d,8);PrintMatrix(g);while(1){cout<<"     故宫导游咨询系统"<<endl;cout<<"**********主菜单**********"<<endl;cout<<"     (1)显示所有景点信息"<<endl; cout<<"     (2)查询景点信息"<<endl; cout<<"     (3)给出到某个景点的最佳路线"<<endl; cout<<"     (4)给出到所有景点的最佳路线"<<endl; cout<<"     (5)修改景点信息"<<endl; cout<<"     (6)撤销旅游线路"<<endl; 		cout<<"     (0)退出"<<endl; cout<<"请选择(1,2,3,4,5,6,0):";cin>>choice;if(choice<0||choice>6)continue;switch(choice){case 1:DisplayMatrix(g); break;case 2:cout<<"请输入景点名称:"; cin>>name;	QueryVertex(g,name);cout<<endl;			break;case 3:cout<<"请输入你现在所在景点名称:";cin>>name;v=Locate(g,name);cout<<"请输入你要去的景点名称:";cin>>name;end=Locate(g,name);Dijkstra(g,D,path,S,v);			Printpath(g,D,path,v,end);break; case 4:cout<<"请输入你现在所在景点名称:";cin>>name;v=Locate(g,name);Dijkstra(g,D,path,S,v);Printpath(g,D,path,v);break;case 5:cout<<"请输入景点名称:";cin>>name;v=Locate(g,name); cout<<"请输入修改后的景点名称:";cin>>name;strcpy(g->data[v].name,name);cout<<"请输入修改后的景点简介:";cin>>name;strcpy(g->data[v].desc,name);break;case 6:cout<<"请输入起始景点名称:";cin>>name;v=Locate(g,name);cout<<"请输入结束景点名称:";cin>>name;end=Locate(g,name);g->arcs[v][end]=MaxValue;g->arcs[end][v]=MaxValue;PrintMatrix(g);break;case 0:exit(0);default:break;} }system("pause");return 0;
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Apache部署与配置
  • 存储产品选型策略 OSS生命周期管理与运维
  • HTTP入门
  • Dify中的weaviate向量数据库操作
  • openssh9.8p1更新 修复漏洞（CVE-2024-6387）
  • 成为编程大佬！！——数据结构与算法（1）——算法复杂度！！
  • 伯克利、斯坦福和CMU面向具身智能端到端操作联合发布开源通用机器人Policy，可支持多种机器人执行多种任务
  • 2.Date类型的请求参数
  • 模拟面试001-Java开发工程师+简历+问题+回答
  • 昇思25天学习打卡营第1天|小试牛刀
  • 虚幻引擎中增强输入映射中鼠标输入无反应，怎么办？
  • SQLite 命令行客户端 + HTA 实现简易UI
  • 深入解析CSS中的!important规则：优先级与最佳实践
  • 企业数字化转型中的低代码开发平台应用：释放创新潜能
  • ADOQuery 查询MSSQL存储过程一个莫名其妙的错误；
  • k8s如何管理Pod
  • Less 日常用法
  • React+TypeScript入门
  • SpriteKit 技巧之添加背景图片
  • 函数式编程与面向对象编程[4]:Scala的类型关联Type Alias
  • 前端面试之CSS3新特性
  • 入手阿里云新服务器的部署NODE
  • 深度学习在携程攻略社区的应用
  • 吴恩达Deep Learning课程练习题参考答案——R语言版
  • 找一份好的前端工作，起点很重要
  • 自制字幕遮挡器
  • 你学不懂C语言，是因为不懂编写C程序的7个步骤 ...
  • ​虚拟化系列介绍（十）
  • ​一文看懂数据清洗：缺失值、异常值和重复值的处理
  • # 20155222 2016-2017-2 《Java程序设计》第5周学习总结
  • #define，static，const，三种常量的区别
  • （￥1011）－（一千零一拾一元整）输出
  • （6）添加vue-cookie
  • （ｃ语言）strcpy函数用法
  • （博弈 sg入门）kiki's game -- hdu -- 2147
  • （机器学习的矩阵）（向量、矩阵与多元线性回归）
  • （每日一问）计算机网络：浏览器输入一个地址到跳出网页这个过程中发生了哪些事情？（废话少说版）
  • （七）MySQL是如何将LRU链表的使用性能优化到极致的？
  • （算法）Game
  • （学习日记）2024.01.09
  • (转)chrome浏览器收藏夹（书签）的导出与导入
  • （转）创业家杂志：UCWEB天使第一步
  • （转载）PyTorch代码规范最佳实践和样式指南
  • .equal()和==的区别 怎样判断字符串为空问题： Illegal invoke-super to void nio.file.AccessDeniedException
  • .Net Core 中间件验签
  • .NET6 开发一个检查某些状态持续多长时间的类
  • .net8.0与halcon编程环境构建
  • .net利用SQLBulkCopy进行数据库之间的大批量数据传递
  • .net之微信企业号开发(一) 所使用的环境与工具以及准备工作
  • [ C++ ] STL_vector -- 迭代器失效问题
  • [023-2].第2节：SpringBoot中接收参数相关注解
  • [20171113]修改表结构删除列相关问题4.txt
  • [C++]运行时,如何确保一个对象是只读的
  • [flink]部署模式
  • [HDU5685]Problem A