ホームページ > 記事 > Java > Java線形テーブルの逐次表現と実装方法

Java線形テーブルの逐次表現と実装方法

WBOY転載: 2023-05-11 16:28:061735ブラウズ

1. シーケンステーブルとは何ですか?

シーケンシャルテーブルは、コンピュータメモリに配列の形式で保存される線形テーブルです。線形テーブルのシーケンシャルストレージとは、連続したアドレスを持つ一連のストレージユニットを使用して各要素を格納することを意味します。線形テーブル内の論理的に隣接するデータ要素が隣接する物理記憶ユニットに格納されるように、線形テーブルを順番に作成します。つまり、データ要素間の論理的隣接関係が、データ要素の物理的記憶の隣接関係を通じて反映されます。順序の使用記憶構造の線形リストは、多くの場合、シーケンシャルリストと呼ばれます。シーケンステーブルは、テーブル内のノードを、コンピュータメモリ 内の連続したアドレスを持つ一連のストレージユニットに順番に格納します。

2. シーケンステーブルの実装

シーケンステーブルの定義からわかるように、シーケンステーブルは、連続したアドレスを持つ

ストレージユニットのグループです。これは本質的には、いくつかの基本的な操作関数を配列に追加したものです。

この記事で実装する関数は次のとおりです。

##シーケンステーブルが空かどうか
#指定したインデックス位置に要素を追加
##シーケンスリストの最後に要素を追加
##先頭に要素を追加配列リストの
指定したインデックス位置の要素を取得
#配列テーブルの最初の要素を取得
#シーケンステーブルの指定された要素を取得します。インデックス
#指定されたインデックス位置の要素を削除します
シーケンステーブルの最初の要素を削除して返します
シーケンステーブルの最後の要素を削除して返します
#シーケンステーブルの指定要素を削除
シーケンステーブルの動的拡張・拡張を行う縮小
1.準備
#実装ツール

IntelliJ IDEA2021.3JDK1.8

IntelliJ IDEA で新しい通常の Java プロジェクトを作成します

Java線形テーブルの逐次表現と実装方法

新しい Java プロジェクトを作成した後、独自のシーケンステーブルクラスを作成します。ここでは、現在のクラスに Array という名前を付け、ここにジェネリックスを実装します。同時に、Array クラスには 2 つのメンバー属性が必要です:

#データを保存する配列:data、タイプは汎用配列です
現在の数値シーケンステーブル内の要素の数 : size、タイプは int

両方のメンバー属性のアクセス権は # # である必要があります

#プライベート、ユーザーは直接変更できず、対応する getter メソッドを通じてのみ取得できます。メンバ属性には、データの配列とシーケンステーブルの要素数を格納します。は宣言されただけで初期化されていないため、コンストラクタ内で==初期化処理を行う必要があります。 ==

: パラメータを使用して構築を実行する場合、受信パラメータが
int## 型のデータであることを指定するだけで済みます。 #capacity は シーケンステーブルの初期容量 を表すため、data の汎用配列を初期化するだけです。同時に、現在のシーケンステーブルには要素がありません。これは、size の初期値が 0 (シーケンステーブルの要素の数を意味します) であることを意味します。
パラメータなしの構築
パラメータ構築を使用して呼び出しを行うだけです。
注:
Java では汎用配列を直接初期化することはできません。最初に

型の配列を宣言してから、 type through

Conversion メソッドは、Object 型の配列をジェネリック配列

package net.csdn.array;
/**
 * @author zhangrongkang
 * @date 2022/6/26
 */
public class Array<E> {
	/**
	 * 存放数据的数组
	 */
	private E[] data;
    /**
     * 数组中元素的数量
     */
    private int size;
	
	/**
     * 构造函数，传入数组的容量capacity构造数组
     *
     * @param capacity 初始数组大小
     */
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    /**
     * 无参构造函数，默认数组大小为0
     */
    public Array() {
        this(10);
    }
}

ジェネリックスを使用する理由

: ジェネリックスを使用した後、現在のシーケンスをテーブル化できる オブジェクトはオブジェクト内に格納される ジェネリックスを使用しない場合、独自に指定した型のデータしか使用できず、スケーラビリティが強くありません。したがって、ジェネリックスを使用した後は、

