數(shù)據(jù)結構課程設計哈夫曼編碼譯碼器

1、題目一：哈夫曼編碼與譯碼一、任務設計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復地顯示并處理以下項目，直到選擇退出為止。要求：1) 將權值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當前目錄中) ；2) 初始化：鍵盤輸入字符集統(tǒng)計字符權值、自定義26個字符和26個權值、統(tǒng)計文件中一篇英文文章中26個字母，建立哈夫曼樹；3) 編碼：利用建好的哈夫曼樹生成哈夫曼編碼；4) 輸出編碼（首先實現(xiàn)屏幕輸出，然后實現(xiàn)文件輸出）；5） 譯碼（鍵盤接收編碼進行譯碼、文件讀入編碼進行譯碼）；6) 界面優(yōu)化設計。二、流程圖主菜單1.建立字符權值2.建立

2、并輸出哈夫曼樹3.建立并查看哈弗曼編碼4.編碼與譯碼0.退出系統(tǒng)1.從鍵盤輸入字符集統(tǒng)計權值2.從文件讀入字符集統(tǒng)計權值3.自定義字符及權值0.返回上級菜單輸出哈夫曼樹并保存至文件“哈夫曼樹。txt”輸出哈夫曼編碼并保存至文件“哈夫曼編碼。txt1.編碼2.譯碼0.返回上級菜單1.從鍵盤輸入字符集進行編碼2.從文件讀入字符集進行編碼1.從鍵盤輸入編碼進行譯碼2.從文件讀入編碼進行譯碼0.返回上級菜單0.返回上級菜單三、代碼分解/頭文件#include<stdio.h>#include<string.h>#include<stdlib.h>#include &

3、lt;conio.h>#define N 1000#define M 2*N-1#define MAXcode 6000/函數(shù)聲明void count(CHar &ch,HTNode ht);void editHCode(HTNode ht,HCode hcd,CHar &ch,int n,char bianma); /編碼函數(shù)void printyima(HTNode ht,HCode hcd,int n,char bianma); /譯碼函數(shù)void creatHT(HTNode ht,int n);void CreateHCode (HTNode ht,HCode

4、hcd,int n);void DispHCode(HTNode ht,HCode hcd,int n);void input_key(CHar &ch);void input_file(CHar &ch);void input_cw(HTNode ht);void bianma1(HTNode ht,HCode hcd,CHar &ch,int n,char bianma);void bianma2(HTNode ht,HCode hcd,CHar &ch,int n,char bianma);void yima1(HTNode ht,HCode hcd,in

5、t n,char bianma);void yima2(HTNode ht,HCode hcd,int n,char bianma);void creat_cw();void bianmacaidan();void yimacaidan();void bianmayima();int caidan(); /結構體typedef structchar data;int parent;int weight;int lchild;int rchild;HTNode;typedef structchar cdN;int start;HCode;typedef structchar sN;int num

6、;CHar;CHar ch;HTNode htM;HCode hcdN;/主函數(shù)int main()int xh;while(1)system("color 1f"); /操作菜單背景顏色xh=caidan(); /調(diào)用菜單函數(shù) switch(xh) /switch語句case 1:system("cls");creat_cw();break;case 2:system("cls");creatHT(ht,n);break;case 3:system("cls");CreateHCode(ht,hcd,n);Dis

7、pHCode(ht,hcd,n);break;case 4:system("cls");bianmayima();break;case 0:system("cls");printf("nnnnnnnnntttt感謝使用本系統(tǒng)!nnnnnnn ttt");exit(0);default:system("cls");putchar('a'); printf("ntt輸入有誤，請重新輸入:n");break;return 0;/菜單函數(shù)int caidan() /菜單函數(shù)模塊/ int

