數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---- 赫夫曼編碼系統(tǒng)

1、課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)題目 ： 赫夫曼編碼系統(tǒng) 學(xué)生姓名 ： 章建 專 業(yè) ： 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí) ： 1120702學(xué) 號(hào) ： 202120070214指導(dǎo)教師 ： 艾菊梅 2021年 06 月 20 日目 錄1、 設(shè)計(jì)要求-2二、存儲(chǔ)結(jié)構(gòu)-2三、設(shè)計(jì)思想-21、設(shè)計(jì)包含的幾個(gè)局部-22、流程圖-3四、詳細(xì)設(shè)計(jì)-4五、算法復(fù)雜度分析-8六、顯示結(jié)果-9七、心得體會(huì)-11八、附錄：源程序代碼-11一、設(shè)計(jì)要求赫夫曼樹任務(wù) ：建立建立最優(yōu)二叉樹函數(shù) 要求：可以建立函數(shù)輸入二叉樹，實(shí)現(xiàn)赫夫曼樹的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理編碼/解碼功能，直到選擇退出為止。二、存儲(chǔ)結(jié)構(gòu)：在本次課程設(shè)計(jì)中，每

2、一個(gè)字符的信息用一個(gè)結(jié)構(gòu)體存儲(chǔ)，包含結(jié)點(diǎn)值、權(quán)值、雙親結(jié)點(diǎn)、左孩子結(jié)點(diǎn)、右孩子結(jié)點(diǎn)等數(shù)據(jù)。赫夫曼碼和所有字符都是用一個(gè)一維數(shù)組建立存儲(chǔ)的，所以本次課程設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)。三、設(shè)計(jì)思想哈夫曼編譯碼系統(tǒng)的主要功能是先建立哈夫曼樹，然后利用建好的哈夫曼樹生成哈夫曼編碼后進(jìn)行譯碼 。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，稱之為編碼。構(gòu)造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分之代表0，右分支代表1，那么從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)所經(jīng)過的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對(duì)應(yīng)字符的編碼，稱之為哈夫曼編碼。最簡(jiǎn)單的二進(jìn)制編碼方式是等長(zhǎng)編碼。假設(shè)采用不等長(zhǎng)編碼，讓出現(xiàn)頻率高

3、的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，這樣可能縮短傳送電文的總長(zhǎng)度。哈夫曼樹用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。1設(shè)計(jì)包含的幾個(gè)方面： 赫夫曼樹的建立赫夫曼樹的建立由赫夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點(diǎn)的二叉樹。算法的第二步是：將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個(gè)新結(jié)點(diǎn)。顯然要進(jìn)行n1次合并，所以共產(chǎn)生n1個(gè)新結(jié)點(diǎn)，它們都是具有兩個(gè)孩子的分支結(jié)點(diǎn)。由此可知，最終求得的赫夫曼樹中一共有2n1個(gè)結(jié)點(diǎn)，其中n個(gè)結(jié)點(diǎn)是初始森林的n個(gè)孤立結(jié)點(diǎn)。并且赫夫曼樹中沒有度數(shù)為1的分支結(jié)點(diǎn)。我們可以利用一個(gè)大

4、小為2n-1的一維數(shù)組來存儲(chǔ)赫夫曼樹中的結(jié)點(diǎn)。 赫夫曼編碼 要求電文的赫夫曼編碼，必須先定義赫夫曼編碼類型，根據(jù)設(shè)計(jì)要求和實(shí)際需要定義的類型如下： typedet struct char ch; / 存放編碼的字符 char bitsN1; / 存放編碼位串 int len; / 編碼的長(zhǎng)度 CodeNode; / 編碼結(jié)構(gòu)體類型 代碼文件的譯碼 譯碼的根本思想是：讀文件中編碼，并與原先生成的赫夫曼編碼表比擬，遇到相等時(shí)，即取出其對(duì)應(yīng)的字符存入一個(gè)新串中。2其主要流程圖如下圖。開始結(jié)點(diǎn)數(shù)是否大于1將data和權(quán)值賦給ht輸出根結(jié)點(diǎn)和權(quán)值調(diào)用SELECT函數(shù)計(jì)算根結(jié)點(diǎn)函數(shù)父結(jié)點(diǎn)為兩子結(jié)點(diǎn)之和輸出

5、兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn)是否為根結(jié)點(diǎn)？左子是否為空？此時(shí)編碼為0I<2*N?I+編碼為1結(jié)束否否否右子是否為空是是否否是是是四、詳細(xì)設(shè)計(jì)1赫夫曼樹的存儲(chǔ)結(jié)構(gòu)描述為： #define N 50 / 葉子結(jié)點(diǎn)數(shù) #define M 2*N-1 / 赫夫曼樹中結(jié)點(diǎn)總數(shù) typedef struct int weight; / 葉子結(jié)點(diǎn)的權(quán)值 int lchild, rchild, parent; / 左右孩子及雙親指針 HTNode; / 樹中結(jié)點(diǎn)類型 typedef HTNode HuffmanTreeM+1; 哈弗曼樹的算法void CreateHT(HTNode ht,int n) /調(diào)用

6、輸入的數(shù)組ht,和節(jié)點(diǎn)數(shù)n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結(jié)點(diǎn)的相關(guān)域置初值-1 for (i=n;i<2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (

7、htk.weight<min1) /假設(shè)權(quán)值小于最小的左節(jié)點(diǎn)的權(quán)值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.weight=htlnode.weight+htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和 hti.lchild=lnode;hti.rchild=rnode; /父節(jié)點(diǎn)的左節(jié)點(diǎn)和右

8、節(jié)點(diǎn)2哈弗曼編碼void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點(diǎn) hc.cdhc.start-='0' else /處理右孩子結(jié)點(diǎn) hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; /start指向哈夫曼

9、編碼hc.cd中最開始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i<n;i+) /輸出data中的所有數(shù)據(jù)，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf("%c",hcdi.cdk); printf("n"); void

10、editHCode(HTNode ht,HCode hcd,int n) /編碼函數(shù)char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要進(jìn)行編碼的字符串存入string數(shù)組中printf("n輸出編碼結(jié)果:n");for (i=0;stringi!='#'i+) /#為終止標(biāo)志for (j=0;j<n;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號(hào)，相同的就輸出這個(gè)字符的編碼for (k=hcdj.start;k<=n;k+) printf(

11、"%c",hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)3哈弗曼譯碼void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要進(jìn)行譯碼的字符串存入code數(shù)組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)if(c

12、odej=hcdi.cdk) /當(dāng)有相同編碼時(shí)m值加1m+;if(m=j) /當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符串個(gè)數(shù)相等時(shí)那么輸出這個(gè)的data數(shù)據(jù)printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;4主函數(shù)void main() int n=26,i; char orz,back,flag=1; char str='a','b','c','d','e','f&#

13、39;,'g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,

