文件压缩程序设计报告

1、课程设计报告课程名称：操作系统实验题目：文件压缩程序院系:计算机科学与工程学院班级:_姓名：学号:年七月一日需求分析:有两种形式的重复存在于计算机数据中，文件压缩程序就是对这两种重复进行了 压缩。一种是短语形式的重复，即三个字节以上的重复，对于这种重复，压缩程序用两 个数字： 1. 重复位置距当前压缩位置的距离； 2. 重复的长度，来表示这个重复，假设 这两个数字各占一个字节，于是数据便得到了压缩。第二种重复为单字节的重复，一个字节只有 256 种可能的取值，所以这种重复是必 然的。给 256 种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的 字节使用较长的编码，这样一来，变短的

2、字节相对于变长的字节更多，文件的总长度 就会减少，并且，字节使用比例越不均匀，压缩比例就越大。编码式压缩必须在短语式压缩之后进行，因为编码式压缩后，原先八位二进制值的 字节就被破坏了，这样文件中短语式重复的倾向也会被破坏（除非先进行解码） 。另 外，短语式压缩后的结果：那些剩下的未被匹配的单、双字节和得到匹配的距离、长 度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺序不能变。本程序设计只做了编码式压缩，采用 Huffman 编码进行压缩和解压缩。 Huffman 编 码是一种可变长编码方式，是二叉树的一种特殊转化形式。编码的原理是：将使用次 数多的代码转换成长度较短的代码，而使用次数少的

3、可以使用较长的编码，并且保持 编码的唯一可解性。根据 ascii 码文件中各 ascii 字符出现的频率情况创建 Huffman 树，再将各字符对应的哈夫曼编码写入文件中。同时，亦可根据对应的哈夫 曼树，将哈夫曼编码文件解压成字符文件 .二、概要设计：主程序流程图：主函数输入测试字符、 串厂根据权值进行建立Huffman树kJ统计字符信息，建立 Huffman 曼 树LJ根据权值进行建立Huffman树输出Huffman树输出 Huffman输入 Huffman码，求得解码Z编码f厂解码丿11丿r1（输出编码 C压缩编码?i解压根据Huffman树，求得对应字符的Huffman 编码V,厂生成

