0

我正在为一堂课编写这个程序。该程序是一个使用堆栈的简单括号检查器应用程序。在这种情况下，我使用了静态数组来实现堆栈数据结构。该程序构建良好，但我遇到了这个运行时错误，到目前为止还无法看到问题可能出在哪里。

这是我确实了解的很少信息，问题可能是由于尝试释放未使用 malloc 分配的内存。但在下面的代码中，我看不出这可能发生在哪里。

下面是使用静态数组的栈的接口实现代码。我还添加了堆栈接口代码以在堆栈上添加字符和驱动程序以测试例程。

#include "stack.h"
#include "stdlib.h" /* malloc, free */
#include "stdio.h"

#define MAXSTACKSIZE 10

struct stack_record {
  generic_ptr base[MAXSTACKSIZE];
  generic_ptr * top;
};

unsigned int num_elements(stack * const p_S)
{
  unsigned int numels = ((*p_S)->top - (*p_S)->base);
  /*  return ((*p_S)->top - (*p_S)->base); */
  printf("number of elements in the stack is: %u\n", numels);
  return numels;
}
status init_stack(stack * const p_S)
{
  stack_record * record = (stack_record *)malloc(sizeof(stack_record));
  if(record == NULL) {
    return ERROR;
  }
  record->top = record->base;
  *p_S = record;
  return OK;
}
bool empty_stack(stack * const p_S)
{
  if(num_elements(p_S) == 0)
    {
      printf("stack is EMPTY!\n");
      return TRUE;
    }
  else
    {
      printf("stack NOT Empty!\n");
      return FALSE;
    }
}
status push(stack * const p_S, generic_ptr const data)
{
  if (num_elements(p_S) == MAXSTACKSIZE)
    return ERROR;

  *( (*p_S)->top ) = data;
  (*p_S)->top++;
   return OK;
}

status pop(stack * const p_S, generic_ptr * const p_data)
{
  if (empty_stack(p_S) == TRUE)
    return ERROR;
  *p_data = *((*p_S)->top);
  (*p_S)->top--;
  /*  ((*p_S)->top)--; */
  return OK;
}

status top(stack *const p_S, generic_ptr * const p_data)
{
   if (pop(p_S, p_data) == ERROR)
    return ERROR;

  return push(p_S, *p_data);
}

void destroy_stack(stack * const p_S, void (* const p_func_f)())
{
  if ((p_func_f) != NULL) {
    generic_ptr * curr;    
    for(curr = (*p_S)->top;
    curr != (*p_S)->base;
    ++curr)
          (*p_func_f)(*curr);
  }
  free(*p_S); /*free the dynamically allocated memory on the heap */
  *p_S = NULL;
 }

以下是字符的堆栈接口例程：

/*************************************************************************/
/* adapted from Esakov and Weiss, Section 5.2                            */
/*************************************************************************/

#include "char_stack.h"
#include "stdlib.h" /* malloc */
#include "stdio.h"
#define DEBUG 1 

status push_char(stack * const p_S, char const c)
{
  /*
   *     Push the character c onto the stack.
   */
  char * p_c = (char *) malloc(sizeof(char));

  if(p_c == NULL)
    return ERROR;
  *p_c = c;

  if(DEBUG)
  /* Debug code: begin */
  {
    printf("Character to PUSH on the stack: %c\n", *p_c);
  }
  /* Debug code: end */

  if (push(p_S, (generic_ptr)p_c) == ERROR) {
    if(DEBUG)
      printf("char_stack: push_char: failed to push the character on the stack!\n");
    free(p_c);
    return ERROR;
  }
  return OK;
}

status pop_char(stack * const p_S, char * const p_c)
{
  /*
   *     Pop the stack. Return the character in p_c.
   */

  generic_ptr p_data;

  if( pop(p_S, &p_data) == ERROR)
    return ERROR;

  *p_c = *((char*)p_data);

  if(DEBUG)
  /*Debug code: begin */
printf("char_stack.c::pop_char: Character to POP on the stack: %c\n", *p_c);

  /*Debug code: end */

   free(p_data);
   return OK;
}

