哈夫曼编译码器-实习报告.doc

实习报告

哈夫曼编译码器

班级：11052414

姓名：沈晓斌（11054417）
盛豪杰（11054418）

一． 需求分析
1.问题描述
用huffman编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。是为着这样的信息收发站写一个huffman编/译码系统。
2.基本要求
该系统应具有以下功能：
（1） I：初始化（Initialization）。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存进文件hfmTree中。
（2） E：编码（Encoding）。利用建好的哈夫曼树（如不在内存中，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3） D：译码(Decoding)。(利用已经建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4） P：印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
（5） T：印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式（凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrin中。
3.测试数据
（1）利用下面这道题中的数据调试程序。
某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROMGRAM IS MY FAVORITE”。

字符

A
B
C
D
E
F
G
H
I
J
K
L
M
频度
186
64
13
22
32
103
21
15
47
57
1
5
32
20
字符
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

频度
57
63
15
1
48
51
80
23
8
18
1
16
1

二.概要设计
typedef struct
{
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树

HTNode HT[30]; //全局变量HT，二维数组HC储存哈夫曼编码

int s1, s2; //定义全局变量
char HC[10000][10000];

void Select(int i) //从HT中选择权值最小的两个作为一个新的结点
void HuffmanCoding(int *w)//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC.
void OpenCode(char a[]) //对输入的字符进行编码
void OpenDecode(char a[])//对输入的编码进行译码
主函数
主函数主要设计的是一个分支语句，让用户挑选所实现的功能。
如图所示：
intHuffmanTree();初始化哈夫曼树
HuffmanCoding()构造哈夫曼树

编码调用Opencod()
译码调用Opendecode（）
Select（）供HuffmanCoding()调用

三.详细设计
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct
{
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树

HTNode HT[30]; //全局变量HT，二维数组HC储存哈夫曼编码
int s1, s2;
char HC[10000][10000];

void Select(int i) //从HT中选择权值最小的两个作为一个新的结点
{
int j;
for(j = 1; j <= i - 1; j++)//随便选择一个双亲不为的结点
{
if(HT[j].parent == 0)
{
s1 = j;
break;
}
}
for(j = s1 + 1; j <= i; j++) //找出第一个权值最小的结点
{
if(HT[j].parent == 0)
{
if(HT[s1].weight > HT[j].weight)
s1 = j;
}
}
HT[s1].parent = 1;
for(j = 1; j <= i; j++) //用相同的方法找出第二个权值最小的结点
{
if(HT[j].parent == 0)
{
s2 = j;
break;
}
}
for(j = s2 + 1; j <= i; j++)
{
if(HT[j].parent == 0)
{
if(HT[s2].weight > HT[j].weight)
s2 = j;
}
}
}

void HuffmanCoding(int *w)
{
//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC.
int i, j, c;
unsigned int t1, t;
char mer[100];
for(i = 1; i <= 27; i++)
{
HT[i].parent = 0;
HT[i].rchild = 0;
HT[i].rchild = 0;
HT[i].weight = w[i];
}
for(i=28;i<=53;++i) //建哈夫曼树
{//在HT[1..i-1]选择parent为且weight最小的两个结点，其序号为s1和s2．
Select(i-1);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
//－－－从叶子到根逆向求每个字符的哈夫曼编码－－－

for(i = 1; i <= 27; i++)
{
t1 = i;
j = 0;
memset(mer, 0, sizeof(mer)); //每次用完mer[]都清空
while(HT[t1].parent != 0)
{
t = HT[t1].parent;
if(HT[t].lchild == t1)
mer[j++] = '0';
if(HT[t].rchild == t1)
mer[j++] = '1';
t1 = t;
}
j--;
for(c = 0; j >= 0; j--, c++) //逆向输出mer[]存入HC中
HC[i][c] = mer[j];
}
}

void OpenCode(char a[]) //对输入的字符进行编码
{
int i;
FILE *fp3=fopen("d:\\CodeFile.txt","w");
for(i = 0; a[i] != '\0'; i++)
{
if(a[i] == ' ')
{
fprintf(fp3,"%s", HC[1]);
printf("%s", HC[1]);
}
else
{
fprintf(fp3,"%s", HC[a[i] - 'A' + 2]);
printf("%s", HC[a[i] - 'A' + 2]);
}
}
fprintf(fp3,"\n");
printf("\n");
fclose(fp3);
}

void OpenDecode(char a[]) //对输入的编码进行译码
{
FILE *fp4=fopen("d:\\TextFile.txt","w");
int i, j, m;
char b[100];
j = 0;
m = 53;
for(i = 0; a[i] != '\0'; i++)
{
if(a[i] == '1')
{
if(HT[m].rchild != 0) //循环知道找出没有孩子的结点，转化为个字母和空格
{
m = HT[m].rchild;
if(m >= 1 && m <= 27)
{
if(m == 1)
b[j++] = ' ';
else
b[j++] = 'A' + m - 2;
m = 53;
}
}
}

if(a[i] == '0')
{
if(HT[m].lchild != 0)
{
m = HT[m].lchild;
if(m >= 1 && m <= 27)
{
if(m == 1)
b[j++] = ' ';
else
b[j++] = 'A' + m - 2;
m = 53;
}
}
}
}
b[j] = '\0';
fprintf(fp4,"%s\n",b);
puts(b);
fclose(fp4);
}

int main()
{
int num, Fre[100], i;
char Character[100], word[100], word1[1000000], num1;
FILE *fp1=fopen("d:\\hfmTree.txt","w");
FILE *fp2=fopen("d:\\ToBeTran.txt","r");
printf("字符:");
for(num = 1; num <= 14; num++) //输入权值表
{
scanf("%c", &num1);
if(num1 != ' ')
Character[num] = num1;
else
num--;
}

printf("频度:");
for(num = 1; num <= 14; num++)
scanf("%d", &Fre[num]);
getchar();
printf("字符:");
for(num = 15; num <= 27; num++)
{
scanf("%c", &num1);
if(num1 != ' ')
Character[num] = num1;
else
num--;
}

printf("频度:");
for(num = 15; num <= 27; num++)
scanf("%d", &Fre[num]);

Character[28] = '\0';

HuffmanCoding(Fre);
printf("----------------------------------------------\n");
fprintf(fp1,"*: %s\n", HC[1]);
printf("*: %s\n", HC[1]);
for(i = 2; i <= 27; i++)
{
fprintf(fp1,"%c: %s\n", 'A' + i - 2, HC[i]);
printf("%c: %s\n", 'A' + i - 2, HC[i]);
}
fclose(fp1);
getchar();
getchar();
getchar();
fgets(word, 28, fp2);
printf("编码后的结果为：");
OpenCode(word);
FILE *fp3=fopen("d:\\CodeFile.txt","r");
fscanf(fp3,"%s",word1);
printf("译码后的结果为：");
OpenDecode(word1);
return 0;
}
四、调试分析：
在写程序与调试的过程中，发现自己对于函数的调用与参数的传递的方面还是存在很多问题，从参数的类型等等方面都出现了很多问题。
关于这个程序的要求比较复杂，刚开始做的时候没有任何思路，最后分模块一点一点的进行。
在调试过程中，出现了很多次明明建立了文件却发现未存入数据的情况，为此我多次进行调试，发现是打开文件的操作放在了循环体内部导致数据无法写入。
整体而言，整个程序主要使用了HuffmanCoding()的方式进行哈夫曼编码，在Openencod（）里面用了字符串的匹配进行译码，在Opendecode（）里进行了重新遍历树的过程，在算法的效率以及如何更为节省空间的存储数据上都要进一步改进。
五．测试数据
权值列表（*为空格）

各字符编码显示

需要编码的文件

编码结果

译码结果
并写入TextFile文件

六.附录
文件：
哈夫曼编.cpp
Code.file
hfmTree
ToBeTran
TextFile