java典型数据结构实现与操作

1、实验二典型数据结构实现与操作一、实验目的1、设计、实现并测试一系列Java引用类型；2、训练学习者面向对象高级特性的应用能力，包括类的继承、方法重写、 抽象类与接口应用、程序流程控制；二、实验内容1、Performer接口，描述一切具有“自我表现”能力的事物，其中至少应 提供一个show()方法用于显示当前事物的相关说明信息。2、Person类，实现Performer接口，描述人员信息及相关操作，包括但不 限于人员姓名、年龄等。3、Book类，实现Performer接口，描述图书信息及相关操作，包括但不限 于书号、书名、价格等。4、抽象类Node,实现Performer接口，描述通用数据节点，

2、其中应封装一 整型的数据值value及相关操作功能。5、 LinkedListNode 类，继承抽象类 Node,描述单向链表节点，在 Node数 据结构基础上添加一个next属性，以指向其后继节点。6、TreeNode类，继承抽象类Node,描述二叉树节点，在 Node数据结构 基础上添加lchild 及rchild属性，分别用于引用其“左孩子”、“右孩子”节点。TestPerformerLinkedLisrTool三、实验要求1、实验前书写实验预习报告；2、掌握继承、多态、方法重写3、掌握抽象类、接口4、了解关键字 super 、static5、学会流程控制6、了解数据结构（链表、二叉树）

3、及相关算法7、写出实验报告四、实验学时8 学时五、实验步骤1、进入 MyEclipse 环境，新建一个 Java Project ；2、编写实验内容中提到的类；3、编写 TestPerformer 类，测试应用程序类，在该类中定义一个测试方法 introduce（Performer p） ，并分别创建和使用 Person、 Book、 LinkedListNode 及 TreeNode 类型对象为实参调用 introduce（） 方法， 以验证 Java 接口与其实现 类之间的多态性。类似地，还可以再定义一个测试方法 getInfo（Node n） ，并分 别使用 LinkedListNode

4、 及 TreeNode 类型对象为实参调用，以验证 Java 父类与 子类之间的多态性机制。 ；4、编写 LinkedListTool 类，单向链表工具类， 在该类中提供一系列 static 方法，实现单向链表的常规操作功能，包括但不限于：构造一个测试用新链表、 遍历链表、 向链表尾部追加节点、 删除链表中符合特定条件的节点 （例如删除链 表中 value 属性为某一特定值的所有节点） 、链表排序、向有序链表中插入一个 新节点（仍保持其有序） 、有序链表合并（结果仍为有序链表） ，并对上述方法进 行测试。5、调试运行程序六. 实验流程图七。实验代码l. pers onimport com.am

5、bow.Performer;public class Pers on impleme nts Performed private String n ame;private int age;public Pers on( Stri ng n ame, int age) super();this. name = n ame; this.age = age;public Stri ng getName() return name;public void setName(String name) = name;public int getAge() return age;publi

6、c void setAge(int age) this.age = age;public void show() System.out.println( 个人信息, 姓名: + name + , 年龄: + age);2. bookimport com.ambow.Performer;public class Book implements Performerprivate String id;private String name;private double price;public Book(String id, String name, double price) super();th

7、is.id = id; = name; this.price = price;public String getId() return id;public void setId(String id) this.id = id;public String getName() return name;public void setName(String name) = name;public double getPrice() return price;public void setPrice(double price) this.price = price

