数据结构课程设计报告-1

1/1数据结构课程设计报告

《数据结构与算法》课程设计报告

学号：

班级序号：

姓名：

指导老师：

成果：

中国地质高校信息工程学院地理信息系统系

2023年12月

1．需求规格说明

【问题描述】

利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，削减存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件。

【基本要求】

一个完整的系统应具有以下功能：

（1）压缩预备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。

（2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件(*.Haf)。

（3）解压缩。打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。

（4）程序使用命令行方式运行

压缩命令：SZipATest.Haf1.doc

解压缩命令：SZipXTest.Haf2.doc或SZipXTest.Haf

用户输入的命令不正确时，给出提示。

（5）使用面对对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。

2．总体分析与设计

（1）设计思想：

1、压缩预备：1>读文件，逐个读取字符，统计频率

2>建立哈夫曼树

3>获得哈弗曼编码

2、压缩过程：

1>建立一个新文件，将储存权值和字符的对象数组取存储在文件头

2>从头连续读取源文件中的每个字符，对于所读取的每一个字符到统计表中

查找相应的哈弗曼编码，每8位转换成一个ascii码，转换成字符存入新文件，不

足八位的连续读取下一个字符，即：字符->哈弗曼编码->8位的二进制->ASCII码

->字符，直到文件结束

3>统计文件大小，利用转变流指针的位置指向文件头和尾统计字符个数来统

计文件大小

3、解压过程：1>将存于文件头的权值和字符的对象数组取出

3>重新建立哈夫曼树

2>建立一个新文件，从源文件中读取一个字符->ASCII码->8位的二进制->

遍历树，遇到叶子节点则将节点中存的字符写入新文件，再读取下一个字符，直到

文件结束

（2）设计表示：

统计频率：建立哈夫曼树：

GetFrequencyGetTree

Judge(intc)HuffmanTree(charnode*ch,intn)

MakeTree(constT&elementInitialize(Ta,BinaryTree&left,BinaryTree&right)intsize,intArraySize)

获得哈弗曼编码：压缩过程：

CodingStoreIntoNew

GetIndex(char)GetIndex(char)EachStore(int,ofstream&)ChangeInto(inta)

解压过程：

Uncompress

Restore(BinaryTree//构造霍夫曼树public:

Compress;

voidGetFrequency;

boolJudge(intc);//推断是否c是否被读过

intGetIndex(charc);//猎取对应字符的索引

voidGetTree;//建立哈夫曼树

voidCoding;//获得哈弗曼编码

intChangeInto(inta);//将每位转化成一个int

voidEachStore(inta,ofstream

voidStoreIntoNew;//将对应ASCII码存入新文件

voidRestore(BinaryTree//遍历树直到叶节点时，解码，存入新文件

voidRechange(BinaryTree//将十进制转化为二进制,解码

voidUncompress;//解压

private:

char*filepath;//源文件路径

char*filepath2;//压缩后文件的路径

char*filepath3;//解压后文件路径

charnodech[257];

intcount;//调试后发觉为：字符的种数-1

BinaryTreebt;//建立的哈弗曼树

BinaryTreeNode*tnode;//解压时遍历树时需要的

voidcoding(BinaryTreeNode*t,Chain

intbit[8];//存八位以供转化为ASCII码

intbitcount;

inttotal;//编码总长度

intcurrentcount;//解压时纪录当前已解压的编码长度

};

字符类

classcharnode

{

public:

charnode{weigh=0;codelen=0;asciikey=0;}

charcharacter;//字符

intasciikey;//字符对应的ASCII码

intweigh;//权重

intcode[100];//存储哈弗曼编码

intcodelen;

};

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

if(!Judge((int)temp))//Judge推断该字符是否消失过

{

ch[count].asciikey=(int)temp;

ch[count].character=temp;

ch[count].weigh++;

count++;}

}

input.close;

}

获得哈弗曼编码

voidCompress::coding(BinaryTreeNode*t,Chain

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);

}

}

压缩过程

voidCompress::StoreIntoNew//将对应ASCII码存入新文件

{

ifstreaminput;

input.open(filepath);//读入的源文件

cout>filepath2;

ofstreamoutput;

output.open(filepath2,ios::binary|ios::out);

if(!output)//顺当打开否

{

cout>filepath2;

fstreaminput;

input.open(filepath2,ios::binary|ios::in);

if(!input)

{

cout>filepath3;

ofstreamoutput;

output.open(filepath3,ios::app);//ios::app—全部输出附加在文件末尾while(!output)

{

cout>filepath3;

}

BinaryTreebc;

input.read((char*)//读取哈夫曼树

StoredNodesnode[256];

input.read((char*)

inttempbc1,tempbc2;

tempbc1=bc.count;

tempbc2=bc.lackcount;

total=bc.total;

bc=HuffmanTree(snode,bc.count);//重新建树bc.count=tempbc1;

bc.lackcount=tempbc2;

tnode=bc.root;

chartemcha;

in