8、 xh; printf("nnn"); printf("tt 歡迎使用哈夫曼編碼譯碼系統(tǒng) n"); printf("tt n"); printf("tt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n"); printf("tt*= =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*= =*n"); printf("tt*= 1.建立字符權值 =*n"); printf("

9、;tt*= *=*=*=*=*=*=*=*=*=*=*= =*n"); printf("tt*= 2.建立并輸出哈夫曼樹 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*= =*n"); printf("tt*= 3.生成并查看哈夫曼編碼 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*= =*n"); printf("tt*= 4.編碼與譯碼 =*n"); printf("tt*= *=*=*=*=*=*=

10、*=*=*=*=*= =*n"); printf("tt*= 0.退出系統(tǒng) =*n"); printf("tt*= =*n"); printf("tt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*n"); printf("ntt請輸入序號進行選擇:"); scanf("%d", &xh); return xh; /返回從鍵盤接收的選項void bianmayima() int xh; while(1) printf("nnn

11、nn"); printf("tt 編碼與譯碼 n"); printf("tt n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 1.編碼 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 2.譯碼 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*

12、=*=*=* =*n"); printf("tt*= 0.返回上級菜單 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("ntt請輸入序號進行選擇:"); scanf("%d",&xh); switch(xh) /switch語句case 1:system("cls");bianmacaidan();break;case 2:system("cls");yimacaidan();

13、break;case 0:system("cls");return;default:system("cls");putchar('a'); printf("ntt輸入有誤，請重新輸入:n");break; void yimacaidan() int xh; while(1) printf("nnnnn"); printf("tt 譯碼 n"); printf("tt n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=

14、*=*=* =*n"); printf("tt*= 1.鍵盤輸入編碼進行譯碼 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 2.文件讀入編碼進行譯碼 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 0.返回上級菜單 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*

15、=*=*=*=*=* =*n"); printf("ntt請輸入序號進行選擇:"); scanf("%d",&xh); switch(xh) /switch語句case 1:system("cls");yima1(ht,hcd,n,bianma);break;case 2:system("cls");yima2(ht,hcd,n,bianma);break;case 0:system("cls");return;default:system("cls");p

16、utchar('a'); printf("ntt輸入有誤，請重新輸入:n");break; void bianmacaidan() int xh; while(1) printf("nnnnn"); printf("tt 編碼 n"); printf("tt n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 1.鍵盤輸入字符集編碼 =*n"); printf("tt

17、*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 2.文件讀入文章編碼 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 0.返回上級菜單 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("ntt請輸入序號進行選擇:"); scanf("%d"

18、,&xh); switch(xh) /switch語句case 1:system("cls");bianma1(ht,hcd,ch,n,bianma);break;case 2:system("cls");bianma2(ht,hcd,ch,n,bianma);break;case 0:system("cls");return;default:system("cls");putchar('a'); printf("ntt輸入有誤，請重新輸入:n");break; void

19、 creat_cw() int xh2; while(1) printf("nnnnn"); printf("tt 建立字符權值 n"); printf("tt n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 1.從鍵盤輸入字符集進行統(tǒng)計 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 2

20、.從文件讀入字符集統(tǒng)計 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 3.自定義字符權值 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("tt*= 0.返回上級菜單 =*n"); printf("tt*= *=*=*=*=*=*=*=*=*=*=*=*=*=*=* =*n"); printf("ntt請

21、輸入序號進行選擇:"); scanf("%d",&xh2); switch(xh2) /switch語句case 1:system("cls");input_key(ch);break;case 2:system("cls");input_file(ch);break;case 3:system("cls");input_cw(ht);break;case 0:system("cls");return;default:system("cls");putcha

22、r('a'); printf("ntt輸入有誤，請重新輸入:n");break; /建立字符權值模塊void input_key(CHar &ch)int i,j=0;char stN;printf("請輸入字符集（以#結束）:n");for(i=0;i<N;i+)scanf("%c",&sti); if(sti='#') sti='0'break; strcpy(ch.s,st);ch.num=strlen(st);count(ch,ht);printf(&quo

23、t;按任意鍵返回!");getch();system("cls");return;void input_file(CHar &ch)int i;FILE*fp;char filename20;printf("請輸入要打開的文件名(*.txt):");scanf("%s",&filename);if(fp=fopen(filename,"r")=NULL)printf("ntt文件打開失敗!");return;for(i=0;!feof(fp);i+)fread(&

24、;ch.si,sizeof(char),1,fp); ch.num=strlen(ch.s);printf("讀入成功!n");printf("文件中的字符集為:%sn",ch.s);fclose(fp);count(ch,ht);printf("按任意鍵返回!");getch();system("cls");return;void input_cw(HTNode ht)int i,w,s,j;char a;printf("要輸入的字符總個數(shù)是？:");scanf("%d",

25、&s);n=s;printf("請輸入字符及其權值:n");for(i=0;i<s;i+)printf("請輸入第%d個字母:",i+1);scanf("%s",&a);hti.data=a;printf("請輸入其權值:");scanf("%d",&w);hti.weight=w;FILE *fp;if(fp=fopen("data.txt","w")=0)printf("ntt文件打開失敗!");ret

26、urn;printf("n定義權值成功!nn");printf("各字符及其權值為:nn");fprintf(fp,"各字符及其權值為:n");printf(" 字符t權值");fprintf(fp," 字符t權值");for(j=0;j<i;j+)printf("n"); fprintf(fp,"n");printf(" %-8c%-8d",htj.data,htj.weight);fprintf(fp," %-8c%

27、-8d%",htj.data,htj.weight);printf("n");printf("n字符權值已輸出至文件“data.txt”！");fclose(fp);printf("輸入完成，按任意鍵返回！");getch();system("cls");return;/統(tǒng)計字符權值函數(shù)void count(CHar &ch,HTNode ht)int i,j,m=0;char cN;int sumN=0;for(i=0;ch.si!='0'i+)for(j=0;j<m;j+

28、)if(ch.si=cj|(cj>='a'&&cj<='z'&&ch.si+32=cj) break;if(j<m)sumj+;elseif(ch.si>='A'&&ch.si<='Z')cj=ch.si+32;else cj=ch.si;sumj+;m+;for(i=0;i<m;i+)hti.data=ci;hti.weight=sumi;n=m;FILE *fp;if(fp=fopen("data.txt","w&

29、quot;)=0)printf("ntt文件打開失敗!");return;printf("n統(tǒng)計權值成功!nn");printf("各字符及其權值為:nn");fprintf(fp,"各字符及其權值為:n");printf(" 字符t權值");fprintf(fp," 字符t權值");for(j=0;j<m;j+)printf("n"); fprintf(fp,"n");printf(" %-8c%-8d",h

30、tj.data,htj.weight);fprintf(fp," %-8c%-8d%",htj.data,htj.weight);printf("n");printf("n字符權值已輸出至文件“data.txt”！");fclose(fp);/構造哈夫曼樹void creatHT(HTNode ht,int n)FILE *fp;if(fp=fopen("哈夫曼樹.txt","w")=0)printf("ntt文件打開失敗!");return;int i,j,k,lnode,

31、rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; for (i=n;i<2*n-1;i+)min1=min2=32767; lnode=rnode=-1; for(k=0;k<=i-1;k+) if(htk.parent=-1)if (htk.weight<min1)min2=min1;rnode=lnode; min1=htk.weight;lnode=k;else if(htk.weight<min2) min2=htk.weight;rnode=k;

32、htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;printf("建立huffman樹成功!n");printf("輸出huffman樹:n");fprintf(fp,"輸出huffman樹:n");printf("t字符t權值t父節(jié)點t 左子節(jié)點t右子節(jié)點");fprintf(fp,"t字符t權值t父節(jié)點t 左子節(jié)點t右子節(jié)點"

33、);for(j=1;j<i;j+)printf("n"); fprintf(fp,"n");printf("t %-8c%-8d%-10d%-14d%-10d",htj.data,htj.weight,htj.parent,hti.lchild,htj.rchild);fprintf(fp,"t %-8c%-8d%-10d%-14d%-10d",htj.data,htj.weight,htj.parent,hti.lchild,htj.rchild);printf("n");printf(

34、"哈夫曼樹已輸出至文件“哈夫曼樹.txt”！按任意鍵返回!");fclose(fp);getch();system("cls");return;/生成哈夫曼編碼void CreateHCode (HTNode ht,HCode hcd,int n)int i,f,c,j=0; HCode hc;for(i=0;i<n;i+) hc.start=n;c=i; hc.cdhc.start-='0' f=hti.parent;while(f!=-1) if (htf.lchild=c) hc.cdhc.start-='0'

35、else hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; for(j=0;j<hc.start;j+) hc.cdj=' ' hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n) FILE *fp;if(fp=fopen("哈夫曼編碼.txt","w")=0)printf("ntt文件打開失敗!");return;int i,k; int sum=0,m=0,j; printf("輸出字符哈夫曼

36、編碼:n");fputs("輸出字符哈夫曼編碼:n",fp); for (i=0;i<n;i+)j=0; printf("%c:t",hti.data);fprintf(fp,"n%c:t",hti.data); for (k=hcdi.start;k<=n;k+) printf("%c",hcdi.cdk); j+; fprintf(fp,"%c",hcdi.cdk);m+=hti.weight; sum+=hti.weight*j; printf("n&quo

37、t;); printf("n哈夫曼編碼已保存至文件“哈夫曼編碼.txt!按任意鍵返回！”");fclose(fp); getch(); system("cls");/編碼函數(shù)void bianma1(HTNode ht,HCode hcd,CHar &ch,int n,char bianma)int i;char strN; printf("請輸入要編碼的字符集（以#結束）:n");for(i=0;i<N;i+)scanf("%c",&stri); if(stri='#') stri='0'break;strcpy(ch.s,str);ch.num=strlen(str);editHCode(ht,hcd,ch,n,bianma); getch();system("cls");return;void bianma2(HTNode ht,HCode hcd,CHar &ch,int n,char bianma)int i;FILE*fp;char filename20;printf("請輸入要打開的文件名(*.txt):");scanf(