还剩27页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据构造》课程设计汇报题目Huff Man编码器混合串:
3.(图七)输入复杂无规则长串:
4.(图八)六.课程设计小结(心得体会、存在问题、改善措施)本次程序设计使我不仅深化理解了教学内容,深入提高灵活运用数据构造、算法和程序设计技术的能力,并且在总体分析、总体构造设计、算法设计、程序设计、上机I操作及程序调试等基本技能方面受到了综合训练本次试验我选择编译码器日勺课题协助我深入研究树日勺多种存储构造的特Huffman性及其应用由于课程设计着眼于原理与应用日勺结合,使我学会把书本上和课堂上学到的I知识用于处理实际问题,从而培养了一部分计算机软件工作所需要的动手能力J我通过对编译码原理的学习,再通过度析、设计、编码、调试等各环节,实Huffman现了编译码器的;数据实现和界面实现在编译码器数据构造的算法设计中Huffman Huffman我同步用到了多种技术和措施,如算法设计的构思措施,算法的编码,递归技术,与二叉树和树有关的技术等从而协助我深入学习研究了树的多种存储构造的特性及其应用为了实现界面友好的规定,我决定采用的界面操作,因此必须以为基本语言,MFC C++不过由于学习数据构造课程是基于试验数据构造部分设计碰到某些语法冲突不过PASCAL,通过课程实践学习,我又开始熟悉的编程环境,从而实现了在不一样语言上数据构造思C++I想的统一本次课程设计并没有划定详细题目,包括算法需求都由我们度量,思绪开阔我一直和同学探讨并独立研究新的功能的实现通过尝试来学习,通过实践去理解当然,通过多天来的上机实践,我获取了某些心得一.充足准备由于课题宽泛,诸多同学去网上下了界面优良的源程序相对而言在DOS下编程日勺我开始时很焦急,不知怎样实现界面友好准备充足是很重要的,为了实现MFC,我重新学习了语言C++二.冷静,耐心投入集中精力地编程,不被外界影响,使自己的思绪一直连贯不被打断看待每一种错误,都要仔细分析,太过焦急,不仅不能及时的改正错误,还对背面的编程导致影响I三.要有一种坚持不懈的毅力,不管自己的程序多么复杂,多么冗长,要坚持不懈的去完毕冷静思索四.要对自己有信心,出错是必然的“屡战屡败,屡败屡战,不怕受挫的心理承受能力和从零开始的决心是走向成功的必要条件五.学会与他人学习讨论,但不依赖他人,可以通过借鉴思绪从而创新,但决不照搬他人的东西通过查找资料,我发现我们做编码和解码时,一般都要在内存通过指针生成Huffman Huffman树,这是一种比较费时间、费空间欧过程实际上,真正的编码程序常常使用其他I IHuffman更快的数据构造来完毕树的生成,如散列等因此我的课题有待继续学习研究•顾客手册/使用阐明镯入字符串笑诏年吉给八娶纳石当年字衿率7京.占.击上匕攵匕迸彳亍纳石马|经的石当,彳导至,」字将串(图九)在此处输入要编码的字符串,点击进行编码
1.再次输入时再点击可成功使用,不会受之前成果影响
2.•附录源程序清单//huffcode.cpp〃编写的源代码,本来具有以及但由于最终用界面实现,故删去,writef printf,MFC只作为一〃些功能子函数被的对话框类调用MFC〃此外,对于类型申明等已包括于头文献#include stdafx.h#include huffcode.h/*记录字符出现的频率*/int statistic_charchar*text,HTree*t{int i,j;int textjen=strlentext;t-total=0;for i=0;itext_len;i++for j=0;jt-total;j++if t-arr[j].ch==text[i]break;if j==t-total{t-arr[t-total].ch=text[i];t-an*[t-total].weight=1;t-total++;return t-total;}int create_htreeHTree*tint i;int total_node=t-total*2-1;权最小的两个结点*/int mini,min2;/*J权最小结点对应的编号*/int minlj,min2_i;/*int leaves=t-total;for i=0;ileaves;i++{t-arr[i].rchild=-1;t-arr[i].lchild=-1;while t-totaltotal_node{mini=min2=MAX WEIGHT;对每一种结点*/for i=0;it-total;i++{/*结点没有被合并*/if t-arr[i].parent==-1/*结点的权比最小权小*/t-arr[i].weightmin2{/*假如它比最小的结点还小*/if t-arr[i].weightmini{/*min2_i=minl_i;min2=min1;二二minl_i i;mini t-arrlij.weight;elsemin2_i=i;min2=t-arr[i].weight;}t-arr[t-total].weight=mini+min2;t-arr[t-total].parent=-1;t-arr[min2_i].parent=t-total;t-arr[t-total].ch=t-total++;return0;/*对哈夫曼树进行编码刃void codingHTree*t,int head_i,char*codeifhead_i==-1return;if t-arr[head_i].lchild==-1t-arr[head_i].rchild==-1{strcpyt-arr[head_i].code,code;/}else{int len=strlencode;strcatcode,n0n;codingt,t-arr[head_i].lchild,code;code[len]=T;codingt,t-arr[head_i].rchild,code;code[len]=0;/*对字符进行编码*/void code__stringchar*text,HTree*t,char*codesint i,j,text_len=strlentext;int n=0;for i=0;itext_len;i++{char ch=textfi];for j=0;jt-total;j++if ch==t-arr[j].ch{strcatcodes,t-arr[j].code;break;//DlgString.cpp〃作为执行文献,通过的可视化界面实现编译码器MFC HuffMan#include stdafx.h#include niostream.hn#include Mstring.hH#include math.hinclude“HUFFMANTREE.h#include HDlgString.hn#include huffcode.h#ifdef.DEBUG#define newDEBUG_NEW#undefTHIS_FILEstatic charTHIS_FILE[]=_FILE_;#endifCDlgString::CDlgStringCWnd*pParent C=NULL*/:CDialogCDlgString::IDD,pParent」//{{AFX_DATA NITCDlgStringmJnStr=_T,M,;m_outstr=_T”;m_wpl=_T»;m_number=_Tnn;//}}AFX_DATA_INITvoid CDlgStringzDoDataExchangeCCDataExchange*pDXCDialog::DoDataExchangepDX;//{{AFX_DATA_MAPCDlgStringDDX_ControlpDX,IDC_LIST1,m_chars;DDX_TextpDX,IDC_EDIT_STR,m_inStr;DDX_TextpDX,IDC_STATIC_OUT,m_outstr;DDX_TextpDX,IDC_STATIC_WPL,m_wpl;DDX_TextpDX,IDC_STATIC_NUM,m_number;//}}AFX_DATA_MAP}BEGIN_MESSAGE_MAPCDlgString,CDialog//{{AFX_MSG_MAPCDlgStringON_NOTIFYNM_CLICK,IDC_LIST1,OnClickListl//}}AFX_MSG_MAPEND_MESSAGE_MAP//CDlgString messagehandlersvoid CDlgString::OnOKUpdateDatatrue;//TODO:Add extravalidation here一,问题描述二.基本规定(需求分析)三.概要设计(设计思想、实现措施、模块设计)・详细设计(数据构造设计、算法设计、算法分析)五.测试数据及测试成果六.课程设计小结(心得体会、存在问题、改善措施)一.问题描述m_chars.DeleteAHItems;CBrush brushRGB225,30,100;CClientDC dcthis;清屏dc.FillRectCRect630,l0,1050,280,brush;//int i,ci,n,nn,wpl,len;int x,y,h;HTree t;m_outstr=_Tn;int path
[16]={0};char code
[128]=”;char codes
[128]=CString str;char text
[128];strcpytext,m_inStr;用于存储叶子个数n=statistic_chartext,t;//nh=intlogn/log2+1;〃建树create_htreet;〃编码codingt,t.totaLl,code;UpdateDataTRUE;wpl=0;forci=1;civ=n;ci++CClientDC*pdc=new CClientDCthis;CPen pen;pen.CreatePenPS_SOLID,1,RGB225,250,250;〃建笔CPen*oldpen=CPen*pdc-SelectObjectpen;原始坐标设定x=800;y=20;〃〃每次途径都从同一源点开始pdc-MoveTox,y;对个叶子的明细输入列表*/str.Format_T”%c,t.arr[ci-l].ch;/*nnn=m_chars.InsertItemm_chars.GetItemCount,str;str.Format_TH%sH,t.arr[ci-1].code;m_chars.Set!temTextnn,1,str;str.Format_TH%d,,t.arr[ci-l],weight;m_chars.SetItemTextnn,2,str;len=strlent.arr[ci-1].code;str.Format_Tn%dn,len;m_chars.SetItemTextnn,3,str;wpl+=t.arr[ci-l].weight*len;对个叶子的编码途径画图,此处循环完毕一种叶子的途径*/fori=0;ilen;i++/*ny=y+50;〃向左ift.arr[ci-1].code[i]==,0,x=x-8*h-i+l;pdc-LineTox,y;pdc-MoveTox,y;ifi==len-l{str.Format_Tn%cn,t.arr[ci-l].ch;pdc-TextOutx,y+10,str;}else ift.arr[ci-1].code[i]==,1!{〃向右x=x+8*h-i+l;pdc-LineTox,y;pdc-MoveTox,y;ifi==len-l{str.Format_Tn%cn,t.arr|ci-l].ch;pdc-TextOutx,y+10,str;}str.Format_Tn%dn,wpl;〃在对话框上显示最短带权途径m_wpl=str;str.FormatLTn%dn,n;〃在对话框上显示不一样的编码字符总数m_number=str;UpdateDatafalse;code_stringtext,t,codes;str.Format_TH%sn,codes;〃在对话框上输出对应于输入字符串的编码成果m_outstr=str;UpdateDatafalse;void CDlgString::OnClickListlNMHDR*pNMHDR,LRESULT*pResult//TODO:Add yourcontrol notificationhandler codehere*pResuIt=0;}〃列表初始化BOOL CDlgString::OnInitDialogCDialog::OnInitDialog;m_font.CreateFontl7,0,0,0,FW_BLACK,0,0,0,DEFAULT_CHARSET,OUT_CHARACTER_PRECIS,CLIP_CHARACTER_PRECIS,DEFAULT_QUALITY,DEFAULT_PITCH|FF_DONTCARE,Courier New”;m_chars.SetFontm_font;m_chars.SetExtendedStyleLVS_EX_FULLROWSELECT|LVS_EX_GRIDLINES;m_chars.SetBkColorRGB100,000,100;m_chars.SetTextColorRGB255,255,255;m_chars.SetTextBkColorRGB150,010,200;字符,m_chars.InsertColumn0,“LVCFMT_CENTER,50;编码m_chars.InsertColumn(l,““,LVCFMT_CENTER,100);频度(权)”,m_chars.InsertColumn(2,”LVCFMT_LEFT,95);途径长度”,m_chars.InsertColumn(3,”LVCFMT_LEFT,95);return TRUE;//return TRUEunless youset thefocus toa control//EXCEPTION:OCX PropertyPages shouldreturn FALSE)运用哈夫曼编码进行通信可以大大提高信道运用率,缩短信息传播时间,减少传播成本不过,这规定在发送端通过一种编码系统看待传数据预先编码,在接受端将传来的数据进行译I码(复原)对于双工信道(即可以双向传播信息的信道),每端都需要一种完整的编/译码系统试为这样日勺信息收发站写一种哈夫曼码日勺编/译码系统二基本规定(需求分析)一种完整的系统应具有如下功能:()初始化()从终端读入字符集大小以及个字符和个权值,建立1I:Initialization n,n n哈夫曼树,并将它存于文献中hfmTree()编码()运用已建好的哈夫曼树(如不在内存,则从文献中读入),2E:Encoding I hfmTree对文献中日勺正文进行编码,然后将成果存入文献中ToBeTran CodeFile()译码()运用已建好的哈夫曼树将文献中的代码进行译码,成果存3D:Decoding CodeFile入文献中TextFile()印代码文献()将文献以紧凑格式显示在终端上,每行个代码4P:Print CodeFile50同步将此字符形式日勺编码文献写入文献中CodePrin()印哈夫曼树()将已在内存中的哈夫曼树以直观的方式(树或凹入表形5T:Tree printingI式)显示在终端上,同步将此字符形式的哈夫曼树写入文献中I TreePrint[测试数据]用下表给出的字符集和频度的实际记录数据建立哈夫曼树,并实现如下报文的编码和译码I“THIS PROGRAMIS MYFAVORITE字符空格ABCDEFGHI频度1866413223210321154757153220字符N OPQRSTUVWXYZ频度[实现提醒]5763151485180238181161编码成果以文本方式存储在文献中1CodeFile顾客界面可以设计为“菜单”方式显示上述功能符号,再加上表达退出运行请2“Q”,Quito顾客键入一种选择功能符此功能执行完毕后再显示此菜单,直至某次顾客选择了为止“Q”在程序时一次执行过程中,第一次执行或命令之后,哈夫曼树已经在内存了,不必再3I,D C读入每次执行中不一定执行命令,由于文献也许早已建好IhfmTree三.概要设计设计思想、实现措施、模块设计哈夫曼编码是一种效率比较高的变长无失真信源编码措施,它的平均码长最短,因此是最佳编码我采用二进制哈夫曼编码设计思想
1.原理构造一种码树编码环节b将信源符号按概率从大到小日勺次序排列,为以便起见,令1pxl2px22pxno对概率最小的两个信源符号求其概率之和,同步给两个符号分别赋予码元2“0”和将“概率之和”当作一种新符号的概率,与剩余符号的概率一起,形成一种缩减信源,“1”成果得到一种只包括个信源符号的新信源,称为信源的第一次缩减信源,用表达n-1S1将缩减信源的符号仍按概率从大到小的次序排列,反复环节得到只含个符号3S12,n-2的缩减信源S2反复上述环节,直至缩减信源只剩余两个符号为止,此时所剩两个符号的概率之和必4为lo按上述环节实际上构造了一种码树,从树根到端点通过的树枝即为码字5实现措施
2.第一,哈夫曼编码实际上构造了一种码树,码树从最上层的端点开始构造,直到树根束,最终得到一种横放的码树,因此,编出的码是即时码J I第二,哈夫曼编码采用概率匹配措施来决定各码字的码长,概率大的符号对应于短码,概率小的符号对应于长码,从而使平均码长最小第三,每次对概率最小的两个符号求概率之和形成缩减信源时,就构造出两个树枝,由于给两个树枝赋码元时是任意日勺,因此编出日勺码字并不惟一模块设计
3.N:WPL:I进入的操作界面:
1.HUFFMAN树(图一)输入字符串,及编码成果
2.镯入字符串绢诏三吉给八室组石当的字衿弟(图二)记录不一样字符数及带权途径长度
3.N:WPL:(图三)(图四)各字符编码明细
4.U!详细设计(数据构造设计、算法设计、算法分析)
(一)数据构造设计)结点类型1//huffcode.cpptypedef structHaffmanTreeNode{char ch,code
[15];int weight;int parent,Ichild,rchild;}HTNode,^HaTree;typedef struct{HTNode arr[MAX_NODE];int total;}HTree;基本操作2int statistic_charchar HTree*t;int create_htreeHTree*t;void codingHTree*t,int head_i,char*code;void print_htree_ldrHTree inthead_i,int deep,int*path;void code_stringchar*text,HTree*t,char*codes;二算法设计在哈夫曼编码过程中,对缩减信源符号按概率由大到小的次序重新排列时,应使合并后的新符号尽量排在靠前的位置,这样可使合并后欧新符号反复编码次数减少,使短码得到充足I运用三算法分析有效的信源编码可获得很好日勺冗余压缩效果1()有效日勺信源编码可使输出码元概率均匀2化
4.测试数据及测试成果输入简短英文字符串
1.(图五)输入数字英文混合串:
2.(图六)。