结构型结构体递归类3.空间复杂度
数据结构（#数据结构与算法#）选择题
单项选择填空题中易
·绪论：时间复杂度空间复杂度等会看会计算会推导（重点：递归，真题：汉诺塔）
·线性表：基本概念实现操作单、双、循环等等
·栈和队列：灵活，栈队列基本概念定义使用操作变形（共享栈，双端队列，波兰表达，逆波兰表达，波兰表达式求解）比较多算是重点
·串：不考不讲但是有一分超纲18年但是还是不用看至于KMP匹配等全部略上机有可能后期事情
·数组、矩阵、广义表基本概念定义使用操作三元组十字链表邻接表广义表两种存储方式概念类定义类居多
·树与二叉树：二叉是重点二叉树的基本概念定义使用操作三种遍历转换线索二叉哈夫曼树哈夫曼编码
·图基本概念定义使用操作遍历深度和广度最小代价树最短路径拓扑关键路径等等
·排序基本概念定义使用操作选择类交换类插入类基数排序外部（不考不讲看一下就行）
·查找基本概念定义使用操作基本查找之外重点有二叉排序树平衡二叉B-B+树散列表
简答题中等题
·绪论：时间复杂度的推导和计算10分
·线性表结构体定义
·栈和队列波兰表达式过程栈队列使用情况画图（画图题）
·十字链表广义表结构体画图
·二叉树：前中后表达式线索树二叉、树、森林的相互转换哈夫曼树生成（画图）哈夫曼编码（画图）
·图：结构体定义邻接表邻接矩阵两个搜索普里姆算法克鲁斯卡尔（加点法加边法配合画图）弗洛伊德和迪杰斯特拉算法（画图画表）AOVAOE网（画图画表）
·排序过程类（画图）
·查找构造类哈希表和解决冲突的方法折半构造二叉排序树和平衡二叉的B树类
算法题中等偏上
链表原地逆置
快排
希尔排序
最基础的图结构体定义和基本操作
二叉树层次遍历（求最宽层）
八皇后（经典回溯加剪枝）
#一.绪论
##1.代码规范和语言基础
###代码规范
不能使用伪代码
C、C++
考到指针之前面向过程OK
核心算法：纯手工实现
不可以使用STL库等API
结构型基本数据类型：intfloatchar。。。。
常用需要注意：数组长度definemaxsize简写
举例inta[maxsize];
free（p）；
结构体typedefstruct{intdata;intn;}TypeX;指针型的int*a;TypeX*x;节点的定义typedefstructNode{intdata;structNode*next;}Node;//树typedefstructBTNode{intdata;structBTNode*lchild;structBTNode*rchild;}BTNode;//申请内存(BTNode*)malloc(sizeof(BTNode));//释放free(BTNode)；//方法voidfunc(形参1，形参2...){}//有返回情况的类型func(形参1，形参2...){方法体；return类型；}//define几乎用不到
##2.时间复杂度
###forwhiledo—while类
陷阱，挖坑题：
基操：循环中最内层操作前++后+++=*=
真正循环次数（规模）：多层循环（画个草图）
数据本身一些特征
解释下面的链式
O（1）=O(lob2n)=.........=O(2^n)
1.n无穷大的
2.n如果有限制则不成立
3.计算题对每种曲线特性要了解
18年比较特定n下的时间复杂度2分
递归类解题思路：
·确定基操和规模
·以终结条件为依据建立基操和规模的等式（草图）
·数学归纳或递推公式解出结果
所有递归类都可以用小规模去试验然后归纳法得到结果（tips:可利用小规模去推测答案，辅助递推公式求解）
3.空间复杂度占用临时内存的大小