1、實驗課程名稱 數據結構課程設計 專 業 班 級 學 生 姓 名 學 號 指 導 教 師 2012 至 2013 學年第 一 學期第 1 至 18 周目錄一、 概 述21.1課程設計的背景21.2 赫夫曼樹21.3 課程設計目的2二、系統分析32.1 課程設計的主要內容32.2功能設計3三、概要設計43.1 設計思想43.2 函數間的關系4四、詳細設計5五、運行于測試8六、總結與心得11附錄：程序代碼12試驗題目：赫夫曼編碼的應用一、 概 述1.1課程設計的背景當下，如何采用有效的數據壓縮技術節省數據文件的存儲空間和計算機網絡傳送時間已越來越引起人們的重視，赫夫曼編碼正是一種運用廣泛且非常有效的

2、數據壓縮技術。1.2 赫夫曼樹 赫夫曼編碼就是利用赫夫曼樹求得用于通信的二進制編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示為“0碼”，指向右子樹的分支表示為“1”碼，取每條路徑上的“0”和“1”的序列作為和各個葉子對應的字符的編碼，這就是所謂的赫夫曼編碼。1.3 課程設計目的本試驗就是通過先建立赫夫曼樹，然后利用建好的赫夫曼樹生成赫夫曼編碼后進行譯碼。二、系統分析2.1 課程設計的主要內容本實驗要求完成發送端對等待傳送數據的編碼和接收端對傳送來的數據的譯碼。要實現五個功能：接受原始數據、編碼、譯碼、輸出編碼、譯碼存檔。通過系統的提示要建立赫夫曼樹并對載入的原

3、文件進行編碼，并保存到txtfile.tet文件中，同時輸出到屏幕。最后將建立的赫夫曼樹用某種的存儲方式存儲后輸出。 2.2功能設計（1）初始化（initialization） 從終端讀入字符集大小n，以及n個字符和n個權值，建立赫夫曼樹。并將它存放于文件htmtree.tx中。 （2）編 碼（encoding） 利用已經建立好的赫夫曼樹（如不在內存，則從文件hfmtree.txe中讀入，對文件tobetree.txt中的正文進行編碼。然后將結果存在文件codefile.txt中。 （3）譯 碼（decoding） 利用已經建立好的赫夫曼樹將文件codefile.txt中的代碼進行譯碼，將結果

4、存入文件textfile.txt中。 （4）輸出譯碼（print） 將文件codefile.txt以緊湊格式顯示在終端上。同時將字符型式寫入到文件codeprint.txt中。 （5）顯示赫夫曼樹（treeprint） 將已經在內存中的赫夫曼樹以直觀的方式顯示在屏幕上，同時將此字符型的赫夫曼樹寫入文件treeprint.txt中。三、概要設計 3.1 設計思想 赫夫曼樹用鄰接矩陣來作為存儲結構，借助靜態鏈表來實現遍歷。3.2 函數間的關系 四、詳細設計1赫夫曼樹的抽象數據類型定義ADT HuffmanCoding數據對象 T：具有相同特征的數據元素的集合數據關系 R：滿足最優二叉樹的關系基本操

5、作 P：Init （&t）操作結果：構造一個空赫夫曼樹t。Encode（）操作結果：利用赫夫曼樹進行編碼Decode（）操作結果：利用赫夫曼進行譯碼2主函數void mian（）打印表頭：while（選擇選項不為0）輸入選項：switch(選擇項)case 1：初始化；break；case 2：輸入編碼字符；break；case 3：編碼字符；break；case 4：譯碼操作；break；case 5：輸出譯碼；break；case 6：顯示赫夫曼樹；break；default ：輸入錯誤，重新選擇；3求赫夫曼編碼if(tj.weight<k&&tj.paren

6、t=0) k=tj.weight,flag=j; /flag為標志符，為不小于可能的值tflag.parent=1;4新建赫夫曼樹HTs1.parent=HTs2.parent=i;/將選好的兩個結點設置成有同一個雙親結點 HTi.lchild=s1;/左孩子的權值 HTi.rchild=s2;/右孩子的權值HTi.weight=HTs1.weight+HTs2.weight;/將兩個權值相加作為新的權值 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/為赫夫曼代碼分配空間5將赫夫曼編碼寫入文件用fputs(HCi,htmTree); fputs(r,ht

7、mTree);fclose(htmTree) 這些函數來實現編碼寫入文件;6完成譯碼功能并將譯碼寫入文件因為赫夫曼樹建好后是左孩子結點旁標上0，右孩子結點上標上1 所以碰到1是用左孩子結點，2是用右孩子結點，可以用條件語句來實現。 if(i2='0') m=HTm.lchild; if(i2='1') m=HTm.rchild; fputs(outext,txtfile);/將譯碼寫入文件五、運行于測試1.程序運行后，出現如下主界面：2.執行其它操作之前必須進行初始化，選擇“1”執行，并輸入結點數3.依次按提示輸入字符集并輸入相應的權值,輸入后會自動寫入根目錄下

