顺序表(java版).doc

第 5 页 共 5 页
//线性表的抽象数据类型定义
public interface ListIntf{
public int size(); //返回表长度
public void clear(); //重置为空表
public boolean isEmpty(); //若为空表返回true,否则返回false
public Object get(int i); //返回第i个数据元素(返回类型可不同)
public int indexOf(Object obj); //第1个与obj满足关系equals()的数据元素位序,这样的数据元素不存在,则返回值为-1(obj的数据类型根据实际不同)
public Object getPre(Object obj); //若obj是表中的元素,返回它的前驱
public Object getNext(Object obj); //若obj是表中的元素,返回它的后继
public void insertElementAt(Object obj,int i);
//在第i个位置之前插入新的数据元素obj,表长度加1
public Object remove(int i); //删除第i个数据元素,并返回其值,表长减1
public Object remove(Object obj); //删除数据元素obj,并返回其值,表长减1
}

public class SqList implements ListIntf {
public static final int MAXSIZE=100; //线性表最大长度
Object []elem=new Object[MAXSIZE]; //存放线性表元素的数组
private int len=0; //线性表的长度,初值为0
//取得表最大长度
public int getMAXSIZE(){
return MAXSIZE;
}
/**
* 实现接口方法
*/
//@Override重置表为空表
public void clear() {
len=0; //设置表长为0
}

//@Override返回第i个数据元素的值(返回类型可不同)
public Object get(int i) {
if(len==0)
return null; //表空,查找失败
if(i<1||i>len)
return null; //查找位置不合法,查找失败
return elem[i-1]; //查找成功
}

//@Override若obj是表中的元素,返回它的后继
public Object getNext(Object obj) {
int i=indexOf(obj);
if(i==-1)
return null; //指定元素不存在
else if(i==len)
return null; //指定元素位于最后一位,不存在后继元素
return elem[i]; //查找后继成功,返回后继
}

//@Override若obj是表中的元素,返回它的前驱
public Object getPre(Object obj) {
int i=indexOf(obj);
if(i==-1)
return null; //指定元素不存在
else if(i==1)
return null; //指定元素位于第一位,不存在前驱元素
return elem[i-2]; //查找前驱成功,返回前驱
}

//@Override第1个与obj满足关系equals()的数据元素的位序,若这样的数据元素不存在,则返回值为-1(obj的类型根据实际不同)
public int indexOf(Object obj) {
for(int i=0;i<len;i++){
if(elem[i].equals(obj))
return i+1; //查找成功,返回位序
}
return -1; //查找失败
}

//@Override在第i个位置之前插入新的数据元素obj,表长度加1
public void insertElementAt(Object obj, int i) {
if(len==MAXSIZE){ //判断线性表的存储空间是否已满
System.out.println("--溢出--");
return;
}
else if(i<1||i>len+1){
System.out.println("--插入位置非法--");
return; //插入位置非法
}
for(int j=len-1;j>=i-1;j--)
elem[j+1]=elem[j];
elem[i-1]=obj; //插入元素
len++; //表长加1
return;
}

//@Override若为空表,则返回true,否则返回false
public boolean isEmpty() {
if(len==0)
return true; //表空,返回true
return false; //表非空,返回false
}

//@Override删除第i个数据元素,并返回其值,表长度减1
public Object remove(int i) {
Object obj;
if(i<1||i>len){
System.out.println("--删除位置非法--");
return null;
}
obj=elem[i-1]; //被删除的值
for(int j=i-1;j<len-1;j++){
elem[j]=elem[j+1];
}
len--;
return obj; //返回被删除的值
}

//@Override删除数据元素obj,并返回其值,表长度减1
public Object remove(Object obj) {
int i=indexOf(obj);
if(i==-1){
System.out.println("--待删除的值不存在--");
return null;
}
return remove(i); //返回删除的值
}

//@Override返回表长度
public int size() {
// TODO Auto-generated method stub
return len;
}

//打印表中元素
public void printList(){
if(len==0){
System.out.println("--表空--");
return;
}
System.out.println(">>表中元素>>");
for(int i=0;i<len;i++)
System.out.println(elem[i].toString());
}

}

import java.util.*;

public class SqListTest {
/**
* @param args
*/
public static void main(String[] args) {
System.out.println("==============================Begin==============================");
System.out.println("----构造顺序表----");
Object obj;
int n;
Scanner input=new Scanner(System.in);
SqList sl=new SqList();
System.out.println("表长:"+sl.size());
//构造5个元素的顺序表
for(int i=0;i<5;i++){
System.out.print("输入元素:");
obj=input.next();
sl.insertElementAt(obj, sl.size()+1);
}
System.out.println("表长:"+sl.size());
sl.printList();
System.out.println("----增加元素----");
System.out.print("元素:");
obj=input.next();
System.out.print("位置:");
n=Integer.parseInt(input.next());
sl.insertElementAt(obj, n);
System.out.println("表长:"+sl.size());
sl.printList();
System.out.println("----查找元素----");
System.out.print("元素:");
obj=input.next();
n=sl.indexOf(obj);
if(n!=-1)
System.out.println("...元素"+obj+"位于第"+n+"位...");
System.out.print("位置:");
n=Integer.parseInt(input.next());
obj=sl.get(n);
if(obj!=null)
System.out.println("...第"+n+"位元素为"+obj+"...");
System.out.println("----删除元素----");
System.out.print("位置:");
n=Integer.parseInt(input.next());
obj=sl.remove(n);
if(obj!=null)
System.out.println("...删除的元素为"+obj+"...");
System.out.println("表长:"+sl.size());
sl.printList();
System.out.print("元素:");
obj=input.next();
Object obj1=sl.remove(obj);
if(obj!=null)
System.out.println("...删除的元素为"+obj1+"...");
System.out.println("表长:"+sl.size());
sl.printList();
System.out.println("===============================End===============================");
}
}

yujmh 第 5 页 2024-12-28