1、精選優質文檔-傾情為你奉上課 程 設 計課程設計名稱： 數據結構課程設計 專 業 班 級 ： 學 生 姓 名 ： 學 號 ： 指 導 教 師 ： 磊 課程設計時間： 2015.7.062015.7.10 計算機類 專業課程設計任務書學生專業班級學號題 目哈夫曼樹編/譯碼系統課題性質A課題來源D指導教師磊同組無主要容1. 學習掌握并熟練運用C語言進行程序設計,2.針對具體應用問題，選擇、設計和實現合適的抽象數據類型；3.進行整體設計使各個函數之間緊密聯系起來；任務要求1.綜合運用和融化所學理論知識，提高分析和解決實際問題的能力，達到培養良好程序設計能力和習慣的目的，為開發滿足問題要求的小型應用軟

2、件奠定基礎，達到軟件工程的綜合性基礎訓練的目的。,2.完成需求分析報告，報告中對關鍵部分給出圖表說明。要求格式規，工作量飽滿。參考文獻C語言程序設計（第三版）譚浩強 清華大學C Primer Plus(第5版) Stephen prata 人民郵電 審查意見指導教師簽字：教研室主任簽字： 年 月 日專心-專注-專業目錄1需求分析1.1系統介紹利用Huffman編碼進行通信可以大大提高信道利用率縮短信息傳輸時間，降低傳輸成本，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編譯碼系統。

3、此程序就是為這樣的信息收發站寫一個Huffman碼的編譯碼系統。1.2程序的輸入和輸出從終端讀入字符集大小n，以及n個字符及各個字符的權值，建立赫夫曼樹，并將它存儲到文件hfmTree中；利用已建好的赫夫曼樹將文件中的字符編碼，如果赫夫曼樹不在存中，則從文件hfmTree中讀取到存；將譯得的代碼存到文件CodeFile中；利用已建好的赫夫曼樹對CodeFile中的代碼進行譯碼，將結果存入文件TextFile中；最后將已在存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。1.3程序要達到的功能用戶可以利用菜單根據自己的需要來選擇要進

4、行編碼或是譯碼,并將轉換好的字符或編碼以文件的形式存到相應的文件里面。1.4調試過程介紹（l）利用教材中的數據調試程序。（2）用下表給出的字符集和頻度的實際統計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼："THIS PROGRAM IS MY FAVORITE"。字符 ABCDEFGHIJKLMNOPQRSTUVWXYZ頻度18664132232103211547571532205763151485180238181161 選擇2，輸入THIS PROGRAM IS MY FAVORITE，屏幕上顯示01010同時文件codefile里面也出現相應的代碼選擇3，從code

5、file中調入代碼，終端顯示THIS PROGRAM IS MY FAVORITE，并且文件textfile中也相應的存入了這段話。選擇4，文件CodeFile以緊湊格式顯示在終端上。選擇5，將已在存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。選擇其他的數字，將出現出錯提示，并重新回到選擇菜單。2概要設計 2.1數據結構設計 InitHuffman(Huffman Hfm)；/初始化哈夫曼樹Encoding(Huffman Hfm)； /翻譯短文Decoding(Huffman Hfm)； /反譯編碼Print1(Huffma

6、n Hfm)； /打印文件編碼Print2(Huffman Hfm)； /打印哈夫曼樹typedef char *HuffmanCode;/動態分配數組存儲霍夫曼表碼表typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/動態分配數組存儲霍夫曼樹typedef struct HuffmanTree HT; char *c; int length; HuffmanCode HC;Huffman;/分配數組存儲字符串及其對應的霍夫曼樹Huffman Hfm;2.2系統模塊

7、設計哈夫曼樹編/譯碼系統錄入數據翻譯短文反譯編碼打印文件編碼打印哈夫曼樹退出系統3詳細設計#include <stdio.h>#include <string.h>#include <malloc.h>#include<stdlib.h>#define NULL 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAX_NUM 32767#define MAX 60typedef char *HuffmanCode;/動態分配數組存儲哈夫曼表碼表typedef struct unsign

8、ed int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/動態分配數組存儲哈夫曼樹typedef struct HuffmanTree HT; char *c; int length; HuffmanCode HC;Huffman;/全局結構體變量，來存儲字符與代碼/*-尋找權值最小的兩個節點-*/void Select(HuffmanTree HT,int end,int *s1,int *s2) int i; int min1=MAX_NUM; int min2; for (i=1;i<=end;i+)

