📄 chapter1.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">
previous = "index.htm";
next = "chapter2.htm";
topic="表 LIST";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content">
<!-- #BeginEditable "MainContent" -->
<h2>表的性质<a name="chr"></a></h2>
<p>从表的定义不难看出表具有以下数学性质：除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。</p>
<p class="noindent"><b>注意：表和数组的区别<a name="dif"></a></b></p>
<p>从概念上来看，表是一种抽象数据类型；数组是一种具体的数据结构。关于<a href="../../ADT/chapter4.htm">抽象数据类型和数据结构的区别</a>，请参见<a href="../../ADT/index.htm">算法表达中的抽象机制</a>。</p>
<p>从数学性质上来看，表是一个二元关系R，<x,y>∈R 当且仅当x是y的前驱；如果将该二元关系用关系图（将每一个元素用一个点来表示，若x与y有关系则从x到y连一条有向线段）来表示，则得到的是一条单链a<sub>1</sub>→a<sub>2</sub>→…→a<sub>n
</sub>，因此表也可以看成是特殊的图或特殊的树（每个节点有且仅有一个子节点）；而数组是从1..n的自然数集合到数组元素集合的一一映射，其中n是数组的长度，1..n中每一个自然数唯一地对应着一个数组元素，反之亦然。所以数组可以用来实现映射。</p>
<p>从物理性质来看，数组中相邻的元素是连续地存储在内存中的，或者对于程序员来说可以认为它们是连续地存储在内存中的（比如动态增长的数组实际上并不存储在连续的内存中，但程序员可以认为它存储在连续的内存中），数组的存取对程序员来说是透明的；表只是一个抽象的数学结构，并不具有具体的物理形式，表需要通过其它有具体物理形式的数据结构来实现。在表的具体实现中，表中相邻的元素<strong>不一定</strong>存储在连续的内存空间中，除非表是用数组来实现的。对于数组，可以利用其下标在一个操作内随机存取任意位置上的元素；对于表，只能根据当前元素找到其前驱或后继，因此要存取第i个位置上的元素，一般不能在一个操作内实现，除非表是用数组实现的。在实现表时需要提供足够的信息以便能够通过表中元素的位置p来存取表中的元素。表中元素的位置p是指示表中元素位置的信息，通过对p进行处理（可能是从事某种函数运算计算出该元素在内存中的位置，也可能从表头开始，依次寻找当前元素的后继，重复i次找到第i个位置的元素）可以得到表中元素在内存中的物理位置，因此<strong>不能简单地将位置p理解为类似数组下标的自然数</strong>，实际上p可以是各种类型的变量，在数学上可将p定义为一个<dfn>偏序集</dfn>上的变量。在具体实现表及其运算时，应区分p与p所表示的位置，以及该位置上的元素三者之间的不同含义。</p>
<!-- #EndEditable -->
</div>
<script src='../../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate --></html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -