实验二 线性表

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