• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C语言实现顺序栈心得

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

栈的构成及初始化

对于“先进后出”的顺序栈,需要控制3个量:栈元素,栈顶指针,栈容量。

栈容量即栈的最大容量,若超过会产生溢出错误。当然,必要时也可以扩充容量。

栈元素可以通过动态数组( base[] )存放。初始化时用 malloc 申请(栈容量 * 元素类型)个空间。

栈顶指针用于记录栈元素个数,始终指向栈顶元素的上一个单位(如 栈顶元素为base[3],栈顶指针为4),这样就能实现元素个数的记录。不过,栈顶指针只是一种形象化的叫法,方便起见,一般将其定义为 int 型。初始化时,栈顶指针置0。

 

定义结构体

struct sta
{
    int top;
    int *base;
    int size;
};

typedef struct sta ZAN;

 

栈的建立(分配空间)

ZAN* create()
{
    ZAN *p;

    p=(ZAN *)malloc(sizeof(ZAN));

    return p;
}

 

栈的初始化

void zer(ZAN *s)
{
    s->top=0;
    s->size=INI;                        //#define INI 10
    s->base=(int *)malloc(INI*sizeof(int));
}

 

压栈

压栈就是让元素进栈,栈顶指针 top 加一,元素存入数组 base[] 。如果已经栈满,可以增加内存空间(实际上是重新分配空间),此时栈容量 size 也要加一。用返回值判断是否压栈成功。

 

int push(ZAN *s,int x)
{

    if( (s->top) >= (s->size) )
    {
        s->base=(int *)realloc(s->base,(s->size+1)*sizeof(int));
        if(!s->size) return 0;
        s->size++;
    }
    s->top++;
    s->base[s->top-1]=x;
    return 1;

}

 

取栈顶元素

取顶只用把栈顶元素的值记录下来,而不需要让其出栈。可以用指针来取值。同样,用返回值判断是否取顶成功。

 

int gettop(ZAN *s,int *e)
{
    if(s->top==0) return 0;
    else
    {
        *e=s->base[(s->top)-1];
        return 1;
    }
}

 

弹栈

弹栈是取出其值,并让栈顶元素出栈,top减一。同样,用指针记录其值,用返回值判断是否弹栈成功。

 

int pop(ZAN *s,int* e)
{
    if(!s->top) return 0;
    else
    {
        *e=s->base[(s->top)-1];
        s->top--;
        return 1;
    }
}

 

求栈长

取出 top 的值即可

 

int getlen(ZAN* s)
{
    return s->top;
}

 

判断栈是否为空

看 top 是否为0即可

 

int isempty(ZAN* s)
{
    if(!s->top) return 0;
    else return 1;
}

 

输出栈元素

将 base[] 自顶向下输出即可,不对栈进行任何操作。

 

void list(ZAN* s)

{

  int i;

 

  puts("\n list ZAN:");

  for(i=s->top-1;i>=0;i--)

  {

    if(i!=s->top-1) printf("\n");          //此处可以用空格代替换行

    printf("%d",s->base[i]);

  }

  puts("");

}

 

测试功能

 

// TEST FUNCTION

main()
{
    ZAN *create();
    void zer(ZAN *s);
    int push(ZAN *s,int x);
    int gettop(ZAN *s,int *e);
    int getlen(ZAN* s);
    int isempty(ZAN* s);
    void list(ZAN* s);
    ZAN *s;
    int n,*e,i=1;

    i=1;e=&i;                                                           // protect


    s=create();                                                         // create a stack
    zer(s);                                                             // initialize

    if(!isempty(s)) puts("ZAN is empty\n");                               // empty?
    else puts("ZAN is not not empty\n");

    puts(" push int x:");                // push an element in
    scanf("%d",&n);
    if(push(s,n)) ;
    else printf(" push %d error\n",n);

    if(gettop(s,e)) printf("gettop %d\n",*e);                      // get top element
    else puts("gettop error");

    printf("\n push int x:\n");
    scanf("%d",&n);
    if(push(s,n)) ;                                            // push an element in
    else printf("push %d error\n",n);


    if(gettop(s,e)) printf("gettop %d\n",*e);                      // get top element
    else puts("gettop error");

    if(pop(s,e)) printf("pop %d\n",*e);          //pop top element
    else printf("pop %d error\n",n);

    if(gettop(s,e)) printf("gettop %d\n",*e);                      // get top element
    else puts("gettop error");

    if(!isempty(s)) puts("ZAN is empty\n");                               // empty?
    else puts("ZAN is not not empty\n");
    if(isempty(s)) list(s);

    printf("\n push int x:\n");
    scanf("%d",&n);
    if(push(s,n)) ;                                            // push an element in
    else printf("push %d error\n",n);

    if(isempty(s)) list(s);                  //output ZAN
}


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#学习与上位机开发之文件操作(EXCEL保存案例)发布时间:2022-07-14
下一篇:
c#创建文件/文件夹对话框发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap