数据结构

2024-06-21 12:28| 来源: 网络整理| 查看: 265

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

邻接多重表相较于邻接表大大节省了空间（一半），邻接多重表中定义相邻顶点的结构体时表示的并不是一个顶点，而是一条边由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 //邻接多重表 #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 vex; i++) { map->head[i].next = NULL; map->head[i].head_ele = i + 'A'; } printf("请输入边:\n"); for (int i = 0; i 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' 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' 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' 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' 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' 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' 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' 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' 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 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可以在下方留言，我好修改）

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