电文的编码和译码数据结构课程设计报告

《电文的编码和译码数据结构课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计报告项目名称：姓名班级名称：专业名称：完成时间:计算机与信息工程学院制目录I.目录一、选题介绍3二、运行结果分析3三、算法设计的思想3四、所遇到的问题及处理方案3五、总结4一、选题介绍1.总体描述A．电文的编码和译码在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中

2、的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进

3、制代码，输入二进制代码时可以编译成字符串。B.栈栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。计算算式、进制转换和括号匹配问题都是栈的应用2.功能描述A．电文的编码和译码1）在textBox1中输入即将发送的电文字符串（textBox1.Text）2）输出字符编码（textBox2）及电文编码（textBox3）3）在textBox4中输入

4、对应电文的编码4）输出译码（textBox5）5）若输入的编码不在电文对应编码中，返回错误提示B.利用栈判断数学式中括号是否匹配1）输入一个数学式（可包含小括号和中括号）2）判断括号是否匹配二、运行结果分析1.运行界面A．电文的编码和译码1）输入电文2）点击第一个转化按钮，输出字符编码和电文编码3）输入编码4）按第二个转化按钮，输出译码5）输入的编码超出范围B.利用栈判断数学式中括号是否匹配1）输入一个数学式2）匹配则为match3)不匹配情况一：括号不成对出现”（/[/]/）”情况二：优先级错误“（[]）”C.进制转换一、算法设计的思想简单

5、介绍一下是如何实现的，算法的设计思想算法的流程图1.算法设计的思想A.电文的编码与译码总体用的是树的应用中哈夫曼编码的思想。首先将用户输入的字符串按顺序建立连接，并计算每个不同字符的出现频率作为叶子节点，再将字符以频率从小到大排序。接着将两个最小数相加，用他们的和与后面的数比较，利用循环每次选出两个最小的叶子节点，求和，将和加入到树中，并把做过运算的叶子节点从列表中移除。生成哈夫曼树后进行编码：左孩子为“0”，右孩子为“1”。显示每个字符对应的编码以及字符串整体的编码。下面输入与电文对应的编码，将其与字符编码逐个比较，完全对应则输出译文，不对

6、应则返回“输入错误”。B.利用栈判断数学式中括号是否匹配建立一个栈，有左括号时，将其入栈，遇到右括号则出栈，栈中元素为空则匹配；无左括号时，右括号单独存在，则不匹配。C.十进制数转换成其他进制进制转换的主要思想为：将十进制数除以要转化的进制，均取前一次商的整数部分作被除数并依次记下每次的余数。另外，所得到的商的最后一位余数是所求二进制数的最高位。程序思想：记录每次得到的商，并将余数入栈，知道商为0时，取出栈中元素。2.流程图A.电文的编码与译码输入字符串开始建立哈夫曼树生成哈夫曼编码输出编码输入对应编码输出译码B.利用栈判断数学式中括号是否匹

7、配开始输入带括号的数学式a是否为左括号或右括号取出元素a；a++将a入栈出栈判断栈是否为空左括号右括号不匹配，输出“notmatch”匹配，输出“macth”否栈中元素是否为空一、所遇到的问题及处理方案lA.电文的编码与译码1.字符出现次数，每个字符出现频率未知，需要计算，计算后也要调用。在Addsign方法中写入循环判断语句while(tmp!=null){if(tmp.data.GetSign()==str){tmp.data.IncFreq();return;}tmp=tmp.link2.排序后求和再比较的问题Nodep=first;w

8、hile(!(p.link==null)){if((p.data.GetFreq()<=hTemp.GetFreq())&&(p.link.data.GetFreq