線形連結リストは線形リストの連結された記憶構造ですか?-よくある問題-php.cn

線形連結リストは線形リストの連結された記憶構造ですか?

(*-*)浩

リリース： 2019-10-24 09:50:34

オリジナル

14189 人が閲覧しました

データ構造内の各データ要素間の関係の複雑さに応じて、データ構造は通常、線形構造と非線形構造の 2 つの主要なタイプに分類されます。

#線形リンクリストは、名前が示すように、チェーンリストに似ています。線形リンクリストの反対は次のとおりです。線形シーケンスリスト両方の違いは、線形シーケンステーブルはメモリ内に連続領域を開く必要があるため、メモリに格納されるデータの状態は連続的ですが、線形リンクリストのメモリへの格納はランダムであることです。データ間の接続はポインタに依存します。 (推奨学習: Web フロントエンドビデオチュートリアル )

空ではないデータ構造が次の 2 つの条件を満たす場合:

①存在するのは 1 つだけですルートノードポイント;

②各ノードには最大 1 つの前件と最大 1 つの後件があります。データ構造は線形構造と呼ばれ、線形テーブルとも呼ばれます。したがって、線形リスト、スタックとキュー、および線形リンクリストはすべて線形構造ですが、バイナリツリーは非線形構造です。

リンクされたストレージ構造を持つ線形テーブル。任意のアドレスを持つ一連のストレージユニットを使用して、線形テーブルにデータ要素を格納します。論理的に隣接する要素は物理的に隣接している必要はなく、ランダムにアクセスすることはできません。。一般にノードによって説明されます: ノード (データ要素を表す) = データドメイン (データ要素のイメージ) ポインタドメイン (後続の要素の格納場所を示す)

チェーンストレージ構造では、データ構造のストレージデータ要素間の論理関係はポインタフィールドによって決定されますが、空間は不連続である可能性があり、各データノードの格納順序はデータ要素間の論理関係と一致しない可能性があります。連鎖記憶法は、線形構造と非線形構造の両方を表現するために使用できます。

一般に、線形リストの連結記憶構造では、各データノードの記憶シンボルが不連続であり、記憶空間内での各ノードの位置関係や論理関係も不整合となる。線形リンクリストの場合、先頭ポインタから開始して、各ノードのポインタに沿ってリンクリスト内のすべてのノードをスキャンできます。

線形リンクリストの構築は、リンクポイントを動的に生成し、それらをリンクリストに順番にリンクするプロセスです。線形リンクリストの最初のリンク点のポインタをリストとする。

最初のリンクポイントが生成されるとき、リンクリストは空です。リンクポイントをリストに直接送信するだけです。データ要素が取得されるたびに、そのデータ要素に対してリンクポイントが生成され、取得したデータ要素のデータ情報が新規ノードのデータフィールドに送信される一方で、新規ノードのポインタフィールドはNULLに設定され、新しいノードは、リンクされたリストの最後に挿入されます。

次のアルゴリズムは、data.txt という名前のファイルから文字列を線形リンクリストのデータ要素として 1 行ずつ読み取ります。アルゴリズムは次のとおりです:

LinkList creatList() {
    LinkList r, p, list = NULL;
    char data[ 100 ];
 
    FILE *f = fopen( "data.txt", "rb" );
    while( fgets( data, 100, f ) )
    {
        p = ( LinkList )malloc( sizeof( LNode ) );
        if( p != NULL ){
            strcpy( p->data, data );
            p->link = NULL;
 
            if( list == NULL )
                list = p;
            else
                r->link = p;
            r = p;
        }
    }
    fclose( f );
 
    return list;
}

ログイン後にコピー

以上が線形連結リストは線形リストの連結された記憶構造ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。