Java數(shù)據(jù)結(jié)構(gòu)之順序表的實(shí)現(xiàn)

更新時間：2022年09月21日 14:11:33 作者：XIN-XIANG榮

線性表（linear?list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。?線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，本文將用Java實(shí)現(xiàn)順序表，感興趣的可以了解一下

1. 順序表的定義
2. 獲取順序表長度
3. 新增元素,在數(shù)組最后添加
4. 在指定位置插入元素
5. 判斷是否包含某個元素
6. 查找某個元素所在位置
7. 獲取指定位置的元素
8. 修改指定位置的元素
9. 刪除第一次出現(xiàn)的元素key
10. 清空順序表
11. 打印順序表(不屬于順序表功能)

一. 線性表中的順序表

線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列…

線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。

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

二. 順序表的全局實(shí)現(xiàn)

MyArrayLisst.java

import java.util.Arrays;

public class MyArrayList {
    private int[] elem;//數(shù)組
    private int usedSize;//記錄有效數(shù)據(jù)個數(shù)
    private static final int DEFAYLT_SIZE = 10;
    //構(gòu)造方法

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

    // 打印順序表
    //注意：該方法并不是順序表中的方法，為了方便看測試結(jié)果給出的
    public void display() {
        for (int i = 0; i < this.size(); i++) {
            System.out.print(this.elem[i] + " ");
        }
    }
    // 新增元素,默認(rèn)在數(shù)組最后新增
    public void add(int data) {
        //1.判斷數(shù)組是否滿了
        if(Full()) {
            System.out.println("空間滿！");
            //2.滿了進(jìn)行擴(kuò)容
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
            System.out.println("擴(kuò)容完成！");
        }
        //3.將數(shù)據(jù)放入
        this.elem[this.usedSize] = data;
        //4.更新有效數(shù)據(jù)個數(shù)
        this.usedSize++;
    }
    //1.
    public boolean Full() {
        return this.size() >= this.elem.length;
    }
    // 在 pos 位置新增元素
    public void add(int pos, int data) throws PosWrongfulException{
        //1.判斷數(shù)組是否滿了
        if(Full()) {
            System.out.println("空間滿！");
            //2.滿了進(jìn)行擴(kuò)容
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
            System.out.println("擴(kuò)容完成！");
        }
        //判斷pos位置是否合法，不合法拋出異常
        if(pos < 0 || pos > this.usedSize) {
            //拋出自定義異常,要注意去聲明異常以便繼續(xù)拋出
            throw new PosWrongfulException("add參數(shù)中，pos位置不合法");
        }
        //pos合法，從pos位置開始的元素向都后挪一個位置，讓pos位置空出來
        for (int i = this.usedSize; i >= pos; i--) {
            this.elem[i+1] = this.elem[i];
        }
        //在pos位置插入數(shù)據(jù)
        this.elem[pos] = data;
        //更新有效數(shù)據(jù)個數(shù)
        this.usedSize++;
    }
    // 判定是否包含某個元素
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(elem[i] == toFind)
                return true;
        }
        return false;
    }
    // 查找某個元素對應(yīng)的位置
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(elem[i] == toFind)
                return i;
        }
        return -1;
    }
    // 獲取 pos 位置的元素
    public int get(int pos) throws EmptyException{
        //判斷順序表是否為空
        if(isEmpty()) {
            throw new EmptyException("當(dāng)前順序表為空！");
        }
        //判斷pos是否合法
        if(pos < 0 || pos >= this.usedSize) {
            //拋出自定義異常,要注意去聲明異常以便繼續(xù)拋出
            throw new PosWrongfulException("get獲取元素時，pos位置不合法");
        }
        return this.elem[pos];
    }
    public boolean isEmpty() {
        return this.size() == 0;
    }
    // 給 pos 位置的元素設(shè)為 value
    public void set(int pos, int value) {
        //判斷順序表是否為空
        if(isEmpty()) {
            throw new EmptyException("當(dāng)前順序表為空！");
        }
        //判斷pos是否合法
        if(pos < 0 || pos >= this.usedSize) {
            //拋出自定義異常,要注意去聲明異常以便繼續(xù)拋出
            throw new PosWrongfulException("set設(shè)置元素時，pos位置不合法");
        }
        this.elem[pos] = value;

    }
    //刪除第一次出現(xiàn)的關(guān)鍵字key
    public void remove(int toRemove) {
        //判斷順序表是否為空
        if(isEmpty()) {
            throw new EmptyException("當(dāng)前順序表為空！");
        }
        //查找要刪除元素的位置
        int index = this.indexOf(toRemove);
        if(index == -1) {
            System.out.println("沒有你要刪除的元素"+toRemove);
            return;
        }
        //刪除元素，從后往前進(jìn)行覆蓋
        for (int i = index; i < this.size(); i++) {
            this.elem[i] = this.elem[i+1];
        }
        //更新有效數(shù)據(jù)個數(shù)
        this.usedSize--;
    }
    // 獲取順序表長度
    public int size() {
       return this.usedSize;
    }
    // 清空順序表
    public void clear() {
        this.usedSize = 0;
    }
}