現在のシーケンステーブルの使用をすべてのクラスオブジェクト

に拡張することができ、作成時に対応するオブジェクトを指定するだけで済みます。

2. シーケンステーブルの要素数を取得する

    /**
     * 获取数组中的元素个数
     *
     * @return 数组当前的元素个数
     */
    public int getSize() {
        return size;
    }

現在のシーケンステーブルの要素数を取得するには、最初のメンバー変数が size

と定義されているためです。意味は

現在のシーケンステーブルの要素の数

ですが、

size 変数の本質は 現在のシーケンステーブルの次の位置を指すポインタです。シーケンステーブルの最後の要素の (要素のインデックスは 0 から始まり、最後の要素のインデックス値は要素の値より 1 小さい値です) 直接変更することはできないため、## を取得するには#size 要素の場合は、getter メソッドを渡す必要があります。同様に、シーケンステーブル内の要素の数を取得するには、size## を返すだけです。 #3. シーケンステーブルの現在の容量を取得します

    /**
     * 获取数组当前容量
     *
     * @return 数组当前容量
     */
    public int getCapacity() {
        return data.length;
    }

シーケンステーブルを宣言するとき、ユーザーによって渡された初期容量

capacity またはデフォルトが使用されますdata

汎用配列を初期化するための配列のサイズとして、現在の

data

の

length 属性は、渡された capacity になります。 (または、後から動的に容量を拡張または縮小する場合、data.length は変更されません。size のみが変更されます) したがって、シーケンステーブルの現在の容量を取得するには、 # を返すだけです。 ##data.length4. シーケンステーブルは空ですか<pre class="brush:java;"> /** * 判断数组是否为空 * * @return 数组是否为空 */ public boolean isEmpty() { return size == 0; }</pre>size がシーケンステーブル内の要素の数を表すことがわかっているため、現在のシーケンステーブルが空かどうかを判断するには、size が 0 に等しいかどうかを確認するだけで済みます。それを返すだけです。

