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

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

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

3、em.Text;namespace进制转换器publicp artial class MainFrm :FormpublicMainFrm()InitializeComponent();private void MainFrm_Load_1( objectsender,EventArgs e)txtStart.Focus();/ <summary>/ 十进制转换为八进制/ </summary>/ <param name="sender"></param>98989/ <param name="e"&g

4、t;</param>private void radio_dto_Click_1(objectsender, EventArgs e)txtEnd.Text ="" ;if98989/TODO:十进制转为八进制。Int32i;tryi =Convert .ToInt32(txtStart.Text.Trim();lblTitle.Text =" 十进制转为八" ;进制txtEnd.Text =Convert .ToString(i, 8);catchMessageBox.Show("请输入合法"" 提"

5、 ,的十进制数,示MessageBoxButtons .OK,MessageBoxIcon.Warning);elseMessageBox.Show(" 请提供转换数据 !" , " 提示 " , MessageBoxButtons .OK, MessageBoxIcon .Warning);txtStart.Focus();/ <summary>/ 十进制转换为十六进制/ </summary>/ <param name="sender"></param>/ <param name

6、="e"></param>private void radio_dth_Click(objectsender,EventArgs e)txtEnd.Text ="" ;if/TODO:十进制转换为十六进制。Int32i;98989tryi =Convert .ToInt32(txtStart.Text.Trim();lblTitle.Text =" 十进制转换为十" ;txtEnd.Text =六进制Convert .ToString(i,16);catchMessageBox.Show("请输入合法的十进

7、制数" ," 提示 " ,98989MessageBoxButtons .OK,MessageBoxIcon.Warning);elseMessageBox.Show(" 请提供转换数据 !" , " 提示 " , MessageBoxButtons .OK, MessageBoxIcon .Warning);txtStart.Focus();/ <summary>/ 十进制转换为二进制/ </summary>/ <param name="sender"></pa

8、ram>/ <param name="e"></param>private void radio_dtb_Click(objectsender,EventArgs e)txtEnd.Text ="" ;if/TODO:十进制转换为二进制。Int32i;tryi =lblTitle.Text =txtEnd.Text =" 十进制转换为二进制 Convert .ToString(i, 2);" ;catchMessageBox.Show("请输入合法的十进制数" ," 提示&q

9、uot; ,MessageBoxButtons .OK,MessageBoxIcon.Warning);else98989MessageBox.Show(" 请提供转换数据 !" , " 提示 " , MessageBoxButtons .OK, MessageBoxIcon .Warning);txtStart.Focus();/ <summary>98989/ 八进制到十进制/ </summary>/ <param name="sender"></param>/ <param

10、name="e"></param>private void radio_otd_Click(objectsender,EventArgs e)txtEnd.Text ="" ;if/TODO:八进制到十进制。trylblTitle.Text =" 八进制到十" ;进制txtEnd.Text =/ 八进制转为十进制Convert .ToString(Convert .ToInt32(txtStart.Text.Trim(), 8);catchMessageBox.Show("请提供合法","

11、;提 ",的八进制数示MessageBoxButtons .OK,MessageBoxIcon.Warning);elseMessageBox.Show("请提供转换数据!","提示 ",MessageBoxButtons .OK, MessageBoxIcon .Warning);txtStart.Focus();/ <summary>/ 十六进制到十进制/ </summary>/ <param name="sender"></param>98989/ <param n

12、ame="e"></param>private void radio_htd_Click(objectsender,EventArgs e)txtEnd.Text ="" ;iftry/ TODO: 十六进制到十进制。lblTitle.Text =" 十六进制到十进制" ;98989txtEnd.Text =Convert .ToStConvert .ToInt32(txtStart.Text,ring(16);catchMessageBox.Show("请提供合法的!" , "提示 &

13、quot;,十六进制数MessageBoxButtons .OK,MessageBoxIcon.Warning);elseMessageBox.Show(" 请提供转换数据 !" , " 提示 " , MessageBoxButtons .OK, MessageBoxIcon .Warning);txtStart.Focus();/ <summary>/ 二进制到十进制/ </summary>/ <param name="sender"></param>/ <param name=

14、"e"></param>private void radio_btd_Click(objectsender,EventArgs e)txtEnd.Text ="" ;iftry/二进制到十进制。TODO:" 二进制到十lblTitle.Text =" ;进制txtEnd.Text=Convert .ToInt32(txtStart.Text, 2);Convert .ToString(98989catchMessageBox.Show("请提供合法的二进制数!" ," 提示 "

15、 , MessageBoxButtons .OK, MessageBoxIcon.Warning);elseMessageBox.Show(" 请提供转换数据 !" , " 提示 " , MessageBoxButtons .OK, MessageBoxIcon .Warning);98989txtStart.Focus();privvoireset_CliobjectEventArgs e)atedck(sender,txtStart.Text"" ;="" ;txtEnd.Text =txtStart.Focu

16、s();private void close_Click(objectsender,EventArgs e)this .Close();3) 测试过程：1. 不输入数据，软件会温馨提示2 输入数据选择转换模式989893. 测试完成，结果正确十四、 Huffman编码1. 问题描述设某编码系统共有n 个字符，使用频率分别为1 , 2 ,., n ，设计一个不等长的编码方案，输出每个字符对应的编码，使得该编码系统的空间效率最好。2. 任务要求掌握 Huffman树的概念、特点和存储结构；掌握 Huffman树的构造算法；运用 Huffman树解决编码问题。3. 实验指导(1) 实验类型：设计实验

17、。 本实验要求同学们针对“ Huffman 树”这个经典的问题，应用二叉树这种数据结构，自己设计一个解决方案，并上机实现。此实验目的是培养学生对数据结构的简单应用能力。(2) 预备知识：二叉树的定义、二叉树的基本操作算法。98989(3) 实现方法提示：1)以字符出现的次数1 , 2 ,.,n 为权值，n 个结点作为根结点分别构成n 棵二叉树；2) 所有二叉树中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，新二叉树根结点的权值为左右子树上根结点的权值之和，并删除原先的两棵二叉树；3) 重复上述步骤，直到只剩一棵二叉树为止。4) Huffman 树的存储结构如下： structunsi

18、gned int weight;unsigned int parent, lchild,rchild; HTNode, *HuffmanTree;4. 实现方案1) 方案描述：本方案采用语言实现数据的Huffman编码与解码2) 实现代码：主要实现代码如下:using System;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;namespace HuffmanCodepublicp artial class Form1 :Formclass Nodepublicchar

