C语言 图操作–邻接表法

C语言 图操作–邻接表法

这里只是图的创建部分，图的遍历会在后面更新。
一、图的介绍
图是一种相较于链表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继（每个元素之间一个一个逐个相连）。在树形结构中，数据元素之间有着明显的层次关系，上一层元素能和下层多个元素相关，但是下层元素只能与一个上层元素相关。而在图结构中，节点之间的关系任意，任何两个顶点都可能相连。
图结构如图所示

此中为“离散数学”中的图理论。
二、图的术语
接下来介绍图结构中的一些术语。
1.顶点 图中的数据元素通常称为顶点。
2.边 两顶点间的连线称为边。
3.V是顶点的有穷非空集合。
4.VR是两个顶点之间关系的集合，也是边的集合。
5.通常表示为:G(V,E),G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
6.无向边：若顶点A到顶点B的边没有方向，称这条边为无向边，用无序偶对(A,B)或(B,A)表示。

7.有向边：若顶点A到顶点B的边有方向，称这条边为有向边，也称为弧(Arc)，用有序对 < B, A >表示；B表示弧尾，A表示弧头
8.由无向边构成的图为无向图
9.由有向边构成的图为有向图
这里只是一些最基本的术语，大家可以自己去看看大佬们的介绍。
三、图结构的构建
1.用邻接表创建图结构既是使用链表记录一个顶点的所有邻近顶点，再用数组存取顶点信息，当然顶点信息也可以用链表串起来。
2.邻接表的结构体定义代码如图所示

void clear() //该函数起到一个清空缓冲区的作用，防止多部输入错误。{int ch;while ((ch = getchar()) != EOF && ch != '\\n');}struct Node  //定义邻接表的节点属性{int data;//邻接表的数据域struct Node *next; //邻接表的指针域};struct Head   //定义图的顶点的属性{char info;  //存储图顶点信息struct Node *dajoin;  //定义临近顶点指针};struct Map  //定义图结构{int side;  //记录边的数量int spot;  //记录图的数量struct Head head[20];  //用数组记录顶点下标};

3.创建一个图
定义完结构体之后需要创建图结构，并对输入的数据进行存储。将存数据的各个顶点进行关联。

void creat_graph(struct Map *map){int i, j;char S1 = 0;char S2 = 0;struct Node *p;printf("请输入要建立的顶点数：\\n");scanf("%d", &map->spot);//将输入的顶点数存入图结构体变量中clear();//清空缓冲区  下同printf("请输入要建立的边的数：\\n");scanf("%d", &map->side);//将输入的边数存入图结构体变量中clear();for (i = 0; i < map->spot; i++){map->head[i].info = i + 'A';//创建n个顶点并分别赋值为A到i+"A"map->head[i].dajoin = NULL;//初始化顶点，使顶点邻接点为空。}printf("请输入要建立的边：\\n");for (j = 0; j < map->side; j++){scanf("%c%c", &S1, &S2);  //通过输入字母 如AB BC 建立边并连接顶点getchar();if (S1 != ' ' && S2 != ' ' && S1 != S2)//如果s1 s2都不为‘ ’ 且不等。{insert(map, S1, S2);//把s2顶点挂在s1顶点下。此函数定义后面介绍}}}

4.邻接表的插入操作。
此步骤与普通的链表插入无不同，如果有不了解的可以区看我前面的博客（记得点赞加关注哦！）。此处不作过多介绍。

void insert(struct Map *map, char S1, char S2){if (map->head[B1].dajoin != NULL)  //如果该顶点下未已挂载链表则进行比较并插入{if (map->head[B1].dajoin->data > B2){struct Node *temp = malloc(sizeof(struct Node));temp->data = B2;temp->next = map->head[B1].dajoin;map->head[B1].dajoin = temp;}else{struct Node *demp = map->head[B1].dajoin;struct Node *before = demp;while (demp && B2 > demp->data){before = demp;demp = demp->next;}struct Node *emp = malloc(sizeof(struct Node));emp->data = B2;emp->next = before->next;before->next = emp;}}else  //如果未挂载链表则直接挂载链表{map->head[B1].dajoin = malloc(sizeof(struct Node));map->head[B1].dajoin->data = B2;map->head[B1].dajoin->next = NULL;}}

5、展现图的结构关系

void print(struct Map *map){int i;for (i = 0; i < map->spot; i++)  //通过循环找到各个顶点之间的连接关系{char ele = i + 'A';struct Node *p = map->head[i].dajoin;printf("与%c连接的结点有：", ele);while (p){char ele = p->data + 'A';printf("%c ", ele);p = p->next;}printf("\\n");}}

四、完整代码

#include "stdlib.h"#include "stdio.h"#define B1 (S1 - 'A')#define B2 (S2 - 'A')void clear(){int ch;while ((ch = getchar()) != EOF && ch != '\\n');}struct Node{int data;struct Node *next;};struct Head{char info;struct Node *dajoin;};struct Map{int side;int spot;struct Head head[20];};void creat_graph(struct Map *map){int i, j;char S1 = 0;char S2 = 0;struct Node *p;printf("请输入要建立的顶点数：\\n");scanf("%d", &map->spot);clear();printf("请输入要建立的边的数：\\n");scanf("%d", &map->side);clear();for (i = 0; i < map->spot; i++){map->head[i].info = i + 'A';map->head[i].dajoin = NULL;}printf("请输入要建立的边：\\n");for (j = 0; j < map->side; j++){scanf("%c%c", &S1, &S2);getchar();if (S1 != ' ' && S2 != ' ' && S1 != S2){insert(map, S1, S2);}}}void insert(struct Map *map, char S1, char S2){if (map->head[B1].dajoin != NULL){if (map->head[B1].dajoin->data > B2){struct Node *temp = malloc(sizeof(struct Node));temp->data = B2;temp->next = map->head[B1].dajoin;map->head[B1].dajoin = temp;}else{struct Node *demp = map->head[B1].dajoin;struct Node *before = demp;while (demp && B2 > demp->data){before = demp;demp = demp->next;}struct Node *emp = malloc(sizeof(struct Node));emp->data = B2;emp->next = before->next;before->next = emp;}}else{map->head[B1].dajoin = malloc(sizeof(struct Node));map->head[B1].dajoin->data = B2;map->head[B1].dajoin->next = NULL;}}void print(struct Map *map){int i;for (i = 0; i < map->spot; i++){char ele = i + 'A';struct Node *p = map->head[i].dajoin;printf("与%c连接的结点有：", ele);while (p){char ele = p->data + 'A';printf("%c ", ele);p = p->next;}printf("\\n");}}int main(){struct Map map;creat_graph(&map);print(&map);return 0;}