c - (在 C 中)使用数组实现堆栈 - 将数组大小时加倍时出现运行时错误

标签 c arrays stack double runtime-error

当我的数组已满时,我在 doublestack() 函数中使用 realloc() 将其加倍。这样做两次以上会给我一个运行时错误。 我想这可能是因为原始堆栈(使用 create() 函数创建)的大小仍然相同,所以我也将其加倍,并且消除了运行时错误。

我的问题:

  1. 这是实际发生的事情吗?数组每增加一倍,栈就需要增加一倍?

  2. 如果是,为什么原始堆栈首先能够支持对 doublestack() 的第一次和第二次调用?

  3. 您能否给我一个图形/内存映射解释,说明当我们重新分配()数组和堆栈时到底发生了什么?

  4. 我是不是在浪费内存?有没有更好的方法用数组来实现栈?

非常感谢您的宝贵时间。

CODE 和 OUTPUTS :(取消注释它说 UNCOMMENT to double stack size using realloc())

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

#define INIT_CAPACITY 1

struct stack
{
    int top;
    int capacity;
    int *array;
};

struct stack * create(int);
void push(struct stack *,int);
int top(struct stack *);
int isfull(struct stack *);
int isempty(struct stack *);
void traverse(struct stack *);
struct stack *doublestack(struct stack *);
int pop(struct stack *);

int main()
{
    struct stack *S=create(INIT_CAPACITY);
    push(S,1);
    push(S,2);//First call to doublestack()
    push(S,3);//Second call to doublestack()
    push(S,4);
    push(S,5);//Third call to doublestack() - ERROR
    traverse(S);
}

struct stack * create(int capacity)//create a new stack with INIT_CAPACITY
{
    struct stack *newstack=(struct stack *)malloc(sizeof(struct stack));
    if(!newstack)   return NULL;
    newstack->top=-1;
    newstack->capacity=capacity;
    newstack->array=(int *)malloc(sizeof(int)*(newstack->capacity));
    return newstack;

}

void push(struct stack *s,int data)
{
    printf("\nCurrent stack is");
    traverse(s);
    printf("\nPushing %d onto stack:\n\n",data);
    if(isfull(s))
    {
        printf("\nStack is FULL.Now doubling...\n\n");
        doublestack(s);
    }
    (s->top)++;
    s->array[s->top]=data;
}

struct stack * doublestack(struct stack *s)//using realloc()
{
    s=realloc(s,(sizeof(struct stack)*2));//**UNCOMMENT THIS TO ELIMINATE ERROR**
    s->capacity *= 2;
    s->array=realloc(s->array,s->capacity);
}

void traverse(struct stack *s)
{
    printf("\n");
    int i;
    for(i=0;i <= s->top;i++)
    {
        printf("%d\t",s->array[i]);
    }
    printf("\n\n");
}

int top(struct stack *s)
{
    return s->array[s->top];
}

int isfull(struct stack *s)
{
    return (s->capacity)-1==s->top;
}

int isempty(struct stack *s)
{
    return s->top==-1;
}

int pop(struct stack *s)
{
    if(isempty(s))
    {
        printf("\nStack is EMPTY\n\n");
        return 0;
    }
    int data=s->array[s->top];
    s->top--;
    return data;
}

输出 1:(没有加倍堆栈,因此有运行时错误)

Current stack is

Pushing 1 onto stack:

Current stack is
1   

Pushing 2 onto stack:

Stack is FULL.Now doubling...

Current stack is
1   2   

Pushing 3 onto stack:

Stack is FULL.Now doubling...

Current stack is
1   2   3   

Pushing 4 onto stack:

Current stack is
1   2   3   4   

Pushing 5 onto stack:

Stack is FULL.Now doubling...

