数据结构实验报告

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

2、lt;conio.h>#include<stdlib.h>#include<string.h>#define INFINITY 255678 /*赋初值用*/#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */enum DG, DN, UDG, UDN;typedef struct ArcCell int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struc

3、t char vexsMAX_VERTEX_NUM5;/*顶点向量*/ 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 = (M

4、Graph *)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); b

5、reak; default : break; getch();/*建立有向图*/void CreateDG(MGraph *G) int i, j, k; char v15, v25; printf("输入顶点数和弧数 : "); scanf("%d%d", &G->vexnum, &G->arcnum); getchar(); for(i = 0; i < G->vexnum; i+) scanf("%s", G->vexsi); /*自动赋值顶点向量*/ for(i = 0; i &l

6、t; G->vexnum; i+) for(j = 0; j < G->vexnum; j+) /*赋初值*/ G->arcsij.adj = INFINITY; G-> = NULL; for(k = 0; k < G->arcnum; k+) scanf("%s%s", v1, v2); /*输入一条边依附的顶点和权值*/ i = LocateVex(G, v1); /*确定v1和v2在G中位置*/ j = LocateVex(G, v2); G->arcsij.adj = 1; /*弧的权值赋值*/

7、 /*建立有向网*/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 < G->vexnum; i+) scanf("%s", G->vexsi); /*自动赋值顶点向量*/ for(i = 0; i < G->vexnum; i+) for(j

8、= 0; j < G->vexnum; j+) /*赋初值*/ G->arcsij.adj = INFINITY; G-> = NULL; for(k = 0; k < G->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 Cr

9、eateUDG(MGraph *G) int i, j, k; char v15,v25; printf("输入顶点数和弧数 : "); scanf("%d%d", &G->vexnum, &G->arcnum); getchar(); for(i = 0; i < G->vexnum; i+) scanf("%s", G->vexsi); /*自动赋值顶点向量*/ for(i = 0; i < G->vexnum; i+) for(j = 0; j < G->ve

10、xnum; j+) /*赋初值*/ G->arcsij.adj = INFINITY; G-> = NULL; for(k = 0; k < G->arcnum; k+) scanf("%s%s", v1, v2); /*输入一条边依附的顶点和权值*/ i = LocateVex(G, v1); /*确定v1和v2在G中位置*/ j = LocateVex(G, v2); G->arcsij.adj = 1; /*弧的权值赋值*/ G->arcsji.adj=G->arcsij.adj;/*置对称弧*/ /*建

11、立无向网*/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 < G->vexnum; i+) scanf("%s", G->vexsi); /*自动赋值顶点向量*/ for(i = 0; i < G->vexnum; i+) for(j = 0

12、; j < G->vexnum; j+) /*赋初值*/ G->arcsij.adj = INFINITY; G-> = NULL; for(k = 0; k < G->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 < G->vexnum; k+) if(strcmp(G->vexsk, v) = 0) break; return k;/*打印矩阵*/void print(MGraph *G) int i, j; printf("n-打印矩阵-nn"); for(i = 0; i < G->vexnum; i+) for(