實驗報告二 線性表華 南 農(nóng) 業(yè) 大 學(xué) 信 息（軟 件）學(xué) 院數(shù)據(jù)結(jié)構(gòu)（JAVA）綜合性、設(shè)計性實驗成績單開設(shè)時間：2017學(xué)年第二學(xué)期班級16信管3班學(xué)號2016250403xx姓名黃xx實驗題目實驗二 線性表的基本操作成績教師簽名一， 實驗?zāi)康模海?） 理解線性表的邏輯結(jié)構(gòu)、兩種存儲結(jié)構(gòu)和數(shù)據(jù)操作，熟練運用JAVA語言實現(xiàn)線性表的基本操作，分析各種操作算法特點和時間復(fù)雜度。（2） 掌握單鏈表的遍歷、插入和刪除等操作算法，實現(xiàn)多項式相加。二， 實驗內(nèi)容：1、設(shè)計一個有序順序表（元素已排序，遞增或遞減），實現(xiàn)插入、刪除等操作，元素插入位置由其值決定。實現(xiàn)：（1）升序排序順序表類名為：SortedSeqList，存成SortedSeqList.java文件；（2）另外編寫SortedSeqList_ex.java文件來演示調(diào)用排序順序表public class SortedSeqList private int MAX_SIZE = 10;private int ary = new intMAX_SIZE;private int length = 0;public SortedSeqList(int array) if (array = null | array.length = 0) this.length = 0; else ary = array;length = array.length;public void clear() length = 0;public boolean isEmpty() return length = 0;public void delete(int index) throws Exception if (length = 0) throw new Exception(No elment to delete);int newAry = new intary.length - 1;for (int i = 0, j = 0; i ary.length; i+) if (i = index) continue; else newAryj+ = aryi;ary = newAry;length-;public int insert(int value) throws Exception if (length = MAX_SIZE) throw new Exception(List is full, cant insert more);int newAry = new intlength + 1;int i = 0, j = 0;for (; i = value) newAryj = value;break; else newAryj = aryi;while (i ary.length) newAry+j = aryi;i+;ary = newAry;length+;return value;public void display() System.out.println(nList now is: );for (int i = 0; i ary.length; i+) System.out.print(aryi + t);（2）SortedSeqList_ex.java文件來演示調(diào)用排序順序表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();list.insert(4);list.display();list.delete(2);list.display();（3）實驗結(jié)果2、在SinglyLinkedList類中增加下列成員方法。public SinglyLinkedList(E element)/由指定數(shù)組中的多個對象構(gòu)造單鏈表public SinglyLinkedList(SinglyLinkedList list)/以單鏈表list構(gòu)造新的單鏈表，復(fù)制單鏈表public void concat(SinglyLinkedList list)/將指定單鏈表list鏈接在當(dāng)前單鏈表之后public Node search(E element)/若查找到指定，則返回結(jié)點，否則返回nullpublic boolean contain (E element)/以查找結(jié)果判斷單鏈表是否包含指定對象public boolean remove (E element)/移去首次出現(xiàn)的指定對象public boolean replace (Object obj, E element)/將單鏈表中的obj對象替換為對象elementpublic boolean equals(Object obj)/比較兩條單鏈表是否相等（1）實現(xiàn)代碼：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)/由指定數(shù)組中的多個對象構(gòu)造單鏈表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構(gòu)造新的單鏈表，復(fù)制單鏈表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鏈接在當(dāng)前單鏈表之后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)/若查找到指定，則返回結(jié)點，否則返回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)/以查找結(jié)果判斷單鏈表是否包含指定對象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)/移去首次出現(xiàn)的指定對象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(請輸入需要查找的數(shù)：);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中找不到指定的數(shù)。);public static void Contain()System.out.println(請輸入所需包含的數(shù)：);Scanner scan=new Scanner(System.in);Integer element=scan.nextInt();if(List3.contain(element)System.out.printf(List3包含指定的數(shù)%-5dn,element);elseSystem.out.printf(List3不包含指定的數(shù)%-5dn,element);public static void remove()System.out.println(請輸入指定移除的數(shù)：);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(請輸入所需交換的兩個數(shù)：);Scanner scan=new Scanner(System.in);Integer obj=scan.nextInt();Integer element=scan.nextInt();if(List3.replace(obj, element)System.out.printf(%-5d與%-5d兩個數(shù)成功交換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();（2）實驗結(jié)果3，先寫出LList接口并寫上要實現(xiàn)的方法的方法頭，再CircSinglyLinkedList類中繼承該接口并實現(xiàn)其方法。（1）寫出LList接口;public interface LList boolean isEmpty();int size();T get(int i);void set(int i,T x);String toString();T remove(int i);void clear();int search(T key);boolean contains(T key);T insertDifferent(T x);T remove(T key);boolean equals(Object obj);(2)結(jié)點類package Lab2;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); public String toString() return this.data.toString();（3）CircSinglyLinkedList類public class CircSinglyLinkedList implements LListpublic Node head; Overridepublic boolean isEmpty() / TODO Auto-generated method stubreturn this.head.next=null;Overridepublic int size() / TODO Auto-generated method stubNode temp = this.head.next;int count = 0;while(temp!=null)count+;temp = temp.next;return count;Overridepublic T get(int i) / TODO Auto-generated method stubNode temp = this.head;int count = 0;while(true)count+=1;temp = temp.next;if(count=i)return temp.data;Overridepublic void set(int i, T x) / TODO Auto-generated method stubNode temp = this.head;int count = 0;while(true)count+=1;temp = temp.next;if(count=i)temp.data = x;Overridepublic T remove(int i) / TODO Auto-generated method stubint count=0;Node temp = this.head;Node p;for(; ; temp=temp.next)if(count+1=i)p = temp.next;temp.next = temp.next.next;return (T) p;count+;Overridepublic void clear() / TODO Auto-generated method stubthis.head.next = null;Overridepublic int search(Object key) / TODO Auto-generated method stubint i=0;Node temp = this.head.next;for(; temp.next!=null; temp=temp.next)i+=1;if(temp.data.equals(key)break;return i;Overridepublic boolean contains(Object key) / TODO Auto-generated method stubNode temp = this.head.next;for(; temp.next!=null; temp=temp.next)if(temp.data.equals(key)return true;return false;Overridepublic Node insertDifferent(T x) / TODO Auto-generated method stubNode front=this.head, p=front.next; while (p!=null & !p.data.equals(x) front = p; p = p.next; if (p!=null) System.out.println(x=+x+，元素重復(fù)，未插入。); return p; return front.next = new Node(x,null);Overridepublic T remove(Object key) / TODO Auto-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接口并寫上要實現(xiàn)的方法的方法頭，再DoublyLinkedList類中繼承該接口并實現(xiàn)其方法。（1）雙結(jié)點類public class DoubleNode public T data;public DoubleNode prev,next;public DoubleNode(T data, DoubleNode prev, DoubleNode next)this.data = data;this.prev = prev;this.next = next;public DoubleNode(T data)this(data, null, null);public DoubleNode()this(null, null, null);public String toString()return this.data.toString();（2）LList接口public interface LList boolean isEmpty();int size();T get(int i);void set(int i,T x);String toString();T remove(int i);void clear();int search(T key);boolean contains(T key);T insertDifferent(T x);T remove(T key);boolean equals(Object obj);（3）DoublyLinkedList類public class DoublyLinkedList implements LListDoubleNode head;Overridepublic boolean isEmpty() / TODO Auto-generated method stubreturn this.head.next=null;Overridepublic int size() / TODO Auto-generated method stubDoubleNode temp = this.head.next;int count = 0;while(temp!=null)count+;temp = temp.next;return count;Overridepublic T get(int i) / TODO Auto-generated method stubDoubleNode temp = this.head;int count = 0;while(true)count+=1;temp = temp.next;if(count=i)return temp.data;Overridepublic void set(int i, T x) / TODO Auto-generated method stubDoubleNode temp = this.head;int count = 0;while(true)count+=1;temp = temp.next;if(count=i)temp.data = x;Overridepublic T remove(int i) / TODO Auto-generated method stubint 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+;Overridepublic void clear() / TODO Auto-generated method stubthis.head.next = null;Overridepublic int search(Object key) / TODO Auto-generated method stubint i=0;DoubleNode temp = this.head.next;for(; temp.next!=null; temp=temp.next)i+=1;if(temp.data.equals(key)break;return i;Overridepublic boolean contains(Object key) / TODO Auto-generated method stubDoubleNode temp = this.head.next;for(; temp.next!=null; temp=temp.next)if(temp.data.equals(key)return true;return false;Overridepublic T insertDifferent(T x) / TODO Auto-generated method stubDoubleNode p=this.head; while (p!=null & !p.data.equals(x) p = p.next; if (p!=null) System.out.println(x=+x+，元素重復(fù)，未插入。); return (T)p; return (T)(p.next = new DoubleNode(x, p, null);5，根據(jù)循環(huán)雙鏈表表的成員方法聲明。SortedCirDoublyList類public class SortedCirDoublyList public DoubleNode head;public SortedCirDoublyList()this.head = new DoubleNode();this.head.prev = this.head;this.head.next = this.head;public SortedCirDoublyList(T values)this(); DoubleNode rear = this.head; for (int i=0; ivalues.length; i+) rear.next = new DoubleNode(valuesi, rear, this.head); rear = rear.next; this.head.prev = rear;public SortedCirDoublyList(CirDoublyList list) this(); DoubleNode rear = this.head; for (DoubleNode p=list.head.next; p!=list.head; p=p.next) rear.next = new DoubleNode(p.data, rear, this.head); rear = rear.next; this.head.prev = rear; 6，實現(xiàn)循環(huán)雙鏈表類，接著再查看LList接口中的方法并實現(xiàn)。（1）List接口類public interface LList boolean isEmpty();int size();T get(int i);void set(int i,T x);String toString();T remove(int i);void clear();int search(T key);boolean contains(T key);T insertDifferent(T x);T remove(T key);boolean equals(Object obj);（2）雙結(jié)點類package Lab2;public class DoubleNode public T data;public DoubleNode prev,next;public DoubleNode(T data, DoubleNode prev, DoubleNode next)this.data = data;this.prev = prev;this.next = next;public DoubleNode(T data)this(data, null, null);public DoubleNode()this(null, null, null);public String toString()return this.data.toString();（3）CHDoublelyLinkedList類package Lab2;public class CHDoublelyLinkedList implements LList DoubleNode head;Overridepublic boolean isEmpty() / TODO Auto-generated method stubreturn this.head.next=null;Overridepublic int size() / TODO Auto-generated method stubDoubleNode temp = this.head.next;int count = 0;while(temp!=head)count+;temp = temp.next;return count;Overridepublic E get(int i) / TODO Auto-generated method stubDoubleNode temp = this.head;int count = 0;while(true)count+=1;temp = temp.next;if(count=i)return temp.data;Overridepublic void set(int i, E x) / TODO Auto-generated method stubDoubleNode temp = this.head;int count = 0;while(true)count+=1;temp = temp.next;if(count=i)temp.data = x;Overridepublic E remove(int i) / TODO Auto-generated method stubint 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 (E) p;count+;Overridepublic void clear() / TODO Auto-generated method stubthis.head.next = null;this.head.prev = null;Overridepublic int search(Object key) / TODO Auto-generated method stubint i=0;DoubleNode temp = this.head.next;for(; temp.next!=head; temp=temp.next)i+=1;if(temp.data.equals(key)break;return i;Overridepublic boolean contains(Object key) / TODO Auto-generated method stubDoubleNode temp = this.head.next;for(; temp.next!=head; temp=temp.next)if(temp.data.equals(key)return true;return false;Overridepublic E insertDifferent(E x) / TODO Auto-generated method stubDoubleNode p=this.head; while (p!=head & !p.data.equals(