数据结构有关论文例文,与基于C语言的哈夫曼编码的实现相关硕士毕业论文

本论文是一篇数据结构有关专科毕业生毕业论文,关于基于C语言的哈夫曼编码的实现相关硕士论文范文。免费优秀的关于数据结构及参考文献及工程技术方面论文范文资料,适合数据结构论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。

摘 要 ：介绍了哈夫曼编码的思想,以及利用C语言实现哈夫曼编码的详细过程.

关 键 词 ：哈夫曼编码；权值；哈夫曼树；二叉树

中图分类号：TP312文献标识码：A文章编号：16727800（2012）009004003

0引言

数据通讯中,经常需要将传送的字符转换为由二进制字符0或1组成的二进制串,我们称此过程为编码.而哈夫曼树可以用来构造代码总长度最短的编码方案,将需要编码的字符作为叶节点,字符在电文中出现的频率作为权值,构造一颗二叉树,规定哈夫曼树的左分支为0,右分支为1,则从根节点到每个叶结点所经历的分支对应的0和1组成的数列变为该结点对应的字符编码.这种总长度最短的不等长编码就叫做哈夫曼编码.利用哈夫曼编码通信可以大大提高通信利用率,缩短通信传输时间,降低传输成本.

1问题描述

利用C语言编程实现哈夫曼编码.要求：用户输入各字母及使用频率（或频数）,用程序输出二进制表示的哈夫曼编码,并采用菜单和会话方式的界面.

2算法思想

（1）哈夫曼编码根据与n个权值{w1,w2,等wn}对应的n个结点构成n棵二叉树的森林,F等于 {T1,T2,等Tn},其中每棵二叉树Ti（1<=I<=n）都有一个权值为wi的根结点,其左右子树均为空.

（2）在森林F中选出两棵根结点权值最小的树作为一棵新树的左右子树,且置新树的附加根结点的权值为其左右树上根结点的权值之和.

（3）从F中删除这两棵树,同时把新树加入F中.

（4）重复（2）和（3）直到只含有一棵树为止,此时便是哈夫曼树.

（5）树从根到每个叶子都有一条路径,对路径上的各分支约定,指向左子树的分支表示 ‘0’ 码,指向右子树的分支表示 ‘1’ 码 .

（6）取每条路径上 ‘0’ 或 ‘1’ 的序列作为各个叶子对应的字符编码,这就是哈夫曼编码.

3逻辑设计

树的逻辑结构是层次结构,树中有且仅有一个没有前驱的结点ht[0]称为树的根,除根ht[0]以外的每个结点都有且只有一个前驱,对于不是根的每一个结点ht[I]都有一个线性序列ht[0],ht[1],等ht[I-1],ht[I] （I>等于0）,其中ht[I]是ht[I-1]的