考研/期末数据结构知识点整理
1.绪论
不能丢分的知识，除了复杂度全是记的
1)基本概念和术语
●数据元素：数据元素是数据的基本单位
●数据项：构成数据元素不可分割的最小单位
●总结：数据项——数据元素——数据对象(N个)——数据
●数据结构：相互之间存在的一种或多种特定关系的数据元素的集合
2)数据结构三要素
●数据的逻辑结构
●特点：独立于计算机，不依赖存储结构，但是存储结构依赖逻辑结构
●线性结构
●非线性结构
●数据的存储结构
●特点：计算机中数据的物理表示（映像）
●顺序存储
●链式存储
●索引存储
●散列存储
3)算法
●特征
●有穷性
●确定性
●可行性
●输入
●输出
●好的算法
●正确性
●可读性
●健壮性
●效率和低存储量需求
4)复杂度分析
●O(1) < O(log_{2}n) < O(n) < O(nlog_{2}n) < O(n^{2}) < O(n^{3}) < O(2^{n}) <
O(n!) < O(n^{n})
●递归空间复杂度表现为他的递归层数，每一次调用自身都会开辟一次栈空间
5)题目
●算法题计算时间复杂度
●嵌套循环下的时间复杂度
●什么是算法？
2.线性表
基础中的基础，但基本上算法题都出在这里，多做力扣上面的题目（剑指Offer）
1)顺序表
●特点：逻辑顺序和物理顺序相同
●最主要特点：随机访问（区别于链表的最主要特征）
2)链表
●特点：结点间离散存储在计算机的内存上，但是结点内部是连续的
●静态链表：表现为 Node = a[a[i]]，以next == -1作为结束标志
3)题目
●双指针
●快慢指针（判断环）
●原链表下的逆置
●两个链表实现加和(力扣题)
3.栈、队列、数组
没啥好说的，基础
1)共享栈：两侧向中间逼近
2)链栈在存储方面优于顺序栈
3)卡塔兰数：\frac{1}{n+1}C_{n}^{2n} （不同元素进栈，出栈序列的个数）
4)循环队列二叉树公式
●区分队满的方式
●牺牲一个单元来区分队空和队满
●类型中增设表示元素个数的数据成员
●类型中增设tag
●特点：rear始终在front沿着顺时针的前面
●初始时：Q.front = Q.rear = 0;
●队首指针进1（弹出）：Q.front = (Q.front + 1) % MaxSize;
●队尾指针进1（压入）：Q.rear = (Q.rear + 1) % MaxSize;
●队列长度：(Q.rear + MaxSize - Q.front) % MaxSize;
●队满条件：(Q.rear + 1) % MaxSize == Q.front;
●队空条件：Q.front == Q.rear;
5)链队：在删除时原队列仅有一个结点，删除时会有Q.rear = Q.front所以在删除的
时候可能头尾结点都会改变
6)栈的应用
●括号匹配
●前中后缀表达式的转变
●表达式求值
●递归
7)队列应用
●层次遍历
●操作系统算法
●缓存
●任务池（实现一定时间内只可执行n个任务，后来的任务需要排队执行）
8)数组：注意行优先还是列优先
9)题目
●出栈个数
●弹出栈后的元素随即进入队列，根据队列的出对顺序求栈的最小容量
●循环队列如何求当前队的元素个数
●前缀、后缀表达式求值
4.串
大部分学校不会考KMP算法，但是next数组是关键
1)求解next、nextval数组方法
5.树和二叉树
超级重点，需要认真把握
1)基本概念
●树中一个结点的孩子个数称为结点的度，树中结点的最大度数称为树的度
●深度 = 高度，但是深度是从上到下计算的，高度是从下到上计算的
●路径长度是路径上所经过的边的个数。路径是从A结点到B结点所经过的结点
序列
2)基本性质
●结点数 = 度的和 + 1
●度为m的树中第i层上最多有m^{i-1}个结点（i >= 1）
●高度为h的m叉树至多有\frac{m^{h}-1}{m-1}个结点
●具有n个结点的m叉树最小高度为\left \lceil log_{m}(n(m-1)+1) \right \rceil
3)二叉树
●n_{0} = n_{2}+1
●完全二叉树
●结点i所在的层次：\left \lfloor log_{2}i \right \rfloor+1
●具有n个基点的完全二叉树的高度为：\left \lceil log_{2}(n+1) \right \rceil、
\left \lfloor log_{2}n\right \rfloor+1
●对完全二叉树进行顺序存储时，最好从下标1处开始写。若从0开始写则计
算父节点下标时会产生错误
●遍历二叉树
●先序遍历
●中序遍历
●后序遍历
●线索二叉树
●结构
●标志
4)树的存储结构
●双亲表示法
●孩子表示法
●孩子兄弟表示法

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。