数据结构课程设计-基于哈夫曼树的知识进行编码和译码.doc

数 据 结 构 课 程 设 计设计题目： 基于哈夫曼树的各种遍历操作 - 13 -课题名称基于哈夫曼树的知识进行编码和译码院 系信息工程学院年级专业学 号姓 名成 绩课题设计目的与设计意义1、课题设计目的：遍历二叉树是二叉树的一种重要的运算，作为特殊二叉树的哈夫曼树，遍历这个规律更显得重要。我们知道，遍历一个线性结构很容易，只需从开始结点出发顺序扫描每个结点即可。但是二叉树是一个非线性结构，每个节点可以有两个后继结点，因此，需要寻找一种规律来系统地访问树中各结点。这就需要遍历操作，将每个结点访问一次且仅访问一次。我们就需要熟练的掌握三种遍历方法，解决问题。2、课题设计意义：作为学计算机专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试计算程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。指导教师：年 月 日目 录一、课程设计的目的- 1 -二、课程设计内容及要求- 1 -三、需求分析- 1 -四、课程设计分析- 1 -（1）流程图- 3 -五、系统实现- 3 -（1）主调函数- 3 -(2)建立哈夫曼树- 4 -（3）先序输出- 5 -（4）中序输出- 5 -（5）后序输出- 5 -（6）结点总数- 5 -（7）哈夫曼树的深度- 6 -（8）叶子结点数- 6 -六、系统调试- 7 -（1）进入主界面- 7 -（2）建立哈夫曼树- 7 -（3）先序输出- 8 -（4）中序输出- 8 -（5）后序输出- 9 -七、结束语- 9 -附录、源程序- 10 -参考文献- 13 -一、课程设计的目的在当今这个科技飞速发展的时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。我们着手课程设计就是为了锻炼自己的动手能力，熟练掌握并运用这一技能，更好的服务于社会。在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试计算程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。二、课程设计内容及要求课程设计其主要内容就是对一个课题从提出，把可用条件根据具体思路按照解题逻辑进行组合，在进行进一步的深入，亦步亦趋，系统的把问题按步骤分块解决。作为学计算机专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。三、需求分析问题描述：（1） 前序遍历算法为： PREORDER(t) Bitree *t; if(t) Printf(“t% cn”,t-data); PREORDER(t-lchild); PREORDER(t-rchild); (2) 中序遍历算法为： INORDER(t) Bitree *t; if(t)INORDER(t-lchild);Printf(“t%cn”,t-data);INORDER(t-rchild); (3) 后序遍历算法为： POSTORDER(t) bitree *t if(t) POSTORDER(t-lchild); POSTORDER(t-rchild); 4、 课程设计分析（1）流程图建哈夫曼树先序输出中序输出 后序输出结点总数树的深度叶子结点数图4.1流程图五、系统实现（1）主调函数void main()bitree root,*bt;int i=1,depth,k,t;while(i)printf(0:创建二叉树n1:先序输出n2:中序输出n3:后序输出n4:结点总数n5:二叉树的深度n6:叶子结点数n); scanf(%d,&i);switch(i)case 0:bt=creatbitree(&root); break;case 1:printf(先序输出后的结果为:); preorder(bt); break;case 2:printf(中序输出后的结果为:); inorder(bt); break;case 3:printf(先序输出后的结果为:); postorder(bt); break;case 4:k=nodenum(bt); printf(结点总数为:%d,k); break;case 5:depth=depthtree(bt); printf(二叉树的深度为:%dn,depth); break;case 6:t=leafnum(bt); printf(叶子结点数为:%d,t); break;printf(n0:结束n1:继续n);scanf(%d,&i);(2)建立哈夫曼树bitree *creatbitree(bitree *root)char ch;int i,j;bitree *s,*p20;printf(请输入位置和元素:n);scanf(%d%c,&i,&ch);while(i)s=(bitree *)malloc(sizeof(bitree);s-data=ch;s-lchild=NULL; s-rchild=NULL;pi=s;if(i=1)root=s;elsej=i/2;if(i%2=0)pj-lchild=s;elsepj-rchild=s; scanf(%d%c,&i,&ch);return root;（3）先序输出void preorder(bitree *bt)if(bt!=NULL)printf(%c,bt-data);preorder(bt-lchild);preorder(bt-rchild);（4）中序输出void inorder(bitree *bt) if(bt!=NULL)inorder(bt-lchild);printf(%c,bt-data);inorder(bt-rchild);（5）后序输出void postorder(bitree *bt) if(bt!=NULL)postorder(bt-lchild);postorder(bt-rchild); printf(%c,bt-data);（6）结点总数int nodenum(bitree *bt)if(bt=NULL)return 0;elsereturn (1+nodenum(bt-lchild)+nodenum(bt-rchild);（7）哈夫曼树的深度int depthtree(bitree *bt)if(bt)int max,hl,hr;hl=depthtree(bt-lchild); hr=depthtree(bt-rchild); max=hlhr? hl:hr; return (1+max);else return 0;（8）叶子结点数int leafnum(bitree *bt)int lnode,rnode; if(bt=NULL)return 0;elseif(bt-lchild=NULL&bt-rchild=NULL)return 1;else lnode=leafnum(bt-lchild); rnode=leafnum(bt-rchild); return lnode+rnode;六、系统调试（1）进入主界面图6.1进入主界面（2）建立哈夫曼树 图6.2建立哈夫曼树（3）先序输出图6.3先序输出（4）中序输出图6.4中序输出（5）后序输出 图6.5后序输出七、结束语 程序分析： 本次哈夫曼编码译码器的课程实验做得还算成功，不仅仅在于程序能够正常运行，实现应有的功能，关键在于过程，在于小组成员的分工合作和一起纠错排错的过程，在完成程序的过程中才能真正理解面向对象和模块化设计的思想，关键在于这些函数代表的是一个个功能模块，任何一个模块出现问题或者模块之间的衔接出现问题都将导致程序运行的失败。哈夫曼编码译码器课程实验我完成了建立哈夫曼树，及对哈夫曼数的编码和译码功能结构体和类型的定义，以及void函数，HUFMCODE函数，DECODE函数的实现。在初始设计的时候，我体会到书写流程图的重要性，只有又一个清晰的设计思路才能事半功倍，分工明确，避免无效劳动或者在错误的编程方向上走弯路，也让大家明白自己在程序设计中的位置和职责。初始的创建是哈夫曼编码译码系统成功的关键，输出接点字符或者权重信息，作为检验，对验证和纠错起到了非常大的作用。在适当的地方调用它们，运行时可以看到验证编写程序的正确性； 实验心得：通过这段时间的课程设计使我对哈夫曼树以及哈夫曼编码和译码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。首先我谈谈我在设计期间我遇到的难点。开始的时候，代码中有许多的错误，特别是有一个“无法找到文件”的错误让我束手无策，最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时，由于对文件不是太熟悉，只好翻开C语言书本仿照其模式编写，但后来进入了死循环，最后的解决方式是把main函数里的一个dowhile循环去掉。许多的错误让我明白了一个道理-细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。这次课程设计不但让我学得了一些编程知识，还学会了系统的做一份课程设计报告，学会了如何截图，学会了如何更好的画流程图，明白了做事情只有认真，才能真正做得更好！ 通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，这主要是平时实践太少的缘故。我想，在未来的暑假中，我会努力尝试编写一些程序。虽然我们信息管理专业的学生，但现在编程的能力太差了，毕竟多精通一门技术总是好事。在这个程序中，还有许多地方值得完善。比如，读出文本只能是大写的文档，空格和小写不能识别，更不用说是任意的ASC码字符了。由于时间问题，暂时不能实现了。我想在暑假里好好研究这个问题。附录、源程序#include#includetypedef char datatype;typedef struct nodedatatype data;struct node *lchild,*rchild;bitree;bitree *root;bitree *creatbitree(bitree *root)char ch;int i,j;bitree *s,*p20;printf(请输入位置和元素:n);scanf(%d%c,&i,&ch);while(i)s=(bitree *)malloc(sizeof(bitree);s-data=ch;s-lchild=NULL; s-rchild=NULL;pi=s;if(i=1)root=s;elsej=i/2;if(i%2=0)pj-lchild=s;elsepj-rchild=s; scanf(%d%c,&i,&ch);return root;void preorder(bitree *bt)if(bt!=NULL)printf(%c,bt-data);preorder(bt-lchild);preorder(bt-rchild);void inorder(bitree *bt) if(bt!=NULL)inorder(bt-lchild);printf(%c,bt-data);inorder(bt-rchild);void postorder(bitree *bt) if(bt!=NULL)postorder(bt-lchild);postorder(bt-rchild); printf(%c,bt-data);int nodenum(bitree *bt)if(bt=NULL)return 0;elsereturn (1+nodenum(bt-lchild)+nodenum(bt-rchild);int depthtree(bitree *bt)if(bt)int max,hl,hr;hl=depthtree(bt-lchild); hr=depthtree(bt-rchild); max=hlhr? hl:hr; return (1+max);else return 0;int leafnum(bitree *bt)int lnode,rnode; if(bt=NULL)return 0;elseif(bt-lchild=NULL&bt-rchild=NULL)return 1;else lnode=leafnum(bt-lchild);