精华内容
下载资源
问答
  • c语言写的有向图邻接表的实现,通过使用图的邻接表实现图的存储结构存储。
  • 本文实例为大家分享了C++实现有向图邻接表的构建代码,供大家参考,具体内容如下数据结构里面的一道基础题,分享下自己的写法,验证可跑。#include#includeconst int MAX = 20;using namespace std;struct ArcNode {...

    本文实例为大家分享了C++实现有向图邻接表的构建代码,供大家参考,具体内容如下

    数据结构里面的一道基础题,分享下自己的写法,验证可跑。

    #include

    #include

    const int MAX = 20;

    using namespace std;

    struct ArcNode { //弧结点

    int adjvex = -1; //所指顶点位置

    ArcNode *nextarc = nullptr; //下一条狐指针

    size_t info = 0; //弧信息

    };

    struct VNode { //顶点

    string data = "0";

    ArcNode *firstarc = nullptr; //第一条依附该顶点的弧的指针

    };

    struct Graph { //图结构

    VNode vertices[MAX]; //全部顶点

    int vexnum, arcnum; //顶点数和弧数

    Graph(int m, int n) :vexnum(m), arcnum(n) {};

    Graph() :vexnum(0), arcnum(0) {};

    };

    int main()

    {

    int vnum, anum, tempanum = 0;

    cout << "输入顶点数:";

    cin >> vnum;

    cout << "输入弧数:";

    cin >> anum;

    cout << "\n\n";

    Graph G(vnum, anum);

    for (int i = 0; i != vnum; ++i) {

    cout << "输入结点" << i << "的信息:";

    cin >> G.vertices[i].data;

    if (tempanum != anum)

    cout << "输入依靠此结点的弧的信息(输入-1以停止):\n";

    else

    cout << "已输入所有弧的信息!\n";

    bool first = true;

    ArcNode *p, *temp;

    for (int j = 0; (j != anum) && (tempanum != vnum); ++j) {

    int pointto;

    cout << "输入弧" << tempanum << "所指向的顶点位置:";

    cin >> pointto;

    if (pointto == -1) break;

    else {

    ++tempanum;

    if (first == true) {

    first = false;

    G.vertices[i].firstarc = new ArcNode;

    G.vertices[i].firstarc->adjvex = pointto;

    p = G.vertices[i].firstarc;

    }

    else {

    temp = new ArcNode;

    temp->adjvex = pointto;

    p->nextarc = temp;

    p = temp;

    }

    }

    }

    cout << endl;

    }

    for (int i = 0; i != anum; ++i) {

    cout << "顶点" << i << ": |" << G.vertices[i].data << "|";

    if (G.vertices[i].firstarc) {

    cout << " -> " << G.vertices[i].firstarc->adjvex;

    auto pt = G.vertices[i].firstarc->nextarc;

    while (pt) {

    cout << " -> " << pt->adjvex;

    pt = pt->nextarc;

    }

    cout << "-> ^";

    }

    else

    cout << " -> ^";

    cout << endl;

    }

    return 0;

    }

    由于只是单纯构建基本的无权值有向图邻接表,里面的弧结构中弧信息未利用到。

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

    本文标题: C++实现有向图邻接表的构建

    本文地址: http://www.cppcns.com/ruanjian/c/310269.html

    展开全文
  • 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);
    }
    
    展开全文
  • 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 }

    展开全文
  • 有向图邻接表遍历 ,有注释,只想赚点分,原作者别介意。
  • 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语言建立有向图的邻接表及其遍历操作

    1 /*C语言建立有向图的邻接表及其遍历操作*/
      2 #include"stdio.h"
      3 #include"stdlib.h"
      4 //图的邻接矩阵储存结构
      5 typedef char elemtype;
      6 #define maxsize 10
      7 #define queuesize 100
      8 //边结点的类型定义
      9 typedef struct edgenode
     10 {
     11     int adjvex;//存放邻接的点在顶点表的下标,邻接点
     12     struct edgenode *next;//指向Vi下一个邻接点的边结点
     13     int weight;/*权值*/
     14 }edgenode;
     15 //顶点结点类型定义
     16 typedef struct vexnode
     17 {
     18     elemtype data; //存储顶点的名称或其相关信息
     19     edgenode *firstedge;//边表头指针
     20 }vexnode;
     21 //图的邻接表数据类型
     22 typedef struct{
     23     vexnode vexlist[maxsize];//顶点表
     24     int n,e;
     25 }graph;
     26 //在图g中查找顶点v,存在顶点数组中的下标,不存在返回-1
     27 int locatevex(graph g,elemtype v)
     28 {
     29     int i;
     30     for(i=0;i<g.n;i++)
     31         if(g.vexlist[i].data==v)return i;
     32     return -1;
     33 }
     34 //打印图信息
     35 void print(graph g)
     36 {
     37     int i;
     38     edgenode *p;
     39     printf("图的邻接表表示:");
     40     for(i=0;i<g.n;i++){
     41         printf("\n%4c",g.vexlist[i].data);
     42         p=g.vexlist[i].firstedge;
     43         while(p!=NULL){
     44             printf("-->%d",p->adjvex);p=p->next;
     45         }
     46     }
     47     printf("\n");
     48 }
     49 void creategraph(graph *g){
     50     int i,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;k<g->e;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,int i)
     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     int v;
    104     for (v=0; v<g.n;v++)visited[v]=0; /*初始化标志数组*/
    105     for  (v=0; v<g.n;v++) /*保证非连通图的遍历*/
    106 /*从第v个顶点出发递归地深度优先遍历图G*/
    107         if (!visited[v])DFS(g,v);        
    108 }
    109 //循环队列存储结构定义
    110 typedef struct  cirqueue
    111 {
    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 int queuelength(cirqueue q)
    156 { 
    157     return (q.rear-q.front+queuesize) % queuesize;
    158 }
    159 //【算法6-10:利用邻接矩阵实现连通图的广度优先搜索遍历】
    160 int BFSvisited[maxsize];
    161 cirqueue q;
    162 /*从第k个顶点出发广度优先遍历图G,G以邻接矩阵表示。*/
    163 void BFS(graph g,int k){
    164     int i;
    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     int v;
    187     for (v=0; v<g.n;v++) //初始化标志数组
    188         visited[v]=0; 
    189     for  (v=0; v<g.n;v++) //保证非连通图的遍历
    190         if (!visited[v])BFS(g,v); 
    191        //从第v个顶点出发递归地深度优先遍历图G
    192 }
    193 int main()
    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 }
    

    程序运行截图:

    程序运行截图

    展开全文
  • 本文主要向大家介绍了C/C++知识点之C语言建立有向图邻接表及其遍历操作,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。1/**/2#include"stdio.h"3#include"stdlib.h"4//图的邻接矩阵储存结构5...
  • 本章介绍邻接表向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本的实现。实现的语言虽不同,但是原理...
  • 邻接表表示法(c语言实现有向网) [ ]为方便理解。 首先先为邻接表画一个模型, 邻接表可以分为两部分(1.表头节点,2.弧节点) 如上,因为写的代码是有向网,所以选择上,首先在脑海里建立一个模型 ...
  • 本章介绍邻接表有向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本的实现。实现的语言虽不同,但是原理...
  • c语言实现无向图邻接表储存

    万次阅读 多人点赞 2016-03-02 21:46:51
    一种邻接表储存结构,这里以无向图为例,输入图的参数,构造并输出图的邻接表。 #include #include #define MAX_VERTEX_NUM 100 typedef struct ArcNode{ int adjvex;//该边的另一个顶点的位置 struct ...
  • 编写程序,输入图的类型(0:无向图,1:有向图)、图中顶点数、边数、边的偶对,建立图的邻接表。如果是无向图,计算并输出每个顶点的度;如果是有向图,计算并输出每个顶点的的入度和出度。 Input 输入: 图的...
  • NULL 博文链接:https://touch-2011.iteye.com/blog/1070798
  • 本章介绍邻接表向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本的实现。实现的语言虽不同,但是原理...
  • 对无向图的每个顶点vi建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对于有向图则是以顶点vi为尾的弧)。这个单链表就称为顶点vi的边(对于有向图则称为出边) 边的头指针和顶点的数据信息采用...
  • 将无向图的邻接矩阵存储转换为对应的邻接表存储 思路:遍历邻接矩阵,将各个顶点关联的边所对应的顶点存储到邻接表所对应的顶点表的边表上,并连接起来。 #include<stdio.h> #include<stdlib.h> #...
  • 有向图:在有向图中,顶点对<V,W>是有序的,表示它从V到W的一条有向边。所以,<W,V>表示的和<V,W>不同的边,顶点的指向不同。有向图中顶点对用尖括号表示<>,<x,y>
  • 图中每个顶点Vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点vi的边表,有向图则称为顶点vi作为弧尾的出边表。 如图1-1就是一个无向图的邻接表结构。 图1-1. 从图
  • ps: 1.部分内容我设置了隐藏,...这次的内容主要难点在删除吧,因为邻接多重的结构,每个结点都两个指针指向他 所以要分别找到这两个结点,让他们的后续指针跳过删除的结点 下面直接上代码吧 #include<stdio...
  • 有向图邻接表实现 初学图的邻接表存储方式,费了很多的时间去理解它。走了很多弯路,终于用代码上实现了这个存储结构,在这里把的感悟和过程做个总结,希望能帮到和我一样的初学者。 对于以下这个图 它的邻接表...
  • 创建(无)向图,深度优先遍历,广度优先遍历 代码实现: #include<stdio.h> #include<stdlib.h> #include<string.h> #define MaxVertexNum 100 #define MaxSize 10 //顶点数目的最大值 ...
  • 邻接表表示图结构是一种简单易懂的方式, #include<stdio.h> //建立图(邻接表) #define num 20//图中的顶点数量 struct Node { int date; ...//顶点,边,类型(1为有向图,0为无向图)
  • 邻接表(adjacency list)是对图中的每个顶点建立一个邻接关系的单链表,并把它们的表头指针用向量存储的一种图的表示方法。...对于有向图来说,等于vi的出边数、或出边邻接点数或出度数。边结点通...

空空如也

空空如也

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

有向图邻接表c语言

c语言 订阅