huffman實驗報告

1、一、 問題描述 1. 實驗題目：huffman編解碼2. 基本要求：初始化（initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立huffman 樹，并將它存入hfmtree 中。 編碼（encoding）。利用已經(jīng)建好的huffman樹（如果不在內(nèi)存，則應(yīng)從文件hfmtree中讀?。?，對文件tobetran中的正文進行編碼，然后將結(jié)果存入文件codefile中。 解碼（decoding）。利用已經(jīng)建立好的huffman樹將文件codefile中的代碼進行解碼，結(jié)果存入textfile中。 打印代碼文件（print）。將文件codefile以緊湊的格式顯示在終端上

2、，每行 50 個代碼。同時將此字符形式的編碼文件寫入文件codeprint中。 打印huffman樹（tree printing）。將已經(jīng)在內(nèi)存中的huffman樹以直觀的形式（樹或者凹入的形式）顯示在終端上，同時將此字符形式的huffman 樹寫入文件treeprint中。 3. 測試數(shù)據(jù)：用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立huffman樹，并對以下報文進行編碼和譯碼：“this program is my favorite”。 字符a b c d e f g h i j k l m 頻度 18664 13 22 32 10321 15 47 57 1 5 32 20 字符 n o

3、p q r s t u v w x y z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 輸入輸出: 字符集大小 n，n個字符和 n個權(quán)值均從終端讀入，初始化后的huffman樹存儲在hfmtree文件中，待編碼文件為tobetran,編碼結(jié)果以文本的方式存儲在文件codefile中，解碼文件存在textfile中,打印的編碼和赫夫曼樹分別存儲在codeprint和treeprint文件中。 用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上一個退出功能“q”，表示退出（quit）。用戶鍵入一個選擇功能符，此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了q為

4、止。 二、 需求分析 1. 本程序可以根據(jù)輸入字符集和頻度建立huffman樹并且對給定文本進行編解碼，還可以直接讀入建立好的huffman樹再對給定文本編解碼，打印編碼、解碼結(jié)果、表格形式及樹形的huffman樹。2. 程序運行后顯示提示信息，提示用戶選擇要進行的操作。i：按提示輸入字符總數(shù)，然后是每個字符及其權(quán)值(輸入時以逗號分隔)，字符為char型，權(quán)值為整型。e：輸入字符的總數(shù)。d：無需輸入。p：無需輸入。t：無需輸入。q：結(jié)束程序。3. 用戶輸入完畢后，輸出結(jié)果如下： i：建立的huffman樹以列表形式被存入hfmtree.txt中。每行的數(shù)據(jù)從左到右依次為節(jié)點中儲存的字符，節(jié)點的

5、左孩子序號，節(jié)點的雙親序號，節(jié)點的右孩子序號，節(jié)點的權(quán)值。e：編碼結(jié)果存入文件codefile.txt中。d：解碼結(jié)果存入文件textfile.txt中。p：將編碼結(jié)果以緊湊的格式顯示在終端上，每行 50 個代碼。同時此字符形式的編碼文件被寫入文件codeprint.txt中。t：huffman樹以樹形顯示在終端上，同時此字符形式的huffman樹被寫入文件treeprint.txt中。q：程序結(jié)束。三、 概要設(shè)計 為了實現(xiàn)上述功能，需要鏈表、棧、隊列、二叉樹四個抽象數(shù)據(jù)類型。 1. 鏈表抽象數(shù)據(jù)類型定義：adt lnode 數(shù)據(jù)對象： d=ai|ailnode,i=1,2.,n,n0 數(shù)據(jù)關(guān)

6、系：r=|ai-1,aid, ai-1ai ,i=2,.,n 基本操作：/初始化鏈表 void initlist_l(linklist &l); /判斷鏈表是否為空 bool listempty_l(linklist l); /求鏈表長度 int listlength_l(linklist l); /插入元素 bool listinsert_l(linklist &l,int i,elemtype e); /刪除元素 bool listdelete_l(linklist &l,int i,elemtype &e); adt lnode2. 棧抽象數(shù)據(jù)類型定義adt sqstack數(shù)據(jù)對象：d=

