无向图邻接多重表的创建 - c语言

青旅半醒 2022-11-21 04:25 162阅读 0赞

并不一定全，但是运行成功了。  
代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAX_VERTEX_NUM 20
    
    typedef enum{ unvisited,visited} VisitIf;//变量名称转换 
    typedef struct EBox
    { 
    	VisitIf mark;//变量mark只能取unvisited和visited；未访问和已访问 
    	int ivex,jvex;//该边依附的两个顶点的位置 
    	struct EBox *ilink,*jlink;//分别指向依附这两个顶点的下一条边 
    	int weight;//权值 
    }EBox;
    typedef struct VexBox
    { 
    	char data;
    	EBox *firstedge;//指向第一条依附该顶点的边 
    }VexBox;
    typedef struct
    { 
    	VexBox adjmulist[MAX_VERTEX_NUM];
    	int vexnum,edgenum;//无向图的当前顶点数和边数 
    }AMLGraph;
    
    void Interrupt(void)//创建一个中断函数 
    { 
    	while(1)//用于检测换行符，使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    } 
    
    void CreateGraph(AMLGraph &G)//图的创建 
    { 
    	int i;//记录次数 
    	printf("请输入顶点数和边数: ");
    	scanf("%d %d",&G.vexnum,&G.edgenum);//顶点数和边数的赋值 
    	Interrupt();//该函数用于检测并吸收换行符 
    	for(i=0;i<G.vexnum;i++)//图的初始化，放在给定顶点之后可省去步骤 
    		G.adjmulist[i].firstedge = NULL; 
    	printf("请输入顶点名称（连续输入）：");
    	for(i=0;i<G.vexnum;i++)//利用循环输入图中顶点名称 
    		scanf("%c",&G.adjmulist[i].data);//第i个顶点的命名 
    	Interrupt();//该函数用于检测并吸收换行符
    	char b,c;//顶点变量 
    	int w,j,k,l;//w为权值变量，j和k是用来记录次数的 
    	EBox *p1,*p2,*a;//创建两个野结点 
    	for(i=0;i<G.edgenum;i++)//利用循环输入所有边的两个顶点和权值 
    	{ 
    		printf("请输入边的两个顶点和权值w:");
    		scanf("%c %c %d",&b,&c,&w);//输入 
    		Interrupt();//该函数用于检测并吸收换行符
    		for(j=0;j<G.vexnum;j++)//该操作为书上的函数LocateVex操作 
    		{ 
    			if(G.adjmulist[j].data == b)//找到输入的顶点b的位置 
    			break;
    		}
    		for(k=0;k<G.vexnum;k++)
    		{ 
    			if(G.adjmulist[k].data == c)//找到输入的顶点c的位置 
    			break;
    		}
    		p1 = (EBox*)malloc(sizeof(EBox));//申请空间 
    		p1->ilink = p1->jlink = NULL;//初始化 
    		p1->ivex = j;
    		p1->jvex = k;//尾位置和头位置的赋值 
    		p1->weight = w;//权值赋值
    		if(G.adjmulist[j].firstedge == NULL)//判断是否为空 
    		{ 
    			p1->ilink = G.adjmulist[j].firstedge;
    			G.adjmulist[j].firstedge = p1;//为空时，直接插入 
    		}
    		else
    		{ 
    			p2 = G.adjmulist[j].firstedge;
    			if(j == p2->ivex)
    				a = p2->ilink;
    			else
    				a = p2->jlink;
    			while(a)
    			{ 
    				if(j == p2->ivex)
    				{ 
    					p2 = p2->ilink;
    					if(j == p2->ivex)
    						a = p2->ilink;
    					else
    						a = p2->jlink;
    				}
    				else
    				{ 
    					p2 = p2->jlink;
    					if(j == p2->ivex)
    						a = p2->ilink;
    					else
    						a = p2->jlink;
    				}
    			}	
    			if(j == p2->ivex)
    				p2->ilink = p1;
    			else
    				p2->jlink = p1;
    		}
    		if(G.adjmulist[k].firstedge == NULL)
    		{ 
    			p1->jlink = G.adjmulist[k].firstedge; 
    			G.adjmulist[k].firstedge = p1;	//并使头结点永远放在第一位 
    		}
    		else
    		{ 
    			p2 = G.adjmulist[k].firstedge;
    			if(j == p2->ivex)
    				a = p2->ilink;
    			else
    				a = p2->jlink;
    			while(a)
    			{ 
    				if(k == p2->ivex)
    				{ 
    					p2 = p2->ilink;
    					a = p2->ilink;
    				}
    				else
    				{ 
    					p2 = p2->jlink;
    					a = p2->jlink;
    				}
    			}	
    			if(k == p2->ivex)
    				p2->ilink = p1;
    			else
    				p2->jlink = p1;
    		}
    	}
    }
     
    void InputGraph(AMLGraph G)//邻接多重表的输出 
    { 
    	int i,j;//记录次数 
    	EBox *p1,*p2;//用于遍历链表 
    	printf("邻接多重表为：\n");
    	//为了能验证创建的图是否正确 
    	for(i=0;i<G.vexnum;i++)//利用循环输出 
    	{ 
    		printf("%c",G.adjmulist[i].data);
    		p1 = p2 = G.adjmulist[i].firstedge;
    		while(p1)//当p为空时，结束循环 
    		{ 
    			if(p1->ivex == i)
    			{ 
    				printf(" ilink -[%d]-> %d-%d",p1->weight,p1->ivex,p1->jvex);
    				p1 = p1->ilink;//p1指向p1的ilink 
    			}	
    			else
    			{ 
    				printf(" jlink -[%d]-> %d-%d",p1->weight,p1->ivex,p1->jvex);
    				p1 = p1->jlink;//p2指向p2的jlink
    			}	
    		}	
    		printf("\n");
    	}
    }
    int main()
    { 
    	AMLGraph G;
    	CreateGraph(G);//创建无向图 
    	InputGraph(G);//验证是否是邻接多重表 
    	return 0;
    }

结果演示：  
根据书上的例子进行输入得。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/67c12b6a2ba546a796d6132e98845e42.png