精华内容
下载资源
问答
  • c语言实现数据结构中有向图和无向图邻接表的建立、插入、删除操作

    提示:部分内容我设置了隐藏,点赞之后会自动显示
    这次的内容是我们数据结构本周的作业,大概是我做的最辛苦的一次作业
    整体难度感觉还可,只是在删除操作里面我因为指针使用混乱导致改了好久
    不过这次作业的难点也就是在删除操作那里,做完之后感觉收获还挺大的。

    好吧,最让我崩溃的是写这篇文章的时候突然发现我作业的第二个算法题做错了555555555555555555555555555555555555
    所以我会在文章的末尾附上无向图邻接表的同样操作供大家参考

    在这里插入图片描述

    题目如下:

    在这里插入图片描述

    下面是我的代码:

    头文件和宏定义以及结构等内容

    #include<stdio.h>
    #include<stdlib.h>
    #define MAX_VER_TEX 20//定点的最大个数 
    #define VertexType int 
    #define ERROR -1
    #define OK 0
    //typedef enum
    //{	Digraph,//有向图 
    //	Undigraph//无向图 
    //}GraphKind;
    typedef struct ArcNode{//弧结点结构 
    	int adjvex;//本弧指向的结点的位置
    	struct ArcNode *nextarc;//指向下一个弧的指针
    	int weight;//权值 
    }ArcNode;
    
    typedef struct VNode{//定点结构
    	VertexType data; //储存结点的信息 
    	ArcNode* firstarc;//指向第一条弧的指针 
    }VNode,AdjList[MAX_VER_TEX];
    typedef struct{	//图的结构
    	AdjList vertexs;//储存顶点的数组
    	int vexnum;//顶点个数 
    	int arcnum;//边的个数
    	//GraphKind kind;//图的种类  
    }ALGraph;
    

    函数部分

    int Locate(ALGraph g,VertexType elem)//定位这个结点在数组中的位置
    {	int i;
    	for(i=0;i<g.vexnum;i++)
    	{	if(elem==g.vertexs[i].data)
    		return i; 
    	}
    	return ERROR;//找不到对应元素,返回-1表示不存在 
    }
    int CreateAlgraph(ALGraph *g)//输入图结构,图的顶点个数,边个数
    {	
    	int i;
    	int a,b,c,pa,pb;
    	ArcNode* p;
    	printf("输入图的有关信息,\n输入格式:图顶点个数+空格+边个数\n");
    	scanf("%d %d",&(g->vexnum),&(g->arcnum));
    	printf("下面请输入第一个顶点信息:");
    	for(i=0;i<g->vexnum;i++)
    	{	scanf("%d",&g->vertexs[i].data);
    		g->vertexs[i].firstarc=NULL;
    		if(i!=g->vexnum-1)
    		{	printf("请输入下一个结点的信息:");
    		}
    	}
    	printf("下面输入第一条边的信息,\n输入格式:起点的信息+空格+终点的信息+权值\n");
    	for(i=0;i<g->arcnum;i++)
    	{	scanf("%d %d %d",&a,&b,&c);
    		pa=Locate(*g,a);//起点在数组里的位置 
    		pb=Locate(*g,b);//终点在数组里的位置
    		if(pa<0||pb<0)
    		{	printf("这个边并不存在,请重新输入\n");
    			i--;
    			continue; 
    		}
    		p=(ArcNode*)malloc(sizeof(ArcNode));
    		p->adjvex=pb;
    		p->weight=c;
    		//下面把这个边信息插到起点的弧信息的第一个 
    		p->nextarc=g->vertexs[pa].firstarc;
    		g->vertexs[pa].firstarc=p;
    		if(i!=g->arcnum-1)
    		printf("请输入下一条边的信息:"); 
    		
    	}
    } 
    void PrintOutAlgraph(ALGraph g)
    {	int i,j=1;
    	ArcNode *p;
    	printf("\n*---------分割线---------*\n");
    	printf("这个图共有%d个顶点%d条边:\n",g.vexnum,g.arcnum); 
    	printf("这个图的顶点信息:\n");
    	for(i=0;i<g.vexnum;i++)
    	{	printf("该图结构的第%d个顶点的信息是%d\n",i+1,g.vertexs[i].data);
    	}
    	printf("这个图的边信息:\n");
    	for(i=0;i<g.vexnum;i++)
    	{	p=g.vertexs[i].firstarc;
    		while(p)
    		{	printf("第%d条边:(%d ,%d) 权值为:%d\n",j,g.vertexs[i].data,g.vertexs[p->adjvex].data,p->weight);
    			j++;
    			p=p->nextarc;
    		}
    	 }
    	printf("*---------分割线---------*\n");  
    }
    //插入一个顶点,返回顶点在图数组里的位置,如果该顶点已经存在,或者数组已满返回-1; 
    int InsertArc(ALGraph *g,int a,int b,int aweight)
    {	int pa,pb;
    	ArcNode*p;
    		pa=Locate(*g,a);//起点在数组里的位置 
    		pb=Locate(*g,b);//终点在数组里的位置
    		if(pa<0||pb<0)
    		{	printf("这个边并不存在,请重新输入\n");
    			return ERROR;
    		}
    		p=(ArcNode*)malloc(sizeof(ArcNode));
    		p->adjvex=pb;
    		p->weight=aweight;
    		//下面把这个边信息插到起点的弧信息的第一个 
    		p->nextarc=g->vertexs[pa].firstarc;
    		g->vertexs[pa].firstarc=p;
    		g->arcnum++;//边个数增加 
    		return OK;
    }
    int DeleteArc(ALGraph *g,int a,int b)
    {	int pa,pb;
    	ArcNode *p,*temp;
    	pa=Locate(*g,a);//起点在数组里的位置 
    	pb=Locate(*g,b);//终点在数组里的位置
    	if(pa<0||pb<0)
    		return ERROR;
    	p=g->vertexs[pa].firstarc;
    	if(p->adjvex==pb)//p为头结点的情况 
    		 {	temp=p;
    		 	free(temp);
    		 	g->vertexs[pa].firstarc=p->nextarc;
    		 }
    
    	while(p->nextarc!=NULL)
    		{	if(p->nextarc->adjvex==pb)
    			{	temp=p->nextarc;
    				p->nextarc=temp->nextarc;	
    				free(temp);
    				break;
    			}			
    			p=p->nextarc;
    		}
    	g->arcnum--;//边个数减一 
    	return OK;
    		 
     } 
    int InsertVex(ALGraph *g,int adata)
    {	int i;
    	if(g->vexnum==MAX_VER_TEX)
    	return ERROR;
    	for(i=0;i<g->vexnum;i++)
    	{	if(adata==g->vertexs[i].data)
    		return ERROR;
    	}
    	g->vertexs[g->vexnum].data=adata;
    	g->vertexs[g->vexnum].firstarc=NULL;
    	g->vexnum++;//顶点个数增加 
    	return g->vexnum-1;
    }
    int Delete(ArcNode *p)//删除顶点的辅助函数:递归调用删除弧结点内容 
    {	if(p)
    	{
    		Delete(p->nextarc);
    		free(p);
    		return OK;
    	}
    	else 
    		return NULL;
    }
    int DeleteVex(ALGraph *g,VertexType adata)
    {	int qq=0;
    	ArcNode *p,*del,*pre;
    	int pdata=Locate(*g,adata);//定位结点位置 
    	if(pdata<0)//结点不存在,返回错误信息 
    	return ERROR;
    	//Delete(g->vertexs[pdata].firstarc);//删除这个结点储存的弧信息
    	p=g->vertexs[pdata].firstarc;
    	while(p)
    	{	g->arcnum--;
    		p=p->nextarc;
    	 } 
    	int i;
    	for(i=pdata;i<g->vexnum-1;i++)//数组内容移位 
    	{	g->vertexs[i].data=g->vertexs[i+1].data;
    		g->vertexs[i].firstarc=g->vertexs[i+1].firstarc;//顶点信息和第一条弧的指针都移位 
    	}
    	g->vertexs[g->vexnum-1].data=-1;
    	g->vertexs[g->vexnum-1].firstarc=NULL;
    	g->vexnum--;//顶点个数减1 
    	for(i=0;i<g->vexnum;i++)
    	{	p=g->vertexs[i].firstarc;
    		while(p)
    		{	if(p->adjvex==pdata)
    			{	
    				if(p==g->vertexs[i].firstarc)
    				{	del=p;
    					p=p->nextarc;
    					g->vertexs[i].firstarc=p;
    					pre=NULL;
    					free(del);
    					g->arcnum--;
    					break;
    				}
    				else
    				{	del=p;
    					p=p->nextarc;
    					pre->nextarc=p;
    					free(del);
    					g->arcnum--;
    					break;
    				}
    			}
    			else if(p->adjvex>pdata)
    			{	p->adjvex--;
    			}
    			pre=p;
    			p=p->nextarc;
    		}
    		
    	}
    	return OK; 
    }
    

    测试函数:

    int main()
    {	ALGraph test;
    	CreateAlgraph(&test);
    	PrintOutAlgraph(test);
    	InsertArc(&test,11,33,9);
    	InsertVex(&test,44);
    	printf("插入后:\n");
    	PrintOutAlgraph(test);
    	DeleteVex(&test,33);
    	//DeleteArc(&test,11,22);
    	printf("删除后:\n");
    	PrintOutAlgraph(test);
    }
    

    输入及输出结果:

    输入图的有关信息,
    输入格式:图顶点个数+空格+边个数
    3 3
    下面请输入第一个顶点信息:11
    请输入下一个结点的信息:22
    请输入下一个结点的信息:33
    下面输入第一条边的信息,
    输入格式:起点的信息+空格+终点的信息+权值
    11 22 5
    请输入下一条边的信息:22 33 6
    请输入下一条边的信息:33 11 7

    ---------分割线---------
    这个图共有3个顶点3条边:
    这个图的顶点信息:
    该图结构的第1个顶点的信息是11
    该图结构的第2个顶点的信息是22
    该图结构的第3个顶点的信息是33
    这个图的边信息:
    第1条边:(11 ,22) 权值为:5
    第2条边:(22 ,33) 权值为:6
    第3条边:(33 ,11) 权值为:7
    ---------分割线---------
    插入后:

    ---------分割线---------
    这个图共有4个顶点4条边:
    这个图的顶点信息:
    该图结构的第1个顶点的信息是11
    该图结构的第2个顶点的信息是22
    该图结构的第3个顶点的信息是33
    该图结构的第4个顶点的信息是44
    这个图的边信息:
    第1条边:(11 ,33) 权值为:9
    第2条边:(11 ,22) 权值为:5
    第3条边:(22 ,33) 权值为:6
    第4条边:(33 ,11) 权值为:7
    ---------分割线---------
    删除后:

    ---------分割线---------
    这个图共有3个顶点1条边:
    这个图的顶点信息:
    该图结构的第1个顶点的信息是11
    该图结构的第2个顶点的信息是22
    该图结构的第3个顶点的信息是44
    这个图的边信息:
    第1条边:(11 ,22) 权值为:5
    ---------分割线---------


    Process exited after 11.89 seconds with return value 0
    请按任意键继续. . .

    关键问题就是在数组移位后,弧域里的位置并没有改变,需要在删除之后将其改变才能正常输出

    无向图邻接表操作

    #include<stdio.h>
    #include<stdlib.h>
    #define MAX_VER_TEX 20//定点的最大个数 
    #define VertexType int 
    #define ERROR -1
    #define OK 0
    //typedef enum
    //{	Digraph,//有向图 
    //	Undigraph//无向图 
    //}GraphKind;
    typedef struct ArcNode{//弧结点结构 
    	int adjvex;//本弧指向的结点的位置
    	struct ArcNode *nextarc;//指向下一个弧的指针
    	int weight;//权值 
    }ArcNode;
    typedef struct VNode{//定点结构
    	VertexType data; //储存结点的信息 
    	ArcNode* firstarc;//指向第一条弧的指针 
    }VNode,AdjList[MAX_VER_TEX];
    typedef struct{	//图的结构
    	AdjList vertexs;//储存顶点的数组
    	int vexnum;//顶点个数 
    	int arcnum;//边的个数
    	//GraphKind kind;//图的种类  
    }UnGraph;
    int Locate(UnGraph g,VertexType elem)//定位这个结点在数组中的位置
    {	int i;
    	for(i=0;i<g.vexnum;i++)
    	{	if(elem==g.vertexs[i].data)
    		return i; 
    	}
    	return ERROR;//找不到对应元素,返回-1表示不存在 
    }
    int CreateUnGraph(UnGraph *g)//输入图结构,图的顶点个数,边个数
    {	
    	int i;
    	int a,b,c,pa,pb;
    	ArcNode* p,*p2;
    	printf("输入图的有关信息,\n输入格式:图顶点个数+空格+边个数\n");
    	scanf("%d %d",&(g->vexnum),&(g->arcnum));
    	printf("下面请输入第一个顶点信息:");
    	for(i=0;i<g->vexnum;i++)
    	{	scanf("%d",&g->vertexs[i].data);
    		g->vertexs[i].firstarc=NULL;
    		if(i!=g->vexnum-1)
    		{	printf("请输入下一个结点的信息:");
    		}
    	}
    	printf("下面输入第一条边的信息,\n输入格式:起点的信息+空格+终点的信息+权值\n");
    	for(i=0;i<g->arcnum;i++)
    	{	scanf("%d %d %d",&a,&b,&c);
    		pa=Locate(*g,a);//起点在数组里的位置 
    		pb=Locate(*g,b);//终点在数组里的位置
    		if(pa<0||pb<0)
    		{	printf("这个边并不存在,请重新输入\n");
    			i--;
    			continue; 
    		}
    		p=(ArcNode*)malloc(sizeof(ArcNode));
    		p->adjvex=pb;
    		p->weight=c;
    		//下面把这个边信息插到起点的弧信息的第一个 
    		p->nextarc=g->vertexs[pa].firstarc;
    		g->vertexs[pa].firstarc=p;
    		//在另一个结点的弧域中插入 
    		p2=(ArcNode*)malloc(sizeof(ArcNode));
    		p2->adjvex=pa;
    		p2->weight=c;
    		//下面把这个边信息插到起点的弧信息的第一个 
    		p2->nextarc=g->vertexs[pb].firstarc;
    		g->vertexs[pb].firstarc=p2;
    		if(i!=g->arcnum-1)
    		printf("请输入下一条边的信息:"); 
    		
    	}
    } 
    void PrintOutUnGraph(UnGraph g)
    {	int i,j=1;
    	ArcNode *p;
    	printf("\n*---------分割线---------*\n");
    	printf("这个图共有%d个顶点%d条边:\n",g.vexnum,g.arcnum); 
    	printf("这个图的顶点信息:\n");
    	for(i=0;i<g.vexnum;i++)
    	{	printf("该图结构的第%d个顶点的信息是%d\n",i+1,g.vertexs[i].data);
    	}
    	printf("这个图的边信息:\n");
    	for(i=0;i<g.vexnum;i++)
    	{	p=g.vertexs[i].firstarc;
    		while(p)
    		{	if(i<p->adjvex)
    			{
    				printf("第%d条边:(%d ,%d) 权值为:%d\n",j,g.vertexs[i].data,g.vertexs[p->adjvex].data,p->weight);
    				j++;
    			}
    			p=p->nextarc;
    		}
    	 }
    	printf("*---------分割线---------*\n");  
    }
    int InsertArc(UnGraph *g,int a,int b,int aweight)
    {	int pa,pb;
    	ArcNode*p,*p2;
    		pa=Locate(*g,a);//起点在数组里的位置 
    		pb=Locate(*g,b);//终点在数组里的位置
    		if(pa<0||pb<0)
    		{	printf("这个边并不存在,请重新输入\n");
    			return ERROR;
    		}
    		p=(ArcNode*)malloc(sizeof(ArcNode));
    		p->adjvex=pb;
    		p->weight=aweight;
    		//下面把这个边信息插到起点的弧信息的第一个 
    		p->nextarc=g->vertexs[pa].firstarc;
    		g->vertexs[pa].firstarc=p;
    		//在另一个结点的弧域中插入 
    		p2=(ArcNode*)malloc(sizeof(ArcNode));
    		p2->adjvex=pa;
    		p2->weight=aweight;
    		//下面把这个边信息插到起点的弧信息的第一个 
    		p2->nextarc=g->vertexs[pb].firstarc;
    		g->vertexs[pb].firstarc=p2;
    		
    		g->arcnum++;//边个数增加 
    		return OK;
    }
    int DeleteArc(UnGraph *g,int a,int b)
    {	int pa,pb;
    	ArcNode *p,*temp,*p2;
    	pa=Locate(*g,a);//起点在数组里的位置 
    	pb=Locate(*g,b);//终点在数组里的位置
    	if(pa<0||pb<0)
    		return ERROR;
    	
    	p=g->vertexs[pa].firstarc;
    	if(p->adjvex==pb)//p为头结点的情况 
    		 {	temp=p;
    		 	free(temp);
    		 	g->vertexs[pa].firstarc=p->nextarc;
    		 	
    		 	
    		 }
    	if(p->nextarc->adjvex==pb)
    	{	temp=p->nextarc;
    		p->nextarc=temp->nextarc;	
    		free(temp);
    	}
    	//从另一个结点删除 
    		p2=g->vertexs[pb].firstarc;
    	if(p2->adjvex==pa)//p为头结点的情况 
    		 {	temp=p2;
    		 	free(temp);
    		 	g->vertexs[pb].firstarc=p2->nextarc;
    		 }
    	if(p2->nextarc->adjvex==pa)
    	{	temp=p2->nextarc;
    		p2->nextarc=temp->nextarc;	
    		free(temp);
    	}
    	g->arcnum--;//边个数减一 
    	return OK;
    		 
     } 
    //插入一个顶点,返回顶点在图数组里的位置,如果该顶点已经存在,或者数组已满返回-1; 
    int InsertVex(UnGraph *g,int adata)
    {	int i;
    	if(g->vexnum==MAX_VER_TEX)
    	return ERROR;
    	for(i=0;i<g->vexnum;i++)
    	{	if(adata==g->vertexs[i].data)
    		return ERROR;
    	}
    	g->vertexs[g->vexnum].data=adata;
    	g->vertexs[g->vexnum].firstarc=NULL;
    	g->vexnum++;//顶点个数增加 
    	return g->vexnum-1;
    }
    int Delete(ArcNode *p)//删除顶点的辅助函数:递归调用删除弧结点内容 
    {	if(p)
    	{
    		Delete(p->nextarc);
    		free(p);
    		return OK;
    	}
    	else 
    		return NULL;
    }
    int DeleteVex(UnGraph *g,VertexType adata)
    {	int qq=0;
    	ArcNode *p,*del,*pre;
    	int pdata=Locate(*g,adata);//定位结点位置 
    	if(pdata<0)//结点不存在,返回错误信息 
    	return ERROR;
    	//Delete(g->vertexs[pdata].firstarc);//删除这个结点储存的弧信息
    	p=g->vertexs[pdata].firstarc;
    	while(p)
    	{	g->arcnum--;
    		p=p->nextarc;
    	 } 
    	int i;
    	for(i=pdata;i<g->vexnum-1;i++)//数组内容移位 
    	{	g->vertexs[i].data=g->vertexs[i+1].data;
    		g->vertexs[i].firstarc=g->vertexs[i+1].firstarc;//顶点信息和第一条弧的指针都移位 
    	}
    	g->vertexs[g->vexnum-1].data=-1;
    	g->vertexs[g->vexnum-1].firstarc=NULL;
    	g->vexnum--;//顶点个数减1 
    	for(i=0;i<g->vexnum;i++)
    	{	p=g->vertexs[i].firstarc;
    		while(p)
    		{	if(p->adjvex==pdata)
    			{	
    				if(p==g->vertexs[i].firstarc)
    				{	del=p;
    					p=p->nextarc;
    					g->vertexs[i].firstarc=p;
    					pre=NULL;
    					free(del);
    					g->arcnum--;
    					break;
    				}
    				else
    				{	del=p;
    					p=p->nextarc;
    					pre->nextarc=p;
    					free(del);
    					g->arcnum--;
    					break;
    				}
    			}
    			else if(p->adjvex>pdata)
    			{	p->adjvex--;
    			}
    			pre=p;
    			p=p->nextarc;
    		}
    		
    	}
    	return OK; 
    }
    
    
    
    int main()
    {	UnGraph test;
    	CreateUnGraph(&test);
    	PrintOutUnGraph(test);
    	InsertVex(&test,44);
    	InsertArc(&test,11,44,9);
    	printf("插入后:\n");
    	PrintOutUnGraph(test);
    	DeleteVex(&test,33);
    	//DeleteArc(&test,11,33);
    	printf("删除后:\n");
    	PrintOutUnGraph(test);
    }
    
    展开全文
  • 编写程序,输入图的类型(0:无向图,1:有向图)、图中顶点数、边数、边的偶对,建立图的邻接表。如果是无向图,计算并输出每个顶点的度;如果是有向图,计算并输出每个顶点的的入度和出度。 Input 输入: 图的...

    Description

    图采用邻接表为存储结构,图中的顶点数为n(0<n<=20),n个顶点的信息依次为 0,1,...,n-1。

    编写程序,输入图的类型(0:无向图,1:有向图)、图中顶点数、边数、边的偶对,建立图的邻接表。如果是无向图,计算并输出每个顶点的度;如果是有向图,计算并输出每个顶点的的入度和出度。

    Input

    输入:

    图的类型(0 或1)

    顶点数,边数

    顶点偶对 (每行一个偶对,如 vi,vj   表示一条边或者弧)

    Output

    输出:

    无向图则依次输出每个顶点的度,以空格分隔。

    有向图则依次输出每个顶点的入度,以空格分隔。

    换行依次输出每个顶点的出度,以空格分隔。

    Sample Input

    1
    4,4
    0,1
    0,2
    2,3
    3,0

    Sample Output

    1 1 1 1
    2 0 1 1

    根据题目的要求,我们先画出样例的图形如下

     代码和注释如下,首先创建结构体

    #include <stdio.h>
    #include <stdlib.h>
    #define Max_Vertex_Num 100
    typedef struct ArcNode{
        int adjvex; //此题用不到
        struct ArcNode *nextarc;//下一个节点
        int weight;//权重-此题用不到
    }ArcNode;
    /*表头节点*/
    typedef struct VNode{
        int vertex;//表头数组的数据
        ArcNode *firstarc;//表头数组的表头节点域
    }VNode; 
    
    typedef VNode Adjlist[Max_Vertex_Num];//VNode构成的表头节点数组
    
    /*整个邻接表*/
    typedef struct{
        Adjlist adjlist;//每个定点后面的链表,记录关联点
        int vexnum,arcnum;//顶点数和边数
    }ALGraph;

    主函数的结构如下,先输入图的类型(gType)

    int main()
    {
        ALGraph G;
        int gType;//定义类型 0是无向图,1是有向图
        scanf("%d",&gType);
        CreateALGraph(&G,gType);
        
        if(gType==0)
            CountOutDegree(&G);//计算出度等同于计算所有度数
        else{
            CountInDegree(&G);//计算入度
            CountOutDegree(&G);//计算出度
        }
        return 0;
    }

    有了主函数的大致结构,应该知道先创建一个图吧,我们需要两个函数LocateVex获取输入的向量对是在函数的哪一行

    然后根据输入的图的类型分类创建图

    int LocateVex(ALGraph *G,int u){
        int i;
        for(i = 0; i<G->vexnum;++i)
        {
            if(G->adjlist[i].vertex == u)
            {
                return i;
            }
        }
        return -1;
    }
    /*创建图*/
    void CreateALGraph(ALGraph *G,int gType)
    {
        ArcNode *p;
        int i,j,k;
        int v1,v2;
    
        scanf("%d,%d",&G->vexnum,&G->arcnum); //输入顶点数和边数
    
        if(gType==0)
        {
            for(k=0;k<G->vexnum;k++)
            {
                G->adjlist[k].vertex = k;
                G->adjlist[k].firstarc = NULL;
            }
            k = 0;
            while(k<G->arcnum){
                scanf("%d,%d",&v1,&v2);
                k++;
                i = LocateVex(G,v1);
                j = LocateVex(G,v2);
                /*给第i的表头添加数据是j的节点*/
                p=(ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
                /*给第j的表头添加数据是i的节点*/
                p=(ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = i;
                p->nextarc = G->adjlist[j].firstarc;
                G->adjlist[j].firstarc = p;
            }
        }else{
             for(k=0;k<G->vexnum;k++)
            {
                G->adjlist[k].vertex = k;
                G->adjlist[k].firstarc = NULL;
            }
            k = 0;
            while(k<G->arcnum){
                scanf("%d,%d",&v1,&v2);
                k++;
                i = LocateVex(G,v1);
                j = LocateVex(G,v2);
                /*给第i的表头添加数据是j的节点——有向图,不需要给j添加i数据的节点了*/
                p=(ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex = j;
                p->nextarc = G->adjlist[i].firstarc;
                G->adjlist[i].firstarc = p;
            }
        }
    }

    怎么求出度和入度呢?代码如下!

    /*计算出度*/
    void CountOutDegree(ALGraph *G){
        int i,j,k;
        int count1 = 0;
        ArcNode *p;
        //根据无向图的结构,表体中有几个节点,就有几度
        for(i=0;i<G->vexnum;i++)
        {
            int degree = 0;
            p = G->adjlist[i].firstarc;
            while(p!=NULL)
            {
                degree++;
                p=p->nextarc;
            }
            
            
            /*操蛋的输出格式!*/
            if(i!=G->vexnum-1)
                printf("%d ",degree);
            else
                printf("%d",degree);
                
        }
    }
    /*计算入度*/
    void CountInDegree(ALGraph *G)
    {
        ArcNode *p;
        int i;
        int j;
        //数组存放每个顶点的入度数量,赋初始值都为0
        int arr[G->vexnum];
        for(i=0;i<G->vexnum;i++)
        {
            arr[i]=0;
        }
        for(i = 0;i<G->vexnum;i++)
        {
            p = G->adjlist[i].firstarc;
            while(p!=NULL)
            {
                //根据有向图的结构
                //表头节点后面连接的表体的数据p->adjvex,出现一次就是作为入度一次
                //比如0后面有1,2,那么顶点1和2肯定都作为后驱一次,就有一个入度
                arr[p->adjvex]++;
                //指针移动到下一个表体
                p=p->nextarc;
            }
    
        }
        
        
        /*操蛋的输出格式!*/
        for(i=0;i<G->vexnum;i++){
            if(i!=G->vexnum-1)
                printf("%d ",arr[i]);
            else
                printf("%d",arr[i]);
        }
    
        printf("\n");
    }

     

    总结:其实这个题目对图的操作还是很简单的,主要是理解了图的邻接表的表示方法其实就是数组+链表的组成结构,剩下的无非就是对单链表的操作而已。

     

    展开全文
  • 1 /*C语言建立有向图邻接表及其遍历操作*/2 #include"stdio.h"3 #include"stdlib.h"4 //图的邻接矩阵储存结构5 typedef charelemtype;6 #define maxsize 107 #define queuesize 1008 //边结点的类型定义9 typedef ...

    1 /*C语言建立有向图的邻接表及其遍历操作*/

    2 #include"stdio.h"

    3 #include"stdlib.h"

    4 //图的邻接矩阵储存结构

    5 typedef charelemtype;6 #define maxsize 10

    7 #define queuesize 100

    8 //边结点的类型定义

    9 typedef structedgenode10 {11 int adjvex;//存放邻接的点在顶点表的下标,邻接点

    12 struct edgenode *next;//指向Vi下一个邻接点的边结点

    13 int weight;/*权值*/

    14 }edgenode;15 //顶点结点类型定义

    16 typedef structvexnode17 {18 elemtype data; //存储顶点的名称或其相关信息

    19 edgenode *firstedge;//边表头指针

    20 }vexnode;21 //图的邻接表数据类型

    22 typedef struct{23 vexnode vexlist[maxsize];//顶点表

    24 intn,e;25 }graph;26 //在图g中查找顶点v,存在顶点数组中的下标,不存在返回-1

    27 intlocatevex(graph g,elemtype v)28 {29 inti;30 for(i=0;i

    35 voidprint(graph g)36 {37 inti;38 edgenode *p;39 printf("图的邻接表表示:");40 for(i=0;i%d",p->adjvex);p=p->next;45 }46 }47 printf("\n");48 }49 void creategraph(graph *g){50 inti,j,k;51 elemtype v1,v2;52 edgenode *s;53 printf("请输入图的顶点数及边数\n");54 printf("顶点数 n=");scanf("%d",&g->n);55 printf("边 数 e=");scanf("%d",&g->e);56 printf("请输入图的顶点信息:\n");getchar();57 for(i=0;i<=g->n;i++){58 scanf("%c",&g->vexlist[i].data); //构造顶点信息

    59 g->vexlist[i].firstedge=NULL;60 }61 printf("请输入图的边的信息:\n");62 for(k=0;ke;k++)63 {64 printf("请输入第%d条边的两个端点下标:",k+1);65 scanf("%c%c",&v1,&v2);getchar();//输入一条边的两个顶点

    66 i=locatevex(*g,v1);67 j=locatevex(*g,v2);68 if(i>=0&&j>=0){69 //建立无向图的邻接表

    70 /*s=(edgenode *)malloc(sizeof(edgenode));71 s->adjvex=j;72 s->next=g->vexlist[i].firstedge;73 g->vexlist[i].firstedge=s;74

    75 s=(edgenode *)malloc(sizeof(edgenode));76 s->adjvex=i;77 s->next=g->vexlist[j].firstedge;78 g->vexlist[j].firstedge=s;*/

    79 //建立有向图的邻接表

    80 s=(edgenode *)malloc(sizeof(edgenode));81 s->adjvex=j;82 s->next=g->vexlist[i].firstedge;83 g->vexlist[i].firstedge=s;84 }85 }86 }87 int visited[maxsize];/*访问标志数组*/

    88 /*从第i个顶点出发递归地深度优先遍历图G*/

    89 void DFS(graph g,inti)90 {91 edgenode *p;92 printf("%3c",g.vexlist[i].data);/*访问第i个项点*/

    93 visited[i]=1;94 p=g.vexlist[i].firstedge;95 while(p!=NULL) {96 if(visited[p->adjvex]==0)97 DFS(g,p->adjvex);/*对i的尚未访问的邻接顶点j递归调用DFS*/

    98 p=p->next;99 }100 }101 void DFStraverse(graph g) /*对图G进行深度优先遍历*/

    102 {103 intv;104 for (v=0; v

    105 for (v=0; v

    106 /*从第v个顶点出发递归地深度优先遍历图G*/

    107 if (!visited[v])DFS(g,v);108 }109 //循环队列存储结构定义

    110 typedef structcirqueue111 {112 elemtype *data; //队列存储空间的首地址

    113 int front; //队头位置:指向当前队头元素

    114 int rear; //队尾位置:指向当前队尾元素的下一位置

    115 }cirqueue; //循环队列116 //构造空队,如果成功,返回1,如果失败,返回0

    117 int initqueue(cirqueue *q)118 {119 q->data=(elemtype *)malloc(queuesize*sizeof(cirqueue));120 if (q->data==NULL)return 0; //存储分配失败

    121 q->front=q->rear=0;122 return 1;123 }124 //插入元素e为Q的新的队尾元素 ,如果成功,返回1,如果失败,返回0

    125 int enqueue (cirqueue *q,elemtype e)126 {127 if ((q->rear+1) % queuesize == q->front)128 return 0; //队列满

    129 q->data[q->rear] =e;130 q->rear = (q->rear+1) % queuesize; //队尾后移一位

    131 return 1;132 }133 //若队列不空,则删除Q的队头元素,用e返回其值,并返回1;否则返回0

    134 int dequeue (cirqueue *q,int *e)135 {136 if (q->front == q->rear) return 0; //队列为空

    137 *e = q->data[q->front];138 q->front = (q->front+1) %queuesize; //队头后移一位

    139 return 1;140 }141 //若栈不空,则用e返回队头元素,并返回1;否则返回0

    142 int getfront(cirqueue q,elemtype *e)143 {144 if (q.front == q.rear) return 0; //队列为空

    145 *e=q.data[q.front];146 return 1;147 }148 //若队列为空栈,则返回1,否则返回0

    149 int queueempty(cirqueue q)//栈非空

    150 {151 if(q.front == q.rear)return 1; //队列为空

    152 else return 0;153 }154 //返回队列的元素个数,即队列的长度

    155 intqueuelength(cirqueue q)156 {157 return (q.rear-q.front+queuesize) %queuesize;158 }159 //【算法6-10:利用邻接矩阵实现连通图的广度优先搜索遍历】

    160 intBFSvisited[maxsize];161 cirqueue q;162 /*从第k个顶点出发广度优先遍历图G,G以邻接矩阵表示。*/

    163 void BFS(graph g,intk){164 inti;165 edgenode *p;166 initqueue(&q);/*初始化队列*/

    167 printf("%3c",g.vexlist[k].data);/*访问第k个项点*/

    168 visited[k]=1;169 enqueue(&q,k);/*第k个顶点进队*/

    170 while(queueempty(q)==0) {/*队列非空*/

    171 dequeue(&q,&i);172 p=g.vexlist[i].firstedge;/*获取第1个邻接点*/

    173 while(p!=NULL){174 if(visited[p->adjvex]==0){175 /*访问第i个顶点的末曾访问的顶点*/

    176 printf("%3c",g.vexlist[p->adjvex].data);177 visited[p->adjvex]=1;178 enqueue(&q,p->adjvex);/*第k个顶点进队*/

    179 }180 p=p->next;181 }182 }183 }184 void BFStraverse(graph g) //对图G进行广度优先遍历

    185 {186 intv;187 for (v=0; v

    188 visited[v]=0;189 for (v=0; v

    190 if (!visited[v])BFS(g,v);191 //从第v个顶点出发递归地深度优先遍历图G

    192 }193 intmain()194 {195 graph g;196 creategraph(&g);197 print(g);198 printf("\n");199 printf("图的深度优先遍历序列:\n");200 DFStraverse(g);201 printf("\n");202 printf("图的广度优先遍历序列:\n");203 BFStraverse(g);204 printf("\n");205 return 0;206 }

    展开全文
  • 有向图邻接表实现 初学图的邻接表存储方式,费了很多的时间去理解它。走了很多弯路,终于用代码上实现了这个存储结构,在这里把的感悟和过程做个总结,希望能帮到和我一样的初学者。 对于以下这个图 它的邻接表...

    有向图的邻接表实现

    初学图的邻接表存储方式,费了很多的时间去理解它。走了很多弯路,终于用代码上实现了这个存储结构,在这里把的感悟和过程做个总结,希望能帮到和我一样的初学者。

    对于以下这个图
    在这里插入图片描述
    它的邻接表存储结构我相信大部分的朋友肯定是能够理解的,但是大部分的资料讲解都是在画一个邻接表的结构表示图之后直接上代码,然后对代码进行解释。

    但对与我这样的初学者来说,这个由理论到代码的中间转换过程其实是最难理解的。我看了很多的博文,图的创建差不多都一样用一个函数进行边节点的不断插入。为了更容易理解这个创建的过程我用一个比较麻烦的方法去实现上图中图的存储

    完整代码

    #include<stdio.h>
    #include<stdlib.h>
    #define MAX 10
    int visit[MAX]={0};
    //以下结构体的创建和大部分资料的相同
    typedef struct arcNode{//边节点
        int adjvex;//边指向的顶点编号,从0到4;这个和顶点信息
                  //不一样哦        
       
        struct arcNode *next;//用于指向下一个arcnode节点
    }arcNode;
    typedef struct vNode{/*表头节点,也就是邻接表中每个单链表                       的表头,存储的是每一个顶点*/
    
        char data;/*这个是顶点信息,比如在其他资料中,这个用来
                  表示v0,v1,v2,v3之类的,只是这里举的例子
                 刚好是顶点为0,1,2,3,4*/
        arcNode *firstArc;//就是表头指向的第一个边节点
    }vNode;
    typedef struct graph{
        vNode adjlist[MAX];/*用顺序表来存储每一个表头,从而                         实现图的邻接表存储结构*/
        int e;//图的边数目
        int n;//图的顶点数目
    }graph;
    
    void createGraph(graph *G){//创建一个图
        int i;
        arcNode *arc[G->e] ;//定义e个边节点
        for(i=0;i<G->n;i++){//图的表头节点初始化
            G->adjlist[i].firstArc = NULL;//置空
            G->adjlist[i].data = '0'+i;//图的顶点信息,不是编号哦
        }
        for(i=0;i<G->e;i++){//初始化n个边节点
            arc[i] = (arcNode*)malloc(sizeof(arcNode));
        }
        //接下来开始手动一个搭建一个图
        //第一条链表,以adjlist[0]为表头
        G->adjlist[0].firstArc = arc[0];//arc[0]为表头节点0的第一条边,也就是0->1
        arc[0]->adjvex = 1;
        arc[0]->next =arc[1];//arc[0]边节点指向下一条边节点,也就是0->1->3
        arc[1]->adjvex = 3;
        arc[1]->next = arc[2];//同理0->1->3->4
        arc[2]->adjvex = 4;
        arc[2]->next = NULL;
        //第二条链表,以adjlist[1]为表头
        G->adjlist[1].firstArc = arc[3];//arc[3]成为表头节点1的第一条边,也就是1->
        arc[3]->adjvex = 4;
        arc[3]->next = arc[4];
        arc[4]->adjvex = 2;
        arc[4]->next = NULL;
        //第三条链表,以adjlist[2]为表头
        G->adjlist[2].firstArc = arc[5];
        arc[5]->adjvex = 0;
        arc[5]->next = NULL;
        
        G->adjlist[3].firstArc = arc[6];
        arc[6]->adjvex = 2;
        arc[6]->next = NULL;
        
        G->adjlist[4].firstArc = NULL;
    }
    void DFS(graph *G,int v){//深度遍历
        arcNode *p ;
        if(visit[v]==0){
        visit[v] = 1;//定义了一个int型数组visit来标记每个顶点是否被遍历过
        printf("%c   ",G->adjlist[v].data);//输出顶点
        p = G->adjlist[v].firstArc;//将每个顶点的下一个边节点赋给p节点
        while(p!=NULL){//循环遍历p所指向的下一个边节点
            if(visit[p->adjvex]==0){
                DFS(G,p->adjvex);
            }
            p=p->next;
        }
        }
    }
    int main(){
        graph *G = (graph*)malloc(sizeof(graph));
        G->e=7;//这个图的边有7条边
        G->n=5;//5个顶点
        createGraph(G);
        printf("\n");
        DFS(G, 0);
        return 0;
    }
    
    

    以上是我的愚解,如有不当的地方还望多指正。

    展开全文
  • 本文实例为大家分享了C++实现有向图邻接表的构建代码,供大家参考,具体内容如下数据结构里面的一道基础题,分享下自己的写法,验证可跑。#include#includeconst int MAX = 20;using namespace std;struct ArcNode {...
  • C语言建立有向图邻接表及其遍历操作

    千次阅读 多人点赞 2018-12-29 17:27:32
    C语言建立有向图邻接表及其遍历操作 1 /*C语言建立有向图邻接表及其遍历操作*/ 2 #include"stdio.h" 3 #include"stdlib.h" 4 //图的邻接矩阵储存结构 5 typedef char elemtype; 6 #...
  • 本文主要向大家介绍了C/C++知识点之C语言建立有向图邻接表及其遍历操作,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。1/**/2#include"stdio.h"3#include"stdlib.h"4//图的邻接矩阵储存结构5...
  • c语言写的有向图邻接表的实现,通过使用图的邻接表实现图的存储结构存储。
  • 本章介绍邻接表向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本的实现。实现的语言虽不同,但是原理...
  • c语言实现无向图邻接表储存

    万次阅读 多人点赞 2016-03-02 21:46:51
    一种邻接表储存结构,这里以无向图为例,输入图的参数,构造并输出图的邻接表。 #include #include #define MAX_VERTEX_NUM 100 typedef struct ArcNode{ int adjvex;//该边的另一个顶点的位置 struct ...
  • 邻接表表示法(c语言实现有向网) [ ]为方便理解。 首先先为邻接表画一个模型, 邻接表可以分为两部分(1.表头节点,2.弧节点) 如上,因为写的代码是有向网,所以选择上,首先在脑海里建立一个模型 ...
  • 有向图邻接表遍历 ,有注释,只想赚点分,原作者别介意。
  • ps: 1.部分内容我设置了隐藏,...这次的内容主要难点在删除吧,因为邻接多重的结构,每个结点都两个指针指向他 所以要分别找到这两个结点,让他们的后续指针跳过删除的结点 下面直接上代码吧 #include<stdio...
  • 本章介绍邻接表有向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本的实现。实现的语言虽不同,但是原理...
  • NULL 博文链接:https://touch-2011.iteye.com/blog/1070798
  • 对无向图的每个顶点vi建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对于有向图则是以顶点vi为尾的弧)。这个单链表就称为顶点vi的边(对于有向图则称为出边) 边的头指针和顶点的数据信息采用...
  • 邻接表向图(一)之 C语言详解

    千次阅读 2014-06-01 18:49:47
    邻接表向图(一)之 C语言详解 本章介绍邻接表向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本...
  • 课本里讲的真的弱智,描述一个图好几个...文件1是邻接表建有向图(无权) 文件2是邻接表实现dijstra算法(无权)(注释) #include<stdio.h> #include<malloc.h> typedef struct node { int id...
  • 创建(无)向图,深度优先遍历,广度优先遍历 代码实现: #include<stdio.h> #include<stdlib.h> #include<string.h> #define MaxVertexNum 100 #define MaxSize 10 //顶点数目的最大值 ...
  • 思路及其详细解释看另一篇:关于的第二题 #include<stdio.h> #include<stdlib.h> //定义的结构体 #define MaxVexNum 100 typedef struct ArcNode{//边结点 int data; struct ArcNode *next; }...
  • 运用邻接表建立有向图,并进行深度遍历、广度遍历(c语言) 自认为深度和广度遍历的思路能够帮助大家更好地理解 #include<stdio.h> #include<stdlib.h> #include<malloc.h> #define OK 1 #define...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 140
精华内容 56
关键字:

c语言有向图邻接表

c语言 订阅