數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈夫曼編碼譯碼器

題目一：哈夫曼編碼與譯碼一、任務(wù)設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。要求：1） 將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件（文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中）；2） 初始化：鍵盤(pán)輸入字符集統(tǒng)計(jì)字符權(quán)值、自定義26個(gè)字符和26個(gè)權(quán)值、統(tǒng)計(jì)文件中一篇英文文章中26個(gè)字母，建立哈夫曼樹(shù)；3） 編碼：利用建好的哈夫曼樹(shù)生成哈夫曼編碼；4） 輸出編碼（首先實(shí)現(xiàn)屏幕輸出，然后實(shí)現(xiàn)文件輸出）；5） 譯碼（鍵盤(pán)接收編碼進(jìn)行譯碼、文件讀入編碼進(jìn)行譯碼）；6）界面優(yōu)化設(shè)計(jì)。、流程圖三、代碼分解〃頭文件#include<stdio.h>#include<string.h>#include<stdlib.h>#include<conio.h>#defineN1000#defineM2*N-1#defineMAXcode6000〃函數(shù)聲明voidcount(CHar&ch,HTNodeht[]);voideditHCode(HTNodeht[],HCodehcd[],CHar&ch,intn,charbianma[]); 〃編碼函數(shù)voidprintyima(HTNodeht[],HCodehcd[],intn,charbianma[]);〃譯碼函數(shù)voidcreatHT(HTNodeht[],intn);voidCreateHCode(HTNodeht[],HCodehcd[],intn);voidDispHCode(HTNodeht[],HCodehcd[],intn);voidinput_key(CHar&ch);voidinput_file(CHar&ch);voidinput_cw(HTNodeht[]);voidbianma1(HTNodeht[],HCodehcd[],CHar&ch,intn,charbianma[]);voidbianma2(HTNodeht[],HCodehcd[],CHar&ch,intn,charbianma[]);voidyima1(HTNodeht[],HCodehcd[],intn,charbianma[]);voidyima2(HTNodeht[],HCodehcd[],intn,charbianma[]);voidcreat_cw();voidbianmacaidan();voidyimacaidan();voidbianmayima();intcaidan();〃結(jié)構(gòu)體typedefstruct{

