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

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

《实验5基本检索与周游方法算法设计.docx》由会员分享，可在线阅读，更多相关《实验5基本检索与周游方法算法设计.docx（28页珍藏版）》请在冰点文库上搜索。

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

《算法分析与设计》实验报告

实验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）

LoopLoopLoop

采用二元树相同的方法将村的结果存储在文件中，并以二叉树的方式表示树的结构，但解释与二叉树不中，其中左孩子表示子辈，右孩子表示同辈；查找是否是近亲时首先查找该节点，将该人的父辈祖先保存在栈中，采用一般树的后序遍历方法（即二叉树的中序周游方法）可以达到此效果，然后再比较它们在规定的代数如5代内是否有相同的祖先，如果有则表示他们为近亲；

publicbooleanisNearRelation（myTypex,myTypey,intn）{

MyLinkedStack>stack0=xStack（x）;

MyLinkedStack>stack1=xStack（y）;

if（stack0==null）{quals（k）））{

returntrue;

}

}

}

returnfalse;

}

/**

*采用后序遍历的方法对就二叉树的中序遍历方法，查找x元素，并将该结点的父辈们加入到一个栈中

*@paramx

*@return

*/

@SuppressWarnings（"unused"）

publicMyLinkedStack>xStack（myTypex）{

BinaryTreeNodep=（）;

MyLinkedStack>stack=newMyLinkedStack>（）;

while（p!

=null||!

（））{

while（p!

=null）{quals（x））{

quals（x）;

if（f）{

returnp;

}else{

（p）;

p=（）;

}

}

elseif（!

（））{

p=（）;

p=（）;

}

}

returnnull;

}

/**

*访问结点

*@paramnode

*/

publicvoidvisit（BinaryTreeNodenode）{

（））;

}

/**

*递归实现二叉树的前序遍历

*@paramBT

*/

publicvoidpreOrderRecursive（BinaryTreeNodeBT）{

if（BT!

=null）{

visit（BT）;

preOrderRecursive（））;

preOrderRecursive（））;

}

}

/**

*递归实现二叉树的中序遍历

*@paramBT

*/

publicvoidinOrderRecursive（BinaryTreeNodeBT）{

if（BT!

=null）{

inOrderRecursive（））;

visit（BT）;

inOrderRecursive（））;

}

}

/**

*递归实现二叉树的后序遍历

*@paramBT

*/

publicvoidpostOrderRecursive（BinaryTreeNodeBT）{

if（BT!

=null）{

postOrderRecursive（））;

postOrderRecursive（））;

visit（BT）;

}

}

/**

*非递归实现二叉树的中序遍历

*@paramBT

*/

publicvoidinNotOrderRecursive（BinaryTreeNodeBT）{

/*MyArrayStack>stack;

intmaxStackSize=50;

stack=newMyArrayStack>（maxStackSize）;*/

MyLinkedStack>stack=newMyLinkedStack>（）;

BinaryTreeNodep=BT;

while（p!

=null||!

（））{

while（p!

=null）{

xt";

Filesur=newFile（surDir,fileName）;

GraphG=null;

;

return;

}

=;

LinkedListle=newLinkedList（）;

if（isDirected）{][edge[k].v]=edge[k].cost;

if（!

{][edge[k].u]=edge[k].cost;

}

}

=COST;

}

publicvoidinitCostList（）{

costList=newLinkedList[n+1];

for（inti=0;i<;i++）{

costList[i]=newLinkedList（）;

}

if（edge==null）{

initEdges（）;

}

if（isDirected）{

for（inti=1;i<;i++）{

intu=edge[i].u;

intv=edge[i].v;

intcost=edge[i].cost;

Edgeed1=newEdge（u,v,cost）;

costList[u].add（ed1）;

}

}else{

for（inti=1;i<;i++）{

intu=edge[i].u;

intv=edge[i].v;

intcost=edge[i].cost;

Edgeed1=newEdge（u,v,cost）;

Edgeed2=newEdge（v,u,cost）;

costList[u].add（ed1）;

costList[v].add（ed2）;

}

}

}

