上海交大--数据结构-试验报告.docx

《上海交大--数据结构-试验报告.docx》由会员分享，可在线阅读，更多相关《上海交大--数据结构-试验报告.docx（16页珍藏版）》请在三一文库上搜索。

1、数据结构?实验报告说明： 本软件在 win7 64 位系统测试通过,需要安装 .net 3.5 以上版本七、数制转换问题1. 问题描述对于输入的任意一个非负十进制整数,输出与其等值的其他进制数(二进制、八进制或十六进制 ).2. 任务要求 建立模型,确定存储结构； 对任意十进制数,实现进制转换问题.3. 实验指导(1) 实验类型：设计实验. 本实验要求同学们针对“数制转换这个经典的问题,应用栈的存储结构, 自己设计一个方案, 并上机实现. 此实验的目的是培养学生对数据结构的简单应用水平.(2) 预备知识：栈的根本定义、栈的根本操作算法、栈的存储结构.(3) 实现方法提示：1) 以十进制转换为八

2、进制为例.将十进制数整除8,计算过程中得到的余数依次进栈,按出栈序列输出栈中的内容即为与输入的十进制数对应的八进制数.设 Conversion 函数执行数制转换的操作,对 (1348)10 转换为 8 进制的过程如下：NN div 8N mod 81348168416821021252022) 设计数制转换的算法.4. 实现方案1) 方案描述：本方案采用C#语言实现,实现十进制与其他进制直接的转换2) 实现代码：主要实现代码如下using System;using System.Collections.Generic;using System.ComponentModel;using Syst

3、em.Data;using System.Drawing;using System.Text;using System.Windows.Forms;namespace 进制转换器public partial class MainFrm : Formpublic MainFrm()InitializeComponent();private void MainFrm_Load_1( object sender, EventArgs e) txtStart.Focus();/ / 十进制转换为八进制/ / / private void radio_dto_Click_1( object sender

4、, EventArgs e) txtEnd.Text = ;if (txtStart.Text.Length != 0)/ TODO: 十进制转为八进制.Int32 i;tryi = Convert .ToInt32(txtStart.Text.Trim();lblTitle.Text = 十进制转为八进制 ;txtEnd.Text = Convert .ToString(i, 8);catchMessageBox.Show( 请输入合法的十进制数 , 提示,MessageBoxButtons .OK, MessageBoxIcon.Warning);elseMessageBoxShow(请提

5、供转换数据!,提示,MessageBoxButtons .0K,MessageBoxIcon.Warning);txtStart.Focus();/ / 十进制转换为十六进制/ / / private void radio_dth_Click( object sender, EventArgs e)txtEnd.Text = ;if (txtStart.Text.Length != 0)/ TODO: 十进制转换为十六进制.Int32 i;tryi =Convert .ToInt32(txtStart.Text.Trim();lblTitle.Text =十进制转换为十六进制 ;txtEnd.

6、Text =Convert .ToString(i, 16);catchMessageBoxShow(请输入合法的十进制数 ,提示 MessageBoxButtons .OK, MessageBoxIcon.Warning);elseMessageBoxShow(请提供转换数据!,提示,MessageBoxButtons .0K, MessageBoxIcon.Warning);txtStart.Focus();/ / 十进制转换为二进制/ / / private void radio_dtb_Click( object sender, EventArgs e) txtEnd.Text = ;

7、if (txtStart.Text.Length != 0)/ TODO: 十进制转换为二进制.Int32 i;tryi =Convert .ToInt32(txtStart.Text.Trim();lblTitle.Text =十进制转换为二进制 ;txtEnd.Text =Convert .ToString(i, 2);catchMessageBoxShow(请输入合法的十进制数 ,提示, MessageBoxButtons .OK, MessageBoxIcon.Warning);elseMessageBoxShow(请提供转换数据!,提示,MessageBoxButtons .0K,

8、MessageBoxIcon.Warning);txtStart.Focus();/ / 八进制到十进制/ /private void radio_otd_Click( object sender, EventArgs e)txtEnd.Text = ;if (txtStart.Text.Length != 0)/ TODO: 八进制到十进制.trylblTitle.Text = 八进制到十进制 ;txtEnd.Text =Convert .ToString( Convert .ToInt32(txtStart.Text.Trim(), 8); / 八进制转为十进制catchMessageBo

9、x.Show( 请提供合法的八进制数 , 提示, MessageBoxButtons .OK, MessageBoxIcon.Warning);elseMessageBoxShow(请提供转换数据!,提示,MessageBoxButtons .0K, MessageBoxIcon.Warning);txtStart.Focus();/ / 十六进制到十进制/ /private void radio_htd_Click( object sender, EventArgs e)txtEnd.Text = ;if (txtStart.Text.Length != 0)try/ TODO: 十六进制到

10、十进制.lblTitle.Text = 十六进制到十进制16);txtEnd.Text =Convert .ToString( Convert .ToInt32(txtStart.Text,catchMessageBox.Show( 请提供合法的十六进制数 ! , 提示, MessageBoxButtons .OK, MessageBoxIcon.Warning);elseMessageBoxShow(请提供转换数据!,提示,MessageBoxButtons .0K, MessageBoxIcon.Warning);txtStart.Focus();/ / 二进制到十进制/ /private

11、 void radio_btd_Click( object sender, EventArgs e) txtEnd.Text = ;if (txtStart.Text.Length != 0)try/ TODO: 二进制到十进制.lblTitle.Text =二进制到十进制 ;txtEnd.Text= Convert .ToString( Convert .ToInt32(txtStart.Text, 2);catchMessageBoxShow(请提供合法的二进制数!,提示, MessageBoxButtons .OK, MessageBoxIcon.Warning);elseMessage

12、BoxShow(请提供转换数据!,提示,MessageBoxButtons .0K, MessageBoxIcon.Warning);txtStart.Focus();private void reset_Click( object sender, EventArgs e) txtStart.Text =;txtEnd.Text =;txtStart.Focus();private void close_Click( object sender, EventArgs e)this .Close();3) 测试过程:1.不输入数据,软件会温馨提示2 输入数据选择转换模式3测试完成,结果正确十四、

13、Huffman编码1问题描述设某编码系统共有n个字符,使用频率分别为 1, 2,n,设计一个不等长的编码方案, 输出每个字符对应的编码,使得该编码系统的空间效率最好.2. 任务要求掌握Huffman树的概念、特点和存储结构；掌握Huffman树的构造算法；运用Huffman树解决编码问题.3. 实验指导(1)实验类型：设计实验.本实验要求同学们针对Huffman树这个经典的问题,应用二叉树这种数 据结构,自己设计一个解决方案,并上机实现.此实验目的是培养学生对数据结构的简 单应用水平.(2)预备知识：二叉树的定义、二叉树的根本操作算法.(3) 实现方法提示：1) 以字符出现的次数1, 2,n为

14、权值,n个结点作为根结点分别构成n棵二叉树;2) 所有二叉树中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树,新二叉树根结点的权值为左右子树上根结点的权值之和,并删除原先的两棵二叉树;3) 重复上述步骤,直到只剩一棵二叉树为止.4) Huffman 树的存储结构如下：structunsigned int weight;unsigned int parent, lchild, rchild;HTNode, *HuffmanTree;4. 实现方案1) 方案描述：本方案采用C#语言实现数据的Hufman编码与解码2) 实现代码：主要实现代码如下 :using System;using Sy

