数据结构第23讲及之后的入栈操作代码顺序好像有问题,红色部分应该倒过来写
本帖最后由 圣狄雅哥 于 2018-1-28 21:26 编辑#define SATCKINCREMENT 10
Push(sqStack *s, ElemType e)
{
// 如果栈满,追加空间
if( s->top – s->base >= s->stackSize )
{
s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if( !s->base )
exit(0);
s->top = s->base + s->stackSize; // 设置栈顶
s->stackSize = s->stackSize + STACKINCREMENT; // 设置栈的最大容量
}
*(s->top) = e;
s->top++;
} 我觉得一个数据要入栈先得让top指针向上移一位,再赋值。 也就是说数据未入栈之前栈顶是非空的,这不太像链表里面的头结点 而且->这个运算符的优先级高于++,所以s->top++好像不能实现对指针的增加 version1.c
#include <stdio.h>
typedef int ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
} sqStack;
void InitStack(sqStack *stack, ElemType *begin, ElemType *end);
void Push(sqStack *stack, ElemType e);
void Pop(sqStack *stack, ElemType *e);
int main()
{
ElemType buff;
sqStack stack;
ElemType e;
InitStack(&stack, buff, buff + (sizeof(buff) / sizeof(buff)));
for(int i = 0; i < 10; ++i)
{
Push(&stack, i);
}
for(int i = 0; i < 10; ++i)
{
Pop(&stack, &e);
printf("%d ", e);
}
printf("\n");
return 0;
}
void InitStack(sqStack *stack, ElemType *begin, ElemType *end)
{
stack->base = begin;
stack->top = end;
}
void Push(sqStack *stack, ElemType e)
{
*--stack->top = e;
}
void Pop(sqStack *stack, ElemType *e)
{
*e = *stack->top++;
}
version2.c
#include <stdio.h>
typedef int ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
} sqStack;
void InitStack(sqStack *stack, ElemType *begin, ElemType *end);
void Push(sqStack *stack, ElemType e);
void Pop(sqStack *stack, ElemType *e);
int main()
{
ElemType buff;
sqStack stack;
ElemType e;
InitStack(&stack, buff, buff + (sizeof(buff) / sizeof(buff)));
for(int i = 0; i < 10; ++i)
{
Push(&stack, i);
}
for(int i = 0; i < 10; ++i)
{
Pop(&stack, &e);
printf("%d ", e);
}
printf("\n");
return 0;
}
void InitStack(sqStack *stack, ElemType *begin, ElemType *end)
{
stack->base = begin;
stack->top = end - 1;
}
void Push(sqStack *stack, ElemType e)
{
*stack->top-- = e;
}
void Pop(sqStack *stack, ElemType *e)
{
*e = *++stack->top;
}
本帖最后由 圣狄雅哥 于 2018-1-29 14:28 编辑
{:5_92:}这个思路相当精妙,解答了我两个问题。虽然和小甲鱼给的那个从底向上入栈不同,但从顶到底入栈再从底到顶出栈完全正确,buff + (sizeof(buff) / sizeof(buff这一句就求出了数组的长度,我服,看来论坛里面也是高手云集。 不过还是没有考虑栈满了拓展空间以及栈空了应该退出 圣狄雅哥 发表于 2018-1-29 10:59
不过还是没有考虑栈满了拓展空间以及栈空了应该退出
^_^ 本帖最后由 圣狄雅哥 于 2018-1-29 15:58 编辑
人造人 发表于 2018-1-28 22:50
version1.c
/*您写的version 1.c 我按照小甲鱼课件里面的改写了一些,红色部分为增加的*/
#include <stdio.h>
#define STACK_INIT_SIZE 20
#difine STACKINCREMENT 10
typedef char ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stacksize;
} sqStack;
void InitStack(sqStack *s, ElemType *begin, ElemType *end);
void Push(sqStack *s, ElemType e);
void Pop(sqStack *s, ElemType *e);
int main()
{
ElemType buff[20];
sqStack s;
ElemType e;
int i,len;
InitStack(&s, buff, buff + (sizeof(buff) / sizeof(buff)));
printf("请输入二进制数,输入#符号表示结束!\n");
scanf("%c", &e);
while( e != '#' )
{
Push(&s, e);
scanf("%c", &e);
}
getchar();// 把'\n'从缓冲区去掉
len=stacksize(s);
printf("栈的当前容量是: %d\n", len);
for( i=0; i < len; i++ )
{
Pop(&s, &e);
printf("%c",e);
}
printf("\n");
return 0;
}
void InitStack(sqStack *s, ElemType *begin, ElemType *end)
{
s->base = begin;
s->top = end;
s->stacksize=STACK_INIT_SIZE;
}
void Push(sqStack *s, ElemType e)
{
if( s->top - s->base <=1)
{
buff = (ElemType *)realloc(buff, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if( !buff )
{
exit(0);
}
s->base=buff; /*这一块我想不到如何增加栈的空间,主要是拓展了数组长度之后指针的位置变化,不知道这样行不行*/
s->top=buff+STACKINCREMENT;
s->stacksize+=STACKINCREMENT;
}
*--s->top=e;
}
void Pop(sqStack *s, ElemType *e)
{
if(s->top-s->base>=s->stacksize)
{
return;
}
*e = *s->top++;
}
int stacklen(sqstack s)
{
return(s.top-s.base);
} 圣狄雅哥 发表于 2018-1-29 15:18
/*您写的version 1.c 我按照小甲鱼课件里面的改写了一些,红色部分为增加的*/
#include
谢谢,不过我用不着这个
圣狄雅哥 发表于 2018-1-29 15:18
/*您写的version 1.c 我按照小甲鱼课件里面的改写了一些,红色部分为增加的*/
#include
路过的朋友谁帮忙看一下深红色的那部分代码,谢谢了 圣狄雅哥 发表于 2018-1-29 16:00
路过的朋友谁帮忙看一下深红色的那部分代码,谢谢了
如果要动态增加栈空间,就不要使用数组,初始化时直接malloc申请
还有,从顶到底的入栈方式不适合动态增加栈空间,需要改为从底到顶的方式
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct
{
ElemType *base;
ElemType *top;
int stackSize;
} sqStack;
void InitStack(sqStack *stack);
void Push(sqStack *stack, ElemType e);
void Pop(sqStack *stack, ElemType *e);
int main(void)
{
sqStack stack;
ElemType e;
InitStack(&stack);
for(int i = 0; i < 10; ++i)
{
Push(&stack, i);
}
for(int i = 0; i < 10; ++i)
{
Pop(&stack, &e);
printf("%d ", e);
}
printf("\n");
return 0;
}
void InitStack(sqStack *stack)
{
static const int defaultSize = 100;
stack->stackSize = defaultSize;
stack->base = malloc(stack->stackSize * sizeof(ElemType));
stack->top = stack->base;
}
void Push(sqStack *stack, ElemType e)
{
static const int increment = 50;
if(stack->top == stack->base + stack->stackSize)
{
stack->base = realloc(stack->base, (stack->stackSize + increment) * sizeof(ElemType));
stack->top = stack->base + stack->stackSize;
stack->stackSize += increment;
}
*stack->top++ = e;
}
void Pop(sqStack *stack, ElemType *e)
{
*e = *--stack->top;
}
页:
[1]