數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-哈夫曼樹

/計(jì)算機(jī)科學(xué)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目：基于哈夫曼樹的文件壓縮/解壓程序?qū)W生姓名：林華專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級：12級〔2班指導(dǎo)教師姓名及職稱：陳明講師起止時(shí)間：2014年3月——2014年4月1需求分析1.1課題背景及意義近年來,隨著計(jì)算機(jī)技術(shù)的發(fā)展,多媒體計(jì)算機(jī)技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)以及現(xiàn)代多媒體通信技術(shù)正在向著信息化、高速化、智能化迅速發(fā)展。各個(gè)領(lǐng)域的應(yīng)用與發(fā)展,各個(gè)系統(tǒng)的數(shù)據(jù)量越來越大,給數(shù)據(jù)的存儲、傳輸以及有效、快速獲取信息帶來了嚴(yán)重的障礙。數(shù)據(jù)壓縮技術(shù)能夠比較有效地解決這個(gè)問題。還有在最近幾年中興起的物聯(lián)網(wǎng)和云計(jì)算都是對海量的數(shù)據(jù)進(jìn)行處理和傳輸?shù)?如果不對數(shù)據(jù)進(jìn)行壓縮,那么數(shù)據(jù)傳輸所需的帶寬要求就很高,物理成本上也隨之上升。所以說數(shù)據(jù)壓縮在計(jì)算機(jī)通信中占有很重要的位置,且涉及領(lǐng)域多,應(yīng)用廣泛,與我們的生活息息相關(guān)。1.2課題要求1.2.1．實(shí)現(xiàn)一個(gè)基于哈夫曼樹的文件壓縮程序和文件解壓程序。1.2.2.壓縮程序能輸入源文件進(jìn)行壓縮,輸出壓縮文件；1.2.3．解壓程序讀入壓縮文件,根據(jù)相應(yīng)的哈夫曼編碼解壓還原,得到對應(yīng)的源文件。1.2.4．可選做：求出壓縮率；打印哈夫曼樹；對文件夾壓縮；圖形圖形化窗口操作界面。1.3任務(wù)和要求1.3.1選擇1時(shí)：輸入一個(gè)待壓縮的文本文件名稱<可帶路徑>。

如:D:\1\XXX.txt

壓縮文件名稱=D:\1\XXX.zip1.3.2選擇2時(shí)：輸入一個(gè)待解壓的壓縮文件名稱<可帶路徑>。

