アルゴリズムを理解するパート 2 - シーケンステーブル

[[407946]]

この記事はWeChatの公開アカウント「Front-end Gravitation」から転載したもので、著者はYichuanです。この記事を転載する場合は、Frontend Gravity の公開アカウントにご連絡ください。

序文

開発において、配列はよく扱うデータ型ですが、その内部の格納構造はどうなっているのでしょうか？詳しく紹介します。

リニアテーブル

線形リストは、最も基本的かつ最も単純で、最も一般的に使用されるデータ構造です。線形リストは、同じ特性を持つ n 個のデータ要素の順序付けられたシーケンスです。

先行要素: 要素 A が要素 B の前に来る場合、A は B の先行要素と呼ばれます。

後続要素: 要素 B が要素 A の後にある場合、B は A の後続要素と呼ばれます。

線形テーブルの分類: 線形テーブル内のデータ保存方法は、シーケンシャル保存とリンク保存に分けられます。

シーケンシャルストレージは、連続したアドレスを持つ一連のストレージユニットを使用して、線形リストのデータ要素を順番に格納します。
チェーンストレージとは、不連続なアドレスを持つストレージユニットにデータを保存し、ノードを使用してアドレスを接続して照会することです。

ランダムアクセス: 線形リストは連続したメモリ位置に格納されるため、インデックスを通じてメモリアドレスを計算し、データにランダムにアクセスできます。

シーケンステーブル

シーケンシャルリストの格納方法は、実際にはメモリ内の空き位置を見つけてそこを占有し、その空き位置にデータ要素を 1 つずつ格納するというものです。

配列の構造に少し似ているように聞こえますか? はい、データは線形テーブル構造です。したがって、配列を使用して連続リストを表すことができます。線形リスト内の論理的に隣接するデータ要素は、隣接する物理ストレージユニットに格納されます。つまり、データ要素間の論理的な隣接関係は、データ要素の物理ストレージの隣接関係によって反映されます。

配列の長さは線形リストのストレージスペースの長さであり、この量は通常、ストレージの割り当て後も変更されません。線形リストの長さは、線形リスト内のデータ要素の数です。この量は、線形リスト内で挿入および削除操作が実行されるたびに変化します。覚えておいてください、線形リストの長さは常に配列の長さ以下である必要があります。

クラスSequenceList{ 
  
  コンストラクタ（）{
    // 要素を格納する配列
    this.elemList = [];
    // 現在のシーケンスリスト内の要素数
    this.elemLength = 0;
  }
  // 線形テーブルを空のテーブルに設定する
  クリア（）{
    this.elemLength = 0;
  }
  // 現在の線形テーブルが空のテーブルかどうかを判定します
  空です(){
 this.elemLength === 0を返します。
  }
  // 現在の線形テーブルの長さを取得します
  長さ（）{
 this.elemLengthを返します。
  }
  // 線形リストに要素を追加する
挿入(要素){
    this.elemList[this.elemLength++] = elem;
  } 
 
  // i番目の要素に要素 elem を挿入する
  挿入インデックス(i,要素){
    // まず、インデックス位置 i の要素とそれ以降の要素を 1 つずつ後方に移動します
for (let index = this.elemLength - 1; index > i; index --) {  
      this.elemList[インデックス] = this.elemList[インデックス-1];
    }
    // インデックス位置 i の elem 要素を格納します
    this.elemList[i] = elem;
  } 
 
  // 指定された位置iの要素を削除した後、要素を返す
  削除(i){
    //インデックス i の値を記録する
    現在のものを this.elemList[i] とします。
    // インデックス i の後の要素を 1 つずつ前方に移動します
for (let index = i; index < this.elemList - 1; index ++) {
      this.elemList[インデックス] = this.elemList[インデックス+1];
    }
    // 要素数 - 1
    this.elemLength --;  
戻る 現在;
  } 
 
  // シーケンスリスト内の elem 要素の最初の位置を検索します
  インデックスOf(要素){
 ( i = 0 とします; i< this.elemLength; i++){
      if (this.elemList[i] === elem) {
 iを返します。
      }
 -1 を返します。
    }
  }
 }

配列の利点と欠点

アドバンテージ：

メモリスペースの高利用率
要素のインデックスによるアクセス、要素のクエリの効率が高い

欠点:

要素の挿入と削除は非効率的です。 (配列の途中で要素を挿入または削除する場合は、要素を操作して順序を変更する前に、テーブル全体を移動する必要があります)
スペースの長さには制限があり、線形テーブルの長さを拡張することはできません。 (アクセス要素の長さがシーケンスリスト内の要素数より大きい場合、「オーバーフロー」が発生します。要素の長さが事前に割り当てられたスペースより小さい場合、スペースが大幅に無駄になります)