数据结构实训(大作业)c++模拟北斗卫星导航系统简单的迪杰斯特拉算法

简介: 数据结构实训(大作业)c++模拟北斗卫星导航系统简单的迪杰斯特拉算法

实现功能:

 

直接给出代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <vector>
using namespace std;
const int N = 100;
unordered_map<string, int> umap_ci; //城市_数字的映射
unordered_map<int, string> umap_ic; //数字_城市
int g[N][N];
int st[N], dist[N], pre[N], del[N];
int n = 19, idx = 20;
void init()
{
    memset(g, 0x3f, sizeof g);
    umap_ci["北京"] = 1;
    umap_ci["天津"] = 2;
    umap_ci["郑州"] = 3;
    umap_ci["徐州"] = 4;
    umap_ci["上海"] = 5;
    umap_ci["武汉"] = 6;
    umap_ci["南昌"] = 7;
    umap_ci["株洲"] = 8;
    umap_ci["福州"] = 9;
    umap_ci["广州"] = 10;
    umap_ci["深圳"] = 11;
    umap_ci["西宁"] = 12;
    umap_ci["柳州"] = 13;
    umap_ci["贵阳"] = 14;
    umap_ci["昆明"] = 15;
    umap_ci["成都"] = 16;
    umap_ci["西安"] = 17;
    umap_ci["兰州"] = 18;
    umap_ci["南宁"] = 19;
    umap_ic[1] = "北京";
    umap_ic[2] = "天津";
    umap_ic[3] = "郑州";
    umap_ic[4] = "徐州";
    umap_ic[5] = "上海";
    umap_ic[6] = "武汉";
    umap_ic[7] = "南昌";
    umap_ic[8] = "株洲";
    umap_ic[9] = "福州";
    umap_ic[10] = "广州";
    umap_ic[11] = "深圳";
    umap_ic[12] = "西宁";
    umap_ic[13] = "柳州";
    umap_ic[14] = "贵阳";
    umap_ic[15] = "昆明";
    umap_ic[16] = "成都";
    umap_ic[17] = "西安";
    umap_ic[18] = "兰州";
    umap_ic[19] = "南宁";
    //建立无向边
    g[1][2] = g[2][1] = 137;
    g[1][3] = g[3][1] = 695;
    g[2][4] = g[4][2] = 674;
    g[3][4] = g[4][3] = 349;
    g[3][6] = g[6][3] = 534;
    g[3][17] = g[17][3] = 511;
    g[4][5] = g[5][4] = 651;
    g[5][7] = g[7][5] = 825;
    g[6][8] = g[8][6] = 409;
    g[7][8] = g[8][7] = 367;
    g[7][9] = g[9][7] = 622;
    g[8][10] = g[10][8] = 675;
    g[8][13] = g[13][8] = 672;
    g[8][14] = g[14][8] = 902;
    g[10][11] = g[11][10] = 140;
    g[19][13] = g[13][19] = 255;
    g[13][14] = g[14][13] = 607;
    g[14][16] = g[16][14] = 967;
    g[14][15] = g[15][14] = 639;
    g[15][16] = g[16][15] = 1100;
    g[16][17] = g[17][16] = 842;
    g[17][18] = g[18][17] = 676;
    g[18][12] = g[12][18] = 216;
}
int dijkstra(int startId, int endId)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    memset(pre, 0, sizeof pre);
    dist[startId] = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
        {
            if (!st[j] && !del[j] && (dist[t] > dist[j] || t == -1))
                t = j;
        }
        st[t] = 1;
        if (t == endId) break;
        for (int k = 1; k <= n; k++)
        {
            if (dist[k] > dist[t] + g[t][k])
            {
                dist[k] = dist[t] + g[t][k];
                pre[k] = t;
            }
        }
    }
    if (dist[endId] == 0x3f3f3f3f)  return -1;
    else return dist[endId];
}
bool add(string a)
{
    if (idx > 100)  return 0;
    umap_ci[a] = idx; umap_ic[idx] = a;
    string city; int w;
    cout << "请输入相连的城市及其距离: " << endl;
    while (cin >> city >> w)
    {
        if (city == "0" && w == 0)   break; //输入错误数据会结束
        int id = umap_ci[city];
        g[id][idx] = g[idx][id] = w;
    }
    idx++; n++;
    return 1;
}
bool delCity(string a)
{
    if (umap_ci.find(a) == umap_ci.end())   return 0;
    int id = umap_ci[a];
    del[id] = 1;
    for (int i = 1; i <= n; i++)
        g[id][i] = g[i][id] = 0x3f3f3f3f;
    return 1;
}
void findAdjacencyPoint(string city)
{
    int id = umap_ci[city];
    cout << "临界点:";
    for (int i = 1; i <= n; i++)
    {
        if (g[id][i] < 0x3f3f3f3f)
            cout << umap_ic[i] << " ";
    }
    cout << endl;
}
bool modify(string start, string end, int w)
{
    int startId = umap_ci[start];
    int endId = umap_ci[end];
    if (del[startId] || del[endId] || umap_ci.find(start) == umap_ci.end() || umap_ci.find(end) == umap_ci.end())
    {
        cout << "起点或者终点城市没有添加过或者已经被删除" << endl;
        return false;
    }
    if (w <= 0 || w >= 0x3f3f3f3f)
    {
        cout << "输入的距离不是一个合理的值!!!" << endl;
        return false;
    }
    g[startId][endId] = g[endId][startId] = w;
    return true;
}
void findShortestPath()
{
    string start, end;
    vector<string> v;  //存储路径的向量
    cout << "请输入起始地和目标地点: " << endl;
    cin >> start >> end;
    int startId = umap_ci[start];
    int endId = umap_ci[end];
    if (del[startId] || del[endId] || umap_ci.find(start) == umap_ci.end() || umap_ci.find(end) == umap_ci.end())
    {
        cout << "起点或者终点城市没有添加过或者已经被删除" << endl;
        return;
    }
    int t = dijkstra(startId, endId);
    if (t == -1)
    {
        cout << "城市" << " " << start << " " << "到不了城市 " << end << " " << endl;
        return;
    }
    while (endId)
    {
        v.push_back(umap_ic[endId]);
        if (endId == startId)  break;
        endId = pre[endId];
    }
    cout << "经过的最短路径为: " << endl;
    for (int i = v.size() - 1; i >= 0; i--)
        cout << v[i] << "->";
    cout << t << endl;
}
void mune()
{
    cout << "----------------------------------------------------" << endl;
    cout << "1.    添加城市" << endl;
    cout << "2.    删除城市" << endl;
    cout << "3.    查询最短路径" << endl;
    cout << "4.    查询相邻城市" << endl;
    cout << "5.    修改两个城市之间的距离" << endl;
}
int main()
{
    init();
    mune();
    int op = -1;
    while (true)
    {
        cout << "请选择要进行的操作(输入为0结束程序): " << endl;
        cin >> op;
        if (op == 0)    return 0;
        switch (op)
        {
        case 1:
        {
            cout << "请输入你要添加的城市名字: " << endl;
            string a; cin >> a;
            if (add(a))
                cout << "添加" << a << "城市成功" << endl;
            else
                cout << "城市已到达上限" << endl;
            break;
        }
        case 2:
        {
            cout << "请输入你要删除的城市: " << endl;
            string a; cin >> a;
            if (delCity(a))
                cout << "删除城市" << a << "成功" << endl;
            else
                cout << "删除城市失败,请检查输入的城市是否错在" << endl;
            break;
        }
        case 3:
        {
            findShortestPath();
            break;
        }
        case 4:
        {
            cout << "请输入城市: " << endl;
            string a; cin >> a;
            findAdjacencyPoint(a);
            break;
        }
        case 5:
        {
            cout << "请输入你要修改的城市名字,及其要修改的距离" << endl;
            string a, b; int w;
            cin >> a >> b >> w;
            modify(a, b, w);
            break;
        }
        }
    }
}
目录
相关文章
|
3月前
|
算法 C语言 C++
C++语言学习指南:从新手到高手,一文带你领略系统编程的巅峰技艺!
【8月更文挑战第22天】C++由Bjarne Stroustrup于1985年创立,凭借卓越性能与灵活性,在系统编程、游戏开发等领域占据重要地位。它继承了C语言的高效性,并引入面向对象编程,使代码更模块化易管理。C++支持基本语法如变量声明与控制结构;通过`iostream`库实现输入输出;利用类与对象实现面向对象编程;提供模板增强代码复用性;具备异常处理机制确保程序健壮性;C++11引入现代化特性简化编程;标准模板库(STL)支持高效编程;多线程支持利用多核优势。虽然学习曲线陡峭,但掌握后可开启高性能编程大门。随着新标准如C++20的发展,C++持续演进,提供更多开发可能性。
80 0
|
13天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
2月前
|
存储 算法 安全
超级好用的C++实用库之sha256算法
超级好用的C++实用库之sha256算法
97 1
|
2月前
|
C++
【C++案例】一个项目掌握C++基础-通讯录管理系统
这篇文章通过一个通讯录管理系统的C++项目案例,详细介绍了如何使用C++实现添加、显示、删除、查找、修改和清空联系人等功能。
43 3
|
1月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
22 0
|
1月前
|
机器学习/深度学习 算法 数据处理
EM算法对人脸数据降维(机器学习作业06)
本文介绍了使用EM算法对人脸数据进行降维的机器学习作业。首先通过加载ORL人脸数据库,然后分别应用SVD_PCA、MLE_PCA及EM_PCA三种方法实现数据降维,并输出降维后的数据形状。此作业展示了不同PCA变种在人脸数据处理中的应用效果。
34 0
|
2月前
|
算法 调度
作业调度算法_先来先服务算法_短作业优先算法_高响应比优先算法
本文介绍了作业调度算法,包括先来先服务(FCFS)、短进程优先(SJF)和高响应比优先(HRRN)算法。通过分析进程的到达时间和所需CPU服务时间,计算进程的开始时间、完成时间、平均周转时间和平均带权周转时间,以评估不同算法的性能。FCFS适合长作业,SJF适合短作业,而HRRN则综合了两者的优点。
86 12
|
3月前
|
算法
算法设计与分析作业
这篇文章是关于算法设计与分析的作业,其中包含了两个算法实现:一个是使用分治算法实现的十进制大整数相乘(包括加法、减法和乘法函数),并进行了正确性和健壮性测试;另一个是使用快速排序思想实现的分治查找第K小元素的程序,并分析了其平均和最坏时间复杂度。
算法设计与分析作业
|
1月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
1月前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)