C/C++面试之算法系列－－如何实现用更少的空间表示英文字母（a ~ z）构成char A[n]字符串

本文转自CSDN：http://blog.csdn.net/zhangfulin_hwatop/article/details/8171520

 

××××××××××××××××××××××××××××××××

“如何实现用更少的空间表示英文字母（a ~ z）构成char A[n]字符串” 

××××××××××××××××××××××××××××××××

 

在嵌入式的通信协议开发过程中由于通信实时性等因素要尽量缩短传输报文的长度，即每一个字节的各位都应该重复利用上；

但是在实际的传输过程中，由于传输报文的某些特性，可以考虑将字符进行编码压缩，再传输，这样就可以有效的利用网络带宽；

在接收端再根据压缩的协议对数据进行解码，即可恢复原始的数据序列。

 

下面“用更少的空间表示这个字符串吗？”本质上就是考的压缩算法，只是问题的问法可能不会一下子让大家想到这个方面而已。当我们抓住了问题的本质就会找到合理的解决方案。

“字节压缩”算法是最容易想到的，但关键在于如何将五位数组织起来的同时保证编解码的时间效率，要编码解码方便。

 

以前在一个485的通信协议中遇到了一个问题，使我在这里产生了一点灵感。

在的通信协议中，因为要连续传输多个字节我们设置了0x55传输起始符，0xAA传输结束符号，但在实际的传输数据过程中数据本身可能为0xAA，这就导致了对数据结束判断的失误，一种方法是利用转义字符来解决的，即连续发送两个0xAA表示此0xAA不为结束符，而是正常有效数据；我们采取了另一种方法，即将待传输的连续8个数据（第一个数据的高位恒为0）的高位取出，构造一个新的数据传输出去，这样就解决了0xAA的问题。

 

利用上面的思想，我想到了将五位分解成4 + 1 的方式，即每个数分解成两部分，两个4组合成1个字节，这样连续连续8个字符即可组合成5个字符进行传输了；8、4的编码效率比顺序每5位一存的效率要高。

 

而“26进制编码”的思想是借鉴了面试中长考的几个函数的思想。

而对于“12356819”类型的十进制的字符串转化为十进制的int数，不就是常考的atio(char *in)函数么？考虑过“011000010100”二进制的字符串么？八进制“23104762”呢？

相信这个时候你应该明白了26进制字符串“adkjflmgdsjkflkmgzxy”的存储转换原理了吧

而其解码过程不就是itoa(int k, char *out)函数么？

 

比较而言，“26进制编码”的思想实现起来更为简单，因为有这么多函数可以借鉴，其转换的时间效率更高。但是这个思想不一定很容易想到。

但“字节压缩”算法的转换效率为5/8，节省3/8，而“26进制编码”最多节省1/3，因此“字节压缩”在大量数据需要压缩的情况下存储效率更好。

 

××××××××××××××××××××××××××××××××

××××××××××××××××××××××××××××××××

 

字符串A是由n个小写英文字母（a ~ z）构成的，定义为char A[n]。你能用更少的空间表示这个字符串吗？请写出实现原理和节省的空间比率. 请写出从char A[n]到你的新的储存格式的转换函数。（请用C/C++编程，不允许上机操作）

 

××××××××××××××××××××××××××××××××

 

一 字节压缩

 

实现原理：因为a~z的ascii码用不了一个字节表示，减小‘a’后每个字符实际上代表了0－26，五个bit即可表示，压缩后，能省3/8的空间，关键在于如何组织存储顺序便于检索和存储，同时要考虑存储的时间效率

如果将五位按照顺序依次存储，一不好保存，二不好访问

访问按照字节进行，应尽量将m个数组合成n个字节，能否将8个字符存成5个字节呢？

 

因此考虑就5位再拆下，分解成最高位和低四位，这样每两个字符就可以转换成一个新的数了；每8个字符的最高位可组合成一个字节；4、8的规律性很强，组合分解都很方便

 

××××××××××××××××××××××××××××××××

 

#define LOWMASK 0x0f

#define HIGHMASK (1<<4)

#define CHARLEN 7

 

输入参数：inarray[] 待编码的字符数组；inlen数组的长度

输入参数：outarray [] 编码后的字符数组；outlen编码后数组的长度

// unsigned char outarray[]编码后的字符数组用到了最高位，是有效位，非符号位