publicvoiddisplayCost（）{

for（inti=0;i<;i++）{

for（intj=0;j

if（cost[i][j]>=0&&cost[i][j]<{

}else{

"∞"）;

}

if（j

"\t"）;

}

}

}

}

publicintgetN（）{

returnn;

}

publicvoidsetN（intn）{

=n;

}

publicintgetM（）{

returnm;

}

publicvoidsetM（intm）{

=m;

}

publicEdge[]getEdge（）{

returnedge;

}

publicvoidsetEdge（Edge[]edge）{

=edge;

}

publicint[][]getCost（）{

returncost;

}

publicvoidsetCost（int[][]cost）{

=cost;

}

publicbooleanisDirected（）{

returnisDirected;

}

publicvoidsetDirected（booleanisDirected）{

=isDirected;

}

}

/**

*边类

*@authorXT

*

*/

classEdge{

intu;

intv;

intcost;

publicEdge（）{};

publicEdge（intu,intv,intcost）{

=u;

=v;

=cost;

}

}

4、图的生成与读取

importReadEdgeData{

/**

*isDirected为true时表示读取有向边

*@paramsur

*@paramisDirected

*@returnGraph

*/

publicstaticGraphreadEdges（Filesur,booleanisDirected）{

Filedate=sur;

if（!

（）||!

（））{

"文件不存在或有误，请检查！

"）;

returnnull;

}

FileReaderinReader;

try{

inReader=newFileReader（date）;;

returnnull;

}

BufferedReaderinStream=newBufferedReader（inReader）;;

returnnull;

}

BufferedWriteroutStream=newBufferedWriter（outWriter）;+""+[i].v+""+[i].cost+"\r\n"）;

}

（）;

（）;

}catch（IOExceptione）{

;

returnnull;

}

BufferedWriteroutStream=newBufferedWriter（outWriter）;ength;j++）{ength-1）{

（"\t"）;

}

}

;

returnnull;

}

BufferedReaderinStream=newBufferedReader（inReader）;;

returnnull;

}

BufferedReaderinStream=newBufferedReader（inReader）;quals（"true"））{

isDirected=true;

}

cost=newint[n+1][n+1];

inti=0;

while（（str=（））!

=null&&i<=m）{

strAry=（"\\s|\\t"）;

for（intj=0;j<;j++）{

if（isNum（strAry[j]））{

cost[i][j]=（strAry[j]）;

}else{

cost[i][j]=;

}

}

i++;

}

graph=newGraph（cost,isDirected）;

if（n!

=||m!

={

"所记结点数或边数与实际不符！

"）;

}

（）;

（）;

}

}catch（IOExceptione）{

（[0-9]+））|（[.]（[0-9]+）））$"）;

}

/**

*随机生成无向图

*@paramn

*@paramm

*@paramminCost

*@parammaxCost

*@return

*/

publicstaticGraphradomGraph（intn,intm,intminCost,intmaxCost）{

if（m>n*n*（n-1）/2）{xt"）;

if（writeEdges（dest,g）!

=null）{

"文件写入成功！

"）;

}

}

n+=15;

k+=1;

}

}

/*

*生成有向图

*/

publicstaticvoidrandom1（）{

StringdestDir="E:

\\我的文档\\大三下\\算法分析与设计\\实验\\实验4动态规划算法设计\\data";

StringdestName="Edges";

intb=10;xt"）;

if（writeEdges（dest,g）!

=null）{

"文件写入成功！

"）;

}

}

}

}

publicstaticvoidrandom3（）{

StringdestDir="E:

\\我的文档\\大三下\\算法分析与设计\\实验\\实验5基本检索与周游方法算法设计\\data";

StringdestName="Cost";

intb=10;xt"）;

（）;

/*（）;*/

if（writeCost（dest,g）!

=null）{

"文件写入成功！

"）;

}

}

}

}