4、压缩文件厂生成新的文本、文档1111 1f统计字符，得 .L (退出测试扫描压缩文件，载入字符信息j/出统计出的字符的权值n 丿压缩过程的实现：压缩过程的流程是清晰而简单的：1. 创建Huffman树2. 打开需压缩文件3. 将需压缩文件中的每个ascii码对应的huffman编码按bit单位输出生成压缩文件压缩结束。其中，步骤1和步骤3是压缩过程的关键。步骤1:这里所要做工作是得到 Huffman数中各叶子结点字符出现的频率并进行创 建统计字符出现的频率可以有很多方法：如每次创建前扫描被创建的文件，“实时”的 生成各字符的出现频率；或者是创建前即做好统计这里采用的是前一种方法。步骤3:将需压

5、缩文件中的每个 ascii码对应的huffman编码按bit单位输出. 这是本压缩程序中最关键的部分： 这里涉及“转换”和“输出”两个关键步骤：“转换”部分大可不必去通过遍历Huffman树来找到每个字符对应的哈夫曼编码，可以将每个Huffman码值及其对应的ascii码存放于如下所示的结 构体中：解压缩过程的实现：如果说，压缩的过程可以通过查找codeList来加速实现的话，而解压缩则必须通过查找huffman树才能加以实现.查找的过程是简单的，可以根据huffman树的性质来做，当haffCode的当前bit位为0时，则向左枝展开搜索；当前 bit位为1时，则向右枝展开搜索，当遇到叶子结点

6、时，则输出 haffCode对应的asciiCoda三、详细设计：核心算法源程序：Huffman树建立源程序：/huffma ntree.h霍夫曼树#ifndef HUFFMANTREE#defi ne HUFFMANTREE#defi ne Defaultsize 300#in clude #i nclude bi ntree.h#in clude heap.hclass Code public: int code; Code *link; Code(int c=0,Code *l=NULL):code(c),link(l);class CharNameNodepublic:un sig n

7、ed char char name; / 要这样才行Code *link;CharNameNode(unsigned char c=0,Code *l=NULL):charname(c),link(l);template class HuffmanTree:public BinaryTreepublic:int key;HuffmanTree();HuffmanTree(HuffmanTree &ht1,HuffmanTree &ht2)Type temp=0; / 可能有变key=ht1.key+ht2.key;root= new BinTreeNode(0,Copy(ht1.root),C

8、opy(ht2.root);void Build(int *fr,Type *value,int n,HuffmanTree &newtree);void Path(BinTreeNode *start,Code *first,Code *last,CharNameNode *Node,int&i); / 一个数组;template void HuffmanTree:Build(int *fr,Type *value,int n,HuffmanTree &newtree) /fr 为 value( 值 ) 对应的权int i;HuffmanTree first,second;HuffmanTr

9、ee NodeDefaultsize;MinHeap HuffmanTree hp;assert(n=0&n=Defaultsize);for(i=0;in;i+)Nodei.root=new BinTreeNode(valuei,NULL,NULL);Nodei.key=fri;hp=MinHeap HuffmanTree (Node,n);for(i=0;in-1;i+)hp.RemoveMin(first);hp.RemoveMin(second);HuffmanTree* temp=new HuffmanTree(first,second);hp.Insert(*temp);hp.Re

10、moveMin(newtree);templatevoid HuffmanTree:Path(BinTreeNode *start,Code *first,Code *last,CharNameNode *Node,int &i) / 一个数组if(start=NULL)return;/ if(start-GetData()!=0) / 是叶结点 严重错误，可能叶结点也是 0！ if(start-GetLeft()=NULL&start-GetRight()=NULL)Nodei.charname=start-GetData();Nodei.link=NULL;if(first=NULL)re

11、turn;Nodei.link=new Code(first-code);Code *p=first-link,*q=Nodei.link;while(p!=NULL)q-link=new Code(p-code); q=q-link;p=p-link; q-link=NULL; i+; return;Code *temp=new Code; / 进入左子树 assert(temp);if(first=NULL)first=last=temp;elselast-link=temp; last=last-link; Path(start-GetLeft(),first,last,Node,i);

12、 last-code=1;Path(start-GetRight(),first,last,Node,i); temp=first;if(first=last)delete last; first=last=NULL; return; while(temp-link!=last) temp=temp-link;temp-link=NULL; delete last; last=temp;#endif实现二叉树的算法源程序：/bintree.h/ 用指针实现的二叉树/Type类型必须有重载 与及=运算 #ifndef BINTREE#define BINTREE #include #includ

13、e int Max(int a,int b) return ab?a:b;template class BinaryTree;template class BinTreeNode friend class BinaryTree; public:BinTreeNode():leftchild(NULL),rightchild(NULL);BinTreeNode(Type item,BinTreeNode *left = NULL,BinTreeNode *right=NULL) :data(item),leftchild(left),rightchild(right);Type GetData(

14、)const return data; BinTreeNode *GetLeft()const return leftchild; BinTreeNode *GetRight()const return rightchild; void SetData(const Type &item) data=item; void SetLeft(BinTreeNode *L) leftchild = L; void SetRight(BinTreeNode *R) rightchild = R; private:BinTreeNode *leftchild, *rightchild;Type data;

15、 ;template class BinaryTreepublic:BinaryTree():root(NULL);BinaryTree(constBinaryTree(const&bt2);BinaryTree(TypeBinaryTree &bt) root=Copy(bt.root);BinaryTreeType &temp,const BinaryTree &bt1,constvalue):RefValue(value),root(NULL);void operator =(const BinaryTree &bt); virtual BinaryTree() Destroy(root

16、); void Destroy()Destroy(root);root=NULL; virtual int IsEmpty() return root=NULL?1:0; virtual BinTreeNode *Parent(BinTreeNode *current) return root=NULL|root=current? NULL : Parent(root,current);virtual BinTreeNode *LeftChild(BinTreeNode *current)return root!=NULL? current-leftchild : NULL;virtual B

17、inTreeNode *RightChild(BinTreeNode *current)return root!=NULL? current-rightchild : NULL;virtual int Insert(const Type &item);virtual int Find(const Type &item)const;BinTreeNode *GetRoot()const return root; friend int Equal(BinTreeNode *a,BinTreeNode *b);friend int operator =(const BinaryTree &bt1,c

18、onst BinaryTree &bt2); friend istream& operator (istream &in, BinaryTree &Tree);/ 遍历friend ostream& operator (ostream &out,BinaryTree &Tree );void InOrder(); void PreOrder();/ 统计结点数/ 计算树的深度void PostOrder(); /* int Size() return Size(root); int Depth() return Depth(root); int Leaves() return Leaves(r

19、oot); int Degrees1() return Degrees1(root); int Degrees2() return Degrees2(root); protected:BinTreeNode *root;Type RefValue;BinTreeNode *Parent(BinTreeNode *start,BinTreeNode *current); int Insert (BinTreeNode *current,const Type &item);int Find(BinTreeNode *current,const Type &item)const; BinTreeNo

20、de* Copy(BinTreeNode *originode); void Destroy(BinTreeNode *current);/*void InOrder(BinTreeNode *current); void PreOrder(BinTreeNode *current);void PostOrder(BinTreeNode *current);/ 一些应用/ /*int Size(const BinTreeNode *t)const;int Depth(const BinTreeNode *t)const;int Leaves(const BinTreeNode *t)const

21、;int Degrees1(const BinTreeNode *t)const;int Degrees2(const BinTreeNode *t)const; ;template BinTreeNode* BinaryTree:Copy(BinTreeNode *orignode) if(orignode=NULL)return NULL;BinTreeNode *temp=new BinTreeNode; temp-data=orignode-data;temp-leftchild=Copy(orignode-leftchild); temp-rightchild=Copy(origno

22、de-rightchild); return temp; template BinaryTree:BinaryTree(const Type &temp,const BinaryTree &bt1,const BinaryTree &bt2)root=new BinTreeNode(temp,Copy(bt1.root),Copy(bt2.root);=(const BinaryTree &bt1)/ 为什么要这样？template void BinaryTree:operator Destroy();/ Destroy(root);root=NULL; root=Copy(bt1.root)

23、; template*current)void BinaryTree:Destroy(BinTreeNode if(current!=NULL)Destroy(current-leftchild);Destroy(current-rightchild);delete current;templateBinTreeNode * BinaryTree:Parent(BinTreeNode *start,BinTreeNode *current)if(start=NULL) return NULL;if(start-leftchild=current | start-rightchild=curre

24、nt) return start;BinTreeNode *p=NULL;if(p=Parent(start-leftchild, current)!=NULL) / 在 start 的左子树中找 return p;elsereturn Parent(start-rightchild,current);templateint BinaryTree:Insert(BinTreeNode *current,const Type &item)if(current=NULL) return 0;BinTreeNode *p=new BinTreeNode(item,NULL,NULL); if(cur

25、rent-leftchild=NULL)current-leftchild=p;else if(current-rightchild=NULL) current-rightchild=p;else Insert(current-leftchild,item); / 这样插可是构不成树状的！估且一用吧 return 1;templateint BinaryTree:Insert(const Type &item)if(root=NULL)root=new BinTreeNode(item,NULL,NULL); return 1;return Insert(root,item);template

26、int BinaryTree:Find(BinTreeNode *current,const Type &item)const if(current=NULL) return 0;if(current-data=item)return 1;int k; if(k=Find(current-leftchild,item)!=0) return 1;else return Find(current-rightchild,item);templateint BinaryTree:Find(const Type &item)constreturn Find(root,item);templateint

27、 Equal(BinTreeNode *a,BinTreeNode *b) 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&bt2)int operator =(const BinaryTree &bt1,const BinaryTree return Equal(bt1.root,bt2.root);templateistr

28、eam& operator(istream &in,BinaryTree &Tree)Type item;cout 构造二叉树 :n;cout 输入数据 ( 用 Tree.RefValue item;while(item!=Tree.RefValue) Tree.Insert(item); cout 输入数据 ( 用 Tree.RefValueitem;return in;templateostream& operator(ostream &out,BinaryTree &Tree)out 二叉树的前序遍历 .n;Tree.PreOrder(); outendl;return out;/*te

29、mplate void BinaryTree :InOrder()InOrder(root);*current)template void BinaryTree:InOrder(BinTreeNode if(current!=NULL)InOrder(current-leftchild);cout datarightchild);template void BinaryTree :PreOrder() PreOrder(root); template void BinaryTree:PreOrder(BinTreeNode *current) if(current!=NULL)coutdata

30、leftchild);PreOrder(current-rightchild);template void BinaryTree:PostOrder()PostOrder(root); template void BinaryTree:PostOrder(BinTreeNode *current) if(current!=NULL)PostOrder(current-leftchild);PostOrder(current-rightchild);coutdata ;/*/ 一些应用*t)const* template int BinaryTree:Size(const BinTreeNode

31、 if(t=NULL)return 0;elsereturn 1+Size(t-leftchild)+Size(t-rightchild); template int BinaryTree:Depth(const BinTreeNode *t)constif(t=NULL)return -1;elsereturn 1+Max(Depth(t-leftchild),Depth(t-rightchild);template int BinaryTree:Leaves(const BinTreeNode *t)const if(t=NULL) return 0; if(t-leftchild=NUL

32、L&t-rightchild=NULL) /t 是叶子结点 return 1;return Leaves(t-leftchild)+Leaves(t-rightchild);template int BinaryTree:Degrees1(const BinTreeNode *t)const if(t=NULL)return 0;if(t-leftchild=NULL&t-rightchild!=NULL) |(t-leftchild!=NULL&t-rightchild=NULL) /t 的度为 1 return 1+Degrees1(t-leftchild)+Degrees1(t-righ

33、tchild);return Degrees1(t-leftchild)+Degrees1(t-rightchild);template int BinaryTree:Degrees2(const BinTreeNode *t)const if(t=NULL) return 0;if(t-leftchild!=NULL&t-rightchild!=NULL) /t 的度为 2return 1+Degrees2(t-leftchild)+Degrees2(t-rightchild); return Degrees2(t-leftchild)+Degrees2(t-rightchild);#end

34、if堆程序：/ 堆#include #include #include /Type类型必须有key成员！及vv =及拷贝构造运算!template class MinPQpublic:virtualint Insert(const Type &)=0;virtualint RemoveMin(Type &)=0;template class MinHeap:public MinPQpublic:MinHeap(int maxsize=DefaultSize);MinHeap(Type arr,int n);MinHeap(const MinHeap &R);MinHeap()delete he

35、ap;void operator =(const MinHeap &R);int Insert(const Type &x);int RemoveMin(Type &x);int IsEmpty() const return currentsize=0;int IsFull() const return currentsize=maxheapsize;void MakeEmpty()currentsize=0;void Display();/ 调试时使用private:enum DefaultSize=10;Type *heap;int currentsize;int maxheapsize;

36、void FilterDown(const int start,constint endofheap);/ 从 i 至U m向下进行调整成为最小堆void FilterUp(int start);/从i到m自底向上进行调整成为最小堆;template MinHeap:MinHeap(int maxsize)maxheapsize=DefaultSizemaxsize?maxsize:DefaultSize;heap=new Typemaxheapsize;assert(heap);currentsize=0;template MinHeap:MinHeap(Type arr,int n)max

37、heapsize=DefaultSizen?n:DefaultSize;heap=new Typemaxheapsize;assert(heap);for(int i=0;i=0)FilterDown(currentpos,currentsize-1); currentpos-;template MinHeap:MinHeap(const MinHeap &R)heap=new Type1;*this=R; template void MinHeap:operator =(const MinHeap &R) maxheapsize=R.maxheapsize; delete heap; hea

38、p=new Typemaxheapsize; assert(heap); currentsize=R.currentsize; for(int i=0;icurrentsize;i+) heapi=R.heapi; return;template void MinHeap:FilterDown(const int start,const int endofheap)int i=start,j=2*i+1;Type temp=heapi; while(j=endofheap)if(jheapj+1.key)j+;if(temp.key=heapj.key) break;elseheapi=hea

39、pj; i=j;j=2*i+1; heapi=temp;template void MinHeap:FilterUp(intint j=start,i=(j-1)/2;Type temp=heapj; while(j0)if(heapi.keytemp.key) break;else heapj=heapi; j=i;i=(j-1)/2;heapj=temp;template int MinHeap:Insert(const if(currentsize=maxheapsize) / heap.key 关键码start)Type &x)/ heap.key 关键码，cerr 堆已满 !n; r

40、eturn 0;heapcurrentsize=x;FilterUp(currentsize); currentsize+; return 1;template int MinHeap:RemoveMin(Type &x) if(!currentsize)cerr 堆空 !n;return 0; x=heap0; heap0=heapcurrentsize-1; currentsize-;FilterDown(0,currentsize-1);return 1;template void MinHeap:Display()for(int i=0;icurrentsize;i+) couthea

41、pi ;coutpressTest.HFI -记事本文件 编辑喲 格式 查看 帮助6 3?19?1 23 tes 1+ tt 101262 f 6 i m 3 n 3 s 231 ?2 ?1 ?1 ?2 ?31 ?9 ?54 ?16 ?6 ?7 ?10 ?24 ?8 ?20 ?15 ?29 ?17 ?17 ?21 ?20 ?8 ?73 ?21 ?16 ?5 ?19 ?3 ?410 6 21 2 2 4nr* 7+ 744 -zb- ?* tl?2 5 ? 2 R?4? 118 ? ?39 2 04 ? 1? ?85 4 7 * 7+ 7+ ?92 ?63 24 1C7# 11- 1*? ?5 47* O6 34 ?3 74?1 ?22 ? ?13 ?3 ?6 ?2 ?3 ?1 ?12 ?3 ?4 ?10 ?5 ?15 ?12 ?6 ?7 ?7 ?3 ?4 ?4 ?10 ?13加慑J !7ey霹畋？匚廓掃驹仏T朴：二?E蛉 亡？曜B?y 7暉？列町丄聚輪丨0?Bgy72冬？縷（=1 s=Z !| ?-0#! fd凤產？都U?髦？XfL?t： ?攜炭D 槨挣奇？號 帯轿彳傩凤？IK q 痉葷逢匚眠眸炕婕/恂掣關茄_4Ffg?L號时IJ嵋b嶷?営粪&?F通28 叮-切1號 ？固脱？卜D8喘4眸馭？cW爭+龜X 。？潸