設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼系統(tǒng)

1、設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。【基本要求】1) 將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中)2) 初始化：鍵盤輸入字符集大小n、n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹；3) 編碼：利用建好的哈夫曼樹生成哈夫曼編碼；4) 輸出（1）各個(gè)字符的編碼；（2）1111111;#include#include#include#define M 50#define MAX 1000;typedef structint weight;/結(jié)點(diǎn)權(quán)值 int parent,lchild,rchild;HTNODE,*HUFFMANTREE

2、;typedef char* HUFFMANCODE;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表HUFFMANTREE huffmantree(int n,int weight)/構(gòu)建哈夫曼樹int m1,m2,k;int i,j,x1,x2;HUFFMANTREE ht;ht=(HUFFMANTREE)malloc(2*n)*sizeof(HTNODE);for(i=1;i(2*n);i+)/初始化哈夫曼樹中各結(jié)點(diǎn)的數(shù)據(jù)，沒(méi)初始值的賦值為0hti.parent=hti.lchild=hti.rchild=0;if(i=n)hti.weight=weighti;elsehti.weight=0;for(i

3、=1;in;i+)/每一重循環(huán)從森林中選擇最小的兩棵樹組建成一顆新樹m1=m2=MAX;x1=x2=0;for(j=1;j(n+i);j+)if(htj.weightm1)&(htj.parent=0)m2=m1;x2=x1;m1=htj.weight;x1=j;else if(htj.weightm2)&(htj.parent=0)m2=htj.weight;x2=j;k=n+i;htx1.parent=htx2.parent=k;htk.weight=m1+m2;htk.lchild=x1;htk.rchild=x2;return ht;void huffmancoding(const i

4、nt n,HUFFMANCODE hc,HUFFMANTREE ht,char str)int i,start,child,father;char *cd;hc=(HUFFMANCODE)malloc(n+1)*sizeof(char*);/分配n個(gè)字符編碼的頭指針cd=(char*)malloc(n*sizeof(char);/分配求編碼的工作空間cdn-1=0;/編碼結(jié)束符for(i=1;i=n;+i)/逐個(gè)字符求哈夫曼編碼start=n-1;for(child=i,father=hti.parent;father!=0;child=father,father=htfather.paren

5、t)/*從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)求逆向編碼*/if(htfather.lchild=child)cd-start=0;elsecd-start=1;hci=(char*)malloc(n-start)*sizeof(char);/為i個(gè)字符編碼分配空間strcpy(hci,&cdstart);/從cd復(fù)制哈夫曼編碼串到hcfree(cd);/釋放工作空間for(i=1;i=n;+i)printf(%c的編碼:,stri);printf(%sn,hci);void main()int i,j,k;char str50;int weight50;printf(請(qǐng)輸入字符(一次性連續(xù)輸入所求的字符):);

6、/*如:abcjhjg不要輸成ab cj hig,即字符間不加空格*/gets(str); for(j=0;j0;j-)strj=strj-1;strn+1=0;for(k=0;k0;k-)weightk=weightk-1;weight0=0;HUFFMANCODE hc=NULL;HUFFMANTREE ht;ht=huffmantree(n,weight);huffmancoding(n,hc,ht,str);補(bǔ)充：噢，我忘了你需要存檔?，F(xiàn)在太晚，明天再改一下。補(bǔ)充：這個(gè)是帶有存盤的程序。#include#include#include#define M 50#define MAX 10

7、00;typedef int Elempe;typedef structint weight;/結(jié)點(diǎn)權(quán)值 int parent,lchild,rchild;HTNODE,*HUFFMANTREE;typedef char* HUFFMANCODE;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表HUFFMANTREE huffmantree(int n,int weight)/構(gòu)建哈夫曼樹int m1,m2,k;int i,j,x1,x2;HUFFMANTREE ht;ht=(HUFFMANTREE)malloc(2*n)*sizeof(HTNODE);for(i=1;i(2*n);i+)/初始化哈夫曼樹中各結(jié)

8、點(diǎn)的數(shù)據(jù)，沒(méi)初始值的賦值為0hti.parent=hti.lchild=hti.rchild=0;if(i=n)hti.weight=weighti;elsehti.weight=0;for(i=1;in;i+)/每一重循環(huán)從森林中選擇最小的兩棵樹組建成一顆新樹m1=m2=MAX;x1=x2=0;for(j=1;j(n+i);j+)if(htj.weightm1)&(htj.parent=0)m2=m1;x2=x1;m1=htj.weight;x1=j;else if(htj.weightm2)&(htj.parent=0)m2=htj.weight;x2=j;k=n+i;htx1.paren

9、t=htx2.parent=k;htk.weight=m1+m2;htk.lchild=x1;htk.rchild=x2;return ht;void huffmancoding(const int n,HUFFMANCODE hc,HUFFMANTREE ht,char str)int i,start,child,father;char *cd;hc=(HUFFMANCODE)malloc(n+1)*sizeof(char*);/分配n個(gè)字符編碼的頭指針cd=(char*)malloc(n*sizeof(char);/分配求編碼的工作空間cdn-1=0;/編碼結(jié)束符for(i=1;i=n;+

10、i)/逐個(gè)字符求哈夫曼編碼start=n-1;for(child=i,father=hti.parent;father!=0;child=father,father=htfather.parent)/*從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)求逆向編碼*/if(htfather.lchild=child)cd-start=0;elsecd-start=1;hci=(char*)malloc(n-start)*sizeof(char);/為i個(gè)字符編碼分配空間strcpy(hci,&cdstart);/從cd復(fù)制哈夫曼編碼串到hcfree(cd);/釋放工作空間for(i=1;i=n;+i)printf(%c的編碼:

11、,stri);printf(%sn,hci);void Save(int a,const int& n)FILE *fp;int i,count=0,flag=1;fp=fopen(data.txt,wb+);for(i=1;i=n;i+)if(fwrite(&ai,sizeof(1),1,fp)=1)count+;elseflag=0;printf(數(shù)據(jù)保存失敗!n);break;if(flag)printf(n數(shù)據(jù)保存成功!(有%d個(gè)權(quán)值已保存)n,count);fclose(fp);void main()FILE fp;int i,j,k;char str50;int weight50;

12、printf(請(qǐng)輸入字符(一次性連續(xù)輸入所求的字符):);/*如:abcjhjg不要輸成ab cj hig,即字符間不加空格*/gets(str); for(j=0;j0;j-)strj=strj-1;strn+1=0;for(k=0;k0;k-)weightk=weightk-1;weight0=0;HUFFMANCODE hc=NULL;HUFFMANTREE ht;ht=huffmantree(n,weight);huffmancoding(n,hc,ht,str);Save(weight,n);2222222222;#include#include#define max 50struc

13、t aint weight;int parent,lchild,rchild;struct bchar cdmax;int start;void main()struct a ht2*max;struct b hcdmax,d;int i,k,n,c,s1,s2,m1,m2,f;printf(輸入n:);scanf(%d,&n);for(i=1;i=n;i+)printf(輸入權(quán)值:);scanf(%d,&hti.weight);hti.parent=0;for(;i=2*n-1;i+)hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=2*n-1;i+)m1=m2=30000;s1=s2=0;for(k=1;k=i-1;k+)if(htk.parent=0 & htk.weightm1)m2=m1;s2=s1;m1=htk.weight;s1=k;else if(htk.parent=0 & htk.weightm2)m2=htk.weight;s2=k;hts1.parent=hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;for(i=1;i=n;i+)d.start=n-1;