5. 指定されたインデックス位置に要素を追加します

    /**
     * 向数组中索引为index位置添加元素e
     *
     * @param index 索引位置
     * @param e 元素e
     */
    public void add(int index, E e) {
        // 判断数组空间是否已满
        if (size == data.length) {
            // 对数组进行扩容
            resize(2 * data.length);
        }
        // 越界判断
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

シーケンステーブル内の指定されたインデックス位置に要素を追加するときは、次の問題を考慮する必要があります。

##現在のテーブルにまだ容量があるかどうかシーケンステーブル？

#追加された要素のインデックス値が範囲外ですか?
resize
の機能メソッドは、配列を動的に拡張および縮小します。
resize

2 番目の問題には 2 つの状況しかありません。 インデックスが 0 未満であるか、インデックスがインデックスの要素数を超えています。現在のシーケンステーブル 、実行時例外をスローするだけです。インデックスに問題がなければ、要素を追加するプロセスは次のようになります。<img src="https://img.php.cn/upload/article/000/887/227/168379368922563.png" alt="Java線形テーブルの逐次表現と実装方法"> 要先将要添加的索引位置后的所有元素依次向后移动一位，在移动完成后将当前索引位置的元素使用要进行添加的元素对当前位置的元素进行覆盖即可，同时添加完元素后将<code>size++，维护指针变量

6. 在顺序表末尾添加元素

    /**
     * 在数组末尾添加一个元素
     *
     * @param e 要添加的元素
     */
    public void addLast(E e) {
        add(size, e);
    }

在末尾添加元素可以对之前写好的向指定索引位置添加元素的代码进行复用，同时在add方法中进行了校验，因此对于扩容以及索引都问题都无需我们进行考虑，将索引位置的参数赋值为当前最后一个元素的下一个位置size 后直接调用即可。

7. 在顺序表头部添加元素

    /**
     * 在数组的头部添加元素e
     *
     * @param e 要添加的元素
     */
    public void addFirst(E e) {
        add(0, e);
    }

在顺序表的头部添加元素也是同样的道理，对指定索引位置插入元素进行复用即可，在此不进行赘述。

8. 获取指定索引位置的元素

    /**
     * 获取索引为index位置的元素
     *
     * @param index 索引位置
     * @return 索引为index位置的元素
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return data[index];
    }

获取指定索引位置的元素与之前在指定索引位置插入元素的思路大体一致，但是要更简单一些，无需考虑顺序表扩容以及缩容的问题，仅需要考虑传入的索引值是否合法，如果传入的索引值合法则直接将对应位置的元素进行返回即可。

9. 获取顺序表第一个元素

    /**
     * 获取数组中第一个元素
     *
     * @return 数组中第一个元素
     */
    public E getFirst() {
        return get(0);
    }

在实现了获取指定索引位置的元素后，获取顺序表的第一个元素同样是对get方法的复用，将0做为索引值进行参数传递即可。

10. 获取顺序表最后一个元素

    /**
     * 获取数组中最后一个元素
     *
     * @return 数组中最后一个元素
     */
    public E getLast() {
        return get(size - 1);
    }

获取顺序表最后一个元素也是对get方法的复用，在此不进行赘述

11. 修改指定索引位置的元素

    /**
     * 设置索引为index位置的元素值为e
     *
     * @param index 索引位置
     * @param e 要进行替换的元素值
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        data[index] = e;
    }

在之前获取指定索引位置的元素时，先判断索引是否合法，如果合法将对应位置的元素进行返回。同理，先判断索引位置是否合法，如果合法就将当前位置的元素使用我们接收到的元素e进行替换。

12. 判断顺序表中是否包含指定元素

    /**
     * 判断数组中是否存在元素e
     *
     * @param e 元素e
     * @return 是否存在元素e
     */
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

对于判断顺序表中是否存在指定元素来说，对顺序表进行线性查找，如果找到了相应的数据，就返回true，如果在对顺序表遍历结束后仍然没有找到指定元素，说明当前顺序表中不存在指定元素，返回false

注意：在这里因为是对象的比较，使用equals方法进行比较，如果是基本数据类型（如int，double等）的比较就要使用==来进行比较

13. 获取顺序表中指定元素的索引

    /**
     * 查找数组中元素e的索引，如果不存在返回 -1
     *
     * @param e 元素e
     * @return 元素e在数组中的索引
     */
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

获取指定元素的索引同样使用线性查找法，使用equals进行比较，如果找到相同的元素则返回对应的索引值，如果遍历完顺序表后仍然没有找到指定元素则返回-1，说明当前元素不存在。

14. 删除指定索引位置的元素

    /**
     * 删除索引位置为 index 的元素并返回被删除的元素
     *
     * @param index 删除元素的索引
     * @return 被删除的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        // 先将返回值进行存储
        E res = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null;
        // 如果当前数组中的元素不足数组容量的一半
        if (size < data.length / 2) {
            // 重新分配空间
            resize(data.length / 2);
        }
        return res;
    }

在之前进行元素的添加时要考虑顺序表是否还有容量，在删除元素时不需要考虑是否还有容量，但是也要考虑相应的有关于数组缩容问题。因此要考虑以下问题：

删除当前元素后，顺序表中的元素个数是否不足数组容量的一半？
删除指定索引的元素时，传来的索引值是否合法？

对于第一个问题的解决方法为在删除元素后，对当前顺序表的元素个数与数组的容量的一半进行比较，如果发现当前元素个数小于数组容量的一半时，我们可以继续调用resize方法重新分配数组的容量（resize方法在之后会详细解释），当前的实现结果就是将数组的容量缩容至原数组都一半，对于内存的节省来说更有好处。

第二个问题解决方式与之前处理一样，查看索引值是否小于0以及是否大于等于当前顺序表都元素个数

删除元素的本质也是将当前索引值的后一个元素开始，依次向前移动，覆盖掉前一个元素，最后再将size--，维护指针，删除结束后将临时存储的被删除的元素返回即可。

删除元素过程如下图所示：

Java線形テーブルの逐次表現と実装方法

注意：顺序表的删除本质上是用后一个元素将前一个元素依次覆盖，移动了size指针后此时指针指向的元素仍然为原本顺序表中的最后一个元素，因为在用户的实际操作中，size指向的元素无法被访问到，所以并没有什么影响。但是我们在这里使用了泛型，在Java的GC（垃圾回收机制）中因为此时顺序表的最后一个元素仍然被size指向引用，无法被回收，因此在这里手动执行data[size] = null;将当前的引用回收。

15. 删除并返回顺序表第一个元素

    /**
     * 删除并返回数组的第一个元素
     *
     * @return 数组的第一个元素
     */
    public E removeFirst() {
        return remove(0);
    }

与之前的思路一致，在有了删除指定索引位置的元素方法后，删除并返回顺序表第一个元素也是对刚才实现的remove方法进行复用，在此不做赘述。

16. 删除并返回顺序表最后一个元素

    /**
     * 删除并返回数组中的最后一个元素
     *
     * @return 数组中的最后一个元素
     */
    public E removeLast() {
        return  remove(size - 1);
    }

删除顺序表中最后一个元素同样是对remove方法的复用，在此也不多做赘述。

17. 删除顺序表中的指定元素

    /**
     * 从数组中删除元素e
     *
     * @param e 数组中被删除的元素
     * @return 是否删除成功
     */
    public boolean removeElement(E e) {
       int index = find(e);
       if (index == -1) {
           return false;
       }
       remove(index);
       return true;
    }

删除顺序表中指定的元素本质上是对之前实现的获取顺序表中指定元素的索引方法和删除指定索引位置元素方法的复用，首先通过find方法获取到要删除元素的索引，接着对索引进行判断，查看当前元素是否存在，如果当前元素存在则将获取到的索引值作为remove方法的参数传递，将当前索引位置的元素删除即可。

18. 对顺序表进行动态的扩容和缩容

    /**
     * 对数组进行扩容
     *
     * @param newCapacity 扩容后数组的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

在之前向顺序表中添加元素以及删除顺序表中的元素都涉及到了扩容以及缩容的过程，其实对于扩容以及缩容来说区别只体现在了传递来的参数与原数组容量大小的差别，扩容与缩容的思路都是声明一个新的数组，初始容量的大小为传递来的参数，接着遍历原来的数组，将每一个元素依次填充到新的数组中，之后再将data对象的引用指向新的数组newData即可。

三、运行结果

在进行结果测试前，为了方便于观察，在这里我重写了Array类的toString方法

@Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

Java線形テーブルの逐次表現と実装方法

四、总结

以上便是Java语言对线性表的顺序表示和实现，和以前使用C语言来写顺序表最大的感受就是曾经觉得很难写、很费脑的代码再次实现时感觉变得很容易了，同时对于很多的方法也有了复用的思想，对线性表的理解更加深刻。高兴于自己成长的同时也更加深刻意识到以后的路会更加的艰难，希望自己可以在未来的道路上戒骄戒躁、稳扎稳打，哪怕再困难，也不会放弃！

源码

以下是源代码

1. Array类源代码

package net.csdn.array;
/**
 * @author zhangrongkang
 * @date 2022/6/26
 */
public class Array {
    private E[] data;
    /**
     * 数组中元素的数量
     */
    private int size;

    /**
     * 构造函数，传入数组的容量capacity构造数组
     *
     * @param capacity 初始数组大小
     */
    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    /**
     * 无参构造函数，默认数组大小为0
     */
    public Array() {
        this(10);
    }

    /**
     * 获取数组中的元素个数
     *
     * @return 数组当前的元素个数
     */
    public int getSize() {
        return size;
    }

    /**
     * 获取数组当前容量
     *
     * @return 数组当前容量
     */
    public int getCapacity() {
        return data.length;
    }
    /**
     * 判断数组是否为空
     *
     * @return 数组是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在数组末尾添加一个元素
     *
     * @param e 要添加的元素
     */
    public void addLast(E e) {
        add(size, e);
    }
    /**
     * 在数组的头部添加元素e
     *
     * @param e 要添加的元素
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 向数组中索引为index位置添加元素e
     *
     * @param index 索引位置
     * @param e 元素e
     */
    public void add(int index, E e) {
        // 判断数组空间是否已满
        if (size == data.length) {
            // 对数组进行扩容
            resize(2 * data.length);
        }
        // 越界判断
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }
    /**
     * 获取索引为index位置的元素
     *
     * @param index 索引位置
     * @return 索引为index位置的元素
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return data[index];
    }
    /**
     * 获取数组中第一个元素
     *
     * @return 数组中第一个元素
     */
    public E getFirst() {
        return get(0);
    }

    /**
     * 获取数组中最后一个元素
     *
     * @return 数组中最后一个元素
     */
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 设置索引为index位置的元素值为e
     *
     * @param index 索引位置
     * @param e 要进行替换的元素值
     */
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        data[index] = e;
    }
    /**
     * 判断数组中是否存在元素e
     *
     * @param e 元素e
     * @return 是否存在元素e
     */
    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找数组中元素e的索引，如果不存在返回 -1
     *
     * @param e 元素e
     * @return 元素e在数组中的索引
     */
    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除索引位置为 index 的元素并返回被删除的元素
     *
     * @param index 删除元素的索引
     * @return 被删除的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        // 先将返回值进行存储
        E res = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        data[size] = null;
        // 如果当前数组中的元素不足数组容量的一半
        if (size < data.length / 2) {
            // 重新分配空间
            resize(data.length / 2);
        }
        return res;
    }

    /**
     * 删除并返回数组的第一个元素
     *
     * @return 数组的第一个元素
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 删除并返回数组中的最后一个元素
     *
     * @return 数组中的最后一个元素
     */
    public E removeLast() {
        return  remove(size - 1);
    }
    /**
     * 从数组中删除元素e
     *
     * @param e 数组中被删除的元素
     * @return 是否删除成功
     */
    public boolean removeElement(E e) {
       int index = find(e);
       if (index == -1) {
           return false;
       }
       remove(index);
       return true;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }
    /**
     * 对数组进行扩容
     *
     * @param newCapacity 扩容后数组的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }
}

2. 测试类源代码

package net.csdn.array;

/**
 * @author zhangrongkang
 * @date 2022/6/26
 */
