数据结构-栈的链式存储
栈的链式存储
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)，并将其置于栈顶。
初始时只包括返回地址和指向上一栈的指针。
当该函数调用另一个函数时，该函数的局部变量、参数将加到它的栈桢中。
一个函数运行结束，将从栈中删除它的栈桢，程序控制返回原调用函数继续执行下去。
从被调函数返回调用函数的一般步骤
若栈为空，则执行正常返回。
否则，从栈顶弹出一个工作记录，将“工作记录”中的参数值、局部变量值赋给相应的变量；。
读取返回地址，将函数值赋给相应的变量。
转移到返回地址。
递归算法的优缺点
优点
程序非常简洁而清晰，并且易于分析，可读性较强。
缺点
费空间：系统实现递归需要一个系统栈，用于在程序运行时间处理函数调用。
费时：局部变量、形式参数和返回地址的进栈、出栈以及参数的传递需要费时，而且递归中的重复计算也很浪费时间。
本站文章为和通数据库网友分享或者投稿，欢迎任何形式的转载，但请务必注明出处.
同时文章内容如有侵犯了您的权益，请联系QQ：970679559，我们会在尽快处理。