数据结构课程设计
一、目的
《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。
二、要求
通过这次设计，要求在数据结构析逻辑特性和物理表示，数据结构的选择的应用、算法的设计及其实现等方面中深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
三、内容
2.哈夫曼编码/译码器
【问题描述】
设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
【基本要求】
(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
(2)编码：利用建好的哈夫曼树生成哈夫曼编码；
(3)输出编码；
(4)设字符集及频度如下表：
字符 空格 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符 N O P Q R S T U V W X Y Z
频度 57 63 15 1 48 51 80 23 8 18 1 16 1
【选做内容】
(1)译码功能；
(2)显示哈夫曼树；
(3)界面设计的优化。
哈夫曼编写编译码
一、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，这要求在发送端通过一个编码系统对待传输预先编码，在接收端将传来的数据进行译码。对于双工通道，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
二、概要设计
1．哈夫曼树的定义：
在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。
2．哈夫曼树的构造：
假设有N个权值，则构造出的哈夫曼树有N个叶子结点。N个权值分别设为W1,W2,……….Wn,则哈夫曼树的构造规则为： 
（1）将W1，W2，……….Wn看成有N棵树的森林；
（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左，右子树，且新树的根结点为其左，右子树结点权值之和；
（3）从森林中删除选取取的两面三刀棵树，并将新树加入森林；
（4）重复（2）（3）步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。
在构造哈夫曼树的过程中，每次由两棵权值最小的树生成一棵新树时，新树的左子树和右子树可以任意安排，这样将会得到具有不同结构的多个哈夫曼树，但字们都具有相同的带权路径长度。为了歙　得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权要小于等于右女树根结点的权。
3．构造哈夫曼树的算法实现：
假设哈夫曼树采用双亲孩子表示法存储，并增加权值域，构造哈夫曼树的叶子结点（树木的权）有N个，合并次数为N—1次，则森林中总共有2N—1棵树，（包含合并后删除的）。  　存储结构描述为：
          const  int  n=maxn      //maxn表示叶子数目
          const  int  m=2*n-1    //m为森林中树的棵数
          class  tree
          {  public:
          float  weight;          //权值
          int  parent;            //双亲
          int  lch, rch;            //左，右孩子 
          }
          tree  hftree[m+1];        //规定从第一个元素hftree[1]开始使用数组元素，故定义长度为m+1而不为m
4．结构类型：
typedef struct
{
char data;
int weight;
int parent;
int lchild;
int rchild;
}huffnode;
typedef struct
{
    char cd[MAX];
    int start;
}huffcode;
5．主程序
int main()
{
  初始化:输入字符代码以及权值.
  编制哈夫曼码:根据权值建立二叉树, 输出相应的根节点到叶结点的路
径,便是哈夫曼编码.
编码:输入字符,输出哈夫曼码.
译码:输入哈夫曼,输出字符代码.
退出:结束进程,退出程序.
return 0;
}
三、详细设计
#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#define MAX 25
typedef struct
{
    char data;
    int weight;
    int parent;
    int lchild;
    int rchild;
} HTNode;
哈夫曼编码树的带权路径长度
typedef struct
{ 
    char cd[MAX];
    int start;
} HuffmanCode;
int main()
{
    HTNode ht[2*MAX];
    HuffmanCode hcd[MAX], d;
    int i, k, f, l, r, n, c, s1, s2;
    cout<<"* * * * * * * * * * * * * * * * * * * * * \n"
        <<"\t哈夫曼编码与译码系统\n"
        <<"* * * * * * * * * * * * * * * * * * * * * \n";
    cout<<"\n请输入哈夫曼码元素个数：";
    cin>>n;
    cout<<"请输入各个元素的结点值与权值:\n";
    for(i=1;i<=n;i++)
    {
        cout<<"  第"<<i<<"个元素-->\n\t结点值：";
        cin>>&ht[i].data;
        cout<<"\t权  值：";
        cin>>ht[i].weight;
    }
    for(i=1;i<=2*n-1;i++)

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