7、ai|aisqstack,i=1,2.,n,n0 數(shù)據(jù)關(guān)系：r=|ai-1,aid, ai-1ai ,i=2,.,n基本操作：/初始化棧bool initstack_sq(sqstack &s,int msize);/判斷棧是否空bool stackempty_sq(sqstack s);/求棧長度int stacklength_sq(sqstack s);/元素入棧bool push_sq(sqstack &s, selemtype e);/元素出棧bool pop_sq(sqstack &s,selemtype &e); adtsqstack3. 隊列抽象數(shù)據(jù)類型定義adt linkque

8、ue數(shù)據(jù)對象：d=ai|ailinkqueue,i=1,2.,n,n0 數(shù)據(jù)關(guān)系：r=|ai-1,aid, ai-1ai ,i=2,.,n基本操作：/初始化隊列bool initqueue_l(linkqueue &q);/判斷隊列是否為空bool stackfull_sq(sqstack s);bool queueempty_l(linkqueue q);/求隊列長度bool gethead_l(linkqueue q,qelemtype &e);/元素入隊列bool enqueue_l(linkqueue &q, qelemtype e);/元素出隊列bool dequeue_l(link

9、queue &q,qelemtype &e); adt linkqueue4. 二叉樹抽象數(shù)據(jù)類型定義adt htnode數(shù)據(jù)對象：d=ai|aihtnode,i=1,2.,n,n0 數(shù)據(jù)關(guān)系：r=|ai-1,aid, ai-1ai ,i=2,.,n基本操作：/求每個節(jié)點層次void level(hufftree ht,int y,int l,int lev);/中序遍歷打印樹形huffmantreevoid inorder(hufftree ht,file *fp,int k,int a);/選擇權(quán)值最小的兩個節(jié)點void select(hufftree ht,int t,int &q1,i

10、nt &q2);/初始化huffman樹void huffmantree(hufftree ht,char *code,int *w,int n);/huffman編碼void coding(hufftree ht,int root,char *hc,sqstack &s); adt htnode5.本程序保護模塊： 主程序模塊 huffman單元模塊：實現(xiàn)二叉樹的抽象數(shù)據(jù)類型 stack單元模塊：實現(xiàn)鏈表、棧、隊列抽象數(shù)據(jù)類型 調(diào)用關(guān)系：主程序模塊-huffman單元模塊-stack單元模塊四、 詳細設(shè)計 1.結(jié)點類型和結(jié)點指針類型： 鏈表：typedef struct lnodechar

11、data;struct lnode *next;lnode，*linklist;棧：typedef structselemtype * elem;int stacksize;int top;sqstack;隊列：typedef linklist queueptr; typedef structqueueptr front; queueptr rear;linkqueue; 二叉樹：typedef structint weight;char data;int parent,lchild,rchild;htnode;typedef htnode *hufftree;2. 鏈表的實現(xiàn) 本實驗只用到鏈

