數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告【一】

課程設(shè)計(jì)題目：文本文件壓縮【一】

 題目: 文本文件壓縮解壓

 需求分析：

  輸入：文本文件(壓縮文件)

  輸出：壓縮文件(文本文件)  (壓縮率)

  知識(shí)點(diǎn)：堆排序、霍夫曼樹(shù)、二叉樹(shù)遍歷,、存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

　　　　  文件流操作,、字符漢字編碼方式、二進(jìn)制文件讀寫(xiě)

  備注：字符文件,、漢字文件的壓縮與解壓

 解決問(wèn)題要點(diǎn)：

1.      文本文件,，二進(jìn)制文件及數(shù)據(jù)流的操作

2.      英文字符，中文字符的存儲(chǔ)與識(shí)別【難點(diǎn)】

3.      壓縮及解壓的主要思想【重點(diǎn)】

4.      Huffman樹(shù)的構(gòu)造

5.      編碼的獲取

6.      壓縮文件的存儲(chǔ)形式[huffman編碼信息及數(shù)據(jù)存儲(chǔ)]

7.      對(duì)文本文件最后一個(gè)字符的處理[補(bǔ)位數(shù)：壓縮,，解壓無(wú)錯(cuò)誤]

　       以上七點(diǎn)即解決問(wèn)題的關(guān)鍵,，僅僅了解整個(gè)思想是遠(yuǎn)遠(yuǎn)不夠的，整個(gè)過(guò)程中,，很多細(xì)節(jié)需要注意,，把握要點(diǎn)的同時(shí)，要在具體實(shí)現(xiàn)中注意細(xì)節(jié),。

模塊及框架設(shè)計(jì)：

按功能需求,，主要分為五個(gè)模塊

主要模塊：

1.      壓縮模塊

2.      解壓模塊

輔助模塊：

 1.  字符識(shí)別及權(quán)重獲取

2.  Huffman樹(shù)構(gòu)造

3.  獲取huffman編碼

 主要設(shè)計(jì)及具體實(shí)現(xiàn)　【實(shí)現(xiàn)代碼(帶注釋)】

l  壓縮解壓的實(shí)現(xiàn)思想及原理

定義：利用算法將文件有損或無(wú)損地處理，以達(dá)到保留最多文件信息,，而令文件體積變小,。

在文本文件中，一個(gè)ASCII碼占用一個(gè)字節(jié)空間（1Byte）,，漢字由兩個(gè)字節(jié)構(gòu)成（區(qū)碼和位碼）,，區(qū)碼和位碼分別用ASCII碼的161-255字符表示，共94*94=8836個(gè)【GB2312編碼】

即,，無(wú)論字符還是漢字,，均可由ASCII碼表示，我們可以以二進(jìn)制文件形式將一個(gè)文本文件讀入,，分析每個(gè)ASCII碼的頻數(shù),，構(gòu)造huffman樹(shù)，并得到相應(yīng)的編碼,。

編碼是由0,、1組成的一串?dāng)?shù)字，出現(xiàn)頻率越高的字符,，其編碼越短,，通過(guò)這個(gè)特性，我們可以將每8位組成一個(gè)新的字符（1Byte）,，輸出到壓縮文件中,，達(dá)到壓縮的目的。

例如：

已知  a: 000  b:10  c: 001  d:01   e:11 

如果其中的一段是:：abcde 則處理如下：

補(bǔ)上兩位

    a     b    c      d     e  

   000   10   00  1  01   11   00

每次取7位【取8位亦可,，但此處為了處理最后一個(gè)字符,，只取7位】

0+7位湊成1Byte,，轉(zhuǎn)化為相應(yīng)AscII碼輸出

最后一位一般不能剛好湊夠8 bit 所以需要補(bǔ)上0

而補(bǔ)上的0的個(gè)數(shù)記錄為補(bǔ)位數(shù) 【補(bǔ)位數(shù)的處理】

原來(lái)：  5*1Byte=8 Byte

處理后：2*1Byte=2 Byte

        僅為原來(lái)的四分之一，達(dá)到了壓縮的目的

l  字符,，漢字處理方式

字符,，即ASCII碼，ASCII編碼由8位組成,，共256個(gè)字符，足夠表示英文文本,。

漢字,，是考慮的重點(diǎn),，多方考慮下,，我選擇了系統(tǒng)支持的GB2312編碼表，而非轉(zhuǎn)化為UNICODE編碼,。GB2312的漢字編碼占用兩個(gè)字節(jié),，區(qū)碼和位碼分別由ASCII碼表的161-255字符表示,，共8836個(gè)漢字，足以承擔(dān)漢字處理,，而UNICODE編碼表是變長(zhǎng)編碼,，處理困難且不利于壓縮。

漢字ASCII碼八位1*******   一般字符編碼八位0*******

    處理的思想：

以字符形式讀入,，每次讀入一個(gè)字節(jié)（1Byte）進(jìn)行處理,，不去判斷區(qū)分是字符還是漢字，只識(shí)別ASCII碼,，進(jìn)行處理,。

l  設(shè)計(jì)字符所存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)

讀入的字符所需要存儲(chǔ)的信息：字符，頻數(shù)以及各自編碼

僅僅以char數(shù)組存儲(chǔ)將帶來(lái)非常大的缺陷,。

作用：提高效率,，減小復(fù)雜性

 class huffmanchar

{

char c;//字符

int count;//字符出現(xiàn)的次數(shù)

intbit[20];//用于存儲(chǔ)huffman編碼                                                                                                                                                                                                                                                                                                                                                                                  

int codelength;//bit中編碼的長(zhǎng)度

}

  實(shí)例化   huffmanchar huff[256]; //ASCII字符總數(shù)

           Int  totalcount;//記錄字符總數(shù) ，

l  設(shè)計(jì)樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

在壓縮時(shí),，為了解壓時(shí)能夠順利獲取該文件相應(yīng)的huffman編碼,，我們可以設(shè)計(jì)一個(gè)表頭，以存儲(chǔ)編碼信息,，但是這種形式不但造成讀入困難,，而且占用空間巨大。

解決方法：壓縮時(shí),，將整棵huffman以對(duì)象的形式寫(xiě)入壓縮文件開(kāi)頭,，解壓整棵讀出，強(qiáng)制類(lèi)型轉(zhuǎn)換即可方便地得到huffman樹(shù)

class BinaryTreeNode 

{

    Int  data;//頻數(shù),，即權(quán)重

char character;//相應(yīng)字符

BinaryTreeNode<T> *LeftChild,*RightChild;

};

設(shè)計(jì)Huffman樹(shù)的數(shù)據(jù)結(jié)構(gòu)

Huffman具有一般二叉樹(shù)的所有特性,，但是，在壓縮處理過(guò)程中遇到一個(gè)情況，我們無(wú)法正確處理最后一個(gè)字符,，因?yàn)橥ǔ５阶詈笠晃?，編碼不會(huì)滿(mǎn)8位，這就在解壓時(shí)輸出多余字符,。

解決方法,，每次令始終第一位為0，僅取7位編碼：0*******

處理到最后一位時(shí),，首位為1,，并記錄缺位數(shù)lackcount

Lackcount傳入huffman樹(shù)對(duì)象，以寫(xiě)入壓縮文件

class BinaryTree 

{

   BinaryTree(){ root=0;lackcount=0;}

BinaryTreeNode<T> *root;

   int lackcount;//構(gòu)造對(duì)象是用于存儲(chǔ)最后一位的缺位數(shù)~~~~~

}

：

整體構(gòu)架及處理流程：

     主類(lèi)：Oper.h   字符獲取,，文件讀取,，流處理，壓縮,，解壓縮

輔助類(lèi)：BinaryTree.h  構(gòu)造huffman樹(shù)及獲取相應(yīng)編碼

             MinHeap.h   用于輔助構(gòu)造huffman樹(shù)

          Chain.h      存儲(chǔ)遍歷huffman時(shí)產(chǎn)生的編碼

          BinaryTreeNode.h  存儲(chǔ)huffman樹(shù)結(jié)點(diǎn)

          Huffmanchar.h     存儲(chǔ)字符及權(quán)重,，編碼

          Huffman.h        存儲(chǔ)huffman

          OutOfBounds.h    huffman結(jié)點(diǎn)，存儲(chǔ)樹(shù)及權(quán)重

壓縮主要流程：

讀入文件       #include <fstream>

                        Ifstream input;

                        Input.open(“d:\\test.txt”);

計(jì)算頻數(shù)     huffmanchar huff[256],；//字符數(shù)組

            Int  totalcount;//記錄字符總數(shù) ,，

                 輔助函數(shù)

                 bool Oper::judge(int c)//判斷c所對(duì)應(yīng)字符是否在數(shù)組里出現(xiàn)

                  //若是出現(xiàn)過(guò)，該字符count++;

                 void Oper::add(char c)//添加新出現(xiàn)的字符totalcount++;

                   主函數(shù)：

                        void Oper::getFrequency()//計(jì)算頻數(shù)

                         {

                             while(!input.eof())

                             {

                          input.get(temp);

                             if(!judge((int)temp))

                                    add(temp); 

                               }

                          }

構(gòu)造huffman樹(shù)

                   構(gòu)造霍夫曼樹(shù)

 思想：

1.為了構(gòu)造霍夫曼樹(shù),，首先從僅含一個(gè)外部節(jié)點(diǎn)的二叉樹(shù)集合開(kāi)始，每個(gè)外部節(jié)點(diǎn)代表字符串中一個(gè)不同的字符,，其權(quán)重等于該字符的頻率,。

2.此后不斷地從集合中選擇兩棵具有最小權(quán)重的二叉樹(shù)，并把它們合并成一棵新的二叉樹(shù),，合并方法是把這兩棵二叉樹(shù)分別作為左右子樹(shù),，然后增加一個(gè)新的根節(jié)點(diǎn)。新二叉樹(shù)的權(quán)重為兩棵子樹(shù)的權(quán)重之和,。

3.這個(gè)過(guò)程可一直持續(xù)到僅剩下一棵樹(shù)為止,。

實(shí)現(xiàn)：               

 利用最小堆，將每個(gè)權(quán)重作為一顆僅有根節(jié)點(diǎn)的樹(shù)傳入,，每次取出權(quán)值最小兩個(gè),，組成一顆新樹(shù)并放回到最小堆，直到僅剩一棵樹(shù)

                                  BinaryTree<int> HuffmanTree(int a[],char c[],int n)

                                    {

                                    Huffman<int> *w=new Huffman<int>[n+1];

                                    BinaryTree<int> z,zero;

                                    MinHeap<Huffman<T> > H(1);//實(shí)例化最小堆對(duì)象

                                    H.Initialize(w,n,n);

                                    Huffman<int> x,y;

                                    for(i=1;i<n;i++)

                                    {

                                          H.DeleteMin(x);//每次取權(quán)值最小兩個(gè)

                                          H.DeleteMin(y);

                                          z.MakeTree(0,' ',x.tree,y.tree);//組成新樹(shù)

                                          z.weight=x.weight+y.weight;

                                          H.Insert(z);//再次加入

                                    }

                                         return x.tree;//最終返回即huffman樹(shù)

                                    }

獲取huffman編碼

                 偽代碼：

                       Chain  A;//由于存儲(chǔ)鏈表huffman編碼

                void OutputCode(root)

                 {

                    if(t->LeftChild ) //若是左子樹(shù)不為空

                   {

                     往左走,，0加入鏈表

                     OutputCode(root->leftChild)//遞歸處理

                    }

                       if(t->RightChild)

                    {

                       往右走，1加入鏈表

                         OutputCode(root->rightChild)//遞歸處理

                     }

                    if(t->LeftChild==NULL && t->RightChild==NULL)

                      {

                        若為葉節(jié)點(diǎn),，將鏈表內(nèi)編碼傳到相應(yīng)字符的bit數(shù)組

                        刪除鏈表最后一個(gè)節(jié)點(diǎn)

                         Return;

                      }

                         Return；

                        }

再次讀入文件

壓縮模塊開(kāi)始        

