最优二叉树的产生及哈夫曼编码 湖北汽车工业学院 数据结构课设

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 数据结构 课程 课设目：       最优二叉树的产生       专  业： 班    级: 姓    名： 一、设计题目 最优二叉树的产生及哈夫曼编码 二、设计目的 最优二叉树即哈夫曼树是一类带权路径长度最短的树，在实际生活中有着广泛的应用，例如用于最佳判断过程和通信编码等。因此，通过此次课设，学习如何构建一颗最优二叉树以及通过已经构建的哈夫曼树进行对输入数据的编码。这样可以在进行课设的过程中加深对树形结构的掌握，熟练掌握树的建立，树的遍历等。可以将在书本上学习到的理论知识运用到实际中去，以加深对知识的理解。这样做起来更有成就感。 三、总体设计 1.系统流程设计 系统的功能模块如下图所示： 2.系统模块设计 1）数据读入：构造函数void input_data()，用于通过文件往链表中输入数据。 2）对数据进行排序:构造函数void bubbleSort()，通过冒泡排序对输入的数据进行升序排序 3）构造哈夫曼树:构造函数void Create_Haffman_Tree()，先调用函数void bubbleSort()对输入的数据进行排序，然后再通过函数void Create_Haffman_Tree()来构造哈夫曼树。 4）哈夫曼树的三种遍历:分别构造函数DLR_btree(BT *search)、LDR_btree(BT *search)、LRD_btree(BT *search)实现哈夫曼树的先根、中根、后根遍历。 5）产生哈夫曼编码:构造函数void BianMa()，首先调用函数void Search_node(BT *search,int n)来搜索枝叶节点，然后再通过void BianMa()函数来实现对输入数据的哈夫曼编码 四、详细设计 1.数据结构设计 本程序采用链表的结构来存储输入的数据，并通过链表构造哈夫曼树。示意图如下： 为此，首先声明一个类型为struct BinaryTree的结构体。结构体定义如下： typedef struct BinaryTree    //二叉树的二叉链表 { int data;    //数据域，用于存放数据 struct BinaryTree *lchild;    //左孩子地址域 struct BinaryTree *rchild;    //右孩子地址域 struct BinaryTree *parent;    //父亲地址域 struct BinaryTree *next;    //下个节点的地址域 }BT; 2.模块接口设计 1）所有函数声明如下： void input_data();    //往数组里面输入数据 void output_data();    //输出数组中的数据 void bubbleSort();    //冒泡排序，对输入的数据进行排序 void Create_Haffman_Tree();    //构造哈夫曼树 void DLR_btree(BT *search);    //哈夫曼树的先根遍历 void LDR_btree(BT *search);    //哈夫曼树的中根遍历 void LRD_btree(BT *search);    //哈夫曼树的后根遍历 void topic_explain();    //题目说明菜单 void welcome_interface();    //欢迎界面 void explain();  //说明菜单 void system_menu();    //显示主菜单 void Search_node(BT *search,int n);    //搜索节点 void BianMa();    //哈夫曼编码 2）定义六个全局变量 BT *root;    //定义根节点为全局变量，所有函数都可以使用它 BT *head;        //定义头节点为全局变量，所有函数都可使用它 int code[100];        //用于存放哈夫曼编码 int data1[100];      //用于存放从文件读入的数据，相当于缓存一样的东西，用于筛选数据 int count;        //用于存放输入有效数据的个数 BT *node;        //用于存放搜寻的到的节点 3.以下是几个主要函数的实现过程说明 1）数据输入函数 为了防止文件输入的误操作，即在文件中输入了除数字字符以外的字符，在输入函数中增加了防止误操作的判断语句。如果发现输入的字符中含有除数字以外的字符，则过滤有非数字字符的那部分，即跳过这部分，从下一部分开始读取。具体过程实现如下： 首先定义整型数组data1和temp,其中data1用于接收从 文件输入的所有字符，包括空格和回车键，其做用相当于缓存。temp用于从data1中取出数据，以空格为间隔，即当遇到一个空格时，认为已经读入一个数据，停止读入。然后在判断temp中的字符有没有非数字字符，如果有，则删除temp中的数据，重新在data1中上次读取的地方开始读入数据。如果没有话，就将temp中存储的数字字符通过函数转化为数字输入到链表中。 2）排序函数 排序函数采用的是冒泡排序，与数组中数据排序不同，这次排序的对象是链表，虽然存储的结构发生了变化，但是基本思想没有发生变化。具体过程如下： 定义指针follow和search，follow用于指向需要排序的节点，search用于往后搜索节点来不断与follow进行比较。当follow中的数据比search大的时候，交换数据，交换左孩子，交换右孩子，交换父亲指针的指向。 3）构造哈夫曼函数 定义三个指针newnode、search、follow，newnode为申请的新节点，search指向最小值，follow指向次小值。具体过程如下： 对链表中的数据进行排序之后，令search指向最小值，follow指向次小值。首先令新节点的左孩子指向最小值节点即search,令新节点的右孩子指向次小值节点即follow。然后令新节点的next指向次小值的next，即将新节点接到原链表中去。 然后令最小值的next为空，令次小值的next为空，使两节点脱离原链。然后令最小值和次小值节点的父亲指针指向新节点。在令头节点的next指向新节点，此时search和follow节点完全独立，只连在新节点的左右孩子上。在使新节点的数据等于最小值和次小值的数据的和。至此，一颗树构造完毕。然后将新产生的链表重新排序，排序完毕之后，在重复上述步骤。知道链表中值剩下一个节点为止。 4）哈夫曼树的三种遍历函数 遍历采用的是递归的。具体过程如下： 先根遍历：若二叉树为空，遍历结束。否则，先访问根节点；然后先根遍历根节点的左子树；在先根遍历根节点的右子树。 中根遍历：若二叉树为空，遍历结束。否则，先进行中根遍历根节点的左子树；再访问根节点；再中根遍历根节点的右子树。 后根遍历：若二叉树为空，遍历结束。否则，先进行后根遍历根节点的左子树；再后根遍历根节点的右子树。再访问根节点； 5）哈夫曼编码函数 首先定义指针node、parent。node用于存放寻找的节点，parent指向node的父亲节点。在定义整型组code,用于存放产生的编码。具体过程如下： 用递归遍历的方法寻找的需要编码数据所在叶结点，将这个节点的地址用node保存。然后令parent指向node的上一个节点即父亲节点，在判断node是parent的左孩子还是右孩子，如果是左孩子的话，则往数组code中写0，如果是右孩子，则往数组code中写1。然后令node=node->parent，再重复上述过程。由此从叶结点往根节点前进，直到到根节点，当前数据编码结束，输出数组中的编码。再编码下一个数据，过程和上述一样。 五、设计结果与分析 主菜单： 从文件导入数据： 对数据进行排序： 建立哈夫曼树： 哈夫曼树的三种遍历： 哈夫曼树编码： 退出： 六、总结 总的来说，这次课设对我来说还是有难度的，不像以前写C语言课设的时候感觉那么顺畅。写的时候总感觉很堵，这个估计就是理论知识没学通。不过通过这次课程设计的训练，我感觉C语言的水平比以前上升了好多，起码对指针的运用比以前更好了。本来我的想法是做一个游戏俄罗斯方块的，感觉那个有意思，有能玩，可是询问老师之后发现不行，因为老师的要求是必须要用到栈、队、树、图，无奈，只能放弃了，不过后来想想，俄罗斯方块难度太大了。如果当时我做这个的话，估计现在也不会这么悠闲的在这写报告了。所以我就选了最优二叉树的建立。才开始做的时候感觉没思路，好难。一开始我是想数组做，可是写了一半之后发现写不下去了。无奈之下只能重新换思路了，就换成用链式存储来做，做着做着发现用指针来做这个要比数组做简单多了，虽然期间也出现了很多问题，指针乱飞，可是在VC强大的单步调试下，问题都找出来了，并解决了。所有基本功能就实现了，对输入的建立哈夫曼树。第二天就兴冲冲的拿去给老师验收，本以为能够通过的，可是老师还是找到了一些BUG，并让我用构造的哈夫曼树对输入的数据进行编码，弄完了之后在来找他。没办法，只能回来乖乖的改程序，加功能。那个BUG到是一会就解决了，可是用哈夫曼树进行编码可把我难住了，期间去请教了老师好多次，原理是弄懂了，可是把转化为语句的话，还是好难。哈夫曼编码就是记录从叶结点回退到根节点走过的路径，如果是左子树，就为0，如果为右子树，就为1。一开始纠结的问题是如何实现这个回退的过程。后来我想到的办法是启用一个父亲指针，这个指针指向该节点的父亲节点。首先通过遍历找到所需编码数据所在的节点，然后只要顺着节点沿着父亲指针一直往上走，类似于链表，直到找到根节点root就停止，期间边走边记录走过的路径，等走到根节点的时候，记录下来的路径就是所谓的哈夫曼编码了。思路是对的，可是在实现的过程老是遇到问题，不断的用单步调试来寻找问题，有好几次以为弄好了，可是换了一组数据之后又不行了，差点没把我弄崩溃，无奈只能一步一步找问题，后来发现基本上都是指针的指向弄错了。最后终于在晚上三点多把所有问题解决了，至此，长叹一口气。最后把程序弄出来之后那种成就感实在是太好了，果然只有在经历困难之后才能见彩虹啊。此次的程序完全是由我自己构建的，没有借鉴他人，一词一句都是通过键盘敲上去的。这才是真正令我满足的原因。总之，通过此次的课设，使我对二叉树的构建有了清晰的认识，知道怎样操作，知道怎样发现问题，怎样解决问题。知道理论运用到实际中才是最好的。最后感谢付老师给我的指导。