数据结构---顺序表

张小驰出没

发布于 2021-12-06 16:20:49

4990

发布于 2021-12-06 16:20:49

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

1.实现顺序表

代码实现

public class SequenceList<T>{
    //存储元素的数组
    private T[] list;
    //记录当前顺序表中的元素个数
    private int n;

    public SequenceList(int capacity) {
        //初始化数组
        this.list = (T[]) new Objects[capacity];
        //初始化长度
        this.n = 0;
    }

    //将一个线性表置为空表
    public void clear() {
        this.n = 0;
    }

    //判断当前线性表是否为空表
    public boolean isEmpty() {
        return n == 0;
    }

    //获取线性表的长度
    public int length() {
        return n;
    }

    //获取指定位置的元素
    public T get(int i) {
        return list[i];
    }

    //向线型表中添加元素t
    public void insert(T t) {
        list[n++] = t;
    }

    //在i元素处插入元素t
    public void insert(int i, T t) {
        //索引i之后的元素，依次向后移动
        for (int index = n; index > i; index--) {
            list[index] = list[index - 1];
        }
        // t 放到i索引处
        list[i] = t;
        //元素个数+1
        n++;
    }

    //删除指定位置i处的元素，并返回该元素
    public T remove(int i) {
        //删除的元素
        T current = list[i];
        //索引i之后的元素，依次前移
        for (int index = i; index < n - 1; index++) {
            list[index] = list[index + 1];
        }
        //元素个数-1
        n--;
        //返回删除元素
        return current;
    }

    //查找t元素第一次出现的位置
    public int indexOf(T t) {
        for (int i = 0; i < n; i++) {
            if (list[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }
}

代码测试

public class SequenceListTest {
    public static void main(String[] args) {
        //创建顺序表对象
        SequenceList<String> sl = new SequenceList<>(10);
        //测试插入
        sl.insert("test1");
        sl.insert("test2");
        sl.insert("test3");
        sl.insert(1,"test4");
        //测试获取
        String getResult = sl.get(1);
        System.out.println("获取索引1处的结果为："+getResult);
        //测试删除
        String removeResult = sl.remove(0);
        System.out.println("删除的元素是："+removeResult);
        //测试清空
        sl.clear();
        System.out.println("清空后的线性表中的元素个数为:"+sl.length());
    }
}

2.顺序表遍历

1.继承实现 Iterable 接口，重写 iterator 方法； 2.提供一个内部类 SIterator, 实现 Iterator 接口，重写 hasNext 方法和 next 方法
代码实现

public class SequenceList<T> implements Iterable<T> {
    
    // .....之前的代码
    
    //重写iterator方法
    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }
    //内部方法类，实现Iterator接口
    private class SIterator implements Iterator {
        private int cusor;
        //构造方法
        public SIterator() {
            this.cusor = 0;
        }
        //下一个是否存在
        @Override
        public boolean hasNext() {
            return cusor < n;
        }
        //指向下一个值
        @Override
        public Object next() {
            return list[cusor++];
        }
    }
}

代码测试

public static void main(String[] args) {
    //创建顺序表对象
    SequenceList<String> sl = new SequenceList<>(10);
    //测试插入
    sl.insert("test1");
    sl.insert("test2");
    sl.insert("test3");
    sl.insert(1,"test4");
    for (String s : sl) {
        System.out.println(s);
    }
    System.out.println("-------------------------------");
    //测试获取
    String getResult = sl.get(1);
    System.out.println("获取索引1处的结果为："+getResult);
    //测试删除
    String removeResult = sl.remove(0);
    System.out.println("删除的元素是："+removeResult);
    //测试清空
    sl.clear();
    System.out.println("清空后的线性表中的元素个数为:"+sl.length());
}

3.顺序表容量可变

测试

创建一个容量为 2 的顺序表
在其中插入 3 个元素

public static void main(String[] args) {
    //创建顺序表对象
    SequenceList<String> sl = new SequenceList<>(2);
    //测试插入
    sl.insert("test1");
    sl.insert("test2");
    sl.insert("test3");
}

1.添加元素时： 添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我们这里创建一个是原数组两倍容量的新数组存储元素。

2.移除元素时： 移除元素时，应该检查当前数组的大小是否太大，这样会造成内存空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建一个是原数组容量的1/2的新数组存储元素。

代码实现

修改上述代码

//根据参数newSize，重置eles的大小
public void resize(int newSize) {
    //定义临时数组，指向原数组
    T[] t = list;
    //创建新的数组
    list = (T[]) new Object[newSize];
    //拷贝数组数据
    for (int i = 0; i < n; i++) {
       list[i] = t[i];
    }
}

//向线型表中添加元素t
public void insert(T t) {
    //判断是否扩容
    if (n == list.length) {
        resize(2 * n);
    }
    list[n++] = t;
}
//在i元素处插入元素t
public void insert(int i, T t) {
    //判断是否扩容
    if (n == list.length) {
        resize(2 * n);
    }
    //索引i之后的元素，依次向后移动
    for (int index = n; index > i; index--) {
        list[index] = list[index - 1];
    }
    // t 放到i索引处
    list[i] = t;
    //元素个数+1
    n++;
}
//删除指定位置i处的元素，并返回该元素
public T remove(int i) {
    //删除的元素
    T current = list[i];
    //索引i之后的元素，依次前移
    for (int index = i; index < n - 1; index++) {
        list[index] = list[index + 1];
    }
    //元素个数-1
    n--;
    //元素个数小于1/4长度，容量缩小为1/2
    if (n < list.length / 4) {
        resize(list.length / 2);
    }
    //返回删除元素
    return current;
}

4.时间复杂度

get(i) : 不难看出，不论数据元素量N有多大，只需要一次查询就可以获取到对应的元素，所以时间复杂度为 O(1) ;
insert(int i,T t) : 每一次插入，都需要把 i 位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时间复杂为 O(n) ;
remove(int i) : 每一次删除，都需要把 i 位置后面的元素移动一次，随着数据量N的增大,移动的元素也越多，时间复杂度为 O(n) ;

由于顺序表的底层由数组实现，数组的长度是固定的，所以在操作的过程中涉及到了容器扩容操作。这样会导致顺序表在使用过程中的时间复杂度不是线性的，在某些需要扩容的结点处，耗时会突增，尤其是元素越多，这个问题越明显