notes

This site uses Just the Docs, a documentation theme for Jekyll.

数组

数组是可以存储多个相同元素的结构，在内存中分配的区域是连续的，大多数数据结构使用数组来实现它们的算法。

元素：数组中存储的每个项目都称为元素
索引：数组中元素的每个位置都有一个数字索引，每个元素通过索引进行访问，索引从 0 开始。

优点：

1、按照索引查询元素速度快
2、按照索引遍历数组方便

缺点：

1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，因为要移动其他的元素

适用场景：

频繁查询，对存储空间要求不大，很少增加和删除的情况

数组和广义表可看成是一种特殊的线性表，其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在 O(1) 时间读 / 写任何元素。

二维数组，多维数组，广义表、树、图都属于非线性结构

数组

数组的顺序存储：行优先顺序；列优先顺序。数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。

关联数组 (Associative Array)，又称映射（Map）、字典（ Dictionary）是一个抽象的数据结构，它包含着类似于(键，值) 的有序对。 不是线性表。

矩阵的压缩：

  1. 对称矩阵、三角矩阵：直接存储矩阵的上三角或者下三角元素。注意区分 i>=j 和 i

广义表

广义表（Lists，又称列表）是线性表的推广。广义表是 n(n≥0) 个元素 a1,a2,a3,…,an 的有限序列，其中 ai 或者是原子项，或者是一个广义表。若广义表 LS（n>=1) 非空，则 a1 是 LS 的表头，其余元素组成的表 (a2,…an) 称为 LS 的表尾。广义表的元素可以是广义表，也可以是原子，广义表的元素也可以为空。表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值。所以表尾不可以是单个元素值。

例子：

  1. A=（）——A 是一个空表，其长度为零。
  2. B=（e）——表 B 只有一个原子 e，B 的长度为 1。
  3. C=（a,(b,c,d))——表 C 的长度为 2，两个元素分别为原子 a 和子表 (b,c,d)。
  4. D=（A，B，C）——表 D 的长度为 3，三个元素都是广义 表。显然，将子表的值代入后，则有 D=((),(e),(a,(b,c,d)))。
  5. E=（a,E）——这是一个递归的表，它的长度为 2，E 相当于一个无限的广义表 E=(a,(a,(a,(a,…)))).

三个结论：

  1. 广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示
  2. 广义表可为其它表所共享。例如在上述例 4 中，广义表 A，B，C 为 D 的子表，则在 D 中可以不必列出子表的值，而是通过子表的名称来引用。
  3. 广义表的递归性

考点：

  1. 广义表是 0 个或多个单因素或子表组成的有限序列，广义表可以是自身的子表，广义表的长度 n>=0，所以可以为空表。广义表的同级元素 (直属于同一个表中的各元素) 具有线性关系
  2. 广义表的表头为空，并不代表该广义表为空表。广义表 () 和(())不同。前者是长度为 0 的空表，对其不能做求表头和表尾的运算；而后者是长度为 l 的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()
  3. 已知广义表 LS＝((a,b,c),(d,e,f)), 运用 head 和 tail 函数取出 LS 中原子 e 的运算是 head(tail(head(tail(LS)))。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。也就是说，广义表的 head 操作，取出的元素是什么，那么结果就是什么。但是 tail 操作取出的元素外必须加一个表——“（）“。tail(LS)＝((d,e,f))；head(tail(LS))=(d,e,f)；tail(head(tail(LS)))=(e,f)；head(tail(head(tail(LS))))=e。
  4. 二维以上的数组其实是一种特殊的广义表
  5. 在（非空）广义表中：1、表头 head 可以是原子或者一个表 2、表尾 tail 一定是一个表 3. 广义表难以用顺序存储结构 4. 广义表可以是一个多层次的结构