第二章
每个C++程序都有一个main( )函数。函数是指能实现一个或多个功能的代码块。通常函数是由其他函数调用或激活,而main( )属于特殊情况,由操作系统直接调用。程序在开始时会自动调用main( )。和所有函数一样,main( )函数也必须标明其返回类型。
“\n”是格式专用符,它告诉cout另起一行。
endl表示end line,是end-ell 而不是end-one。通常它念作“end-ell”。
“\t”是格式化字符,它用来插入一个制表符。Eg:
cout<<"Here is a very big number:\t"<<70000<<endl;
cout<<"Here is the sum of 8 and 5:\t"<<8+5<<endl;
cout<<"Here's a fraction:\t\t"<<(float)5/8<<endl;使用了“\t”,其目的是使输出数据对齐。
注释不应用来说明发生了什么事情,而应说明为什么发生这种事情。
//Utility.h
#include<string.h> //标准串操作
#include<iostream> //标准输入输出操作
#include<limits.h> //数字限定
#include<math.h> //数学函数
#include<fstream> //文件输入输出
#include<ctype.h> //字符分类
#include<time.h> //时间函数
#include<conio.h> //输入输出
#include<stdlib.h> //标准库
#include<stdio.h> //标准输入输出库
enum Error_code{success,fail,underflow,overflow,range_error};//错误码
//enum bool{false,true};
//Lk_stack.h
template<class Node_entry>
struct Node {
// 数据成员
Node_entry entry;
Node<Node_entry> *next;
// 构造函数
Node();
Node(Node_entry item, Node<Node_entry> *add_on = NULL);
};
template<class Stack_entry>
class Stack {
public:
// 标准堆栈方法
Stack();
bool empty() const;
Error_code push(const Stack_entry &item);
Error_code pop();
Error_code top(Stack_entry &item) const;
void clear();
// 相关结构的安全功能
~Stack();
Stack(const Stack<Stack_entry> &original);
void operator =(const Stack<Stack_entry> &original);
protected:
Node<Stack_entry> *top_node;
};
template<class Node_entry>
Node<Node_entry>::Node()
{
next = NULL;
}
template<class Node_entry>
Node<Node_entry>::Node(Node_entry item, Node<Node_entry> *add_on)
{
entry = item;
next = add_on;
}
template<class Stack_entry>
Stack<Stack_entry>::Stack()
{
top_node=NULL;
}
template<class Stack_entry>
bool Stack<Stack_entry>::empty() const
{
if(top_node==NULL)
return true;
else
return false;
}
template<class Stack_entry>
Error_code Stack<Stack_entry>::push(const Stack_entry &item)
/*
Stack_entry 项添加到堆栈的顶部,如果动态内存用尽,则返回成功或返回溢出代码
*/
{
Node<Stack_entry> *new_top = new Node<Stack_entry>(item, top_node);
if (new_top == NULL) return overflow;
top_node = new_top;
return success;
}
template<class Stack_entry>
Error_code Stack<Stack_entry>::pop()
/*
栈的顶部移动。 如果栈为空则返回下溢;否则返回成功。
*/
{
Node<Stack_entry> *old_top = top_node;
if (top_node == NULL) return underflow;
top_node = old_top->next;
delete old_top;
return success;
}
template<class Stack_entry>
Error_code Stack<Stack_entry>::top(Stack_entry &item) const
{
if(empty())
return underflow;
else{
item=top_node->entry;
return success;
}
}
template<class Stack_entry>
void Stack<Stack_entry>::clear() // 清除元素
/*
栈清空
*/
{
while (!empty())
pop();
}
template<class Stack_entry>
Stack<Stack_entry>::~Stack() // 析构函数
/*
栈清空
*/
{
clear();
}
template<class Stack_entry>
Stack<Stack_entry>::Stack(const Stack<Stack_entry> &original) // 复制析构函数
/*
复制的析构函数初始化
*/
{
Node<Stack_entry> *new_copy, *original_node = original.top_node;
if (original_node == NULL) top_node = NULL;
else
{ // 复制相关点
top_node = new_copy = new Node<Stack_entry>(original_node->entry);
while (original_node->next != NULL)
{
original_node = original_node->next;
new_copy->next = new Node<Stack_entry>(original_node->entry);
new_copy = new_copy->next;
}
}
}
template<class Stack_entry>
void Stack<Stack_entry>::operator = (const Stack<Stack_entry> &original) // 超载分配
/*
复制栈重置
*/
{
Node<Stack_entry> *new_top, *new_copy, *original_node = original.top_node;
if (original_node == NULL) new_top = NULL;
else
{ // 复制相关点
new_copy = new_top = new Node<Stack_entry>(original_node->entry);
while (original_node->next != NULL)
{
original_node = original_node->next;
new_copy->next = new Node<Stack_entry>(original_node->entry);
new_copy = new_copy->next;
}
}
while (!empty()) // 清除原栈入口
pop();
top_node = new_top; // 用新的栈入口代替
}
//Huffman.h
const unsigned int n=256; //字符数
const unsigned int m=256*2-1; //结点总数
struct HTNode{ //压缩用Huffman树结点
unsigned long weight; //字符频度(权值)
unsigned int parent,lchild,rchild;
};
struct Buffer{ //字节缓冲压缩用Huffman树
char ch; //字节
unsigned int bits; //实际比特数
};
class HuffmanTree{ //Huffman树
public:
void Code(); //编码
void UnCode(); //译码
private:
HTNode HT[m+1]; //树结点表(HT[1]到HT[m])
char Leaf[n+1]; //叶结点对应字符(leaf[1]到leaf[n])
char *HuffmanCode[n+1]; //叶结点对应编码(*HuffmanCode[1]到*HuffmanCode[n])
unsigned int count; //频度大于零的字符数
unsigned int char_index[n]; //字符对应在树结点表的下标(char_index[0]到char_index[n-1])
unsigned long size; //被压缩文件长度
FILE *infp,*outfp; //输入/出文件
Buffer buf; //字符缓冲
void Stat(); //统计字符出现频度并过滤掉频度为零的字符
//在HT[0]~HT[k]中选择parent为-1,树值最小的两个结点s1,s2
void Select(unsigned int k, unsigned int &s1, unsigned int &s2);
void Write(unsigned int bit); //向outfp中写入一个比特
void Write(unsigned int num,unsigned int k);//向outfp中写入k个比特
void WriteToOutfp(); //强行写入outfp
void Read(unsigned int &bit); //从infp中读出一个比特
void Read(unsigned int &num,unsigned int k);//从infp中读出k个比特
int NToBits(unsigned int num); //0~num之间的整数用二进位表示所需的最少位数
void CreateFromCodeFile(); //由编码文件中存储的树结构建立Huffman树
//由被压缩文件建立Huffman树,将树结构存入编码文件的文件头部中,并求每个字符的Huffman编码
void CreateFromSourceFile();
};
void HuffmanTree::Code() //编码
{
char infName[256],outfName[256];
cout<<"Please input source file name(size less than 4GB):"; //被压缩文件最多GB
cin>>infName;
if((infp=fopen(infName,"rb"))==NULL){
cout<<"Can not open file:"<<infName<<endl;
exit(1);
}
if(feof(infp)!=0){
cout<<"Empty source file:"<<infName<<endl;
exit(1);
}
cout<<"Please input code file name:";
cin>>outfName;
if((outfp=fopen(outfName,"wb"))==NULL){
cout<<"Can not open file:"<<outfName<<endl;
exit(1);
}
cout<<"Pocessing..."<<endl;
unsigned char ch;
unsigned int i,c;
for(i=0;i<=n;i++)HuffmanCode[i]=NULL;
CreateFromSourceFile();
rewind(infp);
ch=fgetc(infp);
while(feof(infp)==0){
c=char_index[ch];
for(i=0;i<strlen(HuffmanCode[c]);i++){
if(HuffmanCode[c][i]=='0')Write(0);
else Write(1);
}
ch=fgetc(infp);
}
WriteToOutfp();
fclose(infp);fclose(outfp);
cout<<"Process end."<<endl<<endl;
}
void HuffmanTree::UnCode()
{
char infName[256],outfName[256];
cout<<"Please input code file name:";
cin>>infName;
if((infp=fopen(infName,"rb"))==NULL){
cout<<"Can not open file:"<<infName<<endl;
exit(1);
}
if(feof(infp)!=0){
cout<<"Empty code file:"<<infName<<endl;
exit(1);
}
cout<<"Please i
没有合适的资源?快使用搜索试试~ 我知道了~
Huffman编码(二叉树应用)
共27个文件
pdb:3个
h:3个
idb:2个
5星 · 超过95%的资源 需积分: 17 54 下载量 198 浏览量
2010-06-21
13:25:17
上传
评论 1
收藏 960KB RAR 举报
温馨提示
一、实验三:Huffman编码(二叉树应用) 二、实验的目的和要求: 1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法 2.………………………… 3.熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C++程序及二叉树上的基本运算; 4.上机调试程序,掌握查错、排错使程序能正确运行。
资源推荐
资源详情
资源评论
收起资源包目录
Huffman.rar (27个子文件)
Huffman
Huffman.vcproj.PC-201002252122.Administrator.user 1KB
Utility.h 491B
Huffman.dsw 539B
样本.txt 13KB
Huffman.cpp 395B
Lk_stack.h 4KB
Huffman.opt 49KB
Huffman.vcproj 5KB
Debug
Huffman.ilk 759KB
Huffman.exe.embed.manifest 2KB
vc60.pdb 100KB
Huffman.exe.embed.manifest.res 2KB
Huffman.pdb 1.05MB
Huffman.exe 528KB
vc60.idb 81KB
vc90.idb 179KB
BuildLog.htm 10KB
Huffman.obj 105KB
vc90.pdb 172KB
Huffman.pch 2.18MB
Huffman.h 8KB
Huffman.sln 879B
Huffman.plg 1KB
Huffman.suo 12KB
样本.rar 10KB
Huffman.ncb 41KB
Huffman.dsp 4KB
共 27 条
- 1
star_bright
- 粉丝: 2
- 资源: 21
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
前往页