void   CodeChar(const char inarray[],unsigned int inlen,unsigned char outarray[], unsigned int &outlen)

{

       int InIndex = 0;

       int OutIndex = 0;

       int CompoudIndex = 0;

       int CompoudValue = 0;

       int tempchar = 0;

 

       while(inlen--)

       {

              tempchar = inarray[InIndex] - 'a'; //将字符换成数字0－26

 

              if(InIndex%2 == 0)              //偶数位存放在每个字符的高位

                     outarray[OutIndex] = ( tempchar & LOWMASK) << 4;

              else         // 奇数位存放在每个字符的低位

                     outarray[OutIndex] |=(tempchar & LOWMASK);

             

              if((InIndex%2 == 1) && (InIndex != 0)) // 存放完两个数后，增加输出数组的下标

                     OutIndex++;

             

              // 将每个字符的第五位存放起来，0－7分别对应此字符的第7－第0位

              CompoudValue |= ((tempchar & HIGHMASK) << 3) >> (InIndex%8);

 

              CompoudIndex++;

              if(CompoudIndex == sizeof(char) * 8)// 存放了八个数后，将合成值保存到输出数组

              {    

                     CompoudIndex = 0;

                     outarray[OutIndex] = CompoudValue;

                     OutIndex++;

              }

              InIndex++;

       }

 

       if(InIndex%2 == 1)       // 某个输出字符只用了高四位，但保存合成值的输出下标未增加

       OutIndex++;

 

       if(CompoudIndex != 0) // 此时说明输入数组个数非8的倍数，最后一个合成值上面未保存

       {

                     outarray[OutIndex] = CompoudValue;

                     OutIndex++;

       }

 

       outlen =OutIndex; // 保存转换完毕后的输出数组长度

}

 

// 输入参数：inarray 上面编码后的数组；inlen编码后的数组长度；outk待解码字符在原数组中的下标位置

// 输出参数：outchar解码的码值；inlen编码后的数组长度

void   DecodeChar(const unsigned char inarray[],unsigned int inlen, unsigned int outk, char &outchar)

{

 

       int CompoudIndex = 0;

       int HighValue = 0;          // 待解码字符的第五位(转换为0－26之后的)

       int LowValue = 0;          // 待解码字符的低四位(转换为0－26之后的)

       int CompoudValue = 0;   // 解码后的值

 

       if(((outk+8)/8 * 5 - 1) < inlen)     // 待解码字符的最高位不在最后一个合成值内

              HighValue = ((inarray[((outk+8)/8 * 5 - 1)] >> (CHARLEN - (outk%8))) & 0x01) << 4;

       Else // 待解码字符的最高位在最后一个合成值内

       {

              HighValue = ((inarray[inlen-1] >> (CHARLEN - (outk%8))) & 0x01) << 4;

       }

 

 

       if(outk%2 == 0)     // 偶数保存在高位

              LowValue = inarray[outk/2+outk/8] >> 4;

       else

              LowValue = inarray[outk/2+outk/8] & LOWMASK;

 

       CompoudValue = HighValue | LowValue;       //解码后的数字

       CompoudValue += 'a';    // 解码后的字符

 

       outchar = CompoudValue;

}

 

 

void   main(void)  

{  

       char *in = "abcdefghijklmnuvw";

       unsigned char out[100] = {0};

       int outindex = 0;

       unsigned int outcount;

       int incount = strlen(in);

       float coderatio = 0;

       char outchar;

      

       while(outindex < 100)

              out[outindex++] = 0;

 

       CodeChar(in,incount, out, outcount);

       out[incount] = '/0'; // 编码

 

       cout<<outcount<<endl;

       printf("%s",out);

 

       coderatio = (float)outcount/incount;

       printf("%6f",coderatio);

 

       outindex = 0; // 解码

       while(outindex < incount)

       {

       DecodeChar(out,outcount,outindex,outchar);

       cout<<outchar<<endl;

       outindex++;

       }

 

}

 

××××××××××××××××××××××××××××××××

××××××××××××××××××××××××××××××××

 

二  26进制编码

    
26个字母就当作26进制，然后每6个字母转换为一个long,32位的 4 个字节..  压缩1/3  

