cs107 编程范式(五)-一一网

补充

malloc: 分配指定字节数的存储区。存储区的初始值不确定

malloc返回内存所采用的字节对齐方式，总是适宜于高效访问任何类型的c语言数据结构。在大多数架构上，意味着malloc是基于8字节或16字节边界来分配内存的。
malloc(0)要么返回NULL, 那么是一块可(并且应该)被free释放的内存

realloc: 增加或减少以前分配区的长度

当增加长度时, 可能需将以前分配区的内容移到另外一个足够大的区域，以便在尾端提供增加的存储区，而新增区域的初始值则不确定
函数调用前后可能是不同的存储区，所以调用前不应该有指针指向这段存储区，不然修改后，可能该指针会非法访问
应该使用另一个指针保存realloc的返回值，因为如果使用传入的实参保存返回值，那么一旦realloc失败，则会传回NULL，原来的动态内存区再也无法访问，从而发生内存泄漏

这个两个函数返回值：成功，返回非空指针；出错，返回NULL

int类型的栈

stack.h

typedef struct {
    int *elems;
    int logLength;
    int allocLength;
} stack;

void StackNew(stack *s);
void StackDispose(stack *s);
void StackPush(stack *s, int value);
void StackPop(stack *s);
复制代码

stack.c

void StackNew(stack *s)
{
    s->allocLength = 4;
    s->logLength = 0;
    s->elems = malloc(4 * sizeof(int));
    assert(s->elems != NULL);
}

void StackDispose(stack *s) 
{
    free(s->elems);
}

void StackPush(stack *s, int value)
{
    if(s->logLength == s->allocLength) 
    {
        s->allocLength *= 2;
        s->elems = realloc(s->elems, s->allocLength * sizeof(int));
        assert(s->elems != NULL);
    }
    
    s->elems[s->logLength] = value;
    s->logLength++;
}

void StackPop(stack *s) 
{
    assert(s->logLength > 0);
    s->logLength--;
    return s->elems[s->logLength];
}
复制代码

通用类型栈

stack.h

typedef struct {
    void *elems;
    int elemSize;
    int logLength;
    int allocLength;
} stack;

void StackNew(stack *s, int elemSize);
void StackDispose(stack *s);
void StackPush(stack *s, void *elemValue);
void StackPop(stack *s, void *elemValue);
复制代码

在通用类型的实现过程中，我们一般是通过void*类型来代替数据类型，但是这也使得我们无法进行指针运算和丢失数据类型大小的信息。因此，我们必须进行额外补充。

stack.c

void StackNew(stack *s, int elemSize)
{
    assert(elemSize > 0);
    s->logLength = 0;
    s->allocLength = 4;
    s->elemSize = elemSize;
    s->elems = malloc(4 * s->elemSize);
    assert(s->elems != NULL);
}

void StackDispose(stack *s)
{
    free(s->elems);
}

void StackPush(stack *s, void *elemValue)
{
    if(s->logLength == s->allocLength)
    {
        s->allocLength *= 2;
        s->elems = realloc(s->elems, s->allocLength * s->elemSize);
        assert(s->elems != NULL);
    }
    
    void *source = (char*)s->elems + s->logLength * s->elemSize;
    memcpy(source, elemValue, s->elemSize);
    s->logLength++;
}

void StackPop(stack *s, void *elemValue)
{
    assert(s->logLength > 0);
    void *source = (char*)s->elems + (s->logLength - 1) * s->elemSize;
    memcpy(elemValue, source, s->elemSize);
    s->logLength--;
}
复制代码