修改程序：问题1。源文件source文本空间太长汉字太多无法运行2，未按频度要求排序
问题描述：
信源编解码是通信系统的重要组成部分。本实验旨在通过程序设计实现基于哈夫曼编码的信源编解码算法。程序具备以下功能：
对于给定的源文档 SourceDoc.txt，
1) 统计其中所有字符的频度（某字符的频度等于其出现的总次数除以总字符数） ，
包括字母（区分大小写） 、标点符号及格式控制符（空格、回车等） 。
2) 按频度统计结果生成哈夫曼编码码表。
3) 基于哈夫曼码表进行编码，生成对应的二进制码流，并输出到文件 Encode.dat。
4) 对二进制码流进行哈夫曼解码，把结果输出到文件 DecodeDoc.txt。
5) 判断DecodeDoc.txt与SourceDoc.txt内容是否一致，以 验证编解码系统的正确性。
要求：
1) 用 C 语言实现。
2) 用子函数实现各功能模块。
3) 输出文件 Statistic.txt，包含的信息有：按频度大小排序的字符表，及各字符出现
的次数、频度及哈夫曼编码。
4) 应至少包含链表、二叉树的数据结构。
5) 不能用冒泡排序算法。
#include
#include
#include
#include
#include
#include
#include
#include
#define N 10000
int count = 0; //每增加一个新的字符, count增加1, 可表示a中的字符种类数, 也即哈夫曼树叶子点个数
/*定义哈夫曼树结构体*/
typedef struct HuffmanTree{
int weight;
int parent;
int Lchild;
int Rchild;
}HuffmanTree[2*N];
/*定义储存字符及其出现次数的结构体*/
typedef struct DifferentCharacter{
char char_date;
int num; //相同字符出现的次数
char a_code[100]; //每种字符对应的编码
}difcha[N];
/*在一定范围内选择两个weight最小的结点, 并将两个结点的序号赋给s1, s2*/
void select_two(HuffmanTree ht, int j, int *s1, int *s2) {
int i = 1, temp;
int min1 = 0, min2 = 0;
while( (ht[i].parent != 0) && (i <= j) )
i++;
*s1 = i;
min1 = ht[i++].weight;
while( (ht[i].parent != 0) && (i <= j) )
i++;
*s2 = i;
min2 = ht[i++].weight;
if(min1 > min2){
temp = min1;
min1 = min2;
min2 = temp;
}
for(; i <= j; i++){ //遍历parent不为0的结点
if(ht[i].parent != 0)
continue;
if(ht[i].weight <= min1){
min2 = min1;
min1 = ht[i].weight;
*s2 = *s1;
*s1 = i;
}
else if( (ht[i].weight < min2) && (ht[i].weight > min1) ) {
min2 = ht[i].weight;
*s2 = i;
}
}
}
/*建哈夫曼树*/
void EstHuffmanTree(HuffmanTree ht, int *w, int n){
int i;
int s1 = 0, s2 = 0;
for(i = 1; i <= n; i++){ //初始化哈夫曼树, 前n个单元存放叶子点
ht[i].weight = w[i];
ht[i].parent = 0;
ht[i].Lchild = 0;
ht[i].Rchild = 0;
}
for(i = n+1; i <= 2*n-1; i++){ //后n-1个单元存放非叶子点
ht[i].weight = 0;
ht[i].parent = 0;
ht[i].Lchild = 0;
ht[i].Rchild = 0;
}
for(i = n+1; i <= 2*n-1; i++){
select_two(ht, i-1, &s1, &s2); //创建非叶子点, 建立哈夫曼树, 每次在ht[1]~ht[i-1]范围内选两个最小的weight结点,并将其序号赋给s1, s2
ht[i].weight = ht[s1].weight + ht[s2].weight;
ht[i].Lchild = s1;
ht[i].Rchild = s2;
ht[s1].parent = i;
ht[s2].parent = i;
} //哈夫曼树建立完毕
}
/*求哈弗曼编码*/
void CrtHuffmanCode(HuffmanTree ht, char **hcd, int n){
int start = 0, c = 0, p = 0, i;
char cd = (char)malloc(n*sizeof(char)); //分配求当前编码的工作空间
cd[n-1] = '\0'; //从左向右存放编码
for(i = 1; i <= n; i++) {
start = n-1; //初始化编码起始指针
c = i;
p = ht[i].parent;
while(p != 0){
start--;
if(ht[p].Lchild == c)
cd[start] = '0'; //左分支标0
else
cd[start] = '1'; //右分支标1
c = p; //向上倒推
p = ht[c].parent;
}
hcd[i] = (char*)malloc((n-start)*sizeof(char));
strcpy(hcd[i], &cd[start]);
}
free(cd);
}
/*自定义错误处理函数*/
void my_err(char *err_string, int line){
printf("Line %d:\n", line);
perror(err_string);
exit(1);
}
/*从 buf_read 中统计每个字符出现的次数,将次数作为该字符的权值*/
void Statistics(difcha a, char *buf_read){
int i, j = 0;
for(i = 0; i < strlen(buf_read) ; i++){ //对buf_read中的字符遍历
for(j = 0; j < count; j++){ //检查是否是新的字符
if(a[j].char_date == buf_read[i]){
a[j].num++; //若是旧字符, 则num++;
break;
}
}
if(j == count){ //若是新字符, 则记录到a中, 且对应的num++
a[count].char_date = buf_read[i];
a[count].num++;
count++; //更新count
}
}
}
/*从 SourceDoc.txt 读取数据到 buf_read */
void ReadFile(char *pathName, char *buf_read){
int fd_date;
int len = 0;
if( (fd_date = open(pathName, O_RDWR)) < 0) //以读写方式打开SourceDoc.txt文件
my_err("open SourceDoc.txt", LINE);
if(lseek(fd_date, 0, SEEK_END) < 0) //获取文件长度,并保持文件读写指针在文件开始处
my_err("lseek", LINE);
if( (len = lseek(fd_date, 0, SEEK_CUR)) < 0 )
my_err("lseek", LINE);
if(lseek(fd_date, 0, SEEK_SET) < 0)
my_err("lseek", LINE);
if(read(fd_date, buf_read, len) > len) //从SourceDoc.txt中读取内容
my_err("read SourceDoc.txt", LINE);
}
/*将 buf_code 写入 Encode.dat 中*/
void WriteFile(char *pathName, char *buf_code){
int fd_code;
if((fd_code = open(pathName, O_CREAT|O_TRUNC|O_RDWR, S_IRWXU)) < 0) //创建Encode.dat文件
my_err("open Encode.dat", LINE);
if( write(fd_code, buf_code, strlen(buf_code)) != strlen(buf_code) ) //将 buf_code 写入Encode.dat
my_err("write Encode.dat", LINE);
}
/*主函数*/
void main(){
char buf_read[N] = {'\0'};
char buf_code[N] = {'\0'};
char buf_yima[N] = {'\0'};
char *hcd[N];
char temp[50] = {'\0'};
difcha a;
int i, j, n, k = 0, m = 0;
int w[N] = {0};
HuffmanTree ht;
ReadFile("SourceDoc.txt", buf_read);
Statistics(a, buf_read);
for(i = 0; i < count; i++)
w[i+1] = a[i].num;
EstHuffmanTree(ht, w, count); //建HuffmanTree
CrtHuffmanCode(ht, hcd, count); //对树中字符进行编码
for(i = 1; i <= count; i++) //将每个字符对应的编码存入结构体 a 中
strcpy(a[i-1].a_code, hcd[i]);
FILE *fp1;
fp1=fopen("Statistic.txt","w");
for(i = 0; i < count; i++) //查看每个字符的权值和对应的编码
fprintf(fp1,"%c %d %s\n", a[i].char_date, a[i].num, a[i].a_code);
fclose(fp1);
for(i = 0; i < strlen(buf_read) ; i++){ //遍历 buf_read, 给 SourceDoc.txt 中每个字符匹配编码, 存入 buf_code 中
for(j = 0; j < count; j++){
if(buf_read[i] == a[j].char_date){
strcat(buf_code, a[j].a_code);
break;
}
}
if(j == count) //匹配异常
printf("Unknown Character: %c\n", buf_read[i]);
}
WriteFile("Encode.dat", buf_code); //将 buf_code 写入 Encode.dat 中
ReadFile("Encode.dat", buf_read); //从 Encode.dat 中读取全部编码
n = strlen(buf_read);
for(i = 0; i < n; i++){ //为 Encode.dat 中的编码匹配字符
temp[k++] = buf_read[i];
for(j = 0; j < count; j++){
if(strcmp(temp, a[j].a_code) == 0){
buf_yima[m++] = a[j].char_date;
break;
}
}
if(j < count){ //匹配成功, 对 temp 初始化
for(;k > 0; k--)
temp[k] = '\0';
}
}
FILE *fp2;
fp2=fopen("DecodeDoc.txt","w");
fprintf(fp2,"%s", buf_yima);
fclose(fp2);
}
