计算机软件基础
课 程 设 计
报告
设计题目：    哈夫曼编\译码器       
专    业  信息工程(系统工程方向)
班    级  09系统1班         
学    生  董健                 
学    号  ***********         
指导教师   陈金辉               
     
一、设计题目
设计题目一 哈夫曼编\译码器
设计要求：
1.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。
2.编码，利用建好的huffman树生成huffman编码；
3.输出编码；
4.译码功能；
5.字符和频度如下：
字符 空格 A B C D E F G H I J K L M N O P Q
频度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1
字符 R S T U V W X Y Z
频度 48 51 80 23 8 18 1 16
1.1 问题分析
构造哈夫曼树时，首先将由n各字符形成的n个叶子节点存放到数组HTNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树，每次构成的新子树的根节点顺序放到HTNode数组中的前n个分量的后面。译码功能，假定电文中只使用A、B、C、D、E、F6种字符，若进行等长编码，它们分别需要3位二进制字符，可一次编码为000、001、010、011、100、101。
1.2 数据结构与算法设计
哈夫曼编\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。
在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。
最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。
哈夫曼树编\译码器流程图
1.3 核心代码
哈夫曼编\译码器程序的主要代码如下所示:
#include <stdio.h>
#include <stdlib.h>          //要用system函数要调用的头文件
#include<conio.h>            //用getch()要调用的头文件
#include <string.h>
#define N 50                //义用N表示50叶节点数
#define M 2*N-1              //用M表示节点总数  当叶节点数位n时总节点数为2n-1
#define MAXSIZE 100
typedef struct
{
    char data;                  //结点值
    int weight;                //权值
    int parent;                //双亲结点
    int lchild;                //左孩子结点
    int rchild;                //右孩子结点
}HTNode;                   
typedef struct
{
    char cd[N];                //存放哈夫曼码
    int start;                  //从start开始读cd中的哈夫曼码
}HCode;
void CreateHT(HTNode ht[],int n)                      //调用输入的数组ht[],和节点数n
{
    int i,k,lnode,rnode;
    int min1,min2;
    for (i=0;i<2*n-1;i++)     
        ht[i].parent=ht[i].lchild=ht[i].rchild=-1;    //所有结点的相关域置初值-1
    for (i=n;i<2*n-1;i++)                            //构造哈夫曼树
    {
        min1=min2=32767;                              //int的范围是-32768—32767
        lnode=rnode=-1;                              //lnode和rnode记录最小权值的两个结点位置
        for (k=0;k<=i-1;k++)
        {
            if (ht[k].parent==-1)                    //只在尚未构造二叉树的结点中查
        {
if (ht[k].weight<min1)                //若权值小于最小的左节点的权值
                {
                    min2=min1;rnode=lnode;字符串转数组编码方式
                    min1=ht[k].weight;lnode=k;
                }
                else if (ht[k].weight<min2)
                {
                    min2=ht[k].weight;rnode=k;
                }
            }
        }
        ht[lnode].parent=i;ht[rnode].parent=i;                  //两个最小节点的父节点是i
        ht[i].weight=ht[lnode].weight+ht[rnode].weight;        //两个最小节点的父节点权值为两个最小节点权值之和
        ht[i].lchild=lnode;ht[i].rchild=rnode;                  //父节点的左节点和右节点
    }
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for (i=0;i<n;i++)                              //根据哈夫曼树求哈夫曼编码
{
  hc.start=n;c=i;
  f=ht[i].parent;
  while (f!=-1)                                  //循序直到树根结点结束循环
  {
  if (ht[f].lchild==c)                          //处理左孩子结点
    hc.cd[hc.start--]='0';
  else                                          //处理右孩子结点
    hc.cd[hc.start--]='1';
  c=f;f=ht[f].parent;
  }
  hc.start++;                                    //start指向哈夫曼编码hc.cd[]中最开始字符
  hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n)    //输出哈夫曼编码的列表
{
int i,k;
printf("  输出哈夫曼编码:\n");
for (i=0;i<n;i++)                                //输出data中的所有数据，即A-Z
{
  printf("      %c:\t",ht[i].data);             

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。