建立一个无向图,采用邻接表做为存储结构。输入信息为:第一行给出图的顶点数n和边数e。第二行给出n个字符,表示n个顶点的数据元素的值。后面是e行,给出每一条边的两个顶点的值(顶点之间无空格)。 输出每个顶点的值以及各顶点的邻接点的值。 输入样例: 7 9 0123456 02 03 04 13 15 23 25 45 56 输出样例: 0: 4 3 2 1: 5 3 2: 5 3 0 3: 2 1 0 4: 5 0 5: 6 4 2 1 6: 5
时间: 2024-03-23 20:38:42 浏览: 48
以下是建立无向图的邻接表并输出的完整代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode { // 边表结点
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode { // 顶点信息
char data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode;
typedef struct { // 图
VNode adjlist[MAX_VERTEX_NUM]; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} Graph;
int LocateVex(Graph G, char v) {
int i;
for (i = 0; i < G.vexnum; i++) {
if (G.adjlist[i].data == v) {
return i;
}
}
return -1;
}
void CreateGraph(Graph &G) {
int i, j, k;
char v1, v2;
ArcNode *p;
scanf("%d%d", &G.vexnum, &G.arcnum);
getchar();
for (i = 0; i < G.vexnum; i++) {
scanf("%c", &G.adjlist[i].data);
G.adjlist[i].firstarc = NULL;
getchar();
}
for (k = 0; k < G.arcnum; k++) {
scanf("%c%c", &v1, &v2);
getchar();
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G.adjlist[i].firstarc;
G.adjlist[i].firstarc = p;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = G.adjlist[j].firstarc;
G.adjlist[j].firstarc = p;
}
}
void PrintGraph(Graph G) {
int i, j;
ArcNode *p;
for (i = 0; i < G.vexnum; i++) {
printf("%c: ", G.adjlist[i].data);
p = G.adjlist[i].firstarc;
while (p != NULL) {
printf("%c ", G.adjlist[p->adjvex].data);
p = p->nextarc;
}
printf("\n");
}
}
int main() {
Graph G;
CreateGraph(G);
PrintGraph(G);
return 0;
}
```
在主函数中,先调用CreateGraph函数建立图,再调用PrintGraph函数输出图的邻接表表示。需要注意的是,在输出每个顶点的邻接点时,需要通过邻接表中存储的邻接点在顶点数组中的下标来获取邻接点的值。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)