《數(shù)據(jù)結構》課程設計報告-哈夫曼樹編碼譯碼

數(shù)據(jù)結構課程設計PAGEPAGE1數(shù)據(jù)結構課程設計《數(shù)據(jù)結構》課程設計報告設計題目：__哈夫曼樹編碼譯碼

摘要哈夫曼編/譯器設計：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求這發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在發(fā)送端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道。每端都需要一個完整的編譯碼系統(tǒng)。本程序將為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。哈夫曼編碼/譯碼程序運行步驟：字查找，從英文文章中識別出字符，并把字符插入到一棵二叉排序樹中。哈夫曼樹中序遍歷，是為了把英文文章中的不重復的字符保存起來。哈夫曼編碼，在已經構造好的霍夫曼樹中從每個葉子結點出發(fā)追溯到樹根，逆向找出霍夫曼樹中葉子結點的編碼，規(guī)定：樹中每個結點的左分支標上0,右分支標上1。哈夫曼譯碼利用霍夫曼樹實現(xiàn)對產生的編碼文件的譯碼，譯碼過程為：從根結點出發(fā)，按二進制位串的0或1進入左分支或右分支，當?shù)竭_葉子結點時譯出該葉子對應的單詞或標點符號，若該編碼文件尚未結束，則回到根結點繼續(xù)進行上述過程。運行環(huán)境：windowsXP語言環(huán)境：簡體中文軟件大?。?1KB編寫工具：MicrosoftVisualstudio2008

AbstractInformation:Huffmancodingusedincommunicationcangreatlyimprovethechannelutilization,reducedtransmissiontime,andlowertransmissioncosts.However,thisrequiresthatthesenderthroughacodingsystemforpre-treatmentdata-coding,thetransmitterwillbesentfordecodingdata(recovery).Fordual-channel.Eachsideneedsacompleteencryptionsystem.ThisprocedurewillthisinformationhubsHuffmanwasoneoftheencryptionsystem.Hoffmanncodeforcodingprocedurestorunthestepsand：wordfromenglishinthewordsandpunctuationmarks；andinsertthewords,andpunctuationmarksasecondsortofatree.thetraversalorderhoffmann,toenglisharticlesdonotrepeatthewordsandpunctuationmarks.Hoffmanntreeinordertotraverse;keepthecodehasbeenconstructedinhoffmanngoodhafmantreeleavesfromthestartdatesbacktotabulatetheroots;Hoffmanndecoding;hafmantheimplementationofthecodetothecoding,codingproceduresfor：fromstarttotabulatetherootsofbinaryof0or1totheleftorright,asubdivisionofabranchistotabulatetheleavesoftheleavestranslatethewordsorpunctuationmarks,ifthecodefileisnotfinishedbutistotabulatetheprocessofcontinuing.allthecode,codingproceduresareinthefile.

目錄一、問題描述……………4二、需求分析……………4三、概要設計……………5四、數(shù)據(jù)結構設計………7五、算法設計……………7六、程序測試與實現(xiàn)……9七、調試分析…………12八、心得體會…………12

