數(shù)據(jù)結構實驗報告

信息與管理科學學院計算機科學系實驗報告課程名稱：《數(shù)據(jù)結構與算法》班級：姓名：學號指導老師：上機實驗內(nèi)容規(guī)范一、實驗目的上機實驗是數(shù)據(jù)結構課程教學不可或缺的重要環(huán)節(jié)。上機實驗是通過編寫解決簡單問題的程序，達到如下課程實驗目的：（1）使學生進一步理解和掌握課堂上所學各種基本抽象數(shù)據(jù)類型的邏輯結構、存儲結構和操作實現(xiàn)算法。（2）使學生深入理解面向對象的概念和程序設計方法，掌握抽象數(shù)據(jù)類型和類的關系。（3）使學生掌握軟件設計的基本內(nèi)容和設計方法，并培養(yǎng)學生進行規(guī)范化軟件設計的能力。（4）能夠運用所學原理和方法解決實際問題，設計相應數(shù)據(jù)結構以及解決實際問題的算法，運用高級語言實現(xiàn)性能優(yōu)、效率高、可讀性強、易維護的程序，并提高探索研究問題的能力。二、實驗環(huán)境1人/I機，windows7及以上操作系統(tǒng)，VC++6.0以上版本（JDK1.6以上版本，Eclipse4.3以上版本）三、實驗內(nèi)容為達到嚴格訓練的目的，要求上機實驗完成后書寫上機實驗報告。上機實驗報告應包括如下8部分內(nèi)容。問題描述：描述要求編程解決的問題。基本要求：給出程序要達到的具體要求。測試數(shù)據(jù)：設計測試數(shù)據(jù)，要求測試數(shù)據(jù)能基本達到測試目的。算法思想：描述解決相應問題的算法思想。類劃分：分析問題所需的類，并給出類的邏輯功能描述。源程序：給出所有源程序清單，要求程序有充分的注釋語句。測試情況：給出程序的測試情況以及必要的說明。心得體會：實驗過程結束后的收獲。在以上8個部分中，問題描述和基本要求部分通常由教師作為上機實驗題目給出；有時測試數(shù)據(jù)部分也由教師給出，若教師沒有給出此部分，則要求學生自己設計測試數(shù)據(jù)；其余算法思想、類劃分、源程序和測試情況部分是學生上機實驗的主體部分；心得體會是學生思考擴展的體現(xiàn)部分。8.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.}Node節(jié)點類packagetree;2./***@authorwyt*@create2021-12-1410:32*/7.publicclassNode<T>{privateTdata;publicNode<T>lChild;publicNode<T>rChild;publicNode(){data=null;lChild=null;rChild=null;}publicNode(Telem){data=elem;lChild=null;rChild=null;}publicTgetData(){returndata;}publicvoidsetData(Ty){data=y;}BinaryTree類packagetree;2./***@authorwyt*@create2021-12-1410:33*/7.publicclassBinaryTree<T>{

publicNode<T>root;8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.privatefinalintmaxNodes=100;publicBinaryTree(){this.root=newNode<T>();}publicBinaryTree(Tx){this.root=newNode<T>(x);}publicbooleaninsertLeft(Tx,Node<T>parent){if(parent==null)returnfalse;Node<T>p=newNode<T>(x);if(parent.lChild==null)parent.lChild=p;else{p.lChild=parent.lChild;parent.lChild=p;}returntrue;}publicbooleaninsertRight(Tx,Node<T>parent){if(parent==null)returnfalse;Node<T>p=newNode<T>(x);if(parent.rChild==null)parent.rChild=p;else{p.rChild=parent.rChild;parent.rChild=p;}returntrue;}publicbooleandeleteLeft(Node<T>parent){if(parent==null)returnfalse;else{parent.lChild=null;returntrue;}}}}publicbooleandeleteRight(Node<T>parent){if(parent==null)returnfalse;else{parent.rChild=null;returntrue;}}publicvoidyezi(Node<T>node){if(node==null)return;else{if(node.lChild==null&&node.rChild==null){System.out.print("\n葉子節(jié)點："+node.getData());}else{yezi(node.lChild);yezi(node.rChild);}}}publicintcount(Node<T>node){intlc,rc,sum;if(node!=null){lc=count(node.lChild);rc=count(node.rChild);sum=lc+rc;return(sum+1);}elsereturn0;}publicNode<T>search(Node<T>node,Tx){if(node==null)returnnull;52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.else{}}96.96.97.98.99.100.101.102.103.104.105.106.107.108.109.110.111.112.113.114.x)){115.116.117.x)){118.119.120.121.122.123.124.125.126.127.128.129.130.131.132.133.134.135.136.137.if((node.getData()).equals(x)){returnnode;}else{Node<T>s=search(node.lChild,x);if(s!=null)returns;elsereturnsearch(node.rChild,x);}}}publicNode<T>search2(Node<T>node,Tx){if(node==null)returnnull;else{if(node.lChild!=null&&(node.lChild.getData()).equals(returnnode;}if(node.rChild!=null&&(node.rChild.getData()).equals(returnnode;}Node<T>s=search2(node.lChild,x);if(s!=null)returns;elsereturnsearch2(node.rChild,x);}}publicbooleaninsertl(Node<T>a,Node<T>parent){if(parent==null)returnfalse;if(parent.lChild==null)parent.lChild=a;else{insertl(a,parent.lChild);}returntrue;138.138.139.140.141.142.143.144.145.146.147.148.149.150.151.152.153.154.155.156.157.158.159.160.161.162.163.164.165.166.167.168.169.170.171.172.173.174.175.176.177.178.179.180.181.publicbooleaninsertr(Node<T>a,Node<T>parent){if(parent==null)returnfalse;if(parent.rChild==null)parent.rChild=a;else{insertr(a,parent.rChild);}returntrue;}publicvoidsuojing(Node<T>node,inti){if(node==null)return;else{for(intj=0;j<i;j++){System.out.print("-");}System.out.println(node.getData());suojing(node.lChild,++i);--i;suojing(node.rChild,++i);--i;}}publicvoidinorder(Node<T>node){if(node==null)return;else{inorder(node.lChild);System.out.print(node.getData());inorder(node.rChild);}}publicvoidpreorder(Node<T>node){if(node==null)return;else{System.out.print(node.getData());182.183.184.185.186.187.188.189.190.191.192.193.194.195.196.197.198.199.200.201.202.203.204.205.206.207.208.209.210.211.212.213.214.215.216.217.218.219.220.221.222.223.224.225.preorder(node.lChild);preorder(node.rChild);}}publicvoidpostorder(Node<T>node){if(node==null)return;else{postorder(node.lChild);postorder(node.rChild);System.out.print(node.getData());}}publicvoidlevelorder(){Node<T>[]queue=newNode[this.maxNodes];intfront,rear;if(this.root==null)return;front=-1;rear=0;queue[rear]=this.root;while(front!=rear){front++;System.out.print(queue[front].getData());if(queue[front].lChild!=null){rear++;queue[rear]=queue[front].lChild;}if(queue[front].rChild!=null){rear++;queue[rear]=queue[front].rChild;}}}publicvoidtraversal(inti){switch(i){28.29.30.31.32.#.35.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.node2.setData(temp);System.out.print("節(jié)點3和節(jié)點7交換后：");tree.traversal(0);System.out.println("(先序遍歷)");//5.將現(xiàn)有二叉樹的某個子樹a移到其他子樹b中Node<Integer>a=tree.search(tree.root,2);Node<Integer>b=tree.search(tree.root,3);//5.1查找a的雙親Node<Integer>parentofa=tree.search2(tree.root,a.getData());//System.out.println("a的雙親是:"+parentOfa.getData());System.out.println("a的雙親:"+parentOfa.getData());System.out.println();//插入操作將a插到b中tree.insertl(a,b);//將子樹a置空if(parentOfa.lChild!=null&&parentOfa.lChild.getData().equals(a.getData()))parentOfa.lChild=null;elseif(parentOfa.rChild!=null&&parentOfa.rChild.getData().equals(a.getData()))parentOfa.rChild=null;//遍歷一下，檢驗是否正確System.out.println("將a移到b以后：");tree.traversal(0);System.out.println("(先序)");tree.traversal(1);System.out.println("(中序)")；//6.刪除一個節(jié)點//找到這個節(jié)點Node<Integer>delete=tree.search(tree.root,3);〃找到這個節(jié)點的雙親節(jié)點Node<Integer>parentOfdelete=tree.search2(tree.root,delete.getData());if(parentOfdelete.lChild!=null&&parentOfdelete.lChild.getData().equals(delete.getData()))parentOfdelete.lChild=null;100.101.102.100.101.102.}100.101.102.100.101.102.}74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.96.97.98.99.elseif(parentOfdelete.rChild!=null&&parentOfdelete.rChild.getData().equals(delete.getData()))parentofdelete.rChild=null;//找到節(jié)點的左孩子和右孩子Node<Integer>left=delete.lChild;Node<Integer>right=delete.rChild;//插入操作if(left!=null){tree.insertl(left,parentofdelete);}if(right!=null){tree.insertr(right,parentOfdelete);}//遍歷一下，檢驗是否正確System.out.println("刪除節(jié)點以后:");tree.traversal(0);System.out.println("(先序)");tree.traversal(1);System.out.println("(中序)”)；//7.縮進結構打印System.out.println("縮進結構打印:");tree.suojing(tree.root,0);}測試結果原始一叉樹：043218765二叉樹的所有葉子節(jié)點：葉子節(jié)點：1葉子節(jié)點：5節(jié)點的數(shù)量為：9節(jié)點3和節(jié)點7交換后：047218365（先序遍歷）且的雙親：7將日移至％以后：047832165（先序）740812365（中序）刪除節(jié)點以后：04782165（先序）74012865（中序）縮進結構打?。?4—7-8—2——1—6——5［心得體會］遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。最初，看到這次的作業(yè)時，我覺得難度應該不大，因為我也學了相關的知識。實際行動起來才發(fā)現(xiàn)，往往大