邻接表程序怎么输入

时间:2025-01-26 04:58:35 单机游戏

输入邻接表程序的方法如下:

定义数据结构

首先定义边结点结构体 `ArcNode`,包含邻接点的序号 `adjvex` 和指向下一个边结点的指针 `nextarc`。

定义顶点结构体 `VNode`,包含顶点信息 `data` 和指向出边表和入边表表头指针 `head1` 和 `head2`。

定义图的结构体 `LGraph`,包含顶点数组 `verts`、顶点数 `vexnum` 和边数 `arcnum`。

初始化

初始化邻接表,设置每个顶点的出边表和入边表的头指针为 `NULL`。

输入边

输入顶点数 `n` 和边数 `m`。

输入每条边的起点 `from`、终点 `to` 和权重 `w`。

将每条边的信息存储在边数组 `e` 中,并更新前驱数组 `pre`。

输出

输出每个顶点的出度和入度。

```c

include

include

define MAXN 100

typedef struct ArcNode {

int adjvex;

struct ArcNode *nextarc;

} ArcNode;

typedef struct VNode {

int data;

ArcNode *head1;

ArcNode *head2;

} VNode;

typedef struct LGraph {

VNode vertes[MAXN];

int vexnum, arcnum;

} LGraph;

void init_adjlist(LGraph *list) {

int i, j;

list->vexnum = 0;

list->arcnum = 0;

}

void add_edge(LGraph *list, int from, int to, int w) {

ArcNode *new_node = (ArcNode *)malloc(sizeof(ArcNode));

new_node->adjvex = to;

new_node->nextarc = list->verts[from].head1;

list->verts[from].head1 = new_node;

list->arcnum++;

}

int main() {

int n, m;

scanf("%d %d", &n, &m);

LGraph lg;

init_adjlist(&lg);

for (int i = 0; i < m; i++) {

int from, to, w;

scanf("%d %d %d", &from, &to, &w);

add_edge(&lg, from - 1, to - 1, w); // 邻接表索引从0开始

}

// 输出每个顶点的出度和入度

for (int i = 0; i < n; i++) {

int out_degree = 0, in_degree = 0;

ArcNode *p = lg.verts[i].head1;

while (p != NULL) {

out_degree++;

p = p->nextarc;

}

p = lg.verts[i].head2;

while (p != NULL) {

in_degree++;

p = p->nextarc;

}

printf("顶点 %d 的出度: %d, 入度: %d\n", i + 1, out_degree, in_degree);

}

return 0;

}

```

建议

确保输入的顶点数和边数不超过定义的最大值 `MAXN`。

在输入边时,确保起点和终点的编号在有效范围内(通常是1到n)。

输出结果时,顶点的编号也从1开始。