📄 chapter3_4.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_3.htm";
var next = "chapter3_5.htm";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h3 align="left">循环链表</h3>
<p align="left" style="text-align:left;text-autospace:none">
我们在用指针实现表时，表中最后一个元素所在单元的指针域(next)为空指针nil。如果将这个空指针改为指向表头单元的指针就使整个链表形成一个环。这种首尾相接的链表称为<b>循环链表</b>。在循环链表中，从任意一个单元出发可以找到表中其他单元。图6所示的是一个单链的循环链表或简称为单循环链表。</p>
<div align="center">
<center>
<table border="0">
<tr>
<td width="50%"><img border="0" src="images/img9.gif" width="465" height="92"></td>
<td width="50%"><img border="0" src="images/img10.gif" width="155" height="71"></td>
</tr>
<tr>
<td width="50%">
<p align="center">(a)非空表
</td>
<td width="50%">
<p align="center">(b)空表
</td>
</tr>
</table>
</center>
</div>
<blockquote>
<p align="center" style="text-autospace: none">图6单循环链表</p>
</blockquote>
<p align="left" style="text-align:left;text-autospace:none">
在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。它们仅在循环终止条件上有所不同:前者是p或p^.next指向表头单元；后者是p或p^.next指向空(nil)。</p>
<p align="left" style="text-align:left;
text-autospace:none"> 在单链表中我们用指向表头单元的指针表示一个表L，这样就可以在<i>O</i>(1)时间内找到表L中的第一个元素。然而要找到表L中最后一个元素就要花<u><i>O</i></u>(n)时间遍历整个链表。在单循环链表中，我们也可以用指向表头单元的指针表示一个表L。但是，如果我们用指向表尾的指针表示一个表L时，我们就可以在<i>O</i>(1)时间内找到表上中最后一个元素。同时通过表尾单元中指向表头单元的指针，我们也可以在<i>O</i>(1)时间内找到表L中的第一个元素。在许多情况下，用这种表示方法可以简化一些关于表的运算。例如要将图7(a)中两个表L<sub>1</sub>和L<sub>2</sub>合并成一个表时，只要修改两个指针值即可，运算时间为<i>O</i>(1)。合并后的表如图7(b)所示。</p>
<blockquote>
<p align="center" style="text-autospace: none"><img border="0" src="images/img11.gif" width="380" height="289"></p>
<p align="center" style="text-autospace: none">图7 两个单循环链表的合并</p>
</blockquote>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -