用C++编写的文件压缩解压程序

huffmantreemain cpp 主界面 include huffmantree h include include include compress1 h include Ceshi h void menu cout endl cout t t 操作菜单 n n cout t t t 1 压缩文件 n cout t t t 2 解压文件 n cout t t t 3 测试 n cout t t t 0 退出 n n n n return int main char meiyong cout n n n n n n n n n t cin setf 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 n n n n n n cout n cout t t n cout t t 实验六 霍夫曼树的应用 n cout t n cout t t 作者 gdgzzch 学号 15201314 n cout t t n n cout t t 2005 11 16 n n menu int choice cout choice while 1 switch choice case 1 Compress break case 2 Decompress break case 3 Ceshi break case 0 cout n n t t 谢谢您使用本软件 再见 n n n n return 1 default cout 无此操作 n n cout endl choice return 1 compress1 h 压缩 ifndef COMPRESS define COMPRESS include huffmantree h include include include include 压缩函数 void Compress unsigned char ch int i j k int Charnum 256 unsigned char Chars 256 与下面共同使用 记录字符 int Charnums 256 记录对应字符的个数 int CharKinds 字符种数 char filenameorg 21 文件名不超过 20 个字符 源文件名 char filenameaim 21 目标文件名 int fileorgsize 源文件大小 int fileaimsize 压缩文件大小 HuffmanTree ht CharNameNode NameNode 256 存储字符对应的霍夫曼编码 BinTreeNode btn NULL Code first NULL Code last NULL ifstream filein ofstream fileout cout filenameorg filein open filenameorg ios nocreate ios binary open filenameorg if filein cout filenameorg 不存在 n filein clear return cout filenameaim char filetype 5 int len len strlen filenameaim if len 4 cout filenameaim len 4 i j filetype j filenameaim i filetype 4 0 if strcmp filetype HFM 0 cout filenameaim 文件的扩展名必须为 HFM n return for i 0 i ch Charnum unsigned int ch 统计每种字符的频数 fileorgsize filein setf ios skipws filein close close filenameorg j 0 for i 0 i 256 i if Charnum i Chars j unsigned char i 统计源文件中存在的字符的 Charnums j Charnum i j CharKinds j fileaimsize 0 计算压缩文件大小 fileout open filenameaim ios binary fileout 0 非法位数 之后修改 fileout filenameorg fileout CharKinds 存入字符种类 fileaimsize 7 for i 0 i CharKinds i fileout Chars i Charnums i ch i 0 while ch NameNode i charname 找到 ch i Code p NameNode i link while p NULL j code k if k 8 fileout link filein setf ios skipws filein close if k 8 j 8 k fileout unsigned char j fileaimsize 计算压缩文件大小 fileout seekp 0 ios beg fileout 8 k 修改非法代码的位数 fileout close for i 0 ilink delete s NameNode i link NULL 清除链表信息 ht Destroy cout 文件压缩成功 压缩率为 fileaimsize 100 fileorgsize endl return void Decompress unsigned char ch int i j k unsigned char Chars 256 与下面共同使用 记录字符 int Charnums 256 记录对应字符的个数 int CharKinds 字符种数 unsigned int total 记录字符转化后的数 int fpend 暂存文件指针的最后位置 char filenameorg 21 文件名不超过 20 个字符 源文件名 char filenameaim 21 目标文件名 HuffmanTree ht CharNameNode NameNode 256 存储字符对应的霍夫曼编码 BinTreeNode btn NULL Code first NULL Code last NULL ifstream filein ofstream fileout char filetype 5 int len cout filenameorg len strlen filenameorg if len 4 cout filenameorg len 4 i j filetype j filenameorg i filetype 4 0 if strcmp filetype HFM 0 cout filenameorg 不是霍夫曼编码的程序 不能解压 n return filein open filenameorg ios nocreate ios binary if filein cout filenameorg 不存在 n filein clear return filein close cout filenameaim filein open filenameorg ios nocreate ios binary if filein cout k ch 最后一个字符不合法的位数 filein filenameaim ch filein CharKinds ch for i 0 i Chars i ch Charnums i ch 载入字符信息 ht Build Charnums Chars CharKinds ht 建立霍夫曼树 btn ht GetRoot fileout open filenameaim ios binary 以文本文件打开 if fileout cout ch total unsigned int ch 这里都是正确的 j 0 if filein tellg fpend 到了文件尾 j k 留 k 位不输出 for i 7 i j i if total else btn btn GetLeft if btn GetData 0 if btn GetLeft NULL btn ht GetRoot fileout close filein setf ios skipws filein close ht Destroy cout 解压成功 n cout 保存在 filenameaim 中 endl return endif huffmantree h 霍夫曼树 ifndef HUFFMANTREE define HUFFMANTREE define Defaultsize 300 include include bintree h include heap h class Code public int code Code link Code int c 0 Code l NULL code c link l class CharNameNode public unsigned char charname 要这样才行 Code link CharNameNode unsigned char c 0 Code l NULL charname c link l template class HuffmanTree public BinaryTree public int key HuffmanTree HuffmanTree HuffmanTree 可能有变 key ht1 key ht2 key root new BinTreeNode 0 Copy ht1 root Copy ht2 root void Build int fr Type value int n HuffmanTree void Path BinTreeNode start Code first Code last CharNameNode Node int 一个数组 template void HuffmanTree Build int fr Type value int n HuffmanTree HuffmanTree first second HuffmanTree Node Defaultsize MinHeap HuffmanTree hp assert n 0 for i 0 i n i Node i root new BinTreeNode value i NULL NULL Node i key fr i hp MinHeap HuffmanTree Node n for i 0 i n 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 if start GetData 0 是叶结点 严重错误 可能叶结点也是 0 if start GetLeft NULL Node i link NULL if first NULL return Node i link new Code first code Code p first link q Node i 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 ceshi h 测试 ifndef CESHI define CESHI include compress1 h include include void Ceshi unsigned char ch int i j k int Charnum 256 unsigned char Chars 256 与下面共同使用 记录字符 int Charnums 256 记录对应字符的个数 int CharKinds 字符种数 unsigned char string 301 unsigned char acharp 字符指针 int length 报文长度 HuffmanTree ht CharNameNode NameNode 256 存储字符对应的霍夫曼编码 BinTreeNode btn NULL Code first NULL Code last NULL Code pCode NULL 临时使用 unsigned int total int fpend ofstream fileout ifstream filein cout string acharp string for i 0 i 256 i Charnum i 0 记录每一个字符的个数 Charnums i 0 记录字符 Char i 的个数 while acharp 0 Charnum unsigned int acharp 统计每种字符的频数 acharp j 0 for i 0 i 256 i if Charnum i Chars j unsigned char i 统计字符串中存在的字符的 Charnums j Charnum i j CharKinds j fileout open temp txt ios binary 输出到临时文件中保存 fileout 0 非法位数 之后修改 fileout CharKinds 存入字符种类 for i 0 i CharKinds i fileout Chars i Charnums i 将字符信息存入临时文件 ht Build Charnums Chars CharKinds ht 建立霍夫曼树 i 0 ht Path ht GetRoot first last NameNode i 搜索霍夫曼树求得字符对应的霍夫曼编码 cout 各字符的霍夫曼编码 n for i 0 i CharKinds i cout t NameNode i charname pCode NameNode i link while pCode NULL cout code pCode pCode link cout endl k 0 j 0 length 0 报文长度 acharp string cout 报文 while acharp 0 i 0 while acharp NameNode i charname 找到 ch i pCode NameNode i link while pCode NULL length j code cout code k if k 8 fileout link acharp cout n 长度 length endl if k 8 j 8 k fileout unsigned char j fileout seekp 0 ios beg fileout 8 k 修改非法代码的位数 fileout close for i 0 ilink delete s NameNode i 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 最后一个字符不合法的位数 filein CharKinds ch for i 0 i Chars i ch Charnums i ch 载入字符信息 ht Build Charnums Chars CharKinds ht 建立霍夫曼 btn ht GetRoot cout ch total unsigned int ch 这里都是正确的 j 0 if filein tellg fpend 到了文件尾 j k 留 k 位不输出 for i 7 i j i if total else btn btn GetLeft if btn GetData 0 cout GetData btn ht GetRoot cout endl filein setf ios skipws filein close cout string acharp string cout GetRight else btn btn GetLeft if btn GetData 0 cout GetData btn ht GetRoot acharp cout endl ht Destroy return endif bintree h 用指针实现的二叉树 Type 类型必须有重载 及 运算 ifndef BINTREE define BINTREE include include int Max int a int b return a b 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 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 BinaryTree const Type BinaryTree Type value RefValue value root NULL void operator const BinaryTree 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 virtual int Find const Type BinTreeNode GetRoot const return root friend int Equal BinTreeNode a BinTreeNode b friend int operator const BinaryTree friend istream friend ostream 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 int Find BinTreeNode current const Type 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 template void BinaryTree operator const BinaryTree 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 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 return 1 return Insert root item template int BinaryTree Find BinTreeNode current const Type 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 template int Equal BinTreeNode a BinTreeNode b if a NULL if a NULL return 0 template int operator const BinaryTree template istream cout 构造二叉树 n cout 输入数据 用 Tree RefValue item while item Tree RefValue Tree Insert item cout 输入数据 用 Tree RefValue item return in template ostream Tree PreOrder out endl return out template void BinaryTree InOrder InOrder root template void BinaryTree InOrder BinTreeNode current if current NULL InOrder current leftchild cout data rightchild template void BinaryTree PreOrder PreOrder root template void BinaryTree PreOrder BinTreeNode current if current NULL cout data 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 cout data 一些应用 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 return Leaves t leftchild Leaves t rightchild template int BinaryTree Degrees1 const BinTreeNode t const if t NULL return 0 if t leftchild NULL return Degrees1 t leftchild Degrees1 t rightchild template int BinaryTree Degrees2 const BinTreeNode t const if t NULL return 0 if t leftchild NULL return Degrees2 t leftchild Degrees2 t rightchild endif 堆 include include include Type 类型必须有 key 成员 及 及拷贝构造运算 template class MinPQ public virtual int Insert const Type virtual int RemoveMin Type template class MinHeap public MinPQ public MinHeap int maxsize DefaultSize MinHeap Type arr int n MinHeap const MinHeap MinHeap delete heap void operator const MinHeap int Insert const Type int RemoveMin Type int IsEmpty const return currentsize 0 int IsFull const return currentsize maxheapsize void MakeEmpty currentsize 0 void Display