數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)例

1、數(shù)據(jù)結(jié)構(gòu)課 程 設(shè) 計(jì) 報(bào) 告 書(shū)題目：赫 夫 曼 編 碼 系別：計(jì)算機(jī)科學(xué)與應(yīng)用 學(xué)號(hào)： 051007222 學(xué)生姓名： 牛 志 遠(yuǎn) 指導(dǎo)教師： 王亞楠 完成日期：2007年2月1日 一需要分析赫夫曼編碼自己找一篇不少于100個(gè)單詞的英文文章，分析該文章中每一個(gè)字符的出現(xiàn)概率（包括標(biāo)點(diǎn)符號(hào)，區(qū)分大小寫(xiě)），根據(jù)分析結(jié)果對(duì)文章中每一個(gè)字符進(jìn)行赫夫曼編碼，并將編碼原則存儲(chǔ)于一個(gè)獨(dú)立的文本文件中。最后，根據(jù)這個(gè)編碼原則，將英文文章轉(zhuǎn)換為01串存儲(chǔ)于一個(gè)文本文件中。如：英文文章為aaabbc則編碼規(guī)則為a-0 b-10c-11英文文章將被轉(zhuǎn)化為000101011 有能力的同學(xué)應(yīng)該再編寫(xiě)一個(gè)解碼程序，這

2、個(gè)就不統(tǒng)一要求。二 概要設(shè)計(jì)1 系統(tǒng)運(yùn)行時(shí)，將有ifstream fs("n.txt")句生成一文本文件，用于存放要編碼的英文文章。2 然后，將有fs.get(c)語(yǔ)句從文章中逐個(gè)讀入字符，其字符的ASCII碼值將存入int w2128的對(duì)應(yīng)下標(biāo)中，且對(duì)應(yīng)w2i的值加1。之后，將ASCII碼值及對(duì)應(yīng)字符出現(xiàn)次數(shù)記錄于一動(dòng)態(tài)分配的機(jī)構(gòu)體tongji數(shù)組*w中。3 然后，將調(diào)用赫夫曼編碼函數(shù)HuffmanCoding(HT,HC,w,n)對(duì)文章中出現(xiàn)的字符進(jìn)行編碼，并將結(jié)果存于數(shù)組HC中。4 有ofstream fp("code.txt")打開(kāi)勇于存儲(chǔ)編碼后

3、的文章。5 對(duì)01碼的解碼程序?qū)⒂泻瘮?shù)Decoding()執(zhí)行。三 詳細(xì)設(shè)計(jì)#include<iostream.h>#include<string.h>#include<stdlib.h>#define MAX_NUM 100000#include<fstream.h> typedef struct int index;/用于記錄字符的ASCII碼int frequent;/用于記錄字符出現(xiàn)的次數(shù) tongji;/該結(jié)構(gòu)體用于對(duì)統(tǒng)計(jì)文章中字符出現(xiàn)的次數(shù)，及該字符對(duì)應(yīng)的整數(shù)值（用于字符與編碼的轉(zhuǎn)換）typedef struct unsigned i

4、nt weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù)typedef char *HuffmanCode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表/Select()函數(shù)，用于選擇兩個(gè)weight最小的結(jié)點(diǎn)void Select(HuffmanTree HT,int end,int *s1,int *s2)/cout<<end<<endl; int i; int min1=MAX_NUM; int min2; for (i=1;i<=end;i+) if (HTi.paren

5、t=0&&HTi.weight<min1) *s1=i; min1=HTi.weight; min2=MAX_NUM; for(i=1;i<=end;i+) if(HTi.parent=0&&(*s1!=i)&&HTi.weight<min2) *s2=i; min2=HTi.weight; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,tongji w,int n)/w存放n個(gè)字符的權(quán)值（均>0），構(gòu)造赫夫曼樹(shù)HT，并求出n個(gè)字符的赫夫曼編碼HC i

