哈弗曼編碼譯碼器

1、哈夫曼編碼/譯碼器 課 程 設(shè) 計哈夫曼編碼/譯碼器系 別 ：專業(yè)（班級）：作者（學(xué)號）：指導(dǎo)教師：完成日期： 27目 錄 1 項目研究背景與意義31.1項目研究背景31.2項目研究意義32 需求分析42.1設(shè)計要求與分析42.2 基本要求43 概要設(shè)計53.1系統(tǒng)功能模塊圖53.2主要功能函數(shù)54詳細設(shè)計64.1數(shù)據(jù)結(jié)構(gòu)的定義64.1.1宏定義64.1.2 huffman樹的結(jié)點結(jié)構(gòu)64.1.3 huffman編碼結(jié)構(gòu)64.1.4 字符及其編碼的結(jié)構(gòu)64.2建立哈夫曼樹74.2.1基本原理74.2.2構(gòu)造思想74.2.3具體構(gòu)造方法84.2.4建立huffuman樹函數(shù)94.3建立huffm

2、an編碼114.3.1構(gòu)造思想114.3.2建立huffman編碼函數(shù)114.4輸出huffman編碼函數(shù)124.5對字符串進行編碼124.5.1構(gòu)造思想124.5.2字符串編碼函數(shù)134.6將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt中)的程序185 調(diào)試分析195.1輸出huffman編碼，即空格和26個大寫字母的界面。195.2對字符串進行編碼的界面195.3將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt) 的界面196總結(jié)20參考文獻21附錄源代碼221 項目研究背景與意義1.1項目研究背景在科技飛速發(fā)展的今天，信息傳輸顯得尤為重要，這主要體現(xiàn)在計算機之間的數(shù)據(jù)傳輸，主要包括

3、文字，聲音，圖像，視頻等文件的傳輸，而計算機不能直接處理這些信息，計算機只能識別二進制數(shù)據(jù)。例如文字，在數(shù)據(jù)通訊中，傳送方要將傳送的文字轉(zhuǎn)換成由二進制字符0、1組成的二進制串，而接受方要將二進制字符0、1組成的二進制串還原成對應(yīng)的文字形式。于是便完成了文字數(shù)據(jù)的傳輸過程。時下，數(shù)據(jù)結(jié)構(gòu)是一門隨著計算機科學(xué)的發(fā)展而逐漸形成的新興學(xué)科。隨著計算機技術(shù)的發(fā)展，計算機的應(yīng)用領(lǐng)域從最初的科學(xué)計算發(fā)展到人類社會的各個領(lǐng)域，計算機處理的對象也由純粹的數(shù)值發(fā)展到字符、表格、圖像和聲音等各種具有一定結(jié)構(gòu)的數(shù)據(jù)，這就給程序設(shè)計帶來一些新的問題。與飛速發(fā)展的計算機硬件相比，計算機軟件的發(fā)展相對緩慢。研究數(shù)據(jù)結(jié)構(gòu)可以

4、解決計算機之間的數(shù)據(jù)傳輸效率低下的問題。在數(shù)據(jù)結(jié)構(gòu)中，研究樹形結(jié)構(gòu)對數(shù)據(jù)編碼有很大作用，對數(shù)據(jù)構(gòu)造二叉樹編碼應(yīng)用廣泛。1.2項目研究意義本設(shè)計旨在解決數(shù)據(jù)通訊中傳輸字符過長的問題，哈夫曼編碼能很好地解決這個問題。哈夫曼編碼是根據(jù)哈夫曼算法夠造的哈夫曼樹所得到的，哈夫曼算法使得編碼總長度最小。哈夫曼編碼的理論依據(jù)是變長編碼理論，將使用次數(shù)多的代碼轉(zhuǎn)換成長度較短的代碼，而是用次數(shù)少的可以使用較長的編碼，并且保持編碼的唯一可解性。利用哈夫曼編碼進行信息通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。2 需求分析2.1設(shè)計要求與分析在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件

5、的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。哈夫曼樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應(yīng)的字符的編碼，這就是哈夫曼編碼。假設(shè)每種字符在字符中出現(xiàn)的次數(shù)為Wi，編碼長度為Li,字符中有n 種字符，則字符編碼總長為WiLi。若將此對應(yīng)到二叉樹上，Wi為葉節(jié)點的權(quán)，Li為根節(jié)點到葉節(jié)點的路徑長度。那么，WiLi恰好為二叉樹上帶權(quán)路徑長

6、度。2.2 基本要求設(shè)計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項目，直到選擇退出為止。 1將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中) 2采用靜態(tài)存儲結(jié)構(gòu) 3初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹； 4編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 5輸出編碼； 6設(shè)字符集及頻度如下表： 字符 空格 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1

7、48 51 80 23 8 18 1 16 13 概要設(shè)計3.1系統(tǒng)功能模塊圖哈夫曼編碼/譯碼器 找權(quán)值最小的2個結(jié)點輸出哈夫曼編碼建立哈夫曼編碼對字符串進行編 碼建立哈夫曼樹 圖3-1系統(tǒng)功能模塊圖3.2主要功能函數(shù)main函數(shù)中調(diào)用了5個主要功能函數(shù)，即1建立huffuman樹函數(shù):void sethfmtree ( )2找權(quán)值最小的2個結(jié)點函數(shù): void select(int s);3建立huffman編碼函數(shù)：void sethfmcode( )4輸出huffman編碼函數(shù)：void printhfmcode() 5對字符串進行編碼函數(shù)：void setcode ()其函數(shù)調(diào)用關(guān)系如

8、圖3-2所示。sethfmcodesethfmtreemain函數(shù)setcodeprinthfmcode 圖3-2函數(shù)調(diào)用關(guān)系圖4詳細設(shè)計4.1數(shù)據(jù)結(jié)構(gòu)的定義4.1.1宏定義1 定義了N為27，表示27個字符,即空格和26個大寫字母#define N 27 2 定義了M為2*N1，表示huffman樹的結(jié)點個數(shù) #define M 2*N-1 3 定義了maxnumber為一個很大的數(shù)#define maxnumber 10000 4.1.2 huffman樹的結(jié)點結(jié)構(gòu)struct node int weight; /結(jié)點權(quán)值 int parent,lchild,rchild; /雙親，左孩子

9、，右孩子;4.1.3 huffman編碼結(jié)構(gòu)struct codetype int start; /起始位置 char codesN+1; /存放哈夫曼編碼的數(shù)組;4.1.4 字符及其編碼的結(jié)構(gòu)struct element char character; /字符 struct codetype code; /字符編碼; 4.2建立哈夫曼樹4.2.1基本原理哈夫曼在上世紀(jì)五十年代初提出這種編碼時，根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。它是一種變長的編碼。在編碼中，若各碼字長度嚴格按照碼字所對應(yīng)符號出現(xiàn)概率的大小的逆序排列，則編碼的平均長度是最小的。（注：碼字即為符號經(jīng)哈夫曼編碼后得到的編碼

10、，其長度是因符號出現(xiàn)的概率而不同，所以說哈夫曼編碼是變長的編碼。）一般而言，給定n個實數(shù)w1，w2，wn（n），求一個具有n個結(jié)點的二叉數(shù)，使其帶權(quán)路徑長度最小。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度（若根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù)）。樹的帶權(quán)路徑長度記為WPL=(W1*L1+W2*L2+ W3*L3+.+Wn*Ln)，N個權(quán)值Wi(i=1,2,.n)構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為Li(i=1,2,.n)。可以證明哈夫曼樹的WPL是最小的。4.2.2構(gòu)造思想由哈夫曼算法的定義可知，初始森林中共有n棵只含有根節(jié)點的

