首页 > 数据库 > Sybase > 正文
数据结构-栈的链式存储
2015-04-29       个评论    来源:王照陆博客  
收藏    我要投稿

栈的链式存储

1 栈的链式表示
栈的链式存储结构称为链栈,是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此,链栈没有必要像单链表那样附加头结点,栈顶指针top就是链表的头指针。图3-4是栈的链式存储表示形式。

链栈的结点类型说明如下:
typedef  struct  Snode
{  ElemType   data ;
struct Snode  *next ;
} SNode, *Link_Stack ;

链栈基本操作的实现

2  链栈基本操作的实现
(1) 栈的初始化
SNode *Init_Link_Stack(void)
{  SNode *top ;
top=(SNode *)malloc(sizeof(SNode)) ;
if(top==NULL)
   return ERROR;
else
{   top->next=NULL ; 
     return(top) ;}
}
(2)  压栈(元素进栈)
Status push(SNode *top , ElemType  e)
{   SNode *p ;
p=(SNode *)malloc(sizeof(SNode)) ; 
if (!p)  return  ERROR; 
/*  申请新结点失败,返回错误标志 */
p->data=e ; 
p->next=top->next  ; 
top->next=p ;    /*  钩链  */
return OK;
}注意:1、与头插入法建立链表类似
 2、此处top结点的数据域不放数据,也可设置成存放数据,程序如何改?
(3)  弹栈(元素出栈)
ElemType pop(SNode *top )
/*  将栈顶元素出栈  */
{   SNode *p ;
ElemType  e ;
if  (top->next==NULL )
return ERROR ;    /*  栈空,返回错误标志    */
p=top->next ; e=p->data ;    /*  取栈顶元素  */
top->next=p->next ;     /*  修改栈顶指针  */
free(p) ; 
return OK ;
}

输出栈中元素

void print(SqStack *S)
{   
    int c;
    cout<<"输出栈中元素"<<endl;

    for( c=S.top--;c>=0;c--)
    {
        cout<<S.bottom[c]<<endl;
    }

}

栈与递归调用的实现

栈的另一个重要应用是在程序设计语言中实现递归调用。
递归调用:一个函数(或过程)直接或间接地调用自己本身,简称递归(Recursive)。
递归是程序设计中的一个强有力的工具。因为递归函数结构清晰,程序易读,正确性很容易得到证明。
为了使递归调用不至于无终止地进行下去,实际上有效的递归调用函数(或过程)应包括两部分:递推规则(方法),终止条件。

系统实现递归需要一个系统栈 (递归工作栈) ,用于在程序运行时处理函数调用。
系统栈是一块特殊的存储区。当一个函数被调用时,系统创建一个工作记录,称为栈桢(stack frame),并将其置于栈顶。
初始时只包括返回地址和指向上一栈的指针。
当该函数调用另一个函数时,该函数的局部变量、参数将加到它的栈桢中。
一个函数运行结束,将从栈中删除它的栈桢,程序控制返回原调用函数继续执行下去。

从被调函数返回调用函数的一般步骤
若栈为空,则执行正常返回。
否则,从栈顶弹出一个工作记录,将“工作记录”中的参数值、局部变量值赋给相应的变量;。
读取返回地址,将函数值赋给相应的变量。
转移到返回地址。

递归算法的优缺点

优点
程序非常简洁而清晰,并且易于分析,可读性较强。
缺点
费空间:系统实现递归需要一个系统栈,用于在程序运行时间处理函数调用。
费时:局部变量、形式参数和返回地址的进栈、出栈以及参数的传递需要费时,而且递归中的重复计算也很浪费时间。

点击复制链接 与好友分享!回本站首页
相关TAG标签 链式 数据结构
上一篇:java连接redis
下一篇:Java从入门到精通——数据库篇MongoDB导出,导入,备份
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站