上海交大--数据结构-实验报告
———————————————————————————————— 作者:
———————————————————————————————— 日期:
《数据结构》实验报告
说明：本软件在wiｎ7 ６4位系统测试通过,需要安装．ｎet ３.５以上版本
七、数制转换问题
1.问题描述
对于输入的任意一个非负十进制整数,输出与其等值的其他进制数(二进制、八进制或十六进制)。
2.任务要求
⑴ 建立模型，确定存储结构；
⑵ 对任意十进制数,实现进制转换问题。
3.实验指导
(1) 实验类型：
设计实验。本实验要求同学们针对“数制转换”这个经典的问题,应用栈的存储结构，自己设计一个方案，并上机实现。此实验的目的是培养学生对数据结构的简单应用能力。
(2) 预备知识：
栈的基本定义、栈的基本操作算法、栈的存储结构。
(３) 实现方法提示:
1) 以十进制转换为八进制为例。将十进制数整除8，计算过程中得到的余数依次进栈，按出栈序列输出栈中的内容即为与输入的十进制数对应的八进制数。设Coｎversion函数执行数制转换的操作，对（1348)１０ 转换为8进制的过程如下:
N
Ｎ diｖ 8
N mｏd 8
1348
168
4
１68
21
0
21
2
5
２
０
２
２） 设计数制转换的算法。
4.实现方案
方案描述：
本方案采用Ｃ＃语言实现,实现十进制与其他进制直接的转换
实现代码：
主要实现代码如下
ｕｓinｇ Ｓｙｓｔｅm；
ｕsｉng Sysｔｅm.Ｃｏllectｉoｎs.Genｅric；
using Ｓysｔem.CｏmｐoｎｅntMｏdeｌ;
usiｎg System.Ｄatａ;
ｕsinｇ Sｙsｔem.Drawinｇ;
usinｇ System.Text；
using Sｙsteｍ.Wｉｎｄoｗs．Foｒmｓ;
namｅspacｅ 进制转换器
{
pｕblｉc ｐartial clａｓs MainFrm : Form
{
puｂlic MaｉnFｒm()
{
IniｔialｉzｅCompｏｎｅnt（);
｝
pｒivａte ｖoｉｄ MaｉnFrm_Ｌoａd_１（object sｅnder, EventＡrgs e)
{
txｔStａrｔ.Ｆoｃus(）;
}
／／/ <suｍmary＞
/// 十进制转换为八进制
//／ </suｍmary＞
／// <pａ＝"ｓｅnｄer＂>＜/paｒaｍ>
/// <parａm name=＂e"＞</paｒａｍ>
prｉvaｔｅ void radｉo_dｔo＿Cliｃk_１(ｏｂject sｅnｄer， ＥventAｒｇｓ e)
{
txtEnｄ．Teｘt ＝ ＂"；
iｆ (txtStart.Tｅxt．Leｎgｔh != 0）
{
／／ ＴODO: 十进制转为八进制。
Iｎt３2 ｉ；
trｙ
{
ｉ = Cｏnvert.ToInt32(ｔxtStａrt.Teｘｔ.Ｔriｍ());
lbｌTitle.Tｅｘt = "十进制转为八进制＂；
txtＥnd.Tｅxt ＝ Convert.ＴoStriｎg(ｉ, 8);
｝
cａtｃh
｛
MｅssageBox.Show(＂请输入合法的十进制数"， "提示", MessagｅBoｘButtons.OK， MeｓsageBoxＩcｏn.Warnｉｎg);
}
}
ｅlｓe
{
MessａgeBｏx.Show("请提供转换数据!"， ＂提示＂, MeｓsageBoxButtoｎs．OK, MｅｓsageBｏxIcoｎ．Wａｒniｎｇ);
}
txｔSｔart.Ｆocus();
}
/／/ ＜ｓummary>
／// 十进制转换为十六进制
／// ＜/summａry>
/// ＜pａram naｍｅ＝"senｄｅｒ">＜/pａｒam＞
//／ ＜parａm ｎame=＂ｅ＂><／pａｒａm>
pｒivａte voiｄ radio_dth_Click(objeｃt ｓeｎdeｒ, EveｎtArｇs e)
{
txtEnd．Text ＝ ""；
ｉf （txtStarｔ．Text.Lengｔh != 0)
｛
// ＴOＤO: 十进制转换为十六进制。
Int３2 i；
try
{
i = Ｃonvert.ToIｎt32(tｘtSｔart.Text.Trim());
lｂlTitle.Teｘt = "十进制转换为十六进制";
ｔxｔEnd.Text = Ｃonｖert.ToSｔring(i, 1６);
｝
caｔch
｛
MｅssａgeBｏx.Ｓhow(＂请输入合法的十进制数", "提示"， MessaｇeBｏxBuｔtoｎs.ＯK, MｅssaｇeBoxIcon.Ｗarninｇ);
}
｝
elｓe
{
ＭesｓａgeBｏx.Shｏw（＂请提供转换数据！", "提示"， MeｓsageBoxＢｕttons.ＯK, ＭeｓsageBoxIｃoｎ.Waｒning);
}
txtSｔart.Ｆoｃuｓ()；
}
/// <summary＞
／// 十进制转换为二进制
/// <／sumｍary>
/// ＜pａrａm name="sｅndｅr"><／param>
/// ＜pａrａｍ naｍe=＂e"></ｐarａm>
privａtｅ ｖoiｄ ｒａdiｏ_dｔb_Click（obｊect seｎｄeｒ, EvｅntArｇs e)
{
ｔxｔＥnd．Ｔexｔ = ""；
if (txtStaｒt．Tｅｘt.Lｅｎgｔh != 0)
{
// TＯＤO: 十进制转换为二进制。
Int3２ i;
try
{
ｉ = Ｃonvｅrt.ToInt32(txtStart．Tｅｘt.Trim());
lblTｉtlｅ．Tｅxt = ＂十进制转换为二进制"；
ｔxtEnd.Text = Coｎvert.ToStｒiｎg(i, ２)；
｝
cａtｃh
｛
ＭessａｇeBox.Sｈow(＂请输入合法的十进制数"， "提示"， MeｓsageBoxButｔons．OK, MessagｅBoxIｃon.Warning);
}
}
eｌse
{
MessageＢｏｘ.Show("请提供转换数据!", ＂提示", MesｓagｅBoxButtonｓ．OK, MeｓｓageBｏxＩcon.Warninｇ);
}
txtＳtart.Ｆｏcｕｓ();
}
／/／ <summary＞
/// 八进制到十进制
/／/ <／suｍmａｒy>
／// ＜param ｎａme="sender"></param＞
/// <pａram naｍe="e"＞＜/paｒam>
privatｅ vｏid radiｏ_otd_Click(object senｄeｒ, ＥventArｇｓ ｅ)
{
txtEnｄ.Tｅxt = "";
if （txtStart.Text.Lengｔh != 0)
{
// ＴODO: 八进制到十进制。
try
{
lbｌTｉtle．Tｅxt = ＂八进制到十进制";
ｔxtEnd.Ｔeｘt = Ｃonverｔ.ToSｔｒinｇ（Coｎvert．ToInt32(txｔStaｒt．Text.Tｒim（)， 8)）；//八进制转为十进制
}
catch
｛
MessaｇｅBox.Sｈow("请提供合法的八进制数", "提示＂, MeｓsａgeBoxBuｔtoｎs．OＫ， MessageBoxIcon.Ｗarnｉｎg);
}
}
ｅlse
{
MｅssageBoｘ.Ｓｈow（"请提供转换数据！＂, "提示", MeｓｓaｇeBoｘButtｏns.OＫ, ＭessageBoxＩｃon.Warning);
｝
txtStaｒt.Ｆocｕs()；
}
/／/ <ｓummaｒy>
//／ 十六进制到十进制
／／/ </sｕmmary＞
/// ＜pａram name="seｎder"></param>
//／ <param name=＂ｅ＂></pａram>
pｒivatｅ ｖoid raｄｉo_htd_Ｃｌiｃk(oｂｊecｔ ｓender, EvｅntＡrgs e)
｛
ｔｘtＥnd．Ｔext = ＂"；
if (tｘｔStaｒt.Text.Lenｇｔｈ！= 0)
{
ｔrｙ
｛
// TＯDO: 十六进制到十进制。
lblTｉtｌe．Ｔexｔ = ＂十六进制到十进制";
tｘｔEnｄ．Ｔext ＝ Cｏｎvert.TｏStrｉｎｇ(Ｃonverｔ．ToInt32(tｘtStaｒt.Text, 1６));
}
catｃh
{
MｅsｓageＢoｘ.Sｈow（"请提供合法的十六进制数!"， "提示"， MessａgeＢoｘＢuttｏｎs．OK， ＭｅssageBoxIｃｏn.Warniｎｇ）；
}
}
ｅｌse
{
MessaｇeBｏｘ．Show("请提供转换数据！＂, "提示", MessａgeＢｏｘBｕttｏnｓ.OK, MｅsｓａgeBoxＩcon.Warｎing)；
｝
tｘtStａｒt.Ｆｏcｕs();
｝
／/／ <ｓuｍmａry＞
/// 二进制到十进制
/// </ｓuｍmaｒy>
/// <="seｎｄｅr">＜/param>
/// <parａm name="e＂></paｒaｍ>
privatｅ vｏid rａｄｉｏ_btd＿Click(oｂｊect ｓｅnder， EｖentＡｒｇs ｅ)
｛
txｔEnd.Ｔexｔ = ＂"；
if (txtStart.Teｘt.Ｌｅｎgth != 0)
{
ｔry
{
／/ TODO： 二进制到十进制。
lblTitle.Ｔeｘt = "二进制到十进制";
ｔxtEｎｄ.Ｔｅxt = Cｏnvert.ＴoＳｔrｉng（Coｎvｅrt.ToＩnt3２(txｔSｔaｒt.Ｔext, 2));
}
ｃａtcｈ
{
MeｓsagｅＢox．Show("请提供合法的二进制数!", "提示"， MeｓsageＢoxBｕttons．ＯＫ, ＭesｓａgeBｏｘIcon．Warｎing）；
}
}
else
｛
MeｓsageＢox.Sｈoｗ（"请提供转换数据！", "提示"， MｅｓｓageBoxBｕttoｎs.ＯK， MessageＢoxIcｏｎ.Warning）;
}
ｔxtStａｒt．Focuｓ()；
}
prｉvａte ｖｏid resｅt_Clｉck(object seｎdｅr, EventArgs e)
{
ｔｘｔStａｒt.Text = ""；
txtEnd.Tｅxｔ ＝ "";
tｘtStart．Focus();
}
priｖate voｉd cｌｏｓe＿Ｃlick（objeｃｔ sendｅｒ， ＥvｅntAｒgs e)
{
this.Close(）;
}
}
}
测试过程:
不输入数据，软件会温馨提示
2.输入数据选择转换模式
3.测试完成，结果正确
十四、Huｆfman编码
1.问题描述
设某编码系统共有个字符,使用频率分别为,设计一个不等长的编码方案，输出每个字符对应的编码，使得该编码系统的空间效率最好。
2.任务要求
⑴ 掌握Ｈuｆfｍan树的概念、特点和存储结构；
⑵ 掌握Ｈｕffman树的构造算法;
⑶ 运用Huffｍａｎ树解决编码问题。
3.实验指导
（1) 实验类型：
设计实验。本实验要求同学们针对“Huffｍan树”这个经典的问题,应用二叉树这种数据结构,自己设计一个解决方案，并上机实现。此实验目的是培养学生对数据结构的简单应用能力。
（2） 预备知识:
二叉树的定义、二叉树的基本操作算法。
（3) 实现方法提示：
１） 以字符出现的次数为权值，个结点作为根结点分别构成棵二叉树;
2) 所有二叉树中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，新二叉树根结点的权值为左右子树上根结点的权值之和,并删除原先的两棵二叉树;
3） 重复上述步骤,直到只剩一棵二叉树为止。
4) Huffｍan树的存储结构如下：
struct{
ｕnsigned int weｉｇht;
unsiｇned iｎt ｐarenｔ， lchｉld, rｃhｉｌd;
｝ＨＴNoｄｅ, ＊ＨuffmaｎTree;
4.实现方案
方案描述:
本方案采用C＃语言实现数据的Ｈufｆman编码与解码
实现代码：
主要实现代码如下:
using Syｓtem;
uｓiｎg Systeｍ.Ｃollectioｎs.Ｇeneric；
using Syｓtem.ComｐonentModel;
usｉnｇ Ｓysteｍ.Data;
uｓing Syｓtｅm．Ｄraｗing；
using System.Text;
usｉｎg Sｙｓｔem.Wｉｎdｏｗs.Ｆormｓ;
usｉng Ｓyｓtｅm.Ｃollections．Ｓｐｅcializeｄ;
namespace HuffmanCoｄe
{
puｂｌｉc ｐaｒtial claｓs Form１ : Form
{
claｓs Node
{
ｐublic chａr codｅ；
ｐuｂlｉc uiｎｔ prioiｒｒy;
pubｌｉc Nodｅ lchild；
pｕblic Noｄe rｃhｉｌd；
}
pｕbｌic Fｏrm１()
{
InitiaｌｉｚeＣｏｍｐoｎｅnt（)；
}
privaｔe Dicｔｉonａry<ｃhａｒ, strｉｎｇ> dｉctcode = new Dｉｃtionaｒy＜ｃｈar, string>();
ｐｒivate Noｄe huffTrｅe；
private int compａrisｏnＮodｅ(Noｄe n１, Ｎode n2)
{
rｅturｎ (inｔ)(ｎ1．prioirry - n2.ｐrioｉrrｙ);
｝
private striｎg encode（ｓtriｎg ｓtｒ）
{
dictｃoｄe．Cｌｅaｒ（)；
hｕffTree = nuｌl；
ｉf (string.ＩｓNｕｌlＯrEmpty(stｒ)）
{
reｔurｎ "";
｝
Ｄicｔｉonary<chaｒ, uｉnt> priorｉｔyQuｅue = new Dictionary<char, uinｔ>()；
ｆｏr (iｎt i = 0; i < ｓtr.Leｎgth; i++)
{
iｆ (prｉorityQｕｅue.ＣoｎtａｉｎｓＫeｙ(ｓtr[i]))
{
priｏrｉtyQuｅuｅ［stｒ[i]]++;
}
elsｅ
{
prｉorityQｕeue.Adｄ（str[i]， 1);
}
}
Ｌist＜Nodｅ> lisｔpc = new Lｉｓt<Ｎodｅ>();
ｆorｅach （var iｔem in priorｉtyQuｅｕe）
{
lｉsｔpｃ．Add(new Node（)
｛
prioｉrrｙ = item.Value， ｌchild ＝ nｕll, rchild = null, code = iteｍ.Ｋeｙ
})；
}
liｓtｐc.Ｓｏrt(compａｒisonＮode);
whilｅ （ｌistpc.Ｃount > 1)
{
Ｎoｄe ｎ = ｎｅw Nｏde(）;
n.ｐrioirry ＝ lisｔpc[0].ｐrｉoirrｙ + listｐc［1］.prioirry;
n．lｃhild = ｌistpc[0];
n.rｃｈild = lisｔpc[１];
lｉstｐc.RemovｅAt(0)；
listｐｃ.ＲeｍoｖeAt（０);
inｔ index ＝ -1;
for （ｉｎt i = 0; i < lｉｓtpc.Count； ｉ+＋)
｛
if (n.prｉoｉrｒｙ <＝ listpc[i].priｏiｒry)
{
indeｘ ＝ i;
bｒeａk;
}
｝
if （index ＝= －1）
｛
index = ｌiｓtｐc.Cｏunt;
}
ｌiｓtpｃ.Ｉｎseｒｔ(index, ｎ）；
}
ｓtrｉnｇ eｎcｏdestｒ = ＂"；
vｉewTｒee(listpc[0], "")；
huffTｒee = ｌistpc[0］；
for （ｉｎt ｉ ＝ 0; ｉ < ｓtr．Lｅngｔｈ; i＋+)
｛
encodestｒ += dictcoｄe［stｒ[i]];
}
retuｒn eｎｃodestｒ;
｝
private voｉｄ vieｗＴreｅ（Node n, string ｖ)
{
if （n.code != ＇＼0')
{
dｉctｃode.Add(n.ｃode, v);
}
elsｅ
{
if (n.ｌchild != nｕｌl)
{
ｓｔrｉng ｖl = v ＋ "0＂；
viｅwTｒｅe(n.lcｈild, vl）；
}
iｆ (n.rchiｌｄ ！= nulｌ)
{
string vr = ｖ + "1";
viewＴree（n.ｒchilｄ, vr）；
}
}
}
ｐrｉvａｔｅ sｔｒｉｎg ｄecodｅ(ｓtring ｓtr)
{
Ｎoｄe root = ｈuffTree;
strinｇ rｅｓｕlt ＝ ＂";
ｆor (inｔ i = 0; i < ｓtr.Lｅｎgｔｈ; i++)
{
iｆ （rooｔ.code != '＼０')
{
ｒesult += root.cｏde．ＴoＳtrｉng（);
root = huffＴrｅe;
}
if （ｓtr[i] == '0')
｛
roｏt = roｏt.ｌchild；
}
eｌse
｛
root = rooｔ.ｒｃhilｄ;
}
｝
if (roｏt.codｅ != ＇\0＇)
{
ｒeｓult +＝ root.coｄe.ToSｔring()；
}
retｕｒn resuｌｔ;
}
pｒｉｖatｅ voiｄ butｔｏn１_Cｌiｃk_1(oｂject sｅnｄeｒ, ＥventArgs e）
｛
textBoｘ２.Texｔ = ｅncode(ｔｅxtBｏx1.Tｅxt）；
}
pｒivatｅ void bｕtｔon2＿Clｉｃk_1(oｂjｅcｔ seｎder, EvｅntAｒgｓ e）
{
tｅxｔBox3.Teｘt ＝ ｄeｃode(ｔextBoｘ2.Tｅxｔ）;
}
ｐrivatｅ voiｄ button３_Clｉck(ｏbject ｓeｎder, EventＡrｇｓ e)
{
ｔhis.Close（)；
}
privａtｅ voiｄ button4_Cliｃk(ｏbject sender， ＥｖeｎtＡrgs e)
{
ｔｅxtBox１.Teｘt ＝ ＂"；
ｔextBｏｘ2.Teｘｔ ＝ ＂";
tｅxtＢox3.Tｅxt = "";
}
}
}
测试过程：
输入任意数据，选择编码,输出结果Ｈuffman编码
输入刚才的Huffman编码，选择解码，则解码结果为原始数据
测试完成。
