数据结构邻接矩阵邻接表图实验报告.doc

《数据结构邻接矩阵邻接表图实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构邻接矩阵邻接表图实验报告.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-/实验名称：数据结构实验五实验内容：1.使用邻接矩阵建立一个图，深度遍历。2使用邻接表建立一个图，广度遍历。3.建立一个图，存储结构自己确定，并进行拓扑排序。实验代码：1.#include stdio.h#define Infinity 100#define MaxVertexNum 20typedef enum DG,DN,UDG,UDN GraphKind;typedef int VRType;typedef char VertexType;bool VisitMaxVertexNum;typedef struct ArcCellVRType adj;ArcCell,AdjMatrixM

2、axVertexNumMaxVertexNum; typedef struct VertexType vexsMaxVertexNum; AdjMatrix arcs; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 GraphKind kind; MGraph;int LocateVex(MGraph G,VertexType v)for(int i=0;iG.vexnum;+i)if(v=G.vexsi)return i;if (i = G.vexnum)printf(输入的顶点不合法n);return 0;VertexType v1,v2;VRType w;vo

3、id CreateUDG(MGraph &G)int i,j,k;printf(请输入顶点数：n);scanf(%d,&G.vexnum);printf(请输入弧数：n);scanf(%d,&G.arcnum);i = 0;while(iG.vexnum)printf(请输入第%d个顶点n,i);getchar();scanf(%c,&G.vexsi);+i;for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj = 0;for(k=0;kG.arcnum;+k)printf(请输入一条边依附的顶点及权值（v1 v2 w）n);getcha

4、r();scanf(%c %c %d,&v1,&v2,&w);i =LocateVex(G,v1);j =LocateVex(G,v2);G.arcsij.adj= w;G.arcsji = G.arcsij;return;void DFSTraverse(MGraph &G,int i)printf(%c ,G.vexsi);Visiti=true;for(int j=0;jG.vexnum;j+)if(G.arcsij.adj=1&!Visitj)DFSTraverse(G,j);void DFS(MGraph &G)int i;for(i=0;iG.vexnum;i+) Visiti=f

