SQLITE 原子提交原理

摘要

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

最长不重复子串

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

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)。

快速排序

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