2023年赫夫曼樹實驗報告

實驗報告實驗原理：霍夫曼編碼（HuffmanCoding）是一，種編碼方式，是一種用于無損數(shù)據(jù)壓縮的燃編碼（權編碼）算法。1952年，DavidA.Huffman在麻省理工攻讀博士時所發(fā)明的。在計算機數(shù)據(jù)解決中，霍夫曼編碼使用變長編碼表對源符號（如文獻中的一個字母）進行編碼,其中變長編碼表是通過一種評估來源符號出現(xiàn)機率的方法得到的，出現(xiàn)機率高的字母使用較短的編碼，反之出現(xiàn)機率低的則使用較長的編碼，這便使編碼之后的字符串的平均長度、盼望值減少，從而達成無損壓縮數(shù)據(jù)的目的。例如，在英文中，e的出現(xiàn)機率最高，而z的出現(xiàn)概率則最低。當運用霍夫曼編碼對一篇英文進行壓縮時，e極有也許用一個比特來表達，而z則也許花去25個比特（不是26）。用普通的表達方法時，每個英文字母均占用一個字節(jié)（byte），即8個比特。兩者相比，e使用了一般編碼的1/8的長度,z則使用了3倍多。倘若我們能實現(xiàn)對于英文中各個字母出現(xiàn)概率的較準確的估算，就可以大幅度提高無損壓縮的比例?；舴蚵鼧鋪V稱最優(yōu)二又樹，是一種帶權途徑長度最短的二叉樹。所謂樹的帶權途徑長度，就是樹中所有的葉結點的權值乘上其到根結點的途徑長度（若根結點為（）層,葉結點到根結點的途徑長度為葉結點的層數(shù)）。樹的途徑長度是從樹根到每一結點的途徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln）,N個權值Wi（i=l,2,...n）構成一棵有N個葉結點的二叉樹，相應的葉結點的途徑長度為Li（i=l,2，…n）。可以證明霍夫曼樹的WPL是最小的。實驗目的：本實驗通過編程實現(xiàn)赫夫曼編碼算法,使學生掌握赫夫曼樹的構造方法,理解樹這種數(shù)據(jù)結構的應用價值，并能純熟運用C語言的指針實現(xiàn)構建赫夫些二叉樹，培養(yǎng)理論聯(lián)系實際和自主學習的能力，加強對數(shù)據(jù)結構的原理理解,提高編程水平。實驗內容：(1)實現(xiàn)輸入的英文字符串輸入，并設計算法分別記錄不同字符在該字符串中出現(xiàn)的次數(shù)，字符要區(qū)分大小寫；(2)實現(xiàn)赫夫曼樹的構建算法；(3)遍歷赫夫曼生成每個字符的二進制編碼；(4)顯示輸出每個字母的編碼。七、實驗器材(設備、元器件)：PC機一臺，裝有C語言集成開發(fā)環(huán)境。數(shù)據(jù)結構與程序：include<iostream>include<cctype>usingnamespacestd;typedefstructHuffNode(ntweight;◎struclHuffNode*lchi1d,*rchild,*parent;}HuffNode,*HuffPtr；voidse1ect(HuffPtr,int*,int*,int);voidcreateHuffTree(HuffPtr,int*,int);voidgetCode(HuffPtr,int,int*);void_free(HuffPtr);voidmain()charch;intcount=0;?inlrefer[52]=｛0｝；cout<<nPleaseinput："<<end1；while((ch=getchar())!=1\n')if(isalpha(ch)&&isupper(ch))。?refer[ch-*A'+26]++;seif(isalpha(ch)&&islower(ch))。refer[ch-za*]++;count++;。｝oHuffPtrheader=newHuffNode[2*count-1];ocreateHuffTree(header,refer,count);?getCode(header,count,refer);?>_free(header)；)voidse1ect(HuffPtrheader,int*node1,int*node2,inta11)//選擇權值最小(?staticboo1flag[103]=｛false｝；intmin=al1;ofor(inti=0；i<a1I；i++)if(header[i].weight>0&&header[i].weight<min

&&!flag[i])叫g*node1=i；。。min=header[i].weight;gflag[i]=true;。})min=all;?for(inti=0；i<all；i++)(。if(header!i].weight>0&&header[i].weight<miflag[i1)°{g*node2=i;min=header[i].weight;?flag[ij=true；00}))voidcreateHuffTree(HuffPtrheader,int*refer,intcount)ffmanTree(intnode1,node2;inta11=2*count-1；n&&!〃建Hun&&!〃建Huoif(refer[i])header[i].weight=referLi];gheader[i].1child=header[i].rchi1d=header[i].parent=NULL；0)?for(inti=count;i<aH;i++)6{header[i].weight=0;??header[i].Ichiid=header[i].rchi1d=header[i].parent=NULL;)for(inti=count;i<a1l;i++){gselect(header,&nodel,&node2,a11);aheader[i].weight=header[nodel].weight+header[node2].weight；?header[ij.lchi1d=header+node1；。header[i].rchild=header+node2;header[node1].parent=header[node2J.parent=header+i；))voidgetCode(HuffPtrheader,intcount,int*refer)//獲取字符編碼(intstart;charcode[10]={、()'};HuffPtrp,head;ofor(inti=0;i<count;i++)start=9;ofor(head=header[i].parent,p=header+i;head;p=head,head=head—>parent)。(-if(p==head->lchild)。code[-start]='1';else。ocode[--start]='0z;}oautoch=[](int*refer)mutable->int{gfor(inti=0;i<52;i++).if(refer[i]&&i<26)0001。。orefer[i]=0;^returni+97；)g>elseif(refer[ij&&i>=26)°{?refer[i]=0;。areturni+39；00j00)叩rintf(HTheHuffmanCodeofa1pha%cis:%s\n",ch(refer),code+start);while(code[start])。code[starl++]='\0';e)}void_free(HuftPtrheader)〃釋放分派的空間(ode1eteheader；header=NULL