但行好事  莫问前程

自己实现集合框架(二):顺序表的实现

这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和java集合有个大概的了解。当然实现没有java集合的实现那么复杂,功能也没有那么强大,但是可以通过这些简单的实现窥探到底层的一些共性原理。

在之前的文章自己实现集合框架(一):线性表接口中已经定义了线性表的接口,那么下面具体说下顺序表的实现。

一. 顺序表的存储结构

顺序表通常采用数组存储数据元素,数据元素在数组中的物理顺序与逻辑顺序完全相同。

数组是顺序存储的随机存取结构,它占用一组连续的存储单元,通过下标识别元素,元素地址是下标的线性函数。一个下标能够唯一确定一个元素,所以存取任何一个元素所花费的时间复杂度是O(1)。数组一旦占用一片存储空间,这片存储空间的地址和长度是确定的,不能更改。数组的内存分配有静态和动态两种方式,静态数组和动态数组都是定长的,当数容量不够时,都不能就地扩容。

二. 顺序表类的实现

顺序表类SeqList是线性表顺序存储结构的一种实现,类似于java集合框架里的ArrayList的实现,它有两个私有成员变量tablen,table是一个存放表元素的对象数组;n为线性表长度,n≤table.lengthSeqList声明如下,它实现了线性表接口LList

1. 定义类并实现LList接口,添加构造函数

package org.light4j.dataStructure.linearList.seqList;

import org.light4j.dataStructure.linearList.LList;

public class SeqList<E> implements LList<E> {  //顺序表类,实现线性表接口
    private Object[] table;   // 对象数组,私有成员
    private int n;  //顺序表长度

    /**
     * 指定空表的默认容量
     */ 
    public SeqList(){
        this(16);
    }

    /**
     * 构造方法,创建指定容量的空表
     * Math.abs(i)返回参数的绝对值
     */
    public SeqList(int capacity){
        this.table=new Object[Math.abs(capacity)];
        this.n=0;
    }
}

代码解释:

SeqList类声明为实现线性表接口LList的泛型类,泛型参数E表示线性表元素的数据类型。当声明SeqList类的一个对象并创建实例时,指定泛型参数E为一个确定的类。泛型E的实际参数必须是类,不能是基本数据类型。如果需要表示基本数据类型,则必须采用数据类型包装类,如Integer等。

2. 判断顺序表是否为空

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

3. 返回顺序表长度

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

4. 返回指定位置的对象

    /**
     * 返回index(初始值為0)位置的对象,若序号无效,返回null
     */
     @Override
    public E get(int index) {
        if(index>=0&&index<this.n){
            return (E) this.table[index];
        }
        return null;
    }

代码解释:

get(index)等方法的参数index所指定序号不正确时,不能正常执行操作,将产生错误,需要传递错误信息。解决的方案有两种:一种是方法返回错误信息,另外一种是抛出异常。为了简化程序,这里选择第一种解决方案,当方法返回null值时表示操作不成功。因此约定,线性表中数据元素不能是空对象(null)。

5. 给指定位置赋值

     /**
     * 设置index位置的对象为element,若操作成功,返回原对象,否则返回null
     */
    @Override
    public E set(int index, E element) {
        if(index>=0&&index<this.n&&element!=null){
            E old=(E)this.table[index];
            this.table[index]=element;
            return old;
        }
        return null;
    }

6. 在指定位置插入值

    /**
     * 在index位置插入element对象,若操作成功返回true,不能插入null
     */
    @Override
    public boolean add(int index, E element) {
        if(element==null){
            return false; //不能插入null
        }
        if(this.n==this.table.length){ //若数组满,则需要扩充顺序表的容量
            Object[] temp = this.table;
            this.table=new Object[temp.length*2]; //重新申请一个容量更大的数组
            for(int i=0;i<temp.length;i++){
                this.table[i]=temp[i];  //复制数组元素,O(n)
            }
        }

        if(index<0){
            index=0;  //下标容错
        }
        if(index>this.n){
            index=this.n; //下标容错
        }

        for(int j=this.n-1;j>=index;j--){ //元素后移,平均移动n/2
            this.table[j+1]=this.table[j];
        }
        this.table[index] = element;
        this.n++;
        return true;
    }

