图的邻接表存储实现及深度优先遍历

《图的邻接表存储实现及深度优先遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四次实验报告图的邻接表存储实现及深度优先遍历学号0708140119电子072姓名陆萍萍一、问题描述1、程序所能达到的基本功能构建以邻接表形式存储的表及实现深度优先遍历并输出结果。2、输入的形式和输入值的范围：根据提示进行输入：先输入要构建的表的结点数和边数，要求是整型；输入各结点的代号，这里用char型，也可在源程序中改变其它形式；输入各边的头结点和尾结点的代号；3、输出的形式若正常输入，则输出深度优先遍历的最后结果。用各结点的代码表示。测试数据要求第一组数据：结点数和边数：44结点名称：abcd边：a-ba-cb-cc-d输出a-b-c-d-over!第

2、二组数据：图如下：输出a-b-c-d-e-f-g-over!3、概要设计1、抽象数据类型，它们的作用//图的结点类templateclassTVex{};//图类templateclassGraph{}//链表存储2主程序流程及模块调用关系(1)主程序模块：voidmain{构造一个图，对T实例化（char）。调用Graph中的Create函数；调用Graph中的DFS函数；}（2）调用关系如下TemplateTlinklistTemplateTvexTemplateGraph1、

3、核心算法的粗线条伪码3、详细设计（要求主要变量和语句加注释）1、抽象数据类型的实现：包括类型定义和各个操作的实现。1)TVex的详细设计（1）私有数据类型的定义private：Tm_elem;TLinklistm_arcs;2)Graph的详细设计（1）私有数据类型的定义private：TVexVextex[maxnum];intvexnum;intarcnum;intkind;intsymbol[maxnum];（2）公有函数成员的定义Graph()；voidCreate();intLocateVex(Tv);voidDFS();voidDF

4、S_IN(inti);(3)具体实现★templatevoidGraph::Create(){Tv1,v2;inti,j;cout<<"*********************基本信息*****************************"<>vexnum>>arcnum;cout<<"***********************结点***************************"<

5、入第"<>Vextex[l].m_elem;}cout<<"***********************边数***************************"<>v1>>v2;i=LocateVex(v1);j=LocateVex(v2);Vextex[i].m_arcs.InsertLate(j);Vextex[j].m_arcs.InsertLate(i);}cout<<"****

6、********************结果**************************"<intGraph::LocateVex(Tv){for(inti=0;ivoidGraph::DFS(){DFS_IN(0);cout<<"over!"<voidGraph::DF

7、S_IN(inti){intindex;symbol[i]=1;cout<";for(intj=0;;j++){index=Vextex[i].m_arcs.GetElem(j+1);if(index!=-1){if(symbol[index]!=1)DFS_IN(index);}elsebreak;}}1、其他主要算法的实现将次要算法均设为Graph的公有函数成员2、主程序的实现Voidmain(){huffmanTreeh;int*ww,n;char*cc;cout<<"请输入叶子节点的个数：";c

8、in>>n;ww=newint[n];