8、;public void show() System.out.println( 图书简介 , 书号: + id + ,书名: + name +价格: + price);3. Nodeimport com.ambow.Performer;public abstract class Node implements Performerprivate int value;public Node() public Node(int value) this.value = value;public int getValue() return value;public void setValue(int v

9、alue) this.value = value;4. LinkedListNode public class LinkedListNode extends Node private LinkedListNode next;public LinkedListNode() super();public LinkedListNode(int value) super(value);public LinkedListNode(LinkedListNode next) super(); this.next = next;public LinkedListNode(int value, LinkedLi

10、stNode next) super(value); this.next = next;public LinkedListNode getNext() return next;public void setNext(LinkedListNode next) this.next = next;public void show() System.out.println(单向链表节点 ,value= + this.getValue();5. TreeNodepublic class TreeNode extends Node private TreeNode lchild;private TreeN

11、ode rchild;public TreeNode() super();public TreeNode(TreeNode lchild, TreeNode rchild) super(); this.lchild = lchild; this.rchild = rchild;public TreeNode(int value, TreeNode lchild, TreeNode rchild) super(value);this.lchild = lchild; this.rchild = rchild;public TreeNode getLchild() return lchild;pu

12、blic void setLchild(TreeNode lchild) this.lchild = lchild;public TreeNode getRchild() return rchild;public void setRchild(TreeNode rchild) this.rchild = rchild;public void show() System.out.println(二叉树节点 ,value= + this.getValue();6. TestPerformerimport com.ambow.Performer;public class TestPerformer

13、public static void main(String args) TestPerformer tp = new TestPerformer();roduce(new Person( 张三, 18); roduce(new Book(ISBN1001, Java核心技术 , 38.50);roduce(new LinkedListNode(20,null);roduce(new TreeNode(33,null,null); public void introduce(Performer p) p.show();7. LinkedListT

14、oolpublic class LinkedListTool public static void main(String args) / 创建一个单向链表LinkedListNode head = LinkedListTool.createLinkedList();/ 遍历它 LinkedListTool.show(head);/ 尾部追加节点LinkedListNode result;result = LinkedListTool.append(head, LinkedListNode(99,null);LinkedListTool.show(result);head = result;/

15、 删除其中符合特定条件的节点result = LinkedListTool.delete(head, 23);LinkedListTool.show(result);head = result;/ 排序result = LinkedListTool.sort(head);LinkedListTool.show(result);head = result;/ 向有序链表中插入一个新节点result = LinkedListTool.insert(head, LinkedListNode(88,null);LinkedListTool.show(result);head = result;/ 合并

16、两个有序链表LinkedListNode h2 = LinkedListTool.createLinkedList();result = LinkedListTool.merge(head, h2);LinkedListTool.show(result);newnewpublic static LinkedListNode createLinkedList()int a = 44,23,45,23,78,33,121,34,322,-76;int size = a.length;LinkedListNode head = new LinkedListNode(asize-1);for(int

17、i=size-2; i=0; i-)head = new LinkedListNode(ai, head);return head;public static void show(LinkedListNode head)while(head != null) System.out.print(head.getValue(); head = head.getNext(); if(head != null)System.out.print( - );System.out.println(n);head,public static LinkedListNode append(LinkedListNo

18、de LinkedListNode new_p) if(head = null)head = new_p;else/p 指向当前头节点(非空的) LinkedListNode p = head;/n 为 p 的后继节点 ( 可能为空值 ) LinkedListNode n = p.getNext();while(n != null)p = n;n = p.getNext();p.setNext(new_p);return head;public static LinkedListNode delete(LinkedListNode head, int v)/ 删除链表开头的连续多个节点whil

19、e(head != null & head.getValue() = v) head = head.getNext();/head 要保留if(head != null) / 删除符合条件中间节点 /p 指向当前头节点(非空的) LinkedListNode p = head;/n 为 p 的后继节点 ( 可能为空值 ) LinkedListNode n = p.getNext(); while(n != null)if(n.getValue() = v)/ 该删除 p.setNext(n.getNext();else p = n;n = p.getNext(); return head;pu

20、blic static LinkedListNode sort(LinkedListNode head) / 创建一个空的结果链表LinkedListNode nhead = null;/ 依次取出源链表中的每一个节点，并将之插入到有序的结构链表中， 仍然结构链表的有序状态while(head != null) LinkedListNode c = head; head = head.getNext(); c.setNext(null);/ 将 c 这个节点插入到有序的链表 nhead 中 nhead = LinkedListTool.insert(nhead, c);return nhead

21、;/ 向有序链表中插入一个新节点，并保持其有序状态head,public static LinkedListNode insert(LinkedListNode LinkedListNode n)/ 如果目标链表为空链表 if(head = null)head = n;else if(n.getValue() p2.getValue() p1 = p2; p2 = p2.getNext();/ 将 n 节点插入到 p1 和 p2 两个节点之间 p1.setNext(n);n.setNext(p2); return head;head1,head2链public static LinkedLis

22、tNode merge(LinkedListNode LinkedListNode head2)head2 = LinkedListTool.sort(head2);/ 依次取出 head1 链表中的每一个节点，并将之插入到有序的 表中，仍然结构链表的有序状态while(head1 != null) LinkedListNode c = head1; head1 = head1.getNext(); c.setNext(null);/ 将 c 这个节点插入到有序的链表 nhead 中 head2 = LinkedListTool.insert(head2, c);return head2; 8

23、. TreeToolublic class TreeTool public static void main(String args) TreeNode root = TreeTool.createLinkedList(); TreeTool.list(root);/ 构建一颗二叉树public static TreeNode createLinkedList()TreeNode n1 = new TreeNode(9, null, null);TreeNode n2 = new TreeNode(12, null, null);TreeNode n3 = new TreeNode(49, n1, n2);TreeNode n4 = new TreeNode(54, null, null);TreeNode n5 = new TreeNode(37, n3, n4); return n5;/ 遍历二叉树(中序遍历)publi