当前位置:首页 » 《资源分享》 » 正文

数据结构-C语言描述(邻接表)

20 人参与  2024年12月12日 12:02  分类 : 《资源分享》  评论

点击全文阅读


概述

1.邻接表的优缺点

邻接表是一种表示图的数据结构,事实上邻接表可以用于有向图、无向图、带权图、无权图。

邻接表表示法的优点主要有空间效率、遍历效率

空间利用率高:邻接表相较于邻接矩阵更加节省空间,特别是对于稀疏图。因为邻接表只需要储存实际存在的边,而邻接矩阵需要储存所有的边。遍历速度:邻接表在遍历与某顶点相邻的全部顶点时,时间复杂度与顶点的度成正比。对于稀疏图而言,这比邻接矩阵表示法的时间复杂度要低。

 邻接表的缺点

不适合储存稠密图,此时邻接表顶点的边列表过长,导致储存和访问的效率大大降低。代码复杂,相较于邻接矩阵,邻接表表示法的代码逻辑稍复杂。

2.怎么从树->图(一对多->多对多)

今天我们用链表形式来实现一个邻接表,在实现邻接表之前,我们先观察一张有向图来摸索一下图中结点之间的关系:

 很自然地,我们会将这张有向图拆成两个部分:连接两个结点的有向边以及每个结点。

那么我们应该如何用链表将这些信息储存起来呢?让我们回想一下树是如何用链表实现的,我们用数组TreeNode *nodes来储存结点,然后通过TreeNode* node->childrenlist(子结点链表)来记录每个结点下的子结点,这就是树结构(一对多)用链表的实现。

然后我们思考如何将这种树结构通过变换,来达到多对多的目的。我们首先明确一条边只能连接两个结点(这是关键),然后想着为结点、有向边定义两种结构体(VertexNode、EdgeNode)。在图结点结构体中要有一个链表(EdgeNode* firstEdge)储存所有由该结点发出的边,还要有数据域。每个边结构体中存放指向的顶点数据,如此就能够将有向图的数据结构用链表表达出来。

 1.邻接表的结构体申明

首先是必要的头文件:

#include <stdio.h>#include <stdlib.h>

然后我们根据先前的分析定义三个结构体用于图的数据结构:

