数据结构实验报告
数据结构实验报告
第 6 次实验
学号：[1**********] 姓名：叶佳伟
一、实验目的
1、复习图的逻辑结构、存储结构及基本操作；
2、掌握邻接矩阵、邻接表及图的创建、遍历；
3、了解图的应用。
二、实验内容
1、（必做题）假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作：
（ 1）构造图（包括有向图、有向网、无向图、无向网）；
（ 2）根据深度优先遍历图；
（ 3）根据广度优先遍历图。
三、算法描述
（采用自然语言描述）
四、详细设计
（画出程序流程图）
五、程序代码
（给出必要注释）
#include
#include
#include
#include
#include
#define INFINITY 255678 /*赋初值用*/
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
enum {DG, DN, UDG, UDN};
typedef struct ArcCell
{
int adj;/*顶点关系类型, 对无权图, 用1(是) 或0(否) 表示相邻否; 对带权图, 则为权值*/ char *info;/*弧相关信息指针*/
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/
AdjMatrix arcs; /*邻接矩阵*/
int vexnum, arcnum;/*图的当前顶点数和弧数*/
int kind;
}MGraph;
void CreateDG(MGraph *G);
void CreateDN(MGraph *G);
void CreateUDG(MGraph *G);
void CreateUDN(MGraph *G);
int LocateVex(MGraph *G, char v[]);
void print(MGraph *G);
int main(void)
{
MGraph *G;
G = (MGraph *)malloc(sizeof(MGraph));
printf("请选者 0-有向图,1-有向网,2-无向图,3-无向网 : ");
scanf("%d", &G->kind);
switch(G->kind)
{
case DG :
CreateDG(G);
print(G);
break;
case DN :
CreateDN(G);
print(G);
break;
case UDG :
CreateUDG(G);
print(G);
break;
case UDN :
CreateUDN(G);
print(G);
break;
default :
break;
}
getch();
}
/*建立有向图*/
void CreateDG(MGraph *G)
{
int i, j, k;
char v1[5], v2[5];
printf("输入顶点数和弧数 : ");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar();
for(i = 0; i vexnum; i++)
{
scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/ }
for(i = 0; i vexnum; i++)
{
for(j = 0; j vexnum; j++) /*赋初值*/
{
G->arcs[i][j].adj = INFINITY;
G->arcs[i][j].info = NULL;
}
}
for(k = 0; k arcnum; k++)
{
scanf("%s%s", v1, v2); /*输入一条边依附的顶点和权值*/
i = LocateVex(G, v1); /*确定v1和v2在G 中位置*/ j = LocateVex(G, v2);
G->arcs[i][j].adj = 1; /*弧的权值赋值*/
}
}
/*建立有向网*/
void CreateDN(MGraph *G)
{
int i, j, k, w;
char v1[5], v2[5];
printf("输入顶点数和弧数 : ");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar();
for(i = 0; i vexnum; i++)
{
scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/ }
for(i = 0; i vexnum; i++)
{
for(j = 0; j vexnum; j++) /*赋初值*/
{
G->arcs[i][j].adj = INFINITY;
G->arcs[i][j].info = NULL;
}
}
for(k = 0; k arcnum; k++)
{
scanf("%s%s%d", v1, v2, &w); /*输入一条边依附的顶点和权值*/
i = LocateVex(G, v1); /*确定v1和v2在G 中位置*/ j = LocateVex(G, v2);
G->arcs[i][j].adj = w; /*弧的权值赋值*/
}
}
/*建立无向图*/
void CreateUDG(MGraph *G)
{
int i, j, k;
char v1[5],v2[5];
printf("输入顶点数和弧数 : ");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar();
for(i = 0; i vexnum; i++)
{
scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/
for(i = 0; i vexnum; i++)
{
for(j = 0; j vexnum; j++) /*赋初值*/
{
G->arcs[i][j].adj = INFINITY;
G->arcs[i][j].info = NULL;
}
}
for(k = 0; k arcnum; k++)
{
scanf("%s%s", v1, v2); /*输入一条边依附的顶点和权值*/
i = LocateVex(G, v1); /*确定v1和v2在G 中位置*/ j = LocateVex(G, v2);
G->arcs[i][j].adj = 1; /*弧的权值赋值*/
G->arcs[j][i].adj=G->arcs[i][j].adj;/*置对称弧*/
}
}
/*建立无向网*/
void CreateUDN(MGraph *G)
{
int i, j, k, w;
char v1[5], v2[5];
printf("输入顶点数和弧数 : ");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar();
for(i = 0; i vexnum; i++)
{
scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/ }
for(i = 0; i vexnum; i++)
{
for(j = 0; j vexnum; j++) /*赋初值*/
{
G->arcs[i][j].adj = INFINITY;
G->arcs[i][j].info = NULL;
}
for(k = 0; k arcnum; k++)
{
scanf("%s%s%d", v1, v2, &w); /*输入一条边依附的顶点和权值*/
i = LocateVex(G, v1); /*确定v1和v2在G 中位置*/ j = LocateVex(G, v2);
G->arcs[i][j].adj = w; /*弧的权值赋值*/
G->arcs[j][i].adj=G->arcs[i][j].adj;/*置对称弧*/
}
}
int LocateVex(MGraph *G, char v[])
{
int k;
for(k = 0; k vexnum; k++)
{
if(strcmp(G->vexs[k], v) == 0)
break;
}
return k;
}
/*打印矩阵*/
void print(MGraph *G)
{
int i, j;
printf("\n------------打印矩阵----------\n\n");
for(i = 0; i vexnum; i++)
{
for(j = 0; j vexnum; j++)
{
if(G->arcs[i][j].adj == INFINITY)
{
printf(" / ");
}
else
{
printf(" %d ", G->arcs[i][j].adj);
}
}
printf("\n\n"); }
}
六、测试和结果
（给出测试用例以及测试结果）
七、用户手册
（告诉用户如何使用程序）