文章目录

一、十字链表二、代码示例    

一、十字链表

  邻接表在某种程度上是有缺陷的，它表示了出度就表示不了入度。所以出现了十字链表，它既能表示入度也能表示出度。   说通俗点，十字链表也就是邻接表的改进，顶点集包含两个指针，firstIn和firstOut, firstIn指向入边表（逆邻接表）， firstOut表示出边表（也就是邻接表）。（需要先理解上面代码中顶点集和边节点的结构）。理解了上一篇博文的邻接表与逆邻接表，十字链表也就没有难道了。

 

二、代码示例

orthogonalListGraph.h

#ifndef __GRAPH__H #define __GRAPH__H /*邻接矩阵*/ #define MAX_VERTEX 100 typedef char vertexType; typedef int weightType; /*十字链表*/ typedef struct _edgeNode { vertexType vertex; vertexType againVertex; weightType weight; struct _edgeNode *next; struct _edgeNode *againNext; } edgeNode_s, *edgeNode_p; typedef struct _vertexGraph { vertexType vertex; edgeNode_p fistIn; edgeNode_p fistOut; }vertexGraph[MAX_VERTEX], vertexGraph_s; typedef struct _OrthogonalListGraph { int numEdges, numVertex; vertexGraph graph; } ortListGraph_s, *ortListGraph_p; #endif

orthogonalListGraph.c

#include <stdio.h> #include <stdlib.h> #include "graph.h" #include <string.h> #ifdef OrthogonalList int locateGraph(ortListGraph_p adjGraph, vertexType c) { int i; for (i = 0; i < adjGraph->numVertex; i++) { if (adjGraph->graph[i].vertex == c) return i; } return -1; } int printfGraph(ortListGraph_p adjGraph) { int i; edgeNode_p p1,p2; if (!adjGraph) return -1; printf("Out:\n"); for(i = 0; i < adjGraph->numVertex; i ++) { printf("%c->", adjGraph->graph[i].vertex); p1 = adjGraph->graph[i].fistOut; while(p1) { p2 = p1->next; printf("%c(%d),", p1->vertex, p1->weight); p1 = p2; } printf("\n"); } printf("In:\n"); for(i = 0; i < adjGraph->numVertex; i ++) { printf("%c<-", adjGraph->graph[i].vertex); p1 = adjGraph->graph[i].fistIn; while(p1) { p2 = p1->againNext; printf("%c(%d),", p1->againVertex, p1->weight); p1 = p2; } printf("\n"); } return 0; } int crateOrtListGraph(ortListGraph_p ortGraph) { int i, j, k, w; vertexType x,y; edgeNode_p edgeNode; if (!ortGraph) return -1; printf("input numEages(int):"); if (1 != scanf("%d", &(ortGraph->numEdges))) { printf("input error\n");return -2;} printf("input numVertex(int):"); if (1 != scanf("%d", &(ortGraph->numVertex))) { printf("input error\n");return -2;} if (ortGraph->numVertex > MAX_VERTEX) return -1; for (i = 0; i < ortGraph->numVertex; i++) { printf("input vertex(char):"); ortGraph->graph[i].vertex = getchar(); while(ortGraph->graph[i].vertex == '\n') ortGraph->graph[i].vertex = getchar(); } for (k = 0; k < ortGraph->numEdges; k ++) { printf("input vertex(char) and weight(int):\n"); x = getchar(); while(x == '\n') x = getchar(); y = getchar(); while(y == '\n') y = getchar(); scanf("%d", &w); i = locateGraph(ortGraph, x); j = locateGraph(ortGraph, y); if (i == -1 || j == -1) { printf("input error\n"); k --; continue; } edgeNode = (edgeNode_p)malloc(sizeof(*edgeNode)); if (!edgeNode) return -2; edgeNode->weight = w; edgeNode->vertex = y; edgeNode->next = ortGraph->graph[i].fistOut; ortGraph->graph[i].fistOut = edgeNode; edgeNode->againVertex = x; edgeNode->againNext = ortGraph->graph[j].fistIn; ortGraph->graph[j].fistIn = edgeNode; } return 0; } #endif

              关注公众号"小败日记"，搬砖过程遇到的问题，大家一起探讨，资源共享