12、表節(jié)點類型的定義，用來定義queueptr,沒有用到實現(xiàn)鏈表操作的函數(shù)。3.棧的實現(xiàn)/元素入棧bool push_sq(sqstack &s, selemtype e)if(stackfull_sq(s)return false;s.elem+s.top=e;return true;其余略4.隊列的實現(xiàn)bool dequeue_l(linkqueue &q,qelemtype &e)if(q.front=q.rear)return false;queueptr p=q.front-next;q.front-next=p-next;e=p-data;if(q.rear=p)q.rear=q.fr

13、ont;delete p;return true;其余略5.二叉樹的實現(xiàn)/選擇權(quán)值最小的兩個節(jié)點void select(hufftree ht,int t,int &q1,int &q2) int i,j;for(i=1;i=t*2-1;i+)if(hti.parent=0)q1=i;break;for(i=1;i=t*2-1;i+)if(hti.weighthtq1.weight&hti.parent=0&hti.weight!=0)q1=i;for(i=1;i=t*2-1;i+)if(hti.parent=0&i!=q1)q2=i;break;for(j=1;j=t*2-1;j+)if(h

14、tj.weighthtq1.weight)q2=j;/初始化huffman樹void huffmantree(hufftree ht,char *code,int *w,int n)int m=n*2-1,i,s1,s2;for(i=1;i=m;i+)hti.lchild=hti.rchild=hti.parent=0;hti.weight=i=n?wi:0;hti.data=i=n?codei:#;for(i=n+1;i=m;i+)select(ht,n,s1,s2);hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight

15、;hts1.parent=hts2.parent=i;/huffman編碼void coding(hufftree ht,int root,char *hc,sqstack &s)char ch,e;if(root!=0)if(htroot.lchild=0)push_sq(s,0);hcroot=new charstacklength_sq(s);strcpy(hcroot,s.elem);pop_sq(s,ch);push_sq(s,0);coding(ht,htroot.lchild,hc,s);pop_sq(s,e);push_sq(s,1);coding(ht,htroot.rchi

16、ld,hc,s);pop_sq(s,e);/求節(jié)點深度void level(hufftree ht,int y,int l,int lev)if(y!=0)lev+;ly=lev;level(ht,hty.lchild,l,lev);level(ht,hty.rchild,l,lev);/中序遍歷打印樹形huffmantreevoid inorder(hufftree ht,file *fp,int k,int a)int le=0,i;if(k=0) return; elseinorder(ht,fp,htk.rchild,a);le=ak; for(i=0;ilchild, htht-rc

17、hild, htht-parent。原先編寫是inorder每次執(zhí)行時，同時調(diào)用level算出節(jié)點層次，但是結(jié)果一直不對（現(xiàn)在還沒發(fā)現(xiàn)錯誤在哪(*_*) ），后來在同學(xué)的建議下先用一個數(shù)組存儲所有節(jié)點的level，然后在inorder中使用，得到了正確的結(jié)果。5.復(fù)雜度分析函數(shù) 時間復(fù)雜度 空間復(fù)雜度select o(n) o(1)huffmantree o(n) o(n)coding o(n) o(n)level o(n) o(n)inorder o(n) o(n)六、 使用說明 程序運行后根據(jù)提示輸入所要進行的操作，字符集大小 n，n個字符和 n個權(quán)值。程序?qū)⒊跏蓟蟮膆uffman樹存儲

18、在hfmtree文件中，編碼結(jié)果以文本的方式存儲在文件codefile中，解碼文件存在textfile中,打印的編碼和哈弗曼樹分別存儲在codeprint和treeprint文件中。七、 調(diào)試結(jié)果 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立huffman樹，并對以下報文進行編碼和譯碼：“this program is my favorite”。 字符a b c d e f g h i j k l m 頻度 18664 13 22 32 10321 15 47 57 1 5 32 20 字符 n o p q r s t u v w x y z 頻度 57 63 15 1 48 51 80 23

19、8 18 1 16 1 結(jié)果：hfmntree:,0,50,0,186a,0,45,0,64b,0,33,0,13c,0,37,0,22d,0,39,0,32e,0,48,0,103f,0,36,0,21g,0,33,0,15h,0,41,0,47i,0,43,0,57j,0,28,0,1k,0,28,0,5l,0,40,0,32m,0,36,0,20n,0,44,0,57o,0,44,0,63p,0,34,0,15q,0,29,0,1r,0,42,0,48s,0,42,0,51t,0,46,0,80u,0,37,0,23v,0,31,0,8w,0,35,0,18x,0,30,0,1y,0,3

20、4,0,16z,0,31,0,1#,11,29,12,6#,18,30,28,7#,25,32,29,8#,27,32,23,9#,30,35,31,17#,3,38,8,28#,17,38,26,31#,32,39,24,35#,14,40,7,41#,4,41,22,45#,33,43,34,59#,5,45,35,67#,13,46,36,73#,37,47,9,92#,19,47,20,99#,10,48,38,116#,15,49,16,120#,2,49,39,131#,40,50,21,153#,41,51,42,191#,6,51,43,219#,44,52,45,251#,4

21、6,52,1,339#,47,53,48,410#,49,53,50,590#,51,0,52,1000codefile：11010001011000111110111100010100101110100101010110010111011000111111100100111111111100111010101110111001001001101101010textfile：this program is my favoritecodeprint：11010001011000111110111100010100101110100101010110010111011000111111100100

22、111111111100111010101110111001001001101101010treeprint： # t # f # m # l # w # v # z # k # j # q # x # d # a # o # n # y # p # g # b # i # e # s # r # h # u # c程序截屏：初始化編碼解碼打印樹八、 附錄 源代碼：huffman.hvoid level(hufftree ht,int y,int l,int lev);void inorder(hufftree ht,file *fp,int k,int a);void select(huff

23、tree ht,int t,int &q1,int &q2);void huffmantree(hufftree ht,char *code,int *w,int n);void coding(hufftree ht,int root,char *hc,sqstack &s);int mygetint(file *fp);stack.htypedef structint weight;char data;int parent,lchild,rchild;htnode;typedef struct lnodechar data;struct lnode *next;lnode,*linklist

