本篇博客將詳細講解順序表的相關知識，

順序表的概念

順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，

順序表一般分為兩類：靜態順序表和動態順序表，

靜態順序表：使用定長陣列存盤，

動態順序表：使用動態開辟的陣列存盤，

為了讓順序表能更好地面向物件，需要創建一個類，來完成順序表的各種功能，

順序表的實作

變數創建

既然順序表一般是用陣列存盤，因此需要一個陣列，為了確定陣列的長度（有效值的個數），因此還需要設定一個變數，代碼如下：

public int[] elem;
public int usedSize;

為了在實體化物件的時候創建陣列，因此需要一個構造方法，代碼如下：

public MyArrayList(){
	this.elem = new int[10];
}

注：我所創建的類的類名為MyArrayList，初始創建的陣列大小為10，

列印順序表

我們在使用順序表的時候，一般需要列印順序表，查看順序表里的內容，代碼如下：

public void display() {
	for (int i = 0;i < this.usedSize;i++) { 
		System.out.print(this.elem[i] + " ");
	}
	System.out.println();
}

注：i<this.usedSize：表示順序表中的有效資料的長度，而不是陣列的長度，

獲取順序表的（有效）長度

我們在使用順序表的時候，需要知道順序表的有效長度，代碼如下：

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

增加元素

在順序表的使用程序中，我們難免需要增加元素，因此我們需要一個方法來完成這個功能，假設在pos位置增加元素，而在增加元素的程序中，需要分四步，

判斷pos位置的合法性

pos不能為負數，同時pos不能大于usedSize，否則沒有意義，

判斷順序表是否需要擴容

I在增加元素的時候，順序表很有可能放滿元素了，因此首先要判斷順序表是否已經放滿元素，如果已經放滿，則需要對順序表進行擴容，

將順序表中的已有資料進行移動

因為需要在pos位置增加元素，因此pos位置以后的資料需要向后移動，移動方向如下圖：

資料插入后，usedSize++

當資料插入后，有效長度（usedSize）需要加1，

具體代碼

public void add(int pos, int data) {
    if(pos < 0 || pos > usedSize) {
        System.out.println("pos位置不合法");
        return;
    }
    if(isFull()) {
        this.elem = Arrays.copyOf(this.elem,2 * this.elem.length);
    }
    for(int i = this.usedSize - 1; i >= pos; i--) {
        this.elem[i+1] = this.elem[i];
    }
    this.elem[pos] = data;
    this.useSize++;
}

public boolean isFull() {
    return this.useSize == this.elem.length;
}

判斷順序表中是否包含某個元素

在使用順序表的時候，我們需要判斷順序表中是否包含某個資料，具體代碼如下：

public boolean contains(int toFind) {
    for (int i = 0; i < this.usedSize; i++) {
        if(this.elem[i] == toFind) {
            return true;
        }
    }
    return false;
}

查找元素

順序表的功能中應該包含查找功能，具體代碼如下：

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

獲取元素

假設需要獲取pos位置的元素，代碼如下：

public int getsPos(int pos) {
    if(pos < 0 || pos >= this.usedSize) {
        System.out.println("pos位置不合法");
        return -1;//這里的-1僅僅代表位置不合法，不考慮業務的處理，當然，也可以用例外去處理，后期會講到，
    }
    return this.elem[pos];
}

更改元素

假設更改pos位置的元素，將其改為value，代碼如下：

public void setPos(int pos, int value) {
    if(pos < 0 || pos >= this.usedSize) {
        System.out.println("pos位置不合法");
        return -1;
    }
    this.elem[pos] = value;
}

洗掉元素

洗掉元素的步驟如下：

1.判斷順序表是否為空

2.查找要洗掉的元素

3.洗掉元素

洗掉元素的本質是覆寫，假設洗掉下列順序表中的85：

具體代碼如下：

public void remove(int toRemove) {
    if(isEmpty()) {
        System.out.println("順序表為空！");
        return -1;
    }
    int index = search(toRemove);
    if(index == -1) {
        System.out.println("沒有你要洗掉的數字");
        return -1;
    }
    for(int i = index;i < this.usedSize-1;i++) {
        this.elem[i] = this.elem[i+1];
    }
    this.usedSize--;


public boolean isEmpty() {
    return this.usedSize == 0;
}

清空順序表

假設順序表中存放的是簡單型別的資料，則清空順序表的代碼如下：

public void clear() {
    this.usedSize = 0;
}

順序表的缺點

1.插入和洗掉元素時，必須移動元素，

2.需要考慮擴容的問題，容易造成記憶體沒有充分的問題，

結尾

那么有沒有其他的資料結構可以解決這些問題呢？

當然有， 至于是什么，且聽下回分說，

上一篇博客：Java學習苦旅（八）——不復雜的復雜度

下一篇博客預告：Java學習苦旅（十）——鏈表的奧秘