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

精选文库实验报告二 线性表华 南 农 业 大 学 信 息（软 件）学 院数据结构（JAVA）综合性、设计性实验成绩单开设时间：2017学年第二学期班级16信管3班学号2016250403xx姓名黄xx实验题目实验二 线性表的基本操作成绩教师签名一， 实验目的：（1） 理解线性表的逻辑结构、两种存储结构和数据操作，熟练运用JAVA语言实现线性表的基本操作，分析各种操作算法特点和时间复杂度。（2） 掌握单链表的遍历、插入和删除等操作算法，实现多项式相加。二， 实验内容：1、设计一个有序顺序表（元素已排序，递增或递减），实现插入、删除等操作，元素插入位置由其值决定。实现：（1）升序排序顺序表类名为：SortedSeqList，存成SortedSeqList.java文件；（2）另外编写SortedSeqList_ex.java文件来演示调用排序顺序表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文件来演示调用排序顺序表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）实验结果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)/比较两条单链表是否相等（1）实现代码：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();（2）实验结果3，先写出LList接口并写上要实现的方法的方法头，再CircSinglyLinkedList类中继承该接口并实现其方法。（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)结点类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+，元素重复，未插入。); 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接口并写上要实现的方法的方法头，再DoublyLinkedList类中继承该接口并实现其方法。（1）双结点类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+，元素重复，未插入。); return (T)p; return (T)(p.next = new DoubleNode(x, p, null);5，根据循环双链表表的成员方法声明。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，实现循环双链表类，接着再查看LList接口中的方法并实现。（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）双结点类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.eq