《数据结构完整的课程设计报告哈夫曼编译码器》由会员分享，可在线阅读，更多相关《数据结构完整的课程设计报告哈夫曼编译码器（27页珍藏版）》请在金锄头文库上搜索。
1、课 程 设 计 任 务 书课程名称 数据结构课程设计 课 题 赫夫曼编译码器 专业班级 网络工程* 学生姓名 * 学 号 * 指导老师 审 批 任务书下达日期： 2011 年 6 月 26 日任务完成日期： 2011 年 7 月 15 日一、设计内容1）问题描述对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。2）基本要求a.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。b.编码，利用建好的huffman树生成huffman编码；c.输出编码；d.译码功能；e.字符和频度如下： 字符ABCDEFGHIJKLM频度1866413223210
2、3211547571232字符NOPQRSTUVWXYZ频度20576315148518023818116二设计要求：l 课程设计报告1)需求分析a.程序的功能。1. 初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。2. 编码，利用建好的huffman树生成huffman编码；3. 输出编码；4. 译码功能；b.输入输出的要求。2)概要设计a. 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。i. void main()ii. void tohuffmancode(int n)/编码部分iii. void decode(char ch,huftree
3、 tree,int n)/译码iv. void huffman(huftree tree,int *w,int n) /生成huffman树v. void select(huftree tree,int k) /找寻parent为0,权最小的两个节点vi. void huffmancode(huftree tree,char code,int n)/输出huffman编码其流程图如下：main()Initialization（）初始化函数Input()输入待编码字符函数Encoding（）编码函数Decoding（）译码函数Code_inting()打印编码函数inting()打印哈夫曼树主函
4、数main 调用其他函数： tohuffmancode(int n)decode(char ch,huftree tree,int n) huffman(huftree tree,int *w,int n) select(huftree tree,int k) huffmancode(huftree tree,char code,int n)其主流程图如下：进行相应的操作输出结果结束一构造哈夫曼树四程序结束退出三对编码串译码二对字符串编码开始进行相应的操作(3)主要模块程序流程图下面介绍三个主要的程序模块流程图： 函数流程图： 结束统计字符种类及频率字符总数num建立哈夫曼树哈夫曼编码哈夫曼译
5、码打开文件？开始否是 流程图注释：该图比较简单，主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基础上对其进行编码，编码之后才是译码。最后输出结束。构造哈夫曼树：开始结束第i个结点权值i=num?创建哈夫曼树输出字符统计情况第i个根结点i=2*num-1?i=num?否是否是否是 流程图注释：该图是表示构造哈夫曼树的过程。首先输入num个叶结点的权值，当i=num是循环结束。然后进行哈夫曼树的构建，当i=2*num-1是循环结束。最后输出所得到的字符统计情况。哈夫曼编码：结束开始Tp.lchlid=c?i=nu
6、m?Cd-start=0,start=numCd-start=0Cd-start=1否否是是 流程图解释：该流程图表四哈夫曼编码情况。首先初始化，Cd-start=0,start=num。然后进行编码，使用了一个三目运算符。cd-start=(Tp.lchild=c) ? 0 : 1，即当cd-start=Tp.lchild= =c时，cd-start=0；当cd-start=Tp.lchild！= =c时，cd-start=1。这个编码循环一直到i=num时结束。b. 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。 有线性结构、树形结构等等。
7、3)详细设计a.采用C语言定义相关的数据类型。Char int 还有数据体结构 链表结构 等等。c. 写出各模块的类C码算法。1. void main()/主函数int i=0,n=0;int *w,weightMAX;char codeMAX;huftree treeMAX;char in;while (in!=5)cout -哈夫曼编码-endlendl;cout1 建立初始化哈夫曼树 2 输出哈夫曼编码 3 编码 4 译码 5 退出endlendl;coutin;coutendl;switch (in)case 1: coutn; cout请输入字符及对应权值:endl; for(i=1
8、;i=n;i+) cout; cinchaiweighti; huffman(tree,w,n); break; case 2:huffmancode(tree,code,n);break;case 3:tohuffmancode(n);break;case 4:decode(cha,tree,n);break;2. void tohuffmancode(int n)/编码部分 int i=0,j; char anychar9999; cout请输入你要编码的字符串:endl; cinanychar; cout编码为:; for (;anychari!=0;i+) j=0; for(;anyc
9、hari!=chaj&j=n;) j+; if (j=n) couthcj; coutendl;3. 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!=10) 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;coutendlend
10、l;4. void 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+) 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
11、.parent=i; trees2.parent=i; treei.lchild=s1; treei.rchild=s2; treei.weight =trees1. weight+ trees2.weight; 5. void select(huftree tree,int k) /找寻parent为0,权最小的两个节点 int i;for (i=1;i=k & treei.parent!=0 ;i+); s1=i; for (i=1;i=k;i+) if (treei.parent=0 & treei.weighttrees1.weight) s1=i; for (i=1; i=k ; i
