JavaScriptにはデータ構造がありますか?-フロントエンドQ&A-php.cn

JavaScript にはデータ構造があります。データ構造とは、相互に 1 つ以上の特定の関係を持つデータ要素のコレクションを指します。データ構造により、データオブジェクトを効果的に管理し、コンピューティングパフォーマンスを向上させることができます。JavaScript のデータ構造はこちらリスト、スタック、キュー、リンクリスト、辞書、ハッシュ、グラフ、二分探索ツリーです。

JavaScriptにはデータ構造がありますか?

このチュートリアルの動作環境: Windows 10 システム、JavaScript バージョン 1.8.5、Dell G3 コンピューター。

JavaScript にはデータ構造がありますか?

JavaScript にはデータ構造があります

データ構造: リスト、スタック、キュー、リンクリスト、辞書、ハッシュ、グラフ、二分探索木

#リスト

日常生活では、人々はTo-Doリスト、買い物リスト、ベストリストなどのリストをよく使用します。トップ 10 リストなど。コンピュータープログラムでもリストが使用されます。選択リストは、次の条件下でデータ構造として特に役立ちます:

データ構造が比較的単純である

長いシーケンスで要素を見つける必要がない、または並べ替えてください

逆に、データ構造が非常に複雑な場合、リストの役割はそれほど大きくありません。

スタック

スタックは特別な種類のリストであり、スタック内の要素にはリストの一方の端からのみアクセスできます。この端はスタックトップと呼ばれます。私たちがレストランでよく見るお皿の積み重ねが現実世界の一般的な例であると想像してください。お皿は一番上からしか取り出すことができず、お皿を洗った後は一番上にのみ置くことができます。スタックは後入れ先出しデータ構造として知られています。データはスタックの最上位でのみ追加または削除できるため、効率的なデータ構造であり、そのような操作は高速です。

使用条件:

データストレージが後入れ先出しまたは先入れ後出しの原則を満たしている限り、スタックの使用が優先されます

Queue

キューもリストの一種です。違いは、キューはキューの最後にのみ要素を挿入できることです。キューの先頭にある要素を削除します。私たちが銀行で列に並んでいると想像してください。列の先頭にいる人が最初に取引を行い、後ろから来た人は順番が来るまで列の後ろで待たなければなりません。

使用条件:

データストレージが先入れ先出しおよび後入れ後出しの原則を満たしている限り、キューの使用が優先されます

一般的なアプリケーションシナリオ:

キューは主に時間に関係する場所、特にオペレーティングシステムで使用されます。キューはマルチタスクを実現するための重要なメカニズムです。

メッセージメカニズムを実装できます。

リンクリスト

リンクリストもリストの一種です。リンクされたリストは必要ですか? JavaScript の配列に関する主な問題は、C や Java などの言語の他の配列とは異なり、比較的非効率であることです。実際に配列を使用すると速度が遅いことがわかった場合は、代わりにリンクリストの使用を検討してください。

使用条件:

リンクリストは、1 次元配列が使用できるほぼすべての状況で使用できます。ランダムアクセスが必要な場合は、やはり配列を選択することをお勧めします。

Dictionary

ディクショナリは、キーと値のペアでデータを保存するデータ構造です。JavaScript のオブジェクトクラスはディクショナリに基づいています。 . フォーマルなデザイン。 JavaScriptでは辞書クラスを実装することでこの辞書型オブジェクトを使いやすくすることができます辞書はオブジェクトの共通機能を実現し、それに応じて必要な機能を拡張することができますオブジェクトはJavaScript記述の随所に現れるため、辞書の役割はも非常に明白です。

ハッシュ

ハッシュ (ハッシュテーブルとも呼ばれる) は、一般的に使用される配列ストレージテクノロジであり、配列をすばやく挿入または取得できます。ハッシュ化に使用されるデータ構造はハッシュテーブルと呼ばれます。ハッシュテーブル上のデータの挿入、削除、取得は非常に高速ですが、配列内の最大値と最小値を見つけるなどの検索操作では非効率的です。これらの操作には、以下で説明する二分探索ツリーなどの他のデータ構造を利用する必要があります。