publicstaticvoidrandom4（）{

StringsurDir="C:

\\Users\\XT\\Desktop\\新建文件夹

（2）\\edges";

GraphG=null;

StringfileName="";

Filesur=newFile（surDir,fileName）;

叉树节点类

publicclassBinaryTreeNode{

privateTdata;

privateBinaryTreeNodeLChild;

privateBinaryTreeNodeRChild;

publicBinaryTreeNode（）{}

publicBinaryTreeNode（Tdata,BinaryTreeNodeLChild,BinaryTreeNodeRChild）{

=data;

=LChild;

=RChild;

}

publicBinaryTreeNode（Tdata）{

=data;

}

publicTgetData（）{

returndata;

}

publicvoidsetData（Tdata）{

=data;

}

publicBinaryTreeNodegetLChild（）{

returnLChild;

}

publicvoidsetLChild（BinaryTreeNodelChild）{

LChild=lChild;

}

publicBinaryTreeNodegetRChild（）{

returnRChild;

}

publicvoidsetRChild（BinaryTreeNoderChild）{

RChild=rChild;

}

/**

*为一般树添加儿子节点,左左孩子表示儿子节点，右孩子表示兄弟节点

*@paramsonNode

*/

publicvoidaddSonNode（BinaryTreeNodesonNode）{

BinaryTreeNodep=this;

if（p!

=null）{

if（）==null）{

类

package;

publicclassMyLinkedStack{

/**

*栈顶指针

*/

privateNodetop;

/**

*栈的长度

*/

privateintsize;

publicMyLinkedStack（）{

top=null;

size=0;

}

@Override

publicbooleanisEmpty（）{

returnsize==0;

}

@Override

publicvoidclear（）{

top=null;

size=0;

}

@Override

publicintlength（）{

returnsize;

}

@Override

publicbooleanpush（Tdata）{

Nodenode=newNode（）;

=data;

=top;

ata）;

}

}

8.查找族谱中的近亲

package;

importclassFamilyTree{

BinaryTreefamilyTree;

publicFamilyTree（）{}

publicFamilyTree（BinaryTreetree）{

familyTree=tree;

}

/**

*比较x和y是不是n代以内的近亲

*@paramx

*@paramy

*@paramn

*@return

*/

publicbooleanisNearRelation（myTypex,myTypey,intn）{

MyLinkedStack>stack0=xStack（x）;

MyLinkedStack>stack1=xStack（y）;

if（stack0==null）{quals（k）））{

returntrue;

}

}

}

returnfalse;

}

/**

*采用后序遍历的方法对就二叉树的中序遍历方法，查找x元素，并将该结点的父辈们加入到一个栈中

*@paramx

*@return

*/

@SuppressWarnings（"unused"）

publicMyLinkedStack>xStack（myTypex）{

BinaryTreeNodep=（）;

MyLinkedStack>stack=newMyLinkedStack>（）;

while（p!

=null||!

（））{

while（p!

=null）{quals（x））{//找到的话直接结束查找，最终返回的是其父辈的终成的栈

returnstack;

}

p=（）;//然后再指向右子树

}

}

}//未找到返回空

returnnull;

}

publicstaticvoidmain（String[]args）{

StringdestDir="E:

\\我的文档\\大三下\\算法分析与设计\\实验\\实验5基本检索与周游方法算法设计\\data";

StringfileName="";

Filesur=newFile（destDir,fileName）;

BinaryTreetree=（sur）;

FamilyTreef=newFamilyTree（tree）;

Stringx="F2";

Stringy="E8";

myTypexn=newmyType（x）;

myTypeyn=newmyType（y）;

intdd=5;

if（xn,yn,dd））{

"号和"+y+"是"+dd+"代以内的探亲！

"）;

}

else{

"号和"+y+"不是"+dd+"代以内的探亲！

"）;

}

}

}