數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼編碼問題的設(shè)計(jì)和實(shí)現(xiàn)

1、.成績課程設(shè)計(jì)說明書(論文)題 目 哈夫曼編碼問題的設(shè)計(jì)和實(shí)現(xiàn) 課 程 名 稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 院（系、部、中心） 專 業(yè) 班 級(jí) 學(xué) 生 姓 名 學(xué) 號(hào) 設(shè) 計(jì) 地 點(diǎn) 指 導(dǎo) 教 師 設(shè)計(jì)起止時(shí)間：2008 年6月 2日至 2008 年 6月 6 日 目錄1問題描述21.1題目內(nèi)容21.2基本要求21.3測試數(shù)據(jù)22需求分析22.1程序的基本功能22.2輸入值、輸出值以及輸入輸出形式22.3各個(gè)模塊的功能要求33概要設(shè)計(jì)43.1所需的ADT，每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說明（如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫出該存儲(chǔ)結(jié)構(gòu)的定義）43.2主程序流程以及模塊調(diào)用關(guān)系43.3各個(gè)模塊的算法設(shè)計(jì)說明44詳細(xì)設(shè)

2、計(jì)74.1數(shù)據(jù)類型74.2函數(shù)調(diào)用85各個(gè)算法實(shí)現(xiàn)的源程序86調(diào)試分析117使用說明128測試結(jié)果129源程序121 問題描述1.1 題目內(nèi)容 哈夫曼編碼問題的設(shè)計(jì)和實(shí)現(xiàn) 輸入一個(gè)英文字符串，對(duì)該字符串中各字符個(gè)數(shù)進(jìn)行統(tǒng)計(jì)取得各字符的出現(xiàn)次數(shù)；以其出現(xiàn)次數(shù)作為關(guān)鍵字建立哈夫曼樹并進(jìn)行編碼，最后輸出各個(gè)字符對(duì)應(yīng)的碼值。1.2 基本要求要求：設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)、基本算法（主要采用程序流程圖體現(xiàn)）；完成基本算法的實(shí)現(xiàn)代碼；設(shè)計(jì)測試輸入數(shù)據(jù)對(duì)程序進(jìn)行測試，分析輸出結(jié)果數(shù)據(jù)、算法的時(shí)間復(fù)雜度分析，如有改進(jìn)算法則提出算法的改進(jìn)方法。1.3 測試數(shù)據(jù) 測試數(shù)據(jù)三組： AAAABBBCCD(判斷連續(xù)的字符串是否可行

3、) AABBAABCDC(判斷間段的字符串是否可行) AAAA BBBCCD(判斷含空格的字符串是否可行)2 需求分析2.1 程序的基本功能該程序大體上有兩個(gè)功能：1 輸入任何一個(gè)字符串后，該程序能統(tǒng)計(jì)不同字符串的個(gè)數(shù)，并以不同字符串的個(gè)數(shù)作為權(quán)值。2 已知不同字母的權(quán)值，以該權(quán)值作為葉結(jié)點(diǎn)，構(gòu)造一棵帶權(quán)路徑最小的樹，對(duì)該樹從葉結(jié)點(diǎn)到根結(jié)點(diǎn)路徑分支遍歷，經(jīng)過一個(gè)分支就得到一位夫曼編碼值。（規(guī)定哈夫曼樹中的左分支為0，右分支為1，則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過的分支對(duì)應(yīng)的0和1組成的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼）2.2 輸入值、輸出值以及輸入輸出形式輸入值 ：AAAABBBCCD輸出值 ：W =4

4、 C=0 W=3 C=10 W=2 C=111 W=1 C=110輸入值 ：AABBAABCDC輸出值 ：W=4 C=0 W=3 C=10 W=2 C=111 W=1 C=110輸入值 ：AAAA BBBCCD輸出值 ：W=4 C=11 W=1 C=010 W=3 C=10 W=2 C=00 W=1 C=0112.3 各個(gè)模塊的功能要求1 統(tǒng)計(jì)模塊任意輸入一個(gè)字符串，不論字母是否相聯(lián)，字符串中是否含空格都能統(tǒng)計(jì)出不同字母的個(gè)數(shù)。2 建立哈夫曼樹模塊 以統(tǒng)計(jì)的字符串個(gè)數(shù)作為權(quán)值，利用仿真存儲(chǔ)結(jié)構(gòu)，建立帶權(quán)路徑最小的樹。其中對(duì)結(jié)點(diǎn)的存儲(chǔ)需要六個(gè)域，分別是 weight 域，flag域， paren

