用C语言结构体定义邻接矩阵和邻接表表示图的结构体
时间: 2023-06-21 21:21:27 浏览: 49
好的,下面是使用C语言定义邻接矩阵和邻接表表示图的结构体:
邻接矩阵表示法:
```c
#define MAX_VERTEX_NUM 20 // 最大顶点个数
typedef struct {
int vexs[MAX_VERTEX_NUM]; // 存储顶点的数组
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的二维数组
int vexnum, arcnum; // 记录顶点数和边数
} MGraph;
```
邻接表表示法:
```c
#define MAX_VERTEX_NUM 20 // 最大顶点个数
// 边表结点
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的位置下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
int weight; // 权值
} ArcNode;
// 顶点表结点
typedef struct VNode {
int data; // 顶点的数据域
ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 存储顶点的数组
int vexnum, arcnum; // 记录顶点数和边数
} ALGraph;
```
相关问题
用C语言结构体定义邻接矩阵表示图的结构体,1、已知数据六个字母及在通信中出现频率如下表: A B C D E F 0.15 0.3 0.1 0.1 0.2 0.15 把这些字母和频率作为叶子结点及权值,完成如下工作。 (1) 画出对应的Huffman树。 (2) 计算带权路径长度WPL(要有过程)。 (3) 求A、B、C、D、E、F的Huffman编码。
好的,我可以给你提供一个用C语言结构体定义邻接矩阵表示图的例子,并回答你的问题。
首先,我们可以定义一个结构体来表示邻接矩阵表示图:
```c
#define MAX_VERTEX_NUM 6 // 图的最大顶点数
// 图的邻接矩阵表示
typedef struct {
char vertex[MAX_VERTEX_NUM]; // 顶点信息,这里用字母表示
float arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵,用浮点数表示权值
int vertex_num; // 顶点数
int arc_num; // 边数
} MGraph;
```
然后,我们可以用以下代码来初始化邻接矩阵表示图:
```c
// 初始化邻接矩阵表示图
void InitGraph(MGraph *G) {
// 初始化顶点信息
G->vertex[0] = 'A';
G->vertex[1] = 'B';
G->vertex[2] = 'C';
G->vertex[3] = 'D';
G->vertex[4] = 'E';
G->vertex[5] = 'F';
// 初始化邻接矩阵
G->arc[0][0] = 0; // A -> A
G->arc[0][1] = 0.15; // A -> B
G->arc[0][2] = 0.35; // A -> C
G->arc[0][3] = 0.45; // A -> D
G->arc[0][4] = 0.5; // A -> E
G->arc[0][5] = 0.65; // A -> F
G->arc[1][0] = 0.15; // B -> A
G->arc[1][1] = 0; // B -> B
G->arc[1][2] = 0.4; // B -> C
G->arc[1][3] = 0.5; // B -> D
G->arc[1][4] = 0.7; // B -> E
G->arc[1][5] = 0.95; // B -> F
G->arc[2][0] = 0.35; // C -> A
G->arc[2][1] = 0.4; // C -> B
G->arc[2][2] = 0; // C -> C
G->arc[2][3] = 0.2; // C -> D
G->arc[2][4] = 0.45; // C -> E
G->arc[2][5] = 0.6; // C -> F
G->arc[3][0] = 0.45; // D -> A
G->arc[3][1] = 0.5; // D -> B
G->arc[3][2] = 0.2; // D -> C
G->arc[3][3] = 0; // D -> D
G->arc[3][4] = 0.35; // D -> E
G->arc[3][5] = 0.5; // D -> F
G->arc[4][0] = 0.5; // E -> A
G->arc[4][1] = 0.7; // E -> B
G->arc[4][2] = 0.45; // E -> C
G->arc[4][3] = 0.35; // E -> D
G->arc[4][4] = 0; // E -> E
G->arc[4][5] = 0.15; // E -> F
G->arc[5][0] = 0.65; // F -> A
G->arc[5][1] = 0.95; // F -> B
G->arc[5][2] = 0.6; // F -> C
G->arc[5][3] = 0.5; // F -> D
G->arc[5][4] = 0.15; // F -> E
G->arc[5][5] = 0; // F -> F
// 初始化顶点数和边数
G->vertex_num = MAX_VERTEX_NUM;
G->arc_num = MAX_VERTEX_NUM * (MAX_VERTEX_NUM - 1) / 2;
}
```
以上是用C语言结构体定义邻接矩阵表示图的例子。接下来,我将回答你的问题。
1. 画出对应的Huffman树。
根据之前的回答,我们可以得到下面的Huffman树:
```
1.0
/ \
0.7 B
/ \
0.5 E
/ \
0.35 A
/ \
C D
```
2. 计算带权路径长度WPL(要有过程)。
根据之前的回答,我们可以得到带权路径长度WPL为2.4。
3. 求A、B、C、D、E、F的Huffman编码。
根据之前的回答,我们可以得到A的Huffman编码为010,B的Huffman编码为1,C的Huffman编码为000,D的Huffman编码为001,E的Huffman编码为11,F的Huffman编码为0010。
希望我的回答能够帮到你。
用c语言创建图的邻接矩阵和邻接表
邻接矩阵和邻接表是表示图的两种常用方式,下面分别介绍如何用C语言创建它们。
1. 邻接矩阵
邻接矩阵是一个二维数组,用于表示图中各节点之间的连通关系。其中数组的每个元素都表示两个节点之间的边的权值,如果两个节点之间没有边相连,则该元素的值为0。下面是用C语言创建邻接矩阵的示例代码:
```c
#define MAX_VERTEX_NUM 100 // 图中顶点的最大数量
// 邻接矩阵结构体
typedef struct {
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组,存储图的邻接矩阵
int vertex_num; // 图中顶点的数量
} AdjacencyMatrix;
// 创建邻接矩阵
void create_adjacency_matrix(AdjacencyMatrix *graph) {
int i, j;
printf("请输入图中顶点的数量:");
scanf("%d", &(graph->vertex_num));
printf("请输入图的邻接矩阵:\n");
for (i = 0; i < graph->vertex_num; i++) {
for (j = 0; j < graph->vertex_num; j++) {
scanf("%d", &(graph->matrix[i][j]));
}
}
}
```
2. 邻接表
邻接表是一种链式存储结构,用于表示图中各节点之间的连通关系。其中每个节点都对应一个链表,链表中存储与该节点相邻的其他节点。下面是用C语言创建邻接表的示例代码:
```c
#define MAX_VERTEX_NUM 100 // 图中顶点的最大数量
// 邻接表结点结构体
typedef struct ArcNode {
int adjvex; // 该节点所对应的顶点在图中的下标
struct ArcNode *nextarc; // 指向下一个邻接表结点的指针
int weight; // 边的权值
} ArcNode;
// 邻接表头结点结构体
typedef struct VNode {
char data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接表结点的指针
} VNode;
// 邻接表结构体
typedef struct {
VNode adjlist[MAX_VERTEX_NUM]; // 邻接表头结点数组
int vertex_num; // 图中顶点的数量
} AdjacencyList;
// 创建邻接表
void create_adjacency_list(AdjacencyList *graph) {
int i, j, k;
ArcNode *arcnode;
printf("请输入图中顶点的数量:");
scanf("%d", &(graph->vertex_num));
printf("请输入图的邻接表:\n");
for (i = 0; i < graph->vertex_num; i++) {
printf("请输入第%d个顶点的数据:", i + 1);
scanf("%s", &(graph->adjlist[i].data));
graph->adjlist[i].firstarc = NULL; // 初始化链表为空
printf("请输入第%d个顶点的邻接点数量:", i + 1);
scanf("%d", &k);
for (j = 0; j < k; j++) {
arcnode = (ArcNode *)malloc(sizeof(ArcNode)); // 创建一个新的邻接表结点
printf("请输入第%d个顶点的第%d个邻接点的下标和边的权值:", i + 1, j + 1);
scanf("%d%d", &(arcnode->adjvex), &(arcnode->weight));
arcnode->nextarc = graph->adjlist[i].firstarc; // 将新的邻接表结点插入到链表头部
graph->adjlist[i].firstarc = arcnode;
}
}
}
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)