0

これらのコードの違いは何ですか?

1)

struct MyStruct
{
    int num;
} ms[2];

ms[0].num = 5;
ms[1].num = 15;

2)

struct MyStruct
{
    int num;
    MyStruct *next;
};

MyStruct *ms = new MyStruct;
ms->num = 5;
ms->next = new MyStruct;
ms->next->num = 15;

おそらく、リンクされたリストとリスト全般について少し混乱していますが、それらは特定の何かに役立ちますか? もっと説明してください。

4

6 に答える 6

4

最初の定義...

struct MyStruct
{
    int num;
} ms[1];

...単一の要素を持つ静的に割り当てられた配列を作成します。プログラムの実行中に配列のサイズを変更することはできません。この配列が複数の要素を保持することはありません。直接インデックスを作成することにより、配列内の項目にアクセスできます。たとえば、適切なサイズの配列を定義したと仮定するとms[5]、配列の 6 番目の要素が取得されます (C および C++ 配列は 0 から始まるため、最初の要素は です)。ms[0]

あなたの2番目の定義...

struct MyStruct
{
    int num;
    MyStruct *next;
};

...動的に割り当てられたリンク リストを作成します。このリストのメモリは実行時に動的に割り当てられ、リンクされたリストはプログラムの存続期間中に拡大 (または縮小) する可能性があります。配列とは異なり、リスト内の要素に直接アクセスすることはできません。6 番目の要素に到達するには、最初の要素から始めて、5 回繰り返す必要があります。

于 2012-05-04T19:04:10.833 に答える
2

コードに含まれるエラーに関して、最初のエラーは静的な数の MyStruct 要素を構築し、それらを ms 配列に格納するため、ms は MyStruct 構造体の配列です。もちろん、これは 2 つの要素のみであることを意味していましたが、後でms配列に他の要素を追加することはできません.MyStruct要素の数を制限していますが、リンクリストがある2番目のケースでは、必要な数のMyStruct要素を連鎖させることができ、これは動的数につながります. MyStruct 要素の 2 番目のケースでは、実行時に必要な数の MyStruct を追加できます。2 番目のケースは、概念的にメモリ内で次のようになります。

