0

私はデータ構造を勉強していますが、スタックとキューを次のように宣言する必要がある理由がわかりません。

struct stack *Stack;

struct（構文は忘れてください）

つまり、なぜ常にポインターとして宣言されるのですか?

4

5 に答える 5

4

彼らは常にそのように宣言されているわけではありません!

一般に、変数をポインターとして宣言すると、後で動的に割り当てるのに役立ちます。これには、いくつかの理由が考えられます。

  • 変数がプログラム スタックに対して大きすぎます
  • 関数からその変数を返したい

あなたの場合、スタックの 2 つの異なる実装を考えてみましょう。

struct stack
{
    void *stuff[10000];
    int size;
};

これはひどい実装ですが、このようなものを持っていると仮定すると、おそらくプログラム スタックに置きたくないでしょう。

または、次の場合:

struct stack
{
    void **stuff;
    int size;
    int mem_size;
};

とにかくのサイズを動的に変更するため、プログラムスタックstuffで型の変数を宣言してもまったく害はありません。つまり、次のようになります。struct stack

struct stack stack;

それ以外の場合は、関数から返したいと思うでしょう。例えば：

struct stack *make_stack(int initial_size)
{
    struct stack *s;

    s = malloc(sizeof(*s));
    if (s == NULL)
        goto exit_no_mem;

    if (initial_size == 0)
        initial_size = 1;
    s->stuff = malloc(initial_size * sizeof(*s->stuff));
    if (s->stuff == NULL)
        goto exit_no_stuff_mem;

    s->size = 0;
    s->mem_size = initial_size;

    return s;
exit_no_stuff_mem:
    free(s);
exit_no_mem:
    return NULL;
}

ただし、個人的には、次のように関数を宣言します。

int make_stack(struct stack *s, int initial_size);

struct stackプログラムスタックに割り当てます。

于 2012-10-30T15:01:56.760 に答える
1

スタック構造がどのように定義されているかによって異なります (のレイアウトだけstructでなく、それを操作する操作も同様です)。

次のように、スタックを単純な配列とインデックスとして定義することは完全に可能です。

struct stack_ {
  T data[N]; // for some type T and size N
  size_t stackptr; // Nobody caught that error, so it never existed, right? ;-)
} stack;

stack.stackptr = N; // stack grows towards 0

// push operation
if (stack.stackptr)
  stack.data[--stack.stackptr] = some_data();
else
  // overflow

// pop operation
if (stack.stackptr < N)
  x = stack.data[stack.stackptr++];
else
  // underflow

ただし、固定サイズの配列には制限があります。スタックを実装する簡単な方法の 1 つは、リスト構造を使用することです。

struct stack_elem {
  T data;
  struct stack_elem *next;
};

リストの先頭がスタックの一番上にあるという考え方です。アイテムをスタックにプッシュすると、リストの先頭に要素が追加されます。アイテムをポップすると、その要素がリストの先頭から削除されます。

int push(struct stack_elem **stack, T data)
{
  struct stack_elem *s = malloc(sizeof *s);
  if (s)
  {
    s->data = data;   // new element gets data
    s->next = *stack; // set new element to point to current stack head
    *stack = s;       // new element becomes new stack head
  }
  return s != NULL;
}

int pop(struct stack_elem **stack, T *data)
{
  int stackempty = (*stack == NULL);

  if (!stackempty)
  {
    struct stack_elem *s = *stack; // retrieve the current stack head
    *stack = (*stack)->next;       // set stack head to point to next element
    *data = s->data;               // get the data
    free(s);                       // deallocate the element
  }

  return r;
}

int main(void)
{
  struct stack_elem *mystack = NULL; // stack is initially empty
  T value;
  ...
  if (!push(&mystack, some_data()))
    // handle overflow
  ...
  if (!pop(&mystack, &value))
    // handle underflow
  ...
}

pushとpopは新しいポインター値を に書き込める必要があるためmystack、ポインターを渡す必要がstackありpushますpop。

于 2012-10-30T16:10:56.447 に答える
0

aleadyが指摘したように、それは構造体の大きさに依存します。

もう1つの理由はカプセル化です。スタック実装は、ヘッダーファイルで構造体スタックの定義を公開しない場合があります。これにより、実装の詳細がユーザーから隠されますが、無料のストア割り当てが必要になるという欠点があります。

于 2012-10-30T21:00:58.773 に答える
0

いいえ、ポインターとして宣言する必要はありません。

スタックとキューをグローバル変数として割り当てることもできます:

struct myHash { int key; int next_idx; int data[4]; } mainTable[65536];
struct myHash duplicates[65536*10];
int stack[16384];

myHash には、インデックスを使用した重複エントリのリンク リストも含まれています。

しかし、コメントで述べたように、最初に計画されていた構造にさらに要素を追加する必要がある場合は、ポインターが便利です。

構造体をポインターとして宣言するもう 1 つの理由は、通常、ポインターを使用すると、完全な構造体全体、構造体の個々の要素、または要素のサブセットの両方にアクセスできるためです。これにより、構文がより用途が広くなります。また、構造体がパラメーターとして外部関数に渡される場合、ポインターは避けられません。

于 2012-10-30T15:02:28.683 に答える
0

ポインターを使用してスタックとキューを実装する必要は実際にはありません-他の人はすでにこの事実を明確に述べています。配列を使用してスタックを完全に実装する方法については、@JohnBode の回答を参照してください。問題は、ポインターを使用して特定のデータ構造 (スタック、キュー、リンクされたリストなど) をモデル化すると、実行速度とメモリ消費の両方の点で非常に効率的な方法でそれらをプログラミングできることです。

通常、データ構造を保持するための基礎となる配列は、ユースケースで構造内の要素への頻繁なランダムアクセスが必要な場合に非常に適した実装の選択肢です (これは配列の FAST です)。ただし、初期容量を超えて構造体を成長させると、コストがかかる可能性があり、配列内の未使用の要素でメモリが浪費されます。構造をコンパクトにするか、新しい要素のためのスペースを作るために要素を再配置する必要がある場合があるため、挿入および削除操作も非常に高価になる可能性があります。

キューとスタックにはこのランダムアクセス要件がなく、それらの途中で要素を挿入または削除しないため、個々の要素を「その場で」動的に割り当ててメモリを要求する方が実装の選択肢として適しています。新しい要素が必要な場合 (これは malloc が行うことです)、要素として解放すると削除されます。これは高速で、データ構造が実際に必要とする以上のメモリを消費しません。

于 2012-10-30T17:33:42.933 に答える