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

1、計算機科學學院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題 目：基于哈夫曼樹的文件壓縮/解壓程序?qū)W生姓名：林華學 號：121345012021專 業(yè)：計算機科學與技術(shù)班 級：12級（2）班 指導教師姓名及職稱：陳明 講師 起止時間： 2014 年 3 月 2014 年 4 月1 需求分析1.1課題背景及意義近年來，隨著計算機技術(shù)的發(fā)展，多媒體計算機技術(shù)、計算機網(wǎng)絡(luò)技術(shù)以及現(xiàn)代多媒體通信技術(shù)正在向著信息化、高速化、智能化迅速發(fā)展。各個領(lǐng)域的應(yīng)用與發(fā)展，各個系統(tǒng)的數(shù)據(jù)量越來越大，給數(shù)據(jù)的存儲、傳輸以及有效、快速獲取信息帶來了嚴重的障礙。數(shù)據(jù)壓縮技術(shù)能夠比較有效地解決這個問題。還有在最近幾年中興起的物聯(lián)網(wǎng)和云計算都是對海量的

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

3、= D:1XXX.zip1.3.2選擇2時：輸入一個待解壓的壓縮文件名稱(可帶路徑)。如:D:1YYY.txt解壓文件名稱=D:1YYY.zip2概要設(shè)計2.1問題解決的思路概述建立哈夫曼樹根據(jù)哈夫曼樹解碼對二進制文件進行解碼統(tǒng)計字符，得出統(tǒng)計出字符的權(quán)值n根據(jù)哈夫曼樹編碼對編碼進行壓縮生成哈夫曼樹生成對應(yīng)文件生成二進制文件 圖1 主程序流程圖2.2 算法思想：2.2.1輸入要壓縮的文件首先運行的時候，用戶主界面上有菜單提示該如何使用軟件，根據(jù)菜單提示選擇所要執(zhí)行的項，依次進行，因為各個環(huán)節(jié)之間有先后順序。第一步為輸入壓縮軟件的名稱，由鍵盤輸入文件路徑和文件名稱，讀入字符數(shù)組中，打開該文件，按

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

5、他們的編碼表示，即完成一次編碼。2.2.5解碼壓縮即根據(jù)Huffman樹進行譯碼讀取編碼文件，依據(jù)創(chuàng)建的Huffman樹，定義一個指針指向根結(jié)點。從根結(jié)點開始，每讀一個字符，指針變化一次（當讀取的字符是1時，指針指向當前所指結(jié)點的右孩子，當讀取的字符是0時，指針指向當前所指結(jié)點的左孩子），直至該指針所指結(jié)點為葉子結(jié)點時結(jié)束（即當結(jié)點的左右孩子均為空時）。將當前葉子結(jié)點所代表的字符值輸出到譯碼文件中，依次讀取編碼文件中的字符，按照上述方法依次進行下去直至文件2.3數(shù)據(jù)結(jié)構(gòu)定義typedef struct node /哈夫曼樹結(jié)構(gòu)體 long w;/權(quán)重 short p,l,r; /定義雙親，左孩

6、子，右孩子htnode,*htnp;typedef struct huffman_code unsigned char len;/記錄該結(jié)點哈夫曼編碼的長度 unsigned char *codestr; /記錄該結(jié)點的哈夫曼編碼hufcode;2.5主程序的流程及模塊間關(guān)系主函數(shù)實例化huffmanTree類，并實現(xiàn)菜單工具欄，通過用戶的選擇輸入，用switch語句進行分支執(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. 詳細設(shè)計核心算法-huffman算法：3.1根據(jù)給定的n個權(quán)值w1,w2,wn構(gòu)成n棵二叉樹的集合F=T1,T2,Tn,其中每棵二叉樹T1中只有一個帶權(quán)的 w1的根據(jù)點，其左右子樹均空。3.2在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左右樹上根結(jié)點的權(quán)值之和。3.3在F中刪除這兩棵樹，同時將所得到的二叉樹加入F中。3.4重復3.2,3.3,直到F中只含一棵樹為止。這棵樹便是Huffman樹。Huffman樹可用于構(gòu)造代碼總長度最短的編

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

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

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

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

12、signed char *codestr; /記錄該結(jié)點的哈夫曼編碼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、/計算字符頻率int search_set(htnp ht,int n,int *s1, int *s2);/查找文件int create_hftree(long w,int n,htnode ht);/創(chuàng)建哈夫曼樹int encode_hftree(htnp htp,int n,hufcode hc);/記錄哈夫曼編碼unsigned char chars_to_bits(const unsigned char chars8);/計算文件大小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);/建立哈弗曼樹中用于選擇最小權(quán)值結(jié)點的函數(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("請輸入待壓縮文件路徑：");gets(file);compress(file,NULL);break;case 2:puts("請輸入待解壓文件路徑：");gets(file);decompress(file,NULL);break;default : printf("指令錯誤！請重新輸入指令：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("文件打開失?。≌堉匦螺斎胛募窂剑?quot;); 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("建立哈夫曼樹失敗

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("是否打印該文件中字符對應(yīng)的huffman樹及編碼？");puts(" Please input Y OR N");doscanf("%s",&ch);switch(ch)case 'Y': puts("以下是哈夫曼樹：");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("指令錯誤！請重新輸入指令：n");while(ch!='Y'&&ch!='N'); fclose(in); fclose(out); for(i=0;i<256;i+) free(hci.codestr); return 0; /計算字符頻率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é)點 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é)點 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)建哈夫曼樹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; /建立哈弗曼樹中用于選擇最小權(quán)值結(jié)點的函數(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