数据结构之图论之十字链表

男娘i 2022-05-12 05:52 199阅读 0赞

代码演示：（包含建立和打印过程）

//建立一个十字链表 
    
    #include <iostream>
    #include <stdlib.h>
    #define maxn 40000
    using namespace std;
    
    typedef struct{
    	int adjvex,weight;
    	EdgeNode *next;
    }EdgeNode;
    
    typedef struct{
    	int data;
    	EdgeNode *firstin,*firstout;
    }VexNode,Vexlist[maxn];
    
    typedef struct{
    	Vexlist vexlist;
    	int numvertex,numedge;
    }GraAdj;
    
    void create(GraAdj &g)
    {
    	int m,n;
    	EdgeNode *e,*p1,*p2;
    	cin>>g.numedge>>g.numvertex;
    	for(int i=0;i<g.numvertex;i++){
    		cin>>g.vexlist[i].data;
    		g.vexlist[i].firstin=NULL;
    		g.vexlist[i].firstout=NULL;
    	}
    	for(int i=0;i<g.numedge;i++){
    		cin>>m>>n;//输入尾头结点的下标 
    		e=(EdgeNode*)malloc(sizeof(EdgeNode));
    		e.adjvex=n;
    		e.next=NULL;
    		if(g.vexlist[m].firstout==NULL)
    			p1=g.vexlist[m].firstout=e;
    		else
    			p1=p1->next=e;
    	
    		if(g.vexlist[n].firstin==NULL)
    			p2=g.vexlist[n].firstin=e;
    		else
    			p2=p2->next=e;
    	}
    }
    //打印有向图的十字链表 
    void prin(GraAdj g)
    {
    	for(int i=0;i<g.numvertex;i++){
    		EdgeNode *in=g.vexlist[i].firstin,*out=g.vexlist[i].firstout;
    		cout<<"以"<<i<<"为尾结点的链："<<i;
    		while(out!=NULL){
    			cout<<"->"<<out->adjvex;
    		}
    		cout<<endl;
    		
    		cout<<"以"<<i<<"为头结点的链："<<i; 
    		while(in!=NULL){
    			cout<<"<-"<<in->adjvex;
    		} 
    		cout<<endl;
    	} 
    }

十字链表基于邻接表，但是却弥补了邻接表不能够很方便的处理出度和入度的问题。

如果读者对邻接表不熟悉，可以查看我的上一篇博客