求编程领域上一些经典算法同时也是程序员必须掌握的算法

[怎样才能成为一名优秀的程序员呢]选择做程序员，是源于真正意义上的兴趣和喜欢，在做程序员的这几年，我的生活也在一步步的提升，但同样，不可否认在我个人眼里，程序员的工作就像选择其他种类的工作一样，只是一份职业，一...+阅读

这是我在一个论坛里看到的，你也参考参考吧。C++的虚函数====================== C++使用虚函数实现了其对象的多态，C++对象的开始四个字节是指向虚函数表的指针，其初始化顺序是先基类后派生类，所以该虚函数表永远指向最后一个派生类，从而实现了相同函数在不同对象中的不同行为，使得对象既有共性，又有其个性。内存池分配、回收之伙伴算法======================= 伙伴算法是空闲链表法的一个增强算法，依次建立2^0\2^1\2^2\2^3...2^n大小的内存块空闲链表，利用相邻内存块的伙伴性质，很容易将互为伙伴的内存块进行合并移到相应的空闲链表或将一块内存拆分成两块伙伴内存，一块分配出去，另一块挂入相应空闲链表，使得内存的分配和回收变得高效。

AVL树======================= AVL树是一个平衡二叉树，其中序遍历是从小到大排序的，该结构插入节点和检索非常高效，被广泛应用快速排序======================= 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

效率非常高密码学之非对称加密协议（公钥、私钥加密协议）====================== 非对称加密算法需要两个密钥，用其中一个加密产生的密文，只能通过另外一个密钥解密，密钥持有者A可以将其中一个公开，称为公用密钥，另外一个秘密保存称为私钥，这样当某人B想给A传一封秘信时，只要将密信使用A的公钥加密后，就可以放心使用各种信道将迷信传给A了，因为该密信只有A可以解密，第三者截取因为无法解密而毫无意义。

该算法很好地解决了密钥的安全传递的问题，因为公钥和加密算法都是公开的，私钥不需要传输。密码学之数字签名协议（身份鉴别、防抵赖）====================== 数字签名也是建立在非对称加密基础之上的，如果A君用它的私钥将文件加密后在发布，A君就无法抵赖该文件是其发布的，因为其他人能通过A君的公钥将文件解密就说明，如果算法可靠，该文件一定是A君用其私钥加密的。

由于非对称加密算法的加密和解密很慢，现在的数字签名并非是将其要发布的信息用其私钥加密，而是先用一个单项散列算法如（MD5）产生一个该信息的比较短的指纹（hash值），对其指纹用其私钥加密后和信息一并发布，同样达到了防抵赖的作用。无回溯字符串模式匹配-kmp算法====================== 他是根据子串的特征，当匹配失败时，不需要回溯，而是直接将字串向后滑动若干个字节，继续匹配，极大提高了匹配速度。

该算法被广泛使用。详细请参考数据结构教程。最小路径选路-迪杰斯特拉算法、弗洛伊德算法====================== 学习数据结构的时候，印象最深的就要算kmp算法和最小路径算法了，因为理解他们比较费脑子，我是不可能发明这些算法了，发明他们的都是天才，呵呵。使用最短路径的算法曾经帮人写过一个小东西，还是很有效的，记得是使用的弗洛伊德算法的一个变种，要详细了解的朋友可以查找相关资料，想将他们使用在你的项目中，代码直接从教科书上抄就可以了，不需要理解。

tcp协议之-nagle算法====================== tcp、ip中令人叫绝的想法很多，印象最深的要算nagle算法了。tcp出于效率和流量控制的考虑，发送端的数据不是产生多少就马上发送多少，一般是等到数据集聚到发送缓冲区长度的一半或者数据达到最大tcp数据包数据部分长度（好像是65515）才启动发送，而且还要看接受端可用缓冲区的大小，如果接受端产生一个回应报文通知发送端没有接受空间了，发送端哪怕缓冲区已经满了，也不会启动发送，直到接受端通告发送端其已经有了接受数据的空间了。

这样就有一个问题，假如发送端就是要发送一个小报文（比如10个字节），然后等待对方的回应。按照上面的方案，tcp会一直等数据收集到一定量才发送，于是矛盾就产生了。应用层不再发数据，tcp等不到足够的数据不会将10个字的数据发送到网卡，接收端应用层收不到数据就不会回应发送端。你也可能说，可以让修改发送端发送条件，不一定要等到足够的数据再发送，为了效率考虑，可以考虑延时一定的时间，比如说1秒，如果上层还没有数据到来，就将发送缓冲中的数据发出去。

当然这样也是可行的，尽管应用端白白等了1秒钟啥也没干，呵呵。其实nagle算法很好解决了该问题，它的做发是链接建立后的第一次发送不用等待，直接将数据组装成tcp报文发送出去，以后要么等到数据量足够多、要么是等到接受方的确认报文，算法及其简单，而且很好解决了上面的矛盾。socket之io模型设计====================== windows下socket有两种工作方式：1）同步方式2）异步方式同步socket又有两种工作模式：1）阻塞模式2）非阻塞模式阻塞模式是最简单的工作模式，以tcp的发送数据为例，如果发送缓冲区没有空间，send调用就不会返回，一直要等到能够发出一点数据为止，哪怕是一个字节，但是send返回并不表示我要发送的数据已经...