EMACS & 程序编程点滴...

Quick Links

Lastupdated: 2009-10-07

基本算法集合

对字符编码进行hash

GB2312
BIG5
EUC_JP

查找

二分查找

排序

快速排序
不用比较的排序方法

字符串操作

字符串转换为16进制数
字符串中匹配内容置换

Hash表

一般的Hash Table
Hash List
Hash 红黑树
Hash AVL树

TOP对字符编码进行hash

字符编码按其区位信息,都是以Block分布的。对其进行简单的hash计算，可以很方便的确认某个编码的索引。能够应用在点阵字库映射等方面。比如以下几种编码，都是2字节的，其范围参考下表。

编码	第一字节	第二字节
	0xFC ~ 0xFE
GB2312	0xB0 ~ 0xF7	0xA0 ~ 0xFE
BIG5	0x81 ~ 0xFE	0x40 ~ 0x7E
		0xA1 ~ 0xFE
EUC_JP	0xA1 ~ 0xFE	0xA1 ~ 0xFE
S-JIS	0x81 ~ 0x9F	0x40 ~ 0x7E
	0xE0 ~ 0xEF	0x80 ~ 0xFC

TOPGB2312

GB2312编码的范围如右图所示，其中纵坐标是高字节（第一字节），横坐标是低字节（第二字节）。

首先计算纵坐标上0xB0开始到C1的偏移，然后将其结果加上横坐标上C2相对于0xA0的偏移。因为索引是由0开始的，这里我们不能忘记最后还要减去1。

1	index = (C1 - 0xB0) * (0xFE - 0xA0) + (C2 - 0xA0 - 1);

TOPBIG5

offset = (0x7E - 0x40 + 1) + (0xFE - 0xA1 + 1);
if 0x40 <= C2 <= 0x7E
   index = ((C1 - 0x81) * offset + (C2 - 0x40)) * 2;
elif 0xA1 <= C2 <= 0xFE
   index = ((C1 - 0x81) * offset + (C2 - 0xA1 + 0x7E - 0x40 + 1)) * 2;

TOPEUC_JP

/* ascII */
if (!ch1) {
    index = ch2;
} else {
    index = ((C1 - 0xA1) * (0xFE - 0xA1) + (C2 - 0xA1 - 1));
}

TOP查找

TOP二分查找

int binarysearch(DataType t)
{
    unsigned int l, u, m;
    l = 0;
    u = n-1; /* n >= 1 */
    while (l <= u) {
        m = (l + u) >> 1;
        /* 如果左值是有符号数，这里就可能溢出,所以左值用无符号数 */
        /* java中用 >>> 1 */

        if (x[m] < t)
            l = m+1;
        else if (x[m] == t)
            return m;
        else /* x[m] > t */
            u = m-1;
    }
    return -1;
}

int binarysearch3(DataType t)
{
    int l, u, m;
    l = -1;
    u = n;
    while (l+1 != u) {
        m = (l + u) >> 1;
        if (x[m] < t)
            l = m;
        else
            u = m;
    }
    if (u >= n || x[u] != t)
        return -1;
    return u;
}

int binarysearch4(DataType t)
{
    int l, p;
    if (n != 1000)
        return binarysearch3(t);
    l = -1;
    if (x[511]   < t) l = 1000 - 512;
    if (x[l+256] < t) l += 256;
    if (x[l+128] < t) l += 128;
    if (x[l+64 ] < t) l += 64;
    if (x[l+32 ] < t) l += 32;
    if (x[l+16 ] < t) l += 16;
    if (x[l+8  ] < t) l += 8;
    if (x[l+4  ] < t) l += 4;
    if (x[l+2  ] < t) l += 2;
    if (x[l+1  ] < t) l += 1;
    p = l+1;
    if (p >= n || x[p] != t)
        return -1;
    return p;
}

TOP排序

TOP快速排序

static inline int randint(int l, int u)
{
    #define RAND_MAX  (0x7FFFUL)
    return l + (RAND_MAX*rand() + rand()) % (u-l+1);
    #undef RAND_MAX
}

static void quicksort(int l, int u)
{
    int i,m;
    if (l >= u) return;
    swap(l, randint(l,u));
    m = l;
    for (i = l+1; i <= u; i++) {
        if (x[i] < x[l]) {
            swap(++m, i);
        }
    }
    swap(l,m);
    quicksort(l, m-1);
    quicksort(m+1, u);
}

TOP不用比较的排序方法

// 求累积度数 f[i]可以用bit位做
for (int i = 0; i <= 800; i++) {
    f[i] = 0;
}

