Java數(shù)據(jù)結(jié)構(gòu)之順序表篇

更新時(shí)間：2022年01月19日 16:51:36 作者：ViolentAsteroid

順序表，全名順序存儲結(jié)構(gòu)，是線性表的一種。線性表用于存儲邏輯關(guān)系為“一對一”的數(shù)據(jù)，順序表自然也不例外，不僅如此，順序表對數(shù)據(jù)物理存儲結(jié)構(gòu)也有要求。順序表存儲數(shù)據(jù)時(shí)，會提前申請一整塊足夠大小的物理空間，然后將數(shù)據(jù)依次存儲起來，存儲時(shí)數(shù)據(jù)元素間不留縫隙

一.線性表

線性表（ linear list ）是 n 個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串... 線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。

二.順序表

1.概念及結(jié)構(gòu)

順序表是用一段物理地址連續(xù) 的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。

而順序表一般可以分為兩類：靜態(tài)順序表、動態(tài)順序表

2.順序表的實(shí)現(xiàn)

首先我們將順序表的成員屬性以及構(gòu)造函數(shù)寫好，接下來實(shí)現(xiàn)具體接口

public class MyArrayList {
 
    public int[] elem;
    public int usedSize;//有效的數(shù)據(jù)個(gè)數(shù)，默認(rèn)值為0
 
    public MyArrayList() {//初始化一個(gè)數(shù)組，容量為5
        this.elem = new int[5];
    }
 
}

打印順序表

只需要遍歷完數(shù)組，然后將其打印出來即可

具體的代碼實(shí)現(xiàn)：

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

獲取順序表的有效長度

有效長度就是已經(jīng)用過的元素，返回usedSize即可

具體的代碼實(shí)現(xiàn)：

// 獲取順序表的有效數(shù)據(jù)長度
    public int size() {
            return usedSize;
    }

在pos位置新增元素

具體的操作分為四步：

1、判斷pos位置是否合法，即pos既不能小于0，也不能大于有效數(shù)據(jù)個(gè)數(shù)

2、判斷順序表是否已滿，如果滿了，需要Arrays.CopyOf()進(jìn)行擴(kuò)容

3、將pos后的元素依次后移，即 elem[i+1]=elem[i]

4、將目標(biāo)元素data放入pos下標(biāo)對應(yīng)位置，即elem[pos]=data

具體的代碼實(shí)現(xiàn)：

// 在 pos 位置新增元素
    public void add(int pos, int data) {
        //1.判斷pos位置是否合法
        if (pos<0 || pos>usedSize){
            System.out.println("pos位置不合法");
            return;
        }
        //2.判斷usedSize是否已滿
        if (isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //3.開始挪數(shù)據(jù),并且給pos位置賦值
        for (int i = usedSize-1; i >= pos ; i--) {
                elem[i+1]=elem[i];//把i下標(biāo)的值給i+1
            }
        this.elem[pos]=data;
        this.usedSize++;//說明存放成功
    }
    public boolean isFull(){
            return this.usedSize == this.elem.length;
    }

判斷是否包含某個(gè)元素

只需要傳入需要查找的元素toFind，然后遍歷查找即可

具體的代碼實(shí)現(xiàn)：

// 判定是否包含某個(gè)元素
    public boolean contains(int toFind) {
        for (int i = 0; i <this.usedSize ; i++) {
            if (this.elem[i]==toFind)
                return true;
        }
        return false;
    }

查找某個(gè)元素對應(yīng)的位置

跟上一個(gè)操作一樣，使用遍歷查找到元素后，返回其下標(biāo)即可

具體的代碼實(shí)現(xiàn)：

// 查找某個(gè)元素對應(yīng)的位置
    public int search(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i]==toFind)
                return i;//找到了返回i下標(biāo)
        }
        return -1; //找不到返回-1，因?yàn)閿?shù)組沒有負(fù)數(shù)下標(biāo)
    }

獲取/查找pos位置的元素

凡是傳入pos位置，我們都需要判斷pos是否合法，也要查看順序表是否為空，如果合法且不為空直接返回該下標(biāo)對應(yīng)的元素即可

具體的代碼實(shí)現(xiàn)：

// 獲取 pos 位置的元素
    public int getPos(int pos) {
        if (pos<0 || pos>this.usedSize){
            System.out.println("pos位置不合法");
            return -1;//說明pos位置不合法
        }
        if(isEmpty()){
            System.out.println("順序表為空");
            return -1;
        }
        return this.elem[pos];//返回pos位置的值
    }
    public boolean isEmpty(){
        return this.usedSize==0;
    }

給pos位置的元素設(shè)為value

依然先判斷pos位置是否合法，再判斷順序表是否為空，如果合法且不為空，則將value賦值給pos下標(biāo)對應(yīng)的元素

具體的代碼實(shí)現(xiàn)：

// 給 pos 位置的元素設(shè)為/更新為 value
    public void setPos(int pos, int value) {
        //還是要先判斷pos位置的合法性
        if (pos<0 || pos>usedSize){
            System.out.println("pos位置不合法");
            return;
        }
        if(isEmpty()){
            System.out.println("順序表為空");
            return ;
        }
        this.elem[pos] = value;//將pos位置的元素更新為value
    }

刪除第一次出現(xiàn)的關(guān)鍵字key

具體步驟如下：

