哈夫曼樹壓縮軟件數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè)計題目： 哈夫曼樹壓縮軟件 姓名： 學號： 班級： 指導老師： 一、設(shè)計分析2二、算法設(shè)計3三、主要模塊說明5主界面5int main()5bintree.h7ceshi.h14compress1.h19void Decompress()22huffmantree.h25#if !defined _HEAP_H_28四、運行截圖32五、總結(jié)33一、設(shè)計分析 1）課程設(shè)計名稱及內(nèi)容 課程設(shè)計名稱：哈夫曼編碼的數(shù)據(jù)壓縮/解壓程序 設(shè)計內(nèi)容：將任意一個指定的文本文件中的字符進行哈夫曼編碼,生成一個編碼文件(壓縮文件);反過來,可將一個壓縮文件解碼還原為一個文本文件。 2)選擇1

2、時: 輸入一個待壓縮的文本文件名稱(帶路徑)。 如:D:lulu.txt 統(tǒng)計文本文件中各字符的個數(shù)作為權(quán)值,生成哈夫曼樹； 將文本文件利用哈夫曼樹進行編碼,生成壓縮文件。壓縮文件名稱=壓縮文件時所命的名稱.HFM如:D:lulu.COD壓縮文件內(nèi)容=哈夫曼樹的核心內(nèi)容+編碼序列 （文件存放在軟件運行的文件夾下）3) 選擇2時: 輸入一個待解壓的壓縮文件名稱(帶路徑 )如:D:lulu.COD 從文件中讀出哈夫曼樹,并利用哈夫曼樹將編碼序列解碼；生成(還原)文本文件。文件名稱 =壓縮文件名時為解壓縮時所命的名字 如:D:lu*.txt （但是沒有實現(xiàn)這一效果，解壓時需要建立一個和文件未壓縮以前

3、一樣的空文件和需要解壓文件放在一起）4)選擇3時： 對輸入的字符串進行編碼、壓縮、解壓并對其進行顯示。5）選擇0是則退出 二、算法設(shè)計 2.1設(shè)計思想： 統(tǒng)計字符，得出統(tǒng)計出字符的權(quán)值n，建立哈夫曼樹，根據(jù)哈夫曼樹編碼對編碼進行壓縮生成二進制文件，根據(jù)哈夫曼樹解碼生成哈夫曼樹，對二進制文件進行解碼生成對應(yīng)文件。 2.2 算法思想： 2.2.1輸入要壓縮的文件首先運行的時候，用戶主界面上有菜單提示該如何使用軟件，根據(jù)菜單提示選擇所要執(zhí)行的 項，依次進行，因為各個環(huán)節(jié)之間有先后順序。第一步為輸入壓縮軟件的名稱，由鍵盤輸入文件路徑和文件名稱，讀入字符數(shù)組中，打開該文件，按照提示進行壓縮。若打不開，則

4、繼續(xù)輸入。2.2.2讀文件并計算字符頻率 文件將信息存放在字符數(shù)組中；計算每個字符出現(xiàn)的次數(shù)，申請一個結(jié)構(gòu)體數(shù)組空間， 用讀取的字符減去字符結(jié)束符作為下標記錄字符的頻率。 2.2.3根據(jù)字符的頻率，利用Huffman編碼思想創(chuàng)建Huffman樹 將所記錄的字符的頻率作為權(quán)值來創(chuàng)建Huffman樹，依次選擇權(quán)值最小的兩個字符作為左右孩子，其和作為父結(jié)點的權(quán)值，依次進行下去，直到所有的字符結(jié)點都成為葉子結(jié)點。 2.2.4由創(chuàng)建的Huffman樹來決定字符對應(yīng)的編碼，進行文件的壓縮 根據(jù)創(chuàng)建的Huffman樹來確定個字符的01編碼，左子樹為0，右子樹為1。讀取文件，依次將每個字符用他們的編碼表示，即

5、完成一次編碼。 2.2.5解碼壓縮即根據(jù)Huffman樹進行譯碼 讀取編碼文件，依據(jù)創(chuàng)建的Huffman樹，定義一個指針指向根結(jié)點。從根結(jié)點開始，每讀一個字符，指針變化一次（當讀取的字符是1時，指針指向當前所指結(jié)點的右孩子，當讀取的字符是0時，指針指向當前所指結(jié)點的左孩子），直至該指針所指結(jié)點為葉子結(jié)點時結(jié)束（即當結(jié)點的左右孩子均為空時）。將當前葉子結(jié)點所代表的字符值輸出到譯碼文件中，依次讀取編碼文件中的字符，按照上述方法依次進行下去直至文件三、主要模塊說明主界面#include "huffmantree.h"#include <fstream.h>#inclu

6、de <conio.h>#include "compress1.h"#include "Ceshi.h"void menu() cout<<endl; cout<<"tt * 操作菜單 *nn" cout<<"ttt 1 壓縮文件n" cout<<"ttt 2 解壓文件n" cout<<"ttt 3 測試n" cout<<"ttt 0 退出nnnn" return;int

7、main() char meiyong; cout<<"nnnnnnnnn" <<"t &* 壓縮軟件 *&n" <<"t * *n" <<"t * *n" <<"t * *nnn" <<"t * 運行本軟件之前,請務(wù)必仔細閱讀使用指南 *" <<"n" cin.unsetf(ios:skipws); cin>>meiyong; cin.setf

8、(ios:skipws); ifstream fin("使用說明.txt",ios:binary); fin.unsetf(ios:skipws); while(fin>>meiyong) cout<<meiyong; cout<<endl; getch(); fin.setf(ios:skipws); fin.close(); cout<<"nnnnnn" cout<<"n" cout<<"tt*-*n" cout<<"

9、tt * 哈弗曼樹的應(yīng)用 * n" cout<<"t * *n" cout<<"tt * 作者: 許定琳 學號: 1314080903243 *n" cout<<"tt*-*nn" cout<<"tt 2015.1.1nn" menu(); int choice; cout<<"請選擇操作: " cin>>choice; while(1) switch(choice) case 1: Compress(); bre

10、ak; case 2: Decompress(); break; case 3: Ceshi(); break; case 0: cout<<"nntt* 謝謝您使用本軟件，再見! *nnnn" return 1; default: cout<<"無此操作!nn" cout<<endl<<"請選擇操作: " cin>>choice; return 1;bintree.h/用指針實現(xiàn)的二叉樹/Type 類型必須有重載<<與>>及運算#if !define

11、d _BINTREE_H_#define _BINTREE_H_#include <assert.h>#include <iostream.h>int Max(int a,int b) return a>b?a:b;template <class Type> class BinaryTree; template <class Type> class BinTreeNode friend class BinaryTree<Type>public: BinTreeNode():leftchild(NULL),rightchild(N

12、ULL); BinTreeNode(Type item,BinTreeNode<Type> *left = NULL,BinTreeNode<Type> *right=NULL) :data(item),leftchild(left),rightchild(right); Type GetData()const return data; BinTreeNode<Type> *GetLeft()const return leftchild; BinTreeNode<Type> *GetRight()const return rightchild;

13、void SetData(const Type &item) data=item; void SetLeft(BinTreeNode <Type> *L) leftchild = L; void SetRight(BinTreeNode <Type> *R) rightchild = R; private: BinTreeNode<Type> *leftchild, *rightchild; Type data;template <class Type> class BinaryTree public: BinaryTree():root

14、(NULL); BinaryTree(const BinaryTree<Type> &bt) root=Copy(bt.root); BinaryTree(const Type &temp,const BinaryTree<Type> &bt1,const BinaryTree<Type> &bt2); BinaryTree(Type value):RefValue(value),root(NULL); void operator =(const BinaryTree<Type> &bt); virtual

15、 BinaryTree() Destroy(root); void Destroy()Destroy(root);root=NULL; virtual int IsEmpty() return root=NULL?1:0; virtual BinTreeNode <Type> *Parent(BinTreeNode <Type> *current) return root=NULL|root=current? NULL : Parent(root,current); virtual BinTreeNode <Type> *LeftChild(BinTreeN

16、ode <Type> *current) return root!=NULL? current->leftchild : NULL; virtual BinTreeNode <Type> *RightChild(BinTreeNode <Type> *current) return root!=NULL? current->rightchild : NULL; virtual int Insert(const Type &item); virtual int Find(const Type &item)const; BinTree

17、Node <Type> *GetRoot()const return root; friend int Equal(BinTreeNode<Type> *a,BinTreeNode<Type> *b); friend int operator =(const BinaryTree<Type> &bt1,const BinaryTree<Type> &bt2); friend istream& operator >>(istream &in, BinaryTree<Type> &a

18、mp;Tree); friend ostream& operator <<(ostream &out,BinaryTree<Type> &Tree ); void InOrder(); /遍歷 void PreOrder(); void PostOrder(); /* /一些應(yīng)用 int Size() return Size(root); /統(tǒng)計結(jié)點數(shù) int Depth() return Depth(root); /計算樹的深度 int Leaves() return Leaves(root); int Degrees1() return De

19、grees1(root); int Degrees2() return Degrees2(root);protected: BinTreeNode <Type> *root; Type RefValue; BinTreeNode<Type> *Parent(BinTreeNode<Type> *start,BinTreeNode<Type> *current); int Insert (BinTreeNode<Type> *current,const Type &item); int Find(BinTreeNode<T

20、ype> *current,const Type &item)const; BinTreeNode<Type>* Copy(BinTreeNode<Type> *originode); void Destroy(BinTreeNode<Type> *current); /* void InOrder(BinTreeNode<Type> *current); void PreOrder(BinTreeNode<Type> *current); void PostOrder(BinTreeNode<Type> *

21、current); /* /一些應(yīng)用 int Size(const BinTreeNode<Type> *t)const; int Depth(const BinTreeNode<Type> *t)const; int Leaves(const BinTreeNode<Type> *t)const; int Degrees1(const BinTreeNode<Type> *t)const; int Degrees2(const BinTreeNode<Type> *t)const;template <class Type>

22、;BinTreeNode<Type>* BinaryTree<Type>:Copy(BinTreeNode<Type> *orignode) if(orignode=NULL) return NULL; BinTreeNode<Type> *temp=new BinTreeNode<Type> temp->data=orignode->data; temp->leftchild=Copy(orignode->leftchild); temp->rightchild=Copy(orignode->ri

23、ghtchild); return temp;template <class Type>BinaryTree<Type>:BinaryTree(const Type &temp,const BinaryTree<Type> &bt1,const BinaryTree<Type> &bt2) root=new BinTreeNode<Type>(temp,Copy(bt1.root),Copy(bt2.root); template <class Type> void BinaryTree<Ty

24、pe>:operator =(const BinaryTree<Type> &bt1) Destroy();/ Destroy(root);root=NULL; /為什么要這樣？ root=Copy(bt1.root);template<class Type> void BinaryTree<Type>:Destroy(BinTreeNode<Type> *current) if(current!=NULL) Destroy(current->leftchild); Destroy(current->rightchild

25、); delete current; template<class Type> BinTreeNode <Type>* BinaryTree<Type>:Parent(BinTreeNode<Type> *start,BinTreeNode<Type> *current) if(start=NULL) return NULL; if(start->leftchild=current | start->rightchild=current) return start; BinTreeNode <Type> *p=

26、NULL; if(p=Parent(start->leftchild, current)!=NULL) /在start的左子樹中找 return p; else return Parent(start->rightchild,current);template<class Type> int BinaryTree<Type>:Insert(BinTreeNode<Type> *current,const Type &item) if(current=NULL) return 0; BinTreeNode<Type> *p=ne

27、w BinTreeNode<Type>(item,NULL,NULL); if(current->leftchild=NULL) current->leftchild=p; else if(current->rightchild=NULL) current->rightchild=p; else Insert(current->leftchild,item); /這樣插可是構(gòu)不成樹狀的！估且一用吧 return 1;template<class Type> int BinaryTree<Type>:Insert(const Ty

28、pe &item) if(root=NULL) root=new BinTreeNode<Type>(item,NULL,NULL); return 1; return Insert(root,item);template<class Type> int BinaryTree<Type>:Find(BinTreeNode<Type> *current,const Type &item)const if(current=NULL) return 0; if(current->data=item) return 1; int k

29、; if(k=Find(current->leftchild,item)!=0) return 1; else return Find(current->rightchild,item);template<class Type> int BinaryTree<Type>:Find(const Type &item)const return Find(root,item);template<class Type>int Equal(BinTreeNode<Type> *a,BinTreeNode<Type> *b)

30、if(a=NULL&&b=NULL) return 1; if(a!=NULL&&b!=NULL&&a->GetData()=b->GetData() &&Equal(a->GetLeft(),b->GetLeft()&&Equal(a->GetRight(),b->GetRight() return 1; return 0;template<class Type>int operator =(const BinaryTree<Type> &bt1

31、,const BinaryTree<Type> &bt2) return Equal(bt1.root,bt2.root);template<class Type> istream& operator>>(istream &in,BinaryTree<Type> &Tree) Type item; cout<<"構(gòu)造二叉樹:n" cout<<"輸入數(shù)據(jù)(用"<<Tree.RefValue<<"結(jié)束): " i

32、n >> item; while(item!=Tree.RefValue) Tree.Insert(item); cout<<"輸入數(shù)據(jù)(用"<<Tree.RefValue<<"結(jié)束): " in>>item; return in;template<class Type> ostream& operator<<(ostream &out,BinaryTree<Type> &Tree) out<<"二叉樹的前序遍歷.

33、n" Tree.PreOrder(); out<<endl; return out;template <class Type> void BinaryTree <Type>:InOrder() InOrder(root);template <class Type> void BinaryTree<Type>:InOrder(BinTreeNode<Type> *current) if(current!=NULL) InOrder(current->leftchild); cout << curr

34、ent->data<<' ' InOrder(current->rightchild); template <class Type>void BinaryTree <Type>:PreOrder() PreOrder(root);template <class Type> void BinaryTree<Type>:PreOrder(BinTreeNode<Type> *current) if(current!=NULL) cout<<current->data<<

35、' ' PreOrder(current->leftchild); PreOrder(current->rightchild); template <class Type> void BinaryTree<Type>:PostOrder() PostOrder(root);template <class Type> void BinaryTree<Type>:PostOrder(BinTreeNode<Type> *current) if(current!=NULL) PostOrder(current-&

36、gt;leftchild); PostOrder(current->rightchild); cout<<current->data<<' ' template <class Type> int BinaryTree<Type>:Size(const BinTreeNode<Type> *t)const if(t=NULL) return 0; else return 1+Size(t->leftchild)+Size(t->rightchild);template <class Type

37、> int BinaryTree<Type>:Depth(const BinTreeNode<Type> *t)const if(t=NULL) return -1; else return 1+Max(Depth(t->leftchild),Depth(t->rightchild); template <class Type> int BinaryTree<Type>:Leaves(const BinTreeNode<Type> *t)const if(t=NULL) return 0; if(t->left

38、child=NULL&&t->rightchild=NULL) /t是葉子結(jié)點 return 1; return Leaves(t->leftchild)+Leaves(t->rightchild);template <class Type>int BinaryTree<Type>:Degrees1(const BinTreeNode<Type> *t)const if(t=NULL) return 0; if(t->leftchild=NULL&&t->rightchild!=NULL) |(t

39、->leftchild!=NULL&&t->rightchild=NULL) /t的度為1 return 1+Degrees1(t->leftchild)+Degrees1(t->rightchild); return Degrees1(t->leftchild)+Degrees1(t->rightchild);template <class Type>int BinaryTree<Type>:Degrees2(const BinTreeNode<Type> *t)const if(t=NULL) retu

40、rn 0; if(t->leftchild!=NULL&&t->rightchild!=NULL) /t 的度為2 return 1+Degrees2(t->leftchild)+Degrees2(t->rightchild); return Degrees2(t->leftchild)+Degrees2(t->rightchild);#endifceshi.h/測試#if !defined _CESHI_H_#define _CESHI_H_#include "compress1.h"#include <iostr

41、eam.h>#include <fstream.h>void Ceshi() unsigned char ch; int i,j,k; int Charnum256;/ unsigned char Chars256; /與下面共同使用 ,記錄字符 int Charnums256; /記錄對應(yīng)字符的個數(shù) int CharKinds; /字符種數(shù) unsigned char string301; unsigned char *acharp; /字符指針 int length; /報文長度 HuffmanTree<unsigned char> ht; CharNameN

42、ode NameNode256; /存儲字符對應(yīng)的哈夫曼編碼 BinTreeNode<unsigned char> *btn=NULL; Code *first=NULL; Code *last=NULL; Code *pCode=NULL; /臨時使用 unsigned int total; int fpend; ofstream fileout; ifstream filein; cout<<"請輸入要測試的字符串(長度不超過300)：" cin>>string; acharp=string; for(i=0;i<256;i+)

43、 Charnumi=0; /記錄每一個字符的個數(shù) Charnumsi=0; /記錄字符Chari的個數(shù) while(*acharp!='0') Charnumunsigned int(*acharp)+; /統(tǒng)計每種字符的頻數(shù) acharp+; j=0; for(i=0;i<256;i+) if(Charnumi) Charsj=unsigned char(i); /統(tǒng)計字符串中存在的字符的 Charnumsj=Charnumi; j+; CharKinds=j; fileout.open("temp.txt",ios:binary); /輸出到臨時文

44、件中保存 fileout<<'0'<<' ' /非法位數(shù)（之后修改） fileout<<CharKinds<<' ' /存入字符種類 for(i=0;i<CharKinds;i+) fileout<<Charsi<<' '<<Charnumsi<<' '/將字符信息存入臨時文件 ht.Build(Charnums,Chars,CharKinds,ht); /建立哈夫曼樹 i=0; ht.Path(ht.GetRoo

45、t(),first,last,NameNode,i); /搜索哈夫曼樹求得字符對應(yīng)的哈夫曼編碼 cout<<"各字符的哈夫曼編碼：n" for(i=0;i<CharKinds;i+) cout<<"t"<<NameNodei.charname<<':' pCode=NameNodei.link; while(pCode!=NULL) cout<<pCode->code; pCode=pCode->link; cout<<endl; k=0; j=0;

46、 length=0; /報文長度 acharp=string; cout<<"報文：" while(*acharp!='0') i=0; while(*acharp!=NameNodei.charname) /找到ch i+; pCode=NameNodei.link; while(pCode!=NULL) length+; j<<=1; j+=pCode->code; cout<<pCode->code; k+; if(k=8) fileout<<unsigned char(j); k=0; j=

47、0; pCode=pCode->link; acharp+; cout<<"n長度："<<length<<endl; if(k<8) j<<=(8-k); fileout<<unsigned char(j); fileout.seekp(0,ios:beg); fileout<<8-k; /修改非法代碼的位數(shù) fileout.close(); for(i=0;i<CharKinds;i+) Code *q=NameNodei.link; Code *s=NULL; while(q!=N

48、ULL) s=q; q=q->link; delete s; NameNodei.link=NULL; /清除鏈表信息 ht.Destroy(); filein.open("temp.txt",ios:binary); /從臨時文件中取出Huffman碼 filein.seekg(0,ios:end); fpend=filein.tellg(); /記錄文件尾的位置 filein.seekg(0,ios:beg); /恢復 filein.unsetf(ios:skipws); filein>>k>>ch; /最后一個字符不合法的位數(shù) filei

49、n>>CharKinds>>ch; for(i=0;i<CharKinds;i+) filein>>Charsi>>ch>>Charnumsi>>ch; /載入字符信息 ht.Build(Charnums,Chars,CharKinds,ht); /建立哈夫曼 btn=ht.GetRoot(); cout<<"上述報文的解碼：" while(filein>>ch) total=(unsigned int)(ch); /這里都是正確的 j=0; if(filein.tellg()=fpend) /到了文件尾 j=k; /留k位不輸出 for(i=7;i>=j;i-) if(total&(1<<i) /這一位是1向右子樹走 b