图形数据结构实验.docx

1、图形数据结构实验淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 图形数据结构实验 班 级： 学 号： 姓 名： 图形数据结构实验报告要求1目的与要求:1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现；3）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；4）认真书写实验报告,并按时提交（第12周周三提交）。2 实验内容或题目题目： 一、图形数据结构实验图的建立与遍历。内容：1） 使用邻接矩阵和邻接表储表示分别实现如下给定的图1和图2所示图的

2、物理存储结构。2） 在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。3 实验步骤与源程序 邻接矩阵：#include stdlib.h#include stdio.h#define MAX_VERTEX_NUM 10 /*最多顶点个数*/#define INFINITY 32768 /*表示极大值，即*/#define True 1#define False 0#define Error -1#define Ok 1typedef enumDG, DN, UDG, UDN GraphKind; /*图的种类：DG表示有向图, DN表示有向网, U

3、DG表示无向图, UDN表示无向网*/typedef char VertexData; /*假设顶点数据为字符型*/typedef struct ArcNode int adj; /*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/ ArcNode;typedef struct VertexData vexsMAX_VERTEX_NUM; /*顶点向量*/ ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; /*邻接矩阵*/ int vexnum,arcnum; /*图的顶点数和弧数*/ GraphKind kind; /*图的种类标志*/AdjMa

