天天看點
傳回

使用Java語言實作線性表當中的順序表

作者：Java開發技術分享

文章目錄

  • EmptyException.java(空指針異常)PosWrongfulException.java(越界異常)TestList.java(測試部分)
  • 三. 順序表功能的具體分析
  • 3. 新增元素,在數組最後添加4. 在指定位置插入元素5. 判斷是否包含某個元素6. 查找某個元素所在位置7. 擷取指定位置的元素8. 修改指定位置的元素9. 删除第一次出現的元素key11. 列印順序表(不屬于順序表功能)

一. 線性表中的順序表

線性表（linear list）是n個具有相同特性的資料元素的有限序列。 線性表是一種在實際中廣泛使用的資料結構， 常見的線性表：順序表 、連結清單、棧、隊列…

線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在實體結構上并不一定是連續的，線性表在實體上存儲時，通常以數組和鍊式結構的形式存儲。

使用Java語言實作線性表當中的順序表

順序表是用一段 實體位址連續 的存儲單元依次存儲資料元素的線性結構，一般情況下采用數組存儲。在數組上完成資料的增删查改。

二. 順序表的全局實作

MyArrayLisst.java 

import java.util.Arrays;

public class MyArrayList {
 
    private int[] elem;//數組
    private int usedSize;//記錄有效資料個數
    private static final int DEFAYLT_SIZE = 10;
    //構造方法

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

    // 列印順序表
    //注意：該方法并不是順序表中的方法，為了友善看測試結果給出的
    public void display() {
 
        for (int i = 0; i < this.size(); i++) {
 
            System.out.print(this.elem[i] + " ");
        }
    }
    // 新增元素,預設在數組最後新增
    public void add(int data) {
 
        //1.判斷數組是否滿了
        if(Full()) {
 
            System.out.println("空間滿！");
            //2.滿了進行擴容
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
            System.out.println("擴容完成！");
        }
        //3.将資料放入
        this.elem[this.usedSize] = data;
        //4.更新有效資料個數
        this.usedSize++;
    }
    //1.
    public boolean Full() {
 
        return this.size() >= this.elem.length;
    }
    // 在 pos 位置新增元素
    public void add(int pos, int data) throws PosWrongfulException{
 
        //1.判斷數組是否滿了
        if(Full()) {
 
            System.out.println("空間滿！");
            //2.滿了進行擴容
            this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
            System.out.println("擴容完成！");
        }
        //判斷pos位置是否合法，不合法抛出異常
        if(pos < 0 || pos > this.usedSize) {
 
            //抛出自定義異常,要注意去聲明異常以便繼續抛出
            throw new PosWrongfulException("add參數中，pos位置不合法");
        }
        //pos合法，從pos位置開始的元素向都後挪一個位置，讓pos位置空出來
        for (int i = this.usedSize; i >= pos; i--) {
 
            this.elem[i+1] = this.elem[i];
        }
        //在pos位置插入資料
        this.elem[pos] = data;
        //更新有效資料個數
        this.usedSize++;
    }
    // 判定是否包含某個元素
    public boolean contains(int toFind) {
 
        for (int i = 0; i < this.usedSize; i++) {
 
            if(elem[i] == toFind)
                return true;
        }
        return false;
    }
    // 查找某個元素對應的位置
    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("目前順序表為空！");
        }
        //判斷pos是否合法
        if(pos < 0 || pos >= this.usedSize) {
 
            //抛出自定義異常,要注意去聲明異常以便繼續抛出
            throw new PosWrongfulException("get擷取元素時，pos位置不合法");
        }
        return this.elem[pos];
    }
    public boolean isEmpty() {
 
        return this.size() == 0;
    }
    // 給 pos 位置的元素設為 value
    public void set(int pos, int value) {
 
        //判斷順序表是否為空
        if(isEmpty()) {
 
            throw new EmptyException("目前順序表為空！");
        }
        //判斷pos是否合法
        if(pos < 0 || pos >= this.usedSize) {
 
            //抛出自定義異常,要注意去聲明異常以便繼續抛出
            throw new PosWrongfulException("set設定元素時，pos位置不合法");
        }
        this.elem[pos] = value;

    }
    //删除第一次出現的關鍵字key
    public void remove(int toRemove) {
 
        //判斷順序表是否為空
        if(isEmpty()) {
 
            throw new EmptyException("目前順序表為空！");
        }
        //查找要删除元素的位置
        int index = this.indexOf(toRemove);
        if(index == -1) {
 
            System.out.println("沒有你要删除的元素"+toRemove);
            return;
        }
        //删除元素，從後往前進行覆寫
        for (int i = index; i < this.size(); i++) {
 
            this.elem[i] = this.elem[i+1];
        }
        //更新有效資料個數
        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("删除第一次出現的數值");
        myArrayList.remove(3);
        myArrayList.remove(999);
        myArrayList.display();
        System.out.println();

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

測試結果

使用Java語言實作線性表當中的順序表
使用Java語言實作線性表當中的順序表

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

1. 順序表的定義

順序表本質上是基于數組進行操作的, 是以順序表成員中定義一個數組elem來存放資料, 這裡的順序表實作以整形為例, 順序表中的元素可以是其他類型,實作方法類似.

定義變量usedSize用來記錄順序表中的元素個數; 定義常量并給出構造方法以友善在建立順序表時給數組配置設定預設空間.

public class MyArrayList {
 
    private int[] elem;//數組
    private int usedSize;//記錄有效資料個數
    private static final int DEFAYLT_SIZE = 10;
    
    //構造方法
    public MyArrayList() {
 
        this.elem = new int[DEFAYLT_SIZE];
    }
}

2. 擷取順序表長度

擷取順序表中記錄數組中有效資料個數的成員即可

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

3. 新增元素,在數組最後添加

在添加元素前要判斷數組空間是否滿了, 如果滿了要先進行擴容然後再添加, 添加成功後要記得更新資料的有效個數

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

4. 在指定位置插入元素

先判斷數組空間是不是滿了, 然後判斷要插入位置的法性, 注意插入資料隻能在以經存放了數劇的範圍内進行插入, 也就是插入的位置相鄰位置要有元素, 不能空着插;

如果位置不合法, 為了使出現問題的地方更突出以便于追蹤和解決問題, 我們可以讓報異常來達到目的, 我們去自定義異常, 如果位置不合法抛出異常, 讓程式進行捕獲和處理.

添加成功後要記得更新資料的有效個數, 異常的實作在上文中已經給出.

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

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

周遊數組将每個元素逐一比較即可

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

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

周遊數組比較即可

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

7. 擷取指定位置的元素

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

上面兩個條件都沒問題的話就可以通過下标去擷取元素了

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

8. 修改指定位置的元素

和6中的代碼屬于一份代碼, 在最後将擷取元素傳回改為指派即可

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

    }

