C言語のデータ構造はどうなっているのでしょうか？一般的なデータ構造は何ですか?

C 言語では、データ構造とは、相互に 1 つ以上の特定の関係を持つデータ要素のコレクションを指します。これは、コンピュータがデータを保存および整理する方法です。一般的なデータ構造には次のようなものがあります。データ構造（配列、リンクリスト、スタック、キュー、線形リスト）、ツリー構造（二分木、完全二分木、二分探索木、ヒープ）、グラフ構造（有向グラフ、無向グラフ）。

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

データ構造とは何ですか?

データ構造は、コンピューターがデータを保存および整理する方法です。データ構造とは、相互に 1 つ以上の特定の関係を持つデータ要素のコレクションを指します。

ほとんどのデータ構造の実装には、C 言語のポインターと構造型の助けが必要です。

O(∩_∩)O いくつかの一般的なデータ構造

(1) 線形データ構造: 一般に、要素間には 1 対 1 の関係があり、これが最も一般的です。 used データ構造の一種。通常: 配列、スタック、キュー、線形テーブル

(2) ツリー構造: ノード間には階層関係があり、各層のノードは結合できます。また結合することもできます。上位層のノードは関連していますが、同時に次の層の複数のノードに関連付けることができ、これを「1 対多」関係と呼びます。一般的なタイプは次のとおりです: ツリー、ヒープ

(3) グラフィック構造: グラフ構造では、複数のノードを関連付けることができます。これを「多対多」関係と呼びます。

以下は、これらの各データの簡単な説明です。構造:

##1. 線形データ構造: 典型的なものは次のとおりです: 配列、スタック、キュー、線形テーブル

(1)配列とリンクリスト

#a. 配列：同じ型のデータの集まりを格納します 1次元配列、2次元配列など配列の長さを事前に指定する必要があります、多次元配列など.

b. リンク リスト: リンク リストは C 言語の一種で広く使用されている構造で、任意のストレージ ユニットのセットを使用して動的に割り当てられたメモリの形式で実装されます。データ要素のリンクされたリストを保存します。一般に、後続の要素を指すように各要素にポインタ フィールドが追加されます。

c, 配列リンク リストとの違い:

論理構造から観点: 配列は事前に固定長を定義する必要があり、データの動的な増減には対応できませんが、リンク リストはストレージを動的に割り当て、データの動的な増減に対応でき、データ項目の挿入と削除が簡単に行えます。 (配列内のデータ項目を挿入または削除する場合、他のデータ項目を移動する必要があります)

メモリストレージの観点から: (静的) 配列はスタックからスペースを割り当てます (NEW がheap) はプログラマにとって便利で高速ですが、自由度が低く、リンク リストはヒープから領域を割り当てます。これは自由度は高いですが、適用と管理が面倒です。

Fromアクセス方法の観点: 配列はメモリ内にあり、連続的に保存されるため、ランダム アクセスに添字インデックスを使用できます。リンク リストはリンクされたストレージ構造であり、要素は前から後ろに線形で連続的にのみアクセスできます。のため、配列に比べてアクセス効率が低くなります

(2) スタック、キュー、リニアテーブル：格納方法にシーケンシャルストレージ、チェーンストレージ方式が利用可能

シーケンシャルストレージ: ストレージスペース内のデータ要素の相対位置を利用します。要素間の論理関係を表す位置

チェーンストレージ: データ要素のストレージアドレスを表すポインタを使用して、要素間の論理関係を表します。

a. スタック: シーケンスの最後でのみ許可されます 操作、スタック操作はスタックの先頭でのみ実行できます 一般に、スタックは後入れ先出しまたは先入れとも呼ばれます-in-last-out 線形構造

シーケンシャル スタック: シーケンシャル記憶構造を使用するスタックはシーケンシャル スタックと呼ばれます。つまり、スタックの要素を格納するために連続したアドレスを持つ空間が必要です。シーケンシャルスタックのタイプは次のように定義されます:

#チェーンスタック: チェーンストレージ構造を使用するスタックはチェーンスタックと呼ばれます:

b. キュー: シーケンスの両端でのみ操作が許可されます。一般に、キューは先入れ先出し線形構造とも呼ばれます。

循環キュー: 順次記憶構造キューは、キューの最大可能長に従ってストレージ スペースを割り当てる必要があります。そのタイプは次のように定義されます:

チェーン キュー: チェーン ストレージを使用するキューこの構造はチェーン キューと呼ばれます. 一般に、先頭ポインタと末尾ポインタの設定は、リンク リストの先頭ノードと末尾ノードだけです:

c. 線形テーブル: が可能シーケンス内の任意の位置での操作が可能です。線形テーブルの操作位置は制限されていません。テーブル操作は非常に柔軟です。一般的な操作には、任意の位置での挿入と削除、任意の位置での要素のクエリと変更が含まれます

シーケンシャルテーブル: シーケンシャルな記憶構造で表される線形テーブルはシーケンシャルテーブルと呼ばれ、連続したアドレスを持つ記憶ユニットのセットは、線形テーブルのデータ要素を一度に記憶するために使用されます。位置は 2 つの要素の間の順序を表します。要素の移動を避けるために、一般に、シーケンス テーブルのインターフェイス定義では、テーブルの末尾の要素の挿入と削除のみが考慮されます。シーケンス テーブルは、次のように実装されています。この方法はスタック テーブルとも呼ばれます:

