十字链表以及实现

一、图的表示优缺点

1.邻接矩阵：适合表示无向图、有向图、有权无权图

缺点：如果存的稀疏矩阵，冗余空间多

2.邻接表：适合存有向图、有权无权图

缺点：a.只存出度，计算入度非常麻烦

b.无向图时，边要表示两次，删除麻烦

3.十字链表：适合有向图，顶点集里既存出度也存入度

4.邻接多重表：适合无向图，一条无向边，用一个节点表示，便于删除

5.边集数组（小众）：只关心边的情况，常用于最小生成树

二，十字链表代码逻辑

要使得链表能够存储入度和出度，我们的节点得有两个指针，一个指向入度firstin、一个指向出度firstout

而我们的边结构有四个成员，弧尾tailvex、弧头headvex、以当前节点为弧头、以当前节点为弧尾

三，十字链表代码实现

1.头文件中的接口

//
// Created by 27893 on 2025/7/27.
//#ifndef CROSSLINKGRAPH_H
#define CROSSLINKGRAPH_H
//十字链表边结构
typedef struct _Arc{int tailVertex;struct _Arc*tailNext;int headVertex;struct _Arc*headNext;int weight;
}ArcBox;
//十字链表顶点结构
typedef struct {int no;char*show;ArcBox*firstIn;ArcBox*firstOut;
}CrossVertex;
//十字链表图头
typedef struct {CrossVertex*nodes;int numVertex;int numEdge;
}CrossGraph;CrossGraph*createCrossGraph(int n);void initCrossGraph(CrossGraph*graph,const char*names[],int num);void addCrossArc(CrossGraph*graph,int tail,int head,int weight);void releaseCrossGraph(CrossGraph*graph);int inDegreeCrossGraph(CrossGraph*graph,int no);int outDegreeCrossGraph(CrossGraph*graph,int no);
#endif //CROSSLINKGRAPH_H

2.将接口一一实现 

//
// Created by 27893 on 2025/7/27.
//#include <stdio.h>
#include <stdlib.h>
#include "CrossLinkGraph.h"CrossGraph * createCrossGraph(int n) {CrossGraph*graph=malloc(sizeof(CrossGraph));if (graph==NULL) {return NULL;}graph->nodes=malloc(sizeof(CrossVertex)*n);if (graph->nodes==NULL) {free(graph);return NULL;}graph->numVertex=0;graph->numEdge=0;return graph;
}void initCrossGraph(CrossGraph *graph, const char *names[], int num) {graph->numVertex=num;for (int i=0;i<num;i++) {graph->nodes[i].show=names[i];graph->nodes[i].no=i;graph->nodes[i].firstIn=graph->nodes[i].firstOut=NULL;}
}void addCrossArc(CrossGraph *graph, int tail, int head, int weight) {ArcBox*Arc=malloc(sizeof(ArcBox));if (Arc==NULL) {return;}Arc->tailVertex=tail;Arc->headVertex=head;Arc->weight=weight;//头插法处理出度问题Arc->tailNext=graph->nodes[tail].firstOut;graph->nodes[tail].firstOut=Arc;//头插法处理入度问题Arc->headNext=graph->nodes[head].firstIn;graph->nodes[head].firstIn=Arc;
}void releaseCrossGraph(CrossGraph *graph) {int count=0;if (graph==NULL) {return ;}for (int i=0;i<graph->numVertex;i++) {ArcBox*box=graph->nodes[i].firstOut;ArcBox*temp;while (box) {temp=box;box=box->tailNext;free(temp);++count;}}printf("release %d edges",count);free(graph->nodes);free(graph);
}
//计算入度个数
int inDegreeCrossGraph(CrossGraph *graph,int no) {ArcBox*box=graph->nodes[no].firstIn;int count=0;while (box) {box=box->headNext;count++;}return count;
}
//计算出度个数
int outDegreeCrossGraph(CrossGraph *graph,int no) {ArcBox*box=graph->nodes[no].firstOut;int count=0;while (box) {box=box->tailNext;count++;}return count;
}

3.测试代码是否有bug

//
// Created by 27893 on 2025/7/27.
//
#include "CrossLinkGraph.h"
#include <stdio.h>
void setupGraph(CrossGraph*graph) {char *nodeNames[] = {"V0", "V1", "V2", "V3"};initCrossGraph(graph, nodeNames,sizeof(nodeNames) / sizeof(nodeNames[0]) );addCrossArc(graph, 0, 3, 1);addCrossArc(graph, 1, 0, 1);addCrossArc(graph, 1, 2, 1);addCrossArc(graph, 2, 0, 1);addCrossArc(graph, 2, 1, 1);
}
int main() {CrossGraph *graph = createCrossGraph(4);setupGraph(graph);printf("V1 inDegree: %d\n", inDegreeCrossGraph(graph, 0));printf("V1 outDegree: %d\n", outDegreeCrossGraph(graph, 0));releaseCrossGraph (graph);return 0;
}