EmptyException.java(空指針異常)

public class EmptyException extends RuntimeException{
    public EmptyException() {
    }

    public EmptyException(String message) {
        super(message);
    }
}

PosWrongfulException.java(越界異常)

public class EmptyException extends RuntimeException{
    public EmptyException() {
    }

    public EmptyException(String message) {
        super(message);
    }
}

TestList.java(測試部分)

public class TestList {
    public static void main(String[] args) {
        MyArrayList myArrayList = new MyArrayList();

        System.out.println("在順序表最后一個位置添加元素");
        myArrayList.add(1);
        myArrayList.add(2);
        myArrayList.add(3);
        myArrayList.add(4);
        myArrayList.display();
        System.out.println();

        System.out.println("插入元素");
        try {
            myArrayList.add(0,6);
            myArrayList.add(6,10);
        } catch (PosWrongfulException e) {
            e.printStackTrace();
        }
        myArrayList.display();
        System.out.println();

        System.out.println("順序表是否包含某個元素");
        System.out.println(myArrayList.contains(2));
        System.out.println(myArrayList.contains(66));

        System.out.println("獲取元素位置");
        System.out.println(myArrayList.indexOf(3));
        System.out.println(myArrayList.indexOf(88));

        System.out.println("獲取pos位置的元素");
        try {
            System.out.println(myArrayList.get(1));
            System.out.println(myArrayList.get(10));
        }catch (PosWrongfulException e) {
            e.printStackTrace();
        }

        System.out.println("更改pos位置的元素值");
        try {
            myArrayList.set(0,99);
            myArrayList.set(10,10);
        }catch (PosWrongfulException e) {
            e.printStackTrace();
        }
        myArrayList.display();
        System.out.println();

        System.out.println("刪除第一次出現(xiàn)的數(shù)值");
        myArrayList.remove(3);
        myArrayList.remove(999);
        myArrayList.display();
        System.out.println();

        System.out.println("清空順序表后再添加一個元素");
        myArrayList.clear();
        myArrayList.add(666);
        myArrayList.display();
    }
}

測試結(jié)果

三. 順序表功能的具體分析

1. 順序表的定義

順序表本質(zhì)上是基于數(shù)組進(jìn)行操作的, 所以順序表成員中定義一個數(shù)組elem來存放數(shù)據(jù), 這里的順序表實(shí)現(xiàn)以整形為例, 順序表中的元素可以是其他類型,實(shí)現(xiàn)方法類似.

定義變量usedSize用來記錄順序表中的元素個數(shù); 定義常量并給出構(gòu)造方法以方便在創(chuàng)建順序表時給數(shù)組分配默認(rèn)空間.

public class MyArrayList {
    private int[] elem;//數(shù)組
    private int usedSize;//記錄有效數(shù)據(jù)個數(shù)
    private static final int DEFAYLT_SIZE = 10;
    
    //構(gòu)造方法
    public MyArrayList() {
        this.elem = new int[DEFAYLT_SIZE];
    }
}

2. 獲取順序表長度

獲取順序表中記錄數(shù)組中有效數(shù)據(jù)個數(shù)的成員即可

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

3. 新增元素,在數(shù)組最后添加

在添加元素前要判斷數(shù)組空間是否滿了, 如果滿了要先進(jìn)行擴(kuò)容然后再添加, 添加成功后要記得更新數(shù)據(jù)的有效個數(shù)

public void add(int data) {
        //1.判斷數(shù)組是否滿了
        if(Full()) {
            System.out.println("空間滿！");
            //2.滿了進(jìn)行擴(kuò)容
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
            System.out.println("擴(kuò)容完成！");
        }
        //3.將數(shù)據(jù)放入
        this.elem[this.usedSize] = data;
        //4.更新有效數(shù)據(jù)個數(shù)
        this.usedSize++;
    }
    //1.
    public boolean Full() {
        return this.size() >= this.elem.length;
    }

4. 在指定位置插入元素

先判斷數(shù)組空間是不是滿了, 然后判斷要插入位置的法性, 注意插入數(shù)據(jù)只能在以經(jīng)存放了數(shù)劇的范圍內(nèi)進(jìn)行插入, 也就是插入的位置相鄰位置要有元素, 不能空著插;

