编程范式之一 - 栈的抽象操作
编程范式之一 ------- 栈的抽象操作
首先,我们需要在栈中设置一个抽象的存储结构, void *elem, 其需要动态分配堆内存, 声明如下所示:
typedef struct { void *elem; int elem_size; int length; int position; void (*freefn)(void *elem); }Stack; void stackNew(Stack *s, int elem_size, void (*freefn)(void *elem)); void push(Stack *s, void *elem); void pop(Stack *s, void *result); void stackDestroy(Stack *s);
void (*freefn)(void *elem) 为函数指针,其表示用于回收抽象指针(void *elem)中,需要回收的数据,比如动态分配的字符串和结构体中动态分配的内容,我们可以通过传递函数指针,使得在回收栈时,不必弹出所有栈中数据进行回收,而是通过stackDestroy调用我们定义的回收方法,进行数据回收。
具体实现如下所示:
#include <stdlib.h> #include <string.h> #include <iostream> void stackNew(Stack *s, int elem_size, void (*freefn)(void *elem)) { s->length = 4; s->position = 0; s->elem_size = elem_size; s->freefn = freefn; s->elem = malloc(s->length * s->elem_size); } static void stackGrow(Stack *s) { s->length = s->length * 2; s->elem = realloc(s->elem, s->length * s->elem_size); } void push(Stack *s, void *elem) { if(s->position == s->length) { stackGrow(s); } void *address; address = (char *)s->elem + s->position * s->elem_size; memcpy(address, elem, s->elem_size); s->position++; } void pop(Stack *s, void *result) { s->position--; memcpy(result, (char *)s->elem + s->position * s->elem_size, s->elem_size); } void stackDestroy(Stack *s) { int i = 0; for(; i < s->position; i++) { s->freefn((char *)s->elem + i * s->elem_size); } free(s->elem); }
由于我们不知道数据类型是什么,所以在初始化栈时,我们需要传递数据类型的大小,在进行数据弹出和压入的时候,我们可以对内存直接进行拷贝工作,这样做的优点是显而易见的。不要忘记,elem_size*length才是需要分配堆内存的大小。
调用时,如下所示:
#include <iostream> #include <string.h> #include <stdlib.h> #include "stack4.h" using namespace std; static char * Strdup(const char * source) { char * temp = (char *)malloc(strlen(source) * sizeof(char) + 1); strcpy(temp, source); return temp; } void freefn(void *element) { cout << "data free..." << endl; char *temp = *((char **) element); free(temp); } int main() { char *str[] = {"AAAAAAAA", "BBBBBBBB", "CCCCCCCC", "DDDDDDDDD"}; Stack *s = (Stack *) malloc(sizeof(Stack)); stackNew(s, sizeof(char *), freefn); int i=0; for(;i < 4; i++) { char *sc = Strdup(str[i]); push(s, &sc); } char *result; pop(s, &result); cout << result << endl; //回收pop的数据 free(result); //有了固定的回收函数后,不必弹出所有的栈中数据,即可回收内存 //若没有,回收内存时,必须弹出所有栈中数据,手动进行回收,然后回收栈内存 stackDestroy(s); free(s); getchar(); return 0; }
使用深度拷贝字符串,是考虑到了实际应用中,动态分配内容的生命周期。
还需注意的是,在压栈时,必须对指向动态分配字符串的指针地址进行操作,因为我们在栈的初始化时,传递的数据大小是sizeof(char *),另一方面,也有助于栈的高效操作。