数据结构实验报告

信息与管理科学学院计算机科学系实验报告课程名称：《数据结构与算法》班级：姓名：学号指导老师：上机实验内容规范一、实验目的上机实验是数据结构课程教学不可或缺的重要环节。上机实验是通过编写解决简单问题的程序，达到如下课程实验目的：（1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法。（2）使学生深入理解面向对象的概念和程序设计方法，掌握抽象数据类型和类的关系。（3）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。（4）能够运用所学原理和方法解决实际问题，设计相应数据结构以及解决实际问题的算法，运用高级语言实现性能优、效率高、可读性强、易维护的程序，并提高探索研究问题的能力。二、实验环境1人/I机，windows7及以上操作系统，VC++6.0以上版本（JDK1.6以上版本，Eclipse4.3以上版本）三、实验内容为达到严格训练的目的，要求上机实验完成后书写上机实验报告。上机实验报告应包括如下8部分内容。问题描述：描述要求编程解决的问题。基本要求：给出程序要达到的具体要求。测试数据：设计测试数据，要求测试数据能基本达到测试目的。算法思想：描述解决相应问题的算法思想。类划分：分析问题所需的类，并给出类的逻辑功能描述。源程序：给出所有源程序清单，要求程序有充分的注释语句。测试情况：给出程序的测试情况以及必要的说明。心得体会：实验过程结束后的收获。在以上8个部分中，问题描述和基本要求部分通常由教师作为上机实验题目给出；有时测试数据部分也由教师给出，若教师没有给出此部分，则要求学生自己设计测试数据；其余算法思想、类划分、源程序和测试情况部分是学生上机实验的主体部分；心得体会是学生思考扩展的体现部分。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节点类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叶子节点："+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("节点3和节点7交换后：");tree.traversal(0);System.out.println("(先序遍历)");//5.将现有二叉树的某个子树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.删除一个节点//找到这个节点Node<Integer>delete=tree.search(tree.root,3);〃找到这个节点的双亲节点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;//找到节点的左孩子和右孩子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("删除节点以后:");tree.traversal(0);System.out.println("(先序)");tree.traversal(1);System.out.println("(中序)”)；//7.缩进结构打印System.out.println("缩进结构打印:");tree.suojing(tree.root,0);}测试结果原始一叉树：043218765二叉树的所有叶子节点：叶子节点：1叶子节点：5节点的数量为：9节点3和节点7交换后：047218365（先序遍历）且的双亲：7将日移至％以后：047832165（先序）740812365（中序）删除节点以后：04782165（先序）74012865（中序）缩进结构打印：-4—7-8—2——1—6——5［心得体会］遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。最初，看到这次的作业时，我觉得难度应该不大，因为我也学了相关的知识。实际行动起来才发现，往往大