首页 / 软件开发 / 数据结构与算法 / 数据结构教程 第十一课 栈的应用

数据结构教程 第十一课 栈的应用2007-05-17本课主题： 栈的应用

教学目的： 掌握栈的应用方法,理解栈的重要作用

教学重点： 利用栈实现行编辑,利用栈实现表达式求值

教学难点： 利用栈实现表达式求值

授课内容：

一、栈应用之一：数制转换

将十进制数转换成其它进制的数有一种简单的方法：

例：十进制转换成八进制：（66）10=（102）8

66/8=8 余 2

8/8=1 余 0

1/8=0 余 1

结果为余数的逆序:102 。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换：

void conversion（） { pSqStack S; SElemType e; int n; InitStack（&S）; printf（"Input a number to convert to OCT: "）; scanf（"%d",&n）; if（n<0） { printf（" The number must be over 0."）; return;} if（！n） Push（S,0）; while（n）{ Push（S,n%8）; n=n/8; } printf（"the result is: "）; while（！StackEmpty（*S））{ Pop（S,&e）; printf（"%d",e）;} }

请看：数制转换的C源程序

二、栈应用之二：行编辑

一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定＃为退格符，以表示前一个字符无效，@为退行符，表示当前行所有字符均无效。

例：在终端上用户输入为

whli##ilr#e（s#*s） 应为

while（*s）

void LineEdit（） { pSqStack S,T; char str[1000]; int strlen=0; char e; char ch; InitStack（&S）; InitStack（&T）; ch=getchar（）; while（ch！=EOFILE） { while（ch！=EOFILE&&ch！=" "） { switch（ch）{ case "#": Pop（S,&ch）; break; case "@": ClearStack（S）; break; default: Push（S,ch）; break; } ch=getchar（）; } if（ch==" "） Push（S,ch）; while（！StackEmpty（*S）） { Pop（S,&e）; Push（T,e）; } while（！StackEmpty（*T）） { Pop（T,&e）; str[strlen++]=e; } if（ch！=EOFILE） ch=getchar（）; } str[strlen]=""; printf（" %s",str）; DestroyStack（S）; DestroyStack（T）; }

请看:行编辑的C源程序

三、栈应用之三：表达式求值

一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例：1+2*3有+,*两个运算符，*的优先级高,1,2,3是操作数。 界定符有括号和表达式结束符等。

算法基本思想：

１首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素；

２依次讲稿表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。

char EvaluateExpression（） { SqStack *OPND,*OPTR; char c,x,theta; char a,b; InitStack（&OPTR）; Push（OPTR,"#"）; InitStack（&OPND）; c=getchar（）; while（c！="#"||GetTop（*OPTR）！="#"） { if（！In（c,OP）） {Push（OPND,c）;c=getchar（）;} else switch（Precede（GetTop（*OPTR）,c）） { case "<": Push（OPTR,c）; c=getchar（）; break; case "=": Pop（OPTR,&x）; c=getchar（）; break; case ">": Pop（OPTR,&theta）; Pop（OPND,&b）; Pop（OPND,&a）; Push（OPND,Operate（a,theta,b））; break; } } c=GetTop（*OPND）; DestroyStack（OPTR）; DestroyStack（OPND）; return c; }

请看:表达式求值的C源程序

四、总结

栈的先进后出、后进先出的特性。