5、t域，leftChild 域，rightChild域。weight 域是對(duì)權(quán)值的存放，flag 域是一個(gè)標(biāo)志域，flag=0時(shí)表示該結(jié)點(diǎn)尚未加入到哈夫曼樹中，flag=1時(shí)表示該結(jié)點(diǎn)已加入到哈夫曼樹中。3 哈夫曼編碼模塊從哈夫曼樹的葉結(jié)點(diǎn)到根結(jié)點(diǎn)路徑分支逐步遍歷，每經(jīng)過一個(gè)分支就得到一位哈夫曼編碼。哈夫曼編碼也利用仿真存儲(chǔ)結(jié)構(gòu)。4 主函數(shù)模塊從屏幕上輸入字符串，調(diào)用函數(shù)，輸出每個(gè)字母的權(quán)值與編碼。3 概要設(shè)計(jì)3.1 所需的ADT，每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說明（如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫出該存儲(chǔ)結(jié)構(gòu)的定義）抽象數(shù)據(jù)類型集合：在該程序中未用到抽象數(shù)據(jù)類型，主要用到的數(shù)據(jù)類型為 ：int ,char

6、。在哈夫曼樹的建立與哈夫曼樹的編碼中用到仿真存儲(chǔ)3.2 主程序流程以及模塊調(diào)用關(guān)系輸入字符串調(diào)用count 函數(shù)申請(qǐng)內(nèi)存空間調(diào)用 Haffman調(diào)用 HaffmanCode輸出權(quán)值與編碼。3.3 各個(gè)模塊的算法設(shè)計(jì)說明1 主函數(shù)模塊開始 定義初始化變量n>MaxN n y打印n越界HaffmanHaffmanCode輸入i=0i<nj=myHaffCodei.start+1 yJ<n n n輸出n結(jié)束 y輸出權(quán)值i+j+ 主函數(shù)中利用gets輸入一個(gè)字符串，調(diào)用count 函數(shù)統(tǒng)計(jì)不同字母的個(gè)數(shù)，在調(diào)用Haffman 函數(shù)建立哈夫曼樹，然后調(diào)用HaffmanCode函數(shù)進(jìn)行編

7、碼，如果成功，輸出權(quán)值與編碼，否則退出。開始2 統(tǒng)計(jì)函數(shù) i=0,k=0n i<n&&si!=0 ytemp=1 j<n N y j=si&&i!=jweightk+=temp i+ ytemp+ P<n Nj+sp=sp+1n+;j- Yp+結(jié)束統(tǒng)計(jì)函數(shù)在統(tǒng)計(jì)不同字符個(gè)數(shù)時(shí)先利用一個(gè)for循環(huán)遍歷所有的字母，每遍歷一個(gè)不同字母前令temp=1,然后用一個(gè)for循環(huán)將其后的字母與之比較，若相等則temp+,且將該字母從字符串中刪除，否則從下一個(gè)字母遍歷。如此循環(huán)直到字符串結(jié)束。3 Haffman 函數(shù)開始 int i,j,m1,m2,x1,x2

8、i=0i<2*n-1 n i=0haffTreej.weight<m2&&haffTreej.flag=0haffTreei.weight=weightihaffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1haffTreei.rightChild=-1;i<ni<n-1ynhaffTreei.weight=0n結(jié)束 賦值 y J<n+i ni+haffTreej.weight<m1&&haffTreej.flag=0

9、yni+ym2=m1;x2=x1;m1=haffTreej.weight; x1=j;x1=j;j+y賦值Haffman函數(shù)主要以仿真結(jié)構(gòu)存儲(chǔ)信息，開始對(duì)每個(gè)域開始賦值，再根據(jù)不同的情況對(duì)每個(gè)域的值進(jìn)行修改，如此循環(huán)下去，直到每個(gè)域的值修改完全。4 HffmanCode 函數(shù)開始 初始化i<nn結(jié)束parent！=0ynj<nhaffTreeparent.leftChild=childnnycd->bitcd->start=1haffCodei.bitj=cd->bitj;i+haffCodei.start=cd->start haffCodei.weigh

