文档内容
kmp 算法
其实很简单的：（第1个肯定为0，第2个肯定为1）
就是每求一个字符的next你就看它前面一个字符串是否和从第一个字符开始的字符串相
等，如果不等就为1；如果有相等的字符串，你就看相等字符串的最大长度，如果为n，那其
next就是n+1;
如：abacd 中求d的next==>这时它前面只有c,ac,bac(bac就不用取了，因为你取bac,
那从第前面也要取三个就是aba,长度之和已超出d所在的j值，既其序号值5），而从开始的
只有a,ab没有一个相等，所以为1；
eg:求abcabdefabcg中d的next==>这时它前面有b,ab，而从开始的有a,ab(这个是相等的，
只是多匹配或少匹配），最大长度为ab的长度为2,所以为:3
求 g的next:==>它前面有 b,ba,abc,fabc,efabc，而从开始的有a,ab,abc,abca(它已不等于
fabc），所以相等的字符串只有abc,其长度为3.所以g的next为:4
还有些补充的情况：如aaabc ==>你求b时，它前面有a,aa从开始有a,aa，这时相遇了，
也就重叠了，但我们可以让它重重叠一个既第二个 a(长度之和为4没超出b的序号）,所以
aaabc的next为：01231
OSI 设备
应用层--------------->SMTP,POP3等高层协议
表示层--------------->数据压缩加密等
会话层--------------->建立应用到应用的连接
传输层--------------->TCP,UDP等
网络层--------------->IP/IPX等 设备:网关,多口网关(路由器)
数据链路层----------->PPP,帧中继等 设备:网桥,多口网桥(交换机)
物理层--------------->物理特性 设备:中继器,多口中继(集线器)
网际层协议：IP、ICMP、ARP、RARP
传输层协议：TCP、UDP
应用层协议：FTP、Telnet、SMTP、HTTP、RIP、NFS、DNS
构造哈夫曼树
如果叶子结点的权值分别为1，2，3，4，5，6，它的构造规则是这样的：
有人认为：
这里的第一步我明白了，先选1、2，构造出新结点3。第二步也明白了，选3和新结点3构造
出新结点6。但第三步不明白，为什么把4、5编作一组构造出新结点9，而不把新结点6和4
构造出新结点10？它的依据是什么？为什么是这样的？还有：在构造树的时候，两个最小结
点，谁做左子结点，谁做右子结点有无次序要求？
分析：
Created by cherish58，2010构造哈夫曼树的过程选结点的原则是，每次选其中的两个权值最小的结点，他并不管这个结
点是不是由多个结点组合而成的树的根结点。你的错误在于：认为构建树时是从剩下的结点
中找一个权值最小的结点与新构造出的树构成一棵树，而正确的思路是：在森林中选出两个
根结点权值最小的树合并构建一棵新树，被选中的不一定包括先前构建的新树，有可能是剩
下结点中的两个结点。新结点6、4、5、6中选小的两个4，5构造新结点9。而不能把新结点6
和剩下结点中权值最小的结点4组成10。
度数最小的两个结点组成子树时，无次序要求，放在左边右边都一样。
平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树
和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1
构造二叉排序树.
构造平衡二叉树
Created by cherish58，2010建初始堆
Created by cherish58，2010加密算法分类
常见的加密算法可以分成三类，对称加密算法，非对称加密算法和Hash算法。
对称密钥加密，又称私钥加密，非对称密钥加密系统，又称公钥密钥加密。SSL采用公钥加密
技术，采用tcp的443默认端口
常见的对称加密算法有：DES、3DES、AES、AFS、IDEA、RC4、RC5、RC6、Blowfish。
常见的非对称加密算法有：RSA、DSA、ECC（移动设备用）、Diffie-Hellman、El Gamal。
常见的Hash算法有：MD2、MD4、MD5、HAVAL、SHA。
排序时间复杂度
选择排序是不稳定的，算法复杂度是O(n ^2 )
直接插入排序是稳定的，算法时间复杂度是O(n ^2) ，最好情况下为O(n)
希尔排序是不稳定的，其时间复杂度为O(n ^2)
快速排序是不稳定的，最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)
堆排序是不稳定的，无论是在最好情况下还是在最坏情况下均是O(nlog n)
归并排序其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)
Created by cherish58，2010电梯调度算法：从移动臂当前位置沿移动方向选择最近的那个柱面的访问者来执行，若该方
向上无请求访问时，就改变移动方向再选择。
软件系统的可靠性计算
串联系统: R = R1×R2×R3×……×Rn
并联系统: R = 1-(1-R1)×(1-R2)×(1-R3)×……×(1-Rn)
极限编程(XP)中包含了5个价值观：沟通、简单、反馈、勇气和尊重。
各分E-R图之间的冲突主要有三类：属性冲突、命名冲突和结构冲突。
完全图和树
例1：在具有n个顶点的完全图Kn中删去多少条边才能得到树？
解：n个顶点的完全图Kn中共有n*（n-1）/2条边，
n个顶点的树应有n-1条边，
于是，应删去的边有：n*（n-1）/2-（n-1）=（n-1）*（n-2）/2
强连通图必须从任何一点出发都可以回到原处,每个节点至少要一条出路(单节点除外)
n个顶点至少要有n条边,正好可以组成一个环
广义表的长度和深度
② L=(a，b)
L是长度为2，深度为1的广义表，它的两个元素都是原子，因此它是一个线性表
③ A=(x，L)=(x，(a，b))
A是长度为2，深度为2广义表，第一个元素是原子x，第二个元素是子表L。
中缀转后缀
根据中缀表达式快速求后缀表达式
例如：a+(b*c-d/e)
根据优先级应该先算b*c，将其改为bc*，并将其看成新的操作数，此时中间结果为a+(bc*-
d/e)；
下一步应该算d/e，照上法改为de/，中间结果变为a+(bc*-de/)；
下一步应该算括号里的了，改为bc*de/-，并看成新的操作数，中间结果为a+bc*de/-；
最后一步得到最终结果是abc*de/-+。
8-(3+5)*(5-6/2)
怎样把中缀表达式转为二叉树？中缀表达式的括号怎样处理？
按照优先级加上括号，得到：( 8 - ( (3 + 5) * ( 5 - (6 / 2) ) ) )
然后从最外层括号开始，依次转化成二叉树
1、根是- ，左子树8，右子树( (3 + 5) * ( 5 - (6 / 2) ) )
2、右子树的根*，右子树的左子树(3 + 5)，右子树的右子树( 5 - (6 / 2) )
3、(3 + 5)的根+，左子树3 ，右子树5
4、( 5 - (6 / 2) )的根-，左子树5，右子树(6 / 2)
5、(6 / 2)的根/，左子树6，右子树2
Created by cherish58，2010
