|
|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 线性表 >
|
|
考试要求：熟悉
相关知识点：3个
|
|
|
|
|
线性表的顺序存储结构使得线性表的存储位置可以用一个简单、直观的公式来表示，但是在插入或删除操作的时候，需要移动大量的元素，十分不便。链式存储结构弥补了它的这个缺点。链式存储结构的特点是可以用一组任意的存储单元来存储线性表中的元素的存储结构，这些存储单元可以连续，也可以不连续。所以，为了表示数据元素ai与它的直接后继元素ai+1的逻辑关系，除了元素ai的基本信息之外，还存储了一个可以指明它的直接后继元素ai+1的存储位置的内容。它们共同组成ai的存储映像，称为结点（node）。存储元素ai的信息，被称为数据域，存储直接后继元素的存储位置的域，被称为指针域。n个结点（ai（1≤i≤n））组成一个链表，也就是线性表（a1，a2，…, an）的链式存储结构。其结构示意图如下图所示。
|
|
|
|
|
|
|
|
上图分别画出了链表的三种不同链式存储结构。若一个指针域的值为空，则在图形中通常用符号“Λ”表示，由于线性表中的第一个元素没有前驱元素，最后一个元素没有后继元素，所以用“Λ”表示。
|
|
|
|
循环链表是另一种形式的链式存储结构，它的特点是表中的最后一个结点的指针域指向头结点，整个链表形成一个环状结构，从表中任意一个结点出发都可以到达其他节点。操作与线性链表基本一致。
|
|
|
|
|
|
|
|
| |
|
|
|
