c语言编程用邻接链表存储结构,编程实现如下功能: (1)输入字符型顶点,有向图的顶点数、边数及各条边的顶点对,建立用邻接表存储的有向图。 (2)输出有向图的邻接表 (3)输入遍历起点,对有向图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-05-14 11:19:34 浏览: 55
c语言实现链表的基本操作,链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
好的,我会尽力回答你的问题。以下是C语言编程用邻接链表存储结构实现的代码,可实现你所述的功能:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INF 0x3f3f3f3f // 无穷大
// 定义邻接表中的边结构体
typedef struct ArcNode {
int adjvex; // 该边所指向的顶点的位置
struct ArcNode* nextarc; // 指向下一条边的指针
int weight; // 权值
} ArcNode;
// 定义邻接表中的顶点结构体
typedef struct VNode {
char data; // 顶点信息
ArcNode* firstarc; // 指向第一条依附该顶点的边的指针
} VNode;
// 定义邻接表结构体
typedef struct {
VNode vexs[MAX_VERTEX_NUM]; // 顶点数组
int vexnum; // 顶点数
int arcnum; // 边数
} ALGraph;
// 建立用邻接表存储的有向图
void CreateGraph(ALGraph* G) {
printf("请输入顶点数和边数:\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar();
printf("请输入各个顶点的信息:\n");
for (int i = 0; i < G->vexnum; i++) {
printf("第%d个顶点:", i + 1);
scanf("%c", &G->vexs[i].data);
G->vexs[i].firstarc = NULL;
getchar();
}
printf("请输入各个边的信息:\n");
for (int k = 0; k < G->arcnum; k++) {
char v1, v2;
int w;
printf("第%d条边:", k + 1);
scanf("%c%c%d", &v1, &v2, &w);
getchar();
int i, j;
for (i = 0; i < G->vexnum; i++) {
if (G->vexs[i].data == v1) break;
}
for (j = 0; j < G->vexnum; j++) {
if (G->vexs[j].data == v2) break;
}
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = w;
p->nextarc = G->vexs[i].firstarc;
G->vexs[i].firstarc = p;
}
}
// 输出有向图的邻接表
void PrintGraph(ALGraph G) {
printf("该有向图的邻接表为:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%c --> ", G.vexs[i].data);
ArcNode* p = G.vexs[i].firstarc;
while (p) {
printf("%c(%d) ", G.vexs[p->adjvex].data, p->weight);
p = p->nextarc;
}
printf("\n");
}
}
// 深度优先搜索遍历
void DFS(ALGraph G, int v, int* visited) {
visited[v] = 1; // 标记当前顶点已被访问
printf("%c ", G.vexs[v].data); // 输出当前顶点的信息
ArcNode* p = G.vexs[v].firstarc;
while (p) {
int j = p->adjvex;
if (!visited[j]) { // 若该顶点未被访问,则继续遍历
DFS(G, j, visited);
}
p = p->nextarc;
}
}
// 深度优先搜索遍历入口函数
void DFSTraverse(ALGraph G) {
int visited[MAX_VERTEX_NUM];
memset(visited, 0, sizeof(visited)); // 初始化visited数组
printf("请输入遍历起点:");
char v;
scanf("%c", &v);
getchar();
int i;
for (i = 0; i < G.vexnum; i++) {
if (G.vexs[i].data == v) break;
}
DFS(G, i, visited);
}
// 广度优先搜索遍历
void BFS(ALGraph G, int v, int* visited) {
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
printf("%c ", G.vexs[v].data);
visited[v] = 1;
queue[rear++] = v;
while (front < rear) {
int w = queue[front++];
ArcNode* p = G.vexs[w].firstarc;
while (p) {
int j = p->adjvex;
if (!visited[j]) {
printf("%c ", G.vexs[j].data);
visited[j] = 1;
queue[rear++] = j;
}
p = p->nextarc;
}
}
}
// 广度优先搜索遍历入口函数
void BFSTraverse(ALGraph G) {
int visited[MAX_VERTEX_NUM];
memset(visited, 0, sizeof(visited)); // 初始化visited数组
printf("请输入遍历起点:");
char v;
scanf("%c", &v);
getchar();
int i;
for (i = 0; i < G.vexnum; i++) {
if (G.vexs[i].data == v) break;
}
BFS(G, i, visited);
}
int main() {
ALGraph G;
CreateGraph(&G);
PrintGraph(G);
DFSTraverse(G);
printf("\n");
BFSTraverse(G);
printf("\n");
return 0;
}
```
以上代码实现了用邻接链表存储结构的有向图的建立、输出邻接表、深度优先搜索遍历、广度优先搜索遍历四个功能。其中,建立有向图和输出邻接表的功能在`CreateGraph()`和`PrintGraph()`函数中实现,深度优先搜索遍历和广度优先搜索遍历的功能在`DFSTraverse()`和`BFSTraverse()`函数中实现。
阅读全文