數(shù)據(jù)結(jié)構(gòu)huffman編碼作業(yè)報(bào)告

《數(shù)據(jù)結(jié)構(gòu)huffman編碼作業(yè)報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、哈夫曼編碼與解碼一、設(shè)計(jì)思想在設(shè)計(jì)本程序時(shí)，主要用到的算法有如下三個(gè)：一、創(chuàng)建哈夫曼樹算法；二、求哈夫曼編碼算法；三、求哈夫曼解碼算法。l創(chuàng)建哈夫曼樹算法如下：1)存儲結(jié)構(gòu)：構(gòu)造由信息元素與對應(yīng)的權(quán)值組成的信息元素結(jié)構(gòu)體來存儲已給定的字母與其權(quán)重信息；構(gòu)造由信息元素、權(quán)值、當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)組成的哈夫曼樹結(jié)點(diǎn)結(jié)構(gòu)體來存儲樹結(jié)點(diǎn)的信息，還會(huì)很方便地幫助創(chuàng)建哈夫曼樹；構(gòu)造由信息元素與對應(yīng)的哈夫曼編碼結(jié)構(gòu)體來存儲哈夫曼編碼信息；方便進(jìn)行對數(shù)據(jù)的編碼。2)結(jié)構(gòu)體數(shù)組處理：哈夫曼樹沒有度為1的結(jié)點(diǎn)，若一個(gè)哈夫曼樹由n個(gè)葉子結(jié)點(diǎn)，則該哈夫曼樹共有2n-1

2、個(gè)結(jié)點(diǎn)。應(yīng)用以上的原理，根據(jù)用戶輸入的信息元素的個(gè)數(shù)n開辟大小為2n-1的哈夫曼樹數(shù)組來滿足創(chuàng)建哈夫曼樹的需要，并對此數(shù)組進(jìn)行初始化，葉子結(jié)點(diǎn)的信息元素與權(quán)值即給定的的信息元素與權(quán)值；非葉子結(jié)點(diǎn)的信息元素與權(quán)值設(shè)置為空值；所有哈夫曼樹結(jié)點(diǎn)的父結(jié)點(diǎn)、左結(jié)點(diǎn)、右結(jié)點(diǎn)設(shè)置為0。3)選擇權(quán)值最小與次?。涸谶M(jìn)行比較的過程中循環(huán)取出權(quán)值進(jìn)行比較，設(shè)置兩個(gè)s1，s2分別記錄本次循環(huán)最小與次小的權(quán)值，進(jìn)行下一次的比較選擇。返回權(quán)值最小與次小的哈夫曼樹結(jié)點(diǎn)信息。4)生成小樹：應(yīng)用3)中想法，在用戶輸入的信息元素中選擇權(quán)值中最小與次小的元素分別賦值給右葉子結(jié)點(diǎn)與左葉子結(jié)點(diǎn)，并

3、把這兩個(gè)權(quán)值之和賦值給這兩個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，記錄父結(jié)點(diǎn)位置。5)生成哈夫曼樹：再應(yīng)用3)4)把這些小樹的父結(jié)點(diǎn)的權(quán)值進(jìn)行比較選擇，選擇權(quán)值比較大的設(shè)置為新的右結(jié)點(diǎn)的權(quán)值，權(quán)值比較小的設(shè)置為左結(jié)點(diǎn)，把這兩個(gè)權(quán)值的和賦值給新的父結(jié)點(diǎn)；以此重復(fù)進(jìn)行，最終生成哈夫曼樹。l求哈夫曼編碼算法如下1)采用無棧非遞歸遍歷哈夫曼樹：每次站在根結(jié)點(diǎn)遍歷哈夫曼樹，直至到達(dá)某一個(gè)葉子結(jié)點(diǎn)為止，并臨時(shí)用一個(gè)數(shù)組記錄遍歷過程中每個(gè)結(jié)點(diǎn)的狀態(tài)。編碼完成后再復(fù)制給哈夫曼編碼結(jié)構(gòu)體中的編碼數(shù)組。2)-10-哈夫曼編碼與解碼遍歷與編碼：在邏輯上，遍歷時(shí)向左子時(shí)，編碼為0，向右子為1，將每次的結(jié)

4、點(diǎn)狀態(tài)記錄連接即哈夫曼編碼；站在根結(jié)點(diǎn)上，若到左子上記錄此時(shí)的結(jié)點(diǎn)狀態(tài)為0，并把指針指向左子，進(jìn)行下一次的遍歷，若到右結(jié)點(diǎn)上記錄此時(shí)的結(jié)點(diǎn)狀態(tài)1，并把指針指向右子，進(jìn)行下一次的判斷遍歷；重復(fù)進(jìn)行，到達(dá)某一個(gè)葉子結(jié)點(diǎn)為止，完畢后，將每次遍歷的結(jié)點(diǎn)狀態(tài)標(biāo)志進(jìn)行連接組成臨時(shí)狀態(tài)數(shù)組；將此葉子結(jié)點(diǎn)的元素信息作為哈夫曼編碼的信息元素，把遍歷時(shí)的狀態(tài)數(shù)組賦值給哈夫曼編碼結(jié)構(gòu)體的編碼。由此，經(jīng)遍歷哈夫曼樹所形成的哈夫曼編碼數(shù)組就是通信中的簡單碼表。1)輸出01編碼：讀入指定文件中的信息后要求輸出01編碼，在此過程中，要對每個(gè)字符進(jìn)行掃描，并輸出01編碼。重復(fù)進(jìn)行，每次都

5、無間隔輸出，最后所形成的01串就是用戶所需要的01編碼信息。并將結(jié)果寫入指定文件。l求哈夫曼解碼算法：1)前提：哈夫曼解碼是哈夫曼編碼的逆運(yùn)算，因此哈夫曼解碼需要用哈夫曼編碼時(shí)的哈夫曼樹。2)哈夫曼解碼：從文件中獲得已進(jìn)行編碼的哈夫曼碼，因?yàn)?1編碼串中僅0與1兩種符號，當(dāng)是1時(shí)去左子結(jié)點(diǎn)上，當(dāng)是0時(shí)去右結(jié)點(diǎn)。在解碼時(shí)，每次均需要站在根結(jié)點(diǎn)上，在對01碼進(jìn)行依次掃描時(shí)，遇到1就去左子結(jié)點(diǎn)，遇到0就去右結(jié)點(diǎn)，直至到達(dá)葉子結(jié)點(diǎn)上結(jié)束。再次站到根結(jié)點(diǎn)上，繼續(xù)進(jìn)行；每次到達(dá)結(jié)點(diǎn)上，就輸出此結(jié)點(diǎn)上的信息元素，因?yàn)橹挥腥~子結(jié)點(diǎn)上有信息元素，而其他結(jié)點(diǎn)上的信息元素為空值

6、，則在輸出時(shí)，僅僅是所需要的明文信息。二、算法流程圖下圖為哈夫曼樹的生成過程中的主要算法（如圖1）：圖1生成哈夫曼樹-10-哈夫曼編碼與解碼下面是哈夫曼編碼過程的大致過程（如圖2）：圖2為huffman樹的各節(jié)點(diǎn)進(jìn)行編碼下面是對指定文件內(nèi)信息編碼的大致過程（如圖3）：圖3信息的編碼-10-哈夫曼編碼與解碼下面是對文件內(nèi)信息解碼碼的大致過程（如圖4）：圖4信息的解碼三、源代碼#include"stdio.h"#include"string.h"#include"stdlib.h"typedefstruct/*聲明儲存信息的結(jié)構(gòu)體*/{charletter;/

7、*字母*/intweight;/*權(quán)值*/intparent;/*父節(jié)點(diǎn)*/intlchild;/*左子節(jié)點(diǎn)*/intrchild;/*右子節(jié)點(diǎn)*/}htnode,*huffmantree;typedefchar**huffmancode;voidselect(huffmantree&ht,inti,int&s1,int&s2)-10-哈夫曼編碼與解碼{intj,k;/*找出第一個(gè)單節(jié)點(diǎn)樹*/for(k=1;k<=i;k++){if(ht[k].parent!=0){continue;}s1=k;break;}/*找出其中權(quán)重最小的樹*/for(j=1;j

8、<=i;j++){if(ht[j].parent!=0){cont