官方接单发单平台上线!有接单发单需求的请直接发布需求,或注册接单!点击此处查看详情!

C++旅游景区推荐作业数据结构图论

时间:2023-12-11 浏览:270 分类:C/C++程序代做

91代做网-专注各种程序代做

包括但不限于:各类毕设课设、作业辅导、代码答疑、报告论文、商业程序开发、论文复现和小程序开发等。

也欢迎各行业程序员加入我们,具体请联系客服详聊:QQ号:,微信号:,接单Q群:

本次作业要求完成一个编程项目。请虚构一张旅游景区地图,景区地图包括 景点(结点)和道路(边):地图上用字母标注出一些点,表示景点(比如,以 点 A、B、C、D 等表示,其中的两个字母 A 和 B 分别表示景区的入口和出口); 点与点之间的连线表示各景点之间的道路,连线的权重表示两景点间的距离。在 程序里,请选择适当的数据结构表达你设计的景区地图,请通过编程实现以下功 能:
1) 用 printf 语句打印出景区地图:要求用不同颜色表示景点和道路;
2) 为游客提供地图中任意景点相关信息的查询:设计查询指令,用户可以
   输入这些指令查询每个景点的信息;
3) 计算从某一景点到另一个景点的最短路径:用户输入两个景点的字母代
   号,程序可以在地图中使用不同于已使用的颜色表达出最短路径;
4) 计算从入口 A 到出口 B 的最短路径;
5) 游客甲从景区入口进入,请用程序帮他自动计算出一条最佳
游览路线(通过所有景点且距离最短),最后到达出口。
6) 某旅游团时间有限,导致其游览的总距离受限,请设计算法, 产生一个从入口开始最后回到入口的环路,让他们可以在有限的总距离
内游览尽量多的景点。

为了完成这个编程项目,我们可以使用图的数据结构来表示景区地图。具体实现可以采用邻接矩阵或邻接表。

首先,我们需要定义景点和道路的数据结构。可以创建一个名为"Spot"的类来表示景点,包含属性如名称、描述等。另外,我们可以创建一个名为"Road"的类来表示道路,包含属性如起点、终点、距离等。

接下来,我们可以创建一个名为"Map"的类来表示整个景区地图。这个类可以包含一个字典来存储景点的信息,键为景点的字母标识,值为对应的Spot对象。同时,我们还可以使用邻接矩阵或邻接表来存储道路的信息。

下面是一个可能的实现示例:

#include <iostream>
#include <vector>
#include <map>
#include <queue>

using namespace std;

// 景点结点
struct Spot {
    char id; // 景点字母代号
    string name; // 景点名称
};

// 道路边
struct Road {
    Spot start; // 起点景点
    Spot end; // 终点景点
    int distance; // 距离
};

class Map {
private:
    map<char, Spot> spots; // 存储景点信息的字典
    vector<Road> roads; // 存储道路信息的列表

public:
    // 添加景点
    void addSpot(char id, string name) {
        Spot spot;
        spot.id = id;
        spot.name = name;
        spots[id] = spot;
    }

    // 添加道路
    void addRoad(char startId, char endId, int distance) {
        Road road;
        road.start = spots[startId];
        road.end = spots[endId];
        road.distance = distance;
        roads.push_back(road);
    }

    // 打印景区地图
    void printMap() {
        for (auto it = spots.begin(); it != spots.end(); ++it) {
            cout << "景点 " << it->second.name << endl;
        }
        for (const auto& road : roads) {
            cout << "从 " << road.start.name << " 到 " << road.end.name << " 的距离为 " << road.distance << endl;
        }
    }

    // 查询景点信息
    void querySpotInfo(char id) {
        Spot spot = spots[id];
        cout << "景点名称: " << spot.name << endl;
    }