如果位置不合法, 為了使出現(xiàn)問題的地方更突出以便于追蹤和解決問題, 我們可以讓報(bào)異常來達(dá)到目的, 我們?nèi)プ远x異常, 如果位置不合法拋出異常, 讓程序進(jìn)行捕獲和處理.

添加成功后要記得更新數(shù)據(jù)的有效個數(shù), 異常的實(shí)現(xiàn)在上文中已經(jīng)給出.

public void add(int pos, int data) throws PosWrongfulException{
        //1.判斷數(shù)組是否滿了
        if(Full()) {
            System.out.println("空間滿！");
            //2.滿了進(jìn)行擴(kuò)容
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
            System.out.println("擴(kuò)容完成！");
        }
        //判斷pos位置是否合法，不合法拋出異常
        if(pos < 0 || pos > this.usedSize) {
            //拋出自定義異常,要注意去聲明異常以便繼續(xù)拋出
            throw new PosWrongfulException("add參數(shù)中，pos位置不合法");
        }
        //pos合法，從pos位置開始的元素向都后挪一個位置，讓pos位置空出來
        for (int i = this.usedSize; i >= pos; i--) {
            this.elem[i+1] = this.elem[i];
        }
        //在pos位置插入數(shù)據(jù)
        this.elem[pos] = data;
        //更新有效數(shù)據(jù)個數(shù)
        this.usedSize++;
    }

5. 判斷是否包含某個元素

遍歷數(shù)組將每個元素逐一比較即可

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

6. 查找某個元素所在位置

遍歷數(shù)組比較即可

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

7. 獲取指定位置的元素

如果順序表中沒有存放元素的話是不能去獲取元素的, 這里同樣可以去聲明一個異常去解決問題; 同時要判斷位置的合法性,

上面兩個條件都沒問題的話就可以通過下標(biāo)去獲取元素了

public int get(int pos) throws EmptyException{
        //判斷順序表是否為空
        if(isEmpty()) {
            throw new EmptyException("當(dāng)前順序表為空！");
        }
        //判斷pos是否合法
        if(pos < 0 || pos >= this.usedSize) {
            //拋出自定義異常,要注意去聲明異常以便繼續(xù)拋出
            throw new PosWrongfulException("get獲取元素時，pos位置不合法");
        }
        return this.elem[pos];
    }

8. 修改指定位置的元素

和6中的代碼屬于一份代碼, 在最后將獲取元素返回改為賦值即可

public void set(int pos, int value) {
        //判斷順序表是否為空
        if(isEmpty()) {
            throw new EmptyException("當(dāng)前順序表為空！");
        }
        //判斷pos是否合法
        if(pos < 0 || pos >= this.usedSize) {
            //拋出自定義異常,要注意去聲明異常以便繼續(xù)拋出
            throw new PosWrongfulException("set設(shè)置元素時，pos位置不合法");
        }
        this.elem[pos] = value;

???????    }

9. 刪除第一次出現(xiàn)的元素key

判斷順序表是否為空, 不為空則先找到要刪除元素的位置, 將key之后的元素逐一往前覆蓋, 將key覆蓋便達(dá)到了刪除的效果; 最后要記得元素的有效個數(shù)要減1;

需要注意的是,這里刪除的基本數(shù)據(jù)類型的數(shù)據(jù), 刪除后相對于刪除前數(shù)組的最后一個位置, 雖然那個位置還留有原來的值, 但這個值不置為0并不會有什么影響;

而如果順序表中放置的是引用類型, 此時這個位置必須置空(置為null), 否則會有內(nèi)存泄漏的問題存在.

public void remove(int toRemove) {
        //判斷順序表是否為空
        if(isEmpty()) {
            throw new EmptyException("當(dāng)前順序表為空！");
        }
        //查找要刪除元素的位置
        int index = this.indexOf(toRemove);
        if(index == -1) {
            System.out.println("沒有你要刪除的元素"+toRemove);
            return;
        }
        //刪除元素，從后往前進(jìn)行覆蓋
        for (int i = index; i < this.size(); i++) {
            this.elem[i] = this.elem[i+1];
        }
        //更新有效數(shù)據(jù)個數(shù)
        this.usedSize--;
    }

10. 清空順序表

將數(shù)組的有效元素個數(shù)賦值為0即可;

同樣的, 要注意如果順序表中的元素是引用類型的話, 要將數(shù)組中的每個元素都置為null.

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

11. 打印順序表(不屬于順序表功能)

遍歷數(shù)組打印即可, 要注意的是順序表中是沒有這個功能的, 只是為了測試, 方便觀察調(diào)試所設(shè).

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

以上就是Java數(shù)據(jù)結(jié)構(gòu)之順序表的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于Java順序表的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片