《C++程序設(shè)計(jì)》項(xiàng)目結(jié)題報(bào)告

1、C+程序設(shè)計(jì)項(xiàng)目結(jié)題報(bào)告目錄C+程序設(shè)計(jì)項(xiàng)目結(jié)題報(bào)告小組名稱： txt 項(xiàng)目名稱： zip 壓縮軟件 小組成員：唐美玲 劉亞楠 黃李成蹊2013 年 5 月 18目錄1項(xiàng)目結(jié)題報(bào)告摘要II2項(xiàng)目概述12.1項(xiàng)目背景12.2系統(tǒng)目標(biāo) 13需求分析23.1系統(tǒng)功能分析23.2系統(tǒng)性能指標(biāo)23.3系統(tǒng)平臺24系統(tǒng)設(shè)計(jì)34.1總體設(shè)計(jì)34.1.1系統(tǒng)總體結(jié)構(gòu) 34.1.2與子系統(tǒng)接口 34.2全局?jǐn)?shù)據(jù)結(jié)構(gòu)說明34.2.1 常量34.2.2 變量44.2.3 數(shù)據(jù)結(jié)構(gòu) 44.3各子系統(tǒng)結(jié)構(gòu)54.4數(shù)據(jù)文件設(shè)計(jì)64.4.1數(shù)據(jù)文件存放位置及命名規(guī)范 64.4.2數(shù)據(jù)文件格式規(guī)范65算法設(shè)計(jì)75.1算法3

2、錯(cuò)誤！未定義書簽。5.2算法2 錯(cuò)誤！未定義書簽。5.3算法3 錯(cuò)誤！未定義書簽。5.4 算法 N 116系統(tǒng)實(shí)現(xiàn)136.1設(shè)計(jì)過程136.2開發(fā)過程 146.3測試過程147使用說明157.1主菜單的使用 157.2具體各項(xiàng)功能的使用 158項(xiàng)目總結(jié)18I程序設(shè)計(jì)與算法語言項(xiàng)目結(jié)題報(bào)告摘要、關(guān)鍵詞1項(xiàng)目結(jié)題報(bào)告摘要隨著時(shí)代的發(fā)展人們對數(shù)據(jù)通信的要求越來越高，為了方便zip文件的傳輸和節(jié)約磁盤的空間，我們想利用哈夫曼算法編寫 出一個(gè)用來壓縮和解壓文本文件的壓縮軟件，利用二進(jìn)制存 儲的方法減小文件的大小，通過查閱大量的資料和不斷的嘗 試，最后我們編出了一個(gè)可以用來壓縮和解壓文本文件的 壓縮軟件。

3、關(guān)鍵詞：壓縮解壓縮哈夫曼算法二進(jìn)制文件文本文件#程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告 2項(xiàng)目概述2項(xiàng)目概述2.1項(xiàng)目背景隨著時(shí)代的發(fā)展，人們對數(shù)據(jù)通信的要求越來越高，為了方 便文件的傳輸和節(jié)約磁盤的空間，人們希望在不影響文件質(zhì) 量的同時(shí)文件的大小越小越好。2.2系統(tǒng)目標(biāo)1. 該壓縮軟件能夠無損的壓縮小于10M的文本文件2該壓縮軟件能夠?qū)嚎s后的文件完整的解壓為原文件3. 該軟件的壓縮率盡可能的高4. 該軟件的壓縮時(shí)間和解壓時(shí)間盡可能的短i程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告 3需求分析3需求分析3.1系統(tǒng)功能分析1. 該壓縮軟件能夠無損的壓縮小于 10M的文本文件 2該壓縮軟件能夠?qū)嚎s后的文件完整的解壓為原文件

4、3.2系統(tǒng)性能指標(biāo)1. 該軟件的壓縮率盡可能的高2. 該軟件的壓縮時(shí)間和解壓時(shí)候盡可能的短3.3系統(tǒng)平臺VC+6.0.#程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告 4系統(tǒng)設(shè)計(jì)4系統(tǒng)設(shè)計(jì)4.1總體設(shè)計(jì)4.1.1系統(tǒng)總體結(jié)構(gòu)4.2全局?jǐn)?shù)據(jù)結(jié)構(gòu)說明4.2.1常量const int N = 256N表示字符種類的最大值422變量int Leaf, Sum, Len gth, CodeLe ngthLeaf:總?cè)~子個(gè)數(shù)；Sum：總節(jié)點(diǎn)個(gè)數(shù)；Length :源文件字符總長；CodeLe ngth壓縮后編碼的長度4.2.3數(shù)據(jù)結(jié)構(gòu)int num100;num數(shù)組用來存儲各種長度的編碼個(gè)數(shù)char daiyasuo50;da

5、iyasuo數(shù)組用來存儲用戶輸入的待壓縮文件的文件名char daijieya50;daijieya數(shù)組用來存儲用戶輸入的壓縮后和待解壓文件的文件名char jieyahou50;jieyahou數(shù)組用來存儲用戶輸入的解壓后的文件的文件名struct NodeNode *pare nt;Node *left;Node *right;un sig ned char info;int weight;char code1000;結(jié)構(gòu)體Node用來存儲節(jié)點(diǎn)，節(jié)點(diǎn)中包含父節(jié)點(diǎn)，左孩子，右孩子，字符, 出現(xiàn)次數(shù)，編碼4.3各子系統(tǒng)結(jié)構(gòu)4.3.1壓縮編碼結(jié)束4.3.2解壓4.4數(shù)據(jù)文件設(shè)計(jì)4.4.1數(shù)據(jù)文件

6、存放位置及命名規(guī)范存放位置：待壓縮文件，壓縮后文件，待解壓文件和解壓后文件都存放在程序所在文件夾的目錄下 命名規(guī)范：所有的文件均以txt的格式存儲，名稱由用戶自己確定4.4.2數(shù)據(jù)文件格式規(guī)范無.5 .程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告 5算法設(shè)計(jì)5算法設(shè)計(jì)5.1編碼過程5.1.1編碼過程中的總算法計(jì)算機(jī)編程實(shí)現(xiàn)時(shí)，首先統(tǒng)計(jì)帶編碼的文本文件中各個(gè)字符出現(xiàn)的次數(shù)，然后將概率作為節(jié)點(diǎn)的權(quán)值，并進(jìn)行排序，然后構(gòu)建huffman樹。編碼時(shí)從葉子節(jié)點(diǎn)出發(fā)，如果這個(gè)節(jié)點(diǎn)在左子樹上，則編碼0,否則編碼1,直到根節(jié)點(diǎn)為止，然后反序，所得到的01序列即為該葉子節(jié)點(diǎn)的編碼。所有葉子節(jié)點(diǎn)的編碼構(gòu)成一一個(gè)碼本。將碼本存儲，然

7、后遍歷文本文件，將字符轉(zhuǎn)化為編碼，再轉(zhuǎn)化為壓縮后的txt文件。5.1.2各函數(shù)的具體算法申請大小為2*n的結(jié)構(gòu)體數(shù)組(n=256)將結(jié)構(gòu)體初始化存入各字符讀取文件，統(tǒng)計(jì)頻率void File(Node *array):將字符轉(zhuǎn)化為相應(yīng)的ascii碼，然后將數(shù)組中與相對應(yīng)的位置處，(即數(shù)組下標(biāo)為該字符所對應(yīng)的的ascii碼)將出現(xiàn)次數(shù)加 1，最后得到含有各字符出現(xiàn)頻率的結(jié)構(gòu)體數(shù)組，排序 void Sort(Node *array):按出現(xiàn)次數(shù)由大到小排序，運(yùn)用冒泡排序法。統(tǒng)計(jì)葉子節(jié)點(diǎn)的數(shù)目leaf建樹 Node BuildTree(Node *array):在數(shù)組中未利用的部分申請節(jié)點(diǎn)作為父節(jié)點(diǎn)

