《电文的编码和译码数据结构课程设计报告》由会员分享，可在线阅读，更多相关《电文的编码和译码数据结构课程设计报告（26页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告项目名称：姓名班级名称：专业名称：完成时间:计算机与信息工程学院制目 录I. 目录一、选题介绍3二、运行结果分析3三、算法设计的思想3四、所遇到的问题及处理方案3五、总结4一、 选题介绍1. 总体描述A电文的编码和译码在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，
2、它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。B.栈栈是允许在同一端进行插入和删除操作的特殊线性表。允许
3、进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。计算算式、进制转换和括号匹配问题都是栈的应用2. 功能描述A电文的编码和译码1）在textBox1中输入即将发送的电文字符串（textBox1.Text）2）输出字符编码（textBox2）及电文编码（textBox3）3）在textBox4中输入对应电文的编码4）输出译码（textBox5）5）若输入的编码不在电文对应编码中，返回错误提示 B.利用栈判断数学式中括号是否匹配1）输入一个数学式（可
4、包含小括号和中括号）2）判断括号是否匹配二、 运行结果分析1.运行界面A电文的编码和译码1）输入电文2）点击第一个转化按钮，输出字符编码和电文编码3）输入编码4）按第二个转化按钮，输出译码5）输入的编码超出范围B.利用栈判断数学式中括号是否匹配1）输入一个数学式2）匹配则为match3)不匹配情况一：括号不成对出现”（/ / / ）”情况二：优先级错误 “（ ）”C.进制转换三、 算法设计的思想 简单介绍一下是如何实现的，算法的设计思想算法的流程图1.算法设计的思想A.电文的编码与译码总体用的是树的应用中哈夫曼编码的思想。首先将用户输入的字符串按顺序建立连接，并计算每个不同字符的出现频率作为叶
5、子节点，再将字符以频率从小到大排序。接着将两个最小数相加，用他们的和与后面的数比较，利用循环每次选出两个最小的叶子节点，求和，将和加入到树中，并把做过运算的叶子节点从列表中移除。生成哈夫曼树后进行编码：左孩子为“0”，右孩子为“1”。显示每个字符对应的编码以及字符串整体的编码。下面输入与电文对应的编码，将其与字符编码逐个比较，完全对应则输出译文，不对应则返回“输入错误”。B.利用栈判断数学式中括号是否匹配建立一个栈，有左括号时，将其入栈，遇到右括号则出栈，栈中元素为空则匹配；无左括号时，右括号单独存在，则不匹配。C.十进制数转换成其他进制进制转换的主要思想为：将十进制数除以要转化的进制，均取前
6、一次商的整数部分作被除数并依次记下每次的余数。另外，所得到的商的最后一位余数是所求二进制数的最高位。程序思想：记录每次得到的商，并将余数入栈，知道商为0时，取出栈中元素。2.流程图A.电文的编码与译码 输入字符串开始建立哈夫曼树生成哈夫曼编码输出编码输入对应编码输出译码 B.利用栈判断数学式中括号是否匹配开始输入带括号的数学式a是否为左括号或右括号取出元素a；a+将a入栈出栈判断栈是否为空左括号右括号不匹配，输出“not match”匹配，输出“macth”否栈中元素是否为空四、 所遇到的问题及处理方案l A.电文的编码与译码 1.字符出现次数，每个字符出现频率未知，需要计算，计算后也要调用。
7、在Addsign方法中写入循环判断语句while (tmp != null) if (tmp.data.GetSign() = str) tmp.data.IncFreq(); return; tmp = tmp.link2.排序后求和再比较的问题Node p = first; while (!(p.link = null) if (p.data.GetFreq() = hTemp.GetFreq() break; p = p.link; eTemp.link = p.link; p.link = eTemp;五、 总结1、 工作时间（5号黑色）6.30：C#“数学式中括号是否匹配”栈的应用7
8、.1：C#“十进制转换成其他进制数”、数学式子的运算栈 7.2-7.4：课程设计：电文的编码与译码选课题；复习哈夫曼编码；输入代码并调试程序（大部分时间）；2、 心得体会经过这一个星期的数据结构课程，我对程序的编译知识加深了许多。主要体现在栈的应用和树的应用。利用栈的后进先出原理，我们可以解决判断括号匹配问题，进制转换问题和算式问题等等。除此之外，我深刻的了解了二叉树中哈夫曼树的构造步骤，它应用于电文的编码译码。这一周的学习，我捡回很多之前程序课的内容，虽然这当中出现了许多问题，但有问题才有进步，同时也让我体会到了这门学科的神奇之处。附页（源代码附加注释）1. 电文编码和译文二、 public
9、 Form1()三、 四、 InitializeComponent();五、 六、七、 private void Form1_Load(object sender, EventArgs e)八、 九、 十、 private void button1_Click(object sender, EventArgs e)十一、 十二、 textBox2.Text = null;十三、 TreeList treeList = new TreeList(textBox1.Text); /调用 TreeList中的方法十四、 for (int i = 0; i 1) /最小叶子节点求和十八、 treeLi
10、st.MergeTree();十九、 treeList.MakeKey(treeList.RemoveTree(), );二十、 string newStr = treeList.translate(textBox1.Text);二十一、 string signTable = treeList.GetSignTable();二十二、 string keyTable = treeList.GetKeyTable();二十三、 二十四、 for (int i = 0; i signTable.Length; i+)二十五、 二十六、 textBox2.Text += signTablei + : + keyTablei+rn; 二十七、 二十八、 textBox3.Text = newStr; 二十九、 三十、 private void button2_Click(object sender, EventArgs e)三十一、 三十二、 TreeList treeList = new TreeList(textBox1.Text);三十三、 string code = textBox4.Text;三十四、 for (int i = 0; i 1) /把输入的电文序列合并为
