技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

リニアテーブル

私たちは話したいですシーケンステーブル逐次テーブルは線形テーブルの一種であるため、最初に線形テーブルについて説明する必要があります。

線形テーブルの定義

名前が示すように、線形テーブルはデータを線のように構成したテーブルです。
それは現実に並ぶことを考えれば分かります。

線形テーブルの特徴:

• 線形テーブルのデータ要素間には順序があります。
• 最初の要素と最後の要素を除き、すべての要素には先行要素と後続要素があります。

シーケンステーブル

シーケンステーブルは段落を使用します物理アドレスは連続している保管ユニットは、人が隣り合って並んでいるようなものです。
データ要素を順番に格納する線形構造。通常は次を使用します。配列ストレージ。
アレイ上のデータの追加、削除、確認、変更を完了します。

シーケンステーブルインターフェースの実装

シーケンス テーブルを自分で実装します (ストレージ int 型データ)。シーケンス テーブルをクラスとして使用し、いくつかのインターフェイスを実装します。メンバーメソッドデータの追加、削除、確認、変更を実現します。

public class SeqList {
     private int[] elem;
     private int usedSize;
     // 默认构造方法
     SeqList(){   }
     // 将顺序表的底层容量设置为initcapacity
     SeqList(int initcapacity){   }
     // 新增元素,默认在数组最后新增
     public void add(int data) { }
     // 在 pos 位置新增元素
     public void add(int pos, int data) { }
     // 判定是否包含某个元素
     public boolean contains(int toFind) { return true; }
     // 查找某个元素对应的位置
     public int indexOf(int toFind) { return -1; }
     // 获取 pos 位置的元素
     public int get(int pos) { return -1; }
     // 给 pos 位置的元素设为 value
     public void set(int pos, int value) {   }
     //删除第一次出现的关键字key
     public void remove(int toRemove) {   }
     // 获取顺序表长度
     public int size() { return 0; }
     // 清空顺序表
     public void clear() {   }
     
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

デフォルトのコンストラクター

デフォルトでは、最初に 10 個のデータスペースを開きます。

private static final int DEFAULT_SIZE = 10;
    public SeqList() {
        this.elem= new int[DEFAULT_SIZE];
    }
1
2
3
4

シーケンス テーブルの基礎となる容量を initcapacity に設定します。

配列の長さを渡し、配列の長さを使用してスペースを空けます。

private static final int DEFAULT_SIZE = 10;
    public SeqList(int initcapacity) {
        this.elem= new int[initcapacity];
    }
1
2
3
4

テールプラグ

デフォルトでは、新しい要素は配列の最後に追加されます。
考慮すべき点:

• 現在のシーケンス テーブルがいっぱいかどうかを確認し、いっぱいの場合はスペースを追加します。
• 要素が追加され、usedSize が 1 増加します。

 public void add(int data) {
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length * 2);
        }
        elem[usedSize++] = data;
    }
     /**
     * 判断当前的顺序表是不是满的！
     *
     * @return true:满   false代表空
     */
    private boolean isFull() {
        return usedSize == elem.length;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

pos 位置に要素を追加

pos 添字に要素を挿入します。
予防：

• 現在のシーケンス テーブルがいっぱいかどうかを確認し、いっぱいの場合はスペースを追加します。
• 指定された pos 位置は正当ですか? そうでない場合は、例外がスローされます。
• 後方から前方へのループを使用して、pos 位置の後の要素を後方に移動します。
• 要素が追加され、usedSize が 1 増加します。

private boolean checkPosInAdd(int pos) throws PosIllegalException{

        if(pos < 0 || pos > usedSize){
            throw new PosIllegalException("位置不合法");
        }
        return true;
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) {
        try{
            if(checkPosInAdd(pos)){
                if(isFull()){
                    elem = Arrays.copyOf(elem,elem.length * 2);
                }
                for (int i = usedSize; i > pos ; i--) {
                    elem[i] = elem[i-1];
                }
                elem[pos] = data;
                usedSize++;
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

要素が含まれているかどうかを判断する

指定されたデータがシーケンス テーブルに含まれているかどうかを確認します。
直接ループして、見つかった場合は true を返し、見つからない場合は false を返します。

public boolean contains(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8

要素に対応する位置を見つける

このシーケンス テーブル内の指定されたデータのインデックスを確認します。
直接ループして、-1 を返さずに戻り添字を見つけます。

public int indexOf(int toFind) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8

pos 位置の要素を取得します

pos 位置の要素を出力します。
予防：

• posが合法かどうかを確認する

public int get(int pos) {
        try{
            if(checkPosInAdd(pos)){
                return elem[pos];
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }
        return 0;
    }
1
2
3
4
5
6
7
8
9
10

位置 pos の要素を value に設定します

pos 位置要素を変更します。
予防：

• posが合法かどうかを確認してください。

public void set(int pos, int value) {
        try{
            if(checkPosInAdd(pos)){
                elem[pos] = value;
            }
        }catch(PosIllegalException e){
            e.printStackTrace();
        }
    }
1
2
3
4
5
6
7
8
9

最初に出現したキーワード キーを削除します

最初に出現したキーを削除します。
予防：

• 検索をループします。
• 見つかったキーの後の要素を使用して、前に向かって 1 つずつカバーします。
• usedSize が 1 減少します。

public void remove(int key) {
        for (int i = 0; i < usedSize; i++) {
            if(elem[i] == key){
                for (int j = i; j < usedSize - 1; j++) {
                    elem[j] = elem[j + 1];
                }
                usedSize--;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10

シーケンステーブルの長さを取得する

ここでシーケンステーブルの長さを求めるとは、有効なデータの数、すなわちusedSizeを指す。

public int size() {
        return usedSize;
    }
1
2
3

シーケンスリストをクリアする

シーケンステーブルの内容を空に設定します。
予防：

• 実際のシーケンシャル テーブルにはジェネリックが格納されているため、要素は 1 つずつ走査されると空に設定され、以下のように 0 に設定されて置き換えられます。
• UsedSize も 0 に設定されます。

public void clear() {
        for (int i = 0; i < usedSize; i++) {
            elem[i] = 0;
        }
        usedSize = 0;
    }
1
2
3
4
5
6

JavaのArrayList

ArrayList クラスは、順次リストを表すために Java で提供されます。

実装されたインターフェース

インターフェースの説明:

1. RandomAccess インターフェイスは、ランダム アクセスのサポートを示します。
2. Cloneable インターフェイスは、クローン作成のサポートを示します。
3. Serializable インターフェイスは、シリアル化のサポートを示します。

施工方法

Java には、表に示す 3 つの構築メソッドが用意されています。

一般的な方法

提供される一般的なメソッドは、上で実装したものと似ています。

シーケンスリストの長所と短所

アドバンテージ

シーケンス テーブルの利点は次のとおりです。

1. ランダムアクセスがサポートされています。
2. 指定された添字のクエリは高速です。

欠点がある

1. 十分なスペースがない場合は拡張する必要があり、メモリが無駄に消費されます。
2. ヘッダーと中間の挿入と削除によりデータが移動されます。

練習する

演習へのリンクは以下のとおりです。
ヤン・フイ・トライアングル