有向图十字链表的创建 - C语言

╰半橙微兮° 2022-11-20 12:58 167阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
代码还是要求严格的输入操作，没有判错能力。见谅！  
代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX_VERTEX_NUM 20
    
    void Interrupt(void)//创建一个中断函数 
    { 
    	while(1)//用于检测换行符，使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    } 
    
    typedef struct ArcBox
    { 
    	int tailvex,headvex;//该弧的尾和头顶点的位置 
    	struct ArcBox *hlink,*tlink;//分别为弧头相同和弧尾相同的弧的链域 
    	int weight;//权值 
    }ArcBox;
    typedef struct VexNode
    { 
    	char data;//弧的名称 
    	ArcBox *firstin,*firstout;//分别指向该顶点第一条入弧和出弧 
    }VexNode;
    typedef struct
    { 
    	VexNode xlist[MAX_VERTEX_NUM];//表头向量 
    	int vexnum,arcnum;//有向图的当前顶点数和弧数 
    }OLGraph;
    
    void CreateGraph(OLGraph &G)//图的创建 
    { 
    	int i;//记录次数 
    	printf("请输入顶点数和边数: ");
    	scanf("%d %d",&G.vexnum,&G.arcnum);//顶点数和边数的赋值 
    	Interrupt();//该函数用于检测并吸收换行符 
    	for(i=0;i<G.vexnum;i++)//图的初始化，放在给定顶点之后可省去步骤 
    	{ 
    		G.xlist[i].firstin = NULL; 
    		G.xlist[i].firstout = NULL;
    	}
    	printf("请输入顶点名称（连续输入）：");
    	for(i=0;i<G.vexnum;i++)//利用循环输入图中顶点名称 
    		scanf("%c",&G.xlist[i].data);//第i个顶点的命名 
    	Interrupt();//该函数用于检测并吸收换行符
    	char b,c;//顶点变量 
    	int w,j,k,l;//w为权值变量，j和k是用来记录次数的 
    	ArcBox *p1,*p2;//创建两个野结点 
    	for(i=0;i<G.arcnum;i++)//利用循环输入所有边的两个顶点和权值 
    	{ 
    		printf("请输入边的两个顶点和权值w:");
    		scanf("%c %c %d",&b,&c,&w);//输入 
    		Interrupt();//该函数用于检测并吸收换行符
    		for(j=0;j<G.vexnum;j++)//该操作为书上的函数LocateVex操作 
    		{ 
    			if(G.xlist[j].data == b)//找到输入的顶点b的位置 
    			break;
    		}
    		for(k=0;k<G.vexnum;k++)
    		{ 
    			if(G.xlist[k].data == c)//找到输入的顶点c的位置 
    			break;
    		}
    		//出弧操作 
    		p1 = (ArcBox*)malloc(sizeof(ArcBox));//申请空间 
    		p1->hlink = p1->tlink = NULL;//初始化 
    		p1->headvex = j;
    		p1->tailvex = k;//尾位置和头位置的赋值 
    		p1->weight = w;//权值赋值
    		p1->hlink = G.xlist[j].firstout;//类似于头插法 
    		G.xlist[j].firstout = p1;	//并使头结点永远放在第一位 
    		//入弧操作
    		if(G.xlist[k].firstin == NULL) 
    			G.xlist[k].firstin = p1;
    		else
    		{ 
    			p2 = G.xlist[k].firstin;
    			while(p2->tlink != NULL)
    				p2 = p2->tlink;
    			p2->tlink = p1;
    		}
    	}
    }
    
    void InputGraph(OLGraph G)//十字链表的输出 
    { 
    	int i,j;//记录次数 
    	ArcBox *p;//用于遍历链表 
    	printf("十字链表为：\n");
    	//为了能验证创建的图是否正确，分别输出顶点的入弧和出弧 
    	//出弧 
    	for(i=0;i<G.vexnum;i++)//利用循环输出 
    	{ 
    		printf("%c",G.xlist[i].data);
    		p = G.xlist[i].firstout;
    		while(p)//当p为空时，结束循环 
    		{ 
    			printf(" -[%d]-> %d-%d",p->weight,p->headvex,p->tailvex);
    			p = p->hlink;//p指向p的下一个结点 
    		}	
    		printf("\n");
    	}
    	//入弧 
    	for(i=0;i<G.vexnum;i++)//利用循环输出 
    	{ 
    		printf("%c",G.xlist[i].data);
    		p = G.xlist[i].firstin;
    		while(p)//当p为空时，结束循环 
    		{ 
    			printf(" <-[%d]- %d-%d",p->weight,p->headvex,p->tailvex);
    			p = p->tlink;//p指向p的下一个结点 
    		}	
    		printf("\n");
    	}
    }
    
    int main()
    { 
    	OLGraph G;
    	CreateGraph(G);//图的创建 
    	InputGraph(G);//图的输出 
    	return 0;
    }

代码结果演示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/bc425ab84338424dafc2ee9ae8c12ef5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/8d9d252c3c67417a9d1379d609d33c2b.png