数据结构图的邻接表存储结构

图的邻接表存储

我们知道，数据之间的关系有 3 种，分别是 “一对一”、“一对多” 和 “多对多”，前两种关系的数据可分别用线性表和树结构存储，最后一种具有"多对多"逻辑关系数据的结构 ——图存储结构

既然大家都来到这看了，相必也是清楚图是啥了，我就不做过多的介绍了，我主要是想给大家分享下可以直接拿来执行的图的邻接表存储C语言源码

我们要实现这个图的邻接表存储：

代码如下：

#include <stdio.h>#include <stdlib.h>#define MAXSIZE 100 //图中最大节点数// 定义边表节点结构typedef struct node{char adjvex; // 与顶点相连的邻接点下标(adjoin：邻接)struct node *next; // 指向顶点的下一个邻接点} EdgeNode;// 定义顶点表节点的结构 -> 结构体数组typedef struct vnode{char vex; // 存储顶点名 顶点在结构体数组中的下标EdgeNode *firstedge; // 边表的头指针，指向顶点的第一个邻接点} VertexNode, AdjList[MAXSIZE];//图的存储结构typedef struct{AdjList adjList; // 描述图结构的邻接表 结构体数组int vexnum;// 顶点的数目int edgenum;// 边的数目} ALGraph;//创建图 -> 邻接表存储void CreateALG(ALGraph *ALG){char ch;int i = 0, count = 0; //i与count为计数器，分别记录图的顶点个数和边数EdgeNode *temp; //临时结构体指针 边表printf("请输入图的顶点：");while ((ch = getchar()) != '\n') // 建立顶点表{ALG->adjList[i].vex = ch; //顶点名ALG->adjList[i].firstedge = NULL; //顶点的next指针 初始化为NULLi++;//记录顶点的个数}ALG->vexnum = i; // 图的顶点数for (int j = 0; j < ALG->vexnum; j++) // 头插法建立顶点的邻接边表{printf("请输入顶点 %c 的邻接顶点：", ALG->adjList[j].vex);while ((ch = getchar()) != '\n') // 按下回车结束邻接点的创建{temp = (EdgeNode *)malloc(sizeof(EdgeNode));temp->adjvex = ch; //存储临界点的名字temp->next = ALG->adjList[j].firstedge; //把NULl值给临接点的next指针ALG->adjList[j].firstedge = temp; //顶点和临接点相连接count++; //记录边的个数}}ALG->edgenum = count / 2; //图边的个数// 无向图中每条边连接两个顶点，故：节点总度数 = 边数 * 2}//遍历图void TraverseALG(ALGraph ALG){int i;EdgeNode *p;if (ALG.vexnum == 0) //判断图的顶点个数，若为0，则图为空{printf("图为空！\n");return;//虽然函数类型是void,但是此处加了return，可以使得当图为空时，函数结束，下方代码不再执行}for (i = 0; i < ALG.vexnum; i++) // 遍历图{printf("顶点 %c ：", ALG.adjList[i].vex);p = ALG.adjList[i].firstedge; //firstedge表示边表的头指针，指向顶点的第一个邻接点while (p) // 输出图的信息{printf("[ %c ] -> ", p->adjvex);p = p->next;}printf("NULL\n");}}//查找顶点在结构体数组中的下标void FindVex(ALGraph ALG, char vertex){for (int i = 0; i < ALG.vexnum; i++) //vexnum表示图的顶点个数if (ALG.adjList[i].vex == vertex){printf("%c 的节点下标：%d\n", vertex, i);return;}printf("节点不存在！\n");}int main(){//声明函数void CreateALG(ALGraph * ALG);// 邻接表法创建图void FindVex(ALGraph ALG, char vertex); // 若图ALG中存在节点vertex，则返回该节点下标void TraverseALG(ALGraph ALG);// 遍历图ALGALGraph g; //创建图CreateALG(&g); //把图的地址(结构体的地址)传过去printf("==============================\n");printf("顶点个数 = %d ; 边的个数 = %d\n", g.vexnum, g.edgenum);printf("==============================\n");FindVex(g, '1'); //查找某一个顶点在结构体数组中的下标printf("==============================\n");TraverseALG(g);system("pause");return 0;}

运行结构如下：

我是在Vscode中运行的，需要用到调试，所以在末尾加了system("pause");，如果你不是在Vscode中运行，而是在Codeblack中运行的话，可以去掉此行代码哦！我也是刚刚期末实训做出来的，注释我觉得很详细了，分享给大家，希望能帮到你们，嘻嘻！欢迎关注我的个人博客 https://www.cyz4531.top如果运行出现问题也欢迎在下方评论哦!

如果觉得《数据结构图的邻接表存储结构》对你有帮助，请点赞、收藏，并留下你的观点哦！