华南农业大学数据结构java版实验二

《华南农业大学数据结构java版实验二》由会员分享，可在线阅读，更多相关《华南农业大学数据结构java版实验二（27页珍藏版）》请在装配图网上搜索。

1、实验报告二线性表华南农业大学信息（软件）学院数据结构（JAVA ）综合性、设计性实验成绩单开设时间： 2017 学年第二学期班级16 信管 3 班学号2016250403xx姓名黄 xx实验题实验二线性表的基本操作目成绩教师签名一，实验目的：（1）理解线性表的逻辑结构、两种存储结构和数据操作，熟练运用JAVA语言实现线性表的基本操作，分析各种操作算法特点和时间复杂度。（ 2） 掌握单链表的遍历、插入和删除等操作算法，实现多项式相加。二， 实验内容：1、设计一个有序顺序表（元素已排序，递增或递减），实现插入、删除等操作，元素插入位置由其值决定。实现：（1）升序排序顺序表类名为：SortedSeq

2、List，存成 SortedSeqList.java文件；（ 2）另外编写 SortedSeqList_ex.java文件来演示调用排序顺序表publicclassSortedSeqList privateintMAX_SIZE = 10;privateintary =new int MAX_SIZE;privateintlength= 0;publicSortedSeqList(intarray) if( array=null|array. lengththis. length= 0;elseary=array;length= array.length;=0)publicvoidclear(

3、) length= 0;publicbooleanisEmpty() returnlength= 0;publicvoiddelete(intindex)throwsException if(length=0)thrownew Exception(No elment to delete);intnewAry =newint ary . length- 1;for(inti= 0,j = 0;iary . length ; i+) if(i=index) continue;elsenewAry j + =ary i ;ary=newAry ;length-;publicintinsert(int

4、value)throwsException if(length=MAX_SIZE) thrownew Exception(List is full, cant insert moreintnewAry=newint length+ 1;inti= 0,j= 0;for(;i=value) newAry j =value;break;elsenewAry j =ary i ;while( iary . length) newAry + j =ary i ;i +;ary =newAry ;length+;returnvalue;publicvoiddisplay() System. out .p

5、rintln(nList now is: );for( inti = 0;i ary . length;i +) System.out .print(ary i +t);精选文库);2精选文库（ 2） SortedSeqList_ex.java文件来演示调用排序顺序表public class SortedSeqList_ex public static void main(String args) throws Exception int ary = 1, 2, 3, 5, 7;SortedSeqList list = new SortedSeqList(ary);list.display()

6、;list.insert(4);list.display();list.delete(2);list.display();（3）实验结果2、在 SinglyLinkedList类中增加下列成员方法。public SinglyLinkedList(E element)/由指定数组中的多个对象构造单链表publicSinglyLinkedList(SinglyLinkedListlist)/以单链表 list构造新的单链表，复制单链表public void concat(SinglyLinkedList list)/将指定单链表list链接在当前单链表之后public Node search(E

7、element)/若查找到指定，则返回结点，否则返回nullpublic boolean contain (E element)/以查找结果判断单链表是否包含指定对象public boolean remove (E element)/移去首次出现的指定对象public boolean replace (Object obj, E element)/将单链表中的obj对象替换为对象 elementpublic boolean equals(Object obj)/比较两条单链表是否相等（1）实现代码：packageQ2;publicclassNode publicTdata ;publicNod

8、enext ;publicNode(T data,Node next)this. data =data;this. next =next;publicNode()this( null, null);packageQ2;3精选文库publicclassSinglyLinkedListNodehead ;publicSinglyLinkedList(E element)/ 由指定数组中的多个对象构造单链表head =new Node();Node List =head ;for ( inti=0;ielement.length;i+)List.next =new Node(elementi,nul

9、l);List=List.next;publicSinglyLinkedList(SinglyLinkedList list)/ 以单链表 list构造新的单链表，复制单链表head =new Node();Node list_new =head ;Node p=list.head ;if (p.data =null)p=p. next ;list_new=list_new.next ;while(p!= null)list_new.next= new Node(p.data , null);list_new=list_new.next ;p=p. next;publicvoidconcat(

10、SinglyLinkedList list)/ 将指定单链表list链接在当前单链表之后Node rear =null;Node p =head ;Node q=list.head . next;if (p.data =null)p=p. next;while(p!= null)rear=p;p=p. next;if (q= null)q=q. next;rear.next =q;public Node search(E element) / 若查找到指定，则返回结点，否则返回 null Node p= this . head ;4精选文库Node temp=null;if(p= null)p

