/***
*huffmanCode.cpp - 压缩软件的代码文件
*
*
*题目：压缩软件的实现
*
*班级：软件1班
*
*姓名：陈润资
*
*学号：200801001
*
****/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include "huffmanCode.h"
/*------------------------------------------------------------
操作目的： 字符串匹配
初始条件： 两个字符串
操作结果： 是否匹配成功
函数参数：
const char *p 压缩文件的字符串
char *q 码表
返回值：
无
------------------------------------------------------------*/
bool isPartof(const char *p,char *q)//判断q是否是p的一部分
{
int i=0;
while(*(p+i)!='\0'&&*(p+i)==*(q+i)){
i++;
}
if(*(q+i)=='\0')
return true;
else
return false;
}
/*------------------------------------------------------------
操作目的： 字符串拷贝
初始条件： 两个已经存在的字符串
操作结果： 将字符串q拷贝到字符串*p中
函数参数：
char **p *p为拷贝的目的串
char *q q为被拷贝的串
返回值：
无
-------------------------------------------------------------*/
void strcpy(char **p,char *q)
{
int i=0;
do{
*(*p+i)=*(q+i);
i++;
}while(*(q+i-1)!='\0');
}
/*------------------------------------------------------------
操作目的： 字符串连接
初始条件： 两个已经存在的字符串
操作结果： 将字符串q连接到字符串*p的后边
函数参数：
char **p *p为连接的目的串
char *q q为被连接的串
返回值：
无
-------------------------------------------------------------*/
void strcat_chen(char **p,char *q)
{
int i=0;
while(*(*p+i)!='\0'){
i++;
}
int j=0;
do{
*(*p+i)=*(q+j);
i++;
j++;
}while(*(q+j-1)!='\0');
}
/*------------------------------------------------------------
操作目的： 选择双亲值为0且权值最小的两个节点
初始条件： 数组A已存在
操作结果： 得到这两个节点的下标
函数参数：
HuffmanTree ht //待选择的树
int n //选择的范围
int *s1 //保存两个最小权值节点的下标
int *s2
返回值：
无
------------------------------------------------------------*/
void select(HuffmanTree ht,int n, int *s1, int *s2)
{
*s1=0;
*s2=0;
for(int i=1;i<=n;i++){
HTNode *p=ht;
ht->weight=62531;//让数组空间的第一个节点(没用的)的权值很大；
if((p+*s1)->weight>(p+*s2)->weight){//总是让检测值和比较大的那个比较；
if((p+i)->parent==0&&(p+i)->weight<(p+*s1)->weight)
*s1=i;
}
else{
if((p+i)->parent==0&&(p+i)->weight<(p+*s2)->weight)
*s2=i;
}
}
}
/*------------------------------------------------------------
操作目的： huffman编码
初始条件： 已知各个节点的权值
操作结果： 得到一棵Huffman树，以及各个叶子节点的huffman编码
函数参数：
HuffmanTree *ht //分配的存储huffman节点的首地址
HuffmanCode *hc //指向各个编码的首地址
int *w //各个待编码节点的权值
返回值：
无
------------------------------------------------------------*/
void HuffmanCoding(HuffmanTree *ht,HufCode_pointer *hc, NodeWeight *w)
{
int n=w->len;
if(n<=1)
return ;
int m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//下标为0的空间没有用。
HuffmanTree p;
int i=0;
int s1,s2;
for(p=*ht+1,i=1;i<=n;i++,p++){
p->weight=(w+i-1)->weight;
p->ch=(w+i-1)->ch;
p->parent=0;
p->lch=0;
p->rch=0;
};
for(;i<=m;i++){
p->parent=0;
p->lch=0;
p->rch=0;
p->weight=0;
p++;
};
for(i=n+1;i<=m;i++){
select(*ht,i-1,&s1,&s2);
(*ht+s1)->parent=i;
(*ht+s2)->parent=i;
(*ht+i)->lch=s1;
(*ht+i)->rch=s2;
(*ht+i)->weight=(*ht+s1)->weight+(*ht+s2)->weight;
};
*hc = (HufCode_pointer)malloc((n+1)*sizeof(HuffmanCode));
char * cd;
cd=(char *)malloc(n*sizeof(char));
*(cd+n-1)='\0';
for(i=1;i<=n;i++){
int start=n-1;
int c=i;
int f=0;
for(f=(*ht+i)->parent;f!=0;c=f,f=(*ht+f)->parent)
if((*ht+f)->lch==c){
start--;
*(cd+start)='0';
}
else if((*ht+f)->rch==c){
start--;
*(cd+start)='1';
};
(*hc+i)->ch_pointer=(char*)malloc((n-start)*sizeof(char));
//保证实际参数cd中的无效内容不会被传入strcpy函数；
strcpy(&(*hc+i)->ch_pointer,cd+start);
//加上数据信息；
(*hc+i)->ch=(*ht+i)->ch;
};
free(cd);
}
void zip(){//压缩
HuffmanTree htree; //hufman树
HufCode_pointer hcode; //码表
NodeWeight * ww=NULL;
int flength;
unsigned char c=0;
struct char_weight
{
unsigned char b; //记录字符在数组中的位置
long count; //字符出现频率（权值）
} char_weight[512]={{'a',0}};
char filename[50],outputfile[50],outcodefile[50];
FILE *ifp,*ofp_zip,*ofp_code;
//请输入要压缩的文件名;
printf("\t请您输入需要压缩的文件:");
gets(filename);
ifp=fopen(filename,"rb");
if(ifp==NULL)
{
printf("\n\t文件打开失败!\n\n");
return;
}
//请输入压缩后的文件名；
printf("\t请您输入压缩后的文件名:");
gets(outputfile);
ofp_zip=fopen(strcat(outputfile,".txt"),"wb");
if(ofp_zip==NULL)
{
printf("\n\t压缩文件指定失败!\n\n");
return;
}
//请输入压缩文件的字符码表保存文件名；
printf("\t请您输入保存码表文件名：");
gets(outcodefile);
ofp_code=fopen(strcat(outcodefile,".txt"),"wb");
if(ofp_code==NULL)
{
printf("\n\t压缩码表文件指定失败!\n\n");
return;
}
//读文件统计各个字符的权重;
flength=0;
while(!feof(ifp))
{
fread(&c,1,1,ifp);
char_weight[c].count++; //字符重复出现频率+1
flength++; //字符出现原文件长度
}
int diff_char=0;
for(int i=0;i<512;i++)
{
if(char_weight[i].count!=0) {
char_weight[i].b=(unsigned char)i;
diff_char++;
}
else char_weight[i].b=0;
}
ww=(NodeWeight*)malloc(diff_char*sizeof(NodeWeight));
int jj=0;
for( i=0;i<512;i++)
{
if(char_weight[i].count!=0) {
ww[jj].ch=char_weight[i].b;
ww[jj].weight=char_weight[i].count;
jj++;
}
}
ww->len=jj;
//编码；
HuffmanCoding(&htree,&hcode,ww);
//压缩；
fseek(ifp,0,SEEK_SET); //从文件开始位置向前移动0字节，即定位到文件开始位置
char *buf=(char *)malloc(50*sizeof(char));//假设每个字符的编码长度不超过25；
int sum_zip=0,sum_total=0;
int j=0;
buf[0]=0; //定义缓冲区,它的二进制表示00000000，初始值为空--陈润资；
unsigned char c_if;
while(!feof(ifp))
{
c_if=fgetc(ifp);
sum_total++;
for(i=0;i<ww->len;i++)
{
if(c_if==ww[i].ch) break;
}
if(i==ww->len)
break;
strcat_chen(&buf,(hcode+i+1)->ch_pointer);
j=strlen(buf);
c=0;
while(j>=8) //对哈夫曼编码位操作进行压缩存储
{
for(i=0;i<8;i++)
{
if(buf[i]=='1') c=(c<<1)|1;
else c=c<<1;
}
fwrite(&c,1,1,ofp_zip);
sum_zip++; //统计压缩后文件的长度
strcpy(&buf,buf+8); //一个字节一个字节拼接
j=strlen(buf);
}
}
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_zip);
sum_zip++;
}
sum_total--;
double div=((double)sum_zip/sum_total)*100;//计算文件的压缩率
//保存码表；
fwrite(&(ww->len),sizeof(int),1,ofp_code);
for(i=1;i<=ww->len;i++)
{
char ch=(hcode+i)->ch;
fwrite(&(ch),sizeof(char),1,ofp_code);
int i_01=0;
do{
char ch_01=(hcode+i)->ch_pointer[i_01];
fwrite(&(ch_01),sizeof(char),1,ofp_code);
i_01++;
}while((hcode+i)->ch_pointer[i_01-1]!='\0');//将'\0'也保存起来
}
fwrite(&sum_zip,sizeof(int),1,ofp_code); //压缩文件的长度保存在码表中
fwrite(&sum_total,sizeof(int),1,ofp_code); //原文件的长度保存在码表中
fclose(ifp);
fclose(ofp_zip);
fclose(ofp_code);
printf("\n\t压缩文件成功!\n");
printf("\t压缩率为 %f%%\n\n",div);
}
void unzip(){
HufCode_pointer hcode; //码表
int char_diff,len_zip=0; //flength;char_diff,是不同的字符数，也是编码的条数。
unsigned char c=0;
char filename_zip[50],filename_code[50],outfile_unzip[50]
