课程设计说明书

课程设计说明书

课程设计：哈夫曼编码和译码 课程名称：数据结构

班级： 姓名： 学号： 教师：

信息工程学院计算机系

课程设计说明书 哈夫曼编码和译码

目录

一、设计任务书 ............................................................................................................... 3 问题描述 ....................................................................................................................... 3 基本要求 ....................................................................................................................... 3 小组成员及分工 ........................................................................................................... 3 二、设计题目 ................................................................................................................... 3 三、设计目的 ................................................................................................................... 3 四、算法思想分析 ........................................................................................................... 4 建立哈夫曼树 ............................................................................................................... 4 构造哈夫曼树的过程 ............................................................................................... 4 一个完整的编/译码系统应具有的功能 .................................................................. 4 选择parent为0且权值最小的两个根结点的算法 ................................................ 5 统计字符串中字符的种类以及各类字符的个数 .................................................... 5 构造哈夫曼树 ........................................................................................................... 5 哈夫曼编码 ................................................................................................................... 5 哈夫曼编码算法 ....................................................................................................... 5 建立正文的编码文件 ............................................................................................... 6 代码文件的译码 ........................................................................................................... 6 五、算法描述与实现 ....................................................................................................... 6 主要算法流程图 ........................................................................................................... 6 主要类型定义 ............................................................................................................... 9 功能描述 ....................................................................................................................... 9 程序源代码 ................................................................................................................... 9 六、程序运行结果 ......................................................................................................... 16 七、结论 ......................................................................................................................... 17

数据结构 2

课程设计说明书 哈夫曼编码和译码

一、设计任务书

问题描述

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

基本要求

一个完整的系统应具有以下功能：

1. 初始化及文本的频率统计。从终端读入字符集大小n，以及n个字符和

n个权值，完成文本的频率统计。建立哈夫曼树，并将它存于文件中； 2. 编码。利用已建好的哈夫曼树，从文件中读入，对正文进行编码。然后

将结果存入文件“CodeFile-姓名”中； 3. 译码。利用已建好的哈夫曼树将输入的代码进行译码，将文件“CodeFile-姓名”中的代码进行译码，结果存入文件“Decoding-姓名”中；

4. 打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式显示在屏幕上。

小组成员及分工

二、设计题目

哈夫曼编码和译码

三、设计目的

利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

数据结构 3

课程设计说明书 哈夫曼编码和译码

四、算法思想分析

树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表。树在计算机领域中也得到广泛应用，如在编译程序中，可以用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织之一。

哈夫曼树能将符号按概率从大到小的顺序排列，能对对概率最小的两个符号求其概率之和，同时给两个符号分别赋予码元，能从树根到端点经过的树枝即为码字，并输出码字。树中从根到每个叶子都有一条路径，对路径上的各分支约定:指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码。

建立哈夫曼树

在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每个结点的路径长度之和。带权二叉树是指每个结点都带有一个权值的二叉树。

构造哈夫曼树的过程

1. 将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n

棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点； 2. 在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新

二叉树，新二叉树的根结点权值为这两棵树根的权值之和；

3. 在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并

将刚刚新构造的二叉树加入到森林中； 4. 重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树

就是哈夫曼树。 易证明，路径长度最短的二叉树一定是一棵完全二叉树。由哈夫曼树算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。

算法的第二步是将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树;每合并一次，森林中就减少一棵树，产生一个新结点.显然要进行n-1次合并,所以,共产生n-1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n-1分支结点，其中n个叶结点是初始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可用一个大小为2n-1的一维数组来存储哈夫曼树中的结点。

一个完整的编/译码系统应具有的功能

1. 建立哈夫曼编码树(Create)。从键盘输入字符集中的所有字符及其对应的

数据结构

4

课程设计说明书 哈夫曼编码和译码

频率值，建立哈夫曼编码树。

2. 输出编码表(Table)。利用已建好的哈夫曼树，列出字符集中的所有字符

及其对应的哈夫曼编码。

3. 编码(Coding)。利用已建好的哈夫曼树，对从键盘输入的正文串进行编

码，并在屏幕上显示结果。

