数据结构与算法实验报告图.doc
沈 阳 工 程 学 院学 生 实 验 报 告（课程名称： 数据结构与算法 ）实验题目： 图 班 级 计算机121学 号 姓 名 赵玉林 地 点 F608 指导教师 张欣 实 验 日 期 : 2013 年 11 月 28 日一、实验目的1 掌握图的基本存储方法。2 掌握有关图的操作算法并用高级语言实现。3 熟练掌握图的两种搜索路径的遍历方法。4 掌握图的有关应用。二、实验环境Turbo C或是Visual C+三、实验内容与要求实验1 建立无向图的邻接矩阵或邻接表存储并输出本题给出了一个无向图的邻接矩阵存储表示，在此基础上稍加改动就可以实现有向图、无向图和有向网的邻接矩阵表示。实验2 建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历图的广度优先遍历用非递归方法很容易理解，非递归方法需要辅助队列Q以及出队、入队函数。四、实验过程及结果分析源代码：#include<stdio.h>#include<malloc.h>#define MAX_NUM 20#define OK 1#define ERROR -1typedef int ElemType;typedef char VertexType;typedef struct ArcNode /定义弧结点ElemType data;ArcNode *nextarc;ArcNode,*ArcLink;typedef struct VNode /定义顶点结点VertexType data;ArcLink firstarc;VNode,AdjListMAX_NUM;typedef structAdjList vdata;int vexnum,arcnum;ALGraph;/构建图的邻接表int Creategraph(ALGraph &G,int n)ArcLink p;int e,i;char v,w;for(i=0;i<n;i+)G.vdatai.data='A'+i;G.vdatai.firstarc=NULL;printf("输入边的个数:n");scanf("%d",&e);for(i=0;i<e;i+)getchar();/接收scanf的回车符printf("请输入某边所依附的两个顶点用A-%C表示n",'A'+n-1);scanf("%c%c",&v,&w);/fflush(stdin);printf("V=%c,W=%c,I=%dn",v,w,i);p=(ArcLink )malloc(sizeof(ArcNode);p->data=(int)(w-'A'+1);printf("%dn",p->data);p->nextarc=G.vdata(int)(v-'A').firstarc;G.vdata(int)(v-'A').firstarc=p;p=(ArcLink)malloc(sizeof(ArcNode);p->data=(int)(v-'A'+1);p->nextarc=G.vdata(int)(w-'A').firstarc;G.vdata(int)(w-'A').firstarc=p;G.vexnum=n; G.arcnum=e;return OK;/输出邻接表int printGraph(ALGraph G)ArcLink p;int i;for(i=0;i<G.vexnum;i+)printf("%2d %c",i,G.vdatai);for(p=G.vdatai.firstarc;p!=NULL;p=p->nextarc)printf("->");printf("%d",p->data);printf("n");return OK;int main()ALGraph G;int n;printf("请输入你要构建的无向图的顶点个数:n");scanf("%d",&n);Creategraph(G,n);printf("你所构建的无向图的邻接表如下所示:n");printGraph(G);return OK;1-1建立无向图的顶点数1-2建立无向图的边数1-3建立无向图五、成绩评定优良中及格不及格出 勤内 容格 式创 新效 果总 评指导教师： 年 月 日
