我正在为一个班级写这个程序。该程序是一个使用堆栈的简单括号检查器应用程序。在这种情况下,我使用静态数组来实现堆栈数据结构。该程序运行良好,但是我遇到了运行时错误,到目前为止,仍然无法看到问题的根源。

这是我所知道的很少信息,该问题可能是由于尝试释放未使用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]:添加了字符的堆栈接口例程。

最佳答案

错误消息告诉您您将值0x7b传递给free。这么小的数字永远不会是malloc返回的内存块的地址。因此,大概有三种可能性:


您有一个完全未初始化的指针,恰好以0x7b结尾,并将其传递给free
您已从包含0的指针开始,将其递增0x7b,并将其传递给free
您还有其他一些创造性的内存损坏错误,已用0x7b替换了有效的指针值。


最快的出路是在valgrind下运行您的程序,并让它告诉您这一切在哪里发生。您还可以在gdb中的任意位置放置断点,然后看看您看到了什么。

10-06 15:07