数组:
稀疏矩阵:一个矩阵中记录的元素大量元素为零。考点:计算稀疏矩阵中某个元素的下标。
数据结构:
数据逻辑结构:
①线性数据机构
②非线性数据结构:树,图
线性表:线性结构的表现方式
①顺序表:连续的空间
②链表:单链表,双向链表,循环链表
顺序存储和链式存储对比:
队列:先进先出。
栈:先进后出。
循环队列:对空条件:head = tail,队满条件:(tail +1)%size = head
广义表:
例二:head(head(tail(LS1)))
表头是最外层的第一个元素,表尾是除了表头的其他所有元素。
树与二叉树:
节点的度:一个节点拥有的孩子节点数。
树的度:树中所有节点度数最高的节点的度。
叶子节点:没有孩子节点。
分支节点:有相应分支。
内部节点:既非叶子节点也非根节点。
完全二叉树:除了最下面的一层其他的都是满的,最下面一层左边排满。
二叉树遍历:
①层次遍历:从上到下从左到右遍历
②前序遍历:先访问根节点,在访问左子树和右子树节点。
③中序遍历:先访问左子树,在访问根节点再访问右子树节点。
④后序遍历:先访问左子树,右子树再访问根节点。
前中后序遍历的区别就是什么时候访问根节点。
反向构造二叉树:知道二叉树的遍历序列,推导出二叉树的结构。
数转二叉树:
查找二叉树:所有的左子树小于根节点,右子树大于根节点的二叉树。
最优二叉树:哈夫曼树
权:叶子节点代表的字符出现的频度。
带权路径长度:权值*路径
线索二叉树:
平衡二叉树:任意节点的左右节点的平衡度相差不超出1.
图:
邻接矩阵
邻接表:
图的遍历:
拓扑序列
图的最小生成树:一个图中能生成的最小边的树。一个有N个节点的树,最多有N-1个边。
算法:普卢姆算法,克鲁斯卡尔算法。
算法的特性:
算法复杂度:
时间复杂度:算法执行过程所需要的时间。
空间复杂度:执行过程中临时占用存储空间大小的度量。
查找:顺序查找,二分查找。
顺序查找法时间复杂度为O(n)。二分查找法时间复杂度为:O(log2n)
散列表查找:
处理机制:线性探测法,伪随机数法
排序:稳定排序和不稳定排序。稳定排序:相同数值经过排序后顺序不变。
排序方法:插入类排序,交换类排序,选择类排序,归并排序,基数排序。
直接插入排序:
直接选择排序: