数据结构实验 3

🕗 发布于 2024-07-10 06:10 数据结构 实验 c++ c语言 算法

题目一：最短路径dijkstra算法

一、实验目的

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

二、实验内容

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

三、实验步骤

先定义邻接矩阵类型
根据键盘输入的数据创建图，输出邻接矩阵
设计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;
}

用无向图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）各个函数功能

voidCreateGraph(AdjMatrix&g,intm[][MaxVertexNum],DataType d[],int n) //根据图的顶点d和权值m创建邻接矩阵g
void DisplayMatrix(AdjMatrix g) //显示所有景点信息
void PrintMatrix(AdjMatrix g) //打印邻接矩阵
void QueryVertex(AdjMatrix g,char name[]) //根据景点名称查询景点信息
int Locate(AdjMatrix g,char name[]) //根据景点名称查询景点序号
void Dijkstra(AdjMatrix g,int dist[],int path[],int S[],int v) //求最短路径长度
void Printpath(AdjMatrix g,int dist[],int path[],int v) // 输出最短路径长度和最短路径
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;
}

原文地址：https://blog.csdn.net/2303_82182099/article/details/140306195

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：等保测评新趋势：应对数字化转型中的安全挑战
下一篇：【机器学习】作业 Exam1

格式串详解
不同语言格式串五花八门，究其本质，无非是如何处理格式串和变量对应关系。
阅读更多2024-09-25
如何恢复被删除的 GitLab 项目？
本文分享如何使用极狐GitLab 的项目延迟删除功能来避免仓库被用户误操作。该功能设置了删除延时时间，在延时期间内，用户还可以对项目进行恢复。极狐GitLab 群组、项目的删除保护功能，主要是为了防止
阅读更多2024-09-25
AI学习指南深度学习篇-Adagrad的基本原理
深度学习作为人工智能领域的重要分支，已经在各个领域取得了显著成就。在深度学习的模型训练过程中，参数优化是一个关键的环节，而学习率的选择对于训练结果有着至关重要的影响。Adagrad是一种自适应学习率算
阅读更多2024-09-25
Java:继承和多态（1）
在 Java SE 中，和是面向对象编程（OOP）的两个核心概念。通过继承，子类可以复用父类的代码；而通过多态，子类可以在不修改父类的前提下定义自己的行为。这两者结合起来使得代码更具扩展性、灵活性和可
阅读更多2024-09-25
Spring Boot集成PageHelper分页插件详解
PageHelper是一个强大的MyBatis分页插件，它简化了分页逻辑的实现，使得开发者可以更专注于业务逻辑。通过在Spring Boot项目中集成PageHelper，我们可以轻松地实现分页功能，
阅读更多2024-09-25
springboot体会BIO（阻塞式IO）
我们一样还是先启动服务端，再启动客户端1和客户端2，使用客户端1和客户端2向服务端写入消息，通过上述的例子我们得知，服务端会先处理客户端1的请求，客户端2的请求会阻塞。我们使用客户端1写入数据，再观察
阅读更多2024-09-25
Spring Boot之Actuator介绍
Spring Boot Actuator 是一个强大的工具，用于监控和管理 Spring Boot 应用。通过提供一系列内置的端点，它使得你可以轻松地获取应用程序的运行时信息，并进行必要的调整。此外，
阅读更多2024-09-25
编程的奥秘
1. **人工智能与机器学习**：随着算法和计算能力的提升，人工智能和机器学习将在更多领域得到应用，编程将成为连接现实世界与智能系统的关键。3. **编程范式**：包括面向过程、面向对象、函数式等多种
阅读更多2024-09-25
设计师一定要收藏好这6个网站，设计必备
新手设计师找免费素材，找灵感就上这6个网站，赶紧收藏好
阅读更多2024-09-25
Dockerfile的详解与案例
Dockerfile 是一个用来构建 Docker 镜像的文本文件，它包含了一系列指令，用于描述如何创建一个 Docker 镜像。通过 Dockerfile，你可以定义镜像的基础环境、安装软件包、设置
阅读更多2024-09-25

数据结构 实验 3

题目一：最短路径dijkstra算法

题目二：用dijkstra算法实现

故宫导游路线设计

相关文章

数据结构实验 3