完整word版數(shù)據(jù)結(jié)構(gòu)課設(shè)報告word文檔良心出品

1、西安郵電大學(xué)（計算機(jī)學(xué)院）數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目：哈弗曼編/譯碼器計算機(jī)科學(xué)與技術(shù)專業(yè)名稱：1505計科級：班常昊生姓名： 04151160 學(xué)號（8 位）：指導(dǎo)教師：設(shè)計起止時間： 日月年2016122612年日2016月30一. 設(shè)計目的1. 訓(xùn)練學(xué)生靈括應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識，獨(dú)立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識，編寫程 序求解指定問題。2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；3. 捉高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力：4. 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)般規(guī)范進(jìn)行軟件開發(fā)，鞏固、深化學(xué)生的理論知識，捉高編 程水平，并在此過程中培

2、養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。二. 設(shè)計內(nèi)容利用哈夫曼編碼進(jìn)行信息通信可以大人提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但 是,這耍求在發(fā)送端通過個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼(復(fù) 原)。三. 概要設(shè)計1. 建立哈夫曼樹：讀入文件(*. souce),統(tǒng)計文件中字符出現(xiàn)的頻度，并以這些字符的頻度作為 權(quán)值，建立哈夫曼樹。這步需要做字符的統(tǒng)計所以考慮到人量數(shù)據(jù)的處理，需要考慮時間復(fù)雜度帶來的影響。所以采 用犧牲定的存儲空間的方法，以哈希農(nóng)的方法完成統(tǒng)計。因?yàn)樽址腶scii碼是0128不重復(fù) 的整數(shù)，所以采用不散列的簡單哈希衣。(例如：對于abcdabb

3、ccc的串的處理遍歷字符串， HZArray char i . HZ+)。在完成頻數(shù)的統(tǒng)計后，下步對整個128的數(shù)組中的頻數(shù)非零的字符按照從小到大的順序扌II：序。 考慮到穩(wěn)定/非穩(wěn)定排序?qū)τ诒绢}沒有什么影響，而且對于128的排序總數(shù)來說各種排序的方法 時間復(fù)雜度相對計算機(jī)的性能不會和差多少，所以采用簡單冒泡排序，而且，每次的扌II：序?qū)嶋H數(shù) 量都不會很多，加上flag的優(yōu)化以后排序效率還是不錯的。完成押:序后，根據(jù)哈弗曼樹的性質(zhì)，直接依據(jù)有序序列建立哈弗曼樹。這里沒有采用書上的方法， 書上的那個三叉鏈衣實(shí)際上是有缺點(diǎn)的，所以這里采用我自己的算法去建立哈夫曼樹，融合了廣 義衣的概念，talk

4、is cheap, show me the code,在后面的代碼部分會講清楚的。2. 編碼：利用已建立好的哈夫曼樹，獲得各個字符的哈夫曼編碼，并對正文進(jìn)行編碼，中。 (*. code)然后輸出編碼結(jié)果，并存入文件.前而建立哈弗曼樹的過程中直接把對應(yīng)字符的哈夫曼編碼存到個用作緩存的數(shù)組中，例如 codeArrayEal.code對應(yīng)的串是0000.這里也用到了簡單哈希農(nóng)的思維，減少了時間復(fù)雜度。 然后去獲取正文。獲取正文有兩種方式：自由錄入、讀取文件。獲取到正文以后，直接遍歷字串，并連續(xù)輸出對應(yīng)字符的哈弗曼編碼。例如：puts(codeArraycha譏a, data, code)。并同時把哈

5、夫曼編碼strcat到編碼總串中，便于保存。然 后將處理完成的總串顯示到0、1碼的顯示區(qū)。如果用戶輸入了保存(*.code)文件的路徑，等待用戶按下“save the code”就會執(zhí)行0、1 的位運(yùn)算數(shù)據(jù)壓縮模塊，然后會將壓縮后的數(shù)據(jù)存到指定路徑下并顯示存儲文件成功。3. 譯碼：利用已建立好的哈夫曼樹將文件（*. code）中的代碼進(jìn)行譯碼，并輸出譯碼結(jié)果，并存 入文件（*. decode）中.譯碼的操作和編碼類似，也是兩種錄入0、1的方式，不同之處只在于譯碼在讀取文件時候需要 先對壓縮過的文件執(zhí)行解壓的操作，使之變?yōu)?、1的字符串，進(jìn)-步對建立好的哈夫曼樹進(jìn)行 0左1右的方式去遍歷哈弗曼樹

