有向网的存储结构

《有向网的存储结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、广东工业大学实验报告学院专业班学号成绩评定_________实验题目：有向网的存储结构一﹑实验需求分析与方案邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及

2、各条边的起点与终点序号，建立图的邻接表。此时要分两种情况：有向图与无向图。对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结点，即起点。邻接表的输出，由于不了解C++中的绘图操作，故采用for语句输出各结点，并配合一些符号完成邻接表的输出。二﹑实验过程与结果1.有向网的邻接矩阵存储结构创建程序：2.有向网的邻接表存储结构创建程序3.测试main()函数程序4.运行结果（截图）#include#include#defineMAXV100//定义邻接矩阵类型

3、typedefstruct{intno;//顶点编号intinfo;//顶点其余的信息}VertexType;typedefstruct{intedges[MAXV][MAXV];//邻接矩阵intn,e;//顶点数，弧数VertexTypevexs[MAXV];//存放顶点信息}MGraph;//一下定义邻接表类型typedefstructANode//弧的节点结构类型{intadjvex;//该弧的终点位置structANode*nextarc;intinfo;//弧的相关信息}ArcNode;typedefstructVnode//邻接表头结点类型{intdata;

4、//顶点信息ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;voidMatToList(MGraphg,ALGraph*&G)//将邻接矩阵转换为邻接表{inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;iadjlist[i].firstarc=NULL;for(i=0;i=0

5、;j--)if(g.edges[i][j]){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=n;G->e=g.e;}voidListToMat(ALGraph*G,MGraph&g)//邻接表转换为邻接矩阵{inti,j,n=G->n;ArcNode*p;for(i=0;i

6、or(i=0;iadjlist[i].firstarc;while(p){g.edges[i][p->adjvex]=p->info;p=p->nextarc;}}g.n=n;g.e=G->e;}voidDispMat(MGraphg)//输出邻接矩阵{inti,j;for(i=0;i

7、");}}voidDispAdj(ALGraph*G)//输出邻接表{inti;ArcNode*p;for(i=0;in;i++){p=G->adjlist[i].firstarc;if(p)printf("%3d:",i);while(p){printf("%3d",p->adjvex);p=p->nextarc;}printf("");}}intmain(){inti,j;MGraphg,g1;ALGraph*G;intA[MAXV][6]={{0,5,0,7,0,0},{0,0,4,0,0,0},{8,0,0