表
常见的表的操作。
print_list和make_empty；find返回关键字首次出现的位置；insert和delete从表的某个位置进行插入或者删除；find_k_th返回第$k$个位置上的元素。
表的两种实现方式
- 数组实现的表
- 链表
数组实现的表
对表的操作可以通过使用数组实现。
- 需要连续的存储空间，数组的大小通常要比链表所需要的大一些
- 获得第$k$个位置上的元素的时间复杂度是$O(1)$
- 遍历和查找的时间复杂度是线性的$O(n)$。
- 插入和删除的平均时间复杂度是$O(n)$，平均情况下每次插入和删除需要移动一半的元素。
- 通过$n$次插入创建一个表需要$O(n^2 )$的时间复杂度。
链表
- 不连续存储，减少插入和删除的时间复杂度
- 链表由一系列不必在内存中连续存储的结构体组成。每一个结构含有表元素和指向表元素后继元素的指针，叫做
next指针。最后一个结构的next指针指向NULL，它的取值是$0$。 - 遍历和查找的时间复杂度是$O(n)$
- 获得第$k$个位置的元素的时间复杂度也是$O(n)$
- 插入和删除的时候不需要进行移动，只需要在插入或者删除节点进行操作。
表头节点（哑结点）
为了使得在表头处节点的操作和在其他节点的操作一样，可以通过添加一个哑结点实现。在删除表的第一个元素的时候，就可以使用哑结点帮助操作。