5、alse;for(i=0;iG.vexnum;i+)if(!Visiti)DFSTraverse(G,i);void main()MGraph graph;CreateUDG(graph);printf(顶点集合为：);for (int i=0;inext = NULL;return;void EnQueue(LinkQueue &Q,QElemType e)Queueptr p = NULL;p = (Queueptr)malloc(sizeof(QNode);if(!p) return;p-data = e;p-next = NULL;Q.rear-next = p;Q.rear = p;

6、return;QElemType DeQueue(LinkQueue &Q,QElemType &e)Queueptr p;if(Q.front=Q.rear) return ;p = Q.front-next;e = p-data;Q.front-next = p-next;if(Q.rear=p)Q.rear = Q.front;free(p);return e;int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return 1;else return 0;int Locate(ALGraph G,VertexType v)for(int k=0;k

7、G.vexnum;+k)if(v=G.verticesk.data)return k;if (k = G.vexnum)printf(输入的顶点不合法n);return 0;void CreateALGraph(ALGraph &G) VertexType v1,v2;int i,j,k;ArcNode *p,*r;printf(请输入顶点数和弧数（以空格分开） : );scanf(%d %d,&G.vexnum,&G.arcnum);for(i=0;iG.vexnum;+i)getchar();printf(请输入第%d个结点 : ,i);scanf(%c,&G.verticesi.data

8、);G.verticesi.firstarc = NULL;for(i=0;iadjvex = j;p-info = NULL;r-adjvex = k;r-info = NULL;p-nextarc=G.verticesk.firstarc;G.verticesk.firstarc=p;r-nextarc=G.verticesj.firstarc;G.verticesj.firstarc=r;return;void BFSTraverse(ALGraph G,QElemType x)int i,v;ArcNode *p;QElemType v1;for(v=0;vG.vexnum;+v) v

9、isitedv = false;LinkQueue Q;InitQueue(Q);EnQueue(Q,x);i = Locate(G,x);visitedi = true;for(v=0;vadjvex)visitedp-adjvex = true;EnQueue(Q,G.verticesp-adjvex.data);p = p-nextarc;if(!visitedv)visitedv = true;EnQueue(Q,G.verticesv.data);void main()char flag1;ALGraph graph2;QElemType x;CreateALGraph(graph2

10、);flag1 = Y;while(flag1 = Y|flag1 = y)printf(请输入遍历的起点 : );getchar();scanf(%c,&x);printf(广度遍历结果是：n);BFSTraverse(graph2,x);printf(n继续遍历（Y/N）: );getchar();scanf(%c,&flag1);return;3#include stdio.h#include stdlib.h#define StackInitSize 20#define StackIncrement 5#define MaxVertexNum 20typedef int InfoTyp

11、e;typedef char VertexType;typedef VertexType SElemType;typedef struct SElemType *base;SElemType *top;int stacksize;SqStack; typedef struct ArcNodeint adjvex; /该弧指向的顶点位置struct ArcNode *nextarc; /指向下一条弧的指针InfoType *info;ArcNode;typedef struct VNodeint indegree;VertexType data; /顶点信息ArcNode *firstarc;

12、/指向第一条依附该顶点的弧的指针VNode,AdjListMaxVertexNum;typedef structAdjList vertices;int vexnum,arcnum; /图的当前顶点数和弧数ALGraph;bool InitStack(SqStack &s)s.base = (SElemType * )malloc(StackInitSize * sizeof(SElemType);if(!s.base) return false;s.top = s.base;s.stacksize = StackInitSize;return true;bool Pop(SqStack &s

13、, int &e)if(s.top=s.base) return false;e = * -s.top;return true;bool Push(SqStack &s, int e)if(s.top-s.base=s.stacksize)s.base = (SElemType *)realloc(s.base,(s.stacksize+StackIncrement) * sizeof(SElemType) );if(!s.base) return false;s.top = s.base+s.stacksize;s.stacksize+=StackIncrement;* s.top+ = e

14、;return true;bool StackEmpty(SqStack s)if(s.top = s.base)return true;elsereturn false; int Locate(ALGraph G,VertexType v)for(int k=0;kG.vexnum;+k)if(v=G.verticesk.data)return k;if (k = G.vexnum)printf(输入的顶点不合法n);return 0;void CreateALGraph(ALGraph &G) /邻接表存储 VertexType v1,v2;int i,j,k;ArcNode *p;pri

15、ntf(请输入顶点数和弧数（以空格分开） : );scanf(%d %d,&G.vexnum,&G.arcnum);for(i=0;iG.vexnum;+i)getchar();printf(请输入第%d个结点 : ,i);scanf(%c,&G.verticesi.data);G.verticesi.firstarc = NULL;G.verticesi.indegree = 0;for(i=0;iadjvex = j;p-info = NULL;p-nextarc=G.verticesk.firstarc;G.verticesk.firstarc=p;return;void FindInD

16、egree(ALGraph G ,int aMaxVertexNum)int i,k;ArcNode *p;for(i=0;inextarc)k = p-adjvex;ak = +G.verticesk.indegree;return;void TopologicalSort(ALGraph G) /拓扑排序算法int i,j, count;ArcNode *p;SqStack s;int indegreeMaxVertexNum;for(i=0;iMaxVertexNum;+i)indegreei = 0;FindInDegree(G,indegree);InitStack(s);for(i=0;inextarc)j = p-adjvex;if(!(- indegreej) Push(s,j);if(countG.vexnum)printf(错误!该有向图有回路!n);else return;void main()ALGraph graph3;CreateALGraph(graph3);printf(拓扑排序的结果是 ：n);TopologicalSort(graph3);printf(n);return;