使用Realloc时，缩小个人实施中的堆栈崩溃

Question

在个人实现数据结构中，我正在遇到缩小堆栈大小的问题。

我想是由于realloc（）的不良使用。执行时（spop（），empty（））（如果我删除realloc并减少元素的数量，则工作正常），程序刚刚结束（崩溃）。

在实施中使用该功能的更好方法是什么，或者问题可能是什么？

stack.h

/*Stack.h*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>


typedef struct Stack{   
    char **storage;     //Elements container;
    size_t capacity;    //Total amount of elements POSSIBLE in the stack;
    size_t size;        //Total amount of elements within the stack;
}Stack;

Stack *salloc(size_t);
void spush(Stack *, char *);
char *spop(Stack *);
void speek(Stack *);
void empty(Stack *);
void print_stack(Stack *);  //Useful but non-conventional

stack.c

/*Stack.c*/
#include "stack.h"

Stack *salloc(size_t size){
    Stack *s = (Stack *)malloc(sizeof(s));
    s->storage = (char **)malloc(sizeof(char *) * size);
    s->capacity = size;
    s->size = 0;
}

static int expand_stack(Stack *s){
    s->storage = realloc(s->storage, (s->capacity * 2));
}

static void shrink_stack(Stack *s){
    s->storage = realloc(s->storage, (s->capacity / sizeof(char *)));
}

void spush(Stack *s, char *elem){
    char *p = elem;
    int k = (s->capacity-1) - s->size; //Next free position

    if(s->size == s->capacity)
        expand_stack(s);

    s->storage[k] = (char *)malloc(sizeof(char) * (strlen(p) + 1));
    memcpy(s->storage[k], p, (strlen(p) + 1));
    // *(s->storage[k] + (strlen(p) + 1)) = '\0';
    s->size++;
}

char *spop(Stack *s){
    int k = s->capacity - s->size;

    if(s->size == 0)
        return NULL;

    free(s->storage[k]);
    s->size--;
    shrink_stack(s);
}

void speek(Stack *s){
    int k = s->capacity - s->size;
    printf("'%s'\n", s->storage[k]);
}

void empty(Stack *s){
    s->storage = realloc(s->storage, 0);
    s->capacity = 0;
    s->size = 0;
}

void print_stack(Stack *s){
    printf("[STACK] = {\n");
    int k = s->capacity - s->size;
    for(int i = k; i <= s->capacity-1; i++)
        printf("   '%s'\n", s->storage[i]);
    printf("}\n");
}

main.c

#include "stack.h"

#define COM1    "echo"
#define COM2    "start"
#define COM3    "sort"

int main(){
    Stack *s = salloc(5);
    spush(s, COM1);
    spush(s, COM2);
    spush(s, COM3);
    // speek(s);
    print_stack(s); //Full Stack
    spop(s);
    print_stack(s);
    spush(s, "cd");
    print_stack(s);
    empty(s);
    print_stack(s);
}

Answer 1

Stack *salloc(size_t size){
    Stack *s = (Stack *)malloc(sizeof(s));
    s->storage = (char **)malloc(sizeof(char *) * size);
    s->capacity = size;
    s->size = 0;
}

您的第一个malloc呼叫仅为stack*分配足够的空间，对于实际stack结构没有足够的空间。您想要：

    Stack *s = (Stack *)malloc(sizeof(*s));

或

    Stack *s = (Stack *)malloc(sizeof(Stack));

Answer 2

您的代码中有很多问题：

1. salloc缺少返回S。
2. spop不返回任何东西（除null案例外）。
3. salloc没有为stack object（sizeof（s）分配足够的内存/代码>对象）。
4. 在表格中的所有调用中：s-＆gt; storege = realloc（...） - realloc（void*）的结果应将其施放到char **。
5. Expand_stack被定义为返回int，但实际上什么都没有返回。可能应该更改为返回void。
6. shink_stack未正确计算大小。结果，在您的情况下，realloc实际上可以分配0尺寸的内存（注意：：这是print_stack中违反访问的原因。调用spop之后）。我建议您使用调试器捕获此错误。

