无向图邻接表的创建 - C语言

╰半橙微兮° 2022-11-20 08:25 164阅读 0赞

还是书上的。代码运行时的输入操作还是必须要严格进行。  
完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MVNum 100 //最大顶点数 
    
    void Interrupt(void)//创建一个中断函数 
    { 
    	while(1)//用于检测换行符，使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    } 
    
    typedef struct ArcNode
    { 
    	int adjvex;//该边所指向的顶点的位置 
    	struct ArcNode *nextarc;//该向下一条边的指针 
    	int weight;//权值 
    }ArcNode;
    typedef struct VNode//顶点信息 
    { 
    	char data;//顶点名称 
    	ArcNode *firstarc;//指向第一条依附该顶点的边的指针 
    }VNode,AdjList[MVNum];//AdjList表示邻接表类型 
    typedef struct//邻接表 
    { 
    	AdjList vertices;
    	int vexnum,arcnum;//图的当前顶点数和边数 
    }ALGraph;
    
    void InitGraph(ALGraph &G)//图的初始化 
    { 
    	int i;
    	for(i=0;i<MVNum;i++)
    		G.vertices[i].firstarc = NULL;//使所有的第一个结点都置空，也就是后面设定的尾指针的判空操作 
    }
    
    void CreateGraph(ALGraph &G)//图的创建 
    { 
    	int i;//记录次数 
    	char a;//顶点变量 
    	printf("请输入顶点数和边数:");
    	scanf("%d %d",&G.vexnum,&G.arcnum);//顶点数和边数的赋值 
    	Interrupt();//该函数用于检测并吸收换行符 
    	printf("请输入顶点名称（连续输入）：");
    	for(i=0;i<G.vexnum;i++)//利用循环输入图中顶点名称 
    	{ 
    		scanf("%c",&a);
    		G.vertices[i].data = a;//第i个顶点的命名 
    	}
    	Interrupt();//该函数用于检测并吸收换行符
    	char b,c;//顶点变量 
    	int w,j,k;//w为权值变量，j和k是用来记录次数的 
    	for(i=0;i<G.arcnum;i++)//利用循环输入所有边的两个顶点和权值 
    	{ 
    		printf("请输入边的两个顶点和权值w:");
    		scanf("%c %c %d",&b,&c,&w);//输入 
    		Interrupt();//该函数用于检测并吸收换行符
    		for(j=0;j<G.arcnum;j++)//该操作为书上的函数LocateVex操作 
    		{ 
    			if(G.vertices[j].data == b)//找到输入的顶点b的位置 
    			break;
    		}
    		for(k=0;k<G.arcnum;k++)
    		{ 
    			if(G.vertices[k].data == c)//找到输入的顶点c的位置 
    			break;
    		}
    		ArcNode *p1,*p2;//创建两个野结点 
    		p1 = (ArcNode*)malloc(sizeof(ArcNode));
    		p1->adjvex = k;
    		p1->weight = w;//权值赋值 
    		p1->nextarc = G.vertices[j].firstarc;//类似于头插法 
    		G.vertices[j].firstarc = p1;//并使头结点永远放在第一位 
    		p2 = (ArcNode*)malloc(sizeof(ArcNode));
    		p2->adjvex = j;
    		p2->weight = w;
    		p2->nextarc = G.vertices[k].firstarc;
    		G.vertices[k].firstarc = p2;
    	}
    }
    
    void InputGraph(ALGraph G)//邻接表的输出 
    { 
    	int i,j;//记录次数 
    	ArcNode *p;//用于遍历链表 
    	printf("邻接表为：\n");
    	for(i=0;i<G.vexnum;i++)//利用循环输出 
    	{ 
    		printf("%c",G.vertices[i].data);
    		p = G.vertices[i].firstarc;
    		while(p)//当p为空时，结束循环 
    		{ 
    			printf(" -[%d]-> %d",p->weight,p->adjvex);
    			p = p->nextarc;//p指向p的下一个结点 
    		}	
    		printf("\n");
    	}
    }
    
    int main()
    { 
    	ALGraph G;
    	InitGraph(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 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/c39e293b16534294af2ab8682f34c970.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/4bdab6b7ca1a4dc8bd3775d4888a9bb6.png