如:D:\1\YYY.txt解壓文件名稱=D:\1\YYY.zip2概要設(shè)計(jì)2.1問題解決的思路概述建立哈夫曼樹建立哈夫曼樹根據(jù)哈夫曼樹解碼對二進(jìn)制文件進(jìn)行解碼根據(jù)哈夫曼樹解碼對二進(jìn)制文件進(jìn)行解碼統(tǒng)計(jì)字符,得出統(tǒng)計(jì)出字符的權(quán)值n根據(jù)哈夫曼樹編碼統(tǒng)計(jì)字符,得出統(tǒng)計(jì)出字符的權(quán)值n根據(jù)哈夫曼樹編碼對編碼進(jìn)行壓縮對編碼進(jìn)行壓縮生成哈夫曼樹生成哈夫曼樹生成對應(yīng)文件生成二進(jìn)制文件生成對應(yīng)文件生成二進(jìn)制文件圖1主程序流程圖2.2算法思想：2.2.1輸入要壓縮的文件首先運(yùn)行的時(shí)候,用戶主界面上有菜單提示該如何使用軟件,根據(jù)菜單提示選擇所要執(zhí)行的項(xiàng),依次進(jìn)行,因?yàn)楦鱾€(gè)環(huán)節(jié)之間有先后順序。第一步為輸入壓縮軟件的名稱,由鍵盤輸入文件路徑和文件名稱,讀入字符數(shù)組中,打開該文件,按照提示進(jìn)行壓縮。若打不開,則繼續(xù)輸入。2.2.2讀文件并計(jì)算字符頻率文件將信息存放在字符數(shù)組中；計(jì)算每個(gè)字符出現(xiàn)的次數(shù),申請一個(gè)結(jié)構(gòu)體數(shù)組空間,用讀取的字符減去字符結(jié)束符作為下標(biāo)記錄字符的頻率。2.2.3根據(jù)字符的頻率,利用Huffman編碼思想創(chuàng)建Huffman樹將所記錄的字符的頻率作為權(quán)值來創(chuàng)建Huffman樹,依次選擇權(quán)值最小的兩個(gè)字符作為左右孩子,其和作為父結(jié)點(diǎn)的權(quán)值,依次進(jìn)行下去,直到所有的字符結(jié)點(diǎn)都成為葉子結(jié)點(diǎn)。2.2.4由創(chuàng)建的Huffman樹來決定字符對應(yīng)的編碼,進(jìn)行文件的壓縮根據(jù)創(chuàng)建的Huffman樹來確定個(gè)字符的01編碼,左孩子為0,右孩子為1。讀取文件,依次將每個(gè)字符用他們的編碼表示,即完成一次編碼。2.2.5解碼壓縮即根據(jù)Huffman樹進(jìn)行譯碼讀取編碼文件,依據(jù)創(chuàng)建的Huffman樹,定義一個(gè)指針指向根結(jié)點(diǎn)。從根結(jié)點(diǎn)開始,每讀一個(gè)字符,指針變化一次〔當(dāng)讀取的字符是‘1’時(shí),指針指向當(dāng)前所指結(jié)點(diǎn)的右孩子,當(dāng)讀取的字符是‘0’時(shí),指針指向當(dāng)前所指結(jié)點(diǎn)的左孩子,直至該指針?biāo)附Y(jié)點(diǎn)為葉子結(jié)點(diǎn)時(shí)結(jié)束〔即當(dāng)結(jié)點(diǎn)的左右孩子均為空時(shí)。將當(dāng)前葉子結(jié)點(diǎn)所代表的字符值輸出到譯碼文件中,依次讀取編碼文件中的字符,按照上述方法依次進(jìn)行下去直至文件2.3數(shù)據(jù)結(jié)構(gòu)定義typedefstructnode//哈夫曼樹結(jié)構(gòu)體{longw;//權(quán)重shortp,l,r;//定義雙親,左孩子,右孩子}htnode,*htnp;typedefstructhuffman_code{unsignedcharlen;//記錄該結(jié)點(diǎn)哈夫曼編碼的長度unsignedchar*codestr;//記錄該結(jié)點(diǎn)的哈夫曼編碼}hufcode;2.5主程序的流程及模塊間關(guān)系主函數(shù)實(shí)例化huffmanTree類,并實(shí)現(xiàn)菜單工具欄,通過用戶的選擇輸入,用switch語句進(jìn)行分支執(zhí)行huffmanTree類中功能函數(shù)：1:壓縮函數(shù)intcompress<char*source_file,char*obj_file>；2:解壓函數(shù)intdecompress<char*source_file,char*obj_file>；并可在完成相應(yīng)功能后安全退出,壓縮或解壓的文件在同文件夾下生成。3.詳細(xì)設(shè)計(jì)核心算法huffman算法：3.1根據(jù)給定的n個(gè)權(quán)值｛w1,w2,……,wn｝構(gòu)成n棵二叉樹的集合F=｛T1,T2,……,Tn｝,其中每棵二叉樹T1中只有一個(gè)帶權(quán)的w1的根據(jù)點(diǎn),其左右子樹均空。3.2在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹,且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右樹上根結(jié)點(diǎn)的權(quán)值之和。3.3在F中刪除這兩棵樹,同時(shí)將所得到的二叉樹加入F中。3.4重復(fù)3.2,3.3,直到F中只含一棵樹為止。這棵樹便是Huffman樹。Huffman樹可用于構(gòu)造代碼總長度最短的編碼方案。為了詳細(xì)說明這個(gè)問題,特以下面例子來說明:圖2問題詳解編碼完成之后,開始對源文件進(jìn)行壓縮。從源文件讀一個(gè)字符,從葉子結(jié)點(diǎn)中找出和此字符相同的字符結(jié)點(diǎn),將其編碼寫入一個(gè)臨時(shí)字符組codes；當(dāng)codes的長度大于等于8時(shí),將其前8位轉(zhuǎn)換成字符寫入目標(biāo)文件中；重復(fù)1和2此過程,直至讀完源文件中的所有字符；若codes最后還有剩余的不足8位的01代碼,則將其低位補(bǔ)0至8位,再寫入目標(biāo)文件。主程序模塊:圖3主程序模塊調(diào)試分析報(bào)告由于壓縮與解壓過程中沒有輸入新生成文件的路徑,因此解壓后的文件會將原文件覆蓋。如圖：圖4壓縮前原文件圖5壓縮后生成文件圖6解壓后文件5.用戶使用說明在運(yùn)行程序之前,首先在D盤先建立一個(gè)待壓縮的文件1.doc,運(yùn)行程序如下圖所示。圖7版本測試結(jié)果圖壓縮：在命令行下輸入1對文件進(jìn)行壓縮,根據(jù)提示輸入剛剛建的文本文件〔1.doc,和要生成的壓縮文件名稱,按回車確認(rèn)進(jìn)行壓縮。圖8執(zhí)行壓縮操作圖成功執(zhí)行完畢后如下圖所示。圖9執(zhí)行壓縮操作圖選擇打印哈夫曼樹及編碼。圖10執(zhí)行打印操作圖解壓：在命令行下輸入2對本程序壓縮的文件進(jìn)行恢復(fù),根據(jù)提示輸入待恢復(fù)的文件名稱和恢復(fù)后的文件名稱,按回車確定,成功執(zhí)行后如下圖所示。圖11執(zhí)行解壓操作圖6.測試結(jié)果詳細(xì)測試結(jié)果請參見5使用功能。6.1測試報(bào)告原文件壓縮后解壓后1txt文件<14598b>8192b8192b2pdf文件<359398b>356352b359398b3jpg文件<31455b>28672b31455b4Mp3文件<72000b>69632b72000b參考文獻(xiàn)[1]鄭莉等編著《C++語言程序設(shè)計(jì)〔第三版》北京：清華大學(xué)出版社.[2]譚浩強(qiáng).C++面向?qū)ο蟪绦蛟O(shè)計(jì)<第二版>[M].北京：中國鐵道出版社,2009.[3]洪國勝等編著《C++Builder程序設(shè)計(jì)輕松上手》北京：清華大學(xué)出版社.[4]胡學(xué)鋼等《數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo)》北京：清華大學(xué)出版社,1999年第1版.[5]王昆侖等編著《數(shù)據(jù)結(jié)構(gòu)域算法〔高等學(xué)校計(jì)算機(jī)精品課程系列教材》中國鐵道工業(yè)出版社.附錄：源程序#include<stdio.h>#include<string.h>#include<stdlib.h>#include<windows.h>typedefstructnode//哈夫曼樹結(jié)構(gòu)體{longw;//權(quán)重shortp,l,r;//定義雙親,左孩子,右孩子}htnode,*htnp;typedefstructhuffman_code{unsignedcharlen;//記錄該結(jié)點(diǎn)哈夫曼編碼的長度unsignedchar*codestr;//記錄該結(jié)點(diǎn)的哈夫曼編碼}hufcode;typedefchar**huffmancode;intinitial_files<char*source_file,FILE**inp,char*obj_file,FILE**outp>;//文件初始信息char*create_file<char*source_file,char*obj_file>;//創(chuàng)建待壓縮文件名intcompress<char*source_file,char*obj_file>;//壓縮函數(shù)longfrequency_data<FILE*in,longfre[]>;//計(jì)算字符頻率intsearch_set<htnpht,intn,int*s1,int*s2>;//查找文件intcreate_hftree<longw[],intn,htnodeht[]>;//創(chuàng)建哈夫曼樹intencode_hftree<htnphtp,intn,hufcodehc[]>;//記錄哈夫曼編碼unsignedcharchars_to_bits<constunsignedcharchars[8]>;//計(jì)算文件大小intwrite_compress_file<FILE*in,FILE*out,htnpht,hufcodehc[],char*source_file,longsource_filesize>;//輸入待壓縮文件路徑intdecompress<char*source_file,char*obj_file>;//解壓函數(shù)voidget_mini_huffmantree<FILE*in,shortmini_ht[][2]>;//建立哈弗曼樹中用于選擇最小權(quán)值結(jié)點(diǎn)的函數(shù)intwrite_decompress_file<FILE*in,FILE*out,shortmini_ht[][2],longbits_pos,longobj_filesize>;//輸入待解壓文件路徑intd_initial_files<char*source_file,FILE**inp,char*obj_file,FILE**outp>;main<>{ ints; charfile[10]; system<"color3F">; printf<"***************************************\n">; printf<"*菜單：*\n">; printf<"*1.壓縮*\n">; printf<"*2.解壓*\n">; printf<"*0.退出*\n">; printf<"***************************************\n">; scanf<"%d",&s>; while<s!=0> { getchar<>; switch<s> { case1: puts<"請輸入待壓縮文件路徑：">; gets<file>; compress<file,NULL>; break; case2: puts<"請輸入待解壓文件路徑：">; gets<file>; decompress<file,NULL>; break; default: printf<"指令錯誤！請重新輸入指令：\n">; } puts<"">; printf<"***************************************\n">; printf<"*菜單：*\n">; printf<"*1.壓縮*\n">; printf<"*2.解壓*\n">; printf<"*0.退出*\n">; printf<"***************************************\n">; scanf<"%d",&s>; }}//文件初始信息intinitial_files<char*source_file,FILE**inp,char*obj_file,FILE**outp>{if<fopen<source_file,"rb">==NULL>{return-1;}if<obj_file==NULL>{if<<obj_file=<char*>malloc<256*sizeof<char>>>==NULL>{return-1;}create_file<source_file,obj_file>;}if<strcmp<source_file,obj_file>==0>{return-1;}printf<"待壓縮文件:%s,壓縮文件:%s\n",source_file,obj_file>;if<<*outp=fopen<obj_file,"wb">>==NULL>{return-1;}if<<*inp=fopen<source_file,"rb">>==NULL>{return-1;}free<obj_file>;return0;}//創(chuàng)建待壓縮文件名char*create_file<char*source_file,char*obj_file>{char*temp;if<<temp=strrchr<source_file,'.'>>==NULL>{strcpy<obj_file,source_file>;strcat<obj_file,".zip">;}else{strncpy<obj_file,source_file,temp-source_file>;obj_file[temp-source_file]='\0';strcat<obj_file,".zip">;} returnobj_file;}//壓縮函數(shù)intcompress<char*source_file,char*obj_file>{FILE*in,*out; charch;interror_code,i,j;floatcompress_rate;hufcodehc[256];//編碼的位數(shù)最多為256位htnodeht[256*2-1];longfrequency[256],source_filesize,obj_filesize=0;error_code=initial_files<source_file,&in,obj_file,&out>;if<error_code!=0>{ puts<"文件打開失敗！請重新輸入文件路徑：">;returnerror_code;}source_filesize=frequency_data<in,frequency>;printf<"文件大小%ld字節(jié)\n",source_filesize>;error_code=create_hftree<frequency,256,ht>;if<error_code!=0>{ puts<"建立哈夫曼樹失?。?>;returnerror_code;}error_code=encode_hftree<ht,256,hc>;if<error_code!=0>{ puts<"建立哈夫曼編碼失??！">;returnerror_code;}for<i=0;i<256;i++>obj_filesize+=frequency[i]*hc[i].len;obj_filesize=obj_filesize%8==0?obj_filesize/8:obj_filesize/8+1;for<i=0;i<256-1;i++>obj_filesize+=2*sizeof<short>;obj_filesize+=strlen<source_file>+1;obj_filesize+=sizeof<long>;obj_filesize+=sizeof<unsignedint>;compress_rate=<float>obj_filesize/source_filesize;printf<"壓縮文件大小:%ld字節(jié),壓縮比例:%.2lf%%\n",obj_filesize,compress_rate*100>;error_code=write_compress_file<in,out,ht,hc,source_file,source_filesize>; if<error_code!=0>{ puts<"寫入文件失?。?>;returnerror_code;}puts<"壓縮完成!">; puts<"">; puts<"是否打印該文件中字符對應(yīng)的huffman樹及編碼？">; puts<"PleaseinputYORN">; do{ scanf<"%s",&ch>; switch<ch> { case'Y': puts<"以下是哈夫曼樹：">; for<i=256;i<256*2-2;i++> { if<ht[i].w>0> printf<"%-10d%-10d%-10d%-10d%-10d\n",i,ht[i].w,ht[i].p,ht[i].l,ht[i].r>; } puts<"以下是哈夫曼編碼：">; for<i=0;i<256;i++> { if<frequency[i]==0> i++; else { printf<"%d\t",frequency[i]>; for<j=0;j<hc[i].len;j++> printf<"%d",hc[i].codestr[j]>; printf<"\n">; } } break; case'N': break; default: printf<"指令錯誤！請重新輸入指令：\n">; } }while<ch!='Y'&&ch!='N'>;fclose<in>;fclose<out>;for<i=0;i<256;i++>{free<hc[i].codestr>;}return0;}//計(jì)算字符頻率longfrequency_data<FILE*in,longfrequency[]>{inti,read_len;unsignedcharbuf[256];longfilesize;for<i=0;i<256;i++>//去掉權(quán)值為0的結(jié)點(diǎn){frequency[i]=0;}fseek<in,0L,SEEK_SET>;read_len=256;while<read_len==256>{read_len=fread<buf,1,256,in>;for<i=0;i<read_len;i++>//初始化根結(jié)點(diǎn){frequency[*<buf+i>]++;}}for<i=0,filesize=0;i<256;i++>{filesize+=frequency[i];}returnfilesize;}intsearch_set<htnpht,intn,int*s1,int*s2>{inti,x; longminValue=999999,min=0;for<x=0;x<n;x++>{if<ht[x].p==-1>break;}for<i=0;i<n;i++>{if<ht[i].p==-1&&ht[i].w<minValue>{ minValue=ht[i].w;min=i;}}*s1=min;minValue=999999,min=0;for<i=0;i<n;i++>{if<ht[i].p==-1&&ht[i].w<minValue&&i!=*s1>{ minValue=ht[i].w;min=i;}}*s2=min;return1;}//創(chuàng)建哈夫曼樹intcreate_hftree<longw[],intn,htnodeht[]>{intm,i,s1,s2;if<n<1>return-1;m=2*n-1;if<ht==NULL>return-1;for<i=0;i<n;i++>{ht[i].w=w[i]; ht[i].p=ht[i].l=ht[i].r=-1;}for<;i<m;i++>{ht[i].w=ht[i].p=ht[i].l=ht[i].r=-1;}for<i=n;i<m;i++>{search_set<ht,i,&s1,&s2>;ht[s1].p=ht[s2].p=i;ht[i].l=s1; ht[i].r=s2;ht[i].w=ht[s1].w+ht[s2].w;}return0;}intencode_hftree<htnphtp,intn,hufcodehc[]>{inti,j,p,codelen;unsignedchar*code=<unsignedchar*>malloc<n*sizeof<unsignedchar>>;if<code==NULL>return-1;for<i=0;i<n;i++>{for<p=i,codelen=0;p!=2*n-2;p=htp[p].p,codelen++>{code[codelen]=<htp[htp[p].p].l==p?0:1>;}if<<hc[i].codestr=<unsignedchar*>malloc<<codelen>*sizeof<unsignedchar>>>==NULL>{return-1;}hc[i].len=codelen;for<j=0;j<codelen;j++>{hc[i].codestr[j]=code[codelen-j-1];}}free<code>;return0;}unsignedcharchars_to_bits<constunsignedcharchars[8]>{inti;unsignedcharbits=0;bits|=chars[0];for<i=1;i<8;++i>{bits<<=1;bits|=chars[i];}returnbits;}intwrite_compress_file<FILE*in,FILE*out,htnpht,hufcodehc[],char*source_file,longsource_filesize>{unsignedinti,read_counter,write_counter,zip_head=0xFFFFFFFF;unsignedcharwrite_char_counter,code_char_counter,copy_char_counter,read_buf[256],write_buf[256],write_chars[8],file_size=strlen<source_file>;hufcode*cur_hufcode;fseek<in,0L,SEEK_SET>;fseek<out,0L,SEEK_SET>;fwrite<&zip_head,sizeof<unsignedint>,1,out>;fwrite<&file_size,sizeof<unsignedchar>,1,out>;fwrite<source_file,sizeof<char>,file_size,out>;fwrite<&source_filesize,sizeof<long>,1,out>;for<i=256;i<256*2-1;i++>{fwrite<&<ht[i].l>,sizeof<ht[i].l>,1,out>;fwrite<&<ht[i].r>,sizeof<ht[i].r>,1,out>;}write_counter=write_char_counter=0;read_counter=256;while<read_counter==256>{read_counter=fread<read_buf,1,256,in>;for<i=0;i<read_counter;i++>{cur_hufcode=&hc[read_buf[i]];code_char_counter=0;while<code_char_counter!=cur_hufcode->len>{copy_char_counter=<8-write_char_counter>cur_hufcode->len-code_char_counter?cur_hufcode->len-code_char_counter:8-write_char_counter>;memcpy<write_chars+write_char_counter,cur_hufcode->codestr+code_char_counter,copy_char_counter>;write_char_counter+=copy_char_counter;code_char_counter+=copy_char_counter;if<write_char_counter==8>{write_char_counter=0;write_buf[write_counter++]=chars_to_bits<write_chars>;if<write_counter==256>{fwrite<write_buf,1,256,out>;write_counter=0;}}}}}fwrite<write_buf,1,write_counter,out>;if<write_char_counter!=0>{write_char_counter=chars_to_bits<write_chars>;fwrite<&write_char_counter,1,1,out>;}return0;}//建立哈弗曼樹中用于選擇最小權(quán)值結(jié)點(diǎn)的函數(shù)voidget_mini_huffmantree<FILE*in,shortmini_ht[][2]>{inti;for<i=0;i<256;i++>{mini_ht[i][0]=mini_ht[i][1]=-1;}fread<mini_ht[i],sizeof<short>,2*<256-1>,in>;}intwrite_decompress_file<FILE*in,FILE*out,shortmini_ht[][2],longbits_pos,longobj_filesize>{longcur_size;unsignedcharread_buf[256],write_buf[256],convert_bit;unsignedintread_counter,write_counter,cur_pos;fseek<in,bits_pos,SEEK_SET>;fseek<out,0L,SEEK_SET>;read_counter=256-1;cur_size=write_counter=0;cur_pos=256*2-2;while<cur_size!=obj_filesize>{if<++read_counter==256>{fread<read_buf,1,256,in>;read_counter=0;}for<convert_bit=128;convert_bit!=0;convert_bit>>=1>{cur_pos=<<read_buf[read_counter]&convert_bit>==0?mini_ht[cur_pos][0]:mini_ht[cur_pos][1]>;if<cur_pos<256>{write_buf[write_counter]=<unsignedchar>cur_pos;if<++write_counter==256>{fwrite<write_buf,1,256,out>;write_counter=0;}cur_pos=256*2-2;if<++cur_size==obj_filesize>{break;}}}}fwri