6、。由于之前建立的哈弗曼樹不同于課本，所以這里的遍歷方式也 是不同的，但是原理大同小異。其他的操作也和編碼的過程大致和同。4. 利用位操作，實(shí)現(xiàn)文件的壓縮與解壓。（選作）我的想法是：01碼如果用char類型的數(shù)據(jù)去存儲的話是很浪費(fèi)空間的。因?yàn)閏har是占字節(jié) 的空間的，意味著存儲0、1的信息是存儲f 00000000. 00000001 o其實(shí)那么多0是不用存儲的。 所以用位運(yùn)算的指定位置0、置1的原理，使得連續(xù)字節(jié)的位都可以用來直接存儲0、K 所以用unsign int來存放0、1的位，這樣和當(dāng)于個無符號的整數(shù)可以存儲32位0、1信息, 壓縮比相當(dāng)感人。具體的代碼會放在下面的代碼部分。.1.

7、功能模塊圖；.2. 各個模塊詳細(xì)的功能描述。輸入輸出：因?yàn)樵摮绦蚴褂昧?口界面的交互設(shè)計，所以可以支持ipad設(shè)備或者在桌面模擬器 的環(huán)境中進(jìn)行觸摸、鼠標(biāo)點(diǎn)擊的操作。該部分的代碼是用objective-c寫的。因?yàn)榻缑娴牟僮?響應(yīng)是實(shí)時的，所以程序運(yùn)行期間可以重復(fù)操作。讀寫文件：讀、寫的操作是用C語言的FILE的操作函數(shù)完成的。建樹模塊：對已有序的節(jié)點(diǎn)數(shù)組建立樹并沒有按照書上的方法前葉f后非葉/節(jié)點(diǎn)，而是直接以各層的葉/節(jié)點(diǎn)作為介樹的根節(jié)點(diǎn)來使用，使用時讓左孩了指向左了樹的根節(jié)點(diǎn), 右孩了指向自身，最底層的葉（節(jié)點(diǎn)的左孩了指向0,右孩/指向白身。（指向0的原岡是：128 個ascii碼農(nóng)示的字

8、符定有的是不能直接從鍵盤上輸入的，所以排序完成后前而的0 定不會 是有效值）,從而解決了數(shù)組的人小的2n+l的問題，這時候只要人小為128的數(shù)組即可完成統(tǒng)計、 建樹。編碼模塊：逐個掃描字符，然后根據(jù)已經(jīng)建立起來的碼值數(shù)組直接轉(zhuǎn)換文本為碼值。其中碼值 數(shù)組可以在哈夫曼樹的建立過程中直接完成。解碼模塊：解碼實(shí)際上是個對哈夫曼樹的指定路徑遍歷。因?yàn)楣蚵幋a是前綴碼，所以直 接根據(jù)遍歷樹的情況去解碼。因?yàn)榇獯a的是個0、1的字符串，所以可以從前到后去依照0 遍歷左了樹1右了樹的原則去遍歷建立好的哈夫曼樹。但是因?yàn)楣蚵鼧涞慕Y(jié)構(gòu)差異，這里遍歷 的時候判斷葉子節(jié)點(diǎn)的方式不同于傳統(tǒng)的。壓縮/解壓模塊：壓縮

9、減壓模塊采用的位運(yùn)算較為簡單。通過判斷0、1串的信息采用位置數(shù)的 思維去實(shí)現(xiàn)，因?yàn)槭且評nsign的變量作為存儲的單元，所以每個unsign變量可以存儲32位1、 0信息。所以采用了 unsign的數(shù)組，這樣數(shù)組越大，存儲的量就越大（32*N位）。解壓模塊原理相同，不過不同的是要逐步確定unsign數(shù)組里的數(shù)的指定位是0還是1,同樣運(yùn) 算也比較簡單。四. 詳細(xì)設(shè)計1. 功能函數(shù)的調(diào)用關(guān)系圖addSouceFile getHZ initbuildbuildthecache addToBeDecodeaddToBeCodecodeToOldecodeToMassagesaveDeCodeFiles

