数组与矩阵

数组

稀疏矩阵

• 记公式

• 面对考试使用代入法，将矩阵中的数值代入选项的公式中，排除掉错误答案
• 例如：A0.0应该存储在数组的M[1]中，所以将i=0，j=0代入，应该得到M[1]，以此类推，再代入其他值。

线性表

顺序表

• 采取一维数组的方式存取信息，开辟一堆连续的空间

链表

• 将一堆离散的空间连起来，这就是每个节点中指针域的作用。存储的是下一个元素的内存地址。

顺序存储与链式存储对比

队列

• 循环队列 由于队空队满的条件都一样，容易造成混淆，所以想出来一个办法，循环队列少存一个元素，就是尾指针指向的是头指针。

栈

• 后进先出
• 注意栈空栈满的条件

广义表

• 求广义表的长度和深度

树与二叉树

树的遍历

反向构造二叉树

树转二叉树

查找二叉树（排序二叉树）

最优二叉树（哈弗曼树）

• 常用于编码，无损压缩
• 带权路径长度wpl=叶结点的值 x（此节点到根节点的距离）
• wpl最小的时候，就是最优二叉树
• 如何构造哈弗曼树

线索二叉树

• 由于在二叉树中有很多结点属于空闲状态，有很多指针没有利用起来，
• 左子树的指针指向（前/中/后）序遍历的前驱结点
• 右子树的指针指向（前/中/后）序遍历的后驱结点

平衡二叉树

• 在之前的排序二叉树中发现，同样的序列，排序二叉树可能有多颗，形态不一样，这也是提出平衡二叉树的原因，一颗二叉树越平衡，他的查找效率越高

图

图的概念

图的存储–邻接矩阵

图的存储–邻接表

图的遍历

拓补排序

• 实质是用一个序列来表达一个图当中，哪些事件可以先执行，哪些事件可以后执行。
  拓补排序可能产生多个序列，考试中常遇到哪些说明下面哪些不是拓补排序的序列。
  

图的最小生成树

• 将图中，很多的线，边，去掉，只留下若干条边，然后连起来
• 普里姆算法 从一个红点出发，选择他可以达到的权最小的那一个点，将那个点也归为红点，一步一步扩展，需要注意的是，不能形成一个环。

• 克鲁斯卡尔算法
  看需要选几条边，比如说五条边，那么就从权值最小的中选区这些边，达到五条，就不再选了，将这五条变连接起来，也要注意的是，不能构成一个环。

算法的特性

时空复杂度

散列表

排序算法

• 各种排序算法:十大排序算法