用哈夫曼編碼C語(yǔ)言實(shí)現(xiàn)文件壓縮

1、華北科技學(xué)院 用哈夫曼編碼實(shí)現(xiàn)文件壓縮實(shí)驗(yàn)報(bào)告用哈夫曼編碼實(shí)現(xiàn)文件壓縮實(shí) 驗(yàn) 報(bào) 告課程名稱 數(shù)據(jù)結(jié)構(gòu)B 實(shí)驗(yàn)學(xué)期 2012 至 2013 學(xué)年 第 一 學(xué)期學(xué)生所在系部 計(jì)算機(jī)學(xué)院 年級(jí) 2011 專業(yè)班級(jí) 信管B111 學(xué)生姓名 學(xué)號(hào) 任課教師 蘭蕓 實(shí)驗(yàn)成績(jī) 一、實(shí)驗(yàn)題目：用哈夫曼編碼實(shí)現(xiàn)文件壓縮二、實(shí)驗(yàn)?zāi)康模?、 了解文件的概念。2、 掌握線性鏈表的插入、刪除等算法。3、掌握Huffman樹的概念及構(gòu)造方法。4、掌握二叉樹的存儲(chǔ)結(jié)構(gòu)及遍歷算法。5、利用Huffman樹及Huffman編碼，掌握實(shí)現(xiàn)文件壓縮的一般原理。三、實(shí)驗(yàn)設(shè)備與環(huán)境：微型計(jì)算機(jī)、Windows 系列操作系統(tǒng) 、Vis

2、ual C+6.0軟件四、實(shí)驗(yàn)內(nèi)容：根據(jù)ascii碼文件中各ascii字符出現(xiàn)的頻率情況創(chuàng)建Haffman樹，再將各字符對(duì)應(yīng)的哈夫曼編碼寫入文件中，實(shí)現(xiàn)文件壓縮。五、概要設(shè)計(jì)：（1）構(gòu)造Hufffman樹的方法Hufffman算法構(gòu)造Huffman樹步驟：I. 根據(jù)給定的n個(gè)權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹，令起權(quán)值為wj。II. 在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和。III. 在森林中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中。IV. 重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。（2）Huf

3、fman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長(zhǎng)最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹，然后將樹中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列。(3) 解壓 根據(jù)存放在文件中的編碼表和文件壓縮后的編碼，進(jìn)行一對(duì)一的翻譯過程。六、詳細(xì)設(shè)計(jì)： 壓縮的代碼#include #include #include #include struct head unsigned char b; /*the charactor*/ long count; /*the frequency*/ long pare