Answer 3

这里有很多问题。无论是在设计还是实施方面，但所有值得学习的课程。

以下是更改的摘要：

• salloc - 我们应该存储初始容量。 空只是释放所有存储，这会使堆栈无法使用。通过存储初始容量，shink_stack可以避免在其下方收缩。

• Expand_stack - 容量必须在扩展后进行修改，否则我们将失去对实际分配的跟踪。另外，如果没有问题，我们将无法超越初始容量。通过int返回，我怀疑您打算返回新容量（应该是size_t。

• shink_stack不应该只保留划分容量，或者我们最终达到零，因此使用initial_capacity我们将事情保持在一开始时也不需要缩小。所以。

• spush - 我不知道为什么您选择从存储末端分配，但是当容量增加和扩张发生时，这从根本上讲会破裂。根据尺寸添加的简单得多，然后从大小回到零。请注意，添加了const，或者某些编译器会抱怨将非const指针传递给字符串文字，这很危险。

• spop - 根据spush，size -1返回零。这里的另一个错误是字符串存储在malloc'd缓冲区中，因此我们应该释放它，这意味着我们不能只返回指针，而是需要spop签名来提供可以放置的缓冲区和最大尺寸。鉴于我们正在处理零终止字符串，因此可以是strncpy。请注意，返回值是传递的地址，如果没有弹出元素，则null。也许还有其他方法可以帮助消除elem == null等的风险。

  。

• speek - 同样，只需使用size -1

• empty - 使用spop即可删除所有元素而无需丢弃初始容量存储。

• print_stack - 从零到大小。

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


typedef struct Stack{   
    char **storage;     //Elements container;
    size_t capacity;    //Total amount of elements POSSIBLE in the stack;
    size_t size;        //Total amount of elements within the stack;
    size_t initial_capacity;
}Stack;

Stack *salloc(size_t size){
    Stack *s = (Stack *)malloc(sizeof(s));
    s->storage = (char **)malloc(sizeof(char *) * size);
    s->capacity = s->initial_capacity = size;
    s->size = 0;
    return s;
}

static int expand_stack(Stack *s){
    
    s->storage = (char **)realloc(s->storage, (sizeof(char *) * s->capacity * 2));
    s->capacity = s->capacity * 2;
    return s->capacity;
}

static void shrink_stack(Stack *s){
    if (s->capacity > s->initial_capacity && s->size < s->capacity / 2) {
        s->storage = (char **)realloc(s->storage, (sizeof(char *) * (s->capacity / 2)));
        s->capacity = s->capacity / 2;
    }
}

void spush(Stack *s, char const * elem){

    if(s->size == s->capacity)
        expand_stack(s);

    size_t size = strlen(elem) + 1;
    s->storage[s->size] = (char *)malloc(sizeof(char) * size);
    memcpy(s->storage[s->size], elem, size);
    s->size++;
}

char *spop(Stack *s, char * elem, size_t size){

    if(s->size == 0)
        return NULL;

    if (size > 0) {
        strncpy(elem, s->storage[s->size - 1], size);
    }
    free(s->storage[s->size - 1]);
    s->storage[s->size - 1] = NULL;
    s->size--;
    shrink_stack(s);
    return elem;
}

void speek(Stack *s){
    printf("'%s'\n", s->storage[s->size - 1]);
}

void empty(Stack *s){
    char notused;
    while (spop(s, ¬used, 0) != NULL);
}

void print_stack(Stack *s){
    printf("[STACK] = {\n");
    for(int i = 0; i < s->size; i++)
        printf("   '%s'\n", s->storage[i]);
    printf("}\n");
}

#define COM1    "echo"
#define COM2    "start"
#define COM3    "sort"

int main(){
    
    Stack *s = salloc(5);

    spush(s, COM1);
    spush(s, COM2);
    spush(s, COM3);

    // speek(s);

    print_stack(s); //Full Stack

    char string[64];
    spop(s, string, sizeof(string)/sizeof(string[0]));

    print_stack(s);

    spush(s, "cd");

    print_stack(s);

    empty(s);

    print_stack(s);
}