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

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);