链栈及栈的应用

链栈及栈的应用第1页，共26页，2023年，2月20日，星期二栈的链接存储结构及实现链栈：栈的链接存储结构特殊线性表——栈firsta1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。第2页，共26页，2023年，2月20日，星期二栈的链接存储结构及实现栈顶栈底链栈：栈的链接存储结构特殊线性表——栈topanan-1a1∧firsta1a2an∧ai两种示意图在内存中对应同一种状态topa1an-1an∧栈顶栈底第3页，共26页，2023年，2月20日，星期二3链栈

栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行.

由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。其类型说明为：

typedefstructStackNode{DataTypedatastructStackNode*next}; StackNode*top;第4页，共26页，2023年，2月20日，星期二(1)初始化栈

voidInitStack(StackNode*top){ top=NULL;}(2)判断空栈

intStackEmpty(StackNode*top){

returntop==NULL;}(3)取栈顶DataTypeGetTop(StackNode*top){if(StackEmpty(p))error(“stackisempty.”);

returntop–>data;}第5页，共26页，2023年，2月20日，星期二算法描述：voidPush(StackNode*top,DataTypex){ s=(StackNode*)malloc(sizeof(StackNode));

s->data=x;s->next=top;top=s;}topanan-1a1∧(4)入栈

xstop操作接口：voidPush(StackNode*top,DataTypex){为什么没有判断栈满？第6页，共26页，2023年，2月20日，星期二算法描述：DataTypePop(StackNode*top){if(StackEmpty(top)error(“stackunderflow.”);x=top->data;p=top;top=top->next;deletep;returnx;}(5)出栈操作接口：DataTypePop(StackNode*top)topanan-1a1∧topp

top++可以吗？第7页，共26页，2023年，2月20日，星期二

3.2栈的应用举例1数制转换

十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)

例如(1348)10=(2504)8，其运算过程如下：第8页，共26页，2023年，2月20日，星期二

NNdiv8Nmod8134816841682102125202

先入栈,再出栈入栈顺序:4,0,5,2.

出栈顺序:2,5,0,4

所以1348=(2504)o第9页，共26页，2023年，2月20日，星期二

voidconversion(){//输入任意一个非负十进制整数,打印输出与其等值的八进制数

InitStack(S);//初始化栈

scanf(“%d”,N);//输入一个非负十进制数

while(N){//非零时,循环

push(S,N%8);//余数入栈

N=N/8;}while(!StackEmpty(S)){Pop(S,e);//余数出栈

printf(“%d”,e);}}//conversion第10页，共26页，2023年，2月20日，星期二2行编辑程序接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。

例如:用户发现输入错误时,输入”#”(退格符),以表示前一个字符无效;输入”@”(退行符),表示当前输入的一行无效;

设一个栈接受输入,每输入一个字符,做如下判断:

是无效符,删除前一个入栈的符号是退行符,删除前一行入栈的符号其它,入栈第11页，共26页，2023年，2月20日，星期二行编辑程序算法如下:

voidLineEdit(){//利用字符栈S,从终端接收一行并传送至数据区

InitStack(S);//构造空栈

ch=getcher();//从终端接收第一个字符

while(ch!=EOF){//EOF为全文结束符

while(ch!=EOF&&ch!=‘\n’){switch(ch){case‘#’:Pop(S,c);//无效符,出栈

case‘@’:ClearStack(S);//退行符,清空栈

default:Push(S,ch);//其它,入栈

}

第12页，共26页，2023年，2月20日，星期二

ch=getchar();//从终端接收下一个字符

}//while//将从栈底到栈顶的栈内字符传送至调用过程的数据区ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}//LindeEdit第13页，共26页，2023年，2月20日，星期二表达式的计算在计算机中进行算术表达式的计算是通过栈来实现的。

(1)算术表达式的三种表示：中缀：——双目运算符出现在两个操作数中间,例：a+b前缀：——双目运算符出现在两个操作数前面,例：+ab后缀：——双目运算符出现在两个操作数后面,例：ab+(2)三种表达式之间的转换：按运算的优先次序全部加上括号，逐个括号写成另一种表示式（括号——*，/——+，-）注意：操作数出现的顺序不变3表达式求值第14页，共26页，2023年，2月20日，星期二三种表达式之间的转换：例将中缀表达式：——转换成后缀表达式（A+B）*D–E/（F+A*D）+CAB+FAD*+AB+D*EFAD*+/

AB+D*EFAD*+/-AB+D*EFAD*+/-C+例：A+B*D–E/F+A*D+CABD*+EF/-AD*+C+第15页，共26页，2023年，2月20日，星期二把表达式翻译成正确的机器执行指令,要正确地解释表达式.

算符优先法是根据算术四则运算的规定来编译或解释表达式的.

表达式由操作数,运算符,界限符组成.操作数可以是变量或常量;此处考虑的运算符仅为+-*/,界限符有左右括号和结束符”#”.

为实现算符优先法,可以使用两个工作栈.OPTR:存放运算符,OPND:存放操作数或运算结果.

第16页，共26页，2023年，2月20日，星期二算法的基本思想:(1)置操作数栈为空,表达式起始符”#”,作为运算符栈的栈底.(2)依次读入表达式中每个字符,若是操作数进OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为”#”).第17页，共26页，2023年，2月20日，星期二算法OperandTypeEvaluateExpression(){//算术表达式求值的算符优先算法,设OPTR和OPND分别为运算符栈和操作数栈;OP为算符(运算符和界限符)集合

InitStack(OPTR;)Push(OPTR,’#’);InitStack(OPND);c=getchar();while(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP)){Push((OPND,c);c=getchar();}//操作数进操作数栈

elseswitch(Precede(GetTop(OPTR),c){case‘<’://栈顶元素优先权低,进运算符栈

Push(OPTR,c);c=getchar();break;case‘=’://脱括号并接收下一个字符,左右括号或两”#”相遇

Pop(OPTR,x);c=getchar();break;第18页，共26页，2023年，2月20日，星期二

case‘>’://栈顶元素优先权高,运算符退栈,操作数退栈,//并将运算结果入栈

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression第19页，共26页，2023年，2月20日，星期二步骤OPTR栈OPND栈输入字符主要操作1#3*(7–2)#

PUSH(OPND,’3’)2#3*

(7–2)#

PUSH(OPTR,’*’)3#*3

(7–2)#

PUSH(OPTR,’(’)4#*(3

7

–2)#

PUSH(OPND,’7’)5#*(37

–2)#

PUSH(OPTR,’-’)6#*(-372)#

PUSH(OPND,’2’)7#*(-372)

#

operate(‘7’,’-’,’2’)8#*(35)#

POP(OPTR){消去括号}9#*35#

operate(‘3,’,’*’,’5’)10#15#

return(GetTop(OPND)“-”大于”)”“(”等于”)”第20页，共26页，2023年，2月20日，星期二3.3栈与递归

若在一个函数、过程或者数据结构定义的内部，直接或间接出现定义本身的应用，则称它们是递归的，或者是递归定义的。

递归是一种强有力的数学工具，它可使问题的描述和求解变得简洁和清晰。

递归算法常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归算法特别合适。第21页，共26页，2023年，2月20日，星期二例:斐波那契数列为：0、1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2)（当n>1时）。

写成递归函数有：

intfib(intn)

{if(n==0)return0;

if(n==1)return1;

if(n>1)returnfib(n-1)+fib(n-2);

}

第22页，共26页，2023年，2月20日，星期二

递归执行分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。

在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。第23页，共26页，2023年，2月20日，星期二

通常,一个函数调用另一个函数之前,要作如下工作:a)将实在参数,返回地址等信息传递给被调用函数保存;b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口.

从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调用函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.

变量和地址等数据都是保存在系统所分配的栈中的.为了保证递归函数正确执行,系统需设立一个”递归工作栈”,作为数