4. 译码(Decoding)。利用已建好的哈夫曼树，对从键盘输入的0、1代码串

进行译码，并在屏幕上显示结果 要实现哈夫曼树算法，首先要实现在parent为0且权值最小的两个根结点的选择算法；另外，还要有一个实现统计输入电文字符串中各种字符出现的频率以及字符的种类的算法。

选择parent为0且权值最小的两个根结点的算法

在众多权中选择parent为0且权值最小的两个根结点，并设其序号，选择并靠引用参数带回主调函数。

统计字符串中字符的种类以及各类字符的个数

假设字符串全是大写字母，那么该算法的实现思想是：先定义一个含有26个元素的临时整型数组，用来存储各种字母出现和次数。因为大写字母的ASCII码与整数1~26之间相差64，因此在算法中使用字母减去64作为统计数组的下标对号入座，无须循环判断来实现，从而提高了效率；另外，要求出字符串中有多少种字符，并保存这些字符以供编码时使用。统计和保存都比较容易，用一个循环来判断先前统计好的各类字符个数的数组元素是否为零，若不为零，则将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组的元素中。

构造哈夫曼树

构造哈夫曼树HT，建立一个数组来存放字符串中不同类的字符，另外设一个数组存放每类字符在字符串中出现的频率(即权值)。

哈夫曼编码

哈夫曼编码算法

根据哈夫曼树HT求哈夫曼编码表HC,设两个变量分别指示HT中孩子和双亲的位置，设一个数组存放编码串。假设是结点的左孩子,则生成0,否则生成代码1。

数据结构 5

课程设计说明书 哈夫曼编码和译码

建立正文的编码文件

建立编码文件的基本思想是：将要编码的字符串中字符逐一与预先生成哈夫曼树时保存的字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件,直至所有的字符处理完为止。

代码文件的译码

译码的基本思想是：读文件中编码，并与原生成的哈夫曼编码表比较，遇到相同时，即取出其对应的字符存入一个新字符数组中。

五、算法描述与实现

主要算法流程图

图1哈夫曼编码流程图

数据结构

6

课程设计说明书 图2创建哈夫曼树

数据结构 哈夫曼编码和译码

7

课程设计说明书 图3哈夫曼译码

数据结构 哈夫曼编码和译码

8

课程设计说明书 哈夫曼编码和译码

主要类型定义

typedefstruct {

int weight; int parent; intlchild; intrchild;

}HTNode; 哈夫曼树节点

typedefstruct {

char ch;

char bits[26]; intlen;

}CodeNode;

储存编码信息的结构体

功能描述

void select(HuffmanTreeHT,intk,int&s1,int &s2)

在HT[1..k]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2，并靠引用参数带回主调函数

intcount(char *s,intcnt[],char str[])

计算出现字符种类的个数

void ChuffmanTree(HuffmanTree HT, HuffmanCode HC, intcnt[], char str[]) 创建哈夫曼树

void HuffmanEncoding(HuffmanTree HT, HuffmanCode HC) 根据哈夫曼树求哈夫曼编码

void coding(HuffmanCodeHC,char *str)

对str所代表的字符串进行编码并写入磁盘文件 char *decode(HuffmanCode HC) 代码文件的译码

程序源代码

---插入源代码---

// HuffmanThree2.cpp : 定义控制台应用程序的入口点。 //制作小组：第五小组北京石油化工学院 //哈夫曼编码/译码系统

数据结构

9

课程设计说明书

//主要功能：1、打开特定文件并显示其内容 // // // // // //

#include\ #include #include

#definen 26 //叶子结点数

#definem 2*n-1 //赫夫曼树中接点总数 intnum; typedefstruct {

int weight; //权值 int parent; intlchild; intrchild;

哈夫曼编码和译码

2、扫描统计字符的频度并生成哈夫曼树 3、进行哈夫曼编码并显示结果 4、对哈夫曼编码进行译码并显示结构 5、退出系统

1、打开文件是.txt类型，文件里的内容是以大写26个字母作为写入的例子使用 2、编码后的哈夫曼编码最后也是以.txt类型文件存储

//实验备注：

}HTNode; //树中结点类型