*** glibc detected *** ./a.out: realloc(): invalid next size: 0x09191018 ***
======= Backtrace: =========
/lib/i386-linux-gnu/i686/cmov/libc.so.6(+0x70f01)[0xb75e5f01]
/lib/i386-linux-gnu/i686/cmov/libc.so.6(+0x7660d)[0xb75eb60d]
/lib/i386-linux-gnu/i686/cmov/libc.so.6(realloc+0xdd)[0xb75eb8ed]
./a.out[0x8048674]
./a.out[0x804861c]
./a.out[0x8048569]
/lib/i386-linux-gnu/i686/cmov/libc.so.6(__libc_start_main+0xe6)[0xb758be46]
./a.out[0x8048421]
======= Memory map: ========
08048000-08049000 r-xp 00000000 08:07 549947     /home/user/a.out
08049000-0804a000 rw-p 00000000 08:07 549947     /home/user/a.out
09191000-091b2000 rw-p 00000000 00:00 0          [heap]
b7400000-b7421000 rw-p 00000000 00:00 0 
b7421000-b7500000 ---p 00000000 00:00 0 
b7546000-b7562000 r-xp 00000000 08:07 548        /lib/i386-linux-gnu/libgcc_s.so.1
b7562000-b7563000 rw-p 0001b000 08:07 548        /lib/i386-linux-gnu/libgcc_s.so.1
b7574000-b7575000 rw-p 00000000 00:00 0 
b7575000-b76d1000 r-xp 00000000 08:07 468        /lib/i386-linux-gnu/i686/cmov/libc-2.13.so
b76d1000-b76d2000 ---p 0015c000 08:07 468        /lib/i386-linux-gnu/i686/cmov/libc-2.13.so
b76d2000-b76d4000 r--p 0015c000 08:07 468        /lib/i386-linux-gnu/i686/cmov/libc-2.13.so
b76d4000-b76d5000 rw-p 0015e000 08:07 468        /lib/i386-linux-gnu/i686/cmov/libc-2.13.so
b76d5000-b76d8000 rw-p 00000000 00:00 0 
b76e8000-b76eb000 rw-p 00000000 00:00 0 
b76eb000-b76ec000 r-xp 00000000 00:00 0          [vdso]
b76ec000-b7708000 r-xp 00000000 08:07 504        /lib/i386-linux-gnu/ld-2.13.so
b7708000-b7709000 r--p 0001b000 08:07 504        /lib/i386-linux-gnu/ld-2.13.so
b7709000-b770a000 rw-p 0001c000 08:07 504        /lib/i386-linux-gnu/ld-2.13.so
bfb34000-bfb55000 rw-p 00000000 00:00 0          [stack]
Aborted

输出 2:(堆栈加倍且没有错误)

Current stack is

Pushing 1 onto stack:

Current stack is
1   

Pushing 2 onto stack:

Stack is FULL.Now doubling...

Current stack is
1   2   

Pushing 3 onto stack:

Current stack is
1   2   3   

Pushing 4 onto stack:

Current stack is
1   2   3   4   

Pushing 5 onto stack:

1   2   3   4   5   

最佳答案

s->capacity 存储堆栈中的项目数。每个项目的大小为 sizeof(int)。 realloc 的第二个参数是 bytes 的数量,就像 malloc 一样。

s->array=realloc(s->array,s->capacity);

你想要

s->array=realloc(s->array, s->capacity * sizeof(int));

或者更一般的

s->array = realloc(s->array, s->capacity * sizeof(*(s->array)));

此外,您应该检查 realloc 的返回值并处理发生的任何错误。

这段代码是废话:

s=realloc(s,(sizeof(struct stack)*2));//**UNCOMMENT THIS TO ELIMINATE ERROR**

首先,如果 realloc 决定移动您的数组,您不会将新的 返回给调用者。但更重要的是,您需要调整数组的大小,而不是它周围的元数据。取消注释该行隐藏了问题,这只是巧合。

关于c - (在 C 中)使用数组实现堆栈 - 将数组大小时加倍时出现运行时错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25214343/

相关文章:

c - C 中的 realloc 与 malloc

c# - WCF (WCF-Binding) in/with C/C++

c++ - 在 C++ 中,我是否为我不吃的东西买单?

调用 opendir 和 readdir 正在更改我的 char 数组

c++ - 堆栈输出错误

c - 在 C 中将数组存储为链表

ios - 从数组 Swift 中按字母生成排序字典

c - 为什么不能将在函数内部创建的数组传递给指针?

optimization - 程序堆栈和数据段之间的距离对 CPU 缓存有影响吗?

linux - gcc -mpreferred-stack-boundary 选项