《数据结构Java版》线性表之顺序表的建立及操作

《数据结构Java版》线性表之顺序表的建立及操作 package sjjg2; 1、LList.java接口

public interface LList {

// 线性表接口，泛型参数T表示数据元素的数据类型 boolean isEmpty(); // 判断线性表是否空 int length(); // 返回线性表长度

T get(int i); // 返回第i（i≥0）个元素

void set(int i, T x); // 设置第i个元素值为x int insert(int i, T x); // 插入x作为第i个元素 int append(T x); // 在线性表最后插入x元素

T remove(int i); // 删除第i个元素并返回被删除对象 void removeAll(); // 删除线性表所有元素

int search(T key); // 查找，返回首次出现的关键字为key的元素的位序 }

2、SeqList.Java

public class SeqList implements LList {

protected Object[] element; protected int n;

public SeqList(int length) //构造容量为length的空表 {

this.element = new Object[length]; //申请数组的存储空间,元素为null.//若length<0，Java抛出负数组长度异常 java.lang.NegativeArraySizeException this.n = 0; }

public SeqList() //创建默认容量的空表，构造方法重载 {

this(64); //调用本类已声明的指定参数列表的构造方法 }

public SeqList(T[] values) //构造顺序表，由values数组提供元素，忽略其中空对象 {

this(values.length*2); //创建2倍values数组容量的空表 //若values==null，用空对象调用方法，Java抛出空对象异常NullPointerException

for (int i=0; i

this.element[this.n++] = values[i]; //对象引用赋值 }

public boolean isEmpty() //判断线性表是否空 {

return this.n==0; }

public int length(){ //返回线性表长度 return this.n; }

public T get(int i){ //返回第i（i≥0）个元素 if (i>=0 && i

1

//编译错，Object对象不能返回T对象 return null; }

public void set(int i, T x){ //设置第i个元素值为x if (x==null) throw new NullPointerException(\); //抛出空对象异常 if (i>=0 && i

this.element[i] = x;

else throw new java.lang.IndexOutOfBoundsException(i+\);//抛出序号越界异常 }

public int insert(int i, T x){ //插入x作为第i个元素

if (x==null)

throw new NullPointerException(\); //抛出空对象异常 if (i<0) i=0; //插入位置i容错，插入在最前 if (i>this.n) i=this.n; //插入在最后

Object[] source = this.element; //数组变量引用赋值，source也引用element数组 if (this.n==element.length) //若数组满，则扩充顺序表的数组容量 {

this.element = new Object[source.length*2]; //重新申请一个容量更大的数组 for (int j=0; j

for (int j=this.n-1; j>=i; j--) //从i开始至表尾的元素向后移动，次序从后向前 this.element[j+1] = source[j]; this.element[i] = x; this.n++;

return i; //返回x序号 }

public int append(T x){ //在线性表最后插入x元素

return this.insert(this.n, x); }

public T remove(int i){

//删除第i个元素并返回被删除对象 if (this.n>0 && i>=0 && i

T old = (T)this.element[i]; //old中存储被删除元素 for (int j=i; j

this.element[j] = this.element[j+1]; //元素前移一个位置

this.element[this.n-1]=null; //设置数组元素对象为空，释放原引用实例 this.n--;

return old; //返回old局部变量引用的对象，传递对象引用 }

return null; }

public void removeAll(){

//删除线性表所有元素 this.n=0; }

public int search(T key){//查找，返回首次出现的关键字为key的元素的位

System.out.print(this.getClass().getName()+\+key+\，\); for (int i=0; i

2

if (key.equals(this.element[i]))//执行T类的equals(Object)方法，运行时多态 return i; }

return -1; }

public String toString(){

String str=this.getClass().getName()+\; //返回类名 if (this.n>0)

str += this.element[0].toString(); //执行T类的toString()方法，运行时多态 for (int i=1; i

str += \+this.element[i].toString(); //执行T类的toString()方法，运行时多态 return str+\; }

public static void main (String args[]) {

SeqList list=new SeqList(20); Integer values[]={10,1,2,3,4,5,6,7,8,9};

SeqList list1=new SeqList(values); System.out.print(\输出顺序表:\);

System.out.println(list1.toString());

System.out.println(\顺序表List是否为空\+list.isEmpty()+\是否为空\+list1.isEmpty());

System.out.println(\的长度\+list.length()+\的长度\+list1.length()); System.out.println(\返回list1的第7个元素是:\+list1.get(6));

System.out.println(\重新设置第5个元素为19:\); list1.set(4, 19);

list1.insert(2, 100); list1.append(20);

System.out.println(\删除8:\+list1.remove(8)); System.out.print(\修改后的顺序表:\); System.out.println(list1.toString()); list1.removeAll();

System.out.println(\删除后的顺序表：\+list1.toString());//为空 System.out.println(\寻找元素50:\+list1.search(50)); } }

3