数据结构:旅游路线图设计问题,、编写一个函数让用户输入这张图,用邻接表存储。且已有a—n的无向图
时间: 2024-03-26 21:39:32 浏览: 23
以下是一个实现旅游路线图设计问题的示例代码,使用邻接表存储:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
// 边表结点
typedef struct ArcNode{
int adjvex; // 邻接点在顶点数组中的位置下标
struct ArcNode *nextarc;// 指向下一个邻接点的指针
int weight; // 边的权重(景点间距离)
}ArcNode;
// 顶点表结点
typedef struct VNode{
char data; // 顶点的数据
ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
}VNode, AdjList[MAX_VERTEX_NUM];
// 图结构
typedef struct{
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
}ALGraph;
// 创建邻接表存储的无向图
void CreateGraph(ALGraph *G, char *vexs, int n, char *edges, int m){
int i, j, k, w;
ArcNode *p;
G->vexnum = n;
G->arcnum = m;
// 初始化顶点表
for(i = 0; i < n; i++){
G->vertices[i].data = vexs[i];
G->vertices[i].firstarc = NULL;
}
// 构造边表
for(k = 0; k < m; k++){
i = edges[k*3] - 'a'; // 边的起点
j = edges[k*3+1] - 'a'; // 边的终点
w = edges[k*3+2] - '0'; // 边的权重(景点间距离)
// 添加边(i, j)
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = w;
p->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
// 添加边(j, i)
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
p->weight = w;
p->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p;
}
}
// 打印邻接表存储的图
void PrintGraph(ALGraph G){
int i;
ArcNode *p;
for(i = 0; i < G.vexnum; i++){
printf("%c:", G.vertices[i].data);
p = G.vertices[i].firstarc;
while(p != NULL){
printf(" %c(%d)", G.vertices[p->adjvex].data, p->weight);
p = p->nextarc;
}
printf("\n");
}
}
int main(){
ALGraph G;
char vexs[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n'};
char edges[] = {
'a', 'b', '2', 'a', 'c', '4', 'a', 'd', '1', 'b', 'e', '3', 'c', 'f', '5',
'd', 'g', '6', 'e', 'h', '7', 'f', 'i', '8', 'g', 'j', '9', 'h', 'k', '10',
'i', 'l', '11', 'j', 'm', '12', 'k', 'n', '13'
};
CreateGraph(&G, vexs, 14, edges, 13);
PrintGraph(G);
return 0;
}
```
以上代码中,CreateGraph函数接收顶点数组和边数组作为参数,通过动态分配内存创建邻接表存储的无向图。PrintGraph函数打印邻接表存储的图。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)