8、，遍歷數(shù)組中前半部分尋找頻率最小的元.9 .素，作為該父節(jié)點(diǎn)的左孩子，再進(jìn)行遍歷尋找頻率第二小的作為右孩子，父節(jié)點(diǎn)的頻率為兩個(gè)頻率的加和，第二次遍歷時(shí)只遍歷沒有父節(jié)點(diǎn)的元素，避免將節(jié)點(diǎn)重復(fù)納入樹中。重復(fù)以上過程，。得到對應(yīng)的二進(jìn)制碼本 void Code(Node *array) ：從葉子節(jié)點(diǎn)出發(fā)，如果這個(gè)節(jié)點(diǎn)在左子樹上，則編碼0，否則編碼1父節(jié)點(diǎn)上移一位。重復(fù)以上過程，直到根節(jié)點(diǎn)為止。然后反序：將由葉子節(jié)點(diǎn)開始的編碼序列化為由根節(jié)點(diǎn)開始編碼的序列(為了符合習(xí)慣)，所得到的01序列即為該葉子節(jié)點(diǎn)的編碼。將碼本序列存入到結(jié)構(gòu)體數(shù)組中。編碼 void BinaryCode(const char *

9、inaddress, const char *outaddress, Node*array)遍歷整個(gè)文件，將其轉(zhuǎn)化為對應(yīng)的編碼，并將編碼轉(zhuǎn)化為字符，并將對應(yīng)字符寫入文件，當(dāng)二進(jìn)制碼不是8的倍數(shù)時(shí)，在結(jié)尾八個(gè) 0以后再進(jìn)行對應(yīng)字符的轉(zhuǎn)化，統(tǒng)計(jì)字節(jié)數(shù)在壓縮后文件的末尾寫入碼本，存入原字符，編碼的位數(shù)及編碼，每個(gè)字符編碼不夠八位的地方用零補(bǔ)齊，存入文件。5.2解碼過程5.2.1 void GetI nfo(Node *array)函數(shù)作用：從壓縮文件中讀取碼本，把碼本中的數(shù)據(jù)轉(zhuǎn)換后存入數(shù)組中，構(gòu)成數(shù)組碼本 算法：程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告 5算法設(shè)計(jì)5.2.2 void SortCompress(N

10、ode *array) 函數(shù)作用：將碼本數(shù)組按照各個(gè)字符編碼的長度從短到長排序# .程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告 5算法設(shè)計(jì)ii523 void Decode(Node *array) 函數(shù)作用：將壓縮文件解壓縮并存到文件中程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告 5算法設(shè)計(jì)524 int Match(Node *array, char *codetemp, i nt & pos)函數(shù)作用：將待匹配編碼與碼本數(shù)組中的編碼進(jìn)行匹配算法：計(jì)算編碼長度小于現(xiàn)在待匹配編碼的長度的字符 的種類個(gè)數(shù)掃描碼本數(shù)組中與待匹配的編碼的長度相等的編碼，并與待匹配的編碼進(jìn)行匹配# .程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告 6系統(tǒng)實(shí)現(xiàn)6

11、系統(tǒng)實(shí)現(xiàn)6.1設(shè)計(jì)過程1.查閱資料Zip壓縮程序的題目是這樣的：zip數(shù)據(jù)壓縮程序只要你愿意，你完全可以做一個(gè)自己的zip壓縮軟件！似乎很難？其實(shí)這只是MIT “Practical Programming in C” 的一個(gè)實(shí)驗(yàn)項(xiàng)目。請?jiān)L問 MIT OCW 網(wǎng)站： /courses/electrical-e ngin eeri ng-a nd-computer-scie nce/6-087-practic al-programming-in-c-january-iap-2010/labs/,請參閱 Lab 2 的文檔。里面提供了 step by step模式的

12、開發(fā)原理，并提供大部分源碼。消化吸收了，就是你的了！難度：所以在確定選題之后我們首先參閱了MIT OCW網(wǎng)站上Lab 2的文檔，了解了哈夫曼算法這一算法，然后上網(wǎng)查找了許多關(guān)于哈夫曼算法的資料。2. 比較各種方法通過對各種方法的比較，我們最后決定在靜態(tài)哈夫曼，動態(tài)哈夫曼和范式哈夫曼 這三種方法中選一種。動態(tài)哈夫曼速度更快，范式哈夫曼需要的內(nèi)存小，靜態(tài)哈 夫曼方法簡單3. 確定最終的方法雖然動態(tài)哈夫曼和范式哈夫曼都比靜態(tài)哈夫曼效果好，但我們擔(dān)心自己不能在規(guī)定的時(shí)間內(nèi)完成任務(wù)，所以經(jīng)過我們小組成員的討論，最后我們確定了先采用靜 態(tài)哈夫曼，如果時(shí)間允許的話我們再嘗試著使用動態(tài)哈夫曼的方法。而靜態(tài)哈夫

13、 曼的解壓又分為重構(gòu)哈夫曼樹和直接根據(jù)編碼從碼本中找對應(yīng)的字符這兩種，重構(gòu)哈夫曼樹速度更快，但直接去碼本中找出錯(cuò)率更低，所以我們決定解壓的時(shí)候 采用根據(jù)編碼直接去碼本中找的方法。為了使壓縮后的文件盡量小，我們決定壓縮后的文件以二進(jìn)制的形式存儲。綜上所述，我們確定的最終方案是：壓縮采用構(gòu)造哈夫曼樹，編碼的方法，壓縮后的碼本和文件以二進(jìn)制的形式存儲，解壓采用每讀入一個(gè)編碼就去碼本中找匹配的字符的方法6.2開發(fā)過程在開發(fā)過程中，根據(jù)一開始時(shí)確定的任務(wù)分配，劉亞楠負(fù)責(zé)壓縮文件部分，黃李 成蹊負(fù)責(zé)編碼的二進(jìn)制轉(zhuǎn)換和二進(jìn)制文件的讀取存儲，唐美玲負(fù)責(zé)解壓縮文件部 分，每個(gè)人在規(guī)定的時(shí)間內(nèi)完成自己負(fù)責(zé)的那部分

