數(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ī)則為 a0b10c11英文文章將被轉(zhuǎn)化為 000101011 有能力的同學(xué)應(yīng)該再編寫(xiě)一個(gè)解碼程序，這個(gè)就不統(tǒng)一要求。二 概要設(shè)計(jì)1

2、 系統(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 fpC'code.txt"）打開(kāi)勇于存儲(chǔ)編碼后的文章。5. 對(duì)

3、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 structint 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 structunsigned int wei

4、ght;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.parent=0&&a

5、mp;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è)字符 的赫夫曼編碼 HCif(n<=1)retur

6、n;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,s2;for(i=n+1;i<=m;+i

7、)在HT1i-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 *)malloc(n*sizeof(char);cdn-1=&

8、#39;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=(HuffmanCode)malloc(n+1)*sizeof(cha

9、r*); 分配 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 if(HTq.rchild=0)登記葉子結(jié)點(diǎn)的字符的編碼HCq=(c

10、har*)malloc(cdlen+1)*sizeof(char); 為第 i 個(gè)字符編碼分配空間cdcdlen='0'strcpy(HCq,cd);從 cd 復(fù)制編碼(串)到 HCelse 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/while/主函數(shù)void main()HuffmanTree HT;Huffm

11、anCode 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=c;w2a+;統(tǒng)計(jì)各個(gè)字符出現(xiàn)的次數(shù)fs.close();tongji *w;w=ne

12、w tongji100;用new動(dòng)態(tài)分配空間int k=0;coutvv"字符的存儲(chǔ)位置，對(duì)應(yīng)ASCCII碼值及出現(xiàn)次數(shù)依次為："<<endl;for(i=0;iv128;i+)if(w2i>0)k+;wk.frequent=w2i;/wk.frequent 存儲(chǔ)字符出現(xiàn)次數(shù)wk.index=i;存儲(chǔ)字符的ASCII碼值cout<<"k="<<k<<""<<"i="<<i<<" "<<wk.fr

13、equent<<endl;n=k;表明要對(duì)n=k個(gè)進(jìn)行編碼HuffmanCoding(HT,HC,w,n);/ 調(diào)用赫夫曼編碼函數(shù)coutvv"各個(gè)字符對(duì)應(yīng)編碼(每行顯示5個(gè)字符編碼)依次為："vvendl;for( i=1;i<=k;i+)coutvvHCivv" " if(i%5=0)coutvvendl;/顯示各個(gè)字符的編碼fs.open("n.txt");char ch;tongji *ptr;ptr=w;/創(chuàng)建并打開(kāi)“ code.tx”文件，存儲(chǔ)編碼結(jié)果ofstream fp("code.txt&

14、quot;);while(fs.get(ch)int b=ch; for(i=1;iv=k;i+)if(wi.index=b)fpvvHCi;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ì)。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í)的了解及不斷嘗試最終

15、得 到了解決。五 測(cè)試結(jié)果要編碼的英文文章及“ n.txt”內(nèi)容為:記事本Ifel文件0）編輯電）格式Q）查看電）幫肋如Read aloud the ice on hearing this words f the heart can not help 人 a burst of constringency t frank 虧ayf he really leave the main reason of the ice snow city is because of oneself, but T stillhaue a reason, be For stay auay this how many a

16、ttractions the beautiful uoman of the pole, he knoui, beautiful uoman although goodt but ould let u訓(xùn)n denoralized,10009100OQ did not thought of f snou is quiet and ould fnake track For the oneself to come out t still wanting to travel ouer uith oneself together big six, this how can he promise?編碼結(jié)果及

17、“ code.tx”為:屏幕顯示結(jié)果為:m程序'阿牛1Dc1hie' -詡的存儲(chǔ)位置對(duì)虛昶C】I碼值及由現(xiàn)錢(qián)共磁古:k=li-102k=2i=3297k=3i=4413k=4i=48Sk=5i=492kWi-631k=7i=821k=8i-9734T1-98&k=10i=9911kll110011k=12i=10146k=131=10213k-141=103Sk=15i=10425k=16i=10524k=17i=1074k=18i=10821k=19i-1098k=2B1=11027k=21i=lll42k=22i-1123k=23i=1131k=24i-11418*

18、5i=11523k=2fc111640b<-27i=117151<=281=1184*=291=119141«=30i-1201=31i=1217b切i-1221將個(gè)字符對(duì)應(yīng)編碼（每行顯示5個(gè)字符編碼依次為；01111601 06101001011111190011IS100011110100011111100110S000116100110101me> 01100 100061 11111kina0111101 10101 100016 010111000100001 01000000 10100 110111.011011101000110 01101 01000001Hl0001011110B0Presshe9 to continue附加：該程序?qū)?yīng)解碼程序?yàn)椋簐oid Decoding(HuffmanCode HC,int n)int i=0,k,t;char c,ch;char *pstr;pstr=new cha