    // 计算最短路径
    void calculateShortestPath(char startId, char endId) {
        map<char, int> distance; // 存储起点到各个景点的最短距离
        map<char, char> previous; // 存储前一个景点

        // 初始化距离为无穷大
        for (auto it = spots.begin(); it != spots.end(); ++it) {
            distance[it->first] = INT_MAX;
        }

        // 设置起点距离为0
        distance[startId] = 0;

        // 使用Dijkstra算法计算最短路径
        priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> pq;
        pq.push(make_pair(0, startId));

        while (!pq.empty()) {
            char currentId = pq.top().second;
            pq.pop();

            for (const auto& road : roads) {
                if (road.start.id == currentId) {
                    int newDistance = distance[currentId] + road.distance;
                    if (newDistance < distance[road.end.id]) {
                        distance[road.end.id] = newDistance;
                        previous[road.end.id] = currentId;
                        pq.push(make_pair(newDistance, road.end.id));
                    }
                }
            }
        }

        // 输出最短路径
        cout << "从 " << spots[startId].name << " 到 " << spots[endId].name << " 的最短路径为:" << endl;
        char currentId = endId;
        while (currentId != startId) {
            cout << spots[currentId].name << " <- ";
            currentId = previous[currentId];
        }
        cout << spots[startId].name << endl;
    }

    // 计算从入口到出口的最短路径
    void calculateEntranceToExitPath(char entranceId, char exitId) {
        calculateShortestPath(entranceId, exitId);
    }

    // 计算最佳游览路线
    void calculateBestRoute(char entranceId, char exitId) {
        vector<char> path; // 存储游览路线
        path.push_back(entranceId);

        // 使用贪心算法计算最佳游览路线
        char currentSpot = entranceId;
        while (currentSpot != exitId) {
            int minDistance = INT_MAX;
            char nextSpot;

            for (const auto& road : roads) {
                if (road.start.id == currentSpot) {
                    if (find(path.begin(), path.end(), road.end.id) == path.end() && road.distance < minDistance) {
                        minDistance = road.distance;
                        nextSpot = road.end.id;
                    }
                }
            }

            path.push_back(nextSpot);
            currentSpot = nextSpot;
        }

        // 输出最佳游览路线
        cout << "最佳游览路线为:" << endl;
        for (const auto& spot : path) {
            cout << spots[spot].name << " -> ";
        }
        cout << spots[exitId].name << endl;
    }

    // 计算有限距离内的环路
    void calculateLimitedDistanceRoute(char entranceId, int maxDistance) {
        vector<char> path; // 存储环路
        path.push_back(entranceId);

        // 使用深度优先搜索算法计算有限距离内的环路
        dfs(entranceId, entranceId, maxDistance, 0, path);
    }

private:
    // 深度优先搜索算法
    void dfs(char startSpot, char currentSpot, int maxDistance, int totalDistance, vector<char>& path) {
        if (totalDistance > maxDistance) {
            return;
        }

        if (totalDistance > 0 && currentSpot == startSpot) {
            // 输出环路
            cout << "有限距离内的环路为:" << endl;
            for (const auto& spot : path) {
                cout << spots[spot].name << " -> ";
            }
            cout << spots[startSpot].name << endl;
        }

        for (const auto& road : roads) {
            if (road.start.id == currentSpot && find(path.begin(), path.end(), road.end.id) == path.end()) {
                path.push_back(road.end.id);
                dfs(startSpot, road.end.id, maxDistance, totalDistance + road.distance, path);
                path.pop_back();
            }
        }
    }
};

int main() {
    Map map;

    // 添加景点
    map.addSpot('A', "入口");
    map.addSpot('B', "景点B");
    map.addSpot('C', "景点C");
    map.addSpot('D', "景点D");
    map.addSpot('E', "景点E");
    map.addSpot('F', "出口");

    // 添加道路
    map.addRoad('A', 'B', 5);
    map.addRoad('A', 'C', 10);
    map.addRoad('B', 'D', 8);
    map.addRoad('B', 'E', 15);
    map.addRoad('C', 'D', 6);
    map.addRoad('D', 'F', 12);
    map.addRoad('E', 'F', 7);

    // 打印景区地图
    map.printMap();
    cout << endl;

    // 查询景点信息
    map.querySpotInfo('B');
    cout << endl;

    // 计算最短路径
    map.calculateShortestPath('A', 'D');
    cout << endl;

    // 计算从入口到出口的最短路径
    map.calculateEntranceToExitPath('A', 'F');
    cout << endl;

    // 计算最佳游览路线
    map.calculateBestRoute('A', 'F');
    cout << endl;

    // 计算有限距离内的环路
    map.calculateLimitedDistanceRoute('A', 35);

    return 0;
}


客服