数据结构实验报告

信息与管理科学学院计算机科学系

实验报告

课程名称： 班 级： 姓 名： 学 号： 指导老师： 《数据结构与算法》

上机实验内容规范

一、实验目的

上机实验是数据结构课程教学不可或缺的重要环节。上机实验是通过编写解决简单问题的程序，达到如下课程实验目的：

（1） 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑

结构、存储结构和操作实现算法。

（2） 使学生深入理解面向对象的概念和程序设计方法，掌握抽象数据类型

和类的关系。

（3） 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化

软件设计的能力。

（4） 能够运用所学原理和方法解决实际问题，设计相应数据结构以及解决

实际问题的算法，运用高级语言实现性能优、效率高、可读性强、易维护的程序，并提高探索研究问题的能力。

二、实验环境

1人/1机，windows7及以上操作系统，VC++6.0以上版本（JDK1.6以上版本，Eclipse4.3以上版本）

三、实验内容

为达到严格训练的目的，要求上机实验完成后书写上机实验报告。上机实验报告应包括如下8部分内容。

问题描述：描述要求编程解决的问题。 基本要求：给出程序要达到的具体要求。

测试数据：设计测试数据，要求测试数据能基本达到测试目的。 算法思想：描述解决相应问题的算法思想。

类 划 分：分析问题所需的类，并给出类的逻辑功能描述。 源 程 序：给出所有源程序清单，要求程序有充分的注释语句。 测试情况：给出程序的测试情况以及必要的说明。 心得体会：实验过程结束后的收获。 在以上8个部分中，问题描述和基本要求部分通常由教师作为上机实验题目给出；有时测试数据部分也由教师给出，若教师没有给出此部分，则要求学生自己设计测试数据；其余算法思想、类划分、源程序和测试情况部分是学生上机实验的主体部分；心得体会是学生思考扩展的体现部分。

Node节点类

1. package tree; 2. 3. /**

4. * @author wyt

5. * @create 2021-12-14 10:32 6. */

7. public class Node { 8. private T data; 9. public Node lChild; 10. public Node rChild; 11. public Node() 12. {

13. data = null; 14. lChild = null; 15. rChild = null; 16. }

17. public Node(T elem) 18. {

19. data = elem; 20. lChild = null; 21. rChild = null; 22. }

23. public T getData() 24. {

25. return data; 26. }

27. public void setData(T y) 28. {

29. data = y; 30. } 31. }

BinaryTree类

1. package tree; 2. 3. /**

4. * @author wyt

5. * @create 2021-12-14 10:33 6. */

7. public class BinaryTree {

8.

9. public Node root;

10. private final int maxNodes=100; 11. public BinaryTree() 12. {

13. this.root = new Node(); 14. }

15. public BinaryTree(T x) 16. {

17. this.root = new Node(x); 18. }

19. public boolean insertLeft(T x, Node parent) 20. {

21. if(parent==null) return false; 22. Node p= new Node(x);

23. if(parent.lChild==null) parent.lChild = p; 24. else 25. {

26. p.lChild = parent.lChild; 27. parent.lChild = p; 28. }

29. return true; 30. }

31. public boolean insertRight(T x, Node parent) 32. {

33. if(parent==null) return false; 34. Node p= new Node(x);

35. if(parent.rChild==null) parent.rChild = p; 36. else 37. {

38. p.rChild = parent.rChild; 39. parent.rChild = p; 40. }

41. return true; 42. } 43.

44. public boolean deleteLeft(Node parent) 45. {

46. if(parent==null) return false; 47. else 48. {

49. parent.lChild=null; 50. return true; 51. }

52. }

53. public boolean deleteRight(Node parent) . {

55. if(parent==null) return false; 56. else 57. {

58. parent.rChild=null; 59. return true; 60. } 61. } 62.

63. public void yezi(Node node) . {

65. if(node==null) return; 66. else 67. {

68. if (node.lChild==null&&node.rChild==null) {

69. System.out.print(\"\\n叶子节点:\"+node.getData()); 70. } 71. else{

72. yezi(node.lChild); 73. yezi(node.rChild); 74. } 75. } 76. } 77.

78. public int count(Node node) 79. {

80. int lc, rc, sum; 81. if(node != null) 82. {

83. lc = count(node.lChild); 84. rc = count(node.rChild); 85. sum = lc+rc; 86. return (sum+1); 87. }

88. else return 0; . 90. } 91.

92. public Node search(Node node,T x){ 93. if(node==null) 94. return null; 95. else{

96. if((node.getData()).equals(x)){ 97. return node; 98. } 99. else{ 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137.

Node s=search(node.lChild,x); if(s!=null) return s; else

return search(node.rChild,x); } } }

public Node search2(Node node,T x){ if(node==null) return null; else{

if(node.lChild!=null &&(node.lChild.getData()).equals( return node; }

if(node.rChild!=null &&(node.rChild.getData()).equals( return node; }

Node s=search2(node.lChild,x); if(s!=null) return s; else

return search2(node.rChild,x); } }

public boolean insertl(Node a, Node parent) {

if(parent==null) return false;

if(parent.lChild==null) parent.lChild = a; else {

insertl(a,parent.lChild); }

return true;

x)){

x)){

138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 1. 155. 156. 157. 158. 159. 160. 161. 162. 163. 1. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181.

}

public boolean insertr(Node a, Node parent) {

if(parent==null) return false;

if(parent.rChild==null) parent.rChild = a; else {

insertr(a,parent.rChild); }

return true; }

public void suojing(Node node,int i) {

if(node==null)return; else {

for (int j = 0; j < i; j++) { System.out.print(\"-\"); }

System.out.println(node.getData()); suojing(node.lChild,++i); --i;

suojing(node.rChild,++i); --i; } }

public void inorder(Node node) {

if(node==null) return; else {

inorder(node.lChild);

System.out.print(node.getData()); inorder(node.rChild); } }

public void preorder(Node node) {

if(node==null) return; else {

System.out.print(node.getData());

182. 183. 184. 185. 186. 187. 188. 1. 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); } }

public void postorder(Node node) {

if(node==null) return; else {

postorder(node.lChild); postorder(node.rChild);

System.out.print(node.getData()); } }

public void levelorder() {

Node[] queue= new Node[this.maxNodes]; int front,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; } } }

public void traversal(int i) {

switch(i) {

226. 227. 228. 229. 230. 231. 232.

case 0: preorder(this.root);break; case 1: inorder(this.root);break; case 2: postorder(this.root);break; default: levelorder(); } } }

Test测试类

1. package tree; 2. 3.

