📄 chapter3_2.htm
字号:
<html><!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>用指针实现队列</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
var previous = "chapter3_1.htm";
var next = "chapter4.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3>用指针实现队列<a name="imp-pointer"></a></h3>
<p>与<a href="../stack/chapter1.htm">栈</a>的情形相同，任何一种<a href="../list/chapter3.htm">实现表的方法</a>都可以用于实现队列。用指针实现队列得到的实际上是一个单链表。由于入队在队尾进行，所以用一个指针来指示队尾可以使入队操作不必从头到尾检查整个表，从而提高运算的效率。另外，指向队头的指针对于Front和Dequeue运算也是必要的。为了便于表示空队列，我们仍使用一个表头单元，将队头指针指向表头单元。当队头和队尾指针都指向表头单元时，表示队列为一个空队列。</p>
<p>用指针实现队列时，单元类型及队列类型可说明如下:</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5">
<tr>
<td width="100%">
<p style="margin-top: 5; margin-bottom: 5">type</p>
<p style="margin-top: 5; margin-bottom: 5">TPosition=^NodeType;</p>
<p style="margin-top: 5; margin-bottom: 5">NodeType=record</p>
<p style="margin-top: 5; margin-bottom: 5">
Element:ElementType;</p>
<p style="margin-top: 5; margin-bottom: 5">
next:TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">
end;</p>
<p style="margin-top: 5; margin-bottom: 5">QueueType=record</p>
<p style="margin-top: 5; margin-bottom: 5">
front,rear:TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">
end;
</td>
</tr>
</table>
</center>
</div>
<p>其中front为队头指针，rear为队尾指针。图8是用指针表示队列的示意图。</p>
<blockquote>
<p align="center"><img border="0" src="images/img1.gif" width="528" height="100"></p>
<p align="center">图8 用指针实现队列</p>
</blockquote>
<p>下面我们来讨论队列的5种基本运算。</p>
<div align="center">
<table border="0" width="90%" cellpadding="5" style="font-size: 10pt">
<center>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Front(Q)</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">这是一个函数，函数值返回队列Q的队头元素。用<a href="../list/chapter2.htm">一般的表运算</a>可将Front(Q)表示为Retrieve(First(Q),Q)。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">Function Front(var Q:QueueType):ElementType;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if Empty(Q) then
error('The queue is empty!')</p>
<p style="margin-top: 5; margin-bottom: 5">
else return(Q.front^.next^.Element);</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
</blockquote>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Enqueue(x,Q)</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">将元素x插入队列Q的队尾。此运算也常简称为将元素x<font face="楷体_GB2312">入队</font>。也可用<a href="../list/chapter2.htm">一般的表运算</a>将Enqueue(x,Q)表示为Insert(x,End(Q),Q)。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">Procedure Enqueue(x:ElementType;var
Q:QueueType);</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> new(Q.rear^.next);</p>
<p style="margin-top: 5; margin-bottom: 5"> Q.rear:=Q.rear^.next;</p>
<p style="margin-top: 5; margin-bottom: 5"> Q.rear^.Element:=x;</p>
<p style="margin-top: 5; margin-bottom: 5"> Q.rear^.next:=nil;</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">图9是该操作修改指针的示意图。</p>
<p align="center"><img border="0" src="images/img2.gif" width="479" height="114"></p>
<p align="center">图9 入队操作</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然为O(1)。</p>
</blockquote>
</td>
</tr>
</center>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<center>
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Dequeue(Q)</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">将Q的队头元素删除，简称为出队。用<a href="../list/chapter2.htm">一般的表运算</a>可将Dequeue(Q)表示为Delete(First(Q),Q)。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">Procedure Dequeue(var Q:QueueType);</p>
<p style="margin-top: 5; margin-bottom: 5">var</p>
<p style="margin-top: 5; margin-bottom: 5">p:TPosition;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if Empty(Q) then
Error('The queue is empty!')</p>
<p style="margin-top: 5; margin-bottom: 5">
else begin</p>
<p style="margin-top: 5; margin-bottom: 5">
p:=Q.front;</p>
<p style="margin-top: 5; margin-bottom: 5">
Q.front:=Q.front^.next;</p>
<p style="margin-top: 5; margin-bottom: 5">
dispose(p);</p>
<p style="margin-top: 5; margin-bottom: 5">
end;</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
</center>
<blockquote>
<p>图10是该操作修改指针的示意图。</p>
<center>
<p align="center"><img border="0" src="images/img3.gif" width="507" height="110"></p>
<p align="center">图10 出队操作</p>
</center>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
</blockquote>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> Empty(Q)</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">这是一个函数，若Q是一个空队列，则函数值为true，否则为false。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">Function Empty(var Q:QueueType):Boolean;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> return(Q.front=Q.rear);</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">当Q.front与Q.rear指向同一个结点单元时队列为空。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">显然为<i>O</i>(1)。</p>
</blockquote>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>函数</b> MakeNull(Q)</p>
<p style="margin-top: 5; margin-bottom: 5"><b>功能</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">使队列Q成为空队列。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>实现</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">Procedure MakeNull(var Q:QueueType);</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> Q.rear:=Q.front;</p>
<p style="margin-top: 5; margin-bottom: 5"> while Q.front<>nil
do</p>
<p style="margin-top: 5; margin-bottom: 5"> begin</p>
<p style="margin-top: 5; margin-bottom: 5"> Q.front:=Q.front^.next;</p>
<p style="margin-top: 5; margin-bottom: 5"> dispose(Q.rear);</p>
<p style="margin-top: 5; margin-bottom: 5"> Q.rear:=Q.front;</p>
<p style="margin-top: 5; margin-bottom: 5"> end;</p>
<p style="margin-top: 5; margin-bottom: 5"> new(Q.front);</p>
<p style="margin-top: 5; margin-bottom: 5"> Q.front^.next:=nil;</p>
<p style="margin-top: 5; margin-bottom: 5"> Q.rear:=Q.front; </p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>说明</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">首先将Q中所有的结点内存释放，然后重新生成一个结点作为标头单元，并使Q.rear:=Q.front。</p>
</blockquote>
<p style="margin-top: 5; margin-bottom: 5"><b>复杂性</b></p>
<blockquote>
<p style="margin-top: 5; margin-bottom: 5">若输入的队列Q中有n个结点，则复杂性为<i>O</i>(n)。</p>
</blockquote>
</td>
</tr>
</table>
</div>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -