我正在为一个班级写这个程序。该程序是一个使用堆栈的简单括号检查器应用程序。在这种情况下,我使用静态数组来实现堆栈数据结构。该程序运行良好,但是我遇到了运行时错误,到目前为止,仍然无法看到问题的根源。
这是我所知道的很少信息,该问题可能是由于尝试释放未使用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中的任意位置放置断点,然后看看您看到了什么。