9. 删除第一次出現的元素key

判斷順序表是否為空, 不為空則先找到要删除元素的位置, 将key之後的元素逐一往前覆寫, 将key覆寫便達到了删除的效果; 最後要記得元素的有效個數要減1;

需要注意的是,這裡删除的基本資料類型的資料, 删除後相對于删除前數組的最後一個位置, 雖然那個位置還留有原來的值, 但這個值不置為0并不會有什麼影響;

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

public void remove(int toRemove) {
 
        //判斷順序表是否為空
        if(isEmpty()) {
 
            throw new EmptyException("目前順序表為空！");
        }
        //查找要删除元素的位置
        int index = this.indexOf(toRemove);
        if(index == -1) {
 
            System.out.println("沒有你要删除的元素"+toRemove);
            return;
        }
        //删除元素，從後往前進行覆寫
        for (int i = index; i < this.size(); i++) {
 
            this.elem[i] = this.elem[i+1];
        }
        //更新有效資料個數
        this.usedSize--;
    }

10. 清空順序表

将數組的有效元素個數指派為0即可;

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

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

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

周遊數組列印即可, 要注意的是順序表中是沒有這個功能的, 隻是為了測試, 友善觀察調試所設.

public void display() {
 
        for (int i = 0; i < this.size(); i++) {
 
            System.out.print(this.elem[i] + " ");
        }
    }
上一篇: golang筆記11--go語言并發程式設計子產品 channel
下一篇: 為什麼基于樹的模型在表格資料上仍然優于深度學習