ハッシュテーブルは、JavaScript の配列に基づいて設計できます。配列の長さはあらかじめ設定されており、すべての要素はその要素に対応するキーに従って配列内の特定の場所に格納されます。ここでのキーとオブジェクトのキーは型の概念です。ハッシュテーブルを使用して配列を格納する場合、ハッシュ関数はキーを 0 からハッシュテーブルの長さまでの範囲の数値にマップします。

効率的なハッシュ関数を使用した場合でも、2 つのキーが同じ値にマッピングされる可能性があり、この現象は衝突と呼ばれます。一般的な衝突処理方法には、オープンチェーン方式と線形検出方式が含まれます (特定の概念に興味がある人は、オンラインで自信を持って学習できます)

使用条件:

はデータ挿入に使用できます。、削除と取得。使用されますが、データの検索には適していません

图

グラフは、一連のエッジと一連の頂点で構成されます。地図は私たちの身の回りにある非常に一般的な現実の風景であり、たとえば、2 つの町ごとに何らかの道路でつながっています。上にある各町を頂点、町を結ぶ道路がエッジと考えられます。エッジは頂点のペア (v1、v2) によって定義されます。ここで、v1 と v2 はグラフ内の 2 つの頂点です。頂点にも重みがあり、コストになります。グラフの頂点ペアが順序付けされている場合、そのグラフは有向グラフ (一般的なフローチャートなど) と呼ばれ、そうでない場合は順序なしグラフと呼ばれます。

使用シナリオ (グラフを使用して現実のシステムをモデル化):

交通システムでは、頂点を使用して道路の交差点を表し、エッジを使用して道路を表すことができます。重み付けされたエッジは、制限速度または車線の数を表すことができます。このシステムを使用すると、最適なルートとどの道路が渋滞する可能性が最も高いかを判断できます。

あらゆる交通システムはグラフを使用してモデル化できます。たとえば、航空会社は図を使用して自社の飛行システムをモデル化できます。各空港を頂点、2 つの頂点を通過する各路線をエッジと考えます。重み付けされたエッジは、モデル化されている内容に応じて、ある空港から別の空港へのフライトのコスト、または 2 つの空港間の距離を表すことができます。

グラフの検索には、深さ優先検索と幅優先検索という 2 つの主なアルゴリズムがあります。

二分木と二分探索ツリー

ツリーは、コンピューターサイエンスでよく使用されるデータ構造です。ツリーは、データを階層的に格納する非線形データ構造です。

バイナリツリーの各ノードは 3 つ以上の子ノードを持つことはできません。親ノードの 2 つの子ノードをそれぞれ左ノード、右ノードと呼びます。子ノードの数を 2 に制限することで、ツリー内のデータの挿入、検索、削除を行う効率的なプログラムを作成できます。

二分探索木 (BST) は、比較的小さな値が左側のノードに格納され、より大きな値が右側のノードに格納される特別な二分木です。この機能により、数値データと非数値データ (単語や文字列など) の両方の検索が非常に効率的になります。

二分探索ツリーの実装方法

function Node(data, left, right) { // 创建节点
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show
}
function show () { // 显示树的数据
  return this.data
}
function BST () { // 二叉查找树类
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder; // inOrder是遍历BST的方式
}
function insert (data) { // 向树中插入数据
  var n = new Node(data, null, null)
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
  parent = current
  if (data < current.data) {
current = current.left;
if (current == null) {
  parent.left = n;
  break;
}
  } else {
current = current.right;
if (current == null) {
  parent.right = n;
  break;
}
  }
    }
  }
}

ログイン後にコピー

BST をトラバースするには 3 つの方法があります: インオーダートラバーサル (ツリー内のすべてのノードに昇順でアクセスし、最初に左側のノードにアクセスし、次に左側のノードにアクセスします)ルートノードにアクセスし、最後に右側のノードにアクセスします)、プレオーダートラバーサル (最初にルートノードにアクセスし、次に同じ方法で左右のノードにアクセスします)、ポストオーダートラバーサル (最初に左側のサブツリーからリーフノードにアクセスします)右のサブツリーに移動し、次にルートノードに移動します)

[関連する推奨事項: JavaScript ビデオチュートリアル、Web フロントエンド ]

以上がJavaScriptにはデータ構造がありますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。