资源预览内容
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
第9页 / 共24页
第10页 / 共24页
亲,该文档总共24页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
哈弗曼编码译码器专 业 班 级 :XXXX学 号 :XXXX姓 名 :XXXX指 导 教 师 :XXXX课程设计时间:XXXX计算机专业 数据结构 课程设计任务书学生姓名XXXX专业班级XXXX学号XXXX题 目哈弗曼编码译码器课题性质工程设计课题来源XXXX指导教师XXXX同组姓名XXXX 主要内容 设计一个哈弗曼编码译码器,实现哈夫曼树的建立,树形输出,编码和解码。任务要求1研究哈弗曼树的数据存储方式2实现哈弗曼编码译码器的主要算法3分析算法的运行效率4具有良好的运行界面5算法具有良好的健壮性6按要求撰写课程设计报告和设计总结。参考文献1数据结构(C语言版),严蔚敏、吴伟民,清华大学出版社,1997.审查意见指导教师签字: 教研室主任签字: 年 月 日 1 需求分析 设计一个哈弗曼编码译码器,实现哈夫曼树的建立,树形输出,编码和解码。2 概要设计main 退出系统帮助 哈夫曼文件解码 哈夫曼文件编码 树形输出哈夫曼树查看哈夫曼编码建立哈夫曼树 3 运行环境(软、硬件环境)1) 硬件:PC机2) 操作系统:Windows 2000/XP/20033) 编译环境:Visual C+6.04 开发工具和编程语言开发工具:VISCALL c+6.0;编程语言:C语言。5 详细设计 #include #include #include typedef struct / 结点的结构 unsigned int weight; / 结点的权值unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / 动态分配数组存储哈夫曼树 typedef char *HuffmanCode; / 动态分配数组存储哈夫曼编码 HuffmanTree HT; HuffmanCode HC; int n=8;const char menu=|1 建立哈夫曼树 |n|2 查看哈夫曼编码 |n|3 树形输出哈夫曼树 |n|4 哈夫曼文件编码 |n|5 哈夫曼文件解码 |n|6 帮助 |n|7 退出系统 |n;const char helpsabout=|主要功能: |n | 利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息的传输时间,降低 |n|传输成本。但是,这要求在发送端通过一个编码系统对待传输的数据预先编码,在接收 |n|端将传来的数据进行译码(复原)。对于双工信道,每端都要有一个完整的编/译码系 |n|统。本系统即是为这样的信息收发站写一个哈夫曼码的编/译系统。 |n| |n| |n; void Huffmantree(); void Huffmancode(); void preorder(); void stringcopy(); int min(); void select(); void decode(); void encode(); void int_huffmantree(); void print_end(); void print_title(); void print_menu(); void print_helpabout(); void print_huffmancode(); void print_tree();/-先序遍历-void preorder(int root,int depth)int i;for(i=1;i=depth;i+)printf( );if(depth!=0)printf();elseprintf( );printf(%d,HTroot.weight,depth);if(root=n)printf( : %sn,HCroot); / 依次输出哈夫曼编码elseprintf(n);if(HTroot.lchild!=0)depth+;preorder(HTroot.lchild,depth);if(HTroot.rchild!=0)preorder(HTroot.rchild,depth);/-字符串拷贝函数-void stringcopy(char *strDest,char *strSrc) char *strDestCopy=strDest; if (!(strDest&strSrc) printf(ERROR!); while (*strDest+=*strSrc+)!=0); /-返回哈夫曼树t的前i个结点中权值最小的树的根结点序号,函数select()调用- int min(HuffmanTree t,int i) int j,m; unsigned int k=0xffffffff; / k存最小权值,初值取为不小于可能的值 for(j=1;j=i;j+) / 对于前i个结点 if(tj.weights2) / s1的序号大于s2的 / 交换 j=s1; s1=s2; / s1是权值最小的2个中序号较小的 s2=j; / s2是权值最小的2个中序号较小的 /-w存放n个字符的权值(均0),构造哈夫曼树HT- void Huffmantree(int *w) int m,i,s1,s2; HuffmanTree p; if(n=1) / 叶子结点数不大于n return ; m=2*n-1; / n个叶子结点的哈夫曼树共有m个结点 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;i=n;+i,+p,+w) / 从1号单元开始到n号单元,给叶子结点赋值 / p的初值指向1号单元 (*p).weight=*w; / 赋权值 (*p).parent=0; / 双亲域为空(是根结点) (*p).lchild=0; / 左右孩子为空(是叶子结点,即单结点树) (*p).rchild=0; for(;i=m;+i,+p) / i从n+1到m (*p).parent=0; / 其余结点的双亲域初值为0 for(i=n+1;i=m;+i) / 建哈夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; / i号单元是s1和s2的双亲 HTi.lchild=s1; / i号单元的左右孩子分别是s1和s2 HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; / i号单元的权值是s1和s2的权值之和 /-并求出n个字符的哈夫曼编码HC-void Huffmancode() in
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号