华南农业大学数据结构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 int[MAX_SIZE]; private int length = 0;

public SortedSeqList(int[] array) { }

public void clear() { }

public boolean isEmpty() {

return length == 0; length = 0;

if (array == null || array.length == 0) { }

this.length = 0; ary = array;

length = array.length; } else {

.. .. ..

.. ..

}

public void delete(int index) throws Exception { }

public int insert(int value) throws Exception { }

public void display() { }

System.out.println(\); for (int i = 0; i < ary.length; i++) { }

System.out.print(ary[i] + \); if (length == MAX_SIZE) { }

int[] newAry = new int[length + 1]; int i = 0, j = 0;

for (; i < ary.length; i++, j++) { }

while (i < ary.length) { }

ary = newAry; length++; return value;

newAry[++j] = ary[i]; i++;

if (ary[i] >= value) { }

newAry[j] = value; break;

newAry[j] = ary[i];

throw new Exception(\); if (length == 0) { }

int newAry[] = new int[ary.length - 1]; for (int i = 0, j = 0; i < ary.length; i++) { }

ary = newAry; length--;

if (i == index) { }

continue;

newAry[j++] = ary[i]; } else {

throw new Exception(\);

} else {

.. .. ..

.. ..

}

（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)//若查找到指定，则返回结点，否则返回null public boolean contain (E element)//以查找结果判断单链表是否包含指定对象 public boolean remove (E element)//移去首次出现的指定对象

public boolean replace (Object obj, E element)//将单链表中的obj对象替换为对象element

public boolean equals(Object obj)//比较两条单链表是否相等

（1）实现代码：

package Q2;

public class Node { }

package Q2;

.. .. ..

public T data; public Node next;

public Node(T data,Node next){ }

public Node(){ }

this(null,null); this.data=data; this.next=next;

.. ..

public class SinglyLinkedList{

Node head;

public SinglyLinkedList(E[] element){//由指定数组中的多个对象构造单链表 }

public SinglyLinkedList(SinglyLinkedList list){//以单链表list构造新的单链表，复 }

public void concat(SinglyLinkedList list){//将指定单链表list在当前单链表之后 }

public Node search(E element){//若查找到指定，则返回结点，否则返回null

Node p=this.head; Node temp=null; Node rear = null; Node p = head;

Node q=list.head.next ; if(p.data==null) }

if(q==null){ }

rear.next=q;

q=q.next ; p=p.next ; rear=p; p=p.next ; while(p!=null){ head=new Node(); Node list_new = head; Node p=list.head; if(p.data==null){ }

while(p!=null){ }

list_new.next =new Node(p.data,null); list_new=list_new.next; p=p.next ; p=p.next;

list_new=list_new.next; head = new Node();

for(int i=0;i

List.next=new Node(element[i],null); List=List.next ;

Node List = head;

制单链表

.. .. ..

.. ..

}

if(p==null) }

return temp;

p=p.next ;

if(p.data==element){ }

p=p.next ;

temp=p;

while(p.next!=null){

public boolean contain (E element){//以查找结果判断单链表是否包含指定对象 }

public boolean remove (E element){//移去首次出现的指定对象 }

Node p=this.head; Node temp=null; Node front=head; boolean flag=false; if(p==null) }

front=p.next ; return flag;

p=p.next ;

if(p.data==element){ }

p=p.next ;

front=front.next ;

temp=p; flag=true; break;

while(p!=null && temp==null){ boolean flag=false; Node p=this.head; Node temp=null; if(p==null) }

return flag;

p=p.next ;

if(p.data==element){ }

p=p.next ;

flag=true;

while(p!=null){

.. .. ..