ACM所有算法总结归纳 .ppt

树状数组 对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度有3N降为N,时间效率也有所提高.编程复杂度更是降了不少. 在很多的情况下,线段树都可以用树状数组实现.凡是能用树状数组的一定能用线段树.当题目不满足减法原则的时候,就只能用线段树,不能用树状数组.例如数列操作如果让我们求出一段数字中最大或者最小的数字,就不能用树状数组了. 链表 链表是内存中不连续块链接而成的数据结构，本着使用多少分配多少的原则，极大地节约和利用了内存，是一种十分基础的数据结构。 优势： 1、动态分配 2、快速删除与插入 3、节省空间 链表 缺点： 1、查找效率低下 2、动态分配结点调用操作系统实现，导致空间分配效率消耗 一种对空间的优化： 内存静态化！！ 一般应用 1、桶 2、跳跃表 桶 一般用做哈希的冲突避免策略，使用桶结构存储在同一冲突域下的数据，作为键值的扩展。 基数数排序的辅助结构。 跳跃表 可以看做是链表结构最优秀的应用，使用跳跃表有着令人震撼的效率，对查询、删除和添加的操作均为O（logn）的复杂度。 利用了链表自身的特点，以较小的空间代价提升了自身的性能。使用了概率算法，使效率堪与AVL、RB-Tree等BST相媲美。 相比而言，极低的编程复杂度！！！有什么理由可以不去掌握呢？ 跳跃表 跳跃表由多条链构成（S0，S1，S2 ……，Sh），且满足如下三个条件： 每条链必须包含两个特殊元素：+∞ 和 -∞ S0包含所有的元素，并且所有链中的元素按照升序排列。 每条链中的元素集合必须包含于序数较小的链的元素集合，即： 53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 -∞ -∞ -∞ -∞ +∞ +∞ +∞ +∞ S0 S1 S2 S3 跳跃表的实例 跳跃表之查找 目的：在跳跃表中查找一个元素 x 在跳跃表中查找一个元素x，按照如下几个步骤进行： 从最上层的链（Sh）的开头开始 假设当前位置为p，它向右指向的节点为q（p与q不一定相邻），且q的值为y。将y与x作比较 x=y 输出查询成功，输出相关信息 xy 从p向右移动到q的位置 xy 从p向下移动一格 如果当前位置在最底层的链中（S0），且还要往下移动的话，则输出查询失败 53 53 53 45 45 37 30 30 30 29 15 11 11 11 11 -∞ -∞ -∞ -∞ +∞ +∞ +∞ +∞ 查询元素53的全过程 S0 S1 S2 S3 查找成功！ 跳跃表之插入 目的：在跳跃表中插入一个元素 x 插入操作由两部分组成： 查找插入的位置和插入对应元素。 为了确定插入的“列高”，我们引入一个随机决策模块： 产生一个0到1的随机数r r ← random() 如果r小于一个概率因子P，则执行方案A， if rp then do A 否则，执行方案B else do B 列的初始高度为1。插入元素时，不停地执行随机决策模块。如果要求执行的是A操作，则将列的高度加1，并且继续反复执行随机决策模块。直到第i次，模块要求执行的是B操作，我们结束决策，并向跳跃表中插入一个高度为i的列。 跳跃表之插入 假设我们现在要插入一个元素40到已有的跳跃表中。 37 30 30 30 29 15 -∞ -∞ -∞ -∞ S0 S1 S2 S3 插入的位置 53 53 53 45 45 +∞ +∞ +∞ +∞ 40 40 40 40 高度+1 随机化模块运行状况： 高度=4 高度+1 高度+1 结束 53 跳跃表之删除 目的：从跳跃表中删除一个元素 x 删除操作分为以下三个步骤： 在跳跃表中查找到这个元素的位置，如果未找到，则退出 将该元素所在整列从表中删除 将多余的“空链”删除 -∞ -∞ -∞ -∞ S0 S1 S2 S3 11 11 11 11 53 53 53 45 45 37 30 30