r****o
发帖数: 1950 | 1 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: roufoo (五经勤向窗前读), 信区: InterviewHackers
标 题: 用C设计Stack的interface，要求支持各种数据类型。
发信站: BBS 未名空间站 (Thu Oct 14 01:36:53 2010, 美东)
用C设计Stack的interface(push, pop, top, ...)，要求支持各种数据类型。
C不支持template，那怎么设计比较好呢? |
c*********7
发帖数: 19373 | 2 array,link list都可以吧。stack本身就可以当个数据类型来实现别的 |
r****o
发帖数: 1950 | 3 那给个能支持各种数据类型的stack的interface定义吧。
【在 c*********7 的大作中提到】
: array,link list都可以吧。stack本身就可以当个数据类型来实现别的
|
x***y
发帖数: 633 | 4 void *
【在 r****o 的大作中提到】
: 那给个能支持各种数据类型的stack的interface定义吧。
|
r****o
发帖数: 1950 | 5 写个完整的吧。
【在 x***y 的大作中提到】
: void *
|
p********7
发帖数: 549 | 6 我被问到过如何用C实现C++的这种类似的功能，面试官的答案其实就是给每个数据类型
都设计一个函
数，比如push_int push_float push_pointer push_double.....
【在 r****o 的大作中提到】
: 写个完整的吧。
|
y*********e
发帖数: 518 | 7 /* create a stack
* returns NULL if failure to create.
*/
STACK* stack_create();
/* dispose a stack */
void stack_close(STACK* stack);
/* push the data into a stack. returns 0 if fail. */
int stack_push(STACK* stack, void* data);
/* pop the top item from the stack and store it into data.
returns 0 if fail. */
int stack_pop(STACK* stack, void** data);
/* get number of items in the stack */
int stack_size(STACK* stack);
【在 r****o 的大作中提到】
: 写个完整的吧。
|
r****o
发帖数: 1950 | 8 stack_push(), stack_pop()这些函数里面具体怎么实现对不同数据类型的处理的呢?
【在 y*********e 的大作中提到】
: /* create a stack
: * returns NULL if failure to create.
: */
: STACK* stack_create();
: /* dispose a stack */
: void stack_close(STACK* stack);
: /* push the data into a stack. returns 0 if fail. */
: int stack_push(STACK* stack, void* data);
: /* pop the top item from the stack and store it into data.
: returns 0 if fail. */
|
t******h
发帖数: 120 | 9
要还需要数据的大小吧
比如
int stack_push(STACK* stack, void* data, int size);
【在 y*********e 的大作中提到】
: /* create a stack
: * returns NULL if failure to create.
: */
: STACK* stack_create();
: /* dispose a stack */
: void stack_close(STACK* stack);
: /* push the data into a stack. returns 0 if fail. */
: int stack_push(STACK* stack, void* data);
: /* pop the top item from the stack and store it into data.
: returns 0 if fail. */
|
t******h
发帖数: 120 | 10
比如
int stack_push(STACK* stack, void* data, int size)
size是你要push的数据类型的大小，就是在内存里用多长的地址来表示。
再举个例子 你想要push一个int 就是
stack_push(stack, data, sizeof(int));
这样就知道这个void* 按一个int的长度来处理
建议你去看看youtube里面stanford大学的教程 Programming Paradigms
没记错里面的前10讲就是讲这方面 讲的很详细
【在 r****o 的大作中提到】
: stack_push(), stack_pop()这些函数里面具体怎么实现对不同数据类型的处理的呢?
|
|
|
y*********e
发帖数: 518 | 11 若是存储的是指针类型，那么就不需要大小。
比如如下的示例代码：
int a = 10;
float b = 3.0f;
stack_push(s, &a);
stack_push(s, &b);
void* 可以兼容所有的指针类型，比如 int*, float* 这些。而指针本身大小是固定的，
在32位机器上一般是32bit。所以不需要大小。
PS：若是需要大小的话，应该带入的参数类型是size_t而不是int
【在 t******h 的大作中提到】
:
: 比如
: int stack_push(STACK* stack, void* data, int size)
: size是你要push的数据类型的大小，就是在内存里用多长的地址来表示。
: 再举个例子 你想要push一个int 就是
: stack_push(stack, data, sizeof(int));
: 这样就知道这个void* 按一个int的长度来处理
: 建议你去看看youtube里面stanford大学的教程 Programming Paradigms
: 没记错里面的前10讲就是讲这方面 讲的很详细
|
d**e
发帖数: 6098 | 12 我觉得需要知道大小吧。
因为需要将void * 转换出来。
比如地址 1234，但怎么知道它是char *，int *,还是double *
的，
【在 y*********e 的大作中提到】
: 若是存储的是指针类型，那么就不需要大小。
: 比如如下的示例代码：
: int a = 10;
: float b = 3.0f;
: stack_push(s, &a);
: stack_push(s, &b);
: void* 可以兼容所有的指针类型，比如 int*, float* 这些。而指针本身大小是固定的，
: 在32位机器上一般是32bit。所以不需要大小。
: PS：若是需要大小的话，应该带入的参数类型是size_t而不是int
|
y*********e
发帖数: 518 | 13 stack_pop 的函数声明形式是 int stack_pop(STACK* stack, void** data);
输出是 void**，所以不需要知道大小。 |
l*******y
发帖数: 1498 | 14 你这样存的是指针，不是data。如果data在stack之外被free了或者被overwrite了，这
个stack存的指针就没用了。
真正的stack还是要存实际数据的吧。
的，
【在 y*********e 的大作中提到】
: 若是存储的是指针类型，那么就不需要大小。
: 比如如下的示例代码：
: int a = 10;
: float b = 3.0f;
: stack_push(s, &a);
: stack_push(s, &b);
: void* 可以兼容所有的指针类型，比如 int*, float* 这些。而指针本身大小是固定的，
: 在32位机器上一般是32bit。所以不需要大小。
: PS：若是需要大小的话，应该带入的参数类型是size_t而不是int
|
y*********e
发帖数: 518 | 15 嗯，这个要看面试的时候沟通弄清楚要求了。
若是要存实实在在的data，那么大抵可以在stack_create的时候引入一个参数
，是为每一个元素的size。在push的时候，把数据拷贝到stack上。
typedef struct {
size_t count; /* no of elements in stack */
size_t capacity; /* max no of elements can be held */
size_t element_size; /* size of each element */
char* ptr;
} STACK;
/* Create a stack by specifying size of each element.
returns NULL if failure. */
STACK* stack_create(size_t element_size) {
STACK* s = malloc(sizeof(STACK));
if (!s) return NULL;
s->element_size = element_size;
s->count = 0;
s->capacity = DEFAULT_CAPACITY;
s->ptr = malloc(DEFAULT_CAPACITY * element_size);
if (!s->ptr) return NULL;
return s;
}
/* Push the data into stack by copying
returns 0 if failure. */
int stack_push(STACK* s, void* data) {
if (!ensure_capacity(s))
return FALSE;
size_t index = s->element_size * s->count;
memcpy(s->ptr[index], data, s->element_size);
++s->count;
return TRUE;
}
/* Pop the top element from the stack, and copy it into
data. Returns 0 if failure. */
int stack_pop(STACK* s, void* data) {
if (s->size == 0)
return FALSE;
size_t index = s->element_size * s->count;
memcpy(data, s->ptr[index], s->element_size);
--s->count;
return TRUE;
}
【在 l*******y 的大作中提到】
: 你这样存的是指针，不是data。如果data在stack之外被free了或者被overwrite了，这
: 个stack存的指针就没用了。
: 真正的stack还是要存实际数据的吧。
:
: 的，
|
b******n
发帖数: 592 | 16 the actual STACK can be a structure, size can be stored when stack is
created
【在 t******h 的大作中提到】
:
: 比如
: int stack_push(STACK* stack, void* data, int size)
: size是你要push的数据类型的大小，就是在内存里用多长的地址来表示。
: 再举个例子 你想要push一个int 就是
: stack_push(stack, data, sizeof(int));
: 这样就知道这个void* 按一个int的长度来处理
: 建议你去看看youtube里面stanford大学的教程 Programming Paradigms
: 没记错里面的前10讲就是讲这方面 讲的很详细
|
b******n
发帖数: 592 | 17 have you ever tested your code?
【在 y*********e 的大作中提到】
: stack_pop 的函数声明形式是 int stack_pop(STACK* stack, void** data);
: 输出是 void**，所以不需要知道大小。
|
