Skip to main content

顺序存储结构

顺序结构定义​

线性表的顺序存储结构，指的是一段地址连续的存储单元依次存储线性表的数据元素。
  • 构成顺序存储结构需要三个属性:
    • 存储空间的起始位置（数组data的第一个内存地址，也就是数组下标0的位置data[0]）
    • 线性表的最大存储容量（数组的长度）
    • 线性表的当前长度（元素的个数，不定量会变化）
warning

注意数组的长度和线性表的长度区别，前者描述存放线性表存储空间的长度一般固定。后者描述是线性表元素的个数。往往后者要小于等于前者。

顺序存储结构基础操作​

  1. 我们根据上述讲述的三个属性，创建一个顺序存储结构的类
Details

定义顺序存储结构类   


    static class LinearStructure {
        // 最大存储长度
        int maxSize;
        // 存储线性表的数组
        int[] data;
        // 线性表长度
        int length;

        // 初始化
        public LinearStructure(int number) {
            // 最大数组长度
            this.maxSize = number;
            // 初始化数组data
            this.data = new int[this.maxSize];
            // this.data[0] = 1;
            // this.data[1] = 2;
            // this.data[2] = 3;
            // this.data[3] = 4;
            // 线性表 初始化长度0
            this.length = 0;
        }
    }

  1. 顺序存储结构获取getElem元素

顺序存储结构获取元素非常简单，直接根据下标获取即可。

         public int getData(int index) {
            return data[index];
         }
因可直接根据下标获取元素，因此线性表不管多长不管在什么位置，时间复杂度都是O(1)
  1. 顺序存储结构的插入insertElem操作

Hare正在火车站排队买票，来了一个小伙子告知是否插队我前面，看着挺着急谁让咱善良呢。小伙子站在了我的前面，随后我就得向后移动，当然后面的人都得向后移动。队伍蠕动了起来！ 插队演示

从以上讲述可得知，顺序存储结构若是遇到了插入则每个元素都得向后移动（插入时，数组长度要有空余的位置）。

         // 插入数据
        public boolean insert(int num, int i) throws Exception {
            if (!full()) {
                if (i >= this.maxSize || i < 0) {
                    throw new Exception("超出数组长度");
                }
                // 最优情况i等于this.data.length-1，每次插入到最后面O(1)
                //data[i] = num;

                // 往后移动
                for (int j = this.length-1; j >= i; j--) {
                    data[j + 1] = data[j];
                }
                // 插队
                data[i] = num;

                this.length++;
                return true;
            }
            throw new Exception("已满，插入失败~");
        }

        // 当线性表长度等于数组最大存储长度则当前已满
        public boolean full() {
            if (this.length == this.maxSize) {
                return true;
            }
            return false;
        }

顺序存储结构最终分析​

  • 最优情况下: 删除，插入最后一个，不需要动其他的元素。则时间复杂度O(1)
  • 最坏情况下: 删除，插入，需要移动元素，则时间复杂度O(n)
  • 当我们获取元素时: 直接根据下标获取即可，所以此顺序存储结构适合读多，增删写少(速度慢性能影响)
0%
Loading Comments...