(1) 文件1: pubuse.h 是公共使用的常量定义和系统函数调用声明。
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等*/
#include<limits.h> /* INT_MAX 等*/
#include<stdio.h> /* EOF(=^Z 或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码,如OK 等*/
typedef int Boolean; /* Boolean 是布尔类型,其值是TRUE 或FALSE */
2)文件GraphDef.h定义了图的邻接矩阵表示类型和邻接表表示类型,该头文件在下面的程序中都会使用到,其代码如下:
#define MAXV 100 //最大顶点个数
//以下定义类型
typedef struct
{
int no; //顶点编号
InfoType info; //顶点其他信息,这里用于存放边的权值
}VertexType; //顶点类型
typedef struct //图的定义
{
int edges[MAXV][MAXV]; //邻接矩阵
int n, e; //顶点数、弧数
VertexType vex[MAXV]; //存放顶点信息
}MGraph; //图的邻接矩阵类型
//以下定义邻接表类型
typedef struct Anode //弧的结点结构类型
{
int adjvex; //该弧的终点位置
struct Anode* nextarc; //指向下一条弧的指针
InfoType info; //该弧的相关信息,这里用于存放权值
}ArcNode;
typedef int Vertex;
typedef struct Vnode //邻接表头结点的类型
{
Vertex data; //顶点信息
ArcNode* firstarc; //指向第一条弧
}VNode;
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{
AdjList adjlist; //邻接表
int n, e; //图中顶点数n和边数e
}ALGraph; //图的邻接表类型
(3)头文件GraphAlgo4-1.h包含若干图的操作函数
1.将邻接矩阵转化为邻接表
#define INF 32767 //INF表示
void MatToList(MGraph g, ALGraph *&G) //将邻接矩阵g转换成邻接表G
{
int i, j, n = g.n; // n为顶点数
ArcNode* p;
G = (ALGraph*)malloc(sizeof(ALGraph));
for (i = 0; i < n; i++) //给邻接表中所有头结点的指针域置初值
G->adjlist[i].firstarc = NULL;
for (i = 0; i < n; i++) //检查邻接矩阵中每个元素
for (j = n - 1; j >= 0; j--)
if (g.edges[i][j] != 0) //邻接矩阵的当前元素不为0
{
p = (ArcNode*)malloc(sizeof(ArcNode)); //创建一个结点*p
p->adjvex = j;
p->info = g.edges[i][j]; //存放边的权值
p->nextarc = G->adjlist[i].firstarc; //将*p插入到链表中,头插法
G->adjlist[i].firstarc = p;
}
G->n = g.n;
G->e = g.e;
}
2.将邻接表转化为邻接矩阵
void ListToMat(ALGraph* G, MGraph& g) //将邻接表G转换成邻接矩阵g
{
int i, j, n = G->n;
ArcNode* p;
for (i = 0; i < n; i++) //g.edges[i][j]赋初值0
for (j = n - 1; j >= 0; j--)
g.edges[i][j] = 0;
for (i = 0; i < n; i++)
{
p = G->adjlist[i].firstarc;
while (p != NULL) //对所有相邻顶点进行处理
{
g.edges[i][p->adjvex] = p->info;
p = p->nextarc;
}
}
g.n = n;
g.e = G->e;
}
3.进行邻接矩阵与邻接表的输出
void DispMat(MGraph g) //输出邻接矩阵g
{
int i, j;
for (i = 0; i < g.n; i++)
{
for (j = 0; j < g.n; j++)
if (g.edges[i][j] == INF)
printf("%3s:" , "#");
else
printf("%3d", g.edges[i][j]);
printf("\n");
}
}
void DispAdj(ALGraph* G) //输出邻接表G
{
int i;
ArcNode* p;
for (i = 0; i < G->n; i++)
{
p = G->adjlist[i].firstarc;
if (p != NULL)
printf("%3d:", i);
while (p != NULL) //对所有相邻顶点进行处理
{
printf("%3d",p->adjvex);//应该输出每个邻接表的顶点数据
p = p->nextarc;
}
printf("\n");
}
}
(3)源程序exp4-1.cpp 实现图的操作函数的测试文件。
#include “pubuse.h”
#include “GraphDef.h”
#include “GraphAlgo.h”
void main()
{
int i, j;
MGraph g,g1;
ALGraph* G;
printf("建立一个有向图:\n"); //自己设计一个有向图
printf("输入有向图的顶点数:");
scanf_s("%d", &g.n);
printf("建立 %d * %d的矩阵:\n", g.n, g.n);
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
{
printf("输入顶点 % d到顶点 % d的权值, 无弧的用0表示:\n",i,j);
scanf_s("%d", &g.edges[i][j]); //用矩阵存储两顶点弧上的权值
}
g.e = 0;
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
if (g.edges[i][j] != 0)
g.e++;
printf("有向图G的邻接矩阵:\n");
DispMat(g);
G = (ALGraph*)malloc(sizeof(ALGraph));
printf("图的邻接矩阵转换成邻接表:\n");
MatToList(g, G);
DispAdj(G);
printf("图G的邻接表转换成邻接矩阵:\n");
ListToMat(G, g1);
DispMat(g1);
printf("\n");
}
运行代码如下所示:文章来源:https://www.toymoban.com/news/detail-505931.html
文章来源地址https://www.toymoban.com/news/detail-505931.html
到了这里,关于邻接矩阵与邻接表的输出及其相互转换的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!