• 《数据结构-第一章》之顺序表

    前言

    在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!”

    博客主页：KC老衲爱尼姑的博客主页

    博主的github，平常所写代码皆在于此

    刷题求职神器

    共勉：talk is cheap, show me the code

    作者是爪哇岛的新手，水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

    文章目录

    线性表

    线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。线性表的逻辑上是连续的,物理上不一定连续的，比如数组它在逻辑上和物理上都是连续的,但是链表在逻辑上是连续的在物理上是不连续的。常见的线性表有数组,栈,队列,链表。

    数组在内存的存储

    在这里插入图片描述

    链表在内存的存储

    在这里插入图片描述

    线性表定义如下

    线性表是具有相同数据类型的n（n≥0）个类型相同的数据元素组成的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其他更复杂的信息。线性表通常记为：（a1，…，ai－1，，ai，ai＋1，，…，an），其中n为表长，n＝0时称为空表。表中相邻元素之间存在着顺序关系，ai－1领先于ai，ai领先于ai＋1，称ai－1是ai的直接前驱元素，ai＋1是ai的直接后继元素。当i＝1，2，…，n－1时，ai有且仅有一个直接后继；当i＝2，3，…，n时，ai有且仅有一个直接前驱ai－1；当i＝1，2，…，n－1时，有且仅有一个直接后继ai＋1，而a1是表中第一个元素，它没有前驱，an是最后一个元素，无后继。

    前驱:线性表中除了第一个元素以外都有前驱

    后继:线性表中除了最后一个元素以外都有后继

    顺序表

    顺序表是用一段物理地址连续的存储单元依次存储元素的线性结构。一般情况下采用数组存储,在数组上完成数据的增删查改。像Java中的ArrayList就是顺序表,底层是一个Object数组。接下来就使用数组来实现一个简单的顺序表。

    接口实现

    public class SeqList {
// 打印顺序表
public void display() { }
// 新增元素,默认在数组最后新增
public void add(int data) { }
// 在 pos 位置新增元素
public void add(int pos, int data) { }
// 判定是否包含某个元素
public boolean contains(int toFind) { return true; }
// 查找某个元素对应的位置
public int indexOf(int toFind) { return -1; }
// 获取 pos 位置的元素
public int get(int pos) { return -1; }
// 给 pos 位置的元素设为 value
public void set(int pos, int value) { }
//删除第一次出现的关键字key
public void remove(int toRemove) { }
// 获取顺序表长度
public int size() { return 0; }
// 清空顺序表
public void clear() { }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    属性

        private static final int capacity = 3;//初始化数组的容量
    private int elem[];//存储元素的数组
    private int userSized;//记录顺序表中元素的个数

    • 1
    • 2
    • 3

    构造方法

    使用无参构造在创建顺序表的时候,为其分配默认的容量

        public MyArrayList() {
        this.size = 0;
        elementData = new int[CAPACITY];
    }

    • 1
    • 2
    • 3
    • 4

    常用方法

    打印顺序表

    遍历数组即可

    
    /**
     * 打印顺序表中的数据
     */
    public void display() {
        for (int i = 0; i < this.userSized; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    添加元素

    默认在数组末尾添加元素

       /**
     * 新增元素,默认在数组末尾添加元素
     *
     * @param element
     */
    public void add(int element) {
        if (isFull()) {//对数组进行判断是否已经满了,满了则2倍扩容
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        this.elementData[this.size++] = element;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    在指定位置插入元素

    在数组中插入一个元素,并不是使用数组直接访问该位置然后进行修改这个位置的值,这不是插入而是修改。在顺序表中定义一个size属性,记录数组中元素的个数,假设现在数组中有8个元素,那么size指向的位置是在数组中元素的后一个位置,我们可以将从指定插入位置到size-1位置的元素都往后挪一个位置出来,然后再将要插入的元素插入即可。

    假设数组长度为11,在数组的索引2处插入一个99，插入过程如下图。

    在这里插入图片描述

        /**
     * 在指定位置插入元素
     *
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        if (isFull()) {//判断是否已满
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        //判断index合法
        if (index < 0 || index > this.size) {
            return;
        }
        //从要插入元素的位置开始将元素都后移
        for (int i = this.size-1; i >= index; i--) {
            this.elementData[i + 1] = this.elementData[i];
        }
        //插入元素
        this.elementData[index] = element;
        this.size++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    判定是否包含某个元素

    直接遍历数组找到目标值

       /**
     * 判断数组中是否包含该元素
     * @param toFind
     * @return
     */
    public boolean contains(int toFind) {
        if (isEmpty()){
            return true;
        }
        for (int i=0;i<this.size;i++) {
            if (this.elementData[i]==toFind) {
                return true;
            }
        }
        return false;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    查找某个元素对应的位置(头到尾)
      /**
     * 查找某个元素对应的位置(从头到尾)
     * @param toFind
     * @return
     */
    public int indexOf(int toFind) {
        for (int i = 0; i < this.size; i++) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    查找某个元素对应的位置(尾–>头)
    
    /**
     * 查找某个元素对应的位置(从尾都头)
     * @param toFind
     * @return
     */
    public int lastIndexOf(int toFind) {
        for (int i=this.size-1;i>=0;i--) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    获得pos位置的值

    首先进进判空,在判断pos是否合法,最后直接访问。

      /**
     *  pos 位置的元素
     * @param pos
     * @return
     */
    public int get(int pos) {
        if (isEmpty()) {
            throw new RuntimeException("MyArrayList为空");
        }
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos位置不合法");
        }
        return this.elementData[pos];
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    设置pos位置的值

    首先进进判空,在判断pos是否合法,最后直接修改。

      /**
     * 给 pos 位置的元素设为 value
     * @param pos
     * @param value
     */
    public void set(int pos, int value) {
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos不合法");
        }
        this.elementData[pos] = value;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    删除第一次出现的关键字

    先找到要删除的位置,然后判断该位置是否合法,然后该位置后面的元素都往前移动一个位置,就可以完成删除。

        /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
        int index = searchIndex(key);
        if (index<0||index>this.size) {
            throw new RuntimeException("index不合法");
        }
        for (int i=index; i<this.size-1; i++) {
            this.elementData[i] = this.elementData[i+1];
        }
        this.size--;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    获取顺序表的长度

    直接返回size即可

        /**
     * 返回数组的长度
     *
     * @return
     */
    public int size() {
        return this.size;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    清空顺序表

    注意:如果是基本类型,直接将size置空,如果是引用类型要将所有元素置为null,再将size置为0。

        /**
     * 清空数组
     */
    public void clear(){
        this.size = 0;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    顺序表所有的源代码

    package com.kc.demo;

import java.util.Arrays;

public class MyArrayList {
    private static int[] elementData;
    private static final int CAPACITY = 5;//初始化数组的容量
    private int size;

    public MyArrayList() {
        this.size = 0;
        elementData = new int[CAPACITY];
    }

    /**
     * 遍历数组
     */
    public void display() {
        for (int i = 0; i < this.size; i++) {
            System.out.print(this.elementData[i] + " ");
        }
        System.out.println();
    }

    /**
     * 新增元素,默认在数组末尾添加元素
     *
     * @param element
     */
    public void add(int element) {
        if (isFull()) {
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        this.elementData[this.size++] = element;
    }

    /**
     * 在指定位置插入元素
     *
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        if (isFull()) {
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        //判断index合法
        if (index < 0 || index > this.size) {
            return;
        }
        for (int i = this.size-1; i >= index; i--) {
            this.elementData[i + 1] = this.elementData[i];
        }
        this.elementData[index] = element;
        this.size++;
    }

    /**
     * 删除第一次出现的关键字key
     * @param key
     */
    public void remove(int key) {
        int index = searchIndex(key);
        if (index<0||index>this.size) {
            throw new RuntimeException("index不合法");
        }
        for (int i=index; i<this.size-1; i++) {
            this.elementData[i] = this.elementData[i+1];
        }
        this.size--;
    }

    /**
     * 查找该元素数组中第一次出现的位置
     * @param key
     * @return
     */
    private int searchIndex(int key){
      for (int i=0;i<this.size;i++) {
          if (this.elementData[i]==key) {
              return i;
          }
      }
      return -1;
    }

    /**
     * 判断数组中是否包含该元素
     * @param toFind
     * @return
     */
    public boolean contains(int toFind) {
        if (isEmpty()){
            return true;
        }
        for (int i=0;i<this.size;i++) {
            if (this.elementData[i]==toFind) {
                return true;
            }
        }
        return false;
    }

    /**
     * 判断数组是否已经满了
     * @return
     */
    private boolean isFull() {
        if (this.size == CAPACITY) {
            return true;
        }
        return false;
    }

    /**
     * 查找某个元素对应的位置(从头到尾)
     * @param toFind
     * @return
     */
    public int indexOf(int toFind) {
        for (int i = 0; i < this.size; i++) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 查找某个元素对应的位置(从尾都头)
     * @param toFind
     * @return
     */
    public int lastIndexOf(int toFind) {
        for (int i=this.size-1;i>=0;i--) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 给 pos 位置的元素设为 value
     * @param pos
     * @param value
     */
    public void set(int pos, int value) {
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos不合法");
        }
        this.elementData[pos] = value;
    }

    /**
     *  pos 位置的元素
     * @param pos
     * @return
     */
    public int get(int pos) {
        if (isEmpty()) {
            throw new RuntimeException("MyArrayList为空");
        }
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos位置不合法");
        }
        return this.elementData[pos];
    }

    /**
     * 判断数组是否为空
     * @return
     */
    private boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 返回数组的长度
     *
     * @return
     */
    public int size() {
        return this.size;
    }

    /**
     * 清空数组
     */
    public void clear(){
        this.size = 0;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193

    结

    各位看官如果觉得文章写得不错，点赞评论关注走一波！谢谢啦！

    在这里插入图片描述

  • 相关阅读:
    数字化档案管理系统解决方案
    sql同表分组取第一条
    Istio EnvoyFilter+Lua 简单实现动态路由转发
    出国参展注意事项
    建行广东江门分行：科技赋能，数据助力纠“四风”
    Unity编辑器扩展——实现样条线编辑器
    linux用户空间向内核空间通信之使用proc接口和使用WARN_ON和BUG_ON调试内核代码
    Vue2.0开发之——Vue组件-组件的基本使用(31)
    Python 快速入门
    批处理及有状态等应用类型在 K8S 上应该如何配置?
  • 原文地址：https://blog.csdn.net/qq_60308100/article/details/127587714