24、;typedef htnode *hufftree;typedef char qelemtype; /elemtype 定義為char類型typedef linklist queueptr; /結(jié)點指針typedef structqueueptr front; queueptr rear;linkqueue; /鏈隊列定義typedef char selemtype; /elemtype 定義為char類型typedef structselemtype * elem;int stacksize;int top;sqstack;/初始化棧bool initstack_sq(sqstack &s,

25、int msize);bool stackempty_sq(sqstack s);/判斷棧是否滿/求棧長度int stacklength_sq(sqstack s);/元素入棧bool push_sq(sqstack &s, selemtype e);/元素出棧bool pop_sq(sqstack &s,selemtype &e);/遍歷元素bool initqueue_l(linkqueue &q);/判斷隊列是否為空bool stackfull_sq(sqstack s);bool queueempty_l(linkqueue q);/求隊列長度bool gethead_l(linkqu

26、eue q,qelemtype &e);/元素入隊列bool enqueue_l(linkqueue &q, qelemtype e);/元素出隊列bool dequeue_l(linkqueue &q,qelemtype &e);void strclear(char str);huffman.cpp#include#include#include#includestack.hvoid select(hufftree ht,int t,int &q1,int &q2) /選擇權(quán)值最小的兩個節(jié)點 int i,j;for(i=1;i=t*2-1;i+) /q1賦初值if(hti.parent=0)

27、q1=i;break;for(i=1;i=t*2-1;i+) if(hti.weighthtq1.weight&hti.parent=0&hti.weight!=0)q1=i;for(i=1;i=t*2-1;i+)if(hti.parent=0&i!=q1) /q2賦初值q2=i;break;for(j=1;j=t*2-1;j+)if(htj.weighthtq1.weight)q2=j;void huffmantree(hufftree ht,char *code,int *w,int n) /建立哈弗曼樹int m=n*2-1,i,s1,s2;for(i=1;i=m;i+)hti.lchi

28、ld=hti.rchild=hti.parent=0;hti.weight=i=n?wi:0;hti.data=i=n?codei:#;for(i=n+1;i=m;i+)select(ht,n,s1,s2);hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;hts1.parent=hts2.parent=i;void coding(hufftree ht,int root,char *hc,sqstack &s) /哈弗曼編碼char ch,e;if(root!=0)if(htroot.lchild=0)push_sq

29、(s,0);hcroot=new charstacklength_sq(s);strcpy(hcroot,s.elem);pop_sq(s,ch);push_sq(s,0);coding(ht,htroot.lchild,hc,s);pop_sq(s,e);push_sq(s,1);coding(ht,htroot.rchild,hc,s);pop_sq(s,e);void level(hufftree ht,int y,int l,int lev) /求每個節(jié)點層次，賦值給數(shù)組levif(y!=0)lev+;ly=lev;level(ht,hty.lchild,l,lev);level(ht

30、,hty.rchild,l,lev);void inorder(hufftree ht,file *fp,int k,int a) /中序遍歷打印哈弗曼樹int le=0,i;if(k=0) return; elseinorder(ht,fp,htk.rchild,a);le=ak; for(i=0;i=48&s=57) /讀取 numj+=s; s=getc(fp);for(k=0;kj;k+) /將讀取結(jié)果轉(zhuǎn)化成整數(shù) i=i*10;i=i+(numk-48);return i;stack.cpp#include#include#includetypedef structint weight

