（1) 文件1：?pubuse.h 是公共使用的常量定義和系統(tǒng)函數(shù)調(diào)用聲明。
#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() */
/* 函數(shù)結(jié)果狀態(tài)代碼*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; /* Status 是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK 等*/
typedef int Boolean; /* Boolean 是布爾類型,其值是TRUE 或FALSE */2)文件GraphDef.h定義了圖的鄰接矩陣表示類型和鄰接表表示類型，該頭文件在下面的程序中都會(huì)使用到，其代碼如下：
#define MAXV 100 //最大頂點(diǎn)個(gè)數(shù)
//以下定義類型
typedef struct
{
int no; //頂點(diǎn)編號(hào)
InfoType info; //頂點(diǎn)其他信息，這里用于存放邊的權(quán)值
}VertexType; //頂點(diǎn)類型
typedef struct //圖的定義
{
int edges[MAXV][MAXV]; //鄰接矩陣
int n, e; //頂點(diǎn)數(shù)、弧數(shù)
VertexType vex[MAXV]; //存放頂點(diǎn)信息
}MGraph; //圖的鄰接矩陣類型
//以下定義鄰接表類型
typedef struct Anode //弧的結(jié)點(diǎn)結(jié)構(gòu)類型
{
int adjvex; //該弧的終點(diǎn)位置
struct Anode* nextarc; //指向下一條弧的指針
InfoType info; //該弧的相關(guān)信息，這里用于存放權(quán)值
}ArcNode;
typedef int Vertex;
typedef struct Vnode //鄰接表頭結(jié)點(diǎn)的類型
{
Vertex data; //頂點(diǎn)信息
ArcNode* firstarc; //指向第一條弧
}VNode;
typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型
typedef struct
{
AdjList adjlist; //鄰接表
int n, e; //圖中頂點(diǎn)數(shù)n和邊數(shù)e
}ALGraph; //圖的鄰接表類型（3）頭文件GraphAlgo4-1.h包含若干圖的操作函數(shù)
1.將鄰接矩陣轉(zhuǎn)化為鄰接表
#define INF 32767 //INF表示
void MatToList(MGraph g, ALGraph *&G) //將鄰接矩陣g轉(zhuǎn)換成鄰接表G
{
int i, j, n = g.n; // n為頂點(diǎn)數(shù)
ArcNode* p;
G = (ALGraph*)malloc(sizeof(ALGraph));
for (i = 0; i < n; i++) //給鄰接表中所有頭結(jié)點(diǎn)的指針域置初值
G->adjlist[i].firstarc = NULL;
for (i = 0; i < n; i++) //檢查鄰接矩陣中每個(gè)元素
for (j = n - 1; j >= 0; j--)
if (g.edges[i][j] != 0) //鄰接矩陣的當(dāng)前元素不為0
{
p = (ArcNode*)malloc(sizeof(ArcNode)); //創(chuàng)建一個(gè)結(jié)點(diǎn)*p
p->adjvex = j;
p->info = g.edges[i][j]; //存放邊的權(quán)值
p->nextarc = G->adjlist[i].firstarc; //將*p插入到鏈表中，頭插法
G->adjlist[i].firstarc = p;
}
G->n = g.n;
G->e = g.e;
}2.將鄰接表轉(zhuǎn)化為鄰接矩陣
void ListToMat(ALGraph* G, MGraph& g) //將鄰接表G轉(zhuǎn)換成鄰接矩陣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) //對(duì)所有相鄰頂點(diǎn)進(jìn)行處理
{
g.edges[i][p->adjvex] = p->info;
p = p->nextarc;
}
}
g.n = n;
g.e = G->e;
}?3.進(jìn)行鄰接矩陣與鄰接表的輸出
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) //對(duì)所有相鄰頂點(diǎn)進(jìn)行處理
{
printf("%3d",p->adjvex);//應(yīng)該輸出每個(gè)鄰接表的頂點(diǎn)數(shù)據(jù)
p = p->nextarc;
}
printf("\n");
}
}(3)源程序exp4-1.cpp 實(shí)現(xiàn)圖的操作函數(shù)的測(cè)試文件。
#include “pubuse.h”
#include “GraphDef.h”
#include “GraphAlgo.h”
void main()
{
int i, j;
MGraph g,g1;
ALGraph* G;
printf("建立一個(gè)有向圖：\n"); //自己設(shè)計(jì)一個(gè)有向圖
printf("輸入有向圖的頂點(diǎn)數(shù)：");
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("輸入頂點(diǎn) % d到頂點(diǎn) % d的權(quán)值, 無弧的用0表示:\n",i,j);
scanf_s("%d", &g.edges[i][j]); //用矩陣存儲(chǔ)兩頂點(diǎn)弧上的權(quán)值
}
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("圖的鄰接矩陣轉(zhuǎn)換成鄰接表:\n");
MatToList(g, G);
DispAdj(G);
printf("圖G的鄰接表轉(zhuǎn)換成鄰接矩陣:\n");
ListToMat(G, g1);
DispMat(g1);
printf("\n");
}運(yùn)行代碼如下所示：文章來源：http://www.zghlxwxcb.cn/news/detail-505931.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-505931.html
到了這里，關(guān)于鄰接矩陣與鄰接表的輸出及其相互轉(zhuǎn)換的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
