数据结构实验报告第 6 次实验学号:20141060106 姓名:叶佳伟一、实验目的1、复习图的逻辑结构、存储结构及基本操作;2、掌握邻接矩阵、邻接表及图的创建、遍历;3、了解图的应用。
二、实验内容1、(必做题)假设图中数据元素类型是字符型,请采用邻接矩阵或邻接表实现图的以下基本操作:( 1)构造图(包括有向图、有向网、无向图、无向网);( 2)根据深度优先遍历图;( 3)根据广度优先遍历图。
三、算法描述(采用自然语言描述)四、详细设计(画出程序流程图)五、程序代码(给出必要注释)#include<stdio.h>#include<malloc.h>#include<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;/*弧相关信息指针*/}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 < G->vexnum; i++){scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/ }for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++) /*赋初值*/{G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = 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->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 < G->vexnum; i++){scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/ }for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++) /*赋初值*/{G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = 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->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 < G->vexnum; i++){scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++) /*赋初值*/{G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = 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->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 < G->vexnum; i++){scanf("%s", G->vexs[i]); /*自动赋值顶点向量*/ }for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++) /*赋初值*/{G->arcs[i][j].adj = INFINITY;G->arcs[i][j].info = 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->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 < G->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 < G->vexnum; i++){for(j = 0; j < G->vexnum; j++){if(G->arcs[i][j].adj == INFINITY){printf(" / ");}else{printf(" %d ", G->arcs[i][j].adj);}}printf("\n\n");}}六、测试和结果(给出测试用例以及测试结果)七、用户手册(告诉用户如何使用程序)。