数据结构课程设计报告

计算机工程学院。

课程设计报告。

课程名称：数据结构课程设计。

设计题目：哈夫曼编码器。

院系：计算机工程学院。

班级：软件1102

组别15学生姓名：吴超学号： 1101306229

起止日期： 2011 年 12 月 26 日 ~ 31 日

目录。1、设计目的 2

2、需求分析 3

2.1选题的意义及背景。

2.2基本要求。

2.3运行环境及开发工具。

3、概要设计 4

3.1设计思想。

3.2程序框图。

3.3方法及原理。

3.4主要数据结构。

4、详细设计 7

4.1创建哈夫曼树。

4.2编码。

4.3源程序。

5、调试与操作说明 14

6、总结与体会 15

7、致谢 16

设计目的。1、利用学过的数据结构知识设计一个简单的哈夫曼编/译码器系统。

2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

需求分析。2.1、选题的意义和背景。

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这是要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

2.2、基本要求。

1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；

2)编码：利用建好的哈夫曼树生成哈夫曼编码；

3)输出编码；

4)设字符集及频度如下表：

2.3、运行环境及开发工具。

本程序采用visual c++6.0编程实现。

概要设计。3.1设计思想。

本程序的主要功能是实现对用户输入的字符编码，然后再把编码结果翻译成原字符。但在进行这些操作之前必须做一项工作，就是创建huffman树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。

所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为wpl=(w1*l1+w2*l2+w3*l3+..wn*ln)，n个权值wi(i=1,2,..

n)构成一棵有n个叶结点的二叉树，相应的叶结点的路径长度为li(i=1,2,..n)。可以证明哈夫曼树的wpl是最小的。

哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。

3.2程序框图及流程图。

3.3.1 创建huffman树。

本文创建huffman树是在顺序链表的基础上进行的，建树原理如下：

1、根据给定的n个权值，构造具有n棵二叉树的森林f=，其中每棵二叉树ti只有一个带权值wi的根结点，其左右子树均为空。

2、重复以下步骤，直到f中仅剩下一棵树为止：

(1)在f中选取两棵根结点的权值最小的二叉树，作为左右子树构造一棵新的二叉树。使新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

(2)在f中删去这两棵二叉树，把新的二叉树加入f。

最后得到的就是huffman树。

3.3.2 编码。

编码操作需在建立好huffman树的基础上进行。二叉树的叶子结点标记字符，由根结点沿着二叉树路径下行，左分支标记为0，右分支标记为1，则每条从根结点到叶子结点的路径唯一表示了该叶结点的二进制编码。编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结点的左孩子，则编码为0，如果是右孩子，则编码为1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。

如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。

3.4 主要的数据结构。

3.4.1 huffman结点结构。

huffman结点结构是本程序的基本结构，所有操作都在此上进行。其中包括存储字符的元素data，字符的权值weight，以及左右孩子指针和父指针。

typedef struct

char ch结点值。

int weight权值。

int parent父结点指针。

int lchild左孩子结点指针。

int rchild右孩子结点指针。

huffnode;

详细设计。4.1.1 功能描述。

huffman树是整个程序的核心部分，是编码译码操作的前提。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。根据字符出现的概率来构造平均长度最短的编码。

它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。

4.1.2 算法原理。

首先根据用户输入创建n棵子树的森林，然后对所有子树扫描，找出权值最小的两个子树，把它们合并成一棵新的子树，同时把它们的权值之和作为新树的权值。把这两棵子树删掉，再把新树加如到森林中，然后再扫描出权值最小的两棵子树，接着进行同样的操作，直到只剩下一棵树即为huffman树。

4.1.3 算法流程。

4.2.1 功能描述。

编码的功能就是把字符转换成二进制数来存储。

4.2.2 算法原理。

编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结点的左孩子，则编码为0，如果是右孩子，则编码为1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。

4.2.3 算法流程。

4.4源程序。

#include<>

typedef struct哈夫曼树的结构体。

char ch;

int weight权值。

int parent,lchild,rchild;

htnode,*hfmtree;

typedef char **hfmcode;

void select(hfmtree &ht,int a,int *p1,int *p2) /select函数，选出ht树到a为止，权值最小且parent为0的2个节点。

int i,j,x,y;

for(j=1;j<=a;++j){

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

x=j;break;

for(i=j+1;i<=a;++i){

if(ht[i].weightx=i选出最小的节点。

for(j=1;j<=a;++j) {

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

y=j;break;

for(i=j+1;i<=a;++i)

if(ht[i].weight{

y=i选出次小的节点。

if(x>y){

p1=y;p2=x;

elsep1=x;

p2=y;void hfmcoding(hfmtree &ht,hfmcode &hc,int n) /构建哈夫曼树ht，并求出n个字符的哈夫曼编码hc

int i,start,c,f,m,w;

int p1,p2;

char *cd,z;

if(n<=1){

return;

m=2*n-1;

ht=(hfmtree)malloc((m+1)*sizeof(htnode));

for(i=1;i<=n;++i初始化n个叶子结点。

printf("请输入第%d字符信息和权值：",i);

scanf("%c%d",&z,&w);

while(getchar()!n')

continue;

ht[i].ch=z;

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了