9、/*遍歷查找權值最小的結點S1*/ if (HTi.parent=0&&HTi.weight<min1) *s1=i; min1=HTi.weight; min2=MAX_NUM; for(i=1;i<=end;i+)/*遍歷查找除S1外權值最小的結點S2*/ if(HTi.parent=0&&(*s1!=i)&&min2>HTi.weight) *s2=i; min2=HTi.weight; /*-對哈夫曼樹進行編碼-*/Huffman HuffmanCoding(Huffman Hfm) int i,n,m,s1,s2,st

10、art; int c,f; char *cd; n=Hfm.length; if(n<=1) return Hfm; m=2*n-1; for(i=n+1;i<=m;+i) /*選擇HT1.i-1中無雙親且權值最小的兩個節點，其序號為s1，s2*/ Select(Hfm.HT,i-1,&s1,&s2); Hfm.HTs1.parent=i; /*修改父親位置*/ Hfm.HTs2.parent=i; Hfm.HTi.lchild=s1; /*修改孩子位置*/ Hfm.HTi.rchild=s2; Hfm.HTi.weight=Hfm.HTs1.weight+Hfm.

11、HTs2.weight;/*父親結點權值為左右孩子權值之和*/ /*從葉子結點到根逆向求每個字符的哈夫曼編碼*/ Hfm.HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/*分配n個字符編碼的頭指針向量*/ cd=(char *)malloc(n*sizeof(char);/*分配求編碼的工作空間*/ cdn-1='0'/*編碼結束符*/ for(i=1;i<=n;+i)/*逐個字符求哈夫曼編碼*/ start=n-1;/*編碼結束符位置*/ for(c=i,f=Hfm.HTi.parent;f!=0;c=f,f=Hfm.HTf.pa

12、rent)/*從葉子到根逆向求編碼*/ if(c=Hfm.HTf.lchild) cd-start='0' else cd-start='1' Hfm.HCi=(char *)malloc(n-start)*sizeof(char); strcpy(Hfm.HCi,&cdstart);/*從cd復制編碼到Hfm.HC*/ free(cd); return Hfm;/*-錄入數據函數-*/Huffman InputHuffman(Huffman Hfm) int i,n; printf("nn*錄入數據*n"); printf(&quo

13、t;錄入的字符及其權值將保存于:hfmTree n"); printf("請輸入錄入字符個數: "); scanf("%d",&n); if(n<=1) printf("只有一個字符無需編碼"); printf("n"); printf("請輸入錄入字符個數: "); scanf("%d",&n); Hfm.HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); Hfm.c=(char *)malloc(n+1)

14、*sizeof(char); for(i=1;i<=n;i+) printf("請輸入字符:"); scanf("%s",&Hfm.ci); printf("請輸入字符權值:"); scanf("%d",&Hfm.HTi.weight); Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; for(;i<=2*n-1;+i) Hfm.HTi.weight=0; Hfm.HTi.parent=0; Hfm.HTi.lchild=0;

15、Hfm.HTi.rchild=0; Hfm.length=n; return Hfm; /*-初始化哈夫曼樹-*/Huffman InitHuffman(Huffman Hfm) int n,i; char x; FILE *fp; fp=fopen("hfmTree","rt");/*對文件hfmTree以讀文本的形式打開*/ if(fp=NULL) Hfm=InputHuffman(Hfm);/*調用InputHuffman函數，用戶輸入字符和相應權值存入哈夫曼數中*/ fp=fopen("hfmTree","wt&qu

16、ot;); fprintf(fp,"%dn",Hfm.length); for(i=1;i<=Hfm.length;i+) fprintf(fp,"%c %d ",Hfm.ci,Hfm.HTi.weight); rewind(fp); else printf("哈夫曼樹已經存在!n你是否需要重新初始化哈夫曼樹?('Y'or'N')n");/*詢問是否重新初始化*/ printf("請輸入選擇:"); scanf("%s",&x); if(x='

17、;Y') Hfm=InputHuffman(Hfm);/*調用InputHuffman函數，用戶輸入字符和相應權值存入哈弗曼數中*/ fp=fopen("hfmTree","w+"); fprintf(fp,"%dn",Hfm.length); for(i=1;i<=Hfm.length;i+) fprintf(fp,"%c %d ",Hfm.ci,Hfm.HTi.weight); rewind(fp); else fscanf(fp,"%dn",&n); Hfm.c=(c

18、har *)malloc(n+1)*sizeof(char); Hfm.HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); for(i=1;i<=n;i+) fscanf(fp,"%s %d ",&Hfm.ci,&Hfm.HTi.weight);/*將已經在文件中的字符和其對應的權重輸入到Hfm.ci和&Hfm.HTi.weight中*/ for(i=1;i<=n;i+)/*對每個節點初始化*/ Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0;

19、for(;i<=2*n-1;+i) Hfm.HTi.weight=0; Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; Hfm.length=n; fclose(fp); Hfm=HuffmanCoding(Hfm); return Hfm;/*-翻譯短文-*/void Encoding(Huffman Hfm)/*利用已建好的Huffman樹(如不在存，則從文件hfmTree中讀入)對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。*/ int i=0,j=0,n; char chMAX; FILE

20、 *fp,*fw; n=Hfm.length; printf("nn*翻譯短文*nn"); if(fw=fopen("ToBeTran","r+")=NULL)/*嘗試打開ToBeTran*/ printf("n請輸入需要翻譯成編碼的短文: "); scanf("%s",ch); printf("n"); fp=fopen("CodeFile","wt+"); else fscanf(fw,"%s",ch); fcl

21、ose(fw); while(chj) for(i=1;i<=n;i+) if(chj=Hfm.ci) printf("%s",Hfm.HCi); fprintf(fp,"%s",Hfm.HCi); break; j+; printf("n"); rewind(fp); fclose(fp);/*-反譯編碼-*/void Decoding(Huffman Hfm)/*利用已建好的Huffman樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。*/ HuffmanTree p; int i,n; int j

22、=0; char d500; char x; FILE *fp; n=Hfm.length; printf("nn*反譯*nn"); if(fp=fopen("CodeFile","r+")=NULL) printf("Please input the code:"); scanf("%s",d); else printf("文件中已經有編碼,是否需要更換編碼?('Y'or'N')n");printf("請輸入選擇:");s

23、canf("%s",&x);if(x='Y') printf("請輸入需要反譯的新編碼:"); scanf("%s",d); else fscanf(fp,"%s",d);/*將文件中的字符輸入到數組d中*/ fclose(fp); printf("n反譯后得到的短文為: "); fp=fopen("TextFile","wt+");/*以寫入文件的形式打開TextFile*/ while(dj) p=&Hfm.HT2*n-

24、1; while(p->lchild|p->rchild) if(dj='0') i=p->lchild; p=&Hfm.HTi; else i=p->rchild; p=&Hfm.HTi; j+; printf("%c",Hfm.ci); fprintf(fp,"%c",Hfm.ci); printf("n"); fclose(fp);/*-打印文件編碼-*/void Print1(Huffman Hfm) int i,n; int m=1; char ch; FILE* fp

25、rint; n=Hfm.length; printf("nn*打印文件編碼*nn"); fprint=fopen("CodeFile","rb"); while ( feof(fprint)=0 ) ch=fgetc(fprint); printf("%c",ch); m+; if (m%50=0) printf("n"); printf("n"); fclose(fprint);/*-打印哈夫曼樹-*/void Print2(Huffman Hfm) int i,n; n=

26、Hfm.length; printf("nn*打印哈夫曼樹*nn"); for(i=1;i<=n;i+) printf("n"); printf("Char:%ct",Hfm.ci); printf("Weight:%dt",Hfm.HTi.weight); printf("parent:%dt",Hfm.HTi.parent); printf("lchild:%dt",Hfm.HTi.lchild); printf("rchild:%dt",Hfm

27、.HTi.rchild); printf("Code:"); puts(Hfm.HCi); printf("n");/*-主函數-*/void main() Huffman Hfm; char k; while(1) printf("n");printf(" 歡迎進入哈夫曼編/譯碼系統:n");printf(" welcomen");printf("t 【1】錄入數據 n"); printf("t 【2】翻譯短文 n"); printf("t 【3】反譯編碼 n"); printf("t 【4】打印文件編碼 n");printf("t 【5】打印哈