Question

哈夫曼编码

2）树的应用（哈夫曼编/译码器）
（1）问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是。这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编译码系统。
（2）基本要求
一个完整的系统应具有以下功能：
（a） I：初始化（Initialization）。从终端读入字符集大小 n ，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。
（b） E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件 T oBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。
（c）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile 中的代码进行译码，结果存入文件 TextFile 中。
（d）P：印代码文件（Print）。将文件 CodeFile 以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。
（e）T：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint中。
高手帮忙下,我们要做课程设计,写出来的话就把剩下的160分全给,决不食言

Answer 1

/* algo6-1.c 求哈夫曼编码。实现算法6.12的程序 */
//------------------- 公用的常量和类型 ----------------------------
#include<stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define UINT_MAX 1000
typedef int Status;

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

typedef char **HuffmanCode; /* 动态分配数组存储哈夫曼编码表 */
typedef struct Node
{
char leaf;
unsigned int weight;
struct Node * next;
}LeafNode,*LeafLink;

typedef struct
{
LeafLink head;
unsigned len;
}LeafLinkList;

int min1(HuffmanTree t,int i)
{ /* 函数void select()调用 */
int j,flag;
unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* s1为最小的两个值中序号小的那个 */
int j;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1>*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, LeafLinkList L) /* 算法6.12 */
{ /* w存放n个字符的权值(权值均需大于0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC*/
int m,i,s1,s2,start;
int n=L.len;
unsigned c,f;
LeafLink ptr;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
printf("表长为%d\t哈夫曼树含节点数为%d\n",n,m);
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
ptr=L.head->next;
for(p=HT+1,i=1;i<=n;++i,++p,ptr=ptr->next)
{
(*p).leaf=ptr->leaf;
printf("%d\t",(*p).leaf);
(*p).weight=ptr->weight;
printf("%d\n",(*p).weight);
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
{
(*p).parent=0;
(*p).leaf=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=(HuffmanCode)malloc((n+1)*sizeof(char*));
/* 分配n个字符编码的头指针向量([0]不用) */
cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
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]=(char*)malloc((n-start)*sizeof(char));
/* 为第i个字符编码分配空间 */
strcpy(HC[i],&cd[start]); /* 从cd复制编码(串)到HC */
}
free(cd); /* 释放工作空间 */
for(i=1;i<=n;i++)
{
printf("%c编码为%s:\n",HT[i].leaf,HC[i]);
}
}

void InitLeafList(LeafLinkList &L)
{
L.head=(LeafLink)malloc(sizeof(LeafLink));
L.head->next=NULL;
L.len=0;
}
void PrintList(LeafLinkList L)
{
LeafLink p;
p=L.head->next;
printf("打印链表\n");
printf("表长为%d\n",L.len);
while(p!=NULL)
{
printf("%c or %d,%u\t",p->leaf,p->leaf,p->weight);
printf("打印一个节点\n");
p=p->next;
}
printf("打印结束\n");
printf("\n");
}

