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

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() && (p.link.data.getfreq() >= htemp.getfreq() break; p = p.link; etemp.link = p.li

8、nk; p.link = etemp;五、 总结1、 工作时间（5号黑色）6.30：c#“数学式中括号是否匹配”栈的应用7.1：c#“十进制转换成其他进制数”、数学式子的运算栈 7.2-7.4：课程设计：电文的编码与译码选课题；复习哈夫曼编码；输入代码并调试程序（大部分时间）；2、 心得体会经过这一个星期的数据结构课程，我对程序的编译知识加深了许多。主要体现在栈的应用和树的应用。利用栈的后进先出原理，我们可以解决判断括号匹配问题，进制转换问题和算式问题等等。除此之外，我深刻的了解了二叉树中哈夫曼树的构造步骤，它应用于电文的编码译码。这一周的学习，我捡回很多之前程序课的内容，虽然这当中出现了许多

9、问题，但有问题才有进步，同时也让我体会到了这门学科的神奇之处。附页（源代码附加注释）1. 电文编码和译文二、 public 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);

10、 /调用 treelist中的方法十四、 for (int i = 0; i < textbox1.text.length; i+) /将输入的每一个字符执行下面的方法十五、 treelist.addsign(textbox1.texti.tostring(); /计算每个字符的频率并建立字符间的连接十六、 treelist.sorttree(); /排序十七、 while (treelist.length() > 1) /最小叶子节点求和十八、 treelist.mergetree();十九、 treelist.makekey(treelist.removetree(), &qu

11、ot;");二十、 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" 二十七、 二

12、十八、 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 < textbox1.text.length; i+) /将输入的每一个字符执行下面的方法三十五、 treelist.addsign(textbox1.texti.tostring()

13、; /计算每个字符的频率并建立字符间的连接三十六、 treelist.sorttree(); /排序三十七、 while (treelist.length() > 1) /把输入的电文序列合并为一课树三十八、 treelist.mergetree();三十九、 treelist.makekey(treelist.removetree(), "");四十、 string newstr = treelist.translate(textbox1.text);四十一、 string signtable = treelist.getsigntable();四十二、 strin

14、g keytable = treelist.getkeytable();四十三、 string print = treelist.code(textbox4.text);四十四、 treelist.code(textbox4.text);四十五、 textbox5.text = print;/输入对应编码 打印译文四十六、 四十七、 class node四十八、 四十九、 public huffmantree data;五十、 public node link; /连接五十一、 public node(huffmantree newdata)五十二、 五十三、 data = newdata;

15、/存储数据五十四、 五十五、 五十六、 class huffmantree /haffman树类 五十七、 五十八、 private huffmantree leftchild; 五十九、 private huffmantree rightchild;六十、 private string letter;六十一、 private int freq;六十二、 public huffmantree(string letter)六十三、 六十四、 this.letter = letter;六十五、 this.freq = 1;六十六、 六十七、 public void setleftchild(huf

16、fmantree newchild)六十八、 六十九、 leftchild = newchild;七十、 七十一、 public void setrightchild(huffmantree newchild)七十二、 七十三、 rightchild = newchild;七十四、 七十五、 public void setletter(string newletter)七十六、 七十七、 letter = newletter;七十八、 七十九、 public void incfreq()八十、 八十一、 freq+;八十二、 八十三、 public void setfreq(int newfr

17、eq)八十四、 八十五、 freq = newfreq;八十六、 八十七、 public huffmantree getleftchild()八十八、 八十九、 return leftchild;九十、 九十一、 public huffmantree getrightchild()九十二、 九十三、 return rightchild;九十四、 九十五、 public int getfreq()九十六、 九十七、 return freq;九十八、 九十九、 public string getsign()百、 百一、 return letter;百二、 百三、 百四、 class treelis

18、t百五、 百六、 int count = 0;百七、 node first = null; /头节点为空百八、 static string signtable = null; /字符百九、 static string keytable = null; /编码百十、百十一、 public treelist(string input)百十二、 百十三、 list<char> list = new list<char>();百十四、 for (int i = 0; i < input.length; i+) /将input中不同的元素加入表中 百十五、 百十六、 if

19、(!list.contains(inputi)百十七、 list.add(inputi);百十八、 百十九、 signtable = new stringlist.count; /list中元素赋值给signtable、 keytable百二十、 keytable = new stringlist.count;百二十一、 百二十二、 public string getsigntable()百二十三、 百二十四、 return signtable;百二十五、 /获取字符百二十六、 public string getkeytable()百二十七、 百二十八、 return keytable;百二十

20、九、 /获取编码百三十、 public void addletter(string letter) /建立一棵树连接起字符串百三十一、 百三十二、 huffmantree htemp = new huffmantree(letter);百三十三、 node etemp = new node(htemp);百三十四、 if (first = null)百三十五、 first = etemp;百三十六、 else百三十七、 百三十八、 etemp.link = first;百三十九、 first = etemp;百四十、 百四十一、 count+;百四十二、 百四十三、 public void s

21、orttree() /排序树百四十四、 百四十五、 if (first != null && first.link != null)百四十六、 百四十七、 node tmp1;百四十八、 node tmp2;百四十九、 for (tmp1 = first; tmp1 != null; tmp1 = tmp1.link) /将字符以频率从小到大排序百五十、 for (tmp2 = tmp1.link; tmp2 != null; tmp2 = tmp2.link)百五十一、 百五十二、 if (tmp1.data.getfreq() > tmp2.data.getfreq(

22、)百五十三、 百五十四、 huffmantree tmpht = tmp1.data;百五十五、 tmp1.data = tmp2.data;百五十六、 tmp2.data = tmpht;百五十七、 百五十八、 百五十九、 百六十、 百六十一、 public void mergetree()百六十二、 百六十三、 if (!(first = null)百六十四、 if (!(first.link = null)百六十五、 百六十六、 huffmantree atemp = removetree();百六十七、 huffmantree btemp = removetree();百六十八、 hu

23、ffmantree sumtemp = new huffmantree("x");百六十九、 sumtemp.setleftchild(atemp);百七十、 sumtemp.setrightchild(btemp);百七十一、 sumtemp.setfreq(atemp.getfreq() + btemp.getfreq(); /两个叶子节点之和百七十二、 inserttree(sumtemp);百七十三、 百七十四、 百七十五、 public huffmantree removetree() /将叶子节点移开百七十六、 百七十七、 if (!(first = null)

24、百七十八、 百七十九、 huffmantree htemp;百八十、 htemp = first.data;百八十一、 first = first.link;百八十二、 count-;百八十三、 return htemp;百八十四、 百八十五、 return null;百八十六、 百八十七、 public void inserttree(huffmantree htemp)百八十八、 百八十九、 node etemp = new node(htemp);百九十、 if (first = null)百九十一、 first = etemp;百九十二、 else百九十三、 百九十四、 node p

25、= first;百九十五、 while (!(p.link = null) /3中取2小百九十六、 百九十七、 if (p.data.getfreq() <= htemp.getfreq() &&百九十八、 (p.link.data.getfreq() >= htemp.getfreq()百九十九、 break;二百、 p = p.link;二百一、 二百二、 etemp.link = p.link;二百三、 p.link = etemp;二百四、 二百五、 count+; /二百六、 二百七、 public int length()二百八、 二百九、 return

26、 count;二百十、 二百十一、 public void addsign(string str) /计算字符的频率二百十二、 二百十三、 if (first = null)二百十四、 二百十五、 addletter(str);二百十六、 return;二百十七、 二百十八、 node tmp = first;二百十九、 while (tmp != null)二百二十、 二百二十一、 if (tmp.data.getsign() = str) /相同时频率加一二百二十二、 二百二十三、 tmp.data.incfreq();二百二十四、 return;二百二十五、 二百二十六、 tmp = t

27、mp.link;二百二十七、 二百二十八、 addletter(str);二百二十九、 二百三十、 public string translate(string original) /译成编码串二百三十一、 二百三十二、 string newstr = ""二百三十三、 for (int i = 0; i < original.length; i+)二百三十四、 for (int j = 0; j < signtable.length; j+)二百三十五、 if (originali.tostring() = signtablej)二百三十六、 newstr +

28、= keytablej;二百三十七、 return newstr;二百三十八、 二百三十九、 int pos = 0;二百四十、 public void makekey(huffmantree tree, string code) /哈夫曼树编号方法二百四十一、 二百四十二、 if (tree.getleftchild() = null)二百四十三、 二百四十四、 signtablepos = tree.getsign();二百四十五、 keytablepos = code;二百四十六、 pos+;二百四十七、 二百四十八、 else二百四十九、 二百五十、 makekey(tree.getl

29、eftchild(), code + "0");二百五十一、 makekey(tree.getrightchild(), code + "1");二百五十二、 二百五十三、 二百五十四、 public string code(string pcode)二百五十五、 二百五十六、 string print=""二百五十七、 string ptr = null;二百五十八、 for (int i = 0; i < pcode.length; i+)二百五十九、 二百六十、 ptr += pcodei;二百六十一、 二百六十二、 fo

30、r (int j = 0; j < keytable.length; j+)二百六十三、 二百六十四、 if (ptr = keytablej)二百六十五、 二百六十六、 print += signtablej;二百六十七、 ptr = null;二百六十八、 二百六十九、 二百七十、 二百七十一、 if (ptr = null)二百七十二、 return print;二百七十三、 else二百七十四、 return ptr ="编码有误" 二百七十五、 二百七十六、 2.检查数学表达式中括号是否匹配 static void main(string args) con

31、sole.write("输入一个数学式:"); stack<char> list = new stack<char>(); string str = convert.tostring(console.readline(); foreach (char a in str) /中括号 if ("".contains(a) list.push(a); if (list.count != 0 ) char top = list.peek(); if (top = '(') console.writeline("n

32、ot match"); console.readline(); return; if ("".contains(a) bool ismatch = false; /只有 if (list.count = 0) console.writeline("not match"); console.readline(); return; else char top = list.peek(); if (top = '') ismatch = ('' = a); /a为）时匹配 if (ismatch) list.pop()

33、; else console.writeline("not match"); console.readline(); return; /小括号 if ("(".contains(a) list.push(a); /将（入站 if (")".contains(a) bool ismatch = false; /只有） char top = list.peek(); if (top = '(') ismatch = (')' = a); /a为）时匹配 else if(list.count=0|top =

34、'') console.writeline("not match"); console.readline(); return; if (ismatch) list.pop(); else console.writeline("not match"); console.readline(); return; if (list.count = 0) console.writeline(" match"); else console.writeline("not match"); console.read

35、line(); 3.十进制转化static void main(string args) console.writeline("输入一个十进制的数:"); stack<int> list = new stack<int>(); /栈 list int x = convert.toint32(console.readline();/十进制数x console.writeline("输入将转化的进制数："); int y=convert.toint16(console.readline();/y进制 int x= x / y; /除数x list.push(x % y); /余数入栈 while (x != 0) list.push( x % y); x = x / y; /第二除数、余数 while( list.count>0) /?why console.write(list.pop(); console.readline(); 4.计算一个算式 static void main(string args) class1 c1 = new class