有向网的存储结构.doc

广东工业大学实验报告 学院 专业 班 学号 成绩评定_实验题目： 有向网的存储结构一实验需求分析与方案邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。 所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接表。此时要分两种情况：有向图与无向图。对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结点，即起点。邻接表的输出，由于不了解C+中的绘图操作，故采用for语句输出各结点，并配合一些符号完成邻接表的输出。二实验过程与结果1.有向网的邻接矩阵存储结构创建程序：2.有向网的邻接表存储结构创建程序3.测试main()函数程序4.运行结果（截图）#include#include#define MAXV 100/定义邻接矩阵类型typedef struct int no; /顶点编号 int info; /顶点其余的信息 VertexType;typedef struct int edgesMAXVMAXV; /邻接矩阵 int n,e; /顶点数，弧数 VertexType vexsMAXV; /存放顶点信息MGraph;/一下定义邻接表类型typedef struct ANode /弧的节点结构类型 int adjvex; /该弧的终点位置 struct ANode *nextarc; int info; /弧的相关信息 ArcNode;typedef struct Vnode /邻接表头结点类型 int data; /顶点信息 ArcNode *firstarc; /指向第一条弧VNode;typedef VNode AdjListMAXV;typedef struct AdjList adjlist; int n,e;ALGraph;void MatToList(MGraph g,ALGraph *&G) /将邻接矩阵转换为邻接表 int i,j,n=g.n; ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph); for(i=0;iadjlisti.firstarc=NULL; for(i=0;i=0;j-) if(g.edgesij) p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=j; p-info=g.edgesij; p-nextarc=G-adjlisti.firstarc; G-adjlisti.firstarc=p; G-n=n; G-e=g.e;void ListToMat(ALGraph *G,MGraph &g) /邻接表转换为邻接矩阵 int i,j,n=G-n; ArcNode *p; for(i=0;in;i+) for(j=0;jn;j+) g.edgesij=0; for(i=0;iadjlisti.firstarc; while(p) g.edgesip-adjvex=p-info; p=p-nextarc; g.n=n; g.e=G-e;void DispMat(MGraph g) /输出邻接矩阵 int i,j; for(i=0;ig.n;i+) for(j=0;jg.n;j+) if(g.edgesij) printf(%3d,g.edgesij); else if(i=j) printf(%3d,0); else printf(%3s,*); printf(n); void DispAdj(ALGraph *G) /输出邻接表 int i; ArcNode *p; for(i=0;in;i+) p=G-adjlisti.firstarc; if(p) printf(%3d:,i); while(p) printf(%3d,p-adjvex); p=p-nextarc; printf(n); int main() int i,j; MGraph g,g1; ALGraph *G; int AMAXV6= 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.n=6; g.e=10; for(i=0;ig.n;i+) for(j=0;jnext!=NULL出了问题。将其改成p!=NULL后，邻接表便可顺利输出。四实验总结（心得体会） 1.必须牢固掌握基础知识。由于C语言知识有所遗忘，且未掌握好这学期所学的数据结构这门课，所以在实习之初感到棘手。不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以，这次实验之后，我告诫自己：今后一定要牢固掌握好专业基础知识。 2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，