图形数据结构实验.doc

淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 图形数据结构实验 班 级： 学 号： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 13 -图形数据结构实验报告要求1目的与要求:1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现（预习）；3）掌握AOV-网普里姆构造最小生成树算法的数据结构和算法实现（待学）；4）掌握AOE-网关路经的生成算法和实现（待学）；5）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；6）认真书写实验报告,并按时提交（第12周周一提交）。2 实验内容或题目题目： 一、图形数据结构实验图的建立与遍历。内容：1） 使用邻接矩阵和邻接表储表示分别实现如下给定的图1和或图2所示图的物理存储结构。2） 在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。图1 无向图V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8例2 有向图题目：二、连通网的最小生成树及其应用实验（暂不做）内容：对下图所示通信连通网，按照普里姆算法实现其最小生成树。通信连通网（权值单位：百万元）V1v6v5v4v3V2265135664253 实验步骤与源程序 邻接矩阵#include#include#define MAX_VERTEX_NUM 8#define OK 1#define FALSE 0#define Error -1#define AdjType int#define OtherInfo intint visitedMAX_VERTEX_NUM;#define TRUE 1#define MAXSIZE 6typedef structint elementMAXSIZE;int front;int rear;SeqQueue;typedef enumDG,DN,UDG,UDN GraphKind;typedef char VertexData;typedef struct ArcNodeAdjType adj;OtherInfo info;ArcNode;typedef structVertexData vexsMAX_VERTEX_NUM;ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;int vernum,arcnum;GraphKind kind;AdjMatrix;int LocateVertex(AdjMatrix *G,VertexData v)int j=Error;intk;for(k=0;kvernum;k+)if(G-vexsk=v)j=k;break;return (j);int CreatUDG(AdjMatrix * G)int i,j,k;VertexData v1,v2;cout输入无向图的顶点数和边数：G-vernum;cinG-arcnum;for(i=0;ivernum;i+)for(j=0;jvernum;j+)G-arcsij.adj=0;cout输入图的顶点：endl;for(i=0;ivernum;i+)cinG-vexsi;for(k=0;karcnum;k+)cout输入一条边的两顶点:v1;cinv2;i=LocateVertex(G,v1);j=LocateVertex(G,v2);G-arcsij.adj =1;G-arcsji.adj=G-arcsij.adj ;return (OK);void Print(AdjMatrix * G)int i,j;for(i=0;ivernum;i+) for(j=0;jarcnum;j+)coutarcsij.adj ; coutendl; void DepthFirstSearch(AdjMatrix * G,int v0)coutvexsv0endl;visitedv0=OK;for(int vi=1;vivernum;vi+)if(!visitedvi & G-arcsv0vi.adj=1)DepthFirstSearch(G,vi);void InitQueue(SeqQueue * Q)Q-front=Q-rear=0;int Empty(SeqQueue * Q)if(Q-front=Q-rear=0)return (TRUE);elsereturn (Error);int EnterQueue(SeqQueue * Q,int x)if(Q-rear+1)%MAXSIZE=Q-front)cout队已满。elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE;return (TRUE);int DeleteQueue(SeqQueue * Q,int * x)if(Q-front=Q-rear)cout队空elementQ-front;Q-front=(Q-front+1)%MAXSIZE;return(*x);int FirstAdj(AdjMatrix * G,int v)int j,p=-1;for(j=0;jvernum;j+)if(G-arcsvj.adj=1)p=j;break;return(p);int NextAdj(AdjMatrix * G,int v,int w)int j,p=-1;for(j=w+1;jvernum;j+)if(G-arcsvj.adj=1)p=j;break;return(p);void BreadthFirstSearch(AdjMatrix * G,int v0)SeqQueue * Q;Q=(SeqQueue *)malloc(sizeof(SeqQueue);InitQueue(Q);for(int i=0;ivernum;i+)visitedi=FALSE;coutvexsv0endl;visitedv0=OK;EnterQueue(Q,v0);int v,w;while(!Empty(Q)v=DeleteQueue(Q,&v); for(w=0;wvernum;w+) if(G-arcsvw.adj!=0) &(visitedw=0) coutvexswendl; visitedw = 1;EnterQueue(Q,w);void main()AdjMatrix * G;G=(AdjMatrix *)malloc(sizeof(AdjMatrix); CreatUDG(G);Print( G);cout打印邻接矩阵endl;cout深度优先搜索：endl;DepthFirstSearch(G,0);cout广度优先搜索：endl;BreadthFirstSearch(G,0);邻接表#include #include #include #include #define OK 1#define ERROR -1#define TRUE 1#define FALSE 0#define maxvernum 10#define maxsize (maxvernum+1)#define infinity 32768typedef struct int elementmaxsize;int front;int rear;Seqqueue;int Enterqueue(Seqqueue *q,int x)if(q-rear+1)%maxsize!=q-front ) q-element q-rear =x;q-rear =(q-rear +1)%maxsize;return(TRUE);else return(FALSE);int Deletequeue(Seqqueue *q,int *x)if(q-front=q-rear)return(FALSE);*x=q-elementq-front;q-front =(q-front +1)%maxsize;return(TRUE);int visitedmaxvernum;typedef struct Arcnodeint adjvex;struct Arcnode *nextarc;Arcnode;typedef struct vexnodeint data;Arcnode *firstarc;vexnode;typedef structvexnode vexsmaxvernum;int vexnum,arcnum;Adjlist;int Locate(Adjlist *g,int v)int k;for(k=0;kvexnum;k+)if(g-vexsk.data=v)return k;return -1;void Create(Adjlist *g)int i,j,k,v1,v2;cout请输入顶点数和弧数:g-vexnumg-arcnum;for(i=0;ivexnum;i+)g-vexsi.data=i+1;g-vexsi.firstarc=NULL;cout打印顶点数据:endl;for(i=0;ivexnum;i+)coutavexsi.data ;coutendl;for(k=0;karcnum;k+)cout请输入第k+1对边：v1v2;i=Locate(g,v1);j=Locate(g,v2);if(i=0&j=0)Arcnode *p,*q;p=(Arcnode *)malloc(sizeof(Arcnode);p-adjvex=j;p-nextarc=NULL;if(!g-vexsi.firstarc) g-vexsi.firstarc=p;elseq=g-vexsi.firstarc;while(q-nextarc)q=q-nextarc;q-nextarc=p;cout打印邻接表：endl;for(i=0;ivexnum;i+)if(g-vexsi.firstarc)Arcnode *p;couti+1 avexsi.data;p=g-vexsi.firstarc;while(p-nextarc)coutadjvex)+1;p=p-nextarc ;coutadjvex)+1endl;else couti+1 avexsi.dataadjvex;else return -1;int Next(Adjlist g,int v,int w)int flag=0;Arcnode *p;p=g.vexsv.firstarc;while(p)if(p-adjvex=w)flag=1;break;p=p-nextarc;if(flag & p-nextarc)return p-nextarc-adjvex;else return -1;void DFS(Adjlist g,int v0)if(g.vexsv0.firstarc)Arcnode *p;coutadjvex)DFS(g,(p-adjvex);p=p-nextarc;else coutrear=q-front=0;int v;int w;for(;v0g.vexnum ;v0+)if(!visitedv0)coutrear!=q-front)Deletequeue(q,&v);w=First(g,v);while(w!=-1)if(!visitedw)coutg.vexsw.data;visitedw=TRUE;Enterqueue(q,w);w=Next(g,v,w); void main()Adjlist g;Create(&g);for(int i=0;ig.vexnum;i+)visitedi=FALSE;cout深度优先遍历：;for(int v0=0;v0g.vexnum ;v0+)if(!visitedv0)DFS(g,v0);coutendl;for(i=0;ig.vexnum;i+)visitedi=FALSE;cout广度优先