typedefHTNodeHuffmanTree[m + 1]; //0号单元不用

typedefstruct {

typedefCodeNodeHuffmanCode[n + 1];

HuffmanTree HT; HuffmanCode HC; charst[254];

////////////////////////////////////////// voidselect(HuffmanTreeHT, intk, int&s1, int&s2)

{ //在HT[1..k]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2，并靠引用参数带回主调函数

inti, j;

intminl = 32767;//int型的上限值 charch; //存放编码的字符 char bits[26]; //存放编码位串 intlen;

}CodeNode;

数据结构 10

课程设计说明书 for (i = 1; i<= k; i++) //找s1 { if (HT[i].weight

minl = HT[i].weight;

}

} s1 = j; minl = 32767;

for (i = 1; i<= k; i++) //找s2 { if (HT[i].weight

minl = HT[i].weight;

} s2 = j;

}

}

/////////////////////////////////////////////////// intcount(char *s, intcnt[], charstr[]) { //str[]是存放所有电文中出现的字符种类个数的数组

//cnt[]是存放每个字符出现次数的数组，也就是字符的对应权值 //s是指向电文中某字符的指针

char *p; inti, j, k;

int temp[27];//临时存放字符个数 for (i = 1; i<= 26; i++)//初始化temp

temp[i] = 0;

for (p = s; *p != '\\0'; p++) if (*p >= 'A'&& *p <= 'Z') { k = *p - 64;//A的ASCII码是65,此步算出字符在数组中的下标 //算出一个下标就说明该字符出现了一次 temp[k]++;

}

j = 0;

for (i = 1, j = 0; i<= 26; i++) {

if (temp[i] != 0)//不等于零说明该字符在电文中出现了 数据结构 哈夫曼编码和译码

11

课程设计说明书

{

j++;

哈夫曼编码和译码

str[j] = i + 64;//i+64对应字符的ASCII码

cnt[j] = temp[i];//把各字符的出现次数复制到保存权值的cnt[]中

} }

return j;//返回出现的字符种类个数 }

/////////有了权值和字母种类////////////////////////////

voidChuffmanTree(HuffmanTreeHT, HuffmanCodeHC, intcnt[], charstr[]) { //str[]是存放所有电文中出现的字符种类个数的数组 //cnt[]是存放每个字符出现次数的数组，也就是字符的对应权值 inti, s1, s2;

for (i = 1; i<= 2 * num - 1; i++)//初始化 { //num是countchar（）的返回值，在main中定义的全局值 HT[i].lchild = 0; HT[i].rchild = 0; HT[i].parent = 0;

HT[i].weight = 0;

}

for (i = 1; i<= num; i++)//给叶子结点赋权值 {

HT[i].weight = cnt[i]; }

//开始构造树

for (i = num; i<= 2 * num - 1; i++) { select(HT, i, s1, s2); HT[s1].parent = i + 1; HT[s2].parent = i + 1; HT[i + 1].lchild = s1; HT[i + 1].rchild = s2;

HT[i + 1].weight = HT[s1].weight + HT[s2].weight; }

HT[2 * num - 1].parent = 0; //根接点的 parent值为0

for (i = 1; i<= num; i++) 数据结构 12

课程设计说明书 }

//////////////////////////////////////////

HC[i].ch = str[i];

哈夫曼编码和译码

i = 1;

printf(\); while (i<= num) { }

printf(\); printf(\显示赫夫曼树HT: ||\\t\\n\); printf(\序号\\t父亲\\t权值\\t左孩子\\t右孩子\\n\);

for (i = 1; i<= 2 * num - 1; i++) //输出最终构造出的赫夫曼树

printf(\, i, HT[i].parent,

printf(\字符 %c,次数为：%d \\n\, HC[i].ch, cnt[i++]);

HT[i].weight, HT[i].lchild, HT[i].rchild);

voidHuffmanEncoding(HuffmanTreeHT, HuffmanCodeHC) { //根据哈夫曼树求哈夫曼编码 }

////////////////////////////////// voidcoding(HuffmanCodeHC, char *str)

{ //对str所代表的字符串进行编码并写入磁盘文件

inti, j;

int c, p, i; //c指向孩子，p指向双亲的位置 char cd[n]; //存放编码的临时向量

int start; //指示编码在临时向量中的起始位置 cd[num] = '\\0'; //编码结束符 for (i = 1; i<= num; i++) { }

printf(\); printf(\显示赫夫曼编码HC: ||\\n\); for (i = 1; i<= num; i++)

printf(\, i, HC[i].ch, HC[i].bits); start = num; //编码起始位置的初值 c = i; //从叶子结点HT[i]开始上溯

while ((p = HT[c].parent)>0) //直到上溯到HT[c]是树根为止 { }

strcpy(HC[i].bits, &cd[start]); //复制编码字符串 HC[i].len = num - start;

cd[--start] = (HT[p].lchild == c) ? '0' : '1'; //若HT[c]是HT[p]的左孩子，则生成c = p; //继续上溯

0，否则生成代码1

数据结构 13

课程设计说明书 FILE *fp;

fp = fopen(\, \);

while (*str) //对电文中字符逐一生成编码并写入文件 { for (i = 1; i<= num; i++) { if (HC[i].ch == *str) { for (j = 0; j

fputc(HC[i].bits[j], fp); break;

}

} str++;

}

fclose(fp);

}

///////////////////////////////////////// char *decode(HuffmanCodeHC) { //代码文件的译码 FILE *fp; charstr[254]; //假设原文本文件不超过254个字符 char *p;

staticcharcd[n + 1]; inti, j, k = 0, cjs;

fp = fopen(\, \); while(!feof(fp)) { cjs = 0; //一个字符的编码是否读结束

for (i = 0; i

}

}

}

str[k] = '\\0'; p = str;

return p;

数据结构 哈夫曼编码和译码

14

课程设计说明书 }

//////////////////////////////////////// intfileopen(charstring[])//读入文件 { FILE *fp;

哈夫曼编码和译码

if ((fp = fopen(\, \)) == NULL) { printf(\); printf(\不能打开文件！ ||\\t\\n\); printf(\);

}

while (fgets(string, 100, fp) != NULL)

printf(\, string); fclose(fp); return 0;

}

voidmain() { charst[100], *s, str[27]; intcn[27]; HuffmanTree HT; HuffmanCode HC; int x; int exit = 0;

while (1) { if (exit) break; printf(\); printf(\哈夫曼编码/译码系统 ***********||\\t\\n\); printf(\欢迎使用本系统 ***********||\\t\\n\); printf(\北京石油化工学院信息工程分院第五小组||\\t\\n\);

printf(\小组成员： ||\\t\\n\); printf(\);

printf(\); printf(\); printf(\打开file.txt&&显示内容 *********||\\t\\n\); printf(\字符频度&&HuffmanTree *********||\\t\\n\); printf(\执行编码&&显示编码结果 *********||\\t\\n\); printf(\执行译码&&显示译码结果 *********||\\t\\n\);

printf(\退出 *********||\\t\\n\);

数据结构 15

课程设计说明书 哈夫曼编码和译码

printf(\); printf(\请选择：\);

scanf(\, &x);

switch (x) { case 1: printf(\); printf(\读出文本为： ||\\t\\n\\t \); fileopen(st);//打开文件函数 printf(\); break;

case 2:num = count(st, cn, str); //统计字符的种类及各类字符出现的频率

ChuffmanTree(HT, HC, cn, str); printf(\); break;

case 3:

HuffmanEncoding(HT, HC); //生成哈夫曼编码 coding(HC, st); //建立哈夫曼编码文件 printf(\); break;

case 4:s = decode(HC); //读编码文件译码

printf(\); printf(\译码后的内容： ||\\t\\n\\t \); printf(\, s); //输出译码后的字符串 printf(\); break; case5:exit = 1; break;

default:

printf(\输入错误！ ||\\t\\n\); continue;

} }

}

六、程序运行结果

数据结构

16

课程设计说明书 哈夫曼编码和译码

七、结论

通过本次设计，明白了利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对传输数据预先进行编码，在接收端将传来的数据进行译码（复原）。在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。对于于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

数据结构 17

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库课程设计说明书在线全文阅读。