線形リスト: 一般に、単一リンク リスト、二重リンク リスト、循環リンク リスト、および双方向循環リンク リストが含まれます

単一リンク リスト:

二重リンク リスト:

線形テーブルの 2 つの記憶構造の比較:

シーケンシャル テーブル:

利点: シーケンシャル テーブルでは、論理が相対的である 隣接する 2 つの要素も物理的に隣接しているため、検索が容易になる 要素へのアクセスの時間計算量は O(1 )

. 欠点: 任意の位置での要素の挿入または削除には適していません。要素を移動する必要があるため、平均時間の計算量は O(n)

リンク リスト:

利点: リンクの任意の位置で要素を挿入または削除するには、対応するポインタを変更するだけでよく、要素を移動する必要はありません。オンデマンドで動的に割り当てられるため、連続した空の要素を事前に割り当てる必要はありません。

# 欠点: 検索が不便です。要素を見つけるには、先頭ポインタから開始してポインタ フィールドに沿って検索する必要があるため、平均時間計算量は O(n) です。

2. ツリー構造: ノード間には階層関係があります。各レイヤーのノードは、前のレイヤーの 1 つのノードにのみ関連付けることができますが、次のレイヤーの複数のノードに関連付けることもできます。レイヤー。ノードは関連しており、これは「1 対多」関係と呼ばれます。一般的なタイプは次のとおりです: ツリー、ヒープ

(1) バイナリ ツリー: バイナリ ツリーは、n ( n>=0) ノード。点の有限集合。バイナリ ツリーには次の特性があります:

バイナリ ツリーは空のツリーになる可能性があります。バイナリ ツリーの各ノードには、1 つまたは 2 つの正確に 2 つのサブツリーがあります。空でもよい; 二分木の各ノード 左右の部分木の位置は逆転できない 位置を変えると別の二分木になる

(2) 完全な二分木ツリー: ルートから始まり、上から下、左から右、完全なバイナリ ツリーの各ノードには 1 から n までの連続した番号が付けられます。各ノードが完全なバイナリ ツリーの 1 から n までの番号が付けられたノードと 1 対 1 に対応する場合、深さ k のバイナリ ツリー、それは完全バイナリ ツリーと呼ばれます

a. シーケンシャル ストレージ構造を使用します: 完全なバイナリ ツリーを格納するには 1 次元配列を使用します。ノードの番号は添字に関連付けられます。ノードの (たとえば、ルートが 1、ルートの左側の子が 2i=21=2、右側の子が 2i 1=21 1=2)

##b. チェーン ストレージ構造の採用:

バイナリ リンク リスト:

Trident リンク リスト: そのノードにはバイナリより 1 つ多いポインタ フィールド親があります。リンク リスト。ノードの親を実行し、親ノードの検索を容易にするために使用されます。

2 つのストレージ構造の比較: 完全なバイナリ ツリーの場合、シーケンシャル ストレージ構造は次のことができます。スペースを節約するだけでなく、配列要素の添字値を使用してバイナリ ツリー内のノードの位置とノード間の関係を決定しますが、格納にはシーケンシャル ストレージ構造が使用されます。一般に、バイナリ ツリーはスペースを無駄にする傾向があります。

(3) 二分探索木: 二分探索木は二分ソート木とも呼ばれ、空の二分木、または次の特徴を持っています: 特性二分木:

a. 左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値はルート ノードの値より小さくなります。サブツリーが空でない場合、右側のサブツリー上のすべてのノードの値はルート ノードの値

c より大きく、その左右のサブツリーも二分探索ツリー

になります。

(4) バランスのとれた二分木: バランスのとれた二分探索木は、バランスのとれた二分木と呼ばれます。両方のバランスの取れた二分木と左側のサブツリーの高さと右側のサブツリーの高さの差の絶対値が 1 を超えない

#バランスの取れた二分木の不均衡と調整二分木は次の 4 つの状況に要約できます: LL 型、RR 型、LR 型、RL 型

(5) 木: 木は n (n>=0) 個のノードを含む有限集合です。空ではないツリー タイプ: a. ルート

と呼ばれる特定のノードが 1 つだけ存在します b. n>1 の場合、残りのノードは m (m>0) の相互に素な有限に分割できますセット T1、T2、...、Tm。各セット自体はツリーであり、T1、T2、...、Tm はルートのサブツリーと呼ばれます

(6) ヒープ: ヒープは、次の特性を持つ完全なバイナリ ツリーです: すべての非リーフ ノードは、その左右の子ノードよりも大きくありません (または小さくありません)。ヒープ内のすべての非リーフ ノードがその左右の子ノードより大きくない場合、それはスモール トップ ヒープ (スモール ルート ヒープ) と呼ばれます。トップヒープ (ビッグルートヒープ)

(7) Union-find: Union-find は集合から構成される集合を指します。 S= {S1,S2,S3,…,Sn}

(8) B-tree

3. グラフ構造: グラフ構造内、複数のノード間の相関関係が許可されます。これは「多対多」関係と呼ばれ、有向グラフと無向グラフに分けることができます

チュートリアルの推奨事項: "c 言語チュートリアル ビデオ"

以上がC言語のデータ構造はどうなっているのでしょうか？一般的なデータ構造は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。