Posted Updated Coursean hour read (About 7726 words)

2021秋季学期 形式语言与自动机 期末复习

丢失图片，没有渲染后的pdf版。。。

FLA Final Review

Slides Review

lect1

  • 字母表，形式符号的非空有限集合

  • 字符串或字

  • 字母表的0次方为{epsilon}，递推定义image-20220104212613395

  • 语言：任何字母表星闭包的子集

  • 证明：逆否证明，反证、互归纳，提出多个原子命题互相证明，一般具有某正对称性和推论关系

  • 归纳定义：基础、归纳递推规则、极小声明

lect2

  • 上下文无关文法 T V S P 自下而上递归推理叫归约，自上而下叫推导

  • 推导传递闭包，通过归纳定义，递归基是自己推自己 最左：总是替换最左非终结符，推导加*

  • 句型：能够由S推出来的状态，有左右句型之分，全是终结符叫句子

  • def 上下文无关文法的语言为上下文无关语言

  • 构造：对称拆分不等关系变大于小于 控制范围的可以两边夹

  • 计数题：找唯一分割点 count a=b S->aSbS|bSaS|epsilon 差2的找轴点切分 计数不等于：第一次a比b多停下，前面相等，中间a，后面a不少于b（通过可以单增a实现

  • 证明文法和语言等价：归纳w的长度和推导步数（讨论第一步所使用的产生式）

  • 经常互归纳一些中间状态的含义。。image-20220105095015925

  • chomsky 0：图灵机 α推β α中至少一个非终结符

  • 1 α长度小于等于β（可以S推epsilon） S不出现在任何P右边 上下文有关 线性有界自动机

  • 2 一个非终结符号推β 上下文无关 下推自动机

  • 3 A推aB 或者A推a 正规文法 正规语言 有限状态自动机

  • 语法分析树，内部非终结 叶子可终结可不终结or空 产生式是父子关系 果实是连接叶子的句型

  • 可归约 存在推导 存在最左 存在最右 存在根节点A分析树果实为w 等价

image-20220105095722168

归约：归纳步数讨论其最后一步产生式（其实为推导的第一个产生式）

归纳分析树的高度，递归的时候归纳第一层的产生式 证明推导到归约 归纳于步数

image-20220105100046970

二义性文法：对某个w存在两颗不同的分析树or存在两个不同的最左推导，二者等价

不可判定的，不存在算法

如果语言的所有文法都是二义的，则L是固有二义的 什么是最左推导？

image-20220105101009429

image-20220105101200757

lect3

  • 正规表达式的语言是正规语言 可以联合并集+ 连接· 星闭包

  • 定义正规表达式集合：字母表都是，空字符和空集都是，变量（可以包含任意的其他变量和递归基础符号和字母）都是 归纳：可+ 接 星闭包和括号

    ？是空+L L零次方为空字符

    定义正规语言 {epsilon}和空语言是正规的，单字母正规，正规之间的并 接和星闭包正规

  • 设计时一定考虑边界情况，讨论结尾，关注长度限制！空，单0单1等等 利用空字符达成位置的位移“前x位至少包含x个1”

  • 代数定律：语言之间的运算可以直接全部替换成简单符号表达式。

image-20220105103024411

image-20220105103035952

应该不考的证明。。

推论：image-20220105103134051

应用：证明语言运算之间的代数定律直接用具体字符替换之后证明即可

lect4

  • 有限状态自动机PDA 状态集、输入符号集、转移函数、开始态、终态集合

  • 记得转移图、转移表上标Start、箭头，终态双圈、星号 对每个状态都要有全部的接受符号转移

  • 这里的转移函数只有q和a=新q，拓展到多步a变w。定义拓展时候w=xa拆开的最后一个符号

  • 可以证明DFA的语言是正规语言：一般可以互归纳证明中间状态的含义，从初态到某个状态当且仅当转移函数的w包含，需要证两个方向。。

  • 构造PDA：不包含就把包含的终态调换，箭头调换为回文，设置垃圾桶节点

  • 非确定自动机NFA，可以转多个或不转，转移函数的值是状态集合，扩展转移函数是所有可能在的状态尝试转移之后再并集。所以w转移之后与F交不为空即可接受。

  • 设计：随时都可以尝试xxx

  • NFA DFA的等价性：D转N把每个转移函数的结果都加上{}变成集合 两者都是归纳于字长

    N转D 子集构造法 一定想着标记开始和结束。从起始状态开始走到哪写哪。意义在于可能到达的状态，正确性证明：任意w代入初态开始的转移函数在两个自动机中得到的值都一样。最坏2^n个状态

  • 文本搜索的NFA和转DFA规则？？借题复习

  • 带空转移的NDA，可以用转移图、转移表表示 特殊的空闭包ECLOSE就是自己和自己空转移的可达状态，转移函数则为每一步都要ECLOSE闭包，算的时候闭包和转移间隔着算

  • 语言：仍然和DFA等价：DFA转空NFA—没有空转移则但可接受空字符到自己，每一个转移函数结果变为集合 空NFA转DFA：自己构造法，每一步都需要做闭包。证明正确性归纳于字长：image-20220105133613383

  • image-20220105133905696

  • 构造空NFA处理那种“前几个里面至少有一个x” 合理运用空转移等价于(0+1+epsi)^x

  • 特定子串情况时尤其考虑好子串的重叠

  • 填表法确定状态偶对，如果状态可区别则其共同前驱可区别，先区别所有终态非终态。之后看表的疏密程度选择由转移表填图还是按图找转移表。在题目里面复习image-20220105134748736

  • 优化DFA：删除不可达，填表找偶对，删除该删除的等价类只保留一个，构造

lect5

  • 证明DFA是正规语言：给DFA转re和RE转空NFA

  • Thompson构造：相加：左边两空右边两空，新增两个状态四条边

    拼接：新增一条空转移边

    星闭包：画飞碟上回下进，新增四条空转移和两个新状态

  • DFA转RE：KLEENE构造和路径消去

    • Kleene：计算Rkij，k=0为中间不经过任何节点，不同节点没弧线为空集，有弧线为a，多条相加 ij相同空加所有a

      迭代Rkij在k！=0时候：一步过不经过k和经过k转几圈再过去

    • 状态消去：消去两入两出带自环的中间态：到该节点转几圈过去，对每一个终态都消到只剩下该终态以及初态。最后要么剩两个要么剩一个。剩一个就是自环的星闭包，剩两个就是（自转+过去转几圈回来）*过去在终态转圈* 这两种都是n^3 * 4^n的复杂度

Lect6

  • Pumping 用来证明不是正规语言

    pumping特性，任何一个长度不小于状态数目的字符串所标记的路径上必然出现重复状态，n长度涉及n次转移共n+1个状态。

    引理：正规语言L，存在常数n>=1，使得任意长度不小于n的字符串w在L中，都可以分成三个部分满足以下条件：y不是空，xy小于等于n，对任何k>=0都有xykz在L中

    证明不是正规语言：如果是正规语言，则存在一个n，随便取一个长度大于等于n的串，证明其任意符合y非空，xy<=n的分割，都没有xykz一定属于L

  • 一些判定算法

    • 判定是否非空：DFA递推求出所有可达状态，若包含任何终态则非空 RE 特殊的空语言的0次方应该是空语言 根据正规的四种运算从小的判定起，复杂度On
    • 判断是否包含特定字符串：DFA：处理看在不在终态，NFA转化DFAor处理看集合中有没有终态 RE：转化空NFA执行
    • 判定两个正规语言相等：都转DFA之后重命名使之不重名，两个相并，终态仍终态，转移边不变。取任何状态为初态？？填表算法看原来的初态是否可区别 On4可降On2

  • 正规封闭运算：并星闭包连接都可以由RE证明

    补：也是正规语言，DFA的所有终态和非终态对调即可

    交：也是正规语言，就是L补并上M补再整体取补orDFA：使用状态的笛卡尔二元积，image-20220105142336532

  • 差：也是正规语言，是M取补再和L交

  • 反向：也是正规语言：分别对RE中的三个基础（空语言 空字符和单字符）四种运算证明or构造DFA把转移弧反向，初态为终态，所有终态空字符连接至超起点

  • 同态：正规语言同态后依然是正规语言 这个T*是嘛玩意？ image-20220105142747528

  • 归纳证明于RE的三个基础与四种运算image-20220105142854777

  • 反同态w为什么不直接是字母表而是星闭包？？仍然也是正规语言，用DFA证明：image-20220105143545409

构造一个状态集合以及始末都相同的DFA B，字母表改成h的定义域表，转移函数为这边的a是那边的h（a）构造好DFA即可，可以归纳与w字长证明正确性 q0经过w==q0经过h（w)

构造反同态dfa相当于构造原集合的转移，先按字母表讨论再去DFAA中找这条路径能到哪

Lect7

  • Push Down Automaton PDA带有堆栈的有限状态自动机 七元组{状态集合，接受字符，堆栈符号，转移函数，起始状态，开始堆栈符号，终态集合} 其中状态转移可以接受epsilon，不用给全所有可能（默认不写的转移函数值为空集），但栈顶和输入符号确定时值唯一

    状态转移函数接受δ（状态、字符、栈顶）=状态+栈顶 新压入的放左边（左边栈顶）

  • ID表达格局（q，w，γ）状态，剩余串和栈内容 定义ID推导关系image-20220105152652801

  • 定义自反传递闭包* ，自己推自己，且可传递。。 这里可以归纳于步数证明，自反传递闭包的推导中字符后面带东西和栈底有东西都不影响

  • 终态接受语言：ID处理完w后能到终态，栈无所谓

    空战接受语言：ID处理完能到空栈，可以不规定终态

  • 从空栈到终态：新增栈底元素X0，增加超起点用来压入原空栈的栈底元素并进入空栈PDA的起始点。对空栈PDA的每个状态都增加一个空转移可以把新栈底元素无偿弹出成空连接到超收点。

    相当于：在原来空栈接受的栈低下垫了一层新的栈底元素，原来的栈只要空了就有机会从任意状态直接弹出新栈底干到终态去。

  • 从终态到空栈：同样增加新的栈底元素，新起点连接老起点负责压入原栈底，在每个终态都可以直接空转移弹出所有到超收点。超收点也是无条件空转移弹出所有栈元素

  • 构造PDA：“任意前缀中a至少是2倍b：a压1个b弹两个才能回来image-20220105154144136

  • a数目和b数目的累计：记录栈中是a多还是b多多几个，a每多一个栈多一个X，b Y，b遇到X弹出…… 最后要求栈里面不空就空字符+X（Y)才能转到终态。

  • a=b且不含连续c：处理连续c—不入栈但把状态拐出去下一个一定得是a或者b

    思考：对于计数来说多用栈解决，对于正规就能搞定的连续之类的问题多用状态（包括压栈时候的一些二倍关系）搞定。最后检测栈里面必须只剩下Z0

  • 可以一次性压入两个但是不能弹出两个，因为只能更换栈顶那L7P23压两个不行吗？

  • 三个阶段的时候比如一定是若干a若干b若干c，阶段间转移建议用空字符+不变栈顶 为了表示“随时可以开始下一阶段”比如判断回文，不知道中点的时候需要尝试

lect08

  • 从CFG到EPDA

    一个状态，接受Terminals，栈里面非终结终结都有，开始符号就是栈底元素

    所有的产生式都是空转移读栈顶替换成新的，所有的终结符都可以与栈顶对应之后消掉。非终结符只处理栈，终结符的处理字符串同时消栈直到非终结符在栈顶

    “PDA的转移函数右端可以是个集合有多个不同结果吗？？？空字符看来一定可以，具体字符呢？”

    证明正确性：归纳于最左推导的步数n ，讨论第一步所用的产生式

    归纳于ID推导的步数n，讨论第一步产生式

  • 从EPDA到CFGimage-20220105161032888

image-20220105160957763

  1. 初态能到任何[初态，栈底符号，any状态]

  2. 对原PDA中任何产生式，都有[p X pk]–>a[q X1 any] [any X2 any]…… [any Xk pk] 每个转移函数对应：新栈顶*状态总数

    特别的 弹出操作新栈顶为epsilon时only a on right

    特别的 新栈为空+转移字符为空时候左边为空

    证明正确性：image-20220105163605434image-20220105163615022image-20220105163625493

LEct9 确定下推自动机

  • 默认是终态接受的DPDA 确定的栈顶、字符转移函数的值只有一个元素即集合只有一个元素但仍为集合+如果有非空字符的转移则不能有相同状态相同栈顶的空转移

  • 判断回文的经典自动机DPDA的话中间得有个标志，不然没法实现“随时都可以尝试进入下一阶段的处理”中的随时。但是虽然确定也不用每个状态写满

    结论：正规语言一定存在DPDA的表示，从对应的DPA继承过来即可，可以对w的字长归纳证明image-20220105164151822

    归纳时候拆成了w=x a ，先用归纳假设干掉x之后 根据继承产生式干掉a

  • DPDA的能力强于DFA 如WcWR不是正规语言（by pumping）

  • 前缀性质：不存在互异的x y串在L中且x是y的前缀 L$一定具有前缀性质

  • 一个语言L是某个空栈接受的EDPDA P的语言 iff L具有前缀性质且是某个FDPDA P‘ 的语言？比如经典的回文，具有前缀性质且L是某个DPDA的语言，则L也一定是某个空战接受的EDPDA的语言

  • 存在上下文无关语言不是任何DPDA的语言（确定的上下文无关语言）不需证明 例： WWR

  • 语言是空栈接受的DPDA的语言时L存在一个无二义文法（参考空栈PDA构CFG的方法，且有唯一的最左推导。。）

  • L是某个DPDA P的语言则L存在一个无二义的文法

    Proof：使用L$构造一个具有前缀性质的语言，根据上一性质得到无二义的G’，把$作为非终结符加上产生式$推epsilon

  • 由上两条：固有二义语言不是任何DPDA的语言 但是也有非固有二义语言不是任何DPDA的语言比如WWRimage-20220105165431985

Lect 10 CFG简化与chomsky范式

  • 符号（包括V和T）：生成符号（能推出w）、可达符号 （能被S推出的一部分）在一起是有用符号？不一定，可能有一个生成又可达的但是和一个无用绑定在一起被生成，为无用符号

    消去所有非生成 再消去所有非可达，就剩下都是有用且与原文法等价。计算生成，删除，计算可达，删除。

    如何计算生成符号？所有T都是生成符号，如果右面都生成则前面的A一定生成。不重不漏Proof？

    计算可达？S可达，左面可达则右面所有皆可达 不重不漏 Proof？

    可以为了简洁把V换名字

  • 消去epsilon产生式，可致空符号能推导出epsilon：基础，右边都是可致空则左边也是 不重不漏 先计算所有可致空符号 在可致空符号出现的地方讨论其出现或者不出现。特别的，单推空的直接删去。这样的与原来相比不能产生epsilon别的不受影响4

  • Unit产生式 A-》B unit偶对当且仅当A能在*步推出B且该推导只使用了unit产生式 需要计算所有unit偶对：每个字母和自己一定是unit偶对；如果AB是偶对，B-》C则AC也是偶对。不重不漏

    计算偶对；对每个偶对找到最后那个非偶对的V比如A-》B B-》α 则加入A-》α删去unit产生式

    但是保留B推α，可能产生不可达！ 最后在偶对的推导链上把前面的都连到最后一个

  • 简化CFG：消除空产生式、消除Unit产生式、消除非生成符号、消除非可达符号。这样的与原G只差空字符

  • Chomsky范式：任何不含空字符的非空上下文无关语言都存在一个CFG G产生式只有两种：一推二非终结符、非终结符推终结符。这样的文法叫做。。。

    对前文的工作（右边长度1的只有终结符）之后再：

    1. 如果有非终结符a出现在右边长度大于1的，则引入新的非终结符替换掉，并加上A->a 至此右边长度大于1的产生式只有非终结符

    2. 对于右边长度大于2的采用级连cascade方法转变为——对A推出k个，引入k-2个新V替换掉

      实质上是对此在二叉化。。 与原L只差空字符

  • CKY算法：判断某个串 属于某个CFG和分析树image-20220105194206387

    先左再上，手指指着更新的时候（紧下列向下滑，右下向左上滑）

Lect 11 上下文无关语言的计算

  • Pumping引理：设非终结符数量m，取字长不小于n=2^m的字符串z，考察其分析树：

    CNF后为二叉，叶节点为n个，则h-1>=log2,|z|>=m，设从根节点S的一条最长路径S A1……Ak 至少为m+1 必有重复节点在A这条路中。划分为uvwxy，image-20220105195058905则一定可以pump v和x，其i次方都应该合格

    理解为某个广义产生式（推导关系）可以递归

    Lemma：存在正常数n，使得任意长度不小于n的字符串z在L内，都可以分成uvwxy五部分且满足：vx不空，|vwx|<=n 对任何k>=0 都可以pump v与x

  • 用来否定

    1. 假设是CFG，则存在一个整数n满足pumping引理，取一个串>n
    2. 讨论符合规则的五段划分，证明其都不能pump起来（都存在一个pump次数k使得串不再是L中）

  • 判定CFL是否为空：计算生成符号之后看S在不在，On方降On

  • 判定是否包含特定字符串：chomsky之后CKY On3

  • 不可判定问题：无二义？固有二义？两个CFG相交为空？相等？给定CFG是否是字母表*

  • 封闭运算

    • 替换：如果任何字母表中的a，s（a）是CFL且L是CFL则替换后s（L）也是上下文无关。

      证明：分析树每个叶节点a替换成s（a）的分析树

      映射每一种字母表中字符到一个语言称为替换，可以替换a，w（拼接替换字符）甚至L（w的替换并集）

    • 并：两个CFL并也是CFL 替换{0,1}中0为L1,1为L2 ，即得

    • *闭包和+闭包：都是CFL 也是替换掉{1*}中的1为L则得

    • 连接：{01}分别替换为L1 L2

    • 同态：替换s（a）={h（a}}，则s（L)=h（L)

    • 反向：L是则LR也是（每一个都Reverse），证明：构造G后尝试构造G’

      产生式中每个右端都reverse掉，这样的G‘就是LR 归纳于推导长度证明？

    • 交 补 差 都不一定 交出0^n 1^n 2^n后不是CFL但是n n i 和 i n n都是

    • CFL与RL正规语言的交一定是CFL 、

      根据DFA和FPDA构造image-20220105202626364

    • 反同态仍然是CFL：image-20220105202714752

Lect 12 Turing Machine

  • 基本图灵机：带与带头，空白符B 七元组{状态集合，接受字符集合、带符号集合、转移函数集合、开始状态、空白符、终态集合} 转移函数为偏函数从状态和带符映射到状态、带符和方向

  • ID表达格局：带头表示为当前状态，后面是正在扫描的单元格cell 前后需要空白之中的符号串但是也可以有B串

  • ID推导，特殊的可以往两边推，如果带头到了B上则写B，如果把最右/左端写成B则可以省略

  • 一般计数的思想为匹配：从左往右跑一趟就是匹配了一组数，再回去再跑。。

  • 可被图灵机接受的是递归可枚举语言REL 定义TM的语言是使得q0w 推出 终态的串w集合

  • halt：不存在下一个移动，与原来的图灵机语言相通但是接受w之后停机不再移动。总是假定图灵机到达终态之后停机（对于可接受的w）

  • 递归语言：当且仅当存在TM M使得LM=L且如果语言中的w，M接受自然会停机，非语言中的w输入M中也会停机（但是无法到达终态） ——对应的问题是可判定的

  • 带存储区的状态：状态有有限个取值，其实是带头有个存储区可以在移动的时候改变。适用于一些分类的情况如 与经典图灵机等价（状态变成了二元组而已）image-20220105210253098

  • 多道图灵机：也是基本图灵机但是纸带是原来的三倍宽，即每个带单元格可以表示为三元组

  • 编程技巧：在图灵机中融入子例程干一件特定的事情

  • 多带图灵机：初始输入符号串在第一条带上，其他所有带的单元格都是B；有限控制位于初态；第一条带头在输入串最左，其余不定。可以有3（多个）带头。每一个move中，控制进入新的状态，每条带上正在被扫描的符号被替换为新带符，每个带头独立的向左、右、不动。

    其能力等价于单带图灵机：用2k道模拟k带图灵机。image-20220105210824345

  • 非确定TM：转移函数右边是三元组的集合，仍与确定图灵机等价。双带图灵机可以模拟非确定。广度优先的方式模拟非确定性图灵机的整个ID‘s空间树image-20220105210953681

  • 受限图灵机（都与基本TM等价）：半无穷带（双道半无穷即为双无穷）、多栈机（k个下推栈可以用k+1条带的多带TM模拟（一条扫描，剩下k条下推），两个下推栈就可以模拟一般图灵机，其中一个是带头左边单元格，另一个是当前以及右边单元格）、k计数器机（多个非负整数的计数器，控制时只知道是否非零——特殊k多栈机，一个计数器就是DPDA,两个以上就是TM

    image-20220105211419937image-20220105211430937image-20220105211439718

  • 普通计算机模拟图灵机，说明计算机不弱于图灵

  • 以多带图灵机模拟普通计算机（TM不弱于现行冯诺依曼计算机）：image-20220105211534159

Lect 13 Computing Theory

  • 图灵机与输入串的二进制编码：假定输入01串，有限状态1~k，规定始末态12，带符号X1到Xm且X1为0 X2为1 X3为B 假定带头移动为D1D2分别LR

    image-20220105211847110

    单1间隔转移规则中的元素，双1间隔转移规则，三1前面是输入串编码（前面需要加个1？）后面是图灵机编码

  • 编码01串：任何01串编码为1w比如 / 空：1/ 1:11 / 0:10 / 00:100 L13P6？image-20220105212609235

  • 对角语言——不是递归可枚举

    按照上述编码每个TM对应整数i 即其二进制编码是第i个0 1字符串，但不是每个整数都有图灵机对应。认为第j个图灵机不接受任何串，这样定义对角语言：image-20220105212754850

  • 递归语言补运算封闭，递归语言的补也是递归语言。image-20220105213137269

  • 递归可枚举语言的补运算不封闭：反例：通用语言

    如果语言和语言的补都是递归可枚举的，则一定都是递归的image-20220105213235015

  • 通用语言——递归可枚举但是非递归，image-20220105213353787image-20220105213401861

  • 语言对应的问题：“任意给一个串w在字母表*内，判定w是否是L内？”

    通用语言对应的问题：“任给图灵机M和输入串w，判定w是否被M接受？“

    图灵机停机问题：任给TM M，以及输入串w试问对w，M是否停机？——image-20220105213646238

  • 如果问题所对应语言是递归的，则该问题可判定，否则不可判定。语言递归可枚举贼该问题部分可判定，否则非部分可判定

  • 问题的归约？image-20220105213808681image-20220105213858952image-20220105213908332

  • image-20220105213918441image-20220105213926063

  • TM的时间复杂度，最多T（n）步停机，无论是否有w是M的语言。则为Tn

  • 非确定的时间复杂度：任何转移序列

  • image-20220105235651637

Posted Updated Course32 minutes read (About 4809 words)

2021秋季学期 数据结构与算法 Cheat Sheet

word三栏复制到markdown很乱，渲染后的pdf版

正确性：保持某性质，单调能中止

CH1最大子段和——从后剪负和更新 公共子序列——DP打表 渐进复杂度——够大，平均（期望复杂度）：

独立考察、各种操作概率加权 & 分摊复杂度：连续足够多操作后，总体成本摊还给单次操作

