C字符串压缩算法
jopen
11年前
#include <iostream> #include <stdlib.h> #include <algorithm> using namespace std; void stringZip( const char* pInputStr, long lInputLen, char* pOutputStr ) { if( !pInputStr || lInputLen <= 1 || !pOutputStr ) return; memset( pOutputStr, 0, lInputLen ); char cValue = *pInputStr;//重复字母对比值 long lCount = 0;//单一字符重复字母个数 int iIndex = 0;//pInputStr迭代位置 int iCur = 0;//pOutputStr当前指针偏移 int iNumLen = 0;//压缩字母的个数长度 char buf[16];//字母长度缓存 while( lInputLen-- ) { if( cValue == *( pInputStr + iIndex++ ) ) {//遇到重复字符 lCount++;// } else { if( lCount > 1 ) {//重复字符 memset( buf, 0, 16 ); itoa( lCount, buf, 10 ); strcat( pOutputStr, buf ); iNumLen = strlen( buf ); } iCur += iNumLen; *( pOutputStr + iCur ) = cValue;//append字符 iCur++; cValue = *(pInputStr + iIndex - 1);//取下一个待比较的字符 //重新计算位置 iIndex--; lInputLen++; //重置计数器 iNumLen = 0; lCount = 0; } } } char* stringUnzip( const char* pStrIn ) {// if( !pStrIn || !strlen( pStrIn ) ) return NULL; long lLen = strlen( pStrIn ); const int INCREMENT = 1024; //先将结果字符串设置为输入字符串的5倍大小 long lCurNums = 5 * lLen * sizeof( char ); char* pStrOut = (char*)malloc( lCurNums ); if( !pStrOut ) return NULL; memset( pStrOut, 0, lCurNums ); long lNum = 0;//重复字母个数 int iNumLen = 0;//重复字母长度 int iCur = 0;//结果集当前指针偏移 char numBuf[16];//用于计算数字长度 char cValue; //临时字符值 const long constLen = lLen; long lIndex = constLen - lLen;//pStrIn的字符串偏移值 int i; while( lIndex < constLen ) { lIndex = constLen - lLen;// lNum = atoi( ( pStrIn + lIndex ));//字符个数 if( lNum > 0 ) {//字符个大于1 if( iCur + lNum >= lCurNums -1 ) {//空间不足 lCurNums += INCREMENT; pStrOut = (char*)realloc( pStrOut, lCurNums ); if( !pStrOut ) return NULL; } memset( numBuf, 0, 16 ); itoa( lNum, numBuf, 10 ); iNumLen = strlen( numBuf );//取数字长度 cValue = *( pStrIn + lIndex + iNumLen );//取压缩的字符 for( i = 0; i < lNum; i++ )//还原压缩的字符 { *( pStrOut + iCur++ ) = cValue; } } else {//未压缩的单一字符 if( iCur >= lCurNums -1 ) {//空间不足 lCurNums += INCREMENT; pStrOut = (char*)realloc( pStrOut, lCurNums ); if( !pStrOut ) return NULL; } *(pStrOut + iCur++ ) = *( pStrIn + lIndex + iNumLen ); } lLen = lLen - iNumLen - 1;//计算偏移值 iNumLen = 0; } return pStrOut; } int main( int argc, char* argv[] ) { char* pInStr = "aaaabasdfaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccddddeeeadfaadfa"; int iLen = strlen( pInStr ) + 1; char* pOutStr = (char*)malloc( iLen ); memset( pOutStr, 0, iLen ); //压缩字符 stringZip( pInStr, iLen, pOutStr ); puts( pOutStr ); //还原压缩的字符 char* pUnzipStr = stringUnzip( pOutStr ); puts( pUnzipStr ); free( pUnzipStr ); pUnzipStr = NULL; return 0; }