主要思想：

    將源文件字符一個(gè)一個(gè)讀入,，判斷,，尋找其相應(yīng)編碼

                      將編碼一位一位加入緩沖區(qū)

                      緩沖區(qū)滿(mǎn)8位時(shí)，轉(zhuǎn)化為相應(yīng)的形影ASCII編碼

                      將編碼輸出

BinaryTree<int>& bc,；//將樹(shù)對(duì)象先寫(xiě)到文件頭

  output.write((char *)&bc,sizeof(bc));

                     int buffer[8];//用作緩沖區(qū)~~~

                     int bufcount;//記錄緩沖字節(jié)數(shù)~~,，初始為1

                     主函數(shù)：

void encoding(BinaryTree<int>& bc)

//調(diào)用輔助函數(shù)

//讀入文件，處理每個(gè)字符,，得到其編碼

//將編碼加入緩沖區(qū)

                     輔助函數(shù)：

int changeinto(int *a)

//緩沖區(qū)滿(mǎn)時(shí)調(diào)用，將8位數(shù)組轉(zhuǎn)化為一個(gè)int

void addToBuff(int a,ofstream output)

//將編碼加入緩沖函數(shù)~~~

//緩沖區(qū)滿(mǎn)時(shí),，轉(zhuǎn)化為一個(gè)int ,寫(xiě)出output<<(char)intA void flushbuffer(ofstream output)

//處理完最后一位字符后,，緩沖區(qū)存在編碼

//將首位設(shè)為1，將緩沖區(qū)剩余的輸出

壓縮結(jié)束

解壓流程：

讀入文件 

重構(gòu)Huffman樹(shù)

                        直接將其存于壓縮文件表頭的對(duì)象讀出

                             BinaryTree<int> bc;

                             input.read((char *)&bc,sizeof(bc));  

                              并得到編碼的缺位數(shù)

                               Lackcount=bc.lackcount;

開(kāi)始解壓 

         解壓思想：

1. 每次一個(gè)Byte ,，

                2. 轉(zhuǎn)化為相應(yīng)二進(jìn)制串，識(shí)別首位是否

                3. 開(kāi)始遍歷huffman樹(shù)(0左  1右)

                   若為葉節(jié)點(diǎn),，輸出相應(yīng)字符

指針回到根節(jié)點(diǎn),，重復(fù)此過(guò)程  

void Oper::gothrough(BinaryTree<int> bc,int a,ofstream output)

//遍歷樹(shù)，若是葉節(jié)點(diǎn)輸出~~~~

{             

       if(a==0 && tnode->LeftChild )

{

            tnode=tnode->LeftChild;  

       }

       else if(a==1 && tnode->RightChild)

{

            tnode=tnode->RightChild;

       }

if(tnode->LeftChild==NULL && tnode->RightChild==N

解壓結(jié)束           {

                   output<<tnode->character;

                   output.flush();

         tnode=bc.root;    

       }  

 壓縮率：

表頭Bytes+字符編碼長(zhǎng)（codelength）總和/8

           總字符數(shù)Bytes

測(cè)試：

操作界面

測(cè)試文件：

l  小文件

1. 英文文本： 

test1.txt    《I have a dream》全文   

壓縮前：8.84KB      

壓縮后：5.51KB

壓縮率：63%

測(cè)試結(jié)果：

壓縮,，解壓成功,！壓縮效果不錯(cuò)

內(nèi)容與原文件相同

英文壓縮測(cè)試成功

2.中文文本：

test2.txt    《GB2312編碼表》   

壓縮前：15.4KB

壓縮后：11.6KB

壓縮率：75%

測(cè)試結(jié)果：壓縮，解壓成功,！

內(nèi)容于原文件相同,，無(wú)亂碼

中文漢字測(cè)試成功

l  略大文件  

test3.txt   《平凡的世界》       

壓縮前：1.62M

壓縮后：1.39M

壓縮率：86%

壓縮時(shí)間14.23秒

解壓時(shí)間 16.85秒

測(cè)試結(jié)果：壓縮，解壓成功,！

          壓縮解壓時(shí)間在可接受范圍之內(nèi)