Java之順序表【五千字肝爆，零基礎保姆集教程不會你打我】

一.線性表

什么是線性表？

線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常
見的線性表：順序表、鏈表、堆疊、佇列、字串…

線性表在邏輯上是線性結構，也就說是連續的一條直線，
但是在物理結構上并不一定是連續的，線性表在物理上存
儲時，通常以陣列和鏈式結構的形式存盤，

二.順序表

2.1 那么什么是順序表？

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，
顧名思義，順序表它里面的數是按順序存放的，不能是隨意存放亦或者是間隔存放

就比如這樣，
那我們再想，順序表既然是順序存放的，那么它和誰的結構相像呢？

陣列

順序表的底層就是陣列

順序表一般可以分為：

• 靜態順序表
• 動態順序表

而我們要注意的是：

靜態順序表適用于確定知道需要存多少資料的場景.
靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用.
相比之下動態順序表更靈活, 根據需要動態的分配空間大小.

那么問題又來了：既然順序表底層是陣列，那為什么不直接使用陣列？？why？？

我們來畫一個圖：
請問這個陣列里面有多少有效資料？？

可能你會說：等于0的時候就跳出來嘛 count計數一下！！！
這樣是不可行的：

那如果0也是資料呢？對吧，這樣就會有問題，

那么我們可以定義一個變數：這個變數叫做 useSide （代表當前里面有多少有效資料）

這里代表里面有4個資料：

所以我們就會認識到：
一個順序表不只一個陣列就可以實作，還需要其他的變數（比如(usedSize）

注意：同時我想告訴大家：不要自己數有幾個數，要讓程式來！！
學資料結構千萬不能背代碼，一定要理解！！！

代碼實作

首先我們發現這個物件就是一個 順序表，里面有陣列和 有效陣列 變數和一個陣列容量：

看一些main里面實體化物件在記憶體的一個布局：

2.2實作順序表

根據上面的理解，我們知道了實作順序表需要的三個因素：

1. 陣列
2. 有效陣列
3. 可用容量

public class MyArrayList {
    public int[] elem;  //陣列
    public int useSize; //有效陣列
    public static int capacity = 10; //可用容量

    public 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() { }

是不是感覺頭皮發麻？

別慌，我們一起來一個一個看

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函式，以執行在pos位置添加data資料的功能，

接下來需要談談細節：

• 判斷陣列是否為滿，如果滿了實作擴容
• 判斷存放的位置下標是否合法（會不會陣列越界）
• 想在pos位置插入資料在陣列，首先要把后面的陣列往后面放一步，這樣前面才會有位置放
• 存放好資料記住useSize++；（有效資料加1）

我們來看一下圖片決議：

1，2，3，4，5順序存放，我們要在3的位置插入元素，那我們只需將3，4，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. 遍歷陣列，看看哪個元素在判斷時等于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. 遍歷陣列即可，找到回傳下標
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

思路：直接賦值即可，需要注意下標合法性

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很像，找到要洗掉的元素，然后讓第i+1個元素移到當前第i個的元素就可以了，最后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;
    }

后續小科還會寫很多關于資料結構等知識，希望我的講解能夠幫助到大家，byebye，