11、二叉樹。算法的第二步是：將當(dāng)前森林中的兩棵根節(jié)點權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個新結(jié)點。顯然要進行n-1次合并，所以共產(chǎn)生n-1個新結(jié)點，它們都是具有兩個孩子的分支結(jié)點。由此可知，最終求得的哈夫曼樹中一共有2n-1個結(jié)點，其中n個葉節(jié)點是初始森林的n個孤立節(jié)點。并且哈夫曼樹中沒有度數(shù)為1的分支結(jié)點。我們可用一個大小為2n-1的一維數(shù)組來存儲哈夫曼樹中的結(jié)點。要實現(xiàn)哈夫曼樹算法，首先要實現(xiàn)在hfmcodes中選擇parent為0且權(quán)值最小的兩個根結(jié)點的選擇算法。4.2.3具體構(gòu)造方法 1首先根據(jù)給定的權(quán)值構(gòu)造n棵二叉樹的森林，其中每個二叉樹都只有一

12、個權(quán)值為treeweighti的根節(jié)點2在森林中選取兩個權(quán)值最小的根節(jié)點作為一個新二叉樹的左右結(jié)點其具體函數(shù)為:void select(int s) /找權(quán)值最小的2個結(jié)點 int i; int v1,v2; v1=v2=maxnumber; x1=x2=0; for(i=1;i<=s;i+) if(treei.parent=0) if(treei.weight<v1) v2=v1； x2=x1; v1=treei.weight; x1=i; else if(treei.weight<v2) v2=treei.weight; x2=i; 通過遍歷所有節(jié)點找到權(quán)值最小的結(jié)點3設(shè)

13、新二叉樹的根節(jié)點為左右子結(jié)點的權(quán)值和其函數(shù)表達為 for(i=N+1;i<=M;i+) /找權(quán)值最小的2個結(jié)點，組成huffman樹 select(i-1); /調(diào)用找權(quán)值最小的2個結(jié)點函數(shù) treex1.parent=i; treex2.parent=i; treei.lchild=x1; treei.rchild=x2; treei.weight=treex1.weight+treex2.weight; 4從森林中刪除選中的那兩棵二叉樹，同時加入新構(gòu)造的那個二叉樹5重復(fù)上述步驟，得到所需的哈夫曼二叉樹4.2.4建立huffuman樹函數(shù)void sethfmtree() /建立huf

14、fuman樹 int i,j; int treeweightN=186,63,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1; char hfmcodeschN= ' ','A','B','C','D','E','F','G','H','I','J','K','L','M','

15、;N','O','P','Q','R','S','T','U','V','W','X','Y','Z' for(i=1;i<=M;i+) /初始化雙親，左右孩子結(jié)點為0 treei.parent=treei.lchild=treei.rchild=0; for(i=1;i<=N+1;i+) /初始化27個字符及其權(quán)值 hfmcodesi.ch=hfmcodeschi-1;/ hfmco

16、desN+1 n個結(jié)點的huffman編碼表 treei.weight=treeweighti-1; for(i=N+1;i<=M;i+) /找權(quán)值最小的2個結(jié)點，組成huffman樹 select(i-1); /調(diào)用找權(quán)值最小的2個結(jié)點函數(shù) treex1.parent=i; treex2.parent=i; treei.lchild=x1; treei.rchild=x2; treei.weight=treex1.weight+treex2.weight; void select(int s) /找權(quán)值最小的2個結(jié)點 int i; int v1,v2; v1=v2=maxnumber;

17、 x1=x2=0; for(i=1;i<=s;i+) if(treei.parent=0) if(treei.weight<v1) v2=v1; x2=x1; v1=treei.weight; x1=i; else if(treei.weight<v2) v2=treei.weight; x2=i; 4.3建立huffman編碼4.3.1構(gòu)造思想 給定字符集的哈夫曼樹生成后，求哈夫曼編碼的具體實現(xiàn)過程是：依次以葉子為出發(fā)點，向上回溯至根為止。上溯時走左分支則生成代碼0，走右分支則生成代碼1。4.3.2建立huffman編碼函數(shù) void sethfmcode() int i,

18、s,f,k=1; struct codetype c; for(i=1;i<=N;i+) c=hfmcodesi.code; c.start=N+1; s=i; f=trees.parent; do c.start-; if(s=treef.lchild) c.codesc.start='0' else c.codesc.start='1' s=f; f=trees.parent; while(f); hfmcodesi.code=c; 4.4輸出huffman編碼函數(shù)void printhfmcode() /輸出huffman編碼，即空格和26個大寫字母

