数据结构——图的存储（十字链表）

谁践踏了优雅 2022-04-12 05:58 157阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define MAX_VERTEX_NUM 20 
    #define MAX 20
    #define error -1
    #define ok 1
    
    //弧节点
    typedef struct ArcBox
    {
    	int tailvex,headvex;
    	struct ArcBox *hlink,*tlink;
    }ArcBox;
    
    //顶点节点
    typedef struct VexNode
    {
    	char data;
    	ArcBox *firstin,*firstout;
    }VexNode;
    
    typedef struct 
    {
    	VexNode xlist[MAX_VERTEX_NUM];
    	int vexnum,arcnum;
    }OLGraph;												
    
    //函数原型
    void GreateDG(OLGraph &G);
    int LocatVex(OLGraph G,char v);
    void show(OLGraph G);
    
    int main()
    {
    	OLGraph G;
        GreateDG(G);
    	show(G);
    	return 0;
    }
    
    void GreateDG(OLGraph &G)
    {
    	int i,j,v;
    	ArcBox *p;
    	char v1,v2;
    	printf("请输入顶点的个数:");
    	scanf("%d",&G.vexnum);
    	printf("请输入边的条数:");
    	scanf("%d",&G.arcnum);
    	for(i=0;i<G.vexnum;i++)
    	{
    		printf("请输入顶点的名称:");
    		scanf(" %c",&G.xlist[i].data);
    		G.xlist[i].firstin=NULL;
    		G.xlist[i].firstout=NULL;
    	}
    	//开始构建十字链表
    	for(v=0;v<G.arcnum;v++)
    	{
    		printf("\n请输入第一个顶点名:");
    		scanf(" %c",&v1);
    		printf("请输入第二个顶点名:");
    		scanf(" %c",&v2);
    		i=LocatVex(G,v1);
    		j=LocatVex(G,v2);
    		p=(ArcBox*)malloc(sizeof(ArcBox));
    		p->tailvex=j;
    		p->headvex=i;
    		p->hlink=G.xlist[i].firstin;
            G.xlist[i].firstin=p;
    		p->tlink=G.xlist[j].firstout;
    		G.xlist[j].firstout=p;	
    	}
    }
    
    void show(OLGraph G)
    {
    	int i;
    	ArcBox *p,*q;
    	for(i=0;i<G.vexnum;i++)
    	{
    		p=G.xlist[i].firstin;
    		printf("%c :",G.xlist[i].data);
    		q=G.xlist[i].firstout;
    		while(p!=NULL)
    		{
    			printf("入 %d %d -> ",p->headvex,p->tailvex);
    			p=p->hlink;
    		}
    		printf("\n");
    		
    	}
    	for(i=0;i<G.vexnum;i++)
    	{
    		p=G.xlist[i].firstin;
    		printf("%c :",G.xlist[i].data);
    		q=G.xlist[i].firstout;
    		while(q!=NULL)
    		{
    			printf("出 %d %d -> ",q->headvex,q->tailvex);
    			q=q->tlink;
    		}
    		printf("\n");	
    	}
    }
    
    int LocatVex(OLGraph G,char v)
    {
    	int i;
    	for(i=0;i<G.vexnum;i++)
    	{
    		if(G.xlist[i].data==v)
    		{
    			return i;
    		}
    	}
    	return error;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dldHVnbHk_size_16_color_FFFFFF_t_70][]

![201812012256054.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0dldHVnbHk_size_16_color_FFFFFF_t_70]: /images/20220412/e18a5ed4a12b4e8285e72059a25820c0.png
[201812012256054.png]: /images/20220412/e0dc0a8c348345c2b1c1bcac47ae5a2e.png