算法設(shè)計(jì)哈夫曼編碼

1、寧夏師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)序號(hào)： 7 實(shí)驗(yàn)項(xiàng)目名稱：哈夫曼編碼學(xué)號(hào)姓名專業(yè)、班實(shí)驗(yàn)地點(diǎn)指導(dǎo)教師時(shí) 間一、實(shí)驗(yàn)?zāi)康募耙螅?） 掌握貪心算法的基本思想和組成要素；（2） 掌握使用貪心方法解決實(shí)際問題的基本方法和步驟；二、實(shí)驗(yàn)設(shè)備（環(huán)境）及要求1、環(huán)境要求：硬件：PC（PII以上，128M以上內(nèi)存）、因特網(wǎng)接入；軟件：Windows XP操作系統(tǒng)、VC+6.0編程環(huán)境。2、實(shí)驗(yàn)要求：(1) 獨(dú)立完成實(shí)驗(yàn)，源代碼書寫規(guī)范；(2) 程序運(yùn)行結(jié)果以屏幕截圖的方式粘貼在對(duì)應(yīng)位置，截圖必須清晰準(zhǔn)確；(3) 實(shí)驗(yàn)完成后必須有實(shí)驗(yàn)結(jié)果的分析及本次實(shí)驗(yàn)的總結(jié)。三、實(shí)驗(yàn)內(nèi)容與步驟#i

2、nclude <stdio.h>#include <stdlib.h>#include <string.h>#define N 7 /編碼字符個(gè)數(shù)#define M (2*N-1)/哈夫曼樹結(jié)點(diǎn)個(gè)數(shù)typedef struct char c;/字符 float f;/指定字符出現(xiàn)的頻率 int i;/序號(hào) int parent,lchild,rchild;/分別指向父親、左孩子、右孩子序號(hào) char *code;/指定字符的哈夫曼前綴編碼huffmanNode,*huffman;typedef struct huffmanNode *element;/ in

3、t capacity;/優(yōu)先隊(duì)列最大容量 int size;/優(yōu)先隊(duì)列中已經(jīng)具有的結(jié)點(diǎn)數(shù)量heapNode,*priorityqueue;/判斷優(yōu)先隊(duì)列是否為空，如果為空，則返回1，否則返回0int isEmpty(priorityqueue h) return h->size=0;/判斷優(yōu)先隊(duì)列是否已滿，如果滿，則返回1，否則0int isFull(priorityqueue h) return h->capacity=h->size;/功能：向隊(duì)列中插入指定的元素，插入后的隊(duì)列具有小隊(duì)性質(zhì)/先判斷隊(duì)列是否已滿，如果已經(jīng)滿了，則給出提示信息，并返回/否則采用上濾法，即先生成

4、一個(gè)空穴，然后把比自己大的父結(jié)點(diǎn)向下移，直到找到插入位置為止/把隊(duì)列中最小的元素出隊(duì)列，同時(shí)隊(duì)列應(yīng)該保持小堆特性/優(yōu)先隊(duì)列初始化void pushPrioQueue(priorityqueue h,huffmanNode x)int i;if(isFull(h) printf("隊(duì)列已滿n"); return;for(i=+h->size;h->elementi/2.f>x.f;i/=2) h->elementi=h->elementi/2;/父結(jié)點(diǎn)向下移h->elementi=x;/功能：將隊(duì)列中出現(xiàn)頻率最小的元素出隊(duì)，并取下濾法使剩下

5、的保持小堆性質(zhì)/首先，判斷隊(duì)列是否已空，如果空，提示，并返回，否則把和一個(gè)元素和隊(duì)列/中最后一個(gè)元素取回，然后按下濾法使剩下的保持小堆性質(zhì)/最后將第一個(gè)元素返回（即最小元素返回）huffmanNode popPrioQueue(priorityqueue h) huffmanNode minNode,lastNode;int i,child;if(isEmpty(h) printf("隊(duì)列已經(jīng)空"); return h->element0;/哨兵元素minNode=h->element1;lastNode=h->elementh->size-; fo

6、r(i=1;2*i<=h->size;i=child) child=i*2;if(child!=h->size&&h->elementchild.f>h->elementchild+1.f) /如果右孩子結(jié)點(diǎn)的頻率小于左孩子結(jié)點(diǎn)的頻率則child的取值為右孩子child+;if(h->elementchild.f<lastNode.f) h->elementi=h->elementchild;else break;h->elementi=lastNode;return minNode;/*初始化優(yōu)先隊(duì)列，將哈夫曼

7、樹中葉子結(jié)點(diǎn)入隊(duì)*/priorityqueue initializePrioQueue(int n,huffman tree) /將tree中n個(gè)元素按字符出現(xiàn)的頻率生成堆/tree中前n個(gè)元素是樹中的葉子結(jié)點(diǎn)priorityqueue h;int i;h=(priorityqueue)malloc(sizeof(heapNode);if(h=NULL) printf("out of space"); exit(-1);h->capacity=n;/最大容量h->size=0;/目前具有的元素個(gè)數(shù)h->element=(huffman)malloc(siz

8、eof(huffmanNode)*(n+1);/*其中第0個(gè)元素為哨兵元素，由于元素出現(xiàn)的頻率必須大于等于零 因此給此元素的頻率設(shè)置為小于零便可,主要有入隊(duì)時(shí)用到*/if(h->element=NULL) printf("out of space"); exit(-1); h->element0.f=-1;for(i=1;i<=n;i+) pushPrioQueue(h,treei);/入隊(duì)列return h;/*功能：用于生成哈夫曼樹*/huffman ctrHuffmanTree(int n)int m=2*n-1;/1n存儲(chǔ)葉子結(jié)點(diǎn)，n+1m存儲(chǔ)樹的

9、n-1個(gè)內(nèi)部結(jié)點(diǎn)huffman tree=(huffman)malloc(sizeof(huffmanNode)*(m+1);/用于存儲(chǔ)哈夫曼樹各結(jié)點(diǎn)priorityqueue h;/用于存儲(chǔ)優(yōu)先隊(duì)列首地址int i;if(tree=NULL) printf("out of space"); exit(-1);/*生成葉子結(jié)點(diǎn)*/for(i=1;i<=n;i+) printf("enter %d chara and weight:",i); scanf("%c%f",&treei.c,&treei.f); tre

10、ei.i=i; treei.parent=treei.lchild=treei.rchild=-1; treei.code=NULL; getchar();/吸收回車/*初始化優(yōu)先隊(duì)列*/ h=initializePrioQueue(n,tree); /*生成n-1個(gè)內(nèi)部結(jié)點(diǎn)*/for(i=n+1;i<=m;i+) huffmanNode x,y,z; x=popPrioQueue(h); y=popPrioQueue(h); z.f=x.f+y.f; z.lchild=x.i; z.rchild=y.i; z.parent=-1; z.i=i; treex.i.parent=i; tr

11、eey.i.parent=i; treei=z; pushPrioQueue(h,z);/*前綴碼生成*/for(i=1;i<=n;i+) char *c=(char *)malloc(sizeof(n); int start=n-1; int j=i; if(c=NULL) printf("out of space"); exit(-1); cn-1='0' while(treej.parent!=-1) if(treetreej.parent.lchild=j)c-start='0' else c-start='1'

12、 j=treej.parent; /*給編碼申請(qǐng)空間*/ treei.code=(char *)malloc(sizeof(char)*(n-start); strcpy(treei.code,c+start);/*釋放優(yōu)先隊(duì)列空間*/free(h->element);free(h);return tree;main() huffman tree=ctrHuffmanTree(N); int i,j; char s20,ch,encoding100; for(i=1;i<=N;i+) printf("character:%c,weight:%f,父結(jié)點(diǎn)序號(hào):%d,前綴編碼

13、:%sn",treei.c,treei.f,treei.parent,treei.code); printf("nninput the string to encoding:"); /輸入要編碼的串 gets(s); /輸出編碼 for(ch=si,i=0;ch!='0'i+) int j; for(j=1;j<=N;j+) if(treej.c=ch) printf("%s",treej.code); break; ch=si; printf("nn"); /輸入編碼，輸出字符串 printf(&qu

14、ot;input the binary string to deencoding:"); gets(encoding); j=0; /源碼為： printf("源碼為"); puts(encoding); printf("解碼結(jié)果為："); while(encodingj!='0') i=M;/從根開始遍歷，至到葉子結(jié)點(diǎn) while(treei.lchild!=-1 |treei.rchild!=-1) if(encodingj='1') i=treei.rchild;/指向右孩子 else i=treei.lchild;/左孩子 j+; printf("%c",treei.c); /釋放樹空間 for(i=1;i<=N;i+) free(treei.code); free(tree); printf("n");四、實(shí)驗(yàn)結(jié)果與數(shù)據(jù)處理五、分析與討論哈夫曼編碼是廣泛的用于數(shù)據(jù)文件壓縮的十分有效的編碼方法，其壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用0,1串表示各字符的最優(yōu)表示方式。 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。哈夫曼算法