19、 int i,j; struct codetype c; printf("哈夫曼的編碼為：n"); for(i=1;i<=N;i+) printf("%c:",hfmcodesi.character); c=hfmcodesi.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf("n"); printf("nn-nn");4.5對字符串進行編碼4.5.1構(gòu)造思想 由于生成的編碼與要求的編碼反序，將生成的代碼先從后往前依

20、次存放在一個臨時向量中，并設(shè)一個指針start指示編碼在該向量中的起始位置（start初始時指示向量的結(jié)束位置）。 當(dāng)某字符編碼完成時，從臨時向量的start處將編碼復(fù)制到該字符相應(yīng)的位串hfmchars中即可。 因為字符集大小為n，故變長編碼的長度不會超過n，加上一個結(jié)束符'0'，hfmchars的大小應(yīng)為n+1。4.5.2字符串編碼函數(shù) void setcode() /對字符串進行編碼 int i,j,count; char c0,k='Y' struct codetype c; while(k='Y') /利用循環(huán)，實現(xiàn)對字符串多次編碼 p

21、rintf("nn請輸入字符串（大寫字母和空格,不多于1000個字符），輸入'.'(+回車)號結(jié)束nn"); for(i=1;i<=100;i+) /利用循環(huán)，實現(xiàn)對字符串輸入 c0=getchar(); ti.character=c0; if(c0='.') break; count=i; /記錄字符串個數(shù) printf("nn-nn"); printf("nn字符串編碼為：nn"); for(i=1;i<=count;i+) /利用循環(huán)，實現(xiàn)對字符串輸出 if(ti.character=

22、'.')break; else switch(ti.character) /利用開關(guān)語句，查找編碼 case ' ': c=hfmcodes1.code; for(j=c.start;j<=N;j+) /輸出編碼 printf("%C",c.codesj); printf(" "); break; case 'A': c=hfmcodes2.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" &q

23、uot;); break; case 'B': c=hfmcodes3.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'C': c=hfmcodes4.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'D': c=hfmcodes5.code;

24、for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'E': c=hfmcodes6.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf發(fā) printf("%c",c.codesj); printf(" "); break; case 'M': c=hfmcodes14.code; for(j=c.

25、start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'N': c=hfmcodes15.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'O': c=hfmcodes16.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj

26、); printf(" "); break; case 'P': c=hfmcodes17.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'Q': c=hfmcodes18.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'R'

27、;: c=hfmcodes19.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'S': c=hfmcodes20.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'T': c=hfmcodes21.code; for(j=c.start;j<=N;j+)

28、printf("%c",c.codesj); printf(" "); break; case 'U': c=hfmcodes22.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'V': c=hfmcodes23.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" &

29、quot;); break; case 'W': c=hfmcodes24.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'X': c=hfmcodes25.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'Y': c=hfmcodes26.co

30、de; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; case 'Z': c=hfmcodes27.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf(" "); break; default: printf(" *此編碼找不到，請檢查輸入是否正確* "); printf("nnn-nn"); pr

31、intf("nnn- 是否繼續(xù)?(Y/N) Y表示繼續(xù)，N表示不繼續(xù) -n"); getchar(); printf("n"); scanf("%c",&k); getchar(); printf("nn*nn"); 4.6將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt中)的程序 5 調(diào)試分析5.1輸出huffman編碼，即空格和26個大寫字母的界面。圖5-1輸出huffman編碼5.2對字符串進行編碼的界面圖5-2字符串編碼5.3將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt) 的界面 圖5-3存

