DNS

泛型编程（Generic Programming）最初提出时的动机很简单直接：发明一种语言机制，能够帮助实现一个通用的标准容器库。所谓通用的标准容器库，就是要能够做到，比如用一个List类存放所有可能类型的对象,这样的事情；熟悉一些其它面向对象的语言的人应该知道，如Java里面这是通过在List里面存放Object引用来实现的。Java的单根继承在这里起到了关键的作用。然而单根继承对C++这样的处在语言链底层的语言却是不能承受之重。此外使用单根继承来实现通用容器也会带来效率和类型安全方面的问题，两者都与C++的理念不相吻合。

阅读全文

SQLITE 原子提交原理

Peach

2013-01-28

摘要

本人正在做一个项目，在项目中定义了自己的文件格式，为了做到停电或程序崩溃不损坏这些文件原有的数据，故针对操作的原子性做一些思考，后来看到sqlite的这篇文章，与自己的实现方式作了一些对比。故顺手在研究此文章的时候将大意译成了中文。毕竟只是一时顺手之作，应该存在不少的误读与错误，请多多包涵，此文章的原始地址在http://chensheng.net/p/sqlite/auto_commit_zh_cn.html，本文可以转载，但请保留出处，以便他人能够方便找到我在修改此文可能的错误之后重新发布的版本。如果发现错误请发mail给我erehw#163.com。

阅读全文

最长不重复子串

Peach

2013-01-22

问题：找到一个字符串中的一个连续子串，这个子串内不能有任何两个字符是相同的，并且这个子串是符合要求的最长的。

void lnorepstr(char*  s)
{
    char A[26];
    int  i, j;
    int  maxi, maxlen = 0;
    int  len = strlen(s);

//    for(i = 0; i < 26; i++)
//        A[i] = -1;

    memset(A, -1, 26);
    for (i = 0; i < len; i++)
    {
        A[s[i] - 'a'] = 1;
        for(j = i+1 ; j < len; j++)
        {
            if(A[s[j]-'a'] == -1) //该字符没有出现
            {
                A[s[j]-'a'] = 1;
                if(j - i> maxlen)
                {
                    maxlen = j - i;
                    maxi = i;
                }
            }
            else
                break;
        }
        memset(A, -1, 26);
    }
    printf("longest no repeat string: %.*s\n", maxlen+1, &s[maxi]);
}

假设字符串全部是由小写字母组成，则内层循环最多执行26次，即最长不重复子串的长度为26，此时，时间复杂度为O(26n)。

阅读全文

快速排序

Peach

2013-01-14

快速排序的基本思想是：从待排序列中任取一个，作为支点。凡关键字小于支点的记录均移动至支点之前，大于支点的记录均移动至支点之后。经过一趟排序后，待排序列将分割成两个子序列，分别进行上述操作。

阅读全文

二分查找

Peach

2013-01-14

二分查找算法基本思想

二分查找算法的前置条件是,一个已经排序好的序列(在本篇文章中为了说明问题的方便,假设这个序列是升序排列的),这样在查找所要查找的元素时,首先与序列中间的元素进行比较,如果大于这个元素,就在当前序列的后半部分继续查找,如果小于这个元素,就在当前序列的前半部分继续查找,直到找到相同的元素,或者所查找的序列范围为空为止.

阅读全文