西工大數(shù)據(jù)結(jié)構(gòu)報告 哈夫曼樹編碼譯碼_第1頁
西工大數(shù)據(jù)結(jié)構(gòu)報告 哈夫曼樹編碼譯碼_第2頁
西工大數(shù)據(jù)結(jié)構(gòu)報告 哈夫曼樹編碼譯碼_第3頁
西工大數(shù)據(jù)結(jié)構(gòu)報告 哈夫曼樹編碼譯碼_第4頁
西工大數(shù)據(jù)結(jié)構(gòu)報告 哈夫曼樹編碼譯碼_第5頁
已閱讀5頁,還剩11頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、數(shù)據(jù)結(jié)構(gòu)實驗報告一實驗題目編寫一個程序,實現(xiàn)哈夫曼樹的編碼和譯碼。二程序設(shè)計 (一) 需求分析1需要編寫這樣一個程序,有以下功能:(1)能夠輸出不同英文字母所代表的權(quán)值;(2)能夠根據(jù)輸入結(jié)點的字母的權(quán)值,生成哈夫曼樹,并得到每個結(jié)點的哈夫曼編碼;(3)能夠在功能2的基礎(chǔ)上,將輸入的哈夫曼編碼翻譯為字母。2.程序運行步驟:(1)開始;(2)選擇要實現(xiàn)的運算:1.輸出字母與權(quán)值的對應(yīng)關(guān)系表 2.將字符編譯為哈夫曼樹 3.將哈夫曼樹譯碼;(3)選擇運算后,程序輸出運算結(jié)果;(4)結(jié)束。(二)概要設(shè)計程序模塊及思想:1.主函數(shù)主函數(shù)包括定義變量和算法兩部分。算法由switch-case結(jié)構(gòu)構(gòu)成。Ca

2、se有三種情況:(1) 輸出權(quán)值表;(2) 哈夫曼樹的編碼:(1) 輸入要編碼的字母;(2) 以表格形式輸出哈夫曼樹;(3) 輸出每個字符的哈夫曼編碼;(4) 結(jié)束;(3) 哈弗曼樹的譯碼:(1) 建立哈夫曼樹:(1)輸入要編碼的字母;(2)以表格形式輸出哈夫曼樹;(3)輸出每個字符的哈夫曼編碼;(4)結(jié)束; (2) 將哈夫曼編碼翻譯為字母: (1)輸入哈弗曼編碼; (2)輸出翻譯結(jié)果; (3)結(jié)束;(3)結(jié)束。2基本操作。typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; 操作結(jié)果:動態(tài)分配數(shù)組儲

3、存哈夫曼樹。typedef char *HuffmanCode;操作結(jié)果:動態(tài)分配數(shù)組儲存哈夫曼編碼表。void Error(char *message);操作結(jié)果:輸出錯誤的原因。void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n); 操作結(jié)果:對字母進(jìn)行哈夫曼樹的編碼。void Select(HuffmanTree &HT, int n,int *s1,int *s2);操作結(jié)果:選擇多個節(jié)點中權(quán)值最小的兩個結(jié)點 void Decoding(HuffmanTree HT,char Ch,

4、char letter,int n);操作結(jié)果:將存在在已知哈夫曼樹中的哈夫曼編碼翻譯為字母。(三)詳細(xì)設(shè)計1結(jié)構(gòu)體定義typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; 操作結(jié)果:動態(tài)分配數(shù)組儲存哈夫曼樹。typedef char *HuffmanCode;操作結(jié)果:動態(tài)分配數(shù)組儲存哈夫曼編碼表。2.每個模塊的分析:(1) 主程序模塊:int main() HuffmanTree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,j,n,a; cha

5、r letter100,code500; /初始化 char 、str1='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V'

6、,'W','X','Y','Z', str2='a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','