public class ArrayMain {
    public static void main(String[] args) {
        System.out.println("声明新的顺序表，初始容量为10：");
        Array<Integer> array = new Array<>(10);
        for (int i = 0; i < 10; i++) {
            array.addLast(i);
        }
        System.out.println(array + "\n");

        System.out.println("向索引为 1 的位置添加元素 100：");
        array.add(1, 100);
        System.out.println(array + "\n");

        System.out.println("在顺序表的头部添加 -1：");
        array.addFirst(-1);
        System.out.println(array + "\n");

        System.out.println("在顺序表的尾部添加 101：");
        array.addLast(101);
        System.out.println(array + "\n");

        System.out.println("移除索引位置为 2 的元素：");
        array.remove(2);
        System.out.println(array + "\n");

        System.out.println("移除顺序表中的元素 4：");
        array.removeElement(4);
        System.out.println(array + "\n");

        System.out.println("移除顺序表中的第一个元素：");
        array.removeFirst();
        System.out.println(array + "\n");

        System.out.println("移除顺序表中的最后一个元素：");
        array.removeLast();
        System.out.println(array + "\n");

        System.out.println("元素7的索引位置为：" + array.find(7));
        System.out.println("数组中是否包含元素4：" + array.contains(4));
    }

}

以上がJava線形テーブルの逐次表現と実装方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明：

この記事はyisu.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。

前の記事：SpringBoot起動処理 SpringApplicationのソースコード解析次の記事：SpringBoot起動処理 SpringApplicationのソースコード解析

続きを見る

Java線形テーブルの逐次表現と実装方法

1. シーケンステーブルとは何ですか?

現在のシーケンス テーブルの要素の数

data

5. 指定されたインデックス位置に要素を追加します

6. 在顺序表末尾添加元素

7. 在顺序表头部添加元素

8. 获取指定索引位置的元素

9. 获取顺序表第一个元素

10. 获取顺序表最后一个元素

11. 修改指定索引位置的元素

12. 判断顺序表中是否包含指定元素

13. 获取顺序表中指定元素的索引

14. 删除指定索引位置的元素

15. 删除并返回顺序表第一个元素

16. 删除并返回顺序表最后一个元素

17. 删除顺序表中的指定元素

18. 对顺序表进行动态的扩容和缩容

三、运行结果

四、总结

源码

1. Array类源代码

2. 测试类源代码

関連記事

現在のシーケンステーブルの要素の数