那位可以看看这代码出了什么问题，整个人都要抓狂了
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <conio.h>
#include <limits.h>
// 构造 Huffman 树的数据
// 包含值域和权重
typedef struct _DATA_
{
unsigned char value; // 值域
int weight; // 权重
}Data;
// Huffman 树结点类型
// 值域、权重、父节点、左孩子、右孩子及 Huffman 编码
// 采用一维数组存储 Huffman 树
// parent, lchild, rchild 取值为结点在数组中的下标
// Huffman 编码采用动态数组
typedef struct _HUFFMANNODE_
{
unsigned char value; // 值域
int weight; // 权重
int parent, lchild, rchild; // parent , leftchild , rightchild
char* code; // Huffman 编码
}HuffmanNode, * HuffmanTree;
///////////////////////////////////
// 函数声明
void descendsort(HuffmanNode ht[], int n);
void InitHuffmanTree(HuffmanTree ht, Data data[], int dn);
int CreateHuffmanTree(HuffmanTree ht, int dn);
void CreateHuffmanCode(HuffmanTree ht, int leafnum);
int ScanFile(const char* filename, Data data[], int dn);
int CompressFile(const char* filename, const char* compfilename);
int DeCompress(const char* compfilename, const char* filename);
void Code(HuffmanTree ht, int leafnum, char str[]);
void DeCode(HuffmanTree ht, int leafnum, char code[]);
///////////////////////////////////
/*/////////////////////////////////
// 采用一维数组 ht 存储 Huffman 树
// 对数组 ht 中的前 n 个结点，按权重以 降序 排序
//
// ht： 存放 Huffman 树的一维数组
// 也可表示为 HuffmanTree ht
// void descendsort( HuffmanTree ht, int n )
*//////////////////////////////////
void descendsort(HuffmanNode ht[], int n)
{
int i, j;
HuffmanNode temp;
for (i = 0; i < n - 1; i++)
{
for (j = i + 1; j < n; )
{
if (ht[i].weight > ht[j].weight)
j++;
else
{
temp = ht[i];
ht[i] = ht[j];
ht[j] = temp;
j++;
}
}
}
}
/*/////////////////////////////////
// 利用数组 data 中的 dn 个数据
// 对存储在一维数组 ht 中的 Huffman 树进行初始化
// 根据 Huffman 树的性质
// 把前 dn 个结点作为叶子结点，用 data 中的数据对成员 value、weight进行赋值
// 成员 parent 赋值为 0，成员 lchild、rchild 赋值为 -1
//
// dn 个叶子结点的 Huffman 树，共有 2 * dn - 1 个结点
// 对于其它结点，成员 weight、parent赋值为 0
// 成员 lchild、rchild 赋值为 -1
*//////////////////////////////////
void InitHuffmanTree(HuffmanTree ht, Data data[], int dn)
{
int i;
for (i = 0; i < dn; i++)
{
ht[i].value = data[i].value;
ht[i].weight = data[i].weight;
ht[i].parent = 0;
ht[i].lchild = -1;
ht[i].rchild = -1;
}
for (; i < 2 * dn - 1; i++)
{
ht[i].weight = 0;
ht[i].parent = 0;
ht[i].lchild = -1;
ht[i].rchild = -1;
}
}
/*/////////////////////////////////
// 根据 ht 中的叶子结点，构造带权路径长度（WPL）最小的 Huffman 树
// ht ：存放 Huffman 树结点的数组，也可表示为 HuffmanNode ht[]
// int CreateHuffmanTree( HuffmanNode ht[], int dn )
// 叶子结点位于 ht[0] - ht[dn-1]
// 完成后，返回叶子结点的个数 leafnum
*//////////////////////////////////
int CreateHuffmanTree(HuffmanTree ht, int dn)
{
int leafnum = 0, nodenum; // 叶子结点数、全部结点数 nodenum = 2 * leafnum - 1
// 调用 descendsort 对前面的 dn 个叶子结点进行排序
descendsort(ht, dn);
// 按权重从大到小排序后
// 从前面的 dn 个叶子结点中，排除权重为０的结点
// 用 leafnum 记录新的叶子结点数 leafnum <= dn
for (int i = 0; i < dn; i++)
{
if (ht[i].weight == 0)
{
break;
}
leafnum++;
}
nodenum = 2 * leafnum - 1;
// 根据 ht 中的叶子结点，构造带权路径长度（WPL）最小的 Huffman 树
// 每次选择两个权重最小、且 parent 为 0 的结点
// INT_MAX 表示 int 类型的最大值
int i, min1, min2, x, y;
// 合并叶子结点
for (i = leafnum; i < nodenum; i++)
{
min1 = min2 = INT_MAX;
x = y = 0;
// 在所有 weight 不为 0 的节点中选出 2 个深度最小的
for (int j = 0; j < i; j++)
{
if (ht[j].weight == 0)
{
continue;
}
if (ht[j].parent == 0)
{
if (ht[j].weight < min1)
{
min2 = min1;
y = x;
min1 = ht[j].weight;
x = j;
}
else if (ht[j].weight < min2)
{
min2 = ht[j].weight;
y = j;
}
}
}
// 合并节点
ht[x].parent = i;
ht[y].parent = i;
ht[i].lchild = x;
ht[i].rchild = y;
ht[i].weight = min1 + min2;
}
/////////////////////////////////
// 以 leafnum 作为返回值
return leafnum;
}
/*/////////////////////////////////
// 对 Huffman 树中的叶子结点进行编码
// ht： 存放 Huffman 树结点的数组
// leafnum：叶子结点的个数，叶子结点位于 ht[0] - ht[leafnum-1]
// 从每个叶子结点出发，利用 parent 向上直到根结点
// 根结点的标志是其 parent 为 0
// 根据路径进行编码，左 0 右 1
// 编码长度不超过 leafnum
// 需要用 calloc 生成动态数组来保存编码
*//////////////////////////////////
void CreateHuffmanCode(HuffmanTree ht, int leafnum)
{
int index, len = leafnum;
char* code;
code = (char*)calloc(len, sizeof(char)); // 暂时存放一个 Huffman 编码，编码长度不超过 leafnum
for (int i = 0; i < leafnum; ++i) // 逐个处理叶子结点
{
index = len - 1;
// 由于是从叶子开始，编码按从后向前的顺序生成
// 例如：编码 "10100" 是按照 0 0 1 0 1 的顺序生成的
// code: [leafnum-1] [leafnum-2] [ ] [ ] [ ] [leafnum-6 ] …… [2] [1] [0]
// 空字符 '0' '0' '1' '0' '1'
// index 为此处的下标值 leafnum-6
// 最后根据码长创建动态数组 ht[i].code
// 用 strcpy 将 code 中的编码复制到 ht[i].code 中
// 此处添加代码
ht[i].code = (char*)calloc(len, sizeof(char));
int cur = i, p = ht[cur].parent;
while (p != 0)
{
if (ht[p].lchild == cur)
code[--index] = '0';
else
code[--index] = '1';
cur = p;
p = ht[p].parent;
}
strcpy_s(ht[i].code, len - index, &code[index]);
}
free(code);
}
/*/////////////////////////////////
// 根据 Huffman 树，对 str 中的字符串进行编码并显示
// ht ：存放 Huffman 树结点的数组，也可表示为 HuffmanNode ht[]
// leafnum：叶子结点的个数，叶子结点位于 ht[0] - ht[leafnum-1]
// 相应的 Huffman 码在 ht[i].code 中
// str；存放字符串的数组
*//////////////////////////////////
void Code(HuffmanTree ht, int leafnum, char str[])
{
for (int i = 0; 'a' <= str[i] && str[i] <= 'z'; i++)
{
for (int j = 0; j < leafnum; j++)
{
if (ht[j].value == str[i])
{
printf("%s", ht[j].code);
break;
}
}
}
printf("\n");
}
/*/////////////////////////////////
// 根据 Huffman 树进行译码，得到原先的字符串
// ht ：存放 Huffman 树结点的数组，也可表示为 HuffmanNode ht[]
// leafnum：叶子结点的个数，叶子结点位于 ht[0] - ht[leafnum-1]
// code；待译码的二进制串
*//////////////////////////////////
void DeCode(HuffmanTree ht, int leafnum, char code[])
{
int nodenum = 2 * leafnum - 1; // 总的结点数
int root = nodenum - 1; // Huffman 树根结点的下标
int cur = root;
// 从根结点开始，根据 code 中的编码左下或右下，直到叶子结点
// 用 cur 记录当前结点，到达叶结点的条件是 cur < leafnum
for (int i = 0; i < strlen(code); i++)
{
if (code[i] == '0')
cur = ht[cur].lchild;
else
cur = ht[cur].rchild;
if (cur < leafnum)
{
printf("%c", ht[cur].value);
if (code[i] == '0' || code[i] == '1')
{
cur = root;
continue;
}
else
break;
}
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*/////////////////////////////////
// 扫描文件，统计权重
//
// 利用 Huffman 树进行文件压缩时
// 将构成文件的二进制串
// 按照 8 位一组，分解为字节序列
//
// 以字节为单位读取文件 filename
// 将每个字节值出现的次数作为权重
// 记录在数组 data 中
// 由于一个字节的取值范围为 0 ~ 255 共 256 个值
// data[0].value = 0 data[0].weight 为 0000 0000 在文件中出现的次数
// data[1].value = 1 data[1].weight 为 0000 0001 在文件中出现的次数
// data[255].value = 255 data[255].weight 为 1111 1111 在文件中出现的次数
// 参数 dn 为数组 data 的长度
// 在调用函数时被传值为 256
//
*//////////////////////////////////
int ScanFile(const char* filename, Data data[], int dn)
{
FILE* fp;
fp = fopen(filename, "rb");
if (fp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
// 对 data[i].value 和 data[i].weight 赋初始值
for (int i = 0; i < 256; i++)
{
data[i].value = i;
data[i].weight = 0;
}
///////////////////////////////////
// 用 fread 从文件中每次读取一个字节
// 统计每个字节所取值的出现频率
// 同时记录文件的长度
int filelength = 0; // 文件长度，以字节为单位
unsigned char ch;
int m=fread(&ch, sizeof(unsigned char), 1, fp);
while(m==1)
{
data[ch].weight++;
filelength++;
m=fread(&ch, sizeof(unsigned char), 1, fp);
}
fclose(fp);
// 返回文件的长度，以字节为单位
return filelength;
}
/*/////////////////////////////////
// 利用 Huffman 树进行文件压缩时
// 将构成文件的二进制串
// 按照 8 位一组，分解为字节序列
// 由于一个字节的取值范围为 0 ~ 255 共 256 个值
// 将每个字节值出现的次数作为权重
// 记录在长度为 256 的数组 data 中
// filename： 原文件名
// compfilename： 压缩文件名
// 压缩成功，返回 1 压缩失败，返回 0
*//////////////////////////////////
int CompressFile(const char* filename, const char* compfilename)
{
int valuenum = 256;
int filelength; // 以字节为单位的文件长度
int leafnum; // 叶子结点数
Data* data; // 存放数据的值和权重
HuffmanTree ht;
///////////////////////////////////
// 不同于英文字母的权重，压缩文件时，需要通过扫描文件进行统计，得到权重数据
data = (Data*)calloc(valuenum, sizeof(Data)); // valuenum 为 256
// 扫描待压缩的文件,统计每个字节值的频率
// 同时统计文件长度，以字节为单位
filelength = ScanFile(filename, data, valuenum);
if (0 == filelength) return 0; // 扫描失败
ht = (HuffmanTree)calloc(2 * valuenum - 1, sizeof(HuffmanNode)); // 结点总数不会超过 2*valuenum-1
// 初始化顺序存储的 Huffman 树结点
InitHuffmanTree(ht, data, valuenum);
// 创建 Huffman 树
leafnum = CreateHuffmanTree(ht, valuenum); // leafnum <= valuenum 有些值可能在文件中未出现
//生成 Huffman 编码
CreateHuffmanCode(ht, leafnum);
// 测试代码，显示 Huffman 编码，完成后删除
for (int i = 0; i < leafnum; i++)
{
printf("[ %3d ] : %s\n", ht[i].value, ht[i].code);
if ((i + 1) % 32 == 0) _getch();
}//////////////////////////////////
///////////////////////////////////
// 生成压缩文件
int i;
FILE* fp, * cfp;
int compfilelength = 0; // 压缩后文件的长度
// 首先将叶子结点数、每个叶子结点的值和权重、文件原始长度依次写入压缩文件
///////////////////////////////////
cfp = fopen(compfilename, "wb"); // 新建二进制文件并写入
if (cfp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
fwrite(&leafnum, sizeof(int), 1, cfp); // 写入叶子结点数
// 此处补充代码，写入其它数据
for (i = 0; i < leafnum; i++)
{
fwrite(&ht[i].value, sizeof(char), 1, cfp);
fwrite(&ht[i].weight, sizeof(int), 1, cfp);
}
fwrite(&filelength, sizeof(int), 1, cfp);
// 开始对文件进行压缩，需要再次扫描原始文件
fp = fopen(filename, "rb");
if (fp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
///////////////////////////////////
unsigned char ch; // 每次写入一个字节
char* code;
code = (char*)calloc(2 * valuenum, sizeof(char)); // 存放 Huffman 编码
unsigned char buf = 0; // 缓存当前正在拼接的字节
int remain_bit = 8; // 跟踪当前字节缓存中剩余的未拼接位数
fread(&ch, sizeof(unsigned char), 1, fp); // 从原文件中读取第一个字节
while (!feof(fp))
{
// 根据 ch 的值找到对应的叶子结点
// 用叶子结点的 Huffman 编码，取代 ch 写入压缩文件中
// 难点在于，写入必须以字节为单位，而每个编码的长度并不是字节的整数倍
// 例如某个编码为 9 位，需要先把前 8 位作为一个字节写入
// 剩下的 1 位和后面的编码凑够一个字节后再次写入
// 还要注意，编码是字符串，"11110000"是8个字节
// 要变为二进制数 11110000 后才是一个字节
// 考虑学习使用位运算运算符 <<= 、 |= 和字符串函数 strcat、strcpy、strlen
for (int i = 0, j = 0; i < filelength; i++)
{
if (ch == ht[i].value)
{
j = (sizeof(ht[i].code)) / 8;//这里可能出错，j值是ht内有多少个数据
strcat(code, ht[i].code);
break;
}
while (strlen(code) >= 8)
{
unsigned char byte = (unsigned char)strtoul(code, NULL, 2);
code += 8; // 指向余下的编码
fwrite(&byte, sizeof(unsigned char), 1, fp);
compfilelength++; // 压缩文件长度加 1
remain_bit = 8; // 写入已经满了一个字节，将剩余位数重置为8位
}
// 缓存不足一个字节的部分编码，并记录剩余位数
remain_bit = remain_bit - strlen(ht[i].code);
buf <<= strlen(ht[i].code);
buf |= (unsigned char)strtoul(ht[i].code, NULL, 2);
}
// 如果最后剩余的编码不足一个字节，需要用 0 补足一个字节再写入
if (remain_bit == 0)
{
fwrite(&buf, sizeof(unsigned char), 1, fp);
remain_bit = 8;
buf = 0;
}
// 读取下一个字符
fread(&ch, sizeof(unsigned char), 1, fp);
// 处理剩余不足一个字节的编码部分
}
if (remain_bit != 8)
{
buf <<= remain_bit; // 缓存中可能存在不足8位的数据
fwrite(&buf, sizeof(unsigned char), 1, fp);
}
///////////////////////////////////
fclose(fp);
fclose(cfp);
free(data);
free(ht);
free(code);
// 用原始文件长度与压缩文件长度的比值作为压缩率
printf("\n Compression ratio : \t %.2f%% \n\n", ((double)(compfilelength) / filelength) * 100);
return 1;
}
/*/////////////////////////////////
// 解压文件
// filename：文件名
// compfilename：压缩文件名
// 解压成功返回 1， 失败返回 0
*//////////////////////////////////
int DeCompress(const char* compfilename, const char* filename)
{
FILE* fp, * cfp;
int leafnum, nodenum; // 叶子结点数、全部结点数 nodenum = 2 * leafnum - 1
///////////////////////////////////
cfp = fopen(compfilename, "rb");
if (cfp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
// 读取叶子结点数，这是压缩时写入的第一个数据
fread(&leafnum, sizeof(int), 1, cfp);
int i;
Data* data;
data = (Data*)calloc(leafnum, sizeof(Data)); // 存放 值 和 权重
///////////////////////////////////
// 从压缩文件中继续读取构成叶子结点的值域和权重到数组 data
for (int i = 0;i<leafnum-1; i++)
{
fread(&data[i].value,sizeof(unsigned char),1, cfp);
fread(&data[i].value, sizeof(int), 1, cfp);
}
// 还原压缩时使用的 Huffman 树
HuffmanTree ht;
nodenum = 2 * leafnum - 1;
ht = (HuffmanTree)calloc(nodenum, sizeof(HuffmanNode));
InitHuffmanTree(ht, data, leafnum);
CreateHuffmanTree(ht, leafnum);
///////////////////////////////////
int filelength; // 原文件的长度，以字节为单位
int root = nodenum - 1, cur; // 根结点 root 的位置
unsigned char ch;
int writenlength = 0; // 已解压出的字节数，和原文件的 filelength 相等时解压结束
fread(&filelength, sizeof(int), 1, cfp); // 读取原始文件的长度
fp = fopen(filename, "wb"); // 创建原始文件
if (fp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
cur = root; // 每次解码都是从 root 开始
while (1)
{
// 从压缩文件件中逐字节读取并解压
fread(&ch, sizeof(unsigned char), 1, cfp);
// 根据 ch 中的 8 个二进制位，向下搜索
// 如果到达了叶子结点，将叶子结点中的 value 写入原始文件中
// 同时将 writenlength 的值增 1
// 考虑学习使用位运算运算符 & 、 <<=
for (int i = 7; i >= 0; i--)
{
if ((1 << i) & ch)
{
if (ht[cur].rchild >= 0)
cur = ht[cur].rchild;
}
else
{
if (ht[cur].lchild >= 0)
cur = ht[cur].lchild;
}
if (ht[cur].lchild == -1 && ht[cur].rchild == -1)
{
fputc(ht[cur].value, fp);
cur = root;
writenlength++;
}
}
if (writenlength == filelength)
goto END;// 解压完成
}
END:
fclose(cfp);
fclose(fp);
free(data);
free(ht);
return 1;
}
int main()
{
char first;//判断用户选择的功能
char fileyq[10], fileyh[10], filejq[10], filejh[10];//压缩与解压缩的文件名
clock_t star,end;
while (1)
{
printf(" ____________________________________________________________\n");
printf(" | |\n");
printf(" | C - 压缩文件 |\n");
printf(" | D - 解压缩 |\n");
printf(" | Q - 退出 |\n");
printf(" |__________________________________________________________|\n\n\n");
loop:
printf(" 请选择功能：");
scanf_s("%c%c", &first);//这里第二个%C用来吃掉回车
if (first == 'C' || first == 'c')
{
printf(" 请您输入需要压缩的文件：");
scanf_s("%s", fileyq, (unsigned)_countof(fileyq));
printf("\n\n 请您输入压缩后的文件：");
scanf_s("%s", fileyh, (unsigned)_countof(fileyq));
printf("\n\n 正在帮您压缩...\n");
printf(" Compression ratio : ");
star = clock();
CompressFile(fileyq, fileyh);
end = clock();
printf("\n\n\n\n");
printf(" 压缩操作完成！\n\n");
printf(" 压缩耗费时间：%lf秒\n\n", (float)(end-star)/CLOCKS_PER_SEC);
}
else
{
if (first == 'D' || first == 'd')
{
printf(" 请您输入需要解压缩的文件：");
scanf_s("%s", filejq,(unsigned)_countof(fileyq));
printf("\n\n 请您输入解压缩后的文件：");
scanf_s("%s", filejh, (unsigned)_countof(fileyq));
printf("\n\n 正在帮您解压缩...\n\n");
star = clock();
DeCompress(filejq, filejh);
end = clock();
printf(" 解压缩操作完成！\n\n");
printf(" 解压缩耗费时间%lf秒\n\n", (float)(end - star) / CLOCKS_PER_SEC);
}
else
{
if (first == 'Q' || first == 'q')
{
printf(" 再见");
break;
}
else
{
printf(" 选项错误，请重新输入\n\n");
goto loop;
}
}
}
}
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <conio.h>
#include <limits.h>
// 构造 Huffman 树的数据
// 包含值域和权重
typedef struct _DATA_
{
unsigned char value; // 值域
int weight; // 权重
}Data;
// Huffman 树结点类型
// 值域、权重、父节点、左孩子、右孩子及 Huffman 编码
// 采用一维数组存储 Huffman 树
// parent, lchild, rchild 取值为结点在数组中的下标
// Huffman 编码采用动态数组
typedef struct _HUFFMANNODE_
{
unsigned char value; // 值域
int weight; // 权重
int parent, lchild, rchild; // parent , leftchild , rightchild
char* code; // Huffman 编码
}HuffmanNode, * HuffmanTree;
///////////////////////////////////
// 函数声明
void descendsort(HuffmanNode ht[], int n);
void InitHuffmanTree(HuffmanTree ht, Data data[], int dn);
int CreateHuffmanTree(HuffmanTree ht, int dn);
void CreateHuffmanCode(HuffmanTree ht, int leafnum);
int ScanFile(const char* filename, Data data[], int dn);
int CompressFile(const char* filename, const char* compfilename);
int DeCompress(const char* compfilename, const char* filename);
void Code(HuffmanTree ht, int leafnum, char str[]);
void DeCode(HuffmanTree ht, int leafnum, char code[]);
///////////////////////////////////
/*/////////////////////////////////
// 采用一维数组 ht 存储 Huffman 树
// 对数组 ht 中的前 n 个结点，按权重以 降序 排序
//
// ht： 存放 Huffman 树的一维数组
// 也可表示为 HuffmanTree ht
// void descendsort( HuffmanTree ht, int n )
*//////////////////////////////////
void descendsort(HuffmanNode ht[], int n)
{
int i, j;
HuffmanNode temp;
for (i = 0; i < n - 1; i++)
{
for (j = i + 1; j < n; )
{
if (ht[i].weight > ht[j].weight)
j++;
else
{
temp = ht[i];
ht[i] = ht[j];
ht[j] = temp;
j++;
}
}
}
}
/*/////////////////////////////////
// 利用数组 data 中的 dn 个数据
// 对存储在一维数组 ht 中的 Huffman 树进行初始化
// 根据 Huffman 树的性质
// 把前 dn 个结点作为叶子结点，用 data 中的数据对成员 value、weight进行赋值
// 成员 parent 赋值为 0，成员 lchild、rchild 赋值为 -1
//
// dn 个叶子结点的 Huffman 树，共有 2 * dn - 1 个结点
// 对于其它结点，成员 weight、parent赋值为 0
// 成员 lchild、rchild 赋值为 -1
*//////////////////////////////////
void InitHuffmanTree(HuffmanTree ht, Data data[], int dn)
{
int i;
for (i = 0; i < dn; i++)
{
ht[i].value = data[i].value;
ht[i].weight = data[i].weight;
ht[i].parent = 0;
ht[i].lchild = -1;
ht[i].rchild = -1;
}
for (; i < 2 * dn - 1; i++)
{
ht[i].weight = 0;
ht[i].parent = 0;
ht[i].lchild = -1;
ht[i].rchild = -1;
}
}
/*/////////////////////////////////
// 根据 ht 中的叶子结点，构造带权路径长度（WPL）最小的 Huffman 树
// ht ：存放 Huffman 树结点的数组，也可表示为 HuffmanNode ht[]
// int CreateHuffmanTree( HuffmanNode ht[], int dn )
// 叶子结点位于 ht[0] - ht[dn-1]
// 完成后，返回叶子结点的个数 leafnum
*//////////////////////////////////
int CreateHuffmanTree(HuffmanTree ht, int dn)
{
int leafnum = 0, nodenum; // 叶子结点数、全部结点数 nodenum = 2 * leafnum - 1
// 调用 descendsort 对前面的 dn 个叶子结点进行排序
descendsort(ht, dn);
// 按权重从大到小排序后
// 从前面的 dn 个叶子结点中，排除权重为０的结点
// 用 leafnum 记录新的叶子结点数 leafnum <= dn
for (int i = 0; i < dn; i++)
{
if (ht[i].weight == 0)
{
break;
}
leafnum++;
}
nodenum = 2 * leafnum - 1;
// 根据 ht 中的叶子结点，构造带权路径长度（WPL）最小的 Huffman 树
// 每次选择两个权重最小、且 parent 为 0 的结点
// INT_MAX 表示 int 类型的最大值
int i, min1, min2, x, y;
// 合并叶子结点
for (i = leafnum; i < nodenum; i++)
{
min1 = min2 = INT_MAX;
x = y = 0;
// 在所有 weight 不为 0 的节点中选出 2 个深度最小的
for (int j = 0; j < i; j++)
{
if (ht[j].weight == 0)
{
continue;
}
if (ht[j].parent == 0)
{
if (ht[j].weight < min1)
{
min2 = min1;
y = x;
min1 = ht[j].weight;
x = j;
}
else if (ht[j].weight < min2)
{
min2 = ht[j].weight;
y = j;
}
}
}
// 合并节点
ht[x].parent = i;
ht[y].parent = i;
ht[i].lchild = x;
ht[i].rchild = y;
ht[i].weight = min1 + min2;
}
/////////////////////////////////
// 以 leafnum 作为返回值
return leafnum;
}
/*/////////////////////////////////
// 对 Huffman 树中的叶子结点进行编码
// ht： 存放 Huffman 树结点的数组
// leafnum：叶子结点的个数，叶子结点位于 ht[0] - ht[leafnum-1]
// 从每个叶子结点出发，利用 parent 向上直到根结点
// 根结点的标志是其 parent 为 0
// 根据路径进行编码，左 0 右 1
// 编码长度不超过 leafnum
// 需要用 calloc 生成动态数组来保存编码
*//////////////////////////////////
void CreateHuffmanCode(HuffmanTree ht, int leafnum)
{
int index, len = leafnum;
char* code;
code = (char*)calloc(len, sizeof(char)); // 暂时存放一个 Huffman 编码，编码长度不超过 leafnum
for (int i = 0; i < leafnum; ++i) // 逐个处理叶子结点
{
index = len - 1;
// 由于是从叶子开始，编码按从后向前的顺序生成
// 例如：编码 "10100" 是按照 0 0 1 0 1 的顺序生成的
// code: [leafnum-1] [leafnum-2] [ ] [ ] [ ] [leafnum-6 ] …… [2] [1] [0]
// 空字符 '0' '0' '1' '0' '1'
// index 为此处的下标值 leafnum-6
// 最后根据码长创建动态数组 ht[i].code
// 用 strcpy 将 code 中的编码复制到 ht[i].code 中
// 此处添加代码
ht[i].code = (char*)calloc(len, sizeof(char));
int cur = i, p = ht[cur].parent;
while (p != 0)
{
if (ht[p].lchild == cur)
code[--index] = '0';
else
code[--index] = '1';
cur = p;
p = ht[p].parent;
}
strcpy_s(ht[i].code, len - index, &code[index]);
}
free(code);
}
/*/////////////////////////////////
// 根据 Huffman 树，对 str 中的字符串进行编码并显示
// ht ：存放 Huffman 树结点的数组，也可表示为 HuffmanNode ht[]
// leafnum：叶子结点的个数，叶子结点位于 ht[0] - ht[leafnum-1]
// 相应的 Huffman 码在 ht[i].code 中
// str；存放字符串的数组
*//////////////////////////////////
void Code(HuffmanTree ht, int leafnum, char str[])
{
for (int i = 0; 'a' <= str[i] && str[i] <= 'z'; i++)
{
for (int j = 0; j < leafnum; j++)
{
if (ht[j].value == str[i])
{
printf("%s", ht[j].code);
break;
}
}
}
printf("\n");
}
/*/////////////////////////////////
// 根据 Huffman 树进行译码，得到原先的字符串
// ht ：存放 Huffman 树结点的数组，也可表示为 HuffmanNode ht[]
// leafnum：叶子结点的个数，叶子结点位于 ht[0] - ht[leafnum-1]
// code；待译码的二进制串
*//////////////////////////////////
void DeCode(HuffmanTree ht, int leafnum, char code[])
{
int nodenum = 2 * leafnum - 1; // 总的结点数
int root = nodenum - 1; // Huffman 树根结点的下标
int cur = root;
// 从根结点开始，根据 code 中的编码左下或右下，直到叶子结点
// 用 cur 记录当前结点，到达叶结点的条件是 cur < leafnum
for (int i = 0; i < strlen(code); i++)
{
if (code[i] == '0')
cur = ht[cur].lchild;
else
cur = ht[cur].rchild;
if (cur < leafnum)
{
printf("%c", ht[cur].value);
if (code[i] == '0' || code[i] == '1')
{
cur = root;
continue;
}
else
break;
}
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*/////////////////////////////////
// 扫描文件，统计权重
//
// 利用 Huffman 树进行文件压缩时
// 将构成文件的二进制串
// 按照 8 位一组，分解为字节序列
//
// 以字节为单位读取文件 filename
// 将每个字节值出现的次数作为权重
// 记录在数组 data 中
// 由于一个字节的取值范围为 0 ~ 255 共 256 个值
// data[0].value = 0 data[0].weight 为 0000 0000 在文件中出现的次数
// data[1].value = 1 data[1].weight 为 0000 0001 在文件中出现的次数
// data[255].value = 255 data[255].weight 为 1111 1111 在文件中出现的次数
// 参数 dn 为数组 data 的长度
// 在调用函数时被传值为 256
//
*//////////////////////////////////
int ScanFile(const char* filename, Data data[], int dn)
{
FILE* fp;
fp = fopen(filename, "rb");
if (fp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
// 对 data[i].value 和 data[i].weight 赋初始值
for (int i = 0; i < 256; i++)
{
data[i].value = i;
data[i].weight = 0;
}
///////////////////////////////////
// 用 fread 从文件中每次读取一个字节
// 统计每个字节所取值的出现频率
// 同时记录文件的长度
int filelength = 0; // 文件长度，以字节为单位
unsigned char ch;
int m=fread(&ch, sizeof(unsigned char), 1, fp);
while(m==1)
{
data[ch].weight++;
filelength++;
m=fread(&ch, sizeof(unsigned char), 1, fp);
}
fclose(fp);
// 返回文件的长度，以字节为单位
return filelength;
}
/*/////////////////////////////////
// 利用 Huffman 树进行文件压缩时
// 将构成文件的二进制串
// 按照 8 位一组，分解为字节序列
// 由于一个字节的取值范围为 0 ~ 255 共 256 个值
// 将每个字节值出现的次数作为权重
// 记录在长度为 256 的数组 data 中
// filename： 原文件名
// compfilename： 压缩文件名
// 压缩成功，返回 1 压缩失败，返回 0
*//////////////////////////////////
int CompressFile(const char* filename, const char* compfilename)
{
int valuenum = 256;
int filelength; // 以字节为单位的文件长度
int leafnum; // 叶子结点数
Data* data; // 存放数据的值和权重
HuffmanTree ht;
///////////////////////////////////
// 不同于英文字母的权重，压缩文件时，需要通过扫描文件进行统计，得到权重数据
data = (Data*)calloc(valuenum, sizeof(Data)); // valuenum 为 256
// 扫描待压缩的文件,统计每个字节值的频率
// 同时统计文件长度，以字节为单位
filelength = ScanFile(filename, data, valuenum);
if (0 == filelength) return 0; // 扫描失败
ht = (HuffmanTree)calloc(2 * valuenum - 1, sizeof(HuffmanNode)); // 结点总数不会超过 2*valuenum-1
// 初始化顺序存储的 Huffman 树结点
InitHuffmanTree(ht, data, valuenum);
// 创建 Huffman 树
leafnum = CreateHuffmanTree(ht, valuenum); // leafnum <= valuenum 有些值可能在文件中未出现
//生成 Huffman 编码
CreateHuffmanCode(ht, leafnum);
// 测试代码，显示 Huffman 编码，完成后删除
for (int i = 0; i < leafnum; i++)
{
printf("[ %3d ] : %s\n", ht[i].value, ht[i].code);
if ((i + 1) % 32 == 0) _getch();
}//////////////////////////////////
///////////////////////////////////
// 生成压缩文件
int i;
FILE* fp, * cfp;
int compfilelength = 0; // 压缩后文件的长度
// 首先将叶子结点数、每个叶子结点的值和权重、文件原始长度依次写入压缩文件
///////////////////////////////////
cfp = fopen(compfilename, "wb"); // 新建二进制文件并写入
if (cfp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
fwrite(&leafnum, sizeof(int), 1, cfp); // 写入叶子结点数
// 此处补充代码，写入其它数据
for (i = 0; i < leafnum; i++)
{
fwrite(&ht[i].value, sizeof(char), 1, cfp);
fwrite(&ht[i].weight, sizeof(int), 1, cfp);
}
fwrite(&filelength, sizeof(int), 1, cfp);
// 开始对文件进行压缩，需要再次扫描原始文件
fp = fopen(filename, "rb");
if (fp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
///////////////////////////////////
unsigned char ch; // 每次写入一个字节
char* code;
code = (char*)calloc(2 * valuenum, sizeof(char)); // 存放 Huffman 编码
unsigned char buf = 0; // 缓存当前正在拼接的字节
int remain_bit = 8; // 跟踪当前字节缓存中剩余的未拼接位数
fread(&ch, sizeof(unsigned char), 1, fp); // 从原文件中读取第一个字节
while (!feof(fp))
{
// 根据 ch 的值找到对应的叶子结点
// 用叶子结点的 Huffman 编码，取代 ch 写入压缩文件中
// 难点在于，写入必须以字节为单位，而每个编码的长度并不是字节的整数倍
// 例如某个编码为 9 位，需要先把前 8 位作为一个字节写入
// 剩下的 1 位和后面的编码凑够一个字节后再次写入
// 还要注意，编码是字符串，"11110000"是8个字节
// 要变为二进制数 11110000 后才是一个字节
// 考虑学习使用位运算运算符 <<= 、 |= 和字符串函数 strcat、strcpy、strlen
for (int i = 0, j = 0; i < filelength; i++)
{
if (ch == ht[i].value)
{
j = (sizeof(ht[i].code)) / 8;//这里可能出错，j值是ht内有多少个数据
strcat(code, ht[i].code);
break;
}
while (strlen(code) >= 8)
{
unsigned char byte = (unsigned char)strtoul(code, NULL, 2);
code += 8; // 指向余下的编码
fwrite(&byte, sizeof(unsigned char), 1, fp);
compfilelength++; // 压缩文件长度加 1
remain_bit = 8; // 写入已经满了一个字节，将剩余位数重置为8位
}
// 缓存不足一个字节的部分编码，并记录剩余位数
remain_bit = remain_bit - strlen(ht[i].code);
buf <<= strlen(ht[i].code);
buf |= (unsigned char)strtoul(ht[i].code, NULL, 2);
}
// 如果最后剩余的编码不足一个字节，需要用 0 补足一个字节再写入
if (remain_bit == 0)
{
fwrite(&buf, sizeof(unsigned char), 1, fp);
remain_bit = 8;
buf = 0;
}
// 读取下一个字符
fread(&ch, sizeof(unsigned char), 1, fp);
// 处理剩余不足一个字节的编码部分
}
if (remain_bit != 8)
{
buf <<= remain_bit; // 缓存中可能存在不足8位的数据
fwrite(&buf, sizeof(unsigned char), 1, fp);
}
///////////////////////////////////
fclose(fp);
fclose(cfp);
free(data);
free(ht);
free(code);
// 用原始文件长度与压缩文件长度的比值作为压缩率
printf("\n Compression ratio : \t %.2f%% \n\n", ((double)(compfilelength) / filelength) * 100);
return 1;
}
/*/////////////////////////////////
// 解压文件
// filename：文件名
// compfilename：压缩文件名
// 解压成功返回 1， 失败返回 0
*//////////////////////////////////
int DeCompress(const char* compfilename, const char* filename)
{
FILE* fp, * cfp;
int leafnum, nodenum; // 叶子结点数、全部结点数 nodenum = 2 * leafnum - 1
///////////////////////////////////
cfp = fopen(compfilename, "rb");
if (cfp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
// 读取叶子结点数，这是压缩时写入的第一个数据
fread(&leafnum, sizeof(int), 1, cfp);
int i;
Data* data;
data = (Data*)calloc(leafnum, sizeof(Data)); // 存放 值 和 权重
///////////////////////////////////
// 从压缩文件中继续读取构成叶子结点的值域和权重到数组 data
for (i = 0;i<leafnum-1; i++)
{
fread(&data[i].value,sizeof(unsigned char),1, cfp);
fread(&data[i].value, sizeof(int), 1, cfp);
}
// 还原压缩时使用的 Huffman 树
HuffmanTree ht;
nodenum = 2 * leafnum - 1;
ht = (HuffmanTree)calloc(nodenum, sizeof(HuffmanNode));
InitHuffmanTree(ht, data, leafnum);
CreateHuffmanTree(ht, leafnum);
///////////////////////////////////
int filelength; // 原文件的长度，以字节为单位
int root = nodenum - 1, cur; // 根结点 root 的位置
unsigned char ch;
int writenlength = 0; // 已解压出的字节数，和原文件的 filelength 相等时解压结束
fread(&filelength, sizeof(int), 1, cfp); // 读取原始文件的长度
fp = fopen(filename, "wb"); // 创建原始文件
if (fp == NULL)
{
printf("\nERROR: No such file\n");
return 0;
}
cur = root; // 每次解码都是从 root 开始
while (1)
{
// 从压缩文件件中逐字节读取并解压
fread(&ch, sizeof(unsigned char), 1, cfp);
// 根据 ch 中的 8 个二进制位，向下搜索
// 如果到达了叶子结点，将叶子结点中的 value 写入原始文件中
// 同时将 writenlength 的值增 1
// 考虑学习使用位运算运算符 & 、 <<=
for (i = 7; i >= 0; i--)
{
if ((1 << i) & ch)
{
if (ht[cur].rchild >= 0)
cur = ht[cur].rchild;
}
else
{
if (ht[cur].lchild >= 0)
cur = ht[cur].lchild;
}
if (ht[cur].lchild == -1 && ht[cur].rchild == -1)
{
fputc(ht[cur].value, fp);
cur = root;
writenlength++;
}
}
if (writenlength == filelength)
goto END;// 解压完成
}
END:
fclose(cfp);
fclose(fp);
free(data);
free(ht);
return 1;
}
int main()
{
char first;//判断用户选择的功能
char fileyq[10], fileyh[10], filejq[10], filejh[10];//压缩与解压缩的文件名
clock_t star,end;
while (1)
{
printf(" ____________________________________________________________\n");
printf(" | |\n");
printf(" | C - 压缩文件 |\n");
printf(" | D - 解压缩 |\n");
printf(" | Q - 退出 |\n");
printf(" |__________________________________________________________|\n\n\n");
loop:
printf(" 请选择功能：");fflush(stdout);
rewind(stdin);scanf("%c", &first);
if (first == 'C' || first == 'c')
{
printf(" 请您输入需要压缩的文件：");
scanf_s("%s", fileyq, (unsigned)_countof(fileyq));
printf("\n\n 请您输入压缩后的文件：");
scanf_s("%s", fileyh, (unsigned)_countof(fileyq));
printf("\n\n 正在帮您压缩...\n");
printf(" Compression ratio : ");
star = clock();
CompressFile(fileyq, fileyh);
end = clock();
printf("\n\n\n\n");
printf(" 压缩操作完成！\n\n");
printf(" 压缩耗费时间：%lf秒\n\n", (float)(end-star)/CLOCKS_PER_SEC);
}
else
{
if (first == 'D' || first == 'd')
{
printf(" 请您输入需要解压缩的文件：");
scanf_s("%s", filejq,(unsigned)_countof(fileyq));
printf("\n\n 请您输入解压缩后的文件：");
scanf_s("%s", filejh, (unsigned)_countof(fileyq));
printf("\n\n 正在帮您解压缩...\n\n");
star = clock();
DeCompress(filejq, filejh);
end = clock();
printf(" 解压缩操作完成！\n\n");
printf(" 解压缩耗费时间%lf秒\n\n", (float)(end - star) / CLOCKS_PER_SEC);
}
else
{
if (first == 'Q' || first == 'q')
{
printf(" 再见");
break;
}
else
{
printf(" 选项错误，请重新输入\n\n");
goto loop;
}
}
}
}
return 0;
}
以下仅供参考：
#include <iostream>
#include <string>
using namespace std;
struct huffTree {
int parent;
int lchild;
int rchild;
int weight;
string flag;
};
struct Lowest_node {
char ch;
int ch_num;
};
void coding(int length,huffTree *tree,int n,int &a,int &b) {
int i;
int r,s;
r=s=length;
for (i=0;i<n;i++) {
if (tree[i].weight<r
&& tree[i].parent==-1) {
r=tree[i].weight;
a=i;
}
}
for (i=0;i<n;i++) {
if (tree[i].weight<s
&& i!=a
&& tree[i].parent==-1) {
s=tree[i].weight;
b=i;
}
}
}
void frequency(string str) {
int i,j;
int length=str.length();
Lowest_node *node=new Lowest_node[length];
for (i=0;i<length;i++) node[i].ch_num=0;
int char_type_num=0;
for (i=0;i<length;i++) {
for (j=0;j<char_type_num;j++)
if (str[i]==node[j].ch
|| ('a'<=node[j].ch && node[j].ch<='z'
&& str[i]+32==node[j].ch))
break;//
if (j<char_type_num) node[j].ch_num++;
else {
if ('A'<=str[i] && str[i] <= 'Z') node[j].ch=str[i]+32;
else node[j].ch=str[i];
node[j].ch_num++;
char_type_num++;
}
}
for (i=0;i<char_type_num;i++) {
for (j=i;j<char_type_num;j++) {
if (node[j].ch_num<node[j+1].ch_num) {
int temp;
char ch_temp;
temp=node[j].ch_num;
ch_temp=node[j].ch;
node[j].ch_num=node[j+1].ch_num;
node[j].ch=node[j+1].ch;
node[j+1].ch_num=temp;
node[j+1].ch=ch_temp;
}
}
}
for (i=0;i<char_type_num;i++)
cout<<"字符"<<node[i].ch<<"出现了"<<node[i].ch_num<<"次"<<endl;
huffTree *huff=new huffTree[2*char_type_num-1];
huffTree temp;
string *code=new string[2*char_type_num-1];
for (i=0;i<2*char_type_num-1;i++) {
huff[i].lchild=-1;
huff[i].parent=-1;
huff[i].rchild=-1;
huff[i].flag=-1;
}
for (j=0;j<char_type_num;j++) huff[j].weight=node[j].ch_num;
int min1,min2;
for (int k=char_type_num;k<2*char_type_num-1;k++) {
coding(length,huff,k,min1,min2);
huff[min1].parent=k;
huff[min2].parent=k;
huff[min1].flag="0";
huff[min2].flag="1";
huff[k].lchild=min1;
huff[k].rchild=min2;
huff[k].weight=huff[min1].weight+huff[min2].weight;
}
for (i=0;i<char_type_num;i++) {
temp=huff[i];
while (1) {
code[i]=temp.flag+code[i];
temp=huff[temp.parent];
if (temp.parent==-1) break;//
}
}
cout<<"字符串的每个字符huffman编码为："<<endl;
for (i=0;i<char_type_num;i++) cout<<node[i].ch<<" "<<code[i]<<endl;
cout<<"整个字符串的huffman编码为："<<endl;
for (i=0;i<length;i++) { //S?
for (j=0;j<char_type_num;j++) {
if (str[i]==node[j].ch)
cout<<code[j];
}
}
delete[] node;
node=NULL;
delete[] huff;
huff=NULL;
delete[] code;
code=NULL;
}
int main() {
int length=0;
string str;
cout<<"请输入一个字符串：";
cin>>str;
frequency(str);
return 0;
}
//请输入一个字符串：2333abcde
//字符3出现了3次
//字符2出现了1次
//字符a出现了1次
//字符b出现了1次
//字符c出现了1次
//字符d出现了1次
//字符e出现了1次
//字符串的每个字符huffman编码为：
//3 11
//2 000
//a 001
//b 010
//c 011
//d 100
//e 101
//整个字符串的huffman编码为：
//000111111001010011100101