void EnLeafList(LeafLinkList &L,char ch)
{
LeafLink p,pre,temp;
int flag=0;
pre=p=L.head;
printf("%d即为%c******\n\n",ch,ch);
if(p->next==NULL) //p->next=NULL则为第一次插入操作
{
printf("第一次插入\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
p->next=temp;
L.len++;
}

else
{

p=p->next;
while(p!=NULL)
{

if(ch==p->leaf)
{
p->weight++;
printf("加权\n");
p=NULL;
flag=1;
} //权重加一
else if(ch<p->leaf) //插入
{
printf("插入A\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=p;
pre->next=temp;
L.len++;
flag=1;
p=NULL;
}
else //继续寻找插入点
{
pre=p;
p=p->next;
}
}

if(p==NULL&&flag!=1) //若p=NULL则插到链尾
{
printf("插入B\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
pre->next=temp;
L.len++;
}
}

}
void EnCoding()
{
FILE *fp,*fr,*fc;
HuffmanTree HT;
HuffmanCode HC;
int i,n;
LeafLinkList L;
InitLeafList(L);
char filename[15];
char ch;
printf("请输入文件名:\n ");
scanf("%s",filename);
if( !(fp=fopen(filename,"r")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("文件已经打开\n");
while(!feof(fp))
{

ch=fgetc(fp);
if(ch==-1)
{
printf("结束统计\n");
}
else
{
EnLeafList(L,ch);
}
}
PrintList(L);
HuffmanCoding(HT,HC, L);
n=L.len;
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
char TreeName[15];
printf("把哈夫曼树存入文件，请输入文件名:\n ");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"wb")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("文件已经打开\n");
//把哈夫曼树存入文件
printf("%d\n",n);
printf("把树的长度先存入\n");
putw(n,fr); //把树的长度先存入
for(i=1;i<=2*n-1;i++)
if(fwrite(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件写入出错\n");
fclose(fr);

printf("打印原来的树\n");
for(i=1;i<=2*n-1;i++)
printf("%c %u %u %u %u\n",HT[i].leaf ,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild );
fclose(fr);

printf("把编码结果存入文件，请输入文件名:\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"wb")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符

printf("待编码的文件位置指针重新指向开始位置\n");
printf("对待编码文件进行编码，编码同步显示，并将结果存入指定的文件\n");
rewind(fp);
while(!feof(fp))
{

ch=fgetc(fp);
printf("%c\n",ch);
if(ch==-1)
{
printf("结束编码\n");
}
else
{
for(int tap=0,i=1;tap==0&&i<=n;) //查找，该叶子对应的编码串
{
if(ch==HT[i].leaf) //找到，打印出对应的编码，并存入文件
{
printf("%s\n",HC[i]);
fputs(HC[i],fc); //将编码字符串存入文件

tap=1;
}
else
{
i++;
}
}
}
}
fclose(fp); //关闭文件
fclose(fc); //关闭文件
}
int decode(FILE *fc,HuffmanTree HT,int n)
{
while(!feof(fc))
{
char ch=fgetc(fc);
if(ch=='0')
{
n=HT[n].lchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else if(ch=='1')
{

n=HT[n].rchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else return OK;
}
return ERROR;
}

void Decoding() //解码文件，并将结果显示出来
{
FILE *fc,*fr;
char CodeFileName[15],ch,TreeName[15];
int i;
printf("解码文件，请输入文件名(如*.dat):\n ");
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("存放编码结果文件已经打开\n");

//读入哈夫曼树

HuffmanTree HT;
printf("取出对应的哈夫曼树文件，请输入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
int n=getw(fr); //将叶子数目取出
printf("叶子数目%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然后分配空间，0号单元未用 */

for(i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件读出出错\n");
int length=2*n-1; //总长度
printf("总结点数目为：%d\n",n);
printf("该文件译码后得到的源文件为：\n");
printf("**************************************\n");
while(!feof(fc))
{
decode(fc,HT,length);
}
printf("**************************************\n");
printf("\n\n");
}

int PreOrderPrint(HuffmanTree HT,int n,int count)
{
if(HT[n].lchild)
{
for(int i=0;i<count;i++)
printf(" ");
printf("%u\n",HT[n].weight);
if( PreOrderPrint(HT,HT[n].lchild, ++count) )
if (PreOrderPrint(HT,HT[n].rchild, ++count))
return OK;
return ERROR;
}
else return OK;
}
void PrintTree()
{
//读入哈夫曼树
FILE *fr;
char TreeName[15];
HuffmanTree HT;
printf("取出对应的哈夫曼树文件(如*.dat)，请输入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
int n=getw(fr); //将叶子数目取出
printf("含叶子数%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然后分配空间，0号单元未用 */

for(int i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件读出出错\n");
int count=0;
n=2*n-1;
printf("总结点数目为；%d\n",n);
printf("哈夫曼树的存储形式为：\n");
for(i=1;i<=n;i++)
{
printf("%c,%u,%u,%u,%u\n",HT[i].leaf,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
printf("哈夫曼树的凹入表形式为：\n");
PreOrderPrint(HT,n,count);
}
void PrintCodeFile()
{
FILE *fc;
printf("打印编码后的文件，请输入文件名(如*.dat):\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);

if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}

char ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("打印编码后的文件，打印方法一\n");
int flag=1;
while(!feof(fc))
{

ch=fgetc(fc);
if(ch==-1)
{
printf("结束打印\n");
}
else
{
printf("%c",ch);
if(flag<=49)
flag++;
else
{
flag=1;
printf("\n");
}
}
}
printf("打印编码后的文件，打印方法二\n");
rewind(fc);
char str[50];
while(!feof(fc))
{
fgets(str,51,fc);
puts(str);
}
fclose(fc); //关闭文件
}

void Initialization() //系统初始化
{
printf("**************************************\n");
printf("*编码文件请输入e\n*译码文件请输入d\n*打印编码后的文件请输入p\n*打印哈夫曼树请输入t\n*结束请输入q \n");
printf("**************************************\n");
printf("\n\n\t\t字符:\n\n\n");
printf("**************************************\n");
printf("* 输入一个字符:e,d,p,t or q *\n");
printf("**************************************\n");
}

int read(char cmd)
{
int i,flag=0;
char choice[10]={'e','E','d','D','p','P','T','t','Q','q'};
for(i=0;i<10;i++)
{
if(cmd==choice[i]) flag++;
}
if(flag==1) return FALSE;
else return TRUE;
}
void ReadCommand(char &cmd) // 读入操作命令符
{
do
{
cmd=getchar();
}
while(read(cmd));
}
void Interpret(char cmd) //解释执行操作命令
{
switch(cmd)
{
case 'e':case'E':
EnCoding();
Initialization();
break;
case 'd':case'D':
Decoding();
Initialization();
break;
case 'p':case'P':
PrintCodeFile();
Initialization();
break;
case't':case'T':
PrintTree(); // Print();
Initialization();
break;
case 'q': case'Q': exit(0);
break;
default: printf("Error\n");break;
}
}
void main() //用户驱式
{
char cmd;
Initialization(); //初始化
do
{
ReadCommand(cmd); //读入一个操作命令符
Interpret(cmd); //解释执行操作命令符
}
while(cmd!='q'&&cmd!='Q');
EnCoding();
Decoding();

}

Answer 2