c语言已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的<vi,vj>(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示:先产生邻接表的n个头结点(其结点数值域从1到n)
时间: 2024-04-16 19:26:39 浏览: 281
数据结构-c语言-带main函数-图7.2-图的存储结构-图的邻接矩阵的创建-有向图。
5星 · 资源好评率100%
以下是根据您的要求编写的算法,用于根据用户输入的偶对建立有向图的邻接表:
```c
#include <stdio.h>
#include <stdlib.h>
// 邻接表的结点定义
typedef struct node {
int vertex; // 顶点编号
struct node* next; // 指向下一个结点的指针
} Node;
// 产生邻接表的n个头结点
Node** createAdjacencyList(int n) {
Node** adjList = (Node**)malloc((n + 1) * sizeof(Node*)); // 头结点数组,索引从1到n
// 初始化头结点数组
for (int i = 1; i <= n; i++) {
adjList[i] = (Node*)malloc(sizeof(Node));
adjList[i]->vertex = i;
adjList[i]->next = NULL;
}
return adjList;
}
// 在邻接表中插入边
void insertEdge(Node** adjList, int vi, int vj) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = vj;
newNode->next = NULL;
Node* current = adjList[vi];
// 寻找插入位置
while (current->next != NULL) {
current = current->next;
}
// 插入结点到链表末尾
current->next = newNode;
}
// 打印邻接表
void printAdjacencyList(Node** adjList, int n) {
for (int i = 1; i <= n; i++) {
Node* current = adjList[i]->next;
printf("%d -> ", i);
while (current != NULL) {
printf("%d ", current->vertex);
current = current->next;
}
printf("\n");
}
}
int main() {
int n;
printf("请输入顶点的个数n:");
scanf("%d", &n);
Node** adjList = createAdjacencyList(n);
int vi, vj;
printf("请输入边的偶对<vi,vj>(以其中之一为0表示结束):\n");
scanf("%d%d", &vi, &vj);
while (vi != 0 && vj != 0) {
insertEdge(adjList, vi, vj);
scanf("%d%d", &vi, &vj);
}
printf("\n生成的邻接表为:\n");
printAdjacencyList(adjList, n);
return 0;
}
```
这段代码首先定义了邻接表的结点结构,然后实现了创建邻接表的函数 `createAdjacencyList`,该函数会产生邻接表的n个头结点。接下来,实现了插入边的函数 `insertEdge`,该函数会根据用户输入的边信息插入到邻接表中。最后,定义了打印邻接表的函数 `printAdjacencyList`,用于输出生成的邻接表。在 `main` 函数中,首先读取用户输入的顶点个数和边的偶对,然后根据用户输入建立邻接表,并最终打印生成的邻接表。
请注意,在这段代码中,我们假设用户输入的边信息是合法的,并且用户输入的顶点编号从1开始。如果需要进行输入的合法性检查或对顶点编号进行调整,请在代码中作出相应修改。
阅读全文