數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-哈夫曼樹(shù)

1、課 程 設(shè) 計(jì)課程設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 專 業(yè) 班 級(jí) ： 學(xué) 生 姓 名 ： 學(xué) 號(hào) ： 指 導(dǎo) 教 師 ： 李磊 課程設(shè)計(jì)時(shí)間： 2015.7.062015.7.10 計(jì)算機(jī)類 專業(yè)課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名專業(yè)班級(jí)學(xué)號(hào)題 目哈夫曼樹(shù)編/譯碼系統(tǒng)課題性質(zhì)A課題來(lái)源D指導(dǎo)教師李磊同組姓名無(wú)主要內(nèi)容1. 學(xué)習(xí)掌握并熟練運(yùn)用C語(yǔ)言進(jìn)行程序設(shè)計(jì),2.針對(duì)具體應(yīng)用問(wèn)題，選擇、設(shè)計(jì)和實(shí)現(xiàn)合適的抽象數(shù)據(jù)類型；3.進(jìn)行整體設(shè)計(jì)使各個(gè)函數(shù)之間緊密聯(lián)系起來(lái)；任務(wù)要求1.綜合運(yùn)用和融化所學(xué)理論知識(shí)，提高分析和解決實(shí)際問(wèn)題的能力，達(dá)到培養(yǎng)良好程序設(shè)計(jì)能力和習(xí)慣的目的，為開(kāi)發(fā)滿足問(wèn)題要求的小型應(yīng)用軟件奠定基礎(chǔ)，

2、達(dá)到軟件工程的綜合性基礎(chǔ)訓(xùn)練的目的。,2.完成需求分析報(bào)告，報(bào)告中對(duì)關(guān)鍵部分給出圖表說(shuō)明。要求格式規(guī)范，工作量飽滿。參考文獻(xiàn)C語(yǔ)言程序設(shè)計(jì)（第三版）譚浩強(qiáng) 清華大學(xué)出版社C Primer Plus(第5版) Stephenprata 北京人民郵電出版社 審查意見(jiàn)指導(dǎo)教師簽字：教研室主任簽字： 年 月 日目錄目錄11需求分析21.1系統(tǒng)介紹21.2程序的輸入和輸出21.3程序要達(dá)到的功能21.4調(diào)試過(guò)程介紹22概要設(shè)計(jì)32.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)32.2系統(tǒng)模塊設(shè)計(jì)33詳細(xì)設(shè)計(jì)44系統(tǒng)演示124.1主界面124.2數(shù)據(jù)錄入124.3翻譯短文134.4反譯編碼134.5打印文件編碼144.6打印哈夫曼樹(shù)1

3、45運(yùn)行環(huán)境156課程心得總結(jié)16參考文獻(xiàn)；16第 15 頁(yè) 共 16 頁(yè)1需求分析1.1系統(tǒng)介紹利用Huffman編碼進(jìn)行通信可以大大提高信道利用率縮短信息傳輸時(shí)間，降低傳輸成本，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編譯碼系統(tǒng)。此程序就是為這樣的信息收發(fā)站寫一個(gè)Huffman碼的編譯碼系統(tǒng)。1.2程序的輸入和輸出從終端讀入字符集大小n，以及n個(gè)字符及各個(gè)字符的權(quán)值，建立赫夫曼樹(shù)，并將它存儲(chǔ)到文件hfmTree中；利用已建好的赫夫曼樹(shù)將文件中的字符編碼，如果赫夫曼樹(shù)不在內(nèi)存中，則從

4、文件hfmTree中讀取到內(nèi)存；將譯得的代碼存到文件CodeFile中；利用已建好的赫夫曼樹(shù)對(duì)CodeFile中的代碼進(jìn)行譯碼，將結(jié)果存入文件TextFile中；最后將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫入文件TreePrint中。1.3程序要達(dá)到的功能用戶可以利用菜單根據(jù)自己的需要來(lái)選擇要進(jìn)行編碼或是譯碼,并將轉(zhuǎn)換好的字符或編碼以文件的形式存到相應(yīng)的文件里面。1.4調(diào)試過(guò)程介紹（l）利用教材中的數(shù)據(jù)調(diào)試程序。（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：THIS PROGRAM IS MY FAV

5、ORITE。字符 ABCDEFGHIJKLMNOPQRSTUVWXYZ頻度18664132232103211547571532205763151485180238181161 選擇2，輸入THIS PROGRAM IS MY FAVORITE，屏幕上顯示1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010同時(shí)文件codefile里面也出現(xiàn)相應(yīng)的代碼選擇3，從codefile中調(diào)入代碼，終端顯示THIS PROGR

6、AM IS MY FAVORITE，并且文件textfile中也相應(yīng)的存入了這段話。選擇4，文件CodeFile以緊湊格式顯示在終端上。選擇5，將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫入文件TreePrint中。選擇其他的數(shù)字，將出現(xiàn)出錯(cuò)提示，并重新回到選擇菜單。2概要設(shè)計(jì) 2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) InitHuffman(Huffman Hfm)；/初始化哈夫曼樹(shù)Encoding(Huffman Hfm)； /翻譯短文Decoding(Huffman Hfm)； /反譯編碼Print1(Huffman Hfm)； /打印文件編碼Print2(H

7、uffman Hfm)； /打印哈夫曼樹(shù)typedef char *HuffmanCode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)霍夫曼表碼表typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)霍夫曼樹(shù)typedef struct HuffmanTree HT; char *c; int length; HuffmanCode HC;Huffman;/分配數(shù)組存儲(chǔ)字符串及其對(duì)應(yīng)的霍夫曼樹(shù)Huffman Hfm;2.2系統(tǒng)模塊設(shè)計(jì)哈夫曼樹(shù)編/譯碼系統(tǒng)錄入數(shù)據(jù)翻譯短文反譯編

8、碼打印文件編碼打印哈夫曼樹(shù)退出系統(tǒng)3詳細(xì)設(shè)計(jì)#include #include #include #include#define NULL 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAX_NUM 32767#define MAX 60typedef char *HuffmanCode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼表碼表typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)type

9、def struct HuffmanTree HT; char *c; int length; HuffmanCode HC;Huffman;/全局結(jié)構(gòu)體變量，來(lái)存儲(chǔ)字符與代碼/*-尋找權(quán)值最小的兩個(gè)節(jié)點(diǎn)-*/void Select(HuffmanTree HT,int end,int *s1,int *s2) int i; int min1=MAX_NUM; int min2; for (i=1;i=end;i+)/*遍歷查找權(quán)值最小的結(jié)點(diǎn)S1*/ if (HTi.parent=0&HTi.weightmin1) *s1=i; min1=HTi.weight; min2=MAX_NUM; f

10、or(i=1;iHTi.weight) *s2=i; min2=HTi.weight; /*-對(duì)哈夫曼樹(shù)進(jìn)行編碼-*/Huffman HuffmanCoding(Huffman Hfm) int i,n,m,s1,s2,start; 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中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2*/ Select(Hfm.HT,i-1,&s1,&s2); Hfm.HTs1.parent=i; /*修改父親位置*/ Hfm.HTs

11、2.parent=i; Hfm.HTi.lchild=s1; /*修改孩子位置*/ Hfm.HTi.rchild=s2; Hfm.HTi.weight=Hfm.HTs1.weight+Hfm.HTs2.weight;/*父親結(jié)點(diǎn)權(quán)值為左右孩子權(quán)值之和*/ /*從葉子結(jié)點(diǎn)到根逆向求每個(gè)字符的哈夫曼編碼*/ Hfm.HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/*分配n個(gè)字符編碼的頭指針向量*/ cd=(char *)malloc(n*sizeof(char);/*分配求編碼的工作空間*/ cdn-1=0;/*編碼結(jié)束符*/ for(i=1;i=n;+i)

12、/*逐個(gè)字符求哈夫曼編碼*/ start=n-1;/*編碼結(jié)束符位置*/ for(c=i,f=Hfm.HTi.parent;f!=0;c=f,f=Hfm.HTf.parent)/*從葉子到根逆向求編碼*/ 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復(fù)制編碼到Hfm.HC*/ free(cd); return Hfm;/*-錄入數(shù)據(jù)函數(shù)-*/Huffman InputHuffman(Huf

13、fman Hfm) int i,n; printf(nn*錄入數(shù)據(jù)*n); printf(錄入的字符及其權(quán)值將保存于:hfmTree n); printf(請(qǐng)輸入錄入字符個(gè)數(shù): ); scanf(%d,&n); if(n=1) printf(只有一個(gè)字符無(wú)需編碼); printf(n); printf(請(qǐng)輸入錄入字符個(gè)數(shù): ); scanf(%d,&n); Hfm.HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); Hfm.c=(char *)malloc(n+1)*sizeof(char); for(i=1;i=n;i+) printf(請(qǐng)輸入字符:);

