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

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

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

5、iyasuo數(shù)組用來(lái)存儲(chǔ)用戶(hù)輸入的待壓縮文件的文件名char daijieya50;daijieya數(shù)組用來(lái)存儲(chǔ)用戶(hù)輸入的壓縮后和待解壓文件的文件名char jieyahou50;jieyahou數(shù)組用來(lái)存儲(chǔ)用戶(hù)輸入的解壓后的文件的文件名struct NodeNode *pare nt;Node *left;Node *right;un sig ned char info;int weight;char code1000;結(jié)構(gòu)體Node用來(lái)存儲(chǔ)節(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的格式存儲(chǔ)，名稱(chēng)由用戶(hù)自己確定4.4.2數(shù)據(jù)文件格式規(guī)范無(wú).5 .程序設(shè)計(jì)與算法語(yǔ)言項(xiàng)目報(bào)告 5算法設(shè)計(jì)5算法設(shè)計(jì)5.1編碼過(guò)程5.1.1編碼過(guò)程中的總算法計(jì)算機(jī)編程實(shí)現(xiàn)時(shí)，首先統(tǒng)計(jì)帶編碼的文本文件中各個(gè)字符出現(xiàn)的次數(shù)，然后將概率作為節(jié)點(diǎn)的權(quán)值，并進(jìn)行排序，然后構(gòu)建huffman樹(shù)。編碼時(shí)從葉子節(jié)點(diǎn)出發(fā)，如果這個(gè)節(jié)點(diǎn)在左子樹(shù)上，則編碼0,否則編碼1,直到根節(jié)點(diǎn)為止，然后反序，所得到的01序列即為該葉子節(jié)點(diǎn)的編碼。所有葉子節(jié)點(diǎn)的編碼構(gòu)成一一個(gè)碼本。將碼本存儲(chǔ)，然

7、后遍歷文本文件，將字符轉(zhuǎn)化為編碼，再轉(zhuǎn)化為壓縮后的txt文件。5.1.2各函數(shù)的具體算法申請(qǐng)大小為2*n的結(jié)構(gòu)體數(shù)組(n=256)將結(jié)構(gòu)體初始化存入各字符讀取文件，統(tǒng)計(jì)頻率void File(Node *array):將字符轉(zhuǎn)化為相應(yīng)的ascii碼，然后將數(shù)組中與相對(duì)應(yīng)的位置處，(即數(shù)組下標(biāo)為該字符所對(duì)應(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建樹(shù) Node BuildTree(Node *array):在數(shù)組中未利用的部分申請(qǐng)節(jié)點(diǎn)作為父節(jié)點(diǎn)

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

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

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

11、系統(tǒng)實(shí)現(xiàn)6.1設(shè)計(jì)過(guò)程1.查閱資料Zip壓縮程序的題目是這樣的：zip數(shù)據(jù)壓縮程序只要你愿意，你完全可以做一個(gè)自己的zip壓縮軟件！似乎很難？其實(shí)這只是MIT “Practical Programming in C” 的一個(gè)實(shí)驗(yàn)項(xiàng)目。請(qǐng)?jiān)L問(wèn) 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/,請(qǐng)參閱 Lab 2 的文檔。里面提供了 step by step模式的

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

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

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

15、行程序01學(xué)習(xí)址*4訃?yán)罘苏身暷空橅?xiàng)目弟誣D"盤(pán)選T時(shí)作 解壓2）通過(guò)鍵盤(pán)輸入1,并按回車(chē)D；學(xué)習(xí)一 +下學(xué)匪大項(xiàng)巨伏項(xiàng)目結(jié)驗(yàn)D兇旳伙項(xiàng)目窮高課計(jì)請(qǐng)選擇您想進(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）通過(guò)鍵盤(pán)輸入待壓縮文件的文件名（注意要在文件名稱(chēng)的末尾加.txt）并按回車(chē)親F遺選擇您想進(jìn)行的操作1 壓縮2 解莊縮的文件tttxt的格式存放在程序所在目錄下，并輸入待壓縮文件的文件名 iflAffi縮后的文件的保存名稱(chēng)5）通過(guò)鍵盤(pán)輸入壓縮后的文件的保存名稱(chēng)（注意要在文件名稱(chēng)的末尾加.txt）并按回車(chē)1-壓縮冬解壓縮的文件畑的格式存放在程序所在目錄H并輸入待壓縮文件的文件名 SSaI縮后的文件的保存名稱(chēng)1 .txt匡縮

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

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

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

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

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