数据结构实验报告

1、数据结构实验报告第 6 次实验学号： 姓名：叶佳伟一、实验目的1、复习图的逻辑结构、存储结构及基本操作；2、掌握邻接矩阵、邻接表及图的创建、遍历；3、了解图的应用。二、实验内容1、（必做题）假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作：（ 1）构造图（包括有向图、有向网、无向图、无向网）；（ 2）根据深度优先遍历图；（ 3）根据广度优先遍历图。三、算法描述（采用自然语言描述）四、详细设计（画出程序流程图）五、程序代码（给出必要注释）#include#include#include#include#include#define INFINITY /*赋初值用*/#de

2、fine MAX_VERTEX_NUM 20 /* 最大顶点个数 */enum DG, DN, UDG, UDN;typedef struct ArcCell int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char vexsMAX_VERTEX_NUM5;/*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum, arcnum;/*图的当前顶点数和弧数*/ in

3、t 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

4、(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 v15, v25; printf(输入顶点数和弧数 : ); scanf(%d%d, &G-vexn

5、um, &G-arcnum); getchar(); for(i = 0; i vexnum; i+) scanf(%s, G-vexsi); /*自动赋值顶点向量*/ for(i = 0; i vexnum; i+) for(j = 0; j vexnum; j+) /*赋初值*/ G-arcsij.adj = INFINITY; G- = NULL; for(k = 0; k arcnum; k+) scanf(%s%s, v1, v2); /*输入一条边依附的顶点和权值*/ i = LocateVex(G, v1); /*确定v1和v2在G中位置*/ j = Loc

6、ateVex(G, v2); G-arcsij.adj = 1; /*弧的权值赋值*/ /*建立有向网*/void CreateDN(MGraph *G) int i, j, k, w; char v15, v25; printf(输入顶点数和弧数 : ); scanf(%d%d, &G-vexnum, &G-arcnum); getchar(); for(i = 0; i vexnum; i+) scanf(%s, G-vexsi); /*自动赋值顶点向量*/ for(i = 0; i vexnum; i+) for(j = 0; j vexnum; j+) /*赋初值*/ G-arcsij

7、.adj = INFINITY; G- = 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-arcsij.adj = w; /*弧的权值赋值*/ /*建立无向图*/void CreateUDG(MGraph *G) int i, j, k; char v15,v25; printf(输入顶点数和弧数 : ); scanf(%d%d, &G-vex

8、num, &G-arcnum); getchar(); for(i = 0; i vexnum; i+) scanf(%s, G-vexsi); /*自动赋值顶点向量*/ for(i = 0; i vexnum; i+) for(j = 0; j vexnum; j+) /*赋初值*/ G-arcsij.adj = INFINITY; G- = NULL; for(k = 0; k arcnum; k+) scanf(%s%s, v1, v2); /*输入一条边依附的顶点和权值*/ i = LocateVex(G, v1); /*确定v1和v2在G中位置*/ j = Lo

9、cateVex(G, v2); G-arcsij.adj = 1; /*弧的权值赋值*/ G-arcsji.adj=G-arcsij.adj;/*置对称弧*/ /*建立无向网*/void CreateUDN(MGraph *G) int i, j, k, w; char v15, v25; printf(输入顶点数和弧数 : ); scanf(%d%d, &G-vexnum, &G-arcnum); getchar(); for(i = 0; i vexnum; i+) scanf(%s, G-vexsi); /*自动赋值顶点向量*/ for(i = 0; i vexnum; i+) for(

10、j = 0; j vexnum; j+) /*赋初值*/ G-arcsij.adj = INFINITY; G- = 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-arcsij.adj = w; /*弧的权值赋值*/ G-arcsji.adj=G-arcsij.adj;/*置对称弧*/ int LocateVex(MGraph *G, char v) int k; for(k = 0; k vexnum; k+) if(strcmp(G-vexsk, v) = 0) break; return k;/*打印矩阵*/void print(MGraph *G) int i, j; printf(n-打印矩阵-nn); for(i = 0;