设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 数据结构第23讲及之后的入栈操作代码顺序好像有问题，红 ...
返回列表 发新帖
查看: 3259|回复: 11

[已解决]数据结构第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
  1. #include <stdio.h>

  3. typedef int ElemType;

  5. typedef struct
  6. {
  7.         ElemType *base;
  8.         ElemType *top;
  9. } sqStack;

  11. void InitStack(sqStack *stack, ElemType *begin, ElemType *end);
  12. void Push(sqStack *stack, ElemType e);
  13. void Pop(sqStack *stack, ElemType *e);

  15. int main()
  16. {
  17.         ElemType buff[100];
  18.         sqStack stack;
  19.         ElemType e;

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

  23.         for(int i = 0; i < 10; ++i)
  24.         {
  25.                 Push(&stack, i);
  26.         }

  28.         for(int i = 0; i < 10; ++i)
  29.         {
  30.                 Pop(&stack, &e);
  31.                 printf("%d ", e);
  32.         }
  33.         printf("\n");

  35.         return 0;
  36. }

  38. void InitStack(sqStack *stack, ElemType *begin, ElemType *end)
  39. {
  40.         stack->base = begin;
  41.         stack->top = end;
  42. }

  44. void Push(sqStack *stack, ElemType e)
  45. {
  46.         *--stack->top = e;
  47. }

  49. void Pop(sqStack *stack, ElemType *e)
  50. {
  51.         *e = *stack->top++;
  52. }
复制代码


