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

精选文库实验二 典型数据结构实现与操作一、实验目的1、设计、实现并测试一系列Java引用类型；2、训练学习者面向对象高级特性的应用能力，包括类的继承、方法重写、抽象类与接口应用、程序流程控制；二、实验内容1、Performer接口，描述一切具有“自我表现”能力的事物，其中至少应提供一个show()方法用于显示当前事物的相关说明信息。2、Person类，实现Performer接口，描述人员信息及相关操作，包括但不限于人员姓名、年龄等。3、Book类，实现Performer接口，描述图书信息及相关操作，包括但不限于书号、书名、价格等。4、抽象类Node，实现Performer接口，描述通用数据节点，其中应封装一整型的数据值value及相关操作功能。5、LinkedListNode类，继承抽象类Node，描述单向链表节点，在Node数据结构基础上添加一个next属性，以指向其后继节点。6、TreeNode类，继承抽象类Node，描述二叉树节点，在Node数据结构基础上添加lchild及rchild属性，分别用于引用其“左孩子”、“右孩子”节点。三、实验要求1、实验前书写实验预习报告；2、掌握继承、多态、方法重写3、掌握抽象类、接口4、了解关键字super、static5、学会流程控制6、了解数据结构（链表、二叉树）及相关算法7、写出实验报告四、实验学时8学时五、实验步骤1、进入MyEclipse环境，新建一个JavaProject；2、编写实验内容中提到的类；3、编写TestPerformer类，测试应用程序类，在该类中定义一个测试方法introduce(Performer p)，并分别创建和使用Person、Book、LinkedListNode及TreeNode类型对象为实参调用introduce()方法，以验证Java接口与其实现类之间的多态性。类似地，还可以再定义一个测试方法getInfo(Node n)，并分别使用LinkedListNode及TreeNode类型对象为实参调用，以验证Java父类与子类之间的多态性机制。；4、编写LinkedListTool类，单向链表工具类，在该类中提供一系列static方法，实现单向链表的常规操作功能，包括但不限于：构造一个测试用新链表、遍历链表、向链表尾部追加节点、删除链表中符合特定条件的节点（例如删除链表中value属性为某一特定值的所有节点）、链表排序、向有序链表中插入一个新节点（仍保持其有序）、有序链表合并（结果仍为有序链表），并对上述方法进行测试。5、调试运行程序。六实验流程图PermorferBOOKNODEPERSONTreeNodeLinkedListNode七。实验代码1.personimport com.ambow.Performer;public class Person implements Performerprivate String name;private int age;public Person(String name, int age) super(); = name;this.age = age;public String getName() return name;public void setName(String name) = name;public int getAge() return age;public 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();this.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;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 value) this.value = value;4. LinkedListNodepublic 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, LinkedListNode 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 TreeNode 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;public 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 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. LinkedListToolpublic class LinkedListTool public static void main(String args) /创建一个单向链表LinkedListNode head = LinkedListTool.createLinkedList();/遍历它LinkedListTool.show(head);/尾部追加节点LinkedListNode result; result = LinkedListTool.append(head, new LinkedListNode(99,null);LinkedListTool.show(result);head = result;/删除其中符合特定条件的节点result = LinkedListTool.delete(head, 23);LinkedListTool.show(result);head = result;/排序result = LinkedListTool.sort(head);LinkedListTool.show(result);head = result;/向有序链表中插入一个新节点result = LinkedListTool.insert(head, new LinkedListNode(88,null);LinkedListTool.show(result);head = result;/合并两个有序链表LinkedListNode h2 = LinkedListTool.createLinkedList();result = LinkedListTool.merge(head, h2);LinkedListTool.show(result);public 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 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-);public static LinkedListNode append(LinkedListNode head, 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)/删除链表开头的连续多个节点while(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();elsep = n;n = p.getNext();return head;public 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;/向有序链表中插入一个新节点，并保持其有序状态public static LinkedListNode insert(LinkedListNode head, 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;public static LinkedListNode merge(LinkedListNode head1, LinkedListNode head2)head2 = LinkedListTool.sort(head2);/依次取出head1链表中的每一个节点，并将之插入到有序的head2链表中，仍然结构链表的有序状态while(head1 != null)LinkedListNode c = head1;head1 = head1.getNext();c.setNext(null);/将c这个节点插入到有序的链表nhead中head2 = LinkedListTool.insert(head2, c);return head2;8. 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, nu