public class VertexNode { public char ch; //表头存结点值,在此为单个字符 public EdgeNode firstnode; //邻接的第一个边表结点 //构造方法 public VertexNode() { this.ch= '0'; this.firstnode = null; } public VertexNode(char ch){ this.ch = ch; this.firstnode = null; } }
时间: 2024-02-21 14:59:55 浏览: 26
这是一个 Java 类 `VertexNode` 的定义,表示图的邻接表中的结点。
该类有两个属性:
- `ch`,表示结点的值,类型为字符型。
- `firstnode`,表示该结点邻接的第一个边表结点,类型为 `EdgeNode`。
该类有两个构造方法:
- `VertexNode()`,无参构造方法,初始化结点值为字符 `'0'`,邻接的第一个边表结点为空。
- `VertexNode(char ch)`,有参构造方法,初始化结点值为参数 `ch`,邻接的第一个边表结点为空。
下面是该类的 Java 代码示例:
```java
public class VertexNode {
public char ch; // 表头存结点值,在此为单个字符
public EdgeNode firstnode; // 邻接的第一个边表结点
// 无参构造方法
public VertexNode() {
this.ch = '0';
this.firstnode = null;
}
// 有参构造方法
public VertexNode(char ch) {
this.ch = ch;
this.firstnode = null;
}
}
```
该类中没有提供任何方法,只有属性和构造方法。这是因为邻接表的操作主要是在图类中进行,邻接表中的结点对象只需要存储结点值和邻接的第一个边表结点即可。
相关问题
void printGraphLit( GraphList *G) { /*输出邻接表,输出格式:顶点->邻接顶点编号->...*/ }
以下是输出邻接表的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
// 邻接表节点
typedef struct ArcNode {
int adjvex; // 邻接点的位置
struct ArcNode *next; // 指向下一个邻接点
} ArcNode;
// 顶点信息
typedef struct VertexNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点
} VertexNode;
// 邻接表
typedef struct GraphList {
VertexNode vertex[MAX_VERTEX_NUM]; // 存放顶点信息
int vexnum; // 顶点数目
int arcnum; // 边数目
} GraphList;
// 输出邻接表
void printGraphList(GraphList *G) {
printf("Adjacency list of the graph:\n");
for (int i = 0; i < G->vexnum; i++) {
printf("%d: ", G->vertex[i].data);
ArcNode *arc = G->vertex[i].firstarc;
while (arc) {
printf("%d ", G->vertex[arc->adjvex].data);
arc = arc->next;
}
printf("\n");
}
}
```
注意事项:
1. 输出格式为 `顶点->邻接顶点编号->...`。
2. 这个函数不需要返回值,直接在函数中输出即可。
将下列代码改成六个结点10条边的无向图:#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 100 // 最大结点数 typedef struct ArcNode { // 弧结点类型 int adjvex; // 邻接点在顶点数组中的下标 struct ArcNode* next; // 指向下一个邻接点的指针 } ArcNode; typedef struct VertexNode { // 顶点类型 char data; // 顶点信息 ArcNode* firstarc; // 指向第一个邻接点的指针 } VertexNode, AdjList[MAX_VERTEX_NUM]; typedef struct Graph { // 图类型 AdjList vertices; // 顶点数组 int vexnum, arcnum; // 顶点数、弧数 } Graph; // 初始化图 void InitGraph(Graph* G) { G->vexnum = G->arcnum = 0; for (int i = 0; i < MAX_VERTEX_NUM; ++i) { G->vertices[i].data = '\0'; G->vertices[i].firstarc = NULL; } } // 添加结点 void AddVertex(Graph* G, char ch) { G->vertices[G->vexnum].data = ch; ++G->vexnum; } // 添加边 void AddEdge(Graph* G, int v1, int v2) { ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = v2; p->next = G->vertices[v1].firstarc; G->vertices[v1].firstarc = p; ++G->arcnum; } // 输出每个结点的度 void PrintDegree(Graph* G) { for (int i = 0; i < G->vexnum; ++i) { int degree = 0; ArcNode* p = G->vertices[i].firstarc; while (p) { ++degree; p = p->next; } printf("结点%c的度为%d\n", G->vertices[i].data, degree); } } int main() { Graph G; InitGraph(&G); AddVertex(&G, 'A'); AddVertex(&G, 'B'); AddVertex(&G, 'C'); AddVertex(&G, 'D'); AddEdge(&G, 0, 1); AddEdge(&G, 0, 2); AddEdge(&G, 1, 2); AddEdge(&G, 2, 0); AddEdge(&G, 2, 3); AddEdge(&G, 3, 3); PrintDegree(&G); return 0; }
将代码改成六个结点十条边的无向图,可以按照以下方式修改:
1. 修改结点数为6,即将MAX_VERTEX_NUM改为6,同时在InitGraph函数中将G->vexnum初始值改为6。
2. 根据题目要求,顶点分别为A、B、C、D、E、F。因此在main函数中添加以下语句:
```
AddVertex(&G, 'A');
AddVertex(&G, 'B');
AddVertex(&G, 'C');
AddVertex(&G, 'D');
AddVertex(&G, 'E');
AddVertex(&G, 'F');
```
3. 添加边的过程中,注意无向图的边是双向的,因此需要添加两条边。具体来说,添加边的代码如下:
```
AddEdge(&G, 0, 1); // A-B
AddEdge(&G, 1, 0); // B-A
AddEdge(&G, 0, 2); // A-C
AddEdge(&G, 2, 0); // C-A
AddEdge(&G, 1, 2); // B-C
AddEdge(&G, 2, 1); // C-B
AddEdge(&G, 2, 3); // C-D
AddEdge(&G, 3, 2); // D-C
AddEdge(&G, 3, 4); // D-E
AddEdge(&G, 4, 3); // E-D
```
4. 最后,修改输出语句中的结点名称为题目给定的名称即可。修改后的代码如下:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 6 // 最大结点数
typedef struct ArcNode { // 弧结点类型
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode* next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VertexNode { // 顶点类型
char data; // 顶点信息
ArcNode* firstarc; // 指向第一个邻接点的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];
typedef struct Graph { // 图类型
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数、弧数
} Graph;
// 初始化图
void InitGraph(Graph* G) {
G->vexnum = 6;
G->arcnum = 0;
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
G->vertices[i].data = '\0';
G->vertices[i].firstarc = NULL;
}
}
// 添加结点
void AddVertex(Graph* G, char ch) {
G->vertices[G->vexnum].data = ch;
++G->vexnum;
}
// 添加边
void AddEdge(Graph* G, int v1, int v2) {
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->next = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = p;
++G->arcnum;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = v1;
p->next = G->vertices[v2].firstarc;
G->vertices[v2].firstarc = p;
++G->arcnum;
}
// 输出每个结点的度
void PrintDegree(Graph* G) {
for (int i = 0; i < G->vexnum; ++i) {
int degree = 0;
ArcNode* p = G->vertices[i].firstarc;
while (p) {
++degree;
p = p->next;
}
printf("结点%c的度为%d\n", G->vertices[i].data, degree);
}
}
int main() {
Graph G;
InitGraph(&G);
AddVertex(&G, 'A');
AddVertex(&G, 'B');
AddVertex(&G, 'C');
AddVertex(&G, 'D');
AddVertex(&G, 'E');
AddVertex(&G, 'F');
AddEdge(&G, 0, 1); // A-B
AddEdge(&G, 1, 0); // B-A
AddEdge(&G, 0, 2); // A-C
AddEdge(&G, 2, 0); // C-A
AddEdge(&G, 1, 2); // B-C
AddEdge(&G, 2, 1); // C-B
AddEdge(&G, 2, 3); // C-D
AddEdge(&G, 3, 2); // D-C
AddEdge(&G, 3, 4); // D-E
AddEdge(&G, 4, 3); // E-D
PrintDegree(&G);
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)