status top_char(stack * const p_S, char * const p_c)
{
  /*
   *     Return the top character from the stack in p_c
   */
  generic_ptr p_data;

  if (top(p_S, &p_data) == ERROR)
    return ERROR;

  *p_c = *((char *)p_data); 
  return OK;
}

应用程序的驱动程序：

/**************************************************************************/
/* adapted from Esakov and Weiss, Section 5.2                             */
/**************************************************************************/

#include "stdio.h"
#include "stdlib.h"
#include "char_stack.h"

char matching_symbol(char const c)
{
  switch(c) {
    case '(': return ')';
    case ')': return '(';
    case '}': return '{';
    case '{': return '}';
    case '[': return ']';
    case ']': return '[';
  }
  return 0;
}

status consume_char(stack * const p_S, char input)
{
  switch (input) {
    case '(':
    case '{':  
    case '[':
      return push_char(p_S, input); 
    case ')':
    case '}':
    case ']':
      { 
        char c;    
        if (pop_char(p_S, &c) == ERROR || c != matching_symbol(input)) { 
          return ERROR;
        } else {
          return OK;
        }
      }
    default:
      return OK; 
  }
}

int main(int argc, char * argv[])
{

  if (argc == 1) {
    exit(EXIT_SUCCESS);
  }

  {
    stack S;

    init_stack(&S);

    {
      char *ptr;
      for (ptr = argv[1];
           *ptr != '\0' && consume_char(&S, *ptr) == OK;
           ++ptr); 
      if (*ptr == '\0' && empty_stack(&S)) { 

    destroy_stack(&S,free);
        exit(EXIT_SUCCESS);
      } else {
    destroy_stack(&S,free);
        exit(EXIT_FAILURE);
      }
    }
  }  

  exit(EXIT_SUCCESS);  
}

我想在驱动程序中补充一点，我已经缩小了对销毁堆栈的调用是触发此问题的原因。但我已经查看了这段代码，并认为这段代码很好，问题出在其他地方。

[编辑 1]：为了完整起见，我在调用这些函数的位置附加了驱动程序代码。[编辑 2]：添加了字符的堆栈接口例程。

4

2 回答 2

1

错误消息告诉您您将值 0x7b 传递给free. 这么小的数字永远不会是从返回的内存块的地址malloc。所以，粗略地说，有三种可能：

  1. 你有一个完全未初始化的指针，它恰好以 0x7b 结束，你将它传递给free.
  2. 您从一个包含 0 的指针开始，将其递增 0x7b，然后将其传递给free.
  3. 您有一些更具创造性的内存损坏错误，已将有效指针值替换为 0x7b。

最快的出路是在 valgrind 下运行你的程序，让它告诉你这一切发生在哪里。您也可以在 gdb 中到处放置断点，然后查看您看到的内容。

于 2012-10-14T21:20:27.957 回答
0

在main函数的末尾，您将free作为函数指针作为第二个参数传递给destroy_stack. 这一点是针对free当前在堆栈上的所有数据元素（如果有的话）。但是，只有在将项目添加到堆栈时push用于分配内存的函数才允许释放此内存。malloc

在给定的实现中，堆栈不负责为项目分配内存，因此它可能不应该尝试释放该内存。在任何一种情况下，寻找差异的地方都可能在函数中push_char：

看起来push_char正在尝试推送一个简单的 '{' 字符（顺便说一句，这是0x7B），而不是指向malloc堆栈所期望的某些内存的指针。

更新

从头开始我push_char在上一段中所说的 - 问题在于destroy_stack，这一行：

(*p_func_f)(*curr);    /* Incorrect */

curr是指向为单个字符（由 分配push_char）分配的一些内存的指针，并且*p_func_f是free()函数。你能看出问题吗？

将其curr传递给*p_func_f. 相反，只需传递原始指针：

(*p_func_f)(curr);     /* Correct */

发现这一点的关键与我上面提到的相同：“内存地址”0x7b实际上是字符“{”，它是存储在堆栈中的数据——这强烈表明该free函数正在接收原始数据而不是指向该数据的指针。

于 2012-10-15T05:04:24.407 回答