31、;char data;int parent,lchild,rchild;htnode;typedef htnode *hufftree;typedef struct lnodechar data;struct lnode *next;lnode,*linklist;typedef htnode *hufftree;typedef char qelemtype; /elemtype 定義為char類型typedef linklist queueptr; /結(jié)點指針typedef structqueueptr front; queueptr rear;linkqueue; /鏈隊列定義typede

32、f char selemtype; /elemtype 定義為char類型typedef structselemtype * elem;int stacksize;int top;sqstack;/初始隊列bool initqueue_l(linkqueue &q)q.front=q.rear=new lnode;/ 給elem指針動態(tài)分配msize長度的數(shù)組if(!q.front)cerr分配內(nèi)存錯誤!next;return i;bool enqueue_l(linkqueue &q, qelemtype e)queueptr p=new lnode;if(!p)return false;p

33、-data=e;p-next=null;q.rear-next=p;q.rear=p;return true;/元素出隊列bool dequeue_l(linkqueue &q,qelemtype &e)if(q.front=q.rear)return false;queueptr p=q.front-next;q.front-next=p-next;e=p-data;if(q.rear=p)q.rear=q.front;delete p;return true;/初始化棧bool initstack_sq(sqstack &s,int msize)s.elem=new selemtypems

34、ize;/ 給elem指針動態(tài)分配msize長度的數(shù)組if(!s.elem)cerr分配內(nèi)存錯誤!endl;return false;s.stacksize=msize; /順序棧的最大容量s.top=-1; / 順序棧初始時空棧return true;/判斷棧是否為空bool stackempty_sq(sqstack s)return (s.top=-1);/判斷棧是否滿bool stackfull_sq(sqstack s)return(s.top=s.stacksize-1);int stacklength_sq(sqstack s)return s.top+1;/元素入棧bool p

35、ush_sq(sqstack &s, selemtype e)if(stackfull_sq(s)return false;s.elem+s.top=e;return true;/元素出棧bool pop_sq(sqstack &s,selemtype &e)if(stackempty_sq(s)return false;e=s.elems.top-;return true;void strclear(char str)str0=0;huffmanoperate.cpp#include#include#include#includestack.h#includehuffman.hvoid ma

36、in()file *fp,*fp1,*fp2,*fp3,*fp4,*fp5;char ch,choice,e,str30,codeelem30;int n,i,k=0,weight30,ll60;htnode hht60; linkqueue qq;char *hhc;doprintf(請選擇要進行的操作（i：初始化哈弗曼樹；e：用建立的樹進行編碼；d：解碼文件；p：打印密碼；t：打印哈弗曼樹；q：終止操作）:);scanf(%c,&choice);fflush(stdin);if(choice=i)printf(輸入字符數(shù)目:); scanf(%d,&n); fflush(stdin);fo

37、r(i=1;i=n;i+)printf(輸入第%d個字符和&權(quán)值（逗號分隔）:,i);scanf(%c,%d,&codeelemi,&weighti);fflush(stdin);huffmantree(hht,codeelem,weight,n);if(fp=fopen(hfmtree.txt,w)=null)printf(cant open hfmtree);exit(1);for(i=1;i=n*2-1;i+)fprintf(fp,%c,%d,%d,%d,%d,hhti.data,hhti.lchild,hhti.parent,hhti.rchild,hhti.weight); fput

38、c(n,fp);fclose(fp);else if(choice=e)sqstack ss;initstack_sq(ss,30);hhc=new char *n+1;printf(輸入字符數(shù)目:); scanf(%d,&n); fflush(stdin);if(fp1=fopen(hfmtree.txt,r)=null)printf(cant open tobetran);exit(1);if(fp2=fopen(codefile.txt,w)=null)printf(cant open codefile);exit(1);if(fp=fopen(tobetran.txt,r)=null)printf(cant open codefile);exit(1); for(i=1;i=n*2-1&ch!=eof;i+) /從哈弗曼樹列表文件中讀取每個節(jié)點信息ch=fgetc(fp1