10、t=cd->weight;ycd->bitcd->start=0cd->start-;child=parent;parent=haffTreechild.parent;HaffmanCode 函數(shù)主要以仿真結(jié)構(gòu)存儲(chǔ)信息 ，由葉結(jié)點(diǎn)向根結(jié)點(diǎn)遍歷，從數(shù)據(jù)域start域開始編碼，bit數(shù)組存放編碼，其編碼為0，1序列.。4 詳細(xì)設(shè)計(jì)4.1 數(shù)據(jù)類型 typedef structint weight; /*權(quán)值*/int flag; /*標(biāo)記*/int parent; /*雙親結(jié)點(diǎn)下標(biāo)*/int leftChild; /*左孩子下標(biāo)*/int rightChild; /*右孩子

11、下標(biāo)*/HaffNode; /*哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu)*/typedef structint bitMaxN; /*數(shù)組*/int start; /*編碼的起始下標(biāo)*/int weight; /*字符的權(quán)值*/Code; /*哈夫曼編碼結(jié)構(gòu)*/ int weight16; /*用于存放權(quán)值*/char s30; /* 存放字符串*/主函數(shù)模塊4.2 函數(shù)調(diào)用哈夫曼樹建立函數(shù) 統(tǒng)計(jì)函數(shù)模塊哈夫曼樹編碼函數(shù)5 各個(gè)算法實(shí)現(xiàn)的源程序1.字符串統(tǒng)計(jì)源程序:int count(char * s,int * weight,int n)int i,j,temp,k=0,p;for(i=0;i<n&

12、&si!='0'i+)temp=1;for(j=0;j<n;j+) /*遍歷相同的字母*/if(sj=si&&i!=j)temp+;for(p=j;p<n;p+) /*刪除相同的字母*/sp=sp+1;n-;j-; weightk+=temp; /*temp 作為權(quán)值賦給weight數(shù)組*/return i; /*返回權(quán)值個(gè)數(shù)*/2哈夫曼樹建立源程序void Haffman( int weight,int n,HaffNode haffTree)/*建立葉結(jié)點(diǎn)個(gè)數(shù)為n，權(quán)值數(shù)組為weight的哈夫曼樹haffTree*/int i,j,m1,

13、m2,x1,x2;for(i=0;i<2*n-1;i+)if(i<n)haffTreei.weight=weighti;elsehaffTreei.weight=0;haffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1;/*構(gòu)造哈夫曼樹haffTree的n-1個(gè)非葉結(jié)點(diǎn)*/for(i=0;i<n-1;i+)m1=m2=MaxValue;x1=x2=0;for(j=0;j<n+i;j+)if(haffTreej.weight<m1&&haf

14、fTreej.flag=0)m2=m1;x2=x1;m1=haffTreej.weight;x1=j;elseif(haffTreej.weight<m2&&haffTreej.flag=0)m2=haffTreej.weight;x2=j;/*將找出的兩顆權(quán)值最小的子樹合并為一棵子樹*/haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1;haffTreen+i.weight=haffTreex1.weight+haffTreex2.weight;haffTreen

15、+i.leftChild=x1;haffTreen+i.rightChild=x2; 3哈夫曼樹編碼函數(shù)void HaffmanCode(HaffNode haffTree,int n,Code haffCode)/*由n個(gè)結(jié)點(diǎn)的哈夫曼樹haffTree構(gòu)造哈夫曼編碼haffCode*/ Code *cd=(Code *)malloc(sizeof(Code);int i,j,child,parent;/*求n個(gè)結(jié)點(diǎn)的哈夫曼編碼*/for(i=0;i<n;i+)cd->start=n-1;cd->weight=haffTreei.weight;child=i;parent=h

16、affTreechild.parent;/*由葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)*/while(parent!=0)if(haffTreeparent.leftChild=child)cd->bitcd->start=0; /*左孩子分支編碼0*/elsecd->bitcd->start=1; /*左孩子分支編碼1*/cd->start-;child=parent;parent=haffTreechild.parent;for(j=cd->start+1;j<n;j+)haffCodei.bitj=cd->bitj; /*保存每個(gè)葉結(jié)點(diǎn)的編碼*/haffCod

17、ei.start=cd->start; /*保存不等長編碼的起始位置*/haffCodei.weight=cd->weight; /*保存相應(yīng)字符的權(quán)值*/6 調(diào)試分析 測試數(shù)據(jù)與輸出結(jié)果與2.2結(jié)果相同。對(duì)過函數(shù)的分析：1count 函數(shù):最壞情況下時(shí)間復(fù)雜度為O(n*n*n),調(diào)試時(shí)必須給定字符串的長度，否則會(huì)輸出亂碼，這很不方便。只要在條件語句中加上”si!='0'” ,就能解決。同時(shí)對(duì)入含空格的字符串不能正確統(tǒng)計(jì)，因?yàn)檩斎胱址且詓canf 的形式輸入，scanf 遇到空格自動(dòng)結(jié)束，將scanf 改為gets 即可，出現(xiàn)gets(s);2Haffman函數(shù)