version2.c
  1. #include <stdio.h>

  3. typedef int ElemType;

  5. typedef struct
  6. {
  7.         ElemType *base;
  8.         ElemType *top;
  9. } sqStack;

  11. void InitStack(sqStack *stack, ElemType *begin, ElemType *end);
  12. void Push(sqStack *stack, ElemType e);
  13. void Pop(sqStack *stack, ElemType *e);

  15. int main()
  16. {
  17.         ElemType buff[100];
  18.         sqStack stack;
  19.         ElemType e;

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

  23.         for(int i = 0; i < 10; ++i)
  24.         {
  25.                 Push(&stack, i);
  26.         }

  28.         for(int i = 0; i < 10; ++i)
  29.         {
  30.                 Pop(&stack, &e);
  31.                 printf("%d ", e);
  32.         }
  33.         printf("\n");

  35.         return 0;
  36. }

  38. void InitStack(sqStack *stack, ElemType *begin, ElemType *end)
  39. {
  40.         stack->base = begin;
  41.         stack->top = end - 1;
  42. }

  44. void Push(sqStack *stack, ElemType e)
  45. {
  46.         *stack->top-- = e;
  47. }

  49. void Pop(sqStack *stack, ElemType *e)
  50. {
  51.         *e = *++stack->top;
  52. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

圣狄雅哥
 楼主| 发表于 2018-1-28 21:24:18 | 显示全部楼层
我觉得一个数据要入栈先得让top指针向上移一位，再赋值。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

圣狄雅哥
 楼主| 发表于 2018-1-28 21:31:39 | 显示全部楼层
也就是说数据未入栈之前栈顶是非空的，这不太像链表里面的头结点
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

圣狄雅哥
 楼主| 发表于 2018-1-28 21:51:28 | 显示全部楼层
而且->这个运算符的优先级高于++，所以s->top++好像不能实现对指针的增加
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2018-1-28 22:50:32 | 显示全部楼层    本楼为最佳答案   
version1.c
  1. #include <stdio.h>

  3. typedef int ElemType;

  5. typedef struct
  6. {
  7.         ElemType *base;
  8.         ElemType *top;
  9. } sqStack;

  11. void InitStack(sqStack *stack, ElemType *begin, ElemType *end);
  12. void Push(sqStack *stack, ElemType e);
  13. void Pop(sqStack *stack, ElemType *e);

  15. int main()
  16. {
  17.         ElemType buff[100];
  18.         sqStack stack;
  19.         ElemType e;

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

  23.         for(int i = 0; i < 10; ++i)
  24.         {
  25.                 Push(&stack, i);
  26.         }

  28.         for(int i = 0; i < 10; ++i)
  29.         {
  30.                 Pop(&stack, &e);
  31.                 printf("%d ", e);
  32.         }
  33.         printf("\n");

  35.         return 0;
  36. }

  38. void InitStack(sqStack *stack, ElemType *begin, ElemType *end)
  39. {
  40.         stack->base = begin;
  41.         stack->top = end;
  42. }

  44. void Push(sqStack *stack, ElemType e)
  45. {
  46.         *--stack->top = e;
  47. }

  49. void Pop(sqStack *stack, ElemType *e)
  50. {
  51.         *e = *stack->top++;
  52. }
复制代码


version2.c
  1. #include <stdio.h>

  3. typedef int ElemType;

  5. typedef struct
  6. {
  7.         ElemType *base;
  8.         ElemType *top;
  9. } sqStack;

  11. void InitStack(sqStack *stack, ElemType *begin, ElemType *end);
  12. void Push(sqStack *stack, ElemType e);
  13. void Pop(sqStack *stack, ElemType *e);

  15. int main()
  16. {
  17.         ElemType buff[100];
  18.         sqStack stack;
  19.         ElemType e;

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

  23.         for(int i = 0; i < 10; ++i)
  24.         {
  25.                 Push(&stack, i);
  26.         }

  28.         for(int i = 0; i < 10; ++i)
  29.         {
  30.                 Pop(&stack, &e);
  31.                 printf("%d ", e);
  32.         }
  33.         printf("\n");

  35.         return 0;
  36. }

  38. void InitStack(sqStack *stack, ElemType *begin, ElemType *end)
  39. {
  40.         stack->base = begin;
  41.         stack->top = end - 1;
  42. }

  44. void Push(sqStack *stack, ElemType e)
  45. {
  46.         *stack->top-- = e;
  47. }

  49. void Pop(sqStack *stack, ElemType *e)
  50. {
  51.         *e = *++stack->top;
  52. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

圣狄雅哥
 楼主| 发表于 2018-1-29 10:36:23 | 显示全部楼层
本帖最后由 圣狄雅哥 于 2018-1-29 14:28 编辑

这个思路相当精妙，解答了我两个问题。虽然和小甲鱼给的那个从底向上入栈不同，但从顶到底入栈再从底到顶出栈完全正确，buff + (sizeof(buff) / sizeof(buff[0]这一句就求出了数组的长度，我服，看来论坛里面也是高手云集。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

圣狄雅哥
 楼主| 发表于 2018-1-29 10:59:44 | 显示全部楼层
不过还是没有考虑栈满了拓展空间以及栈空了应该退出
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2018-1-29 14:34:18 | 显示全部楼层
圣狄雅哥 发表于 2018-1-29 10:59
不过还是没有考虑栈满了拓展空间以及栈空了应该退出

^_^
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

圣狄雅哥
 楼主| 发表于 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);
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

#include

谢谢，不过我用不着这个
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

#include

路过的朋友谁帮忙看一下深红色的那部分代码，谢谢了
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

人造人
发表于 2018-1-30 20:00:47 | 显示全部楼层
圣狄雅哥 发表于 2018-1-29 16:00
路过的朋友谁帮忙看一下深红色的那部分代码，谢谢了

如果要动态增加栈空间，就不要使用数组，初始化时直接malloc申请
还有，从顶到底的入栈方式不适合动态增加栈空间，需要改为从底到顶的方式

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. typedef int ElemType;

  6. typedef struct
  7. {
  8.         ElemType *base;
  9.         ElemType *top;
  10.         int stackSize;
  11. } sqStack;

  13. void InitStack(sqStack *stack);
  14. void Push(sqStack *stack, ElemType e);
  15. void Pop(sqStack *stack, ElemType *e);

  17. int main(void)
  18. {
  19.         sqStack stack;
  20.         ElemType e;

  22.         InitStack(&stack);

  24.         for(int i = 0; i < 10; ++i)
  25.         {
  26.                 Push(&stack, i);
  27.         }

  29.         for(int i = 0; i < 10; ++i)
  30.         {
  31.                 Pop(&stack, &e);
  32.                 printf("%d ", e);
  33.         }
  34.         printf("\n");

  36.         return 0;
  37. }

  39. void InitStack(sqStack *stack)
  40. {
  41.         static const int defaultSize = 100;

  43.         stack->stackSize = defaultSize;
  44.         stack->base = malloc(stack->stackSize * sizeof(ElemType));
  45.         stack->top = stack->base;
  46. }

  48. void Push(sqStack *stack, ElemType e)
  49. {
  50.         static const int increment = 50;

  52.         if(stack->top == stack->base + stack->stackSize)
  53.         {
  54.                 stack->base = realloc(stack->base, (stack->stackSize + increment) * sizeof(ElemType));
  55.                 stack->top = stack->base + stack->stackSize;
  56.                 stack->stackSize += increment;
  57.         }
  58.         *stack->top++ = e;
  59. }

  61. void Pop(sqStack *stack, ElemType *e)
  62. {
  63.         *e = *--stack->top;
  64. }
复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-25 13:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表