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

本文格式为Word版，下载可任意编辑——上海交大数据结构实验报告上海交大--数据结构-试验报告

————————————————————————————————:

————————————————————————————————日期:

《数据结构》试验报告

说明：本软件在wiｎ7６4位系统测试通过,需要安装．ｎet３.５以上版本

七、数制转换问题

1.问题描述

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

2.任务要求

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

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

3.试验指导

(1)试验类型：

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

(2)预备知识：

栈的基本定义、栈的基本操作算法、栈的存储结构。

(３)实现方法提醒:

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

N

Ｎdiｖ8

Nmｏd8

1348

168

4

１68

21

0

21

2

5

２

０

２

２）设计数制转换的算法。

4.实现方案

方案描述：

本方案采用Ｃ＃语言实现,实现十进制与其他进制直接的转换

实现代码：

主要实现代码如下

ｕｓinｇＳｙｓｔｅm；

ｕsｉngSysｔｅm.Ｃｏllectｉoｎs.Genｅric；

usingＳysｔem.CｏmｐoｎｅntMｏdeｌ;

usiｎgSystem.Ｄatａ;

ｕsinｇSｙsｔem.Drawinｇ;

usinｇSystem.Text；

usingSｙsteｍ.Wｉｎｄoｗs．Foｒmｓ;

namｅspacｅ进制转换器

{

pｕblｉcｐartialclａｓsMainFrm:Form

{

puｂlicMaｉnFｒm()

{

IniｔialｉzｅCompｏｎｅnt（);

｝

pｒivａteｖoｉｄMaｉnFrm_Ｌoａd_１（objectsｅnder,EventＡrgse)

{

txｔStａrｔ.Ｆoｃus(）;

}

／／/suｍmary＞

///十进制转换为八进制

//／/suｍmary＞

／//pａ＝ｓｅnｄer＂＜/paｒaｍ

///parａmname=＂e＞/paｒａｍ

prｉvaｔｅvoidradｉo_dｔo＿Cliｃk_１(ｏｂjectsｅ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ａramnaｍｅ＝senｄｅｒ＜/pａｒam＞

//／＜parａmｎame=＂ｅ＂／pａｒａm

pｒivａtevoiｄradio_dth_Click(objeｃtｓeｎdeｒ,EveｎtArｇse)

{

txtEnd．Text＝；

ｉf（txtStarｔ．Text.Lengｔh!=0)

｛

//ＴOＤO:十进制转换为十六进制。

Int３2i；

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ａmname=sｅndｅr／param

///＜pａrａｍnaｍe=＂e/ｐarａm

privａtｅｖoiｄｒａdiｏ_dｔb_Click（obｊectseｎｄeｒ,EvｅntArｇse)

{

ｔ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ａramnaｍe=e＞＜/paｒam

privatｅvｏidradiｏ_otd_Click(objectsenｄ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ａramname=seｎder/param

//／paramname=＂ｅ＂/pａram

pｒivatｅｖoidraｄｉo_htd_Ｃｌiｃk(oｂｊecｔｓender,EvｅntＡrgse)

｛

ｔｘ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ａmname=e＂/paｒaｍ

privatｅvｏidrａｄｉｏ_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ｖｏidresｅt_Clｉck(objectseｎdｅr,EventArgse)

{

ｔｘｔStａｒt.Text=；

txtEnd.Tｅxｔ＝;

tｘtStart．Focus();

}

priｖatevoｉdcｌｏｓe＿Ｃlick（objeｃｔsendｅｒ，ＥvｅntAｒgse)

{

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{

ｕnsignedintweｉｇht;

unsiｇnediｎtｐarenｔ，lchｉld,rｃhｉｌd;

｝ＨＴNoｄｅ,＊ＨuffmaｎTree;

4.实现方案

方案描述:

本方案采用C＃语言实现数据的Ｈufｆman编码与解码

实现代码：

主要实现代码如下:

usingSyｓtem;

uｓiｎgSysteｍ.Ｃollectioｎs.Ｇeneric；

usingSyｓtem.ComｐonentModel;

usｉnｇＳysteｍ.Data;

uｓingSyｓtｅm．Ｄraｗing；

usingSystem.Text;

usｉｎgSｙｓｔem.Wｉｎdｏｗs.Ｆormｓ;

usｉngＳyｓtｅm.Ｃollections．Ｓｐｅcializeｄ;

namespaceHuffmanCoｄe

{

puｂｌｉcｐaｒtialclaｓsForm１:Form

{

claｓsNode

{

ｐublicchａrcodｅ；

ｐuｂlｉcuiｎｔprioiｒｒy;

pubｌｉcNodｅlchild；

pｕblicNoｄerｃhｉｌd；

}

pｕbｌicFｏrm１()

{

InitiaｌｉｚeＣｏｍｐoｎｅnt（)；

}

privaｔeDicｔｉonａryｃhａｒ,strｉｎｇdｉctcode=newDｉｃtionaｒy＜ｃｈar,string();

ｐｒivateNoｄehuffTrｅe；

privateintcompａrisｏnＮodｅ(Noｄen１,Ｎoden2)

{

rｅturｎ(inｔ)(ｎ1．prioirry-n2.ｐrioｉrrｙ);

｝

privatestriｎgencode（ｓtriｎgｓtｒ）

{

dictｃoｄe．Cｌｅaｒ（)；

hｕffTree=nuｌl；

ｉf(string.ＩｓNｕｌlＯrEmpty(stｒ)）

{

reｔurｎ;

｝

Ｄicｔｉonarychaｒ,uｉntpriorｉｔyQuｅue=newDictionarychar,uinｔ()；

ｆｏr(iｎti=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=newLｉｓtＮodｅ();

ｆorｅach（variｔeminpriorｉtyQuｅｕe）

{

lｉsｔpｃ．Add(newNode（)

｛

prioｉrrｙ=item.Value，ｌchild＝nｕll,rchild=null,code=iteｍ.Ｋeｙ

})；

}

liｓtｐc.Ｓｏrt(compａｒisonＮode);

whilｅ（ｌistpc.Ｃount1)

{

Ｎoｄeｎ=ｎｅwNｏ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（ｉｎti=0;ilｉｓ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ｒneｎｃodestｒ;

｝

privatevoｉｄvieｗＴreｅ（Noden,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ｌ)

{

stringvr=ｖ+1;

viewＴree（n.ｒchilｄ,vr）；

}

}

}

ｐrｉvａｔｅsｔｒｉｎgｄecodｅ(ｓtringｓtr)

{

Ｎoｄeroot=ｈuffTree;

strinｇrｅｓｕlt＝＂;

ｆor(inｔi=0;iｓtr.Lｅｎgｔｈ;i