南邮数据结构上机实验三图的基本运算及飞机换乘次数最少问题

实验报告（2015/2016学年第二学期）课程名称数据结构A实验名称图的基本运算及飞机换乘次数最少问题实验时间2016年5月19日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院系管理学院专业信息管理与信息系统实习题名图的基本运算班级姓名学号日期20160519一、问题描述验证教材中关于在邻接矩阵和邻接表两种不同的储存结构上实现图的基本运算的算法见程序91程序98，在邻接矩阵存储结构上实现图的深度和广度优先遍历算法，设计主函数，测试上述运算。二、概要设计文件GRAPHCPP中在该文件中定义图数据结构的抽象模板类GRAPH。邻接矩阵类MGRAPH是从抽象类GRAPH派生得来，邻接表类LGRAPH也是从抽象类GRAPH派生得来。主函数的代码如图所示。三、详细设计1类和类的层次设计程序定义了GRAPH类，以及邻接矩阵类MGRAPH和邻接表类LGRAPH以及循环列表类SEQQUEUE。邻接矩阵类MGRAPH继承了GRAPH的数据成员N和E，重载了GRAPH的纯虚函数。保护数据成员TA指向动态生成的二维数组，用以存储邻接矩阵。邻接表类LGRAPH也继承了GRAPH的数据成员N和E及重载了GRAPH的纯虚函数，边结点由类ENODE定义，每个结点有三个域ADJVEX、W和NEXTARC。邻接表的表头组成为一维数组，A是指向该数组的指针。SEQQUEUEINTFRONT,REARINTMAXSIZEBTNODEQSEQQUEUEINTMSIZESEQQUEUEDELETEQBOOLISEMPTYCONSTRETURNFRONTREARBOOLISFULLCONSTRETURNREAR1MAXSIZEFRONTBOOLFRONTBTNODEBOOLENQUEUEBTNODEXBOOLDEQUEUEVOIDCLEARFRONTREAR0（A）循环队列类MGRAPHTATNOEDGEVOIDDFSINTV,BOOLVISITEDVOIDBFSINTV,BOOLVISITEDMGRAPHINTMSIZE,CONSTTMGRAPHRESULTCODEINSERTINTU,INTV,TRESULTCODEREMOVEINTU,INTVBOOLEXISTINTU,INTVCONSTVOIDDFSVOIDBFSTLGRAPHENODEALGRAPHINTMSIZELGRAPHRESULTCODEINSERTINTU,INTV,TRESULTCODEREMOVEINTU,INTVBOOLEXISTINTU,INTVCONSTTGRAPHINTN,EVIRTUALRESULTCODEINSERTINTU,INTV,TVIRTUALRESULTCODEREMOVEINTU,INTV0VIRTUALBOOLEXISTINTU,INTVCONST0T（B）模版类GRAPH，MGRAPH和LGRAPHT2核心算法深度优先搜索用栈来实现1把根节点压入栈中2每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱3找到所要找的元素时结束程序4如果遍历整个树还没有找到，结束程序广度优先搜索使用队列来实现1把根节点放到队列的末尾2每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱3找到所要找的元素时结束程序4如果遍历整个树还没有找到，结束程序DFSBFS四、程序代码TEMPLATEVOIDMGRAPHDFS/深度遍历BOOLVISITEDNEWBOOLNFORINTI0IVOIDMGRAPHDFSINTV,BOOLVISITEDVISITEDVTRUECOUTVOIDMGRAPHBFS/广度遍历BOOLVISITEDNEWBOOLNFORINTI0IVOIDMGRAPHBFSINTV,BOOLVISITEDSEQQUEUEQNVISITEDVTRUECOUTVOIDMGRAPHDIJKSTRAINTV,TD,INTPATH/迪杰斯特拉算法INTI,K,WIFVN1THROWOUTOFBOUNDSBOOLSNEWBOOLNFORI0ICONSTINTINFTY2147483640ENUMRESULTCODEUNDERFLOW,DUPLICATE,FAILURE,SUCCESS,NOTPRESENTTEMPLATECLASSGRAPH/抽象类PUBLICVIRTUALRESULTCODEINSERTINTU,INTV,TVIRTUALRESULTCODEREMOVEINTU,INTV0VIRTUALBOOLEXISTINTU,INTVCONST0PROTECTEDINTN,ETEMPLATE/循环队列类CLASSSEQQUEUEPUBLICSEQQUEUEINTMSIZESEQQUEUEDELETEQBOOLISEMPTYCONSTRETURNFRONTREARBOOLISFULLCONSTRETURNREAR1MAXSIZEFRONTBOOLFRONTTBOOLENQUEUETXBOOLDEQUEUEVOIDCLEARFRONTREAR0PRIVATEINTFRONT,REARINTMAXSIZETQTEMPLATESEQQUEUESEQQUEUEINTMSIZE/构造函数MAXSIZEMSIZEQNEWTMAXSIZEFRONTREAR0TEMPLATEBOOLSEQQUEUEFRONTTXQFRONT1MAXSIZERETURNTRUETEMPLATEBOOLSEQQUEUEENQUEUETX/在队尾插入XIFISFULLCOUTBOOLSEQQUEUEDEQUEUE/删除队头元素IFISEMPTYCOUTCLASSMGRAPHPUBLICGRAPH/邻接矩阵类PUBLICMGRAPHINTMSIZE,CONSTTMGRAPHRESULTCODEINSERTINTU,INTV,TRESULTCODEREMOVEINTU,INTVBOOLEXISTINTU,INTVCONSTVOIDDFSVOIDBFSPROTECTEDTATNOEDGEVOIDDFSINTV,BOOLVISITEDVOIDBFSINTV,BOOLVISITEDTEMPLATEMGRAPHMGRAPHINTMSIZE,CONSTTE0NOEDGENOEDGANEWTNFORINTI0IMGRAPHMGRAPH/析构函数FORINTI0IRESULTCODEMGRAPHINSERTINTU,INTV,TIFAUVNOEDGERETURNDUPLICATEAUVWERETURNSUCCESSTEMPLATERESULTCODEMGRAPHREMOVEINTU,INTV/删除函数IFUN1|VN1|UVRETURNFAILUREIFAUVNOEDGERETURNNOTPRESENTAUVNOEDGEERETURNSUCCESSTEMPLATEBOOLMGRAPHEXISTINTU,INTVCONST/判断边是否存在IFUN1|VN1|UV|AUVNOEDGERETURNFALSERETURNTRUETEMPLATEVOIDMGRAPHDFS/深度遍历BOOLVISITEDNEWBOOLNFORINTI0IVOIDMGRAPHDFSINTV,BOOLVISITEDVISITEDVTRUECOUTVOIDMGRAPHBFS/广度遍历BOOLVISITEDNEWBOOLNFORINTI0IVOIDMGRAPHBFSINTV,BOOLVISITEDSEQQUEUEQNVISITEDVTRUECOUT/结点类CLASSENODEPUBLICENODENEXTARCNULLENODEINTVERTEX,TWEIGHT,ENODENEXTADJVEXVERTEXWWEIGHTNEXTARCNEXTINTADJVEXTWENODENEXTARCTEMPLATECLASSLGRAPHPUBLICGRAPH/邻接表类PUBLICLGRAPHINTMSIZELGRAPHRESULTCODEINSERTINTU,INTV,TRESULTCODEREMOVEINTU,INTVBOOLEXISTINTU,INTVCONSTPROTECTEDENODEATEMPLATELGRAPHLGRAPHINTMSIZE/构造函数NMSIZEE0ANEWENODENFORINTI0ILGRAPHLGRAPH/析构ENODEP,QFORINTI0INEXTARCDELETEQQPDELETEATEMPLATEBOOLLGRAPHEXISTINTU,INTVCONST/判断边是否存在IFUN1|VN1|UVRETURNFALSEENODEPAUWHILEPIFPRETURNFALSEELSERETURNTRUETEMPLATERESULTCODELGRAPHINSERTINTU,INTV,TIFEXISTU,VRETURNDUPLICATEENODEPNEWENODEV,W,AUAUPERETURNSUCCESSTEMPLATERESULTCODELGRAPHREMOVEINTU,INTV/删除IFUN1|VN1|UVRETURNFAILUREENODEPAU,QQNULLWHILEPPPNEXTARCIFPRETURNNOTPRESENTIFQQNEXTARCPNEXTARCELSEAUPNEXTARCDELETEPERETURNSUCCESSINTMAIN/主函数INTN,GCOUTNMGRAPHAN,INFTYLGRAPHBNCOUTGINTANEWINTGINTBNEWINTGINTWNEWINTGFORINTI0IAIBIWIAINSERTAI,BI,WIBINSERTAI,BI,WICOUTCDIFAEXISTC,DCOUTEFIFAREMOVEE,FSUCCESSCOUTINCLUDECONSTINTINF2147483647ENUMRESULTCODEUNDERFLOW,DUPLICATE,FAILURE,SUCCESS,NOTPRESENT,OUTOFBOUNDSTEMPLATECLASSGRAPH/抽象类PUBLICVIRTUALRESULTCODEINSERTINTU,INTV,TW0VIRTUALRESULTCODEREMOVEINTU,INTV0VIRTUALBOOLEXISTINTU,INTVCONST0PROTECTEDINTN,ETEMPLATECLASSMGRAPHPUBLICGRAPH/邻接矩阵类PUBLICMGRAPHINTMSIZE,CONSTTNOEDGMGRAPHRESULTCODEINSERTINTU,INTV,TWRESULTCODEREMOVEINTU,INTVBOOLEXISTINTU,INTVCONSTINTCHOOSEINTD,BOOLSVOIDDIJKSTRAINTV,TD,INTPATHPROTECTEDTATNOEDGETEMPLATEMGRAPHMGRAPHINTMSIZE,CONSTTNOEDGNMSIZEE0NOEDGENOEDGANEWTNFORINTI0IMGRAPHMGRAPHFORINTI0IRESULTCODEMGRAPHINSERTINTU,INTV,TWIFUN1|VN1|UVRETURNFAILUREIFAUVNOEDGERETURNDUPLICATEAUVWERETURNSUCCESSTEMPLATERESULTCODEMGRAPHREMOVEINTU,INTVIFUN1|VN1|UVRETURNFAILUREIFAUVNOEDGERETURNNOTPRESENTAUVNOEDGEERETURNSUCCESSTEMPLATEBOOLMGRAPHEXISTINTU,INTVCONSTIFUN1|VN1|UV|AUVNOEDGERETURNFALSERETURNTRUETEMPLATEINTMGRAPHCHOOSEINTD,BOOLS/求最小DIINTI,MINPOSTMINMININFMINPOS1FOR