0

我正在研究数据结构，但我不明白为什么需要像这样声明堆栈和队列：

struct stack *Stack;

（忘记struct语法）

我的意思是，为什么它总是被声明为指针？

4

5 回答 5

4

他们并不总是这样宣布！

通常，将变量声明为指针对于以后动态分配它很有用。这可能是由于以下几个原因：

  • 变量对于程序堆栈来说太大了
  • 您想从函数中返回该变量

在您的情况下，让我们考虑两种不同的堆栈实现：

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

但是，固定大小的数组是有限制的。实现堆栈的一种简单方法是使用列表结构：

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
  ...
}

由于pushandpop需要能够将新的指针值写入mystack，我们需要将指针传递给它，因此stackinpush和的双重间接pop。

于 2012-10-30T16:10:56.447 回答
0

真的没有必要用指针来实现堆栈和队列——其他人已经清楚地说明了这个事实。查看@JohnBode 关于如何使用数组完美实现堆栈的答案。问题是，使用指针对某些数据结构（例如堆栈、队列和链表）进行建模，可以让您在执行速度和内存消耗方面以非常有效的方式对其进行编程。

通常，如果您的用例需要频繁随机访问结构中的元素，则用于保存数据结构的底层数组是非常好的实现选择，因为它是位置索引（这是 FAST 与数组）。但是，将结构扩展到其初始容量可能会很昂贵，并且您会在数组中未使用的元素上浪费内存。插入和删除操作也可能非常昂贵，因为您可能需要重新排列元素以压缩结构或为新元素腾出空间。

由于队列和堆栈没有这种随机访问要求，并且您不会在它们中间插入或删除元素，因此“动态”动态分配每个单独的元素，请求内存是更好的实现选择当需要一个新元素时（这就是 malloc 所做的），并将其作为一个元素释放将被删除。这很快，并且不会消耗比您的数据结构实际需要的内存更多的内存。

于 2012-10-30T17:33:42.933 回答
0

不，它们不必被声明为指针。

也可以将堆栈和队列分配为全局变量：

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

myHash 还包括一个使用索引的重复条目的链接列表。

但正如评论中所述，如果必须向结构添加更多元素，这是最初计划的，那么指针就派上用场了。

将结构声明为指针的另一个原因是，通常使用指针可以访问整个结构、结构的任何单个元素或元素的某些子集。这使得语法更加通用。此外，当结构作为参数传递给某个外部函数时，指针是不可避免的。

于 2012-10-30T15:02:28.683 回答
0

正如 aleady 指出的那样，这取决于结构有多大。

另一个原因是封装。stack 实现可能不会在其头文件中公开 struct stack 的定义。这对用户隐藏了实现细节，缺点是需要免费的存储分配。

于 2012-10-30T21:00:58.773 回答