數(shù)據結構課程設計實例

1、數(shù)據結構課程設計報告書題目：赫夫曼編碼系別:計算機科學與應用學號:051007222學生姓名：牛志遠指導教師：王亞楠完成日期：2007年2月1日需要分析赫夫曼編碼自己找一篇不少于 100 個單詞的英文文章，分析該文章中每一個字符的出 現(xiàn)概率（包括標點符號，區(qū)分大小寫） ，根據分析結果對文章中每一個字符進行 赫夫曼編碼，并將編碼原則存儲于一個獨立的文本文件中。最后，根據這個編 碼原則，將英文文章轉換為 01 串存儲于一個文本文件中。如：英文文章為 aaabbc則編碼規(guī)則為 a0b10c11英文文章將被轉化為 000101011 有能力的同學應該再編寫一個解碼程序，這個就不統(tǒng)一要求。二 概要設計1

2、 系統(tǒng)運行時， 將有 ifstream fs（"n.txt"） 句生成一文本文件， 用于存放要編 碼的英文文章。2. 然后，將有fs.get（c語句從文章中逐個讀入字符，其字符的ASCII碼值將存入int w2128的對應下標中，且對應w2i的值加1。之后，將ASCII 碼值及對應字符出現(xiàn)次數(shù)記錄于一動態(tài)分配的機構體tongji數(shù)組*w中。3. 然后，將調用赫夫曼編碼函數(shù)HuffmanCoding（HT,HC,w,n）對文章中出現(xiàn)的字符進行編碼，并將結果存于數(shù)組HC中。4. 有ofstream fpC'code.txt"）打開勇于存儲編碼后的文章。5. 對

3、01碼的解碼程序將有函數(shù) Decoding（執(zhí)行。三. 詳細設計#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;該結構體用于對統(tǒng)計文章中字符出現(xiàn)的次數(shù)，及該字符對應的整 數(shù)值（用于字符與編碼的轉換）typedef structunsigned int wei

4、ght;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/ 動態(tài)分配數(shù)組存儲赫夫曼樹typedef char *HuffmanCode;/ 動態(tài)分配數(shù)組存儲赫夫曼編碼表/Select(函數(shù)，用于選擇兩個 weight最小的結點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個字符的權值(均>0),構造赫夫曼樹HT,并求出n個字符 的赫夫曼編碼 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最小的兩個結點，其序號分 別為 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;/ 從葉子到根逆向求每個字符的赫夫曼編碼 /*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)/ 逐個字符求赫夫曼編碼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 個字符編碼的頭 指針向量char *cd;cd=(char*)malloc(n*sizeof(char);分配求編碼的工作空間 cdn-1='0'編碼結束符 int q=m;int cdlen=0;for(i=1;i<=m;+i) HTi.weight=0;/ 遍歷赫夫曼樹時用作結點狀態(tài)標志 while (q)if(HTq.weight=0)/ 向左HTq.weight=1;if(HTq.lchild!=0)q=HTq.lchild; cdcdlen+='0'else if(HTq.rchild=0)登記葉子結點的字符的編碼HCq=(c

10、har*)malloc(cdlen+1)*sizeof(char); 為第 i 個字符編碼分配空間cdcdlen='0'strcpy(HCq,cd);從 cd 復制編碼(串)到 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;/ 退到父結點，編碼長度 減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");/該語句將自動創(chuàng)建并打開一個“ n.txt ”文本文件，用于要翻譯的英文文章char c;int w2128;對應 128 個 ASCII 碼值for(int i=1;i<128;i+)w2i=0;while(fs.get(c)int a=c;w2a+;統(tǒng)計各個字符出現(xiàn)的次數(shù)fs.close();tongji *w;w=ne

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

13、equent<<endl;n=k;表明要對n=k個進行編碼HuffmanCoding(HT,HC,w,n);/ 調用赫夫曼編碼函數(shù)coutvv"各個字符對應編碼(每行顯示5個字符編碼)依次為："vvendl;for( i=1;i<=k;i+)coutvvHCivv" " if(i%5=0)coutvvendl;/顯示各個字符的編碼fs.open("n.txt");char ch;tongji *ptr;ptr=w;/創(chuàng)建并打開“ code.tx”文件，存儲編碼結果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()四 調試分析1 本題是利用赫夫曼樹對一篇英文文章進行編碼，起初感到無從下 手，通過老師的講解及對課本相關內容的分析，了解了其一般的 思路，掌握該設計的基本方法。經過小組的商討及不斷的調試， 完成了該項設計。2 對赫夫曼樹的構造及其編碼的詳細過程不會程序化，經過仔細看 書和同學交流，經過不斷調試，最終實現(xiàn)。3 設計中用到文件的輸入輸出，其中對于文件中字符的提取及把字 符讀入到文件不清楚，通過對相關知識的了解及不斷嘗試最終

15、得 到了解決。五 測試結果要編碼的英文文章及“ n.txt”內容為:記事本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訓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?編碼結果及

17、“ code.tx”為:屏幕顯示結果為:m程序'阿牛1Dc1hie' -詡的存儲位置對虛昶C】I碼值及由現(xià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將個字符對應編碼（每行顯示5個字符編碼依次為；01111601 06101001011111190011IS100011110100011111100110S000116100110101me> 01100 100061 11111kina0111101 10101 100016 010111000100001 01000000 10100 110111.011011101000110 01101 01000001Hl0001011110B0Presshe9 to continue附加：該程序對應解碼程序為：void Decoding(HuffmanCode HC,int n)int i=0,k,t;char c,ch;char *pstr;pstr=new cha