数据结构思维导图
数据结构概述
树图思维导图提供 数据结构 在线思维导图免费制作，点击“编辑”按钮，可对 数据结构 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：e1b00e5c54cfdd3b4a8dcfb0aa0ee9d7
思维导图大纲
数据结构思维导图模板大纲
考试时如何写代码
重要的是让老师理解思路，不需要能执行
不能完全用机试的思维做
不能省略、调用库函数的地方
超过1/4的代码不能省略
可以偷懒的地方
最大最小值Max_int、Min_int
比大小函数max(a, b)、min(a, b)
输入输出函数Cin、Cout
A[i++]和A[++i]
交换函数swap(a, b)
复杂度问题
题目的描述
时间上尽可能高效
不用管空间
时间和空间两方面都尽可能高效
先时间后空间
尽可能高效
先时间后空间
空间复杂度为O(1)且时间上尽可能高效的算法
只管时间，空间O(1)
什么都没说
能做出来就行
本质
空间复杂度：使用额外
多项式的最高项（不考虑常数部分）
时间复杂度
定义
指令执行总次数数量级
计算
循环
递归次数
空间复杂度
定义
额外空间数量级
计算
数组、链表
递归层数
符合加法原理
算法题只考虑最坏复杂度
顺序表
先想出暴力解法
枚举所有情况
代码简洁
对无序数组快速排序
需要默写快排
思考优化
有没有条件没用到
摆烂人
有没有超额完成任务
卷王
有没有别的思路
王道顶针
潜在优化算法，根据条件选择优化
折半查找
条件：一个、数组、有序
数组指针后移
条件：多个、线性表、有序
原理：归并算法
以空间换时间
空间保存状态
贪心思想
每次选最有利的
类快排
分析复杂度
常见时间复杂度：O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^3)
书写
先考虑清楚整个做法再做题
第一问
主要介绍逻辑，告诉老师你用了什么，比如快排
第二问
注释详实，用来介绍这部分变量、过程的作用
对于快速排序和折半查找（注意是否查找成功）可以直接默写，过程函数不需要改动，注意调用的参数即可
第三问
直接写复杂度，不用过程，要检验是否符合代码
单链表
特点
是线性表
无法随机访问
用不了快排
用不了折半
只能向后查找，无法回头
需要注意题目要求
空间复杂度要求是O(1)
不可修改链表结构
注意是否有头节点
考察结构
记忆模板，根据题目要求修改
先想出暴力解法
枚举，用一些比较“憨”的做法
容易思考
先用数组保存链表元素
使用条件：题目所求不是链表，而是值
优化方向
利用链表的操作
前后指针
前后指针的距离是一样的
查找倒数第k个
快慢指针
如果有环，快指针早晚追上慢指针
头插法
逆置
类似数组指针后移
条件：多个、线性表、有序
原理：归并算法
以空间换时间
树
考察结构
记忆模板，根据题目要求修改
二叉树
左右孩子表示法
双亲表示法
并查集
树和森林
孩子兄弟表示法
重点考察遍历
二叉树
先序
中序
后序
层序
树和森林
先根
后根
层序
树转二叉树
理解即可
二叉排序树
平衡二叉树
红黑树
真题检验
使用上述的分析方法
沪公网安备 31011502019485号
上海工商