查看“︁链式结构”︁的源代码

[[分类:存储结构]]
[[分类:寻址方式]]
{{InfoBox
|name=链式结构
|eng_name=linked data structure
|aliases=链接存储结构
}}
{{InfoBox
|name=结点
|eng_name=node
|aliases=节点
}}
{{InfoBox
|name=元素
|eng_name=element
}}
{{InfoBox
|name=链接
|eng_name=link
|aliases=connector,引用,reference,指针,pointer
}}
{{InfoBox
|name=空
|eng_name=empty
}}
{{InfoBox
|name=空链接
|eng_name=null link
|aliases=空,null
}}
{{InfoBox
|name=解引用
|eng_name=dereference
|aliases=间接寻址,间址
}}
'''链式存储结构'''/'''链接存储结构'''('''linked data structure''')是一类最基础的存储结构。有时也用代表数据结构[[链表]]代指，但是链式结构范围比链表范围宽很多。有时仅链式存储结构的数据结构也被会称为某某链表。

链式存储结构容纳一系列的'''结点'''，每个结点中有若干数据记录。除外，每个结点中还会含有至少一个'''链接'''，且'''指向'''另一个结点或'''空'''，在不同的语言中可能使用[[引用（数据类型）|引用]]或[[指针]]等[[引用类型]]表达。

链式存储结构中，寻址需要通过某个已知结点开始逐个寻找其指向的结点，因此有时被称为'''链式寻址'''或'''链表寻址'''。

== 定义 ==

=== 存储结构 ===

'''链式'''存储结构/'''链接'''存储结构('''linked''' data structure)是一种存储结构。链式结构包括多个'''结点'''('''node''')，其内存空间关系不做要求；结点中含有数据记录，称为'''元素'''('''element''')。结点中除元素外，还有称为'''链接'''('''link'''/'''connector''')的数据，链接可以'''引用'''('''refer''' to/'''reference''')/'''指向'''('''point''' to)结点自身或另一个结点。

链接存储结构中的链接是一个抽象类型，其可以指向某个结点，通常只要求其是一个可空、等值可比较的引用类型：
# 判断空值(emptiness)：是[[可空类型]]的同名操作。一个链接的数据，可以指向某个结点，也可以不指向任何结点（注：指向不是结点的数据不符合要求，不属于合理状态），分别称这个链接是'''非空'''的('''non-empty''')和'''空'''的('''empty''')。一个空的链接(empty link)也可以称为一个'''空链接'''('''null link''')并简称为'''空'''('''null'''<ref>英语 {{IPA|[nʌɫ]}} ，来自拉丁语 {{Lat|nūllus|[ˈnuːlːʲʊs]}} 。但是有人会根据德语 {{Deu|Null|[nʊɫ]}} 读，也偶尔见到有人训读成 nil {{IPA|[nɪɫ]}} 或 none {{IPA|[nʌn]}} 。</ref>)<ref>严格地说，这里 empty 是形容词 null 是名词，所以英语两个词不可替换。尽管 null 有形容词用法，但是计算机术语上只使用名词，非正式场合可能作动词相当于 nullify 、 invalidate 或 crack 。不过因为中文都翻译成空，这句话看起来会有点奇怪。</ref>，记作 <code>NULL</code> 或 <code>^</code> 。
# 判断两个链接是否相等(equality)：两个链接的数据指向同一个结点，或者同时为空，称两个链接'''相等'''('''equal''')，否则称为不相等。通常用等号或不等号表达。
# '''解引用'''/'''间址'''('''deference''')：是[[引用类型]]的同名操作。若链接非空，可以通过这一操作得到其指向的结点。

=== 寻址方式 ===

'''链式寻址'''/'''链接寻址'''/'''链表寻址'''中，数据结构由结点构成，结点间以链接相连接。若已知结点 <math>b</math> ，函数 <math>f(\cdot)</math> 给出从某结点确定下一结点的链接，函数 <math>d(\cdot)</math> 代表对链接解引用，则对任意元素 <math>e</math> ，其所在结点 <math>n_e</math> 与任意结点 <math>n</math> 间的函数关系 <math>n_e(n)</math> 满足递归关系：

<math>
n_e(n) = \begin{cases}
n &, n = n_e \\
n_e(d(f(n))) &, n \neq n_e \\
\end{cases}
</math>

且展开有 <math>n_e = d(f(d(f(\cdots d(f( n )) \cdots ))))</math> 。

由于在寻找 <math>n_e</math> 时是不知道 <math>n_e</math> ，无法比较 <math>n_e = n</math> 的，通常用其他条件结束递归，如位置计数或者元素的某种特征。


{{数据结构}}