CH2 二分while(lo<hi){mi=/2; e<S[mi]?hi=mi:lo=mi+1;

ret lo-1; 插值最慢On 字长到n^1/2后为loglogn

Bubble优化：大趟无误停止；大趟中表明last（最后逆序对可能出现的位置，后面一定有序，hi更新为last

Bitmap 掩码位置0x80>>(k&0x07) 校验环 等长intF[]和一个stack，使得stack添加的时候辅助F记录位置，del：交换为栈顶，懒惰删除 Read:k==T[F[k]]

列表去重：相邻对相同删除后者

选择排序稳定性:选择大于等于保证稳定性，后者优先

循环节 A[k] A[r(k)] A[r(r(k))]回到A[k]互不交 不超n

交换法使M脱离原循环节自成且原来减小1 无需交换次数等效于最初的循环节个数 插入排序 就地在线输入敏感 最坏n^2 [3-10] 归并排序 适于并行外部

逆序对：上界On^2 冒泡交换逆序减一 归并可计数

游标列表 一组数据等长游标，空数据指向下一个可插入位置，非空指向下一个可删除位置（头方向）

CH4 Stack尾递归进制转换：while{模入栈，数/=进制}

D括号匹配：规定通用，不能失配，最后为空

E 栈混洗：只允许原入辅助，辅助入目标。本质是等量PopPush序列，等价于括号匹配。混洗数卡特兰（S第一次变空的时候——A首元素S弹出）(2n)!/(n+1)!n!，SPn=sum(1kn)（SP（k-1）*SP(n-k)）

充要：没有312，没有j+1,i,j，模拟验证：从另一个栈底开始匹配，对上了就pop，否则push成功则对。

F 中缀表达式求值：维护数和符号栈，读符号若读入高push，栈顶高开算直到栈顶低，相等（右括号或\0）脱括号进入下一字符;左括号全< 右括号全>从来不入栈

G RPN 数压入，符直接算 生成：操作数直接接入RPN，也放到栈中；运算符执行计算时接入RPN。

J 双栈当队 裹进两个底对底的栈，enq压入R，deq弹出F，若无F则把所有R都装过来。分摊分析针对每一个输入对他们的不同状态提出不同的开销，再根据假设情况计算上界最后总开销摊还给这种假设情况 d次deq和e次enq之后。。势能：原开销+动态势能=定

K Steap Queap Def辅助序列：每一个元素都是原序列中后缀最大者——从尾端扫描“顶”起非降。栈push新元素与辅助栈顶较大的。队列push要向前撑到够不到为止。优化：只计那几个撑起来的index

直方图最大矩形 for<n{while(!empty&&H[top]>=H[r]) S.pop(); //until H[top]<H[r] S[r]=empty? 0:1+H[top]; push(r); }pop all..栈顶小于扫描就入栈，栈顶大时就一直POP+计算更新直到栈顶小。继续扫描。分摊O（n）？

CH5 A 空树H取-1，RB取0 真:全二度 完全只剩最后一层不满 满为全满 长子左孩与兄弟右孩—多叉树

E 先序：维护栈while: pop访问+push rc lc while{访问左藤（loop: visit x+push x->rc+x=x->lc until !x），栈空退出，否则弹出子树循环.}

F中序：深入左藤（从上到下依次入栈），栈空退出，否则pop一个节点visit后转向其右子树..节点出栈时左子树不存在或完成，右子树未入栈。是否O（n）

Succ()：有右孩子，右孩子一路向左深入。否则一路作为右孩子(向左上)找爹，停止后再找一个爹。

G后序：若栈顶不是x的爹，就去找其子树中最左的叶子（while栈顶x非空(if lc，（if rc,push rc）push lc) else(push rc).返回前pop()）。Pop and visit 每个节点出栈时以它为根的子树已经遍历，且右兄弟如果存在一定在栈顶。正可以遍历右兄弟。验证复杂度？

等价于表达式树的计算~RPN

H 层次遍历：deq visit enq lc rc，其中队列最大规模n/2的ceiling。前面都出1入2.向量紧凑表示完全树

I重构 中序+先序|后序 or先序+后序&&真 增强序列allNULL输出 PFC 文件长度正比于平均带权深度wald。必有叶子在底两层 不断贪心合并最小树直到只剩一棵 正确：内节点必双子、兄弟可换、层次 归纳 定差

CH6 图 A 简单图：无自环重边 简单路径没有重点 带权网络即各边带权重的图

B 邻接矩阵 nn记录边 关联矩阵ne structV中有出入度、状态、dftime、遍历树parent、priority structE中有type（undetermined、tree、cross\forward\backward）

实现：线性Vs、双vec嵌套构成二维边指针集合。枚举所有邻居O(n) 邻接表为Ooutdeg+1 addedge：new

表并更新关联点的出入度。Deledge类似 addvertex：Vs push新、每个已有的外层vec都要push一个null并且加一个整个的外层vec。删除：del出边（入度）和那一列vec，删除顶点后再删除所有的入边（出度）。

性能分析 适稠密图 θn^2空间 用vec后透明地处理空间溢出等 平面图有点-边+区域-连通支=1

C 邻接表 每个点作表头连接自己所有邻居（所有后继），有向图只记录作为前驱\后继的边，适稀疏

空间On+e 平面图On 时间：构造n+e 枚举所有以v为尾（头）的弧1+degv （n+e，可建立逆邻接表改进） 维护后查deg+-都是O1 但exists需要搜索Oe，选用散列可期望O1 适遍历、顶点数目不定，算deg相关

D bfs 树的层次遍历 维护Queue，每次dTime=++clock，对于所有邻居开始处理{如果尚未发现则改为发现并加入Q中，标记为Tree边和parent，如果已经被发现标记为跨边}标记访问完毕

用于：寻找连通支和可达分量，对连通支的遍历包一层小写的bfs，reset并重置clock，对所有节点做遍历一旦未发现就做BFS(v,clock)。

复杂度：无向图reset n+e 每个顶点内枚举邻居需要1+deg，共需要n+2e

性质应用：最短路径即为深度 周星驰数

​ E dfs 先序遍历支撑树 DFS{标记开始时钟; 发现当前v 考察每个邻居{未被发现：标树，递归DFS它；dis—指向了祖先，backward；visited—比较发现时间，自己早则forward 否则cross} v已经访问完毕；标记结束时钟}

无向图中只有TREE和BACKWARD 有向图 也包装

遍历树所有边取反向 括号引理：后代活跃期包含于祖先，无关则不相交，没有别的情况。Backward一定有回路但！=回路forward是我的孩子，cross和我无关。有向图环路检测dfs 欧拉回路拓扑排序双联通分量dfs

F 拓扑排序DAG有向无环图 构造与偏序相容的全序 可以拓扑排序一定无环，无环一定可拓扑排序。因为“有向无环图中必有零入度节点不唯一m”若去掉m可排序则加入m的排序为m在最前 m。

顺序：所有零入度入Stack，取空Q，while S不空{栈顶入Q，如果v邻接u入度1则入栈，并删除v及其关联}最后G删空当且仅当成功拓扑排序

逆序：DFS中每当visited加入S，有backward not dag。结束后顺序弹出S已经ftime由大到小 CH7APP

A 双连通分量 关节点删了之后连通分量增多，无关节点为双连通图，极大的双连通子图为双连通分量BCC 找关节点？—通过dfs根至少两子树，内部节点有某个孩子u且这颗子树不能由任何backward连接到v的真祖先（可以backward到v）。这时BCC父亲和BCCu的关节点。记录Highest Connected Ancestor：hca(v) = subtree(v) 经过backward连接的最高祖先。DFS中一旦发现backward v,u，取hca v=min(hca(v),dtime(u))最后标记的是dtime。如果dfsu完成返回v时若有hcau<dtimev则hca(v)=min(hca(v),hca(u))。否则u子树的最高祖先不超过v即可断定v是关节点。而v+子树u为一个BCC

Dfs找bcc：额外围护Stack，将当前v入栈。枚举邻居{未发现Evu—标树边，递归遍历u、讨论hca关系确定关节点后持续弹出S直到u弹出这些就是一个BCC；见上}同O(n+e) 推广到强联通分量？618

B pfs 存放顶点并维护priority(v)越小越先 框架{枚举邻居更新优先级和父节点；从undis节点中挑出pri最小的点作为下一个s；标记为访问以及标记好树边（特别的，s的爹已确定）

C Dijkstra 均正最短路径树!=MST 更新时发现比较路径长度松弛长的（by set new parent）

D prim—MST 允负0 Cayley完全图有n^(n-2)

uv是该割的一条极短跨边则一定存在包含uv的MST。反证证明。任何MST都通过极短跨边连接割。若支撑树添一条边的环路中存在其他边为极长边。则原T-f+e为新图的MST。构造中把当前树看成割。正确性：每一条都属于某一MST 6-28？

实现：比较老pri和权重，后者小则更新pri和parent

E Kruskal MST 每个节点都是一棵树，按照边权排序依次尝试使森林变为一棵树。找e来自不同树时可以合并。Proof 引入的每条边都属于某颗MST e一定是割

T的极短跨边。归纳证明。。

并查集union-find问题：维护group[]所属子集快找慢合并。维护parent法：合并时指向新爹即可680？

F Floydwarshall 允负边但不能负环路。For k for u for v A[u][v]=min(A[u][v],A[u][k]+A[k][v]) 8****二叉搜索树

A 中序有序 归纳树高可证中序遍历单调

B 查找—返回引用，可能为空节点表示该插入的位置 插入—查找确定位置，插入后向上更新高度 删除—分类删除{单分支时删除自身让孩子替换，双分支与直接后继交换数值！删除其直接后继}向上更新高度

C 期望树高 全随机排列的平均高度θlognBST越低的权重越大 n个互异节点的不同BST共有catalan(n)棵=sum(S(k-1)*S(n-k)=(2n)!/(n+1)!n! BST等概率θsqrtn

理想平衡：n个节点高度在log2n 渐进平衡—渐进不超过Ologn即为BBST 等价BST可On互转

D AVL树渐进平衡 定义平衡因子=H(lc)-H(rc)<=1 h高度至少包含S(h)=fib(h+3)-1个节点此为最瘦的情况 S(h)=1+S(h-1)+S(h-2)配成fib

插入可能从祖父向上一整路失衡，找到最低失衡节点(一边updH)和儿孙考虑。同向一次zigzag用34实现,异向两次等价于34重构。高度复原，全树复衡。

删除：单旋、双旋情况可能祖先继续失衡高度减小，可能需要logn次调整、 可能全树高度下降 kunth: 0.21次

1D****查区间 二分查右边界后向前检查+输出Or+logn

2D：利用容斥原理n方时间的预处理，矩阵每个点中包含其左下的点的个数，答案正对角线-反对角线

预处理和空间为n^2，每次queryOlogn

B kdtree1D—完全二叉each key=Minkey in Rsubtree，即右边区间的左端点。仅最底两层的叶节点是1D点集

2D 每个region左下开右上闭 等价于四叉树划分

递归建树P：如果只剩一个，创造叶节点返回;

Root=createKdNode();splitDirection=even(d)? ver|hori; root->splitline=findmedian(direction,P);

分隔开子点集，并左右递归建树 所属region往左下移

Query：如果是叶区间，判断是否在；左右分别{整个region都在搜索中，report，否则如果有交集则继续递归搜索}

复杂度：预处理Onlogn 储存On 查询Or+sqrtn

Q(1)=O1; Q(n)=2+2Q(n/4) 节点的四个孙子不超过两个会继续递归。更高维度？O(r+n^(1-1/d))

C MultiLevelSearchTree 按维度搜索范围，最坏——x搜出了所有点但y拒绝了所有点 On

嵌套树实现 O(r+(logn)^2) 二维建树时空Onlogn

二维以上建树储存都是nlog（d-1）n 查询为r+logdn

A 逐层伸展 对v的父亲做zigzag，最坏时分摊Ωn

双层伸展 向上追溯两层， 在双zig或zag时先转祖父再转父亲。使最坏情况的单条路径也能收缩一半。【8-2】分摊Ologn每次旋转之后都要对三代updH

搜索：标准搜索+splay+返回根

插入：搜索后决定在根的左上还是右上插入新根

删除：搜索后删除，在R里面做失败查找Rmin来当根 评价：无需高度和平衡，分摊Ologn近AVL且反复顺序访问子集分摊仅常数

分摊分析：定义势能φT=sum(log(sizev))平衡小倾侧大

单链logn!=Onlogn 满树On 不妨仅考察search

连续m>>n次访问，记Ak=Tk+△φk

则显然T=A-△φ在A+-Onlogn区间内若能证明 A=Omlogn则一定有T=Omlogn

​ 讨论A在单zig/zag中Ai<1+rankiV-randi-1V

B BTree d代合并 m=2^d出路和2^d-1个关键码 多级存储中减少外部查找的IO，批量访问一组关键码

外部节点深度相等为树高，叶节点为h-1，内部节点关键码<=m-1&&分支出路：ceiling m/2<=n+1<=m（root>=2）成为(m/2，m)-树 典型(2,4)-树

内部都是vec装关键码和孩子

查找 vec，不成功标记_hot，v=v->child[r+1]每一深度最多一次IO运行时间Ologn

插入上溢 在_hot中插关键码和空指针，检查上溢：上溢节点中位数归入父节点的子树位置并分裂指针分别指向中位数左边右边，仍然可继续分裂。。到根仍上溢则提升中位数为新根，是B树增高唯一途径 O（h）

删除下溢：如果不是叶子，在右子树中找直接后继交换

1.若有左兄弟且够大，则p节点分界key作为最小，左兄弟最小作为p节点分界。2.右兄弟借父亲旋转修复

3.左右兄弟必有其一但不够用则把父亲的分解key降下来粘接自己与兄弟。但父亲仍继续下溢，不超过Oh

Max Height时内部节点尽量瘦logmN+1 <= h<= 1+ log (ceiling(m/2), grounding ((N+1)/2))

C 红黑树 减少结构变化，相邻版本差不超过O1

1树根和外节点为黑 2.红节点只有黑孩子父亲 3.外部节点黑深度相等 即根的黑高度 等价于2,4 B树证明其平衡h<=R+H<=2H 黑高度上界log2,n+1故Ologn

插入：红节点黑高度0修双红{爹是红则一定有黑祖父，1.叔父黑，则局部34重构+染色RBR 2.叔父红，pu转黑（BH++）g转红。分裂节点g上移但g仍可能双红 若已经抵达树根则强行转黑、黑高度++}

删除：仅分析实际删除的，单分支被接替的情况。删除者和接替者一个红时，接替者染黑即可。

​ 删除者接替者都黑需修正 如果删除根则新根置黑，更新高度即可。若父亲平衡则好，替代节点为红染黑即可，接替和删除均黑（此时接替者为null）{接替者父亲p和兄弟s

​ BB-1兄弟黑且至少有一个红孩子t{ s继承pcolor, tp to black} 等效于关键码旋转消除下溢 转下p转上s

​ BB2-R s黑且两个孩子都黑p红 下溢节点与兄弟合并顺便向父节点借了一个红色

​ BB2-B s黑两个孩子都黑 p黑 合并兄弟和空空的自己和爹，父节点变空继续上溢 solve（p）

BB-3S 红孩子必黑

绕p单旋继续solve （r）下一步必恢复

1~2旋转 3染色/2染色/1染色上升一层/1转2染色

A hash() key->&entry 期望O1不是O1

B 散列函数 确定快速(期望O1)满射均匀少聚集取质

数模：不动点0，相关性(相邻映射也相邻) MAD (ax+b)%primeM 还有数字分析、平方取中间几位，折叠取和、按位异或、伪随机数、多项式{循环移位异或之后相加，最后模表长}

C 冲突排解 开放散列 多槽位、独立链空间不连续无法缓存、公共溢出区处理冲突正比于溢出区规模

封闭散列+开放定址可出借

线性试探：非同义词也会冲突，数据堆积严重、局部性良好。标记以懒惰删除—后查找时为不匹配的非空桶，插入时为空桶

平方试探：表长素数且装填因子小于0.5一定能找到出空桶——n方%M取值为ceiling(M/2)且前面就能取遍

双向平方试探 表长取4n+3素数就不重不漏

素数p表示为平方和等价4k+1 自然数表示成平方和等价于每一个4k+3素因子都是偶次方

再散列：约定冲突后再hash一次为每次的偏移增量

重散列：懒惰标记过多或者装填因子太大

桶排序 初始化置0，扫描标记Om、顺序输出On。允许重复时桶里维护链表和表长空间变Om+n

N个互异点在实轴上的最大缝隙？1.找出最左最有并划分n-1个桶 2.模余归入对应的桶并在每个桶中动态记录最左最右点（可相同可没有） 3.计算相邻非空桶的距离 Proof Maxgap至少跨过两桶 但mingap？

基数排序 从低位开始分别桶排序 Proof会保持前i-1趟的顺序复杂度为O(t*(m+n))m为取值范围，t为数域位数 且有稳定性。。二进制时1扔到尾巴0不管

整数排序 n进制d位 比如六十四位整数的n>2^16即可 在0~n^d中n个数转换进制后排序时间为Odn

转换进制的复杂度。。？

计数排序 大数据小取值——已经按数字排序的牌再按花色排序：归到四个花色桶中，得到各个桶内的最大rank（向后累加桶内个数）。从后向前扫描原序列并相应桶的–最大rank即为位置。。

跳转表 期望塔高2解决空间On

查找：每一层向后到更大的key or溢出，命中则返回否则向下一层继续。。纵向跳转不超过期望Ologn

横向跳转一定抵达塔顶Thm Ey=(1-p)/p=1次，同层不超过两次，每次查找都在期望2h即Ologn内

插入：查找位置（雷同降落）插入底层后后扔硬币长高 删除时从高到低拆塔

A 支持取删插(sorted) vector list BBST都可实现

B 完全二叉堆借助Vector

插入：末尾插入后逐层上滤，大了就换，不需则停

删除：删头补脚后逐层下滤，找堪为父者交换或停止

建堆：按个上滤时最坏Onlogn->自下而上的下滤Floyd 从n/2-1开始向上的下滤

C 堆排序 改进selecttion的发动机选最大值，就地算法{建堆后swap头元素和elem[n–]，下滤堆头}

D 胜者树 叶节点待排序内部为胜者 createOn removeOlogn insertOlogn 树根是全局冠军。用于排序时建堆后排一个数就下去删除然后向上重赛。。Onlogn

选取最小的k个 n+klogn

败者树：根的父节点是冠军，重构时和败者比赢得向上输的留下。构造时相当于n次重构

E 优先级队列 堆装满顶点 delmax nlogn increase更新关联顶点距离需要elogn d****叉par**:**k-1/d， child=kd+i

上滤logdn 下滤dlogdn 运行时间为ndlogdn+elogdn

取d=e/n+2时达到O(elog((e/n+2),n))自适应达到最优

左式堆后O(e+nlogn) 插入合并inc接口分摊O1

F 左式堆(knuth修订命名) 沿藤合并 基于二叉树

引入all外部节点 定义NPL为到外节点的最近距离且规定npl左孩子>=npl右孩子 自己npl=1+npl(rc)

根右侧链(长度d)的终点为最浅外部节点，存在以r为根高度为d的满子树 至少有2^d-1个内部节点和2^(d+1)-1个节点 反之n节点左式堆一定小于grounding（log(2n+1)）=Ologn

合并：{把较大的堆的右子堆与另一堆合并后连接到较大的堆顶，并根据npl可能交换左右子堆，更新npl1116

插入 merge原树和新节点 删除 merge左右子树

B 暴力 i(原串) j都要回退

C KMP(Knuth+Morris+Parrt) i永不回退 失败时j变小并继续，记录j回到的next表：前缀=后缀的最大前缀右点 while(j<m&&i<n){ if (j<0||T[i]==p[j]) i,j++ else j=next[j]} 分摊分析：K=2*i-j 成功失败k都会至少加1，结束时k<=2n+1

Next表：失败前的后缀=原串前缀len

mamammia-10012310 -1 0 -1 1 0 -1 3 1 0

Boyer & Moore****算法BC从末字符开始比对，BC怀字符，遍历Pstr标记字符的最右出现

偏好概率小P长字母表大 策略移动到那里/没出现整个移过去/出现太靠右移动一个

最好n/m 最坏n*m worst: 100in000000？

Gs表好后缀 最好n/m最差n+m 改良kmp反过来找P[j:m]=P[k:m-j]把j-k记录在j里

构造：MS/ss=P[0:j]的某个后缀==P的某个后缀<=j+1

Ssj=j+1: gs[i]=m-j-1任i<m-j-1/gs[m-ss[j]-1]=m-j-1

ms[n-1] = n; int lower = n-1, upper = n-1;

KarpRabin d进制数编号 匹配则一定子串相等 将指纹用散列压缩（相邻两次散列，O1内获得下一个指纹） 哈希值相等后仍需精确比对

A 快排mi**=**Partition(lo,hi),递归快排两边

LUG版 随机选一个轴点swap到lo并备份，向内交替移动hi lo 把有效的指向空的后变为空的。最后轴点归位 期望logn 取消递归时维护栈小贪心，大任务优先入栈。保证递归深度不超过logn 落在λn试试，一条递归路径最多log(2/(1+λ),n)个准居中，λ>1/3时有1-1/pown的概率深度不超3log3/2,n 比较次数1.386

LUG‘解决重复，if(lo<hi)elem[lo++]=elem[hi];

DUP’版 松LUG’的交换条件，多交换轴点居中 DUP

LGU稳定：从第二个往后如果小于轴点就与++mi交换

众数for{ifc==0 maj=A[i];c=1;else maj==A[i]?c++:c–}

Median(vec &S1,int lo1,Vec &S2,int lo2,int n){

If(n<3)return trivialmedian(~~~~~)

Int mi1=lo1+n/2;mi2=lo2+(n-1)/2;

If(S1[mi1]<S2[mi2])return median(mi1,lo2,n+lo1-mi1)

Else if{} else return S1[mi1] 任意子向量Ologmin(n1,n2)

第k+1小 选pivot进行LUG后缩小范围继续猜

Linearselect:Q是小常量，如果序列小于Q为trivial，划分子序列；各自On*n排序找到中位数；递归找到全局中位数；划分LEQ计数；每轮缩减到3/4子问题

​ 希尔排序 矩阵变窄，每次对各列排序。对希尔序列的最坏情况 6 7 8 52 3 1 4

g有序在h排序后仍g有序

当gh互质时，最小组不出来为gh-g+h 则gh有序后其线性组合依然有序 gh互质时for all elems: i-j>x(g,h) only if S[j]<=S[i] 不超过n*x(g,h)个inversions

Posted Updated Course32 minutes read (About 4765 words)

2021春季学期 面向对象程序设计基础 期末复习笔记

My Object Oriented Programming Habits

  • class中的数据变量英文命名写全并且每个单词首字母大写，构造函数传参数时参数名称全大写
  • private数据成员在public中获得函数用get_Data（）命名

记录期末之前上课&题目

5.24 W14 1-1
  • function<returntype(parameters)> 类型可以统一函数指针和函数对象，如果将function<int(int)>作为函数参数则可以将所有以int返回值int参数的函数或者int返回值int参数的对象都可以传入并不违法【/统一了函数对象和函数指针/】
5.29 HW14-15
  • string.c_str() 返回一个const char*为string内部存储的数组结尾是\0，为了保证不用外部char指针修改string这个const无法初始化char*类型。将string转换成char*应该用int copy(char* tar,int lenth,int pos=0)返回实际拷贝的字符数目。
  • string类的拼接操作+时间复杂度为生成的字符串长度，用+=更快
5.31 W15 1-1
  • string拼接操作速度：+= > string.append( string) > stringstream > +
5.31 Review L1-L3
  • 带缺省值参数函数不算参数个数，去掉缺省值参数后如果其他参数都一样会产生歧义被拒绝
  • auto后面定义的变量要同一类型
  • auto i=0; and decltype(i) b; 即decltype（） xxx为类型说明符，后面可以带个参数为“定义一个和这个参数一样类型的变量xxx”
  • auto作为函数返回值类型要在参数列表后面加->decltype(returnvalue表达式)
  • NULL是int型常量0 nullptr是严格空指针
  • Function f1(int a,int b=1)and f1(int a=2)即使一个是private不许访问但是仍然会ambiguous二义性错误。
  • inline ReturnType Function();
  • 遍历某个范围的for循环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int arr[3] = {1, 3, 9};
		for (int e : arr) // auto e:arr 也可以
			cout << e << endl;

如下程序无法过编译会导致二义性
#include <iostream>
using namespace std;
class A {
private:
    int a;
    void f(int i=2) { a = i; }
public:
    void f(int i, int j=2) { a = i + j; }
    int get_a() { return a; }
};

int main() {
    A aa;
    aa.f(1);
    cout << aa.get_a() << endl;//二义性
    return 0;
}
5.31 Review L4

  • 初始化列表顺序并不是初始化顺序，初始化列表时应用声明顺序进行初始化

  • 后缀运算符++需要哑元dummy，要把原本的数据增加之后返回的值仍然是增加前的，可以先复制原对象然后给原对象++，最后返回原对象的复制。

  • =，【】，（），->这些只能通过成员函数来重载

  • 流运算符重载

    1
    2
    3
    4
    istream& operator>> (istream& in, Obj& dst );
    ostream& operator<< (ostream& out, const Obj& src );
    需要声明为类的友元以便访问私有对象，在类外（全局）进行重载的定义
    friend istream& operator>>(istream& in, Obj& dst);
5.31 Review L5

  • 友元函数可以是其他类的构造、析构函数，也可以是其他类，也可以是全局函数

  • static普通静态变量与函数：初定义要初始化仅一次，内部可链接，作用域仅限声明文件cpp不能被其他cpp所用

  • static静态成员变量：归属于类而不是具体对象，所有对象可共享。通过obj.var和classname::var均可访问。在实现文件赋初值VarType ClassName::static_var=Value.

    需要在h中声明cpp中定义，h定义会导致包含h后重复定义

  • static静态成员函数：static关键字在ReturnType前，类和obj都可以访问，不能访问非静态成员，即属于整个类的函数只能访问类变量

  • 常量数据成员：初始化后在该obj整个生命周期中不能改变

  • 常量成员函数：const关键字在函数体前Function（） const{...}不能修改class的成员，只读而不可写入，常量对象只能调用const成员函数

  • 拷贝（传递参数）时如果有指针成员容易出错，直接位拷贝指针不变而同一块内存会释放两次

5.31 Review L6

  • 不想给某个函数修改值的权限则使用const参数

  • 拷贝构造函数参数：同类对象的常量引用 自动合成为Bitwise Copy遇指针出错

  • 常（左值）引用可以绑定右值，引用本身为左值

  • 右值引用在延续即将销毁变量的声明，提升处理效率，即把本要销毁的变量引用了变成了不销毁的左值——移动构造函数参数：同类右值引用

    移动构造函数需要：1.复制指针地址或者值 2.将原指针地址改0避免释放

    使得生成的临时对象被保留下来，本该释放（析构）时发现指针为空，不能释放内存，而真正有意义的指针（数据）被移动保留了下来

    原则：不浪费任何右值（创造右值之后不销毁，及时利用）

  • std::move(左值)，把左值当做右值用，需要这个左值不再被使用或者即将被改（swap）

  • 类型转换函数的自定义 从Src到Dst类

1
2
3
4
5
6
7
class Src{
operator Dst() const {}
}
或者在目标Dst类中定义常量引用为参数的构造函数
class Dst{
Dst(const Src& s){};
}
5.31 Review L7
  • 构造函数和析构函数，复制运算、友元不能被继承
  • use using关键字来使用基类的（所有）构造函数
  • 基类的私有成员在派生类函数中也不能访问，只有基类的成员函数中被访问。而公有成员成为派生类共有成员可以被访问。protected成员可以在派生类成员函数中访问但不能在外部函数访问
  • 重载Overload，函数名必须相同，函数参数必须不同，作用域相同。（编译多态或者属于静多态）
  • 重写隐藏其实就是Redefining，重新定义基类函数实现特殊功能，屏蔽了所有同名函数，参数可以同可以不同（运行时多态、动态多态）using 类::成员函数来解除屏蔽）
6.1 Review L8
  • 凡是可以接受基类ptr或obj，都可以直接接受派生类，会自动切片
  • 通过对象的向上类型转换可以访问private继承无法访问的基类成员变量coz向上类型转换只可以Public继承，不允许私有继承向上转换
  • 带有虚函数的class，对象大小会加上一个指针（8），多个虚函数也只有一个Vptr指向vtable
  • 虚函数机制在构造、析构函数中不工作，构造不能虚而析构经常是虚的总是将基类的析构函数设置为虚
  • 虚函数Feature重写覆盖必须要函数名参数表一模一样，这样会根据运行时实际类型进行动态晚绑定
  • 在函数体前面加override关键字检查是否成功重写覆盖
  • 函数体前加final关键字——禁止继承后再覆盖，已经是最终版本的函数实现
6.1 Review L9
  • （形参）之后加=0声明为纯虚函数，含有一个纯虚即为抽象类无法具象化出对象，只为了之后的继承类实现共性“接口”或者“方法”。一般是没有实际物理意义的抽象（shape，creature）
  • 纯虚函数必须被之后要使用的继承类重写覆盖，不然仍然是纯虚函数而该类为抽象类，即必须把所有纯虚函数实现一遍
  • 纯虚析构函数仍需要函数体，即声明纯虚=0之后还要写一个空实现函数体，后面不用显式地重写覆盖
  • 使用基类指针数组管理具体派生类对象，具体处理时转化成专用指针调用专用接口
  • 使用dynamic_cast<tar*or&>(obj_p or obj_r)如果失败返回nullptr，用来判断实际类型
  • static_cast不检查实际类型，只要有继承关系就转，dynamic会动态检查，慢但是安全
  • 向上类型转换：指针和引用时不改变虚函数表（晚绑定，仍按实际类型调用继承重写函数）而直接切片为基类对象会丢失增加数据和方法
  • dynamic_cast正是通过虚函数表判断是否安全地进行向下类型转换
  • 多重继承：Best Practice 最多继承一个非抽象类，可以继承多个抽象类（接口）
  • 多态（接口函数根据实际派生类而不同表现）效果条件：继承&&虚函数&&（引用or指针）
  • 模板：算法实现与参数类型无关，则将函数的参数类型定义为一种特殊的“参数”
  • 调用函数模板时，可以手动输入“模板参数”也可以让编译器自己认。实现原理：编译期将模板替换为需要的类型生成一份对应的函数代码，需要多少不同的就生成多少
  • 模板使用：
1
2
3
4
5
tmplate <typename T>
class A{};
or
tmplate <class T>
ReturnType Function(){}
  • 类模板中成员函数类外定义前要声明一下同样的模板，模板参数编译期确定不可使用变量
  • 模板也是同一段代码实现不同的相似功能，但是在编译期处理为“静多态”
  • image-20210601195810985

image-20210601195823314

image-20210601195839453

image-20210601195846178

image-20210601195853777

6.1 Review L10
  • 标准C++库所有内容都在标准命名空间std里，包括stl标准库
  • 不同命名空间中的同名函数、变量等命名不会互相冲突
  • 自定义命名空间namespace A{int x,y;}使用时A::x and A::y，用using namespace直接使用这个命名空间的所有成员，也可以using namespace::var or ::func 直接使用某几个函数
  • Containers: 简单、序列vec,list、关系set,map
1
2
3
4
5
  template<class T1, class T2> struct pair{
T1 first;
T2 second;
//若干其它函数
  };

  • 支持 .first .second make_pair( , ) < > 按照第一第二比较

  • tuple：类似pair，无限长，使用v0=get(tuple_var)且pos需要编译确定，不能使用变量

    支持make_tuple(,,,) tie(x,y,z)=make_tuple(xx,yy,zz)即tie返回左值引用的元组，可以利用右侧的tuple来一次性多重赋值

  • vector支持：vec[pos] vector vec0 .size() .clear() .push_back( xx) .pop_back(xx) use iterator to .erase(x.begin()+1,num) .insert(iterator)而iterator支持*，可以直接sort，支持++ – += -=支持减法运算

  • 迭代器失效：insert和erase，和改变大小时可能会扩展capacity而整体迁移所有it失效，修改过容器后不使用之前的迭代器

  • list：快速的增减push_front() push_back() find(l.begin(),l.end(),tar) l.insert(it,tar) 不支持下标，插入和删除时不相关迭代器不失效

  • set：不重复元素构成的无序集合，只是不保持加入顺序，内部按大小排列

    支持insert（） 查询find（）返回迭代器 erase（s.find(val)） count(val)只有0或1

  • map：关联映射 其实为<Key，T> Key必须互不相同 通过下标map[key]访问val如果不存在则创建对应映射 支持insert(pair)插入 查询find(key)返回it 统计count(key)要么0要么1 支持erase(it)

6.1 Review L12
  • 构造方式s3(“string”,num)num为截取的长度（num,’x‘）赋值num个x，（it1，it2）迭代器
  • string.c_str()返回一个const char*不能修改，涉及底层实现，不能赋值给char*需要copy(ptr,n,pos=0)
  • size()orlength() clear() empty() push_back(‘a’) or append(s2) 字典序比较
  • cin>>读到空格 getline（cin，str）读一行不包括/n getline(cin,str,’#’)可以读换行一直到终止符#
  • stoi（“2001”） stoi（“50 cats”，&sz）sz为读入长度 stoi（string，nullptr，进制=0）默认自动检查进制，可以stod转化double
  • 库中格式控制函数fixed scientific setprecision（2） oct dec setw（3） setfill（’‘）设置对齐长度为3且填充字符
  • 使用stringstream拼接字符串，也是stream可以赋值于var ss>>a>>b
  • 正则表达式https://www.runoob.com/regexp/regexp-intro.html菜鸟教程https://blog.csdn.net/bgzclxqq/article/details/90262904 CSDN关于C++的正则式
6.1 Review L13

  • 声明函数指针 ReturnType (*ptrvar)(parameters)，可以直接赋值，甚至可以直接auto指定类型

  • less()和greater()为自带的比较函数,其实是个对象，长得像个函数

  • greater是一个模板类

    greater 用int实例化的类

    greater() 该类的一个对象

  • 函数对象需要public重载()运算符

  • 把函数当参数需要声明：template <class Compare> void sort(Compare comp)可以接受函数指针和函数对象

  • 智能指针shared_ptr<T> p1(new int (1))也可以make_shared(2) 或者拷贝构造同类

    重载了*运算符直接访问对象 也可以->访问成员

  • 自带引用计数use_count()引用全归0才自动销毁对象

  • 实现原理：image-20210601211114941

  • 获取常规指针.get() 清楚并减少引用.reset（） 可以用static或dynamic_cast<>(p)

  • 不能使用同一个裸指针初始化多个智能指针 即辅助指针U_ptr只能有一个不然多次释放

  • 存在循环引用永不析构问题weak_ptr指向对象但是不计数wp.lock()转换智能指针

  • unique_ptr确保一个对象只能被一个指针指向（引用） 不能赋值指针，可以移动up2=std::move(up1) 使用release放弃up控制权并返回裸指针

6.1 Review L14

  • 模板方法：抽象出不同具体类的骨架，写出通用的基类并且将步骤的实现延迟到子类中（设置为纯虚函数）。不改变算法结构而重新定义一些实现步骤。

  • 父类定义骨架，子类实现细节，需要新的实现重新继承即可

  • image-20210601214723704

  • 策略模式（strategy）：定义一系列算法并封装，可以互相替换

image-20210601215008527

image-20210601215017697

  • 对不同的每个子任务（方法）都写出基类Strategy然后继承出具体实现类，实际调用的框架中只需要管理（存储）这些方法的基类Strategy指针即可
  • 策略模式符合“单一责任”原则：一个类or接口只负责一项职责，功能层面解耦
  • .迭代器模式：基于Iterator基类，实现不同聚合对象的顺序访问，使得接口统一而使用方法统一
6.8 Review L15

  • 结构性模式——适配器Adapter、代理委托Proxy、装饰器Decorator

  • 适配器模式：客户期待接口基类Stack中有各种接口，现在有一个写好的类似功能类Vector，想加一层Adaptec使得代码继续复用

    Adaptee——Adapter——Target——Client

    实现：

    组合——把Adaptee放到Adapter中当成员，继承Tar基类，挨个实现要求的函数

    继承——公有继承Tar和私有继承Adaptee类，即er类就是ee和tar类，实现函数时直接调用ee中继承过来的函数即可

  • 代理委托Proxy：客户要求的基类接口，有一个RealSubject继承了基类接口可以满足需求，但是需要更多功能和控制操作

    Client—BaseSub—Realsub<—Proxy：BaseSub

    Programer—ProxySub（derived from BaseSub）has a RealSubPtr

    实现BaseSub中的函数，函数体{Ptr->Request; other commands;}实现了包装并增加。

  • 装饰器Decorator：无限的增加新功能，每次增加几个功能并可以无限进行这个装饰的过程。装饰器是定义一种递归模式，方便之后的功能继承这种模式

    实现：装饰器:public Base 私有基类指针，构造函数接受一个基类指针（这一层装饰之前的类的指针）并存储。定义虚函数addon（）为每一层装饰的新功能，定义常规需求函数Draw{add（），ptr->draw（）}。具体增加功能的时候需要功能类继承装饰器类然后实现add函数为新功能

    魔兽争霸学技能：学技能类（Decorator） 具体学了什么（继承Decorator的类）构造，一级级学技能上去。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Decorator::public base{
    	base* upper;
    public:
    	virtual ReturnType addon(){}
        ReturnType Request(parameters){
            addon();
            upper->Request;
        }
    };

    //crearte a decorator pattern

    构造：基类—装饰递归结构—装饰1—装饰12—装饰123

    调用过程（解嵌套）：装饰123—3Draw，指针变为装饰12—2Draw指针变为1—1Draw，指针变为基类Draw

6.10 FinalExample：

  • 不能继续使用（using）纯虚基类的构造函数

  • 使用虚函数机制时把基类析构函数生命为virtual

  • list的迭代器是双向的，甚至可以反向迭代。反向迭代器rbegin（）和rend（）其自增运算++为向头变换

  • 迭代器失效仅有erase操作的迭代器，其他任何迭代器不受影响。而且list迭代器太牛了，锁定自己的元素不变，也就是说指向链表中的某一个元素。头迭代器和尾迭代器在中间插入元素后依然是头尾不需要改变。

  • list中的insert是在迭代器it之前的位置插入元素，并且迭代器仍然指向原来元素（链表特性）

  • list为空时，用insert比较危险——头尾迭代器相等并且会一起指向尾空元素。不要把list想象成动态数组，还是想象成链表安全些。

  • 关于Strategy模式：管理一堆Strategy_x基类，每个决定单独的x1、x2、x3

  • 关于map类，声明：typedef map<int,string> num2name; 使用时可以用数组符号修改key值也可insert（），但是insert不支持已经存在的key，数组下标[]会覆盖。

Posted Updated Autoa minute read (About 123 words)

Hello World by hexo

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Follow

Links

Categories

Recents

Archives

×