Java数据结构线性表之顺序表

分手后的思念是犯贱 2022-10-27 01:40 252阅读 0赞

### 目录 ###

*   *  一、线性表
     *  二、顺序表
     *   *  （1）顺序表的实现
         *  （2）顺序表的遍历
         *  （3）顺序表的容量可变
         *  （4）顺序表的时间复杂度
         *  （5）java中ArrayList实现

## 一、线性表 ##

线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM2NjQ5OQ_size_16_color_FFFFFF_t_70]  
前驱元素：

若A元素在B元素的前面，则称A为B的前驱元素

后继元素：

若B元素在A元素的后面，则称B为A的后继元素

**线性表的特征：** 数据元素之间具有一种“一对一”的逻辑关系。

1.  第一个数据元素没有前驱，这个数据元素被称为头结点；
2.  最后一个数据元素没有后继，这个数据元素被称为尾结点；
3.  除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

如果把线性表用数学语言来定义，则可以表示为(a1,…ai-1,ai,ai+1,…an)，ai-1领先于ai,ai领先于ai+1，称ai-1是ai的 前驱元素，ai+1是ai的后继元素  
![在这里插入图片描述][20210202220504511.png]  
**线性表的分类：**

线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为顺序 表和链表。

## 二、顺序表 ##

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

![在这里插入图片描述][20210202220617550.png]

### （1）顺序表的实现 ###

**顺序表API设计：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM2NjQ5OQ_size_16_color_FFFFFF_t_70_pic_center]  
**顺序表的代码实现：**

package cn.itcast.algorithm.linear;
    
    import java.util.Iterator;
    
    /** * @author ：caizhengjie * @description：TODO * @date ：2021/2/1 11:29 下午 */
    public class SequenceList<T> implements Iterable<T>{ 
    
        /** * 存储元素的数组 */
        private T[] eles;
    
        /** * 记录当前顺序表中的元素个数 */
        private int N;
    
        /** * 构造方法 * @param capacity */
        public SequenceList(int capacity) { 
            // 初始化数组
            this.eles = (T[]) new Object[capacity];
            // 初始化长度
            this.N = 0;
    
        }
    
        /** * 空置线性表 */
        public void clear(){ 
            this.N = 0;
        }
    
        /** * 判断线性表是否为空，是返回true，否返回false * @return */
        public boolean isEmpty(){ 
            return N == 0;
        }
    
        /** * 获取线性表中元素的个数 * @return */
        public int length(){ 
            return N;
        }
    
        /** * 读取并返回线性表中的第i个元素的值 * @param i * @return */
        public T get(int i){ 
            return eles[i];
        }
    
        /** * 在线性表的第i个元素之前插入一个值为t的数据元素 * @param i * @param t */
        public void insert(int i, T t){ 
    
            if (N == eles.length){ 
                resize(2*eles.length );
            }
    
            // 先把i索引处的元素及其后面的元素依次向后移动一位
            for (int index = N;index > i;index--){ 
                eles[index] = eles[index - 1];
            }
            // 再把t元素放到i索引处位置即可
            eles[i] = t;
    
            // 元素个数+1
            N++;
    
        }
    
        /** * 向线性表中添加一个元素t * @param t */
        public void insert(T t){ 
            if (N == eles.length){ 
                resize(2*eles.length );
            }
            eles[N++] = t;
    
        }
    
        /** * 删除并返回线性表中第i个数据元素 * @param i * @return */
        public T remove(int i){ 
            // 记录索引i处的位置
            T current = eles[i];
            // 索引i后面的元素依次向前移动一位即可
            for (int index = i;index < N-1;index++){ 
                eles[index] = eles[index + 1];
            }
            // 元素个数-1
            N--;
    
            if (N < eles.length/4){ 
                resize(eles.length/2);
            }
    
            return current;
    
        }
    
        /** * 返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返 回-1 * @param t * @return */
        public int indexOf(T t){ 
            for (int i=0;i<N;i++){ 
                if (eles[i].equals(t)){ 
                    return i;
                }
            }
            return -1;
        }
    
        /** * 根据参数newSize，重置eles大小 * @param newSize */
        public void resize(int newSize){ 
    
            // 定义一个临时数组，指向原数组
            T[] temp = eles;
            // 创建新数组
            eles = (T[]) new Object[newSize];
            // 把原数组的数组拷贝到新数组即可
            for (int i=0;i<N;i++){ 
                eles[i]=temp[i];
            }
    
        }
    
        @Override
        public Iterator<T> iterator() { 
            return new Iterator<T>() { 
                private int cusor;
                @Override
                public boolean hasNext() { 
                    return cusor < N;
                }
    
                @Override
                public T next() { 
                    return eles[cusor++];
                }
            };
        }
    }