10、aveCodeFile帶符號的為隨用戶操作調(diào)用的入口函數(shù)。.2 各功能函數(shù)的數(shù)據(jù)流程圖文本文件輸入文本/編碼/譯碼輸入編碼/編碼文 件成功創(chuàng)建輸出編碼編碼文件正確編碼文本文件輸出文本重點(diǎn)設(shè)計及編碼3統(tǒng)計頻數(shù)void getHZ ()/ int i=0,j;HZarray temp;for(i=0;i100;i+)if (!ail)break;elseif (ai != n)J=ai；bEjl.HZ 卄；簡單排序for (i=0; i128; i+) /for (j=i ;jbj.HZ)temp=bi;bi=bj;bj=temp;void build()/二叉樹建立int i=0, j=0, n

11、ow=l:while (bnow. HZ=0) now+;i=j=now;now+=l;while (bnowj. HZ=0&now 128)if (bi sum!=0&bj. sum!=0)if (bLiZ sum=bj sum)b now. sum=b i sum+b now. HZ; b now. r i ght=now; bnow left二i;i=now;elsebnow. sum=b j sum+bnow HZ; b now. r i ght=now; bnow left=j;j=now; elsej=now+l;辻(bnow-2. HZ=O) b now. sum=b i HZ+

12、b now. HZ; bnow left=i;bnow. right=now;i=now;now二i+1;j=now+l;if (bi sum=bj.HZ)b now sum=b i sum+b now. HZ;bnow left=i;bnow right=now;i=now;elsebj sum=bnow. HZ+bj HZ;bj left二now;bj. right二j;now=j;now+;root sum=bLi_. sum+bj sum;root left二i;root right=j;return ;- (void) decodeToMassage/解碼if (E_pathOfFi

13、le.text isEqualToString:) _ForNow setText:please load the souce file first; return;NSMutableString*temp=NSMutableStringalloc initWithString:_toBeDecode text;/tempappendString:NSStringstringWithFormat:temp.NSMutableString *tmpCode=NSMutableString allocj init;HZarray p=root;for (NSInteger i二0; itemp l

14、ength; i+) if (temp characterAtIndex:i=，0)P=bp left;if (p. left=0)tmpCode appendString:NSString stringWithFormat:p. data!;p=root;continue;elseif (p. sum二二root sum) p=broot right:elseappendString:NSStringtmpCodestringWithFormat:p. data!;p=root;continue;_ForNow setText:decoded successfully.;_toBeCode

15、setText:tmpCode:tmpCode setString:-(void) codeToOl/編碼if (E_pathOfFile.text isEqualToString:) _ForNow setText:please load the souce file first; return;NSString *temp=NSString allocZ init;temp二_toBeCode text;char tmp;NSMutableString *tempCode=NSMutableString allocinit; /NSLogtemp);for (NSInteger i二0;

16、itemp length; i+) tmp=temp characterAtIndex:ij;/printf(%c %sn, tmp, theCodeEtmp_ code);if (strlen (theCodetmp code) 1) _ForNow setText: NSString stringWithFormat:warning! %cis not in souce filereturn;tempCodeappendString:NSStringstringWithUTF8String:theCode(int)tmp code;/NSLogtempCode);_toBeDecode s

17、etText:NSString stringWithString:tempCode ;_ForNow setText:coded successfully.;tempCode setString:;/此段為位運(yùn)算的壓縮過程unsigned int s10 = 0, temp2=2147483648;char a500 = , 0;/char b100二 0 ;int i二0, n;int flag;strcpy(a, file);flag=l;for(n=0;(n10)&(istrlen(a);n+, flag=0)for (;il)break; elseflag=l;辻(ai=l)sn (t

18、emp2 (i2);/此段為解壓縮的過程unsigned int s10二0, k, temp二2147483648;char a100 = ，0;char b100 = ，0;int i=0, n;int flag;k二s0;i 二0;flag=l;for (n=0; (n10)&(il)break; elseflag=l;if (sn(sn廠(temp(i2) bi=J O;else/printf (%udn, sn);puts(b);return ;五. 測試數(shù)據(jù)及運(yùn)行結(jié)果1.正常測試數(shù)據(jù)和運(yùn)行結(jié)果正確解碼果結(jié)運(yùn)行據(jù)常2.異測試數(shù)及錯謀后綴文件依然保住未輸入文件名依然捉示正確保存.六. 調(diào)試情況，設(shè)計技巧及體會調(diào)試情況：主要是在位運(yùn)算的調(diào)試過程出現(xiàn)了很多未知情況，通過斷點(diǎn)調(diào)試逐漸拙除了故障。在樹的操作過程中因?yàn)樽约簩懥?種新的樹的結(jié)構(gòu)，所以也用了比較