【数据结构】图的存储结构之十字链表的创建（C语言）

「爱情、让人受尽委屈。」 2023-02-25 08:43 11阅读 0赞

## 定义 ##

对于有向图图来说，邻接表是有缺陷。关心了出度问题，想了解入度就必须要遍历整个图才可以知道，反之，逆邻接表解决了入度却不了解出度的情况。有没有可能把**邻接表与逆邻接表结合**起来呢？答案是肯定的，就是把它们整合在一起、**这就是有向图一种存储方法：十字链表**

定义顶点结构如图1-1所示。  
![在这里插入图片描述][20200711165938502.png_pic_center]

图1-1

**firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。**

边表结点结构如图1-2所示。  
![在这里插入图片描述][20200711170223422.png_pic_center]

图1-2  
**tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向结点相同的下一条边。如果是网，还可以增加一个weight域来存储权值。**

## 十字链表的优点： ##

1.  十字链表是把邻接表和逆邻接表整合在一起，这样既容易找到以Vi为尾的弧，也容易找到以Vi为头的弧，因而容易求的顶点的出度和入度。
2.  十字链表创建图算法的时间复杂度和邻接表是相同的。

## 代码 ##

#include <iostream>
    #include <cstdio>
    #include <stdlib.h>
    #include <cstring>
    using namespace std;
    #define MAX_VERTEX_NUM 20
    #define OVERFLOW -2
    #define OK 1
    typedef int Status;
    typedef char VertexType[MAX_VERTEX_NUM];
    typedef char InfoType;
    //弧（边）的结构体
    typedef struct ArcBox
    {
        
    	int tailvex,headvex;  						//该弧的尾和头顶点的位置
    	struct ArcBox *hlink, *tlink;  				//分别为弧头同样和弧尾同样的弧的链域
    	InfoType *info;  							//该弧的相关信息的指针
    }ArcBox;
    
    //顶点的结构体
    typedef struct VexNode
    {
        
    	VertexType data;
    	ArcBox *firstin, *firstout;  //分别指向该顶点的第一条入弧和出弧
    }VexNode;
    
    //有向图的结构体
    typedef struct  
    {
        
    	VexNode xlist[MAX_VERTEX_NUM];  	//表头向量
    	int vexnum, arcnum;  				//有向图的当前顶点数和弧数
    }OLGraph;
    
    int LocateVex(OLGraph &G, VertexType u)
    {
        
    	for(int i = 0; i < G.vexnum; ++i)
    		if(strcmp(G.xlist[i].data, u) == 0)
    			return i;
    	return -1;
    }
    
    //构造有向图G;
    Status CreateDG(OLGraph &G)
    {
        
    	
    	int i,j,k;
    	printf("请输入有向图的顶点数以及弧数:\n");
    	scanf("%d%d",&G.vexnum, &G.arcnum);
    	printf("请输入%d个顶点的值，之间有空格隔开:\n",G.vexnum);
    	for(i=0; i<G.vexnum; ++i) //构造表头向量
    	{
        
    		getchar();
    		scanf("%s",G.xlist[i].data);  //输入顶点值
    		G.xlist[i].firstin = NULL;
    		G.xlist[i].firstout = NULL;
    	}
    	
    	VertexType v1,v2;
    	ArcBox *p;
    	printf("请依次输入%d条弧各自依附的两个顶点（输入格式:v1 v2）\n",G.arcnum);
    	for(k=0; k < G.arcnum; ++k)  //输入各弧并构造十字链表
    	{
        
    		getchar();
    		scanf("%s%s",v1,v2);
    		i=LocateVex(G,v1);
    		j=LocateVex(G,v2);
    		p = (ArcBox *)malloc(sizeof(ArcBox));
    		if(!p)
    			exit(OVERFLOW);
    		p->tailvex = i;
    		p->headvex = j;
    		p->hlink = G.xlist[j].firstin;
    		p->tlink = G.xlist[i].firstout;
    		p->info = NULL;
    		G.xlist[j].firstin = G.xlist[i].firstout = p;  //完毕在入弧和出弧链头的插入
    	}
    	getchar();
    	return OK;
    }
    
    void DisplayArc(OLGraph &G)
    {
        
    	ArcBox *p;
    	for(int i=0; i < G.vexnum; ++i)
    	{
        
    		p=G.xlist[i].firstout;
    		while(p)
    		{
        
    			printf("<%s,%s> ",G.xlist[p->tailvex].data, G.xlist[p->headvex].data);
    			p = p->tlink;
    		}
    	}
    	printf("\n");
    }
    
    
    //顶点的度：入度+出度
    int VexDegree(OLGraph &G, VertexType v)
    {
        
    	
    	int k = LocateVex(G,v);
    	if(k<0)
    		exit(OVERFLOW);
    	int id=0,od=0;  //入度，出度
    
    	ArcBox *pin = G.xlist[k].firstin;
    	ArcBox *pout = G.xlist[k].firstout;
    	while(pin)  //求入度
    	{
        
    		++id;
    		pin = pin->hlink;
    	}
    
    	while(pout)  //求出度
    	{
        
    		++od;
    		pout = pout->tlink;
    	}
    
    	return id+od; //顶点的度
    }
    
    int main()
    {
        
    	int flag = 1;
    	OLGraph G;
    	CreateDG(G);
    	printf("=========================================\n");
    	printf("该有向图的弧例如以下:\n");
    	DisplayArc(G);
    	VertexType v;
    	printf("\n=========================================\n");
    	while(1)
    	{
        
    		if(flag == 0)
    				break;
    		printf("请输入随意顶点,将输出该顶点度的值:");
    		scanf("%s",v);
    		getchar();
    		printf("顶点 %s 的度为 :%d\n",v,VexDegree(G,v));
    		printf("结束请输入 0 以回车键结束\n\n");
    		cin>>flag;
    	}
    	printf("=========================================\n");
    	return 0;
    }

[20200711165938502.png_pic_center]: /images/20230209/6d07149e37e84c3884cc4eee38c089c9.png
[20200711170223422.png_pic_center]: /images/20230209/3de83607727e4a53a70f9770dc5ad89b.png