[求助]我的赫夫曼程序有问题 - 数据结构与算法

问题点数：0 回复次数：1

[求助]我的赫夫曼程序有问题

《数据结构课程设计》指导书
一、课程设计目的
理解哈夫曼编码/解码的基本原理，主要理解哈夫曼编码的数据结构和算法的设计方法。通过实践，使学生加深对树这类非线性数据结构特性的理解，归纳学习方法和思考方法，并能将所学理论应用到实际问题中，提高学生分析问题、解决问题能力，使学生具备较强的软件设计能力和较严密的思维能力。
二、课程设计要求
1．使用C或C++语言编写程序，实现哈夫曼编码技术的全过程。
2．用C/C++语言实现算法，形成完整的C/C++程序，并上机调试。
3．记录调试过程及结果，并注意对调试程序集成环境的掌握及应用，不断积累编程及调试经验。
4．给出本实验单元的课程设计报告。
三、课程设计内容
1．课程设计题目：
哈夫曼编码和解码程序设计
2．设计内容：
利用哈夫曼树设计一个编码系统。要求在发送端通过一个编码系统对待传送数据进行编码；在接收端将传来的数据进行译码(复原)。试为这样的信息收发站写一个哈夫曼码的编译码系统。
—个完整的系统应具有以下功能：
(1)初始化。从终端读入字符集大小n，及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.txt中，同时将各字符及其哈夫曼编码值存于文件hc.txt中。
(2)编码。利用已建好的哈夫曼树(如不在内存，则从文件hfmtree中读入)，对文本文件BTree.txt中的正文进行编码，然后将结果存入文件codefile中。文件BTree.txt的内容如下：
SINCE THERE ARE TWO BINARY TREES WITH TWO NODES AND ONLY ONE EMPTY TREE,THE FIRST CASE GIVES TWO BINARY TREES.THE THIRD CASE,SIMILARLY,GIVES TWO MORE BINARY TREES.IN THE SECOND CASE THE LEFT AND RIGHT SUBTREES BOTH HAVE ONE NODE,AND THREE IS ONLY ONE BINARY TREE WITH ONE NODE,SO THERE IS ONE BINARY TREE IN THE SECOND CASE.ALTOGETHER,THEN,THERE ARE FIVE BINARY TREES WITH THREE NODES.
(3)译码。利用己建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile.txt中。
(4)打印代码文件。将文件codefile以紧凑格式（即8个二进制位组成1个字节）显示在终端上(以16进制形式)，每行25个字节。同时将此字节形式的编码文件写入文件codeprint中。
(5)计算文件BTree.txt的编码压缩比：即计算编码二进制位数÷原文字符的二进制位数。
【注】文件BTree.txt的字节数为385
3．有关知识和说明：
(1)哈夫曼树和字符的哈夫曼编码值的存储结构与教材相同。
(2)规定存储哈夫曼树的文件hfmtree.txt的结构形式是：第1行存储哈夫曼树的结点数，第2行开始，存储哈夫曼树的结点，每行1个结点（包括权值、父结点、左孩子、右孩子），形式如下：
59
174 56 0 0
64 51 0 0
13 38 0 0
……
(3) 规定文件hc.txt的结构形式是：第1行存储字符个数，第2行开始，存储字符及其哈夫曼编码值（后者为字符串），每行1个字符，字符与编码值之间用“-”隔开，形式如下：
30
-110
A-1010
B-001110
C-111110
……
(4)在存储紧凑格式编码文件codeprint时，若最后一个字节不满时，应将编码值在字节高位对齐，低位补“0”。
(5)有关模块的流程图如下
(6) 考虑到部分同学编程能力一般，提供了参考程序，源文件名为：课程设计_Huffman编码译码_2005.cpp。学生应仔细阅读本课程设计指导书，明白基本要求，同时仔细阅读参考源程序，在此基础上修改编码模块和译码模块。具体要求是：编码模块中，哈夫曼树应从文件hc.txt中读入；译码模块中，字符集及其编码值从文件hfmtree.txthc.txt中读入。修改后的程序运行结果应与参考源程序运行结果相同。
四、课程设计的具体步骤和进度安排
1．明确问题的要求及所要实现的功能。
2．分解成4个模块，分别实现上述4个功能，分别给出算法。
3．按功能编写4个函数及主函数，并上机调试。
4．用下表中给出的字符集和频度的实际统计数据建立哈夫曼树，并实现对文本文件BTree.txt的编码和译码。
字符空格 A B C D E F G H I J K L M N
频度 174 64 13 22 32 103 21 15 47 57 1 5 32 20 57
字符 O P Q R S T U V W X Y Z , . :
频度 63 15 1 48 51 80 23 8 18 1 16 1 2 9 1
5．通过对文本文件BTree.txt内容的编码、译码，以验证程序的可靠性，只有在textfile.txt的内容与文件BTree.txt内容相同时，才表明程序运行是正确的。还可自己选择若干组数据测试，或请其他同学帮助测试检查，以验证程序的可靠性。
6．从程序的运行结果，即从codefile文件的长度，分析、计算哈夫曼编码对文件BTree.txt的压缩比。