chardata;intparent;intweight;intIchild;intrchild;}HTNode;typedefstruct{charcd[N];intstart;}HCode;typedefstruct{chars[N];intnum;}CHar;CHarch;HTNodeht[M];HCodehcd[N];〃主函數(shù)intmain(){intxh;while(1){〃操作菜單背景顏色〃調(diào)用菜單函數(shù)〃操作菜單背景顏色〃調(diào)用菜單函數(shù)//switch語(yǔ)句xh=caidan();switch(xh){case1:system("cls");creat_cw();break;case2:system("cls");creatHT(ht,n);break;case3:system("cls");CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);break;case4:system("cls");bianmayima();break;case0:system("cls");printf("\n\n\n\n\n\n\n\n\n\t\t\t\t感使用本系統(tǒng)!\n\n\n\n\n\n\n\t\t\t");exit(0);default:system("cls");putchar('\a');printf("\n\t\t輸入有誤，請(qǐng)重新輸入:\n");break;}}return0;}〃菜單函數(shù)intcaidan() 〃菜單函數(shù)模塊〃{intxh;printf("\n\n\n");printf("\t\t歡迎使用哈夫曼編碼譯碼系統(tǒng)\n");printf("\t\t\n");printf("\t\t*=*=*=*__小__小__小__小__小__小__小__小__小__小__小__小__小__小__小__小_=*_*_*\n");printf("\t\t*=_*\n");printf("\t\t*=??!-???!-???!-???!-???!-???!-?“““““*_*_*_*_*_*_*_*_*_*_*__*\n");printf("\t\t*=1.建立字符權(quán)值_*\n");printf("\t\t*=“““““““““““*_*_*_*_*_*_*_*_*_*_*__*\n");printf("\t\t*=2.建立并輸出哈夫曼樹(shù)_*\n");printf("\t\t*=“““““““““““*_*_*_*_*_*_*_*_*_*_*__*\n");printf("\t\t*=3.生成并查看哈夫曼編碼_*\n");printf("\t\t*=“““““““““““*_*_*_*_*_*_*_*_*_*_*__*\n");printf("\t\t*=4.編碼與譯碼_*\n");printf("\t\t*=“““““““““““*_*_*_*_*_*_*_*_*_*_*__*\n");printf("\t\t*=0.退出系統(tǒng)_*\n");printf("\t\t*=_*\n");printf("\t\t*=*=*=*__小__小__小__小__小__小__小__小__小__小__小__小__小__小__小__小_=*_*_*\n");printf（"\n\t\t請(qǐng)輸入序號(hào)進(jìn)行選擇:"）；scanf("%d",&xh);returnxh;〃返回從鍵盤(pán)接收的選項(xiàng)}voidbianmayima()

intxh;while(1)printf("\n\n\n\n\n");printf("\t\t編碼與譯碼printf("\t\tprintf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*printf("\t\t*=1.編碼printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*printf("\t\t*=2.譯碼printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*printf("\t\t*=0.返回上級(jí)菜單printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*{\n");\n");=*\n");=*\n");=*\n");=*\n");=*\n");=*\n");=*\n");printf("\n\t\t請(qǐng)輸入序號(hào)進(jìn)行選擇:")；scanf("%d",&xh);switch(xh) //switch語(yǔ)句{case1:system("cls");bianmacaidan();break;case2:system("cls");yimacaidan();break;case0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t輸入有誤，請(qǐng)重新輸入:\n");break;}}}voidyimacaidan(){intxh;while(1){printf("\n\n\n\n\n");譯碼\n");\n");譯碼\n");\n");printf("\t\tprintf("\t\t*=printf("\t\t*=printf("\t\t*=printf("\t\t*=printf("\t\t*=printf("\t\t*=printf("\t\t*=1.鍵盤(pán)輸入編碼進(jìn)行譯碼“““““““““““““““小一小一小一小一小一小一小一小一小一小一小一小一小一小一小2.文件讀入編碼進(jìn)行譯碼“““““““““““““““小一小一小一小一小一小一小一小一小一小一小一小一小一小一小0.返回上級(jí)菜單*J* *J* *J* *J* *J* *J* *J* *J* *J* *J* *J* *J* *J* *J* *1*小一小一小一小一小一小一小一小一小一小一小一小一小一小一小=*\n");=*\n");=*\n");=*\n");=*\n");=*\n");=*\n");printf("\n\t\t請(qǐng)輸入序號(hào)進(jìn)行選擇:");//switch語(yǔ)句//switch語(yǔ)句switch(xh){case1:system("cls");yima1(ht,hcd,n,bianma);break;case2:system("cls");yima2(ht,hcd,n,bianma);break;case0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t輸入有誤，請(qǐng)重新輸入:\n");break;}}}voidbianmacaidan(){intxh;while(1){printf("\n\n\n\n\n");printf("\t\t編碼\n");printf("\t\t\n");printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*=1.鍵盤(pán)輸入字符集編碼=*\n");printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*=2.文件讀入文章編碼=*\n");printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*=0.返回上級(jí)菜單=*\n");printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\n\t\t請(qǐng)輸入序號(hào)進(jìn)行選擇:")；scanf("%d",&xh);switch(xh) //switch語(yǔ)句{case1:system("cls");bianma1(ht,hcd,ch,n,bianma);break;case2:system("cls");bianma2(ht,hcd,ch,n,bianma);break;case0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t輸入有誤，請(qǐng)重新輸入:\n");break;}}}voidcreat_cw(){intxh2;while(1)printf("\n\n\n\n\n");printf("\t\t建立字符權(quán)值\n");printf("\t\t\n");printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*=1.從鍵盤(pán)輸入字符集進(jìn)行統(tǒng)計(jì)=*\n");printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*=2.從文件讀入字符集統(tǒng)計(jì)=*\n");printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*=3.自定義字符權(quán)值=*\n");printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf("\t\t*=0.返回上級(jí)菜單=*\n");printf("\t\t*=“““““““““““““““*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*\n");printf（"\n\t\t請(qǐng)輸入序號(hào)進(jìn)行選擇:"）；scanf("%d",&xh2);switch(xh2)//switch語(yǔ)句case1:system("cls");input_key(ch);break;case2:system("cls");input_file(ch);break;case3:system("cls");input_cw(ht);break;case0:system("cls");return;default:system("cls");putchar('\a');printf("\n\t\t輸入有誤，請(qǐng)重新輸入:\n");break;}}}〃建立字符權(quán)值模塊voidinput_key(CHar&ch){inti,j=0;charst[N];printf(-請(qǐng)輸入字符集(以#結(jié)束):\n");for(i=0;i<N;i++){scanf("%c”,&st[i]);if(st[i]=='#'){st[i]='\0';break;}}strcpy(ch.s,st);ch.num=strlen(st);count(ch,ht);printf("按任意鍵返回!")；getch();system("cls");return;}voidinput_file(CHar&ch){inti;FILE*fp;charfilename[20];printf("請(qǐng)輸入要打開(kāi)的文件名(*.txt):");scanf("%s”,&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文件打開(kāi)失敗!!!");return;}for(i=0;!feof(fp);i++){fread(&ch.s[i],sizeof(char),1,fp);}ch.num=strlen(ch.s);printf("讀入成功!\n");printf("文件中的字符集為:％s\n",ch.s);fclose(fp);count(ch,ht);printf("按任意鍵返回!")；getch();system("cls");return;}voidinput_cw(HTNodeht[]){inti,w,s,j;chara;printf(-要輸入的字符總個(gè)數(shù)是？：，scanf("%d”,&s);n=s;printf(-請(qǐng)輸入字符及其權(quán)值:\n");for(i=0;i<s;i++){printf("請(qǐng)輸入第％d個(gè)字母:",i+1);scanf("%s”,&a);ht[i].data=a;printf("請(qǐng)輸入其權(quán)值:")；scanf("%d",&w);ht[i].weight=w;}FILE*fp;if((fp=fopen("data.txt","w"))==0){printf("\n\t\t文件打開(kāi)失敗!!!");return;}printf("\n定義權(quán)值成功!\n\n");printf(-各字符及其權(quán)值為:\n\n");fprintf(fp,"各字符及其權(quán)值為:\n");printf("字符\t權(quán)值")；fprintf(fp,"字符\t權(quán)值")；for(j=0;j<i;j++){printf("\n");fprintf(fp,"\n");printf("%-8c%-8d”,ht[j].data,ht[j].weight);fprintf(fp,”%-8c%-8d%”,ht[j].data,ht[j].weight);}printf("\n");printf("\n字符權(quán)值已輸出至文件"data.txt”！");fclose(fp);printf("輸入完成，按任意鍵返回！”)；getch();system("cls");return;}〃統(tǒng)計(jì)字符權(quán)值函數(shù)voidcount(CHar&ch,HTNodeht[]){inti,j,m=0;charc[N];intsum[N]={0};for(i=0;ch.s[i]!='\0';i++){for(j=0;j<m;j++)if(ch.s[i]==c[j]ll(c[j]>='a'&&c[j]<='z'&&ch.s[i]+32==c[j]))break;if(j<m)sum[j]++;else{if(ch.s[i]>='A'&&ch.s[i]<='Z')c[j]=ch.s[i]+32;elsec[j]=ch.s[i];sum[j]++;m++;}}for(i=0;i<m;i++){ht[i].data=c[i];ht[i].weight=sum[i];}n=m;FILE*fp;if((fp=fopen("data.txt","w"))==0){printf("\n\t\t文件打開(kāi)失敗!!!");return;}printf("\n統(tǒng)計(jì)權(quán)值成功!\n\n");printf(-各字符及其權(quán)值為:\n\n");fprintf(fp,"各字符及其權(quán)值為:\n");printf("字符\t權(quán)值")；fprintf(fp,"字符\t權(quán)值")；for(j=0;j<m;j++){printf("\n");fprintf(fp,"\n");printf("%-8c%-8d”,ht[j].data,ht[j].weight);fprintf(fp,”%-8c%-8d%”,ht[j].data,ht[j].weight);}printf("\n");printf("\n字符權(quán)值已輸出至文件"data.txt”！");fclose(fp);}〃構(gòu)造哈夫曼樹(shù)voidcreatHT(HTNodeht[],intn){FILE*fp;if((fp=fopen("哈夫曼樹(shù).txt","w"))=0){printf("\n\t\t文件打開(kāi)失敗!!!");return;}inti,j,k,lnode,rnode;intmin1,min2;for(i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;for(i=n;i<2*n-1;i++){min1=min2=32767;lnode=rnode=-1;for(k=0;k<=i-1;k++)if(ht[k].parent==-1){if(ht[k].weight<min1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}elseif(ht[k].weight<min2)min2=ht[k].weight;rnode=k;}}ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}printf("建立huffman樹(shù)成功!\n");printf("輸出huffman樹(shù):\n");fprintf(fp,"輸出huffman樹(shù):\n");printf("\t字符\t權(quán)值\t父節(jié)點(diǎn)\t左子節(jié)點(diǎn)\t右子節(jié)點(diǎn)")；fprintf(fp,"\t字符\t權(quán)值\t父節(jié)點(diǎn)\t左子節(jié)點(diǎn)\t右子節(jié)點(diǎn)”)；for(j=1;j<i;j++){printf("\n");fprintf(fp,"\n");printf("\t%-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,ht[i].lchild,ht[j].rchild);fprintf(fp,"\t%-8c%-8d%-10d%-14d%-10d",ht[j].data,ht[j].weight,ht[j].parent,ht[i].lchild,ht[j].rchild);}printf("\n");printf("哈夫曼樹(shù)已輸出至文件"哈夫曼樹(shù).txt”！按任意鍵返回!")；fclose(fp);getch();system("cls");return;}〃生成哈夫曼編碼voidCreateHCode(HTNodeht[],HCodehcd[],intn){inti,f,c,j=0;HCodehc;for(i=0;i<n;i++){hc.start=n;c=i;hc.cd[hc.start--]='0';f=ht[i].parent;while(f!=-1){if(ht[f].lchild=c)hc.cd[hc.start--]='0';elsehc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;for(j=0;j<hc.start;j++)hc.cd[j]='';hcd[i]=hc;}}voidDispHCode(HTNodeht[],HCodehcd[],intn){FILE*fp;if((fp=fopen("哈夫曼編碼.txt","w"))=0){printf("\n\t\t文件打開(kāi)失敗!!!");return;}inti,k;intsum=0,m=0,j;printf("輸出字符哈夫曼編碼:\n");fputs("輸出字符哈夫曼編碼:\n”,fp);for(i=0;i<n;i++)j=0；printf("%c:\t”,ht[i].data);fprintf(fp,"\n%c:\t”,ht[i].data);for(k=hcd[i].start;k<=n;k++){printf("%c",hcd[i].cd[k]);j++;fprintf(fp,"%c",hcd[i].cd[k]);}m+=ht[i].weight;sum+=ht[i].weight*j;printf("\n");}printf("\n哈夫曼編碼已保存至文件"哈夫曼編碼.txt!按任意鍵返回!");fclose(fp);getch();system("cls");}〃編碼函數(shù)voidbianma1(HTNodeht[],HCodehcd[],CHar&ch,intn,charbianma[]){inti;charstr[N];printf(-請(qǐng)輸入要編碼的字符集(以#結(jié)束):\n");for(i=0;i<N;i++){scanf("%c”,&str[i]);if(str[i]=='#'){str[i]='\0';break;}}strcpy(ch.s,str);ch.num=strlen(str);editHCode(ht,hcd,ch,n,bianma);getch();system("cls");return;}voidbianma2(HTNodeht[],HCodehcd[],CHar&ch,intn,charbianma[]){inti;FILE*fp;charfilename[20];printf("請(qǐng)輸入要打開(kāi)的文件名(*.txt):");scanf("%s”,&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文件打開(kāi)失敗!!!");return;}for(i=0;!feof(fp);i++){fread(&ch.s[i],sizeof(char),1,fp);}ch.num=strlen(ch.s);printf("\n讀入成功!\n");printf("文件中的字符集為:\n%s",ch.s);fclose(fp);editHCode(ht,hcd,ch,n,bianma);getch();system("cls");return;}〃譯碼函數(shù)voidyima1(HTNodeht[],HCodehcd[],intn,charbianma[]){inti;charcode[MAXcode];printf("請(qǐng)輸入編碼進(jìn)行譯碼(以#結(jié)束):\n");for(i=0;i<MAXcode;i++){scanf("%c”,&code[i]);if(code[i]=='#'){code[i]='\0';break;}}strcpy(bianma,code);printyima(ht,hcd,n,bianma);printf(-\n譯碼完成！按任意鍵返回!")；getch();system("cls");return;}voidyima2(HTNodeht[],HCodehcd[],intn,charbianma[]){inti;FILE*fp;charfilename[20];printf("請(qǐng)輸入要打開(kāi)的文件名(*.txt):");scanf("%s”,&filename);if((fp=fopen(filename,"r"))==NULL){printf("\n\t\t文件打開(kāi)失敗!!!");return;}for(i=0;!feof(fp);i++){fread(&bianma[i],sizeof(char),1,fp);}printf("讀入成功!\n");printf("文件中的編碼是:％s\n",bianma);printyima(ht,hcd,n,bianma);printf(-\n譯碼完成！按任意鍵返回!")；getch();system("cls");}四、調(diào)試結(jié)果主菜單建立字符權(quán)值選擇2.從文件讀入字符進(jìn)行統(tǒng)計(jì)輸入測(cè)試文件名"cs.txt”輸出個(gè)字符權(quán)值"C:\Users\xuchao\Deski。pk.誄圜就h.Debug'\吟大晏裁磚與譯瑪器,exe'；件點(diǎn)的岸符集為：alieshiyipi.anceshiuendanq?統(tǒng)計(jì)權(quán)值成功T各字符及其權(quán)值為:宇符權(quán)隹宇符13□7211111輸己至文件七拓任意世返回，Vhuffnan-；礦成功1輸出Huffman^ij: