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

第四次实验报告 图的邻接表存储实现及深度优先遍历 学号0708140119 电子072 姓名 陆萍萍一、 问题描述1、 程序所能达到的基本功能 构建以邻接表形式存储的表及实现深度优先遍历并输出结果。 2、 输入的形式和输入值的范围： 根据提示进行输入：先输入要构建的表的结点数和边数，要求是整型；输入各结点的代号，这里用char型，也可在源程序中改变其它形式；输入各边的头结点和尾结点的代号；3、 输出的形式 若正常输入，则输出深度优先遍历的最后结果。用各结点的代码表示。测试数据要求第一组数据： 结点数和边数：4 4 结点名称：a b c d 边：a-b a-c b-c c-d 输出a-b-c-d-over!第二组数据：图如下：输出a-b-c-d-e-f-g-over!4、 概要设计1、 抽象数据类型，它们的作用/图的结点类templateclass TVex;/图类templateclass Graph/链表存储2主程序流程及模块调用关系(1) 主程序模块： void main构造一个图，对T实例化（char）。调用Graph中的Create函数；调用Graph中的DFS函数；（2）调用关系如下TemplateTlinklistTemplateTvex TemplateGraph2、 核心算法的粗线条伪码 5、 详细设计（要求主要变量和语句加注释）1、 抽象数据类型的实现：包括类型定义和各个操作的实现。1) TVex的详细设计（1）私有数据类型的定义private： T m_elem;TLinklist m_arcs; 2)Graph的详细设计（1）私有数据类型的定义private：TVex Vextexmaxnum;int vexnum;int arcnum;int kind;int symbolmaxnum;（2）公有函数成员的定义Graph()；void Create();int LocateVex(T v);void DFS();void DFS_IN(int i); (3)具体实现 templatevoid Graph:Create() T v1,v2; int i,j; cout*基本信息*endl; coutvexnumarcnum; cout*结点*endl; for(int l=0;lvexnum;l+) cout请输入第l+1Vextexl.m_elem; cout*边数*endl; for(int k=0;karcnum;k+) cout请输入第k+1v1v2; i=LocateVex(v1); j=LocateVex(v2); Vextexi.m_arcs.InsertLate(j); Vextexj.m_arcs.InsertLate(i); cout*结果*endl;templateint Graph:LocateVex(T v) for(int i=0;ivexnum&Vextexi.m_elem!=v;i+); if(i=vexnum) return -1; else return i;templatevoid Graph:DFS() DFS_IN(0);coutover!endl;templatevoid Graph:DFS_IN(int i)int index; symboli=1; coutVextexi.m_elem; for(int j=0;j+) index=Vextexi.m_arcs.GetElem(j+1); if(index!=-1) if(symbolindex!=1) DFS_IN(index);else break; 2、 其他主要算法的实现将次要算法均设为Graph的公有函数成员3、 主程序的实现Void main()huffmanTree h;int *ww,n;char *cc;coutn;ww=new intn;cc=new charn;cout请依次输入节点名称和权重：endl;for(int i=1;i=n;i+)cout第i个endl;coutcci-1;coutwwi-1;h.CreatehuffmanTree(cc,ww,n);h.huffmanTreecoding();四 .调试分析1、 设计与调试过程中遇到的问题及分析、体会（1） 这个实验较简单，经过对书本上已经给出的c版程序的分析，很容易就写出了对整个实验的大体思路。（2） 这个程序不难，但前提是Tlinklist已经做得做够全面，在这个实验中发现了Tlinklist的很多不足，经过改进，才使得程序简单明了，如在其中增加了获取长度，获取数据，在链表麽增加数据几个函数，解决很多问题。（3） 该程