jsデータ構造とアルゴリズム(一)概要
2612 ワード
= +
データ構造とは関係であり、つまり、データ要素同士の間に存在する一種または複数の特定の関係の集合である.
従来,データ構造を論理構造と物理構造に分けた.
論理構造:データオブジェクトにおけるデータ要素間の相互関係であり、今後最も関心と議論が必要な問題でもある.
物理構造:データの論理構造がコンピュータに記憶されている形態を指す.
よく使われるデータ構造は以下の通りです.
， （queue）， （heap）, （stack）， （linked list ）， （tree）， （graph） （hash）
キュー(queue)は、端のみに挿入操作を許可し、他端で削除操作を行う線形表です.
スタックとは対照的に、キューは、ファースト・アウト(First In First Out、FIFO)の線形表である.
スタックと同じで、キューも重要な線形構造であり、1つのキューを実現するには、シーケンステーブルまたはチェーンテーブルをベースとして必要である.
四大構造
集合構造
線形構造
ツリー構造
グラフィック構造
順序記憶とチェーン記憶
データ要素の記憶構造には、順序記憶とチェーン記憶があります.例えば、私たちが言語をプログラミングする配列構造はこのようにしています.
チェーン式記憶構造:データ要素を任意の記憶ユニットに格納することであり、この記憶ユニットは連続的であってもよいし、不連続であってもよい.
チェーン記憶構造
線形表
線形表:行列のように線のような性質を持つ構造で、ゼロまたは複数のデータ要素からなる有限なシーケンスです.
要素が複数存在する場合、最初の要素は前駆がなく、最後の要素は後継がなく、他の要素は全部あり、前駆と後継が一つだけあります.
線形表現を(a 1,…,ai-1,ai＋1,…an)と表記すると、ai-1がai＋1より先にリードされ、ai-1はaiの直接的な前駆要素であり、ai＋1はaiの直接的な後継要素である.
データの種類
データの種類:性質が同じ値のセットと、このセット上のいくつかの動作を定義する総称です.
多くのプログラミング言語の整型、浮動小数点型、文字型などはデータタイプを指します.
コンピュータの中で、メモリは無限大ではありません.大きな数を計算したり処理したりするには、大きなメモリ空間を開く必要があります.そこでコンピュータに対してデータの種類を分類して、さまざまな計算条件の違いに適合するデータの種類を分けます.
C言語では、データの種類は次のように分けられます.
原子のタイプ:再分解できない基本的なタイプ、例えば整型、浮動小数点型、文字型など.
構造タイプ:いくつかのタイプの組み合わせによって構成され、再分解可能であり、例えば、整数行列はいくつかの整数データから構成されている.
アルゴリズム
アルゴリズムは特定の問題を解決するためのステップの記述であり、コンピュータでは命令の有限シーケンスとして表現され、各命令は1つ以上の動作を表す.
アルゴリズムは5つの基本的な特徴を持っています.入出力、貧困性、確定性、実現可能性があります.
出力:アルゴリズムは少なくとも1つ以上の出力があります.貧乏性がある:アルゴリズムは限られたステップを実行した後、無限ループが発生することなく自動的に終了し、各ステップは許容可能な時間内に完了する.
決定性:アルゴリズムの各ステップは決定的な意味を持ち、二義性は現れない.
実現可能性:アルゴリズムの各ステップは実行可能である必要があります.つまり、各ステップは限られた回数を実行することによって達成できます.
正確性:アルゴリズムの正確性とは、アルゴリズムが少なくとも入力、出力、加工処理の曖昧性がなく、問題のニーズを正確に反映し、問題の正解を得ることができるということである.
高度な言語で作成されたプログラムがコンピュータ上で実行される時に消費される時間は以下の要因に依存します.
1. ，
2.
3.
4.
線形テーブルの順序記憶構造とは、一セグメントのアドレスで連続する記憶部が、線形テーブルのデータ要素を順次記憶することをいう.
リニアテーブル(a 1,a 2,…,an)の順序は以下の通りです.
リニアテーブル順に記憶される構造
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length; //
} SqList;
記憶空間の開始位置は、配列dataであり、その記憶位置は、線形テーブル記憶空間の記憶位置である.
線形テーブルの最大記憶容量:配列の長さMaxSize.
線形表の現在の長さ:length.
アルゴリズムの考えを挿入する
， ；
， ；
i ， ；
i ；
+1。