实现图的邻接矩阵和邻接表存储.doc下载_Word模板_8

实现图的邻接矩阵和邻接表存储.doc 南京信息工程大学数据结构实验(实习) 报告实验(实习)名称实现图的邻接矩阵和邻接表存储实验(实习)日期 12.4.23 得分指导老师宣文霞系计算机专业网络工程班级姓名学号一、需求分析编写一个程序，实现图的相关运算，并在此基础上设计一个主程序，完成如下功能: (1)建立图示的有向图,1的邻接矩阵，并输出。 (2)由有向图,1的邻接矩阵产生邻接表，并输出。 (3)再由(,)的邻接表产生对应的邻接矩阵，并输出。 (4)输出有向图G1从顶点0开始的深度优先遍历序列(递归算法)。 (5)输出有向图G1从顶点0开始的广度优先遍历序列(递归算法)。 , , , , , , , , ,, , , , , , ,, , 二、设计 CreatGraph(&G, V, VR): // 按定义(V, VR) 构造图 DestroyGraph(&G): // 销毁图 LocateVex(G, u); //若G中存在顶点u, 则返回该顶点在图中“位置”,否则返回其他信息。 GetVex(G, v); // 返回 v 的值。 PutVex(&G, v, value); // 对 v 赋值value。 FirstAdjVex(G, v); //返回v的“第一个邻接点”。若该顶点在G中没有邻接点，则返回“空”。 NextAdjVex(G, v, w); // 返回v的(相对于w的)“下一个邻接点”。若w是v的最后一个邻接点，则返回“空”。 InsertVex(&G, v); //在图G中增添新顶点v。 DeleteVex(&G, v); // 删除G中顶点v及其相关的弧。 InsertArc(&G, v, w); // 在G中增添弧，若G是无向的，则还增添对称弧。 DeleteArc(&G, v, w); //在G中删除弧，若G是无向的，则还删除对称弧。 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit()); //从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。三、调试分析调试过程中显示1个错误，改了几次后仍然显示1个错误，后来经过删减、添加。错误没有了，点击可运行了四、测试结果五、附录 1.typedef int InfoType; #define MAXV 100 /*最大顶点个数*/ /*以下定义邻接矩阵类型*/ typedef struct { int no; /*顶点编号*/ InfoType info; /*顶点其他信息*/ } VertexType; /*顶点类型*/ typedef struct /*图的定义*/ { int edges[MAXV][MAXV]; /*邻接矩阵*/ int vexnum,arcnum; /*顶点数，弧数*/ VertexType vexs[MAXV]; /*存放顶点信息*/ } MGraph; /*图的邻接矩阵类型*/ /*以下定义邻接表类型*/ typedef struct ANode /*弧的结点结构类型*/ { int adjvex; /*该弧的终点位置*/ struct ANode *nextarc; /*指向下一条弧的指针*/ InfoType info; /*该弧的相关信息,这里用于存放权值*/ } ArcNode; typedef int Vertex; typedef struct Vnode /*邻接表头结点的类型*/ { Vertex data; /*顶点信息*/ ArcNode *firstarc; /*指向第一条弧*/ } VNode; typedef VNode AdjList[MAXV]; /*AdjList是邻接表类型*/ typedef struct { AdjList adjlist; /*邻接表*/ int n,e; /*图中顶点数n和边数e*/ } ALGraph; /*图的邻接表类型*/ 2.#define INF 32767 /*INF表示?*/ void MatToList(MGraph g,ALGraph *&G) /*将邻接矩阵g转换成邻接表G*/ { int i,j,n=g.vexnum; /*n为顶点数*/ ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph)); for (i=0;iadjlist[i].firstarc=NULL; for (i=0;i=0;j--) if (g.edges[i][j]!=0) /*邻接矩阵的当前元素不为0*/ { p=(ArcNode *)malloc(sizeof(ArcNode)); /*创建一个结点*p*/ p->adjvex=j; p->info=g.edges[i][j]; p->nextarc=G->adjlist[i].firstarc; /*将*p链到链表后*/ G->adjlist[i].firstarc=p; } G->n=n;G->e=g.arcnum; } void ListToMat(ALGraph *G,MGraph &g) /*将邻接表G转换成邻接矩阵g*/ { int i,j,n=G->n; ArcNode *p; for (i=0;iadjlist[i].firstarc; while (p!=NULL) { g.edges[i][p->adjvex]=p->info; p=p->nextarc; } } g.vexnum=n;g.arcnum=G->e; } void DispMat(MGraph g) /*输出邻接矩阵g*/ { int i,j; for (i=0;in;i++) { p=G->adjlist[i].firstarc; if (p!=NULL) printf("%3d: ",i); while (p!=NULL) { printf("%3d",p->adjvex); p=p->nextarc; } printf("\n"); } } void main() { int i,j; MGraph g,g1; ALGraph *G; int A[MAXV][6]={ {0,5,0,7,0,0}, {0,0,4,0,0,0}, {8,0,0,0,0,9}, {0,0,5,0,0,6}, {0,0,0,5,0,0}, {3,0,0,0,1,0}}; g.vexnum=6;g.arcnum=10; for (i=0;i

                    本文档为【实现图的邻接矩阵和邻接表存储&#46;doc】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

实现图的邻接矩阵和邻接表存储&#46;doc

你可能还喜欢

实现图的邻接矩阵和邻接表存储.doc