BTree.txt内容是
SINCE THERE ARE TWO BINARY TREES WITH TWO NODES AND ONLY ONE EMPTY TREE,THE FIRST CASE GIVES TWO BINARY TREES.THE THIRD CASE,SIMILARLY,GIVES TWO MORE BINARY TREES.IN THE SECOND CASE THE LEFT AND RIGHT SUBTREES BOTH HAVE ONE NODE,AND THREE IS ONLY ONE BINARY TREE WITH ONE NODE,SO THERE IS ONE BINARY TREE IN THE SECOND CASE.ALTOGETHER,THEN,THERE ARE FIVE BINARY TREES WITH THREE NODES.

需要修改的程序是：

// 课程设计_Huffman编码译码_2005.cpp

#include //printf(),FILE等
#include //strcpy()等
#include //exit()

// c6-7.h 赫夫曼树和赫夫曼编码的存储表示
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表

int min(HuffmanTree t,int i)
{ // 返回i个结点中权值最小的树的根结点序号，函数select()调用
int j,flag;
unsigned int k=20000; // 取k为不小于可能的值
for(j=1;j<=i;j++)
if(t[j].weight k=t[j].weight,flag=j;
t[flag].parent=1; // 给选中的根结点的双亲赋1，避免第2次查找该结点
return flag;
}
void select(HuffmanTree t,int i,int &s1,int &s2)
{ // 在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个
int j;
s1=min(t,i);
s2=min(t,i);
if(s1>s2)
{
j=s1;s1=s2;s2=j; //交换s1,s2,确保s1≤s2
}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ // w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
HT=new HTNode[m+1]; // 0号单元未用
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
(*p).parent=0;
for(i=n+1;i<=m;++i) // 建赫夫曼树
{ // 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
// 从叶子到根逆向求每个字符的赫夫曼编码
HC=new char*[n]; // 分配n个字符编码的头指针向量
cd=new char[n]; // 分配求编码的工作空间
cd[n-1]='\0'; // 编码结束符
for(i=1;i<=n;i++)
{ // 逐个字符求赫夫曼编码
start=n-1; // 编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
// 从叶子到根逆向求编码
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i-1]=new char[n-start];
// 为第i个字符编码分配空间
strcpy(HC[i-1],&cd[start]); // 从cd复制编码(串)到HC
}
delete []cd; // 释放工作空间
}

//初始化模块。从终端读入字符集大小n，及n个字符和n个权值，建立哈夫曼树，
//并将它存于文件hfmtree中，同时将各字符及其哈夫曼编码值存于文件hc.txt中。
void Init(HuffmanTree &HT,HuffmanCode &HC,char* &ch,int& n)
{ // 字符存放在ch[]中，字符对应的权值存放在w[]中，
// n为字符集大小，即字符个数
//为操作方便，本程序的n以及字符集及其权值皆通过赋值语句得到
int i,m;
int w[]={174,64,13,22,32,103,21,15,47,57,1,5,32,20,57,
63,15,1,48,51,80,23,8,18,1,16,1,2,9,1}; //权值
FILE *fp;
ch=" ABCDEFGHIJKLMNOPQRSTUVWXYZ,.:"; //字符集,第一个是空格字符
n=strlen(ch);
HuffmanCoding(HT,HC,w,n);
fp=fopen("hfmtree.txt","w"); //创建/打开文件hfmtree.txt
m=2*n-1;
fprintf(fp,"%d\n",m); //保存哈夫曼树的结点数
for (i=1;i<=m;i++) //保存哈夫曼树
fprintf(fp,"%-6u%-6u%-6u%-6u\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
fclose(fp); //关闭文件hfmtree.txt
fp=fopen("hc.txt","w"); //创建/打开文件hc.txt
fprintf(fp,"%d\n",n); //保存字符个数
for (i=0;i fprintf(fp,"%c-%s\n",ch[i],HC[i]);
fclose(fp); //关闭文件hc.txt
}

//编码模块。利用已建好的哈夫曼树(如不在内存，则从文件hfmtree.txt中读入)，
//对文本文件BTree.txt中的正文进行编码，然后将结果存入文件codefile.txt中。
void Code(HuffmanCode HC,char* ch,int n)
{
int j;
char c;
FILE *fp,*fp1;
if ((fp1=fopen("BTree.txt","r"))==NULL)//打开文件BTree.txt
{
printf("File BTree.txt not found\n");
exit(0);
}
fp=fopen("codefile","w"); //建立文件codefile
c=fgetc(fp1); //从文件BTree.txt中读入一字符到c
while(c!=EOF)
{
for (j=0;j if (c==ch[j]) break;
if (j==n) //字符集中没有该字符
{
printf("字符集中无字符%c\n",c);
exit(0); //中断程序的执行
}
fprintf(fp,"%s",HC[j]);//将该字符的哈夫曼编码写入文件codefile
c=fgetc(fp1); //从文件BTree.txt中读入一字符到c
}
fclose(fp); //关闭文件codefile
fclose(fp1); //关闭文件BTree.txt
}

//译码模块。
//利用己建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。
void Decode(HuffmanTree HT,char* ch,int n)
{
int m;
char c;
FILE *fp,*fp1;
if ((fp1=fopen("codefile","r"))==NULL)//打开文件codefile
{ //若文件codefile不存在，则报错，并中断程序的执行
printf("File(codefile) not found\n");
exit(0);
}
fp=fopen("textfile.txt","w"); //建立/打开文件textfile.txt
m=2*n-1; //m指向哈夫曼树的根结点
while (!feof(fp1))//未到文件尾部，则循环
{
c=fgetc(fp1); //从文件codefile读入一字符到c
if (c=='0')
m=HT[m].lchild;//c为'0'，则m指向左孩子
else
m=HT[m].rchild;//否m指向右孩子
if (HT[m].lchild==0 && HT[m].rchild==0)
{ //若当前m所指为叶子，则将该叶子对应的字符写到文件textfile.txt
fputc(ch[m-1],fp);
m=2*n-1; //m重新指向哈夫曼树的根结点，准备进行下一个译码
}
}
fclose(fp); //关闭文件textfile.txt
fclose(fp1); //关闭文件codefile
}

//打印代码文件模块。
//将文件codefile以紧凑格式显示在终端上，每行25个字节。
//同时将此字节形式的编码文件写入文件codeprint中。
void PrintCode()
{
unsigned char a=0,c,k=0,i=0;
FILE *fp,*fp1;
if ((fp1=fopen("codefile","r"))==NULL)//打开文件codefile
{ //若文件codefile不存在，则报错，并中断程序的执行
printf("File(codefile) not found\n");
exit(0);
}
fp=fopen("codeprint","wb"); //建立文件codeprint
c=fgetc(fp1); //从文件codefile读入一字符到c
while(!feof(fp1))//未到文件尾部，循环
{ //每8个字符('0'或'1')，合成一个字节存于a中
c=c-'0'; //将字符转换成数字
a=(a<<1)|c; //加到字节a
k++;
if (k==8)
{
k=0;
fputc(a,fp); //合成的字节写到文件codeprint中
printf("%02x",a);//同时以16进制形式在屏幕显示
a=0;
i++;
if (i==25)//每行显示25个字节
{
printf("\n");
i=0;
}
}
c=fgetc(fp1);//继续从文件codefile读入一字符到c
}
if (k) //若最后一个字节未凑满
{
for (;k<8;k++)
a=a<<1; //则在其尾部添0
fputc(a,fp); //添0后的字节写到文件codeprint
printf("%0x",a);//同时以16进制形式在屏幕显示
}
printf("\n");
fclose(fp); //关闭文件codeprint
fclose(fp1);//关闭文件codefile
}

void main()
{
HuffmanTree HT;
HuffmanCode HC;
int n;
char* ch;
Init(HT,HC,ch,n); //调用初始化模块
Code(HC,ch,n); //调用编码模块
Decode(HT,ch,n); //调用译码模块
PrintCode(); //调用打印代码文件模块
}

[此贴子已经被作者于2006-1-3 18:24:17编辑过]

搜索更多相关主题的帖子: 赫夫曼　