数据结构大纲答案6
实验编号：年 12 月 25 日 计算机科学学院 2014级 1班实验名称：图及其应用
姓名：陈元玲 学号：2014110105 指导老师：刘芳实验成绩：______ 一. 目的要求：
（1） 通过完成本实验，掌握图的两种基本的存储结构（邻接矩阵、邻接表），以及图
的基本算法实现（建立、遍历），并能运用图结构分析解决一些实际问题。
（2） 本实验训练的要点是：图的两种基本存储结构，及各种操作的算法实现（建立、
遍历、图的典型应用）。
二. 实验内容：
（1） 建立无向图和有向图的邻接矩阵存储，计算顶点的度，并输出图的基本信息。
//1.h
#include
#include
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedefint Status;
//2.h
#define INIFINITY 1000 // 最大值
//最大顶点数 #define MAX_VERTEX_NUM 20
typedefenum{DG,DN,UDG,UDN} GraphKind; //图的四种类型
typedef char VertexType;
typedefstruct {
VertexTypevexs[MAX_VERTEX_NUM]; //顶点向量
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
intvexnum,arcnum;
GraphKind kind;
}MGraph; //顶点数和弧的数目 //图的种类
//3.h
intLovateVex(MGraphG,VertexType v){
for (int i=0;G.vexs[i]!=v;i++);
return i;
}
Status CreateUDN(MGraph&G){
inti,j,k;
VertexType v1,v2;
int w;
cout
cin>>G.vexnum>>G.arcnum;
cout
for (i=0;i>G.vexs[i];
for (i=0;i
for (j=0;j
cout
for (k=0;k
cin>>v1;
cin>>v2; cin>>w;
i=LovateVex(G,v1);
j=LovateVex(G,v2); G.arcs[i][j]=w;
G.arcs[j][i]=G.arcs[i][j];
}//for k
return OK;
}//CreateUDN
Status CreateDN(MGraph&G){
inti,j,k;
VertexType v1,v2;
int w;
cout
cin>>G.vexnum>>G.arcnum;
cout
for (i=0;i>G.vexs[i];
for (i=0;i
for (j=0;j
cout
for (k=0;k
cin>>v1;
cin>>v2; cin>>w;
i=LovateVex(G,v1);
}//for k
return OK;
}//CreateDN
Status CreateUDG(MGraph&G){
inti,j,k;
VertexType v1,v2;
int w;
cout
cin>>G.vexnum>>G.arcnum;
cout
for (i=0;i>G.vexs[i];
for (i=0;i
for (j=0;j
cout
for (k=0;k
cin>>v1;
cin>>v2;
i=LovateVex(G,v1);
j=LovateVex(G,v2); G.arcs[i][j]=1;
G.arcs[j][i]=G.arcs[i][j];
}//for k
return OK;
}//CreateUDG
Status CreateDG(MGraph&G){
inti,j,k;
VertexType v1,v2;
int w;
cout
cin>>G.vexnum>>G.arcnum;
cout
for (i=0;i>G.vexs[i];
for (i=0;i
for (j=0;j
cout
for (k=0;k
cin>>v1;
cin>>v2;
i=LovateVex(G,v1);
}//for k
return OK;
}//CreateDG
Status CreateGraph(MGraph&G){
int kind;
cout
cin>>kind;
G.kind=(GraphKind)kind;
switch (G.kind){
case DG
case DN :return CreateDG(G); :return CreateDN(G); j=LovateVex(G,v2); G.arcs[i][j]=1;
case UDG :return CreateUDG(G);
case UDN :return CreateUDN(G);
default :return ERROR;
}
}//CreateGraph
voidPrintGraph(MGraph G){
inti,j;
cout
cout
cout
for (i=0;i
cout
for (i=0;i
cout
}//for i
cout
}
voidGraphDegree(MGraph G){
intindegree[MAX_VERTEX_NUM]={0},outdegree[MAX_VERTEX_NUM]={0}; int i;
switch (G.kind){
case DN :
case DG :FindIndegree(G,indegree);
for (i=0;i
case UDN :
case UDG :FindOutdegree(G,outdegree);
}
cout
}//GraphDegree
//main.cpp
#include "1.h"
#include "2.h"
#include "3.h"
void main(){
MGraph G;
CreateGraph(G); //创建图 for (i=0;i
PrintGraph(G); //输出图
GraphDegree(G); //计算图中顶点的度，并输出
cout
}
（2） 建立有向图的邻接表存储表示，并根据存储计算顶点的出度和入度，然后输
出图的基本信息。
//1.h
#include
#include
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedefint Status;
#define INIFINITY 1000 // 最大值
//最大顶点数 #define MAX_VERTEX_NUM 20
typedefenum{DG,DN,UDG,UDN} GraphKind; //图的四种类型 typedef char VertexType;
typedefintInfoType;
typedefstructArcNode{
intadjvex;
InfoType weight;
structArcNode *nextarc;
}ArcNode;
typedefstructVnode{
VertexType data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM ];
typedefstruct {
AdjList vertices;
intvexnum,arcnum;
GraphKind kind;
}ALGraph;
//3.h
intLovateVex(ALGraphG,VertexType v){
for (int i=0;G.vertices[i].data!=v;i++);
return i;
}
Status CreateUDN(ALGraph&G){
inti,j,k;
VertexType v1,v2;
InfoType w;
ArcNode *p,*q;
cout
cin>>G.vexnum>>G.arcnum;
cout
for (i=0;i
}
cout
cin>>v1;
cin>>v2; cin>>w; i=LovateVex(G,v1); j=LovateVex(G,v2); p=(ArcNode *)malloc (sizeof(ArcNode )); p->adjvex=j; p->weight=w; p->nextarc=G.vertices[i].firstarc; cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL;
G.vertices[i].firstarc=p;
q=(ArcNode *)malloc (sizeof(ArcNode ));
q->adjvex=i; q->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=q;
}//for k
return OK;
}//CreateUDN
Status CreatDN(ALGragh&G){
Status CreateGraph(ALGraph&G){
int kind;
cout
G.kind=(GraphKind)kind;
switch (G.kind){
//case DG
case DN :return CreateDG(G); :return CreateDN(G);
// case UDG :return CreateUDG(G);
case UDN :return CreateUDN(G);
default :return ERROR;
}
}//CreateGraph
voidPrintGraph(ALGraph G){
inti,j;
ArcNode *p;
cout
cout
for (i=0;i
for (i=0;i
coutadjvex; coutnextarc; }//while cout
}//for
cout
}
//main.cpp
#include "1.h"
#include "3.h"
void main(){
ALGraph G;
CreateGraph(G); //建立图 PrintGraph(G); //输出图
}
三．结果及分析 1.
2.