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**,所以不需要知道大小。
|