最新军队文职-计算机类计算机类-数据结构与算法知识点总结

精品文档

字符串

1、几个名词的定义：串的长度，子串，位置，串相等，模式匹配。简单模式匹配算法在正文设置一个指针指向第一个然后跟模式串匹配。不行就指针加一直到匹配成功或者正文结束。时间复杂度为O(m+n)最坏为O(mn)

2、KMP算法：时间复杂度为O(m+n)。next(j)函数的计算(计算到第j个就是从1到j-1这个子串首位分别截取尽可能长的相同子串。从尾巴那里截取的子串不用倒过来。得到的最长相同子串长+1就是next(j)的值啦。Next(1)固定等于0。 恒有next(2) = 1)， int KMP_StrMatch(SString S, SString P)｛ int i = 1, j = 1, m = 0; while(i <= S[0] && j <= P[0]) if (j = 0 || S[i] = P[j])｛i++; j++;｝ else j = next[j]; //失配时从next[j]重新比较 if(j > P[0]) m = i – j + 1; return(m); ｝

=================Newnext函数的计算====================================== void get_newnext(){ int k,j;

newnext[1]=0; j=2; while(j<=P[0]){ k=next[j]; if(k==0||p[k]!=p[j]) newnext[j]=k;

else newnext[j]=newnext[k]; j=j+1;}}

3、BM算法：Boyer-Moore串匹配算法(简称BM算法)。最坏时间复杂度O(mn) 精品文档

精品文档

其思想是在匹配过程中，一旦发现在正文中出现模式中没有的字符时就可以将模式、正文大幅度地“滑过”一段距离。

同时考虑到多数不匹配的情形是发生在最后的若干个字符，采用从左到右的方式扫描将浪费很多时间，因此改自右到左的方式扫描模式和正文

========================dist函数的计算==================================== m c?P, 或c= pm且c1 pj(0

? dist(c) =

m – j 否则 (j=max{c= pj, 0

4、KR算法：指印函数的要求：（1）速度快。（2）冲突概率小。（3）相邻两个字符串的HASH值必须有相关性。

5、KR算法的基本思想：首先计算模式串和正文串所有长度为m的子串的指印函数；然后匹配与模式串指印函数相等的正文串中的子串，找到匹配串。

6、KMP算法，BM算法，KR算法的优缺点：三者中KMP算法的最坏情形下的时间复杂度最低，而平均情形则三者差不多。KMP算法最早提出，应用也最广泛，而且它的优势在于无需对正文回溯，当正文不能一次性读入内存时，这种优势是显而易见的。BM算法的平均性能也很出色，但它需要对正文进行回溯，所以当正文不能一次性读入内存时，可能会出现“抖动”，需要用双缓冲区技术来处理这一问题。KR算法的优势在于可以推广到二维模型，而且可以并行地处理，所以较多地运用于图形图像领域。

NP完全问题

1、NP类问题定义：由非确定性图灵机再多项式时间内可以计算的判定问题

2、NP困难问题与NPC问题是一类问题么？就旅行商问题和判定问题谈谈你的看法。

不一定：对于问题Q，若满足Q∈NP且Q是NP困难的，则称Q是NP完全的。旅行商问题不属于NP问题。因为我们无法在多项式时间内验证其解的正确性。当然也就不是NPC问题(NPC问题就是NP完全问题)。但他们仍然是NP困难的。旅行商判定问题则完全可以在多项式时间内检验其正确性这就是一个NP问题更进一步说他是一个NPC问题。但是无论哪种问题。都没有改变这个问题的难度。二者难度是等价的一般来说。判定问题可能属于NPC问题相应的最优问题则是NP难题

3、

概率算法

1、伪随机数的产生方法：（1）线性同余法：实现简单，速度快，具有较好的统计性能，广泛应用于仿真，但不能用于加密。（2）线性反馈移位寄存器。

2、 舍伍德算法：（1）舍伍德算法总能求得问题的一个解，且所求得解的结果总是正确的。其主要

目的是消除算法所需计算时间对输入实例的依赖。（2）当一个确定型算法最坏情况下的计算复杂性与其平均情形下的复杂度有较大差别时，可以在这个确定型算法中引入随机性将它改造成一

精品文档

精品文档

个舍伍德算法，消除或减少问题的好坏实例间的这种差别。（3）舍伍德算法的精髓不是避免算法的最坏情况行为，而是设法消除这种最坏情形行为与特定实例之间的关联性。 3、拉斯维加斯算法：（1）显著地改进算法的有效性，甚至对某些迄今为止找不到有效算法的问题，也能找到满意的算法；但它所做的随机性决策有可能导致算法找不到需要的解。

（4） 由于后者的原因，通常用boolean型方法表示拉斯维加斯型算法。

4、蒙特卡洛算法：（1）蒙特卡罗算法用于求解问题的准确解。（2）蒙特卡罗算法能求得一个解，但未必是正确的。其求得正确解的概率依赖于算法所用的时间。所用时间越多，得到正确解的概率就越高，但它的缺点也在于此。在一般情况下，无法有效地判定所得到的解是否肯定正确。

数据压缩算法

1、被压缩的对象：物理空间，即数据存储介质的尺寸。时间区间，传输消息集合所需要的时间。电磁频谱区域，如为传输消息的带宽等。

2、ASCII码压缩方法是一种经过两级压缩之后可以减少56.25%的存储空间的算法，它之适用于纯数字。

压缩方法：

把原始数据两两分组。然后把每个两位数化成十六进制。然后每8个一组。把第八个十六进制对应的二进制最高位(最左边)去掉。分别填在前面七个的最高位。就可以了

3、哈夫曼编码：哈夫曼编码的长度笔筒，它的基本理论基于下列定理：在变长编码中，若各码字长度严格按照所对应的符号出现概率的大小逆序排列，则其平均长度最小。 结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。

树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和。拥有最小带权路径长度的二叉树称为最有二叉树或者哈夫曼树。

编码方法：先构造哈弗曼树。就是每次每次选取最小的两个作为子节点生成一个父节点。父节点的值就是两个子节点的值的和然后从根节点开始往下走左节点为0右节点为1到达叶子节点经过的01就是他的编码

4、字典法：基本思想：构造一个字典，将信息中反复出现的字符串，登记为较短的字符串，解码时对这种字符串，通过查字典，转换为原字符串。最原始的字典法是模式置换压缩算法。 5、字典法存在的几个困扰的难点：（1）如何找到这些重复出现的字符串？（2）如何找到尽量长的字符串被替代？（3）怎样选用较短的字符串？如何区分原始信息中就已经存在的用于代替的字符串？

6、LZW算法：先压入所有单字符。然后读入两个字符。把前缀替换成数字。然后依次往后读入字符。如果读入后已经在表中有了就再读入一个。再把前缀换成数字。最后如果不够了可以把整个都换成数字。解压缩算法对比下压缩时的过程就知道了

精品文档