上海交大 数据结构 实验报告.doc

_数据结构实验报告说明：本软件在win7 64位系统测试通过，需要安装.net 3.5以上版本七、数制转换问题1.问题描述对于输入的任意一个非负十进制整数，输出与其等值的其他进制数(二进制、八进制或十六进制)。2.任务要求 建立模型，确定存储结构； 对任意十进制数，实现进制转换问题。 3.实验指导(1) 实验类型：设计实验。本实验要求同学们针对“数制转换”这个经典的问题，应用栈的存储结构，自己设计一个方案，并上机实现。此实验的目的是培养学生对数据结构的简单应用能力。(2) 预备知识：栈的基本定义、栈的基本操作算法、栈的存储结构。(3) 实现方法提示：1) 以十进制转换为八进制为例。将十进制数整除8，计算过程中得到的余数依次进栈，按出栈序列输出栈中的内容即为与输入的十进制数对应的八进制数。设Conversion函数执行数制转换的操作，对(1348)10 转换为8进制的过程如下：NN div 8N mod 81348168416821021252022) 设计数制转换的算法。4.实现方案1) 方案描述： 本方案采用语言实现，实现十进制与其他进制直接的转换2) 实现代码：主要实现代码如下using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;namespace 进制转换器 public partial class MainFrm : Form public MainFrm() InitializeComponent(); private void MainFrm_Load_1(object sender, EventArgs e) txtStart.Focus(); / / 十进制转换为八进制 / / / private void radio_dto_Click_1(object sender, EventArgs e) txtEnd.Text = ; if (txtStart.Text.Length != 0) / TODO: 十进制转为八进制。 Int32 i; try i = Convert.ToInt32(txtStart.Text.Trim(); lblTitle.Text = 十进制转为八进制; txtEnd.Text = Convert.ToString(i, 8); catch MessageBox.Show(请输入合法的十进制数, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); else MessageBox.Show(请提供转换数据!, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); txtStart.Focus(); / / 十进制转换为十六进制 / / / private void radio_dth_Click(object sender, EventArgs e) txtEnd.Text = ; if (txtStart.Text.Length != 0) / TODO: 十进制转换为十六进制。 Int32 i; try i = Convert.ToInt32(txtStart.Text.Trim(); lblTitle.Text = 十进制转换为十六进制; txtEnd.Text = Convert.ToString(i, 16); catch MessageBox.Show(请输入合法的十进制数, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); else MessageBox.Show(请提供转换数据!, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); txtStart.Focus(); / / 十进制转换为二进制 / / / private void radio_dtb_Click(object sender, EventArgs e) txtEnd.Text = ; if (txtStart.Text.Length != 0) / TODO: 十进制转换为二进制。 Int32 i; try i = Convert.ToInt32(txtStart.Text.Trim(); lblTitle.Text = 十进制转换为二进制; txtEnd.Text = Convert.ToString(i, 2); catch MessageBox.Show(请输入合法的十进制数, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); else MessageBox.Show(请提供转换数据!, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); txtStart.Focus(); / / 八进制到十进制 / / / private void radio_otd_Click(object sender, EventArgs e) txtEnd.Text = ; if (txtStart.Text.Length != 0) / TODO: 八进制到十进制。 try lblTitle.Text = 八进制到十进制; txtEnd.Text = Convert.ToString(Convert.ToInt32(txtStart.Text.Trim(), 8);/八进制转为十进制 catch MessageBox.Show(请提供合法的八进制数, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); else MessageBox.Show(请提供转换数据!, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); txtStart.Focus(); / / 十六进制到十进制 / / / private void radio_htd_Click(object sender, EventArgs e) txtEnd.Text = ; if (txtStart.Text.Length != 0) try / TODO: 十六进制到十进制。 lblTitle.Text = 十六进制到十进制; txtEnd.Text = Convert.ToString(Convert.ToInt32(txtStart.Text, 16); catch MessageBox.Show(请提供合法的十六进制数!, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); else MessageBox.Show(请提供转换数据!, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); txtStart.Focus(); / / 二进制到十进制 / / / private 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); catch MessageBox.Show(请提供合法的二进制数!, 提示, MessageBoxButtons.OK, MessageBoxIcon.Warning); else MessageBox.Show(请提供转换数据!, 提示, MessageBoxButtons.OK, 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.测试完成，结果正确十四、Huffman编码1.问题描述设某编码系统共有个字符，使用频率分别为，设计一个不等长的编码方案，输出每个字符对应的编码，使得该编码系统的空间效率最好。2.任务要求 掌握Huffman树的概念、特点和存储结构； 掌握Huffman树的构造算法； 运用Huffman树解决编码问题。 3.实验指导(1) 实验类型：设计实验。本实验要求同学们针对“Huffman树”这个经典的问题，应用二叉树这种数据结构，自己设计一个解决方案，并上机实现。此实验目的是培养学生对数据结构的简单应用能力。(2) 预备知识：二叉树的定义、二叉树的基本操作算法。(3) 实现方法提示：1) 以字符出现的次数为权值，个结点作为根结点分别构成棵二叉树；2) 所有二叉树中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，新二叉树根结点的权值为左右子树上根结点的权值之和，并删除原先的两棵二叉树；3) 重复上述步骤，直到只剩一棵二叉树为止。4) Huffman树的存储结构如下： struct unsigned int weight; unsigned int parent, lchild, rchild;HTNode, *HuffmanTree;4.实现方案1) 方案描述： 本方案采用语言实现数据的Huffman编码与解码2) 实现代码：主要实现代码如下:using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;using System.Collections.Specialized;namespace HuffmanCode public partial class Form1 : Form class Node public char code; public uint prioirry; public Node lchild; public Node 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(str) return ; Dictionary priorityQueue = new Dictionary(); for (int i = 0; i str.Length; i+) if (priorityQueue.ContainsKey(stri) priorityQueuestri+; else priorityQueue.Add(stri, 1); List listpc = new List(); foreach (var item in priorityQueue) listpc.Add(new Node() prioirry = item.Value, lchild = null, rchild = null, code = item.Key ); listpc.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 = listpci.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.code, v); else if (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