数据结构与算法 8. 高级搜索树 2021-07-26 浏览量 529 暂无评论 [TOC] ## 8.1 伸展树:逐层伸展 ### 宽松平衡 更潇洒 ### 局部性 刚被访问过的数据,极有可能很快地再次被访问。 对于AVL数,连续m次访问的时间复杂度:$O(mlogn)$ ### 自适应调整 拿列表来说,每次访问完一个元素,就把它移到前端,方便下次访问。 ### 逐层伸展 通过zig和zag等价变化,将节点逐步移到树根。 一步一步往上爬:自下而上,逐层单旋。 ### 最坏情况 退化为单链,每一周期$\omiga (n^2)$ ## 8.2 伸展树:双层伸展 旋转两次 子孙异侧时与逐层伸展等效 子孙同侧时,有改进的地方,也就是先旋转祖父,而不是父亲。这样微小的变化在全局上有不同的结构,每次访问完最深点,树的高度都被优化为一半。 分摊复杂度:$log(n)$ ![在这里插入图片描述](https://img-blog.csdnimg.cn/a05ea2298c324747ac5a5fa31ef36776.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.4 伸展树:算法实现 ### 功能接口 ```cpp template class Splay : public BST { protected: BinNodePosi(T) splay(BinNodePosi(T) v); public: BinNodePosi(T) & search(const T & e); // 查找也会引起拓扑变化,动态 BinNodePosi(T) insert(const T & e); bool remove(const T & e); }; ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/cac8624a4920439c9a6f47ebcca20d29.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 查找算法 ```cpp template BinNodePosi(T) & Splay::search(const T & e) { BinNodePosi(T) p = searchIn(_root, e, _hot = NULL); _root = splay(p ? p : _hot); return _root; } ``` ![在这里插入图片描述](https://img-blog.csdnimg.cn/71f4eff30c68461383190cd6a390366a.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/2e5c8ec60ba44d6ab7099904202a1128.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/9168b2d0554e4e868e4a255ec0b47c0c.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/2af05a5820a0422b9912562071818be8.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 综合评价 优于AVL树 分摊复杂度$O(log(n))$--与AVL树相当 局部性强、缓存命中率极高时(即k << n << m) 效率甚至可以更高--自适应的$O(logk)$ ## 8.5 B树:动机 严格意义上,B树并不是二分查找树,因为节点可能包含多个分支,从逻辑意义上,仍等效于二分查找树。 弥合不同存储级别之间在访问速度上的巨大差异,即实现高效IO。 **640KB。** 物理上,存储器的容量与速度成反比。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/56f77422c0c64bf39805fa60d4de971a.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/66dde712631845738d62b9dd8ef2cb64.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.6 B树:结构 B树又宽又低。 平衡的多路搜索树。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/f19f53253de845549d610edb9dab0547.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 多级存储系统中使用B-树,可针对外部查找,大大减少I/O次数。 怎么说?批量访问,超级节点的规模视磁盘的数据块大小而定。 **有个重要的参数:阶数** ![在这里插入图片描述](https://img-blog.csdnimg.cn/738bee2bc57c4ab08d777efa46965042.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 在这里,外节点是叶节点的空子树。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/526c392fb31244a09fe70692b74e9d96.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 最大关键码的个数其实就是d代中节点的最大总数,2代3个,3代7个 最大分支数就是下一代的最大节点数,2代的下一代4个,3代8个,最小分支数就是最大分支数的一半,也就是保证上一代的每个节点至少有一个分支? (2, 4)树与红黑树渊源不小。 ### 结构定义 ![在这里插入图片描述](https://img-blog.csdnimg.cn/a62cd40a493b48f886407aee6560c27d.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/7bfa2c2424c14fa592a47371b2eea2fc.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.7 B树:查找 只将需要的节点载入内存。 在每一节点进行顺序查找(因为是中序的),成功则返回,失败则通过停留位置的引用前往下一层(进行一次I/O)。 ### 实现 ```cpp template BTNodePosi(T) BTree::search(const T & e) { BTNodePosi(T) = _root; _hot = NULL; while (v) { Rank r = v->key.search(e); if (0 <= r && e == v->key[r]) return v; _hot = v; v = v->child[r + 1]; } return NULL; } ``` **为了与I/O匹配,每个节点的规模大概xxKB,实验表明,在此规模的有序向量下,顺序查找效率要高于二分查找。** ### 最大树高 ![在这里插入图片描述](https://img-blog.csdnimg.cn/e3fca4b81cb349db9dafa0bd6e746866.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 最小树高 ![在这里插入图片描述](https://img-blog.csdnimg.cn/df1807f25de042c6b914e217c9ef2c06.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) B树高度变化有限,最高和最低接近。 ## 8.8 B树:插入 ```cpp template bool BTree::insert(const T & e) { BTNodePosi(T) v = search(e); if (v) return false; Rank r = _hot->key.search(e); _hot->key.insert(r + 1, e); _hot->child.insert(r + 2, NULL); _size++; solveOverflow(_hot); return true; } ``` 如发生上溢,需分裂。 发生上溢的情况:超过m个分支,即插入后有m + 1个分支,m个关键码 分裂步骤: - 设上溢节点中的关键码依次为$k_0, k_1, k_2, ..., k_{m-1}$ - 取中位数$s = \lfloor m/2 \rfloor$,以关键码$k_s$为界划分为$k_0, ..., k_{s-1}$,$k_s$,$k_{s+1}, ..., k_{m-1}$ - 关键码$k_s$上升一层,并分裂,以所得的两个节点作为左右孩子(为什么可以有左右呢?上升一层是指将该关键码插入到上一层超级节点还是单独作为一个节点,如果是插入到上一层的超级节点,那不是只多了一个分支吗?哦,没错,因为本身该关键码所在的超级节点也是一个分支,只要把分裂出的右半部分作为新孩子接入即可。) 时间复杂度:$O(h)$ ## 8.9 B树:删除 ![在这里插入图片描述](https://img-blog.csdnimg.cn/6e2478996e23403796f92f81cf28d5b7.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 发生下溢的情况:恰好包含$\lceil m/2 \rceil-2$个关键码 + $\lceil m/2 \rceil-1$个分支 当前节点左顾右盼,朝兄弟借一个关键码(但实际实施时是向父亲借,父亲再管儿子要),兄弟的关键码要不小于$\lceil m/2 \rceil$。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/979e38ad8ac446c4947c6fe9db65ca6a.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 如果左顾右盼不行的话$\lceil m/2 \rceil -1$,就要采用优先级低的合并。 将父亲的关键码拿下来,和两兄弟合并。 ## 8.10 红黑树:动机 先前的数据结构在经动态操作后,其之前的状态都转瞬即逝,没有记忆。 当然可以通过保存历史版本来记忆,但在时间和空间上均不如人意。 利用前后版本间的关联性。 如果想将前后版本之间的拓扑差异不超过$O(1)$,那么每次动态调整时,旋转操作不能超过常数次,AVL树的插入操作是满足的。 有没有一种树结构,任何动态操作都控制在$O(1)$。 有,红黑树! ## 8.11 红黑树:结构 ### 定义规则 由红黑两类节点组成的BST(统一增设外部节点NULL,使之成为真二叉树) - 树根:必为黑色 - 外部节点:均为黑色 - 其余节点:若为红,则只能有黑孩子 // 红之子、之父必黑 - 外部节点到根:途中黑节点数目相等 提升变化:将所有红节点提升至与其父亲齐平 红黑树经提升变换后即变为4阶B树,将黑节点与其红孩子视作超级节点。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/cf6bf3ec8e244b03a8afe31b0c7d5898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/ef412b3a79f14bfba7f6d25fd1e80a88.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.12 红黑树:插入 插入节点x时,将x染红(除非它是根节点),红黑树的规则124满足,但3未必满足,如果插入节点的父亲为红色,会出现“双红缺陷”,如何解决呢? ![在这里插入图片描述](https://img-blog.csdnimg.cn/80345f1af8254f5d81956107e58a1044.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 双红修正1:插入节点的叔父为黑 "3+4"重构后调整节点颜色 ![在这里插入图片描述](https://img-blog.csdnimg.cn/1d751f5f2015476e8f0d12038b016873.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/5680e4d923b74f3a8c83c6195eb37109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 双红修正2:插入节点的叔父为红 ![在这里插入图片描述](https://img-blog.csdnimg.cn/717a807cc6a04f22a5148b69fe35dcdb.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 8.13 红黑树:删除 时间复杂度不会超过$logn$ 但拓扑结构变化只有常数次,重染色可能进行多次。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/8fcdea33f1194d169f85b6e3949b7923.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) - 阅读全文 -
数据结构与算法 7. 二叉搜索树 2021-07-24 浏览量 520 暂无评论 [TOC] ## 7.1 概述 借鉴了列表的特点,又借鉴了有序向量的特点(质的提高)。 BST的优势集中体现在一个子集--平衡二叉搜索树BBST - 定义 - 特点 - 接口 ### 循关键码访问--call-by-key 数据项之间,依照各自的关键码区分。 **条件**:大小比较 + 相等比对 **词条** ![在这里插入图片描述](https://img-blog.csdnimg.cn/f34589ba824a47519b2c7fd340d27b32.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 有序性 节点 ~ 词条 ~ 关键码(等效) 任一节点均不小于/不大于其左/右后代 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2fd187c0eb4c4b68b4a7f36a2d362db1.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70#pic_center) ### 单调性 局部有序性 -> 单调性(中序遍历--二叉树垂直投影) 这也是二叉树为BST的充要条件。 ### 接口 ![在这里插入图片描述](https://img-blog.csdnimg.cn/bba1001f930d4907bffa83e9ca033305.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 虚函数: - 派生类重载基类的虚函数后,指向派生类的基类指针`human* test = new man("dd");`可以调用派生类的虚函数,因为派生类的虚函数表中对应的函数地址已替换为重载后的函数地址;如果派生类重载了基类的普通函数,那么指向派生类的基类指针只能调用基类的普通函数 - 地址存在虚函数表中,每个含有虚函数的类都有一个虚函数表指针,指向该类的虚函数表 - 含有纯虚函数`virtual 返回值类型 函数名字(参数) = 0`的类不能实例化,称作抽象类。 ## 7.2 查找 减而治之,类似有序向量的二分查找。**共性**:存在某一部分整体不大于某数,另一部分整体不小于该数。 ```cpp template BinNodePosi(T) & BST::search(const T & e) { return searchIn(_root, e, hot = NULL); } static BinNodePosi(T) & searchIn( BinNodePosi(T) & v, const T & e, BinNodePosi(T) & hot) { if (!v || (e == v->data)) return v; // 记录当前非空的节点 hot = v; return searchIn(((e < v->data) ? v->lChild : v->rChild), e, hot); } ``` **时间复杂度**:$O(h)$ **语义**:成功时,返回命中的真实存在的节点;失败时,返回假想的命中节点(空节点),这样,_hot就总是指向命中节点的父亲。 ## 7.3 插入 假设不存在重复词条 先调用`search(e)`找到应该插入的位置的节点的引用,再将值赋给该引用。 ```cpp template BinNodePosi(T) BST::insert(const T & e) { BinNodePosi(T) & x = search(e); if (!x) { x = new BinNode(e, _hot); _size++; updateHeightAbove(x); } return x; } ``` 时间复杂度:$O(h)$ ## 7.4 删除 当只有一个孩子时,直接用这个孩子替换; 当左右孩子都存在时,**化繁为简**,找到要删除节点的后继(中序遍历的下一个节点),交换,再删除。 ```cpp template bool BST::remove(const T & e) { BinNodePosi(T) & x = search(e); if (!x) return false; removeAt(x, _hot); _size--; updateHeightAbove(_hot); return true; } template static BinNodePosi(T) removeAt(BinNodePosi(T) & x, BinNodePosi(T) & hot) { BinNodePosi(T) w = x; BinNodePosi(T) succ = NULL; // 其实这里也处理了同时有左右孩子时的左孩子 if (!HasLChild(*x)) succ = x = x->rChild; else if (!HasRChild(*x)) succ = x = x->lChild; // 能不能将右子树接到左子树的最右端呢? else { w = w->succ(); swap(x->data, w->data); BinNodePosi(T) u = w->parent; (u == x ? u->rChild : u->lChild) = w->rChild; } hot = w->parent; if (succ) succ->parent = hot; release(w->data); release(w); return succ; } ``` 时间复杂度取决于succ(),不会超过$O(h)$ ## 7.5 平衡与等价 二叉搜索树本意是要结合向量与列表的优点,即查找地快、插入/删除地快,而目前,最坏的时间复杂度都为$O(h)$。 考虑退化的情况,所有节点的度不超过1,树退化为单链,最坏情况时间复杂度均变为$O(N)$。 ### 随机生成 n个节点,可以有n!种排列 平均高度为$O(log(n))$,有重复计算的情况。 ### 随机组成 n个节点,可以有catalan(n)种,即互异BST树的数量,也是拓扑互异的二叉树的数量。 $C_{n+1}=C_0C_n+C_1C_{n-1}+...+C_nC_0$,前几项为$1, 1, 2, 5$ 平均高度为$O(\sqrt{n})$,更符合实际,但比随机生成的高度更高。 ### 什么样的树高度更低呢? - 节点数目固定时,兄弟子树高度越接近平衡,全树也将倾向于更低 - 由n个节点 组成的二叉树,高度不低于$\lfloor log_2n \rfloor$--恰为$\lfloor log_2n \rfloor$时,称作理想平衡。 完全二叉树、满二叉树满足理想平衡,但不切实际。 退一步,只要渐进地不超过$O(logn)$就行了,叫适度平衡。 拓扑结构不同,但中序遍历相同的BST,称作等价BST。 ### 等价变换 zig, zag ![在这里插入图片描述](https://img-blog.csdnimg.cn/799b57ecf6e14dbab227c87abb44d7b8.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 7.6 AVL树--重平衡 ### 平衡因子 节点左子树与右子树高度之差 若对任意节点,平衡因子绝对值均小于等于1,则称为AVL树。 ### 适度平衡 ![在这里插入图片描述](https://img-blog.csdnimg.cn/c18cb81964bc4f48861892a53e390740.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 接口 ![在这里插入图片描述](https://img-blog.csdnimg.cn/dcc5038298b045e596d13c95a61bf724.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 失衡 + 复衡 插入一节点后,可能引起一系列祖先高度变化; 删除一节点后,只会引起一个高度最低祖先高度变化。 **疑问**:在例子中,如果删除节点N+,那一系列祖先的高度不就都变化了吗? 纠正:不是高度,是平衡性 ![在这里插入图片描述](https://img-blog.csdnimg.cn/b26d3dcb82ac40ce97cf7d8526960c91.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 7.7 插入 ### 单旋 p的左子树变为g的右子树,g变为p的左子树,祖父变为p 包含gpv节点的子树高度不变。 zagzag:gpv斜向右下 zigzig:gpv斜向左下 ![在这里插入图片描述](https://img-blog.csdnimg.cn/f1502ead69c54c88a00caab9007c6385.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 双旋 zigzag 两轮旋转 先对p进行zig,再对g进行zag,最终把v提到最高,gp等高。 包含gpv节点的子树高度不变。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/6ff8cca5c8c2417fb15807e5c24adb8b.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 实现 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2f85c588934d4f98bb79c8535278ebfe.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 7.8 删除 ### 单旋 只做一次旋转 包含gpv节点的子树高度可能变化。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/4707a334d3d8412ea00bcef06eb6cf93.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 双旋 ![在这里插入图片描述](https://img-blog.csdnimg.cn/b30b2f8c59cf4f479c8a1142c9eb2634.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 实现 ![在这里插入图片描述](https://img-blog.csdnimg.cn/30869a1f3dea4455b84b19fea78694aa.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) # 7.9 (3+4)重构 观察上面插入和删除后重平衡的BBST,发现都是3个节点加4个子树,并且拓扑结构一致,并且等价变换后中序遍历一样,那可以直接将该3个节点和4个子树拼接起来。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/ed735a37385c4f37a44c9a42d2b3fb94.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 确定abc,T0~T3的顺序。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/beda6c92d91943c3b7d44c330eec4ad0.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/418ef9f8a92d4f849bd15a95553fb303.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) - 阅读全文 -
数据结构与算法 6. 图 2021-07-19 浏览量 655 暂无评论 [TOC] ## 6.1 概述 邻接、关联、有向、无向、路径、环路 简单路径:路径中不含重复节点 欧拉环路(Eulerian tour):经过图中所有的边一次且恰好一次的路径构成的环路。 哈密尔顿环路(Hamiltonian tour):经过所有点一次且恰好一次的环路。 无向图的边数等于各定点度数之和的一半。 ## 6.2 邻接矩阵 adjacency matrix:点与点的关系,$R^{n×n}$ incidence matrix:点与边的关系,$R^{n×e}$ ### 节点实现 ```cpp typedef enum {UNDISCOVERED, DISCOVERED, VISITED} VStatus; // 这里用struct只是想省去严格的封装 template struct Vertex { Tv data; int inDegree, outDegree; VStatus status; int dTime, fTime; // 时间标签 int parent; // 在遍历树中的父节点 int priority; // 在遍历树中的优先级 Vertex(Tv const & d) : data(d), inDegree(0), outDegree(0), status(UNDISCOVERED), dTime(-1), fTime(-1), parent(-1), priority(INT_MAX) {} }; ``` ### 边实现 ```cpp typedef enum {UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD} EStatus; template struct Edge { Te data; int weight; EStatus status; Edge(Te const & d, int w) : data(d), weight(w), status(UNDETERMINED) {} }; ``` ### 邻接矩阵实现 ```cpp template class GraphMatrix : public Graph { private: Vector> V; Vector*>> E; public: GraphMatrix() {n = e = 0;} ~GraphMatrix() { for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) delete E[j][k]; } } ``` ### 顶点静态操作 ```cpp int nextNbr(int i, int j) { while ((-1 < j) && !exists(i, --j)); // 逆向顺序查找 return j; } int firstNbr(int i) { return nextNbr(i, n); } ``` ### 边操作 ```cpp bool exists(int i, int j) { return (0 <= i) && (i < n) && (0 <= j) && (j < n) && E[i][j] != NULL; } Te & edge(int i, int j) {return E[i][j]->data;} ``` 插入和删除只需要设置相应的邻接矩阵即可,并维护对应的信息。 ### 顶点动态操作 顶点的插入与删除,维护V[], E[], E[j] ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210718223938829.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 综合评价 适合稠密图。 空间性能差。 平面图就稀疏,欧拉公式判断平面图$v-e+f-c=1$。0维:顶点数,1维:边数,2维:区域面片,+ 连通域 ## 6.3 广度优先搜索(BFS) 化繁为简,将图转化为支撑树(Spaning Tree)。等同于树的层次遍历。 遍历。 由指定节点出发,依次访问它的邻居,全部邻居访问完后再访问邻居的邻居。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210719104607637.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 单连通 ```cpp template void Graph::BFS(int v, int & clock) { Queue Q; status(v) = DISCOVERED; Q.enqueue(v); while (!Q.empty()) { int v = Q.dequeue(); dTime(v) = ++clock; for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) if (UNDISCOVERED == status(u)) { status(u) = DISCOVERED; Q.enqueue(u); status(v, u) = TREE; parent(u) = v; } else status(v, u) = CROSS; // 那(0, 1)和(1, 0)岂不是有两种状态了 status(v) = VISITED; } } ``` ### 多连通 ```cpp template void Graph::bfs(int s) { reset(); int clock = 0; int v = s; do if (UNDISCOVERED == status(v)) BFS(v, clock); while (s != (v = (++v % n))); } ``` ### 复杂度 本来是$O(n^2+e)$,但由于此处的for循环速度很快(一方面是特别基本的操作,另一方面是物理地址连续),所以第二个n可忽略,得到$O(n+e)$,也就是说至少要访问完每个节点和它的边。 ### 最短路径 BFS给出的顶点序列到起点s的距离,就是按照非降次单调排列的。 ## 6.4 深度优先搜索 过程: > 访问顶点s > 若s尚有未被访问的邻居,则任取其一u,递归执行DFS(u) > 否则,回溯 ### 单可达域 ```cpp template void Graph::DFS(int v, int & clock) { dTime = ++clock; status(v) = DISCOVERED; // 通过这个循环,可以实现回溯,访问祖先的下一个邻居 // 跳过父节点 for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) switch (status(u)) { case UNDISCOVERED: status(v, u) = TREE; parent(u) = v; DFS(u, clock); break; case DISCOVERED: status(v, u) = BACKWARD; break; default: // v < u,更早被发现,什么情况下会大于呢?回溯到祖先的邻居,且该邻居的邻居为visited status(v, u) = dTime(v) < dTime(u) ? FORWARD : CROSS; break; status(v) = VISITED; fTime(v) = ++clock; } ``` ### 多可达域 有向图要更复杂一些。引入可达域的概念。 ```cpp template void Graph::dfs(int s) { reset(); int clock = 0; int v = s; do if (UNDISCOVERED == status(v)) DFS(v); while (s != (v = ++v % n))); } ``` 一个回边代表一个回路。 ### 嵌套引理 打的时间标签有何用呢? ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210719190103771.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 6.5 拓扑排序 任给有向图G,尝试将所有顶点拍成一个线性序列,使其次序与原图相容(每一个顶点都不会通过边指向前驱顶点)。 非有向无环图排不出。DAG:Directed Acyclic Graph ### 零入度算法 流程: > 先找零入度的点,找到了就去掉 > 再找下一个 挺麻烦,每次都要遍历得到零入度的点,且需要更新图,可能改变图的原结构。 ### 零出度算法 先知道最后要干嘛,再向前找干这个需要什么,抽象出来就是DFS,每次回溯时的点。 DGF各节点按fTime逆序排序 ## 6.6 双连通分量分解 无向图。 - 关节点:去除该点后,图中的连通域数量增加。 - 双连通图:无关节点的图 - 极大的双连通子图,称作双连通分量(Bi-Connected Components) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210719205439926.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) hca(v) = subtree(v)经后向边能抵达的最高祖先。 - 阅读全文 -
数据结构与算法 5. 二叉树 2021-07-17 浏览量 607 暂无评论 [TOC] [课程链接](https://www.xuetangx.com/learn/THU08091000384/THU08091000384/5883586/video/9215810) [资料链接](http://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/) ## 5.1 树 向量和列表这种线性结构无法兼顾静态和动态操作的效率,怎么结合各自的优势? ## 5.2 一些性质 路径、深度、高度 节点的高度等于以该节点为根的子树的高度。 任一节点的深度加上高度不大于树的高度。 $depth(v)+height(v)<=height(T)$ ## 5.3 树的表示 ### 接口 节点|功能 --|-- root()|根节点 parent()|父节点 firstChild()|长子 nextSibling()|兄弟 insert(i, e)|将e作为第i个孩子插入 remove(i)|删除第i个孩子及其后代 traverse()|遍历 ### 5.3.1 双亲表示法 不利于查找孩子节点或兄弟节点。 ```cpp #define MAX_TREE_SIZE 100 typedef int TElemType; typedef struct PTNode { TElemType data; // 节点数据 int parent; // 双亲位置 } PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; // 节点数组 int r, n; // 根的位置和节点数 } PTree; ``` 可以添加一个长子域域来体现孩子关系,添加右兄弟域来体现兄弟关系,但仍然不方便 。 rank|data|parent| --|--|-- 0|A|-1 1|B|0 2|C|0 ### 5.3.2 孩子表示法 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210706212436365.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 5.3.3 双亲孩子表示法 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210706212708663.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 分析:即便这样查找双亲和孩子都比较方便,但各children的子数据集大小悬殊很大,总体规模为边的数量n-1,则每个children的子数据集的平均规模为$O(1)$,可否借助此性质简化表示方法? ### 5.3.4 孩子兄弟表示法 二叉树来了,规整性突出。 观察每个节点的不变性。 每个节点均设两个引用: - 纵:firstChild() - 横:nextSibling() ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210706214803361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp typedef struct CSNode { TElemType data; struct CSNode *firstChild, *nextSibling; } CSNode, *CSTree; ``` ## 5.4 二叉树 ### 5.4.1 二叉树 高度增长缓慢,宽度增长爆炸。 因为每个节点的度最多为2,所以 - 深度为k的节点,至多$2^k$ - $h BinNodePosi(T) BinNode::insertAsLC(T const &e) { return lChild = new BinNode(e, this); } template BinNodePosi(T) BinNode::insertAsRC(T const &e) { return rChild = new BinNode(e, this); } template int BinNode::size() { // 后代总数 int s = 1; if (lChild) s += lChild->size(); if (rChild) s += rChild->size(); return s; } ``` ### 5.5.3 BinTree类 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210717164310620.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 5.5.4 高度更新 ```cpp #define stature(p) ( (p) ? (p)->height : -1) template int BinTree::updateHeight(BinNodePosi(T) x) { return x->height = 1 + max(stature(x->lChild), stature(x->rChild)); } // 若v更新了高度,那么它的祖先高度也会变化 template void BinTree::updateHeightAbove(BinNodePosi(T) x) { while (x) { updateHeight(x); x = x->parent; } } ``` ### 5.5.5 节点插入 ```cpp template BinNodePosi(T) BinTree::insertAsRC(BinNodePosi x, T const & e) { _size++; x->insertAsRC(e); updateHeightAbove(x); return x->rChild; } ``` ## 5.6 先序遍历 ### 5.6.1 转化策略 利用已有轮子,通过**遍历**将半线性结构转化为线性结构。 ### 5.6.2 遍历规则 根节点在次序中的位置。 先序:根-左-右 层次(广度):自上而下、先左后右 ### 5.6.3 递归实现 ```cpp template void traverse(BinNodePosi(T) x, VST & visit) { if (!x) return; visit(x->data); traverse(x->lChild, visit); traverse(x->rChild, visit); } // T(n) = O(1) + T(a) + T(n-a-1) = O(n),渐进的,可以改进 ``` **观察:** 递归处于整个程序的尾部,称作尾递归,非常容易化解为迭代的形式。 ### 5.6.4 迭代实现1 引入**栈**。 注意压栈的次序。 ```cpp template void travPre_I1(BinNodePosi(T) x, VST & visit) { Stack S; if (x) S.push(x); while (!S.empty()) { x = S.pop(); visit(x->data); if (HasRChild(*x)) S.push(x->rChild); if (HasLChild(*x)) S.push(x->lChild); } } ``` 缺点:不容易推广至中序及后序遍历算法。 ### 5.6.5 迭代实现2 **观察:** 对于任何一棵子树,都是沿着左侧链访问,再自下往上遍历右孩子 ```cpp template // 使用static修饰,不必担心与其他文件中的函数同名,和全局变量类似,不会发生冲突 static void visitAlongLeftBranch( BinNodePosi(T) x, VST & visit, Stack data); S.push(x->rChild); x = x->lChild; } } template void travPre_I2(BinNodePosi(T) x, VST & visit) { Stack void traverse(BinNodePosi(T) x, VST & visit) { if (!x) return; traverse(x->lChild, visit); visit(x->data); traverse(x->rChild, visit); } ``` ### 5.7.2 迭代 观察:当节点接到控制权后,不首先访问自己,而是将控制权转交给它的左孩子,访问完左孩子后,访问左孩子的右孩子,再访问自己。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2021071720133566.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp template static void goAlongLeftBranch(BinNodePosi(T) x, Stack & S) {while (x) {S.push(x); x = x->lChild;}} template void travIn_I1(BinNodePosi(T) x, VST & visit) { Stack S; while (true) { goAlongLeftBranch(x, S); if (S.empty()) break; x = S.pop(); visit(x->data); x = x->rChild; // 当访问完一个节点及它的左孩子时,栈顶元素为该节点的祖先 } } ``` ## 5.8 后序遍历 ### 5.8.1 递归 ```cpp void traverse(BinNodePosi(T) x, typename VST) { if (!x) return; traverse(x->lChild, visit); traverse(x->rChild, visit); visit(x->data); } ``` ### 5.8.2 迭代 ```cpp template static void gotoLeftmostLeaf(Stack & S) { while (BinNodePosi(T) x = S.top()) if (HasLChild(*x)) { if (HasRChild(*x)) S.push(x->rChild); S.push(x->lChild); } else S.push(x->rChild); S.pop(); } void travPost_I(BinNodePosi(T) x, VST & visit) { Stack S; if (x) S.push(x); while (!S.empty()) { if (S.top != x->parent) gotoLeftmostLeaf(S); x = S.pop(); visit(x->data); } } ``` ### 5.8.3 表达式树 逆波兰表达式等效为后序遍历,数字为叶子,双亲为运算符,运算优先级为后序遍历次序。 ## 5.9 层次遍历 有根性:垂直 有序性:水平 自上而下、自左向右,顺序 ```cpp void BinNode::travLevel(VST & visit) { Queue Q; Q.enqueue(this); while (!Q.empty()) { BinNodePosi(T) x = Q.dequeue(); visit(x->data); if (HasLChild(*x)) Q.enqueue(x->lChild); if (HasRChild(*x)) Q.enqueue(x->rChild); } } ``` ## 完全二叉树 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2021071814454218.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) # 5.10 重构 由遍历序列还原树。 先序+后序不可以,但是在真二叉树的条件下是可以的。 ```cpp #include #include typedef struct BinTree { int key; BinTree* lChild; BinTree* rChild; }BinTree; int arrayFind(int* A, int begin, int end, int key) { for (int i = begin; i < end; i++) if (key == A[i]) return i; return -1; } BinTree* reconstBinTree( int* preOrder, int pbegin, int pend, int* inOrder, int ibegin, int iend) { if (pbegin >= pend || ibegin >= iend) return NULL; BinTree* root = new BinTree; *root = { preOrder[pbegin], NULL, NULL }; int r = arrayFind(inOrder, ibegin, iend, preOrder[pbegin]); root->lChild = reconstBinTree(preOrder, pbegin + 1, r - ibegin + pbegin + 1, inOrder, ibegin, r); root->rChild = reconstBinTree(preOrder, r - ibegin + pbegin + 1, pend, inOrder, r + 1, iend); return root; } void travPre(BinTree* t) { if (!t) return; printf("data is %d\n", t->key); travPre(t->lChild); travPre(t->rChild); } int main() { std::cout << "Hello World!\n"; int PreOrder[] = { 43, 12, 8, 32, 16, 35, 78, 56, 88, 83, 121, 97 }; int InOrder[] = { 8, 12, 16, 32, 35, 43, 56, 78, 83, 88, 97, 121 }; BinTree* root = reconstBinTree(PreOrder, 0, 12, InOrder, 0, 12); travPre(root); return 0; } ``` # 5.11 Huffman树 无前缀冲突编码 叶子通路唯一=>解决编码句读问题。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210718160117670.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 如何构造编码树,使得文件最小呢?=>最优编码树 使叶子只在最后两层,否则,交换节点。 还要考虑出现的频率,带权编码:将频次高的尽可能放在高处。 使用贪婪策略: 1. 为每个字符创建一颗单节点的树,组成森林F 2. 按照出现的频率,对所有树排序 3. while (F中的树不止一棵) 取出频率最小的两棵树$T_1$和$T_2$ 将它们合并成一棵新树$T$ 这棵新树的频率为两棵子树频率之和,再插回有序森林中 - 阅读全文 -
数据结构与算法 4. 栈与队列 2021-07-06 浏览量 574 暂无评论 [TOC] ## 4.1 接口与实现 特殊的线性结构。 push, top, pop 实现:借助向量或列表 ```cpp class Stack: public Vector { public: void push(T const & e) {insert(size(), e);} T pop() {return remove(size() - 1);} T & top() {return (*this)[size() - 1];} }; ``` 应用场合 - 逆序输出 - 递归嵌套 - 延迟缓冲 - 栈式计算 ## 4.2 逆序输出--进制转换 商+余数,逆序输出余数 ```cpp void convert( Stack & S, __init64 n, int base) { static char digit[] = {'0', '1', '2', '3', '4', '5', '6', '7'}; while (n > 0) { S.push(digit[n % base]); n /= base; } } main() { Stack S; convert(S, n, base); while (!S.empty()) printf("%c", S.pop()); } ``` ## 4.3 递归嵌套--括号匹配 ```cpp // 假设只有(),没有其他字符 bool paren(const char exp[], int lo, int hi) { Stack S; for (int i = lo; i < hi; i++) if ('(' == exp[i]) S.push(exp[i]); else if (!S.empty()) S.pop(); else return false; // 右括号缺失对应的左括号 return S.empty(); // 左括号缺失对应的右括号 } ``` 可扩展至多种类型括号,在弹出时检查当前右括号是否与栈顶的左括号匹配。 ## 4.4 栈混洗 按某种顺序,移动栈中的元素。 只允许: - 将A的顶元素弹出并压入S - 将S的顶元素弹出并压入B **计数** 一个长度为n的栈的栈混洗总数为$SP(n)=\sum_{k=1}^{n}{SP(k-1)xSP(n-k)}=catalan(n)$ ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210706093301949.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) **如何判断一个排列是否为一个序列的栈混洗:** 观察:任意三个元素能否按某相对次序出现与混洗中,与其他元素无关。 > 对于任何$1<=i 第一个是从顶到底,第二个是从底到顶,因为这样一来,栈底元素相同,只能有一种顺序 1. 枚举并判断i,j,k,$O(n^3)$ 2. 枚举并判断i,j,j+1,$O(n^2)$ 3. 利用栈,$O(n)$ 模拟混洗过程,每次S.pop()之前,检测S是否已空;或需弹出的元素在S中,却非顶元素。 ```python for k in B: while (S.empty() or k!=S.top()): if A.empty(): return False S.push(A.pop()) if (k in S) and (k!=S.top()): return False return True # 更正 while len(A) > 0: S.append(A.pop()) if B[0] in S and S[-1] != B[0]: print(False) while len(S) > 0 and S[-1] == B[0]: S.pop() B.pop(0) print(True) ``` **合法的栈混洗与合法的括号匹配存在一一对应关系。** ![在这里插入图片描述](https://img-blog.csdnimg.cn/202107061058285.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 4.5 延迟缓冲--中缀表达式 不能保证处理的速度和读取的速度同步,所以要缓冲。 求值算法 = 栈 + 线性扫描 两个栈:一个栈用来存放操作数,一个栈用来存放操作符 ```cpp float evaluate(char* S, char*& RPN) { stack opnd; stack optr; optr.push('\0'); while (!optr.empty()) { if (isdigit(*S)) {readNumber(S, opnd); append(RPN. opnd.top();} else switch (orderBetween(optr.top(), *S)) { case '<': optr.push(*S); S++; break; case '=': optr.pop(); S++; break; case '>': { char op = optr.pop(); append(RPN, op); if ('!' == op) opnd.push(calcu(op, opnd.opo())); else { float p0pnd2 = opnd.pop(), p0pnd1 = opnd.pop(); opnd.push(calcu(p0pnd1, op, p0pnd1)); // why not opnd.push(calcu(opnd.pop(), op, opnd.pop())); // 顺序问题 } break; } default: exit(-1); } } return opnd.pop(); } void readNumber(char* & p, stack& stk) { stk.push((float)(*p - '0')); while (isdigit(*(++p))) stk.push(stk.pop() * 10 + (*p - '0')); if ('.' != *p) return; float fraction = 1; while (isdigit(*(++p))) stk.push(stk.pop() + (*p - '0') * (fraction /= 10)); } Operator optr2rank ( char op ) { //由运算符转译出编号 switch ( op ) { case '+' : return ADD; //加 case '-' : return SUB; //减 case '*' : return MUL; //乘 case '/' : return DIV; //除 case '^' : return POW; //乘方 case '!' : return FAC; //阶乘 case '(' : return L_P; //左括号 case ')' : return R_P; //右括号 case '\0': return EOE; //起始符与终止符 default : exit ( -1 ); //未知运算符 } } char orderBetween ( char op1, char op2 ) //比较两个运算符之间的优先级 { return pri[optr2rank ( op1 ) ][optr2rank ( op2 ) ]; } ``` ## 4.6 逆波兰表达式(Reverse Polish Notation) 又称为后缀式。 不使用括号,即可表示带优先级的运算关系。 infix到postfix手工转换 操作数的相对位置不会改变,操作符的相对位置可能改变。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2021070616150694.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 代码实现结合evaluate,只在两种情况下将当前字符添加至RPN末尾: 1. 数字 2. 当前操作符可立即执行 ## 4.7 队列接口与实现 队尾插入(查询):enqueue、rear 队头删除(查询):dequeue、front ```cpp template class Queue: public List { public: void enqueue(T const & e) {insertAsLast(e);} T dequeue() {return remove(first());} T & front() {return first()->data;} T & rear() {return last()->data;} } ``` - 阅读全文 -