数据结构实验报告

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