空间复杂度：
定义：
一般情况下，一个程序在机器上执行时，除了需要寄存器本身所用的指令，常数，变量和输入数据外，还需要一些对数据进行操作的辅助空间。
辅助空间与算法的功能无关：
- 不被称为辅助空间：
- 作为输入参数的空间
- 作为输出参数的空间
- 被称为辅助空间：
- 如果流程需要开辟空间才能让流程继续下去，该空间被称为辅助空间。
链表：
对首元结点，头结点，头指针的声明：
- 首元结点：链表中存储第一个数据的结点。
- 头节点：在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。
- 头指针：指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。
堆结构：
- 堆结构就是用数组实现的完全二叉树结构。
- 完全二叉树中如果每棵子树的最大值都是在堆顶就是大根堆。
- 完全二叉树中如果每棵子树的最小值都是在堆顶就是小根堆。
核心操作：
- 插入元素（上浮调整）
- 步骤：
- 将新元素插入数组末尾。
- 向上调整：若新元素大于父节点（最大堆），与其交换，知道满足堆性质。
- 时间复杂度：O(log n)
- 删除堆顶元素(下沉调整)
- 步骤：
- 移除堆顶元素，将数组末尾元素移至堆顶。
- 向下调整：将当前节点与较大子节点（最大堆）比较，若小于则交换，知道满足堆性质。
- 时间复杂度：O(log n)
- 构建堆
-
自底向上法：从最后一个非叶子节点（下标为n/2-1）开始，向前遍历并对每个节点执行下沉操作。
-
时间复杂度：O(n)
哈希表
-
散列查找法：通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较，因此，散列查找法又叫杂凑法或散列法。
-
散列函数和散列地址：在记录的存储位置p和其关键字key之间建立一个确定的对应关系H，使p=H（key），称这个对应关系H为散列函数，P为散列函数地址。
-
哈希表（散列表）：一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。
-
冲突和同义词：对不同的关键字可能得到同一散列地址，即key1不等于key2，而H（key1） 等于 H（key2），这种现象称为冲突，具有相同函数值的关键字对该散列函数来说称作同义词，key1，key2互称为同义词。
使用链表可以解决哈希冲突。
图：
图的存储结构 -- 邻接表（链式存储）
邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点vi建立一个单链表，把与vi相邻接的顶点放在这个链表中。邻接表中每个单链表的第一个结点存放有关顶点的信息，把这一结点看成链表的表头，其余结点存放有关边的信息，这样的邻接表便由两部分组成： 表头结点和边表。
- 表头结点：由所有表头结点以顺序结构的形式存储，以便可以随机访问任一顶点的边链表。表头结点包括数据域和链域两部分。链域指向与顶点vi邻接的第一个邻接点。
- 边表：由表示图中顶点间关系的2n个边链表组成。边链表中边结点包括邻接点域，数据域，链域，邻接点域指示与顶点vi邻接的点在图中的位置；数据域存储与边相关的信息；链域指示与顶点vi邻接的下一条边的结点。
前缀编码
任何一个字符的编码都不是同一字符集中另一字符编码的前缀；哈夫曼编码是最优前缀编码。
连通图
如果对于无向图G中的任意两个属于顶点集V的顶点V1,V2;V1,V2都是连通的，则称G是连通图。
重（双）连通图和关节点
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。
若连通图中的某个顶点和其相关联的边被删除之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。
没有关节点的连通图为双连通图
广义表：
定义：
广义表是线性表的推广，也成为列表；广义表的定义是一个递归的定义。
长度与深度
广义表的长度定义为最外层包含元素的个数 广义表的深度定义为所含括号的重（层）数；广义表的深度=MAX{子表的深度}+1
取表头表尾
取表头：取出的表头为非空广义表的第一个元素，它可以是一个单元素，也可以是一个子表；
取表尾：取出的表尾为除去表头之外，由其余元素构成的表。即表尾一定是一个广义表。
京公网安备 11010502036488号