4、nt,lch,rch; /*make a tree*/ char bits256; /*the haffuman code*/ header512,tmp; void yasuo() /*壓縮*/ char filename255,outputfile255,buf512; unsigned char c; char wenjianming255; long i,j,m,n,f; long min1,pt1,flength; FILE *ifp,*ofp; printf(輸入文件地址及文件名:); gets(filename); ifp=fopen(filename,rb); /*打開源文件*

5、/while(ifp=NULL) printf(打開文件出錯(cuò)n); printf(重新輸入文件地址及文件名); gets(filename); ifp=fopen(filename,rb); printf(輸入壓縮后的文件地址和文件名及后綴:); gets(wenjianming); ofp=fopen(wenjianming,wb); /*創(chuàng)建并打開目的文件*/while(ofp=NULL)printf(重新輸入壓縮后的文件地址和文件名及后綴:); ofp=fopen(wenjianming,wb); flength=0; while(!feof(ifp) /*讀取ifp文件*/ fread

6、(&c,1,1,ifp); /*按位讀取*/ headerc.count+; flength+; flength-1; headerc.count-1; /*讀取文件結(jié)束*/ for(i=0;i512;i+) /*構(gòu)造哈弗曼樹*/ if(headeri.count!=0) headeri.b=(unsigned char)i; else headeri.b=0; headeri.parent=-1; headeri.lch=headeri.rch=-1; for(i=0;i256;i+) for(j=i+1;j256;j+) if(headeri.countheaderj.count) tmp

7、=headeri; headeri=headerj; headerj=tmp; for(i=0;i256;i+) if(headeri.count=0) break; n=i; m=2*n-1; for(i=n;im;i+) min1=999999999; for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count=headerpt1.count; headerpt1.parent=i; headeri.lch=pt1; min1=999999999; for(j=0;jheaderj.count) pt

8、1=j; min1=headerj.count; continue; headeri.count+=headerpt1.count; headeri.rch=pt1; headerpt1.parent=i; for(i=0;in;i+) f=i; headeri.bits0=0; while(headerf.parent!=-1) j=f; f=headerf.parent; if(headerf.lch=j) j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=0; else j=st

9、rlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=1; /*哈弗曼構(gòu)造結(jié)束*/ fseek(ifp,0,SEEK_SET); /*把文件指針指向文件的開頭*/ fwrite(&flength,sizeof(int),1,ofp); /把哈弗曼代碼寫入ofp文件 fseek(ofp,8,SEEK_SET); buf0=0; f=0; pt1=8; while(!feof(ifp) c=fgetc(ifp); /從流中讀取一個(gè)字符，并增加文件指針的位置 f+; for(i=0;i=8) for(i

10、=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c0) strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); pt1+; fseek(ofp,4,SEEK_SET); /*fseek 用于二進(jìn)制方式打開的文件,移動(dòng)文件讀寫指針位置.第一個(gè)是文件流,第3個(gè)是指針零點(diǎn)位置,第2個(gè)是把指針移動(dòng)到的地點(diǎn). */ fwrite(&pt1,sizeof(long),1,ofp); /*是要輸出數(shù)據(jù)的地址,每次寫入的位數(shù),數(shù)據(jù)項(xiàng)的個(gè)數(shù)，目標(biāo)文件地址*/ fs

11、eek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(long),1,ofp); for(i=0;in;i+) fwrite(&(headeri.b),1,1,ofp); c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0) /*按八位讀取*/ for(f=j%8;f8;f+) strcat(headeri.bits,0); while(headeri.bits0!=0) c=0; for(j=0;j8;j+) if(headeri.bitsj=1) c=(c1)|

12、1; else c=c1; strcpy(headeri.bits,headeri.bits+8); /*把從headeri.bits+8地址開始且含有NULL結(jié)束符的字符串賦值到以headeri.bits開始的地址空間 */ fwrite(&c,1,1,ofp); fclose(ifp); fclose(ofp); printf(壓縮成功n); void main() /*主函數(shù)*/printf(輸入a開始?jí)嚎sn);printf(輸入b結(jié)束壓縮n);while(1)char c; c=getch(); if(c=a) yasuo(); else if(c=b) return;壓縮的圖解解壓的

13、代碼#include #include #include #include struct head unsigned char b; /*the charactor*/ long count; /*the frequency*/ long parent,lch,rch; /*make a tree*/ char bits256; /*the haffuman code*/ header512,tmp; void jieya() /*解壓*/ char filename255,outputfile255,buf255,bx255; unsigned char c; char wenjianmin

14、g255; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; printf(要解壓的文件：); gets(filename); ifp=fopen(filename,rb); /*打開源文件*/while(ifp=NULL) printf(打開文件出錯(cuò)n); printf(重新輸入文件地址及文件名); gets(filename); ifp=fopen(filename,rb); printf(輸入解壓后的文件地址和文件名及后綴:); gets(wenjianming); ofp=fopen(wenjianming,wb); /*創(chuàng)建并打開目的

15、文件*/while(ofp=NULL) ofp=fopen(d:123解壓的文件.txt,wb); fread(&flength,sizeof(long),1,ifp); fread(&f,sizeof(long),1,ifp); fseek(ifp,f,SEEK_SET); fread(&n,sizeof(long),1,ifp); for(i=0;i0) m=p/8+1; else m=p/8; for(j=0;jf;l-) strcat(headeri.bits,0); strcat(headeri.bits,buf); headeri.bitsp=0; for(i=0;in;i+) f

16、or(j=i+1;jstrlen(headerj.bits) tmp=headeri; headeri=headerj; headerj=tmp; p=strlen(headern-1.bits); fseek(ifp,8,SEEK_SET); m=0; bx0=0; while(1) while(strlen(bx)f;l-) strcat(bx,0); strcat(bx,buf); for(i=0;in;i+) if(memcmp(headeri.bits,bx,headeri.count)=0) break; strcpy(bx,bx+headeri.count); c=headeri.b; fwrite(&c,1,1,ofp); m+; if(m=flength) break; fclose(ifp); fclose(ofp); printf(解壓成功n); return;