压缩程序设计报告.doc

课程设计报告课程名称：操作系统 实验题目：文件压缩程序院 系：计算机科学与工程学院班 级： 姓 名： 学 号： 二一一年七月一日一、 需求分析： 有两种形式的重复存在于计算机数据中，文件压缩程序就是对这两种重复进行了压缩。一种是短语形式的重复，即三个字节以上的重复，对于这种重复，压缩程序用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩。第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。给 256 种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于变长的字节更多，文件的总长度就会减少，并且，字节使用比例越不均匀，压缩比例就越大。编码式压缩必须在短语式压缩之后进行，因为编码式压缩后，原先八位二进制值的字节就被破坏了，这样文件中短语式重复的倾向也会被破坏（除非先进行解码）。另外，短语式压缩后的结果：那些剩下的未被匹配的单、双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺序不能变。本程序设计只做了编码式压缩，采用Huffman编码进行压缩和解压缩。Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。根据 ascii 码文件中各 ascii 字符出现的频率情况创建 Huffman 树，再将各字符对应的哈夫曼编码写入文件中。同时，亦可根据对应的哈夫曼树，将哈夫曼编码文件解压成字符文件.二、 概要设计：主程序流程图：主函数统计字符，得出统计出的字符的权值n编码解码退出根据权值进行建立Huffman树输出Huffman树输出编码压缩编码生成压缩文件解压生成新的文本文档 扫描压缩文件，载入字符信息根据权值进行建立Huffman树输出Huffman树 测试输入测试字符串统计字符信息，建立Huffman曼树根据Huffman树，求得对应字符的Huffman编码输入Huffman编码，求得解码压缩过程的实现: 压缩过程的流程是清晰而简单的: 1. 创建 Huffman 树 2. 打开需压缩文件 3. 将需压缩文件中的每个 ascii 码对应的 huffman 编码按 bit 单位输出生成压缩文件压缩结束。 其中，步骤 1和步骤 3是压缩过程的关键。 步骤1:这里所要做工作是得到 Huffman数中各叶子结点字符出现的频率并进行创建.统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件，“实时”的生成各字符的出现频率;或者是创建前即做好统计.这里采用的是前一种方法。 步骤 3: 将需压缩文件中的每个 ascii 码对应的 huffman 编码按 bit 单位输出. 这是本压缩程序中最关键的部分: 这里涉及“转换”和“输出”两个关键步骤： “转换”部分大可不必去通过遍历 Huffman 树来找到每个字符对应的哈夫曼编码，可以将每个 Huffman 码值及其对应的 ascii 码存放于如下所示的结构体中：解压缩过程的实现: 如果说,压缩的过程可以通过查找 codeList 来加速实现的话，而解压缩则必须通过查找 huffman 树才能加以实现.查找的过程是简单的，可以根据huffman 树的性质来做，当 haffCode的当前 bit 位为 0 时，则向左枝展开搜索;当前bit 位为1时，则向右枝展开搜索，当遇到叶子结点时，则输出haffCode对应的 asciiCode。三、 详细设计：核心算法源程序：Huffman树建立源程序：/-/huffmantree.h/霍夫曼树#ifndef HUFFMANTREE#define HUFFMANTREE#define Defaultsize 300#include #include bintree.h#include heap.hclass Codepublic: int code; Code *link; Code(int c=0,Code *l=NULL):code(c),link(l);class CharNameNodepublic: unsigned char charname; /要这样才行 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),Copy(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; HuffmanTree 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.RemoveMin(newtree);template void 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) return; 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; else last-link=temp; last=last-link; Path(start-GetLeft(),first,last,Node,i); 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 #include 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()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;template class BinaryTree public: BinaryTree():root(NULL); BinaryTree(const BinaryTree &bt) root=Copy(bt.root); BinaryTree(const Type &temp,const BinaryTree &bt1,const BinaryTree &bt2); BinaryTree(Type value):RefValue(value),root(NULL); void operator =(const BinaryTree &bt); virtual BinaryTree() Destroy(root); 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 BinTreeNode *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,const 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(root); 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; BinTreeNode* 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; 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(orignode-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); template void BinaryTree:operator =(const BinaryTree &bt1) Destroy();/ Destroy(root);root=NULL; /为什么要这样？ root=Copy(bt1.root);template void BinaryTree:Destroy(BinTreeNode *current) if(current!=NULL) Destroy(current-leftchild); Destroy(current-rightchild); delete current; template BinTreeNode * BinaryTree:Parent(BinTreeNode *start,BinTreeNode *current) if(start=NULL) return NULL; if(start-leftchild=current | start-rightchild=current) return start; BinTreeNode *p=NULL; if(p=Parent(start-leftchild, current)!=NULL) /在start的左子树中找 return p; else return Parent(start-rightchild,current);template int BinaryTree:Insert(BinTreeNode *current,const Type &item) if(current=NULL) return 0; BinTreeNode *p=new BinTreeNode(item,NULL,NULL); if(current-leftchild=NULL) current-leftchild=p; else if(current-rightchild=NULL) current-rightchild=p; else Insert(current-leftchild,item); /这样插可是构不成树状的！估且一用吧 return 1;template int BinaryTree:Insert(const Type &item) if(root=NULL) root=new BinTreeNode(item,NULL,NULL); return 1; return Insert(root,item);template 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);template int BinaryTree:Find(const Type &item)const return Find(root,item);templateint 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;templateint operator =(const BinaryTree &bt1,const BinaryTree &bt2) return Equal(bt1.root,bt2.root);template istream& 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;template ostream& operator(ostream &out,BinaryTree &Tree) out二叉树的前序遍历.n; Tree.PreOrder(); outendl; return out;/*template void BinaryTree :InOrder() InOrder(root);template void BinaryTree:InOrder(BinTreeNode *current) if(current!=NULL) InOrder(current-leftchild); cout datarightchild); template void BinaryTree :PreOrder() PreOrder(root);template void BinaryTree:PreOrder(BinTreeNode *current) if(current!=NULL) coutdataleftchild); 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 ; /*/一些应用template int BinaryTree:Size(const BinTreeNode *t)const if(t=NULL) return 0; else return 1+Size(t-leftchild)+Size(t-rightchild);template int BinaryTree:Depth(const BinTreeNode *t)const if(t=NULL) return -1; else return 1+Max(Depth(t-leftchild),Depth(t-rightchild); template int BinaryTree:Leaves(const BinTreeNode *t)const if(t=NULL) return 0; if(t-leftchild=NULL&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-rightchild); 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 的度为2 return 1+Degrees2(t-leftchild)+Degrees2(t-rightchild); return Degrees2(t-leftchild)+Degrees2(t-rightchild);#endif堆程序：/-/堆#include #include #include /Type 类型必须有key成员！及及拷贝构造运算！template class MinPQpublic: virtual int Insert(const Type &)=0; virtual int RemoveMin(Type &)=0;template class MinHeap:public MinPQpublic: MinHeap(int maxsize=DefaultSize); MinHeap(Type arr,int n); MinHeap(const MinHeap &R); MinHeap()delete heap; 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; void FilterDown(const int start,const int endofheap); /从i到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) maxheapsize=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; heap=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+; / heap.key 关键码 if(temp.key=heapj.key) break; else heapi=heapj; i=j; j=2*i+1; heapi=temp; template void MinHeap:FilterUp(int start) int j=start,i=(j-1)/2; Type temp=heapj; while(j0) if(heapi.keytemp.key) / heap.key 关键码， break; else heapj=heapi; j=i; i=(j-1)/2; heapj=temp;template int MinHeap:Insert(const Type &x) if(currentsize=maxheapsize) cerr堆已满!n; return 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:Di