リニアテーブルのシーケンシャルストレージ構造

線形テーブルは、最も基本的かつ単純で、最も一般的に使用されるデータ構造です。線形リストはデータ構造の一種であり、同じ特性を持つ n データ要素の有限シーケンスです。

#線形テーブルは主にシーケンシャル表現またはチェーン表現で表現されます。実際のアプリケーションでは、スタック、キュー、文字列などの特別な形式で使用されることがよくあります。

#シーケンシャル表現とは、連続したアドレスを持つ一連のストレージ ユニットを使用して、線形テーブルのデータ要素をシーケンシャルに格納することを指します。これは、シーケンシャル ストレージ構造または線形テーブルのシーケンシャル マッピングと呼ばれます。 。 「物理的位置隣接性」を使用して線形テーブル内のデータ要素間の論理関係を表し、テーブル内の任意の要素にランダムにアクセスできます。

結果として得られるストレージ構造は、シーケンシャル ストレージ構造です。通常、シーケンシャル ストレージ構造は、コンピュータ プログラミング言語 (c/c など) の配列を使用して記述されます。

シーケンシャル ストレージ構造の主な利点は、(配列のサイズを指定する必要があるかどうかに関係なく) データに割り当てられたストレージ ユニットがすべてノード データの格納に使用されるため、ストレージ スペースを節約できることです。 C/C 言語)、ノード間の論理関係は追加の記憶領域を占有しません。この方法を採用すると、ノードへのランダムアクセスが可能となり、各ノードに通し番号が対応付けられ、この通し番号からノードの記憶アドレスを直接計算することができる。ただし、順次保存方法の主な欠点は、変更が不便であり、ノードの挿入や削除の際に、一連のノードを移動する必要がある場合があります。

推奨コース:

C 言語チュートリアル 。

線形テーブルの順次ストレージ構造の構造コード:

#define MAXSIZE 20    
typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int length;    // 线性表当前长度
} SqList;

順次ストレージ構造のカプセル化には 3 つの属性が必要です:

Storage空間の開始位置、配列データの格納場所は、線形テーブル格納空間の格納場所です。

線形テーブルの最大ストレージ容量: 配列の長さ MaxSize。

線形テーブルの現在の長さ: length。

注: 配列の長さと線形テーブルの現在の長さを区別する必要があります。配列の長さは、線形テーブルを保存するための記憶領域の合計長です。であり、通常は初期化後も変化しません。線形テーブルの現在の長さは線形テーブル内の要素の数であり、今後変化します。

線形テーブルのシーケンシャル ストレージ構造の利点と欠点

線形テーブルのシーケンシャル ストレージ構造では、データがどこにあるかに関係なく、データを格納および読み取る際の時間計算量が大きくなります。はO(1)です。挿入または削除の場合、時間計算量は O(n) です。

これは、要素の数が比較的安定しており、要素の挿入や削除が頻繁に行われず、データへのアクセスに多くの操作が使用されるアプリケーションにより適していることを意味します。

利点:

テーブル内の要素間の論理関係を表現するために追加の記憶域を追加する必要はありません。

テーブル内のどこにでも要素にすばやくアクセスできます。

欠点:

挿入および削除操作では、多数の要素を移動する必要があります。

リニアテーブルの長さが大きく変わると、格納スペースの容量を決めるのが難しくなります。

ストレージスペースの「断片化」が発生しやすいです。

以上がリニアテーブルのシーケンシャルストレージ構造の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。