数据结构设计报告

课 程 设 计 报 告

课程名称 《数据结构》 课题名称 对电文中的字符串编码和译码 专 业 班 级 学 号 姓 名 指导教师

2011 年 12 月 26 日

湖南工程学院 课 程 设 计 任 务 书

课程名称 数据结构 课 题 对电文中的字符串编码和译码

专业班级 学生姓名 学 号 指导老师 审 批

任务书下达日期 2011 年 12 月 12 日 任务完成日期 2011 年 12 月 26 日

一、设计内容与设计要求

1．设计内容：

[问题描述] Huffman编码是一种最优变长码，即带权路径最小。这种编码有很强的应用背景，是数据压缩中的一个重要理论依据。对输入的一串文字符号实现Huffman编码，再对Huffman编码生成的代码串进行译码，输出电文字符串。

[基本功能]

1）．针对给定的字符串，建立Huffman树。 2）．生成Huffman编码。 3）．对编码文件译码。

2．设计要求：

1）．设计正确，方案合理。 2）．界面友好，使用方便。 3）．程序精炼，结构清晰。

4）．设计报告5000字以上，含程序设计说明、系统的功能框图、流程图、源程序清单等。

5）．实际操作过程中遇到的问题及解决方法：设计总结及心得体会。

6）．上机演示。

二、进度安排

第 17 周 星期一 8时：00分——11时：30分 星期二 14时：00分——17时：30分 星期三 14时：00分——17时：30分 星期五 14时：00分——17时：30分

第 18 周 星期一 8时：00分——11时：30分

星期二 8时：00分——11时：30分

附：

课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的源代码，要求对程序写出必要的注释）。 正文总字数要求在5000字以上（不含程序源代码）。

目 录

1.需求分析.................................................................................................................... 1

1.1问题描述.......................................................................................................... 1 1.2程序的功能...................................................................................................... 1 2.概要设计.................................................................................................................... 1

1. 1系统的总体设计.............................................................................................. 1 2.2各模块的功能.................................................................................................. 2 2.3相关数据结构设计........................................................................................... 3 3.详细设计.................................................................................................................... 3

3.1 采用C语言定义相关的数据类型 ................................................................. 3 3.2优先级结果比较函数...................................................................................... 4 3.4函数主模块...................................................................................................... 5 4.系统调试.................................................................................................................... 5 5.运行结果.................................................................................................................... 7

5.1输入界面.......................................................................................................... 7 5.2求值界面.......................................................................................................... 8 5.3退出程序.......................................................................................................... 9 5.4程序调试中的问题.......................................................................................... 9 6.心得体会.................................................................................................................... 9 7.附录.......................................................................................................................... 10

7.1程序清单........................................................................................................ 10 7.2. 参考文献....................................................................................................... 16 8.评分表...................................................................................................................... 17

1.需求分析

1.1问题描述

问题描述：Huffman编码是一种最优变长码，即带权路径最小。这种编码有很强的应用背景，是数据压缩中的一个重要理论依据。对输入的一串文字符号实现Huffman编码，再对Huffman编码生成的代码串进行译码，输出电文字符串。

1.2程序的功能

1）．针对给定的字符串，建立Huffman树。 2）．生成Huffman编码。 3）．对编码文件译码。

2.概要设计

1. 1系统的总体设计

1). 确定哈夫曼树和哈夫曼编码的储存表示

2). 在HT[1..n]中选择parent 为0 的且weight 最小的两个节点s1 和s2 3). w 存放n 个字符的权值(均>0)，构造哈夫曼树HT，输出静态链表(数组)储存哈夫曼树储存结构模拟，然后求出n 个字符的哈夫曼编码HC 4). 利用哈夫曼编码对密文进行译码，输出译后的字符串

5). 在main()中实现：输入一串字符（正文），计算不同字符(包括空格)的数目以及每种字符出现的频率(以该种字符出现的次数作为其出现频率,然后调用各子函数实现该程序功能

6).程序的输出，程序输出的形式： 7).统计字符出现次数并输出

8).根据字符出现次数求出哈夫曼编码并输出（根据算法差异得到的编码可能不同，但应具有两个特征，一是编码长度应与表中相同，二是编码应该是前缀编码） 9).以树的形式输出哈夫曼树

