哈夫曼编码译码器.doc

软件综合课程设计 哈夫曼编码/译码器二叉排序树的实现二一四 年 六 月二叉排序树的实现一、 内容 用顺序和二叉链表作存储结构 1) 以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；2) 对二叉排序树T作中序遍历，输出结果；3) 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；二、 程序代码#include #include #define MAX 64 /规定树中结点的最大数目typedefstruct node /定义数据结构intltag,rtag; /表示child域指示该结点是否孩子char data; /记录结点的数据struct node *lchild; /记录左右孩子的指针struct node *rchild;TBtree;TBtree *QueMAX; /建队，保存已输入的结点的地址TBtree *CreatTree() /建树函数，返回根指针charch;intfront,rear;TBtree *T,*s;T=NULL;front=1;rear=0; /置空二叉树printf(进行初始化，创建二叉树(按满二叉树序号顺序输入，中间的虚节点用表示,#结束)n);ch=getchar(); /输入第一个字符while(ch!=#) /判断是否为结束字符s=NULL;if(ch!=) /判断是否为虚结点s=(TBtree *)malloc(sizeof(TBtree);s-data=ch;s-lchild=NULL;s-rchild=NULL;s-rtag=0;s-ltag=0;rear+;Querear=s; /将结点地址加入队列中if(rear=1)T=s; /输入为第一个结点为根结点elseif(s!=NULL&Quefront!=NULL) /孩子和双亲结点均不是虚结点if(rear%2=0)Quefront-lchild=s;elseQuefront-rchild=s;if(rear%2=1)front+;ch=getchar();return T;void Inorder(TBtree *T) /中序遍历if(T!=NULL)if(T-ltag!=1)Inorder(T-lchild);printf(%c,T-data);if(T-rtag!=1)Inorder(T-rchild);TBtree *pre=NULL;void PreThread(TBtree *root) /中序线索化算法，函数实现TBtree *p;p=root;if(p) PreThread(p-lchild);/线索化左子树if(pre&pre-rtag=1)pre-rchild=p; /前驱结点后继线索化if(p-lchild=NULL)p-ltag=1;p-lchild=pre;if(p-rchild=NULL) /后继结点前驱线索化p-rtag=1;pre=p;PreThread(p-rchild);void PrintIndex(TBtree *t) /输出线索TBtree *f;f=t;if(f)if(f-ltag=1&f-lchild=NULL&f-rtag=1)printf(【%c】,f-data); /如果是第一个结点if(f-ltag=1&f-lchild!=NULL)printf(%c【%c】,f-lchild-data,f-data); /如果此结点有前驱就输出前驱和此结点if(f-ltag=1&f-rtag=1&f-rchild!=NULL)printf(%c,f-rchild-data); /如果此结点有前驱也有后继，就输出后继else if(f-rtag=1&f-rchild!=NULL)printf(【%c】%c,f-data,f-rchild-data);/如果没有前驱，就输出此结点和后继printf(n);if(f-ltag!=1)PrintIndex(f-lchild);if(f-rtag!=1)PrintIndex(f-rchild);TBtree *SearchChild(TBtree *point,charfindnode) /查找孩子结点函数TBtree *point1,*point2;if(point!=NULL) if(point-data=findnode) return point;elseif(point-ltag!=1)point1=SearchChild(point-lchild,findnode);if(point1!=NULL)return point1;if(point-rtag!=1) point2=SearchChild(point-rchild,findnode);if(point2!=NULL)return point2; return NULL; return NULL;TBtree *SearchPre(TBtree *point,TBtree *child) /查找父亲结点函数TBtree *point1,*point2;if(point!=NULL) if(point-ltag!=1&point-lchild=child)|(point-rtag!=1&point-rchild=child) return point;elseif(point-ltag!=1) point1=SearchPre(point-lchild,child);if(point1!=NULL)return point1; if(point-rtag!=1) point2=SearchPre(point-rchild,child);if(point2!=NULL)return point2; return NULL; elsereturn NULL;void Insert(TBtree *root)charch;char c;TBtree *p1,*child;printf(请输入要插入的结点的信息:);scanf(%c,&c);scanf(%c,&c); p1=(TBtree *)malloc(sizeof(TBtree); /插入的结点信息p1-data=c;p1-lchild=NULL;p1-rchild=NULL;p1-rtag=0;p1-ltag=0;printf(输入查找的结点信息:);scanf(%c,&ch);scanf(%c,&ch);child=SearchChild(root,ch); /查孩子结点的地址if(child=NULL)printf(没有找到结点n);return ;else printf(发现结点%cn,child-data);if(child-ltag=0) /当孩子结点有左孩子的时候/p2=child;child=child-lchild;while(child-rchild&child-rtag=0) /找到左子树下，最右结点child=child-rchild;printf(发现结点%cn,child-data);p1-rchild=child-rchild; /后继化p1-rtag=1;child-rtag=0;child-rchild=p1; /连接p1-lchild=child; /前驱化p1-ltag=1;else /当孩子结点没有左孩子的时候p1-lchild=child-lchild; /前驱化child-ltag=0;p1-ltag=1;child-lchild=p1;p1-rchild=child;p1-rtag=1;printf(n插入结点操作已经完成，并同时完成了线索化的恢复n);voidDeleteNode(TBtree *t)TBtree *child,*pre,*s,*q;charch;printf(输入查找的结点信息:);ch=getchar();ch=getchar();child=SearchChild(t,ch);printf(发现结点:%cn,child-data);printf(ltag=%d,rtag=%dn,child-ltag,child-rtag);pre=SearchPre(t,child);printf(发现结点:%cn,pre-data);if(NULL=child)printf(没有找到结点:);return;system(pause); if(child=pre-lchild|child=pre) /是父亲结点的左孩子if(1=child-ltag&1=child-rtag)/孩子结点无左右pre-lchild=child-lchild;pre-ltag=1;if(child-lchild!=NULL)if(child-lchild-rtag=1)child-lchild-rchild=pre;free(child);else if(1!=child-ltag&1=child-rtag)/孩子结点有左无右pre-lchild=child-lchild; s=child-lchild;while(s-rchild&s-rtag!=1)s=s-rchild;s-rchild=child-rchild;free(child);else if(1=child-ltag&1!=child-rtag)/孩子结点有右无左pre-lchild=child-rchild;s=child-rchild;while(s-lchild&s-ltag!=1)/查找左子树最左下点s=s-lchild;s-lchild=child-lchild;if(child-lchild!=NULL)if(child-lchild-rtag=1)child-lchild-rchild=pre;free(child); else if(1!=child-ltag&1!=child-rtag)/孩子结点左右都有 pre-lchild=child-lchild;s=child-rchild;while(s-lchild&s-ltag!=1)/右子树的左下s=s-lchild;q=child-lchild;while(q-rchild&q-rtag!=1)/左子树的右下q=q-rchild;q-rchild=child-rchild;q-rtag=0;s-lchild=q;free(child); if(child=pre-rchild) /是父亲结点的右孩子if(1=child-ltag&1=child-rtag)/孩子结点无左右pre-rchild=child-rchild;pre-rtag=1;if(child-rchild!=NULL)if(child-rchild-ltag=1)child-rchild-lchild=pre;free(child);else if(1!=child-ltag&1=child-rtag)/孩子结点有左无右pre-rchild=child-lchild;s=child-lchild;while(s-rchild&s-rtag!=1)s=s-rchild;s-rchild=child-rchild;if(child-rchild!=NULL)if(child-rchild-ltag=1)child-rchild-lchild=pre;free(child);else if(1=child-ltag&1!=child-rtag)/孩子结点有右无左pre-rchild=child-rchild;s=child-rchild;while(s-lchild&s-ltag!=1)s=s-lchild;s-lchild=child-lchild;free(child);else if(1!=child-ltag&1!=child-rtag)/孩子结点左右都有pre-rchild=child-rchild;s=child-rchild;while(s-lchild&s-ltag!=1)/右子树的左下s=s-lchild;q=child-lchild;while(q-rchild&q-rtag!=1)/左子树的右下q=q-rchild;s-lchild=child-lchild;s-ltag=0;q-rchild=s;free(child);printf(n删除结点操作已经完成，并同时完成了线索化的恢复n);printf(find %c,child-data);return;int main(void)TBtree *T;inti;T=CreatTree();printf(n);i=1;while(i)printf(t1.二叉树的线索化n);printf(t2.线索二叉树插入操作n);printf(t3.线索二叉树删除操作n);printf(t4.中序输出n);printf(t5.线索输出n);printf(t0.退出n);printf(t 请选择:);scanf(%d,&i);printf(n);switch(i)case 1:PreThread(T);printf(t已经实现二叉树的线索化n);printf(n);break;case 2:Insert(T);printf(n);break;case 3:DeleteNode(T);printf(n);break;case 4:Inorder(T);printf(n);break;case 5:PrintIndex(T);break;case 0:exit(1);default:printf(errornt请继续选择:);return 0;三运行结果二叉树创建：二叉树线索化：线索二叉树插入结点：线索二叉树删除结点：四、设计总结通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。我觉得作为一名计算机工程专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。在设计时首先要端正心态，忌焦忌燥，而且要会运用软件工程的思想，说白了就是先构思轮廓，别先急着写代码，要不然会一直修改，越改越乱，越乱越心烦，越心烦越完不成，而且在调试查错的时候不要急，要静下心来慢慢找，什么东西越急越弄不成，慢慢改，一步一步来，通过这次课程设计也让我对数据结构的了解以及掌握更进一步，扎实了基础，受益良多。哈夫曼编码/译码器一、内容：哈夫曼编码/译码器【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。 【基本要求】1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符 空格 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)译码功能；2)显示哈夫曼树；3)界面设计的优化。二、需求分析 哈夫曼编码是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码是使用一张特殊的编码表将源字符进行编码。这张编码表的特殊之处在于，这是根据每一个源字符出现的估算概率而建立起来的。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”和“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进制的代码，输入二进制代码时可以编译成字符串。三、概要设计1.哈夫曼树的定义在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最佳二叉树，也称为哈夫曼树。2哈夫曼树的构造假设在N个权值，则构造出的哈夫曼树有N个叶子结点。N个权值分别为W1，W2，Wn,则哈夫曼树的构造规则为：（1）将W1，W2，Wn看成有N棵树的森林；（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点为其左、右子树结点权值之和；（3）从森林中删除选取的两棵树，并将新树加入森林；（4）重复（2）（3）步，直到森林中只剩一棵树为止，该树即我们所求得的哈夫曼树。在构造哈夫曼树的过程中，每次由两棵权值最小的树生成一棵新树时，新树的左子树和右子树可以任意安排，这样将会得到具有不同结构的多个哈夫曼树。为了得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的权要小于等于右子树根结点的权。四、详细设计（1）哈夫曼树的结构体typedef struct char ch;int weight; int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;（2）主函数部分Int main() 初始化：输入字符代码以及权值 编制哈夫曼码：根据权值建立二叉树，输出相应的根节点到叶结点的路径，但是哈夫曼编码。 编码：输入字符，输出哈夫曼码 译码：输入哈夫曼，输出字符代码 退出：结束进程，退出程序 Return 0;五、程序代码#include#include#include#include#includetypedef struct /哈夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /选出最小的节点for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /构建哈夫曼树HT，并求出n个字符的哈夫曼编码HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化n个叶子结点printf(请输入第%d字符信息和权值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立哈夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /给n个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件输入输出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;while(choice!=Q) /当choice的值不为Q时循环cout *哈夫曼编码/译码器*n; cout *I.初始化哈夫曼树 *n; cout *E.编码*n; cout *D.译码*n; cout *Q.退出*n; coutchoice; if(choice=I) /初始化哈夫曼树coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();cout哈夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!endl; else if(choice=E) /进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中printf(请输入字符：);gets(str);output_file.open(ToBeTran.txt);if(!output_file)coutcant oen file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)output_fileHCj;break;output_file.close();coutn;cout编码完毕，并且已经存入CodeFile.txt文件！n;input_file.open(CodeFile.txt); /从CodeFile.txt中读入编码，输出在终端if(!input_file)coutcant oen file!code;cout编码码值为：codeendl;input_file.close(); else if(choice=D) /读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中input_file.