哈夫曼實現文件壓縮解壓縮（c語言）

寫一個對文件進行壓縮和解壓縮的程序，功能如下：

① 可以對純英文文檔實現壓縮和解壓；

② 較好的界面程序運行的說明。

介紹哈夫曼：

效率最高的判別樹即為哈夫曼樹

在計算機數據處理中，霍夫曼編碼使用變長編碼表對源符號（如文件中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之后的字符串的平均長度、期望值降低，從而達到無損壓縮數據的目的。

例如，在英文中，e的出現機率最高，而z的出現概率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時，e極有可能用一個比特來表示，而z則可能花去25個比特（不是26）。用普通的表示方法時，每個英文字母均占用一個字節，即8個比特。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對于英文中各個字母出現概率的較準確的估算，就可以大幅度提高無損壓縮的比例。

霍夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個權值Wi（i=1,2,...n）構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度為Li（i=1,2,...n）?？梢宰C明霍夫曼樹的WPL是最小的。

文件壓縮與解壓

姓名：

范天祚

1 程序說明

1.1數據結構

哈夫曼樹

1.2函數功能說明

printfPercent界面

compress()讀取文件內容并加以壓縮，將壓縮內容寫入另一個文檔

uncompress()解壓縮文件，并將解壓后的內容寫入新文件

1.3 程序編寫的思路及流程

壓縮：統計字符出現次數、將節點按出現次數排序、構造哈夫曼樹、設置字符編碼、讀文件字符、按設置好的編碼替換字符、寫入存儲文件

解壓：讀取文件各參數、轉換成二進制碼、按碼求對應字符、寫入存儲文件

#define _CRT_SECURE_NO_WARNINGS

#include

#include

#include

struct head

{

int b; //字符

long count; //文件中該字符出現的次數

long parent, lch, rch; //make a tree

char bits[256]; //the huffuman code

};

struct head header[512], tmp; //節點樹

void printfPercent(int per)

{

int i = 0;

printf("|");

for(i = 0; i < 10; i++)

{

if(i < per/10)

printf(">");

else

printf("-");

}

printf("|已完成%d%%\n",per);

}

//函數：compress()

//作用：讀取文件內容并加以壓縮

//將壓縮內容寫入另一個文檔

int compress(const char *filename,const char *outputfile)

{

char buf[512];

unsigned char c;

long i, j, m, n, f;

long min1, pt1, flength;

FILE *ifp, *ofp;

int per = 10;

ifp = fopen(filename, "rb"); //打開原始文件

if (ifp == NULL)

{

printf("打開文件失敗:%s\n",filename);

return 0; //如果打開失敗，則輸出錯誤信息

}

ofp = fopen(outputfile,"wb"); //打開壓縮后存儲信息的文件

if (ofp == NULL)

{

printf("打開文件失敗:%s\n",outputfile);

return 0;

}

flength = 0;

while (!feof(ifp))

{

fread(&c, 1, 1, ifp);

header[c].count ++; //讀文件，統計字符出現次數

flength ++; //記錄文件的字符總數

}

flength --;

header[c].count --;

for (i = 0; i < 512; i ++) //HUFFMAN算法中初始節點的設置

{

if (header[i].count != 0)

header[i].b = (unsigned char) i;

else

header[i].b = -1;

header[i].parent = -1;

header[i].lch = header[i].rch = -1;

}

for (i = 0; i < 256; i ++) //將節點按出現次數排序

{

for (j = i + 1; j < 256; j ++)

{

if (header[i].count < header[j].count)

{

tmp = header[i];

header[i] = header[j];

header[j] = tmp;

}

}

}

for (i = 0; i < 256; i ++) //統計不同字符的數量

{

if (header[i].count == 0)

break;

}

n = i;

m = 2 * n - 1;

for (i = n; i < m; i ++)

{

min1 = 999999999;

for (j = 0; j < i; j ++)

{

if (header[j].parent != -1) continue;

if (min1 > header[j].count)

{

pt1 = j;

min1 = header[j].count;

continue;

}

}

header[i].count = header[pt1].count;

header[pt1].parent = i;

header[i].lch = pt1;

min1 = 999999999;

for (j = 0; j < i; j ++)

{

if (header[j].parent != -1) continue;

if (min1 > header[j].count)

{

pt1 = j;

min1 = header[j].count;

continue;

}

}

header[i].count += header[pt1].count;

header[i].rch = pt1;

header[pt1].parent = i;

}

for (i = 0; i < n; i ++) //構造HUFFMAN樹，設置字符的編碼

{

f = i;

header[i].bits[0] = 0;

while (header[f].parent != -1)

{

j = f;

f = header[f].parent;

if (header[f].lch == j)

{

j = strlen(header[i].bits);

memmove(header[i].bits + 1, header[i].bits, j + 1);

header[i].bits[0] = '0';

}

else

{

j = strlen(header[i].bits);

memmove(header[i].bits + 1, header[i].bits, j + 1);

header[i].bits[0] = '1';

}

}

}

//下面的就是讀原文件的每一個字符，按照設置好的編碼替換文件中的字符

fseek(ifp, 0, SEEK_SET); //將指針定在文件起始位置

fseek(ofp, 8, SEEK_SET); //以8位二進制數為單位進行讀取

buf[0] = 0;

f = 0;

pt1 = 8;

printf("讀取將要壓縮的文件:%s\n",filename);

printf("當前文件有:%d字符\n",flength);

printf("正在壓縮\n");

while (!feof(ifp))

{

c = fgetc(ifp);

f ++;

for (i = 0; i < n; i ++)

{

if (c == header[i].b) break;

}

strcat(buf, header[i].bits);

j = strlen(buf);

c = 0;

while (j >= 8) //當剩余字符數量不小于8個時

{

for (i = 0; i < 8; i ++) //按照八位二進制數轉化成十進制ASCII碼寫入文件一次進行壓縮

{

if (buf[i] == '1') c = (c << 1) | 1;

else c = c << 1;

}

fwrite(&c, 1, 1, ofp);

pt1 ++;

strcpy(buf, buf + 8);

j = strlen(buf);

}

if(100 * f/flength > per)

{

printfPercent(per);

per += 10;

}

if (f == flength)

break;

}

printfPercent(100);

if (j > 0) //當剩余字符數量少于8個時

{

strcat(buf, "00000000");

for (i = 0; i < 8; i ++)

{

if (buf[i] == '1') c = (c << 1) | 1;

else c = c << 1; //對不足的位數進行補零

}

fwrite(&c, 1, 1, ofp);

pt1 ++;

}

fseek(ofp, 0, SEEK_SET); //將編碼信息寫入存儲文件

fwrite(&flength,1,sizeof(flength),ofp);

fwrite(&pt1, sizeof(long), 1, ofp);

fseek(ofp, pt1, SEEK_SET);

fwrite(&n, sizeof(long), 1, ofp);

for (i = 0; i < n; i ++)

{

tmp = header[i];

fwrite(&(header[i].b), 1, 1, ofp);

pt1++;

c = strlen(header[i].bits);

fwrite(&c, 1, 1, ofp);

pt1++;

j = strlen(header[i].bits);

if (j % 8 != 0) //當位數不滿8時，對該數進行補零操作

{

for (f = j % 8; f < 8; f ++)

strcat(header[i].bits, "0");

}

while (header[i].bits[0] != 0)

{

c = 0;

for (j = 0; j < 8; j ++)

{

if (header[i].bits[j] == '1') c = (c << 1) | 1;

else c = c << 1;

}

strcpy(header[i].bits, header[i].bits + 8);

fwrite(&c, 1, 1, ofp); //將所得的編碼信息寫入文件

pt1++;

}

header[i] = tmp;

}

fclose(ifp);

fclose(ofp); //關閉文件

printf("壓縮后文件為:%s\n",outputfile);

printf("壓縮后文件有:%d字符\n",pt1 + 4);

return 1; //返回壓縮成功信息

}