1

10).程序总体结构设计图：

开始

是 是否继续 译码： 接收方利用哈夫曼编码对密文进行译码，输出译后的字符串。 编码： 发送方利用得到的哈夫曼编码对正文进行编码，输出密文。 初始化： 输入字符 输入字符出现的频率

否

结束 2.2各模块的功能

1).创建哈弗曼树

int Creat(HuffmanTree &ht, HTNode ch[N], int n) 2)．对所有的叶子节点进行编码

void CrtHuffmanCode(HuffmanTree ht, Char hc[N], int n) 3). 输出哈弗曼树

void Print(HuffmanTree ht, int m)

2

4）.输出哈弗曼码

void PrintHuffmanCode(HuffmanTree ht,Char hc[], int n)//输出哈弗曼码 5).对字符串译码

void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m) 6).寻找权值最小的两个结点

void Search(HuffmanTree &ht, int flag[2], int n) 6). 输入字符串

int Input(HTNode ch[N])

2.3相关数据结构设计

1)初始化：

a.输入正文: 输入一串字符（正文）

b.统计字符出现次数并输出: 计算不同字符(包括空格)的数目以及每种字符出现的频率(以该种字符出现的次数作为其出现频率） c.求出哈夫曼编码并输出 d.以树的形式输出哈夫曼树 e. 编码：

发送方利用得到的哈夫曼编码对正文进行编码，输出密文 f.译码：

接收方利用哈夫曼编码对密文进行译码，输出译后的字符串

3.详细设计

3.1 采用C语言定义相关的数据类型

定义了两个结构体HTNode为哈弗曼树形结构，WNode存放叶子节点的信息。 #include #include #include

#define N 20

typedef char * Char;

typedef struct Node

3

{ char data; //存放节点的数据 int weight; //存放节点的权值 int parent; //双亲节点信息 int lchild; //左孩子的信息 int rchild; //右孩子的信息 int flag; //判断真假

}HTNode, *HuffmanTree;//0号未用

3.2优先级结果比较函数

1).初始化：构造哈弗曼树

a.输入: 输入字符和它的权值 b.求出哈夫曼编码并输出 c.以树的形式输出哈夫曼树

2).编码：发送方利用得到的哈夫曼编码对正文进行编码，输出密文 3).译码：接收方利用哈夫曼编码对密文进行译码，输出译后的字符串

3.3函数各模块功能分析

1）创建哈弗曼树：首先开辟空间，对哈弗曼树赋初值，用flag为0或1来标志它是否被访问过。然后从叶子节点到双亲节点依次构造哈弗曼树。

2）对哈弗曼树进行编码：构造哈弗曼树之后，对每个叶子节点进行编码，将其存放在数组中，方便之后进行解码。

3）输入模块：最开始输入字符及它出现的频率，用N/Y判断是否输入完成，用n记录输入字符的个数，依次存放到数组ch[n].data,和 ch[n].weight中。 4）search函数：寻找叶子节点中权值最小的节点，为构造哈弗曼树建立基础。 5）解码：将输入的0、1字符串解码为字符。从根节点开始，依次扫描，若遇到0则指向左孩子节点若为1则指向右孩子节点，知道遇到左右孩子节点都为0则将其叶子节点信息（字符）输出。完成解码过程。

6）主函数中调用了Creat(ht, ch, num) CrtHuffmanCode(ht, hc, num) PrintHuffmanCode(ht,hc, num) Decoding(ht, str, m)等函数，将问题实现了， 在创建哈弗曼树的时候调用了Search(ht, flag, i-1)函数，找出叶子节点中权值最小的两个节点，就可以成功的将哈弗曼树构造出来。

4

3.4函数主模块

