哈夫曼編碼譯碼器

參考文獻(xiàn)[1]嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).清華大學(xué)出版社，2007[2]譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)教程.高等教育出版社，2006[3]蘇仕華.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).機(jī)械工業(yè)出版社，2007沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告附錄源程序如下：#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedefstruct{//赫夫曼樹(shù)的結(jié)構(gòu)體 charch; intweight;//權(quán)值 intparent,lchild,rchild;}Htnode,*Hfmtree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù)typedefchar**Hfmcode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表voidSelect(Hfmtree&HT,inta,int*s1,int*s2)//Select函數(shù)，選出HT樹(shù)到a為止，權(quán)值最小且parent為0的2個(gè)節(jié)點(diǎn){ inti,j,x,y; for(j=1;j<=a;++j){ if(HT[j].parent==0){ x=j; break; } } for(i=j+1;i<=a;++i){ if(HT[i].weight<HT[x].weight&&HT[i].parent==0){ x=i;//選出最小的節(jié)點(diǎn) } } for(j=1;j<=a;++j) { if(HT[j].parent==0&&x!=j) { y=j; break; } } for(i=j+1;i<=a;++i) { if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i) { y=i;//選出次小的節(jié)點(diǎn) } } if(x>y){ *s1=y; *s2=x; } else { *s1=x; *s2=y; }}voidHfmcoding(Hfmtree&HT,Hfmcode&HC,intn)//構(gòu)建赫夫曼樹(shù)HT，并求出n個(gè)字符的赫夫曼編碼HC{ inti,start,c,f,m,w; intp1,p2; char*cd,z; if(n<=1){ return; } m=2*n-1; HT=(Hfmtree)malloc((m+1)*sizeof(Htnode)); for(i=1;i<=n;++i)//初始化n個(gè)葉子結(jié)點(diǎn) { printf("請(qǐng)輸入第%d字符信息和權(quán)值：",i); scanf("%c%d",&z,&w); while(getchar()!='\n') { continue; } HT[i].ch=z; HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(;i<=m;++i)//初始化其余的結(jié)點(diǎn) { HT[i].ch='0'; HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=n+1;i<=m;++i)//建立赫夫曼樹(shù) { Select(HT,i-1,&p1,&p2); HT[p1].parent=i; HT[p2].parent=i; HT[i].lchild=p1; HT[i].rchild=p2; HT[i].weight=HT[p1].weight+HT[p2].weight; } HC=(Hfmcode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0';//從葉子到根逆向給出每個(gè)字符的哈夫曼編碼 for(i=1;i<=n;++i) { start=n-1;//編碼起始符位置 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼 { if(HT[f].lchild==c) { cd[--start]='0'; } else { cd[--start]='1'; } } HC[i]=(char*)malloc((n-start)*sizeof(char));//為地i個(gè)字符編碼分配空間 strcpy(HC[i],&cd[start]); } free(cd);}voidmain(){ charcode[100],h[100],hl[100]; intn,i,j,k,l; ifstreaminput_file;//文件輸入輸出流 ofstreamoutput_file; charchoice,str[100]; HfmtreeHT; HfmcodeHC; while(choice!='4')//當(dāng)choice的值4時(shí)循環(huán) {printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("*************************赫夫曼編碼/譯碼器*************************\n"); printf("*************************1創(chuàng)建哈夫曼樹(shù)*************************\n"); printf("*************************2編碼*************************\n"); printf("*************************3譯碼*************************\n"); printf("*************************4退出*************************\n"); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("請(qǐng)輸入您要操作的步驟"); cin>>choice; if(choice=='1')//初始化赫夫曼樹(shù) { cout<<"請(qǐng)輸入字符個(gè)數(shù)："; cin>>n; Hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout<<HT[i].ch<<":"<<HC[i]<<endl; } output_file.open("hfmTree.txt"); if(!output_file){ cout<<"can'toenfile!"<<endl; } for(i=1;i<=n;i++) { output_file<<"("<<HT[i].ch<<HC[i]<<")"; } output_file.close(); printf("赫夫曼樹(shù)已經(jīng)創(chuàng)建完畢，并且已經(jīng)放入hfmTree.txt文件中!\n"); } elseif(choice=='2')//進(jìn)行編碼，并將字符放入A.txt，碼值放入B.txt中 { printf("請(qǐng)輸入字符："); gets(str); output_file.open("A.txt"); if(!output_file) { cout<<"can'toenfile!"<<endl; } output_file<<str<<endl; output_file.close(); output_file.open("B.txt"); if(!output_file){ cout<<"can'toenfile!"<<endl; } for(i=0;i<strlen(str);i++){ for(j=0;j<=n;++j) { if(HT[j].ch==str[i]) { output_file<<HC[j]; break; } } } output_file.close(); cout<<"\n"; printf("編碼完畢，并且已經(jīng)存入B.txt文件！\n"); input_file.open("B.txt");//從B.txt中讀入編碼，輸出在終端 if(!input_file) { cout<<"can'toenfile!"<<endl; } input_file>>code; cout<<"編碼碼值為："<<code<<endl; input_file.close(); } elseif(choice=='3')//讀入B.txt中的編碼進(jìn)行譯碼，將譯出來(lái)的字符放入Textfile.txt中 { input_file.open("B.txt"); if(!input_file){ cout<<"can'toenfile!"<<endl; } input_file>>h; input_file.close(); output_file.open("Textfile.txt"); if(!output_file) { cout<<"can'toenfile!"<<endl; } k=0; while(h[k]!='\0')//先用編碼中的前幾個(gè)和字符的編碼相比較，然后往后移 { for(i=1;i<=n;i++){ l=k; for(j=0;j<strlen(HC[i]);j++,l++){ hl[j]=h[l]; } hl[j]='\0'; if(strcmp(HC[i],hl)==0) { output_file<<HT[i].ch; k=k+strlen(HC[i]); break; } } } output_file.close(); input_file.open("Textfile.txt"); if(!input_file){ cout<<"can'toenfile!"<<endl; } input_file>>h; cout<<h<<endl; input_file.close(); printf("譯碼結(jié)束，字符已經(jīng)存入Textfile.txt文件中!\n"); } elseif(choice=='4') { exit(0); } else//如果選了選項(xiàng)之外的就讓用戶重新選擇 { printf("您沒(méi)有輸入正確的步驟，請(qǐng)重新輸入！"); } }}沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告

課程設(shè)計(jì)總結(jié)：通過(guò)近兩周的課程設(shè)計(jì)使我對(duì)哈夫曼樹(shù)以及哈夫曼編碼譯碼有了更深的認(rèn)識(shí)和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。在做課設(shè)的過(guò)程中我也遇到了很多問(wèn)題：開(kāi)始的時(shí)候，代碼中有許多的錯(cuò)誤，特別是有一個(gè)“無(wú)法找到文件”的錯(cuò)誤讓我束手無(wú)策，最后還是屏蔽了定義的四個(gè)頭文件然后慢慢地改正錯(cuò)誤才讓我又看到了希望。然后在實(shí)現(xiàn)文章的讀入時(shí)，由于對(duì)文件不是太熟悉，只好翻開(kāi)C語(yǔ)言和C++語(yǔ)言書本仿照其模式編寫，但后來(lái)進(jìn)入了死循環(huán)，最后的解決方式是在main函數(shù)里有一個(gè)控制語(yǔ)句使用不正確。我們遇到問(wèn)題很正常，說(shuō)明我們掌握的知識(shí)還是太少不靈活，并且這些