数据结构-数组

极客-数据结构与算法之美(王争)-数组笔记

数据结构-数组

• 概念
  • 数组（Array）是一种线性表数据结构。它使用一组连续的内存空间，存储具有相同数据类型的数据。
• 特性
  • 1、随机访问
    • 数组使用连续的内存空间存储相同类型的数据，使数组可以支持基于下标的”随机访问“
  • 2、低效的“插入”和“删除”
    • a、插入操作
      • 假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。最好时间复杂度为O(1)，最坏时间复杂度O(n)，平均时间复杂度为O(n)。
    • b、删除操作
      • 跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度也为 O(n)。
  • 3、访问越界问题
    • int main(int argc, char* argv[]){ int i = 0; int arr[3] = {0}; for(; i<=3; i++){ arr[i] = 0; printf("hello world\n"); } return 0;} 因为，数组大小为 3，a[0]，a[1]，a[2]，而我们的代码因为书写错误，导致 for 循环的结束条件错写为了 i<=3 而非 i<3，所以当 i=3 时，数组 a[3] 访问越界。我们知道，在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。根据我们前面讲的数组寻址公式，a[3] 也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量 i 的内存地址，那么 a[3]=0 就相当于 i=0，所以就会导致代码无限循环。 数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。这种情况下，一般都会出现莫名其妙的逻辑错误，就像我们刚刚举的那个例子，debug 的难度非常的大。而且，很多计算机病毒也正是利用到了代码中的数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码的时候一定要警惕数组越界。 但并非所有的语言都像 C 一样，把数组越界检查的工作丢给程序员来做，像 Java 本身就会做越界检查，比如下面这几行 Java 代码，就会抛出 java.lang.ArrayIndexOutOfBoundsException。 int[] a = new int[3]; a[3] = 10;
• 0下标问题
  • 从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就表示偏移 k 个 type_size 的位置，所以计算 a[k] 的内存地址只需要用这个公式： a[k]_address = base_address + k * type_size 但是，如果数组从 1 开始计数，那我们计算数组元素 a[k] 的内存地址就会变为： a[k]_address = base_address + (k-1)*type_size 对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。 不过王争老师认为，上面解释得再多其实都算不上压倒性的证明，说数组起始编号非 0 开始不可。所以我觉得最主要的原因可能是历史原因。
• 非线性表
  • 概念
    • 与线性表相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
  • 常见类型
  • 特性
    • ① 集合结构。特点： 集合中任何两个数据元素之间都没有逻辑关系,组织形式松散. ② 树形结构。特点：树形结构具有分支、层次特性,其形态有点象自然界中的树. ③图状结构。特点：图状结构中的结点按逻辑关系互相缠绕,任何两个结点都可以邻接。
• 线性表
  • 概念
    • 线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。
  • 常见类型
  • 特性
    • 1．集合中必存在唯一的一个“第一元素”。 2．集合中必存在唯一的一个 “最后元素” 。 3．除最后一个元素之外，均有唯一的后继(后件)。 4．除第一个元素之外，均有唯一的前驱(前件)。
  • 优点
    • 线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
• 寻址公式
  • 我们知道，计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址： a[i]_address = base_address + i * data_type_size 其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里，数组中存储的是 int 类型数据，所以 data_type_size 就为 4 个字节。这个公式非常简单，我就不多做解释了。