qq_38608195 2018-04-17 18:10 采纳率: 100%
浏览 1070
已采纳

关于HUFFMAN利用数组压缩的算法问题

整体代码如下,具体关于问题在最下方,
struct head
{
unsigned char b; /*the charactor*/
long count; /*the frequency*/
long parent,lch,rch; /*make a tree*/
char bits[256]; /*the haffuman code*/
}
header[512],tmp;

void compress()
{

clock_t start,end;
char filename[255],outputfile[255],buf[512];
int fn = 0, sz = 0, sz1 = 0;
double x = 0;
unsigned char c;
long i,j,m,n,f;
long min1,pt1,flength;
FILE ifp,*ofp;
printf("源文件名:");
gets_s(filename);
ifp=fopen(filename,"rb");
if(ifp==NULL)
{
printf("源文件打开失败!\n");
return;
}
fn = _fileno(ifp); /
取得文件指针的底层流式文件号*/
sz = _filelength(fn);/*根据文件号取得文件大小*/
printf("文件大小为:%d B.\n", sz);
sz1 = sz;
printf("压缩后文件名:");
gets_s(outputfile);
start=clock(); /* 计时开始 */
ofp=fopen(outputfile,"wb");
if(ofp==NULL)
{
printf("压缩文件打开失败!\n");
return;
}
flength=0;

while(!feof(ifp))
{
fread(&c,1,1,ifp);//读数据
header[c].count++; //字符重复出现频率+1
flength++; //字符出现原文件长度+1
}
flength--;
header[c].count--;//减一平衡位数
for(i=0;i {
if(header[i].count!=0)
header[i].b=(unsigned char)i;
/*将每个哈夫曼码值及其对应的ASCII码存放在一维数组header[i]中,
且编码表中的下标和ASCII码满足顺序存放关系*/
else header[i].b=0;
header[i].parent=-1; //对结点进行初始化
header[i].lch=header[i].rch=-1;
}
for(i=0;i {
for(j=i+1;j {
if(header[i].count {
tmp=header[i];
header[i]=header[j];
header[j]=tmp;
}
}
}
for(i=0;i n=i;
m=2*n-1; //外部叶子结点数为n个时,内部结点数为n-1,整个哈夫曼树的需要的结点数为2*n-1.
for(i=n;i {
min1=999999999;
for(j=0;j {
if(header[j].parent!=-1) continue;//parent!=-1说明该结点已存在哈夫曼树中,跳出循环重新选择新结点*/
if(min1>header[j].count)
{
pt1=j;
min1=header[j].count;//找到最小值
continue;
}
}
header[i].count=header[pt1].count;
header[pt1].parent=i; //依据parent域值(结点层数)确定树中结点之间的关系
header[i].lch=pt1;//计算左分支权值大小
min1=999999999;
for(j=0;j {
if(header[j].parent!=-1) continue;
if(min1>header[j].count)
{
pt1=j;
min1=header[j].count;
continue;
}
}
header[i].count+=header[pt1].count;
header[i].rch=pt1;//计算右分支权值大小
header[pt1].parent=i;
}
for(i=0;i {
f=i;
header[i].bits[0]=0;//根结点编码0
while(header[f].parent!=-1)
{
j=f;
f=header[f].parent;
if(header[f].lch==j) //置左分支编码0
{
j=strlen(header[i].bits);//扫描长度
memmove(header[i].bits+1,header[i].bits,j+1);//由header复制j+ 1个到前者
//依次存储连接“0”“1”编码
header[i].bits[0]='0';
}
else//置右分支编码1
{
j=strlen(header[i].bits);//计算字符长度?
memmove(header[i].bits+1,header[i].bits,j+1);
header[i].bits[0]='1';
}
}
}
fseek(ifp,0,SEEK_SET);//从文件开始位置向前移动0字节,即定位到文件开始位置
fwrite(&flength,sizeof(int),1,ofp);/*用来将数据写入文件流中,参数flength指向欲写入的数据地址,
总共写入的字符数以参数size*int来决定,返回实际写入的int数目1*/
fseek(ofp,8,SEEK_SET);
buf[0]=0; //定义缓冲区,它的二进制表示00000000
f=0;
pt1=8;
/*假设原文件第一个字符是"A",8位2进制为01000001,编码后为0110识别编码第一个'0',
那么我们就可以将其左移一位,看起来没什么变化。下一个是'1',应该|1,结果00000001
同理4位都做完,应该是00000110,由于字节中的8位并没有全部用完,我们应该继续读下一个字符,
根据编码表继续拼完剩下的4位,如果字符的编码不足4位,还要继续读一个字符,
如果字符编码超过4位,那么我们将把剩下的位信息拼接到一个新的字节里*/
while(!feof(ifp))
{
c=fgetc(ifp);
f++;
for(i=0;i {
if(c==header[i].b) break;
}
strcat(buf,header[i].bits);
j=strlen(buf);
c=0;
while(j>=8) //对哈夫曼编码位操作进行压缩存储
{
for(i=0;i {
if(buf[i]=='1') c=(c else c=c }
fwrite(&c,1,1,ofp);
pt1++; //统计压缩后文件的长度
strcpy(buf,buf+8);//一个字节一个字节拼接
j=strlen(buf);
}
if(f==flength) break;
}
if(j>0) //对哈夫曼编码位操作进行压缩存储
{
strcat(buf,"00000000");
for(i=0;i<8;i++)
{
if(buf[i]=='1') c=(c<<1)|1;
else c=c<<1;
}
fwrite(&c,1,1,ofp);
pt1++;
}
fseek(ofp,4,SEEK_SET);
fwrite(&pt1,sizeof(long),1,ofp);
fseek(ofp,pt1,SEEK_SET);
fwrite(&n,sizeof(long),1,ofp);
for(i=0;i<n;i++)
{
fwrite(&(header[i].b),1,1,ofp);
c=strlen(header[i].bits);
fwrite(&c,1,1,ofp);
j=strlen(header[i].bits);
if(j%8!=0) //若存储的位数不是8的倍数,则补0

{
for(f=j%8;f<8;f++)
strcat(header[i].bits,"0");
}
while(header[i].bits[0]!=0)
{
c=0;
for(j=0;j<8;j++) //字符的有效存储不超过8位,则对有效位数左移实现两字符编码的连接
{
if(header[i].bits[j]=='1') c=(c<<1)|1; //|1不改变原位置上的“0”“1”值
else c=c<<1;
}
strcpy(header[i].bits,header[i].bits+8);// 把字符的编码按原先存储顺序连接
fwrite(&c,1,1,ofp);
}
}
fclose(ifp);

printf("压缩成功!\n");
end=clock(); /* 计时结束 /
fn = _fileno(ofp); /
取得文件指针的底层流式文件号*/
sz = _filelength(fn);/*根据文件号取得文件大小*/
printf("压缩后文件大小为:%d B.\n", sz);
x = (sz / sz1)*1.0;
printf("压缩率为:%d B.\n", x);
fclose(ofp);
printf("压缩用时%f秒\n",(double)(end - start) / CLOCKS_PER_SEC);
return;
}

//
整体代码如上,请问下 关于找到最小值以后

header[i].count=header[pt1].count;
header[pt1].parent=i; //依据parent域值(结点层数)确定树中结点之间的关系
header[i].lch=pt1;//计算左分支权值大小
哈夫曼生成的节点权重不应该两者之和么,这个对于双亲的赋值不是很懂,这种利用数组进行排序以后的这个操作不是很明白,这个i好像是顺序,但不是累加,怎么剔除以后去和剩下的节点比较啊。原来搞不明白这里怎么赋值的

  • 写回答

1条回答 默认 最新

  • dabocaiqq 2018-04-18 01:56
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题