數(shù)據(jù)結(jié)構(gòu)哈夫曼樹

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1問題描述已知n個(gè)字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼2問題分析求哈夫曼編碼，首先要根據(jù)字符出現(xiàn)的頻率，即權(quán)值，構(gòu)建哈夫曼樹，然后 根據(jù)哈夫曼樹求出哈夫曼編碼。3.算法設(shè)計(jì)創(chuàng)建哈夫曼樹：對n個(gè)權(quán)值，創(chuàng)建2n-1個(gè)節(jié)點(diǎn)，pare nt都默認(rèn)為0,然后進(jìn) 行循環(huán)查找，每次循環(huán)都從所有節(jié)點(diǎn)中找出pare nt為0且weight最小的兩個(gè)節(jié)點(diǎn)，序號分別為si和s2,將si節(jié)點(diǎn)和s2節(jié)點(diǎn)作為本節(jié)點(diǎn)的Ichild和 rchild，構(gòu)建出一顆哈夫曼樹，循環(huán) 2n-1次，最后只剩下一顆哈夫曼樹，即 所要求的哈夫曼樹。哈夫曼編碼：從葉子節(jié)點(diǎn)出發(fā)，尋找雙親節(jié)點(diǎn)，若沒有則說明已經(jīng)到根節(jié) 點(diǎn)；若

2、有雙親節(jié)點(diǎn)，如果本節(jié)點(diǎn)是雙親節(jié)點(diǎn)的左孩子，則編碼為0,右孩子編碼為1,依次尋找直到走到根節(jié)點(diǎn)。最后將所求編碼倒序輸出即為哈夫曼 編碼。4.測試數(shù)據(jù)測試數(shù)據(jù)為8個(gè)字符，權(quán)值分別為：5,29,7,8,14,23,3,11測試結(jié)果：請蓊入套編碼陽字將，頁空格開 a b c d e f 1請輸入要編碼字符的權(quán)值，以空格輛開5 29 7 a 14 23 3 11 赫夫曼編碼為：b：18c:0Q01d:0603fi：01f9：0U1h：lll5總結(jié)建立哈夫曼樹的時(shí)候，是逆向構(gòu)建，即先創(chuàng)建葉節(jié)點(diǎn)，再創(chuàng)建根節(jié)點(diǎn)，從下往上 倉U建。求哈夫曼編碼的時(shí)候也是一樣，從葉子節(jié)點(diǎn)不斷找該節(jié)點(diǎn)的根節(jié)點(diǎn)，直到找到 該哈夫曼樹

3、的根節(jié)點(diǎn)。6附錄#in elude <iostream.h>#i nclude <malloc.h>#in elude <stri ng.h>#define ERROR 0#define OK 1/赫夫曼樹和赫夫曼編碼的存儲表示 typedef structun sig ned int weight;un sig ned int pare nt,lchild,rchild;HTNode,* Huffma nTree;typedef char * Huffma nCode;/赫夫曼算法void Select(HuffmanTree HT, int n, int

4、 &min 1, int &min2)un sig ned int m1,m2;m1=m2=-1;/隨意確定兩個(gè)權(quán)值為最小for(i nt i=1;i<=n ;i+) if(m2!=-1)break;if(HTi.pare nt=O) if(m 1=-1)m仁 HTi.weight;min 1=i; elsem2=HTi.weight;mi n2=i;II找最小權(quán)值for(i nt k=1;k<=n; k+)if(HTk.pare nt=O)int w=HTk.weight; if(k=mini | k=min2)con ti nue;if(w<m2)m2=w

5、;min 2=k;else if(w<mi)m1=w;mi n仁k;void Huffma nCodi ng(Huffma nTree &HT, Huffma nCode & HC, i nt *w, i nt n)w存放n個(gè)字符的權(quán)值(均>0)，構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的赫夫曼編碼HCif(n <=1)return;int m = 2* n-1;HT = (Huffma nTree)malloc(m+1)*sizeof(HTNode);/0號單元未用int i;Huffma nTree p=HT;for(p+,i=1;i<=n ;i+,p+,w

6、+)p->weight = *w;p->pare nt = 0;p->lchild = 0;p->rchild = 0;for(;i<=m;i+,p+)p->weight = 0;p->pare nt = 0;p->lchild = 0;p->rchild = 0;int s1,s2;for(i=n+1;i<=m;i+)建赫夫曼樹/在HT1.i-1選擇pare nt為0且weight最小的兩個(gè)節(jié)點(diǎn)，其序號分別為si和s2Select(HT,i-1,s1,s2);HTs1.pare nt = i;HTs2.pare nt = i;HTi

7、.lchild = si;HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight;/-從葉子到根逆向求每個(gè)字符的赫夫曼編碼-HC = (Huffma nCode)malloc( n+1)*sizeof(char*);char* cd = (char*)malloc( n*sizeof(char);cdn-1='0'int start;for(i=1;i<=n; i+)start = n-1;for(unsigned int c=i,f=HTi.parent;f!=O;c=f,f=HTf.parent)if(HTf.l

8、child = c)cd-start = '0'elsecd-start = '1'HCi = (char*)malloc(n-start)*sizeof(char); 為第 i 個(gè)字符編碼分配空間 strcpy(HCi,&cdstart);free(cd);void mai n()int num;cout<<"請輸入要編碼字符的數(shù)量："；cin»num;char* zifu = new char nu m;cout<<"請輸入要編碼的字符，以空格隔開"<<endl;for(i nt i=0;i <nu m;i+)cin> >zifui;int* qua n=new intnu m;cout<<"請輸入要編碼字符的權(quán)值，以空格隔開"<<endl;for(int i2=0;i2<num;i2+)cin>> qua ni2;Huffma nTree ht;Huffma nCode hc;Huffma nCod in g(ht,hc,qua n,nu m);cout<<"赫夫曼編碼為: