信息與管理科學(xué)學(xué)院計(jì)算機(jī)科學(xué)系實(shí)驗(yàn)報(bào)告課程名稱(chēng)：《數(shù)據(jù)結(jié)構(gòu)與算法》班級(jí)：姓名：學(xué)號(hào)指導(dǎo)老師：上機(jī)實(shí)驗(yàn)內(nèi)容規(guī)范一、實(shí)驗(yàn)?zāi)康纳蠙C(jī)實(shí)驗(yàn)是數(shù)據(jù)結(jié)構(gòu)課程教學(xué)不可或缺的重要環(huán)節(jié)。上機(jī)實(shí)驗(yàn)是通過(guò)編寫(xiě)解決簡(jiǎn)單問(wèn)題的程序，達(dá)到如下課程實(shí)驗(yàn)?zāi)康模海?）使學(xué)生進(jìn)一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類(lèi)型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法。（2）使學(xué)生深入理解面向?qū)ο蟮母拍詈统绦蛟O(shè)計(jì)方法，掌握抽象數(shù)據(jù)類(lèi)型和類(lèi)的關(guān)系。（3）使學(xué)生掌握軟件設(shè)計(jì)的基本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行規(guī)范化軟件設(shè)計(jì)的能力。（4）能夠運(yùn)用所學(xué)原理和方法解決實(shí)際問(wèn)題，設(shè)計(jì)相應(yīng)數(shù)據(jù)結(jié)構(gòu)以及解決實(shí)際問(wèn)題的算法，運(yùn)用高級(jí)語(yǔ)言實(shí)現(xiàn)性能優(yōu)、效率高、可讀性強(qiáng)、易維護(hù)的程序，并提高探索研究問(wèn)題的能力。二、實(shí)驗(yàn)環(huán)境1人/I機(jī)，windows7及以上操作系統(tǒng)，VC++6.0以上版本（JDK1.6以上版本，Eclipse4.3以上版本）三、實(shí)驗(yàn)內(nèi)容為達(dá)到嚴(yán)格訓(xùn)練的目的，要求上機(jī)實(shí)驗(yàn)完成后書(shū)寫(xiě)上機(jī)實(shí)驗(yàn)報(bào)告。上機(jī)實(shí)驗(yàn)報(bào)告應(yīng)包括如下8部分內(nèi)容。問(wèn)題描述：描述要求編程解決的問(wèn)題。基本要求：給出程序要達(dá)到的具體要求。測(cè)試數(shù)據(jù)：設(shè)計(jì)測(cè)試數(shù)據(jù)，要求測(cè)試數(shù)據(jù)能基本達(dá)到測(cè)試目的。算法思想：描述解決相應(yīng)問(wèn)題的算法思想。類(lèi)劃分：分析問(wèn)題所需的類(lèi)，并給出類(lèi)的邏輯功能描述。源程序：給出所有源程序清單，要求程序有充分的注釋語(yǔ)句。測(cè)試情況：給出程序的測(cè)試情況以及必要的說(shuō)明。心得體會(huì)：實(shí)驗(yàn)過(guò)程結(jié)束后的收獲。在以上8個(gè)部分中，問(wèn)題描述和基本要求部分通常由教師作為上機(jī)實(shí)驗(yàn)題目給出；有時(shí)測(cè)試數(shù)據(jù)部分也由教師給出，若教師沒(méi)有給出此部分，則要求學(xué)生自己設(shè)計(jì)測(cè)試數(shù)據(jù)；其余算法思想、類(lèi)劃分、源程序和測(cè)試情況部分是學(xué)生上機(jī)實(shí)驗(yàn)的主體部分；心得體會(huì)是學(xué)生思考擴(kuò)展的體現(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é)點(diǎn)類(lèi)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類(lèi)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é)點(diǎn)："+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é)點(diǎn)3和節(jié)點(diǎn)7交換后：");tree.traversal(0);System.out.println("(先序遍歷)");//5.將現(xiàn)有二叉樹(shù)的某個(gè)子樹(shù)a移到其他子樹(shù)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);//將子樹(shù)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;//遍歷一下，檢驗(yàn)是否正確System.out.println("將a移到b以后：");tree.traversal(0);System.out.println("(先序)");tree.traversal(1);System.out.println("(中序)")；//6.刪除一個(gè)節(jié)點(diǎn)//找到這個(gè)節(jié)點(diǎn)Node<Integer>delete=tree.search(tree.root,3);〃找到這個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)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é)點(diǎn)的左孩子和右孩子Node<Integer>left=delete.lChild;Node<Integer>right=delete.rChild;//插入操作if(left!=null){tree.insertl(left,parentofdelete);}if(right!=null){tree.insertr(right,parentOfdelete);}//遍歷一下，檢驗(yàn)是否正確System.out.println("刪除節(jié)點(diǎn)以后:");tree.traversal(0);System.out.println("(先序)");tree.traversal(1);System.out.println("(中序)”)；//7.縮進(jìn)結(jié)構(gòu)打印System.out.println("縮進(jìn)結(jié)構(gòu)打印:");tree.suojing(tree.root,0);}測(cè)試結(jié)果原始一叉樹(shù)：043218765二叉樹(shù)的所有葉子節(jié)點(diǎn)：葉子節(jié)點(diǎn)：1葉子節(jié)點(diǎn)：5節(jié)點(diǎn)的數(shù)量為：9節(jié)點(diǎn)3和節(jié)點(diǎn)7交換后：047218365（先序遍歷）且的雙親：7將日移至％以后：047832165（先序）740812365（中序）刪除節(jié)點(diǎn)以后：04782165（先序）74012865（中序）縮進(jìn)結(jié)構(gòu)打?。?4—7-8—2——1—6——5［心得體會(huì)］遍歷是對(duì)樹(shù)的一種最基本的運(yùn)算，所謂遍歷二叉樹(shù)，就是按一定的規(guī)則和順序走遍二叉樹(shù)的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪(fǎng)問(wèn)一次，而且只被訪(fǎng)問(wèn)一次。由于二叉樹(shù)是非線(xiàn)性結(jié)構(gòu)，因此，樹(shù)的遍歷實(shí)質(zhì)上是將二叉樹(shù)的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線(xiàn)性序列來(lái)表示。最初，看到這次的作業(yè)時(shí)，我覺(jué)得難度應(yīng)該不大，因?yàn)槲乙矊W(xué)了相關(guān)的知識(shí)。實(shí)際行動(dòng)起來(lái)才發(fā)現(xiàn)，往往大