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

青灯夜游

リリース： 2021-11-22 15:04:58

オリジナル

13618 人が閲覧しました

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

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

このチュートリアルの動作環境: 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 サイトの他の関連記事を参照してください。