7、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; /權(quán)值表 printf("請選擇要進(jìn)行的操作:1.顯示權(quán)值表 2.將字符編碼 3.翻譯哈夫曼碼 n"); scanf("%d",&a); switch(a) case 1: for(i=1;i<=26;i+) /輸出權(quán)值表 printf(&q

8、uot;%c %c %dtt",str1i-1,str2i-1,fnumi-1); printf("n");break; case 2: printf("請輸入要編碼的電文:n"); scanf("n"); gets(letter); n=strlen(letter); w=( int *)malloc(n+1)*sizeof( int *); /創(chuàng)建n+1個單元儲存字母的權(quán)值 w0=0; for(i=1;i<=n;i+) if(letteri-1>64 && letteri-1<91) j

9、=1; while (letteri-1!=str1j-1) +j; wi=fnumj-1; /w儲存每個字母的權(quán)值if(letteri-1>96 && letteri-1<123)j=1;while (letteri-1!=str2j-1) +j; wi=fnumj-1; /w儲存每個字母的權(quán)值 HuffmanCoding(HT,HC,w,n); /建立哈夫曼樹,并輸出 printf("HuffmanCode如下所示:n"); printf("NumberttLetterttWeightttCoden"); for(i=1;

10、i<=n;i+) /依次輸出編號,字母,權(quán)值,和哈夫曼編碼 printf("%dtt",i); printf("%ctt",letteri-1); printf("%dtt%sn",wi,HCi); / printf("n"); break; case 3: printf("先輸入一個拉丁字符串:n"); scanf("n"); gets(letter); n=strlen(letter); w=( int *)malloc(n+1)*sizeof( int *); /

11、創(chuàng)建n+1個單元儲存字母的權(quán)值 w0=0; for(i=1;i<=n;i+) if(letteri-1>64 && letteri-1<91) j=1; while (letteri-1!=str1j-1) +j; wi=fnumj-1; /w儲存每個字母的權(quán)值 if(letteri-1>96 && letteri-1<123)j=1;while (letteri-1!=str2j-1) +j; wi=fnumj-1; /w儲存每個字母的權(quán)值 HuffmanCoding(HT,HC,w,n); /建立哈夫曼樹,并輸出 printf(

12、"HuffmanCode如下所示:n"); printf("NumberttLetterttWeightttCoden"); for(i=1;i<=n;i+) printf("%dtt",i); printf("%ctt",letteri-1); printf("%dtt%sn",wi,HCi); /依次輸出編號,字母,權(quán)值,和哈夫曼編碼; printf("請輸入要翻譯的哈夫曼編碼:n"); gets(code); /根據(jù)先前的哈夫曼編碼表,輸入哈夫曼編碼 Decodi

13、ng(HT,code,letter,n); /哈夫曼編碼譯為字母 printf("n"); break; return 0; (2)基本操作函數(shù):(1)輸出錯誤的原因void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1); /輸出出現(xiàn)錯誤的原因(2)建哈夫曼樹函數(shù)void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n) /w存放n個字符的權(quán)值,構(gòu)造哈夫曼樹HT,并求出n個字符的哈

14、夫曼編碼HC int i,s1,s2; HuffmanTree p; char *cd; int f,c,start,m; if(n<=1) Error("輸入數(shù)據(jù)太少!"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0號單元未用for(p=HT,i=0;i<=n;i+,p+,w+) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; for(;i<=m;i+,p+) p->weight=0; p->

15、parent=0; p->lchild=0; p->rchild=0; for(i=n+1;i<=m;i+) /建立哈夫曼樹 /在哈夫曼樹中選擇parent為零且weight最小的兩個結(jié)點,其序號分別為s1和s2。Select(HT,i-1,&s1,&s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight= HTs1.weight + HTs2.weight; printf("HT List:n"); printf("Numberttw

16、eightttparentttlchildttrchildn"); /輸出序號,權(quán)值,父節(jié)點,左孩子和右孩子 for(i=1;i<=m;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); /從葉子到根逆向求每個字符的哈夫曼編碼 HC=(HuffmanCode)malloc(n+1) * sizeof(char *); /分配n個字符編碼的頭指針 cd=(char *)malloc(n* sizeof(char *); /分配求編碼的工作空間 cdn-

17、1='0' /編碼結(jié)束符 for(i=1;i<=n;i+) /逐個字符求哈夫曼編碼 start=n-1; /編碼結(jié)束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /從葉子向根逆向求編碼 if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char *); /為第i個字符編碼分配空間 strcpy(HCi,&cdstart); /從Cd復(fù)制字符串到HC free(cd);

18、/釋放空間 (3)選擇權(quán)值最小的兩個結(jié)點void Select(HuffmanTree &HT,int num,int *s1,int *s2) /變量:哈夫曼樹,節(jié)點數(shù),兩個指針int i; for(i=1;i<=num;i+)if(HTi.parent=0)*s1=i; break; /S1指向頭結(jié)點for(i=1;i<=num;i+)if(HTi.parent=0)if(HT*s1.weight>HTi.weight)*s1=i; /s1指向權(quán)值最小的結(jié)點 for(i=1;i<=num;i+) if(i=*s1) continue; else if(HTi

19、.parent=0)*s2=i; break;for(i=1;i<=num;i+)if(HTi.parent=0) if(i=*s1) continue; else if(HT*s2.weight>=HTi.weight) *s2=i; /s2指向次小結(jié)點 (4)譯碼函數(shù)。void Decoding(HuffmanTree HT,char Ch,char letter,int n) /已知哈夫曼樹,一個用以儲存編碼的字符數(shù)組,一個用以儲存譯碼的字符數(shù)組,和輸入字符串的長度 int leave; char *p; p=Ch;printf("譯碼結(jié)果如下:n");

20、while(*p!='0') leave=2*n-1; /剩余空間為2*n-1 while(HTleave.lchild!=0) /左孩子存在時 if(*p='0') leave=HTleave.lchild; /如果哈夫曼編碼為0,是左孩子 else leave=HTleave.rchild; /否則是右孩子 p+; /指向下一節(jié)點 printf("%c",letterleave-1); /輸出譯碼結(jié)果 printf("n");四程序使用說明及測試結(jié)果程序使用和測試的截圖如下:1.顯示權(quán)值表2.將字符編為哈夫曼碼3.將哈

21、夫曼樹譯碼。五)、實驗總結(jié)(實驗心得)1.你在編程過程中花時多少? 答:從設(shè)計到編寫,從調(diào)試到完成,直至最終完成實驗報告一共用了約八個小時。2.多少時間在紙上設(shè)計?答:兩個小時。3.多少時間上機輸入和調(diào)試?答:四個多小時。4.多少時間在思考問題?答:設(shè)計前就思考,直至完成報告,十多個小時。5.遇到了哪些難題?又是怎么克服的?答:1.知識掌握不熟練??朔椒ǎ赫J(rèn)真閱讀教科書及有關(guān)資料中的相關(guān)知識。 2.算法編不出來或錯誤百出。解決方法:借鑒課本和有關(guān)資料中的算法,自己努力思考編寫,向同學(xué)學(xué)習(xí)。算法出現(xiàn)錯誤,慢慢調(diào)試,發(fā)現(xiàn)錯誤并不斷改進(jìn),直到完成程序編寫。6.你的收獲有哪些?答:首先,我對哈夫曼書

22、樹的知識有了更多了解,破除了錯誤的認(rèn)識。其次,通過這次作業(yè),我掌握了幾種與哈夫曼樹有關(guān)的算法。最后,我還溫習(xí)了有關(guān)C語言的許多知識。 參考文獻(xiàn):【1】嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu) 清華大學(xué)出版社【2】朱明方 吳及數(shù)據(jù)結(jié)構(gòu)與算法教程人民郵電出版社附:完整程序#include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct int weight; int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode;

