Chapter 2. 线性表

概念

• 在顺序表中，逻辑上相邻的元素在物理位置上相邻。

• 广义表的概念

  • 广义表中存储的单个元素称为"原子"，而存储的广义表称为 "子表"。
  • 当广义表不是空表时，称第一个数据（原子或子表）为"表头"，剩下的数据构成的新广义表为"表尾"。
  • 广义表的长度：广义表中所包含的数据元素的个数。广义表中存储的每个原子算作一个数据元素，同样每个子表也只算作是一个数据元素。
  • 广义表的深度：广义表中嵌套的子表的最大深度。
  • head()操作：取表头。
  • tail()操作：取表尾（注意取到的是由表尾元素构成的长度为1的广义表）。

考点

• 头指针等于首结点（指针），头结点指向首结点。

• 设有两个长度为n的带头结点的单链表，结点类型相同，若以 h_1 为头结点指针的链表是非循环的，以 h_2 为头结点指针的链表是循环的，则对两个链表来说，删除开始结点的操作时间复杂度都是 O(1) 。

  对于 h_2 ，即使链表是循环的，对于开始结点，其结构也是 头结点 ---> 开始结点 ---> 后一结点 ，删除开始结点与终端节点无关。