4.2 单向链表

如下图所示,链表被画成结点顺序的序列,把其中的链表示为箭头。指向表中首结点的指针名就是链表的名字。链表有以下特点:

  1. 结点并不按地址顺序存储
  2. 结点地址在每次运行时是可变的

4-1

链表的一般画法

如下图所示,在 catsat 中插入 mat,所需的操作是:

  1. 申请当前未用的新结点,令它的地址是 paddr
  2. 把新结点的值域设为 mat
  3. paddr 的链域设置为包含 cat 结点的链域的地址
  4. 把包含结点 cat 的链域设置为 paddr

4-2

在 cat 后插入 mat

当需要从表中删除 mat,先找到 mat 的前驱 cat,并且把其链域设为 mat 的链域。

4-3

从表中删除 mat

PS:

在 C 语言中,如果 e 是一个指向域名为 name 的结构的指针,那么 e->name 就是表达式 (*e).name 的简写形式。运算符 -> 称为 「结构成员 structure member」 选择运算符。

  • 「动态链栈」与「动态链队列」

如下图所示,链栈可以很容易地从栈顶插入或删除一个结点。

4-4

链栈

如下图所示,链队列可以很容易地在队尾插入结点,在队列前端删除结点。

4-5

链队列

results matching ""

    No results matching ""