有向图综合实验文.doc

《有向图综合实验文.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、有向图综合实验文档1.前言本文档及相关程序是数据结构大作业的解答。程序使用C++语言编写，在TurboC++3.0环境下调试通过。2.总体设计本次实验的范围是有向图和网络，其中网络相当于加权有向图，或者反过来说，无权有向图可以看作是边的权值为1的加权有向图。因此有向图可以看作是网络的子集。实验要求有向图分别使用邻接矩阵和邻接表两种数据结构表示。考虑到能将两种数据结构不同的图在同一个接口框架内描述和实现，因此在实验程序中采用面向对象的技术，将基于邻接矩阵和邻接表的有向图和网络分别抽象为具有继承关系的类来实现。整个程序中共包括三个类

2、，分别是公共父类NETWORK，以及两个子类ARRARGRAPH和LINKGRAPH。类的继承关系图如下：NETWORKLINKGRAPHARRAYGRAPHNETWORK是一个虚基类，没有实现的数据结构，但定义了数据结构的封装接口层和应用方法。其中由于没有实际的数据结构，因此封装接口层都定义为纯虚函数，留待继承类中实现。ARRAYGRAPH是NETWORK的邻接矩阵实现类。LINKGRAPH是NETWORK的邻接表实现类。基于实验代码应该尽可能简洁的考虑，本次的实现代码中假定图中边的权值都是整型，节点除名称外也没有其它附加的信

3、息。3.程序模块3.1.概述本实验程序共包括6个C++程序文件。其中包括一个类定义文件以及五个主程序文件，每个主程序文件分别解答一道至多道实验题目。具体清单如下：程序名称程序说明CLASSDEF.CPP类定义文件，其中定义了NETWORK、ARRAYGRAPH、LINKGRAPH三个有向图类以及STACK、QUEUE两个辅助类WORK_1.CPP主程序，演示有向图的构造，邻接矩阵与邻接表的转换，深度优先和广度优先遍历，解答题目1-5WORK_2.CPP主程序，演示有向图的拓扑和逆拓扑排序，解答题目6-7WORK_3.CPP主程序

4、，演示有向图两个顶点之间路径和回路的搜索，解答题目8-9WORK_4.CPP主程序，演示有向图强连通分量的搜索，解答题目10WORK_5.CPP主程序，演示网络的关键路径查找，解答题目11注：实验题目的具体内容和要求请参见附录1本部分的下面几个章节中将详细叙述模块定义文件中的各个类定义。而几个主程序将留待到运行和结果分析部分再结合测试案例同一叙述。1.1.邻接表实现类LINKGRAPH描述：LINKGRAPH是虚基类NETWORK的派生类，用邻接表作为有向图的存储结构，并按照邻接表存储的要求实现了在NETWORK类中声明的数据接

5、口层。LINKGRAPH类中没有应用层的函数，而是全部从NETWORK类中继承。属性：属性名说明vexs[MAX_VERTEX_NUM]一维的顶点数组，数组元素是VEXNODE结构体类型，定义如下：charname[MAX_STRING_LEN]顶点名称intindegree顶点入度intoutdegree顶点出度ARCNODE*firstarc指向第一条边的指针注：MAX_VERTEX_NUM表示图中允许的最大顶点数量方法：属性名说明LINKGRAPH(intkind)构造函数LINKGRAPH(NETWORK&obj)拷贝构

6、造函数，可以从ARRAYGRAPH和LINKGRAPH类实例复制信息，构造出一个新的LINKGRAPH类实例~LINKGRAPH()析构函数，遍历整个邻接表，释放分配的存储空间char*GetVexName(intv)接口层函数，返回顶点v的名称intInDegree(intv)接口层函数，返回顶点v的入度，顶点入度在边插入时计算，结果直接存储在vexs顶点数组中intOutDegree(intv)接口层函数，返回顶点v的出度，顶点出度在边插入时计算，结果直接存储在vexs顶点数组中intGetArcWeight(intv1,i

7、ntv2)接口层函数，返回从顶点v1到v2的边的权值，无权有向图返回1intFindVex(char*name)接口层函数，根据名称name返回顶点的序号intFirstVex(intv,intdirect=0)接口层函数，查找顶点v的第一个邻接点的序号direct=0：正向查找，即依据以v为尾的弧进行查找direct=1：逆向查找，即依据以v为头的弧进行查找intNextVex(intv,intw,intdirect=0)接口层函数，查找顶点v的在w之后下一个邻接点的序号direct=0：正向查找，即依据以v为尾的弧进行查找d

8、irect=1：逆向查找，即依据以v为头的弧进行查找intInsertVex(char*name)接口层函数，在图中增加名称为name的顶点intInsertArc(intv1,intv2,intvalue=1)接口层函数，在图中增加从顶点v1到v2的边，val