實驗二 線性表

1、實驗報告二 線性表一、 實驗目的：（1） 理解線性表的邏輯結構、兩種存儲結構和數據操作；（2） 應用順序表的基本算法實現集合A=AUB算法，應用順序表的基本算法實現兩有序順序表的歸并算法；（單鏈表的歸并算法）（3） 掌握單鏈表的遍歷、插入和刪除等操作算法，實現多項式相加。二、 實驗內容：1、設有線性表 LA（3,5,8,11）和 LB=（2,6,8,9,11,15,20）； 若LA和LB分別表示兩個集合A和B，求新集合 AA U B（并操作，相同元素不保留）； 預測輸出：LA=（3,5,8,11,2,6,9,15,20）實現代碼：package Q1_1;public class Node&l

2、t;T> public T data;public Node<T> next;public Node(T data,Node<T> next)this.data=data;this.next=next;public Node()this(null,null);package Q1_1;import Q1_2.Node;public class LList public static Node<Integer> headA;public static Node<Integer> headB;public static Node<Inte

3、ger> CreateLA()int A=3,5,8,11;Node<Integer> LA = new Node<Integer>();headA=LA;for(int i=0;i<A.length;i+)LA.next=new Node<Integer>(Ai,null);LA=LA.next ;return headA;public static Node<Integer> CreateLB()int B=2,6,8,9,11,15,20;Node<Integer> LB = new Node<Integer&

4、gt;();headB=LB;for(int i=0;i<B.length;i+)LB.next=new Node<Integer>(Bi,null);LB=LB.next ;return headB;public static boolean Compare(Node<Integer> List,int t)Node<Integer> p=List.next;boolean flag=false;while(p!=null)if(p.data=t)flag=true;p=p.next ;return flag;public static Node&l

5、t;Integer> link(Node<Integer> LA,Node<Integer> LB)LB=LB.next;LA=LA.next;boolean flag;Node<Integer> rear = null;while(LA!=null)rear=LA;LA=LA.next;while(LB!=null)flag=Compare(headA,LB.data);if(flag=false)Node<Integer >temp =new Node<Integer>(LB.data,null);rear.next=tem

6、p;rear=rear.next;LB=LB.next;elseLB=LB.next;return headA;public static void main(String args) Node<Integer> t = new Node<Integer>();headA=CreateLA();headB=CreateLB();t=link(headA,headB);while(t.next!=null)System.out.printf("%-3d",t.next.data);t=t.next;粘貼運行結果： 將LA與LB表歸并，要求仍有序（相同元

7、素要保留）預測輸出：LC=（2,3,5,6,8,8,9,11,11,15,20）package Q1_2;public class Node<T> public T data;public Node<T> next;public Node(T data,Node<T> next)this.data=data;this.next=next;public Node()this(null,null);package Q1_2;import java.util.*;public class LList public static Node<Integer>

8、; headA;public static Node<Integer> headB;public static Node<Integer> CreateLA()int A=3,5,8,11;Node<Integer> LA = new Node<Integer>();headA=LA;for(int i=0;i<A.length;i+)LA.next=new Node<Integer>(Ai,null);LA=LA.next ;return headA;public static Node<Integer> Crea

9、teLB()int B=2,6,8,9,11,15,20;Node<Integer> LB = new Node<Integer>();headB=LB;for(int i=0;i<B.length;i+)LB.next=new Node<Integer>(Bi,null);LB=LB.next ;return headB;public static Node<Integer> compare(Node<Integer> LA,Node<Integer> LB)LB=LB.next;LA=LA.next;while(

10、LA!=null)if(LB.data <= LA.data && LA.data <LB.next.data)Node<Integer >temp =new Node<Integer>(LA.data,null);temp.next=LB.next ;LB.next=temp;LA=LA.next ;elseLB=LB.next ;return headB;public static void main(String args) Node<Integer> t = new Node<Integer>();headA=

11、CreateLA();headB=CreateLB();t=compare(headA,headB);while(t.next!=null)System.out.printf("%-3d",t.next.data);t=t.next;粘貼運行結果：2、在SinglyLinkedList類中增加下列成員方法。public SinglyLinkedList(E element)/由指定數組中的多個對象構造單鏈表public SinglyLinkedList(SinglyLinkedList list)/以單鏈表list構造新的單鏈表，復制單鏈表public void conca

12、t(SinglyLinkedList list)/將指定單鏈表list鏈接在當前單鏈表之后public Node<E> search(E element)/若查找到指定，則返回結點，否則返回nullpublic boolean contain (E element)/以查找結果判斷單鏈表是否包含指定對象public boolean remove (E element)/移去首次出現的指定對象public boolean replace (Object obj, E element)/將單鏈表中的obj對象替換為對象elementpublic boolean equals(Objec

13、t obj)/比較兩條單鏈表是否相等實現代碼：package Q2;public class Node<T> public T data;public Node<T> next;public Node(T data,Node<T> next)this.data=data;this.next=next;public Node()this(null,null);package Q2;public class SinglyLinkedList<E>Node<E> head;public SinglyLinkedList(E element)

