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

左手的ㄟ右手 2022-12-29 06:36 174阅读 0赞

![在这里插入图片描述][20201220202516951.png]  
![在这里插入图片描述][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]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70 2]

#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; 
    	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)
    {
        
    	//向邻接表中添加一个新顶点
    		
    		G->AdjList[G->vexnum].vertex=v;
    	
    		G->AdjList[G->vexnum].firstarc=NULL;
    		
    		G->vexnum=G->vexnum+1;
    }
    
    void InsertArc(ALGraph *G,VertexType v,VertexType w)
    {
        
    	//添加一条新边到邻接表 
    	int value;
    	printf("输入这条边的权值：");
    	scanf("%d",&value);
    	ArcNode *p1; 
    		int n,m;
    	n=LocateVex(G,v);
    	m=LocateVex(G,w);
    		
    	p1=(ArcNode *)malloc(sizeof(ArcNode));
    		p1->adjvex=m;//填上坐标 
    		p1->weight=value;
    		p1->next=G->AdjList[n].firstarc;//改链（头插法）  
    		G->AdjList[n].firstarc=p1;
    		
    	G->arcnum++;
     } 
    
    void DeleteArc(ALGraph *G,VertexType v,VertexType w)
    {
        
    	//删除一条指定的边 
    		int n,m;
    	n=LocateVex(G,v);
    	m=LocateVex(G,w);
    		ArcNode *pre,*p;
    		
    		
    	pre=G->AdjList[n].firstarc;
    	p=pre->next;
    	while(p!=NULL)
    	{
        
    		if(pre->next->adjvex==p->adjvex)
    		{
        
    			pre->next=p->next;
    			free(p);
    			break;
    		}
    		p=p->next;
    		pre=pre->next;
    	}
    	G->arcnum--; 
    
    }
    
    void DeleteVex(ALGraph *G,VertexType v)
    {
        
    	int n;
    	n=LocateVex(G,v);
    
    	int arcn=0;
    	ArcNode *p;
    	p=G->AdjList[n].firstarc;
    	while(p!=NULL)
    	{
        
    		p=p->next;
    		arcn++;
    	}
    	
    	
    		G->AdjList[n].firstarc=NULL;
    		
    		
    		
     	for(int i=n;i<G->vexnum-1;i++)
     	{
        
     		G->AdjList[i].firstarc=G->AdjList[i+1].firstarc;
     		G->AdjList[i].vertex=G->AdjList[i+1].vertex;
    	 }
    	 G->vexnum--;
    	 G->arcnum=G->arcnum-arcn;
     } 
    
    void choice(ALGraph *G)
    {
        
    	int i=0;
    	int j=1;
    	VertexType v,w;
    	printf("[1]:添加的新顶点\n");
    	printf("[2]:添加新边的两端结点\n");
    	printf("[3]:删除边的两端结点\n");
    	printf("[4]:删除的顶点(及其相关联的边)\n");
    	printf("[5]:退出\n");
    	while(j)
    	{
        
    		scanf("%d",&i);
    	switch(i)
    	{
        
    		case 1:
    				printf("输入要添加的新顶点：");
    				getchar();
    				scanf("%c",&v); 
    				InsertVex(G,v);
    				print(*G);
    				break;
    				
    		case 2:
    				printf("输入要添加新边的两端结点：");
    				getchar();	
    				scanf("%c %c",&v,&w); 
    				InsertArc(G,v, w);
    				print(*G);
    				break;
    		case 3:
    				printf("输入要删除边的两端结点：");
    				getchar();
    				scanf("%c %c",&v,&w); 
    				DeleteArc(G,v, w);
    				print(*G);
    				break;
    		case 4:
    				printf("输入要删除的顶点(及其相关联的边)：");
    				getchar();
    				scanf("%c",&v); 
    				DeleteVex(G,v);
    				print(*G);
    				break;
    		case 5:
    				j=0;
    				break;
    	
    	}	
    	}
    	
    	
    	
     } 
    int main() 
    {
        
    	ALGraph G;
    	CreateDG(&G);
    	print(G);
    	
    
    	
    
    	choice(&G);
    
    	
    	
    	
    	
    	
    	return 0;
    }

[20201220202516951.png]: /images/20221120/c6055d4ea33f4d6894e0a143e4bf3cb4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201220202751352.png?x-oss-process=image/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]: https://img-blog.csdnimg.cn/20201220202756558.png?x-oss-process=image/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 2]: https://img-blog.csdnimg.cn/20201220202800289.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70