栈的操作算法实现Word下载.docx
《栈的操作算法实现Word下载.docx》由会员分享，可在线阅读，更多相关《栈的操作算法实现Word下载.docx（9页珍藏版）》请在冰点文库上搜索。
{if（sq->
top==maxsize-1） {printf（"
栈满"
）;
return（0）;
else {sq->
top++;
sq->
data[sq->
top]=x;
}
3.退栈:
退栈先要将栈顶元素取出，由参数返回，并将栈顶减１。
intPop（SqStackTp*sq,ElementType*x）;
{if（sq->
top==-1）{printf（"
下溢"
return（0）;
else{*x=sq->
top];
top--;
};
4.判栈空:
intEmptyStack（SqStackTp*sq） /*若栈空返回1;
否则返回0*/
{ if（sq->
top==-1）return
（1） elsereturn（0）;
5.读栈顶元素:
intGetTop（SqStackTp*sq,ElementType*x）
/*取栈顶元素，栈顶元素通过参数返回*/
{if（sq->
top==-1）return（0）;
else{*x=sq->
6.顺序栈应用举例（进栈与出栈）
#include"
stdio.h"
#defineElementTypechar
#definemaxsize40
typedefstruct
{ElementTypedata[maxsize];
inttop;
}SqStackTp;
intInitStack（SqStackTp*sq）
{sq->
intPush（SqStackTp*sq,ElementTypex）
{if（sq->
else {sq->
}
intPop（SqStackTp*sq,ElementType*x）
{if（sq->
top==-1）{printf（"
intEmptyStack（SqStackTp*sq）
top==-1）return
（1）;
elsereturn（0）;
/*主函数*/
voidmain（）
{SqStackTpsq;
typedefchElementType;
InitStack（&
sq）;
for（ch='
A'
;
ch<
='
+12;
ch++）
{Push（&
sq,ch）;
printf（"
%c"
ch）;
printf（"
\n"
while（!
EmptyStack（&
sq））
{Pop（&
sq,&
ch）;
printf（"
}
运行结果：
ABCDEFGHIJKLM
MLKJIHGFEDCBA
二链栈的实现
链栈类型定义如下：
typedefstructnode
{ElementTypedata;
structnode*next;
}node；
node*LStackTp;
下面讨论栈的基本运算在链栈上的实现。
栈初始化的作用是设置一个空栈。
而一个空的链栈可以用栈顶指针为NULL来表示。
voidInitStack（LStackTp*ls）
{ *ls=NULL;
进栈算法的基本步骤包括：
①申请一个新结点,并将x的值送入该结点的data域;
②将该结点链入栈中使之成为新的栈顶结点。
voidPush（LStackTp*ls,ElementTypex）
{LStackTpp;
p=/*申请一个新结点*/
p->
data=（LStackTp）malloc（sizeof（node））;
x;
/*元素的值填入新结点的data域*/
next=*ls;
/*原栈顶链入新结点的next域*/
*ls=p;
/*新结点成为新的栈顶*/
退栈算法的基本步骤包括：
①栈顶结点的data域的值由参数返回，并取下栈顶结点，让它的下一个结点成为新的栈顶；
②将取出的栈顶结点空间释放。
intPop（LStackTp*ls,ElementType*x）
/*栈顶元素通过参数返回，它的直接后继成为新的栈顶*/
{LStackTpp;
if（（*ls）!
=NULL）
{p=*ls;
*x=p->
data;
/*栈顶元素通过参数返回*/
*ls=p->
next;
/*原栈顶的下一个结点成为新的栈顶*/
free（p）;
/*释放原栈顶结点空间*/
return1;
}
elsereturn0;
intEmptyStack（LStackTp*ls）/*若栈为空则返回值1,否则返回值0*/
{ if（*ls==NULL）return
（1）;
elsereturn（0）;
intGetTop（LStackTp*ls,ElementType*x）/*取栈顶元素*/
{if（（*ls）!
=NULL）{*x=（*ls）->
return1;
}elsereturn0;
6.链栈应用举例（进栈与出栈）
1） #include"
#definesizesizeof（node）
{ElementTypedata;
structnode*next;
}node;
voidInitStack（LStackTp*ls）
{ *ls=NULL;
voidPush（LStackTp*ls,ElementTypex）
{LStackTpp;
p=（LStackTp）malloc（size）;
p->
data=x;
*ls=p;
intPop（LStackTp*ls,ElementType*x）
if（（*ls）!
{p=*ls;
*x=p->
*ls=（*ls）->
free（p）;
return
（1）;
}elsereturn（0）;
intEmptyStack（LStackTpls）
{
if（ls==NULL）return
（1）;
elsereturn（0）;
voidmain（）
{LStackTpls;
ElementTypech;
InitStack（ls）;
ls,ch）;
ls->
data）;
EmptyStack（ls））
ls,&
2）写一个算法，借助栈将一个带头结点的单链表倒置。
head
─
→
头
a1
a2
→......
an
NULL
分析：
这里可利用栈的特征，先沿着链表从头至尾扫描一遍，将链表的每个结点的data域的值依次进栈，然后再沿着链表从头至尾扫描一遍，同时栈中元素依次出栈，并填入到链表的每个结点的data域中。
算法如下：
voidreverse_list（LkListTp*head）
{LStackTpls,p;
ElementTypex;
InitStack（&
ls）;
/*初始化链栈*/
p=（*head）->
while（p!
{Push（&
ls,p->
p=p->
while（!
{Pop（&
x）;
p->
实现程序如下：
（用链栈实现单链表倒置）
typedefstruct {
ElementTypedata;
}node;
node*LkListTp;
{*ls=NULL;
{LStackTpq;
q=（LStackTp）malloc（size）;
/*申请一个新结点*/
q->
*ls=q;
/*新结点成为新的栈顶*/
/*栈顶元素通过参数返回，它的直接后继成为新的栈顶*/
*ls=（*ls）->
/*原栈顶的下一个结点成为新的栈顶*/
return
（1）;
intEmptyStack（LStackTpls）/*若栈为空则返回值1,否则返回值0*/
ElementTypex;
while（p!
while（!
LkListTpcreate_lklist2（）
/*直接建表算法。
p是一个pointer类型的变量，用来指示链入位置*/
LkListTpp,q,s,head;
ElementTypex;
head=（LkListTp）malloc（size）;
/*生成头结点*/
p=head;
/*尾指针置初值*/
scanf（"
&
/*读入第一个元素*/
while（x!
?
'
）/*输入的不是结束标志时继续链入*/
{
q=（LkListTp）malloc（size）;
q->
/*生成一个新结点*/
p->
next=q;
/*新结点链入*/
p=q;
/*修改尾指针指向新的表尾*/
scanf（"
/*读入下一个元素*/
next=NULL;
return（head）;
/*置尾结点标志*/
LkListTpp,q,head;
\ninputLkList:
"
head=create_lklist2（）;
reverse_list（&
head）;
\noutputLkList:
p=head->
while（p!
{printf（"
p->
p=p->
inputLkList:
ABCDEFG?
outputLkList:
GFEDCBA
升级会员 