看数据结构写代码（37） 图的十字链表的表示与实现

图的邻接表在 查找 有向图的 出度 很 方便，，但是 在 查找 入度 时，需要遍历整个图。如果想要 方便的 查找 入度，需要 建立 逆邻接表。十字链表 正好 就是 邻接表 和 逆邻接表的集合。具体结构图如下：

感觉 十字链表 在 查找 入度时 方便 一些，其他 跟 邻接表没什么区别。

代码如下：

// CrossLinkGraph.cpp : 定义控制台应用程序的入口点。//有向图的十字链表表示法#include "stdafx.h"#include <cstdlib>#define MAX_VEX_NUM 20enum E_State{E_State_Error = 0,E_State_Ok = 1,};struct ArcNode//弧节点{int tailIndex;//弧尾位置int headIndex;//弧头位置ArcNode * tailNext;//下一个弧尾相同的弧ArcNode * headNext;//下一个弧头相同的弧};typedef struct VNode{char vexName;//顶点名称ArcNode * firstIn;ArcNode * firstOut;}GraphList[MAX_VEX_NUM];//struct Graph{GraphList list;//顶点数组.int vexNum,arcNum;};//获取弧 的 头节点ArcNode * getHeadNode(){ArcNode * pNode = (ArcNode *)malloc(sizeof(ArcNode));if (pNode){pNode->headIndex = pNode->tailIndex = -1;pNode->headNext = pNode->tailNext = NULL;}return pNode;}ArcNode * getArcNode(int tailIndex,int headIndex){ArcNode * pNode = getHeadNode();if (pNode){pNode->headIndex = headIndex;pNode->tailIndex = tailIndex;}return pNode;}int vexLocation(Graph g,char vex){for (int i = 0; i < g.vexNum; i++){if (g.list[i].vexName == vex){return i;}}return -1;}void createGrahp(Graph * g){printf("输入图的顶点数 和 边（弧）数\n");scanf("%d%d%*c",&g->vexNum,&g->arcNum);//构造顶点集printf("请输入顶点集\n");for (int i = 0; i < g->vexNum; i++){char name;scanf("%c",&name);g->list[i].vexName = name;g->list[i].firstIn = g->list[i].firstOut = getHeadNode();//建立 头节点，并让头指针指向头节点}//构造顶点关系fflush(stdin);printf("请输入顶点的关系\n");for (int i = 0; i < g->arcNum; i++){char vex1,vex2;scanf("%c%c%*c",&vex1,&vex2);int location1 = vexLocation(*g,vex1);int location2 = vexLocation(*g,vex2);ArcNode * pNode = getArcNode(location1,location2);pNode->tailNext = g->list[location1].firstOut->tailNext;g->list[location1].firstOut->tailNext = pNode;pNode->headNext = g->list[location2].firstIn->headNext;g->list[location2].firstIn->headNext = pNode;} }//只要删除所有顶点的弧尾（或者弧头）节点即可，//同时删除弧头弧尾 ，内存错误void destoryGraph(Graph * g){for (int i = 0; i < g->vexNum; i++){ArcNode * next = g->list[i].firstOut;//删除所有弧尾while (next != NULL){ArcNode * freeNode = next;next = next->tailNext;free(freeNode);}g->list[i].firstIn = g->list[i].firstOut = NULL;g->list[i].vexName = ' ';g->vexNum = g->arcNum = 0;}}//顶点vex1 和顶点vex2 是否相邻bool graphIsAdj(Graph g,char vex1,char vex2){int location = vexLocation(g,vex1);ArcNode * next = g.list[location].firstOut->tailNext;while (next != NULL){if (g.list[next->headIndex].vexName == vex2){return true;}next = next->tailNext;}return false;}int graphDegree(Graph g,char vex){int degree = 0;int locaiton = vexLocation(g,vex);ArcNode * next = g.list[locaiton].firstOut->tailNext;//计算所有出度while (next != NULL){degree++;next = next->tailNext;}next = g.list[locaiton].firstIn->headNext;//计算所有入度while (next != NULL){degree++;next = next->headNext;}return degree;}char firstAdj(Graph g,char vex){int location = vexLocation(g,vex);ArcNode * next = g.list[location].firstOut->tailNext;if (next != NULL){return g.list[next->headIndex].vexName;}return ' ';}char nextAdj(Graph g,char vex1,char vex2){int location = vexLocation(g,vex1);ArcNode * next = g.list[location].firstOut->tailNext;while (next != NULL){//查找到 vex2if (g.list[next->headIndex].vexName == vex2){break;}next = next->tailNext;}if (next != NULL){ArcNode * nextNode = next->tailNext;if (nextNode != NULL){return g.list[nextNode->headIndex].vexName;}}return ' ';}//插入边（弧）void insertArc(Graph * g,char vex1,char vex2){int location1 = vexLocation(*g,vex1);int location2 = vexLocation(*g,vex2);ArcNode * node = getArcNode(location1,location2);node->tailNext = g->list[location1].firstOut->tailNext;g->list[location1].firstOut->tailNext = node;node->headNext = g->list[location2].firstIn->headNext;g->list[location2].firstIn->headNext = node;g->arcNum ++;}//删除边（弧）void deleteArc(Graph * g,char vex1,char vex2){g->arcNum–;int location1 = vexLocation(*g,vex1);int location2 = vexLocation(*g,vex2);ArcNode * next = g->list[location1].firstOut->tailNext;ArcNode * pre = g->list[location1].firstOut;while (next != NULL){//在更改 尾部相同的 链表时，不能删除 弧if (next->headIndex == location2){pre->tailNext = next->tailNext;//free(next);break;}pre = next;next = next->tailNext;}next = g->list[location2].firstIn->headNext;pre = g->list[location2].firstIn;//在更改弧头相同的链表时，释放空间.while (next != NULL){if (next->tailIndex == location1){pre->headNext = next->headNext;free(next);break;}pre = next;next = next->headNext;}}//插入顶点void insertVex(Graph * g, char vex){if (g->vexNum < MAX_VEX_NUM){g->list[g->vexNum].vexName = vex;g->list[g->vexNum].firstIn = g->list[g->vexNum].firstOut = getHeadNode();g->vexNum++;}}//删除顶点void deleteVex(Graph * g,char vex){int location = vexLocation(*g,vex);//删除顶点 同样需要 遍历整个 图 查找 与 vex 相关的弧节点for (int i = 0; i < g->vexNum; i++){ArcNode * next = g->list[i].firstOut->tailNext;while (next != NULL){if (next->headIndex == location || next->tailIndex == location){ArcNode * delNode = next;next = next->tailNext;char delData1 = g->list[delNode->tailIndex].vexName;char delData2 = g->list[delNode->headIndex].vexName;deleteArc(g,delData1,delData2);}else{next = next->tailNext;}}}for (int i = 0; i < g->vexNum; i++){ArcNode * next = g->list[i].firstOut->tailNext;while (next != NULL){if(next->headIndex > location){next->headIndex –;}if(next->tailIndex > location){next->tailIndex –;}next = next->tailNext;}}free(g->list[location].firstIn);//释放头节点//vex下面的 顶点上移for (int i = location + 1; i < g->vexNum; i++){g->list[i-1] = g->list[i];}g->vexNum –;}void printGrahp(Graph g){for (int i = 0; i < g.vexNum; i++){printf("以%c为弧尾的 顶点有：",g.list[i].vexName);ArcNode * next = g.list[i].firstOut->tailNext;//删除所有弧尾while (next != NULL){printf("%c",g.list[next->headIndex].vexName);next = next->tailNext;}printf("\n以%c为弧头的 顶点有：",g.list[i].vexName);next = g.list[i].firstIn->headNext;//删除所有弧尾while (next != NULL){printf("%c",g.list[next->tailIndex].vexName);next = next->headNext;}printf("\n");}}int _tmain(int argc, _TCHAR* argv[]){Graph g;createGrahp(&g);printGrahp(g);printf("图的顶点数：%d,边（弧）树为：%d\n",g.vexNum,g.arcNum);char * isAdj = graphIsAdj(g,'b','d')? "相邻" : "不相邻";int degree = graphDegree(g,'d');char first = firstAdj(g,'c');char next = nextAdj(g,'d','c');printf("c的第一个邻接点是%c,d的c邻接点的下一个邻接点是：%c\n",first,next);printf("b 和 d %s,d的度为：%d\n",isAdj,degree);insertVex(&g,'e');printf("插入e顶点之后图结构如下：\n");printGrahp(g);insertArc(&g,'a','e');printf("插入(a,e) 之后图结构如下：\n");printGrahp(g);deleteArc(&g,'d','c');printf("删除(d,c)之后图结构如下：\n");printGrahp(g);deleteVex(&g,'a');printf("删除顶点a之后图结构如下：\n");printGrahp(g);printf("图的顶点数：%d,边（弧）数为：%d\n",g.vexNum,g.arcNum);destoryGraph(&g);return 0;}运行截图：

回避现实的人，未来将更不理想。