實驗5--基本檢索與周游方法算法設(shè)計

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法分析與設(shè)計實驗報告實驗5基本檢索與周游方法算法設(shè)計姓名 xxx 學(xué)號 xxxxx 班級 xxxxxxx時間：xxxxxx 地點：xxxx同 組 人：無指導(dǎo)教師：xxxxx實驗?zāi)康?1. 掌握基本檢索與周游方法算法設(shè)計的一般思想。2. 掌握二元樹、圖的周游和檢索算法。3. 理解樹、與或樹、對策樹周游與檢索的思想和方法。實驗內(nèi)容 1. 二元樹周游2. 圖的周游3. 準(zhǔn)備模擬二元樹和模擬圖的數(shù)據(jù)。4. 用遞歸方法設(shè)計二元樹周游和檢索程序，調(diào)試通過。周游和檢索的次序可以是先序、中序和后序。5. 用非遞歸方法設(shè)計二元樹周游和檢索程序，調(diào)試通過。周游和檢索的次序可以是先序、中

2、序和后序。6. 用遞歸方法設(shè)計圖的周游程序，調(diào)試通過。周游的次序可以是深度優(yōu)先，也可以是寬度優(yōu)先。7. 用非遞歸方法設(shè)計圖的周游程序，調(diào)試通過。周游的次序可以是深度優(yōu)先，也可以是寬度優(yōu)先。實驗環(huán)境 硬件： Intel(R) Pentium(R) CPU RAM:4G軟件：Myeclipse2013編程語言：Java實驗前準(zhǔn)備1、 算法設(shè)計：二元樹周游a）、 中根次序周游（LDR）Procedure INORDER(T)/T是一棵二元樹。T的每個結(jié)點有三個信息段：LCHILD、DATA、RCHILD/If T0 then call INORDER(LCHILD(T) call VISIT(T)

3、call INORDER(RCHILD(T)endifendINORDERb）、 先根次序周游（DLR）Procedure PREORDER(T)/T是一棵二元樹。T的每個結(jié)點有三個信息段：LCHILD、DATA、RCHILD/If T0 then call VISIT(T)call PREORDER(LCHILD(T) call PREORDER(RCHILD(T)endifendPREORDERc）、 后根次序周游（LRD）Procedure POSTORDER(T)/T是一棵二元樹。T的每個結(jié)點有三個信息段：LCHILD、DATA、RCHILD/If T0 then call POSTO

4、RDER(LCHILD(T) call POSTORDER(RCHILD(T) call VISIT(T)endifendINORDERd）、 中根次序周游的非遞歸算法Procedure INORDER1(T)/T是一棵二元樹，每個結(jié)點有三個信息段：LCHILD、DATA、RCHILD/使用大小為m的棧的一個非遞歸算法/1 integer i, m, STACK(M)2 if T=0 then return endif /T為空/3 PT; i0 /周游T；i為棧頂/4 Loop5 While LCHILD(P)0 do /周游左子樹/6 ii+17 If i>m then print(

5、stack overflow)8 Stop9 Endif10 STACK(i) P; PLCHILD(P)11 Repeat12 Loop13 Call VISIT(P) /P的左子樹周游完/14 PRCHILD(P)15 If P0 then exit endif /周游右子樹/16 If i=0 then return endif17 PSTACK(i); ii-118 Repeat /訪問父結(jié)點/19 repeatendINORDER1二、 圖的檢索與周游 a) 圖的寬度優(yōu)先檢索算法Line procedure BFS(v)/寬度優(yōu)先檢索G，它在結(jié)點v開始執(zhí)行。所有已訪問結(jié)點都標(biāo)上VIS

6、ITED(i)=1。圖G和數(shù)組VISITED是全程量。VISITED開始時都已置成0。/1 VISITED(V) 1; uv2 將Q初始化庫空 /Q是未檢測結(jié)點的隊列/3 Loop4 For 鄰接于u的所有結(jié)點w do 5 If VISITED(w)=0 then call ADDQ(w, Q) /w未檢測/6 VISITED(w) 17 Endif8 Repeat9 If Q為空 then return endif /不再有還未檢測的結(jié)點/10 Call DELETEQ(u, Q) /從隊中取一個未檢測的結(jié)點/11 Repeat12 endBFSb) 圖的寬度優(yōu)先周游Procedure BF

7、T(G, n)Declare VISITED(n)For i1 to n do /將所有結(jié)點標(biāo)注為未訪問/ VISITED0RepeatFor i1 to n do /反復(fù)調(diào)用BFS/ If VISITED(i)=0 then call BFS(i) endifRepeatendBFTc) 圖的深度優(yōu)先檢索算法procedure DFS(v)/已知一個n結(jié)點無向（或有向）圖G=（V，E）以及初值已置為零的數(shù)組VISITED(1: n)。這個算法訪問由v可以到達(dá)的所有結(jié)點。G和VISITED是全程量。/ VISITED(V) 1; For 鄰接于v的每個結(jié)點w do If VISITED(w)=

8、0 then call DFS(w) Endif RepeatendDFSd) 圖的深度優(yōu)先周游算法Procedure DFT(G, n)Declare VISITED(n)For i1 to n do /將所有結(jié)點標(biāo)注為未訪問/ VISITED0RepeatFor i1 to n do /反復(fù)調(diào)用DFS/ If VISITED(i)=0 then call DFS(i) endifRepeatendDFT1、 程序設(shè)計：實驗步驟1、準(zhǔn)備實驗數(shù)據(jù)。準(zhǔn)備模擬二元樹和模擬圖的數(shù)據(jù)。將二元樹和模擬圖的數(shù)據(jù)保存在文件中，在程序運行時讀取，分別取名為btree.txt和|Cost.txt其中樹的表現(xiàn)形式

9、為第一行為根節(jié)點，其余若干行表示每行第一個數(shù)為子節(jié)點，第二個數(shù)為父節(jié)點如：圖的表示方式為第一行為節(jié)點數(shù)，邊數(shù)和是否為有向圖，剩下的行是圖和節(jié)點所組成的鄰接矩陣，文件表示如下圖：其中表示為無窮即不可達(dá)2、遞歸方法設(shè)計二元樹周游和檢索根據(jù)算法設(shè)計的多段圖向前處理法的sparks語言，寫出相應(yīng)的java程序，并調(diào)試驗證通過。周游和檢索的次序可以是先序、中序和后序。（其中的<T>為java中的泛型類，類似c語言中的宏定義）visit（）方法是訪問該節(jié)點，將其加入到一個鏈表中，方便以后輸出，同時可以減少計算時間時噪聲影響。/* * 訪問結(jié)點 * param node */ public vo

10、id visit(BinaryTreeNode<T> node) list.add(node.getData(); /* * 遞歸實現(xiàn)二叉樹的前序遍歷 * param BT */ public void preOrderRecursive(BinaryTreeNode<T> BT) if(BT!=null) visit(BT); preOrderRecursive(BT.getLChild(); preOrderRecursive(BT.getRChild(); /* * 遞歸實現(xiàn)二叉樹的中序遍歷 * param BT */ public void inOrderRec

11、ursive(BinaryTreeNode<T> BT) if(BT!=null) inOrderRecursive(BT.getLChild(); visit(BT); inOrderRecursive(BT.getRChild(); /* * 遞歸實現(xiàn)二叉樹的后序遍歷 * param BT */ public void postOrderRecursive(BinaryTreeNode<T> BT) if(BT!=null) postOrderRecursive(BT.getLChild(); visit(BT); postOrderRecursive(BT.get

12、RChild(); 分別將其結(jié)果保存到文件中，分析其結(jié)果3、非遞歸方法設(shè)計二元樹周游和檢索根據(jù)最短路徑問題的動態(tài)規(guī)劃程序算法的sparks語言寫出對應(yīng)的java程序，并調(diào)試驗證通過，對比遞歸和非遞歸程序，驗證其正確性；/* * 非遞歸實現(xiàn)二叉樹的中序遍歷 * param BT */ public void inNotOrderRecursive(BinaryTreeNode<T> BT) /*MyArrayStack<BinaryTreeNode<T>> stack; int maxStackSize=50; stack=new MyArrayStack&l

13、t;BinaryTreeNode<T>>(maxStackSize);*/ MyLinkedStack<BinaryTreeNode<T>> stack=new MyLinkedStack<BinaryTreeNode<T>>(); BinaryTreeNode<T> p=BT; while(p!=null|!stack.isEmpty() while(p!=null)/找到左子樹 stack.push(p); p=p.getLChild(); if(!stack.isEmpty() p=stack.pop();/先

14、從棧中彈出要結(jié)點 visit(p);/再訪問根結(jié)點 p=p.getRChild();/然后再指向右子樹 輸出結(jié)果保存到文件中，可以看出與遞歸結(jié)果一致；4、圖的寬度優(yōu)先檢索和周游用鄰接矩陣的方式表示整個圖并將每個節(jié)點是否訪問用一個數(shù)組表示，同時訪問時將該結(jié)點加入到一個鏈表中去，方便以后輸出使用并減少噪聲影響；/* * <p>圖的寬度優(yōu)先檢索 * <p>G，它在結(jié)點v開始執(zhí)行，所有已訪問結(jié)點都標(biāo)上visitedi=1,圖G和數(shù)組visited是全程變量,visited開始記為0 * param v */ public void BFS(int v) visit(v); vi

15、sitedv=1; int u=v; LinkedList<Integer> Q=new LinkedList<Integer>();/當(dāng)作放置未檢測結(jié)點的隊列 while(true) LinkedList<Edge> list=G.costListu; for(Edge e:list)/鄰接于u的所有結(jié)點 int w=e.v; if(visitedw=0) Q.add(w);/將未檢測的結(jié)點為w放入隊列 visit(w);/訪問該結(jié)點 visitedw=1;/將該結(jié)點標(biāo)記為1 if(!Q.isEmpty()/若隊列不為空 u=Q.remove();/將未訪

16、問的結(jié)點從隊列取出賦給u，并準(zhǔn)備下一輪循環(huán) else/隊列為空表示所有結(jié)點訪問結(jié)束 return; /* * 寬度優(yōu)先周游算法 */ public void BFT() for(int i=1;i<=G.n;i+)/將所有結(jié)點標(biāo)注為未訪問/ visitedi=0; for(int i=1;i<G.n;i+)/反復(fù)調(diào)動BFS if(visitedi=0) BFS(i); 寬度優(yōu)先檢索結(jié)果（最后一行為檢索的結(jié)果順序）寬度優(yōu)先周游的結(jié)果：5、圖的深度度優(yōu)先檢索和周游用鄰接矩陣的方式表示整個圖并將每個節(jié)點是否訪問用一個數(shù)組表示，同時訪問時將該結(jié)點加入到一個鏈表中去，方便以后輸出使用并減少噪

17、聲影響；/* * <p>圖的深度優(yōu)先檢索 * <p>已知一個n結(jié)點的無向（或有向圖）G，以及初會已置為零的數(shù)組visited，這個算法可到達(dá)訪問由v所可以到過的所有結(jié)點，G和visite是全程變量 * param v */ public void DFS(int v) visit(v);/訪問該結(jié)點 visitedv=1;/將該結(jié)點標(biāo)記為1 LinkedList<Edge> list=G.costListv; for(Edge e:list)/鄰接于u的所有結(jié)點 int w=e.v; if(visitedw=0) DFS(w); /* * 圖的深度優(yōu)先周游

18、*/ public void DFT() for(int i=1;i<=G.n;i+)/將所有結(jié)點標(biāo)注為未訪問/ visitedi=0; for(int i=1;i<G.n;i+)/反復(fù)調(diào)動DFS if(visitedi=0) DFS(i); 深度優(yōu)先檢索結(jié)果（最后一行為檢索的結(jié)果順序）深度優(yōu)先周游的結(jié)果：5、【附】查找族譜中的近親采用二元樹相同的方法將村的結(jié)果存儲在文件中，并以二叉樹的方式表示樹的結(jié)構(gòu)，但解釋與二叉樹不中，其中左孩子表示子輩，右孩子表示同輩；查找是否是近親時首先查找該節(jié)點，將該人的父輩祖先保存在棧中，采用一般樹的后序遍歷方法（即二叉樹的中序周游方法）可以達(dá)到此效果

19、，然后再比較它們在規(guī)定的代數(shù)如5代內(nèi)是否有相同的祖先，如果有則表示他們?yōu)榻H；public boolean isNearRelation(myType x,myType y,int n) MyLinkedStack<BinaryTreeNode<myType>> stack0=xStack(x); MyLinkedStack<BinaryTreeNode<myType>> stack1=xStack(y); if(stack0=null)/若有一個結(jié)點未找到 System.out.println("未找到結(jié)點"+x.data)

20、; return false; else if(stack1=null) System.out.println("未找到結(jié)點"+y.data); return false; int i=0; LinkedList<myType> arryx=new LinkedList<myType>(); LinkedList<myType> arryy=new LinkedList<myType>(); /將兩個結(jié)點的父輩們組成的棧加入鏈表中，只取前n個 while(!stack0.isEmpty()&&i<n) B

21、inaryTreeNode<myType> s=stack0.pop(); myType m=s.getData(); arryx.add(m); i+; i=0; while(!stack1.isEmpty()&&i<n) BinaryTreeNode<myType> s=stack1.pop(); myType m=s.getData(); arryy.add(m); i+; /比較鏈表是否有相同元素 for(int j=0;j<arryx.size();j+) for(int k=0;k<arryy.size();k+) if(a

22、rryx.get(j).equals(arryy.get(k) return true; return false; /* * 采用后序遍歷的方法對就二叉樹的中序遍歷方法，查找x元素，并將該結(jié)點的父輩們加入到一個棧中 * param x * return */ SuppressWarnings("unused") public MyLinkedStack<BinaryTreeNode<myType>> xStack(myType x) BinaryTreeNode<myType> p=familyTree.getRoot(); MyLin

23、kedStack<BinaryTreeNode<myType>> stack=new MyLinkedStack<BinaryTreeNode<myType>>(); while(p!=null|!stack.isEmpty() while(p!=null)/先找到子樹的最左邊結(jié)點 stack.push(p); p=p.getLChild(); if(!stack.isEmpty() if(!stack.isEmpty() p=stack.pop();/先從棧中彈出要結(jié)點 if(p.getData().equals(x)/找到的話直接結(jié)束查找，最

24、終返回的是其父輩的終成的棧 return stack; p=p.getRChild();/然后再指向右子樹 /未找到返回空 return null; 族譜結(jié)構(gòu)為（從1開始順序編號）表示的圖形為用二叉樹表示如下：比如查找F2和E8是否是5代以內(nèi)的近親，由圖中可以清楚看到是，結(jié)果與之一致查找它們是否為4代以內(nèi)的近親時，可以看出它是不是的實驗結(jié)果及其分析1、遞歸方法設(shè)計二元樹周游和檢索如果訪問一個結(jié)點所需要的時間和空間為O(1)，n個結(jié)點每個結(jié)點均門訪問一次，這么算法的時間和空間復(fù)雜度均為O(n)；2、圖的寬度優(yōu)先檢索和周游圖的寬度優(yōu)先檢索，t(n,e)=O(n+e)圖的寬度優(yōu)先檢索BFSn1020

25、30405060708090100次運行耗時12325244765796713351774227628523452圖的寬度度優(yōu)先周游，t(n)=O(n2)圖的寬度優(yōu)先周游BFTn102030405060708090100次運行耗時126249440665976134917702290281134773、圖的深度優(yōu)先檢索和周游圖的深度度優(yōu)先檢索，t(n,e)=O(n+e)圖的深度優(yōu)先檢索DFSn102030405060708090100次運行耗時13918035463496813351749230429813742圖的深度度優(yōu)先周游，t(n)=O(n2)圖的深度優(yōu)先周游DFTn102030405

26、060708090100次運行耗時174198363654967134217822328299335964、總結(jié)基本的檢索和周游算法主要包括對樹和圖各結(jié)點的遍歷訪問。二元樹的訪問根據(jù)每個子樹的訪問次序可分為前序周游，中序周游和后序周游，三種方法周游所需要的時間和空間復(fù)雜度相同，但過程中在棧中所存儲和結(jié)點不同，在實際情況中可根據(jù)需要采取不同的周游方法（比如在查找近親一題中采用了后序周游（對應(yīng)的是二元樹的中序周游）所具有的特性，即訪問某結(jié)點時，其祖先結(jié)點在棧中）；圖的檢索又分為寬度和深度檢索和周游，所需要的時間和空間復(fù)雜度也相同的。 附：源代碼1、二元樹周游和檢索BinaryTree.javaim

27、port java.io.File;import java.util.LinkedList;public class BinaryTree<T> BinaryTreeNode<T> root; LinkedList<T> list; public BinaryTree() list=new LinkedList<T>(); public BinaryTree(BinaryTreeNode<T> root) this.root=root; list=new LinkedList<T>(); public BinaryTree

28、Node<T> getRoot() return root; public void setRoot(BinaryTreeNode<T> root) this.root = root; /* * 采用非遞歸前序遍歷查找結(jié)點x，并返回該結(jié)點 * param BT * param x * return 找到返回該節(jié)點，否則返回空 */ public BinaryTreeNode<T> allBinaryTreeSearch(BinaryTreeNode<T> BT,T x) BinaryTreeNode<T> p=BT; MyLinked

29、Stack<BinaryTreeNode<T>> stack=new MyLinkedStack<BinaryTreeNode<T>>(); while(p!=null|!stack.isEmpty() if(p!=null) boolean f=false; if(x instanceof Integer) f=(p.getData()=x); else f=p.getData().equals(x); if(f) return p; else stack.push(p); p=p.getLChild(); else if(!stack.isE

30、mpty() p=stack.pop(); p=p.getRChild(); return null; /* * 訪問結(jié)點 * param node */ public void visit(BinaryTreeNode<T> node) list.add(node.getData(); /* * 遞歸實現(xiàn)二叉樹的前序遍歷 * param BT */ public void preOrderRecursive(BinaryTreeNode<T> BT) if(BT!=null) visit(BT); preOrderRecursive(BT.getLChild(); p

31、reOrderRecursive(BT.getRChild(); /* * 遞歸實現(xiàn)二叉樹的中序遍歷 * param BT */ public void inOrderRecursive(BinaryTreeNode<T> BT) if(BT!=null) inOrderRecursive(BT.getLChild(); visit(BT); inOrderRecursive(BT.getRChild(); /* * 遞歸實現(xiàn)二叉樹的后序遍歷 * param BT */ public void postOrderRecursive(BinaryTreeNode<T> B

32、T) if(BT!=null) postOrderRecursive(BT.getLChild(); postOrderRecursive(BT.getRChild(); visit(BT); /* * 非遞歸實現(xiàn)二叉樹的中序遍歷 * param BT */ public void inNotOrderRecursive(BinaryTreeNode<T> BT) /*MyArrayStack<BinaryTreeNode<T>> stack; int maxStackSize=50; stack=new MyArrayStack<BinaryTree

33、Node<T>>(maxStackSize);*/ MyLinkedStack<BinaryTreeNode<T>> stack=new MyLinkedStack<BinaryTreeNode<T>>(); BinaryTreeNode<T> p=BT; while(p!=null|!stack.isEmpty() while(p!=null)/找到左子樹 stack.push(p); p=p.getLChild(); if(!stack.isEmpty() p=stack.pop();/先從棧中彈出要結(jié)點 vis

34、it(p);/再訪問根結(jié)點 p=p.getRChild();/然后再指向右子樹 public static BinaryTreeNode<Character> init0() BinaryTreeNode<Character> f=new BinaryTreeNode<Character>('f'); BinaryTreeNode<Character> g=new BinaryTreeNode<Character>('g'); BinaryTreeNode<Character> e=new

35、BinaryTreeNode<Character>('e',g,null); BinaryTreeNode<Character> d=new BinaryTreeNode<Character>('d'); BinaryTreeNode<Character> c=new BinaryTreeNode<Character>('c',null,f); BinaryTreeNode<Character> b=new BinaryTreeNode<Character>(&#

36、39;b',d,e); BinaryTreeNode<Character> a=new BinaryTreeNode<Character>('a',b,c); return a; public static void exp0() BinaryTreeNode<Character> root=init0(); BinaryTree<Character> T=new BinaryTree<Character>(root); /T.preOrderRecursive(root); /T.inOrderRecursi

37、ve(root); /T.postOrderRecursive(root); T.inNotOrderRecursive(root); System.out.println(T.list); public static void exp1() String destDir="E:我的文檔大三下算法分析與設(shè)計實驗實驗5 基本檢索與周游方法算法設(shè)計data" String fileName="btree.txt" File sur=new File(destDir,fileName); BinaryTree<myType> tree=TreeFi

38、le.readTreeFile(sur); /tree.preOrderRecursive(tree.getRoot(); /tree.inOrderRecursive(tree.getRoot(); /tree.postOrderRecursive(tree.getRoot(); tree.inNotOrderRecursive(tree.getRoot(); for(myType mt:tree.list) System.out.print(mt.getData()+"=>"); public static void main(String args) exp1(

39、); 2、圖的檢索和周游GraphSearch.javaimport java.io.File;import java.util.Arrays;import java.util.LinkedList;public class GraphSearch private Graph G; private int visited; private LinkedList<Integer> list; public GraphSearch() public GraphSearch(Graph G) this.G = G; int n = G.n; visited = new intn + 1;

40、 list = new LinkedList<Integer>(); public void clear() Arrays.fill(visited, 0); list.clear(); /* * 訪問結(jié)點w，將w放到一個鏈表中去 * * param w */ public void visit(int w) list.add(w); /* * <p> * 圖的寬度優(yōu)先檢索 * <p> * G，它在結(jié)點v開始執(zhí)行，所有已訪問結(jié)點都標(biāo)上visitedi=1,圖G和數(shù)組visited是全程變量,visited開始記為0 * * param v */ public

41、 void BFS(int v) visit(v); visitedv = 1; int u = v; LinkedList<Integer> Q = new LinkedList<Integer>();/ 當(dāng)作放置未檢測結(jié)點的隊列 while (true) LinkedList<Edge> list = G.costListu; for (Edge e : list) / 鄰接于u的所有結(jié)點 int w = e.v; if (visitedw = 0) Q.add(w);/ 將未檢測的結(jié)點為w放入隊列 visit(w);/ 訪問該結(jié)點 visitedw =

42、 1;/ 將該結(jié)點標(biāo)記為1 if (!Q.isEmpty() / 若隊列不為空 u = Q.remove();/ 將未訪問的結(jié)點從隊列取出賦給u，并準(zhǔn)備下一輪循環(huán) else / 隊列為空表示所有結(jié)點訪問結(jié)束 return; /* * 寬度優(yōu)先周游算法 */ public void BFT() for (int i = 1; i <= G.n; i+) / 將所有結(jié)點標(biāo)注為未訪問/ visitedi = 0; for (int i = 1; i < G.n; i+) / 反復(fù)調(diào)動BFS if (visitedi = 0) BFS(i); /* * <p> * 圖的深度優(yōu)先檢索 * <p> * 已知一個n結(jié)點的無向（或有向圖）G，以及初會已置為零的數(shù)組visited，這個算法可到達(dá)訪問由v所可以到過的所有結(jié)點，G和visite是全程變量 * * param v */ public void DFS(int v) visit(v);/ 訪問該結(jié)點 visitedv = 1;/ 將該結(jié)點標(biāo)記為1 LinkedList<Edge> list = G.costListv; for (Edge e :