实验5--基本检索与周游方法算法设计

1《算法分析与设计》实验报告实验5基本检索与周游方法算法设计姓名xxx学号xxxxx班级xxxxxxx时间：xxxxxx地点：xxxx同组人：无指导教师：xxxxx实验目的1.掌握基本检索与周游方法算法设计的一般思想。2.掌握二元树、图的周游和检索算法。3.理解树、与或树、对策树周游与检索的思想和方法。实验内容1.二元树周游2.图的周游3.准备模拟二元树和模拟图的数据。4.用递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。5.用非递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。6.用递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。7.用非递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。实验环境硬件：Intel(R)Pentium(R)CPURAM:4G软件：Myeclipse2013编程语言：Java实验前准备1、算法设计：二元树周游a）、中根次序周游（LDR）ProcedureINORDER(T)//T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD//2IfT≠0thencallINORDER(LCHILD(T))callVISIT(T)callINORDER(RCHILD(T))endifendINORDERb）、先根次序周游（DLR）ProcedurePREORDER(T)//T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD//IfT≠0thencallVISIT(T)callPREORDER(LCHILD(T))callPREORDER(RCHILD(T))endifendPREORDERc）、后根次序周游（LRD）ProcedurePOSTORDER(T)//T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD//IfT≠0thencallPOSTORDER(LCHILD(T))callPOSTORDER(RCHILD(T))callVISIT(T)endifendINORDERd）、中根次序周游的非递归算法ProcedureINORDER1(T)//T是一棵二元树，每个结点有三个信息段：LCHILD、DATA、RCHILD////使用大小为m的栈的一个非递归算法//1integeri,m,STACK(M)2ifT=0thenreturnendif//T为空//3P←T;i←0//周游T；i为栈顶//4Loop5WhileLCHILD(P)≠0do//周游左子树//6i←i+17Ifimthenprint(‘stackoverflow’)8Stop9Endif10STACK(i)←P;P←LCHILD(P)11Repeat12Loop13CallVISIT(P)//P的左子树周游完//14P←RCHILD(P)15IfP≠0thenexitendif//周游右子树//16Ifi=0thenreturnendif317P←STACK(i);i←i-118Repeat//访问父结点//19repeatendINORDER1二、图的检索与周游a)图的宽度优先检索算法LineprocedureBFS(v)//宽度优先检索G，它在结点v开始执行。所有已访问结点都标上VISITED(i)=1。图G和数组VISITED是全程量。VISITED开始时都已置成0。//1VISITED(V)←1;u←v2将Q初始化库空//Q是未检测结点的队列//3Loop4For邻接于u的所有结点wdo5IfVISITED(w)=0thencallADDQ(w,Q)//w未检测//6VISITED(w)←17Endif8Repeat9IfQ为空thenreturnendif//不再有还未检测的结点//10CallDELETEQ(u,Q)//从队中取一个未检测的结点//11Repeat12endBFSb)图的宽度优先周游ProcedureBFT(G,n)DeclareVISITED(n)Fori←1tondo//将所有结点标注为未访问//VISITED←0RepeatFori←1tondo/反复调用BFS//IfVISITED(i)=0thencallBFS(i)endifRepeatendBFTc)图的深度优先检索算法procedureDFS(v)//已知一个n结点无向（或有向）图G=（V，E）以及初值已置为零的数组VISITED(1:n)。这个算法访问由v可以到达的所有结点。G和VISITED是全程量。//VISITED(V)←1;For邻接于v的每个结点wdoIfVISITED(w)=0thencallDFS(w)Endif4RepeatendDFSd)图的深度优先周游算法ProcedureDFT(G,n)DeclareVISITED(n)Fori←1tondo//将所有结点标注为未访问//VISITED←0RepeatFori←1tondo/反复调用DFS//IfVISITED(i)=0thencallDFS(i)endifRepeatendDFT1、程序设计：见附1实验步骤1、准备实验数据。准备模拟二元树和模拟图的数据。将二元树和模拟图的数据保存在文件中，在程序运行时读取，分别取名为btree.txt和|Cost.txt其中树的表现形式为第一行为根节点，其余若干行表示每行第一个数为子节点，第二个数为父节点如：5图的表示方式为第一行为节点数，边数和是否为有向图，剩下的行是图和节点所组成的邻接矩阵，文件表示如下图：其中∞表示为无穷即不可达2、递归方法设计二元树周游和检索BinaryTree.java根据算法设计的多段图向前处理法的sparks语言，写出相应的java程序，并调试验证通过。周游和检索的次序可以是先序、中序和后序。（其中的T为java中的泛型类，类似c语言中的宏定义）visit（）方法是访问该节点，将其加入到一个链表中，方便以后输出，同时可以减少计算时间时噪声影响。/***访问结点*@paramnode*/publicvoidvisit(BinaryTreeNodeTnode){list.add(node.getData());}/***递归实现二叉树的前序遍历*@paramBT6*/publicvoidpreOrderRecursive(BinaryTreeNodeTBT){if(BT!=null){visit(BT);preOrderRecursive(BT.getLChild());preOrderRecursive(BT.getRChild());}}/***递归实现二叉树的中序遍历*@paramBT*/publicvoidinOrderRecursive(BinaryTreeNodeTBT){if(BT!=null){inOrderRecursive(BT.getLChild());visit(BT);inOrderRecursive(BT.getRChild());}}/***递归实现二叉树的后序遍历*@paramBT*/publicvoidpostOrderRecursive(BinaryTreeNodeTBT){if(BT!=null){postOrderRecursive(BT.getLChild());visit(BT);postOrderRecursive(BT.getRChild());}}分别将其结果保存到文件中，分析其结果73、非递归方法设计二元树周游和检索BinaryTree.java根据最短路径问题的动态规划程序算法的sparks语言写出对应的java程序，并调试验证通过，对比递归和非递归程序，验证其正确性；/***非递归实现二叉树的中序遍历*@paramBT*/publicvoidinNotOrderRecursive(BinaryTreeNodeTBT){/*MyArrayStackBinaryTreeNodeTstack;intmaxStackSize=50;stack=newMyArrayStackBinaryTreeNodeT(maxStackSize);*/MyLinkedStackBinaryTreeNodeTstack=newMyLinkedStackBinaryTreeNodeT();BinaryTreeNodeTp=BT;while(p!=null||!stack.isEmpty()){while(p!=null){//找到左子树stack.push(p);p=p.getLChild();}if(!stack.isEmpty()){p=stack.pop();//先从栈中弹出要结点visit(p);//再访问根结点p=p.getRChild();//然后再指向右子树}}}输出结果保存到文件中，可以看出与递归结果一致；84、图的宽度优先检索和周游GraphSearch.java用邻接矩阵的方式表示整个图并将每个节点是否访问用一个数组表示，同时访问时将该结点加入到一个链表中去，方便以后输出使用并减少噪声影响；/***p图的宽度优先检索*pG，它在结点v开始执行，所有已访问结点都标上visited[i]=1,图G和数组visited是全程变量,visited开始记为0*@paramv*/publicvoidBFS(intv){visit(v);visited[v]=1;intu=v;LinkedListIntegerQ=newLinkedListInteger();//当作放置未检测结点的队列while(true){LinkedListEdgelist=G.costList[u];for(Edgee:list){//邻接于u的所有结点intw=e.v;if(visited[w]==0){Q.add(w);//将未检测的结点为w放入队列visit(w);//访问该结点visited[w]=1;//将该结点标记为1}}if(!Q.isEmpty()){//若队列不为空u=Q.remove();//将未访问的结点从队列取出赋给u，并准备下一轮循环}else{//队列为空表示所有结点访问结束return;}}}/***宽度优先周游算法*/publicvoidBFT(){for(inti=1;i=G.n;i++){//将所有结点标注为未访问//9visited[i]=0;}for(inti=1;iG.n;i++){//反复调动BFSif(visited[i]==0)BFS(i);}}宽度优先检索结果（最后一行为检索的结果顺序）宽度优先周游的结果：5、图的深度度优先检索和周游GraphSearch.java用邻接矩阵的方式表示整个图并将每个节点是否访问用一个数组表示，同时访问时将该结点加入到一个链表中去，方便以后输出使用并减少噪声影响；/***p图的深度优先检索*p已知一个n结点的无向（或有向图）G，以及初会已置为零的数组visited，这个算法可到达访问由v所可以到过的所有结点，G和visite是全程变量*@paramv*/publicvoidDFS(intv){visit(v);//访问该结点visited[v]=1;//将该结点标记为1LinkedListEdgelist=G.costList[v];10for(Edgee:list){//邻接于u的所有结点intw=e.v;if(visited[w]==0){DFS(w);}}}/***图的深度优先周游*/publicvoidDFT(){for(inti=1;i=G.n;i++){//将所有结点标注为未访问//visited[i]=0;}for(inti=1;iG.n;i++){//反复调动DFSif(visited[i]==0)DFS(i);}}深度优先检索结果（最后一行为检索的结果顺序）深度优先周游的结果：