前言

数组与链表都属于数据结构中线性表结构。同一线性表中的元素必定具有相同特性，且相邻数据元素之间存在着一对一关系（前驱，后继）。

我认为存在线性表这种数据结构的意义是，它可以以一定的顺序进行遍历，方便迭代所有的数据，且在查找的时候可以轻松的利用邻居元素一对一的关系，获取到某个数据。

动态查找表：不仅仅是顺序查找，动态查找表的特点是表结构本身在查找过程中动态生成,即对给定的关键字key，若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。

数组

C中的数组是一种将标量类型数据聚集成更大数据类型的方式。

基本规则

对于数据类型T和整数N，声明

1
T A[N]

有两个效果。

  • 首先，在存储器中分配了L*N字节的连续区域（L是数据类型T的大小），我们用a来表示起始位置。
  • 其次，引入标识符A，作为指向数组开头的指针，指针的值是a。数组元素i的地址为a+L*i。

动态分配的数组

在许多应用程序中，我们需要代码能够对动态分配的任意大小的数组进行操作。

1
2
3
4
5
typedef int * var_matrix;
var matrix new_var_matrix(int n)
{
    return (var_matrix)calloc(sizeof(int), n * n)
}

注意：在C中，堆（一个可以用来存放数据结构的存储池）中的存储分配是用的库函数malloc或calloc。它们要求程度用free函数来释放已分配的空间。在Java中是由gc的进程自动完成的。

结构

C中的struct声明创建一个结构数据类型，将可能不同类型的对象聚合到一个对象中。

声明

1
2
3
4
5
6
struct rec {
    int i;
    int j;
    int a[3];
    int *p;
};

这个结构包含四个域————两个整数、一个数组和一个指针。

1
2
3
4
0    4    8                20
-----------------------------------
|  i |  j | a[0] a[1] a[2] |  p   |
-----------------------------------

指向结构的指针就是结构第一个字节的地址，为了访问结构中的域，编译器产生的代码要将结构的地址加上适当的偏移。

链表

链表是由一系列不必在内存中相连的结构组成，每一个结构包含表元素和指向包含该元素后继的结构的指针。

链表在许多语言的内存管理、垃圾回收策略中有着广泛的应用，如Python的内存管理、标记-清除垃圾回收策略、分代收集策略。

区别

分配内存：

  • 数组：静态数组内存的分配是由栈完成的，它的内存的分配和释放都是有计算机自己处理。
  • 链表：链表的内存的分配是由堆完成的，它的内存的分配和释放都是有程序员手动处理。

内存中的状态：

  • 数组：在内存中是一段连续的区域。
  • 链表：在内存中是非连续的。

大小：

  • 数组：固定。
  • 链表：不固定。

操作：

  • 数组：查找O(1)，增加、删除O(n)。
  • 链表：查找O(n)，增加、删除O(1)。

跳跃链表

https://lfkdsk.github.io/2017/09/11/quick-learn-skip-list/

参考

《数据结构——C语言版》严蔚敏
《数据机构与算法分析——C语言描述》韦斯
《深入理解计算机系统》