小弟最近在學資料結構，昨天自己實作了一下鄰接多重表，寫之前是有一點小問題的，本來想找一位大佬寫的程式參考一下，但是并么有找到令人滿意的，所以只能自己獨立寫了，小弟寫這個程式全程只參考了課本中對鄰接多重表的一些簡單的文字描述，至于代碼部分，全是小弟一個人寫出來的，無任何參考，寫的比較冗余，所以如果有大佬覺得小弟寫的太拙劣的話，請嘴下留情，第一次在網上發文，
鄰接多重表相較于鄰接表大大節省了空間（一半），鄰接多重表中定義相鄰頂點的結構體時表示的并不是一個頂點，而是一條邊由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可以在下方留言，我好修改）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/207870.html
標籤：其他