线性表章节。

线性表的定义和操作

线性表的定义

线性表是具有相同数据类型的 n 个数据元素的有限序列。

线性表是逻辑结构，表示了元素之间一对一的相邻关系。而顺序表（顺序存取表）和链表（链式存储表）是指存储结构。

  • 线性表具有先后顺序。
  • 线性表每个元素具有相同大小的存储空间。

线性表的操作

有以下操作：

  • 初始化分配内存空间。
  • 求表长。
  • 按值查找。
  • 读取某个元素。
  • 插入操作。
  • 删除操作
  • 顺序输出所有元素。
  • 判断元素个数是否为 0。
  • 销毁线性表。

线性表的顺序实现

概念

顺序表是指，逻辑上相邻的数据元素在物理地址上也相邻。

结论就是：

随机存取方便，插入删除困难，顺序表是一种随机存取的数据结构。

例题遇到的概念

没什么好说的，连续多次删除元素的话不一定要重复 k 次的移动，可以一次移动完。具体算法思路是这样的：

  • 定义一个下表 index=0 和循环变量 i=0。
  • 循环遍历：
  • 如果该元素要被删除，则不作任何操作。
  • 如果该元素不会被删除，把它存入下标为 index 的数组，并使得 index++。
  • 结束循环
  • 最后让长度 = index 即可。

或者用下面的思路：

  • 记录要删除元素个数，维护 k。
  • 循环遍历：
  • 如果该元素要被删除，则 k++。
  • 如果该元素不被删除，则存入下标为 i-k 的数组当中。
  • 结束循环
  • 最后让长度 -= k。

循环左移或者循环右移的思路：

主要是空间复杂度怎么优秀起来，其实可以直接把数组 reverse 一下。然后选取一个点 k，让 （0，k） reverse，（k+1，n-1） reverse，这样相当于循环右移了 k+1 位。

让 n=5，k=0 试试看。

初始

1
0 1 2 3 4

全部 reverse 一下。

1
4 3 2 1 0

让 （0，0） reverse，（1，4）reverse。

1
4 0 1 2 3

就是循环右移了 k+1 也就是 1 位。

k=1的时候，在

1
4 3 2 1 0

的情况下，让（0，1）reverse，让（2，4） reverse，就变成了：

1
3 4 0 1 2

相当于是右移了 2 位。

线性表的链式实现

概念

没有难的地方，把头节点想象为一个不带值的节点即可，循环链表的最后一个 next 域要指向头节点。

如果不带头节点，那么那节点直接是指向第一个元素的。

举个例子就是：

有一个头指针 LinkList head，如果带头节点，那么 head->next->value 是第一个节点的值。如果不带头节点，那么 head->value 就是第一个节点的值。

  • 静态链表：参考链式前向星，链式前向星就是很经典的静态链表。

然后就是，对于单链表来说，删除节点需要知道该节点的前一个地址。

其它就没什么了，都很 easy。