论文题目是动态哈弗曼编码在视频压缩中的应用
我搜到一些程序 不知道能用不 各位大神有没有有这个压缩 解压的程序的发给我救急一下吧
网上找了一段这样的编码 不知道能不能用 谁给看一下呢 谢谢了
#ifndef HUFFTREE_H
#define HUFFTREE_H
//由于SAList类要用到HuffTree类，此处即为虚定义
class HuffTree;
//有序表类的声明
class SAList {
int fence;
int maxSize;
int listSize;
public:
SAList(int size = 0);
~SAList();
HuffTree* *listArray;
void setStart();
void next();
int getLength();
bool insert(HuffTree* item); //排序插入
HuffTree* remove();
bool lessThan(HuffTree* x, HuffTree* y);
};
//哈弗曼树结点的类声明
class HuffTreeNode {
public:
unsigned char value;
unsigned long int weight;
unsigned int leftOrRight; //若为左儿子，则值为0，若为右儿子，则值为1
HuffTreeNode *parent;
HuffTreeNode *leftChild;
HuffTreeNode *rightChild;
bool isLeaf;
};
//哈夫曼树的声明
class HuffTree {
public:
HuffTreeNode* subRoot;
HuffTree();
HuffTree(unsigned char val, unsigned long int freq);
HuffTree(HuffTree* l, HuffTree* r);
HuffTree* buildHuffTree(SAList *sal, SAList *copy );
};
#endif
--------------------------------------------------------------------
HuffTree.cpp文件：
//哈夫曼树的实现
#include <iostream>
#include "HuffTree.h"
//有序表类的声明
SAList::SAList(int size) {
maxSize = size;
listSize = fence = 0;
listArray = new HuffTree*[maxSize];
}
SAList::~SAList(){
delete []listArray;
}
void SAList::setStart() {
fence = 0;
}
void SAList::next() {
if(fence <= listSize)
++fence;
}
int SAList::getLength() {
return listSize;
}
//排序插入
bool SAList::insert(HuffTree* item) {
if (listSize == maxSize)
return false;
HuffTree *current;
for (fence=0; fence<listSize; fence++) {
current = listArray[fence];
if(!lessThan(current, item))
break;
}
for (int i=listSize; i>fence; i--) {
listArray[i] = listArray[i-1];
}
listArray[fence] = item;
++listSize;
return true;
}
HuffTree* SAList::remove() {
if(listSize == fence) {
return NULL;
}
HuffTree *temp = listArray[fence];
for(int i=fence; i<listSize-1; ++i) {
listArray[i] = listArray[i+1];
}
--listSize;
return temp;
}
bool SAList::lessThan(HuffTree* x, HuffTree* y) {
return x->subRoot->weight < y->subRoot->weight;
}
//哈夫曼树的实现
HuffTree::HuffTree() {
subRoot = new HuffTreeNode;
subRoot->weight = 0;
}
HuffTree::HuffTree(unsigned char val, unsigned long int freq) {
subRoot = new HuffTreeNode;
subRoot->value = val;
subRoot->weight = freq;
subRoot->isLeaf = true;
}
HuffTree::HuffTree(HuffTree* l, HuffTree* r) {
subRoot = new HuffTreeNode;
subRoot->leftChild = l->subRoot;
subRoot->rightChild = r->subRoot;
subRoot->leftChild->parent = subRoot->rightChild->parent = subRoot;
subRoot->weight = l->subRoot->weight + r->subRoot->weight;
subRoot->isLeaf = false;
}
HuffTree* HuffTree::buildHuffTree(SAList *sal, SAList *copy) {
HuffTree *temp1, *temp2, *temp3;
temp1 = temp2 = temp3 = new HuffTree;
for(int i=sal->getLength(); i>1; i--) {
sal->setStart();
temp1 = sal->remove();
temp2 = sal->remove();
temp1->subRoot->leftOrRight = 0;
temp2->subRoot->leftOrRight = 1;
temp3 = new HuffTree(temp1, temp2);
if(temp1->subRoot->isLeaf)
copy->insert(temp1);
if(temp2->subRoot->isLeaf)
copy->insert(temp2);
sal->insert(temp3);
}
return temp3;
}
------------------------------------------------------------------
HuffmanCodeing.h文件：
/*
* 四川大学.软件学院
*
* 文件名称： HuffmanCodeing.h
* 摘 要： 利用哈夫曼树，对文件内容进行哈夫曼编码与译码
*
* 作 者： **
* 完成日期： 2008.11.21
*/
#ifndef HUFFMANCODING_H
#define HUFFMANCODING_H
#include <iostream>
#include "HuffTree.h"
using namespace std;
//栈结构
struct Link {
unsigned int element;
Link *next;
Link(const unsigned int &elemval, Link *nextval = NULL);
Link(Link *nextval = NULL );
};
struct LStack {
Link* top;
int size;
LStack() { size = 0; top = NULL; }
~LStack() { clear(); }
void clear();
bool push(const unsigned int &item);
bool pop(unsigned int &it);
};
//缓冲区
struct Buffer {
unsigned char byte; //表示字节，每个字节由8个位组成
unsigned int bits; //表示位（比特）
void clear(); //清空缓存区
};
//临时保存叶子结点的数域
struct Save {
unsigned char ch;
unsigned long int val;
};
class HuffmanCoding {
private:
SAList *list, *copy;//有序表
HuffTree* tree; //哈夫曼树
Buffer buffer; //缓存区
LStack *stack; //栈
Save save; //临时保存叶子结点的数域
FILE *sourceFile; //表示源文件
FILE *targetFile; //表示目标文件
unsigned long int total; //表示要进行编码的文件的总字节数（number < 4290000000）
unsigned long int ch[257]; //表示可以编码的所有字符，其下标表示对应的字符，对应下标的数组值表示该字符的权值
unsigned int numOfLeaf; //表示需要建立叶子结点的个数
public:
void code(); //对文件内容进行编码
void decode(); //对文件内容进行译码
void buildSAList(); //建立有序表,并将建立有序表的信息保存到目标文件
void write(unsigned int c); //利用建立的缓存，向目标文件中输出字符
void exportSAList(); //压缩文件中导出有序表
unsigned int read(); //利用建立的缓存，从压缩文件提取字符
};
#endif
---------------------------------------------------------------------
HuffmanCoding.cpp文件：
//哈夫曼编码、译码的实现
#include <fstream>
#include <iostream>
#include "HuffmanCoding.h"
using namespace std;
Link::Link(const unsigned int &elemval, Link *nextval) {
element = elemval;
next = nextval;
}
Link::Link( Link *nextval) {
next = nextval;
}
void LStack::clear() {
while(top != NULL){
Link *temp = top;
top = top->next;
delete temp;
}
size = 0;
}
bool LStack::push(const unsigned int &item) {
top = new Link(item, top);
size++;
return true;
}
bool LStack::pop(unsigned int &it) {
if(size == 0) return false;
it = top->element;
Link *temp = top;
top = top->next;
size--;
delete temp;
return true;
}
void Buffer::clear() {
bits = 0;
byte = 0;
}
void HuffmanCoding::code() {
char *sourceFileName = new char[];
char *targetFileName = new char[];
total = 0;
numOfLeaf = 0;
cout << "请输入源文件的文件名：（支持最大文件为4.29G）";
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->buildHuffTree(list, copy); //利用已建立的有序表，建立哈夫曼树
//开始编码，并将编码后的内容输出到目标文件
rewind(sourceFile); //将文件指针重新指向文件内容起始处
unsigned char tempChar = fgetc(sourceFile); //取文件内容的下一个字符
unsigned int tempInt;
HuffTreeNode *tempTreeNode;
stack = new LStack();
buffer.clear(); //清空缓存区
//当文件内容全部被扫描完，循环结束
while (!feof(sourceFile)) {
//搜索匹配tempChar的叶子的值
for (int i=0; i< copy->getLength(); i++) {
if (tempChar == copy->listArray[i]->subRoot->value) {
stack->clear();
tempTreeNode = copy->listArray[i]->subRoot;
while (tempTreeNode != tree->subRoot) {
stack->push(tempTreeNode->leftOrRight);
tempTreeNode = tempTreeNode->parent;
}//end while
while (stack->pop(tempInt)) {
write(tempInt);
}
break;
}//end if
}//end for
tempChar = fgetc(sourceFile);
}//end while
//如果缓存区还有剩余的位，则添加0到缓存区，直到够满8个位建立个字符，并向目标文件写入该字符
if (buffer.bits > 0) {
for (unsigned int i=buffer.bits; i<8; i++)
write(0);
}
cout << "文件压缩完毕" << endl;
delete stack;
delete list;
fclose(sourceFile); //关闭文件流
fclose(targetFile);
}
void HuffmanCoding::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->buildHuffTree(list, copy); //利用已建立的有序表，建立哈夫曼树
//译码开始
buffer.clear(); //清空缓存区
unsigned int tempInt;
HuffTreeNode *tempTreeNode;
while (total > 0) {
tempTreeNode = tree->subRoot;
while(!tempTreeNode->isLeaf) {
tempInt = read();
if(tempInt == 0) {
tempTreeNode = tempTreeNode->leftChild;
}
else {
tempTreeNode = tempTreeNode->rightChild;
}
}
fputc(tempTreeNode->value, targetFile);
total--;
}
cout << "文件解压完毕" << endl;
delete list;
fclose(sourceFile);
fclose(targetFile);
}
//按字符扫描源文件，统计源文件出现的字符及其权值
//利用统计出的字符和和其权值建立叶子结点有序表，并将统计出的信息保存到目标文件
void HuffmanCoding::buildSAList() {
unsigned char tempChar;
HuffTree *temp;
//初始化储存字符的数组
for (int i=0; i<257; i++)
ch[i] = 0;
rewind(sourceFile); //将文件指针重新指向文件内容起始处
tempChar = fgetc(sourceFile); //取文件内容的下一个字符
//当文件内容全部被扫描完，循环结束
while (!feof(sourceFile)) {
++ch[tempChar];
++total;
tempChar = fgetc(sourceFile);
}
//计算应该建立的叶子结点总数
for(int j=0; j<257; j++) {
if(ch[j] > 0)
numOfLeaf++;
}
//将源文件的字符总数及叶子结点总数保存到目标文件
fwrite(&total, sizeof(unsigned long int), 1, targetFile);
fwrite(&numOfLeaf, sizeof(unsigned int), 1, targetFile);
//建立叶子结点有序表
list = new SAList(numOfLeaf);
copy = new SAList(numOfLeaf);
//依次扫描ch，将权值不为0的字符插入到叶子结点有序表中
//并将此字符及其权值保存到目标文件
for(int k=0; k<257; k++) {
if(ch[k] > 0) {
temp = new HuffTree(k, ch[k]);
list->insert(temp);
save.ch = k;
save.val = ch[k];
fwrite(&save, sizeof(save), 1, targetFile);
}
}
}
//利用建立的缓存，向目标文件中输出字符
void HuffmanCoding::write(unsigned int c) {
++buffer.bits;
buffer.byte = (buffer.byte << 1) + c; //将byte左移一位，并在末位加上c
//如果byte的8个位都被写满，则向目标文件输出byte，并清空缓存区
if (buffer.bits == 8) {
fputc(buffer.byte, targetFile);
buffer.clear();
}
}
//从压缩文件中导出叶子结点有序表
void HuffmanCoding::exportSAList() {
HuffTree *temp;
fread(&total, sizeof(unsigned long int), 1, sourceFile);
fread(&numOfLeaf, sizeof(unsigned int), 1, sourceFile);
list = new SAList(numOfLeaf);
for(int i=0; i<numOfLeaf; i++) {
fread(&save, sizeof(save), 1, sourceFile);
temp = new HuffTree(save.ch, save.val);
list->insert(temp);
}
}
//从压缩文件中读取一个比特
unsigned int HuffmanCoding::read() {
if(buffer.bits == 0) {
buffer.bits = 8;
buffer.byte = fgetc(sourceFile);
}
if(buffer.byte & (1<<(buffer.bits-1))) {
buffer.bits--;
return 1;
}
else {
buffer.bits--;
return 0;
}
}
-------------------------------------------------------------------
Driver.cpp文件：
#include "HuffmanCoding.h"
int main() {
HuffmanCoding h;
h.code();
h.decode();
system("PAUSE");
return 0;
} |
|
楼主
标题置顶
标题高亮
