哈夫曼編譯碼器-c語言

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)目錄1.問題描述……………第2頁2.系統(tǒng)設(shè)計(jì)……………第2頁3.數(shù)據(jù)結(jié)構(gòu)與算法描述………………第5頁4.測(cè)試結(jié)果與分析……第6頁5.總結(jié)………………第10頁6.參考文獻(xiàn)……………第10頁附錄程序源代碼………第11頁課程設(shè)計(jì)題目1.問題描述利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸本錢。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼〔復(fù)原〕。試為這樣的信息傳輸寫一個(gè)哈夫曼編/譯碼系統(tǒng)。2.系統(tǒng)設(shè)計(jì)2.1設(shè)計(jì)目標(biāo)一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：1〕I：初始化〔Initialization〕。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。輸出哈夫曼樹，及各字符對(duì)應(yīng)的編碼。2〕W：輸入〔Input〕。從終端讀入需要編碼的字符串s，將字符串s存入文件Tobetran.txt中。3〕E：編碼〔Encoding〕與譯碼〔Decoding〕。編碼〔Encoding〕。利用已建好的哈夫曼樹〔如不在內(nèi)存，那么從文件htmTree中讀入〕，對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。譯碼〔Decoding〕。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。印代碼文件〔Print〕。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼寫入文件CodePrint中。4〕T：印哈夫曼樹〔TreePrinting〕。將已在內(nèi)存中的哈夫曼樹以直觀的方式〔樹或凹入表形式〕顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。5〕Q：退出程序。返回WINDOWS界面。2.2設(shè)計(jì)思想哈夫曼編碼(HuffmanCoding)是一種編碼方式，以哈夫曼樹─即最優(yōu)二叉樹，帶權(quán)路徑長(zhǎng)度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。是指使用一張?zhí)厥獾木幋a表將源字符〔例如某文件中的一個(gè)符號(hào)〕進(jìn)行編碼。這種方法是由David.A.Huffman開展起來的。例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率那么最低。當(dāng)利用哈夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)位(bit)來表示，而z那么可能花去25個(gè)位〔不是26〕。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)〔byte〕，即8個(gè)位。二者相比，e使用了一般編碼的1/8的長(zhǎng)度，z那么使用了3倍多。倘假設(shè)我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無損壓縮的比例。2.3系統(tǒng)模塊劃分main()Initialization〔〕初始化函數(shù)main()Initialization〔〕初始化函數(shù)Input()輸入待編碼字符函數(shù)Encoding〔〕編碼函數(shù)Decoding〔〕譯碼函數(shù)Code_printing()打印編碼函數(shù)Tree_printing()打印哈夫曼樹初始化算法：程序從文件abc.txt中獲取26個(gè)英文字母的權(quán)值。編碼算法：〔1〕對(duì)輸入的一段欲編碼的字符串進(jìn)行統(tǒng)計(jì)各個(gè)字符出現(xiàn)的次數(shù)，并它們轉(zhuǎn)化為權(quán)值{w1,w2,……，wN}構(gòu)成n棵二叉樹的集合F={T1,T2,……，Tn}把它們保存到結(jié)構(gòu)體數(shù)組HT[n]中,其中{Ti是按它們的ASCⅡ碼值先后排序。其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為Wi的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。

〔2〕在HT[1..i]中選取兩棵根結(jié)點(diǎn)的權(quán)值最小且沒有被選過的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。

〔3〕哈夫曼樹已經(jīng)建立后，從葉子到根逆向求每一個(gè)字符的哈夫曼編碼。

2.3.3譯碼算法：

譯碼的過程是分解電文中字符串，從根出發(fā)，按字符'0',或'1'確定找左孩子或右孩子，直至葉子結(jié)點(diǎn)，便求的該子串相應(yīng)字符并輸出接著下一個(gè)字符。3.數(shù)據(jù)結(jié)構(gòu)與算法描述3-1typedefstruct{intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹

typedefchar**HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表3-2intmin(HuffmanTreet,inti)//---------求赫夫曼編碼-------------3-3voidselect(HuffmanTreet,inti,int&s1,int&s2)//----slect函數(shù)----3-4voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)//w存放n個(gè)字符的權(quán)值(均>0),構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的赫夫曼編碼HC3-5voidInitialization()//----------初始化赫夫曼鏈表--------------3-6voidInputCode()//---------獲取報(bào)文并寫入文件-------------3-7voidEncoding()//----------------編碼函數(shù)------------------3-8voidDecoding()//-----------------譯碼函數(shù)-----------------3-9voidCode_printing()//-------------打印編碼的函數(shù)--------------3-19voidcoprint(HuffmanTreestart,HuffmanTreeHT)//------------------------打印赫夫曼樹的函數(shù)-----------------------3-20voidmain()//--------------------主函數(shù)-------------------4.測(cè)試結(jié)果與分析A186B64C13D22E32F103G21H15I47J57K15L32M20N57O63P15Q1R48S51T80U23V8W18X1Y16Z1

表4-1abc.txt文件中的字母和權(quán)值聲明：程序預(yù)先將Huffman編碼解碼所需的26個(gè)字母和權(quán)值保存在根目錄下的abc.txt文件下。4-1.按照程序提示輸入i對(duì)Huffman進(jìn)行初始化。4-2.初始化后程序?qū)bc.txt文件中的數(shù)據(jù)進(jìn)行讀取并運(yùn)行編碼函數(shù)進(jìn)行哈夫曼編碼。然后將字母、權(quán)值和哈夫曼編碼存在根目錄下的htmTree.txt文件中。在屏幕顯示出字符、權(quán)值、編碼。4-3.輸入w進(jìn)入待編碼字符輸入窗口，并鍵入字符串〔注意單詞間無空格〕“happynewyear〞。4-4.可以看出所獲得的字符串已經(jīng)存入根目錄下的tobetran.txt文件中。4-5.輸入e進(jìn)行編碼、譯碼和打印編碼功能。4-6.輸入t打印哈夫曼樹。由于哈夫曼樹過于巨大，一次截屏無法完全顯示，使用兩次截屏。以上兩幅圖顯示出來程序編出的哈夫曼樹的形狀。打印出來的圖形與教科書上的常見哈夫曼樹略有不同，左邊的數(shù)是右邊數(shù)的父節(jié)點(diǎn)。4-7.輸入q退出程序。5.總結(jié)5-1、用戶界面設(shè)計(jì)為“菜單〞模式，使人們更加容易使用。5-2、在程序的一次執(zhí)行過程中，第一次執(zhí)行e命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。5-3.在編程中使用了很不標(biāo)準(zhǔn)的編程方法，應(yīng)用了一些臨時(shí)變量來實(shí)現(xiàn)功能，，而大量臨時(shí)變量在代碼中沒有很好地進(jìn)行命名。這給程序的閱讀和維護(hù)帶來了極大的困難。5-4.本程序僅能對(duì)26個(gè)小寫字母構(gòu)成的字符串進(jìn)行處理，并不具有對(duì)漢字等的編碼處理能力。5-5.設(shè)計(jì)中得到了老師和廣闊同學(xué)的幫助，并參考了網(wǎng)絡(luò)上的優(yōu)秀論文和紙質(zhì)文件，使我的程序設(shè)計(jì)能夠較為順利的進(jìn)行下去。在此我衷心感謝我的老師同學(xué)和對(duì)以上資源的作者。6.參考文獻(xiàn)A：書籍資料[1]李春葆《數(shù)據(jù)結(jié)構(gòu)教程上機(jī)實(shí)驗(yàn)指導(dǎo)》北京：清華大學(xué)出版社[2]嚴(yán)蔚敏吳偉民《數(shù)據(jù)結(jié)構(gòu)〔C語言版〕》北京：清華大學(xué)出版社[3]蘇仕華《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》北京：機(jī)械工業(yè)出版社B：網(wǎng)絡(luò)資料[1]哈夫曼編/譯碼器(課程設(shè)計(jì)).html[2]哈夫曼編碼432169091693efce3bc763ab.html附錄程序源代碼//哈夫曼編/譯碼器(課程設(shè)計(jì))2023/5/21#include<iostream.h>#include<fstream.h>#include<iomanip.h>#include<string.h>#include<malloc.h>#include<stdio.h>#include<iomanip.h>constintUINT_MAX=10000;typedefstruct{intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹

typedefchar**HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表//--------------------全局變量-----------------------HuffmanTreeHT;HuffmanCodeHC;int*w,i,j;constintn=26;char*z;intflag=0;intnumb=0;//-----------------求赫夫曼編碼---------------------intmin(HuffmanTreet,inti){//此函數(shù)將要被voidselect()調(diào)用intj,flag;intk=UINT_MAX;//取k為不小于可能的值for(j=1;j<=i;j++)if(t[j].weight<k&&t[j].parent==0)k=t[j].weight,flag=j;t[flag].parent=1;returnflag;}//--------------------slect函數(shù)----------------------voidselect(HuffmanTreet,inti,int&s1,int&s2){//s1為最小的兩個(gè)值中序號(hào)小的那個(gè)intj;s1=min(t,i);s2=min(t,i);if(s1>s2){j=s1;s1=s2;s2=j;}}//-------------------參考課本算法6.12-------------------voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n個(gè)字符的權(quán)值(均>0),構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的赫夫曼編碼HCintm,i,s1,s2,start;intc,f;HuffmanTreep;char*cd;if(n<=1)return;//檢測(cè)結(jié)點(diǎn)數(shù)是否可以構(gòu)成樹m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號(hào)單元未用for(p=HT+1,i=1;i<=n;++i,++p,++w){p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p)p->parent=0;for(i=n+1;i<=m;++i)//建赫夫曼樹{//在HT[1~i-1]中選擇parent=0且weight最小的兩個(gè)結(jié)點(diǎn),其序號(hào)分別為s1和s2select(HT,i-1,s1,s2);HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//從葉子到根逆向求每個(gè)字符的赫夫曼編碼HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個(gè)字符編碼的頭指針向量([0]不用)cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間cd[n-1]='\0';//編碼結(jié)束符for(i=1;i<=n;i++){//逐個(gè)字符求赫夫曼編碼start=n-1;//編碼結(jié)束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));//為第i個(gè)字符編碼分配空間strcpy(HC[i],&cd[start]);//從cd復(fù)制編碼(串)到HC}free(cd);//釋放工作空間}//----------------------初始化赫夫曼鏈表-------------------------voidInitialization(){flag=1;intnum2;cout<<"下面初始化赫夫曼鏈表"<<endl; w=(int*)malloc(n*sizeof(int));//為第26個(gè)字符權(quán)值分配空間z=(char*)malloc(n*sizeof(char));//為第26個(gè)字符分配空間cout<<"\n依次顯示"<<n<<"個(gè)字符與其權(quán)值和編碼\n"<<endl;charbase[2];//? ifstreamfin("abc.txt");for(i=0;i<n;i++) { fin>>base;*(z+i)=*base;//? fin>>num2;//上面123行*(w+i)=num2; }HuffmanCoding(HT,HC,w,n);//----------------------------------打印編碼--------------------------------------- cout<<"字符"<<setw(6)<<"權(quán)值"<<setw(11)<<"編碼"<<endl;for(i=1;i<=n;i++){ cout<<setw(3)<<*(z+i-1);cout<<setw(6)<<*(w+i-1)<<setw(12)<<HC[i]<<endl;}//--------------------------將赫夫曼編碼寫入文件----------------------------cout<<"下面將赫夫曼編碼寫入文件"<<endl<<"...................."<<endl;FILE*htmTree;charr[]={'','\0'};if((htmTree=fopen("htmTree.txt","w"))==NULL){cout<<"不能翻開文件"<<endl;return;}for(i=0;i<n;i++){fputc(*(z+i),htmTree); fputs(r,htmTree); } for(i=0;i<n;i++){fprintf(htmTree,"%6d",*(w+i));fputs(r,htmTree); }for(i=1;i<=n;i++){fputs(HC[i],htmTree);fputs(r,htmTree);}fclose(htmTree);cout<<"已將字符與對(duì)應(yīng)編碼寫入根目錄下文件htmTree.txt中"<<endl<<endl;}//--------------------------獲取報(bào)文并寫入文件---------------------------voidInputCode(){FILE*tobetran;charstr[100];if((tobetran=fopen("tobetran.txt","w"))==NULL){cout<<"不能翻開文件"<<endl;return;}cout<<"請(qǐng)輸入你想要編碼的字符"<<endl;//字符個(gè)數(shù)應(yīng)當(dāng)小于100gets(str);fputs(str,tobetran);cout<<"獲取報(bào)文成功"<<endl;fclose(tobetran);cout<<"...................."<<endl<"報(bào)文存入根目錄下的tobetran.txt文件中"<<endl;}//---------------------------------編碼函數(shù)---------------------------------voidEncoding(){cout<<"下面對(duì)目錄下文件tobetran.txt中的字符進(jìn)行編碼"<<endl;FILE*tobetran,*codefile;if((tobetran=fopen("tobetran.txt","rb"))==NULL){cout<<"不能翻開文件"<<endl;}if((codefile=fopen("codefile.txt","wb"))==NULL){cout<<"不能翻開文件"<<endl;}char*tran;i=99;tran=(char*)malloc(100*sizeof(char));while(i==99){if(fgets(tran,100,tobetran)==NULL){cout<<"不能翻開文件"<<endl;break;}for(i=0;*(tran+i)!='\0';i++){for(j=0;j<=n;j++){if(*(z+j-1)==*(tran+i)){fputs(HC[j],codefile);if(j>n){cout<<"字符錯(cuò)誤，無法編碼!"<<endl;break;}}}}}cout<<"…………編碼完成…………"<<endl；cout<<"編碼寫入目錄下的codefile.txt中"<<endl<<endl;fclose(tobetran);fclose(codefile);free(tran);}//-------------------------譯碼函數(shù)---------------------------voidDecoding(){cout<<"下面對(duì)根目錄下文件codefile.txt中的字符進(jìn)行譯碼"<<endl;FILE*codef,*txtfile;if((txtfile=fopen("\\Textfile.txt","w"))==NULL){cout<<"不能翻開文件"<<endl;}txtfile=fopen("Textfile.txt","w");if((codef=fopen("codefile.txt","r"))==NULL){cout<<"不能翻開文件"<<endl;}codef=fopen("codefile.txt","r");char*work,*work2,i2;inti4=0,i,i3;unsignedlonglength=10000;work=(char*)malloc(length*sizeof(char));fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char));i3=2*n-1;for(i=0;*(work+i-1)!='\0';i++){i2=*(work+i);if(HT[i3].lchild==0){*(work2+i4)=*(z+i3-1);i4++;i3=2*n-1;i--;}elseif(i2=='0')i3=HT[i3].lchild;elseif(i2=='1')i3=HT[i3].rchild;}*(work2+i4)='\0';fputs(work2,txtfile);cout<<"…………譯碼完成…………"<<endl；cout<<"內(nèi)容寫入根目錄下的文件textfile.txt中"<<endl<<endl;free(work);//釋放工作區(qū)free(work2);//釋放工作區(qū)fclose(txtfile);//關(guān)閉文件txtfile.txtfclose(codef);//關(guān)閉文件codef.txt}//-----------------------打印編碼的函數(shù)----------------------voidCode_printing(){cout<<"下面打印根目錄下文件CodePrin.txt中編碼字符"<<endl;FILE*CodePrin,*codefile;if((CodePrin=fopen("CodePrin.txt","w"))==NULL){cout<<"不能翻開文件"<<endl;return;}if((codefile=fopen("codefile.txt","r"))==NULL){cout<<"不能翻開文件"<<endl;return;}char*work3;work3=(char*)malloc(51*sizeof(char));if(fgets(work3,51,codefile)==NULL){cout<<"不能讀取文件"<<endl;} elsedo{fputs(work3,CodePrin);puts(work3);}while(strlen(work3)==50&&fgets(work3,51,codefile)!=NULL);free(work3);cout<<"打印結(jié)束"<<endl<<endl;fclose(CodePrin);fclose(codefile);}//------------------------打印赫夫曼樹的函數(shù)-----------------------voidcoprint(HuffmanTreestart,HuffmanTreeHT)//start=ht+26這是一個(gè)遞歸算法{if(start!=HT){FILE*TreePrint;if((TreePrint=fopen("TreePrint.txt","a"))==NULL){cout<<"創(chuàng)立文件失敗"<<endl;return;}numb++;//number=0該變量為已被聲明為全局變量coprint(HT+start->rchild,HT);//遞歸先序遍歷cout<<setw(5*numb)<<start->weight<<endl;fprintf(TreePrint,"%d\n",start->weight);coprint(HT+start->lchild,HT);numb--;fclose(TreePrint);}}voidTree_printing(HuffmanTreeHT,intw){HuffmanTreep;p=HT+w;//p=HT+26cout<<"下面打印赫夫曼樹"<<endl;coprint(p,HT);//p=HT+26cout<<"打印工作結(jié)束"<<endl;}//----------------------------------主函數(shù)--------