C/C++面试之算法系列--怎么实现用更少的空间表明英文字母(a ~ z)构成char A[n]字符串ITeye - 凯发娱乐

C/C++面试之算法系列--怎么实现用更少的空间表明英文字母(a ~ z)构成char A[n]字符串ITeye

2019年02月23日14时32分44秒 | 作者: 昆谊 | 标签: 字符,字符串,数组 | 浏览: 2174

但“字节紧缩”算法的转化功率为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)函数么? 有爱好的朋友能够参阅前面的帖子“从“整数转化成字符串”看算法的联想”
版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表凯发娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章