主题:关于简单压缩算法的问题【已解决】
3751002
[专家分:160] 发布于 2011-03-08 20:58:00
[code=c]
/*
* 压缩
* src原字符串指针,comped压缩后字符串保存
*/
void compress(const char *src, char *comped)
{
char pre = *src++; //前一个字符
char n = 0; //重复次数
if(pre == 0) //输入非法
exit(1);
*comped++ = pre;
while(*src != 0) {
if(*src == pre) { //发现重复字符
while((*src == pre) && (*src != 0)) { //计算重复次数
n++; src++;
}
if(*src == 0) //遍历结束
break;
*comped++ = pre; *comped++ = n; pre = *src; n = 0;
}
else //没有发现重复字符
pre = *src;
*comped++ = pre; src++;
}
*comped = 0; //字符串结束
}
/*
* 解压缩
* comped压缩字符串指针,str还原字符串保存
*/
void uncompress(const char *comped, char *str)
{
int count = 0, i; //重复次数
char temp = 0; //保存重复字符
char pre = *comped++; //保存comped指针上一字符
if(pre == 0)
exit(1);
*str++ = pre;
while(*comped != 0) {
for(i = 0; i < count; i++) //恢复重复字符
*str++ = temp;
if(count != 0) //记录重复次数下一字符
*str++ = pre;
count = 0;
if(*comped == pre) {
count = (int)*++comped; temp = pre; comped++;
if(*comped == 0) //解压缩完成
break;
if(*(comped + 1) == 0) {
pre = *comped; *str++ = pre; break;
}
pre = *comped++;
}
else {
pre = *comped++; *str++ = pre;
}
}
if(count != 0) //未来得及处理的重复次数
for(i = 0; i < count; i++)
*str++ = temp;
*str = 0; //字符串结束
}
[/code]
3.10 时隔两天,回头重看了这段代码,增加了一点判断。
这次作出注释,希望大家帮忙指正。
非常感谢
3.11 修正一个Bug. 我在想会不会是我测试方法的问题。 希望哪位可以提供下测试方法
3.11晚 ok 问题出在while((*src == pre) && (*src != 0)) 判断时迷糊了。 已经正常工作。
3.15 改善第二版的存储结构,格式为c0,c1,c1,[x],c2 重复次数只能记录255以内 c:字符 x:重复次数
end:告一段落。尝试别的结构来实现。
最后更新于:2011-03-15 15:32:00
回复列表 (共10个回复)
沙发
fragileeye [专家分:1990] 发布于 2011-03-09 15:38:00
while(*src != pre)
{
n++;
src++;
}
这段,感觉while里应该是 == ,有的变量没加注释,实在无心看了、、个人感觉这个压缩对于cool这种单词无能为力了……
板凳
3751002 [专家分:160] 发布于 2011-03-10 16:41:00
[quote]while(*src != pre)
{
n++;
src++;
}
这段,感觉while里应该是 == ,有的变量没加注释,实在无心看了、、个人感觉这个压缩对于cool这种单词无能为力了……[/quote]
现在作出了比较详细的注释
谢谢LS的关注
3 楼
fragileeye [专家分:1990] 发布于 2011-03-10 18:41:00
[code=c]
#include <stdio.h>
#define MAX_WORDS 80
unsigned char compress(const char * src, char * comped);
int main(int argc, char *argv[])
{
char src[MAX_WORDS] , comped[MAX_WORDS];
unsigned char comped_num ;
puts("please init the array src");
fgets(src,MAX_WORDS,stdin);
comped_num = compress(src,comped);
printf("the phrase after being compressed is:%s\n",comped);
printf("and there are %i word being compressed .\n",comped_num);
return 0;
}
unsigned char compress(const char *src,char *comped)
{
unsigned char n = 0; //统计重复次数
char *now = src ,*store = comped;
char pre = *src; //前一个字符且初始化
while(*now != '\0')
{
*store++ = pre ; //存储压缩后的字符
while(*now == pre && *now != '\0') //如果重复字符了则后移指针
{
n++;
now++;
}
if(*now == '\0') //循环结束
{
break;
}
else //进行调整操作,开始记录新的未与pre重复的字符
{
pre = *now;
now ++;
}
}
*store = '\0' ;
return n;
}[/code]
简单的写了没经过严密思考过的一小段,记录重复字符的可能有错。。不过希望这些帮lz整理下思路、、
4 楼
3751002 [专家分:160] 发布于 2011-03-10 21:45:00
思路上只可以压缩coooool这种可以保证正确吧
不过非常感谢楼上花费时间写的代码
5 楼
fragileeye [专家分:1990] 发布于 2011-03-10 22:13:00
不明白lz的要求了……
6 楼
3751002 [专家分:160] 发布于 2011-03-10 23:20:00
我的代码想实现的是比如一个字符串"I liiiiiiiiiiiiiiike yooooooooou verrrrrrry much!"
压缩函数将该字符串转化成字符串"I li(14)ke yo(8)u ver(6)y much!"
然后根据已压缩的字符串还原
()内表示之前字符重复次数
因为直接是存储在char类型中,为了区分字符和重复次数,也为了简化问题,暂时只能压缩31次以内重复字符。 ASCII码中,空格的十进制是32
不知与ASCII的前30个不可显示字符有关,也曾想过迁移到高的地方。
不知道这个描述清楚吗?
7 楼
fragileeye [专家分:1990] 发布于 2011-03-10 23:25:00
lz试试那段代码,貌似可以解决吧……不过压缩字数确实有问题,lz觉得如何控制呢
8 楼
3751002 [专家分:160] 发布于 2011-03-11 13:07:00
LS提供的代码修改个小地方可以实现cooool的正常压缩
但是如果测试cool liike,就会出现截断情况
并且不能有效还原,n值记录所有压缩的次数
哦,发现了个bug,在出现重复字符时,comped并没有记录下一个字符。今天一天的课,熬完后再回来修改。
9 楼
fragileeye [专家分:1990] 发布于 2011-03-11 15:55:00
出现cool这样的单词,肯定不行的啊。思路都不能这样 啊、、那样的话得配个字典,然后判断能不能覆盖单词中重复字母……呵呵、、
10 楼
3751002 [专家分:160] 发布于 2011-03-11 23:10:00
已经解决 谢谢ls这么长时间的关注
我来回复