Java之顺序表【五千字肝爆，零基础保姆集教程不会你打我】

前言 11月7日凌晨1点LPL全球总决赛࿰c;在距离中国7777公里的冰岛上࿰c;EDG打败DK战队赢得冠军࿰c;让我们恭喜EDG

一.线性表

什么是线性表？

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构࿰c;常 见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构࿰c;也就说是连续的一条直线。 但是在物理结构上并不一定是连续的࿰c;线性表在物理上存 储时࿰c;通常以数组和链式结构的形式存储。

@H_262_75@

二.顺序表

2.1 那么什么是顺序表？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构࿰c;一般情况下采用数组存储。在数组上完成数据的增删查改。 顾名思义࿰c;顺序表它里面的数是按顺序存放的࿰c;不能是随意存放亦或者是间隔存放

就比如这样。 那我们再想࿰c;顺序表既然是顺序存放的࿰c;那么它和谁的结构相像呢？

数组

顺序表的底层就是数组

顺序表一般可以分为：

• 静态顺序表
• 动态顺序表

而我们要注意的是：

静态顺序表适用于确定知道需要存多少数据的场景. 静态顺序表的定长数组导致N定大了࿰c;空间开多了浪费࿰c;开少了不够用. 相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.

那么问题又来了：既然顺序表底层是数组࿰c;那为什么不直接使用数组？？why？？

我们来画一个图： 请问这个数组里面有多少有效数据？？

可能你会说：等于0的时候就跳出来嘛 count计数一下！！！ 这样是不可行的：

那如果0也是数据呢？对吧࿰c;这样就会有问题。

那么我们可以定义一个变量：这个变量叫做 useSide （代表当前里面有多少有效数据）

这里代表里面有4个数据：

所以我们就会认识到： 一个顺序表不只一个数组就可以实现࿰c;还需要其他的变量（比如(usedSize）

注意：同时我想告诉大家：不要自己数有几个数࿰c;要让程序来！！ 学数据结构千万不能背代码࿰c;一定要理解！！！

代码实现

首先我们发现这个对象就是一个 顺序表࿰c;里面有数组和 有效数组 变量和一个数组容量：

看一些main里面实例化对象在内存的一个布局：

2.2实现顺序表

根据上面的理解࿰c;我们知道了实现顺序表需要的三个因素：

1. 数组
2. 有效数组
3. 可用容量

public class @H_68_175@myArrayList {
    public int[] elem;  //数组
    public int useSize; //有效数组
    public static int capacity = 10; //可用容量

    public @H_68_175@myArrayList() {   //使用构造方法 初始容量
        this.elem = new int[capacity];
    }
}

构造函数的相关知识可以去看我写的另一篇博客： 带你一分钟理解构造函数

三.顺序表的接口（常用操作）实现：

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

是不是感觉头皮发麻？

别慌࿰c;我们一起来一个一个看

1.打印顺序表

思路：遍历数组即可

注意遍历的长度是useSize（打印有效的数字）

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

2.在pos位置加入一个指定的元素

给定指定的位置放入指定的数据：

public void add(int pos,int data){
	
}

我们需要在顺序表中执行add函数࿰c;以执行在pos位置添加data数据的功能。

接下来需要谈谈细节：

• 判断数组是否为满࿰c;如果满了实现扩容
• 判断存放的位置下标是否合法（会不会数组越界）
• 想在pos位置插入数据在数组࿰c;首先要把后面的数组往后面放一步࿰c;这样前面才会有位置放
• 存放好数据记住useSize++；（有效数据加1）

我们来看一下图片解析：

1࿰c;2࿰c;3࿰c;4࿰c;5顺序存放࿰c;我们要在3的位置插入元素࿰c;那我们只需将3࿰c;4࿰c;5都向后移一个位置即可。

让我们一起来看一下代码：

		public Boolean isFull() {
        /*if(thiS.UsedSize == capacity) {
            return true;
        }
        return false;*////两种方法
        return this.usedSize == capacity;//判断useSize和最大容量一样吗 一样就满了
    }
		public void add(int pos, int data) {
		//1、pos的合法情况
        if(pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法！");
            return;
        }
        //2、满的情况 
        if(isFull()) {
            //扩容
            this.elem = Arrays.copyOf(this.elem,2*capacity);
            capacity *= 2;//新的容量
        }
        for(int i = this.usedSize-1; i >= pos;i--) {
            this.elem[i+1] = this.elem[i];
        }
        this.elem[pos] = data;
        this.usedSize++;
    }

3.判定是否包含某个元素

思路：

1. 遍历的长度为：useSize
2. 遍历数组࿰c;看看哪个元素在判断时等于toFind（需要判断的元素）

//判断数组是否为空（有效数据是否为0）
public Boolean isEmpty() {
        return this.usedSize == 0;
    }
public Boolean contains(int toFind) {
        if(isEmpty()) return false;
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

4.查找某个元素对应的位置

思路：

1. 遍历数组即可࿰c;找到返回下标
2. 注意数组的遍历长度为useSize

	public Boolean isEmpty() {
        return this.usedSize == 0;
    }
	public int search(int toFind) {
        if(isEmpty()) return -1;
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

5.获取 pos 位置的元素

思路： 直接返回pos下标的数组

public int getPos(int pos) {
        if(isEmpty()) {
            //return -1; 业务的处理
            throw new RuntimeException("顺序表是空的");//手动抛出错误(异常)
        }
        if(pos < 0 || pos >= this.usedSize) {
            throw new RuntimeException("pos不合法");//手动抛出错误(异常)
        }

        return this.elem[pos];
    }

6.获取顺序表长度

思路：直接返回useSize 即可

public int size() {
        return this.usedSize;
    }

7.给 pos 位置的元素设为 value

思路：直接赋值即可࿰c;需要注意下标合法性

public void setPos(int pos, int value) {
        if(pos < 0 || pos >= this.usedSize) {
            System.out.println("pos不合法！");
            return;
        }
        if(isEmpty()) {
            System.out.println("顺序表为空！");
            return;
        }
        this.elem[pos] = value;
    }

8.删除第一次出现的关键字key

代码和add很像࿰c;找到要删除的元素࿰c;然后让第i+1个元素移到当前第i个的元素就可以了࿰c;最后useSize–1.

图片解析：

public void remove(int toRemove) {
        if(isEmpty()) return;
        int index = search(toRemove);
        if(index == -1) {
            System.out.println("没有你要删除的数字");
            return;
        }
        for (int i = index; i < this.usedSize-1; i++) {
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
    }

9.清空顺序表

思路：让数组每个元素都为0（有效数据也为0）

public void clear() {
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = 0;
        }
        this.usedSize = 0;
    }

后续小科还会写很多关于数据结构等知识࿰c;希望我的讲解能够帮助到大家࿰c;byebye。