数据结构哈夫曼压缩文件

利用哈夫曼编码对数据进行无损压缩，实现Huffman压缩的编码器和译码器。 1．首先读入待压缩源文件。 2．然后建立并分析字母表，对每种字符的出现频度进行统计，以频度作为建立Huffman树的权值。 3. 频度表建好后，就可以根据算法建立Huffman树，对出现的每种字符进行Huffman编码。 4. 此时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件。 5. 译码过程先读入被压缩的文件，将其解释为比特流，根据Huffman树，对比特流逐位译码，将译码结果逐次写入到磁盘文件。

#include
#include   
#include   
#include   
////////////////////////////////////////////////  
/*************** 用于压缩的编码 ***************/  
char *t = “ !\“#$%&\‘（）*+-./0123456789:;\
<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_‘abc\
defghijklmnopqrstuvwxyz{|}~“;  
 
//#define DIGIT 6 // binary“111111“ == decimal“63“  
const DIGIT=6;
 
char IntToChar（int x）  
{   
    return t[x];  
}  
 
int CharToInt（char c）   
{  
    for （int i=0; i    {  
        if （c == t[i]） 
		{  
            return i;  
        }  
    }  
}  
/**********************************************/  
////////////////////////////////////////////////  
 
int main（）  
{  
    void Coding（）;  
    void Decode（）;  
    char s[10];  
     
	cout<	cout<     
	cin>>s;
    if （s[0] == ‘1‘） 
	{  
        Coding（）;  
    }  
    else if （s[0] == ‘2‘） 
	{  
        Decode（）;  
    }  
    else {  
		cout<    }  
    fclose（stdout）;  
     
    return 0;  
}  
 
const RANGE = 256;
 
//定义赫夫曼树节点  
typedef struct {  
    int w; // 权值  
    int p l r; // 双亲 左孩子 右孩子  
    char *cd; //对应编码  
} node;  
 
void Coding（）  
{  
    //如果只有一个节点编码会出错~  
	cout<    char s[100];  
	cin>>s;
    if （!freopen（s “r“ stdin））
	{  
		cout<<“你输入的文件\““<        return;  
    }  
     
    strcat（s “.zdker“）;  
	cout<<“已经成功压缩到:“<    freopen（s “w“ stdout）;  
     
    //统计  
    int i len = 2 * RANGE - 1;					//RANGE=256最大也就是256
    node *ht = （node *）malloc（sizeof（node） * len）;  
    node temp = { 0 0 0 0 NULL };  
    for （i=0; i	{						
        ht[i] = temp;  
    }  
    while （（i = getchar（）） != EOF）				//频度分析???
	{  
        ht[i].w++;  
    }  
     
    //建树  
    int Select（node * int int * int *）;  
    int s1 s2;  
    for （i=RANGE; Select（ht i - 1 &s1 &s2）; i++）			
	{  
        ht[s1].p = ht[s2].p = i;  
        ht[i].l = s1;  
        ht[i].r = s2;  
        ht[i].w = ht[s1].w + ht[s2].w;  
    }  
     
    //找出编码  
    char temps[RANGE];									//256
    int start now c;  
    temps[RANGE - 1] = 0;								//最后一个先放个0
    for （i=0; i	{  
        if （ht[i].w）									//是否有字符
		{   
            start = RANGE - 1;							//第二次还是从最后一个开始
            now = i;   
            while （c = ht[now].p）						//不是根结点
			{   
                if （ht[c].l == now） 
				{   
                    temps[--start] = ‘0‘;   
                }   
                else 
				{   
                    temps[--start] = ‘1‘;   
                }   
                now = c;   
            }   
            ht[i].cd = （char *）malloc（（RANGE - start） * sizeof（char））;//temps中有RANGE - start个已赋值后面开始
            strcpy（ht[i].cd &temps[start]）;   
      

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      26112  2007-09-13 01:42  哈夫曼问题\2.1  软件需求分析.doc

     文件      25088  2007-09-13 01:46  哈夫曼问题\2.2  概要设计.doc

     文件     147456  2007-09-13 01:45  哈夫曼问题\2.3  详细设计.doc

     文件      49152  2007-09-13 01:47  哈夫曼问题\2.4  测试分析及用户使用手册.doc

     文件       6532  2007-09-12 12:21  哈夫曼问题\哈夫曼压缩与解压 .cpp

     文件       3535  2007-09-13 22:16  哈夫曼问题\哈夫曼压缩与解压 .dsp

     文件        559  2007-09-13 22:16  哈夫曼问题\哈夫曼压缩与解压 .dsw

     文件      41984  2007-09-13 22:16  哈夫曼问题\哈夫曼压缩与解压 .ncb

     文件      48640  2007-09-13 22:16  哈夫曼问题\哈夫曼压缩与解压 .opt

     文件        268  2007-09-13 22:16  哈夫曼问题\哈夫曼压缩与解压 .plg

     文件      51200  2007-09-13 02:44  哈夫曼问题\附：源代码.doc

     目录          0  2009-06-26 18:18  哈夫曼问题

----------- ---------  ---------- -----  ----

               400526                    12