数据结构课程设计报告(HuffMan编码器)

数据结构设计报告 计科0403 雷娜 数据结构课程设计报告题目：HuffMan编码器目 录一问题描述二基本要求(需求分析)三概要设计(设计思想、实现方法、模块设计)四详细设计(数据结构设计、算法设计、算法分析)五测试数据及测试结果六课程设计小结(心得体会、存在问题、改进措施)一 问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。二 基本要求(需求分析)一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。（5）T：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符 空格 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） 编码结果以文本方式存储在文件CodeFile中。（2） 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。（3） 在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。三 概要设计(设计思想、实现方法、模块设计)哈夫曼编码是一种效率比较高的变长无失真信源编码方法，它的平均码长最短，因此是最佳编码。我采用二进制哈夫曼编码。1 设计思想a、 原理：构造一个码树。b、 编码步骤： (1) 将信源符号按概率从大到小的顺序排列，为方便起见，令p(x1)p(x2)p(xn) 。 (2) 对概率最小的两个信源符号求其概率之和，同时给两个符号分别赋予码元“0”和“1”。将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，结果得到一个只包含（n1）个信源符号的新信源，称为信源的第一次缩减信源,用S1表示。 (3) 将缩减信源S1的符号仍按概率从大到小的顺序排列，重复步骤2，得到只含（n2）个符号的缩减信源S2。 (4) 重复上述步骤，直至缩减信源只剩下两个符号为止，此时所剩两个符号的概率之和必为1。 (5) 按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。2 实现方法第一， 哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根束，最后得到一个横放的码树，因此，编出的码是即时码。第二， 哈夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码，从而使平均码长最小。第三， 每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字并不惟一。3 模块设计1进入的操作界面：（图一）2输入字符串，及编码结果（图二）3统计不同字符数及带权路径长度（图三）4各字符编码明细（图四）四详细设计(数据结构设计、算法设计、算法分析)（一） 数据结构设计1) 结点类型：/huffcode.cpptypedef struct HaffmanTreeNode char ch, code15; int weight; int parent, lchild, rchild; HTNode, *HaTree;typedef struct HTNode arrMAX_NODE; int total; HTree;2) 基本操作：int statistic_char(char *text, HTree *t);int create_htree(HTree *t);void coding(HTree *t, int head_i, char *code);void print_htree_ldr(HTree *t, int head_i, int deep, int* path);void code_string(char *text, HTree *t,char *codes);（二）算法设计在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。（三）算法分析(1) 有效的信源编码可取得较好的冗余压缩效果。(2) 有效的信源编码可使输出码元概率均匀化。4 测试数据及测试结果1输入简短英文字符串：（图五）2输入数字英文混合串：（图六）3混合串： （图七） 4输入复杂无规则长串：（图八）六课程设计小结(心得体会、存在问题、改进措施)本次程序设计使我不仅深化理解了教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且在总体分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到了综合训练。本次实验我选择Huffman编译码器的课题。帮助我深入研究树的各种存储结构的特性及其应用。由于课程设计着眼于原理与应用的结合，使我学会把书本上和课堂上学到的知识用于解决实际问题，从而培养了一部分计算机软件工作所需要的动手能力。我通过对Huffman编译码原理的学习，再通过分析、设计、编码、调试等各环节，实现了Huffman编译码器的数据实现和界面实现。在Huffman编译码器数据结构的算法设计中我同时用到了多种技术和方法，如算法设计的构思方法，算法的编码，递归技术，与二叉树和树相关的技术等。从而帮助我深入学习研究了树的各种存储结构的特性及其应用。为了实现界面友好的要求，我决定采用MFC的界面操作，所以必须以C+为基本语言，但是由于学习数据结构课程是基于PASCAL，实验数据结构部分设计遇到一些语法冲突。但是通过课程实践学习，我又开始熟悉C+的编程环境，从而实现了在不同语言上数据结构思想的统一。此次课程设计并没有划定具体题目，包括算法需求都由我们度量，思路开阔。我始终和同学探讨并独立研究新的功能的实现。通过尝试来学习，通过实践去理解。当然，通过多天来的上机实践，我获取了一些心得：一充分准备。由于课题宽泛，很多同学去网上下了界面优良的源程序。相对而言在DOS下编程的我开始时很焦急，不知如何实现界面友好。准备充分是很重要的，为了实现MFC，我重新学习了C+语言。二冷静，耐心投入。集中精力地编程，不被外界影响，使自己的思路始终连贯不被打断。对待每一个错误，都要仔细分析，太过焦急，不仅不能及时的改正错误，还对后面的编程造成影响。三要有一种坚持不懈的毅力，不管自己的程序多么复杂，多么冗长，要坚持不懈的去完成。冷静思考。四要对自己有信心，出错是必然的。“屡战屡败，屡败屡战”，不怕受挫的心理承受能力和从零开始的决心是走向成功的必要条件。五学会与别人学习讨论，但不依赖别人，可以通过借鉴思路从而创新，但决不照搬别人的东西。通过查找资料，我发现我们做Huffman编码和解码时，一般都要在内存通过指针生成Huffman树，这是一个比较费时间、费空间的过程。实际上，真正的Huffman编码程序经常使用其他更快的数据结构来完成树的生成，如散列等。所以我的课题有待继续学习研究。用户手册/使用说明 （图九）1在此处输入要编码的字符串，点击进行编码。2再次输入时再点击可成功使用，不会受之前结果影响。附录(源程序清单)/huffcode.cpp/C编写的源代码，原来含有writef()以及printf(),但由于最终用MFC界面实现，故删去，只作为一/些功能子函数被MFC的对话框类调用。/另外，对于类型申明等已包含于头文件。#include stdafx.h#include huffcode.h/* 统计字符出现的频率 */int statistic_char(char *text, HTree *t) int i, j; int text_len = strlen(text); t-total = 0; for (i=0; itext_len; i+) for (j=0; jtotal; j+) if (t-arrj.ch = texti) t-arrj.weight +; break; if (j=t-total) t-arrt-total.ch = texti; t-arrt-total.weight = 1; t-total +; return t-total;int create_htree(HTree *t) int i; int total_node = t-total * 2 - 1;int min1, min2; /* 权最小的两个结点 */ int min1_i, min2_i; /* 权最小结点对应的编号 */ int leaves = t-total; for (i=0; iarri.parent = -1; t-arri.rchild = -1; t-arri.lchild = -1; while (t-total total_node) min1 = min2 = MAX_WEIGHT; for (i=0; itotal; i+) /* 对每一个结点 */ if (t-arri.parent = -1 /* 结点没有被合并 */ & t-arri.weight arri.weight arri.weight; else min2_i = i; min2 = t-arri.weight; t-arrt-total.weight = min1 + min2; t-arrt-total.parent = -1; t-arrmin1_i.parent = t-total; t-arrmin2_i.parent = t-total; t-arrt-total.ch = ; t-total +; return 0;/* 对哈夫曼树进行编码 */void coding(HTree *t, int head_i, char *code) if ( head_i = -1) return; if (t-arrhead_i.lchild = -1 & t-arrhead_i.rchild = -1) strcpy(t-arrhead_i.code, code);/ else int len = strlen(code); strcat(code, 0); coding(t, t-arrhead_i.lchild, code); codelen = 1; coding(t, t-arrhead_i.rchild, code); codelen = 0; /* 对字符进行编码 */void code_string(char *text, HTree *t,char *codes) int i, j, text_len = strlen(text); int n = 0; for (i=0; itext_len; i+) char ch = texti; for (j=0; jtotal; j+) if (ch = t-arrj.ch) strcat(codes, t-arrj.code); break; / DlgString.cpp /作为执行文件，通过MFC的可视化界面实现HuffMan编译码器#include stdafx.h#include iostream.h#include string.h#include math.h#include HUFFMANTREE.h#include DlgString.h#include huffcode.h#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE = _FILE_;#endifCDlgString:CDlgString(CWnd* pParent /*=NULL*/): CDialog(CDlgString:IDD, pParent)/AFX_DATA_INIT(CDlgString)m_inStr = _T();m_outstr = _T();m_wpl = _T();m_number = _T();/AFX_DATA_INITvoid CDlgString:DoDataExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);/AFX_DATA_MAP(CDlgString)DDX_Control(pDX, IDC_LIST1, m_chars);DDX_Text(pDX, IDC_EDIT_STR, m_inStr);DDX_Text(pDX, IDC_STATIC_OUT, m_outstr);DDX_Text(pDX, IDC_STATIC_WPL, m_wpl);DDX_Text(pDX, IDC_STATIC_NUM, m_number);/AFX_DATA_MAPBEGIN_MESSAGE_MAP(CDlgString, CDialog)/AFX_MSG_MAP(CDlgString)ON_NOTIFY(NM_CLICK, IDC_LIST1, OnClickList1)/AFX_MSG_MAPEND_MESSAGE_MAP()/ CDlgString message handlersvoid CDlgString:OnOK() UpdateData(true);/ TODO: Add extra validation herem_chars.DeleteAllItems();CBrush brush(RGB(225,30,100);CClientDC dc(this);dc.FillRect(CRect(630,10,1050,280),&brush);/ 清屏 int i,ci,n,nn,wpl,len; int x,y,h; HTree t; m_outstr= _T(); int path16=0; char code128 = ; char codes128 = ;CString str; char text128; strcpy(text,m_inStr); n=statistic_char(text, &t);/n用于存储叶子个数 h=(int)(log(n)/log(2)+1); create_htree(&t);/建树 coding(&t, t.total-1, code);/编码 UpdateData(TRUE); wpl=0;for(ci=1;ciSelectObject(&pen);/建笔 x=800;y=20;/ 原始坐标设定pdc-MoveTo(x,y);/每次路径都从同一源点开始str.Format(_T(%c),t.arrci-1.ch);/*对n个叶子的明细输入列表*/nn=m_chars.InsertItem(m_chars.GetItemCount(),str); str.Format(_T(%s),t.arrci-1.code);m_chars.SetItemText(nn,1,str);str.Format(_T(%d),t.arrci-1.weight);m_chars.SetItemText(nn,2,str); len=strlen(t.arrci-1.code);str.Format(_T(%d),len);m_chars.SetItemText(nn,3,str);wpl+=t.arrci-1.weight*len; for(i=0;iLineTo(x,y);pdc-MoveTo(x,y); if(i=len-1)str.Format(_T(%c),t.arrci-1.ch);pdc-TextOut(x,y+10,str);else if(t.arrci-1.codei=1)/向右x=x+8*(h-i+1); pdc-LineTo(x,y);pdc-MoveTo(x,y);if(i=len-1)str.Format(_T(%c),t.arrci-1.ch);pdc-TextOut(x,y+10,str); str.Format(_T(%d),wpl);m_wpl=str;/在对话框上显示最短带权路径str.Format(_T(%d),n);m_number=str;/在对话框上显示不同的编码字符总数UpdateData(false);code_string(text, &t,codes);str.Format(_T(%s),codes);m_outstr=str;/在对话框上输出对应于输入字符串的编码结果UpdateData(false); void CDlgString:OnClickList1(NMHDR* pNM