【數(shù)據(jù)結(jié)構(gòu)】哈夫曼壓縮軟件設(shè)計(jì)-實(shí)驗(yàn)報(bào)告

-38-東北大學(xué)信息科學(xué)與工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目哈夫曼壓縮軟件設(shè)計(jì)課題組長王健課題組成員張穎劉琪張曉雨專業(yè)名稱計(jì)算機(jī)科學(xué)與技術(shù)班級計(jì)1307指導(dǎo)教師楊雷 2015年1月課程設(shè)計(jì)任務(wù)書題目：哈夫曼壓縮軟件設(shè)計(jì)問題描述：采用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。利用哈夫曼編碼的數(shù)據(jù)壓縮技術(shù)，設(shè)計(jì)文本格式的壓縮軟件或位圖格式的壓縮軟件。設(shè)計(jì)要求：設(shè)計(jì)基于哈夫曼編碼的壓縮軟件。（1）采用靜態(tài)鏈表的二叉樹等數(shù)據(jù)結(jié)構(gòu)的類實(shí)現(xiàn)。（2）創(chuàng)建哈夫曼樹。（3）哈夫曼編碼和譯碼。（4）源碼、編碼和壓縮后的信息均以文件形式保存。（5）軟件時(shí)間和空間性能分析。（6）基于哈夫曼編碼的位圖壓縮軟件設(shè)計(jì)（可選）。指導(dǎo)教師簽字：年月日目錄1課題概述 41.1課題任務(wù) 41.2課題原理 41.3相關(guān)知識 42需求分析 52.1課題調(diào)研 52.2用戶需求分析 53方案設(shè)計(jì) 53.1總體功能設(shè)計(jì) 53.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 63.3函數(shù)原型設(shè)計(jì) 63.4主算法設(shè)計(jì) 73.5用戶界面設(shè)計(jì) 94方案實(shí)現(xiàn) 124.1開發(fā)環(huán)境與工具 124.2程序設(shè)計(jì)關(guān)鍵技術(shù) 124.3個(gè)人設(shè)計(jì)實(shí)現(xiàn)（按組員分工）4.3.1王健設(shè)計(jì)實(shí)現(xiàn) 124.3.2張穎設(shè)計(jì)實(shí)現(xiàn) 174.3.3劉琪設(shè)計(jì)實(shí)現(xiàn) 204.3.4張曉雨設(shè)計(jì)實(shí)現(xiàn) 225測試與調(diào)試 255.1個(gè)人測試（按組員分工） 255.1.1王健測試 255.1.2張穎測試 265.1.3劉琪測試 275.1.4張曉雨測試 315.2組裝與系統(tǒng)測試 325.3系統(tǒng)運(yùn)行 326課題總結(jié) 336.1課題評價(jià) 336.2團(tuán)隊(duì)協(xié)作 336.3下一步工作 336.4個(gè)人設(shè)計(jì)小結(jié)（按組員分工） 336.4.1王健設(shè)計(jì)小結(jié) 336.4.2張穎設(shè)計(jì)小結(jié) 346.4.3劉琪設(shè)計(jì)小結(jié) 346.4.4張曉雨設(shè)計(jì)小結(jié) 347附錄A課題任務(wù)分工 35A-1課題程序設(shè)計(jì)分工 35A-2課題報(bào)告分工 36附錄B課題設(shè)計(jì)文檔（光盤） 37B-1源程序代碼（*.H，*.CPP） 37B-2工程與可執(zhí)行文件） 37附錄C用戶操作手冊（可選） 37C.1運(yùn)行環(huán)境說明 37C.2操作說明 37

1課題概述1.1課題任務(wù) 采用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。利用哈夫曼編碼對文本或圖像進(jìn)行數(shù)據(jù)壓縮，設(shè)計(jì)數(shù)據(jù)壓縮軟件。【設(shè)計(jì)要求】設(shè)計(jì)基于哈夫曼編碼的壓縮軟件。（1）采用靜態(tài)鏈表的二叉樹等數(shù)據(jù)結(jié)構(gòu)。（2）創(chuàng)建哈夫曼樹。（3）哈夫曼編碼和譯碼。（4）源碼、編碼和壓縮后的信息均以文件形式保存。（5）其它完善性功能。1.2課題原理 1.2.1哈夫曼樹：哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉子結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度為葉結(jié)點(diǎn)的層數(shù)）。樹的帶權(quán)路徑長度記為WPL=W1*L1+W2*L2+ 1.2.2壓縮軟件：壓縮軟件是利用算法將文件有損或無損地處理，以達(dá)到保留最多文件信息，而令文件體積變小的應(yīng)用軟件。壓縮軟件一般同時(shí)具有解壓縮的功能。壓縮軟件的的基本原理是查找文件內(nèi)的重復(fù)字節(jié),并建立一個(gè)相同字節(jié)的"詞典"文件,并用一個(gè)代碼表示,比如在文件里有幾處有一個(gè)相同的詞"中華人民共和國"用一個(gè)代碼表示并寫入"詞典"文件,這樣就可以達(dá)到縮小文件的目的。常見的壓縮軟件有WinRAR,好壓(Haozip),WinZip,7-Zip,WinMount,Peazip等等。 1.2.3哈夫曼壓縮：哈夫曼壓縮是個(gè)無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個(gè)體符號（例如，文本文件中的字符）用一個(gè)特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。1.3相關(guān)知識 1.3.1二進(jìn)制文件的創(chuàng)建、讀取、寫入操作 1.3.2數(shù)學(xué)統(tǒng)計(jì) 1.3.3哈夫曼樹算法 1.3.4獲取哈夫曼編碼 1.3.5壓縮文件相關(guān)信息 1.3.6C/C++語言的熟悉掌握，一定程度上掌握MFC2需求分析2.1課題調(diào)研 隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們對文件信息的需求量逐漸增大，不光對文件個(gè)數(shù)的使用量增加，單個(gè)文件的內(nèi)存也增大到幾個(gè)G，這種現(xiàn)象的產(chǎn)生，將導(dǎo)致計(jì)算機(jī)上內(nèi)存的消耗過大，以及計(jì)算機(jī)對文件的操作變得十分困難。2.2用戶需求分析 經(jīng)過調(diào)研，目前用戶比較傾向的壓縮工具的特點(diǎn)有：使用方便、用戶友好，在壓縮率以及壓縮速度方面表現(xiàn)出色。 在這個(gè)背景下，我們小組決定運(yùn)用哈夫曼算法，設(shè)計(jì)一款符合大眾要求的小壓縮工具。3方案設(shè)計(jì)3.1總體功能設(shè)計(jì)開始開始菜單解壓壓縮結(jié)束

