首页 博客

# 斯坦福编程范式 CS107_6

# 实现一个整型的栈（下）

在 C 语言中结构体中的所有内容都是隐式的 public ，无法像 C++ 那样，实现 private protect 之类的限定词进行限制，但是我们可以假装里面的内容是不可见的，并要求通过我们定义的函数对其中的内容进行操作。

下面内容在 stack.h 文件中

typedef struct{
    int *elems;
    int logicalLen;		// 已经使用的内存
    int alloclength;	// 申请的内存大小
}stack;
void StackNew(stack *s);
void StackDispose(stack *s);
void StackPush(stack *s,int value);
int StackPop(stack *s);
上节课实现的 New 以及我们接下来要实现的其他函数，他们都在  stack.c  文件中


void StackNew(stack &s){
    s->logicallen = 0;
    s->allocLen = 4;
    s->elems = malloc(4*sizeof(int));	// 动态分配内存函数，返回这一大块内存地址的开始地址
    assert(s->elems != NULL);	// 如果 assert 里面的内容为 false，assert 会终止程序，并告知终止位置
}
下面是 Dispose 的实现


void StackDispose(stack *s){
	free(s->elems);
}
有人可能会问，能否直接使用  free(s)  实现直接对栈进行释放内存？答案是不可以，因为除了在 New 函数中，其他任何地方对这个栈变量分配空间。 free(s)  这样操作的假设是 s 栈空间已经被分配好，并将它被 New 函数所指定的地址作为参数传递给 Dispose。


下面是 Push 的实现


void StackPush(stack *s,int value){
    if(s->logicalLen == s->alloclength){
        s->alloclength *= 2;
        s->elems = realloc(s->elems,s->alloclength * sizeof(int)); 
        //realloc 首先假设第一个参数指向了一个动态申请的内存块，随后将其调整成第二个参数大小，如果可以调整，则返回第一个		// 参数原先的地址，否则就使用 alloc 另开一块地址，返回新的地址
        assert(s->elems != NULL);
    }
    s->elems[s->logicalLen]=valus;
    s->logicalLen ++ ;
}
下面是 Pop 的实现


int StackPop(stack *s){
    assert(s->logicalLen > 0);
    logicalLen--;
    return s->elems[s->logicalLen];
}
# 实现上述类型的通用模板


# 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 *elemAddr);
void StackPop(stack *s,void *elemAddr);
# stack.c


void StackNew(stack *s,int elemSize){
    assert(elemSize > 0);
    s->elemSize = elemSize;
    s->loglength = 0;
    s->alloclength = 4;
    s->elems = malloc(4*elemSize);
    assert(s->elems!=NULL);
}
void StackDispose(stack *s){
    
    free(s->elems);
}
void StackPush(stack *s,void *elemAddr){
    if(s->loglength == s->alloclength)
        StackGrow(s);	// 这里添加了一个辅助函数用于进行内存空间拓展
    void *target =(char*)s->elems + s->loglength *s->elemSize;
    memcpy(target,elemAddr,s->elemSize);
    s->loglength++;
}
当 static  修饰 c 或者 c 的函数原型时，这意味着，这是一个私有函数，不应该在函数所在文件之外的地方对其引用，因此在大多数情况下，它和 C 中的 private 有着相同的含义。其他的函数诸如我们上面写的 New、Disopose、Push 等都是全局函数，可以被其他的 .o  文件所使用


static void StackGrow(stack *s){
    s->alloclength *= 2;
    s->elems = realloc(s->elems,s->alloclength * s->slemSize);
}
void StackPop(stack *s,void *elemAddr){
    void *source = (char*)s->elems + (s->loglength - 1) * s->elemSize; 
    memcpy(elemAddr,source,s->elemSize);
    s->loglength--; 
}