数据结构
时间复杂度(这边都是非递归)
O(1) 加法：相加，保留最高项系数化为1 4n^3+2n²+4n+2 =n^3乘法：相乘，系数化为1规则：先括号在乘在加log2n 常见是while循环 x=x*2n 常见的for循环 x++ 时间复杂度(递归的)=递归的次数*每次递归的时间复杂度(复杂度一样的情况) 空间复杂度(非递归) O(1) O(n) O(n²) (非递归的) 递归:nlog2n log2n看定义的空间 1 一个空间 n一维数组 n² 二维数组 渐进符号 递归主方法 运行时间更快就是时间复杂度更小 线性结构 线性表 最简单、最基本也是最常用的一种线性结构，采用顺序存储和链式存储定义：一个线性表是(n>=0)个元素的有限序列。非空的线性表，除了第一个外，其他元素都只有一个直接前驱，除了最后一个，其他元素都只有一个直接后继只有一个时它既是第一个也是最后一个，没有前驱和后继。顺序存储 一组地址连续的存储单元依次存储在线性表中的数据元素。只有数据优点：可以随机存取表中的元素 查找时间复杂度O(1)缺点:插入删除都需要移动元素 插入需要平均移动n/2 时间复杂度O(n)删除需要移动n-1/2 链式存储 通过指针链接起来的结点来存储数据元素。 数据域|指针域带头(不带头)单链表插入、删除、查找平均复杂度O(n) 平均移动 0 栈 只能访问它的一端来实现数据的存储和检索的一种线性数据结构特点：先进后出，进行插入跟删除的一端是栈顶，另外一端是栈底。没有数据元素就是空栈实现函数或过程的递归调用及返回处理时出栈跟入栈是不需要遍历的 队列 先进先出的线性表，只允许在表的一端插入元素(队尾Rear)，而在表的另外一端删除元素(对头Front) 串 仅有字符构成的有限序列，是一种线性表。空格也算长度，里面不包含任何字符才是空串(长度为零)子串：串中任意长度的连续字符构成的 ‘abc’ ab bc ac(不算)串的模式匹配 n主串:b b c a b e m模式串:a b e朴实模式匹配 模式串第一位比较主串第一位如匹配就比第二位，若不匹配 ，则模式串的第一位匹配主串的第二位，以此类推，匹配成功返回主串的起始位置。失败了1开始就返回0,0开始就返回-1时间复杂度最好O(m) orO(1) 最坏O(m*n) or(n-m+1)m 平均O(n+m) KMP 前缀：b bb bbc bbca bbcab （以上面主串n为例）后缀:e be abe cabe bcabe第i个字符的next值=1~i-1串中最长的相等前后缀长度+1 特殊情况next[1]=0ps:主串:a b a b a next的第五个的next值 3时间复杂度O(n+m) 数组的首地址 矩阵 n*n矩阵 存储n²个元素对称矩阵 就是Aij=Aji 所以存储的时候只需要存 主对角线+下三角区i>=j时按行存储从0开始 Aij=(i+1)i/2+j+1 j>=i时根据Aji=Aij求解就行了 三对角矩阵 就是只有三条斜对角线，旁边的三角形(都是0)不要，也不需要存储按行存储从0开始的 Aij=2i+j+1 稀疏矩阵 矩阵很大，存储的东西很少三元顺序表和十字链表是压缩存储方式 树 度就是子节点的个数，度为0的结点为叶子结点。一棵树的最大层数记为树的高度，最大的度数记为树的度性质 二叉树 结点最大度为2，0个结点的为空树，有递归性质，结点的子树需要分左子树右子树 性质 完全二叉树：编号可以从1-n连续着 顺序存储 一组地址连续的存储单元存储的二叉树中的结点，结点排成一个线性序列最坏情况，深度k且只有k个结点，需要2的k次方-1个存储单元 链式存储 二叉树结点包含有数据元素、左子树的根、右子树的根及双亲，因此可以用三叉表跟二叉表来存储。链表的头指向二叉树的根节点二叉树表n个结点会有n+1个空指针域三叉树表n个结点会有n+2个空指针域 二叉树的遍历算法 先序遍历(根左右)中序遍历(左根右)后序遍历(左右根)层次遍历(从第一层到第i层，每层左到右遍历)要推出其他的序列必须要有一个中序遍历，其他的随意再来一个即可。 平衡二叉树 二叉树的任意一个结点的左右子树高度之差的绝对值不超过1如果是完全二叉树就一定是平衡二叉树，叶子结点一定满足 二叉排序树(二叉查找树) 根节点大于左子树的所有结点，小于右节点所有的关键结点，左右子树也是一颗二叉排序树中序遍历得到的序列是有序序列 最优二叉树(哈夫曼树) 一类带权路径长度(WPL)最短的树构造最优二叉树(不唯一但是wpl是一样的) 从前往后找两个权值最小的小左大右算完加入末尾权值相同，从前往后 只有度为0跟2的结点，总个数为:2n-1 哈夫曼编码 左零右一，几位数*几，贪心策略压缩比 (等长编码-哈夫曼编码)/等长编码等长编码x：2的x次方>=几个字符，就是几位哈夫曼编码:几位*出现频率 线索二叉树 为了保存结点在任一序列中的前驱和后继信息，利用空指针域来存储 图 n个顶点，无向完全图共有n(n-1)/2 有向完全图共有n(n-1)有向无向的度=边数*2无向连通图：每个顶点都是连通的 最少有n-1条边最多n(n-1)/2 有向强连通图:每个顶点都可以来回连通 最少n边最多n(n-1) 路径：到达经过了几条边，就是几领接矩阵：顶点之间的关系，适用稠密图存(边多) 无向图的是对称的，第i行(列)就是顶点的度 2e非零个数有向图是不对称的，行是出度，列是入度 e个非零个数 链接链表，适用于稀疏图存(边少) 图 网图 图的遍历： 从某个顶点出发，访问所有顶点，只访问一次的过程 深度优先遍历(DFS) 栈 和广度优先搜索(BFS) 队列 序列都不唯一有向图平均复杂度：领接矩阵O(n²)、领街表O(n+e) 拓扑排序 AOV网(有向无环图) 顶点Vi到顶点Vj有一条有向路径，则顶点Vi是Vj的前驱 z在网中选择一个入度为0的顶点且输出它从网中删除该顶点及与该顶点有关的弧重复上两步，直到网中不存在入度为0 的顶点为止 查找 查找表示有同一类型的数据元素构成的集合。关键字是数据元素的某个数据项的值，一个就是主关键字，多个是次关键字。给关键字，找到就是查找成功，失败就是空指针静态查找:顺序、折半、分块查找动态查找:二叉排序树、平衡二叉树、B_树、哈希表顺序查找成功的平均查找长度:n+1/2折半(二分)查找(正常都下取整) 要求顺序存储，并有序排列递增平均查找长度:log2(n+1)-1最多是[log2n]+1 向下取整 哈希表 哈希函数，将关键字映射到空间去，这一过程叫哈希造表或散列，存储的地址为哈希地址或散列地址冲突就是不同关键字具有相同哈希函数值，映射同一个地址了，它们两个为同义词冲突是不可避免的，只能尽量的避免哈希构造方法:除留取余法，H(key)=key%m=地址 m一般取接近n(n个元素)但不大于n的质数尽可能使用关键字的所有组成部分都能起作用 处理冲突 开放地址法 Hi=(H(key)%di)%m(表长) 线性探测法二次探测法:1、-1、4、-4、9、-9…k²、-k² 链地址法:记录后面加一个链域用来存放下一个相同哈希的函数值的记录的存储地址 哈希表的查找 取决因素:哈希函数、处理冲突的方法、哈希表的装填因子a a=表中装入的记录数/哈希表的长度a越小，冲突可能性就越小，反之同理。 堆 大顶堆 ki>=k2i和k2i+1小顶堆 ki<=k2i和k2i+1可以根据二叉树的顺序存储来画图 学会如何构造大(小)顶堆 排序 将相应的关键字。经过排序满足了递增(递减)关系 内部排序：排序记录全部存放在内存中 外部排序 计数排序适合于序列中只有0-9的数字，统计每个数的个数 直接插入排序不可以归位 简单选择排序可以归位 堆排序可以归位 快速排序(分治算法)可以归位 归并(分治)不可以归位 好文链接
发表评论