哈夫曼编码译码器数据结构C语言

人生充满着期待，梦想连接着未来。 一、需求分析 目前

进行快速远距离通信的主要手段是电报

即将需传送的文字转化成由二级制的字符组成的字符串 例如

假设需传送的电文为\它只有4种字符 只需两个字符的串 便可以分辨

假设A、B、C、D、的编码分别为00 01

10和11

则上述7个字符的电文便为\总长14位 对方接受时

可按二位一分进行译码

当然 在传送电文时

希望总长尽可能地短

如果对每个字符设计长度不等的编码

且让电文中出现次数较多的字符采用尽可能短的编码 则传送电文的总长便可减少

如果设计A、B、C、D的编码分别为0 00 1 01

则上述7个字符的电文可转换成总长为9的字符串\但是

这样的电文无法翻译

例如传送过去的字符串中前4个字符的字串\就可以有很多种译法 或是\或者\或者\等 因此

若要设计长短不等的编码

则必须是任一字符的编码都不是另一个字符的编码的前缀 这种编码称作前缀编码

然而

如何进行前缀编码就是利用哈夫曼树来做 也就有了现在的哈夫曼编码和译码

二、概要设计

利用哈夫曼树编/译码 （一）、建立哈夫曼树 （二）、对哈夫曼树进行编码 （三）、输出对应字符的编码 （四）、译码过程

主要代码实现：

struct code //结构体的定义 {

char a; int w;

int parent; int lchild; int rchild; };

void creation(code *p int n

int m); //建立哈夫曼树 void coding(code *p int n); //编码 void display(code *p int n

int m); //输出函数 void translate(char **hc code *p

int n); //译码 三、 详细设计

（一） 、建立哈夫曼树

（二） 、对哈夫曼树进行编码 主要代码实现： for(c=i

f=p[i].parent;f!=0;c=f f=p[f].parent) {

if(p[f].lchild==c) {

//左孩子编码为'0'

cd[--start]='0'; }

else {

cd[--start]='1'; } }

（三） 、输出对应字符的码 字符 编码 a 110 b 111 c 10 d 0

（四） 、译码过程 主要代码实现： if(strcmp(a

hc[i])==0) //比较两个字符串是否相等 相等则输出0 {

for(c=2*n-1

j=0;a[j]!='\\0';j++) //从根出发 按字符'0'或'1'确定找左孩子或右孩子 {

if(a[j]=='0') //左孩子 {

c=p[c].lchild; } else {

c=p[c].rchild; //右孩子 } }

//右孩子编码为'1'

四、 调试分析 （一）、数字的输入判断

（二）、字母的输入判断

（三）、程序是否继续进行的 判断

五、 用户手册

（一） 、首先根据提示输入初始化数据 提示输入一个数字 请输入一个数a

0

则请输入一个字母（a~z)或者(A~Z)中的一个字符；请勿在输入一个数字后再输入一个字符 或者在输入一个字符后再输入一个数字

（二） 在某一界面结束后

会有\请按回车继续下面操作\提示 请按提示进行操作 如输入其他数字则无效

知道输入回车符界面才会跳转

（三） 对界面的操作可以自行选择 在询问是否译码的时候 请按要求进行选择

在一次译码结束后会询问是否继续译码 如需要则输入y或者Y 输入其他字符则退出程序

六、测试结果 （一）、初始化

（二）、建立哈夫曼树

（三）、哈夫曼编码

（四）、哈夫曼译码

（五）、错误判定

附录： 源代码：

#include #include #include #include

struct code //结构体的定义 {

char a; int w;

int parent; int lchild; int rchild; };

void creation(code *p int n

int m); //建立哈夫曼树 void coding(code *p

int n); //编码 void translate(char **hc code *p

int n);//译码

void display(code *p int n

int m); //输出函数 //主函数 void main() {

int i n m;

code *ht;

printf(\字符的数量:\\n(请输入一个大于0的数字 输入多个数字则按第一个数字运行)\\n\ while(scanf(\&n)!=1||n<0||n>9999) {

printf(\重新输入：\\n\ fflush(stdin); }

m=2*n-1; //哈夫曼树中没有度为1的结点 故含有m=2n-1个结点

ht=(code*)malloc((m+1)*sizeof(code));//动态申请内存

for(i=1;i<=n;i++) //对1~n的数进行初始化 {

printf(\输入编码中的字符(请输入一个字母):\\n\ fflush(stdin); scanf(\&ht[i].a);

while(!(ht[i].a>'a'||ht[i].a<'z'||ht[i].a>'A'||ht[i].a<'Z')) {

printf(\重新输入：\\n\ fflush(stdin); scanf(\&ht[i].a);//清空输入缓冲区 往往是确保不影响后面数据的读取 }

printf(\输入字符的权值(请输入一个数字):\\n\ while(scanf(\

&ht[i].w)!=1||ht[i].w<0||ht[i].w>9999) {

printf(\重新输入：\\n\

fflush(stdin); //清空输入缓冲区 往往是确保不影响后面数据的读取 }

ht[i].lchild=0; ht[i].rchild=0; ht[i].parent=0; }

for(i=n+1;i<=m;i++) //对n+1~2n-1的数进行初始化 { ht[i].a='*'; ht[i].w=0;

ht[i].lchild=0; ht[i].rchild=0; ht[i].parent=0; }

creation(ht n m);

printf(\请按回车进入哈夫曼树对应界面\\n\ getchar(); getchar(); system(\ display(ht n m);

printf(\请按回车进入编码对应界面\\n\ getchar(); system(\ coding(ht n);

getchar(); }

void creation(code *ht int n int m) {

int i j m1 m2 t1 t2;

for(i=n+1;i<=m;i++)

{

j=1; //找到第一个最小值（双亲不为0） while(ht[j].parent!=0) //找到表中第一个没有双亲的结点 {

j++; }

t1=ht[j].w; m1=j;

for(j=m1+1;j<=m;j++) {

if(ht[j].parent==0&&ht[j].w!=0)//条件(ht[j].w!=0)是因为n~2n-1的权值初始值为0 {

if(ht[j].w

t1=ht[j].w; m1=j; } } }

ht[m1].parent=i; //第一个值的双亲为ht[i]

ht[i].lchild=m1; //h[i]的的左孩子是最小值的序号

j=1; //剩余中找到第二个最小值（双亲不为0） while(ht[j].parent!=0) {

j++; }

t2=ht[j].w; m2=j;

for(j=m2+1;j<=m;j++) {

if(ht[j].parent==0&&ht[j].w!=0) {

if(ht[j].w

t2=ht[j].w; m2=j; } } }

ht[m2].parent=i; //第二个值的双亲为ht[i]

ht[i].rchild=m2; //h[i]的的左孩子是最小值的序号

ht[i].w=t1+t2; //h[i]的权值是找到的两个值的权值之和 }

}

void coding(code *p int n) {

int i c f;

char **hc; //指针的指针 char *cd; char ch; int start;

hc=(char**)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量 cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间 cd[n-1]='\\0'; //编码结束符 for(i=1;i<=n;i++) {

start=n-1; for(c=i

f=p[i].parent;f!=0;c=f

f=p[f].parent)//从叶子到根逆向求编码 {

if(p[f].lchild==c) //左孩子编码为'0' {

cd[--start]='0'; }

else //右孩子编码为'1' {

cd[--start]='1'; } }

hc[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间 strcpy(hc[i]

&cd[start]); //从cd复制编码（串）到hc &是取地址符 即取首地址

从start位置到'\\0'的编码为止

}

free(cd); //释放工作空间 printf(\输出编码后的结果：\\n\ printf(\符号 数码\\n\ for(i=1;i<=n;i++) {

printf(\ %s\\n\

p[i].a hc[i]); }

printf(\是否进行译码操作 是则译码

否则退出程序！\\n是（输入y/Y）否（输入其他字符）\\n\ scanf(\&ch);

if(ch=='y'||ch=='Y') {

translate(hc p n); } else

exit(0); }

void translate(char **hc code *p int n) {

char a[10] ch;

int i j c; do {

printf(\请输入编码：\\n\ scanf(\

a); //回车之后会自动生成'\\0' for(i=1;i<=n;i++) {

if(strcmp(a

hc[i])==0) //比较两个字符串是否相等 相等则输出0 {

for(c=2*n-1 j=0;a[j]!='\\0';j++) //从根出发 按字符'0'或'1'确定找左孩子或右孩子 {

if(a[j]=='0') //左孩子 {

c=p[c].lchild;

} else {

c=p[c].rchild; //右孩子 } }

printf(\字符是：\\n\ printf(\p[c].a);

break; } }

if(i>n) {

printf(\编码不存在对应的字符！\\n\ }

printf(\是否继续输入?是（输入y或者Y）否(其他）\\n\ fflush(stdin); scanf(\&ch);

}while(ch=='y'||ch=='Y'); }

void display(code *p int n int m) {

int i;

printf(\序号 码值 权值 双亲 左孩子 右孩子\\n\ for(i=1;i<=m;i++) {

printf(\%c %d %d %d %d\\n\i

p[i].a p[i].w

p[i].parent p[i].lchild p[i].rchild); } }

设计体会

通过这个课程设计

让我对数据结构这门课程有了更深一步的了解 对以后的深造奠定了基础

本次课程设计的课题是：哈夫曼编码以及译码的实现

本程序的特色是：结构清晰 内容全面

输入的错误提醒

在输入的错误的提醒方面 做了很大的改进

不过在这方面仍存在些许的不足 就是在输入一个字母的时候 如果输入的数据是\不会提示错误

只会按第一个'a'有效 在初始化的时候 输入'a3'这种数据 则不会提示错误

而是执行了下一条scanf语句输入的数字 学习是一个无止境的过境 我们要善于使用资源 书籍 网络等等

努力地提升自己

为今后的发展做更大的努力 ?? ?? ?? ?? 1

本文来源：https://www.bwwdw.com/article/7w4.html