图的存储与基本操作详解：邻接矩阵和邻接表方法及C/C++代码示例

最编程 2024-02-15 09:28:34

...

#include<stdio.h> #include<stdbool.h> #include<stdlib.h> #include<string.h> //#include<math.h> #define string char* #define VertexType string #define MAXSIZE 100 #define REALLOCSIZE 50 #define INF 0xfffffff //边表结点 typedef struct ArcNode{ int adjvex; //某条边指向的那个顶点的位置 ArcNode * next; //指向下一条弧的指针 weight w; //权值 }ArcNode; //顶点表结点 typedef struct VNode{ VertexType data; //顶点信息 ArcNode * first; //指向第一条依附该顶点的弧的指针 }VNode; typedef struct GraphRepr{ VNode * node; //邻接表 int vexnum, arcnum; //图的顶点数和弧数 }Graph, *graph; graph graph_create(void) { //初始化一个图的指针 graph g = (graph)malloc(sizeof(Graph)); if(g){ //初始化邻接表 g->node = (VNode*)malloc(MAXSIZE*sizeof(VNode)); if(!g->node) { printf("error\n"); return NULL; } g->arcnum = g->vexnum = 0; return g; } return NULL; } void graph_destroy(graph g) { ArcNode *pre, *p; //定义临时指针 char * temp; for(int i = 0; i < g->vexnum;i++){ pre = g->node[i].first; //指向边表 temp = g->node[i].data; free(temp); //等价于链表的销毁 if(pre != NULL) { p = pre->next; while(p != NULL) { free(pre); pre = p; p = pre->next; } free(pre); } } free(g); return; } //判断字符串是否相等 bool is_equal(string s1, string s2){ //首先判断长度 int len_s1 = strlen(s1); int len_s2 = strlen(s2); if(len_s1 != len_s2) return false; //长度相等后，判断每一个位置的字符 for(int i = 0; i < len_s1; i++) if(s1[i] != s2[i]) return false; return true; } void graph_add_vertex(graph g, string v) { if(!graph_has_vertex(g, v)){ int vlen = strlen(v); //判断是否超出邻接表的大小限制 if(g->vexnum+1 > MAXSIZE){ //重新申请一片空间 VNode * temp = (VNode*)malloc((g->vexnum+REALLOCSIZE)*sizeof(VNode)); //将原邻接表的信息复制到新的内存空间 for(int i = 0; i < g->vexnum; i++){ temp[i].data = g->node[i].data; temp[i].first = g->node[i].first; } g->node = temp; //新的指针赋给邻接表 } g->node[g->vexnum].data = (char*)malloc(sizeof(char)*vlen+1); // printf("%p\t", strcpy(g->node[g->vexnum].data, v)); // printf("%p\t", g->node[g->vexnum].data); // printf("%p\n", v); // int i; // for(i = 0; i < vlen; i++) // g->node[g->vexnum].data[i] = v[i]; // v[i] = '\0'; g->node[g->vexnum].first = NULL; //初始化顶点的依附表结点为空 g->vexnum++; } return; } bool graph_has_vertex(graph g, string v) { for(int i = 0; i < g->vexnum; i++) if(is_equal(g->node[i].data, v)) //如果能够找到一个顶点的信息为v return true; return false; } size_t graph_vertices_count(graph g) { return g->vexnum; } int get_index(graph g, string v){ for(int i = 0; i < g->vexnum; i++) if(is_equal(g->node[i].data, v)) return i+1; //如果能找到这个结点，返回结点位置 return -1; //否则返回-1 } void graph_add_edge(graph g, string v1, string v2, weight w){ //判断是否存在这两个顶点,如果不存在，添加这些顶点 if(!graph_has_vertex(g, v1)) graph_add_vertex(g, v1); if(!graph_has_vertex(g, v2)) graph_add_vertex(g, v2); int start = get_index(g, v1); int end = get_index(g, v2); //判断是否存在这条边 if(!graph_has_edge(g, v1, v2)){ //初始化一个边表结点 ArcNode * Next = (ArcNode*)malloc(sizeof(ArcNode)); Next->adjvex = end-1; Next->next = NULL; Next->w = w; //如果start依附的边为空 if(g->node[start-1].first == NULL) g->node[start-1].first = Next; else{ ArcNode * temp = g->node[start-1].first;//临时表结点 while(temp->next) temp = temp->next; //找到表结点中start-1这个结点的链表的最后一个顶点 temp->next = Next; //在该链表的尾部插入这个边表结点 } g->arcnum++; //边的数量++ } return; } bool graph_has_edge(graph g, string v1, string v2) { int start = get_index(g, v1); int end = get_index(g, v2); //如果边表为空，则不存在边 if(g->node[start-1].first == NULL) return false; ArcNode * temp = g->node[start-1].first; //临时表结点 while(temp) { if(temp->adjvex == end-1) return true; //如果存在一条v1指向v2的边 temp = temp->next; //指针后移 } return false; } weight graph_get_edge(graph g, string v1, string v2) { double w; //如果不存在这条边，返回0 if(!graph_has_edge(g, v1, v2)) return 0.0; int start = get_index(g, v1); int end = get_index(g, v2); ArcNode * temp = g->node[start-1].first; while(temp){ //找到v1指向v2的边，并返回weight if(temp->adjvex == end-1) return temp->w; temp = temp->next; } return 0.0; } void graph_show(graph g, FILE *output) { //先打印每一个顶点信息 for(int i = 0; i < g->vexnum; i++){ fprintf(output, "%s\n", g->node[i].data); // printf("%s\n", g->node[i].data); } //然后打印每一条边 for(int i = 0; i < g->vexnum; i++){ ArcNode * Next = g->node[i].first; while (Next) { fprintf(output, "%s %s %10.2lf\n", g->node[i].data, g->node[Next->adjvex].data, Next->w); // printf("%s %s %10.2lf\n", g->node[i].data, g->node[Next->adjvex].data, Next->w); Next = Next->next; } } return; }

上一篇：全面了解GPT Open API，轻松打造你的个人ChatGPT

下一篇：小小价签，大大学问：揭秘超市价签管理的背后

图的存储与基本操作详解：邻接矩阵和邻接表方法及C/C++代码示例

理解图：从基本概念到实现细节 - 存储方式详解（邻接矩阵与邻接表）、图的创建与代码示例

图的存储与基本操作详解：邻接矩阵和邻接表方法及C/C++代码示例