18、在最壞情況下計(jì)算的次數(shù)為2*n-1+(3*n-3)*n/2時(shí)間復(fù)雜度最壞情況下為O(n*n); Haffman函數(shù)在書寫時(shí)要注意定義變量的位置。3HaffmanCode函數(shù)在最壞情況下計(jì)算的次數(shù)為n*(3*n-1),時(shí)間復(fù)雜度為O(n*n); HaffmanCode函數(shù)在書寫時(shí)要注意定義變量的位置。4主函數(shù)的時(shí)間復(fù)雜度又輸入的字符串決定。曾在主函數(shù)中將printf("輸入:n"); get(s),n=count(s,weight,30)放在Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode)前面，

19、出現(xiàn)很多問題，像“HaffNode undefine”,”see undeclear HaffNode”等， 調(diào)整后沒有問題。主函數(shù)的時(shí)間復(fù)雜度由輸入的字符串決定。 算法改進(jìn)設(shè)想：由于統(tǒng)計(jì)函數(shù)時(shí)間復(fù)雜度較高，是否降低其時(shí)間復(fù)雜度?統(tǒng)計(jì)函數(shù)中用到三個(gè)循環(huán)，一個(gè)用于遍歷所有字符，一個(gè)用于尋找相同字符，一個(gè)用于刪除相同字符。而且三個(gè)循環(huán)嵌套，如果能減少循環(huán)的次數(shù)或者是由較少的循環(huán)嵌套，就能降低時(shí)間復(fù)雜度了。7 使用說明在寫源程序前先將所要用到的函數(shù)都寫好，以“haffman.h”保存起來。再書寫主函數(shù)，保存到相同的位置。在vc環(huán)境下，用“Build”里面的“complie”，進(jìn)行編譯 ，運(yùn)行。利用D

20、ebug中的F5,F10,F9,F11設(shè)置斷點(diǎn)等進(jìn)行調(diào)試。8 測試結(jié)果 9 源程序 包含哈夫曼樹和圖，以哈夫曼樹為主要。圖在壓縮文件中 哈夫曼樹#include<stdio.h>#include<stdlib.h>#define MaxValue 10000#define MaxBit 4#define MaxN 10 typedef structint weight; /*權(quán)值*/int flag; /*標(biāo)記*/int parent; /*雙親結(jié)點(diǎn)下標(biāo)*/int leftChild; /*左孩子下標(biāo)*/int rightChild; /*右孩子下標(biāo)*/HaffNode

21、; /*哈夫曼樹的結(jié)點(diǎn)結(jié)構(gòu)*/typedef structint bitMaxN; /*數(shù)組*/int start; /*編碼的起始下標(biāo)*/int weight; /*字符的權(quán)值*/Code; /*哈夫曼編碼結(jié)構(gòu)*/void Haffman( int weight,int n,HaffNode haffTree)/*建立葉結(jié)點(diǎn)個(gè)數(shù)為n，權(quán)值數(shù)組為weight的哈夫曼樹haffTree*/int i,j,m1,m2,x1,x2;for(i=0;i<2*n-1;i+)if(i<n)haffTreei.weight=weighti;elsehaffTreei.weight=0;haffT

22、reei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1;/*構(gòu)造哈夫曼樹haffTree的n-1個(gè)非葉結(jié)點(diǎn)*/for(i=0;i<n-1;i+)m1=m2=MaxValue;x1=x2=0;for(j=0;j<n+i;j+)if(haffTreej.weight<m1&&haffTreej.flag=0)m2=m1;x2=x1;m1=haffTreej.weight;x1=j;elseif(haffTreej.weight<m2&&haff

23、Treej.flag=0)m2=haffTreej.weight;x2=j;/*將找出的兩顆權(quán)值最小的子樹合并為一棵子樹*/haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1;haffTreen+i.weight=haffTreex1.weight+haffTreex2.weight;haffTreen+i.leftChild=x1;haffTreen+i.rightChild=x2;void HaffmanCode(HaffNode haffTree,int n,Code haffCo

24、de)/*由n個(gè)結(jié)點(diǎn)的哈夫曼樹haffTree構(gòu)造哈夫曼編碼haffCode*/ Code *cd=(Code *)malloc(sizeof(Code);int i,j,child,parent;/*求n個(gè)結(jié)點(diǎn)的哈夫曼編碼*/for(i=0;i<n;i+)cd->start=n-1;cd->weight=haffTreei.weight;child=i;parent=haffTreechild.parent;/*由葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)*/while(parent!=0)if(haffTreeparent.leftChild=child)cd->bitcd->start=0; /*左孩子分支編碼0*/elsecd->bitcd->start=1; /*左孩子分支編碼1*/cd->start-;child=parent;parent=haffTreechild.parent;for(j=cd->start+1;j<n;j+)haffCodei.bitj=cd->bitj; /*保存每個(gè)葉結(jié)點(diǎn)的編碼*/haffCodei.start=cd->