11、=p. next;while(p.next!= null)if(p.data=element)temp=p;p=p. next;returntemp;publicbooleancontain (E element)/以查找结果判断单链表是否包含指定对象booleanflag=false;Node p=this. head ;Node temp=null;if(p= null)p=p. next;while(p!=null)if(p.data=element)flag=true;p=p. next;returnflag;publicbooleanremove (E element)/移去首次出现

12、的指定对象Node p=this. head ;Node temp=null;Node front=head ;booleanflag=false;if(p= null)p=p. next;while(p!=null& temp= null)if(p.data=element)temp=p;flag=true;break;p=p. next;front=front.next ;front=p.next;returnflag;5精选文库publicbooleanreplace (Object obj, E element)/ 将单链表中的obj 对象替换为对象 elementbooleanfla

13、g=false;if(obj!=null& element!=null)Node p=this. head ;while(p!=null)if(obj.equals(p.data )p.data= element;flag =true;p = p.next ;returnflag;publicbooleanequals(Object obj)/ 比较两条单链表是否相等booleanflag=true;SinglyLinkedList x=(SinglyLinkedList) obj;Node t=x.head . next ;Node s= this. head . next ;while(t

14、!=null&s!= null)if(t.data !=s.data )flag=false;break ;t=t.next ;s=s. next ;returnflag;packageQ2;importjava.util.*;publicclass Test staticIntegerx =3,5,8,11;staticIntegerx1 =3,5,8,11;staticIntegerx2 =2,6,8,9,11,15,20;staticSinglyLinkedListList1=new SinglyLinkedList(x);staticSinglyLinkedListList2= new

15、 SinglyLinkedList(x1 );staticSinglyLinkedListList3= new SinglyLinkedList(x2 );publicstaticvoid disList(SinglyLinkedList List)for(Node temp=List.head . next;temp!= null ;temp=temp. next )6精选文库System.out .printf(%-5d ,temp.data );System. out .println();publicstaticvoidconcat()List1.concat(List3);publi

16、cstaticvoidFind()System.out.println( 请输入需要查找的数： );Scanner scan=new Scanner(System.in );Integer element=scan.nextInt();Node t=List1.search(element);if(t!=null)System.out.println(t.data);elseSystem.out.println(List1中找不到指定的数。 );publicstaticvoidContain()System.out.println( 请输入所需包含的数： );Scanner scan=new

17、Scanner(System.in );Integer element=scan.nextInt();if( List3.contain(element)System.out.printf(List3包含指定的数 %-5dn,element);elseSystem.out.printf(List3不包含指定的数 %-5dn,element);publicstaticvoidremove()System.out.println( 请输入指定移除的数： );Scanner scan=new Scanner(System.in );Integer element=scan.nextInt();if(

18、 List3.remove(element)System.out.printf(%-5d 已在 List3中移除 n ,element);elseSystem.out .printf(%-5d无法在 List3中找到，无法移除 n ,element);publicstaticvoidreplace()System.out.println( 请输入所需交换的两个数： );Scanner scan=new Scanner(System.in );Integer obj=scan.nextInt();Integer element=scan.nextInt();if( List3.replace(o

19、bj, element)System.out.printf(%-5d 与 %-5d 两个数成功交换 n,obj,element);elseSystem.out .println( 无法改动 );publicstaticvoidequals()7精选文库if ( List1.equals(List2)System. out.println(List1与 List2两个单链表相等 );elseSystem.out .println(List1与 List2两个单链表不相等 );if ( List1.equals(List3)System. out.println(List1与 List3两个单链表

20、相等 );elseSystem.out .println(List1与 List3两个单链表不相等 );publicstaticvoidmain(String args) disList( List1);disList( List2);disList( List3);concat ();disList( List1);Find();Contain();remove ();replace();equals ();（2）实验结果3，先写出LList接口并写上要实现的方法的方法头，再CircSinglyLinkedList类中继承该接口并实现其方法。（ 1）写出 LList 接口 ;publicin

21、terfaceLList booleanisEmpty();intsize();T get(inti);voidset(inti,T x);String toString();T remove(inti);voidclear();intsearch(T key);booleancontains(T key);T insertDifferent(T x);T remove(T key);8精选文库booleanequals(Object obj);(2) 结点类package Lab2;publicclassNode publicTdata ;publicNodenext ;publicNode

22、(T data, Node next)this. data= data;this. next= next;publicNode()this( null,null);publicString toString()returnthis. data .toString();（ 3） CircSinglyLinkedList类publicclassCircSinglyLinkedListimplementsLListpublicNodehead ;OverridepublicbooleanisEmpty() / TODOAuto-generated method stubreturnthis. hea

23、d . next =null;Overridepublicintsize() / TODOAuto-generated method stubNode temp =this. head . next ;intcount = 0;while (temp!=null)count+;temp = temp.next ;returncount;9精选文库OverridepublicT get(inti) / TODOAuto-generated method stubNode temp =this. head ;intcount = 0;while ( true )count+=1;temp = te

24、mp.next ;if (count=i)returntemp.data ;Overridepublicvoidset(inti, T x) / TODOAuto-generated method stubNode temp =this. head ;intcount = 0;while ( true )count+=1;temp = temp.next ;if (count=i)temp. data= x;OverridepublicT remove(inti) / TODOAuto-generated method stub int count=0;Node temp =this. hea

25、d ;Node p;for (; ; temp=temp.next )if (count+1=i)p = temp.next ;temp. next= temp.next . next ;return(T) p;count+;10精选文库Overridepublicvoidclear() / TODOAuto-generated method stub this . head . next = null ;Overridepublicintsearch(Object key) / TODOAuto-generated method stubinti=0;Node temp =this. hea

26、d . next ;for (; temp.next != null; temp=temp.next )i+=1;if (temp.data .equals(key)break ;returni;Overridepublicbooleancontains(Object key) / TODOAuto-generated method stubNode temp =this. head . next ;for (; temp.next != null; temp=temp.next )if (temp.data .equals(key)returntrue ;returnfalse;Overri

27、depublicNode insertDifferent(T x) / TODOAuto-generated method stubNode front=this. head , p=front.next ;while(p!=null& !p.data .equals(x)front = p;p = p.next ;if(p!=null)11精选文库System.out .println(x= +x+ ，元素重复，未插入。 );returnp;returnfront.next=new Node(x,null);OverridepublicT remove(Object key) /TODOAu

28、to-generated method stubNode temp =this. head ;Node p;for (; ; temp=temp.next )if (temp.next . data .equals(key)p = temp.next ;temp. next= temp.next . next ;return(T)p;4，先写出LList接口并写上要实现的方法的方法头，再DoublyLinkedList类中继承该接口并实现其方法。（1）双结点类publicclassDoubleNode publicTdata ;publicDoubleNodeprev , next ;publ

29、ic DoubleNode(T data, DoubleNode prev, DoubleNode next)this. data= data;this. prev= prev;this. next= next;publicDoubleNode(T data)this(data,null,null);publicDoubleNode()this( null,null,null);publicString toString()12精选文库returnthis. data .toString();（ 2） LList 接口publicinterfaceLList booleanisEmpty();

30、intsize();T get( inti);voidset(inti,T x);String toString();T remove(inti);voidclear();intsearch(T key);booleancontains(T key);T insertDifferent(T x);T remove(T key);booleanequals(Object obj);（ 3） DoublyLinkedList类publicclassDoublyLinkedListimplementsLListDoubleNodehead ;OverridepublicbooleanisEmpty(

31、) / TODOAuto-generated method stubreturnthis. head . next =null;Overridepublicintsize() / TODOAuto-generated method stubDoubleNode temp =this. head . next ;intcount = 0;while (temp!=null)count+;temp = temp.next ;returncount;OverridepublicT get(inti) / TODOAuto-generated method stub13精选文库DoubleNode t

32、emp =this. head ;intcount = 0;while ( true )count+=1;temp = temp.next ;if (count=i)returntemp.data ;Overridepublicvoidset(inti, T x) / TODOAuto-generated method stubDoubleNode temp =this. head ;intcount = 0;while ( true )count+=1;temp = temp.next ;if (count=i)temp. data= x;OverridepublicT remove(int

33、i) / TODOAuto-generated method stub int count=0;DoubleNode temp =this. head ;DoubleNode p;for (; ; temp=temp.next )if (count+1=i)p = temp.next ;temp. next= temp.next . next ;temp. next . next . prev= temp;return(T) p;count+;Overridepublicvoidclear() 14精选文库/ TODOAuto-generated method stub this . head

34、 . next = null ;Overridepublicintsearch(Object key) / TODOAuto-generated method stub int i=0;DoubleNode temp =this. head . next ;for (; temp.next != null; temp=temp.next )i+=1;if (temp.data .equals(key)break ;returni;Overridepublicbooleancontains(Object key) / TODOAuto-generated method stubDoubleNod

35、e temp =this. head . next ;for (; temp.next != null; temp=temp.next )if (temp.data .equals(key)returntrue ;returnfalse;OverridepublicT insertDifferent(T x) / TODOAuto-generated method stubDoubleNode p=this. head ;while(p!=null& !p.data .equals(x)p = p.next ;if(p!=null)System.out .println(x= +x+ ，元素重

36、复，未插入。 );return(T)p;return(T)(p.next=new DoubleNode(x, p,null);15精选文库5，根据循环双链表表的成员方法声明。SortedCirDoublyList类publicclassSortedCirDoublyList publicDoubleNodehead ;publicSortedCirDoublyList()this. head =new DoubleNode();this. head . prev =this. head ;this. head . next=this. head ;publicSortedCirDoublyLi

37、st(T values)this();DoubleNode rear =this. head ;for( inti=0; ivalues.length; i+)rear.next=new DoubleNode(valuesi, rear,this. head );rear = rear.next ;this. head . prev= rear;publicSortedCirDoublyList(CirDoublyList list)this();DoubleNode rear =this. head ;rear.next=new DoubleNode(p.data , rear,this.

38、head );rear = rear.next ;this. head . prev= rear;6，实现循环双链表类，接着再查看LList接口中的方法并实现。（ 1） List 接口类publicinterfaceLList booleanisEmpty();intsize();T get(inti);voidset(inti,T x);16精选文库String toString();T remove(inti);voidclear();intsearch(T key);booleancontains(T key);T insertDifferent(T x);T remove(T key)

39、;booleanequals(Object obj);（ 2） 双结点类package Lab2;publicclassDoubleNode publicTdata ;publicDoubleNodeprev , next ;public DoubleNode(T data, DoubleNode prev, DoubleNode next)this. data = data;this. prev = prev;this. next= next;publicDoubleNode(T data)this(data,null,null);publicDoubleNode()this( null,n

40、ull,null);publicString toString()returnthis. data .toString();（3） CHDoublelyLinkedList类package Lab2;publicclassCHDoublelyLinkedListimplementsLList DoubleNodehead ;OverridepublicbooleanisEmpty() / TODOAuto-generated method stub17精选文库returnthis. head . next =null;Overridepublicintsize() / TODOAuto-gen

41、erated method stubDoubleNode temp =this. head . next ;intcount = 0;while (temp!=head )count+;temp = temp.next ;returncount;OverridepublicE get(inti) / TODOAuto-generated method stubDoubleNode temp =this. head ;intcount = 0;while ( true )count+=1;temp = temp.next ;if (count=i)returntemp.data ;Overrid

42、epublicvoidset(inti, E x) / TODOAuto-generated method stubDoubleNode temp =this. head ;intcount = 0;while ( true )count+=1;temp = temp.next ;if (count=i)temp. data= x;Override18精选文库publicE remove(inti) / TODOAuto-generated method stub int count=0;DoubleNode temp =this. head ;DoubleNode p;for (; ; temp=temp.next )if