数据结构教程第十一课栈的应用

文章作者 100test 发表时间 2007:03:10 18:29:42
来源 100Test.Com百考试题网

本课主题： 栈的应用
教学目的： 掌握栈的应用方法,理解栈的重要作用
教学重点： 利用栈实现行编辑,利用栈实现表达式求值
教学难点： 利用栈实现表达式求值
授课内容：
一、栈应用之一：数制转换
将十进制数转换成其它进制的数有一种简单的方法：
例：十进制转换成八进制：(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:\n").
scanf("%d",&.n).
if(n<0)
{ printf("\nThe 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!=’\n’) {
switch(ch){
case ’#’: Pop(S,&.ch). break.
case ’@’: ClearStack(S). break.
default: Push(S,ch). break. }
ch=getchar().
}
if(ch==’\n’) 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]=’\0’.
printf("\n%s",str).
DestroyStack(S).
DestroyStack(T).
}


请看:行编辑的C源程序