哈夫曼編碼程序設(shè)計(jì)

時(shí)間：2023-04-30 22:57:36 資料我要投稿

相關(guān)推薦

哈夫曼編碼程序設(shè)計(jì)

算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

哈夫曼編碼/譯碼器設(shè)計(jì)

學(xué)生姓名：學(xué) 號(hào)：

專業(yè)：（計(jì)算機(jī)科學(xué)與技術(shù)）年級(jí)：（大二）指導(dǎo)教師：（汪洋）

2009年6月19日

哈夫曼編碼/譯碼器

問(wèn)題描述：

利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本，但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道）每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣/譯碼系統(tǒng)。

基本要求：

I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmTree中。

E：編碼（Encoding）。利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。

D：譯碼（Decoding）。利用已建好的哈夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。

P：打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。

T：打印哈夫曼樹(shù)（Tree printing）。將已在中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫入文件TreePrint中。

大體解題思路:

（1）對(duì)輸入的一段欲編碼的字符串進(jìn)行統(tǒng)計(jì)各個(gè)字符出現(xiàn)的次數(shù)，并它們轉(zhuǎn)化為權(quán)值{w1,w2,……，wN}構(gòu)成n棵二叉樹(shù)的集合F={T1,T2,……，Tn}把它們保存到結(jié)構(gòu)體數(shù)組HT[n]中,其中{Ti是按它們的ASCⅡ碼值先后排序。其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為Wi的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。

（2）在HT[1..i]中選取兩棵根結(jié)點(diǎn)的權(quán)值最小且沒(méi)有被選過(guò)的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和。

（3）哈夫曼樹(shù)已經(jīng)建立后，從葉子到根逆向求每一個(gè)字符的哈夫曼編碼。

概要設(shè)計(jì)：

實(shí)現(xiàn)的功能：1.查看原文（showpassage()），2.字符統(tǒng)計(jì)(showdetail())，

3.哈夫曼編碼并輸出內(nèi)容(HuffmanCoding(HT,HC,30,w))，4.輸出整篇文章的碼字(printcode())，5.求最小權(quán)值(minweight())，6.最碼字進(jìn)行解碼(decode())，7.測(cè)試解碼(testdecode())，8.推出(break)。

（1）定義結(jié)構(gòu)體HTNOde,*HuffmanTree;typedefchar**HuffmanCode;

定義堆結(jié)構(gòu)體RedType;定義全局變量；

（2）編程序：測(cè)試編碼(void testdecode())；解碼(void decode)；求最

小權(quán)值(void minweight())；打印碼字(void printcode())；堆排序(void HeapAdjust(SqList&L,int s,int

m))

；

哈

夫

曼

編

碼

(void

HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,float *w,int n ))；輸出個(gè)字符的次數(shù)比例(void showdetail())；輸出原英文文章并做統(tǒng)計(jì)(void showpassage())；

（3）主函數(shù)

詳細(xì)設(shè)計(jì)：（1）定義結(jié)構(gòu)體

1.哈夫曼結(jié)構(gòu)體 typedef struct {

float weight;

unsigned int parent, lchild, rchild; }HTNode, *HuffmanTree; typedef char **HuffmanCode ; 2.堆結(jié)構(gòu)體 typedef struct {

float key; //關(guān)鍵字項(xiàng)

int otherinfo; //其他數(shù)據(jù)項(xiàng)（此題目中用不到）

}RedType;

typedef struct {

RedType r[MAXSIZE+1]; //r[0]閑置用作哨兵 int length; //順序表長(zhǎng)度 }SqList;

3.定義全局變量

HuffmanTree HT; //赫夫曼樹(shù) HuffmanCode HC; //碼值

FILE *fp, *fp1, *fp2; int a[30] = {0}; float b[30];

float *w; //權(quán) （2）程序代碼

1.測(cè)試解碼（可以輸入一個(gè)不正確的二進(jìn)制碼串） void testdecode() {

char str[200]; //存放自己輸入的碼子 int p, p1, i; //解碼的線索 char ch; 內(nèi)):\n");

gets(str);

printf("以上碼子解碼后為:\n");

p = 59; //最初令p為樹(shù)根整數(shù)，p由根順著樹(shù)枝一直到樹(shù)葉

i = 0; ch = str[i++]; while (ch!='\0') {

printf("\n請(qǐng)根據(jù)以上各個(gè)字符的編碼輸入一串二進(jìn)制碼字(200個(gè)以

查 !\n");

{

if (ch == '0') {

p = HT[p].lchild; } {

p = HT[p].rchild; } else {

printf("\n你輸入了'0','1'之外的字符，無(wú)法正確譯碼，請(qǐng)檢 return ; //直接結(jié)束 }

ch = str[i++]; //下一個(gè)碼字不斷的取下一個(gè)

else if(ch == '1')

}

if(p

switch (p) {

case 27 : printf(",");

break;

case 28 : printf("."); break;

case 29 : printf(" "); break;

case 30 : printf("\n"); break;

}

p1 = p; //讓p1記住p p = 59; //這里p要重置為59，因?yàn)榻?jīng)過(guò)上面的程序p已經(jīng)變化了，不重置為1則HT[p].lchild!=0||HT[p].rchild!=0所以for語(yǔ)句無(wú)法進(jìn)行!!!!

} //while循環(huán) if (p1 > 30)

printf("\n以上正確譯出了前面的字符，由于你輸入的二進(jìn)制碼不完整，最后一位字符無(wú)法譯出，請(qǐng)檢查!\n");

}

2.下面是解碼 void decode() { int p; char ch;

printf("\n\n對(duì)碼子解碼后的如下:\n"); fp1 = fopen("bianma.txt","r"); if(!fp1) { printf("can not open this file!\n"); exit(0);

}

p = 59; 個(gè)非零整數(shù)，p由根順著樹(shù)枝一直到樹(shù)葉

ch = fgetc(fp1); fp2 = fopen("jiema.txt","w"); if (!fp2) {

printf("can not open this file!\n");

//最初令p為任意一

exit(0);

}

while (ch!=EOF) { for ( ; HT[p].lchild!=0||HT[p].rchild!=0 ; ) 下一個(gè)

{ if (ch == '0') {

p = HT[p].lchild; }

else {

p = HT[p].rchild;

}

ch = fgetc(fp1); } switch (p) {

case 27 : printf(","); fprintf(fp2,","); break;

case 28 : printf("."); fprintf(fp2, "."); break;

case 29 : printf(" ");

fprintf(fp2, " "); break;

case 30 : printf("\n");

fprintf(fp2, "\n");

break;

//下一個(gè)碼字不斷的取

default : printf("%c", p+96);

fprintf(fp2, "%c", p+96);

} p = 59; //這里p要重置為59，因?yàn)榻?jīng)過(guò)上面的程序p已經(jīng)變化了，不重置為1則HT[p].lchild!=0||HT[p].rchild!=0所以for語(yǔ)句無(wú)法進(jìn)行!!!!

} //while循環(huán) printf("\n"); fprintf(fp2, "\n"); fclose(fp1); fclose(fp2); }

3.求最小權(quán)值 void minweight() {

float Weight = 0; int i;

for (i = 0 ; i

Weight = Weight + strlen(HC[i+1])*b[i]; printf("最小權(quán)值是:%f\n",Weight); }

4.打印碼子 void printcode() { char ch;

fp = fopen("Huffman.txt","r"); if (!fp) {

printf("can not open this file!\n"); }

fp1 = fopen("bianma.txt","w");

exit(0);

if (!fp1) { printf("can not open this file!\n"); exit(0);

}

printf("\n原英文文章經(jīng)編碼后如下:\n"); ch = fgetc(fp); while (ch!=EOF) {

if (ch > 96 && ch

printf("%s", HC[ch-96]);

fputs(HC[ch-96], fp1); ch = fgetc(fp); continue; }

if (ch > 64 && ch

fputs(HC[ch-64], fp1); ch = fgetc(fp); continue; } if (ch == ',')

{ printf("%s", HC[27]); fputs(HC[27], fp1); ch = fgetc(fp);

continue; } if (ch == '.')

{

//小寫字母 //輸出到文件里面 //大小字母 //輸出到文件里面

printf("%s", HC[28]); f第一文庫(kù)網(wǎng)puts(HC[28], fp1); ch = fgetc(fp); continue;

} {

if (ch == ' ')

printf("%s", HC[29]); fputs(HC[29], fp1); ch = fgetc(fp); continue;

} {

if (ch == '\n')

printf("%s", HC[30]); fputs(HC[30], fp1); ch = fgetc(fp); continue;

}

printf("\n\n"); fclose(fp); fclose(fp1); } 5.堆排序

void HeapAdjust(SqList &L, int s, int m) {

RedType rc; int j; rc = L.r[s];

for (j = 2 * s ; j

{

if (j L.r[j+1].key) //即使等于也不要?jiǎng)樱挥眉?

++j; break; if (rc.key

}

L.r[s] = rc;

}

void select(HuffmanTree t, int i, int &s1, int &s2)

{ //此函數(shù)被調(diào)用一次則就用堆排序選擇兩個(gè)最小的賦給s1和s2

SqList L;

RedType rc;

int j, k, n = 1;

L.length = 0;

for (j = 1 ; j

{ if (t[j].parent!=0)

continue;

L.r[n].key = t[j].weight; //賦值好,用堆排序

}

for (k = L.length/2 ; k > 0 ; --k)

HeapAdjust(L,k,L.length);

s1 = L.r[1].otherinfo; //最小的選出來(lái)了！

/***把最小的換到最下面***/

rc = L.r[1];

L.r[n].otherinfo = j; //存放序號(hào),j是一直在加一的，n++; L.length++; //這樣寫很巧妙的循環(huán)一次加1，但是n不是的只有在符合條件的情況下才加1

L.r[1] = L.r[L.length]; //此次的select函數(shù)，進(jìn)行堆排序的只有L.length 個(gè)（parent！=0的沒(méi)有在里面），所以這里是L.length而不是i

L.r[L.length] = rc;

HeapAdjust(L,1,L.length-1);

s2 = L.r[1].otherinfo; //次小的選出來(lái)了(這里當(dāng)輸入1 4 2 8四個(gè)數(shù)時(shí)，第一次選出的s1=1,s2=3是對(duì)的，但第二次選出的s1=5，但s2是隨機(jī)數(shù))

}

6.赫夫曼編碼

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *w, int n) // 算法6.12

{ // w存放n個(gè)字符的權(quán)值(均>0),構(gòu)造赫夫曼樹(shù)HT,并求出n個(gè)字符的赫夫曼編碼HC

int m, i, s1, s2, start, k;

unsigned c, f;

HuffmanTree p;

char *cd;

if (n

return;

m = 2 * n - 1;

w = (float *)malloc(30*sizeof(float));

for (i = 0 ; i

*(w+i) = b[i];

HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號(hào)單元未用 for (p = HT + 1, i = 1 ; i

{

(*p).weight = *w;

(*p).parent = 0;

(*p).lchild = 0;

(*p).rchild = 0;

for (i = n + 1 ; i

(*p).parent=0;

for (i = n + 1 ; i

{ // 在HT[1~i-1]中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn),其序號(hào)分別為s1和s2

select(HT, i-1, s1, s2);

HT[s1].parent = i;

HT[s2].parent = i; //最小的和次小的雙親已經(jīng)不為0了，下次就不在它兩中間找最小的和次小的了。

HT[i].lchild = s1;

HT[i].rchild = s2;

HT[i].weight = HT[s1].weight + HT[s2].weight;

} //建立赫夫曼樹(shù)也容易，關(guān)鍵是select這個(gè)子函數(shù)!!! printf("赫夫曼樹(shù)如下表:\n") ;

printf("__________________________________________________________________\n")

\n");

for(k = 1 ; k

{

if (k

printf("|___%2d____|__%c

和%c__|__%f__|____%2d____|____%2d____|____%2d____|\n",k,k+64,k+96,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);

if (k == 27)

printf("|___%2d____|___,____|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);

if (k == 28)

printf("|___%2d____|___.____|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);

if (k == 29)

printf("|___%2d____|__

[k].parent,HT[k].lchild,HT[k].rchild);

if (k == 30)

printf("|___%2d____|__

[k].parent,HT[k].lchild,HT[k].rchild);

if (k > 30)

printf("|___%2d____|________|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);

}

printf("\n") ;

HC = (HuffmanCode)malloc((n+1)*sizeof(char*));

cd = (char*)malloc(n*sizeof(char));

cd[n-1] = '\0';

for (i = 1 ; i

{

start = n-1; //這里f=HT[f].parent是很巧妙的!!! for (c = i, f = HT[i].parent ; f!=0 ; c = f, f = HT[f].parent)//f=HT[i].parent f!=0是結(jié)束條件，所有的編碼最后都要回到HT[m],而只有HT[m]的parent是0!!!

// 從葉子到根逆向求編碼 if (HT[f].lchild==c) //c是左孩子則碼值是0 cd[--start] = '0'; //這樣逆著輸，當(dāng)我們正序輸出的時(shí)候就恰好是想要的編碼了!!!

else

空格__|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT換行__|__%f__|____%2d____|____%2d____|____%2d____|\n",k,HT[k].weight,HT

cd[--start] = '1';

HC[i] = (char*)malloc((n-start)*sizeof(char));

// 為第i個(gè)字符編碼分配空間 strcpy(HC[i],&cd[start]); //從cd復(fù)制編碼(串)到HC，這里的&cd[start]是一個(gè)地址

}

free(cd); // 釋放工作空間 printf("經(jīng)赫夫曼編碼后碼值如下:\n");

for (i = 1 ; i

{

printf("%c和%c---->%f---->", i+64, i+96, HT[i].weight);

puts(HC[i]);

}

printf(" , ---->%f---->%s\n", HT[27].weight, HC[27]);

printf(" . ---->%f---->%s\n", HT[28].weight, HC[28]);

printf("空格---->%f---->%s\n", HT[29].weight, HC[29]);

printf("換行---->%f---->%s\n", HT[30].weight, HC[30]);

}

7.輸出各個(gè)字符的次數(shù)，比例

void showdetail()

{

int i;

printf("此英文文章中各個(gè)字母,個(gè)數(shù)，比例如下表:\n");

printf("____________________________________________\n"); printf("|__字母__|_____個(gè)數(shù)_____|_______比例_______|\n");

for (i = 0 ; i

printf("|__%c和%c__|_____%3d______|_____%f_____|\n", i+97, i+65, a[i], b[i]);

printf("|___,____|_____%3d______|_____%f_____|\n", a[26], b[26]); printf("|___.____|_____%3d______|_____%f_____|\n", a[27], b[27]); printf("|__空格__|_____%3d______|_____%f_____|\n", a[28], b[28]);

printf("|__換行__|_____%3d______|_____%f_____|\n", a[29], b[29]); printf("\n");

}

8.輸出原英文文章，并做統(tǒng)計(jì)

void showpassage()

{

float count = 0;

int i;

char ch;

{

printf("can not open Huffman.txt !\n"); exit(0); fp = fopen("Huffman.txt","r"); if (!fp)

}

printf("要編碼的文章如下:\n");

ch = fgetc(fp);

while (ch!=EOF)

{

putchar(ch); //把要編碼的文章輸入到屏幕中 if (ch >= 'a' && ch

{

a[ch-'a']++;

count+=1;

}

if (ch >= 'A' && ch

count+=1;

}

if (ch == ',')

元 a[26]++; //逗號(hào)放在27號(hào)單元 a[27]++; //句號(hào)放在28號(hào)單元 a[28]++; //空格符放在29號(hào)單元 a[29]++; //換行符放在30號(hào)單 if (ch == '.') if (ch == ' ') if (ch == '\n')

ch = fgetc(fp); //a[]的零號(hào)單元放a

}

printf("\n\n");

}

（3）主函數(shù)

void main()

{

char c;

char s[200]=" 1.查看原文.\n 2.字符統(tǒng)計(jì).\n 3.赫夫曼編碼并輸出內(nèi)容.\n 4.輸出整篇文章的碼字.\n 5.求最小權(quán)值.\n 6.對(duì)碼子進(jìn)行解碼.\n 7.測(cè)試解碼.\n 8.退出.\n";

printf("\n\n");

printf("******************************************************\n");

printf("

**\n");

printf(" ** 說(shuō)明:本程序只對(duì)英文文章的52個(gè)大小寫字母，逗號(hào)，句 **\n");

printf(" ** 號(hào)，空格符，換行符進(jìn)行赫夫曼編碼，并且大小寫字母不 **\n");

printf(" ** 區(qū)分，其它字符因?yàn)槌霈F(xiàn)的概率太低，for (i = 0 ; i

故本程序沒(méi)有考慮 **\n");

printf(" ** ，各個(gè)字符出現(xiàn)的頻率對(duì)應(yīng)他們的權(quán)值，解碼時(shí)可能與原 **\n");

printf(" ** 文有少量的失真，希望用戶理解和支持，謝謝! **\n");

printf("** **\n");

printf("********************************************************\n");

printf("\n\n");

printf("******************************************************\n");

printf(" * 注意:必須按順序先進(jìn)行1，2，3項(xiàng)的操作,否則會(huì)有錯(cuò)誤! *\n");

printf(" * 當(dāng)1,2,3項(xiàng)順次進(jìn)行完后可以任意選擇這8種操作. *\n");

printf("******************************************************\n");

printf("請(qǐng)認(rèn)真閱讀以上注意的內(nèi)容，如果已經(jīng)讀完請(qǐng)按任意鍵開(kāi)始操作:\n");

c=getch();

system("cls");

{

printf("\n請(qǐng)選擇你要的操作:\n\n");

puts(s);

c=getch();

switch (c)

{

case '1' : showpassage(); //這里必須先按 break; //1，2，3先按順序進(jìn)行1，2，3的操作，否則有問(wèn)題順序操作完后，則可以任意選擇這8項(xiàng)操作

case '2' : showdetail(); break; break; break; break; break; break; case '3' : HuffmanCoding(HT, HC, w, 30); case '4' : printcode(); case '5' : minweight(); case '6' : decode(); case '7' : testdecode(); case '8' : break; printf("請(qǐng)輸入正確的選項(xiàng)!\n"); } default : putch(7);

}while(c!='8');

printf("\n\nBye Bye ^_^ .!\n\n");

}

調(diào)試分析：

1. 在堆定義中RedType r[MAXSIZE+1],r[0]閑置用作哨兵；

2. 在測(cè)試解碼中（p

switch (p)后P重置59是因?yàn)橐驗(yàn)榻?jīng)過(guò)上面的程序p已經(jīng)變化了，不重置為1則HT[p].lchild!=0||HT[p].rchild!=0所以for語(yǔ)句無(wú)法進(jìn)行!!!!

3. 在解碼void decode()中最初令p為任意一個(gè)非零整數(shù)，p由根順著樹(shù)枝一直到樹(shù)葉; switch (p)后p要重置為59，因?yàn)榻?jīng)過(guò)上面的程序p已經(jīng)變化了，不重置為1則HT[p].lchild!=0||HT[p].rchild!=0所以for語(yǔ)句無(wú)法進(jìn)行!!!!

4. 堆排序void HeapAdjust(SqList &L, int s, int m) 中 if (j

L.r[j].key > L.r[j+1].key) //即使等于也不要?jiǎng)樱挥眉?；if (rc.key

5. void select(HuffmanTree t, int i, int &s1, int &s2)

//此函數(shù)被調(diào)用一次則就用堆排序選擇兩個(gè)最小的賦給s1和s2

6. void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *w, int n) // w存放n個(gè)字符的權(quán)值(均>0),構(gòu)造赫夫曼樹(shù)HT,并求出n個(gè)字符的赫夫曼編碼HC

測(cè)試數(shù)據(jù)：

權(quán)值的個(gè)數(shù)是N=8

測(cè)試數(shù)據(jù)為7 19 2 6 32 3 21 10

結(jié)果是：

哈夫曼樹(shù):

5 (2, 3)

11 (5, 6)