for (int j = 0; j < n; i++) {
    i = d[j].point;
    f[i] = f[i] + 1;
}

for (int i = 1; i <= 800; i++) {
    f[i] = f[i] + f[i-1];
}

// sort
for (j = n-1; j >= 0; j--) {
    i = d[j].point;
    p[f[i]] = j;
    f[i] = f[i] - 1;
}

TOP字符串操作

TOP字符串转换为16进制数

通常我们用od¹, 或者其他文本编辑器将二进制文件编辑成为文本本件，或着转换为程序中定义的整形数组。而当我们想把这样的文本文件还原为二进制文件的话，却没有好的方法。下面介绍的函数讲一个文本格式的二进制字符串转换为实际的二进制文件(16进制数据)。

typedef unsigned char uint8_t;

uint8_t lookupA[23] = {
    0x00, 0x10, 0x20, 0x30, 0x40,
    0x50, 0x60, 0x70, 0x80, 0x90,
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
    0xFF, 0xFF,
    0xA0, 0xB0, 0xC0, 0xD0, 0xE0, 0xF0
};

uint8_t lookupB[23] = {
    0x00, 0x01, 0x02, 0x03, 0x04,
    0x05, 0x06, 0x07, 0x08, 0x09,
    0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
    0xFF, 0xFF,
    0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F
};

inline int little_endian(void)
{
    int i = 0x01;
    return *(uint8_t*)&i == 0x01;
}

void txt_to_hex(uint8_t* hex, const uint8_t* txt, int length)
{
#if 0
/* 包含大写字符 */
    int i, a, b;
    if (little_endian()) {
        for (i = 0; i<length; i++) {
            a = (int)txt[i << 1] - '0';
            b = (int)txt[(i << 1) + 1] - '0';
            hex[length-i-1] = lookupA[a] + lookupB[b];
        }
    } else {
        for (i = 0; i<length; i++) {
            a = (int)txt[i << 1] - '0';
            b = (int)txt[(i << 1) + 1] - '0';
            hex[i] = lookupA[a] + lookupB[b];
        }
    }
#else
/* 包含小写字符 */
    int i;
    int slength = strlen((char*)txt);
    if (little_endian()) {
        for (i = 0; i < slength; i+=2) {
            hex[length - i/2 - 1] = txt[i]%87%48 << 4 | txt[i+1]%87%48;
        }
    } else {
        for (i = 0; i < slength; i+=2) {
            hex[i/2] = txt[i]%87%48 << 4 | txt[i+1]%87%48;
        }
    }
#endif
}

int APIENTRY WinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPSTR     lpCmdLine,
                     int       nCmdShow)
{
    uint8_t str[] = "ef1234";
    char tt[32] = {0};
    int temp = 0;
    txt_to_hex((uint8_t*)&temp, str, sizeof(temp));
    sprintf(tt, "----- 0x%X -----\n", temp);
    OutputDebugString(tt);
    return 0;
}

TOP字符串中匹配内容置换

static inline char* strrepl(char *orgstr,
                            uint32_t maxsize,
                            char *oldstr,
                            char *newstr)
{
    int oldlen, newlen;
    char *s, *p;
    s = orgstr;
    oldlen = strlen(oldstr);
    newlen = strlen(newstr);

    while (s) {
        p = strstr(s, oldstr);
        if (p == NULL )
            return orgstr;
        if (orgstr == NULL)
            return NULL;
        if (strlen(orgstr)-oldlen+newlen+1 > maxsize) {
            return NULL;
        }
        memmove(p + newlen, p + oldlen, strlen(p + oldlen) + 1);
        memcpy(p, newstr, newlen);
        s = p + newlen;
    }
    return orgstr;
}

1. linux的命令之一，用来按指定形式输入文件

TOPHash表

程序中经常用到Hash表，它具有插入，查找效率高等特点。这里总结一些hash表的用法。包括Hash List，Hash 红黑树，Hash AVL树等。

TOP一般的Hash Table

特点: 插入效率高，查找效率高，不支持有序输出

TOPHash List

特点: 除了具有一般hash表的特点外，增加了排序的功能。

TOPHash 红黑树

特点: 除了具有hash list的特点以外，还支持模糊查找。具体：

查找速度：哈希表 > 红黑树
插入/删除速度：等于哈希表和红黑树之和
按哈希表查找后可以按红黑树有序输出，避免了哈希表的数据无序，以及红黑树查找慢的不足

TOPHash AVL树

特点: 查找/插入/删除的效率都有所提高。如图所示，每个bucket指向的不是list而是一颗AVL树。

EMACS & 程序 编程点滴...