EdgeNode结构体用于表示图中的边,包括三个成员,vertex(这条边指向的顶点)、weight(这条边的权重)、*next(用于指向下一个边结点)VertexNode结构体用于表示图中的顶点,包括两个成员,vertex(顶点索引)、firstEdge(指向该结点的第一个边结点)Graph结构体用于整个图的表示,包括两个成员,vertices(顶点的数量)、数组nodes(用于记录所有顶点信息)
typedef struct EdgeNode {int vertex;  //这条边的结尾顶点 int weight;  //这条边上的权重 struct EdgeNode* next;  //指向下一边结点} EdgeNode; typedef struct VertexNode {int vertex;  //顶点数据域 EdgeNode* firstEdge;  //指向该顶点的第一条边 } VertexNode; typedef struct Graph {int vertices;  //顶点的数量 VertexNode* nodes;  //用来记录每个顶点信息 } Graph; 

 2.邻接表的创建

 邻接表的创建就是将其初始化,调用malloc函数将g->nodes的空间分配好后,然后每个顶点赋值编号,并且将每个顶点指向的第一条边置空:

void GraphCreat(Graph* g,int vertices) {  //传入的参数是表*g和结点的数量vertices g->vertices=vertices;  g->nodes=(VertexNode*)malloc(sizeof(VertexNode)*vertices);//为g->nodes分配空间 for(int i=0;i<g->vertices;i++){     g->nodes[i].vertex=i;          //将每个结点的数据初始化为结点编号g->nodes[i].firstEdge=NULL;    //且将结点指向的第一条边置空 }}

3.邻接表的销毁

 销毁时需要将每个顶点的空间释放掉,仅需要获取每个顶点邻接边的链表头,然后遍历做删除操作即可:

void GraphDestroy(Graph* g) {for(int i=0;i<g->vertices;i++){EdgeNode* cur=g->nodes[i].firstEdge;while(cur){EdgeNode* temp=cur;cur=cur->next;free(temp);}}free(g->nodes);g->nodes=NULL;}

 4.邻接表的边添加

 操作结果是是添加一条u->v,权值为w的有向边,需要新定义一个边结点,将v作为该边结尾的顶点,w赋给该有向边的权值。然后将新边结点的后继next指向第u号元素的链表头,最后将链表头更新为新的边结点:

void GraphAddEdge(Graph* g,int u,int v,int w) {EdgeNode* nownode=(EdgeNode*)malloc(sizeof(EdgeNode));nownode->vertex=v;nownode->weight=w;nownode->next=g->nodes[u].firstEdge; //典型的头插法 g->nodes[u].firstEdge=nownode; }  

 5.邻接表的打印

void GraphPrint(Graph* g) {for(int i=0;i<g->vertices;i++){EdgeNode* cur=g->nodes[i].firstEdge;printf("Vertex %d:",i);while(cur){printf("%d(%d)",cur->vertex,cur->weight);cur=cur->next;}printf("\n");} } 

打印就是将该图遍历一遍,并且将顶点值与该顶点的边结点(包括边结尾顶点值)及权重依次打印出来。

例如下面有向图:

 打印的结果应该为:

完整源码

#include <stdio.h>#include <stdlib.h>typedef struct EdgeNode {int vertex;  //这条边的结尾顶点 int weight;  //这条边上的权重 struct EdgeNode* next;  //指向下一条边 } EdgeNode; typedef struct VertexNode {int vertex;  //顶点数据域 EdgeNode* firstEdge;  //指向该节点的第一条边 } VertexNode; typedef struct Graph {int vertices;  //结点的数量 VertexNode* nodes;  //用来记录每个结点 } Graph; void GraphCreat(Graph* g,int vertices) {  //传入的参数是表g和结点的数量vertices g->vertices=vertices;  g->nodes=(VertexNode*)malloc(sizeof(VertexNode)*vertices);//为g->node分配空间 for(int i=0;i<g->vertices;i++){     g->nodes[i].vertex=i;          //将每个结点的数据初始化为结点编号g->nodes[i].firstEdge=NULL;    //且将结点指向的第一条边置空 }}void GraphDestroy(Graph* g) {for(int i=0;i<g->vertices;i++){EdgeNode* cur=g->nodes[i].firstEdge;while(cur){EdgeNode* temp=cur;cur=cur->next;free(temp);}}free(g->nodes);g->nodes=NULL;}void GraphAddEdge(Graph* g,int u,int v,int w) {EdgeNode* nownode=(EdgeNode*)malloc(sizeof(EdgeNode));nownode->vertex=v;nownode->weight=w;nownode->next=g->nodes[u].firstEdge; //典型的头插法 g->nodes[u].firstEdge=nownode; }  void GraphPrint(Graph* g) {for(int i=0;i<g->vertices;i++){EdgeNode* cur=g->nodes[i].firstEdge;printf("Vertex %d:",i);while(cur){printf("%d(%d)",cur->vertex,cur->weight);cur=cur->next;}printf("\n");} } int main (){Graph g;GraphCreat(&g,5);GraphAddEdge(&g,0,1,4);GraphAddEdge(&g,0,2,2);GraphAddEdge(&g,1,2,3);GraphAddEdge(&g,2,3,4);GraphAddEdge(&g,3,4,2);GraphPrint(&g);GraphDestroy(&g);return 0; }


点击全文阅读


本文链接:http://zhangshiyu.com/post/200031.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 她的记忆停留在了最爱初恋的那年许欣柔楚临川完本_她的记忆停留在了最爱初恋的那年(许欣柔楚临川)
  • 全书浏览假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)_假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)全书结局
  • 童养夫让我给他的新欢出修复费(林嘉芝林思雅)_童养夫让我给他的新欢出修复费林嘉芝林思雅
  • 全文资助生女婿让我给他白月光付三千万月子中心钱(宋清玉宋雅)列表_全文资助生女婿让我给他白月光付三千万月子中心钱
  • 碎在时光里的谎言喻景宴秦明月完本_碎在时光里的谎言(喻景宴秦明月)
  • 旧爱剜心吻成灰席鄢之岑秋全书免费旧爱剜心吻成灰席鄢之岑秋全书免费
  • 结婚六年丈夫不碰我谁知儿子亲爹是寡头(纪清言傅司砚),结婚六年丈夫不碰我谁知儿子亲爹是寡头
  • 老公想换掉我的男胎,我笑他自不量力(宋薇于继业)_老公想换掉我的男胎,我笑他自不量力宋薇于继业
  • 给太子下了噬心蛊后,皇后找上门(小夭赵劼)全书浏览_给太子下了噬心蛊后,皇后找上门全书浏览
  • 豪门绝嗣!带球跑的夫人回来了!(谢长宴慕清杳)_豪门绝嗣!带球跑的夫人回来了!谢长宴慕清杳
  • 完美身材(李朵林之晴)_完美身材李朵林之晴
  • 离婚后,我和快穿系统绑定(白意秋陈荣周立慧)_离婚后,我和快穿系统绑定(白意秋陈荣周立慧)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1