23、void Error(char *message); void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n); void Select(HuffmanTree &HT, int n,int *s1,int *s2); void Decoding(HuffmanTree HT,char Ch,char letter,int n); void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1); v

24、oid HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w, int n) /建哈夫曼樹函數(shù) int i,s1,s2; HuffmanTree p; char *cd; int f,c,start,m; if(n<=1) Error("輸入數(shù)據(jù)太少!"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT,i=0;i<=n;i+,p+,w+) p->weight=*w; p->parent=0; p->

25、;lchild=0; p->rchild=0; for(;i<=m;i+,p+) p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; for(i=n+1;i<=m;i+) Select(HT,i-1,&s1,&s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight= HTs1.weight + HTs2.weight; printf("HT List:n"); print

26、f("Numberttweightttparentttlchildttrchildn"); for(i=1;i<=m;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); HC=(HuffmanCode)malloc(n+1) * sizeof(char *); cd=(char *)malloc(n* sizeof(char *); cdn-1='0' for(i=1;i<=n;i+) start=n-1; for(c

27、=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char *); strcpy(HCi,&cdstart); free(cd); void Select(HuffmanTree &HT,int num,int *s1,int *s2) /選擇權(quán)值最小的兩個結(jié)點int i; for(i=1;i<=num;i+)if(HTi.parent=0)*s1=

28、i; break;for(i=1;i<=num;i+)if(HTi.parent=0)if(HT*s1.weight>HTi.weight)*s1=i; /從首到尾找出權(quán)值最小的 for(i=1;i<=num;i+) if(i=*s1) continue; else if(HTi.parent=0)*s2=i; break;for(i=1;i<=num;i+)if(HTi.parent=0) if(i=*s1) continue; else if(HT*s2.weight>=HTi.weight) *s2=i;void Decoding(HuffmanTree H

29、T,char Ch,char letter,int n) /譯碼函數(shù) int leave; char *p; p=Ch;printf("譯碼結(jié)果如下:n"); while(*p!='0') leave=2*n-1; while(HTleave.lchild!=0) if(*p='0')leave=HTleave.lchild; else leave=HTleave.rchild; p+; printf("%c",letterleave-1); printf("n");int main() Huffman

30、Tree HT=NULL; HuffmanCode HC=NULL; int *w=NULL; int i,j,n,a; char letter100,code500; char str1='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q',&

31、#39;R','S','T','U','V','W','X','Y','Z', str2='a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p&

32、#39;,'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; printf("請選擇要進(jìn)行的操作:1.顯示權(quán)值表 2.將字符編碼 3.翻譯哈夫曼碼 n"); scanf("%d",&a

33、); switch(a) case 1: for(i=1;i<=26;i+) printf("%c %c %dtt",str1i-1,str2i-1,fnumi-1); printf("n");break; case 2: printf("請輸入要編碼的電文:n"); scanf("n"); gets(letter); n=strlen(letter); w=( int *)malloc(n+1)*sizeof( int *); w0=0; for(i=1;i<=n;i+) if(letteri-1>64 && letteri-1<91) j=1; wh

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論