要求:1)从终端读入字符集大小为n,及n个字符和n个权值,建立哈夫曼树,进行编码并且输出,并将它存于文件hfmtree中。2)利用已建好的哈夫曼编码文件hfmtree,对存储于文件中的某正文进行编码。输出字符正文,再输出该文的二进制码。3)对2)的编码进行译码,译码结果存储到文件中,并与编码前的文件对比。程序编写C语言
时间: 2024-03-20 09:45:18 浏览: 26
好的,我已经了解你的要求了。下面是代码实现,我将分为三部分进行解释。
第一部分:建立哈夫曼树并进行编码
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000
typedef struct Node{
int weight;
int parent;
int lchild;
int rchild;
char c;
}HuffNode, *HuffTree;
typedef struct Code{
char ch;
char bits[MAX];
}HuffCode;
void CreateHuffTree(HuffTree HT, int n){
int i, j, k, min1, min2;
for(i = 1; i <= n; i++){
HT[i].weight = getchar() - '0';
HT[i].c = getchar();
getchar();
}
for(i = 1; i <= 2 * n - 1; i++){
HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
}
for(i = n + 1; i <= 2 * n - 1; i++){
min1 = min2 = MAX;
for(j = 1; j < i; j++){
if(!HT[j].parent){
if(HT[j].weight < min1){
min2 = min1;
min1 = HT[j].weight;
k = j;
}
else if(HT[j].weight < min2){
min2 = HT[j].weight;
}
}
}
HT[k].parent = i;
HT[i].lchild = k;
HT[i].weight = min1 + min2;
min1 = min2 = MAX;
for(j = 1; j < i; j++){
if(!HT[j].parent){
if(HT[j].weight < min1){
min2 = min1;
min1 = HT[j].weight;
k = j;
}
else if(HT[j].weight < min2){
min2 = HT[j].weight;
}
}
}
HT[k].parent = i;
HT[i].rchild = k;
HT[i].weight = min1 + min2;
}
}
void HuffCodeing(HuffTree HT, HuffCode HC[], int n){
int i, j, c, p;
char cd[MAX];
int start;
cd[n - 1] = '\0';
for(i = 1; i <= n; i++){
HC[i].ch = HT[i].c;
start = n - 1;
for(c = i, p = HT[i].parent; p != 0; c = p, p = HT[p].parent){
if(HT[p].lchild == c){
cd[--start] = '0';
}
else{
cd[--start] = '1';
}
}
strcpy(HC[i].bits, &cd[start]);
}
}
int main(){
int n;
scanf("%d", &n);
HuffTree HT = (HuffTree)malloc(sizeof(HuffNode) * (2 * n));
HuffCode HC[MAX];
CreateHuffTree(HT, n);
HuffCodeing(HT, HC, n);
FILE* fp = fopen("hfmtree", "w+");
for(int i = 1; i <= n; i++){
fprintf(fp, "%c %s\n", HC[i].ch, HC[i].bits);
}
fclose(fp);
free(HT);
return 0;
}
```
这部分主要实现了建立哈夫曼树及对其进行编码的功能。首先读入字符集大小n及n个字符和权值,然后根据这些权值建立哈夫曼树。接着,构建哈夫曼编码,将哈夫曼编码存入结构体中。最后将编码存储于文件hfmtree中。
第二部分:利用已建好的哈夫曼编码文件hfmtree,对存储于文件中的某正文进行编码
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000
typedef struct Code{
char ch;
char bits[MAX];
}HuffCode;
int main(){
FILE* fp = fopen("hfmtree", "r");
char ch;
int i = 0;
HuffCode HC[MAX];
while(fscanf(fp, "%c %s\n", &HC[i].ch, HC[i].bits) != EOF){
i++;
}
fclose(fp);
fp = fopen("text", "r");
char text[MAX];
fgets(text, MAX, fp);
fclose(fp);
fp = fopen("code", "w+");
int len = strlen(text);
for(int i = 0; i < len; i++){
for(int j = 0; j < strlen(HC[text[i] - 'a'].bits); j++){
fprintf(fp, "%c", HC[text[i] - 'a'].bits[j]);
}
}
fclose(fp);
return 0;
}
```
这部分主要实现了对文件进行哈夫曼编码的功能。首先读入文件hfmtree中的哈夫曼编码,然后读入需要编码的文件,接着对文件进行哈夫曼编码,将编码存入文件code中。
第三部分:对哈夫曼编码进行译码并与编码前的文件对比
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000
typedef struct Node{
int weight;
int parent;
int lchild;
int rchild;
char c;
}HuffNode, *HuffTree;
typedef struct Code{
char ch;
char bits[MAX];
}HuffCode;
int main(){
FILE* fp = fopen("hfmtree", "r");
char ch;
int i = 0;
HuffCode HC[MAX];
while(fscanf(fp, "%c %s\n", &HC[i].ch, HC[i].bits) != EOF){
i++;
}
fclose(fp);
fp = fopen("code", "r");
char code[MAX];
fgets(code, MAX, fp);
fclose(fp);
fp = fopen("decode", "w+");
int len = strlen(code);
char text[MAX];
int j = 0;
for(int i = 0; i < len; i++){
text[j] = code[i];
for(int k = 0; k < i; k++){
if(strcmp(HC[text[k] - 'a'].bits, "") == 0){
continue;
}
if(strncmp(&code[k], HC[text[k] - 'a'].bits, strlen(HC[text[k] - 'a'].bits)) == 0){
i = k + strlen(HC[text[k] - 'a'].bits) - 1;
j++;
text[j] = '\0';
fprintf(fp, "%c", HC[text[k] - 'a'].ch);
text[j] = '\0';
break;
}
}
}
fclose(fp);
fp = fopen("text", "r");
char old_text[MAX];
fgets(old_text, MAX, fp);
fclose(fp);
fp = fopen("decode", "r");
char new_text[MAX];
fgets(new_text, MAX, fp);
fclose(fp);
if(strcmp(old_text, new_text) == 0){
printf("Decode Succeed!\n");
}
else{
printf("Decode Failed!\n");
}
return 0;
}
```
这部分主要实现了对哈夫曼编码进行译码并与编码前的文件对比的功能。首先读入文件hfmtree中的哈夫曼编码和编码后的文件,然后对编码进行译码,将译码结果存储于文件decode中。接着,读入编码前的文件和编码后的文件,进行对比,判断译码是否成功。
以上就是对你要求的一个简单实现,希望能够帮助到你。