プログラミングパターンのスタックの抽象操作
3473 ワード
まず、スタックに抽象的なストレージ構造を設定する必要があります.void*elemは、スタックメモリを動的に割り当てる必要があります.次のように宣言します.
void(*freefn)(void*elem)は、抽象ポインタ(void*elem)を回収するために、動的に割り当てられた文字列や構造体で動的に割り当てられた内容など、回収する必要があるデータを表す関数ポインタであり、スタックを回収する際にすべてのスタックからデータをポップアップして回収する必要がないように、関数ポインタを伝達することで、私たちが定義した回収方法をstackDestroyで呼び出し、データ回収を行います.
具体的な実装は以下のとおりです.
データ型が何なのか分からないので、スタックを初期化するときにデータ型のサイズを渡す必要があります.データのポップアップと圧入を行うときに、メモリを直接コピーすることができます.このような利点は明らかです.忘れないでsize*lengthこそ、スタックメモリのサイズを割り当てる必要があります.
次のように呼び出されます.
深度コピー文字列を使用するのは、実際のアプリケーションでコンテンツを動的に割り当てるライフサイクルを考慮したものです.
また、スタックを圧縮する際には、スタックの初期化時に伝達されるデータサイズがsizeof(char*)であるため、動的に割り当てられた文字列を指すポインタアドレスを操作する必要があります.一方、スタックの効率的な操作にも役立ちます.
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);
}
データ型が何なのか分からないので、スタックを初期化するときにデータ型のサイズを渡す必要があります.データのポップアップと圧入を行うときに、メモリを直接コピーすることができます.このような利点は明らかです.忘れないで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*)であるため、動的に割り当てられた文字列を指すポインタアドレスを操作する必要があります.一方、スタックの効率的な操作にも役立ちます.