数据结构课程设计哈夫曼.doc

#include#include#include#define MAX 99char chaMAX;char hcMAX-1MAX;int s1,s2; /设置全局变量，以便在方法(函数)select中返回两个变量typedef struct /huffman树存储结构unsigned int weight;/权值int lchild,rchild,parent;huftree;void select(huftree tree,int k) /找寻parent为0,权最小的两个节点int i;for (i=1;i=k & treei.parent!=0 ;i+); s1=i;/初始化s1for (i=1;i=k;i+)if (treei.parent=0 & treei.weighttrees1.weight) s1=i;/把最小值赋给s1for (i=1; i=k ; i+)if (treei.parent=0 & i!=s1) break; s2=i;/初始化s2for (i=1;i=k;i+)if ( treei.parent=0 & i!=s1 & treei.weighttrees2.weight) s2=i;/把最小值赋给s2void huffman(huftree tree,int *w,int n) /生成huffman树 int m,i;if (n=1) return;m=2*n-1;for (i=1;i=n;i+)/给tree中每个结点权值赋值，且分别给左右孩子及双亲初始化 treei.weight=wi; treei.parent=0;treei.lchild=0; treei.rchild=0; for (i=n+1;i=m;i+)/给除了叶子结点下的其它结点初始化 treei.weight=0; treei.parent=0;treei.lchild=0; treei.rchild=0; for (i=n+1;i=m;i+)/最终结果 select(tree, i-1);trees1.parent=i;trees2.parent=i;treei.lchild=s1;treei.rchild=s2; treei.weight =trees1. weight+ trees2.weight;void huffmancode(huftree tree,char code,int n)/输出huffman编码int start,c,i,f;cout哈夫曼树：endl;/输出hufftreefor(i=1;i=2*n-1;i+)coutsetw(0)isetw(5)treei.weightsetw(5)treei.parentsetw(5)treei.lchildsetw(5)treei.rchildendl;coden-1=0;/cout哈夫曼编码:endl;for(i=1;i=n;i+)start=n-1;for(c=i,f=treei.parent;f!=0;c=f,f=treef.parent)/输出huffman编码if(treef.lchild=c)code-start=0;/把编码存入codeelse code-start=1;strcpy(hci,&codestart);/把code分别复制给hccoutchaihciendl;/分别输出编码 for是满足条件进入void tohuffmancode(int n)/编码部分int i=0,j;char anychar9999;cout请输入你要编码的字符串:endl;cinanychar;cout编码为:;for (;anychari!=0;i+)j=0;for(;anychari!=chaj&j=n;) j+;if (j=n) couthcj;coutendl;void decode(char ch,huftree tree,int n)/译码int i,j,m;char b;m=2*n-1;i=m;cout请输入编码:endl;cinb;cout译码为:;while(b!=n) /遇到回车时，结束if(b=0)i=treei.lchild;else i=treei.rchild;if(treei.lchild=0)coutchi;j=i,i=m;cin.get(b);if(treej.lchild!=0)coutendlERRORendl;coutendlendl;void main()int i=0,n=0;int *w,weightMAX;char codeMAX;huftree treeMAX;w=weight;char in;while (in!=5)cout * * * * * * 哈夫曼编码 * * * * * * * *endlendl;cout * 1 建立初始化哈夫曼树 * endlendl;cout * 2 输出哈夫曼编码 * endlendl; cout * 3 编码 * endlendl;cout * 4 译码 * endlendl;cout * 5 退出 * endlendl;cout * * * * * * * * * * * * * * * * * * * * endlendl;coutin;coutendl;switch (in)case 1: coutn; cout请输入字符及对应权值:endl;for(i=1;i=n;i+)cout;cinchaiweighti;huffman(tree,w,n); break; /生成huffman树case 2:huffmancode(tree,code,n);break;case 3:tohuffmancode(n);break;case 4:decode(cha,tree,n);break;一、设计题目与要求 【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【内容】1) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；2) 编码：利用建好的哈夫曼树生成哈夫曼编码；3) 输出编码；4) 译码功能5) 显示哈夫曼树；6)二、概要设计 这个设计主要是解决如何将字符进行哈夫曼编和译码的功能,主要分为头节点、select程序、创建哈夫曼树、输出哈夫曼树、输出哈夫曼编码和译码功能。 创建Huffman树原理：假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、，然后将其认为有n棵树的森林，在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树且新树的根结点权值为其左、右子树根结点权值之和，从森林中删除选取的两棵树，并将新树加入森林，一直重复这个过程，最后合成唯一的一个树即为Huffman树；首先要对数进行定义。然后进行初始化，将每个节点的所有指针都标记为-1，m个叶结点的哈夫曼树共有2m-1个结点，然后构造哈夫曼树的m-1个非叶结点，然后查找文件中权值最小的两个结点相结合，用for循环实现最小权值结合，最后构成哈夫曼树。1. select程序是为了寻找最小权值的字符，不断地循环找寻最小权值。2. 创建哈夫曼树是将最小的权值依次相结合成成一个大的二叉树3. 输出哈夫曼树是将二叉树用矩阵的方式表达出来4. 输出哈夫曼编码是将输入的字符用01串的形式表达出来5. 译码功能是将01串的哈夫曼编码在二叉树中的字符输出译码退出开始建立哈夫曼树输出哈夫曼编码编码三、算法设计1、 生成huffman树（流程图如下1.1） 图1.1这是生成哈夫曼树的流程图，节点一共有2n-1个，首先给n个叶子赋值，初始化其余的n-1个节点，然后寻找双亲，再给双亲赋值。在给n个叶子赋值时要先挑选出两棵根节点最小的树最为左右子树构造。新的树的权值是这两个树的权值之和。在生成哈夫曼树之前还有一个寻找最小权值的select函数，这个函数是生成哈夫曼树的一个重要的函数，流程图如下图2.哈夫曼编码的输出（如图）哈夫曼编码的输出是将n-1的节点赋给start，然后经i赋给c，i的双亲则赋值给f，在进行循环的时候，f与c的关系则是f一直都是c的双亲，当f=0的时候则此时的c就是二叉树的根节点，如果左孩子等于c则记为0，如果有孩子是C则记为1，然后根据左零右一的定则依次读取，因为程序的读取是从树的最下端的叶子依次往上读取,所以要反转存储的顺序，将先前的01串从后往前进行读取储存 3.译码译码是根据哈夫曼编码来读取字符，相对于哈夫曼编码的输出是一个反向的过程，首先输入01字符串，然后根据字符串的01的顺序来读取哈夫曼树中的字符。首先输入编码，当编码不为空的时候，如果输入的编码是零则是左孩子，1则是右孩子，如此类推，最后寻找到字符的所在地位置，然后输出字符。如果排定左孩子不等于零，则说明输入的编码错误。四、运行结果和调试分析1.建立和初始化哈夫曼树 在初始化的过程是在寻找最小权值的时候进行的，然后把最小的两个权值分别赋给s1和s2，在这段程序中的对字符与权值的输入