14、的代碼，并進(jìn)行測試，然后將三個(gè)人的代碼合為一份完整的代碼。6.3測試過程1在個(gè)人完成自己代碼的時(shí)間里，每個(gè)人對自己的代碼進(jìn)行了測試2.在將三份代碼合為一份后，我們先用一個(gè)只輸入了幾個(gè)字母的很小的文件對程 序進(jìn)行了測試和單步調(diào)試，再用幾個(gè)較大的文本文件對程序進(jìn)行了測試，同時(shí)對 幾種可能出現(xiàn)的出錯(cuò)情況進(jìn)行了測試。13 .程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告 7使用說明17 .7使用說明7.1主菜單的使用1.運(yùn)行程序，出現(xiàn)如圖所示主菜單: H.學(xué)習(xí)址4 4訃飆尢項(xiàng)目說頂目苗姿Dab裁選擇您礙亍的撫作解壓如果用戶想壓縮文件就通過鍵盤輸入 1如果用戶想解壓文件就通過鍵盤輸入 27.2具體各項(xiàng)功能的使用1壓縮1）運(yùn)

15、行程序01學(xué)習(xí)址*4訃?yán)罘苏身暷空橅?xiàng)目弟誣D"盤選T時(shí)作 解壓2）通過鍵盤輸入1,并按回車D；學(xué)習(xí)一 +下學(xué)匪大項(xiàng)巨伏項(xiàng)目結(jié)驗(yàn)D兇旳伙項(xiàng)目窮高課計(jì)請選擇您想進(jìn)行的操作1 壓縮2情將待壓縮的文件以t泌的格式存放在程序所在目錄下-并輸入禱壓縮文件的文件名3）將待壓縮的文件以txt的格式存放在程序所在的目錄下Debug2013/5/18 16:04.耐丸頂目紹念匚PP2C13/5/10 11:55C+ + Somrce tile17 K6二為換昌嬌海rub2013/5/18 16:04MCE文件KB一大壩目堡檻201/5/18 2上強(qiáng)H【ML坯1 KB囲這盂揑吉2 13/5/15 13:3

16、9Microsoft Power.495 KB超幵趙舌2013/4/18 13i0iMicrosoft Poweri3U KB劉丄 S/5/lfi 10:44京本文苦1 KB4）通過鍵盤輸入待壓縮文件的文件名（注意要在文件名稱的末尾加.txt）并按回車親F遺選擇您想進(jìn)行的操作1 壓縮2 解莊縮的文件tttxt的格式存放在程序所在目錄下，并輸入待壓縮文件的文件名 iflAffi縮后的文件的保存名稱5）通過鍵盤輸入壓縮后的文件的保存名稱（注意要在文件名稱的末尾加.txt）并按回車1-壓縮冬解壓縮的文件畑的格式存放在程序所在目錄H并輸入待壓縮文件的文件名 SSaI縮后的文件的保存名稱1 .txt匡縮

17、完成壓縮后的文件保存曲- txt中Pi'ess an# key to contlnue6）壓縮完成，按任意鍵結(jié)束程序2.解壓縮1）運(yùn)行程序 P：學(xué)習(xí)址+十下學(xué)期龍項(xiàng)目試頂目細(xì)DubugVt®®¥親住臺選擇您想進(jìn)行的操作2）通過鍵盤輸入2，并按回車3）將待解壓的文件以txt的格式存放在程序所在的目錄下Debug儒改日期類型大小2013/5/13 16:04文收 12O13/5/1S 22:442 KB畫大項(xiàng)巨變狷仲P2013/5/18 11:55C+ Source file17 KB大項(xiàng)呂関得nub2013/5/18 16:04NCB玄件25 KB_大項(xiàng)巨鐸