14、57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結(jié)構(gòu)體 HCode hcdN; /建立結(jié)構(gòu)體 for (i=0;i<n;i+) /把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數(shù)，當(dāng)flag為0時(shí)跳出循環(huán) 5顯示局部源程序： printf(" 歡送使用赫夫曼編譯系統(tǒng) n"); printf(" 制作人：章建n"); printf(" *n"); printf(" 1：顯示編碼

15、n "); printf(" 2：進(jìn)行編碼n"); printf(" 3：進(jìn)行譯碼n"); printf(" 0：退出n"); printf(" *n"); printf(" 請(qǐng)輸入選擇的編號(hào):"); scanf("%c",&orz); switch(orz) case '1': system("cls"); /清屏函數(shù) CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht

16、,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case '2': system("cls"); printf("請(qǐng)輸入要進(jìn)行編碼的字符串(以#結(jié)束,字符為小寫英文字母):n"); editHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case '3': system("cl

17、s"); DispHCode(ht,hcd,n); printf("請(qǐng)輸入編碼(以#結(jié)束):n"); deHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case '0': flag=0; printf(" 感謝您的使用！ n"); break; default: system("cls"); 五、算法復(fù)雜度分析：void editHCode(HTNode ht,HCode hcd,

18、int n) /編碼函數(shù)void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)這兩個(gè)被調(diào)函數(shù)里面都用了三重循環(huán)，其他的調(diào)用函數(shù)或者主函數(shù)都是一重或二重循環(huán)，所以算法復(fù)雜度為o(n3)?？梢钥闯龃怂惴ㄐ适潜葦M低的，希望能夠找出更好的算法來減小復(fù)雜度。六、調(diào)試結(jié)果進(jìn)入主菜單選1時(shí)的顯示結(jié)果選擇2時(shí)的顯示結(jié)果選3時(shí)的顯示結(jié)果七、心得體會(huì)通過這次課程設(shè)計(jì)，讓我對(duì)一個(gè)程序的數(shù)據(jù)結(jié)構(gòu)有更全面更進(jìn)一步的認(rèn)識(shí)，根據(jù)不同的需求，采用不同的數(shù)據(jù)存儲(chǔ)方式，不一定要用棧，二叉樹等高級(jí)類型，有時(shí)用根本的一維數(shù)組，只要運(yùn)用得當(dāng)，也能到達(dá)相同的效果，甚至更佳，就如這次的課程設(shè)計(jì)，通過用

19、for的多重循環(huán)，舍棄多余的循環(huán)，提高了程序的運(yùn)行效率。在編寫這個(gè)程序的過程中，我復(fù)習(xí)了之前學(xué)的根本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼及譯碼的應(yīng)用范圍，程序結(jié)構(gòu)算法等一系列的問題它使我對(duì)數(shù)據(jù)結(jié)構(gòu)改變了看法。在這次設(shè)計(jì)過程中，表達(dá)出自己?jiǎn)为?dú)設(shè)計(jì)模具的能力以及綜合運(yùn)用知識(shí)的能力，體會(huì)了學(xué)以致用、突出自己勞動(dòng)成果的喜悅心情，也從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的缺乏和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。八、附錄：源程序代碼源程序如下：#include <stdio.h>#include <stdlib.h> /要用system函數(shù)要調(diào)用的頭文件#include<conio.h> /用

20、getch()要調(diào)用的頭文件#include <string.h>#define N 50 /義用N表示50葉節(jié)點(diǎn)數(shù)#define M 2*N-1 /用M表示節(jié)點(diǎn)總數(shù) 當(dāng)葉節(jié)點(diǎn)數(shù)位n時(shí)總節(jié)點(diǎn)數(shù)為2n-1#define MAXSIZE 100typedef struct char data; /結(jié)點(diǎn)值 int weight; /權(quán)值 int parent; /雙親結(jié)點(diǎn) int lchild; /左孩子結(jié)點(diǎn) int rchild; /右孩子結(jié)點(diǎn)HTNode; typedef struct char cdN; /存放哈夫曼碼 int start; /從start開始讀cd中的哈夫曼碼HC

21、ode;void CreateHT(HTNode ht,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點(diǎn)數(shù)n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結(jié)點(diǎn)的相關(guān)域置初值-1 for (i=n;i<2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-32768-32767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 for (k=0;k<=i-1;k+) i

22、f (htk.parent=-1) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (htk.weight<min1) /假設(shè)權(quán)值小于最小的左節(jié)點(diǎn)的權(quán)值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.weight=htlnode.weight+htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和 hti.lc

23、hild=lnode;hti.rchild=rnode; /父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點(diǎn) hc.cdhc.start-='0' else /處理右孩子結(jié)點(diǎn) hc.cdhc.start-='1' c=f;f=h

24、tf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i<n;i+) /輸出data中的所有數(shù)據(jù)，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf("%c",hcdi.c

25、dk); printf("n"); void editHCode(HTNode ht,HCode hcd,int n) /編碼函數(shù)char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要進(jìn)行編碼的字符串存入string數(shù)組中printf("n輸出編碼結(jié)果:n");for (i=0;stringi!='#'i+) /#為終止標(biāo)志for (j=0;j<n;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號(hào)，相同的就輸出這個(gè)字符的編碼for

26、(k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要進(jìn)行譯碼的字符串存入code數(shù)組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.start,j=0;k<=n;k

27、+,j+) /j為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)if(codej=hcdi.cdk) /當(dāng)有相同編碼時(shí)m值加1m+;if(m=j) /當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符串個(gè)數(shù)相等時(shí)那么輸出這個(gè)的data數(shù)據(jù)printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str='a','b','c','d

28、9;,'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結(jié)構(gòu)體 HCode hcdN; /建立結(jié)構(gòu)體 for (i=0;i<n;i+) /把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數(shù)，當(dāng)flag為0時(shí)跳出循環(huán) printf(&qu