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

📄 ds3.3.2.htm

📁 这是清华大学所用的数据结构的电子版教材
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<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 color="#FFFFFF" size="6"><b><font face="oúì?,SimHei" lang="ZH-CN">3.3.2</font> 
<font face="??ì?,SimSun" lang="ZH-CN">队列的存储实现及运算实现</font></b></font></p>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp; 
与线性表、栈类似，队列也有顺序存储和链式存储两种存储方法。</b></font></p>
<font SIZE="3">
<p ALIGN="JUSTIFY"></font><font FACE="oúì?,SimHei" LANG="ZH-CN"><font size="5" color="#FFFFFF"><b>1、顺序队</b></font></p>
</font>
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp; 
顺序存储的队称为顺序队。因为队的队头和队尾都是活动的，因此，除了队列的数据区外还有队头、队尾两个指针。</b></font></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>顺序队的类型定义如下：</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; 
define MAXSIZE 1024 /*<font FACE="??ì?,SimSun" LANG="ZH-CN">队列的最大容量</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; 
typedef struct</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; 
{datatype data[MAXSIZE]; /*<font FACE="??ì?,SimSun" LANG="ZH-CN">队员的存储空间</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp;&nbsp; 
int rear,front; /*<font FACE="??ì?,SimSun" LANG="ZH-CN">队头队尾指针</font>*/</b></font></p>
<p ALIGN="justify" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; 
}SeQueue;</b></font></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>定义一个指向队的指针变量：</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; SeQueue *sq;</b></font></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>申请一个顺序队的存储空间：</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; sq=malloc(sizeof(SeQueue));</b></font></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>队列的数据区为：</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; 
sq-&gt;data[0]---sq-&gt;data[MAXSIZE -1]</b></font></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">队头指针：</font>sq-&gt;front</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">队尾指针：</font>sq-&gt;rear</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p ALIGN="JUSTIFY"><b><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF">&nbsp; 
设队头指针指向</font><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FF00FF">队头元素前面一个位置</font><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF">，队尾指针</font><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FF00FF">指向队尾元素</font><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF">（这样的设置是为了某些运算的方便，并不是唯一的方法）。</font></b></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">置空队则为：</font>sq-&gt;front=sq-&gt;rear=-1;</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">在不考虑溢出的情况下，入队操作队尾指针加</font>1<font FACE="??ì?,SimSun" LANG="ZH-CN">，指向新位置后，元素入队。</font></b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp;&nbsp; 
操作如下：</b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; sq-&gt;rear++;</b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; sq-&gt;data[sq-&gt;rear]=x; 
/*<font FACE="??ì?,SimSun" LANG="ZH-CN">原队头元素送</font>x<font FACE="??ì?,SimSun" LANG="ZH-CN">中</font>*/</b></font></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">在不考虑队空的情况下，出队操作队头指针加</font>1<font FACE="??ì?,SimSun" LANG="ZH-CN">，表明队头元素出队。</font></b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p ALIGN="JUSTIFY"><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF"><b>&nbsp;&nbsp; 
操作如下：</b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; 
sq-&gt;front++;</b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>&nbsp;&nbsp; x=sq-&gt;data[sq-&gt;front];</b></font></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">队中元素的个数：</font>m=(sq-&gt;rear)-(q-&gt;front);</b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="expbul1a.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体">
      <p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">队满时：</font>m= 
      MAXSIZE<font FACE="??ì?,SimSun" LANG="ZH-CN">；</font> <font FACE="??ì?,SimSun" LANG="ZH-CN">队空时：</font>m=0<font FACE="??ì?,SimSun" LANG="ZH-CN">。</font></b></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">&nbsp; 
按照上述思想建立的空队及入队出队示意图如图</font>3.12<font FACE="??ì?,SimSun" LANG="ZH-CN">所示，设</font>MAXSIZE=10<font FACE="??ì?,SimSun" LANG="ZH-CN">。</font></b></font></p>
<font SIZE="3">
<p ALIGN="center" style="margin-bottom: 0"><img SRC="Image2.gif" WIDTH="425" HEIGHT="281"></p>
<p ALIGN="center" style="margin-top: 0"><img border="0" src="ds3.3.2.gif" width="413" height="84"></p>
<p></font><b><font size="5" color="#FFFFFF"><font FACE="??ì?,SimSun" LANG="ZH-CN">&nbsp;&nbsp; 
从图中可以看到，随着入队出队的进行，会使整个队列整体向后移动，这样就出现了图</font>3.12(d)<font FACE="??ì?,SimSun" LANG="ZH-CN">中的现象：队尾指针已经移到了最后</font>,<font FACE="??ì?,SimSun" LANG="ZH-CN">再有元素入队就会出现溢出，而事实上此时队中并未真的“满员</font>”<font FACE="??ì?,SimSun" LANG="ZH-CN">，这种现象为“假溢出”，这是由于“队尾入队头出”这种受限制</font></font><font FACE="??ì?,SimSun" LANG="ZH-CN" size="5" color="#FFFFFF">的操作所造成。解决假溢出的方法之一是将队列的数据区data[0..MAXSIZE-1]看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队”，“循环队”的示意图如图3.13所示。</font></b></p>
<p align="center" style="margin-bottom: 0"><font SIZE="3"><img SRC="Image3.gif" width="243" height="204"></font></p>
<p align="center" style="margin-top: 0"><img border="0" src="ds3.3.3.gif" width="252" height="32"></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">&nbsp; 
因为是头尾相接的循环结构，入队时的队尾指针加</font>1<font FACE="??ì?,SimSun" LANG="ZH-CN">操作修改为：</font></b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b>&nbsp; 
sq-&gt;rear=(sq-&gt;rear+1) % MAXSIZE;</b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><font FACE="??ì?,SimSun" LANG="ZH-CN">出队时的队头指针加</font>1<font FACE="??ì?,SimSun" LANG="ZH-CN">操作修改为：</font></b></font></p>
<p><font size="5" color="#FFFFFF"><b>&nbsp; sq-&gt;front=(sq-&gt;front+1) % 
MAXSIZE;</b></font></p>
12

⌨️ 快捷键说明

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