数据结构的提炼与压缩

null数据结构的提炼与压缩数据结构的提炼与压缩上海市上海中学 曹钦翔 指导教师：上海市上海中学 毛黎莉数据结构的“化繁为简”数据结构的“化繁为简”减少存储规模 化简存储结构时空复杂度降低 处理方式多样“化繁为简”的三种手段“化繁为简”的三种手段提炼：忽略无效信息，减少存储规模 压 ：调整存储方式，化简存储结构 缩 ：合并重复信息，减少存储规模 1.二维结构的化简1.二维结构的化简问题一：Ural 1568 Train car sorting 问题描述：对于一个序列{an}，定义一种操作，将{an}分成两个子列，把其中一个置于另一个前面，得到一个新的序列。现给出一个序列（这个序列是1到n的一个排列），求一种，通过最少的操作次数是它变成升序序列。一个操作的例子一个操作的例子5 3 2 4 15 4 3 2 15 3 2 4 1算法算法（5，3，2，4，1）优化数据结构优化数据结构朴素实现，单次操作复杂度O(n2)。需要优化零元素过多，形成冗余提炼：忽略零元素问题二：CEOI 2007 Day 2 Necklace 问题二：CEOI 2007 Day 2 Necklace 问题描述：要求编译一个库，能够对若干已知的整数串进行两个操作： （1）在某个已知串的左端或右端增加或减少一个元素，得到一个新的已知的串。 （2）输出某个已知串的最左端或最右端的数。 在问题的一开始，只有一个已知的串：空串。分析朴素：每个串分别储存——复杂度过高，难以承受大量重复信息，空间严重浪费缩：合并重复信息两个特例两个特例星形 链形 特例存储方式数据结构:Left-Right Tree数据结构:Left-Right Tree添加新结点添加新结点删除结点删除结点转化结论转化结论已知树中某链的两端点，求底部端点的父亲 已知树中某链的两端点，求顶部端点在链中的儿子 2.树形结构的化简2.树形结构的化简问题五：问题二的遗留问题 问题描述：给定一棵有根树，在线回答两种询问： （1）已知树中某链的两端点，求底部端点的父亲 （2）已知树中某链的两端点，求顶部端点在链中的儿子分析分析提炼：后代信息成为冗余，不再储存转化：顶结点的儿子底结点的超级祖先数据结构:Supper Father数据结构:Supper FatherSu(x,0)Su(x,2)Su(x,1)用Su(x,k)示结点x的第2k代祖先3.图结构的化简3.图结构的化简问题六：ural 1557 Network Attack 问题描述：给定一个无向连通图，若从中删去两条边能使它不连通，求所有这样的方案的总数。图点数n边数m。 分析分析核心问题：图结构复杂不易处理关键信息：连通性压：以图的DFS树为解题突破口两种情况两种情况只有两条边： 一树边一回边只有两条边： 两条树边XXYYZ小结小结因题而易，用好“三大手段” 提炼：忽略无效信息，减少存储规模 压 ：调整存储方式，化简存储结构 缩 ：合并重复信息，减少存储规模 谢谢谢谢算法算法原序列的最简母矩阵中偶数行的非零元素，形成一个子列，前置。 原序列的最简母矩阵中奇数行的非零元素，形成一个子列，后置。 形成新序列。 不断重复，直到的到升序列。2.树形结构的化简2.树形结构的化简问题三：浙江2007年省选 捉迷藏 问题描述：给定一棵树，每个节点要么是黑色，要么是白色，能执行一个操作：把某一个点取反色。动态维护并返回树中距离最远的黑色点对。 分析分析问题类型：局部参数调整+整体属性返回 解题障碍：树形结构不易整体处理压：线性结构存储“点对距离”数据结构:括号编码数据结构:括号编码[A[B[C][D][E]]][A[B[C][D]][E]][ [ [ ] [ ] ] [ ] ]数据结构:括号编码数据结构:括号编码存储方式：]]（）[ ——〉]][ ——〉（2，1）结论：对于两个点PQ，如果介于某两点PQ之间编码S可表示为(a,b)，PQ之间的距离就是a+b。数据结构:括号编码数据结构:括号编码对于（a,b)=(a1,b1)+(a2,b2) a+b=a1+b2+|a2-b1|=a1+b2+Max{a2-b1,b1-a2} =Max{(a1+a2)+(b2-b1),(a1-a2)+(b1+b2)}数据结构:括号编码+线段树数据结构:括号编码+线段树维护以下变量 dis(s) ： {a+b|S’(a,b)是S的一个子串，且S’介于两个黑点之间} right_plus： max{a+b|S’(a,b)是S的一个后缀，且S’紧接在一个黑点之后} right_minus： max{a-b|S’(a,b)是S的一个后缀，且S’紧接在一个黑点之后} left_plus： max{a+b|S’(a,b)是S的一个前缀，且有一个黑点紧接在S之后} left_minus： max{b-a|S’(a,b)是S的一个前缀，且有一个黑点紧接在S之后} 数据结构:括号编码+线段树数据结构:括号编码+线段树利用以下实现合并：S=S1+S2，其中S1(a,b)、S2(c,d) dis(S)=max{right_plus(S1)+left_minus(S2)，right_minus(S1)+left_plus(S2)，dis(S1)，dis(S2)} right_plus(S) =max{right_plus(S1)-c+d,right_minus(S1)+c+d,right_plus(S2)} left_plus(S) =max{left_plus(S2)-b+a,left_minus(S2)+b+a, left_plus(S1)} right_minus(S)=max{right_minus(S1)+c-d,right_minus(S2)} left_minus(S)=max{left_minus(S2)+b-a,left_minus(S1)} 问题三小结问题三小结关键点1：树形变线形，为使用线段树创造条件。关键点2：数对表编码，沟通整体部分关系。最简母矩阵最简母矩阵称一个p*q的矩阵A为序列{an}的母矩阵，当且仅当，矩阵A中的所有非零元素，自上到下自左到右逐列读出得到{an} ，自左到右自下到上逐行读出得到升序序列。 称序列{an}的所有母矩阵中，行数列数都最小的那个矩阵为序列{an}的最简母矩阵。最简母矩阵最简母矩阵（5，3，2，4，1）的最简母矩阵53421——原序列53421——升序序列DFS VS BFSDFS VS BFS其一：性质上（结构决定性质），DFS遍历后的可以得到DFS树，图中的边在DFS树中要么是树边要么是回边；而BFS遍历后往往得到层状结构，图中的边要么连接同一层中的两个点，要么连接相邻两层的两个点。 其二：用途上（性质决定用途），DFS能较有效解决与连通性相关的问题（因为任意一棵子树只与它的祖先相联）；BFS能较有效解决与点对距离相关的问题（由前面的性质，两点的距离，与所在层数密切相关）。