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

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

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

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

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

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

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

配列の数を取得します。シーケンス テーブル内の要素
シーケンス テーブルの現在の容量を取得します

• ##シーケンス テーブルが空かどうか

• #指定したインデックス位置に要素を追加

• ##シーケンスリストの最後に要素を追加

• ##先頭に要素を追加配列リストの

• 指定したインデックス位置の要素を取得

• #配列テーブルの最初の要素を取得

##シーケンス テーブルの最後の要素を取得します
指定されたインデックス位置にある要素を変更します
シーケンスがテーブルに指定された要素が含まれています

• #シーケンス テーブルの指定された要素を取得します。インデックス

• #指定されたインデックス位置の要素を削除します

• シーケンス テーブルの最初の要素を削除して返します

• シーケンス テーブルの最後の要素を削除して返します

• #シーケンステーブルの指定要素を削除

• シーケンステーブルの動的拡張・拡張を行う縮小

• 1.準備

• #実装ツール

バージョン

IntelliJ IDEA2021.3JDK1.8

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

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

• #データを保存する配列:data、タイプは汎用配列です

• 現在の数値シーケンス テーブル内の要素の数 : size、タイプは int

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

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

パラメータを使用した構築
• : パラメータを使用して構築を実行する場合、受信パラメータが

  int## 型のデータであることを指定するだけで済みます。 #capacity は シーケンス テーブルの初期容量 を表すため、data の汎用配列を初期化するだけです。同時に、現在のシーケンス テーブルには要素がありません。これは、size の初期値が 0 (シーケンス テーブルの要素の数を意味します) であることを意味します。

  パラメータなしの構築
: ユーザーがシーケンス テーブルの初期容量を指定しない場合、## を渡すだけで初期容量を 10 にカスタマイズできます。 #this( 10)
• パラメータ構築を使用して呼び出しを行うだけです。

  注:

  Java では汎用配列を直接初期化することはできません。最初に
Object

型の配列を宣言してから、 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. シーケンス テーブルは空ですか<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class='brush:php;toolbar:false;'> /** * 判断数组是否为空 * * @return 数组是否为空 */ public boolean isEmpty() { return size == 0; }</pre><div class="contentsignin">ログイン後にコピー</div></div>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
メソッドの実装については、後ほど詳しく説明します。ここで、現在のシーケンス テーブルの容量がフルの場合、expand することがわかります。シーケンス テーブルの容量を現在のシーケンス テーブルの容量の 2 倍にします。

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

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

注意：顺序表的删除本质上是用后一个元素将前一个元素依次覆盖，移动了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语言对线性表的顺序表示和实现，和以前使用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 サイトの他の関連記事を参照してください。