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

《实验5 基本检索与周游方法算法设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法分析与设计》实验报告实验5基本检索与周游方法算法设计xxx学号xxxxx班级xxxxxxx时间：xxxxxx地点：xxxx同组人：无指导教师：xxxxx实验目的1.掌握基本检索与周游方法算法设计的一般思想。2.掌握二元树、图的周游和检索算法。3.理解树、与或树、对策树周游与检索的思想和方法。实验容1.二元树周游2.图的周游3.准备模拟二元树和模拟图的数据。4.用递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。5.用非递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。6.用递

2、归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。7.用非递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。实验环境硬件：Intel(R)Pentium(R)CPURAM:4G软件：Myeclipse2013编程语言：Java实验前准备1、算法设计：二元树周游a）、中根次序周游（LDR）ProcedureINORDER(T)//T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD//IfT≠0thencallINORDER(LCHILD(T))callVISIT(T

3、)callINORDER(RCHILD(T))endifendINORDERa）、先根次序周游（DLR）ProcedurePREORDER(T)//T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD//IfT≠0thencallVISIT(T)callPREORDER(LCHILD(T))callPREORDER(RCHILD(T))endifendPREORDERb）、后根次序周游（LRD）ProcedurePOSTORDER(T)//T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD//I

4、fT≠0thencallPOSTORDER(LCHILD(T))callPOSTORDER(RCHILD(T))callVISIT(T)endifendINORDERc）、中根次序周游的非递归算法ProcedureINORDER1(T)//T是一棵二元树，每个结点有三个信息段：LCHILD、DATA、RCHILD////使用大小为m的栈的一个非递归算法//1integeri,m,STACK(M)2ifT=0thenreturnendif//T为空//3P←T;i←0//周游T；i为栈顶//4Loop5WhileLCHILD(P)≠0do//周游左子

5、树//6i←i+17Ifi>mthenprint(‘stackoverflow’)8Stop9Endif10STACK(i)←P;P←LCHILD(P)11Repeat12Loop13CallVISIT(P)//P的左子树周游完//14P←RCHILD(P)1IfP≠0thenexitendif//周游右子树//2Ifi=0thenreturnendif3P←STACK(i);i←i-14Repeat//访问父结点//5repeatendINORDER1一、图的检索与周游a)图的宽度优先检索算法LineprocedureBFS(v)//宽度优先检索

6、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)//从队中取一个未检测的结点//11Repeat12en

7、dBFSb)图的宽度优先周游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;

8、For邻接于v的每个结点wdoIfVISITED(w)=0thencallDFS(w)EndifRepeatendDFSd