数据结构——图-有向带权图的邻接表基础

港控/mmm° 2022-12-29 06:36 153阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]  
![\`][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]

#include <stdio.h>
    #include <stdlib.h>
    #define VertexType char //顶点的数据类型（char） 
    #define VertexMax 20 //最大顶点个数 
    
    typedef struct ArcNode//边表 
    {
        
    	int adjvex;//存储的是该顶点在顶点数组即AdjList[]中的位置
    	int weight; 
    	struct ArcNode *next;
    }ArcNode;
    
    typedef struct VNode //单个顶点 
    {
        
    	VertexType vertex;
    	struct ArcNode *firstarc;
    }VNode;
    
    typedef struct //顶点表 
    {
        
    	VNode AdjList[VertexMax];//由顶点构成的结构体数组 
    	int vexnum,arcnum; //顶点数和边数 
    	
    }ALGraph;
    
    int LocateVex(ALGraph *G,VertexType v)
    {
            
        int i;
    	for(i=0;i<G->vexnum;i++)
    	{
        
    		if(v==G->AdjList[i].vertex)
    		{
        
    			return i;
    		}
    	}
    	
    	printf("No Such Vertex!\n");
    	return -1;
    }
    
    
    void CreateDG(ALGraph *G)
    {
        
    	int i,j;
    	//1.输入顶点数和边数 
    	printf("有向带权图\n"); 
    	printf("输入顶点个数和边数：\n");
    	printf("顶点数 n="); 
    	scanf("%d",&G->vexnum);
    	printf("边  数 e="); 
    	scanf("%d",&G->arcnum);
    	printf("\n\n"); 
    
    	//2.顶点表数据域填值初始化顶点表指针域 
    	printf("输入顶点元素(需要用空格隔开)：");
    	for(i=0;i<G->vexnum;i++)
    	{
        
    		scanf(" %c",&G->AdjList[i].vertex);
    		G->AdjList[i].firstarc=NULL;
    	} 
    	printf("\n");
    	
    	//3.输入边信息构造邻接表 
    	int n,m;
    	VertexType v1,v2;
    	ArcNode *p1,*p2; 
    	int value;
    	printf("请输入边的信息(需要用空格隔开)：\n\n"); 
    	for(i=0;i<G->arcnum;i++)
    	{
           //输入边信息，并确定v1和v2在G中的位置，即顶点在AdjList[]数组中的位置（下标）  
    		printf("输入第%d条边信息：",i+1); 
    		getchar();
    		scanf(" %c %c %d",&v1,&v2,&value);
    		n=LocateVex(G,v1);
    		m=LocateVex(G,v2);
    		
    		if(n==-1||m==-1)
    		 {
        
    		 	printf("NO This Vertex!\n");
    		 	return;
    		 } 
    		
    		p1=(ArcNode *)malloc(sizeof(ArcNode));
    		p1->adjvex=m;//填上坐标 
    		p1->weight=value;
    		p1->next=G->AdjList[n].firstarc;//改链（头插法）  
    		G->AdjList[n].firstarc=p1;
    	}
    
    } 
    void print(ALGraph G)
    {
        
    	int i;
    	ArcNode *p;
    	printf("\n-------------------------------");
    	printf("\n图的邻接表表示：\n");
    	
    	for(i=0;i<G.vexnum;i++)
    	{
        
    		
    		printf("\n   AdjList[%d]%4c",i,G.AdjList[i].vertex);
    		p=G.AdjList[i].firstarc;
    		
    		while(p!=NULL)
    		{
        
    			printf("-->%d权值[%d]",p->adjvex,p->weight);
    			p=p->next;
    		}
    		
    	 } 
    	 printf("\n");
    } 
    
    void InsertVex(ALGraph *G,VertexType v)
    {
        
    	
    }
    int main() 
    {
        
    	ALGraph G;
    	CreateDG(&G);
    	print(G);
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221120/bd7b6b7534154a6f811493758d4c866f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 1]: /images/20221120/0bb50c75e1234e6cafc12fa5c4b0baff.png