精华内容
下载资源
问答
  • 的存储结构邻接多重表邻接多重表的定义:邻接多重表的代码定义:十字链表与邻接多重表的对比 邻接多重表的定义: 顶点表节点: 1、data:顶点数据域 2、firstedge:边表节点的头指针 边表节点: 1、ivex:该边的...

    产生条件:

    当用邻接矩阵法存储时:空间复杂度为O(|V|^2),太大
    当用邻接表法存储时:一条边会重复存储两次,产生冗余

    邻接多重表的定义:

    在这里插入图片描述

    在这里插入图片描述

    顶点表节点:

    1、data:顶点数据域
    2、firstedge:边表节点的头指针
    

    边表节点:

    1、ivex:该边的第一个端点
    2、ilink:与该端点相邻的下一个边表节点的指针
    3、jvex:该边的第二个端点
    4、jlink:与该端点相邻的下一个边表节点的指针
    5、info:权值
    6、mark:标记
    

    邻接多重表的代码定义:

    #define MaxVertexTypeNum 100
    typedef char VertexType;		
    typedef int EdgeType;	
    
    typedef struct ArcNode{					//边表节点 
    	int ivex,jvex;						//边的俩个节点			
    	struct ArcNode *ilink , *jhink;		//维护俩个节点的边表 
    	//InfoType info; 					//权值 
    	//bool mark;						//标记位 
    }ArcNode;								//边表节点的类型 
    
    typedef struct VNode{					//顶点表节点 
    	VertexType data;					//顶点的数据 
    	ArcNode *firstedge;					//边表的头指针 
    }VNode;									// 邻接表类型 
    
    typedef struct{							//十字链表 
    	VNode adjmulist[MaxVertexTypeNum];	//所有结点的数据 
    	int vexnum,arcnum;					//节点数和边数 
    }ALGraph;								//十字链表的类型 
    

    删除:

    删除边AB:
    在这里插入图片描述
    在这里插入图片描述

    删除节点E:
    在这里插入图片描述在这里插入图片描述

    性能分析:

    空间复杂度:O(|v| + |E|)

    十字链表与邻接多重表的对比

    十字链表: 用于有向图,解决了无法快速找到一个顶点入边的问题
    邻接多重表: 用于无向图,解决了重复存储同一条边2次的问题
    在这里插入图片描述在这里插入图片描述

    展开全文
  • 数据结构————存储结构——邻接多重表 如果我们在无向的应用中,关注的重点是顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着,需要...

    数据结构——图——存储结构——邻接多重表

    如果我们在无向图的应用中,关注的重点是顶点,那么邻接表是不错的选择,但如果我们更关注边的操作,比如对已访问过的边做标记,删除某一条边等操作,那就意味着,需要找到这条边的两个边表结点进行操作,这其实还是比较麻烦的。比如图7-4-11,若要删除左图的(v0,v2)这条边,需要对邻接表结构中右边表的阴影两个结点进行删除操作,显然这是比较烦琐的。
    在这里插入图片描述
    因此,我们也仿照十字链表的方式,对边表结点的结构进行一些改造,也许就可以避免刚才提到的问题。

    重新定义的边表结点结构如表7-4-3所示。
    在这里插入图片描述
    其中 ivex 和jvex是与某条边依附的两个顶点在顶点表中下标。ilink指向依附顶点ivex的下一条边,jlink指向依附顶点jvex的下一条边。这就是邻接多重表结构。

    我们来看结构示意图的绘制过程,理解了它是如何连线的,也就理解邻接多重表构造原理了。如图7-4-12所示,左图告诉我们它有4个顶点和5条边,显然,我们就应该先将4个顶点和5条边的边表结点画出来。由于是无向图,所以ivex是0、jvex是1还是反过来都是无所谓的,不过为了绘图方便,都将ivex值设置得与一旁的顶点下标相同。
    在这里插入图片描述
    我们开始连线,如图7-4-13。首先连线的①②③④就是将顶点的 firstedge指向一条边,顶点下标要与ivex的值相同,这很好理解。接着,由于顶点v0的(v0,v1)边的邻边有(v0,v3)和(v0,v2)。因此⑤⑥的连线就是满足指向下一条依附于顶点v0的边的目标,注意ilink 指向的结点的 jvex一定要和它本身的 ivex的值相同。同样的道理,连线⑦就是指(v1,v0)这条边,它是相当于顶点v1指向(v1,v,2)边后的下一条。vz有三条边依附,所以在③之后就有了⑧⑨。连线⑩的就是顶点vs在连线④之后的下一条边。左图一共有5条边,所以右图有10条连线,完全符合预期。
    在这里插入图片描述
    到这里,大家应该可以明白,邻接多重表与邻接表的差别,仅仅是在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。这样对边的操作就方便多了,若要删除左图的 (v0,v2)这条边,只需要将右图的⑥⑨的链接指向改为 ^ 即可。由于各种基本操作的实现也和邻接表是相似的

    展开全文
  • 数据结构——邻接多重表(C语言实现)

    千次阅读 热门讨论 2020-11-08 13:33:12
    小弟最近在学数据结构,昨天自己实现了一下邻接多重表,写之前是有一点小问题的,本来想找一位大佬写的程序参考一下,但是并么有找到令人满意的,所以只能自己独立写了。小弟写这个程序全程只参考了课本中对邻接多重...

    小弟最近在学数据结构,昨天自己实现了一下邻接多重表,写之前是有一点小问题的,本来想找一位大佬写的程序参考一下,但是并么有找到令人满意的,所以只能自己独立写了。小弟写这个程序全程只参考了课本中对邻接多重表的一些简单的文字描述,至于代码部分,全是小弟一个人写出来的,无任何参考,写的比较冗余,所以如果有大佬觉得小弟写的太拙劣的话,请嘴下留情,第一次在网上发文。

    邻接多重表相较于邻接表大大节省了空间(一半),邻接多重表中定义相邻顶点的结构体时表示的并不是一个顶点,而是一条边由node_1到node_2的一条边,并且有两个指针域一个指针域属于node_1一个指针域属于node_2,他们两个不干扰,就像两条相邻的公路,一条公路上放node_1的车队,另一条公路上放node_2的车队(首先应该建立起邻接多重表的感觉),也正因此一个边节点可以供两个顶点使用
    这是定义边节点的结构体
    在这里插入图片描述
    这是定义顶点节点的结构体,其中vex记录顶点数,edge记录边数,head结构体中记录各顶点的信息,和与其连接的链表的指针域
    在这里插入图片描述

    这是在网上找的一张邻接多重表的图片,各位可以理解一下
    在这里插入图片描述
    然后来讲一下这个程序的重难点!!!!!
    请看上面的那个例图,我们随便找一条边,就v2到v5这条边吧,也就是(4,1)这条边,我们现在要做的是把该边挂载到v2节点和v5节点下,先简单一点,我们先把这条边挂载在v5下(挂载在与node_1值相同的顶点节点下),首先要判断v5下是否有挂载节点,判断无,则把该节点直接挂载在v5顶点节点的next中,这就挂载成功了。
    接下来再挂载在v2下(挂载在与node_2值相同的顶点节点下),一样,先判断v2是否有挂载节点,判断有,用1(node_2)与v2的第一个节点(0,1)比较(先判断已挂载的边节点的node_1和node_2哪一个是要挂载的顶点v2)。发现已挂载的node_2与要挂载的node_2相同,再比较出要挂载的node_1(4)大于已挂载的node_1(0),进入node_2_pointer,再与(2,1)比较发现已挂载的node_2与要挂载的node_2相同,再比较出要挂载的node_1(4)大于已挂载的node_1(2),进入node_2_pointer,发现node_2_pointer为NULL则将(4,1)边节点,挂载在此指针域。对上述操作有疑惑的朋友可以看一下下面括号中的内容。
    (------------------------------------------------------------------------------------------------------------------
    因为是要插在与node_2相同的顶点节点下,所以要用要挂载的node_2进行如下判断:
    第一种情况:若要挂载的边节点的node_2和已挂载的node_1相同,则比较要挂载的node_1和已挂载的node_2,若小,则将该边节点插入到该顶点节点的第一个(next),否则的话,结点指针进入已挂载节点node_1_pointer(为什么不进入node_2_pointer呢?因为上面已经比较出来要挂载的node_2与已挂载的node_1的值相同,所以进入node_1_pointer指针域),接着继续进行同样的操作(比较->判断大小->插入节点或进入指针域)。
    第二种情况:若要挂载的边节点node_2与已挂载的node_2相同,则比较要挂载的node_1和已挂载的node_1,若小,则将该边节点插入到该顶点节点的第一个(next),否则的话,结点指针进入已挂载节点node_2_pointer,为什么进入该指针域,原因同上。接着继续进行同样的操作。
    )--------------------------------------------------------------------------------------------------------------------

    总的来说,插入有三种情况,
    第一种情况:顶点头无挂载,或判断出已挂载的第一个边节点的邻节点大于要挂载的边节点的邻节点,则将该边节点插在顶点节点的next
    第二种情况:判断出需要插在顶点节点的挂载链表中间
    第三种情况:要挂载的边节点的邻节点大于所有的已挂载的边节点的邻节点
    (因为情况太复杂,所以语言描述起来十分吃力,各位看起来也应该一样^ _ ^)
    下面请各位看一下代码

    #include<stdio.h>
    //邻接多重表
    #define MAX 20
    
    
    struct Enode
    {
    	int node_1;
    	int node_2;
    	struct Enode* node_1_pointer;
    	struct Enode* node_2_pointer;
    };
    
    struct AMLGraph
    {
    	int edge;
    	int vex;
    	struct
    	{
    		char head_ele;
    		struct Enode* next;
    	}head[MAX];
    };
    
    void show(struct AMLGraph* map);
    void creat(struct AMLGraph* map);
    void insert(struct AMLGraph* map, char node_1, char node_2);
    
    
    void creat(struct AMLGraph* map)
    {
    	char node_1;
    	char node_2;
    	printf("要建立几个节点,几条边:");
    	scanf("%d%d", &map->vex, &map->edge);
    	getchar();
    	for (int i = 0; i < map->vex; i++)
    	{
    		map->head[i].next = NULL;
    		map->head[i].head_ele = i + 'A';
    	}
    	printf("请输入边:\n");
    	for (int i = 0; i < map->edge; i++)
    	{
    		scanf("%c%c", &node_1, &node_2);
    		getchar();
    		insert(map, node_1, node_2);
    	}
    
    
    }
    void insert(struct AMLGraph* map, char node_1, char node_2)
    {
    	struct Enode* now;
    	struct Enode* q;
    	struct Enode* before;
    	struct Enode* p = malloc(sizeof(struct Enode));
    	p->node_1 = node_1 - 'A';
    	p->node_2 = node_2 - 'A';
    	p->node_1_pointer = NULL;
    	p->node_2_pointer = NULL;
    	//把此节点分别挂载在node_1和node_2的链表中
    	//插入与node_1相同的链表
    	now = map->head[node_1 - 'A'].next;
    	before = now;
    	while (now)
    	{
    		//判断该节点是否要插在链表头
    		if (node_1-'A' == map->head[node_1 - 'A'].next->node_1 )
    		{
    			if (node_2-'A' < map->head[node_1 - 'A'].next->node_2)
    			{
    				p->node_1_pointer = map->head[node_1 - 'A'].next;
    				map->head[node_1 - 'A'].next = p;
    				break;
    			}
    		}
    		else
    		{
    			if (node_2 - 'A' < map->head[node_1 - 'A'].next->node_1)
    			{
    				p->node_1_pointer = map->head[node_1 - 'A'].next;
    				map->head[node_1 - 'A'].next = p;
    				break;
    			}
    		}
    		
    		//node_1和now->node_1相等
    		if (node_1 - 'A' == now->node_1)
    		{
    			if (node_2 - 'A' > now->node_2)
    			{
    				before = now;
    				now = now->node_1_pointer;
    			}
    			else if (node_2 - 'A' < now->node_2)
    			{
    				if (before->node_1 == node_1 - 'A')
    				{
    					q = before->node_1_pointer;
    					before->node_1_pointer = p;
    					p->node_1_pointer = q;
    				}
    				else
    				{
    					q = before->node_2_pointer;
    					before->node_2_pointer = p;
    					p->node_1_pointer = q;
    				}
    				break;
    			}
    		}
    		else//node_1和now->node_2相等
    		{
    			if (node_2 - 'A' > now->node_1)
    			{
    				before = now;
    				now = now->node_2_pointer;
    			}
    			else if (node_2 - 'A' < now->node_1)
    			{
    				if (before->node_2 == node_1 - 'A')
    				{
    					q = before->node_2_pointer;
    					before->node_2_pointer = p;
    					p->node_1_pointer = q;
    				}
    				else
    				{
    					q = before->node_1_pointer;
    					before->node_1_pointer = p;
    					p->node_1_pointer = q;
    				}
    				break;
    			}
    		}
    
    	}
    
    	if (!now)//有两种情况map->head[node_1 - 'A'].next为空或要插在链表尾
    	{
    		if (!before)
    		{
    			map->head[node_1 - 'A'].next = p;
    		}
    		else if (before->node_1 == node_1 - 'A')
    		{
    			before->node_1_pointer = p;
    		}
    		else if (before->node_2 == node_1 - 'A')
    		{
    			before->node_2_pointer = p;
    		}
    	}
    	//--------------------------------------------------------------------------------------
    	//插入与node_2相同的链表
    	now = map->head[node_2 - 'A'].next;
    	before = now;
    	while (now)
    	{
    		//判断该节点是否要插在链表头
    		if (node_2 - 'A' == map->head[node_2 - 'A'].next->node_1)
    		{
    			if (node_1 - 'A' < map->head[node_2 - 'A'].next->node_2)
    			{
    				p->node_2_pointer = map->head[node_2 - 'A'].next;
    				map->head[node_2 - 'A'].next = p;
    				break;
    			}
    		}
    		else
    		{
    			if (node_1 - 'A' < map->head[node_2 - 'A'].next->node_1)
    			{
    				p->node_2_pointer = map->head[node_2 - 'A'].next;
    				map->head[node_2 - 'A'].next = p;
    				break;
    			}
    		}
    
    		//node_2和now->node_2相等
    		if (node_2 - 'A' == now->node_2)
    		{
    			if (node_1 - 'A' > now->node_1)		
    			{
    				before = now;
    				now = now->node_2_pointer;
    			}
    			else if (node_1 - 'A' < now->node_1)
    			{
    				
    				if (before->node_1 == node_2 - 'A')
    				{
    					q = before->node_1_pointer;
    					before->node_1_pointer = p;
    					p->node_2_pointer = q;
    				}
    				else
    				{
    					q = before->node_2_pointer;
    					before->node_2_pointer = p;
    					p->node_2_pointer = q;
    				}
    				break;
    			}
    		}
    		else//node_2和now->node_1相等
    		{
    			if (node_1 - 'A' > now->node_2)
    			{
    				before = now;
    				now = now->node_1_pointer;
    			}
    			else if (node_1 - 'A' < now->node_2)
    			{
    				if (before->node_1 == node_2-'A')
    				{
    					q = before->node_1_pointer;
    					before->node_1_pointer = p;
    					p->node_2_pointer = q;
    				}
    				else
    				{
    					q = before->node_2_pointer;
    					before->node_2_pointer = p;
    					p->node_2_pointer = q;
    				}
    				break;
    			}
    		}
    	}
    	if (!now)//有两种情况map->head[node_2 - 'A'].next为空或要插在链表尾
    	{
    		if (!before)
    		{
    			map->head[node_2 - 'A'].next = p;
    		}
    		else if (before->node_1 == node_2 - 'A')
    		{
    			before->node_1_pointer = p;
    		}
    		else if (before->node_2 == node_2 - 'A')
    		{
    			before->node_2_pointer = p;
    		}
    	}
    }
    
    void show(struct AMLGraph* map)
    {
        int head_ele;
    	struct Enode* p;
    	for (int i = 0; i < map->vex; i++)
    	{
    		p = map->head[i].next;
    		head_ele = map->head[i].head_ele - 'A';
    		printf("与%c相连的节点有:", head_ele+'A');
    		while (p)
    		{
    
    			printf("%c ",( head_ele == p->node_1 ? (p->node_2 + 'A') :( p->node_1 + 'A')));//head_ele如果等于p->node_1就把另一个值输出
    			p = (head_ele == p->node_1 ?( p->node_1_pointer) : (p->node_2_pointer));//head_ele如果等于p->node_1就进入p->node_1_pointer
    		}
    		printf("\n");
    	}
    
    }
    
    
    
    int main()
    {
    
    	struct AMLGraph map;
    	creat(&map);
    	show(&map);
    }
    
    
    
    
    
    

    下面看两个在vs2019下运行的结果吧

    在这里插入图片描述
    在这里插入图片描述

    我还在书上找了一个比较复杂的图验证了一下,结果是正确的
    在这里插入图片描述

    在这里插入图片描述
    如果有什么不懂同学可以在下方留言,大家一起进步^ _ ^(对了,如果有朋友运行程序时发现bug可以在下方留言,我好修改)

    展开全文
  • 边数不少于30,的类型可以是有向、无向、有向网、无向网),能够输入的顶点和边(或弧)的信息,并存储到相应存储结构(邻接矩阵、邻接表、十字链表、邻接多重表,任选其中两种类型),对自己所创建的完成...
  • 数据结构邻接多重表

    万次阅读 多人点赞 2017-05-06 11:57:32
    介绍了无向的另一种链式存储方式--邻接多重表

    邻接多重表

    上一节总结了有向图的另外一种链式存储结构—十字链表,该节继续总结无向图的另一种链式存储结构。

    基本概念

    邻接表虽然已经能够很好地表示无向图了,但是无向图访问或者删除一条边(Vi,Vj)时需要同时访问两个链表i和j并分别找到对应的边结点,这给针对图的边的操作(标记或删除)带来不便利。邻接多重表因此而演变过来的。

    邻接多重表中,无向图中的每一个顶点分配一个顶点结点,所有顶点结点构成一个顶点数组adjmultiList[num]。另外每条边也分配一个边结点。

    顶点结构如下所示:


    其中data用来记录顶点的信息,firstEdge用来表示依附于该顶点的第一条边。

    顶点数组如下所示:

    边结点结构如下所示:

    其中mark表示标志位,用于标记该边是否已经被访问过;iVex和jVex表示该边的两个顶点在顶点数组adjmultiList[num]中的位置;iLink和jLink分别表示指向依附于顶点iVex和jVex下一条边的指针。

    从上面的顶点和边的结构来看,邻接多重表和邻接表的主要区别在于:邻接多重表中的边结点同时被链入对应边顶点的链表内(2条);邻接表中的边用两个表结点表示。另外,邻接多重表中的边结点就表示一条边,比较容易理解。

    举个例子。某无向图如下图所示:


    当采用邻接表表示该无向图时,其邻接表入下图所示:

    如上图所示,图中黄色标记的结点表示A-D之间的边,在邻接表中一条边需要两个结点表示。因此如果对于边的操作(标记或者删除)则需要访问两条链表。

    当采用邻接多重表表示该无向图时,其邻接多重表入下图所示:


    如上图所示,结点A-D 之间的边,在邻接多重表中只需要一个边结点既可以表示。另外,在该结构中,每个边结点被链入了两个不同的链表。其中A-D之间的边被链入了红色和绿色标记的链表中。如果需要访问一条边,则可以从该边的两个顶点结点中的任何一个出发,遍历依附于该顶点的边构成的链表即可。如果需要删除一条边,则只需要删除一个边结点,但是需要修改这条边依附的两个顶点所对应的链表。另外,需要注意的是,在无向图中,边结点中的iVexjVex链域与该边所依附的顶点无关,即iVex=0jVex=3iVex=3jVex=0这都表示同一条边A-D,因此这给链表的指针修改带来一定的麻烦。

    基本操作

    1、建立无向图的邻接多重表

    输入ABCDE五个顶点V={A,B,C,D,E},然后输入边E={(A,B),(B,C),(B,E),(C,D),(C,E),(D,A)},建立如下无向图:


    代码如下:

    Status createAMLGraph(AMLGraph &G, int vexNum){
    	G.vexNum = vexNum;
    	G.edgeNum = 0;
    	for(int i = 0; i< G.vexNum; i++){
    		cin>>G.adjmultiList[i].data;
    		G.adjmultiList[i].firstEdge = NULL;
    	}
    
    	cout<<"Try to input arcs info"<<endl;
    	while(1){
    		char SWITCH;
    		cout<<"are you going to add a edge into AMLGraph?(y?n)"<<endl;
    		
    		cin>>SWITCH;
    		if(SWITCH == 'y'){
    			cout<<"please input two nodes of "<<G.edgeNum+1<<"-th arc"<<endl;
    
    			vertexNode node1, node2;
    			cin>>node1.data>>node2.data;
    			insertEdge(G, node1, node2);
    			G.edgeNum++;
    		}
    		else
    			break;
    	}
    	return 1;
    }

    2、打印无向图的邻接多重表


    代码如下:

    Status printAMLGraph(AMLGraph &G){
    	for(int i = 0; i<G.vexNum; i++){
    		cout<<i<<" "<<G.adjmultiList[i].data;
    		edgeNode *edge = G.adjmultiList[i].firstEdge;
    
    		while(edge){
    			cout<<"-->|"<<edge->iVex<<"|"<<edge->jVex<<"|";
    			if(edge->iVex == i){
    				edge = edge->iLink;
    			}
    			else{
    				edge = edge->jLink;
    			}
    		}
    		cout<<"-->NULL"<<endl;
    	}
    	return 1;
    }

    3、向无向图中添加顶点

    向无向图中添加结点F。


    代码如下:

    Status insertNode(AMLGraph &G, vertexNode node){
    	G.adjmultiList[G.vexNum].data = node.data;
    	G.adjmultiList[G.vexNum].firstEdge = NULL;
    	G.vexNum++;
    	return 1;
    }

    4、向无向图中添加边

    向无向图中添加边A-C。


    代码如下:
    void insertEdgeAction(AMLGraph &G, int index1, int index2){
    	edgeNode *p, *q;
    	edgeNode *edge = new edgeNode[1];
    	
    	edge->iVex = index1;
    	edge->jVex = index2;
    
    	p = G.adjmultiList[index1].firstEdge;//相当于链表的插入
    	if(!p){
    		G.adjmultiList[index1].firstEdge = edge;
    		edge->iLink = NULL;
    	}
    	else{
    		G.adjmultiList[index1].firstEdge = edge;
    
    		edge->iLink = p;
    	}
    
    	q = G.adjmultiList[index2].firstEdge;//相当于链表的插入
    	if(!q){
    		G.adjmultiList[index2].firstEdge = edge;
    		edge->jLink = NULL;
    	}
    	else{
    		G.adjmultiList[index2].firstEdge = edge;
    		edge->jLink = q;
    	}
    }
    
    Status insertEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
    	int index1 = locateNode(G, node1);//i和j表示AdjList[MAX_VERTEX_NUM]中的位置
    	int index2 = locateNode(G, node2);
    	if(index1<0 || index2<0) exit(-1);
    	
    	insertEdgeAction(G, index1, index2);
    
    	return 1;
    }

    5、删除无向图中的边

    删除无线图中的边B-C。


    代码如下:
    Status deleteEdgeAction(AMLGraph &G, int index1, int index2){
    	edgeNode *curEdge = G.adjmultiList[index1].firstEdge;
    	edgeNode *preEdge = curEdge;
    	int count = 0;
    
    	if(!curEdge) return 1;
    	else{
    		while(curEdge){
    			count++;
    			if((curEdge->iVex == index1&&curEdge->jVex == index2)||(curEdge->iVex == index2&&curEdge->jVex == index1)){
    				break;
    			}
    			preEdge = curEdge;
    			if(curEdge->iVex ==index1)
    				curEdge = curEdge->iLink;
    			else
    				curEdge = curEdge->jLink;
    		}
    	}
    
    	if(!curEdge)
    		return 1;
    	else if(count<=1){
    		if(preEdge->iVex == index1)
    			G.adjmultiList[index1].firstEdge = preEdge->iLink;
    		else 
    			G.adjmultiList[index1].firstEdge = preEdge->jLink;
    	}
    	else{
    		if(preEdge->iVex == index1){ 
    			if (curEdge->iVex == index1)
    				preEdge->iLink = curEdge->iLink;
    			else
    				preEdge->iLink = curEdge->jLink;
    		}
    		else{
    			if (curEdge->iVex == index1)
    				preEdge->jLink = curEdge->iLink;
    			else
    				preEdge->jLink = curEdge->jLink;
    		}
    	}
    	return 1;
    }
    
    Status deleteEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
    	int index1 = locateNode(G, node1);
    	int index2 = locateNode(G, node2);
    
    	deleteEdgeAction(G, index1, index2);
    	deleteEdgeAction(G, index2, index1);
    
    	return 1;
    }

    6、删除无向图中的顶点

    删除结点C。


    代码如下:

    Status deleteNode(AMLGraph &G, vertexNode node){
    	//删除结点时,结点不真实删除而只是删除结点相关的边以及赋值该结点的data为特殊值‘0’
    	int index = locateNode(G, node);
    
    	for(int i = 0; i<G.vexNum; i++){
    		if(i == index) continue;
    		else{
    			deleteEdge(G, G.adjmultiList[index], G.adjmultiList[i]);
    		}
    	}
    	G.adjmultiList[index].firstEdge = NULL;
    	G.adjmultiList[index].data = '0';
    	return 1;
    }

    7、全部代码:

    // 邻接多重表.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include <iostream>
    
    using namespace std;
    
    #define MAX_VERTEX_NUM 20
    
    typedef int infoType;
    typedef char vertexType;
    typedef int Status;
    
    typedef struct edgeNode{
    	int iVex, jVex;
    	struct edgeNode *iLink, *jLink;
    	infoType *info;
    }edgeNode;
    
    typedef struct vertexNode{
    	vertexType data;
    	edgeNode *firstEdge;
    }vertexNode;
    
    typedef struct{
    	vertexNode adjmultiList[MAX_VERTEX_NUM];
    	int vexNum, edgeNum;
    }AMLGraph;
    
    int locateNode(AMLGraph &G, vertexNode node){
    	for(int i=0; i<G.vexNum;i++){
    		if(node.data == G.adjmultiList[i].data)
    			return i;
    	}
    	return -1;
    }
    
    Status insertEdge(AMLGraph &G, vertexNode node1, vertexNode node2);
    
    Status createAMLGraph(AMLGraph &G, int vexNum){
    	G.vexNum = vexNum;
    	G.edgeNum = 0;
    	for(int i = 0; i< G.vexNum; i++){
    		cin>>G.adjmultiList[i].data;
    		G.adjmultiList[i].firstEdge = NULL;
    	}
    
    	cout<<"Try to input arcs info"<<endl;
    	while(1){
    		char SWITCH;
    		cout<<"are you going to add a edge into AMLGraph?(y?n)"<<endl;
    		
    		cin>>SWITCH;
    		if(SWITCH == 'y'){
    			cout<<"please input two nodes of "<<G.edgeNum+1<<"-th arc"<<endl;
    
    			vertexNode node1, node2;
    			cin>>node1.data>>node2.data;
    			insertEdge(G, node1, node2);
    			G.edgeNum++;
    		}
    		else
    			break;
    	}
    	return 1;
    }
    
    void insertEdgeAction(AMLGraph &G, int index1, int index2){
    	edgeNode *p, *q;
    	edgeNode *edge = new edgeNode[1];
    	
    	edge->iVex = index1;
    	edge->jVex = index2;
    
    	p = G.adjmultiList[index1].firstEdge;//相当于链表的插入
    	if(!p){
    		G.adjmultiList[index1].firstEdge = edge;
    		edge->iLink = NULL;
    	}
    	else{
    		G.adjmultiList[index1].firstEdge = edge;
    
    		edge->iLink = p;
    	}
    
    	q = G.adjmultiList[index2].firstEdge;//相当于链表的插入
    	if(!q){
    		G.adjmultiList[index2].firstEdge = edge;
    		edge->jLink = NULL;
    	}
    	else{
    		G.adjmultiList[index2].firstEdge = edge;
    		edge->jLink = q;
    	}
    }
    
    Status insertEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
    	int index1 = locateNode(G, node1);//i和j表示AdjList[MAX_VERTEX_NUM]中的位置
    	int index2 = locateNode(G, node2);
    	if(index1<0 || index2<0) exit(-1);
    	
    	insertEdgeAction(G, index1, index2);
    
    	return 1;
    }
    
    Status printAMLGraph(AMLGraph &G){
    	for(int i = 0; i<G.vexNum; i++){
    		cout<<i<<" "<<G.adjmultiList[i].data;
    		edgeNode *edge = G.adjmultiList[i].firstEdge;
    
    		while(edge){
    			cout<<"-->|"<<edge->iVex<<"|"<<edge->jVex<<"|";
    			if(edge->iVex == i){
    				edge = edge->iLink;
    			}
    			else{
    				edge = edge->jLink;
    			}
    		}
    		cout<<"-->NULL"<<endl;
    	}
    	return 1;
    }
    
    Status insertNode(AMLGraph &G, vertexNode node){
    	G.adjmultiList[G.vexNum].data = node.data;
    	G.adjmultiList[G.vexNum].firstEdge = NULL;
    	G.vexNum++;
    	return 1;
    }
    
    Status deleteEdgeAction(AMLGraph &G, int index1, int index2){
    	edgeNode *curEdge = G.adjmultiList[index1].firstEdge;
    	edgeNode *preEdge = curEdge;
    	int count = 0;
    
    	if(!curEdge) return 1;
    	else{
    		while(curEdge){
    			count++;
    			if((curEdge->iVex == index1&&curEdge->jVex == index2)||(curEdge->iVex == index2&&curEdge->jVex == index1)){
    				break;
    			}
    			preEdge = curEdge;
    			if(curEdge->iVex ==index1)
    				curEdge = curEdge->iLink;
    			else
    				curEdge = curEdge->jLink;
    		}
    	}
    
    	if(!curEdge)
    		return 1;
    	else if(count<=1){
    		if(preEdge->iVex == index1)
    			G.adjmultiList[index1].firstEdge = preEdge->iLink;
    		else 
    			G.adjmultiList[index1].firstEdge = preEdge->jLink;
    	}
    	else{
    		if(preEdge->iVex == index1){ 
    			if (curEdge->iVex == index1)
    				preEdge->iLink = curEdge->iLink;
    			else
    				preEdge->iLink = curEdge->jLink;
    		}
    		else{
    			if (curEdge->iVex == index1)
    				preEdge->jLink = curEdge->iLink;
    			else
    				preEdge->jLink = curEdge->jLink;
    		}
    	}
    	return 1;
    }
    
    Status deleteEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
    	int index1 = locateNode(G, node1);
    	int index2 = locateNode(G, node2);
    
    	deleteEdgeAction(G, index1, index2);
    	deleteEdgeAction(G, index2, index1);
    
    	return 1;
    }
    
    Status deleteNode(AMLGraph &G, vertexNode node){
    	//删除结点时,结点不真实删除而只是删除结点相关的边以及赋值该结点的data为特殊值‘0’
    	int index = locateNode(G, node);
    
    	for(int i = 0; i<G.vexNum; i++){
    		if(i == index) continue;
    		else{
    			deleteEdge(G, G.adjmultiList[index], G.adjmultiList[i]);
    		}
    	}
    	G.adjmultiList[index].firstEdge = NULL;
    	G.adjmultiList[index].data = '0';
    	return 1;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int vexNum = 5;
    	AMLGraph G;
    	cout<<"Try to create a adjacence multilist of a graph ..."<<endl;
    	createAMLGraph(G, vexNum);
    	printAMLGraph(G);
    
    	cout<<"Try to insert a node into the graph..."<<endl;
    	vertexNode node;
    	cout<<"   please input the data of the node to insert:"<<endl;
    	cin>>node.data;
    	insertNode(G, node);
    	printAMLGraph(G);
    
    	cout<<"Try to insert a edge into the graph..."<<endl;
    	vertexNode node1, node2;
    	cout<<"   please choose two node:"<<endl;
    	cin>>node1.data>>node2.data;
    	insertEdge(G, node1, node2);
    	printAMLGraph(G);
    
    	cout<<"Try to delete the edge between two nodes..."<<endl;
    	vertexNode node3, node4;
    	cout<<"   please choose a edge with specifing two nodes:"<<endl;
    	cin>>node3.data>>node4.data;
    	deleteEdge(G, node3, node4);
    	printAMLGraph(G);
    
    	cout<<"Try to delete a node of the graph..."<<endl;
    	vertexNode node5;
    	cout<<"   please choose a node:"<<endl;
    	cin>>node5.data;
    	deleteNode(G, node5);
    	printAMLGraph(G);
    
    	system("pause");
    	return 0;
    }
    



    展开全文
  • 无向邻接多重表 无向邻接多重表存储表示 #define MAX_VERTEX_NUM 20 typedef enmu{unvisited,visited} VisitIf; //枚举类型,将变量限定在一定范围内 //链表中的边结点 typedef struct EBox{ VisitIf mark...
  • 无向邻接多重表(Adjacency Multilist)表示
  • 二、无向的存储结构邻接多重表法 2.1 邻接多重表法定义 顶点结构定义 data:数据域,存放顶点数据 firstedge:第一条边的指针 边表节点结构定义 ivex:边的两个顶点其中一个顶点 i 的序号 ilink:边的两个顶点...
  • } } } void InputGraph(AMLGraph G)//邻接多重表的输出 { int i,j;//记录次数 EBox *p1,*p2;//用于遍历链表 printf("邻接多重表为:\n"); //为了能验证创建的是否正确 for(i=0;i;i++)//利用循环输出 { ...
  • 上篇博客讲到,图状结构是非常复杂的结构,图也是非常复杂的,所以图的存储就是一个非常重要的部分,因为我们不仅要表示顶点集...邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。 设G=(V,E)是一个图,其中V={v1,v2...
  • 7.2 的存储结构7.2.3 邻接多重表(多重邻接表)Adjacency Multilist邻接多重表的类定义邻接多重表的顶点结点类模板邻接多重表的边结点类模板邻接多重表的类模板邻接多重表与邻接表的对比 7.2.3 邻接多重表(多重...
  • 多重邻接表数组元素结构是:数据、包含 当前索引对应顶点 的第一条边引用。 多重邻接表链表的元素结构是:边的起点、包含当前边的起点的另一条边的引用、边的终点、包含当前边终点的另一条边的...
  • ps: 1.部分内容我设置了隐藏,...这次的内容主要难点在删除吧,因为邻接多重表结构,每个结点都有两个指针指向他 所以要分别找到这两个结点,让他们的后续指针跳过删除的结点 下面直接上代码吧 #include<stdio...
  • 除此之外还有链式存储结构,包括邻接表、十字链表和邻接多重表。其中邻接矩阵和邻接表最常用。 十字链表 十字链表(Orthogonal List)是有向的另一种链式存储结构,可以看作是有向的...
  • 上一节介绍了如何使用顺序存储...使用链式存储结构表示的常用方法有 3 种:邻接表、邻接多重表和十字链表。 邻接的意思是顶点之间有边或者弧存在,通过当前顶点,可以直接找到下一个顶点。 邻接表 使用邻接表存...
  • 4、邻接多重表 1、邻接矩阵法 所谓邻接矩阵存储,是指用一个一维数组存储中顶点的信息,用一个二维数组存储中边的信息(即各顶点之间的邻接关系),存储顶点之间邻接关系的二维数组称为邻接矩阵。 结点数为n...
  • 如果我们在无向的应用中,关注的重点是顶点的话,那么邻接表是不错的选择,但如果我们更关注的是边的操作,比如对已经访问过的边做标记,或者删除某一条边等操作,邻接表就显得不那么方便了。 因此,我们也...
  • 邻接多重表为存储结构,实现连通无向的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 【测试数据】 这里我将可视化数据提取特征,变为可利用数据,...
  • 学习数据结构和离散数学的同学, 这是我的理解和相关代码
  •   由主函数中图的顶点数组和邻接矩阵,给出的已知信息,据此建立无向邻接多重表。   因为对于无向的邻接链表来说,一条边对应的顶点间的连接关系会在两个顶点的邻接链表里各出现一次,造成存储上的资源...
  • 文章目录邻接表1、邻接表表示法2、无向的邻接表3、有向的邻接表4、练习5、邻接表的结构类型定义6、采用邻接表表示法创建无向网7、邻接表特点8、邻接矩阵与邻接表表示法的关系十字链表邻接多重表 邻接表 1、邻接...
  • 邻接多重表的实现。这次研讨确实有难度,除了实现这个还要完成最小生成树。 直接上代码吧。 边节点Arc.h #ifndef ARC_H #define ARC_H #ifndef NULL #define NULL 0 #endif struct Arc { bool tag; int ...
  • 数据结构---- 前言   学习数据结构的时候,经常存在这样一个问题,为什么有这么多的数据结构,有一种不就行了吗?假如数据结构是不断发展的,那怎么学习最好的那种结构不就行了?解释一下 1:我们学习的...
  • 邻接多重表 是 无向的 另一种表示法。其与 邻接表 的差别 仅仅 在于 ,邻接表 用 两个 顶点 来表示 一条边,而 邻接多重表 用一个 顶点来表示一条边。这样使得 邻接多重表 在 某些操作 要 来的 方便。例如 将 ...
  • 无向邻接多重表存储结构: 上是根据程序定义的无向的存储结构。程序中基本操作函数 CreateGraph()是在表头插入边结点的。所以,对于给定的,它的边结点的链表结构也不惟一,与边的输入顺序有关。...
  • 的存储结构 邻接矩阵 用一维数组存储顶点信息,用二维数组表示邻接关系 一个无向: 一个带权邻接矩阵存储特点: 1)无向邻接矩阵是对称阵。 对于无向,i行(i列)非零元素个数=第i个顶点的度TD ...
  • 【十字链-用于有向】 定点结点: data:数据内容 firstin:以该顶点为尾的第一个弧结点(A→B) firstout:以该顶点为头的第一个弧结点(A→B) 实际上对于选边没有一个特定的规则,所以firstin/out的结点...
  • 结点数为n的G = (V,E)的邻接矩阵A是n×n的。 将G的顶点编号为v1,v2,,…,Vn,(数组下标) 若<vi,vj>∈E,则A[i][j]=1,否则A[i][j]=O。 无向 #define MaxvertexNum 100 typedef char vertexType; ...
  • 邻接矩阵不对称,行和是出度,列和是入度网:用一个不可能的值表示不存在的边的权代码邻接表:最常使用的存储结构,把数组和链表结合使用有向的逆邻接表带权邻接表:给边结点增加一个存储权值的数据域代码十字...
  •  你会发现,要表示一个有向,因为有 出度 和 入度 ,需要两个邻接表邻接表和逆邻接表。  其实我们可以把这两个整合在一起,也就是十字链(Orthogonal List)。  我们依然需要构造一种结构体A,用结构体...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,806
精华内容 1,522
关键字:

数据结构图邻接多重表

数据结构 订阅