8、htmTree.txt文件中。4輸入要編碼的字符，如下圖：6編碼，對目錄下tobetran.txt文件進行編碼，編碼完成后將寫入目錄下codefile.txt文件中。7.譯碼，即對目錄下codefile.txt文件中的字符進行譯碼，譯碼完成后，內容將會被寫入到目錄下txtfile.txt文件中。 8輸出譯碼，即將CodePrint.txt中的編碼字符。9顯示赫夫曼樹：六、總結與心得 通過兩個學期對數據結構課程設計的學習，從中認識到怎樣將知識遷移運用，深刻的知道了理論應用和實際相互間的密切聯系，感受到了理論知識的重要，在今后的學習中一定會更加努力，認真，并且將理論與實踐相結合。在做這個課程設計論

9、文的時候，我遇到過許多的問題，比如說，寫程序以及調試程序時，有很多地方的錯誤都搞不懂，不過在同學的幫助下，我成功的調試出了程序，并運行出了結果，當時我感覺非常有成就感。還有就是論文格式上，之前都沒有學習過，不過通過老師講解以及網上百度，最終我還是把它搞懂了，總之，覺得這門課程我收獲了很多課堂外不能學到的東西。非常讓我受益匪淺！ 通過這門課程的學習，我也確實體會到了自己的知識還有很多不足之處和個人能力的十分有限，只有通過同學、老師間的密切配合才能完成一項不錯的工作。 不過從中我也體會到了在學習中也有無限的樂趣，可以將現實生活中某一問題用程序編寫出來并將以調試，得出結果。 在這里也要感謝老師和同學

10、們對我的幫助，有你們的幫助，我才會學得更好。附錄：程序代碼#include <iostream.h> #include <iomanip.h> #include <string.h> #include <malloc.h>#include <stdio.h> typedef int TElemType; const int UINT_MAX=999;typedef struct int weight; /權值 int parent,lchild,rchild; /父節點，左孩子結點，右孩子結點 HTNode,* HuffmanTree

11、; typedef char *HuffmanCode; /-全局變量- HuffmanTree HT; /代表赫夫曼樹 HuffmanCode HC; /代表赫夫曼編碼 int *w,i,j,n; char *z; int flag=0; int numb=0; / -求赫夫曼編碼- void line()cout<<"n=n" int min(HuffmanTree t,int i) int j,flag; int k=UINT_MAX; / 取k為不小于可能的值 for(j=1;j<=i;j+) if(tj.weight<k&&

12、tj.parent=0) k=tj.weight,flag=j; tflag.parent=1; return flag; /返回標識符 /- void select(HuffmanTree t,int i,int &s1,int &s2) int j; s1=min(t,i); s2=min(t,i); if(s1>s2)/ s1為最小的兩個值中序號小的那個 j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2,s

13、tart; int c,f; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0號單元未用 for(p=HT+1,i=1;i<=n;+i,+p,+w) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; for(;i<=m;+i,+p) p->parent=0; for(i=n+1;i<=m;+i) / 建赫夫曼樹 select(HT,i-1,

14、s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; 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=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 從葉子到根逆向求編碼 if(HTf.lchild=c)

15、cd-start='0' else cd-start='1' HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); /-初始化赫夫曼鏈表- void init() flag=1; int num; int num2; cout<<"赫夫曼鏈表初始化完成 !"<<endl<<"=n"<<"請輸入結點數：" cin>>num; n=num; line

16、(); w=(int*)malloc(n*sizeof(int);/weight z=(char*)malloc(n*sizeof(char);/word cout<<"n請依次輸入"<<n<<"個字符(字符型)n按Enter結束：<<endl; char temp2; line(); for(i=0;i<n;i+) cout<<"第"<<i+1<<"個字符:"<<endl; gets(temp); *(z+i)=*temp

17、; line(); for(i=0;i<=n-1;i+) cout<<setw(6)<<*(z+i); line(); cout<<"n請依次輸入"<<n<<"個權值n按Enter結束："<<endl; line(); for(i=0;i<=n-1;i+) cout<<endl<<"第"<<i+1<<"個字符的權值:" cin>>num2; *(w+i)=num2; /輸入

18、部分結束- HuffmanCoding(HT,HC,w,n); line(); cout<<"字符對應的編碼為:"<<endl; for(i=1;i<=n;i+) /cout<<"字符"<<*(z+i-1)<<"的編碼" puts(HCi); /-將赫夫曼編碼寫入文件- line(); /cout<<"下面將赫夫曼編碼寫入文件"<<endl<<"."<<endl; FILE *htm

19、Tree; char r=' ','0' if(htmTree=fopen("htmTree.txt","w")=NULL) cout<<"文件打開失敗"<<endl; return; fputs(z,htmTree); for(i=0;i<n+1;i+) fprintf(htmTree,"%6d",*(w+i); fputs(r,htmTree); for(i=1;i<=n;i+) fputs(HCi,htmTree); fputs(r,htmT

20、ree); fclose(htmTree); cout<<"已將字符與對應編碼寫入根目錄下文件htmTree.txt中"<<endl<<endl; /init /-獲取字符并寫入文件- void inputcode() /cout<<"請輸入你想要編碼的字符"<<endl; FILE *virttran,*tobetran; char str100; if(tobetran=fopen("tobetran.txt","w")=NULL) cout<&

21、lt;"不能打開文件"<<endl; return; cout<<"請輸入你想要編碼的字符"<<endl; gets(str); fputs(str,tobetran); cout<<"獲取字符成功"<<endl; fclose(tobetran); void encode() /完成譯碼功能 cout<<"下面對目錄下文件tobetran.txt中的字符進行編碼"<<endl; FILE *tobetran,*codefile;

22、if(tobetran=fopen("tobetran.txt","rb")=NULL) cout<<"不能打開文件"<<endl; if(codefile=fopen("codefile.txt","wb")=NULL) cout<<"不能打開文件"<<endl; char *tran; i=99; tran=(char*)malloc(100*sizeof(char); /為tuan分配100個字節 while(i=99)

23、if(fgets(tran,100,tobetran)=NULL) cout<<"不能打開文件"<<endl; break; for(i=0;*(tran+i)!='0'i+) for(j=0;j<=n;j+) if(*(z+j-1)=*(tran+i) fputs(HCj,codefile); puts(HCj); if(j>n) cout<<"字符錯誤，無法編碼!"<<endl; break; cout<<"編碼工作完成"<<end

24、l<<"編碼寫入目錄下的codefile.txt中"<<endl<<endl; fclose(tobetran); fclose(codefile); free(tran); void decode() /完成譯碼功能 cout<<"下面對根目錄下文件codefile.txt中的字符進行譯碼"<<endl; FILE *codef,*txtfile; if(txtfile=fopen("Textfile.txt","w")=NULL) cout<&l

25、t;"不能打開文件"<<endl; if (codef=fopen("codefile.txt","r")=NULL) cout<<"不能打開文件"<<endl; char *tbdc,*outext,i2; int io=0,i,m; unsigned long length=10000; tbdc=(char*)malloc(length*sizeof(char); /分配空間 fgets(tbdc,length,codef); outext=(char*)malloc(le

26、ngth*sizeof(char); /分配空間 m=2*n-1; for(i=0;*(tbdc+i)!='0'i+) /進入循環 i2=*(tbdc+i); if(HTm.lchild=0) *(outext+io)=*(z+m-1); io+; m=2*n-1; i-; else if(i2='0') m=HTm.lchild; else if(i2='1') m=HTm.rchild; *(outext+io)='0' fputs(outext,txtfile); cout<<"譯碼完成"&l

27、t;<endl<<"內容寫入根目錄下的文件txtfile.txt中"<<endl<<endl; free(tbdc); free(outext); fclose(txtfile); fclose(codef); void printcode() /打印代碼 cout<<"下面打印根目錄下文件CodePrin.txt中編碼字符"<<endl<<"=n" FILE * CodePrin,* codefile; if(CodePrin=fopen("Co

28、dePrin.txt","w")=NULL) cout<<"不能打開文件"<<endl; return; if(codefile=fopen("codefile.txt","r")=NULL) cout<<"不能打開文件"<<endl; return; char *work3; work3=(char*)malloc(51*sizeof(char); do if(fgets(work3,51,codefile)=NULL) cout<

29、;<"不能讀取文件"<<endl; break; fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50); free(work3); line(); cout<<"打印工作結束"<<endl<<endl; fclose(CodePrin); fclose(codefile); /-打印赫夫曼樹的函數- void coprint(HuffmanTree start,HuffmanTree HT) char t=' ' if(

30、start!=HT) FILE * TreePrint; if(TreePrint=fopen("TreePrint.txt","a")=NULL) cout<<"創建文件失敗"<<endl; return; numb+;/該變量為已被聲明為全局變量 coprint(HT+start->rchild,HT); if(start->lchild!=NULL&&start->rchild!=NULL) t='<' cout<<setw(5*numb

31、)<<start->weight<<t<<endl; fprintf(TreePrint,"%dn",start->weight); coprint(HT+start->lchild,HT); numb-; fclose(TreePrint); void printree(HuffmanTree HT,int w) /打印赫夫曼樹 HuffmanTree p; p=HT+w; cout<<"下面打印赫夫曼樹"<<endl; / 輸出“打印赫夫曼樹”語句 line(); coprint(p,HT); line(); cout<<"打印工作結束"<<endl; /輸出“打印工作結束” void printhead() cout<<"ntt" cout<<"*ntt" cout<<