void main() { HTNode ch[N]; int num = Input(ch); HuffmanTree ht;

int m = Creat(ht, ch, num); Print(ht, m);

Char hc[N]; CrtHuffmanCode(ht, hc, num);

PrintHuffmanCode(ht,hc, num); int flag = 1; while(flag)

{ char str[N];

printf(\"输入字符串: \"); scanf(\"%s\ Decoding(ht, str, m); printf(\"是否继续输入: \"); getchar();

char ch;

scanf(\"%c\

if('n' == ch || 'N' == ch)

flag = 0;

}

}

4.系统调试

问题1：统计字符出现次数并输出；

解决方案：运用for循环和数组来实现该功能 问题2：输出哈弗曼树；

解决方案：运用静态链表(数组)进行哈夫曼树储存结构模拟问题3：构造哈弗曼树；

5

解决方案：利用结构体数组来存储，这样可以方便将每个叶节点的信息保存，输出，调用。

初始化：输入一串字符（正文），计算不同字符(包括空格)的数目以及每种字符出现的频率(以该种字符出现的次数作为其出现频率），根据权值建立哈夫曼树，输出每一种字符的哈夫曼编码。

编码：利用求出的哈夫曼编码，对该正文（字符串）进行编码，并输出。 译码：对于得到的一串编码，利用已求得的哈夫曼编码进行译码，将译出的正文输出。

输出哈夫曼树形态：以树的形式输出哈夫曼树。程序相对比较复杂，以四维数组为哈弗曼树的存储结构在数据通信中，经常需要将传送的文字转换成为二进制字符0和1组成的二进制字符串，称这个过程为编码。显然，希望电文编码的代码长度最短。哈夫曼树可用于构造使电文编码的代码长度最短的编码方案。在程序运行中出现很多问题，比如说在解码的时候对输入的0、1串不能正确解码，后来多增加了一个结构体来存叶子节点的信息将这个问题成功解决。

6

5.运行结果

5.1输入界面

7

5.2求值界面

8

5.3退出程序

5.4程序调试中的问题

（1）统计字符出现次数并输出，本程序只能输入there are three students

(char型)来运行，该处可以运用其他函数或方法进行改进 （2）译码处存在问题，可以进一步改进

（3）进行更多的输入的编码和译码，使程序更具实用性 （4）多应用一些C++知识，使程序更加简洁一些

6.心得体会

通过这次课题实验的程序实践，我实在获益匪浅！数据结构是这个学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。同时，学习这门学科也是艰辛的，因为它比较难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。因为开始时基础不是很好，过程中遇到了不少

9

的阻碍，编写程序的进度也比较慢。虽然如此，但是通过自己的努力与老师的指导及同学的帮助，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次实验的核心算法，并使其能够正常的运行。这将近两个星期的设计工作，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中包含的心酸，外人是不会明白的。非常感谢在背后一直给我指导的老师和同学，他们的支持和鼓励让我在遇到挫折时能够站起来战胜它，也让我走到了今天这一步，完成了实验的设计。今后，我会更加努力的学习专业知识，提高自我的能力。

7.附录

7.1程序清单

#include #include #include #define N 20 typedef char * Char; typedef struct Node {

char data; int weight; int parent; int lchild; int rchild; int flag;

}HTNode, *HuffmanTree;//0号未用 int Input(HTNode ch[N])//输入字符串 {

int flag = 1;

10

int n = 0;

while(flag && n != N) { printf(\"input word weight: \");

scanf(\"%c%d\ getchar();

ch[n].parent = 0; //用来标记 printf(\"continue input :(Y/N) \"); char select;

scanf(\"%c\ getchar();

if('n' == select || 'N' == select) //判断输入终止的条件 { flag = 0;

}

++n; // 计数

} return n;

}

void Search(HuffmanTree &ht, int flag[2], int n) //寻找权值最小的两个结点{ int min;

for(int i = 0; i < 2; ++i) { min = 0; int mark = 0;

for(int j = 1; j <= n; ++j) { if(0 == ht[j].flag) {

if(!mark)

11

{ min = j; mark = 1; }

if(ht[min].weight > ht[j].weight) { min = j;

}

}

}

flag[i] = min;

ht[min].flag = 1; //删除

}

}

//出的问题在于逻辑上，没有考虑清楚 //出现很多逻辑错误

int Creat(HuffmanTree &ht, HTNode ch[N], int n)//构造哈弗曼树{ int m = 2 * n - 1;

ht = (HuffmanTree )malloc((m + 1) * sizeof(HTNode)); int i;

for(i = 1; i <= n; ++i) { ht[i].data = ch[i-1].data; ht[i].weight = ch[i-1].weight; ht[i].lchild = 0; ht[i].rchild = 0; ht[i].parent = 0; ht[i].flag = 0;

}

12

for(i = n+1; i <= m; ++i) { } int flag[2];

for(i = n+1; i <= m; ++i) {

Search(ht, flag, i-1);

ht[i].data = '#'; //标示没有 ht[i].weight = ht[flag[0]].weight + ht[flag[1]].weight; ht[flag[0]].parent = i; ht[flag[1]].parent = i; ht[i].lchild = flag[0]; //合并 ht[i].rchild = flag[1];

//printf(\"%d %c %d %d %d %d\\n\i, ht[i].data, ht[i].weight, ht[i].parent, ht[i].weight = 0; ht[i].lchild = 0; ht[i].rchild = 0; ht[i].parent = 0;

ht[i].flag = 0; //用来标记是否被访问

flag[0], flag[1]); }

void CrtHuffmanCode(HuffmanTree ht, Char hc[N], int n) //编码 {

} return m;

