输入一个长为2^k（k≤8）01串s，按照"ABC编码规则"进行编码，ABC编码规则是：
     {  A             //若s串全是0
T(s)={  B             //若s串全是1
     {  CT(s1)(s2)    //否则把s串分成两个等长的字串s1和s2

例如：
    T(01001011)
   =CT(0100)T(1011)
   =CCT(01)T(00)CT(10)T(11)
   =CCCT(0)T(1)ACCT(1)T(0)B
   =CCCABACCBAB

1 对每个字串求和 if（sum=0）s1=A;if(sum=length) s1=B;
2 递归。mid=s.length/2;

就是具体的函数我怎么也写不出来，你能不能写一个让我看一下。感觉递归里有些细节想不明白。。

// 查找第一个字符 子 字串
char *str_char_n(char *p, int nLen, char ch)
{
    for (int i = 0; i < nLen; i++)
    {
        if (p[i] == ch) return p + i;
    }
    return NULL;
}

// 递归编码 s_out带出结果
void e_code_recursive(char *p, int nLen, std::string *s_out)
{
    // 外面确保已经是 全 01 串
    char *p1 = str_char_n(p, nLen, '0');
    char *p2 = str_char_n(p, nLen, '1');
    if (p1 != NULL && p2 != NULL)
    {
        // CT(s1)(s2)    //否则把s串分成两个等长的字串s1和s2
        std::string s1 = "";
        std::string s2 = "";
        e_code_recursive(p, nLen / 2, &s1);
        e_code_recursive(p + nLen / 2, nLen / 2, &s2);
        *s_out = "C";
        *s_out += s1;
        *s_out += s2;
    }
    else if (p1 != NULL)
    {  // A             //若s串全是0
        *s_out = "A";
    }
    else if (p2 != NULL)
    {  //B             //若s串全是0
        *s_out = "B";
    }
}

// 检测字符串并且编码，如果字符串不合 01 串并且长度不为2 到n倍数，返回false
bool e_code(char *p, std::string *s_out)
{
    int nLen = strlen(p);
    if (nLen == 0) return false;
    int nSize = nLen;
    // 检查是否为2^n
    while (nSize > 1) {
        if (nSize & 1) return false;
        nSize = nSize>>1;
    }
    // 检查是否为 全部0 1 串
    for (int i = 0; i < nLen; i++)
    {
        if (p[i] != '0' && p[i] != '1') return false;
    }
    // 递归编码
    e_code_recursive(p, nLen, s_out);
    return true;
}
int main(void)
{
    std::string s = "";
    // e_code("0011100000111001", &s);
    char str[] = {"01001011"};
    e_code(str, &s);
    printf("%s -> %s \n", str, s.c_str());
    getchar();

    return 0;
}



C:\Users\yuccn>C:\code\test\vecter\Debug\vecter.exe
01001011 -> CCCABACCBAB



[ 本帖最后由 yuccn 于 2013-4-11 13:19 编辑 ]

给你个简单 但没有效率的方案 递归过程若干重复比较 不过你最大只有256个 要是对海量数据编码的话 这样递归不是个办法

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void code_ABC(char *beg, char *end, char *res);

int main()
{
    int k, n;
    char *src, *res;
    
    printf("Enter k: ");
    scanf("%d", &k);
    
    n = (int)pow(2, k);
    if ((src=(char*)malloc(n)) == NULL) exit(1);
    if ((res=(char*)malloc(n+k)) == NULL) exit(1);
    
    printf("Enter the string [0|1]: ");
    scanf("%s", src);
    
    code_ABC(src, src+n, res);    
    printf("The code result is: %s", res);
    
    return 0;
}


void code_ABC(char *beg, char *end, char *res)
{
    static int i = 0;
    char *p = beg;
    
    while (p < end && *p == *beg) p++;
    
    if (p < end) {
        res[i] = 'C';
        res[++i] = '\0';
        
        code_ABC(beg, beg + (end-beg)/2, res);
        code_ABC(beg + (end-beg)/2, end, res);
    }
    else {
        res[i] = (*beg == '0' ? 'A' : 'B');
        res[++i] = '\0';
    }
}

谢了，只是能不用指针么？不用指针好像能做出来的

谢了，但是能不用这么复杂的么？好多没见过

你能不用计算机吗？ 用笔好像就能算出来

呵呵  经典

版主能给出解码方法吗？ 我想了两节课都没想出来，就是根据编码结果很难推出源字符串的长度……希望指教。
如 0011 是 CAB
   00001111 也是CAB
如何解码呢？


[ 本帖最后由 yctchxf 于 2013-4-12 09:51 编辑 ]