1、西安郵電學院數據結構課程設計報告題 目1： 哈夫曼編碼/譯碼器 題 目2： 學生信息管理系統 系部名稱：通信工程系專業名稱：通信工程班 級：*學號：*學生姓名 ：*指導教師：*時間：2009年12月16日 至2009年12月25日 題目1.哈夫曼編碼/譯碼器 一、 課程設計目的通過對哈夫曼編碼/譯碼器的實現，熟悉了解Huffman樹的創建過程以及存儲結構，對Huffman編碼/譯碼過程及原則有了更深層次的認識，鍛煉了動手能力，使知識更好的學以致用，為解決數據壓縮問題提供方法。二、 課程設計內容通過統計文件中各字符的出現頻率，建立Huffman樹，再通過建立的已經Huffman的樹，對文件中各字

2、符進行編碼，將結果存入新的文件中，然后從文件中讀取Huffman編碼，進行解碼，結果存入新的文件中，并與源文件進行比較。三、需求分析1統計字符頻率：存文件中讀入字符，并對各字符出現頻率進行統計；2建立Huffman樹：將各字符出現的頻率作為權值，建立Huffman樹；3Huffman編碼：通過已經建立的Huffman樹，對個各字符進行編碼，并存入新的文件中；4.譯碼：讀取存放Huffman編碼的文件，對文件中編碼進行譯碼，把譯碼結果存入新的文件中；5.結果驗證：將譯碼結果與原文件內容進行比較；四、概要設計1. 系統結構圖（功能模塊圖）開始 main（）統計字符頻率創建Huffman樹對文件編碼

3、對編碼譯碼出現次數字符名稱初 始 化結點賦值Huffma編碼存入文件讀取編碼存入文件對編碼譯碼對編碼譯碼成功失敗2功能模塊說明1：統計字符頻率： 定義結構體typedef struct str char data; char num;str;其中data域存放字符名稱，num域存放字符出現頻率，讀取文件ywq1.txt，通過循環比較將結果賦入S2128中；2：創建Huffman樹: 定義結構體typedef struct char data; int weight; int parent; int lchild; int rchild;HTNode,HuffmanTreeM+1;作為Huffm

4、an樹存儲節點類型，調用CrtHuffmanTree()函數，初始化各節點均為 0；然后將存儲字符頻率的數組S2的值賦值給各節點，字符出現頻率作為權值，創建Huffman樹；3：對文件編碼： 定義結構體typedef struct char data; char bitsN+1;CodeNode,HuffmanCodeN;作為HuffmanCode的存儲類型，調用CrtHuffmanCode()函數，從葉子節點向上回溯，是lchild則賦值0，是rchild則賦值為1，對各字符編碼，再調用WriteToFile()函數，將結果寫入文件ywq2.txt中；4：對文件譯碼:讀取編碼文件ywq2.t

5、xt中數據，調用DecodHuffmanCode()函數，從根節點開始，讀取1，走向rchild，讀取0, 走向lchild,直到葉子節點，將葉子節點data域的值寫入文件ywq3.txt中；五、詳細設計及運行結果1讀文件統計字符頻率(read()函數中實現)：打開源文件ywq1.txt讀文件內的字符，初始化數組s1文件是否結束將字符存入數組S1ch.num+讀下一個字符給數組末尾加上結束標志“0”關閉文件是否開始結束源文件ywq1.txt：運行結果：2：創建Huffman樹，CrtHuffmanTree():初始化結構體數組htCrtHuffmanTree()有n棵二叉樹n > 1選權

6、值最小2個二叉樹權值相加得新二叉樹n - 1n = 1建立Huffman樹結束 運行結果：3：Huffman編碼，CrtHuffmanCode();CrtHuffmanCode()根cd-start = 0cd-start = 1否LchildRchildcdstart 賦給hci.bits是結束對應字符編碼寫入文件ywq2.txt運行結果：編碼文件ywq2.txt：3：譯碼，DecodHuffmanCode():DecodHuffmanCode()打開文件ywq2.txt讀取字符ch文件結束否否找根節點ch = 0, 找lchild；ch = 1, 找rchild；葉子節點是是保存 ywq3

7、.txt是結束運行結果：文件ywq3.txt:4:結果驗證：比較源文件ywq1.txt與譯碼文件ywq3.txt可知，譯碼結果與源文件一致。Compare()讀取ywq1.txt中的字符，存入s1，并輸出，讀取ywq3.txt中的字符，存入s2，并輸出，sii= =s2i 是i+,i=1i<k是編譯成功編譯失敗i=k否結束運行結果：六、調試情況，設計技巧及體會通過本次數據結構-哈夫曼編碼的應用-課程設計為期兩周的實習，讓我對數據結構這門課有了深刻的體會，數據結構是在C語言的基礎上建立起來的，它是一個程序的必要條件之一，通過本次實習，也讓我真正領略到數據結構在一個程序中占有多么重要的地位，

8、程序=算法+數據結構。不同的程序運用不同的數據結構可以起到事半功倍的作用。在這次實習，我就已經深深體會到數據結構的精彩運用。這次實習的題目是哈夫曼編碼的應用，在給定的源文件情況下，要根椐所學的哈夫曼樹來建立各字符對應的編碼從而達到使字符編碼化的目的，又要通過解碼使所生成的編碼能原封不動地解成原來的文件。在編寫程序的過程中，也遇到了許多問題，也更讓我體會到了編寫程序應該是一步一個腳印得來的，編寫一個模塊，調試一個，不能全部編寫的差不多了，在進行調試，這樣反而是得不償失，遇到一大堆的錯誤讓人無從找起。從最開始的統計，建樹，選擇最小次小值，到后來的編碼、譯碼，自己寫了一些，也參考了一下別人好的程序，

9、例如在選擇最小值和次小值時，按照書上是給min1和min2初始賦值為32767，但參照了一些好的程序之后，我選擇將min1，min2初始賦值位一個小于等于零的數，這樣會更好，因為字符的頻率不吭能為一個小于等于零的數，如此更符合邏輯；又如統計字符頻率時利用ASC碼進行統計會更加方便與明了。當我們寫一段程序前，一定要反復的思考，怎樣寫更方便，更完美，這樣才能寫出一個好的程序來。另外調試程序前要有一個大概的圖樣，這樣在編程時可以有目的，針對性的建立函數，對函數的形參與實參也要在大腦中有個清晰的認識，否則問題出在這就很難解決了。由于哈夫曼編碼中會運用到很多循環，所以在編寫循環時一定要注意控制語句，防止

10、造成死循環。七、參考文獻C語言程序設計-科學出版社數據結構（C語言描述）-清華大學出版社數據結構（使用C語言）-電子科技大學出版社八、附錄：源代碼#include "stdio.h"#include "string.h"#include "stdlib.h"#include "conio.h"#define N 100#define M 2*N-1typedef struct /定義哈夫曼樹存儲節點結構體類型 char data; int weight; int parent; int lchild; int rc

