8

C での連結リストの実装でポインターを使用することが重要なのはなぜですか?

例えば：

typedef struct item                                     
{
    type data;
    struct item *next;
} Item;

typedef struct list                                          
    Item *head;
} List;

ポインターなしで同じ実装を使用するとどうなりますか?

4

7 に答える 7

14

まあ、あなたはこのようなもので終わるでしょう

typedef struct item                                     
{
    type data;
    struct item next;
} Item;

これで、C コンパイラは がどれくらい大きいかを把握しようとしますItem。しかし、nextは に埋め込まれItemているため、最終的には次のような方程式になります。

size-of-Item = size-of-type + size-of-Item

これは無限です。したがって、問題があります。このため、C ではポインターが必要なので、

size-of-Item = size-of-type + size-of-pointer

これは閉じています。さらに興味深いことに、Java、Python、または Haskell などの言語でこれを行う場合でも、サイクルを断ち切るためにポインター (参照と呼ばれます) を暗黙的に格納していることになります。彼らはあなたにその事実を隠しているだけです。

于 2013-07-16T12:42:36.333 に答える
8

リンク リストのインターフェイスを公開するデータ構造を実装するためにポインターを実際に使用する必要はありませんが、リンク リストのパフォーマンス特性を提供するために必要です。

ポインターの代わりになるものは何ですか? さて、item次の項目を参照する何らかの方法が必要です。さまざまな理由で次の項目を集約できません。そのうちの 1 つは、これにより構造体が「再帰的」になり、実現できないことです。

// does not compile -- an item has an item has an item has an item has...
typedef struct item                                     
{
    type data;
    struct item next;
} Item;

あなたができることは、アイテムの配列を持ち、その上にリンクされたリストを実装することです:

Item *storage[100];

typedef struct item                                     
{
    type data;
    int next; // points to the index inside storage of the next item
} Item;

これは機能するようです。リストにアイテムを追加する関数と、それらを削除する別の関数を使用できます。

void add_after(Item *new, Item *existing);
void remove(Item *existing);

existingこれらの関数は、配列から削除して (next前の項目の「ポインター」を更新するように注意して) 空のスロットを作成するか、existing項目を見つけて空のスロットに挿入newしますstorage(そこを指すように更新nextします)。

これに関する問題は、スペースがなくなるたびに配列を検索して再割り当てする必要があるため、 add_afterand操作を一定時間で実現できないことです。remove

一定時間の追加/削除が人々がリンクされたリストを使用する理由であるため、これにより、非ポインターアプローチは知的な演習としてのみ役立ちます。実際のリストの場合、ポインターを使用すると、これらの操作を一定の時間で実行できます。

于 2013-07-16T12:43:10.930 に答える
4

ポインターは、メモリの動的割り当てに使用されます。

リストを単純な配列として実装できますが、それは連続したメモリ領域を割り当てることを意味し、大きなリストでは効率的ではありません。また、配列は cu の拡張がより困難です (最大サイズに達した場合は、配列を再割り当てする必要があります)。

したがって、動的割り当ては大きなリストに適しています。各要素について、連続的または非連続的に任意の場所にメモリに割り当てることができ、簡単に拡張できます。

また、構造がまだ定義されておらず、構造のサイズを確立できないため、別の構造に格納することはできません。struct itemstruct item

これはできません:

typedef struct item                                     
{
    type data;
    struct item next;
} Item;

したがって、構造体がコンパイルされるときにポインターのサイズ (そのプラットフォームでの整数のサイズ) を判別できるため、ポインターが使用されます。

于 2013-07-16T12:45:31.563 に答える
3

C でリストを作成するためにポインターは必要ありません。ポインター リストが望ましいかどうかは、アプリケーションによって異なります。人々は、言語に実装されたポインターの概念を持たないうちに、連結リストを使用していました。一部の人々にとっては（ポインターを使用して）理解するのが簡単な場合があります。データを含む構造も必要ありません。

単純な配列で十分です。必要なもの:

  • インデックスを保持する 1 つの整数配列 (これはポインターに似ています)。配列の内容は、-1(nilまたはNULLポインター用語0 .. N-1で意味する)、または のいずれかです。次のリンクされた要素の配列インデックスを意味します。index-array の indexは、データ配列内の item のインデックスを表します。
  • 上記の「リスト」内で「接続」されるデータ用の 1 つの配列。

それだけです。

ポインタリストの代わりに配列が

  • データの量が変わらない (増えない) 場合は、利点があります。この場合、利点は非常に大きくなる可能性があります。遭遇するデータの最大数を知っていて、事前にデータを割り当てることができる場合、配列の実装は、ポインターでリンクされたリストよりもはるかに高速になります。特に、挿入するだけで、削除する必要がない場合。
  • それ以外のデメリット。この場合、デメリットは非常に大きくなる可能性があります。

ここまで読んでください。

したがって、あなたの例は次のようになります。

type data[N];  // or: type *data = new type [N];
int links[N];  // or:  int *links = new int [N];

簡単なテスト ケースを開始するために必要なのは、これだけです。

于 2013-07-16T12:49:10.470 に答える
1

cにおけるポインタの重要性

利点:-

  1. 実行速度が速くなります。

  2. ポインターを使用すると、関数の外部にある変数にアクセスできます。

  3. コードのサイズを縮小します。

ポインターなし:-

  1. コードサイズが大きくなります。

  2. データを効率的に維持できません。

  3. リストでは、ポインターはリストの次のアイテムを指すために使用されます。ポインターが宣言されていない場合、リストから複数のアイテムにアクセスできないことを意味します。

  4. 実行時に動的にメモリを割り当てると、実際にはポインターが非常に必要になります。

于 2013-07-16T12:47:03.667 に答える
0

「リスト」には複数の種類があります。あなたが示す実装は「リンクされたリスト」です。ポインターがなければ「リンク」は存在しないため、他の種類のリストを調べる必要があります。

*まず、構造体定義から を削除するとどうなるか: コンパイルされません。別の構造体の中に構造体を含めることができますが、再帰がある場合、構造体は無限のサイズになり、起こりません!

リストとしての配列はどうですか：

struct item list[100];

うん、それはうまくいくだろうが、今あなたのリストは固定サイズです。

それでは、リストを動的に割り当てましょう。

struct item *list = malloc(sizeof(struct item));

次に、リストに追加するたびに、これを行う必要があります。

list = realloc(list, newcount * sizeof(struct item));
list[newitem] = blah;

それはうまくいきましたが、今ではメモリを頻繁に再割り当てしているため、大量のメモリ コピーが発生し、効率が低下しています。

一方、リストの更新頻度が非常に低い場合、これはスペース効率が高く、良いことかもしれません。

配列を使用することのもう 1 つの欠点は、push、pop、sort、reverse などの操作のコストがはるかに高くなることです。それらはすべて複数のメモリコピーを意味します。

「リスト」には他にも種類がありますが、それらはすべてポインターを伴うため、ここでは無視してよいと思います。

于 2013-07-16T12:49:12.153 に答える