0－26个当作26进制对应的26个数符，把6个字符组成的字符串当作一个26进制的数.，转换为10进制整数，刚好范围可以被32位long容纳,不过存在一点点浪费.   
比如a代表1,b代表2 ，ab代表26进制的12, 即十进制的28;

 

反过来从long X得到原始的字符

X/26^5即得到六个字符的高位，依次类推；但对于最后一个整型数应该特殊考虑。

就相当于十六进展和十进制的转换问题

 

××××××××××××××××××××××××××××××××

 

#define AZMAX 26

//输入参数：inarray[] 待编码的字符数组；inlen数组的长度

//输入参数：outarray [] 编码后的整型数组；outlen编码后数组的长度

// unsigned int outarray[] 编码后的整型数组用到了最高位，是有效位，非符号位

void AzCodeChar(const char inarray[],unsigned int inlen, unsigned int outarray[], unsigned int &outlen)

{

       int InIndex = 0;

       int OutIndex = 0;

       unsigned int CompoudValue = 0;

 

       while(inlen--)

       {

              CompoudValue = CompoudValue* AZMAX + (inarray[InIndex] - 'a'); // 将字符换成数字0－26

              InIndex++;

              // 按照字符的顺序依次乘26，即把各个数对应的值的和求出来了

 

              if(InIndex%6 == 0)              //六个字符转化为一个整型数

              {

                     outarray[OutIndex] = CompoudValue;

                     CompoudValue = 0;

                     OutIndex++;

              }           

       }

 

       if(InIndex%6 != 0) //不足六个字符，上面未保存

       {

                     outarray[OutIndex] = CompoudValue;

                     CompoudValue = 0;

                     OutIndex++;

       }

 

       outlen =OutIndex; // 保存转换完毕后的输出数组长度

}

 

// 输入参数：inarray 上面编码后的数组；inlen编码后的数组长度；outindex待解码字符在原数组中的下标位置；outlen待解码字符的原数组总长度（比按5位编码多了一个参数）

// 输出参数：outchar解码的码值

void   AzDecodeChar(const unsigned int inarray[],unsigned int inlen, unsigned int outindex, unsigned int outlen, char &outchar)

{

 

       int DecodeValue = 0;      // 解码后的值

       unsigned int DevideIndex = 0;

       unsigned int DevideValue = 1;

 

       if(outindex < (inlen - 1)*6)    //待解码字符不在最后一个合成值内

       {    

              DevideIndex = 5 - outindex%6;     //得到待除的数基于26的幂指数           

       }

       else // 待解码字符在最后一个合成值内

       {

              DevideIndex = 5 - (inlen*6 - outlen)- outindex%6;// 此时最高位的意义变小了

       }

 

       while(DevideIndex > 0)

       {

              DevideValue *= AZMAX;       //得到待除的数26^ DevideIndex

              DevideIndex--;

       }

 

       DecodeValue   = (inarray[outindex/6]/DevideValue)%AZMAX;// 得到当前的个位数

 

       outchar = DecodeValue + 'a';

}

 

void   main(void)  

{  

       char *in = "abcdefghijklmnuvw";

       unsigned int out[100] = {0};

       int outindex = 0;

       unsigned int outcount;

       int incount = strlen(in);

       float coderatio = 0;

       char outchar;

      

       while(outindex < 100)

              out[outindex++] = 0;

 

       AzCodeChar(in,incount, out, outcount);

       cout<<outcount<<endl;

 

       coderatio = (float)outcount * sizeof(int)/incount;

       printf("%6f/n",coderatio);

 

       outindex = 0; // 解码

       while(outindex < incount)

       {

       AzDecodeChar(out, outcount, outindex, incount, outchar);

       cout<<outchar<<endl;

       outindex++;

       }

 

}

 

××××××××××××××××××××××××××××××××

××××××××××××××××××××××××××××××××

 

细心的读者可能会发现，上述将字符串看成26进制的字符串，然后再将其编码为十进制，即int类型存起来；

而对于“12356819”类型的十进制的字符串转化为十进制的int数，不就是常考的atio(char *in)函数么？考虑过“011000010100”二进制的字符串么？八进制“23104762”呢？

相信这个时候你应该明白了26进制字符串“adkjflmgdsjkflkmgzxy”的存储转换原理了吧

而其解码过程不就是itoa(int k, char *out)函数么？

有兴趣的朋友可以参考前面的帖子“从“整数转换成字符串”看算法的联想”