14、/由指定數組中的多個對象構造單鏈表head = new Node<E>(); Node<E> List = head;for(int i=0;i<element.length;i+)List.next=new Node(elementi,null);List=List.next ;public SinglyLinkedList(SinglyLinkedList list)/以單鏈表list構造新的單鏈表，復制單鏈表head=new Node<E>();Node<E> list_new = head;Node<E> p=list.

15、head;if(p.data=null)p=p.next;list_new=list_new.next;while(p!=null)list_new.next =new Node<E>(p.data,null);list_new=list_new.next;p=p.next ;public void concat(SinglyLinkedList list)/將指定單鏈表list鏈接在當前單鏈表之后Node<E> rear = null;Node<E> p = head;Node<E> q=list.head.next ;if(p.data=nu

16、ll)p=p.next ;while(p!=null)rear=p;p=p.next ;if(q=null)q=q.next ;rear.next=q;public Node<E> search(E element)/若查找到指定，則返回結點，否則返回nullNode<E> p=this.head;Node<E> temp=null;if(p=null)p=p.next ;while(p.next!=null)if(p.data=element)temp=p;p=p.next ;return temp;public boolean contain (E el

17、ement)/以查找結果判斷單鏈表是否包含指定對象boolean flag=false;Node<E> p=this.head;Node<E> temp=null;if(p=null)p=p.next ;while(p!=null)if(p.data=element)flag=true;p=p.next ;return flag;public boolean remove (E element)/移去首次出現的指定對象Node<E> p=this.head;Node<E> temp=null;Node<E> front=head;bo

18、olean flag=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 ;return flag;public boolean replace (Object obj, E element)/將單鏈表中的obj對象替換為對象elementboolean flag=false; if (obj!=null && element!=null) Nod

19、e<E> p=this.head; while (p!=null) if (obj.equals(p.data) p.data = element; flag = true; p = p.next; return flag;public boolean equals(Object obj)/比較兩條單鏈表是否相等boolean flag=true;SinglyLinkedList x=(SinglyLinkedList) obj;Node t=x.head.next;Node s=this.head.next;while(t!=null&&s!=null)if(t.

20、data!=s.data)flag=false;break;t=t.next;s=s.next; return flag;package Q2;import java.util.*;public class Test static Integer x=3,5,8,11;static Integer x1=3,5,8,11;static Integer x2=2,6,8,9,11,15,20;static SinglyLinkedList<Integer> List1=new SinglyLinkedList<Integer>(x);static SinglyLinked

21、List<Integer> List2=new SinglyLinkedList<Integer>(x1);static SinglyLinkedList<Integer> List3=new SinglyLinkedList<Integer>(x2);public static void disList(SinglyLinkedList List)for(Node temp=List.head.next;temp!=null;temp=temp.next)System.out.printf("%-5d",temp.data)

22、;System.out.println();public static void concat()List1.concat(List3);public static void Find()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("

23、List1中找不到指定的數。");public static void Contain()System.out.println("請輸入所需包含的數：");Scanner scan=new Scanner(System.in);Integer element=scan.nextInt();if(List3.contain(element)System.out.printf("List3包含指定的數%-5dn",element);elseSystem.out.printf("List3不包含指定的數%-5dn",element

24、);public static void remove()System.out.println("請輸入指定移除的數：");Scanner scan=new Scanner(System.in);Integer element=scan.nextInt();if(List3.remove(element)System.out.printf("%-5d已在List3中移除n",element);else System.out.printf("%-5d無法在List3中找到，無法移除n",element);public static vo

25、id replace()System.out.println("請輸入所需交換的兩個數：");Scanner scan=new Scanner(System.in);Integer obj=scan.nextInt();Integer element=scan.nextInt();if(List3.replace(obj, element)System.out.printf("%-5d與%-5d兩個數成功交換n",obj,element);else System.out.println("無法改動");public static vo

26、id equals()if(List1.equals(List2)System.out.println("List1與List2兩個單鏈表相等");else System.out.println("List1與List2兩個單鏈表不相等");if(List1.equals(List3)System.out.println("List1與List3兩個單鏈表相等");else System.out.println("List1與List3兩個單鏈表不相等");public static void main(Strin

27、g args) disList(List1);disList(List2);disList(List3);concat();disList(List1);Find();Contain();remove();replace();equals();3、算法實現：多項式相加一條單鏈表可以表示一個一元多項式，每個結點包含三個域：指數域、系數域和后繼結點鏈。表示多項式的單鏈表如圖1所示。給定兩個多項式，實現兩個多項式相加算法。 系數 指數 鏈5 1-10 0 -6 23 4 head實現代碼：package Q3;public class Node<T> public T base;publ

28、ic T index;public Node<T> next;public Node(T base,T index,Node<T> next)this.base=base;this.index=index;this.next=next;public Node()this(null,null,null);package Q3;public class Polynomial public static Node<Integer> head;public static Node<Integer> Create(int t)Node<Integer

29、> p=new Node<Integer>();head=p;for(int i=0;i<t.length;i+)p.next=new Node<Integer>(ti0,ti1, null);p=p.next;print(head);return head;public static void print(Node<Integer> a)a=a.next;while(a.next!=null)System.out.print(a.base+""+a.index+" + ");a=a.next;System.out.print(a.base+""+a.index);System.out.println();public static Node<Integer> Add(Node<Integer> a,Node<Integer> b)Node<In