顺序表

首先定义一个抽象类,包括两个方面:数据集合和该数据集合上的操作集合。线性表常见操作有插入、删除、查找、获取元素值、设置元素值等,在java语言中,抽象数据类型通常设计成接口。线性表抽象类型的java接口可声明如下: 

//线性表抽象数据类型
public interface LinearList<Student> {
    public Student get(int i);//返回下标为i的元素
    public void set(int i,Student t);//用指定元素t替换列表中指定位置i的元素
    public int insert(Student t);//在线性表的最后插入元素t,返回t序号
    public int insert(int i,Student t);//在线性表的位置i处插入元素t,返回t序号
    public Student remove(int i);//删除下标为i的元素,返回被删除的元素
    public boolean contains(Student key);//判断线性表中是否包含key元素
    public void indexOf(int i); //在线性表查找首次出现的与key相等元素,返回元素位置,若不存在,则返回-1
    public int size();//返回线性表的长度
    public void clear();//清空线性表
    public boolean isEmpty();//判断线性表是否为空
    public void printList(); //遍历顺序表所有元素
}


 顺序表类声明、构造方法、存取操作实现

声明顺序表SeqList,实现线性表接口LinearList,顺序表包含2个保护成员变量data和n。其中,data数组存放顺序表中的数据元素,元素类型用泛型T表示;n为顺序表中的元素个数(顺序表长度)。


//顺序表类
public class SeqList implements LinearList<Student>{
    protected Student[] data;         //对象数组存储顺序表的数据元素
    protected int n;             //顺序表数据元素个数(长度)

    public SeqList(int length){          //构造容量为length的空表
        this.data=new Student[length];//创建长度为length的数组,元素均为null
        this.n=0;                        //空表长度为0
    }

    public SeqList(Student[] values){    //由values数组构造顺序表
        this(values.length);             //创建容量为values.length的空表
        for(int i=0;i<values.length;i++){//复制数组元素
            this.data[i]=values[i];   //对象引用赋值
        }
        this.n=values.length;            //顺序表长度
    }

    public SeqList(){                    //创建默认容量的空表
        this(10);                        //构造方法重载,调用本类已声明的指定参数列表的构造方法
    }


    @Override
    public Student get(int i) {          //返回下标为i的元素
        if(i>=0&&i<this.n){
            return this.data[i];
        }else{
            throw new java.lang.IndexOutOfBoundsException(i+"下标越界");//抛出下标越界异常
        }
    }

    @Override
    public void set(int i, Student t) { //用指定元素t替换列表中指定位置i的元素
        for(int j=0;j<this.n;j++){
            if(j==i){
                this.data[j]=t;
            }
        }

    }

    @Override
    public int insert(Student t) {//在顺序表的最后插入元素t,返回t序号
        return this.insert(this.n,t);
    }

    @Override
    public int insert(int i, Student t) { //在顺序表的位置i处插入元素t,返回t序号
        if(t==null)
            throw new NullPointerException("t==null");              //抛出空对象异常
        if(i>=0&&i<=this.n){
            Student src[]=this.data;  //保存原数组
            if(this.n==data.length){  //若数组满,则扩充顺序表的数组容量
                this.data=new Student[src.length*2];            //重新申请一个容量为原来2倍的数组
                for(int j=0;j<i;j++){
                    this.data[j]=src[j];                        //复制当前数组前i个元素
                }
            }
            for(int j=this.n-1;j>=i;j--){ //从最后一个位置开始到位置i处,每一个元素向后移动1位
                this.data[j+1]=src[j];
            }
            this.data[i]=t;            //把要插入的元素t存放在位置i处
            this.n++;
            return i;                    //返回下标
        }else{
            throw new IndexOutOfBoundsException(i+"下标越界");//抛出下标越界异常
        }

    }

    @Override
    public Student remove(int i) {
        if(this.n==0){
            try {
                throw new Exception("空表无法删除!");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        if(i>=0&&i<this.n){
            Student old=this.data[i];  //old中存放被删除元素
            for(int j=i;j<this.n-1;j++){
                this.data[j]=this.data[j+1];                  //从位置i+1开始每个元素依次前移一位
            }
            this.data[this.n-1]=null;  //设置最后一个位置元素为空
            this.n--;
            return old;
        }else{
            throw new IndexOutOfBoundsException(i+"下标越界");//抛出下标越界异常
        }
    }

    @Override
    public boolean contains(Student key) {//判断顺序表中是否包含key元素
        for(int i=0;i<this.n;i++){
            if(key.equals(this.data[i])){
                return true;
            }
        }
        return false;
    }

    @Override
    public int size() {		//返回顺序表的长度
        return this.n;
    }

    @Override
    public void clear() {   //清空顺序表
        this.n=0;
    }

    @Override
    public boolean isEmpty() {	//判断顺序表是否为空
        return this.n==0;
    }

    @Override
    public void printList() { //遍历顺序表所有元素
        for(int i=0;i<this.n;i++){
            System.out.println(this.data[i]);
        }
    }

    @Override
    public void indexOf(int i) { //在顺序表查找首次出现的与key相等元素,返回元素位置,若不存在,则返回null

        for(int j=0;j<this.n;j++){
            if(j==i){
                System.out.println(this.data[j]);
            }
        }

    }
}


定义一个学生类来让上面顺序表类调用

public class Student {
    public String no;
    public String name;
    public double score;
    public Student next;                                        //单链表会用到
    

    public Student() {
        super();
    }

    public Student(String no, String name, double score) {
        super();
        this.no = no;
        this.name = name;
        this.score = score;
    }

    public String getNo() {
        return no;
    }

    public void setNo(String no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getScore() {
        return score;
    }

    public void setScore(double score) {
        this.score = score;
    }

    @Override
    public String toString() {                                                 
        return "Student [no=" + no + ", name=" + name + ", score=" + score
                + "]";
    }
}

都OK了之后就可以开始测试了

再创建一个测试类来测试

public class ceshi2 {
    public static void main(String[] args) {
        SeqList s1=new SeqList(20);                        //创建一个长度为20的线性表
        s1.insert(new Student("1","大娃",100));            //添加元素
        s1.insert(new Student("2","二娃",99));
        s1.insert(new Student("3","三娃",98));
        System.out.println("添加三个学生后结果");
        s1.printList();                                    //遍历所有元素

        System.out.println("表中第二个位置添加第四个学生");
        s1.insert(1,new Student("4","四娃",99.5));          //增
        s1.printList();                                    

        System.out.println("删除第三个学生的信息");
        s1.remove(2);                                      //删
        s1.printList();

        System.out.println("查询第三个学生");
        s1.indexOf(2);                                     //查

        System.out.println("修改第三个学生");
        s1.set(2,new Student("5","五娃",95));              //改
        s1.printList();

    }
}

结果