数据结构上机作业——顺序表.doc

数据结构上机作业顺序表一、实验目的理解线性表的逻辑结构、顺序存储结构和数据操作，熟练运用Java语言实现线性表的基本操作，分析各种操作算法特点和时间复杂度。熟悉JCreator调试程序的方法。二、主要内容1、按照教材P37编写顺序表类，在SeqList中增加main方法或者编写一个测试类测试各方法的正确性。说明：注意package路径，导入LList，过程参考如下：1）创建工程：File-New-Project，选择Empty Project，输入工程名称及路径，点击完成。2）鼠标指向工程ds，单击鼠标右键，在快捷菜单中选择Add-New Folder，新建文件夹dataStructure，在dataStructure新建文件夹linearList。3）鼠标指向文件夹linearList，单击鼠标右键，在快捷菜单中选择Add Existing Files，选择LList.java（教育在线例程中）。4）鼠标指向文件夹linearList，单击鼠标右键，在快捷菜单中选择New Class，在Class Wizard中输入相关内容，类名：SeqList。5）程序编辑结束后，执行Build-Build File菜单命令，编译Java程序，系统在Build Output区域输出错误信息，编译通过后将生成字节码文件（.class）。6）测试：方法1 在SeqList类中增加main方法，例如public static void main(String args)SeqList list=new SeqList(7);list.add(091202);list.add(091203);list.add(091205);list.add(091206);System.out.println(list.toString();list.add(2,091204);System.out.println(list.toString();list.remove(3);System.out.println(list.toString();修改main方法，完成相应测试。方法2 新建一个测试类，在main方法中测试你所编写的各方法。例如import dataStructure.linearList.*;import java.util.Scanner;public class SeqListTest public static void main(String args)SeqList list=new SeqList(7);Scanner scanner=new Scanner(System.in);System.out.println(请输入线性表长度);int n=scanner.nextInt();System.out.println(请依次输入各元素);int e;for(int i=0;iRun File，若没有错误，系统将运行结果显示在General Output区域。8）调试2、在SeqList类中增加下列成员方法。1）public void concat(SeqList list)说明：将指定顺序表list链接在当前顺序表之后测试数据：第一组：(1，2，3，4，5)，()第二组：()，(1，2，3，4，5)第三组：(1，2，3，4，5)，(6，7，8)2）public boolean remove(T element)说明：移去首次出现的指定对象测试数据：第一组：(1，2，3，4，5)，删除6第二组： (1，2，3，4，5)，删除1第三组： (1，2，3，4，5，5)，删除53）public boolean replace(Object obj, T element)说明：将元素值为obj的结点值替换为element，若替换成功返回true，否则返回false测试数据：第一组：(1，2，3，4，5)，将6替换为4第二组： (1，2，3，4，5)，将3替换为30第三组： (1，2，3，4，5，5)，将5替换为303、（选做）设计一个有序顺序表（元素已排序，递增或递减），实现插入、删除等操作，元素插入位置由其值决定。要求：测试数据使用一组随机数提示：对象比较大小方法见例1.4；可继承SeqList类三、要求1、 上机前请先理清程序思路，复杂程序的主要算法应事先写出。2、 源程序请自己保存，以备抽查。3、 上机后一周内交上机报告，包括源程序、测试数据、运行结果和上机调试心得。答案：1.方法1：package dataStructure.linearList;import java.util.Scanner;class SeqList private Objectelement;private int len;public SeqList(int size)this.element=new Objectsize;this.len=0;public SeqList()this(64);public boolean isEmpty()return this.len=0;public int length()return this.len;public T get(int i)if(i=0&i=0&i0) str+=this.element0.toString();for(int i=1;ithis.len;i+) str+=,+this.elementi.toString();return str+);public void insert(int i,T x)if(x=null) return;if(this.len=element.length)Objecttemp=this.element;this.element=new Objecttemp.length*2;for(int j=0;jtemp.length;j+) this.elementj=tempj;if(ithis.len) i=this.len;for(int j=this.len-1;j=i;j-) this.elementj+1=this.elementj;this.elementi=x;this.len+;public void append(T x)insert(this.len,x);public T remove(int i)if(this.len=0|i=this.len) return null;T old=(T)this.elementi; for(int j=i;jthis.len-1;j+) this.elementj=this.elementj+1; this.elementthis.len-1=null; this.len-; return old; public void removeAll() this.len=0; public static void main(String args)SeqList list=new SeqList(7);list.append(091202);list.append(091203);list.append(091205);list.append(091206);System.out.println(list.toString();list.insert(2,091204);System.out.println(list.toString();list.remove(3);System.out.println(list.toString();运行结果：-Configuration: ds - JDK version 1.6.0_31 - -(091202,091203,091205,091206)(091202,091203,091204,091205,091206)(091202,091203,091204,091206)Process completed.方法2：package dataStructure.linearList;import java.util.Scanner;class SeqListTest private Objectelement;private int len;public SeqListTest(int size)this.element=new Objectsize;this.len=0;public SeqListTest()this(64);public boolean isEmpty()return this.len=0;public int length()return this.len;public T get(int i)if(i=0&i=0&i0) str+=this.element0.toString();for(int i=1;ithis.len;i+) str+=,+this.elementi.toString();return str+);public void insert(int i,T x)if(x=null) return;if(this.len=element.length)Objecttemp=this.element;this.element=new Objecttemp.length*2;for(int j=0;jtemp.length;j+) this.elementj=tempj;if(ithis.len) i=this.len;for(int j=this.len-1;j=i;j-) this.elementj+1=this.elementj;this.elementi=x;this.len+;public void append(T x)insert(this.len,x);public static void main(String args)SeqList list=new SeqList(7);Scanner scanner=new Scanner(System.in);System.out.println(请输入线性表长度);int n=scanner.nextInt();System.out.println(请依次输入各元素);int e;for(int i=0;in;i+)e=scanner.nextInt();list.append(new Integer(e);System.out.println(list.toString();运行结果：-Configuration: ds - JDK version 1.6.0_31 - -请输入线性表长度5请依次输入各元素1 3 5 2 4(1,3,5,2,4)Process completed.错误1：错误分析：没有声明T，所以找不到符号错误2：错误分析：数组下标越界54行处代码应为for(int j=this.len-1;j=i;j-) this.elementj+1=this.elementj;this.elementi=x;this.len+;错误3：错误分析：在调用insert方法时只填写了一个参数而insert方法是(int i,T x),所以此时应调用append方法 2.(1)将指定顺序表list链接在当前顺序表之后package dataStructure.linearList;import java.util.Scanner;class SeqListTest private Objectelement;private int len;public SeqListTest(int size)this.element=new Objectsize;this.len=0; public SeqListTest()this(64);public boolean isEmpty()return this.len=0;public int length()return this.len;public T get(int i)if(i=0&i=0&i0) str+=this.element0.toString();for(int i=1;ithis.len;i+) str+=,+this.elementi.toString();return str+);public void insert(int i,T x)if(x=null) return;if(this.len=element.length)Objecttemp=this.element;this.element=new Objecttemp.length*2;for(int j=0;jtemp.length;j+) this.elementj=tempj;if(ithis.len) i=this.len;for(int j=this.len-1;j=i;j-) this.elementj+1=this.elementj;this.elementi=x;this.len+;public void append(T x)insert(this.len,x); public static void concat(SeqList list,SeqList list1) int n=list1.length();for(int i=0;ilist.length();i+)list1.insert(i+n,list.get(i);System.out.print(list1.toString();public static void main(String args)SeqList list=new SeqList(7);SeqList list1=new SeqList(7);Scanner scanner=new Scanner(System.in);list.append(1);list.append(2);list.append(3);list.append(4); list.append(5);list1.append(7);list1.append(8);list1.append(9); concat(list1,list);运行结果：-Configuration: da - JDK version 1.6.0_13 - -(1,2,3,4,5,7,8,9)Process completed.错误：无法将 dataStructure.linearList.SeqListTest 中的 insert(int,T) 应用于 (int,java.lang.Object) this.insert(i+5,list.get(i);错误分析:应将SeqList list=new SeqList(7);改为SeqList list1=new SeqList(7); （2）移去首次出现的指定对象package dataStructure.linearList;import java.util.Scanner;class SeqList private Objectelement;private int len;public SeqList(int size)this.element=new Objectsize;this.len=0;public SeqList()this(64);public boolean isEmpty()return this.len=0;public int length()return this.len;public T get(int i)if(i=0&i=0&i0) str+=this.element0.toString();for(int i=1;ithis.len;i+) str+=,+this.elementi.toString();return str+);public void insert(int i,T x)if(x=null) return;if(this.len=element.length)Objecttemp=this.element;this.element=new Objecttemp.length*2;for(int j=0;jtemp.length;j+) this.elementj=tempj;if(ithis.len) i=this.len;for(int j=this.len-1;j=i;j-) this.elementj+1=this.elementj;this.elementi=x;this.len+;public void append(T x)insert(this.len,x);public T Remove(int i)if(this.len=0|i=this.len) return null;T old=(T)this.elementi; for(int j=i;jthis.len-1;j+) this.elementj=this.elementj+1; this.elementthis.len-1=null; this.len-; return old; public boolean remove(T x) int i=0; while(elementi!=x&ilen) i+; if(elementi=x&ilen) this.Remove(i); return true; return false; public void removeAll(int n) this.len=0; public static void main(String args)SeqList list=new SeqList(7);list.append(1);list.append(2);list.append(3);list.append(4);list.append(5);list.append(5);System.out.println(list.toString();list.remove(5);System.out.println(删除后：);System.out.print(list.toString();运行结果：-Configuration: da - JDK version 1.6.0_13 - -(1,2,3,4,5,5)删除后：(1,2,3,4,5)Process completed.错误：-Configuration: da - JDK version 1.6.0_13 - -(1,2,3,4,5)删除后：(1,2,4,4,5)Process completed.错误分析：删除3后，应该将后面的元素前移。（3） 将元素值为obj的结点值替换为element，若替换成功返回true，否则返回falsepackage dataStructure.linearList;import java.util.Scanner;class SeqList private Objectelement;private int len;public SeqList(int size)this.element=new Objectsize;this.len=0;public SeqList()this(64);public boolean isEmpty()return this.len=0;public int length()return this.len;public T get(int i)if(i=0&i=0&i0) str+=this.element0.toString();for(int i=1;ithis.len;i+) str+=,+this.elementi.toString();return str+);public void insert(int i,T x)if(x=