《数据布局（C语言版）第二版》第六章-图（6.4 图的存储布局——6.4.2 毗邻
6.4.2 毗邻表接纳毗邻表表现法创建无向图
//算法6.2 采用邻接表表示法创建无向图
#include <stdio.h>
#include <stdlib.h>
#define MVNum 100
typedef int OtherInfo; //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef struct ArcNode
{
int adjvex;
struct ArcNode* nextarc;
OtherInfo info;
}ArcNode;//边结点
typedef struct VNode
{
VerTexType data;
ArcNode* firstarc;
}VNode,AdjList;//表头结点
typedef struct
{
AdjList vertices;//存储所有顶点
int vexnum;//顶点总数
int arcnum;//总边数
}ALGraph;//图的信息
void CreateUDG(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph &G);
int main()
{
ALGraph G = { {'\0',NULL}, 0,0};
CreateUDG(G);
printALGraph(G);
return 0;
}
void CreateUDG(ALGraph& G)
{
int i = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
int j = 0;
ArcNode *p1 = NULL;
ArcNode *p2 = NULL;
printf("请输入无向图的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入无向图的总边数：");
scanf_s(" %d", &G.arcnum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.vertices.data));
G.vertices.firstarc = NULL; //初始化
}
for (k = 0; k < G.arcnum; k++)
{
printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = (ArcNode*)malloc(sizeof(ArcNode));
p1->adjvex = j;
p1->nextarc = G.vertices.firstarc;
G.vertices.firstarc = p1;//将新结点*p1插入顶点Vi的边表头部
p2 = (ArcNode*)malloc(sizeof(ArcNode));
p2->adjvex = i;
p2->nextarc = G.vertices.firstarc;
G.vertices.firstarc = p2;//将与*p1对称的新的边结点*p2插入顶点Vj的边表头部
}
}
//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{
int i = 0;
for (i = 0; i < G.vexnum && (G.vertices.data != v); ++i)
{
;
}
return i;
}
//打印邻接表
void printALGraph(ALGraph& G)
{
int i = 0;
ArcNode* pMove = NULL;
for (i = 0; i < G.vexnum; i++)
{
printf("\n第%d个顶点为：%c", i + 1, G.vertices.data);
pMove = G.vertices.firstarc;
if (pMove)
{
printf("\n与第%d个顶点相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
while (pMove)
{
printf("%d ", pMove->adjvex);
pMove = pMove->nextarc;
}
}
else
{
printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);
}
}
}
https://i-blog.csdnimg.cn/direct/11e50d6f3d064f0898897eb04595a79a.png
https://i-blog.csdnimg.cn/direct/8c94c52927ee40a7a39e29719f3eeed2.png
https://i-blog.csdnimg.cn/direct/fea1ccf3c94d4e709b0273eea7713629.png
一个图的毗邻矩阵表现是唯一的，但其毗邻表表现不唯一。
不改变图中每个顶点的命名方式，也不改变图的边（每条边的起尽头），
仅改变边的输入序次时，图的毗邻表中每个顶点背面边表中的结点排序方式会发生变化。
由于图中的顶点没变，边也没变，每个顶点及其边表中的内容不会发生变化。
https://i-blog.csdnimg.cn/direct/82f4efd36dd34330bbe81d4d6f8210bd.png
https://i-blog.csdnimg.cn/direct/f9e66b1612e84ddeb7c455fbcf8aa224.png
https://i-blog.csdnimg.cn/direct/be3a103d73bf4d0289deb321cb691fd4.png
接纳毗邻表表现法创建有向图
//采用邻接表表示法创建有向图
#include <stdio.h>
#include <stdlib.h>
#define MVNum 100
typedef int OtherInfo; //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef struct ArcNode
{
int adjvex;
struct ArcNode* nextarc;
OtherInfo info;
}ArcNode;//边结点
typedef struct VNode
{
VerTexType data;
ArcNode* firstarc;
}VNode, AdjList;//表头结点
typedef struct
{
AdjList vertices;//存储所有顶点
int vexnum;//顶点总数
int arcnum;//总边数
}ALGraph;//图的信息
void CreateDG(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
int main()
{
ALGraph G = { {'\0',NULL}, 0,0 };
CreateDG(G);
printALGraph(G);
return 0;
}
//采用邻接表表示法创建有向图
void CreateDG(ALGraph& G)
{
int i = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
int j = 0;
ArcNode* p1 = NULL;
ArcNode* p2 = NULL;
printf("请输入有向图的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入有向图的总边数：");
scanf_s(" %d", &G.arcnum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.vertices.data));
G.vertices.firstarc = NULL; //初始化
}
for (k = 0; k < G.arcnum; k++)
{
printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = (ArcNode*)malloc(sizeof(ArcNode));
p1->adjvex = j;
p1->nextarc = G.vertices.firstarc;
G.vertices.firstarc = p1;//将新结点*p1插入顶点Vi的边表头部
}
}
//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{
int i = 0;
for (i = 0; i < G.vexnum && (G.vertices.data != v); ++i)
{
;
}
return i;
}
//打印邻接表
void printALGraph(ALGraph& G)
{
int i = 0;
ArcNode* pMove = NULL;
for (i = 0; i < G.vexnum; i++)
{
printf("\n第%d个顶点为：%c", i + 1, G.vertices.data);
pMove = G.vertices.firstarc;
if (pMove)
{
printf("\n将第%d个顶点作为出度，与其相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
while (pMove)
{
printf("%d ", pMove->adjvex);
pMove = pMove->nextarc;
}
}
else
{
printf("\n将第%d个顶点作为出度，没有与其相邻接的顶点。", i + 1);
}
}
}
https://i-blog.csdnimg.cn/direct/25ef799994a643dfb8efac9c4cba5143.png
https://i-blog.csdnimg.cn/direct/1f05e968d7f249f1a8c649e81bb30e19.png
https://i-blog.csdnimg.cn/direct/38157912c9554322a0d6984298dcb490.png
创建有向图的逆毗邻表
//创建有向图的逆邻接表
#include <stdio.h>
#include <stdlib.h>
#define MVNum 100
typedef int OtherInfo; //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef struct ArcNode
{
int adjvex;
struct ArcNode* nextarc;
OtherInfo info;
}ArcNode;//边结点
typedef struct VNode
{
VerTexType data;
ArcNode* firstarc;
}VNode, AdjList;//表头结点
typedef struct
{
AdjList vertices;//存储所有顶点
int vexnum;//顶点总数
int arcnum;//总边数
}ALGraph;//图的信息
void CreateDG(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
int main()
{
ALGraph G = { {'\0',NULL}, 0,0 };
CreateDG(G);
printALGraph(G);
return 0;
}
//创建有向图的逆邻接表
void CreateDG(ALGraph& G)
{
int i = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
int j = 0;
ArcNode* p1 = NULL;
ArcNode* p2 = NULL;
printf("请输入有向图的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入有向图的总边数：");
scanf_s(" %d", &G.arcnum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.vertices.data));
G.vertices.firstarc = NULL; //初始化
}
for (k = 0; k < G.arcnum; k++)
{
printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = (ArcNode*)malloc(sizeof(ArcNode));
p1->adjvex = i;
p1->nextarc = G.vertices.firstarc;
G.vertices.firstarc = p1;//将新结点*p1插入顶点Vj的边表头部
}
}
//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{
int i = 0;
for (i = 0; i < G.vexnum && (G.vertices.data != v); ++i)
{
;
}
return i;
}
//打印逆邻接表
void printALGraph(ALGraph& G)
{
int i = 0;
ArcNode* pMove = NULL;
for (i = 0; i < G.vexnum; i++)
{
printf("\n第%d个顶点为：%c", i + 1, G.vertices.data);
pMove = G.vertices.firstarc;
if (pMove)
{
printf("\n将第%d个顶点作为入度，与其相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
while (pMove)
{
printf("%d ", pMove->adjvex);
pMove = pMove->nextarc;
}
}
else
{
printf("\n将第%d个顶点作为入度，没有与其相邻接的顶点。", i + 1);
}
}
}
https://i-blog.csdnimg.cn/direct/9ed611e0a11d47efa71e6b48c423c021.png
https://i-blog.csdnimg.cn/direct/f1080b765cd748fc98000043e679d8a7.png
接纳毗邻表表现法创建无向网
#include <stdio.h>
#include <stdlib.h>
#define MVNum 100
typedef int OtherInfo; //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef struct ArcNode
{
int adjvex;
struct ArcNode* nextarc;
OtherInfo info;
}ArcNode;//边结点
typedef struct VNode
{
VerTexType data;
ArcNode* firstarc;
}VNode, AdjList;//表头结点
typedef struct
{
AdjList vertices;//存储所有顶点
int vexnum;//顶点总数
int arcnum;//总边数
}ALGraph;//图的信息
void CreateUDN(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
int main()
{
ALGraph G = { {'\0',NULL}, 0,0 };
CreateUDN(G);
printALGraph(G);
return 0;
}
//采用邻接表表示法创建无向网
void CreateUDN(ALGraph& G)
{
int i = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
int j = 0;
ArcNode* p1 = NULL;
ArcNode* p2 = NULL;
int w = 0;
printf("请输入无向网的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入无向网的总边数：");
scanf_s(" %d", &G.arcnum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.vertices.data));
G.vertices.firstarc = NULL; //初始化
}
for (k = 0; k < G.arcnum; k++)
{
printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
printf("请输入第%d条边的权值 : ", k + 1);
scanf_s(" %d", &w, sizeof(OtherInfo));
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = (ArcNode*)malloc(sizeof(ArcNode));
p1->adjvex = j;
p1->info = w;
p1->nextarc = G.vertices.firstarc;
G.vertices.firstarc = p1;//将新结点*p1插入顶点Vi的边表头部
p2 = (ArcNode*)malloc(sizeof(ArcNode));
p2->adjvex = i;
p1->info = w;
p2->nextarc = G.vertices.firstarc;
G.vertices.firstarc = p2;//将与*p1对称的新的边结点*p2插入顶点Vj的边表头部
}
}
//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{
int i = 0;
for (i = 0; i < G.vexnum && (G.vertices.data != v); ++i)
{
;
}
return i;
}
//打印邻接表
void printALGraph(ALGraph& G)
{
int i = 0;
ArcNode* pMove = NULL;
for (i = 0; i < G.vexnum; i++)
{
printf("\n第%d个顶点为：%c", i + 1, G.vertices.data);
pMove = G.vertices.firstarc;
if (pMove)
{
printf("\n与第%d个顶点相邻接的每个顶点在网中的位置（下标值）为：", i + 1);
while (pMove)
{
printf("%d ", pMove->adjvex);
pMove = pMove->nextarc;
}
}
else
{
printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);
}
}
}
https://i-blog.csdnimg.cn/direct/b951b4c2e5224510b4a24690432fc56b.jpeg
https://i-blog.csdnimg.cn/direct/54d4b126d8f94d50a5aa43db1f00ec04.png
接纳毗邻表表现法创建有向网
#include <stdio.h>
#include <stdlib.h>
#define MVNum 100
typedef int OtherInfo; //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef struct ArcNode
{
int adjvex;
struct ArcNode* nextarc;
OtherInfo info;
}ArcNode;//边结点
typedef struct VNode
{
VerTexType data;
ArcNode* firstarc;
}VNode, AdjList;//表头结点
typedef struct
{
AdjList vertices;//存储所有顶点
int vexnum;//顶点总数
int arcnum;//总边数
}ALGraph;//图的信息
void CreateDN(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
int main()
{
ALGraph G = { {'\0',NULL}, 0,0 };
CreateDN(G);
printALGraph(G);
return 0;
}
//采用邻接表表示法创建有向网
void CreateDN(ALGraph& G)
{
int i = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
int j = 0;
ArcNode* p1 = NULL;
ArcNode* p2 = NULL;
int w = 0;
printf("请输入有向网的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入有向网的总边数：");
scanf_s(" %d", &G.arcnum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.vertices.data));
G.vertices.firstarc = NULL; //初始化
}
for (k = 0; k < G.arcnum; k++)
{
printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
printf("请输入第%d条边的权值 : ", k + 1);
scanf_s(" %d", &w, sizeof(OtherInfo));
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = (ArcNode*)malloc(sizeof(ArcNode));
p1->adjvex = j;
p1->info = w;
p1->nextarc = G.vertices.firstarc;
G.vertices.firstarc = p1;//将新结点*p1插入顶点Vi的边表头部
}
}
//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{
int i = 0;
for (i = 0; i < G.vexnum && (G.vertices.data != v); ++i)
{
;
}
return i;
}
//打印邻接表
void printALGraph(ALGraph& G)
{
int i = 0;
ArcNode* pMove = NULL;
for (i = 0; i < G.vexnum; i++)
{
printf("\n第%d个顶点为：%c", i + 1, G.vertices.data);
pMove = G.vertices.firstarc;
if (pMove)
{
printf("\n将第%d个顶点作为出度，与其相邻接的每个顶点在网中的位置（下标值）为：", i + 1);
while (pMove)
{
printf("%d ", pMove->adjvex);
pMove = pMove->nextarc;
}
}
else
{
printf("\n将第%d个顶点作为出度，没有与第%d个顶点相邻接的顶点。", i + 1);
}
}
}
https://i-blog.csdnimg.cn/direct/4c7636161e4049c8a542f2f996edc6fb.png
https://i-blog.csdnimg.cn/direct/b38b1be5c20b401a874c32c411af1616.png
创建有向网的逆毗邻表
#include <stdio.h>
#include <stdlib.h>
#define MVNum 100
typedef int OtherInfo; //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef struct ArcNode
{
int adjvex;
struct ArcNode* nextarc;
OtherInfo info;
}ArcNode;//边结点
typedef struct VNode
{
VerTexType data;
ArcNode* firstarc;
}VNode, AdjList;//表头结点
typedef struct
{
AdjList vertices;//存储所有顶点
int vexnum;//顶点总数
int arcnum;//总边数
}ALGraph;//图的信息
void CreateDN(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
int main()
{
ALGraph G = { {'\0',NULL}, 0,0 };
CreateDN(G);
printALGraph(G);
return 0;
}
//创建有向网的逆邻接表
void CreateDN(ALGraph& G)
{
int i = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
int j = 0;
ArcNode* p1 = NULL;
ArcNode* p2 = NULL;
int w = 0;
printf("请输入有向网的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入有向网的总边数：");
scanf_s(" %d", &G.arcnum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.vertices.data));
G.vertices.firstarc = NULL; //初始化
}
for (k = 0; k < G.arcnum; k++)
{
printf("请输入第%d条边依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
printf("请输入第%d条边的权值 : ", k + 1);
scanf_s(" %d", &w, sizeof(OtherInfo));
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = (ArcNode*)malloc(sizeof(ArcNode));
p1->adjvex = i;
p1->info = w;
p1->nextarc = G.vertices.firstarc;
G.vertices.firstarc = p1;//将新结点*p1插入顶点Vj的边表头部
}
}
//在G的顶点表vexs中获取字符v的下标（数组G.vexs的下标从0开始）
int LocateVex(ALGraph& G, VerTexType v)
{
int i = 0;
for (i = 0; i < G.vexnum && (G.vertices.data != v); ++i)
{
;
}
return i;
}
//打印逆邻接表
void printALGraph(ALGraph& G)
{
int i = 0;
ArcNode* pMove = NULL;
for (i = 0; i < G.vexnum; i++)
{
printf("\n第%d个顶点为：%c", i + 1, G.vertices.data);
pMove = G.vertices.firstarc;
if (pMove)
{
printf("\n将第%d个顶点作为入度，与其相邻接的每个顶点在网中的位置（下标值）为：", i + 1);
while (pMove)
{
printf("%d ", pMove->adjvex);
pMove = pMove->nextarc;
}
}
else
{
printf("\n将第%d个顶点作为入度，没有与第%d个顶点相邻接的顶点。", i + 1);
}
}
}
https://i-blog.csdnimg.cn/direct/3571a14a8f5c467ab98d721acd7f2bc1.png
6.4.3 十字链表
接纳十字链表表现法创建有向图
//采用十字链表表示法创建有向图
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM20
typedef int InfoType; //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef struct ArcBox
{
int tailvext;
int headvex;
struct ArcBox* hlink;
struct ArcBox* tlink;
InfoType *info;
}ArcBox;
typedef struct VexNode
{
VerTexType data;
ArcBox *firstin;
ArcBox *firstout;
}VexNode;
typedef struct
{
VexNode xlist;//表头向量
int vexnum;//顶点总数
int arcnum;//总边数
}OLGraph;//图的信息
void CreateOLGraph(OLGraph& G);
int LocateVex(OLGraph& G, VerTexType v);
void printOLGraph(OLGraph& G);
int main()
{
OLGraph G = { {'\0',NULL,NULL}, 0,0 };
CreateOLGraph(G);
printOLGraph(G);
return 0;
}
//采用十字链表表示法创建有向图
void CreateOLGraph(OLGraph& G)
{
int i = 0;
int j = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
ArcBox* p1 = NULL;
printf("请输入有向图的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入有向图的总边数：");
scanf_s(" %d", &G.arcnum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.xlist.data));
G.xlist.firstin = NULL;
G.xlist.firstout = NULL;//初始化
}
for (k = 0; k < G.arcnum; k++)
{
printf("请输入第%d条弧依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
//起点v1是弧尾，终点v2是弧头
//弧<v1,v2>是v1的出度，是v2的入度
i = LocateVex(G, v1);
j = LocateVex(G, v2);
//起点v1是弧尾，下标值为i；终点v2是弧头，下标值为j
//弧<v1,v2>是第i+1个顶点的出度firstout，是第j+1个顶点的入度firstin
p1 = (ArcBox*)malloc(sizeof(ArcBox));
p1->tailvext = i;//起点v1是弧尾，下标值为i
p1->headvex = j; //终点v2是弧头，下标值为j
//p1弧结点中的链域tlink指向与其弧尾tailvext相同的下一条弧（即指向第i+1个顶点v1的下一个出度firstout）
p1->tlink = G.xlist.firstout;//p1指向的弧<v1,v2>是第i+1个顶点v1的出度firstout
G.xlist.firstout = p1; //前插法将p1插入到第i+1个顶点v1的出度单链表中
//p1弧结点中的链域hlink指向与其弧头headvex相同的下一条弧（即指向第j+1个顶点v2的下一个入度firstin）
p1->hlink = G.xlist.firstin; //p1指向的弧<v1,v2>是第j+1个顶点v2的入度firstin
G.xlist.firstin = p1;//前插法将p1插入到第j+1个顶点v2的入度单链表中
}
}
//在G的顶点表xlist中获取字符v的下标（数组G.xlist的下标从0开始）
int LocateVex(OLGraph& G, VerTexType v)
{
int i = 0;
for (i = 0; i < G.vexnum && (G.xlist.data != v); ++i)
{
;
}
return i;
}
//打印十字链表
void printOLGraph(OLGraph& G)
{
int i = 0;
ArcBox* pMoveIn = NULL;
ArcBox* pMoveOut = NULL;
for (i = 0; i < G.vexnum; i++)
{
printf("\n第%d个顶点为：%c", i + 1, G.xlist.data);
pMoveOut = G.xlist.firstout;
if (pMoveOut)
{
printf("\n将第%d个顶点作为出度，与其相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
while (pMoveOut)
{
printf("%d ", pMoveOut->headvex);
pMoveOut = pMoveOut->tlink;
}
}
else
{
printf("\n将第%d个顶点作为出度，没有与其相邻接的顶点。", i + 1);
}
pMoveIn = G.xlist.firstin;
if (pMoveIn)
{
printf("\n将第%d个顶点作为入度，与其相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
while (pMoveIn)
{
printf("%d ", pMoveIn->tailvext);
pMoveIn = pMoveIn->hlink;
}
}
else
{
printf("\n将第%d个顶点作为入度，没有与其相邻接的顶点。", i + 1);
}
}
}
https://i-blog.csdnimg.cn/direct/d1b1d2af022242a290e738f7dc81823f.png
https://i-blog.csdnimg.cn/direct/7704c40bda5d41e1b33f00aa6d32b637.png
该有向图的毗邻矩阵，其中各行、各列中不为0的元素，与其十字链表每个顶点的出度、入度效果有对应关系。
https://i-blog.csdnimg.cn/direct/0a4c60a613874760b0867f8d110cab34.png
接纳十字链表表现法创建有向网
输入并读取权值，赋值到 弧结点 ArcBox 布局中的 info 成员即可。
//采用十字链表表示法创建有向网
void CreateOLGraph(OLGraph& G)
{
int i = 0;
int j = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
ArcBox* p1 = NULL;
int* w = 0;
printf("请输入有向网的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入有向网的总边数：");
scanf_s(" %d", &G.arcnum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.xlist.data));
G.xlist.firstin = NULL;
G.xlist.firstout = NULL;//初始化
}
for (k = 0; k < G.arcnum; k++)
{
printf("请输入第%d条弧依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
printf("请输入第%d条边的权值 : ", k + 1);
scanf_s(" %d", w, sizeof(InfoType));//在ArcBox中，info由指向int的指针定义
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = (ArcBox*)malloc(sizeof(ArcBox));
p1->tailvext = i;
p1->headvex = j;
p1->info = w;//赋值到弧结点p1中的info成员
p1->tlink = G.xlist.firstout;
G.xlist.firstout = p1;
p1->hlink = G.xlist.firstin;
G.xlist.firstin = p1;
}
}
6.4.4 毗邻多重表
接纳毗邻多重表表现法创建无向图
//采用邻接多重表表示法创建无向图
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM20
typedef enum {unvisited,visited} VisitIf;
typedef int InfoType; //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef struct EBox
{
VisitIf mark;
int ivex;
int jvex;
struct EBox* ilink;
struct EBox* jlink;
InfoType *info;
}EBox;
typedef struct VexBox
{
VerTexType data;
EBox* firstedge;
}VexBox;
typedef struct
{
VexBox adjmulist;//表头向量
int vexnum;//顶点总数
int edgenum;//总边数
}AMLGraph;//图的信息
void CreateAMLGraph(AMLGraph& G);
int LocateVex(AMLGraph& G, VerTexType v);
void printAMLGraph(AMLGraph& G);
int main()
{
AMLGraph G = { {'\0',NULL,NULL}, 0,0 };
CreateAMLGraph(G);
printAMLGraph(G);
return 0;
}
//采用邻接多重表表示法创建无向图
void CreateAMLGraph(AMLGraph& G)
{
int i = 0;
int j = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
EBox* p1 = NULL;
printf("请输入无向图的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入无向图的总边数：");
scanf_s(" %d", &G.edgenum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.adjmulist.data));
G.adjmulist.firstedge = NULL;//初始化
}
for (k = 0; k < G.edgenum; k++)
{
printf("请输入第%d条弧依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = (EBox*)malloc(sizeof(EBox));
p1->ivex = i;
p1->jvex = j;
p1->ilink = G.adjmulist.firstedge;
G.adjmulist.firstedge = p1;
p1->jlink = G.adjmulist.firstedge;
G.adjmulist.firstedge = p1;
}
}
//在G的顶点表adjmulist中获取字符v的下标（数组G.xlist的下标从0开始）
int LocateVex(AMLGraph& G, VerTexType v)
{
int i = 0;
for (i = 0; i < G.vexnum && (G.adjmulist.data != v); ++i)
{
;
}
return i;
}
//打印邻接多重表
void printAMLGraph(AMLGraph& G)
{
int i = 0;
EBox* pMove = NULL;
for (i = 0; i < G.vexnum; i++)
{
printf("\n第%d个顶点为：%c", i + 1, G.adjmulist.data);
pMove = G.adjmulist.firstedge;
if (pMove)
{
printf("\n与第%d个顶点相邻接的每个顶点在图中的位置（下标值）为：", i + 1);
while (pMove)
{
if (pMove->ivex == i)
{
printf("%d ", pMove->jvex);
pMove = pMove->ilink;
}
else if (pMove->jvex == i)
{
printf("%d ", pMove->ivex);
pMove = pMove->jlink;
}
}
}
else
{
printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);
}
}
}
https://i-blog.csdnimg.cn/direct/70076410dc2a4fd6a0ab9ec5f4b24496.png
https://i-blog.csdnimg.cn/direct/7f736d0998f54953b696fbea69bbe318.png
https://i-blog.csdnimg.cn/direct/d7a9dfb6b9384790808f1cdba5534974.png
接纳毗邻多重表表现法创建无向网
输入并读取权值，赋值到 边结点 EBox 布局中的 info 成员即可。
//采用邻接多重表表示法创建无向网
void CreateAMLGraph(AMLGraph& G)
{
int i = 0;
int j = 0;
int k = 0;
VerTexType v1 = 0;
VerTexType v2 = 0;
EBox* p1 = NULL;
int* w = 0;
printf("请输入无向网的总顶点数：");
scanf_s(" %d", &G.vexnum);
printf("请输入无向网的总边数：");
scanf_s(" %d", &G.edgenum);
for (i = 0; i < G.vexnum; ++i)
{
printf("请输入第%d个顶点的值：", i + 1);
scanf_s(" %c", &(G.adjmulist.data));
G.adjmulist.firstedge = NULL;//初始化
}
for (k = 0; k < G.edgenum; k++)
{
printf("请输入第%d条弧依附的两个顶点（用空格间隔，输入结束后按回车）: ", k + 1);
scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));
printf("请输入第%d条边的权值 : ", k + 1);
scanf_s(" %d", w, sizeof(InfoType));//在EBox中，info由指向int的指针定义
i = LocateVex(G, v1);
j = LocateVex(G, v2);
p1 = (EBox*)malloc(sizeof(EBox));
p1->ivex = i;
p1->jvex = j;
p1->info = w; //赋值到边结点p1中的info成员
p1->ilink = G.adjmulist.firstedge;
G.adjmulist.firstedge = p1;
p1->jlink = G.adjmulist.firstedge;
G.adjmulist.firstedge = p1;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]