リンクされたリストは、どのような記憶構造に格納される線形リストです

リンク リストは、「連鎖」ストレージ構造に格納される線形リストです。リンク リストのデータ要素が占めるストレージ ユニット アドレスは、連続または不連続にすることができます。対応するストレージ スペースは、必要に応じて一時的かつ動的に割り当てることができます。データ要素間の論理関係は、「チェーン」として表現できます。

このチュートリアルの動作環境: Windows 7 システム、Dell G3 コンピューター。

シーケンシャル テーブル ストレージ構造の欠点を克服し、ストレージ スペースを最大限に活用し、操作効率を向上させるために、リニア テーブルは別のストレージ構造 - リンク ストレージ構造 を使用できます。 線形リストの連結された記憶構造を「リンク リスト」と呼びます

1. 連結リストの概要

データ要素が占める記憶単位のアドレスリンクされたリストの は連続的であることも、不連続であることもあり、対応する記憶領域は必要に応じて一時的かつ動的に割り当てることができ、データ要素間の論理関係は「チェーン」として表現できます。

リンク リストの挿入と削除にはデータ要素を移動する必要はなく、チェーンを変更するだけで済みます。

リンクリストの分類:

1. リンクリストのメモリ割り当て方法による分類

①動的リンクリスト

②静的リンクリスト

2 .リンク方法による分類

①単一リンクリスト

②循環リンクリスト

③ダブルリンクリスト

(すべて動的リンクリスト)

2. 単結合リストの定義

1. 定義

各データ要素 ai とその直接の後続データ要素 ai 1 の間の論理関係を表現するには、 を除く各データ要素 ai は、独自の情報を格納することに加えて、その直接の後続を示す情報も格納する必要があります(後継のストレージの場所-アドレス)。 データ要素情報を格納するフィールドを

データ フィールド と呼び、直後の後続位置を格納するフィールドを ポインタ フィールド#と呼びます# #、ポインタ領域に格納される情報はポインタまたはチェーンと呼ばれます。 これら 2 つの情報部分は、

node

と呼ばれるデータ要素 ai のストレージ イメージを構成します。 n 個のノードがリンク リストにリンクされます。リンク リストは、線形リスト (a1、a2、a3、...、an) のリンクされた記憶構造です。これは、リンク リストの各ノードにはポインタが 1 つだけ含まれるためです。ドメインなので、single

リンク リスト と呼ばれます。 線形リストには常に先頭と末尾があり、リンクされたリストも例外ではありません。 リンク リスト内の単一リンク リストの最初のノードへのポインタは、

ヘッド ポインタ と呼ばれます。リンク リスト全体へのアクセスは先頭から開始する必要があります。ポインタと後続の各ノード ポイントは、前のノードの後続ポインタが指す位置です。 リンクされたリストの最後のノードのポインタは、「empty (通常は NULL で表されます)」、つまり NULL ポインタです。 連結リストに対するさまざまな操作を容易に行うために、単一連結リストの最初のデータノードの前に同じ種類のノードが設定され、このノードをヘッドノードと呼びます。

ヘッド ノードのデータ フィールドには、リンク リストの長さなどの特別なフラグ情報を格納できますが、データを格納することはできません。

リンクされたリストの最初のデータ ノードと最後のノードは、

先頭ノードと末尾ノード

とも呼ばれます。

2. ヘッド ポインターとヘッド ノードの類似点と相違点

ヘッド ポインター:

ヘッド ポインターリンクリストを参照します 最初のノードへのポインタ リンクリストに先頭ノードがある場合は、先頭ノードへのポインタです。

先頭ポインタは識別機能を持ち、リンクリストの名前としてよく使われます。
• リンクされたリストが空かどうかに関係なく、先頭ポインタは空ではありません。
• ヘッド ポインタはリンク リストの必須要素です。
• ヘッド ノード:

ヘッド ノードは、操作の統一と利便性を目的として設けられ、最初の要素のノードとそのデータ フィールドの前に配置されます。意図的ではない。

先頭ノードでは、先頭要素ノードの前にノードを挿入したり、先頭ノードを削除したりする操作が他のノードと統一されます。
• ヘッド ノードは、リンク リストの必須要素である必要はありません。
• 3. コードのデモ

/*线性表的单链表存储结构*/
/*结点定义*/
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;

/*单链表定义*/
typedef struct Node *LinkList;

3. 単結合リストの操作

1. 挿入操作

1) 挿入シミュレーション

要素 e を格納するノードを s として、ai に s を挿入します。ノードの背後で操作するにはどうすればよいですか?

考察: 挿入された 2 つのコードは交換できるでしょうか?

いいえ、切り替えた場合、s のポインター フィールドが ai 1 のアドレスを指していないため、ai 1 などの後続の要素は見つかりません。

2) 単一リンクリストのノードに i 番目のデータを挿入するアルゴリズムのアイデア

• リンクリストの最初のノードを指すノード p を宣言します。 initialize j=1;
• j
• p が最後に空の場合リンクリストの i 番目の要素が存在しないことを意味します; 検索が成功した場合は、空のノード s を生成します (malloc 関数を使用)
• データ要素 e を s-> に代入します。データ (s->data=e;
• 標準ステートメントを挿入: s->next=p->next;p->next=s;
• 正常に戻りました。

2. 削除操作

1) シミュレーションの削除

要素 ai を格納するノードを q とし、単一リンクからノード q を削除する操作を行う。リストが実装される予定です。

2) 単一リンクリストの i 番目のデータノードを削除するアルゴリズムのアイデア

• を指すノード p を宣言します。リンク リストの最初のノードを指し、j=1;
• を初期化します。j を指します。
• p がリンクリストの最後に到達した場合 空の場合は、i 番目の要素が存在しないことを意味し、検索が成功した場合、ノード p->next は削除され、q に割り当てられます
• . 標準ステートメントを挿入します: p->next=q->next;
• q ノードを e に割り当てます、つまり e=q->data;
• q ノードを解放します
• 正常に戻りました。

4. 単一リンクリスト構造とシーケンシャルテーブル構造の比較

ストレージ方式:

• シーケンシャルテーブルは、連続ストレージユニットを使用してデータを保存します。シーケンス内の線形テーブル データ要素
• 単一リンク リストはリンク ストレージ構造を採用し、任意のストレージ ユニットのセットを使用して線形テーブル要素を格納します

時間パフォーマンス:

①検索

• 配列テーブルO(1)
• 単一リンクリストO(n)

②挿入と削除

• シーケンス テーブル O (n)
• 単一リンク リスト O(1)

スペース パフォーマンス:

• シーケンス テーブルには、事前に割り当てられたストレージが必要ですスペースが大きすぎると無駄になります。小さすぎるとオーバーフローが発生しやすくなります。
• 単一リンク リストには、必要なだけのストレージ スペースを事前に割り当てる必要はありません。割り当てられ、要素の数に制限はありません

関連する知識の詳細については、FAQ 列を参照してください。

以上がリンクされたリストは、どのような記憶構造に格納される線形リストですの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。