压缩软件的实现

题目： 压缩软件的实现——利用哈夫曼树

东华理工大学数据结构课程设计报告

一． 需求分析

1. 通过利用哈夫曼树实现软件的压缩和解压将所学知识应用起来，有效的应用到解决实际问题中去，从而提高编程能力，达到学以致用。

2. 设计目标是实现哈弗满压缩的编码和译码器。为了读入文件与原文件信息完全一致，对文件读写采用二进制方式进行，对字符进行统计后，建立哈夫曼树，对字符进行哈弗曼编码，读入源文件，编码后将结果写到磁盘文件。

3. 程序最终要求能比较完善的对txt文件进行压缩和解压。

二． 总体设计

1. 设计要求：准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。

2. 建立哈夫曼树。根据哈弗曼编码技术，可以将已经给出的字母的使用频率建立一个哈夫曼树。

3. 编码：利用二叉树的遍历知识，左孩子用“0”表示，右孩子用“1”表示，将文字进行编码。 4. 测试和输出。

5. 译码。本程序要求对已编码的数字能够给以反编码。

东华理工大学数据结构课程设计报告

三． 详细设计

1. 构建哈夫曼树三个类：有序表类、哈夫曼树类、哈夫曼结点类 （1）有序表类：

class pList //有序表类的声明

{

int biaosize; int maxSize; int listSize;

public:

pList(int size = 0); hafumanshu* *listArray; void setStart();

int getLength();

bool insert(hafumanshu* item); //排序插入 hafumanshu* remove();

bool lessThan(hafumanshu* x, hafumanshu* y);

};

（2）哈夫曼树类：

class hafumanshu {

public:

hafumanshuNode *subRoot; hafumanshu();

hafumanshu(unsigned char val, unsigned long int freq); hafumanshu(hafumanshu* l, hafumanshu* r);

hafumanshu* buildhafumanshu(pList *sal, pList *copy );

};

（3）哈夫曼结点类：

class hafumanshuNode //哈弗曼树结点的类声明 {

public:

char value;

long int weight;

int lOrR; //若为左儿子，则值为0，若为右儿子，则值为1 hafumanshuNode *parent;

东华理工大学数据结构课程设计报告

hafumanshuNode *leftChild; hafumanshuNode *rightChild; bool isLeaf;

};

2.（核心）哈夫曼编码与解码类：

class hafumanshuCoding {

private:

pList *list, *copy;//有序表 hafumanshu* tree; //哈夫曼树 Buffer buffer;

Save save;

FILE *sourceFile; FILE *targetFile; int total; int ch[257];

int numOfLeaf; //叶子结点的个数 public:

void code(); void decode();

void buildSAList(); //建立有序表,并将建立有序表的信息保存到目标文件

void write(unsigned int c); //利用建立的缓存，向目标文件中输出字符 void exportSAList(); //压缩文件中导出有序表 unsigned int read(); };

3.结构体：

struct head {

unsigned char b; //记录字符 long count; //权重

int parent,lch,rch; //定义双亲，左孩子，右孩子 char bits[256]; //存放哈夫曼编码的数组 }

header[512],tmp;

struct Buffer //缓冲区 {

unsigned char byte; //表示字节，每个字节由8个位组成 unsigned int bits; //表示位（比特）

东华理工大学数据结构课程设计报告

void clear(); //清空缓存区

};

struct Save //临时保存叶子结点的数域 {

unsigned char ch;

unsigned long int val;

};

4.（核心）函数的实现

分析：调用哈夫曼树，建立有序表，将建立的信息保存到目标文件，利用建立的缓存向目标文件中输出字符，利用哈夫曼编码知识实现文件的压缩和解压