3.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)//壓縮函數(shù)使用數(shù)據(jù)結(jié)構(gòu)typedefstructHTNode{unsignedcharb;/*thecharactor*/longparent,lchild,rchild;/*makeatree*/charbits[256];/*thehaffumancode*/longcount;/*thefrequency*/}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲哈夫曼樹t//解壓函數(shù)使用數(shù)據(jù)結(jié)構(gòu)structhead{unsignedcharb;/*thecharactor*/longcount;/*thefrequency*/longparent,lch,rch;/*makeatree*/charbits[256];/*thehaffumancode*/}header[512],tmp;3.3函數(shù)原型設(shè)計(jì)voidSelect(HuffmanTreeHT,intx,int&s1,int&s2);//HT[]數(shù)組1…x中選出能夠建樹結(jié)點(diǎn)中權(quán)值最小兩個(gè)voidCompress(char*filename,char*outputfile);//壓縮函數(shù)voidDeCompress(char*filename,char*outputfile);//解壓函數(shù)

3.4主算法設(shè)計(jì)壓縮算法實(shí)現(xiàn)壓縮壓縮開始統(tǒng)計(jì)文件字符/統(tǒng)計(jì)字符總數(shù)構(gòu)建哈夫曼樹生成哈夫曼編碼判斷字符讀取是否結(jié)束打開文件/創(chuàng)建壓縮文件尋找該字符對應(yīng)哈夫曼編碼寫入壓縮文件滿八位寫入一次否

是將總字符數(shù)寫入壓縮文件將哈夫曼樹信息寫入壓縮文件壓縮結(jié)束解壓算法實(shí)現(xiàn)解壓解壓開始打開壓縮文件/創(chuàng)建解壓文件讀取總字符數(shù)flength/讀取哈夫曼信息讀取壓縮文件主信息，讀取次數(shù)是否小于flength每次讀八位，寫入字符串中根據(jù)讀取的哈夫曼編碼，找到對應(yīng)的ASCII將字符寫入解壓文件關(guān)閉文件解壓結(jié)束否是

3.5用戶界面設(shè)計(jì)3.5.1主界面3.5.2菜單界面3.5.3壓縮界面3.5.4解壓界面

3.5.5查找文件和尋找壓縮路徑界面

4方案實(shí)現(xiàn)4.1開發(fā)環(huán)境與工具 硬件：個(gè)人PC 軟件：VS2013 開發(fā)環(huán)境：C++4.2程序設(shè)計(jì)關(guān)鍵技術(shù) 二進(jìn)制文件的讀取、寫入； 哈夫曼算法； MFC實(shí)現(xiàn)圖形界面。4.3個(gè)人設(shè)計(jì)實(shí)現(xiàn)（按組員分工）4.3.1王健設(shè)計(jì)實(shí)現(xiàn)實(shí)現(xiàn)部分——壓縮voidCompress(char*filename,char*outputfile){/*前面省略其他人的部分*/fseek(ifp,0,SEEK_SET);fwrite(&flength,sizeof(long),1,ofp);//壓縮文件前四個(gè)字節(jié)用于//存放原文件字節(jié)數(shù)//fwrite(constvoid*buffer,size_tsize,size_tcount,FILE*stream); /*fwrite這個(gè)函數(shù)以二進(jìn)制形式對文件進(jìn)行操作，不局限于文本文件 （1）buffer：是一個(gè)指針，對fwrite來說，是要獲取數(shù)據(jù)的地址；（2）size：要寫入內(nèi)容的單字節(jié)數(shù)； （3）count:要進(jìn)行寫入size字節(jié)的數(shù)據(jù)項(xiàng)的個(gè)數(shù)； （4）stream:目標(biāo)文件指針; （5）返回實(shí)際寫入的數(shù)據(jù)項(xiàng)個(gè)數(shù)count。 */fseek(ofp,8,SEEK_SET);//ofp從第九個(gè)字節(jié)處開始寫入壓縮編碼buf[0]=0;f=0;pt1=8;//用于記錄寫入壓縮文件的字節(jié)數(shù)while(!feof(ifp)){ch=fgetc(ifp);f++;for(i=0;i<n;i++)if(ch==HT[i].b)break;strcat(buf,HT[i].bits);//字符串連接函數(shù)j=strlen(buf);ch=0;while(j>=8){//每滿八位，存儲至文件for(i=0;i<8;i++){if(buf[i]=='1')ch=(ch<<1)|1;//左移一位，用零補(bǔ)，并加一elsech=ch<<1;//左移一位，用零補(bǔ)}fwrite(&ch,1,1,ofp);pt1++;strcpy(buf,buf+8);//buf前八位被覆蓋j=strlen(buf);}if(f==flength)//所有哈夫曼編碼都被讀完break;}if(j>0){//flength不是八的整數(shù)倍，用0補(bǔ)全strcat(buf,"00000000");for(i=0;i<8;i++){if(buf[i]=='1')ch=(ch<<1)|1;elsech=ch<<1;}fwrite(&ch,1,1,ofp);pt1++;}fseek(ofp,4,SEEK_SET);fwrite(&pt1,sizeof(long),1,ofp);//第二個(gè)四字節(jié)存放哈夫曼樹在//壓縮文件的位置fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp);//pt1個(gè)字節(jié)后存放哈夫曼樹結(jié)點(diǎn)//數(shù)for(i=0;i<n;i++){//將哈夫曼編碼信息存入壓縮文件fwrite(&(HT[i].b),1,1,ofp);//單個(gè)字節(jié)存儲一個(gè)葉子結(jié)點(diǎn)ch=strlen(HT[i].bits);fwrite(&ch,1,1,ofp);//接著存儲其哈夫曼編碼數(shù)j=strlen(HT[i].bits);if(j%8!=0){//每個(gè)葉子結(jié)點(diǎn)哈夫曼編碼不足八位，左移，并補(bǔ)零for(f=j%8;f<8;f++)strcat(HT[i].bits,"0");}while(HT[i].bits[0]!=0){ch=0;for(j=0;j<8;j++){if(HT[i].bits[j]=='1')ch=(ch<<1)|1;elsech=ch<<1;}strcpy(HT[i].bits,HT[i].bits+8);fwrite(&ch,1,1,ofp);//將哈夫曼編碼信息存入壓縮文件?}}fclose(ifp);fclose(ofp);}實(shí)現(xiàn)部分——MFC實(shí)現(xiàn)圖形界面//類ClassCHuffmanDlg:publicCDialog{}//主界面類Classmenu:publicCDialog{}//菜單界面類Classcompress:publicCDialog{}//壓縮界面類ClassDecompress:publicCDialog{}//解壓界面類//主界面類中的函數(shù)成員afx_msgvoidOnBnClickedOk();//鼠標(biāo)按下功能選項(xiàng)按鈕afx_msgvoidOnBnClickedCancel();//鼠標(biāo)按下退出//菜單界面類中的函數(shù)成員afx_msgvoidOnOk2();//鼠標(biāo)按下解壓按鈕afx_msgvoidOnBnClickedOk();//鼠標(biāo)按下壓縮按鈕afx_msgvoidOnBnClickedButton1();//鼠標(biāo)按下取消按鈕//壓縮界面類中的函數(shù)成員afx_msgvoidOnButton1();//鼠標(biāo)按下查找1按鈕（彈出文件查找界面）afx_msgvoidOnBnClickedButton2();//鼠標(biāo)按下查找2按鈕（彈出保存文//件路徑界面）afx_msgvoidOnEnChangeEdit3();//壓縮文件命名編輯框afx_msgvoidOnBnClickedButton3();//鼠標(biāo)按下取消按鈕afx_msgvoidOnBnClickedOk();//鼠標(biāo)按下確定按鈕//解壓界面類中的函數(shù)成員afx_msgvoidOnButton1();//鼠標(biāo)按下查找1按鈕（彈出文件查找界面）afx_msgvoidOnBnClickedButton2();//鼠標(biāo)按下取消按鈕afx_msgvoidOnEnChangeEdit2();//鼠標(biāo)按下取消按鈕afx_msgvoidOnBnClickedOk();//鼠標(biāo)按下確定按鈕afx_msgvoidOnBnClickedButton4();//鼠標(biāo)按下查找2按鈕（彈出保存文//件路徑界面）

4.3.2張穎設(shè)計(jì)實(shí)現(xiàn)實(shí)現(xiàn)部分——解壓//解壓功能，此設(shè)有調(diào)試函數(shù)#include<stdio.h>#include<string.h>#include<stdlib.h>#ifndefHEAD2_H#defineHEAD2_Hstructhead{unsignedcharb;/*thecharactor*/longcount;/*thefrequency*/longparent,lch,rch;/*makeatree*/charbits[256];/*thehaffumancode*/}header[512],tmp;voidDeCompress(char*filename,char*outputfile){charbuf[255],bx[255];unsignedcharc;longi,j,m,n,f,p,l;longflength;//flength文件中存儲字節(jié)數(shù)FILE*ifp,*ofp;for(i=0;i<512;++i)header[i].count=0;ifp=fopen(filename,"rb");if(ifp==NULL)exit(0);ofp=fopen(outputfile,"wb");if(ofp==NULL)exit(0);fread(&flength,sizeof(long),1,ifp);//讀取前四個(gè)字節(jié)，//flength為原文件字節(jié)數(shù)fread(&f,sizeof(long),1,ifp);//f為壓縮文件中哈夫曼樹信息前//的字節(jié)數(shù)fseek(ifp,f,SEEK_SET);fread(&n,sizeof(long),1,ifp);//讀取哈夫曼樹葉子結(jié)點(diǎn)數(shù)nfor(i=0;i<n;i++){//重建哈夫曼樹fread(&header[i].b,1,1,ifp);//讀取葉子字符fread(&c,1,1,ifp);//讀取葉子哈夫曼編碼長度p=(long)c;//單個(gè)葉子的哈夫曼編碼長度header[i].count=p;header[i].bits[0]=0;if(p%8>0)m=p/8+1;elsem=p/8;for(j=0;j<m;j++){fread(&c,1,1,ifp);//讀取該葉子結(jié)點(diǎn)哈夫曼編碼f=c;itoa(f,buf,2);//將任意類型的數(shù)字轉(zhuǎn)換為字符串，2進(jìn)制編//碼，存儲在buf中f=strlen(buf);for(l=8;l>f;l--)//不足八位用零補(bǔ)strcat(header[i].bits,"0");strcat(header[i].bits,buf);}header[i].bits[p]=0;}for(i=0;i<n;i++){for(j=i+1;j<n;j++){if(strlen(header[i].bits)>strlen(header[j].bits)){tmp=header[i];header[i]=header[j];header[j]=tmp;}}}p=strlen(header[n-1].bits);//最長葉子結(jié)點(diǎn)編碼長度fseek(ifp,8,SEEK_SET);//ifp開始指向原文件內(nèi)容信息m=0;bx[0]=0;while(1){while(strlen(bx)<(unsignedint)p){fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;l>f;l--)strcat(bx,"0");strcat(bx,buf);}for(i=0;i<n;i++)if(memcmp(header[i].bits,bx,header[i].count)==0)//比較內(nèi)存區(qū)域header[i].bits和bx的前count個(gè)字節(jié)break;strcpy(bx,bx+header[i].count);c=header[i].b;fwrite(&c,1,1,ofp);m++;if(m==flength)break;}fclose(ifp);fclose(ofp);return;}intmain(){charfilename[100],outputfile[100];intc;charb;printf("\nHaffman文件壓縮軟件解壓模塊測試：\n");printf("1解壓\n");printf("2退出\n\n");printf("請輸入序號選擇功能：");scanf("%d%c",&c,&b);if(c==1){printf("請輸入要解壓的文件名：");gets(filename);printf("\n");printf("請輸入解壓后的文件名：");gets(outputfile);DeCompress(filename,outputfile);}elsereturn0;}

4.3.3劉琪設(shè)計(jì)實(shí)現(xiàn)//統(tǒng)計(jì)：讀入源文件，統(tǒng)計(jì)字符出現(xiàn)的次數(shù)（即統(tǒng)計(jì)權(quán)重），順便根據(jù)權(quán)重進(jìn)行從大到小的//排序（主要的話之后的操作會簡單一些）；typedefstructHTNode{unsignedcharb;/*thecharactor*/longparent,lchild,rchild;/*makeatree*/charbits[256];/*thehaffumancode*/longcount;/*thefrequency*/}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲哈夫曼樹typedefchar**HuffmanCode;//動態(tài)分配數(shù)組存儲哈夫曼編碼表//下面具體代碼在head1.h的函數(shù)compress里FILE*ifp,*ofp;HTNodeHT[512];unsignedcharch;//無符號字符型，可以做數(shù)組下表charbuf[512];inti,j,f,n,m,s1,s2;longpt1,flength;//flength原文件字節(jié)個(gè)數(shù)，pt1壓縮文件中哈夫曼//樹信息前字節(jié)個(gè)數(shù)HTNodetmp;for(i=0;i<256;++i)HT[i].count=0;ifp=fopen(filename,"rb");//原文件if(ifp==NULL)exit(0);ofp=fopen(outputfile,"wb");//壓縮文件if(ofp==NULL)exit(0);flength=0;while(!feof(ifp)){fread(&ch,1,1,ifp);HT[ch].count++;flength++;}flength--;//flength表示字節(jié)總數(shù)，feof判斷，結(jié)尾重復(fù)一次，需要減一HT[ch].count--;//最后一個(gè)字節(jié)頻率減一for(i=0;i<512;i++){//二次定義結(jié)點(diǎn)if(HT[i].count!=0)HT[i].b=(unsignedchar)i;elseHT[i].b=0;//NULLHT[i].parent=-1;HT[i].lchild=HT[i].rchild=-1;}for(i=0;i<256;i++){//排序，大在前，小在后for(j=i+1;j<256;j++){if(HT[i].count<HT[j].count){tmp=HT[i];HT[i]=HT[j];HT[j]=tmp;}}}

4.3.4張曉雨設(shè)計(jì)實(shí)現(xiàn)設(shè)計(jì)實(shí)現(xiàn)——哈夫曼樹構(gòu)建、哈夫曼編碼生成//構(gòu)建哈夫曼樹功能，生成哈夫曼編碼，設(shè)有調(diào)試函數(shù)#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstructHTNode{unsignedcharb;/*thecharactor*/longparent,lchild,rchild;/*makeatree*/charbits[256];/*thehaffumancode*/longcount;/*thefrequency*/}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲哈夫曼樹typedefchar**HuffmanCode;//動態(tài)分配數(shù)組存儲哈夫曼編碼表HTNodeHT[512];voidSelect(HuffmanTreeHT,intx,int&s1,int&s2){inti,nu,mu;longmin1;for(i=0,min1=999999999;i<=x;++i){if(HT[i].parent!=-1)continue;if(min1>HT[i].count){min1=HT[i].count;nu=i;}}s1=nu;for(i=0,min1=999999999;i<=x;++i){if(HT[i].parent!=-1||i==nu)continue;if(min1>HT[i].count){min1=HT[i].count;mu=i;}}s2=mu;}voidCompress(constchar*filename,constchar*outputfile){FILE*ifp,*ofp;unsignedcharch;//無符號字符型，可以做數(shù)組下表charbuf[512];inti,j,f,n,m,s1,s2;longpt1,flength;//flength原文件字節(jié)個(gè)數(shù)，pt1壓縮文件中哈夫曼//樹信息前字節(jié)個(gè)數(shù)HTNodetmp;for(i=0;i<256;++i)HT[i].count=0;ifp=fopen(filename,"rb");//原文件if(ifp==NULL)exit(0);ofp=fopen(outputfile,"wb");//壓縮文件if(ofp==NULL)exit(0);flength=0;while(!feof(ifp)){fread(&ch,1,1,ifp);HT[ch].count++;flength++;}flength--;//flength表示字節(jié)總數(shù)，feof判斷，結(jié)尾重復(fù)一次，需要減一HT[ch].count--;//最后一個(gè)字節(jié)頻率減一for(i=0;i<512;i++){//二次定義結(jié)點(diǎn)if(HT[i].count!=0)HT[i].b=(unsignedchar)i;elseHT[i].b=0;//NULLHT[i].parent=-1;HT[i].lchild=HT[i].rchild=-1;}for(i=0;i<256;i++){//排序，大在前，小在后for(j=i+1;j<256;j++){if(HT[i].count<HT[j].count){tmp=HT[i];HT[i]=HT[j];HT[j]=tmp;}}}for(i=0;i<256;i++)//統(tǒng)計(jì)葉子個(gè)數(shù)if(HT[i].count==0)break;n=i;//用n表示葉子數(shù)m=2*n-1;//m為總結(jié)點(diǎn)數(shù)for(i=n;i<m;++i){//葉子結(jié)點(diǎn)生成哈夫曼樹Select(HT,i-1,s1,s2);//在HT[1..i-1]選擇parent為0且//weight最小的兩個(gè)結(jié)點(diǎn)，其序號分別為s1和s2HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].count=HT[s1].count+HT[s2].count;}for(i=0;i<n;i++){//生成哈夫曼編碼f=i;HT[i].bits[0]=0;while(HT[f].parent!=-1){j=f;f=HT[f].parent;if(HT[f].lchild==j){j=strlen(HT[i].bits);memmove(HT[i].bits+1,HT[i].bits,j+1);//memmove用于從HT[i].bits拷貝j+1個(gè)字符到HT[i].bits+1，如果目標(biāo)區(qū)域和//源區(qū)域有重疊的話，//memmove能夠保證源串在被覆蓋之前將重疊區(qū)域的字節(jié)拷貝到目標(biāo)區(qū)域中HT[i].bits[0]='0';}else{j=strlen(HT[i].bits);memmove(HT[i].bits+1,HT[i].bits,j+1);HT[i].bits[0]='1';}}}fclose(ifp);fclose(ofp);}voidPrint(HuffmanTreeHT,intf,intn){//中序遍歷inti;if(HT[f].rchild==-1&&HT[f].lchild==-1){for(i=0;i<n;i++)printf("");if(n>=0){printf("");printf("%d%c%s\n",HT[f].count,HT[f].b,HT[f].bits);}return;//遞歸出口}Print(HT,HT[f].rchild,n+3);//遍歷打印右子樹//訪問根節(jié)點(diǎn)for(i=0;i<n;i++)printf("");if(n>=0){printf("");printf("%d\n",HT[f].count);}Print(HT,HT[f].lchild,n+3);//便利打印左子樹l}voidVeiw_Huff(HuffmanTreeHT){inti;for(i=511;i>=0;i--)if(HT[i].parent!=-1||HT[i].rchild!=-1||HT[i].lchild!=-1)break;printf("哈夫曼樹:\n");Print(HT,i,5);printf("\n\n\n\n\n\n\n\n\n\n\n");printf("按任意鍵返回菜單");getchar();}intmain(){Compress("test.cpp","test1.cpp");Veiw_Huff(HT);return0;}

5測試與調(diào)試5.1個(gè)人測試（按組員分工）5.1.1王健測試1.準(zhǔn)備一個(gè)圖片文件test.jpg2打開應(yīng)用程序，進(jìn)入壓縮功能3.選擇文件和壓縮后的地址4.點(diǎn)擊確定，進(jìn)行壓縮，生成了test.huf壓縮文件5.通過張穎部分的解壓功能檢驗(yàn)，test.huf信息完整5.1.2張穎測試（使用單獨(dú)測試函數(shù)）1.準(zhǔn)備一張圖片，利用已編好的壓縮程序?qū)D片壓縮為后綴為.huf的壓縮文件。2.運(yùn)行解壓測試程序，選擇功能1解壓。3.輸入需要解壓的文件名以及解壓后的文件名4.文件夾中出現(xiàn)解壓后的文件，大小與壓縮前文件大小一致，解壓成功

5.1.3劉琪測試//測試程序#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<string.h>intmain(){structCount{charc;intcount;};intnumbers=0,i;structCountw[256];for(i=0;i<256;i++){w[i].c=i;w[i].count=0;}FILE*fp;fp=fopen("a.txt","r");chartmp;while(!feof(fp)){tmp=getc(fp);w[tmp].count++;}for(i=0;i<256;i++){if(w[i].count>0){numbers+=w[i].count;if(w[i].c==10){printf("\\nnumber=%d\n",w[i].count);}elseif(w[i].c==32){printf("spacenumber=%d\n",w[i].count);}elseif(w[i].c==9){printf("\\tnumber=%d\n",w[i].count);}elseif(w[i].c==0){printf("NULLnumber=%d\n",w[i].count);}elseif(w[i].c==13){printf("carriagereturnnumber=%d\n",w[i].count);}elseprintf("%cnumber=%d\n",w[i].c,w[i].count);}}printf("Filethetotlenumberofcharacters=%d\n",numbers);fclose(fp);return0;}設(shè)置測試程序準(zhǔn)備測試文件a.txt程序運(yùn)行結(jié)果

5.1.4張曉雨測試——測試哈夫曼樹、哈夫曼編碼1.準(zhǔn)備測試文件test.cpp2.運(yùn)行測試程序3.運(yùn)行結(jié)果如下（生成一個(gè)哈夫曼樹，以及打印其字符和哈夫曼編碼）

5.2組裝與系統(tǒng)測試1.C語言代碼組裝在head1.h中聲明、定義Select和Compress；在head2.h中聲明、定義DeCompress；2.將C語言函數(shù)封裝進(jìn)MFC圖形界面實(shí)現(xiàn)中。在MFC工程中調(diào)用Compress和DeCompress函數(shù)，實(shí)現(xiàn)壓縮和解壓功能。5.3系統(tǒng)運(yùn)行1.準(zhǔn)備一個(gè)圖片文件test.jpg2.運(yùn)用壓縮功能，生成test.huf壓縮文件3.運(yùn)用解壓功能，生成test1.jpf解壓文件4.比較二者，原文件和壓縮文件一樣，小組程序?qū)崿F(xiàn)了哈夫曼無算壓縮

6課題總結(jié)6.1課題評價(jià) 小組設(shè)計(jì)哈夫曼軟件小巧，使用方便、用戶友好。經(jīng)過多次驗(yàn)證，我們發(fā)現(xiàn)，在壓縮率方面較之WinRAR等軟件表現(xiàn)更出色，且采取無損壓縮，不會產(chǎn)生信息丟失，但在壓縮解壓速度方面較之其他壓縮軟件稍次，還有待進(jìn)一步提高。6.2團(tuán)隊(duì)協(xié)作 整個(gè)工程分工細(xì)致，任務(wù)明確，在組長的帶領(lǐng)下，小組全體組員出色的完成了自己的任務(wù)。經(jīng)過各個(gè)成員的反復(fù)修改，小組程序的錯誤越來越少，并在驗(yàn)收中一次通過。6.3下一步工作 提供更加友好的用戶界面，讓用戶使用更加便捷。增添更多的壓縮功能，完善它在壓縮功能上的不足，使其能夠成為符合壓縮標(biāo)準(zhǔn)的壓縮軟件。在往后使用的過程中，記錄它出現(xiàn)的debug，使其能夠應(yīng)對突發(fā)情況，進(jìn)而更加完美。6.4個(gè)人工作總結(jié)6.4.1王健設(shè)計(jì)小結(jié)1.軟件開工之前，最好查閱相關(guān)資料，觀摩前任類似軟件代碼。在自己編寫代碼過程中，因?yàn)榍捌谝?guī)劃不夠，導(dǎo)致代碼編寫過程中遇到各種知識欠缺問題，例如：對文件操作了解不夠。2.應(yīng)該做好總體設(shè)計(jì)。作為小組長，雖然討論過整個(gè)過程如何實(shí)現(xiàn)，也做過一定的分析，但是后來發(fā)現(xiàn)，分析并不透徹，缺乏全局思考。最主要的原因在于花在總體設(shè)計(jì)時(shí)間太短。3.設(shè)計(jì)好各個(gè)接口，能夠便于小組組裝以及調(diào)試。由于當(dāng)初規(guī)劃時(shí)間過短，導(dǎo)致接口設(shè)計(jì)不夠完美，在接下來的調(diào)試中花了大量時(shí)間，但是還未解決，最終廢棄了不少代碼。4.在整個(gè)工程中，本小組組員表現(xiàn)團(tuán)結(jié)，各有分工，為工程如期完成奠定了良好的基礎(chǔ)。

6.4.2張穎設(shè)計(jì)小結(jié)通過這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實(shí)踐相結(jié)合起來，從理論中得出結(jié)論，從實(shí)踐中驗(yàn)證理論，從而提高自己的實(shí)際動手能力和獨(dú)立思考的能力。當(dāng)然，在設(shè)計(jì)的過程中遇到許許多多的問題，可以說得是困難重重，畢竟這是一次課程設(shè)計(jì)，需要掌握的知識面比較廣，同時(shí)在設(shè)計(jì)的過程中發(fā)現(xiàn)了自己的不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固，通過這次課程設(shè)計(jì)之后，一定把以前所學(xué)過的知識重新溫故。6.4.3劉琪設(shè)計(jì)小結(jié)這門課結(jié)束之后，我總結(jié)了學(xué)習(xí)中遇到的一些問題，最為突出的，書本上的知識與老師的講解都比較容易理解，但是當(dāng)自己采用剛學(xué)的知識點(diǎn)編寫程序的時(shí)候卻感到十分棘手，有時(shí)候表現(xiàn)在想不到適合題意的算法，有時(shí)候表現(xiàn)在算法想出來之后，只能將書本上原有的程序段轉(zhuǎn)寫到自己的程序中再加以必要的連接已完成程序的編寫。在設(shè)計(jì)軟件之前，我們充分考慮到了軟件的可行性、特殊性以及普遍性，本著由易到難的思想，我們先進(jìn)行了全英文字符的文章的統(tǒng)計(jì)，而后我們則進(jìn)行了其他格式的文章一起圖形文件的讀取，并以二進(jìn)制格式存儲。這次試驗(yàn)讓我充分理解了編程的方法，提高了動手能力。6.4.4張曉雨設(shè)計(jì)小結(jié)首先，通過這次的課程設(shè)計(jì)，我知道并掌握了哈夫曼樹的建立方法，哈夫曼樹的存儲方法，求哈夫曼編碼的方法，這也是我的負(fù)責(zé)編碼的部分。同時(shí)通過小組其他成員的程序設(shè)計(jì)情況，我對用戶界面設(shè)計(jì)有了一定的了解。同時(shí)，我對哈夫曼樹的應(yīng)用有了一定的認(rèn)識，而不是僅僅停留在課本上的程序，而是對最優(yōu)二叉樹在數(shù)據(jù)傳輸上的應(yīng)用有了領(lǐng)會。同時(shí)，我也明白了團(tuán)隊(duì)協(xié)作的重要性。團(tuán)隊(duì)的合作遠(yuǎn)比幾個(gè)人單獨(dú)的工作效率要高。一個(gè)團(tuán)隊(duì)如果有一定的默契程度，那么工作起來也會事半功倍，得心應(yīng)手。一個(gè)真正優(yōu)秀的程序設(shè)計(jì)者，一定不是只會一個(gè)人在工作，而是有團(tuán)隊(duì)協(xié)作能力，與隊(duì)友并肩奮戰(zhàn)。這次的實(shí)踐課，我也學(xué)會了與隊(duì)友一起努力，相互溝通，在團(tuán)隊(duì)合作能力上有了一定的提升。

7附錄A課題任務(wù)分工A-1課題程序設(shè)計(jì)分工學(xué)號姓名程序設(shè)計(jì)函數(shù)原型、類功能說明20133989王健1、voidCompress(char*filename,char*outputfile)//壓縮可視化的實(shí)現(xiàn)新建解壓文件，將壓縮文件哈夫曼信息轉(zhuǎn)換成原文件信息，寫入解壓文件實(shí)現(xiàn)可視化，提供更好的用戶體驗(yàn)20134006張穎voidDeCompress(char*filename,char*outputfile)//解壓可視化的實(shí)現(xiàn)（協(xié)作）新建解壓文件，將壓縮文件哈夫曼信息轉(zhuǎn)換成原文件信息，寫入解壓文件提供更好的用戶體驗(yàn)20133985劉琪voidCompress(char*filename,char*outputfile)//統(tǒng)計(jì)權(quán)重voidDeCompress(char*filename,char*outputfile)//解壓（協(xié)作）讀取原文件，統(tǒng)計(jì)字符出現(xiàn)的次數(shù)（計(jì)統(tǒng)計(jì)權(quán)重），順便根據(jù)權(quán)重進(jìn)行從大到小的排序（便于之后的操作）解壓文件張曉雨voidCompress(char*filename,char*outputfile)//建立哈夫曼樹voidCompress(char*filename,char*outputfile)//編碼以字符的權(quán)重（權(quán)重為0的字符除外）為依據(jù)建立哈夫曼樹依據(jù)建立的哈夫曼樹，得到每一個(gè)字符的編碼

A-2課題報(bào)告分工章節(jié)內(nèi)容完成人1課題概述1.1課題任務(wù)1.2課題原理1.3相關(guān)知識王健2需求分析2.1課題調(diào)研2.2用戶需求分析張穎3方案設(shè)計(jì)3.1總體功能設(shè)計(jì)3.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)3.3函數(shù)原型設(shè)計(jì)3.4主算法設(shè)計(jì)3.5用戶界面設(shè)計(jì)王健4方案實(shí)現(xiàn)4.1開發(fā)環(huán)境與工具4.2程序設(shè)計(jì)關(guān)鍵技術(shù)4.3個(gè)人設(shè)計(jì)實(shí)現(xiàn)（按組員分工）4.3.1王健設(shè)計(jì)實(shí)現(xiàn)4.3.2張穎設(shè)計(jì)實(shí)現(xiàn)4.3.3劉琪設(shè)計(jì)實(shí)現(xiàn)4.3.4張曉雨設(shè)計(jì)實(shí)現(xiàn)王健張穎劉琪張曉雨5測試與調(diào)試5.1個(gè)人測試（按組員分工）5.1.1王健測試5.1.2張穎設(shè)計(jì)5.1.3劉琪設(shè)計(jì)5.1.4張曉雨設(shè)計(jì)5.2組裝與系統(tǒng)測試5.3系統(tǒng)運(yùn)行王健張穎劉琪張曉雨6課題總結(jié)6.1課題評價(jià)6.2團(tuán)隊(duì)協(xié)作6.3下一步工作6.4個(gè)人設(shè)計(jì)心得（按組員分工）6.4.1王健設(shè)計(jì)心得6.4.2張穎設(shè)計(jì)心得6.4.3劉琪設(shè)計(jì)心得6.4.4張曉雨設(shè)計(jì)心得王健張穎劉琪張曉雨

附錄B課題設(shè)計(jì)文檔B-1源程序代碼（見附工程文件夾）B-2工程與可執(zhí)行文件（見附工程文件夾）附錄C用戶操作手冊C．1運(yùn)行環(huán)境說明VS2013C．2操作說明 Windows基本操作基于C8051F單片機(jī)直流電動機(jī)反饋控制系統(tǒng)的設(shè)計(jì)與研究基于單片機(jī)的嵌入式Web服務(wù)器的研究MOTOROLA單片機(jī)MC68HC（8）05PV8/A內(nèi)嵌EEPROM的工藝和制程方法及對良率的影響研究基于模糊控制的電阻釬焊單片機(jī)溫度控制系統(tǒng)的研制基于MCS-51系列單片機(jī)的通用控制模塊的研究基于單片機(jī)實(shí)現(xiàn)的供暖系統(tǒng)最佳啟停自校正（STR）調(diào)節(jié)器單片機(jī)控制的二級倒立擺系統(tǒng)的研究基于增強(qiáng)型51系列單片機(jī)的TCP/IP協(xié)議棧的實(shí)現(xiàn)基于單片機(jī)的蓄電池自動監(jiān)測系統(tǒng)基于32位嵌入式單片機(jī)系統(tǒng)的圖像采集與處理技術(shù)的研究基于單片機(jī)的作物營養(yǎng)診斷專家系統(tǒng)的研究基于單片機(jī)的交流伺服電機(jī)運(yùn)動控制系統(tǒng)研究與開發(fā)基于單片機(jī)的泵管內(nèi)壁硬度測試儀的研制基于單片機(jī)的自動找平控制系統(tǒng)研究基于C8051F040單片機(jī)的嵌入式系統(tǒng)開發(fā)基于單片機(jī)的液壓動力系統(tǒng)狀態(tài)監(jiān)測儀開發(fā)模糊Smith智能控制方法的研究及其單片機(jī)實(shí)現(xiàn)一種基于單片機(jī)的軸快流CO〈,2〉激光器的手持控制面板的研制基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究基于CYGNAL單片機(jī)的在線間歇式濁度儀的研制基于單片機(jī)的噴油泵試驗(yàn)臺控制器的研制基于單片機(jī)的軟起動器的研究和設(shè)計(jì)基于單片機(jī)控制的高速快走絲電火花線切割機(jī)床短循環(huán)走絲方式研究基于單片機(jī)的機(jī)電產(chǎn)品控制系統(tǒng)開發(fā)基于PIC單片機(jī)的智能手機(jī)充電器基于單片機(jī)的實(shí)時(shí)內(nèi)核設(shè)計(jì)及其應(yīng)用研究基于單片機(jī)的遠(yuǎn)程抄表系統(tǒng)的設(shè)計(jì)與研究基于單片機(jī)的煙氣二氧化硫濃度檢測儀的研制基于微型光譜儀的單片機(jī)系統(tǒng)單片機(jī)系統(tǒng)軟件構(gòu)件開發(fā)的技術(shù)研究基于單片機(jī)的液體點(diǎn)滴速度自動檢測儀的研制基于單片機(jī)系統(tǒng)的多功能溫度測量儀的研制基于PIC單片機(jī)的電能采集終端的設(shè)計(jì)和應(yīng)用基于單片機(jī)的光纖光柵解調(diào)儀的研制氣壓式線性摩擦焊機(jī)單片機(jī)控制系統(tǒng)的研制基于單片機(jī)的數(shù)字磁通門傳感器基于單片機(jī)的旋轉(zhuǎn)變壓器-數(shù)字轉(zhuǎn)換器的研究基于單片機(jī)的光纖Bragg光柵解調(diào)系統(tǒng)的研究單片機(jī)控制的便攜式多功能乳腺治療儀的研制基于C8051F020單片機(jī)的多生理信號檢測儀基于單片機(jī)的電機(jī)運(yùn)動控制系統(tǒng)設(shè)計(jì)Pico專用單片機(jī)核的可測性設(shè)計(jì)研究基于MCS-51單片機(jī)的熱量計(jì)基于雙單片機(jī)的智能遙測微型氣象站MCS-51單片機(jī)構(gòu)建機(jī)器人的實(shí)踐研究基于單片機(jī)的輪軌力檢測基于單片機(jī)的GPS定位儀的研究與實(shí)現(xiàn)基于單片機(jī)的電液伺服控制系統(tǒng)用于單片機(jī)系統(tǒng)的MMC卡文件系統(tǒng)研制基于單片機(jī)的時(shí)控和計(jì)數(shù)系統(tǒng)性能優(yōu)化的研究基于單片機(jī)和CPLD的粗光柵位移測量系統(tǒng)研究單片機(jī)控制的后備式方波UPS提升高職學(xué)生單片機(jī)應(yīng)用能力的探究基于單片機(jī)控制的自動低頻減載裝置研究基于單片機(jī)控制的水下焊接電源的研究基于單片機(jī)的多通道數(shù)據(jù)采集系統(tǒng)基于uPSD3234單片機(jī)的氚表面污染測量儀的研制基于單片機(jī)的紅外測油儀的研究96系列單片機(jī)仿真器研究與設(shè)計(jì)基于單片機(jī)的單晶金剛石刀具刃磨設(shè)備的數(shù)控改造基于單片機(jī)的溫度智能控制系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)基于MSP430單片機(jī)的電梯門機(jī)控制器的研制基于單片機(jī)的氣體測漏儀的研究基于三菱M16C/6N系列單片機(jī)的CAN/USB協(xié)議轉(zhuǎn)換器基于單片機(jī)和DSP的變壓器油色譜在線監(jiān)測技術(shù)研究基于單片機(jī)的膛壁溫度報(bào)警系統(tǒng)設(shè)計(jì)基于AVR單片機(jī)的低壓無功補(bǔ)償控制器的設(shè)計(jì)基于單片機(jī)船舶電力推進(jìn)電機(jī)監(jiān)測系統(tǒng)基于單片機(jī)網(wǎng)絡(luò)的振動信號的采集系統(tǒng)基于單片機(jī)的大容量數(shù)據(jù)存儲技術(shù)的應(yīng)用研究基于單片機(jī)的疊圖機(jī)研究與教學(xué)方法實(shí)踐基于單片機(jī)嵌入式Web服務(wù)器技術(shù)的研究及實(shí)現(xiàn)基于AT89S52單片機(jī)的通用數(shù)據(jù)采集系統(tǒng)基于單片機(jī)的多道脈沖幅度分析儀研究機(jī)器人旋轉(zhuǎn)電弧傳感角焊縫跟蹤單片機(jī)控制系統(tǒng)基于單片機(jī)的控制系統(tǒng)在PLC虛擬教學(xué)實(shí)驗(yàn)中的應(yīng)用研究基于單片機(jī)系統(tǒng)的網(wǎng)絡(luò)通信