一、問題描述1、題目內容：利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。試寫一個哈夫曼編/譯碼系統(tǒng)。2、基本要求：一個完整的系統(tǒng)應具有以下功能：（1）初始化。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件中。（2）編碼。利用已建好的哈夫曼樹對文件中的正文進行編碼，然后將結果存入文件中。（3）譯碼。利用已建好的哈夫曼樹將文件中的代碼進行譯碼，結果存入文件中。（4）完成數(shù)據(jù)測試，要求編碼字符不低于15個，編碼文件的長度不低于50個字符。(5)計算平均編碼長度。二、需求分析一個完整的系統(tǒng)應具有以下功能：初始化(Initialization)。從終端讀入字符集大小n，以及n個字符和n個權值，建立赫夫曼樹。對赫夫曼樹初始化。根據(jù)書本算法，對樹進行從葉子到根的逆向求每個字符的赫夫曼編碼。更新赫夫曼樹。編碼(Encoding)。利用已建好的哈夫曼樹正文進行編碼。將終端輸入須要編碼的語句逐字在已建好的赫夫曼樹中查找。當在樹中找到相匹配字符時，將該字符對應的赫夫曼編碼同意保存。③最后將數(shù)組中的編碼在終端輸出。譯碼(Decoding)。利用已建好的哈夫曼樹將文件中的代碼進行譯碼。獲取須要譯碼的編碼組。將編碼逐一讀入，并在赫夫曼中根據(jù)左‘0’右‘1’去查找字符。將譯好的語句在終端輸出。三、概要設計操作集合：voidSelect(intcur,int&r1,int&r2);nodes[1~cur]中選擇雙親為,權值最小的兩個結點r1,r2voidCreatHuffmanTree(charch[],intw[],intn);public:HuffmanTree(charch[],intw[],intn);由字符,權值和字符個數(shù)構造哈夫曼樹virtual~HuffmanTree();析構函數(shù)stringEncode(charch);編碼LinkListDecode(stringstrCode);譯碼本程序主要用到了三個算法。(1)哈夫曼編碼;在初始化過程中間，要用輸入的字符和權值建立哈夫曼樹并求得哈夫曼編碼。先將輸入的字符和權值存放到一個結構體數(shù)組中，建立哈夫曼樹，將計算所得的哈夫曼編碼存儲到另一個結構體數(shù)組中。(2)串的匹配;在編碼過程中間，要對已經編碼過的代碼譯碼，可利用循環(huán)，將代碼中的與哈夫曼編碼的長度相同的串與這個哈夫曼編碼比較，如果相等就回顯。(3)二叉樹的遍歷在印哈夫曼樹(T)的中，因為哈夫曼樹也是二叉樹，所以就要利用二叉樹的先序遍歷將哈夫曼樹輸出。四、數(shù)據(jù)結構設計structNode{chardata;//節(jié)點數(shù)據(jù)域為字符型Node*next;Node(){next=NULL;};Node(charitem,Node*link=NULL){data=item;next=link;};}structHuffmanTreeNode{intweight;unsignedintparent,leftChild,rightChild;//雙親,左右孩子域HuffmanTreeNode();HuffmanTreeNode(intw,intp=0,intlChild=0,intrChild=0);}五、算法設計1、算法分析（必須要用語言進行描述）構造樹:初始化:每個字符就是一個結點，字符的頻度就是結點的權:1、將結點按頻度從小到大排序;2、選取頻度最小的兩個結點，以它們?yōu)閮鹤?，構造出一個新的結點;新結點的權值就是它兩個兒子的權值之和;構造之后，從原來的結點序列里刪除剛才選出的那兩個結點，但同時將新生成的結點加進去;3、如果結點序列里只剩下一個結點，表示構造完畢，退出。否則回到第一步。編碼:編碼：可以假定，對某個結點而言，其左孩子在當前階段的編碼為0，右孩子的編碼為1。這樣就可以通過”樹的遍歷“的方式來生成字長—編碼對照表來到這里，基本上艱苦的已經完成了，對某個具體的字符串編碼和解碼就只是簡單的“查表—替換”的工作了。解碼:解碼也是個簡單的查表、替換過程。如果利用該種編碼發(fā)送字符串，則它的”字寧含—編碼側應表也必須發(fā)送過去，不然對方是不知道怎么解碼的。對給出的一串編碼，從左向右，將編碼組合起來并查表. 2、算法流程圖 結束傳入參數(shù)：結點個數(shù)結束傳入參數(shù)：結點個數(shù)n動態(tài)分配內存，聲明哈夫曼樹HT，并對其值進行初始化建哈夫曼樹，依次在HT[1..i-1]中Selectparent為0且weight最小的兩個結點分配n個字符編碼的頭指針向量和求編碼的工作區(qū)間從葉子到根逆向逐個字符求哈夫曼編碼釋放工作空間開始I<=n?六、程序測試與實現(xiàn)1、函數(shù)之間的調用關系2、主程序intmain(void){char*ch;int*w,n,i;cout<<"輸入字符集中字符的個數(shù)："<<endl;cin>>n;ch=newchar[n];w=newint[n];cout<<"輸入字符集中的字符："<<endl;for(i=0;i<n;i++)cin>>ch[i];cout<<"輸入字符集中的字符的權值："<<endl;for(i=0;i<n;i++)cin>>w[i];HuffmanTreehmTree(ch,w,n);stringstrText,strCode;cout<<"請輸入要編碼的字符串";cin>>strText;cout<<"文本串"<<strText.c_str()<<"編碼為:";for(intpos=0;pos<strText.length();pos++){stringstrTmp=hmTree.Encode(strText[pos]);cout<<strTmp.c_str();}cout<<endl;system("PAUSE");cout<<"請輸入要譯碼的二進制串";cin>>strCode;cout<<"編碼串"<<strCode.c_str()<<"譯碼為:";LinkListlkText=hmTree.Decode(strCode);lkText.Traverse();system("PAUSE");return0;}3、測試數(shù)據(jù) 字符集中字符個數(shù)：15 字符集中的字符：a,b,c,d,e,f,g,h,i,j,k,l,m,n,o 權值：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 要編碼的字符串：abcdefghijklmno4、測試結果 0011100011110011011010110110010101010111100111011110七、調試分析1．鏈表中的結點變量是通過指針變量來訪問的。因為在C++語言中是用P—>來表示P所指的變量，又由于結點類型是一個結構類型，因此可用P—>data和P—>next分別表示結點的數(shù)據(jù)域變量和指針域變量。指針變量的值要么為空(NULL)，不指向任何結點；要么其值為非空，即它的值是一個結點的存儲地址。注意，當P為空值時，則它不指向任何結點，此時不能通過P 來訪問結點，否則會引起程序錯誤。八、心得體會通過這次數(shù)據(jù)結構課程設計，使我對軟件的界面設計有了一個比較深刻的了解，對各種內部排序方法的性能有了清晰的認識，使我感覺到到，一個優(yōu)秀的軟件，不僅僅是可以運行的，更應該具有人性化的界面，協(xié)調的布局，合理的結構，良好的性能和一定的容錯性一個人要完成所有的工作是非常困難和耗時的.在以后的