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,描述二叉机t节点，在Node数据结构基础上添加lchild及rchild属性，分别用于引用其“左孩子”、“右孩子”节点。ALinkcdLinNgie TreeNode|_JL3KJ_F-.-E-a.JLinkedLisvTooI三、实验要求1、实验前书写实验预习报告；2、掌握继承、多态、方法重写3、掌握抽象类、接口4、了解关键字super、static5、学会流程控制6、了

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

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

5、erformerprivateStringname;privateintage;publicPerson(Stringname,intage)super();=name;this.age=age;publicStringgetName()returnname;publicvoidsetName(Stringname)=name;publicintgetAge()returnage;publicvoidsetAge(intage)this.age=age;publicvoidshow()System.out.println("个人信息,姓名:&quo

6、t;+name+",年龄:"+age);2.bookimportcom.ambow.Performer;publicclassBookimplementsPerformerprivateStringid;privateStringname;privatedoubleprice;publicBook(Stringid,Stringname,doubleprice)super();this.id=id;=name;this.price=price;publicStringgetId()returnid;publicvoidsetId(Stringid)this

7、.id=id;publicStringgetName()returnname;publicvoidsetName(Stringname)=name;publicdoublegetPrice()returnprice;publicvoidsetPrice(doubleprice)this.price=price;publicvoidshow()System.out.println("图书简介,书号:"+id+",书名:"+name+",价格:"+price);3. Nodeimportcom.ambow.Perform

8、er;publicabstractclassNodeimplementsPerformerprivateintvalue;publicNode()publicNode(intvalue)this.value=value;publicintgetValue()returnvalue;publicvoidsetValue(intvalue)this.value=value;4. LinkedListNodepublicclassLinkedListNodeextendsNodeprivateLinkedListNodenext;publicLinkedListNode()super();publi

9、cLinkedListNode(intvalue)super(value);publicLinkedListNode(LinkedListNodenext)super();this.next=next;publicLinkedListNode(intvalue,LinkedListNodenext)super(value);this.next=next;publicLinkedListNodegetNext()returnnext;publicvoidsetNext(LinkedListNodenext)this.next=next;publicvoidshow()System.out.pri

10、ntln("单向链表节点,value="+this.getValue();5. TreeNodepublicclassTreeNodeextendsNodeprivateTreeNodelchild;privateTreeNoderchild;publicTreeNode()super();publicTreeNode(TreeNodelchild,TreeNoderchild)super();this.lchild=lchild;this.rchild=rchild;publicTreeNode(intvalue,TreeNodelchild,TreeNoderchild

11、)super(value);this.lchild=lchild;this.rchild=rchild;publicTreeNodegetLchild()returnlchild;publicvoidsetLchild(TreeNodelchild)this.lchild=lchild;publicTreeNodegetRchild()returnrchild;publicvoidsetRchild(TreeNoderchild)this.rchild=rchild;publicvoidshow()System.out.println("二叉树节点,value="+this

12、.getValue();6. TestPerformerimportcom.ambow.Performer;publicclassTestPerformerpublicstaticvoidmain(Stringargs)TestPerformertp=newTestPerformer();roduce(newPerson("张三",18);roduce(newBook("ISBN1001","Java核心技术",38.50);roduce(newLinkedListNode(20,null);tp.

13、introduce(newTreeNode(33,null,null);publicvoidintroduce(Performerp)p.show();7.LinkedListToolpublicclassLinkedListToolpublicstaticvoidmain(Stringargs)/创建一个单向链表LinkedListNodehead=LinkedListTool.createLinkedList();/遍历它LinkedListTool.show(head);/尾部追加节点LinkedListNoderesult;result=LinkedListTool.append(he

14、ad,newLinkedListNode(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;/向有序链表中插入一个新节点resultLinkedListNode(88,null);LinkedListTool.ins

15、ert(head,newLinkedListTool.show(result);head=result;/合并两个有序链表LinkedListNodeh2=LinkedListTool.createLinkedList();result=LinkedListTool.merge(head,h2);LinkedListTool.show(result);publicstaticLinkedListNodecreateLinkedList()inta=44,23,45,23,78,33,121,34,322,-76;intsize=a.length;LinkedListNodehead=newLi

16、nkedListNode(asize-1);for(inti=size-2;i>=0;i-)head=newLinkedListNode(ai,head);returnhead;publicstaticvoidshow(LinkedListNodehead)while(head!=null)System.out.print(head.getValue();head=head.getNext();if(head!=null)System.out.print("->");System.out.println("n");publicstaticLi

17、nkedListNodeappend(LinkedListNodehead,LinkedListNodenew_p)if(head=null)head=new_p;else/p指向当前头节点(非空的)LinkedListNodep=head;/n为p的后继节点(可能为空值)LinkedListNoden=p.getNext();while(n!=null)p=n;n=p.getNext();p.setNext(new_p);returnhead;publicstaticLinkedListNodedelete(LinkedListNodehead,intv)/删除链表开头的连续多个节点whil

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

19、ListNodehead)/创建一个空的结果链表LinkedListNodenhead=null;/依次取出源链表中的每一个节点，并将之插入到有序的结构链表中，仍然结构链表的有序状态while(head!=null)LinkedListNodec=head;head=head.getNext();c.setNext(null);/将c这个节点插入到有序的链表nhead中nhead=LinkedListTool.insert(nhead,c);returnnhead;head,/向有序链表中插入一个新节点，并保持其有序状态publicstaticLinkedListNodeinsert(Link

20、edListNodeLinkedListNoden)/如果目标链表为空链表if(head=null)head=n;elseif(n.getValue()<head.getValue()n.setNext(head);head=n;elseLinkedListNodep1=head;LinkedListNodep2=head.getNext();while(p2!=null&&n.getValue()>p2.getValue()p1=p2;p2=p2.getNext();/将n节点插入到p1和p2两个节点之间p1.setNext(n);n.setNext(p2);re

21、turnhead;publicstaticLinkedListNodemerge(LinkedListNodehead1,LinkedListNodehead2)head2=LinkedListTool.sort(head2);/依次取出headl链表中的每一个节点，并将之插入到有序的head2链表中，仍然结构链表的有序状态while(head1!=null)LinkedListNodec=head1;head1=head1.getNext();c.setNext(null);/将c这个节点插入到有序的链表nhead中head2=LinkedListTool.insert(head2,c);r

22、eturnhead2;8.TreeToolublicclassTreeToolpublicstaticvoidmain(Stringargs)TreeNoderoot=TreeTool.createLinkedList();TreeTool.list(root);/构建一颗二叉树publicstaticTreeNodecreateLinkedList()TreeNoden1=newTreeNode(9,null,null);TreeNoden2=newTreeNode(12,null,null);TreeNoden3=newTreeNode(49,n1,n2);TreeNoden4=newTreeNode(54,null,null);TreeNoden5=newTreeNode(37,n3,n4);returnn5;/遍历二叉树(中序遍历)publicstaticvoidlist(TreeNoderoot)if(root!=null)list(root.getLchild();System.out.println(root.getValue();list(root.getRchild();/遍历