19、code;98989publiuinprioirctry;publiNodeclchild;publiNodecrchild;public Form1()98989InitializeComponent();privateprivDictionary<char ,> dictcode =Node huffTree;stringnewDictionary<char ,string>();ateprivateint comparisonNode(Node n1,Node n2)return( int )(n1.prioirry - n2.prioirry);privates

20、tringencode( stringstr)dictcode.Clear();huffTree =null ;if( string.IsNullOrEmpty(str)return"" ;Dictionary<char ,<char ,uint > priorityQueue =uint >();newDictionaryfor ( int i = 0; i < str.Length; i+)if(priorityQueue.ContainsKey(stri)priorityQueuestri+;elsepriorityQueue.Add(s

21、tri, 1);List <Node> listpc =98989foreach( varnew List <Node>();itemin priorityQueue)listpc.Add(new Node()prioirry = item.Value, lchild =);n,n , code = item.Keyulrchildull=llistpc.Sort(comparisonNode);98989while(listpc.Count > 1)Node n =new Node();n.prioirry = listpc0.prioirry + listpc

22、1.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);stringencodestr ="" ;viewTree(list

23、pc0,"" );huffTree = listpc0;for ( int i = 0; i < str.Length; i+)encodestr += dictcodestri;returnencodestr;privatevoid viewTree(Node n,stringv)98989if(n.code != '0')dictcode.Add(n.code, v);elseif(n.lchild !=null )98989stringvl = v"0" ;+viewTree(n.lchild,vl);ifnull )(n.rchild !=stringvr = v+viewTree(n.rchild, vr);"1" ;pr