📄 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="../list/chapter3_2.htm#def-chain">链表</a>作为栈的存储结构，即用指针来实现栈。用这种方式实现的栈也称为<b>链栈</b>，见图4。由于栈的插人和删除操作只在表头进行，因此用指针实现栈时没有必要像<a href="../list/chapter3_2.htm#def-chain">单链表</a>那样设置一个表头单元。</p>
<p align="center"><img border="0" src="images/img4.gif" width="408" height="69"></p>
<p align="center">图4 链栈</p>
<p>栈的类型说明与单链表类似。</p>
<div align="center">
<center>
<table border="0" width="90%" bgcolor="#E0E0E0" cellpadding="5">
<tr>
<td width="100%">type
<p> TNode=record</p>
<p> element:TElement;</p>
<p> next:^TNpde;</p>
<p> ent;</p>
<p> TStack=^TNode
</td>
</tr>
</table>
</center>
</div>
<p>链栈的基本操作实现如下：</p>
<div align="center">
<center>
<table border="1" width="90%" cellpadding="5" bordercolor="#FFFFFF">
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>procedure</b> MakeNull(Var
S:TStack);</p>
<p style="margin-top: 5; margin-bottom: 5">var p:TStack;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> p:=S;</p>
<p style="margin-top: 5; margin-bottom: 5"> while S<>nil
do</p>
<p style="margin-top: 5; margin-bottom: 5"> begin</p>
<p style="margin-top: 5; margin-bottom: 5"> S:=S^.next;</p>
<p style="margin-top: 5; margin-bottom: 5"> dispose(p);
{释放该单元占用的内存空间}</p>
<p style="margin-top: 5; margin-bottom: 5"> p:=S;</p>
<p style="margin-top: 5; margin-bottom: 5"> end;</p>
<p style="margin-top: 5; margin-bottom: 5">end;</p>
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>function</b> Empty(var
S:Stack):Boolean;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> return(S=nil);</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>finction</b> Top(var S:TStack):TElement;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if Empty(S) then Error('The
stack is empty.')</p>
<p style="margin-top: 5; margin-bottom: 5">
else return(S.element);</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>procedure</b> Pop(var
S:TStack);</p>
<p style="margin-top: 5; margin-bottom: 5">var p:TStack;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> if Empty(S) then Error('The
stack is empty.')</p>
<p style="margin-top: 5; margin-bottom: 5">
else begin</p>
<p style="margin-top: 5; margin-bottom: 5">
p:=S;</p>
<p style="margin-top: 5; margin-bottom: 5">
S:=S^.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;
</td>
</tr>
<tr>
<td width="100%" bgcolor="#E0E0E0">
<p style="margin-top: 5; margin-bottom: 5"><b>procedure</b> Push(x:TElement;var
S:TStack);</p>
<p style="margin-top: 5; margin-bottom: 5">var p:TStack;</p>
<p style="margin-top: 5; margin-bottom: 5">begin</p>
<p style="margin-top: 5; margin-bottom: 5"> new(p);</p>
<p style="margin-top: 5; margin-bottom: 5"> p^.element:=x;</p>
<p style="margin-top: 5; margin-bottom: 5"> p^.next:=S;</p>
<p style="margin-top: 5; margin-bottom: 5"> S:=p;</p>
<p style="margin-top: 5; margin-bottom: 5">end;
</td>
</tr>
</table>
</center>
</div>
<p>显然，以上操作中只用MakeNull的复杂性为<i>O</i>(n)，其余的复杂性为<i>O</i>(1)。</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -