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

1、計(jì)算機(jī)科學(xué)學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目：基于哈夫曼樹(shù)的文件壓縮/解壓程序?qū)W生姓名：林華學(xué) 號(hào)：121345012021專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)：12級(jí)（2）班 指導(dǎo)教師姓名及職稱：陳明 講師 起止時(shí)間： 2014 年 3 月 2014 年 4 月1 需求分析1.1課題背景及意義近年來(lái)，隨著計(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ù)量越來(lái)越大，給數(shù)據(jù)的存儲(chǔ)、傳輸以及有效、快速獲取信息帶來(lái)了嚴(yán)重的障礙。數(shù)據(jù)壓縮技術(shù)能夠比較有效地解決這個(gè)問(wèn)題。還有在最近幾年中興起的物聯(lián)網(wǎng)和云計(jì)算都是對(duì)海量的

2、數(shù)據(jù)進(jìn)行處理和傳輸?shù)?，如果不?duì)數(shù)據(jù)進(jìn)行壓縮，那么數(shù)據(jù)傳輸所需的帶寬要求就很高，物理成本上也隨之上升。所以說(shuō)數(shù)據(jù)壓縮在計(jì)算機(jī)通信中占有很重要的位置，且涉及領(lǐng)域多，應(yīng)用廣泛，與我們的生活息息相關(guān)。1.2課題要求1.2.1實(shí)現(xiàn)一個(gè)基于哈夫曼樹(shù)的文件壓縮程序和文件解壓程序。1.2.2.壓縮程序能輸入源文件進(jìn)行壓縮，輸出壓縮文件；1.2.3解壓程序讀入壓縮文件，根據(jù)相應(yīng)的哈夫曼編碼解壓還原 ，得到對(duì)應(yīng)的源文件。1.2.4可選做：求出壓縮率；打印哈夫曼樹(shù)；對(duì)文件夾壓縮；圖形圖形化窗口操作界面。1.3任務(wù)和要求1.3.1選擇1時(shí)：輸入一個(gè)待壓縮的文本文件名稱(可帶路徑)。如:D:1XXX.txt壓縮文件名稱

3、= D:1XXX.zip1.3.2選擇2時(shí)：輸入一個(gè)待解壓的壓縮文件名稱(可帶路徑)。如:D:1YYY.txt解壓文件名稱=D:1YYY.zip2概要設(shè)計(jì)2.1問(wèn)題解決的思路概述建立哈夫曼樹(shù)根據(jù)哈夫曼樹(shù)解碼對(duì)二進(jìn)制文件進(jìn)行解碼統(tǒng)計(jì)字符，得出統(tǒng)計(jì)出字符的權(quán)值n根據(jù)哈夫曼樹(shù)編碼對(duì)編碼進(jìn)行壓縮生成哈夫曼樹(shù)生成對(duì)應(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ù)組中，打開(kāi)該文件，按

4、照提示進(jìn)行壓縮。若打不開(kāi)，則繼續(xù)輸入。2.2.2讀文件并計(jì)算字符頻率文件將信息存放在字符數(shù)組中；計(jì)算每個(gè)字符出現(xiàn)的次數(shù)，申請(qǐng)一個(gè)結(jié)構(gòu)體數(shù)組空間， 用讀取的字符減去字符結(jié)束符作為下標(biāo)記錄字符的頻率。2.2.3根據(jù)字符的頻率，利用Huffman編碼思想創(chuàng)建Huffman樹(shù)將所記錄的字符的頻率作為權(quán)值來(lái)創(chuàng)建Huffman樹(shù)，依次選擇權(quán)值最小的兩個(gè)字符作為左右孩子，其和作為父結(jié)點(diǎn)的權(quán)值，依次進(jìn)行下去，直到所有的字符結(jié)點(diǎn)都成為葉子結(jié)點(diǎn)。2.2.4由創(chuàng)建的Huffman樹(shù)來(lái)決定字符對(duì)應(yīng)的編碼，進(jìn)行文件的壓縮根據(jù)創(chuàng)建的Huffman樹(shù)來(lái)確定個(gè)字符的01編碼，左孩子為0，右孩子為1。讀取文件，依次將每個(gè)字符用

5、他們的編碼表示，即完成一次編碼。2.2.5解碼壓縮即根據(jù)Huffman樹(shù)進(jìn)行譯碼讀取編碼文件，依據(jù)創(chuàng)建的Huffman樹(shù)，定義一個(gè)指針指向根結(jié)點(diǎn)。從根結(jié)點(diǎn)開(kāi)始，每讀一個(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)定義typedef struct node /哈夫曼樹(shù)結(jié)構(gòu)體 long w;/權(quán)重 short p,l,r; /定義雙親，左孩

6、子，右孩子htnode,*htnp;typedef struct huffman_code unsigned char len;/記錄該結(jié)點(diǎn)哈夫曼編碼的長(zhǎng)度 unsigned char *codestr; /記錄該結(jié)點(diǎn)的哈夫曼編碼hufcode;2.5主程序的流程及模塊間關(guān)系主函數(shù)實(shí)例化huffmanTree類，并實(shí)現(xiàn)菜單工具欄，通過(guò)用戶的選擇輸入，用switch語(yǔ)句進(jìn)行分支執(zhí)行huffmanTree類中功能函數(shù)：1:壓縮函數(shù) int compress(char *source_file,char *obj_file)；2:解壓函數(shù) int decompress(char *source_fi

7、le,char*obj_file)；并可在完成相應(yīng)功能后安全退出，壓縮或解壓的文件在同文件夾下生成。3. 詳細(xì)設(shè)計(jì)核心算法-huffman算法：3.1根據(jù)給定的n個(gè)權(quán)值w1,w2,wn構(gòu)成n棵二叉樹(shù)的集合F=T1,T2,Tn,其中每棵二叉樹(shù)T1中只有一個(gè)帶權(quán)的 w1的根據(jù)點(diǎn)，其左右子樹(shù)均空。3.2在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。3.3在F中刪除這兩棵樹(shù)，同時(shí)將所得到的二叉樹(shù)加入F中。3.4重復(fù)3.2,3.3,直到F中只含一棵樹(shù)為止。這棵樹(shù)便是Huffman樹(shù)。Huffman樹(shù)可用于構(gòu)造代碼總長(zhǎng)度最短的編

8、碼方案。為了詳細(xì)說(shuō)明這個(gè)問(wèn)題，特以下面例子來(lái)說(shuō)明: 圖2 問(wèn)題詳解編碼完成之后，開(kāi)始對(duì)源文件進(jìn)行壓縮。1. 從源文件讀一個(gè)字符，從葉子結(jié)點(diǎn)中找出和此字符相同的字符結(jié)點(diǎn)，將其編碼寫入一個(gè)臨時(shí)字符組codes；2. 當(dāng)codes的長(zhǎng)度大于等于8時(shí)，將其前8位轉(zhuǎn)換成字符寫入目標(biāo)文件中；3. 重復(fù)1和2此過(guò)程，直至讀完源文件中的所有字符；4. 若codes最后還有剩余的不足8位的01代碼，則將其低位補(bǔ)0至8位，再寫入目標(biāo)文件。 主程序模塊: 圖 3 主程序模塊4. 調(diào)試分析報(bào)告由于壓縮與解壓過(guò)程中沒(méi)有輸入新生成文件的路徑，因此解壓后的文件會(huì)將原文件覆蓋。如圖： 圖4 壓縮前原文件 圖 5 壓縮后生成文

9、件 圖 6 解壓后文件5.用戶使用說(shuō)明在運(yùn)行程序之前，首先在D盤先建立一個(gè)待壓縮的文件1.doc，運(yùn)行程序如下圖所示。 圖7 版本測(cè)試結(jié)果圖壓縮：在命令行下輸入1對(duì)文件進(jìn)行壓縮，根據(jù)提示輸入剛剛建的文本文件（1.doc），和要生成的壓縮文件名稱，按回車確認(rèn)進(jìn)行壓縮。 圖 8 執(zhí)行壓縮操作圖成功執(zhí)行完畢后如下圖所示。 圖 9 執(zhí)行壓縮操作圖選擇打印哈夫曼樹(shù)及編碼。 圖10 執(zhí)行打印操作圖解壓：在命令行下輸入2對(duì)本程序壓縮的文件進(jìn)行恢復(fù)，根據(jù)提示輸入待恢復(fù)的文件名稱和恢復(fù)后的文件名稱，按回車確定，成功執(zhí)行后如下圖所示。 圖11 執(zhí)行解壓操作圖6.測(cè)試結(jié)果詳細(xì)測(cè)試結(jié)果請(qǐng)參見(jiàn) 5 使用功能。6.1測(cè)試

10、報(bào)告原文件壓縮后解壓后1txt文件(14598b)8192b8192b2pdf文件(359398b)356352b359398b3jpg文件(31455b)28672b31455b4Mp3文件(72000b)69632b72000b參考文獻(xiàn)1鄭莉 等編著C+語(yǔ)言程序設(shè)計(jì)（第三版）北京：清華大學(xué)出版社.2譚浩強(qiáng) .C+面向?qū)ο蟪绦蛟O(shè)計(jì)(第二版) M.北京：中國(guó)鐵道出版社，2009.3洪國(guó)勝 等編著 C+ Builder程序設(shè)計(jì)輕松上手北京：清華大學(xué)出版社.4胡學(xué)鋼等數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo)北京：清華大學(xué)出版社，1999年 第1版.5王昆侖 

11、等編著 數(shù)據(jù)結(jié)構(gòu)域算法（高等學(xué)校計(jì)算機(jī)精品課程系列教材） 中國(guó)鐵道工業(yè)出版社.附錄：源程序#include <stdio.h> #include <string.h> #include <stdlib.h> #include <windows.h>typedef struct node /哈夫曼樹(shù)結(jié)構(gòu)體 long w;/權(quán)重 short p,l,r; /定義雙親，左孩子，右孩子htnode,*htnp;typedef struct huffman_code unsigned char len;/記錄該結(jié)點(diǎn)哈夫曼編碼的長(zhǎng)度 un

12、signed char *codestr; /記錄該結(jié)點(diǎn)的哈夫曼編碼hufcode;typedef char *huffmancode;int initial_files(char *source_file,FILE *inp,char *obj_file,FILE *outp);/文件初始信息char *create_file(char *source_file,char* obj_file);/創(chuàng)建待壓縮文件名int compress(char *source_file,char *obj_file);/壓縮函數(shù)long frequency_data(FILE *in,long fre);

13、/計(jì)算字符頻率int search_set(htnp ht,int n,int *s1, int *s2);/查找文件int create_hftree(long w,int n,htnode ht);/創(chuàng)建哈夫曼樹(shù)int encode_hftree(htnp htp,int n,hufcode hc);/記錄哈夫曼編碼unsigned char chars_to_bits(const unsigned char chars8);/計(jì)算文件大小int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc,char* source_f

14、ile,long source_filesize);/輸入待壓縮文件路徑int decompress(char *source_file,char *obj_file);/解壓函數(shù)void get_mini_huffmantree(FILE* in,short mini_ht2);/建立哈弗曼樹(shù)中用于選擇最小權(quán)值結(jié)點(diǎn)的函數(shù)int write_decompress_file(FILE *in,FILE* out,short mini_ht2,long bits_pos,long obj_filesize);/輸入待解壓文件路徑int d_initial_files(char *source_fi

15、le,FILE *inp,char *obj_file,FILE *outp);main()int s;char file10;system("color 3F");printf(" *n");printf(" * 菜單： *n");printf(" * 1.-壓縮- *n");printf(" * 2.-解壓- *n");printf(" * 0.-退出- *n");printf(" *n");scanf("%d",&s);w

16、hile(s!=0)getchar();switch(s)case 1:puts("請(qǐng)輸入待壓縮文件路徑：");gets(file);compress(file,NULL);break;case 2:puts("請(qǐng)輸入待解壓文件路徑：");gets(file);decompress(file,NULL);break;default : printf("指令錯(cuò)誤！請(qǐng)重新輸入指令：n");puts(" ");printf(" *n");printf(" * 菜單： *n");pr

17、intf(" * 1.-壓縮- *n");printf(" * 2.-解壓- *n");printf(" * 0.-退出- *n");printf(" *n");scanf("%d",&s);/文件初始信息int initial_files(char *source_file,FILE *inp,char *obj_file,FILE *outp) if(fopen(source_file,"rb")=NULL) return -1; if(obj_file=NULL

18、) 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,壓縮文件:%sn",source_file,obj_file); if(*outp=fopen(obj_file,"wb")=NULL) return -1; if(*inp=fopen(source_file,"rb"

19、)=NULL) return -1; free(obj_file); return 0; /創(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_filetemp-sour

20、ce_file='0' strcat(obj_file,".zip"); return obj_file;/壓縮函數(shù)int compress(char *source_file,char *obj_file) FILE *in,*out;char ch; int error_code,i,j; float compress_rate; hufcode hc256; /編碼的位數(shù)最多為256位 htnode ht256*2-1; long frequency256,source_filesize,obj_filesize=0; error_code=initi

21、al_files(source_file,&in,obj_file,&out); if(error_code!=0) puts("文件打開(kāi)失??！請(qǐng)重新輸入文件路徑："); return error_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("建立哈夫曼樹(shù)失敗

22、！"); return error_code; error_code=encode_hftree(ht,256,hc); if(error_code!=0) puts("建立哈夫曼編碼失??！"); return error_code; for(i=0;i<256;i+) obj_filesize+=frequencyi*hci.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(sho

23、rt); obj_filesize+=strlen(source_file)+1; obj_filesize+=sizeof(long); obj_filesize+=sizeof(unsigned int); 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_fi

24、lesize); if(error_code!=0) puts("寫入文件失??！"); return error_code; puts("壓縮完成!"); puts(" ");puts("是否打印該文件中字符對(duì)應(yīng)的huffman樹(shù)及編碼？");puts(" Please input Y OR N");doscanf("%s",&ch);switch(ch)case 'Y': puts("以下是哈夫曼樹(shù)：");for(i=256;i&

25、lt;256*2-2;i+)if(hti.w>0)printf("%-10d%-10d%-10d%-10d%-10dn",i,hti.w,hti.p,hti.l,hti.r);puts("以下是哈夫曼編碼：");for(i=0;i<256;i+)if(frequencyi=0)i+;elseprintf("%dt",frequencyi);for(j=0;j<hci.len;j+)printf(" %d",hci.codestrj);printf("n");break;case

26、 'N':break;default : printf("指令錯(cuò)誤！請(qǐng)重新輸入指令：n");while(ch!='Y'&&ch!='N'); fclose(in); fclose(out); for(i=0;i<256;i+) free(hci.codestr); return 0; /計(jì)算字符頻率long frequency_data(FILE *in,long frequency) int i,read_len; unsigned char buf256; long filesize; for(i=0

27、;i<256;i+) /去掉權(quán)值為0的結(jié)點(diǎn) frequencyi=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+=frequencyi; return filesize; int search_set(htnp ht,int n,int *s1, int *s2) in

28、t i,x; long minValue = 999999,min = 0; for(x=0;x<n;x+) if(htx.p=-1) break; for(i=0;i<n;i+) if(hti.p=-1 && hti.w < minValue) minValue = hti.w; min=i; *s1 = min; minValue = 999999,min = 0; for(i=0;i<n;i+) if(hti.p=-1 && hti.w < minValue && i != *s1) minValue = ht

29、i.w; min=i; *s2 = min; return 1; /創(chuàng)建哈夫曼樹(shù)int create_hftree(long w,int n,htnode ht) int m,i,s1,s2; if (n<1) return -1; m=2*n-1; if (ht=NULL) return -1; for(i=0;i<n;i+) hti.w=wi;hti.p=hti.l=hti.r=-1; for(;i<m;i+) hti.w=hti.p=hti.l=hti.r=-1; for(i=n;i<m;i+) search_set(ht,i,&s1,&s2);

30、hts1.p = hts2.p = i; hti.l = s1;hti.r = s2; hti.w = hts1.w + hts2.w; return 0; int encode_hftree(htnp htp,int n,hufcode hc) int i,j,p,codelen; unsigned char *code=(unsigned char*)malloc(n*sizeof(unsigned char); if (code=NULL) return -1; for(i=0;i<n;i+) for(p=i,codelen=0;p!=2*n-2;p=htpp.p,codelen+

31、) codecodelen=(htphtpp.p.l=p?0:1); if(hci.codestr=(unsigned char *)malloc(codelen)*sizeof(unsigned char)=NULL) return -1; hci.len=codelen; for(j=0;j<codelen;j+) hci.codestrj=codecodelen-j-1; free(code); return 0; unsigned char chars_to_bits(const unsigned char chars8) int i; unsigned char bits=0;

32、 bits|=chars0; for(i=1;i<8;+i) bits<<=1; bits|=charsi; return bits; int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc,char* source_file,long source_filesize) unsigned int i,read_counter,write_counter,zip_head=0xFFFFFFFF; unsigned char write_char_counter,code_char_counter,copy_ch

33、ar_counter, read_buf256,write_buf256,write_chars8,file_size=strlen(source_file); hufcode *cur_hufcode; fseek(in,0L,SEEK_SET); fseek(out,0L,SEEK_SET); fwrite(&zip_head,sizeof(unsigned int),1,out); fwrite(&file_size,sizeof(unsigned char),1,out); fwrite(source_file,sizeof(char),file_size,out);

34、fwrite(&source_filesize,sizeof(long),1,out); for(i=256;i<256*2-1;i+) fwrite(&(hti.l),sizeof(hti.l),1,out); fwrite(&(hti.r),sizeof(hti.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_count

35、er;i+) cur_hufcode=&hcread_bufi; 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_hufco

36、de->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_bufwrite_counter+=chars_to_bits(write_chars); if(write_counter=256) fwrite(write_buf,1,256,out); write_counter=0; fwr

37、ite(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); return 0; /建立哈弗曼樹(shù)中用于選擇最小權(quán)值結(jié)點(diǎn)的函數(shù)void get_mini_huffmantree(FILE* in,short mini_ht2) int i; for(i=0;i<256;i+) mini_hti0=mini_hti1=-1; fread(mini_hti,s

38、izeof(short),2*(256-1),in); int write_decompress_file(FILE *in,FILE* out,short mini_ht2,long bits_pos,long obj_filesize) long cur_size; unsigned char read_buf256,write_buf256,convert_bit; unsigned int read_counter,write_counter,cur_pos; fseek(in,bits_pos,SEEK_SET); fseek(out,0L,SEEK_SET); read_count

39、er=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_bufread_counter&convert_bit)=0?mini_htcur_pos0:mini_htcur_pos1); if(cur_pos<256) write_bufwrite_counter=(unsigned char)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; fwrite(write_buf,1,write_counter,out); ret