哈弗曼编码正文

1、输出形式：按照计算机界面的相关提醒进行操作 2、输入形式：相关文件均保存到相应的磁盘文件中 3、程序所执行的命令 1.哈弗曼编码； 2、哈弗曼译码。

二：概要设计：

1. 抽象数据类型定义

typedef struct { char zifu; int weight; int parent,lchild,rchild;

}HFNode,*Huffmantree;//数组元素的类型

typedef char * *Huffmancode;//存放每个字符的哈弗曼编码

2. 主程序模块

1. 扫描字符求得权值 2. 进行哈弗曼编码 3. 对文件进行加密 4. 密文进行解密

三：详细设计：

#include

#define N 16000 //字符不超过N+1 #define M 2*N-1

typedef struct //huffman树的结点结构 {

char data; //字符 int weight; //权值

float weight0; //频度百分比

int plink,llink,rlink; // 双亲，左孩子，右孩子 }HTNode;

typedef struct //huffman编码结构 {

char cd[N]; //存放0，1的数组 int start; //起始位置 }HCode;

int COUNT0,COUNT; //COUNT为报文字符总个数，COUNT0为报文中出现的每种字符的个数统计

HTNode ht0[M+1],ht[M+1]; //huffman树，与COUNT0，COUNT对应 HCode hcd[N+1]; //huffman编码 void CreatHT() //创建huffman树并输出 {

int i,j,k,lnode,rnode; char c;

float min1,min2,countw,count;

for(i=1;i<=M;i++) //初始双亲，左，右结点及权值为：0 {

ht[i].plink=ht[i].llink=ht[i].rlink=ht[i].weight=ht[i].weight0=0; ht[i].data=' ';

ht0[i].plink=ht0[i].llink=ht0[i].rlink=ht0[i].weight=ht0[i].weight0=0; ht0[i].data=' '; }

printf(\"请输入报文（字母+标点+空格）,按#号结束\\n\\n\"); for(i=1;i<=N;i++) //利用for循环输入报文 {

c=getchar(); if(c!='#') {

ht[i].data=c; ht[i].weight=1; } else

{c=getchar(); i--; break; } }

COUNT=i; //记录报文总数

k=1; ht0[1]=ht[1];

for(i=2;i<=COUNT;i++) //统计每种字符的频度（出现次数），即权值 {

for(j=1;j<=k;j++)

if(ht[i].data==ht0[j].data) {

ht0[j].weight++; break; } if(j>k) {

k++;

ht0[k]=ht[i]; } }

COUNT0=k; //记录字符种类数

for(i=k+1;i<=2*k-1;i++) //找权值最小的2个结点开始建立huffman树 {

min1=min2=32767; lnode=rnode=0; for(j=1;jif(ht0[j].plink==0)

if(ht0[j].weight min2=min1; rnode=lnode;

min1=ht0[j].weight; lnode=j; }

else if(ht0[j].weight min2=ht0[j].weight; rnode=j; } ht0[lnode].plink=i; ht0[rnode].plink=i;

ht0[i].weight=ht0[lnode].weight+ht0[rnode].weight; ht0[i].llink=lnode; ht0[i].rlink=rnode; }

count=COUNT;

for(i=1;i<=k;i++) //输出huffman树 {

countw=ht0[i].weight;

ht0[i].weight0=(float)(countw/count); }

printf(\"\\n\\n-----------------------------------------------------------------\\n\\n\");

printf(\"\\n\\n 序号 结点值 权值(频度) 频度比例 双亲 左孩子 右孩子\\n\"); for(i=1;i<=2*k-1;i++)

printf(\" %-7d%-8c%-7d%-12f%-6d%-7d%d\\n\link,ht0[i].llink,ht0[i].rlink); }

void CreatCode() //建立huffman编码并输出，非报文 {

int i,j,f,c; HCode hc;

for(i=1;i<=COUNT0;i++) {

hc.start=COUNT0; c=i;

f=ht0[i].plink; while(f!=0) {

if(ht0[f].llink==c)

hc.cd[hc.start--]='0'; else

hc.cd[hc.start--]='1'; c=f;

f=ht0[f].plink; }

hc.start++; hcd[i]=hc; }

printf(\"\\n\\n\\n-----------------------------------------------------------------\\n\"); printf(\"\\n\\nhuffman编码为:\\n\"); for(i=1;i<=COUNT0;i++) {

printf(\"%c:\

for(j=hcd[i].start;j<=COUNT0;j++) printf(\"%c\ printf(\"\\n\"); } }

void code() //建立报文的编码 {

int i,j,k;

printf(\"\\n\\n\\n-----------------------------------------------------------------\\n\"); printf(\"\\n\\n报文编码为:(报文总数为：%d)\\n\

for(i=1;i<=COUNT;i++)

for(j=1;j<=COUNT0;j++)

if(ht[i].data==ht0[j].data) {

for(k=hcd[j].start;k<=COUNT0;k++) printf(\"%c\ printf(\" \"); } }

void main() //主函数 {

char k='y';

while(k=='y') //利用循环实现对多段报文的编码 {

CreatHT(); CreatCode(); code();

printf(\"\\n\\n\\n\\n******************************************************************\\n\");

printf(\"\\n------------ 继续(y/n) ------------\\n\\n\"); scanf(\"%c\

getchar();

printf(\"\\n******************************************************************\\n\\n\\n\\n\");

} }

四：用书使用说明：

1．程序使用说明

（1）本程序的运行环境为VC6.0。

（2）进入演示程序后即显示提示信息：除中文外，本程序可对所有键盘可见字 符编码。

五：结果测试：

六：参考文献:

1．李春葆 编著．《数据结构教程》．（清化大学出版社 2005） 2．蒋立翔 编著．《C++程序设计技能百练》．（中国铁道出版社 2004）