1、判斷順序表是否為空(除了增加元素是判斷順序表是否已滿，其他的都是判斷是否為空)

2、調(diào)用我們上邊寫的search函數(shù)，看是否存在該元素

3、如果存在，則從該元素起，將后面的元素往前挪，將要刪除的元素覆蓋

具體的代碼實(shí)現(xiàn)如下：

//刪除第一次出現(xiàn)的關(guān)鍵字key
    public void remove(int toRemove) {
        if (isEmpty()){
            System.out.println("順序表為空");
            return;
        }
        int index = search(toRemove);
        if (index==-1) {
            System.out.println("沒有你要刪除的數(shù)字");
            return;
        }
        for (int i = index; i < usedSize-1; i++) {
            this.elem[i]=this.elem[i+1];
        }
        this.usedSize--;
        //this.elem[usedSize]=null; 如果數(shù)組當(dāng)中是引用類型，則要將其置為空
    }

清空順序表

清空順序表，只需要把有效長度置于0即可

具體的代碼實(shí)現(xiàn)：

// 清空順序表
    public void clear() {
        this.usedSize = 0;
    }

3.順序表的優(yōu)、缺點(diǎn)

優(yōu)點(diǎn)：由于順序表是物理和邏輯上都連續(xù)的，可以快速查找到當(dāng)前數(shù)據(jù)，時(shí)間復(fù)雜度為O(1)

缺點(diǎn)：

1、刪除和插入數(shù)據(jù)的時(shí)候，都需要移動數(shù)據(jù)，時(shí)間復(fù)雜度為O(N)

2、擴(kuò)容也是問題，增容一般是呈2倍的增長，勢必會有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們再繼續(xù)插入5個(gè)數(shù)據(jù)，無后續(xù)數(shù)據(jù)插入，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間

那么順序表的缺點(diǎn)怎么才能解決呢？鏈表很好的解決了順序表的缺點(diǎn)，隨用隨取，需要空間的時(shí)候就new一個(gè)結(jié)點(diǎn)。需要注意的是，鏈表是物理上不連續(xù)，而邏輯上連續(xù)。

三.順序表的實(shí)現(xiàn)代碼匯總

 
public class MyArrayList {
 
    public int[] elem;
    public int usedSize;
    public MyArrayList() {
        this.elem = new int[5];
    }
 
 
    // 打印順序表
    public void display() {
        for (int i = 0; i <this.usedSize ; i++) {
            System.out.print(elem[i]+" ");
        }
        System.out.println();
    }
 
    // 獲取順序表的有效數(shù)據(jù)長度
    public int size() {
            return usedSize;
    }
 
    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        //1.判斷pos位置是否合法
        if (pos<0 || pos>usedSize){
            System.out.println("pos位置不合法");
            return;
        }
        //2.判斷usedSize是否已滿
        if (isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //3.開始挪數(shù)據(jù),并且給pos位置賦值
        for (int i = usedSize-1; i >= pos ; i--) {
                elem[i+1]=elem[i];//把i下標(biāo)的值給i+1
            }
        this.elem[pos]=data;
        this.usedSize++;//說明存放成功
    }
    public boolean isFull(){
            return this.usedSize == this.elem.length;
    }
 
 
    // 判定是否包含某個(gè)元素
    public boolean contains(int toFind) {
        for (int i = 0; i <this.usedSize ; i++) {
            if (this.elem[i]==toFind)
                return true;
        }
        return false;
    }
 
 
    // 查找某個(gè)元素對應(yīng)的位置
    public int search(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i]==toFind)
                return i;//找到了返回i下標(biāo)
        }
        return -1; //找不到返回-1，因?yàn)閿?shù)組沒有負(fù)數(shù)下標(biāo)
    }
 
 
    // 獲取 pos 位置的元素
    public int getPos(int pos) {
        if (pos<0 || pos>this.usedSize){
            System.out.println("pos位置不合法");
            return -1;//說明pos位置不合法
        }
        if(isEmpty()){
            System.out.println("順序表為空");
            return -1;
        }
        return this.elem[pos];//返回pos位置的值
    }
    public boolean isEmpty(){
        return this.usedSize==0;
    }
 
    // 給 pos 位置的元素設(shè)為/更新為 value
    public void setPos(int pos, int value) {
        //還是要先判斷pos位置的合法性
        if (pos<0 || pos>usedSize){
            System.out.println("pos位置不合法");
            return;
        }
        if(isEmpty()){
            System.out.println("順序表為空");
            return ;
        }
        this.elem[pos] = value;//將pos位置的元素更新為value
    }
 
    //刪除第一次出現(xiàn)的關(guān)鍵字key
    public void remove(int toRemove) {
        if (isEmpty()){
            System.out.println("順序表為空");
            return;
        }
        int index = search(toRemove);
        if (index==-1) {
            System.out.println("沒有你要刪除的數(shù)字");
            return;
        }
        for (int i = index; i < usedSize-1; i++) {
            this.elem[i]=this.elem[i+1];
        }
        this.usedSize--;
        //this.elem[usedSize]=null; 如果數(shù)組當(dāng)中是引用類型，則要將其置為空
    }
 
    // 清空順序表
    public void clear() {
        this.usedSize = 0;
 
    }
 
}

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之順序表篇的文章就介紹到這了,更多相關(guān)Java 順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: