⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 class11.htm

📁 Data Structure Ebook
💻 HTM
字号:
🔍 
<html>
<head>
<title>数据结构--数据空间http://zmofun.topcool.net</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
</head>

<body bgcolor="#FFFFFF">
<p align="center"><b>第十一课</b></p>
<p><b><i>本课主题：</i></b> 栈的应用</p>
<p><b><i>教学目的：</i></b> 掌握栈的应用方法,理解栈的重要作用</p>
<p><b><i>教学重点：</i></b> 利用栈实现行编辑,利用栈实现表达式求值</p>
<p><b><i>教学难点：</i></b> 利用栈实现表达式求值</p>
<p><b><i>授课内容：</i></b></p>
<p>一、<a name="#1101"></a>栈应用之一：数制转换</p>
<blockquote> 
  <p>将十进制数转换成其它进制的数有一种简单的方法：</p>
  <p>例：十进制转换成八进制：(66)<font size="-3">10</font>=(102)<font size="-3">8</font></p>
  <p>66/8=8 余 2</p>
  <p> 8/8=1 余 0</p>
  <p>1/8=0 余 1</p>
  <p>结果为余数的逆序:102 。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换：</p>
  <table width="100%" border="1" cellspacing="0">
    <tr bgcolor="#0066FF"> 
      <td height="71"> 
        <p><font color="#FFFF33"><b>void conversion() { </b></font></p>
        <p><b><font color="#FFFF33">pSqStack S; </font></b></p>
        <p><b><font color="#FFFF33">SElemType e; </font></b></p>
        <p><b><font color="#FFFF33">int n; </font></b></p>
        <p><b><font color="#FFFF33">InitStack(&S); </font></b></p>
        <p><b><font color="#FFFF33">printf("Input a number to convert to OCT:\n");</font></b></p>
        <p><b><font color="#FFFF33"> scanf("%d",&n); </font></b></p>
        <p><b><font color="#FFFF33">if(n<0) </font></b></p>
        <blockquote> 
          <p><b><font color="#FFFF33">{ printf("\nThe number must be over 0."); 
            </font></b></p>
          <p><b><font color="#FFFF33">return;}</font></b></p>
        </blockquote>
        <p><b><font color="#FFFF33"> if(!n) Push(S,0); </font></b></p>
        <p><b><font color="#FFFF33">while(n){ </font></b></p>
        <blockquote> 
          <p><b><font color="#FFFF33">Push(S,n%8); </font></b></p>
          <p><b><font color="#FFFF33">n=n/8; } </font></b></p>
        </blockquote>
        <p><b><font color="#FFFF33">printf("the result is: "); </font></b></p>
        <p><b><font color="#FFFF33">while(!StackEmpty(*S)){ </font></b></p>
        <blockquote> 
          <p><b><font color="#FFFF33">Pop(S,&e); printf("%d",e);}</font></b></p>
        </blockquote>
        <p><b><font color="#FFFF33"> }</font></b></p>
      </td>
    </tr>
  </table>
  <p>请看：<a href="convert.txt">数制转换的C源程序</a></p>
</blockquote>
<p>二、<a name="#1102"></a>栈应用之二：行编辑</p>
<blockquote>
  <p>一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定＃为退格符，以表示前一个字符无效，@为退行符，表示当前行所有字符均无效。</p>
  <p>例：在终端上用户输入为</p>
  <p>whli##ilr#e(s#*s) 应为</p>
  <p>while(*s)</p>
  <table width="89%" border="1" cellspacing="0">
    <tr bgcolor="#0066FF"> 
      <td> 
        <p><font color="#FFFF33"><b>void LineEdit() {</b></font></p>
        <p><b><font color="#FFFF33"> pSqStack S,T; char str[1000]; </font></b></p>
        <p><b><font color="#FFFF33">int strlen=0; char e; char ch; </font></b></p>
        <p><b><font color="#FFFF33">InitStack(&S); </font></b></p>
        <p><b><font color="#FFFF33">InitStack(&T); </font></b></p>
        <p><b><font color="#FFFF33">ch=getchar();</font></b></p>
        <p><b><font color="#FFFF33"> while(ch!=EOFILE) {</font></b></p>
        <blockquote> 
          <p><b><font color="#FFFF33"> while(ch!=EOFILE&&ch!='\n') {</font></b></p>
          <blockquote> 
            <p><b><font color="#FFFF33"> switch(ch){ </font></b></p>
            <blockquote> 
              <p><b><font color="#FFFF33">case '#': Pop(S,&ch); break; </font></b></p>
              <p><b><font color="#FFFF33">case '@': ClearStack(S); break; </font></b></p>
              <p><b><font color="#FFFF33">default: Push(S,ch); break; } </font></b></p>
            </blockquote>
            <p><b><font color="#FFFF33">ch=getchar(); </font></b></p>
          </blockquote>
          <p><b><font color="#FFFF33">} </font></b></p>
          <p><b><font color="#FFFF33">if(ch=='\n') Push(S,ch);</font></b></p>
          <p><b><font color="#FFFF33"> while(!StackEmpty(*S)) { Pop(S,&e); Push(T,e); 
            } </font></b></p>
          <p><b><font color="#FFFF33">while(!StackEmpty(*T)) { Pop(T,&e); str[strlen++]=e; 
            } </font></b></p>
          <p><b><font color="#FFFF33">if(ch!=EOFILE) ch=getchar();</font></b></p>
        </blockquote>
        <p><b><font color="#FFFF33"> } </font></b></p>
        <p><b><font color="#FFFF33">str[strlen]='\0'; </font></b></p>
        <p><b><font color="#FFFF33">printf("\n%s",str); </font></b></p>
        <p><b><font color="#FFFF33">DestroyStack(S); </font></b></p>
        <p><b><font color="#FFFF33">DestroyStack(T); </font></b></p>
        <p><b><font color="#FFFF33">}</font></b></p>
      </td>
    </tr>
  </table>
  <p>&nbsp;</p>
  <p>请看:<a href="lineedit.txt">行编辑的C源程序 </a></p>
</blockquote>
<p>三、<a name="#1103"></a>栈应用之三：表达式求值</p>
<blockquote> 
  <p>一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例：1+2*3有+,*两个运算符，*的优先级高,1,2,3是操作数。 
    界定符有括号和表达式结束符等。</p>
  <p>算法基本思想：</p>
  <p>１首先置操作数栈为空栈，表达式起始符＃为运算符栈的栈底元素；</p>
  <p>２依次讲稿表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。</p>
  <table width="97%" border="1" cellspacing="0">
    <tr bgcolor="#0066FF"> 
      <td> 
        <p><b><font color="#FFFF00">char EvaluateExpression() {</font></b></p>
        <p><font color="#FFFF00"><b> SqStack *OPND,*OPTR; </b></font></p>
        <p><font color="#FFFF00"><b>char c,x,theta; char a,b; </b></font></p>
        <p><font color="#FFFF00"><b>InitStack(&OPTR); Push(OPTR,'#'); </b></font></p>
        <p><font color="#FFFF00"><b>InitStack(&OPND); </b></font></p>
        <p><font color="#FFFF00"><b>c=getchar(); </b></font></p>
        <p><font color="#FFFF00"><b>while(c!='#'||GetTop(*OPTR)!='#') {</b></font></p>
        <blockquote> 
          <p><font color="#FFFF00"><b> if(!In(c,OP)) {Push(OPND,c);c=getchar();} 
            </b></font></p>
          <p><font color="#FFFF00"><b>else </b></font></p>
          <blockquote> 
            <p><font color="#FFFF00"><b>switch(Precede(GetTop(*OPTR),c)) { </b></font></p>
            <blockquote> 
              <p><font color="#FFFF00"><b>case '<': Push(OPTR,c); c=getchar(); 
                break; </b></font></p>
              <p><font color="#FFFF00"><b>case '=': Pop(OPTR,&x); c=getchar(); 
                break; </b></font></p>
              <p><font color="#FFFF00"><b>case '>': Pop(OPTR,&theta); </b></font></p>
              <blockquote> 
                <blockquote> 
                  <p><font color="#FFFF00"><b>Pop(OPND,&b); Pop(OPND,&a); </b></font></p>
                  <p><font color="#FFFF00"><b>Push(OPND,Operate(a,theta,b));</b></font></p>
                  <p><font color="#FFFF00"><b> break; </b></font></p>
                </blockquote>
              </blockquote>
            </blockquote>
            <p><font color="#FFFF00"><b>} </b></font></p>
          </blockquote>
          <p><font color="#FFFF00"><b>} </b></font></p>
        </blockquote>
        <p><font color="#FFFF00"><b>c=GetTop(*OPND); </b></font></p>
        <p><font color="#FFFF00"><b>DestroyStack(OPTR); </b></font></p>
        <p><font color="#FFFF00"><b>DestroyStack(OPND); </b></font></p>
        <p><font color="#FFFF00"><b>return c; </b></font></p>
        <p><font color="#FFFF00"><b>} </b></font></p>
      </td>
    </tr>
  </table>
  <p>请看:<a href="expre.c">表达式求值的C源程序 </a></p>
  </blockquote>
<p>四、总结</p>
<blockquote>
  <p>栈的先进后出、后进先出的特性。</p>
</blockquote>
<p><a href="../index.htm">回目录</a> <a href="../class10/class10.htm">上一课</a> <a href="../class12/class12.htm">下一课</a></p>
</body>
</html>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -