赫夫曼編譯碼器 課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào) 告 書題目名稱 赫夫曼編/譯碼器 學(xué) 院 專 業(yè) 專業(yè)班級(jí) 學(xué) 號(hào) 學(xué)生姓名 指導(dǎo)教師 目 錄一 需求分析1二 概要設(shè)計(jì)1 1 抽象數(shù)據(jù)類型 2 算法設(shè)計(jì)的思想 3 程序總體及主要算法的流程圖三 源代碼4四 測(cè)試結(jié)果12五 運(yùn)行結(jié)果分析14 六 收獲、體會(huì)及意見14 一、 需求分析1. 演示過程中，輸入字符為26個(gè)大寫的英文字母與空格，輸入個(gè)數(shù)n<=27,輸入形式以一個(gè)“#”為結(jié)束符，且不可輸入非法字符和重復(fù)自符，若出現(xiàn)，程序?qū)⒆詣?dòng)刪除。2. 程序執(zhí)行的命令包括：1） 根據(jù)給出的數(shù)值構(gòu)造哈夫曼樹。2） 根據(jù)哈夫曼樹給字符編碼。3） 根據(jù)所得出的編碼進(jìn)行譯碼。3.利用哈

2、夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。在此程序的運(yùn)行過程中，充分體現(xiàn)出赫夫曼編譯碼器可利用價(jià)值。二、 概要設(shè)計(jì)為了實(shí)現(xiàn)上述程序功能，需要一個(gè)抽象數(shù)據(jù)類型，如：1.抽象數(shù)據(jù)類型赫夫曼樹的定義如下：ADT HuffmanTree數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R:若D=F，則R=F，稱HuffmanTree為空二叉樹；若¹F,則=，是如下二元關(guān)系：（1）在中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū);（2）若D-root¹F，則存在D-root=D1,Dr,且D1ÇDr=F;（3） 若D1¹

3、F，則D1中存在唯一的元素x1，<root,x1>ÎH,且存在D1上的關(guān)系H1ÌH；若Dr¹F，則Dr中存在唯一的元素xr，<root,xr>ÎH,且存在Dr上的關(guān)系HrÌH;H=<root,x1>,<root,xr>,H1,Hr （4） (D1,H1)是一棵符合本定義的二叉樹，稱為根的左子樹，(Dr,Hr)是一棵符合本定義的二叉樹，稱為根的右子樹。2、算法的設(shè)計(jì)思想此程序的設(shè)計(jì)思想為：輸入程序所需數(shù)據(jù)，構(gòu)建相應(yīng)的赫夫曼樹，利用已有數(shù)據(jù)進(jìn)行赫夫曼編碼，并進(jìn)行譯碼過程，最后對(duì)運(yùn)行結(jié)果分析處理。大致思

4、路如下：1）.初始化。根據(jù)下表給出的英文字母的使用頻度，建立赫夫曼樹。調(diào)用函數(shù)選擇出權(quán)值最小的兩個(gè)結(jié)點(diǎn)，依照程序構(gòu)建赫夫曼樹?？崭瘢?.2 E：0.105 T：0.071 O：0.0644A：0.063 N：0.059 I：0.054 R：0.053S：0.052 H：0.047 D：0.035 L：0.029C：0.023 U：0.0225 F：0.0221 M：0.021P：0.0175 Y、W：0.012 G：0.011 B：0.0105V：0.008 K：0.003 X：0.002 J、Q：0.001Z：0.0012）. 編碼。利用已建好的赫夫曼樹，對(duì)電報(bào)正文進(jìn)行編碼。3）. 譯碼。對(duì)

5、編碼好的內(nèi)容進(jìn)行譯碼。4）. 打印編碼。3、程序總體及主要算法的流程圖 1）.程序總體 輸入程序所需數(shù)據(jù)，運(yùn)用select函數(shù)構(gòu)建相應(yīng)的赫夫曼樹，利用已有字符進(jìn)行逆根法求赫夫曼編碼，并運(yùn)用transcode函數(shù)進(jìn)行譯碼過程，再運(yùn)用input函數(shù)進(jìn)行字符的輸入，最后對(duì)運(yùn)行結(jié)果分析處理 2）.主要算法的流程圖三、源代碼#include<stdio.h>#include<malloc.h>#include<string.h>#include<stdlib.h>typedef struct int weight; char ch; int parent,

6、lchild,rchild;/定義赫夫曼樹HTNode,*HuffmanTree;/動(dòng)態(tài)分布數(shù)組存儲(chǔ)赫夫曼樹typedef structchar ch;char *chs;/定義赫夫曼型的字符和指針HuffmanCode;/ 存儲(chǔ)赫夫曼編碼typedef struct/char ch;/int weight;/聲明字符及權(quán)值sw;/ 存儲(chǔ)權(quán)值和字符typedef struct/HuffmanTree HT;/HuffmanCode *HC;/聲明一個(gè)赫夫曼樹編碼huf;/ 存儲(chǔ)赫夫曼樹HT及其編碼HCvoid select(HTNode * HT,int n,int *n1,int *n2)/

7、 int i=1; int n3;/ while(HTi.parent!=0)/ i+;/ *n1=i;/ i+;/ while(HTi.parent!=0) i+;/ *n2=i;/ if(HT*n1.weight<HT*n2.weight)/ n3=*n1;*n1=*n2;*n2=n3;/ for(i+;i<=n;i+)/ if(HTi.parent=0)/ if(HTi.weight<HT*n1.weight)/ *n1=i;/ else if(HTi.weight<HT*n2.weight)/ *n2=i;/ /運(yùn)用select函數(shù)找出最小的兩個(gè)權(quán)值以便構(gòu)造赫夫

8、曼樹huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)/w存放n個(gè)字符的權(quán)值（均>0)，構(gòu)造赫夫曼樹HT，并求出n個(gè)字符的赫夫曼編碼HC。int m,i,s1,s2,start,c,f;/HuffmanTree p;/char *cd;/if(n<=1) return 0;/m=2*n-1;/HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0單元未用for(p=HT+1,i=1;i<=n;i+,p+,w+)/p->weight=w->

9、;weight;p->ch=w->ch;p->parent=0;p->lchild=0;p->rchild=0;/for(;i<=m;i+,p+)/p->weight=0;p->ch=''p->parent=0;p->lchild=0;p->rchild=0;/for(i=n+1;i<=m;i+)/建赫夫曼樹 select(HT,i-1,&s1,&s2);/ HTs1.parent=i;HTs2.parent=i;/ HTi.lchild=s1;HTi.rchild=s2;/ HTi.wei

10、ght=HTs1.weight+HTs2.weight;/建樹過程調(diào)用select函數(shù)以建樹HC=(HuffmanCode *)malloc(n+1)*sizeof(char);/分配n個(gè)字符編碼的頭指針向量cd=(char *)malloc(n*sizeof(char);/分配求編碼的工作空間cdn-1='0'/編碼結(jié)束符for(i=1;i<=n;i+)/逐個(gè)字符求赫夫曼編碼 start=n-1;/編碼結(jié)束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/從葉子到根逆向求編碼 if(HTf.lchild=c)cd-start

11、='0'/ else cd-start='1'/ HCi.ch=HTi.ch;/ HCi.chs=(char*)malloc(n-start)*sizeof(char);/為第i個(gè)字符編碼分配空間 strcpy(HCi.chs,&cdstart);/從cd編制編碼（串）到HC printf("%c %-10sn",HCi.ch,HCi.chs);/HUF->HT=HT;/HUF->HC=HC;/return HUF;/char * convert(char *chars,char *chars1,HuffmanCode *

12、hc,int n)/ 編寫轉(zhuǎn)換函數(shù) char *p=chars; int i; / strcpy(chars1,"");/ 將輸入的字符串復(fù)制到chars1中 while(*p)/ i=1; while(hci.ch!=*p&&i<=n) i+;/ strcat(chars1,hci.chs); p+;/將字符串連接起來 printf("the chars translate are:%sn",chars1);/return chars1;/運(yùn)用convent函數(shù)對(duì)已寫好的字符列進(jìn)行編碼void transcode(HuffmanT

13、ree ht,char *chars2,char*chars3)/ 編寫譯碼過程 int i=1,p; char *q=chars2;char *r=chars3;/ while(hti.parent!=0) i+;/ p=i; / while(*q)/ while(htp.lchild!=0 && *q)/ 當(dāng)遍歷時(shí)遇到0則向左走，遇到1則向右走 if(*q='0')/ p=htp.lchild;/ else p=htp.rchild;/ q+;/ if(htp.lchild=0)/*r=htp.ch;r+;/ p=i;/ *r='0'/ pr

14、intf("the chars are:");/ puts(chars3);/ /運(yùn)用transcode函數(shù)進(jìn)行譯碼void input(int *n,sw *w)/ int i;/printf("input the mount of char:");/scanf("%d",n);/ for(i=1;i<=*n;i+,w+)/printf("input the %dth char and weight:",i);/ 輸入字符和權(quán)值fflush(stdin);/scanf("%c%d",&a

15、mp;w->ch,&w->weight);/運(yùn)用input函數(shù)進(jìn)行字符的輸入void main(void)/HTNode HT;/HuffmanCode HC,*hc;/聲明一個(gè)指針HuffmanTree ht;/huf *HUF,huf2;/int n;/sw w40;/聲明一個(gè)數(shù)組char ch,inchar500,outchar1000;/ 定義輸入和輸出的最大字符數(shù)char *abc;/char *p=inchar;/input(&n,w);/調(diào)用input函數(shù)HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);

16、/printf("input chars to translate,ends of '#':");/ 輸入待翻譯的字符fflush(stdin);/清除流,解決輸入干擾ch=getchar();/while(ch!='#')/ 字符結(jié)束符*p=ch;/p+;/ch=getchar();/*p='0'/hc=HUF->HC;/ht=HUF->HT;/譯碼abc=convert(inchar,outchar,hc,n);/用convert函數(shù)進(jìn)行字符轉(zhuǎn)換transcode(ht,abc,outchar);/調(diào)用transcode函數(shù)翻譯編碼四、測(cè)試結(jié)果五、運(yùn)行結(jié)果分析1在源代碼的編寫結(jié)束之后，進(jìn)行調(diào)試，等到調(diào)試的結(jié)果完全正確時(shí)，根據(jù)要求進(jìn)行程序運(yùn)行，輸入數(shù)據(jù)，最終記錄得出的結(jié)果。2由于對(duì)學(xué)習(xí)的知識(shí)理解、掌握不足，在早期的編碼過程中存在一些困難，但經(jīng)過查找相關(guān)資料及自己的相關(guān)學(xué)習(xí)，問題已經(jīng)得到解決。今后應(yīng)該重點(diǎn)理解二叉樹的基本操作和實(shí)際