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

📄 ds3.2.htm

📁 这是清华大学所用的数据结构的电子版教材
💻 HTM
📖 第 1 页 / 共 5 页
字号:
🔍
12345 
<html>

<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>

<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">

<!--mstheme--><font face="宋体">

<p:colorscheme
 colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><font face="oúì?,SimHei" lang="ZH-CN" size="5" color="#FFFFFF"><b>3.2  
栈的应用举例</b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; <font FACE="??ì?,SimSun" LANG="ZH-CN">  
由于栈的“先进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。</font></b></font></p>
<p ALIGN="JUSTIFY"><b><font color="#FFFFFF"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5">例</font><font size="5"> 
3.1 <font FACE="??ì?,SimSun" LANG="ZH-CN">简单应用：数制转换问题</font></font></font></b></p>  
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">&nbsp;将十进制数</font>N<font FACE="??ì?,SimSun" LANG="ZH-CN">转换为</font>r<font FACE="??ì?,SimSun" LANG="ZH-CN">进制的数，其转换方法利用辗转相除法：以</font>N=3456<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>r=8<font FACE="??ì?,SimSun" LANG="ZH-CN">为例转换方法如下：</font></b></font></p>
<div align="center">
  <center>
  <!--mstheme--></font>
  <table border="1" width="431" height="166" bordercolorlight="#3366CC" bordercolordark="#000000">
    <tr>
      <td width="108" height="44" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
N</b></font><!--mstheme--></font></td>
      <td width="108" height="44" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> N / 8 <font FACE="??ì?,SimSun" LANG="ZH-CN">（整除）</font>   
        </b></font><!--mstheme--></font></td>
      <td width="108" height="44" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> N % 8<font FACE="??ì?,SimSun" LANG="ZH-CN">（求余）</font></b></font><!--mstheme--></font></td>  
      <td width="107" height="44" align="center"><!--mstheme--><font face="宋体"><font color="#FFFFFF" size="5"><b>次序</b></font><!--mstheme--></font></td>
    </tr>
    <tr>
      <td width="108" height="26" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>3467</b></font><!--mstheme--></font></td>
      <td width="108" height="26" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
433</b></font><!--mstheme--></font></td>
      <td width="108" height="26" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
3</b></font><!--mstheme--></font></td>
      <td width="107" height="67" align="center" rowspan="4"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">低</font></b></font>
        <p>　</p>
        <p><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">高</font></b></font><!--mstheme--></font></td>
    </tr>
    <tr>
      <td width="108" height="14" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>433</b></font><!--mstheme--></font></td>
      <td width="108" height="14" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
54</b></font><!--mstheme--></font></td>
      <td width="108" height="14" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
1</b></font><!--mstheme--></font></td>
    </tr>
    <tr>
      <td width="108" height="7" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
54</b></font><!--mstheme--></font></td>
      <td width="108" height="7" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
6</b></font><!--mstheme--></font></td>
      <td width="108" height="7" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
6</b></font><!--mstheme--></font></td>
    </tr>
    <tr>
      <td width="108" height="20" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
6</b></font><!--mstheme--></font></td>
      <td width="108" height="20" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
0</b></font><!--mstheme--></font></td>
      <td width="108" height="20" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b> 
6</b></font><!--mstheme--></font></td>
    </tr>
  </table>
  <!--mstheme--><font face="宋体">
  </center>