32、放數(shù)據(jù)文件(文件名為data.txt) 6總結(jié)參考文獻1 嚴蔚敏.數(shù)據(jù)結(jié)構(gòu).C語言版.清華大學(xué)出版社 .20132 嚴蔚敏等.數(shù)據(jù)結(jié)構(gòu)題集.C語言版. 清華大學(xué)出版社 .20133 曲建民,劉元紅,鄭陶然 .數(shù)據(jù)結(jié)構(gòu).C語言版.清華大學(xué)出版社.2005 4 李春葆 編著數(shù)據(jù)結(jié)構(gòu)教程清化大學(xué)出版社 . 20055 蔣立翔 編著C+程序設(shè)計技能百練中國鐵道出版社.2004附錄源代碼#include <string.h>#include <stdio.h>#include <stdlib.h>#define N 27 /空格和26個大寫字母#define M 2*

33、N-1#define maxnumber 10000struct node /huffman樹的結(jié)點結(jié)構(gòu) int weight; /結(jié)點權(quán)值 int parent,lchild,rchild; /雙親，左孩子，右孩子;struct codetype /huffman編碼結(jié)構(gòu) int start; /起始位置 char codesN+1; /存放哈夫曼編碼的數(shù)組;struct element /字符及其編碼的結(jié)構(gòu) char character; /字符 struct codetype code; /字符編碼;struct node treeM+1; /n個結(jié)點的huffman樹struct el

34、ement hfmcodesN+1,hfmchars1000; /n個結(jié)點的huffman編碼表，字符串編碼int x1,x2;void sethfmtree(); /有關(guān)函數(shù)聲明void select(int s);void sethfmcode();void setcode();void printhfmcode();void main() /主函數(shù) sethfmtree(); /建立huffuman樹 sethfmcode(); /建立huffman編碼 printhfmcode(); /輸出huffman編碼，即空格和26個大寫字母 setcode(); /對字符串進行編碼 print

35、f("nn");void sethfmtree() /建立huffuman樹 int i,j; int treeweightN=186,63,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1; char hfmcodescharacterN= ' ','A','B','C','D','E','F','G','H','I',

36、9;J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' for(i=1;i<=M;i+) /初始化雙親，左右孩子結(jié)點為0 treei.parent=treei.lchild=treei.rchild=0; for(i=1;i<=N+1;i+)

37、 /初始化27個字符及其權(quán)值 hfmcodesi.character=hfmcodescharacteri-1; treei.weight=treeweighti-1; for(i=N+1;i<=M;i+) /找權(quán)值最小的2個結(jié)點，組成huffman樹 select(i-1); /調(diào)用找權(quán)值最小的2個結(jié)點函數(shù) treex1.parent=i; treex2.parent=i; treei.lchild=x1; treei.rchild=x2; treei.weight=treex1.weight+treex2.weight; void select(int s) /找權(quán)值最小的2個結(jié)點

38、int i; int v1,v2; v1=v2=maxnumber; x1=x2=0; for(i=1;i<=s;i+) if(treei.parent=0) if(treei.weight<v1) v2=v1； x2=x1; v1=treei.weight; x1=i; else if(treei.weight<v2) v2=treei.weight; x2=i; void sethfmcode() /建立huffman編碼 int i,s,f,k=1; struct codetype c; for(i=1;i<=N;i+) c=hfmcodesi.code; c.s

39、tart=N+1; s=i; f=trees.parent; do c.start-; if(s=treef.lchild) c.codesc.start='0' else c.codesc.start='1' s=f; f=trees.parent; while(f); hfmcodesi.code=c; void printhfmcode() /輸出huffman編碼，即空格+26個大寫字母 int i,j; struct codetype c; printf("哈夫曼的編碼為：n"); for(i=1;i<=N;i+) print

40、f("%c:",hfmcodesi.character); c=hfmcodesi.code; for(j=c.start;j<=N;j+) printf("%c",c.codesj); printf("n"); printf("nn-nn");void setcode() /對字符串進行編碼 int i,j,count; char c0,k='Y' struct codetype c; while(k='Y') /利用循環(huán)，實現(xiàn)對字符串多次編碼 printf("nn請輸入字符串（大寫字母+空格,不大于100個字符），輸入'.'(+回車)號結(jié)束nn"); for(i=1;i<=100;i+) /利用循環(huán)，實現(xiàn)對字符串輸入 c0=getchar(); ti.characte