【数据结构实验四】

您所在的位置：网站首页 › 递归函数的设计与实现实验报告 › 【数据结构实验四】

【数据结构实验四】

2024-07-10 15:22| 来源: 网络整理| 查看: 265

文章目录一、实验题目：二、实验目的：三、实验内容：1.建立无向图的邻接矩阵存储结构，进行深度优先遍历和广度优先遍历。程序代码： 2.建立有向图的邻接表存储结构，进行深度优先遍历和广度优先遍历。程序代码：四、实验心得体会

实验四

一、实验题目：

图的存储和遍历

二、实验目的：

⑴ 掌握图的逻辑结构； ⑵ 掌握图的邻接矩阵存储结构和图的邻接表存储结构； ⑶ 验证图的邻接矩阵存储和邻接表的存储以及深度优先遍历和广度优先遍历操作的实现。

三、实验内容：

（1）建立无向图的邻接矩阵存储；（2）对建立的无向图，进行深度优先遍历和广度优先遍历；（3）建立有向图的邻接表存储；（4）对建立的有向图，进行深度优先遍历和广度优先遍历。

1.建立无向图的邻接矩阵存储结构，进行深度优先遍历和广度优先遍历。程序代码： #include #include #define MaxSize 10 int visited1[MaxSize]={0}; int visited2[MaxSize]={0}; typedef char DataType; typedef struct { DataType vertex[MaxSize]; int edge[MaxSize][MaxSize]; int vertexNum,edgeNum; }MGraph; void CreatGraph(MGraph *G,DataType a[],int n,int e); void DFTravere(MGraph *G,int v); void BFTraverse(MGraph *G,int v); void CreatGraph(MGraph *G,DataType a[],int n,int e) { int i,j,k; G->vertexNum=n; G->edgeNum=e; for(i=0;ivertexNum;i++){ G->vertex[i]=a[i]; } for(i=0;ivertexNum;i++){ for(j=0;jvertexNum;j++) G->edge[i][j]=0; } for(k=0;kedgeNum;k++){ scanf("%d %d",&i,&j); G->edge[i][j]=1; G->edge[j][i]=1; } } void DFTraverse(MGraph *G,int v) { int j; printf("%c",G->vertex[v]); visited1[v]=1; for(j=0;jvertexNum;j++) if(G->edge[v][j]==1&&visited1[j]==0) DFTraverse(G,j); } void BFTraverse(MGraph *G,int v) { int i,j,Q[MaxSize]; int front,rear; front=-1,rear=-1; printf("%c",G->vertex[v]); visited2[v]=1; Q[++rear]=v; while(front!=rear){ v=Q[++front]; for(j=0;jvertexNum;j++){ if(G->edge[v][j]==1&&visited2[j]==0) { printf("%c",G->vertex[j]); visited2[j]=1; Q[++rear]=j; } } } } int main() { char ch[]={'A','B','C','D','E'}; MGraph MG; CreatGraph(&MG,ch,5,6); printf("深度优先遍历序列是："); DFTraverse(&MG,0); printf("\n广度优先遍历序列是："); BFTraverse(&MG,0); return 0; }

程序运行结果截图：在这里插入图片描述

2.建立有向图的邻接表存储结构，进行深度优先遍历和广度优先遍历。程序代码： #include #include #define MaxSize 10 int visited1[MaxSize]={0}; int visited2[MaxSize]={0}; typedef char DataType; typedef struct EdgeNode { int adjvex; struct EdgeNode *next; }EdgeNode; typedef struct { DataType vertex; EdgeNode *first; }VertexNode; typedef struct { VertexNode adjlist[MaxSize]; int vertexNum,edgeNum; }ALGraph; void CreateGraph(ALGraph *G,DataType a[],int n,int e){ int i,j,k; EdgeNode *s=NULL; G->vertexNum=n; G->edgeNum=e; for(i=0;ivertexNum;i++){ G->adjlist[i].vertex=a[i]; G->adjlist[i].first=NULL; } for(k=0;kedgeNum;k++){ scanf("%d %d",&i,&j); s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=j; s->next=G->adjlist[i].first; G->adjlist[i].first=s; } } void DFTraverse(ALGraph *G,int v){ EdgeNode *p=NULL; int j; printf("%c",G->adjlist[v].vertex); visited2[v]=1; p=G->adjlist[v].first; while(p!=NULL){ j=p->adjvex; if(visited2[j]==0) DFTraverse(G,j); p=p->next; } } void BFTraverse(ALGraph *G,int v){ EdgeNode *p=NULL; int Q[MaxSize],front=-1,rear=-1,j; printf("%c",G->adjlist[v].vertex); visited1[v]=1; Q[++rear]=v; while(front!=rear){ v=Q[++front]; p=G->adjlist[v].first; while(p!=NULL){ j=p->adjvex; if(visited1[j]==0) { printf("%c",G->adjlist[j].vertex); visited1[j]=1; Q[++rear]=j; } p=p->next; } } } int main(){ char ch[]={'A','B','C','D','E'}; ALGraph ALG; CreateGraph(&ALG,ch,5,6); printf("广度优先遍历序列是："); BFTraverse(&ALG,0); printf("\n深度优先遍历序列是："); DFTraverse(&ALG,0); return 0; }

程序运行结果截图：在这里插入图片描述

四、实验心得体会

通过本次实验我掌握了图的逻辑结构；掌握了图的邻接矩阵存储结构和图的邻接表存储结构；验证了图的邻接矩阵存储和邻接表的存储以及深度优先遍历和广度优先遍历操作的实现，在这个过程中我的程序技能更加完善。

【本文地址】

【数据结构实验四】

【数据结构实验四】

今日新闻

推荐新闻