用c语言:已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的<vi,vj>(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示:先产生邻接表的n个头结点(其结点数值域从1到n)。
时间: 2024-04-15 09:31:04 浏览: 114
以下是用C语言编写的根据用户输入的偶对建立有向图邻接表的算法:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int vertex;
struct Node* next;
} Node;
void insertEdge(Node** adjList, int src, int dest) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = dest;
newNode->next = adjList[src];
adjList[src] = newNode;
}
void createAdjList(Node** adjList, int n) {
int src, dest;
for (int i = 1; i <= n; i++) {
adjList[i] = NULL; // 初始化邻接表的头结点
}
printf("请输入边的偶对(以0表示结束):\n");
while (1) {
scanf("%d%d", &src, &dest);
if (src == 0 || dest == 0) {
break; // 输入0结束循环
}
if (src < 1 || src > n || dest < 1 || dest > n) {
printf("输入的顶点编号超出范围,请重新输入。\n");
continue; // 输入的顶点编号错误,重新输入
}
insertEdge(adjList, src, dest);
}
}
void printAdjList(Node** adjList, int n) {
printf("邻接表:\n");
for (int i = 1; i <= n; i++) {
printf("顶点 %d:", i);
Node* temp = adjList[i];
while (temp != NULL) {
printf(" -> %d", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
int main() {
int n;
printf("请输入顶点个数:");
scanf("%d", &n);
Node** adjList = (Node**)malloc((n+1) * sizeof(Node*));
createAdjList(adjList, n);
printAdjList(adjList, n);
// 释放邻接表的内存
for (int i = 1; i <= n; i++) {
Node* temp = adjList[i];
while (temp != NULL) {
Node* prev = temp;
temp = temp->next;
free(prev);
}
}
free(adjList);
return 0;
}
```
这个算法通过动态申请内存来构建有向图的邻接表,并根据用户输入的边的偶对逐一插入到对应的单链表中。最后,输出建立的邻接表。
阅读全文