代码解释:

顺序表的插入操作要移动数据元素。在顺序表元素ai位置插入元素element,首先必须将元素ai以及后面的元素向后移动,空出一个位置,然后将element插入。

当插入一个元素时,如果数组table已经装满,为了能够使插入操作正常运行,需要自动扩充容量,add()方法创建一个容量为原数组两倍的新数组。并将原数组中的元素复制到新数组中。若使用new申请存储空间失败,java虚拟机将产生内存溢出错误,并终止程序运行。

7. 在末尾位置插入值

     /**
     * 在顺序表最好插入element对象
     */
   @Override
    public boolean add(E element) {
        return this.add(this.n, element);
    }

8. 移除元素

     /**
     * 移去index位置的对象,若操作成功,则返回被移去对象,否则返回null
     */
    @Override
    public E remove(int index) {
        if(this.n!=0&&index>=0&&index<this.n){
            E old = (E)this.table[index];
            for(int i=index;i<this.n-1;i++){ //元素前移,平均移动n/2
                this.table[i]=this.table[i+1];
            }
            this.table[this.n-1]=null;
            this.n--;
            return old;  //若操作成功,则返回被移除对象
        }
        return null;  //未找到删除对象,操作不成功,返回null
    }

代码解释

顺序表的删除操作要移动数据元素。删除顺序表元素ai,必须将元素ai+1以及后面的元素向前移动。

9. 清空顺序表

     /**
     * 清空顺序表
     */
     @Override
    public void clear() {
        if(this.n!=0){
            for(int i=0;i<this.n;i++){
                this.table[i]=null;
            }
            this.n=0;
        }
    }

10. 重写toString()方法

     /**
     * 重写toString()方法
     */
        @Override
        public String toString() {
        String str="(";
        if(this.n!=0){
            for(int i=0;i<this.n-1;i++){
                str+=this.table[i].toString()+",";
            }
            str+=this.table[this.n-1].toString();
        }
        return str+")";
    }

三.测试

测试代码如下:

package org.light4j.dataStructure.linearList.seqList;

import org.light4j.dataStructure.linearList.LList;

public class Test {
    public static void main(String[] args) {
        // 初始化默认值容量的SeqList
        LList<String> defalutValueList = new SeqList<String>();
        // 添加A,B,C三个元素
        defalutValueList.add("A");
        defalutValueList.add("B");
        defalutValueList.add("C");
        // 输出元素个数
        System.out.println("defalutValueList线性表元素个数:"+defalutValueList.length());
        // 初始化容量值为10的SeqList
        LList<String> specifiedValueList = new SeqList<String>(10);
        // 添加D,E,F,G四个元素
        specifiedValueList.add("D");
        specifiedValueList.add("E");
        specifiedValueList.add("F");
        specifiedValueList.add("G");
        // 输出元素个数
        System.out.println("specifiedValueList线性表元素个数:"+specifiedValueList.length());
    }
}

运行结果如下图所示

四.顺序表操作的效率分析

顺序表是一种随机存取结构,存取任何一个元素的get(),set()方法的时间复杂度是O(1)

对顺序表进行插入或者删除操作时,算法所花费的时间主要用于移动元素。设表长度为n,若在第一个位置插入新元素,则需要移动n个元素;若在表的最后一个元素之后插入新元素,则不需要移动元素。在等概率情况下,插入一个元素平均需要移动一半的元素,时间复杂度为O(n)。同理,删除一个元素的时间复杂度也为O(n)

所以,顺序表具有下列特点:

元素的物理存储顺序直接反映表中元素的逻辑顺序,可以随机存取元素。

插入和删除效率低。每次插入或者删除一个元素,可能需要移动大量元素,其平均移动次数是顺序表长度的一半。再者,数组容量不可更改,存在因容量小造成数据溢出,或因容量过大造成内存资源浪费的问题。解决数据溢出的办法是,申请另一个更大容量的数组,并进行数组元素复制,但插入效率很低。

五.源代码示例

github地址:点击查看
码云地址:点击查看

打赏
欢迎关注人生设计师的微信公众账号
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » 自己实现集合框架(二):顺序表的实现

分享到:更多 ()

人生设计师-接受不同的声音

联系我关于我