数据结构课程设计报告
《数据结构与算法》课程设计报告
学号：
班级序号：
姓名：
指导教师：
成绩：
中国地质大学信息工程学院地理信息系统系
2011年12 月
1．需求规格说明
【问题描述】
利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件。
【基本要求】
一个完整的系统应具有以下功能：
（1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。
（2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件(*.Haf)。
（3）解压缩。打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。
（4）程序使用命令行方式运行
压缩命令：SZip A Test.Haf 1.doc
解压缩命令：SZip X Test.Haf 2.doc或SZip X Test.Haf
用户输入的命令不正确时，给出提示。
（5）使用面向对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。
2．总体分析与设计
（1）设计思想：
1、压缩准备：1> 读文件，逐个读取字符，统计频率
2> 建立哈夫曼树
3> 获得哈弗曼编码
2、压缩过程：
1> 建立一个新文件，将储存权值和字符的对象数组取存储在文件头
2> 从头连续读取源文件中的每个字符，对于所读取的每一个字符到统计表中
查找相应的哈弗曼编码，每8位转换成一个ascii码，转换成字符存入新文件，不
足八位的继续读取下一个字符，即：字符->哈弗曼编码->8位的二进制->ASCII码
->字符，直到文件结束
3> 统计文件大小，利用改变流指针的位置指向文件头和尾统计字符个数来统
计文件大小
3、解压过程：1> 将存于文件头的权值和字符的对象数组取出
3> 重新建立哈夫曼树
2> 建立一个新文件，从源文件中读取一个字符->ASCII码->8位的二进制->
遍历树，遇到叶子节点则将节点中存的字符写入新文件，再读取下一个字符，直到
文件结束
（2）设计表示：
统计频率：建立哈夫曼树：
GetFrequency() GetTree()
Judge(int c) HuffmanTree(charnode *ch, int n)
MakeTree(const T& element Initialize(T a[], BinaryTree
获得哈弗曼编码：压缩过程：
Coding() StoreIntoNew ()
GetIndex(char) GetIndex(char) EachStore(int ,ofstream &) ChangeInto(int a[])
解压过程：
Uncompress()
Restore(BinaryTree
,int a,ofstream &output) ,int a,ofstream &output)
（3）详细设计表示：
class Compress
{
friend BinaryTree
Compress();
void GetFrequency();
bool Judge(int c);//判断是否c是否被读过
int GetIndex(char c);//获取对应字符的索引
void GetTree();//建立哈夫曼树
void Coding();//获得哈弗曼编码
int ChangeInto(int a[]);//将每位转化成一个int
void EachStore(int a,ofstream &output);
void StoreIntoNew();//将对应ASCII码存入新文件
void Restore(BinaryTree
void Rechange(BinaryTree
void Uncompress();//解压
private:
char *filepath;//源文件路径
char *filepath2;//压缩后文件的路径
char *filepath3;//解压后文件路径
charnode ch[257];
int count;//调试后发现为：字符的种数-1
BinaryTree
BinaryTreeNode
void coding(BinaryTreeNode
int bit[8];//存八位以供转化为ASCII码
int bitcount;
int total;//编码总长度
int currentcount;//解压时纪录当前已解压的编码长度
};
字符类
class charnode
{
public:
charnode(){weigh=0;codelen=0;asciikey=0;}
char character;//字符
int asciikey;//字符对应的ASCII码
int weigh;//权重
int code[100];//存储哈弗曼编码
int codelen;
};
3．编码
1、用eof()作为循环控制条件时，总是会重复读取最后一个字符。解决方法将while(input.eof()){...}改为while(true){input.get(temp);if(input.eof())break;...}
2、在获得字符的哈弗曼编码，本来觉得就是一个前序遍历，但要编码与遍历时刻同步却是个难点，最后决定用链表代替栈，并且调整了顺序，首先判断是否需要导出编码，便于递归
3、在压缩的时候首先想到要怎么解压，所以将解压所需的信息储存到文件头，却不能直接储已经存建立好的哈夫曼树，最后想到将建树所需的信息储存起来在解压前再建立一个相同的树
4、对于源文件末尾编码不满8位字符的处理，将缺位数补零，在解压时仅遍历到总编码位数（已保存在文件头）
5、在解压时，挨个读取压缩文件的字符时会有负数，第一次并没有考虑到，将十进制转化为二进制时得到的都是0，后面调试时才发现这个问题，于是在转化前首先判断正负，若是负数则加上256
6、关于封装读取的字符类，前前后后改了很多次，最开始是结构体，结果不会调用，后面改成类，对于他的私有数据增增减减好几次
4．程序及算法分析初始界面
压缩功能
压缩后生成的文件
解压功能
解压后的文件
退出程序
5．小结
6．附录
统计频率
while(true)
{
input.get(temp);//get(char& ch)是从流中读取一个字符，结果保存在引用ch 中，如果到文件尾，返回空字符。
if(input.eof())break;
if(!Judge((int)temp))//Judge()判断该字符是否出现过
{
ch[count].asciikey=(int)temp;
ch[count].character=temp;
ch[count].weigh++;
count++; }
}
input.close();
}
获得哈弗曼编码
void Compress::coding(BinaryTreeNode
{
if(t->LeftChild==0 && t->RightChild==0)//当到达叶节点，然后读取相应队列中的代码存放到该编码
{
int index=GetIndex(t->data);
A.GetCode(ch[index]);//存储哈弗曼编码
A.Delete(A.Length());
}
else {
if(t->LeftChild )
{
A.Insert(A.Length(),0);//向左走记为0
coding(t->LeftChild,A);
}
if(t->RightChild )
{
A.Insert(A.Length(),1);//向右走记为1
coding(t->RightChild,A);
}
A.Delete(A.Length());
}
}
压缩过程
void Compress::StoreIntoNew()//将对应ASCII码存入新文件
{
ifstream input;
input.open(filepath);//读入的源文件
cout<<"输入压缩后的文件路径输入文件名.Haf:"< cin>>filepath2; ofstream output; output.open(filepath2,ios::binary | ios::out); if(!output)//顺利打开否 { cout <<"打开错误！"< } bt.count=count-1;//记录下字符的种数，以便解压 bt.total =0; for(int i=1;i<=count-1;i++)//计算字符的总数 bt.total+=ch[i].codelen*ch[i].weigh; https://www.sodocs.net/doc/07720375.html,ckcount=bt.total%8; //解压的时候发现必须记录下不满位的个数output.write((char *)&bt,sizeof(bt));//将构造好的哈弗曼树存储于文件中 StoredNode snode[257]; for(int i=1;i { snode[i].character=ch[i].character ; snode[i].weigh =ch[i].weigh ; } output.write ((char*)&snode,sizeof(snode)); output.flush();//刷新缓冲，并将缓存中的内容写入文件 char temp; int i,j; input.get(temp); while(!input.eof())//读取每一个字符，直到文件末尾{ j=GetIndex(temp); for(i=0;i<=ch[j].codelen-1;i++)//逐个bit送入 { EachStore(ch[j].code[i],output);//每八位一输出 } input.get(temp); } if(bitcount!=0)//处理不足位数的编码 { for(int i=bitcount;i<8;i++) bit[i]=0; int n=ChangeInto(bit); output<<(char)n; output.flush(); } input.close (); output.close (); ifstream file(filepath, ios::in|ios::binary); long l1,m1; l1=file.tellg(); file.seekg(0,ios::end); m1=file.tellg(); cout<<"压缩前文件："<<(m1-11)/1024<<"KB"< file.open(filepath2,ios::binary | ios::in); long l2,m2; l2=file.tellg(); file.seekg(0, ios::end); m2 = file.tellg(); cout<<"压缩后文件："<<(m2-12)/1024<<"KB"< file.close (); cout<<"压缩完毕"< } 解压过程 void Compress::Uncompress()//解压 { cout<<"输入要解压的文件路径，输入文件名:"< cin>>filepath2; fstream input; input.open(filepath2,ios::binary | ios::in); if(!input) { cout <<"打开错误！"< } cout<<"请输入解压后文件路径: "< cin>>filepath3; ofstream output; output.open(filepath3,ios::app);//ios::app—所有输出附加在文件末尾while(!output) { cout <<"打开错误！"< cout<<"请重新输入解压后文件的路径"< cin>>filepath3; } BinaryTree input.read((char *)&bc,sizeof(bc)); //读取哈夫曼树 StoredNode snode[256]; input.read((char *)&snode,sizeof(snode)); int tempbc1,tempbc2; tempbc1=bc.count ; tempbc2=https://www.sodocs.net/doc/07720375.html,ckcount ; total=bc.total ; bc=HuffmanTree(snode,bc.count);//重新建树bc.count=tempbc1; https://www.sodocs.net/doc/07720375.html,ckcount=tempbc2; tnode=bc.root; char temcha; int intcha; input.get(temcha); while(!input.eof()) { intcha=(int)temcha; if(intcha<0) intcha+=256; Rechange(bc,intcha,output); input.get(temcha); } input.close(); output.close(); cout<<"解压完成"< }