[ MyStruct#1 ] ----> [ MyStruct#2 ] ----> [ NULL ]

NULL は、たとえば MyStruct#3 である可能性がありますが、最初

[ MyStruct#1 ] ----> [ MyStruct#2 ]

のものは、それだけです。MyStruct#3 を追加することはできません。

では、あなたが書いたコードを見てみましょう:

struct MyStruct
{
    int num;
} ms[1];

ms[1]実際には、1 つの MyStruct 要素の ms 配列を作成することを意味します。
次のコードは、次の 2 つを作成したことを前提としています。

ms[0].num = 5;
ms[1].num = 15

したがって、次のようになるはずです。

struct MyStruct
{
    int num;
} ms[2];

そして、それはうまくいきます！私が作成した簡単な図を覚えておいてください。
[ MyStruct#1 ] ----> [ MyStruct#2 ]

2 番目のケース:

struct MyStruct
{
    int num;
    MyStruct *next;
};

MyStruct *ms = new MyStruct;
ms->num = 5;
ms->next = new MyStruct;
ms->next->num = 15;

newソース コードを保存する.cppと、エラーなしで C++ アプリケーションとしてコンパイルできるため、このコードでは C++ 演算子を使用しますが、C の場合、構文は次のように変更する必要があります。

struct MyStruct
{
    int num;
    MyStruct *next;
};

MyStruct *ms = (MyStruct *) malloc(sizeof MyStruct);
ms->num = 5;
ms->next = (MyStruct *) malloc(sizeof MyStruct);
ms->next->num = 15;

#include <stdlib.h>関数に含めることを忘れないでください。malloc()この関数の詳細については、こちらを参照してください。
そして、最初のケースとして、リンクされたリストの私の図を思い出してください:
[ MyStruct#1 ] ----> [ MyStruct#2 ] ----> [ NULL ]

ここで、NULL は実際には ms->next MyStruct 構造の次の要素です。それを説明するために、ms->next が MyStruct のポインターであり、それを割り当てたことを思い出してください。ヒープ内のスペースなので、同じサイズの MyStruct 構造のメモリ ブロックを指しています。最後に、いつ連結リストを使用し、いつ配列を使用するかについてのStackoverflowの質問です。これにより、世界中の人々が連結リストを好む場合と配列を好む場合がある理由を正確に理解できます。

于 2012-05-04T19:15:06.460 に答える
1

一般的なリストと配列の主な違い:

  • リスト内の順序は明示的です。各要素には、前後の要素の位置が格納されます。配列内の順序付けは暗黙的です。各要素には、前後の要素があると見なされます。1 つのリストに複数の順序が含まれる場合があることに注意してください。たとえば、次のようなものがあります

    struct dualList {
T data1;
K data2;
struct dualList *nextT;
struct dualList *nextK;
};
    これにより、同じリストを 2 つの異なる方法で順序付けることができdata1ますdata2。

  • 隣接する配列要素は隣接するメモリ位置にあります。隣接するリスト要素は、隣接する場所にある必要はありません。

  • 配列は、その要素へのランダム アクセスを提供します。リストはシーケンシャル アクセスのみを提供します (つまり、要素を見つけるにはリストをたどる必要があります)。

  • 配列は (通常) 長さ1に固定されています。配列に要素を追加したり、配列から要素を削除したりしても、配列のサイズは変わりません。リストは、必要に応じて拡大または縮小できます。

リストは、特に値の順序を維持する必要がある場合に、動的に変化する値のシーケンスを維持するのに最適です。要素にランダムにアクセスできないため、迅速かつ頻繁に取得する必要がある比較的静的なデータを格納するのにはあまり適していません。

  1. これは、メモリを動的に宣言しrealloc、必要に応じてそのメモリ ブロックのサイズを変更することで回避できますが、慎重に行う必要があり、少し PITA になる可能性があります。
于 2012-05-04T19:26:19.503 に答える
1

ああ、私の友人、たくさんのnum値などを保持するだけのさまざまな種類のデータ構造が何十もあります。プログラマーがすべてに配列を使用しない理由は、必要なメモリ量の違いと、特定のニーズにとって最も重要な操作を簡単に実行できるためです。

リンクされたリストは、個々のアイテムを追加または削除するのが非常に高速です。トレードオフは、リストの中間にある項目を見つけるのが比較的遅く、nextポインタによって余分なメモリが必要になることです。適切なサイズの配列はメモリ内で非常にコンパクトであり、中間のアイテムに非常に迅速にアクセスできますが、最後に新しいアイテムを追加するには、要素の最大数を事前に知る必要があり、多くの場合不可能であるか無駄になります。メモリを再割り当てするか、より大きな配列を再割り当てしてすべてをコピーしますが、これは遅いです。

したがって、自分のリストがどれだけ大きくなければならないかわからない人や、ほとんどの場合、リストの最初または最後にある項目のみを処理する必要があるか、常にリスト全体をループする必要がある人で、ファイルを保存するよりも実行速度を重視する人です。数バイトのメモリでは、配列よりもリンク リストを選択する可能性が非常に高くなります。

于 2012-05-04T19:22:11.477 に答える
0

配列は連続した事前に割り当てられたメモリのブロックですが、リンクされたリストは、mallocポインタ ( ) を介して互いにリンクされた、実行時に割り当てられた ( ) メモリの断片 (必ずしも連続している必要はありません)のコレクションです*next。structs保存する必要がある要素の最大数がコンパイル時にわかっている場合は、通常、配列を使用します。structsただし、保存する必要がある要素の最大数がわからない場合は、リンクされたリストが役立ちます。また、リンクされたリストでは、要素の数が変更されたり、要素が追加および削除されたりする場合があります。

于 2012-05-04T19:10:59.703 に答える
0

リンク リストは、要素の順序が重要で、要素の数が事前にわからない場合に便利です。また、連結リスト内の要素へのアクセスには O(n) 時間がかかります。リスト内の要素を探す場合、最悪の場合、リストのすべての要素を調べなければなりません。

配列の場合、その数は事前にわかっている必要があります。C で配列を定義するときは、そのサイズを渡す必要があります。一方、要素はインデックスでアドレス指定できるため、配列要素へのアクセスには O(1) 時間がかかります。リンクされたリストでは、それは不可能です。

ただし、リンクされたリストと配列の概念は C++ に関連付けられていないため、これは C++ 関連の質問ではありません。

于 2012-05-04T19:04:08.593 に答える