数据结构思维导图
数据结构概述
树图思维导图提供 数据结构 在线思维导图免费制作，点击“编辑”按钮，可对 数据结构 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：11db5cd17dcdd3b433d2f2fc9cb747f7
思维导图大纲
数据结构思维导图模板大纲
考试时如何写代码
重要的是让老师理解思路，不需要能执行
不能完全用机试的思维做
不能省略、调用库函数的地方
超过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)
书写
先考虑清楚整个做法再做题
第一问
主要介绍逻辑，告诉老师你用了什么，比如快排
第二问
注释详实，用来介绍这部分变量、过程的作用
对于快速排序和折半查找（注意是否查找成功）可以直接默写，过程函数不需要改动，注意调用的参数即可
第三问
直接写复杂度，不用过程，要检验是否符合代码
真题检验
使用上述的分析方法
沪公网安备 31011502019485号
上海工商