运用好c++处理设计一个校园导游程序为来访的客人提供各种信息查询。(校园平面是一个无向图) 参考图示: 基本要求: 1)设计学校的旗山校区北区校园平面图,所含场所不少于 10 个。以图中顶点表示校 内各场所,存放场所名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。 2)为来访客人提供图中任意场所相关信息的查询。 3)为来访客人提供图中任意场所的问路查询,即查询任意两个景点之间的一条最短的简单路径。 要求:(1)实现场所增加、删除、查询 (2)实现路径的增加、删除 (3)数据的保存、调入。
时间: 2024-02-27 14:54:47 浏览: 84
这是一个比较复杂的项目,需要涉及到图的遍历、最短路径算法等知识点,下面是一个基本的实现思路,供您参考:
1. 定义场所和路径的数据结构
可以使用结构体来表示一个场所或一条路径,例如:
```c++
struct Place {
string name; // 场所名称
int code; // 场所代号
string intro; // 场所简介
};
struct Path {
int from; // 起点代号
int to; // 终点代号
int length; // 路径长度
};
```
2. 构建校园平面图
可以使用邻接表来表示一个无向图,其中每个顶点对应一个场所,每个边对应一条路径。例如:
```c++
vector<Path> adjList[N]; // 邻接表,N为顶点数
void addPath(int from, int to, int length) {
adjList[from].push_back({from, to, length});
adjList[to].push_back({to, from, length});
}
```
3. 实现场所和路径的增加、删除、查询
可以使用向量或map等数据结构来存储场所和路径信息,并实现相关的增加、删除、查询函数。例如:
```c++
vector<Place> places; // 场所向量
void addPlace(string name, int code, string intro) {
places.push_back({name, code, intro});
}
void removePlace(int code) {
for (auto& p : places) {
if (p.code == code) {
// 删除场所
// ...
break;
}
}
}
vector<Path> paths; // 路径向量
void addPath(int from, int to, int length) {
paths.push_back({from, to, length});
}
void removePath(int from, int to) {
for (auto& p : paths) {
if (p.from == from && p.to == to) {
// 删除路径
// ...
break;
}
}
}
Place* findPlace(int code) {
for (auto& p : places) {
if (p.code == code) {
return &p;
}
}
return nullptr;
}
Path* findPath(int from, int to) {
for (auto& p : paths) {
if (p.from == from && p.to == to) {
return &p;
}
}
return nullptr;
}
```
4. 实现最短路径算法
可以使用Dijkstra算法或BFS算法来求解最短路径。例如:
```c++
vector<int> dijkstra(int start, int end) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> dist(N, INF);
vector<int> prev(N, -1);
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (u == end) break;
if (dist[u] < d) continue;
for (auto& e : adjList[u]) {
int v = e.to;
int w = e.length;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
prev[v] = u;
pq.push({dist[v], v});
}
}
}
vector<int> path;
for (int u = end; u != -1; u = prev[u]) {
path.push_back(u);
}
reverse(path.begin(), path.end());
return path;
}
```
5. 实现数据的保存、调入
可以使用文件读写来实现数据的保存和调入。例如:
```c++
void saveData(string filename) {
ofstream fout(filename);
if (!fout.is_open()) {
// ...
}
// 写入场所信息
for (auto& p : places) {
fout << p.name << "," << p.code << "," << p.intro << endl;
}
fout << "#\n"; // 场所信息结束符
// 写入路径信息
for (auto& p : paths) {
fout << p.from << "," << p.to << "," << p.length << endl;
}
fout << "#\n"; // 路径信息结束符
fout.close();
}
void loadData(string filename) {
ifstream fin(filename);
if (!fin.is_open()) {
// ...
}
string line;
char c;
// 读入场所信息
while (getline(fin, line)) {
if (line == "#") break;
stringstream ss(line);
string name, intro;
int code;
getline(ss, name, ',');
ss >> code;
ss >> c; // 读入','
getline(ss, intro);
addPlace(name, code, intro);
}
// 读入路径信息
while (getline(fin, line)) {
if (line == "#") break;
stringstream ss(line);
int from, to, length;
ss >> from;
ss >> c; // 读入','
ss >> to;
ss >> c; // 读入','
ss >> length;
addPath(from, to, length);
}
fin.close();
}
```
以上是一个简单的实现思路,具体实现过程可能还需要根据具体需求进行调整。希望对您有帮助!
阅读全文