void hafumanshuCoding::code() {

char *sourceFileName = new char[]; char *targetFileName = new char[]; total = 0;

numOfLeaf = 0;

cout << \"请输入源文件的文件名：\"; cin >> sourceFileName;

sourceFile = fopen(sourceFileName, \"rb\"); while (sourceFile == NULL) {

cout << \"您输入的源文件不存在！\" << \"\\n请重新输入：\"; cin >> sourceFileName;

sourceFile = fopen(sourceFileName, \"rb\"); }

fgetc(sourceFile); if (feof(sourceFile)) {

cout << \"文件内容为空！\"; system(\"PAUSE\"); exit(-1); }

cout << \"请输入目标文件的文件名：\"; cin >> targetFileName;

targetFile = fopen(targetFileName, \"wb\"); while (targetFile == NULL) {

cout << \"目标文件无法建立！\" << \"\\n请重新输入：\";

东华理工大学数据结构课程设计报告

cin >> targetFileName;

targetFile = fopen(targetFileName, \"wb\"); }

cout << \"文件压缩中...\\n\\n\"; buildSAList();

tree = tree->buildhafumanshu(list, copy);

rewind(sourceFile); //将文件指针重新指向文件内容起始处

unsigned char tempChar = fgetc(sourceFile); //取文件内容的下一个字符

unsigned int tempInt;

hafumanshuNode *tempTreeNode; buffer.clear(); //清空缓存区 while (!feof(sourceFile))

{ //搜索匹配tempChar的叶子的值

for (int i=0; i< copy->getLength(); i++) {

if (tempChar == copy->listArray[i]->subRoot->value) {

tempTreeNode = copy->listArray[i]->subRoot; while (tempTreeNode != tree->subRoot) {

tempTreeNode = tempTreeNode->parent; }//end while

break; } }

tempChar = fgetc(sourceFile); }

if (buffer.bits > 0)

{ //如果缓存区还有剩余的位，则添加0到缓存区，直到够满8个位建立个字符，并向目标文件写入该字符

for (unsigned int i=buffer.bits; i<8; i++) write(0); }

cout << \"文件压缩完毕\" <delete list;

fclose(sourceFile); //关闭文件流 fclose(targetFile); }

东华理工大学数据结构课程设计报告

void hafumanshuCoding::decode() {

char *sourceFileName = new char[]; char *targetFileName = new char[]; total = 0;

numOfLeaf = 0;

cout << \"\\n请输入压缩文件的文件名：\"; cin >> sourceFileName;

sourceFile = fopen(sourceFileName, \"rb\"); while (sourceFile == NULL)

{ //判断源文件是否存在，不存在则要求用户重新输入

cout << \"您输入的压缩文件不存在！\" << \"\\n请重新输入：\"; cin >> sourceFileName;

sourceFile = fopen(sourceFileName, \"rb\"); }

fgetc(sourceFile); if (feof(sourceFile))

{ //判断文件内容是否为空，若为空则退出程序 cout << \"文件内容为空！\"; system(\"PAUSE\"); exit(-1); }

cout << \"请输入目标文件的文件名：\"; cin >> targetFileName;

targetFile = fopen(targetFileName, \"wb\"); while (targetFile == NULL) {

cout << \"目标文件无法建立！\" << \"\\n请重新输入：\"; cin >> targetFileName;

targetFile = fopen(targetFileName, \"wb\"); }

cout << \"文件解压中...\\n\\n\";

rewind(sourceFile); //将源文件指针重新指向文件起始处 exportSAList(); //导出叶子结点有序表

tree = tree->buildhafumanshu(list, copy); //利用已建立的有序表，建立哈夫曼树 ,译码开始

四、实现部分

核心代码实现：

void hafumanshuCoding::code() {

东华理工大学数据结构课程设计报告

char *sourceFileName = new char[]; char *targetFileName = new char[]; total = 0;

numOfLeaf = 0;

cout << \"请输入源文件的文件名：\"; cin >> sourceFileName;

sourceFile = fopen(sourceFileName, \"rb\"); while (sourceFile == NULL) {

cout << \"您输入的源文件不存在！\" << \"\\n请重新输入：\"; cin >> sourceFileName;

sourceFile = fopen(sourceFileName, \"rb\"); }

fgetc(sourceFile); if (feof(sourceFile)) {

cout << \"文件内容为空！\"; system(\"PAUSE\"); exit(-1); }

cout << \"请输入目标文件的文件名：\"; cin >> targetFileName;

targetFile = fopen(targetFileName, \"wb\"); while (targetFile == NULL) {

cout << \"目标文件无法建立！\" << \"\\n请重新输入：\"; cin >> targetFileName;

targetFile = fopen(targetFileName, \"wb\"); }

cout << \"文件压缩中...\\n\\n\"; buildSAList();

tree = tree->buildhafumanshu(list, copy);

rewind(sourceFile); //将文件指针重新指向文件内容起始处

unsigned char tempChar = fgetc(sourceFile); //取文件内容的下一个字符

unsigned int tempInt;

hafumanshuNode *tempTreeNode; buffer.clear(); //清空缓存区 while (!feof(sourceFile))

{ //搜索匹配tempChar的叶子的值

for (int i=0; i< copy->getLength(); i++) {

if (tempChar == copy->listArray[i]->subRoot->value) {

东华理工大学数据结构课程设计报告

tempTreeNode = copy->listArray[i]->subRoot; while (tempTreeNode != tree->subRoot) {

tempTreeNode = tempTreeNode->parent; }//end while

break; } }

tempChar = fgetc(sourceFile); }

if (buffer.bits > 0)

{ //如果缓存区还有剩余的位，则添加0到缓存区，直到够满8个位建立个字符，并向目标文件写入该字符

for (unsigned int i=buffer.bits; i<8; i++) write(0); }

cout << \"文件压缩完毕\" <delete list;

fclose(sourceFile); //关闭文件流 fclose(targetFile); }

void hafumanshuCoding::decode() {

char *sourceFileName = new char[]; char *targetFileName = new char[]; total = 0;

numOfLeaf = 0;

cout << \"\\n请输入压缩文件的文件名：\"; cin >> sourceFileName;

sourceFile = fopen(sourceFileName, \"rb\"); while (sourceFile == NULL)

{ //判断源文件是否存在，不存在则要求用户重新输入

cout << \"您输入的压缩文件不存在！\" << \"\\n请重新输入：\"; cin >> sourceFileName;

sourceFile = fopen(sourceFileName, \"rb\"); }

fgetc(sourceFile); if (feof(sourceFile))

{ //判断文件内容是否为空，若为空则退出程序

东华理工大学数据结构课程设计报告

cout << \"文件内容为空！\"; system(\"PAUSE\"); exit(-1); }

cout << \"请输入目标文件的文件名：\"; cin >> targetFileName;

targetFile = fopen(targetFileName, \"wb\"); while (targetFile == NULL) {

cout << \"目标文件无法建立！\" << \"\\n请重新输入：\"; cin >> targetFileName;

targetFile = fopen(targetFileName, \"wb\"); }

cout << \"文件解压中...\\n\\n\";

rewind(sourceFile); //将源文件指针重新指向文件起始处 exportSAList(); //导出叶子结点有序表

tree = tree->buildhafumanshu(list, copy); //利用已建立的有序表，建立哈夫曼树 ,译码开始 int main() {

int sel=1;

hafumanshuCoding h; while(sel) {

cout<<\" 哈夫曼树实现文件压缩 \"<cout<<\" 哈夫曼树实现文件压缩 \"<>sel; switch(sel) {

case 1:h.code();break; case 2:h.decode();break; case 3:help();break; case 0:break; } }

system(\"PAUSE\"); return 0; }

东华理工大学数据结构课程设计报告

五、程序测试 1、开始

2、文件压缩：

3、压缩文件：

东华理工大学数据结构课程设计报告

4、在起初的设计中，无法将字符解压，经过讨论实践以及借鉴书籍，在后期的改进中将所有字符转化为二进制后，解决了这个问题 六、总结

1、通过课程设计对数据结构c++版的有了更加深入的了解，进一步明确了各种算法的编程及应用

2、在实践中利用了哈夫曼数的另一种构建方法，即利用有序数表存储各节点，这是本次课程设计我最大的收获

3、在最后的设计中，解决了一直存在的一些问题，虽然没有做到十全十美，但已经尽了最大努力，完成了文件的压缩和解压

东华理工大学数据结构课程设计报告