14、scanf(%s,&Hfm.ci); printf(請(qǐng)輸入字符權(quán)值:); 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; Hfm.HTi.rchild=0; Hfm.length=n; return Hfm; /*-初始化哈夫曼樹(shù)-*/Huffman InitHuffman(Huffman Hfm) int n,i; char x; FILE

15、 *fp; fp=fopen(hfmTree,rt);/*對(duì)文件hfmTree以讀文本的形式打開(kāi)*/ if(fp=NULL) Hfm=InputHuffman(Hfm);/*調(diào)用InputHuffman函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈夫曼數(shù)中*/ fp=fopen(hfmTree,wt); 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(哈夫曼樹(shù)已經(jīng)存在!n你是否需要重新初始化哈夫曼樹(shù)?(YorN)n);

16、/*詢問(wèn)是否重新初始化*/ printf(請(qǐng)輸入選擇:); scanf(%s,&x); if(x=Y) Hfm=InputHuffman(Hfm);/*調(diào)用InputHuffman函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈弗曼數(shù)中*/ 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=(char *)malloc(n+1)*sizeof(

17、char); Hfm.HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); for(i=1;i=n;i+) fscanf(fp,%s %d ,&Hfm.ci,&Hfm.HTi.weight);/*將已經(jīng)在文件中的字符和其對(duì)應(yīng)的權(quán)重輸入到Hfm.ci和&Hfm.HTi.weight中*/ for(i=1;i=n;i+)/*對(duì)每個(gè)節(jié)點(diǎn)初始化*/ 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.

18、HTi.lchild=0; Hfm.HTi.rchild=0; Hfm.length=n; fclose(fp); Hfm=HuffmanCoding(Hfm); return Hfm;/*-翻譯短文-*/void Encoding(Huffman Hfm)/*利用已建好的Huffman樹(shù)(如不在內(nèi)存，則從文件hfmTree中讀入)對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。*/ int i=0,j=0,n; char chMAX; FILE *fp,*fw; n=Hfm.length; printf(nn*翻譯短文*nn); if(fw=fopen(ToBe

19、Tran,r+)=NULL)/*嘗試打開(kāi)ToBeTran*/ printf(n請(qǐng)輸入需要翻譯成編碼的短文: ); scanf(%s,ch); printf(n); fp=fopen(CodeFile,wt+); else fscanf(fw,%s,ch); fclose(fw); while(chj) for(i=1;ilchild|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); fcl

20、ose(fp);/*-打印文件編碼-*/void Print1(Huffman Hfm) int i,n; int m=1; char ch; FILE* fprint; 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);/*-打印哈夫曼樹(shù)-*/void Print2(Huffman Hfm) int

21、 i,n; n=Hfm.length; printf(nn*打印哈夫曼樹(shù)*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.HTi.rchild); printf(Code:); puts(Hfm.HCi); printf(n);/*-主函數(shù)-*/void main() Huffman Hfm; char k; while(1) printf(n);printf( 歡迎進(jìn)入哈夫曼編/譯碼系統(tǒng):n);printf( welcomen);printf(t 【1】錄入數(shù)據(jù) n); printf(t 【2】翻譯短文 n); printf(t 【3】反譯編碼 n); printf(t 【4】打印文件編碼 n);printf(t 【5】打印哈夫曼樹(shù) n);printf(t 【0】退出系統(tǒng) n);printf(n); printf(請(qǐng)輸入你的選