4. public class test { 5.

6. /**主函数部分 7. * @param args 8. */

9. public static void main(String[] args) { 10. // TODO Auto-generated method stub 11. int[] aa= new int[]{1,2,3,4}; 12. int[] bb= new int[]{5,6,7,8};

13. BinaryTree tree = new BinaryTree<>(0); 14. Node node = tree.root; 15. for (int i = 0; i < aa.length; i++) { 16. tree.insertLeft(aa[i], node); 17. tree.insertRight(bb[i], node); 18. }

19. System.out.println(\"原始二叉树:\"); 20. tree.traversal(0); 21. 22.

23. //2.输出二叉树的所有叶子节点

24. System.out.println(\"\\n二叉树的所有叶子节点:\"); 25. tree.yezi(tree.root); 26.

27. //3.统计节点数量

28. System.out.println(\"\\n节点的数量为：\"+tree.count(tree.root)); 29.

30. //4.交换二叉树任意两个节点（假设二叉树的每个节点的值都不一样） 31. Node node1 = tree.search(tree.root, 3); 32. Node node2 = tree.search(tree.root, 7); 33. int temp = node1.getData(); 34. node1.setData(node2.getData());

35. node2.setData(temp);

36. System.out.print(\"节点3和节点7交换后：\"); 37. tree.traversal(0);

38. System.out.println(\"(先序遍历)\"); 39. 40. 41.

42. //5.将现有二叉树的某个子树a移到其他子树b中 43. Node a = tree.search(tree.root, 2); 44. Node b = tree.search(tree.root, 3); 45.

46. //5.1查找a的双亲

47. Node parentOfa=tree.search2(tree.root,a.getData());

48. //System.out.println(\"a的双亲是:\"+parentOfa.getData()); 49. System.out.println(\"a的双亲:\"+parentOfa.getData()); 50. System.out.println(); 51. //插入操作将a插到b中 52. tree.insertl(a, b); 53. //将子树a置空

. if(parentOfa.lChild!=null && parentOfa.lChild.getData().equal

s(a.getData()))

55. parentOfa.lChild=null; 56. else

57. if(parentOfa.rChild!=null && parentOfa.rChild.getData().equal

s(a.getData()))

58. parentOfa.rChild=null; 59. //遍历一下,检验是否正确

60. System.out.println(\"将a移到b以后：\"); 61. tree.traversal(0);

62. System.out.println(\"(先序)\"); 63. tree.traversal(1);

. System.out.println(\"(中序)\"); 65. 66.

67. //6.删除一个节点 68. //找到这个节点

69. Node delete = tree.search(tree.root, 3); 70. //找到这个节点的双亲节点

71. Node parentOfdelete=tree.search2(tree.root,delete.ge

tData());

72. if(parentOfdelete.lChild!=null && parentOfdelete.lChild.getDa

ta().equals(delete.getData()))

73. parentOfdelete.lChild=null;

74. else

75. if(parentOfdelete.rChild!=null && parentOfdelete.rChild.getDa

ta().equals(delete.getData()))

76. parentOfdelete.rChild=null; 77. //找到节点的左孩子和右孩子

78. Node left = delete.lChild; 79. Node right = delete.rChild; 80. //插入操作

81. if (left != null) {

82. tree.insertl(left,parentOfdelete); 83. }

84. if (right != null) {

85. tree.insertr( right,parentOfdelete); 86. }

87. //遍历一下,检验是否正确

88. System.out.println(\"删除节点以后:\"); . tree.traversal(0);

90. System.out.println(\"(先序)\"); 91. tree.traversal(1);

92. System.out.println(\"(中序)\"); 93.

94. //7.缩进结构打印

95. System.out.println(\"缩进结构打印:\"); 96. tree.suojing(tree.root,0); 97. 98. 99. } 100. 101. 102.

}

测试结果

[心得体会]

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

最初，看到这次的作业时，我觉得难度应该不大，因为我也学了相关的知识。实际行动起来才发现，往往大方向的确定是很容易的，而具体实施起来才会认识到层层困难。由于之前没有了解具体的方法，结合实验要求，从而确定实验步骤，过程中困难重重。经过和室友一起的讨论和实际操作，慢慢困难就解决了，按时完成了本次实验报告。通过这段时间的，实际操作和讨论，我在动手操作能力，思考问题上，有了不同程度上的收获，对我以后的工作和学习，积累了一定的经验。

本次报告，加深了我对树的认识。树是由n(n≥1)个有限节点组成一个具有层次关系的集合，把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树

1、后序非递归遍历二叉树时，访问到指定结点时栈中的元素为此结点的祖先。2、k叉树第p个结点的第k-1个孩子的层次序列为p*k。

3、在树这章写递归时，出口判断常为树空或子树空。4、树转成的二叉树无右子树。

5、树用孩子兄弟存储的结构中，结点若无firstchild，则该结点在树的结构中必是一个叶子。故用孩子兄弟链表示的树统计叶子的算法可以写为firstchild == NULL。6、找子孙常用先序遍历，找祖先常用后序遍历。7、在按层次访问一棵二叉树的基础上加以修改，不论其左右子树是否为空均入队，若为完全二叉树，则将它按层序输出时得到的是一个连续的不含空指针的序列，反之序列中会含有空指针。8、递归中常用return向上级函数返回值。

这次报告，让我更加了解了树的含义，对树的输出与创建更加了解了，通过属的方式获取数据对数据进行处理是数据更加可读，对树状结构的了解更加深刻更加清晰。同时也对类的封装性有了更加深刻的了解，将游戏的功能封装到方法，文件结构放在一个个对象中使结构更加规范，更容易调试和改写。