数据结构上机作业——顺序表.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〈String〉 list=new SeqList〈String>（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<Integer> list=new SeqList<Integer>（7）；
Scanner scanner=new Scanner(System.in)；
System.out.println（"请输入线性表长度”）;
int n=scanner。nextInt（)；
System.out.println（”请依次输入各元素")；
int e;
for(int i=0;i〈n；i++）{
e=scanner.nextInt（）；
list。add（new Integer（e）);
}
System.out.println(list.toString（））；
｝
｝
修改main方法，完成相应测试。

7）运行：执行Run->Run 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)，删除5
3）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替换为30
3、（选做）设计一个有序顺序表（元素已排序，递增或递减），实现插入、删除等操作,元素插入位置由其值决定.
要求：测试数据使用一组随机数
提示：对象比较大小方法见例1。4;可继承SeqList类
三、要求
1、 上机前请先理清程序思路，复杂程序的主要算法应事先写出。
2、 源程序请自己保存，以备抽查。
3、 上机后一周内交上机报告，包括源程序、测试数据、运行结果和上机调试心得.

答案：
1.方法1：
package dataStructure。linearList;
import java.util。Scanner；

class SeqList〈T〉 {
private Object[]element；
private int len;
public SeqList（int size)｛
this。element=new Object[size];
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〈this。len)
return(T)this。element［i]；
return null;
｝
public void set(int i,T x){
if（x==null）
return；
if（i>=0＆＆i〈this。len）
this。element［i]=x;
else
throw new IndexOutOfBoundsException（i+"”)；
｝
public String toString（)｛
String str="（";
if(this.len〉0）
str+=this。element[0].toString(）;
for(int i=1；i<this。len;i++）
str+=",”+this。element［i］。toString(）；
return str+”）”;
}
public void insert(int i,T x）{
if(x==null)
return；
if（this。len==element.length)｛
Object［］temp=this.element;
this。element=new Object[temp。length＊2]；
for（int j=0；j〈temp。length；j++)
this。element[j］=temp［j］；
}
if（i〈0)
i=0;
if(i〉this。len)
i=this.len；
for(int j=this.len-1；j>=i;j-—）
this.element［j+1］=this。element［j];
this.element［i]=x；
this.len++;
}
public void append（T x）｛
insert(this.len,x）;
}
public T remove（int i)｛
if(this。len==0｜｜i<0|｜i>=this.len）
return null;
T old=(T）this。element[i］;
for(int j=i;j<this.len—1；j++）
this.element［j]=this.element[j+1];
this。element[this.len—1]=null;
this.len——；
return old;
｝
public void removeAll（)｛
this。len=0；
｝
public static void main(String args[]）{
SeqList<String> list=new SeqList<String>（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 <Default> — 〈Default〉--—---—---——-——---——
（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〈T〉 ｛
private Object［]element;
private int len;
public SeqListTest(int size){
this。element=new Object[size］；
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〈this.len）
return（T)this.element［i］；
return null；
}
public void set（int i，T x）{
if（x==null）
return；
if（i〉=0＆＆i〈this。len)
this.element[i]=x;
else
throw new IndexOutOfBoundsException（i+””)；
}
public String toString(）{
String str=”（”；
if（this。len>0)
str+=this。element［0]。toString(）;
for(int i=1;i〈this。len;i++)
str+=”,"+this。element[i］.toString（)；
return str+"）";
｝
public void insert(int i,T x)｛
if（x==null)
return;
if（this.len==element.length)｛
Object[]temp=this.element;
this.element=new Object［temp.length*2];
for(int j=0；j<temp.length；j++)
this。element［j]=temp［j］；
｝
if（i<0）
i=0;
if（i>this。len）
i=this。len;
for(int j=this。len—1；j>=i；j—-)
this.element［j+1]=this.element［j];
this。element[i］=x；
this。len++;
｝
public void append(T x）｛
insert(this。len,x);
｝

public static void main（String args[］){
SeqList<Integer〉 list=new SeqList〈Integer〉(7);
Scanner scanner=new Scanner（System.in);
System.out。println（"请输入线性表长度”)；
int n=scanner。nextInt（）；
System。out。println(”请依次输入各元素")；
int e；
for（int i=0;i〈n;i++)｛
e=scanner.nextInt();
list.append(new Integer(e)）;
｝
System.out。println（list.toString（))；
｝
｝

运行结果：
—-—-———---——-—--——-—Configuration： ds - JDK version 1。6.0_31 〈Default> — 〈Default〉-————-—--—-—-—--——-—
请输入线性表长度
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.element［j+1］=this。element[j]；
this。element[i]=x;
this。len++；

错误3：

错误分析：
在调用insert方法时只填写了一个参数
而insert方法是(int i，T x）,所以此时应调用append方法

2.
（1）将指定顺序表list链接在当前顺序表之后
package dataStructure。linearList;
import java.util。Scanner;

class SeqListTest〈T〉 ｛
private Object［]element；
private int len；
public SeqListTest(int size)｛
this.element=new Object［size];
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<this。len)
return(T）this。element[i］；
return null;
}
public void set（int i,T x){
if(x==null）
return；
if（i>=0&＆i<this.len）
this.element［i］=x;
else
throw new IndexOutOfBoundsException(i+"”)；
｝
public String toString(）{
String str="（”;
if（this。len〉0）
str+=this.element［0］.toString(）；
for（int i=1;i<this.len；i++)
str+=","+this.element[i].toString();
return str+”)"；
｝
public void insert(int i,T x){
if(x==null)
return；
if（this。len==element.length）{
Object[]temp=this。element;
this。element=new Object[temp。length＊2]；
for（int j=0;j〈temp.length;j++)
this.element[j]=temp[j］；
}
if（i〈0）
i=0;
if(i〉this。len)
i=this.len;
for(int j=this。len-1;j〉=i；j——）
this。element［j+1］=this。element[j］；
this.element[i]=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；i<list。length();i++){
list1.insert(i+n，list。get(i）);
｝
System.out。print(list1。toString(））；
｝
public static void main(String args［]){
SeqList<String> list=new SeqList〈String〉(7)；
SeqList<Integer〉 list1=new SeqList<Integer〉（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 〈Default〉 — <Default>---—-——-—-—-—-—-———-
（1,2，3，4,5，7,8,9)
Process completed.

错误:
无法将 dataStructure。linearList.SeqListTest〈T〉 中的 insert（int,T) 应用于 (int，java.lang.Object)
            this.insert(i+5,list。get(i))；
错误分析：
应将SeqList〈String〉 list=new SeqList〈String>（7）；改为 SeqList〈Integer> list1=new SeqList〈Integer>(7)；
                ^

（2)移去首次出现的指定对象
package dataStructure.linearList；
import java。util.Scanner;

class SeqList<T〉 {
private Object［]element;
private int len;
public SeqList（int size)｛
this。element=new Object［size];
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〈this。len)
return（T)this。element[i］；
return null;
}
public void set(int i,T x）{
if（x==null）
return；
if（i〉=0&＆i<this.len)
this.element［i］=x;
else
throw new IndexOutOfBoundsException(i+""）;
｝
public String toString（）｛
String str=”（”；
if（this。len〉0）
str+=this.element［0］.toString()；
for(int i=1；i<this.len;i++)
str+="，"+this。element[i］。toString(）；
return str+”)”；
}
public void insert(int i，T x）｛
if（x==null）
return;
if(this.len==element。length){
Object［]temp=this。element;
this。element=new Object[temp.length＊2]；
for（int j=0；j<temp.length；j++）
this.element［j]=temp［j];
}
if(i<0）
i=0；
if(i>this.len）
i=this.len；
for(int j=this.len-1；j>=i;j--)
this。element［j+1]=this.element［j］；
this.element[i]=x;
this.len++；
｝
public void append(T x){
insert（this.len，x)；
}
public T Remove（int i){
if（this。len==0||i<0||i>=this。len）
return null;
T old=（T）this.element［i］;
for(int j=i；j〈this。len-1；j++）
this.element[j]=this.element［j+1］;
this。element［this.len—1]=null；
this。len--;
return old;
}
public boolean remove(T x){
int i=0;
while（element［i]!=x&&i<len）{
i++；
}
if（element[i]==x＆&i<len）{
this.Remove（i）;
return true;

}
return false;

}
public void removeAll（int n）｛
this.len=0;
｝
public static void main(String args[］){
SeqList<String> list=new SeqList<String>(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 <Default> - 〈Default〉---——----—-————--———
（1，2，3，4，5，5)
删除后：
（1,2,3,4,5）
Process completed.

错误：
——-——-—-——-—-——-——-—Configuration： da — JDK version 1。6。0_13 〈Default〉 — 〈Default〉-—---—--—------—----
（1,2,3，4,5)
删除后：
（1,2，4，4，5）
Process completed.

错误分析：
删除3后，应该将后面的元素前移。

（3） 将元素值为obj的结点值替换为element，若替换成功返回true，否则返回false

package dataStructure。linearList；
import java.util。Scanner;

class SeqList<T> {
private Object［]element；
private int len；
public SeqList（int size）{
this。element=new Object［size];
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〈this。len）
return（T）this.element[i］；
return null；
｝
public void set(int i，T x)｛
if（x==null）
return；
if(i〉=0＆&i<this。len）
this。element［i］=x；
else
throw new IndexOutOfBoundsException（i+"")；
}
public String toString(）{
String str="(";
if(this.len>0)
str+=this。element[0］。toString();
for（int i=1;i<this。len;i++)
str+=”，”+this。element[i]。toString(）；
return str+")”;
｝
public void insert(int i，T x）{
if(x==null)
return；
if(this。len==element。length）｛
Object［]temp=this.element；
this。element=new Object［temp。length*2］;
for(int j=0；j〈temp。length;j++）
this.element［j］=temp[j];
}
if（i<0)
i=0；
if（i>this.len)
i=this.len;
for(int j=this.len-1;j>=i；j——）
this。element[j+1］=this。element[j]；
this。element［i]=x;
this。len++;
｝
public void append（T x)｛
insert（this。len，x）；
}
public T remove(int i）｛
if（this.len==0｜｜i<0||i>=this。len）
return null；
T old=（T）this.element[i］;
for(int j=i;j〈this.len-1;j++)
this。element［j]=this.element[j+1];
this.element［this。len-1］=null;
this.len-—;
return old;
}
public void removeAll（){
this。len=0;
｝
public boolean replace(Object obj， T x)｛
for（int i=0;i<len；i++）{
if(element[i]==obj）{
element[i］=x；
}
//if（element==x）
// return true；
}
return element==x；

｝
public static void main(String args［]）｛
SeqList〈Integer> list=new SeqList〈Integer〉（7);
list。append（1);
list.append(2）；
list。append（3);
list。append(4）；
list.append（5）;
System。out。println(list.toString（))；
System。out。println(list.replace（3，30）)；
System。out。print（list。toString（）);
｝

}