6、f(n<=1)return; tongji *t=w+1; int m=2*n-1; HuffmanTree p;int i; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT,i=1;i<=n;+i,+t) pi.weight=t->frequent;pi.parent=0;pi.lchild=0;pi.rchild=0; /*p=*w,0,0,0; for(;i<=m;+i)pi.weight=0;pi.parent=0;pi.lchild=0;pi.rchild=0;/*p=0,0,0,0; int s1,s

7、2; for(i=n+1;i<=m;+i) /在HT1.i-1選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)，其序號(hào)分別為s1和s2。 Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight; /-從葉子到根逆向求每個(gè)字符的赫夫曼編碼-/*int start,c,f;HC=(HuffmanCode)malloc(n+1)*sizeof(char *);char *cd; cd=(char *)mall

8、oc(n*sizeof(char); cdn-1='0' for(i=1;i<=n;+i)/逐個(gè)字符求赫夫曼編碼 start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/從葉子到根逆向求編碼 if(c=HTf.lchild) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd);/釋放工作空間*/-從根到葉子求編碼- HC=(H

9、uffmanCode)malloc(n+1)*sizeof(char*);/分配n個(gè)字符編碼的頭指針向量 char *cd; cd=(char*)malloc(n*sizeof(char);/分配求編碼的工作空間 cdn-1='0'/編碼結(jié)束符 int q=m;int cdlen=0; for(i=1;i<=m;+i) HTi.weight=0;/遍歷赫夫曼樹(shù)時(shí)用作結(jié)點(diǎn)狀態(tài)標(biāo)志 while (q) if(HTq.weight=0)/向左 HTq.weight=1;if(HTq.lchild!=0)q=HTq.lchild; cdcdlen+='0'else

10、 if(HTq.rchild=0)/登記葉子結(jié)點(diǎn)的字符的編碼 HCq=(char*)malloc(cdlen+1)*sizeof(char);/為第i個(gè)字符編碼分配空間 cdcdlen='0'strcpy(HCq,cd);/從cd復(fù)制編碼（串）到HC else if(HTq.weight=1)/向右 HTq.weight=2;if(HTq.rchild!=0)q=HTq.rchild;cdcdlen+='1' else/HTq.weight=2,退回 HTq.weight=0;q=HTq.parent;-cdlen;/退到父結(jié)點(diǎn)，編碼長(zhǎng)度減1 /else /wh

11、ile/主函數(shù)void main() HuffmanTree HT;HuffmanCode HC; int n=128; / int w20=0,5,29,7,8,14,23,3,11; /for(int i=1;i<9;i+)cout<<HCi<<endl; ifstream fs("n.txt");/該語(yǔ)句將自動(dòng)創(chuàng)建并打開(kāi)一個(gè)“n.txt”文本文件，用于要翻譯的英文文章 char c; int w2128;/對(duì)應(yīng)128個(gè)ASCII碼值 for(int i=1;i<128;i+)w2i=0; while(fs.get(c) int a=

12、c;w2a+;/統(tǒng)計(jì)各個(gè)字符出現(xiàn)的次數(shù) fs.close(); tongji *w; w=new tongji100;/用new動(dòng)態(tài)分配空間 int k=0;cout<<"字符的存儲(chǔ)位置，對(duì)應(yīng)ASCCII碼值及出現(xiàn)次數(shù)依次為："<<endl; for(i=0;i<128;i+) if(w2i>0) k+;wk.frequent=w2i;/wk.frequent存儲(chǔ)字符出現(xiàn)次數(shù)wk.index=i;/存儲(chǔ)字符的ASCII碼值cout<<"k="<<k<<" "<

13、;<"i="<<i<<" "<<wk.frequent<<endl; n=k;/表明要對(duì)n=k個(gè)進(jìn)行編碼HuffmanCoding(HT,HC,w,n);/調(diào)用赫夫曼編碼函數(shù)cout<<"各個(gè)字符對(duì)應(yīng)編碼(每行顯示5個(gè)字符編碼)依次為："<<endl; for( i=1;i<=k;i+)cout<<HCi<<" "if(i%5=0)cout<<endl;/顯示各個(gè)字符的編碼 fs.open(&qu

14、ot;n.txt"); char ch; tongji *ptr;ptr=w; /創(chuàng)建并打開(kāi)“code.txt”文件，存儲(chǔ)編碼結(jié)果 ofstream fp("code.txt"); while(fs.get(ch) int b=ch; for(i=1;i<=k;i+) if(wi.index=b)fp<<HCi; fp.close();/main()四 調(diào)試分析1 本題是利用赫夫曼樹(shù)對(duì)一篇英文文章進(jìn)行編碼，起初感到無(wú)從下手，通過(guò)老師的講解及對(duì)課本相關(guān)內(nèi)容的分析，了解了其一般的思路，掌握該設(shè)計(jì)的基本方法。經(jīng)過(guò)小組的商討及不斷的調(diào)試，完成了該項(xiàng)設(shè)計(jì)。

15、2 對(duì)赫夫曼樹(shù)的構(gòu)造及其編碼的詳細(xì)過(guò)程不會(huì)程序化，經(jīng)過(guò)仔細(xì)看書(shū)和同學(xué)交流，經(jīng)過(guò)不斷調(diào)試，最終實(shí)現(xiàn)。3 設(shè)計(jì)中用到文件的輸入輸出，其中對(duì)于文件中字符的提取及把字符讀入到文件不清楚，通過(guò)對(duì)相關(guān)知識(shí)的了解及不斷嘗試最終得到了解決。五 測(cè)試結(jié)果要編碼的英文文章及“n.txt”內(nèi)容為：編碼結(jié)果及“code.txt”為：屏幕顯示結(jié)果為： 附加：該程序?qū)?yīng)解碼程序?yàn)椋簐oid Decoding(HuffmanCode HC,int n) int i=0,k,t; char c,ch; char *pstr; pstr=new charn; ifstream fs("code.txt");/打開(kāi)含01碼的文本 ofstream fp("dec