char *cd;

cd = (char *)malloc(n * sizeof(char )); cd[n-1] = '\\0';

for(int i = 1; i <= n; ++i) //1 n 之间是叶子 {

int start = n-1;

13

}

}

int c = i;

int p = ht[i].parent;

while(p) //一直找到根,这是从叶子到根 { }

hc[i] = (char *)malloc((n - start) * sizeof(char )); strcpy(hc[i], &cd[start]);

--start; if(c == ht[p].lchild) { } else { } c = p;

p = ht[p].parent;

cd[start] = '1'; cd[start] = '0';

free(cd);

void Print(HuffmanTree ht, int m)//输出哈弗曼树

{ printf(\"输出蛤夫曼树：\\n ht data weight parent lchild rchild\\n\");

for(int i = 1; i <= m; ++i)

{ printf(\"%3d\%c\%d\%d\%d\%d\\n\i, ht[i].data, ht[i].weight, ht[i].parent,

ht[i].lchild, ht[i].rchild); }

}

void PrintHuffmanCode(HuffmanTree ht,Char hc[], int n)//输出哈弗曼码 { printf(\"输出蛤夫曼编码：\\n\");

for(int i = 1; i <= n; ++i)

14

{ printf(\"%c\\ printf(\"%s\\n\

}

}

void Decoding(HuffmanTree ht, char str[N], int n)//解码 { for(int i = 0; str[i] != '\\0';) { int p = n;//p 应该是根 while(ht[p].lchild || ht[p].rchild) { if('0' == str[i]) { p = ht[p].lchild;

} else { p = ht[p].rchild; } ++i;

}

printf(\"%c\

}

printf(\"\\n\");

}

void main() { HTNode ch[N]; int num = Input(ch); HuffmanTree ht;

int m = Creat(ht, ch, num); Print(ht, m);

15

}

Char hc[N];

CrtHuffmanCode(ht, hc, num); PrintHuffmanCode(ht,hc, num); int flag = 1; while(flag) {

char str[N];

printf(\"输入字符串: \"); scanf(\"%s\ Decoding(ht, str, m); }

printf(\"是否继续输入: \"); getchar(); char ch;

scanf(\"%c\if('n' == ch || 'N' == ch) flag = 0;

7.2. 参考文献

[1]数据结构（C 语言版）147 页.赫夫曼树和赫夫曼树编码的存储表示，及求赫夫曼编码的算法

[2]C 语言设计（第三版）371 页—377 页附录E C 库函数.用于程序的开始 [3]网络.赫夫曼译码

[4]数据结构课程设计指导丛书.

[5]谭浩强.C程序设计(第三版).北京：清华大学出版，2005 [6]谭浩强.C程序设计(第四版).北京：清华大学出版，2010 [7]李春葆 尹为民.数据结构.北京：清华大学出版，2010. [8]C编写组编.常用C语言用法速查手册.北京：龙门书局，1995

16

8.评分表

计算机与通信学院课程设计评分表

课程名称： 数 据 结 构 项 目 评 价 设计方案的合理性与创造性 设计与调试结果 设计说明书的质量 答辩陈述与回答问题情况 课程设计周表现情况 综合成绩

教师签名： 日 期：

17