数据结构大纲答案6

实验编号：年 12 月 25 日计算机科学学院 2014级 1班实验名称：图及其应用

姓名：陈元玲学号：2014110105 指导老师：刘芳实验成绩：______ 一. 目的要求：

（1）通过完成本实验，掌握图的两种基本的存储结构（邻接矩阵、邻接表），以及图

的基本算法实现（建立、遍历），并能运用图结构分析解决一些实际问题。

（2）本实验训练的要点是：图的两种基本存储结构，及各种操作的算法实现（建立、

遍历、图的典型应用）。

二. 实验内容：

（1）建立无向图和有向图的邻接矩阵存储，计算顶点的度，并输出图的基本信息。

//1.h

#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

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

#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

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.

数据结构大纲答案6

相关文章