15、stem.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;using System.Collections.Specialized;namespace HuffmanCodepublic partial class Form1 : Formclass Nodepublicchar code;publicuint prioirry;publicNode lchild;publicNo

16、de rchild;public Form1()InitializeComponent();private Dictionary dictcode = new Dictionary();private Node huffTree;private int comparisonNode( Node n1, Node n2) return ( int )(n1.prioirry - n2.prioirry);private string encode( string str) dictcode.Clear();huffTree = null ;if ( string .IsNullOrEmpty(s

17、tr) return ;Dictionary priorityQueue =new Dictionary();for ( int i = 0; i str.Length; i+)if (priorityQueue.ContainsKey(stri)priorityQueuestri+;elsepriorityQueue.Add(stri, 1);List listpc = new List (); foreach ( var item in priorityQueue) listpc.Add( new Node()prioirry = item.Value, lchild =);null ,

18、rchild =null , code = item.Keylistpc.Sort(comparisonNode);while (listpc.Count 1)Node n = new Node();n.prioirry = listpc0.prioirry + listpc1.prioirry; n.lchild = listpc0;n.rchild = listpc1;listpc.RemoveAt(0);listpc.RemoveAt(0);int index = -1;for ( int i = 0; i listpc.Count; i+)if (n.prioirry = listpc

19、i.prioirry)index = i;break ;if (index = -1)index = listpc.Count;listpc.Insert(index, n);string encodestr = ;viewTree(listpc0, ); huffTree = listpc0;for ( int i = 0; i str.Length; i+)encodestr += dictcodestri;return encodestr;private void viewTree( Node n, string v)if (n.code != 0 )dictcode.Add(n.cod

20、e, v);elseif (n.lchild !=null )string vl = v + 0 ; viewTree(n.lchild, vl);if (n.rchild != null )string vr = v + 1 ; viewTree(n.rchild, vr);private string decode( string str)Node root = huffTree;string result = ;for ( int i = 0; i str.Length; i+)if (root.code !=0 )result += root.code.ToString();root

21、= huffTree;if (stri = 0 )root = root.lchild;elseroot = root.rchild;if (root.code != 0 )result += root.code.ToString();return result;EventArgs e)private void button1_Click_1( object sender, textBox2.Text = encode(textBox1.Text);private void button2_Click_1( object sender, EventArgs e)textBox3.Text = decode(textBox2.Text);private void button3_Click( object sender, EventArgs e) this .Close();private void button4_Click( object sender, EventArgs e)textBox1.Text =;textBox2.Text =;textBox3.Text =;4) 测试过程:1.输入任意数据,选择编码,输出结果Hufman编码2.输入刚刚的Huffman编码,选择解码,那么解码结果为原始数据3.测试完成.