数据结构采用邻接矩阵构造无向网G.doc

实验目的
采用数组（邻接矩阵）表示法，构造无向网G

实验内容

编程序并上机调试运行。

采用数组（邻接矩阵）表示法，构造无向网G

编写程序

//采用邻接矩阵表示法，构造无向网G

#define MAX_VERTEX_NUM 20 //最大顶点个数
#include<stdio.h>
//typedef enum {DG,DN,UDG,UDN} Graphkind;
typedef struct ArcCell{
int adj;
// int *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
int vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
//GraphKind kind;
}MGraph;

int CreateUDN(MGraph G){
int i,j,k,v1,v2,w;
printf("请输入顶点数和边数(中间用逗号隔开)：\n");
scanf("%d,%d",&G.vexnum ,&G.arcnum );

for(i=0;i<G.vexnum ;i++)
{printf("请输入顶点信息：");
scanf("%d",&G.vexs[i]);
getchar();
}

for(i=0;i<G.vexnum ;++i) //初始化邻接矩阵
for(j=0;j<G.vexnum ;++j)
{G.arcs[i][j].adj =0;
// G.arcs[i][j].info =NULL;
}

for(k=0;k<G.arcnum ;++k){ //构造邻接矩阵
printf("请输入边和权值(输入格式为:i,j,w)：\n");
scanf("%d,%d,%d",&v1,&v2,&w);
getchar();
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
//if(IncInfo) Input(*G.arcs[i][j].info);
G.arcs[j][i].adj =G.arcs[i][j].adj ;
}
//输出
printf("\n");
printf("****************************************\n");
printf("输出：\n");
for(i=0;i<G.vexnum ;i++)
{
for(j=0;j<G.vexnum ;j++)
printf("%4d",G.arcs[i][j].adj );
printf("\n");
}
printf("****************************************\n");
return 0;
}

//LocateVex函数
int LocateVex(MGraph G,int ver){
int i;
for(i=0;i<G.vexnum;++i)
if(G.vexs[i]==ver)
return i;
}

//main函数
int main()
{
MGraph G;
CreateUDN(G);

return 0;
}
运行程序：

输入6个顶点和10条边，依次输入以上权值<1,2,6> <1,3,1> <1,4,5> <2,3,5> <2,5,3> <3,4,5> <3,5,6> <3,6,4> <4,6,2> <5,6,6> 然后输出矩阵表，可以看到其权值是对应的。

程序解析：
1.编写头文件，定义最大顶点个数为20个.

定义权值类型为int型，顶点和弧数为int型。顶点类型为int型。

2. 编写函数CreateUDN。

先用一个scanf获得用户的顶点数和边数输入，类型为整型。然后用一个for语句将0到顶点数的顶点信息输入，然后初始化邻接矩阵，用内外循环将矩阵都初始化为最大值，最大值默认为0.让其每一位的初始值都为0.
然后构造邻接矩阵，用一个for函数实现邻接矩阵数据的输入，对应到行和列。用scanf获得用户输入，类型为整型。然后i和j调用LocateVex函数。使矩阵对应的值为权值，然后进行对称弧的定义。

输出矩阵。先内循环输出横向的权值，在外循环输出竖向的权值。

3.编写LocateVex函数。

设ver为int型，用一个for语句实现循环，从0到顶点数，若顶点等于ver则返回第几个顶点i.

4.建立main函数。

Main函数直接调用CreateUDN函数。