//函數：uncompress()

//作用：解壓縮文件，并將解壓后的內容寫入新文件

int uncompress(const char *filename,const char *outputfile)

{

char buf[255], bx[255];

unsigned char c;

char out_filename[512];

long i, j, m, n, f, p, l;

long flength;

int per = 10;

int len = 0;

FILE *ifp, *ofp;

char c_name[512] = {0};

ifp = fopen(filename, "rb"); //打開文件

if (ifp == NULL)

{

return 0; //若打開失敗，則輸出錯誤信息

}

//讀取原文件長

if(outputfile)

strcpy(out_filename,outputfile);

else

strcpy(out_filename,c_name);

ofp = fopen(out_filename, "wb"); //打開文件

if (ofp == NULL)

{

return 0;

}

fseek(ifp,0,SEEK_END);

len = ftell(ifp);

fseek(ifp,0,SEEK_SET);

printf("將要讀取解壓的文件:%s\n",filename);

printf("當前文件有:%d字符\n",len);

printf("正在解壓\n");

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; i < n; i ++) //讀取壓縮文件內容并轉換成二進制碼

{

fread(&header[i].b, 1, 1, ifp);

fread(&c, 1, 1, ifp);

p = (long) c;

header[i].count = p;

header[i].bits[0] = 0;

if (p % 8 > 0) m = p / 8 + 1;

else m = p / 8;

for (j = 0; j < m; j ++)

{

fread(&c, 1 , 1 , ifp);

f = c;

_itoa(f, buf, 2);

f = strlen(buf);

for (l = 8; l > f; l --)

{

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);

fseek(ifp, 8, SEEK_SET);

m = 0;

bx[0] = 0;

while (1)

{

while (strlen(bx) < (unsigned int)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) break;

}

strcpy(bx, bx + header[i].count);

c = header[i].b;

fwrite(&c, 1, 1, ofp);

m ++;

if(100 * m/flength > per)

{

printfPercent(per);

per += 10;

}

if (m == flength) break;

}

printfPercent(100);

fclose(ifp);

fclose(ofp);

printf("解壓后文件為:%s\n",out_filename);

printf("解壓后文件有:%d字符\n",flength);

return 1; //輸出成功信息

}

int main(int argc,const char *argv[])

{

memset(&header,0,sizeof(header));

memset(&tmp,0,sizeof(tmp));

compress("測試文檔.txt","測試文檔.txt.zip");

uncompress("測試文檔.txt.zip","測試文檔.txt 解壓后.txt");

system("pause");

return 0;

}

2?功能展示

2.1 控制臺顯示

2.2 文件效果

開始時只有一個文件《測試文檔.txt》：

打開《測試文檔.txt》

《測試文檔.txt》文件大?。?/p>

程序運行結束后多了兩個文件：

以文本形式打開壓縮二進制文件《測試文檔.txt.zip》：

《測試文檔.txt.zip》文件屬性：

C 語言

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。