大話データ構造ノート-リニアテーブル

大話データ構造ノート-リニアテーブル
基礎知識
線形テーブル(List):0個以上のデータ要素の有限シーケンス.
ポイント:順序がある、限られている
たとえば、a, b, c, d, ···, zの線形テーブルがあります.

aはbの直接前駆元素

である.

bはaの直接後続要素

である.

各要素には、最大1つの直接前駆要素と直接後続要素

がある.
すべての線形テーブル要素の個数n(n>=0)は線形テーブルの長さであり、n=0の場合、空のテーブルである.
複雑なリニア・テーブルでは、1つのデータ要素は、花名簿などのいくつかのデータ・アイテムで構成できます.
ちくじきおくこうぞう
リニアテーブルのデータ記憶構造とは、リニアテーブルを一段のアドレスで連続した記憶手段で順次記憶するデータ要素を指す.
シーケンスストレージ構造の3つの重要な属性:

記憶空間の開始位置

リニアテーブルの最大長

リニアテーブルの現在の長さ

アドレスけいさんほうしき
ゼロからi番目の要素の格納位置はi−1である.
メモリ内の各メモリセルには、アドレスと呼ばれる独自の番号があります.
メリットとデメリット
メリット:

は、テーブル内の要素間の論理関係のために徐々に追加される記憶領域

を必要としない.

クイックアクセステーブルの任意の要素

欠点:

挿入および削除操作には、大量の要素

を移動する必要がある.

リニアテーブル長の変化が大きいと、記憶空間の容量

を特定することが困難となる.

ストレージスペースの「断片化」

チェーンストレージ構造
基本定義

は、その名の通り、各要素が鎖のように環状に接続されている.

は、各要素とその後続要素との関係を表すために、自身の情報のほかに、その直接後続要素のアドレスも記憶する.

要素情報を格納するドメインをデータドメイン、後続の位置を格納するドメインをポインタドメインと呼ぶ.ポインタドメインに格納されている情報をポインタまたはチェーンと呼びます.

データ要素を構成する2つの部分のストレージイメージをノードと呼びます.

チェーンテーブルの最初のノードの格納位置をヘッダポインタと呼びます.

ヘッダノードには何の情報も格納されない場合があり、リニアテーブルの長さなどの情報を格納できる場合があります.
データの挿入または削除が頻繁であればあるほど、単一チェーンテーブルの利点が大きくなります.
ヘッドポインタとヘッド接点
ヘッドポインタ

チェーンテーブルは、最初のノードのポインタを指し、チェーンテーブルにヘッダノードがある場合は、ヘッダノードを指す.

は識別機能を有するため、よく用いられるヘッドポインタはチェーンテーブル名を冠する.

チェーンテーブルが空であるかどうかにかかわらず、ヘッドポインタは空ではなく、ヘッドポインタはチェーンテーブルの必要な要素である.

ヘッドノード

ヘッダノードは、操作の統一と利便性のために設けられ、第1要素のノードの前に置くと、そのデータドメインは一般的に意味(または長さ)がない.

にはヘッダノードがあり、第1要素ノードの前にノードを挿入し、第1ノードを削除することを統一している.

ヘッダノードは、必ずしもチェーンテーブルに必要な要素ではありません.

シングルチェーンテーブルの読み取り、挿入、削除
読み取り:
ポインタを後ろに移動すると、チェーンテーブルのヘッダノードから指定されたノードが1つずつ見つかります.
挿入:
ポインタを後方に移動する所定の位置の前のノード(n-1)を見つけた後、そのポインタドメインを挿入する要素のノード(n)に指向し、次に挿入要素のポインタを次の要素(n+1)に指向する.
削除:
挿入と同様に、逆方向に操作します.
シングルチェーンテーブル構造とシーケンスストレージ構造のメリットとデメリット
きおくわりあてほうしき

シーケンス記憶構造は、線形テーブルのデータ要素を連続した記憶ユニットで順次記憶する.

単一チェーンテーブル用チェーンストレージ構造は、任意のストレージユニットのセットに線形テーブルの要素を格納させるために使用される.

タイムパフォーマンス

検索:

順次記憶:O(1)

単鎖表:O(n)

挿入削除

は、平均移動テーブル長の半分を必要とする要素O(n)

を順次記憶する.

単鎖表は位置を探し出した後O(1)

である.

くうかんせいのう

シーケンスストレージ構造は、予めストレージスペースを割り当てる必要があり、浪費が大きくなり、オーバーフローが発生しやすくなる.

単一チェーンテーブルは、割り当てスペースを必要とせず、あれば個数も制限されないように割り当てることができます.

理解する

データの変更が少ない頻繁なクエリの場合、逆選択チェーンテーブル

が使用順序で格納.

データサイズが既知である場合は、順序記憶

を用いることができる.

実はやはり状況によって判断しなければならない.

静的チェーンテーブル
ポインタのない言語では,配列を用いてチェーンテーブルを実現し,静的チェーンテーブルを形成する.
すなわち、配列の各要素を2つのデータドメインに分け、1つの(data)はデータを格納し、1つの(cur)は次の要素のインデックスを格納する.
静的チェーンテーブルには、配列の長さが大きく、データの挿入が容易である必要があります.
個人的には2 D配列です

array = [
    0 => ["  ","     key"],
    ...
];

静的チェーンテーブルの挿入と削除
動的チェーンテーブル構造を静的にシミュレートし,必要に応じて申請し,不要になった場合に解放する.
単一チェーンテーブルと同様に、配列内部で完了したにすぎません.
メリットとデメリット
メリット

は、カーソルを変更したり削除したりするだけで、要素を移動する必要がなく、シーケンスストレージ構造における挿入削除操作に多くの要素を移動する必要があるという欠点を改善します.

欠点

は、連続的なストレージ割り当てによるテーブル長の特定が困難な問題を解決していない.

は、シーケンスストレージ構造のランダムアクセスの特性を失った.

静的チェーンテーブルは、ポインタのない高度な言語設計のための単一チェーンテーブル能力を実現する方法である.
ループチェーンテーブル
単一チェーンテーブルの端末ノードのポインタ端を空のポインタからヘッドノードを指すように変更し、単一チェーンテーブル全体をさらに形成し、このようなヘッドテールが接続された単一チェーンテーブルを単一サイクルチェーンテーブルと呼び、単一チェーンテーブルと略称する.
ヘビを食いしん坊にする
にほうこうチェーンテーブル
単一チェーンテーブルの各ノードに、前駆ノードを指すポインタドメインを追加します.
もちろん,双方向チェーンテーブルの首尾部を接続すると双方向ループチェーンテーブルが形成される.
まとめ

リニアメータ

シーケンス記憶構造

チェーンストレージ構造

単鎖表

静的チェーンテーブル

循環チェーンテーブル

双方向チェーンテーブル