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

《数据结构》实验报告

说明：本软件在win7 64位系统测试通过，需要安装.net 3.5以上

版本

七、数制转换问题

1.问题描述

对于输入的任意一个非负十进制整数，输出与其等值的其他进制数(二进制、八进制或十六进制)。

2.任务要求

⑴ 建立模型，确定存储结构；

⑵ 对任意十进制数，实现进制转换问题。

3.实验指导

(1) 实验类型：

设计实验。本实验要求同学们针对“数制转换”这个经典的问题，应用栈的存储结构，自己设计一个方案，并上机实现。此实验的目的是培养学生对数据结构的简单应用能力。 (2) 预备知识：

栈的基本定义、栈的基本操作算法、栈的存储结构。 (3) 实现方法提示：

1) 以十进制转换为八进制为例。将十进制数整除8，计算过程中得到的余数依次进栈，按出栈序列输出栈中的内容即为与输入的十进制数对应的八进制数。设Conversion函数执行数制转换的操作，对(1348)10 转换为8进制的过程如下：

N 1348 168 21 2

2) 设计数制转换的算法。

N div 8 168 21 2 0

N mod 8 4 0 5 2

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.问题描述

设某编码系统共有n个字符，使用频率分别为{?1,?2,...,?n}，设计一个不等长的编码方案，输出每个字符对应的编码，使得该编码系统的空间效率最好。

2.任务要求

⑴ 掌握Huffman树的概念、特点和存储结构； ⑵ 掌握Huffman树的构造算法； ⑶ 运用Huffman树解决编码问题。

3.实验指导

(1) 实验类型：

设计实验。本实验要求同学们针对“Huffman树”这个经典的问题，应用二叉树这种数据结构，自己设计一个解决方案，并上机实现。此实验目的是培养学生对数据结构的简单应用能力。 (2) 预备知识：

二叉树的定义、二叉树的基本操作算法。

(3) 实现方法提示：

1) 以字符出现的次数?1,?2,...,?n为权值，n个结点作为根结点分别构成n棵二叉树； 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(str[i])) {

priorityQueue[str[i]]++; } else {

priorityQueue.Add(str[i], 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 = listpc[0].prioirry + listpc[1].prioirry; n.lchild = listpc[0]; n.rchild = listpc[1]; listpc.RemoveAt(0); listpc.RemoveAt(0); int index = -1;

for (int i = 0; i < listpc.Count; i++) {

if (n.prioirry <= listpc[i].prioirry) {

index = i; break; } }

if (index == -1) {

index = listpc.Count; }

listpc.Insert(index, n); }

string encodestr = \; viewTree(listpc[0], \); huffTree = listpc[0];

for (int i = 0; i < str.Length; i++) {

encodestr += dictcode[str[i]]; }

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 + \; viewTree(n.lchild, vl); }

if (n.rchild != null) {

string vr = v + \; 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 = huffTree; }

if (str[i] == '0') {

root = root.lchild; } else {

root = root.rchild; } }

if (root.code != '\\0') {

result += root.code.ToString(); }

return result; }

private void button1_Click_1(object sender, EventArgs e) {

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. 输入任意数据，选择编码，输出结果Huffman编码

2. 输入刚才的Huffman编码，选择解码，则解码结果为原始数据

3. 测试完成。

本文来源：https://www.bwwdw.com/article/f3z6.html