实验二 线性表.docVIP

实验报告二 线性表一、 实验目的：（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 public T data;public Node next;public Node(T data,Node 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 headA;public static Node headB;public static Node CreateLA()int A=3,5,8,11;Node LA = new Node();headA=LA;for(int i=0;iA.length;i+)LA.next=new Node(Ai,null);LA=LA.next ;return headA;public static Node CreateLB()int B=2,6,8,9,11,15,20;Node LB = new Node();headB=LB;for(int i=0;iB.length;i+)LB.next=new Node(Bi,null);LB=LB.next ;return headB;public static boolean Compare(Node List,int t)Node p=List.next;boolean flag=false;while(p!=null)if(p.data=t)flag=true;p=p.next ;return flag;public static Node link(Node LA,Node LB)LB=LB.next;LA=LA.next;boolean flag;Node rear = null;while(LA!=null)rear=LA;LA=LA.next;while(LB!=null)flag=Compare(headA,LB.data);if(flag=false)Nodetemp =new Node(LB.data,null);rear.next=temp;rear=rear.next;LB=LB.next;elseLB=LB.next;return headA;public static void main(String args) Node t = new Node();headA=CreateLA();headB=CreateLB();t=link(headA,headB);while(t.next!=null)System.out.printf(%-3d,t.next.data);t=t.next;粘贴运行结果： 将LA与LB表归并，要求仍有序（相同元素要保留）预测输出：LC=（2,3,5,6,8,8,9,11,11,15,20）package Q1_2;public class Node public T data;public Node next;public Node(T data,Node next)this.data=data;this.next=next;public Node()this(null,null);package Q1_2;import java.util.*;public class LList public static Node headA;public static Node headB;public static Node CreateLA()int A=3,5,8,11;Node LA = new Node();headA=LA;for(int i=0;iA.length;i+)LA.next=new Node(Ai,null);LA=LA.next ;return headA;public static Node CreateLB()int B=2,6,8,9,11,15,20;Node LB = new Node();headB=LB;for(int i=0;iB.length;i+)LB.next=new Node(Bi,null);LB=LB.next ;return headB;public static Node compare(Node LA,Node LB)LB=LB.next;LA=LA.next;while(LA!=null)if(LB.data = LA.data & LA.data LB.next.data)Nodetemp =new Node(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 t = new Node();headA=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 concat(SinglyLinkedList list)/将指定单链表list链接在当前单链表之后public Node search(E element)/若查找到指定，则返回结点，否则返回nullpublic boolean contain (E element)/以查找结果判断单链表是否包含指定对象public boolean remove (E element)/移去首次出现的指定对象public boolean replace (Object obj, E element)/将单链表中的obj对象替换为对象elementpublic boolean equals(Object obj)/比较两条单链表是否相等实现代码：package Q2;public class Node public T data;public Node next;public Node(T data,Node next)this.data=data;this.next=next;public Node()this(null,null);package Q2;public class SinglyLinkedListNode head;public SinglyLinkedList(E element)/由指定数组中的多个对象构造单链表head = new Node(); Node List = head;for(int i=0;ielement.length;i+)List.next=new Node(elementi,null);List=List.next ;public SinglyLinkedList(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 ;public void concat(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)/若查找到指定，则返回结点，否则返回nullNode p=this.head;Node 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 element)/以查找结果判断单链表是否包含指定对象boolean flag=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 ;return flag;public boolean remove (E element)/移去首次出现的指定对象Node p=this.head;Node temp=null;Node front=head;boolean 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) Node 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.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 List1=new SinglyLinkedList(x);static SinglyLinkedList List2=new SinglyLinkedList(x1);static SinglyLinkedList List3=new SinglyLinkedList(x2);public static void disList(SinglyLinkedList List)for(Node temp=List.head.next;temp!=null;temp=temp.next)System.out.printf(%-5d,temp.data);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(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);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 void 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 void 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(String 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 public T base;public T index;public Node next;public Node(T base,T index,Node next)this.base=base;this.index=index;this.next=next;public Node()this(null,null,null);package Q3;public class Polynomial public static Node head;public static Node Create(int t)Node p=new Node();head=p;for(int i=0;it.length;i+)p.next=new Node(ti0,ti1, null);p=p.next;print(head);return head;public static void print(Node 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 Add(Node