18、稱2013/5/18 22:34HTMLim1KB曲結(jié)讎吉2013/5/16 13:39Microsoft Power.-495 KB場開虧售2O13/4A8 13:05Microsoft Power».313 KB追夢2O13/5/1& 10:441 KB4）通過鍵盤輸入待解壓文件的文件名（注意要在文件名稱的末尾加.txt）并按回車1 壓縮2 解壓2請將待解壓的文件以t泌的格式徉放在程序所在目錄下莽輸入待解壓文件的文件名1 - txt請輸入解壓后的文件的保存名稱5）通過鍵盤輸入解壓后的文件的保存名稱（注意要在文件名稱的末尾加.txt）并按回車1-壓縮牛解壓肯將待解壓的文件以

19、z的格式存放在程序所在目錄F,并輸人待網(wǎng)土丈件的文件名1 .txt障輸入解壓后的文件的保存名稱2 -txt字符的種類數(shù)為.lei源文件中字符的總個(gè)數(shù)；943匡縮文件中編碼長度為'725辭壓完成解壓后的文件保存在2 - txt中Press any ke to continueH6）解壓完成，按任意鍵結(jié)束程序運(yùn)行程序設(shè)計(jì)與算法語言項(xiàng)目報(bào)告0 8.項(xiàng)目總結(jié)8.項(xiàng)目總結(jié)我們小組完成zip壓縮軟件收獲頗多。通過這次的項(xiàng)目，我們了解了 huffman算法，學(xué)會了建樹，更加 熟練地掌握了文件的相關(guān)操作，并對二進(jìn)制文件有了相應(yīng)的了解。開始拿到題目時(shí)，我們原以為很簡單，（因?yàn)槊菜朴写a的樣子）， 結(jié)果我

20、們失望了，代碼不全這只是其一，相應(yīng)的參考資料是英文的這 是其二。百度huffman算法的時(shí)候我們還發(fā)現(xiàn)涉及到二叉樹這一從未 接觸過的東西，于是我們果斷放棄了MIT的代碼，自己尋找漢語版的zip壓縮程序的相關(guān)資料。在把算法搞懂了以后，我們開始了編代碼。找到了一些參考的代 碼，仿照他們的思想我們決定用結(jié)構(gòu)體數(shù)組來實(shí)現(xiàn)頻率的統(tǒng)計(jì)，二叉樹的建立等功能，因?yàn)樽址?ascII碼在0256之間，最開始定義的 結(jié)構(gòu)體數(shù)組大小為256，可是后面由于要建樹，若僅采用二叉樹的方 式，會對于之后的查找?guī)聿槐?。于是想到將非葉子節(jié)點(diǎn)也同樣存入 數(shù)組中，又因?yàn)榭偨Y(jié)點(diǎn)數(shù)最多為二倍葉子數(shù)減一， 所以定義結(jié)構(gòu)體數(shù) 組的大小為

21、2*256。并采取將字符對應(yīng)的ascII碼作為下標(biāo)的方法使 統(tǒng)計(jì)頻率的過程更加方便易操作。在建樹的過程中，我們采用了 “在結(jié)構(gòu)體數(shù)組中建樹”的思想， 直接在結(jié)構(gòu)體數(shù)組中進(jìn)行相應(yīng)的左孩子右孩子父節(jié)點(diǎn)進(jìn)行鏈接。在一開始我們米用將編碼和碼本輸入到兩個(gè) txt文件中，后來考慮 到呈現(xiàn)形式的簡潔性問題和壓縮效率的問題（txt文件本身有一定的 大小）我們實(shí)現(xiàn)了兩個(gè)文件的合并，在其中添加了計(jì)數(shù)的變量（統(tǒng)計(jì) 壓縮文件部分的字節(jié)數(shù)），實(shí)現(xiàn)了壓縮部分的優(yōu)化。對于二進(jìn)制轉(zhuǎn)換這一部分，我們采用的是首先將源文件轉(zhuǎn)換為二 進(jìn)制數(shù)串，并逐一記錄進(jìn)字符數(shù)組中，再判斷長度是否大于8,若是, 則進(jìn)行二進(jìn)制轉(zhuǎn)換，返回一個(gè)被位運(yùn)算過的字符，將字符數(shù)組中的前 八位之后的字符串向前移。不斷循環(huán)，直到運(yùn)行到最后，在后面加入 八個(gè)“ 0”，完成二進(jìn)制編碼。解碼時(shí)，先創(chuàng)建碼本數(shù)組，一次讀入一個(gè)字符，通過位運(yùn)算與， 輸出其二進(jìn)制串，再根據(jù)碼本中所存的代碼長度，確定二進(jìn)制串的長 度，在代碼