数据结构课程设计-赫夫曼编码

1、建立哈夫曼树

//-------------------------------------初始化--------------------------------------

int min(HfmTeee &t,int x) //查找权值最小的树 { int flag; int k=999999999; for(int i=1;i<=x;i++) { if(t[i].weight

void Find(HfmTeee &H,int x,int *p1,int *p2) //查找权值最小的两棵树 {

*p1=min(H,x); *p2=min(H,x); if(*p1>*p2) { int t=*p1; *p1=*p2; *p2=t; } }

void CreateHfmTree(HfmTeee &H,HuffCode &Code,int n) //构建哈夫曼树 { int i,start,c,f,m,w; int p1,p2; char *cd,z;

if(n<=1){ //如果节点小于1，无法构造！ return; }

m=2*n-1;

H=(HfmTeee)malloc((m+1)*sizeof(HtNode)); for(i=1;i<=n;++i) {

9

printf(\请输入第%d字符信息和权值：\ scanf(\ while(getchar()!='\\n') continue; H[i].ch=z;

H[i].weight=w; H[i].parent=0; H[i].lchild=0; H[i].rchild=0; }

for(;i<=m;++i) {

H[i].ch='0'; H[i].weight=0; H[i].parent=0; H[i].lchild=0; H[i].rchild=0; }

for(i=n+1;i<=m;++i) {

Find(H,i-1,&p1,&p2);

H[p1].parent=i;H[p2].parent=i; H[i].lchild=p1;H[i].rchild=p2;

H[i].weight=H[p1].weight+H[p2].weight; }

Code=(HuffCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\\0';

for(i=1;i<=n;++i) //进行哈夫曼编码 {

start=n-1;

for(c=i,f=H[i].parent;f!=0;c=f,f=H[f].parent) {

if(H[f].lchild==c) cd[--start]='0'; else

cd[--start]='1'; }

Code[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(Code[i],&cd[start]);

} ofstream oFile(\10

//以清空方式

打开文件，并写入

if(!oFile) { cout<<\ return ; }

oFile<

{ oFile<

oFile.close();

cout<<\赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!\ free(cd);

ok=1; }

2、编码

//-------------------------------------编码--------------------------------------

void Encoding(HfmTeee H,HuffCode code,int leaves) { char str[100];

cout<<\请输入字符：\

getchar(); gets(str); ofstream oFile(\if(!oFile) { cout<<\ return ; } oFile<

ifstream iFile(\

if(!iFile) {

cout<<\对不起您未建哈夫曼树同时文件中也不存在!\

11

return ; }

char ch,th,str1[20]; iFile>>leaves;

H=(HfmTeee)malloc((leaves+1)*sizeof(HtNode));

code=(HuffCode)malloc((leaves+1)*sizeof(char *)); int ant=1;

while(iFile.peek()!=EOF) {

iFile.get(ch);//接收上一行的换行符 iFile.get(ch); iFile>>th>>str1; int l=strlen(str1); H[ant].ch=ch;

code[ant]=(char*)malloc((l+1)*sizeof(char)); strcpy(code[ant++],str1); }

iFile.close(); }

for(int i=0;i

oFile1<

cout<<\译码结束，字符已经存入CodeFile.txt文件中！\}

3、译码

//-------------------------------------译码--------------------------------------

void Decoding(HfmTeee h,HuffCode code,int leaves) { char str[100000]; char temp[100];

cout<<\对CodeFile.txt的数据进行编译……\ if(ok==0)

12