[已解决]数据结构第23讲及之后的入栈操作代码顺序好像有问题，红色部分应该倒过来写

圣狄雅哥 · 发表于 2018-1-28 21:22:42

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由圣狄雅哥于 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++;
}

最佳答案

月排行榜 / 总排行榜

人造人

2018-1-28 22:50:32

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[100];
        sqStack stack;
        ElemType e;

        InitStack(&stack, buff, buff + (sizeof(buff) / sizeof(buff[0])));

        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[100];
        sqStack stack;
        ElemType e;

        InitStack(&stack, buff, buff + (sizeof(buff) / sizeof(buff[0])));

        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-28 21:24:18

我觉得一个数据要入栈先得让top指针向上移一位，再赋值。

圣狄雅哥 · 发表于 2018-1-28 21:31:39

也就是说数据未入栈之前栈顶是非空的，这不太像链表里面的头结点

圣狄雅哥 · 发表于 2018-1-28 21:51:28

而且->这个运算符的优先级高于++，所以s->top++好像不能实现对指针的增加

人造人 · 发表于 2018-1-28 22:50:32

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[100];
        sqStack stack;
        ElemType e;

        InitStack(&stack, buff, buff + (sizeof(buff) / sizeof(buff[0])));

        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[100];
        sqStack stack;
        ElemType e;

        InitStack(&stack, buff, buff + (sizeof(buff) / sizeof(buff[0])));

        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 10:36:23

本帖最后由圣狄雅哥于 2018-1-29 14:28 编辑

这个思路相当精妙，解答了我两个问题。虽然和小甲鱼给的那个从底向上入栈不同，但从顶到底入栈再从底到顶出栈完全正确，buff + (sizeof(buff) / sizeof(buff[0]这一句就求出了数组的长度，我服，看来论坛里面也是高手云集。

圣狄雅哥 · 发表于 2018-1-29 10:59:44

不过还是没有考虑栈满了拓展空间以及栈空了应该退出

人造人 · 发表于 2018-1-29 14:34:18

圣狄雅哥发表于 2018-1-29 10:59
不过还是没有考虑栈满了拓展空间以及栈空了应该退出

^_^

圣狄雅哥 · 发表于 2018-1-29 15:18:36

本帖最后由圣狄雅哥于 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[0])));

      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:21:28

圣狄雅哥发表于 2018-1-29 15:18
/*您写的version 1.c 我按照小甲鱼课件里面的改写了一些，红色部分为增加的*/

#include

谢谢，不过我用不着这个

圣狄雅哥 · 发表于 2018-1-29 16:00:47

圣狄雅哥发表于 2018-1-29 15:18
/*您写的version 1.c 我按照小甲鱼课件里面的改写了一些，红色部分为增加的*/

#include

路过的朋友谁帮忙看一下深红色的那部分代码，谢谢了

人造人 · 发表于 2018-1-30 20:00:47

圣狄雅哥发表于 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;
}

账号		自动登录	找回密码
密码			立即注册