4、trix; /*(Adjacency Matrix Graph)*/typedef struct node int data; struct node *next; struct node *first; struct node *last;LinkQueue;int InitQueue(LinkQueue *s) s-first=(LinkQueue*)malloc(sizeof(LinkQueue); s-last=s-first; s-first-next=NULL; return True;int EnterQueue(LinkQueue *s,int x) LinkQueue *te

5、mp; temp=(LinkQueue*)malloc(sizeof(LinkQueue); if(temp!=NULL) temp-data=x; temp-next=NULL; s-last-next=temp; s-last=temp; return True; return False;int IsEmpty(LinkQueue *s) if(s-first=s-last) return True; else return False;int DeleteQueue(LinkQueue *s,int *v) LinkQueue *temp; if(s-last=s-first) ret

6、urn False; temp=(LinkQueue*)malloc(sizeof(LinkQueue); temp-first=s-first-next; s-first-next=temp-first-next; if(s-last=temp-first) s-last=s-first; *v=temp-first-data; free(temp); return True;int LocateVertex(AdjMatrix *G,VertexData v) /*求顶点位置函数*/ int j=Error,k; for(k=0;kvexnum;k+) if(G-vexsk=v) j=k;

7、 break; return(j);int visited50;int CreateDN(AdjMatrix *G) /*创建一个有向网*/ int i,j,k,weight; VertexData v1,v2; printf(输入图的弧数和顶点数n); fflush(stdin); scanf(%d,%d,&G-arcnum,&G-vexnum); /*输入图的顶点数和弧数*/ for(i=0;ivexnum;i+) /*初始化邻接矩阵*/ for(j=0;jvexnum;j+) G-arcsij.adj=INFINITY; for(i=0;ivexnum;i+) /输入顶点字符循环 pri

8、ntf(输入图的顶点n); fflush(stdin); scanf(%c,&G-vexsi); /* 输入图的顶点*/ for(k=0;karcnum;k+) printf(输入一条弧的两个顶点及权值n); fflush(stdin); scanf(%c,%c,%d,&v1,&v2,&weight);/*输入一条弧的两个顶点及权值*/ i=LocateVertex(G,v1); j=LocateVertex(G,v2); G-arcsij.adj=1; /*建立弧*/ return(Ok);int CreateUDN(AdjMatrix *G) /*创建一个有向网*/ int i,j,k,w

9、eight; VertexData v1,v2; printf(输入图的弧数和顶点数n); fflush(stdin); scanf(%d,%d,&G-arcnum,&G-vexnum); /*输入图的顶点数和弧数*/ for(i=0;ivexnum;i+) /*初始化邻接矩阵*/ for(j=0;jvexnum;j+) G-arcsij.adj=INFINITY; for(i=0;ivexnum;i+) /输入顶点字符循环 printf(输入图的顶点n); fflush(stdin); scanf(%c,&G-vexsi); /* 输入图的顶点*/ for(k=0;karcnum;k+) p

10、rintf(输入一条弧的两个顶点及权值n); fflush(stdin); scanf(%c,%c,%d,&v1,&v2,&weight);/*输入一条弧的两个顶点及权值*/ i=LocateVertex(G,v1); j=LocateVertex(G,v2); G-arcsij.adj=1; /*建立弧*/ G-arcsji.adj=G-arcsij.adj; return(Ok);void Depth1(AdjMatrix g1,int vo) int vj; printf(%c,g1.vexsvo); visitedvo=True; for(vj=0;vjg1.vexnum;vj+) i

11、f(!visitedvj)&(g1.arcsvovj.adj=1) Depth1(g1,vj);void Breadth1(AdjMatrix g1,int vo) int vi,vj; LinkQueue Q; InitQueue(&Q); visitedvo=True; EnterQueue(&Q,vo); while(!IsEmpty(&Q) DeleteQueue(&Q,&vi); printf(%c,g1.vexsvi); for(vj=0;vjg1.vexnum;vj+) if(!visitedvj)&(g1.arcsvivj.adj=1) visitedvj=True; Ente

12、rQueue(&Q,vj); void Traverse1(AdjMatrix g1) /邻接矩阵存储结构的深度和广度优先搜索遍历 int vi; for(vi=0;vig1.vexnum;vi+) /深度遍历邻接矩阵 visitedvi=False; printf(n图的深度遍历序列n); for(vi=0;vig1.vexnum;vi+) if(!visitedvi) Depth1(g1,vi); printf(n); for(vi=0;vig1.vexnum;vi+) visitedvi=False; printf(n图的广度遍历序列n); for(vi=0;vig1.vexnum;vi

13、+) if(!visitedvi) Breadth1(g1,vi); printf(n); void main() printf(有向图n); AdjMatrix G; CreateDN(&G); Traverse1(G); printf(无向图n); CreateUDN(&G); Traverse1(G);邻接表：#includestdio.h#includestring.h#includestdlib.h#includemath.h#define MAX_INT 1000#define MAX_VERTEX_NUM 20#define MAX_QUEUE_NUMBER 20#define

14、TRUE 1#define FALSE 0#define QueueElementType inttypedef struct ArcNode int adjvex; double adj; struct ArcNode *nextarc;ArcNode;typedef struct VexNode char szName40; ArcNode *firstarc;VexNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vexs; int vexnum,arcnum;Net;/定义队列typedef struct int *elem; int

15、front, rear;Queue;void InitQueue(Queue &Q) Q.elem = new intMAX_QUEUE_NUMBER; Q.front = Q.rear = 0;int EmptyQueue(Queue Q) if(Q.front=Q.rear) return 0; else return 1;void DestroyQueue(Queue &Q) delete Q.elem; Q.front = Q.rear = 0;void EnterQueue(Queue &Q, int e) if(Q.rear + 1)%MAX_QUEUE_NUMBER != Q.f

16、ront) Q.elemQ.rear = e; else printf(队列满!n); Q.rear = (Q.rear + 1)%MAX_QUEUE_NUMBER;void LeaveQueue(Queue &Q, int &e) if(Q.rear != Q.front) e = Q.elemQ.front; else printf(队列空!n); Q.front = (Q.front+1)%MAX_QUEUE_NUMBER;int LocateVex(Net ga,char *name) int i; for(i=0;iga.vexnum;i+) if(strcmp(name,ga.ve

17、xsi.szName)=0) return i; return -1;void crt_net(Net &ga) ArcNode *p; char name140,name240; int i,j,k; double w; printf(请输入顶点数和弧数：); scanf(%d%d,&ga.vexnum,&ga.arcnum); printf(请依次输入顶点名：n); for(i=0;iga.vexnum;i+) scanf(%s,ga.vexsi.szName); ga.vexsi.firstarc=NULL; for(k=0;kadjvex=j; p-adj=w; p-nextarc=g

18、a.vexsi.firstarc; ga.vexsi.firstarc=p; void DFS(Net ga,char *name,int *visited) int v,w; ArcNode *p; v=LocateVex(ga,name); visitedv=1; printf(%s ,ga.vexsv.szName); p=ga.vexsv.firstarc; while(p!=NULL) w=p-adjvex; if(visitedw=0) DFS(ga,ga.vexsw.szName,visited); p=p-nextarc; void DFSTravel(Net ga,char

19、*name) int v,k=0; int visited20; for(v=0;vga.vexnum;v+) visitedv=0; for(v=LocateVex(ga,name);k!=2;v=(v+1)%(ga.vexnum-1) if(v+1=LocateVex(ga,name) k+; if(visitedv=0) DFS(ga,ga.vexsv.szName,visited); void BFSTravel(Net ga,char *name) ArcNode *p; int v,w,u,k=0; Queue Q; int visited20; for(v=0;vadjvex;

20、if(visitedw=0) printf(%s ,ga.vexsw.szName); visitedw=1; EnterQueue(Q,w); p=p-nextarc; void main() Net ga; crt_net(ga); printf(深度优先遍历：); DFSTravel(ga,ga.vexs1.szName); printf(n); printf(广度优先遍历：); BFSTravel(ga,ga.vexs1.szName); printf(n);4 测试数据与实验结果（可以抓图粘贴） 5 结果分析与实验体会 个人觉得这次的实验很难，很多的地方都不知道要怎么写，比如怎么输出邻接矩阵，邻接表的也不知道要怎么处理，自己改了很久，但是不对，最后是请同学帮忙完成的。