</div>
<p ALIGN="JUSTIFY"><font color="#FFFFFF"><b><font size="5"><font FACE="??ì?,SimSun" LANG="ZH-CN">所以：（</font>3456<font FACE="??ì?,SimSun" LANG="ZH-CN">）</font><sub>10 
</sub>=<font FACE="??ì?,SimSun" LANG="ZH-CN">（</font>6613<font FACE="??ì?,SimSun" LANG="ZH-CN">）</font></font></b></font><sub><font color="#FFFFFF"><b><font size="5">8</font></b></font></p>
</sub>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">&nbsp;&nbsp;  
我们看到所转换的</font>8<font FACE="??ì?,SimSun" LANG="ZH-CN">进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位</font>8<font FACE="??ì?,SimSun" LANG="ZH-CN">进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。</font></b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">算法思想如下：当</font>N&gt;0<font FACE="??ì?,SimSun" LANG="ZH-CN">时重复</font>1<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>2</b></font></p>
<ol>
  <li><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">若</font> 
    N<font FACE="??ì?,SimSun" LANG="ZH-CN">≠</font>0<font FACE="??ì?,SimSun" LANG="ZH-CN">，则将</font>N   
    % r <font FACE="??ì?,SimSun" LANG="ZH-CN">压入栈</font>s<font FACE="??ì?,SimSun" LANG="ZH-CN">中</font>   
    <font FACE="??ì?,SimSun" LANG="ZH-CN">，执行</font>2;<font FACE="??ì?,SimSun" LANG="ZH-CN">若</font>N=0<font FACE="??ì?,SimSun" LANG="ZH-CN">，将栈</font>s<font FACE="??ì?,SimSun" LANG="ZH-CN">的内容依次出栈，算法结束。</font></b></font></li>  
  <li><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">用</font>N   
    / r <font FACE="??ì?,SimSun" LANG="ZH-CN">代替</font> N</b></font></li>  
</ol>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>算法如下：</b></font></p>
<!--mstheme--></font>
<table border="1" width="100%" bordercolorlight="#3366CC" bordercolordark="#000000">
  <tr>
    <td width="45%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">typedef   
int datatype;&nbsp;</font></b><!--mstheme--></font></td>  
    <td width="55%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">#define L 10</font></b><!--mstheme--></font></td> 
  </tr>
  <tr>
    <td width="45%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">void  
conSq1(int N<font face="??ì?,SimSun" lang="ZH-CN">,</font>int  
r)</font></b><!--mstheme--></font></td>
    <td width="55%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4"> void conSq2(int N<font FACE="??ì?,SimSun" LANG="ZH-CN">，</font>int   
r)</font></b><!--mstheme--></font></td>
  </tr>
  <tr>
    <td width="45%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">{ </font></b><!--mstheme--></font></td>
    <td width="55%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4"> 
{ </font></b><!--mstheme--></font></td>
  </tr>
  <tr>
    <td width="45%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;SeqStack   
s;</font></b><!--mstheme--></font></td>
    <td width="55%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;int s[L],top;/</font><font color="#FF0000" size="4">*<font FACE="??ì?,SimSun" LANG="ZH-CN">定义一个顺序栈</font>*</font><font color="#FFFFFF" size="4">/</font></b><!--mstheme--></font></td> 
  </tr>
  <tr>
    <td width="45%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;datetype   
x;</font></b><!--mstheme--></font></td>
    <td width="55%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;int x;</font></b><!--mstheme--></font></td>  
  </tr>
  <tr>
    <td width="45%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;Init_SeqStack(&amp;s);</font></b><!--mstheme--></font></td>
    <td width="55%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;top =-1; /</font><font color="#FF0000" size="4">*<font FACE="??ì?,SimSun" LANG="ZH-CN">初始化栈</font>*</font><font color="#FFFFFF" size="4">/</font></b><!--mstheme--></font></td> 
  </tr>
  <tr>
    <td width="45%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;while   
( N   
)</font></b><!--mstheme--></font></td>
    <td width="55%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;while ( N )</font></b><!--mstheme--></font></td>  
  </tr>
  <tr>
    <td width="45%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;{&nbsp;</font></b><!--mstheme--></font></td>
    <td width="55%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp;{</font></b><!--mstheme--></font></td>
  </tr>
  <tr>
    <td width="45%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp; Push_SeqStack(&amp;s,N%r);</font></b><!--mstheme--></font></td> 
    <td width="55%"><!--mstheme--><font face="宋体"><b><font color="#FFFFFF" size="4">&nbsp; s[++top]=N%r; /</font><font color="#FF0000" size="4">*<font FACE="??ì?,SimSun" LANG="ZH-CN">余数入栈</font>  
      *</font><font color="#FFFFFF" size="4">/</font></b><!--mstheme--></font></td> 
  </tr>
12345

⌨️ 快捷键说明

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