图的遍历数据结构实验报告.docx

发布时间：2022-06-10 发布人：admin 分类：说明书资料大小：0.15M 资料格式：docx 举报版权申诉

linda1212-4610395-16359648008048852452.docx.pdf-第1页.png

第1页 / 共7页

linda1212-4610395-16359648008048852452.docx.pdf-第2页.png

第2页 / 共7页

linda1212-4610395-16359648008048852452.docx.pdf-第3页.png

第3页 / 共7页

linda1212-4610395-16359648008048852452.docx.pdf-第4页.png

第4页 / 共7页

linda1212-4610395-16359648008048852452.docx.pdf-第5页.png

第5页 / 共7页

linda1212-4610395-16359648008048852452.docx.pdf-第6页.png

第6页 / 共7页

linda1212-4610395-16359648008048852452.docx.pdf-第7页.png

第7页 / 共7页

数据结构实验

实验四实验7.1

班级：信安1002

学号：0705100229

姓名：张慧珍

数据结构实验实验四实验 7.1 班级：信安 1002 学号：0705100229 姓名：张慧珍

一、实验题目编写一个程序 algo8-2.cpp，实现实现图的遍历运算，并在此基础上设计一个主程序完成如下功能: （1）输出如图所示的有向图 G 从顶点 0 开始的深度优先遍历序列（递归算法）；（2）输出如图所示的有向图 G 从顶点 0 开始的深度优先遍历序列（非递归算法）；（3）输出如图所示的有向图 G 从顶点 0 开始的广度优先遍历序列; 二、实验目的通过实验巩固对图的各种基本遍历运算的操作。三、实验过程 #include #include #define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR 0 typedef int InfoType; typedef char VertexType; /* 该弧相关信息的指针类型 */ /* 顶点的类型 */ typedef struct ArcNode { /* 弧结点的结构 */ adjvex; int struct ArcNode *nextarc; InfoType }ArcNode; *info; /* 该弧所指向的顶点的位置 */ /* 指向下一条弧的指针 */ /* 该弧相关信息的指针（觉得应该是记录某些备注信息）如权值 */ typedef struct VNode { /* 顶点结点的结构 */ VertexType data; ArcNode }VNode, AdjList[MAX_VERTEX_NUM]; *firstarc; /* 顶点信息 */ /* 指向第一条依附该顶点的弧的指针 */ typedef struct { AdjList vertices; int //int }ALGraph; kind; vexnum, arcnum; /* 图的邻接表结构定义 */ /* 存放顶点的数组 */ /* 图的当前顶点数和弧数 */ /* 图的种类标志 */

int CreateDG(ALGraph &G,FILE *fp,FILE *pl) { /* 邻接表建立有向图 */ /* 输入结点数目和边数 */ *p; i,s,d; int char c; ArcNode printf("请输入顶点和边数"); fprintf(pl,"请输入顶点和边数"); fscanf(fp,"%d%d",&G.vexnum,&G.arcnum); // scanf("%d%d",&G.vexnum,&G.arcnum); printf("%d %d\n",G.vexnum,G.arcnum); fprintf(pl,"%d %d\n",G.vexnum,G.arcnum); //getchar(); printf("请输入顶点值"); fprintf(pl,"请输入顶点值"); fscanf(fp,"\n"); for(i=0; { i

p = (struct ArcNode *)malloc(sizeof(struct ArcNode)); p->adjvex = d; /* 保存该弧所指向的终点位置 */ p->nextarc G.vertices[s].firstarc = G.vertices[s].firstarc; /* 保存顶点所对应的终点位置 */ = p; } return OK; } { void DispAdj(ALGraph *G,FILE *pl) int i; ArcNode *p; printf("\n 邻接表：\n"); fprintf(pl,"\n 邻接表：\n"); for(i=0;ivexnum;i++) { p=G->vertices[i].firstarc; printf("%2d:",i); fprintf(pl,"%2d:",i); while(p!=NULL) { printf("%2d",p->adjvex); fprintf(pl,"%2d",p->adjvex); p=p->nextarc; } printf("\n"); fprintf(pl,"\n"); } } void DFS(ALGraph *G,int v,FILE *pl)//深度优先遍历（递归） { ArcNode *p; static int visited[100]={0}; visited[v]=1; printf(" %d ",v); fprintf(pl," %d ",v); p=G->vertices[v].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0) DFS(G,p->adjvex,pl); p=p->nextarc; }

} void BFS(ALGraph *G,int v,FILE *pl)//广度优先遍历 { ArcNode *p; int queue[MAX_VERTEX_NUM],front=0,rear=0; int visited[MAX_VERTEX_NUM]={0}; int w; printf(" %d ",v); fprintf(pl," %d ",v); visited[v]=1; rear=(rear+1)%MAX_VERTEX_NUM; queue[rear]=v; while(front!=rear) { front=(front+1)%MAX_VERTEX_NUM; w=queue[front]; p=G->vertices[w].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0) { printf(" %d ",p->adjvex); fprintf(pl," %d ",p->adjvex); visited[p->adjvex]=1; rear=(rear+1)%MAX_VERTEX_NUM; queue[rear]=p->adjvex; } p=p->nextarc; } } printf("\n"); fprintf(pl,"\n"); } { void DFS2(ALGraph *G,int v,FILE *pl)//深度优先遍历（非递归） ArcNode *p; ArcNode *s[MAX_VERTEX_NUM]; int visited[MAX_VERTEX_NUM]={0}; int i; int top=0; printf(" %d ",v); fprintf(pl," %d ",v); s[top++]=G->vertices[v].firstarc;

visited[v]=1; while(top!=0) { p=s[--top]; if(p!=NULL) { s[top++]=p->nextarc; i=p->adjvex; if(visited[i]==0) { visited[i]=1; printf(" %d ",i); fprintf(pl," %d ",i); s[top++]=G->vertices[i].firstarc; } } } } void main() { FILE *fp; FILE *pl; fp=fopen("E://du.txt","r"); pl=fopen("E://xie.txt","w"); int v; ALGraph G; fscanf(fp,"%d",&v); fscanf(fp,"\n"); CreateDG(G,fp,pl); DispAdj(&G,pl); printf("从顶点%d 开始遍历\n",v); fprintf(pl,"从顶点%d 开始遍历\n",v); printf("深度优先遍历（递归）\n"); fprintf(pl,"深度优先遍历（递归）\n"); DFS(&G, v,pl); printf("\n 深度优先遍历（非递归）\n"); fprintf(pl,"\n 深度优先遍历（非递归）\n"); DFS2(&G, v,pl); printf("\n 广度优先遍历（递归）\n"); fprintf(pl,"\n 广度优先遍历（递归）\n"); BFS(&G,v,pl); }

四、实验结果

分享到：

赞收藏

资料库

图的遍历数据结构实验报告.docx

相关推荐

网络技术

热门标签

最新资料