package cn.itcast.algorithm.test;
    
    import cn.itcast.algorithm.linear.SequenceList;
    
    /** * @author ：caizhengjie * @description：TODO * @date ：2021/2/2 12:11 上午 */
    public class SequenceListTest { 
        public static void main(String[] args) { 
            // 创建顺序表对象
            SequenceList<String> s1 = new SequenceList<>(10);
    
            // 测试插入
            s1.insert("alex");
            s1.insert("lili");
            s1.insert("jone");
            s1.insert(1,"jack");
    
            // 遍历
            for (String s : s1) { 
                System.out.println(s);
            }
    
            // 测试获取
            String getResult = s1.get(1);
            System.out.println("获取索引1处的结果为：" + getResult);
    
            // 测试删除
            String removeResult = s1.remove(0);
            System.out.println("删除的元素为：" + removeResult);
    
            // 测试清空
            s1.clear();
            System.out.println("清空后线性表中的元素的个数为：" + s1.length());
        }
    }

alex
    jack
    lili
    jone
    获取索引1处的结果为：jack
    删除的元素为：alex
    清空后线性表中的元素的个数为：0

### （2）顺序表的遍历 ###

一般作为容器存储数据，都需要向外部提供遍历的方式，因此我们需要给顺序表提供遍历方式。在java中，遍历集合的方式一般都是用的是foreach循环，如果想让我们的SequenceList也能支持foreach循环，则 需要做如下操作：

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

### （3）顺序表的容量可变 ###

在之前的实现中，当我们使用SequenceList时，先new SequenceList(5)创建一个对象，创建对象时就需要指定容 器的大小，初始化指定大小的数组来存储元素，当我们插入元素时，如果已经插入了5个元素，还要继续插入数 据，则会报错，就不能插入了。这种设计不符合容器的设计理念，因此我们在设计顺序表时，应该考虑它的容量的 伸缩性。

考虑容器的容量伸缩性，其实就是改变存储数据元素的数组的大小，那我们需要考虑什么时候需要改变数组的大 小？

**添加元素时：**  
添加元素时，应该检查当前数组的大小是否能容纳新的元素，如果不能容纳，则需要创建新的容量更大的数组，我 们这里创建一个是原数组两倍容量的新数组存储元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM2NjQ5OQ_size_16_color_FFFFFF_t_70 1]  
**移除元素时：**  
移除元素时，应该检查当前数组的大小是否太大，比如正在用100个容量的数组存储10个元素，这样就会造成内存 空间的浪费，应该创建一个容量更小的数组存储元素。如果我们发现数据元素的数量不足数组容量的1/4，则创建 一个是原数组容量的1/2的新数组存储元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM2NjQ5OQ_size_16_color_FFFFFF_t_70 2]

### （4）顺序表的时间复杂度 ###

get(i):不难看出，不论数据元素量N有多大，只需要一次eles\[i\]就可以获取到对应的元素，所以时间复杂度为O(1);

insert(int i,T t):每一次插入，都需要把i位置后面的元素移动一次，随着元素数量N的增大，移动的元素也越多，时 间复杂为O(n);

remove(int i):每一次删除，都需要把i位置后面的元素移动一次，随着数据量N的增大,移动的元素也越多，时间复 杂度为O(n);

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

### （5）java中ArrayList实现 ###

**java中ArrayList集合的底层也是一种顺序表，使用数组实现，同样提供了增删改查以及扩容等功能。**

--------------------

以上内容仅供参考学习，如有侵权请联系我删除！  
如果这篇文章对您有帮助，左下角的大拇指就是对博主最大的鼓励。  
您的鼓励就是博主最大的动力！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM2NjQ5OQ_size_16_color_FFFFFF_t_70]: /images/20221024/5b555dee2bd2447ab50d7c45c236c97b.png
[20210202220504511.png]: /images/20221024/a32c65edc847464385002bfc2b57fb01.png
[20210202220617550.png]: /images/20221024/1d3beff6597c4a7a98101c54dc334016.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM2NjQ5OQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/05e0b770ae6a495f80083f39096f4a91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM2NjQ5OQ_size_16_color_FFFFFF_t_70 1]: /images/20221024/65958462f6c840fda6cfa73069b3c82c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM2NjQ5OQ_size_16_color_FFFFFF_t_70 2]: /images/20221024/c1186afc545a41f584ad18b4528b6da4.png