c++哈夫曼樹的文件壓縮解壓程序全部代碼及設(shè)計(jì)報(bào)告

#include<iostream>#include<fstream>#include<queue>//隊(duì)列容器usingnamespacestd;constintleaf=256;//最多可能出現(xiàn)的不同字符數(shù)constlongMAX=99999999;typedefstructHTnode{longweight;intparent;intlchild;intrchild;int*code;intcodelen;//表示無窮大//記錄結(jié)點(diǎn)的權(quán)值//記錄結(jié)點(diǎn)的雙親結(jié)點(diǎn)位置//結(jié)點(diǎn)的左孩子//結(jié)點(diǎn)的右孩子該結(jié)點(diǎn)的huffman編碼//記錄該結(jié)點(diǎn)huffman編碼的長度HTnode{weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;}}HTnode;classhuffmanTree{chuffmanTree();virtual~huffmanTree();boolcount(char*input);//統(tǒng)計(jì)各字符出現(xiàn)的次數(shù)，將其寫入對應(yīng)結(jié)點(diǎn)的權(quán)值voidcreate();voidcode();voidaddbit(intbit);voidresetbyte();n/計(jì)算每個(gè)字符的huffman編碼boolcompress(char*input,char*output);敗falsebooldecompress(char*input,char*output);失敗falsevoidcompare(char*input,char*output);//壓縮函數(shù)成功執(zhí)行返回true失//解壓函數(shù)成功執(zhí)行返回true//將原文件與壓縮后的文件比較vateintroot;intleafnum;//記錄根結(jié)點(diǎn)的位置//記錄不同字符的個(gè)數(shù)HTnodeHT[leaf*2-1];charbyte;intbitsnum;intlacknum;//HTnode結(jié)構(gòu)的數(shù)組，用來表示huffman樹，樹的最大結(jié)//壓縮文件時(shí)用來緩沖bit的變量ebithuffmanTree::huffmanTree(){//初始化成員變量root=0;leafnum=0;byte=0;bitsnum=0;lacknum=0;}huffmanTree::~huffmanTree(){for(inti=0;i<leaf;i++){if(HT[i].codelen!=0)delete[]HT[i].code;}}//統(tǒng)計(jì)各字符出現(xiàn)的次數(shù)boolhuffmanTree::count(char*input){ifstreamifs;charc;ifs.open(input,ios::binary);ififs{cout<<"無法打開文件"<<input<<'!'<<endl;returnfalse;}while(ifs.get(c)){if(HT[c+128].weight==MAX){HT[c+128].weight=0;//若該字符是第一次出現(xiàn)，先初始化權(quán)值leafnum++;}HT[c+128].weight++;}ifs.close();//權(quán)值+1returntrue;}//選權(quán)值最小的兩棵樹組成新的數(shù)voidhuffmanTree::create(){for(inti=leaf;i<2*leaf-1;i++){intloc1=-1,loc2=-1;for(intj=0;j<i;j++){if(HT[j].parent!=-1)continue;if(loc1==-1||HT[j].weight<HT[loc1].weight){loc2=loc1;locj;}elseif(loc2==-1||HT[j].weight<HT[loc2].weight)locj;}if(HT[loc1].weight==MAX||HT[loc2].weight==MAX||loc2==-1)//只剩一棵樹，結(jié)束HT[i].weight=HT[loc1].weight+HT[loc2].weight;結(jié)點(diǎn)的左孩子HT[i].lchild=loc1>loc2?loc2:loc1;HT[i].rchild=loc1>loc2?loc1:loc2;HT[loc1].parent=i;HT[loc2].parent=i;root=i;}}//計(jì)算每個(gè)字符的huffman編碼voidhuffmanTree::code(){for(inti=0;i<leaf;i++){intlen=0;intloc=i;while(HT[loc].parent!=-1){//計(jì)算huffman編碼長度loc=HT[loc].parent;}HT[i].codelen=len;HT[i].code=newint[len];loc=i;for(intj=len-1;j>=0;j--){//從后往前找，記錄結(jié)點(diǎn)的huffman編碼if(loc==HT[HT[loc].parent].lchild)HT[i].code[j]=0;eHT[i].code[j]=1;loc=HT[loc].parent;}}}voidhuffmanTree::addbit(intbit){if(bit==0)byteebyte=((byte<<1)|1);或運(yùn)算bitsnum++;}voidhuffmanTree::resetbyte(){byte=0;bitsnum=0;}//壓縮函數(shù)成功執(zhí)行返回true失敗falseboolhuffmanTree::compress(char*input,char*output){if(!count(input))returnfalse;create();code();ifstreamifs;ofstreamofs;ifs.open(input,ios::binary);ofs.open(output,ios::binary);charc;ifs{cout<<"無法打開文件"<<input<<'!'<<endl;returnfalse;}ifofs{cout<<"無法打開文件"<<output<<'!'<<endl;returnfalse;}ofs.put(0);//預(yù)留一個(gè)字符，等壓縮完后在該位置寫入不足一個(gè)byte的bit個(gè)數(shù)ofs.put(root-384);//將根節(jié)點(diǎn)的位置-384寫入(為使該值不超過char的最大表示范圍)for(inti=0;i<leaf*2-1;i++){//寫入每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)位置ofs.put(127);else//否則將雙親結(jié)點(diǎn)的位置-384再寫入(為使該值不超過char的最大表示范圍)ofs.put(HT[i].parent-384);}while(ifs.get(c)){nbyteinttmp=c+128;for(inti=0;i<HT[tmp].codelen;i++){addbit(HT[tmp].code[i]);if(bitsnum==8)yteofs.put(byte);resetbyte();}}}ifbitsnum8個(gè)字符的byte，用0填充并記錄填充的個(gè)數(shù)for(inti=bitsnum;i<8;i++){addbit(0);lacknum++;}ofs.put(byte);resetbyte();}ofs.seekp(0,ios::beg);ofs.put(lacknum);ifs.close();ofs.close();returntrue;}//將寫指針移動(dòng)到文件開頭//寫入最后一個(gè)字節(jié)缺失的bit個(gè)數(shù)//解壓函數(shù)成功執(zhí)行返回true失敗falseboolhuffmanTree::decompress(char*input,char*output){queue<char>q;charc;ifstreamifs;ofstreamofs;ifs.open(input,ios::binary);ofs.open(output,ios::binary);ifs{cout<<"無法打開文件"<<input<<'!'<<endl;returntrue;}ifofs{cout<<"無法打開文件"<<output<<'!'<<endl;returnfalse;}ifs.get(c);lacknum=c;//讀出最后一個(gè)字節(jié)缺失的bit個(gè)數(shù)ifs.get(c);root=c+384;//讀出根結(jié)點(diǎn)的位置for(inti=0;i<leaf*2-1;i++){//建立各結(jié)點(diǎn)之間的雙親孩子關(guān)系ifs.get(c);if(c==127)continue;e{HT[i].parent=c+384;if(HT[c+384].lchild==-1)HT[c+384].lchild=i;eHT[c+384].rchild=i;}}intpoint=root;//為了方便處理最后一個(gè)可能有缺失bit的字節(jié)，先將讀出的數(shù)據(jù)放入隊(duì)列while(ifs.get(c))q.push(c);//還原文件過程while(q.size()>1){//還未到最后一個(gè)字節(jié)c=q.front();for(inti=0;i<8;i++){if(int(c&128)==0){point=HT[point].lchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}e{point=HT[point].rchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}}q.pop();}c=q.front();//最后一個(gè)字節(jié)for(i=0;i<8-lacknum;i++){if(int(c&128)==0){point=HT[point].lchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}lsepoint=HT[point].rchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}}q.pop();ifs.close();ofs.close();returntrue;}//將原文件與壓縮后的文件比較voidhuffmanTree::compare(char*input,char*output){ifstreamorigin,compress;origin.open(input,ios::binary);compress.open(output,ios::binary);if(!origin){cout<<"無法打開文件"<<input<<'!'<<endl;n}if(!compress){cout<<"無法打開文件"<<output<<'!'<<endl;n}doubletotal1=0,total2=0;charc;while(origin.get(c))total1++;while(compress.get(c))total2++;ByteendlByteendlorigin.close();compress.close();}voidmain(){intchoice=1;charinput[255],output[255];huffmanTreeh;while(choice){cout<<"****************************************************"<<endl;cout<<"*基于哈夫曼樹的文件壓縮/解壓程序*"<<endl;cout<<"**"<<endl;cout<<"cout<<"**1)壓縮*"<<endl;*"<<endl;cout<<"cout<<"**2)解壓*"<<endl;*"<<endl;cout<<"cout<<"**0)退出*"<<endl;*"<<endl;cout<<"*說明：請輸入相應(yīng)的操作序號(hào)*"<<endl;cout<<"****************************************************"<<endl;cout<<"請選擇:";cin>>choice;switch(choice){case1:{cin>>input;cin>>output;if(press(input,output)){pare(input,output);cout<<"文件壓縮成功!"<<endl;{cout<<"文件壓縮失敗!"<<endl;}}case2:{cin>>input;cin>>output;if(h.decompress(input,output))cout<<"文件解壓成功!"<<endl;ecout<<"文件解壓失敗!"<<endl;}case0:default:cout<<"參數(shù)錯(cuò)誤！請重新輸入"<<endl;}cout<<endl;}}設(shè)計(jì)題目：基于哈夫曼樹的文件壓縮/解壓程序術(shù)班級(jí)：11級(jí)(1)班指導(dǎo)教師姓名及職稱：陳正銘講師月展，多媒體計(jì)算機(jī)技術(shù)、計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)以及現(xiàn)息化、高速化、智能化迅速發(fā)展。各個(gè)領(lǐng)域的應(yīng)用與越大，給數(shù)據(jù)的存儲(chǔ)、傳輸以及有效、快速獲取信息網(wǎng)和云計(jì)算都是對海量的數(shù)據(jù)進(jìn)行處理和傳輸傳輸所需的帶寬要求就很高，物理成本上也信中占有很重要的位置，且涉及領(lǐng)域多，應(yīng)名稱(可帶路徑)。tD\1\YYY.txt名稱(可帶路徑)。t=D:\XXX.txt樹n碼碼如何使用軟件，根據(jù)菜單提示選因?yàn)楦鱾€(gè)環(huán)節(jié)之間有先后順序。第一步為輸入壓縮軟徑和文件名稱，讀入字符數(shù)組中，打開該文件，按照個(gè)字符出現(xiàn)的次數(shù)，申請一個(gè)結(jié)構(gòu)體數(shù)n的權(quán)值，依次進(jìn)行下去，直到所有的字符結(jié)點(diǎn)始，每讀一個(gè)字符，指針變化一次(當(dāng)讀取的字符是‘1’時(shí)，指針指向當(dāng)前所指結(jié)針?biāo)附Y(jié)點(diǎn)為葉子結(jié)點(diǎn)時(shí)結(jié)束(即當(dāng)結(jié)點(diǎn)的左右孩子均為空時(shí))。將當(dāng)前葉子結(jié)點(diǎn)所//huffman樹的結(jié)點(diǎn)結(jié)構(gòu)體{的權(quán)值的雙親結(jié)點(diǎn)位置孩子intcodelen;//記錄該結(jié)點(diǎn)huffman編碼的長度de{weight=MAX;parent=-1;rchild=-1;}{TreehuffmanTreeutvoidcreate();//壓縮時(shí)根據(jù)各結(jié)點(diǎn)的權(quán)值構(gòu)造huffman樹voidcode();//壓縮時(shí)利用huffman樹計(jì)算每個(gè)字符的huffman編碼voidaddbit(intbit);//壓縮時(shí)對一個(gè)未滿8個(gè)bit的byte中加入一個(gè)bitelsecompresscharinputcharoutputtrue失敗falsevoidcomparecharinput,char*output);//將原文件與壓縮后的文introot;//記錄根結(jié)點(diǎn)的位置intbitsnum/byte中bit的個(gè)數(shù)intlacknum;//壓縮到最后byte中的bit不滿8個(gè)時(shí)填充的0的個(gè)數(shù)routputooldecompresscharinputcharoutput為了詳細(xì)說明這個(gè)問題，特以下面例子來說明:[4]AABCD0000010000010110010001010110010100011110把兩個(gè)出現(xiàn)次數(shù)最小的字符圈到一起，看作一個(gè)新字對所有字符的處理。這種操作形成的結(jié)構(gòu)看起來像棵樹(下圖)，被稱為——霍夫曼(Huffman)樹。支編號(hào)連到它那里，無重復(fù)也無遺漏，這AABCD0011000100111110主程序模塊:壓縮函數(shù)ffman主函數(shù)菜單對比函數(shù)對比函數(shù)程序模塊碼YES編碼流程ffman根據(jù)哈夫曼編碼的長短,對通過哈夫曼編碼的長短,依解碼,從原來的位存儲(chǔ)還置補(bǔ)0解碼流程4.調(diào)試分析報(bào)告經(jīng)百度后發(fā)現(xiàn)：壓縮率(Compressionratio)，描述壓縮文件的效果名，是文0m的文件壓縮后是90m，壓縮圖7壓縮率測試結(jié)果圖8改正后的測試結(jié)果5.用戶使用說明2.txt)，圖10執(zhí)行壓縮操作圖圖11執(zhí)行壓縮操作圖壓縮的文件進(jìn)行恢復(fù)，根據(jù)提示輸入待恢復(fù)的圖15解壓后的文件333.txt詳細(xì)測試結(jié)果請參見5使用功能。txt件(7kb)pdf文件Mp3文件24圖16打開解壓后pdf文件的提示jpgmp同樣遇到無法打開的提示。[1]嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京:人民郵電出版社，2011.[3]潘瑋華.用Huffman編碼進(jìn)行文件壓縮的方法[J].電腦知識(shí)與技術(shù),2010年07期.[4]kaikai.數(shù)據(jù)是怎么被壓縮的[OL]./article/46865/,2011.[5]百度百科.[OL]./view/354638.htm.#include<iostream>#include<fstream>#include<queue>//隊(duì)列容器usingnamespacestd;constintleaf=256;constlongMAX=99999999;typedefstructHTnode{longweight;intparent;intlchild;intrchild;int*code;intcodelen;//最多可能出現(xiàn)的不同字符數(shù)//表示無窮大//記錄結(jié)點(diǎn)的權(quán)值//記錄結(jié)點(diǎn)的雙親結(jié)點(diǎn)位置//結(jié)點(diǎn)的左孩子//結(jié)點(diǎn)的右孩子//記錄該結(jié)點(diǎn)的huffman編碼//記錄該結(jié)點(diǎn)huffman編碼的長度HTnode(){weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;}}HTnode;classhuffmanTree{public:huffmanTree();virtual~huffmanTree();boolcount(char*input);voidcreate();voidcode();voidaddbit(intbit);//統(tǒng)計(jì)各字符出現(xiàn)的次數(shù)，將其寫入對應(yīng)結(jié)點(diǎn)的權(quán)值//構(gòu)造huffman樹//計(jì)算每個(gè)字符的huffman編碼//壓縮時(shí)對一個(gè)未滿8個(gè)bit的byte中加入一個(gè)bitvoidresetbyte();//將byte清空boolcompress(char*input,char*output);回true失敗falsebooldecompress(char*input,char*output);回true失敗falsevoidcompare(char*input,char*output);//壓縮函數(shù)成功執(zhí)行返//解壓函數(shù)成功執(zhí)行返//將原文件與壓縮后的文件比較private:ntrootintleafnum;HTnodeHT[leaf*2-1];結(jié)點(diǎn)個(gè)數(shù)不會(huì)超過leaf*2-1charbyte;intbitsnum;intlacknum;//記錄根結(jié)點(diǎn)的位置//記錄不同字符的個(gè)數(shù)//壓縮文件時(shí)用來緩沖bit的變量//byte中bit的個(gè)數(shù)//壓縮到最后byte中的bit不滿8個(gè)時(shí)填充的0的個(gè)數(shù)huffmanTree::huffmanTree(){//初始化成員變量root=0;leafnum=0;byte=0;bitsnum=0;lacknum=0;}huffmanTree::~huffmanTree(){for(inti=0;i<leaf;i++){if(HT[i].codelen!=0)delete[]HT[i].code;}}//統(tǒng)計(jì)各字符出現(xiàn)的次數(shù)boolhuffmanTree::count(char*input){ifstreamifs;charc;ififs{cout<<"無法打開文件"<<input<<'!'<<endl;returnfalse;}while(ifs.get(c)){if(HT[c+128].weight==MAX){HT[c+128].weight=0;//若該字符是第一次出現(xiàn)，先初始化權(quán)值leafnum++;}HT[c+128].weight++;}//權(quán)值+1ifs.close();returntrue;}//選權(quán)值最小的兩棵樹組成新的數(shù)voidhuffmanTree::create(){for(inti=leaf;i<2*leaf-1;i++){intloc1=-1,loc2=-1;for(intj=0;j<i;j++){if(HT[j].parent!=-1)continue;if(loc1==-1||HT[j].weight<HT[loc1].weight){loc2=loc1;loc1=j;}elseif(loc2==-1||HT[j].weight<HT[loc2].weight)loc2=j;}//只剩if(HT[loc1].weight==MAX||HT[loc2].weight==MAX||loc2==-1)//只剩一棵樹，結(jié)束break;HT[i].weight=HT[loc1].weight+HT[loc2].weight;//為了減少壓縮文件中需要寫入的huffman樹的信息，約定小標(biāo)小的結(jié)點(diǎn)做為雙親結(jié)點(diǎn)的左孩子HT[i].lchild=loc1>loc2?loc2:loc1;HT[i].rchild=loc1>loc2?loc1:loc2;HT[loc1].parent=i;HT[loc2].parent=i;root=i;}}//計(jì)算每個(gè)字符的huffman編碼voidhuffmanTree::code(){for(inti=0;i<leaf;i++){intlen=0;intloc=i;while(HT[loc].parent!=-1){//計(jì)算huffman編碼長度loc=HT[loc].parent;}HT[i].codelen=len;HT[i].code=newint[len];loc=i;for(intj=len-1;j>=0;j--){//從后往前找，記錄結(jié)點(diǎn)的huffman編碼if(loc==HT[HT[loc].parent].lchild)HT[i].code[j]=0;HT[i].code[j]=1;loc=HT[loc].parent;}}}//壓縮時(shí)對一個(gè)未滿8個(gè)bit的byte中加入一個(gè)bitvoidhuffmanTree::addbit(intbit){if(bit==0)byte=byte<<1;//若新增的bit為0，則直接將byte按位左移byte=((byte<<1)|1);//若新增的bit為1，先將byte按位左移，再與1按位或運(yùn)算bitsnum++;}//將byte清空voidhuffmanTree::resetbyte(){byte=0;bitsnum=0;}//壓縮函數(shù)成功執(zhí)行返回true失敗falseboolhuffmanTree::compress(char*input,char*output){if(!count(input))returnfalse;create();code();ifstreamifs;ofstreamofs;charc;fs{cout<<"無法打開文件"<<input<<'!'<<endl;returnfalse;}fs{cout<<"無法打開文件"<<output<<'!'<<endl;returnfalse;}ofs.put(0);//預(yù)留一個(gè)字符，等壓縮完后在該位置寫入不足一個(gè)byte的bit個(gè)數(shù)ofs.put(root-384);//將根節(jié)點(diǎn)的位置-384寫入(為使該值不超過char的最大表示for(inti=0;i<leaf*2-1;i++){//寫入每個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)位置if(HT[i].parent==-1)//若該節(jié)點(diǎn)沒有雙親結(jié)點(diǎn)，則寫入127(一個(gè)字節(jié)所能表示的最大值)ofs.put(127);else//否則將雙親結(jié)點(diǎn)的位置-384再寫入(為使該值不超過char的最大表示ofs.put(HT[i].parent-384);}while(ifs.get(c)){//將字符的huffman編碼并加入byte中inttmp=c+128;for(inti=0;i<HT[tmp].codelen;i++){addbit(HT[tmp].code[i]);if(bitsnum==8){//若byte已滿8位，則輸出該byte并將byte清空ofs.put(byte);resetbyte();}}}if(bitsnum!=0){//處理最后未滿8個(gè)字符的byte，用0填充并記錄填充的個(gè)數(shù)for(inti=bitsnum;i<8;i++){addbit(0);lacknum++;}ofs.put(byte);resetbyte();}ofs.seekp(0,ios::beg);ofs.put(lacknum);ifs.close();ofs.close();returntrue;}//將寫指針移動(dòng)到文件開頭//寫入最后一個(gè)字節(jié)缺失的bit個(gè)數(shù)//解壓函數(shù)成功執(zhí)行返回true失敗falseboolhuffmanTree::decompress(char*input,char*output){queue<char>q;charc;ifstreamifs;ofstreamofs;fs{cout<<"無法打開文件"<<input<<'!'<<endl;returntrue;}fs{cout<<"無法打開文件"<<output<<'!'<<endl;returnfalse;}ifs.get(c);lacknum=c;ifs.get(c);root=c+384;//讀出最后一個(gè)字節(jié)缺失的bit個(gè)數(shù)//讀出根結(jié)點(diǎn)的位置for(inti=0;i<leaf*2-1;i++){//建立各結(jié)點(diǎn)之間的雙親孩子關(guān)系ifs.get(c);if(c==127)continue;{HT[i].parent=c+384;if(HT[c+384].lchild==-1)HT[c+384].lchild=i;HT[c+384].rchild=i;}}intpoint=root;//為了方便處理最后一個(gè)可能有缺失bit的字節(jié)，先將讀出的數(shù)據(jù)放入隊(duì)列while(ifs.get(c))q.push(c);//還原文件過程while(q.size()>1){//還未到最后一個(gè)字節(jié)c=q.front();for(inti=0;i<8;i++){if(int(c&128)==0){point=HT[point].lchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}{point=HT[point].rchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}}q.pop();}c=q.front();for(i=0;i<8-lacknum;i++){if(int(c&128)==0)//最后一個(gè)字節(jié){point=HT[point].lchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}sepoint=HT[point].rchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));poin