11、hild;HuffmanTreeM; typedef struct /定義哈夫曼編碼結構體類型 char data; char bitsN;HuffmanCodeN;typedef struct str /定義字符串存儲單元結構體類型 char data; char num;str;int read(str s2) FILE *fp; char ch; int i,k; str s1128;for(i=0;i<=128;i+) s1i.num = 0; s1i.data = 0; s2i.num = 0; s2i.data = 0; if(fp=fopen("d:ywqywq1

12、.txt","r")=NULL) printf("n庫文件不存在!"); exit(1); printf("n.讀取字符串為:n"); ch=fgetc(fp); while(!feof(fp) /統計字符頻率 printf("%c",ch); s1ch.num+; s1ch.data = ch; ch=fgetc(fp); fclose(fp); for(i=1,k=1;i<=128;i+) if(s1i.num!=0) s2k.num = s1i.num; s2k.data = s1i.data

13、; k+; printf("nn.統計結果為(字符 頻率):n"); for(i=1;i<k;i+) printf("<%c %d> ",s2i.data,s2i.num); printf(" (共%d種字符)n",k-1); return k;void SelectMin(HuffmanTree ht,int i,int *p1,int *p2) /查找哈夫曼鏈表中兩個權值最小的節點 int j,min1,min2; min1 = min2 = -1; for(j = 1;j<=i;j+) if(htj.pa

14、rent = 0) if(htj.weight<min1|min1=-1) if(min1!=-1) min2 = min1;*p2=*p1; min1 = htj.weight;*p1=j; else if(htj.weight<min2|min2=-1) min2 = htj.weight; *p2=j; void CrtHuffmanTree(HuffmanTree ht,str s,int n) /創建哈夫曼樹 int i,m,p1,p2; for(i=1;i<n;i+) /初始化節點 hti.data = si.data; hti.weight = si.num;

15、hti.parent = 0; hti.lchild = 0; hti.rchild = 0; m=2*n-3; for(i=n;i<=m;i+) hti.data = 0; hti.weight = 0; hti.parent = 0; hti.lchild = 0; hti.rchild = 0; for(i=n;i<=m;i+) SelectMin(ht,i-1,&p1,&p2); /調用SelectMin函數 hti.weight=htp1.weight+htp2.weight; htp1.parent=i;htp2.parent=i; hti.lchild

16、=p1;hti.rchild=p2; void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int k) /利用建立好的哈夫曼樹對字符串進行編碼 int c,p,i; char cdN+1; int start; for(i=1;i<k;i+) hci.data = hti.data; start = k-1; cdstart = '0' c=i; while(p=htc.parent)!=NULL) cd-start = (htp.lchild=c)?'0':'1' /左分支為0，右分支為1

17、c=p; strcpy(hci.bits,&cdstart); printf("nn.每個字符對應的編碼為:n"); for(i=1;i<k;i+) printf("<%d %c %s> n",i,hci.data,hci.bits);void WriteToFile(HuffmanCode hc,int n) /將編碼結果存儲在文件文件ywq2.txt中 FILE *fp1,*fp2; char ch; int i; if(fp1=fopen("d:ywqywq1.txt","r")=N

18、ULL) printf("n文件不存在!"); exit(1); if(fp2=fopen("d:ywqywq2.txt","w")=NULL) printf("n文件不存在!"); exit(1); ch = fgetc(fp1);printf("n.編碼結果為："); while(ch != EOF) for(i=1;i<n;i+) if(ch = hci.data) fputs(hci.bits,fp2); printf("%s",hci.bits); ch =

19、fgetc(fp1); fclose(fp1); fclose(fp2);printf("n");void DecodHuffmanCode(HuffmanTree ht,int n) /碼結果進行譯碼，并將結果存儲 在文件ywq3中 FILE *fp1,*fp2; char ch; int p,k; if(fp1=fopen("d:ywqywq2.txt","r")=NULL) printf("n文件不存在!"); exit(1); if(fp2=fopen("d:ywqywq3.txt",&

20、quot;w")=NULL) printf("n文件未能創建!"); exit(1); p=k=2*n-3; ch=fgetc(fp1); printf(".譯碼為: ");while(ch!=EOF) if(ch='0')p=htp.lchild; else if(ch='1') p=htp.rchild; if(htp.data!=0) printf("%c",htp.data); fputc(htp.data,fp2); p=k; ch = fgetc(fp1); printf(&quo

21、t;n");fclose(fp1); fclose(fp2);void compare(int k)FILE *fp1,*fp2; char s1N,s2N;int i=1,j=1;printf("nn.編譯前后結果的比較:");if(fp1=fopen("d:ywqywq1.txt","rt")=NULL) printf("n打開文件失敗！n"); exit(1);printf("nn原文件ywq1.txt中的字符為: "); for(i=1;(s1i=fgetc(fp1)!=EOF;i+)printf("%c",s1i);fclose(fp1); if(fp2=fopen("d:ywqywq3.txt","rt")=NULL) printf("n打開文件失敗！n"); exit(1); printf("n文 件ywq3.txt中的字符為: "); for(i=1;(s2i=fgetc(fp2)!=EOF;i+