c - popStack 弹出我没有push的数据(stack adt)

Question

这是一段压入 0 和 1 并再次弹出 1 和 0 的代码。但是，它会弹出 2 和 2。我似乎不明白为什么。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "stackADT.h"

int main (void)
{
  STACK* stack;
  int data;

  stack = createStack ();

  int i;
  for (i = 0; i < 2; i++)
  {
    printf("insert %d\n", i);
    pushStack (stack, &i);
    //printf("count: %d\n", stackCount (stack));
    //data = *(int*) popStack (stack);
    //printf("%d popped\n", data);
  }


  while (!emptyStack (stack))
  {

    data = *(int*) popStack (stack);
    printf("%d popped\n", data);
  }
}

这是输出。

insert 0
insert 1
2 popped
2 popped

当我尝试使用 for (i = 0; i < 5; i++) 时，这就是发生的事情。

insert 0
insert 1
insert 2
insert 3
insert 4
5 popped
5 popped
5 popped
5 popped
5 popped

我正在附加 stackADT.h。(此代码来自数据结构:Richard F. Gilbert 和 Behrouz A. Forouzan 的 C 伪代码方法)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Structure Declarations
typedef struct node
  {
  void* dataPtr;
  struct node* link;
  } STACK_NODE;

typedef struct
  {
  int count;
  STACK_NODE* top;
  } STACK;

// Prototype Declarations
STACK* createStack (void);
bool pushStack (STACK* stack, void* dataInPtr);
void* popStack (STACK* stack);
void* stackTop (STACK* stack);
bool emptyStack (STACK* stack);
bool fullStack (STACK* stack);
int stackCount (STACK* stack);
STACK* destroyStack (STACK* stack);


/* =============== createStack ==================
  Creates an empty stack
    Pre Nothing
    Post Returns pointer to a null stack
      -or- NULL if overflow
*/
STACK* createStack (void)
{
  // Local Declarations
  STACK* stack;

  // Statements
  stack = (STACK*) malloc(sizeof (STACK));
  if (stack)
    {
      stack->count = 0;
      stack->top = NULL;
    } // if

  return stack;
} // createStack


/* ================ pushStack =================
    Pre stack: STACK*
        dataInPtr: data* to be inserted

    Post data inserted into stack
    Return true if successful; flase if underflow

*/
bool pushStack (STACK* stack, void* dataInPtr)
{
  // Local Declarations
  STACK_NODE* newPtr;

  // Statements
  newPtr = (STACK_NODE*) malloc(sizeof(STACK_NODE));
  if (!newPtr)
    return false;

  newPtr->dataPtr = dataInPtr;
  newPtr->link = stack->top;
  stack->top = newPtr;

  (stack->count)++;
  return true;
} // pushStack


/* ================ popStack ====================

*/
void* popStack (STACK* stack)
{
  //Local Definitions
  void* dataOutPtr;
  STACK_NODE* temp;

  //Statements
  if (stack->count == 0)
    dataOutPtr = NULL;
  else
    {
      temp = stack->top;
      dataOutPtr = stack->top->dataPtr;
      stack->top = stack->top->link;
      free(temp);
      (stack->count)--;
    }
  return dataOutPtr;
}



/* ================ stackTop =========================

*/
void* stackTop (STACK* stack)
{
  //Local Definitions
  //Statements
  if (stack->count == 0)
    return NULL;
  else
    return stack->top->dataPtr;
} // stackTop

/* ================== emptyStack =====================
  returns: 1 if the stack is empty; 0 otherwise
*/
bool emptyStack (STACK* stack)
{
  // Statements
  return (stack->count == 0);
} // emptyStack


/* ================= fullStack =======================
  determines if a stack is full
  Full == heap full

  returns: true if heap full; false otherwise
*/
bool fullStack (STACK* stack)
{
  // local definitions
  STACK_NODE* temp;
  // statements
  if ((temp =
    (STACK_NODE*) malloc(sizeof(*(stack->top)))))
    {
      free(temp);
      return false;
    } //if
  // malloc failed
  return true;
} // fullStack




/* ============== stackCount ====================
  returns: int, stack count
*/
int stackCount (STACK* stack)
{
  return stack->count;
}


/* ============== destroyStack ===================
    release all nodes to the heap
  returns: null pointer
*/
STACK* destroyStack (STACK* stack)
{
  //local definitions
  STACK_NODE* temp;
  //statements
  if (stack)
    {
      //Delete all nodes in stack
      while (stack->top != NULL)
        {
          free(stack->top->dataPtr);

          temp = stack->top;
          stack->top = stack->top->link;
          free(temp);
        } // while
      // Stack now empty. Destroy stack head node.
      free(stack);
    }
  return NULL;
} // destoryStack

和我的 gcc 版本。

$ gcc --version
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)
Target: x86_64-apple-darwin14.3.0
Thread model: posix

Answer 1

for (i = 0; i < 2; i++)
{
    ...
    pushStack (stack, &i);  // Push address of i
}

您正在推送 i 的(相同)地址两次。循环结束后包含 2。当您弹出时，您会得到包含 2 的地址，因此两次输出都是 2。

Stack:
+----+    &i
| &i |\  +----+
+----+ \ | 02 |
| &i | / +----+
+----+/

一些可能的解决方案是:

• 不存储地址，而是创建一个新节点并复制要推送的地址的内容。
• 存储数据而不是指针。